# 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')))``
1. 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`.