_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. # Introduction [Shift](https://github.com/iatorm/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. # Specification 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 <code>x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n-1</sub></code> and returns <code>f(x,x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n-1</sub>)</code>. - `?` (_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 `0`s or `1`s 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 `0`s and `1`s. 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 `1`s always increases by one: @?/!@>!.!!??/!!>!.!!+.!!.+>!.!!$$.!!$.!!$.!!+.!!$>!>!.!!$>!>!.!!+>!.!!$>!>!>!.!!+>!>!.!!///!!>!>!>!.!!+!!!!! The repository contains an annotated version.