Curious OCaml

Lukasz Stafiniak

Lecture 1: Logic

From logic rules to programming constructs

1 In the Beginning there was Logos

What logical connectives do you know?

\top \bot \wedge \vee \rightarrow
a \wedge b a \vee b a \rightarrow b
truth falsehood conjunction disjunction implication
“trivial” “impossible” a and b a or b a gives b
shouldn’t get got both got at least one given a, we get b

How can we define them? Think in terms of derivation trees:

\frac{\begin{matrix} \frac{\begin{matrix} \frac{\,}{\text{a premise}} & \frac{\,}{\text{another premise}} \end{matrix}}{\text{some fact}} & \frac{\frac{\,}{\text{this we have by default}}}{\text{another fact}} \end{matrix}}{\text{final conclusion}}

Define by providing rules for using the connectives: for example, a rule \frac{\begin{matrix} a & b \end{matrix}}{c} matches parts of the tree that have two premises, represented by variables a and b, and have any conclusion, represented by variable c.

Try to use only the connective you define in its definition.

2 Rules for Logical Connectives

Introduction rules say how to produce a connective.

Elimination rules say how to use it.

Text in parentheses is comments. Letters are variables: stand for anything.

Connective Introduction Rules Elimination Rules
\top \frac{}{\top} doesn’t have
\bot doesn’t have \frac{\bot}{a} (i.e. anything)
\wedge \frac{a \; b}{a \wedge b} \frac{a \wedge b}{a} (take first) \frac{a \wedge b}{b} (take second)
\vee \frac{a}{a \vee b} (put first) \frac{b}{a \vee b} (put second) \frac{{a \vee b} \; {{{\frac{\,}{a} \tiny{x}} \atop {\text{\textbar}}} \atop {c}} (\text{consider }a) \; {{{\frac{\,}{b} \tiny{y}} \atop {\text{\textbar}}} \atop {c}} (\text{consider }b)}{c} using x, y
\rightarrow \frac{{{\frac{\,}{a} \tiny{x}} \atop {\text{\textbar}}} \atop {b}}{a \rightarrow b} using x \frac{{a \rightarrow b} \; a}{b}

Notations

{{{\frac{\,}{a} \tiny{x}} \atop {\text{\textbar}}} \atop {b}} \text{, \ \ or \ \ } {{{\frac{\,}{a} \tiny{x}} \atop {\text{\textbar}}} \atop {c}}

match any subtree that derives b (or c) and can use a (by assumption \frac{\,}{a} \tiny{x}) although otherwise a might not be warranted. For example:

\frac{\frac{\frac{\frac{\frac{\,}{\text{sunny}} \small{x}}{\text{go outdoor}}}{\text{playing}}}{\text{happy}}}{\text{sunny} \rightarrow \text{happy}} \small{\text{ using } x}

Such assumption can only be used in the matched subtree! But it can be used several times, e.g. if someone’s mood is more difficult to influence:

\frac{\frac{\begin{matrix} \frac{\frac{\frac{\,}{\text{sunny}} \small{x}}{\text{go outdoor}}}{\text{playing}} & \frac{\begin{matrix} \frac{\,}{\text{sunny}} \small{x} & \frac{\frac{\,}{\text{sunny}} \small{x}}{\text{go outdoor}} \end{matrix}}{\text{nice view}} \end{matrix}}{\text{happy}}}{\text{sunny} \rightarrow \text{happy}} \small{\text{ using } x}

Elimination rule for disjunction represents reasoning by cases.

How can we use the fact that it is sunny\veecloudy (but not rainy)?

\frac{\begin{matrix} \frac{\,}{\text{sunny} \vee \text{cloudy}} \tiny{\text{ forecast}} & \frac{\frac{\,}{\text{sunny}} \tiny{x}}{\text{no-umbrella}} & \frac{\frac{\,}{\text{cloudy}} \tiny{y}}{\text{no-umbrella}} \end{matrix}}{\text{no-umbrella}} \small{\text{ using } x, y}

We know that it will be sunny or cloudy, by watching weather forecast. If it will be sunny, we won’t need an umbrella. If it will be cloudy, we won’t need an umbrella. Therefore, won’t need an umbrella.We need one more kind of rules to do serious math: reasoning by induction (it is somewhat similar to reasoning by cases). Example rule for induction on natural numbers:

\frac{\begin{matrix} p (0) & {{{\frac{\,}{p(x)} \tiny{x}} \atop {\text{\textbar}}} \atop {p(x+1)}} \end{matrix}}{p (n)} \text{ by induction, using } x

So we get any p for any natural number n, provided we can get it for 0, and using it for x we can derive it for the successor x + 1, where x is a unique variable (we cannot substitute for it some particular number, because we write “using x” on the side).

3 Logos was Programmed in OCaml

Logic Type Expression Introduction Rules Elimination Rules
\top unit () \frac{\;}{\texttt{()} : \texttt{unit}}

3.1 Definitions

Writing out expressions and types repetitively is tedious: we need definitions. Definitions for types are written: type ty = some type.

type int_string_record = {a: int; b: string}

and create its values: {a = 7; b = "Mary"}. * We access the fields of records using the dot notation:

{a=7; b="Mary"}.b = "Mary".Recursive expression {\texttt{rec}} \; x \; {\texttt{=}} \; e in the table was cheating: rec (usually called fix) cannot appear alone in OCaml! It must be part of a definition.

Definitions for expressions are introduced by rules a bit more complex than these:

\frac{\begin{matrix} e_{1} : a & {{{\frac{\,}{x : a} \tiny{x}} \atop {\text{\textbar}}} \atop {e_2 : b}} \end{matrix}}{{\texttt{let}} \; x \; {\texttt{=}} \; e_{1} \; {\texttt{in}} \; e_{2} : b}

(note that this rule is the same as introducing and eliminating \rightarrow), and:

\frac{\begin{matrix} {{{\frac{\,}{x : a} \tiny{x}} \atop {\text{\textbar}}} \atop {e_1 : a}} & {{{\frac{\,}{x : a} \tiny{x}} \atop {\text{\textbar}}} \atop {e_2 : b}} \end{matrix}}{{\texttt{let rec}} \; x \; {\texttt{=}} e_{1} \; {\texttt{in}} \; e_{2} \: b}

We will cover what is missing in above rules when we will talk about polymorphism.* Type definitions we have seen above are global: they need to be at the top-level, not nested in expressions, and they extend from the point they occur till the end of the source file or interactive session. * let-in definitions for expressions: {\texttt{let}} \; x \; {\texttt{=}} \; e_{1} \; {\texttt{in}} \; e_{2} are local, x is only visible in e_{2}. But let definitions are global: placing {\texttt{let}} \; x \; {\texttt{=}} \; e_{1} at the top-level makes x visible from after e_{1} till the end of the source file or interactive session. * In the interactive session, we mark an end of a top-level “sentence” by ;; – it is unnecessary in source files. * Operators like +, *, <, =, are names of functions. Just like other names, you can use operator names for your own functions:

let (+:) a b = String.concat “” [a; b];;Special way of defining”Alpha” +: “Beta”;;but normal way of using operators. * Operators in OCaml are not overloaded. It means, that every type needs its own set of operators. For example, +, , / work for intigers, while +., ., /. work for floating point numbers. Exception: comparisons <, =, etc. work for all values other than functions.

4 Exercises

Exercises from Think OCaml. How to Think Like a Computer Scientist by Nicholas Monje and Allen Downey.

  1. Assume that we execute the following assignment statements:

    let width = 17;;let height = 12.0;;let delimiter = ‘.’;;

    For each of the following expressions, write the value of the expression and the type (of the value of the expression), or the resulting type error.

    1. width/2
    2. width/.2.0
    3. height/3
    4. 1 + 2 * 5
    5. delimiter * 5
  2. Practice using the OCaml interpreter as a calculator:

    1. The volume of a sphere with radius r is \frac{4}{3} \pi r^3. What is the volume of a sphere with radius 5?

      Hint: 392.6 is wrong!

    2. Suppose the cover price of a book is $24.95, but bookstores get a 40% discount. Shipping costs $3 for the first copy and 75 cents for each additional copy. What is the total wholesale cost for 60 copies?

    3. If I leave my house at 6:52 am and run 1 mile at an easy pace (8:15 per mile), then 3 miles at tempo (7:12 per mile) and 1 mile at easy pace again, what time do I get home for breakfast?

  3. You’ve probably heard of the fibonacci numbers before, but in case you haven’t, they’re defined by the following recursive relationship:

    \left\lbrace\begin{matrix} f (0) & = & 0 & \\\\\\ f (1) & = & 1 & \\\\\\ f (n + 1) & = & f (n) + f (n - 1) & \text{for } n = 2, 3, \ldots \end{matrix}\right.

    Write a recursive function to calculate these numbers.

  4. A palindrome is a word that is spelled the same backward and forward, like “noon” and “redivider”. Recursively, a word is a palindrome if the first and last letters are the same and the middle is a palindrome.

    The following are functions that take a string argument and return the first, last, and middle letters:

    let firstchar word = word.[0];;let lastchar word = let len = String.length word - 1 in word.[len];;let middle word = let len = String.length word - 2 in String.sub word 1 len;;

    1. Enter these functions into the toplevel and test them out. What happens if you call middle with a string with two letters? One letter? What about the empty string, which is written ““?
    2. Write a function called is_palindrome that takes a string argument and returns true if it is a palindrome and false otherwise.
  5. The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.

    One way to find the GCD of two numbers is Euclid’s algorithm, which is based on the observation that if r is the remainder when a is divided by b, then \gcd (a, b) = \gcd (b, r). As a base case, we can consider \gcd (a, 0) = a.

    Write a function called gcd that takes parameters a and b and returns their greatest common divisor.

    If you need help, see http://en.wikipedia.org/wiki/Euclidean_algorithm.

Lecture 2: Algebra

Algebraic Data Types and some curious analogies

1 A Glimpse at Type Inference

For a refresher, let’s try to use the rules we introduced last time on some simple examples. Starting with fun x -> x. [?] will mean “dunno yet”.

\begin{matrix} & \frac{[?]}{{\texttt{fun x -> x}} : [?]} & \text{use } \rightarrow \text{ introduction:}\\\\\\ & \frac{\frac{\,}{{\texttt{x}} : a} \tiny{x}}{{\texttt{fun x -> x}} : [?] \rightarrow [?]} & \frac{\,}{{\texttt{x}} : a} \tiny{x} \text{ matches with } {{{\frac{\,}{x : a} \tiny{x}} \atop {\text{\textbar}}} \atop {e : b}} \text{ since } e = {\texttt{x}}\\\\\\ & \frac{\frac{\,}{{\texttt{x}} : a} \tiny{x}}{{\texttt{fun x -> x}} : a \rightarrow a} & \text{since } b = a \text{ because } x : a \text{ matched with } e : b \end{matrix}

Because a is arbitrary, OCaml puts a type variable 'a for it:

# fun x -> x;;
- : 'a -> 'a = <fun>

Let’s try fun x -> x+1, which is the same as fun x -> ((+) x) 1(try it with OCaml/F#!). [? \alpha] will mean “dunno yet, but the same as in other places with [? \alpha]”.

\begin{matrix} & \frac{[?]}{{\texttt{fun x -> ((+) x) 1}} : [?]} & \text{use } \rightarrow \text{ introduction:}\\\\\\ & \frac{\frac{[?]}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]} & \text{use } \rightarrow \text{ elimination:}\\\\\\ & \frac{\frac{\begin{matrix} \frac{[?]}{{\texttt{(+) x}} : [? \beta] \rightarrow [? \alpha]} & \frac{[?]}{{\texttt{1}} : [? \beta]} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]} & \text{we know that {\texttt{1}}} : {\texttt{int}}\\\\\\ & \frac{\frac{\begin{matrix} \frac{[?]}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]} & \text{application again:}\\\\\\ & \frac{\frac{\begin{matrix} \frac{\begin{matrix} \frac{[?]}{{\texttt{(+)}} : [? \gamma] \rightarrow {\texttt{int}} \rightarrow [? \alpha]} & \frac{[?]}{{\texttt{x}} : [? \gamma]} \end{matrix}}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]} & \text{it's our {\texttt{x}}!}\\\\\\ & \frac{\frac{\begin{matrix} \frac{\begin{matrix} \frac{[?]}{{\texttt{(+)}} : [? \gamma] \rightarrow {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{x}} : [? \gamma]} \tiny{{\texttt{x}}} \end{matrix}}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [? \gamma] \rightarrow [? \alpha]} & \text{but {\texttt{(+)}}} : {\texttt{int}} \rightarrow {\texttt{int}} \rightarrow {\texttt{int}}\\\\\\ & \frac{\frac{\begin{matrix} \frac{\begin{matrix} \frac{\,}{{\texttt{(+)}} : {\texttt{int}} \rightarrow {\texttt{int}} \rightarrow {\texttt{int}}} \tiny{\text{(constant)}} & \frac{\,}{{\texttt{x}} : {\texttt{int}}} \tiny{{\texttt{x}}} \end{matrix}}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow {\texttt{int}}} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : {\texttt{int}}}}{\text{{\texttt{fun x -> ((+) x) 1}}} : {\texttt{int}} \rightarrow {\texttt{int}}} & \end{matrix}

1.1 Curried form

When there are several arrows “on the same depth” in a function type, it means that the function returns a function: e.g. {\texttt{(+)}} : {\texttt{int}} \rightarrow {\texttt{int}} \rightarrow {\texttt{int}} is just a shorthand for {\texttt{(+)}} : {\texttt{int}} \rightarrow \left( {\texttt{int}} \rightarrow {\texttt{int}} \right). It is very different from

{\texttt{fun f -> (f 1) + 1}} : \left( {\texttt{int}} \rightarrow {\texttt{int}} \right) \rightarrow {\texttt{int}}

For addition, instead of (fun x -> x+1) we can write ((+) 1). What expanded form does ((+) 1) correspond to exactly (computationally)?

We will get used to functions returning functions when learning about the lambda calculus.

2 Algebraic Data Types

type int_string_choice = A of int | B of string

and also tuple types, record types, and type definitions. * Variants don’t have to have arguments: instead of A of unit just use A. * In OCaml, variants take multiple arguments rather than taking tuples as arguments: A of int * string is different thanA of (int * string). But it’s not important unless you get bitten by it. * Type definitions can be recursive!

type int_list = Empty | Cons of int * int_list

Let’s see what we have in int_list:Empty, Cons (5, Cons (7, Cons (13, Empty))), etc. * Type bool can be seen as type bool = true | false, type int can be seen as a very large type int = 0 | -1 | 1 | -2 | 2 | … * Type definitions can be parametric with respect to types of their components (more on this in lecture about polymorphism), for example a list elements of arbitrary type:

type 'elem list = Empty | Cons of 'elem * 'elem list
  type 'white_color dog = Dog of 'white_color

3 Syntactic Bread and Sugar

type my_bool = True | False

Only constructors and module names can start with capital letter. * Modules are “shelves” with values. For example, List has operations on lists, like List.map and List.filter. * Did I mention that we can use record.field to access a field? * fun x y -> e stands for fun x -> fun y -> e, etc. – and of course,fun x -> fun y -> e parses as fun x -> (fun y -> e) * function A x -> e1 | B y -> e2 stands for fun p -> match p with A x -> e1 | B y -> e2, etc. * the general form is: function *PATTERN-MATCHING* stands forfun v -> match v with *PATTERN-MATCHING* * let f ARGS = e is a shorthand for let f = fun ARGS -> e

4 Pattern Matching

let fst = fun p -> match p with (a, b) -> a
let snd = fun p -> match p with (a, b) -> b
type person = {name: string; surname: string; age: int}
match {name="Walker"; surname="Johnnie"; age=207}
with {name=n; surname=sn; age=a} -> "Hi "^sn^"!"
match Some (5, 7) with None -> "sum: nothing"
  | Some (x, y) -> "sum: " ^ string_of_int (x+y)
let fst (a,_) = a
let snd (_,b) = b
match p with (x, y) when x = y -> "diag" | _ -> "off-diag"
let compare a b = match a, b with
  | (x, y) when x < y -> -1
  | (x, y) when x = y -> 0
  | _ -> 1
type month =
  | Jan | Feb | Mar | Apr | May | Jun
  | Jul | Aug | Sep | Oct | Nov | Dec
type weekday = Mon | Tue | Wed | Thu | Fri | Sat | Sun
type date =
  {year: int; month: month; day: int; weekday: weekday}
let day =
  {year = 2012; month = Feb; day = 14; weekday = Wed};;
match day with
  | {weekday = Sat | Sun} -> "Weekend!"
  | _ -> "Work day"
match day with
  | {weekday = (Mon | Tue | Wed | Thu | Fri **as** wday)}
      when not (day.month = Dec && day.day = 24) ->
    Some (work (get_plan wday))
  | _ -> None

5 Interpreting Algebraic DTs as Polynomials

Let’s do a peculiar translation: take a data type and replace | with +, * with \times, treating record types as tuple types (i.e. erasing field names and translationg ; as \times).

There is a special type for which we cannot build a value:

type void

(yes, it is its definition, no = something part). Translate it as 0.

Translate the unit type as 1. Since variants without arguments behave as variants of unit, translate them as 1 as well. Translate bool as 2.

Translate int, string, float, type parameters and other types of interest as variables. Translate defined types by their translations (substituting variables if necessary).

Give name to the type being defined (denoting a function of the variables introduced). Now interpret the result as ordinary numeric polynomial! (Or “rational function” if it is recursively defined.)

Let’s have fun with it.

type date = {year: int; month: int; day: int}

D = xxx = x^3

type 'a option = None | Some of 'a   (* built-in type *)

O = 1 + x

type 'a my_list = Empty | Cons of 'a * 'a my_list

L = 1 + xL

type btree = Tip | Node of int * btree * btree

T = 1 + xTT = 1 + xT^2

When translations of two types are equal according to laws of high-school algebra, the types are isomorphic, that is, there exist 1-to-1 functions from one type to the other.

Let’s play with the type of binary trees:

\begin{matrix} T & = & 1 + xT^2 = 1 + xT + x^2 T^3 = 1 + x + x^2 T^2 + x^2 T^3 =\\\\\\ & = & 1 + x + x^2 T^2 (1 + T) = 1 + x (1 + xT^2 (1 + T)) \end{matrix}

Now let’s translate the resulting type:

type repr =
  (int * (int * btree * btree * btree option) option) option

Try to find the isomorphism functions iso1 and iso2

val iso1 : btree -> repr
val iso2 : repr -> btree

i.e. functions such that for all trees t, iso2 (iso1 t) = t, and for all representations r, iso1 (iso2 r) = r.

My first failed attempt:

# let iso1 (t : btree) : repr =
  match t with
    | Tip -> None
    | Node (x, Tip, Tip) -> Some (x, None)
    | Node (x, Node (y, t1, t2), Tip) ->
      Some (x, Some (y, t1, t2, None))
    | Node (x, Node (y, t1, t2), t3) ->
      Some (x, Some (y, t1, t2, Some t3));;
            Characters 32-261: […]
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Node (_, Tip, Node (_, _, _))

I forgot about one case. It seems difficult to guess the solution, have you found it on your try?

Let’s divide the task into smaller steps corresponding to selected intermediate points in the transformation of the polynomial:

type ('a, 'b) choice = Left of 'a | Right of 'b
type interm1 =
  ((int * btree, int * int * btree * btree * btree) choice)
  option
type interm2 =
  ((int, int * int * btree * btree * btree option) choice)
  option

let step1r (t : btree) : interm1 =
  match t with
    | Tip -> None
    | Node (x, t1, Tip) -> Some (Left (x, t1))
    | Node (x, t1, Node (y, t2, t3)) ->
      Some (Right (x, y, t1, t2, t3))

let step2r (r : interm1) : interm2 =
  match r with
    | None -> None
    | Some (Left (x, Tip)) -> Some (Left x)
    | Some (Left (x, Node (y, t1, t2))) ->
      Some (Right (x, y, t1, t2, None))
    | Some (Right (x, y, t1, t2, t3)) ->
      Some (Right (x, y, t1, t2, Some t3))

let step3r (r : interm2) : repr =
  match r with
    | None -> None
    | Some (Left x) -> Some (x, None)
    | Some (Right (x, y, t1, t2, t3opt)) ->
      Some (x, Some (y, t1, t2, t3opt))

let iso1 (t : btree) : repr =
  step3r (step2r (step1r t))

Define step1l, step2l, step3l, and iso2. Hint: now it’s trivial!

Take-home lessons:

5.1 Differentiating Algebraic Data Types

Of course, you would say, the pompous title is wrong, we will differentiate the translated polynomials. But what sense does it make?

It turns out, that taking the partial derivative of a polynomial resulting from translating a data type, gives us, when translated back, a type representing how to change one occurrence of a value of type corresponding to the variable with respect to which we computed the partial derivative.

Take the “date” example:

type date = {year: int; month: int; day: int}

\begin{matrix} D & = & xxx = x^3\\\\\\ \frac{\partial D}{\partial x} & = & 3 x^2 = xx + xx + xx \end{matrix}

(we could have left it at 3 xx as well). Now we construct the type:

type date_deriv =
  Year of int * int | Month of int * int | Day of int * int

Now we need to introduce and use (“eliminate”) the type date_deriv.

let date_deriv {year=y; month=m; day=d} =
  [Year (m, d); Month (y, d); Day (y, m)]

let date_integr n = function
  | Year (m, d) -> {year=n; month=m; day=d}
  | Month (y, d) -> {year=y; month=n; day=d}
  | Day (y, m) -> {year=y; month=m, day=n}
;;
List.map (date_integr 7)
  (date_deriv {year=2012; month=2; day=14})

Let’s do now the more difficult case of binary trees:

type btree = Tip | Node of int * btree * btree

\begin{matrix} T & = & 1 + xT^2\\\\\\ \frac{\partial T}{\partial x} & = & 0 + T^2 + 2 xT \frac{\partial T}{\partial x} = TT + 2 xT \frac{\partial T}{\partial x} \end{matrix}

(again, we could expand further into \frac{\partial T}{\partial x} = TT + xT \frac{\partial T}{\partial x} + xT \frac{\partial T}{\partial x}).

Instead of translating 2 as bool, we will introduce new type for clarity:

type btree_dir = LeftBranch | RightBranch
type btree_deriv =
  | Here of btree * btree
  | Below of btree_dir * int * btree * btree_deriv

(You might someday hear about zippers – they are “inverted” w.r.t. our type, in zippers the hole comes first.)

Write a function that takes a number and a btree_deriv, and builds a btree by putting the number into the “hole” in btree_deriv.

Solution:

let rec btree_integr n =
  | Here (ltree, rtree) -> Node (n, ltree, rtree)
  | Below (LeftBranch, m, rtree) ->
    Node (m, btree_integr n ltree, rtree)
  | Below (RightBranch, m, ltree) ->
    Node (m, ltree, btree_integr n rtree)

6 Homework

Write a function btree_deriv_at that takes a predicate over integers (i.e. a function f: int -> bool), and a btree, and builds a btree_deriv whose “hole” is in the first position for which the predicate returns true. It should actually return a btree_deriv option, with None in case the predicate does not hold for any node.

This homework is due for the class after the Computation class, i.e. for (before) the Functions class.

Chapter 2: Derivation example

Lecture 2: Algebra

Type inference example derivation

\frac{[?]}{{\texttt{fun x -> ((+) x) 1}} : [?]}

\text{use } \rightarrow \text{ introduction:}

\frac{\frac{[?]}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]}

\text{use } \rightarrow \text{ elimination:}

\frac{\frac{\begin{matrix} \frac{[?]}{{\texttt{(+) x}} : [? \beta] \rightarrow [? \alpha]} & \frac{[?]}{{\texttt{1}} : [? \beta]} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]}

\text{we know that {\texttt{1}}} : {\texttt{int}}

\frac{\frac{\begin{matrix} \frac{[?]}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]}

\text{application again:}

\frac{\frac{\begin{matrix} \frac{\begin{matrix} \frac{[?]}{{\texttt{(+)}} : [? \gamma] \rightarrow {\texttt{int}} \rightarrow [? \alpha]} & \frac{[?]}{{\texttt{x}} : [? \gamma]} \end{matrix}}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [?] \rightarrow [? \alpha]}

\text{it's our {\texttt{x}}!}

\frac{\frac{\begin{matrix} \frac{\begin{matrix} \frac{[?]}{{\texttt{(+)}} : [? \gamma] \rightarrow {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{x}} : [? \gamma]} {\texttt{x}} \end{matrix}}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow [? \alpha]} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : [? \alpha]}}{{\texttt{fun x -> ((+) x) 1}} : [? \gamma] \rightarrow [? \alpha]}

\text{but {\texttt{(+)}}} : {\texttt{int}} \rightarrow {\texttt{int}} \rightarrow {\texttt{int}}

\frac{\frac{\begin{matrix} \frac{\begin{matrix} \frac{\,}{{\texttt{(+)}} : {\texttt{int}} \rightarrow {\texttt{int}} \rightarrow {\texttt{int}}} \tiny{\text{(constant)}} & \frac{\,}{{\texttt{x}} : {\texttt{int}}} {\texttt{x}} \end{matrix}}{{\texttt{(+) x}} : {\texttt{int}} \rightarrow {\texttt{int}}} & \frac{\,}{{\texttt{1}} : {\texttt{int}}} \tiny{\text{(constant)}} \end{matrix}}{{\texttt{((+) x) 1}} : {\texttt{int}}}}{\text{{\texttt{fun x -> ((+) x) 1}}} : {\texttt{int}} \rightarrow {\texttt{int}}}

Exercise 1.

Due to Yaron Minsky.

Consider a datatype to store internet connection information. The time when_initiated marks the start of connecting and is not needed after the connection is established (it is only used to decide whether to give up trying to connect). The ping information is available for established connection but not straight away.

type connectionstate = | Connecting | Connected | Disconnectedtype connectioninfo = { state : connectionstate; server : Inetaddr.t;
lastpingtime : Time.t option; lastpingid : int option; sessionid : string option; wheninitiated : Time.t option; whendisconnected : Time.t option;}

(The types Time.t and Inetaddr.t come from the library Core used where Yaron Minsky works. You can replace them with float and Unix.inet_addr. Load the Unix library in the interactive toplevel by #load "unix.cma";;.) Rewrite the type definitions so that the datatype will contain only reasonable combinations of information.

Exercise 2.

In OCaml, functions can have named arguments, and also default arguments (parameters, possibly with default values, which can be omitted when providing arguments). The names of arguments are called labels. The labels can be different from the names of the argument values:

let f \simmeaningfulname:n = n+1let = f \simmeaningfulname:5We do not need the result so we ignore it.

When the label and value names are the same, the syntax is shorter:

let g \simpos \simlen = StringLabels.sub “0123456789abcdefghijklmnopqrstuvwxyz” \simpos \simlenlet () =A nicer way to mark computations that do not produce a result (return unit). let pos = Random.int 26 in let len = Random.int 10 in printstring (g \simpos \simlen)

When some function arguments are optional, the function has to take non-optional arguments after the last optional argument. When the optional parameters have default values:

let h ?(len=1) pos = g \simpos \simlenlet () = printstring (h 10)

Optional arguments are implemented as parameters of an option type. This allows us to check whether the argument was actually provided:

let foo ?bar n = match bar with | None -> “Argument =” stringofint n | Some m -> “Sum =” stringofint (m + n);;foo 5;;foo \simbar:5 7;;

We can also provide the option value directly:

let bar = if Random.int 10 < 5 then None else Some 7 infoo ?bar 7;;

  1. Observe the types that functions with labelled and optional arguments have. Come up with coding style guidelines, e.g. when to use labeled arguments.
  2. Write a rectangle-drawing procedure that takes three optional arguments: left-upper corner, right-lower corner, and a width-height pair. It should draw a correct rectangle whenever two arguments are given, and raise exception otherwise. Load the graphics library in the interactive toplevel by #load "graphics.cma";;. Use “functions” invalid_arg, Graphics.open_graph and Graphics.draw_rect.
  3. Write a function that takes an optional argument of arbitrary type and a function argument, and passes the optional argument to the function without inspecting it.

Exercise 3.

From last year’s exam.

  1. Give the (most general) types of the following expressions, either by guessing or inferring by hand:
    1. let double f y = f (f y) in fun g x -> double (g x)
    2. let rec tails l = match l with [] -> [] | x::xs -> xs::tails xs infun l -> List.combine l (tails l)
  2. Give example expressions that have the following types (without using type constraints):
    1. (int -> int) -> bool
    2. 'a option -> 'a list

Exercise 4.

We have seen in the class, that algebraic data types can be related to analytic functions (the subset that can be defined out of polynomials via recursion) – by literally interpreting sum types (i.e. variant types) as sums and product types (i.e. tuple and record types) as products. We can extend this interpretation to all OCaml types that we introduced, by interpreting a function type a \rightarrow b as b^a, b to the power of a. Note that the b^a notation is actually used to denote functions in set theory.

  1. Translate a^{b + cd} and a^b (a^c)^d into OCaml types, using any distinct types for a, b, c, d, and using the ('a,'b) choice = Left of 'a | Right of 'b datatype for +. Write the bijection function in both directions.
  2. Come up with a type 't exp, that shares with the exponential function the following property: \frac{\partial \exp (t)}{\partial t} = \exp (t), where we translate a derivative of a type as a context, i.e. the type with a “hole”, as in the lecture. Explain why your answer is correct. Hint: in computer science, our logarithms are mostly base 2.

Further reading: http://bababadalgharaghtakamminarronnkonnbro.blogspot.com/2012/10/algebraic-type-systems-combinatorial.html

Lecture 3: Computation

‘‘Using, Understanding and Unraveling the OCaml Language’’ Didier Rémy, chapter 1

‘‘The OCaml system’’ manual, the tutorial part, chapter 1

1 Function Composition

let iso2 = step1l -| step2l -| step3l
let iso1 = step1r |- step2r |- step3r
let rec power f n =
  if n <= 0 then (fun x -> x) else f -| power f (n-1)
let derivative dx f = fun x -> (f(x +. dx) -. f(x)) /. dx

where the intent to use with two arguments is stressed, or for short:

let derivative dx f x = (f(x +. dx) -. f(x)) /. dx
let pi = 4.0 *. atan 1.0
let sin''' = (power (derivative 1e-5) 3) sin;;
sin''' pi;;

2 Evaluation Rules (reduction semantics)

3 Symbolic Derivation Example

Go through the examples from the Lec3.ml file in the toplevel.

eval_1_2 <-- 3.00 * x + 2.00 * y + x * x * y
  eval_1_2 <-- x * x * y
    eval_1_2 <-- y
    eval_1_2 --> 2.
    eval_1_2 <-- x * x
      eval_1_2 <-- x
      eval_1_2 --> 1.
      eval_1_2 <-- x
      eval_1_2 --> 1.
    eval_1_2 --> 1.
  eval_1_2 --> 2.
  eval_1_2 <-- 3.00 * x + 2.00 * y
    eval_1_2 <-- 2.00 * y
      eval_1_2 <-- y
      eval_1_2 --> 2.
      eval_1_2 <-- 2.00
      eval_1_2 --> 2.
    eval_1_2 --> 4.
    eval_1_2 <-- 3.00 * x
      eval_1_2 <-- x
      eval_1_2 --> 1.
      eval_1_2 <-- 3.00
      eval_1_2 --> 3.
    eval_1_2 --> 3.
  eval_1_2 --> 7.
eval_1_2 --> 9.
- : float = 9.

4 Tail Calls (and tail recursion)

# let rec unfold n = if n <= 0 then [] else n :: unfold (n-1);;
val unfold : int -> int list = <fun>
# unfold 100000;;
- : int list =
[100000; 99999; 99998; 99997; 99996; 99995; 99994; 99993; …]
# unfold 1000000;;
Stack overflow during evaluation (looping recursion?).
# let rec unfold_tcall acc n =
  if n <= 0 then acc else unfold_tcall (n::acc) (n-1);;
  val unfold_tcall : int list -> int -> int list = <fun>
# unfold_tcall [] 100000;;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; …]
# unfold_tcall [] 1000000;;
- : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; …]

5 First Encounter of Continuation Passing Style

We can postpone doing the actual work till the last moment:

let rec depth tree k = match tree with
    | Tip -> k 0
    | Node(_,left,right) ->
      depth left (fun dleft ->
        depth right (fun dright ->
          k (1 + (max dleft dright))))

let depth tree = depth tree (fun d -> d)

6 Homework

By “traverse a tree” below we mean: write a function that takes a tree and returns a list of values in the nodes of the tree.

  1. Write a function (of type btree -> int list) that traverses a binary tree: in prefix order – first the value stored in a node, then values in all nodes to the left, then values in all nodes to the right;
  2. in infix order – first values in all nodes to the left, then value stored in a node, then values in all nodes to the right (so it is “left-to-right” order);
  3. in breadth-first order – first values in more shallow nodes.
  4. Turn the function from ex. 1 or 2 into continuation passing style.
  5. Do the homework from the end of last week slides: write btree_deriv_at.
  6. Write a function simplify: expression -> expression that simplifies the expression a bit, so that for example the result of simplify (deriv exp dv) looks more like what a human would get computing the derivative of exp with respect to dv.

Functional Programming

Computation

Exercise 1: By “traverse a tree” below we mean: write a function that takes a tree and returns a list of values in the nodes of the tree.

  1. Write a function (of type *btree -> int list*) that traverses a binary tree: in prefix order – first the value stored in a node, then values in all nodes to the left, then values in all nodes to the right;
  2. in infix order – first values in all nodes to the left, then value stored in a node, then values in all nodes to the right (so it is “left-to-right” order);
  3. in breadth-first order – first values in more shallow nodes.

Exercise 2: Turn the function from ex. 1 point 1 or 2 into continuation passing style.

Exercise 3: Do the homework from the end of last week slides: write btree_deriv_at.

Exercise 4: Write a function simplify: expression -> expression that simplifies the expression a bit, so that for example the result of simplify (deriv exp dv) looks more like what a human would get computing the derivative of exp with respect to dv:

Write a simplify_once function that performs a single step of the simplification, and wrap it using a general fixpoint function that performs an operation until a fixed point* is reached: given f and x, it computes f^n (x) such that f^n (x) = f^{n + 1} (x).*

Exercise 5: Write two sorting algorithms, working on lists: merge sort and quicksort.

  1. Merge sort splits the list roughly in half, sorts the parts, and merges the sorted parts into the sorted result.
  2. Quicksort splits the list into elements smaller/greater than the first element, sorts the parts, and puts them together.

Lecture 4: Functions.

Programming in untyped \lambda-calculus.

Introduction to Lambda Calculus Henk Barendregt, Erik Barendsen

Lecture Notes on the Lambda Calculus Peter Selinger

1 Review: a “computation by hand” example

Let’s compute some larger, recursive program.Recall that we use fix instead of let rec to simplify rules for recursion. Also remember our syntactic conventions: fun x y -> e stands for fun x -> (fun y -> e), etc.

let rec fix f x = f (fix f) xPreparations.type intlist = Nil | Cons of int * intlistWe will evaluate (reduce) the following expression.let length = fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs) inlength (Cons (1, (Cons (2, Nil))))

let length = fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs) inlength (Cons (1, (Cons (2, Nil))))

\begin{matrix} {\texttt{let }} x = v {\texttt{ in }} a & \Downarrow & a [x := v] \end{matrix}

fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs) (Cons (1, (Cons (2, Nil))))

\begin{matrix} {\texttt{fix}}^2 v_{1} v_{2} & \Downarrow & v_{1} \left( {\texttt{fix}}^2 v_{1} \right) v_{2} \end{matrix}

\begin{matrix} {\texttt{fix}}^2 v_{1} v_{2} & \Downarrow & v_{1} \left( {\texttt{fix}}^2 v_{1} \right) v_{2} \end{matrix}

(fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs) (fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) (Cons (1, (Cons (2, Nil))))

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1}' a_{2} \end{matrix}

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1}' a_{2} \end{matrix}

(fun l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + (fix (fun f l -> match l with | Nil -> 0
| Cons (x, xs) -> 1 + f xs)) xs) (Cons (1, (Cons (2, Nil))))

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \Downarrow & a [x := v] \end{matrix}

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \Downarrow & a [x := v] \end{matrix}

(match Cons (1, (Cons (2, Nil))) with | Nil -> 0 | Cons (x, xs) -> 1 + (fix (fun f l -> match l with | Nil -> 0
| Cons (x, xs) -> 1 + f xs)) xs)

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{2}^n (p_{1}, \ldots, p_{k}) {\texttt{->}} a {\texttt{ \textbar }} \operatorname{pm} & \Downarrow & {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n})\\\\\\ & & {\texttt{with} } \operatorname{pm} \end{matrix}

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{2}^n (p_{1}, \ldots, p_{k}) {\texttt{->}} a {\texttt{ \textbar }} \operatorname{pm} & \Downarrow & {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n})\\\\\\ & & {\texttt{with} } \operatorname{pm} \end{matrix}

(match Cons (1, (Cons (2, Nil))) with | Cons (x, xs) -> 1 + (fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) xs)

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{1}^n (x_{1}, \ldots, x_{n}) {\texttt{->}} a {\texttt{ \textbar }} \ldots & \Downarrow & a [x_{1} := v_{1} ; \ldots ; x_{n} := v_{n}] \end{matrix}

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{1}^n (x_{1}, \ldots, x_{n}) {\texttt{->}} a {\texttt{ \textbar }} \ldots & \Downarrow & a [x_{1} := v_{1} ; \ldots ; x_{n} := v_{n}] \end{matrix}

1 + (fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) (Cons (2, Nil))

\begin{matrix} {\texttt{fix}}^2 v_{1} v_{2} & \rightsquigarrow & v_{1} \left( {\texttt{fix}}^2 v_{1} \right) v_{2}\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} {\texttt{fix}}^2 v_{1} v_{2} & \rightsquigarrow & v_{1} \left( {\texttt{fix}}^2 v_{1} \right) v_{2}\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) (fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) (Cons (2, Nil))

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (fun l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + (fix (fun f l -> match l with
| Nil -> 0 | Cons (x, xs) -> 1 + f xs)) xs))
(Cons (2, Nil))

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (match Cons (2, Nil) with | Nil -> 0 | Cons (x, xs) -> 1 + (fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) xs))

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{2}^n (p_{1}, \ldots, p_{k}) {\texttt{->}} a {\texttt{ \textbar }} \operatorname{pm} & \rightsquigarrow & {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n})\\\\\\ & & {\texttt{with} } \operatorname{pm}\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{2}^n (p_{1}, \ldots, p_{k}) {\texttt{->}} a {\texttt{ \textbar }} \operatorname{pm} & \rightsquigarrow & {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n})\\\\\\ & & {\texttt{with} } \operatorname{pm}\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (match Cons (2, Nil) with | Cons (x, xs) -> 1 + (fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) xs)

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{1}^n (x_{1}, \ldots, x_{n}) {\texttt{->}} a {\texttt{ \textbar }} \ldots & \Downarrow & a [x_{1} := v_{1} ; \ldots ; x_{n} := v_{n}]\\\\\\ & & \end{matrix}

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{1}^n (x_{1}, \ldots, x_{n}) {\texttt{->}} a {\texttt{ \textbar }} \ldots & \rightsquigarrow & a [x_{1} \:= v_{1} ; \ldots ; x_{n} := v_{n}]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (1 + (fix (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) Nil)

\begin{matrix} {\texttt{fix}}^2 v_{1} v_{2} & \rightsquigarrow & v_{1} \left( {\texttt{fix}}^2 v_{1} \right) v_{2}\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} {\texttt{fix}}^2 v_{1} v_{2} & \rightsquigarrow & v_{1} \left( {\texttt{fix}}^2 v_{1} \right) v_{2}\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (1 + (fun f l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs) (fix (fun f l ->
match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) Nil)

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (1 + (fun l -> match l with | Nil -> 0 | Cons (x, xs) -> 1 + (fix (fun f l ->
match l with | Nil -> 0 | Cons (x, xs) -> 1 + f xs)) xs) Nil)

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} \left( {\texttt{fun }} x {\texttt{->}} a \right) v & \rightsquigarrow & a [x := v]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (1 + (match Nil with | Nil -> 0 | Cons (x, xs) -> 1 + (fix (fun f l -> match l with
| Nil -> 0 | Cons (x, xs) -> 1 + f xs)) xs))

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{1}^n (x_{1}, \ldots, x_{n}) {\texttt{->}} a {\texttt{ \textbar }} \ldots & \rightsquigarrow & a [x_{1} \:= v_{1} ; \ldots ; x_{n} := v_{n}]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

\begin{matrix} {\texttt{match }} C_{1}^n (v_{1}, \ldots, v_{n}) {\texttt{ with}} & & \\\\\\ C_{1}^n (x_{1}, \ldots, x_{n}) {\texttt{->}} a {\texttt{ \textbar }} \ldots & \rightsquigarrow & a [x_{1} \:= v_{1} ; \ldots ; x_{n} := v_{n}]\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}'\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + (1 + 0)

\begin{matrix} f^n v_{1} \ldots v_{n} & \rightsquigarrow & f (v_{1}, \ldots, v_{n})\\\\\\ a_{1} a_{2} & \Downarrow & a_{1} a_{2}' \end{matrix}

1 + 1

\begin{matrix} f^n v_{1} \ldots v_{n} & \Downarrow & f (v_{1}, \ldots, v_{n}) \end{matrix}

2

2 Language and rules of the untyped \lambda-calculus

3 Booleans

let ctrue = fun x y -> x‘‘True’’ is projection on the first argument.let cfalse = fun x y -> yAnd ‘‘false’’ on the second argument.let cand = fun x y -> x y cfalseIf one is false, then return false.let encodebool b = if b then ctrue else cfalselet decodebool c = c true falseTest the functions in the toplevel.

4 If-then-else and pairs

let ifthenelse = fun b -> bBooleans select the argument!

Remember to play with the functions in the toplevel.

let cpair m n = fun x -> x m nWe couple thingslet cfirst = fun p -> p ctrueby passing them together.let csecond = fun p -> p cfalseCheck that it works!

let encodepair encfst encsnd (a, b) = cpair (encfst a) (encsnd b)let decodepair defst desnd c = c (fun x y -> defst x, desnd y)let decodeboolpair c = decodepair decodebool decodebool c

5 Pair-encoded natural numbers

let pn0 = fun x -> xStart with the identity function.let pnsucc n = cpair cfalse nStack another pair.let pnpred = fun x -> x cfalse[Explain these functions.]let pniszero = fun x -> x ctrue

We program in untyped lambda calculus as an exercise, and we need encoding / decoding to verify our exercises, so using “magic” for encoding / decoding is “fair game”.

let rec encodepnat n =We use Obj.magic to forget types. if n <= 0 then Obj.magic pn0 else pnsucc (Obj.magic (encodepnat (n-1)))Disregarding types,let rec decodepnat pn =these functions are straightforward! if decodebool (pniszero pn) then 0 else 1 + decodepnat (pnpred (Obj.magic pn))

6 Church numerals (natural numbers in Ch. enc.)

let cn0 = fun f x -> xThe same as c_false.let cn1 = fun f x -> f xBehaves like identity.let cn2 = fun f x -> f (f x)let cn3 = fun f x -> f (f (f x))

let cnsucc = fun n f x -> f (n f x)

let rec encodecnat n f = if n <= 0 then (fun x -> x) else f -| encodecnat (n-1) flet decodecnat n = n ((+) 1) 0let cn7 f x = encodecnat 7 f xWe need to \eta-expand these definitionslet cn13 f x = encodecnat 13 f xfor type-system reasons.(Because OCaml allows side-effects.)let cnadd = fun n m f x -> n f (m f x)Put n of f in front.let cnmult = fun n m f -> n (m f)Repeat n timesputting m of f in front.let cnprev n =
fun f x ->This is the ‘‘Church numeral signature’‘. nThe only thing we have is an n-step loop. (fun g v -> v (g f))We need sth that operates on f. (fun z->x)We need to ignore the innermost step.
(fun z->z)We’ve build a ‘‘machine’’ not results – start the machine.

cn_is_zero left as an exercise.

decodecnat (cn_prev cn3)

\Downarrow

(cn_prev cn3) ((+) 1) 0

\Downarrow

(fun f x -> cn3 (fun g v -> v (g f)) (fun z->x)
(fun z->z)) ((+) 1) 0

\Downarrow

((fun f x -> f (f (f x))) (fun g v -> v (g ((+) 1))) (fun z->0) (fun z->z))

\Downarrow

((fun g v -> v (g ((+) 1))) ((fun g v -> v (g ((+) 1))) ((fun g v -> v (g ((+) 1))) (fun z->0)))) (fun z->z))

\Downarrow

((fun z->z) (((fun g v -> v (g ((+) 1))) ((fun g v -> v (g ((+) 1))) (fun z->0)))) ((+) 1)))

\Downarrow

(fun g v -> v (g ((+) 1))) ((fun g v -> v (g ((+) 1))) (fun z->0)) ((+) 1)

\Downarrow

((+) 1) ((fun g v -> v (g ((+) 1))) (fun z->0) ((+) 1))

\Downarrow

((+) 1) (((+) 1) ((fun z->0) ((+) 1)))

\Downarrow

((+) 1) (((+) 1) (0))

\Downarrow

((+) 1) 1

\Downarrow

2

7 Recursion: Fixpoint Combinator

8 Encoding of Lists and Trees

let nil = fun x y -> ylet cons h t = fun x y -> x h tlet addlist l =
fix (fun f l -> l (fun h t -> cnadd h (f t)) cn0) l;;decodecnat
(addlist (cons cn1 (cons cn2 (cons cn7 nil))));;let leaf n = fun x y -> x nlet node l r = fun x y -> y l rlet addtree t = fix (fun f t -> t (fun n -> n) (fun l r -> cnadd (f l) (f r)) ) t;;decodecnat (addtree (node (node (leaf cn3) (leaf cn7)) (leaf cn1)));;

9 Looping Recursion

let pnadd m n = fix (fun f m n -> ifthenelse (pniszero m) n (pnsucc (f (pnpred m) n)) ) m n;;decodepnat (pnadd pn3 pn3);;

let pnadd m n = fix (fun f m n -> (ifthenelse (pniszero m) (fun x -> n) (fun x -> pnsucc (f (pnpred m) n))) id ) m n;;decodepnat (pnadd pn3 pn3);;decodepnat (pnadd pn3 pn7);;

10 In-class Work and Homework

Define (implement) and verify: 1. c_or and c_not; 1. exponentiation for Church numerals; 1. is-zero predicate for Church numerals; 1. even-number predicate for Church numerals; 1. multiplication for pair-encoded natural numbers; 1. factorial n! for pair-encoded natural numbers. 1. Construct \lambda-terms m_{0}, m_{1}, \ldots such that for all n one has:

\begin{matrix} m_{0} & = & x \\\\\\ m_{n + 1} & = & m_{n + 2} m_{n} \end{matrix}

(where equality is after performing \beta-reductions). 1. Define (implement) and verify a function computing: the length of a list (in Church numerals); 1. cn_max – maximum of two Church numerals; 1. the depth of a tree (in Church numerals). 1. Representing side-effects as an explicitly “passed around” state value, write combinators that represent the imperative constructs: 1. for…to… 1. for…downto… 1. while…do… 1. do…while… 1. repeat…until…

Rather than writing a \lambda-term using the encodings that we’ve learnt, just implement the functions in OCaml / F#, using built-in int and bool types. You can use let rec instead of fix. * For example, in exercise (a), write a function let rec for_to f beg_i end_i s =… where f takes arguments i ranging from beg_i to end_i, state s at given step, and returns state s at next step; the for_to function returns the state after the last step. * And in exercise (c), write a function let rec while_do p f s =… where both p and f take state s at given step, and if p s returns true, then f s is computed to obtain state at next step; the while_do function returns the state after the last step.

Do not use the imperative features of OCaml and F#, we will not even cover them in this course!

Although we will not cover them, it is instructive to see the implementation using the imperative features, to better understand what is actually required of a solution to the last exercise.

  1. let forto f begi endi s = let s = ref s in for i = begi to endi do
    s := f i !s done; !s
  2. let fordownto f begi endi s = let s = ref s in for i = begi downto endi do s := f i !s done; !s
  3. let whiledo p f s = let s = ref s in while p !s do s := f !s done;
    !s
  4. let dowhile p f s = let s = ref (f s) in while p !s do s := f !s
    done; !s
  5. let repeatuntil p f s = let s = ref (f s) in while not (p !s) do s := f !s done; !s

Functional Programming

Functions

Exercise 1: Define (implement) and test on a couple of examples functions corresponding to / computing:

  1. *c_or* and *c_not*;
  2. exponentiation for Church numerals;
  3. is-zero predicate for Church numerals;
  4. even-number predicate for Church numerals;
  5. multiplication for pair-encoded natural numbers;
  6. factorial n! for pair-encoded natural numbers.
  7. the length of a list (in Church numerals);
  8. *cn_max* – maximum of two Church numerals;
  9. the depth of a tree (in Church numerals).

Exercise 2: Representing side-effects as an explicitly “passed around” state value, write (higher-order) functions that represent the imperative constructs:

  1. *forto**…*
  2. *fordownto**…*
  3. *whiledo**…*
  4. *dowhile**…*
  5. *repeatuntil**…*

Rather than writing a \lambda-term using the encodings that we’ve learnt, just implement the functions in OCaml / F#, using built-in int and bool types. You can use let rec instead of fix.

Do not use the imperative features of OCaml and F#, we will not even cover them in this course!

Despite we will not cover them, it is instructive to see the implementation using the imperative features, to better understand what is actually required of a solution to this exercise.

  1. let forto f begi endi s = let s = ref s in for i = begi to endi do
    s := f i !s done; !s
  2. let fordownto f begi endi s = let s = ref s in for i = begi downto endi do s := f i !s done; !s
  3. let whiledo p f s = let s = ref s in while p !s do s := f !s done;
    !s
  4. let dowhile p f s = let s = ref (f s) in while p !s do s := f !s
    done; !s
  5. let repeatuntil p f s = let s = ref (f s) in while not (p !s) do s := f !s done; !s

Lecture 5: Polymorphism & ADTs

Parametric types. Abstract Data Types.

Example: maps using red-black trees.

If you see any error on the slides, let me know!

1 Type Inference

We have seen the rules that govern the assignment of types to expressions, but how does OCaml guess what types to use, and when no correct types exist? It solves equations.

2 Parametric Types

3 Type Inference, Formally

\begin{matrix} \llbracket \Gamma \vdash x : \tau \rrbracket & = & \exists \overline{\beta'} \bar{\alpha}' . (D [\bar{\beta} \bar{\alpha} := \overline{\beta'} \bar{\alpha}'] \wedge \tau_{x} [\bar{\beta} \bar{\alpha} := \overline{\beta'} \bar{\alpha}'] \dot{=} \tau)\\\\\\ & & \text{where } \Gamma (x) = \forall \bar{\beta} [\exists \bar{\alpha} .D] . \tau_{x}, \overline{\beta'} \bar{\alpha}' \#\operatorname{FV} (\Gamma, \tau)\\\\\\ & & \\\\\\ \llbracket \Gamma \vdash \boldsymbol{\operatorname{fun}} x {\texttt{->}} e : \tau \rrbracket & = & \exists \alpha _{1} \alpha_{2} . (\llbracket \Gamma \lbrace x : \alpha_{1} \rbrace \vdash e : \alpha_{2} \rrbracket \wedge \alpha_{1} \rightarrow \alpha _{2} \dot{=} \tau),\\\\\\ & & \text{where } \alpha_{1} \alpha_{2} \#\operatorname{FV} (\Gamma, \tau)\\\\\\ & & \\\\\\ \llbracket \Gamma \vdash e_{1} e_{2} : \tau \rrbracket & = & \exists \alpha . (\llbracket \Gamma \vdash e_{1} : \alpha \rightarrow \tau \rrbracket \wedge \llbracket \Gamma \vdash e_{2} : \alpha \rrbracket), \alpha \#\operatorname{FV} (\Gamma, \tau)\\\\\\ & & \\\\\\ \llbracket \Gamma \vdash K e_{1} \ldots e_{n} : \tau \rrbracket & = & \exists \bar{\alpha}' . (\wedge_{i} \llbracket \Gamma \vdash e_{i} : \tau _{i} [\bar{\alpha} := \bar{\alpha}'] \rrbracket \wedge \varepsilon (\bar{\alpha}') \dot{=} \tau),\\\\\\ & & \text{w. } K \,:\, \forall \bar{\alpha} . \tau_{1} \times \ldots \times \tau_{n} \rightarrow \varepsilon (\bar{\alpha}), \bar{\alpha}' \#\operatorname{FV} (\Gamma, \tau)\\\\\\ & & \\\\\\ \llbracket \Gamma \vdash e : \tau \rrbracket & = & (\exists \beta .C) \wedge \llbracket \Gamma \lbrace x : \forall \beta [C] . \beta \rbrace \vdash e_{2} : \tau \rrbracket\\\\\\ e = \boldsymbol{\operatorname{let}} x = e_{1} \boldsymbol{\operatorname{in}} e_{2} & & \text{where } C = \llbracket \Gamma \vdash e_{1} : \beta \rrbracket\\\\\\ & & \\\\\\ \llbracket \Gamma \vdash e : \tau \rrbracket & = & (\exists \beta .C) \wedge \llbracket \Gamma \lbrace x : \forall \beta [C] . \beta \rbrace \vdash e_{2} : \tau \rrbracket\\\\\\ e = \boldsymbol{\operatorname{letrec}} x = e_{1} \boldsymbol{\operatorname{in}} e_{2} & & \text{where } C = \llbracket \Gamma \lbrace x : \beta \rbrace \vdash e_{1} : \beta \rrbracket\\\\\\ & & \\\\\\ \llbracket \Gamma \vdash e : \tau \rrbracket & = & \exists \alpha_{v} . \llbracket \Gamma \vdash e_{v} : \alpha_{v} \rrbracket \wedge_{i} \llbracket \Gamma \vdash p_{i} .e_{i} : \alpha_{v} \rightarrow \tau \rrbracket,\\\\\\ e = \boldsymbol{\operatorname{match}} e_{v} \boldsymbol{\operatorname{with}} \bar{c} & & \alpha_{v} \#\operatorname{FV} (\Gamma, \tau)\\\\\\ \bar{c} = p_{1} .e_{1} | \ldots |p_{n} .e_{n} & & \\\\\\ & & \\\\\\ \llbracket \Gamma, \Sigma \vdash p.e : \tau_{1} \rightarrow \tau_{2} \rrbracket & = & \llbracket \Sigma \vdash p \downarrow \tau_{1} \rrbracket \wedge \exists \bar{\beta} . \llbracket \Gamma \Gamma' \vdash e : \tau_{2} \rrbracket\\\\\\ & & \text{where } \exists \bar{\beta} \Gamma' \text{ is } \llbracket \Sigma \vdash p \uparrow \tau_{1} \rrbracket, \bar{\beta} \#\operatorname{FV} (\Gamma, \tau_{2})\\\\\\ & & \\\\\\ \llbracket \Sigma \vdash p \downarrow \tau_{1} \rrbracket & & \text{derives constraints on type of matched value}\\\\\\ & & \\\\\\ \llbracket \Sigma \vdash p \uparrow \tau_{1} \rrbracket & & \text{derives environment for pattern variables} \end{matrix}

3.1 Polymorphic Recursion

3.1.1 Polymorphic Rec: A list alternating between two types of elements

type (’x, ’o) alterning =| Stop| One of ’x * (’o, ’x) alterninglet rec tolist : ’x ’o ’a. (’x->’a) -> (’o->’a) -> (’x, ’o) alterning -> ’a list = fun x2a o2a -> function | Stop -> [] | One (x, rest) -> x2a x::tolist o2a x2a restlet tochoicelist alt = tolist (fun x->Left x) (fun o->Right o) altlet it = tochoicelist (One (1, One (“o”, One (2, One (“oo”, Stop)))))

3.1.2 Polymorphic Rec: Data-Structural Bootstrapping

type ’a seq = Nil | Zero of (’a * ’a) seq | One of ’a * (’a * ’a) seqWe store a list of elements in exponentially increasing chunks.let example = One (0, One ((1,2), Zero (One ((((3,4),(5,6)), ((7,8),(9,10))), Nil))))let rec cons : ’a. ’a -> ’a seq -> ’a seq = fun x -> functionAppending an element to the datastructure is like | Nil -> One (x, Nil)adding one to a binary number: 1+0=1 | Zero ps -> One (x, ps)1+…0=…1 | One (y, ps) -> Zero (cons (x,y) ps)1+…1=[…+1]0let rec lookup : ’a. int -> ’a seq -> ’a = fun i s -> match i, s withRather than returning None : 'a option | , Nil -> raise Notfoundwe raise exception, for convenience. | 0, One (x, ) -> x | i, One (, ps) -> lookup (i-1) (Zero ps) | i, Zero ps ->Random-Access lookup works let x, y = lookup (i / 2) ps inin logarithmic time – much faster than if i mod 2 = 0 then x else yin standard lists.

4 Algebraic Specification

4.1 Algebraic specifications: examples

uses ,

5 Homomorphisms

6 Example: Maps

, or
uses , type parameters
, ,

7 Modules and interfaces (signatures): syntax

module type MAP = sig type (’a, ’b) t val empty : (’a, ’b) t val member : ’a -> (’a, ’b) t -> bool val add : ’a -> ’b -> (’a, ’b) t -> (’a, ’b) t val remove : ’a -> (’a, ’b) t -> (’a, ’b) t val find : ’a -> (’a, ’b) t -> ’bendmodule ListMap : MAP = struct type (’a, ’b) t = (’a * ’b) list let empty = [] let member = List.memassoc let add k v m = (k, v)::m let remove = List.removeassoc let find = List.assocend

8 Implementing maps: Association lists

Let’s now build an implementation of maps from the ground up. The most straightforward implementation… might not be what you expected:

module TrivialMap : MAP = struct  type ('a, 'b) t =    | Empty    | Add of 'a 
\* 'b \* ('a, 'b) t    | Remove of 'a \* ('a, 'b) t          let empty = Empty 
 let rec member k m =    match m with      | Empty -> false      | Add 
(k2, , ) when k = k2 -> true      | Remove (k2, ) when k = k2 -> false 
     | Add (, , m2) -> member k m2      | Remove (, m2) -> member k m2 
 let add k v m = Add (k, v, m)  let remove k m = Remove (k, m)  let rec find k 
m =    match m with      | Empty -> raise Not_found      | Add (k2, v, ) 
when k = k2 -> v      | Remove (k2, ) when k = k2 -> raise Notfound    
  | Add (, , m2) -> find k m2      | Remove (, m2) -> find k m2 end

Here is an implementation based on association lists, i.e. on lists of key-value pairs.

module MyListMap : MAP = struct  type ('a, 'b) t = Empty | Add of 'a \* 'b \* 
('a, 'b) t  let empty = Empty  let rec member k m =    match m with      | 
Empty -> false      | Add (k2, , ) when k = k2 -> true      | Add (, , 
m2) -> member k m2  let rec add k v m =    match m with      | 
Empty -> Add (k, v, Empty)      | Add (k2, , m) when k = k2 -> Add (k, 
v, m)      | Add (k2, v2, m) -> Add (k2, v2, add k v m)

  let rec remove k m =    match m with      | Empty -> Empty      | Add 
(k2, , m) when k = k2 -> m      | Add (k2, v, m) -> Add (k2, v, remove 
k m)  let rec find k m =    match m with      | Empty -> raise Error      
| Add (k2, v, ) when k = k2 -> v      | Add (, , m2) -> find k m2 end

9 Implementing maps: Binary search trees

module BTreeMap : MAP = struct  type ('a, 'b) t = Empty | T of ('a, 'b) t \* 
'a \* 'b \* ('a, 'b) t  let empty = Empty  let rec member k m =‘‘Divide and 
conquer'' search through the tree.    match m with      | Empty -> false   
   | T (, k2, , ) when k = k2 -> true      | T (m1, k2, , ) when k < 
k2 -> member k m1      | T (, , , m2) -> member k m2  let rec add k v 
m =Searches the tree in the same way as `member`    match m withbut copies 
every node along the way.      | Empty -> T (Empty, k, v, Empty)      | T 
(m1, k2, , m2) when k = k2 -> T (m1, k, v, m2)      | T (m1, k2, v2, m2) 
when k < k2 -> T (add k v m1, k2, v2, m2)      | T (m1, k2, v2, 
m2) -> T (m1, k2, v2, add k v m2)

let rec splitrightmost m = (* A helper 
function, it does not belong *)
   match m with (* to the ‘‘exported'' signature.     *)
 | Empty -> raise Notfound      | T (Empty, k, v, Empty) -> k, v, 
EmptyWe remove one element,      | T (m1, k, v, m2) ->the one that is on 
the bottom right.        let rk, rv, rm = splitrightmost m2 in        rk, rv, 
T (m1, k, v, rm)

  let rec remove k m =    match m with      | Empty -> Empty      | T (m1, 
k2, , Empty) when k = k2 -> m1      | T (Empty, k2, , m2) when k = 
k2 -> m2      | T (m1, k2, , m2) when k = k2 ->        let rk, rv, rm 
= splitrightmost m1 in        T (rm, rk, rv, m2)      | T (m1, k2, v, m2) when 
k < k2 -> T (remove k m1, k2, v, m2)      | T (m1, k2, v, m2) -> 
T (m1, k2, v, remove k m2)  let rec find k m =    match m with      | 
Empty -> raise Notfound      | T (, k2, v, ) when k = k2 -> v      | T 
(m1, k2, , ) when k < k2 -> find k m1      | T (, , , m2) -> find 
k m2 end

10 Implementing maps: red-black trees

Based on Wikipedia http://en.wikipedia.org/wiki/Red-black_tree, Chris Okasaki’s “Functional Data Structures” and Matt Might’s excellent blog post http://matt.might.net/articles/red-black-delete/.

10.1 B-trees of order 4 (2-3-4 trees)

How can we have perfectly balanced trees without worrying about having 2^k - 1 elements? 2-3-4 trees can store from 1 to 3 elements in each node and have 2 to 4 subtrees correspondingly. Lots of freedom!

To insert “25” into (“.” stand for leaves, ignored later)

we descend right, but it is a full node, so we move the middle up and split the remaining elements:

Now there is a place between 24 and 29: next to 29

To represent 2-3-4 tree as a binary tree with one element per node, we color the middle element of a 4-node, or the first element of 2-/3-node, black and make it the parent of its neighbor elements, and make them parents of the original subtrees. Turning this:

Red-black_tree_B-tree.png

into this Red-Black tree:

Red-black_tree_example.png

10.2 Red-Black trees, without deletion

type color = R | Btype 'a t = E | T of color \* 'a t \* 'a \* 'a tlet empty = 
Elet rec member x m =  match m withLike in unbalanced binary search tree.  | 
Empty -> false  | T (, , y, ) when x = y -> true  | T (, a, y, ) when 
x < y -> member x a  | T (, , , b) -> member x blet balance = 
functionRestoring the invariants.  | B,T (R,T (R,a,x,b),y,c),z,dOn next 
figure: left,  | B,T (R,a,x,T (R,b,y,c)),z,dtop,  | B,a,x,T (R,T 
(R,b,y,c),z,d)bottom,  | B,a,x,T (R,b,y,T (R,c,z,d))right,    -> T (R,T 
(B,a,x,b),y,T (B,c,z,d))center tree.  | color,a,x,b -> T (color,a,x,b)We 
allow red-red violation for now.

let insert x s =  let rec ins = functionLike in unbalanced binary search tree, 
   | E -> T (R,E,x,E)but fix violation above created node.    | T 
(color,a,y,b) as s ->      if x<y then balance (color,ins a,y,b)      
else if x>y then balance (color,a,y,ins b)      else s in
  match ins s with (* We could still have red-red violation at root, *)
  | T (,a,y,b) -> T (B,a,y,b) (* fixed by coloring it black. *)
  | E -> failwith "insert: impossible"

11 Homework

  1. Derive the equations and solve them to find the type for:

    let cadr l = List.hd (List.tl l) in cadr (1::2::[]), cadr (true::false::[])

    in environ. \Gamma = \left\lbrace \text{{\textcolor{green}{List}}{\textcolor{blue}{.}}{\textcolor{brown}{hd}}} : \forall \alpha . \alpha \operatorname{list} \rightarrow \alpha ; \text{{\textcolor{green}{List}}{\textcolor{blue}{.}}{\textcolor{brown}{tl}}} : \forall \alpha . \alpha \operatorname{list} \rightarrow \alpha \operatorname{list} \right\rbrace. You can take “shortcuts” if it is too many equations to write down.

  2. What does it mean that an implementation has junk (as an algebraic structure for a given signature)? Is it bad?

  3. Define a monomorphic algebraic specification (other than, but similar to, \operatorname{nat}_{p} or \operatorname{string}_{p}, some useful data type).

  4. Discuss an example of a (monomorphic) algebraic specification where it would be useful to drop some axioms (giving up monomorphicity) to allow more efficient implementations.

  5. Does the example ListMap meet the requirements of the algebraic specification for maps? Hint: here is the definition of List.removeassoc; compare a x equals 0 if and only if a = x.

    let rec removeassoc x = function  | [] -> []  | (a, b as pair) :: l ->
          if compare a x = 0 then l else pair :: removeassoc x l
  6. Trick question: what is the computational complexity of ListMap or TrivialMap?

  7. * The implementation MyListMap is inefficient: it performs a lot of copying and is not tail-recursive. Optimize it (without changing the type definition).

  8. Add (and specify) \operatorname{isEmpty}: (\alpha, \beta) \operatorname{map} \rightarrow \operatorname{bool} to the example algebraic specification of maps without increasing the burden on its implementations (i.e. without affecting implementations of other operations). Hint: equational reasoning might be not enough; consider an equivalence relation \approx meaning “have the same keys”, defined and used just in the axioms of the specification.

  9. Design an algebraic specification and write a signature for first-in-first-out queues. Provide two implementations: one straightforward using a list, and another one using two lists: one for freshly added elements providing efficient queueing of new elements, and “reversed” one for efficient popping of old elements.

  10. Design an algebraic specification and write a signature for sets. Provide two implementations: one straightforward using a list, and another one using a map into the unit type.

  11. (Ex. 2.2 in Chris Okasaki “Purely Functional Data Structures”) In the worst case, member performs approximately 2 d comparisons, where d is the depth of the tree. Rewrite member to take no mare than d + 1 comparisons by keeping track of a candidate element that might be equal to the query element (say, the last element for which < returned false) and checking for equality only when you hit the bottom of the tree.

  12. (Ex. 3.10 in Chris Okasaki “Purely Functional Data Structures”) The balance function currently performs several unnecessary tests: when e.g.  ins recurses on the left child, there are no violations on the right child.

    1. Split balance into lbalance and rbalance that test for violations of left resp. right child only. Replace calls to balance appropriately.
    2. One of the remaining tests on grandchildren is also unnecessary. Rewrite ins so that it never tests the color of nodes not on the search path.
  13. * Implement maps (i.e. write a module for the map signature) based on AVL trees. See http://en.wikipedia.org/wiki/AVL_tree.

Functional Programming

Type Inference

Abstract Data Types

Exercise 1: Derive the equations and solve them to find the type for:

let cadr l = List.hd (List.tl l) in cadr (1::2::[]), cadr (true::false::[])

in environment \Gamma = \left\lbrace \text{{\textcolor{green}{List}}{\textcolor{blue}{.}}{\textcolor{brown}{hd}}} : \forall \alpha . \alpha \operatorname{list} \rightarrow \alpha ; \text{{\textcolor{green}{List}}{\textcolor{blue}{.}}{\textcolor{brown}{tl}}} : \forall \alpha . \alpha \operatorname{list} \rightarrow \alpha \operatorname{list} \right\rbrace. You can take “shortcuts” if it is too many equations to write down.

Exercise 2: Terms t_{1}, t_{2}, \ldots \in T (\Sigma, X) are built out of variables x, y, \ldots \in X and function symbols f, g, \ldots \in \Sigma the way you build values out of functions:

In OCaml, we can define terms as: type term = V of string | T of string term list5mm, where for example V(“x”) is a variable x and T(“f”, [V(“x”); V(“y”)]) is the term f (x, y).*

By substitutions* \sigma, \rho, \ldots we mean finite sets of variable, term pairs which we can write as \lbrace x_{1} \mapsto t_{1}, \ldots, x_{k} \mapsto t_{k} \rbrace or [x_{1} := t_{1} ; \ldots ; x_{k} := t_{k}], but also functions from terms to terms \sigma : T (\Sigma, X) \rightarrow T (\Sigma, X) related to the pairs as follows: if \sigma = \lbrace x_{1} \mapsto t_{1}, \ldots, x_{k} \mapsto t_{k} \rbrace, then*

In OCaml, we can define substitutions \sigma as: type subst = (string term) list, together with a function apply : subst -> term -> term which computes \sigma (\cdot).*

We say that a substitution \sigma is more general* than all substitutions \rho \circ \sigma, where (\rho \circ \sigma) (x) = \rho (\sigma (x)). In type inference, we are interested in most general solutions: the less general type judgement \text{{\textcolor{green}{List}}{\textcolor{blue}{.}}{\textcolor{brown}{hd}}} : \operatorname{int}\operatorname{list} \rightarrow \operatorname{int}, although valid, is less useful than \text{{\textcolor{green}{List}}{\textcolor{blue}{.}}{\textcolor{brown}{hd}}} : \forall \alpha . \alpha \operatorname{list} \rightarrow \alpha because it limits the usage of List.hd.*

A unification problem* is a finite set of equations S = \lbrace s_{1} =^? t_{1}, \ldots, s_{n} =^? t_{n} \rbrace which we can also write as s_{1} \dot{=} t_{1} \wedge \ldots \wedge s_{n} \dot{=} t_{n}. A solution, or unifier of S, is a substitution \sigma such that \sigma (s_{i}) = \sigma (t_{i}) for i = 1, \ldots, n. A most general unifier, for short MGU, is a most general such substitution.*

A substitution is idempotent* when \sigma = \sigma \circ \sigma. If \sigma = \lbrace x_{1} \mapsto t_{1}, \ldots, x_{k} \mapsto t_{k} \rbrace, then \sigma is idempotent exactly when no t_{i} contains any of the variables \lbrace x_{1}, \ldots, x_{n} \rbrace; i.e. \lbrace x_{1}, \ldots, x_{n} \rbrace \cap \operatorname{Vars} (t_{1}, \ldots, t_{n}) = \varnothing.*

  1. Implement an algorithm that, given a set of equations represented as a list of pairs of terms, computes an idempotent most general unifier of the equations.
  2. ** (Ex. 4.22 in* *Franz Baader and Tobias Nipkov “Term Rewriting and All That”**, p. 82.) Modify the implementation of unification to achieve linear space complexity by working with what could be called iterated substitutions. For example, the solution to* \lbrace x =^? f (y), y =^? g (z), z =^? a \rbrace should be represented as variable, term pairs (x, f (y)), (y, g (z)), (z, a). (Hint: iterated substitutions should be unfolded lazily, i.e. only so far that either a non-variable term or the end of the instantiation chain is found.)

Exercise 3:

  1. What does it mean that an implementation has junk (as an algebraic structure for a given signature)? Is it bad?
  2. Define a monomorphic algebraic specification (other than, but similar to, \operatorname{nat}_{p} or \operatorname{string}_{p}, some useful data type).
  3. Discuss an example of a (monomorphic) algebraic specification where it would be useful to drop some axioms (giving up monomorphicity) to allow more efficient implementations.

Exercise 4:

  1. Does the example ListMap meet the requirements of the algebraic specification for maps? Hint: here is the definition of List.removeassoc;*compare a x* equals 0 if and only if *a*=*x*.

    let rec removeassoc x = function | [] -> [] | (a, b as pair) :: l -> if compare a x = 0 then l else pair :: removeassoc x l

  2. Trick question: what is the computational complexity of ListMap or TrivialMap?

  3. ** The implementation* MyListMap is inefficient: it performs a lot of copying and is not tail-recursive. Optimize it (without changing the type definition).

  4. Add (and specify) \operatorname{isEmpty}: (\alpha, \beta) \operatorname{map} \rightarrow \operatorname{bool} to the example algebraic specification of maps without increasing the burden on its implementations (i.e. without affecting implementations of other operations). Hint: equational reasoning might be not enough; consider an equivalence relation \approx meaning “have the same keys”, defined and used just in the axioms of the specification.

Exercise 5: Design an algebraic specification and write a signature for first-in-first-out queues. Provide two implementations: one straightforward using a list, and another one using two lists: one for freshly added elements providing efficient queueing of new elements, and “reversed” one for efficient popping of old elements.

Exercise 6: Design an algebraic specification and write a signature for sets. Provide two implementations: one straightforward using a list, and another one using a map into the unit type.

Exercise 7:

  1. (Ex. 2.2 in *Chris Okasaki “Purely Functional Data Structures”**) In the worst case,* *member* performs approximately 2 d comparisons, where d is the depth of the tree. Rewrite *member* to take no mare than d + 1 comparisons by keeping track of a candidate element that might be equal to the query element (say, the last element for which < returned false) and checking for equality only when you hit the bottom of the tree.
  2. (Ex. 3.10 in *Chris Okasaki “Purely Functional Data Structures”**) The *balance* function currently performs several unnecessary tests: when e.g.* *ins* recurses on the left child, there are no violations on the right child.
    1. Split *balance* into *lbalance* and *rbalance* that test for violations of left resp. right child only. Replace calls to *balance* appropriately.
    2. One of the remaining tests on grandchildren is also unnecessary. Rewrite *ins* so that it never tests the color of nodes not on the search path.

Lecture 6: Folding and Backtracking

Mapping and folding.Backtracking using lists. Constraint solving.

Martin Odersky ‘‘Functional Programming Fundamentals’’ Lectures 2, 5 and 6

Bits of Ralf Laemmel ‘‘Going Bananas’’

Graham Hutton ‘‘Programming in Haskell’’ Chapter 11 ‘‘Countdown Problem’’

Tomasz Wierzbicki ‘‘Honey Islands Puzzle Solver’’

If you see any error on the slides, let me know!

1 Plan

2 Basic generic list operations

How to print a comma-separated list of integers? In module String:

val concat : string -> string list -> string

First convert numbers into strings:

let rec stringsofints = function | [] -> [] | hd::tl -> stringofint hd :: stringsofints tllet commasepints = String.concat “,” -| stringsofints

How to get strings sorted from shortest to longest? First find the length:

let rec stringslengths = function | [] -> [] | hd::tl -> (String.length hd, hd) :: stringslengths tllet bysize = List.sort compare -| stringslengths

2.1 Always extract common patterns

1.589482.889124.91267032676283.016123164439747.15635335361822.783288133350976.098012303214712.127116682100812.139816774705652.127116682100811.483645323455482.296451250165373.70616-0.561076.6695164704326-0.4552354808837159.37886955946554-0.6034032279402048.15119394099749-1.323075142214584.36233298055298-1.19607421616616-8.062594.51897-5.437905146183364.62480156105305-2.538050668077794.56130109802884-3.5117244344493.79929554173833-7.575754067998413.92629646778674-7.914421.15344-4.506565021828281.30161066278608-2.453383384045510.984108347665035-3.659892181505490.391437359439079-7.575754067998410.4549378224632891.483652.27528-0.506035851303082-3.630258632094194.34117-1.217240.255969704987432-3.63025863209419-7.639253.88396-7.66042135203069-2.1485811615293-3.659890.370271-6.55974665961106-2.12741434052123-8.16843-2.31792-5.94590885037703-2.21208162455351-4.16789588569917-2.27558208757772-4.76056687392512-2.88941989681175-7.78742227807911-2.86825307580368-2.72855-3.79959-0.506035851303082-3.630258632094190.742806588173039-4.053595052255590.213636062971293-4.60393239846541-2.79205252017463-4.41343100939278-5.840072.78329-2.919053446223053.01612316443974-1.05637319751292.78328813335097-1.691377827754992.14828350310888-5.395571504167222.23295078714116-5.33207-0.476402-0.992872734488689-0.2647340918110861.75881399656039-0.5399027649159940.785140230189178-1.21724103717423-4.52773184283635-1.19607421616616-5.459072.19062-5.62840653525599-3.71492591612647-4.52773-1.23841-5.45907196719143-3.778426379150680cm

Now use the generic function:

let commasepints = String.concat “,” -| listmap stringofintlet bysize =
List.sort compare -| listmap (fun s->String.length s, s)

How to sum elements of a list?
How to multiply elements in a list?
Generic solution:
Caution: list_fold f base l = List.fold_right f l base.

-6.968285.20805-5.592439476121185.48321537240376-4.237762931604715.22921352030692-4.576432067733834.72120981611324-6.354445032411694.70004299510517-6.693111.18635-4.682266172774181.24985117078979-2.756085461039821.1016834237333-3.306422807249640.509012435507342-6.354445032411690.466678793491203-2.269253.7687-0.8722383913216043.7687028707501-0.1102328350310893.45120055562905-0.5759028972086263.04903095647572-2.692584998015613.11253141949993-2.37508-0.549329-0.512402434184416-0.3799940468315911.73128059267099-0.591662256912291.05394232041275-1.16316642413018-2.03641354676544-1.12083278211404-6.92595-2.36968-4.02609472152401-2.11567336949332-0.999239317370023-2.34850840058209-1.48607620055563-2.87767892578383-6.07927635930679-2.87767892578383-2.26925-3.914851.49844556158222-3.809019050138913.40345945230851-4.063020902235752.93778939013097-4.52869096441328-1.27440799047493-4.61335824844556-6.354454.70004-6.10044318031486-2.2003406535256-3.306420.509012-5.10853954194466-2.14605530848409-2.734923.11253-1.38460084405009-3.806950349498371.05394-1.184330.19997872622222-3.78626681481166-3.560423.4512-3.200588702209293.133698240508-3.073587776160873.64170194470168-3.58159-0.760997-2.90425320809631-0.54932861489615-2.75608546103982-0.866830930017198-4.70343-4.21119-4.08959518454822-4.10535454425189-4.1742624685805-4.48635732239714-3.242923.11253-4.3859306786612-3.87251951316312-3.26132-1.28056-4.23776293160471-3.95718679719540cm

map alters the contents of data fold computes a value using
without changing the structure: the structure as a scaffolding:

2.2 Can we make fold tail-recursive?

Let’s investigate some tail-recursive functions. (Not hidden as helpers.)

acc

hd

tot
hd tl



-5.909944.94728-3.729759227411035.01078184945099-1.486076200555634.88378092340257-2.099914009789654.33344357719275-5.338437624024344.26994311416854-5.867611.47592-2.756085461039821.666424130175950.7152731842836351.49708956211139-0.4489019711602060.925585394893504-4.936268024871010.925585394893504-6.01578-2.79978-2.69258499801561-2.56694007143802-0.152566477047228-2.79977510252679-0.427735150152137-3.30777880672047-4.57643206773383-3.35011244873661-3.750933.06343-2.121080830797723.29626934779733-0.5970697182166953.04226749570049-2.226914935838072.55543061251488-4.02609-1.1911-2.45974996692684-0.852427569784363-1.21090752745072-1.25459716893769-2.43858314591877-1.63559994708295-4.5341-4.40845-2.37508268289456-4.28145257309168-0.343067866119857-4.4084534991401-1.02040613837809-4.93762402434184-3.83559333245138-4.93762402434184-0.1102333.296271.498445561582223.423270273845752.874288927106763.232768884773122.175783833840452.555430612514880.1437690170657492.57659743352295-0.491236-0.9582623.61512766238921-0.8100939277682237.04415266569652-1.064095779865065.71064294218812-1.720267231115230.524771795211007-1.677933589099090.376604-4.302622.21811747585659-4.239118931075543.61512766238921-4.429620320148173.17062442121974-4.916457203333770.799940468315915-4.95879084534991-5.338444.29111-6.07927635930679-2.16477047228469-5.69827358116153-2.69394099748644-4.957430.967919-5.48660537108083-1.97426908321207-5.44427172906469-2.6516073554703-2.226912.55543-2.03641354676544-3.62528112184151-2.37508268289456-4.28145257309168-2.41742-1.61443-2.69258499801561-3.79461568990607-2.80072853017803-4.283284085867292.895463.253945.64714247916391-2.397605503373463.72096176742955-4.429620320148174.73754-1.786764.14429818759095-3.413612911760813.50929355734886-4.323786215107820.5036052.70363.00128985315518-4.49312078317238-0.0678992-1.50862.89545574811483-4.598954888212731.752452.70361.62544648763064-4.450787141156242.47212-1.57213.04362349517132-2.461105966397676.17631-1.50863.04362349517132-2.461105966397673.04362-2.461112.02761608678397-4.366119857123960cm

3 map and fold for trees and other structures

3.1 map and fold for more complex structures

To have a data structure to work with, we recall expressions from lecture 3.

type expression = Const of float | Var of string | Sum of expression * expression (* e1 + e2 ) | Diff of expression expression (* e1 - e2 ) | Prod of expression expression (* e1 * e2 ) | Quot of expression expression (* e1 / e2 *)

Multitude of cases make the datatype harder to work with. Fortunately, or-patterns help a bit:

let rec vars = function | Const -> [] | Var x -> [x] | Sum (a,b) | Diff (a,b) | Prod (a,b) | Quot (a,b) -> vars a @ vars b

Mapping and folding needs to be specialized for each case. We pack the behaviors into a record.

type expressionmap = { mapconst : float -> expression; mapvar : string -> expression; mapsum : expression -> expression -> expression; mapdiff : expression -> expression -> expression;
mapprod : expression -> expression -> expression; mapquot : expression -> expression -> expression;}Note how expression from above is substituted by 'a below, explain why?type ’a expressionfold = {
foldconst : float -> ’a; foldvar : string -> ’a; foldsum : ’a -> ’a -> ’a; folddiff : ’a -> ’a -> ’a; foldprod : ’a -> ’a -> ’a; foldquot : ’a -> ’a -> ’a;}

Next we define standard behaviors for map and fold, which can be tailored to needs for particular case.

let identitymap = { mapconst = (fun c -> Const c); mapvar = (fun x -> Var x); mapsum = (fun a b -> Sum (a, b)); mapdiff = (fun a b -> Diff (a, b)); mapprod = (fun a b -> Prod (a, b)); mapquot = (fun a b -> Quot (a, b));}let makefold op base = { foldconst = (fun -> base); foldvar = (fun -> base); foldsum = op; folddiff = op;
foldprod = op; foldquot = op;}

The actual map and fold functions are straightforward:

let rec exprmap emap = function | Const c -> emap.mapconst c | Var x -> emap.mapvar x | Sum (a,b) -> emap.mapsum (exprmap emap a) (exprmap emap b) | Diff (a,b) -> emap.mapdiff (exprmap emap a) (exprmap emap b) | Prod (a,b) -> emap.mapprod (exprmap emap a) (exprmap emap b) | Quot (a,b) -> emap.mapquot (exprmap emap a) (exprmap emap b)let rec exprfold efold = function | Const c -> efold.foldconst c | Var x -> efold.foldvar x | Sum (a,b) -> efold.foldsum (exprfold efold a) (exprfold efold b) | Diff (a,b) -> efold.folddiff (exprfold efold a) (exprfold efold b) | Prod (a,b) -> efold.foldprod (exprfold efold a) (exprfold efold b) | Quot (a,b) -> efold.foldquot (exprfold efold a) (exprfold efold b)

Now examples. We use {record with field=value} syntax which copies record but puts value instead of record.field in the result.

let primevars = exprmap {identitymap with mapvar = fun x -> Var (x”’“)}let subst s = let apply x = try List.assoc x s with Notfound -> Var x in exprmap {identitymap with mapvar = apply}let vars = exprfold {(makefold (@) []) with foldvar = fun x-> [x]}let size = exprfold (makefold (fun a b->1+a+b) 1)let eval env = exprfold { foldconst = id;
foldvar = (fun x -> List.assoc x env); foldsum = (+.); folddiff = (-.);
foldprod = ( *.); foldquot = (/.);}

4 Point-free Programming



-9.51-4.01.0-9.4935-0.00601931-4.00.0Char.escaped-41string_of_int-4.05-5.47857e-050.513.50.50.5395720333377430.0151475062839uncurry (^)3.50.57.50.510.50.50cm

5 Reductions. More higher-order/list functions

Mathematics has notation for sum over an interval: \sum_{n = a}^b f (n).

In OCaml, we do not have a universal addition operator:

let rec isumfromto f a b = if a > b then 0 else f a + isumfromto f (a+1) blet rec fsumfromto f a b = if a > b then 0. else f a +. fsumfromto f (a+1) blet pi2over6 = fsumfromto (fun i->1. /. floatofint (i*i)) 1 5000

It is natural to generalize:

let rec opfromto op base f a b = if a > b then base else op (f a) (opfromto op base f (a+1) b)

Let’s collect the results of a multifunction (i.e. a set-valued function) for a set of arguments, in math notation:

f (A) = \bigcup_{p \in A} f (p)

It is a useful operation over lists with union translated as append:

let rec concatmap f = function | [] -> [] | a::l -> f a @ concatmap f l

and more efficiently:

let concatmap f l = let rec cmapf accu = function | [] -> accu | a::l -> cmapf (List.revappend (f a) accu) l in List.rev (cmapf [] l)

5.1 List manipulation: All subsequences of a list

let rec subseqs l = match l with | [] -> [[]] | x::xs ->
let pxs = subseqs xs in List.map (fun px -> x::px) pxs @ pxs

Tail-recursively:

let rec rmapappend f accu = function | [] -> accu | a::l -> rmapappend f (f a :: accu) l

let rec subseqs l = match l with | [] -> [[]] | x::xs ->
let pxs = subseqs xs in rmapappend (fun px -> x::px) pxs pxs

In-class work: Return a list of all possible ways of splitting a list into two non-empty parts.

Homework:

Find all permutations of a list.

Find all ways of choosing without repetition from a list.

5.2 By key: group_by and map_reduce

It is often useful to organize values by some property.

First we collect an elements from an association list by key.

let collect l = match List.sort (fun x y -> compare (fst x) (fst y)) l with | [] -> []Start with associations sorted by key. | (k0, v0)::tl -> let k0, vs, l = List.foldleft (fun (k0, vs, l) (kn, vn) ->Collect values for the current key if k0 = kn then k0, vn::vs, land when the key changes else kn, [vn], (k0,List.rev vs)::l)stack the collected values. (k0, [v0], []) tl inWhat do we gain by reversing?
List.rev ((k0,List.rev vs)::l)

Now we can group by an arbitrary property:

let groupby p l = collect (List.map (fun e->p e, e) l)

But we want to process the results, like with an aggregate operation in SQL. The aggregation operation is called reduction.

let aggregateby p red base l = let ags = groupby p l in List.map (fun (k,vs)->k, List.foldright red vs base) ags

We can use the feed-forward operator: let ( |> ) x f = f x

let aggregateby p redf base l = groupby p l |> List.map (fun (k,vs)->k, List.foldright redf vs base)

Often it is easier to extract the property over which we aggregate upfront. Since we first map the elements into the extracted key-value pairs, we call the operation map_reduce:

let mapreduce mapf redf base l = List.map mapf l |> collect |> List.map (fun (k,vs)->k, List.foldright redf vs base)

5.2.1 map_reduce/concat_reduce examples

Sometimes we have multiple sources of information rather than records.

let concatreduce mapf redf base l = concatmap mapf l |> collect |> List.map (fun (k,vs)->k, List.foldright redf vs base)

Compute the merged histogram of several documents:

let histogram documents = let mapf doc = Str.split (Str.regexp “[ t.,;]+”) doc |> List.map (fun word->word,1) in concatreduce mapf (+) 0 documents

Now compute the inverted index of several documents (which come with identifiers or addresses).

let cons hd tl = hd::tllet invertedindex documents = let mapf (addr, doc) =
Str.split (Str.regexp “[ t.,;]+”) doc |> List.map (fun word->word,addr) in concatreduce mapf cons [] documents

And now… a “search engine”:

let search index words = match List.map (flip List.assoc index) words with | [] -> [] | idx::idcs -> List.foldleft intersect idx idcs

where intersect computes intersection of sets represented as lists.

5.2.2 Tail-recursive variants

let revcollect l = match List.sort (fun x y -> compare (fst x) (fst y)) l with | [] -> [] | (k0, v0)::tl -> let k0, vs, l = List.foldleft
(fun (k0, vs, l) (kn, vn) -> if k0 = kn then k0, vn::vs, l
else kn, [vn], (k0, vs)::l) (k0, [v0], []) tl in List.rev ((k0, vs)::l)

let trconcatreduce mapf redf base l = concatmap mapf l |> revcollect
|> List.revmap (fun (k,vs)->k, List.foldleft redf base vs)

let rcons tl hd = hd::tllet invertedindex documents = let mapf (addr, doc) = … in trconcatreduce mapf rcons [] documents

5.2.3 Helper functions for inverted index demonstration

let intersect xs ys =Sets as sorted lists. let rec aux acc = function
| [], | , [] -> acc | (x::xs’ as xs), (y::ys’ as ys) -> let c = compare x y in if c = 0 then aux (x::acc) (xs’, ys’) else if c < 0 then aux acc (xs’, ys) else aux acc (xs, ys’) in List.rev (aux [] (xs, ys))

let readlines file = let input = openin file in let rec read lines =The Scanf library uses continuation passing. try Scanf.fscanf input “%[]” (fun x -> read (x :: lines)) with Endoffile -> lines in
List.rev (read [])

let indexed l =Index elements by their positions. Array.oflist l |> Array.mapi (fun i e->i,e) |> Array.tolist

let searchengine lines = let lines = indexed lines in let index = invertedindex lines in fun words -> let ans = search index words in
List.map (flip List.assoc lines) ans

let searchbible = searchengine (readlines “./bible-kjv.txt”)let testresult =
searchbible [“Abraham”; “sons”; “wife”]

5.3 Higher-order functions for the option type

Operate on an optional value:

let mapoption f = function | None -> None | Some e -> f e

Map an operation over a list and filter-out cases when it does not succeed:

let rec mapsome f = function | [] -> [] | e::l -> match f e with
| None -> mapsome f l | Some r -> r :: mapsome f lTail-recurively:

let mapsome f l = let rec mapsf accu = function | [] -> accu | a::l -> mapsf (match f a with None -> accu | Some r -> r::accu) l in List.rev (mapsf [] l)

6 The Countdown Problem Puzzle

6.1 Brute force solution

6.2 Fuse the generate phase with the test phase

6.3 Eliminate symmetric cases

7 The Honey Islands Puzzle

Task: 3 islands x 3Solution:

7.1 Representing the honeycomb

type cell = int * intWe address cells using ‘‘cartesian’’ coordinatesmodule CellSet =and store them in either lists or sets. Set.Make (struct type t = cell let compare = compare end)type task = {For board ‘‘size’’ N, the honeycomb coordinates boardsize : int;range from (- 2 N, - N) to 2 N, N.
numislands : int;Required number of islands islandsize : int;and required number of cells in an island. emptycells : CellSet.t;The cells that are initially without honey.}

let cellsetoflist l =List into set, inverse of CellSet.elements
List.foldright CellSet.add l CellSet.empty

7.1.1 Neighborhood

x,y-0.902203-0.291672x+2,y2.23049-0.376339x+1,y+10.410142.35418x-1,y+1-2.637882.33301x-2,y-4.20423-0.418673x-1,y-1-2.65905-3.08569x+1,y-10.431307-3.191530cm

let neighbors n eaten (x,y) = List.filter (insideboard n eaten) [x-1,y-1; x+1,y-1; x+2,y; x+1,y+1; x-1,y+1; x-2,y]

7.1.2 Building the honeycomb

0,0-0.373032-0.1543520,2-0.3730323.041840,-2-0.394199-3.541041,10.5159741.496664,03.33116-0.239023,12.505661.496662,21.510813.063-2,0-2.23571-0.1543520cm

let even x = x mod 2 = 0

let insideboard n eaten (x, y) = even x = even y && abs y <= n && abs x + abs y <= 2*n && not (CellSet.mem (x,y) eaten)

let honeycells n eaten = fromto (-2n) (2n)|->(fun x -> fromto (-n) n |-> (fun y -> guard (insideboard n eaten) (x, y)))

7.1.3 Drawing honeycombs

We separately generate colored polygons:

let drawhoneycomb \simw \simh task eaten = let i2f = floatofint in let nx = i2f (4 * task.boardsize + 2) in let ny = i2f (2 * task.boardsize + 2) in let radius = min (i2f w /. nx) (i2f h /. ny) in let x0 = w / 2 in let y0 = h / 2 in let dx = (sqrt 3. /. 2.) . radius +. 1. inThe distance between let dy = (3. /. 2.) . radius +. 2. in(x, y) and (x + 1, y + 1). let drawcell (x,y) = Array.init 7We draw a closed polygon by placing 6 points (fun i ->evenly spaced on a circumcircle. let phi = floatofint i . pi /. 3. in x0 + intoffloat (radius . sin phi +. floatofint x . dx), y0 + intoffloat (radius . cos phi +. floatofint y *. dy)) in let honey = honeycells task.boardsize (CellSet.union task.emptycells (cellsetoflist eaten)) |> List.map (fun p->drawcell p, (255, 255, 0)) in let eaten = List.map (fun p->drawcell p, (50, 0, 50)) eaten in let oldempty = List.map (fun p->drawcell p, (0, 0, 0)) (CellSet.elements task.emptycells) in honey @ eaten @ oldempty

We can draw the polygons to an SVG image:

let drawtosvg file \simw \simh ?title ?desc curves = let f = openout file in Printf.fprintf f “<!DOCTYPE svg PUBLIC”-//W3C//DTD SVG 1.1//EN” “http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd”>” w h w h; (match title with None -> () | Some title -> Printf.fprintf f ” %s

n” title); (match desc with None -> () | Some desc -> Printf.fprintf f ” %sn” desc); let drawshape (points, (r,g,b)) = uncurry (Printf.fprintf f ” <path d=“M %d %d”) points.(0); Array.iteri (fun i (x, y) -> if i > 0 then Printf.fprintf f ” L %d %d” x y) points; Printf.fprintf f ““n fill=”rgb(%d, %d, %d)” stroke-width=“3” />n” r g b in List.iter drawshape curves; Printf.fprintf f “%!”

But we also want to draw on a screen window – we need to link the Graphics library. In the interactive toplevel:

##load “graphics.cma”;;

When compiling we just provide graphics.cma to the command.

let drawtoscreen \simw \simh curves = Graphics.opengraph (” “stringofint w”x”stringofint h); Graphics.setcolor (Graphics.rgb 50 50 0);We draw a brown background. Graphics.fillrect 0 0 (Graphics.sizex ()) (Graphics.sizey ()); List.iter (fun (points, (r,g,b)) -> Graphics.setcolor (Graphics.rgb r g b); Graphics.fillpoly points) curves; if Graphics.readkey () = 'q'We wait so that solutions can be seen then failwith “User interrupted finding solutions.”;as they’re computed. Graphics.closegraph ()

7.2 Testing correctness of a solution

We walk through each island counting its cells, depth-first: having visited everything possible in one direction, we check whether something remains in another direction.

Correctness means there are numislands components each with islandsize cells. We start by computing the cells to walk on: honey.

let checkcorrect n islandsize numislands emptycells = let honey = honeycells n emptycells in

We keep track of already visited cells and islands. When an unvisited cell is there after walking around an island, it must belong to a different island.

let rec checkboard beenislands unvisited visited = match unvisited with
| [] -> beenislands = numislands | cell::remaining when CellSet.mem cell visited -> checkboard been_islands remaining visitedKeep looking.
| cell::remaining (* when not visited *) -> let (beensize, unvisited, visited) = checkisland cellVisit another island.(1, remaining, CellSet.add cell visited) in beensize = islandsize && checkboard (beenislands+1) unvisited visited

When walking over an island, besides the unvisited and visited cells, we need to remember been_size – number of cells in the island visited so far.

and checkisland current state = neighbors n emptycells current |> List.foldleft Walk into each direction and accumulate visits.(fun (beensize, unvisited, visited as state) neighbor -> if CellSet.mem neighbor visited then state else let unvisited = remove neighbor unvisited in let visited = CellSet.add neighbor visited in
let beensize = beensize + 1 in checkisland neighbor
(beensize, unvisited, visited)) state inStart from the current overall state (initial been_size is 1).

Initially there are no islands already visited.

checkboard 0 honey emptycells

7.3 Interlude: multiple results per step

When there is only one possible result per step, we work through a list using List.foldright and List.foldleft functions.

What if there are multiple results? Recall that when we have multiple sources of data and want to collect multiple results, we use concat_map:

-4.568261.32331-3.509921.34447-2.218751.32331-0.9699031.323310.3424391.30214-4.568261.32331-5.541936764122240.264965603915862-4.568261.32331-4.695263923799440.328466066940071-4.568261.32331-4.039092472549280.286132424923932-3.509921.34447-3.573422410371740.391966529964281-3.509921.34447-2.896084138113510.370799708956211-2.218751.32331-2.451580896944040.434300171980421-0.9699031.32331-1.604908056621250.413133350972351-0.9699031.32331-0.8640693213388010.3919665299642811.316111.386811.316111.386810.405939939145390.4554669929884911.316111.386811.083278211403620.476633813996561.316111.386811.8029501256780.4131333509723511.316111.386812.586122502976580.54013427702077-5.541940.264966-5.541940.264966-4.695260.328466-4.039090.286132-3.573420.391967-2.896080.3708-2.451580.4343-1.604910.413133-0.8640690.3919670.405940.4554671.083280.4766341.802950.4131332.586120.540134-5.774770.624802-6.007606826299780.56130109802884-6.02877364730784-0.0525367112051859-5.73243815319487-0.116037174229395-4.017930.794136-3.890924725492790.56130109802884-3.933258367508930.0109637518190237-4.22959386162191-0.116037174229395-3.763920.878803-3.679256515412090.0532973938351634-3.44642148432332-0.031369890197116-2.874920.89997-2.769083212065090.688302024077259-2.76908321206509-0.0102030691890462-2.98075142214579-0.031369890197116-2.557420.89997-2.557415001984390.0956310358513031-2.45158089694404-0.0737035322132557-2.091740.815303-2.007077655774570.688302024077259-2.070578118798780.0744642148432332-2.23991268686334-0.031369890197116-1.668410.878803-1.816576266701940.794136129117608-1.837743087710010.0532973938351634-1.62607487762932-0.137203995237465-0.6312340.878803-0.4830665431935440.794136129117608-0.5254001852096840.0956310358513031-0.821735679322662-0.0948703532213256-0.01739650.857637-0.1443974070644270.794136129117608-0.2078978700886360.264965603915862-0.1443974070644270.1379646778674430.1731050.7518020.0672708030162720.1591314988755130.469440.8788030.300105834105040.9634706971821670.278939013096970.05329739383516340.4271067601534590.05329739383516342.649620.9423042.882457997089560.8999702341579572.84012435507342-0.0313698901971162.48028839793623-0.0525367112051859-5.541940.264966-5.54193676412224-0.539373594390792-4.695260.328466-4.71643074480751-0.560540415398862-3.573420.391967-3.55225558936367-0.539373594390792-2.896080.3708-2.89608413811351-0.539373594390792-1.604910.413133-1.62607487762932-0.560540415398862-0.8640690.391967-0.864069321338801-0.5817072364069320.405940.4554670.38477311813732-0.5605404153988621.083280.4766341.06211139039556-0.4970399523746531.802950.4131331.78178330466993-0.4758731313665832.586120.5401342.5014552189443-0.497039952374653-5.54194-0.539374-4.71643-0.56054-3.55226-0.539374-2.89608-0.539374-1.62607-0.56054-0.864069-0.5817070.384773-0.560541.06211-0.497041.78178-0.4758732.50146-0.49704-5.541941.55614-5.859439079243291.47147440137584-5.859439079243291.11163844423866-5.626604048154520.9846375181902372.120451.534972.416787934912031.492641222383912.416787934912031.196305728270942.205119724831331.13280526524673-5.98644-0.306539-6.28277549940468-0.348872205318164-6.24044185738854-0.687541341447281-5.9229395422675-0.856875909511842.96713-0.2218713.30579441725096-0.3700390263262343.30579441725096-0.6452076994311422.88245799708956-0.85687590951184concat_map-11.06650.984638f xs =-10.34680.264966List.map f xs3.707961.04814|> List.concat3.87730.0744642

We shortened concat_map calls using “work |-> (fun a_result -> …)” scheme. Here we need to collect results once per step.

let rec concatfold f a = function | [] -> [a] | x::xs -> f x a |-> (fun a’ -> concatfold f a’ xs)

7.4 Generating a solution

We turn the code for testing a solution into one that generates a correct solution.

The generating function has the same signature as the testing function:

let findtoeat n islandsize numislands emptycells = let honey = honeycells n emptycells in

Since we return lists of solutions, if we are done with current solution eaten we return [eaten], and if we are in a “dead corner” we return [].

let rec findboard beenislands unvisited visited eaten = match unvisited with | [] -> if beenislands = numislands then [eaten] else [] | cell::remaining when CellSet.mem cell visited -> findboard beenislands remaining visited eaten | cell::remaining (* when not visited *) -> findisland cell (1, remaining, CellSet.add cell visited, eaten) |->Concatenate solutions for each way of eating cells around and island. (fun (beensize, unvisited, visited, eaten) ->
if beensize = islandsize then findboard (beenislands+1)
unvisited visited eaten else [])

We step into each neighbor of a current cell of the island, and either eat it or walk further.

and findisland current state = neighbors n emptycells current |> concatfoldInstead of fold_left since multiple results.(fun neighbor
(beensize, unvisited, visited, eaten as state) -> if CellSet.mem neighbor visited then [state] else let unvisited = remove neighbor unvisited in let visited = CellSet.add neighbor visited in (beensize, unvisited, visited,
neighbor::eaten):: (* solutions where neighbor is honey *)
findisland neighbor (beensize+1, unvisited, visited, eaten)) state in

The initial partial solution is – nothing eaten yet.

checkboard 0 honey emptycells []

We can test it now:

let w = 800 and h = 800let ans0 = findtoeat testtask0.boardsize testtask0.islandsize testtask0.numislands testtask0.emptycellslet = drawtoscreen \simw \simh (drawhoneycomb \simw \simh testtask0 (List.hd ans0))

But in a more complex case, finding all solutions takes too long:

let ans1 = findtoeat testtask1.boardsize testtask1.islandsize testtask1.numislands testtask1.emptycellslet = drawtoscreen \simw \simh (drawhoneycomb \simw \simh testtask1 (List.hd ans1))

(See Lec6.ml for definitions of test cases.)

7.5 Optimizations for Honey Islands

type state = { beensize: int;Number of honey cells in current island.
beenislands: int;Number of islands visited so far. unvisited: cell list;Cells that need to be visited. visited: CellSet.t;Already visited. eaten: cell list;Current solution candidate. moretoeat: int;Remaining cells to eat for a complete solution.}

We define the basic operations on the state up-front. If you could keep them inlined, the code would remain more similar to the previous version.

let rec visitcell s = match s.unvisited with | [] -> None | c::remaining when CellSet.mem c s.visited -> visitcell {s with unvisited=remaining} | c::remaining (* when c not visited *) -> Some (c, {s with unvisited=remaining; visited = CellSet.add c s.visited})

let eatcell c s = {s with eaten = c::s.eaten; visited = CellSet.add c s.visited; moretoeat = s.moretoeat - 1}

let keepcell c s =Actually c is not used… {s with beensize = s.beensize + 1; visited = CellSet.add c s.visited}

let freshisland s =We increase been_size at the start of find_island {s with beensize = 0;rather than before calling it. beenislands = s.beenislands + 1}

let initstate unvisited moretoeat = { beensize =5mm 0; beenislands = 0;
unvisited; visited = CellSet.empty; eaten = []; moretoeat;}

We need a state to begin with:

let initstate unvisited moretoeat = { beensize = 0; beenislands = 0;
unvisited; visited = CellSet.empty; eaten = []; moretoeat;}

The “main loop” only changes because of the different handling of state.

let rec findboard s = match visitcell s with | None -> if s.beenislands = numislands then [eaten] else [] | Some (cell, s) ->
findisland cell (freshisland s) |-> (fun s -> if s.beensize = s.islandsize then findboard s else [])

In the “island loop” we only try actions that make sense:

and findisland current s = let s = keepcell current s in neighbors n emptycells current |> concatfold (fun neighbor s ->
if CellSet.mem neighbor s.visited then [s] else let chooseeat =Guard against actions that would fail. if s.moretoeat = 0 then [] else [eatcell neighbor s] and choosekeep = if s.beensize >= islandsize then [] else findisland neighbor s in chooseeat @ choosekeep) s in

Finally, we compute the required length of eaten and start searching.

let cellstoeat = List.length honey - islandsize * numislands in
findboard (initstate honey cellstoeat)

8 Constraint-based puzzles

Lecture 7: Laziness

Lazy evaluation. Stream processing.

M. Douglas McIlroy ‘‘Power Series, Power Serious’’

Oleg Kiselyov, Simon Peyton-Jones, Amr Sabry ‘‘Lazy v. Yield: Incremental, Linear Pretty-Printing’’

If you see any error on the slides, let me know!

1 Laziness

2 Evaluation strategies and parameter passing

3 Call-by-name: streams

4 Lazy values

5 Power series and differential equations

5.1 Power series / polynomial operations

5.2 Differential equations

6 Arbitrary precision computation

7 Circular data structures: double-linked list

8 Input-Output streams

8.1 Pipes

8.2 Example: pretty-printing

Functional Programming

Streams and lazy evaluation

Exercise 1: My first impulse was to define lazy list functions as here:

let rec wrong_lzip = function | LNil, LNil -> LNil | LCons (a1, lazy l1), LCons (a2, lazy l2) -> LCons ((a1, a2), lazy (wrong_lzip (l1, l2))) | -> raise (Invalidargument “lzip”)let rec wrong_lmap f = function | LNil -> LNil | LCons (a, lazy l) -> LCons (f a, lazy (wrong_lmap f l))

What is wrong with these definitions – for which edge cases they do not work as intended?

Exercise 2: Cyclic lazy lists:

  1. Implement a function *cycle : 'a list -> 'a llist* that creates a lazy list with elements from standard list, and the whole list as the tail after the last element from the input list.

    *[a1; a2; …; aN]\mapsto

    -1.407730.189096-0.9632226484984790.210262600873131-0.2012170.1890960.2644529699695730.2102626008731310.751290.1890961.068792168276230.1890957798650621.788460.1890962.190633681703930.2102626008731312.19063368170393-0.191906998280196-2.0-0.2-2.0003968778939-0.001405609207567140cm*

    Your function cycle can either return LNil or fail for an empty list as argument. 1. Note that *inv_fact* from the lecture defines the power series for the \exp (\cdot) function (\exp (x) = e^x). Using *cycle* and *inv_fact*, define the power series for \sin (\cdot) and \cos (\cdot), and draw their graphs using helper functions from the lecture script *Lec7.ml*.

    Exercise 3: * Modify one of the puzzle solving programs (either from the previous lecture or from your previous homework) to work with lazy lists. Implement the necessary higher-order lazy list functions. Check that indeed displaying only the first solution when there are multiple solutions in the result takes shorter than computing solutions by the original program.

    Exercise 4: Hamming’s problem. Generate in increasing order the numbers of the form 2^{a_{1}} 3^{a_{2}} 5^{a_{3}} \ldots p_{k}^{a_{k}}, that is numbers not divisible by prime numbers greater than the kth prime number.

    to* http://en.wikipedia.org/wiki/Regular_number.

    Starter code is available in the middle of the lecture script Lec7.ml:let rec lfilter f = function | LNil -> LNil | LCons (n, ll) -> if f n then LCons (n, lazy (lfilter f (Lazy.force ll))) else lfilter f (Lazy.force ll)let primes = let rec sieve = function LCons(p,nf) -> LCons(p, lazy (sieve (sift p (Lazy.force nf)))) | LNil -> failwith “Impossible! Internal error.” and sift p = lfilter (function n -> n mod p <> 0)in sieve (lfrom 2)let times ll n = lmap (fun i -> i n) ll;;let rec merge xs ys = match xs, ys with | LCons (x, lazy xr), LCons (y, lazy yr) -> if x < y then LCons (x, lazy (merge xr ys)) else if x > y then LCons (y, lazy (merge xs yr)) else LCons (x, lazy (merge xr yr)) | r, LNil | LNil, r -> rlet hamming k = let pr = ltake k primes in let rec h = LCons (1, lazy ( )) in h*

    Exercise 5: Modify format and/or breaks to use just a single number instead of a stack of booleans to keep track of what groups should be inlined.

    Exercise 6: Add indentation to the pretty-printer for groups: if a group does not fit in a single line, its consecutive lines are indented by a given amount tab of spaces deeper than its parent group lines would be. For comparison, let’s do several implementations.

    1. Modify the straightforward implementation of *pretty*.
    2. Modify the first pipe-based implementation of *pretty* by modifying the *format* function.
    3. Modify the second pipe-based implementation of *pretty* by modifying the *breaks* function. Recover the positions of elements – the number of characters from the beginning of the document – by keeping track of the growing offset.
    4. ** Modify a pipe-based implementation to provide a different style of indentation: indent the first line of a group, when the group starts on a new line, at the same level as the consecutive lines (rather than at the parent level of indentation).*

    Exercise 7: Write a pipe that takes document elements annotated with linear position, and produces document elements annotated with (line, column) coordinates.

    Write another pipe that takes so annotated elements and adds a line number indicator in front of each line. Do not update the column coordinate. Test the pipes by plugging them before the emit pipe.

    1: first line
    2: second line, etc.

    Exercise 8: Write a pipe that consumes document elements doc_e and yields the toplevel subdocuments doc which would generate the corresponding elements.

    You can modify the definition of documents to allow annotations, so that the element annotations are preserved (gen should ignore annotations to keep things simple):type ’a doc = Text of ’a string | Line of ’a | Cat of doc * doc | Group of ’a * doc*

    Exercise 9: * Design and implement a way to duplicate arrows outgoing from a pipe-box, that would memoize the stream, i.e. not recompute everything “upstream” for the composition of pipes. Such duplicated arrows would behave nicely with pipes reading from files.

    *
    Does not recompute g nor f. Reads once and passes all content to f and g.

    -5.769180.217059-4.245171318957530.217059134806191-3.800670.238226-2.44599153327160.746229660007938-3.821830.259393-2.4459915332716-0.2909445693874851.088870.2170593.988722053181640.7250628389998681.046530.1958923.96755523217357-0.3332782114036250cm*

    Lecture 8: Monads

    List comprehensions. Basic monads; transformers. Probabilistic Programming.Lightweight cooperative threads.

    Some examples from Tomasz Wierzbicki. Jeff Newbern ‘‘All About Monads’‘.M. Erwig, S. Kollmansberger ‘‘Probabilistic Functional Programming in Haskell’‘.Jerome Vouillon ‘‘Lwt: a Cooperative Thread Library’’.

    If you see any error on the slides, let me know!

    1 List comprehensions

    2 Generalized comprehensions aka. do-notation

    3 Monads

    3.1 Monad laws

    3.2 Monoid laws and monad-plus

    3.3 Backtracking: computation with choice

    We have seen mzero, i.e. fail in the countdown problem. What about mplus?

    let findtoeat n islandsize numislands emptycells = let honey = honeycells n emptycells in let rec findboard s = (* Printf.printf “findboard: %sn” (statestr s); ) match visitcell s with | None -> perform
    guard (s.beenislands = numislands); return s.eaten | Some (cell, s) -> perform s <– findisland cell (freshisland s);
    guard (s.beensize = islandsize); findboard s and findisland current s = let s = keepcell current s in neighbors n emptycells current
    |> foldM (fun neighbor s -> if CellSet.mem neighbor s.visited then return s else let chooseeat =
    if s.moretoeat <= 0 then fail else return (eatcell neighbor s) and choosekeep = if s.beensize >= islandsize then fail else findisland neighbor s in mplus chooseeat choosekeep) s in let cellstoeat = List.length honey - islandsize
    numislands in findboard (initstate honey cellstoeat)

    4 Monad “flavors”

    5 Interlude: the module system

    6 The two metaphors

    6.1 Monads as containers

    6.2 Monads as computation

    7 Monad classes

    8 Monad instances

    8.1 Backtracking parameterized by monad-plus

    module Countdown (M : MONADPLUSOPS) = struct open MOpen the module to make monad operations visible.

    let rec insert x = functionAll choice-introducing operations | [] -> return [x]need to happen in the monad. | y::ys as xs -> return (x::xs) ++ perform xys <– insert x ys; return (y::xys)

    let rec choices = function | [] -> return [] | x::xs -> perform cxs <– choices xs;Choosing which numbers in what order
    return cxs ++ insert x cxsand now whether with or without x.

    type op = Add | Sub | Mul | Div

    let apply op x y = match op with | Add -> x + y | Sub -> x - y | Mul -> x * y | Div -> x / y

    let valid op x y = match op with | Add -> x <= y | Sub -> x > y | Mul -> x <= y && x <> 1 && y <> 1 | Div -> x mod y = 0 && y <> 1

    type expr = Val of int | App of op * expr * expr

    let op2str = function | Add -> “+” | Sub -> “-” | Mul -> “*” | Div -> “/” let rec expr2str = functionWe will provide solutions as strings. | Val n -> stringofint n | App (op,l,r) ->“(”expr2str lop2str opexpr2str r”)”

    let combine (l,x) (r,y) o = performTry out an operator. guard (valid o x y); return (App (o,l,r), apply o x y)

    let split l =Another choice: which numbers go into which argument. let rec aux lhs = function | [] | [] -> failBoth arguments need numbers.| [y; z] -> return (List.rev (y::lhs), [z]) | hd::rhs ->
    let lhs = hd::lhs in return (List.rev lhs, rhs) ++ aux lhs rhs in aux [] l

    let rec results = functionBuild possible expressions once numbers | [] -> failhave been picked.| [n] -> perform guard (n > 0); return (Val n, n) | ns -> perform (ls, rs) <– split ns; lx <– results ls; ly <– results rs;Collect solutions using each operator. msummap (combine lx ly) [Add; Sub; Mul; Div]

    let solutions ns n = performSolve the problem: ns’ <– choices ns;pick numbers and their order, (e,m) <– results ns’;build possible expressions, guard (m=n);check if the expression gives target value, return (expr2str e)‘‘print’’ the solution.end

    8.2 Understanding laziness

    8.3 The exception monad

    module ExceptionM(Excn : sig type t end) : sig type excn = Excn.t type ’a t = OK of ’a | Bad of excn include MONADOPS val run : ’a monad -> ’a t
    val throw : excn -> ’a monad val catch : ’a monad -> (excn -> ’a monad) -> ’a monadend = struct type excn = Excn.t

    module M = struct type ’a t = OK of ’a | Bad of excn let return a = OK a let bind m b = match m with | OK a -> b a | Bad e -> Bad e end include M include MonadOps(M) let throw e = Bad e let catch m handler = match m with | OK -> m | Bad e -> handler eend

    8.4 The state monad

    module StateM(Store : sig type t end) : sig type store = Store.tPass the current store value to get the next value.type ‘a t = store -> ’a * store include MONADOPS include STATE with type ’a t := ’a monad
    and type store := store val run : ’a monad -> ’a tend = struct type store = Store.t module M = struct type ’a t = store -> ’a * store
    let return a = fun s -> a, sKeep the current value unchanged.let bind m b = fun s -> let a, s’ = m s in b a s’ endTo bind two steps, pass the value after first step to the second step. include M include MonadOps(M) let get = fun s -> s, sKeep the value unchanged but put it in monad.let put s’ = fun -> (), s’Change the value; a throwaway in monad.end

    9 Monad transformers

    9.1 State transformer

    module StateT (MP : MONADPLUSOPS) (Store : sig type t end) : sigFunctor takes two modules – the second one type store = Store.tprovides only the storage type.type ‘a t = store -> (’a * store) MP.monad include MONADPLUSOPSExporting all the monad-plus operations include STATE with type ’a t := 'a monadand state operations.and type store := store val run : ’a monad -> 'a tExpose ‘‘what happened’’ – resulting states.val runT : ’a monad -> store -> ’a MP.monadend = structRun the state transformer – get the resulting values. type store = Store.t

    module M = struct type ‘a t = store -> (’a * store) MP.monad let return a = fun s -> MP.return (a, s) let bind m b = fun s ->
    MP.bind (m s) (fun (a, s’) -> b a s’) let mzero = fun -> MP.mzeroLift the monad-plus operations.let mplus ma mb = fun s -> MP.mplus (ma s) (mb s) end include M include MonadPlusOps(M) let get = fun s -> MP.return (s, s)Instead of just returning, let put s’ = fun -> MP.return ((), s’)MP.return. let runT m s = MP.lift fst (m s)end

    9.2 Backtracking with state

    module HoneyIslands (M : MONADPLUSOPS) = struct type state = {For use with list monad or lazy list monad. beensize: int; beenislands: int;
    unvisited: cell list; visited: CellSet.t; eaten: cell list;
    moretoeat: int; } let initstate unvisited moretoeat = { beensize = 0;
    beenislands = 0; unvisited; visited = CellSet.empty; eaten = [];
    moretoeat; }

    module BacktrackingM = StateT (M) (struct type t = state end) open BacktrackingM let rec visitcell () = performState update actions. s <– get; match s.unvisited with | [] -> return None | c::remaining when CellSet.mem c s.visited -> perform put {s with unvisited=remaining}; visitcell ()Throwaway argument because of recursion. See () | c::remaining ( when c not visited *) -> perform put {s with unvisited=remaining; visited = CellSet.add c s.visited}; return (Some c)This action returns a value.

    let eatcell c = perform s <– get; put {s with eaten = c::s.eaten; visited = CellSet.add c s.visited; moretoeat = s.moretoeat - 1}; return ()Remaining state update actions just affect the state. let keepcell c = perform s <– get; put {s with
    visited = CellSet.add c s.visited; beensize = s.beensize + 1};
    return () let freshisland = perform s <– get; put {s with beensize = 0; beenislands = s.beenislands + 1}; return ()

    let findtoeat n islandsize numislands emptycells = let honey = honeycells n emptycells inOCaml does not realize that 'a monad with state is actually a function – let rec findboard () = performit’s an abstract type.(*)
    cell <– visitcell (); match cell with | None -> perform s <– get; guard (s.beenislands = numislands); return s.eaten | Some cell -> perform
    freshisland; findisland cell; s <– get;
    guard (s.beensize = islandsize); findboard ()

    and findisland current = perform        keepcell current;        neighbors 

    n emptycells current |> foldMThe partial answer sits in the state – throwaway result.(fun () neighbor -> perform s <– get; whenM (not (CellSet.mem neighbor s.visited))
    (let chooseeat = perform guard (s.moretoeat > 0); eatcell neighbor
    and choosekeep = perform guard (s.beensize < islandsize); findisland neighbor in
    chooseeat ++ choosekeep)) () in

    let cellstoeat =      List.length honey - islandsize * numislands in    

    initstate honey cellstoeat |> runT (findboard ())endmodule HoneyL = HoneyIslands (ListM)let findtoeat a b c d = ListM.run (HoneyL.findtoeat a b c d)

    10 Probabilistic Programming

    10.1 The probability monad

    10.2 Example: The Monty Hall problem

    10.4 Burglary example: encoding a Bayes net

    # let t1 = DistribMP.distrib  (BurglaryExact.check $\sim$johncalled:true 
    $\sim$marycalled:false     $\sim$radio:None);;    val t1 : 
    (BurglaryExact.whathappened * float) list =  
    [(BurglaryExact.Burglnearthq, 1.03476433660005444e-05);   
    (BurglaryExact.Earthq, 0.00452829235738691407);   
    (BurglaryExact.Burgl, 0.00511951049003530299);   
    (BurglaryExact.Safe, 0.99034184950921178)]# let t2 = DistribMP.distrib  
    (BurglaryExact.check $\sim$johncalled:true $\sim$marycalled:true     
    $\sim$radio:None);;    val t2 : (BurglaryExact.whathappened * float) list =  
    [(BurglaryExact.Burglnearthq, 0.00057437256500405794);   
    (BurglaryExact.Earthq, 0.175492465840075218);   
    (BurglaryExact.Burgl, 0.283597462799388911);   
    (BurglaryExact.Safe, 0.540335698795532)]# let t3 = DistribMP.distrib  
    (BurglaryExact.check $\sim$johncalled:true $\sim$marycalled:true     
    $\sim$radio:(Some true));;    val t3 : (BurglaryExact.whathappened * float) 
    list =  [(BurglaryExact.Burglnearthq, 0.0032622416021499262);   
    (BurglaryExact.Earthq, 0.99673775839785006)]
    
    # let t4 = Sampling2000.distrib  (BurglarySimul.check $\sim$johncalled:true 
    $\sim$marycalled:false     $\sim$radio:None);;    val t4 : 
    (BurglarySimul.whathappened * float) list =  [(BurglarySimul.Earthq, 0.0035); 
    (BurglarySimul.Burgl, 0.0035);   (BurglarySimul.Safe, 0.993)]# let t5 = 
    Sampling2000.distrib  (BurglarySimul.check $\sim$johncalled:true 
    $\sim$marycalled:true     $\sim$radio:None);;    val t5 : 
    (BurglarySimul.whathappened * float) list =  
    [(BurglarySimul.Burglnearthq, 0.0005); (BurglarySimul.Earthq, 0.1715);   
    (BurglarySimul.Burgl, 0.2875); (BurglarySimul.Safe, 0.5405)]# let t6 = 
    Sampling2000.distrib  (BurglarySimul.check $\sim$johncalled:true 
    $\sim$marycalled:true     $\sim$radio:(Some true));;    val t6 : 
    (BurglarySimul.whathappened * float) list =  
    [(BurglarySimul.Burglnearthq, 0.0015); (BurglarySimul.Earthq, 0.9985)]

    11 Lightweight cooperative threads

    module Cooperative = Threads(struct type ‘a state = | Return of 'aThe thread has returned.| Sleep of (’a -> unit) listWhen thread returns, wake up waiters.| Link of 'a tA link to the actual thread.and ’a t = {mutable state : ’a state}State of the thread can change– it can return, or more waiters can be added.let rec find t = match t.state withUnion-find style link chasing. | Link t -> find t | -> t let jobs = Queue.create ()Work queue – will storeunit -> unit procedures. let wakeup m a =Thread m has actually finished – let m = find m inupdating its state. match m.state with | Return -> assert false | Sleep waiters -> m.state <- Return a;Set the state, and only then
    List.iter ((|>) a) waiterswake up the waiters. | Link -> assert false let return a = {state = Return a}let connect t t’ =t was a placeholder for t'. let t’ = find t’ in match t’.state with | Sleep waiters’ -> let t = find t in (match t.state with | Sleep waiters ->If both sleep, collect their waiters t.state <- Sleep (waiters’ @ waiters); t’.state <- Link tand link one to the other.| -> assert false) | Return x -> wakeup t xIf t' returned, wake up the placeholder.| Link -> assert falselet rec bind a b = let a = find a in let m = {state = Sleep []} inThe resulting monad.
    (match a.state with | Return x ->If a returned, we suspend further work. let job () = connect m (b x) in(In exercise 11, this should
    Queue.push job jobsonly happen after suspend.)| Sleep waiters ->If a sleeps, we wait for it to return. let job x = connect m (b x) in
    a.state <- Sleep (job::waiters) | Link -> assert false); m
    let parallel a b c = performSince in our implementation x <– a;the threads run as soon as they are created, y <– b;parallel is redundant. c x ylet rec access m =Accessing not only gets the result of m, let m = find m inbut spins the thread loop till m terminates. match m.state with | Return x -> xNo further work.| Sleep -> (try Queue.pop jobs ()Perform suspended work. with Queue.Empty ->
    failwith “access: result not available”); access m | Link -> assert false let killthreads () = Queue.clear jobsRemove pending work.end)

    # let test =    Cooperative.killthreads ();    let thread1 = TT.loop "A" 5 in    let thread2 = TT.loop "B" 4 in    Cooperative.access thread1;    Cooperative.access thread2;;-- A(5)-- B(4)-- A(4)-- B(3)-- A(3)-- B(2)-- A(2)-- B(1)-- A(1)-- B(0)-- A(0)val test : unit = ()

    Exercise 1.

    Puzzle via Oleg Kiselyov.

    “U2” has a concert that starts in 17 minutes and they must all cross a bridge to get there. All four men begin on the same side of the bridge. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc.. Each band member walks at a different speed. A pair must walk together at the rate of the slower man’s pace:

    For example: if Bono and Larry walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If Larry then returns with the flashlight, a total of 20 minutes have passed and you have failed the mission.

    Find all answers to the puzzle using a list comprehension. The comprehension will be a bit long but recursion is not needed.

    Exercise 2.

    Assume concat_map as defined in lecture 6. What will the following expresions return? Why?

    1. perform with (|->) in return 5; return 7
    2. let guard p = if p then [()] else [];;perform with (|->) in guard false; return 7;;
    3. perform with (|->) in return 5; guard false; return 7;;

    Exercise 3.

    Define bind in terms of lift and join.

    Exercise 4.

    Define a monad-plus implementation based on binary trees, with constant-time mzero and mplus. Starter code:type ’a tree = Empty | Leaf of ’a | T of ’a t * ’a tmodule TreeM = MonadPlus (struct type ’a t = ’a tree let bind a b = TODO let return a = TODO let mzero = TODO let mplus a b = TODOend)

    Exercise 5.

    Show the monad-plus laws for one of:

    1. TreeM from your solution of exercise ;
    2. ListM from lecture.

    Exercise 6.

    Why the following monad-plus is not lazy enough?

    Exercise 7.

    Convert a “rectangular” list of lists of strings, representing a matrix with inner lists being rows, into a string, where elements are column-aligned. (Exercise not related to recent material.)

    Exercise 8.

    Recall the overly rich way to introduce monads – providing the freedom of additional parametermodule type MONAD = sig type (’s, ’a) t val return : ’a -> (’s, ’a) t val bind : (’s, ’a) t -> (’a -> (’s, ’b) t) -> (’s, ’b) tend

    Recall the operations for the exception monad:val throw : excn -> ’a monadval catch : ’a monad -> (excn -> ’a monad) -> ’a monad

    1. Design the signatures for the exception monad operations to use the enriched monads with (’s, ’a) monad type, so that they provide more flexibility than our exception monad.
    2. Does the implementation of the exception monad need to change? The same implementation can work with both sets of signatures, but the implementation given in lecture needs a very slight change. Can you find it without implementing? If not, the lecture script provides RMONAD, RMONAD_OPS, RMonadOps and RMonad, so you can implement and see for yourself – copy ExceptionM and modify:module ExceptionRM : sig type (’e, ’a) t = KEEP/TODO include RMONADOPS val run : (’e, ’a) monad -> (’e, ’a) t val throw : TODO val catch : TODOend = struct module M = struct
      type (’e, ’a) t = KEEP/TODO let return a = OK a let bind m b = KEEP/TODO end include M include RMonadOps(M) let throw e = KEEP/TODO
      let catch m handler = KEEP/TODOend

    Exercise 9.

    Implement the following constructs for all monads:

    1. for…to…
    2. for…downto…
    3. while…do…
    4. do…while…
    5. repeat…until…

    Explain how, when your implementation is instantiated with the StateM monad, we get the solution to exercise 2 from lecture 4.

    Exercise 10.

    A canonical example of a probabilistic model is that of a lawn whose grass may be wet because it rained, because the sprinkler was on, or for some other reason. Oleg Kiselyov builds on this example with variables rain, sprinkler, and wet_grass, by adding variables cloudy and wet_roof. The probability tables are:

    \begin{eqnarray*} P (\operatorname{cloudy}) & = & 0.5 \\\\\\ P (\operatorname{rain}|\operatorname{cloudy}) & = & 0.8 \\\\\\ P (\operatorname{rain}|\operatorname{not}\operatorname{cloudy}) & = & 0.2 \\\\\\ P (\operatorname{sprinkler}|\operatorname{cloudy}) & = & 0.1 \\\\\\ P (\operatorname{sprinkler}|\operatorname{not}\operatorname{cloudy}) & = & \0.5 \\\\\\ P (\operatorname{wet}\operatorname{roof}|\operatorname{not}\operatorname{rain}) & = & 0 \\\\\\ P (\operatorname{wet}\operatorname{roof}|\operatorname{rain}) & = & 0.7 \\\\\\ P (\operatorname{wet}\operatorname{grass}|\operatorname{rain} \wedge \operatorname{not}\operatorname{sprinkler}) & = & 0.9 \\\\\\ P (\operatorname{wet}\operatorname{grass}|\operatorname{sprinkler} \wedge \operatorname{not}\operatorname{rain}) & = & 0.9 \end{eqnarray*}

    We observe whether the grass is wet and whether the roof is wet. What is the probability that it rained?

    Exercise 11.

    Implement the coarse-grained concurrency model.

    Lecture 9: Compiler

    Compilation. Runtime. Optimization. Parsing.

    Andrew W. Appel ‘‘Modern Compiler Implementation in ML’‘E. Chailloux, P. Manoury, B. Pagano ‘‘Developing Applications with OCaml’‘Jon D. Harrop ‘‘OCaml for Scientists’’Francois Pottier, Yann Regis-Gianas ‘‘Menhir Reference Manual’’

    If you see any error on the slides, let me know!

    1 OCaml Compilers

    1.1 Compiling multiple-file projects

    PROG := prog
    LIBS := unix
    SOURCES := sub1.ml sub2.ml main.ml
    INTERFACES := $(wildcard *.mli)
    OBJS := $(patsubst %.ml,%.cmx,$(SOURCES))
    LIBS := $(patsubst %,%.cmxa,$(LIBS))
    $(PROG): $(OBJS)
    ocamlopt -o $@ $(LIBS) $(OBJS)
    clean: rm -rf $(PROG) *.o *.cmx *.cmi *~
    %.cmx: %.ml
    ocamlopt -c $*.ml
    %.cmi: %.mli
    ocamlopt -c $*.mli
    depend: $(SOURCES) $(INTERFACES)
    ocamldep -native $(SOURCES) $(INTERFACES)

    1.2 Editors

    2 Imperative features in OCaml

    OCaml is not a purely functional language, it has built-in:

    Using global state e.g. reference cells makes code non re-entrant: finish one task before starting another – any form of concurrency is excluded.

    2.1 Parsing command-line arguments

    To go beyond Sys.argv array, see Arg module:http://caml.inria.fr/pub/docs/manual-ocaml/libref/Arg.html

    type config = { Example: configuring a Mine Sweeper game. nbcols : int ; nbrows : int ; nbmines : int }let defaultconfig = { nbcols=10; nbrows=10; nbmines=15 }let setnbcols cf n = cf := {!cf with nbcols = n}let setnbrows cf n = cf := {!cf with nbrows = n}let setnbmines cf n = cf := {!cf with nbmines = n}let readargs() = let cf = ref defaultconfig inState of configuration let speclist = will be updated by given functions. [(“-col”, Arg.Int (setnbcols cf), “number of columns”); (“-lin”, Arg.Int (setnbrows cf), “number of lines”); (“-min”, Arg.Int (setnbmines cf), “number of mines”)] in let usagemsg = “usage : minesweep [-col n] [-lin n] [-min n]” in Arg.parse speclist (fun s -> ()) usagemsg; !cf

    3 OCaml Garbage Collection

    3.1 Representation of values

    3.2 Generational Garbage Collection

    3.3 Stop & Copy GC

    3.4 Mark & Sweep GC

    4 Stack Frames and Closures

    4.1 Tail Recursion

    4.2 Generated assembly

    5 Profiling and Optimization

    5.1 Profiling

    let readwords file =Imperative programming example. let input = openin file in let words = ref [] and more = ref true in tryLecture 6 read_lines function would stack-overflow while !more dobecause of the try-with clause. Scanf.fscanf input “%[a-zA-Z0-9’]%[a-zA-Z0-9’]” (fun b x -> words := x :: !words; more := x <> ““) done; List.rev (List.tl !words) with Endoffile -> List.rev !wordslet empty () = []let increment h w =Inefficient map update. try let c = List.assoc w h in (w, c+1) :: List.removeassoc w h with Notfound -> (w, 1)::hlet iterate f h =
    List.iter (fun (k,v)->f k v) hlet histogram words = List.foldleft increment (empty ()) wordslet = let words = readwords”./shakespeare.xml” in let words = List.revmap String.lowercase words in let h = histogram words in let output = openout “histogram.txt” in iterate (Printf.fprintf output “%s: %dn”) h; closeout output

      %   cumulative   self              self     total
     time   seconds   seconds    calls   s/call   s/call  name
     37.88      8.54     8.54 306656698    0.00     0.00  compare_val
     19.97     13.04     4.50   273169     0.00     0.00  camlList__assoc_1169
      9.17     15.10     2.07 633527269    0.00     0.00  caml_page_table_lookup
      8.72     17.07     1.97   260756    0.00  0.00 camlList__remove_assoc_1189
      7.10     18.67     1.60 612779467    0.00     0.00  caml_string_length
      4.97     19.79     1.12 306656692     0.00    0.00  caml_compare
      2.84     20.43     0.64                             caml_c_call
      1.53     20.77     0.35    14417     0.00     0.00  caml_page_table_modify
      1.07     21.01     0.24     1115     0.00     0.00  sweep_slice
      0.89     21.21     0.20      484     0.00     0.00  mark_slice
    index % time    self  children    called     name
    -----------------------------------------------
                    0.00    6.47  273169/273169  camlList__fold_left_1078 [7]
    [8]     28.7    0.00    6.47  273169         camlOptim0__increment_1038 [8]
                    4.50    0.00  273169/273169  camlList__assoc_1169 [9]
                   1.97    0.00  260756/260756  camlList__remove_assoc_1189 [11]
    -----------------------------------------------
                    1.12   12.13 306656692/306656692     caml_c_call [1]
    [2]     58.8    1.12   12.13 306656692         caml_compare [2]
                    8.54    3.60 306656692/306656698     compare_val [3]

    5.2 Algorithmic optimizations

    5.3 Low-level optimizations

    5.4 Comparison of data structure implementations

    create:
    assoc list 0.25 0.25 0.18 0.19 0.17 0.22 0.19 0.19 0.19
    tree map 0.48 0.81 0.82 1.2 1.6 2.3 2.7 3.6 4.1 5.1
    hashtable 27 9.1 5.5 4 2.9 2.4 2.1 1.9 1.8 3.7
    create:
    tree map 6.5 8 9.8 15 19 26 34 41 51 67 80 130
    hashtable 4.8 5.6 6.4 8.4 12 15 19 20 22 24 23 33
    found:
    assoc list 1.1 1.5 2.5 4.2 8.1 17 30 60 120
    tree map 1 1.1 1.3 1.5 1.9 2.1 2.5 2.8 3.1 3.6
    hashtable 1.4 1.5 1.4 1.4 1.5 1.5 1.6 1.6 1.8 1.8
    found:
    tree map 4.3 5.2 6 7.6 9.4 12 15 17 19 24 28 32
    hashtable 1.8 2 2.5 3.1 4 5.1 5.9 6.4 6.8 7.6 6.7 7.5
    not found:
    assoc list 1.8 2.6 4.6 8 16 32 60 120 240
    tree map 1.5 1.5 1.8 2.1 2.4 2.7 3 3.2 3.5 3.8
    hashtable 1.4 1.4 1.5 1.5 1.6 1.5 1.7 1.9 2 2.1
    not found:
    tree map 4.2 4.3 4.7 4.9 5.3 5.5 6.1 6.3 6.6 7.2 7.5 7.3
    hashtable 1.8 1.9 2 1.9 1.9 1.9 2 2 2.2 2 2 1.9

    6 Parsing: ocamllex and Menhir

    6.1 Lexing with ocamllex

    6.1.1 Example: Finding email addresses

    {The header with OCaml code. open LexingMake accessing Lexing easier. let nextline lexbuf =Typical lexer function: move position to next line. let pos = lexbuf.lexcurrp in lexbuf.lexcurrp <- { pos with poslnum = pos.poslnum + 1; posbol = pos.poscnum; } type state =Which step of searching for address we’re at: | SeekSeek: still seeking, Addr (true…): possibly finished, | Addr of bool * string * string listAddr (false…): no domain.

    let report state lexbuf =Report the found address, if any. match state with | Seek -> () | Addr (false, , ) -> () | Addr (true, name, addr) ->With line at which it is found. Printf.printf “%d: %s@%sn” lexbuf.lexcurrp.poslnum name (String.concat “.” (List.rev addr))}let newline = (‘’ | “”)Regexp for end of line.let addrchar = [‘a’-‘z’‘A’-‘Z’‘0’-‘9’‘-’’’]let atwsymb = “where” | “WHERE” | “at” | “At” | “AT”let atnwsymb = ‘@’ | “@” | “@”let opensymb = ’ ‘*’(’ ’ ‘* |’ ‘+Demarcate a possible @let closesymb =’ ‘*’)’’ ‘* |’ ’+or . symbol.let atsepsymb = opensymb? atnwsymb closesymb? | opensymb atwsymb closesymb

    let dotwsymb = “dot” | “DOT” | “dt” | “DT”let domwsymb = dotwsymb | “dom” | “DOM”Obfuscation for last dot.let dotsepsymb = opensymb dotwsymb closesymb |
    opensymb? ‘.’ closesymb?let domsepsymb = opensymb domwsymb closesymb |
    opensymb? ‘.’ closesymb?let addrdom = addrchar addrcharRestricted form of last part| “edu” | “EDU” | “org” | “ORG” | “com” | “COM”of address.rule email state = parse| newlineCheck state before moving on.{ report state lexbuf; nextline lexbuf; email Seek lexbuf }\swarrowDetected possible start of address.| (addrchar+ as name) atsepsymb (addrchar+ as addr) { email (Addr (false, name, [addr])) lexbuf }

    domsepsymb (addrdom as dom)Detected possible finish of address. { let

    state = match state with | Seek -> SeekWe weren’t looking at an address. | Addr (, name, addrs) ->Bingo. Addr (true, name, dom::addrs) in email state lexbuf }| dotsepsymb (addrchar+ as addr)Next part of address – { let state =must be continued. match state with | Seek -> Seek | Addr (, name, addrs) ->
    Addr (false, name, addr::addrs) in email state lexbuf }| eofEnd of file – end loop.{ report state lexbuf }|Some boring character – not looking at an address yet.{ report state lexbuf; email Seek lexbuf }{The trailer with OCaml code. let =Open a file and start mining for email addresses. let ch = openin Sys.argv.(1) in email Seek (Lexing.fromchannel ch); closein chClose the file at the end.}

    6.2 Parsing with Menhir

    6.2.1 Example: parsing arithmetic expressions

    6.2.2 Example: a toy sentence grammar

    { type sentence = {Could be in any module visible to EngParser. subject : string;The actor/actors, i.e. subject noun. action : string;The action, i.e.  verb. plural : bool;Whether one or multiple actors. adjs : string list;Characteristics of actor. advs : string listCharacteristics of action. }

    type token = | VERB of string | NOUN of string | ADJ of string | ADV of string | PLURAL | SINGULAR | ADET | THEDET | SOMEDET | THISDET | THATDET | THESEDET | THOSEDET | COMMACNJ | ANDCNJ | DOTPUNCT let tokstr = function …Print the token. let adjectives =Recognized adjectives. [“smart”; “extreme”; “green”; “slow”; “old”; “incredible”; “quiet”; “diligent”; “mellow”; “new”] let logfile = openout “log.txt”File with debugging information.let log s = Printf.fprintf logfile “%sn%!” s let lasttok = ref DOTPUNCTState for better tagging.

    let tokbuf = Queue.create ()Token buffer, since single word let push w =is sometimes two tokens. log (“lex:”tokstr w);Log lexed token. lasttok := w; Queue.push w tokbuf exception LexError of string}let alphanum = [‘0’-‘9’ ‘a’-‘z’ ‘A’-‘Z’ ’’’ ‘-’]rule line = parseFor line-based interface.| ([‘’]* ‘’) as l { l }| eof { exit 0 }and lexword = parse| [’ ’ ’]Skip whitespace. { lexword lexbuf }| ‘.’ { push DOTPUNCT }End of sentence.| “a” { push ADET } | “the” { push THEDET }‘‘Keywords’‘.| “some” { push SOMEDET }| “this” { push THISDET } | “that” { push THATDET }| “these” { push THESEDET } | “those” { push THOSEDET }| “A” { push ADET } | “The” { push THEDET }| “Some” { push SOMEDET }| “This” { push THISDET } | “That” { push THATDET }| “These” { push THESEDET } | “Those” { push THOSEDET }| “and” { push ANDCNJ }|’,’ { push COMMACNJ }| (alphanum+ as w) “ly”Adverb is adjective that ends in ‘‘ly’’.{
    if List.mem w adjectives then push (ADV w) else if List.mem (w”le”) adjectives then push (ADV (w”le”)) else (push (NOUN w); push SINGULAR) }

    (alphanum+ as w) “s”Plural noun or singular verb.{ if List.mem w

    adjectives then push (ADJ w) else match !lasttok with | THEDET | SOMEDET | THESEDET | THOSEDET | DOTPUNCT | ADJ -> push (NOUN w); push PLURAL | -> push (VERB w); push SINGULAR }| alphanum+ as wNoun contexts vs. verb contexts.{ if List.mem w adjectives then push (ADJ w) else match !lasttok with | ADET | THEDET | SOMEDET | THISDET | THATDET | DOTPUNCT | ADJ -> push (NOUN w); push SINGULAR
    | -> push (VERB w); push PLURAL }

     as w { raise (LexError (“Unrecognized character”

    Char.escaped w)) }{ let lexeme lexbuf =The proper interface reads from the token buffer. if Queue.isempty tokbuf then lexword lexbuf; Queue.pop tokbuf}

    %{ open EngLexerSource of the token type and sentence type.%}%token VERB NOUN ADJ ADVOpen word classes.%token PLURAL SINGULARNumber marker.%token ADET THEDET SOMEDET THISDET THATDET‘‘Keywords’’.%token THESEDET THOSEDET%token COMMACNJ ANDCNJ DOTPUNCT%start <EngLexer.sentence> sentenceGrammar entry.%%

    %public %inline sep2list(sep1, sep2, X):General purpose.| xs = separatednonemptylist(sep1, X) sep2 x=X { xs @ [x] }We use it for ‘‘comma-and’’ lists:| x=option(X)smart, quiet and diligent. { match x with None->[] | Some x->[x] }singonlydet:How determiners relate to number.| ADET | THISDET | THATDET { log “prs: singonlydet” }pluonlydet:| THESEDET | THOSEDET { log “prs: pluonlydet” }otherdet:| THEDET | SOMEDET { log “prs: otherdet” }np(det):| det adjs=list(ADJ) subject=NOUN { log “prs: np”; adjs, subject }vp(NUM):| advs=separatedlist(ANDCNJ,ADV) action=VERB NUM| action=VERB NUM advs=sep2list(COMMACNJ,ANDCNJ,ADV) { log “prs: vp”; action, advs }

    sent(det,NUM):Sentence parameterized by number.| adjsub=np(det) NUM vbadv=vp(NUM) { log “prs: sent”; {subject=snd adjsub; action=fst vbadv; plural=false; adjs=fst adjsub; advs=snd vbadv} }vbsent(NUM):Unfortunately, it doesn’t always work…| NUM vbadv=vp(NUM)
    { log “prs: vbsent”; vbadv }sentence:Sentence, either singular or plural number.| s=sent(singonlydet,SINGULAR) DOTPUNCT { log “prs: sentence1”;
    {s with plural = false} }| s=sent(pluonlydet,PLURAL) DOTPUNCT { log “prs: sentence2”; {s with plural = true} }

    adjsub=np(otherdet) vbadv=vbsent(SINGULAR) DOTPUNCT { log “prs:

    sentence3”;Because parser allows only one token look-ahead {subject=snd adjsub; action=fst vbadv; plural=false; adjs=fst adjsub; advs=snd vbadv} }| adjsub=np(otherdet) vbadv=vbsent(PLURAL) DOTPUNCT { log “prs: sentence4”;we need to factor-out the ‘‘common subset’’. {subject=snd adjsub; action=fst vbadv; plural=true; adjs=fst adjsub; advs=snd vbadv} }

    open EngLexerlet () = let stdinbuf = Lexing.fromchannel stdin in while true do (* Read line by line. *) let linebuf = Lexing.fromstring (line stdinbuf) in

    try      (* Run the parser on a single line of input. *)      let s = 

    EngParser.sentence lexeme linebuf in Printf.printf
    “subject=%s=%b=%s=%snadvs=%s%!” s.subject s.plural (String.concat “,” s.adjs) s.action (String.concat “,” s.advs) with | LexError msg -> Printf.fprintf stderr “%sn%!” msg | EngParser.Error -> Printf.fprintf stderr “At offset %d: syntax error.n%!” (Lexing.lexemestart linebuf) done

    { open IndexParser let word = ref 0 let linebreaks = ref [] let commentstart = ref Lexing.dummypos let resetasfile lexbuf s =General purpose lexer function: let pos = lexbuf.Lexing.lexcurrp instart lexing from a file. lexbuf.Lexing.lexcurrp <- { pos with Lexing.poslnum = 1;
    posfname = s; posbol = pos.Lexing.poscnum; }; linebreaks := []; word := 0 let nextline lexbuf =Old friend. …Besides changing position, remember a line break. linebreaks := !word :: !linebreaks

    let parseerrormsg startpos endpos report =General purpose lexer function:
    let clbeg =report a syntax error. startpos.Lexing.poscnum - startpos.Lexing.posbol in ignore (Format.flushstrformatter ());
    Printf.sprintf “File”%s”, lines %d-%d, characters %d-%d: %sn”
    startpos.Lexing.posfname startpos.Lexing.poslnum endpos.Lexing.poslnum clbeg (clbeg+(endpos.Lexing.poscnum - startpos.Lexing.poscnum))
    report}let alphanum = [‘0’-‘9’ ‘a’-‘z’ ‘A’-‘Z’]let newline = (‘n’ | “rn”)let xmlstart = (“” | “?>”)rule token = parse | [’ ’ ‘t’] { token lexbuf } | newline { nextline lexbuf; token lexbuf }

    | ‘<’ alphanum+ ‘>’ as wDedicated token variants for XML tags.{ OPEN w } | “</” alphanum+ ‘>’ as w { CLOSE w } | “’tis” { word := !word+2; WORDS [“it”, !word-1; “is”, !word] } | “‘Tis” { word := !word+2; WORDS [“It”, !word-1; “is”, !word] } | “o’clock” { incr word; WORDS [“o’clock”, !word] } | “O’clock” { incr word; WORDS [“O’clock”, !word] } | (alphanum+ as w1)’’’ (alphanum+ as w2) { let words = EngMorph.abridged w1 w2 in let words = List.map (fun w -> incr word; w, !word) words in WORDS words } | alphanum+ as w { incr word; WORDS [w, !word] } |”&” { incr word; WORDS [“&”, !word] }

    | [‘.’ ‘!’ ‘?’] as pDedicated tokens for punctuation { SENTENCE (Char.escaped p) }so that it doesn’t break phrases. | “–” { PUNCT “–” } | [‘,’ ‘:’ ’’’ ‘-’ ‘;’] as p { PUNCT (Char.escaped p) } | eof { EOF } | xmlstart { commentstart := lexbuf.Lexing.lexcurrp; let s = comment [] lexbuf in COMMENT s } | { let pos = lexbuf.Lexing.lexcurrp in let pos’ = {pos with Lexing.poscnum = pos.Lexing.poscnum + 1} in Printf.printf “%s%!”
    (parseerrormsg pos pos’ “lexer error”); failwith “LEXER ERROR” }

    and comment strings = parse | xmlend { String.concat “” (List.rev strings) } | eof { let pos = !commentstart in let pos’ = lexbuf.Lexing.lexcurrp in Printf.printf “%sn%!” (parseerrormsg pos pos’ “lexer error: unclosed comment”); failwith “LEXER ERROR” } | newline { nextline lexbuf; comment (Lexing.lexeme lexbuf :: strings) lexbuf } | { comment (Lexing.lexeme lexbuf :: strings) lexbuf }

    type token =| WORDS of (string * int) list| OPEN of string | CLOSE of string | COMMENT of string| SENTENCE of string | PUNCT of string| EOF

    let invindex update ii lexer lexbuf = let rec aux ii = match lexer lexbuf with | WORDS ws -> let ws = List.map (fun (w,p)->EngMorph.normalize w, p) ws in aux (List.foldleft update ii ws) | OPEN | CLOSE | SENTENCE | PUNCT | COMMENT -> aux ii
    | EOF -> ii in aux ii

    let phrase lexer lexbuf = let rec aux words = match lexer lexbuf with | WORDS ws -> let ws = List.map (fun (w,p)->EngMorph.normalize w) ws in aux (List.revappend ws words) | OPEN | CLOSE | SENTENCE | PUNCT | COMMENT -> aux words | EOF -> List.rev words in aux []

    let update ii (w, p) = try let ps = List.assoc w ii inAdd position to the postings list of w. (w, p::ps) :: List.removeassoc w ii with Notfound -> (w, [p])::iilet empty = []let find w ii = List.assoc w iilet mapv f ii = List.map (fun (k,v)->k, f v) iilet index file = let ch = openin file in let lexbuf = Lexing.fromchannel ch in EngLexer.resetasfile lexbuf file; let ii = IndexParser.invindex update empty EngLexer.token lexbuf in closein ch;Keep postings lists in increasing order. mapv List.rev ii, List.rev !EngLexer.linebreakslet findline linebreaks p =Recover the line in document of a position. let rec aux line = function | [] -> line
    | bp:: when p < bp -> line | ::breaks -> aux (line+1) breaks in aux 1 linebreakslet search (ii, linebreaks) phrase = let lexbuf = Lexing.fromstring phrase in EngLexer.resetasfile lexbuf (“search phrase:”phrase); let phrase = IndexParser.phrase EngLexer.token lexbuf in let rec aux wpos = functionMerge postings lists for words in query: | [] -> wposno more words in query;| w::ws ->for positions of w, keep those that are next to let nwpos = find w ii infiltered positions of previous word. aux (List.filter (fun p->List.mem (p-1) wpos) nwpos) ws in let wpos = match phrase with | [] -> []No results for an empty query.
    | w::ws -> aux (find w ii) ws in List.map (findline linebreaks) wposAnswer in terms of document lines.

    let shakespeare = index “./shakespeare.xml”let query q = let lines = search shakespeare q in Printf.printf “%s: lines %sn%!” q (String.concat “,” (List.map stringofint lines))

    2 Replace association list with hash table

    3 Replace naive merging with ordered merging

    4 Bruteforce optimization: biword indexes

    7.1 Smart way: Information Retrieval G.V. Cormack et al.

    7.1.1 The phrase search algorithm

    let rec nextphrase ii phrase cp =Return the beginning and end position let rec aux cp = functionof occurrence of phrase after position cp. | [] -> raise NotfoundEmpty phrase counts as not occurring. | [w] ->Single or last word of phrase has the same let np = next ii w cp in np, npbeg. and end position.| w::ws ->After locating the endp. move back. let np, fp = aux (next ii w cp) ws in prev ii w np, fp inIf distance is this small, let np, fp = aux cp phrase inwords are consecutive. if fp - np = List.length phrase - 1 then np, fp else nextphrase ii phrase fp

    let search (ii, linebreaks) phrase = let lexbuf = Lexing.fromstring phrase in EngLexer.resetasfile lexbuf (“search phrase:”phrase); let phrase = IndexParser.phrase EngLexer.token lexbuf in let rec aux cp = tryFind all occurrences of the phrase. let np, fp = nextphrase ii phrase cp in
    np :: aux fp with Notfound -> [] inMoved past last occurrence.
    List.map (findline linebreaks) (aux (-1))

    7.1.2 Naive but purely functional inverted index

    module S = Set.Make(struct type t=int let compare i j = i-j end)let update ii (w, p) = (try let ps = Hashtbl.find ii w in Hashtbl.replace ii w (S.add p ps) with Notfound -> Hashtbl.add ii w (S.singleton p)); iilet first ii w = S.minelt (find w ii)The functions raise Not_foundlet last ii w = S.maxelt (find w ii)whenever such position would not exist.let prev ii w cp = let ps = find w ii inSplit the set into elements let smaller, , = S.split cp ps insmaller and bigger than cp. S.maxelt smallerlet next ii w cp = let ps = find w ii in let , , bigger = S.split cp ps in S.minelt bigger

    7.1.3 Binary search based inverted index

    let prev ii w cp = let ps = find w ii in let rec aux b e =We implement binary search separately for prev if e-b <= 1 then ps.(b)to make sure here we return less than cp else let m = (b+e)/2 in if ps.(m) < cp then aux m eelse aux b m in let l = Array.length ps in if l = 0 || ps.(0) >= cp then raise Notfound else aux 0 (l-1)let next ii w cp = let ps = find w ii in let rec aux b e = if e-b <= 1 then ps.(e)and here more than cp. else let m = (b+e)/2 in if ps.(m) <= cp then aux m e else aux b m in let l = Array.length ps in if l = 0 || ps.(l-1) <= cp then raise Notfound else aux 0 (l-1)

    7.1.4 Imperative, linear scan

    let prev ii w cp = let cw,ps = find w ii inFor each word we add a cell with last visited occurrence. let l = Array.length ps in if l = 0 || ps.(0) >= cp then raise Notfound else if ps.(l-1) < cp then cw := l-1 else (Reset pointer if current position is not ‘‘ahead’’ of it. if !cw < l-1 && ps.(!cw+1) < cp then cw := l-1;Otherwise scan while ps.(!cw) >= cp do decr cw donestarting from last visited. ); ps.(!cw)let next ii w cp = let cw,ps = find w ii in let l = Array.length ps in if l = 0 || ps.(l-1) <= cp then raise Notfound else if ps.(0) > cp then cw := 0 else (Reset pointer if current position is not ahead of it. if !cw > 0 && ps.(!cw-1) > cp then cw := 0; while ps.(!cw) <= cp do incr cw done ); ps.(!cw)

    let next ii w cp = let cw,ps = find w ii in let l = Array.length ps in if l = 0 || ps.(l-1) <= cp then raise Notfound; let rec jump (b,e as bounds) j =Locate the interval with cp inside. if e < l-1 && ps.(e) <= cp then jump (e,e+j) (2*j) else bounds in let rec binse b e =Binary search over that interval. if e-b <= 1 then e else let m = (b+e)/2 in if ps.(m) <= cp then binse m e else binse b m in if ps.(0) > cp then cw := 0 else ( let b =The invariant is that ps.(b) <= cp. if !cw > 0 && ps.(!cw-1) <= cp then !cw-1 else 0 in let b,e = jump (b,b+1) 2 inLocate interval starting near !cw. let e = if e > l-1 then l-1 else e in cw := binse b e ); ps.(!cw)

    Exercise 1.

    (Exercise 6.1 from “Modern Compiler Implementation in ML” by Andrew W. Appel.) Using the ocamlopt compiler with parameter -S and other parameters turning on all possible compiler optimizations, evaluate the compiled programs by these criteria:

    1. Are local variables kept in registers? Show on an example.
    2. If local variable b is live across more than one procedure call, is it kept in a callee-save register? Explain how it would speed up the program:let f a = let b = a+1 in let c = g () in let d = h c in b+c
    3. If local variable x is never live across a procedure call, is it properly kept in a caller-save register? Explain how doing thes would speed up the program:let h y = let x = y+1 in let z = f y in f z

    Exercise 2.

    As above, verify whether escaping variables of a function are kept in a closure corresponding to the function, or in closures corresponding to the local, i.e. nested, functions that are returned from the function (or assigned to a mutable field).

    Exercise 3.

    As above, verify that OCaml compiler performs inline expansion of small functions. Check whether the compiler can inline, or specialize (produce a local function to help inlining), recursive functions.

    Exercise 4.

    Write a “.mll program” that anonymizes, or masks, text. That is, it replaces identified probable full names (of persons, companies etc.) with fresh shorthands Mr. A, Ms. B, or Mr./Ms. C when the gender cannot be easily determined. The same (full) name should be replaced with the same letter.

    Exercise 5.

    In the lexer EngLexer we call function abridged from the module EngMorph. Inline the operation of abridged into the lexer by adding a new regular expression pattern for each if clause. Assess the speedup on the Shakespeare corpus and the readability and either keep the change or revert it.

    Exercise 6.

    Make the lexer re-entrant for the second Menhir example (toy English grammar parser).

    Exercise 7.

    Make the determiner optional in the toy English grammar.

    1. * Can you come up with a factorization that would avoid having two more productions in total?

    Exercise 8.

    Integrate into the Phrase search example, the Porter Stemmer whose source is in the stemmer.ml file.

    Exercise 9.

    Revisit the search engine example from lecture 6.

    1. Perform optimization of data structure, i.e. replace association lists with hash tables.
    2. Optimize the algorithm: perform query optimization. Measure time gains for selected queries.
    3. For bonus points, as time and interest permits, extend the query language with OR and NOT connectives, in addition to AND.
    4. * Extend query optimization to the query language with AND, OR and NOT connectives.

    Exercise 10.

    Write an XML parser tailored to the shakespeare.xml corpus provided with the phrase search example. Modify the phrase search engine to provide detailed information for each found location, e.g. which play and who speaks the phrase.

    Lecture 10: FRP

    Zippers. Functional Reactive Programming. GUIs.

    *‘‘Zipper’‘* in Haskell Wikibook and ‘‘The Zipper’’ by Gerard Huet ‘‘How froc works’’ by Jacob Donham ‘‘The Haskell School of Expression’’ by Paul Hudak ‘‘Deprecating the Observer Pattern with Scala.React’’ by Ingo Maier, Martin Odersky

    If you see any error on the slides, let me know!

    1 Zippers

    type btree = Tip | Node of int * btree * btree

    \begin{matrix} T & = & 1 + xT^2\\\\\\ \frac{\partial T}{\partial x} & = & 0 + T^2 + 2 xT \frac{\partial T}{\partial x} = TT + 2 xT \frac{\partial T}{\partial x} \end{matrix}

    type btree_dir = LeftBranch | RightBranch
    type btree_deriv =
      | Here of btree * btree
      | Below of btree_dir * int * btree * btree_deriv

    type doc = Text of string | Line | Group of doc listtype context = (doc list * doc list) listtype location = {sub: doc; ctx: context}

    let goup loc = match loc.ctx with | [] -> invalidarg “goup: at top” | (left, right) :: upctx ->Previous subdocument and its siblings.
    {sub=Group (List.rev left @ loc.sub::right); ctx=upctx}let goleft loc = match loc.ctx with | [] -> invalidarg “goleft: at top” | (l::left, right) :: upctx ->Left sibling of previous subdocument. {sub=l; ctx=(left, loc.sub::right) :: upctx} | ([], ) :: -> invalidarg “goleft: at first”

    let goright loc = match loc.ctx with | [] -> invalidarg “goright: at top” | (left, r::right) :: upctx -> {sub=r; ctx=(loc.sub::left, right) :: upctx} | (, []) :: -> invalidarg “goright: at last”let godown loc =Go to the first (i.e. leftmost) subdocument. match loc.sub with | Text -> invalidarg “godown: at text” | Line -> invalidarg “godown: at line” | Group [] -> invalidarg “godown: at empty” | Group (doc::docs) -> {sub=doc; ctx=([], docs)::loc.ctx}

    1.1 Example: Context rewriting

    type op = Add | Multype expr = Val of int | Var of string | App of expropexprtype exprdir = Leftarg | Rightargtype context = (exprdir * op * expr) listtype location = {sub: expr; ctx: context}

    let rec findaux p e = if p e then Some (e, []) else match e with | Val | Var -> None | App (l, op, r) -> match findaux p l with | Some (sub, upctx) -> Some (sub, (Rightarg, op, r)::upctx) | None -> match findaux p r with | Some (sub, upctx) -> Some (sub, (Leftarg, op, l)::upctx) | None -> None

    let find p e = match findaux p e with | None -> None | Some (sub, ctx) -> Some {sub; ctx=List.rev ctx}

    let rec pullout loc = match loc.ctx with | [] -> locDone.| (Leftarg, op, l) :: upctx ->D [e \circ C [x]] \Rightarrow D [C [x] \circ e] pullout {loc with ctx=(Rightarg, op, l) :: upctx} | (Rightarg, op1, e1) :: (, op2, e2) :: upctx when op1 = op2 ->D [(C [x] \circ e_{1}) \circ e_{2}] / D [e_{2} \circ (C [x] \circ e_{1})] \Rightarrow D [C [x] \circ (e_{1} \circ e_{2})] pullout {loc with ctx=(Rightarg, op1, App(e1,op1,e2)) :: upctx} | (Rightarg, Add, e1) :: (, Mul, e2) :: upctx -> pullout {loc with ctx=D [(C [x] + e_{1}) e_{2}] / D [e_{2} (C [x] + e_{1})] \Rightarrow D [C [x] e_{2} + e_{1} e_{2}] (Rightarg, Mul, e2) :: (Rightarg, Add, App(e1,Mul,e2)) :: upctx} | (Rightarg, op, r)::upctx ->Move up the context. pullout {sub=App(loc.sub, op, r); ctx=upctx}

    2 Adaptive Programming aka.Incremental Computing

    1 Dependency Graphs (explained by Jake Dunham)

    2.1 Example using Froc

    3 Functional Reactive Programming

    4 Reactivity by Stream Processing

    1 The Paddle Game example

    let pbal vel = let rec xvel uts = stepaccum vel (xbounce ->> (\sim-.)) $ uts and xvel = {memof = xvel; memor = None} and xpos uts = (liftB intoffloat (integral xvel) +* width /* !2) $ uts and xpos = {memof = xpos; memor = None} and xbounce uts = whenB ((xpos > width -* !27) || (xpos <* !27)) $ uts and xbounce = {memof = xbounce; memor = None} in let rec yvel uts = (stepaccum vel (ybounce ->> (\sim-.))) $ uts and yvel = {memof = yvel; memor = None} and ypos uts = (liftB intoffloat (integral yvel) + height /* !2) $ uts and ypos = {memof = ypos; memor = None} and ybounce uts = whenB ( (ypos > height -* !27) || ((ypos <* !17) && (ypos >* !7) && (xpos >* mousex) &&* (xpos <* mousex +* !*50))) $ uts and ybounce = {memof = ybounce; memor = None} in liftB2 (fun x y -> Color (Graphics.red, Circle (x, y, 6))) xpos ypos

    5 Reactivity by Incremental Computing

    1 Reimplementing the Paddle Game example

    6 Direct Control

    1 Flows and state

    Global state and thread-local state can be used with lightweight threads, but pay attention to semantics – which computations are inside the monad and which while building the initial monadic value.

    let f = repeat (perform emit (Printf.printf “[0]%!”; ‘0’); () <– await aas; emit (Printf.printf “[1]%!”; ‘1’); () <– await bs; emit (Printf.printf “[2]%!”; ‘2’); () <– await cs; emit (Printf.printf “[3]%!”; ‘3’); () <– await ds; emit (Printf.printf “[4]%!”; ‘4’))let e, cancele = eventflow flet () = F.notifye e (fun c -> Printf.printf “flow: %c%!” c); Printf.printf “notification installed%!”let () = F.send a (); F.send b (); F.send c (); F.send d (); F.send a (); F.send b (); F.send c (); F.send d ()

    [0]Only printed once – when building the loop.notification installedOnly installed after the first flow event sent.event: aEvent notification (see source Lec10e.ml).[1]Second emit computed after first await returns.flow: 1Emitted signal.event: bNext event…[2]flow: 2event: c[3]flow: 3event: d[4]flow: 4Last signal emitted from first turn of the loop –flow: 0and first signal of the second turn (but [0] not printed).event: a[1]flow: 1event: b[2]flow: 2event: c[3]flow: 3event: d[4]flow: 4flow: 0Program ends while flow in third turn of the loop.

    7 Graphical User Interfaces

    7.1 Calculator Flow

    let digits, digit = F.makeevent ()We represent the mechanicslet ops, op = F.makeevent ()of the calculator directly as a flow.let dots, dot = F.makeevent ()let calc =We need two state variables for two arguments of calculation let f = ref (fun x -> x) and now = ref 0.0 inbut we repeat (performremember the older argument in partial application. op <– repeat
    (performEnter the digits of a number (on later turns d <– await digits;starting from the second digit) emit (now := 10. *. !now +. d; !now)) \simuntil:ops;until operator button is pressed.
    emit (now := !f !now; f := op !now; !now); d <– repeat\nwarrowCompute the result and ‘‘store away’’ the operator.(perform op <– await ops; return (f := op !now)) \simuntil:digits;The user can pick a different operator. emit (now := d; !now))Reset the state to a new number.let calce, cancelcalc = eventflow calcNotifies display update.

    7.2 Tk: LablTk

    7.3 GTk+: LablGTk

    Functional Programming

    Zippers, Reactivity, GUIs

    Exercise 1: Introduce operators -, / into the context rewriting “pull out subexpression” example. Remember that they are not commutative.

    Exercise 2: Add to the paddle game example:

    1. game restart,
    2. score keeping,
    3. game quitting (in more-or-less elegant way).

    Exercise 3: Our numerical integration function roughly corresponds to the rectangle rule. Modify the rule and write a test for the accuracy of:

    1. the trapezoidal rule;
    2. *the Simpson’s

    rule.* http://en.wikipedia.org/wiki/Simpson%27s_rule

    Exercise 4: Explain the recursive behavior of integration:

    1. In paddle game implemented by stream processing – *Lec10b.ml*, do we look at past velocity to determine current position, at past position to determine current velocity, both, or neither?
    2. What is the difference between *integral* and *integral_nice* in *Lec10c.ml*, what happens when we replace the former with the latter in the *pbal* function? How about after rewriting *pbal* into pure style as in the following exercise?

    Exercise 5: Reimplement the Froc based paddle ball example in a pure style: rewrite the pbal function to not use notify_e.

    Exercise 6: * Our implementation of flows is a bit heavy. One alternative approach is to use continuations, as in Scala.React. OCaml has a continuations library Delimcc; for how it can cooperate with Froc, seehttp://ambassadortothecomputers.blogspot.com/2010/08/mixing-monadic-and-direct-style-code.html

    Exercise 7: Implement parallel for flows, retaining coarse-grained implementation and using the event queue from Froc somehow (instead of introducing a new job queue).

    Exercise 8: Add quitting, e.g. via a 'q' key press, to the painter example. Use the is_cancelled function.

    Exercise 9: Our calculator example is not finished. Implement entering decimal fractions: add handling of the dots event.

    Exercise 10: The Flow module has reader monad functions that have not been discussed on slides:let local f m = fun emit -> m (fun x -> emit (f x))let localopt f m = fun emit -> m (fun x -> match f x with None -> () | Some y -> emit y)val local : (’a -> ’b) -> (’a, ’c) flow -> (’b, ’c) flowval localopt : (’a -> ’b option) -> (’a, ’c) flow -> (’b, ’c) flow

    Implement an example that uses this compositionality-increasing capability.

    The Expression Problem

    The Expression Problem

    Code organization, extensibility and reuse

    type0.5emvar0.5em=0.5emstringVariables constitute a sub-language of its own.We treat this sub-language slightly differently – no need for a dedicated variant.let0.5emevalvar0.5emwrap0.5emsub0.5em(s0.5em:0.5emvar)0.5em=0.5em0.5emtry0.5emList.assoc0.5ems0.5emsub0.5emwith0.5emNotfound0.5em->0.5emwrap0.5emstype0.5em’a0.5emlambda0.5em=Here we define the sub-language of \lambda-expressions.0.5em0.5emVarL0.5emof0.5emvar0.5em|0.5emAbs0.5emof0.5emstring0.5em0.5em’a0.5em|0.5emApp0.5emof0.5em’a0.5em0.5em’aDuring evaluation, we need to freshen variables to avoid capturelet0.5emgensym0.5em=0.5emlet0.5emn0.5em=0.5emref0.5em00.5emin0.5emfun0.5em()0.5em->0.5emincr0.5emn;0.5em”“0.5emˆ0.5emstringofint0.5em!n(mistaking distinct variables with the same name).let0.5emevallambda0.5emevalrec0.5emwrap0.5emunwrap0.5emsubst0.5eme0.5em=0.5em0.5emmatch0.5emunwrap0.5eme0.5emwithAlternatively, unwrapping could use an exception,0.5em0.5em|0.5emSome0.5em(VarL0.5emv)0.5em->0.5emevalvar0.5em(fun0.5emv0.5em->0.5emwrap0.5em(VarL0.5emv))0.5emsubst0.5emv0.5em0.5em|0.5emSome0.5em(App0.5em(l1,0.5eml2))0.5em->but we use the option type as it is safer0.5em0.5em0.5em0.5emlet0.5eml1’0.5em=0.5emevalrec0.5emsubst0.5eml1and more flexible in this context.0.5em0.5em0.5em0.5emand0.5eml2’0.5em=0.5emevalrec0.5emsubst0.5eml20.5eminRecursive processing function returns expression0.5em0.5em0.5em0.5em(match0.5emunwrap0.5eml1’0.5emwithof the completed language, we need0.5em0.5em0.5em0.5em|0.5emSome0.5em(Abs0.5em(s,0.5embody))0.5em->to unwrap it into the current sub-language.0.5em0.5em0.5em0.5em0.5em0.5emevalrec0.5em[s,0.5eml2’]0.5embodyThe recursive call is already wrapped.0.5em0.5em0.5em0.5em|0.5em0.5em _ ->0.5emwrap0.5em(App0.5em(l1’,0.5eml2’)))Wrap into the completed language.0.5em0.5em0.5emSome0.5em(Abs0.5em(s,0.5eml1))0.5em->0.5em0.5em0.5em0.5emlet0.5ems’0.5em=0.5emgensym0.5em()0.5eminRename variable to avoid capture (\alpha-equivalence).0.5em0.5em0.5em0.5emwrap0.5em(Abs0.5em(s’,0.5emevalrec0.5em((s,0.5emwrap0.5em(VarL0.5ems’))::subst)0.5eml1))0.5em0.5em0.5emNone0.5em->0.5emeFalling-through when not in the current sub-language.type0.5emlambdat0.5em=0.5emLambdat0.5emof0.5emlambdat0.5emlambdaDefining \lambda-expressionsas the completed language,let0.5emrec0.5emeval10.5emsubst0.5em=and the corresponding eval function.0.5em0.5emevallambda0.5emeval10.5em0.5em0.5em0.5em(fun0.5eme0.5em->0.5emLambdat0.5eme)0.5em(fun0.5em(Lambdat0.5eme)0.5em->0.5emSome0.5eme)0.5emsubsttype0.5em’a0.5emexpr0.5em=The sub-language of arithmetic expressions.0.5em0.5emVarE0.5emof0.5emvar0.5em0.5emNum0.5emof0.5emint0.5em0.5emAdd0.5emof0.5em’a0.5em0.5em’a0.5em0.5emMult0.5emof0.5em’a0.5em0.5em’alet0.5emevalexpr0.5emevalrec0.5emwrap0.5emunwrap0.5emsubst0.5eme0.5em=0.5em0.5emmatch0.5emunwrap0.5eme0.5emwith0.5em0.5em0.5emSome0.5em(Num0.5em)0.5em->0.5eme0.5em0.5em0.5emSome0.5em(VarE0.5emv)0.5em->0.5em0.5em0.5em0.5emevalvar0.5em(fun0.5emx0.5em->0.5emwrap0.5em(VarE0.5emx))0.5emsubst0.5emv0.5em0.5em0.5emSome0.5em(Add0.5em(m,0.5emn))0.5em->0.5em0.5em0.5em0.5emlet0.5emm’0.5em=0.5emevalrec0.5emsubst0.5emm0.5em0.5em0.5em0.5emand0.5emn’0.5em=0.5emevalrec0.5emsubst0.5emn0.5emin0.5em0.5em0.5em0.5em(match0.5emunwrap0.5emm’,0.5emunwrap0.5emn’0.5emwithUnwrapping to check if the subexpressions0.5em0.5em0.5em0.5em0.5emSome0.5em(Num0.5emm’),0.5emSome0.5em(Num0.5emn’)0.5em->got computed to values.0.5em0.5em0.5em0.5em0.5em0.5emwrap0.5em(Num0.5em(m’0.5em+0.5emn’))0.5em0.5em0.5em0.5em->0.5emwrap0.5em(Add0.5em(m’,0.5emn’)))Here m' and n' are wrapped.0.5em0.5em0.5emSome0.5em(Mult0.5em(m,0.5emn))0.5em->0.5em0.5em0.5em0.5emlet0.5emm’0.5em=0.5emevalrec0.5emsubst0.5emm0.5em0.5em0.5em0.5emand0.5emn’0.5em=0.5emevalrec0.5emsubst0.5emn0.5emin0.5em0.5em0.5em0.5em(match0.5emunwrap0.5emm’,0.5emunwrap0.5emn’0.5emwith0.5em0.5em0.5em0.5em0.5emSome0.5em(Num0.5emm’),0.5emSome0.5em(Num0.5emn’)0.5em->0.5em0.5em0.5em0.5em0.5em0.5emwrap0.5em(Num0.5em(m’0.5em*0.5emn’))0.5em0.5em0.5em0.5em->0.5emwrap0.5em(Mult0.5em(m’,0.5emn’)))0.5em0.5em0.5emNone0.5em->0.5emetype0.5emexprt0.5em=0.5emExprt0.5emof0.5emexprt0.5emexprDefining arithmetic expressionsas the completed language,let0.5emrec0.5emeval20.5emsubst0.5em=aka. ‘‘tying the recursive knot’‘.0.5em0.5emevalexpr0.5emeval20.5em0.5em0.5em0.5em(fun0.5eme0.5em->0.5emExprt0.5eme)0.5em(fun0.5em(Exprt0.5eme)0.5em->0.5emSome0.5eme)0.5emsubsttype0.5em’a0.5emlexpr0.5em=The language merging \lambda-expressions and arithmetic expressions,0.5em0.5emLambda0.5emof0.5em’a0.5emlambda0.5em0.5emExpr0.5emof0.5em’a0.5emexprcan also be used asa sub-language for further extensions.let0.5emevallexpr0.5emevalrec0.5emwrap0.5emunwrap0.5emsubst0.5eme0.5em=0.5em0.5emevallambda0.5emevalrec0.5em0.5em0.5em0.5em(fun0.5eme0.5em->0.5emwrap0.5em(Lambda0.5eme))0.5em0.5em0.5em0.5em(fun0.5eme0.5em->0.5em0.5em0.5em0.5em0.5em0.5emmatch0.5emunwrap0.5eme0.5emwith0.5em0.5em0.5em0.5em0.5em0.5em0.5emSome0.5em(Lambda0.5eme)0.5em->0.5emSome0.5eme0.5em0.5em0.5em0.5em0.5em0.5em->0.5emNone)0.5em0.5em0.5em0.5emsubst0.5em0.5em0.5em0.5em(evalexpr0.5emevalrecWe use the ‘‘fall-through’’ property of eval_expr``0.5em0.5em0.5em0.5em0.5em0.5em0.5em(fun0.5eme0.5em->0.5emwrap0.5em(Expr0.5eme))to combine the evaluators.0.5em0.5em0.5em0.5em0.5em0.5em0.5em(fun0.5eme0.5em->0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5emmatch0.5emunwrap0.5eme0.5emwith0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5emSome0.5em(Expr0.5eme)0.5em->0.5emSome0.5eme0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em->0.5emNone)0.5em0.5em0.5em0.5em0.5em0.5em0.5emsubst0.5eme)type0.5emlexprt0.5em=0.5emLExprt0.5emof0.5emlexprt0.5emlexprTying the recursive knot one last time.let0.5emrec0.5emeval30.5emsubst0.5em=0.5em0.5emevallexpr0.5emeval30.5em0.5em0.5em0.5em(fun0.5eme0.5em->0.5emLExprt0.5eme)0.5em0.5em0.5em0.5em(fun0.5em(LExprt0.5eme)0.5em->0.5emSome0.5eme)0.5emsubstLightweight FP non-solution: Extensible Variant Types

    type0.5emexpr0.5em=0.5em..This is how extensible variant types are defined.type0.5emvarname0.5em=0.5emstringtype0.5emexpr0.5em+=0.5emVar0.5emof0.5emstringWe add a variant case.let0.5emevalvar0.5emsub0.5em=0.5emfunction0.5em0.5em0.5emVar0.5ems0.5emas0.5emv0.5em->0.5em(try0.5emList.assoc0.5ems0.5emsub0.5emwith0.5emNotfound0.5em->0.5emv)0.5em0.5em0.5eme0.5em->0.5emelet0.5emgensym0.5em=0.5emlet0.5emn0.5em=0.5emref0.5em00.5emin0.5emfun0.5em()0.5em->0.5emincr0.5emn;0.5em”“0.5em0.5emstringofint0.5em!ntype0.5emexpr0.5em+=0.5emAbs0.5emof0.5emstring0.5em0.5emexpr0.5em0.5emApp0.5emof0.5emexpr0.5em0.5emexprThe sub-languagesare not differentiated by types, a shortcoming of this non-solution.let0.5emevallambda0.5emevalrec0.5emsubst0.5em=0.5emfunction0.5em0.5em0.5emVar0.5em0.5emas0.5emv0.5em->0.5emevalvar0.5emsubst0.5emv0.5em0.5em0.5emApp0.5em(l1,0.5eml2)0.5em->0.5em0.5em0.5em0.5emlet0.5eml2’0.5em=0.5emevalrec0.5emsubst0.5eml20.5emin0.5em0.5em0.5em0.5em(match0.5emevalrec0.5emsubst0.5eml10.5emwith0.5em0.5em0.5em0.5em0.5emAbs0.5em(s,0.5embody)0.5em->0.5em0.5em0.5em0.5em0.5em0.5emevalrec0.5em[s,0.5eml2’]0.5embody0.5em0.5em0.5em0.5em0.5eml1’0.5em->0.5emApp0.5em(l1’,0.5eml2’))0.5em0.5em0.5emAbs0.5em(s,0.5eml1)0.5em->0.5em0.5em0.5em0.5emlet0.5ems’0.5em=0.5emgensym0.5em()0.5emin0.5em0.5em0.5em0.5emAbs0.5em(s’,0.5emevalrec0.5em((s,0.5emVar0.5ems’)::subst)0.5eml1)0.5em0.5em0.5eme0.5em->0.5emelet0.5emfreevarslambda0.5emfreevarsrec0.5em=0.5emfunction0.5em0.5em0.5emVar0.5emv0.5em->0.5em[v]0.5em0.5em0.5emApp0.5em(l1,0.5eml2)0.5em->0.5emfreevarsrec0.5eml10.5em@0.5emfreevarsrec0.5eml20.5em0.5em0.5emAbs0.5em(s,0.5eml1)0.5em->0.5em0.5em0.5em0.5emList.filter0.5em(fun0.5emv0.5em->0.5emv0.5em<>0.5ems)0.5em(freevarsrec0.5eml1)0.5em0.5em->0.5em[]let0.5emrec0.5emeval10.5emsubst0.5eme0.5em=0.5emevallambda0.5emeval10.5emsubst0.5emelet0.5emrec0.5emfreevars10.5eme0.5em=0.5emfreevarslambda0.5emfreevars10.5emelet0.5emtest10.5em=0.5emApp0.5em(Abs0.5em(”x”,0.5emVar0.5em”x”),0.5emVar0.5em”y”)let0.5emetest0.5em=0.5emeval10.5em[]0.5emtest1let0.5emfvtest0.5em=0.5emfreevars10.5emtest1type0.5emexpr0.5em+=0.5emNum0.5emof0.5emint0.5em0.5emAdd0.5emof0.5emexpr0.5em0.5emexpr0.5em0.5emMult0.5emof0.5emexpr0.5em0.5emexprlet0.5emmapexpr0.5emf0.5em=0.5emfunction0.5em0.5em0.5emAdd0.5em(e1,0.5eme2)0.5em->0.5emAdd0.5em(f0.5eme1,0.5emf0.5eme2)0.5em0.5em0.5emMult0.5em(e1,0.5eme2)0.5em->0.5emMult0.5em(f0.5eme1,0.5emf0.5eme2)0.5em0.5em0.5eme0.5em->0.5emelet0.5emevalexpr0.5emevalrec0.5emsubst0.5eme0.5em=0.5em0.5emmatch0.5emmapexpr0.5em(evalrec0.5emsubst)0.5eme0.5emwith0.5em0.5em0.5emAdd0.5em(Num0.5emm,0.5emNum0.5emn)0.5em->0.5emNum0.5em(m0.5em+0.5emn)0.5em0.5em0.5emMult0.5em(Num0.5emm,0.5emNum0.5emn)0.5em->0.5emNum0.5em(m0.5em*0.5emn)0.5em0.5em0.5em(Num0.5em0.5em0.5emAdd0.5em0.5em0.5emMult0.5em)0.5emas0.5eme0.5em->0.5eme0.5em0.5em0.5eme0.5em->0.5emelet0.5emfreevarsexpr0.5emfreevarsrec0.5em=0.5emfunction0.5em0.5em0.5emNum0.5em0.5em->0.5em[]0.5em0.5em0.5emAdd0.5em(e1,0.5eme2)0.5em0.5emMult0.5em(e1,0.5eme2)0.5em->0.5emfreevarsrec0.5eme10.5em@0.5emfreevarsrec0.5eme20.5em0.5em->0.5em[]let0.5emrec0.5emeval20.5emsubst0.5eme0.5em=0.5emevalexpr0.5emeval20.5emsubst0.5emelet0.5emrec0.5emfreevars20.5eme0.5em=0.5emfreevarsexpr0.5emfreevars20.5emelet0.5emtest20.5em=0.5emAdd0.5em(Mult0.5em(Num0.5em3,0.5emVar0.5em”x”),0.5emNum0.5em1)let0.5emetest20.5em=0.5emeval20.5em[]0.5emtest2let0.5emfvtest20.5em=0.5emfreevars20.5emtest2let0.5emevallexpr0.5emevalrec0.5emsubst0.5eme0.5em=0.5em0.5emevalexpr0.5emevalrec0.5emsubst0.5em(evallambda0.5emevalrec0.5emsubst0.5eme)let0.5emfreevarslexpr0.5emfreevarsrec0.5eme0.5em=0.5em0.5emfreevarslambda0.5emfreevarsrec0.5eme0.5em@0.5emfreevarsexpr0.5emfreevarsrec0.5emelet0.5emrec0.5emeval30.5emsubst0.5eme0.5em=0.5emevallexpr0.5emeval30.5emsubst0.5emelet0.5emrec0.5emfreevars30.5eme0.5em=0.5emfreevarslexpr0.5emfreevars30.5emelet0.5emtest30.5em=0.5em0.5emApp0.5em(Abs0.5em(“x”,0.5emAdd0.5em(Mult0.5em(Num0.5em3,0.5emVar0.5em”x”),0.5emNum0.5em1)),0.5em0.5em0.5em0.5em0.5em0.5em0.5emNum0.5em2)let0.5emetest30.5em=0.5emeval30.5em[]0.5emtest3let0.5emfvtest30.5em=0.5emfreevars30.5emtest3Object Oriented Programming: Subtyping

    let0.5emf0.5emx0.5em=0.5emx#mMethod invocation: object#method.val0.5emf0.5em:0.5em<0.5emm0.5em:0.5em’a;0.5em..0.5em>0.5em->0.5em’aType poymorphic in two ways: 'a is the method type,.. means that objects with more methods will be accepted.

    let0.5ema0.5em=0.5emobject0.5emmethod0.5emm0.5em=0.5em70.5em0.5emmethod0.5emx0.5em=0.5em”a”0.5emendToy example: object typeslet0.5emb0.5em=0.5emobject0.5emmethod0.5emm0.5em=0.5em420.5emmethod0.5emy0.5em=0.5em”b”0.5emendshare some but not all methods.let0.5eml0.5em=0.5em[a;0.5emb]The exact types of the objects do not agree.Error:0.5emThis0.5emexpression0.5emhas0.5emtype0.5em<0.5emm0.5em:0.5emint;0.5emy0.5em:0.5emstring0.5em>0.5em0.5em0.5em0.5em0.5em0.5em0.5embut0.5eman0.5emexpression0.5emwas0.5emexpected0.5emof0.5emtype0.5em<0.5emm0.5em:0.5emint;0.5emx0.5em:0.5emstring0.5em>0.5em0.5em0.5em0.5em0.5em0.5em0.5emThe0.5emsecond0.5emobject0.5emtype0.5emhas0.5emno0.5emmethod0.5emylet0.5eml0.5em=0.5em[(a0.5em:>0.5em<m0.5em:0.5em’a>);0.5em(b0.5em:>0.5em<m0.5em:0.5em’a>)]But the types share a supertype.val0.5eml0.5em:0.5em<0.5emm0.5em:0.5emint0.5em>0.5emlist

    OOP Non-solution: direct approach

    type0.5emvarname0.5em=0.5emstringlet0.5emgensym0.5em=0.5emlet0.5emn0.5em=0.5emref0.5em00.5emin0.5emfun0.5em()0.5em->0.5emincr0.5emn;0.5em”“0.5em0.5emstringofint0.5em!nclass0.5emvirtual0.5em[’lang]0.5emevaluable0.5em=The abstract class for objects supporting the eval method.object0.5emFor \lambda-calculus, we need helper functions:0.5em0.5emmethod0.5emvirtual0.5emeval0.5em:0.5em(varname0.5em0.5em’lang)0.5emlist0.5em->0.5em’lang0.5em0.5emmethod0.5emvirtual0.5emrename0.5em:0.5emvarname0.5em->0.5emvarname0.5em->0.5em'langrenaming of free variables,0.5em0.5emmethod0.5emapply0.5em(arg0.5em:0.5em’lang)\beta-reduction if possible (fallback otherwise).0.5em0.5em0.5em0.5em(fallback0.5em:0.5emunit0.5em->0.5em’lang)0.5em(subst0.5em:0.5em(varname0.5em0.5em’lang)0.5emlist)0.5em=0.5em0.5em0.5em0.5emfallback0.5em()endclass0.5em[’lang]0.5emvar0.5em(v0.5em:0.5emvarname)0.5em=object0.5em(self)We name the current object self.0.5em0.5eminherit0.5em[’lang]0.5emevaluable0.5em0.5emval0.5emv0.5em=0.5emv0.5em0.5emmethod0.5emeval0.5emsubst0.5em=0.5em0.5em0.5em0.5emtry0.5emList.assoc0.5emv0.5emsubst0.5emwith0.5emNotfound0.5em->0.5emself0.5em0.5emmethod0.5emrename0.5emv10.5emv20.5em=Renaming a variable:0.5em0.5em0.5em0.5emif0.5emv0.5em=0.5emv10.5emthen0.5em{<0.5emv0.5em=0.5emv20.5em>}0.5emelse0.5emselfwe clone the current object putting the new name.endclass0.5em[’lang]0.5emabs0.5em(v0.5em:0.5emvarname)0.5em(body0.5em:0.5em’lang)0.5em=object0.5em(self)0.5em0.5eminherit0.5em[’lang]0.5emevaluable0.5em0.5emval0.5emv0.5em=0.5emv0.5em0.5emval0.5embody0.5em=0.5embody0.5em0.5emmethod0.5emeval0.5emsubst0.5em=We do \alpha-conversion prior to evaluation.0.5em0.5em0.5em0.5emlet0.5emv’0.5em=0.5emgensym0.5em()0.5eminAlternatively, we could evaluate with0.5em0.5em0.5em0.5em{<0.5emv0.5em=0.5emv’;0.5embody0.5em=0.5em(body#rename0.5emv0.5emv’)#eval0.5emsubst0.5em>}substitution of v0.5em0.5emmethod0.5emrename0.5emv10.5emv20.5em=by v_inst v' : 'lang similar to num_inst below.0.5em0.5em0.5em0.5emif0.5emv0.5em=0.5emv10.5emthen0.5emselfRenaming the free variable v1, so no work if v=v1.0.5em0.5em0.5em0.5emelse0.5em{<0.5embody0.5em=0.5embody#rename0.5emv10.5emv20.5em>}0.5em0.5emmethod0.5emapply0.5emargsubst0.5em=0.5em0.5em0.5em0.5embody#eval0.5em((v,0.5emarg)::subst)endclass0.5em[’lang]0.5emapp0.5em(f0.5em:0.5em’lang)0.5em(arg0.5em:0.5em’lang)0.5em=object0.5em(self)0.5em0.5eminherit0.5em[’lang]0.5emevaluable0.5em0.5emval0.5emf0.5em=0.5emf0.5em0.5emval0.5emarg0.5em=0.5emarg0.5em0.5emmethod0.5emeval0.5emsubst0.5em=We use apply to differentiate between f = abs0.5em0.5em0.5em0.5emlet0.5emarg’0.5em=0.5emarg#eval0.5emsubst0.5emin (\beta-redexes) and f ≠ abs.0.5em0.5em0.5em0.5emf#apply0.5emarg’0.5em(fun0.5em()0.5em->0.5em{<0.5emf0.5em=0.5emf#eval0.5emsubst;0.5emarg0.5em=0.5emarg’0.5em>})0.5emsubst0.5em0.5emmethod0.5emrename0.5emv10.5emv20.5em=Cloning the object ensures that it will be a subtype of 'lang0.5em0.5em0.5em0.5em{<0.5emf0.5em=0.5emf#rename0.5emv10.5emv2;0.5emarg0.5em=0.5emarg#rename0.5emv10.5emv20.5em>}rather than just 'lang app.endtype0.5emevaluablet0.5em=0.5emevaluablet0.5emevaluableThese definitions only add nice-looking types.let0.5emnewvar10.5emv0.5em:0.5emevaluablet0.5em=0.5emnew0.5emvar0.5emvlet0.5emnewabs10.5emv0.5em(body0.5em:0.5emevaluablet)0.5em:0.5emevaluablet0.5em=0.5emnew0.5emabs0.5emv0.5embodyclass0.5emvirtual0.5emcomputemixin0.5em=0.5emobjectFor evaluating arithmetic expressions we need0.5em0.5emmethod0.5emcompute0.5em:0.5emint0.5emoption0.5em=0.5emNone0.5em0.5ema heper method compute.endclass0.5em[’lang]0.5emvarc0.5emv0.5em=0.5emobjectTo use \lambda-expressions together with arithmetic expressions0.5em0.5eminherit0.5em[’lang]0.5emvar0.5emvwe need to upgrade them with the helper method.0.5em0.5eminherit0.5emcomputemixinendclass0.5em[’lang]0.5emabsc0.5emv0.5embody0.5em=0.5emobject0.5em0.5eminherit0.5em[’lang]0.5emabs0.5emv0.5embody0.5em0.5eminherit0.5emcomputemixinendclass0.5em[’lang]0.5emappc0.5emf0.5emarg0.5em=0.5emobject0.5em0.5eminherit0.5em[’lang]0.5emapp0.5emf0.5emarg0.5em0.5eminherit0.5emcomputemixinendclass0.5em[’lang]0.5emnum0.5em(i0.5em:0.5emint)0.5em=A numerical constant.object0.5em(self)0.5em0.5eminherit0.5em[’lang]0.5emevaluable0.5em0.5emval0.5emi0.5em=0.5emi0.5em0.5emmethod0.5emeval0.5emsubst0.5em=0.5emself0.5em0.5emmethod0.5emrename0.5em=0.5emself0.5em0.5emmethod0.5emcompute0.5em=0.5emSome0.5emiendclass0.5emvirtual0.5em[’lang]0.5emoperationAbstract class for evaluating arithmetic operations.0.5em0.5em0.5em0.5em(numinst0.5em:0.5emint0.5em->0.5em’lang)0.5em(n10.5em:0.5em’lang)0.5em(n20.5em:0.5em’lang)0.5em=object0.5em(self)0.5em0.5eminherit0.5em[’lang]0.5emevaluable0.5em0.5emval0.5emn10.5em=0.5emn10.5em0.5emval0.5emn20.5em=0.5emn20.5em0.5emmethod0.5emeval0.5emsubst0.5em=0.5em0.5em0.5em0.5emlet0.5emself’0.5em=0.5em{<0.5emn10.5em=0.5emn1#eval0.5emsubst;0.5emn20.5em=0.5emn2#eval0.5emsubst0.5em>}0.5emin0.5em0.5em0.5em0.5emmatch0.5emself’#compute0.5emwith0.5em0.5em0.5em0.5em0.5emSome0.5emi0.5em->0.5emnuminst0.5emiWe need to inject the integer as a constant that is0.5em0.5em0.5em0.5em->0.5emself'a subtype of 'lang.0.5em0.5emmethod0.5emrename0.5emv10.5emv20.5em=0.5em{<0.5emn10.5em=0.5emn1#rename0.5emv10.5emv2;0.5emn20.5em=0.5emn2#rename0.5emv10.5emv20.5em>}endclass0.5em[’lang]0.5emadd0.5emnuminst0.5emn10.5emn20.5em=object0.5em(self)0.5em0.5eminherit0.5em[’lang]0.5emoperation0.5emnuminst0.5emn10.5emn20.5em0.5emmethod0.5emcompute0.5em=If compute is called by eval, as intended,0.5em0.5em0.5em0.5emmatch0.5emn1#compute,0.5emn2#compute0.5emwiththen n1 and n2 are already computed.0.5em0.5em0.5em0.5em0.5emSome0.5emi1,0.5emSome0.5emi20.5em->0.5emSome0.5em(i10.5em+0.5emi2)0.5em0.5em0.5em0.5em->0.5emNoneendclass0.5em[’lang]0.5emmult0.5emnuminst0.5emn10.5emn20.5em=object0.5em(self)0.5em0.5eminherit0.5em[’lang]0.5emoperation0.5emnuminst0.5emn10.5emn20.5em0.5emmethod0.5emcompute0.5em=0.5em0.5em0.5em0.5emmatch0.5emn1#compute,0.5emn2#compute0.5emwith0.5em0.5em0.5em0.5em0.5emSome0.5emi1,0.5emSome0.5emi20.5em->0.5emSome0.5em(i10.5em*0.5emi2)0.5em0.5em0.5em0.5em->0.5emNoneendclass0.5emvirtual0.5em[’lang]0.5emcomputable0.5em=This class is defined merely to provide an object type,objectwe could also define this object type ‘‘by hand’’.0.5em0.5eminherit0.5em[’lang]0.5emevaluable0.5em0.5eminherit0.5emcomputemixinendtype0.5emcomputablet0.5em=0.5emcomputablet0.5emcomputableNice types for all the constructors.let0.5emnewvar20.5emv0.5em:0.5emcomputablet0.5em=0.5emnew0.5emvarc0.5emvlet0.5emnewabs20.5emv0.5em(body0.5em:0.5emcomputablet)0.5em:0.5emcomputablet0.5em=0.5emnew0.5emabsc0.5emv0.5embodylet0.5emnewapp20.5emv0.5em(body0.5em:0.5emcomputablet)0.5em:0.5emcomputablet0.5em=0.5emnew0.5emappc0.5emv0.5embodylet0.5emnewnum20.5emi0.5em:0.5emcomputablet0.5em=0.5emnew0.5emnum0.5emilet0.5emnewadd20.5em(n10.5em:0.5emcomputablet)0.5em(n20.5em:0.5emcomputablet)0.5em:0.5emcomputablet0.5em=0.5em0.5emnew0.5emadd0.5emnewnum20.5emn10.5emn2let0.5emnewmult20.5em(n10.5em:0.5emcomputablet)0.5em(n20.5em:0.5emcomputablet)0.5em:0.5emcomputablet0.5em=0.5em0.5emnew0.5emmult0.5emnewnum20.5emn10.5emn2OOP: The Visitor Pattern

    type0.5em’visitor0.5emvisitable0.5em=0.5em<0.5emaccept0.5em:0.5em’visitor0.5em->0.5emunit0.5em>The variants need be visitable.We store the computation as side effect because of the difficultytype0.5emvarname0.5em=0.5emstringto keep the visitor polymorphic but have the result typedepend on the visitor.class0.5em[’visitor]0.5emvar0.5em(v0.5em:0.5emvarname)0.5em=The 'visitor will determine the (sub)languageobject0.5em(self)to which a given var variant belongs.0.5em0.5emmethod0.5emv0.5em=0.5emv0.5em0.5emmethod0.5emaccept0.5em:0.5em’visitor0.5em->0.5emunit0.5em=The visitor pattern inverts the way0.5em0.5em0.5em0.5emfun0.5emvisitor0.5em->0.5emvisitor#visitVar0.5emselfpattern matching proceeds: the variantendselects the pattern matching branch.let0.5emnewvar0.5emv0.5em=0.5em(new0.5emvar0.5emv0.5em:>0.5em’a0.5emvisitable)Visitors need to see the stored data,but distinct constructors need to belong to the same type.class0.5em[’visitor]0.5emabs0.5em(v0.5em:0.5emvarname)0.5em(body0.5em:0.5em’visitor0.5emvisitable)0.5em=object0.5em(self)0.5em0.5emmethod0.5emv0.5em=0.5emv0.5em0.5emmethod0.5embody0.5em=0.5embody0.5em0.5emmethod0.5emaccept0.5em:0.5em’visitor0.5em->0.5emunit0.5em=0.5em0.5em0.5em0.5emfun0.5emvisitor0.5em->0.5emvisitor#visitAbs0.5emselfendlet0.5emnewabs0.5emv0.5embody0.5em=0.5em(new0.5emabs0.5emv0.5embody0.5em:>0.5em’a0.5emvisitable)class0.5em[’visitor]0.5emapp0.5em(f0.5em:0.5em’visitor0.5emvisitable)0.5em(arg0.5em:0.5em’visitor0.5emvisitable)0.5em=object0.5em(self)0.5em0.5emmethod0.5emf0.5em=0.5emf0.5em0.5emmethod0.5emarg0.5em=0.5emarg0.5em0.5emmethod0.5emaccept0.5em:0.5em’visitor0.5em->0.5emunit0.5em=0.5em0.5em0.5em0.5emfun0.5emvisitor0.5em->0.5emvisitor#visitApp0.5emselfendlet0.5emnewapp0.5emf0.5emarg0.5em=0.5em(new0.5emapp0.5emf0.5emarg0.5em:>0.5em’a0.5emvisitable)class0.5emvirtual0.5em[’visitor]0.5emlambdavisit0.5em=This abstract class has two uses:objectit defines the visitors for the sub-langauge of \lambda-expressions,0.5em0.5emmethod0.5emvirtual0.5emvisitVar0.5em:0.5em’visitor0.5emvar0.5em->0.5emunitand it will provide an early check0.5em0.5emmethod0.5emvirtual0.5emvisitAbs0.5em:0.5em’visitor0.5emabs0.5em->0.5emunitthat the visitor classes0.5em0.5emmethod0.5emvirtual0.5emvisitApp0.5em:0.5em’visitor0.5emapp0.5em->0.5emunitimplement all the methods.endlet0.5emgensym0.5em=0.5emlet0.5emn0.5em=0.5emref0.5em00.5emin0.5emfun0.5em()0.5em->0.5emincr0.5emn;0.5em”“0.5em0.5emstringofint0.5em!nclass0.5em[’visitor]0.5emevallambda0.5em0.5em(subst0.5em:0.5em(varname0.5em0.5em’visitor0.5emvisitable)0.5emlist)0.5em0.5em(result0.5em:0.5em’visitor0.5emvisitable0.5emref)0.5em=An output argument, but also used internallyobject0.5em(self)to store intermediate results.0.5em0.5eminherit0.5em[’visitor]0.5emlambdavisit0.5em0.5emval0.5emmutable0.5emsubst0.5em=0.5emsubstWe avoid threading the argument through the visit methods.0.5em0.5emval0.5emmutable0.5embetaredex0.5em:0.5em(varname0.5em0.5em’visitor0.5emvisitable)0.5emoption0.5em=0.5emNoneWe work around0.5em0.5emmethod0.5emvisitVar0.5emvar0.5em=the need to differentiate between abs and non-abs values0.5em0.5em0.5em0.5embetaredex0.5em<-0.5emNone;of app#f inside visitApp.0.5em0.5em0.5em0.5emtry0.5emresult0.5em:=0.5emList.assoc0.5emvar#v0.5emsubst0.5em0.5em0.5em0.5emwith0.5emNotfound0.5em->0.5emresult0.5em:=0.5em(var0.5em:>0.5em’visitor0.5emvisitable)0.5em0.5emmethod0.5emvisitAbs0.5emabs0.5em=0.5em0.5em0.5em0.5emlet0.5emv’0.5em=0.5emgensym0.5em()0.5emin0.5em0.5em0.5em0.5emlet0.5emorigsubst0.5em=0.5emsubst0.5emin0.5em0.5em0.5em0.5emsubst0.5em<-0.5em(abs#v,0.5emnew_var0.5emv’)::subst;‘‘Pass’’ the updated substitution0.5em0.5em0.5em0.5em(abs#body)#accept0.5emself;to the recursive call0.5em0.5em0.5em0.5emlet0.5embody’0.5em=0.5em!result0.5eminand collect the result of the recursive call.0.5em0.5em0.5em0.5emsubst0.5em<-0.5emorigsubst;0.5em0.5em0.5em0.5embetaredex0.5em<-0.5emSome0.5em(v’,0.5embody’);Indicate that an abs has just been visited.0.5em0.5em0.5em0.5emresult0.5em:=0.5emnewabs0.5emv’0.5embody’0.5em0.5emmethod0.5emvisitApp0.5emapp0.5em=0.5em0.5em0.5em0.5emapp#arg#accept0.5emself;0.5em0.5em0.5em0.5emlet0.5emarg’0.5em=0.5em!result0.5emin0.5em0.5em0.5em0.5emapp#f#accept0.5emself;0.5em0.5em0.5em0.5emlet0.5emf’0.5em=0.5em!result0.5emin0.5em0.5em0.5em0.5emmatch0.5embetaredex0.5emwithPattern-match on app#f.0.5em0.5em0.5em0.5em0.5emSome0.5em(v’,0.5embody’)0.5em->0.5em0.5em0.5em0.5em0.5em0.5embetaredex0.5em<-0.5emNone;0.5em0.5em0.5em0.5em0.5em0.5emlet0.5emorigsubst0.5em=0.5emsubst0.5emin0.5em0.5em0.5em0.5em0.5em0.5emsubst0.5em<-0.5em(v’,0.5emarg’)::subst;0.5em0.5em0.5em0.5em0.5em0.5embody’#accept0.5emself;0.5em0.5em0.5em0.5em0.5em0.5emsubst0.5em<-0.5emorigsubst0.5em0.5em0.5em0.5em0.5emNone0.5em->0.5emresult0.5em:=0.5emnewapp0.5emf’0.5emarg’endclass0.5em[’visitor]0.5emfreevarslambda0.5em(result0.5em:0.5emvarname0.5emlist0.5emref)0.5em=object0.5em(self)We use result as an accumulator.0.5em0.5eminherit0.5em[’visitor]0.5emlambdavisit0.5em0.5emmethod0.5emvisitVar0.5emvar0.5em=0.5em0.5em0.5em0.5emresult0.5em:=0.5emvar#v0.5em::0.5em!result0.5em0.5emmethod0.5emvisitAbs0.5emabs0.5em=0.5em0.5em0.5em0.5em(abs#body)#accept0.5emself;0.5em0.5em0.5em0.5emresult0.5em:=0.5emList.filter0.5em(fun0.5emv’0.5em->0.5emv’0.5em<>0.5emabs#v)0.5em!result0.5em0.5emmethod0.5emvisitApp0.5emapp0.5em=0.5em0.5em0.5em0.5emapp#arg#accept0.5emself;0.5emapp#f#accept0.5emselfendtype0.5emlambdavisitt0.5em=0.5emlambdavisitt0.5emlambdavisitVisitor for the language of \lambda-expressions.type0.5emlambdat0.5em=0.5emlambdavisitt0.5emvisitablelet0.5emeval10.5em(e0.5em:0.5emlambdat)0.5emsubst0.5em:0.5emlambdat0.5em=0.5em0.5emlet0.5emresult0.5em=0.5emref0.5em(newvar0.5em”“)0.5eminThis initial value will be ignored.0.5em0.5eme#accept0.5em(new0.5emevallambda0.5emsubst0.5emresult0.5em:>0.5emlambdavisitt);0.5em0.5em!resultlet0.5emfreevars10.5em(e0.5em:0.5emlambdat)0.5em=0.5em0.5emlet0.5emresult0.5em=0.5emref0.5em[]0.5eminInitial value of the accumulator.0.5em0.5eme#accept0.5em(new0.5emfreevarslambda0.5emresult);0.5em0.5em!resultlet0.5emtest10.5em=0.5em0.5em(newapp0.5em(newabs0.5em”x”0.5em(newvar0.5em”x”))0.5em(newvar0.5em”y”)0.5em:>0.5emlambdat)let0.5emetest0.5em=0.5emeval10.5emtest10.5em[]let0.5emfvtest0.5em=0.5emfreevars10.5emtest1class0.5em[’visitor]0.5emnum0.5em(i0.5em:0.5emint)0.5em=object0.5em(self)0.5em0.5emmethod0.5emi0.5em=0.5emi0.5em0.5emmethod0.5emaccept0.5em:0.5em’visitor0.5em->0.5emunit0.5em=0.5em0.5em0.5em0.5emfun0.5emvisitor0.5em->0.5emvisitor#visitNum0.5emselfendlet0.5emnewnum0.5emi0.5em=0.5em(new0.5emnum0.5emi0.5em:>0.5em’a0.5emvisitable)class0.5emvirtual0.5em[’visitor]0.5emoperation0.5em0.5em(arg10.5em:0.5em’visitor0.5emvisitable)0.5em(arg20.5em:0.5em’visitor0.5emvisitable)0.5em=object0.5em(self)Shared accessor methods.0.5em0.5emmethod0.5emarg10.5em=0.5emarg10.5em0.5emmethod0.5emarg20.5em=0.5emarg2endclass0.5em[’visitor]0.5emadd0.5emarg10.5emarg20.5em=object0.5em(self)0.5em0.5eminherit0.5em[’visitor]0.5emoperation0.5emarg10.5emarg20.5em0.5emmethod0.5emaccept0.5em:0.5em’visitor0.5em->0.5emunit0.5em=0.5em0.5em0.5em0.5emfun0.5emvisitor0.5em->0.5emvisitor#visitAdd0.5emselfendlet0.5emnewadd0.5emarg10.5emarg20.5em=0.5em(new0.5emadd0.5emarg10.5emarg20.5em:>0.5em’a0.5emvisitable)class0.5em[’visitor]0.5emmult0.5emarg10.5emarg20.5em=object0.5em(self)0.5em0.5eminherit0.5em[’visitor]0.5emoperation0.5emarg10.5emarg20.5em0.5emmethod0.5emaccept0.5em:0.5em’visitor0.5em->0.5emunit0.5em=0.5em0.5em0.5em0.5emfun0.5emvisitor0.5em->0.5emvisitor#visitMult0.5emselfendlet0.5emnewmult0.5emarg10.5emarg20.5em=0.5em(new0.5emmult0.5emarg10.5emarg20.5em:>0.5em’a0.5emvisitable)class0.5emvirtual0.5em[’visitor]0.5emexprvisit0.5em=The sub-language of arithmetic expressions.object0.5em0.5emmethod0.5emvirtual0.5emvisitNum0.5em:0.5em’visitor0.5emnum0.5em->0.5emunit0.5em0.5emmethod0.5emvirtual0.5emvisitAdd0.5em:0.5em’visitor0.5emadd0.5em->0.5emunit0.5em0.5emmethod0.5emvirtual0.5emvisitMult0.5em:0.5em’visitor0.5emmult0.5em->0.5emunitendclass0.5em[’visitor]0.5emevalexpr0.5em0.5em(result0.5em:0.5em’visitor0.5emvisitable0.5emref)0.5em=object0.5em(self)0.5em0.5eminherit0.5em[’visitor]0.5emexprvisit0.5em0.5emval0.5emmutable0.5emnumredex0.5em:0.5emint0.5emoption0.5em=0.5emNoneThe numeric result, if any.0.5em0.5emmethod0.5emvisitNum0.5emnum0.5em=0.5em0.5em0.5em0.5emnumredex0.5em<-0.5emSome0.5emnum#i;0.5em0.5em0.5em0.5emresult0.5em:=0.5em(num0.5em:>0.5em’visitor0.5emvisitable)0.5em0.5emmethod0.5emprivate0.5emvisitOperation0.5emnewe0.5emop0.5eme0.5em=0.5em0.5em0.5em0.5em(e#arg1)#accept0.5emself;0.5em0.5em0.5em0.5emlet0.5emarg1’0.5em=0.5em!result0.5emand0.5emi10.5em=0.5emnumredex0.5emin0.5em0.5em0.5em0.5em(e#arg2)#accept0.5emself;0.5em0.5em0.5em0.5emlet0.5emarg2’0.5em=0.5em!result0.5emand0.5emi20.5em=0.5emnumredex0.5emin0.5em0.5em0.5em0.5emmatch0.5emi1,0.5emi20.5emwith0.5em0.5em0.5em0.5em0.5emSome0.5emi1,0.5emSome0.5emi20.5em->0.5em0.5em0.5em0.5em0.5em0.5emlet0.5emres0.5em=0.5emop0.5emi10.5emi20.5emin0.5em0.5em0.5em0.5em0.5em0.5emnumredex0.5em<-0.5emSome0.5emres;0.5emresult0.5em:=0.5emnewnum0.5emres0.5em0.5em0.5em0.5em->0.5em0.5em0.5em0.5em0.5em0.5emnumredex0.5em<-0.5emNone;0.5em0.5em0.5em0.5em0.5em0.5emresult0.5em:=0.5emnewe0.5emarg1’0.5emarg2’0.5em0.5emmethod0.5emvisitAdd0.5emadd0.5em=0.5emself#visitOperation0.5emnewadd0.5em(0.5em+0.5em)0.5emadd0.5em0.5emmethod0.5emvisitMult0.5emmult0.5em=0.5emself#visitOperation0.5emnewmult0.5em(0.5em*0.5em)0.5emmultendclass0.5em[’visitor]0.5emfreevarsexpr0.5em(result0.5em:0.5emvarname0.5emlist0.5emref)0.5em=Flow-through classobject0.5em(self)for computing free variables.0.5em0.5eminherit0.5em[’visitor]0.5emexprvisit0.5em0.5emmethod0.5emvisitNum=0.5em()0.5em0.5emmethod0.5emvisitAdd0.5emadd0.5em=0.5em0.5em0.5em0.5emadd#arg1#accept0.5emself;0.5emadd#arg2#accept0.5emself0.5em0.5emmethod0.5emvisitMult0.5emmult0.5em=0.5em0.5em0.5em0.5emmult#arg1#accept0.5emself;0.5emmult#arg2#accept0.5emselfendtype0.5emexprvisitt0.5em=0.5emexprvisitt0.5emexprvisitThe language of arithmetic expressionstype0.5emexprt0.5em=0.5emexprvisitt0.5emvisitable– in this example without variables.let0.5emeval20.5em(e0.5em:0.5emexprt)0.5em:0.5emexprt0.5em=0.5em0.5emlet0.5emresult0.5em=0.5emref0.5em(newnum0.5em0)0.5eminThis initial value will be ignored.0.5em0.5eme#accept0.5em(new0.5emevalexpr0.5emresult);0.5em0.5em!resultlet0.5emtest20.5em=0.5em0.5em(newadd0.5em(newmult0.5em(newnum0.5em3)0.5em(newnum0.5em3))0.5em(newnum0.5em1)0.5em:>0.5emexprt)let0.5emetest0.5em=0.5emeval20.5emtest2class0.5emvirtual0.5em[’visitor]0.5emlexprvisit0.5em=Combining the variants / constructors.object0.5em0.5eminherit0.5em[’visitor]0.5emlambdavisit0.5em0.5eminherit0.5em[’visitor]0.5emexprvisitendclass0.5em[’visitor]0.5emevallexpr0.5emsubst0.5emresult0.5em=Combining the ‘‘pattern-matching branches’’.object0.5em0.5eminherit0.5em[’visitor]0.5emevalexpr0.5emresult0.5em0.5eminherit0.5em[’visitor]0.5emevallambda0.5emsubst0.5emresultendclass0.5em[’visitor]0.5emfreevarslexpr0.5emresult0.5em=object0.5em0.5eminherit0.5em[’visitor]0.5emfreevarsexpr0.5emresult0.5em0.5eminherit0.5em[’visitor]0.5emfreevarslambda0.5emresultendtype0.5emlexprvisitt0.5em=0.5emlexprvisitt0.5emlexprvisitThe language combiningtype0.5emlexprt0.5em=0.5emlexprvisitt0.5emvisitable\lambda-expressions and arithmetic expressions.let0.5emeval30.5em(e0.5em:0.5emlexprt)0.5emsubst0.5em:0.5emlexprt0.5em=0.5em0.5emlet0.5emresult0.5em=0.5emref0.5em(newnum0.5em0)0.5emin0.5em0.5eme#accept0.5em(new0.5emevallexpr0.5emsubst0.5emresult);0.5em0.5em!resultlet0.5emfreevars30.5em(e0.5em:0.5emlexprt)0.5em=0.5em0.5emlet0.5emresult0.5em=0.5emref0.5em[]0.5emin0.5em0.5eme#accept0.5em(new0.5emfreevarslexpr0.5emresult);0.5em0.5em!resultlet0.5emtest30.5em=0.5em0.5em(newadd0.5em(newmult0.5em(newnum0.5em3)0.5em(newvar0.5em”x”))0.5em(newnum0.5em1)0.5em:>0.5emlexprt)let0.5emetest0.5em=0.5emeval30.5emtest30.5em[]let0.5emfvtest0.5em=0.5emfreevars30.5emtest3let0.5emoldetest0.5em=0.5emeval30.5em(test20.5em:>0.5emlexprt)0.5em[]let0.5emoldfvtest0.5em=0.5emeval30.5em(test20.5em:>0.5emlexprt)0.5em[]Polymorphic Variant Types: Subtyping

    type0.5emvar0.5em=0.5em[’Var0.5emof0.5emstring]let0.5emevalvar0.5emsub0.5em(’Var0.5ems0.5emas0.5emv0.5em:0.5emvar)0.5em=0.5em0.5emtry0.5emList.assoc0.5ems0.5emsub0.5emwith0.5emNotfound0.5em->0.5emvtype0.5em’a0.5emlambda0.5em=0.5em0.5em[’Var0.5emof0.5emstring0.5em0.5em‘Abs0.5emof0.5emstring0.5em0.5em’a0.5em0.5em‘App0.5emof0.5em’a0.5em0.5em’a]let0.5emgensym0.5em=0.5emlet0.5emn0.5em=0.5emref0.5em00.5emin0.5emfun0.5em()0.5em->0.5emincr0.5emn;0.5em”“0.5em0.5emstringofint0.5em!nlet0.5emevallambda0.5emevalrec0.5emsubst0.5em:0.5em’a0.5emlambda0.5em->0.5em’a0.5em=0.5emfunction0.5em0.5em0.5em#var0.5emas0.5emv0.5em->0.5emevalvar0.5emsubst0.5emvWe could also leave the type open0.5em0.5em0.5em‘App0.5em(l1,0.5eml2)0.5em->rather than closing it to lambda.0.5em0.5em0.5em0.5emlet0.5eml2’0.5em=0.5emevalrec0.5emsubst0.5eml20.5emin0.5em0.5em0.5em0.5em(match0.5emevalrec0.5emsubst0.5eml10.5emwith0.5em0.5em0.5em0.5em0.5em‘Abs0.5em(s,0.5embody)0.5em->0.5em0.5em0.5em0.5em0.5em0.5emevalrec0.5em[s,0.5eml2’]0.5embody0.5em0.5em0.5em0.5em0.5eml1’0.5em->0.5em‘App0.5em(l1’,0.5eml2’))0.5em0.5em0.5em‘Abs0.5em(s,0.5eml1)0.5em->0.5em0.5em0.5em0.5emlet0.5ems’0.5em=0.5emgensym0.5em()0.5emin0.5em0.5em0.5em0.5em‘Abs0.5em(s’,0.5emevalrec0.5em((s,0.5em‘Var0.5ems’)::subst)0.5eml1)let0.5emfreevarslambda0.5emfreevarsrec0.5em:0.5em’a0.5emlambda0.5em->0.5em’b0.5em=0.5emfunction0.5em0.5em0.5em‘Var0.5emv0.5em->0.5em[v]0.5em0.5em0.5em‘App0.5em(l1,0.5eml2)0.5em->0.5emfreevarsrec0.5eml10.5em@0.5emfreevarsrec0.5eml20.5em0.5em0.5em‘Abs0.5em(s,0.5eml1)0.5em->0.5em0.5em0.5em0.5emList.filter0.5em(fun0.5emv0.5em->0.5emv0.5em<>0.5ems)0.5em(freevarsrec0.5eml1)type0.5emlambdat0.5em=0.5emlambdat0.5emlambdalet0.5emrec0.5emeval10.5emsubst0.5eme0.5em:0.5emlambdat0.5em=0.5emevallambda0.5emeval10.5emsubst0.5emelet0.5emrec0.5emfreevars10.5em(e0.5em:0.5emlambdat)0.5em=0.5emfreevarslambda0.5emfreevars10.5emelet0.5emtest10.5em=0.5em(’App0.5em(’Abs0.5em(”x”,0.5em‘Var0.5em”x”),0.5em‘Var0.5em”y”)0.5em:>0.5emlambdat)let0.5emetest0.5em=0.5emeval10.5em[]0.5emtest1let0.5emfvtest0.5em=0.5emfreevars10.5emtest1type0.5em’a0.5emexpr0.5em=0.5em0.5em[’Var0.5emof0.5emstring0.5em0.5em‘Num0.5emof0.5emint0.5em0.5em‘Add0.5emof0.5em’a0.5em0.5em’a0.5em0.5em‘Mult0.5emof0.5em’a0.5em0.5em’a]let0.5emmapexpr0.5em(f0.5em:0.5em0.5em->0.5em’a)0.5em:0.5em’a0.5emexpr0.5em->0.5em’a0.5em=0.5emfunction0.5em0.5em0.5em#var0.5emas0.5emv0.5em->0.5emv0.5em0.5em0.5em‘Num0.5em0.5emas0.5emn0.5em->0.5emn0.5em0.5em0.5em‘Add0.5em(e1,0.5eme2)0.5em->0.5em‘Add0.5em(f0.5eme1,0.5emf0.5eme2)0.5em0.5em0.5em‘Mult0.5em(e1,0.5eme2)0.5em->0.5em‘Mult0.5em(f0.5eme1,0.5emf0.5eme2)let0.5emevalexpr0.5emevalrec0.5emsubst0.5em(e0.5em:0.5em’a0.5emexpr)0.5em:0.5em’a0.5em=0.5em0.5emmatch0.5emmapexpr0.5em(evalrec0.5emsubst)0.5eme0.5emwith0.5em0.5em0.5em#var0.5emas0.5emv0.5em->0.5emevalvar0.5emsubst0.5emvHere and elsewhere, we could also factor-out0.5em0.5em0.5em‘Add0.5em(’Num0.5emm,0.5em‘Num0.5emn)0.5em->0.5em‘Num0.5em(m0.5em+0.5emn)the sub-language of variables.0.5em0.5em0.5em‘Mult0.5em(’Num0.5emm,0.5em‘Num0.5emn)0.5em->0.5em‘Num0.5em(m0.5em*0.5emn)0.5em0.5em0.5eme0.5em->0.5emelet0.5emfreevarsexpr0.5emfreevarsrec0.5em:0.5em’a0.5emexpr0.5em->0.5em’b0.5em=0.5emfunction0.5em0.5em0.5em‘Var0.5emv0.5em->0.5em[v]0.5em0.5em0.5em‘Num0.5em0.5em->0.5em[]0.5em0.5em0.5em‘Add0.5em(e1,0.5eme2)0.5em0.5em‘Mult0.5em(e1,0.5eme2)0.5em->0.5emfreevarsrec0.5eme10.5em@0.5emfreevarsrec0.5eme2type0.5emexprt0.5em=0.5emexprt0.5emexprlet0.5emrec0.5emeval20.5emsubst0.5eme0.5em:0.5emexprt0.5em=0.5emevalexpr0.5emeval20.5emsubst0.5emelet0.5emrec0.5emfreevars20.5em(e0.5em:0.5emexprt)0.5em=0.5emfreevarsexpr0.5emfreevars20.5emelet0.5emtest20.5em=0.5em(’Add0.5em(’Mult0.5em(’Num0.5em3,0.5em‘Var0.5em”x”),0.5em‘Num0.5em1)0.5em:0.5emexprt)let0.5emetest20.5em=0.5emeval20.5em[“x”,0.5em‘Num0.5em2]0.5emtest2let0.5emfvtest20.5em=0.5emfreevars20.5emtest2type0.5em’a0.5emlexpr0.5em=0.5em[’a0.5emlambda0.5em0.5em’a0.5emexpr]let0.5emevallexpr0.5emevalrec0.5emsubst0.5em:0.5em’a0.5emlexpr0.5em->0.5em’a0.5em=0.5emfunction0.5em0.5em0.5em#lambda0.5emas0.5emx0.5em->0.5emevallambda0.5emevalrec0.5emsubst0.5emx0.5em0.5em0.5em#expr0.5emas0.5emx0.5em->0.5emevalexpr0.5emevalrec0.5emsubst0.5emxlet0.5emfreevarslexpr0.5emfreevarsrec0.5em:0.5em’a0.5emlexpr0.5em->0.5em’b0.5em=0.5emfunction0.5em0.5em0.5em#lambda0.5emas0.5emx0.5em->0.5emfreevarslambda0.5emfreevarsrec0.5emx0.5em0.5em0.5em#expr0.5emas0.5emx0.5em->0.5emfreevarsexpr0.5emfreevarsrec0.5emxtype0.5emlexprt0.5em=0.5emlexprt0.5emlexprlet0.5emrec0.5emeval30.5emsubst0.5eme0.5em:0.5emlexprt0.5em=0.5emevallexpr0.5emeval30.5emsubst0.5emelet0.5emrec0.5emfreevars30.5em(e0.5em:0.5emlexprt)0.5em=0.5emfreevarslexpr0.5emfreevars30.5emelet0.5emtest30.5em=0.5em0.5em(’App0.5em(’Abs0.5em(“x”,0.5em‘Add0.5em(’Mult0.5em(’Num0.5em3,0.5em‘Var0.5em”x”),0.5em‘Num0.5em1)),0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em‘Num0.5em2)0.5em:0.5emlexprt)let0.5emetest30.5em=0.5emeval30.5em[]0.5emtest3let0.5emfvtest30.5em=0.5emfreevars30.5emtest3let0.5emeoldtest0.5em=0.5emeval30.5em[]0.5em(test20.5em:>0.5emlexprt)let0.5emfvoldtest0.5em=0.5emfreevars30.5em(test20.5em:>0.5emlexprt)Polymorphic Variants and Recursive Modules

    type0.5emvar0.5em=0.5em[’Var0.5emof0.5emstring]let0.5emevalvar0.5emsubst0.5em(’Var0.5ems0.5emas0.5emv0.5em:0.5emvar)0.5em=0.5em0.5emtry0.5emList.assoc0.5ems0.5emsubst0.5emwith0.5emNotfound0.5em->0.5emvtype0.5em’a0.5emlambda0.5em=0.5em0.5em[’Var0.5emof0.5emstring0.5em0.5em‘Abs0.5emof0.5emstring0.5em0.5em’a0.5em0.5em‘App0.5emof0.5em’a0.5em0.5em’a]module0.5emtype0.5emEval0.5em=sig0.5emtype0.5emexp0.5emval0.5emeval0.5em:0.5em(string0.5em*0.5emexp)0.5emlist0.5em->0.5emexp0.5em->0.5emexp0.5emendmodule0.5emLF(X0.5em:0.5emEval0.5emwith0.5emtype0.5emexp0.5em=0.5emprivate0.5em[>0.5em’a0.5emlambda]0.5emas0.5em’a)0.5em=struct0.5em0.5emtype0.5emexp0.5em=0.5emX.exp0.5emlambda0.5em0.5emlet0.5emgensym0.5em=0.5em

    let0.5emn0.5em=0.5emref0.5em00.5emin0.5emfun0.5em()0.5em->0.5emincr0.5emn;0.5em”“0.5em0.5emstringofint0.5em!n0.5em0.5emlet0.5emeval0.5emsubst0.5em:0.5emexp0.5em->0.5emX.exp0.5em=0.5emfunction0.5em0.5em0.5em0.5em0.5em#var0.5emas0.5emv0.5em->0.5emevalvar0.5emsubst0.5emv0.5em0.5em0.5em0.5em0.5em‘App0.5em(l1,0.5eml2)0.5em->0.5em0.5em0.5em0.5em0.5em0.5emlet0.5eml2’0.5em=0.5emX.eval0.5emsubst0.5eml20.5emin0.5em0.5em0.5em0.5em0.5em0.5em(match0.5emX.eval0.5emsubst0.5eml10.5emwith0.5em0.5em0.5em0.5em0.5em0.5em0.5em‘Abs0.5em(s,0.5embody)0.5em->0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5emX.eval0.5em[s,0.5eml2’]0.5embody0.5em0.5em0.5em0.5em0.5em0.5em0.5eml1’0.5em->0.5em‘App0.5em(l1’,0.5eml2’))0.5em0.5em0.5em0.5em0.5em‘Abs0.5em(s,0.5eml1)0.5em->0.5em0.5em0.5em0.5em0.5em0.5emlet0.5ems’0.5em=0.5emgensym0.5em()0.5emin0.5em0.5em0.5em0.5em0.5em0.5em‘Abs0.5em(s’,0.5emX.eval0.5em((s,0.5em‘Var0.5ems’)::subst)0.5eml1)endmodule0.5emrec0.5emLambda0.5em:0.5em(Eval0.5emwith0.5emtype0.5emexp0.5em=0.5emLambda.exp0.5emlambda)0.5em=0.5em0.5emLF(Lambda)module0.5emtype0.5emFreeVars0.5em=sig0.5emtype0.5emexp0.5emval0.5emfreevars0.5em:0.5emexp0.5em->0.5emstring0.5emlist0.5emendmodule0.5emLFVF(X0.5em:0.5emFreeVars0.5emwith0.5emtype0.5emexp0.5em=0.5emprivate0.5em[>0.5em’a0.5emlambda]0.5emas0.5em’a)0.5em=struct0.5em0.5emtype0.5emexp0.5em=0.5emX.exp0.5emlambda0.5em0.5emlet0.5emfreevars0.5em:0.5emexp0.5em->0.5em’b0.5em=0.5emfunction0.5em0.5em0.5em0.5em0.5em‘Var0.5emv0.5em->0.5em[v]0.5em0.5em0.5em0.5em0.5em‘App0.5em(l1,0.5eml2)0.5em->0.5emX.freevars0.5eml10.5em@0.5emX.freevars0.5eml20.5em0.5em0.5em0.5em0.5em‘Abs0.5em(s,0.5eml1)0.5em->0.5em0.5em0.5em0.5em0.5em0.5emList.filter0.5em(fun0.5emv0.5em->0.5emv0.5em<>0.5ems)0.5em(X.freevars0.5eml1)endmodule0.5emrec0.5emLambdaFV0.5em:0.5em(FreeVars0.5emwith0.5emtype0.5emexp0.5em=0.5emLambdaFV.exp0.5emlambda)0.5em=0.5em0.5emLFVF(LambdaFV)let0.5emtest10.5em=0.5em(’App0.5em(’Abs0.5em(”x”,0.5em‘Var0.5em”x”),0.5em‘Var0.5em”y”)0.5em:0.5emLambda.exp)let0.5emetest0.5em=0.5emLambda.eval0.5em[]0.5emtest1let0.5emfvtest0.5em=0.5emLambdaFV.freevars0.5emtest1type0.5em’a0.5emexpr0.5em=0.5em0.5em[’Var0.5emof0.5emstring0.5em0.5em‘Num0.5emof0.5emint0.5em0.5em‘Add0.5emof0.5em’a0.5em0.5em’a0.5em0.5em‘Mult0.5emof0.5em’a0.5em0.5em’a]module0.5emtype0.5emOperations0.5em=sig0.5eminclude0.5emEval0.5eminclude0.5emFreeVars0.5emwith0.5emtype0.5emexp0.5em:=0.5emexp0.5emendmodule0.5emEF(X0.5em:0.5emOperations0.5emwith0.5emtype0.5emexp0.5em=0.5emprivate0.5em[>0.5em’a0.5emexpr]0.5emas0.5em’a)0.5em=struct0.5em0.5emtype0.5emexp0.5em=0.5emX.exp0.5emexpr0.5em0.5emlet0.5emmapexpr0.5emf0.5em=0.5emfunction0.5em0.5em0.5em0.5em0.5em#var0.5emas0.5emv0.5em->0.5emv0.5em0.5em0.5em0.5em0.5em‘Num0.5em0.5emas0.5emn0.5em->0.5emn0.5em0.5em0.5em0.5em0.5em‘Add0.5em(e1,0.5eme2)0.5em->0.5em‘Add0.5em(f0.5eme1,0.5emf0.5eme2)0.5em0.5em0.5em0.5em0.5em‘Mult0.5em(e1,0.5eme2)0.5em->0.5em‘Mult0.5em(f0.5eme1,0.5emf0.5eme2)0.5em0.5emlet0.5emeval0.5emsubst0.5em(e0.5em:0.5emexp)0.5em:0.5emX.exp0.5em=0.5em0.5em0.5em0.5emmatch0.5emmapexpr0.5em(X.eval0.5emsubst)0.5eme0.5emwith0.5em0.5em0.5em0.5em0.5em#var0.5emas0.5emv0.5em->0.5emevalvar0.5emsubst0.5emv0.5em0.5em0.5em0.5em0.5em‘Add0.5em(’Num0.5emm,0.5em‘Num0.5emn)0.5em->0.5em‘Num0.5em(m0.5em+0.5emn)0.5em0.5em0.5em0.5em0.5em‘Mult0.5em(’Num0.5emm,0.5em‘Num0.5emn)0.5em->0.5em‘Num0.5em(m0.5em*0.5emn)0.5em0.5em0.5em0.5em0.5eme0.5em->0.5eme0.5em0.5emlet0.5emfreevars0.5em:0.5emexp0.5em->0.5em’b0.5em=0.5emfunction0.5em0.5em0.5em0.5em0.5em‘Var0.5emv0.5em->0.5em[v]0.5em0.5em0.5em0.5em0.5em‘Num0.5em0.5em->0.5em[]0.5em0.5em0.5em0.5em0.5em‘Add0.5em(e1,0.5eme2)0.5em0.5em‘Mult0.5em(e1,0.5eme2)0.5em->0.5emX.freevars0.5eme10.5em@0.5emX.freevars0.5eme2endmodule0.5emrec0.5emExpr0.5em:0.5em(Operations0.5emwith0.5emtype0.5emexp0.5em=0.5emExpr.exp0.5emexpr)0.5em=0.5em0.5emEF(Expr)let0.5emtest20.5em=0.5em(’Add0.5em(’Mult0.5em(’Num0.5em3,0.5em‘Var0.5em”x”),0.5em‘Num0.5em1)0.5em:0.5emExpr.exp)let0.5emetest20.5em=0.5emExpr.eval0.5em[“x”,0.5em‘Num0.5em2]0.5emtest2let0.5emfvstest20.5em=0.5emExpr.freevars0.5emtest2type0.5em’a0.5emlexpr0.5em=0.5em[’a0.5emlambda0.5em0.5em’a0.5emexpr]module0.5emLEF(X0.5em:0.5emOperations0.5emwith0.5emtype0.5emexp0.5em=0.5emprivate0.5em[>0.5em’a0.5emlexpr]0.5emas0.5em’a)0.5em=struct0.5em0.5emtype0.5emexp0.5em=0.5emX.exp0.5emlexpr0.5em0.5emmodule0.5emLambdaX0.5em=0.5emLF(X)0.5em0.5emmodule0.5emLambdaFVX0.5em=0.5emLFVF(X)0.5em0.5emmodule0.5emExprX0.5em=0.5emEF(X)0.5em0.5emlet0.5emeval0.5emsubst0.5em:0.5emexp0.5em->0.5emX.exp0.5em=0.5emfunction0.5em0.5em0.5em0.5em0.5em#LambdaX.exp0.5emas0.5emx0.5em->0.5emLambdaX.eval0.5emsubst0.5emx0.5em0.5em0.5em0.5em0.5em#ExprX.exp0.5emas0.5emx0.5em->0.5emExprX.eval0.5emsubst0.5emx0.5em0.5emlet0.5emfreevars0.5em:0.5emexp0.5em->0.5em’b0.5em=0.5emfunction0.5em0.5em0.5em0.5em0.5em#lambda0.5emas0.5emx0.5em->0.5emLambdaFVX.freevars0.5emxEither of #lambda or #LambdaX.exp is fine.0.5em0.5em0.5em0.5em0.5em#expr0.5emas0.5emx0.5em->0.5emExprX.freevars0.5emxEither of #expr or #ExprX.exp is fine.endmodule0.5emrec0.5emLExpr0.5em:0.5em(Operations0.5emwith0.5emtype0.5emexp0.5em=0.5emLExpr.exp0.5emlexpr)0.5em=0.5em0.5emLEF(LExpr)let0.5emtest30.5em=0.5em0.5em(’App0.5em(’Abs0.5em(“x”,0.5em‘Add0.5em(’Mult0.5em(’Num0.5em3,0.5em‘Var0.5em”x”),0.5em‘Num0.5em1)),0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em‘Num0.5em2)0.5em:0.5emLExpr.exp)let0.5emetest30.5em=0.5emLExpr.eval0.5em[]0.5emtest3let0.5emfvtest30.5em=0.5emLExpr.freevars0.5emtest3let0.5emeoldtest0.5em=0.5emLExpr.eval0.5em[]0.5em(test20.5em:>0.5emLExpr.exp)let0.5emfvoldtest0.5em=0.5emLExpr.freevars0.5em(test20.5em:>0.5emLExpr.exp)Digression: Parser Combinators

    Parser Combinators: Implementation of lazy-monad-plus

    0.5em0.5emlet0.5emmsummap0.5emf0.5eml0.5em=0.5em0.5em0.5em0.5emList.foldleftFolding left reversers the apparent order of composition,0.5em0.5em0.5em0.5em0.5em0.5em(fun0.5emacc0.5ema0.5em->0.5emmplus0.5emacc0.5em(lazy0.5em(f0.5ema)))0.5emmzero0.5emlorder from l is preserved.

    type0.5em’a0.5emllist0.5em=0.5emLNil0.5em0.5emLCons0.5emof0.5em’a0.5em0.5em’a0.5emllist0.5emLazy.tlet0.5emrec0.5emltake0.5emn0.5em=0.5emfunction0.5em0.5emLCons0.5em(a,0.5eml)0.5emwhen0.5emn0.5em>0.5em10.5em->0.5ema::(ltake0.5em(n-1)0.5em(Lazy.force0.5eml))0.5em0.5emLCons0.5em(a,0.5eml)0.5emwhen0.5emn0.5em=0.5em10.5em->0.5em[a]Avoid forcing the tail if not needed.0.5em->0.5em[]let0.5emrec0.5emlappend0.5eml10.5eml20.5em=0.5em0.5emmatch0.5eml10.5emwith0.5emLNil0.5em->0.5emLazy.force0.5eml20.5em0.5em0.5emLCons0.5em(hd,0.5emtl)0.5em-> LCons0.5em(hd,0.5emlazy0.5em(lappend0.5em(Lazy.force0.5emtl)0.5eml2))let0.5emrec0.5emlconcatmap0.5emf0.5em=0.5emfunction0.5em0.5em0.5emLNil0.5em->0.5emLNil0.5em0.5em0.5emLCons0.5em(a,0.5eml)0.5em->0.5emlappend0.5em(f0.5ema)0.5em(lazy0.5em(lconcatmap0.5emf0.5em(Lazy.force0.5eml)))module0.5emLListM0.5em=0.5emMonadPlus0.5em(struct0.5em0.5emtype0.5em’a0.5emt0.5em=0.5em’a0.5emllist0.5em0.5emlet0.5embind0.5ema0.5emb0.5em=0.5emlconcatmap0.5emb0.5ema0.5em0.5emlet0.5emreturn0.5ema0.5em=0.5emLCons0.5em(a,0.5emlazy0.5emLNil)0.5em0.5emlet0.5emmzero0.5em=0.5emLNil0.5em0.5emlet0.5emmplus0.5em=0.5emlappendend)Parser Combinators: the Parsec* Monad

    open0.5emMonadmodule0.5emtype0.5emPARSE0.5em=0.5emsig0.5em0.5emtype0.5em'a0.5embacktrackingmonadName for the underlying monad-plus.0.5em0.5emtype0.5em’a0.5emparsingstate0.5em=0.5emint0.5em->0.5em(‘a0.5em0.5emint)0.5embacktrackingmonadProcessing state – position.0.5em0.5emtype0.5em’a0.5emt0.5em=0.5emstring0.5em->0.5em'a0.5emparsingstateReader for the parsed text.0.5em0.5eminclude0.5emMONADPLUSOPS0.5em0.5emval0.5em(<>)0.5em:0.5em’a0.5emmonad0.5em->0.5em’a0.5emmonad0.5emLazy.t0.5em->0.5em'a0.5emmonadA synonym for mplus.0.5em0.5emval0.5emrun0.5em:0.5em’a0.5emmonad0.5em->0.5em’a0.5emt0.5em0.5emval0.5emrunT0.5em:0.5em’a0.5emmonad0.5em->0.5emstring0.5em->0.5emint0.5em->0.5em’a0.5embacktrackingmonad0.5em0.5emval0.5emsatisfy0.5em:0.5em(char0.5em->0.5embool)0.5em->0.5emchar0.5emmonadConsume a character of the specified class.0.5em0.5emval0.5emendoftext0.5em:0.5emunit0.5emmonadCheck for end of the processed text.endmodule0.5emParseT0.5em(MP0.5em:0.5emMONADPLUSOPS)0.5em:0.5em0.5emPARSE0.5emwith0.5emtype0.5em’a0.5embacktrackingmonad0.5em:=0.5em’a0.5emMP.monad0.5em=struct0.5em0.5emtype0.5em’a0.5embacktrackingmonad0.5em=0.5em’a0.5emMP.monad0.5em0.5emtype0.5em’a0.5emparsingstate0.5em=0.5emint0.5em->0.5em(’a0.5em0.5emint)0.5emMP.monad0.5em0.5emmodule0.5emM0.5em=0.5emstruct0.5em0.5em0.5em0.5emtype0.5em’a0.5emt0.5em=0.5emstring0.5em->0.5em’a0.5emparsingstate0.5em0.5em0.5em0.5em0.5emlet0.5emreturn0.5ema0.5em=0.5emfun0.5ems0.5emp0.5em->0.5emMP.return0.5em(a,0.5emp)0.5em0.5em0.5em0.5emlet0.5embind0.5emm0.5emb0.5em=0.5emfun0.5ems0.5emp0.5em->0.5em0.5em0.5em0.5em0.5em0.5emMP.bind0.5em(m0.5ems0.5emp)0.5em(fun0.5em(a,0.5emp’)0.5em->0.5emb0.5ema0.5ems0.5emp’)0.5em0.5em0.5em0.5emlet0.5emmzero0.5em=0.5emfun0.5em0.5em_0.5em->0.5emMP.mzero0.5em0.5em0.5em0.5emlet0.5emmplus0.5emma0.5emmb0.5em=0.5emfun0.5ems0.5emp0.5em->0.5em0.5em0.5em0.5em0.5em0.5emMP.mplus0.5em(ma0.5ems0.5emp)0.5em(lazy0.5em(Lazy.force0.5emmb0.5ems0.5emp))0.5em0.5emend0.5em0.5eminclude0.5emM0.5em0.5eminclude0.5emMonadPlusOps(M)0.5em0.5emlet0.5em(<>)0.5emma0.5emmb0.5em=0.5emmplus0.5emma0.5emmb0.5em0.5emlet0.5emrunT0.5emm0.5ems0.5emp0.5em=0.5emMP.lift0.5emfst0.5em(m0.5ems0.5emp)0.5em0.5emlet0.5emsatisfy0.5emf0.5ems0.5emp0.5em=0.5em0.5em0.5em0.5emif0.5emp0.5em<0.5emString.length0.5ems0.5em&&0.5emf0.5ems.[p]Consuming a character means accessing it0.5em0.5em0.5em0.5emthen0.5emMP.return0.5em(s.[p],0.5emp0.5em+0.5em1)0.5emelse0.5emMP.mzeroand advancing the parsing position.0.5em0.5emlet0.5emendoftext0.5ems0.5emp0.5em=0.5em0.5em0.5em0.5emif0.5emp0.5em>=0.5emString.length0.5ems0.5emthen0.5emMP.return0.5em((),0.5emp)0.5emelse0.5emMP.mzeroendmodule0.5emtype0.5emPARSEOPS0.5em=0.5emsig0.5em0.5eminclude0.5emPARSE0.5em0.5emval0.5emmany0.5em:0.5em’a0.5emmonad0.5em->0.5em’a0.5emlist0.5emmonad0.5em0.5emval0.5emopt0.5em:0.5em’a0.5emmonad0.5em->0.5em’a0.5emoption0.5emmonad0.5em0.5emval0.5em(?)0.5em:0.5em’a0.5emmonad0.5em->0.5em’a0.5emoption0.5emmonad0.5em0.5emval0.5emseq0.5em:0.5em’a0.5emmonad0.5em->0.5em’b0.5emmonad0.5emLazy.t0.5em->0.5em(‘a0.5em0.5em’b)0.5emmonadExercise: why laziness here?0.5em0.5emval0.5em(<>)0.5em:0.5em’a0.5emmonad0.5em->0.5em’b0.5emmonad0.5emLazy.t0.5em->0.5em(’a0.5em0.5em’b)0.5emmonadSynonym for seq.0.5em0.5emval0.5emlowercase0.5em:0.5emchar0.5emmonad0.5em0.5emval0.5emuppercase0.5em:0.5emchar0.5emmonad0.5em0.5emval0.5emdigit0.5em:0.5emchar0.5emmonad0.5em0.5emval0.5emalpha0.5em:0.5emchar0.5emmonad0.5em0.5emval0.5emalphanum0.5em:0.5emchar0.5emmonad0.5em0.5emval0.5emliteral0.5em:0.5emstring0.5em->0.5emunit0.5emmonadConsume characters of the given string.0.5em0.5emval0.5em(<<>)0.5em:0.5emstring0.5em->0.5em’a0.5emmonad0.5em->0.5em'a0.5emmonadPrefix and postfix keywords.0.5em0.5emval0.5em(<>>)0.5em:0.5em’a0.5emmonad0.5em->0.5emstring0.5em->0.5em’a0.5emmonadendmodule0.5emParseOps0.5em(R0.5em:0.5emMONADPLUSOPS)0.5em0.5em(P0.5em:0.5emPARSE0.5emwith0.5emtype0.5em’a0.5embacktrackingmonad0.5em:=0.5em’a0.5emR.monad)0.5em:0.5em0.5emPARSEOPS0.5emwith0.5emtype0.5em’a0.5embacktrackingmonad0.5em:=0.5em’a0.5emR.monad0.5em=struct0.5em0.5eminclude0.5emP0.5em0.5emlet0.5emrec0.5emmany0.5emp0.5em=0.5em0.5em0.5em0.5em(perform0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5emr0.5em<–0.5emp;0.5emrs0.5em<–0.5emmany0.5emp;0.5emreturn0.5em(r::rs))0.5em0.5em0.5em0.5em++0.5emlazy0.5em(return0.5em[])0.5em0.5emlet0.5emopt0.5emp0.5em=0.5em(p0.5em>>=0.5em(fun0.5emx0.5em->0.5emreturn0.5em(Some0.5emx)))0.5em++0.5emlazy0.5em(return0.5emNone)0.5em0.5emlet0.5em(?)0.5emp0.5em=0.5emopt0.5emp0.5em0.5emlet0.5emseq0.5emp0.5emq0.5em=0.5emperform0.5em0.5em0.5em0.5em0.5em0.5emx0.5em<–0.5emp;0.5emy0.5em<–0.5emLazy.force0.5emq;0.5emreturn0.5em(x,0.5emy)0.5em0.5emlet0.5em(<>)0.5emp0.5emq0.5em=0.5emseq0.5emp0.5emq0.5em0.5emlet0.5emlowercase0.5em=0.5emsatisfy0.5em(fun0.5emc0.5em->0.5emc0.5em>=0.5em’a’0.5em&&0.5emc0.5em<=0.5em’z’)0.5em0.5emlet0.5emuppercase0.5em=0.5emsatisfy0.5em(fun0.5emc0.5em->0.5emc0.5em>=0.5em’A’0.5em&&0.5emc0.5em<=0.5em’Z’)0.5em0.5emlet0.5emdigit0.5em=0.5emsatisfy0.5em(fun0.5emc0.5em->0.5emc0.5em>=0.5em’0’0.5em&&0.5emc0.5em<=0.5em’9’)0.5em0.5emlet0.5emalpha0.5em=0.5emlowercase0.5em++0.5emlazy0.5emuppercase0.5em0.5emlet0.5emalphanum0.5em=0.5emalpha0.5em++0.5emlazy0.5emdigit0.5em0.5emlet0.5emliteral0.5eml0.5em=0.5em0.5em0.5em0.5emlet0.5emrec0.5emloop0.5empos0.5em=0.5em0.5em0.5em0.5em0.5em0.5emif0.5empos0.5em=0.5emString.length0.5eml0.5emthen0.5emreturn0.5em()0.5em0.5em0.5em0.5em0.5em0.5emelse0.5emsatisfy0.5em(fun0.5emc0.5em->0.5emc0.5em=0.5eml.[pos])0.5em>>-0.5emloop0.5em(pos0.5em+0.5em1)0.5emin0.5em0.5em0.5em0.5emloop0.5em00.5em0.5emlet0.5em(<<>)0.5embra0.5emp0.5em=0.5emliteral0.5embra0.5em>>-0.5emp0.5em0.5emlet0.5em(<>>)0.5emp0.5emket0.5em=0.5emp0.5em>>=0.5em(fun0.5emx0.5em->0.5emliteral0.5emket0.5em>>-0.5emreturn0.5emx)endParser Combinators: Tying the Recursive Knot

    module0.5emParseM0.5em=0.5em0.5emParsec.ParseOps0.5em(Monad.LListM)0.5em(Parsec.ParseT0.5em(Monad.LListM))open0.5emParseMlet0.5emgrammarrules0.5em:0.5em(int0.5emmonad0.5em->0.5emint0.5emmonad)0.5emlist0.5emref0.5em=0.5emref0.5em[]let0.5emgetlanguage0.5em()0.5em:0.5emint0.5emmonad0.5em=0.5em0.5emlet0.5emrec0.5emresult0.5em=0.5em0.5em0.5em0.5emlazy0.5em0.5em0.5em0.5em0.5em0.5em(List.foldleft0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em(fun0.5emacc0.5emlang0.5em->0.5emacc0.5em<>0.5emlazy0.5em(lang0.5em(Lazy.force0.5emresult)))0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5emmzero0.5em!grammarrules)0.5eminEnsure we parse the whole text.0.5em0.5emperform0.5emr0.5em<–0.5emLazy.force0.5emresult;0.5emendoftext;0.5emreturn0.5emrParser Combinators: Dynamic Code Loading

    let0.5emloadplug0.5emfname0.5em:0.5emunit0.5em=0.5em0.5emlet0.5emfname0.5em=0.5emDynlink.adaptfilename0.5emfname0.5emin0.5em0.5emif0.5emSys.fileexists0.5emfname0.5emthen0.5em0.5em0.5em0.5emtry0.5emDynlink.loadfile0.5emfname0.5em0.5em0.5em0.5emwith0.5em0.5em0.5em0.5em0.5em0.5em(Dynlink.Error0.5emerr)0.5emas0.5eme0.5em->0.5em0.5em0.5em0.5em0.5em0.5emPrintf.printf0.5em”0.5emloading0.5emplugin:0.5em%s%!“0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em(Dynlink.errormessage0.5emerr);0.5em0.5em0.5em0.5em0.5em0.5emraise0.5eme0.5em0.5em0.5em0.5em0.5eme0.5em->0.5emPrintf.printf0.5em”0.5emerror0.5emwhile0.5emloading0.5emplugin%!“0.5em0.5emelse0.5em(0.5em0.5em0.5em0.5emPrintf.printf0.5em”0.5emfile0.5em%s0.5emdoes0.5emnot0.5emexist%!“0.5emfname;0.5em0.5em0.5em0.5emexit0.5em(-1))let0.5em()0.5em=0.5em0.5emfor0.5emi0.5em=0.5em20.5emto0.5emArray.length0.5emSys.argv0.5em-0.5em10.5emdo0.5em0.5em0.5em0.5emloadplug0.5emSys.argv.(i)0.5emdone;0.5em0.5emlet0.5emlang0.5em=0.5emPluginBase.getlanguage0.5em()0.5emin0.5em0.5emlet0.5emresult0.5em=0.5em0.5em0.5em0.5emMonad.LListM.run0.5em0.5em0.5em0.5em0.5em0.5em(PluginBase.ParseM.runT0.5emlang0.5emSys.argv.(1)0.5em0)0.5emin0.5em0.5emmatch0.5emMonad.ltake0.5em10.5emresult0.5emwith0.5em0.5em0.5em[]0.5em->0.5emPrintf.printf0.5em”0.5emerror%!“0.5em0.5em0.5emr::0.5em->0.5emPrintf.printf0.5em”:0.5em%d%!“0.5emrParser Combinators: Toy Example

    open0.5emPluginBase.ParseMlet0.5emdigitofchar0.5emd0.5em=0.5emintofchar0.5emd0.5em-0.5emintofchar0.5em’0’let0.5emnumber=0.5em0.5emlet0.5emrec0.5emnum0.5em=Numbers: N := D N | D where D is digits.0.5em0.5em0.5em0.5emlazy0.5em(0.5em0.5em(perform0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5emd0.5em<–0.5emdigit;0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em(n,0.5emb)0.5em<–0.5emLazy.force0.5emnum;0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5em0.5emreturn0.5em(digitofchar0.5emd0.5em0.5emb0.5em+0.5emn,0.5emb0.5em0.5em10))0.5em0.5em0.5em0.5em0.5em0.5em<>0.5emlazy0.5em(digit0.5em>>=0.5em(fun0.5emd0.5em->0.5emreturn0.5em(digitofchar0.5emd,0.5em10))))0.5emin0.5em0.5emLazy.force0.5emnum0.5em>>0.5emfstlet0.5emaddition0.5emlang0.5em=Addition rule: S \rightarrow (S + S).0.5em0.5emperformRequiring a parenthesis ( turns the rule into non-left-recursive.0.5em0.5em0.5em0.5emliteral0.5em”(“;0.5emn10.5em<–0.5emlang;0.5emliteral0.5em”+“;0.5emn20.5em<–0.5emlang;0.5emliteral0.5em”)“;0.5em0.5em0.5em0.5emreturn0.5em(n10.5em+0.5emn2)let0.5em()0.5em= PluginBase.(grammarrules0.5em:=0.5emnumber0.5em::0.5emaddition0.5em::0.5em!grammarrules)

    open0.5emPluginBase.ParseMlet0.5emmultiplication0.5emlang0.5em=0.5em0.5emperformMultiplication rule: S \rightarrow (S \ast S).0.5em0.5em0.5em0.5emliteral0.5em”(“;0.5emn10.5em<–0.5emlang;0.5emliteral0.5em”“;0.5emn20.5em<–0.5emlang;0.5emliteral0.5em”)“;0.5em0.5em0.5em0.5emreturn0.5em(n10.5em0.5emn2)let0.5em()0.5em= PluginBase.(grammarrules0.5em:=0.5emmultiplication0.5em::0.5em!grammarrules)

    Functional ProgrammingŁukasz Stafiniak

    The Expression Problem

    Exercise 1: Implement the string_of_ functions or methods, covering all data cases, corresponding to the eval_ functions in at least two examples from the lecture, including both an object-based example and a variant-based example (either standard, or polymorphic, or extensible variants).

    Exercise 2: Split at least one of the examples from the previous exercise into multiple files and demonstrate separate compilation.

    Exercise 3: Can we drop the tags Lambda_t, Expr_t and LExpr_t used in the examples based on standard variants (file FP_ADT.ml)? When using polymorphic variants, such tags are not needed.

    Exercise 4: Factor-out the sub-language consisting only of variables, thus eliminating the duplication of tags VarL, VarE in the examples based on standard variants (file FP_ADT.ml).

    Exercise 5: Come up with a scenario where the extensible variant types-based solution leads to a non-obvious or hard to locate bug.

    Exercise 6: * Re-implement the direct object-based solution to the expression problem (file Objects.ml) to make it more satisfying. For example, eliminate the need for some of the rename, apply, compute methods.

    Exercise 7: Re-implement the visitor pattern-based solution to the expression problem (file Visitor.ml) in a functional way, i.e. replace the mutable fields subst and beta_redex in the eval_lambda class with a different solution to the problem of treating abs and non-abs expressions differently.

    ** See if you can replace the reference cells result in evalN and freevarsN functions (for N=1,2,3) with a different solution to the problem of polymorphism wrt. the type of the computed values.*

    Exercise 8: Extend the sub-language expr_visit with variables, and add to arguments of the evaluation constructor eval_expr the substitution. Handle the problem of potentially duplicate fields subst. (One approach might be to use ideas from exercise 6.)

    Exercise 9: Impement the following modifications to the example from the file PolyV.ml:

    1. Factor-out the sub-language of variables, around the already present *var* type.
    2. Open the types of functions *eval3*,*freevars3* and other functions as required, so that explicit subtyping, e.g. in eval30.5em[]0.5em(test20.5em:>0.5emlexprt), is not necessary.
    3. Remove the double-dispatch currently in *eval_lexpr* and *freevars_lexpr*, by implementing a cascading design rather than a “divide-and-conquer” design.

    Exercise 10: Streamline the solution PolyRecM.ml by extending the language of \lambda-expressions with arithmetic expressions, rather than defining the sub-languages separately and then merging them. See slide on page 15 of Jacques Garrigue Structural Types, Recursive Modules, and the Expression Problem.

    Exercise 11: Transform a parser monad, or rewrite the parser monad transformer, by adding state for the line and column numbers.

    ** How to implement a monad transformer transformer in OCaml?*

    Exercise 12: Implement _of_string functions as parser combinators on top of the example PolyRecM.ml. Sections 4.3 and 6.2 of Monadic Parser Combinators by Graham Hutton and Erik Meijer might be helpful. Split the result into multiple files as in Exercise 2 and demonstrate dynamic loading of code.

    Exercise 13: What are the benefits and drawbacks of our lazy-monad-plus (built on top of odd lazy lists) approach, as compared to regular monad-plus built on top of even lazy lists? To additionally illustrate your answer:

    1. Rewrite the parser combinators example to use regular monad-plus and even lazy lists.
    2. Select one example from Lecture 8 and rewrite it using lazy-monad-plus and odd lazy lists.

    Exam: Exercises for review

    Exam set 0

    Exercise 1.

    Give types of the following expressions, either by guessing or inferring them by hand:

    1. let double f y = f (f y) in fun g x -> double (g x)
    2. let rec tails l = match l with [] -> [] | x::xs -> xs::tails xs infun l -> List.combine l (tails l)

    Exercise 2.

    Assume that the corresponding expression from previous exercise is bound to name foo. What are the values computed for the expressions (compute in your head or derive on paper):

    1. foo (+) 2 3, foo ( * ) 2 3, foo ( * ) 3 2
    2. foo [1; 2; 3]

    Exercise 3.

    Give example expressions that have the following types (without using type constraints):

    1. (int -> int) -> bool
    2. 'a option -> 'a list

    Exercise 4.

    Write function that returns the list of all lists containing elements from the input list, preserving order from the input list, but without two elements.

    Exercise 5.

    Write a breadth-first-search function that returns an element from a binary tree for which a predicate holds, or None if no such element exists. The function should have signature:

    val bfs : ('a -> bool) -> 'a btree -> 'a option

    Exercise 6.

    Solve the n-queens problem using backtracking based on lists.

    Available functions: from_to, concat_map, concat_foldl, unique.

    Hint functions (asking for hint each loses one point): valid_queens, add_queen, find_queen, find_queens. Final function solve takes n as an argument. Each function, other than valid_queens that takes 3 lines, fits on one line.

    Exercise 7.

    Provide an algebraic specification and an implementation for first-in-first-out queues (lecture 5 exercise 9).

    Exam set 1

    Functional ProgrammingFebruary 5th 2013

    Exam set 1

    Exercise 1: (Blue.) What is the type of the subexpression y as part of the expression below assuming that the whole expression has the type given?

    *(fun double g x -> double (g x)) (fun f y -> f (f
    y

    ))*

    : (’a -> ’b -> ’b) -> ’a -> ’b -> ’b

    Exercise 2: (Blue.) Write an example function with type:

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

    Tell “in your words” what it does.

    Exercise 3: (Green.) Write a function last : 'a list -> 'a option that returns the last element of a list.

    Exercise 4: (Green.) Duplicate the elements of a list.

    Exercise 5: (Yellow.) Drop every N’th element from a list.

    Exercise 6: (Yellow.) Construct completely balanced binary trees of given depth.

    In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

    Write a function cbal_tree to construct completely balanced binary trees for a given number of nodes. The function should generate the list of all solutions (e.g. via backtracking). Put the letter 'x' as information into all nodes of the tree.

    Exercise 7: (White.) Due to Yaron Minsky.

    Consider a datatype to store internet connection information. The time when_initiated marks the start of connecting and is not needed after the connection is established (it is only used to decide whether to give up trying to connect). The ping information is available for established connection but not straight away.

    type connectionstate = | Connecting | Connected | Disconnectedtype connectioninfo = { state : connectionstate; server : Inetaddr.t; lastpingtime : Time.t option; lastpingid : int option; sessionid : string option; wheninitiated : Time.t option; whendisconnected : Time.t option;}

    (The types Time.t and Inetaddr.t come from the library Core* used where Yaron Minsky works. You can replace them with float and Unix.inet_addr. Load the Unix library in the interactive toplevel by #load "unix.cma";;.) Rewrite the type definitions so that the datatype will contain only reasonable combinations of information.*

    Exercise 8: (White.) Design an algebraic specification and write a signature for first-in-first-out queues. Provide two implementations: one straightforward using a list, and another one using two lists: one for freshly added elements providing efficient queueing of new elements, and “reversed” one for efficient popping of old elements.

    Exercise 9: (Orange.) Implement while_do in terms of repeat_until.

    Exercise 10: (Orange.) Implement a map from keys to values (a dictionary) using only functions (without data structures like lists or trees).

    Exercise 11: (Purple.) One way to express constraints on a polymorphic function is to write its type in the form: \forall \alpha _{1} \ldots \alpha _{n} [C] . \tau, where \tau is the type of the function, \alpha _{1} \ldots \alpha _{n} are the polymorphic type variables, and C are additional constraints that the variables \alpha _{1} \ldots \alpha _{n} have to meet. Let’s say we allow “local variables” in C: for example C = \exists \beta . \alpha _{1} \dot{=} \operatorname{list} (\beta). Why the general form \forall \beta [C] . \beta is enough to express all types of the general form \forall \alpha _{1} \ldots \alpha _{n} [C] . \tau?

    Exercise 12: (Purple.) Define a type that corresponds to a set with a googleplex of elements (i.e. 10^{10^{100}} elements).

    Exercise 13: (Red.) In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one. Consider a height-balanced binary tree of height h. What is the maximum number of nodes it can contain? Clearly, \operatorname{maxN}= 2 h - 1. However, finding the minimum number \operatorname{minN} is more difficult.

    Construct all the height-balanced binary trees with a given nuber of nodes. hbal_tree_nodes n returns a list of all height-balanced binary tree with n nodes.

    Find out how many height-balanced trees exist for n = 15.

    Exercise 14: (Crimson.) To construct a Huffman code for symbols with probability/frequency, we can start by building a binary tree as follows. The algorithm uses a priority queue where the node with lowest probability is given highest priority:

    1. Create a leaf node for each symbol and add it to the priority queue.
    2. While there is more than one node in the queue:
      1. Remove the two nodes of highest priority (lowest probability) from the queue.
      2. Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes’ probabilities.
      3. Add the new node to the queue.
    3. The remaining node is the root node and the tree is complete.

    Label each left edge by 0 and right edge by 1. The final binary code assigns the string of bits on the path from root to the symbol as its code.

    We suppose a set of symbols with their frequencies, given as a list of Fr(S,F) terms. Example: fs = [Fr(a,45); Fr(b,13); Fr(c,12); Fr(d,16); Fr(e,9); Fr(f,5)]. Our objective is to construct a list Hc(S,C) terms, where C is the Huffman code word for the symbol S. In our example, the result could be hs = [Hc(a,'0'); Hc(b,'101'); Hc(c,'100'); Hc(d,'111'); Hc(e,'1101'); Hc(f,'1100')] [Hc(a,'01'),…etc.]. The task shall be performed by the function huffman defined as follows: huffman(fs) returns the Huffman code table for the frequency table fs.

    Exercise 15: (Black.) Implement the Gaussian Elimination algorithm for solving linear equations and inverting square invertible matrices.

    Exam set 2

    Functional ProgrammingFebruary 5th 2013

    Exam set 2

    Exercise 1: (Blue.) What is the type of the subexpression f as part of the expression below assuming that the whole expression has the type given?

    *(fun double g x -> double (g x)) (fun f y ->

    (f y))*

    : (’a -> ’b -> ’b) -> ’a -> ’b -> ’b

    Exercise 2: (Blue.) Write an example function with type:

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

    Tell “in your words” what it does.

    Exercise 3: (Green.) Find the number of elements of a list.

    Exercise 4: (Green.) Split a list into two parts; the length of the first part is given.

    Exercise 5: (Yellow.) Rotate a list N places to the left.

    Exercise 6: (Yellow.) Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a function is_symmetric to check whether a given binary tree is symmetric.

    Exercise 7: (White.) By “traverse a tree” we mean: write a function that takes a tree and returns a list of values in the nodes of the tree. Traverse a tree in breadth-first order – first values in more shallow nodes.

    Exercise 8: (White.) Generate all combinations of K distinct elements chosen from the N elements of a list.

    Exercise 9: (Orange.) Implement a topological sort of a graph: write a function that either returns a list of graph nodes in topological order or informs (via exception or option type) that the graph has a cycle.

    Exercise 10: (Orange.) Express fold_left in terms of fold_right. Hint: continuation passing style.

    Exercise 11: (Purple.) Show why for a monomorphic specification, if datastructures d_{1} and d_{2} have the same behavior under all operations, then they have the same representation d_{1} = d_{2} in all implementations.

    Exercise 12: (Purple.) append for lazy lists returns in constant time. Where has its linear-time complexity gone? Explain how you would account for this in a time complexity analysis.

    Exercise 13: (Red.) Write a function ms_tree graph to construct the minimal spanning tree of a given weighted graph. A weighted graph will be represented as follows:

    *type 'a weighted_graph = {nodes : 'a list; edges : ('a * 'a * int) list}*

    The labels identify the nodes 'a uniquely and there is at most one edge between a pair of nodes. A triple (a,b,w) inside edges corresponds to edge between a and b with weight w. The minimal spanning tree is a subset of edges that forms an undirected tree, covers all nodes of the graph, and has the minimal sum of weights.

    Exercise 14: (Crimson.) Von Koch’s conjecture. Given a tree with N nodes (and hence N-1 edges). Find a way to enumerate the nodes from 1 to N and, accordingly, the edges from 1 to N-1 in such a way, that for each edge K the difference of its node numbers equals to K. The conjecture is that this is always possible.

    For small trees the problem is easy to solve by hand. However, for larger trees, and 14 is already very large, it is extremely difficult to find a solution. And remember, we don’t know for sure whether there is always a solution!

    Write a function that calculates a numbering scheme for a given tree. What is the solution for the larger tree pictured above?

    Exercise 15: (Black.) Based on our search engine implementation, write a function that for a list of keywords returns three best “next keyword” suggestions (in some sense of “best”, e.g. occurring in most of documents containing the given words).

    Exam set 3

    Functional ProgrammingFebruary 5th 2013

    Exam set 3

    Exercise 1: (Blue.) What is the type of the subexpression f y as part of the expression below assuming that the whole expression has the type given?

    *(fun double g x -> double (g x)) (fun f y -> f (

    ))*

    : (’a -> ’b -> ’b) -> ’a -> ’b -> ’b

    Exercise 2: (Blue.) Write an example function with type:

    *(int -> int -> bool option) -> bool list*

    Tell “in your words” what it does.

    Exercise 3: (Green.) Find the k’th element of a list.

    Exercise 4: (Green.) Insert an element at a given position into a list.

    Exercise 5: (Yellow.) Group the elements of a set into disjoint subsets. Represent sets as lists, preserve the order of elements. The required sizes of subsets are given as a list of numbers.

    Exercise 6: (Yellow.) A complete binary tree with height H is defined as follows: The levels 1, 2, 3, \ldots, H - 1 contain the maximum number of nodes (i.e 2^{i - 1} at the level i, note that we start counting the levels from 1 at the root). In level H, which may contain less than the maximum possible number of nodes, all the nodes are “left-adjusted”. This means that in a levelorder tree traversal all internal nodes come first, the leaves come second, and empty successors (the nil’s which are not really nodes!) come last.

    We can assign an address number to each node in a complete binary tree by enumerating the nodes in levelorder, starting at the root with number 1. In doing so, we realize that for every node X with address A the following property holds: The address of X’s left and right successors are 2A and 2A+1, respectively, supposed the successors do exist. This fact can be used to elegantly construct a complete binary tree structure. Write a function is_complete_binary_tree with the following specification: is_complete_binary_tree n t returns true iff t is a complete binary tree with n nodes.

    Exercise 7: (White.) Write two sorting algorithms, working on lists: merge sort and quicksort.

    1. Merge sort splits the list roughly in half, sorts the parts, and merges the sorted parts into the sorted result.
    2. Quicksort splits the list into elements smaller/greater than the first element, sorts the parts, and puts them together.

    Exercise 8: (White.) Express in terms of fold_left or fold_right, i.e.  with all recursion contained in the call to one of these functions, run-length encoding of a list (exercise 10 from 99 Problems).

    Exercise 9: (Orange.) Implement Priority Queue module that is an abstract data type for polymorphic queues parameterized by comparison function: the empty queue creation has signature

    val make_empty : leq:('a -> 'a -> bool) -> 'a prio_queue

    Provide only functions: make_empty, add, min, delete_min. Is this data structure “safe”?

    Implement the heap as a heap-ordered tree, i.e. in which the element at each node is no larger than the elements at its children. Unbalanced binary trees are OK.

    Exercise 10: (Orange.) Write a function that transposes a rectangular matrix represented as a list of lists.

    Exercise 11: (Purple.) Find the bijective functions between the types corresponding to a (a^b + c) and a^{b + 1} + ac (in OCaml).

    Exercise 12: (Purple.) Show the monad-plus laws for OptionM monad.

    Exercise 13: (Red.) As a preparation for drawing the tree, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable, one of them is shown in the illustration below.

    In this layout strategy, the position of a node v is obtained by the following two rules:

    In order to store the position of the nodes, we redefine the OCaml type representing a node (and its successors) as follows:

    type 'a pos_binary_tree =
        | E (* represents the empty tree *)
        | N of 'a * int * int * 'a pos_binary_tree * 'a pos_binary_tree

    N(w,x,y,l,r) represents a (non-empty) binary tree with root w “positioned” at (x,y), and subtrees l and r. Write a function layout_binary_tree with the following specification: layout_binary_tree t returns the “positioned” binary tree obtained from the binary tree t.

    An alternative layout method is depicted in the illustration:

    Find out the rules and write the corresponding function.

    Hint: On a given level, the horizontal distance between neighboring nodes is constant.

    Exercise 14: (Crimson.) Nonograms. Each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves the puzzle must complete the bitmap given only these lengths.

              Problem statement:          Solution:
    
              |_|_|_|_|_|_|_|_| 3         |_|X|X|X|_|_|_|_| 3
              |_|_|_|_|_|_|_|_| 2 1       |X|X|_|X|_|_|_|_| 2 1
              |_|_|_|_|_|_|_|_| 3 2       |_|X|X|X|_|_|X|X| 3 2
              |_|_|_|_|_|_|_|_| 2 2       |_|_|X|X|_|_|X|X| 2 2
              |_|_|_|_|_|_|_|_| 6         |_|_|X|X|X|X|X|X| 6
              |_|_|_|_|_|_|_|_| 1 5       |X|_|X|X|X|X|X|_| 1 5
              |_|_|_|_|_|_|_|_| 6         |X|X|X|X|X|X|_|_| 6
              |_|_|_|_|_|_|_|_| 1         |_|_|_|_|X|_|_|_| 1
              |_|_|_|_|_|_|_|_| 2         |_|_|_|X|X|_|_|_| 2
               1 3 1 7 5 3 4 3             1 3 1 7 5 3 4 3
               2 1 5 1                     2 1 5 1

    For the example above, the problem can be stated as the two lists [[3];[2;1];[3;2];[2;2];[6];[1;5];[6];[1];[2]] and [[1;2];[3;1];[1;5];[7;1];[5];[3];[4];[3]] which give the “solid” lengths of the rows and columns, top-to-bottom and left-to-right, respectively. Published puzzles are larger than this example, e.g. 2520, and apparently always have unique solutions.*

    Exercise 15: (Black.) Leftist heaps are heap-ordered binary trees that satisfy the leftist property: the rank of any left child is at least as large as the rank of its right sibling. The rank of a node is defined to be the length of its right spine, i.e. the rightmost path from the node in question to an empty node. Implement O (\log n) worst case time complexity Priority Queues based on leftist heaps. Each node of the tree should contain its rank.

    Note that the elements along any path through a heap-ordered tree are stored in sorted order. The key insight behind leftist heaps is that two heaps can be merged by merging their right spines as you would merge two sorted lists, and then swapping the children of nodes along this path as necessary to restore the leftist property.