Environments

An environment is an abstract data type, i.e., to say it again, a data type together with some operators that satisfy some conditions and which can only be used through these operators. The goal of an environment is to represent names and their denotation. So assuming the type:

type name = string;;

our goal here is to define the polymorphic type:

type 'a environment

together with the following operators:

• empty (of type 'a environment), the empty environment;
• extend (of type name -> 'a -> 'a environment -> 'a environment), to extend an environment with a name and its denotation; and
• lookup (of type name -> 'a environment -> 'a option) to yield the denotation of a given name in a given environment, if it exists.

An environment maps names (represented here as OCaml strings) to their denotation (represented here as OCaml values). An environment may be empty, it may result from extending an environment with a new binding, and it can be consulted by looking up a name.

Food for thought:

• The term “denotable value” refers to the value a name can denote in the current environment, the term “expressible value” refers to the value obtained by evaluating an expression, and the term “storable value” refers to the value that can be stored in memory. These terms are due to Christopher Strachey.

OCaml features two notions of environment:

• the typing environment used in the type inferencer (G on the left of the turnstile in the typing judgment), and
• the environment used at runtime:
  • the initial environment where pre-existing names denote pre-existing values (e.g., List.hd and List.tl),
  • the current lexical environment that holds all the bindings declared so far with global let-expressions, and that extends the initial environment.

(Looking up a name in OCaml does not return an optional value: if this name denotes a value in the current environment, this value is returned; otherwise, an error is raised.)

The environment operators should satisfy the following conditions:

• looking up a name in the empty environment should return None;
• looking up a name in an environment where this name is not bound should return None;
• looking up a name in an environment where this name is bound should return Some d, where d is the latest denotation that was associated to this name.

The following unit-test function illustrates these conditions:

let test_environment_int empty extend lookup =
  let b0 = (lookup "x" empty
            = None)
  and b1 = (lookup "x" (extend "x" 2 empty)
            = Some 2)
  and b2 = (lookup "x" (extend "x" 2 (extend "x" 3 empty))
            = Some 2)
  and b3 = (lookup "x" (extend "y" 2 (extend "x" 3 empty))
            = Some 3)
  and b4 = (lookup "z" (extend "y" 2 (extend "x" 3 empty))
            = None)
  (* etc. *)
  in b0 && b1 && b2 && b3 && b4;;

Exercise 1

Beef up test_environment_int with more tests and add error messages, along the lines of the After hours section of Week 08.

Environments as association lists

An association list is a list of pairs where each pair holds a name and the corresponding denotation.

When an environment is represented as an association list,

• the empty environment is the empty list;
• extending a given environment is done by cons’ing a new pair in front of it; and
• looking up a name requires traversing the association list in search for the first occurrence of the name.

Programmatically:

type 'a environment_alist = (name * 'a) list;;

let empty_alist =
  [];;

let extend_alist x d e =
  (x, d) :: e;;

let lookup_alist x e =
  let rec visit e =
    match e with
    | [] ->
       None
    | (x', d) :: e' ->
       if x' = x
       then Some d
       else visit e'
  in visit e;;

These OCaml functions pass the unit test:

# test_environment_int empty_alist extend_alist lookup_alist;;
- : bool = true
#

Environments as functions

When an environment is represented as a function mapping a name to an optional denotation,

• the empty environment is the constant function that yields None;
• extending a given environment with a given name and a given denotation is done by wrapping it with a function that tests whether the name being looked up is the same as the given name; if that is the case, then the given denotation is returned, and otherwise, the given environment is consulted; and
• looking up a given name in a given environment is achieved by applying this environment to this name.

Programmatically:

type 'a environment_fun = name -> 'a option;;

let empty_fun =
  fun x -> None;;

let extend_fun x d e =
  fun x' -> if x = x'
            then Some d
            else e x';;

let lookup_fun x e =
  e x;;

These OCaml functions pass the unit test:

# test_environment_int empty_fun extend_fun lookup_fun;;
- : bool = true
#

Postlude

Alfrothul: The definition of lookup_fun is simple, but what a headache to come up with it.

Harald: Maybe we should have looked at its type.

Alfrothul: But we know its type, it is name -> 'a environment -> 'a option.

Harald: Yes it is, but here, 'a environment is name -> 'a option.

Alfrothul: So?

Harald: So the type of lookup_fun is name -> (name -> 'a option) -> 'a option.

Brynja: Hello, modus ponens. We meet again.

Alfrothul: You mean, as in the Interlude about functions applied to other functions in Week 05?

Brynja: Yup.

Harald: We need to be more than constantly vigilant. Linearly, perhaps?

Halcyon: Like Professor Moody would go all “LINEAR VIGILANCE!”?

Brynja: More like “QUADRATIC VIGILANCE!”.

Alfrothul: I kind of like “POLYNOMIAL VIGILANCE!”.

“Mad Eye” Moody: You all might as well stop mincing words – “EXPONENTIAL VIGILANCE!”

Resources

• The OCaml code for the present lecture note (latest version: 24 Mar 2020).

Version

Created [24 Mar 2020]