_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.
# 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), with unused items from the output of `f` remaining in the result of `h`. 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.