Affordable Access

Publisher Website

A list-oriented extension of the lambda-calculus satisfying the Church—Rosser theorem

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
93
Issue
1
Identifiers
DOI: 10.1016/0304-3975(92)90212-x
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract A list-oriented extension of the type-free lambda-calculus is considered where lists have a unique applicative property. This property is related to the combining form of construction in Backus's functional programming system called FP. We express this property in our system by two extra reduction rules, which we call γ-rules. Our extension helps reducing the gap between type-free lambda-calculus and high-level functional languages. The main purpose of this paper is to prove the consistency of this extended lambda-calculus by showing that it satisfies the Church—Rosser theorem.

There are no comments yet on this publication. Be the first to share your thoughts.