'lsip'에 해당되는 글 2건

  1. 2010.01.30 taoi-part1 -session3 - 변수추적
  2. 2009.10.24 Pioneer Profiles - Christopher Strachey
2010.01.30 01:10

taoi-part1 -session3 - 변수추적

아무래도 충동을 이기지 못하고 변수를 추적해 보았다. 직접 보고 싶었기 때문이다. 

만약 직관적으로 이해할 수 있다면 그 것도 좋은 방법이다.

일단은 기계적으로 변수추적을 해보았다. 
다른 방법도 있으나 가장 원시적인 방법을 동원해 보았다. 
다음번의 렉시컬 스코프도 비슷하거나 동등에 가까은 방법을 사용해야 한다.

너무 번거로우니 트레이스 해보는 것은  개인적인 선택이다. 


(define (mapcar fun l)
(cond ((null? l)  '())
(#t (cons (fun (car l)) (mapcar fun (cdr l ))))))
-->
env => {{{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

(DEFINE (SCALE S V) (MAPCAR (LAMBDA (X) (* X S))V))
-->
env => {{{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

(scale 4 '(1 2 4))
--->
exp => {scale 4 {quote {1 2 4}}}
env => {{{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

-->value lookup of scale 
name => scale
vars => {scale}
vals => {{&procedure {s v} {mapcar {lambda {x} {* x s}} v}}}

env => {{{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

-->evlis of scale

arglist => {4 {quote {1 2 4}}}
env => {{{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

fun => {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}
args => {4 {1 2 4}}
env => {{{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

---> 다시  eval로  s,v 의 값이 환경에 들어가 있다.

exp => {mapcar {lambda {x} {* x s}} v}
env => {{{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

--->value  mapcar는 

vars => {mapcar}
vals => {{&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}

-->mapcar 의 evlis는 {lambda {x} {* x s}}  v  다.  
arglist => {{lambda {x} {* x s}} v}

먼저  다음식을 eval 하여 evlis에 추가해야 한다 
exp => {lambda {x} {* x s}}
env => {{{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

결국 얻어내는 것은  apply에 적용하기 위한 fun과 args 다. 

fun => {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}
args => {{&procedure {x} {* x s}} {1 2 4}}

env => {{{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}


다시 &procedure 는 함수와 인자로 다시 계산한다. 
인자는  
vars => {fun l}
vals => {{&procedure {x} {* x s}} {1 2 4}}
이들이 환경에 들어간다. env 가 늘어난 것을 알 수 있다.

exp => {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

그 다음 계산은 evcond가 된다. eval 이 처음 만나는 식은 cond 이므로  evcond 조건이 된다. 

exp => {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

evcond 에서 처음 만나는 조건절은 null? 이다. null? 은 변수 lookup으로 한참 찾아야 한다.

exp => {null? l}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

name => null?
vars => {l}
vals => {{1 2 4}}

당연히 null 이 아니니 #이하의 조건절이 계산된다.
null? 도 #t 도  한참을 찾아야 한다. 이들은 환경변수표의 거의 끝에 있다. 

그래서 
{{#t {cons {fun {car l}} {mapcar fun {cdr l}}}}} 가 참인 조건절이 되어 
{cons {fun {car l}} {mapcar fun {cdr l}}} 가 계산된다.

이제는 cons 로 시작하는 조합식을 푸는 것이다.
cons는 프리미티브에 속한다.  두 인자는 {fun {car l}} 과  {mapcar fun {cdr l}}이다. 
현재의 환경에서 cons 의 value lookup을 하고 두 가지 인자를 찾아야 한다. 

첫번째 인자인 (fun (car l) )을 찾는 과정은 극히 기계적이다.
fun 이라는 함수에 (car l) 을 찾아 대입하는 과정이다. 
(fun 1) 과 마찬가지이고 다시 최종 계산은 (* 4 1) 이므로 4 가 나온다. 

exp => {fun {car l}}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

 car 와 l 값을 찾는다. 

fun => car
args => {{1 2 4}}

1 이 나온다.

fun => {&procedure {x} {* x s}}
args => {1}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

fun 의 값이 {&procedure {x} {* x s}} 이므로 다시 apply 계산으로 들어간다 .

fun => {&procedure {x} {* x s}}
args => {1}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

bind를 써서 환경을 확장했다는 것을 알 수 있다. 
환경표에서 인자와 바인딩하여 x 가 1이라는 것을 알 수 있다. 

exp => {* x s}
env => {{{x} 1} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}
 

이번에는 식 exp => {* x s}를 계산한다. 프리미티브 연산자이며 x 와 s 는 환경에서 룩업하여 구할 수 있다. 
그러면 이제 다음함수와 값의 적용이 일어난다. 

fun => *
args => {1 4}
env => {{{x} 1} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

 결국 cons 의 앞 인자가 4 라는 계산이 나온다.


이 게산이 끝나면  cons의 다음인자인 {mapcar fun {cdr l}}를 찾는 것이다.
사실상 앞의 계산과 마찬가지지만 일단 충실하고 질리게 계산을 해보자. 

mapcar의 값을 찾으면  인자는  fun 과 {cdr l} 이다.  그다음은 인자에 대해 evlist 한다. 

arglist => {fun {cdr l}}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}


fun 은 금방 찾을 수 있고  {cdr l}은  다시 계산이 필요하다. 


결국 인터프리터가 계산해야 하는 것은 다음에 나오는 식의 apply다. 

fun => {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}
args => {{&procedure {x} {* x s}} {2 4}}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

여기서 &procedure  적용을 하면서 바인드 함수는 환경을 확장한다. fun 과 l 의 값을 찾아 환경을 확장하고 다시 식과 환경으로 변한다. 아래에 나오는 환경은 
fun 과 l 의 값이 두개가 나타났다.  자세히 살펴보기 바란다. 룩업이 일어나면 가장 좌측의 값을 먼저 찾는다. 
이번의 l은 (2 4) 다. fun 도 환경의 확장이 일어나면서 다시 복사되었다. 두벌의 fun 이 있다!

exp => {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}
env => {{{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

그 다음은 똑같은 과정의 연속이다. 
evcond 가 계산되고 null? l 이  아니므로 다시 지금과 같은 과정이 반복될 것이다.

fun => null?
args => {{2 4}}


clauses => {{#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}

다시 cons 를 찾은 후 (fun(car l)) 을 계산하고   {mapcar fun {cdr l}을 계산할 것이다. 

arglist => {{fun {car l}} {mapcar fun {cdr l}}}

이제 * x s 를 계산하기 전에 앞서와 마찬가지로 환경의 확장이 일어난다. x는 람다 식의 몸체를 계산하기전 미리 바인딩한다. 

 
name => s
vars => {x}
vals => {2}
env => {{{x} 2} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

이제 {{mapcar fun {cdr l}}} 를 구해야 한다. 
mapcar의 값을 찾으면  인자는  fun 과 {cdr l} 이다.  그다음은 인자에 대해 evlist 한다. 


이제 계산이 끝나면  다음의 함수와 인자를 또 apply 해야 한다. 

fun => {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}
args => {{&procedure {x} {* x s}} {4}}
env => {{{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

결국 이 함수의 apply 과정에서 환경의 확장이 일어난다.

그 다음은 몸체의 계산이다. env는 다시 길어졌다,

exp => {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}
env => {{{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}


그 다음은 evcond다,  이전과 똑같다.  이번의 l은 {4} 이다. 
앞서와 마찬가지로 null? 조건절에서 통과하지 못한다. 다시 앞부분들과 똑같은 계산이다. 


clauses => {{#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}
env => {{{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

다시 {cons {fun {car l}} {mapcar fun {cdr l}}}를 계산한다. 
cons 값을 룩업하고 인자리스트에 대해 evlist 한다. 

arglist => {{fun {car l}} {mapcar fun {cdr l}}}

fun => {&procedure {x} {* x s}}
args => {4}
env => {{{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

*를  계산하기전 환경의 확장이 일어난다. 

exp => {* x s}
env => {{{x} 4} {{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}
exp => {* x s}
env => {{{x} 4} {{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

이제  {{mapcar fun {cdr l}}} 를 계산해야 한다. 
exp => {mapcar fun {cdr l}}
env => {{{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

이 식을 apply하면서 
앞서와 마찬가지로 함수값을 룩업하고 인자리스트를 계산한다. 
결국 다음과 같은 값이 된다.

fun => {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}
args => {{&procedure {x} {* x s}} ()}
env => {{{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}


다시 계산하기 위해 환경을 확장하면 
exp => {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}
env => {{{fun l} {&procedure {x} {* x s}} ()} {{fun l} {&procedure {x} {* x s}} {4}} {{fun l} {&procedure {x} {* x s}} {2 4}} {{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

이제 l 은 '() 이 되었으니 null? 을 통과할 것이다. 

아무튼 다시 evcond .

이제 null? 을 통과한다. 

name => l
slot => {()}

clauses => {{{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}

이제 다음식을 계산하고 내보내게 된다 
exp => {quote ()}

그 다음 계산은 

fun => cons
args => {16 ()}

fun => cons
args => {8 {16}}


exp => {cons {fun {car l}} {mapcar fun {cdr l}}}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

fun => cons
args => {4 {8 16}}
env => {{{fun l} {&procedure {x} {* x s}} {1 2 4}} {{s v} 4 {1 2 4}} {{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

-->

(4 8 16)

env => {{{scale} {&procedure {s v} {mapcar {lambda {x} {* x s}} v}}} {{mapcar} {&procedure {fun l} {cond {{null? l} {quote ()}} {#t {cons {fun {car l}} {mapcar fun {cdr l}}}}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}
form => {scale 4 {quote {1 2 4}}}
저작자 표시
신고
Trackback 0 Comment 0
2009.10.24 08:54

Pioneer Profiles - Christopher Strachey

세상에는 재미있는 사람이 많다.
denotational semantics를 만들었던 스트래치 같은 사람이 그 예다. 
튜링상을 받은 사람들과 오랫동안 작업을 해오면서도 의외로 알려지지 않았다. 

스트래치는 집안 대대로 머리가 좋았는데 블룸스베리 그룹의 일원이 리튼 스트래치도 있고 다른 유명한 스트래치가 있다.  블룸스베리 그룹은 이상하게도 재미있는 사람들이 많았고 이들의 문재는 탁월했다.   가장 많이 알려진 사람은 메이나드 케인즈일 것이다. 버지니아 울프도 바네사 벨도 이 그룹의 일원이었다. 아더 웨일리( 많이 알려지지는 않았지만 노자의 도덕경을 영어로 번역한 "The Way and it's Power"를  썼다. 하이쿠와 동양의 많은 작품이 웨일리를 통해 번역되었다.  이들은 너무 자유분방해서 박사학위를 따지 않은 사람도 많다. 동성애와 양성애적 성향을 항상 이들을 따라 다녔다. 케인즈 역시 마찬가지였다.  찰스 스트래치도 그런 사람으로 볼 수 있다.   

얼마전 작고한 피터란딘은 스트래치의 유일한 조수였다. 란딘은 컨티뉴에이션으로 많이 알려져 있지만  스트래치와 란딘이 알골과 다른 컴퓨터언어에 미친 영향은 상당히 컸다.  스트래치는 1975년 작고 했다.  그 다음 스트래치 그룹의 영향력은 많이 시들해졌다. 스트래치의 영향력이 너무 컸다면 우리는 수학에 가까운 프로그래밍으로 많이 기울었을 것이다. 

C 언어의 직접적인 조상인 CPL ,BCPL ,B와 관련이 있고 마크로를 만든 사람으로도 알려져 있다.  l-valu와 r-value의 이론적인 확립을 하기도 했다.  Cuurrying (Haskel Curry의 이름에서 따옴)을 명명하기도 했다.

무엇보다도 Fixed Point 의 이론을 보면 언제나 스트래치를 만나게 되어있다. sicp 에 지겹도록 나오는 함수형언어의 개념은 처음부터 lisp에서 강조된 것은 아니다. 재 발견한 것이다.  Christopher Strachey는 ”Functions as First-class Citizen' 이라는 모토아래 Lamda 계산 개념이 프로그래 언어의 설계에 기본이라고 하였다. Scheme은 특히 이런 영향을 직접적으로 받았다. 람다페이퍼라고 부르는 문서들에 명확히 나온다.

너무 방탕하게 놀다가 대학을 간신히 졸업했으나 나중에는 캠브리지의 컴퓨터 연구소를 지도한다. 후반부에 공동으로 연구하던 Dana Scott는 튜링상을 받았다.   현재의 수학실력으로는 즐기기엔 무리였다. MIT의 해커들도 버거워했던 주제다. 증명이 되는 것으로 만족해야 할지 모른다. 

위키백과에도 소개글이 있다. (http://en.wikipedia.org/wiki/Christopher_Strachey )

얼마전 서핑을 하다가 스트래치를 재평가하는 작업들을 보았다. 
아래의 글은 그 중의 하나다. 


Pioneer Profiles - Christopher Strachey

David Barron
Christopher Strachey

Author’s Note.

This is not a fully-referenced scholarly paper. Rather, it is an affectionate tribute to a former colleague and friend and is based mostly on memories of conversations, whether at High Table in Cambridge, in the Laboratory, or in the rural seclusion of the Strachey family home in Sussex.

Anyone who recognises the name ‘Strachey’ will no doubt associate it with the literary family who were at the heart of the Bloomsbury Group (think ‘Eminent Victorians’ by Lytton Strachey - Christopher’s uncle). And those few computer scientists who recognise ‘Christopher Strachey’ will probably associate the name with his work on formal semantics of programming language at Oxford, in collaboration with Dana Scott. But Christopher was far more than a theorist: he was always the programmer’s programmer, and also played a leading part in the founding of the British computer industry, as a logical designer.

Although the Stracheys were mainly a literary clan, there was a mathematical streak in the family - Christopher’s father Oliver was engaged in decryption in both world wars. Christopher followed this streak, and went up to King’s College Cambridge in 1935 to read Mathematics. After various vicissitudes, he graduated in Natural Sciences and took up a job as a research physicist with STC (Standard Telephone and Cables Ltd.). At the end of the war, he left STC and took up teaching, eventually becoming a mathematics master at Harrow School in 1949.

During his time with STC he had been involved in numerical solution of differential equations using a Differential Analyser (an analogue computer). Whilst at Harrow, he was introduced to Mike Woodger who told him about Turing’s ‘Pilot Ace’ computer at NPL. Christopher wrote a program to play draughts on the machine, but the Pilot Ace wasn’t really up to the job. Hearing about the Manchester Mark 1, he wrote to Turing, his contemporary at King’s, asked for details of the instruction sets and completed a program that not only played draughts, but also played “God Save the King” on completion.

In 1949, Lord Halsbury had persuaded the Government to set up the National Research Development Corporation (NRDC) under his leadership, the intention being to commercialise British scientific ability. Halsbury was particularly seized by the potential of the then new computers, and persuaded Strachey to join NRDC. As well as doing the programming for a simulation of the proposed St Lawrence Seaway, he took a major role in the development of the Elliot 401 and Ferranti Pegasus computers, being responsible for the logical design of the Pegasus, a workhorse to replace the Ferranti Mark 1 (based on the Manchester Mark 1). In 1959, he left NRDC and set up shop as the country’s first freelance computer consultant. In this capacity he had substantial input into the design of EMI’s EMIDEC 1100 and 2400 computers.

In 1962, Strachey, whilst continuing as a consultant, was persuaded by Maurice Wilkes to join the team at Cambridge developing a cut-down version of the Manchester Atlas supercomputer (called Titan in Cambridge, but marketed by Ferranti/ICL as Atlas 2). Strachey’s brief was to develop a new programming language for the machine, working with myself and David Hartley. The language was based on Algol 60, and was initially called CPL (Cambridge Programming Language). Later, we joined forces with a team at the University of London Institute of Computer Science, and it became ‘Combined Programming Language’. For myself, I am content for it to be remembered as Christopher’s Private Language.

CPL had many innovative features: some of these were just, in Christopher’s phrase, “syntactic sugar”, but a major contribution was the clarification of the concept of L-values and R-values, which can be seen in C and all subsequent languages. (CPL begat BCPL, which begat B and then C and C++: another example of the pervasive influence of Christopher at the time). The development of CPL also provides another instance of Christopher as a programmer’s programmer. He decided that we needed a macro generator to assist in developing the CPL compiler, and - over a weekend in his Sussex home - produced the General Purpose Macrogenerator, GPM. This was an incredibly elegant string-substitution language - which could also, as he demonstrated in a tour-de-force of programming, be used to compute factorials.

As the CPL project proceeded, he became more and more interested in the formal semantics of programming languages. Delivery of the compiler fell more and more behind schedule. As a result, in 1965 he accepted an offer of a post at Oxford, as Head of the Programming Research Group (PRG), an offshoot of the Computing Laboratory. Here, in collaboration with Dana Scott, he developed his theory of denotational semantics and was eventually recognised by the award of a Personal Chair. But even whilst he was engaged in this theoretical work, the demon programmer survived. The PRG was given funds to buy a Modular One computer. Christopher decided from the start that the group would do their programming using an interpreter to simulate a stack machine. This was to be embedded in an operating system (OS/6) based on high level concepts. In the months between the placing of the order for the Modular One and its delivery, Christopher and his assistant Joe Stoy wrote the system in a CPL-like language, and developed a cross-compiler on the University’s KDF9 mainframe to compile the code into Modular One assembler. The machine eventually arrived, and the engineers installed it. The cross-compiled code was loaded, and pretty well worked out of the box. A night of tweaking followed, and in the morning the PRG personnel appeared to find a working system. Strachey locked away the Modular One manuals: “I’m the only one who knows the instruction code” he joked. His premature death in 1975 deprived the country of one of its greatest and most prolific computer scientists. (He always denied the existence of Computer Science, but he will be remembered as one of the subject’s founding fathers.)

There’s so much more that I could say about this remarkable man: perhaps the Editor will allow me another thousand words in a forthcoming issue. Let me finish with a quotation that says it all:

“It has long been my personal view that the separation of practical and theoretical work is artificial and injurious. Much of the practical work done in computing, both in software and in hardware design, is unsound and clumsy because the people who do it have not any clear understanding of the fundamental design principles of their work. Most of the abstract mathematical and theoretical work is sterile because it has no point of contact with real computing.”


저작자 표시
신고
Trackback 0 Comment 0


티스토리 툴바