태그 보관물: lambda-calculus

lambda-calculus

형식화되지 않은 람다 미적분에 대한 통역사 작성 표현이 있습니다. 람다 표현식은 형태가

문제는 형식화되지 않은 람다 미적분 에 대한 해석기를 가능한 한 적은 문자로 작성하는 것입니다. 형식화되지 않은 람다 미적분학을 다음과 같이 정의합니다.

통사론

다음과 같은 세 가지 유형의 표현이 있습니다.

  • 람다 표현식은 형태가 법적 변수 이름과 수 법적 표현. 여기 에서 매개 변수 라고하며 함수 본문이라고합니다.(λ x. e)xexe

    간단히하기 위해 x현재 범위에 있는 것과 동일한 이름을 가진 변수가 없어야한다는 추가 제한 사항을 추가합니다 . 그 이름이 나타날 때 사이의 변수는 시작 범위에 속할 (λ및 .상기 대응하는 범위에서 판정 중지 ).

  • 기능 응용 프로그램 형태로 가지고 와 법적 표현됩니다. 여기 에서 함수 라고하며 인수라고합니다.(f a)fafa
  • 변수는 형태가 법적 변수 이름입니다.xx

의미론

함수 본문에있는 각 매개 변수를 해당 인수로 바꾸면 함수가 적용됩니다. 더 형식적 형태의 식 ((λ x. e) a), x변수 이름이고 e하고 a식에 표현 평가하여 (또는 감소)이다 나타난 각 대체의 결과 에서 와 .e'e'xea

정상적인 형태는 더 이상 평가할 수없는 표현입니다.

도전

당신의 임무는, 당신이 그것을 받아들이기로 선택한다면, 자유 변수를 포함하지 않는 타입이 지정되지 않은 람다 미적분의 표현을 입력으로 사용하고 그 출력을 표현의 정상적인 형태 (또는 알파와 일치하는 표현)를 생성하는 인터프리터를 작성하는 것입니다. . 식에 정상적인 형식이 없거나 유효한식이 아닌 경우 동작이 정의되지 않습니다.

문자 수가 가장 적은 솔루션이 이깁니다.

몇 가지 메모 :

  • 입력은 stdin 또는 명령 행 인수로 제공된 파일 이름에서 읽을 수 있습니다 (둘 중 하나만 구현하면 됨). 출력이 stdout으로 이동합니다.
  • 또는 입력을 문자열로 가져 와서 출력을 문자열로 반환하는 함수를 정의 할 수 있습니다.
  • 비 ASCII 문자가 문제가되는 경우 \λ 대신 백 슬래시 ( ) 문자를 사용할 수 있습니다 .
  • 우리는 바이트가 아닌 문자 수를 계산하므로 소스 파일이 유니 코드로 인코딩 된 경우에도 λ는 하나의 문자로 계산됩니다.
  • 유효한 변수 이름은 하나 이상의 소문자, 즉 a와 z 사이의 문자로 구성됩니다 (영숫자 이름, 대문자 또는 비 라틴 문자를 지원할 필요는 없지만 물론 솔루션을 무효화하지는 않습니다).
  • 이 문제와 관련하여 괄호는 선택 사항이 아닙니다. 각 람다 식과 각 함수 응용 프로그램은 정확히 한 쌍의 괄호로 묶습니다. 변수 이름은 괄호로 묶지 않습니다.
  • 쓰기와 같은 문법 설탕 (λ x y. e)에 대한이 (λ x. (λ y. e))지원 할 필요가 없습니다.
  • 함수를 평가하기 위해 재귀 깊이가 100을 초과해야하는 경우 동작이 정의되지 않습니다. 모든 언어에서 최적화하지 않고 구현할 수있을 정도로 낮아야하며 대부분의 식을 실행할 수있을 정도로 커야합니다.
  • 또한, 그 간격이 예와 같이 될 것입니다 가정에는 입력의 시작과 끝에서 또는 이전 공간, 즉 수 없다 λ또는 .후 정확히 하나 개의 공간 .과 기능과 인수 사이와 후 λ.

샘플 입력 및 출력

  • 입력: ((λ x. x) (λ y. (λ z. z)))

    산출: (λ y. (λ z. z))

  • 입력: (λ x. ((λ y. y) x))

    산출: (λ x. x)

  • 입력: ((λ x. (λ y. x)) (λ a. a))

    산출: (λ y. (λ a. a))

  • 입력: (((λ 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)))

    출력 : 무엇이든 (이것은 정상적인 형태가없는 표현식의 예입니다)

  • 입력: (((λ x. (λ y. x)) (λ a. a)) ((λx. (x x)) (λx. (x x))))

    출력 : (λ a. a)(이것은 함수 호출 전에 인수를 평가하면 정규화되지 않는 표현식의 예이며 슬프게도 시도한 솔루션이 실패하는 예입니다)

  • 입력: ((λ a. (λ b. (a (a (a b))))) (λ c. (λ d. (c (c d)))))

    결과 : `(λ a. (λ b. (a (a (a (a (a (a (a (a b))))))))))
    교회 숫자로 2 ^ 3을 계산합니다.

답변

최신 :

나는 그것을 644 개의 문자 로 줄였다. 나는 cEll의 일부를 cOpy와 Par에 포함시켰다. 셀 및 cdr에 대한 캐시 된 호출을 임시 로컬 변수로 호출하고 해당 로컬 변수를 “터미널”(즉, 비 재귀) 함수에서 전역 변수로 옮겼습니다. 또한 십진 상수는 문자 리터럴보다 짧고이 불쾌한 사업은 …

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

… 소문자를 정확하게 식별하고 (ASCII 가정)`{|} ~ 중 하나를 허용합니다. UTF-8에 대한 이 훌륭한 비디오 에서 ASCII에 대한 동일한 관찰이 이루어집니다 .

비올라 ::

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

일찍이:

노력에 몇 표를 얻을 수 있습니까? 나는 낮과 밤에 일주일 동안 일하고 있습니다. 나는 원래 McCarthy 논문을 파고 Paul Graham의 The Lis of Lisp 부록을 읽을 때까지 논문 자체의 버그에 시달렸다 . 나는 너무 산만 해져서 내 집에서 내 몸을 가두었다가 12:30에 그날 밤 다시 집에 도착할 때까지 완전히 잊어 버렸다. 할머니의 밤 (노트북 배터리가 마를 때까지 해킹).

그리고 결국, 그것은 우승작에 가깝지 않습니다!

이것을 더 짧게 만드는 방법을 모르겠습니다. 그리고 내가 생각할 수있는 더러운 속임수를 모두 사용했습니다! 아마도 C에서는 불가능할 것입니다.

계산에 약간의 관용으로, 그것은의 (첫 번째 덩어리는 결과 출력 문자열 및 인쇄 소요) 778 개 770 709 694 문자는. 그러나 독립형으로 만들려면 sbrk전화 가 필요합니다 . 보다 복잡한 표현식을 처리하려면 signal핸들러도 필요합니다 . 물론 사용하려는 코드가있는 모듈로 만들 수 없습니다 malloc.

아아, 여기 있습니다 :

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

최종 축소 직전의 블록은 다음과 같습니다. 여기서의 트릭은 포인터 대신 정수 커서 ( ‘내재적 int’동작의 이점을 활용 함)와 ‘스크래치 메모리’를 사용하는 것입니다 char*n. 빈 공간에 대한 ‘새’또는 ‘다음’포인터입니다. 그러나 때로는 메모리에 문자열을 쓴 다음 strlen을 호출하고 n을 증가시킵니다. 효율적으로 메모리를 사용하여 다음 크기를 계산하기 쉽게 한 후, 할당. cell()함수와 데이터의 문자열 표현 사이의 인터페이스를 제외하고 McCarthy 논문에서 거의 직선적임을 알 수 있습니다 .

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

답변

이항 람다 미적분학 186

아래의 16 진 덤프에 표시된 프로그램

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  |........oy..@..F|
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

제안한 형식을 받아들이지 않습니다. 오히려 이진 람다 미적분 (blc) 형식의 람다 용어를 예상합니다. 그러나 최소한의 괄호를 사용하여 일반 양식 축소의 모든 단일 단계를 보여줍니다.

예 : 교회 숫자로 2 ^ 3 계산

xxd -r> symbolic.Blc를 사용하여 위의 16 진 덤프를 저장하십시오.

http://tromp.github.io/cl/uni.c 에서 blc 인터프리터를 가져옵니다.

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

16 진수 덤프를 읽을 수 없으므로 “분해 된”버전입니다.

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

00 (lambda)을 \로 바꾸고 01 (application)을 @로 바꾸십시오. 이제 brainfuck처럼 읽을 수 있습니다 🙂

또한 참조 http://www.ioccc.org/2012/tromp/hint.html

답변

하스켈, 342 323 317 305 자

이 글을 쓰는 시점에서 이것은 ((λ f. (λ x. (fx))) (λ y. (λ x. y)))를 올바른 결과 (λ x. (λ z. (λ x. (λ x. x))보다는 x)). 람다 미적분의 올바른 구현은 이 문제의 단순화를 통해 변수가 범위 내의 다른 변수를 가리지 않도록 보장하는 캡처 방지 대체를 필요로합니다 . (이 보증 없이도 프로그램이 작동합니다.)

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

노트:

  • 이 문제는 2011 년 1 월에 설정 되었기 때문에 필요에 따라 GHC 7.0에서 실행됩니다 . GHC 7.10으로 가정하면 13 자 더 짧습니다 .

설명서가 포함 된 Ungolfed 버전 .

답변

파이썬 – 321 (320)

내 (고정) 시도는 다음과 같습니다.

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

답변

루비 254 자

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}

그것은처럼 사용할 수 있습니다

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

이 솔루션은 아직 완전히 구현되지 않았지만 거의 읽을 수 없습니다.

답변

편집 : 순수한 JavaScript에서 250에 대한 내 대답을 확인하십시오.

2852 는 LiveScript 사용하여 243 자 (없음 정규식을하지 완전히 golfed! – 개선 될 수있다)

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

테스트:

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

이는 3^2=9영업 이익에 명시된 바와 같이.

궁금한 사람이 있으면 다음과 같이 주석이 달린 확장 버전이 있습니다.

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

답변

워터 하우스 아크-140 자

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