弱LisperがMITでSICP(シクピー)を受講した結果

  • 163
    いいね
  • 5
    コメント
この記事は最終更新日から1年以上が経過しています。

SICPとは何か

sicp_cover_small.png

Structure and Interpretation of Computer Programsという古めかしい表紙の本をご存知でしょうか? これはもともと、マサチューセッツ工科大学(Massachusetts Institute of Technologies; MIT)の電気工学および計算機科学(Electrical Engineering & Computer Science; EECS)系の学部の授業の一本目として提供されていた同名の授業から発生した教科書です。教科書は無料公開されています。

コースには6.001という番号がつけられていました(米国の学校の授業は番号が付いていて数字が高い方がだいたい難しい)。MITの授業はEECSが6番台で、6.001-6.004がcomputer programs, circuits and electronics, signals and systems, computation structuresだったそうです(参考)。1986年(?)の授業の様子は動画が公開されています(MIT OCW SICP 1986) 。Lisperならば黒板で括弧の対応をあわせる(ときどき間違える)講師の姿に心が震えることうけあいです。難解なことで知られる名物授業だったようなのですが、他の専攻だけど一個だけcomputer scienceの授業を受けてみようと目を輝かせてきた学生の心が折れるとか、授業の再編成だかの理由で2007年で終りになってしまったようです(参考)

その後は、computer scienceの授業の一本目はIntroduction to Computer Science and Programming という授業になっているようです。edXでも同じ講師が 授業 をやっています。使用言語はPythonになっているようです。シラバスを見るとこれはこれで結構難しそうな感じもします。

私はボストン南部の他の大学院で(高齢)学生をしているので、MITでSICPの授業に潜りたいな~と思っていたのですが、調べたら上記のような経緯を知って、大変がっかりしておりました。と、、思いきや、6.037 SICPとして、冬期間(米国の大学/大学院では9-12月がFall semester、2-5月がSpring semesterとなっていることが多い?)の特別授業(4週8コマ; もともとの授業は26コマ)として、無理矢理復活している(コースのメールアドレスが6.001-zombies!)のを発見。最初これで単位申請(提携している大学同士だとできる)しようかと試みましたが、学部の授業じゃだめといわれたので、講師に頼みこんでモグリ学生として受講させてもらうことにしました。2007年の授業の終了を嘆いた6.001の過去のteaching assistantたちが2009年ぐらいから復活させたということのようです。

下記はそのサマリーです。私自身は計算機科学の人間でもソフトウェア工学の人間でもなく、主に書くのはRとEmacs Lispぐらいですので、内容的に不十分、不正確な部分もあるかと思います。

Lecture 1: Syntax of Scheme, procedural abstraction, and recursion

Schemeの基本的な文法に関してと、再帰(recursion)とiterationの違いみたいな話し。まわりの学生が若い(学部の一年生とかがほとんどっぽいので年齢は私の半分ぐらいなはず)。得意な言語は?とクラスに聞いていて、Python, Matlab, Cとかみんな答えているなかで、ひとりだけ"R"といったら、えっ?と聞きかえされました(私の発音が悪いだけ?)。

環境はDrRacketを勧めていました。なので、SchemeというかRacketですね。DrRacketが一番環境設定が楽だからのようでした。まあ、開発環境設定でこけるとやる気がそがれますからね。

この回の授業内容は初歩的でした。再帰的な計算と繰り返し的(iterativeの訳のつもり)な計算を対比するのにGuile Scheme が便利であるのを発見しました。REPLで ,trace (fact-recur 5)とかやると計算経過を表示してくれます(最初の,は特別REPLコマンドの識別用で必要)。

深度が深くなっている(SICP本曰く三角形を感じよ!)とstackを消費していることを示します。accumulatorを使って、iterativeに計算すると深度が深くならずstackが一個ですんでいるのがわかります(SICP本曰くiterationは四角い!)。traceはRacketでも一応あるのですが、経過表示がいまいちで、わかりやすくありませんでした。

;;; Factorial (linear recursion)
(define (fact-recur n)
  (if (zero? n)
      1
      (* n (fact-recur (- n 1)))))

;; scheme@(guile-user)> ,trace (fact-recur 5)
;; trace: |  (#<procedure 105a4d480> #(#<directory (guile-user) 104467c60> #f))
;; trace: |  #(#<directory (guile-user) 104467c60> fact-recur)
;; trace: (#<procedure 105a56a60 at <current input>:818:7 ()>)
;; trace: (fact-recur 5)
;; trace: |  (fact-recur 4)
;; trace: |  |  (fact-recur 3)
;; trace: |  |  |  (fact-recur 2)
;; trace: |  |  |  |  (fact-recur 1)
;; trace: |  |  |  |  |  (fact-recur 0)
;; trace: |  |  |  |  |  1
;; trace: |  |  |  |  1
;; trace: |  |  |  2
;; trace: |  |  6
;; trace: |  24
;; trace: 120

;;; Factorial (iteration)
(define (fact-iter-helper n acc)
    (if (zero? n)
        acc
        (fact-iter-helper (- n 1) (* acc n))))
(define (fact-iter n)
  (fact-iter-helper n 1))

;; scheme@(guile-user)> ,trace (fact-iter 5)
;; trace: |  (#<procedure 1056fc340> #(#<directory (guile-user) 104467c60> #f))
;; trace: |  #(#<directory (guile-user) 104467c60> fact-iter)
;; trace: (#<procedure 105702860 at <current input>:1042:7 ()>)
;; trace: (fact-iter 5)
;; trace: (fact-iter-helper 5 1)
;; trace: (fact-iter-helper 4 5)
;; trace: (fact-iter-helper 3 20)
;; trace: (fact-iter-helper 2 60)
;; trace: (fact-iter-helper 1 120)
;; trace: (fact-iter-helper 0 120)
;; trace: 120

Lecture 2: Data abstractions, higher order procedures, symbols, and quotation

これも、まだ基本的な内容。関数の入出力の型、高階関数による似た処理の抽象化、cons cellによるデータ収納とcar/cdr/consの関連など。symbolとquote、eq?によるsymbolの比較など。

途中のrecitation(レクチャー形式の講義の内容を再度小グループにわかれて問題をやりながら復習するみたいな感じ)では、map, filter, reverse, foldなどいわゆる関数型プログラミングで良く出てくる関数の書きかたみたいな内容。

reverseはconsがリストの頭にものを付け加えるので、iterationで書いた方がシンプル。通常の再帰で書くとリストの最後にものを付け加えるappendが必要になって効率が悪いみたい。

(define (reverse-rec lst)
  (cond
   [(null? lst) '()]
   [#t (append (reverse-rec (cdr lst)) (list (car lst)))]))

;; scheme@(guile-user)> ,trace (reverse-rec (iota 4))
;; trace: |  (#<procedure 103784a00> #(#<directory (guile-user) 102cd8c60> #f #f))
;; trace: |  #(#<directory (guile-user) 102cd8c60> reverse-rec iota)
;; trace: (#<procedure 1037c09e0 at <current input>:93:7 ()>)
;; trace: |  (iota 4)
;; trace: |  (0 1 2 3)
;; trace: (reverse-rec (0 1 2 3))
;; trace: |  (reverse-rec (1 2 3))
;; trace: |  |  (reverse-rec (2 3))
;; trace: |  |  |  (reverse-rec (3))
;; trace: |  |  |  |  (reverse-rec ())
;; trace: |  |  |  |  ()
;; trace: |  |  |  |  (append () (3))
;; trace: |  |  |  |  (3)
;; trace: |  |  |  (3)
;; trace: |  |  |  (append (3) (2))
;; trace: |  |  |  (3 2)
;; trace: |  |  (3 2)
;; trace: |  |  (append (3 2) (1))
;; trace: |  |  (3 2 1)
;; trace: |  (3 2 1)
;; trace: |  (append (3 2 1) (0))
;; trace: |  (3 2 1 0)
;; trace: (3 2 1 0)

(define (reverse-iter lst)
  (define (helper acc lst)
    (cond
     [(null? lst) acc]
     [#t (helper (cons (car lst) acc)
                 (cdr lst))]))
  (helper '() lst))

;; scheme@(guile-user)> ,trace (reverse-iter (iota 4))
;; trace: |  (#<procedure 103270a40> #(#<directory (guile-user) 102cd8c60> #f #f))
;; trace: |  #(#<directory (guile-user) 102cd8c60> reverse-iter iota)
;; trace: (#<procedure 103c549a0 at <current input>:277:7 ()>)
;; trace: |  (iota 4)
;; trace: |  (0 1 2 3)
;; trace: (reverse-iter (0 1 2 3))
;; trace: (3 2 1 0)

勉強になったのはfold関数。以前、Programming in Haskellの説明が秀逸とどこかに書いてあったので、読んでみたことがありますが、Haskellが良くわからないのとあいまってよくわかりませんでした。Schemeで実際書いてみると良くわかりました。

まずは、reduceとも呼ばれてより一般的っぽいfold left。初期値から始めて左からリストの要素を与えられた関数で処理して、accumulatorに貯めていきます。画像はWikipediaより。

foldl

処理の順番が頭(左)からなのでiterationとしてすぐ書けるので、計算効率が良いようです。下記の例では三角形にならずにスタックが一定ですんでいるところがわかります。

;;; fold left
(define (foldl f init lst)
  (define (helper lst acc)
    (if (null? lst)
        acc
        (helper (cdr lst) (f acc (car lst)))))
  ;;
  (helper lst init))

;; scheme@(guile-user)> ,trace (foldl + 0 (iota 5))
;; trace: |  (#<procedure 108c46820> #(#<directory (guile-user) 107ce6c60> #f #f #f))
;; trace: |  #(#<directory (guile-user) 107ce6c60> foldl + iota)
;; trace: (#<procedure 108c4b160 at <current input>:1503:7 ()>)
;; trace: |  (iota 5)
;; trace: |  (0 1 2 3 4)
;; trace: (foldl #<procedure + (#:optional _ _ . _)> 0 (0 1 2 3 4))
;; trace: |  (+ 0 0)
;; trace: |  0
;; trace: |  (+ 0 1)
;; trace: |  1
;; trace: |  (+ 1 2)
;; trace: |  3
;; trace: |  (+ 3 3)
;; trace: |  6
;; trace: |  (+ 6 4)
;; trace: |  10
;; trace: 10

fold rightはClojureにないのでよく知らなかったのですが、リストの初期値を右端に持ってきて、末尾側(右)からリストをたたんでいきます。画像はWikipediaより。

foldr

実際の実行としてはリストの頭側から再帰で処理をまたせておいて、最後尾に達したら初期値と最後尾の値で関数を実行します。あとは、右側から処理待ちの処理をすすめていけばOK。再帰の処理待ちが発生するので三角形にtraceが伸びていくのがわかります。

;;; fold right
(define (foldr f init lst)
  (if (null? lst)
      init
      (f (car lst)
         (foldr f init (cdr lst)))))

;; scheme@(guile-user)> ,trace (foldr + 0 (iota 5))
;; trace: |  (#<procedure 108c89c80> #(#<directory (guile-user) 107ce6c60> #f #f #f))
;; trace: |  #(#<directory (guile-user) 107ce6c60> foldr + iota)
;; trace: (#<procedure 108c8d900 at <current input>:1220:7 ()>)
;; trace: |  (iota 5)
;; trace: |  (0 1 2 3 4)
;; trace: (foldr #<procedure + (#:optional _ _ . _)> 0 (0 1 2 3 4))
;; trace: |  (foldr #<procedure + (#:optional _ _ . _)> 0 (1 2 3 4))
;; trace: |  |  (foldr #<procedure + (#:optional _ _ . _)> 0 (2 3 4))
;; trace: |  |  |  (foldr #<procedure + (#:optional _ _ . _)> 0 (3 4))
;; trace: |  |  |  |  (foldr #<procedure + (#:optional _ _ . _)> 0 (4))
;; trace: |  |  |  |  |  (foldr #<procedure + (#:optional _ _ . _)> 0 ())
;; trace: |  |  |  |  |  0
;; trace: |  |  |  |  (+ 4 0)
;; trace: |  |  |  |  4
;; trace: |  |  |  (+ 3 4)
;; trace: |  |  |  7
;; trace: |  |  (+ 2 7)
;; trace: |  |  9
;; trace: |  (+ 1 9)
;; trace: |  10
;; trace: (+ 0 10)
;; trace: 10

この例ではleftでもrightでも加算は順番が関係ないので、結果は同じです。結果が同じ場合はfold left (reduce)の方がわかりやすいし、計算効率も良いのでよさそうです。ただ、計算によってはright foldでないとできないものもあるようです。このcode IQの問題(ちら見で見られます)は、分数の分母の右側から計算がすすむので、まさにfold rightが表現に良いようです。私はfold rightを理解していない状態でやったら、reverseを使ってリストを反転して先頭から処理するようなプログラムになってしまいました(つまり、右から処理した方が楽)。ちなみに、Haskellでは遅延評価の関係でfoldrがより使いやすいらしいです(参考)。

Lecture 3: Mutation, and the environment model

3日目にして講師たちがSICPをシクピーと読んでいるのに気づいて衝撃をうけました。sick peeみたいで気持悪いですが、シクなのでsickには聞こえないか。

主にmutationについて。Schemeではset!(!はbangと呼んでいた)でsymbolに関連付けられている値を変更、set-car!とset-cdr!でcons cellにぶら下がっている値を変更できます。set!は再度defineしたみたいな感じなのでわかりやすいですが、set-car!とset-cdr!はcons cellをのこしたまま変更が起るので難解。これをうまいこと使うことで循環構造になっている無限リスト(というのか不明ですが)を作成して、処理Aと処理Bを交互に行うような例を出していました(下記)。

(define mystery
  (let ([step1 (lambda () 'flop)]
        [step2 (lambda () 'flip)])
    (let ([todo (list step1 step2)])
      (set-cdr! (cdr todo) todo)
      (lambda ()
        (set! todo (cdr todo))
        ((car todo))))))

(mystery) ; => flip
(mystery) ; => flop
(mystery) ; => flip
(mystery) ; => flop

ぱっと見ではなにがおこっているのかわかりにくいですが、まず、symbol flopを返す関数とsymbol flipを返す関数を定義してリストtodoとしてまとめます。ここまでで、[ step1(flop) | (pointer to 2nd) ]というcons cellと[ step2(flip) | (empty) ]というcons cellがつながったリストが出来ます。ここで(cdr todo)を行なうと二個目のcons cellが得られるので、そのcons cellのcdrつまりempty部分をtodo自体へのpointerとしてmutationします(set-cdr!)。それにより、下記のように二個目のcons cellのcdrが一個目のcons cellの先頭を指す循環構造になります。

[ step1(flop) | (pointer to 2nd) ]->[ step2(flip) | (pointer to 1st) ]

todoというsymbolはこの時点ではflop cons cellに結びついています。mystery関数は実行時にset!でsymbol todoが指すcons cellを一個後ろにずらします。なので一回目の実行結果はflipのcons cellのcar、つまり、step2関数が実行され、symbol flipが返ります。二回目の実行では再度symbol todoが再定義されて次のcons cell(最初に戻る)を指すようになります。そのcons cellのcar、つまり、step1関数が実行されて、symbol flopが返ります。

stackやqueueといったデータ構造をどうやってcons cellで表現するかというような話もありました(資料page 15-)。stackの方が簡単なようです。queueは一個のcons cellでリストの最初と最後へのpointerを両方格納すると良いようでした。

mutationを導入することで関数型プログラミングのsubstitution modelから、environmental modelが必要になるのだという話をしていましたが、いまいちsubstitution modelがなんのことだかがわかりませんでした(資料page 40-)。。

environmentとは名前(symbol)と値の対応表であるframeとenclosing environment(親environment)へのpointerからなる概念とのこと。cons cellといったデータ構造はenvironmentに格納されているのではなく、bindingはあくまで名前とcons cellへのpointerが格納されているだけとのことでした。確かにそうでないと、同じデータを複数のenvironmentで使おうとすると複製しないといけなくなってしまいそうです。

procedureの定義では"double bubble"と呼ぶ概念を使っていました(資料p53)。これはlambdaによって生成されて、code pointer(引数を定義するparametersと処理を定義するbodyからなる)とenvironment pointer(名前の対応表を指ししめす)からなるとのことでした。procedureの名前というのはframeで名前との対応として二次的に定義されるもので、procedure自体には名前という概念はないようです。procedureの実行時には、引数と値の対応表のframeを持つenvironmentが一時的に作成されることで、bodyの中の引数にあたる部分が解釈可能になるとのことでした。

Lecture 4: Interpretation and evaluation

4日目にしていきなりSchemeでScheme evaluator (interpreter)を書く話。いきなりレベル上りすぎ。同じ言語自体のevaluatorを書く場合をMeta-circular evaluatorというようです。CourseraのProgramming Languages(もしくは講師のweb site)で、Racketを使って同様な内容をやっていたので、なんとかついていけた感じ。このCourseraコースは非常におすすめです。言語をあえてSML, Racket, Rubyと三種類使うことで、特定の言語ではなく、言語パラダイムなどにフォーカスをあてています。ちなみに、同時期にやっていたedXの Introduction to Functional Programmingはあえなく途中で挫折しました。

関係ないけど授業にいる髪の毛の片側だけ緑色の男性二人組(カップル?)が、なぜかふたりとも裸足であることに気付いて、Emacs開発者のRichard Stallmanを輩出したMITのヒッピー文化半端ない。。と思いました。講義はSchemeで書くSchemeのevaluator (interpreter)を足早に説明していて、速すぎてついていけず。。SICPの表示の絵にもあるevalとapplyの説明をしていたように思います。課題は非常に勉強になったので、そちらについて記載します。

課題は与えられた不完全なinterpreterを補完するというもの。コードの最初の方に下記みたいな記述がやたらずらずらあり。言語環境はRacketなのですが、Scheme R5RSにあたる部分だけを使うという方針なのでRacketのデータ構造定義structを使わないので冗長になっているようでした。Racketだとstruct一行でデータ構造定義、predicate、selectorも一度に定義してくれたように思います。

## Plain Scheme
(define (lambda? exp) (tagged-list? exp 'lambda))
(define (lambda-parameters lambda-exp) (cadr lambda-exp))
(define (lambda-body lambda-exp) (cddr lambda-exp))
(define (make-lambda parms body) (cons 'lambda (cons parms body)))

## Racket
(struct lambda (parms body))

evaluatorの本体は下記(課題)。要は与えられた式(expression)のタイプを判別して、それに応じて適切な評価をする、という手順が羅列されているようです。評価の際にかならずenv (environment)が指定されているのも重要で、式の評価というのは名前の対応表であるframeを含むenvironmentがなければなりたたないということのようです。

(define (m-eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp) (lambda-body exp) env))
        ((begin? exp) (eval-sequence (begin-actions exp) env))
        ((cond? exp) (m-eval (cond->if exp) env))
        ((let? exp) (m-eval (let->application exp) env))
        ((time? exp) (time (m-eval (second exp) env)))
        ((application? exp)
         (m-apply (m-eval (operator exp) env)
                  (list-of-values (operands exp) env)))
        (else (error "Unknown expression type -- EVAL" exp))))

一番簡単なのはself-evaluating?でひっかかるもの、下記のように数値、文字列、booleanは、評価すると自分になるので式(exp)がそのまま返るというようになっています。

(define (self-evaluating? exp)
  (cond ((number? exp) #t)
        ((string? exp) #t)
        ((boolean? exp) #t)
        (else #f)))

;; corresponding part of m-eval
        ((self-evaluating? exp) exp)

以降は普通の関数と違い、本体実行前に全ての引数を事前に評価(eager evaluation)しない、special formの定義がずらずら続いています。通常の関数はみな同じ評価方法なので最後のapplication?のところにひっかかるという仕組みのようです。eval-Xという専用評価法が用意されている部分とcond->ifなどと変換法が用意されている部分があります。

むしろこっちの方が複雑に見えますが、通常の関数の評価から見てみます。

(define (application? exp) (pair? exp))
(define (operator app) (car app))
(define (operands app) (cdr app))
(define (no-operands? args) (null? args))
(define (first-operand args) (car args))
(define (rest-operands args) (cdr args))
(define (make-application rator rands)
  (cons rator rands))

;; corresponding part of eval
        ((application? exp)
         (m-apply (m-eval (operator exp) env)
                  (list-of-values (operands exp) env)))

(define (m-apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
          (procedure-body procedure)
          (extend-environment (make-frame (procedure-parameters procedure)
                                          arguments)
                              (procedure-environment procedure))))
        (else (error "Unknown procedure type -- APPLY" procedure))))

(define (list-of-values exps env)
  (cond ((no-operands? exps) '())
        (else (cons (m-eval (first-operand exps) env)
                    (list-of-values (rest-operands exps) env)))))

m-applyという関数に評価を投げています。m-applyの定義をみるとprocedureを引数群に適用するというしくみのようです。m-applyに与えられているのはoperator(関数適用式のcar部分)を評価したもの、とoperands(引数群)を評価して値に変換したもののリストのようです。list-of-valuesは引数を一個ずつ評価していくという関数のようです。

次に専用evauatorを用意しているものを見てみます。eval-definitionはdefine special formを評価するevaulatorのようです。

(define (definition? exp) (tagged-list? exp 'define))
(define (definition-variable exp)
  (if (symbol? (cadr exp))   (cadr exp)   (caadr exp)))
(define (definition-value exp)
  (if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp) (cddr exp))))  ; formal params, body
(define (make-define var expr)
  (list 'define var expr))

;; corresponding part of m-eval
        ((definition? exp) (eval-definition exp env))

(define (eval-definition exp env)
  (define-variable! (definition-variable exp)
                    (m-eval (definition-value exp) env)
                    env))

(define (define-variable! var val env)
  (let ((frame (environment-first-frame env)))
    (let ((binding (find-in-frame var frame)))
      (if binding
          (set-binding-value! binding val)
          (add-binding-to-frame!
           (make-binding var val)
           frame)))))

eval-definitionが行なっているのは、variableの名前をdefinition-variableで取り出して、definition-valueで取り出した値になる式をm-evalで評価した値を結び付けるということのようです。結びつけるというのは、define-variable!で行っており、与えられたenvironmentの直近のframe (current environmentと考えてよいか)に、変数と値のbindingを加えるということのようです。これは副作用を目的としているので複雑になっているようです。

副作用をもたないspecial formであるifの評価を見てみます。

(define (if? exp) (tagged-list? exp 'if))
(define (if-predicate exp) (cadr exp))
(define (if-consequent exp) (caddr exp))
(define (if-alternative exp) (cadddr exp))
(define (make-if pred conseq alt) (list 'if pred conseq alt))

;; corresponding part of m-eval
        ((if? exp) (eval-if exp env))

(define (eval-if exp env)
  (if (m-eval (if-predicate exp) env)
      (m-eval (if-consequent exp) env)
      (m-eval (if-alternative exp) env)))

だいぶシンプルです。要はeval-ifは特別な挙動をそのままScheme組込みのifに丸投げしているようです。predicate部分を評価して、それに応じてtrue節を評価するかfalse節を評価するかを決めています。

私が一番おもしろいと思ったのはcode transformerと呼ばれていたものです。condの例を見てみます。

(define (cond? exp) (tagged-list? exp 'cond))
(define (cond-clauses exp) (cdr exp))
(define first-cond-clause car)
(define rest-cond-clauses cdr)
(define (make-cond seq) (cons 'cond seq))

;; corresponding part of m-eval
        ((cond? exp) (m-eval (cond->if exp) env))

(define (cond->if expr)
  (let ((clauses (cond-clauses expr)))
    (if (null? clauses)
        #f
        (if (eq? (car (first-cond-clause clauses)) 'else)
            (sequence->exp (cdr (first-cond-clause clauses)))
            (make-if (car (first-cond-clause clauses))
                     (sequence->exp (cdr (first-cond-clause clauses)))
                     (make-cond (rest-cond-clauses clauses)))))))

m-evalの対応部分をみると、cond式を見つけたら、まず、cond->ifで変換して、それをm-evalで普通に評価するという形になっています。ifに変換するので、最終的にはeval-ifが出てきますが、おもしろいのはcond->ifです。実際使ってみます。

(cond->if '(cond
            [A do-a]
            [B do-b]
            [C do-c]
            [#t do-d]))
;; =>
;; (if A
;;     do-a
;;     (cond
;;      (B do-b)
;;      (C do-c)
;;      (#t do-d)))

注意が必要なのはここでは、一切評価は行われておらず、cond式がif式にリストをいじることで変換されているだけだということです。プログラムが普通にデータ構造であること(homoiconicity)が、この過程を単純化しているわけですね(参考 Lispの悟りが分かっちゃう新春ポエム)。その後、この変換されたものがm-evalに差し戻しになり評価がおこなわれます。Aがtrueであればdo-aが実行されます。そうでなければ次のbranchをチェックするために残りのcond式をif式に変換、以下同文、となるようです。おそらく、cond->ifをcondを一度にnested ifに変換するようにも実装できそうですが、必要なところだけ変換するこの方法の方が、上の方で終ることが、多ければ無駄が少ないでしょうか。

environmentの実装を見てみるというのも理解を助ける内容でした。下記ではfree variable xを持つadd1 procedureのenvironmentをチェックするprocedure-envという関数のテストです。

(let ([env (setup-environment)])
  (m-eval '(begin
             (define (add-x x)
               (lambda (y) (+ x y)))
             (define add1 (add-x 1))
             (procedure-env add1))
          env))
;; =>
;;(environment
;;    (frame (binding x 1 ()))
;;    #1=(environment
;;        (frame
;;         (binding add1 (procedure #2=(y) #3=((+ x y)) #0#) ())
;;         (binding add-x (procedure (x) ((lambda #2# . #3#)) #1#) ())
;;         (binding car (primitive #<procedure:mcar>) ())
;;         (binding cdr (primitive #<procedure:mcdr>) ())
;;         (binding cons (primitive #<procedure:mcons>) ())
;;         (binding set-car! (primitive #<procedure:set-mcar!>) ())
;;         (binding set-cdr! (primitive #<procedure:set-mcdr!>) ())
;;         (binding null? (primitive #<procedure:null?>) ())
;;         (binding + (primitive #<procedure:+>) ())
;;         (binding - (primitive #<procedure:->) ())
;;         (binding < (primitive #<procedure:<>) ())
;;         (binding > (primitive #<procedure:>>) ())
;;         (binding = (primitive #<procedure:=>) ())
;;         (binding display (primitive #<procedure:mdisplay>) ())
;;         (binding not (primitive #<procedure:not>) ())
;;         (binding * (primitive #<procedure:*>) ())
;;         (binding / (primitive #<procedure:/>) ())
;;         (binding list (primitive #<procedure:mlist>) ())
;;         (binding cadr (primitive #<procedure:mcadr>) ())
;;         (binding cddr (primitive #<procedure:mcddr>) ())
;;         (binding newline (primitive #<procedure:newline>) ())
;;         (binding printf (primitive #<procedure:printf>) ())
;;         (binding length (primitive #<procedure:mlength>) ())
;;         (binding env-variables (primitive #<procedure:env-variables>) ())
;;         (binding env-parent (primitive #<procedure:env-parent>) ())
;;         (binding env-value (primitive #<procedure:env-value>) ())
;;         (binding caddr (primitive #<procedure:mcaddr>) ())
;;         (binding cdddr (primitive #<procedure:mcdddr>) ())
;;         (binding cadddr (primitive #<procedure:mcadddr>) ())
;;         (binding cddddr (primitive #<procedure:mcddddr>) ())
;;         (binding symbol? (primitive #<procedure:symbol?>) ())
;;         (binding pair? (primitive #<procedure:mpair?>) ())
;;         (binding eq? (primitive #<procedure:eq?>) ())
;;         (binding equal? (primitive #<procedure:equal?>) ())
;;         (binding number? (primitive #<procedure:number?>) ())
;;         (binding string? (primitive #<procedure:string?>) ())
;;         (binding boolean? (primitive #<procedure:boolean?>) ())
;;         (binding append (primitive #<procedure:mappend>) ())
;;         (binding caadr (primitive #<procedure:mcaadr>) ())
;;         (binding cdadr (primitive #<procedure:mcdadr>) ()))
;;        (environment)))

出力の一番下にある(environment)という空のenvironmentが大本になります。#1=で示されているglobal environmentには実装されているprimitive procedureの名前対応(binding)がframe内に並んでいます。2回defineをして、bindingを二個足しているので、frameの一番上にはaddxとadd-1 procedureのbindingがあります。更にadd-1はfree variable xをprocedure定義時に外から与えられているので、もう一層environment(#0)が存在して、そこのframeにx = 1のbindingが入っています。実行前の状態なので、ここまでですが実際のprocedureの実行時には引数として与えらえたyのbindingを含む一時environment/frameが実行中のみ作成されるということのようです。SICPの教科書に書いてあるdouble bubbleの説明を見てもいまいちわかりませんでしたが、実装しながら下記のようにclosureを作成してみると良くわかりました。

この課題のクライマックスは作成したevaluatorで、evaluatorのコード自体をREPLで実行してみるというもの。下記はDr.RacketのREPLで実行してみたものです。

Welcome to DrRacket, version 6.1.1 [3m].
Language: racket; memory limit: 128 MB.
#f
> (define (fib n)
  (cond
   [(< n 2) 1]
   [else (+ (fib (- n 1)) (fib (- n 2)))]))
> (time (fib 8))
cpu time: 0 real time: 1 gc time: 0
34

ここまでは普通にRacketでコードを実行しているところ。Fibonacciの8は一瞬で出ます。次はm-evalをRacket上で走らせてみます。

> (load-meval-defs)
loaded
> (driver-loop)

;;; M-Eval input level 1
(define (fib n)
  (cond
   [(< n 2) 1]
   [else (+ (fib (- n 1)) (fib (- n 2)))]))

;;; M-Eval value:
#<void>

;;; M-Eval input level 1
(time (fib 8))
cpu time: 3 real time: 3 gc time: 0

;;; M-Eval value:
34

M-Eval input level 1と出ています。この状態ではRacketのREPL上で、Schemeのevaluatorが走っていて、そこでコードを走らせています。REPLが二段になっているわけです。コード実行に少し時間がかかるようです。さらに、ここでevaluatorを走らせてみます。

;;; M-Eval input level 1
(driver-loop)

;;; M-Eval input level 2
(define (fib n)
  (cond
   [(< n 2) 1]
   [else (+ (fib (- n 1)) (fib (- n 2)))]))

;;; M-Eval value:
#<void>

;;; M-Eval input level 2
(time (fib 8))
cpu time: 1148 real time: 1148 gc time: 10

;;; M-Eval value:
34

evauatorのコードで実行しているREPL上でさらに同じevaluatorのコードでREPLを走らせているわけです。REPLが三段になっているわけですね。もう何が何だかわかりません。同じFibonacciの実行には大分時間がかかっているようです。コードが3回解釈されないといけないのでやむなしでしょうか。REPLを二回exitするとものとRacket REPLに戻ります。

;;; M-Eval input level 2
**quit**

;;; M-Eval value:
meval-done

;;; M-Eval input level 1
**quit**
meval-done

Lecture 5: Debugging

妻出産のため受講せず。Lecture 5のスライドを見るかぎりは、SICPの内容というよりは、モジュラーなコードを書け、テストを書け、バージョン管理せよ、とかgood programming practiceの一般論の話だった様子。スライドの後半でRacketのunit testing frameworkとDr.Racketのdebuggerの話が一瞬ふれられているので、そこは有用かもしれません。。

Lecture 6: Language design and implementation

退院直後のため受講せず。米国では出産後2泊で退院が標準的なようです。Lecture 6のスライドを見ると主にSchemeを使ってObject Oriented Programming Systemを実装しながらOOPについて学ぶといった内容だったようです。私は、R言語があまり一般的な形式のOOPを使わないので、OOP関連は全体的に苦手です。1986年のビデオでは、この内容は存在しなかったっぽいです。

授業のスライド(スライド5-9)では複数のデータ形式に複数の操作がピボットテーブルの様に存在するときにどのようにまとめるかという方法が言及されているようです。functional programmingでは"generic operation"として、ひとつのprocedureにいろいろなデータを投げてprocedureが内部で場合分けで対応する形。OOPではそれぞれのデータ側にmethodとして操作が付属していて、、といった話をしていたものと推測します。これは前述の Courseraコース(リンクは講師のwebsite) でもUnit 8でふれていた内容と思います。R言語は前者の考え方に近い形式と思います。スライドにも出てきますが、前者のまとめかたをすると、generic operationを足すときは変更が一箇所(足すoperationのみ)で楽だけど、データ形式を足すときは全てのgeneric operationを変更しなければいけない。後者のまとめかただと逆になり、データ形式を足すときは変更箇所が一箇所だが、operationを足すときは全てのデータ形式(class)を変更する必要があるとのこと。

授業のコードではOOP sytemをScheme上に構築するコード直リンクということをやっていたようです。仕組みとしては下記のように1個目の要素でマーキングしたリストを使って、既存のSchemeの枠内でclassやinstanceといったものを定義しているようです。

クラス定義

;; Class data abstraction
(define (class? obj)
  (tagged-list? obj 'class))
(define (class-type class)
  (second class))
(define (class-state class)
  (third class))
(define (class-parent class)
  (fourth class))
(define (class-methods class)
  (fifth class))

(define (make-class type state parent methods)
  (list 'class
        type
        state
        parent
        methods))

インスタンス関連

;; Instance data abstraction
(define (instance? obj)
  (tagged-list? obj 'instance))
(define (instance-state inst)
  (second inst))
(define (instance-class inst)
  (third inst))

(define (collect-type class)
  (if (class? class)
      (cons (class-type class)
            (collect-type (class-parent class)))
      '()))

(define (collect-state class)
  (if (class? class)
      (append (class-state class)
              (collect-state (class-parent class)))
      '()))

(define (make-instance class . args)
  (let ((inst
         (list 'instance
               (map (lambda (x) (list x #f)) (collect-state class))
               class)))
    (if (has-method? inst 'CONSTRUCTOR)  ;; if it has a constructor, invoke it
        (apply invoke inst 'CONSTRUCTOR args)
        (void))
    inst))

コードを見ていて気付きましたが、Schemeにはfluid-letというdynamic scopingのためのletがあるんですね。Clojureではbindingだったでしょうか。(脈略なかったです)

課題は前回の課題で作成したScheme evaluatorをさらに拡張することでScheme with OOP的なものを作成して、ゲームをプレイするというもののようです。課題にかなり無理矢理感のあるゲームのバイオハザードみたいなストーリーが書いてあります。実際上はOOP systemのテストは書いてあって、それにあわせてtest-driven development(というか既存のコードの拡張を)するということのようです。とりあえず、テストを走らせてみると"BRAINSBRAINSBRAINSBRAINS"とかなっちゃってます。書いていたひとがゾンビになっちゃたんですね。「かゆい うま」ってやつですね(参考)。

racket@> (run-all-tests)
RUNNING TEST: Getting started: make-instance with no extra args.
test-passed
RUNNING TEST: Getting started: make-instance with arguments.
test-passed
RUNNING TEST: Problem 1: create-class
create-class did not produce a class. Instead, it produced:  BRAINSBRAINSBRAINSBRAINS
  context...:
   /Users/kazuki/Library/Racket/6.1.1/pkgs/compatibility-lib/compatibility/mlist.rkt:47:11: loop
   /usr/local/Cellar/plt-racket/6.1.1/share/racket/collects/racket/private/misc.rkt:87:7

問題5までやるとOOP systemがとりあえず動くようになります。下記みたいな感じでnamed-objectクラスのsicpインスタンスを作成できます。method callも(instance-name 'METHOD-NAME)みたいな感じでinstance.method()的な雰囲気です。

> (driver-loop) ; enter the Scheme with OOP interpreter

;;; OO-Eval input
(define sicp (new named-object 'SICP))

;;; OO-Eval value:
#<void>

;;; OO-Eval input
(sicp 'NAME)

;;; OO-Eval value:
SICP

この時点でゲームを起動することもできます。ゲーム世界のクラス定義はoo-types.scmというファイルでなされています。課題のPDFの8ページに解説があります。"Mightly Chuck Riverの川岸にある無名の工科大学"を舞台にしているそうです(MITはチャールズ川の川岸にある)。自分(avatarクラスのインスタンス)がいる部屋の様子しか見えないようですが、DEITY-MODE(ネ申モード?)にすると他の部屋も見えるようにチートできるとのこと。

> (run-game 'kaz-yos)

At green-building-roof zombie-of-george says -- uuuuUUUUuuuuh.. brains...
You are in great-court
You are not holding anything.
You see stuff in the room: flag-pole lovely-trees
There are no other people around you.
The exits are in directions: east north

;;; OO-Eval input
(screen 'DEITY-MODE #t)

;;; OO-Eval value:
#<void>

とりあえず手頃な凶器をと思って旗のポールを取ろうとしましたが取れませんでした。よっぽど重いのでしょう。

;;; OO-Eval input
(me 'TAKE (thing-named 'flag-pole))

At great-court kaz-yos says -- I try but cannot take flag-pole
;;; OO-Eval value:
#f

西に向ってみるとPDFにあるストーリーに出てくる相棒的なひとを発見したようです。

;;; OO-Eval input
(me 'GO 'east)

kaz-yos moves from great-court to the-dot
At the-dot kaz-yos says -- Hi alyssa-p-hacker
--- Clock tick 0 ---
lem-e-tweakit moves from lobby-7 to dorm-row
At lobby-10 dr-v says -- I take math-book from lobby-10
gjs moves from 10-250 to barker-library
You are in the-dot
You are not holding anything.
You see stuff in the room: dollar-bill
You see other people: alyssa-p-hacker
The exits are in directions: west north
;;; OO-Eval value:
OK

avatarが使えるメソッド一覧。EMIT(放つ?)ってなんでしょうね。

;;; OO-Eval input
((me 'GET-CLASS) 'GET-METHODS)

;;; OO-Eval value:
(LOOK-AROUND
 GO
 CONSTRUCTOR
 SAY
 PEOPLE-AROUND
 STUFF-AROUND
 PEEK-AROUND
 TAKE
 DROP
 HAVE-FIT
 LOSE
 GO-EXIT
 GO
 ENTER-ROOM
 SUFFER
 DIE
 CHANGE-LOCATION
 ENTER-ROOM
 LEAVE-ROOM
 CONSTRUCTOR
 LOCATION
 EMIT
 DESTROY
 CONSTRUCTOR
 ADD-THING
 DEL-THING
 THINGS
 HAVE-THING?
 CONSTRUCTOR
 NAME
 DESTROY
 GET-CLASS)

この後はmixinを実装するという問題もあるのですが、力尽きました。。

Lecture 7: Continuations, concurrency, lazy evalutation, and streams

前日の時点で、歴史上まれに見る大雪の予報で授業がキャンセル。マサチューセッツ州知事が緊急事態宣言しちゃって、公共交通機関は動かない予定とのこと。

=> 結局丸一日、周囲の学校も職場もみな休みになっていました。biomedicalの基礎系の研究室には日本人ポスドクだけは来ていたみたいですが。。。

以降は、復習資料(recitation; PDF)の内容だけいくつか。

;;; Stream operators
;; Stream constructor macro (cdr part delayed)
(define-syntax cons-stream
  (syntax-rules ()
    [(_ a b)
     (cons a (delay b))]))

;; Stream car part selector
(define stream-car car)

;; Stream cdr part selector (cdr part forced)
(define stream-cdr
  (lambda (s)
    (force (cdr s))))

delayとforceはGuile Schemeではprimitiveとして実装されていました。delayは計算を遅延させて、"呼ばれたら計算するよ"という意味のpromiseというものを返すとのことです。

R5RSでは実装されていないようなので下記の様にdelayをマクロとして定義、forceを通常のprocedureとして定義すれば良いようです。

;;; DIY implementation
(define-syntax my-delay
  (syntax-rules ()
    [(delay expr)
     (lambda ()
       expr)]))
(define (my-force delayed-expr)
  (delayed-expr))

(my-delay (+ 1 2))
;; => #<procedure 10672d220 at <current input>:143:0 ()>
(my-force (my-delay (+ 1 2)))
;; => 3

資料の例をやってみます。0がならんだ無限sequenceになっています。

;;; Infinite sequence of 0's
(define zeros
  (cons-stream
   0
   zeros))

zeros
;; => (0 . #<promise #<procedure 10719a840 at <current input>:22:2 ()>>)
(stream-car zeros)
;; => 0
(stream-cdr zeros)
;; => (0 . #<promise #-1#>)
(stream-car (stream-cdr zeros))

stream用のnthを定義してみます。確かにずっと0が続いているようです。

(define (stream-nth s n)
  (if (<= n 0)
      (stream-car s)
      (stream-nth (stream-cdr s) (- n 1))))
;; 1 millionth element
(stream-nth zeros 999999)
;; => 0

ずっと同じ数字だと本当に計算しているかわからないので自然数の無限数列を定義します。stream-consでのやりかたが思いつかなかったので、とりあえず Coursera Programming Languagesの課題でみかけたやりかたでやってみます。

;;; Infinite sequence of natural numbers
(define nats
  (letrec ([f (lambda (x)
                (cons
                 x
                 (delay (f (+ x 1)))))])
    (f 1)))

;; First element
(stream-car nats)
;; => 1

関数型言語でよく見掛けるようなtakeを定義しておきます。これは最初のn個の要素をrealizeします。

;;; take for streams
(define (take n s)
  (map (lambda (x) (stream-nth s x)) (iota n)))
;; First 10 elements
(take 10 nats)
;; => (1 2 3 4 5 6 7 8 9 10)

上記のnatsの定義だとabstraction不足な感じがします。復習課題での解法はこんなのでした。

;;; Define a function to map a binary operator over two streams
(define (map2-stream op s1 s2)
  (cons-stream
   ;; Map the operator to first elements
   (op (stream-car s1)
       (stream-car s2))
   ;; recurse
   (map2-stream op
                (stream-cdr s1)
                (stream-cdr s2))))

;; Arithmetic operators
(define (add-streams s1 s2) (map2-stream + s1 s2))
(define (sub-streams s1 s2) (map2-stream - s1 s2))
(define (mul-streams s1 s2) (map2-stream * s1 s2))
(define (div-streams s1 s2) (map2-stream / s1 s2))

;; Infinite sequence of 1's
(define ones (cons-stream 1 ones))

;; Infinite sequence of natural numbers
(define nats
  (cons-stream
   1
   (add-streams nats ones)))

;; First 10 elements
(take 10 nats)
;; => (1 2 3 4 5 6 7 8 9 10)

すごくabstractになって今度は何が起っているのかわかりにくいですが、一個づつずれながら1の無限数列が、縦方向に足しあげられているということでしょうか。後になるほど足す1の数が増えていくと。

1 1 1 1 1 1 1 1 1 1 ....
  1 1 1 1 1 1 1 1 1 1 ....
    1 1 1 1 1 1 1 1 1 1 ....
      1 1 1 1 1 1 1 1 1 1 ....
        1 1 1 1 1 1 1 1 1 1 ....
         ..........

Streamのかけ算をつかえばこんなのもできますね。

;;; Infinite sequence of squared natural numbers
(define squared-nats (mul-streams nats nats))

(take 15 squared-nats)
;; => (1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)

Clojureだと標準でinfinite sequence (これもstreamと呼ぶのでしょうか?)をサポートしているので、直ぐできますね。

(defn square [n] (* n n))
(def nats (iterate #(+ % 1) 1))
(take 15 (map square nats))
;; => (1 4 9 16 25 36 49 64 81 100 121 144 169 196 225)

Factorialsという問題は、stream用のmapを用意してこんな感じでしょうか。こちらで先程のsquared-natsを定義することもできますね。

;;; Infinite sequence of factorials
(define (map-stream op s)
  (cons-stream
   (op (stream-car s))
   (map-stream op
               (stream-cdr s))))

(define (factorial n)
  (define (helper n acc)
    (if (<= n 0)
        acc
        (helper (- n 1) (* acc n))))
  (helper n 1))

(define facts (map-stream factorial nats))
(take 7 facts)
;; => (1 2 6 24 120 720 5040)

Code IQで出ていた円周率の近似計算の問題が締め切ったので、streamを使ってやってみます。まずは準備としてstream用のfilterを定義します。

;;; Stream filter
(define (filter-stream pred s)
  (if (pred (stream-car s))
      (cons-stream (stream-car s) (filter-stream pred (stream-cdr s)))
      (filter-stream pred (stream-cdr s))))

(take 10 (filter-stream odd? nats))
;; => (1 3 5 7 9 11 13 15 17 19)

分母と分子のペアのstreamを作成します。分母と分子のstreamを個別に作成して、先程のmap2-streamでペア作成します。

;; Stream of numerator-denominator pairs
(define numer-stream (cons-stream 4 squared-nats))
(define denom-stream (filter-stream odd? nats))
(define numer-denom-pair-stream (map2-stream list numer-stream denom-stream))

(take 10 numer-denom-pair-stream)
;; => ((4 1) (1 3) (4 5) (9 7) (16 9) (25 11) (36 13) (49 15) (64 17) (81 19))

あとは一段一段の計算の関数を作成します。こちら の二個目の方法です。

;;; Procedure to perform one step in the continued fraction method 2
;; http://en.wikipedia.org/wiki/Approximations_of_π#Continued_fractions
(define (add-and-devide lst acc)
  (let ([a (car lst)]
        [b (cadr lst)])
    (/ a (+ b acc))))

最初の方でも出てきたfold-rightを使ってまとめます。

;;; fold-right procedure
(define (foldr f init lst)
  (if (null? lst)
      init
      (f (car lst)
         (foldr f init (cdr lst)))))

;;; Pi approximator
(define (pi-calc n)
  (foldr add-and-devide 0 (take n numer-denom-pair-stream)))

;;; First 10 approximations
(map pi-calc (take 10 nats))
;; => (4 3 19/6 160/51 1744/555 644/205 2529/805 183296/58345 3763456/1197945 4317632/1374345)
(map exact->inexact (map pi-calc (take 10 nats)))
;; => (4.0 3.0 3.1666666666666665 3.1372549019607843 3.142342342342342 3.1414634146341465 3.1416149068322983 3.1415888250921244 3.1415933118799275 3.14159254044654)

;; Reach the maximum precision at 22
(map exact->inexact (map pi-calc (list 1 10 21 22 100 1000)))
;; => (4.0 3.14159254044654 3.1415926535897936 3.141592653589793 3.141592653589793 3.141592653589793)

22回目で浮動小数点演算の限界値まで至るようです。

Lecture 8: Memory management, garbage collection, and the lambda calculus

最終日。なぜか参加者は最初の半分弱(20名ぐらい)になっていましたが。。内容はlambdaがあればなんでもできる!というはなしと、Lecture 7のcontinuation, concurrency, streamを無理矢理つめこんだ感じでした。

まず、最初にSchemeでSchemeのevaluatorを書く(meta-circular evaluator)という行為は意味があるのかという話。これは何もevaluatorだけではなくて、compilerも書けるよと。つまり、SchemeでScheme -> Assemblyの変換を行うcompilerを書く。ここにSchemeで書かれたSchemeのevaluatorを通すと、assemblyで書かれたScheme evaluatorが出来ると。さらに、compiler自体をそのcompilerに通すと、assemblyで書かれたScheme -> Assemblyのcompilerが出来るとのこと(スライドp22より)。なるほどこれなら実用性がある行為に思えますね。

lambda calculusの部分はどこまでprimitiveを減らすことができるかいう導入から、ifのようなspecial formやbooleanも他のもの(lambda)で表現できる、数字すらChurch numberというかたちでlambdaで表現できるというようなはなしでした。

たとえばcons cellとcar/cdrは下記の様にlambdaだけで表わせるようです。cons cellがprocedureを引数cとしてとるprocedureとして定義されています。car/cdrはそれぞれ二つ引数をとって前者/後者を返すprocedureになっています。これがcons cellに渡るとaとbにcar/cdrが適用されて前者/後者がとりだされるということのようです。

;;; pair construction and selection
(define (cons a b)
  (lambda (c)
    (c a b)))
(define (car p)
  (p (lambda (a b) a)))
(define (cdr p)
  (p (lambda (a b) b)))

(define pair1 (cons 1 (cons 2 '())))
(car pair1)
;; => 1
(cdr pair1)
;; => #<procedure 10ac241b0 at <current input>:5:2 (c)>
(car (cdr pair1))
;; => 2

Booleanとandも下記のごとくprocedureで表されるようです。

(define (true x)
  (lambda (y) x))

(define (false x)
  (lambda (y) y))

(define (and a b)
  ((a b) false))

(and true true)
;; ((true true) false)
;; ((lambda (y) true) false)
;; true
;; => #<procedure true (x)>

(and true false)
;; ((true false) false)
;; ((lambda (y) false) false)
;; false
;; => #<procedure false (x)>

このセクションが終ったときに、これであなたもOrder of Lambda (ラムダ団?)の一員だ!ということで、ラムダ団の缶バッジを貰いました。普通にうれしかったです。

lambda.png

Continuationという概念は今回初めて学んだので例示しておきます。こちらの資料 の分になります。continuationというのは、"で、そのprocedureの返す結果で何をしたいの"という問いに対する答えということのようです。つまり、現在のprocedureが結果を返した後の残りの計算です。この残りの計算をprocedureとして渡していく形のプログラムをcontinuation passing sytleというようです。資料の例を見てみます。例はおなじみのfactorialです。

まずは、通常の再帰と末尾再帰です。再帰では計算まちがスタックを消費する様子が三角形から見てとれます。

;;; Regular linear recursion
(define (factorial n)
  (if (= n 0)
      1
      (* n (factorial (- n 1)))))
;;
;; scheme@(guile-user)> ,trace (factorial 5)
;; trace: |  (#<procedure 105893500> #(#<directory (guile-user) 1048f2c60> #f))
;; trace: |  #(#<directory (guile-user) 1048f2c60> factorial)
;; trace: (#<procedure 105896880 at <current input>:129:7 ()>)
;; trace: (factorial 5)
;; trace: |  (factorial 4)
;; trace: |  |  (factorial 3)
;; trace: |  |  |  (factorial 2)
;; trace: |  |  |  |  (factorial 1)
;; trace: |  |  |  |  |  (factorial 0)
;; trace: |  |  |  |  |  1
;; trace: |  |  |  |  1
;; trace: |  |  |  2
;; trace: |  |  6
;; trace: |  24
;; trace: 120

末尾再帰(実質ループ)にすると"現在までの計算結果の値"を順次accmulatorにためながら進めていくため、スタックが増えません。

;;; Tail-recursion (iterative)
(define (fact-helper n acc)
    (if (zero? n)
        acc
        (fact-helper (- n 1) (* acc n))))
(define (fact-iter n)
  (fact-helper n 1))
;;
;; scheme@(guile-user)> ,trace (fact-iter 5)
;; trace: |  (#<procedure 10bb63440> #(#<directory (guile-user) 10afb6c60> #f))
;; trace: |  #(#<directory (guile-user) 10afb6c60> fact-iter)
;; trace: (#<procedure 10bb79c80 at <current input>:142:7 ()>)
;; trace: (fact-iter 5)
;; trace: (fact-helper 5 1)
;; trace: (fact-helper 4 5)
;; trace: (fact-helper 3 20)
;; trace: (fact-helper 2 60)
;; trace: (fact-helper 1 120)
;; trace: (fact-helper 0 120)
;; trace: 120

下記がcontinuation passing sytle (以下CPS)です。形態としては末尾再帰になっています。通常のiterationでは"現在までの計算結果の値"があった部分にprocedureが存在するのがわかります。これは、"現在までの計算結果の値"のかわりに"これからの計算方法(procedure)"を渡しています。一番最初に渡しているのはidentity procedureで、fact-cps 5の結果がでたら、"そこからはただそのまま値をくれ"という指示をしていることを示します。以降はこの簡単な指示書に次々と指示を書きこんでは渡しているということになります。

;;; Continuation passing style
(define (fact-cps n cont)
  (if (zero? n)
      (cont 1)
      (fact-cps (- n 1)
                (lambda (x) (cont (* n x))))))
;;
;; scheme@(guile-user)> ,trace (fact-cps 5 (lambda (x) x))
;; trace: |  (#<procedure 1053fb140> #(#<directory (guile-user) 1048f2c60> #f))
;; trace: |  #(#<directory (guile-user) 1048f2c60> fact-cps)
;; trace: (#<procedure 1054426a0 at <current input>:198:7 ()>)
;; trace: (fact-cps 5 #<procedure 10557d820 at <current input>:198:19 (x)>)
;; trace: (fact-cps 4 #<procedure 105583b70 at <current input>:160:16 (x)>)
;; trace: (fact-cps 3 #<procedure 105745c60 at <current input>:160:16 (x)>)
;; trace: (fact-cps 2 #<procedure 105745090 at <current input>:160:16 (x)>)
;; trace: (fact-cps 1 #<procedure 105807180 at <current input>:160:16 (x)>)
;; trace: (fact-cps 0 #<procedure 1058ef2a0 at <current input>:160:16 (x)>)
;; trace: (#<procedure 1058ef2a0 at <current input>:160:16 (x)> 1)
;; trace: (#<procedure 105807180 at <current input>:160:16 (x)> 1)
;; trace: (#<procedure 105745090 at <current input>:160:16 (x)> 2)
;; trace: (#<procedure 105745c60 at <current input>:160:16 (x)> 6)
;; trace: (#<procedure 105583b70 at <current input>:160:16 (x)> 24)
;; trace: (#<procedure 10557d820 at <current input>:198:19 (x)> 120)
;; trace: 120

上記のものだけだとよくわからないので具体化してみます。最初はidentity procedure("結果をそのまま返す")ですが、次のステップでは"結果に5をかける、そのまま返す"になっています。その次では、"結果に4をかける、結果に5をかける、そのまま返す"になっています。最終的にfact-cps 0の結果に"1,2,3,4,5を順番にかける、そのまま返す"という指示書がprocedureとしてわたっています。

;;; Continuation passing in action
;; Want to return the result of fact-cps 5
(fact-cps 5 (lambda (x) x))
;; Want to multiply the result of fact-cps 4 with 5, and return
(fact-cps 4 (lambda (x) ((lambda (x) x) (* 5 x))))
;; Want to multiply the result of fact-cps 3 with 4 and 5, and return
(fact-cps 3 (lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))))
;; Want to multiply the result of fact-cps 2 with 3, 4, and 5, and return
(fact-cps 2 (lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))))
;; Want to multiply the result of fact-cps 1 with 2, 3, 4, and 5, and return
(fact-cps 1 (lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))))
;; Want to multiply the result of fact-cps 0 with 1, 2, 3, 4, and 5, and return
(fact-cps 0 (lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))) (* 1 x))))

fact-cps 0はif式がtrueになりますので、(cont 1)、つまり、渡された指示書(procedure)を1に適用せよということになります。つまり、"1をとる、1,2,3,4,5を順番にかける、そのまま返す"という式が完成して実行が開始されます。具体的には下記の様にたまねぎの皮をむくようにlambdaを外からむいていきます。最終的には"120をとる、そのまま返す"という式になり、120という評価結果がでます。

;;; Passed procedures are executed
;; (cont 1)
((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))) (* 1 x))) 1)
((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))) (* 1 1))

((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))) (* 2 x))) 1)
((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))) (* 2 1))

((lambda (x) ((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 x))) 2)
((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) (* 3 2))

((lambda (x) ((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 x))) 6)
((lambda (x) ((lambda (x) x) (* 5 x))) (* 4 6))

((lambda (x) ((lambda (x) x) (* 5 x))) 24)
((lambda (x) x) (* 5 24))

((lambda (x) x) 120)
120

Schemeではこのcontinuation("計算結果に対して、今後やること")をプログラムから捉えて保存することができるそうです。例を見てみます。

;;; call/cc example
;; define a variable
(define c #f)

;; set! c as continuation in following
(+ 10 (* 3 (call/cc
            (lambda (cont)
              (set! c cont)
              (cont 5)))))
;; => 25

call/ccは自分の外側にある式、つまり、(call/cc ...)の結果に対して行うことになっている計算を捉えます。自分の括弧の外側に出ていって、残りの計算をかきあつめてくるわけですね。他のプログラミングの概念と大きく違っている感じがします。その残りの計算continuation(実質はprocedure)はcall/ccの引数になっているprocedureに渡されます(contになります)。"その残りの計算(continuation)"が、cと結びつけられます。次に"その残りの計算(continuation)"が5に適用されます。この時点で下記のlambda部分に5がつっこまれて実行される感じでしょうか。call/ccは自分の外側にある残りの計算を持っていってしまったので、この外側にはなにもなくなっていますので、25が出て計算終了です。

(cont 5)
((lambda (x) (+ 10 (* 3 x))) 5)
(+ 10 (* 3 5))
25

おもしろいのはcに捉えられている、"残りの計算(continuation)"を適用してみた場合です。3という値に"この残りの計算"を適用すると予想通り3倍して10を足して19になります。

(c 3)
;; => 19

しかし、そのまわりに更に式があった場合は無視されてやっぱり19になります。なぜなら、3という値に対する"残りの計算"は、"3倍して10を足す"だけだからです。計算を横取りしてオレオレ結末を押し付けているわけですね。

(+ 3 (* 99 (c 3)))
;; => 19

continuationを適用する前にあるものは先に評価されますので影響を受けません。下記では9が計算された時点で"残りの計算"は、"3倍して10を足す"だけになって、37となります。

(+ 3 (* 99 (c (* 3 3))))
;; => 37

これの使い道は、、資料ではmulti-threadもどき(?)を作成しているようですが、正直十分理解できませんでした。

総括

Lispの聖地MITで簡略版SICP(シクピー)の授業(6.037)を受講したので、まとめを作成しました。私は普段Rぐらいしか書かないのですが、プログラムの評価におけるenvironmentとscopeの概念の理解が進んだのは有用だったと思います。

資料に"Scheme is useful because code and data are just a quote away"という名言がありました(スライドp17)。コードとデータ表現の同一性(homoiconicity)ということの理解が若干得られて(Lecture 4参照)、Lispの悟り に少し近づいたかもしれません。