# 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 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 <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, 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 `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). 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 `1`s 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.