Homework 4: ML and typed NB

• Due: 03/01 at 11:55pm
• Points: 15 (each question 5 points)

Please prepare your solution for problem 1-2 as .ml files and your answer to problems 3 as a PDF file (scanned handwriting is okay, but no .doc or .docx, please). Submit both files in Sakai.

1. Avoid kerning fails

Don’t let this happen to you! Write an ML function find_split : (string → string → bool) → string → (string * string) option that looks for a way to split a string in two such that a given predicate is true. That is, find_split f w should do the following:

• If w can be split into two (possibly empty) strings u and v such that f u v is true, then it returns Some (u, v).

• Otherwise, it returns None.

Then the following code should print don ate:

let input_lines chan =
  let rec loop acc =
    match input_line chan with
    | line -> loop (line::acc)
    | exception End_of_file -> List.rev acc
  in loop []

let words = input_lines (open_in "/usr/share/dict/words")

let s = "donate"

let () = match find_split (fun x y -> List.mem x words && List.mem y words) s with
  | None -> print_string "no\n"
  | Some (u, v) -> print_string (u ^ " " ^ v ^ "\n")

Hint: Look in the String module for helpful functions, especially String.length, String.get, and String.sub.

2. Regular expression matching

1. Define an ML type regexp for regular expressions:

   • EmptySet is a regexp (which matches nothing)
   • Epsilon is a regexp (which matches only the empty string)
   • Symbol a is a regexp if a is a char
   • Union (a, b) is a regexp if a and b are
   • Concat (a, b) is a regexp if a and b are
   • Star a is a regexp if a is

For example, the regular expression (a|bc)* would be represented by

Star (Union (Symbol 'a', Concat (Symbol 'b', Symbol 'c')))

2. Write an ML function match_regexp : regexp → string → bool such that match_regexp a w returns true iff w matches regular expression a. Hints:

   • Use your solution to question 1.

   • String w matches Concat(a, b) iff w can be split into two (possibly empty) strings u and v such that u matches a and v matches b.

   • String w matches Star a iff

     • w is empty, or

     • w can be split into two strings u (which is non-empty) and v (which could be empty) such that u matches a and v matches Star a.

   • Check the test case match_regexp (Star Epsilon) "a" = false.

3. An alternative to pred

1. Do Exercise 8.3.5. Try to write your answer before looking at the solution.

2. Let’s define an alternative to pred:

   t ::= ...
         pred t else t

   The idea is that pred t1 else t2 should reduce to the predecessor of t1 if it has one, and to t2 otherwise. For example, we should have

               pred 0 else 0 = 0
   pred 0 else succ (succ 0) = succ (succ 0)
   pred succ (succ 0) else 0 = succ 0

   Extend the evaluation rules (it’s probably better to use congruence rules rather than evaluation contexts) and typing rules for pred...else.

3. Extend the proofs of 8.3.2 (progress) and 8.3.3 (preservation) with new cases to handle pred...else.