A non-deterministic call-by-need lambda calculus
- In this paper we present a non-deterministic call-by-need (untyped) lambda calculus lambda nd with a constant choice and a let-syntax that models sharing. Our main result is that lambda nd has the nice operational properties of the standard lambda calculus: confluence on sets of expressions, and normal order reduction is sufficient to reach head normal form. Using a strong contextual equivalence we show correctness of several program transformations. In particular of lambdalifting using deterministic maximal free expressions. These results show that lambda nd is a new and also natural combination of non-determinism and lambda-calculus, which has a lot of opportunities for parallel evaluation. An intended application of lambda nd is as a foundation for compiling lazy functional programming languages with I/O based on direct calls. The set of correct program transformations can be rigorously distinguished from non-correct ones. All program transformations are permitted with the slight exception that for transformations like common subexpression elimination and lambda-lifting with maximal free expressions the involved subexpressions have to be deterministic ones.
Verfasserangaben: | Arne Kutzner, Manfred Schmidt-SchaußORCiDGND |
---|---|
URN: | urn:nbn:de:hebis:30-19313 |
Titel des übergeordneten Werkes (Deutsch): | Proceedings of the third ACM SIGPLAN international conference on Functional programming, Baltimore, Maryland, United States |
Dokumentart: | Wissenschaftlicher Artikel |
Sprache: | Englisch |
Jahr der Fertigstellung: | 1998 |
Jahr der Erstveröffentlichung: | 1998 |
Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Datum der Freischaltung: | 18.10.2005 |
Seitenzahl: | 12 |
Erste Seite: | 324 |
Letzte Seite: | 335 |
Quelle: | Proceedings of the third ACM SIGPLAN international conference on Functional programming, Baltimore, Maryland, United States, pages: 324 - 335, http://portal.acm.org/citation.cfm?id=289462 |
HeBIS-PPN: | 225811863 |
Institute: | Informatik und Mathematik / Informatik |
DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Lizenz (Deutsch): | Deutsches Urheberrecht |