Microsoft Word – Problem 3.docx
(*
Problem 3-2
Implement the library function append, which takes two lists (of the same
times) and concatenates them. Do not use the library function or the built-in
short-hand ‘@’.
(append [1;2;3] [4;5]) should evaluate to [1;2;3;4;5]
(append [] []) should evaluate to []
Note that OCaml provides the infix fuction @ as an alternate way of writing
append. So (List.append [1;2] [3]) is the same as ([1;2] @ [3]).
*)
let rec append (l1:’a list) (l2:’a list) : ‘a list =
failwith “rev unimplemented”
(*
Problem 3-3
Implement the library function rev, which reverses a list. In this solution,
you might want to call append. Do not use the library function.
*)
let rec rev (l:’a list) : ‘a list =
failwith “rev unimplemented”
(*
Problem 3-4
Read IOC 5.4 about “tail recursion” and implement a tail recursive version of
rev. Note that you will need a helper function that takes an extra parameter,
which is defined using a local let definition. The rev_t function
itself should not be recursive. Tail recursion is important to efficiency —
OCaml will compile a tail recursive function to a simple loop.
*)
let rev_t (l: ‘a list) : ‘a list =
let rec rev_aux l acc =
begin match l with
| _ -> failwith “rev_t unimplemented”
end
in
rev_aux l []
(*
Problem 3-5
Implement insert, a function that, given an element x and a sorted list l
(i.e. one for which is_sorted returns true) returns the list obtained by
inserting x into the list l at the proper location. Note that if x is
already in the list then insert should just return the original list.
You will need to use the if-then-else expression (see IOC 2.2). Remember that
OCaml is expression-oriented; “if t then e1 else e2” evaluates to either the
value computed by e1 or the value computed by e2 depending on whether t
evaluates to true or false.
*)
let rec insert (x:’a) (l:’a list) : ‘a list =
failwith “insert unimplemented”
(*
Problem 3-6
Implement union, a function that takes two sorted lists and returns the
sorted list containing all of the elements from both of the two input lists.
Hint: you might want to use the insert function that you just defined.
*)
let rec union (l1:’a list) (l2:’a list) : ‘a list =
failwith “union unimplemented”
(*
Problem 4-1
Implement vars_of — a function that, given en expression e returns
a list containing exactly the strings representing variables that appear
in the expression. The result should be a set — that is, it should
contain no duplicates and be sorted (according to is_sorted).
For example:
vars_of e1 should produce []
vars_of e2 should produce [“x”]
vars_of e3 should produce [“x”;”y”]
Hint: you need to pattern match on the exp e.
Hint: you probably want to use the ‘union’ function you wrote for Problem 3-5.
*)
let rec vars_of (e:exp) : string list =
failwith “vars_of unimplemented”
(*
Problem 4-2
Implement string_of — a function that, given an expression e returns
a string representing that expression.
For example:
string_of e1 should produce “(2 * 3)”
string_of e2 should produce “(x + 1)”
string_of e3 should produce “(y * ((x + 1) * -((x + 1))))”
Hint: you can use the “^” operator to concatenate strings.
Hint: you can print the string using the print_string function.
*)
let rec string_of (e:exp) : string =
failwith “string_of unimplemented”
(*
How should we _interpret_ (i.e. give meaning to) an expression?
Some examples:
Add(Const 3L, Const 5L) should have the interpretation 8L
Mult(Const 2L, (Add(Const 3L, Const 5L))) denotes 16L
What about Add(Var “x”, Const 1L)?
What should we do with (Var “x”)?
Each expression denotes an int64 value, but since it can contain variables,
we need an “evaluation context” that maps variable names to int64 values.
NOTE: an _evaluation context_ is just a finite map from variables to values.
One simple (but not particularly efficient) way to represent a context is as
an “association list” that is just a list of (string * int64) pairs:
*)
type ctxt = (string * int64) list
(* Here are some example evalution contexts: *)
let ctxt1 : ctxt = [(“x”, 3L)] (* maps “x” to 3L *)
let ctxt2 : ctxt = [(“x”, 2L); (“y”, 7L)] (* maps “x” to 2L, “y” to 7L *)
(*
When interpreting an expression, we need to look up the value
associated with a variable in an evaluation context.
For example:
lookup “x” ctxt1 should yield 3L
lookup “x” ctxt2 should yield 2L
lookup “y” cxtx2 should yield 7L
What if we lookup a variable that doesn’t appear in the context? In that
case we raise an exception. OCaml provides user-defined and some pre-
defined exceptions. For container-like structures (like ctxt), the
Not_found exception is appropriate.
See IOC 9.2.1 (and 9.2 about exception handlers)
To throw an exception Exception just use:
raise Exception
For example:
lookup “y” ctxt1 should raise Not_found
There is one other case to consider — if the context has two bindings for a
variable, the one closer to the head of the list should take precedence.
For example:
lookup “x” [(“x”, 1L);(“x”, 2L)] should yield 1L (not 2L)
*)
(*
Problem 4-3
Implement the lookup function with the signature given below. It should find
the int64 value associated with a given string in the ctxt c. If there is no
such value, it should raise the Not_found exception.
*)
let rec lookup (x:string) (c:ctxt) : int64 =
failwith “unimplemented”
(*
Problem 4-4
At last, we can write an interpreter for exp’s. This is just a function
‘interpret’ that, given an evaluation context c and an expression e, computes
an int64 value corresponding to the expression. If the expression mentions a
variable that does not appear in the context, interpret should throw the
Not_found exception (note that this amounts to trying to lookup the variable
and *not* catching any resulting Not_found exception.)
For example:
interpret ctxt1 e1 should yield 6L
interpret ctxt1 e2 should yield 4L
interpret ctxt1 e3 should raise a Not_found exception
Note that the interpreter should recursively call itself to obtain the int64
values of subexpressions. You will need to use the Int64 library to
implement addition and multiplication.
You should test your interpeter on more examples than just those provided in
gradedtests.ml.
*)
let rec interpret (c:ctxt) (e:exp) : int64 =
failwith “unimplemented”
(*
Problem 4-5
Now, write an _optimizer_ for expressions. An optimizer is just a function
that tries to reduce the number of operations by doing some work “at compile
time” rather than at “run time”.
For example:
optimize (Add(Const 3L, Const 4L)) might yield (Const 7L)
optimize (Mult(Const 0L, Var “x”)) might yield (Const 0L)
No matter what optimizations your function performs, it should not change the
value computed by the expression (if there is one). That is, for every
context c and exp e, if c has bindings for all the variables in e, it should
be the case that:
(interpret c e) = (interpret c (optimize e))
Note that it is not always possible to reduce the size of an expression:
(Var “x”) is already “optimal”). You will also have to optimize sub-
expressions before applying further optimizations — this means that you will
need to use nested match expressions.
Here is a (slightly) more complex example:
optimize (Add(Const 3L, Mult(Const 0L, Var “x”))) yields (Const 3L)
Note that your optimizer won’t be complete (unless you work *very* hard)
for example,
Add(Var “x”, Neg(Add(Var “x”, Neg(Const 1L)))) “x – (x – 1)”
is equivalent to Const 1l, but we do not expect your optimizer to
discover that. Indeed, there are many algebraic laws that would be hard
to fully exploit.
You can get full credit for this problem if your optimizer:
(1) doesn’t change the meaning of an expression in any context
that provides bindings for all of the expression’s variables
(2) recursively reduces the size of the expression in “obvious” cases
— adding 0, multiplying by 0 or 1, constants, etc.
Hint: what simple optimizations can you do with Neg?
*)
let rec optimize (e:exp) : exp =
failwith “optimize unimplemented”
(*
Problem 5
Implement a function ‘compile’ that takes a program in the ‘exp’ language and
translates it to an equivalent program in the ‘stack’ language.
For example, (compile e1) should yield the program p1 given above.
Correctness means that:
For all expressions e, contexts c (defining the variables in e), and int64
values v:
(interpret c e) = v if and only if
(run c (compile e)) = v
Hints:
– Think about how to define your compiler compositionally so that you build
up the sequence of instructions for a compound expression like Add(e1, e2)
from the programs that compute e1 and e2.
– You may want to use the append function (or the built in @) function to
glue together two programs.
– You should test the correctness of your compiler on several examples.
*)
let rec compile (e:exp) : program =
failwith “compile unimplemented”