10
1
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 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 functionf
and a valuex
from the stack, and appliesf
tox
. Iff
has arity 1, the listf(x)
is added to the front of the stack. If it has arityn > 1
, a new(n-1)
-ary functiong
is pushed to the stack. It takes inputsx1,x2,...,xn-1
and returnsf(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 valuex
is mapped to[x,x]
.>
(shift) pushes to the stack a unary function that takes in ann
-ary functionf
, and returns an(n+1)
-ary functiong
that ignores its first argumentx
, callsf
on the remaining ones, and tacksx
in front of the result. For example,shift(clone)
is a binary function that takes inputsa,b
and returns[a,b,b]
./
(fork) pushes to the stack a ternary function that takes three inputsa,b,c
, and returns[b]
ifa
is a blank, and[c]
otherwise.$
(call) pushes to the stack a binary function that pops a functionf
and a valuex
, and appliesf
tox
exactly as!
does..
(chain) pushes to the stack a binary function that pops two functionsf
andg
, and returns their composition: a functionh
that has the same arity asf
, and which takes its inputs normally, appliesf
to them, and then fully appliesg
to the result (calls it as many times as its arity dictates), with unused items from the output off
remaining in the result ofh
. For example, suppose thatf
is a binary function that clones its second argument, andg
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, thenf
is first applied toa,b
, producing[a,b,b]
, theng
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 prints0
if it was a blank, and1
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.
I'm a little confused here. When you write "takes in" like in the shift command, do you mean pops or do you mean applied by the apply command? – tecywiz121 – 2015-04-17T17:58:38.937
1Also, I'm really not sure from your spec how chain is supposed to work. Could you clarify it with an example please? – tecywiz121 – 2015-04-17T19:05:32.620
@tecywiz121 This is how I understand it: say you've got two functions on the top of the stack,
f(x1, x2, ..., xn)
andg(y1, y2, ..., ym)
. Calling.
pops both of them and pushes a functionh(z1, z2, ..., zn)
. Now you can eat up all those arguments by gradually currying it with!
. Aftern
such applications, the remaining function had only one argument, and at that point it computesf(z1, z2, ..., zn)
(i.e.f
applied to all the arguments you curried in), which pushes some new values, and then immediately consumesm
values from the stack and callsg
on them. – Martin Ender – 2015-04-18T14:47:43.023@MartinBüttner If Zgarb thinks it's in line with the rules you could use a second input parameter defining the maximal size of the output. This would also be a solution for the lazy evaluation issue. – randomra – 2015-04-18T18:30:18.587
@tecywiz121
.
works exactly as Martin described, except that iff
returns a list of less thanm
values, the result is undefined (the composition has arityn
, so it cannot eat more arguments from the stack). Essentially, the output off
is used as a temporary stack, on whichg
is pushed and appliedm
times using!
, and the result of that is added to the main stack. – Zgarb – 2015-04-18T20:58:29.903@randomra That's a good idea, I'll allow that. Also, apologizes for the delay, I've been unexpectedly busy; the extra examples will still have to wait... – Zgarb – 2015-04-18T20:59:52.673
I ran the third example program on my potential submission and got a "stack empty" error on the fourth-last
!
. Tried to run the reference implementation for comparison, but gotCould not find module 'Control.Monad.Trans.Maybe'
(usingrunhaskell
command after installing ghc 7.6.3 on Ubuntu 14.04). 1) Is the empty stack a bug in the Shift example or in my interpreter? 2) How should I configure Haskell so the reference implementation will run? An answer to either question will make the other question unnecessary. :) – DLosc – 2015-04-18T22:41:03.623We really, really need some more test cases in order to implement this. – AJMansfield – 2015-04-19T21:03:04.717
@DLosc I got the same error on my potential submission as well... It is possible that the last example is in fact in error. – AJMansfield – 2015-04-19T21:30:17.197
Also,
+$.!!+!!
is not an infinite loop, its just a function.+$.!!
is just a call-and-clone-the-results function. After the next+!
, we have two call-and-clone-the-results functions. The last!
calls the first call-and-clone on the second. The first call-and-clone calls the first call-and-clone, which then attempts to call on an empty stack, so clearly the function is missing some arguments. So going back up the call stack, the second call-and-clone just embeds the first one as a parameter, and execution halts. – AJMansfield – 2015-04-19T21:44:12.533@AJMansfield I apologize for the delay. The composition function had a bug both in the interpreter and the examples, which are fixed now. Thanks for noticing it. – Zgarb – 2015-04-21T07:32:39.943
Why is there both
$
and!
if they end up doing the same thing? – kirbyfan64sos – 2015-04-22T18:44:36.633No problem about the delay, real life >> PPCG. ;) – DLosc – 2015-04-22T19:37:53.777
FYI, the last three example programs only work with Martin's definition of
.
--your version gives me an empty stack error in all three. For example, part of the0010
program puts together the functionchain(clone,chain(chain,call))
and calls it onsay
. But after cloningsay
and chaining it with the copy, all we have on the temporary stack ischain(say,say)
, and socall
fails. If everything goes back on the global stack, however, we have a blank to use for the second argument ofcall
. (Hope this made sense--it's hard without stack diagrams.) – DLosc – 2015-04-22T20:12:49.850@kirbyfan64sos ! acts directly on the stack, whereas $ pushes a ! onto the stack for use later. – sirpercival – 2015-04-22T23:36:58.730
@DLosc Thanks for the observation! The examples and my interpreter are indeed bugged (again), but I think I know where the problem lies. – Zgarb – 2015-04-23T13:15:21.387
@DLosc The examples are now fixed. – Zgarb – 2015-04-24T10:52:56.473
Either I made a mistake in my implementation, or the specification of
chain
doesn't fit to what the examples do. As I understand, when the output off
doesn't has the same number of arguments as the input ofg
, the result is undefined (i.e. the interpreter can throw an error, or do anything else). When running example 3 in my interpreter, I get an error when evaluatingchain(f=shift(clone<1>)<2>, g=clone<1>)([say<1>, #])
(the angle brackets show the arity): f returns[say<1>, #, #]
, and this doesn't fit the arity of clone. – Paŭlo Ebermann – 2015-10-20T19:46:40.890@PaŭloEbermann The output of
f
may have more arguments thang
takes in. The extra arguments are left where they are, and become part of the output ofchain(f,g)
. With your example, the output would be[say<1>, say<1>, #, #]
, sinceg
takes only the firstsay<1>
as its argument. – Zgarb – 2015-10-20T19:54:22.607@Zgarb thanks, this fixes my interpreter ... I suggested an edit which hopefully makes this clearer (although actually the example already shows this behaviour). I will post my solution when I succeeded golfing it a bit. – Paŭlo Ebermann – 2015-10-20T20:10:37.427