## [REBOL] Re: Functional programming in REBOL

### 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 > 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 ;-) >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). > 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 >-Volker