Mailing List Archive: 49091 messages

[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