Programming Language

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

1(* Let's SML! *)
2
3val x = 1;
4(* static env: x: int *)
5(* dynamic env: x -> 1 *)
6
7val y = 2;
8(* static env: x: int, y: int *)
9(* dynamic env: x -> 1, y -> 2 *)
10
11val z = (x + 1) * (y + 2);
12(* static env: x: int, y: int, z: int *)
13(* dynamic env: x -> 1, y -> 2, z -> 8 *)
14
15val abs_z = if z < 0 then 0 - z else z; (* bool *) (* int *)
16(* static env: ..., abs_z: int *)
17(* dynamic env: ..., abs_z: 8 *)
18
19val 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 - 5
2val y = ~5
3y = x (* true *)
4
52.0 / 1.0 (* 2.0: real *)
62 div 1 (* 2: int *)

Function

1fun pow(x : int, y : int) =
2  if y = 0
3  then 1
4  else x * pow(x, y - 1)
5(* val pow = fn : int * int -> int *)
6
7fun cube(x) =
8  pow(x, 3)
9(* val cube = fn : int -> int *)
10
11val 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 *)
4
5fun 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 *)
8
9fun div_mod(x : int, y : int) =
10  (x div y, x mod y)
11(* val div_mod = fn : int * int -> int * int *)
12
13fun sort_pair(pr : int * int) =
14  if (#1 pr) < (#2 pr)
15  then pr
16  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 *)
4
5true::[] (* bool list *)
65::[6, 7] (* [5, 6, 7] int list *)
7[1]::[[2, 3], [4, 5]] (* int list list *)
8
9(* val null = fn : 'a list -> bool *)
10null [1, 2] (* false *)
11null [] (* true *)
12
13(* val hd = fn : 'a list -> 'a *)
14hd (tl [1, 2, 3]) (* 2 *)
15
16(* 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 xs
3  then ys
4  else (hd xs) :: append ((tl xs), ys)
5
6fun map (f, xs) =
7  if null xs
8  then []
9  else (f (hd xs)) :: (map (f, (tl xs)))
10
11fun firsts2 (xs : (int * int) list) =
12  map (fn (x) => (#1 x), xs)
13
14fun seconds2 (xs : (int * int) list) =
15  map (fn (x) => (#2 x), xs)