## [REBOL] Re: Fun with literal blocks!

### 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 > 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-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