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).
  • http://lucacardelli.name/Papers/FAM.pdf

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
  • https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/compilingml.pdf

状態：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
  • https://caml.inria.fr/pub/papers/xleroy-zinc.pdf

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
  • Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine - Microsoft Research

CEK Machine

control, environment, continuation

• CEK Machine - Wikipedia

論文メモ

• 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
  • アキュムレーターは使わず、純粋にスタック（ローカル変数も含む）でやっているようだ。

Emacs Lisp

• GNU Emacs Lisp Bytecode Reference Manual
• [Home] Byte Code Engineering

CLISP

• Chapter 37. The CLISP bytecode specification