Crafting Interpreters in OCaml - starting a lexer
Tags: computerscience, tutorial, functional
Published: 2019-05-21 15:26:50

I am currently working on learning how interpreters work via Bob Nystrom's book *Crafting Interpreters*. This post is a sample of an ongoing series I'm working on.

***
To follow along the source material, check out the [Scanning chapter](https://craftinginterpreters.com/scanning.html) of Crafting Interpreters
***

For ease, I'll recommend you clone down this [starter repo](https://github.com/nt591/olox-starter-template). We'll be building a scanner for a Lox implementation in OCaml, which we'll call Olox. Let's create a file called `olox.ml`. This is going to be our entry point for the application, similar to `Lox.java` in the source material.

Bob's Java code handles the following three cases:

1) If more than one argument is passed in, output a line telling the user the proper usage and exit.
2) If one argument is passed in, run a file with that name.
3) Else, just open a prompt.

Okay, let's start by writing out the following code in our `olox.ml`

```ocaml
  let main = fun _ -> match Array.length Sys.argv with
    | 0 -> run_prompt ()
    | 1 -> run_file (Array.get Sys.argv 0)
    | _ -> print_endline "Usage: olox [script]"; exit 64;
```

We're pattern matching on the length of the arguments vector passed in. [Sys.argv](https://caml.inria.fr/pub/docs/manual-ocaml/libref/Sys.html) takes an array of strings that we can use. If no arguments are passed in, we run a prompt. If one is passed in, we run a file with that first element. Else, we'll print an error and exit. We can't really run this code, since we have two undefined functions in `run_prompt` and `run_file` but we're just following along.

So now need to define those two functions. Bob's implementation defers `run_file` to a function called `run` by reading the bytes out of a file. `run_prompt` also just takes a line from input and calls `run`. So we now need to define those three functions.

Let's add the following in our module above our main function

```ocaml
  let run source =
    let tokens = Scanner.scan_tokens in
    List.iter (fun token -> print_endline token) tokens

  let run_prompt = fun _ ->
    while true do
      print_string "> ";
      let input = read_line ()
      in run input;
    done

  let run_file filename =
    let channel = open_in filename in
    try
      (* read entire file *)
      let line = really_input_string channel (in_channel_length channel) in
      run line;
      flush stdout;
      close_in channel
    with e ->
      close_in_noerr channel;
      raise e
```

Like Bob's Java code, we have a `run` function that just gets tokens from a scanner - in his case, an instance of a Scanner class. We'll just use a to-be-defined module. Then we'll just iterate over the returned tokens and print them out.

Our `run_prompt` function will print a string as a prompt, then read in the next line and pass it to our run function.

Our `run_file` function takes some filename and creates an input channel, positioned at the beginning of the file. It then gets the entirety of the file by reading `in_channel_length channel` number of characters, then passes into `run`. For clarity, see the following type signatures.

`val really_input_string : in_channel -> int -> string`
`val in_channel_length : in_channel -> int`

`really_input_string` takes a channel and an int, and returns a string. `in_channel_length` returns the length of a channel.

So far so good! If you were to copy and paste this into utop, you'd error on the `Scanner` module. That's fine - feel free to replace `run` with something like `let run = print_endline` and test all those functions. In fact, let's try it right now. Create a file called `test.md` and add the following code.

```
Hello, world!
This is the second line!
Now on line 3 with spec!@l characters
```

In your terminal, run `utop` and copy and paste the following code which replaces `run` with a simple print.

```ocaml
let run = print_endline

let run_prompt = fun _ ->
  while true do
    print_string "> ";
    let input = read_line ()
    in run input;
  done

let run_file filename =
  let channel = open_in filename in
  try
    (* read entire file *)
    let line = really_input_string channel (in_channel_length channel) in
    run line;
    flush stdout;
    close_in channel
  with e ->
    close_in_noerr channel;
    raise e
```

Try running `run_file "test.md";;` and then `run_prompt ();;` Anything in your prompt should be returned back. Neat! Now `ctrl+D` to exit.

Next up is error handling! Bob makes the following point and I think it's very valid

> The other reason I pulled the error reporting out here instead of stuffing it into the scanner and other phases where the error occurs is to remind you that it’s a good engineering practice to separate the code that generates the errors from the code that reports them.

However, in the interest of not having a global mutable variable, and keeping some of my logic contained in the scanner (for now), I'm going to go ahead and handle all error management in the scanner. This way we can maintain all our scanner logic (line number, character positions) safely isolated and still report on it.

Let's jump right into it. Create a file called `scanner.ml`. Bob's examples creates classes for Token and TokenType. In our FP world, those can just be types that our scanner knows about so we'll wrap it all up inside one file. If we need to refactor later we can.

Looking at `Token.java` in the source, we see a giant enum. When I see enum, I think `variant types` - read up [here](https://dev.realworldocaml.org/variants.html) if you need. Let's take the enum and create a variant type in our scanner.

```ocaml
module Scanner = struct
  type token_type =
    (* single-character tokens *)
    | LEFT_PAREN
    | RIGHT_PAREN
    | LEFT_BRACE
    | RIGHT_BRACE
    | COMMA
    | DOT
    | MINUS
    | PLUS
    | SEMICOLON
    | SLASH
    | STAR

    (* One or two character tokens *)
    | BANG
    | BANG_EQUAL
    | EQUAL
    | EQUAL_EQUAL
    | GREATER
    | GREATER_EQUAL
    | LESS
    | LESS_EQUAL

    (* Literals *)
    | IDENTIFIER
    | STRING
    | NUMBER
    (* Keywords *)
    | AND
    | CLASS
    | ELSE
    | FALSE
    | FUN
    | FOR
    | IF
    | NIL
    | OR
    | PRINT
    | RETURN
    | SUPER
    | THIS
    | TRUE
    | VAR
    | WHILE
    | EOF
end
```

Just to quote section 4.2.2,

> There are lexemes for literal values—numbers and strings and the like. Since the scanner has to walk each character in the literal to correctly identify it, it can also convert it to the real runtime value that will be used by the interpreter later.

Before we move on, we'll need to have some way of wrapping literals. Our token is going to want to have a reference of token type AND optional literals - e.g. a token could be of type TRUE with no literal, or of type NUMBER with a literal `2`. So, let's start by just making two types for literals - string and number

```ocaml
  type literal_type = STRING_LITERAL of string | NUMBER_LITERAL of float
```

This doesn't solve all our problems, but at least we now have some idea of what a literal can be. Moving on to make our token, we should define a type that represents a token. Bob's Token class has a type of TokenType, a lexeme of String, a literal of some Object, and a line of Int. We can do something similar with

```ocaml
type token = {
  lexeme: string;
  literal: literal_type option;
  line: int;
  token_type: token_type;
}
```

*Nikhil why is that literal an option?* Well, as we had mentioned before - a token does not need to contain a literal. There is no literal for the token_type `VAR`, so we may not need a literal in our token. Options represent that. Real World OCaml's [chapter on options](https://dev.realworldocaml.org/guided-tour.html#options) is a great primer for more info.

Lets take a moment to look at the initial Scanner code in section 4.4. The file defined a class `Scanner` that has a field `source`, a string that represents the code we're scanning. `scanTokens` takes a list of tokens, checks to see if we're at the end of the source and if not, scans tokens. Once at the end, we add a token representing the end of the file and return the list of tokens. We also have the use of a helper function that determines if we're at the end of the source code.

We see that the original Java code has some fields for use. Let's embrace our FP-world and rather than create a class, we're going to create a type that represents some record of fields. We can then ensure all our functions take and emit that type.

```ocaml
type scanner_context = {
  source: string;
  start: int;
  current: int;
  line: int;
}
```

Now that we have a type that contains all the fields we know about, let's define our methods. To start, let's create an interface file. Create a file called `scanner.mli` with the following

```ocaml
module Scanner : sig
  type token_type

  type literal_type

  type token

  type scanner_context

  val scan_tokens: string -> token list

  val is_at_end: scanner_context -> bool
end
```

In our interface, I'll be using abstract types. `type token` and `type scanner_context` now hide the implementation of the type from any module that implements this signature. You can read more about them on the [OCaml website](https://ocaml.org/learn/tutorials/modules.html#Abstract-types) and this Cornell class's [notes](http://www.cs.cornell.edu/courses/cs3110/2019sp/textbook/modules/abstract_types.html).

Our signatures implement what Bob's Java code does - `is_at_end` returns true or false for the state of the application. `scan_tokens` will go through the source code and return all the tokens.

Let's prove that our interface actually does something! Open `dune` and replace with the following code

```
(executable
  (name olox)
  (libraries oUnit)
)

(alias
  (name    runtest)
  (deps    (:x olox.exe))
  (action  (run %{x})))
```

Now just run `dune build` and `dune runtest`. You should see the following errors.

```
File "scanner.ml", line 1:
Error: The implementation scanner.ml
       does not match the interface .olox.eobjs/byte/scanner.cmi:
       ...
       In module Scanner:
       The value `is_at_end' is required but not provided
       File "scanner.mli", line 56, characters 2-40: Expected declaration
       In module Scanner:
       The value `scan_tokens' is required but not provided
       File "scanner.mli", line 54, characters 2-48: Expected declaration
```

There's a bit more above it but let's come back to that later. Our interface works! We stated that the module must have two specific functions but did not implement them. Now to do that.

We'll first write `is_at_end`. The function takes our wrapping context and returns a boolean. I wrote

```ocaml
let is_at_end ctx = ctx.current >= (String.length ctx.source)
```

Then we'll have our `scan_tokens` function. This function takes just the source code string as an input, and will return a list of tokens. Somewhere in the middle we'll need to wrap up the rest of our context. OCaml has local `let` bindings we can use for this. We also now realize we need to maintain a running list of tokens that we're adding. Let's add tokens to our `scanner_context`. In the definition of `type scanner_context` just add `tokens: token list;` inside.

Looking at Bob's implementation, we have a few more pieces of information. We have a `scanToken` function that does...something. We can at least assume it changes the value of `current` globally due to the reset inside the loop. We also have some addition of an EOF token. Let's sketch out what a `scan_token` function might look like. Given that it'll change two values, current and our token list, let's have it receive and output a `scanner_context`. In our `.mli` file add

```ocaml
  val scan_token: scanner_context -> scanner_context
```

Bob's token addition basically just instantiates a token object and adds it to the global list. Let's do the same, by writing a function `add_token` that takes all the fields of a token as well as context and returns the new context.

```ocaml
  val add_token: token_type -> string -> literal_type option -> int -> scanner_context -> scanner_context
```

Okay! We have some loosely defined code interfaces. Let's implement. In `scanner.ml` we'll do the eaier of the two first.

```ocaml
let add_token token_type lexeme literal line ctx =
  {ctx with tokens = ctx.tokens @ [{
      token_type;
      lexeme;
      literal;
      line
    }]
  }
```

There's a performance issue here where OCaml's list appending operator (either `@` or `List.append`) runs in `O(n)` time by walking through the length of the first list. It's not ideal but that's what we get for using a linked list. For now, we'll ignore this and come back to it when it's a performance issue.

Our next function will be our scanning. Look at Bob's implementation. In words - he gets the next character, checks to see what it is, then adds a token. I'm going to break this into three functions - one function to just increment the `current` counter, one to get the next character, and our add token above.

We can add the following two interfaces

```ocaml
  val advance: scanner_context -> scanner_context

  val current_char: scanner_context -> char option
```

And then define our functions

```ocaml
  let advance context = {context with current = context.current + 1}

  let current_char context =
    try Some (String.get context.source context.current) with Invalid_argument _ -> None
```

I'm using an `option` for the `current_char` because it's possible to get an out of bounds exception on string access, and it's better to just be safe than sorry.

We also have sone unary function `addToken` that Bob defines, that just defers to a binary function. I'm going to define these two functions as either adding a literal, or a nonliteral. That means we'll need a function `add_literal_token` and `add_non_literal_token` - the former takes both a `token_type` and `Some literal` and the latter can defer to the former with a `None`. We're going to again have `context` passed along as the last argument in order to make pipelining our functions easy.

```ocaml
val add_literal_token: token_type -> literal_type option -> scanner_context -> scanner_context

val add_non_literal_token: token_type -> scanner_context -> scanner_context
```

Great. Now to just write those little helpers...

```ocaml
let add_literal_token token_type literal_type context =
  let text = (String.sub context.source context.start (context.current - context.start)) in
  add_token token_type text literal_type context.line context

let add_non_literal_token token_type context = add_literal_token token_type None context
```

We create a substring from the start position and capture the difference between start and current, then add the token. `String.sub` in OCaml takes a start and length, rather than a start and end so we need to do a little math.

Now that we have these, we can write out our `scan_token` function and finally write `scan_tokens`. Again, since we see that `scan_token` in Bob's example cares about two fields - the current character, and the token list, let's pass in our context and get out context.

```ocaml
val scan_token: scanner_context -> scanner_context
```


```ocaml
let scan_token context =
  let advanced_context = advance context in
  match (current_char advanced_context) with
  | Some '(' -> add_non_literal_token LEFT_PAREN advanced_context
  | Some ')' -> add_non_literal_token RIGHT_PAREN advanced_context
  | Some '{' -> add_non_literal_token LEFT_BRACE advanced_context
  | Some '}' -> add_non_literal_token RIGHT_BRACE advanced_context
  | Some ',' -> add_non_literal_token COMMA advanced_context
  | Some '.' -> add_non_literal_token DOT advanced_context
  | Some '-' -> add_non_literal_token MINUS advanced_context
  | Some '+' -> add_non_literal_token PLUS advanced_context
  | Some ';' -> add_non_literal_token SEMICOLON advanced_context
  | Some '*' -> add_non_literal_token STAR advanced_context
  | _ -> failwith "Disallowed character"
```


WHEW. That's a whole lot of work but we did it. We now have a way to scan tokens from a string. Now for the fun part.

In our next post let's try to write more matching cases. And if we're lucky, some tests.