Enjoying an Haskell like Type System in Javascript
Tags: functional, javascript, node, typescript
Published: 2021-05-25 18:30:10

---
title: Enjoying an Haskell like Type System in Javascript
published: true
description: 
tags: #functional #javascript #node #typescript
//cover_image: https://direct_url_to_image.jpg
---

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:

```javascript
const _let = (...args) => ({in: f => f(...args)});
_let(2, 3).in((x, y) => x + y); // 5
```
`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.

```javascript
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
```
`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*)
}`
```
(`·` 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:

```javascript
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]");
```

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:

```javascript
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
```

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](https://github.com/kongware/scriptum)