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

Fun with literal blocks!

 [1/18] from: joel:neely:fedex at: 26-Oct-2000 23:25


How about some non-curmudgeonly comments on a unique REBOL idiom, the appearance of literal blocks in function bodies? This can be a handy tool to *GREATLY* improve performance in some cases. The technique, well-known in formal computing science, is known as memo-ization. The guinea pig of choice for demonstrating this technique is the old familiar Fibonacci series. That series (well-known to breeders of imaginary rabbits everywhere) can be recursively defined by knowing that Fibonacci n = if n = 0, 0 if n = 1, 1 otherwise, Fibonacci n-1 + Fibonacci n-2 As the last line can be rewritten as Fibonacci n-2 = Fibonacci n - Fibonacci n-1 we can understand Fibonacci as a total function over the integers, with typical small values such as n: ... -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ... Fibonacci n: ... 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 ... Notice that the positive and negative values have the relationship Fibonacci -n = if odd n, Fibonacci n if even n, - Fibonacci n With those facts in hand, we can compose the more-or-less classic recursive function fibo: func [n [integer!] /local t] [ either n < 0 [ t: fibo - n either odd? n [ t ][ - t ] ][ either n = 0 [ 0.0 ][ either n = 1 [ 1.0 ][ (fibo (n - 1)) + (fibo (n - 2)) ] ] ] ] This definition is correct, but performs very poorly as the argument becomes larger -- in fact, requiring exponential time. A quick benchmark confirms this (on a slow box...) for n 0 24 1 [ wall: now/time prin [n fibo n] print [" " now/time - wall] ] 0 0 0:00 1 1 0:00 2 1 0:00 3 2 0:00 4 3 0:00 5 5 0:00 6 8 0:00 7 13 0:00 8 21 0:00 9 34 0:00 10 55 0:00 11 89 0:00 12 144 0:00 13 233 0:00 14 377 0:00:01 15 610 0:00 16 987 0:00 17 1597 0:00:01 18 2584 0:00:01 19 4181 0:00:01 20 6765 0:00:03 21 10946 0:00:03 22 17711 0:00:07 23 28657 0:00:09 24 46368 0:00:16 Each increase by 1 of the argument multiplies the run time by about 1.6 (as we get large enough values to settle down). The problem, of course, is that many (most) values are computed over and over as the recursion descends and ascends. To illustrate the pattern of recursion (using an abbreviation of F for the function): F 5 | -------------^------------- / \ F 4 F 3 | | --------^------- ----^---- / \ / \ F 3 F 2 F 2 F 1 | | | | -----^----- ---^--- ---^--- 1 / \ / \ / \ F 2 F 1 F 1 F 0 F 1 F 0 | | | | | | ---^--- 1 1 0 1 0 / \ F 1 F 0 | | 1 0 Computing F 5 makes the following number of calls for each argument F 5 1 F 4 1 F 3 2 F 2 3 F 1 5 F 0 3 and it only gets worse as we go up. Wouldn't it be nice to cache each value, and avoid ever computing a value which is in the cache? Enter the REBOL literal series! fibonacci: func [n [integer!] /local t cache] [ cache: [1.0] either n < 0 [ t: fibonacci - n either odd? n [ t ][ - t ] ][ either n = 0 [ 0.0 ][ while [n > length? cache] [append cache none] if none? t: pick cache n [ poke cache n t: (fibonacci (n - 1)) + (fibonacci (n - 2)) ] t ] ] ] The literal series referenced by Cache contains previously-known values for positive values of N, so that pick cache n = fibonacci n whenever that position in Cache has been set to a number. Since we know the base case of Fibonacci 1 = 1, we initialize the literal series referenced by Cache to contain 1 at position 1 (as in the earlier function Fibo, we'll use decimal! values to allow larger values to be computed without overflow). After handling negative arguments (done as in Fibo) and taking care of zero arguments, our modified Fibonacci function first ensures that Cache is big enough to save the result for the current argument (if it's not already). Then it checks to see if the result for the current argument is already available in Cache. It does the recursive calculation only if needed, saving the result into Cache. Finally, the result (retrieved or newly- computed) is returned. Using the same benchmark scheme as before, we see a big improvment in speed -- as in too fast to measure! for n 0 24 1 [ wall: now/time prin [n fibonacci n] print [" " now/time - wall] ] 0 0 0:00 1 1 0:00 2 1 0:00 3 2 0:00 4 3 0:00 5 5 0:00 6 8 0:00 7 13 0:00 8 21 0:00 9 34 0:00 10 55 0:00 11 89 0:00 12 144 0:00 13 233 0:00 14 377 0:00 15 610 0:00 16 987 0:00 17 1597 0:00 18 2584 0:00 19 4181 0:00 20 6765 0:00 21 10946 0:00 22 17711 0:00 23 28657 0:00 24 46368 0:00 Examining the function afterwards shows that the cache has been put to use:
>> source fibonacci
fibonacci: func [n [integer!] /local t cache][ cache: [1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368] either n < 0 [ t: fibonacci - n either odd? n [t] [- t] ] [ either n = 0 [ 0 ] [ while [n > length? cache] [append cache none] if none? t: pick cache n [ poke cache n t: (fibonacci (n - 1)) + (fibonacci (n - 2)) ] t ] ] ] Of course, the nice thing is that all of those cached values are still there, ready for any future calls to Fibonacci. Persistence pays off! -jn-

 [2/18] from: lmecir:geocities at: 27-Oct-2000 9:13


Hi Joel, picking the WYSIWYG flag and trying to answer ;-)
> How about some non-curmudgeonly comments on a unique REBOL idiom, the > appearance of literal blocks in function bodies? >
My purpose here is to non-curmudgeonly present a WYSIWYG approach to Rebol programming, as I stated before.
> This can be a handy tool to *GREATLY* improve performance in some > cases.
Not at all, see below!
> The technique, well-known in formal computing science, is > known as memo-ization. The guinea pig of choice for demonstrating
<<quoted lines omitted: 187>>
> Persistence pays off! > -jn-
Why not use a WYSIWYG code (code which doesn't try to modify itself during its execution, but does everything we need): fibonacci-cache: copy [1.0] fibonacci: function [n [integer!]] [t] [ either n < 0 [ t: fibonacci - n either odd? n [ t ][ - t ] ][ either n = 0 [ 0.0 ][ insert/dup tail fibonacci-cache none n - length? fibonacci-cache if none? t: pick fibonacci-cache n [ poke fibonacci-cache n t: (fibonacci (n - 1)) + (fibonacci (n - 2)) ] t ] ] ] Regards Ladislav

 [3/18] from: joel:neely:fedex at: 27-Oct-2000 7:30


[rebol-bounce--rebol--com] wrote:
> How about some non-curmudgeonly comments on a unique REBOL idiom, the > appearance of literal blocks in function bodies? >
It is possible to make the memo-izing Fibonacci function a bit more tense, but at the usual cost of decreased obviousness. The prior version is called Fibon below, the slightly-more-bummed version is the new Fibonacci: fibon: func [n [integer!] /local t cache] [ cache: [1.0] either n < 0 [ t: fibon - n either odd? n [ t ][ - t ] ][ either n = 0 [ 0.0 ][ while [n > length? cache] [append cache none] if none? t: pick cache n [ poke cache n t: (fibon (n - 1)) + (fibon (n - 2)) ] t ] ] ] The reason for using Pick and Poke would be to make explicit the relationship between N and T; the purpose of the None-appending loop was to ensure that Poke would not be grumpy. We can leave N implicit upon caching and arrive at: fibonacci: func [n [integer!] /local t cache] [ cache: [1.0] either n < 0 [ t: fibonacci - n either odd? n [ t ][ - t ] ][ either n = 0 [ 0.0 ][ if none? t: cache/:n [ append cache t: (fibonacci (n - 1)) + (fibonacci (n - 2)) ] t ] ] ] -jn-

 [4/18] from: joel:neely:fedex at: 27-Oct-2000 7:44


[rebol-bounce--rebol--com] wrote:
> Hi Joel, >
[...snip...]
> My purpose here is to non-curmudgeonly present a WYSIWYG approach to > Rebol programming, as I stated before. > > > > > This can be a handy tool to *GREATLY* improve performance in some > > cases. > > Not at all, see below! >
Certainly agreed! It only helps performance when: 1) the recursion causes the same argument to be revisited many times in a single "top-level" use of the function, gaining performance improvement at each call, or 2) the function is simply (unavoidably) quite expensive to compute, so that caching can provide performance improvement on subsequent calls with the same (or smaller) argument(s). I probably should have been more explicit about that!
> Why not use a WYSIWYG code (code which doesn't try to modify itself > during its execution, but does everything we need): > > fibonacci-cache: copy [1.0] > fibonacci: function [n [integer!]] [t] [ >[...snip...] >
That is, of course, a quite valid way to do the memo-izing. It is certainly less "tricky". My main reason for not doing it that way is that it puts 2 names in the global namespace for 1 function. I can think of other cases the natural combination of auxiliary functions and memo-ization would require even more names. As I prefer to hide implementation from interface, and avoid any unnecessary pollution of the global namespace, I would actually code a memo-ized Fibonacci as an object in most cases. Fibonacci: make object! [ cache: array/initial 100 none f: function [n [integer!]] [t] [ ... ] ]
> insert/dup tail fibonacci-cache none n - length? fibonacci-cache >
Thanks for the reminder! That is, of course, better than the brute-force loop of my original version! -jn-

 [5/18] from: ptretter:charter at: 27-Oct-2000 7:54


How can you reference the function your defining within itself. Is this good practice? Paul Tretter

 [6/18] from: lmecir:geocities at: 27-Oct-2000 15:11


Hi Joel,
> > > This can be a handy tool to *GREATLY* improve performance in some > > > cases.
<<quoted lines omitted: 9>>
> calls with the same (or smaller) argument(s). > I probably should have been more explicit about that!
The one that wasn't explicit enough was me, this time. I wanted to say, that Memoizing *can* help to improve the performance, but that the usage of literal blocks and creating non-WYSIWYG code *cannot*! Regards Ladislav

 [7/18] from: joel:neely:fedex at: 27-Oct-2000 10:21


Hi, Ladislav, I think we'll just have to agree to disagree then (which is perfectly OK). [rebol-bounce--rebol--com] wrote:
> Memoizing *can* help to improve the performance, but that the usage of > literal blocks and creating non-WYSIWYG code *cannot*! >
Apples and oranges! I see it thus: The "interesting" behavior of literal series values and SMC are simply language features of REBOL (which one may choose to use -- or not). Memoizing is a design technique for improving the speed of some functions. When I said, speaking of literal-block tricks, "This can be a handy tool ..." --- to achieve a performance improvement, I simply meant that it was one of several possible ways of achieving that goal, not that it was the only way. -jn- -- ; Joel Neely [joel--neely--fedex--com] 901-263-4460 38017/HKA/9677 REBOL [] do [ do func [s] [ foreach [a b] s [prin b] ] sort/skip do function [s] [t] [ t: "" foreach [a b] s [repend t [b a]] t ] { | e s m!zauafBpcvekexEohthjJakwLrngohOqrlryRnsctdtiub} 2 ]

 [8/18] from: joel:neely:fedex at: 27-Oct-2000 10:12


Hi, Paul, [rebol-bounce--rebol--com] wrote:
> How can you reference the function your defining within itself. Is this > good practice? >
I'm not sure that I understand the question. If you mean "How can the definition to Fibon contain calls of Fibon?" Then I'd answer that this is simply the fact that Fibon is a recursive function. If you mean "Should Fibon be written as self-modifying code?" then (see my answer to Ladislav's comments on the same post) I'd answer that there are certainly some pros and cons to SMC. It is certainly a technique that should be used with care. OTOH, there are some very elegant things that can be done with functions that either: * maintain persistent state via SMC (less overhead vs full-blown objects), * construct and then evaluate code blocks "on the fly", or * can examine (and modify) their own operation for explanation or optimization. The whole history of AI is full of examples of the latter two. Please let me know if I failed to get your meaning. -jn- -- ; Joel Neely [joel--neely--fedex--com] 901-263-4460 38017/HKA/9677 REBOL [] do [ do func [s] [ foreach [a b] s [prin b] ] sort/skip do function [s] [t] [ t: "" foreach [a b] s [repend t [b a]] t ] { | e s m!zauafBpcvekexEohthjJakwLrngohOqrlryRnsctdtiub} 2 ]

 [9/18] from: lmecir:geocities at: 28-Oct-2000 9:03


Hi Joel,
> If you mean > "Should Fibon be written as self-modifying code?"
<<quoted lines omitted: 3>>
> elegant things that can be done with functions that either: > * maintain persistent state via SMC (less overhead vs full-blown objects),
I think, that you are mixing two issues here. One is a use of SMC and the second one is the ability of a function to maintain its state or to do other useful things... The most general version of the state-maintaining technique is a possibility to create a function having static local variables. Here are my 3 implementations of that: ; 1) this version of Sfun creates a function having static local variables ; using an embedded object to maintain its state sfun: function [ {Create a function with static local variables} init [block!] args [block!] body [block!] ] [ini] [ ini: make-object init body: compose [ (ini) (bind/copy :body in ini 'self) ] func :args :body ] ; a Make Object! modification allowing any Self make-object: function [ {make object} blk [block!] "object spec" ] [result getres] [ getres: func [value] [result: :value] blk: compose [(:getres) :self (blk)] error? make object! copy/deep blk result ] { Example #1: counter: sfun [self: 0] [] [ self: self + 1 print self ] counter counter recycle counter Example #2 cell: func [ {create a function that holds a value} initval [any-type!] ] [ sfun [value: none set/any 'value get/any 'initval origset: :set] [ /set newval [any-type!] ] [ either set [origset/any 'value get/any 'newval] [ get/any 'value ] ] ] a: cell 5 print a a/set 18 print a Example #3 cell: func [ {create a function that holds a value} require-type [datatype!] initval [any-type!] /local result ] [ result: sfun [value: none origset: :set] [ /set newval [require-type] ] [ either set [origset/any 'value get/any 'newval] [ get/any 'value ] ] result/set get/any 'initval :result ] a: cell 5 print a a/set 18 print a } ; 2) this version of Sfun uses a Use technique, ; is *much* more elegant, totally WYSIWYG, ; it doesn't always have a static local 'Self as opposed to 1), ; but the GC bug doesn't allow it to work sometimes :( ; I wrote it to show, that the only reason ; for using a SMC technique ; may be to circumvent the GC bug ; (out of a frying pan and into the fire) sfun: function [ {Create a function with static local variables} init [block!] args [block!] body [block!] ] [words] [ words: make block! 0 foreach elem init [ if set-word? get/any 'elem [ append words to word! :elem ] ] use union words [] copy/deep reduce [ :do :init :func :args :body ] ] { Example #1: counter: sfun [self: 0] [] [ self: self + 1 print self ] counter counter counter counter } ; 3) this version creates an object behaving like ; a function having static local variables, ; the code is totally WYSIWYG too, ; and the GC bug doesn't have a chance: sfun: func [ {Create a function with static local variables} init [block!] args [block!] body [block!] ] [ make-object [ ini: make-object init do: func args bind/copy body in ini 'self ] ] { Example #1: counter: sfun [self: 0] [] [ self: self + 1 print self ] counter/do counter/do recycle counter/do }
> * construct and then evaluate code blocks "on the fly", or > * can examine (and modify) their own operation for explanation or > optimization. > > The whole history of AI is full of examples of the latter two.
Just a comment: my definition of SM/WYSIWYG Code is *much weeker*, than a "normal" one. That means, that you *can* use a Rebol WYSIWYG code to construct and then evaluate code blocks "on the fly". Similarly it is possible to examine and modify the operation of functions. E.g. the code: code: [ a: copy [1 remove a 2] do copy a ] is WYSIWYG according to the defininion I supplied.

 [10/18] from: joel:neely:fedex at: 28-Oct-2000 18:12


Hi, Ladislav, Thanks for the very interesting techniques. I want to think carefully about them before making any comments. (I might embarrass myself it I didn't think hard enough!) Ladislav Mecir wrote:
> Hi Joel, > > If you mean
<<quoted lines omitted: 9>>
> > * maintain persistent state via SMC > > (less overhead vs full-blown objects),
...and I'd be happy to have this list extended with techniques such as those you supplied.
> I think, that you are mixing two issues here. One is a use of SMC > and the second one is the ability of a function to maintain its > state or to do other useful things... >
Well, again, I simply think of SMC as being one (of a growing number, thanks to you and others) way to maintain internal "state". Clearly the use of objects is an important technique, whether explicitly created, or supplied by an "object factory', etc.
> The most general version of the state-maintaining technique is a > possibility to create a function having static local variables... >
I tend to draw a distinction between: * code such as Fibon, which modifies values stored inside itself, but which only uses those values as stored state data, and * monsters such as the following, which modify portions of them- selves which then will actually be evaluated in a CODE-like manner, and which therefore stress our minds (and, apparently, the REBOL interpreter!) much harder.
>> a: [append a [+ 1] 1]
== [append a [+ 1] 1]
>> repeat i 30 [print [i do a]]
1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 14 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 30 Note: 7 skipped, 14 duplicated, 15 skipped, 30 duplicated... Something VERY bizarre is going on here. Is this a bug or an undocumented feature? ;-) -jn-

 [11/18] from: lmecir:geocities at: 29-Oct-2000 16:06


Hi Joel, thank you for choosing the Monsters subject. I would like to present a somewhat surprising/questionable point of view. 1) A safe statement: the Monsters are undocumented. 2) A questionable statement: the Monsters are *undocumentable*. I know that it is wrong, if I don't add an explanation, what that means. Let's go: Let me define the Monsters first. a) I call a Rebol value a Self Modifying (Rebol Code), if its evaluation (with a help of Do e.g.) causes its change (to be precise, I should define what is a Change, but let's leave that for a future discussion). (This definition differs from a "usual" definition of a Self Modifying Code!) b) I call a Rebol value a WYSIWYG (Rebol Code), if its evaluation (using Do e.g.) doesn't cause an evaluation of a Self Modifying Rebol Code. c) There are some Rebol values, like functions/natives If, Either, For, While, Make, ..., for whose the latter depends on the argument(s) they receive or on some other unknowns. Such values I call (relatively) WYSIWYG. d) Any Rebol Value, that is not (at least relatively) WYSIWYG I call non-WYSIWYG. I would call a Monster any non-WYSIWYG Rebol Value. Now back to the questionable statement. I think, that: i) The behaviour of Monsters is irregular and heavily implementation-dependent (see the example Monster below, or any other Monster I supplied in the WYSIWYG programming thread). ii) Nobody can list all Monsters. iii) The one thing that could describe the behaviour of all Monsters is the interpreter source code. In the above sense are the Monsters undocumentable, which means, that their evalualuation shall be avoided as much as possible. Regards Ladislav

 [12/18] from: joel:neely:fedex at: 29-Oct-2000 14:01


Hi, Ladislav, [rebol-bounce--rebol--com] wrote:
> Hi Joel, > > thank you for choosing the Monsters subject. I would like to > present a somewhat surprising/questionable point of view. >
Debatable, perhaps, but an interesting analysis! (And surprises can be good...)
> 1) A safe statement: the Monsters are undocumented. >
Yep.
> 2) A questionable statement: the Monsters are *undocumentable*. >
In theory, I might argue with you; in practice -- given the current state of things -- I'd agree that the only adequage model would be the actual source code of the interpreter (as you stated further on).
> I know that it is wrong, if I don't add an explanation, > what that means. Let's go:
<<quoted lines omitted: 11>>
> argument(s) they receive or on some other unknowns. Such values I > call (relatively) WYSIWYG.
I understood your point (c) to cover such cases as: twiddle: func ['a [word!]] [ append second get a true ]
>> so-called-data: [[1 2 3] ["a" "b" "c"]]
== [[1 2 3] ["a" "b" "c"]]
>> twiddle so-called-data
== ["a" "b" "c" true]
>> so-called-data
== [[1 2 3] ["a" "b" "c" true]] given that someone could always do
>> second get 'twiddle
== [ append second get a true ]
>> twiddle twiddle
== [ append second get a true true ]
>> twiddle so-called-data
== true
>> so-called-data
== [[1 2 3] ["a" "b" "c" true true]] So, I take your point (a) to mean if its evaluation NECESSARILY causes its change ----------- Did I interpret correctly?
> d) Any Rebol Value, that is not (at least relatively) WYSIWYG > I call non-WYSIWYG.
<<quoted lines omitted: 3>>
> implementation-dependent (see the example Monster below, or > any other Monster I supplied in the WYSIWYG programming thread).
I agree with your general statement, although it would be possible to specify high-level (e.g. non-implementation-dependent) semantics for some cases. There would probably always be some monstors which would slip through the specificational net, no matter how tightly it was woven...
> ii) Nobody can list all Monsters. > iii) The one thing that could describe the behaviour of all > Monsters is the interpreter source code. > > In the above sense are the Monsters undocumentable, which means, > that their evalualuation shall be avoided as much as possible. >
I think we agree on goal, but I think your "guard rail" is just a bit more conservative than mine. I see a distinction between Monsters such as
>> a: [append a [+ 1] 1]
== [append a [+ 1] 1] and (to invent a bit of terminology) Safely Self-Referential Code such as count: func [/reset val [integer!] /local state] [ state: [0] either reset [ change state val ][ state/1: 1 + state/1 ] first state ]
>> count == 1 >> count == 2
<<quoted lines omitted: 4>>
>> count == 1 >> count == 2
I think it is possible to specify the semantics of a vNL such that one can write Safely Self-Referential Code without too much risk. Of course, I think we're in agreement that such code will always remain mysterious to those who are not yet familiar with REBOL's use of definitional scope and the way in which literal blocks are handled. Whether that level of mystery is unacceptable or not is (to me) more of a matter of opinion than the belief (which I think we share) that general-purpose industrial-strength Monsters should not be allowed to roam the streets, but should be kept in biohazard- equipped zoos. -jn-

 [13/18] from: lmecir:geocities at: 29-Oct-2000 23:39


Hi Joel, clever as always. You understood everything perfectly. My only point against a (safe) non-WYSIWYG code is, that the code is not as self-documenting/maintainable as a WYSIWYG code. Moreover, I still think, that with WYSIWYG I can write anything I would like to without feeling any restrictions as long, as the GC bug stops messing things in Rebol (moreover, even with non-WYSIWYG code allowed, I found some examples I would like to write in Rebol but am not able to as long, as the GC bug "works"). Two more comments: 1) A notion of vNL seems adequate, although If we recall that the Rebol intepreter is written in C, we can conclude that C (in a sense) can be used to write self-modifying code too. 2) The WYSIWYG definition I wrote/am promoting is (to be honest) my "mental model" of your idea: do to immutable-code! whatever Regards Ladislav

 [14/18] from: rishi:picostar at: 31-Oct-2000 23:04


ok. I've tried to ignore this but I have seen it referenced one to many times. So...what is the "GC" bug? Does GC stand for "Garbage Collector?" Rishi Previously, you (Ladislav Mecir) wrote:

 [15/18] from: al:bri:xtra at: 1-Nov-2000 20:15


Rishi (the evangelist ;-)) wrote:
> ok. I've tried to ignore this but I have seen it referenced one to many
times. So...what is the "GC" bug? Does GC stand for "Garbage Collector?" Yes. GC = "Garbage collector" It recycles memory that's no longer being used. The bug is that it's a little over-enthusiastic... Andrew Martin ICQ: 26227169 http://members.nbci.com/AndrewMartin/

 [16/18] from: joel:neely:fedex at: 2-Nov-2000 13:26


Hi, Rishi, Rishi Oswal wrote:
> ok. I've tried to ignore this but I have seen it referenced one > too many times. So...what is the "GC" bug? Does GC stand for > "Garbage Collector?" >
Yes. Sometimes the baby gets thrown out with the bath-water (to mix metaphors ... ;-) Here's a specific recipe for one way to invoke it: make-bump: func [n [number!]] [ do func [nn [number!]] [ func [m [number!]] [m + nn] ] n ]
>> onemore: make-bump 1 >> onemore 5 == 6
<<quoted lines omitted: 5>>
>> recycle >> onemore 5
at which point REBOL goes to South Dakota, leaving no forwarding address... Now you may ask yourself, "Self, why would *anybody* write such an odd-looking bit of code to begin with?" [ STOP READING HERE IF YOU DON'T CARE ] Well, Self, there are several reasons, one of which is In an attempt to create a "closure", which can be used as a "specialized" function to minimize argument-passing. For example: Tennessee sales tax uses two rates, "state" and "local", with a cap on how much of a "single article" price is to be taxed at the local rate. The state portion applies no matter how high the single-article price. So, we can write sales-tax: func [ stt [decimal!] loc [decimal!] cap [money!] amt [money!] ][ (stt * amt) + (loc * min amt cap) ]
>> sales-tax 0.05 0.02 $100.00 $100.00 == $7.00 >> sales-tax 0.05 0.02 $100.00 $200.00 == $12.00
We can see that 7% (state plus local) was applied only to the first $100, and 5% (state only) was applied to any amount above that cap. Instead of sprinkling four-argument functions throughout our code, we would like to encapsulate the rate data into some special-purpose functions, which can be retrieved and used as appropriate. Our first attempt to do this might be... make-sales-tax: func [ srate [decimal!] lrate [decimal!] llim [money!] ][ func [amt [money!]] [ (srate * amt) + (lrate * min amt llim) ] ] Make-sales-tax just creates and returns a function that does needs only the amount; it uses the rate and limit information from make-sales-tax...(we might think!) Gotham-sales-tax: make-sales-tax 0.05 0.03 $100.00 The "function factory" gives us a function that now has those values plugged in, so the correct calculations are done...
>> Gotham-sales-tax $100.00 == $8.00 >> Gotham-sales-tax $200.00 == $13.00
That worked so well, that we'll try it again... Smallville-sales-tax: make-sales-tax 0.05 0.01 $100
>> Smallville-sales-tax $100.00 == $6.00 >> Smallville-sales-tax $200.00 == $11.00 >> Gotham-sales-tax $220.00 == $12.00
Whoops! How come the Gotham sales tax is less on $220 than on $200??? It's because the Srate, Lrate, and Llim inside any function from the function factory are actually in the context of Make-sales-tax. Changing one changes them all. One way around this (we might think...) is to ensure that a new context is established each time we call on the factory to give us a new sales tax function. Since function contexts are (apparently) constructed when the function is *defined* (not for each invocation), we can try defining and immediately invoking a function-defining function inside the function factory. (What a tongue-twister!) sales-tax-factory: func [ srate [decimal!] lrate [decimal!] llim [money!] ][ do func [stt [decimal!] loc [decimal!] cap [money!]] [ func [amt [money!]] [ (stt * amt) + (loc * min amt cap) ] ] srate lrate llim ]
>> Bigtown-sales-tax: sales-tax-factory 0.05 0.02 $100.00 >> Bigtown-sales-tax $100.00 == $7.00 >> Bigtown-sales-tax $200.00 == $12.00
So far, so good...
>> Smalltown-sales-tax: sales-tax-factory 0.05 0.01 $100.00 >> Smalltown-sales-tax $100.00 == $6.00 >> Smalltown-sales-tax $200.00 == $11.00 >> Bigtown-sales-tax $200.00 == $12.00
Hooray! It works -- until the next garbage collection, that is!
>> recycle >> Bigtown-sales-tax $150.00 Kaboom!
It appears that GC is concluding that the "hidden" function context is no longer in use and is wiping it out. That's only an inference on my part, but the above behavior is reliably reproducible. Closures are handy. We should be able to use them (and some other higher-order-function techniques) once GC stops being so greedy. -jn- -- ; Joel Neely [joel--neely--fedex--com] 901-263-4460 38017/HKA/9677 REBOL [] foreach [order string] sort/skip reduce [ true "!" false head reverse "rekcah" none "REBOL " prin "Just " "another " ] 2 [prin string] print ""

 [17/18] from: jeff:rebol at: 2-Nov-2000 11:27


Howdy, Joel:
> make-sales-tax: func [ > srate [decimal!] lrate [decimal!] llim [money!]
<<quoted lines omitted: 3>>
> ] > ]
or.. if you're feeling nutty: make-sales-tax: func [ srate [decimal!] lrate [decimal!] llim [money!] ][ func [amt [money!]] compose [ (to-paren compose [(srate) * amt]) + (to-paren compose [(lrate) * min amt (llim)]) ] ] Gotham and smallville get paid correctly and the GC stays happy. -jeff

 [18/18] from: lmecir:geocities at: 2-Nov-2000 21:27


Tax functions available! If anybody is missing tax functions after Joel's lucid explanation, there is a way: sales-tax: func [ stt [decimal!] loc [decimal!] cap [money!] amt [money!] ][ (stt * amt) + (loc * min amt cap) ] make-sales-tax: curry :sales-tax 3 Gotham-sales-tax: make-sales-tax 0.05 0.03 $100.00 Smallville-sales-tax: make-sales-tax 0.05 0.01 $100 Smallville-sales-tax $100.00 == $6.00 Smallville-sales-tax $200.00 == $11.00 Gotham-sales-tax $100.00 == $8.00 Gotham-sales-tax $200.00 == $13.00 The only thing you need is http://www.rebol.org/advanced/highfun.r Regards Ladislav

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted