DEV Community

loading...

Enjoying an Haskell like Type System in Javascript

Iven Marquardt
Author of "A fool's scriptum on functional programming".
Updated on ・4 min read

scriptum is a type validator and a functional library build upon it. A type validator is distinguished by a static type checker like Typescript by operating at runtime. Besides it doesn't infere types from terms but only checks applications.

Doing without type inference sounds like a silly idea but fortunately the validator can resort to Javascript's introspection means, so the developer only has to annotate function types.

Technically speaking scriptum is based on the Hindler-Milner type system extended by higher-kinded/rank types and row polymorphism.

A runtime type system can never attain the soundness of a static one. You can think of it more as a tool for gradual typing. Here is a complex, real world example that should give an intuition how expressive this approach is.

Javascript is modeled around the idea of mutations. Mutations are not bad per se but sharing this side effect causes harm. Mutable represents a data type that helps to tame mutations by keeping them local by design. I am going to introduce the untyped version first, so that you can comprehend its functionality without distraction.

In order to understand the Mutable constructor we first need to understand the _let combinator for local bindings, which is used in the implementation. It is like a let declaration but as a fist class expression and with its own scope. You can consider _let as a more readable IFFE:

const _let = (...args) => ({in: f => f(...args)});
_let(2, 3).in((x, y) => x + y); // 5
Enter fullscreen mode Exit fullscreen mode

Mutable provides an interface to construct values which can be safely updated in-place. The underlying idea is to hide the mutations inside the Mutable wrapper until the wrapped value is actually consumed. Once consumed no more in-place updates are possible.

const Mutable = clone => ref => {
  return _let({}, ref).in((o, ref) => {
    let mutated = false;

    o.consume = () => {
      if (mutated) {
        delete o.consume;
        delete o.update;

        o.consume = fun(() => ref, "_ => t<a>");

        o.update = _ => {
          throw new TypeError(
            "illegal in-place update of consumed data structure");
        };
      }
      return ref;
    };
    o.update = k => {
      if (!mutated) {
        ref = clone(ref); // copy once on first write
        mutated = true;
      }
      k(ref); // use the effect but discard the result
      return o;
    };
    return (o[Symbol.toStringTag] = "Mutable", o);
  });
};

const arrClone = xs => xs.concat(),
  arrPush = x => xs => (xs.push(x), xs);

const mutableArr = Mutable(arrClone),
  foo = mutableArr([1, 2, 3]);

foo.update(arrPush(4))
  .update(arrPush(5))
  .consume(); // [1, 2, 3, 4, 5]

foo.update(arrPush(6)); // type error
Enter fullscreen mode Exit fullscreen mode

Mutable essentially prevents us from sharing mutated values at different places in the code and thus alleviates the peril of unexpected side effects.

One issue remains though. arrMutable doesn't give us any guarantee that the updated value is still of type [Number] after a mutation. It could just as well be [String] or even Set<Boolean>. This is the moment when the type validator comes into play. But how do we make the composite type with its pretty complex interface type safe?

Here is the necessary main annotation,

`{}, t<a> => Mutable {
  consume: (_ => t<a>),
  ·update: ((t<a> => t<a>) => this*)
}`
Enter fullscreen mode Exit fullscreen mode

(· denotes a safe space so that you can actually indent type annotations as demonstrated above)

which reads: Mutable is a function that takes two arguments, an empty object {} and the actual mutable type t<a>. It returns a Mutable object with two properties consume and update.

consume expects a thunk (a function without arguments) that returns the mutable type.

update is a bit more involved. It expects a function that takes another function t<a> => t<a> and returns the object to be constructed. this* indicates a self-reference at the type level. The function argument t<a> => t<a> takes the mutable value and gives back the updated value of the same type.

t<a> is a higher kinded type, better known as generics in Typescript, which takes another generics as an argument. The type ensures that only mutable composite values are passed to the constructor.

As Mutable is a composite type we need to annotate the methods consume and update as well. Moreover, we need to connect the inner types with the outer one. Please note that Mutable is a quite advanced type which requires some additional plumbing. Usually you don't need the extra step.

Here is the complete implementation from the scriptum library:

const Mutable = clone => ref => {
  return _let({}, ref).in(fun((o, ref) => {
    const anno = CHECK ? introspectDeep(ref) : "";
    let mutated = false;

    o.consume = fun(() => {
      if (mutated) {
        delete o.consume;
        delete o.update;
        o.consume = fun(() => ref, `_ => ${anno}`);

        o.update = _ => {
          throw new TypeError(
            "illegal in-place update of consumed data structure");
        };
      }

      return ref;
    }, `_ => ${anno}`);

    o.update = fun(k => {
      if (!mutated) {
        ref = clone(ref); // copy once on first write
        mutated = true;
      }

      k(ref); // use the effect but discard the result
      return o;
    }, `(${anno} => ${anno}) => Mutable {
      consume: (_ => ${anno}),
      ·update: ((${anno} => t<a>) => this*)
    }`);

    return (o[TAG] = "Mutable", o);
  }, `{}, t<a> => Mutable {
    consume: (_ => t<a>),
    ·update: ((t<a> => t<a>) => this*)
  }`));
};

const arrClone = fun(
  xs => xs.concat(),
  "[a] => [a]");

const arrPush = fun(
  x => xs => (xs.push(x), xs),
  "a => [a] => [a]");
Enter fullscreen mode Exit fullscreen mode

As you can see types and functions are associated with the fun combinator.

Now we can safely assume for our example that t<a> is always an array of numbers:

const arrForEach = fun(
  f => xs => (xs.forEach((x, i) => xs[i] = f(x)), xs),
  "(a => b) => [a] => [b]");

const numToStr = fun(
  n => n.toString(),
  "Number => String");

foo.update(arrPush(4))
  .update(arrPush(5))
  .update(arrForEach(numToStr)); // type error
Enter fullscreen mode Exit fullscreen mode

Hopefully, this brief introduction gave you a rough idea how the type validator can assist your coding. We've just scratched the surface!

scriptum on GitHub

Discussion (0)