Booleans I

Up until now, our language has supported only one type: numbers. This means that:

• The values produced by all expressions are numbers
• The values accepted by all operations are numbers

For instance, add1 is an operation that takes in a number and produces a number.

Now we’re going to add booleans to our language. This means adding some expressions that produce booleans, and also some operations that accept booleans.

Here’s our interp_exp function from last time:

let rec interp_exp (exp : s_exp) : int =
  match exp with
  | Num n -> n
  | Lst [Sym "add1"; arg] ->
    (interp_exp arg) + 1
  | Lst [Sym "sub1"; arg] ->
      (interp_exp arg) - 1
  | _ -> raise (BadExpression exp)

Since all of the expressions in our language evaluate to integers, interp_exp can return an integer. How will we modify our interpreter to work with booleans?

One option would be to represent booleans as numbers. For instance, we could decide that true is 1 and false is 0. Then we could implement our operations like this:

let rec interp_exp (exp : s_exp) : int =
  match exp with
  | Num n -> n
  | Sym "true" -> 1
  | Sym "false" -> 0
  | Lst [Sym "add1"; arg] ->
    (interp_exp arg) + 1
  | Lst [Sym "sub1"; arg] ->
      (interp_exp arg) - 1
  | Lst [Sym "not"; arg] ->
      if (interp_exp arg) = 0 then 1 else 0
  | _ -> raise (BadExpression exp)

This is a perfectly valid approach–it’s more or less how C encodes booleans. It’s not going to work very well, though, once we have more complex types like strings and lists (though I guess we could use Gödel numbering if we really had to). We’ll also have a hard time correctly implementing our num operator. What should (num true) return?

Instead of encoding booleans as numbers, we’re going to introduce a new type: value. (We’ll also take this opportunity to move our interpreter into its own file, interp.ml).

open S_exp

type value = Number of int | Boolean of bool

Our interp_exp function should return this type. First, we’ll just modify it to support the same operations it did before:

exception BadExpression of s_exp

let rec interp_exp (exp : s_exp) : value =
  match exp with
  | Num n -> Number n
  | Lst [Sym "add1"; arg] as e -> (
    match interp_exp arg with
    | Number n -> Number (n + 1)
    | _ -> raise (BadExpression e) )
  | Lst [Sym "sub1"; arg] -> (
    match interp_exp arg with
    | Number n -> Number (n - 1)
    | _ -> raise (BadExpression e) )
  | e -> raise (BadExpression e)

Notice what we’re doing in the add1 and sub1 cases: if their argument doesn’t evaluate to a number, it’s not a valid expression. So, for instance, (add1 false) won’t evaluate to anything.

Now we can add booleans:

let rec interp_exp (exp : s_exp) : value =
  match exp with
  | Num n -> Number n
  | Sym "true" -> Boolean true
  | Sym "false" -> Boolean false
  | Lst [Sym "add1"; arg] as e -> (
    match interp_exp arg with
    | Number n -> Number (n + 1)
    | _ -> raise (BadExpression e) )
  | Lst [Sym "sub1"; arg] as e -> (
    match interp_exp arg with
    | Number n -> Number (n - 1)
    | _ -> raise (BadExpression e) )
  | Lst [Sym "not"; arg] ->
    if interp_exp arg = Boolean false then Boolean true else Boolean false
  | Lst [Sym "zero?"; arg] ->
    if interp_exp arg = (Number 0) then Boolean true else Boolean false
  | Lst [Sym "num?"; arg] -> (
    match interp_exp arg with
    | Number _ -> Boolean true
    | _ -> Boolean false )
  | e -> raise (BadExpression e)

Notice that our new operations can take in arguments of any type. The Lisp-like language we’re implementing, like Python or Racket or Javascript, is dynamically typed.

Finally, we’ll patch up our top-level interpreter function:

let string_of_value (v : value) : string =
  match v with
  | Number n -> string_of_int n
  | Boolean b -> if b then "true" else "false"

let interp (program : string) : string =
  parse program |> interp_exp |> string_of_value