# Booleans I

The next step in growing our language is to add booleans to our interpreter and our compiler. Specifically, we’re going to add support for these expressions:

• `true` and `false`, the two boolean values
• `(not e)`, a unary operation which evaluates to `true` on the boolean value `false` and `false` otherwise
• `(num? e)`, a unary opertion which evaluates to `true` if `e` is a number and `false` otherwise
• `(zero? e)`, a unary opertion which evaluates to `true` if `e` is the number `0` and `false` otherwise

## Types in the interpreter

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.

```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
```