ULC Bootstrap

An experimental project demonstrating a self-hosting compiler built entirely with untyped Lambda Calculus.

Purpose

This project serves as a practical exploration of:

• Untyped Lambda Calculus fundamentals
• Compiler construction techniques
• Bootstrapping methodology
• Functional encoding of data structures

Architecture

The project follows a bootstrapping approach:

1. compiler0 (Haskell): A compiler that translates .ulc source files to .sexpr intermediate code
2. runtime (Haskell): An interpreter that executes .sexpr files
3. stdlib: Standard library providing data structures (booleans, natural numbers, lists, etc.) encoded as pure functions using Scott encoding
4. compiler1: A self-hosting compiler written in Lambda Calculus (.ulc)
5. examples: Sample programs demonstrating the system's capabilities

Performance Note: The runtime evaluator is a naive implementation without optimization. It is suitable for small examples but impractical for complex programs like the self-hosting compiler due to exponential space/time complexity.

Prerequisites

• Haskell Stack

Building

Build the Haskell compiler and runtime:

stack build

Usage

Compiling .ulc files

stack run compiler0 -- <input.ulc> > <output.sexpr>

Example:

stack run compiler0 -- examples/sources/factorial.ulc > examples/factorial.sexpr

Running .sexpr files

stack run runtime -- <input.sexpr>

Example:

stack run runtime -- examples/factorial.sexpr

Compiling the Standard Library

Compile all standard library modules:

# On Linux/Mac
for file in stdlib/sources/*.ulc; do
    stack run compiler0 -- "$file" > "stdlib/$(basename "$file" .ulc).sexpr"
done

# On Windows (PowerShell)
Get-ChildItem stdlib\sources\*.ulc | ForEach-Object {
    stack run compiler0 -- $_.FullName > "stdlib\$($_.BaseName).sexpr"
}

Compiling the Self-Hosting Compiler

stack run compiler0 -- compiler1/sources/compiler.ulc > compiler1/compiler.sexpr

Note: While compiler1/compiler.sexpr is theoretically a working compiler, running it through the runtime is impractical due to performance limitations.

Project Structure

ulc-bootstrap/
├── compiler0/           # Bootstrap compiler (Haskell)
│   └── src/
│       ├── Compiler.hs
│       ├── Lexer.hs
│       └── Parser.hs
├── runtime/             # S-expression interpreter (Haskell)
│   └── src/
│       ├── Evaluator.hs
│       ├── ScottEncoding.hs
│       └── SExprParser.hs
├── stdlib/              # Standard library
│   └── sources/
│       ├── bool.ulc
│       ├── nat.ulc
│       ├── list.ulc
│       └── ...
├── compiler1/           # Self-hosting compiler
│   └── sources/
│       └── compiler.ulc
└── examples/            # Example programs
    └── sources/
        ├── factorial.ulc
        ├── fibonacci.ulc
        └── ...