Forem: Yassine Elouafi

Types as Propositions in Typescript

Yassine Elouafi — Sat, 23 Sep 2023 14:50:17 +0000

Propositions as types correspondance (PAT) (or Types as Propositions) is one of the most intriguing discoveries of Computer Science. The gist of it is:

In Logic land, you often see stuff like P is True. Here, P can stand for some statement that can be true or false. And a Proof is constructed to back the statement.
In code, we've got something like: let x: T = term;.

The correspondance is basically saying Logic and Programming are two sides of the same coin:

In Logic: When you claim something is true, you must provide a Proof for it.
In code: If you got a type and want to use it, you create a term of that type.

It's as if we were writing let x: P = proof; in TypeScript. And it's not just some quirky coincidence. If we restrict ourself to a pure subset TypeScript, you'll see you can write logical proofs using code.

Code's Take on Logic Constructs

First let's review quickly the key concepts in Logic, they work pretty much like the booleans we use in programming:

True or ⊤: This represents a proposition that's always true.
False or ⊥: signifies something that's never true.
A ∨ B : A disjunction. True if either A or B hold true. Could be both.
A ∧ B : A conjunction. Both A and B must be true.
A -> B : Logical implication. If A is true, then B is consequently true.
!A : negation, a Proposition that's true if A is not.

There's also A <=> B. It's essentially stating that A implies B and B implies A. In other words, (A -> B) ∧ (B -> A).

Now for each one of the above constructs we have an equivalent type in Typescript.

True corresponds to any inhabitated type

type True = unknown;

We could use a singleton type like null or undefined. But with the unknown type, we can assign any value to it.

False translates to an uninhabited type in TypeScript. This mirrors the fact that there's no proof for a false proposition in Logic:

type False = never;

A ∨ B corresponds to a discriminated union type in TypeScript.

type Or<A, B> = 
  | { tag: "left"; value: A } 
  | { tag: "right"; value: B };

We'll also write two constructor functions:

function left<A>(value: A): Or<A, never> {
  return { tag: "left", value };
}

function right<B>(value: B): Or<never, B> {
  return { tag: "right", value };
}

And a helper for case analysis:

function either<A, B, C>(
  or: Or<A, B>,
  onLeft: (a: A) => C,
  onRight: (b: B) => C,
): C {

  return (
    or.tag === "left" 
      ? onLeft(or.value) 
      : onRight(or.value)
  );
}

A ∧ B corresponds to a pair of types:

type And<A, B> = [A, B];

Logical implications translate to function types:

type Imp<A, B> = (a: A) => B;

Finally, The equivalence A <=> B corresponds to a pair of 2 functions. It's a sort of 2-way conversion between A and B

type Iff<A, B> = [Imp<A, B>, Imp<B, A>];

So far, everything's been kinda familiar, right? But with negation, things are getting a bit wild.

Negative types

Let's start by unpacking the meaning of False/never. The never type acts as a universal subtype, as it can be assigned to any other type.

You might wonder about the meaning of any here. Intriguingly, any stands as a proposition that is both True and False at once. This duality allows any value to be assigned to it, making it akin to unknown or True. On the flip side, it can fit into any type (except never), reflecting the nature of never or False.

In logical discourse, a proposition that holds as true and false simultaneously is labeled a contradiction. If one can prove a contradiction, the whole logic system just falls apart.

In a parallel sense, being able to produce terms of type any compromises the soundness of the type system. As highlighted in the TypeScript documentation, the flexibility of any sacrifices type safety.

This brings us to the concept of Proof by contradiction: To disprove a proposition A (or to assert !A), one assumes A is true and then demonstrates that this assumption leads to a contradiction.. In essence, !A equates to A -> False.

Hence, negating a type A in TypeScript translates to the function (x: A) => never.

type Not<A> = (x: A) => never;

Double negation, paradoxes and the halting problem

Constructing a term of type A -> never poses challenges though. How can we return a never value when, by definition, never lacks any values?

One way to produce a negative type in Typescript is by writing a non terminating function. For example:

function forever<A>(a: A) {
  return forever(a);
}
// typeof forever = <A>(a: A) => never

Typesript detects that the function never terminates and assigns to it a type of <A>(a: A) => never. (There are alternative methods to create functions that don't return, but remember we're operating within a limited TypeScript subset here).

Is this type designation genuinely accurate from a logical standpoint?

Consider the following function

function double_neg<A>(ff: (callback: (a: A) => never) => never): A {
  //
  function wait_forever(a: A): never {
    return wait_forever(a);
  }

  return ff(wait_forever);
}

A closer look at the type reveals it corresponds to Not<Not<A>> => A. This is just the double negation law in Logic: !!A = A.

The implementation exploits the fact that never can be assigned to any type A. Now we should be able to use our double negation in our code to turn values of type !!A into values of type A:

const a = double_neg(k => k(5));

let b = a + 2;
// ...

However an issue arises: the statement let b = a + 2; is never reached. Upon entering double_neg, the body invokes k(5) where k represents the non terminating function wait_forever. The program remains trapped there indefinitely.

The core issue with wait_forever is its endless recursion. It's like an infinite loop that keeps running without an exit condition. In Logic, infinite loops can give birth to tricky paradoxes, like this classic:

This statement is false

This is the essence of the liar paradox. If you try to reason through it, you'll get stuck in a endless cycle of contradictions. Give it a try!

If we assume that statement is true, then the statement must be false as it claims to be. But then it contradicts our own assumption that the statement was true.a
If we assume that statement is false, then it's ironically being truthful about its falsehood, making it true. Again, this is a contradiction because we just assumed it was false.

The self-referencing nature of the statement is the real troublemaker here. It creates a loop where the truth value keeps toggling between true and false, never settling, similar to how a piece of code is stuck in an infinite loop.

This is bad for Logic, which requires every proof to be finite. What this says in reality is that wait_forever is not exactly the function we're seeking for our negative types.

A more Logic freindly interpretation of negation is actually possible, and would allow writing programs in double negation style. To see how, let's revisit our earlier example:

const a = double_neg(k => k(5));

let b = a + 2;
// ...

The double negation principle, !!A = A, hints that the program should progress beyond the initial line, assigning a number type to a. Which number? In this context, 5 seems like a logical choice.

But then, what's the role of the k argument, and how do we instantiate it?

Here's the twist: k isn't a function we can implement by ourselves. It has to be provided to us by the programming language.

This isn't just a normal function, It belongs to a special class known as continuations. Think of a continuation as a snapshot of a program's future from a particular moment. For example, consider this code:

// assume f : (n: number) => number
const a = f(5);

let b = a + 2;
// ...

Now, let's transform it into a continuation-passing style (CPS):

f(5, (a) => {

  let b = a + 2;
  // ...
})

In the CPS style, every function receives an extra k argument, which represents the program's subsequent steps.

Our double_neg, by converting from Not<Not<A>> to A, essentially transforms a CPS function call into a standard value of type A. It achieves this by encapsulating the program's future steps and repackaging them into a function awaiting a value to proceed.

While non-terminating functions and continuations both return never, continuations avoid embedding self-referential inconsistencies within our system. By the time the function concludes, the program has also concluded.

That means to make values of type Not<A>, our programming language should equip us with something to encapsulate the program's subsequent steps as a continuation.

Although TypeScript doesn't natively support this construct, for the sake of discussion, let's pretend it does:

declare function double_neg<A>(f: Not<Not<A>>): A;

While the double negation principle might feel intuitive, I should mention it's not something universally accepted. Some logicians believe that just because a statement isn't proven doesn't mean the opposite holds true. Think of it as "absence of evidence isn't evidence of absence." This viewpoint is held by intuitionistic logic.

In contrast classical Logic embraces the double negation law. But as we've observed, to embed this principle in a programming language, we need a control operator to turn double negation into identity. This hints at a deep connection between the context in which a program runs and the foundational logic underpinning it.

If you've dabbled with Lisp-like languages (like Scheme or Clojure), you might've bumped into a cousin of double_neg named call/cc (though its type is a bit different).

Diving into Logical Proofs using TypeScript

Having established a bridge between Logic's concepts and our TypeScript subset, We're ready to weild this knowledge to perform some common proofs in Logic.

The most elementary proof is the tautology A => A. This is just the identity function

function id<A>(a: A) {
  return a;
}

Let's see some more interesting proofs.

We'll define all our proofs in a generic function, to abstract over propostions A and B.

function context<A, B>() {
  //
  type NotA = Not<A>;

  type NotB = Not<B>;

  // ... subsequent proofs will be populated here
}

Law of Excluded Middle (`A ∨ !A <=> True`)

The law of excluded middle is a foundational principle in classical logic, which asserts that any proposition is either true or its negation is true. There's no in-between state.

Let's first write the implementation:

// A ∨ !A
const excluded_middle: Or<A, NotA> = 
  double_neg(k => 
    k(right(a => 
      k(left(a))
    ))
  );

To construct a value of type A ∨ !A, we have 2 choices:

Constructing A: Creating an instance of an arbitrary type A is unfeasible. It's like attempting to materialize something from nothing.
On the other hand, creating an instance of !A is feasible. To understand this, recall that !A is synonymous with a continuation of type (a:A) -> never. So we'll need the help of double_neg.

Here's the step-by-step breakdown of the implementation:

Invoke double_neg and capture the current continuation as k.
Inside the continuation, the next plausible action is to make use of right to indicate we're choosing the negation path. This gives: k(right(a => _)).
Now, inside our function (a => _), we need to return a value of type never. The one tool we have at our disposal to achieve this effect is the captured continuation k. Since we now have access to a value of type A (through the function argument), we can use k to redirect our flow to the other branch, i.e., left(A). This is expressed as: k(left(a)).

This construction can look mind-bending, especially if encountered for the first time. It's somewhat analogous to a closed time-like loop in physics, where cause and effect blur.

In [one of his papers (https://homepages.inf.ed.ac.uk/wadler/papers/dual/dual.pdf), Philipe Wadler, illustrates the above behavior:

The following story illustrates this behavior. (With apologies to Peter Selinger, who tells a similar story about a king, a wizard, and the Philosopher’s stone.)

Once upon a time, the devil approached a man and made an offer: “Either (a) I will give you one billion dollars, or (b)
I will grant you any wish if you pay me one billion dollars. Of course, I get to choose whether I offer (a) or (b).

The man was wary. Did he need to sign over his soul? No, said the devil, all the man need do is accept the offer.

The man pondered. If he was offered (b) it was unlikely that he would ever be able to buy the wish, but what was the harm in having the opportunity available? “I accept,” said the man at last. “Do I get (a) or (b)?” The devil paused. “I choose (b).”

The man was disappointed but not surprised. That was that, he thought. But the offer gnawed at him. Imagine what he could do with his wish! Many years passed, and the man began to accumulate money. To get the money he sometimes did bad things, and dimly he realized that this must be what the devil had in mind. Eventually he had his billion dollars, and the devil appeared again.

“Here is a billion dollars,” said the man, handing over a valise containing the money. “Grant me my wish!” The devil took possession of the valise. Then he said, “Oh, did I say (b) before? I’m so sorry. I meant (a). It is my great pleasure to give you one billion dollars.”

And the devil handed back to the man the same valise that the man had just handed to him.

Lastly, an important takeaway is that the double_neg function anchors this logic in the domain of classical logic. In intuitionistic logic, which is more conservative about claims of truth or falsity, such a construction might not hold true. Here, if you cannot furnish a proof for A, it doesn't automatically mean A is false. It simply means that the truth value of A remains undetermined.

`A ∧ !A -> False`

A proposition and its negation cannot both be true simultaneously.

// A ∧ !A -> False
const neg_law: Imp<And<A, NotA>, False> = ([a, notA]) => notA(a);

In code, this means we can just smash matter and antimatter together and watch them annihilate.

Equivalence between Functions and Discriminated Unions?

Here's a thought-provoking equivalence:

A -> B <=> !A ∨ B

It basically says a function A -> B is equivalent to an union of a continuation expecting A and a value B.

Let's see what this means in code.

From (A -> B) to (!A ∨ B):

// Transition from (A -> B) to (!A ∨ B)
const fn_union_fwd: Imp<Imp<A, B>, Or<NotA, B>> = 
  (f) =>
    double_neg(k => 
      k(left(a => 
        k(right(
          f(a)
        ))
      ))
    );

Utilizing the previous time-traveling maneuver, we initially yield a continuation to solicit an A type. Then we use our A -> B function to transform the A into a B value. Subsequently, we reinvoke the continuation to yield the result B to the surroundings.

Conversely, for the transformation of a union type to a function:

// Transition from (!A ∨ B) to (A -> B)
const fn_union_bwd: Imp<Or<NotA, B>, Imp<A, B>> = 
  notA_or_B => 
    a =>
      either(
        notA_or_B,
        (notA) => notA(a),
        (b) => b,
      );

To morph a union type to a function, we assume an A argument. Then based on the content of our container !A ∨ B:

If it's a continuation waiting for an A, we just present our A argument.
Conversely, if it's a B value, we directly return it.

This may appear as a form of trickery. One usually expects a genuine mechanism to turn an A into a B. Instead, the transformation feels more like routing around the union, merely forwarding existing information rather than truly processing it.

To be honest, I don't really have a plausible explanation. I was thinking it might be because of classical logic quirks, but the above proof doesn't use double_neg so it's equally valid in intuitionistic logic.

I tried to ask my freind GPT-4. Can't say it adds much but here's the answer anyway:

"Imagine you have a box that might either contain a machine that needs some input A to work or an already finished product B. Now, if someone hands you an A, this function simply checks the box. If there's a machine (notA), it feeds the A to it. If there's a finished product B, it just hands it over. The function doesn't do the "creation" part itself, but instead relies on what's in the box. This doesn't feel like a trick anymore; it's more about delegation and routing based on what's available."

TS playground where you can find other common proofs in Logic.

Happy proving!

A simple rule for using callbacks in React

Yassine Elouafi — Wed, 20 Jan 2021 17:11:00 +0000

In this post I assume you know React and the Hooks API. I also assume a basic knowledge about render and commit phases in Concurrent mode.

Most of React hooks complaints seem to revolve around having to manually manage hooks dependencies. Personally, I don't find that problematic (The rules are pretty clear, and you can just follow the linter). I was, however, having difficulty wrapping my head around the useCallback hook. Yes, I know what it does and how it works, but I'm talking about having a simple mental model and how it fits into the greater picture inside a React application.

Well, dependency management plays a role in the following story but not the way it's often stated. I think the issue is not having to manage dependencies by ourselves, but the way reactivity in React plays with side effects.

My aim in this post is to answer the following questions

Why does useCallback seem problematic?
Is there a simple way to reason about callback usage in React ?

With class Components, using a callback seemed easy enough: just bind the function to the class instance and pass around the result. With the introduction of hooks, things suddenly appeared more difficult (or more subtle). The most common complaint you'll probably hear is about stable references.

With classes the callback typically follows the lifecycle of the class instance, you'll create and bind the function only once in the constructor or using field declarations. The reference you pass around doesn't change during this time. Also since those functions relied on this.state and this.props, they had access to the latest values which seems to be a correct behavior.

With hooks, functions are typically created inside render functions in order to access props and state, which means we'll get a new reference on every render. In an ideal world, this doesn't hurt, the main benefit of naked callbacks is that they give us the correct state/props values which is even more crucial in Concurrent mode. But in the real world this may be undesirable because it could trigger superfluous render cycles or unwanted useEffect executions.

The purpose of useCallback is to control the creation of a new reference inside render functions using the dependency management mechanism. Often in docs or tutorials, you'll find mentions of useCallback(fn, deps) being just an alias for useMemo(() => fn, deps) (which, as we'll see later, is not always the case from the point of view of this post). Like useMemo, useCallback is only an optimisation, it means the code should still be working without it.

There is an interesting issue in the React repo called useCallback() invalidates too often in practice which refers to why the default useCallback behavior is not always what we want. Some appear to be valid, like I don't want to rerender a component just because dependencies of an event handler has changed, the behavior of the handler is still the same (The counter argument is also valid, technically it's not the same event handler if it closes over different values). As we'll see later, which point is correct depends essentially on what kind of value is the event handler.

Another interesting case concerns initiating a websocket connection only once upon mounting, then executing some socket handler regularly. We don't want to retrigger the connection process every time something changes but the handler should always see the last committed value.

The often proposed workaround is to use a mutable reference to store the function, then schedule an effect to update the values accessed by the function. A more concise workaround proposed in the issue is to store the changing function itself:

function useEventCallback(fn) {
  let ref = useRef();
  useLayoutEffect(() => {
    ref.current = fn;
  });
  return useCallback(() => (0, ref.current)(), []);
}

This seems pretty good, so why not just adopt this as the default behavior for useCallback? we keep a stable reference while still having access to the latest value. But what's the meaning of latest values here?

In Concurrent mode, there could be two different answers: either we mean the last values seen in a render function, or we mean the last values used when committing to the screen. useEventCallback has an affinity for committed values. But there are other use cases where I want to see the last rendered values instead (e.g. render callbacks).

So it may seem that the general rule is: use useEventCallback when doing side effects, and use the builtin useCallback when doing render work. Alas, it's not that simple. Imagine the following example

function MyComponent(props) {
  const [state, setState] = useState(...);

  const logger = useEventCallback(() => {
    console.log(state);
  });

  useEffect(() => {
    const tid = setTimeout(logger, 1000);
    return () => clearTimeout(tid);
  }, [logger]);
}

The code seems perfectly correct per the hooks rules, yet it won't get the desired result. Think it a moment ...

The problem is that useEventCallback returned a stable reference for logger, and although the returned function can see the last committed state (which is what we want because we're in a side effect), the effect will be executed only once since its single dependency doesn't change. What we want though is to execute the effect as soon as state changes. We can add state as a dependency but the question is per what rule? state doesn't appear anywhere inside the effect code. Our chosen useEventCallback has broken the transitivity of hooks dependencies and the rules are no longer valid.

So does it mean invalidation is inevitable and we're doomed? I don't think so. I believe there is a way out.

The example above reveals another decision factor, it's not just about doing render vs side effects. Invalidation also plays a role in effect execution, sometimes it's desirable to invalidate, but in other cases we'd rather keep a stable reference and use mutation to access last committed values (like in DOM event handlers).

Let's recap

The case of render callbacks is unambiguous, useCallback is necessary because it gives us the minimum amount of invalidation required. We must rerender and we must access the last rendered values.
The case of side effects is more subtle
- In some cases invalidation is desirable because we want to schedule the effect execution as soon as possible.
- In other cases invalidation is superfluous, because we're only interested in executing the same handler code but with the last committed values.

Is there a generic rule by which we can distinguish between the 2 last cases?

Notice the similarity between render callbacks and the logger example, in both cases, we want React to output something into the external world as soon as the internal state of the application has changed.

There is also a similarity between the event DOM callbacks and the websocket example. In both cases, we've told the external world (the user or the network) that we're interested in receiving some kind of input. When the input arrives, we'll decide what to do next based on the last committed state of the application. For optimisation purposes, the right amount of invalidation in this case is precisely the commit cycles triggered by state changes, the rest are just undesirable glitches.

In other words it all depends on the direction of the dataflow:

With output effects, data flows from React into the external world. We want that output to happen as soon as something changes internally.
With input effects, data flows from the external world into React. We want to react to some external event, and the decision should always be based on the latest output the world has seen from us, i.e. should always be based on the last committed state.

Which answers the 2nd question from the beginning of this post

useEventCallback is more suited for callbacks waiting for some external input, then changing the state of the application.
useCallback is more suited for callbacks that output something into the external world. In fact useCallback is semantically really an alias for useMemo since we're treating functions here the same as the values we output from JSX.

This also should explain why useCallback seems problematic, the same abstraction is used to handle input and output cases. But the 2 cases have incompatible semantics. It may also be a consequence of the fact that React doesn't have a first class support for inputs. For example, input callbacks like DOM event handlers are treated like regular data that must flow to the external world every time something changes.

Finally let's answer a previous question: Is it the same event handler or not if the code stays the same but the dependencies change?

As I said, it depends on what kind of value you think the event handler is. If you think of it as a regular data value, like rendered JSX, then the answer is no. If you think of the handler as a special kind of value waiting for an input, then the answer is yes. In this case, the callback is not closing over a regular value, but over a mutable reference which always refer to the latest committed value.

But what if it's not just the dependencies that changes but the code itself. This would be similar to a stateful event handler, something similar to the generators used in redux-saga. Well, in this case, I think it's better to break things down using a mix of state, input and output code. In other words, we'll be using a state machine where the changing behavior is taken care of by the machine's transition function. The event handler code would be essentially to feed the machine with external input. In fact, it may be even better to extend this kind of reasoning to the whole component, in this sense JSX is just another output.

Algebraic Effects in JavaScript part 4 - Implementing Algebraic Effects and Handlers

Yassine Elouafi — Sat, 06 Oct 2018 11:48:34 +0000

This is the final part of a series about Algebraic Effects and Handlers.

Part 1 : continuations and control transfer
Part 2 : Capturing continuations with Generators
Part 3 : Delimited continuations
Part 4 : Implementing Algebraic Effects and handlers

So we've come to the core topic. The reality is that we've already covered most of it in the previous parts. Especially, in the third part, where we saw delimited continuations at work.

In this part, we'll see that the mechanism of Algebraic Effects isn't much different from that of delimited continuations. But first, let's approach the topic from a more familiar perspective. We'll exploit the similarity with JavaScript Error handling to introduce the concept.

From Exceptions to Algebraic Effects

Below a simple example of Error handling. Don't pay much attention to the program logic, all we're interested on are the mechanics of the Call Stack.

function main(n) {
  return handler(n);
}

function handler(n) {
  try {
    unsafeOperation(n);
  } catch (e) {
    return 0;
  }
}

function unsafeOperation(n) {
  const x = oneMoreIndirection(n);
  return x * 2;
}

function oneMoreIndirection(n) {
  if (n < 0) {
    throw "cant be under zero!";
  }
  return n + 1;
}

main(-1);
// => 0

Once we reach the oneMoreIndirection, the Call Stack looks like:

main(-1) -> handler(-1) -> unsafeOperation(-1) -> oneMoreIndirection(-1)

When oneMoreIndirection throws, the exception bubbles up to the closest try/catch block, which in this case is located in handler. All stack frames below that handler (oneMoreIndirection(-1) -> unsafeOperation(-1)) are discarded. So the Call Stack becomes like:

main() -> handler()

Now, let's envision what those discarded frames represent concretely. If we were to resume after throw "can't be a zero!", then we should

return n + 1 from oneMoreIndirection
then return x * 2 from unsafeOperation
then return to ...hmmm

Where should we return after? It must be somewhere inside handler but where exactly? The control is now inside catch but it may not be obvious where our continuation would fit. But remember, exceptions work through a double decision

control is transferred to the most recent enclosing handler
the stack frames from the throwing function up to the handler are discarded

So what happens if we keep decision (1) but change (2): the stack frames aren't discarded but reified as a function (a delimited continuation), which is provided as argument to the handler? In an hypothetical JavaScript, this would look like:

function handler() {
  try {
    unsafeOperation(0);
  } catch (e, /**/resume/**/) {
    // ...
    return 0;
  }
}

Now it may not be obvious what should we do with resume. After all, it doesn't make much sense to resume a function that has already aborted. But that's only if we consider non-local control transfer as exclusively meant to signal exceptions. What if we could use it in a more general way, as a sort of interaction between a (maybe deeply nested) function and an enclosing handler?

The function can throw a request, and the handler interprets the request then resumes the function using the provided continuation. As with exceptions, the function doesn't need to know anything about the handler or how the request is fullfilled. And, that's the core idea of Algebraic Effects.

I'm not going to discuss the motivation behind throwing effects vs executing them right away inside a function. The question just translates to why we should separate pure and impure computations, which is a whole subject ont its own.

The thing I want to mention here, is that many discussions I saw on this subject lack the required context. Many arguments that are valid in a language like Haskell aren't necessarily transposable to a language like JavaScript. In the former, things like purity makes it easier to give a mathemtical interpretation to a program, which can be exploited by the compiler to prove many properties about the program at compile time. This isn't the case in JavaScript, which doesn't have the same mathematical formalism underline (for example I see no reason to forbid mutation of local varibales in JavaSript). On the other hand, I do beleive some other properties, like Compositionality, are equally important in any programming language.

So back to our earlier example, here's how the whole example may look like in our hypothetical JavaScript:

function main() {
  return handler();
}

function handler() {
  try {
    operation();
  } catch (e, resume) {
    return resume("Yassine");
  }
}

function operation() {
  return oneMoreIndirection();
}

function oneMoreIndirection() {
  const name = throw "Your name, please?";
  return `Hi ${name}`;
}

If you ever worked with libraries like redux-saga it's the same idea but on streoids. Here, you have full control over the effects (while in libs like redux-saga the interpretation of effects is hard coded in the library). As we'll see, you have even control over the return value of the handled computation.

Ok, having seen what could be JavaScript in a parallel universe, let's go back to reality. While we'll, probably, never see the catch clause taking a continuation argument some day, we can use our old freinds, Generators, as a decent consolation.

Implementing Algebraic Effects with Generators

We're going to do this in two steps.

First, we'll implement just the exception like part: transfer the control to the closest handler
Then we'll add the code to capture the delimited continuation up to the handler

We'll base our implementation on this version from the last post

function isGenerator(x) {
  return x != null && typeof x.next === "function";
}

function runGenerator(gen, arg) {
  const { value, done } = gen.next(arg);

  if (done) {
    const _return = gen._return;
    if (isGenerator(_return)) {
      runGenerator(_return, value);
    } else if (typeof _return === "function") {
      _return(value);
    }
  } else {
    if (isGenerator(value)) {
      value._return = gen;
      runGenerator(value, null);
    } else if (typeof value === "function") {
      value(gen);
    }
  }
}

function start(gen, onDone) {
  gen._return = onDone;
  runGenerator(gen, null);
}

Quick remainder, the code relies on a _return field on the Generator, which points to the parent Generator. Inside a Generator, we can either yield a call to a child Generator (in which case we set its _return to the current one), or yield a suspended computation (just a fancy name for a function taking the current Generator).

First, let's add the equivalent of our try/catch clause.

function withHandler(handler, gen) {
  function* withHandlerFrame() {
    const result = yield gen;
    // eventually handles the return value
    if (handler.return != null) {
      return yield handler.return(result);
    }
    return result;
  }

  const withHandlerGen = withHandlerFrame();
  withHandlerGen._handler = handler;
  return withHandlerGen;
}

First thing we need is to run withHandler in its own Generator, this way it'll have its own stack frame
We save the provided handler in a _handler field in withHandler's own Generator
Inside this Generator, we run the provided computation
The handler may eventually handle the return value of the computation, we'll see later how it can be useful

For example:

const abortHandler = {
  //optional, handles the return value
  *return(result) {
    // ...
  },
  *abort(msg) {
    console.error(msg);
    return 0;
  }
};

function* main() {
  yield withHandler(abortHandler, someFunc());
}

We set abortHandler as a handler for all abort effects thrown from inside someFunc(). The function, or one of its children, can use perform("abort", msg) to throw an exception that will bubbles up to the handler.

Below our first implementation of perform (note we don't capture the continuation)

function perform(type, data) {
  return performGen => {
    // finds the closest handler for effect `type`
    let withHandlerGen = performGen;
    while (
      withHandlerGen._handler == null ||
      !withHandlerGen._handler.hasOwnProperty(type)
    ) {
      if (withHandlerGen._return == null) break;
      withHandlerGen = withHandlerGen._return;
    }

    if (
      withHandlerGen._handler == null ||
      !withHandlerGen._handler.hasOwnProperty(type)
    ) {
      throw new Error(`Unhandled Effect ${type}!`);
    }

    // found a handler, get the withHandler Generator
    const handlerFunc = withHandlerGen._handler[type];
    const handlerGen = handlerFunc(data);

    // will return to the parent of withHandler
    handlerGen._return = withHandlerGen._return;
    runGenerator(handlerGen, null);
  };
}

The function returns a suspended computation that does the following

lookup for the closest handler that can handle type like effects
if we can't find a suitable handler, we throw (for real this time) an error
if a matching handler is found, we instantiate its function with the effect data
set the _return address of the handler's Generator to the parent of withHandler clause
run the handler's Generator

Note the last step means we're purely ignoring performGen, which corresponds to how catch discards the throwing function.

Let's see how it works with the earlier error handling example adapted to Generators

const abort = {
  *abort(msg) {
    console.error(msg);
    return 0;
  }
};

function* main(n) {
  return yield handler(n);
}

function* handler(n) {
  return yield withHandler(abort, unsafeOperation(n));
}

function* unsafeOperation(n) {
  const x = yield oneMoreIndirection(n);
  return x * 2;
}

function* oneMoreIndirection(n) {
  if (n < 0) {
    // throw
    yield perform("abort", "can't be under zero!");
  }
  return n + 1;
}

start(main(2), console.log);
// => 6

start(main(-1), console.log);
// => can't be under zero!
// => 0

Let's take a closer look to how perform/withHandler work together in this case.

Since withHandler doesn't change the Call Stack, but just wraps the given Generator and sets a special _handler field, when we reach the oneMoreIndirection(-1) the stack looks like this:

main(-1) -> handler(-1) -> withHandler({abort}) -> unsafeOperation(-1) ->  oneMoreIndirection(-1)

yield perform("abort", msg) finds the closest handler, which becomes the direct child for the parent of withHandler clause:

main(-1) -> handler(-1) -> abort(msg)

Notice how this is similar to shift/reset we saw in the previous post. When shift doesn't use the captured continuation, it effectively discards all the stack frames up to, and including, the reset block. shift repalces, then, the whole surrounding reset block and becomes the main expression of reset's parent. In fact, shift/reset presents much more similaralities with perform/withHanndler as we'll see in a moment.

Capturing the delimited continuation

We shall, now, generalize our exception like handling by providing the handler with a delimited continuation that represents the previously discarded stack frames. This time, however, we'll proceed differently. Before jumping into the code, we'll start with a usage example, analyze how things should work in this example, then show the implementation.

The example uses a read effect to get a value from the surrounding environment. For our purpose, the handler will interpret the effect with a constant value.

// define the `read` handler
const constRead = {
  *read(_, resume) {
    const result = yield resume("Stranger");
    return result;
  }
};

function* main() {
  return yield withHandler(constRead, greet());
}

function* greet() {
  const name = yield withCivility();
  return `Hi, ${name}`;
}

function* withCivility() {
  // throw the `read` effect
  const name = yield perform("read");
  return `M. ${name}`;
}

start(main(), console.log);
// => Hi, M.Stranger;

Assuming we have a working perform implementation, let's envision how the example should manipulate the Call Stack. As always, nothing happens until we reach withCivility()

main() -> withHandler({read}) -> greet() -> withCivility()

When performing the read effect, we know from the previous example that the handler will become the direct child of main(). However, the intermediate frames, previously discarded, will now become the delimited continuation provided to the read handler

main() -> read(_, <<withHandler({read}) -> greet() -> withCivility()>>)

We should point to an important thing here. The captured continuation is still wrapped by withHandler({read}), this is essential because we still want to handle further read effects from the rest of the computation. Notice, also, that the read handler runs outside withHandler({read}) scope, this is also important, this handler may, itself, forward read effects (or any other effect) to an upstream handler. This makes it possible to compose different handlers. Each handler in the chain may perform some preprocessing then delegate the same (or another) effect to a parent handler.

So, now when read's handler resumes the delimited continuation the stack becomes

main() -> read(_, <<>>) -> withHandler({read}) -> greet() -> withCivility()

Note our continuations can only be invoked once (one shot). This is repersented by setting the second argument of read to <<>>.

In the case withCivility performs a second read effect, it will be trapped again by the surrounding withHandler and a new handler instance will be created and inserted into the stack. The parent of the new handler will be withHandler({rad})'s parent, which in this case the former read handler.

Ok, having seen an example of how perform should manipulate the Call Stack. Let's put it into actual code

function perform(type, data) {
  return performGen => {
    // finds the closest handler for effect `type`
    let withHandlerGen = performGen;
    while (
      withHandlerGen._handler == null ||
      !withHandlerGen._handler.hasOwnProperty(type)
    ) {
      if (withHandlerGen._return == null) break;
      withHandlerGen = withHandlerGen._return;
    }

    if (
      withHandlerGen._handler == null ||
      !withHandlerGen._handler.hasOwnProperty(type)
    ) {
      throw new Error(`Unhandled Effect ${type}!`);
    }

    // found a handler, get the withHandler Generator
    const handlerFunc = withHandlerGen._handler[type];

    const handlerGen = handlerFunc(data, function resume(value) {
      return currentGen => {
        withHandlerGen._return = currentGen;
        runGenerator(performGen, value);
      };
    });

    // will return to the parent of withHandler
    handlerGen._return = withHandlerGen._return;
    runGenerator(handlerGen, null);
  };
}

The key code is

function resume(value) {
  return currentGen => {
    withHandlerGen._return = currentGen;
    runGenerator(performGen, value);
  };
}

It gives its meaning to the line const result = yield resume("Stranger") in the handler code. Especially, withHandlerGen._return = currentGen delimits the continuation starting from performGen (the Generator that performed the effect) to currentGen (the Generator that executed yield resume(...)).

You may have noticed how the implementation of withHandler/perform looks similar to shift/reset from the previous post:

reset puts a special mark on a satck frame
withHandler installs a handler on a stack frame
shift finds the closest reset and becomes the direct child of reset's parent
perform finds the closest & matching withHandler, the matching handler becomes the direct child of withHandler's parent
shift captures all the intermediate frames and reifies them into an argument to its computation
perform captures all the intermediate frames and reifies them into an argument to the matching handler

In fact, Algebraic Effects can be seen as a more structured alternative to delimited continuations.

Voilà, that's all mechanics of Algebraic Effects in action. In the remaining of this post, we'll see some more examples.

Example 1: reverse logging

Our first example will be a log handler that prints the logged messages in the reverse order. It may look a little fancy, but should give us a more firm understanding of the mechanics.

function log(msg) {
  return perform("log", msg);
}

const reverseLog = {
  *log(msg, resume) {
    yield resume();
    console.log(msg);
  }
};

function* main() {
  return yield withHandler(reverseLog, parent());
}

function* parent() {
  yield child();
}

function* child() {
  yield log("A");
  yield log("B");
  yield log("C");
}

Let's see the Call stack before performing the first log effect

main() -> withHandler({reverseLog}) -> parent() -> child()

After yield log("A")

main() -> log("A", <<withHandler({reverseLog}) -> parent() -> child()>>)

The handler invokes the continuation before logging the message so

main() -> log("A", <<>>) -> withHandler({reverseLog}) -> parent() -> child()

After yield log("B")

main() -> log("A", <<>>) -> log("B", <<withHandler({reverseLog}) -> parent() -> child()>>)

Again the second handler instance invokes the continuation before logging, so

main() -> log("A", <<>>) -> log("B", <<>>) -> withHandler({reverseLog}) -> parent() -> child()

After yield log("C")

main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<withHandler({reverseLog}) -> parent() -> child()>>)

After the third handler instance invokes the continuation

main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>) -> withHandler({reverseLog}) -> parent() -> child()

child(), parent(), withHandler({reverseLog}) terminate successively, which results in the following Call Stack

main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>)

The logs will now resume starting from rightmost stack frame, which prints the messages in the reverse order.

Example 2: collecting logs

This one collects the logs in an array instead of logging them

const collectLogs = {
  return(x) {
    return [x, ""];
  },
  *log(msg, resume) {
    const [x, acc] = yield resume();
    return [x, `${msg} {acc}`];
  }
};

function* main() {
  return yield withHandler(collectLogs, parent());
}

function* parent() {
  return yield child();
}

function* child() {
  yield log("A");
  yield log("B");
  yield log("C");
  return 10;
}

start(main(), console.log);
// => [10, "A B C "]

After the third handler instance invokes the continuation, we endup with

main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>) -> withHandler({collectLogs}) -> parent() -> child()

child() returns 10 to parent(), which returns the same value to withHandler({collectLogs})

main() -> log("A", <<>>) -> log("B", <<>>) -> log("C", <<>>) -> withHandler({collectLogs})

Since collectLogs has defined a return clause, the value will be processed by the matching handler, which results in withHandler({collectLogs}) returning [10, ""] to its parent log("C"). This one concats "" (acc) with "C" (msg) and returns [10, "C "] to log("B"). The whole process results in [10, "A B C "] being returned

Combining handlers

Here we compose the two precedent handlers

const reverseLog = {
  *log(msg, resume) {
    yield resume();
    console.log(msg);
    yield log(msg);
  }
};

const collectLogs = {
  return(x) {
    return [x, ""];
  },
  *log(msg, resume) {
    const [x, acc] = yield resume();
    return [x, `${msg} ${acc}`];
  }
};

function* main() {
  return yield withHandler(collectLogs, withHandler(reverseLog, parent()));
}

// ... rest unmodified

start(main(), console.log);
// => C
// => B
// => A
// => [undefined, "C B A "]

The first handler prints the message in the reverse order, then forwards the log effect to collectLogs, since the logs are forwarded in the reverse order, they endup collected also in the reverse order.

Conclusion

There are many other examples (state, async, ...). Some simple ones could be found here. If you feel more adventurous, you can consult this collection of ocaml examples (not all of them would be applicable in JavaScript).

This concludes our series about Algebraic Effects & Handlers. Hope it wasn't too booring, and thanks again for being a patient reader!

Some references

An Introduction to Algebraic Effects and Handlers using Eff language
A talk about Algebraic Effects using the language Koka
What's algebraic about Algebraic Effects, if you feel more adventurous. (hint: In programming world, the arity of an algebraic operation isn't the number of params but the number of the possible outcomes, the interpretation I^A -> I can be translated into (A -> I) -> I (function == exponential) which is also the siganture of a CPS function that invokes its continuation (A -> I) with a value of type A, the same siganture of a handler, example: a boolean type has 2 possible outcomes Bool -> I -> I can be seen as I^2 -> I; please don't ask me more!)

Algebraic Effects in JavaScript part 3 - Delimited Continuations

Yassine Elouafi — Sat, 06 Oct 2018 11:42:54 +0000

This is the third part of a series about Algebraic Effects and Handlers.

Part 1 : continuations and control transfer
Part 2 : Capturing continuations with Generators
Part 3 : Delimited continuations
Part 4 : Algebraic Effects and handlers

In the preceding parts, we introduced the notions of continuations and control transfer. We saw how to capture the current continuation inside a Generator, and illustrated how to implement (the one shot version) of the famous callcc.

In this part, we're going to see how to capture delimited continuations with Generators. While callcc allowed us to capture the rest of the whole program, we can also choose to capture only a slice of it. One of the direct consequences of this concept is that delimited continuations can now return a value, and thus they can be composed inside the flow of another function. This is an important trait that will be exploited in the next part.

Back to the Call Stack

In direct style, we saw that control transfer between functions works through the Call Stack.

Each function call pushes a new frame (called also an activation record) onto the stack
Each function return pops the corresponding frame from the stack

Let's consider the following example, which computes the product of an array of numbers

function main() {
  const result = product([2, 4, 6]);
  return result;
}

function product(xs) {
  if (xs.length === 0) return 1;
  const [y, ...ys] = xs;
  return y * product(ys);
}

To visualize the call stack at a given moment, we can set a breakpoint in the browser devtools then run the above example in the console. The program will pause and we can examine the Call Stack panel of the browser

Here, the program is paused on the third line of product(). The Call Stack contains already four frames:

anonymous can be seen as the root frame of the browser console session
main corresponds to the main() call executed in the console
The first product frame represents product([2, 4, 6]) executed in main
The second product frame represents the recursive call inside the return y * product(ys) statement (ie return 2 * product([4,6]))

In other words, the Call Stack tells us what part of the work has already been done. It tells us, also, what part of the work remains to do:

The rest of the work to do inside the current frame (product([4,6])), namely calling product([6]), multiplying the result by y (= 4) then returning the result (24) to the parent frame
Plus the rest of the work to do in the parent frames:
- the call frame of product([2,4,6]) will multiply the previous result by 2 then returns 48 to the main frame
- The call frame of main() will simply return the result 48 to its parent frame
- The call frame of anonymous will display the result into the console

In other words, the continuation is mainly represented with the state of the Call Stack at the considered moment of
execution. Therefore, if we could implement something similar to the Call Stack on top of Generators we'll be able, in principle,
to capture current continuations.

Contrast this with the CPS representation of the continuation as an ordinary function. This stateless representation may be seen as superior (to the Call Stack's statefull representation) since it brings us closer to purity. However, the Call Stack representation has some advantages as well:

It's easier to implement more advanced stack manipulations, like delimited continuations, using the statefull representation (possible because JavaScript is single threaded)
It's easier to add DX features on top of the statefull approach. For example, a babel plugin can instrument the code to add some useful information (function name, line, column) to the stack frames, and some program API can dump this information in developer mode.

Modeling the Call Stack with Generators

Below is a new implementation using the statefull approach

function isGenerator(x) {
  return x != null && typeof x.next === "function";
}

function runGenerator(gen, arg) {
  const { value, done } = gen.next(arg);

  if (done) {
    const _return = gen._return;
    if (isGenerator(_return)) {
      runGenerator(_return, value);
    } else if (typeof _return === "function") {
      _return(value);
    }
  } else {
    if (isGenerator(value)) {
      value._return = gen;
      runGenerator(value, null);
    } else if (typeof value === "function") {
      value(gen);
    }
  }
}

function start(gen, onDone) {
  gen._return = onDone;
  runGenerator(gen, null);
}

Instead of passing a continuation argument, we now rely on the presence of a _return field in the Generator, which represents the parent frame (it may be safer to use a Symbol here). When the Generator is done, it passes the return value to its caller. When we call a child Generator, we set its _return to the current Generator.

Note also that we're now passing the Generator itself to the yielded function. So to implement something like sleep(millis) we have to write

function sleep(ms) {
  return function(gen) {
    setTimeout(x => runGenerator(gen, null), ms);
  };
}

In the statefull implementation, we're effectively building a linked list of Generators (with a callback inserted at the root by start).

The implementation of callcc can be also automatically adapted

function callcc(genFunc) {
  return function(capturedGen) {
    // this is our escape function
    function jumpToCallccPos(value) {
      // instead if resuming the current generator
      // we directly resume the one captured by callcc
      return next => runGenerator(capturedGen, value);
    }
    const gen = genFunc(jumpToCallccPos);
    gen._return = capturedGen;
    runGenerator(gen, null);
  };
}

Ok, now that we have reified the Call stack as a concrete data structure, we're ready to tackle delimited continuations.

Delimited Continuations

We'll introduce how delimited continuations work step by step through a series of examples.

We said that delimited continuations capture only a slice of the Call Stack. Our first step will be, then, some way to mark a stack frame as the limit of the continuation to be captured. This is the purpose of reset

function reset(genFunc) {
  return function(parentGen) {
    const gen = genFunc();
    gen._return = parentGen;
    // setting the limit of the continuation
    gen._reset = true;
    runGenerator(gen, null);
  };
}

reset takes a Generator function and returns a suspended computation (here a function taking the parent Generator). Like runGenerator, the suspended computation will run the provided Generator function after setting its _return field to the caller Generator. It also adds a special _reset field, which acts as a marker on the Call Stack. This field will serve us to limit the extent of the captured continuation as we'll see later.

The first thing to note is that, when invoked on an 'ordinary' Generator, reset amounts to a simple Generator call

function* main() {
  const result = yield reset(function*() {
    return "Hi";
  });
  return result;
}

start(main(), console.log);
// => Hi

So alone, reset is pretty useless. The interesting stuff happens when we introduce our next function shift inside a reset block.

We'll first introduce a simplified version of shift that doesn't capture the current continuation

function shift(genFunc) {
  return function(parentGen) {
    // finds the closest reset
    let resetGen = parentGen;
    while (!resetGen._reset) {
      resetGen = resetGen._return;
    }
    const gen = genFunc();
    // gen will directly return to the parent of reset
    gen._return = resetGen._return;
    runGenerator(gen, null);
  };
}

Here's an example of how it works

function* main() {
  const result = yield reset(function* resetFn() {
    const name = yield child();
    return "Hi " + name;
  });
  return result;
}

function* child() {
  const result = yield shift(function* shiftFn() {
    return "from inside shift";
  });
  return result;
}

start(main(), console.log);
// => from inside shift

In a normal sequence of calls, we'd expect the result to be 'Hi from inside shift'. However, shift isn't an ordinary function. In the above code, the Generator provided to shift will return, directly, to the parent of the closest reset block. In this case, it effectively behaves as our previous exit function. More concretely, w've transformed the following Call Stack

main() -> reset(resetFn) -> child() -> shift(shiftFn)

into this one

main -> shiftFn()

Put another way, we've discarded all the stack frames between shift and (including) reset.

What happens to the discarded frames? Well, here's the more interesting stuff, those would constitute the delimited continuation that should be provided to shift.

function shift(genFunc) {
  return function(parentGen) {
    // finds the closest reset
    let resetGen = parentGen;
    while (!resetGen._reset) {
      resetGen = resetGen._return;
    }

    function delimitedCont(value) {
      // captures the continuation from after shift up to reset
      return nextGen => {
        resetGen._return = nextGen;
        // resume from the shift's parent frame
        runGenerator(parentGen, value);
      };
    }

    const gen = genFunc(delimitedCont);
    gen._return = resetGen._return;
    runGenerator(gen, null);
  };
}

It may seem confusing how this works, so let's go step by step on a simple example

function* main() {
  const x = yield reset(function* resetFn() {
    const a = 10;
    const b = yield shift(function* shiftFn(k) {
      const c = yield k(2);
      return c + 3;
    });
    return a * b;
  });
  return x;
}

The sequence of calls until shift corresponds to

main() -> #resetFn() -> shift(shiftFn)

Where # is used to mark the reset position. We saw that the first effect of shift is to discard the frames up to the enclosing reset

main() -> shift(shiftFn) -> ...

Then the discarded frames (here #resetFn()) are provided as a continuation to shiftFn. So after the yield k(2) we obtain the following sequence

main() -> shiftFn(k) -> #resetFn()

What does #resetFn() corresponds to? it's the rest of work to do after the shift position: namely setting b with some provided value then multiplying by a (= 10). ie it's like a function: (v => a * v) -> (2 * 10) -> 20

After #resetFn() returns, shift continues by adding the obtained result 20 to 3. The final result is then 23.

Naturally, you have all the right to ask the legitimate question: why do we have to program in such a confusing style?

We have the choice between two answers:

I can repeat the arguments from the previous parts about how this can give control-flow super-powers. Which is partly true, but maybe not too concrete.

Or, you can read the next (and final) part: this time we'll be really talking about Algebraic Effects and Handlers.

Algebraic Effects in JavaScript part 2 - Capturing continuations with Generators

Yassine Elouafi — Sat, 06 Oct 2018 11:36:09 +0000

This is the second part of a series about Algebraic Effects and Handlers.

Part 1 : continuations and control transfer
Part 2 : Capturing continuations with Generators
Part 3 : Delimited continuations
Part 4 : Algebraic Effects and handlers

In the first post we introduced the notions of continuation and control transfer. We saw how programs written in Continuation Passing Style (CPS) are more flexible in terms of control transfer manipulation. While, in direct style, control transfer is implicitly managed by the compiler via the call stack, in CPS continuations are reified as first class arguments to CPS functions.

However, a major drawback of CPS programs is that they are harder to read and write by humans, so they are more suitable to be manipulated by other programs like compilers or interpreters. This is why programming languages that expose continuations often provide a direct style syntax/API to manipulate them.

In this part, we'll do the same in JavaScript. Although the language doesn’t provide a way to access continuations we can always [try to] emulate them using Generator functions.

This post assumes the reader is familiar with Generator functions.

Driving Generators in direct style

Say we have this simple function

function greet(name) {
  const message = `Hi ${name}`;
  return message;
}

greet("Stranger");
// => "Hi Stranger"

Running this function is as simple as const result = greet(someString). Now if we take the Generator version

function* greet(name) {
  const message = yield `Hi ${name}`;
  return message;
}

greet("Stranger");
// => greet { <suspended>, __proto__: Generator, ... }

We get only the Generator object. In order to get the result we need to step the Generator until it's done. Below is the code for a function that drives the Generator and returns its result

function runGenerator(gen, arg) {
  const { done, value } = gen.next(arg);
  if (done) {
    return value;
  }
  return runGenerator(gen, value);
}

runGenerator(greet("Stranger"));
// => "Hi Stranger"

Works greet, but just like normal functions can call other normal functions, we'd like also for our Generators to call other Generators. For example, this is the Generator version of the factorial function

function* factorial(n) {
  if (n === 0) return 1;
  const n1 = yield factorial(n - 1);
  return n * n1;
}

runGenerator(factorial(10));
// => NaN

Fortunately, Generators allow us to intercept yielded values. This gives us the ability to interpret those values as desired then resume the Generator with the result of the interpretation.

In our case, interpreting child generators amounts to recursively running them and getting their result.

function isGenerator(x) {
  return x != null && typeof x.next === "function";
}

function runGenerator(gen, arg) {
  const { done, value } = gen.next(arg);
  if (done) {
    return value;
  }
  // interpret calls to child Generators
  if (isGenerator(value)) {
    const result = runGenerator(value);
    return runGenerator(gen, result);
  }
  return runGenerator(gen, value);
}

runGenerator(factorial(10));
// => 3628800

So far, we can call a Generator like a normal function, which includes nested and recursive calls. It seems like we've been able to emulate the call stack. Note here we're just reusing the underlying JavaScript call stack.

However, as we saw in the previous post, direct style can't deal with the async problem. CPS allows us to perform asynchronous calls but that comes with a price. Our next step is to allow those calls while still preserving the direct style.

Driving Generators in CPS

Let's say we want to implement a sleep function that, when yielded in a Generator, will pause its execution for some time

function* slowDouble(x) {
  yield sleep(2000);
  return x * 2;
}

In its current form, runGenerator is unable to implement the sleep behavior because it runs recursively/synchronously until completion.

In order to allow async calls, we need to rewrite the function in CPS: remember in this style we don't return function results, instead we pass them to the provided continuation(s)

function runGenerator(gen, arg, next) {
  const { done, value } = gen.next(arg);
  if (done) {
    next(value);
  } else if (isGenerator(value)) {
    runGenerator(value, null, function(result) {
      runGenerator(gen, result, next);
    });
  } else {
    runGenerator(gen, value, next);
  }
}

But we're not there yet. So far we can only yield child generators or plain values. We need a way to represent async calls and we need to interpret the given representation.

A simple solution is to represent async calls themselves as CPS functions. Let's say we write a CPS sleep version

function sleep(millis, next) {
  setTimeout(next, millis);
}

If we curry it

function sleep(millis) {
  return next => setTimeout(next, millis);
}

The curried version is more suitable to use with runGenerator. We can simply plug in a continuation that will resume the Generator with the async result. More generally, we'll represent async calls with functions taking a single callback. We'll call those functions suspended computations.

function runGenerator(gen, arg, next) {
  const { done, value } = gen.next(arg);
  if (done) {
    next(value);
  } else if (isGenerator(value)) {
    runGenerator(value, null, function continuation(result) {
      runGenerator(gen, result, next);
    });
  } else if (typeof value === "function") {
    // here we handle suspended computations
    value(function continuation(result) {
      runGenerator(gen, result, next);
    });
  } else {
    runGenerator(gen, value, next);
  }
}

runGenerator(slowDouble(10), null, console.log);
// tic tac toc
// 20

For readers already familiar with async implementation on top of Generators, this seems just like the old plumbing trick. But observe that the callback we provided to the suspended computation represents the continuation of the whole program, so now we have the full control over what to do next. Put another way, we gain the flexibility of CPS while still writing direct style code.

As a simple illustration, here is an example that simulates debugger's break. Instead of invoking the continuation, we save it in a variable and then pause the whole program.

let resume;

const BREAK = next => {
  console.log("**PAUSED**");
  resume = next;
};

function* main() {
  yield breakTest();
  yield sleep(1000);
  console.log("end of main");
}

function* breakTest() {
  for (let i = 1; i < 5; i++) {
    yield sleep(1000);
    console.log("message", i);
    if (i % 2 === 0) yield BREAK;
  }
}

// typing this in the console
runGenerator(main(), null, console.log);
/*
  message 1
  message 2
  **** PROGRAM PAUSED ****
*/
resume();
/*
  message 3
  message 4
  **** PROGRAM PAUSED ****
*/
resume();
// end of main

Another example would be an exit(result) function that, when yielded from inside a deeply nested Generator, would skip all the parents and abort the whole computation with the given result. For example consider the following code

function* main() {
  const result = yield parent();
  return `main result: (${result})`;
}

function* parent() {
  const result = yield child();
  return `parent result: (${result})`;
}

function* child() {
  return "child result";
}

runGenerator(main(), null, console.log);
// => main result: (parent result: (child result))

Using exit we could abort directly from inside child

function main() { ... }

function parent() { ... }

function* child() {
  yield exit("child result");
  throw "This shouldn't happen";
}

runGenerator(main(), null, console.log);
// should be => child result

If you recall the interpreter example in the previous post, at some point we did the same thing by providing the top-level continuation as a second argument to all child CPS functions. We can do the same trick here with runGenerator. It would be a good exercise.

The road to undelemited continuations

Ok, I assume, with good faith, that you did the last exercise. Here is ~the~ my solution

function runGenerator(gen, arg, abort, next) {
  const { done, value } = gen.next(arg);
  if (done) {
    next(value);
  } else if (isGenerator(value)) {
    runGenerator(value, null, abort, function continuation(result) {
      runGenerator(gen, result, abort, next);
    });
  } else if (typeof value === "function") {
    value(abort, function continuation(result) {
      runGenerator(gen, result, abort, next);
    });
  } else {
    runGenerator(gen, value, abort, next);
  }
}

// helper function to thread in the top-level continuation
function start(gen, next) {
  runGenerator(gen, null, next, next);
}

start(main(), console.log);
// => child result

It works, but it's not very satisfactory. We said that the promise of CPS is to empower us, end users of the API, so we can implement various control operators. But in the above solution, the control is hard coded inside the interpreter (runGenerator). We don't want to modify the interpreter each time we want to add some control construct and more importantly we don't want to implement our solutions in low level CPS code. What w're really aiming for is to provide some more general API in order to implement exit or other control flow in user land.

Let's go step by step. First, observe that what start does, essentially, is capturing the top-level continuation. But we know we can capture a continuation by yielding a suspended computation in the Generator. So, our first step would be capturing the top-level continuation.

For that, We'll make start itself a Generator and capture its continuation.

function* start(genFunc) {
  const result = yield function(abort) {
    runGenerator(genFunc(abort), null, abort);
  };
  return result;
}

We're using runGenerator manually, which is a little awkaward, but this leaves our interpreter unmodified. Later we'll see how to abstract away this code.

Next, we observe that the captured continuation is just passed as an additional argument to the nested runGenerator calls in order to keep it visible in the current scope. We can do the same by exploiting the lexical scope of Generators and passing the captured continuation as an argument to child Generators.

Our first tentative of refactoring yields the below code

function* start(genFunc) {
  const result = yield function(abort) {
    runGenerator(genFunc(abort), null, abort);
  };
  return result;
}

function* main(abort) {
  const result = yield parent(abort);
  return `main result: (${result})`;
}

function* parent(abort) {
  const result = yield child(abort);
  return `parent result: (${result})`;
}

function* child(abort) {
  yield next => abort("child result");
  throw "This shouldn't happen";
}

runGenerator(start(main), null, console.log);
// => child result

By the way, notice how, in child, the next continuation is ignored in the body of the suspended computation, which instead invokes abort. It means the next statement throw "This shouldn't happen" won't be executed and the control will jump back directly into the start Generator.

But we're not there yet, how can we implement the generic exit(result) function?

Well, given the current code, we can't. Our exit has no way to get the abort continuation without this being visible in scope. Surely this is awkward, we don't want to end up writing yield next => abort(result) each time we want to exit.

There is less awkward alternative, though. Instead of forwarding the captured continuation itself, then creating the suspended computation (exit) inside the exiting function, we can create exit itself inside the code that captures the top-level continuation (here in the start Generator), then pass it to child Generators.

function* start(genFunc) {
  const result = yield function(abort) {
    function exit(value) {
      return next => abort(value);
    }
    runGenerator(genFunc(exit), null, abort);
  };
  return result;
}

function* main(exit) {
  const result = yield parent(exit);
  return `main result: (${result})`;
}

function* parent(exit) {
  const result = yield child(exit);
  return `parent result: (${result})`;
}

function* child(exit) {
  yield exit("child result");
  throw "This shouldn't happen";
}

runGenerator(start(main), null, console.log);
// => child result

All we need, in order to complete the refactoring, is to abstract away the code that captures the top-level continuation inside a reusable function. But first we need to pick a suitable name for it. call_with_current_continuation looks expressive but quite verbose, so let's abbreviate it to callcc.

function callcc(genFunc) {
  return function(capturedCont) {
    // this is our previous exit
    function jumpToCallccPos(value) {
      return next => capturedCont(value);
    }
    runGenerator(genFunc(jumpToCallccPos), null, capturedCont);
  };
}

function* start() {
  const result = yield callcc(main);
  return result;
}

// rest of the code unmodified

runGenerator(start(), null, console.log);
// => child result

Note that, unlike what's found in languages like Scheme, our implementation allows only one invocation of the callcc continuation. We're here constrained by how Generators work in JavaScript. Each call to generator.next() is a one way ticket, so invoking the continuation multiple times will just keep advancing the Generator. Continuations that can be resumed only once are said to be one shot. Continuations that can be resumed many times are said to be multi shot.

In this series, we'll content ourselves with one shot continuations. If you're interested in how we could emulate multi shoot continuations Here is an example. Note this has a non negligible space/time cost.

The rest of the post illustrates the use of callcc with a couple of common examples.

Example 1: Emulating try/cacth

The previous exit example implemented a simplified version of exceptions. Next, we'll try to make a more elaborated example of structured
exception handling

const handlerStack = [];

function* trycc(computation, handler) {
  return yield callcc(function*(k) {
    handlerStack.push([handler, k]);
    const result = yield computation;
    handlerStack.pop();
    return result;
  });
}

function* throwcc(exception) {
  const [handler, k] = handlerStack.pop();
  const result = yield handler(exception);
  yield k(result);
}

trycc/throwcc emulates the try/catch/throw statements. trycc starts by capturing the current continuation, saves it in a stack along with the handler, then run the computation, which may (or may not) throw. If the computation returns successfully then no exception was thrown and we can remove the handler from the stack. In the case the computation has invoked throwcc then we also pop the handler stack along with the captured continuation, run the handler then use the captured continuation to jump back to where trycc was called.

Example 2: cooperative scheduling

Another popular example is the implementation of cooperative scheduling using what we call coroutines. They are somewhat similar to Generators. Once started, a coroutine executes some code then may yield to a central scheduler. The scheduler will save the state of the coroutine then pick another coroutine to run. Below is an example

function* main() {
  yield fork(proc("1", 4));
  yield fork(proc("2", 2));
  yield dequeue();
  console.log("end main");
}

function* proc(id, n) {
  for (let i = 0; i <= n; i++) {
    yield sleep(1000);
    console.log(id, i);
    yield pause;
  }
}

Assuming we have implemented fork and pause, the result of running main() gives the following outputs

A possible implementation of coroutines is given below

const processQueue = [];

function fork(gen) {
  return next => {
    processQueue.push(
      (function*() {
        yield gen;
        yield dequeue();
      })()
    );
    next();
  };
}

const pause = callcc(function*(k) {
  processQueue.push(k());
  yield dequeue();
});

function* dequeue() {
  if (processQueue.length) {
    const next = processQueue.shift();
    yield next;
  }
}

Here's how the above code works

fork doesn't start the provided coroutine immediately, it just adds it to a global queue of processes
pause saves the state of the current coroutine by capturing its continuation, adding it to the process queue then picking the next coroutine to resume
dequeue is called both when a coroutine pauses and when it returns

Conclusion

Voilà! we reached the end of the second part. Just a couple more of posts to complete the understanding Algebraic Effects and Handlers.

Main takeaways of this part:

When driven using dierct style, Generators can emulate the call stack, but can't support async calls
When driven using CPS, Generators can perfom async work while still allowing the user to program in direct style
More important, we can capture the current contiuation of the program anytime we need it (callcc)
When the callcc continuation is invoked it aborts the current execution context and resumes from when callcc was invoked

Although callcc is quite powerful, it has a major limitation. The captured continuation represents the rest of the whole program. It means the yield k(someValue) can't return values since all we can do is resume until the program completes. This kind of continuations is known as undelimited continuations.

Next part, we'll see an even more powerful kind: delimited continuations, which allow us to capture only a slice of the rest of the program. A delimited continuation can return a value and thus it can be composed inside other functions.

See you next post. Thanks for being a patien reader!

Algebraic Effects in JavaScript part 1 - continuations and control transfer

Yassine Elouafi — Sat, 06 Oct 2018 11:17:05 +0000

This is the first post of a series about Algebraic Effects and Handlers.

There are 2 ways to approach this topic:

Denotational: explain Algebraic Effects in terms of their meaning in mathematics/Category theory
Operational: explain the mechanic of Algebraic Effects by showing how they operate under a chosen runtime environment

Both approaches are valuables and give different insights on the topic. However, not everyone (including me), has the prerequisites to grasp the concepts of Category theory and Universal Algebra. On the other hand, the operational approach is accessible to a much wider audience of programmers even if it doesn't provide the full picture.

So we'll take the operational road. We'll work out our way through a series of examples and build, progressively, the intuition on the introduced concepts. By the end of this series, we'll have a working implementation of Algebraic Effects based on JavaScript Generators.

Since this is going to be a long topic, we'll split it in 4 parts:

First we need to familiarize with the concepts of Continuations and Control Transfer
Next post we'll see how to use Generators to capture Continuations
Then we'll see how to delimit the extent of continuations
Finally we'll see the mechanics behind Algebraic Effects and Handlers

Direct Style vs Continuation Passing Style

In this part, we'll build our concepts around the example of a simple interpreter for a small functional language. The language will support numbers, addition and calling functions that return other expressions.

We'll use the following functions to build the AST (Abstract Syntax Tree) that will be passed to the interpreter:

function fun(param, body) {
  return { type: "fun", param, body };
}

function call(funExp, argExp) {
  return { type: "call", funExp, argExp };
}

function add(exp1, exp2) {
  return { type: "add", exp1, exp2 };
}

// example
const doubleFun = fun("x", add("x", "x"));
program = call(doubleFun, 10);

The interpreter takes an AST like above and returns a final value. Final values mirror atomic expressions, which don't require further evaluation (here a number or fun) and are objects of the target language (here JavaScript), we'll represent numbers as is and fun expressions with JavaScript functions.

To evaluate a program, the interpreter takes, in addition to the program AST, an environment that maps variable names to their values. We'll use a plain JavaScript Object to represent the environment.

Below a possible implementation for the interpreter:

function evaluate(exp, env) {
  if (typeof exp === "number") {
    return exp;
  }
  if (typeof exp === "string") {
    return env[exp];
  }
  if (exp.type === "add") {
    return evaluate(exp.exp1, env) + evaluate(exp.exp2, env);
  }
  if (exp.type === "fun") {
    return function(value) {
      const funEnv = { ...env, [exp.param]: value };
      return evaluate(exp.body, funEnv);
    };
  }
  if (exp.type === "call") {
    const funValue = evaluate(exp.funExp, env);
    const argValue = evaluate(exp.argExp, env);
    return funValue(argValue);
  }
}

evaluate(program);
// => 20

Here's how evaluate works:

Simple numbers are returned as is
Variables are resolved from the current environment. We don't handle unknown variables for now
Addition recursively evaluates its operands and returns the sum of the evaluated results
For the function case, we return a JavaScript function that will be called with a final value (the result of some other evaluation). When invoked, the function will build a new environment in which the fun param is bound to the provided value, then it evaluates the fun body in this new environment
The call case is similar to add we evaluate the function and argument expressions recursively then apply the function value to the argument value

evaluate is said to be written in direct style. This is not something specific to interpreters. A program that is in direct style simply means that the functions communicate their results via return statement. For example this simple function is also in direct style:

function add(x, y) {
  return x + y;
}

In contrast, in the Continuation Passing Style (CPS):

The function takes a callback as an additional argument
The function never returns its result. It always uses the callback to communicate its result
Contrary to what you may think. Originally, it has nothing to do with async Node.js functions

For example, converted to CPS, the previous function becomes:

function add(x, y, next) {
  const result = x + y;
  return next(result);
}

The provided callback is also called a continuation, because it specifies what to do next in the program. When a CPS function terminates, it throws the result on its continuation.

Recommended: as a quick exercise, try to convert the interpreter into CPS form. Start by adding the continuation parameter to the signature of evaluate.

Solution:

function evaluate(exp, env, next) {
  if (typeof exp === "number") {
    return next(exp);
  }
  if (typeof exp === "string") {
    return next(env[exp]);
  }
  if (exp.type === "add") {
    return evaluate(exp.exp1, env, function addCont1(val1) {
      return evaluate(exp.exp2, env, function addCont2(val2) {
        return next(val1 + val2);
      });
    });
  }
  if (exp.type === "fun") {
    // notice the function value becomes a CPS itself
    const closure = function(value, next) {
      const funEnv = { ...env, [exp.param]: value };
      return evaluate(exp.body, funEnv, next);
    };
    return next(closure);
  }
  if (exp.type === "call") {
    return evaluate(exp.funExp, env, function callCont1(funValue) {
      return evaluate(exp.argExp, env, function callCont2(argValue) {
        return funValue(argValue, next);
      });
    });
  }
}

function run(program) {
  return evaluate(program, {}, x => x);
}

Here are the things to notice:

Every return statement either calls the continuation or another CPS function
All those calls are in tail call position
In the case we need to evaluate multiple expressions (add and call cases) we chain those evaluations by providing intermediate continuations which capture the intermediate results. When the chaining is terminated we throw the result onto the main continuation
Life is better with direct style

At this stage, the program is already harder to read. So you're probably asking

why would we want write a program in such style?

Short answer: you don't. But that doesn't make CPS useless.

There are various reasons which make CPS useful and even preferable, but not all of them are applicable to JavaScript (in its current status).

First and foremost is control. In the direct style version, the caller controls what to do next, the continuation is implicit and hidden from us. In the CPS version, however, the continuation is made explicit and passed as argument, the callee can decide what to do next by invoking the continuation. As we'll see in the next section, CPS can be used to implement various control flows that are not possible with direct style
Second all function calls are in tail call position in CPS. Tail calls don't need to grow the call stack (explained in next section). Since there is nothing to do after the tail call, the execution context doesn't have to be saved before performing the tail call. A compiler can optimize those tail calls by directly replacing the current execution context with the one of the function been called (instead of pushing it on top of the current one). This process is known as tail call elimination and is heavily exploited by functional compilers. Unfortunately, current JavaScript engines dot not all implement tail call elimination despite being part of the ECMAScript specification
And the most important of course is the required Asynchrony due the single threaded nature of JavaScript. If we were to use direct style functions to perform remote requests, we would have to suspend the only thread we have until the request is fulfilled, blocking the process on the current statement and preventing any other interaction meantime. CPS provides a handy and efficient way to fork some work, so the current code can continue to execute and handle other interactions. In fact, one may consider this as the only practical reason to use that style in JavaScript
Finally, CPS is quite powerful but not something meant to be used directly by humans. It's a more suitable target for compilers or interpreters. Our brain is more comfortable with the structured direct style. So while we wont be writing in CPS ourselves, it's still a powerful tool use by an interpreter behind the scene. In the upcoming posts, we'll see how we exploit the power of CPS behind the scenes to present a more powerful direct style API

For our purpose, reasons 1, 3 and 4 apply. We need a more flexible control about the code and we need to handle the async problem while still recovering back the direct style.

Currently, the idiomatic solution in JavaScript is using async/await, this effectively gives us 3 and 4 but not 1. We don't have enough power over control flow.

What is control flow?

control flow is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated (wikipedia).

By default, in an imperative language like JavaScript, statements are executed sequentially (at the CPU level, the instruction pointer is automatically incremented unless you execute a control transfer instruction). But the language also provides some control operators to alter that behavior. For example when we break inside a loop, the control jumps to the first instruction following the loop block. Similarly, an if may skip a whole block if its condition evaluates to false. All those are examples of local control transfer, meaning jumps that occur inside the same function.

An important control transfer mechanism is function invocation. It works thanks to a data structure known as the call stack. this short video gives a good explanation of the mechanism (PS it's worth watching).

Notice how, in the video, the caller pushes the return address which points to the next instruction after the callee returns. This looks very similar to how we provide the continuation as an additional argument to a CPS function. With the call stack, however, we don't have any power over this continuation. When a function terminates, control is automatically transferred back to the caller. In CPS, we do have this power since the continuation is reified as a normal function.

That doesn't mean we're not using the call stack in CPS mode. A CPS call still uses the call stack but doesn't rely on it for control transfer (this is the reason we never return). It means the call stack grows with each step. With a compiler that supports tail call optimization this is a no problem (since CPS calls are always in tail position), but it can be in a language like JavaScript if a significant part of our process is synchronous (like heavy recursive calls). But since we're using CPS mostly here to handle asynchronous calls, we don't have this issue.

Exceptions represent a common form of non local control transfer. A function throwing an exception may cause the control to jump outside to another function located far up in the call hierarchy.

function main() {
  try {
    // ...
    child1();
    // ...
  } catch (something) {
    console.log(something);
  }
}

function child1() {
  // ...
  child2();
  workAfterChild2();
}

function child2() {
  // ...
  throw something;
  //...
}

throw bypasses intermediate function calls in order to reach the closest handler. When we reach the catch clause, all the intermediate stack frames are automatically discarded. In the above example, the remaining workAfterChild2() in the intermediate call to child1 is skipped. Since this is implicitly managed by the compiler, we don't have any way to recover the skipped work. We'll comeback to this mechanism later when talking about Algebraic Effects.

To illustrate how CPS can implement other control flows, we're going to add error handling to our interpreter without relying on native Javascript Exceptions. The trick is to provide, along the normal completion continuation, another one which bypasses the next step and aborts the whole computation.

function evaluate(exp, env, abort, next) {
  if (typeof exp === "number") {
    return next(exp);
  }
  if (typeof exp === "string") {
    if (!env.hasOwnProperty(exp)) {
      return abort(`Unkown variable ${exp}!`);
    }
    return next(env[exp]);
  }
  if (exp.type === "add") {
    return evaluate(exp.exp1, env, abort, function cont1(val1) {
      if (typeof val1 != "number") {
        return abort("add called with a non numeric value");
      }
      return evaluate(exp.exp2, env, abort, function cont2(val2) {
        if (typeof val2 != "number") {
          return abort("add called with a non numeric value");
        }
        return next(val1 + val2);
      });
    });
  }
  if (exp.type === "fun") {
    // notice the function value becomes a CPS itself
    const closure = function(value, abort, next) {
      const funEnv = { ...env, [exp.param]: value };
      return evaluate(exp.body, funEnv, abort, next);
    };
    return next(closure);
  }
  if (exp.type === "call") {
    return evaluate(exp.funExp, env, abort, function cont1(funValue) {
      if (typeof funValue != "function") {
        return abort("trying to call a non function");
      }
      return evaluate(exp.argExp, env, abort, function cont2(argValue) {
        return funValue(argValue, abort, next);
      });
    });
  }
}

function run(program) {
  return evaluate(program, {}, console.error, x => x);
}

run(add("x", 3), 10);
// => Unkown variable x!

run(call(5, 3), 10);
// => 5 is not a function

We'll conclude this part by adding a feature that will give you an early taste on captured continuations: the escape operator.

To see how escape works, consider the following example:

// ie: (x => x + x)(3 + 4)
call(fun("x", add("x", "x")), add(3, 4));

which evaluates to 14. If we wrap it inside the escape operator like this

// escape (eject) in (x => x + x)(3 + eject(4))
escape(
  "eject", // name of the eject function
  call(fun("x", add("x", "x")), add(3, call("eject", 4)))
);

We obtain 4 instead, because the eject function aborts the whole expression with the provided value.

Below are the required additions to our code. The implementation is surprisingly short:

function escape(eject, exp) {
  return { type: "escape", eject, exp };
}

function evaluate(exp, env, abort, next) {
  //...
  if (exp.type === "escape") {
    const escapeEnv = { ...env, [exp.eject]: next };
    return evaluate(exp.exp, escapeEnv, abort, next);
  }
}

run(escape("eject", call(fun("x", add("x", "x")), add(3, call("eject", 4)))));
// => 4

All we need is to bind the eject parameter to the current continuation of the escape expression.

Conclusion

Main takeaways of the first part:

Direct style relies on the call stack for control transfer
In direct style, control transfer between functions is implicit and hidden from us. A function must always return to its direct caller
You can use Exceptions for making non local control transfer
CPS functions never return their results. They take additional callback argument(s) representing the continuation(s) of the current code
In CPS, control transfer doesn't rely on the call stack. It's made explicit via the provided continuation(s)
CPS can emulate both local and non local control transfers but...
CPS is not something meant to be used by humans, hand written CPS code becomes quickly unreadable
Make sure to read the previous sentence

Next part we'll see how to use Generators in order to:

recover back the direct style
Capture the continuation when needed
The difference between undelimited and delimited continuations

Thanks for being a patient reader!

A gentle introduction to parser combinators

Yassine Elouafi — Fri, 05 Oct 2018 21:42:33 +0000

In this tutorial we're going to build a set of parser combinators.

What is a parser combinator?

We'll answer the above question in 2 steps

what is a parser?
and.. what is a parser combinator?

So first question: What is parser?

Answer: (in its simplest form) a parser is a

a function
that takes some input in form of a raw sequence (like a string of characters)
and returns some meaningful data built from the raw input
or some error if the raw input does not conform to what is expected

Here is a very simple example. A parser that takes a string. If the string represents a valid integer it returns that integer, otherwise it returns a parse error.

function parseInteger(input) {
  const match = /^\d+$/.exec(input);
  if (match != null) {
    return +match[0];
  }
  return new Error("Invalid integer");
}

$ parseInteger("12")
  >> 12

$ parseInteger("hey")
  >> Error: Invalid integer

Nice, but what about

$ parseInteger("12hey")
  >> Error: Invalid integer

Because we used ^ & $ our regular expression checks if the entire input is a valid integer. It makes sense if this is the only thing we want to parse. However, very often we want to parse more complicated things.

Sequencing parsers

Here is another example, we want to parse the following sequence

an integer
a '+' character
then another integer

And return the sum of the 2 numbers obtained in (1) and (3)

We'll keep it simple and not allow spaces between the 3 steps. So how do we approach it?

We have already our parseInteger function. We could reuse it somehow with another function parsePlus. But we need to rethink our previous definition.

Let's think about it: to parse the above sequence, we need to run 3 parsers (ie functions) one after another. But it's not as simple as composing simple functions. Passing from one step to another requires some glue code.

first parseInteger will try to parse an integer from the begining of the input
if (1) returns an error then we stop parsing and returns that error
otherwise, we call the second parser with the rest of the string

But to achieve (3) we must get the rest of the string from the first parser. So now our parser function should return

either an error if the parser has failed
or the result plus the rest of the input in case of success

So that with the return value in (2) we can call the next parser in the sequence to parse the rest of the input.

Before rewriting parseInteger let's first make some changes to our parser interface.

// We'll use our own error description
function failure(expected, actual) {
  return { isFailure: true, expected, actual };
}

function success(data, rest) {
  return { data, rest };
}

// And for our main parsing, we'll invoke this function
function parse(parser, input) {
  const result = parser(input);
  if (result.isFailure) {
    throw new Error(`Parse error.
        expected ${result.expected}.
        instead found '${result.actual}'
    `);
  } else {
    return result;
  }
}

Now let's modify the parseInteger function to fit the new interface (from now on we'll use a more concise naming convention: eg ìnteger insetad of parseInteger. It will make our code more readable as we'll be defining more complex parsers)

function integer(input) {
  // note we removed $ from the end of the regular expression
  const match = /^\d+/.exec(input);
  if (match != null) {
    const matchedText = match[0];
    return success(+matchedText, input.slice(matchedText.length));
  }
  return failure("an integer", input);
}

$ parse(integer, "12")
  >> {data: 12, rest: ""}

$ parse(integer, "hey")
  Uncaught Error: Parse error.
        expected an integer.
        instead found 'hey'

$ parse(integer, "12hey")
  >> {data: 12, rest: "hey"}

Fine. Let's write our second parser which parses the '+' character. This one is much simpler

function plus(input) {
  if (input[0] === "+") {
    return success("+", input.slice(1));
  }
  return failure("'+'", input);
}

and 2 quick tests

$ parse(plus, '+33')
  >> {data: "+", rest: "33"}

$ parse(plus, '33+')
  >> Uncaught Error: Parse error.
        expected '+'.
        instead found '33+'

Now we'll write our main parser which will parse the entire sequence

function plusExpr(input) {
  // step 1 : parse the first integer
  const result1 = integer(input);
  if (result1.isFailure) return result1;
  const { data: int1, rest: input1 } = result1;

  // step 2 : parse "+"
  const result2 = plus(input1);
  if (result2.isFailure) return result2;
  const { rest: input2 } = result2;

  // step 3 : parse the second integer
  const result3 = integer(input2);
  if (result3.isFailure) return result3;
  const { data: int2, rest: input3 } = result3;

  // one last check
  if (input3.length > 0) {
    return failure("end of input", input3);
  }
  // everything is allright. returns the final result
  return success(int1 + int2, input3);
}

$ parse(plusExpr, "12+34")
  >> {data: 46, rest: ""}

$ parse(plusExpr, "12a+34")
  >> Uncaught Error: Parse error.
        expected '+'.
        instead found 'a+34'

parse(plusExpr, "12-34")
>> Uncaught Error: Parse error.
        expected '+'.
        instead found '-34'

$ parse(plusExpr, "12+34rest")
  >> Uncaught Error: Parse error.
        expected end of input.
        instead found '12+34rest'

So far so good. But for our parser to be practical we need to make some improvements

we would like to have some resuable way parse more things and not just numbers.
we need also some reusable way to create sequences like in plusExpr. Right now sequencing parsers involves some boilerplate:

at each step we must check if the result is an error to decide whether we should continue or stop
we need also to take care of passing the rest of the input to the next parser

This may not seem too much. But remember that in practice we'll be creating this kind of sequences a lot of time. So abstracting this someway is going to make our life easier.

So first (1). We're going to make a couple of helper functions which create parsers.

The first one will just generate a parser that parses a given a string of characters

function text(match) {
  return function textParser(input) {
    if (input.startsWith(match)) {
      return success(match, input.slice(match.length));
    }
    return failure(`'${match}'`, input);
  };
}

// example
const plus = text("+");

$ parse(plus, "+12")
  >> {data: "+", rest: "12"}

$ parse(plus, "12+")
  >> Uncaught Error: Parse error.
        expected '+'.
        instead found '12+'

Our second helper works like the first one but matches regular expressions instead of plain text

function regex(regex) {
  const anchoredRegex = new RegExp(`^${regex.source}`);

  return function regexParser(input) {
    const match = anchoredRegex.exec(input);
    if (match != null) {
      const matchedText = match[0];
      return success(matchedText, input.slice(matchedText.length));
    }
    return failure(regex, input);
  };
}

const decimal = regex(/\d+(?:\.\d+)?/);

parse(decimal, "12.34")
  >> {data: "12.34", rest: ""}

Hmm... not quite. Our aim is for an actual number 2.3 and not just its textual representation.

We can not blame our regex helper. A regular expression can be used to parse arbitrary data types, it has no idea what kind of data we are expecting. So we need some general way of transforming the textual representation into some meaningful data.

To make it even more 'general' we'll define another helper function which transforms the result of any parser not just regex ones. meet the map function

function map(func, parser) {
  return function mapParser(input) {
    const result = parser(input);
    if (result.isFailure) return result;
    return success(func(result.data), result.rest);
  };
}

const decimal = map(x => +x, regex(/\d+(?:\.\d+)?/));

$ parse(decimal, "12.34")
  >> {data: 12.34, rest: ""}

$ parse(decimal, "a12.34")
  >> Uncaught Error: Parse error.
        expected /\d+(?:\.\d+)?/.
        instead found 'a12.34'

Certainely not the most helpful error message. We'll see later how to improve that.

Now that we defined our primitive parsers. Let's define our sequencing combinator.

We already know that our sequencer needs to take care of error handling and state passing (ie passing the rest of the input) between steps. The last question is: what should be the return value?

There may be multiple answers

we could return just the result of the last step
we could also return an array with the results from all steps
we could apply some given function to the results from all steps and returns the result

If we think about it, we can define (1) and (2) in terms of (3) (another possibility is to take (2) and use it with map but we'll stick with (3)).

Ok. So our combinator will take 2 parameters :

a function that will be applied to the collected results from all parsers
an array of parsers to be sequenced

function apply(func, parsers) {
  return function applyParser(input) {
    const accData = [];
    let currentInput = input;

    for (const parser of parsers) {
      const result = parser(currentInput);
      if (result.isFailure) return result;
      accData.push(result.data);
      currentInput = result.rest;
    }

    return success(func(...accData), currentInput);
  };
}

Our plusExpr parser can now be defined in terms of apply

const plusExpr = apply((num1, _, num2) => num1 + num2, [
  decimal,
  plus,
  decimal
]);

$ parse(plusExpr, "12+34")
  >> {data: 46, rest: ""}

$ parse(plusExpr, "12+34rest")
  >> {data: 46, rest: "rest"}

Oops! we forgot to take care of the end of input.

Never mind. We'll just create a parser for that

function eof(input) {
  if (input.length === 0) return success(null, input);
  return failure("end of input", input);
}

// fix plusExpr
const plusExpr = apply((num1, _, num2) => num1 + num2, [
  decimal,
  plus,
  decimal,
  eof
]);

$ parse(plusExpr, "12+34rest")
  >> Uncaught Error: Parse error.
        expected end of input.
        instead found 'rest'

Using apply we can define helpers for the other possible results of sequencing

// Yeah not the best name I guess
function sequence(...parsers) {
  return apply((...results) => results[results.length - 1], parsers);
}

function collect(...parsers) {
  return apply((...results) => results, parsers);
}

$ parse(
    sequence(text("hello"), text(", "), text("world")),
    "hello, world"
  )
  >> {data: "world", rest: ""}

$ parse(
    collect(text("hello"), text(", "), text("world")),
    "hello, world"
  )
  >> {data: ["hello", ", ", "world"], rest: ""}

Merging parsers

We are going improve our expression parser by allowing more arithmetic operations.

We need to modify plusExpr so that in its 2nd step it can handle other alternatives than '+'.

Ah and as usual we need our solution to be general so that we can allow alternatives between arbitrary parsers and not just from simple strings (so you guessed it, a simple regex wont do it).

You should be used to it now. We need another parser combinator.

function oneOf(...parsers) {
  return function oneOfParser(input) {
    for (const parser of parsers) {
      const result = parser(input);
      if (result.isFailure) continue;
      return result;
    }
    // We'll see later a way to improve error reporting
    return failure("oneOf", input);
  };
}

We're equiped now to make a better experssion parser (and evaluator).

const opMap = {
  "+": (left, right) => left + right,
  "-": (left, right) => left - right,
  "*": (left, right) => left * right,
  "/": (left, right) => left / right
};

function getOp(op) {
  return opMap[op];
}

const op = map(getOp, oneOf(text("+"), text("-"), text("*"), text("/")));

const decimal = map(x => +x, regex(/\d+(?:\.\d+)?/));

const expr = apply((num1, opFunc, num2) => opFunc(num1, num2), [
  decimal,
  op,
  decimal
]);

$ parse(expr, "12-34")
  >> {data: -22, rest: ""}

$ parse(expr, "12*34")
  >> {data: 408, rest: ""}

Works great. But error reporting could be better

$ parse(expr, "a12*34")

>> Uncaught Error: Parse error.
        expected /\d+(?:\.\d+)?/.
        instead found 'a12*34'

parse(expr, "12 + 34")
  >> Uncaught Error: Parse error.
        expected oneOf.
        instead found ' + 34'

And we are not still supporting white spaces.

Proper error reporting for real world parsers includes much more than just printing freindly names for regular expressions or the oneOf pasrers. We need to report the precise location (file, line & column) of the error as well as all the alternatives expected at this location (including from deeply nested parsers).

We ~~will~~ may cover error reporting in more detail in another post. For now our solution will be a simple label helper which decorates a given parser with a user freindly message. The implementation has some pitfalls (more precisely we need to fix lookahead) but will suffice for our current needs

function label(parser, expected) {
  return function labelParser(input) {
    const result = parser(input);
    if (result.isFailure) {
      // replace the parser error with our custom one
      return failure(expected, result.actual);
    }
    return result;
  };
}

const decimal = map(x => +x, label(regex(/\d+(?:\.\d+)?/), "a decimal"));

const expr = apply((num1, opFunc, num2) => opFunc(num1, num2), [
  decimal,
  label(op, "an arithmetic operator"),
  decimal
]);

$ parse(expr, "12 + 34")
  >> Uncaught Error: Parse error.
        expected an arithmetic operator.
        instead found ' + 34'

$ parse(expr, "a12 + 34")
  >> Uncaught Error: Parse error.
        expected a decimal.
        instead found 'a12 + 34'

Our final touch will be to make the parser a little more realisic by skipping white spaces.

// lexeme is a function which takes a parser for 'junk' (eg whitespaces, comments)
function lexeme(junk) {
  // and returns another function which takes a parser for some meaningful data
  return function createTokenParser(parser) {
    // the (second) function returns a parser that
    // parses the menaninful data then skips the junk
    return apply((data, _) => data, [parser, junk]);
  };
}

const spaces = regex(/\s*/);
const token = lexeme(spaces);

// redefine our experssion to skip leading and trailing spaces
const expr = apply((_, num1, opFunc, num2) => opFunc(num1, num2), [
  spaces, // skips leading spaces
  token(decimal),
  token(label(op, "an arithmetic operator")),
  token(decimal), // skips trailing spaces
  eof
]);

$ parse(expr, " 12 + 34 ")
  >> {data: 46, rest: ""}

Yielding parsers

Some of you may know that as the original author of redux-saga
I have a soft spot for generators (which some FP folks see as a restricted do notation but whatever).

Imagine we could use genertaors to write sequences like expr. Instead of apply we could write something like

const expr = go(function*() {
  yield spaces;
  const num1 = yield decimal;
  const opFunc = yield op;
  const num2 = yield decimal;
  yield eof;
  return opFunc(num1, num2);
});

The yield statements embed all the machinery of error handling and state passing. We can write our sequences as if we were calling normal functions.

It doesnt take much more to implement go than apply. The only difference is that instead of stepping over an array of parsers we step over a generator object. The generator yields successive parsers and at the end returns a value which will be returned as the final result of the main parser.

function go(genFunc) {
  return function yieldParser(input) {
    const gen = genFunc();
    let currentInput = input;
    let genResult = gen.next();
    // if not done yet, genResult.value is the next parser
    while (!genResult.done) {
      const result = genResult.value(currentInput);
      if (result.isFailure) return result;
      currentInput = result.rest;
      genResult = gen.next(result.data);
    }
    // if done, genResult.value is the return value of the parser
    return success(genResult.value, currentInput);
  };
}

The generator definition of expr looks more imperative than the apply based one (aka Applicative definition). Some people will prefer the first style, other will prefer the second. 'Generator definitions' (aka Monadic definitions) also allows some things that are not possible with Applicative ones. For example, imagine parsing an html like syntax where each opening tag must have a corresponding closing tag

const openBracket = text("<");
const closeBracket = text(">");

const element = go(function*() {
  // parses opening tag
  yield openBracket;
  const tagName = yield identifier;
  yield closeBracket;
  yield whateverContent;
  yield text(`</${tagName}>`);
});

In the last step, the yielded parser is created dynamically. There is no way to know what will be the closing tag before parsing the opening tag. With apply all parsers must be statically passed (known in advance) so we cant have the above kind of definitions.

Generators can also allow some nice recusive definitions. For example, suppose we want to parse some token as many times as possible

$ parse(many(regex(/\d/)), "123xyz")
  should return >> {data: ["1", "2", "3"], rest: "xyz"}

We can define many using generators like this

// creates a parser that always succeeds with `value` without consuming any input
function pure(value) {
  return function pureParser(input) {
    return success(value, input);
  };
}

function many(parser) {
  const self = oneOf(
    go(function*() {
      const head = yield parser;
      // 1. keep calling self recursively
      const tail = yield self;
      return [head, ...tail];
    }),
    // 2. until it fails in which case we return an empty array
    pure([])
  );
  return self;
}

Using many we can for example parse expressions of an arbitrary length

const expr = go(function*() {
  yield spaces;
  const num1 = yield decimal;
  const rest = yield many(collect(op, decimal));
  yield eof
  return rest.reduce((acc, [opFunc, num]) => opFunc(acc, num), num1)
});

$ parse(expr, '1 + 2 + 3 + 4')
  >> {data: 10, rest: ""}

There is much more

A single post can not cover parser combinators in detail. For those who want to go further, I made a library pcomb that packages a more comprhensive set of combinators. It'not something ready for production but there are already enough features to play with more advanced parsers. Included also some examples of parsers which illustrates how combinators work.

Here are things that still need to be covered (may do that in later posts)

Lookahead: For example Our oneOf definition allows for an arbitrary lookahead. It means that even if an alternative consumes an arbitrary amount of input before failing, oneOf will always restart the next alternative from the begining of the current input.

This is not efficient in practice and doesnt allow for proper error reporting. In practice we may better restrict the lookahead so that oneOf will not try another alternative if the current one has failed while consuming some input. This will also allow for better error reporting since we can propagate exactly what's expected at a specific location.

(Proper) Error reporting, this includes reporting the exact location of the failure as well as the expected items at that location while still allowing developpers to plug in their own error messages.
User state: Parsing complex languages involves state bookeeping (eg "are we inside a function body?"). This involves allowing a parser to read/write state information. The most simple and composable solution is to write state readers/writers themeseves as parsers that can be inserted in a sequence.
Refactoring using modular interfaces: abstarcts away error handling & state passing into sparate interfaces (as done in Haskell with stacks of Monad Transformers). This provides a more flexible interface allowing developpers to plug in their own implementations.

I hope you enjoyed this post and that you'll have some fun creating your own parsers.

Forem: Yassine Elouafi

Types as Propositions in Typescript

Code's Take on Logic Constructs

Negative types

Double negation, paradoxes and the halting problem

Diving into Logical Proofs using TypeScript

Law of Excluded Middle (A ∨ !A <=> True)

A ∧ !A -> False

Equivalence between Functions and Discriminated Unions?

A simple rule for using callbacks in React

Algebraic Effects in JavaScript part 4 - Implementing Algebraic Effects and Handlers

From Exceptions to Algebraic Effects

Implementing Algebraic Effects with Generators

Capturing the delimited continuation

Example 1: reverse logging

Example 2: collecting logs

Combining handlers

Conclusion

Some references

Algebraic Effects in JavaScript part 3 - Delimited Continuations

Back to the Call Stack

Modeling the Call Stack with Generators

Delimited Continuations

Algebraic Effects in JavaScript part 2 - Capturing continuations with Generators

Driving Generators in direct style

Driving Generators in CPS

The road to undelemited continuations

Example 1: Emulating try/cacth

Example 2: cooperative scheduling

Conclusion

Algebraic Effects in JavaScript part 1 - continuations and control transfer

Direct Style vs Continuation Passing Style

why would we want write a program in such style?

What is control flow?

Conclusion

A gentle introduction to parser combinators

What is a parser combinator?

Sequencing parsers

Merging parsers

Yielding parsers

There is much more

Law of Excluded Middle (`A ∨ !A <=> True`)

`A ∧ !A -> False`