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
fand a value
xfrom the stack, and applies
fhas arity 1, the list
f(x)is added to the front of the stack. If it has arity
n > 1, a new
gis pushed to the stack. It takes inputs
?(blank) pushes a blank to the stack.
+(clone) pushes to the stack a unary function that duplicates its input: any value
xis mapped to
>(shift) pushes to the stack a unary function that takes in an
f, and returns an
gthat ignores its first argument
fon the remaining ones, and tacks
xin front of the result. For example,
shift(clone)is a binary function that takes inputs
/(fork) pushes to the stack a ternary function that takes three inputs
a,b,c, and returns
ais a blank, and
$(call) pushes to the stack a binary function that pops a function
fand a value
x, and applies
.(chain) pushes to the stack a binary function that pops two functions
g, and returns their composition: a function
hthat has the same arity as
f, and which takes its inputs normally, applies
fto them, and then fully applies
gto the result (calls it as many times as its arity dictates), with unused items from the output of
fremaining in the result of
h. For example, suppose that
fis a binary function that clones its second argument, and
gis 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
fis first applied to
gis applied to the first two elements of that since its arity is 2, producing
[a(b),b], and the stack will finally be
@(say) pushes a unary function that simply returns its input, and prints
0if it was a blank, and
1if 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
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.
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
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
The lowest byte count wins, and standard loopholes are disallowed.
This Shift program prints
Starting from the left: push a blank, push say, then apply the say to the blank.
Then, push say twice, and apply the second say to the first.
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.
+!!, we duplicate this function and call it on itself.
This program prints
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
Apply it to say and blank, then apply say to the two elements remaining on the stack.
This program prints
!!! that you append to it, it prints an additional
Push a blank and say.
Then, compose a ternary function that takes
f,g,x as inputs and returns
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.
f(x1, x2, ..., xn)and
g(y1, y2, ..., ym). Calling
.pops both of them and pushes a function
h(z1, z2, ..., zn). Now you can eat up all those arguments by gradually currying it with
nsuch applications, the remaining function had only one argument, and at that point it computes
f(z1, z2, ..., zn)(i.e.
fapplied to all the arguments you curried in), which pushes some new values, and then immediately consumes
mvalues from the stack and calls
gon them. \$\endgroup\$
.works exactly as Martin described, except that if
freturns a list of less than
mvalues, the result is undefined (the composition has arity
n, so it cannot eat more arguments from the stack). Essentially, the output of
fis used as a temporary stack, on which
gis pushed and applied
!, and the result of that is added to the main stack. \$\endgroup\$