Director Strings as Combinators

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)

Abstract

A simple calculus (the Director String Calculus-DSC) for expressing abstractions is introduced, which captures the essence of the “long reach” combinators introduced by Turner. We present abstraction rules that preserve the applicative structure of the original lambda term, and that cannot increase the number of subterms in the translation. A translated lambda term can be reduced according to the evaluation rules of DSC. If this terminates with a DSC normal form, this can be translated into a lambda term using rules presented below. We call this process of abstracting a lambda term, reducing to normal form in the space of DSC terms, and translating back to a lambda term an implementation. We show that our implementation of the lambda calculus is correct: For lambda terms with a normal form that contains no lambdas (ground terms), the implementation is shown to yield a lambda calculus normal form. For lambda terms whose normal forms represent functions, it is shown that the implementation yields lambda terms that are beta-convertible in zero or more steps to the normal form of the original lambda term. In this sense, our implementation involves weak reduction according to Hindley et al. [9].
Original languageEnglish
Pages (from-to)602-626
Number of pages25
JournalACM Transactions on Programming Languages and Systems
Volume10
Issue number4
DOIs
Publication statusPublished - 1988

Cite this