Write a Shift Interpreter

Question

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 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 x1,x2,...,xn-1 and returns f(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 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 0s or 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.

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 0s and 1s. 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 1s always increases by one:

@?/!@>!??/!!>!+.!!.!!.!!.+>!.!!$$$$+$>!>!$>!>!+>!$>!>!>!+>!>!///!!>!>!>!.!!.!!.!!.!!.!!.!!.!!.!!.!!.!!+!!!!!

The repository contains an annotated version.

Answer 1

Python 2, 752 667 534 506 445 436 427 404 398 393 bytes

This is by no means short... but I did my best. Any golfing suggestions would be very much appreciated...

EDIT6: This is now a script instead of a function. Save it to a file (shift.py, forex), then run it with $ python shift.py '<my_input>'. Make sure to put the input in single quotes, or bash will go crazy with the input characters.

EDIT7: Aaaaaaand... it's not readable anymore. But I got rid of 23 more bytes, so that's good, I guess? I'll post an ungolfed version too.

EDIT8: One more golf, thanks to @Zgarb.

k,d=[],[]
u=k.append
def z(f,a=1):f.a=a;return f
exec "i=!x:x(*map(k.pop,[-1]*x.a)));e=dict(zip('?+>/$.@',[0,!x:u(x)<u(x)),!x:u(!a,*_:x(*_)<u(a),x.a+1))),!x,y,z:u((z,y)[x<1]),3),!x,y:u(!*_:x(y,*_),x.a-1))if x.a>1 else x(y),2),!x,y:u(!*_:x(*_)<i(y),x.a)),2),!x:d.append(`+(x>0)`)<u(x))]))".replace('!',"z(lambda ")
for _ in raw_input():
 try:[i,u][_ in e](e.get(_,e['$']))
 except:break
print d

EDIT: thanks to @DLosc for the golfing help! Managed to reduce it by 85 bytes.

EDIT2: cut out a ton of unnecessary wrappers, and dropped it by another 133 bytes!

EDIT3: ...and 28 more thanks to @Sp3000 and @orlp in chat!

EDIT4: with help from @orlp & @Sp3000, removed all the decorators and now it's 61 bytes shorter.

EDIT5: help meeeeee, I can't stop golfing this.... 9 more bytes gone. Getting rid of the final print statement would save another 7, but then if you run m() in a loop, all the output is on the same line... is that ok?

Here's an ungolfed version:

stack = []
push = stack.append

def arity(func,a=1): #give each of our functions an arity
    func.arity = a
    return func

def do(func): ##pop the args off the stack, then call the function
    args = map(stack.pop,[-1]*func.arity)
    func(*args)

def call(func,arg): #apply is just do(call)
    if func.arity == 1:
        func(arg)
    else:
        def curried(*a): #a quick little currier
            func(arg, *a)
        curried = arity(curried, func.arity - 1)
        push(curried)

def clone(arg):
    push(arg)
    push(arg)

def shift(func):
    def shifted(a, *arg):
        func(*arg)
        push(a)
    shifted = arity(shifted, func.arity + 1)
    push(shifted)

def fork(a, b, c):
    if a == 0:
        push(b)
    else:
        push(c)

def chain(func, gunc):
    def composition(*args):
        func(*args)
        do(gunc)
    composition = arity(composition, func.arity)
    push(composition)

def say(arg):
    print '10'[arg == 0],
    push(arg)

commands = {'?': 0,
            '+': arity(clone),
            '>': arity(shift),
            '/': arity(fork, 3),
            '$': arity(call, 2),
            '.': arity(chain, 2),
            '@': arity(say)}

def interpret(input_string):
    for command in input_string:
        try:
            if command == '!':
                do(call)
            else:
                push(commands[command])
        except RuntimeError: #this handles max recursion depth errors
            break            # for infinite programs
    print

if __name__ == "__main__":
    interpret(raw_input())

Basic idea is that the python list works very nicely as a stack, and by storing u=k.append, not only do I save characters, but I can also use @u as a decorator for pushing functions (not anymore!).

Since the couple of functions which act on functions of n-arity need to be able to accept an arbitrary number of arguments, I had to use *args, which meant that my original plan of tracking f.func_code.co_argcount had to be replaced by an arity decorator attribute.

In terms of handling infinite programs, the interpreter runs until it hits max recursive depth; the RuntimeError handler at the bottom has it exit quietly at that point, and it prints out the current output string then.

Test cases:

>>> tests
['?@!@@!', '$+.!!+!!', '?@$..!!+.!!+>!.!!!!+?/!!!@!@>!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!', '?@+$>!>!.!!+>!.!!///!!>!>!.!!+!!!!!!!!!!!!!', '@?/!@>!.!!??/!!>!.!!+.!!.+>!.!!$$.!!$.!!$.!!+.!!$>!>!.!!$>!>!.!!+>!.!!$>!>!>!.!!+>!>!.!!///!!>!>!>!.!!+!!!!!']
>>> for t in tests: m(t)
0 1

0 0 1 0
0
0 0
0 0 0
0 0 0 0
0 0 1 0 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Answer 2

Ghostscript

Not golfed yet, since I still need to work out the parsing function.

This implementation uses _ and : instead of > and /, and it requires all the program characters to be separated with spaces. This is because > and / are not valid names in Postscript, and the operators are not self-delimiting, but this will be fixed when I write the parser.

The first part of the code should be fairly transparent, as it is merely repeating the definitions of the operator functions. The magic happens in the definition of !.

/switch {
    /y exch def
    /x exch def
    {x} {y} ifelse
} bind def

/unwrap {
    dup type (arraytype) eq {aload pop} if
} bind def

/! { % IN: <x> <f> OUT: <g>|<f(x)>
    [ 3 1 roll unwrap] cvx %prefix argument into function
    dup /fun exch def %bind

    [ count 1 roll ] { %run the function sandboxed so it can't take any additional args
        2 dict begin
        /=only {} def % suppress output
            {
                fun
            } stopped /err exch def clear err
        end
    } .runandhide


    exch {
        $error /errorname get
        (stackunderflow) ne {
            handleerror
        } if

        $error /newerror false put

        unwrap
    } {
        unwrap exec
    } ifelse
} def

/? 0 def
/+ {{dup}} def
/_ {{/f exch def pop f}} def % using _ instead of >
/: {{? ne 3 1 roll switch}} def % using : instead of /
/$ {{!}} def
/. {{/g exch def exec g}} def 
/@ {{dup ? eq {0}{1} ifelse =only}} def

The way ! works is simple: First, it adds argument x to f by prefixing x to the contents of f, pushing it back on the stack, and naming a copy of the result fun.

It then wraps the entire stack up as an array. .runandhide is a Ghostscript extension for running sandboxed code, hiding the contents of the preceding array from the procedure it is invoked on. The dict command pushes a new dictionary on the dict stack, narrowing the scope of names defined within until end pops it back off. It also replaces =only (the output operator I use in @) with a dummy one, suppressing the output during the trial run. stopped is the PostScript equivalent of the try statement found in other languages, and it returns true if its procedure threw an error, and false if it ran to completion.

Once the trial run of fun completes, the program restores the original stack from the hidden array, and if fun completed without error, it then runs it for real, keeping the output.

Answer 3

Python3, 685 670 634 633 bytes

I'm pretty sure this is the longest thing I've ever golfed. It used to be somewhat readable, but following @sirpercival's advice has eliminated that drawback!

from re import*
E,*k="E"
P="e(k.pop(),k.pop())"
def H(a,b):global k;k+=list(a)+[N(b)];exec("k+=%s;"%P*Z(N(b)));return[]
def e(a,b):a=sub("(?<!\d)0",repr(N(b,1)).replace("\\",r"\\"),a,1);return Z(a)and[a]or list(eval(a))
D=list(zip("ilhydsSNZ",[3,2,2]+[1]*6,sub("A","N(a)",',b,c:[N([b,c][a>E])]|,b:e(A,N(b))|,b:["H(%s,%s)"%(A,repr(b))]|:print(0+(a>E),end="")or[A]|:[A]*2|:["S(0,%s)"%A]|,b:b+[A]|,b=-1:sub("\d+",lambda m:str(int(m.group())+b),a)|:len(split("\D0",a))-1').split("|")))
for n,r,f in D:exec(n+"=lambda a"+f)
F=dict(zip("/$.@+>?!",D))
for z in input():n,r,f=F[z];k+=z!="!"and[[n+"(%s)"%",".join("0"*r),E][z=="?"]]or eval(P)

k is the stack, which contains functions represented as strings like "h(0,0)" (which is chain). When a function is passed as an argument to another function, it gets repr'd and all the numbers incremented: "h('h(1,1)',0)". Once all the 0s are replaced in a function, the whole thing is passed to eval, thereby calling the appropriate Python function--most of which are lambda functions generated from the big string in line 6 by exec in line 7.

Getting multiple levels of nested functions incremented, quoted, and escaped properly was the biggest headache. I could save a bit more on regex operations if I could assume that function nesting won't proceed any deeper than 9 levels, but as pointed out in comments that's probably not a safe assumption.

Ungolfed earlier version of code:

from re import *
E="E"
stack=[]

clone=lambda a:[unnest(a)]*2
shift=lambda a:["shifted(0,%s)"%unnest(a)]
fork=lambda a,b,c:[unnest(c if a!=E else b)]
call=lambda a,b:apply(unnest(a),unnest(b))
chain=lambda a,b:["chained(%s,%s)"%(unnest(a),repr(b))]
def say(a):
 print(1 if a!=E else 0,end="")
 return [unnest(a)]

shifted=lambda a,b:b+[unnest(a)]
def chained(a,b):
 global stack
 stack+=list(a)+[unnest(b)]
 exec("stack+=apply(stack.pop(),stack.pop());"*zeros(unnest(b)))
 return []

nest=lambda a,direction:sub("\d+",lambda m:str(int(m.group())+direction),a)
unnest=lambda a:nest(a,-1)
zeros=lambda a:len(split("\D0",a))-1
def apply(a,b):
 a=sub("(?<!\d)0",repr(nest(b,1)).replace("\\",r"\\"),a,1)
 return [a] if zeros(a) else list(eval(a))

functions=dict(zip("+>/$.@",zip(["clone","shift","fork","call","chain","say"],[1,1,3,2,2,1])))

for cmd in input():
 if"!"==cmd:
  stack+=apply(stack.pop(),stack.pop())
 elif"?"==cmd:
  stack+=[E]
 else:
  name,arity=functions[cmd]
  stack+=[name+"(%s)"%",".join("0"*arity)]

The one potential flaw of this implementation is that it uses recursion, so programs that ought to be infinite hit the max recursion depth pretty quickly. (You probably want to redirect stderr when you run an infinite program--otherwise the stack trace will swamp the actual output.) Other than that, everything seems to be working.

Answer 4

Ceylon, 1167 1057 1031

I don't get it that short as the mono-typed python versions ...

import ceylon.language.meta.model{N=Function}import ceylon.collection{H=HashMap}interface D of F|b{}object b satisfies D{}class F(shared Integer a,[D+](D+)f,[D*]c=[])satisfies D{shared[D+]o(D i){[D+]s=[i].prepend(c);return a==1then f(*s)else[F(a-1,f,s)];}shared[D+]y([D+]i){return f(*i.prepend(c));}}F m<A>(N<[D+],A>f)given A satisfies[D+]=>F(f.parameterTypes.size,(D+i)=>f.apply(*i));[D,D]e(D x)=>[x,x];[F]t(F f){[D+]g(D+i){assert(is[D+]r=i.rest);return[i[0],*f.y(r)];}return[F(f.a+1,g)];}[D]k(D a,D d,D c)=>a==b then[d]else[c];[D+]l(F a,D x)=>a.o(x);[F]n(F f,F g){[D+]h(D+i){[D+]r=f.y(i);assert(is[D+]d=r[0:g.a]);return g.y(d).append(r[g.a...]);}return[F(f.a,h)];}[D]y(D x){process.write(x==b then"0"else"1");return[x];}class I(){variable D[]s=[];value c=H{'?'->b,'+'->m(`e`),'>'->m(`t`),'/'->m(`k`),'$'->m(`l`),'.'->m(`n`),'@'->m(`y`)};shared void r(Character i){if(i=='!'){assert(is F f=s[0],is D x=s[1]);s=f.o(x).append(s[2...]);}else{assert(is D d=c[i]);s=[d].append(s);}}}shared void z(){process.readLine()?.collect(I().r);}

Here is a formatted (and commented) version of the same code (with spaces/newlines/comments it becomes 4867 bytes):

import ceylon.language.meta.model {
    N=Function
}
import ceylon.collection {
    H=HashMap
}
//↑ Import of stuff we need – with a shorter alias.
// (The comment is down here due to a bug in my comment and space
//  remover – it doesn't remove a comment if it is the first token
//  at all.)

// Our data items are either functions or blanks.
interface D of F | b {}

// There is no point in having many blanks – so here a singleton.
object b satisfies D {}

// The function class. Our functions take a number of data items,
// and return a number of data items.
// We know the arity a, and have also an actual function f, and a number
// or already collected arguments.
class F(shared Integer a, [D+](D+) f, [D*] c = [])
        satisfies D {
    // apply once (= collect one parameter). Returns either the result,
    // or a function with arity one less.
    shared [D+] o(D i) {
        [D+] s = [i].prepend(c);
        return a == 1 then f(*s) else [F(a - 1, f, s)];
    }
    // apply fully (= with all needed parameters).
    // The input size should equal the arity.
    shared [D+] y([D+] i) {
        // merge collected and input arguments.
        return f(*i.prepend(c));
    }
}
// creates a shift function from a ceylon function,
// deriving the arity using reflection.
F m<A>(N<[D+],A> f)
        given A satisfies [D+]
        => F(f.parameterTypes.size, (D+ i) => f.apply(*i));

//
// clone: a unary function that duplicates its input: any value x is mapped to [x,x].
//
[D, D] e(D x) => [x, x];

//
// shift: 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].
//
[F] t(F f) {
    [D+] g(D+ i) {
        assert (is [D+] r = i.rest);
        return [i[0], *f.y(r)];
    }
    return [F(f.a + 1, g)];
}

//
// fork: a ternary function that takes three inputs a,d,c, and returns [d] if a is a blank,
// and [c] otherwise.
//
[D] k(D a, D d, D c) => a == b then [d] else [c];

//
// call: a binary function that pops a function f and a value x,
//        and applies f to x exactly as ! does.
//
[D+] l(F a, D x) => a.o(x);

//
// chain:  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].
//
[F] n(F f, F g) {
    [D+] h(D+ i) {
        // call f, remember the results.
        [D+] r = f.y(i);
        // first some results from f are the arguments to g:
        assert (is [D+] d = r[0:g.a]);
        // remaining results from f are passed back directly, with the results from g.
        return g.y(d).append(r[g.a...]);
    }
    return [F(f.a, h)];
}

//
// say: a unary function that simply returns its input, and prints 0 if it was a blank,
//      and 1 if it was a function.
// 
[D] y(D x) {
    process.write(x == b then "0" else "1");
    return [x];
}

//
// Interpreter class, which manages the stack and interprets the commands.
// Just call the r method with the individual command characters.
//
class I() {
    // The stack. The only variable in the whole program.
    variable D[] s = [];

    // a hash map of items to be pushed by commands, most build using the m function.
    // The apply command is not here, this is handled separately by the interpreter. 
    value c = H {
        '?'->b,
        '+'->m(`e`),
        '>'->m(`t`),
        '/'->m(`k`),
        '$'->m(`l`),
        '.'->m(`n`),
        '@'->m(`y`)
    };

    // Interprets one command, indicated by a character.
    // Will throw an AssertionError for unknown commands.
    shared void r(Character i) {
        if (i == '!') {
            assert (
                is F f = s[0],
                is D x = s[1]);
            // apply f on x, push the result onto a shortened version of the stack.
            s = f.o(x).append(s[2...]);
        } else {
            assert (is D d = c[i]);
            // push d on top of the stack.
            s = [d].append(s);
        }
    }
}

shared void z() {
    process.readLine()?.collect(I().r);
}

The functions clone e, shift t, fork k, call l, say y and chain n use the last letter of the names for the abbreviated version, because that gave less collisions. (Trivia: fork was originally defined this way: [Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c]; – when I renamed blank to b, this broke, because it now compared the parameters a and b instead a with the blank. Took me some time to debug.)

The z function is shared because my IDE runs those functions – the command line tool can also run non-shared ones.