My interest in Tree Calculus

I was playing with lambda calculus and even writing an interpretor for a small language based on it. One of the pain points was related to metaprogramming. Specifically that lambda calculus didn’t have any support for it. I did implement Mogensen-Scott encoding ¹ but it felt like the theory was lacking because metaprogramming existed outside of the theory. Around the same time, I saw tree calculus mentioned. It was a hacker news post ². I naturally felt inclined to learn about it since it offered metaprogramming in the core theory. After an initial pass through the calculus I put it off to the side due to other priorities. I decided to pick it back up again in December and decided to write an interpreter to learn it more thoroughly.

Introduction

The specification ³ mentions 5 rules, the first two matching the K and S combinators respectively. The last 3 are about triaging to different branches based on the shape of the argument. One comment ⁴ on hacker news was particularly insightful for me to initially understanding the calculus. They mentioned there are 2 implicit preamble rules, which add a left and right branch before you can actually use the tree. These rules in total look like:

1. Δ @ x = Δ x
2. Δ x @ y = Δ x y
3. Δ Δ y @ z = y
4. Δ (Δ x) y @ z = (x @ z) @ (y @ z)
5. Δ (Δ w x) y @ Δ = w
6. Δ (Δ w x) y @ Δ u = x u
7. Δ (Δ w x) y @ Δ u v = y u v

Rules 1 and 2 correspond to rules 0a and 0b in the comment. Rules 3 and 4 correspond to rules 1 and 2 in the specification. Rules 5, 6 and 7 correspond to rules 3a, 3b and 3c in the specification.

These are all the rules that exist in the calculus. If you memorize these you will have the building blocks of what you can do.

Creating my language

I code named the interpreter “spruce” since I started working on it around Christmas and I wanted it to take its name after a tree. Initially I added support for the core machine. And slowly started adding quality of life improvements. I eventually ended up with something that looks like:

:import "combinators.spruce"
:import "list.spruce"
:import "boolean.spruce"
:import "bin.spruce"

serialize_string = \s.map (\bits.right_pad bits 8 false) s # assuming all codepoints are single byte ascii characters

serialize_nat_to_uint16 = \n.chunk 8 (right_pad (nat_to_bin n) 16 false)
serialize_nat_to_uint32 = \n.chunk 8 (right_pad (nat_to_bin n) 32 false)

sample_rate = 44100

count_down = fix (\self.
    triage
      [0]
      (\s.cons (Δ s) (self s))
      (\l.\r.Δ) # shouldn't be possible with nats
  )

count_up = \n.reverse (count_down n)

saw_window = map nat_to_bin (count_up 255)

samples = concat (repeat saw_window 173) # 44100 / 256 ~ 173

wav = concat [
    (serialize_string "RIFF"),
    (serialize_nat_to_uint32 (plus (length samples) 36)),
    (serialize_string "WAVE"),
    (serialize_string "fmt "),
    (serialize_nat_to_uint32 16),
    (serialize_nat_to_uint16 1), # 1 is PCM
    (serialize_nat_to_uint16 1), # num of channels
    (serialize_nat_to_uint32 sample_rate),
    (serialize_nat_to_uint32 sample_rate),
    (serialize_nat_to_uint16 1), # 1 is 8 bit mono
    (serialize_nat_to_uint16 8), # bits per sample
    (serialize_string "data"),
    samples
  ]

:write_file "test.wav" wav

This program outputs a wav file with a 1 second sawtooth sound. This desugars into tree calculus. The only functions with side effects are :import which modifies the environment by importing definitions from other files, = which modifies the environment with a new definition, and :write_file which writes bytes into a file.