Extending Ale

Thomas Bradford Apr 17, 2019

Ale is a dialect of Lisp which means that it’s infinitely extensible out of the box. Hygienic macros and syntax quoting make this possible. But what if you really, really need to start making deep changes? Like at the compiler level? Well, I’ve designed that to be a relatively straight-forward process as well!

From the Ale REPL, type the word if (no parens) and you’ll see something like this:

{:instance "0x51a160" :type special}

This is the string representation of Ale’s if special form. Other forms will present themselves differently. For example, lazy-seq has a type of “macro”, while first is a lambda and has a type of “procedure”. But what’s this “special” stuff?

Encoder functions, such as if, are another special kind of function that can only be invoked by Ale’s compiler. They differ from macros in that when the compiler does invoke them, it will pass an encoder object in the receiver position (first argument). The function can then use that encoder to emit instructions for the Ale compiler. I’ll show you.

func If(e encoder.Encoder, args ...data.Value) {
    al := arity.AssertRanged(2, 3, len(args)) // step 1
    generate.Branch(e,                        // step 2
        func(e encoder.Encoder) {
            generate.Value(e, args[0])        // step 3
        },
        func(e encoder.Encoder) {
            generate.Value(e, args[1])        // step 4
        },
        func(e encoder.Encoder) {
            if al == 3 {                      // step 5
                generate.Value(e, args[2])
            } else {
                generate.Null(e)
            }
        },
    )
}

This is a possible implementation of the if special form that we mentioned before. Not a lot to see here, right?

In step 1 we’re performing an arity check. For normal functions and macros, the compiler will emit code that performs arity checks, but it doesn’t do so for encoder functions because, well, it hasn’t encoded anything yet. We’re just too low-level!

In step 2 we’re calling a builder function named Branch. This function emits the necessary instructions for performing a conditional branch, so that we don’t have to. All we need to do is fill in the gaps. This is done by providing functions that emit their own code. The first is the condition to test, the second is the then branch, and the third is the else branch.

In step 3 we’re taking if’s first argument and asking Ale to generate evaluating code for it. generate.Value will accept some kind of value, whether its a sequence, symbol, or literal, and generate the proper code for evaluating it.

In step 4 we’re telling the encoder to generate code that evaluates the then branch.

In step 5 we’re testing whether or not there is an else branch, and if so we generate code for it. Otherwise we just tell Ale to push a null literal onto the stack.

By the way, the generate.Branch() function is every bit as straight-forward. I’ll leave it to you to figure out what it’s doing.

func Branch(e encoder.Encoder,
        predicate, consequent, alternative Builder,
) {
	thenLabel := e.NewLabel()
	endLabel := e.NewLabel()

	predicate(e)
	e.Emit(isa.CondJump, thenLabel)
	alternative(e)
	e.Emit(isa.Jump, endLabel)
	e.Emit(isa.Label, thenLabel)
	consequent(e)
	e.Emit(isa.Label, endLabel)
}

And Why Should I Care?

So what can you do with this knowledge? Well, let’s say you don’t like the built-in + function. After all, it’s applicative, written in Go, and performing a dynamic loop over its arguments. Well, you can write an encoder function for + that generates proper VM code.

import "github.com/kode4food/ale/compiler/encoder"
import "github.com/kode4food/ale/compiler/generate"
import "github.com/kode4food/ale/data"
import "github.com/kode4food/ale/runtime/isa"

func FastAdd(e encoder.Encoder, args ...data.Value) {
    e.Emit(isa.Zero)            // step 1
    for _, arg := range args {
        generate.Value(e, arg)  // step 2
        e.Emit(isa.Add)         // step 3
    }
}

// step4 -- somewhere else
env.GetRoot().Declare("fast+").Bind(encoder.Call(FastAdd))

In step 1 we push the literal number zero onto the stack. Zero is used so often in the VM that it has a dedicated instruction.

In steps 2 and 3 we’re pushing each evaluated argument onto the stack, and performing an Add instruction.

In step 4 we mark our function as an encoder.Call, and bind it to the root of our environment. We can then call it like so: (fast+ 9 10 73 12.4).

Because we know ahead of time how many operands we’re adding, we can generate much faster VM code. The problem with this approach is that we can’t use it with the apply function, and that makes Lisp less fun.