Peter Sestoft - Programming Language Concepts

First, let us consider expressions consisting only of integer constants and two-argument (dyadic) operators such as ( + ) and ( * ). We represent an expression as a term of an F# datatype expr , where integer constants are represented by constructor CstI , and operator applications are represented by constructor Prim : A value of type expr is an abstract syntax tree that represents an expression. Here are some example expressions and their representations as expr values: An expression in this representation can be evaluated to an integer by a function eval : expr -> int that uses pattern matching to distinguish the various forms of expression. Note that to evaluate e 1+ e 2, it must first evaluate e 1 and e 2 to obtain two integers and then add those integers, so the evaluation function must call itself recursively: The eval function is an interpreter for programs in the expression language. It looks rather boring, as it implements the expression language constructs directly by similar F# constructs. However, we might change it to interpret the operator ( - ) as cut-off subtraction, whose result is never negative. Then we get a language with the same expressions but a very different meaning. For instance, 34 now evaluates to zero:

Now, let us extend our expression language with variables such as x and y . First, we add a new constructor Var to the syntax: Here are some expressions and their representation in this syntax: Next we need to extend the eval interpreter to give a meaning to such variables. To do this, we give eval an extra argument env , a so-called environment . The role of the environment is to associate a value (here, an integer) with a variable; that is, the environment is a map or dictionary, mapping a variable name to the variables current value. A simple classical representation of such a map is an association list : a list of pairs of a variable name and the associated value: This environment maps "a" to 3, "c" to 78, and so on. The environment has type (string * int) list . An empty environment, which does not map any variable to anything, is represented by the empty association list To look up a variable in an environment, we define a function lookup of type (string * int) list -> string -> int . An attempt to look up variable x in an empty environment fails; otherwise, if the environment associates y with v , and x equals y , the result is v ; else the result is obtained by looking for x in the rest r of the environment: As promised, our new eval function takes both an expression and an environment, and uses the environment and the lookup function to determine the value of a variable Var x . Otherwise the function is as before, except that env must be passed on in recursive calls: Note that our lookup function returns the first value associated with a variable, so if env is [("x", 11); ("x", 22)] , then lookup env "x" is 11, not 22. This is useful when we consider nested scopes in Chap..