Interpret Gelatin

Question

Gelatin is a worse version of Jelly. It is a tacit programming language that always takes a single integer argument and that has 7 (or maybe 16) commands. You are to take in a Gelatin program and its argument and output the result.

Gelatin

Gelatin programs will always match the following regex:

^[+_DSa\d~]*$

i.e. they will only contain +_DSa0123456789~ characters. The commands in Gelatin are:

• Digits return their value (0 is \$0\$, 1 is \$1\$ etc.) Digits are stand alone, so 10 represents \$1\$ and \$0\$, not \$10\$
• a returns the argument passed to the Gelatin program
• D takes a left argument and returns it minus one (decremented)
• S takes a left argument and returns its square
• + takes a left and a right argument and returns their sum
• _ takes a left and a right argument and returns their difference (subtract the right from the left)
• ~ is a special command. It is always preceded by either + or _ and it indicates that the preceding command uses the same argument for both the left and the right.

Each command - aside from ~ - in Gelatin has a fixed arity, which is the number of arguments it takes. Digits and a have an arity of \$0\$ (termed nilads), D and S have an arity of \$1\$ (termed monads, no relation) and + and _ have an arity of \$2\$ (termed dyads)

If + or _ is followed by a ~, however, they become monads. This affects how the program is parsed.

Tacit languages try to avoid referring to their arguments as much as possible. Instead, they compose the functions in their code so that, when run, the correct output is produced. How the functions are composed depends on their arity.

Each program has a "flow-through" value, v and an argument ω. v is initially equal to ω. We match the start of the program against one of the following arity patterns - earliest first, update v and remove the matched pattern from the start. This continues until the program is empty:

• 2, 1: This is a dyad d, followed by a monad M. First, we apply the monad to ω, yielding M(ω). We then update v to be equal to d(v, M(ω)).
• 2, 0: This is a dyad d, followed by a nilad N. We simply update v to be d(v, N)
• 0, 2: The reverse of the previous pattern, v becomes d(N, v)
• 2: The first arity is a dyad d, and it's not followed by either a monad or a nilad as it would've been matches by the first 2. Therefore, we set v to be d(v, ω)
• 1: The first arity is a monad M. We simply set v to be M(v)

For example, consider the program +S+~_2_ with an argument 5. The arities of this are [2, 1, 1, 2, 0, 2] (note that +~ is one arity, 1). We start with v = ω = 5:

• The first 2 arities match pattern 2, 1 (+S), so we calculate S(ω) = S(5) = 25, then calculate v = v + S(ω) = 5 + 25 = 30
• The next arity matches pattern 1 (+~). +~ means we add the argument to itself, so we double it. Therefore, we apply the monad to v, updating it to v = v + v = 30 + 30 = 60
• The next arity pattern is 2, 0 (_2), which just subtracts 2, updating v to v = v - 2 = 60 - 2 = 58
• Finally, the last arity pattern is 2 (_), meaning we update v to be v = v - ω = 58 - 5 = 53.
• There are now no more arity patterns to match, so we end the program

At the end of the program, Gelatin outputs the value of v and terminates.

In a more general sense, +S+~_2_ is a function that, with an argument \$\omega\$, calculates \$2(\omega + \omega^2) - 2 - \omega = 2\omega^2 + \omega - 2\$.

---

You are to take a string representing a Gelatin program, using the characters specified above, and a positive integer \$\omega\$ and output the result of running the Gelatin program with an argument of \$\omega\$

You may assume that the arities of the program will always fit one of the 5 patterns (so nothing like S1S (1, 0, 1) will appear), and that the flow-through value will never exceed your language's integer bounds. The output may be negative.

This is code-golf so the shortest code in bytes wins

Test cases

Program         ω              out
+S              7              56            
_aSS+           20             20            
++DDDS+1_       15             1750          
_S              13             -156          
D0+             12             11            
_+~SSS++__S++a  6              1679598       
_++a            17             34            
a+_6D           20             33            
D+_+_aD         17             15  
                5              5
DD              8              6              
+_aa+S+SS+_+    4              6404           
+9+S_           19             370            
_DDD+_a+_3_4D_  13             -9             
SS_SD+          15             50414          
+~D_~_          7              -7             
D_a+S           10             99             
_S+aD+4         1              4              
+_a+            3              6   
_aD+60+         13             5   
+1++~           3              10

This is a program that randomly generates \$n\$ Gelatin programs, along with random inputs and the intended outputs

Answer 1

Jelly, 15 bytes

⁾D’y“S²a⁸~`”yKv

Try it online!

⁾D’y               Substitute D for Jelly's decrement builtin.
                   (This is done alone because ’ is a string terminator.)
    “      ”y      Substitute
     S²            S for square,
       a⁸          a for left argument,
         ~`        and ~ for reuse argument.
                   (+ and _ are already plus and minus.)
             K     Join the program on spaces to split up multi-digit numbers,
              v    and evaluate it as Jelly with the right argument as its sole argument.

Answer 2

JavaScript (ES6),  306 ... 227  226 bytes

Expects (program)(ω).

s=>g=(v,w=v,n=0,h=_=>(O={a:w,'+':"x+y",_:"x-y",S:"x*x",D:"x-1",'+~':"x*2",'_~':"0"}[c=(s+'a').match(/.~?/g)[n++]]||+c)[2]>O?2:O>g)=>(I=h(i=h(E=(o,x,y)=>eval(o)),o=O),o)?g(i?E(o,v,I?I-2?E(O,w):w:O):I?E(O,o,v):v,w,n-=i==I|i&1):v

Try it online!

Commented

Header and helper function h

s =>                 // outer function taking the program string s
g = (                // g = inner recursive function taking:
  v,                 //   v = current output value
  w = v,             //   w = initial value of v (aka ω)
  n = 0,             //   n = pointer in the command stream
  h = _ => (         //   h is a helper function which turns the next
                     //   command into a JS code snippet or an integer,
                     //   along with the arity of the command:
    O = {            //     1) command:
      a   : w,       //       'a' : use w
      '+' : "x+y",   //       '+' : add y to x
      _   : "x-y",   //       '_' : subtract y from x
      S   : "x*x",   //       'S' : square x
      D   : "x-1",   //       'D' : decrement x
      '+~': "x*2",   //       '+~': double x
      '_~': "0"      //       '_~': yield 0
    }[               //
      c = (s + 'a')  //       append an explicit 'a' command at the end
      .match(/.~?/g) //       split the commands (either "x" or "x~")
      [n++]          //       load the next command into c
    ]                //
    || +c            //       if the above is undefined, use +c (it's a digit)
  )                  //     2) arity of the command:
  [2] > O ? 2        //       dyad if the 3rd character is 'y'
          : O > g    //       monad if it's a code snippet, or nilad otherwise
) =>                 //

Body of g

( I =                // (O, I) = (2nd command, 2nd arity)
  h( i =             // (o, i) = (1st command, 1st arity)
    h( E =           // E is a helper function
      (o, x, y) =>   //   which takes o, x, y
        eval(o)      //   and evaluates o in this local context
    ),               //
    o = O            //
  ),                 //
  o                  // we eventually test o
) ?                  // if o is defined:
  g(                 //   do a recursive call to g:
    i ?              //     if the 1st command is not a nilad:
      E(             //       v = result of a call to E with:
        o,           //         the 1st command
        v,           //         x = v
        I ?          //         if the 2nd command is not a nilad:
          I - 2 ?    //           if the 2nd command is a monad:
            E(O, w)  //             y = result of the 2nd command as a monad
          :          //           else (the 2nd command is a dyad):
            w        //             y = w
        :            //         else:
          O          //           y = O
      )              //       end of call
    :                //     else (the 1st command is a nilad):
      I ?            //       if the 2nd command is not a nilad:
        E(O, o, v)   //         v = result of the 2nd command as a dyad
      :              //       else:
        v,           //         v is left unchanged
    w,               //     pass w unchanged
    n -=             //     decrement n if only one command was 'consumed':
      i == I | i & 1 //       i.e. if i = I or i is odd
  )                  //   end of recursive call
:                    // else:
  v                  //   we're done: return the final output value

Answer 3

Charcoal, 147 bytes

Ｎθ≔θζＦ⁺⪫⪪⪫⪪Ｓ+~¦d¦_~¦z¦i«≡№DSdiz++__鲫Ｆ⁼²Ｌυ⊞υθＦ²⊞υ⎇⊖Ｌυζι»¹«≔⎇υθζε≡ιD≦⊖εS≦×εεd≦⊗εz≦⁻εε⎚¿υ⊞υε≔εζ»⊞υ⎇⁼aιθＩι¿‹²Ｌυ«≔⎇⁼+§υ¹⁺§υ⁰§υ²⁻§υ⁰§υ²ζ≔…⟦ζι⟧⁻Ｌυ³υ»»Ｉζ

Try it online! Link is to verbose version of code. Takes the argument as the first input and the script as the second input. Explanation:

Ｎθ≔θζ

Input the argument and copy it to the flow-though value.

Ｆ⁺⪫⪪⪫⪪Ｓ+~¦d¦_~¦z¦i«

Transform the script by replacing the +~ and _~ operators with single-byte operators and appending the identity operator (in case the script ends with a dyadic operator). Loop over each operator.

≡№DSdiz++__ι

See how many arguments this operator expects.

²«Ｆ⁼²Ｌυ⊞υθＦ²⊞υ⎇⊖Ｌυζι»

If this is a dyad, then if there is already a dyad on the stack then push the argument as its RHS. Push the flow-through value and the dyad, ensuring that the dyad is between its operands. Note that the flow-through value is incorrect if there is already a dyad on the stack but that will be fixed up later.

¹«≔⎇υθζε≡ιD≦⊖εS≦×εεd≦⊗εz≦⁻εε⎚¿υ⊞υε≔εζ»

If this is a monad, then get either the flow-through value or the argument (depending on whether there is a dyad on the stack), apply the monad to it, then save it to the flow-through value or the stack (again depending on whether there is a dyad on the stack).

⊞υ⎇⁼aιθＩι

Otherwise push either the argument (if this is an a operator) or the numeric value of the digit to the stack, assuming that the next operator is a dyad.

¿‹²Ｌυ«

If we now have a dyad with both its arguments on the stack, then:

≔⎇⁼+§υ¹⁺§υ⁰§υ²⁻§υ⁰§υ²ζ

Update the flow-through value with the result of the dyad.

≔…⟦ζι⟧⁻Ｌυ³υ

If there were in fact two dyads on the stack, then recalculate the stack with the new flow-through value and the current dyad, otherwise clear the stack.

»»Ｉζ

Once the script has been processed output the final flow-through value.

Answer 4

Pip, 129 bytes

YaLRqR"+~_~_"<>2;^"TZ-"`\W\w?|[A-Z]|..`Y V$0R['^.XU`([A-Z]|^.)$`][`&y``&a`]R(^"DSTZ").CXX'Y.[B.vB.'*.B"2*".B0]R`\W$`_.yR`^\W`y._y

Try it online!

How?

We're basically going to use a translate-and-eval approach. Unlike Jelly (cough), Pip's execution model is rather different from Gelatin's, so the translation takes some work. We are fortunate in some ways: 0-9 and + can be used as they are, and so can a if we take the input number as a command-line argument.

Ya

Copy the input number into y, which will be our flow-through value.

qR"+~_~_"<>2;^"TZ-"

Read the Gelatin program from stdin and make some substitutions: +~ -> T (for Twice, since x+x = 2*x), _~ -> Z (for Zero, since x-x = 0), and _ -> - (so we can eval it later). After these substitutions, we have two dyads (+ and -), four monads (D, S, T, and Z), and eleven nilads (0 through 9, plus a). Note that all monads are capital letters. Note also that both dyads are symbols, whereas all monads and nilads are alphanumeric.

LR  ...  `\W\w?|[A-Z]|..`

Parse the arity patterns with regex and loop over all matches. The first branch \W\w? matches a dyad followed by a monad, nilad, or nothing; the second branch [A-Z] matches a single monad; and the third branch .. matches two characters, which in practice is the only remaining case, a nilad followed by a dyad.

$0R['^.XU`([A-Z]|^.)$`][`&y``&a`]

Starting from the arity pattern stored in the match variable $0, we make some more replacements. This stage adds the right argument for monads and for solitary dyads: A monad at the beginning of the pattern must be pattern 1; its argument should be y, the flow-through value. After that replacement, any other monad (pattern 2,1) or any other single character (pattern 2) should have a right argument of a, the input number.

...  R(^"DSTZ").CXX'Y.[B.vB.'*.B"2*".B0]

Next, we replace monads with the appropriate Pip expressions: Dx (here x represents the right argument, either y or v) becomes Yx-1; Sx becomes Yx*x; Tx becomes Y2*x; and Zx becomes Y0. (The Y enforces correct precedence of operations in the 2,1 pattern.)

...  R`\W$`_.yR`^\W`y._

Finally, we fill in the missing argument of each dyad. An operator at the end of the pattern is a dyad with a left argument (pattern 0,2), so its right argument should be y, the flow-through value. An operator at the beginning of the pattern is a dyad with a right argument (pattern 2,0 or 2,1 or 2), so its left argument should be `y.

Y V  ...

Evaluate the resulting expression as Pip code, and store the result back into y.

y

After the loop, output the final value of y.

Answer 5

Bash PATH=".:$PATH", 233 + 1 = 234 bytes

Filename is f and it must be chmod u+xed. Self recursion, now $1 is a and $3 is v.

L()(f "${p:${2-1}}" $a $[$1])
a=$2 v=${3-$a}
p=${1//_/-}
p=${p//+\~/T}
p=${p//-\~/Z}
((S=v*v,D=v-1,T=2*v))
case $p in '')echo $v;;[+-][!+-]*)((S=a*a,D=a-1,T=2*a))
L v${p::2} 2;;[+-]*)L v${p::1}a;;[D-Z]*)L ${p::1};;*)L ${p::2}v 2
esac

Try it online!

---

Bash, 245 bytes

Full program, expect $1 is program and $2 is program argument:

L(){
v=$[$1]
p=${p:${2-1}}
}
a=${v=$2}
p=${1//_/-}
p=${p//+\~/T}
p=${p//-\~/Z}
while [ $p ];do((S=v*v,D=v-1,T=2*v))
case $p in [+-][!+-]*)((S=a*a,D=a-1,T=2*a))
L v${p::2} 2;;[+-]*)L v${p::1}a;;[D-Z]*)L ${p::1};;*)L ${p::2}v 2
esac
done
echo "$v"

Try it online!

Fixed version

Ungolfed

# Define lexer
# $1 is expression for new v
# $2 is erased characters from program (default: 1)
L(){
   v=$[$1]
   p=${p:${2-1}}
}

# Define program argument and current value
a=${v=$2}

# Program, but replace underscore with hyphen
# Also replace two letter monad into one letter
p=${1//_/-}
p=${p//+\~/T}
p=${p//-\~/Z}

# Loop until program gets empty
while [ $p ]; do
   ((S=v*v,D=v-1,T=2*v,Z=0)) # Precalculate monadic value for 1 rule

   case $p in
   [+-][!+-]*) # 2,1 or 2,0
      ((S=a*a,D=a-1)) # Calculate monadic values
      L v${p::2} 2 # expands to v+1, v+D, v-(v-v), etc.
   ;;[+-]*) # 2
      L v${p::1}a # expands to v+a or v-a
   ;;[SDTZ]*) # 1
      L ${p::1}
   ;;*) # 0,2
      L ${p::2}v 2 # expands to 1+v
   esac
done

# finally
echo "$v"

Answer 6

APL (Dyalog Unicode), 193 bytes (SBCS)

B M N←'(?<!⍨)([+_])' '(D|S|⍨[+_])' '[0-9⍵]'
_←-⍨
S←×⍨
D←¯1∘+
{(⍎'{','⍵}',⍨'.'⎕R' \0 '⌽(B,M)(B,N)(∊'('N')'B)(∊B'(?!'N'|'M')')⎕R')⊢\1)⍵\2((' ')⊢\0(' ')⊢⍨\2\1(' ')⊢\0⍵('⊢'a' '(.)~'⎕R'⍵' '⍨\1'⊢⍺)⍵}

Try it online!

Takes the program on the left and the argument on the right. I figured this'd be easy with APL's trains and regex, but apparently not ⍨.

⍝ Regexes (regices?) for dyads (B), monads (M), and nilads (N)
B M N←'(?<!⍨)([+_])' '(D|S|⍨[+_])' '[0-9⍵]'
_←-⍨ ⍝ The _ dyad (flipped because APL is RTL)
S←×⍨ ⍝ The S monad (multiply with itself)
D←¯1∘+ ⍝ The D monad (add -1 to decrement)

The actual function:

{(⍎'{','⍵}',⍨'.'⎕R' \0 '⌽(B,M)(B,N)(∊'('N')'B)(∊B'(?!'N'|'M')')⎕R')⊢\1)⍵\2((' ')⊢\0(' ')⊢⍨\2\1(' ')⊢\0⍵('⊢'a' '(.)~'⎕R'⍵' '⍨\1'⊢⍺)⍵}

First 'a' '(.)~'⎕R'⍵' '⍨\1'⊢⍺ replaces a with ⍵ and +~ and _~ with ⍨+ and ⍨_. This is just to make life simpler later. The next part is

(B,M)(B,N)(∊'('N')'B)(∊B'(?!'N'|'M')')⎕R')⊢\1)⍵\2((' ')⊢\0(' ')⊢⍨\2\1(' ')⊢\0⍵('

This may look like a mess, but it's actually pretty simple:

• The pattern BM (dyad, monad) becomes ((M⍵)B⊢), but reversed.
• The pattern BN (dyad, nilad) becomes (NB⊢), but reversed.
• The pattern NB (nilad, dyad) becomes (NB⍨⊢), but reversed.
• The pattern B (dyad not followed by a nilad or monad) becomes (⍵B⊢), but reversed.
• Monads not preceded by dyads are left as is.

This is pretty much an exact translation of the rules in the question. After this, ⌽ reverses everything because unlike Jelly, APL goes from right to left (this is also why _ takes its arguments reversed). Then '.'⎕R' \0 ' puts a space on each side of each character so that APL doesn't throw up the result thinking SD is a single token. Then the result r is turned into {r⍵} and evaluated to obtain a dfn. This function is applied to the outer function's right argument, ⍵.

Answer 7

TypeScript's type system, 858 763 673 bytes

//@ts-ignore
type U<n,a=[]>=a extends{length:n}?a:U<n,[...a,1]>;type I<o,w>=U<o extends'a'?w:o>;type J<o,v,d=v,s=[]>=v extends[1,...infer v]?o extends'D'?v:J<o,v,d,[...s,...d]>:s;type K<o,a,b>=[o,a]extends['_',[...b,...infer d]]?d:[...a,...b];type F<z,w,v=U<w>,M='D'|'S'>=z extends`${infer c}${infer r}`?c extends M?F<r,w,J<c,v>>:z extends`${infer n extends'a'|number}${infer d}${infer r}`?F<r,w,K<d,I<n,w>,v>>:r extends`~${infer r}`?F<r,w,K<c,v,v>>:r extends`${infer m extends M}${infer r}`?F<r,w,K<c,v,J<m,U<w>>>>:r extends`${infer n extends'a'|number}${infer r}`?F<r,w,K<c,v,I<n,w>>>:r extends`${infer z}~${infer r}`?F<r,w,K<c,v,K<z,v,v>>>:F<r,w,K<c,v,U<w>>>:v["length"]

Try it at the TS playground

This is a recursive generic type F that takes the program as a string-type c and the input as a number-type w, and yields the result number-type.

It's one in the morning. This is my longest TypeScript-types submission yet. It only supports numbers between 0 and 999 because of a limitation of how numbers work in TS types. Took forever to debug. My suffering ;_;

Explanation

/* This line tells the compiler to ignore any
     pesky warnings: */
// @ts-ignore

/* U takes a number n and returns an array of that
     many ones.
   This is used for doing arithmetic, we use this
     list as a unary number and at the end return
     its length.
   This is also why we can only use numbers between 0
     and 999; the recursion limit is 999 iterations,
     and a list can't have negative length.
   Until a is of length n, append 1 and recurse,
     starting with empty a. */
type U<n, a = []> = a extends { length: n } ? a : U<n, [...a, 1]>;

/* I converts a parsed nilad o to a unary number.
   o is either a number or 'a'. If 'a', we take
     w, the input to the program. Otherwise, take
     o.
   That is then passed to U and returned. */
type I<o, w> = U<o extends "a" ? w : o>;

/* J evaluates a parsed monad o 'D' or 'S' on value v.
   Handling both in one type is nice because they
     have a tiny bit of shared code: in order to
     calculate the square, we add n to the running
     total 's' n times, but that involves decrementing
     n each time, so we decrement first and then check
     if the monad was 'D'. If it was, return the
     decremented result, otherwise continue with the
     squaring logic. */
type J<o, v, d = v, s = []> = v extends [1, ...infer v]
  ? o extends "D"
    ? v
    : J<o, v, d, [...s, ...d]>
  : s;

/* K evaluates a parsed dyad o '+' or '_' on
     values a and b.
   Remember a and b are unary numbers, so to add
     them you concatenate, and to subtract we
     pattern-match a against (b + infer d) to get
     the difference d. */
type K<o, a, b> = [o, a] extends ["_", [...b, ...infer d]] ? d : [...a, ...b];

// And now for the main act...

/* type parameters key:
     z = remaining code
     w = input
     v = value, starts as w
     M = alias for "match either 'D' or 'S' (the
       monads)"
     c = first character, r = the rest

   F acts in a recursive "loop" by parsing an arity
     pattern, modifying v as needed, and removing the
     parsed bit from z. This loop continues until z is
     empty, at which point v is returned. */

type F<z, w, v = U<w>, M = "D" | "S"> = z extends `${infer c}${infer r}`
  ? c extends M           // if c is a monad:
    ? F<r, w, J<c, v>>    //   set v to J<c, v>
    : z extends `${infer n extends "a" | number}${infer d}${infer r}`
                          // if c is a nilad, inferring the
                          //   next character as the dyad d:
    ? F<r, w, K<d, I<n, w>, v>>
                          //   d(c, v)
    : r extends `~${infer r}`
                          // if the next character is ~:
    ? F<r, w, K<c, v, v>> //   c(v, v)
    : r extends `${infer m extends M}${infer r}`
                          // if the next character is a monad m:
    ? F<r, w, K<c, v, J<m, U<w>>>>
                          //   c(v, m(w))
    : r extends `${infer n extends "a" | number}${infer r}`
                          // if the next character is a nilad n:
    ? F<r, w, K<c, v, I<n, w>>>
                          //   c(v, n)
    : r extends `${infer d}~${infer r}`
                          // if the next character is a dyad d
                          //   followed by ~:
    ? F<r, w, K<c, v, K<d, v, v>>>
                          //   c(v, d(v, v))
    : F<r, w, K<c, v, U<w>>>
                          // otherwise: c(v, w)
  : v["length"]; // final result, converted back to decimal