An Adequate Left-Associated Binary Numeral System in the lambda-Calculus (Revised Version)
DOI:
https://doi.org/10.7146/brics.v3i6.19969Abstract
This paper introduces a sequence of lambda-expressions modelling the binary expansion of integers. We derive expressions computing the test for zero, the successor function, and the predecessor function, thereby showing the sequence to be an adequate numeral system. These functions can be computed efficiently. Their complexity is independent of the order of evaluation.
Keywords: Programming calculi, lambda-calculus, functional programming.
Downloads
Published
1996-01-06
How to Cite
Goldberg, M. (1996). An Adequate Left-Associated Binary Numeral System in the lambda-Calculus (Revised Version). BRICS Report Series, 3(6). https://doi.org/10.7146/brics.v3i6.19969
Issue
Section
Articles
License
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.