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.