Assignment 2

This week's assignment is simple in specify, but pretty darn difficult to implement. First, the spec: implement a function

val eval : string list -> int

which evaluates an arithmetic expression over addition (+), subtraction (-), multiplication (*), and division (/) treated as infix operators. These expressions may have parentheses. All the usual conventions of arithmetic expressions you (should) know (and love) apply:

• all operators are left associative, i.e., \(1 - 2 - 3 = (1 - 2) - 3\) and \(1 / 2 / 3 = (1 / 2) / 3\).
• Addition and subtraction have the same precedence, i.e., \(1 + 2 - 3 = (1 + 2) - 3\) and \(1 - 2 + 3 = (1 - 2) + 3\).
• Multiplication and division have the same precedence, i.e., \(1 * 2 / 3 = (1 * 2) / 3\) and \(1 / 2 * 3 = (1 / 2) * 3\).
• Multiplication (and division) has higher precedence then addition (and subtraction), i.e., \(1 + 2 * 3 = 1 + (2 * 3)\).

The input to eval is a list of strings, all of which are of the following form:

You may assume that any nonnegative integer that appears in an expression can be successfully converted into an integer via int_of_string, and that the behavior of eval is undefined in the case that the input is not a valid arithmetic expression as described above.

A couple examples:

let _ = assert (eval ["1"] = 1)
let _ = assert (eval ["1"; "+"; "2"] = 3)
let _ = assert (eval ["1"; "+"; "2"; "*"; "3"] = 7)
let _ = assert (eval ["("; "1"; "+"; "2"; ")"; "*"; "3"] = 9)

Hint: The hardest part of implementing this function is dealing with precedence. A useful observation: we can decompose any arithmetic expression as described above in the following way.

• At the top level, an arithmetic expression is of the form

  \[ e_1 \ (+ \ |\ -) \ e_2 \ (+ \ |\ -) \ \dots \ (+ \ |\ -) \ e_n \]

  where \(e_1, \dots, e_n\) are expressions with only multiplications or divisions of numbers and parenthesized expressions.

• At the next level, each of those \(e_1, \dots, e_n\) must be of the form

  \[ f_1 \ (* \ |\ /) \ f_2 \ (* \ |\ /) \ \dots \ (* \ |\ /) \ f_m \] where \(f_1, \dots, f_m\) are either numbers or parenthesized expressions.

This hints at a mutually recursive approach. The function eval can depend on a function eval_mul_div which evaluates expressions like \(e_1, \dots, e_n\) above. This function can, in turn, depend on a function eval_num_paren which can evaluate expressions like \(f_1, \dots, f_m\) above. Finally, this function can depend on the eval function we're defining to handle what's in the parentheses. More concretely, this hints at the following skeleton:

let drop_last l =
  match l with
  | x :: y :: rest -> x :: drop_last (y :: rest)
  | _ -> []

let eval expr =
  assert false (* TODO *)
and eval_mul_div expr =
  assert false (* TODO *)
and eval_num_paren expr =
  match expr with
  | [n] -> int_of_string n               (* number *)
  | "(" :: rest -> eval (drop_last rest) (* parened expr *)
  | _ -> assert false                    (* undefined *)

Note the use of a new keyword: and. This allows us to define functions in terms of each other (i.e., mutually).

There are other ways to approach this function, but hopefully this provides a basis from which you can get started. Happy coding!

1. What is the type of g so that the following expression is well-typed? Can g be given a polymorphic type? Also, what is the type of the following expression?

   let rec f x = g x + g (f x) in f
   

2. Suppose that h is of type list 'a -> list 'a -> 'a and k is of type 'b -> ('b -> 'b) list. Determine the type of the following expression.

   fun x y -> h x (k y)
   

For each of the following types, determine an OCaml expression using only basic constructs (e.g., anonymous functions, applications, variables, list constructors, match statements, etc.) of the given type. In particular, you cannot use exceptions or assertions, and the expression should type-check without warnings. If this is not possible, then explain why in 1-2 sentences.

1. 'a -> 'b -> 'a
2. int -> 'a
3. 'a -> 'a list
4. 'a list -> 'a
5. ('a -> 'b) -> 'a -> 'b¹
6. ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c