
Yesno Combinators and an
Efficient Abstraction Algorithm?
Antoni Diller
School of Computer Science
Aston Webb Building
University of Birmingham
Birmingham
B15 2TT
England
A.Diller@cs.bham.ac.uk
December 7, 1993
Abstract
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 yesno 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.