## [REBOL] Fun with literal blocks!

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