Decomposing probabilistic lambda-calculi

Ugo Dal Lago, Giulio Guerrieri, Willem Heijltjes

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

1 Citation (Scopus)

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 languageEnglish
Title of host publicationFoundations of Software Science and Computation Structures
Subtitle of host publication23rd 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
EditorsGoubault-Larrecq Jean, Barbara König
Place of PublicationCham
PublisherSpringer
Pages136-156
Number of pages21
Volume12077
ISBN (Electronic)9783030452315
ISBN (Print)9783030452308
DOIs
Publication statusPublished - 17 Apr 2020
Event23rd International Conference on Foundations of Software Science and Computation Structures - Dublin, Ireland
Duration: 25 Apr 2020 → …
https://etaps.org/2020/fossacs

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12077
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference23rd International Conference on Foundations of Software Science and Computation Structures
Abbreviated titleFoSSaCS 2020
CountryIreland
CityDublin
Period25/04/20 → …
Internet address

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this