×

Complexity of the combinator reduction machine. (English) Zbl 0591.68048

Summary: The complexity of the computation of recursive programs by the combinator reduction machine is studied. The number of the reduction steps is compared between the two models of computation. The main theorem states that the time required by the reduction machine is linear in that of the program scheme. The coefficient of the linearity was shown to be \(O(n^ 2)\), where n is the maximal number of variables of the functions being used. For the analysis of the combinator codes, the notion of extended combinator code is introduced.

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aiello, L.; Prini, G., An efficient interpreter for the lambda calculus, J. Comput. System Sci., 23, 383-424 (1981) · Zbl 0472.03012
[2] Barendregt, H. P., The Lambda Calculus, Its Syntax and Semantics (1981), North-Holland: North-Holland Amsterdam · Zbl 0467.03010
[3] Berry, G.; Levy, J.-J., Minimal and optimal computations of recursive programs, J. ACM, 26, 148-175 (1979) · Zbl 0388.68012
[4] Burton, F. W., A linear space translation of functional programs to Turner combinators, Inform. Process. Lett., 14, 201-204 (1982) · Zbl 0507.03004
[5] Hikita, T., On the average size of Turner’s translation to combinator programs, J. Inform. Process., 7, 164-169 (1984) · Zbl 0567.68012
[6] Levy, J.-J., Optimal reductions in the lambda calculus, (Seldin, J. P.; Hindley, J. R., To H.B. Carry: Essays on Combinatory Logic, Lambda Calculus and Formalism (1980), Academic Press: Academic Press New York/London), 159-191
[7] Noshita, K.; Hikita, T., The BC-chain method for representing combinators in linear space, New Generation Comput., 3, 131-144 (1985) · Zbl 0594.68034
[8] Turner, D. A., A new implementation technique for applicative languages, Softw. Pract. Exper., 9, 31-49 (1979) · Zbl 0386.68009
[9] Turner, D. A., Another algorithm for bracket abstraction, J. Symbolic Logic, 44, 267-270 (1979) · Zbl 0408.03013
[10] Vuillemin, J., Correct and optimal implementations of recursion in a simple programming language, J. Comput. System Sci., 9, 332-354 (1974)
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.