Open4
関数型言語向けの抽象機械
だめぽSECD機械
- P. J. Landin, The Mechanical Evaluation of Expressions, The Computer Journal, Volume 6, Issue 4, January 1964, Pages 308–320, https://doi.org/10.1093/comjnl/6.4.308
Modern SECD機械
D (dump)がない。環境の参照に名前ではなくde Bruijn indexを使う。
- https://pages.cpsc.ucalgary.ca/~robin/class/521/lectures_lambda/secd.pdf
- https://xavierleroy.org/mpri/2-4/machines.pdf
- A first look at SECD machines - depsterr.com
FAM (The Functional Abstract Machine)
- Cardelli, Luca. “The Functional Abstract Machine.” (1983).
The instructions of the machine are not supposed to be interpreted, but assembled into machine code and then executed.
とある。
- Luca Cardelli. 1984. Compiling a functional language. In Proceedings of the 1984 ACM Symposium on LISP and functional programming (LFP '84). Association for Computing Machinery, New York, NY, USA, 208–217. https://doi.org/10.1145/800055.802037
状態：Argument Pointer, Frame Pointer, Stack Pointer, Trap Pointer, Program Counter, Environment Pointer
クロージャーに関する操作：Closure, DumClosure, RecClosure, GetGlobal, GetLiteral, FunId, FunComp
関数呼び出し：SaveFrame, ApplFrame, RestFrame, TailApply
CAM (The Categorical Abstract Machine)
- G. Cousineau, P.-L. Curien, M. Mauny, The categorical abstract machine, Science of Computer Programming, Volume 8, Issue 2, 1987, Pages 173-202, ISSN 0167-6423, https://doi.org/10.1016/0167-6423(87)90020-7. (https://www.sciencedirect.com/science/article/pii/0167642387900207)
- Michel Mauny and Ascánder Suárez. 1986. Implementing functional languages in the Categorical Abstract Machine. In Proceedings of the 1986 ACM conference on LISP and functional programming (LFP '86). Association for Computing Machinery, New York, NY, USA, 266–278. https://doi.org/10.1145/319838.319869
状態：Term, Code, Stack
2要素版：Stack, Code
主な命令：fst, snd, push, swap, cons, app, cur (curry), quote
ZINC
Caml Lightを経てOCamlになるやつ。
カリー化と部分適用が効率的らしい。
- Xavier Leroy, The ZINC Experiment, an Economical Implementation of the ML Language, 1990
Spineless Tagless G-machine
非正格な言語向け。
GHCで使われていたやつ。なお今のGHCにはtagがあるほか、push/enterからeval/applyに代わっている。
- Peyton Jones , Simon L, Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine, Journal of Functional Programming | July 1992, Vol 2: pp. 127-202
CEK Machine
control, environment, continuation
だめぽ論文メモ
- Stephan Diehl, Pieter Hartel, Peter Sestoft, Abstract machines for programming language implementation, Future Generation Computer Systems, Volume 16, Issue 7,
2000, Pages 739-751, ISSN 0167-739X, https://doi.org/10.1016/S0167-739X(99)00088-6. (https://www.sciencedirect.com/science/article/pii/S0167739X99000886) - R. Kent Dybvig, Three Implementation Models for Scheme, 1987
- スタックベースのやつはChez Schemeの基礎になったらしい
- Ager, M. S., Biernacki, D., Danvy, O., & Midtgaard, J. (2003). From Interpreter to Compiler and Virtual Machine: A Functional Derivation. BRICS Report Series, 10(14). https://doi.org/10.7146/brics.v10i14.21784
だめぽ要件
ソース言語：Standard ML
- 末尾呼び出しの最適化（TCO）が必須
- 副作用（可変な参照セルと配列、例外）がある
- 評価順は左から右
- 複数引数はタプルで表現する；カリー化と部分適用はそこまで重要視しない
- LunarMLの拡張として、マルチショットな限定継続も実装したい
だめぽ各種処理系のVM
Gauche
-
VMのスタック操作 - Gauche - A Scheme Implementation
- アキュムレーター（値レジスタ
val0）を持っている。
- アキュムレーター（値レジスタ
Poly/ML
- polyml/IntCodeCons.ML at master · polyml/polyml
-
polyml/bytecode.h at master · polyml/polyml
- 状態：PC, stack
- アキュムレーターはなさそう
- stackは下（アドレスが小さい方）に向かって伸びる
- polyml/bytecode.cpp at master · polyml/polyml
- スタック先頭を保ったまま下の値をpopする命令がある（
INSTR_reset_r_*）
Chibi-Scheme
-
chibi-scheme/vm.c at master · ashinn/chibi-scheme
- アキュムレーターは使わず、純粋にスタック（ローカル変数も含む）でやっているようだ。