Write a Shift Interpreter

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 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.

Zgarb

Posted 2015-04-17T16:56:04.127

Reputation: 39 083

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) 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 !. After n such applications, the remaining function had only one argument, and at that point it computes f(z1, z2, ..., zn) (i.e. f applied to all the arguments you curried in), which pushes some new values, and then immediately consumes m values from the stack and calls g 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 if f returns a list of less than m values, the result is undefined (the composition has arity n, so it cannot eat more arguments from the stack). Essentially, the output of f is used as a temporary stack, on which g is pushed and applied m 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 got Could not find module 'Control.Monad.Trans.Maybe' (using runhaskell 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.623

We 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.633

No 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 the 0010 program puts together the function chain(clone,chain(chain,call)) and calls it on say. But after cloning say and chaining it with the copy, all we have on the temporary stack is chain(say,say), and so call fails. If everything goes back on the global stack, however, we have a blank to use for the second argument of call. (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 of f doesn't has the same number of arguments as the input of g, 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 evaluating chain(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 than g takes in. The extra arguments are left where they are, and become part of the output of chain(f,g). With your example, the output would be [say<1>, say<1>, #, #], since g takes only the first say<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

Answers

12

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

sirpercival

Posted 2015-04-17T16:56:04.127

Reputation: 1 824

1

My first reaction: @_@ Seriously, though, nice work--putting actual functions on the stack is a really neat solution. A few tips: 1) Ternary operators can usually be shortened one way or another. 2) You can replace ['1','0'][...] with just '10'[...]. 3) Why x is 0 and not x==0 (or x<1)? 4) Don't bother specifying RuntimeError, just except will do. 5) Since you're using Python 2, tabs and spaces count as different indentation levels--ugly, but should save you ~25 bytes.

– DLosc – 2015-04-22T22:18:02.380

@DLosc thanks so much! I cut it down by ~80 bytes in total, which is a >10% improvement. I tried to get rid of the ternary expression in p(), but it threw a syntax error... :/ – sirpercival – 2015-04-22T23:19:14.857

1You should be able to cut it to x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))--the logical operators are still short-circuiting, but use fewer characters than the ternary. Then save another byte by using x.a-1 as the condition (0/false if x is 1, nonzero/true otherwise) and swapping the 'then' and 'else' expressions: x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y). (Gotta golf mine some more now that you've passed me... ;^) ) – DLosc – 2015-04-23T03:43:02.863

Doesn't work, sadly... one of the functions doesn't get the right number of arguments, and it throws an error. What I'm looking for right now is a way to deal with the decorators more succinctly. – sirpercival – 2015-04-23T11:48:51.780

1After running into a similar problem with mine, I understand what's failing now--if x.a==1 is true but x(y) returns something falsy, it tries to evaluate u(...) as well. But it looks as if you don't need to save the measly 3 bytes that would have given you! I concede, sir: you have surpassed me. – DLosc – 2015-04-23T15:47:24.493

1

Just one quibble: the specified output format doesn't have spaces--you can solve by various strategies, not sure which one is shortest. Of course, your program handles the RuntimeError while mine just asks the user to redirect stderr... so we're probably even on quibbles. ;^)

– DLosc – 2015-04-23T15:56:31.280

1What is the *_ for in the lambdas? – mbomb007 – 2015-04-23T16:11:01.057

@DLosc it didn't seem like the output format was that stringent to me, but I could be wrong - maybe OP would care to comment? I can output a spaceless string, it just costs me 9 bytes. – sirpercival – 2015-04-23T17:19:15.950

@mbomb007 each of apply, chain, and shift act on n-ary functions, so you have to be able to handle any size input. – sirpercival – 2015-04-23T17:19:25.407

1Outputting a space-delimited string is fine. – Zgarb – 2015-04-23T20:40:33.053

1This is unusually readable for a colf - well done. You can save a couple characters by combining the second and third lines and the eleventh and twelfth lines using semicolons. – isaacg – 2015-04-24T11:54:00.773

@isaacg i have one more golf to post that removes the readability in favor of an exec/translate string... lol. cuts it down by 23 bytes, though... i should probably post an ungolfed version, or just go full Pyth (if i knew Pyth well enough). – sirpercival – 2015-04-24T18:32:33.743

1Wouldn't raw_input be shorter than using sys.argv? – Zgarb – 2015-04-24T19:29:02.597

ha. yes, i believe it would. i shall update. EDIT: wait, maybe not. i'm using sys.stdout.write() for the output, since i can't print inside a lambda. i still need to import sys, so i might as well go with sys.argv[1]. EDIT2: nope, still shorter. good call. – sirpercival – 2015-04-24T20:06:37.557

1Can you use .replace("!","z(lambda ") instead of .translate({33:u"z(lambda "})? – DLosc – 2015-04-24T20:54:45.250

Oh, yeah, i forgot i don't need to do translate since I'm only subbing one character! – sirpercival – 2015-04-24T21:06:48.040

1Two less: exec" instead of exec " and 1else instead of 1 else. – Erik the Outgolfer – 2016-07-16T16:45:42.190

4

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.

AJMansfield

Posted 2015-04-17T16:56:04.127

Reputation: 2 758

2

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.

DLosc

Posted 2015-04-17T16:56:04.127

Reputation: 21 213

Could you write a program that generates the above program and then executes it? You have lots of recurring code that should be compressible like lambda a and k.pop(). – mbomb007 – 2015-04-22T21:26:25.817

@mbomb007 ... I think my brain would explode. (But see recent edit--I made the k.pop() situation a little less repetitive, anyway.) – DLosc – 2015-04-22T22:36:50.890

can you do the exec/translate trick for all those lambdas? stick them all in one string? – sirpercival – 2015-04-22T23:23:44.893

one other comment: I doubt you can rely on function nesting <= 9 with this language – sirpercival – 2015-04-23T00:40:54.000

@sirpercival Yes, I was thinking of trying that. And no, I suppose not. :^P – DLosc – 2015-04-23T03:49:06.620

Yup. Wasn't readable before. Is even less so now. Prettify markup should help. – mbomb007 – 2015-04-23T16:08:04.907

1

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.

Paŭlo Ebermann

Posted 2015-04-17T16:56:04.127

Reputation: 1 010

The looping versions actually will throw a StackOverflowError at some point, finishing then. The JVM has no recursion stack optimization (or at least none which would work for my program). – Paŭlo Ebermann – 2015-10-21T00:19:16.603