×

The BC-chain method for representing combinators in linear space. (English) Zbl 0594.68034

Summary: D. A. Turner’s combinator implementation [Software, Pract. Exper. 9, 31-49 (1979; Zbl 0386.68009)] of functional programs requires the memory space of size \(\Omega (n^ 2)\) in the worst case for translating given lambda expressions of length n to combinator graphs. In this paper a new idea named the BC-chain method for transferring actual arguments to variables is presented. We show that the BC-chain method requires only O(n) space for the translation. The basic idea is to group together into a single entity a sequence of combinators B, B’, C and C’, for a variable, which appear consecutively along a path in the combinator graph. We formulate two reduction algorithms in the new representation. The first algorithm naively simulates the original normal order reduction, while the second algorithm simulates it in constant time per unit operation of the original reduction. Another reduction method is also suggested, and a technique for practical implementation is briefly mentioned.

MSC:

68Q65 Abstract data types; algebraic specification
68Q25 Analysis of algorithms and problem complexity
68N01 General topics in the theory of software
03B40 Combinatory logic and lambda calculus
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdali, S. K., ”An abstraction algorithm for combinatory logic,”J. Symbolic Logic, 41, pp. 222–224, 1976. · Zbl 0331.02012
[2] Burton, F. W., ”A linear space representation of functional programs to Turner combinators,”Inform. Process. Lett., 14, pp. 201–204, 1982. · Zbl 0507.03004
[3] Hikita, T., ”On the average size of Turner’s translation to combinator programs,”J. Inform. Process., 7, 3, pp. 164–169, 1984. · Zbl 0567.68012
[4] Hughes, R. J. M., ”Super-Combinators,”Conf. Rec. of the 1982 ACM Symp. on LISP and Functional Programming, pp. 1–10, 1982.
[5] Kennaway, J. R., ”The complexity of a translation of {\(\lambda\)}-calculus to combinators,” School of Computing Studies and Accountancy, Univ. of East Anglia, Norwich, 1982.
[6] Kennaway, J. R. and Sleep, M. R., ”Efficiency of counting director strings,”typescript, 1983. · Zbl 0669.68013
[7] Noshita, K., ”Translation of Turner combinators inO(nlogn) space,”Inform. Process. Lett., 20, pp. 71–74, 1985. · Zbl 0558.68028
[8] Turner, D. A., ”Another algorithm for bracket abstraction,”J. Symbolic Logic., 44, pp. 267–270, 1979. · Zbl 0408.03013
[9] Turner, D. A., ”A new implementation technique for applicative languages,”Softw. Pract. Exper., 9, pp. 31–49, 1979. · Zbl 0386.68009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.