Writing an Interpreter in OCaml
Tags: functional, ocaml, computerscience
Published: 2019-08-19 16:25:51

***
Code is on my [Github](https://github.com/nt591/monkey-ocaml/tree/46882b03ca7d911b5a12b0e47738778fde5ee7fc)
***

## Background
I've decided to take another stab at this interpreter. I'll be using Thorsten Ball's book [Writing an Interpreter in Go](https://interpreterbook.com/) as my primary source, with extra reading material from Bob Nystrom's [Crafting Interpreters](https://craftinginterpreters.com). I find that Thorsten's book gets me productive faster, while Bob's material is deeper and helps clarify and illuminate what I don't understand.

Thorsten's book defines a language called Monkey, that's similar in syntax to Javascript. Curly braces, integer math, not whitespace sensitive, recursion, the whole nine yards.

For this project I'll be using the OCaml language. OCaml sits at an intersection of academia and large production-scale software. It's used at Jane Street, Docker, Bloomberg, Facebook and other companies. I plan on redoing this project in Haskell eventually - I missed some syntax and conventions from Haskell in writing this chapter. I find inline function composition and application is more readable with Haskell's dot notation and `$` application than pipelines.

```haskell
-- Haskell
next_char . read_char $ lexer
```

```ocaml
(* OCaml *)
lexer |> read_char |> next_char
```

## Requirements
- Dune 1.11.x
- opam 2.0.3
- OCaml 4.07.1
- Alcotest 0.8.5 (testing framework)
- Fmt 0.8.8 (pretty printer for testing)

Use `opam` to set up OCaml and install those dependencies. I chose a new version of Dune, and I went with Alcotest as it seemed relatively popular on the OCaml discord. It's also quite readable and pleasant to configure.

## Project structure

Take a look at this [commit](https://github.com/nt591/monkey-ocaml/commit/7dba667d0c20c69aaddaa4640479f26f5673ee20) for some files you can copy

```
ROOT
  - dune-project
  - monkey.intall
  - monkey.opam
  - src/
    - dune
  - test/
    - dune
```

The dune files will let you link and build your code and run the tests. We'll update these as we move along, but for now this will get you started.

## Defining our first tokens

The first step for Thorsten's interpreter is defining a subset of our tokens. In lexical analysis, a token is a simple data structure that represents a small piece of syntax in our programming language. A token could be a SEMICOLON, a PLUS_SIGN, an IDENTIFIER("x"), an INTEGER(5), or some other representation.

We're going to define our tokens in `src/token.ml`. Create that file and let's add some code. We're going to open a module and add basic tokens.


```ocaml
module Token = struct
  type token_type =
    | ILLEGAL
    | EOF
    (* Identifiers and literals *)
    | IDENT of string
    | INT of int
    (* Operators *)
    | ASSIGN
    | PLUS

    (* -- Delimiters *)
    | COMMA
    | SEMICOLON
    | LPAREN
    | RPAREN
    | LBRACE
    | RBRACE
    (* -- Keywords *)
    | FUNCTION
    | LET
end
```

We're also going to add a `token_to_string` function so we can print out some tokens for our tests, as well as keep our compiler happy when it inevitably barks at us for unused code.

```ocaml
let token_to_string = function
  | ILLEGAL -> "ILLEGAL"
  | EOF -> "EOF"
  | IDENT a -> "IDENT " ^ a
  | INT a -> "INT " ^ string_of_int a
  | ASSIGN -> "ASSIGN"
  | PLUS -> "PLUS"
  | COMMA -> "COMMA"
  | SEMICOLON -> "SEMICOLON"
  | LPAREN -> "LPAREN"
  | RPAREN -> "RPAREN"
  | LBRACE -> "LBRACE"
  | RBRACE -> "RBRACE"
  | FUNCTION -> "FUNCTION"
  | LET -> "LET"

```

Unlike Thorsten's Go implementation, we don't need to keep a list of constants. Rather, we can use OCaml's algebraic data types to represent tokens. In fact, OCaml is commonly used in compilers and similar dev tools for exactly this reason.

Thorsten then moves on to creating some tests, in order to build his `NextChar` function. We're going to similar add tests.

We'll need to set up a small module export. Create `src/monkey.ml` and add the following code.

```ocaml
module Token = Token
module Lexer = Lexer

```

Create a file `test/test.ml` and let's add a bit of boilerplate.


```ocaml

open Monkey
include Lexer
include Token

let token_testable = Alcotest.testable Token.pretty_print (=)

let test_lexer_delimiters () =
  Alcotest.(check (list token_testable))
    "same token types" [
        Token.ASSIGN
      ; Token.PLUS
      ; Token.LPAREN
      ; Token.RPAREN
      ; Token.LBRACE
      ; Token.RBRACE
      ; Token.COMMA
      ; Token.SEMICOLON
      ; Token.EOF
      ]
      (Lexer.generate_tokens "=+(){},;")

let () =
  Alcotest.run "Lexer"
    [
      ( "list-delimiters",
        [ Alcotest.test_case "first case" `Slow test_lexer_delimiters ] );
    ]
```

See that `Token.pretty_print` function? We'll need to define a way to return a formatting string representing our Token. Let's go back into `src/token.ml`

```ocaml
let pretty_print ppf tok = Fmt.pf ppf "Token %s" (token_to_string tok)
```

We can look at Alcotest's [source code](https://github.com/mirage/alcotest/blob/24a77e6f8b025d8fd79a6bfcf5f77a26ba8b8a19/src/alcotest.ml#L773-L781) to dig into what this code does. Effectively, for any inferred type `a` it takes a function that formats a type `a` and an equality checking function that takes two `a` and returns a boolean. You can look at the implementations of `int32` or `string` to get a hint of how that works. Our `token_testable` is a module that works on `Token.token_type`, our defined set of token tags. If we were to run `dune runtest` we'd get an error because we haven't yet implemented our lexer. So let's do that.

## Setting up the Lexer

Let's create `src/lexer.ml`.

```ocaml
(* lexer *)

module Lexer = struct
  include Token

  type lexer = {
    input : string;
    position : int;
    read_position : int;
    ch : char;
  }

  let null_byte = '\x00'

  let new_lexer input_string =
    {
      input = input_string;
      position = 0;
      read_position = 0;
      ch = null_byte;
    }
end

```

I chose to use a null_byte instead of an OCaml [option type](http://ocaml-lib.sourceforge.net/doc/Option.html) because in my opinion, an Option represents a potential gap whereas we know that we won't have gaps in our source code. We'll simply be reading the string until we run out of string. The end of our source code isn't undefined, but a known value.

We need to define our `read_char` function. In a lexer, reading a character is simply incrementing our pointer in our lexer and looking at the next character in the input string.


```ocaml
let read_char lexer =
  let read_to_end = lexer.read_position >= String.length(lexer.input) in
  let new_ch = if read_to_end then null_byte else String.get lexer.input lexer.read_position
  in {lexer with position = lexer.read_position; read_position = lexer.read_position + 1; ch = new_ch}
```

OCaml is immutable by default, so we can't just adjust our lexer. Or rather, we can, but why do that when we can avoid that mutable state. We look to see if we're at the end of the string. If we are, the character is a null, else we get the next character in the string and update our lexer. In order to initialize our lexer, we can use our `read_char`. We'll update `new_lexer` to look like

```ocaml

let new_lexer input_string =
  let lexer = {
    input = input_string;
    position = 0;
    read_position = 0;
    ch = null_byte;
  } in
  read_char lexer
```

Awesome! Our test code is still calling `Lexer.generate_tokens` so we'll need to continue working on this.


```ocaml
let next_char lexer = match lexer.ch with
  | '=' -> (read_char lexer, Token.ASSIGN)
  | ';' -> (read_char lexer, Token.SEMICOLON)
  | '(' -> (read_char lexer, Token.LPAREN)
  | ')' -> (read_char lexer, Token.RPAREN)
  | ',' -> (read_char lexer, Token.COMMA)
  | '+' -> (read_char lexer, Token.PLUS)
  | '{' -> (read_char lexer, Token.LBRACE)
  | '}' -> (read_char lexer, Token.RBRACE)
  | '\x00' -> (lexer, Token.EOF)
  | _ -> failwith "unmatched character"

let generate_tokens input_string =
  let lexer = new_lexer input_string in
  let rec gen lxr tokens =
    match next_char lxr with
    | (_, Token.EOF) -> List.rev_append tokens [Token.EOF]
    | (l, tok) -> gen l (tok :: tokens)
  in gen lexer []

```

This code matches on our known inputs and returns a tuple of an updated lexer and the last read token. This tuple allows us to collect tokens and continue to call `next_char` until it ends in our `generate_tokens` function.

`generate_tokens` is defining a recursive function that calls `next_char` on a lexer. For any token, it'll add the token to a list of seen tokens and call `gen` again on the new lexer. Once it finds an `EOF` token, it will `rev_append` the collected tokens to the `EOF`.

Side note: `rev_append` reverses the first list and concatenates it to the second. Because we're using the OCaml `cons` operator in the non-EOF case, we're actually constructing a list in reverse order so we need to flip it at the end. The reason for this is that `cons` is constant time where `append` is linear time proportional to the first list (the operation has to traverse the entire list before adding the elements of the second list). So it's easier to reverse at the end (linear time once) instead of appending (linear time for every token).

If we run `dune runtest` we get passing tests!

## Up next

The next chapter will take care of adding tokens for real source code.