Macros and optimizations: it's just a phase

2024-06-23 21:41

This post builds upon the previous one where I built the smallest OOP language I could based only on message dispatch. Everything is as late bound as possible, even the language semantics, the core only has basic data types, a call stack and logic for message dispatch.

In the previous post I implemented the semantics for evaluating expressions with enough message handlers to show arithmetic operations and binding lookups, here we are going to show that those semantics are not special, they can be just a phase in a sequence of phases that evaluate the same expression tree using different semantics.

To show an example of this, in this post I'm going to add two phases before what we will now call the run phase:

macro phase: it quotes the right thing ™️ (if not already quoted) in reply handler definitions, name bindings and implements support for short circuit boolean operators by quoting the right hand side. When this phase is present the programmer doesn't have to quote anything.
opt phase: it applies some basic optimizations like evaluating constant sub expressions, removing unnecessary wraps and so on.

But an important idea here is that the fixed "compile time" and "runtime" phases in most programming languages is an arbitrary restriction and we can have as many "times" as we want.

Note that the macros and optimizations implemented here assume semantics from the run phase, since the language core has no semantics, only message dispatch, there can be many implementations of semantics for the run phase, this means that any phase that comes before assumes it's running in a sequence of phases that share the same language semantics.

In a less abstract way, the new phases assume name binding and lookup; arithmetic, comparison, boolean operations and conditionals behave as you would expect, which is what's implemented in the current run phase.

The macro phase assumes that replies and is have a specific meaning, that and and or are short circuit boolean operations, otherwise the wrapping it does makes no sense. Also that ints, floats and strings evaluate to themselves with no side effects.

The opt phase assumes arithmetic, comparison and boolean operations work as expected, otherwise it can't replace them with their result.

The key take away from this post and one of the objectives of this language is to show that you can not only play with language semantics by implementing your own run phase, but also to add as many extra phases as you want.

Nothing special about this phases, they run with the following code:

function main(code) {
  console.log("> ", code);
  console.log("");

  const eToStr = bindReplies(mergeToStr({})).right();
  runPhases(
    code,
    [
      { name: "macro", e: macroPhase().right() },
      { name: "opt", e: optPhase().right() },
      { name: "run", e: runPhase().right() },
    ],
    ({ name }, input, output) => {
      console.log("#  ", name);
      console.log("in ", toStr(input, eToStr));
      console.log("out", toStr(output, eToStr));
      console.log("");
    },
  );
}

You can see the array as a second argument to runPhases, just replace them with your own and have fun!

Before starting I want to note that all the code in this post is based on the following commit: 7302325, the code in the repo may change in the future and not work the same way as in this post.

Also notice that the modules here import from fatter.js instead of fatt.js, the only difference is that fatter.js has better error handling and an extra method in Frame: getSendHandler.

We are going to see examples and explain what happens on each phase, all examples are going to look like this:

>  1 + 2

#   macro
in  1 + 2
out 1 + 2

#   opt
in  1 + 2
out 3

#   run
in  3
out 3

The first line is the input, then for each phase you will see the name of the phase in the first line (macro, opt, run) then the input to the phase (in) followed by the output (out).

In the example above the macro does nothing:

#   macro
in  1 + 2
out 1 + 2

The opt phase evaluates 1 + 2 since it's a constant message send:

#   opt
in  1 + 2
out 3

The run phase gets 3 as input which evaluates as itself.

#   run
in  3
out 3

Below the same example for floats:

>  1.5 + 1.2

#   macro
in  1.5 + 1.2
out 1.5 + 1.2

#   opt
in  1.5 + 1.2
out 2.7

#   run
in  2.7
out 2.7

The optimization for both Int and Float is the same, we define reply handlers for all arithmetic and comparison operations in the opt phase using cBinOp and cCompOp helpers:

    "+": cBinOp((a, b) => a + b),
    "-": cBinOp((a, b) => a - b),
    "*": cBinOp((a, b) => a * b),
    "/": cBinOp((a, b) => a / b),
    "=": cCompOp((a, b) => a === b),
    "!=": cCompOp((a, b) => a !== b),
    ">": cCompOp((a, b) => a > b),
    ">=": cCompOp((a, b) => a >= b),
    "<": cCompOp((a, b) => a < b),
    "<=": cCompOp((a, b) => a <= b),

The helpers do almost the same thing:

  function cBinOp(fn) {
    return (s, m) => {
      if (typeof m.obj === typeof s) {
        return fn(s, m.obj);
      } else {
        return new Send(s, m);
      }
    };
  }

  function cCompOp(fn) {
    return (s, m) => {
      if (typeof m.obj === typeof s) {
        return fn(s, m.obj) ? s : NIL;
      } else {
        return new Send(s, m);
      }
    };
  }

cBinOp checks if the subject and the message object are of the same type (which will be the type of the type handling the message) and if so it calls fn with both.

If they are not of the same type (for example in the expression 1 + a) it returns the original message Send, but notice that since this phase, like a normal "run" phase, evaluates the subject and message before calling the handler, it means that both subject and object are going to be potentially optimized before the new Send(s, m) is constructed.

This also means that if an optimization happened on the subject or object that turned them into constants this one will optimize the constant expression even further.

For example, the expression 1 + 2 + 4 is two chained message sends: (1 + 2) + 4:

evals the first send (1 + 2)
- which evals the subject 1
- and the object 2
- calls the handler for the verb + since its defined in the opt phase with 1 as subject and 2 as object
- this returns 3 since the expression is constant
with 3 as the result it sends + 4 to it
- which evals the subject 3
- and the object 4
- calls the handler for the verb + with 3 as subject and 4 as object
- this returns 7 since the expression is constant

In this language comparisons return () if the comparison is "false" but return the subject if "true":

>  1 > 2

#   macro
in  1 > 2
out 1 > 2

#   opt
in  1 > 2
out ()

#   run
in  ()
out ()

This allows chaining of comparisons:

>  1 < 2 < 3

#   macro
in  1 < 2 < 3
out 1 < 2 < 3

#   opt
in  1 < 2 < 3
out 1

#   run
in  1
out 1

>  3 > 2 > 1

#   macro
in  3 > 2 > 1
out 3 > 2 > 1

#   opt
in  3 > 2 > 1
out 3

#   run
in  3
out 3

>  1 > 3 < 2

#   macro
in  1 > 3 < 2
out 1 > 3 < 2

#   opt
in  1 > 3 < 2
out ()

#   run
in  ()
out ()

By having the following replies for comparison operations on Nil in the optimization phase:

    ">": () => NIL,
    ">=": () => NIL,
    "<": () => NIL,
    "<=": () => NIL,

The same optimization works for strings:

>  "hello " + "joe"

#   macro
in  "hello " + "joe"
out "hello " + "joe"

#   opt
in  "hello " + "joe"
out "hello joe"

#   run
in  "hello joe"
out "hello joe"

But only implemented for the + message:

    "+": cBinOp((a, b) => a + b),

In the next example we can see that the optimization works even when the addition is a value inside a Pair:

>  (1 + 2) : 3

#   macro
in  (1 + 2) : 3
out (1 + 2) : 3

#   opt
in  (1 + 2) : 3
out 3 : 3

#   run
in  3 : 3
out 3 : 3

That's because eval for Pair in the opt phase is:

  eval: (s, _, e) => new Pair(e.eval(s.a), e.eval(s.b))

Which comes from the merge with the ident phase, it evaluates both sides of the Pair and returns a new Pair with them.

It also works inside Later:

>  @ (1 + 2)

#   macro
in  @(1 + 2)
out @(1 + 2)

#   opt
in  @(1 + 2)
out 3

#   run
in  3
out 3

The opt phase not only evaluates 1 + 2 but also unwraps the Later since it's unnecesary for a constant expression.

eval for Later in the opt phase is:

  eval(s, _, e) {
    const v = e.eval(s.value);
    return isConstantExpr(v) ? v : new Later(v);
  },

You should start to see a pattern already, the opt phase is similar to the run phase but it only evaluates an expression if it can optimize it, if not it returns the original. Like run it also walks the whole expression "tree" until the "leafs".

For Msg's obj:

>  {@foo is (1 + 42), foo}

#   macro
in  {@(foo) is (1 + 42), foo}
out {@(foo) is (1 + 42), foo}

#   opt
in  {@(foo) is (1 + 42), foo}
out {@(foo) is 43, foo}

#   run
in  {@(foo) is 43, foo}
out 43

and

>  (0 add+1 (0 + 2)) replies (0 + 1 + it + that)

#   macro
in  0 add+1 (0 + 2) replies (0 + 1 + it + that)
out @(0 add+1 (0 + 2)) replies @(0 + 1 + it + that)

#   opt
in  @(0 add+1 (0 + 2)) replies @(0 + 1 + it + that)
out @(0 add+1 2) replies @(1 + it + that)

#   run
in  @(0 add+1 2) replies @(1 + it + that)
out ()

Here the opt phase optimized 0 + 2 and 0 + 1 but also wraps the subject and object of the replies message, this is because replies has a handler in the macro phase:

  // no need to eval here since we were called by send
  replies: (s, m) =>
    new Send(new Later(s), new Msg(m.verb, new Later(m.obj)))

eval for Send in the opt phase is:

  eval: (s, _m, e) => {
    const subj = e.eval(s.subj),
      msg = e.eval(s.msg);
    if (e.getSendHandler(subj, msg)) {
      return e.send(subj, msg);
    } else {
      return new Send(subj, msg);
    }
  }

This one is a little more interesting, it first evaluates the subject and message and then checks if there's a handler for the message, if there is, it evaluates the message send and returns the result, if there's no message handler it builds a new send with the the evaluated subj and msg.

This is a big difference between this two phases and the run phase, this ones leave the send as it was if they don't know what to do with it, the run phase raises an error in that case.

Another way of seeing it is that this phases evaluate what they know how to handle and leave the rest "as is". More specifically, the macro phase expands what it knows how to expand and the optimization phase reduces what it knows how to reduce.

Optimizations inside Block:

>  {1 + 2, 42, ()}

#   macro
in  {1 + 2, 42, ()}
out {1 + 2, 42, ()}

#   opt
in  {1 + 2, 42, ()}
out {3, 42, ()}

#   run
in  {3, 42, ()}
out ()

Because eval for Block in the opt phase is:

  eval: (s, _m, e) => new Block(s.value.map((item) => e.eval(item)))

The difference between eval in the opt phase and the run phase is that in the run phase it evals every item but returns the result of the last one.

In the opt phase it evals all items and returns a new Block with the evaluated items.

The eval implementation for Block in the opt phase is almost the same as the eval implementation for Array in the run phase, the only difference is that the collection is different for each.

We could do a further optimization where if all items but the last are side effect free we could return the last one because we know it won't make a difference in semantics.

A similar optimization would be to filter all Block items that are constant expressions, since their evaluation doesn't affect the result, followed by a check to see if the resulting block has one item, in that case we don't wrap it back in a Block, if the result is an empty block we return () which is the result of evaluating an empty Block.

Another optimization is to pre evaluate conditional expressions where the condition is a constant, if it's Nil we can replace it with the optimization of the second item in the Pair:

>  () ? 1 : 2

#   macro
in  () ? 1 : 2
out () ? @(1 : 2)

#   opt
in  () ? @(1 : 2)
out 2

#   run
in  2
out 2

Nil has this handler for ?:

  "?": ternaryFalse

The other constants (Int, Float, Str) have this one:

  "?": ternaryTrue

Why those 3 and not all others? after all the only falsy value is Nil...

It's the same thing we talked about in the Block optimization, we should check that all other truthy expressions are side effect free if we want to optimize them out and keep the same semantics, something doable but not done here.

Notice that the macro phase did something too:

#   macro
in  () ? 1 : 2
out () ? @(1 : 2)

It noticed that the "body" of the conditional was not "quoted" with Later and it wrapped it with a @, here's the reply for ? in all types in the macro phase:

  "?": ternaryWrap

And the implementation of ternaryWrap:

  const ternaryWrap = (s, m, _e) =>
    new Send(s, new Msg(m.verb, pairToLaterOrLaterPair(m.obj)));

But it does more than just wrapping it if it's not a Later already:

function pairToLaterOrLaterPair(v) {
  if (v instanceof Pair) {
    return new Later(v);
  } else if (v instanceof Later) {
    if (v.value instanceof Pair) {
      return v;
    } else {
      console.error(
        "Expected pair or later of pair, got later of",
        getType(v.value),
        "fixing",
      );
      return new Later(new Pair(v.value, NIL));
    }
  } else {
    console.error("Expected pair or later of pair, got", getType(v), "fixing");
    return new Later(new Pair(v, NIL));
  }
}

It wraps a Pair and forces it to be a Pair if it's not one even if it's already wrapped in a Later.

This fixing could be its own phase, like eslint --fix.

An example showing the case for truthy values:

>  42 ? 1 : 2

#   macro
in  42 ? 1 : 2
out 42 ? @(1 : 2)

#   opt
in  42 ? @(1 : 2)
out 1

#   run
in  1
out 1

A "fix and wrap":

>  {@a is 1, a ? 1}

#   macro
in  {@(a) is 1, a ? 1}
out {@(a) is 1, a ? @(1 : ())}

#   opt
in  {@(a) is 1, a ? @(1 : ())}
out {@(a) is 1, a ? @(1 : ())}

#   run
in  {@(a) is 1, a ? @(1 : ())}
out 1

A "fix" in an already wrapped body:

>  {@a is 1, a ? @ 1}

#   macro
in  {@(a) is 1, a ? @(1)}
out {@(a) is 1, a ? @(1 : ())}

#   opt
in  {@(a) is 1, a ? @(1 : ())}
out {@(a) is 1, a ? @(1 : ())}

#   run
in  {@(a) is 1, a ? @(1 : ())}
out 1

The next examples shows macro and opt phase handling of short circuit boolean operations and and or:

>  () and 1

#   macro
in  () and 1
out () and @(1)

#   opt
in  () and @(1)
out ()

#   run
in  ()
out ()

The macro phase wraps the right hand side of boolean operations to make them "short circuit"

With the following reply handlers for both in all types:

  and: andWrap,
  or: orWrap,

The implementations of andWrap and orWrap are the same:

  function lazyRhs(s, m, _e) {
    return new Send(s, new Msg(m.verb, maybeWrapLater(m.obj)));
  }

  const andWrap = lazyRhs,
    orWrap = lazyRhs;

The optimization phase works similarly to the optimization for arithmetic and comparison operations, it evaluates the send expression if the subject is a constant and it's enough to know what to do with the operation:

For truthy constant values the reply handler is:

    and: trueAnd,
    or: trueOr,

With the implementations of trueAnd and trueOr being:

function maybeUnwrapLater(v) {
  return v instanceof Later ? v.value : v;
}

function trueAnd(_s, m, _e) {
  return maybeUnwrapLater(m.obj);
}

function trueOr(s) {
  return s;
}

This means that if the subject is true for and it returns the right side unwrapped if it's a Later.

If the subject is true for or it returns it directly, no need to evaluate the right hand side.

The optimization that applies here is the unwrapping of the right hand side if it's inside a Later which allows the next optimization to apply, which evaluates constant expressions, more examples:

>  1 or 2 and 3

#   macro
in  1 or 2 and 3
out 1 or @(2) and @(3)

#   opt
in  1 or @(2) and @(3)
out 3

#   run
in  3
out 3

>  () or 2 and 3

#   macro
in  () or 2 and 3
out () or @(2) and @(3)

#   opt
in  () or @(2) and @(3)
out 3

#   run
in  3
out 3

>  () or 2 or 3

#   macro
in  () or 2 or 3
out () or @(2) or @(3)

#   opt
in  () or @(2) or @(3)
out 2

#   run
in  2
out 2

Now let's see another combination of macro and optimization phase:

>  {@a is 1, a and (1 + 2 + a) or (a * 3)}

#   macro
in  {@(a) is 1, a and (1 + 2 + a) or (a * 3)}
out {@(a) is 1, a and @(1 + 2 + a) or @(a * 3)}

#   opt
in  {@(a) is 1, a and @(1 + 2 + a) or @(a * 3)}
out {@(a) is 1, a and @(3 + a) or @(a * 3)}

Here the macro phase quotes the Name in an is expression, short circuits the boolean operations and optimizes constant arithmetic expressions.

The reply handler for the message is in Name in the macro phase is:

  is: (s, m, _e) => new Send(new Later(s), m)

This last example should show you how optimizations compose because the evaluation order on all phases follows the evaluation order of the final run phase.

While there may be further optimizations it's interesting to note that both the macro and opt phases shown above are ~230 lines of code.

Some closing notes on the idea:

These two phases can either run "just in time" before run on each execution or they can be run once at "build time" and the result of the last one stored as the "optimized build".
There's no "Abstract Syntax Tree" and there are no "Intermediate Representations"
- The "tree" is just a composition of the runtime value types
- Each phase takes that "tree" as input and produces the same or a modification as output, all types in all phases are the same types the programmer uses.
- 💁 is this 🦋 homoiconic?
There's an extra phase used in this post, did you notice it? to convert the inputs and outputs for each phase to string we run a phase that takes an expression as input and returns a string as output.

Mariano Guerra's Log