Mailing List Archive: 49091 messages

## [REBOL] Re: Functional programming in REBOL

### From: lmecir:mbox:vol:cz at: 14-Aug-2001 7:53

```
Hi Larry,

you wrote:

> I just blew a mental fuse and possibly discovered a new way of defining
the
> Y-combinator in REBOL which is much simpler than the previous ones. Given
> the wrapped version of the factorial function:
>
> fact*: func [fact][
>  func [n][
>   either zero? n [1][n * fact n - 1]
>  ]
> ]
>
> Define Y like this:
>
> Y2: func [f][f f :f]
>
> This is another combinator, (i.e., a higher order function with no free
> variables). Now at the console:
>
> >> fact: Y2 :fact*
> >> fact 16.0
> == 20922789888000
>
> fact seems to calculate the correct answers.
>
> >> do fact* Y2 :fact* 5
> == 120
> >> do fact* fact* Y2 :fact* 5
> == 120
>
> It seems to satisfy the fixed-point property for Y.
>
> Question 1: Is Y2 really a valid definition of Y? Or have I missed
something
> important.
>
> One warning sign is that the same formulation does not work in Scheme. In
> Scheme you have to put as many applications of f into the definition of Y2
> as the n you want the recursion to work for.
>
> Possibly it works for all cases in REBOL with just the 2 applications of f
> to f because of the difference in the evaluation model for local variables
> between REBOL and Scheme.
>
> I'll have another look at this when brain function is restored.
>
> Puzzled
> -Larry
>

This is explainable. If we define:

fact**: cfunc [fact][
func [n][
either zero? n [1][n * fact n - 1]
]
]
f: y2 :fact**
f 0 ; == 1
f 1 ; == 1
f 2
** Script Error: Cannot use multiply on function! value
** Where: fact
** Near: n * fact n -

We see, that Y2 combinator "works" for FACT*, while it cannot work for
FACT**. That is the difference between Rebol and Scheme. FACT* simply
doesn't "remember" its FACT argument. When called twice, it uses the newest
value supllied, i.e. FACT* supplied to Y2 behaves like FACT** supplied to Y.
The thing breaks, if we supply another argument to FACT*:

broken-fact: y2 :fact*
broken-fact 0 ; == 1
broken-fact 1 ; == 1
fact* 0
broken-fact 1 ; == 0

Moreover, there is another "glitch":

f: fact* :fact*
f 1
CRASH!

BTW Larry, one more disadvantage to your CFUNC is, that the SPEC gets bound
to local context and that is why any words contained in SPEC that aren't
local (like ANY-TYPE! e.g.) may get "harmed".

Cheers