Notes about Coursera "Programming Languages": https://www.coursera.org/course/proglang - part 1 (ML)

proglang.sml

Programming languages

(* Emacs tips :
  open file: ctr-c ctr-f
  copy: M-w, paste: ctr+y
  save file: ctr+x ctr+s,
  next/previous buffer: ctr+x left/right:
  start REPL: ctr+c ctr+s sml, stop REPL: ctr+c ctr+d 
  stop command interpreter: ctr-g 
  split window vertically: C-x 2
  undo: C-x u
  search: M-s w
*)
 
Week 1:

 Intro:
(
 Learn essential functional programming concepts through 3 "simple" vehicles languages (SML, Racket and Ruby) 
 Goal: be a better programmer

 ML Variable Bindings and Expressions:
 new mindset (forget about Java, Python, etc...)
 first ML program:
  (* comment for first program *)
  val x = 34; (* integer variable ; a binding *)
  (* val a = x + y;  (* is not OK because y is not bound yet *) *) 
  val y = 17;
  val z = x + y; (* OK because earlier binding and because types are OK *)
  val abs_of_z = if z < 0 then 0 - z else z;
  val abs_of_z_simpler = abs z (* call built-in function *)
  
  variable binding syntax: val v = e;
  static environment: type checks (before program runs)
  dynamic environment: evaluation  
)
 
 Rules for Expressions:
(
 expression examples: 34, true, x, x + y, etc... 
 
 1. syntax:
   sequence of letters, digits, 8, not starting with digits
 2. type-check rules:
   look up in current static environment and fail if not here
 3. evaluation rules:
  look up in dynamic environment

  value:
    expression that evaluates to itself

  examples:
    values:
      42 (*type: int *), true (*type: bool *), () (*type: unit *))
    if-then-else:
    "if e1 then e2 else e3" is an expression that contains
        keywords: if, then, else
        sub-expressions: e1 (type: bool), e2 (type T), e3 (type T)
        eval rules: 1) eval e1 to v1  2) if v1 is true evaluate e2 else evaluate e3
)

 The REPL and Errors:
(
 REPL usage: "use "file.sml";"
 Advice: always restart session before loading a file (in emacs : CTRL D then CTRL S) / do not load file twice!

 Shadowing:
 A variable can have several bindings (even if it can be confusing)
 REPL displays "hidden-value" for shadowed values
 ML has no assignent, only shadowed variables
 
 Examples:
 val a = 10
 val b = 20
 val a = 5 (* this is not an assignment, 'a' is shadowed: it has a different binding for next lines *)
 val c = b (* 20, not 5 *)

 val x = y (* type check error: y is not bound, yet)
 val y = 2
)

 Functions Informally:
(
 new kind of binding: function
 function can call themselves (recursion) or call earlier defined functions, but not later functions

  example:
   val x = 7

   fun pow(x : int, y : int) =
    if y = 0
    then 1
    else x * pow(x,y-1)  (* look 'ma, recursivity! *)

   fun cube(x : int) =
    pow(x,3) (* it's OK, functions can use earlier functions, but not later ones *)

   val sixtfour = cube 4
   val v = pow(4, 5)

  REPL displays function signature (example : "fun pow = fn int * int -> int")
)

 Functions formally:
(
 1. function binding (i.e. defining a function):
  - syntax:
    fun x0 (x1 : t1, ..., xn : tn) = e
     x0 = name of the function
     x1..xn = arguments
     e = expression (function body)

   - evaluation:
    a function is a value that is only evaluated when called

   - type-checking:
    adds binding x0 : (t1 * ... * tn) -> t if
     - "enclosing" static environment (earlier bindings)
     - arguments with types type check
     - return type t type check

     2. function calls:
       - syntax: e0 (e1, ..., en)
         parentheses are optional if 1 arg
         functions cannot take variables numbers of arguments 

       - evaluation:
         1. evaluate e0 to know which function has to be called
         2. evaluate all arguments
         3. evaluate the function body => extend dynamic environment, adding bindings for arguments and for itself (if recursion)

       -  type-checking:
         right number of args 
         args' type match
)

 Pairs and Other Tuples:
(
 tuple = fixed number of data items with different types

 2-tuples, aka pairs:
   a) build
  - syntax:(e1, e2)
  - evaluation: result is (v1, v2) 
  - type-checking: new king of type: ta * tb
    (e1 has type ta and e2 has type tb)

    b) access
    - syntax: #1 e and #2 e
    - evaluation: return first or second item
    - type-checking: #1 e has type ta, #2 e has type tb

    examples:
      fun div_mod (x : int, y : int) = (x div y, x mod y)
      fun sort_pair (pr : int * int) = if (#1 pr) < (#2 pr) then pr else (#2 pr, #1 pr)

    Tuples:
      same thing, generalized
      tuples can be nested
)

 Introducing Lists:
(
  a list has any number of elements of the same type
  1. build:
    empty list: []
    list of values: [v1, v2, ..., vn]
    from other list: v1 :: vList (* "cons", adding e1 at the beginning of vList *) 
  2. accessing:
   accessing missing element raises a runtime exception (ex : hd []) 
   before learning pattern-matching, we need 3 standard-library functions 
     null e (* true if list is empty, otherwise false *)
     hd e (* head of a list *)
     tl e (* tail of a list *)
  type-checking:
    new type for lists: "t list"
    [] has type "alpha list" (displayed 'a list in REPL), which means any type
    list operations (head, cons, tail, etc...) use 'a list as parameter 
    null is a function "fn : 'a list -> bool"
)

 List Functions:
(
  functions that take lists as arguments
  They are usually recursive

  fun sum_list(xs: int list) =
    if null xs
    then 0
    else hd xs + sum_list(tl xs)
)

 Let Expressions:
(
 local variables aka local bindings
 let expressions introduce local scope

 syntax:
   let b1 b2 ... bn in e end
     given bindings b1, b2, ... bn
       expression e is the body
  type-checking:
    bn are in static env
  evaluation:
    evaluate each binding in order then e
    result = evaluation of e

  examples:
    fun silly (z: int) =
      let
         val x= if z > 0 then z else 42
         val y = x + z +5
       in
         if x > y then x * 2 else y * 
       end
)
 
 Nested Functions:
(
  nested functions, bound via "let", are great to define private helper functions
  unnecessary parameters are bad style
  example:
    (* [1, 2, 3, ... x] *)
    fun countup_from1(tox: int) =
      let 
        (* "private" helper function *)
        fun count (from : int) =
          if from = tox
          then tox::[]
          else from :: count(from+1, tox)
      in
        count(1,tox)
      end
    design trade-off:
      reusing code saves effort / avoid bugs
       vs
      reused code is harder to change later
)

 Let and Efficiency:
(
  let expressions is a natural way to avoid repeated computation
  
  example:
    fun bad_max (xs : int list) =
      if null xs
      then 0
      else if null (tl xs)
      then hd xs
      else if hd xs > bad_max(tl xs)
      then hd xs
      else bad_max(tl xs)    (* Oops, bad_max called twice => exponential issue *)

    fun good_max (xs : int list) =
      if null xs
      then 0
      else if null (tl xs)
      then hd xs
      else
        let val tl_ans = good_max(tl xs)
        in 
          if hd xs > tl_ans 
          then hd xs
          else tl_ans
)

 Options:
(
  motivation =
    avoiding returning values for "not a value" such as null or -1
    return one value or none (similar to lists)
  t option is a type for any type t
  building:
    NONE (* has type 'a option *)
    SOME e  (* e has type t *)
  accessing:
    isSome (* has type 'a option -> bool *)
    valOf (* has type 'a option -> 'a (exception if given NONE) *)
  example:
    (* fn : int list -> int option  *)
    fun better_max (xs : int list) =
      if null xs
      then NONE
      else
        let val tl_ans = better_max(tl xs)
        in 
          if isSome tl_ans andalso valOf tl_ans > hd xs  
          then tl_ans
          else SOME (hd xs)
        end
    (* fn : int list -> int option  *)
    fun even_better_max (xs : int list) =
      if null xs
      then NONE
      else let 
        (* fn : int list -> int *)
        fun max_nonempty (xs : int list) =
          if null (tl xs)  
          then hd xs
          else let val tl_ans = max_nonempty(tl xs)
                  in
                    if hd xs > tl_ans
                    then hd xs
                    else tl_ans
                  end
        in
          SOME (max_nonempty xs)
        end
)

 Booleans and Comparison Operations:
(
  boolean operations:
    e1 andAlso e2    (* e2 is only evaluated if e1 is true *)
    e1 orElse e2        (* idem *)
    not e1
    
    "andAlso" and "orElse" are keywords, not functions
    "not" is a built-in function
    All three can be written with if-then-else
    comparisons:
      = <> > < >= <=
       3 > 1 (* true *)
       3.0 > 1 (* error! *)
       3.0 > Real.fromInt 1 (* OK *)
       1 = 1 (* true *)
       1 <> 1 (* false *)
       1.0 = 1.0 (* error *)
)

 Benefits of No Mutation:
(
  ML does not have mutation
  => no need to copy function input (it can be returned directly, for example in list sort)
  => saves space (cf. appending 2 lists)
  In ML, we can't tell where there is aliasing (we don't know if returned data is a copy or not)
  => we focus on algorithms (do not worry about copies /equality / identity)
)

 Optional: Java Mutation:
(
  
 Java security nightmare: 
      public String[] getAllowedUsers() // security issue if returned arrays is not a copy
  If code is immutable, reference (alias) vs copy doesn't matter 
)

 Pieces of a Language:
(
  5 things
    - syntax
    - semantics (e.g. evaluation rules)
    - idioms (typical patterns, e.g. nested functions)
    - libraries
    - tools (e.g. REPL, debugger, code formatter...)
  This course focuses on semantics and idioms.
)

Week 2:

 Building Compound Types:
(
    How to build new types?

  2 kinds of types:
      - base types (int, bool, etc...)
      - compound (or nested) types (tuple, list, option...)

  all languages (nearly) have 3 ways to build types:
      - "each of" (e.g. tuple: int * bool has an int AND a bool)
      - "one of" (e.g. option: int option has an int OR no data)
      - "self reference", notion of recursion (e.g. list: int list contains AND int and another int list OR no data)

  next:
      another "each-of" type: records
      use our one-of types via pattern matching
      how OOP does "one-of" types
)

Records:
(
    "each-of" type

    examples:
      val dummyRecord = { bar=(1+3,true andalso true), foo=3+4, baz=(false,9) }.
      (* evaluation in REPL:
       {bar=int * bool, baz=bool * int, foo: int} *)

      val student = { name="Robert", id=1234 }
      #id student (* 1234 *)

    def:
      Record values have unordered and named fields holding values { f1=v1, f2=v2, fn=vn } with types { f1:t1, ..., fn:tn }
        (REPL sorts fields alphabetically)
      build: { f1:v1, f2:v2, ..., fn:vn}
      accessing field values: #fieldname e

    record vs tuple:
      tuple: fields by position, shorter to type
      records: fields by name, easier to remember, specially if numerous fields
)

 Tuples as Syntactic Sugar:
(
 Tuples are records: { 2="bar", 1="foo" } = ("foo", "bar")
   Tuples are just syntactic sugar for records

 Datatype Bindings:
   how to build our "one-of" types? Via 3rd type of binding: datatype binding, aka tagged unions

   example:
     datatype mytype = TwoInts of int * int
                     | Str of string
                     | Pizza
   (* 1. creates type 'mytype' *)
   (* 2. creates 3 constructors (functions):
       TwoInts : int * int-> mytype
       Str : string -> mytype
       Pizza -> mytype *)

   using data type value: 1. check the variant aka tag (eg. TwoInts, Str, Pizza) 2. extract the data 
)

 Case Expressions:
(
   used for accessing "one-of" values
   less powerful that pattern matching

   example:
     fun f x = (* f has type: mytype -> int *)
       case x of 
         Pizza => 3
       | TwoInts(i1,i2) => i1+i2
       | Str s => String.size s

   syntax:
     case e0 of
       p1 => e1
     | p2 => e2
       ...
     | pn => en

       p1, p2... pn are patterns
       Patterns are not expressions: they are not evaluated
       in patterns, variable names must be different

   advantages:
     cannot forget a case (compile warning + runtime error)
     cannot duplicate a case (compile error)
     cannot forget to check variant
     see pattern matching for generalization of case expressions
)

 Useful Datatypes:
(
   enumerations:
     datatype suit = Club | Diamond | Heart | Spade (* enum without data *)
     datatype rank = Jack | Queen | King | Ace | Num of int (* enum with data *)
   
   alternate identifiers:
     datatype id = StudentNum of int | Name of string * (string option) * string
   
   expression trees:
      datatype exp = Constant of int
                  | Negate of exp
                  | Add of exp * exp
                  | Multiply of exp * exp
      fun eval e =
        case e of 
          Constant i       => i
        | Negate e2        => ~ (eval e2)
        | Add(e1,e2)       => (eval e1) + (eval e2)
        | Multiply(e1,e2)  => (eval e1) * (eval e2)
)

 Pattern Matching So Far:
(
   datatype syntax:
     datatype t = C1 of t1 : C2 of t2 | ... | Cn of tn
       C1, C2, ..., Cn: constructors of type t1, t2, ..., tn
       Ci v: a value
       omit "of ti" if no underlying data (cf. enumerations)

   case expression syntax:
     case e of p1 => e1 | p2 => e2 | ... | pn => en

   Case expressions is used on expressions of type t for
     - checking variant
     - extracting underlying data

   Evaluation rules:
     evaluate e to value v
     patterns are evaluated in order (code)
     if pi is the first pattern to match v, then result is evaluation of ei
)

 Another Expression Example:
(
  datatype exp = Constant of int
                | Negate of exp
                | Add of exp * exp
                | Multiply of exp * exp
   Define max_constant : exp -> int

  fun eval max_constant =
    case e of 
      Constant i       => i
    | Negate e2        => max_constant(i)
    | Add(e1,e2)       => Int.max(max_constant e1, max_constant e2)
    | Multiply(e1,e2)  => Int.max(max_constant e1, max_constant e2) 
)

  Type Synonyms:
(
    Create synonyms (aliases) for datatypes

    syntax:
      type aname = t

    examples:
      type date = int * int * int
      type card = suit * rank
      type record_name = { id: int, name : string option}

      fun is_queen_of_spades (c: card) =
        #1 c = Spade andalso #2 c = Queen

      fun is_queen_of_spades_2  c =
        case c of (Spade, Queen) => true
            | _ => false

      val c1 = (Diamond, Ace) 
)

 Lists and Options are Datatypes:
(
   a better way to use lists and options via case expressions
   because: no misses case, no exception for wrong variant, easier to read

   case expressions on options:
     Favor case expressions on option constructors over isSome/valOf functions

     fun inc_or_zero intoption =
       case intoption of 
         NONE => 0
       | SOME i => i+1

     case expressions on lists:
       Favor case expressions on [] and :: constructors, over hd, tl or null

       fun sum_list xs =
         case xs of
           [] => 0
         | x::xs' => x + sum_list xs'

     usage of null, tl, etc...?:
       for passing arguments to functions
       sometimes more convenient  
)

 Polymorphic Datatypes:
(
  Use type variables in datatypes
  Note: types cannot be mixed (e.g. lists cannot have ints and string)

  syntax:
    datatype (t1, t2, ..., tn) datatype
      t1, t2, ..., tn: type variables

  examples:
   (* `a ("alpha"), `b ("beta"), etc... is a traditional way to name type parameters *)
   datatype 'a option = NON | SOME of `a

   datatype `a mylist = Empty | Cons of `a * `a mylist

   datatype (`a, `b) tree =
     Node of `a * (`a, `b) tree * (`a, `b) tree
   | Leaf of `b
)

 Each of Pattern Matching / Truth About Functions:
(
    We used more syntactic sugar that we realized!
    - every val-binding and function-binding uses pattern-matching
    - every function in ML:
        takes exactly one argument (not zero, not 2, not 3...) which is a tuple
        returns exactly one tuple (that can be )

    Pattern matching not only works for "one-of" types (options, etc...), it also works for "each-of" types (records, tuples, etc...):_
      Pattern (x1, ..., xn) matches tuple values (v1, ..., vn)
      Pattern { f1=x1, ..., fn=xn } matches the record value { f1=v1, ..., fn=vn }

    Examples:
      (* bad style *)
      fun sum_triple t = case t of
        (x, y, z) => x + y + z

      (* bad style *)
      fun full_name r = case r of
        { first=x, middle=y, last=z } => x ^ " " ^ y ^ " " ^ z

      Val-binding patterns:
        Val-binding can use a pattern (not only a variable).

        val p = e
          p: pattern (poor style to use constructor because it works for one variant but raises expression otherwise)

        Better examples:
          fun sum_triple = triple
            let val (x, y, z) = triple
            in
              => x + y + z
            end

          fun full_name r =
            let val { first=x, middle=y, last=z } = r
            in
                x ^ " " ^ y ^ " " ^ z
            end

      Function-argument patterns:
          A function argument can also be a pattern.

          Syntax:
            fun f p = examples

          Even better examples:
          fun sum_triple (x, y, z) =
            x + y + z
          
          fun full_name { first=x, middle=y, last=z } =
                x ^ " " ^ y ^ " " ^ z

      Conclusion:
        Since all functions take a tuple and return a tuple, they can be combined easily.
        Example: fun rotate_right = rotate_left(rotate_left(1,2,3))
)

A little type inference:
(
   Type checker infers types of values, except for record #:
     fun sum_triple (triple) =
       #1 triple + #2 triple + #3 triple    (* compile error, is there a 4th field, 5th field, etc... *)

   Partial matching is OK:
     (* int * int * `a -> int *)
     fun partial_sum (a, b, c) = a + b
)

Polymorphic and Equality Types: 
(
  polymorphic functions = generic functions
   
   example: function that appends two lists of strings (string list * string list -> string list) can also append two lists of ints (int list * int list -> int list)
      => implement general function:  `a list * `a list -> `a list

    use of type synonyms does not matter
    order of fields name (in records) does not matter

    Equality types:
      equality types = a type that has the equality operator (=)
      
      Examples of equality types: int, string, tuples with equality types
      but not functions, real...

      ''a (two single quotes) means equality type

      examples:
        (* ''a * ''a -> string *)
        fun same_thing(x,y) =
          if x=y then "yes" else "no"

        (* int -> string *)
        fun is_three x =
          if x=3 then "yes" else "no"
)

Nested Patterns:
(
  generalization of pattern matching
  patterns can be nested

  full meaning of pattern-matching:
    - compare pattern with a value "of same shape"
    - bind variables o the right part 

  examples:

    (* zipping: tuple of list -> list of tuples 
        example: ([1,2,3], [4,5,6], [7,8,9]) -> [(1,2,3), (4,5,6), (7,8,9)] *)
    fun zip list_triple =
      case list_triple of
        ([], [], []) => []
      | (hd1::tl1, hd2::tl2, h3::tl3) => (hd1, hd2, hd3) :: zip(tl1, tl2, tl3)
      | _ => raise ListLengthMismatch

    fun unzip lst =
      case lst of
        [] => ([], [], [])
      | (a, b, c) : tl  => let val (l1, l2, l3) = unzip tl
                                   in
                                     (a::l1, b::l2, c::l3)
                                   end
)

More Nested Patterns:
(
  More examples:
  
  fun nondecreasing xs = (* int list -> bool *)
    case xs of
      [] => true
    | _::[] => true
    | head::(neck::rest) => head <= neck 
                                            andalso nondecreasing(rest)

  (* sign of a number *)
  datatype sgn = P | N | Z

  (* sign of the result of two numbers *)
  fun multsign(x1,X2) =
    let fun sign x = if x=0 then z else if x>0 then P else N
    in
      case (sign x1, sign x2) of
        (_, Z) => Z
      | (Z, _) => Z
      | (P,P) => P
      | (N,N) => P
      | (N,P) => N
      | (P,N) => N
    end

    fun len xs =
      case xs of
        [] => 0
      | _::xs' => 1 + len xs'

    Style:
      Nested patterns can lead to elegant and concise code
      Avoid nested case expressions if nested patterns are simpler and avoid branches (ex: unzip, nondecreasing)
      Common idiom: match against a tuple of datatypes (ex: zip, multsign)
      Wildcards are good style if variable is not needed
)

Nested Patterns Precisely:
(
  semantics:
    take a pattern p and a value v and decide if match ; if so bind introduced variables

  definition is recursive (because patterns can be nested)

  rules:
    if p is a variable, match always succeeds and x is bound to v
    if p is _, match succeeds, no bindings
    if p is (p1,...,pn) and v is (v1,...,vn), match succeeds if and only if p1 matches v1, ..., pn matches vn ; bindings are the union of all bindings from submatches
    if p is constructor "C p1", the match succeds if v is C v1 and p1 matches v1.

    variables can only be used once

  examples:
    pattern a::b::c::d matches all lists with 3 elements or more
    pattern a::b::c::[] matches all lists with 3 elements
    pattern ((a,b),(c,d))::e matches all non-empty lists of pairs of pairs
)

Optional: Function Patterns:
(
  (Dan does not particularly like it)

  fun f p = e

   This is just syntactic sugar
     fun  x =
       case x of
         p1 => e1
       | p2 => e2
       ...
       | pn = en

   can be written
     fun f p1 = e1
         | f p2 = e2
           ...
         | f pn = en

   example:
    fun eval (Constant i) = ip
     |    eval (Negate e2) => ~ (eval e2)
     |    eval (Add(e1,e2)) => (eval e1) + (eval e2)
     |    eval (Multiply(e1,e2)) = (eval e1) * (eval e2)
)

Exceptions:
(
  runtime errors

  syntax:
    declare: exception ex     (new kind of binding)
    raise: raise ex
    catch: e1 handle ex => e2

    exceptions are like datatypes, they can be pattern-matched

  examples:

    exception CatastrophicFailure
    exception HttpFailure of int    
    fun dummy(x) = 
      if x > 100 then raise CatastrophicFailure else raise HttpFailure 404

    fun maxlist(xs, ex) = 
      case xs of 
        [] => raise ex
      | x::[] => x
      | x::xs' => Int.max(x,maxlist(xs', ex))
    exception EmptyList

    maxlist([3,4,5], EmptyList) handle EmptyList => 42
)

Tail Recursion:
(
  How efficient are recursive functions in ML?

  Recursion:
    Easier that a loop (e.g. when parsing a tree)
    Avoid mutation

  Call-stacks:
    = functions that are called but not finished yet
    recursion: stack contains multiple calls to same function

  Example:
    (* factorial, simple way *)
    fun fact n = if n=0 then 1 else n*fact(n-1)
    val x = fact 3
    (* call-stacks:
    fact 3 -> fact 3: 3*_ -> fact 3: 3*_ -> fact 3: 3*_ -> fact 3: 3*_ -> fact 3: 3*_ etc...
              fact 2         fact 2: 2*_    fact 2: 2*_    fact 2: 2*_    fact 2: 2*_
                             fact 1         fact 1: 1*_    fact 1: 1*_    fact 1: 1*1
                                            fact 0         fact 0: 1      
    *)

    (* factorial with accumulator, more complicated, more efficient because of tail call optimization*)
    fun fact n =
      let fun aux(n, acc) =
        if n=0
        then acc
        else aux(n-1, acc*n)
      in
        aux(n,1)
      end
    val x = fact 
    (* call-stacks should be:
      fact 3 -> fact 3: _ -> fact 3: _   -> fact 3: _   -> fact 3: _  -> fact 3: _   -> fact 3: _  
                aux(3,1)     aux(3,1): _    aux(3,1): _    aux(3,1): _   aux(3,1): _    aux(3,1): _
                             aux(2,3)       aux(2,3): _    aux(2,3): _   aux(2,3): _    aux(2,3): _
                                            aux(1,6)       aux(1,6): _   aux(1,6): _    aux(1,6): 6
                                                           aux(0,6)      aux(0,6): 6    
      but is (due to tail-call optimization):

      fact 3 -> aux(3,1) -> aux(2,3) -> aux(1,6) -> aux(0,6)  
    *)
  
  Tail call:
    When stack call is immediately returned without any further evaluation

  Tail call optimization:
    Compiler recognizes tail calls and treats them differently: reuses the same stack space (pop caller before call).
    => tail calls are as efficient as loops (in other languages)
    All functional languages do tail-call optimization.
)

Accumulators for Tail Recursion :
(
  Common pattern for tail recursion

  Methodology:
   - create a helper function that takes an accumulator
   - old base case becomes initial accumulator
   - new base case becomes final accumulator

  More examples:

  (* int sum, not tail recursive *)
  fun sum xs =
     case xs od 
      [] => 0
  | x::xs' => x + sum xs'

  (* int sum, tail recursive *)
  fun sum xs =
    let fun aux(xs,acc) =
      case xs of
        [] => acc
      | h::t => aux(t, acc+h)
    in
    end
    aux(xs, 0)

    (* reverse list, not tail recursive *)
    fun rev xs =
        case xs of 
          [] => []
      | x::xs' => (rev xs) @ [x] (** beware: @ copies the items so algorithm is quadratic *)

    (* reverse list, tail recursive *)
    fun rev xs =
        let fun aux(xs, acc) = 
          case xs of
            [] => acc
          | x::xs' => aux(xs', x::acc)
        in
          aux(xs,[])
        end
)

Perspective on Tail Recursion:
(
  All functions cannot be magically to tail-recursice one (because memory is limited!), for example tree traversal.
  Beaware of premature optimization: favor clear and concise code.
    Tail position, by intuition: "no more work to do" 
  
  Tail position definition:
    tail call: function call in tail position

    if an expression is not in tail position, no subexpressions are
    if "fun f p = e", the body e is in tail position
    if "if e1 then e2 else e3" is in tail position, then e2 and e3 are in tail position but e1 is not
    if "let b1,...bn in e end" is in tail position, then e is in tail position (but no bindings expressions are)
    funcion-call arguments "e1 e2" are not in tail position (eg. nested functions)
)

Week 3:

Functions as arguments:
(
  Elegant strategy for factoring out code: replace N similar fuctions with calls to 1 function

  fun f (g, ...) = ... g(...) ...

  example:
    (* first-order functions LACK OF CODE SHARING *)
    fun increment_n_times_lame (n,x) =
      if n=0 then x else 1 + increment_n_times_lame(n-1,x)
    fun double_n_times_lame (n,x) =
      if n=0 then x else 2 * double_n_times_lame(n-1,x)
    fun nth_tail_lame (n,xs) = (* example : 3, [7,8,12,16] -> [16] *)
      if n=0 then xs else tl (nth_tail_lame(n-1,xs))

    (* higher-order function *)
    fun n_times(f,n,x) =
      if n=0 then x else f (n_times(f,n-1,x))
    fun increment x = x+1
    fun double x = x+x
    val x1 = n_times(double,4,7)
    val x2 = n_times(increment,4,7)
    val x3 = n_times(tl,2,[4,8,12,16])

    (* mask complexity for callers: *)
    fun addition(n,x) = n_times(increment,n,x)
    fun double_n_times(n,x) = n_times(double,n,x)
    fun nth_tail(n,x) = n_times(tl,n,x)
)

Polymorphic Types and Functions as Arguments:
(
  About types of higher-order functions

  HOF often have polymorphic types (i.e. types with type variables)

  Example:
    (*
      ('a -> 'a) * int * 'a -> 'a'
      *)
    fun n_times(f,n,x) =
      if n=0 then x else f (n_times(f,n-1,x))

  All HOFs are not polymorphic. Example:
    (* 
      (int -> int) * int -> int
      a better implementation would be tail-recursive
    *)
    fun times_until_zero (f,x) =
      if x=0 the 0 else 1 + times_until_zero(f, f x)

  Some polymorphic functions are not HOFs. Example:
    fun len xs =
      case xs of
        [] => 0
      | x::xs' => 1 + len xs'
)

Anonymous Functions:
(
  Functions defined without a "fun" binding.
  Common use: arguments to HOFs, only if function is not recursive

  Example:
    fun triple_n_times (n,x) =
      n_times(fn x => 3*x, n, x)
    
    (* which is more concise than: *)
    fun triple_n_times (n,x) =
      let
       fun triple x = 3*x
      in
        n_times(triple,n,x)?,
      end
)

Unnecessary Function Wrapping:
(
  "(fn x => f x)" is bad style, it is equivalent to "if e then true else false"

  examples:
    (* bad style, unnecessary function wrapping: *)
    func nth_tail(n,xs) = n_times(fn y => tl y, n, xs)
    (* better style: *)
    func nth_tail(n,xs) = n_times(tl, n, xs)

    (* Bad style, function "alias":*)
    fun rev xs = List.rev xs
    (* better style, simpler: *)
    val rev = List.rev xs
)

Map and Filter:
(
  2 famous HOFs: map and filter on lists

  (* 
    List.map is predefined (but it uses currying) but let's write our own:
      ('a -> 'b) * 'a list) -> 'b list
  *)
  fun map(f, xs) =
    case xs' of
      [] => []
    | x::xs' => f(x)::map(f,xs')

  val x1 = map(x => x+1, [2,4,6]) (* [3,5,7] *)
  val x2 = map(hd, [[2,3,4], [5,6,7]]) (* [[3,4], [6,7]] *)

  (* 
    List.filter is predefined (but it uses currying) but let's implement our own: 
    ('a -> bool) * 'a list -> 'a list
  *)
  fun filter(f,xs) =
    case xs of
      [] => []
    | x::xs' => if f(x) then x::(filter(f,xs')) else filter(f,xs')
  fun is_even n = (v mod 2 = 0)
  fun all_even xs = filter(is_even, xs)
  fun all_even_snd xs = filter((fn (_,s) => is_even(s)), xs)

)

Generalizing Prior Topics:
(
  higher-order functions:
  - can take several functions as arguments
  - can return functions a results

  examples:

  (* returning a function *)
  fun double_or_triple f = (* (int -> bool) -> (int -> int) *)
    if f 7 then fn x => 2*x else fn x => 3*x
  val double = double_or_triple(fn x => x - 3 = 4)
  val four = double 2
  (* note: REPL prints 
      (int -> bool) -> int -> int
    instead of
      (int -> bool) -> (int -> int)
    because it does not display unnecessary parentheses *)

    (* HOF on our own datatype binding *)
    datetype exp = Constant of int
                  | Negate of exp
                  | Add of exp * exp
                  | Multiply of exp * exp
    (* are all constant even numbers? *)
    fun true_of_all_constants(f, e) =
      case e of
        Constant i => f i
      | Negate e1 => true_of_all_constants(f, e1)
      | Add(e1,e2) => true_of_all_constants(f, e1) andalso true_of_all_constants(f, e2)
      | Multiply(e1,e2) => true_of_all_constants(f, e1) andalso true_of_all_constants(f, e2)
    (* higher-order predicate: *)
    fun all_even e = true_of_all_constants((fn x => x mod 2 = 0), e)
)

Lexical Scope:
(
    Functions use scope where defined, not where called
    Closure: function code + environment where function is defined    

    Example:
      val x = 1
      fun f y = x + y (* f adds 1 to argument. It is a closure. *)
      val x = 2 (* no effect on function f *)
      val y = 3
      val z = f(x + y) (* f still adds 1 to arg, so z = 6 *)  
)

Lexical Scope and Higher-Order Functions:
(
  Lexcial scope makes HOF more powerful
  Benefits:
    - we can understand a function without knowing about caller environment
    - modifing function implementation that does not change behaviour (ex: val renamings) has no effect on caller

  example 1:
    val x = 1

    (* HOF that returns a function *)
    fun f y =
      let 
        val x = y+1 (* shadows previous val *)
      in
        fn z => x + y + z (* adds 2y+1 to argument *)
      end

    val x = 3 (* irrelevant *)
    val g = f 4 (* returns a function that adds 9 to its argument *)
    val y = 5 (* irrelevant *)
    val z = g 6 (* gets 15 *)

  example 2:
    (* HOF that takes a function as argument *)
    fun f g =
      let
        val x = 3 (* irrelevant *)
      in
        g 2
      end
    val x = 4
    fun h y = x + y (* adds 4 to argument *)
    val z = f h (* 6 *)

)

Why Lexical Scope:
(
  dynamic scope: use environment where function is called
  lexical scope: use environment where function is defined

  Lexical scope is used by ML. It makes more sense because:
  1. function's meaning does not depend on variable names used (so they can be modified, removed if not used, etc...)
  2. functions can be type-checked and reasoned about where defined
  3. closures can store data they need (ex: "filter(fn x => x <  0, numbers)" stores a function)

  Dynamic scope is occasionally convenient (some languages don't bother, Racket has a way to do it, etc...).
  NB: exception handling is a bit like dynamic scope  

)

Closures and Recomputation:
(
  Closure can be used to avoir repeating computations

  A function body:
  - is not evaluated until function is called
  - is evaluated every time the funciton is called
  - a variable binding evaluates its expression when the biding is evaluated (not every time the variable is used)
  => closures can be used to prevent recomputations 

  Example:
    fun filter(f,xs) =
      case xs of
        [] => []
      | x::xs' => if f(x) then x::(filter(f,xs')) else filter(f,xs')

    (* This implem works OK but size of s is recomputed on every call *)
    fun allShorterThan1(xs,s) =
        filter(fn x => String.size x < String.size s, xs)
        (* 
          we could print out "!" to be sure that computation occurred:
          filter(fn x => (print "!"; String.size x < String.size s), xs)
        *)

    (* Optimized version using closure: *)
    fun allShorterThan2(xs,s) =
      let
        val i = String.size s (* i is stored in environment => computed only once *)
      in
        filter(fn x => String.size x < i, xs)
      end
)

Fold and More Closures:
(
  Another famous HOF: fold to traverse a recursive datastructure (like lists).

  Let's implement our own fold function (BTW, there are not built-in "iterator-like" functions in ML):
    (* 
      This version "folds left"
      ('a * 'b -> 'a) * 'a * 'b list -> 'a
    *)
    fun fold (f, acc, xs) =
      case xs of
        [] => acc
      | x::xs => fold(f, f(acc, x), xs)

    fun sum xs = fold((fn (x,y) => x+y), 0, xs)
    
    fun all_non_negative xs = fold((fn (x,y) => x andalso y >= 0), true, xs)
    
    fun count_elements_in_range (xs, lo, hi) =
      fold ((fn (x,y) =>
        x + (if y >= lo andalso y <= hi then 1 else 0)),
        0, xs)
    
    fun all_elements_have_size_less_than (xs, s) =
      let 
        val i = String.size s
      in
        all_elements_have_size_less_than(fn y => String.size y < i, xs)
      end
    
    fun true_for_all (g, xs) =
        fold((fn(x,y) => x andalso g y), true, xs)
    
    fun all_elements_have_size_less_than_bis (xs,s) =
      let
        val i = String.size s
      in
        true_for_all(fn y => String.size y < i, xs)
      end
)

Closure Idiom: Combining Functions:
(
	Combine functions, aka composition

	We'll use 'o' operator that compose two funtions, from left to right.
	We cant define our own infix operator to compose two functions from right to left.

	example:
		(*  ('b -> c') * ('a -> b') -> ('a -> 'c) *)
		fun compose(f,g) = fn x => f(g x)

		(* equivalent to: *)
		f o g

		(* int -> real *)
		fun sqrt_of_abs1 i = Math.sqrt (Real.fromInt (abs i))

		(* better implem via compostion, from letf to right *)
		val sqrt_of_abs2 = Math.sqrt o Real.fromInt o abs

		(* idem from right to left via pipeline operator
			'|>' exists in F#, a dialect of ML
			so we define our own infix operator, '!>' *)
		infix !> 
		fun x !> f = f x
		val sqrt_of_abs3 i = i !> abs !> Real.fromInt !> Math.sqrt

		(* conditional composition via option: *)
		fun backup1 (f,g) = fn x => case f x of
									NONE => g x
								  | SOME y => y

	  	(* conditional compistion with exception: *)
		fun backup2 (f,g) = fn x => case f x raise _ => g x
)

Closure Idiom: Currying:
(
	A way to deal with multi-argument functions (another way is to use n-tuple to deal with n arguments), using closures.
	Currying: when function take 1st argument and returns a function that takes another arguments, etc...

	Syntactic sugar:
		1. e1 e2 e3... means ((e1 e2) e3)...
		2. "fun f p1 p2 p3" means "fun f p1 = fn p2 => fn p3 => ..." (ML has built-in support for currying)

	Example:
		(* old way: *)
		fun sorted_3_tuple (x,y,z) = z >= y andalso y >= x
		val s1 = sorted_3_tuple(7,9,11)

		(* via currying: *)
		val sorted2 = fn x => fn y => fn z => z >= y andalso y >= x
		val s2 = ((sorted2 7) 9) 11
		(* plus syntactic sugar (1): *)
		val s3 = sorted2 7 9 11
		(* plus syntactic sugar (2): *)
		val sorted3 x y z =
			z >= y andalso y >= x
		val s4 = sorted3 7 9 11

		(* beware, curried function and tupled functions are different: *)
		val wrong1 = sorted_3_tuple 7 9 11
		val wrong2 = sorted2 (7, 9, 11)

		(* curried version of fold: *)
		fun fold f acc xs =
			case xs of
				[] => acc
			| x::xs' => fold f (f(acc,x)) xs'
		fun sum xs = fold (fn (x,y) => x+y) 0 xs
)

Partial Application:
(
	Curried functions with "too few arguments", for convenience.
	Works for all curried functions.

	Examples:
		val is_non_negative x = sorted3 0 0
		val sum = fold (fn (x,y) => x+y) 0

		fun range i j = if i > j then [] else i::range (i+1) j (* [i, i+1, ...., j] *)
		val countup = range 1 (* [1, 2, 3, ..., x] *)

		fun exists predicate xs = 
			case xs of
				[] => true
			| 	x::xs' => predicate(x) orelse exists predicate xs'
		val no = exists (fn x => x=7) [3,4,5]
		val hasZero = exists (fn x => x=0 )

		val incrementAll = List.map (fn x => x+1)
		val removeZeros = List.filter (fn x => x<>0)

	Value restriction:
		Using partial application to create a polymorphic function may not work due to type system limitation.
		=> SML compiler warns about "type vars not generalized" + cannot call function

		example:
			(* compiler will warn, call wil fail *)
			val pairWithOne = List.map (fn x => (x,1)) (* 'a list -> ('a * int) list *)
			(* work-around is declare explicit type (non-polymorphic): *)
			val pairWithOne : string list -> (string * int)
				 List.map (fn x => (x,1)) (* 'a list -> ('a * int) list *)
)

Currying Wrapup:
(
	How to curry a tupled function? Or tuple a curried one?
	How to change order of arguments in a curried function?

	examples:
		(* Currying tupled function  *)
		fun range (i,j) = if i > j then [] else i::range(i+1,j)
		fun curry f x y => f(x,y) (* (* ('a * 'b -> 'c') -> 'a -> 'b -> 'c *) *)
		val countup = curry range 1

		(* Uncurrying *)
		fun uncurry f(x,y) => f x y (* ('a -> 'b -> 'c') -> 'a * 'b -> 'c *)
		(* uncurry foo *)

		(* Changing order of parameters of a curried function: *)
		fun other_cury y x => f y x


	Efficiency:
		Which is more efficient, tupled or curried function?
		It depends on the language implementation and it is rarely important.
		If it really matters, tupled functions are faster in SML/NJ.
		But for other language implementations such as Haskell, F#, Ocaml, curried functions are faster.
)

Mutable References:
(
	Assignment statements!

	Data mutation is sometimes OK, ML has (seperate) mutation: references.

	Syntax:
		t ref (* where t is a type *)
		ref e (* sets initial content *)
		e1 := e2 (* updates content *)
		!e (* reads content *)

	Example:
		val x = ref 42
		val y = ref 42
		val z = x (* z is an alias for x *)
		val _ = x := 43 (* _ is a idiom for "I don't care about the result" *)
		val w = (!y) + (!z) (* 42 + 43 = 85 *)
		(* x + 1 does not type-check *)
)

Closure Idiom: Callbacks:
(
  Callback:
    "call me later, after an event occurs" via closures (private data = context)
    Callback are executed for side-effect.
    They may use mutable state in order to register


  Examples:
    (* list of registered callbacks of type (int -> unit) *)
    val cbs : (int -> unit) list ref = ref []

    (*  Registers call-back *)
    fun onKeyEvent f = cbs := f :: (!cbs)

    (* Simulates keyboard event *)
    fun onEvent i = 
      let fun loop fs =
        case fs of
          [] => ()
        | f::fs' => (f i; loop fs')
      in loop (!cbs) end

    (* Client example: *)
    val timesPressed = ref 0
    val _ = onKeyEvent (fn _ => timesPressed := (!timesPressed) + 1)
    fun printIfPressed i =
      onKeyEvent (fn j =>
        if i=j
        then print ("you pressed " ^ Int.toString i)
        else ())
    val _ = predefined 4
    val _ = predefined 11
)

Standard-Library Documentation:
(
  Like many languages, ML has a standard library. How to learn?

  Standard library:
    Contains:
    - things you could not do on your own (ex: open a file)
    - common things (ex: string concatenation, List.map) we don't need to rewrite, explain, etc...

  ML doc:
    http://sml-family.org/Basis/manpages.html
    Organized by structures + signatures (ex: List.map, String.isSubstring)

    (for homework 3: see STRING, Char, List and ListPair)

  REPL trick:
    Evaluating a function
      - confirms it exists!
      - displays its signature
    Example:
      (* Check function signature *)
      List.last;
      (* REPL displays:
        val it = fn: 'a list -> 'a
      *)

      (* Lists all list functions: *)
      structure x = List; (* displays: "signature LIST" *)
      signature LIST; (* Displays all List functions *)
)

Abstract Data Types With Closures:
(
  Implementing abstract datatypes with closures:
    - is a bit like OOP
    - a set a functions applying to a record
    - with closures => private data that can be mutable or immutable (prefered)

  Example:
    operations on integer sets: insert, member and size 

  Code:
    (* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
    (* Section 3: Optional: Abstract Data Types with Closures *)

    (* a set of ints with three operations *)
    (* this interface is immutable -- insert returns a new set -- but we could
       also have implemented a mutable version using ML's references *)
    (* Note: a 1-constructor datatype is an SML trick for recursive types *)
    datatype set = S of { insert : int -> set, 
              member : int -> bool, 
              size   : unit -> int }

    (* implementation of sets: this is the fancy stuff, but clients using
       this abstraction do not need to understand it *)
    val empty_set =
        let
            fun make_set xs = (* xs is a "private field" in result *)
                let (* contains a "private method" in result *)
                    fun contains i = List.exists (fn j => i=j) xs
                in
                    S { insert = fn i => if contains i 
                                         then make_set xs 
                                         else make_set (i::xs),
                        member = contains,
                        size   = fn () => length xs
                      }
                end
        in
            make_set []
        end 

    (* example client *)
    fun use_sets () =
        let val S s1 = empty_set
            val S s2 = (#insert s1) 34
            val S s3 = (#insert s2) 34
            val S s4 = #insert s3 19
        in
            if (#member s4) 42
            then 99
            else if (#member s4) 19
            then 17 + (#size s3) ()
            else 0
        end 
)

Closure idoms without closures:
(
  Some languages don't have closures, let's see how to use similar style of code.

  ML reference code (will be ported in Java):
    (* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
    (* Section 3: Optional: Closure Idioms Without Closures *)

    (* Note this file is sort of misnamed.  It /does/ use closures.  It is code
       that we will compare to code in Java or C that does not use closures. *)

    (* re-implementation of a list library with map, filter, length *)

    datatype 'a mylist = Cons of 'a * ('a mylist) | Empty

    fun map f xs =
        case xs of
      Empty => Empty
          | Cons(x,xs) => Cons(f x, map f xs)

    fun filter f xs =
        case xs of
      Empty => Empty
          | Cons(x,xs) => if f x then Cons(x,filter f xs) else filter f xs 

    fun length xs =
        case xs of
      Empty => 0
          | Cons(_,xs) => 1 + length xs

    (* One fine way to double all numbers in a list *)

    val doubleAll = map (fn x => x * 2)

    (* One way to count Ns in a list *)

    fun countNs (xs, n : int) = length (filter (fn x => x=n) xs)

  OOP code without closures (Java):
    (note : Java 8 has closures but let's pretend we're using Java 7)

    Key technique:
      One-method interface
      ex: 
        interface Func<B,A> { B m(A x); }
        interface Pred<A> { boolean m(A x); }

      Implem classes will have fields for "closure private data"

    Higher-order function:
      ex:
      static <A,B> List<B> map(<Func<B,A> f, List<A> xs) {
        if (xs == null)
          return null;
        return new List<B>(f.m(xs.head), map(f, xs.tail));
      }
)

Course Motivation:
(
  Intro:
    Some concepts are easier to teach in some PLs
    3 languages => show same concepts implemented differently + show differences
    a good PL is "a good interface"
    FP has been on the leading edge for decades (they are slowly adopted by other languages)
    First-class functions and immutability are essentials (for concurrent programming...)

  Why Study General PL Concepts?:
    There is no "best PL", some PLs are better than other for a given purpose
    Analogy with cars (formula 1 vs offroad vs car-for-shopping, etc.)
    Learning programming is easier with a simple PL (like ML)
    Popular != good or bad

    This course focuses on
    - semantics => reason about code, interface
    - idioms => be better programmer

  Are All PLs the Same?:
    yes:
    - we can implement all programs (input/output) via any PLs (cd. Church-Turing thesis)
    - share the same fundamentals (variables, abstractions, one-of-type, recursion, etc...)
    no:
    - different idioms (e.g. OOP in SML is not pleasant)
    - beware the "Turing tarpit" (using the wrong way to implement just because we only know this way)

  Why Functional Languages?:
    This course contains 70% FP because: correct, elegant, "look-to-the-future", concurrent programming, code complexity (but slow adoption)
    Garbage collection => LISP, generic types => ML , XML syntax => LISP, type inference from ML, recursion since 60's, etc...
    FP adoption in mainstream langs: Java 8 (closures), Hadoop map/reduce (aka map/fold), etc...
    Recent-ish surge: Clojure, Erlang, F#, Haskell, OCaml, Scala... see http://cufp.org

  Why ML, Racket, and Ruby?
                      | dynamically-typed   |   statically-typed
    -------------------------------------------------------------
    functional        |     Racket          |     SML
    object-oriented   |     Ruby            |     Java, C#, etc... (mainstream)

    ML: polymorphic types, pattern matching, abstract types and modules, old but a fine foundation
    Racket: dynamic typing, macros, minmalist syntax, eval, good module system, large community, IDE is included
    Ruby: very object-oriented, classes (but not types), mixins

    If we had more time:
    Haskell: laziness, purity, type classes, monads
    Prolog: unification and backtracking
)

Week 4:

What is type inference:
(
	Dynamic / Static:
		Statically type-checking: prevent errors at compile time (before runtime)
			ex: Java, ML, Scala, etc...
	 	vs
		Dynamically type-checking: no (or few) such checks, errors occur at runtime, mainly
			ex: Racket, Ruby, JavaScript

	Implicitly typed:
	 Types are static but we rarely need to write down them
	 ex: ML

 	Type inference:
 		Types are deduced from code
)

ML type inference:
(
	Key steps:
		1. determine types of bindings in order (except for mutual recursion)
		2. for each val or fun binding: analyze facts (constraints)
		3. use type variables (e.g. 'a) for unconstraint types

	Value-restriction:
		ML type-checker is a bit too lenient
)

Mutual recursion:
(
  Allow f to call g and d to call f

  Sometimes useful, workaround for ML's binding-in-order rule for environments (note: using HOF is another workaround).
  Example: implementing state machines.
  
  Syntax:
    (* mutually recursive functions: *)
    fun f1 p1 = e
    and f2 p2 = e2
    (* etc. *)

    (* Also, mutually recursive datatype bindings: *)
    datatype t1 = ...
    and t2 = ...
      (* ... *)

  Finite-state-machine idiom:

    (* only accepts [] or [1,2] or [1,2,1,2] etc... *)
    fun match xs =
      let fun s_need_one xs = (* state 1 => check for state 2 *)
            case xs of 
              [] => true
            | 1:: xs' => s_need_two xs'
            | _ => false 
          and s_need_two xs = (* state 2 => check for end or state 1 *)
            case xs of
               [] => false
               | 2::xs' => s_need_one xs'
               | _ => false
      in
          s_need_one xs
      end

    Work-around:
      (* via HOF *)
      fun earlier (f,x) = .... f y ...
      fun later x = ... earlier(later, y) ...
)

Modules for namespace management:
(
  Motivation: organize real-life (larger) programs

  Syntax:
    ML module creation:
      structure MyModule = struct bindings (* functions, datatypes, etc... *) end
    ML module usage:
      MyModule.bindingName

    example:
      structure MyMathLib = 
      struct
        
        fun fact = if x= 0 then 1 else x * fact (x-1)

        val half_pi = Math.pi / 2.0

        fun doubler y = y + y
      end

      val eight = doubler(4) 

  Namespace management:
    give a hierarchy to names to avoid shadowing (modules can contain sub-module)
    Important, noit interesting!

  Use-all-the-things via Open:
    open ModuleName (* all bindings can be used without indicating Moduel *)
    Dan is not a big fan (* like wildcard imports in Java *) except for REPL

  Hiding things via Signatures
    Motivation: show some functions/datatytpes and hide others.

    Signature is used to declare public bindings, other bindings are hidden (private).
    A signature can have several implementations.

    Syntax: 
      signature SIGNAME
      sig 
        (* bindings *)
      end
      structure MyModule :> SIGNAME =
      struct
        (* bindings *)
      end

    Example:
      signature MATHLIB = 
      sig
        val fact : int -> int
        val half_pi : int
        val doubler : int -> int
      end
      structure MyMathLib :> MATHLIB = 
      struct
        fun fact x = ...
        fun half_pi = ...
        fun doubler x = ...
        fun hidden_function x = ...
      end

      Example #2:
        (* with rational numbers *)
        Properties (visible externally):
          - denominator cannot be 0 => constructor raises exception
          - toString uses reduced form => toString(2/4) = "1/2"
          - no infinite loops or exceptions
        Invariants (part of the implementation, not the module spec)
          - denominators > 0
          - all rationals returned by any functions are reduced. Some functions maintain invariants (constructor and add), others rely on it (gcd, toString)

        Code:
          (* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
          (* Section 4: A Module Example *)

          (* will assign different signatures to this module in later segments *)

          structure Rational1 = 
          struct

          (* Invariant 1: all denominators > 0
             Invariant 2: rationals kept in reduced form *)

            datatype rational = Whole of int | Frac of int*int
            exception BadFrac

          (* gcd and reduce help keep fractions reduced, 
             but clients need not know about them *)
          (* they _assume_ their inputs are not negative *)
            fun gcd (x,y) =
                 if x=y
                 then x
                 else if x < y
                 then gcd(x,y-x)
                 else gcd(y,x)
                   
            fun reduce r =
                case r of
              Whole _ => r
            | Frac(x,y) => 
              if x=0
              then Whole 0
              else let val d = gcd(abs x,y) in (* using invariant 1 *)
                 if d=y 
                 then Whole(x div d) 
                 else Frac(x div d, y div d) 
                   end

          (* when making a frac, we ban zero denominators *)
            fun make_frac (x,y) =
                if y = 0
                then raise BadFrac
                else if y < 0
                then reduce(Frac(~x,~y))
                else reduce(Frac(x,y))

          (* using math properties, both invariants hold of the result
             assuming they hold of the arguments *)
            fun add (r1,r2) = 
                case (r1,r2) of
              (Whole(i),Whole(j))   => Whole(i+j)
            | (Whole(i),Frac(j,k))  => Frac(j+k*i,k)
            | (Frac(j,k),Whole(i))  => Frac(j+k*i,k)
            | (Frac(a,b),Frac(c,d)) => reduce (Frac(a*d + b*c, b*d))

          (* given invariant, prints in reduced form *)
            fun toString r =
                case r of
              Whole i => Int.toString i
            | Frac(a,b) => (Int.toString a) ^ "/" ^ (Int.toString b)

          end

        Enhanced code
          - declares abstract type (=> cannot be constructed direclty, only via 'makeFrac' function) in order to maintains invariants
          - but exposes Whole constructor which does not break invariant

          (* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
          (* Section 4: Signatures for Our Example *)

          (* this signature hides gcd and reduce.  
          That way clients cannot assume they exist or 
          call them with unexpected inputs. *)
          signature RATIONAL_A = 
          sig
          datatype rational = Frac of int * int | Whole of int
          exception BadFrac
          val make_frac : int * int -> rational
          val add : rational * rational -> rational
          val toString : rational -> string
          end

          (* the previous signature lets clients build 
           any value of type rational they
           want by exposing the Frac and Whole constructors.
           This makes it impossible to maintain invariants 
           about rationals, so we might have negative denominators,
           which some functions do not handle, 
           and print_rat may print a non-reduced fraction.  
           We fix this by making rational abstract. *)
          signature RATIONAL_B =
          sig
          type rational (* type now abstract *)
          exception BadFrac
          val make_frac : int * int -> rational
          val add : rational * rational -> rational
          val toString : rational -> string
          end
            
          (* as a cute trick, it is actually okay to expose
             the Whole function since no value breaks
             our invariants, and different implementations
             can still implement Whole differently.
          *)
          signature RATIONAL_C =
          sig
          type rational (* type still abstract *)
          exception BadFrac
          val Whole : int -> rational 
             (* client knows only that Whole is a function *)
          val make_frac : int * int -> rational
          val add : rational * rational -> rational
          val toString : rational -> string
          end 

          (* this structure provides a small library 
             for rational numbers -- same code as in previous 
             segment, but now we give it a signature *)
          structure Rational1 :> RATIONAL_A (*or B or C*) = 
          struct
          (* Invariant 1: all denominators > 0
             Invariant 2: rationals kept in reduced form *)
            datatype rational = Whole of int | Frac of int*int
            exception BadFrac

          (* gcd and reduce help keep fractions reduced, 
             but clients need not know about them *)
          (* they _assume_ their inputs are not negative *)
            fun gcd (x,y) =
                 if x=y
                 then x
                 else if x < y
                 then gcd(x,y-x)
                 else gcd(y,x)

             fun reduce r =
                 case r of
               Whole _ => r
             | Frac(x,y) => 
               if x=0
               then Whole 0
               else let val d = gcd(abs x,y) in (* using invariant 1 *)
                  if d=y 
                  then Whole(x div d) 
                  else Frac(x div d, y div d) 
              end

          (* when making a frac, we ban zero denominators *)
             fun make_frac (x,y) =
                 if y = 0
                 then raise BadFrac
                 else if y < 0
                 then reduce(Frac(~x,~y))
                 else reduce(Frac(x,y))

          (* using math properties, both invariants hold of the result
             assuming they hold of the arguments *)
             fun add (r1,r2) = 
                 case (r1,r2) of
               (Whole(i),Whole(j))   => Whole(i+j)
             | (Whole(i),Frac(j,k))  => Frac(j+k*i,k)
             | (Frac(j,k),Whole(i))  => Frac(j+k*i,k)
             | (Frac(a,b),Frac(c,d)) => reduce (Frac(a*d + b*c, b*d))

          (* given invariant, prints in reduced form *)
             fun toString r =
                 case r of
               Whole i => Int.toString i
             | Frac(a,b) => (Int.toString a) ^ "/" ^ (Int.toString b)

          end

      Signature matching:
        structure Foo :> BAR

        Is allowed if:
        - every non-abstract data-type in BAR is provided in Foo 
        - every abstract data-types in BAR is provided in Foo as datatype or type synonym
        - every val-binding in BAR is provided in Foo as val-binding or as function-binding (possibly with a more general and/or less abstract internal type)
        - every exception in BAR is provided in Foo


  An Equivalent Structure:
    We can implement several abstractions that are equivalent (i.e. two implementations of rational numbers operations) => client can't tell the difference.
      - Rational2 does not keep rationals in reduced form in toString 
      - not equivalent under RATIONAL_A: Rational1.toString and Rational2.toString can return different results
      - equivalent under RATIONAL_B or RATIONAL_C: different invariants but same properties
    => it's easier to replace a module with another one if we expose less (ex: expose abstract types)!

    Code:
      (* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
      (* Section 4: An Equivalent Structure *)

      (* this signature hides gcd and reduce.  
      That way clients cannot assume they exist or 
      call them with unexpected inputs. *)
      signature RATIONAL_A = 
      sig
      datatype rational = Frac of int * int | Whole of int
      exception BadFrac
      val make_frac : int * int -> rational
      val add : rational * rational -> rational
      val toString : rational -> string
      end

      (* the previous signature lets clients build 
       any value of type rational they
       want by exposing the Frac and Whole constructors.
       This makes it impossible to maintain invariants 
       about rationals, so we might have negative denominators,
       which some functions do not handle, 
       and print_rat may print a non-reduced fraction.  
       We fix this by making rational abstract. *)
      signature RATIONAL_B =
      sig
      type rational (* type now abstract *)
      exception BadFrac
      val make_frac : int * int -> rational
      val add : rational * rational -> rational
      val toString : rational -> string
      end
        
      (* as a cute trick, it is actually okay to expose
         the Whole function since no value breaks
         our invariants, and different implementations
         can still implement Whole differently.
      *)
      signature RATIONAL_C =
      sig
      type rational (* type still abstract *)
      exception BadFrac
      val Whole : int -> rational 
         (* client knows only that Whole is a function *)
      val make_frac : int * int -> rational
      val add : rational * rational -> rational
      val toString : rational -> string
      end 

      (* this structure can have all three signatures we gave
         Rationa1 in previous segments, and/but it is 
         /equivalent/ under signatures RATIONAL_B and RATIONAL_C 

         this structure does not reduce fractions until printing
      *)
             
      structure Rational2 :> RATIONAL_A (* or B or C *) =
      struct
        datatype rational = Whole of int | Frac of int*int
        exception BadFrac

         fun make_frac (x,y) =
             if y = 0
             then raise BadFrac
             else if y < 0
             then Frac(~x,~y)
             else Frac(x,y)

         fun add (r1,r2) = 
             case (r1,r2) of
           (Whole(i),Whole(j))   => Whole(i+j)
         | (Whole(i),Frac(j,k))  => Frac(j+k*i,k)
         | (Frac(j,k),Whole(i))  => Frac(j+k*i,k)
         | (Frac(a,b),Frac(c,d)) => Frac(a*d + b*c, b*d)

         fun toString r =
             let fun gcd (x,y) =
               if x=y
               then x
               else if x < y
               then gcd(x,y-x)
               else gcd(y,x)

           fun reduce r =
               case r of
             Whole _ => r
           | Frac(x,y) => 
             if x=0
             then Whole 0
             else
                 let val d = gcd(abs x,y) in 
               if d=y 
               then Whole(x div d) 
               else Frac(x div d, y div d) 
                 end
             in 
           case reduce r of
               Whole i   => Int.toString i
             | Frac(a,b) => (Int.toString a) ^ "/" ^ (Int.toString b)
             end
      end


  Another equivalent structure:

    Implement another rational module, Rational3:
     - with type synonym type (rational = int * int)
     - that deals with reducing rational in toString

    Code:
      (* Programming Languages, Dan Grossman, Jan-Mar 2013 *)
      (* Section 4: Another Equivalent Structure *)

      (* this signature hides gcd and reduce.  
      That way clients cannot assume they exist or 
      call them with unexpected inputs. *)
      signature RATIONAL_A = 
      sig
      datatype rational = Frac of int * int | Whole of int
      exception BadFrac
      val make_frac : int * int -> rational
      val add : rational * rational -> rational
      val toString : rational -> string
      end

      (* the previous signature lets clients build 
       any value of type rational they
       want by exposing the Frac and Whole constructors.
       This makes it impossible to maintain invariants 
       about rationals, so we might have negative denominators,
       which some functions do not handle, 
       and print_rat may print a non-reduced fraction.  
       We fix this by making rational abstract. *)
      signature RATIONAL_B =
      sig
      type rational (* type now abstract *)
      exception BadFrac
      val make_frac : int * int -> rational
      val add : rational * rational -> rational
      val toString : rational -> string
      end
        
      (* as a cute trick, it is actually okay to expose
         the Whole function since no value breaks
         our invariants, and different implementations
         can still implement Whole differently.
      *)
      signature RATIONAL_C =
      sig
      type rational (* type still abstract *)
      exception BadFrac
      val Whole : int -> rational  (* client knows only that Whole is a function *)
      val make_frac : int * int -> rational
      val add : rational * rational -> rational
      val toString : rational -> string
      end 

      (* this structure uses a different abstract type.  
         It does not even have signature RATIONAL_A.  
         For RATIONAL_C, we need a function Whole.  
      *) 
      structure Rational3 :> RATIONAL_B (* or C *)= 
      struct 
         type rational = int * int
         exception BadFrac
             
         fun make_frac (x,y) = 
             if y = 0
             then raise BadFrac
             else if y < 0
             then (~x,~y)
             else (x,y)

         fun Whole i = (i,1)

         fun add ((a,b),(c,d)) = (a*d + c*b, b*d)

         fun toString (x,y) =
             if x=0
             then "0"
             else
           let fun gcd (x,y) =
             if x=y
             then x
             else if x < y
             then gcd(x,y-x)
             else gcd(y,x)
               val d = gcd (abs x,y)
               val num = x div d
               val denom = y div d
           in
               Int.toString num ^ (if denom=1 
                 then "" 
                 else "/" ^ (Int.toString denom))
           end
      end

  Different Modules Define Different Types: 
  (
    Two modules that implement the same signature with abstract type can use distinct types.

    If modules Rational1, Rational2 and Rational3 have the same signature, we can write:
     Rational1.toString(Rational1.make_frac(5,3));
     Rational3.toString(Rational3.make_frac(5,3));

    But we cannot mix them:
      Rational1.toString(Rational3.make_frac(5,3)); (* compilation error - that's good news because they are not equivalent *) 
      Rational2.toString(Rational3.make_frac(5,3)); (* compilation error - that's also good news because we're breaking our abstraction, even if they are equivalent *) 
  )
)

Equivalent Functions:
(
  Equivalence:
    => code simplification (maintenance)
    => ensure backward compatibility (I can add a feature without breaking existing ones)
    => optimization (can I make code faster?)
    => abstraction (can an external client tell I made this change?)

  Equivalent functions => same observable behaviour, i.e. given equivalent arguments, they:
   - always return the same result
   - have the same termination behavior
   - mututate memory the same way (i.e. mutable reference)
   - do the same input/output behavior (ex. printing to log file)
   - raise the same exceptions

  It's easier to have equivalent functions if:
   - there are fewer possible arguments (with a type-system and abstraction)
   - we avoid side-effects

  Pure functional languages like Haskell ensure equivalence, others don't.

  Examples:
    func f x = x + x
    (* is equivalent to: *)
    val y = 2
    fun f x = y * x

    fun g (f,x) = (f x ) + (f x)
    (* is not equivalent to: *)
    val y = 2
    fun g (f,x) = y * (f x)
    (* because f can have side-effects (ex : (fn i => (print "hello world: " ; i), 7)) *)


  Standard Equivalences:
  (
    syntactic sugar:
    (* example: *) fun f x = x andalso g x   (* is equivalent to: *) fun f x = if x then g x else false
    (* but beware of evaluation order: *) fun f x = x andalso g x   (* is NOT equivalent to: *) fun f x = if g x then x else false

    rename bound variables:
    (* example: *) val y = 14 ; fun f x = x + y + x (* is equivalent to: *) val y = 14 ; fun f z = z + y + z
    (* but we cannot reuse existing binding: *)
    val y = 14 ; fun f x = x + y + x (* is NOT equivalent to: *) val y = 14 ; fun f y = y + y + y
    fun f x = let val y = 3 in x+y end (* is NOT equivalent to: *) fun f y = let val y = 3 in y+y end

    use a helper function or not:
    (* example: *) val y = 14 ; fun g z = (z+y+z)+z (* is equivalent to: *) val y = 14 ; fun f x = x+y+x ; fun g z = (f z)+z
    (* but beware of environment: *) val y = 14 ; val y = 7 ; fun g z = (z+y+z)+z (* is NOT equivalent to: *) val y = 14 ; fun f x = x+y+x ; val y = 7 ; fun g z = (f z)+z

    unnecessary function wrapping:
    (* example: *) fun f x = x+x ; fun g y = f y (* is equivalent to: *) fun f x = x+x ; val g = f
    (* but beware of side-effects, *) fun f x = x+x ; fun h() = (print "hi"; f) ; fun g y = (h()) y (* is NOT equivalent to: *) fun f x = x+x ; fun h() = (print "hi"; f) ; val g = (h())

    let-binding vs anonymous function:
    (* could be equivalent ; it is not equivalent in ML because of type-system *)
    (* example: *) let val x = e1 in e2 end (* is NOT equivalent to: *) (fn x => e2) e1  
  )

  Equivalence Versus Performance: 
  (
    Our definition of equivalence does not take performance into account

    In facts, there are 3 kind of equivalences:
      1. PL equivalence: same inputs, same outputs and side-effects
      2. asymptotoc equivalence: -> focus on algorithm efficiency for large inputs, but ignores constant factors (i.e. ignores algo x4 times improvement, by example)
      3. systems equivalence: -> focus on tuning / algorithm for specific inputs (pragmatic, can be too specific, or wrong if we optimize for the wrong input) 
  )

)