Extending abramsky's lazy lambda calculus: (Non)-conservativity of embeddings

Manfred Schmidt-Schauß, Elena MacHkasova, David Sabel

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Our motivation is the question whether the lazy lambda calculus, a pure lambda calculus with the leftmost outermost rewriting strategy, considered under observational semantics, or extensions thereof, are an adequate model for semantic equivalences in real-world purely functional programming languages, in particular for a pure core language of Haskell. We explore several extensions of the lazy lambda calculus: Addition of a seq-operator, addition of data constructors and case-expressions, and their combination, focusing on conservativity of these extensions. In addition to untyped calculi, we study their monomorphically and polymorphically typed versions. For most of the extensions we obtain non-conservativity which we prove by providing counterexamples. However, we prove conservativity of the extension by data constructors and case in the monomorphically typed scenario.

Original languageEnglish (US)
Title of host publication24th International Conference on Rewriting Techniques and Applications, RTA 2013
EditorsFemke van Raamsdonk
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages239-254
Number of pages16
ISBN (Electronic)9783939897538
ISBN (Print)9783939897538
DOIs
StatePublished - Jan 1 2013
Event24th International Conference on Rewriting Techniques and Applications, RTA 2013 - Eindhoven, Netherlands
Duration: Jun 24 2013Jun 26 2013

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume21
ISSN (Print)1868-8969

Conference

Conference24th International Conference on Rewriting Techniques and Applications, RTA 2013
Country/TerritoryNetherlands
CityEindhoven
Period6/24/136/26/13

Keywords

  • Conservativity
  • Contextual semantics
  • Lazy lambda calculus

Fingerprint

Dive into the research topics of 'Extending abramsky's lazy lambda calculus: (Non)-conservativity of embeddings'. Together they form a unique fingerprint.

Cite this