O desafio é escrever um intérprete para o cálculo lambda não digitado com o mínimo de caracteres possível. Definimos o cálculo lambda sem tipo da seguinte maneira:

Sintaxe

Existem os três tipos de expressões a seguir:

• Uma expressão lambda tem o formato (λ x. e)onde xpode haver qualquer nome de variável legal e equalquer expressão legal. Aqui xé chamado de parâmetro e eé chamado de corpo da função.

  Por uma questão de simplicidade, adicionamos a restrição adicional de que não deve haver uma variável com o mesmo nome que xatualmente no escopo. Uma variável começa a estar no escopo quando seu nome aparece entre (λe .e para no escopo correspondente ).

• O aplicativo de funções tem a forma (f a)onde fe asão expressões legais. Aqui fé chamado de função e aé chamado de argumento.
• Uma variável tem o formato em xque xé um nome de variável legal.

Semântica

Uma função é aplicada substituindo cada ocorrência do parâmetro no corpo das funções por seu argumento. Mais formalmente uma expressão da forma ((λ x. e) a), em que xé um nome da variável e ee asão expressões, avalia (ou reduz) para a expressão e'em que e'é o resultado da substituição de cada ocorrência de xem ecom a.

Uma forma normal é uma expressão que não pode ser avaliada mais.

O desafio

Sua missão, se você optar por aceitá-la, é escrever um intérprete que tenha como entrada uma expressão do cálculo lambda não digitado que não contém variáveis ​​livres e produz como saída a forma normal da expressão (ou uma expressão alfa-congruente a ela) . Se a expressão não tiver uma forma normal ou não for uma expressão válida, o comportamento será indefinido.

A solução com o menor número de caracteres vence.

Algumas notas:

• A entrada pode ser lida a partir de stdin ou de um nome de arquivo fornecido como argumento de linha de comando (você só precisa implementar um ou outro - e não ambos). A saída vai para stdout.
• Como alternativa, você pode definir uma função que recebe a entrada como uma string e retorna a saída como uma string.
• Se caracteres não ASCII forem problemáticos para você, você poderá usar o \caractere barra invertida ( ) em vez de λ.
• Contamos o número de caracteres, não bytes, portanto, mesmo que seu arquivo de origem seja codificado como unicode, λ conta como um caractere.
• Os nomes de variáveis ​​legais consistem em uma ou mais letras minúsculas, ou seja, caracteres entre a e z (não é necessário suportar nomes alfanuméricos, maiúsculas ou letras não latinas - embora isso não invalide sua solução, é claro).
• No que diz respeito a esse desafio, nenhum parênteses é opcional. Cada expressão lambda e cada aplicativo de função serão cercados por exatamente um par de parênteses. Nenhum nome de variável estará entre parênteses.
• Açúcar sintático como escrever (λ x y. e)para (λ x. (λ y. e))não precisa ser suportado.
• Se uma profundidade de recursão superior a 100 for necessária para avaliar uma função, o comportamento será indefinido. Isso deve ser mais do que baixo o suficiente para ser implementado sem otimização em todos os idiomas e ainda grande o suficiente para poder executar a maioria das expressões.
• Você também pode assumir que o espaçamento será como nos exemplos, ou seja, não há espaços no início e no final da entrada ou antes de um λou .e exatamente um espaço após ae .entre uma função e seu argumento e após a λ.

Entrada e Saída de Amostra

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

  Resultado: (λ y. (λ z. z))

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

  Resultado: (λ x. x)

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

  Resultado: (λ y. (λ a. a))

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

  Resultado: (λ a. a)

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

  Resultado: (λ y. y)

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

  Resultado: (λ b. b)

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

  Saída: qualquer coisa (este é um exemplo de expressão que não possui forma normal)

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

  Saída: (λ a. a)(este é um exemplo de expressão que não se normaliza se você avaliar os argumentos antes da chamada da função e, infelizmente, um exemplo para o qual minha tentativa de solução falha)

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

  Saída: `(λ a. (λ b. (a (a (a (a (a (a (a (a b)))))))))) Calcula 2 ^ 3 em numerais da igreja.

O mais novo:

Aumentei para 644 caracteres , considerei partes de cEll em cOpy e Par; chamadas armazenadas em cache para célula e cdr em variáveis ​​locais temporárias e movidas essas variáveis ​​locais para globais em funções "terminais" (isto é, não recursivas). Além disso, constantes decimais são mais curtas que literais de caracteres e esse negócio desagradável ...

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

... identifica corretamente letras minúsculas (assumindo ASCII), mas também aceita qualquer um dos caracteres `{|} ~. (Essa mesma observação sobre ASCII é feita neste excelente vídeo 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;}

Anteriormente:

Posso obter alguns votos por esforço? Estou trabalhando dia e noite há uma semana. Desenterrei o artigo original de McCarthy e fui atormentado por um inseto no próprio artigo até ler o apêndice de The Roots of Lisp, de Paul Graham . Fiquei tão distraído que me tranquei fora da minha casa, depois esqueci completamente até chegar em casa novamente às 12:30 (um pouco tarde para ligar para o gerente do prédio que mora no condado) e tive que passar o tempo. noite na casa da minha avó (cortando até que a bateria do meu laptop estivesse seca).

E depois de tudo isso, não é nem perto da entrada vencedora!

Não sei como diminuir isso; e usei todos os truques sujos que consigo imaginar! Talvez não possa ser feito em C.

Com alguma generosidade na contagem (o primeiro pedaço pega uma corda e imprime o resultado), são 778 770 709 694 caracteres. Mas, para torná-lo independente, é preciso ter essa sbrkligação. E para lidar com expressões mais complicadas, ele também precisa do signalmanipulador. E é claro que não pode ser transformado em um módulo com qualquer código que tente usar malloc.

Então, infelizmente, aqui 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;
}

Aqui está o bloco antes das reduções finais. Os truques aqui são cursores inteiros em vez de ponteiros (aproveitando o comportamento 'implícito') e o uso de 'memória temporária': o char*né o ponteiro 'novo' ou 'próximo' no espaço livre. Mas, às vezes, escrevo uma string na memória, depois chamo strlen e incrementamos n; efetivamente usando memória e , em seguida, alocá-lo, após o tamanho é mais fácil de calcular. Você pode ver que é praticamente direto do artigo de McCarthy, com exceção de cell()quais interfaces entre as funções e a representação de strings dos dados.

#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 binário Lambda 186

O programa mostrado no dump hexadecimal abaixo

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ão aceita exatamente o formato que você propõe. Em vez disso, espera um termo lambda no formato binário lambda calculus (blc). No entanto, ele mostra todas as etapas na redução da forma normal, usando parênteses mínimos.

Exemplo: computando 2 ^ 3 em numerais da igreja

Salve o dump hexadecimal acima com xxd -r> symbolic.Blc

Pegue um intérprete do blc em 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 o hexdump é bastante ilegível, aqui está uma versão "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\
@

substituindo 00 (lambda) por \ e 01 (aplicativo) por @ Agora é quase tão legível quanto brainfuck :-)

Veja também http://www.ioccc.org/2012/tromp/hint.html

Haskell, 342 323 317 305 caracteres

Até o momento em que este artigo foi escrito, essa é a única solução que avalia ((λ f. (Λ x. (Fx))) (λ y. (Λ x. Y))) para o resultado correto (λ x. (Λ z. x)) em vez de (λ x. (λ x. x)). A implementação correta do cálculo lambda requer substituição para evitar capturas , mesmo com a garantia simplificadora desse problema de que nenhuma variável oculta outra variável em seu escopo. (Meu programa funciona mesmo sem essa garantia.)

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:

• Isso é executado no GHC 7.0, conforme necessário, porque esse desafio foi definido em janeiro de 2011. Seria 13 caracteres menor se eu fosse autorizado a assumir o GHC 7.10.

Versão ungolfed com documentação.

Python - 321 320

Aqui está minha tentativa (fixa):

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}

Pode ser usado como

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

A solução ainda não está totalmente disponível, mas já está quase ilegível.

Edit: verifique minha resposta abaixo para 250 sob JavaScript puro.

2852 243 caracteres usando LiveScript (sem Regex! Não totalmente golfe - pode ser melhorado)

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

Teste:

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

Ou seja 3^2=9, conforme declarado no OP.

Se alguém estiver curioso, aqui está uma versão estendida com alguns comentários:

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

Arco Waterhouse - 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 #\._])

Bytes C 1039

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

As variáveis ​​permitem como entrada usando letras minúsculas [de a..z] o sys pode gerar variáveis ​​usando letras maiúsculas [de A..Z] se necessário na saída ... Assuma a configuração 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

Pode ser muito menor se o recurso de avaliação lenta do Haskell for totalmente utilizado. Infelizmente, eu não sei como fazer isso.

Além disso, muitos caracteres são desperdiçados na etapa de análise.

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

Versão ungolfed

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

Obteve 231 com JavaScript / sem 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})

Recebe matrizes de 2 elementos. 1representa λe 2 representa uma variável de índice bruijn.

Teste:

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 (medido usando o 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()))

Não é o mais curto em termos gerais, mas lida corretamente com a renomeação alfa e todos os exemplos listados na postagem dos OPs.

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

Experimente online!

A idéia básica aqui é que o código use uma representação interna baseada na idéia dos índices de De Bruijn - exceto que eu inverto os índices para indicar a profundidade lambda da ligação da variável referida. No código:

• E::trepresenta o tipo de um nó - 0 para um nó folha variável, 1 para um nó lambda e 2 para um nó de aplicativo de função. (Escolhido para coincidir com a aridade do nó, o que por acaso é possível.) Então, E::le E::rsão os filhos conforme apropriado (apenas E::lpara um nó lambda) e E::ié o índice de profundidade lambda para um nó folha variável.
• O construtor E::E(E&o,int d,int e)clona uma subexpressão que estava inicialmente na profundidade lambda dpara colar em um novo local na profundidade lambda d+e. Isso envolve preservar variáveis ​​na profundidade lambda menor que dao incrementar variáveis ​​na profundidade lambda pelo menos dem e.
• E::sfaz uma substituição da subexpressão vem número variável dno *thistempo variável decrementing números maiores do que d(e eé um detalhe interno rastrear o incremento lambda profundidade para quando se necessita de chamada E::c).
• E::Rprocura uma única redução beta para executar, preferindo as instâncias superior ou esquerda, de acordo com uma pesquisa de pré-venda no AST. Ele retorna diferente de zero se encontrou uma redução para executar ou zero se não encontrou nenhuma.
• E::ué uma to_stringoperação de tipo que reconstitui uma string "legível por humanos" usando nomes sintéticos para as variáveis. (Observe que, devido a um pouco de golfe na Vfunção auxiliar, ela só gera nomes contendo aatravés dela i.)
• O construtor E::E(int d, std::map<std::string, int> m, char*&s)analisa uma sequência de entrada sem uma expressão AST com base em um mapeamento mde nomes de variáveis ​​atualmente vinculados em índices de profundidade lambda.
• f é a principal função que responde à pergunta.

(Como você pode ver no link TIO, o código faz nomes de variáveis punho com vários personagens, e que também recebe uma resposta correta de (\ a. (\ b. a))para ((\ f. (\ x. (f x))) (\ y. (\ x. y))). Também acontece que o código de análise pode lidar com sombreamento variável, sem nenhum custo extra.)

-16 bytes parcialmente devido à idéia de ceilingcat (que eu também inventei de forma independente) e parcialmente devido à alteração E*a=new E;para E&a=*new E;e depois a alteração a->paraa.

-8 bytes a mais devido a outro comentário de ceilingcat (atribuição de fator de a.tsaída ternário)

-27 bytes da conversão de analisador e clone em construtores de E

Bytes C 637

#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 versão não usa variáveis ​​auxiliares (portanto, não segue 100% do que o cálculo lambda diz ... como muitas outras aqui ...). Cada variável deve ter 1 caractere de comprimento (como algumas outras aqui). Código do teste:

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