CSCI 330 — Lab 3

Due: Wednesday March 21, 2018 @ 11:59PM

OCaml Tuples, Higher-Order Functions, and Recursive Descent

Goals

Overview

You have been tasked with implementing several functions in OCaml. All of the programs require relatively little coding ranging from 2 to 15 lines. If any function requires more than that, you will need to rethink your solution.

  1. Download the handout file from Our Files Directory
  2. Update each of the functions with your own solutions. As a reminder, you are expected to complete this individually. Do not update any function headers
  3. Test your program using the OCaml environment installed on the Linux Lab machines
  4. Submit your updated handout file to the "Lab 3" Autolab assignment.

Start this assignment early I cannot emphasize this enough! ML programming is relatively easy (syntax-wise) but it will seem foreign, especially with recursion and list manipulation.

Note: Solutions using imperative features such as references, arrays, or while loops will receive no credit. Do not use any additional libraries, just use standard OCaml as installed in the Linux environment.

You are required to implement each of the following functions:

assoc (10 points)

Accepts a single parameter as a tuple of three values (d,k,l) where l is a list of key-value pairs [ (k1,v1) ; (k2,v2) ; ... ] and finds the first key which equals k. If such a key is find, then the value of that pair is returned. Otherwise, the default value d is returned. Your function should be tail recursive

Signature:

int * string * (string * int) list -> int

(* Or more general *)

'a * 'b * ('b * 'a) list -> 'a

Expected Output

assoc (-1,"jeff", [("sorin",85);("jeff",23);("moose",44)]);;

(* int = 23 *)


assoc (-1,"bob",[("mary",77);("bob",33);("bob",44)]);;

(* int = 33 *)


assoc (1337,"alice",[("bob",1);("charlie",2)]);;

(* int = 1337 *)

removeDuplicates (15 points)

Accepts a list, l, where we return the list of elements of l where all duplicates are removed and all remaining appear in the same order as in l. You should only replace the two occurences of failwith "to be written" in the existing skeleton. Do not change any of the other skeleton code. HINT: check out List.mem

Signature:

int list -> int list

Expected Output

removeDuplicates [1;6;2;4;12;2;13;6;9];;

(* int list = [1;6;2;4;12;13;9] *)

wwhile (15 points)

Without using any built-in OCaml functions (and definitely not the while or for construct, write an OCaml function, wwhile that takes as input a tuple (f,b) and calls the function f on input b to get a pair (b',c'). wwhile should continue calling f on b' to update the pair as long as c' is true. Once f returns a c' that is false, wwhile should return b'.

Your function should be tail recursive. Once you have implemented the function, you should get the following behavior at the OCaml prompt:

Signature:

(int -> int * bool) * int -> int

(* generally: *)
('a -> 'a * bool) * 'a -> 'a

Expected Output

let f x =
  let xx = x * x * x
  in (xx, xx < 100);;

wwhile (f, 2);;

(* int = 512 *)

In other words, the function parameter (f in the above example) needs to be a function that takes an int and returns a tuple with an int and a bool. wwhile is a function that takes a tuple -- a function and an int. wwhile applies the provided function to the int and gets back an int * bool tuple. As long as the bool in the result is true, wwhile continues to recurse by using the new int result.

fixpoint (15 points)

Without using any built-in OCaml functions, modify the skeleton for fixpoint, which repeatedly updates b with f(b) until b = f(b) and then returns b. You should only replace the failwith "to be written" in the existing skeleton. Do not change any of the other skeleton code.

Once you have implemented the function, you should get the following behavior at the OCaml prompt:

Signature:

(int -> int) * int -> int

(* generally: *)
('a -> 'a) * 'a -> 'a)

Expected Output

let g x = truncate (1e6 *. cos (1e-6 *. float x));;
let h x = x * x;;

fixpoint (g,0);;
(* int = 739085 *)


fixpoint (h, 0);;
(* int = 0 *)

fixpoint (h, 1);;
(* int = 1 *)

In other words, fixpoint is using wwhile to find the value, x, of a function f where f(x) = x. To do this, you will need to write an anonymous function to pass in as part of the input to wwhile. In the first example above, the function being tested is g and the starting point for calling it is 0. g(739085) = 739085. This one is abstract and getting the pieces to fit together can be confusing, but it is essentially a one-liner.

Recursive Descent

You are tasked with writing a recursive descent parser which verifies sentences for expression assignments. Instead of having tokens and lexemes, our language is much easier -- we will only process one character at a time. This means no two (or more) digit numbers are permitted. Similarly, variables will only be one character long.

The BNF for the grammar is as follows (HINT: you will want to convert this to EBNF)

assign -> var '=' expr

expr   -> expr '+' term
        | expr '-' term
        | term

term   -> term '*' factor
        | term '/' factor
        | factor

factor -> var
        | num
        | '(' expr ')'

var    -> 'a' | 'b' | 'c' | ... | 'y' | 'z'

num    -> '0' | '1' | '2' | ... | '8' | '9'
Helper/Support Functions
(* returns true IFF c is a digit [0-9] *)
let is_digit (c : char) -> bool

(* returns true IFF c is a alpha [a-z] *)
let is_alpha (c : char) -> bool

(* state is a tuple-type which defines validity, index, and characters remaining
   NOTE: This is not actually defined in the file but substituting state in for
         the following tuple to improve readability *)
type state = bool * int * char list

(* causes the program to error with a provided message *)
let error_with (msg : string) (s : state) -> Failure

(* returns true IFF the provided string is accepted by the provided grammar *)
let is_valid_grammar (g : state -> state) (s : string) -> bool

(* peeks at top symbol without consuming *)
let symbol (s : state) -> char

(* checks if passed state is valid *)
let is_valid (s : state) -> bool

(* attempts to advance state by consuming c
   advances the state unless an error is encountered
   returns a valid state IFF c was at the front of the list *)
let accept (c : char) (s : state) -> state

(* like accept but hard-errors if returned state is invalid *)
let expect (c : char) (s : state) -> state

You are expected to complete the six following implementations below.

Each one of the methods accepts a state and will return a new state (or produce an error).

is_valid_grammar can be used by you at the testing end. Feel free to also trace any functions you want to observe. e.g. #trace <function_name>;;

let var state = (* 3 points *)
  failwith "to be implemented"

let num state = (* 3 points *)
  failwith "to be implemented"

let rec expr state = (* 6 points *)
  failwith "to be implemented"
and term state = (* 6 points *)
  failwith "to be implemented"
and factor state = (* 7 points *)
  failwith "to be implemented"

let assign state = (* 5 points *)
  failwith "to be implemented"
;;

Submission

Submit lab3.ml as the Lab 3 assignment through Autolab

Grading

100 points total

Attribution

This assignment was adapted from Sorin Lerner's CSE 130 course at UCSD

The recursive-descent component was developed by Professor Killian.