[PDF][PDF] From interpreter to compiler and virtual machine: a functional derivation

MS Ager, D Biernacki, O Danvy, J Midtgaard - BRICS Report Series, 2003 - tidsskrift.dk
BRICS Report Series, 2003tidsskrift.dk
We show how to derive a compiler and a virtual machine from a compositional interpreter.
We first illustrate the derivation with two evaluation functions and two normalization
functions. We obtain Krivine's machine, Felleisen et al.'s CEK machine, and a generalization
of these machines performing strong normalization, which is new. We observe that several
existing compilers and virtual machines—eg, the Categorical Abstract Machine (CAM),
Schmidt's VEC machine, and Leroy's Zinc abstract machine—are already in derived form …
Abstract
We show how to derive a compiler and a virtual machine from a compositional interpreter. We first illustrate the derivation with two evaluation functions and two normalization functions. We obtain Krivine’s machine, Felleisen et al.’s CEK machine, and a generalization of these machines performing strong normalization, which is new. We observe that several existing compilers and virtual machines—eg, the Categorical Abstract Machine (CAM), Schmidt’s VEC machine, and Leroy’s Zinc abstract machine—are already in derived form and we present the corresponding interpreter for the CAM and the VEC machine. We also consider Hannan and Miller’s CLS machine and Landin’s SECD machine. We derived Krivine’s machine via a call-by-name CPS transformation and the CEK machine via a call-by-value CPS transformation. These two derivations hold both for an evaluation function and for a normalization function. They provide a non-trivial illustration of Reynolds’s warning about the evaluation order of a meta-language.
tidsskrift.dk
以上显示的是最相近的搜索结果。 查看全部搜索结果