LISP and Symbolic Computation, 3(2)113-133

A Metacircular Evaluator for a Logical Extension of Scheme

Pierre E. Bonzon, HEC, University of Lausanne, 1015 Lausanne, Switzerland

Abstract: We define a computational model for a logical extension of Scheme, and give a metacircular evaluator for it. This minimal extension incorporates two new features only, i.e., logical variables and clause expressions, which can be used to define predicates in exactly the same way as lambda expressions can be used to define functions.

Higher-order properties of Scheme are preserved; predicates can be passed to and returned from function applications. Predicate applications can appear as terms in functions. On the other hand, function applications can appear as terms in predicates, and can be formal as well as actual arguments, but only as long as they can be evaluated according to the usual Scheme semantics prohibiting access to unbound variables (except for constructor applications).

This article is not available online. 		[picture of journal cover]

March 2003 - hosc@brics.dk