De Bruijn Numerals: A Novel Number Encoding Method in Lambda Calculus
By
marvinborner
Baker's choice. Dense with flavour, light on filler.
Summary
The article introduces a novel method for encoding numbers in pure lambda calculus called 'de Bruijn numerals', which uses nested de Bruijn indices to represent numbers through reference depth. The author explains that this encoding differs from traditional methods like Church numerals, n-ary representations, and Scott encoding, and presents the mathematical formulation where a number n is encoded as λ^(S(n)) n (lambda raised to S(n) applied to n). The article appears to be a technical exploration of lambda calculus representations with mathematical notation and examples.
Key quotes
· 4 pulledA method that I have not seen yet is an encoding by reference depth. Specifically, I refer to a nested de Bruijn index that, by itself, encodes the number: ⟨n⟩d=λS(n) n
For example, the decimal number 4 would be encoded as ⟨4⟩d=λ5 4.
Isn't this just so elegant? Because I could not find a name for the encoding, I call it 'de Bruijn numerals'.
There are many ways to encode numbers and do arithmetic in the pure lambda calculus, for example using unary Church numerals, various n-ary representations, and the Scott encoding.
You might also wanna read
The History of Pipes, Forks, and Zombies in Unix Systems
This article discusses the history and concept of pipes in Unix systems, focusing on Doug McIlroy's original vision of coupling programs lik
A 7-line interpreter: Implementing a functional programming language in minutes
The article presents a minimal 7-line interpreter for a functional programming language, demonstrating the eval/apply design pattern from St
Demystifying Floating Point Numbers: An Interactive Guide
An in-depth technical blog post that demystifies floating point numbers, explaining their internal representation and behavior. The author i
ciechanow.ski·1mo agoThe Seven Foundational Programming Paradigms: Understanding Core Concepts Beyond Specific Languages
The article argues that instead of focusing on specific programming languages, learners should understand the fundamental 'ur-languages' or
Introduction to C Programming: Understanding the Foundational Language
This appears to be the beginning of a book about the C programming language, specifically Chapter 1 titled 'Getting Started.' The content in
A Compiler Writing Journey: Building a Self-Compiling C Subset Compiler
A GitHub repository documenting a personal journey to write a self-compiling compiler for a subset of the C language. The project provides p
github.com·2mo ago