% % Eta-conversion % declare Increment = fun {$ X} X+1 end {Browse {Increment 5}} declare Inc = fun {$ X} {Increment X} end {Browse {Inc 6}} % Inc can be simplified to Increment using eta-reduction % also called "inlining" in compiler optimizations % %%% Combinators % % Identity combinator declare I = fun {$ X} X end {Browse {I 5}} {Browse {I I}} % Application combinator declare App = fun {$ F X} {F X} end declare fun {Square X} X*X end {Browse {App Square 7}} % Normal order sequencing combinator, Z should not appear free in Y declare Seq = fun {$ X Y} { fun {$ Z} Y end X } end declare Display = fun {$ X} {Browse X} X end {Browse {Seq {Display 3} {Display 4}}} declare RSeq = fun {$ X Y} { fun {$ Z} X end Y } end {Browse {RSeq {Display 3} {Display 4}}} % Exercise: why does the normal order sequencing combinator not work % in an applicative order (call by value) language? % % Applicative order Reverse Sequencing combinator % declare ARSeq = fun {$ X Y} { fun {$ Z} {X} end {Y} } end {Browse {ARSeq fun {$} {Display 3} end fun {$} {Display 4} end}} % the use of functions with no arguments (also called "thunks") to % wrap (and delay the evaluation of) expressions enables us to % simulate call by name in a call by value language. %% Recursive definitions in lambda-calculus %% Recursion combinator Y %% Defining factorial in pure lambda calculus %% This expression (call it F) takes a function (call it G) and %% returns a function that computes the factorial of a number. declare F = fun {$ G} fun {$ N} if N==0 then 1 else N * {G N-1} end end end %% What can we apply it to, to get the factorial function? %% {F F} is not well defined: type of F is (Z->Z)->(Z->Z) %% actually, you can apply F to itself but the resulting function cannot be %% applied to anything. %% {F I} is well defined: it returns n * (n-1) (for n>0) but it %% does not return the desired factorial function, e.g.: declare I = fun {$ X} X end {Browse {{F I} 5}} %% how do we get factorial? %% we need a procedure X representing factorial, i.e., %% (F X) = X %% Notice that G itself in the construction above is supposed to %% compute the factorial function. %% In the factorial example, the following lambda-expression does the job: declare X = {fun {$ Z} {fun {$ G} fun {$ N} if N==0 then 1 else N * {G N-1} end end end fun {$ Y} {{Z Z} Y} end } end fun {$ Z} {fun {$ G} fun {$ N} if N==0 then 1 else N * {G N-1} end end end fun {$ Y} {{Z Z} Y} end } end } {Browse {{F X} 5}} %% Such X can be defined in terms of the recursive function F as follows %% X = (Y F) %% where Y is the recursion combinator (in normal order) declare Y = fun {$ F} {fun {$ X} {F {X X}} end fun {$ X} {F {X X}} end } end % Do not try the normal order Y combinator %(in applicative order, it goes into an infinite loop) % {Browse {{F {Y F}} 5}} %% here in applicative order (after eta-expansion) so that it %% terminates with applicative order reduction declare Y = fun {$ F} {fun {$ X} {F fun {$ Y} {{X X} Y} end } end fun {$ X} {F fun {$ Y} {{X X} Y} end } end } end %% the type of Y is ((Z->Z)->(Z->Z))->(Z->Z) declare X = {Y F} {Browse {{F X} 5}} %% notice that (Y f) = (f (Y f)) by the construction above. {Browse {X 5}} {Browse {{F {Y F}} 5}} %% thus, here is the "pure" lambda-calculus expression computing factorial: %% (assuming that lambda calculus has beed extended with 0, 1, -, *, =, if) declare Factorial = {fun {$ F} {fun {$ X} {F fun {$ Y} {{X X} Y} end } end fun {$ X} {F fun {$ Y} {{X X} Y} end } end } end fun {$ G} fun {$ N} if N==0 then 1 else N * {G N-1} end end end } {Browse {Factorial 6}} %% Fortunately, in Oz, we can more easily define recursive procedures. declare fun {Fact X} if X==0 then 1 else X*{Fact X-1} end end {Browse {Fact 6}} %% which is syntactic sugar for: declare Fact = fun {$ X} if X==0 then 1 else X*{Fact X-1} end end %% which itself is represented as a procedure of arity 2 in the Oz kernel language. %% More on this later. {Browse {Fact 10}} {Browse {Fact 100}} % %% Higher-Order Programming % %% Exponential declare Exp = fun {$ B N} if N==0 then 1 else B * {Exp B N-1} end end {Browse {Exp 2 5}} {Browse {Exp 2 30}} {Browse {Exp 2 100}} {Browse {Exp 2 1000}} %% Powers of 2 %% recall the Curry combinator declare Curry = fun {$ F} fun {$ X} fun {$ Y} {F X Y} end end end declare TwoE= {{Curry Exp} 2} {Browse {TwoE 100}} %% Reverse curry declare RCurry = fun {$ F} fun {$ X} fun {$ Y} {F Y X} end end end %% Square function revisited declare Square = {{RCurry Exp} 2} {Browse {Square 5}} %% %% Lambda-calculus representation of non-negative integers %% %% |0| = \x.x %% |n+1| = \x.|n| %% declare Zero = I declare Succ = fun {$ N} fun {$ X} N end end declare Pred = fun {$ N} {N Zero} % when applied to 0 it returns 0. end %% You can then implement Add by using recursion and Succ, %% and you can implement Multiply by using recursion and Add. %% %% assuming pure lambda calculus has been extended with "Not", "true" %% and "IsProcedure" declare IsZero? = fun {$ N} {Not {IsProcedure {N true}}} end {Browse {IsZero Zero}} {Browse {IsZero {Succ Zero}}} {Browse {IsZero {Pred {Succ Zero}}}} %% %% to facilitate printing the numbers in Oz %% declare LambdaNumber = fun {$ N} if {IsZero N} then 0 else 1+{LambdaNumber {Pred N}} end end %% e.g.: {Browse {LambdaNumber {Succ {Succ Zero}}}} % exercise: implement Add for the lambda calculus representation of % numbers %{Browse {LambdaNumber {Add {Succ Zero} Zero}}} %% Booleans in pure lambda calculus (normal order) declare LambdaTrue = fun {$ X Y} X end declare LambdaFalse = fun {$ X Y} Y end declare LambdaIf = fun {$ B T E} {B T E} end %% e.g.: {Browse {LambdaIf LambdaTrue 4 5}} {Browse {LambdaIf LambdaFalse 4 5}}