go-v.orgdoi

A Temporal Logic Approach to Binding-Time Analysis

Rowan Davies · Journal of the ACM · 2017

  • DOI 10.1145/3011069
  • Publisher Association for Computing Machinery
  • Type article
  • Issued 2017

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

Journal of the ACM · Association for Computing Machinery · article · 2017

Abstract

This article demonstrates that there is a fundamental relationship between temporal logic and languages that involve multiple stages, such as those used to analyze binding times in the context of partial evaluation. This relationship is based on an extension of the Curry-Howard isomorphism, which identifies proofs with programs, and propositions with types. Our extension involves the “next time” (○) operator from linear-time temporal logic and yields a λ-calculus λ° with types of the form ○ A for expressions in the subsequent stage, with appropriate introduction and elimination forms. We demonstrate that λ° is equivalent to the core of a previously studied multilevel binding-time analysis.

This is similar to work by Davies and Pfenning on staged computation based on the necessity (□) operator of modal logic, but □ only allows closed code, and naturally supports a code evaluation construct, whereas ○ captures open code, thus is more flexible, but is incompatible with such a construct. Instead, code evaluation is an external global operation that is validated by the proof theory regarding closed proofs of ○ formulas. We demonstrate the relevance of λ° to staged computation directly by showing that that normalization can be done in an order strictly following the times of the logic.

We also extend λ° to small functional language and show that it would serve as a suitable basis for directly programming with multiple stages by presenting some example programs.

Open the resolved locator · 10.1145/3011069

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-20 00:07 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://doi.org/10.1145/3011069
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.