CATEGORICAL COMBINATORS WITH EXPLICIT PRODUCTS

Article type: Research Article

Authors: Révész, György E.

Affiliations: Department of Computer Science, University of North Carolina at Charlotte, Charlotte, N.C. 28223, 704-547-4880, Internet: revesz@mosaic.uncc.edu

Abstract: Categorical Combinators arose from the intertranslation between lambda-calculus and Cartesian Closed Categories. Their theory is fairly similar to classical Combinatory Logic, and they also have been used for the design of the so called Categorical Abstract Machine [2]. The latter is claimed to be more efficient than Landin's SEDC Machine [9], which has been based on classical combinators. There is, however, an intriguing problem with Categorical Combinators. Namely, their defining properties imply the existence of surjective pairing, which is known to be incompatible with the Church-Rosser property in the type-free lambda-calculus. The non-confluence of the type-free lambda-calculus with surjective pairing was shown by Klop in 1980 [5]. In March, 1991, Curien communicated an amazingly simple new proof. The confluence of Curien's Strong Categorical Combinatory Logic [3], which involves surjective pairing, is still an open problem. Therefore, Curien and others have studied various weaker systems. One of them appears to be closely related to a conservative extension of the type-free lambda-calculus, whose confluence has been shown by the author in a previous paper [11]. In this paper we study the relationship between categorical combinators and our Extended Lambda-Calculus with Explicit Products, which was first published in 1984 [10].

DOI: 10.3233/FI-1995-22127

Journal: Fundamenta Informaticae, vol. 22, no. 1-2, pp. 153-166, 1995