';isp'에 해당되는 글 1건

  1. 2010.02.22 TAOI로 CPS factorial 풀어보기
2010.02.22 07:59

TAOI로 CPS factorial 풀어보기

이것은 개인적인 호기심으로 factorial을 CPS 방식으로 푸는 예제가 리스프나 스킴의 내부에서 어떻게 돌아가는 가를 알려준다. 
람다가 환경을 다루는 방식을 알려주는 것으로 개인적인 호기심이다. 

(긴 데다가 쓸모도 없다.  이글을 이해할 필요는 없다.  나중에 생각이 나지 않으면 보려고 만든 문제다. 
그래도 올리는 이유는 이런 방법론도 있다는 것을 적어 놓기 위해서다.
)

예전의 컬럼에서 나는 cps 예제를 다루었다, 실제로 인터프리터까지 동원해서 풀어본 것은 호기심 때문이다.
람다 주변의 환경과 클로저를 관찰하기 위한 것이었다.  예상대로 동작했다. 

하지만 풀어본 경험으로는 역시 골치아프다는 말 밖에는 ^^

----------------------------------------

원래의 예제 

....

그런데 제3의 방법도 있다. 컨티뉴에이션을 이용하는 방법이다. 서스만과 스틸의 장난감 언어에서 구현한 예제다. 식은 매우 간단하다(출처는 Scheme: An Interpreter for Extended Lambda Calculus의 앞부분이다. 이 문서는 ‘inspired by actors’라는 문구로 시작한다). Hewitt이 발견한 방법으로 적용한 것이다.


(define fact 
	(lambda (n c)
		(if (= n 0) (c 1)
		(fact (- n 1) 
			(lambda (a) (c (* n a)))))))


얼핏 보기에는 이터레이션과 같다. 그러나 이 식은 컨티뉴에이션을 사용한다. 저장되는 것은 프로그램 수행에 필요한 정보이며 계산의 중간 값이 아니다.

(fact 3 answer)라는 식을 입력하였을 때 위의 식은 컨티뉴에이션인 answer에 결과를 적용한다. 이 프로그램을 스킴에서 실행하면 다음과 같이 된다. 컨티뉴에이션 패싱 스타일(continuation passing style)의 원시적인 모습이다. 계산의 중간 과정들을 옮겨본다.

fact 3 answer

-->(if  (= 3 0) (answer 1)
	(fact (-3 1) (lambda (a) (answer (* 3 a)))))
-->(fact (- 3 1) (lambda (a) (answer (* 3 a)))))
-->(fact (2) (lambda (a) (answer (* 3 a))))) 
// 람다에 3을 적용한다. 
-->(if  (= 2 0) (lambda (a) (answer (* 3 a))) 1 )
	(fact (- 2 1) 
		 (lambda (a) 
	           ( (lambda (a) (answer (* 3 a)))
			(* 2 a)))))
// 3이 적용된 람다 함수 자체의 실행 컨텍스트가 c의 값으로 적용되고
// 다시 (* 2 a)가 적용된다. 
-->(fact (- 2 1) 
		 (lambda (a) 
	           ( (lambda (a) (answer (* 3 a)))
			(* 2 a)))))
-->(fact 1 
		 (lambda (a) 
	           ( (lambda (a) (answer (* 3 a)))
			(* 2 a)))))

-->(if (= 1 0) 
	( (lambda (a) 
	           ( (lambda (a) (answer (* 3 a)))
			(* 2 a))))) 
	1)

	(fact - 1 1)
		(lambda(a)
			((lmbda (a)
				((lambda (a) 
					(answer (* 3 a)))
			(* 2 a)))
		(* 1 a)))))
// c는 계속 길어진다. 
-->(fact - 1 1)
		(lambda(a)
			((lmbda (a)
				((lambda (a) 
					(answer (* 3 a)))
			(* 2 a)))
		(* 1 a)))))

-->(fact 0)
		(lambda(a)
			((lmbda (a)
				((lambda (a) 
					(answer (* 3 a)))
			(* 2 a)))
		(* 1 a)))))

-->(if (=0 0)
		((lambda(a)
			((lmbda (a)
				((lambda (a) 
					(answer (* 3 a)))
			(* 2 a)))
		(* 1 a)))
		1)

 (fact (- 0 1)
    ......))

// 이제 n=0이 되었으므로 컨티뉴에이션에 1을 적용할 수 있다! 
// 기다랗게 만들어진 람다 함수에 1을 적용하면서 계산이 일어난다. 

---> ((lambda (a)
			((lmbda (a)
				((lambda (a) 
					(answer (* 3 a)))
			(* 2 a)))
		(* 1 a)))
		1)

---> 	((lambda (a)
				((lambda (a) 
					(answer (* 3 a)))
			(* 2 a)))
		(* 1 1))
		

--->((lambda (a)
			((lambda (a) 
				(answer (* 3 a)))
		(* 2 a)))
	1)

--->	((lambda (a) 
				(answer (* 3 a)))
		(* 2 1))
	
---> ((lambda (a) 
				(answer (* 3 a)))
		2)
--->( answer (* 3 2))
--->( answer 6)  



 
위로


이제야 계산이 끝났다. 새로운 방법의 팩토리얼 계산법은 이렇게 끝난 것이다. 괄호가 한두 개 빠지거나 더해졌을지는 모르지만 컨티뉴에이션을 전달하여 문제를 푸는 방식의 기본적인 개념은 어떤 람다에게 값을 전해주는 것뿐이다. fact가 한 일은 아무것도 없다. fact는 이터레이션처럼 동작했고 마지막에는 (fact n c)의 컨티뉴에이션 c에게 n=0인 경우에 1을 적용(apply)했을 뿐이다. 위에 적은 식이 팩토리얼의 재귀나 이터레이션보다 복잡한 것도 없다. 결국 모든 치환과 적용이 일어나면 answer에게 값이 전달된다.

실제의 answer는 어떤 함수일까? 결과가 적용되는 가장 간단한 함수 answer는 자기가 받은 값을 되돌리는 (lambda (x) x)다. 그렇다면 (fact 3 (lambda (x) x))는 6을 되돌린다.

조금 싱겁겠지만 실행 문맥 자체를 적용하는 새로운 계산법이 등장한 것이다. 복잡하고 중요한 문맥을 되돌릴 수도 있으며 아주 복잡한 계산도 할 수 있다. 실제로 컴파일러 내부에서는 이런 방법을 적용할 수 있다. 문맥을 전달하면서 복잡한 제어 구조를 명시적인 식으로 만들어 낼 수도 있다. 계산식을 만들어 내는 것은 소스코드를 새로 쓰는 것과 다르지 않다. 컨티뉴에이션에 대해서는 생각할 거리가 많은 것이다.

다음 이야기인 CPS(continuation passing style)와 call/cc(call with current continuation)는 이보다 조금 더 복잡하기는 해도 컨티뉴에이션에 대한 가장 기본적인 부분은 이번 글에서 다룬 셈이다.



--------------------------------------


이 식을 taoi 인터프리터로 풀어보기 

예전에 continuation passing style 의 주제를 다룬 적이 있다. 
이해가 어려운 것은 아니었으나 실제로 어땋게 돌아가는 가를 조사한 적은 없었다.
TAOI 에 물려서 돌려볼 필요가 있었다. 

아직 TAOI 에는 cond 밖에 없으므로 if 를 사용하지 않고 cond를 사용하였다. 
sicp 는 if  를 기본으로 cond는 derived expression으로 만들었다.
아무튼 기본 동작의 이해에 지장을 주는 것은 아니다. 

(driver)


(define (fact n c)
(cond ( (= n 0) (c 1))
(#t (fact (- n 1) 
(lambda (a) (c (* n a)))))))

(fact  5  (lambda (x)  x ) )


이번 분석은 n=5 로 넣어서 너무 길다. 3 이나 4 정도 가 알맞을 듯..
스페이스를 넣어  변수 구분자로 사용했다.

n=5 :
..
n=3:

; fun is closure

fun => {&procedure {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}  {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}

args => {3  {&procedure {a} {c {* n a}}      {{{n c} 4 {&procedure {a} {c {* n a}}      {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f}    {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}}     {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}}


n=2

fun => {&procedure {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}} {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}

args => {2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}}}}}}


n=1:

fun => {&procedure {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}} {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}

args => {1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}}

arglist => {0}
env => {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}

exp => {fact {- n 1} {lambda {a} {c {* n a}}}}
env => {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}


;n=0:


fun => {&procedure {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}} {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}

args => {0 {&procedure {a} {c {* n a}} {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}}


;c is apllied to 1  (c 1)

exp => {c 1}
env => {{{n c} 0 {&procedure {a} {c {* n a}} {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}


name => c
vars => {n c}
vals => {0 {&procedure {a} {c {* n a}} {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a}
...


name => c
vars => {c}
vals => {{&procedure {a} {c {* n a}} {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t

...

; evaluation CPS lambda 


fun => {&procedure {a} {c {* n a}} {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {1}

vars => {a}
vals => {1}
base-env => {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}

exp => {c {* n a}}
env => {{{a} 1} {{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}


exp => c
env => {{{a} 1} {{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {
....



name => c
vars => {c}

vals => {{&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}}


env => {{{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}







exp => {c {* n a}}
env => {{{a} 1} {{n c} 1 {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}



fun => {&procedure {a} {c {* n a}} {{{n c} 2 {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {1}


fun => {&procedure {a} {c {* n a}} {{{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {2}

exp => {c {* n a}}
env => {{{a} 2} {{n c} 3 {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}


fun => *
args => {3 2}

fun => {&procedure {a} {c {* n a}} {{{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {6}


exp => {* n a}
env => {{{a} 6} {{n c} 4 {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}

fun => *
args => {4 6}


fun => {&procedure {a} {c {* n a}} {{{n c} 5 {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {24}



fun => *
args => {5 24}


fun => {&procedure {x} x {{{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {120}


exp => x
env => {{{x} 120} {{fact + - * = eq? cons car cdr null? #t #f} {&labeled {n c} {cond {{= n 0} {c 1}} {#t {fact {- n 1} {lambda {a} {c {* n a}}}}}}} + - * = eq? cons car cdr null? #t #f}}

120





저작자 표시
신고
Trackback 0 Comment 0


티스토리 툴바