El desafío es escribir un intérprete para el cálculo lambda sin tipo en la menor cantidad de caracteres posible. Definimos el cálculo lambda sin tipo de la siguiente manera:

Sintaxis

Existen los siguientes tres tipos de expresiones:

• Una expresión lambda tiene la forma (λ x. e)donde xpodría ser cualquier nombre de variable legal y ecualquier expresión legal. Aquí xse llama parámetro y ese llama cuerpo de función.

  En aras de la simplicidad, agregamos la restricción adicional de que no debe haber una variable con el mismo nombre que xactualmente está en el alcance. Una variable comienza a estar dentro del alcance cuando su nombre aparece entre (λy .y deja de estar dentro del alcance en el correspondiente ).

• La aplicación de función tiene la forma (f a)donde fy ason expresiones legales. Aquí fse llama función y ase llama argumento.
• Una variable tiene la forma xdonde xes un nombre de variable legal.

Semántica

Una función se aplica reemplazando cada aparición del parámetro en el cuerpo de las funciones con su argumento. Más formalmente una expresión de la forma ((λ x. e) a), donde xes un nombre de variable y ey ason expresiones, evalúa (o reduce) la expresión e', donde e'es el resultado de reemplazar cada aparición de xen econ a.

Una forma normal es una expresión que no puede evaluarse más.

El reto

Su misión, si elige aceptarla, es escribir un intérprete que tome como entrada una expresión del cálculo lambda sin tipo que no contenga variables libres y produzca como salida la forma normal de la expresión (o una expresión alfa-congruente con ella) . Si la expresión no tiene forma normal o no es una expresión válida, el comportamiento es indefinido.

La solución con el menor número de caracteres gana.

Un par de notas:

• La entrada puede leerse desde stdin o desde un nombre de archivo dado como argumento de línea de comando (solo necesita implementar uno u otro, no ambos). La salida va a stdout.
• Alternativamente, puede definir una función que tome la entrada como una cadena y devuelva la salida como una cadena.
• Si los caracteres que no son ASCII son problemáticos para usted, puede usar el carácter de barra diagonal inversa ( \) en lugar de λ.
• Contamos el número de caracteres, no bytes, por lo que incluso si su archivo fuente está codificado como ico unicode cuenta como un carácter.
• Los nombres de variables legales consisten en una o más letras minúsculas, es decir, caracteres entre a y z (no es necesario admitir nombres alfanuméricos, letras mayúsculas o letras no latinas, aunque hacerlo no invalidará su solución, por supuesto).
• En lo que respecta a este desafío, no hay paréntesis opcionales. Cada expresión lambda y cada aplicación de función estarán rodeadas exactamente por un par de paréntesis. Ningún nombre de variable estará rodeado de paréntesis.
• Azúcar sintáctico como escribir (λ x y. e)para (λ x. (λ y. e))no necesita ser apoyada.
• Si se requiere una profundidad de recursión de más de 100 para evaluar una función, el comportamiento es indefinido. Eso debería ser más que lo suficientemente bajo como para implementarse sin optimización en todos los idiomas y aún lo suficientemente grande como para poder ejecutar la mayoría de las expresiones.
• También puede suponer que el espaciado será como en los ejemplos, es decir, sin espacios al principio y al final de la entrada o antes de λao .y exactamente un espacio después de ay .entre una función y su argumento y después de a λ.

Muestra de entrada y salida

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

  Salida: (λ y. (λ z. z))

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

  Salida: (λ x. x)

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

  Salida: (λ y. (λ a. a))

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

  Salida: (λ a. a)

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

  Salida: (λ y. y)

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

  Salida: (λ b. b)

• Entrada: ((λx. (x x)) (λx. (x x)))

  Salida: cualquier cosa (este es un ejemplo de una expresión que no tiene forma normal)

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

  Salida: (λ a. a)(Este es un ejemplo de una expresión que no se normaliza si evalúa los argumentos antes de la llamada a la función, y lamentablemente un ejemplo para el que falla mi intento de solución)

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

  Salida: `(λ a. (λ b. (a (a (a (a (a (a (a (a b)))))))))) Esto calcula 2 ^ 3 en números de la Iglesia.

El más nuevo:

Lo reduje a 644 caracteres , factoricé partes de cEll en Copy y Par; llamadas en caché a la celda y cdr en variables locales temporales, y movió esas variables locales a globales en funciones "terminales" (es decir, no recursivas). Además, las constantes decimales son más cortas que los literales de caracteres y este asunto desagradable ...

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

... identifica correctamente letras minúsculas (suponiendo ASCII), pero también acepta cualquiera de `{|} ~. (Esta misma observación sobre ASCII se hace en este excelente video sobre UTF-8 ).

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

Más temprano:

¿Puedo obtener algunos votos por esfuerzo? He estado trabajando en esto día y noche durante una semana. Saqué el artículo original de McCarthy y tuve una plaga de insectos en el periódico hasta que leí el apéndice de Las raíces de Lisp de Paul Graham . Estaba tan distraído que me encerré fuera de mi casa, luego me olvidé por completo hasta llegar a casa esa noche a las 12:30 (un poco tarde para llamar al administrador del edificio que vive en el condado), y tuve que pasar el tiempo noche en casa de mi abuela (cortando hasta que la batería de mi portátil estaba seca)

Y después de todo eso, ¡ni siquiera está cerca de la entrada ganadora!

No estoy seguro de cómo hacer esto más corto; ¡Y he usado todos los trucos sucios que se me ocurren! Quizás no se pueda hacer en C.

Con algo de generosidad en el conteo (el primer fragmento toma una secuencia e imprime el resultado), son 778 770 709 694 caracteres. Pero para que sea independiente, tiene que tener esa sbrkllamada. Y para manejar expresiones más complicadas, también necesita el signalcontrolador. Y, por supuesto, no se puede convertir en un módulo con ningún código que intente usar malloc.

Entonces, por desgracia, aquí está:

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

Aquí está el bloque justo antes de las reducciones finales. Los trucos aquí son cursores enteros en lugar de punteros (aprovechando el comportamiento 'implícito int') y el uso de 'memoria de memoria virtual': char*nes el puntero 'nuevo' o 'próximo' en el espacio libre. Pero a veces escribo una cadena en la memoria, luego llamo a strlen e incremento n; usando efectivamente la memoria y luego asignándola, después de que el tamaño sea más fácil de calcular. Puede ver que es bastante directo del documento de McCarthy, con la excepción de cell()qué interfaces entre las funciones y la representación de datos en cadena.

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

Cálculo Lambda Binario 186

El programa que se muestra en el volcado hexadecimal a continuación

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

no acepta el formato que propones. Más bien, espera un término lambda en formato binario de cálculo lambda (blc). Sin embargo, muestra cada paso en la reducción de forma normal, usando paréntesis mínimos.

Ejemplo: calcular 2 ^ 3 en números de la Iglesia

Guarde el volcado hexadecimal anterior con xxd -r> symbolic.Blc

Tome un intérprete blc de 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)))))))

Como el hexdump es bastante ilegible, aquí hay una versión "desmontada"

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

reemplazando 00 (lambda) con \ y 01 (aplicación) con @ Ahora es casi tan legible como brainfuck :-)

Ver también http://www.ioccc.org/2012/tromp/hint.html

Haskell, 342 323 317 305 caracteres

Al momento de escribir este artículo, esta es la única solución que evalúa ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))) al resultado correcto (λ x. (Λ z. x)) en lugar de (λ x. (λ x. x)). La implementación correcta del cálculo lambda requiere una sustitución que evite la captura , incluso bajo la garantía simplificadora de este problema de que ninguna variable sombrea a otra variable en su alcance. (Mi programa funciona incluso sin esta garantía).

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"++))

Notas:

• Esto se ejecuta en GHC 7.0, como se requiere porque este desafío se estableció en enero de 2011. Sería 13 caracteres más corto si se me permitiera asumir GHC 7.10.

Versión sin golf con documentación.

Python - 321 320

Aquí está mi intento (fijo):

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

Ruby 254 caracteres

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}

Se puede usar como

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

La solución aún no está totalmente desarrollada, pero ya es casi ilegible.

Editar: verifique mi respuesta a continuación para 250 bajo JavaScript puro.

2852 243 caracteres usando LiveScript (¡No Regex! No completamente golfizado - podría mejorarse)

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

Prueba:

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

Que es 3^2=9, como se indica en OP.

Si alguien tiene curiosidad, aquí hay una versión extendida con algunos comentarios:

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

Waterhouse Arc - 140 caracteres

(=
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 #\._])

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

Las variables permiten como entrada usando letras minúsculas [de a..z] el sistema puede generar variables usando letras mayúsculas [de A..Z] si es necesario en la salida ... Asumir la configuración de caracteres 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*/

Haskell 456 C

Puede ser mucho más corto si la característica de evaluación perezosa de Haskell se utiliza por completo. Lamentablemente, no sé cómo hacerlo.

Además, se desperdician muchos caracteres en el paso de análisis.

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

Versión sin golf

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

Obtuve 231 con 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})

Recibe matrices de 2 elementos. 1representa λy 2 representa una variable de índice bruijn.

Prueba:

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

Python: 1266 caracteres (medidos con 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()))

No es el más corto por mucho, pero maneja correctamente el cambio de nombre alfa y todos los ejemplos enumerados en la publicación de OP.

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

Pruébalo en línea!

La idea básica aquí es que el código usa una representación interna basada en la idea de los índices de Bruijn , excepto que invierto los índices para indicar la profundidad lambda de la unión de la variable referida. En el codigo:

• E::trepresenta el tipo de nodo: 0 para un nodo hoja variable, 1 para un nodo lambda y 2 para un nodo de aplicación de función. (Elegido para que coincida con la aridad del nodo, que es posible.) Entonces, E::ly E::rson los hijos según corresponda (solo E::lpara un nodo lambda), y E::ies el índice de profundidad lambda para un nodo de hoja variable.
• El constructor E::E(E&o,int d,int e)clona una subexpresión que inicialmente estaba en profundidad lambda dpara pegarla en una nueva ubicación en profundidad lambda d+e. Esto implica preservar las variables en la profundidad lambda menos que dal incrementar las variables en la profundidad lambda al menos den e.
• E::shace una sustitución de la subexpresión ven número variable den *thismientras decrementar un número variable mayor que d(y ees un detalle interno de seguimiento el incremento lambda profundidad para cuando se necesita a la llamada E::c).
• E::Rbusca una única reducción beta para realizar, prefiriendo las instancias más altas o más izquierdas de acuerdo con una búsqueda previa a través del AST. Devuelve un valor distinto de cero si encuentra una reducción para realizar o cero si no encuentra ninguna.
• E::ues una to_stringoperación de tipo que reconstituye una cadena "legible para humanos" usando nombres sintéticos para las variables. (Tenga en cuenta que debido a un poco de golf de la Vfunción auxiliar que sólo generará nombres que contiene através i.)
• El constructor E::E(int d, std::map<std::string, int> m, char*&s)analiza una cadena de entrada sen una expresión AST basada en una asignación mde nombres de variables actualmente vinculados a índices de profundidad lambda.
• f es la función principal que responde la pregunta.

(Como puede ver en el enlace TIO, el código maneja nombres de variables con múltiples caracteres, y también obtiene una respuesta correcta de (\ a. (\ b. a))for ((\ f. (\ x. (f x))) (\ y. (\ x. y))). También sucede que el código de análisis puede manejar el sombreado de variables sin costo adicional).

-16 bytes en parte debido a la idea de ceilingcat (que también había llegado con forma independiente), y en parte debido a los cambios E*a=new E;a E&a=*new E;y luego cambiar a->aa.

-8 bytes más debido a otro comentario de ceilingcat (factorizar la asignación de a.tdesde ternary)

-27 bytes de convertir el analizador y el clon en constructores de E

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

Esta versión no utiliza variables auxiliares (por lo que esto no sigue al 100% lo que dice el cálculo lambda ... como muchos otros aquí ...). Cada variable debe tener una longitud de 1 carácter (como alguna otra aquí). Código de prueba:

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

resultados:

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

este es el 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; 
}