22
\$\begingroup\$

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!

\$\endgroup\$
6
  • 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

11 Answers 11

9
\$\begingroup\$

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
\$\endgroup\$
9
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\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
7
\$\begingroup\$

Stax, 88 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)
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
7
  • \$\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
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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: ];.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 87 bytes

≔⪪⮌S¹θWθ≡⊟θ~FE²⊟υ⊞υκ:⊞υ§υ±¹!≔⊟υδ*⊞υ⪫⮌E²⊟υω(⊞υ⭆⊖L⌊ΦEθ…⮌θ⊕λ›№κ)№κ(⊟θa⊞υ⪫()⊟υ^F⪪⮌⊟υ¹⊞θκS⊟υ

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

≔⪪⮌S¹θ

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

Wθ≡⊟θ

Loop over each character in turn.

~FE²⊟υ⊞υκ

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.

*⊞υ⪫⮌E²⊟υω

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

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

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.

^F⪪⮌⊟υ¹⊞θκ

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

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.