Let expressions

In class we described a language of arithmetic expressions

  type expr = 
    | Num of int
    | Plus of expr * expr 
    | Times of expr * expr

and how to evaluate them. At the end of class we talked about adding a "let x = e1 in e2" syntax. This is the subject of this problem. Download the file let.ml. In it you will find the expr type defined with 'let' syntax. Your task is to implement the eval function. It is found at the bottom of the file.

  let eval : expr -> int = raise Unimplemented;;

The function evals lets you write expressions as strings. Examples are found in the file.

Hint: The OCaml function List.assoc may be helpful. Note: If you want to #use let.ml, you'll have to execute #load "camlp4o.cma";; at the OCaml toplevel first. Otherwise you will get a syntax error.

Interval Arithmetic

In this homework you will write a program to find the minimum of a mathematical function f : \mathbb{R}^n \to \mathbb{R} over a given domain X \subset \mathbb{R}^n. This can be done using interval arithmetic.

Intervals are written as follows:

(0) By what OCaml type can an interval be represented?

(1) The interval extensions of arithmetic functions are given by:

(a) Derive formulas for the interval extensions of +, \times, and -. For example, -[a,b] = [-b,-a].

(b) Write OCaml functions iv_add, iv_mul, and iv_neg that implement these interval extensions.

(c) Write an OCaml function iv_union that computes the union of two intervals.

(2) The function f will be described by an inductive datatype for expressions:

  type expr = 
    | Const of float
    | Var of int
    | Neg of expr
    | Sum of expr * expr
    | Prod of expr * expr

Note that a Const is a singleton interval (e.g. Const 1.0 ~~ [1.0, 1.0]). Here are some examples of mathematical expressions and their representation in OCaml:

Write an OCaml function eval that evaluates expressions given a list of intervals for the variables:

  # eval [(0.0,1.0); (2.0,3.0) ] (Sum(Prod(Var 0, Var 0), Sum(Var 1, Const 1.0)));;
  - : float * float = (3., 5.)

(3)The domain X = \{x \in \mathbb{R}^n \,|\, x_1 \in [a_1,b_1] \land \ldots \land x_n \in [a_n,b_n]\} will be described as a list of intervals

  [(a_1,b_1);\ldots;(a_n,b_n)] : iv list

where

  type iv = float * float

Write an OCaml function subdiv that subdivides a given domain into two subdomains along a given dimension:

  subdiv [(10.0,20.0); (15.0,35.0); (10.0,12.0); (0.0,1.0)] 2 = 
    ([(10.0,20.0); (15.0,35.0); (10.0,11.0); (0.0,1.0)],
     [(10.0,20.0); (15.0,35.0); (11.0,12.0); (0.0,1.0)])

(4) Write a recursive OCaml function subdivN : int -> iv list -> int -> iv list list, such that subdivN d b k subdivides b into 2^d subdomains. At the first level it should divide along dimension k at the next one along dimension (k+1) \,\mathrm{mod}\, n etc. (where n is the length of b)

(5) The united extension of a function f can be described as

    
\mathrm{unext}\,d\,f\,xs = \bigcup_{x \in \mathrm{subdivN}\, d\, xs\, 0}  \mathrm{eval}\,x\,f

Implement this as an OCaml function unext : int -> expr -> iv list -> iv

You can now find bounds on any given expression, e.g.

  # unext 5 (Sum(Prod(Var 0, Var 0), Sum(Neg (Var 0), Var 1))) [(0.0,1.0); (2.0,3.0) ];;
      val it : float * float = (1.625, 3.125)

(5) Extend the type expr with the square root, arctangent, and division. Adapt the function eval.