Abstract
We express implementations of functional languages as a succession of program transformations in a common framework. At each step, different transformations model fundamental choices or optimizations. A benefit of this approach is to structure and decompose the implementation process. The correctness proofs can be tackled independently for each step and amount to proving program transformations in the functional world. It also paves the way to formal comparisons by estimating the complexity of individual transformations or compositions of them. We focus on call-by-value implementations, describe and compare the diverse alternatives and classify well-known abstract machines. This work also aims to open the design space of functional language implementations and we suggest how distinct choices could be mixed to yield efficient hybrid abstract machines.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
A. W. Appel. Compiling with Continuations. Cambridge University Press. 1992.
A. Asperti. A categorical understanding of environment machines. Journal of Functional Programming, 2(1), pp.23–59,1992.
G. Argo. Improving the three instruction machine. In Proc. of FPCA'89, pp. 100–115, 1989.
G. Burn, S.L. Peyton Jones and J.D. Robson. The spineless G-machine. In Proc. of LFP'88, pp. 244–258, 1988.
G. Burn and D. Le Métayer. Proving the correctness of compiler optimisations based on a global analysis. Journal of Functional Programming, 1995. (to appear).
L. Cardelli. Compiling a functional language. In Proc. of LFP'84, pp. 208–217, 1984.
G. Cousineau, P.-L. Curien and M. Mauny, The categorical abstract machine. Science of Computer Programming, 8(2), pp. 173–202, 1987.
P. Crégut. Machines à environnement pour la réduction symbolique et l'évaluation partielle. Thèse de l'université de Paris VII, 1991.
R. Douence and P. Fradet. A taxonomy of functional language implementations. Part I: Call-by-Value, INRIA Research Report, 1995. (to appear)
J. Fairbairn and S. Wray. Tim: a simple, lazy abstract machine to execute supercombinators. In Proc of FPCA'87, LNCS 274, pp. 34–45, 1987.
M. J. Fischer. Lambda-calculus schemata. In Proc. of the ACM Conf. on Proving Properties about Programs, Sigplan Notices, Vol. 7(1), pp. 104–109, 1972.
P. Fradet and D. Le Métayer. Compilation of functional languages by program transformation. ACM Trans. on Prog. Lang. and Sys., 13(1), pp. 21–51, 1991.
J. Hannan. From operational semantics to abstract machines. Math. Struct. in Comp. Sci., 2(4), pp. 415–459, 1992.
J. Hatcliff and O. Danvy. A generic account of continuation-passing styles. In Proc. of POPL'94, pp. 458–471, 1994.
T. Johnsson. Compiling Lazy Functional Languages. PhD Thesis, Chalmers University, 1987.
M. S. Joy, V. J. Rayward-Smith and F. W. Burton. Efficient combinator code. Computer Languages, 10(3), 1985.
D. Kranz, R. Kesley, J. Rees, P. Hudak, J. Philbin, and N. Adams. ORBIT: An optimizing compiler for Scheme. SIGPLAN Notices, 21(7), pp.219–233, 1986.
P. J. Landin. The mechanical evaluation of expressions. The Computer Journal, 6(4), pp.308–320, 1964.
X. Leroy. The Zinc experiment: an economical implementation of the ML language. INRIA Technical Report 117, 1990.
R. D. Lins. Categorical multi-combinators. In Proc. of FPCA'87, LNCS 274, pp. 60–79, 1987.
R. Lins, S. Thompson and S.L. Peyton Jones. On the equivalence between CMC and TIM. Journal of Functional Programming, 4(1), pp. 47–63, 1992.
E. Meijer and R. Paterson. Down with lambda lifting. copies available at: erik@cs.kun.nl, 1991.
E. Moggi. Notions of computation and monads. Information and Computation, 93:55–92, 1991.
S.L. Peyton Jones. Implementing lazy functional languages on stock hardware: the spineless tagless G-machine. Journal of Functional Programming, 2(2):127–202, 1992.
S. L. Peyton Jones and D. Lester. Implementing functional languages, a tutorial. Prentice Hall, 1992.
S. L. Peyton Jones and J. Launchbury. Unboxed values as first class citizens in a non-strict functional language. In Proc. of FPCA'91, LNCS 523, pp.636–666, 1991.
P. Sestoft. Deriving a lazy abstract machine. Technical Report 1994-146, Technical University of Denmark, 1994.
Z. Shao and A. Appel. Space-efficient closure representations. In Proc. of LFP'94, pp. 150–161,1994.
D.A. Turner. A new implementation technique for applicative languages. Soft. Pract. and Exper., 9, pp. 31–49, 1979.
M. Wand. Deriving target code as a representation of continuation semantics. ACM Trans. on Prog. Lang. and Sys., 4(3), pp. 496–517, 1982.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Douence, R., Fradet, P. (1995). Towards a taxonomy of functional language implementations. In: Hermenegildo, M., Swierstra, S.D. (eds) Programming Languages: Implementations, Logics and Programs. PLILP 1995. Lecture Notes in Computer Science, vol 982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0026812
Download citation
DOI: https://doi.org/10.1007/BFb0026812
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60359-7
Online ISBN: 978-3-540-45048-1
eBook Packages: Springer Book Archive