[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
