(* Programming language concepts, seminar 1, 2002-02-04 *)
(* The meta language Standard ML, a crash course *)


(* SML arithmetic expressions, the int type *)

3+4;


(* SML variables and binding *)

val res = 3+4;

res;


(* SML arithmetic expressions, the real type *)

Math.sqrt 2.0;


(* SML logical expressions, the bool type *)

3 < 4;

val res = 3 < 4;


(* SML conditional expressions *)

if 3 < 4 then 117 else 118;


(* SML string expressions *)

val title = "Professor";
val name = "Lauesen";
val junkmail = "Dear " ^ title ^ " " ^ name ^ ", You have won $$$!";
val n = size junkmail;
val junkmail2 = 
    String.concat["Dear ", title, " ", name, ", You have won $$$!"];

(* SML: limiting the scope of a binding *)

val x = 5;

let 
    val x = 3 < 4
in 
    if x then 117 else 118 
end;

x;                                   (* outer x still has the value 5 *)


local val x = 3 < 4                  (* a new x is declared *)
in 
    val z = if x then 117 else 118 
end;

x;                                   (* outer x still has the value 5 *)


(* SML function declarations *)

fun circleArea r = Math.pi * r * r;

val a = circleArea 10.0;

fun double x = 2.0 * x;

double 3.5;

fun junkmail title name = 
    "Dear " ^ title ^ " " ^ name ^ ", You have won $$$!"; 

fun junkmail title name = 
    String.concat["Dear ", title, " ", name, ", You have won $$$!"];


(* SML recursive function declarations *)

fun fac n = if n=0 then 1 else n * fac(n-1);

fac 7; 


(* SML pattern matching *)

fun fac 0 = 1
  | fac n = n * fac(n-1);

fac 7;


(* SML case expressions *)

fun fac n = 
    case n of 
       0 => 1
     | _ => n * fac(n-1);

fac 7;


(* SML pairs and tuples, product types *)

val w = (2, true, 3.4, "blah");

fun add (x, y) = x + y;
add (2, 3);

val noon = (12, 0);
val talk = (15, 15);

fun earlier ((h1, m1), (h2, m2)) = 
    h1<h2 orelse (h1=h2 andalso m1<m2)


(* SML lists of integers *)

val x1 = 7 :: 9 :: 13 :: [];
val x2 = [7, 9, 13];

val equal = (x1 = x2);

fun sum []      = 0
  | sum (x::xr) = x + sum xr;

fun prod []      = 1
  | prod (x::xr) = x * prod xr;

fun len []      = 0
  | len (x::xr) = 1 + len xr;

val x2sum = sum x2;
val x2prod = prod x2;
val x2len = len x2;

val x3 = [47, 11];

val x1x3 = x1 @ x3;

fun rev []      = []					(* inefficient *)
  | rev (x::xr) = rev xr @ [x];

val x1r = rev x1;

local 
    fun irev []      res = res				(* efficient *)
      | irev (x::xr) res = irev xr (x :: res)
in
    fun rev xs = irev xs []
end;

rev x1;


(* SML exceptions *)

exception IllegalHour

fun mins h = 
    if h < 0 orelse h > 23 then raise IllegalHour
    else h * 60;


(* SML datatypes *)

datatype person =
    Student of string			(* name              *)
  | Teacher of string * int		(* name and phone no *)

val people = [Student "Niels Jørgen", Teacher("Peter", 831)];

fun getphone (Teacher(name, phone)) = phone
  | getphone (Student name)         = raise Fail "no phone";


(* The option datatype *)

datatype intopt = 
    SOME of int
  | NONE

fun getphone (Teacher(name, phone)) = SOME phone
  | getphone (Student name)         = NONE;


(* Representing binary trees using recursive datatypes *)

datatype inttree =
    Lf 
  | Br of int * inttree * inttree;

val t1 = Br(34, Br(23, Lf, Lf), Br(54, Lf, Br(78, Lf, Lf)));

fun sumtree Lf              = 0
  | sumtree (Br(v, t1, t2)) = v + sumtree t1 + sumtree t2;

val t1sum = sumtree t1;


(* Representing object language expressions using recursive datatypes *)

datatype expr = 
    CstI of int
  | Prim of string * expr list

val e1 = CstI 17;

val e2 = Prim("+", [CstI 3, CstI 4]);

val e3 = Prim("+", [Prim("*", [CstI 7, CstI 9]), CstI 10]);


(* Evaluating expressions using recursive functions *)

fun eval (e : expr) : int =
    case e of 
        CstI i => i
      | Prim("+", [e1, e2]) => eval e1 + eval e2
      | Prim("*", [e1, e2]) => eval e1 * eval e2
      | Prim("-", [e1, e2]) => eval e1 - eval e2
      | Prim _              => raise Fail "unknown primitive";

val e1v = eval e1;
val e2v = eval e2;
val e3v = eval e3;


(* Changing the meaning of subtraction *)

fun eval (e : expr) : int =
    case e of 
	CstI i => i
      | Prim("+", [e1, e2]) => eval e1 + eval e2
      | Prim("*", [e1, e2]) => eval e1 * eval e2
      | Prim("-", [e1, e2]) => 
	    let val res = eval e1 - eval e2
	    in if res < 0 then 0 else res end
      | Prim _              => raise Fail "unknown primitive";

val e4v = eval (Prim("-", [CstI 10, CstI 27]));


(* Association lists map object language variables to their values *)

val env = [("a", 3), ("c", 78), ("baf", 666), ("b", 111)];

val emptyenv = []; (* the empty environment *)

fun lookup []          x = raise Fail (x ^ " not found")
  | lookup ((y, v)::r) x = if x=y then v else lookup r x;

lookup env "c";


(* Object language expressions with variables *)

datatype expr = 
    CstI of int
  | Var of string
  | Prim of string * expr list

val e1 = CstI 17;

val e2 = Prim("+", [CstI 3, Var "a"]);

val e3 = Prim("+", [Prim("*", [Var "b", CstI 9]), Var "a"]);


(* Evaluation within an environment *)

fun eval e (env : (string * int) list) : int =
    case e of 
	CstI i => i
      | Var x  => lookup env x 
      | Prim("+", [e1, e2]) => eval e1 env + eval e2 env
      | Prim("*", [e1, e2]) => eval e1 env * eval e2 env
      | Prim("-", [e1, e2]) => eval e1 env - eval e2 env
      | Prim _              => raise Fail "unknown primitive"

val e1v  = eval e1 env;
val e2v1 = eval e2 env;
val e2v2 = eval e2 [("a", 314)];
val e3v  = eval e3 env;


(* Object language expressions with variable bindings and nested scope *)

datatype expr = 
    CstI of int
  | Var of string
  | Let of string * expr * expr
  | Prim of string * expr list

val e1 = Let("z", CstI 17, Prim("+", [Var "z", Var "z"]));

val e2 = Let("z", CstI 17, 
	     Prim("+", [Let("z", CstI 22, Prim("*", [CstI 100, Var "z"])),
			Var "z"]));

fun eval e (env : (string * int) list) : int =
    case e of 
	CstI i => i
      | Var x  => lookup env x 
      | Let(x, erhs, ebody) => 
	    let val xval  = eval erhs env
		val env1 = (x, xval) :: env 
	    in eval ebody env1 end
      | Prim("+", [e1, e2]) => eval e1 env + eval e2 env
      | Prim("*", [e1, e2]) => eval e1 env * eval e2 env
      | Prim("-", [e1, e2]) => eval e1 env - eval e2 env
      | Prim _              => raise Fail "unknown primitive"

val e1v = eval e1 emptyenv;

val e2v = eval e2 emptyenv;