On the average size of Turner’s translation to combinator programs. (English) Zbl 0567.68012

D. A. Turner [Software, Pract. Exper. 9, 31-49 (1979; Zbl 0386.68009)] proposed an interesting method of implementation for functional programs by first translating them to combinator expressions without variables, and then reducing the graphs they represent. One of the points of concern for this method was the expansion of the sizes of expressions resulting from the translation. Kennaway has recently shown that the worst case of the size of this translation is of order \(n^ 2\) where n is the size of an original program. In this paper we choose a theoretical definition of an average size of the translation, and show that the order of the average is at most \(n^{3/2}\). Partial results on lower bounds of the average are also shown in the case of programs with one distinct variable. Finally, numerical results for the average size are exhibited.


68Q60 Specification and verification (program logics, model checking, etc.)


Zbl 0386.68009