Abstract Machines

Abstract machines for functional programming languages

Overview

• Stephan Diehl, Pieter Hartel, Peter Sestoft (2000) Abstract machines for programming language implementation Link

Books

• Simon Peyton Jones (1987), The Implementation of Functional Programming Languages Link
• Simon Peyton Jones (1992), Implementing functional languages: A tutorial Link
• Werner Kluge (2004), Abstract Computing Machines: A Lambda Calculus Perspective Link

Other

• R.J.M. Hughes (1982), Super-combinators: A new implementation method for applicative languages Link

  The key to the new approach is to generalise the class of combinators [W.r.t David Turner's approach of compiling lambda expressions to SKI]. Recall that S, K, and I can be defined by lambda-expressions (...). These lambda-expressions have two special properties that make them suitable for use directly as operators in a graph reduction machine. Firstly, they have no free variables and so are "pure code", hence their internal structur is of no consequence and any suitable representation may be used for them. Secondly, their bodies are applicative forms, ie are composed from variables and constants by applications. ... Any lambda-expression with these two properties is a combinator (...) Where it is necessary to distinguish generalised combinators from Turner's, they are called super-combinators.

• R.J.M. Hughes (1982), Graph-Reduction with Super-Combinators Link

Strict languages

CEK/CESK

• Matt Might blog post Link
• dito Link

SECD Machine

• Landin (1964), The mechanical evaluation of expressions Link

Functional Abstract Machine (FAM)

• Luca Cardelli (1983), The functional abstract machine, Technical Report Link

• Luca Cardelli (1984), Compiling a functional language Link

Categorical Abstract Machine (CAM)

• Cousineau, Curien, Mauny (1985), The Categorical Abstract Machine Link

Zinc Abstract Machine

• Xavier Leroy (1990), The Zinc experiment: An economical implementation of the ML language Link

Lazy Languages

SK Machine

• David Turner (1979), A new implementation technique for applicative languages Link

G-Machine

• L. Augustsson (1984), A compiler for lazy ML Link
• T. Johnsson (1984), Efficient compilation of lazy evaluation Link

Krivine Machine

• Remi Douence, Pascal Fradet (2007), The next 700 Krivine machines Link
• Jean-Louis Krivine (2007), A call-by-name lambda-calculus machine Link

Three Instruction Machine (TIM)

• J. Fairbairn, S.C. Wray (1987), TIM: A simple lazy abstract machine to execute supercombinators Link
• G. Argo (1989), Improving the three instruction machine Link

Spineless Tagless G-Machine (STG)

• Simon Peyton Jones (1992), Implementing lazy functional languages on stock hardware, the spineless tagless G-Machine Link
• STGi Implementation on Hackage Link