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

[Pieter Koopman]

Hi Maks,

Your typed identity function

idLazyArray :: {a} -> {a}
idLazyArray a = a

is a smart way to solve the overloading for the array.

Adding a type to a local definition always turns it into a function. 
This explains way adding a type to memo makes your program slow. You are 
completely right: the compiler should complain if it wants to treat a 
definition as a function while the user indicates with a =: that it 
should be a constant.

In the future we will most likely add special notation to indicate 
strict or unboxed arrays. For situations like this it is also desirable 
to have syntax that indicates lazy arrays.

In some situations it is desirable to be able to indicate the type of 
local constants. A Haskell like notation to indicate the type of 
expressions is a solution we are considering.

Best, Pieter

On 22/08/2012 8:44 PM, Maks Verver wrote:
> On Tue, 21 Aug 2012 13:16:51 +0200
> Pieter Koopman <pieter at cs.ru.nl> wrote:
>> 1) Most likely you have to recompile _SystemArray with the -ci flag
>> (throw away the .o object file).
> That's it.  For future reference, I did this:
>
>    make -C path-to-clean-dir CLMFLAGS+=-ci cleanup install
>
>
>> 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] }
> I see.  That's a useful trick, though in this case you've reshuffled
> the definitions considerably.
>
> In this case I can also fix my problem by introducing a function to
> restrict the kind of array used:
>
>    lazyArray :: u:{a} -> u:{a}
>    lazyArray a = a
>
> And then stay relatively close to the original, simpler definition:
>
>    memoize :: ((Int -> a) -> Int -> a) Int -> (Int -> a)
>    memoize f max = g
>        where g = select (lazyArray {f g i \\ i <- [0..max]})
>
>> The standard solution is to add an argument to fix the the type.
> I can't imagine that's always a nice solution, considering that adding
> an argument to a constant expression apparently affects the efficiency
> of the resulting program.
>
>
>> 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.
> This sounds reasonable but I still have trouble applying this to
> concrete programs.  For example, it doesn't explain why this is fast,
> even though I use a lambda-closure:
>
>    memoize :: ((Int -> Int) -> Int -> Int) Int -> (Int -> Int)
>    memoize f max = g
>        where
>            g = \i -> memo.[i]
>            memo =: lazyArray { f g i \\ i <- [0..max] }
>
> ... while adding a type to memo makes it slow:
>
>    memoize :: ((Int -> Int) -> Int -> Int) Int -> (Int -> Int)
>    memoize f max = g
>        where
>            g = \i -> memo.[i]
>            memo :: {Int}  // <-- only added this
>            memo =: lazyArray { f g i \\ i <- [0..max] }
>
> What is the type inferred by the compiler in the first case that would
> result in a completely different kind of evaluation?
>
> Or does adding a type declaration turn `memo' from a graph into a
> (constant) function?  In that case, shouldn't the compiler reject my
> use of `=:' instead of `='?
>
>   - Maks.

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