Abstract
We describe lambda calculus reduction strategies, such as call-by-value, call-by-name, normal order, and applicative order, using big-step operational semantics. We show how to simply and efficiently trace such reductions, and use this in a web-based lambda calculus reducer available at <http://www.dina.kvl.dk/~sestoft/lamreduce/>.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abramsky, S., Ong, C.-H.L.: Full Abstraction in the Lazy λ-Calculus. Information and Computation 105, 2 (1993) 159–268.
Ariola, Z.M., Felleisen, M.: The Call-by-Need Lambda Calculus. Journal of Functional Programming 7, 3 (1997) 265–301.
Augustsson, L.: A Compiler for Lazy ML. In: 1984 ACM Symposium on Lisp and Functional Programming, Austin, Texas. ACM Press (1984) 218–227.
Barendregt, H.P.: The Lambda Calculus. Its Syntax and Semantics. North-Holland (1984).
Barendregt, H.P. et al.: Needed Reduction and Spine Strategies for the Lambda Calculus. Information and Computation 75 (1987) 191–231.
Church, A.: A Note on the Entscheidungsproblem. Journal of Symbolic Logic 1 (1936) 40–41, 101-102.
Engelfriet, J., Schmidt, E.M.: IO and OI. Journal of Computer and System Sciences 15 (1977) 328–353 and 16 (1978) 67-99.
Felleisen, M., Hieb, R.: The Revised Report on the Syntactic Theories of Sequential Control and State. Theoretical Computer Science 103, 2 (1992) 235–271.
Kahn, G.: Natural Semantics. In: STACS 87. 4th Annual Symposium on Theoretical Aspects of Computer Science, Passau, Germany. Lecture Notes in Computer Science, Vol. 247. Springer-Verlag (1987) 22–39.
Landin, P.J.: The Mechanical Evaluation of Expressions. Computer Journal 6, 4 (1964) 308–320.
Landin, P.J.: A Correspondence Between ALGOL 60 and Church’s Lambda-Notation: Part I. Communications of the ACM 8, 2 (1965) 89–101.
Landin, P.J.: The Next 700 Programming Languages. Communications of the ACM 9, 3 (1966) 157–166.
Launchbury, J.: A Natural Semantics for Lazy Evaluation. In: Twentieth ACM Symposium on Principles of Programming Languages, Charleston, South Carolina, January 1993. ACM Press (1993) 144–154.
Milner, R., Tofte, M., Harper, R., MacQueen, D.B.: The Definition of Standard ML (Revised). The MIT Press (1997).
Paulson, L.C.: ML for the Working Programmer. Second edition. Cambridge University Press (1996).
Peyton Jones, S.L.: The Implementation of Functional Programming Languages. Prentice-Hall (1987).
Peyton Jones, S.L., Hughes, J. (eds.): Haskell 98: A Non-Strict, Purely Functional Language. At <http://www.haskell.org/onlinereport/>.
Plotkin, G.: Call-by-Name, Call-by-Value and the λ-Calculus. Theoretical Computer Science 1 (1975) 125–159.
Sestoft, P.: Deriving a Lazy Abstract Machine. Journal of Functional Programming 7,3 (1997) 231–264.
Stoy, J.E.: The Scott-Strachey Approach to Programming Language Theory. The MIT Press (1977).
Turner, D.A.: A New Implementation Technique for Applicative Languages. Software-Practice and Experience 9 (1979) 31–49.
Wadsworth, C.P.: Semantics and Pragmatics of the Lambda Calculus. D.Phil. thesis, Oxford University, September 1971.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Sestoft, P. (2002). Demonstrating Lambda Calculus Reduction. In: Mogensen, T.Æ., Schmidt, D.A., Sudborough, I.H. (eds) The Essence of Computation. Lecture Notes in Computer Science, vol 2566. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36377-7_19
Download citation
DOI: https://doi.org/10.1007/3-540-36377-7_19
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00326-7
Online ISBN: 978-3-540-36377-4
eBook Packages: Springer Book Archive