ICFP 2022 Paper: The Theory of Call-by-Value Solvability

by Beniamino Accattoli (INRIA) and Giulio Guerrieri (Huawei Edinburgh, PL team) Giulio Guerrieri

The denotational semantics of the untyped lambda-calculus is a well developed field built around the concept of solvable terms, which are elegantly characterized in many different ways. In particular, unsolvable terms provide a consistent notion of meaningless term. The semantics of the untyped call-by-value lambda-calculus is instead still in its infancy, because of some inherent difficulties but also because call-by-value solvable terms are less studied and understood than in call-by-name. On the one hand, we show that a carefully crafted presentation of call-by-value allows us to recover many of the properties that solvability has in call-by-name, in particular qualitative and quantitative characterizations via multi types. On the other hand, we stress that, in call-by-value, solvability plays a different role: identifying unsolvable terms as meaningless induces an inconsistent theory.

Paper: https://doi.org/10.1145/3547652 


Report this page

To report inappropriate content on this page, please use the form below. Upon receiving your report, we will be in touch as per the Take Down Policy of the service.

Please note that personal data collected through this form is used and stored for the purposes of processing this report and communication with you.

If you are unable to report a concern about content via this form please contact the Service Owner.

Please enter an email address you wish to be contacted on. Please describe the unacceptable content in sufficient detail to allow us to locate it, and why you consider it to be unacceptable.
By submitting this report, you accept that it is accurate and that fraudulent or nuisance complaints may result in action by the University.