TY - GEN
T1 - Extending abramsky's lazy lambda calculus
T2 - 24th International Conference on Rewriting Techniques and Applications, RTA 2013
AU - Schmidt-Schauß, Manfred
AU - MacHkasova, Elena
AU - Sabel, David
PY - 2013/1/1
Y1 - 2013/1/1
N2 - 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.
AB - 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.
KW - Conservativity
KW - Contextual semantics
KW - Lazy lambda calculus
UR - http://www.scopus.com/inward/record.url?scp=84889591977&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84889591977&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.RTA.2013.239
DO - 10.4230/LIPIcs.RTA.2013.239
M3 - Conference contribution
AN - SCOPUS:84889591977
SN - 9783939897538
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 239
EP - 254
BT - 24th International Conference on Rewriting Techniques and Applications, RTA 2013
A2 - van Raamsdonk, Femke
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 24 June 2013 through 26 June 2013
ER -