[clean-list] Memoization of recursive functions using Clean arrays

[Pieter Koopman]

Hi Maks,

1) Most likely you have to recompile _SystemArray with the -ci flag 
(throw away the .o object file).

2) For instance
memoize :: ((Int -> e) -> (Int -> e)) Int -> (Int -> e)
memoize f max = select (memo f max)
where
     memo :: ((Int -> e) -> (Int -> e)) Int -> {e}
     memo f max = array
     where array = { f (select array) i \\ i <- [0..max] }

fib :: (Int -> Int)
fib =: memoize fib_rec 10000

The essential thing is that you need to specify what kind of array you 
want in order to solve the overloading. When you do this directly the 
type of a local an global type variable have to be equal, this is 
something the type checker does not like. The standard solution is to 
add an argument to fix the the type. The additional level of local 
functions solve all problems. Here it is 'accidental' that memoize and 
memo use the same type variable e, it are different variables.

3) It is essential to define the memo object as a local constant, that 
is a definition without arguments. In that way it will become a local 
graph which is shared in all compuations. Each local definition with 
arguments is a function. Functions are lifted to the global level by the 
compiler an evaluated for each argument all over again. This is exactly 
what you try to avoid.
\y -> f x y is a (anonymous) function, while f x is just a function 
application. They are beta equal (that is: they reduce to the same 
value) but not operational equal.

Have fun,

Pieter

On 20/08/2012 5:15 PM, Maks Verver wrote:
> Hi Pieter,
>
> On Mon, 20 Aug 2012 12:54:38 +0200
> Pieter Koopman <pieter at cs.ru.nl> wrote:
>> By using =: in the definition of memo instead of =, you create a
>> graph that is evaluated at most once.
> Thanks, I had overlooked the differences between graphs/constants and
> global/local definitions.  Using =: does allow me to solve my problems,
> but it also raises a couple more questions.
>
> I've now rewritten my code like this:
>
>    fib_rec :: (Int -> Int) Int -> Int
>    fib_rec _ 0 = 0
>    fib_rec _ 1 = 1
>    fib_rec f i = (f (i - 2) + f (i - 1)) rem 1000000
>
>    memoize :: ((Int -> Int) -> Int -> Int) Int -> (Int -> Int)
>    memoize f max = g
>        where
>            g = select memo
>            memo :: {Int}
>            memo = { f g i \\ i <- [0..max] }
>
>    fib =: memoize fib_rec 10000
>
> The =: in the last line is required to prevent the memo from being
> recomputed unnecessarily.  However, there are a couple of weird
> things about this code:
>
>   1. My program segfaults when I try to call fib with an argument
> outside the range of the array, even when compiling with -ci.  Of
> course that can't work, but I'd expect an array-index-out-of-bounds
> error in that case.  Could this be a bug in the code generator?
>
>   2. I'd like the type of `memoize' to be ((Int -> a) -> Int -> a) Int ->
> (Int -> a).  But in that case I don't know how to type memo; {a} is not
> allowed, and omitting the type of memo entirely fails due to unresolved
> overloading.  Is there a solution for this?
>
>   3. The desired sharing of memo seems to occur only if I define g as a
> partially applied function.  For example, defining:
>      g i = memo.[i]
> or:
>      g i = select memo i
> or:
>      g =: \i -> memo.[i]
> ... results in the memo being recomputed for every invocation of g (and
> thus exponential runtime).  But if I use a list instead of an array
> for the memo, this doesn't occur: `g i = memo!!i' works fine.
>
> Apparently (\y -> f x y) isn't equivalent to (f x).  That's really
> surprising!
>
>   - Maks.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.science.ru.nl/pipermail/clean-list/attachments/20120821/d7c7273e/attachment.html>