ML: Local Environments, Exceptions, I/O

ML uses lazy eval only with boolean expressions. Eager eval otherwise. All arguments are evaluated, for example, before the function is called on the values... strict call-by-value.

  fun looper x = looper(x);
  looper(5);

  fun heaper x = x*heaper(x);
  heaper(5);

  fun higher (flag, arg, func) = 
     if flag 
        then func(arg):int
        else 1
     ;

  higher(false,5,heaper);
  higher(true,5,heaper);
  
  fun yurk (flag, arg) = 
     if flag 
        then arg
        else 1
     ;

  yurk(true,17);
  yurk(false,heaper(5));
  yurk(true,heaper(5));

Eager evaluations is called Applicative order evaluation

These come from lambda calculus, the mathematical foundation for claiming that a language of functions can express all possible computable computations.

Binding is not assignment

   val x = 5;

is not the ML equivalent of 

   x := 5;

in imperative languages.

x := 5     says "there is a storage location... we have bound the 
           name x to that storage location, and now we would
           like to place this bit pattern in that storage
           location"
           subsequent references to x will go to the storage
           location and use what value is there

val x = 5  says "make a new entry in the symbol table (environment)
           binding the name x to the integer value 5"

it is a matter of indirection... what is the name bound to?

   x  --->  storage loc  --->  value  (imperative)
   x  --->  value                     (functional)

The name "x" is not refered to as a "variable"
rather it is an identifier

Local Environments: LET

Let will define a local scope... allowing symbol definitions that 
live only for part of a function definition


  fun hunPower (x:real) =
    let val four = x*x*x*x ;
        val twenty = four*four*four*four*four ;
    in
        twenty*twenty*twenty*twenty*twenty
    end;


Perverse example:


  fun hunPower (x:real) =
    let val x = x*x*x*x ;
        val x = x*x*x*x*x 
    in
        x*x*x*x*x 
    end;


Bindings work fine this way... x keeps on getting a new binding, which
is added successively to the symbol table and hides previous bindings.
At end of LET all bindings created in the block are removed.

LET can be used in conjunction with patterns in several useful ways 

  (* function to split a list into two lists, alternating elements *)
  fun split(nil) = (nil,nil)
   |  split([a]) = ([a],nil)
   |  split(a::b::cs) =
        let val (M,N) = split(cs)
        in  (a::M,b::N)
        end;

Now we're getting somewhere... here's MergeSort

  (* using split as previously defined *)

  (* remember merge? *)
  (* merges two sorted lists, sorted smallest first *)
    fun merge(nil,M) = M
     |  merge(L,nil) = L
     |  merge(L as x::xs, M as y::ys) =
          if (x:int) < y then x::merge(xs,M)
          else y::merge(L,ys) ;

  fun mst (nil) = nil
   |  mst ([a]) = [a]
   |  mst (L) =
        let val (M,N) = split(L) ; 
            val M = mst(M) ;
            val N = mst(N) 
        in  merge(M,N)
        end;

Simple Output

Traditionally I/O is a side effect... but it is useful even in 
a functional PL 

"print" function puts value of its argument to STDOUT

   fun tz(0) = print("zero\n")
    |  tz(_) = print("not zero\n") ;
   >> val tz = fn : int -> unit

Note the type "unit" for print "result"

print takes arguments of int, bool, real, or string
but you must be careful when mixing types in a function definition

   fun prhd(nil) = print("oops... list has no head\n")
    |  prhd(x::_) = print(x) ;
   >> Error: overloaded variable cannot be resolved: print

You have to help the type inference system

   fun prhd(nil) = print("oops... list has no head\n")
    |  prhd(x::_) = print(x:int) ;
   >>  val prhd = fn : int list -> unit

Note that this now works only for int list... not generic list.

This sometimes prints string, sometimes integer... which is ok,
since printing is a side effect.  Type of prhd is "int list -> unit"

You can combine statements into a statement list with ( )
Here is a print list example

  fun prlst(nil) = ()
   |  prlst(x::xs) = 
        ( print(x:int); 
          print("\n");
          prlst(xs)
        );

What happens here (without parens)?

  fun prlst(nil) = ()
   |  prlst(x::xs) = 
        print(x:int); 
        print("\n");
        prlst(xs)
        ;

What is the difference between STATEMENT LIST and LET?

Between LET ... IN we must find declarations (val, fun, etc.)

Simple Input

Reading a file... open_in , end_of_stream , input 

  fun rdlst (file) = 
    if end_of_stream(file) then nil
    else input(file,1) :: rdlst(file) ;
  >>  val rdlst = fn : instream -> string list

  rdlst(open_in("foo"));
  >> val it = ["1","2","3","4","5","\n","6","7","8",...] : string list

Here, input(fn,n) says read "n" characters from file handle "fn"

open_in creates a file handle of type "instream"

  val inf = open_in("foo");
  >> val inf = - : instream

instream is a sequence of characters, includes "\n" from files.

A more complex I/O example

read a list of integers from a file and compute their sum
 -- positive integers only
 -- integers separated by one or more white-space chars 
 -- last int may or may not have white-space after it
 -- any char except ws and digit is error

exception BadChar;

val END = ~1;

fun white(c) =
c=" " orelse c="\n" orelse c="\t";

fun digit(c) =
c >= "0" andalso c <= "9";

fun startInt(file) = 
  (* get the first digit from file;
     return END if there is no integer *)
  if end_of_stream(file) then END
  else let val c = input(file,1)
       in  if digit(c) then ord(c)-ord("0")
	   else if white(c) then startInt(file)
	   else raise BadChar
       end;

fun finishInt(i,file) = 
  (* return the integer whose first digits have value i and 
     whose remaining digits are found on file, up to the end or 
     the first white space *)
  if end_of_stream(file) then i
  else let val c = input(file,1)
       in if digit(c) then finishInt(10*i+ord(c)-ord("0"), file)
	  else if white(c) then i
	  else raise BadChar
       end;

fun getInt(file) = 
  (* read an integer from file *)
  finishInt(startInt(file), file) ;

fun sumInts1(file) = 
  (* sum the integers on file *)
  let val i = getInt(file)
  in if i=END then 0
     else i + sumInts1(file) 
  end;

fun sumInts(filename) = 
  (* sum the integers on file "filename" relative to the 
     current UNIX directory *)
  sumInts1(open_in(filename));

Useful I/O Functions

(*
======================================================================= 

  ML (before ML97) has limited I/O functions built-in
  they are:

  INPUT

    val inf = open_in ("");
       opens an instream

    ch = input(inf,1)  
       reads 1 character from instream "inf"

    str = input(inf,)
       reads n character from instream "inf"

    ch = lookahead(inf)
       gets the next character in "inf" but leaves the character 
       in the instream

    end_of_stream(inf)
       tells if there are more characters to input

    can_input(inf)
       returns an integer that tells how many characters can be
       obtained from instream "inf"
       for some reason, this function seems to return 0 when an
       instream has just been opened, then works as expected after
       the first character is input, or after an "end_of"stream"
       inquiry...

    close_in(inf)
       terminates the instream

  OUTPUT

    val outf = open_out("");
       opens an outstream "opuf" which will be connected to the
       indicated file.  This stomps the indicated file.

    val outf = open_append("");
       opens an outstream "opuf" which will be connected to the
       indicated file.  This DOES NOT stomp the indicated file,
       but will have output begin at the end of the information
       that is already there.

    output(outf,st)
       appends the string "st" to the outstream "outf"

    flush_out(outf)
       forces output for output to a screen 

    close_out(outf)
       terminates the outstream

  EXCEPTIONS
   
    these raise "Io" if you try to write or read a stream that has
    been closed.

  STANDARD I/O

    std_in
    std_out
      preopened instream, outstream connected to keyboard and screen
   
========================================================================
*)

(*
======================================================================= 

Here are some functions I have written to help with I/O
feel free to modify, rename, or ignore them

  inAll(inf)
    returns a string that contains all remaining characters
    from the instream

  inAllList(inf)
    returns a list composed of all the remaining characters in instream

  inLine(inf)
    returns a string containing all the characters up to (but not
    including) the next "\n" characters in the instream... 
    note that two successive calls to inLine will skip over the
    "\n" and neither will return it.

  inLineList(inf)
    returns a list containing all the characters up to (but not
    including) the next "\n" character in the instream

========================================================================
*)

fun inAllList (x) =
  if end_of_stream(x) then nil
  else input(x,1) :: inAllList(x);

fun inAll (x) =
  implode(inAllList(x));


fun inLineList (x) =
  if end_of_stream(x) 
    then nil
    else if lookahead(x) = "\n" 
      then (input(x,1);nil)
      else input(x,1) :: inLineList(x);

fun inLine (x) =
  implode(inLineList(x));

Exceptions

"exception" is a type (exn, built-in like int, etc.).  
Any function can return type "exception" no matter what its defined 
result type is normally. 

Exceptions can be user-defined as follows:

  exception Foo ;
  >> exception Foo
  exception Bar and Baz ;
  >> exception Bar
  >> exception Baz

"Foo" is now a value of type "exception", as are "Bar" and "Baz"

A defined exception can be raised as follows: 

  raise Foo ;
  >> uncaught exception Foo

Exceptions can also be defined to have parameters:

  exception Foo of string;
  >> exception Foo of string

When raised, the parameter must be supplied a value:

  raise Foo("bar");
  >> uncaught exception Foo

Handling Exceptions

If a raised exception is not handled, computation always stops.

  < expression > handle < match >
  here we fear that some exception may be raised in < expression >
  the "handle" section will deal with all exceptions we fear


  exception OutOfRange of int * int * string;

  fun safe_comb(n,m) =
    if n <= 0 then raise OutOfRange(n,m,"")
    else if m < 0 then raise OutOfRange(n,m,"m must be greater than 0")
    else if m > n then raise OutOfRange(n,m,"n must be greater than m")
    else if m=0 orelse m=n then 1
    else safe_comb(n-1,m) + safe_comb(n-1,m-1);

  fun comb(n,m) = safe_comb(n,m) 
    handle
      OutOfRange(0,0,mess) => 1
    | OutOfRange(n,m,mess) => 
         ( print("out of range: n="); print(n); 
           print(" m="); print(m); 
           print("\n"); print(mess); print("\n"); 
           0 
         ) ;

MORE EXAMPLES

fun expo (x, 1) = x
  | expo (x:int, y) = x * expo(x, y-1) ;

fun inverse x = 1.0 / x
  handle Div => ( print("divide by zero produces 'infinite' value: "); 
                  real(expo(10,10))
                );

Higher-Order Functions

Higher-order function generates a function value as result
  or take functions as parameters

Example is often integration... take a function, produces another
  function that is the integral

  fun trap (a,b,n,F) =
    if n<=0 orelse b-a<=0.0 then 0.0
    else 
      let val delta = (b-a)/real(n)
      in  delta*(F(a)+F(a+delta))/2.0 
            + trap(a+delta,b,n-1,F)
      end;

  >> val trap = fn : real * real * int * (real -> real) -> real

  fun sq(x) = x*x : real;

  trap(0.0,1.0,100,sq);  gens .333...  1/3 is analytical result

Common Higher-order Function

MAP
  applies a function F to a list [a, b, c, ...] 
    producing [F(a), F(b), F(c), ... ]

  fun map(F,nil) = nil
   |  map(F,x::xs) = F(x)::map(F,xs) ;
  >> val map = f : ('a -> 'b) * 'a list -> b' list
  (rem built-in >> val it = fn : ('a -> 'b) -> 'a list -> 'b list )

  how's that for polymorphic??

Anonymous functions

We don't always have to define named functions:

  map(fn(x) => x*x, [3,5,8]);
  >> val it = [9,25,64] : int list

Here, the square function is defined inline, as an anonymous
(nameless) function.

Let's practice currying... here's the "real" internal map function:
what does this mean?

  map ;
  val it = fn : ('a -> 'b) -> 'a list -> 'b list

map takes a function and a list and gens a list of function values
Look at the type notation...

  map ~ [1,2,3,4]
  >> val it = [~1,~2,~3,~4] : int list

REDUCE
  takes function F of two args and a list [a,b,c,...]
    and produces F(a,F(b,F(c,...))) 

  example: reduce(+,[1,2,3,4,5]) gives the sum of the integers 
    in the list... gives 1+2+3+4+5

    exception EmptyList;
    fun reduce (F,nil) = raise EmptyList
     |  reduce (F,[a]) = a (* rem we want F to take two args *)
     |  reduce (F,x::xs) = F(x,reduce(F,xs)) ;
    >> val reduce = fn : ('a * 'a -> 'a) * 'a list -> 'a

  example of use: variance

    fun sq(x) = x*x : real;

    fun plus(x,y) = x+y : real;

    fun len(nil) = 0.0
     |  len(x::xs) = 1.0 + len(xs);

    fun var(L) =
      let val n = len(L)
      in  reduce(plus,map(sq,L))/n - sq(reduce(plus,L)/n)
      end;

BTW, we could do without the function "plus" above in this way:
  fun var(L) =
    let val n = len(L)
    in  reduce(op +, map(sq,L))/n - sq(reduce(op +, L)/n)
    end;

In sml the reduce funtion is "fold"

  fold;
  val it = fn : ('a * 'b -> 'b) -> 'a list -> 'b -> 'b

What's the difference?
  fold doesn't require operators with same types
  fold allows...

FILTER
  takes a predicate P (boolean function) and a list A = [a,b,c,...]
    and produces a list of elements from A where P(A) is true

    fun filter(P,nil) = nil
     |  filter(P,x::xs) =
          if P(x) then x::filter(P,xs)
          else filter(P,xs);
    >> val filter = fn : ('a -> bool) * 'a list -> 'a list

    filter(fn(x) => x>10, [1,10,23,5,16]);

    >> val it = [23,16] : int list 

  We have used an anonymous function here to provide the predicate.

More on Functions...
Example: Function Composition

  fun comp(F,G,x) = G(F(x)) ;
  >> val comp = fn : ('a -> 'b) * ('b -> 'c) * 'a -> 'c

  comp(fn(x)=>x+3, fn(y)=>y*y+2*y,10);
  >> val it = 195 : int

This approach produces the values of F o G, but not the function 
itself as a value we can "carry around" with us.

We really want comp to generate a function for us, using its function
parameters.

  fun comp(F,G) =
    let fun C(x) = G(F(x))
    in  C
    end;
  >> val comp = fn : ('a -> 'b) * ('b -> 'c) -> 'a -> 'c

Here, the let allows us to return the entire function rather than
an evaluation of it.

Another way:

  fun comp(F,G) = 
    fn(x) => G(F(x)) ;
  >> val comp = fn : ('a -> 'b) * ('b -> 'c) -> 'a -> 'c


Yet another (curried):

  fun compC F G x = G ( F ( x ) ) ;
  >> val compC = fn : ('a -> 'b) -> ('b -> 'c) -> 'a -> 'c

ML does have a built-in composition operator "o", BTW...

  fun sq(x) = x*x : int;
  fun cu(x) = x*x*x : int;

  val sqcu = sq o cu ; (* sq of cu *)
  >> val sqcu = fn : int -> int

  sqcu 2;
  >> val it = 64 : int

real version of MAP

  fun map(F) =
    let fun M(nil) = nil
         |  M(x::xs) = F(x)::M(xs)
    in  M
    end;
  >> val map = fn : ('a -> 'b) -> 'a list -> 'b list

As mentioned before, predefined map returns a function... so

  val ms = map sq;
  >> val ms = fn : real list -> real list

will make a function ms that will take a list and gen 
a list of squares

An Interesting Example... with HOFunctions, LET, and Curried form

   Design a small ML function that will take a function G (of one argument) 
   and an integer x and produces a function that computes G composed x times 
   on an argument. If we call this function "CUF", then one simple 
   example of its use would be to create a function to raise an argument 
   to the 64th power: CUF(sq,6) would return this function (assuming "sq" 
   is an integer square function). 
 
   The function CUF should not use ML library functions or built-ins 
   (like "o" composition or map). 

   (i) Write such a function in Curried form (call it "CUF"). 

      fun CUF G x =
        if x = 1 then 
           G
        else let val F = CUF G (x-1) ;
                 fun C(p) = G(F(p)) ;
             in C
      end;

      use of this:

      fun t2 x = 2 * x;  this is a function that will multiply it's arg by 2

      val fff = CUF t2 3 ;  this makes a function that will apply the
                            t2 function 3 times to its argument 

      fff 4 ;    makes t2(t2(t2(4))) = 32.