<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<font size="-1"><font face="Helvetica, Arial, sans-serif">Hi Maks,<br>
<br>
1) Most likely you have to recompile _SystemArray with the -ci
flag (throw away the .o object file).<br>
<br>
2) For instance<br>
memoize :: ((Int -> e) -> (Int -> e)) Int -> (Int
-> e)<br>
memoize f max = select (memo f max)<br>
where<br>
memo :: ((Int -> e) -> (Int -> e)) Int -> {e}<br>
memo f max = array<br>
where array = { f (select array) i \\ i <- [0..max] }<br>
<br>
fib :: (Int -> Int)<br>
fib =: memoize fib_rec 10000<br>
<br>
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.<br>
<br>
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.<br>
\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.<br>
<br>
Have fun,<br>
<br>
Pieter<br>
<br>
</font></font>
<div class="moz-cite-prefix">On 20/08/2012 5:15 PM, Maks Verver
wrote:<br>
</div>
<blockquote
cite="mid:20120820171533.aab29bb67d47ab297dce11cc@geocities.com"
type="cite">
<pre wrap="">Hi Pieter,
On Mon, 20 Aug 2012 12:54:38 +0200
Pieter Koopman <a class="moz-txt-link-rfc2396E" href="mailto:pieter@cs.ru.nl"><pieter@cs.ru.nl></a> wrote:
</pre>
<blockquote type="cite">
<pre wrap="">By using =: in the definition of memo instead of =, you create a
graph that is evaluated at most once.
</pre>
</blockquote>
<pre wrap="">
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.
</pre>
</blockquote>
<br>
</body>
</html>