Open AccessAn Adequate Left-Associated Binary Numeral System in the lambda-Calculus
Author(s) -
Mayer Goldberg
Publication year - 1995
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v2i42.19943
Subject(s) - numeral system , mathematics , arithmetic , lambda , sequence (biology) , binary number , lambda calculus , combinatorics , successor cardinal , function (biology) , discrete mathematics , algorithm , mathematical analysis , physics , evolutionary biology , biology , optics , genetics
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.