page 1  (9 pages)
2to next section

Yes-no Combinators and an

Efficient Abstraction Algorithm?

Antoni Diller
School of Computer Science
Aston Webb Building
University of Birmingham
B15 2TT

December 7, 1993


One way of implementing a pure functional language is by compiling programs written in it into terms of combinatory logic and then reducing those terms (Turner, 1979b; Diller, 1988). One important part of this process is the bracket abstraction algorithm which removes a variable from a term. A new algorithm is presented in this paper which uses a potentially infinite number of yes-no combinators. The code produced by this algorithm is at most twice the length of the input, where the length of a term is the number of atoms in it.

1 Introduction

The language of combinatory logic is extremely simple. It makes use of three syntactic categories, namely that of constants, that of variables and that of terms, and only a single mode of combination, which represents function application. Its abstract syntax is given by the production:

ffl ::= <= j ? j fflffl0 :

This states that a term ffl is either a constant <= or a variable ? or it is formed by juxtaposing two terms fflffl0 . Some of the constants are known as combinators

?This report has appeared as Research Report CSR{93{8 of the School of Computer Science at the University of Birmingham.