Hostname: page-component-745bb68f8f-f46jp Total loading time: 0 Render date: 2025-01-11T20:37:31.810Z Has data issue: false hasContentIssue false
  • English
  • Français

The lambda calculus is algebraic

Published online by Cambridge University Press:  06 November 2002

PETER SELINGER
PETER SELINGER
Affiliation:
Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario K1N 6N5, Canada (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper serves as a self-contained, tutorial introduction to combinatory models of the untyped lambda calculus. We focus particularly on the interpretation of free variables. We argue that free variables should not be interpreted as elements in a model, as is usually done, but as indeterminates. We claim that the resulting interpretation is more natural and leads to a closer correspondence between models and theories. In particular, it solves the problem of the notorious ζ-rule, which asserts that equations should be preserved under binders, and which fails to be sound for the usual interpretation.

Type
Research Article
Information
Journal of Functional Programming , Volume 12 , Issue 6 , November 2002 , pp. 549 - 566
Copyright
© 2002 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.