Programming Language
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]
thenhd e
evaluates tov1
(raise exception if e evaluates to[]
) - if e evaluates to
[v1, v2, ..., vn]
thentl 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)