Lambda Calculus and ML
----------------------
Before we go too far, let us look back at ml. How close to ml is the
material we have already presented? Remember, we have added a wee bit of
sugar, so we allow ourselves:

      I = Lx.x
      apply = Lf.La.(f a)
      self_apply = Ls.(s s)

Is there an ml-equivalent? Yes.

- val I = fn x => x; (* I = Lx.x *)
val I = fn : 'a -> 'a

- (I I); (* (Lx.x Lx.x) => Lx.x *)
val it = fn : 'a -> 'a

- val apply = fn f => fn a => (f a); (* apply = Lf.La.(f a) *)
val apply = fn : ('a -> 'b) -> 'a -> 'b

- (apply I); (* (Lf.La.(f a) Lx.x) => La.(Lx.x a) => La.a *)
val it = fn : 'a -> 'a

- (apply apply); (* (Lf.La.(f a) Lf'.La'.(f' a')) 
                      => La.(Lf'.La'.('f a') a) *)
val it = fn : ('a -> 'b) -> 'a -> 'b

NOTE: I replaced a with a', and f with f' in the function argument 
      to avoid NAME CLASHES (and "cognitive overload"!!). We
      will return to this in some detail when we discuss the SCOPE
      of variables, and ALPHA CONVERSION.

- val self_apply = fn s => (s s); (* self_apply = Ls.(s s) *)
std_in:2.17-2.21 Error: operator is not a function
  operator: 'Z
  in expression:
    s s

Why is this not allowed?

- val times = fn n:int => fn m:int => n*m; (* times = Ln.Lm.n*m *)
val times = fn : int -> int -> int

- (times 3); (* (Ln.Lm.n*m 3) => Lm.3*m *)
val it = fn : int -> int

- val triple = (times 3); (* triple = (Ln.Lm.n*m 3)
                                    => Lm.3*m       *)
val triple = fn : int -> int

- (triple 4); (* (Lm.3*m 4) => 3*4 => 12 *)
val it = 12 : int
- ((times 3) 4); (* ((Ln.Lm.n*m 3) 4) => (Lm.3*m 4)
                                      => 3*4
                                      => 12          *)
val it = 12 : int


It is tempting (and I think "acceptable") to think along the 
following lines:





In Lambda calculus we have:      Lx.body
In ml we have:                   fn x => body

Therefore we might make the substitutions:

     L-Calculus                 ML
     ----------                 --
        L                       fn
        x                       x
        .                       =>
        body                    body


In addition we might think of a lambda function in the following way. 
Lets (for sake of example) say that we want a function 
that takes 3 arguments, x, y and z. Straight away we would
expect to see a lambda function 

                 Lx.Ly.Lz.body

where the body would (in all likelihood) be expressed in terms
of x y and z.  Furthermore, we apply it (call it) as follows:

              f_in_y_and_z = (Lx.Ly.Lz.body x_arg)

which reduces to (delivers as a result) a lambda function in 2
variables, y and z. More generally, 

          (((Lx.Ly.Lz.body x_arg) y_arg) z_arg)

where x is bound to x_arg giving a new function, then y is
bound to y_arg giving a new function, then z is bound to z_arg
giving a final result. This is NO DIFFERENT TO CURRYING IN ML.

Note that we may have a lambda function that ignores some of
its arguments, such as first and second:

     first = Lx.Ly.x
     second = Lx.Ly.y

Therefore ((first 1) 2) 
          => ((Lx.Ly.x 1) 2)
          => (Ly.1 2)
          => 1

In the second last step (Ly.1 2) the application ignores y in
its body, so 2 is lost, and we deliver 1 as a result.

          ((second 1) 2)
          => ((Lx.Ly.y 1) 2)
          => (Ly.y 2)
          => 2

Similarly in the second step ((Lx.Ly.y 1) 2) the application
ignores x in its body, so 1 is lost, and we deliver 2 as a
result.