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!









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.


The output will also be a string.

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

  • 4
    \$\begingroup\$ Suggest not adding error handling to an already complex code-golf challenge. Either assume input is always valid or make the whole challenge just checking if the input is valid or not. \$\endgroup\$ – Noodle9 May 17 at 12:12
  • 1
    \$\begingroup\$ @Noodle9 Alright. \$\endgroup\$ – nph May 17 at 12:16
  • \$\begingroup\$ Can you take the program itself as an array of instructions or is parsing required? \$\endgroup\$ – Jonah May 17 at 12:39
  • 2
    \$\begingroup\$ how are brackets matched? Do we match until the next closing bracket followed by a non-closing-bracket character? \$\endgroup\$ – Razetime May 17 at 12:48
  • \$\begingroup\$ @Jonah Parsing is required, the input is just a string. \$\endgroup\$ – nph May 17 at 12:54

Python 3, 243 242 238 bytes

while s[i:]:
 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
  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

    execute the code for the current command

JavaScript (Node.js),  237  221 bytes

Saved 8 bytes thanks to @tsh


Try it online!


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

cmd =
  .replace(/\d/g, n => +n ? 'S.pop()' : '/S.push(')

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
  • \$\begingroup\$ S.push((r=q=S.pop(),q=S.pop(),r),q): wont S.push(q=S.pop(),q=S.pop()) work? Or is q used later? \$\endgroup\$ – tsh May 18 at 7:46
  • \$\begingroup\$ @tsh That does work, thank you. I believe the convoluted expression was a result of a previous iteration. \$\endgroup\$ – Arnauld May 18 at 7:59
  • \$\begingroup\$ [...1,...s] could be 1+s.join``; and you may still use 'q=S.pop()', and ')/S.push('. \$\endgroup\$ – tsh May 18 at 8:11
  • \$\begingroup\$ S.push((q=S.pop(),S.pop())+q) could be S.push((q=S.pop(),q=S.pop()+q)) \$\endgroup\$ – tsh May 18 at 8:18

Stax, 88 72 bytes


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.


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
  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)

Haskell, 322 bytes

Function is l [].

l(_:s)('!':x)=l s 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
  • \$\begingroup\$ You don't need the u=--just clarify that the relevant function is l[]. (On TIO, you can use -cpp and put u=\ in the header.) \$\endgroup\$ – Unrelated String May 17 at 19:43
  • \$\begingroup\$ OK, will fix. ₁ \$\endgroup\$ – NoLongerBreathedIn May 17 at 20:55
  • 1
    \$\begingroup\$ Actually, you should still include l[] at the top of your code (and add 4 to your byte count), but you do not need to assign it with u=. See this TIO link for an example. Also, from this TIO link it looks like your code fails to compile. [TBC] \$\endgroup\$ – Delfad0r May 17 at 21:06
  • 1
    \$\begingroup\$ I think the problem is the line l(s:t)('^':x)=l(l t s)x, since l t s is a String and not a String, as the compiler expects. \$\endgroup\$ – Delfad0r May 17 at 21:07
  • \$\begingroup\$ Yep, that's the issue. \$\endgroup\$ – NoLongerBreathedIn May 18 at 1:30

Retina, 157 bytes


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).


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


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.


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.)


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.)


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


JavaScript (V8), 189 bytes


Try it online!

[C,...P], // C = Current command; P = Following program
X= // X, Y = Top 2 of stack; S = Remaining stack
T= // Output
L='', // Current brackets level
)=>C? // Is program not finished?
// Recursive call fol following command
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
// We use thi regex to get codes we need execute
},...S)` // Remaining stack
):T // Everything done, output goes here

Haskell, 272 252 bytes

s?('(':r)|l<-1%r=(take(l-1)r:s)?drop l 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...


Jelly, 93 bytes


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.


Charcoal, 87 bytes


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.)


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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.