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.
- 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.