I made a programming language! It’s called dodo. There’s basically nothing special about it — it’s a Lisp, chosen to be easy to implement, and it’s interpreted in JavaScript. You can try it here and read the spec here.

The language

Dodo is a Lisp. Function calls are made by putting the function and its arguments in parentheses, and can be arbitrarily nested:

(+ 1 1) ;; => 2

(str-join
    (str-split "john paul ringo george" " ")
    ",") ;; => "john,paul,ringo,george"

(defn square (x) (* x x))
(defn pythag (a b) (+ (square a) (square b)))
(pythag 3 4) ;; => 25

List and map literals use JavaScript-style syntax, rather than Lisp-style quoting:

(head [1 2 3]) ;; => 1
(get { "hi": "hola", "bye": "adios" } "bye") ;; => "adios"

The most interesting thing (currently still a little broken) is the match functionality. You can match arbitrary objects against literals as a control flow construct (in fact, the only control flow construct), with _ as a wildcard:

(match 5
    (1 "one")
    (2 "two")
    (_ "many")) ;; => "many"

You can also recursively match on data structures:

(match band
    ([{"name": "Annie"}, {"name": "Dave"}] "The Eurhythmics")
    ([{"name": "Richard"}, {"name": "Karen"}] "The Carpenters"))

You can bind destructured values to variables in the local scope:

(match points
    ([[x1, y1],[x2, y2]] (js "Math.sqrt" (+ (square (- x2 x1)) (square (- y2 y1))))))

You can also use a when clause to filter based on bound variables or anything else:

(match n
    (x when (> x 0) "positive")
    (x when (< x 0) "negative")
    (_ "zero"))

Implementation Notes

Parser Combinators

I wrote the lexer / parser together as a handrolled parser combinator library. This would be a very silly thing to do for a real project - both production grade lexers and parsers, as well as good parser combinator libraries, already exist. But it was fun, and I learned a lot from it.

A parser combinator takes parsers - functions from strings to some data structure - and combines them into new parsers. For example, the lit() function creates a parser that matches some string exactly:

export function lit(str) {
  const len = str.length;
  return (input) => {
    return (
      input.slice(0, len) === str
        ? {
          result: str,
          rest: input.slice(len)
        } : null
    );
  }
}

(The rest part of the return value is the remainder of the string that was unused). Then an example of a combinator would be seq, as in the grammar definition of fn:

fn = {...} seq(tok('fn'), lit('('), many(g.identifier), lit(')'), g.expr) {...};

This is saying that an anonymous function definition consists of the keyword fn, followed by a list of variable names in parentheses, followed by an expression. Each of those is represented by a parser that identifies its own part of the input, and the seq parser combinator tries each of them in order, passing the rest from one parser into the next one. Note that many is itself a parser combinator, so we’re nesting them here.

This technique is remarkably powerful and remarkably general - the full list of parsing utilities I had to define for this project is:

  • parsers:
    • lit: creates a parser to recognize literal strings
    • tok: like lit, with a fix to keep it from recognizing prefixes of other tokens (e.g., it won’t recognize the first character of if (condition) as the variable i)
    • regex: parser to recognize any string that matches a regular expression
  • combinators:
    • seq: applies parsers one after another
    • or: tries one parser; if it does not match, tries the next
    • many: like BNF *, keeps applying a parser until it fails to match
  • utilities:
    • oneOrMore: many, but must match at least once
    • barring: removes some strings from those a parser would match (for reserved words)
    • opt: makes a parser optional - if it doesn’t match, opt(parser) matches with no return value and consuming none of the input

This was enough to already be able to write a grammar for dodo that is basically a mechanical transformation of the grammar in the spec!

There were a few hacks that I did to get things working, that would have been done better by a real library. For example, with no lexing step, it’s a bit hard to recognize token boundaries, and to consume whitespace properly - you need to ignore spaces, newlines, and commas, but can’t rely on them to delimit tokens because open / close parens might bump up against the identifiers directly. I ended up just doing greedy regex matching for most identifiers and having seq consume whitespace as it goes along, but this is tailored specifically for dodo.

As I look now though it looks like more production grade uses of parser combinators don’t have a great trick for getting around this - this lisp grammar using Parsimmon just calls .trim(P.optWhitespace) a bunch. Probably better to be explicit like that than to silently eat it like I do though.

Another thing to note is that grammars are hard to define in a naive way because of evaluation order in javascript. For example, we might want to write:

const expr = or(literal, identifier, fnCall, {...etc});

const fnCall = seq(lit('('), oneOrMore(g.expr), lit(')'));

Takeaways

You can just write a programming language. Lexer, parser, grammar, interpreter, compiler — do whatever you find interesting and most of the rest is optional or has a library. Learn from the experience and start seeing the skeleton underneath the tools you use every day.