Projects per year
Abstract
A notion of probabilistic lambda-calculus usually comes with a prescribed reduction strategy, typically call-by-name or call-by-value, as the calculus is non-confluent and these strategies yield different results. This is a break with one of the main advantages of lambda-calculus: confluence, which means results are independent from the choice of strategy. We present a probabilistic lambda-calculus where the probabilistic operator is decomposed into two syntactic constructs: a generator, which represents a probabilistic event; and a consumer, which acts on the term depending on a given event. The resulting calculus, the Probabilistic Event Lambda-Calculus, is confluent, and interprets the call-by-name and call-by-value strategies through different interpretations of the probabilistic operator into our generator and consumer constructs. We present two notions of reduction, one via fine-grained local rewrite steps, and one by generation and consumption of probabilistic events. Simple types for the calculus are essentially standard, and they convey strong normalization. We demonstrate how we can encode call-by-name and call-by-value probabilistic evaluation.
Original language | English |
---|---|
Title of host publication | Foundations of Software Science and Computation Structures |
Subtitle of host publication | 23rd International Conference, FOSSACS 2020 Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2020 Dublin, Ireland, April 25–30, 2020, Proceedings |
Editors | Goubault-Larrecq Jean, Barbara König |
Place of Publication | Cham |
Publisher | Springer |
Pages | 136-156 |
Number of pages | 21 |
Volume | 12077 |
ISBN (Electronic) | 9783030452315 |
ISBN (Print) | 9783030452308 |
DOIs | |
Publication status | Published - 17 Apr 2020 |
Event | 23rd International Conference on Foundations of Software Science and Computation Structures - Dublin, Ireland Duration: 25 Apr 2020 → … https://etaps.org/2020/fossacs |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 12077 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 23rd International Conference on Foundations of Software Science and Computation Structures |
---|---|
Abbreviated title | FoSSaCS 2020 |
Country/Territory | Ireland |
City | Dublin |
Period | 25/04/20 → … |
Internet address |
ASJC Scopus subject areas
- Theoretical Computer Science
- General Computer Science
Fingerprint
Dive into the research topics of 'Decomposing probabilistic lambda-calculi'. Together they form a unique fingerprint.Projects
- 1 Finished
-
Typed Lambda-Calculi with Sharing and Unsharing
Heijltjes, W. (PI)
Engineering and Physical Sciences Research Council
1/01/19 → 30/07/22
Project: Research council
Profiles
-
Willem Heijltjes
- Department of Computer Science - Senior Lecturer
- Mathematical Foundations of Computation
Person: Research & Teaching