Title: GNU Mes and macro expansion Date: 2025-10-02 Category: Tags: GNU Mes interpreter speedup Slug: fasterMes3 Lang: en Summary: How does the GNU Mes macro expansion work and why is that important to understand. 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. [^method] [^method]: We could even discuss my methods another time. I tend not to read much about things but *think* about them (what a revolutionary idea!). This oftentimes makes me do things in a non-optimal way, or reinvent things that were already invented by others before. Then I read a little bit more and think again. ### 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][prev] of the series. [prev]: {filename}02_garbage_collector.md 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.[^metadata] [^metadata]: Like line numbers and all those things that help a lot but we don't think about until the end. 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*.[^fernando] [^fernando]: Use a mask, stay at home if you are sick, and also remember not to eat almonds before talking in public. That's what we have learned since. 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`.[^more-defmacro] [^more-defmacro]: Guile's documentation has a section about them both: They look like this: ``` scheme ;; 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: ``` scheme (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`][eval-when] thing that lets you run arbitrary code in any combination of `expand`, `load`, `eval` and `compile` times. [eval-when]: https://www.gnu.org/software/guile/manual/html_node/Eval-When.html 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-load`s in the boot file by it. ``` scheme (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-macro`s that appeared in the top-level, but that's not how Guile does it: ``` scheme (macroexpand '((lambda () (define-macro (f) 10) (lambda () (define-macro (f) 11) (f)) (display (f))))) ; Returns: ; # ; or, in scheme: ; (let () (lambda () 11) (display 10)) ``` This means we need to keep track of the `lambda`s 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 `lambda`s 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: ``` scheme ;; 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[^eval]. 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. [^eval]: Expanding and then evaluating is actually what `eval` does, which is also needed. We killed it when we moved to `eval_core`, but we need to bring it back. 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: ``` scheme ;; 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? ``` scheme ;; 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: ``` scheme ;; 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? ``` scheme ;; 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 `load`ed 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:
Click here to expand a slightly cleaned up version of the core of the macro expander ``` clike 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 (¯os); 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 (¯os); 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 (¯os); 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 (¯os); 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 (¯os); 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 (¯os); 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 (¯os); 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 (¯os); 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 (¯os); 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][github]. [github]: https://github.com/ekaitz-zarraga/mes 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.