Spinal atomic lambda-calculus

David Sherratt, Willem Heijltjes, Tom Gundersen, Michel Parigot

Research output: Contribution to conferencePaperpeer-review

3 Citations (SciVal)

Abstract

We present the spinal atomic λ-calculus, a typed λ-calculus with explicit sharing and atomic duplication that achieves spinal full laziness: duplicating only the direct paths between a binder and bound variables is enough for beta reduction to proceed. We show this calculus is the result of a Curry–Howard style interpretation of a deep-inference proof system, and prove that it has natural properties with respect to the λ-calculus: confluence and preservation of strong normalisation.

Original languageEnglish
Pages582-601
Number of pages20
DOIs
Publication statusPublished - 2020

Bibliographical note

Publisher Copyright:
© 2020, The Author(s).

Keywords

  • Curry–Howard
  • Deep inference
  • Full laziness
  • Lambda-Calculus

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Spinal atomic lambda-calculus'. Together they form a unique fingerprint.

Cite this