Description
0. Introduction.
In the past few lectures, we’ve discussed writing an interpreter in OCaml for a side-effect-free subset of Lisp, called Pure Lisp. For this laboratory assignment, you’ll investigate a potentially efficient way that the interpreter could represent its environments. This lab is shorter than most others you have seen.
1. Theory.
An environment is a data structure used by a programming language interpreter: it maps names to their values, called bindings. The Pure Lisp interpreter discussed in the lectures represents an environment as an OCaml list of 2-tuples, like this.
[(n0, b0); (n1, b1) ⋯; (nj−1, bj−1)]
Here the subscripted n’s are OCaml strings that represent names, and the subscripted b’s are OCaml objects that represent the bindings of those names. To find the binding of a name n, the Pure Lisp interpreter searches this list until it finds the first 2-tuple with n on its left side. The binding of n is then on the right side of that tuple. This takes O(j) string comparisons, on average.
Is it possible to search faster? One possibility uses a list of binary search trees (BST’s) instead of 2-tuples. If each BST is written as a subscripted t, then the environment looks like this.
[t0; t1 ⋯; tk−1]
Each BST associates many distinct names with their bindings. As a result, the length of this list, k, should be much less than that of the original list, j. Also, if the BST’s in the list are approximately balanced, then each can be searched in logarithmic time—faster than the linear time that was needed for a list of 2-tuples.
This representation is perhaps a better match for the needs of the Pure Lisp interpreter. To see why, suppose that we call a function f with m arguments (the subscripted a’s) like this.
(f a0 a1 ⋯ am−1)
To execute this call, the interpreter must bind each of f’s parameter names to the value of its corresponding argument. It might do that by creating a BST that stores the bindings of those parameter names, then adding the BST to the front of the list that represents the environment. The body of the function f can then find the bindings of its parameter names in the environment. When the call to f returns, it can simply remove the BST from the front of the list, restoring the environment to what it was before the call.
2. Implementation.
This laboratory assignment will deal only with finding the value of a name in an environment represented as a list of BST’s. A future lecture will discuss how functions are called, and how environments for those calls are created.
The following OCaml type definition describes a BST whose keys are strings and whose values are instances of the type 'value. It defines two constructors, BSTEmpty and BSTNode. (You saw something like this in Lab 3.)
type 'value bst =
BSTEmpty |
BSTNode of (string * 'value * 'value bst * 'value bst) ;;
Also, this OCaml type definition defines layers, a list of the BST’s from the previous definition.
type 'value layers = ('value bst) list ;;
Finally, this OCaml definition defines LayerError, which is raise’d if the binding of a name can’t be found. The string is an error message.
exception LayerError of string ;;
Using these, you must write a function called layerGet, which takes two parameters, layers and name. The parameter layers is an instance of the type layers, a list of BST’s. The parameter name is a string that represents a name.
The function layerGet must search the BST’s in layers, in order of their appearance, until it finds one that has name as a key. It must then return the object (the binding of name) associated with that key. If it cannot find name in any bst from layers, then it must raise the exception LayerError.
Here are some hints. You might define a helper for layerGet called layerGetting that takes two arguments: the first BST in layers, and the BST’s that follow it in layers. The helper first searches the first BST for name. If it finds name, then it returns name’s binding from the BST. If it can’t find name, then it calls itself recursively. If it runs out of BST’s to search, then it raises LayerError. Note that both layerGet and layerGetting can be tail-recursive.
3. Deliverables.
The file tests11.ml contains some tests. Insert your code into this file, and then run it with OCaml. When you think your code is correct, submit the file with your code in it. If you don’t know how and where to submit your file, then ask your lab TA’s. It must be submitted to Canvas by 11:55 PM on Tuesday, December 7, 2021. Please DOUBLE CHECK your file BEFORE AND AFTER you submit it, to make sure you have submitted the right one.
