Skip to content

AHABHGK

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)