# 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

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')))`

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`

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

Let’s define an alternative to

`pred`

:`t ::= ... pred t else t`

The idea is that

`pred t`

should reduce to the predecessor of_{1}else t_{2}`t`

if it has one, and to_{1}`t`

otherwise. For example, we should have_{2}`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`

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

`pred...else`

.