![SECDマシンの概要: 基本
●
ラムダ計算を評価?実行するための抽象機械
– つまり純粋関数型言語のための抽象機械
●
Peter Landinによる論文[3]で提唱された
– 命令一覧が載ってないくらいには抽象的
●
具体的な命令はLispKit Lispの実装が有名
– Peter Hendersonによる
– ググるとでてくる具体的な命令はだいたいこ
れが元](https://image.slidesharecdn.com/2020-10-29-secd-machine-201029120601/85/SECD-5-320.jpg)
![参考文献
●
[1] SECDマシンとLispあれこれ - Arantium
Maestum
– https://zehnpaard.hatenablog.com/entry/
2018/12/23/075158
●
[2] SECD machine – Wikipedia
– https://en.wikipedia.org/wiki/SECD_machi
ne
●
[3] Peter Landin, The Mechanical
Evaluation of Expression
●
[4] Miloˇs Radovanovi, Mirjana Ivanovi, An
Implementation of LispKit Lisp in Java](https://image.slidesharecdn.com/2020-10-29-secd-machine-201029120601/85/SECD-45-320.jpg)
More Related Content
What's hot (20)
More from t-sin (10)
SECDマシン 実装と動きとその他もろもろについて
- 2. おことわり ● SECDマシンの上にLispKit Lispを実装した Peter Hendersonの本の内容は出てきませ ん – “Functional Programming Application and Implementation” – 先日届いたけどまだ読めてないので… – 目次には並列化や手続き型プログラムからの変換など のトピックがあった ● 純Lispにコンパイルする話はありません ● 予告していた継続の話もありません
- 5. SECDマシンの概要: 基本 ● ラムダ計算を評価?実行するための抽象機械 – つまり純粋関数型言語のための抽象機械 ● Peter Landinによる論文[3]で提唱された – 命令一覧が載ってないくらいには抽象的 ● 具体的な命令はLispKit Lispの実装が有名 – Peter Hendersonによる – ググるとでてくる具体的な命令はだいたいこ れが元
- 6. SECDマシンの概要: 特徴 ● スタックマシン – 4つのレジスタにスタックを保持する ● レキシカルスコープをもつ ● 第一級の関数オブジェクト ● 関数は引数を1個のみ取る – カリー化されている – 複数の引数は関数呼び出しの入れ子で表現する ● コアの機能は命令でいうと8個ほど
- 7. SECDマシンの概要: 詳細 ● スタックマシン – 引数等のデータの一時保管場所がスタックな もの – レジスタマシンは一時保管場所がレジスタな もの ● 4つのスタックをもつ – Stack: データスタック – Environment: 引数の束縛 – Controll: 未実行の命令のリスト – Dump: 関数適用や分岐時のデータ退避場所
- 8. SECDマシンの概要: 動作 ● プログラムをControllスタックに読み込む ● 以下を繰り返す – Controllスタックが空なら終了 – Controllスタックから命令をポップ – 命令に対応した処理を実行 ● これによりS, E, C, Dの値が変化する
- 10. SECDマシンの詳細: スタック ● Stack (データスタック) – 命令や関数への引数のやりとりに用いる ● Environment (環境) – 関数適用の実引数を積む場所 – 数字(添字)を使ってアクセスする ● Controll (制御) – 次に実行する命令列 – 木構造をしている(コンスセルでできている) – プログラムカウンタに対応する ● Dump – 関数適用や条件分岐の終了時に戻ってくる先を保持 – じつは継続(この話はまたいつか)
- 11. SECDマシンの詳細: 命令一覧 ● ロード系命令 – ld, ldc, ldf ● 制御系命令 – ap, rtn, dum, rap sel, join ● コンスセル系命令 – cons, car, cdr ● 述語系命令 – eq, atom ● 数値演算?比較系命令 – add, sub, mul, div, rem, leq
- 12. SECDマシンの詳細: 命令 (1) ● ロード系命令 – ld, ldc, ldf ● 制御系命令 – ap, rtn, dum, rap sel, join ● コンスセル系命令 – cons, car, cdr ● 述語系命令 – eq, atom ● 数値演算?比較系命令 – add, sub, mul, div, rem, leq 環境から 値をロード 定数を ロード 関数を ロード
- 13. SECDマシンの詳細: 命令 (2) ● ロード系命令 – ld, ldc, ldf ● 制御系命令 – ap, rtn, dum, rap, – sel, join ● コンスセル系命令 – cons, car, cdr ● 述語系命令 – eq, atom ● 数値演算?比較系命令 – add, sub, mul, div, rem, leq 関数適用 (再帰呼び出し) 関数適用 関数を抜ける ダミー値を 環境に入れる 条件分岐 条件分岐を 抜ける
- 14. SECDマシンの詳細: 命令 (3) ● ロード系命令 – ld, ldc, ldf ● 制御系命令 – ap, rtn, dum, rap sel, join ● コンスセル系命令 – cons, car, cdr ● 述語系命令 – eq, atom ● 数値演算?比較系命令 – add, sub, mul, div, rem, leq コンスセル つくる car部を取る cdr部を取る オブジェクト 同値性！ アトムか否か +, -, *, /, %, <=
- 15. SECDマシンの詳細: 命令 ● ロード系命令 – ld, ldc, ldf ● 制御系命令 – ap, rtn, dum, rap, sel, join ● コンスセル系命令 – cons, car, cdr ● 述語系命令 – eq, atom ● 数値演算?比較系命令 – add, sub, mul, div, rem, leq これらの命令が SECDマシンを 理解する上で重要
- 16. SECDマシンの詳細: ロード命令 ● ld (load) – 環境から値をロードする – 1つの定数を引数に取る – 環境(Eスタック)のn番目の値をSスタックにpush ● ldc (load constant) – 引数の定数をSスタックにpush ● ldf (load function) – 引数に機械語コードを取る – 引数のコードをSスタックにpush – このとき実行時の環境をコピーしてコードと一緒に push ● これがレキシカルな束縛となる
- 17. SECDマシンの詳細: 制御命令 ● ap (apply) – 関数適用するための命令 – やることは3つ ● 現在の実行状態の退避(戻り先の保持) ● 新しい環境を作って引数をpush – カリー化されているので引数は1つだけであ る点に注意 ● 関数本体に入る準備(環境とコードを変更) ● rtn (return) – 関数本体の処理から抜ける命令 – apで退避した実行状態を復元し、 関数適用の次の処理を開始できるようにする
- 18. SECDマシンの詳細: 制御命令 ● dum (dummy) – 環境のトップにダミー値を設定する – これはrapで書き換えるためのプレースホルダ – ldfの前(レキシカル環境を作る前)にdumする必要がある ● rap (recursive apply) – 再帰的に関数適用するための命令 – (dum)(ldf …) のように作られた関数に対して用いる – apとの違いは ● 「新しい環境を作って引数をpush」するのではなく ● 「関数のレキシカル環境の先頭(ダミー値)を引数で上書き」する ● 以降の再帰呼び出しでもrapの引数は環境に置かれる ＝参照できる ● rapの引数を関数にするとその関数を無限に呼べる！
- 19. SECDマシンの詳細: 制御命令 ● sel (select) – 条件分岐を行う命令 – コードを2つ引数に取る(true節とfalse節) – やることは2つ ● 実行状態(EとC)をDにバックアップ ● Sのトップの値によりCに設定するコードを変える ● join (join) – 分岐の後始末をする命令 – selの各節の最後に必ず置く – Dにバックアップした実行状態(EとC)を元に戻す
- 21. SECDマシンの実装: サンプル ● 勉強のため実装を用意してみた – https://github.com/t-sin/secdm – Common Lisp製 – 2年前に実装してたPython製のやつあるのでそち らも参考に ● python-implementation タグ
- 22. SECDマシンの実装: 概要(1) ● VMの表現を考える ● VMが扱うデータの種類も考える ● VMのマシン語の表現を考える – バイト型の配列？ – Lispのリスト？ ● VMの実行の流れを考える – プログラムはどこからくる？ – データはどこからくる？
- 23. SECDマシンの実装: 概要(2) ● VMの表現 – S,E,C,Dのフィールドがある構造体 ● VMが扱うデータの種類 – シンボル、整数、コンスセル ● VMのマシン語の表現 – リストで表現 – 1個の命令もまたリスト(例は後ほど) – 分岐等はリストのネストで表現 ● VMの実行の流れを考える – プログラムは基本的にCスタックのトップから – データはSスタックからか命令の引数
- 24. SECDマシンの実装: 入力(1) ● 入力はCommon Lispリーダに任せて 以下のようなS式とする ● 木構造をしている点に注意 ; test1 (ldc 42) (ldc 1) (cons) (car) (ldf ((ldc 100) (ldc 200) (rtn))) (ap) (dum) (ldc "> ") (print) (input) (println) (stop)
- 25. SECDマシンの実装: 入力(2) ● 入力はCommon Lispリーダに任せて 以下のようなS式とする ● 木構造をしている点に注意 ; test1 (ldc 42) (ldc 1) (cons) (car) (ldf ((ldc 100) (ldc 200) (rtn))) (ap) (dum) (ldc "> ") (print) (input) (println) (stop)
- 26. SECDマシンの実装: 入力(3) ● 分岐と再帰をやっているコード例 ● Python版とCL版で入出力命令の有無とかあ るので注意 ;; printlnなどのせいでPython版でだけ動くコード (dum) (ldc 0) (ldf ((ld 0) (cdr) (ldc 10) (eq) (sel ((ldc "stop counting up.") (println) (join)) ((ld 0) (cdr) (println) (ld 0) (cdr) (ldc 1) (add) (ld 0) (car) (cons) (ld 0) (car) (ap) (join))) (rtn))) (cons) (ldf ((ld 0) (ld 0) (car) (rap) (rtn))) (ap) (stop)
- 27. SECDマシンの実装: VM ● まずはS,E,C,Dのスタックを格納する構造体を 用意 ● 構造体のスロットのデフォルト値はnil (空) – ここにpush/pop関数で値を出し入れしていく ● デバッグする用のスロットもいくつか用意 ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defstruct (vm (:constructor make-vm*)) (debug-p nil) (step-p nil) (running-p t) s e c d)
- 28. SECDマシンの実装: 命令の実行 ● 命令をCスタックから1個取って実行 ● 命令はシンボルに関数としてセットしておく 設計にした ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defun run-1 (vm) (when (vm-debug-p vm) ; デバッグ出力 (print-vm vm)) (when (null (vm-c vm)) ; コードがなくなったら抜ける (return-from run-1 nil)) (let ((op (pop (vm-c vm)))) ; 命令をCスタックから取り出す (assert (listp op)) (let ((name (car op)) ; 名前と引数を取り出す (args (cdr op))) (assert (symbolp name)) (apply name vm args) ; 名前のシンボルに対応する命令を実行 (if (vm-running-p vm) t nil)))) ここが本体
- 29. SECDマシンの実装: 命令の定義(1) ● 命令をどうやって定義しよう？ ● こんな感じで定義したいな… – nil: nilをスタックにプッシュする – ldc: 定数をスタックにプッシュする (defop nil (vm) "Load nil to S register." (push nil (vm-s vm))) (defop ldc (vm n) "Load a constant to S register." (push n (vm-s vm)))
- 30. SECDマシンの実装: 命令の定義(2) ● 命令はリスト ● 名前(0番目)と引数(1番目以降)を持つ – 引数は値(定数)やコード(分岐など)を埋め込むとき用 ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defpackage #:secdm.op ; 命令のシンボルだけを入れる名前空間 (:use)) (defpackage #:secdm.symbol ; 命令以外のシンボルを入れる名前空間 (:use #:secdm.op)) ;; 命令を定義するためのマクロ (defmacro defop (name (&rest args) doc &body body) (let ((fn-name (intern (symbol-name name) :secdm.op))) `(progn (defun ,fn-name ,args ,doc ,@body) (export ',fn-name :secdm.op))))
- 31. SECDマシンの実装: 関数(1) ● 関数とはなにか – 処理本体のマシン語 – 定義位置での束縛(レキシカルな束縛) ● VMが扱えるデータで、 他のデータと区別が付けばよい ● ldf (load function) – 引数に機械語コードを取る – 引数のコードをSスタックにpush – このとき実行時の環境をコピーしてコードと一緒に push ● これがレキシカルな束縛となる
- 32. SECDマシンの実装: 関数(2) ● 関数とはなにか – 処理本体のマシン語 – 定義位置での束縛(レキシカルな束縛) ● VMが扱えるデータで、 他のデータと区別が付けばよい →じゃあリストでいいや！！！！！ ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defop ldf (vm code) "Load a function to S register." (let ((f (list :fn :code code :env (vm-e vm)))) (push f (vm-s vm))))
- 33. SECDマシンの実装: 関数(3) ● 関数呼び出しとはなにか – 実行コンテキスト(Sスタックや環境、コード)の切り替え ● 現在のコンテキスト退避 ● 引数を入れる環境の用意 ● Cスタック(プログラム)の切り替え – 実行が終わったら元のコンテキストに戻す ● return文的な ● ap (apply) – 関数適用するための命令 – やることは3つ ● 現在の実行状態の退避(戻り先の保持) ● 新しい環境を作って引数をpush – カリー化されているので引数は1つだけである点に注意 ● 関数本体に入る準備(環境とコードを変更) ● rtn (return) – 関数本体の処理から抜ける命令 – apで退避した実行状態を復元し、 関数適用の次の処理を開始できるようにする
- 34. SECDマシンの実装: 関数(4) ● 実行コンテキスト(Sスタックや環境、コード)の切り替え – 現在のコンテキスト退避(Dスタックに入れる) – 引数を入れる環境の用意 – Cスタック(プログラム)の切り替え ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defop ap (vm) "Apply a function to a value on top of S register." (let ((f (pop (vm-s vm))) (v (pop (vm-s vm)))) (assert (eq (car f) :fn)) (let ((dump (list :s (vm-s vm) :e (vm-e vm) :c (vm-c vm))) (env (append (list v) (vm-e vm)))) (setf (vm-s vm) nil (vm-e vm) env (vm-c vm) (getf (cdr f) :code)) (push dump (vm-d vm)))))
- 35. SECDマシンの実装: 関数(5) – 実行が終わったら元のコンテキストに戻す ● Dスタックのトップの内容から呼び出し前を復元 ● 関数の返り値をSスタックに入れておく ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defop rtn (vm) "Exit from function evaluation and return a value on the top of S stack." (let ((v (pop (vm-s vm))) (dump (pop (vm-d vm)))) (setf (vm-s vm) (append (list v) (getf dump :s)) (vm-e vm) (getf dump :e) (vm-c vm) (getf dump :c))))
- 36. SECDマシンの実装: 再帰する(1) ● やりかた – dumを実行して環境にプレースホルダを置く – 関数を引数に取る関数を定義する(1つめのldf) – 再帰のスタート用関数を定義する(2つめのldf) ● 本体では、引数にきた関数をrapする ● こうすると1つめの関数がずっと環境に残る(dumしたところ) ;; https://github.com/t-sin/secdm/blob/master/program/loop.l (dum) (ldc 0) (ldf ((ld 0) (cdr) (ldc 10) (eq) (sel ((ldc "stop counting up.") (println) (join)) ((ld 0) (cdr) (println) (ld 0) (cdr) (ldc 1) (add) (ld 0) (car) (cons) (ld 0) (car) (ap) (join))) (rtn))) (cons) (ldf ((ld 0) (ld 0) (car) (rap) (rtn))) (ap) (stop)
- 37. SECDマシンの詳細: 再帰する(2) ● dum (dummy) – 環境のトップにダミー値を設定する – これはrapで書き換えるためのプレースホルダ – ldfの前(レキシカル環境を作る前)にdumする必要がある ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defop dum (vm) "Load a dummy value to current enviroment. This dummy value :omega will be replaced by `rap` operator." (push :omega (vm-e vm)))
- 38. SECDマシンの詳細: 再帰する(3) ● rap (recursive apply) – apとの違いは ● 「新しい環境を作って引数をpush」するのではなく ● 「関数のレキシカル環境の先頭(ダミー値)を引数で上書き」する ● 以降の再帰呼び出しでもrapの引数は環境に置かれる ＝参照できる ● rapの引数を関数にするとその関数を無限に呼べる！ ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defop rap (vm) (let ((f (pop (vm-s vm))) (v (pop (vm-s vm)))) (assert (eq (car f) :fn)) (let ((dump (list :s (vm-s vm) :e (cdr (vm-e vm)) ; :omegaは除く :c (vm-c vm))) (env (getf (cdr f) :env))) (rplaca env v) ; car部を変更するCLの関数で:omegaを引数に変更 (setf (vm-s vm) nil (vm-e vm) env (vm-c vm) (getf (cdr f) :code)) (push dump (vm-d vm)))))
- 39. SECDマシンの実装: 分岐する(1) ● 分岐とは – Sスタックの値により次に実行するコードを切り替えること – 真と偽のときのコードは命令の引数で指定する – つまり、以下のsel命令みたいになる – もちろん、分岐の終了時に元のコンテキストに戻す必要あり ;; https://github.com/t-sin/secdm/blob/master/program/loop.l (dum) (ldc 0) (ldf ((ld 0) (cdr) (ldc 10) (eq) (sel ((ldc "stop counting up.") (println) (join)) ((ld 0) (cdr) (println) (ld 0) (cdr) (ldc 1) (add) (ld 0) (car) (cons) (ld 0) (car) (ap) (join))) (rtn))) (cons) (ldf ((ld 0) (ld 0) (car) (rap) (rtn))) (ap) (stop)
- 40. SECDマシンの実装: 分岐する(2) ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defop sel (vm true false) (let ((v (pop (vm-s vm))) (dump (list :s nil :e nil :c (vm-c vm)))) (push dump (vm-d vm)) (setf (vm-c vm) (if v true false)))) ● sel (select) – 条件分岐を行う命令 – コードを2つ引数に取る(true節とfalse節) – やることは2つ ● 実行状態(EとC)をDにバックアップ ● Sのトップの値によりCに設定するコードを変える
- 41. SECDマシンの実装: 分岐する(3) ;; https://github.com/t-sin/secdm/blob/master/vm.lisp (defop join (vm) "Terminate branching. True/False causes for `sel` should ends with this operator." (let ((dump (pop (vm-d vm)))) (setf (vm-c vm) (getf dump :c)))) ● join (join) – 分岐の後始末をする命令 – selの各節の最後に必ず置く – Dにバックアップした実行状態(EとC)を元に戻す
- 43. まとめ ● SECDマシンはラムダ計算を実行する抽象機械 – Stack?Environment?Controll?Dump！ ● Peter HendersonがLispKit Lispを実装す る際に具体化した ● レキシカルスコープと1引数の関数をもつ ● 再帰もできるよ！
- 44. 今後の話 ● 実際に純LispをSECDマシン語にコンパイル してみる話 – 準備中(コンパイラ実装中) ● SECDのDが継続である話 – Dump用命令dump/restoreを実装し制御フロー の実現？ ● 副作用や並列化を実現する話？ – Peter Henderson本の目次にある
- 45. 参考文献 ● [1] SECDマシンとLispあれこれ - Arantium Maestum – https://zehnpaard.hatenablog.com/entry/ 2018/12/23/075158 ● [2] SECD machine – Wikipedia – https://en.wikipedia.org/wiki/SECD_machi ne ● [3] Peter Landin, The Mechanical Evaluation of Expression ● [4] Miloˇs Radovanovi, Mirjana Ivanovi, An Implementation of LispKit Lisp in Java