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

[REBOL] Functional programming in REBOL

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