狠狠撸

90分
Scheme to C
(勝手に抄訳版)
元の文章との整合性は保証しないよ
Orignal is written by Marc Feeley

Goals
? Goals
– Scheme から C へのコンパイル
– 家に帰ってから
– 90分でできちゃうもんね。
? Non-goals
– Scheme の RnRS への互換性
– C interoperability
– 最適化とかパフォーマンスとか
– Gambit-C とか
? ターゲットにしている読者
– Scheme/Lisp プログラマ
– 後悔関数に興味がある人

何が難しいの？
? Scheme にあって C にないもの
– 末尾呼び出し(末尾再帰）
– 継続(1st class のオブジェクトとしての)
– 無限エクステントのクロージャ(Closure Of Indefinite
Extent)
– GC (自動的なメモリマネージメント機構）
? ということは、、、
– すべての Scheme を C に変換できない
– 継続の実装が必要
– クロージャの実装が必要
– GC みたいなのが必要
? あとは簡単!!

末尾呼び出し(Tail-calls)と GC (1)(*1)
? Schemeでは、次の関数は与えられた n の値に
拘わらず必要とするメモリ領域(*2) は一定だ。（計
算に必要“だった”(*3)数列の領域は捨てちゃう）
(define f
(lambda (n x)
(if (= n 0)
(car x)
(f (- n 1)
(cons (cdr x)
(+ (car x)
(cdr x)))))))
(f 20 (cons 1 . 1)) ; => 10946 (*4)
(*1) 元のPPTでは 1ページで説明されています。
入りきらなかったので(1)(2)と分割しました。
(*2) 原文では constant space としか書いてありません。
メモリやスタックという言葉は使っていません。
Scheme ではスタックを使わない方が実装上よいからでしょう。
(*3) 強調は訳者
なおこの手の”勝手な解釈”については以後コメントしません。
(*4) 原文に BUG があったので勝手に修正

末尾呼び出し(Tail-calls)と GC (2)
? (前頁のプログラムは)再帰呼び出しが末尾呼
び出しになってるだろ。結果として関数 f は
ループになるんだ。
? 使用されなくなった領域は GC によって回収さ
れるから心配ない。

クロージャ(1)
? Scheme の関数は階層化でき、変数はレキシ
カル?スコープ
? (lambda (x) (+ x n)) の中を見ると
– x は束縛された x の出現
– n は自由な n の出現
? 変数は最も近い包まれたラムダ式、すなわち
現在のアクティブなフレームのスロットに束縛
される

クロージャ(2)
? クロージャはその生成した親より長生きする
こともある。
? アクティブなフレームについての伝統的な（連
続した）スタックアロケーションではうまく動作
しない。
? クロージャはその親のクロージャのアクティブ
なフレームを”思い出す”必要があり、GC はア
クティブなフレームワークを必要でないと判断
したときのみ回収する必要がある。

ファースト?クラスの継続(*1)(1)
? ファースト?クラスの継続だと、通常の処理の流れを変
えて、意図的な処理順に変更することが出来るんだ。
? 継続は値としての結果を待ちの中断された計算の値
を保持しいるという特徴もある。
? 例えば REPL で上記のプログラムを動かしたとすると、
read でユーザからの数字入力を待つのはわかるね。
読み取りのための関数呼び出しとしての継続は値を
取得するという計算を指し示し、1が加えられ、ルート
の計算がなされ、結果が表示され、次の REPL の入力
待ちへと進む。継続のイメージはこれに近い。
(*1)frist-class continuation :
Scheme では言語“そのもの”の機能として継続があり、
関数呼び出しのように使える。
> (sqrt (+ (read) 1))

ファースト?クラスの継続(2)
? call/cc は継続を lambda 式の引数に返してくれて、その継
続を呼ぶことで計算の中断が再開できる。
? (call/cc f) のように書いた場合関数 f は実際に実行される。
? ファースト?クラスの継続を使うと backtracking, coroutining,
multithreading, non-local escapes (for exception handling)
などが簡単に実現できる。なんだかすごそうだろ？
> (sqrt (+ (call/cc
(lambda (cont)
(* 2 (cont 8))))
1))
=>3

? 例1: non-local escape
(define (map-/ lst)
(call/cc
(lambda (return)
(map (lambda (x)
(if (= x 0)
(return #f)
(/ 1 x)))
lst))))
(map-/ ’(1 2 3)) ; => (1 1/2 1/3)
(map-/ ’(1 0 3)) ; => #f

? 例 2: backtracking
? 次の式の X,Y,Z を求めるとしよう
2<= X, Y, Z <=9 and X2 = Y2 + Z2
? in-range と fail はどう実現しているか？興味深いでしょ？
(let ((x (in-range 2 9))
(y (in-range 2 9))
(z (in-range 2 9)))
(if (= (* x x)
(+ (* y y) (* z z)))
(list x y z)
(fail))) ; => (5 3 4)

(define fail
(lambda () (error "no solution")))
(define in-range
(lambda (a b)
(call/cc
(lambda (cont)
(enumerate a b cont)))))
(define enumerate
(lambda (a b cont)
(if (> a b)
(fail)
(let ((save fail))
(set! fail
(lambda ()
(set! fail save)
(enumerate (+ a 1) b cont)))
(cont a)))))

Scheme から C のコンパイルの方針
? コンパイル作業として複数のソースからソース(Source-
to-Source)への変換を採用
? 各Source-to-Source変換はつまりはコンパイラであり入
出力共に同じ言語, つまり Scheme。
? それぞれの変換のたびに入力より簡単にコンパイル
可能な状態にする。（段階的に特別な機能を使わない
ようにする）
? 最終的な Scheme のコードは容易に C に変換できるも
のとする。
? 重要なのは２つの Source-to-Source :クロージャー変
換(Closure-conversion)と CPS 変換(CPS-conversion)

Scheme のサブセット
? 実際のフルスペックの Scheme をコンパイルするのは
難しいんだよね。そこで簡単な Scheme のサブセットを
扱うことにするよ。
– プリミティブは(+, -, +, =, <, display) にとどめ、すべて整数
のみの対応。そして call/cc も考慮しよう
– Only small exact integers and functions (and #f=0/#t=1)
– Only the main special forms and no macros
– set! で許される代入はグローバル変数へのみ
– No variable-arity functions
– No error checking
? 残りの実装は読者への宿題としよう。

クロージャ変換(1)
? 問題：自由変数(*1)へのアクセスはどうする？
? どのようにして関数 F 内で x, y の値を得たら
よいと思う？
(lambda (x y z)
(let ((f (lambda (a b)
(+ (* a x) (* b y)))))
(- (f 1 2) (f 3 4))))
(*1) ヤクチュウ。いきなり自由変数といってもなんのことやら。
コンパイラでは必ず出てくる話です。事前に勉強しておきましょう。

? 最初に思いつく方法として自由変数を引数に入れ込んでしまうと
いうのがあるね。
? この変換はラムダ?リフティング(lamda lifting)と呼ばれていて、この
ケースではうまくいくけど、万能ではないんだ(*1)。
? そこでクロージャ(closure)の登場だ。自由変数を関数と共に一つ
のオブジェクトにパッケージする方法だ。
(lambda (x y z)
(let ((f (lambda (x y a b)
(+ (* a x) (* b y)))))
(- (f x y 1 2) (f x y 3 4))))
(*1) ヤクチュウ。下のように関数を返すケースでは x y を入れ込みようがない。
(lambda (x y z)
(let ((f (lambda (a b)
(+ (* a x) (* b y)))))
ｆ))

? 次に考えられる方法は関数呼び出し時に自由変数を含む
構造体のようなものを作り出し(*1)関数の引数にも追加する
ことだ。
? この方法で自由変数の排除ができるね。
? 各ラムダ式は(関数そのものじゃなくて)一種の指示書のよ
うなブロックを表すことになるんだ。(just like in C)
(lambda (x y z)
(let ((f (vector
(lambda (self a b)
(+ (* a (vector-ref self 1))
(* b (vector-ref self 2)))
x
y)))
(- ((vector-ref f 0) 1 2) ((vector-ref f 0) 3 4))))
(*1) ヤクチュウ。一応書いておくよ。原文は build a structure で
構造と書いてあるけど、C を思わせる構造体とは書いていない。

クロージャ変換のルール
? (lambda (P1 … Pn) E) =
(vector (lambda (self P1…Pn) E) v…)
v… で表されているのが自由変数のリスト
(lambda (P1…Pn) E)
? v = (vector-ref self i)
v は自由変数で i はラムダ式をも含むオブジェクトにある自
由変数のリスト内の位置
? (f E1…En) = ((vector-ref f 0) f E1 … En)
この変換は f が変数であっても、CPS変換の後であろうとも
なりたつということに注目してほしい。f=(lambda…) のよう
な特別な場合の扱いは例外だけどね。
? そして、クロージャとクロージャの参照(closure-ref)は動的
型付けを可能とする点も重要だ

CPS変換(1)
? 継続は次の性質を持つので GC と調整が必要だ
– 不明瞭な使用範囲(call/cc があるからね)
– 何度でも呼びだし可能(X2=y2+Z2 がいい例だ)
? 継続は関数から戻ったからといって、再利用の
ために破棄することは出来ないんだ。
? だから、GC は使用中の継続に対して適切な対
応をとる必要がある。
? “Simple” solution:あるプログラムへの変換は継
続が明示的にそのプログラムから操作されるオ
ブジェクトとし、そしてGC がそれらを扱えるものと
しよう。

CPS変換(2)
? ここでCPS変換の基本的なアイデアを披露し
よう
– ある式の評価は結果として値を生成し(produce)、
その値は継続(*1)に消費(consume)される。
– 継続がある関数を表現可能であるなら、それは”
継続へ値を送信する”かのような関数コール
(function call)として表現することになるだろうね。
(*1) ヤクチュウ。気持ちとしては“次の継続に”と書きたい。
意味が重複しているからおかしいのだけどね。

CPS変換(3)
? プログラムで例をあげよう。
? (square 10) の継続は、次の計算として、１が加
えられた上に write されるといった一連の計
算であり、引数を一つ必要とする(*1)。
? 継続を関数形式で表現するとこうだ
(let ((square (lambda (x) (* x x))))
(write (+ (square 10) 1)))
(lambda (r) (write (+ r 1)))
(*1) ヤクチュウ。なにいっているかわからんだろう。
しかも忠実に訳していない。

CPS変換(4)
? 前のページで示した継続自身は square の計
算へ渡される必要があります。そのとき、
squareの結果は継続に送ることが出来るよう
にしておく必要があります。これが CPS (=
Continuation-Passing Style) です。
? 継続を引数として、その引数をすべてのラム
ダ式へと追加し、継続関数を渡すために関数
呼び出しを変更します。継続を使います、あ
る関数が結果を戻す必要があるときに。
(let ((square (lambda (k x) (k (* x x)))))
(square (lambda (r) (write (+ r 1)))
10))

CPS変換(5)
? 末尾呼び出しも簡単に表現できる、呼び出された関数へ今の継続を返す
ことで
? 例を挙げるよ
結果はこう
square の中の mult の呼び出しが末尾呼び出しなので、mult はsqaure と
して、同じ継続をとる。
(let ((mult (lambda (a b) (* a b))))
(let ((square (lambda (x) (mult x x))))
(write (+ (square 10) 1))))
(let ((mult (lambda (k a b) (k * a b)))))
(let ((sqauare (lambda (k x) (mult k x x))
(square (lambda ? (write (+ r 1)))
10)

CPS変換(6)
? CPS-変換はすべてのプログラムに体系的に
行われると結果としてつぎようになるよ
– すべての関数呼び出しは末尾呼び出しになる
– 末尾呼び出しではないものはクロージャーを一つ
作って、呼び出しの継続に備えるよ
? 関数呼び出しは単純に “jump” 命令に置き得
ることが可能だよ。

CPS 変換のルール(1)
? まずは表現方法(notation)を定義しよう
? これは E という Scheme 式をCPS 変換した結果の
Scheme の式。C の Scheme 式は E の継続を表す。
? E は元の式で(末尾からではない呼び出しを含むか
もしれない) C は CPS 形式の式(末尾呼び出ししか含
まない)になる。
? C は変数かあるいは lambda 式になる。
C
E

? 最初のルールはこうだ
? これは、プログラムの原始継続をr、プログラ
ムの結果を取得し、実行を終了プリミティブ操
作(% halt)を呼び出すことを言いますa
(a) 実際のコンパイラではその結果を表示することになるだろうね。
(lambda (r) (%halt r))Program
Program
=

c =
C
(C c)
v =
C
(C v)
(set! v E1)
=
C
E1
(lambda (r1)
(C (set! v r1)
(if E1 E2 E3)
=
C (lambda (r1)
(C r1 ))E2
C
E3
C
E1

CPS 変換のルール(4)～(6)
? 割愛(原文参照の事)

call/cc はどうよ？
? CPS では call/cc はシンプルに実現できる
? CPS 変換に call/cc が使われたときに CPS 変
換されたプログラムになるようにこの定義を
追加すればできあがりだ。
(define call/cc
(lambda (k f)
(f k (lambda (dummy-k result)
(k result)))))

Comiler Structure
? 800 行よりすくない Scheme
? 達成したこと
– forms に対してのパージングと展開
– CPS 変換
– クロージャー変換
– C コードの生成
? Runtime has
– ヒープ?セクション ( 今のところGCなし!!)
– グローバル変数のテーブル
– パラメータやローカル変数、プリミティブである式の評
価に使用される小さな目のスタック

Example

まとめ
? Powerful transformations
– CPS 変換
– クロージャ変換
? N性能はそんなに悪くはない。(Gambit-C でフ
ル最適化したものより 6倍)
? 改善のし甲斐がある…

狠狠撸

90分 Scheme to C(勝手に抄訳版)

More Related Content

90分 Scheme to C(勝手に抄訳版)