Ekaitz's tech blog:
I make stuff at ElenQ Technology and I talk about it

In our previous blogpost we talked about GNU Mes’ garbage collector and we left some cliffhanger in the end, saying that we’d need to use that for the macro expansion and I was having a really hard time with it.

I guess we are going to discuss macro expansion in this one then, but very happily for us this time we need to deep dive on the subject, so this thing will become way longer than the previous post was and also way more intense.

Just before we start, if you are new here let me remind you this whole thing is not me being an expert on anything. This is me taking macro expansion seriously for the very first time. I have barely written a scheme macro before. That’s why I am doing this, actually: I want to learn from this, I want to be better at it. ¹

Macro expansion

When I defined the NLnet project, I didn’t pay attention to macros because I believed they were not so relevant. This was a huge mistake, but I was kind of right, too.

It is true I had some knowledge about how to hack inside interpreters but macros are a thing that I never had the chance to think about deeply. It doesn’t help that most of the scripting languages don’t have them, and that most of the “let’s make a scheme” books simply ignore them. I guess I had to do it the hard way. Let’s follow how that looks like.

Scheme interpreters, like many other Lisps, are supposed to work in two kind of independent steps: macro expansion and evaluation.

Macro expansion step runs some pieces of code on top of the code itself and converts it to the basic scheme constructs. Then, the evaluator, that is only aware of the basic scheme constructs, runs the code. This is the beauty of Scheme, the basic constructs are just a few. From the top of my head: lambda, if, define, set! and quote.

This keeps both the macro expander and the evaluator simple and separate. In principle.

So, my goal of making a bytecode interpreter focused on the evaluation step, as that’s the part that is actually affected by the change: the part that actually runs the code.

I thought I could go to the code that was already expanded, convert it to bytecode and change the evaluator so it runs bytecode instead of the AST. But this happened to be a little bit more complex than I thought: in Mes there was no separation between the two steps really, the code was expanded and evaluated as the interpreter processed it.

Splitting the phases

My plan for the compiler was simple: expand the code ahead of time, compile it and then execute that result. The easiest way I found to do this was to untangle the macro expansion step from the evaluation, and that’s mostly what I’ve been working on since, and the reason for this potentially very long blogpost.

Separating expansion and evaluation sounded like the most reasonable thing to do: there are scheme compilers, like Chicken, that compile Scheme code to C, so there must be a way to be able to expand and compile the code ahead of time.

Also, the macro expansion in Mes was written in the infamous eval_apply function described in previous posts, with all the goto magic to make the Garbage Collector and the stack happy, and I didn’t really want to touch that.

So, I started to move the macro expansion to a separate step. The plan goes like this:

1. Reduce the eval_apply function to eval_core, a function that can only evaluate basic Scheme constructs and nothing else.
2. Remove all macro expansion code from Mes.
3. Write a macro expander from scratch that: takes code and returns expanded code, that only uses basic Scheme constructs so eval_core can evaluate it later.

The step 3 is tricky though, applying the macros requires evaluating code, so macros themselves have to be recursively macro expanded to be able to be applied by calling eval_core. Working on the step 1 first makes sure we cannot cheat.

Now, let’s keep our goal in mind and think about bringing some bytecode compilation to the interpreter. Isn’t this process that I just described a little bit like compilation?

If our eval_core is only able to evaluate bytecode, that would force our macro expander return bytecode, instead of expanded code, but the whole thing still applies. We could just add another step to of the proposed architecture and we’ll be ready.

Reading a little bit what Guile does, and remember Mes tries to be Guile-compatible, we see they are even more clever about this: as the macro expander already has to process the code, it’s that step that does some compilation. Clever!

In my very simplistic brain, from an architecture perspective, expansion and compilation are the same thing now. And that’s exactly why I’m doing all this very exhausting thinking.

Side quest: C vs the GC

Now that I knew that I was going to rewrite the macro expander, I needed to be comfortable doing so. That opened a side quest, where I had to wrestle the Garbage Collector so it didn’t destroy my C pointers when eval_core was called and garbage collection was triggered.

That is explained in the previous blogpost of the series.

And yes, I could also write the macro expander in Scheme, but that would make me write very weird scheme at the beginning (remember, no macros!) and I think that wouldn’t help with readability. Also, I feel more comfortable writing C where I have better mutation, a compiler that helps me, a debugger and so on, while in the Scheme side of Mes I would need to rely on eval_core for everything (good luck debugging there), not to mention the speed improvement, which is the main goal of the project.

Macros vs Syntax

Before starting to type I had to know what I was trying to implement and it was also a great moment to think about possible improvements, like the one on the GC.

In modern scheme implementations you are probably used to hygienic macros, define-syntax and all those things. Those are supposed to work with syntax objects, a fancy way to call a piece of code with some metadata attached to it.²

Before people started to wash their hands, scheme did not have that kind of hygienic macros, and it had those classic Lisp macros you can still find in Common Lisp or Clojure. These traditional macros, normally introduced by defmacro, take pieces of code (expressions) as input and manipulate them. There is no metadata attached, and there is chance of infection because of the lack of hygiene.³

GNU Mes tries to be both simple and compatible with Guile, which is a little bit incompatible sometimes, so it implemented plain ol’ macros inside the interpreter and some define-syntax support on top of them in the scheme side.

The basic macro construct in Mes, also available in Guile, is define-macro, which is equivalent to defmacro, but it looks more like a normal scheme define.⁴

They look like this:

;; This is a macro definition
(define-macro (when condition . body)
  `(if ,condition
     (begin ,@body)))

;; This `when` block will be converted to an `if` during expansion
(when (not (= 1 a))
  (display a)
  (newline))

I was confronted with the possibility of writing a fully hygienic macro expander for GNU Mes, and I even tried to make some small proof of concept of it, but I decided it was a better idea to do one change at a time, so I could reuse most of what Mes already has. Once this whole thing works, we could consider moving to something else.

Helper functions

With only that in mind, writing a macro expander is not that complex, so I did that. I always took the simplest path, and waited for the program to ask me for more. That’s how I do most of my coding, actually.

Once a simple macro expander was working, I had to try to make it run the Mes boot file, the file that is run before the user code is called. In there many things are defined, and the environment is set up for the user code to run. The first thing I found there was this:

(define (cond-expand-expander clauses)
  (if (defined? (car (car clauses)))
      (cdr (car clauses))
      (cond-expand-expander (cdr clauses))))

(define-macro (cond-expand . clauses)
  (cons 'begin (cond-expand-expander clauses)))

What should I do now?

Probably you, a very smart person that likes to read sophisticated blog posts, already realized the problem here. The define there is processed at evaluation time, while the macro below is run at expansion time, which is supposed to happen before.

This is a well known issue in Scheme, but there’s no standard way to solve it. Some simple Scheme implementations directly don’t allow helper function usage. Chicken has a define-constant construct that lets you define things that are available at compile time. Guile, instead, has some eval-when thing that lets you run arbitrary code in any combination of expand, load, eval and compile times.

Guile is weird though, because it is able to compile files and run them, but also interpret the files without compiling. This is one of the things I meant when I said being compatible with Guile and simple at the same time is sometimes very hard to achieve.

I decided to make Mes act like Guile but only when it works as a compiler, meaning that would fail to run the cond-expand-expander during the expansion time in the example unless it is wrapped in a proper eval-when that includes the expand condition.

load vs include

Once the very first lines of the boot file work, we encounter the next obstacle in our journey. The file is split in several smaller files that are run using primitive-load.

primitive-load is a procedure of the load family that reads the contents of a file and evaluates them in the top-level environment. But it is a procedure, meaning it is available at evaluation time, which triggered some discomfort in the back of my brain.

I read about how does Chicken work around that and I found it encourages users to use include. From their FAQ:

Why isn’t load properly loading my library of macros?

During compile-time, macros are only available in the source file in which they are defined. Files included via include are considered part of the containing file.

This sounded like an acceptable solution for the moment so I implemented include instead, and replaced the primitive-loads in the boot file by it.

(define-macro (include file)
  ; We don't have `let` yet. I'm sorry for this.
  ((lambda (input-port)
     (set-current-input-port (open-input-file (primitive-eval file)))
     ((lambda (contents)
        (set-current-input-port input-port)
        (cons 'begin contents))
      (read-input-file-env '())))
   (current-input-port)))

See what I told you about weird Scheme code? Maybe I should do something about it…

Now, everything is included in the main boot file, and I don’t have any headaches.

Scoped macros

There is some slight inconvenience, though. The macro expander I made was only dealing with define-macros that appeared in the top-level, but that’s not how Guile does it:

(macroexpand
  '((lambda ()
      (define-macro (f) 10)
      (lambda () (define-macro (f) 11) (f))
      (display (f)))))

; Returns:
; #<tree-il
;    (call (lambda ()
;           (lambda-case ((() #f #f #f () ())
;                         (seq
;                          (lambda ()
;                            (lambda-case ((() #f #f #f () ())
;                              (const 11))))
;                          (call (toplevel display) (const 10)))))))>
; or, in scheme:
; (let () (lambda () 11) (display 10))

This means we need to keep track of the lambdas we encounter when we navigate through the code and create separate scopes for their macros.

I have to admit I was kind of afraid at the beginning but it happens to be easier to implement than I thought. Where I had a hash-map for the macros, I slapped a list on top and made it work as a stack. When the interpreter finds lambda I push a new hash-map to the stack, and when it leaves the lambda I remove it. All new macros are defined in the hash-map that is on the top of the stack. That could be the top-level one (when the stack size is 1) or any other, which are destroyed when the lambdas are left.

Hey! But we need load anyway

At this point I had a beautiful recursive macro expander implementing define-macro style macros. But then I realized I had been kicking all the complexity out of the way just to find it later.

A little bit later in the boot file, the Guile module system, written in Scheme with some help from a C file, is included and it uses primitive-load. Guile modules are mandatory in Mes, there’s no way around them, as they allow us to reuse many things that are written for Guile.

The headache was back. Using include I tried to make a huge compilation unit, compile it, run it and forget, but Scheme has other plans.

Unlucky me, it was worse than I thought. primitive-load, that is run at evaluation time (it’s a procedure) has very interesting behaviour in Guile:

;; a.scm
(eval-when (compile expand)
  (define (f) 10))
(define-macro (m) (f))
(primitive-load "b.scm")

;; b.scm
(display (m))

;; guile a.scm => Displays `10`

But, what the actual fuck?

First of all, m is not in b.scm, and when b.scm is loaded (evaluation time), the m‘s are already processed (expansion time). Even further, the eval-when says the f procedure shouldn’t be available at evaluation time, what is the time when primitive-load is run, isn’t it?

Wait, not so fast.

One way to read this is that primitive-load, or any other load really, reads the file, then expands it, and evaluates it⁵. This means, you can have a full interpreter life-cycle during evaluation, meaning when load is called. So, scheme acts here as a recursive interpreter.

Good. Then, in order to solve the example above we could make some kind of a system that keeps track of the macros that exist in a file and runs them later, when they are needed in the mini expansion time that the load produces. For the f function there we could use closures, making the macros grab the environment when they were defined lets m remember what f was.

This starts to become very tricky because load crosses the boundary between evaluation and expansion time, but it’s manageable. Let’s see another example:

;; a.scm
(eval-when (compile expand)
  (define (f) 10))
(define (f) 1)
(define-macro (m) (f))
(primitive-load "b.scm")

;; b.scm
(display (m))

;; guile a.scm => Displays `1`

Oh…

So maybe the macros need to reference the context where they were created but only use it when the evaluation time lookup fails… This is kind of a reverse-closure situation…

And what about this?

;; a.scm
(eval-when (compile expand)
  (define (f) 10))
(define-macro (b) (f))
(primitive-load "b.scm")
(define-macro (c) 11)

;; b.scm
(display (b))
(display (c))

;; guile a.scm => Displays `1011`

I was expecting the program to fail because c isn’t defined at the point where b.scm is loaded, but thankfully that’s not how it works, as it would require a crazy backtracking mechanism.

All of them couldn’t be bad news, right? This is a huge relief, because it means it’s going to macro expand against all the macros known by the program when the load is called, it doesn’t require to attach them to specific points of the program or anything like that.

Let’s try another:

;; a.scm
(eval-when (compile expand)
  (define (f) 10))
(define-macro (b) (f))
(primitive-load "b.scm")
(define-macro (c) 11)

;; b.scm
(define-macro (d) 12)
(primitive-load "c.scm")

;; c.scm
(display (d))

;; guile a.scm => Displays `12`

So yes, the program knows all the macros when primitive-load is actually called, but they are updated as the program goes. How is this thing done in two steps?

I guess when I load a file, it is expanded to something that also remembers its macros and, when a file is loaded from it, the macros of previously evaluated files are there already, because expanding them means updating some global state that contains all the macros.

The macros on the very first compilation unit are also stored on it somewhere, so they can be merged regardless of when the file was expanded.

And does this whole thing work with scoped macros?

;; a.scm
(eval-when (compile expand eval)
  (define (f)
    (define-macro (b) 10)
    (primitive-load "b.scm"))
  (f))

;; b.scm
(display (b))

;; guile a.scm => Unknown variable `b`

It doesn’t. This would have been too much.

But still, how does this whole thing work?

Breathe

I hope you can feel the spiral my thought process was going through, so I contacted some seasoned schemers I can trust and that made me organize my ideas.

First of all load is not that weird really, it just reads a file from disk, similar to what our include does, and then eval‘s it. It’s eval what is actually weird.

Second, eval is not that hard to implement from the C side: macro_expand and then eval_core. It’s literally the same what we do in our main with the boot file.

The problem is only in the state, and how are the macros and helper functions remembered from one place to another. That is what I was missing, when I got new mail that gave me the most obvious answer I could get, but I didn’t think about: the module system is who takes care of that.

My problem was also my solution.

I had been avoiding the module system entirely since the beginning of the project because it involves some of the registers (M0 and M1) and global state, and that was making me uncomfortable. I didn’t understand it. The C code that deals with modules doesn’t do much, so I was kind of lost with it. What I didn’t think about was the Scheme code had the missing part.

In the boot file Mes includes a modified version of the Guile module system, that makes use of the C side, but most of the functionality is there. It’s like 2kLoC of Scheme, and it’s not that easy to read for me.

I decided to start trusting the module system, using it for the top-level lookups. The case when my stack of hash-maps has a size of 1, that is. And most of the thing started to work, magically, once a very simple primitive-load was added to the interpreter.

As modules are global, it’s very easy to add a primitive-load (or an eval) that “just works”. Take the file (or the expression in the case of eval), expand it, wrap it in a begin, and then run eval_core on it. As all the interpreter and the macro expansion is (now) designed to use the module system for the lookups, most of it just works and all the cases introduced in the previous block behave exactly like Guile does.

Most of it

Saying most of it means some of it doesn’t work.

Yet.

The macro expansion works as-is right now, and some of the evaluation happens, but I’m having issues with some specific file which is trying to apply a #f. Also, I don’t know which change triggered it, but the evaluator now has some infinite recursion when trying to report an error, which makes the debugging a little bit harder.

I believe I will fix it soonish, but there are still questions I need to answer and things I need to review.

Next

The first obvious question is if I’ll manage to make the interpreter run the whole boot file and actually run some Mes user code. I have to believe I will, if I didn’t, none of this would make any sense.

The second and more relevant question talks directly to the module system and the compilation step that we very conveniently forgot about with the excuse that it should be very similar to what we are doing right now. The current module system is running as the interpreter goes, loading things in expansion time and evaluation time when needed, in the very same interpreter run, with all the state in the memory. If we plan to compile things, we could also take a look to how to do that ahead of time, like Guile can do, and we should be able to store those compiled files somewhere, in a way that they can be loaded later, with all the module information intact. That’s how the Guile .go files work, but I’m not even remotely motivated to write an ELF representation for the Mes modules that is compatible with Guile’s. Maybe we could use Guile’s ELF modules for it, but also that might be too much for a simple Scheme implementation like Mes.

If we don’t do the ahead of time compilation, and let everything be in the memory, we still need a way to represent our compiled code in a way that is compatible with the module system. In this very moment that is extremely easy to do because my compiled expanded code is valid Scheme code, still. There is no way that doesn’t work perfectly with the module system. When we move to a compiled solution what should we do?

Thinking out loud, I have some different possibilities. The first one is to represent the bytecode in a Scheme vector (or bytevector), that would let me store it in the module system as-is but run with an evaluator that is only capable of running bytecode. That could do it, but I would need to have separate pieces of bytecode hanging in the module system, instead of a huge piece of bytecode I can feed the evaluator with, which was my idea since the beginning.

I need to think about it, and read what Guile does, but from what I have already read, I anticipate it won’t be that easy to understand.

The rest of it, for the moment, are not-very-concerning concerns like taking care of M2-Planet compatibility of my code, rethinking a little bit the API my macro expander provides, making sure all the eval-when‘s I had to add to the boot file make sense and so on. But I’ll try not to bother my subconscious self with things that have easy solutions. I need to learn to focus in the good things.

The good things

The most interesting thing is the design of this ugly macro expander, that works pretty cleanly with some C recursion that looks more like Scheme than the old eval_apply based one did. It is so clean that it feels like I’m missing something very important that is going to make the code fall apart.

Yeah, yeah, yeah, I hear you: the good things.

I removed a lot of code from the eval_apply function, meaning I removed many cases that had to be handled for expansion, and some functions too. This makes the evaluator smaller: the new eval_core function is only 385LoC, versus the 611LoC of the previous one, which also made the if chain in the top proportionally shorter, which should slightly improve evaluator’s performance. Having already digested everything during expansion gives you this things.

Of course, there’s new code now, that replaces that functionality, but I believe it’s a little bit easier to follow, as it is way more flat, and described in simple terms. Judge by yourselves:

struct scm *
macro_expand_expr (struct scm *macros, struct scm *exp, char level)
{
  /* This is a recursive macro expander. Arguments:
   * - `macros` are the available local macros in the current expansion.
   * - `exp` is the sub-tree we are working with.
   * - `level` keeps track of how deep we are in code. It serves as a way to
   *   catch `define-macro`s that don't happen in the top-level. Remove me
   *   maybe?
   */
  if (exp->type != TPAIR || exp->car == cell_symbol_quote)
    return exp;
  if (exp->car == cell_symbol_define_macro)
    {
      assert_msg (level == 0, "Syntax error: `define-macro` must be in top-level");
      expand_define_ (exp);

      gc_preserve (&exp);
      gc_preserve (&macros);
      exp->cdr->cdr = macro_expand_expr (macros, exp->cdr->cdr, level);
      gc_release (2); /* exp, macros */
      struct scm *name = exp->cdr->car;
      struct scm *lambda = exp->cdr->cdr->car;
      register_macro (macros, name, lambda);
      exp = cell_unspecified; /* Eat the macro */
      return exp;
    }
  if (exp->car == cell_symbol_eval_when)
    {
      /*
       * (eval-when (expand compile load eval) ...)
       */
      char eval_when = eval_when_ (exp->cdr->car);
      /* TODO: The expansion will read the macro expansions regardless if they
       * are set not to be evaluated during expansion time.
       * But macro definitions are supposed to be always there for expansion
       * time. Check me just in case.
       */
      gc_preserve (&exp);
      gc_preserve (&macros);
      exp = macro_expand_expr (macros, cons (cell_symbol_begin, exp->cdr->cdr),
                               level);
      gc_release (2); /* exp, macros */
      if ((eval_when & EVAL_WHEN_EXPAND) == 1)
        {
          gc_preserve (&exp);
          gc_preserve (&macros);
          macro_eval (exp);
          gc_release (2); /* exp, macros */
        }
      if ((eval_when & EVAL_WHEN_EVAL) == 0)
        exp = cell_unspecified; /* Eat the body for the next step */
      /* TODO else ...?
       *  When we are using this macro expander for compilation, we should
       *  check other cases. Also the load case is an interesting one.
       */
      return exp;
    }
  if (exp->car == cell_symbol_define)
    {
      if (exp->cdr->car->type == TPAIR) /* Procedure declaration */
        expand_define_ (exp);
      gc_preserve (&exp);
      gc_preserve (&macros);
      exp->cdr->cdr = macro_expand_expr (macros, exp->cdr->cdr, level);
      gc_release (2); /* exp, macros */
      return exp;
    }

  if (exp->car == cell_symbol_lambda)
    {
      gc_preserve (&exp);
      gc_preserve (&macros);
      exp->cdr->cdr = macro_expand_expr (macros_push_scope (macros), exp->cdr->cdr, 0);
      /* Level is back to 0 because we can define macros in lambda's top-level */
      gc_release (2); /* exp, macros */
      return exp;
    }

  struct scm *macro = get_macro (macros, exp->car);
  if (macro != cell_f)
    {
      /* It's a macro call -> expand.
       * In our world, apply the lambda that represents the macro body with the
       * exp as arguments.
       */
      gc_preserve (&macros);
      gc_preserve (&exp);
      exp = macro_apply (cons (macro, exp->cdr));
      gc_release (1); /* exp */
      gc_preserve (&exp);
      exp = macro_expand_expr (macros, exp, level); /* Re-expand the result */
      gc_release (2); /* exp, macros */
      return exp;
    }

  if (exp->type == TPAIR)
    {
      /* Any other form, just expand the list element by element */
      struct scm *tmp = exp;
      gc_preserve (&tmp);
      /* Start with the `car` just in case it expands to a `begin` */
      gc_preserve (&exp);
      gc_preserve (&macros);
      exp->car = macro_expand_expr (macros, exp->car, level);
      gc_release (2); /* exp, macros */

      /* The (begin ...) case shouldn't increase the level */
      if (exp->car != cell_symbol_begin)
        level++;

      exp = exp->cdr;
      while (exp != cell_nil)
        {
          if (exp->type == TPAIR)
            {
              gc_preserve (&exp);
              gc_preserve (&macros);
              exp->car = macro_expand_expr (macros, exp->car, level);
              gc_release (2); /* exp, macros */
              exp = exp->cdr;
            }
          else /* Last element in an improper list */
            {
              gc_preserve (&exp);
              gc_preserve (&macros);
              exp = macro_expand_expr (macros, exp, level);
              gc_release (2); /* exp, macros */
              break;
            }
        }
      gc_release (1); /* tmp */
      exp = tmp;
      return exp;
    }
}

The full code is publicly available, bugs included.

I tried to write it in a way that is easy to move to separate functions, and that doesn’t rely on previous constructs like the weird R0, R1, R2 and R3 registers directly, and most of the cleanup is done by the garbage collector. I need to review it a little more, but I believe it’s readable.

Apart from all that, of course, I have learned a lot and read many papers that I won’t use for this project, but the personal development is still there I guess.

It has been a wild run, and I’m not yet in the finish line.

Actually, we barely started.

I’ll keep you posted when it finally works, and we’ll see if we can actually start compiling something.