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 <[email protected]> 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.
_______________________________________________
clean-list mailing list
[email protected]
http://mailman.science.ru.nl/mailman/listinfo/clean-list
