Interpret underload

Question

The challenge

Interpret the stack-based programming language underload.

The stack is a stack of strings that can be concatenated together.

Each underload program is a string of some of these instructions:

• ~: Swap the top two elements of the stack.
• :: Duplicate the top element of the stack.
• !: Discard the top element of the stack.
• *: Concatenate the top two elements of the stack together.
• (x): Push the string between the parenthesis to the stack. Parentheses can nest within strings, so (a(bc)d) should push the string a(bc)d to the stack, not a(bc.
• a: Enclose the top element of the stack in parenthesis.
• ^: Pop the top element of the stack, and append it the program, directly after this instruction.
• S: Pop the top element of the stack and print it.

Test cases

(Hello, world!)S
Hello, world!

(!@#$%^&*())S
!@#$%^&*()

(a)(b)~SS
ab

(a)(b)!S
a

(a)(b)*S
ab

(a)aS
(a)

(b)(a)^S
(b)

(a(:^)*S):^
(a(:^)*S):^

Input

The input will be a string, either through STDIN, as an argument to a function, or however your programming language takes input.

You can assume the input will have matched parenthesis and will not attempt to run invalid instructions.

Output

The output will also be a string.

This is code-golf, so the shortest answer in bytes is wins!

Answer 1

Python 3, 243 242 238 bytes

s=input()
q=[]
P=q.pop
d=w=i=0
while s[i:]:
 c=ord(s[i]);i+=1
 if 40==c:d+=1;w=[i,w][d>1]
 elif d:x=41==c;d-=x;q+=[s[w:i-1]][d:]*x
 else:y=P();exec("q+=y,y q+='(%s)'%y, q+=P()+y, print(end=y) y s=s[:i]+y+s[i:] q+=y,P()".split()[c%20%9%7])

Try it online!

Pseudo Code:

read program from STDIN into s
initialize 
  empty stack q
  parenthesis nesting level d
  string start index w
  instruction pointer i

while the program has instructions left:
  get current instruction; increment instruction pointer

  if current instruction c is '(':
    increment parenthesis nesting level d
    update string start index if new nesting level is 1

  elif we are in a string:
    if the current command is ')':
      decrement nesting level d
      push string to stack if we reached level 0

  otherwise
    execute the code for the current command

Answer 2

JavaScript (Node.js),  237  221 bytes

Saved 8 bytes thanks to @tsh

f=([c,...s],S=p=[O=o=''])=>c?((n=Buffer(c)[0],n-40?n-41?p:--p||!S.push(o):p++)?o+=c:eval("o=''0(q=1,1)+q)0q=1,q)/1/s=[...1,...s]/01,1)0`(${1})`)/O+=1".replace(/\d/g,n=>+n?'S.pop()':'/S.push(').split`/`[n%15%11]),f(s,S)):O

Try it online!

Commented

For readability, let's assign the list of commands to an explicit variable cmd:

cmd =
  "o=''0(q=1,1)+q)0q=1,q)/1/s=[...1,...s]/01,1)0`(${1})`)/O+=1"
  .replace(/\d/g, n => +n ? 'S.pop()' : '/S.push(')
  .split`/`

This expands to:

[
  "o=''",                          // non-nested closing parenthesis
  'S.push((q=S.pop(),S.pop())+q)', // '*' (concatenate)
  'S.push(q=S.pop(),q)',           // ':' (duplicate)
  'S.pop()',                       // '!' (drop)
  's=[...S.pop(),...s]',           // '^' (append to the program)
  '',                              // not used
  'S.push(S.pop(),S.pop())',       // '~' (swap)
  'S.push(`(${S.pop()})`)',        // 'a' (enclose)
  'O+=S.pop()'                     // 'S' (print)
]

The main code now reads as:

f = (                      // f is a recursive function taking:
  [ c,                     //   c   = next character
       ...s ],             //   s[] = array of remaining characters
  S =                      //   S[] = stack
  p = [                    //   p   = counter of opened parentheses
    O =                    //   O   = output string
    o = ''                 //   o   = current string
  ]                        //
) =>                       //
  c ?                      // if c is defined:
    (                      //
      (                    //   parentheses processing:
        n = Buffer(c)[0],  //     n = ASCII code of c
        n - 40 ?           //     if c is not an opening parenthesis:
          n - 41 ?         //       if c is not a closing parenthesis:
            p              //         yield p
          :                //       else:
            --p ||         //         pre-decrement p
           !S.push(o)      //         push o to the stack if p = 0
        :                  //     else:
          p++              //       post-increment p
      )                    //   end of parentheses processing
      ?                    //   if the above is truthy (i.e. we are
                           //   currently within a string definition):
        o += c             //     append c to o
      :                    //   else:
        eval(              //     evaluate the command which is indexed
          cmd[n % 15 % 11] //     by (n mod 15) mod 11
        ),                 //
      f(s, S)              //   recursive call to f
    )                      //
  :                        // else:
    O                      //   we're done: return the final output

Answer 3

Stax, ⁸⁸ 72 bytes

ï9╓╩¢▬'D└⌡○♠↨ó•ó♀▒m5E■V\╖O|é░xÄ9ª╝╬K╝╝∩1◄3`-2*♫▓☼╤?÷°ZôyZ┘¿{ClñI▀«╛■ß«R9

Run and debug it

I thought this would be simple with a stack based language. I was wrong.

Fixed a bug which caused () to immediately halt the program.

Explanation

w # while top of stack isn't empty:
 yB # remove first char of program
 sY # store rest of program in register Y 
 sc40= # is first char a '('?
 { # if true:
  d1y # delete char, push 1 and program 
  { # take chars while the following returns true
   c.()# # is current char in "()"? 
   {]"(^)v"|tl} #if so, if (, increment the 1 otherwise decrement
   {d}? # otherwise delete the char
   c copy the 1
  }h
  sdc%^Na)Yd # remove length + 1 chars from the program, store in Y 
 }
 { # otherwise, execute stack command:
  sd] # delete copy of input
  "~s:c!d*+Sp^""y+Yd"97.:{3l+ # underload to stax translation array
  :t # translate the current char to stax
  l  # execute
 }?
 y # push y at the end(if empty, ends the program)

Answer 4

Retina, 157 bytes

.{/^S/&*>,G1`
^((\^)|[S!])(.*)¶(.*)|^:(.*(¶.*))
$#2*$4$3$5$6
^((~)|\*)(.*)¶(.*)(¶.*)
$3$5$#2*¶$4
^\((((\()|(?<-3>\))|[^()¶])*)\)(.*)
$4¶$1
^a(.*¶)(.*)
$1($2)

Try it online! Link includes test suite. Explanation:

.

Don't output the stack at the end of the program.

{

Repeat until the program has been processed (assuming no invalid instructions).

/^S/&*>,G1`

If the next instruction is S then print the top of the stack (this does not pop the stack yet).

^((\^)|[S!])(.*)¶(.*)|^:(.*(¶.*))
$#2*$4$3$5$6

If the next instruction is S or ! then discard the top of the stack, but if it is \^ then prepend it to the remainder of the program, while if it is : then duplicate the top of the stack.

^((~)|\*)(.*)¶(.*)(¶.*)
$3$5$#2*¶$4

If the next instruction is ~ then swap the two elements of the stack otherwise if it is * then join then together (this needs the elements to be swapped first, so the functions are combined here.)

^\((((\()|(?<-3>\))|[^()¶])*)\)(.*)
$4¶$1

If the next instruction is a ( then push a (presumably) balanced string until the matching ). (If there aren't any )s then the interpreter will give up while if there aren't enough )s then the interpreter will match until the last one.)

^a(.*¶)(.*)
$1($2)

If the next instruction is an a then wrap the top of the stack in ( and ).

Answer 5

Haskell, 322 bytes

Function is l [].

l(s:t:v)('~':x)=l(t:s:v)x
l(s:t)(':':x)=l(s:s:t)x
l(_:s)('!':x)=l s x
l(s:t:v)('*':x)=l((s++t):v)x
l(s:t)('a':x)=l(('(':s++")"):t)x
l(s:t)('^':x)=l t(s++x)
l(s:t)('S':x)=s++l t x
l t('(':x)=h t 0""x
h t 0a(')':x)=l(reverse a:t)x
h t n a(')':x)=h t(n-1)(')':a)x
h t n a('(':x)=h t(n+1)('(':a)x
h t n a(c:x)=h t n(c:a)x

Answer 6

Haskell, ^272… 252 bytes

([]?)
s?('(':r)|l<-1%r=(take(l-1)r:s)?drop l r
(x:s)?('^':r)=s?(x++r)
(x:s)?('S':r)=x++s?r
s?(c:r)=s!c?r
s?e=e
(x:y:s)!'~'=y:x:s
(x:s)!':'=x:x:s
(_:s)!'!'=s
(x:y:s)!'*'=(y++x):s
(x:s)!'a'=('(':x++")"):s
0%r=0
n%(c:r)=1+(n+sum[1|c=='(']-sum[1|c==')'])%r

Try it online!

The relevant function is ([]?), which takes an Underload program as a String as input and returns a String as output.

There is already an interesting Haskell answer, make sure to go upvote that as well (once it's fixed)! I decided to post my own answer because, well, I finally found a use for the Monad instance of (,) a! Yeah, I knew it couldn't last...

Answer 7

JavaScript (V8), 189 bytes

f=([C,...P],X=T=L='',Y,...S)=>C?eval(`f(P,${L*(L-=C=='('?-1:C==')')?'X+C,Y':`
^P.unshift(...X)&&Y
~Y,X
:X,X,Y
!Y
*Y+X
a'('+X+')',Y
S(T+=X,Y)
('',X,Y
)X,Y`.match(`
[${C}](.*)`)[1]},...S)`):T

Try it online!

f=(
[C,...P], // C = Current command; P = Following program
X= // X, Y = Top 2 of stack; S = Remaining stack
T= // Output
L='', // Current brackets level
Y,...S
)=>C? // Is program not finished?
// Recursive call fol following command
eval(`f(P,${
L*(L-=C=='('?-1:C==')')? // If currently we are in brackets
'X+C,Y': // We append this character to the top element of stack
// Otherwise, based on different command (1st letter each line)
// we execute different codes here
// And the the result is whatever placed on top of stack
`
^P.unshift(...X)&&Y
~Y,X
:X,X,Y
!Y
*Y+X
a'('+X+')',Y
S(T+=X,Y)
('',X,Y
)X,Y`.match(
// We use thi regex to get codes we need execute
`
[${C}](.*)`)[1]
},...S)` // Remaining stack
):T // Everything done, output goes here

Answer 8

CJam, 80 bytes

{`(;);EDero}:S{[\\]`(;);"} {"/~+~}:B{a`"[]"Eer~}:Cq"()~:!*^a":D"{}\_;B~C":Eer~];

Try it online!

Could probably be a fair bit smaller ;)

---

How it works

The interpreter is split into two parts: first, we define helper functions; then, we convert the Underload program into a CJam program and run it.

Conversion

q"()~:!*^a":D"{}\_;B~C":Eer

q                                Reads in the Underload program as a string
 "()~:!*^a"  "{}\_;B~C"  er      Replaces "(" with "{", ")" with "}", etc
           :D          :E        We take the opportunity to define these strings as D and E,
                                 since we have to "unreplace" when we print

Helper functions

We call the printing function S so we can avoid having to replace characters when S comes up in the Underload program.

{`(;);EDero}:S

{          }:S   Define a function named S
 `               Since the elements are represented as blocks, we have to turn the block into a
                 string
  (;);           On top of that, all the blocks are surrounded by 1 too many parentheses when  we
                 turn them into strings, so we remove those
      EDer       We translate backwards into Underload by "unreplacing" the special characters
          o      And then print and pop the string

We call the concatenation function B (for no particular reason).

{[\\]`(;);"} {"/~+~}:B

 [\\]                     Make an array with ONLY the top two elements of the stack
     `(;);                And turn it into a string (remembering to remove the square brackets
                          we got when we turned it into an array)
          "} {"/          The only gap between two curly brackets is between the two elements
                          that we want to merge, so we split along that gap
                ~+~       Then we merge and turn it back into a block

We call the array-enising function C (we unfortunately cannot use a as lowercase letters are reserved for language-defined functions)

{a`"[]"Eer~}:C
 a`               Array-enise our block in CJam and turn it into a string
   "[]"Eer        Replace the array characters with "{}" (luckily the extra characters
                  in E are ignored)
          ~       Convert it from a string to a block

Running the converted program (& cleanup)

It takes 1 character to run the converted program after we've made it: ~.

After this we need to clean up our functions, since they are sitting on the stack and will be printed if we don't get rid of them. We do this by collecting everything left on the stack and popping it: ];.

Answer 9

Underload, 1 byte

^

Try it online!

If we assume the input program is put on the stack as an element ((PROGRAM)), then all that is required is to run that program!

Note: In the TIO, the header and footer wrap the "Code" section in parentheses, making it not run, but instead become an element at the top of the stack. Then at the end of the footer is the ^ which runs the code.

---

This is only a joke/non-competing answer, since although interpreting languages in themselves isn't always trivial/boring, in this case it really is.

Answer 10

Jelly, 93 bytes

“Ṫ,Ṫ;@“0ịṭ“Ṗ“Ṫ;@Ṫṭ“Ṫ⁾()jṭ“ṪȮṛ”W€“~:!*aS”żẎy
Żi@þØ(Ä_/Ṣ⁼Ø.ƊƝœp;1ÇṾ;”ṭWƊƭ€ṖẎ
ṪÇß}v⁼”^$?@ƒ
WÇṛ“”

Try it online!

This feels far too long!

A full program taking an Underload program as it’s argument and printing the output to STDOUT. In principle, translates the program to a series of Jelly chains and executes them, with special handling for the ^ command.

Answer 11

Charcoal, 87 bytes

≔⪪⮌Ｓ¹θＷθ≡⊟θ~ＦＥ²⊟υ⊞υκ:⊞υ§υ±¹!≔⊟υδ*⊞υ⪫⮌Ｅ²⊟υω(⊞υ⭆⊖Ｌ⌊ΦＥθ…⮌θ⊕λ›№κ)№κ(⊟θa⊞υ⪫()⊟υ^Ｆ⪪⮌⊟υ¹⊞θκS⊟υ

Try it online! Link is to verbose version of code. Explanation:

≔⪪⮌Ｓ¹θ

Reverse the input and split it into characters so that it can be processed more easily.

Ｗθ≡⊟θ

Loop over each character in turn.

~ＦＥ²⊟υ⊞υκ

If it's a ~ then pop the top two elements from the stack and push them again, swapping them.

:⊞υ§υ±¹

If it's a : then duplicate the top element of the stack.

!≔⊟υδ

If it's a ! then discard the top element of the stack.

*⊞υ⪫⮌Ｅ²⊟υω

If it's a * then concatenate the top two elements of the stack. (Annoyingly the elements pop in the wrong order.)

(⊞υ⭆⊖Ｌ⌊ΦＥθ…⮌θ⊕λ›№κ)№κ(⊟θ

If it's a ( then find the shortest unbalanced prefix and push the characters up to the unbalanced ) to the stack. (The ) doesn't get removed but unrecognised characters get ignored anyway.)

a⊞υ⪫()⊟υ

If it's an a then wrap the top of the stack in ()s.

^Ｆ⪪⮌⊟υ¹⊞θκ

If it's a ^ then push the top of the stack to the input.

S⊟υ

If it's a S then pop and print the top of the stack.

Answer 12

JavaScript (v8), 205 bytes

F=(p,s=[],o=d="")=>eval('for(c of p)c=="(32d++?0+c:"")1)3--d&&20+c):d?20+c)1~320,0)1:32t=0,t)1!301*3(t=0,20+t))1a32`(${0})`)1^3o+=F(0,s)1S3o+=0:o;o'.replace(/\d/g,x=>["s.pop()",':c=="',"s.push(",'"?'][x]))

F=(
  p,     // source code (as string)
  s=[],  // stack
  o=     // output
  d=""   // depth of the parentheses
)=>eval(`
  for(c of p)
    c=="(32d++?0+c:"") // open parentheses
    1)3--d&&20+c)      // close parentheses
    :d?20+c)           // inside of parentheses
    1~320,0)           // swap
    1:32t=0,t)         // dup
    1!30               // drop
    1*3(t=0,20+t))     // concat
    1a32\`(\${0})\`)   // quote
    1^3o+=F(0,s)       // exec
    1S3o+=0            // print
    :o;o               // return output
  `.replace(/\d/g,x=>["s.pop()",':c=="',"s.push(",'"?'][x])
)

Answer 13

Ruby 3+, 213 bytes

$s=[]
def g(i)=i==""?0:(s=$s;i=~/^(\(((\g<1>|[^()])*)\))/?(s<<$2;g $'):('gqVas<<"(#{q})"V~a,b=q,q;s<<a;s<<bV:s<<s[-1]V!qV%a,b=q,q;s<<b+aVSprintqV'=~/#{i[0].tr'*','%'}([^V]+)/;eval($1.gsub'q','(s.pop)');g i[1..]))

Attempt This Online!

Pass Underload code into the g function.

Note that this uses the new def syntax from Ruby 3 so it won't parse on previous versions.

Does a few regex tricks, like matching paren blocks in one pass or saving a few bytes by not escaping the start anchor before it's interpolated into the instruction decoding regex. This entry encodes the Undercode instruction names and does instruction lookup in a similar way to this entry.