Usually when I get an itch to work on a programming language (case in point) I usually reach out to JavaScript as my compilation target. I was once asked why that is and was told it might be a good topic to blog about, so here we are!

Here's the tl;dr:

  • It runs everywhere
  • I get a step debugger for free
  • It maps well to FP because:
    • It has first class functions and closures
    • It has a built-in record type
    • It uses dynamic typing
  • It's easy to interop with

It runs everywhere

There's not much to say here. It's JavaScript. It's the only language that runs in a browser directly without any build steps, and it runs on tons of other platforms using node.js or other engines. Pretty sure I can also run it on embedded systems or use it in a game engine as a scripting language. It's everywhere!

I get a step debugger for free

The compilation scheme to JS can be fairly straightforward (more on that later) so I can often look at the JavaScript output (and more importantly, debug it using common tools) and figure out what's wrong in my source program or compiler.

Maps well to Functional Programming

JavaScript has a number of features that makes it very easy to translate a bunch of common functional programming features to. The features are:

  • First class functions and closures
  • Dynamic scope
  • A built-in, first-class record type
  • Dynamic typing

With these features I can now translate high-level concepts to a subset of JavaScript pretty easy:

Functions and values

Defining a variable or a function can be done by translating:

x = 1

two = f x x

f n m = n + m

To:

var x = 1;

var f = function(n) { return function(m) { return (n + m); } };

var two = f(x)(x);

I did need to reorder the definitions so that by the time I get to two (and we evaluate JS strictly) everything it uses has already been defined. But because of dynamic scope, I don't need to do that for functions! So I can translate the following:

isEven n =
  if n == 0
    then True
    else isOdd (n - 1)

isOdd n =
  if n == 0
    then False
    else isEven (n - 1)

Directly into:

var isEven = function(n) {
  if (n == 0) {
    return true;
  } else {
    return isOdd(n - 1);
  }
};

var isOdd = function(n) {
  if (n == 0) {
    return false;
  } else {
    return isEven(n - 1);
  }
};

Because while isOdd is not defined when we define isEven, by the time we actually call isEven, which will always be after var isOdd = ..., isOdd has been defined and it will be available inside isEven! This dreadful behaviour is quite useful for a compiler writer trying to hack a compiler together quickly.

So in JavaScript, we can create functions and closures, pass them around, store them in variables, and even define them in any order we'd like! Very convenient.

Translating data types

One killer feature of the ML family of languages that everyone loves to steal is Algebraic Data Types (also known as tagged unions).

We can figure out a easy and uniform way to encode adts using only first-class records:

data Expr
  = Lit Int
  | Var String
  | Add Expr Expr
  | Let String Expr Expr

expr = Let "x" (Lit 1) (Add (Var "x") (Var "x"))

Can be translated to:

var expr = {
  "_constr": "Let",
  "_1": "x",
  "_2": {
    "_constr": "Lit",
    "_1": 1
  },
  "_3": {
    "_constr": "Add",
    "_1": {
      "_constr": "Var",
      "_1": "x"
    },
    "_2": {
      "_constr": "Var",
      "_1": "x"
    }
  }
};

So essentially every data constructor becomes a specific field in a record, and the other fields are added in order.

We can also use normal field names instead of _1, _2, ..., if fields are named in the ADT. What's more, we can implement first-class records directly, and even a module system by "importing" a record of functions and values!

Pattern Matching

A pattern matching expression is a function call with a big "if" statement - each arm becomes an if, and multiple or nested patterns are chained with && so they can short circuit:

simplifyStep expr =
  case expr of
    Add (Lit n) (Lit m) -> Lit (n + m)
    e -> e

simplify expr =
  case expr of
    Add e1 e2 -> simplifyStep (Add (simplify e1) (simplify e2))
    Let name e body -> Let name (simplify e) (simplify body)
    _ -> expr
var simplifyStep = function(expr) {
  if (expr._constr == "Add" && expr._1._constr == "Lit" && expr._2._constr == "Lit") {
    return {
      "_constr": "Lit",
      "_1": expr._1._1 + expr._2._1
    };
  };
  if (true) {
    return expr;
  };
};

var simplify = function(expr) {
  if (expr._constr == "Add") {
    return simplifyStep({
      "_constr": "Add",
      "_1": simplify(expr._1),
      "_2": simplify(expr._2)
    });
  };
  if (expr._constr == "Let") {
    return {
      "_constr": "Let",
      "_1": expr._1,
      "_2": simplify(expr._2),
      "_3": simplify(expr._3)
    };
  };
  if (true) {
    return expr;
  };
};

Interop

Since JavaScript is an interpreted language, there's no need to link against it. One can just call functions without any effort!

For example, in Giml I added the keyword ffi that takes a string, an optional type signature, and a parameter. And I can write stuff like:

main = ffi("console.log" : Int -> IO {}, 1)

or even:

parseInt : String -> Option Int
parseInt str =
    ffi( "function(x) {
            var i = parseInt(x);
            if (isNaN(i)) {
                return { _constr: \"None\", _field: {} };
            } else {
                return { _constr: \"Some\", _field: i };
            }
        }" : String -> Option Int
    , str
    )

And it just works! This saves a lot of time compared to writing library functions for your interpreter.

(btw, in Giml, all data constructors take exactly one type, which is why there's _field there and not _1)

Conclusion

JavaScript has a few features that make it quite easy to target if you're writing an implementation for a strict functional language. If you ignore the rest of its features and focus on a subset of it with these features, it becomes a very compelling compilation target or even a potential intermediate representation. This is why I've been using it to hack on programming languages.