Naming expressions with let: Interpreter Edition
Now that we know how to access memory, we can add support for names. Our
language will support OCaml-style variable binding: variables are
immutable, and are bound in expressions using let
. Some
examples:
(let ((x 1)) x) ; => 1 (let ((x 3)) (let ((y (+ x 2)) (+ x y))) ; => 8 (let ((x 3)) (let ((x (+ x 2)) (+ x x))) ; => 10
As usual, we’ll start with our interpreter and then work on the compiler.
Names in the interpreter
How should the interpreter evaluate this expression?
x
It depends! If the expression is nested inside a let
,
e.g.,
(let ((x 1)) x)
then the interpreter should evaluate it to its bound value.
Otherwise, x
is meaningless. So it seems like the
interpreter needs to do different things depending on context. We
can’t just do interp_expr (Sym "x")
and expect it
to do the right thing!
We’ll supply this context via another argument to the
interpreter. This argument stores a mapping between names (i.e.,
strings) and values. In util.ml
, we’ve defined a
type called symtab
(short for “symbol
table”) that maps strings to some other value. We can use
symbol tables like this:
$ open Cs164.Util;; $ let st : int symtab = Symtab.empty;; $ let st' = Symtab.add "x" 2 st;; $ Symtab.find "x" st';; 2 $ Symtab.find_opt "x" st;; Exception: Not_found
Symbol tables are sort of like dictionaries in Python or Java,
except that they are immutable: notice that adding a key to
st
above returned a new symbol table instead of
changing st
. (For the curious, our symbol tables use
OCaml’s Map
type, which is implemented using balanced binary trees.) We’ll be
using only a few functions to manipulate our tables:
-
Symtab.empty
is the empty symbol table, containing no mappings -
Symtab.add var value st
returns a symbol table with all ofst
’s mappings plus a mapping betweenvar
andvalue
; any previous mapping forvar
is overwritten -
Symtab.mem var st
returnstrue
ifst
has a mapping forvar
andfalse
otherwise -
Symtab.find var st
returns the valuevar
is mapped to inst
, raising an exception if no such mapping is present
OK, so we’re going to need to modify our interpreter to take a
value symtab
as an argument:
let rec interp_exp (env: value symtab) (exp : s_exp) : value = ...
env
is short for “environment”. None of our
existing expressions modify the environment, so they’ll all
just pass it through in their recursive calls.
Now that we have our environment, we can use it to interpret names:
let rec interp_exp (env: value symtab) (exp : s_exp) : value = match exp with (* some cases elided ... *) | Sym var when Symtab.mem var env -> Symtab.find var env
That “when” restricts when this pattern fires: we’ll only evaluate the right-hand side of the pattern if the “when” condition is true.
We’ll also need to update interp
:
let interp (program : string) : string = parse program |> interp_exp Symtab.empty |> string_of_value
Let’s see our interpreter work:
$ Interp.interp_exp Symtab.empty (parse "x");; <BadExpression error> $ Interp.interp_exp (Symtab.add "x" (Number 1) Symtab.empty) (parse "x");; Number 1 $ Interp.interp_exp (Symtab.add "x" (Number 1) Symtab.empty) (parse "(+ x x)");; Number 2
Cool! Now we just need to implement let
, which updates
this environment. It’s pretty straightforward:
let rec interp_exp (env : value symtab) (exp : s_exp) : value = match exp with (* some cases elided... *) | Lst [Sym "let"; Lst [Lst [Sym var; e]]; body] -> let e_value = interp_exp env e in interp_exp (Symtab.add var e_value env) body
You may notice an “extra” Lst
constructor;
that’s because our let
expression looks like
(let ((var val)) body)
. This is how Scheme’s
let
works, so we’ve done it that way as well. In
Homework 3, you’ll add support for multiple variables:
(let ((x 1) (y 2)) (+ x y))