Schreiben Sie einen Dolmetscher für die untypisierte Lambda-Rechnung

45

Die Herausforderung besteht darin, einen Interpreter für die untypisierte Lambda-Rechnung mit möglichst wenigen Zeichen zu schreiben . Wir definieren den untypisierten Lambda-Kalkül wie folgt:

Syntax

Es gibt die folgenden drei Arten von Ausdrücken:

  • Ein Lambda-Ausdruck hat die Form, (λ x. e)bei der es xsich um einen beliebigen legalen Variablennamen und einen ebeliebigen legalen Ausdruck handeln kann. Hier xheißt der Parameter und eheißt der Funktionskörper.

    Der Einfachheit halber fügen wir die weitere Einschränkung hinzu, dass es keine Variable mit demselben Namen geben darf, wie xderzeit im Gültigkeitsbereich. Eine Variable beginnt im Gültigkeitsbereich zu sein, wenn ihr Name zwischen und erscheint, und .endet am entsprechenden Gültigkeitsbereich ).

  • Funktionsanwendung hat die Form (f a)wo fund asind gesetzliche Ausdrücke. Hier fheißt die Funktion und aheißt das Argument.
  • Eine Variable hat die Form, xbei der xes sich um einen zulässigen Variablennamen handelt.

Semantik

Eine Funktion wird angewendet, indem jedes Vorkommen des Parameters im Funktionskörper durch sein Argument ersetzt wird. Formal ein Ausdruck der Form ((λ x. e) a), in dem xein Name ist variabel und eund asind Ausdrücke, bewertet (oder reduziert) auf den Ausdruck , e'wo e'das Ergebnis des Ersetzens jedes Auftreten xin emit a.

Eine Normalform ist ein Ausdruck, der nicht weiter ausgewertet werden kann.

Die Herausforderung

Ihre Mission ist es, einen Interpreter zu schreiben, der als Eingabe einen Ausdruck des untypisierten Lambda-Kalküls ohne freie Variablen verwendet und als Ausgabe die Normalform des Ausdrucks (oder einen Ausdruck, der Alpha-Kongruenz zu ihm aufweist) erzeugt. . Wenn der Ausdruck keine normale Form hat oder kein gültiger Ausdruck ist, ist das Verhalten undefiniert.

Die Lösung mit der geringsten Anzahl von Zeichen gewinnt.

Ein paar Notizen:

  • Die Eingabe kann entweder von stdin oder von einem Dateinamen als Befehlszeilenargument gelesen werden (Sie müssen nur das eine oder das andere implementieren - nicht beide). Die Ausgabe erfolgt nach stdout.
  • Alternativ können Sie eine Funktion definieren, die die Eingabe als Zeichenfolge verwendet und die Ausgabe als Zeichenfolge zurückgibt.
  • Wenn für Sie Nicht-ASCII-Zeichen problematisch sind, können Sie \anstelle von λ den Backslash ( ) verwenden.
  • Wir zählen die Anzahl der Zeichen, nicht die Bytes. Selbst wenn Ihre Quelldatei als Unicode kodiert ist, zählt λ als ein Zeichen.
  • Zulässige Variablennamen bestehen aus einem oder mehreren Kleinbuchstaben, dh Zeichen zwischen a und z (alphanumerische Namen, Großbuchstaben oder nicht-lateinische Buchstaben müssen nicht unterstützt werden - dies macht Ihre Lösung jedoch nicht ungültig).
  • In Bezug auf diese Herausforderung sind keine Klammern optional. Jeder Lambda-Ausdruck und jede Funktionsanwendung wird von genau einem Klammerpaar umgeben. Kein Variablenname wird in Klammern gesetzt.
  • Syntaktischer Zucker wie das Schreiben (λ x y. e)für (λ x. (λ y. e))muss nicht unterstützt werden.
  • Wenn eine Rekursionstiefe von mehr als 100 erforderlich ist, um eine Funktion auszuwerten, ist das Verhalten undefiniert. Das sollte mehr als niedrig genug sein, um ohne Optimierung in allen Sprachen implementiert zu werden und dennoch groß genug, um die meisten Ausdrücke ausführen zu können.
  • Sie können auch davon ausgehen, dass der Abstand wie in den Beispielen ist, dh keine Leerzeichen am Anfang und Ende der Eingabe oder vor einem λoder .genau einem Leerzeichen nach einem .und zwischen einer Funktion und ihrem Argument und nach einem λ.

Sample Input und Output

  • Eingang: ((λ x. x) (λ y. (λ z. z)))

    Ausgabe: (λ y. (λ z. z))

  • Eingang: (λ x. ((λ y. y) x))

    Ausgabe: (λ x. x)

  • Eingang: ((λ x. (λ y. x)) (λ a. a))

    Ausgabe: (λ y. (λ a. a))

  • Eingang: (((λ x. (λ y. x)) (λ a. a)) (λ b. b))

    Ausgabe: (λ a. a)

  • Eingang: ((λ x. (λ y. y)) (λ a. a))

    Ausgabe: (λ y. y)

  • Eingang: (((λ x. (λ y. y)) (λ a. a)) (λ b. b))

    Ausgabe: (λ b. b)

  • Eingang: ((λx. (x x)) (λx. (x x)))

    Ausgabe: alles (Dies ist ein Beispiel für einen Ausdruck ohne normale Form)

  • Eingang: (((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))

    Ausgabe: (λ a. a)(Dies ist ein Beispiel für einen Ausdruck, der sich nicht normalisiert, wenn Sie die Argumente vor dem Funktionsaufruf auswerten, und leider ein Beispiel, für das mein Lösungsversuch fehlschlägt.)

  • Eingang: ((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))

    Ausgabe: `(λ a. (λ b. (a (a (a (a (a (a (a (a b)))))))))) Dies berechnet 2 ^ 3 in Zahlen der Kirche.

sepp2k
quelle
1
Können wir davon ausgehen, dass der Zeichenfolge kein vorangestelltes oder angefügtes Leerzeichen hinzugefügt wird und dass das Leerzeichen ansonsten wie in der Beispieleingabe angegeben ist? Das heißt, kein Leerzeichen zwischen Klammern, zwischen dem Punkt und dem Parameternamen und anderen Instanzen von Leerzeichen ist genau 1 Leerzeichen.
JPvdMerwe
@JPvdMerwe: Ja, guter Punkt, das können Sie annehmen.
sepp2k 31.01.11
Gibt es freie Variablen? Ich meine Variablen, die nicht durch ein Lambda gebunden sind, wie im Ausdruck (\y. a).
FUZxxl
3
Viele oder alle der hier beschriebenen Lösungen können keine Substitution implementieren, die die Erfassung vermeidet! Sie sollten einen Testfall wie ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y)) hinzufügen, der zu (λ x. (Λ z. X)) ausgewertet werden soll. nicht (λ x. (λ x. x)).
Anders Kaseorg
1
@ sepp2k Haben Sie darüber nachgedacht, ((λ f. (λ x. (fx))) (λ y. (λ x. y))) als Testfall zu addieren und die aktuelle Antwort, die fälschlicherweise (λ x. (λ x. x))?
Anders Kaseorg

Antworten:

36

Neueste:

Ich habe es auf 644 Zeichen reduziert und Teile von cEll in cOpy und Par zerlegt. Zwischengespeicherte Aufrufe von cell und cdr in temporäre lokale Variablen und Verschieben dieser lokalen Variablen in Globals in "Terminal" -Funktionen (dh nicht rekursiven Funktionen). Außerdem sind Dezimalkonstanten kürzer als Zeichenliterale und dieses fiese Geschäft ...

atom(x){
    return m[x]>>5==3;
}

... identifiziert Kleinbuchstaben korrekt (unter der Annahme von ASCII), akzeptiert aber auch alle von `{|} ~. (Dieselbe Beobachtung zu ASCII wird in diesem hervorragenden Video zu UTF-8 gemacht .)

Et viola: |

#include<stdio.h>
#include<string.h>
#define X m[x]
#define R return
char*n,*m;int u,w,d;C(x,y){w=n-m;n+=sprintf(n,y?"(%s %s)":"(%s)",&X,m+y)+1;R w;}T(x){R X>>5==3;}
L(x){R X==92;}O(x,j){w=n-m;memcpy(n,&X,j);n+=j;*n++=0;R w;}E(x){X==' '?++x:0;R
X==41?0:L(x)?O(x,4):P(x);}P(x){d=0,w=x;do{X==40?d++:X==41?d--:0;++x;}while(d>0);R
O(w,x-w);}D(x){u=E(x+1);R u?E(x+1+strlen(m+u)):0;}V(x){int a=E(x+1),b=D(x);R
T(x)|T(a)?x:L(a)?C(a,V(b)):L(E(a+1))?V(S(V(b),E(a+3),D(a))):V(C(V(a),b?V(b):0));}S(w,y,x){R
T(x)?(X==m[y]?w:x):C(L(w+1)?E(x+1):S(w,y,E(x+1)),D(x)?S(w,y,D(x)):0);}
Y(char*s){n+=strlen(s=strcpy(n,s))+1;printf("%s\n%s\n\n",s,m+V(s-m));n=m+1;}

char*s[]={
"((\\ a. a) (b))",
"((\\ x. x) (\\ y. (\\ z. z)))",
"(\\ x. ((\\ y. y) x))",
"(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))",
"((\\ x. (\\ y. y)) (\\ a. a))",
"(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))",
"((\\x. (x x)) (\\x. (x x)))",0};
#include<unistd.h>
main(){char**k;n=m=sbrk(4096);*n++=0;for(k=s;*k;k++)Y(*k);R 0;}

Vorhin:

Kann ich ein paar Stimmen für Mühe bekommen? Ich arbeite seit einer Woche Tag und Nacht daran. Ich habe das Originalpapier von McCarthy ausgegraben und war von einem Fehler im Papier selbst geplagt, bis ich den Anhang zu Paul Grahams The Roots of Lisp gelesen habe . Ich war so abgelenkt, dass ich mich aus meinem Haus ausgesperrt und dann völlig vergessen hatte, bis ich in dieser Nacht um 12:30 Uhr wieder nach Hause kam (ein wenig zu spät, um den Hausverwalter anzurufen, der weit draußen in der Grafschaft wohnt), und das Geld ausgeben musste Nacht bei meiner Großmutter (Hacken weg, bis mein Laptop Akku trocken war).

Und nach alledem ist es noch lange nicht so weit bis zum Sieger!

Ich bin mir nicht sicher, wie ich das verkürzen soll. und ich habe alle schmutzigen Tricks benutzt, die mir einfallen! Vielleicht geht es nicht in C.

Mit etwas Großzügigkeit beim Zählen (der erste Block nimmt eine Zeichenfolge und druckt das Ergebnis aus) sind es 778 770 709 694 Zeichen. Aber um es eigenständig zu machen, muss es diesen sbrkAufruf haben. Und um kompliziertere Ausdrücke verarbeiten zu können, ist auch der signalHandler erforderlich . Und natürlich kann es nicht mit einem Code, der versucht zu verwenden, zu einem Modul gemacht werden malloc.

Also leider ist es hier:

#include<stdio.h>
#include<string.h>
#define K(j) strncpy(n,m+x,j);n+=j;goto N;
#define R return
#define X m[x]
#define L =='\\'
char*m,*n;T(x){R islower(X);}V(x){int a=E(x+1);R
T(x)?x:T(a)?x:m[a]L?C(a,V(D(x))):m[E(a+1)]L?V(S(V(D(x)),E(a+3),D(a))):V(C(V(a),D(x)?V(D(x)):0));}
C(x,y){char*t=n;sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y);n+=strlen(n)+1;R
t-m;}Y(char*s){char*t=strcpy(n,s);n+=strlen(n)+1;printf("%s=>%s\n",s,m+V(t-m));n=m+1;}S(x,y,z){R
T(z)?(m[z]==m[y]?x:z):C(m[z+1]L?E(z+1):S(x,y,E(z+1)),D(z)?S(x,y,D(z)):0);}D(x){R
E(x+1)?E(x+strlen(m+E(x+1))+1):0;}E(x){char*t=n,d=0;if(X==' ')++x;if(T(x)){K(1)}if(X
L){K(4)}do{d=X?(X=='('?d+1:(X==')'?d-1:d)):0;*n++=m[x++];}while(d);N:*n++=0;R t-m;}

char*samp[]={
    "a","a","b","b",
    "((\\ a. a) (b))", "(b)",
    "((\\ x. x) (\\ y. (\\ z. z)))", "(\\ y. (\\ z. z))",
    "(\\ x. ((\\ y. y) x))", "(\\ x. x)",
    "(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))", "(\\ a. a)",
    "((\\ x. (\\ y. y)) (\\ a. a))", "(\\ y. y)",
    "(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))", "(\\ b. b)",
    "((\\x. (x x)) (\\x. (x x)))", "undef",
    NULL};
#include<unistd.h>

unsigned sz;
#include<signal.h>
void fix(x){signal(SIGSEGV,fix);brk(m+(sz*=2));}
main(){
    char**t;
    signal(SIGSEGV,fix);
    m=n=sbrk(sz=10*getpagesize());
    *n++=0;
    for(t=samp;*t;t+=2){
        Y(*t);
        printf("s.b. => %s\n\n", t[1]);
    }
    return 0;
}

Hier ist der Block kurz vor den endgültigen Reduzierungen. Die Tricks hier sind ganzzahlige Cursor anstelle von Zeigern (unter Ausnutzung des 'impliziten int'-Verhaltens) und die Verwendung von' Arbeitsspeicher ': Dies char*nist der' neue 'oder' nächste 'Zeiger in den freien Raum. Aber manchmal schreibe ich einen String in den Speicher, rufe dann strlen auf und erhöhe n; effektiv Speicher verwenden und dann zuweisen, nachdem die Größe einfacher zu berechnen ist. Sie können sehen, dass dies praktisch direkt aus dem McCarthy-Artikel hervorgeht, mit Ausnahme der cell()Schnittstellen zwischen den Funktionen und der Zeichenfolgendarstellung von Daten.

#include<stdio.h>
#include<string.h>
char*m,*n;  //memory_base, memory_next
atom(x){  // x is an atom if it is a cursor to a lowercase alpha char.
    return x?(islower(m[x])?m[x]:0):0;
}
eq(x,y){  // x and y are equal if they are both atoms, the same atom.
    return x&&y&&atom(x)==atom(y);
}
cell(x){  // return a copy of the list-string by cursor, by parsing
    char*t=n,d=0;
    if(!x||!m[x])
        return 0;
    if(m[x]==' ')
        ++x;
    if(atom(x)){
        *n++=m[x];
        *n++=0;
        return(n-m)-2;
    }
    if(m[x]=='\\'){  // our lambda symbol
        memcpy(n,m+x,4);
        n+=4;
        *n++=0;
        return(n-m)-5;
    }
    do{  // um ...
        d=m[x]?(m[x]=='('?d+1:(m[x]==')'?d-1:d)):0;
        *n++=m[x++];
    }while(d);
    *n++=0;
    return t-m;
}
car(x){  // return (copy of) first element
    return x?cell(x+1):0;
}
cdr(x){  // return (copy of) rest of list
    return car(x)?cell(x+strlen(m+car(x))+1):0;
}
cons(x,y){  // return new list containing first x and rest y
    char*t=n;
    return x?(sprintf(n,y?"(%s %s)":"(%s)",m+x,m+y),n+=strlen(n)+1,t-m):0;
}
subst(x,y,z){  // substitute x for z in y
    if(!x||!y||!z)
        return 0;
    return atom(z)? (eq(z,y)?x:z):
        cons(m[z+1]=='\\'?car(z):
        subst(x,y,car(z)),cdr(z)?subst(x,y,cdr(z)):0);
}
eval(x){  // evaluate a lambda expression
    int a;
    return atom(x)?x:
        atom(a=car(x))?x:
        m[a]=='\\'?cons(a,eval(cdr(x))):
        m[car(a)]=='\\'?eval(subst(eval(cdr(x)),cell(a+3),cdr(a))):
        eval( cons(eval(a),cdr(x)?eval(cdr(x)):0));
}
try(char*s){  // handler
    char*t=strcpy(n,s);
    n+=strlen(n)+1;
    printf("input: %s\n", s);
    printf("eval => %s\n", m+eval(t-m));
    n=m+1;
}
Luser Droog
quelle
1
Ich habe noch ein paar Tricks gefunden, um ein oder zwei Charaktere zu retten, aber nichts Radikales. sprintf(n,...);n+=strlen(n)+1;ist besser, als n+=sprintf(n,...)+1;die Array-Syntax zu invertieren, x[m]anstatt m[x]mir zu erlauben, alle Indirektionen durch ein 'postfix'-Makro zu ersetzen #define M [m]... x Mdas 1 Zeichen spart und einen "freien" Zeilenumbruch ergibt, da Leerzeichen zum Trennen der Token erforderlich sind.
Luser Droog
Es scheint Ähnlichkeiten mit jar.2 xlisp 4.0 von IOCCC 1989 zu geben .
Luser Droog
Ich habe versucht, dies zu einem volleren Lisp-Interpreter zu erweitern .
luser droog
Der kommentierte Code // um ...durchläuft die Zeichenfolge und zählt die runden Klammern, bis er die übereinstimmende enge Klammer auf der richtigen Verschachtelungsebene findet.
Luser Droog
1
Dies wertet fälschlicherweise ((\ f. (\ X. (Fx))) (\ y. (\ X. Y))) bis (\ x. (Fx)) aus.
Anders Kaseorg
22

Binäre Lambda-Rechnung 186

Das im Hex-Dump unten gezeigte Programm

00000000  18 18 18 18 18 18 44 45  1a 10 18 18 45 7f fb cf  |......DE....E...|
00000010  f0 b9 fe 00 78 7f 0b 6f  cf f8 7f c0 0b 9f de 7e  |....x..o.......~|
00000020  f2 cf e1 b0 bf e1 ff 0e  6f 79 ff d3 40 f3 a4 46  |[email protected]|
00000030  87 34 0a a8 d0 80 2b 0b  ff 78 16 ff fe 16 fc 2d  |.4....+..x.....-|
00000040  ff ff fc ab ff 06 55 1a  00 58 57 ef 81 15 bf bf  |......U..XW.....|
00000050  0b 6f 02 fd 60 7e 16 f7  3d 11 7f 3f 00 df fb c0  |.o..`~..=..?....|
00000060  bf f9 7e f8 85 5f e0 60  df 70 b7 ff ff e5 5f f0  |..~.._.`.p...._.|
00000070  30 30 6f dd 80 5b b3 41  be 85 bf ff ca a3 42 0a  |00o..[.A......B.|
00000080  c2 bc c0 37 83 00 c0 3c  2b ff 9f f5 10 22 bc 03  |...7...<+...."..|
00000090  3d f0 71 95 f6 57 d0 60  18 05 df ef c0 30 0b bf  |=.q..W.`.....0..|
000000a0  7f 01 9a c1 70 2e 80 5b  ff e7 c2 df fe e1 15 55  |....p..[.......U|
000000b0  75 55 41 82 0a 20 28 29  5c 61                    |uUA.. ()\a|
000000ba

akzeptiert nicht ganz das von Ihnen vorgeschlagene Format. Es wird vielmehr ein Lambda-Term im binären Lambda-Kalkül-Format (BLC) erwartet. In der normalen Formreduktion wird jedoch jeder einzelne Schritt mit minimalen Klammern angezeigt.

Beispiel: Berechnung von 2 ^ 3 in Zahlen der Kirche

Speichern Sie den obigen Hex-Dump mit xxd -r> symbolic.Blc

Besorgen Sie sich einen BLC-Interpreter von http://tromp.github.io/cl/uni.c

cc -O2 -DM=0x100000 -m32 -std=c99 uni.c -o uni
echo -n "010000011100111001110100000011100111010" > threetwo.blc
cat symbolic.Blc threetwo.blc | ./uni
(\a \b a (a (a b))) (\a \b a (a b))
\a (\b \c b (b c)) ((\b \c b (b c)) ((\b \c b (b c)) a))
\a \b (\c \d c (c d)) ((\c \d c (c d)) a) ((\c \d c (c d)) ((\c \d c (c d)) a) b)
\a \b (\c (\d \e d (d e)) a ((\d \e d (d e)) a c)) ((\c \d c (c d)) ((\c \d c (c d)) a) b)
\a \b (\c \d c (c d)) a ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b))
\a \b (\c a (a c)) ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b))
\a \b a (a ((\c \d c (c d)) a ((\c \d c (c d)) ((\c \d c (c d)) a) b)))
\a \b a (a ((\c a (a c)) ((\c \d c (c d)) ((\c \d c (c d)) a) b)))
\a \b a (a (a (a ((\c \d c (c d)) ((\c \d c (c d)) a) b))))
\a \b a (a (a (a ((\c (\d \e d (d e)) a ((\d \e d (d e)) a c)) b))))
\a \b a (a (a (a ((\c \d c (c d)) a ((\c \d c (c d)) a b)))))
\a \b a (a (a (a ((\c a (a c)) ((\c \d c (c d)) a b)))))
\a \b a (a (a (a (a (a ((\c \d c (c d)) a b))))))
\a \b a (a (a (a (a (a ((\c a (a c)) b))))))
\a \b a (a (a (a (a (a (a (a b)))))))

Da der Hexdump eher unlesbar ist, handelt es sich hier um eine "disassemblierte" Version

@10\\@10\\@10\\@10\\@10\\@10\@\@\@\@@\@1010\@\\\@10\\@10\@\@@@1111111111101
1110@11111110\@@110@11111110\\\\@1110\@1111110\@@101101111110@111111110\@111
111110\\\\@@110@111111011110@11111011110@@10@1111110\@10110\@@111111110\@111
111110\@110@101111011110@1111111111010@1010\\@1110@11010@\@\@1010\@110@1010\
\@@@@@\@1010\@\\\\@@@10\@@111111111011110\\@@101111111111111110\@@101111110\
@@10111111111111111111111110@@@@1111111110\\110@@@@\@1010\\\\@@10\@@@1111101
11110\\@\@@@10111111101111110\@@1011011110\\@@11111010110\\@111110\@@1011110
1110@111010\10\1011111110@111110\\\@101111111111011110\\@@11111111110@@11111
0111110\10\@@@@11111110\\@10\\1101111101110\@@1011111111111111111111110@@@@1
11111110\\@10\\@10\\11011111101110110\\\@@101110110@1010\\11011111010\@@1011
111111111111110@@@@\@1010\@\\@@@10\@@@1110@10\\\@1011110\\110\\\@10\\\@1110\
@@@11111111110@1111111101010\10\\@\@@@1110\\\@10@1110111110\\1110\110@@@1111
0110@@@1111010\\110\\\@10\\\@@1101111111101111110\\\@10\\\@@1101111110111111
10\\\110@1010110\\101110\\@@11010\\\@@1011111111111110@11110\@@1011111111111
101110\@\@@@@@@@@11010101010101010\\110\\10\\1010\10\\\1010\\1010@@@110\110\
@

Ersetzen Sie 00 (Lambda) durch \ und 01 (Anwendung) durch @ Jetzt ist es fast so lesbar wie Brainfuck :-)

Siehe auch http://www.ioccc.org/2012/tromp/hint.html

John Tromp
quelle
7
BLC verwendet zufällig ein binäres Alphabet. 00 ist Lambda, 01 ist Application und 1 ^ {n} 0 ist eine Variable in Unary. Es ist keine Kompilierung erforderlich.
John Tromp
3
Woher bekommst du einen Faktor x3? Tatsächlich haben Sie den Vorteil, dass Sprachen mit kleineren Quellenalphabeten wie BF bestraft werden. Für einen fairen Vergleich sollten alle Größen in Bits angegeben werden, und BF-Zeichen benötigen jeweils nur 3 Bits. Die meisten anderen Sprachen benötigen 7 Bit für ASCII, einige verwenden alle 8.
John Tromp
1
BTW +1 Das ist verdammt cool!
Luser Droog
1
Wenn Fraktran in Fraktran akzeptabel ist, verstehe ich nicht, warum dies überhaupt ein Problem sein sollte. Du kannst es nicht lesen? Du möchtest? Lernen!
Luser Droog
1
Was würde es brauchen, um das tatsächliche Eingabeformat zu lesen? Ich denke, da verlierst du potenzielle Gegenstimmen.
Luser Droog
14

Haskell, 342 323 317 305 Zeichen

Zum jetzigen Zeitpunkt ist dies die einzige Lösung, die ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y)) zum korrekten Ergebnis (λ x. (Λ z. x)) und nicht (λ x. (λ x. x)). Die korrekte Implementierung des Lambda-Kalküls erfordert eine Substitution ohne Capture , auch wenn durch die Vereinfachung dieses Problems garantiert wird, dass keine Variable eine andere Variable in ihrem Gültigkeitsbereich abschattet. (Mein Programm funktioniert auch ohne diese Garantie.)

data T=T{a::T->T,(%)::ShowS}
i d=T(i. \x v->'(':d v++' ':x%v++")")d
l f=f`T`\v->"(λ "++v++". "++f(i(\_->v))%('x':v)++")"
(?)=q.lex
q[(v,s)]k|v/="("=k(maybe T{}id.lookup v)s|'λ':u<-s,[(w,_:t)]<-lex u=t? \b->k(\e->l$b.(:e).(,)w).tail|0<1=s? \f->(?(.tail).k. \x z->f z`a`x z)
main=interact(? \f->(f[]%"x"++))

Anmerkungen:

  • Dies läuft in GHC 7.0, wie erforderlich, da diese Herausforderung im Januar 2011 festgelegt wurde. Es wäre 13 Zeichen kürzer, wenn ich GHC 7.10 annehmen dürfe.

Ungolfed-Version mit Dokumentation.

Anders Kaseorg
quelle
Ihr Prog in Ideone HashKell Compiler auf die Eingabe ((\ x. x) (\ y. (\ z. z))) "Laufzeitfehler" zurückgeben, auch in ((\\ x. x) (\\ y. ( \\ z. z))) ... was bedeutet es in Haskell "lex"?
RosLuP
2
@RosLuP Mein Programm akzeptiert λ, nicht \.
Anders Kaseorg
Geben Sie diesen Wert ((λ x. x) (λ y. (λ z. z)) in ideone.com ein. Rückgabe: Laufzeitfehler: 0 Speicher: 4876 Signal: -1
RosLuP
1
@RosLuP Ideone scheint die Unicode-Unterstützung unterbrochen zu haben. Probieren Sie die Befehlszeile oder einen anderen Online-Interpreter aus (funktioniert beispielsweise mit Rextester ).
Anders Kaseorg
2
@codeshot Der Frageautor hat bereits kommentiert, dass ((λ f. (λ x. (fx))) (λ y. (λ x. y))) ↦ (λ x. (λ z. x)) korrekt ist für Dieses Problem (genau wie der echte Lambda-Kalkül).
Anders Kaseorg
13

Python - 321 320

Hier ist mein (fester) Versuch:

l="("
def S(s):
 if s[0]!=l:return s
 if s[1]=="\\":g=s.find('.');return"(\\ %s. %s)"%(s[3:g],S(s[g+2:-1]))
 i=2;c=s[1]==l
 while c:c+=(s[i]==l)-(s[i]==')');i+=1
 t=S(s[1:i])
 z=s[i+1:-1]
 if l!=t[0]:return"(%s %s)"%(t,S(z))
 g=t.find('.')
 t=S(t[g+2:-1]).replace(t[3:g],z)
 if t!=s:t=S(t)
 return t
print S(raw_input())
JPvdMerwe
quelle
Das sieht gut aus, scheint aber nicht zu funktionieren. Ich habe einige Beispieleingaben und -ausgaben hinzugefügt, für die Ihr Code die falschen Ergebnisse liefert.
sepp2k
1
Dies führt nicht zu einer Substitution, die die Erfassung vermeidet. Zum Beispiel wird ((\ f. (\ X. (Fx))) (\ y. (\ X. Y))) fälschlicherweise zu (\ x. (\ X. X)) ausgewertet.
Anders Kaseorg
1
Warum ist dies als Antwort markiert, wenn es kaum funktioniert? Haben Sie die angegebenen Ein- und Ausgänge des Autors ausprobiert?
rbaleksandar
1
Die vom Autor bereitgestellten Testfälle reichen nicht aus, um die Fehler in dieser Antwort zu demonstrieren.
Anders Kaseorg
1
Diese Antwort ist weder richtig noch die kürzeste. Es kann die Erfassung nicht vermeiden und weist Fehler beim Ersetzen von Zeichenfolgen auf.
Richard Padley
6

Ruby 254 Zeichen

f=->u,r{r.chars.take_while{|c|u+=c==?(?1:c==?)?-1:0;u>0}*''}
l=->x{x=~/^(\(*)\(\\ (\w+)\. (.*)/&&(b,v,r=$1,$2,$3;e=f[1,r];(e==s=l[e])?b==''?x:(s=f[2,r];(x==y=b.chop+e.gsub(v,s[2+e.size..-1])+r[1+s.size..-1])?x:l[y]):(b+'(\\ '+v+'. '+s+r[e.size..-1]))||x}

Es kann gerne verwendet werden

puts l["((\\ x. (\\ y. x)) (\\ a. a))"]    # <= (\ y. (\ a. a))

Die Lösung ist noch nicht voll ausgereift, aber schon fast unlesbar.

Howard
quelle
Hallo Neid, mein alter Freund :)
Luser Droog
Dies führt nicht zu einer Substitution, die die Erfassung vermeidet. Zum Beispiel wird ((\ f. (\ X. (Fx))) (\ y. (\ X. Y))) fälschlicherweise zu (\ x. (\ X. X)) ausgewertet.
Anders Kaseorg
Zusätzlich zu dem obigen Erfassungsfehler wird hierdurch auch fälschlicherweise (\ y. (\ Xx. (\ X. Xx) y)) bis (\ y. (\ Xx. Yy)) ausgewertet, bei denen eine übereifrige Zeichenfolgensubstitution aufgetreten ist die nicht existierende Variable yy.
Anders Kaseorg
3

Bearbeiten: Überprüfen Sie meine Antwort unten für 250 unter reinem JavaScript.

2852 243 Zeichen mit LiveScript (Kein Regex! Nicht voll ausgereift - könnte verbessert werden)

L=(.0==\\)
A=->it.forEach?&&it.0!=\\
V=(.toFixed?)
S=(a,b,t=-1,l=0)->|L a=>[\\,S(a.1,b,t,l+1)];|A a=>(map (->S(a[it],b,t,l)),[0 1]);|a==l+-1=>S(b,0,l+-1,0)||a|l-1<a=>a+t;|_=>a
R=(a)->|L a=>[\\,R a.1]|(A a)&&(L a.0)=>R(S(R(a.0),R(a.1)).1)|_=>a

Prüfung:

a = [\\,[\\,[1 [1 0]]]]
b = [\\,[\\,[1 [1 [1 0]]]]]
console.log R [a, b]
# outputs ["\\",["\\",[1,[1,[1,[1,[1,[1,[1,[1,[1,0]]]]]]]]]]]

Welches ist 3^2=9, wie auf OP angegeben.

Wenn jemand neugierig ist, ist hier eine erweiterte Version mit einigen Kommentaren:

# Just type checking
λ = 100
isλ = (.0==λ)
isA = -> it.forEach? && it.0!=λ
isV = (.toFixed?)

# Performs substitutions in trees
# a: trees to perform substitution in
# b: substitute bound variables by this, if != void
# f: add this value to all unbound variables
# l: internal (depth)
S = (a,b,t=-1,l=0) ->
    switch
    | isλ a             => [λ, (S a.1, b, t, l+1)]
    | isA a             => [(S a.0, b, t, l), (S a.1, b, t, l)]
    | a == l - 1        => (S b, 0, (l - 1), 0) || a
    | l - 1 < a < 100   => a + t
    | _                 => a

# Performs the beta-reduction
R = (a) ->
    switch
    | (isλ a)               => [λ,R a.1]
    | (isA a) && (isλ a.0)  => R(S(R(a.0),R(a.1)).1)
    | _                     => a

# Test
a = [λ,[λ,[1 [1 0]]]]
b = [λ,[λ,[1 [1 [1 0]]]]]
console.log show R [a, b]
MaiaVictor
quelle
Dies entspricht nicht den Eingabe- und Ausgabespezifikationen des Problems.
Anders Kaseorg
3

Waterhouse Arc - 140 Zeichen

(=
f[is cons?&car._'λ]n[if
atom._ _
f._ `(λ,_.1,n:_.2)(=
c n:_.0
e _)(if
f.c(n:deep-map[if(is
c.1 _)e.1
_]c.2)(map n
_))]λ[n:read:rem #\._])
erhitzt
quelle
Wo kann ich Waterhouse Arc bekommen?
Anders Kaseorg
1
Als Dolmetscher ungültig ist nirgends zu finden
Katze
@AndersKaseorg hier
ASCII
@ Nur ASCII Ich weiß, was Arc ist, aber der Teil „Waterhouse“ hat mir nahegelegt, dass ein bestimmter Dialekt erforderlich war. Hast du es zum Laufen gebracht?
Anders Kaseorg
@AndersKaseorg Egal. Gefunden
Nur ASCII
2

C 1039 Bytes

#define F for
#define R return
#define E if(i>=M||j>=M)R-1;
enum{O='(',C,M=3999};signed char Q[M],D[M],t[M],Z,v,*o=Q,*d=D,*T;int m,n,s,c,w,x,y;K(i,j,k){!Z&&(Z=t[O]=1)+(t[C]=-1);E;if(!o[i]){d[j]=0;R 0;}if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!='\\'){d[j++]=o[i++];R K(i,j,i);}F(i+=2,y=w=0;i<M&&o[i]&&c;++i)c+=t[o[i]],!w&&c==1?w=i:0,!y&&o[i]=='.'?y=i+2:0;E;if(c){F(;d[j++]=o[i++];)E;R 0;}F(c=y;c<w;++c)if(o[c]=='\\')F(n=0,m=w+2;m<i;++m){if(o[m]==o[c+2]){F(x=0;o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[c+2+x];++x);if(o[c+2+x]!='.'||isalpha(o[m+x]))continue;if(v>'Z')R-1;F(n=c+2;n<w;++n)if(o[n]==o[m]){F(x=0; o[m+x]&&isalpha(o[m+x])&&o[m+x]==o[n+x];++x);if(o[m+x]=='.'&&!isalpha(o[n+x]))F(;--x>=0;) o[n+x]=v;}++v;}}F(c=y;c<w&&j<M;++c){F(x=0;o[c+x]&&o[c+x]==o[k+4+x]&&isalpha(o[c+x]); ++x);if(o[k+4+x]=='.'&&!isalpha(o[c+x])){F(m=w+2;m<i-1&&j<M;++m)d[j++]=o[m];c+=x-1;}else d[j++]=o[c];}E;Z=2;R K(i,j,i);}char*L(char*a){F(s=n=0;n<M&&(o[n]=a[n]);++n);if(n==M)R 0;v='A';F(;++s<M;){Z=0;n=K(0,0,0);if(Z==2&&n!=-1)T=d,d=o,o=T;else break;}R n==-1||s>=M?0:d;}

Variablen können als Eingabe mit Kleinbuchstaben [von a..z] eingegeben werden. Das System kann Variablen mit Großbuchstaben [von A..Z] generieren, wenn dies in der Ausgabe erforderlich ist. Nehmen Sie eine ASCII-Zeichenkonfiguration an.

#define P printf
main()
{char  *r[]={ "((\\ abc. (\\ b. (abc (abc (abc b))))) (\\ cc. (\\ dd. (cc (cc dd)))))",
              "((\\ fa. (\\ abc. (fa abc))) (\\ yy. (\\ abc. yy)))",
              "((\\ x. x) z)", 
              "((\\ x. x) (\\ y. (\\ z. z)))", 
              "(\\ x. ((\\ y. y) x))", 
              "((\\ x. (\\ y. x)) (\\ a. a))", 
              "(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))",
              "((\\ x. (\\ y. y)) (\\ a. a))",
              "(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))",             
              "((\\ x. (x x)) (\\ x. (x x)))",
              "(((\\ x. (\\ y. x)) (\\ a. a)) ((\\ x. (x x)) (\\ x. (x x))))",
             0}, *p;
 int    w;

 for(w=0; r[w] ;++w)
   {p=L(r[w]);
    P("o=%s d=%s\n", r[w], p==0?"Error ":p);
   }
 R  0;
}

/*1.039*/
RosLuP
quelle
Die Spezifikation verlangt \ oder λ, nicht /. Es erfordert auch die Unterstützung von Variablennamen mit mehreren Buchstaben.
Anders Kaseorg
'\ n' etc symbol '\' hat andere Verwendungen, es ist besser, '/' stattdessen zu verwenden
RosLuP
1
Die Herausforderung besteht jedoch darin, die Spezifikation zu erfüllen und nicht zu verbessern.
Anders Kaseorg
Ich habe etwas geschrieben, weil es ein bisschen konformer ist ... aber die Größe explodiert ...
RosLuP
1
932 Bytes
Ceilingcat
1

Haskell 456 C

Es kann viel kürzer sein, wenn die Lazy-Evaluierungsfunktion von Haskell vollständig genutzt wird. Leider weiß ich nicht, wie ich es machen soll.

Außerdem werden im Analyseschritt viele Zeichen verschwendet.

data T=A[Char]|B[Char]T|C T T
(!)=(++)
s(A a)=a
s(B a b)="(λ "!a!". "!s b!")"
s(C a b)='(':s a!" "!s b!")"
e d(A a)=maybe(A a)id(lookup a d)
e d(B a b)=B a.e d$b
e d(C a b)=f d(e d a)(e d b)
f d(B x s)q=e((x,q):d)s
f d p q=C p q
d=tail
p('(':'λ':s)=let(A c,t)=p(d s);(b,u)=p(d.d$t);in(B c b,d u)
p('(':s)=let(a,t)=p s;(b,u)=p(d t)in(C a b,d u)
p(c:s)|elem c" .)"=(A "",c:s)|1<2=let((A w),t)=p s in(A(c:w),t)
r=s.e[].fst.p
main=do l<-getLine;putStrLn$r l

Ungolfed-Version

data Expression = Literal String 
                | Lambda String Expression
                | Apply Expression Expression
                deriving Show

type Context = [(String, Expression)]

show' :: Expression -> String
show' (Literal a) = a
show' (Lambda x e) = "(λ " ++ x ++ ". " ++ show' e ++ ")"
show' (Apply e1 e2) = "(" ++ show' e1 ++ " " ++ show' e2 ++ ")"

eval :: Context -> Expression -> Expression
eval context e@(Literal a) = maybe e id (lookup a context)
eval context (Lambda x e) = Lambda x (eval context e)
eval context (Apply e1 e2) = apply context (eval context e1) (eval context e2)

apply :: Context -> Expression -> Expression -> Expression
apply context (Lambda x e) e2 = eval ((x, e2):context) e
apply context e1 e2 = Apply e1 e2

parse :: String -> (Expression, String)
parse ('(':'λ':s) = let
    (Literal a, s') = parse (tail s)
    (e, s'') = parse (drop 2 s')
    in (Lambda a e, tail s'')

parse ('(':s) = let
    (e1, s') = parse s
    (e2, s'') = parse (tail s')
    in (Apply e1 e2, tail s'')

parse (c:s) | elem c " .)" = (Literal "", c:s)
            | otherwise    = let ((Literal a), s') = parse s 
                             in (Literal (c:a), s')

run :: String -> String
run = show' . eval [] . fst . parse
main = do
  line <- getLine
  putStrLn$ run line
Strahl
quelle
3
Dies führt nicht zu einer Substitution, die die Erfassung vermeidet. Beispielsweise wird ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))) fälschlicherweise zu (λ x. (Λ x. X)) ausgewertet.
Anders Kaseorg
1

Erhält 231 mit JavaScript / ohne Regex

(function f(a){return a[0]?(a=a.map(f),1===a[0][0]?f(function d(b,a,e,c){return b[0]?1===b[0]?[1,d(b[1],a,e,c+1)]:2===b[0]?b[1]===c-1?d(a,0,c-1,0)||b:c-1<b[1]?[2,b[1]+e]:b:[d(b[0],a,e,c),d(b[1],a,e,c)]:b}(a[0],a[1],-1,0)[1]):a):a})

Erhält 2-Elemente-Arrays. 1steht für λund 2 steht für eine Bruijn-Indexvariable.

Prüfung:

zero = [1,[1,[2,0]]]; // λλ0
succ = [1,[1,[1,[[2,1],[[[2,2],[2,1]],[2,0]]]]]]; // λλλ(1 ((2 1) 0))
console.log(JSON.stringify(reduce([succ,[succ,[succ,zero]]]))); // 0+1+1+1
// Output: [1,[1,[[2,1],[[2,1],[[2,1],[2,0]]]]]] = λλ(1(1(1 0))) = number 3
MaiaVictor
quelle
Dies entspricht nicht den Eingabe- und Ausgabespezifikationen des Problems.
Anders Kaseorg
1

Python: 1266 Zeichen (gemessen mit wc)

from collections import *;import re
A,B,y,c=namedtuple('A',['l','r']),namedtuple('B',['i','b']),type,list.pop
def ab(t):c(t,0);p=c(t,0);c(t,0);return B(p,tm(t))
def tm(t):return ab(t)if t[0]=='\\'else ap(t)
def at(t):
    if t[0]=='(':c(t,0);r=tm(t);c(t,0);return r
    if 96<ord(t[0][0])<123:return c(t,0)
    if t[0]=='\\':return ab(t)
def ap(t):
    l = at(t)
    while 1:
        r = at(t)
        if not r:return l
        l = A(l,r)
def P(s):return tm(re.findall(r'(\(|\)|\\|[a-z]\w*|\.)',s)+['='])
def V(e):o=y(e);return V(e.b)-{e.i} if o==B else V(e.l)|V(e.r)if o==A else{e}
def R(e,f,t):return B(e.i,R(e.b,f,t)) if y(e)==B else A(R(e.l,f,t),R(e.r,f,t))if y(e)==A else t if e==f else e
def N(i,e):return N(chr(97+(ord(i[0])-96)%26),e) if i in V(e)else i
def S(i,e,a): return A(S(i,e.l,a),S(i,e.r,a)) if y(e)==A else(e if e.i==i else B(N(e.i,a),S(i,R(e.b,e.i,N(e.i,a)),a)))if y(e)==B else a if e==i else e
def T(e):
    if y(e)==A:l,r=e;return S(l.i,l.b,r)if y(l)==B else A(T(l),r)if y(l)==A else A(l,T(r))
    if y(e)==B:return B(e.i,T(e.b))
    q
def F(e):o=y(e);return r'(\%s. %s)'%(e.i,F(e.b))if o==B else'(%s %s)'%(F(e.l),F(e.r)) if o==A else e
def E(a):
    try: return E(T(a))
    except NameError:print(F(a))
E(P(input()))

Bei weitem nicht die kürzeste, aber es behandelt die Alpha-Umbenennung und alle in OPs Post aufgeführten Beispiele korrekt.

Björn Lindqvist
quelle
Sie können einige dieser Funktionsnamen kürzen und einige in Lambdas umwandeln. Sie haben hier und da auch etwas mehr Leerzeichen
Jo King
(1) Wenn Sie Einrückungen mit 4 Leerzeichen durch einzelne Leerzeichen ersetzen, sparen Sie einige Bytes. (2) Können Sie except NameErrormit nur ersetzen except? (3) Funktionsnamen mit zwei Zeichen können in Namen mit einem Zeichen umbenannt werden. (4) Es gibt einige Stellen, an denen Sie Aufgaben haben, die mit Leerzeichen versehen sind =. (5) if t[0]=='c'kann durch ersetzt werden if'c'==t[0].
Esolanging Fruit
1045 Bytes durch meist Formatierungsänderungen wie Einrückung und Lambdas
Jo King
0

C ++ (gcc) ,782 766 758 731 Bytes

#include <string>
#include <map>
#define A return
#define N new E
using S=std::string;using C=char;using I=int;S V(I i){A(i>8?V(i/9):"")+C(97+i%9);}S W(C*&s){C*b=s;while(*++s>96);A{b,s};}struct E{I t,i;E*l,*r;E(E&o,I d,I e){t=o.t;i=o.i+(o.i>=d)*e;t?l=N{*o.l,d,e},t-1?r=N{*o.r,d,e}:0:0;}E(I d,std::map<S,I>m,C*&s){t=*s-40?i=m[W(s)],0:*++s-92?l=N{d,m,s},r=N{d,m,++s},++s,2:(m[W(s+=2)]=d,l=N{d+1,m,s+=2},++s,1);}I R(I d){A t?t-1?l->t==1?l->l->s(d,0,*r),*this=*l->l,1:l->R(d)||r->R(d):l->R(d+1):0;}I s(I d,I e,E&v){t?t-1?l->s(d,e,v),r->s(d,e,v):l->s(d,e+1,v):i==d?*this={v,d,e},0:i-=i>d;}S u(I d){A t?t-1?S{"("}+l->u(d)+' '+r->u(d)+')':S{"(\\ "}+V(d)+". "+l->u(d+1)+')':V(i);}};S f(C*s){E a{0,{},s};for(I c=999;a.R(0)&&c--;);A a.u(0);}

Probieren Sie es online!

Die Grundidee hierbei ist, dass der Code eine interne Darstellung verwendet, die auf der Idee von de Bruijn-Indizes basiert - mit der Ausnahme, dass ich die Indizes umdrehe, um die Lambda-Tiefe der Bindung der referenzierten Variablen anzuzeigen. Im Code:

  • E::tstellt den Typ eines Knotens dar - 0 für einen variablen Blattknoten, 1 für einen Lambda-Knoten und 2 für einen Funktionsanwendungsknoten. (So ​​gewählt, dass es mit der Arität des Knotens übereinstimmt, was zufällig möglich ist.) Dann E::lund E::rsind die Kinder (nur E::lfür einen Lambda-Knoten), und E::iist der Lambda-Tiefenindex für einen variablen Blattknoten.
  • Der Konstruktor E::E(E&o,int d,int e)klont einen Teilausdruck, der sich ursprünglich in Lambda-Tiefe befand, dum ihn an einer neuen Position in Lambda-Tiefe einzufügen d+e. Dabei werden Variablen in Lambda-Tiefe weniger dbeibehalten als Variablen in Lambda-Tiefe mindestens dum inkrementiert e.
  • E::sführt eine Ersetzung des Unterausdrucks vin eine Variablennummer ddurch, *thiswährend Variablennummern dekrementiert werden, die größer sind als d(und eist ein internes Detail, das das Lambda-Tiefeninkrement nachverfolgt, wenn es aufgerufen werden muss E::c).
  • E::RSucht nach einer einzelnen Beta-Reduktion, die ausgeführt werden soll, und bevorzugt Instanzen ganz oben oder ganz links gemäß einer Suche in der AST vor der Bestellung. Es wird ein Wert ungleich Null zurückgegeben, wenn eine Leistungsreduzierung gefunden wurde, oder Null, wenn keine gefunden wurde.
  • E::uist eine to_stringTypoperation, die eine "vom Menschen lesbare" Zeichenfolge unter Verwendung von synthetischen Namen für die Variablen wiederherstellt. (Beachten Sie, dass die VHelferfunktion aufgrund des geringen Golfspiels nur Namen generiert, die adurch enthalten i.)
  • Der Konstruktor E::E(int d, std::map<std::string, int> m, char*&s)parst eine Eingabezeichenfolge sin einen Ausdruck AST auf der Grundlage einer Zuordnung mder aktuell gebundenen Variablennamen zu lambda-tiefen Indizes.
  • f ist die Hauptfunktion zur Beantwortung der Frage.

(Wie Sie am TIO-Link sehen können, verarbeitet der Code Variablennamen mit mehreren Zeichen und erhält auch die richtige Antwort von (\ a. (\ b. a))for ((\ f. (\ x. (f x))) (\ y. (\ x. y))). Es kommt auch nur so vor, dass der Parsing-Code das Spiegeln von Variablen ohne zusätzliche Kosten verarbeiten kann.)


-16 Bytes, teils aufgrund einer Idee von ceilingcat (die ich mir auch selbst ausgedacht hatte), teils aufgrund des Wechsels E*a=new E;zu E&a=*new E;und dann des Wechsels a->zua.

-8 weitere Bytes aufgrund eines weiteren Kommentars von ceilingcat (Zuweisung a.tvon ternary ausklammern )

-27 Bytes aus der Konvertierung von Parser und Klon in Konstruktoren von E

Daniel Schepler
quelle
-1

C 637 Bytes

#define R return
#define E if(i>=M||j>=M)R-1;
#define H d[j++]
enum{O=40,C,M=3999};signed char Q[M],D[M],t[M],Z,*o=Q,*d=D,*T;int m,n,s,c,w;K(i,j,k){!Z&&(Z=t[O]=1)+(t[C]=-1);E;if(!o[i]){H=0;R 0;}if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!=92){H=o[i++];R K(i,j,i);}for(i+=2,w=0;i<M&&o[i]&&c;++i)c+=t[o[i]],!w&&c==1?w=i:0;E;if(c){for(;H=o[i++];)E;R 0;}for(c=k+7,n=j;c<w&&j<M;++c)if(o[c]==o[k+4]){if(o[c+1]==46){d[n++]=o[k++];R K(k,n,k);}for(m=w+2;m<i-1&&j<M;)H=o[m++];}else H=o[c];E;Z=2;R K(i,j,i);}char*L(char*a){for(s=n=0;n<M&&(o[n]=a[n]);++n);if(n==M)R 0;for(;++s<M;){Z=0;if((n=K(0,0,0))!=-1&&Z==2)T=d,d=o,o=T;else break;}R n==-1||s>=M?0:d;}

Diese Version verwendet keine Hilfsvariablen (daher folgt dies nicht zu 100% dem, was die Lambda-Rechnung sagt ... wie viele andere hier ...). Jede Variable muss 1 Zeichen lang sein (wie einige andere hier). Testcode:

#define P printf

main()
{char  *r[]={ "((\\ x. x) z)", 
              "((\\ x. x) (\\ y. (\\ z. z)))", 
              "(\\ x. ((\\ y. y) x))", 
              "((\\ x. (\\ y. x)) (\\ a. a))", 
              "(((\\ x. (\\ y. x)) (\\ a. a)) (\\ b. b))",
              "((\\ x. (\\ y. y)) (\\ a. a))",
              "(((\\ x. (\\ y. y)) (\\ a. a)) (\\ b. b))",
              "((\\ x. (x x)) (\\ x. (x x)))",
              "(((\\ x. (\\ y. x)) (\\ a. a)) ((\\ x. (x x)) (\\ x. (x x))))",
              "((\\ a. (\\ b. (a (a (a b))))) (\\ c. (\\ d. (c (c d)))))",
              "((\\ f. (\\ x. (f x))) (\\ y. (\\ x. y)))",
             0}, *y;
 int    w;

 for(w=0; r[w] ;++w)
   {y=L(r[w]);
    P("o=%s d=%s\n", r[w], y==0?"Error ":y);
   }
 R  0;
}

Ergebnisse:

/*
637
o=((\ x. x) z) d=z
o=((\ x. x) (\ y. (\ z. z))) d=(\ y. (\ z. z))
o=(\ x. ((\ y. y) x)) d=(\ x. x)
o=((\ x. (\ y. x)) (\ a. a)) d=(\ y. (\ a. a))
o=(((\ x. (\ y. x)) (\ a. a)) (\ b. b)) d=(\ a. a)
o=((\ x. (\ y. y)) (\ a. a)) d=(\ y. y)
o=(((\ x. (\ y. y)) (\ a. a)) (\ b. b)) d=(\ b. b)
o=((\ x. (x x)) (\ x. (x x))) d=Error
o=(((\ x. (\ y. x)) (\ a. a)) ((\ x. (x x)) (\ x. (x x)))) d=(\ a. a)
o=((\ a. (\ b. (a (a (a b))))) (\ c. (\ d. (c (c d))))) d=(\ b. (\ d. (b (b (b (b (b (b (b (b d))))))))))
o=((\ f. (\ x. (f x))) (\ y. (\ x. y))) d=(\ x. (\ x. x))
*/

Dies ist der Semi-Ungolf:

#define R return
#define E if(i>=M||j>=M)R-1;
#define H d[j++]
enum{O=40,C,M=3999}; // assume ascii
signed char Q[M],D[M],t[M],Z,*o=Q,*d=D,*T;
int m,n,s,c,w;

K(i,j,k)
{!Z&&(Z=t[O]=1)+(t[C]=-1); //inizializza tabelle

 E;if(!o[i]){H=0;R 0;}
 if((c=t[o[i]]+t[o[i+1]])!=2||o[i+2]!=92)
      {H=o[i++]; R K(i,j,i);}
 for(i+=2,w=0;i<M&&o[i]&&c;++i)
         c+=t[o[i]],!w&&c==1?w=i:0;
 E;
 if(c){for(;H=o[i++];)E;R 0;} 
//  01234567w12 i
//  ((/ x. x) z)
//   x                 w              z
// o[k+4]..o[k+5];  o[k+7]..o[w];  o[w+2]..o[i-1]

// sostituzione
// sostituisce a x z in w e lo scrive in d
for(c=k+7,n=j;c<w&&j<M;++c)
      if(o[c]==o[k+4])
         {if(o[c+1]==46) // non puo' sostituire una variabile dove c'e' lambda
             {d[n++]=o[k++]; R K(k,n,k);}
          for(m=w+2;m<i-1&&j<M;++m)
                H=o[m];
         }
      else H=o[c];
 E;
 Z=2;
 R K(i,j,i);
}

char*L(char*a)
{for(s=n=0;n<M&&(o[n]=a[n]);++n);
 if(n==M)R 0;
 for(;++s<M;)
   {Z=0;
    n=K(0,0,0);
//    if(Z==2)printf("n=%d>%s\n", n, d);
    if(Z==2&&n!=-1)T=d,d=o,o=T;
    else break;
   }
 R n==-1||s>=M?0:d; 
}
RosLuP
quelle
Die Spezifikation verlangt \ oder λ, nicht /. Es erfordert auch die Unterstützung von Variablennamen mit mehreren Buchstaben. Zusätzlich (ich weiß, dass Sie sich dessen bewusst sind, aber es ist immer noch falsch), wertet dies falsch aus ((/ f. (/ X. (Fx))) (/ y. (/ X. Y))) bis ( / x. (/ x. x)).
Anders Kaseorg
Ich ändere / nach \ dort ist das Problem nicht erlaubt, dass mehrere Zeichen variabel sind. Wenn Sie andere testen, gilt dies auch für andere Lösungen
RosLuP