fasterMes: 03: Macro expansion.

1 files changed, 757 insertions, 0 deletions

diff --git a/content/fasterMes/03_macro_expander.md b/content/fasterMes/03_macro_expander.md
new file mode 100644
index 0000000..108f8ad
--- /dev/null
+++ b/content/fasterMes/03_macro_expander.md
@@ -0,0 +1,757 @@
+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:
+<https://www.gnu.org/software/guile/manual/html_node/Defmacros.html>
+
+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:
+; #<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 `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 <del>compiled</del> *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:
+
+<details>
+<summary>Click here to expand a slightly cleaned up version of the core of the
+macro expander</summary>
+
+``` 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 (&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;
+    }
+}
+```
+</details>
+
+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.