Hostname: page-component-586b7cd67f-2brh9 Total loading time: 0 Render date: 2024-11-24T02:43:52.345Z Has data issue: false hasContentIssue false
  • English
  • Français

An adequate and efficient left-associated binary numeral system in the λ-calculus

Published online by Cambridge University Press:  01 March 2001

MAYER GOLDBERG
MAYER GOLDBERG
Affiliation:
Department of Computer Science, Ben Gurion University, Beer Sheva 84105, Israel (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper introduces a sequence of λ-expressions modeling 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, i.e. one in which all recursive functions are lambda-definable. These functions can be computed efficiently; To this end, we introduce a notion of complexity that is independent of the order of evaluation.

Type
THEORETICAL PEARLS
Information
Journal of Functional Programming , Volume 10 , Issue 6 , November 2000 , pp. 607 - 623
Copyright
© 2000 Cambridge University Press
Submit a response

Discussions

No Discussions have been published for this article.