A Rational Deconstruction of Landin’s SECD Machine
- Olivier DanvyAffiliated withBRICS Department of Computer Science, University of Aarhus, IT-parken
Landin’s SECD machine was the first abstract machine for the λ-calculus viewed as a programming language. Both theoretically as a model of computation and practically as an idealized implementation, it has set the tone for the subsequent development of abstract machines for functional programming languages. However, and even though variants of the SECD machine have been presented, derived, and invented, the precise rationale for its architecture and modus operandi has remained elusive. In this article, we deconstruct the SECD machine into a λ-interpreter, i.e., an evaluation function, and we reconstruct λ-interpreters into a variety of SECD-like machines. The deconstruction and reconstructions are transformational: they are based on equational reasoning and on a combination of simple program transformations—mainly closure conversion, transformation into continuation-passing style, and defunctionalization.
The evaluation function underlying the SECD machine provides a precise rationale for its architecture: it is an environment-based eval-apply evaluator with a callee-save strategy for the environment, a data stack of intermediate results, and a control delimiter. Each of the components of the SECD machine (stack, environment, control, and dump) is therefore rationalized and so are its transitions.
The deconstruction and reconstruction method also applies to other abstract machines and other evaluation functions.
- A Rational Deconstruction of Landin’s SECD Machine
- Book Title
- Implementation and Application of Functional Languages
- Book Subtitle
- 16th International Workshop, IFL 2004, Lübeck, Germany, September 8-10, 2004 Revised Selected Papers
- pp 52-71
- Print ISBN
- Online ISBN
- Series Title
- Lecture Notes in Computer Science
- Series Volume
- Series ISSN
- Springer Berlin Heidelberg
- Copyright Holder
- Springer-Verlag Berlin Heidelberg
- Additional Links
- Industry Sectors
- Editor Affiliations
- 16. University of Lübeck
- 17. Institute of Computer Science, University of Kiel
- 18. Dept. of Mathematics and Computer Science, Heriot-Watt University
- 19. School of Mathematical and Computer Sciences, Heriot-Watt University
- Olivier Danvy (20)
- Author Affiliations
- 20. BRICS Department of Computer Science, University of Aarhus, IT-parken, Aabogade 34, DK-8200, Aarhus N, Denmark
To view the rest of this content please follow the download PDF link above.