Control flow

CPS style

Let's talk about CPS - Continuation Passing Style. Let's say we've got a function to add two numbers:

function add(a, b) {
  return a + b;
}

To use it, write:

function add(a, b) {
  return a + b;
}
console.log(add(1, 2)); // 3

But imagine we can't use return keyword, because it doesn't exist in the language. How could we pass result back to caller? By using callbacks:

function add(a, b, onSuccess) {
  onSuccess(a + b);
}
add(1, 2, (result) => {
  // [2] here we can continue our program
  console.log(result); // 3
});
// [1] don't know how to continue from this point using result

Here comes the problem: how to continue after result is passed to the caller at position [1]? We're waiting for the result inside result => console.log(result) callback ([2]), not outside add call. Here we enter callback based control flow, very well known from node.js which very easily turns into callback hell. Fortunately, this can be fixed using generators or async/await.

However - in case of metaES - callbacks are what we want. They are low level, fast, controllable, allow to suspend execution and allow to recreate any other control flow. We can also go ahead use more than one callback: one for success value, second for error value - an exception:

function add(a, b, onSuccess, onError) {
  if (typeof a === "number" && typeof b === "number") {
    onSuccess(a + b);
  } else {
    onError(new Error("one of the operands is not a number"));
  }
}
// usage
add(1, 2, (result) => console.log("result is:", result), console.error);

Price to pay is slightly worst readability of metaES source code, but with tools like `forwarding` it's still pretty decent to read and stays maintainable. Most of metaES sources in fact could be tried to be written in async/await style and then compiled to older ECMAScript version if needed, but this approach would cause compiled code size explosion and would disallow to use "calling with current continuation" and other control flows.

function add(a, b, c, cerr) {
  if (typeof a === "number" && typeof b === "number") {
    c(a + b);
  } else {
    cerr(new Error("one of the operands is not a number"));
  }
}
// usage
add(1, 2, (result) => console.log("result is:", result), console.error);

c is a continuation. cerr is error continuation. Now we now what continuation passing style stands for: it is programming with callbacks for control flow, not return/throw statements.

Let's go one more step on abstraction ladder - abstract out the function call.

Instead of writing add(1, 2, result => console.log("result is:", result), console.error); we'd want to type:

evaluate(add, [1, 2], (result) => console.log("result is:", result), console.error);

Therefore, evaluate becomes:

function evaluate(fn, args, c, cerr) {
  const fnWithArgs = fn.bind(null, args);
  fnWithArgs(c, cerr);
}

// use it
evaluate(add, [1, 2], (result) => console.log("result is:", result), console.error);

As next step, eliminate add direct reference and use string based lookup. Lookup table will be implemented using pure JavaScript object:

function add(a, b, c, cerr) {
  if (typeof a === "number" && typeof b === "number") {
    c(a + b);
  } else {
    cerr(new Error("one of the operands is not a number"));
  }
}

// lookup table
const functions = { add };

function evaluate(fnName, args, c, cerr) {
  const fn = functions[fnName];
  if (fn) {
    fn.apply(null, args.concat([c, cerr]));
  } else {
    cerr(new ReferenceError(`${fnName} is not defined`));
  }
}

// example of positive succesful result
evaluate("add", [1, 2], (result) => console.log("result is:", result), console.error);

// example of error result
evaluate("add2", [1, 2], (result) => console.log("result is:", result), console.error);

Next piece is function subcalls. To achieve that, use evaluate again, this time with different args:

// add different function
function multiply(a, b, c, cerr) {
  if (typeof a === "number" && typeof b === "number") {
    c(a * b);
  } else {
    cerr(new Error("one of the operands is not a number"));
  }
}

const functions = {
  add,
  // add to lookup table
  multiply
};

evaluate(
  "add",
  [1, 2],
  (result) =>
    // got result from adding, now multiply it
    evaluate(
      "multiply",
      [result, 3],
      (result) =>
        // that's our result
        console.log("result is:", result),
      console.error
    ),
  console.error
);

We already can see two problems:

• two callbacks are required to support simple arthmetic operations,
• we need to handle error continuations twice (console.error is used twice), one time for each call. Errors can't be propagated yet.

Depsite the issues, we can add and multiply - in a verbose way though. Let's add few more abstractions to be able to eventually collapse previous abstractions. This sounds paradoxical but that's a very good sign. Composable design at some point allows some pieces of code to disappear.

Let's change numbers to Literals object:

const literal1 = { type: "Literal", value: 1 };
const literal2 = { type: "Literal", value: 2 };
const literal3 = { type: "Literal", value: 3 };

Then move to creating AST-like structures for add and multiply function calls. They're not functions anymore, but execution tree binary expressions:

const add = {
  type: "BinaryExpression",
  operator: "+",
  left: literal1,
  right: literal2
};

const multiply = {
  type: "BinaryExpression",
  operator: "*",
  left: add,
  right: literal3
};

Next, refactor evaluate to accept AST-like nodes - not strings mixed with function names as it did so far:

const functions = {
  Literal(node, c) {
    c(node.value);
  },
  BinaryExpression(node, c) {
    evaluate(node.left, (left) =>
      evaluate(node.right, (right) => {
        switch (node.operator) {
          case "+":
            c(left + right);
            break;
          case "*":
            c(left * right);
            break;
        }
      })
    );
  }
};

function evaluate(node, c, cerr) {
  let fn = functions[node.type];
  fn ? fn(node, c, cerr) : cerr(new Error(`${node.type} function is not supported.`));
}

// use
evaluate(
  {
    type: "BinaryExpression",
    operator: "+",
    left: {
      type: "Literal",
      value: 1,
      raw: "1"
    },
    right: {
      type: "BinaryExpression",
      operator: "*",
      left: {
        type: "Literal",
        value: 2,
        raw: "2"
      },
      right: {
        type: "Literal",
        value: 3,
        raw: "3"
      }
    }
  },
  console.log
);

What we achieved is very simple evaluator of AST-like nodes. Implementation looks very overblown, but this is the inflection point where collapsing becomes possible.

To recap:

• we started with simple 1+2 expression written using infix operator,
• expression was evaluated using return statement inside a function,
• we had eliminated return statement and switched to continuations,
• we had added support for error handling using second - failure - continuation,
• we've removed need for accessing add function directly,
• we've moved literals like 1 to move a structure of type Literal
• we embraced evaluate function which became ubiquitous used even inside add and mul functions.
• whole program to evaluate was expressed using evaluation tree which can be equivalent to AST (abstract syntax tree) known in parsing theory.

That's why at this point you can use a parser:

// Let's pretend we went few steps ahead
const metaesEval = evaluate;
metaesEval(
  // result of `parse` function should be an AST tree
  parse("2+2"),
  console.log,
  console.error
);

To be precise, metaES uses meriyah parser underneath which will actually return:

{
  "type": "Program",
  "sourceType": "module",
  "body": [
    {
      "type": "ExpressionStatement",
      "expression": {
        "type": "BinaryExpression",
        "left": {
          "type": "Literal",
          "value": 2
        },
        "right": {
          "type": "Literal",
          "value": 2
        },
        "operator": "+"
      }
    }
  ]
}

but at this point it should be easy to implement missing AST nodes as an excercise for the reader.