🚀 go-pugleaf

In <2531@wn1.sci.kun.nl> ge@wn3.sci.kun.nl (Ge' Weijers) writes:

>I assume that languages like Miranda (TM) and ML are based on typed lambda
>calculus. In Miranda the Y combinator can be written as

>y f = g
>      where
>	 g = f g

>fac = y fac1
>      where
>	 fac1 f x = 1, x <= 1
>		  = x * (fac1 (x-1)), otherwise

>In Algol68 you can also write a Y combinator. The next example is not tested,
>as elas no implementation is available to me anymore:

>BEGIN
>    MODE M = PROC(M,INT)INT;

>    PROC fac1 = (M f, INT x)INT:
>    IF x <= 1
>    THEN 1
>    ELSE x * f(x-1)
>    FI;

>    PROC y = (M f, INT x)INT:
>      f (f,x);
>    
>    print((y(fac1,5), newline))
>END

Both these contain bugs. I think what he meant to write was

 y f = g
       where
 	 g = f g

 fac = y fac1
       where
 	 fac1 f x = 1, x <= 1
 		  = x * (f (x-1)), otherwise   <--------------

 In Algol68 you can also write a Y combinator. The next example is not tested,
 as elas no implementation is available to me anymore:

 BEGIN
     MODE M = PROC(M,INT)INT;

     PROC fac1 = (M f, INT x)INT:
     IF x <= 1
     THEN 1
     ELSE x * f(f, x-1)        <----------------
     FI;

     PROC y = (M f, INT x)INT:
       f (f,x);
     
     print((y(fac1,5), newline))
 END

In that form, the Algol68 program indeed works, and prints 120. However, I do
not see that it is really equivalent to the Miranda version. Here is a better
version, that also runs and prints 120.

BEGIN 
    MODE M = PROC(PROC(INT)INT,INT)INT;

    M fac1 = (PROC(INT)INT f, INT x)INT:
        IF x <= 1     
        THEN 1   
        ELSE x * f(x-1) 
        FI;   

    PROC y = (M f, INT x)INT:
        ( PROC g = (INT x)INT: f(g, x);
          f(g,x) 
        ); 

    print((y(fac1,5), newline))
END