Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

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