Environments, revisited

Let us implement the abstract data type of environments using modules and signatures. Assuming a type for names, we first specify the type of environments together with its operators in a signature:

type name = string;;

module type ENVIRONMENT =
  sig
    type 'a environment
    val empty : 'a environment
    val extend : name -> 'a -> 'a environment -> 'a environment
    val lookup : name -> 'a environment -> 'a option
  end;;

All we need to do now is to implement modules that satisfy this signature and the same unit test as before (see the lecture note on Environments):

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

Environments as association lists, revisited

Let us relocate the implementation of environments as association lists in a module:

module Environment_alist : ENVIRONMENT =
  struct
    type 'a environment = (name * 'a) list

    let empty = []

    let extend n d e
      = (n, d) :: e

    let lookup n e_current =
      let rec look_it_up e =
        match e with
        | [] -> None
        | (n', d) :: e' ->
           if n = n'
           then Some d
           else look_it_up e'
      in look_it_up e_current
  end;;

This implementation passes the unit test:

# test_environment_int Environment_alist.empty
                       Environment_alist.extend
                       Environment_alist.lookup;;
- : bool = true
#

Analysis:

• Environment_alist.empty is equivalent to empty_alist the lecture note on Environments;
• Environment_alist.extend is equivalent to extend_alist the lecture note on Environments; and
• Environment_alist.lookup is equivalent to lookup_alist the lecture note on Environments.

Environments as functions, revisited

Let us relocate the implementation of environments as functions in a module:

module Environment_fun : ENVIRONMENT =
  struct
    type 'a environment = name -> 'a option

    let empty =
      fun n -> None

    let extend n d e =
      fun n' -> if n = n'
                then Some d
                else e n'

    let lookup n e_current =
      e_current n
  end;;

This implementation passes the unit test:

# test_environment_int Environment_fun.empty
                       Environment_fun.extend
                       Environment_fun.lookup;;
- : bool = true
#

Analysis:

• Environment_fun.empty is equivalent to empty_fun the lecture note on Environments;
• Environment_fun.extend is equivalent to extend_fun the lecture note on Environments; and
• Environment_fun.lookup is equivalent to lookup_fun the lecture note on Environments.

Resources

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

Version

Created [02 Apr 2019]