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
andfalse
, the two boolean values 
(not e)
, a unary operation which evaluates totrue
on the boolean valuefalse
andfalse
otherwise 
(num? e)
, a unary opertion which evaluates totrue
ife
is a number andfalse
otherwise 
(zero? e)
, a unary opertion which evaluates totrue
ife
is the number0
andfalse
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.
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 Lisplike language we’re implementing, like Python or Racket or Javascript, is dynamically typed.
Finally, we’ll patch up our toplevel 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