Memoizing tree recursive calls

[Aravindh Johendran]

If we have tree recursive procedure such as the follows, how can we
use memoize it so that it automatically caches the values it has
already computed .....

(defn fib [n]
(println "Calling fib with arg --> " n)
(cond
(= n 0) 0
(= n 1) 1
:else (+ (fib (- n 1))
(fib (- n 2)))))


I changed the source for memoize - added two print statements
(defn memoize
"Returns a memoized version of a referentially transparent function.
The
memoized version of the function keeps a cache of the mapping from
arguments
to results and, when calls with the same arguments are repeated
often, has
higher performance at the expense of higher memory use."
{:added "1.0"}
[f]
(let [mem (atom {})]
(fn [& args]
(println "Calling memoized fn with args ->" args)
(if-let [e (find @mem args)]
(do (println "taking from cache"(val e) )(val e) )
(let [ret (apply f args)]
(swap! mem assoc args ret)
ret))) ))


Now memoizing and calling the function .....
(defn m-fib (memoize fib))

In this case, the INTERMEDIATE values the function computes are NOT
stored in the memoize cache.

The only way I can think of of utilizing the memoize function as such
is as follows:

(defn fib2 [my-fun n]
(println "Calling fib with arg --> " n)
(cond
(= n 0) 0
(= n 1) 1
:else (+ (my-fun my-fun (- n 1))
(my-fun my-fun (- n 2)))))

(def m-fib2 (memoize fib2))
(m-fib2 m-fib2 10)


--------------------------------------------------------------------------------

Maybe memoize should go the same way as the contrib trace package -
i.e, have special macros. "Functional" memoizing can only cover so
much .........

[Moritz Ulrich]

Offtopic: Java doesn't support tail-recursive calls, so your fib will
blow up the stack for larger ns. Use recur for recursion.

I think the tour problem is the (def m-fib (memoize fib)). You create
a new memoized function m-fib, while fib will internally call the
non-memoized fib. You have to do something like: (binding [fib
(memoize fib)] (fib 42)).
However, this will break if you use recur instead of recursive calls to fib.

On Tue, Jul 20, 2010 at 10:11 PM, Aravindh Johendran
<ajohe...@gmail.com> wrote:
> (defn m-fib (memoize fib))

--
Moritz Ulrich
Programmer, Student, Almost normal Guy

http://www.google.com/profiles/ulrich.moritz

[Michał Marczyk]

On 20 July 2010 23:41, Moritz Ulrich <ulrich...@googlemail.com> wrote:
> I think the tour problem is the (def m-fib (memoize fib)). You create
> a new memoized function m-fib, while fib will internally call the
> non-memoized fib. You have to do something like: (binding [fib
> (memoize fib)] (fib 42)).
> However, this will break if you use recur instead of recursive calls to fib.

Actually self-calls don't go through Vars, so the binding changes
nothing. Try this if you want to check it for yourself:

user=> (defn foo [x] (Thread/sleep 100) (if (zero? x) :done (foo (dec
x))))
#'user/foo
user=> (binding [foo (memoize foo)] (println (foo 10)) (println (foo
10)) (println (foo 9)))
:done ; after a delay
:done ; immediately afterwards
:done ; after another delay
nil

To force the self-call to go through the Var, you could use #'foo in
place of foo:

(defn foo [x] (Thread/sleep 100) (if (zero? x) :done (#'foo (dec x))))

If you try the above (binding ...) form with this version, you'll
notice there's no delay before the final printout.

This has a cost of its own and requires a change to the function's
code, so might not always be a good idea. It's simpler than baking a
local cache into the function itself, though; and if you've got a
self-recursive function foo written in this fashion, you can do

(alter-var-root #'foo memoize)

to memoize it "in place". (If you need the original function, you
could put it in the Var's metadata; and if at some point metadata on
functions becomes officially supported -- as opposed to being an
experimental feature -- maybe memoize could put the original function
in the memoized function's metadata.)

Sincerely,
Michał

[Mike Meyer]

On Tue, 20 Jul 2010 13:11:12 -0700 (PDT)
Aravindh Johendran <ajohe...@gmail.com> wrote:

> If we have tree recursive procedure such as the follows, how can we
> use memoize it so that it automatically caches the values it has
> already computed .....

[example elided]

> Maybe memoize should go the same way as the contrib trace package -
> i.e, have special macros. "Functional" memoizing can only cover so
> much .........

You mean something like defn-memo, which is already defined in the
clojure.contrib.def package, and seems to do exactly what you want?

<mike
--
Mike Meyer <m...@mired.org> http://www.mired.org/consulting.html
Independent Network/Unix/Perforce consultant, email for more information.

O< ascii ribbon campaign - stop html mail - www.asciiribbon.org