4 of 7 Fixed issue with chain.

Write a Shift Interpreter

EDIT: As some of you suspected, there was a bug in the official interpreter: the order of composition in . was reversed. I had two versions of the interpreter, and used the wrong one here. The examples were also written for this incorrect version. I have fixed the interpreter in the repository, and the examples below. The description of > was also a bit ambiguous, so I've fixed that. Also, apologies for this taking so long, I was caught up in some real life stuff.

EDIT2: My interpreter had a bug in the implementation of . which was reflected in the examples (they relied on undefined behavior). The issue is now fixed.


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 added to the front of 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 x, calls f on the remaining ones, and tacks x in front of the result. For example, shift(clone) is a binary function that takes inputs a,b and returns [a,b,b].
  • / (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). For example, suppose that f is a binary function that clones its second argument, and g is call. If the stack contains [f,g,a,b,c] and we do .!!, then it contains [chain(f,g),a,b,c]; if we do !! next, then f is first applied to a,b, producing [a,b,b], then g is applied to the first two elements of that since its arity is 2, producing [a(b),b], and the stack will finally be [a(b),b,c].
  • @ (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). Alternatively, you can take another input, a number n, and return at least n characters of the output if it is longer than n.

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 call and clone, 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 0010:


Push a blank and say. Then, compose a binary function that copies its second argument b, then copies the first a and composes it with itself, then applies the composition to the copy of b, returning [a(a(b)),b]. Apply it to say and blank, then apply say to the two elements remaining on the stack.

This program prints 0. For each !!! that you append to it, it prints an additional 0.


Push a blank and say. Then, compose a ternary function that takes f,g,x as inputs and returns [f,f,g,g(x)]. Clone that function, and apply it to itself, say, and the blank. This application does not change the stack, so we can apply the function again as many times as we want.

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


The repository contains an annotated version.