Écrire un interprète pour le calcul lambda non typé

45

Le défi consiste à écrire un interprète pour le calcul lambda non typé dans le moins de caractères possible. Nous définissons le calcul lambda non typé comme suit:

Syntaxe

Il existe trois types d'expressions:

  • Une expression lambda a la forme (λ x. e)xpourrait être n'importe quel nom de variable juridique et etoute expression juridique. Ici xs'appelle le paramètre et es'appelle le corps de la fonction.

    Par souci de simplicité, nous ajoutons la restriction supplémentaire selon laquelle il ne doit pas y avoir de variable portant le même nom que celle xactuellement dans la portée. Une variable commence à se trouver dans la portée lorsque son nom apparaît entre et .et cesse de se trouver dans la portée correspondante ).

  • L'application de fonction a la forme (f a)fet asont des expressions juridiques. Ici fs'appelle la fonction et as'appelle l'argument.
  • Une variable a la forme xxest un nom de variable légal.

Sémantique

Une fonction est appliquée en remplaçant chaque occurrence du paramètre dans le corps de la fonction par son argument. Plus formellement, une expression de la forme ((λ x. e) a), où xest un nom de variable et eet asont des expressions, est évaluée (ou réduite) à l'expression e'e'est le résultat du remplacement de chaque occurrence de xin epar a.

Une forme normale est une expression qui ne peut plus être évaluée.

Le défi

Votre mission, si vous l'acceptez, est d'écrire un interpréteur qui prend en entrée une expression du calcul lambda non typé ne contenant aucune variable libre et produit en sortie la forme normale de l'expression (ou une expression qui lui correspond parfaitement) . Si l'expression n'a pas de forme normale ou s'il ne s'agit pas d'une expression valide, le comportement n'est pas défini.

La solution avec le plus petit nombre de caractères gagne.

Quelques notes:

  • Les entrées peuvent être lues à partir de stdin ou d'un nom de fichier donné en argument de ligne de commande (vous devez uniquement implémenter l'un ou l'autre, pas les deux). La sortie passe à stdout.
  • Vous pouvez également définir une fonction qui prend l’entrée sous forme de chaîne et renvoie le résultat sous forme de chaîne.
  • Si les caractères non-ASCII vous posent problème, vous pouvez utiliser le caractère barre oblique inverse ( \) au lieu de λ.
  • Nous comptons le nombre de caractères, pas d'octets, donc même si votre fichier source est codé sous la forme d'unicode, λ compte pour un caractère.
  • Les noms de variables légales consistent en une ou plusieurs lettres minuscules, c'est-à-dire des caractères compris entre a et z (inutile de prendre en charge les noms alphanumériques, les majuscules ou les lettres non latines - bien que cela n'invalidera pas votre solution, bien sûr).
  • En ce qui concerne ce défi, aucune parenthèse n'est optionnelle. Chaque expression lambda et chaque application de fonction seront entourées d’exactement une paire de parenthèses. Aucun nom de variable ne sera entouré de parenthèses.
  • Le sucre syntaxique comme écrire (λ x y. e)pour (λ x. (λ y. e))n'a pas besoin d'être soutenu.
  • Si une profondeur de récursivité supérieure à 100 est requise pour évaluer une fonction, le comportement n'est pas défini. Cela devrait être plus que suffisamment bas pour être implémenté sans optimisation dans toutes les langues et toujours assez grand pour pouvoir exécuter la plupart des expressions.
  • Vous pouvez également supposer que l'espacement sera comme dans les exemples, c'est-à-dire pas d'espaces au début et à la fin de l'entrée ou avant un λou .et exactement un espace après un .et entre une fonction et son argument et après un λ.

Exemple d'entrée et de sortie

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

    Sortie: (λ y. (λ z. z))

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

    Sortie: (λ x. x)

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

    Sortie: (λ y. (λ a. a))

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

    Sortie: (λ a. a)

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

    Sortie: (λ y. y)

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

    Sortie: (λ b. b)

  • Contribution: ((λx. (x x)) (λx. (x x)))

    Sortie: n'importe quoi (Ceci est un exemple d'expression qui n'a pas de forme normale)

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

    Résultat: (λ a. a)(Ceci est un exemple d'expression qui ne se normalise pas si vous évaluez les arguments avant l'appel de la fonction et, malheureusement, un exemple pour lequel ma tentative de solution a échoué.)

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

    Sortie: `(λ a. (λ b. (a (a (a (a (a (a (a (a b)))))))))) Ceci calcule 2 ^ 3 en chiffres d'église.

sepp2k
la source
1
Pouvons-nous supposer qu’il n’y aura pas d’espace ajouté ou ajouté à la chaîne et que l’espace est comme spécifié dans l’exemple d’entrée? C'est-à-dire qu'aucun espace entre crochets, entre le point et le nom du paramètre et les autres instances d'espaces ne correspondent exactement à 1 espace.
JPvdMerwe le
@JPvdMerwe: Oui, bon point, vous pouvez en déduire.
sepp2k le
Y a-t-il des variables libres? Je veux dire des variables non liées par un lambda comme dans l'expression (\y. a).
FUZxxl
3
Beaucoup de solutions, voire toutes, ne parviennent pas à implémenter une substitution évitant la capture! Vous devez ajouter un scénario de test tel que ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))), qui devrait correspondre à (λ x. (Λ z. X)), non (λ x. (λ x. x)).
Anders Kaseorg
1
@ sepp2k Avez-vous envisagé d'ajouter ((λ f. (λ x. (fx))) (λ y. (λ x. y))) comme scénario de test et d'annuler la réponse actuelle qui produit incorrectement (λ x. (λ x. x))?
Anders Kaseorg

Réponses:

36

Le plus récent:

Je l'ai réduit à 644 caractères , j'ai factorisé des parties de cEll dans cOpy et Par; Mise en cache des appels à cell et cdr dans des variables locales temporaires et déplacement de ces variables locales vers des globales dans des fonctions "terminal" (c'est-à-dire non récursives). En outre, les constantes décimales sont plus courtes que les littéraux de caractères et cette mauvaise affaire ...

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

... identifie correctement les lettres minuscules (en supposant que ASCII), mais accepte également n'importe lequel des `{|} ~. (Cette même observation à propos d'ASCII est faite dans cette excellente vidéo sur UTF-8 .)

Et alto: |

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

Plus tôt:

Puis-je obtenir quelques votes pour l'effort? Je travaille ce jour et cette nuit depuis une semaine. J'ai extrait le papier original de McCarthy et j'ai été affecté par un bug dans le papier lui-même jusqu'à ce que je lise l'annexe de The Roots of Lisp de Paul Graham . J'étais tellement distraite que je me suis enfermée à l'extérieur de ma maison, puis complètement oubliée jusqu'à mon retour à la maison ce soir-là à 12 h 30 (un peu tard pour appeler le gérant de l'immeuble qui vit très loin dans le comté) et j'ai dû passer le nuit chez ma grand-mère (piratage jusqu’à ce que la batterie de mon ordinateur portable soit sèche).

Et après tout cela, ce n'est même pas proche de l'entrée gagnante!

Je ne suis pas sûr de savoir comment rendre cela plus court; et j'ai utilisé tous les sales tours auxquels je peux penser! Peut-être que cela ne peut pas être fait en C.

Avec une certaine générosité dans le comptage (le premier morceau prend une chaîne et affiche le résultat), il s'agit de 778 770 709 694 caractères. Mais pour le rendre autonome, il doit avoir cet sbrkappel. Et pour gérer des expressions plus complexes, il a également besoin du signalgestionnaire. Et bien sûr, il ne peut pas être transformé en un module avec un code qui tente de l'utiliser malloc.

Alors, hélas, la voici:

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

Voici le bloc juste avant les dernières réductions. Les astuces ici sont des curseurs de nombre entier au lieu de pointeurs (tirant parti du comportement "implicite") et de l'utilisation de "mémoire de travail": il char*ns'agit du pointeur "nouveau" ou "suivant" dans l'espace libre. Mais parfois, j'écris une chaîne dans la mémoire, puis j'appelle strlen et incrémente n; en utilisant efficacement la mémoire, puis en l' attribuant, il est plus facile de calculer la taille. Vous pouvez voir que c'est assez directement du papier McCarthy, à l'exception des cell()interfaces entre les fonctions et la représentation sous forme de chaîne de données.

#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
la source
1
J'ai trouvé quelques astuces supplémentaires pour sauver un personnage ou deux, mais rien de radical. sprintf(n,...);n+=strlen(n)+1;est préférable car n+=sprintf(n,...)+1;Inverser la syntaxe du tableau x[m]au lieu de m[x]me permettre de remplacer tous les indirections par une macro 'postfixe' #define M [m]... x Mqui enregistre 1 caractère et donne un retour à la ligne "libre" car un espace est nécessaire pour séparer les jetons.
Luser droog
Il semble y avoir quelques similitudes avec this et jar.2 xlisp 4.0 de IOCCC 1989 .
luser droog
J'ai essayé de développer cela en un interpréteur Lisp plus complet .
Luser droog
Le code commenté // um ...parcourt la chaîne et compte entre parenthèses jusqu'à ce qu'il trouve la parence proche correspondante au niveau d'imbrication correct.
luser droog
1
Cela évalue incorrectement ((\ f. (\ X. (Fx))) (\ y. (\ X. Y))) à (\ x. (Fx)).
Anders Kaseorg
22

Lambda Calcul binaire 186

Le programme affiché dans le vidage hexadécimal ci-dessous

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

n'accepte pas tout à fait le format que vous proposez. Au contraire, il attend un terme lambda au format binaire lambda calcul (blc). Cependant, il montre chaque étape de la réduction de la forme normale, en utilisant des parenthèses minimales.

Exemple: calculer 2 ^ 3 en chiffres d'église

Enregistrez le vidage hexadécimal ci-dessus avec xxd -r> symbolic.Blc

Prenez un interpréteur blc depuis 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)))))))

Puisque l'hexdump est assez illisible, voici une version "désassemblée"

@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\
@

remplacer 00 (lambda) par \ et 01 (application) par @ Maintenant, il est presque aussi lisible que brainfuck :-)

Voir aussi http://www.ioccc.org/2012/tromp/hint.html

John Tromp
la source
7
Il se trouve que BLC utilise un alphabet binaire. 00 est lambda, 01 est l'application et 1 ^ {n} 0 est une variable unaire. Il n'y a pas de compilation impliquée.
John Tromp
3
Où obtenez-vous un facteur x3? En fait, vous soulevez un bon point dans les langues où les alphabets sources plus petits comme BF sont pénalisés. Pour une comparaison équitable, toutes les tailles doivent être exprimées en bits et les caractères BF ne prennent que 3 bits chacun. La plupart des autres langues nécessitent 7 bits en ASCII, certaines utilisent les 8.
John Tromp
1
BTW +1 C'est sacrément cool!
luser droog
1
Si fractran in fractran est acceptable, je ne vois pas pourquoi cela poserait un problème du tout. Vous ne pouvez pas le lire? Tu veux? Apprendre!
luser droog
1
Que faudrait-il pour lui faire lire le format d'entrée actuel? Je pense que c'est là que vous perdez des upvotes potentiels.
luser droog
14

Haskell, 342 323 317 305 caractères

Au moment d'écrire ces lignes, c'est la seule solution qui évalue ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))) au résultat correct (λ x. (Λ z. x)) plutôt que (λ x. (λ x. x)). La mise en œuvre correcte du lambda calcul nécessite une substitution sans capture , même avec la garantie de simplification de ce problème qu'aucune variable ne masque une autre variable dans son étendue. (Mon programme fonctionne même sans cette 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"++))

Remarques:

  • Cela fonctionne dans GHC 7.0, comme requis, car ce défi a été défini en janvier 2011. Il serait plus court de 13 caractères si je pouvais assumer GHC 7.10.

Version non-golfée avec documentation.

Anders Kaseorg
la source
votre prog dans ideone haskell compilateur à l’entrée ((\ x. x) (\ y. (\ z. z))) renvoie "une erreur d’exécution" même dans ((\\ x. x) (\\ y. ( \\ z. z))) ... que signifie "lex" en Haskell?
RosLuP
2
@RosLuP Mon programme accepte λ, pas \.
Anders Kaseorg
tapez cette entrée ((λ x. x) (λ y. (λ z. z))) dans ideone.com return: time time error: 0 memory: 4876 signal: -1
RosLuP
1
@RosLuP Ideone semble avoir cassé le support Unicode. Essayez la ligne de commande ou un autre interpréteur en ligne (cela fonctionne sur Rextester , par exemple).
Anders Kaseorg
2
@codeshot L'auteur de la question a déjà commenté que ((λ f. (λ x. (fx))) (λ y. (λ x. y))) (λ x. (λ z. x)) est correct pour ce problème (tout comme le vrai calcul lambda).
Anders Kaseorg
13

Python - 321 320

Voici ma tentative (corrigée):

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
la source
Cela a l'air bien, mais ne semble pas fonctionner. J'ai ajouté quelques exemples d'entrées et de sorties pour lesquelles votre code produit des résultats erronés.
sepp2k le
1
Cela ne permet pas de faire une substitution en évitant la capture. Par exemple, ((\ f. (\ X. (Fx))) (\ y. (\ X. Y))) n'évalue pas correctement (\ x. (\ X. X)).
Anders Kaseorg
1
Pourquoi est-ce marqué comme une réponse alors que cela fonctionne à peine? Avez-vous essayé les entrées et les sorties données par l'auteur?
rbaleksandar
1
Les cas de test fournis par l'auteur sont insuffisants pour démontrer les bugs dans cette réponse.
Anders Kaseorg
1
Cette réponse n'est ni correcte ni la plus courte. Il ne parvient pas à éviter la capture et présente des bogues de substitution de chaînes.
Richard Padley
6

Ruby 254 personnages

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}

Il peut être utilisé comme

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

La solution n’est pas encore totalement jouée au golf mais déjà presque illisible.

Howard
la source
bonjour l'envie, mon vieil ami :)
luser droog
Cela ne permet pas de faire une substitution en évitant la capture Par exemple, ((\ f. (\ X. (Fx))) (\ y. (\ X. Y))) n'évalue pas correctement (\ x. (\ X. X)).
Anders Kaseorg
En plus du bogue de capture ci-dessus, ceci évalue également incorrectement (\ y. (\ Xx. ((X. Xx) y))) à (\ y. (\ Xx. Yy)), où la substitution de chaînes trop zélée a fabriqué la variable inexistante yy.
Anders Kaseorg
3

Edit: vérifiez ma réponse ci-dessous pour 250 sous JavaScript pur.

2852 243 caractères utilisant LiveScript (Pas de Regex! Pas complètement joué au golf - pourrait être amélioré)

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

Tester:

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

Ce qui est 3^2=9, comme indiqué sur OP.

Si quelqu'un est curieux, voici une version étendue avec quelques commentaires:

# 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
la source
Cela ne correspond pas aux spécifications d'entrée et de sortie du problème.
Anders Kaseorg
3

Waterhouse Arc - 140 personnages

(=
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 #\._])
chauffé
la source
Où puis-je obtenir Waterhouse Arc?
Anders Kaseorg
1
Invalide car un interprète est introuvable
Cat
@AndersKaseorg ici
ASCII seulement
@ ASCII-only, je sais ce qu’est Arc, mais la partie «Waterhouse» m’a suggéré la nécessité d’un dialecte particulier. L'avez-vous eu à courir?
Anders Kaseorg
@ AndersKaseorg Peu importe. Je l'ai trouvé
ASCII seulement
2

C 1039 octets

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

Les variables permettent une entrée utilisant des lettres minuscules [de a..z]. Le système peut générer des variables avec des lettres majuscules [de A..Z] si nécessaire dans la sortie ... Supposons la configuration de caractères ascii.

#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
la source
La spécification nécessite \ ou λ, pas /. Il nécessite également la prise en charge des noms de variables multi-lettres.
Anders Kaseorg
Le symbole '\ n' etc '\' a d'autres utilisations qu'il vaut mieux utiliser '/' à la place
RosLuP
1
Néanmoins, le défi consiste à satisfaire aux spécifications et non à les améliorer.
Anders Kaseorg
J'ai écrit quelque chose pour être un peu plus conforme ... mais la taille explose ...
RosLuP
1
932 octets
ceilingcat le
1

Haskell 456 C

Cela peut être beaucoup plus court si la fonctionnalité d'évaluation paresseuse de Haskell est pleinement utilisée. Malheureusement, je ne sais pas comment faire.

En outre, de nombreux caractères sont perdus lors de l’analyse.

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

Version non-golfée

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
Rayon
la source
3
Cela ne permet pas de faire une substitution en évitant la capture Par exemple, ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))) est évalué de manière incorrecte à (λ x. (Λ x. X)).
Anders Kaseorg
1

Vous avez 231 avec JavaScript / no 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})

Reçoit des tableaux à 2 éléments. 1représente λ2 et correspond à une variable d'index de Bruijn.

Tester:

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
la source
Cela ne correspond pas aux spécifications d'entrée et de sortie du problème.
Anders Kaseorg
1

Python: 1266 caractères (mesurés avec 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()))

Pas le plus court de loin, mais il gère correctement le renommage alpha et tous les exemples énumérés dans les PO post.

Björn Lindqvist
la source
Vous pouvez raccourcir certains de ces noms de fonctions et en transformer certains en lambdas. Vous avez également des excès de blancs ici et là
Jo King
(1) Remplacer l'indentation de 4 espaces par un seul espace économisera pas mal d'octets. (2) Pouvez-vous remplacer except NameErrorpar juste except? (3) Les noms de fonction à deux caractères peuvent être renommés en noms à un caractère. (4) Il existe quelques endroits où vous avez des tâches qui ont des espaces autour du =. (5) if t[0]=='c'peut être remplacé par if'c'==t[0].
Esolanging Fruit
1045 octets, principalement par des modifications de formatage telles que l'indentation et les lambdas
Jo King
0

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

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

Essayez-le en ligne!

L'idée de base est que le code utilise une représentation interne basée sur l'idée des indices de Bruijn - sauf que j'inverse les indices pour indiquer la profondeur lambda de la liaison de la variable mentionnée. Dans le code:

  • E::treprésente le type d'un nœud - 0 pour un nœud feuille variable, 1 pour un nœud lambda et 2 pour un nœud d'application de fonction. (Choisi de manière à ce qu'il coïncide avec l'arité du nœud, ce qui est tout à fait possible.) Ensuite E::l, E::rles enfants sont appropriés ( E::lpour un nœud lambda uniquement ) et E::iconstitue l'indice de profondeur lambda d'un nœud feuille variable.
  • Le constructeur E::E(E&o,int d,int e)clone une sous-expression qui était initialement à la profondeur lambda dpour pouvoir être collée dans un nouvel emplacement à la profondeur lambda d+e. Cela implique la préservation des variables à la lambda-profondeur inférieure dtout en incrémentant variables à lambda profondeur au moins dpar e.
  • E::seffectue une substitution de la sous-expression ven nombre variable den *thisdécrémentant les nombres variables supérieurs à d(et eest un détail interne suivi de l'incrément de profondeur lambda pour le moment où il doit appeler E::c).
  • E::Rrecherche une seule réduction bêta à effectuer, en préférant les instances les plus en haut ou les plus à gauche selon une recherche en pré-commande via l'AST. Il renvoie une valeur différente de zéro s'il trouve une réduction à effectuer ou zéro si aucune.
  • E::uest une to_stringopération de type qui reconstitue une chaîne "lisible par l'homme" en utilisant des noms synthétiques pour les variables. (Notez que à cause d'un petit golf de la Vfonction d'aide , il ne générer des noms contenant apar i.)
  • Le constructeur E::E(int d, std::map<std::string, int> m, char*&s)analyse une chaîne d'entrée sen une expression AST basée sur un mappage mdes noms de variable actuellement liés en indices lambda-depth.
  • f est la fonction principale qui répond à la question.

(Comme vous pouvez le constater sur le lien TIO, le code gère les noms de variables avec plusieurs caractères et obtient également une réponse correcte de (\ a. (\ b. a))pour ((\ f. (\ x. (f x))) (\ y. (\ x. y))). Il arrive également que le code d'analyse puisse gérer l'ombrage des variables sans coût supplémentaire.)


-16 octets en partie due à idée par ceilingcat (que j'étais venu aussi avec indépendamment), et en partie en raison du changement E*a=new E;de E&a=*new E;puis changer a->àa.

-8 octets supplémentaires dus à un autre commentaire de ceilingcat (factor out assignation a.tfrom from ternary)

-27 octets provenant de la conversion de l’analyseur et du clone en constructeurs de E

Daniel Schepler
la source
-1

C 637 octets

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

Cette version n'utilise pas de variables auxiliaires (donc cela ne suit pas à 100% ce que dit le lambda calcul ... comme beaucoup d'autres ici ...). Chaque variable doit avoir une longueur de 1 caractère (comme certaines autres ici). Code de test:

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

résultats:

/*
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))
*/

c'est le 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
la source
La spécification nécessite \ ou λ, pas /. Il nécessite également la prise en charge des noms de variables multi-lettres. De plus (je sais que vous en êtes conscient, mais oui, c'est toujours faux), ceci évalue incorrectement ((/ f. (/ X. (Fx))) (/ y. (/ X. Y))) à ( / x. (/ x. x)).
Anders Kaseorg
Je change / en \ il y a le problème n'autorise pas la variable multi caractères. si vous testez un autre, c'est aussi pour une autre solution
RosLuP