Schreiben Sie einen Schichtdolmetscher

10

EDIT: Wie einige von Ihnen vermuteten, gab es einen Fehler im offiziellen Dolmetscher: Die Reihenfolge der Komposition .wurde umgekehrt. Ich hatte zwei Versionen des Dolmetschers und habe hier die falsche verwendet. Die Beispiele wurden auch für diese falsche Version geschrieben. Ich habe den Interpreter im Repository und die folgenden Beispiele behoben. Die Beschreibung von >war auch etwas mehrdeutig, also habe ich das behoben. Ich entschuldige mich auch dafür, dass ich so lange gebraucht habe, dass ich in echte Dinge verwickelt war.

EDIT2: Mein Interpreter hatte einen Fehler, dessen Implementierung .sich in den Beispielen widerspiegelte (sie stützten sich auf undefiniertes Verhalten). Das Problem ist jetzt behoben.

Einführung

Shift ist eine esoterische funktionale Programmiersprache, die ich vor ein paar Jahren erstellt, aber heute veröffentlicht habe. Es ist stapelbasiert, hat aber auch automatisches Currying wie Haskell.

Spezifikation

In Shift gibt es zwei Datentypen:

  • Funktionen, die eine beliebige positive Arität (Anzahl der Eingänge) haben und die eine Liste der Ausgänge zurückgeben. Beispielsweise hat eine Funktion, die ihre einzige Eingabe dupliziert, Arität 1, und eine Funktion, die ihre beiden Eingaben vertauscht, hat Arität 2.
  • Leerzeichen, die alle identisch sind und keinen anderen Zweck haben, als keine Funktionen zu sein.

Ein Shift-Programm besteht aus null oder mehr Befehlen , von denen jeder ein einzelnes ASCII-Zeichen ist. Insgesamt gibt es 8 Befehle:

  • !( apply ) fügt eine Funktion fund einen Wert xaus dem Stapel ein und gilt ffür x. Wenn fArity 1 vorhanden ist, wird die Liste f(x)an der Vorderseite des Stapels hinzugefügt. Wenn es arity hat n > 1, wird eine neue (n-1)-ary-Funktion gauf den Stack verschoben . Es nimmt Eingaben und kehrt zurück .x1,x2,...,xn-1f(x,x1,x2,...,xn-1)
  • ?( leer ) schiebt ein Leerzeichen auf den Stapel.
  • +( Klon ) schiebt eine unäre Funktion auf den Stapel, die ihre Eingabe dupliziert: Jeder Wert xwird zugeordnet [x,x].
  • >( shift ) schiebt eine unäre Funktion, die eine n-ary-Funktion übernimmt, auf den Stapel fund gibt eine (n+1)-ary-Funktion zurück g, die ihr erstes Argument ignoriert x, fdie verbleibenden aufruft und xvor dem Ergebnis angreift . Zum Beispiel shift(clone)ist eine Binärfunktion, die Eingaben a,bund Rückgaben entgegennimmt [a,b,b].
  • /( fork ) schiebt eine ternäre Funktion, die drei Eingaben benötigt a,b,c, auf den Stapel und gibt zurück, [b]wenn sie aleer ist, und [c]ansonsten.
  • $( Anruf ) drückt auf den Stapel eine binäre Funktion , die eine Funktion öffnet fund einen Wert x, und wendet fauf xgenau wie der !Fall ist.
  • .( chain ) schiebt eine Binärfunktion auf den Stapel, die zwei Funktionen fund gund ihre Zusammensetzung zurückgibt: Eine Funktion h, die dieselbe Arität wie fhat und deren Eingaben normal sind, gilt ffür sie und dann vollständig für gdas Ergebnis (Aufrufe) es so oft, wie es seine Arität vorschreibt), mit unbenutzten Gegenständen aus der Ausgabe des fVerbleibs im Ergebnis von h. Zum Beispiel sei angenommen , daß feine binäre Funktion ist, die ihr zweites Argument Klonen und gist Anruf . Wenn der Stapel enthält [f,g,a,b,c]und wir tun .!!, dann enthält er [chain(f,g),a,b,c]; Wenn wir es als !!nächstes tun , fwird es zuerst angewendet a,b, um zu produzieren[a,b,b]wird dann gauf die ersten beiden Elemente davon angewendet, da seine Arität 2 ist und erzeugt [a(b),b], und der Stapel wird schließlich sein [a(b),b,c].
  • @( sagen wir ) drückt eine unäre Funktion, die einfach ihre Eingabe zurückgibt und druckt, 0wenn es ein Leerzeichen war und 1wenn es eine Funktion war.

Beachten Sie, dass alle Befehle außer dem !einfachen Verschieben eines Werts auf den Stapel keine Möglichkeit zur Eingabe bieten und die einzige Möglichkeit zur Ausgabe die Verwendung ist @. Ein Programm wird interpretiert, indem die Befehle einzeln ausgewertet, 0s oder 1s gedruckt werden, wenn "say" aufgerufen wird, und beendet werden. Jedes hier nicht beschriebene Verhalten (Anwenden eines Leerzeichens, Anwenden eines Stapels der Länge 0 oder 1, Aufrufen von "Kette" auf ein Leerzeichen usw.) ist undefiniert: Der Interpreter kann abstürzen, stillschweigend fehlschlagen, nach Eingaben fragen oder was auch immer.

Die Aufgabe

Ihre Aufgabe ist es, einen Dolmetscher für Shift zu schreiben. Es sollte von STDIN, der Befehlszeile oder dem Funktionsargument ein zu interpretierendes Shift-Programm nehmen und in STDOUT drucken oder die resultierende (möglicherweise unendliche) Ausgabe von 0s und 1s zurückgeben. Wenn Sie eine Funktion schreiben, müssen Sie in irgendeiner Weise auf die Ausgaben mit unendlicher Länge zugreifen können (Generator in Python, Lazy List in Haskell usw.). Alternativ können Sie eine andere Eingabe, eine Zahl n, verwenden und mindestens nZeichen der Ausgabe zurückgeben, wenn diese länger als ist n.

Die niedrigste Byteanzahl gewinnt und Standardschlupflöcher sind nicht zulässig.

Testfälle

Dieses Schichtprogramm druckt 01:

?@!@@!

Von links beginnend: Drücken Sie ein Leerzeichen, drücken Sie say und wenden Sie das say auf das Leerzeichen an. Dies gibt aus 0. Drücken Sie dann zweimal auf " Sagen" und wenden Sie das zweite Wort auf das erste an. Dies gibt aus 1.

Dieses Programm wiederholt sich für immer und erzeugt keine Ausgabe:

$+.!!+!!

Drücken Sie call und clone und wenden Sie dann chain auf sie an (wir benötigen zwei !s, da chain eine binäre Funktion ist). Jetzt enthält der Stapel eine Funktion, die ein Argument akzeptiert, es dupliziert und die erste Kopie der zweiten aufruft. Mit +!!duplizieren wir diese Funktion und rufen sie selbst auf.

Dieses Programm druckt 0010:

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

Schieben Sie ein Leerzeichen und sagen Sie . Erstellen Sie dann eine Binärfunktion, die das zweite Argument bkopiert, dann das erste kopiert aund mit sich selbst komponiert. Anschließend wendet Sie die Komposition auf die Kopie von an bund gibt sie zurück [a(a(b)),b]. Wenden Sie es auf say und blank an und wenden Sie dann say auf die beiden auf dem Stapel verbleibenden Elemente an.

Dieses Programm druckt 0. Für jedes !!!angehängte Element wird ein zusätzliches gedruckt 0.

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

Schieben Sie ein Leerzeichen und sagen Sie . Erstellen Sie dann eine ternäre Funktion, die f,g,xals Eingabe und Rückgabe verwendet wird [f,f,g,g(x)]. Clone , dass Funktion, und es auf sich, sagen wir , und der Rohling. Diese Anwendung ändert den Stapel nicht, sodass wir die Funktion beliebig oft erneut anwenden können.

Dieses Programm druckt die unendliche Folge 001011011101111..., wobei die Anzahl der 1s immer um eins zunimmt:

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

Das Repository enthält eine mit Anmerkungen versehene Version.

Zgarb
quelle
Ich bin hier etwas verwirrt. Wenn Sie "Takes In" wie im Shift-Befehl schreiben, meinen Sie Pops oder den Apply-Befehl "Apply"?
Tecywiz121
1
Außerdem bin ich mir aus Ihrer Spezifikation nicht sicher, wie die Kette funktionieren soll. Könnten Sie es bitte anhand eines Beispiels erläutern?
Tecywiz121
@ tecywiz121 So verstehe ich es: Angenommen, Sie haben zwei Funktionen oben auf dem Stapel, f(x1, x2, ..., xn)und g(y1, y2, ..., ym). Durch das Aufrufen werden .beide Popups angezeigt und eine Funktion gedrückt h(z1, z2, ..., zn). Jetzt können Sie all diese Argumente auffressen, indem Sie sie schrittweise verarbeiten !. Nach nsolchen Anwendungen hatte die verbleibende Funktion nur ein Argument und berechnet zu diesem Zeitpunkt f(z1, z2, ..., zn)(dh fangewendet auf alle Argumente, die Sie eingegeben haben), wodurch einige neue Werte übertragen werden, und verwendet dann sofort mWerte aus dem Stapel und ruft gsie auf.
Martin Ender
@ MartinBüttner Wenn Zgarb der Meinung ist, dass es den Regeln entspricht, können Sie einen zweiten Eingabeparameter verwenden, der die maximale Größe der Ausgabe definiert. Dies wäre auch eine Lösung für das Problem der trägen Bewertung.
Randomra
@ tecywiz121 .funktioniert genau wie von Martin beschrieben, außer dass das Ergebnis undefiniert ist , wenn feine Liste mit weniger als mWerten zurückgegeben wird (die Komposition hat Arität n, sodass sie nicht mehr Argumente vom Stapel essen kann). Im Wesentlichen wird die Ausgabe von fals temporärer Stapel verwendet, auf den mal mit ggeschoben und angewendet mwird !, und das Ergebnis davon wird dem Hauptstapel hinzugefügt.
Zgarb

Antworten:

12

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

Das ist keineswegs kurz ... aber ich habe mein Bestes gegeben. Irgendwelche Golfvorschläge wären sehr dankbar ...

EDIT6: Dies ist jetzt ein Skript anstelle einer Funktion. Speichern Sie es in einer Datei (shift.py, forex) und führen Sie es dann mit aus $ python shift.py '<my_input>'. Stellen Sie sicher, dass die Eingabe in einfache Anführungszeichen gesetzt wird, da sonst die Eingabezeichen verrückt werden.

EDIT7: Aaaaaaund ... es ist nicht mehr lesbar. Aber ich habe 23 weitere Bytes entfernt, also ist das gut, denke ich? Ich werde auch eine ungolfed Version posten.

EDIT8: Noch ein Golf, dank @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: danke an @DLosc für die Golfhilfe! Hat es geschafft, es um 85 Bytes zu reduzieren.

EDIT2: Schneiden Sie eine Tonne unnötiger Wrapper aus und lassen Sie sie um weitere 133 Bytes fallen!

EDIT3: ... und 28 weitere dank @ Sp3000 und @orlp im Chat!

EDIT4: Mit Hilfe von @orlp & @ Sp3000 wurden alle Dekoratoren entfernt und jetzt sind es 61 Bytes kürzer.

EDIT5: hilf mir, ich kann nicht aufhören, dies zu spielen ... 9 weitere Bytes sind weg. Wenn Sie die endgültige print-Anweisung entfernen, werden weitere 7 gespeichert. Wenn Sie jedoch m () in einer Schleife ausführen, befindet sich die gesamte Ausgabe in derselben Zeile. Ist das in Ordnung?

Hier ist eine 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())

Die Grundidee ist, dass die Python-Liste sehr gut als Stapel funktioniert. Durch das Speichern speichere u=k.appendich nicht nur Zeichen, sondern kann sie auch @uals Dekorator für Push-Funktionen verwenden (nicht mehr!).

Da die beiden Funktionen, die auf Funktionen von n-arity wirken, eine beliebige Anzahl von Argumenten akzeptieren müssen, musste ich sie verwenden *args, was bedeutete, dass mein ursprünglicher Plan zur Verfolgung von f.func_code.co_argcount durch eine Arität ersetzt werden musste Dekorateur Attribut.

In Bezug auf die Verarbeitung von unendlichen Programmen wird der Interpreter ausgeführt, bis die maximale rekursive Tiefe erreicht ist. Der RuntimeError-Handler unten lässt ihn an diesem Punkt leise beenden und druckt dann die aktuelle Ausgabezeichenfolge aus.

Testfälle:

>>> 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
quelle
1
Meine erste Reaktion: @ _ @ Im Ernst, gute Arbeit - tatsächliche Funktionen auf den Stapel zu legen, ist eine wirklich nette Lösung. Einige Tipps: 1) Ternäre Operatoren können normalerweise auf die eine oder andere Weise gekürzt werden . 2) Sie können durch ['1','0'][...]nur ersetzen '10'[...]. 3) Warum x is 0und nicht x==0(oder x<1)? 4) Geben Sie nicht an RuntimeError, sondern exceptreichen Sie einfach aus . 5) Da Sie Python 2 verwenden, gelten Tabulatoren und Leerzeichen als unterschiedliche Einrückungsstufen. Sie sollten jedoch ~ 25 Byte sparen.
DLosc
1
Sie sollten in der Lage sein, es zu x.a==1and x(y)or u(a(x.a-1)(b.partial(x,y)))schneiden - die logischen Operatoren schließen immer noch kurz, verwenden jedoch weniger Zeichen als das ternäre. Speichern Sie dann ein weiteres Byte, indem Sie x.a-1als Bedingung (0 / false, wenn x1, ungleich Null / true, andernfalls) die Ausdrücke 'then' und 'else' austauschen : x.a-1and u(a(x.a-1)(b.partial(x,y)))or x(y). (Ich muss noch mehr Golf spielen, jetzt wo du an mir vorbeigegangen bist ...; ^))
DLosc
1
Nachdem ich auf ein ähnliches Problem mit meinem gestoßen bin, verstehe ich, was jetzt fehlschlägt - wenn x.a==1es wahr ist, aber x(y)etwas Falsches zurückgibt, versucht es auch zu bewerten u(...). Aber es sieht so aus, als müssten Sie nicht die mickrigen 3 Bytes speichern, die Sie erhalten hätten! Ich gebe zu, Sir: Sie haben mich übertroffen.
DLosc
1
Nur ein Problem: Das angegebene Ausgabeformat hat keine Leerzeichen - Sie können mit verschiedenen Strategien lösen , ohne sicher zu sein, welches das kürzeste ist. Natürlich erledigt Ihr Programm das, RuntimeErrorwährend meins den Benutzer nur auffordert, stderr umzuleiten ... also sind wir wahrscheinlich sogar auf Streitereien. ; ^)
DLosc
1
Wofür ist das *_in den Lambdas?
mbomb007
4

Ghostscript

Noch nicht Golf gespielt, da ich die Parsing-Funktion noch ausarbeiten muss.

Diese Implementierung verwendet _und :anstelle von >und /und erfordert, dass alle Programmzeichen durch Leerzeichen getrennt werden. Dies liegt daran, dass >und /sind keine gültigen Namen in Postscript, und die Operatoren sind nicht selbstabgrenzend, aber dies wird behoben, wenn ich den Parser schreibe.

Der erste Teil des Codes sollte ziemlich transparent sein, da er lediglich die Definitionen der Operatorfunktionen wiederholt. Die Magie geschieht in der Definition von !.

/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

Die Art und Weise !funktioniert , ist einfach: Erstens, es fügt Argument xzu fdurch das Vorsetzen xauf den Inhalt f, es zurück auf den Stapel schieben, und eine Kopie des Ergebnisses zu benennen fun.

Anschließend wird der gesamte Stapel als Array zusammengefasst. .runandhideist eine Ghostscript-Erweiterung zum Ausführen von Sandbox-Code, die den Inhalt des vorhergehenden Arrays vor der Prozedur verbirgt, mit der es aufgerufen wird. Der dictBefehl verschiebt ein neues Wörterbuch auf den Diktierstapel und schränkt den Umfang der darin definierten Namen ein, bis endes wieder entfernt wird. Es ersetzt auch =only(den Ausgabeoperator, in dem ich verwende @) durch einen Dummy- Operator , wodurch die Ausgabe während des Testlaufs unterdrückt wird. stoppedist das PostScript-Äquivalent der tryin anderen Sprachen gefundenen Anweisung und gibt true zurück, wenn die Prozedur einen Fehler ausgelöst hat, und false, wenn sie vollständig ausgeführt wurde.

Sobald der Testlauf von funabgeschlossen ist, stellt das Programm den ursprünglichen Stapel aus dem verborgenen Array wieder her. Wenn es funohne Fehler abgeschlossen wurde, führt es ihn tatsächlich aus und behält die Ausgabe bei.

AJMansfield
quelle
2

Python3, 685 670 634 633 Bytes

Ich bin mir ziemlich sicher, dass dies das längste ist, was ich jemals Golf gespielt habe. Früher war es etwas lesbar, aber das Befolgen des Ratschlags von @ sirpercival hat diesen Nachteil beseitigt !

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)

kist der Stapel, der Funktionen enthält, die als Zeichenfolgen dargestellt werden "h(0,0)"(was c h ain ist ). Wenn eine Funktion als Argument an eine andere Funktion übergeben wird, werden sie reprund alle Zahlen inkrementiert : "h('h(1,1)',0)". Sobald alle 0s in einer Funktion ersetzt wurden, wird das Ganze an übergeben eval, wodurch die entsprechende Python-Funktion aufgerufen wird. Die meisten davon sind Lambda-Funktionen, die aus der großen Zeichenfolge in Zeile 6 von execin Zeile 7 generiert werden .

Das größte Problem bestand darin, mehrere Ebenen verschachtelter Funktionen zu erhöhen, in Anführungszeichen zu setzen und ordnungsgemäß zu entkommen. Ich könnte ein bisschen mehr bei Regex-Operationen sparen, wenn ich davon ausgehen könnte, dass die Funktionsverschachtelung nicht tiefer als 9 Ebenen verläuft, aber wie in den Kommentaren erwähnt, ist dies wahrscheinlich keine sichere Annahme.

Ungolfed frühere Version des Codes:

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)]

Der einzige mögliche Fehler dieser Implementierung besteht darin, dass sie eine Rekursion verwendet, sodass Programme, die unendlich sein sollten, die maximale Rekursionstiefe ziemlich schnell erreichen. (Sie möchten wahrscheinlich stderr umleiten, wenn Sie ein unendliches Programm ausführen - andernfalls überschwemmt der Stack-Trace die tatsächliche Ausgabe.) Ansonsten scheint alles zu funktionieren.

DLosc
quelle
Könnten Sie ein Programm schreiben, das das obige Programm generiert und dann ausführt? Sie haben viele wiederkehrende Codes, die wie lambda aund komprimierbar sein sollten k.pop().
mbomb007
@ mbomb007 ... Ich denke mein Gehirn würde explodieren. (Aber siehe letzte Änderung - ich habe die k.pop()Situation sowieso ein wenig weniger repetitiv gemacht.)
DLosc
Kannst du den Exec / Translate-Trick für all diese Lambdas machen? sie alle in eine Schnur stecken?
Sirpercival
ein weiterer Kommentar: Ich bezweifle, dass Sie sich auf die Funktionsverschachtelung <= 9 mit dieser Sprache verlassen können
sirpercival
@sirpercival Ja, ich habe darüber nachgedacht, das zu versuchen. Und nein, ich denke nicht. : ^ P
DLosc
1

Ceylon, 1167 1057 1031

Ich verstehe es nicht so kurz wie die monotypisierten Python-Versionen ...

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);}

Hier ist eine formatierte (und kommentierte) Version desselben Codes (mit Leerzeichen / Zeilenumbrüchen / Kommentaren werden 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);
}

Die Funktionen Klonen e, Verschieben t, Verzweigen k, Aufrufen l, Sagen yund Verketten nverwenden den letzten Buchstaben der Namen für die abgekürzte Version, da dies weniger Kollisionen ergab. (Trivia: Gabel wurde ursprünglich auf diese Weise definiert: [Data] fork(Data a, Data b, Data c) => a == blank then [b] else [c];- wenn ich umbenannt blankzu b, diese brach, weil es nun die Parameter verglichen aund bstattdessen amit dem Rohling hat mich einige Zeit zu debuggen..)

Die zFunktion wird gemeinsam genutzt, da meine IDE diese Funktionen ausführt. Das Befehlszeilentool kann auch nicht gemeinsam genutzte Funktionen ausführen.

Paŭlo Ebermann
quelle
Die Loop-Versionen lösen tatsächlich irgendwann einen StackOverflowError aus und beenden ihn dann. Die JVM hat keine Rekursionsstapeloptimierung (oder zumindest keine, die für mein Programm funktionieren würde).
Paŭlo Ebermann