[clean-list] Re: Question on destructive array updates

[Carlos Aya]

Hi Atilla,

The point is that one needs to perform 'createArray' only once. Fib5_, and if I understood correctly, does that every time

...
Fib5 :: Int -> Int
Fib5 n
| n >= 0 =
    let
        (res, _) = Memoize Fib5_ n (createArray (n+1) 0)
more ...

This is: for every 'n', you are saying 'createArray (n+1) 0'. So, you are not using memoization at all. And probably Memoize
is calculating everything from scratch all the time...

That's
why I defined fibm = ... in the code at top level, so that way the
definition itself, I hoped, captured this. I know that in Clean there
are differences at the top level in the meaning of '='. Sometimes
recalculates, sometimes is a macro (calculated only once). If I
remember correctly, the way I did it is a macro definition and
therefore calculated only once.

cheers
Carlos


----- Original Message ----
Date: Tue, 21 Oct 2008 17:23:13 -0400 (EDT)
From: "Attila Ondi" <aondi at fit.edu>
Subject: Re: [clean-list] Question on destructive array updates
To: clean-list at science.ru.nl
Message-ID:
    <3217.163.118.203.36.1224624193.squirrel at webaccess.fit.edu>
Content-Type: text/plain;charset=iso-8859-1

More questions :)

I was playing around with Carlos's memoization implementation, especially
after I realized it will store only the result of the topmost call (see f
n in his memo function).  After a little fiddling, this is what I came up
with to store all intermediate values:

:: *ArrayTuple a :== (a, *{a})

Memoize :: (Int -> ((Int -> (*{Int} -> ArrayTuple Int)) -> (*{Int} ->
ArrayTuple Int))) Int *{Int} -> ArrayTuple Int
Memoize f n a
| size a < n+1 = abort ("Memoize: Array is smaller than required (size: "
+++ (toString (size a)) +++ ", n: " +++ (toString n) +++ ")")
| a.[n] < 0 = abort ("Memoize: Invalid array value (n: " +++ (toString n)
+++ ", a[n]: " +++ (toString (a.[n])) +++ ")")
| a.[n] > 0 = a![n]
# (res, resa) = f n (Memoize f) a
| otherwise = {resa&[n] = res}![n]

Fib5 :: Int -> Int
Fib5 n
| n >= 0 =
    let
        (res, _) = Memoize Fib5_ n (createArray (n+1) 0)

        Fib5_ :: Int (Int -> (*{Int} -> ArrayTuple Int)) *{Int} -> ArrayTuple Int
        Fib5_ 0 _ a = (1, a)
        Fib5_ 1 _ a = (1, a)
        Fib5_ n g a
        # (res1, resa1) = g (n-1) a
        # (res2, resa2) = g (n-2) resa1
        = (res1 + res2, resa2)
    in res
| otherwise = abort ("Fib5: Called with negative parameter (n : " +++
(toString n) +++ ")")


As (obviously) the type of the function Memoize takes is the same as
Fib5_, I was trying to name that type:

:: MemoizeFun a :== a (a -> (*{a} -> ArrayTuple a)) *{a} -> ArrayTuple a
Memoize :: (MemoizeFun Int) Int *{Int} -> ArrayTuple Int
Fib5_ :: (MemoizeFun Int)

However, the compiler now treats Fib5_ as a constant.  So my question is,
is there a way to name the types of functions so I don't have to type the
full arrow and its two sides(*)?

(*) I know I don't _have_ to, but since I'm not that close to functional
programming yet, I like to see (and understand) what's going on.


Also, according to the profiler, the program spends the most time in
Memoize (compared to all other Fibonacci implementations of mine), which
is surprising to me as the implementation of Fib5 is practically the same
as my earlier attempt to use arrays (which was a specialized, interwoven
case of computation and memoization as Carlos pointed it out).  So my
question is: what is the reason for this result?

Actually, upon measuring some re-run, the time spent in Memoize varies a
lot.  Is this normal?  I know lazy evaluation allows the compiler/runtime
to do some tricks, but I expected the performance to stay the same if
running without recompilation.  Could memory allocation be the reason?

Thank you,
Attila

******************************************


Send instant messages to your online friends http://au.messenger.yahoo.com 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.science.ru.nl/pipermail/clean-list/attachments/20081021/30f90993/attachment.html