Functional programming in REBOL
[1/21] from: larry:ecotope at: 6-Aug-2001 21:33
Hi all,
I have been experimenting with some functional programming techniques in
REBOL using examples from various Scheme books and articles.
One of the major difficulties I encountered is the difference in evaluation
models for functions in REBOL versus those in Scheme. In Scheme, each time a
function is called Scheme creates a new context or environment containing
the bindings for the arguments. In REBOL, a context or environment for the
args is created only once. Subsequent evaluations reuse the *same* context.
In both languages an internal function which is returned as the function
value can reference any of the args of the outer function indefinitely.
This makes it effectively impossible to create typical functional constructs
in the way they are created in Scheme. However, I found a workable general
solution to this problem which is described in this note. And at the end
there is brain-twister puzzle ;-)
Lets see how this works with an example. Let's create a partial application
function, pa. pa is a function factory (i.e., it makes functions for us).
This function needs to satisfy the following identity.
((pa f x) y) = (f x y)
This says the function pa consumes 2 arguments; a function of 2 variables f
and a value x, and returns a function of one variable which when applied to
y gives the same result as the application of the function f to x and y.
This must hold for all f x and y. The function pa is a higher-order function
which contains no free variables. Such functions are often called
combinators.
We would like to write the function pa directly from the definition above in
the same way that we would in Scheme or Lisp. Our first try is then:
pa1: func [f x][func [y][f :x :y]]
Notice that x and y have to be set-words in the last block, because they
might also be functions and we want the evaluation to be delayed. Now lets
try our function:
>> m5: pa1 :* 5 ;make a function that multiplies by 5
>> m5 100
== 500
This works so far. Lets make a function that adds 5
>> a5: pa1 :+ 5
>> a5 100
== 105
It works also, but
>> m5 100
== 105
The multiply by 5 function is now add5 !! This is because all of the
functions made by pa1 will reference the one and only parent context, each
new use of pa1 will change all previous returned functions to do whatever
the last one does.
There is a simple and generalizable solution to this problem based on the
properties of REBOL functions. Consider the following function:
pa2: func [f x /local h][
h: func [f x][func [y][f :x :y]]
h :f :x
]
>> m5: pa2 :* 5
>> a5: pa2 :+ 5
>> m5 100
== 500
This function works correctly. The inner function h is the function written
as we want to write it (i.e., pa1). pa2 returns the result of h applied to
the arguments of pa2 (notice the use of the set-word forms). The arguments
are now stored in the context created for function h. They will remain
indefinitely accessible because the function h will never be called a second
time. Each time pa2 is executed, it will create a *new* function h. The
overall effect is exactly the same as with functions in Scheme, function
args are "remembered as necessary".
We can eliminate the local variable h as follows:
pa3: func [f x][
do append reduce [func [f x][func [y][f :x :y]]][:f :x]
]
This approach can now be generalized to create a function which will
automatically create functions that "remember their arguments" when needed.
My current version of this function is called cfunc indicating "context
func" or "closure func". If anyone sees a shorter or more elegant way to
write this function, please post. Here is my current version:
cfunc: func [spec body /local args][
args: copy []
repeat el spec [append args to-get-word :el]
func spec compose/deep [
do append reduce [func [(spec)] [(body)]][(args)]
]
]
Now we can write pa in exactly the same transparent fashion as in Scheme (by
transparent, I mean one can translate at sight between the code and the
defining equation for the function). And it only requires adding one
character to the REBOL pa1 code !
; partial application on x
pa: cfunc [f x][func [y][f :x :y]]
While we are at it, here are a few more combinators:
; partial application on y
pa-y: cfunc [f y][func [x][f :x :y]]
; duplicate x arg
dupx: cfunc [f][func [x][f :x :x]]
; complete curry of 2 arg function: note nested cfunc
; the eq. is (((curry f) x) y) = (f x y)
curry: cfunc [f][cfunc [x][func [y][f :x :y]]]
; uncurry a curried function: note the do
; the eq. is ((uncurry f) x y) = ((f x) y)
uncurry: cfunc [f][func [x y][do f :x :y]]
; compose two functions of one arg
comp: cfunc [f g][func [x][f g :x]]
Some examples:
>> c-add: curry :+
>> add5: c-add 5
>> add5 100
== 105
>> do uncurry :c-add 20 10
== 30
>> f: comp :log-10 :dupx :*
>> f 100
== 4
>> div5: pa-y :divide 5
>> div5 40
== 8
>> store: pa :append []
>> store 12.2
== [12.2]
>> store "functional is fun"
== [12.2 "functional is fun"]
Use of these functions with REBOL operators is hampered by the fact that ops
with any of the characters [/ < >] cannot be accessed as set- or lit- words.
I solved this with the function op which returns the value of the operator
given as an unevaluated word.
op: func [:x][:x] ;how does it work?
Now we can say
>> mod5: pa-y op // 5
>> mod5 7
== 2
Now, at last, it's puzzle time ;-) Actually two puzzles. We note that pa
itself is a function of 2 arguments and therefore pa can be applied with
itself as the function arg and with itself as the value arg:
mystery: pa :pa :pa
What does the function mystery do?
hmm: uncurry :curry
What does the function hmm do?
Some caveats. The use of cfunc is fairly expensive in terms of resources. it
should only be used to create a relatively small number of functions. My
main emphasis was on simple transparent programming, so cfunc and it's
creations may not work properly for some of the more esoteric REBOL
datatypes.
I hope some of you find this interesting and useful. Comments are welcome.
-Larry
[2/21] from: lmecir:mbox:vol:cz at: 7-Aug-2001 11:00
Hi Larry,
a few notes:
...snip...
> Let's create a partial application
> function, pa. pa is a function factory (i.e., it makes functions for us).
> This function needs to satisfy the following identity.
>
> ((pa f x) y) = (f x y)
...snip...
The problem with the above is, that it is a Scheme expression. In Rebol we
would have to say
(do (pa :f :x) :y) = (f :x :y)
, but there are cases, when even this is unsatisfactory, cf. my "mumblings"
on UNSET! datatype, functions with unevaluated/fetched arguments, ...
...snip...
> create a function which will
> automatically create functions that "remember their arguments" when
needed.
> My current version of this function is called cfunc indicating "context
> func" or "closure func". If anyone sees a shorter or more elegant way to
> write this function, please post.
...snip...
In http://www.sweb.cz/LMecir/highfun.r I call such a function E-FUNC. The
difference is, that E-FUNC is neither shorter, nor more elegant, but "more
general" in some aspects, e.g. it supports datatype checking and doesn't
have trouble with "active arguments" like functions, words, paths, ...
...snip...
> Use of these functions with REBOL operators is hampered by the fact that
ops
> with any of the characters [/ < >] cannot be accessed as set- or lit-
words.
> I solved this with the function op which returns the value of the operator
> given as an unevaluated word.
Not exactly, your OP function doesn't take an operator as an unevaluated
word, it rather fetches the value, i.e. the X value your function below gets
is not a word, it is an OP! value:
> op: func [:x][:x] ;how does it work?
>
> Now we can say
>
> >> mod5: pa-y op // 5
...snip...
BTW, I don't like this kind of functions (out of the frying pan and into the
fire, see my "mumblings" on unevaluated arguments etc. above). I would
write:
mod5: pa-y get first [//] 5
, which looks more readable to me.
> Now, at last, it's puzzle time ;-) Actually two puzzles. We note that pa
> itself is a function of 2 arguments and therefore pa can be applied with
<<quoted lines omitted: 3>>
> hmm: uncurry :curry
> What does the function hmm do?
...snip...
Nice puzzles.
[3/21] from: lmecir:mbox:vol:cz at: 7-Aug-2001 13:03
Hi myself,
> In http://www.sweb.cz/LMecir/highfun.r I call such a function E-FUNC. The
> difference is, that E-FUNC is neither shorter, nor more elegant, but "more
> general" in some aspects, e.g. it supports datatype checking and doesn't
> have trouble with "active arguments" like functions, words, paths, ...
Larry, your CFUNC doesn't have trouble with "active arguments". Some
differences:
f1: e-func [x [any-type!]] [type? get/any 'x]
f1 () ; == unset!
while
g1: cfunc [x [any-type!]] [type? get/any 'x]
** Script Error: Expected one of: word! - not: block!
** Where: to-get-word
** Near: to get-word! :value
f2: e-func [:x] [type? get/any 'x]
f2 // ; == op!
while
g2: cfunc [:x] [type? get/any 'x]
g2 // ; == get-word!
f3: e-func [do] [type? get/any 'do]
f3 "OK" ; == string!
while
g3: cfunc [do] [type? get/any 'do]
g3 "OK" ; == [func [do][type? get/any 'do] :do]
Cheers
Ladislav
[4/21] from: agem:crosswinds at: 7-Aug-2001 12:39
RE: [REBOL] Functional programming in REBOL
[larry--ecotope--com] wrote:
> Hi all,
> I have been experimenting with some functional programming techniques in
<<quoted lines omitted: 10>>
> solution to this problem which is described in this note. And at the end
> there is brain-twister puzzle ;-)
if i understand right, how about
f: func[a b][
context[local1: local2: none do-the-work return]
]
?
> Lets see how this works with an example. Let's create a partial application
> function, pa. pa is a function factory (i.e., it makes functions for us).
<<quoted lines omitted: 120>>
> I hope some of you find this interesting and useful. Comments are welcome.
> -Larry
-Volker
[5/21] from: g:santilli:tiscalinet:it at: 7-Aug-2001 19:23
Hello Larry!
On 07-Ago-01, you wrote:
[BTW, just to let you know, I think this has been discussed on
this list before, with Ladislav providing a nice and general solution
IIRC]
LP> pa2: func [f x /local h][
LP> h: func [f x][func [y][f :x :y]]
LP> h :f :x
LP> ]
I'd write it as:
pa2: func [f x] [
use [ff xx] [
xx: :x
ff: :f
func [y] [ff xx y]
]
]
or
pa2: func [f x] [
func [y] reduce [:f :x 'y]
]
Regards,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
[6/21] from: larry:ecotope at: 8-Aug-2001 10:13
Hi Ladislav,
Thanks for your excellent comments. I must confess that I was completely
unaware of e-func in your higher-order function library, although I had
looked at some of the other functions. Please accept my apologies.
e-func and cfunc were created from very similar goals. I agree with your
assessment that e-func is more general because it handles refinements and
delayed evaluation args in the spec block.
Two quick comments on e-func, if the line:
:nm-use locals reduce [ ...
was changed to
:use locals copy/deep reduce [ ...
e-func would be self-contained, making it a little more portable.
The other comment is that, for me personally, the e-func code much easier to
read and follow with the internal comments removed.
Out of curiosity, I checked the storage requirements for a curry function
created two ways:
1) using cfunc: 1268 bytes
2) using e-func: 2052 bytes
so e-func is using about 60% more storage. It is also noticeably slower.
I like the method you used to redefine the locals inside the use block, I
think that approach is much preferable to renaming the variables in the body
block as suggested by Gabriele.
I thought about your comments below and decided to add argument
type-checking and allow comment strings in the spec block for cfunc. Here is
the new version:
cfunc: func [spec body /local args][
args: copy []
repeat el spec [if word? :el [append args to-get-word :el]]
func spec compose/deep [
do append reduce [func [(spec)][(body)]][(args)]
]
]
The other restrictions still apply. The spec block for cfunc should not
contain refinements, get-words, lit-words, or set-words. The approach which
I took of reusing the spec block for all the args will not work for dealing
with these items, I think your approach is probably the best one.
On the other hand, I had a limited goal in creating cfunc. I just wanted
something that would handle "ordinary" arguments, so that Scheme code could
be entered more or less the same way as it would be in Scheme and produce
the same results. Scheme does not support user definition of datatypes for
args, or any of the other REBOL features mentioned above.
So, for my purposes, cfunc is acceptable and the version above allows
type-checking and doc strings as well. One of the main ideas from Scheme is
that most of the higher order functions are really simple, and in Scheme
they are simple. When we try to implement them to include all of the nuances
and features of REBOL functions, they tend to get more complex. In this
regard, I note that many of your functions also do not support delayed
evaluation arguments.
> Larry, your CFUNC doesn't have trouble with "active arguments". Some
> differences:
<<quoted lines omitted: 5>>
> ** Where: to-get-word
> ** Near: to get-word! :value
This is now fixed.
> f2: e-func [:x] [type? get/any 'x]
> f2 // ; == op!
>
> while
>
> g2: cfunc [:x] [type? get/any 'x]
> g2 // ; == get-word!
See above
> f3: e-func [do] [type? get/any 'do]
> f3 "OK" ; == string!
>
> while
>
> g3: cfunc [do] [type? get/any 'do]
> g3 "OK" ; == [func [do][type? get/any 'do] :do]
>
This one bothers me, but I don't see how to fix cfunc. Meanwhile, just don't
use DO as a variable name. Are there any other words that create this
problem?
Thanks again for your comments. And thanks for the effort which you have put
into highfun.r, it is a good resource for all of us.
Meanwhile I am looking forward to your solution of the puzzles ;-)
Cheers
-Larry
[7/21] from: larry:ecotope at: 8-Aug-2001 10:39
Hi Gabriele,
Thanks for your comments.
> [BTW, just to let you know, I think this has been discussed on
> this list before, with Ladislav providing a nice and general solution
> IIRC]
Yes, I missed e-func, see my reply to Ladislav earlier.
> LP> pa2: func [f x /local h][
> LP> h: func [f x][func [y][f :x :y]]
<<quoted lines omitted: 8>>
> ]
> ]
Yes, I have a set of higher-order funcs written in exactly that fashion. But
I don't like it. Renaming all the variables in the code block is ugly, and
it seemed to me the approach would be cumbersome (and perhaps diffcult) to
generalize for creating the generic cfunc. I think changing only the spec
blocks as in cfunc or Ladislav's e-func is preferable.
> or
>
> pa2: func [f x] [
> func [y] reduce [:f :x 'y]
> ]
I really liked that one. Unfortunately, it doesn't pass the mystery test as
shown in the console session below where I have renamed your version to pa4.
>> pa2: func [f x /local h][
[ h: func [f x][func [y][f :x :y]]
[ h :f :x
[ ]
>> pa4: func [f x] [
[ func [y] reduce [:f :x 'y]
[ ]
>> mystery2: pa2 :pa2 :pa2
>> mystery4: pa4 :pa4 :pa4
>> type? mystery2 :+
== function!
>> type? mystery4 :+
** Script Error: y expected value1 argument of type: number pair char mone
y date time tuple
** Where: mystery4
** Near: func [f x][
func [y] reduce [:f :x 'y]
] func [f x][
func [y] reduce [:f :x 'y]
] y
Regards
-Larry
[8/21] from: lmecir:mbox:vol:cz at: 8-Aug-2001 22:06
Hi Larry,
> Thanks for your excellent comments. I must confess that I was completely
> unaware of e-func in your higher-order function library, although I had
> looked at some of the other functions. Please accept my apologies.
Nevermind, you don't have to read everything I write :-), for the
interested: something on the subject is in
http://www.sweb.cz/LMecir/contexts.html
> e-func and cfunc were created from very similar goals. I agree with your
> assessment that e-func is more general because it handles refinements and
> delayed evaluation args in the spec block.
To be fair, I would like to say, that I am still convinced, that the
unevaluated/fetched argument passing is something Rebol shouldn't use at
all, because it is breaking the language evaluation order rules, ...
> Two quick comments on e-func, if the line:
>
> :nm-use locals reduce [ ...
>
> was changed to
>
> :use locals copy/deep reduce [ ...
>
> e-func would be self-contained, making it a little more portable.
I considered that, but it would harm E-FUNC in cases like:
f: e-func [copy [any-type!]] [type? get/any 'copy]
> Out of curiosity, I checked the storage requirements for a curry function
> created two ways:
<<quoted lines omitted: 3>>
> I like the method you used to redefine the locals inside the use block, I
> think that approach is much preferable to renaming the variables in the
body
> block as suggested by Gabriele.
>
> I thought about your comments below and decided to add argument
> type-checking and allow comment strings in the spec block for cfunc
...snip...
> The other restrictions still apply. The spec block for cfunc should not
> contain refinements, get-words, lit-words, or set-words. The approach
which
> I took of reusing the spec block for all the args will not work for
dealing
> with these items, I think your approach is probably the best one.
>
> On the other hand, I had a limited goal in creating cfunc. I just wanted
> something that would handle "ordinary" arguments, so that Scheme code
could
> be entered more or less the same way as it would be in Scheme and produce
> the same results. Scheme does not support user definition of datatypes for
> args, or any of the other REBOL features mentioned above.
>
> So, for my purposes, cfunc is acceptable and the version above allows
> type-checking and doc strings as well. One of the main ideas from Scheme
is
> that most of the higher order functions are really simple, and in Scheme
> they are simple. When we try to implement them to include all of the
nuances
> and features of REBOL functions, they tend to get more complex. In this
> regard, I note that many of your functions also do not support delayed
> evaluation arguments.
I personally do not support the strange argument passing methods too.
> > Larry, your CFUNC doesn't have trouble with "active arguments". Some
> > differences:
<<quoted lines omitted: 9>>
> > ** Near: to get-word! :value
> This is now fixed.
It isn't, see this:
g1 ()
** Script Error: x has no value
** Where: g1
** Near: func [x [any-type!]][type? get/any 'x] :x
> > f3: e-func [do] [type? get/any 'do]
> > f3 "OK" ; == string!
<<quoted lines omitted: 5>>
> >
> This one bothers me, but I don't see how to fix cfunc. Meanwhile, just
don't
> use DO as a variable name. Are there any other words that create this
> problem?
Yes: 'append, 'reduce, 'func
See this modification:
ga: func [word [any-word!]] [get/any word]
cfunc: function [
{closure creating function}
spec [block!]
body [block!]
] [body2] [
body2: reduce [:do :func spec body]
repeat el spec [if word? :el [append body2 reduce [:ga to lit-word!
el]]]
func spec body2
]
> Thanks again for your comments. And thanks for the effort which you have
put
> into highfun.r, it is a good resource for all of us.
>
> Meanwhile I am looking forward to your solution of the puzzles ;-)
I wanted to let the others to post their solutions. Don't read below the
line, if you want to solve the puzzle on your own:
-------------------------------------------------------
My solution:
pa :pa :pa
should be the CURRY function, while
uncurry :curry
should be the PA function.
[9/21] from: g:santilli:tiscalinet:it at: 8-Aug-2001 23:40
Hello Larry!
On 08-Ago-01, you wrote:
LP>> pa2: func [f x] [
LP>> use [ff xx] [
LP>> xx: :x
LP>> ff: :f
LP>> func [y] [ff xx y]
LP>> ]
LP>> ]
LP> Yes, I have a set of higher-order funcs written in exactly
LP> that fashion. But I don't like it. Renaming all the variables
LP> in the code block is ugly, and it seemed to me the approach
LP> would be cumbersome (and perhaps diffcult) to generalize for
LP> creating the generic cfunc. I think changing only the spec
LP> blocks as in cfunc or Ladislav's e-func is preferable.
Yes, of course you can also write:
pa2: func [f x /local w] [
w: use [f x] ['f]
set bind [f x] w reduce [:f :x]
func [y] bind [f x y] w
]
Of course all this can be generalized.
LP> I really liked that one. Unfortunately, it doesn't pass the
LP> mystery test as shown in the console session below where I
LP> have renamed your version to pa4.
[...]
LP>>> type? mystery4 :+
LP> ** Script Error: y expected value1 argument of type: number
LP> pair char mone y date time tuple
So that would need to be changed to:
pa4: func [f x] [
func [y] reduce [:f :x to-get-word 'y]
]
or (will have problems with blocks):
pa4: func [f x] [
func [y] compose [(:f) (:x) :y]
]
or even:
pa4: func [f x] [
func [y] reduce [get 'f get 'x 'get to-lit-word 'y]
]
or any other variant.
Regards,
Gabriele.
--
Gabriele Santilli <[giesse--writeme--com]> - Amigan - REBOL programmer
Amiga Group Italia sez. L'Aquila -- http://www.amyresource.it/AGI/
[10/21] from: lmecir:mbox:vol:cz at: 9-Aug-2001 14:34
Hi again,
two other variants of the CFUNC function:
comment {var1}
use [values pass-values in-new-context] [
pass-values: func [
{pass values to locals and do body}
[throw]
locals
body
] [
set/any locals values
do body
]
in-new-context: func [
{do body with locals in new context}
[throw]
locals
body
] [
values: make block! length? locals
foreach word locals [
insert/only tail values get/any word
]
use locals copy/deep reduce [
:pass-values locals body
]
]
cfunc: function [
{make a closure}
[catch]
spec [block!]
body [block!]
] [locals] [
locals: copy []
foreach item spec [
if all [any-word? :item not set-word? :item] [
append locals to word! :item
]
]
throw-on-error [
func spec reduce [
:in-new-context locals body
]
]
]
]
comment {var 2}
use [in-new-context] [
in-new-context: function [
{do body with locals in new context}
[throw]
locals
spec
body
] [statement] [
statement: make block! 1 + length? locals
append statement func spec body
foreach word locals [
insert/only tail statement get/any word
]
do statement
]
cfunc: function [
{make a closure}
[catch]
spec [block!]
body [block!]
] [locals spec2] [
locals: copy []
spec2: copy [[throw]]
foreach item spec [
if all [any-word? :item not set-word? :item] [
append locals to word! :item
append spec2 reduce [to lit-word! :item [any-type!]]
]
]
throw-on-error [
func spec reduce [
:in-new-context locals spec2 body
]
]
]
]
[11/21] from: lmecir:mbox:vol:cz at: 9-Aug-2001 18:52
Hi Larry et Rebols,
another variant of CFUNC, which looks like the fastest from the most general
versions. It uses the "fresh function creation" method to get a new context:
cfunc: function [
{make a closure}
[catch]
spec [block!]
body [block!]
] [locals in-new-context spec2 body2 i] [
locals: copy []
spec2: copy [[throw]]
body2: reduce ['do 'func spec2 body]
i: 1
repeat item spec [
if all [any-word? :item not set-word? :item] [
append locals to word! :item
append spec2 reduce [to word! :item [any-type!]]
append body2 reduce ['get/any 'pick 'locals i]
i: i + 1
]
]
in-new-context: func [
[throw]
locals
] body2
throw-on-error [
func spec reduce [:in-new-context locals]
]
]
[12/21] from: larry:ecotope at: 9-Aug-2001 11:53
Hi Ladislav,
Thanks for your many suggestions for a more general cfunc. I will be looking
these over when I get a chance.
BTW I implemented Church numerals last night using cfunc and everything
seems to work ok. Of course, they are not very practical: the Church numeral
100 takes up 235904 bytes!
Meantime, here is another puzzle. Given the definitions from my original
posting:
dupx: cfunc [f2][func [x][f2 :x :x]]
uncurry: cfunc [f][func [x y][do f :x :y]]
Define this function:
puzzle: dupx :uncurry :dupx
What does the function puzzle do?
Cheers
-Larry
[13/21] from: lmecir:mbox:vol:cz at: 10-Aug-2001 1:42
Hi Larry,
> Meantime, here is another puzzle. Given the definitions from my original
> posting:
<<quoted lines omitted: 5>>
> Cheers
> -Larry
with some minor exceptions
dupx :uncurry
behaves like:
identity: func [x] [:x]
the :dupx at the end of the expression doesn't change PUZZLE. Was it really
meant that way?
[14/21] from: larry:ecotope at: 9-Aug-2001 22:05
Hi Ladislav,
I just went back and checked the source for that puzzle and it should have
been written
puzzle: dupx (uncurry :dupx)
which makes sense because dupx returns a function of one arg, which is
consumed by uncurry which returns a function of two args which is consumed
by dupx which returns a function of one arg. So the idea is we use uncurry
to change dupx so that it can be applied to itself.
Sorry for the confusion.
-Larry
[15/21] from: lmecir:mbox:vol:cz at: 10-Aug-2001 9:31
Hi,
> I just went back and checked the source for that puzzle and it should have
> been written
<<quoted lines omitted: 7>>
> > >
> > > What does the function puzzle do?
It works like function:
puzzle2: func [x] [x :x :x]
[16/21] from: larry:ecotope at: 10-Aug-2001 20:47
Hi Ladislav,
Excellent! Your solutions for all three puzzles are correct. Here is one
more combinator which is more difficult to explain (at least for myself):
???: cfunc [f][
do
cfunc [x][f func [y][do x :x :y]]
cfunc [x][f func [y][do x :x :y]]
]
What does the function ??? do? And what requirements must its function
argument meet in order to guarantee that it produces a result?
Cheers
-Larry
PS This is one where I thought perhaps cfunc and this whole approach to
functional programming in REBOL would break down, but it seems to work just
fine.
[17/21] from: larry:ecotope at: 11-Aug-2001 22:23
Hi Ladislav, all,
Here is another way of writing the puzzle function in the post below. This
may make the nature of the function more clear:
???: cfunc [g][
do
func [f][f :f]
cfunc [f][g func [x][do f :f x]]
]
Cheers
-Larry
[18/21] from: lmecir:mbox:vol:cz at: 12-Aug-2001 9:46
Hi Larry,
> Your solutions for all three puzzles are correct. Here is one
> more combinator which is more difficult to explain (at least for myself):
<<quoted lines omitted: 9>>
> PS This is one where I thought perhaps cfunc and this whole approach to
> functional programming in REBOL would break down, but it seems to work
just
> fine.
Very interesting! The ??? function looks like an impersonalized Russell'd
paradox. I didn't know about such functions until now. If I define:
id: func [x] [:x]
then the result:
beast: ??? :id
is pretty well defined. The problem is, that the BEAST function is a
function of one argument, but the result of its evaluation is totally
undefined. In Rebol the expression:
beast 1
Produces only stack overflow, but that is the best thing we can expect. If F
supplied as an argument to ??? tried to evaluate its argument e.g. like:
f: func [x] [x 1 0]
Then, although the result of F should be 0 for X being a function taking one
argument, the result of ??? :f cannot be evaluated. Similarly any attempt to
supply a function evaluating its argument or any attempt to allow such an
evaluation later cannot produce a sensible result, because ??? is a
self-referencing definition.
Nice indeed.
[19/21] from: larry:ecotope at: 12-Aug-2001 17:08
Hi Ladislav,
OK, I will stop teasing. The mystery function ??? is actually a very famous
function with the rather imposing name "the applicative-order Y-combinator".
Its derivation was a culminating point in the development of the lambda
calculus (the mathematical theory underlyling functional programming). It is
also known as the Paradoxical Combinator and the *dreaded* Y-combinator. I
must say that it is a truly mind-stretching function, even when you have
done a derivation of it, it still seems like black magic.
There have been recent discussions of the implementation of Y in Perl,
Scheme, Ruby, Java, and the lambda calculus on the web:
http://lambda.weblogs.com/discuss/msgReader$838
And now we also have a version in REBOL.:-)
Although paradoxical, it is actually a useful function (especially in the
lambda calculus, because it is what allows recursion).
The applicative-order Y-combinator in REBOL:
Y: func [g][
do
func [h][h :h]
cfunc [f][g func [x][do f :f x]]
]
I found that it requires only one use of cfunc (the function that makes
functions that remember their args). My simple cfunc is included below for
those who wish to try this version. Ladislav's e-func will work just as
well. Alternatively, we can replace the single use of cfunc with an
equivalent USE block, thus making Y self-contained:
Y: func [g][
do
func [h][h :h]
func [f][use [h][h: :f g func [x][do h :h x]]]
]
We can define the "self-application" U-combinator as:
U: func [f][f :f]
Then the second version of Y can be written as:
Y: func [g][
U func [f][use [h][h: :f g func [x][do h :h x]]]
]
The Y-combinator is a very special function because it generates the
fixed-point of its function argument. It satisifes the following equation:
(g (Y g)) = (Y g) (g (g (Y g))) = (Y g) and so on.
We will test this in a bit.
The Why of Y
We know that we can use a function without giving it a name, e.g.
>> do func [x][x + 12] 5
== 17
But consider a recursive function like the recursive version of factorial:
fact: func [n][
either zero? n [1][n * fact n - 1]
]
Here it seems, the name fact for the function is required in order to obtain
the recursion. But one can avoid naming the function and still get the
recursion. In a nutshell, this is what Y does. I will illustrate it's use on
the fact function.
Step 1) We want to use functional abstraction to remove the reference to
fact in the global context from the body. We can do this with a function
wrapper made like this:
fact*: func [fact][
func [n][
either zero? n [1][n * fact n - 1]
]
]
So the function to be applied in the body for the next recursion is passed
in as an argument. Notice the code in the body of fact has not been changed.
Making the wrapper just means creating a func with an arg of the same name
as the name of the function used in the body for the recursion step. Notice
that fact* is not recursive.
This is the kind of function which Y needs for its argument. Y will
instantly turn this kind of function into one that recurs as often as
needed. The inner func must have a termination condition or the application
of Y will create a function that loops forever.
Step 2)
Now we can define the recursive factorial we want as:
>>fact: Y :fact*
>> fact 12
== 479001600
>> source fact
fact: func [n][
either zero? n [1] [n * fact n - 1]
]
This is a bit misleading because the two occurences of fact are unrelated,
we could have named the outer function anything we wanted.
But we still seem to be using a variable name for one of our functions. This
is easily avoided by substituting the definition of fact* as the arg for Y:
fact: Y func [fact][
func [n][either zero? n [1][n * fact n - 1]]
]
Look Ma! No Names.
This is the final product, a recursive version of factorial which does not
require any external name resolution for the recursion function in the inner
body. It can be shown that Y is a universal recurser (i.e., it can be used
to recursively reduce any wrapped recursive function).
Now we can test the fixed-point property with respect to the fact* function.
>> do Y :fact* 5
== 120
>> do fact* Y :fact* 5
== 120
>> do fact* fact* Y :fact* 5
== 120
>>
So (Y fact*) is indeed a fixed-point of fact*.
The Y-combinator has been an object of fascination in computer science since
Church invented it in the 30's. It has also apparently struck fear in the
hearts of many students.
My own reaction is: Wow! Y is possibly the most clever and devious function
I have seen. It's fun stretching your mind and Y is guaranteed to do that.
There are some good references on the web with derivations of Y, mostly in
the Scheme language:
http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html
http://www.mactech.com/articles/mactech/Vol.08/08.01/DazeY/
http://www.mactech.com/articles/mactech/Vol.07/07.05/LambdaCalculus/index.ht
ml
http://www.mit.edu/afs/athena/project/adedev/elk/tst/Y
There is also a good derivation in Chapter 9 of "The Little Schemer" by
Friedman and Felleisen. This is repeated with extensive annotation by Jim
Weirich in the Scheme link of the URL at the top of this note. His final
comment:
;; I've walked through the entire thing, and can say I believe I
;; understand each step, but the wonder of the entire process leaves
;; my mind boggled.
Ladislav, could you please check all the functions I give above, and see if
I went too far in eliminating the use of cfunc. Let me know if you see a
better way to present the Y function.
Try applying it to your favorite recursive function.
Enjoy
-Larry
PS I am looking forward to your further comments on Y, especially with
regard to your comments below. BTW There is another way to produce recursive
anonymous functions using just the U combinator combined with a small change
in the original recursive function body.
---------code for cfunc --------------------
cfunc: func [spec body /local args][
args: copy []
repeat el spec [if word? :el [append args to-get-word :el]]
func spec compose/deep [
do append reduce [func [(spec)][(body)]][(args)]
]
]
[20/21] from: larry:ecotope at: 12-Aug-2001 21:42
Hi Ladislav, all
Latest News Flash from the Y front.
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
[21/21] 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:
<<quoted lines omitted: 17>>
> 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
<<quoted lines omitted: 6>>
> 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
Ladislav
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted