Ale Assembler

Thomas Bradford Aug 21, 2024

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?

Special forms, such as if, are a low-level type 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 provide the means to emit instructions for the Ale compiler and VM. I’ll show you.

(define* if
  (asm* !make-special
    [(predicate consequent alternative) ;; step 1
          .eval predicate               ;; step 2
          cond-jump :consequent         ;; step 3
          .eval alternative             ;; step 4
          jump :end
      :consequent                       ;; step 5
          .eval consequent
      :end]
    [(predicate consequent)
          .eval predicate
          cond-jump :consequent
          null
          jump :end
      :consequent
          .eval consequent
      :end]))

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

In step 1 we’re defining the arity case that accepts three arguments: a predicate, a consequent, and an alternative.

In step 2 we’re instructing the assembler to evaluate the provided predicate and push its value onto the front of the stack.

In step 3 we’re instructing the assembler to pop the front of the stack, and if the value is ’truthy’, to jump to the label called :consequent. In the Ale Assembler, labels are represented by keywords.

In step 4 we’re instructing the assembler to evaluate the alternative, pushing its value onto the front of the stack, and to jump to the label called :end, which is the end of the arity case in this example.

In step 5 we’re instructing the assembler to evaluate the consequent, pushing its value onto the front of the stack. It will then fall through to the end of the arity case.

Steps 4 and 5 are mutually exclusive and depend on the outcome of the cond-jump call. In the second arity case, we’re essentially doing the same thing but pushing the null value in place of an alternative branch that isn’t provided.

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 and performs a dynamic loop over its arguments. Well, you can write an encoder function for + that generates proper VM code.

(define* fast+
  (asm* !make-special operands
      zero                      ;; step 1
      .for-each [o operands]    ;; step 2
          .eval o               ;; step 3
          add                   ;; step 4
      .end))

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 step 2 we’re looping over the operands value provided to the special form, assigning each element to an argument of o for the body of the loop.

In steps 3 and 4 we’re evaluating each argument, pushing its value onto the stack, and performing an Add instruction.

We now have a special form that is bound 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.

Ale Assembler

And Why Should I Care?

Further Reading