Spinal atomic lambda-calculus

David Sherratt; Willem Heijltjes; Tom Gundersen; Michel Parigot

doi:10.1007/978-3-030-45231-5_30

Spinal atomic lambda-calculus

David Sherratt, Willem Heijltjes, Tom Gundersen, Michel Parigot

Research output: Contribution to conference › Paper › peer-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 language	English
Pages	582-601
Number of pages	20
DOIs	https://doi.org/10.1007/978-3-030-45231-5_30
Publication status	Published - 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
General Computer Science

Access to Document

10.1007/978-3-030-45231-5_30Licence: CC BY

Cite this

@conference{eedca6c7304b427aaf44a5fd759fd7d3,

title = "Spinal atomic lambda-calculus",

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.",

keywords = "Curry–Howard, Deep inference, Full laziness, Lambda-Calculus",

author = "David Sherratt and Willem Heijltjes and Tom Gundersen and Michel Parigot",

note = "Publisher Copyright: {\textcopyright} 2020, The Author(s).",

year = "2020",

doi = "10.1007/978-3-030-45231-5_30",

language = "English",

pages = "582--601",

}

TY - CONF

T1 - Spinal atomic lambda-calculus

AU - Sherratt, David

AU - Heijltjes, Willem

AU - Gundersen, Tom

AU - Parigot, Michel

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Curry–Howard

KW - Deep inference

KW - Full laziness

KW - Lambda-Calculus

UR - http://www.scopus.com/inward/record.url?scp=85084108091&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-45231-5_30

DO - 10.1007/978-3-030-45231-5_30

M3 - Paper

SP - 582

EP - 601

ER -

Spinal atomic lambda-calculus

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Typed Lambda-Calculi with Sharing and Unsharing

Cite this

Spinal atomic lambda-calculus

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

Typed Lambda-Calculi with Sharing and Unsharing

Cite this