'lisp'에 해당되는 글 35건

  1. 2009.03.29 Recursion 과 let , letrec- Teach Yourself Scheme in Fixnum Days
  2. 2009.03.27 sicp (1)
  3. 2009.03.26 변수에 대해 생각해보기 (2) Teach Yourself Scheme in Fixnum Days
  4. 2009.03.23 피터 노빅의 paip
  5. 2009.03.21 동적 바인딩 생각해 보기 (1)
  6. 2009.03.21 anatomy of lisp
  7. 2009.03.20 A Gentle Introduction to Symbolic Computation
  8. 2009.03.20 lambda the ultimate imperative 10-13 페이지 생각해 보기 (1)
  9. 2009.03.13 The Y Combinator
  10. 2009.03.12 느긋한 계산법
2009.03.29 00:30

Recursion 과 let , letrec- Teach Yourself Scheme in Fixnum Days



Teach Yourself Scheme in Fixnum Days의  6장은  Recursion 이다.
이전에 Y combinator를 설명한적이 있다.

리스프에서 recursion의 구현의 본질은  함수를 변수처럼 만들어 치환해 버리는 것이다.
Y 컴비네이터의 본질은 이런 일을 일으키는 조합자를 만드는 것이다.

둘은 사실상 같다.

인터프리터를 만들면서 돌려보면 정말로 같다는 것을 알것이고 얼마 후에 적을 인터프리터 이야기 1편 (예전의 ibm 글의 개작편)에서 자세히 다룰 예정이다.  lisp에서는 label 이지만 스킴에서는 초기에 label을 사용하다 letrec을 사용한다. letrec은  그 이전에 다른 lisp들에서 쓰인 적이 있았고 스킴에서 처음 만든 것은 아니다.

별다른 내용은 아니지만 fixnum days의 6장에 토를 달아본다.


A procedure body can contain calls to other procedures, not least itself:

 
(define factorial
  (lambda (n)
    (if (= n 0) 1
        (* n (factorial (- n 1))))))
- 위의 define..은 다음과 같이 적을 수도 있다. 결국 define이 한 일은 람다식에 변수이름을 달아준 것이다. 
 
(define (factorial n)
      (if (= n 0) 1
        (* n (factorial (- n 1)))))
 
 
This recursive procedure calculates the factorial of a number.
If the number is 0, the answer is 1. 
For any other number n, the procedure uses itself to calculate the factorial of n - 1, multiplies that subresult by n, and returns the product.

-  recursion 이 위의 fact 처럼 하나의 함수에서 일어나는 것이 아니라 몇개의 함수들이 서로 상대방을 부르는 경우도 있는데 이 경우에는 조금 복잡해진다. 가장 간단한 것은 톱레벨에서 정의하는 것이다.  다음 예제에서 홀수와 짝수는 서로 상대방을 부른다. (처음에 하나를 먼저 정의할 때  다른 함수는 정의되어 있지 않다. 있다고 간주하는 메카니즘이 있어야 한다. )

Mutually recursive procedures are also possible. The following predicates for evenness and oddness use each other:

(define is-even?
  (lambda (n)
    (if (= n 0) #t
        (is-odd? (- n 1)))))

(define is-odd?
  (lambda (n)
    (if (= n 0) #f
        (is-even? (- n 1)))))

These definitions are offered here only as simple illustrations of mutual recursion. Scheme already provides the primitive predicates even? and odd?.

6.1  letrec


-  let을 쓰면 잘 동작하지 않는다는 것을 보여주고 있다. l let* 도 마찬가지다. (지난번에 설명했듯이 let*은 (let ..(let 의 형태다.)

If we wanted the above procedures as local variables, we could try to use a let form:

(let ((local-even? (lambda (n)
                     (if (= n 0) #t
                         (local-odd? (- n 1)))))
      (local-odd? (lambda (n)
                    (if (= n 0) #f
                        (local-even? (- n 1))))))
  (list (local-even? 23) (local-odd? 23)))
 
This won't quite work, because the occurrences of local-even? and local-odd? 
in the initializations don't refer to the lexical variables themselves. 
Changing the let to a let* won't work either, for while the local-even? inside local-odd?'s body refers to the correct procedure value, the local-odd? in local-even?'s body still points elsewhere.

To solve problems like this, Scheme provides the form letrec:

(letrec ((local-even? (lambda (n)
                        (if (= n 0) #t
                            (local-odd? (- n 1)))))
         (local-odd? (lambda (n)
                       (if (= n 0) #f
                           (local-even? (- n 1))))))
  (list (local-even? 23) (local-odd? 23)))

The lexical variables introduced by a letrec are visible not only in the letrec-body but also within all the initializations. letrec is thus tailor-made for defining recursive and mutually recursive local procedures.

- letrec 안의 렉시컬 변수(여기서는 함수이름이다)는 초기화하면서 서로에게 보인다. 그래서  상호순환하는 프로시저를 정의하기에 안성맞춤인 함수이다. 

r5rs에는 11페이지에 다음과 같이 나온다,

(letrec bindings body) 


Semantics: Bindings은 ((variable1 init1i) : : : ),의 형태다. variable은 같은 이름이 두번 나와서는 안된다.
variable 은 처음에 특정한 값을 갖지 않은 채 위치만 차지한다. 그 다음에 init 이 계산되어 이 값이 variale에 지정된다.  그 다음에는 앞에서 일어난  variable의 변화를  environmet 에 반영하여 body를 계산한다. 


(letrec ((even?
(lambda (n)
(if (zero? n)
#t
(odd? (- n 1)))))
(odd?
(lambda (n)
(if (zero? n)
#f
(even? (- n 1))))))
(even? 88))
=) #t


letrec 의 구현상 대단히 중요한 조건이 있다.
각각의 init를 계산할 때  다른 varaible 값을 참조하거나 지정하지 않고 계산할 수 있어야 한다.
거의 대부분의 경우 init 이 람다식이므로  이런 조건은 별다른 문제 없이 자동으로 충족된다.

프리드만의 why of y 에 보면

(letrec ((f (lambda ...))) ...) 은  다음과 등가이다.
--> (let ((f <undefined>)) (set! f (lambda ...)) ...)
결국 let 과  set! 으로 구현하는 경우가 많다는 것이다.


(결국 구현상의 조건이며 사용자들은 별다른 문제를 느끼지 않을 것이다.
r5rs에도 별다른 내용은 없다. )

(아래의 내용은 특별한 것이 없다.)




6.2  Named let

A recursive procedure defined using letrec can describe loops. Let's say we want to display a countdown from 10:

(letrec ((countdown (lambda (i)
                      (if (= i 0) 'liftoff
                          (begin
                            (display i)
                            (newline)
                            (countdown (- i 1)))))))
  (countdown 10))

This outputs on the console the numbers 10 down to 1, and returns the result liftoff.

Scheme allows a variant of let called named let to write this kind of loop more compactly:

(let countdown ((i 10))
  (if (= i 0) 'liftoff
      (begin
        (display i)
        (newline)
        (countdown (- i 1)))))

Note the presence of a variable identifying the loop immediately after the let. This program is equivalent to the one written with letrec. You may consider the named let to be a macro (chap 8) expanding to the letrec form.


-  위에 나온 카우트다운 예제는 10 이라는 초기값을 가지고 곧바로 실행된다.  이런 식으로 프로그램을 작성하는 것을 좋아하는 사람도 있다.  불필요한 define을 사용하지 않는다.




6.3  Iteration

countdown defined above is really a recursive procedure. Scheme can define loops only through recursion. There are no special looping or iteration constructs.

Nevertheless, the loop as defined above is a genuine loop, in exactly the same way that other languages bill their loops. Ie, Scheme takes special care to ensure that recursion of the type used above will not generate the procedure call/return overhead.

Scheme does this by a process called tail-call elimination. If you look closely at the countdown procedure, you will note that when the recursive call occurs in countdown's body, it is the tail call, or the very last thing done -- each invocation of countdown either does not call itself, or when it does, it does so as its very last act. To a Scheme implementation, this makes the recursion indistinguishable from iteration. So go ahead, use recursion to write loops. It's safe.

Here's another example of a useful tail-recursive procedure:

(define list-position
  (lambda (o l)
    (let loop ((i 0) (l l))
      (if (null? l) #f
          (if (eqv? (car l) o) i
              (loop (+ i 1) (cdr l)))))))

list-position finds the index of the first occurrence of the object o in the list l. If the object is not found in the list, the procedure returns #f.

Here's yet another tail-recursive procedure, one that reverses its argument list ``in place'', ie, by mutating the contents of the existing list, and without allocating a new one:

(define reverse!
  (lambda (s)
    (let loop ((s s) (r '()))
      (if (null? s) r
	  (let ((d (cdr s)))
            (set-cdr! s r)
	    (loop d s))))))

(reverse! is a useful enough procedure that it is provided primitively in many Scheme dialects, eg, MzScheme and Guile.)

For some numerical examples of recursion (including iteration), see Appendix C.

6.4  Mapping a procedure across a list

A special kind of iteration involves repeating the same action for each element of a list. Scheme offers two procedures for this situation: map and for-each.

The map procedure applies a given procedure to every element of a given list, and returns the list of the results. Eg,

(map add2 '(1 2 3))
=>  (3 4 5)

The for-each procedure also applies a procedure to each element in a list, but returns void. The procedure application is done purely for any side-effects it may cause. Eg,

(for-each display
  (list "one " "two " "buckle my shoe"))

has the side-effect of displaying the strings (in the order they appear) on the console.

The procedures applied by map and for-each need not be one-argument procedures. For example, given an n-argument procedure, map takes n lists and applies the procedure to every set of n of arguments selected from across the lists. Eg,

(map cons '(1 2 3) '(10 20 30))
=>  ((1 . 10) (2 . 20) (3 . 30))

(map + '(1 2 3) '(10 20 30))
=>  (11 22 33)

Trackback 0 Comment 0
2009.03.27 17:48

sicp

워낙 평가가 엇갈리는 책이라 쉽게 평가를 내리지는 못하고 있다.  아마존의 평가에는 lisp 관계자들이 이 책을 옹호하고 이에 동조하는 많은 사람들이 있고 전혀 그렇지 않다는 사람들도 있다. 중간값들이 없는 이상한 분포가 나온다. 

한국어 번역판에 대해서도 뭐라고 할말은 없다.
책의 번역에 참가했으면서도 용어선정에 대해 많은 불평을 했던 장본인으로 
마지막장을 번역하는 입장에서 앞장의 용어사용을 가로막을 수는 없었던 것 같다. 
recusion 을 재귀 , 순환 , 되도는 등의 용어를 사용했고,evaluation을 계산  , compiler 를 번역기라고 사용했는데 나는 컴파일러와 이밸류에이터 역시 아름다운 우리말에 대해 아름다운 외래어라고 생각하기 때문이었다. 물론 컴퓨터라는 용어에 한 적당한 대응물도 없다. 계산기는 흔히 사용하며 셈틀이라고 적으면 아직은 머쓱하다.
외국어에 대한 다대일 적용 역시 쉬운일이 아니다. 



그러나 이 책의 분위기는 아름다운 우리말을 쓰자는 분위기였고 나중에는 현실과 타협했다.  너무 우리말을 많이 쓰지는 않았던 것이다.   
 하지만  이 책의 번역에 대한 인사이트 관심과 노력은 정말 대단했다고 생각된다.  그 점에 대해서는  할말이 없다.

책을 코스로 가르치는 일 , 특히  학부에서 가르치는 일은 쉽지는 않을 것은 분명하다.  그점은 mit 역시 쉽지 않지만  대신 전통과 막강한 강사들이 있다.  (sussman 과  abelson 이후에  sicp 과정을 가르치는 사람들의 수준은 매우 높은 편이다.)




책의 이해에는 행과 행간에 설명하지 않은 많은 내용들이 필요한데 :

일차적으로는 람다페이퍼들의 이해가 필요하며 (전부 다는 아니지만 역사적 맥락이나  배경지식 정도는 꼭 필요하다. )

두번째는 람다 페이퍼가 아닌 다른 배경 설명이 필요하다.  sicp의 내용을 이해하기 위해 다른 자료를 뒤지면서 찾기도 한다.

세번째는 이 책이 하나의 토이가 되는 과정이 필요하다. 시간이 든다. 책이 사람의 사고 방식을 바꿀 수 있다면 매우 좋은 책인데  sicp 는 그런  능력은 있다. 프로그램의 내공이 증가한다던가 하는 구체적인 내용은 없을 것이지만 분명히 오래 놀고 있으면 변화는 온다. 하지만 한학기 만에 오지는 않을 것이다.  붇잡고 노는 것이 중요하리라고 생각한다. 

이 블로그의 엉성한 자료와 글들의 일부는 분명히 sicp 를 위한 것 (sicp 만을 위한 것은 아니다.) 이고 배경지식을 보충하는 역할을 한다. 단지 개인적으로는 많은 것들을 배울 수 있었다고 말할 수 있다. 거창한 것들은 아니지만 그렇다.  문제는  1장부터 적는 것이 아니라 3장 정도부터 자료를 올리는 점이라고 할 수 있다. 

영문판책은 사지 않아도 인터넷에 있다. (ttp://mitpress.mit.edu/sicp/full-text/book/book.html)
요즘은 비디오 강의는 트래픽이 많아 다운 로드 받기 어려운 것 같다. 누군가 올려주었으면 좋겠다.




예전에 적었던 평가를 다시 옮겨본다.
----------------------------

'마법사 책'이라 불린 SICP

SICP(Structure and Interpretation of Computer Programs)는 한때 미국 주요 대학들의 컴퓨터학과 필수 과정 중 하나였다. 책은 매우 어려운 편이고 책의 연습문제라는 것들에는 우수한 컴퓨터 프로그래머들이 고민하던 문제들이 포함되어 있다. 그리고 다른 책과는 그 구성이 너무 다르다. 끝부분에 가면 메타 서큘러 실행기를 거쳐 언어의 컴파일러인지, 하드웨어의 컴파일러인지 경계가 애매한 지경에까지 이른다. 학생들이 당혹해 할 것은 틀림없다. SICP는 컴퓨터 교육의 패러다임을 바꾸어 놓았다는 평을 듣기도 한다.



그래서 SICP에 대해서는 많은 사람들의 의견이 반반으로 갈린다. 생각하고 배울 점이 많은 책이라는 의견과 배울 것도 없으면서 시간만 낭비하게 하는 괴상한 책이라는 견해다. 한때 이 책을 필수 학점의 교재로 사용하던 학교에서는 학생들이 과정을 따라가는 일 자체에 공포심을 느꼈으며 불평도 대단했다. 시종일관 생각하게 만든다는 것이 공포심을 갖게 하는 요인이었다. 필자 역시 처음에는 책이 너무나 이상하다고 생각해서, 보다가 두 번이나 집어 던진 기억이 있다. 필자는 강의를 들은 것이 아니라 혼자서 공부했기 때문에 책의 배경을 이해하지 못했다. 책에 대한 재평가는 SICP와 관련된 메모들과 문서들, 그리고 문서들의 역사적인 맥락을 조금이나마 알게 되면서부터다. 그리고 컴퓨터에 대해 다시 생각하게 되었다.

책에 대해 불평하던 사람들 가운데 나중에 이 책을 다시 보거나 재평가하는 사람들이 꽤 있다. 그 중에는 조엘 스폴스키(Joel Spolsky)도 있었다. 조엘은 조엘 온 소프트웨어(Joel On the Software)라는 블로그로 유명한 사람이다. 조엘의 글 중에 “Perils on the Java School”은 미국 대학의 컴퓨터 학과가 너무 쉬운 것들만 다루려고 해서 수준 저하가 올 것이라는 내용이었다.
조엘 자신이 나이를 먹었다는 확실한 징조가 “요즘 아이들이” 어려워 보이는 것들을 하려고도, 할 수 있다고도 생각하지 않는다는 현상이라고 했다. 컴퓨터 학과에서 자료구조와 함수형 언어 같은 것을 심도 있게 가르치지 않기 때문에 평이한 학생들만을 만들어 내며, 학생들은 교과 과정이 어렵지 않기 때문에 많은 생각을 하지 않고 졸업한다. 그래서 평범한 프로그램만 만들어 내는 평범한 프로그래머만이 나올 것 같다는 내용이다(예전에는 자료구조나 함수형 언어 같은 것이 너무 어려워 고교 시절까지 스스로 우수하다고 생각했던 학생들이 자신의 능력을 진지하게 생각하고 과를 바꾸는 경우가 있었다는 것이다. 과정 자체가 사람들을 솎아내는 기능이 있었다).

이렇게 어려운 교과 중 하나가 MIT 학부 과정의 SICP다. 앞서 말했듯이 과거에는 주요 대학들의 표준 교재였다. 조엘은 블로그에서 이렇게 말하고 있다.

“코스의 난이도는 경이적이다. 처음 5번 정도의 강의에서 스킴(Scheme)의 대부분을 배우며 그것으로 다른 함수를 입력으로 받는 fixed-point 함수를 배울 준비가 끝난다. 펜실베니아 대학의 CSE121에서 나 자신이 이런 과정과 씨름할 때, 전부는 아니더라도 대부분은 강의를 따라갈 수 없었다. 교재는 너무 어려웠다. 교수님에게 이런 과정은 부당하다는 긴 하소연 편지를 썼다. 학교의 누군가가 내 말(아니면 다른 불평자)을 들은 것이 틀림없다. 왜냐하면 이 과정은 이제 자바로 진행되기 때문이다. … 차라리 이런 불평을 듣지 않았으면 좋았을 것이다. … 이제 전공과목에서 4.0을 받느라 머리를 쓸 필요가 없어진 것이다.”

아마존의 서평은 책의 내용이 좋다('great'와 'excellent' 정도의 표현은 흔하다)는 평으로 도배되어 있다. 책의 내용이 지나치게 어렵다는 것을 불평하면서도 그렇다. 사람들이 지적하는 불만 사항은 현실적인 면에 관한 것이다. 이 책은 실전에는 바로 도움이 되지 않는다. 서평 목록 처음에 나오는 피터 노빅(구글의 검색엔진 품질 책임자로 norvig.com에 가면 리스프에 대한 많은 글들을 볼 수 있다)이나 폴 그레이엄(비아웹의 창업자로 '해커와 화가'라는 책을 썼다. www.paulgraham.com에 가면 역시 리스프에 대한 많은 글이 있다) 같은 사람들은 SICP에 대해 극찬 일색이다. 두 사람은 리스프의 중요한 옹호자이고 리스프 세계에서 SICP는 중요한 교과서다. 두 사람 모두 리스프에 대해 중요한 책들을 출판했지만 SICP는 아주 중요한 책으로 평가된다.

SICP의 문화 코드, 그리고 리스프

사람들이 이렇게 생각한다면 SICP는 나름대로 중요한 의미를 지닌다. 이유는 간단하다. 사람들이 중요하다고 생각하는 그 무엇이 있기 때문이다. 책에는 생각할 내용이 많은 것이다. 고전으로 평가 받는 이유는 책이 담고 있는 내용도 있지만 책을 주제로 담론을 전개할 수 있기 때문이기도 하다. 그렇다면 책이 어려워도 고생해가며 읽을 가치는 충분하다고 볼 수 있다. 물론 아닐 수도 있다.

SICP는 한글판으로도 출판된다. 필자도 부분적으로나마 번역 과정에 참여했다. 한글 번역의 문제점과 장점을 다 같이 갖고 있는 SICP의 한글판은 컴퓨터의 고전이 번역되는 것으로 볼 수 있고 중요한 의미를 갖는다. 아무래도 한글판이 나오면 한 명이라도 더 보게 되어 있다. 이를테면 예전에 Computer Organization and Design 같은 고전이 번역되자 사람들이 더 많이 읽고 더 많은 과정에서 교재로 도입했다.
그러나 SICP를 교재로 사용하고 있는 과정은 아무래도 줄고 있다. 조엘이 말한 것과 같은 맥락이다. 그러나 컴퓨터의 중요한 고전을 독학으로 공부하는 것도 가능하다. 이미 학부를 졸업한 사람들이나 관련이 없는 학과를 나온 경우에는 독학 이외에는 방법이 없다(필자 역시 독학 내지 흥미로 공부하고 이 글을 쓰고 있다).

SICP가 쉽다거나 어렵다거나 하는 문제는 교사와 학생의 문제일 수도 있으며(예상보다 높은 수준의 교사가 필요할 것이라는 것이 개인적 의견이다) 리스프나 스킴 자체의 문제일 수도 있다. 커리큘럼이 너무 어렵고 격렬하다고 하여 HTDP(How to Design Programs)와 같은 교과 과정도 있다. 그러나 분명히 이런 격렬함이 이 책을 다른 책과 다르게 만든 그 무엇이기도 하다. 이상한 주입 과정과 사고 과정을 거치면서 분명히 어떤 변화가 나타난다. 그러나 우수한 선생이나 대가에게 배울 수 없다면 우수한 학생 또는 대가학생이라는 방법도 가능하다. 학생이 목표를 선정하고 이리저리 공부하는 방법을 고안하면 된다. 실패율은 높지만 배우는 것도 많다. 아무튼 리스프나 SICP를 배우고 이해하거나 짜보고 싶은 프로그램들이 있었으므로 해봐야 할 과정이었다.

필자는 이 책을 독학하기 위해 여러 가지 자료를 살펴보아야 했고 약간의 시간을 낼 수 있어서 여러 가지를 구경할 수 있었다. 그래서 이번에 쓰는 글은 아마추어 해커의 관점에서 해커 사상의 원류라고 할 수 있는 리스프와 리스프의 중요한 파생 언어 중 하나인 스킴을 살펴보는 것이다.
필자는 컴퓨터로 먹고 살지 않는다. 진지하기는 하지만 생업은 아니다. 아마추어다. 덕분에 하고 싶은 것들을 하고 있어도 누가 뭐라고 하지 않는다. 적극적으로 보자면 컴퓨터는 필자에게 중요한 문화 탐험의 하나다. 그래서 도대체 SICP라는 책을 만들기 위한 문화코드와 재료가 무엇인지, 그리고 역사(history)와 사람들의 이야기(biography)가 어떤 것인지가 더 중요하다. 이런 날줄과 씨줄로 리스프의 문화 코드가 만들어진 것이기 때문이다. 그래서 필자의 이야기는 완전한 전문가의 이야기도 아니며 그저 진지한 아마추어의 이야기 정도로 파악해주면 좋을 것이다.
그래서 SICP라는 책을 해설하는 것이 아니라 SICP를 만든 자료들과 근거들이 어떠한 맥락에서 어떤 경로를 거쳐 발전해 왔는가를 보는 것이 필자의 접근법이다(이러한 접근법은 시간이 조금 더 든다).

SICP의 그 이전에 리스프라는 더 거대한 덩어리가 있었다. 여기에도 문서들이 보존되어 있다. 필자는 코드만 보고 '아하!' 하고 모든 것을 이해하는 천재가 아니기 때문에 이것저것을 살펴보아야 하고 문서가 있으면 다 이해하지는 못하더라도 읽어보려고 했다. 때로는 코드만 보는 것보다는 더 이해가 빠를 수도 있겠다. 자칫하면 재미가 없을 수도 있으므로 접근방법을 미리 설명하는 것이다. 그러니까 필자의 글은 어려운 SICP를 이해하기 위한 주변 자료들을 제시하고 나름대로 설명해 보고 싶은 것이다. 실제로 리스프나 스킴이 오랜 세월 동안 진화해 왔기 때문에 역사성을 무시하지 못한다. 그래서 역사적 자료와 문헌들을 사람들의 이야기와 몇 줄의 코드에 섞어서 이야기할 수밖에 없다. 교양과목들처럼 말이다.

거슬러 살펴본 리스프의 탄생

SICP는 개정 과정을 몇 차례 거쳤는데 SICP는 리스프가 아니라 리스프의 방언인 스킴으로 되어 있다. 그리고 스킴을 만든 사람은 가이 스틸(Guy Steele)과 제럴드 서스만(Gerald Sussman)이다. 그 전까지의 리스프와 스킴의 차이점이라면 스킴은 칼 휴이트(Carl Hewitt)의 액터 모델(actor model)을 구현하기 위해 만들었으며 그 이전의 다른 리스프 구현의 전통을 이어받았다는 점이다.
그런 노력의 와중에서 전통적인 리스프에 대한 심각한 의문 제기가 있었고 일련의 사고 과정은 람다 페이퍼(lambda paper)라는 이름으로 나타난다. 결국 여러 편의 논문들이 나오고 SICP라는 책으로 만들어지기까지는 10년의 세월이 필요했다. 1970년대 초반부터 작업이 시작되어 1980년대 중반에야 책으로 나온 것이다.

이른바 이들이 발표하는 람다 페이퍼라는 것을 사람들은 좋아하기도 했고 싫어하기도 했다(글들은 http://library.readscheme.org/page1.html에 있다). 그 중 "The Art of the Interpreter of, the Modularity Complex(Parts Zero, One, and Two)"라는 유명한 문서가 많은 사람들에게 영향을 주었다. 그 외에도 "Lambda: The Ultimate Imperative"와 “Lambda: The Ultimate Declarative”, 그리고 “Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO”라는 글들도 유명하지만 사람들은 이 글들을 별로 좋아하지 않았던 것 같다. "Lambda: The Ultimate X” and “X considered Harmful"이라고 풍자하는 글들도 있었다고 한다.

중요한 내용이라 언급하지 않을 수 없는 액터 모델에 대해서도 설명하면 좋겠지만 지면상 불가능하다. 일단 위키 백과의 소개 글 정도면 큰 그림을 이해하는 데는 충분할 것이다. 휴이트와 대화하면서 람다가 액터와 같다는 것을 확인한 서스만은 정말로 좋아했다고 한다. 나중에 앨런 케이(Alan Kay)와 휴이트가 만나면서 스몰토크(smalltalk) OOP(Object-Oriented Programming)의 메시지 모델과 액터 모델은 서로 많은 영향을 주고받았다.

1970년대 스킴이 람다 페이퍼를 중심으로 사람들의 관심과 비난을 한데 얻던 시절, 서스만과 함께 스킴에 대한 연구를 진행하던 가이 스틸은 당시를 아주 재미있던 시절이라고 나중에 회고했다. 스틸은 당시 대학원을 다녔다. 석사 과정에 다니는 학생이 젊은 교수와 함께 언어의 중요한 틀을 만든 것이다. 스틸은 나중에 스킴 컴파일러에 대한 논문을 쓰고 D. Hillis의 Thinking Machine으로 자리를 옮겼기 때문에 SICP가 출판될 때는 동료인 Harold Abelson이 공동 저자로 되어 있다(가이 스틸은 현재 썬(Sun)의 연구진으로 있다).
기존의 리스프에 대해 문제점을 제기한 가이 스틸은 나중에 CLTL(Common Lisp The Language)라는 리스프 드래프트의 작성자가 되었다. 드래프트를 만들며 리스프의 많은 구현들의 장단점을 취합했다. 그만큼 실력이 있었다(스틸은 C 표준안과 자바 표준 그리고 포트란의 표준안을 작성했거나 위원회의 주요 멤버이기도 했다).

스킴이 그전까지의 리스프와 중요한 차이를 보인 것은 람다에 대한 중요성을 부각시키고 람다의 행동에 대한 엄밀한 분석을 이룬 것이다. 테일 리커전(tail recursion)이나 렉시컬 스코프(lexical scope)와 같은 것도 중요한 차이점이다. 람다에 대해 생각한 것은 앞의 오리지널 람다 페이퍼라는 문서들이 바로 그 증거이며 SICP에는 이 문서들의 내용이 녹아 들어있다. 진지한 독자들이라면 호기심으로라도 람다 페이퍼들을 살펴볼 필요는 충분히 있겠다.

Trackback 0 Comment 1
2009.03.26 22:03

변수에 대해 생각해보기 (2) Teach Yourself Scheme in Fixnum Days

오늘은 지난번의 동적 바인딩 생각해보기 (1) 에 대해 변수에 대해 생각해보기 (2)라는 제목으로 적어 봐야 할 것 같다.
오늘은 let 에 대한 부분을 정리하기 위해 스킴의 문헌 Teach Yourself Scheme in Fixnum Days 의 5장을 인용한다.

스킴의 교과서로 출판된 것은 아니지만 일정한 날자안에 스킴을 배울 수 있게 해준다는 책이다.
일단 책으로 여겨야 할 것 같다.





Teach Yourself Scheme in Fixnum Days 라는 제목으로 보아서는 킬러 앱스인데 사실 그렇게 많이 보지는 않는다. 스킴의 사용자들이 한정되어 있기 때문이다.  그리고 21 days가 아니고 fixnum days라고 적은 것은 들여다보고 있으면 언젠가는  이해할 수 있을 것이라는 사실을 알기 때문이라고 생각한다.  언제인가는..
아무튼 책들을 많이 펼치지 않고 스킴의 많은 부분을 요약할 수 있다. 그 이유는 이 글(책)이 r5rs의 요약본이나 마찬가지기 때문이다.  

결론은 매우 잘 쓴 책이며 간결하게 정리되어 있다. 예제들도 적당하다. 분명히 도움이 되는 사람들도 있을 것이다. 가끔 비교 검토할 가치는 충분하다.

SICP의 무서움은 이런 절차를 무시하고 바로 총을 주고 전쟁터로 보내는 방식이다. 간결하지도 않으며 예제들도 어렵다. 그리고 중요한 차이점들은 연습문제로 남겨 놓는다. 설명이 연습문제에 있는 경우도 있으며 전혀 친절하지도 않다.
(하지만 둘 다 좋은 책이다. 가르치는 방법도 여러가지이며 배우는 방법도 여러가지이고 대가 학생은 선생을 찾아 다닌다. )

http://www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html



5

Lexical variables

스킴의 변수들은 렉스컬 스코프를 따른다.  아래의 예제들은 람다 인자를 사용한 지역변수들이다. 이들은 프로시저 호출에서 바인딩을 일으키며 그 범위는 프로시저의 몸이다.

(define x 9)
(define add2 (lambda (x) (+ x 2)))

x        =>  9

(add2 3) =>  5
(add2 x) =>  11

x        =>  9

글로벌 x가 있고 로컬인 x 가 있다.  그리고 x 라는 변수를 받는 add2 가 있다.  먼저 글로벌 x 는 9 이다.  그 다음 add2에 2를 입력하면 5가 나오고 x를 입력하면 9에 2를 더한  11 이 나온다.  로컬의 x 와 글로벌x는 다르기 때문에 글로벌 값은 영향받지 않고 9가 나온다. 당연해 보인다.  

그다음의 예제 set! 을 톱레벨에서 실행하면 x의 값을 20을 바꾼다.
 
(set! x 20)

글로벌 변수 x 는 이제 9에서  20이 되었다.

만약  set! 이 add2의 몸체 안에서 작용하면 어떻게 될까?

(define add2
  (lambda (x) (set! x (+ x 2))
    x))

set! 은 에제 로컬 변수에 2를 더하고 그 값을 되돌린다.  효과면에서 새로운  add2는 변한 것이 없다.

이제  add2 에 글로벌 x를 적용하자.

(add2 x) =>  22

add2안에서 set! 이 작용한 것은 로컬변수이다. (x는 프로시저를 만들면서 같이 만들어진 로컬 변수다.)

그래서 글로벌 x는 변하지 않는다.

x
=>  20

여기까지도 뻔한 내용이다.

아래는 로컬 x 가 그로벌 변수를 샤도우 했다는 내용이다. 이  내용은 sicp 3장의 시작부에 잘 나타난다.

Note that we had all this discussion because we used the same identifier for a local variable and a global variable. In any text, an identifier named x refers to the lexically closest variable named x. This will shadow any outer or global x's. Eg, in add2, the parameter x shadows the global x.

그러나 로컬 변수가 아니면 이야기는 달라진다.

A procedure's body can access and modify variables in its surrounding scope provided the procedure's parameters don't shadow them. This can give some interesting programs. Eg,

(define counter 0)

(define bump-counter
  (lambda ()
    (set! counter (+ counter 1))
    counter))

The procedure bump-counter is a zero-argument procedure (also called a thunk). It introduces no local variables, and thus cannot shadow anything. Each time it is called, it modifies the global variable counter -- it increments it by 1 -- and returns its current value. Here are some successive calls to bump-counter:

(bump-counter) =>  1
(bump-counter) =>  2
(bump-counter) =>  3
여기서는 로컬 변수가 없고 counter는 글로벌 변수를 참조한다.  (이런 용법을 free 변수라고 하며 
bump-cpunter는 글로벌이자 free변수인 counter를 증가시킨다. free변수는 람다에 의해 바인딩되지 
변수다.  프리변수는 많은 언어에서 적법하지 않은 요소지만 리스프에서는 예전부터 사용한 변수다.  
나중에 funarg를 정리하면서 반드시 생각해 보아야 할 숙제이기도 하다. )
 

5.1  let and let*


아래의 내용은 특별한 것이 없다. let과 let*의 차이점이다.  let* 이 사실상 let (let ( 처럼 let 안의 let  형태라는 것은 sicp의 연습문제에도 나온다.  sicp를 보지 않아도 아래의 예제 정도면 충분하다.

Local variables can be introduced without explicitly creating a procedure. The special form let introduces a list of local variables for use within its body:

(let ((x 1)
      (y 2)
      (z 3))
  (list x y z))
=>  (1 2 3)

As with lambda, within the let-body, the local x (bound to 1) shadows the global x (which is bound to 20).

The local variable initializations -- x to 1; y to 2; z to 3 -- are not considered part of the let body. Therefore, a reference to x in the initialization will refer to the global, not the local x:

(let ((x 1)
      (y x))
  (+ x y))
=>  21

This is because x is bound to 1, and y is bound to the global x, which is 20.

Sometimes, it is convenient to have let's list of lexical variables be introduced in sequence, so that the initialization of a later variable occurs in the lexical scope of earlier variables. The form let* does this:

(let* ((x 1)
       (y x))
  (+ x y))
=>  2

The x in y's initialization refers to the x just above. The example is entirely equivalent to -- and is in fact intended to be a convenient abbreviation for -- the following program with nested lets:

(let ((x 1))
  (let ((y x))
    (+ x y)))
=>  2

The values bound to lexical variables can be procedures:

(let ((cons (lambda (x y) (+ x y))))
  (cons 1 2))
=>  3

Inside this let body, the lexical variable cons adds its arguments. Outside, cons continues to create dotted pairs.

5.2  fluid-let


그런데 렉시컬 변수도 때로는 일정한 값으로 유지되는 편이 나을지도 모른다.  fluid -let 은 이런 경우에 사용된다.
fluid 라는 이름은 지난번에 설명한 다이나믹 바인딩과 유사한 성격이다.
fluid-let 은 글로벌 변수를 가리는 (샤도우하는 ) 것이 아니라 counter를 임시로 99로 세팅한다.

(fluid-let ((counter 99))
  (display (bump-counter)) (newline)
  (display (bump-counter)) (newline)
  (display (bump-counter)) (newline))

100 
101 
102 

 fluid-let 을 사용한 식의 계산이 끝나면 global counter의 값은 다시 원래로 돌아간다.

counter
=>  3

fluid-let 은 let과 다르다. let처럼 완전히 새로운  렉시컬 변수를 만드는 것이 아니라 현재의 렉시컬 변수의 바인딩만 바꾼다.

이제  다시 원점으로 돌아와서 let을 사용한 예제를 돌려보자.

(let ((counter 99))
  (display (bump-counter)) (newline)
  (display (bump-counter)) (newline)
  (display (bump-counter)) (newline))

결과는

4

5
6

글로벌 변수  counter는 아무런 영향을 받지 않았다. bump-counter를 호출하기는 했으나 bump-counter의 counter는 글로벌 변수를 참조했으며 아무런 영향이 없었던 것이다. 그러나 fluid-let은 일시적으로 모든 counter 변수의 바인딩을 유지했다.

(이것은 지난번의 dynamic 변수 예제를 보고 다시 한번 대조해 보면 이해할 수 있을 것이다.)
 

Ie, the global, which is initially 3, is updated by each call to bump-counter. The new lexical variable counter, with its initialization of 99, has no impact on the calls to bump-counter, because although the calls to bump-counter are within the scope of this local counter, the body of bump-counter isn't. The latter continues to refer to the global counter, whose final value is 6.

counter =>  6

counter는 이제 6이 되었다. 99로 세팅한 로컬 변수는 아무런 영향을 미치지 못했다.

아주 좋은 예이긴 하지만 실감이 나지 않을지도 모른다. 하지만  중요한  차이점이다.
좋은 예를 만들어 내는 것은 중요한 일이지만 일단 이 정도 예제로 대부분 이해하고 있으니 오늘은 여기까지 ..

(fluid-let은 비표준형의 스페셜 폼이며 마크로로 만들었다. 8.3 장에 만드는 방법이 있다.) 

Trackback 0 Comment 0
2009.03.23 21:06

피터 노빅의 paip

사람들의 공포심과는 달리 그다지 어려운 책은 아니라고 생각한다.  노빅은 이 책은 인공지능 교과서로서는 성공하지 못했고 (노빅의 유명한 AIMA 가 더 성공적이었다.) 리스프로 인공지능 프로그램을 짜는 법을 가르치는 일에는 성공적이라고 평했다. 

개인적으로는 도전적인 주제를 던진 좋은 책이라고 생각하며 아직도 읽고 있다.  이 책의 평가도 양분되지만 비평적인 글중에는 prolog 인터프리터에 너무 집착한 것 같다는 평도 있다.
그러나 프롤로그의 영향력은 너무나 강력했다.

가격은  비싼 편이다.  (74 달러) 아마존에서는 ansi common lisp + aima 까지 묶어 246달러에 팔고 있다. 

책을 소개하는 순서로 보면 원래는 더 쉬워보이는  Graham의 ansi common lisp 을 소개해야 하는 것이 마땅하다. 이 책은 ACL 이라고도 부른다.  많은 사람들이 좋다고들 한다.  저자의 유명세와 비교적 새롭게 나온 프리미엄을 모두 갖고 있다.

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp

by Peter Norvig

A book published by Morgan Kaufmann, 1992.
Paperbound, xxviii + 946 pages, ISBN 1-55860-191-0.
As seen on TV!   Rated 5 stars at Amazon.

Contents


I: Introduction to Common Lisp
1. Introduction to Lisp
2. A Simple Lisp Program
3. Overview of Lisp
II: Early AI Programs
4. GPS: The General Problem Solver
5. ELIZA: Dialog with a Machine
6. Building Software Tools
7. STUDENT: Solving Algebra Word Problems
8. Symbolic Mathematics: A Simplification Program
III: Tools and Techniques
9. Efficiency Issues
10. Low Level Efficiency Issues
11. Logic Programming
12. Compiling Logic Programs

13. Object-Oriented Programming
14. Knowledge Representation and Reasoning
IV: Advanced AI Programs
15. Symbolic Mathematics with Canonical Form
16. Expert Systems
17. Line-Diagram Labeling by Constraint Satisfaction
18. Search and the Game of Othello
19. Introduction to Natural Language
20. Unification Grammars
21. A Grammar of English
V: The Rest of Lisp
22. Scheme: An Uncommon Lisp
23. Compiling Lisp
24. ANSI Common Lisp
25. Troubleshooting

Peter Norvig

Trackback 0 Comment 0
2009.03.21 21:10

동적 바인딩 생각해 보기 (1)

리스프에서 아마 가장 많은 문제를 일으킨 부분이 동적 바인딩과 FUNARG 문제일 것이다.


14.16 DYNAMIC SCOPING

14.16 은 gentle intro to symbolic computation 의 사실상  마지막 부분에 해당한다. 몇페이뒤의 4.18에서 책의 본문이 끝나기  때문이다.  이해하기가 조금 애매한 부분이기도 하다.  아무튼 개인적인 생각으로는 이 책의 설명이 제일 나은 것 같다. 다시 말하지만 개인적인 생각이다.

책의 마지막에 이르기까지 동적(dynamic) 스코프를 사용하지 않고 설명을 했고 저자는 마지막 부분에서 렉시컬 스코프와 동적 스코프의 구분을 하고 있다.

대부분의 언어들은 렉시컬 스코프를 적용하고 있고 동적 스코프는 별로 쓰이지 않는다.
그러나 한때는 리스프에서 동적 스코프가 표준이었다. 

동적 스코프에 대해서는 많은 오해가 있기 때문에 설명할 필요가 있다.   글을 쓰고 있는 사람도 예외가 아니다. 그러나 생각해 보면 매우 자연스럽기도 하다.  과거의 리스프 해커들은 동적 스코프를 썼을 뿐만 아니라 응용하고 기법화하기 조차 했다.

책의 해설을 잠깐 옮기면 foo 라는 함수가 X라는 변수에 접근하려면 foo라는 함수는 X라는 변수가 정의된 문맥 안에 존재해야 한다는 점이다.  만약 foo가 toplevel 에서 정의되었다면 foo가 접근할 수 있는 변수는 글로벌 변수와 함수안에서 정의된 로칼변수뿐이다.  그러나 bar 라는 함수안에 어떤 람다식으로 정의된 함수가 있다면 이 함수는 bar의 변수에 접근할 수 있고 자신의 로컬 변수에도 접근할 수 있다. Bar의 바깥에 정의된 함수들은 bar의 변수들에 접근할 수 없다,

동적 변수는 때로 스페셜변수라고도 부른다. 일단 변수 이름이 스페셜로 선언되면 이 변수는 어떤 함수에 대해서도 로컬변수가 아니다.  (이점은 정말 중요하다.) 변수는 어디서나 접근할 수 있는 것이다.  그러나 렉시컬 스코프의 변수는 정의된  몸체에서만 접근할 수 있다. 

스페셜 변수를 정의하는 방법의 하나는  DEFVAR macro 를 사용하는 것이다. 이를테면 (defvar birds)

이제 예를 들어보자
BIRDS 는  동적 스코프의 변수이고 FISH 는 렉시컬 스코프의 변수라고 하자.이제 이들에게 적당한 값을 주고 이들을 사용하는 함수도 하나 만들어 보자.

먼저 동적 변수를 하나 선언한다.
(defvar birds)

적당한 값을 만든다.

(setf fish ’(salmon tuna))
(setf birds ’(eagle vulture))


(defun ref-fish ()
fish)

(defun ref-birds ()
birds)

두개의 함수는 동적인 변수와  렉시컬 변수를 돌려준다.

(ref-fish) 
--> (salmon tuna)
(ref-birds) 
--> (eagle vulture)

이제 렉시컬 변수를 시험하는 함수를 만들어 보자.

(defun test-lexical (fish)
(list fish (ref-fish)))

인자로 받은 fish와 reffish 함수의 결과를 다시 리스트로 만든다.

> (test-lexical ’(guppy minnow))
((GUPPY MINNOW) (SALMON TUNA))

결과는 로컬 변수 fish를 돌려준다. 그리고 이 로컬 변수는 ref-fish에서는 접근할 수 없는 값으로 톱레벨에서 정의된 ref-fish는 글로벌 환경의 fish를 돌려준다. 그결과 로컬 변수로 (GUPPY MINNOW)를 글로벌 변수인 (SALMON TUNA)를 보여준다.

각각 다른 스코프를 쓰고 있다는 것을 보여준다.
책의 437 페이지에 있는 그림을 보면  동작 원리를 eval-trace 그림으로 보여준다.


동적스코프를 글로벌 변수와 혼동해서 설명하는 사람들이 많지만 사실은 다르다.

동적 스코프의 경우 (이전에 birds를 동적변수로 정의했다.)  결과는 하나는 같고 하나는 달라진다.  이차이는 defvar가 birds를 스페셜 변수로 만들어 놓았기 때문이다.

먼저 함수를 정의하자 . 이 함수는 birds를 사용한다.

(defun test-dynamic (birds)
(list birds (ref-birds)))

인자로 '(robin sparrow)를 사용했다.

> (test-dynamic ’(robin sparrow))

결과는  다음과 같다.
((ROBIN SPARROW) (ROBIN SPARROW))

  ref-birds가  주어진 인자와 같은 값을 낸 것이다. 

식의 계산이 끝나고 ref-birds는  원래의 값을 다시 돌려준다. 수행중에는 아니었다.
> (ref-birds)
(EAGLE VULTURE)

이런 이상한 답을 내어준 것은 다름이 아니다. TEST-DYNAMIC으로 진입하면서 스페셜 변수로 정의된 BIRDS 가 만들어진 것이고 몸체를 빠져 나가기 전까지 BIRDS는 이 값을 갖게된다. TEST-DYNAMIC 의 밖에 있는 함수 (ref-birds) 에서도 마찬가지다. BIRDS 라는 이름의 원래의 글로변 변수는 동적인 변수가 있는한 접근가능하지 않다.  test-dynamic  함수를 빠져 나오면서 함수의 인자인 BIRDS가 사라지면  원래의 BIRDS 값이 복원된다.

동적이라는 이름이 붙은 것은 REF-BIRDS의 BIRDS라는 이름의 변수의 값이 한 변수에 영구적으로 고정된 것이 아니라는 점이다. FISH 의 경우에는 고정되어 있었다, 그러나  BIRDS는 TEST-DYNAMIC로 들어가며 변수의 값이 새로 고정되고 나중에 원래의 값으로 돌아갔다. 

(이 과정은 바인딩이 일어날 때마다 항상 변한다. 예측이 불가능한 경우도 있다. 만약에 중간에 다른 바인딩이 일어났으면 도대체 어떤 BIRDS를 바인딩하고 있을지 정말 애매하다.

그리고 한가지 더 첨부하자면 birds는 함수의 범위를 무시하고 글로벌 함수인 ref-fish의 동작까지 영향을 주다가  영향력을 상실했다.)

스페셜 변수는 조심스레 사용되어야 한다. 초기의 리스프들에서  동적 스코프가 기본이었을 당시 한 함수는 다른 함수가 만든 변수의 값을 바꾸는 경우가 있었고 드물지만 문제를 일으키곤 했다.  렉시컬에서는 이런 일은 일어나지 않는다. 하지만 가끔씩은 동적 스코프의 변수의 사용이 합당한 경우가 있고 이들은 4.18에서 볼 것이다.


- 이제 4.16을 이해했으면 4.18을 이해하는 것은 아무런 문제가 없다.
이런 동적 바인딩과 렉시컬 바인딩을 차이나게 하는  근본적인 이유는  새로운 환경을 만드는 방법에 달려있다.

BIND함수가 환경을 어떻게 바인드하느냐에 따라 달라진다.
나중에 TAOI에서 자세히 설명하겠다.

만약 그때까지 기다리기가 어려우면 다른 자료들을 열심히 찾아보면 된다.
(그러나 이 글을 다시 한번 읽게 될 것이다. )
Trackback 0 Comment 0
2009.03.21 17:27

anatomy of lisp


sicp의 참고문헌에 맨 위에 뜨는 책이다.
저자의 이름은 John Allen 이다.
절판되었으나 아마존에서 구할 수 있다. 가격은 110 달라에서 150 달러 사이인 것 같다.
ACM classic 20선중에 들어 있기도 했다. 




책의 출판년도는 1978년으로 되어있거나 1979년으로 되어 있다.
Knuth가 책의 조판을 도와주었다고 적혀 있다. LaTEK 의 초기 버전으로 만들어져서 인쇄된 결과물이 엉망이다.

이책의 특징은 프로그램을 어떻게 분석하는가를 알려준다. 
프로그래밍이 아니라 컴퓨테이션을 가르친다고 보면 된다.
알렌은 이 책으로 학생들을 위한 입문과정을 가르쳤다.
이 책을 가르칠 수 있으려면 아주 우수한 강의자가 필요한 것은 분명하다.

책의 난이도는 상당히 높다.  수식을 보면 공포스러울 정도다. 책이 중시하는 것은 mathematical thinking이다.
같은 내용이라도 수식처럼 만들어 놓은 식을 보면 무서운 것은 아마 나만의 일은 아닐 것이다.
정교함의 댓가라고 할 수 있다. 

스킴의 저자들은 알렌으로부터 많은 영향을 받았다. 알렌은 초기 리스프의 구현멤버이기도 했다. 
책의 평가는 극과 극이다. sicp와 마찬가지다. 

리스프에 대한 클래식이고 정교한 동작에 대해 관심이 있는 사람은 읽어 볼만한 책이다.
혹자는 Lisp In Small Pieces가 요즘 시대에 맞다고 하는데 이 책은 시대와는 상관이 없다.
정교하고 엄밀한 evaluation 에 대한 여러 방향의  분석을 시도한다.



Trackback 0 Comment 0
2009.03.20 23:55

A Gentle Introduction to Symbolic Computation

http://www.cs.cmu.edu/~dst/LispBook/index.html

David S. Touretzky의 책으로 마음의 여유만 있으면 쉽게 리스프를 배울 수 있는 좋은 책이다. 그레이엄의 유명한 on lisp은 이 책에 나오는 마크로 부분이 부족한 부분이 있다고 생각하던 David S. Touretzky 와 그레이엄의 공저라고 볼 수 있다.
물론 ansi common lisp 는 좋은 책이지만 이 책은 공짜라는 점에서 그리고 친절한 설명이 지나칠 정도라는 점에서 아주 좋은 책이다.  그러나 어떤 부분의 설명은 아주 예리하다. 너무 쉽다고 평가절하하는 리뷰를 믿지 않았으면 한다.
(개인적인 의견을 덧붙이자면 ansi common lisp 은 날카롭지만 비싸며  practical common lisp은 가끔 예리하지 않은 주제로 혼동을 준다.  하지만 둘다 좋은 책이다.  그 두책만큼 이 책도 우수하다. 사람들이 좋다고 하는 리스프 교과서들은 사실 어느 정도는 다 비슷하다. 이 정도로도 초보자들은 몇개월은 재미있게 읽을 수 있다.
한글로 된 쉽고 우수한 교과서가 있으면 좋겠지만 없는 것 같다. )

 

 

Common Lisp: A Gentle Introduction to Symbolic Computation

David S. Touretzky


This book may be distributed in hardcopy form, for non-profit educational purposes, provided that no fee is charged to the recipient beyond photocopying costs. All other rights reserved. You may not redistribute the Postscript file, e.g., you may not put a copy on another web page, or include it on a CD-ROM.

Entire book -- Postscript (1.75 MB file)

Entire book -- PDF (1 MB file)

Free software accompanying this book is also available.

Materials provided by David S. Touretzky, Carnegie Mellon University.


Trackback 0 Comment 0
2009.03.20 23:40

lambda the ultimate imperative 10-13 페이지 생각해 보기 (1)

지난번의 Y cominator 만큼이나 골치아픈 문제이긴 하지만 람다 페이퍼를 관통하는 큰 주제는 

- lexical scope 
- continuation 과  tail recusion 

라고 생각한다.  이 주제는 리스프와 그 다음에 나오는 함수형 언어들에 큰 영향을 미쳤다. 
SICP 보다 조금 어려운 과제이긴 하지만 이런 성찰을 거쳐서 SICP 가 만들어진 것은 분명하다. 
얘전의 ibm dw 에 대한 리라이팅 이긴 하지만 정리하는 과정은 중요하다,

 

lambda the ultimate imperative 10-13 페이지 생각해 보기 (1)


이글은 이전의 IBM의 디벨로퍼웍스 스페셜 이슈 “컴퓨팅 기술의 원형 탐험, Part 4: 제어 흐름을 다루는 또 다른 방법, 컨티뉴에이션 ” 이라는 글의

( http://www.ibm.com/developerworks/kr/library/s_issue/20080617/  ) 전후의 내용을 다시 한 번 적어 보는 것이다.  “Best writing is re-writing” 같은 어떤 미련한 작가의 후렴을 되뇌이면서 조금 다른 각도에서 생각해 본다.


3. Continuation


람다는 함수이기도 하지만  일종의 제어구조와 환경변경자로 사용되는 경우도 많다.  


우선 block 의 이야기부터 하자.  블록의 가장 간단한 구조는 2개의 식으로 구성되는 경우일 것이다.


(block S1 S2)

-->((lambda (dummy) s2 ) s1)


(

확장하면 

(block S1 S2 … Sn)은 (block S1 (block S2 (... (block Sn-1 block Sn) ...))처럼 적을 수 있겠다)


이런 구조로 다음과 같은 식을 생각할 수 있다.


((lambda (dummy) (print 4) ) (print 3))


인자 dummy를 계산하면 (print 3) 그 다음에는 (print 4)가 수행된다. side effect 다.

사이드이펙트를 생각하지 않으면 두 개의 식이 연속적으로 수행될 이유는 없다.

사이드이펙트가 있다는 것은 무엇인가 변하는 것으로 여기서는 프린트문이 무엇인가를 찍어낸 것이다. 그러니 람다는 일종의 환경변환자이다.


제어구문으로서 람다를 생각할 수 있다.  예전에 설명한 것처럼 imperative programming의 최종적인 형태는 CPS일 것이다. 그러나 람다는 일종의 CPS 처럼 움직인다.


우선  (define bar (lambda (x y) (f x y))) 같은 식을 생각해 보자. 이 람다식에 인수를 적용하는 식 (bar foo etc)는 foo와 etc를 앞서 정의한 bar에 적용한다. 이때 foo와 etc가 람다 식이라면 먼저 foo와 etc를 계산한다. foo를 먼저 etc를 나중에 계산한다. 결과적으로 내부의 (f x y)에 다시 대입되기 이전에 이미 한번 계산이 일어난다!  람다는 이미 환경을 변경시키는 식 foo 와 etc 를 갖고 있을 수도 있고 그렇다면 의도했건 하지 않았건 일종의 블록문을 수행한 것으로 볼 수 있다. 아니면 인자를 계산하다가 삼천포로 빠져서 다시는 돌아오지 않을 수도 있다.  그러니 람다는 제어구조이기도 하다. 우리가 질리도록 보아온 fact는 일종의 반복문으로 볼 수 있다. 람다는 loop 와 같은 제어문이기도 하다.


 foo와 etc를 미리 계산하는 것은 s1과 s2를 계산하는 패턴과 다르지 않다. 원래는 foo의 계산된 값이 x이고 etc의 계산된 값을 y에 적용하기 위한 계산이었으나 이것들이 함수 호출을 일으키면 일종의 시퀀셜 블록처럼 작용하는 것을 알 수 있다. 물론 값을 되돌릴 준비를 하는 것이 다르다. 계산이 끝나면 이 값들은 스택같은 곳에 저장되어 f 에 적용될 준비가 끝난다. f는 계산이 끝나면 값을 되돌리기도 하지만 아무 일도 하지 않을 수도 있다.


오늘의 이야기는 이런 이야기를 조금 더  풀어보는 일이다.

제어 구조로서의 람다는 “컴퓨팅 기술의 원형 탐험, Part 8: 제어 흐름의 패턴“

http://www.ibm.com/developerworks/kr/library/s_issue/20081028/ 를 읽어 보는 것이 좋겠다.



3.1 CPS recursion


예전의 IBM의 디벨로퍼웍스 스페셜 이슈 “컴퓨팅 기술의 원형 탐험, Part 4: 제어 흐름을 다루는 또 다른 방법, 컨티뉴에이션 ”

( http://www.ibm.com/developerworks/kr/library/s_issue/20080617/  )

에서는 다음과 같은 내용을 보여 주었다.


CPS의 예제에서


fact는 컨티뉴에이션 함수인 answer에 값을 전해주는 역할을 한다. 결국 나중에 일을 처리할 함수는 answer다. 지난 회 예제의 긴 식에서 answer는 람다 함수 (lambda(x) x)다. 그러니까 받은 값이 무엇이든 그 값을 그대로 되돌리는 함수이고 이 answer에 적용할 값을 건네준 것이다. answer는 끝에서 계산된 값을 그대로 되돌린다. 이제 원래 예제를 생각해보고 설명을 덧붙이자.



(define fact (lambda n c)

                (if (= n c 1 )

                        (fact (- n 1)

                                (lambda (a) (c (* n a)))))))


이제 이 fact 에 3을 적용해 보자. (fact 3 answer)라는 식을 입력하였을 때 위의 식은 컨티뉴에이션인 answer에 결과를 적용한다.


이 프로그램을 스킴에서 실행하면 대략 다음과 같이 된다. 컨티뉴에이션 패싱 스타일(continuation passing style)의 원시적인 모습이다. 계산의 중간 과정들을 옮겨본다.




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




마지막 식의 a는 결국 길어진 식을 인자로 받는다. 이 간단한 식에서 컨티뉴에이션 c는 변하지 않으며 n은 계속 감소한다. 자꾸 길어지는 식은 결국 앞으로 계산할 식이 늘어나는 것이니 늘어나는 식을 받는 람다 함수는 n을 a에 곱하고 함수 c에 적용한다. (c (* n a)) 부분이 계속 늘어난다. 별것 아니지만 지금까지의 방법과 다른 것은 사실이다. 실행 문맥이 전해진 것이다.



앞의 fact는 결국  n이 0이면 c에 1을 적용한다.

(c 1)


n이 0이 아니면 fact는 (fact (- n 1) (lambda (a) (c (* n a))))를 계산한다. 그러니까 n에서 1을 뺀 값과 새로운 람다 함수를 부른다. 그러면 함수의 정의에서 fact (lambda (n c)...)의 n에는 (- n 1)이, c에는 (lambda (a) (c (* n a)))가 주어진다. 물론 (lambda(a) (…로 시작하는 c는 계속 길어진다. 그러다가 (lambda (a) (…에 적용할 값이 주어지면 계산이 일어나면서 줄어든다. 위 예제에서는 c에 1을 적용하는 경우다. 그러면 이번 예제의 answer 라고 주어진 c는 (lambda (x) x)로 정했으므로 1을 되돌린다. 그리고 기다란 람다식이 계산을 일으키며 줄어든다. 스택이 늘어난 대신 람다식의 중첩(nesting)이 일어났다.


이 방법이 컨티뉴에이션을 전달하는 재귀의 예제다. 조금 생소하지만 강력한 패러다임이다. 함수형 언어의 표기법과 람다 함수의 생소함이 독자에게 낯선 느낌을 줄 뿐이다. 아무튼 독자들이 재귀와 스택으로 만들어진 예제들로만 생각할 필요는 없다는 것이 중요하다. 중요한 내용은 계산의 컨트롤을 전달하는 일과 접근 방식이다. 컨트롤은 다른 함수를 부르는 것으로 전해진다. Hewitt이 말한 액터(actor)의 역할과 같은 것이다. 컨트롤은 다른 함수를 부르는 것으로 전달되며 정작 fact에서 계산된 것은 아니다. 이것이 가장 중요한 아이디어라고 스틸과 서스만은 말하고 있다.


모든 것을 이해하지는 않았더라도 컨티뉴에이션이 어떤 것인지는 대략 알게 되었다고 가정한다면 이제 다시 다음과 같은 내용을 생각할 수 있겠다.


일단 fact의 내부에서는 어떤 요소도 리턴값을 되돌리지 않았다. 리턴값을 되돌린 것은 컨티뉴에이션 함수인 answer다. 이전 예제에서 마지막 문장 (answer 6)이 값을 되돌린다. answer는 (lambda (x) x) 같은 함수다.


CPS(Continuation Passing Style)에서 생각한다면 스택과 함수의 리턴값에 익숙한 관행을 바꾸어 생각하는 접근이 몇 가지 더 있다.


우선 앞의 예제에서 =, -, *는 값을 되돌리는 프리미티브를 사용했다. 그러나 이것은 프리미티브의 특성이다. 컨티뉴에이션을 사용하는 새로운 프리미티브를 만들면 프로그램의 스타일을 바꿀 수 있다. =, -, *의 새로운 구현을 ==, --, **처럼 표기하자. 이것들의 마지막 요소는 컨티뉴에이션이다. ==는 두 개의 컨티뉴에이션을 받아 조건이 참이면 앞의 컨티뉴에이션을, 나머지 경우는 두 번째 컨티뉴에이션을 부른다.


이런 프리미티브가 구현된다면 앞의 fact를 아래와 같이 표기할 수 있다. 아주 이해하기 쉽고 명료한 코드다(단 프리미티브가 구현되어 있어야 한다).



(define fact

        (lambda (n c)

                (== n 0)

                        (lambda () (c 1))

                        (lambda ()

                                (-- n 1

                                        (lambda (m)    

                                                (fact m (lambda (a) (** a n c)))))))



앞서의 길어지는 람다와 위에서처럼 CPS로 작성한 코드는 같다! 프리미티브를 구현한다면 앞의 예제와 같은 작용을 한다. 설명을 덧붙이면 이 예제에서는 팩토리얼 계산에서 값을 되돌리는 함수 적용이 없다. 모두 다른 함수를 호출할 뿐이다. 의도한 스타일이 더 명확해 보인다!(프리미티브 구현은 Lambda: The Ultimate Declarative의 뒷부분에 적고 있다)


컨티뉴에이션 전달 방식의 예제로
B^2 - 4AC 를 계산하는 경우를 들어보자.

^^  **  -- 는 모두 CPS 스타일로 형태를 바꾼 프리미티브다. 이들은 앞의 fact 처럼 마지막 인자로 계산 결과를 전달한다. 그래서 X 와 Y는 값을 받았다. 그래서 --  연산을 했다. 그렇다면 그 다음에 할일이 무엇인가? 그것은 앞으로 할일이다. 이것을 continuation 이라고 부르며 CPS는 이런 스타일로 프로그램을 짜는 방식을 말한다.  만드는 일이 번거롭기는 해도 (대부분의 프로그래머가 별로 선호하지 않는 방식이다. ) 동작은 확실하다.

(^^  B 2 (LAMBDA (X)
               (** 4 A C  (LAMBDA (Y)
                  (-- X Y <the continuation>))))



샤프한 프로그래머라면 Y 컴비네이터와 CPS를  동시에 비교해서 생각할 수 있을 것 같다.  하나는 튜링식이고 하나는 알론조 처치의 방식이다. 둘은 같으면서 다르다.  개인적으로는 생각할 숙제로 남아있다.
Trackback 0 Comment 0
2009.03.13 20:37

The Y Combinator

Recursion의 본질에 해당하는 Y 컴비네이터는

하스켈 커리가 발견했다
영어판 위키백과에 나오는 Y combinator 에는  다음과 같은 내용이 있다. 

One well-known (and perhaps the simplest) fixed point combinator in the untyped lambda calculus is called the Y combinator. It was discovered by Haskell B. Curry, and is defined as

Y = λf·(λx·f (x x)) (λx·f (x x))

We can see that this function acts as a fixed point combinator by expanding it for an example function g:

Y g = (λf . (λx . f (x x)) (λx . f (x x))) g
Y g = (λx . g (x x)) (λx . g (x x)) (β-reduction of λf - applied main function to g)
Y g = (λy . g (y y)) (λx . g (x x)) (α-conversion - renamed bound variable)
Y g = g ((λx . g (x x)) (λx . g (x x))) (β-reduction of λy - applied left function to right function)
Y g = g (Y g) (definition of Y)


Y combinator는  Fixed Point 의 본질에 해당하는 부분으로 설명할 내용이 많다. 
픽스드포인트는 sicp 에도 나오지만 f(x)=x ; f  (f (x)) =f(x) =x ; 
이런 식으로 만들어 낼 수 있는 함수의 성질이다


리스프의 가장 본질적인 재귀처리는 label 함수로 처리한다, 그 본질은 결국 Y 컴비네이터와 같다. 
이 문제는 TAOI에도 나온다.  TAOI의 맨 마지막 페이지에 나온다.

좋은 예제를 찾고 있었으나 최근에 발견한 설명중 가장 좋은 예는 J.Franco라는 UC 교수님의 글이다. 
정말 잘 쓴 예라고 생각한다. 
이 글과 Why of Y 라는 Friedman의 글 그리고 root of lisp을 같이 놓고 생각하면 윤곽을 잡을 수 있을 것이다.  
자기자신에 스스로를 대입하는 함수는 신기한 것 같지만 별다른 것이 아니다.
그 설명이 아래에 있다. 몇일 동안 궁금하던 것을 글을 읽고 바로 이해했다. 정말 기뻤다.

예전의 root of lisp 의 소개글에서 eval (e, a) 는 식 (e) 와  환경(a)를  놓고 계산하는 것인데 (예전의 리스프에 대한 생각들 - 두번째 이야기에 해당한다. )

(eval. '((label firstatom (lambda (x) (cond ((atom x) x)    ('t (firstatom (car x)))))) y) '((y ((a b) (c d))))) ==> (eval. '((lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))) y) '((firstatom (label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))))) (y ((a b) (c d)))))


여기서 중요한 것은 firstatom 이라는 람다식이 그대로 환경에 등록되어 결국은 firstatom 내에서 일종의 텍스트치환이 일어나는 것처럼 동작한다.  초기의 리스프부터  recursion은 이런 식으로 해결되었다. 나중에는 set!을 써서 환경을 직접 고쳤다. 결국 변수문제는 환경문제다.  리스프와 스킴의 변수 문제는 깊은 통찰을 제공한다. 

 

스킴에서는 letrec 이라는 것으로 해결할 수 있는데  letrec이 별다른 것이 아니다. Richard P. Gabriel 의 why of y 에 보면

(define fact
 (lambda (n)
  (if (< n 2) 1 (* n (fact (- n 1))))))

은  다음과 같이 만들 수도 있는데
(letrec
 ((f (lambda (n)
   (if (< n 2) 1 (* n (f (- n 1)))))))
(f 10))

결국 let 과  set! 으로 구현하는 경우가 많다.

(letrec ((f (lambda ...))) ...)

은  다음과 등가이다.

(let ((f <undefined>)) (set! f (lambda ...)) ...)

define은 인터프리터의 구현에서 set! 를 사용하고 letrec도 마찬가지다.
그러나 label 과 letrec을 사용하지 않고 recursion을 구현할 수도 있는데 그것은 Y 컴비네이터를 사용하는 방법이다.  Y는 recursion과 fixed point 의 본질이다. 

따지고 보면 앞의 label은 같은 일을 하는 것으로 볼 수 있다. 
머리가 나쁜  이유로 몇번을 보고서야 이해 비슷한 것을 얻을 수 있었다.


 

 

The Y Combinator

In this file we derive the Y combinator, one of the fundamental results of recursive procedure theory. You already know that in some cases it is not necessary to give a procedure a name. For example,

  ((lambda (x) (+ x 1)) 6)

adds 1 to 6 without naming the procedure that does it. But, what about a recursive procedure? For example,

  (define fact
    (lambda (n)
      (if (zero? n)
          1
          (* n (fact (- n 1))))))

which computes the factorial of a number n, seems to need the name "fact" so that in the last line of the procedure it can recurse on itself. But, we will see this is not necessary and, in the process, will develop a lot of intuition about using Scheme. We proceed step by step, changing "fact" slightly on each step.

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

영어판 위키백과에 나오는 Y combinator 에는  다음과 같은 내용이 있다. 

Consider the factorial function (under Church encoding). The usual recursive mathematical equation is

fact(n) = if n=0 then 1 else n * fact(n-1)

We can express a "single step" of this recursion in lambda calculus as

F = λf. λx. (ISZERO x) 1 (MULT x (f (PRED x))),

where "f" is a place-holder argument for the factorial function to be passed to itself. The function F performs a single step in the evaluation of the recursive formula. Applying the fix operator gives

fix(F)(n) = F(fix(F))(n)
fix(F)(n) = λx. (ISZERO x) 1 (MULT x (fix(F) (PRED x)))(n)
fix(F)(n) = (ISZERO n) 1 (MULT n (fix(F) (PRED n)))

We can abbreviate fix(F) as fact, and we have

fact(n) = (ISZERO n) 1 (MULT n (fact(PRED n)))

So we see that a fixed-point operator really does turn our non-recursive "factorial step" function into a recursive function satisfying the intended equation.

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

Step 1. The first idea is simply to pass "fact" in as an argument in much the same way that we did for

  (define op-maker
    (lambda (op)
      (lambda (x y)
        (op x y))))

The first lambda passes the name of the operation and the second lambda is the nameless operation. Let's try this with "fact". The first attempt is

  (define fact-maker
    (lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n (procedure (- n 1)))))))

The idea will be to pass "fact-maker" in through "procedure". Thus, what we would like to do is invoke (fact-maker fact-maker) to produce our nameless (well, almost nameless) factorial procedure. This would allow us to write, for example

  >((fact-maker fact-maker) 5)
  120

But, this doesn't work because "fact-maker" is a procedure which takes as input one argument that is a procedure but "procedure", which is supposed to be identical to "fact", requires a numeric argument. The solution is the following:

  (define fact-maker
    (lambda (procedure)
      (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1)))))))

Try this, for example, with

 >((fact-maker fact-maker) 5)

Well, we got the name out of the body of the procedure but we still have to pass the procedure in and so far we have been using a name to do that. So let's try to get the whole dependence on a name out.

Step 2. Recall we demand that "fact" be identical to (procedure procedure) which in turn must be identical to (fact-maker fact-maker) (recall the example ((fact-maker fact-maker) 5) which gives the same result as (fact 5)). Thus, we can write "fact-maker" in the following way, making use of the result of step 1.

  (define fact
    ((lambda (procedure)
       (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1))))))
     (lambda (procedure)
       (lambda (n)
         (if (zero? n)
             1
             (* n ((procedure procedure) (- n 1))))))))

Try this with >(fact 5)

Consider the following:

  (((lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((procedure procedure) (- n 1))))))
    (lambda (procedure)
      (lambda (n)
        (if (zero? n)
            1
            (* n ((procedure procedure) (- n 1)))))))
   5)

This produces the factorial of 5 because the procedure which is invoked (the huge mess) is exactly the definition of "fact." But, lo and behold, there is no name for this procedure anywhere!

In what follows, we try to generalize this to all procedures and wind up with the dreaded applicative-order Y-combinator.

Step 3. First, we need to separate out the part that pertains to computing the factorial. The goal is to write this part in one place and when code for other problems is substituted for the factorial code, the result will be a new recursive procedure. This step is a little tricky because we insist on using, with no significant changes, code that was designed assuming a procedure name. The section of factorial code we currently have, from step 2, is

  (define F
    (lambda (n)
      (if (zero? n)
          1
          (* n ((procedure procedure) (- n 1))))))

This is different from what we want because it contains a (procedure procedure) where we would like to see a plain old procedure. So, we use a trick to get it out. In general, isn't

  (f arg)

identical to

  ((lambda (x) (f x)) arg) ?

The second statement is a little strange, though, because it makes you pass "arg" into a procedure so that the procedure which would be applied to it anyway is applied. Why do we want to do such a thing? Watch! This means that

  ((procedure procedure) (- n 1))

is the same as

  ((lambda (arg) ((procedure procedure) arg)) (- n 1))

and we substitute this into our current version of F to get

  (define F
    (lambda (n)
      (if (zero? n)
          1
          (* n ((lambda (arg) ((procedure procedure) arg)) (- n 1))))))

How has this helped? Well, the (lambda (arg)...) is ONE procedure and procedures can be passed as arguments so F can be defined as

  (define F
    ((lambda (func-arg)
       (lambda (n)
         (if (zero? n)
             1
             (* n (func-arg (- n 1))))))
     (lambda (arg) ((procedure procedure) arg))))

Yes, it's the same F but the old definition looked like this:

  (define F (lambda (n) ... < procedure >))

and the new definition looks like this:

  (define F ((lambda (func-arg) (lambda (n) ...)) < procedure >))

where < procedure > is the (lambda (arg) ((procedure... ) ...) ...) expression

Step 4. - Now we are ready to take the result of step 3 and apply it to the result of step 2. Writing out the whole thing, we get:

  (define fact
    ((lambda (procedure)
       ((lambda (func-arg)
          (lambda (n)
            (if (zero? n)
                1
                (* n (func-arg (- n 1))))))
        (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       ((lambda (func-arg)
          (lambda (n)
            (if (zero? n)
                1
                (* n (func-arg (- n 1))))))
        (lambda (arg) ((procedure procedure) arg))))))

You will probably want to study this carefully. Notice the double left parens in front of ((lambda (func-arg)... This is because we are writing

   ...
   ((lambda (func-arg) < body-using-func-arg >) (lambda (arg) ...))

which has the same form as

  ((lambda (arg) ((procedure procedure) arg)) (- n 1))

but is different in that a procedure is passed as an "arg" instead of an integer.

The two expressions beginning with (lambda (func-arg) ...) are exactly the pieces of code that correspond to the factorial code and they are in exactly the right form. So we can get them out of the definition of fact in the following way:

  (define F*
    (lambda (func-arg)
      (lambda (n)
        (if (zero? n)
            1
            (* n (func-arg (- n 1)))))))

  (define fact
    ((lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))
     (lambda (procedure)
       (F* (lambda (arg) ((procedure procedure) arg))))))

This is significant because we can now use any procedure in place of F* to change functionality to whatever we want. The only problem is that, as written, we still need to name F*. This is easily remedied in the next step.

-----------------------------------------------------------------------------
영어판 위키백과에 나오는 Y combinator 의 예제는 이번의 예제가  application - order라는 것을 설명하고 있다.

A version of the Y combinator that can be used in call-by-value (applicative-order) evaluation is given by η-expansion of part of the ordinary Y combinator:

Z = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))

..

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


Step 5. Jackpot! Now we write the dreaded applicative-order Y-combinator:

  (define Y
    (lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg)))))))

Notice that the procedure which does our computation is X (we stopped using F* to emphasize this code can be applied to any procedure) and that is passed in as an argument.

Step 6. We can write "fact" in terms of the Y-combinator as follows:

  (define fact (Y F*))

Try >(fact 5) to check the result. For that matter, try >((Y F*) 5). But Y is general and F* is specific to factorial but with no name! If we wrote the whole thing out it would be

  (((lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))))
    (lambda (func-arg)
      (lambda (n)
        (if (zero? n)
            1
            (* n (func-arg (- n 1)))))))
   5)

Look Ma! No name! Just to show the generality of all this let's use the Y combinator to define another procedure. Say findmax - finding the largest integer in a list.

  (define findmax
    (lambda (l)
      (if (null? l)
          'no-list
          (if (null? (cdr l))
              (car l)
              (max (car l) (findmax (cdr l)))))))

First, create the analog of F* for fact, call it M for max.

  (define M
    (lambda (func-arg)
      (lambda (l)
        (if (null? l)
            'no-list
            (if (null? (cdr l))
                (car l)
                (max (car l) (func-arg (cdr l))))))))

Now try ((Y M) '(4 5 6 3 4 8 6 2)) to see if it works. If you want to build it out it looks like this:

  (((lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))))
    (lambda (func-arg)
      (lambda (l)
        (if (null? l)
            'no-list
            (if (null? (cdr l))
                (car l)
                (max (car l) (func-arg (cdr l))))))))
   '(4 5 6 3 4 8 6 2))

As an assignment for the interested student, write findamx without using the procedure name "max". Just how many of the remaining names in findmax do you think can be disposed of? Talk about a nameless society...


조금 더 유명했던 글로  리처드 가브리엘(Richard P. Gabriel)의 Why of Y 가 있다. 이글 역시 대단한 개념글로  유명한 연구자가 쓴 글이다.  비슷하게 유명한 Daniel Friedman 이 쓴 (Y Y) works! 라는 글도 있으나  Little Lisper 라는 책이  정이 붙지 않는 것과 비슷하게 적응하기 힘들었다.

글의 형태를 간단하게 카피앤페이스트 하기 위해 ddj에 있는 것을 옮겼으나 웹에서는 pdf 문서를 구할 수 있다.
주석만 달겠다. 많은 부분이 겹치기 때문이다. 

The Why of Y

One way to derive Y.

By Richard P. Gabriel,  Dr. Dobb's Journal
4Ô 22, 2007
URL:http://www.ddj.com/architect/199200394

Richard P. Gabriel is a Distinguished Engineer at IBM Research, looking into the architecture, design, and implementation of extraordinarily large, self-sustaining systems. He can be contacted at www.dreamsongs.com.


Did you ever wonder how Y works and how anyone could ever have thought of it? In this article, I explain not only how it works, but how someone could have invented it in the first place. I'll use Scheme notation because when functions passed as arguments are applied, Y is easier to understand.

Y's goal is to provide a mechanism to write self-referential progra ms without any special built-in means. Scheme has several mechanisms for writing such programs, including global function definitions and letrec. One way you can write the factorial function in Scheme is:

(define fact (lambda (n) (if (< n 2) 1 (* n (fact (- n 1))))))

This function works because a global variable, fact, has its value set to the value of the lambda expression. When the variable fact in the body of the function is evaluated to determine which function to invoke, the value is found in the global variable. Using a global variable as a function name can be rather unpleasant because it relies on a global, and thus vulnerable, resource -- that is, the global variable space. The Scheme self-reference form letrec usually is implemented using a side effect; it is easier to reason about programming languages and programs that have no side effects. Therefore, it is of theoretical interest to establish the ability to write recursive functions without using side effects. A program that uses letrec is:

(letrec ((f (lambda (n) (if (< n 2) 1 (* n (f (- n1))))))) (f 10))

This program computes 10!. The reference inside the lambda express ion is to the binding of f, as established by the letrec. You can implement letrec using let and set!:

(letrec ((f (lambda ...))) ...)

which is equivalent to:

(let ((f )) (set! f (lambda ...)) ...)

All references to f in the lambda expression are to the value of the lambda expression. Y takes a function describing another recursive or self-referential function and returns another function that implements the recursive function. Y is used to compute 10! with:

(let ((f (y (lambda (n) (lambda (n) (if (< n 2) 1 (* n (h (- n 1))))) )))))) (f 10))

The function passed as an argument to Y takes a function as an argument and returns a function that looks like the factorial function we want to define. That is, the function passed to Y is (lambda (h) ...). The body of this function looks like the factorial function, except that where we would expect a recursive call to the factorial function, h is called instead. Y arranges for an appropriate value to be supplied as the value of h.

People call Y the "applicative-order fixed-point operator for functionals." Let's take a closer look at what this means in the factorial example.

Suppose M is the true mathematical factorial function, possibly in Plato's heaven. Let F denote the function:

F = (lambda (h) (lambda (n) (if (< n 2) 1 (* n (h (- n 1))))))

Then:

((F M) n) = (M n).

That is, M is a fixed point of F: F maps (in some sense) M onto M. Y satisfies the property:

((F (Y F)) X) = ((Y F) X)

This property of Y is very important. Another important property is that the least defined fixed point for functionals is unique; therefore, (Y F) and M are in some sense the same. Applicative-order Y is not the same as classical Y, which is a combinator. Some texts refer to Y as Z. To derive Y, I will start with a recursive function example, factorial. In the derivation I will use three techniques:

  • The first one passes an additional argument to avoid using any self-reference primitives from Scheme.
  • The second technique converts multiple-parameter functions to nested single-parameter functions to separate manipulations of the self-reference and ordinary parameters.
  • The third technique introduces functions through abstraction.

All code examples will use the variables n and m to refer to integers, the variable x to refer to an unknown but undistinguished argument, and the variables f, g, h, q, and r to refer to functions. The basic form of the factorial function is:

(lambda (n) (if (< n 2) 1 (* n (h (- n1)))))

The h variable should refer to the function we wish to invoke when a recursive call is made, which is the factorial function itself. Since we have no way to make h refer directly to the correct function, let's pass it in as an argument:

(lambda (h n) (if (< n 2) 1 (* n (h h (- n 1)))))

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

앞의 첫번째 예제가 h,n 을  개별적인 lambda 를 사용한 것과 달리 h 는 함수로 n은
팩토리얼의 인자로 사용했다.

그 결과 (h h (- n 1)) 은  (lambda (h n) 에서 인자로 받은 h 에 h와 n-1 을 다시 적용하는
(* n (h h (- n 1))) 형태가 된다. (h h (- n 1))  은 새로운 recursion 을 일으킨다.

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

In the recursive call to h, the first argument will also be h because we want to pass on the correct function to use in the recursive situation for later invocations of the function. Therefore, to compute 10! we would write:

(let ((g (lambda (h n) (if (< n 2) 1 (* n (h h (- n 1))))))) (g g 10) )


-------------------------------------------------------------------------------------
앞의 식을 g 로 만들고  (g g 10) 을 대입한다.
실제로 이 코드를 돌려보면 3628800 이  나온다.
-------------------------------------------------------------------------------------

During the evaluation of the body of g, h's value is the same as the value of g established by let; that is, during execution of g, h refers to the executing function. When the function call (h h (- n 1)) happens, the same value is passed along as an argument to h; h passes itself to itself. We want to split the management of the function's self-reference fr om the management of other arguments. In this particular case, we want to separate the management of h from that of n. A technique called "currying" is the standard way to handle this separation. Before we curry this example, let's look at another example of currying. Here is a program that also computes 10!, but in a slightly more clever way:

(letrec ((f (lambda (n m) (if (< n 2) m (f (- n 1) (* m n)))))) (f 10 1))

The trick is to use an accumulator, m, to compute the result. Let's curry the definition of f:

(letrec ((f (lambda (n) (lambda (m) (if (< n 2) m ((f (- n 1)) (* m n ))))))) ((f 10) 1))

-------------------------------------------------------
아래의 몇줄의 문항은 closure 와 currying 을 적용하겠다는 것이다.
currying은  영어판 위키 백과에도 나온다.
-----------------------------------------------------

The idea of currying is that every function has one argument. Passing multiple arguments is accomplished with nested function application: the first application returns a function that takes the second argument and completes the computation of the value. In the previous piece of code, the recursive call:

((f (- n 1)) (* m n))

has two steps: the proper function to apply is computed and applied to the right argument. We can use this idea to curry the other factorial program:

(let ((g (lambda (h) (lambda (n) (if (< n 2) 1 (* n ((h h) (- n 1)))) ))) ((g g) 10))


----------------------------------------------------------------------------------
let 이 lambda 의 syntactic sugar 라는 말은 sicp 에 여러 번 나온다,
결국 (labmda (g)  ( (g g) 10 ) (lambda (h) (....))
----------------------------------------------------------------------------------

In this piece of code, the recursive call also computes and applies the proper function. But that proper function is computed by applying a function to itself. Applying a function to itself is the process by which we get the basic functionality of a self-reference. The self-application (g g) in the last line of the program calls g with g itself as an argument. This returns a closure in which the variable h is bound to the outside g. This closure takes a number and does the basic factorial comput ation. If the computation needs to perform a recursive call, it invokes the closed-over h with the closed-over has an argument, but all the hs are bound to the function g as defined by the let. To summarize this technique, suppose we have a self-referential function using letrec as in the following code skeleton:

(letrec ((f (lambda (x) ... f ...))) ... f ...)

This skeleton can be turned into a self-referential function that uses let where r is a fresh identifier:

(let ((f (lambda (r) (lambda (x) ... (r r) ...)))) ... (f f) 


----------------------------------------------------------------------------------------
위의 letrec과 let 의 차이를 설명하는 결정적인 커멘트는 매우 중요한 것인데 썰렁하게 설명하고 있다,
앞의 label 함수 부분을 다시 한번 살펴 보라!
----------------------------------------------------------------------------------------


For the next step, let's examine how to separate further the management of h in our factorial function from the management of n. Recall that the factorial program looks like:


(let ((g (lambda (h)
    (lambda (n)
     (if (< n 2) 1 (* n ((h h) (- n 1))))))))
  ((g g) 10))

 

Our plan of attack is to abstract the if expression over (h h) and n, which will accomplish two things: the resulting function will become independent of its surrounding bindings and the management of the control argument will become separated from the numeric argument. The result of the abstraction is:

(let ((g (lambda (h) 
   (lambda (n) 
      (let ((f (lambda (q n) 
         (if (< n 2) 1 (* n (q (- n 1))))))) (f (h h) n)))))) 
((g g) 10))

We can curry the definition of f, which also changes its call:

(let ((g (lambda (h) 
       (lambda (n) 
          (let ((f (lambda (q) 
            (lambda (n) 
               (if (< n 2) 1 (* n (q (- n 1)))))))) ((f (h h)) n)))))) 
((g g) 10))

Notice that the definition of the function f need not be deeply embedded in the function g. Therefore, we can extract the main part of the function -- the part that computes factorial -- from the rest of the code.

(let ((f (lambda (q) (lambda (n) (if (< n 2) 1 (* n (q (- n 1)))))))) 
  (let ((g (lambda (h) (lambda (n) ((f (h h)) n))))) 
     ((g g) 10)))

The form of f is once again the parameterized form of factorial, and we can abstract this expression over f, which produces Y as follows:

(define Y (lambda (f) 
           (let ((g (lambda (h) 
                     (lambda (x) ((f (h h)) x)) ))) 
                      (g g))))

This is one way to derive Y.


------------------------------------------------------
결론은 둘다  같다.
그리고 전체 다시 한두번 더 읽어 보기를 권한다.
머리 속에도 다시 한 번 이 내용을 apply 해서 계산을 일으킬 필요가 있다. 

두 글의 결론은?
람다 함수는 치환으로 모든 것을 해결한다는 것이다.

이렇게 끝난다. 
조만간 한글로된 정리판을 만들 예정이지만 
그때까지는 이 정도로 참는 수 밖에 없겠다.


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

추가:)

람다를  쓰다보니 형식은 자유롭다. 그중에는

http://www.rosettacode.org/wiki/Y_combinator#Scheme

> (define (Y f) ((lambda (x) (x x)) (lambda (y) (f (lambda args (apply (y y) args))))))
> (define (fac f) (lambda (n) (if (= n 0) 1 (* n (f (- n 1))))))
> ((Y fac) 5)
120
> (define (fib f)

(lambda (n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (f (- n 1)) (f (- n 2)))))))





>
((Y fib) 8)
21




(lambda  args (apply ..) ...) 의 형태는 괄호가 없는데 r5rs 9 페이지에 나오는 설명이 있다.
args 는 임의의 숫자로 정할 수 있다.

The procedure takes any number of arguments;
when the procedure is called, the sequence
of actual arguments is converted into a newly allocated
list, and the list is stored in the binding of the
variable.

Trackback 2 Comment 0
2009.03.12 03:36

느긋한 계산법

한글 위키백과에 나오는 lazy evaluation은 언뜻 실감이 나지 않는다. 그런데 이 문제는 영어판에서도 같다. 또 하나의 문제는 많은 예제들이 하스켈로 되어 있는데 하스켈은 이미 언어 자체가 너무 강력해서 중간의 구현 과정을 모르고 넘어가버린다. 이론의 학습이라면 모르지만 실제로 코딩 비슷한 것을 보려면 만들어 보아야 한다. sicp 의 스트림이나 게으른 계산의 예제는 이런 주제들을 다룬다. 그리고 예전에 람다페이퍼를 소개한 글 (ibm dw 에 적은 글에 적었다.)에 예제를 올려놓았다.
하지만 당분간 위키를 무시할 수는 없고 여러가지 새롭고 생소한 한글 용어들을 접하는 수밖에는 없다. 그래서 가끔 읽어보기 위해 블로그에 올려 놓고 읽거나 주석을 붙이기로 했다.
현재의 상태는 주석을 붙이지 않은 상태다.
용어의 혼란은 여러가지지만 개인적으로 게으른 계산법이라는 용어를 이미 사용하고 있기 때문이다. 어느 것이 더 좋은지는 나중에 사용자들이 정할 문제다.

느긋한 계산법

위키백과 ― 우리 모두의 백과사전.

컴퓨터 프로그래밍에서 느긋한 계산법(Lazy evaluation)은 계산의 결과값이 필요할 때까지 계산을 늦추는 기법이다. 두 가지 관련된 항목들이 있는데 지연 계산법최소 계산법이다.

느긋하게 계산하면 필요없는 계산을 하지 않으므로 실행을 더 빠르게 할 수 있고, 복합 수식을 계산할 때 오류 상태를 피할 수 있고, 무한 자료 구조를 쓸 수 있고, 미리 정의된 것을 이용하지 않고 보통 함수로 제어 구조를 정의할 수 있다.

느긋한 계산법을 사용하는 언어들은 "이름으로 호출"하거나 "필요할 때 호출"하는 계산 전략을 사용하는 것으로 나눌 수 있다. 하스켈과 같은 대부분의 실제 느긋한 언어들은 성능상의 이유로 "필요할 때 호출" 전략을 사용한다. 그러나 느긋한 계산법을 이론적으로 표현한 것들은 간편하게 "이름으로 호출"하기도 한다.

느긋한 계산법의 반대되는 계산법은 조급한 계산법이 있는데 엄격한 계산법이라고도 한다. 조급한 계산법은 대부분의 프로그래밍 언어가 동작하는 방식이다.

목차

[편집] 복합 수식

(a and b)와 같은 논리식을 계산한다고 하면 a항이 거짓인 경우에, b항을 계산하지 않아도 전체 식의 답을 알 수 있다. (a or b)에서 a항이 인 경우에도 마찬가지이다. 여기서 항이 복잡한 식이면 이점이 많고, 식에서 결과가 이나 거짓일 가능성과 계산의 비용에 따라 어떤 항이 먼저 계산되어야 좋은지 알 수 있다. 따라서 (a or b or c)와 같은 식에서 a항이 값을 가질 가능성이 많다면, 전체 식을 쉽게 계산할 수 있다. 이런 가능성을 보장하기 위해, 컴파일러는 더 계산해야 할 것인지, 다른 항을 지름길 계산 해야 할 것인지를 검사하기도 한다. 이런 검사는 계산을 줄이는 것을 실패할 경우나 꼭 필요한 경우 무조건 전체 식을 계산해야 할 때 시간이 더 많이 걸리게 된다.

산술식을 계산할 때에도 유사한 접근 방식을 취할 수 있다. 어떤 수에 0을 더하는 것은 의미 없고, 0이나 1을 곱하는 경우에는 특별한 효과가 있다. 그러나 이런 특별한 값들을 검사하는 것은 논리값은 2개의 값을 가지는데 비하여 수는 여러가지 값을 가질 수 있기 때문에 큰 이득이 되지 못한다. 그러나 0이 소수점 값으로 변환하는데 쓰이지 않는 이상 하드웨어가 특수한 경우는 잘 계산하고 있다.

[편집] 오류 회피

특정한 상황에서는 계산되면 오류 상황이 되어 오류를 발생시키는 수식이 있다고 가정하자. 그 수식은 (계산해도 안전한 식 and 수식)과 같은 형태로 보호되어 있을 수도 있다. 예를 들면 (N <> 0 and (x mod N = 0)과 같은 형태이다. 분명히, 이것은 if N <> 0 then if x mod N = 0 then ...과 같은 형태로 쓸 수 있지만 깔끔하지 못하다. 반대로, (a or b)로 검사할 때, a인 경우에 b는 계산될 필요가 없을 뿐더러 문제를 일으키는 경우가 있을 수 있다. ab 둘 중에 하나가 참인 경우에 어떤 행동을 하고 싶다고 하면(이 식에서 의미하는 것이다!) 친절하게 if a then action else if b then action이라고 쓸 수 있지만, action을 반복해서 쓰기 때문에 실수를 할 가능성이 있다.

좀 더 현명하게, 뒤에 공백이 있는 텍스트 문자열이 있고 공백이 아닌 맨 마지막 문자의 위치를 알고 싶다고 하자.

 l:=Length(t);
 while l > 0 and t(l) = " " do decrement l;

라고 하거나. 좀 더 유연한 언어에서는,

 for l:=Length(t):1:-1 while t(l) = " " do;

라고 할 수 있다. 분명히, 문자열의 전체가 빈칸으로 차 있다고 하면 l은 0이 될 것이다. 그러나 문자열에서 0번째 문자열을 읽는 시도는 하지 않는다. 이것은 잘해야 쓸데 없는 노력이고, 못하면 오류를 일으킬 수도 있다.

[편집] 지연 계산법

지연 계산법은 함수형 프로그래밍 언어에서 주로 사용한다. 지연 계산법을 사용하면 수식이 변수에 접근하는 순간 계산되는 것이 아니라, 강제로 계산값을 출력하라고 할 때까지 계산을 늦춘다. 말하자면, x:=수식;과 같은 구문이 있다고 하면, 분명히 수식을 계산하여 결과값을 x에 넣어야 한다. 하지만 x에 들어있는 값은 나중에 참조되어 그 값을 요구한다던지 할 때까지는 상관이 없다. 비록 다른 심볼보다 바깥 세상을 보고자 하는 몇 가지 심볼을 생성하기 위해 빠르게 자라는 의존성 나무의 가지를 칠 수 있다고 할지라도, 식의 계산을 뒤로 미룰 수 있다.

수식의 계산을 기본으로 늦추는 프로그래밍 언어도 있고 함수나 특별한 구문으로 계산을 늦추는 언어도 있다. 미란다와 하스켈은 기본으로 계산을 늦춘다. 다른 언어들은 특수한 구문을 써서 계산을 늦추라고 명시하거나 썽크에 수식을 감싸서 계산을 늦춘다. 예를 들어 스킴에서는 "delay"와 "force"를 써서 이런 것을 명시할 수 있다.

지연 계산법은 계산할 때 무한 반복 문제나 크기 문제 없이 계산 가능한 끝없는 목록을 만들 수 있다. 예를 들어, 피보나치 수로 (보통 스트림이라고 부르는) 끝없는 목록을 만드는 함수를 작성할 수 있다. n번째 피보나치 수는 끝없는 목록의 원소를 추출하는 것만으로도 간단하게 계산할 수 있는데, 목록의 처음 n개의 수들만 계산하도록 하면서 할 수 있다.

예를 들어 하스켈에서는 모든 피보나치 수의 목록을 다음과 같이 쓸 수 있다.

  fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

하스켈의 구문 ":"는 목록에 원소를 첨가하는 것이고 tail은 첫 번째 원소를 빼고 리스트를 돌려주며, zipWith는 특정한 (여기서는 (+)) 함수를 사용하여 두 목록의 각 원소를 결합하여 세번째 항목을 생성하도록 한다.

프로그래머가 주의한다면, 특정한 결과값을 생성할 때 필요한 값만 계산할 것이다. 그러나 특정 계산이 목록의 길이를 구하는 것이라던지, 목록의 원소들의 전체합을 구하는 것과 같이 프로그램에서 무한히 많은 원소를 계산하는 것이라면 계산을 끝내지 못하거나 메모리를 다 쓰게 될 것이다.


Trackback 6 Comment 0