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
    Commented May 17, 2021 at 12:12
  • 1
    \$\begingroup\$ @Noodle9 Alright. \$\endgroup\$
    – nph
    Commented May 17, 2021 at 12:16
  • \$\begingroup\$ Can you take the program itself as an array of instructions or is parsing required? \$\endgroup\$
    – Jonah
    Commented May 17, 2021 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
    Commented May 17, 2021 at 12:48
  • \$\begingroup\$ @Jonah Parsing is required, the input is just a string. \$\endgroup\$
    – nph
    Commented May 17, 2021 at 12:54

13 Answers 13


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

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


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\$ Commented May 17, 2021 at 19:43
  • \$\begingroup\$ OK, will fix. ₁ \$\endgroup\$ Commented May 17, 2021 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
    Commented May 17, 2021 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
    Commented May 17, 2021 at 21:07
  • \$\begingroup\$ Yep, that's the issue. \$\endgroup\$ Commented May 18, 2021 at 1:30

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


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

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.


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.

{          }:S   Define a function named S
 `               Since the elements are represented as blocks, we have to turn the block into a
  (;);           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`               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: ];.


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.


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.


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]))
  p,     // source code (as string)
  s=[],  // stack
  o=     // output
  d=""   // depth of the parentheses
  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
New contributor
zptr1 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • \$\begingroup\$ Welcome to Code Golf, and nice first answer! Be sure to check out our Tips for golfing in JavaScript page for ways you can golf your program! I think you can save three bytes by using single quotes for the string in eval and then not escaping the two backticks and $. \$\endgroup\$
    – emanresu A
    Commented Jul 9 at 20:23

Ruby 3+, 213 bytes

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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