Lambda Calculus in 383 Bytes
SectorLambda is a 383-byte binary lambda calculus implementation featuring a virtual machine with garbage collection and lazy lists, suitable for education and data compression, with compact program examples provided.
Read original article
The blog post discusses a new implementation of binary lambda calculus, which is a minimalist programming language, in just 383 bytes as an x86-64 Linux ELF executable. This implementation, called SectorLambda, features a Church-Krivine-Tromp virtual machine capable of garbage collection, lazy lists, and tail recursion. The interpreter processes input by extracting the least significant bit from each byte, producing binary output. While the 383-byte version is suitable for learning, a larger 520-byte version is available for more complex applications. The post highlights the compactness of programs written in binary lambda calculus, with examples demonstrating how small programs can be. It also discusses potential applications in compression formats, suggesting that the interpreter could be used to create self-extracting archives. The post includes details on how to compile and run programs, as well as examples of lambda calculus expressions and their corresponding outputs. Additionally, it provides insights into the programming constructs and definitions used within the language, emphasizing its efficiency and expressiveness compared to traditional programming languages.
- SectorLambda is a 383-byte implementation of binary lambda calculus.
- It features a virtual machine with capabilities like garbage collection and lazy lists.
- The language allows for extremely compact programs, with examples showing programs as small as 43 bytes.
- The implementation can be used for educational purposes and has potential applications in data compression.
- The post includes instructions for compiling and running programs in binary lambda calculus.
Related
Lisp with GC in 436 Bytes
SectorLISP, a compact programming language with garbage collection, fits in a 436-byte boot sector, surpassing FORTH and BASIC. It runs on 1981 PC models and emphasizes file size optimization.
SectorC: A C Compiler in 512 bytes (2023)
SectorC is a compact C compiler fitting within a 512-byte boot sector, supporting a significant subset of C with advanced features, achieving a size of 303 bytes for practical applications.
Introduction to the λ-Calculus
The λ-calculus is a foundational framework in computer science, influencing programming languages and introducing concepts like currying, variable types, and key operations such as β-reduction and α-conversion.
Compiling Lisp to Bytecode and Running It
Andrew Healey explains compiling Lisp to bytecode for a custom virtual machine, detailing instruction processing, performance optimizations, and providing source code on GitHub for further exploration of bytecode VMs.
Size Optimization Tricks (2022)
The blog post discusses techniques for optimizing binary sizes in programming languages, emphasizing the Cosmopolitan codebase and advocating for efficiency, simplicity, and a cultural shift towards minimizing software complexity.
- Several users express difficulty in understanding the core concepts of lambda calculus, seeking simpler explanations or introductions.
- One commenter shares an example of a program that can be run on the virtual machine, highlighting its capabilities.
- There is a mention of the compactness and expressiveness of the implementation, with some users surprised by its efficiency.
- Some users draw comparisons to other programming languages and concepts, indicating a diverse range of backgrounds among commenters.
- Technical issues are noted, with one user reporting that the implementation does not work on macOS.
13 commentsBut I can't quite wrap my mind around the core concepts and internalize them into a mental model. It's too different from the simple world of imperative C or scripting languages I guess I call home. So I'm left watching das blinkenlights from the outside, as my attention span chokes on the layers of computer science incorporated into typical explanations. *shrug*
I'd be very interested if anyone knows of an ELI5-style alternate path I could walk to break each of the concepts down one at a time. (I ask because I think this is (currently) the kind of thing I think ChatGPT would struggle to present as effectively as a human.)
Lambda Calculus in 400 Bytes - https://news.ycombinator.com/item?id=30493713 - Feb 2022 (63 comments)
Looks like Brainfuck in disguise :)
Cheers,
> { printf 0010; printf 0101; } | ./lambda.com; echo
zsh: done { printf 0010; printf 0101; } |
zsh: segmentation fault ./lambda.comRelated
Lisp with GC in 436 Bytes
SectorLISP, a compact programming language with garbage collection, fits in a 436-byte boot sector, surpassing FORTH and BASIC. It runs on 1981 PC models and emphasizes file size optimization.
SectorC: A C Compiler in 512 bytes (2023)
SectorC is a compact C compiler fitting within a 512-byte boot sector, supporting a significant subset of C with advanced features, achieving a size of 303 bytes for practical applications.
Introduction to the λ-Calculus
The λ-calculus is a foundational framework in computer science, influencing programming languages and introducing concepts like currying, variable types, and key operations such as β-reduction and α-conversion.
Compiling Lisp to Bytecode and Running It
Andrew Healey explains compiling Lisp to bytecode for a custom virtual machine, detailing instruction processing, performance optimizations, and providing source code on GitHub for further exploration of bytecode VMs.
Size Optimization Tricks (2022)
The blog post discusses techniques for optimizing binary sizes in programming languages, emphasizing the Cosmopolitan codebase and advocating for efficiency, simplicity, and a cultural shift towards minimizing software complexity.