Homework 3: ML and the simply-typed λ-calculus
- Due: 10/14 at 11:59pm
- Points: 30
Please prepare your solutions for problems 1–2 as .ml files and your answer to problem 3 as a PDF file (scanned handwriting is okay, but no .doc or .docx, please). Submit both files in Canvas.
1. Avoid kerning fails
![DON ATE YOUR OLD GLASSES HERE](https://img.buzzfeed.com/buzzfeed-static/static/2018-02/7/16/asset/buzzfeed-prod-fastlane-02/sub-buzz-13154-1518039042-10.jpg?downsize=200:*&output-format=auto&output-quality=auto)
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) stringsu
andv
such thatf u v
is true, then it returnsSome (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 aregexp
(which matches nothing)Epsilon
is aregexp
(which matches only the empty string)Symbol a
is aregexp
ifa
is achar
Union (a, b)
is aregexp
ifa
andb
areConcat (a, b)
is aregexp
ifa
andb
areStar a
is aregexp
ifa
is
For example, the regular expression
(a|bc)*
would be represented byStar (Union (Symbol 'a', Concat (Symbol 'b', Symbol 'c')))
Write an ML function
match_regexp : regexp → string → bool
such thatmatch_regexp a w
returnstrue
iffw
matches regular expressiona
. Hints:Use your solution to question 1.
String
w
matchesConcat(a, b)
iffw
can be split into two (possibly empty) stringsu
andv
such thatu
matchesa
andv
matchesb
.String
w
matchesStar a
iffw
is empty, orw
can be split into two stringsu
(which is non-empty) andv
(which could be empty) such thatu
matchesa
andv
matchesStar a
.
Check the test case
match_regexp (Star Epsilon) "a" = false
.
3. Unpairing
Consider the following term:
t = λx:___. if x.1 then x.2 else succ x.2
What type should go into the
___
to maket
well-typed? Write out the typing derivation fort
.In Python, we can write things like
(a, b) = p
, which is equivalent toa = p[0]; b = p[1]
ifp
is a pair. Let’s add a similar construct to our extended λ-calculus:t ::= ... letpair {x1, x2} = t3 in t4
Furthermore, suppose that we want to get rid of
.1
and.2
and makeletpair
the only way to unpair pairs.Write
.1
and.2
as syntactic sugar in terms ofletpair
(fill in the___
):t.1 ≡ ___ t.2 ≡ ___
Write evaluation and typing rules for
letpair
.