Terminology: Review

Feb 18, 2024
All notes are expanded based on

CPS Transformation

Example

Before:

After: 

let rec add_list lst = 
    match lst with [] -> 0
    | (0::xs) -> add_list xs 
    | (x::xs) -> (+) x (add_list xs)
 
let rec add_listk k = 
    match lst with      (* rule 1 *)
    | [] -> k 0         (* rule 2 *) 
    | (0::xs) -> add_list xs k  (* rule 3 *)
    | (x::xs) -> add_list xs 
                (fun r -> k ((+) x r))
                    (* rule 4 *)

Example 2

Before:

After: 

let rec mem (y, lst) = 
    match lst with [] -> false 
    | (x::xs) -> 
        if x = y then 
            true 
        else 
            mem(y, xs)
 
let rec memk (y, lst) k =
    match lst with      (* rule 1 *)
    | [] -> k false  
    | (x::xs) ->        (* rule 2 *)
        eqk (x, y)
        (fun b -> 
            if b then  (* rule 4 *)
                k true (* rule 2 *)
            else memk (y, xs) k 
            (* rule 3 *))

Data type in Ocaml: lists

Variants - Syntax (slightly simplified)

Enumeartion Types as Variants

An enumeration type is a collection of distinct values

In C and Ocaml they have an order structure; order by order of input

type weekday = Monday | Tuesday | Wednesday | Thursday | Friday 
    | Saturday | Sunday

Functions over Enumerations 

let day_after day = match day with 
    Monday -> Tuesday 
    | Tuesday -> Wednesday
    | Wednesday -> Thursday
    | Thursday -> Friday 
    | Friday -> Saturday
    | Saturday -> Sunday
    | Sunday -> Monday


let rec days_later n day =
    match n with 0 -> day
    | _ -> if n > 0 
            then day_after (days_later (n -1) day)
            else days_later (n + 7) day
# days_later 2 Tuesday;;
- : weekday = Thursday
# days_later (-1) Wednesday;;
- : weekday = Tuesday
# days_later (-4) Monday;;
- : weekday = Thursday

Problem:

Write a function \(\textcolor{blue}{\text{is\_weekend : weekday bool}}\)

let is_weekend day =
    match day with 
    Saturday -> true
    | Sunday -> true
    | _ -> false

Example Enumeration Types 

type bin_op = IntPlusOp | IntMinusOp
        | EqOp | CommaOp | ConsOp

type mon_op = HdOp | TlOp | FstOp
        | SndOp

Explanantion of \(\textcolor{blue}{\text{bin\_op type}}\)

We create a type name bin_op (short for binary operator), which can take one of the following five values:

Explanantion of \(\textcolor{blue}{\text{mon\_op type}}\)

We create a type name mon_op (short for monadic or unary operator), which can take one of the following five values:

Disjoint Union Types

Disjoint union types, with some possibly occurring more than once

We can also add in some new singleton elements

type id = DriversLicense of int 
    | SocialSecurity of int | Name of string

let check_id id = match id with 
    DriversLicense num -> 
        not (List.mem num[13570; 99999])
        | SocialSecurity num -> num < 900000000
        | Name str -> not (str = "John Doe")

Problem:

Create a type to represent the currencies for US, UK, Europe and Japan

type currency = 
    Dollar of int 
    | Pound of int 
    | Euro of int
    | Yen of int

Example Disjoint Union Type 

type const = 
    BoolConst of bool
    | IntConst of int 
    | FloatConst of float 
    | StringConst of float
    | NilConst 
    | UnitConst

type const = BoolConst of bool
    | IntConst of int | FloatConst of float 
    | StringConst of string | NilConst
    | UnitConst

Polymorphism in Variants 

type `a option = Some of `a | None

Functions producing option 

# let rec first p list = 
    match list with [] -> None 
    | (x::xs) -> if p x then Some x else first p xs
val first : (`a -> bool) -> `a lost -> a` option = <fun>

# first (fun x -> x > 3) [1;3;4;2;5];;
- : int option = Some 4
# first (fun x -> x > 5) [1;3;4;2;5];;
- : int option = None

Functions over option 

# let result_ok r = 
    match r with None -> false
    | Some _ -> true;;
val result_ok : `a option -> bool = <fun>
# result_ok (first (fun x -> x > 3) [1;3;4;2;5]);;
- : bool = true
# result_ok (first (fun x -> x > 5) [1;3;4;2;5]);;
- : bool = false

Problem: 

let hd list = 
    match list with [] -> None
    | (x::xs) -> Some x

let tl list = 
    match list with [] -> none
    | (x::xs) -> Some xs

Mapping over Variants 

# let optionMap f opt = 
    match opt with None -> None
    | Some x -> Some (f x)
val optionMap : (`a -> `b) -> `a option -> `b
    option = <fun>
# optionMap (fun x -> x - 2)
    (first (fun x -> x > 3) [1;3;4;2;5]);;
- : int option = Some 2

Folding over Variants 

# let optionFold someFun noneVal opt = 
    match opt with None -> noneVal
    | Some x -> someFun x;;
val optionFold : (`a -> `b) -> `b -> `a option -> 
    `b = <fun>
# let optionMap f opt = 
    optionFold (fun x -> Some(f x)) None opt;;
val optionMap : (`b -> `b) -> `a option -> `b 
    option = <fun>

Recursive Types

Recursive Data Types 

type int_Bin_Tree = 
    Leaf of int | Node of (int_Bin_Tree * int_Bin_Tree)

Recursive Data Types Values 

let bin_tree = 
    Node(Node(Leaf 3, Leaf 6), Leaf(-7))

Recursive Functions 

let rec first_leaf_value tree = 
    match tree with (Leaf n) -> n
    | Node (left_tree, right_tree) -> 
    first_leaf_value left_tree

# let left = first_leaf_value bin_tree
val left : int = 3

Recursive Data Types 

type exp = 
    VarExp of string
    | ConstExp of const
    | MonOpAppExp of mon_op * exp
    | BinOpAppExp of bin_op * exo * exp 
    | IfExp of exp * exp * exp 
    | AppExp of exp * exp 
    | FunExp of string * exp
# type bin_op = IntPlusOp | IntMinusOp | EqOp | CommaOp 
    | ConsOp | ...

# type const = BoolConst of bool | IntConst of int |
...

# type exp = VarExp of string | ConstExp of const | 
    BinOpAppExp of bin_op * exp * exp | ...

Problem 

type int_Bin_Tree = Leaf of int 
    | Node of (int_Bin_Tree * int_Bin_Tree)
let rec sum_tree t = 
    match t with Leaf n -> n
    | Node(t1, t2) -> sum_tree t1 + sum_tree t2
let rec varCnt exp = 
    match exp with VarExp x -> 1
    | ConstExp c -> 0 
    | BinOpAppExp (b, e1, e2) ->  varCnt e1 + varCnt e2
    | FunExp (x, e) -> 1 + varCnt e
    | AppExp (e1, e2) ->  varCnt e1 + varCnt e2

Mapping over Recursive Types 

let rec ibtreeMap f tree = 
    match tree with (Leaf n) -> Leaf (f n)
    | Node (left_tree, right_tree) -> 
    Node (ibtreeMap f left_tree, ibtreeMap f right_tree)

# ibtreeMap ((+) 2) bin_tree;;
- : int_Bin_Tree = Node (Node (Leaf 5, Leaf 8), Leaf(-5))

Folding over Recursive Types 

# let rec ibtreeFoldRight leafFun nodeFun tree = 
    match tree with Leaf n -> leafFun n
    | Node (left_tree, right_tree) -> 
    nodeFun 
    (ibtreeFoldRight leafFun nodeFun left_tree)
    (ibtreeFoldRight leafFun nodeFun right_tree);;
val ibtreeFoldRight : (int -> `a) -> (`a -> `a -> `a) -> 
    int_Bin_Tree -> `a = <fun>

# let tree_sum = 
    ibtreeFoldRight (fun x -> x) (+);;
val tree_sum : int_Bin_Tree -> int = <fun>
# tree_sum bin_tree;;
- : int = 2

Mutually Recursive Types 

type `a tree = TreeLeaf of `a 
    | TreeNode of `a treeList 
and a` treeList = Last of `a tree
    | More of (`a tree * `a treeList);;
type `a tree = TreeLeaf of `a | TreeNode of `a
    treeList
and `a treeList = Last of `a tree | More of (`a 
    tree * `a treeList)

Mutually Recursive Types - Values 

let tree = 
    TreeNode
    (More (TreeLeaf 5, 
        More(TreeNode 
            More(TreeLeaf 3, 
                Last(TreeLeaf 2))),
            Last (TreeLeaf 7)))

A more conventional picture

Mutually Recursive Functions 

# let rec fringe tree = 
    match tree with (TreeLeaf x) -> [x]
    |(TreeNode list) -> list_fringe list
and list_fringe tree_list = 
    match tree_list with (Last tree) -> fringe tree 
    | (More (tree, list)) -> 
        (fringe tree) @ (list_fringe list);;

val fringe : `a tree -> `a list = <fun> 
val list_fringe : `a treeList -> `a list = <fun> 

# fringe tree;;
- : int list = [5; 3; 2; 7]

Problem 

# type `a tree = TreeLeaf of `a | TreeNode of `a a treeList 
and `a treeList = Last of `a tree | More of (`a tree * `a treeList);;

\(\textcolor{blue}{\text{Define tree\_size}}\)

let rec tree_size t = 
    match t with TreeLeaf _ -> 1
    | TreeNode ts -> treeList_size ts
and treeList_size ts = 
    match ts with Last t -> 
    | More t ts` -> tree_size t + treeList_size ts`

Nested Recursive Types 

type `a labeled_tree =    
    TreeNode of (`a * `a labeled_tree list)

let ltree = 
    TreeNode(5, 
    [TreeNode (3, []);
    TreeNode (2, [TreeNode (1, []);
            TreeNode (7, [])]);
    TreeNode (5, [])])