marvinborner/bruijn: :abacus: Programming with pure lambda calculus

A purely functional programming language based on lambda calculus and de Bruijn indices written in Haskell.

Pronunciation: /bɹaʊn/.

Wiki, docs, articles, examples and more: website. Also: Rosetta Code.

Features

De Bruijn indices eliminate the complexity of α-equivalence and α-conversion
Call-by-need reduction with great time/memory complexity by using the RKNL abstract machine (similar to calm)
Syntactic sugar for unary/binary/ternary numerals and binary-encoded strings and chars
No primitive functions - every function is implemented in Bruijn itself
Highly space-efficient compilation to binary lambda calculus (BLC) additionally to normal interpretation and REPL
Recursion can be implemented using combinators such as Y, Z or ω
Substantial standard library featuring many useful functions (see std/)

Learn anything about bruijn in the wiki (also found in docs/wiki_src/).

De Bruijn, Nicolaas Govert. “Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem.” Indagationes Mathematicae (Proceedings). Vol. 75. No. 5. North-Holland, 1972.
Mogensen, Torben. “An investigation of compact and efficient number representations in the pure lambda calculus.” International Andrei Ershov Memorial Conference on Perspectives of System Informatics. Springer, Berlin, Heidelberg, 2001.
Wadsworth, Christopher. “Some unusual λ-calculus numeral systems.” (1980): 215-230.
Tromp, John. “Binary lambda calculus and combinatory logic.” Randomness and Complexity, from Leibniz to Chaitin. 2007. 237-260.
Tromp, John. “Functional Bits: Lambda Calculus based Algorithmic Information Theory.” (2022).
Biernacka, M., Charatonik, W., & Drab, T. (2022). A simple and efficient implementation of strong call by need by an abstract machine. Proceedings of the ACM on Programming Languages, 6(ICFP), 109-136.