In the previous posts: Make Your Self and Macros and optimizations: it's just a phase I described the design and implementation of a minimal object oriented language with the implementation done in JavaScript.

When we design our language on top of a high level language we may reuse accidentally or on purpose a lot of the host language semantics and make it hard to tell if our design is our own or we are just an alternative syntax on top of the host language.

To make sure the design is sound, to show an alternative way of implementing the language and to get a nice native JIT interpreter I did what anybody would do.

I implemented an interpreter on top of rpython, the toolchain that allows pypy to be a really fast Python interpreter implemented in "Python".

Before you say "you are trying to avoid the problem of using a high level language like JavaScript by using Python?", the quotes around Python are because the language used to implement the interpreter is a restricted subset of Python called rpython, short for "restricted python" which defines itself as: "RPython is everything that our translation toolchain can accept". In the end rpython is a language that looks like a subset of python but restricts programs written with it to be statically typed, it's just that all the types are inferred, you can read more about the restrictions here: RPython Language.

The implementations is in the mclulang/pypyfatt folder, follow the instructions in the readme if you want to build it yourself, if you want to believe me, it does everything fatt.cli.js does, the parsers may have some corner cases between them but I will fix them as I see them.

I came for the meta-tracing JIT compiler, I stayed for the fractals

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.

In Search of Maxwell's equations of Object Oriented Software

Motivation

Yes, that was the big revelation to me when I was in graduate school—when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were “Maxwell’s Equations of Software!” This is the whole world of programming in a few lines that I can put my hand over.

-- A Conversation with Alan Kay

Which are Maxwell's equations of Object Oriented software?

This is an attempt at answering that question based on the following:

OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.

-- Dr. Alan Kay on the Meaning of “Object-Oriented Programming”

I think our confusion with objects is the problem that in our Western culture, we have a language that has very hard nouns and verbs in it. Our process words stink. It's much easier for us when we think of an object—and I have apologized profusely over the last twenty years for making up the term object-oriented, because as soon as it started to be misapplied, I realized that I should have used a much more process-oriented term for it.—The Japanese have an interesting word, which is called ma. Spelled in English, just ma. Ma is the stuff in-between what we call objects. It's the stuff we don't see, because we're focused on the nounness of things rather than the processness of things. Japanese has a more process-feel oriented way of looking at how things relate to each other. You can always tell that by looking at the size of [the] word it takes to express something that is important. Ma is very short. We have to use words like interstitial or worse to approximate what the Japanese are talking about.

-- Alan Kay at OOPSLA 1997: The Computer Revolution has not Happened Yet

Don't Bury the Lede

At the end of this post you will understand the design and code that allows you to write and understand why this:

{
  @MyType is ("my-type" as-type ()),
  @name is "Joe",
  MyType apply-to name,
  @(name say-hello ()) replies @("Well, hello " + it),
  (name say-hello ()) : ("Mike" say-hello ())
}

Evaluates to:

"Well, hello Joe" : "Hello, Mike!"

With a runtime that consists of a Frame class that allows to bind values to names and find the value for a given name plus this two methods:

class Frame {
    // ...
    eval(v) {
      return this.send(v, new Msg("eval", this));
    }
    send(s, m) {
      return this.find(getType(s))
        .find(m.verb)
        .call(null, s, m, this);
    }
    // ...
}

And the following data types as the smallest set to make it all work:

• Nil: similar to nil, null or Unit, the only falsy value
• Int: Javascript's BigInt
• Name: a variable name
• Pair: a pair of values, like cons
• Msg: similar to a method, a name and an argument
• Send: like a method call, a method sent to a value
• Later: like Lisp's quote
• Block: like Lisp's progn, a sequence of instructions that returns the result of the last one
• Symbol: Javascript's Symbol

A runnable version of this post can be found here: fatt.test.js (fatt: frame all the things)

A full implementation of the language with extra support for Array and Map in 100 lines for the runtime and 73 lines for the parser can be found here fatt.js.

A CLI to evaluate expressions can be found here fatt.cli.js, here are some expressions you can evaluate and their results:

./fatt.cli.js '42' '10 + 2' '10 + 2 - 5 * 2' '1 : 2.5 : () : "hi"' '() ? @ "true" : "false"' '\ + 2' '@(1 + 2)' '[]' '[1, 1.4, ["hi", ()]]' '"my-type" as-type ()' '@{42, ()}' '#{1: "one", "two": 2}' '#{} . "foo"' '#{"foo": "bar"} . "foo"' '{@foo is 42, foo}' '{@(0 add+1 0) replies @(it + that + 1), 1 add+1 2}'

>  42
42

>  10 + 2
12

>  10 + 2 - 5 * 2
14

>  1 : 2.5 : () : "hi"
1 : 2.5 : () : "hi"

>  () ? @ "true" : "false"
"false"

>  \ + 2
\ + 2

>  @(1 + 2)
1 + 2

>  []
[]

>  [1, 1.4, ["hi", ()]]
[1, 1.4, ["hi", ()]]

>  "my-type" as-type ()
("my-type" as-type ())

>  @{42, ()}
{42, ()}

>  #{1: "one", "two": 2}
#{1: "one", "two": 2}

>  #{} . "foo"
()

>  #{"foo": "bar"} . "foo"
"bar"

>  {@foo is 42, foo}
42

>  {@(0 add+1 0) replies @(it + that + 1), 1 add+1 2}
4

Bindings

If we had a calculator language and wanted to upgrade it to make it closer to a programming language probably the first feature would be the ability to give names to values and look them up later.

In programming languages bindings are stored in Frames in a call stack, let's try a simple example in JavaScript:

{
  let a = 10;
  let b = 20;

  test("single scope bindings", () => {
    expect(a).toBe(10);
    expect(b).toBe(20);
  });
}

Let's start with a simple Frame class that holds bindings in a Map and has two operations:

• bind(name, value): store a value associated to a name
• find(name): return the value associated with a name or undefined if not found

{
  class Frame {
    constructor() {
      this.binds = new Map();
    }

    bind(name, value) {
      this.binds.set(name, value);
      return this;
    }

    find(name) {
      return this.binds.get(name);
    }
  }

  test("single scope bindings implementation", () => {
    const env = new Frame().bind("a", 10).bind("b", 20);
    expect(env.find("a")).toBe(10);
    expect(env.find("b")).toBe(20);
  });
}

But in most languages bindings are not all in a single global namespace, in languages like JavaScript binding lookup starts in the current scope and continues in outer scopes:

{
  let a = 10;
  let b = 20;

  {
    let b = 30;

    test("nested scopes", () => {
      expect(a).toBe(10);
      expect(b).toBe(30);
    });
  }
}

To replicate this our new implementation of Frame gains a new attribute: up.

find starts in the current scope and if the binding is not found it continues in the scope referenced by up until the binding is found or up is null.

The method down enters a new Frame with its up attribute set to the current instance.

{
  class Frame {
    constructor(up = null) {
      this.up = up;
      this.binds = new Map();
    }

    bind(name, value) {
      this.binds.set(name, value);
      return this;
    }

    find(name) {
      const v = this.binds.get(name);
      if (v === undefined && this.up !== null) {
        return this.up.find(name);
      } else {
        return v;
      }
    }

    down() {
      return new Frame(this);
    }
  }

  test("nested scopes implementation", () => {
    const env = new Frame()
                  .bind("a", 10).bind("b", 20)
                  .down().bind("b", 30);

    expect(env.find("a")).toBe(10);
    expect(env.find("b")).toBe(30);
  });
}

But binding lookup stops for a second reason other than up being null, let's see it with an example:

{
  function f1() {
    let a = 10;
    let b = 20;
    f2();
  }

  function f2() {
    let b = 30;
    return a + b;
  }

  test("call frames", () => {
    expect(f1).toThrow();
  });
}

a is not available in f2 even if it was called from f1 where it was defined, this is because binding lookup stops at call frames.

We can implement this by adding a marker attribute upLimit that makes the lookup stop:

{
  class Frame {
    constructor(up = null) {
      this.up = up;
      this.upLimit = false;
      this.binds = new Map();
    }

    bind(name, value) {
      this.binds.set(name, value);
      return this;
    }

    find(name) {
      const v = this.binds.get(name);
      if (v === undefined) {
        if (this.upLimit || this.up === null) {
          return v;
        } else {
          return this.up.find(name);
        }
      } else {
        return v;
      }
    }

    down() {
      return new Frame(this.left, this);
    }

    setUpLimit() {
      this.upLimit = true;
      return this;
    }
  }

And test it:

  test("call frames implementation", () => {
    const env = new Frame()
      .bind("a", 10)
      .bind("b", 20)
      .down()
      .setUpLimit()
      .bind("b", 30);

    expect(env.find("a")).toBe(undefined);
    expect(env.find("b")).toBe(30);
  });
}

Even when binding lookup stops at the first call frame boundary there are two simple examples showing that the lookup continues "somewhere else":

{
  let a = 10;

  function f() {
    return a;
  }

  test("top level and prelude bindings", () => {
    expect(f()).toBe(10);
    expect(parseInt("42", 10)).toBe(42);
  });
}

In the first case after stopping at the first call frame it "continues" the lookup with bindings available at the top level (module) scope.

It the second case it finds a value that is not bound in our program: parseInt.

This is one of the bindings that are available everywhere without the need to include them, in JavaScript you may call it the window object, in other languages it is described as a set of bindings that are automatically imported on every module, or prelude for short.

If the "look up" stops at the call frame then after reaching that point it has to go somewhere else. We could say that module and "prelude" bindings are bound "before" the bindings in the call stack. In many cultures the past is to the left, so let's continue there.

Let's add a left attribute to our Frame class and make it work in a similar way to up, start the lookup in the current Frame and continue up until upLimit or until up is null, then continue left until leftLimit or until left is null.

The right method is similar to the down method but it returns a new Frame instance that has the current frame as its left and up set to null.

We redefine down to return a new Frame instance where left is the same as the left of the current frame and up is the current frame itself.

{
  class Frame {
    constructor(left = null, up = null) {
      this.up = up;
      this.left = left;
      this.upLimit = false;
      this.leftLimit = false;
      this.binds = new Map();
    }

    bind(name, value) {
      this.binds.set(name, value);
      return this;
    }

    find(name) {
      const v = this.binds.get(name);
      if (v === undefined) {
        if (this.upLimit || this.up === null) {
          if (this.leftLimit || this.left === null) {
            return v;
          } else {
            return this.left.find(name);
          }
        } else {
          return this.up.find(name);
        }
      } else {
        return v;
      }
    }

    down() {
      return new Frame(this.left, this);
    }

    right() {
      return new Frame(this, null);
    }

    setUpLimit() {
      this.upLimit = true;
      return this;
    }

    setLeftLimit() {
      this.leftLimit = true;
      return this;
    }
  }

  {
    test("prelude implementation", () => {
      const env = new Frame()
        .bind("parseInt", parseInt)
        .right()
        .bind("a", 10)
        .right()
        .down()
        .setUpLimit();

      expect(env.find("parseInt")("42", 10)).toBe(42);
      expect(env.find("a")).toBe(10);
    });
  }
}

Prototype Chains

Another thing in object oriented languages that can be described as looking up bindings is "message dispatch", let's see some examples.

If we define an empty class A in JavaScript it "inherits by default" from the Object class:

{
  class A {}

  test("Object default inheritance", () => {
    expect(new A().toString()).toBe("[object Object]");
  });
}

We can emulate the lookup of toString with the Frame class as it is:

{
  test("Object default inheritance implementation", () => {
    const a = new Frame().bind("toString",
                 () => "[object Object]").right();

    expect(a.find("toString")()).toBe("[object Object]");
  });
}

We can declare a class B that defines its own toString method:

class B {
  toString() {
    return "B!";
  }
}

test("method", () => {
  expect(new B().toString()).toBe("B!");
});

We can again emulate it with the Frame class:

test("method implementation", () => {
  const b = new Frame()
    .bind("toString", () => "[object Object]")
    .right()
    .bind("toString", () => "B!");

  expect(b.find("toString")()).toBe("B!");
});

A more complicated prototype chain:

class C extends B {
  toString() {
    return "C!";
  }
}

test("method override", () => {
  expect(new C().toString()).toBe("C!");
});

test("method override implementation", () => {
  const c = new Frame()
    .bind("toString", () => "[object Object]")
    .right()
    .bind("toString", () => "B!")
    .down()
    .bind("toString", () => "C!");

  expect(c.find("toString")()).toBe("C!");
});

A class can have instance attributes, each instance binds it's own attributes but looks up methods in the prototype chain:

class D extends C {
  constructor(count) {
    super();
    this.count = count;
  }
}

test("instance attributes", () => {
  const d1 = new D(10);
  const d2 = new D(20);

  expect(d1.toString()).toBe("C!");
  expect(d1.count).toBe(10);
  expect(d2.toString()).toBe("C!");
  expect(d2.count).toBe(20);
});

We can emulate this by having the prototype chain "to the left" and the instance attributes in its own scope.

test("method override implementation", () => {
  const D = new Frame()
    .bind("toString", () => "[object Object]")
    .right()
    .bind("toString", () => "B!")
    .down()
    .bind("toString", () => "C!")
    .down();
  const d1 = D.down().bind("count", 10);
  const d2 = D.down().bind("count", 20);

  expect(d1.find("toString")()).toBe("C!");
  expect(d1.find("count")).toBe(10);
  expect(d2.find("toString")()).toBe("C!");
  expect(d2.find("count")).toBe(20);
});

We can do an analogy and say that in OOP Object is a kind of "class prelude", the class hierarchy is an analog to nested modules and the instance is the call stack :)

Growing a Language

But manipulating frames directly doesn't feel like a programming language, if we want to create a really simple language on top we should be able to at least bind and lookup names and do some operations on those values, like arithmetic operations on numbers.

This is the point where most articles pull the "small Lisp or Forth interpreter" trick, but the initial motivation for this exploration was to find a small object oriented language that could be grown and expressed from a small set of primitives.

We are going to start with numbers, specifically integers, since we are implementing our language on top of JavaScript let's use BigInts.

To express a variable we can define a Name class that holds the variable name in its value attribute:

{
  class Name {
    constructor(value) {
      this.value = value;
    }

    getType() {
      return "Name";
    }
  }

The OOP way to eval a Name would be to send it the eval message.

To do that we need a Msg class that can hold eval as the verb.

Following the vocabulary of message, name and verb, the message is sent to the subject and has an object, in case of eval the object is the current scope:

Some verbs (called transitive verbs) take direct objects; some also take indirect objects. A direct object names the person or thing directly affected by the action of an active sentence. An indirect object names the entity indirectly affected

-- Wikipedia: Traditional Grammar

  class Msg {
    constructor(verb, obj) {
      this.verb = verb;
      this.obj = obj;
    }

    getType() {
      return "Msg";
    }
  }

Let's redefine Frame with just two extra methods:

• eval(value): sends the message eval to value and return the result
• send(subject, message): sends the message to the subject

  class Frame {
    constructor(left = null, up = null) {
      this.up = up;
      this.left = left;
      this.upLimit = false;
      this.leftLimit = false;
      this.binds = new Map();
    }

    eval(v) {
      return this.send(v, new Msg("eval", this));
    }

    send(s, m) {
      return this
        .find(s.getType())
        .find(m.verb)
        .call(null, s, m, this);
    }

    bind(name, value) {
      this.binds.set(name, value);
      return this;
    }

    find(name) {
      const v = this.binds.get(name);
      if (v === undefined) {
        if (this.upLimit || this.up === null) {
          if (this.leftLimit || this.left === null) {
            return v;
          } else {
            return this.left.find(name);
          }
        } else {
          return this.up.find(name);
        }
      } else {
        return v;
      }
    }

    down() {
      return new Frame(this.left, this);
    }

    right() {
      return new Frame(this, null);
    }

    setUpLimit() {
      this.upLimit = true;
      return this;
    }

    setLeftLimit() {
      this.leftLimit = true;
      return this;
    }
  }

The implementation of send:

• gets the subject type
• looks up the type in the environment
  • the result should be a Frame instance with the "prototype" for that type
• it does a lookup for the Msg verb in the prototype
• calls the handler passing the subject, message and environment as arguments

We can try it by:

• creating an instance of Name for the name "a"
• creating a Frame that works as the prototype for Name, it holds a binding for eval that when called does a variable lookup in the environment
• creating a Frame for the call stack, binding "a" to 42, nameEnv to the type of Name (returned by a.getType())
• evaluating a in env and checking that it returns 42

  test("Name resolution with eval message", () => {
    const a = new Name("a");
    const nameEnv = new Frame()
                      .bind("eval", (s, _m, e) => e.find(s.value));
    const env = new Frame()
                      .bind("a", 42)
                      .bind(a.getType(), nameEnv);

    expect(env.eval(a)).toBe(42);
  });

We now have a language that supports bindings but we still can't express message sends in it.

Let's fix this by defining a Send class that has a subject and a message as attributes:

  class Send {
    constructor(subj, msg) {
      this.subj = subj;
      this.msg = msg;
    }

    getType() {
      return "Send";
    }
  }

Since we are going to be using BigInt as our language's Int type we will need to monkey patch BigInt's prototype with our getType method to be able to lookup handlers for Ints:

  BigInt.prototype.getType = () => "Int";

Note: In the next version we are going to use Symbols to avoid monkey patching.

We can now implement message sends in our language by defining eval message handlers for:

• Name: does a lookup for the name in the environment
• BigInt: returns itself
• Msg: returns a new Msg instance where the verb is the same but obj is evaluated
• Send:
  • evaluates subject and message
  • enters a call frame
  • binds it to the subject
    • I use it instead of this to differenciate from this and self in other OOP languages
  • binds msg to the message
  • binds that for the message's object and
  • sends the evaluated msg to the evaluated subject

To have some message to send that we can test we define a handler for the + message for Ints which does a lookup for it and adds it to the value bound to that.

There's an alternative implementation commented that directly uses s and m.obj that contain the same values.

Finally we test it by building an object that represents the expression 10 + a and check that it results in 42n since a was bounds to 32n in the environment.

  test("Msg Send eval", () => {
    const nameEnv = new Frame()
                      .bind("eval", (s, _m, e) => e.find(s.value));
    const intEnv = new Frame()
      .bind("eval", (s, _m, _e) => s)
      .bind("+", (_s, _m, e) => e.find("it") + e.find("that"));
    //.bind("+", (s, m, _e) => s + m.obj);
    const msgEnv = new Frame().bind(
      "eval",
      (s, _m, e) => new Msg(s.verb, e.eval(s.obj)),
    );
    const sendEnv = new Frame().bind("eval", (s, _m, e) => {
      const subj = e.eval(s.subj),
        msg = e.eval(s.msg);
      return e
        .down()
        .setUpLimit()
        .bind("it", subj)
        .bind("msg", msg)
        .bind("that", msg.obj)
        .send(subj, msg);
    });
    const env = new Frame()
      .bind("Name", nameEnv)
      .bind("Int", intEnv)
      .bind("Msg", msgEnv)
      .bind("Send", sendEnv)
      .right()
      .bind("a", 32n);

    // 10 + a
    const expr = new Send(10n, new Msg("+", new Name("a")));
    expect(env.eval(expr)).toBe(42n);
  });
}

A Language with Syntax

Let's write a parser for our language to make it easier to test, we are going to use ohmjs

import * as ohm from "./node_modules/ohm-js/index.mjs";

Since we are going to be Growing a Language let's create an utility function to define new languages:

function mkLang(g, s) {
  const grammar = ohm.grammar(g),
    semantics = grammar.createSemantics().addOperation("toAst", s),
    parse = (code) => {
      const matchResult = grammar.match(code);

      if (matchResult.failed()) {
        console.warn("parse failed", matchResult.message);
        return null;
      }

      return semantics(matchResult).toAst();
    },
    run = (code, e) => {
      const ast = parse(code);
      return ast ? e.eval(ast) : null;
    };

  return { run, parse };
}

Let's define our types again to use Symbols instead of monkey patching and to add a base class that allows any type to be used as a reply handler for a message by implementing the call method:

class Base {
  call(_, s, m, e) {
    return e.eval(this);
  }
}

Name, Msg and Send are almost the same as before:

class Name extends Base {
  constructor(value) {
    super();
    this.value = value;
  }
}

class Msg extends Base {
  constructor(verb, obj) {
    super();
    this.verb = verb;
    this.obj = obj;
  }
}

class Send extends Base {
  constructor(subj, msg) {
    super();
    this.subj = subj;
    this.msg = msg;
  }
}

But now instead of implementing getType as a method each type is going to have a unique Symbol used to lookup its "prototype" in the call stack when looking for a message handler.

We are going to create a Symbol called typeSym to get and set the type for each object and 3 utility functions to get, set and make a type, which creates the type sets it on a class and returns the type Symbol:

const typeSym = Symbol("TypeSym"),
  getType = (v) => v[typeSym],
  setType = (Cls, type) => ((Cls.prototype[typeSym] = type), type),
  mkType = (name, Cls) => setType(Cls, Symbol(name));

Let's define types for the classes we already have:

const TYPE_NAME = mkType("Name", Name),
  TYPE_MSG = mkType("Msg", Msg),
  TYPE_SEND = mkType("Send", Send),
  TYPE_INT = mkType("Int", BigInt);

Let's redefine Frame for the last time to use getType to get the type associated with a value:

class Frame {
  constructor(left = null, up = null) {
    this.up = up;
    this.left = left;
    this.upLimit = false;
    this.leftLimit = false;
    this.binds = new Map();
  }

  eval(v) {
    return this.send(v, new Msg("eval", this));
  }

  send(s, m) {
    return this
            .find(getType(s))
            .find(m.verb)
            .call(null, s, m, this);
  }

  bind(name, value) {
    this.binds.set(name, value);
    return this;
  }

  find(name) {
    const v = this.binds.get(name);
    if (v === undefined) {
      if (this.upLimit || this.up === null) {
        if (this.leftLimit || this.left === null) {
          return v;
        } else {
          return this.left.find(name);
        }
      } else {
        return this.up.find(name);
      }
    } else {
      return v;
    }
  }

  down() {
    return new Frame(this.left, this);
  }

  right() {
    return new Frame(this, null);
  }

  setUpLimit() {
    this.upLimit = true;
    return this;
  }

  setLeftLimit() {
    this.leftLimit = true;
    return this;
  }
}

We have everything in place to create the first version of our language:

const { run: run1 } = mkLang(
  `Lang {
    Main = Send
    name = (letter | "_") (letter | "_" | digit)*
    Msg = verb Value
    verb = verbStart verbPart*
    verbStart = "+" | "-" | "*" | "/" | "-" | "%" | "&" | "<" | ">" | "!" | "?" | "." | letter
    verbPart = verbStart | digit
    Send = Value Msg*
    Value = int | name
    int = digit+
  }`,
  {
    name(_1, _2) {
      return new Name(this.sourceString);
    },
    Msg: (verb, obj) => new Msg(verb.toAst(), obj.toAst()),
    verb(_1, _2) {
      return this.sourceString;
    },
    Send: (v, msgs) =>
      msgs.children.reduce(
        (acc, msg) => new Send(acc, msg.toAst()), v.toAst()
      ),
    int(_) {
      return BigInt(this.sourceString);
    },
  },
);