3impを読みながらわかったことを書いてく
2学期が終わって、2週間の休みに入りました。
部屋にいると息が詰まるし、常時接続環境に生産性を著しく低下させられるので、用事がない日は、近くの公園でローカルに保存したpdfを読んだりしてます。
それはそうと、Lispにぞっこんで、色々読み漁り始めてから約2週間が経ちました。プログラミングGauche,R5RSは読み終わり、現在3imp, The Little Schemer, SICPを並行して読み進めています. 英語の技術文を読むのが楽しすぎてすてき。
今日は3imp.pdfの3.4章まで読み終わったのを記念して、今後のためにメモを残しておきます。
すげー長いので続きに書きます
Three Implementation Models for Scheme (3imp)は題名の通り、Schemeの3つの実装方法についての文章で、僕が読み終えた3.4章はそのうちの最初のヒープベースな処理系の実装方法が述べてあります。
3章以前はSchemeがどんな言語か、とか、クロージャ、継続とかの概念の解説です。まずはそこからメモ:
基本情報:
- Scheme
- Lisp方言・ 非純粋関数型・レキシカルスコープ・ダイナミックタイピング・なんでも再帰・λ
- 関数型言語
- 引数を渡すと評価した結果が戻ってくるブラックボックスを入れ子にしてプログラムを組む。
- 参照透過性 - 変数は一度定義したら再代入はできない。
- レキシカルスコープ
- λが入れ子になっているとき、あるλは、自分より内側のλたちの変数を見れない。
- 内側のλからは、外側のλたちの変数を見れる。
- ダイナミックタイピング
- 動的型付け
- Cみたいに int hoge とか書かなくていい
- 実行時に型が合わなかったらエラー
- 何でも再帰
- CLerと違い、Schemerは積極的に再帰で書く
- 末尾呼び出しは単純なジャンプになるから速度面はクリア
- λ
次は2章以前:
そうそう、この前pythonizedLispとか言って純Lisp風なLispを書いたのですが 、defineがない上にクロージャがないので、ループが出来ないのでチューリング不完全なのです。クロージャがあればYコンビネータっていう魔法のlambda式で名無しの再帰が書けるようです。 続いて第3章:
- 環境
- λによって作られる、変数と値(λへの引数)を対にして保存したリスト ‘([(d e) . (3 4)] [(c) . (2)])みたいな形(ここでは！)
- consで作るから内側のlambdaの対が上にくる
- Closure
- クロージャ,第一級関数
- lambdaで作る
- '(λの本体と 環境 未束縛変数)
- High-order functions
- 高階関数
- 関数(クロージャ)を返す関数。カリー化とかできる
- (lambda (x) (lambda (y) (+ x y))
- こうするとクロージャが返ってくる
- 関数が第一級じゃないとできない
- Lazy Evaluation
- 遅延評価
- クロージャは、評価される時に初めて計算を行う。(lambda () (+ 1 2))っていうのは (lambda () 3)じゃない。( (lambda () (+ 1 2)) )って評価されてから+する。
- Continuation
- 継続
- CPS
- *2 2 3 +) ;=>5
- call/cc
- call-with-current-continuation
- (lambda (x) (call/cc (lambda (cont) (if (= x 0) (cont “zero") (/ 1 x)))))
- xが0だったら"zero",それ以外だったら1÷xの値が返る
コンパイラとVMのソースは写経したってしょうがないので、3imp.pdfの70ページちょい前あたりをみる。 補助関数:Heap based model
- ここでのヒープは木構造ではなく、メモリのヒープ領域のこと。クロージャと継続があるせいで、変数の束縛を無期限に保存しなくちゃいけない。スタック(後入れ先出し)ではこれができないから、環境をヒープに置く。
- 必要なデータ構造
- 環境,コールフレーム,コントロールスタック,クロージャ,継続
- 環境
- 上記
- コールフレームとコントロールスタック
- コールフレーム
- ある関数aが他の関数bを呼んだときに作られる。関数bの評価が終わる(aに値が返却される)まで、関数aは現在の状態を保持していなくちゃいけない。
- ’(次に評価する式 ・ 環境 ・ 評価された引数のリスト ・ 次のフレーム)
- コントロールスタック
- ’(フレーム ・ 次のフレーム ・ 次のフレーム ・・・)なスタック.フレームが作られたら評価前にここにコンスされる.評価が終わったらpop
- クロージャと継続
- クロージャ
- 上記
- *3 (y))
- 継続
- 本体部にスタックが保存された特別なクロージャ。実行時に、スタックを保存されたスタックで置き換えて、継続の引数を継続(call/ccの親)にわたす
- 実装に必要なレジスタ
- a - アキュムレータ,累算器
- x - 次に評価する式
- e - 現在の環境.関数適用の前にフレームに保存される
- r - 既に評価した引数の値のリスト.すべての引数評価が終わったら環境に追加.関数適用の前にフレームに保存される
- s - 現在のスタック
実装
- VMが解釈するアセンブリコード
- (halt) - 実行の終了.この時点でアキュムレータに乗っかってる値が最終的な戻り値になる
- (refer var x) - 環境から変数varに束縛されてる値を探してきてアキュムレータにのっける。次に実行するのはx
- (constant obj x) - objをアキュムレータにのっける。次に実行するのはx
- (close vars body x) - 本体body,環境,vars(変数のリスト) からクロージャを作ってアキュムレータにのっける。次に実行するのはx
- (test then else) - アキュムレータがヌルくなければ次に実行するのはthen。ヌルかったら次に実行するのはelse
- (assign var x) - 環境中のvarに束縛されている値をアキュムレータの値で置き換える(副作用)。次に実行するのはx
- (conti x) - スタックから継続をつくってアキュムレータに置く。次に実行するのはx
- (nuate s var) - スタックをsに戻す。varの値(環境からフェッチ)をアキュムレータにのっける。次に実行するのは(return)
- (frame x ret) - 環境と、r(評価済み引数リスト)、retからフレームを作ってスタックに積む。フレームのxはret。rを空にする。次に実行するのはx
- (argument x) - アキュムレータの値をrにcons。次に実行するのはx
- (apply) - rにアキュムレータのってるクロージャを適用する。
- (クロージャ内の環境)に(クロージャ内の変数とフレームのr)をコンスした新しい環境を作って、それを現在の環境と置き換える。rを空にする。次に実行するのはクロージャの本体
- (return) - フレームをスタックから取り除き、e,r,x,sをリセットする。 -残るのは前のフレームとアキュムレータ
lookupはこの前書いたpl-assocと同じことをする。-環境から変数と値のペアを取り出す. closureは'(本体 ・ 環境 ・ 変数)なリストを作る. continuationは継続を作る。これが評価されたらnuateが起動する。 call-frameは’(x e r s)なリストを作る extendは環境に束縛を追加する evaluateはトリガ
