Arc Forum | Does memo work right?

Arc Forum

Does memo work right?

5 points by zhtw 5866 days ago | 7 comments

When f returns smth other than nil then (memo f) works just fine, but if f returns nil then (memo f) calls f again and again when being called itself:

  arc> (def f ()
         (prn "called") 10)
  #<procedure: f>
  arc> (set g (memo f))
  #<procedure>
  arc> (g)
  called
  10
  arc> (g)
  10

This is ok. Now this:

  arc> (def f () (prn "called") nil)
  #<procedure: f>
  arc> (set g (memo f))
  #<procedure>
  arc> (g)
  called
  nil
  arc> (g)
  called
  nil

See? f is called twice. I clearly see why from arc.arc, but is it really an intended behavior?

1 point by skenney26 5866 days ago | link

You could write a more complicated check within memo that examined whether the arguments had been passed before. This would probably slow down lookup though and not give much of a net gain.

-----

3 points by eds 5864 days ago | link

> You could write a more complicated check within memo that examined whether the arguments had been passed before.

This is exactly what memo does right now: it just stores the args to 'f in a hash table and looks them up whenever 'f gets called.

  (def memo (f)
    (let cache (table)
      (fn args
        (or (cache args)
            (= (cache args) (apply f args))))))

The problem which prevents this from working nicely with nil is that hash tables in Arc do not distinguish between the value nil and a key simply not being there. The workaround is to use a default value (generally a symbol returned by (uniq)) to guarantee uniqueness for the case when the key does not exist.

See http://arclanguage.org/item?id=8566 for more information.

-----

2 points by zhtw 5862 days ago | link

Actually I know why it happens and how to fix that. The question was more like "is it a bug or a feature?" I remember that PG suggested (but forgot where I read that) to store cons' in a table when you need to distinguish nil and absence of an element but why doesn't he use that technique (or any other) himself?

-----

2 points by skenney26 5862 days ago | link

I think the simple answer is that he hasn't needed that feature. 'memo and 'defmemo are used in 5 places in news.arc and it doesn't look like any of those uses would benefit from allowing nil as a value.

If someone created an application that benefited from that feature then perhaps there would be reason to redefine 'memo.

This seems to be an important part of the Arc philosophy: add a feature only when its absolutely needed.

-----

1 point by zhtw 5859 days ago | link

Only now I realized that you treat memo as some kind of the way to improve performance (do you?). What I used memo for is to make sure that function won't be called twice:

  (mac delay (e)
    `(memo (fn () ,e)))

  (def force (d) (d))

When I use lazy sequences (of symbols read from input port for example) based on these definitions I can't be sure that readc somewhere inside will never be called twice if I call force for an element of this sequence twice.

So I treat this as a bug. Or maybe I'm just wrong about what memo is for at all. Am I?

-----

1 point by aaronla 5848 days ago | link

I'd venture to guess that memo creates a new cache for each invocation, so two calls

  (map (lambda (f)  ;; invokes f 3 times
               (f) (f) (f) )
       (list (delay (foo bar)) 
             (delay (foo bar))))

I think thiw will call foo exactly twice, because each memo invokation produces a new cache, but I may be mistaken.

[pardon the syntax... this is in scheme. i have only just installed arc and (def hello-world ...) is as far as i've gotten]

-----

1 point by absz 5848 days ago | link

The real problem is that if you do

  (let d (delay (foo bar))
    (force d)
    (force d))

, then there's no guarantee that (foo bar) will be run exactly once---if (foo bar) returns nil, then it won't be cached.

-----