An Adequate Left-Associated Binary Numeral System in the lambda-Calculus

Mayer Goldberg

Abstract


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.


Full Text:

PDF


DOI: http://dx.doi.org/10.7146/brics.v2i42.19943
This website uses cookies to allow us to see how the site is used. The cookies cannot identify you or any content at your own computer.
OK


ISSN: 0909-0878 

Hosted by the Royal Danish Library and Aarhus University Library