Skip to main content

Partial Categorical Multi-Combinators and Church-Rosser Theorems

Lins, Rafael D. (1994) Partial Categorical Multi-Combinators and Church-Rosser Theorems. Technical report. University of Kent, Canterbury, UK, University of Kent, Canterbury, UK (The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided) (KAR id:21163)

The full text of this publication is not currently available from this repository. You may be able to access a copy if URLs are provided.

Abstract

Categorical Multi-Combinators form a rewriting system developed with the aim of providing efficient implementations of lazy functional languages. The core of the system of Categorical Multi-Combinators consists of only four rewriting laws with a very low pattern-matching complexity. This system allows the equivalent of several b-reductions to be performed at once, as functions form frames with all their arguments. This feature is convenient for most cases of function application, but it does not allow partially parameterised functions to fetch arguments. Presented within this paper are Partial Categorical Multi-Combinators (PCMC), a new rewriting system, which removes this drawback. The computational power of Partial Categorical Multi-Combinators is equivalent to the rewriting system presented in [17], but PCMC uses fewer rewriting laws with a much simpler syntax. These factors made the proofs of the Church-Rosser properties for PCMC far easier than the ones in [17]. This report replaces report no. 7-92.

Item Type: Reports and Papers (Technical report)
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Mark Wheadon
Date Deposited: 12 Aug 2009 19:26 UTC
Last Modified: 16 Nov 2021 09:59 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/21163 (The current URI for this page, for reference purposes)

University of Kent Author Information

  • Depositors only (login required):

Total unique views for this document in KAR since July 2020. For more details click on the image.