1 of 7

Write a Shift Interpreter


Shift is an esoteric functional programming language I made a couple of years ago, but published today. It is stack-based, but also has automatic currying like Haskell.


There are two datatypes in Shift:

  • Functions, which have an arbitrary positive arity (number of inputs), and which return a list of outputs. For example, a function that duplicates its only input has arity 1, and a function that swaps its two inputs has arity 2.
  • Blanks, which are all identical and have no other purpose than not being functions.

A Shift program consists of zero or more commands, each of which is a single ASCII character. There are 8 commands in total:

  • ! (apply) pops a function f and a value x from the stack, and applies f to x. If f has arity 1, the list f(x) is appended to the stack. If it has arity n > 1, a new (n-1)-ary function g is pushed to the stack. It takes inputs x1,x2,...,xn-1 and returns f(x,x1,x2,...,xn-1).
  • ? (blank) pushes a blank to the stack.
  • + (clone) pushes to the stack a unary function that duplicates its input: any value x is mapped to [x,x].
  • > (shift) pushes to the stack a unary function that takes in an n-ary function f, and returns an (n+1)-ary function g that ignores its first argument, and calls f on the remaining ones.
  • / (fork) pushes to the stack a ternary function that takes three inputs a,b,c, and returns [b] if a is a blank, and [c] otherwise.
  • $ (call) pushes to the stack a binary function that pops a function f and a value x, and applies f to x exactly as ! does.
  • . (chain) pushes to the stack a binary function that pops two functions f and g, and returns their composition: a function h that has the same arity as f, and which takes its inputs normally, applies f to them, and then fully applies g to the result (calls it as many times as its arity dictates).
  • @ (say) pushes a unary function that simply returns its input, and prints 0 if it was a blank, and 1 if it was a function.

Note that all commands except ! simply push a value to the stack, there is no way to perform input, and the only way to output anything is to use @. A program is interpreted by evaluating the commands one by one, printing 0s or 1s whenever "say" is called, and exiting. Any behavior not described here (applying a blank, applying a stack of length 0 or 1, calling "chain" on a blank etc.) is undefined: the interpreter may crash, silently fail, ask for input, or whatever.

The Task

Your task is to write an interpreter for Shift. It should take from STDIN, command line, or function argument a Shift program to be interpreted, and print to STDOUT or return the resulting (possibly infinite) output of 0s and 1s. If you write a function, you must be able to access the infinite-length outputs in some way (generator in Python, lazy list in Haskell, etc).

The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

This Shift program prints 01:


Starting from the left: push a blank, push say, then apply the say to the blank. This outputs 0. Then, push say twice, and apply the second say to the first. This outputs 1.

This program loops forever, producing no output:


Push clone and call, then apply chain to them (we need two !s since chain is a binary function). Now the stack contains a function that takes one argument, duplicates it, and calls the first copy on the second. With +!!, we duplicate this function and call it on itself.

This program prints the infinite sequence 01011011101111..., where the number of 1s always increases by one:


I'm not going to explain it, mainly because I wrote it many years ago and forgot how it works. See the repository for a partial explanation.