Rewriting system for categorical combinators with multiple arguments

Abstract

Categorical combinators have been derived from the study of categorical semantics of lambda calculus, and it has been found that they may be used in implementation of functional languages. In this paper categorical combinators are extended so that functions with multiple arguments can be directly handled, thus making them more suitable for practical computation. A rewriting system named CCLMβ is formulated for these combinators. This system naturally corresponds to the type-free λβ-calculus. The relationship between these two systems is established, and as a result of this, the Church-Rosser property of CCLMβ is proved. A similar relationship is also established between the original CCLβ by Curien and the type-free λβ-calculus with product. Finally the embedding theorem of CCLMβ into CCLβ is shown.