×

zbMATH — the first resource for mathematics

Deforestation: Transforming programs to eliminate trees. (English) Zbl 0701.68013
Summary: An algorithm that transforms programs to eliminate intermediate trees is presented. The algorithm applies to any term containing only functions with definitions in a given syntactic form, and is suitable for incorporation in an optimizing compiler.

MSC:
68N01 General topics in the theory of software
68W10 Parallel algorithms in computer science
68N20 Theory of compilers and interpreters
Software:
Miranda; ML
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Augustsson, L., Compiling pattern matching, ()
[2] Augustsson, L.; Johnsson, T., The chalmers lazy ML compiler, Comput. J., 32, 2, 127-141, (1989)
[3] Burstall, R.M.; Darlington, J., A transformation system for developing recursive programs, J. ACM, 24, 1, 44-67, (1977) · Zbl 0343.68014
[4] Davis, M.K., Deforestation: transformation of functional programs to eliminate intermediate trees, ()
[5] Damas, L.; Milner, R., Principal type schemes for functional programs, Proc. ACM symp. on principles of programming languages, (1982)
[6] Ferguson, A.B.; Wadler, P.L., When will deforestation stop?, ()
[7] Goguen, J.A., Higher order functions considered unnecessary for higher order programming, ()
[8] Hindley, R., The principal type scheme of an object in combinatory logic, Trans. amer. math. soc., 146, 29-60, (1979) · Zbl 0196.01501
[9] Milner, R., A theory of type polymorphism in programming, J. comput. system sci., 17, 348-375, (1978) · Zbl 0388.68003
[10] Peyton Jones, S.L., The implementation of functional programming languages, (1987), Prentice Hall Englewood Cliffs, NJ · Zbl 0712.68017
[11] Turchin, V.F.; Nirenberg, R.M.; Turchin, D.V., Experiments with a supercompiler, Pittsburgh, PA, Proc. ACM symp. on lisp and functional programming, (1982)
[12] Wadler, P.L., Listlessness is better than laziness: lazy evaluation and garbage collection at compile time, Austin, TX, Proc. ACM symp. on lisp and functional programming, (1984)
[13] Wadler, P.L., Listlessness is better than laziness II: composing listless functions, (), Copenhagen · Zbl 0596.68016
[14] Wadler, P.L., Efficient compilation of pattern-matching, ()
[15] Wadler, P.L., The concatenate vanishes, (1987), Note distributed to FP electronic mailing list
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.