# AHABHGK

## Unit 1: ML Functions, Tuples, Lists, and More

1(* Let's SML! *)23val x = 1;4(* static env: x: int *)5(* dynamic env: x -> 1 *)67val y = 2;8(* static env: x: int, y: int *)9(* dynamic env: x -> 1, y -> 2 *)1011val z = (x + 1) * (y + 2);12(* static env: x: int, y: int, z: int *)13(* dynamic env: x -> 1, y -> 2, z -> 8 *)1415val abs_z = if z < 0 then 0 - z else z; (* bool *) (* int *)16(* static env: ..., abs_z: int *)17(* dynamic env: ..., abs_z: 8 *)1819val abs_z_simpler = abs z;

Semantics

• Syntax is just how you write something
• Semantics is what that something means
• Type-checking (before program runs)
• Evaluation (as program runs)
• For variable bindings:
• Type-check expression and extend static environment
• Evaluate expression and extend dynamic environment

Expression

• Syntax
• Type-checking rules
• Produces a type or fails (with a bad error message)
• Types so far: int bool unit
• Evaluation rules (used only on things that type-check)
• Produces a value (or exception or infinite-loop)

Variables

• Syntax:
• sequence of letters, digits, _, not starting with digit
• Type-checking:
• Look up type in current static environment
• If not there fail
• Evaluation:
• Look up value in current dynamic environment

Less-than

• Syntax:
• e1 + e2 where e1 and e2 are expressions
• Type-checking:
• If e1 and e2 have type int, then e1 + e2 has type int
• Evaluation:
• If e1 evaluates to v1 and e2 evaluates to v2, then e1 + e2 evaluates to sum of v1 and v2

Conditional

• Syntax:
• if e1 then e2 else e3. e1, e2 and e3 are expressions
• Type-checking:
• e1 must have type bool, e2 and e3 have type T, the type of entire expression is also T
• Evaluation:
• evaluate e1 to a value call it v1, if v1 is true, then evaluate e2 and that result is the whole expression's result, else evaluate e3 and that result is the whole exporession's result
1val x = 0 - 52val y = ~53y = x (* true *)452.0 / 1.0 (* 2.0: real *)62 div 1 (* 2: int *)

Function

1fun pow(x : int, y : int) =2  if y = 03  then 14  else x * pow(x, y - 1)5(* val pow = fn : int * int -> int *)67fun cube(x) =8  pow(x, 3)9(* val cube = fn : int -> int *)1011val x = pow(3, 4)12val y = cube(3)

Pair

1fun swap(pr : int * bool) =2  (#2 pr, #1 pr)3(* val swap = fn : int * bool -> bool * int *)45fun sum_two_pairs(pr1: int * int, pr2 : int * int) =6  (#1 pr1) + (#2 pr1) + (#1 pr2) + (#2 pr2)7(* val sum_two_pair = fn : (int * int) * (int * int) -> int *)89fun div_mod(x : int, y : int) =10  (x div y, x mod y)11(* val div_mod = fn : int * int -> int * int *)1213fun sort_pair(pr : int * int) =14  if (#1 pr) < (#2 pr)15  then pr16  else (#2 pr, #1 pr)

Tuples: fixed "number of pieces" that may have different types

1val x = (7, (true, 9), (1, 2, 3)) (* int * (bool * int) * (int * int * int) *)2val y = #1 (#2 x) (* bool *)3val z = #3 x (* int * int * int *)

Lists: have any number of elements, all list elements have the same type

• null e evaluates to true if and only if e evaluates to []
• if e evaluates to [v1, v2, ..., vn] then hd e evaluates to v1 (raise exception if e evaluates to [])
• if e evaluates to [v1, v2, ..., vn] then tl e evaluates to [v2, ..., vn] (raise exception if e evaluates to [])
1[] (* 'a list (type a list) *)2[1, 2, 3] (* int list *)3[true, false, false] (* bool list *)45true::[] (* bool list *)65::[6, 7] (* [5, 6, 7] int list *)7[1]::[[2, 3], [4, 5]] (* int list list *)89(* val null = fn : 'a list -> bool *)10null [1, 2] (* false *)11null [] (* true *)1213(* val hd = fn : 'a list -> 'a *)14hd (tl [1, 2, 3]) (* 2 *)1516(* val hd = fn : 'a list -> 'a list *)17tl (tl (tl [1, 2, 3])) (* [] *)18tl (tl (tl (tl [1, 2, 3]))) (* error! *)
1fun append (xs, ys) =2  if null xs3  then ys4  else (hd xs) :: append ((tl xs), ys)56fun map (f, xs) =7  if null xs8  then []9  else (f (hd xs)) :: (map (f, (tl xs)))1011fun firsts2 (xs : (int * int) list) =12  map (fn (x) => (#1 x), xs)1314fun seconds2 (xs : (int * int) list) =15  map (fn (x) => (#2 x), xs)