WIP - Work in progress

The following post is a work in progress, but I thought I'd keep uploading it as a way to push myself to finish it sooner rather than later.

Lambda Calculus: Building little languages

In my work I have had several opportunities to build tooling for other developers. Specifically these have been tools for assembling apps, programs and infrastructure using a high level language.

These have mostly been experimental, either exploring the benefits of different compiler architectures, approaches to optimisation or programming paradigms.

So, I've been stuck with a question:

How do we build a programming language from the smallest number of the simplest parts possible?

Many approaches have been taken to building programming languages and compilers, and there are almost as many approaches to doing so.

A small family tree of programming language models

My favourite approach: Lambda Calculus

My favourite class of approaches is to build a small core language and build everything on top of that. This has a few benefits that I hope to detail here.

TODO: Finish

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Eq, Hash, Ord, PartialOrd, PartialEq)]
enum Term {
    Var(usize),
    App(Box<Term>, Box<Term>),
    Abs(Box<Term>),
}

fn abs(t: Term) -> Term {
    Term::Abs(Box::new(t))
}

fn app(t: Term, a: Term) -> Term {
    Term::App(Box::new(t), Box::new(a))
}

fn var(i: usize) -> Term {
    Term::Var(i)
}

let a_b_gives_a = abs(abs(var(0)));
let a_b_gives_b = abs(abs(var(1)));
println!("A simple term {:?}", a_b_gives_a);
println!("Another simple term {:?}", a_b_gives_b);

fn render(term: &Term) -> String {
    format!("{:?}", term)
}

}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Eq, Hash, Ord, PartialOrd, PartialEq)]
enum Term {
    Var(usize),
    App(Box<Term>, Box<Term>),
    Abs(Box<Term>),
}

fn abs(t: Term) -> Term {
    Term::Abs(Box::new(t))
}

fn app(t: Term, a: Term) -> Term {
    Term::App(Box::new(t), Box::new(a))
}

fn var(i: usize) -> Term {
    Term::Var(i)
}

let a_b_gives_a = abs(abs(var(0)));
let a_b_gives_b = abs(abs(var(1)));
println!("A simple term {:?}", a_b_gives_a);
println!("Another simple term {:?}", a_b_gives_b);

fn render(term: &Term) -> String {
    format!("{:?}", term)
}

}

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Eq, Hash, Ord, PartialOrd, PartialEq)]
enum Term {
    Var(usize),
    App(Box<Term>, Box<Term>),
    Abs(Box<Term>),
}

fn abs(t: Term) -> Term {
    Term::Abs(Box::new(t))
}

fn app(t: Term, a: Term) -> Term {
    Term::App(Box::new(t), Box::new(a))
}

fn var(i: usize) -> Term {
    Term::Var(i)
}

let a_b_gives_a = abs(abs(var(0)));
let a_b_gives_b = abs(abs(var(1)));
println!("A simple term {:?}", a_b_gives_a);
println!("Another simple term {:?}", a_b_gives_b);

fn render(term: &Term) -> String {
    format!("{:?}", term)
}

}

Here's the full code for you to experiment with:

#[derive(Debug, Clone, Eq, Hash, Ord, PartialOrd, PartialEq)]
enum Term {
    Var(usize),
    App(Box<Term>, Box<Term>),
    Abs(Box<Term>),
}

fn abs(t: Term) -> Term {
    Term::Abs(Box::new(t))
}

fn app(t: Term, a: Term) -> Term {
    Term::App(Box::new(t), Box::new(a))
}

fn var(i: usize) -> Term {
    Term::Var(i)
}

let a_b_gives_a = abs(abs(var(0)));
let a_b_gives_b = abs(abs(var(1)));
println!("A simple term {:?}", a_b_gives_a);
println!("Another simple term {:?}", a_b_gives_b);

fn render(term: &Term) -> String {
    format!("{:?}", term)
}