[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
