Ben Hinkle wrote:
> "Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:dc3df6$2a7d$1@digitaldaemon.com...
> 
>>Ben Hinkle wrote:
>>
>>>>int delegate(int) memoize(Fcn f) {
>>>> Memoize m = new Memoize(f);
>>>> return &m.opCall;
>>>>}
>>>>...
>>>>int main() {
>>>> ...
>>>> int delegate(int) dg = memoize(&fib);
>>>> ...
>>>>}
>>>>
>>>>The two functionality are roughly equivalent.  The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.
>>>
>>>
>>>Good point. I agree. Here's a slightly shorter version of memoize:
>>>int delegate(int) memoize(int function(int) f) {
>>>    struct Frame {
>>>        int function(int) f;
>>>        int call(int x){return f(x);}
>>>    }
>>>    Frame* frame = new Frame;
>>>    frame.f = f;
>>>    return &frame.call;
>>>}
>>>int fib(int n){return n+10;}
>>>int main() {
>>>    int delegate(int) dg = memoize(&fib);
>>>    printf("%d\n",dg(5));
>>>    return 0;
>>>}
>>
>>Remember the caching functions.
> 
> 
> hehe - I got a little carried away in "simplifying" :-P
> 
> 
>>Also note that the caching example given above is not thread-safe.
> 
> That would actually be an advantage of using a class since it can synchronize the opCall method (or whatever method name is chosen - it doesn't really matter what the name is if the delegate is used).. 

True.  I wonder, if you take a delegate to a synchronized member function, does the member function implementation do the synchronization?  Or is it not ever legal?  Something I'll have to investigate some day, unless somebody has the answer right offhand...

"Ben Hinkle" <ben.hinkle@gmail.com> wrote:

[...]
> If you don't mind nailing down the
> signatures then it would be easy.
[...]

Are you sure?

Isnt there the restriction in D, that no function can have its own type as a parameter or as a return value?

If so then by diagonalization you cannot memoize especially a memoize-function or similar.

-manfred

"Manfred Nowak" <svv1999@hotmail.com> wrote in message news:dc8lm3$fle$2@digitaldaemon.com...
> "Ben Hinkle" <ben.hinkle@gmail.com> wrote:
>
> [...]
>> If you don't mind nailing down the
>> signatures then it would be easy.
> [...]
>
> Are you sure?
>
> Isnt there the restriction in D, that no function can have its own type as a parameter or as a return value?
>
> If so then by diagonalization you cannot memoize especially a memoize-function or similar.
>
> -manfred

uhh - this might be too esoteric for my understanding, but by "nailing down the signature" I meant it is possible to write a memoize function for the set of functions with a particular signature. I wouldn't be surprised if a memoize function couldn't memoize itself - though perhaps with some vicious use of vararg ... and/or void* casting it would be possible. I expect it would be possible to memoize another memoize function, though.

"Ben Hinkle" <bhinkle@mathworks.com> wrote:

[...]
> I wouldn't be surprised if a memoize function
> couldn't memoize itself
[...]

Then my question is not that much esoteric. Tony wanted a generalized, i.e. unrestricted, memoize function capable of attaching a cache to any function, i.e. including itself.

But this might be thoretically as possible as that famous program that solves the halting problem.

The reference Tony was talking of, says itself that its example solution is restricted in several ways and Tony did not answer my question what is meant by "work with any function signature" in case of D-signatures.

Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden.

-manfred

"Manfred Nowak" <svv1999@hotmail.com> wrote in message news:dc962h$snm$1@digitaldaemon.com...
> "Ben Hinkle" <bhinkle@mathworks.com> wrote:
>
> [...]
> > I wouldn't be surprised if a memoize function
> > couldn't memoize itself
> [...]
>
> Then my question is not that much esoteric. Tony wanted a generalized, i.e. unrestricted, memoize function capable of attaching a cache to any function, i.e. including itself.
>
> But this might be thoretically as possible as that famous program that solves the halting problem.
>
> The reference Tony was talking of, says itself that its example solution is restricted in several ways and Tony did not answer my question what is meant by "work with any function signature" in case of D-signatures.
>
> Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden.
>
> -manfred

Hi Manfred,

Sorry for being a wee bit slow in replying.

The limitations raised by Paul Graham apply when functions have keyword arguments or return multiple values.  Its worth noting that (to the best of my knowledge) the majority of programming languages do not support either of these features.  So for the functions typical of many languages, Paul Grahams solution is a general one.

In addition, dealing with multiple return values requires only a minor addition to the memoize function.  I've just had a go at it and it seems to be working correctly (but no guarantees!):

(defun memoize (fn)

    (let ((cache (make-hash-table :test #'equal)))

        #'(lambda (&rest args)

            (multiple-value-bind (vals win) (gethash args cache)

            (if win

                (values-list vals)

                (progn

                    (let ((vals (multiple-value-list (apply fn args))))

                        (setf (gethash args cache) vals)

                            (values-list vals))))))))


I'm not entirely sure of the issues regarding support for keyword arguments so I can't comment on this.

My main concern with the D implementations I've seen so far is that a separate version seems to be required for each function signature supported (resulting in duplicate code).  Since it is the strong (static) typing that seems to be creating this situation, it seems reasonable to conclude that in this instance strong typing is counter-productive.

Tony
Melbourne, Australia

"Tony" <talktotony@email.com> wrote:

[...]
>> Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden.
[...]
> I've just had a go at
> it and it seems to be working correctly (but no guarantees!):
[...]

I do not understand Lisp. Therefore I am not able to capture the semantics of your implementation. But with Ben I believe that such generalized memoize constructs are at least close to impossibility. And if this is true, then only a subset of the possible constructs is memoizable and this subset has to be defined.

An informal argument for the impossibility of a generalized memoize construct (gmc):

Assume a gmc is possible.

gmc must turn any construct c into a similar construct c' that on invocation with some arguments p1, ..., pn looks up its cache and then do the appropriate of returning the value cached or execute the construct c with arguments p1,...,pn and cache the result.

Now apply gmc to itself:

  gmc'= gmc( gmc)

Now call gmc':

  result = gmc'( gmc')

gmc' works as defind: it looks up the entry for gmc' in the hashtable. There is no entry. So it calls itself with its argument ... resulting in an infinite recursion. A contradiction.

Therefore the assumption is wrong, that a gmc as defined can exist.

-manfred

"Manfred Nowak" <svv1999@hotmail.com> wrote in message news:dcajm5$1tcn$1@digitaldaemon.com...
> "Tony" <talktotony@email.com> wrote:
>
> [...]
> >> Then: unless somebody has a proof for the existence of such a generalized memoize construct it is nonsense to conclude that strong typing is a burden.
> [...]
> > I've just had a go at
> > it and it seems to be working correctly (but no guarantees!):
> [...]
>
> I do not understand Lisp. Therefore I am not able to capture the semantics of your implementation. But with Ben I believe that such generalized memoize constructs are at least close to impossibility. And if this is true, then only a subset of the possible constructs is memoizable and this subset has to be defined.
>
> An informal argument for the impossibility of a generalized memoize
> construct (gmc):
>
> Assume a gmc is possible.
>
> gmc must turn any construct c into a similar construct c' that on invocation with some arguments p1, ..., pn looks up its cache and then do the appropriate of returning the value cached or execute the construct c with arguments p1,...,pn and cache the result.
>
> Now apply gmc to itself:
>
>   gmc'= gmc( gmc)
>
> Now call gmc':
>
>   result = gmc'( gmc')
>
> gmc' works as defind: it looks up the entry for gmc' in the hashtable. There is no entry. So it calls itself with its argument ... resulting in an infinite recursion. A contradiction.
>
> Therefore the assumption is wrong, that a gmc as defined can exist.
>
> -manfred

Hi Manfred,

I think we may have a slight misunderstanding here.

I have not been seeking a totally general memoize function in D.  In fact, there are many instances where it does not make sense to apply a memoize function.  Namely when:

1. The function to be memoized involves less processing than the cache
lookup in a memoized version, or
2. When a function is not referentially transparent.

What I am saying is that for the subset of functions that can benefit from memoizing, it is desirable to be able to write a single memoize function rather than needing to write multiple versions for each different function signature.

So far the consensus seems to be that the strong static typing in D precludes this.

Tony
Melbourne, Australia

Stefan wrote:
> In article <dc15p2$gn1$1@digitaldaemon.com>, Ben Hinkle says...
> 
>>>that sounds quite interesting, is Box(ing) documented somewhere?
>>>How can I learn more about it?
>>
>>http://www.digitalmars.com/d/std_boxer.html
>>The one wrinkle in using Box today is that you have to compile your code with -release in order to avoid linking problems. Or you can recompile phobos with debugging. 
>>
> 
> 
> 
> "float opCmp(Box other)"
> 
> Why float as return type, that's quite unusal, no?

If the compiler sees "a <= b" and "a" is a struct that has an opCmp or a class, it converts that into "a.opCmp (b) <= 0"; it only uses opEquals for == and !=.  So if you return negative for below, positive for above, zero for equivalent, and float.nan for unordered (nan is unordered with everything including itself), then all of the comparison operators will work correctly.

This behaviour is undocumented, of course.  :)  And classes are resigned to using int opCmp because that's what's in Object.  That should really be fixed.

Russ Lewis wrote:

> Ben Hinkle wrote:
> 
>> "Russ Lewis" <spamhole-2001-07-16@deming-os.org> wrote in message news:dc3df6$2a7d$1@digitaldaemon.com...
>>
>>> Ben Hinkle wrote:
>>>
>>>>> int delegate(int) memoize(Fcn f) {
>>>>> Memoize m = new Memoize(f);
>>>>> return &m.opCall;
>>>>> }
>>>>> ...
>>>>> int main() {
>>>>> ...
>>>>> int delegate(int) dg = memoize(&fib);
>>>>> ...
>>>>> }
>>>>>
>>>>> The two functionality are roughly equivalent.  The delegate version requires a tiny bit more storage (8 bytes for a delegate, rather than 4 bytes for a class reference), but is much more general and adaptible.
>>>>
>>>>
>>>>
>>>> Good point. I agree. Here's a slightly shorter version of memoize:
>>>> int delegate(int) memoize(int function(int) f) {
>>>>    struct Frame {
>>>>        int function(int) f;
>>>>        int call(int x){return f(x);}
>>>>    }
>>>>    Frame* frame = new Frame;
>>>>    frame.f = f;
>>>>    return &frame.call;
>>>> }
>>>> int fib(int n){return n+10;}
>>>> int main() {
>>>>    int delegate(int) dg = memoize(&fib);
>>>>    printf("%d\n",dg(5));
>>>>    return 0;
>>>> }
>>>
>>>
>>> Remember the caching functions.
>>
>>
>>
>> hehe - I got a little carried away in "simplifying" :-P
>>
>>
>>> Also note that the caching example given above is not thread-safe.
>>
>>
>> That would actually be an advantage of using a class since it can synchronize the opCall method (or whatever method name is chosen - it doesn't really matter what the name is if the delegate is used).. 
> 
> 
> True.  I wonder, if you take a delegate to a synchronized member function, does the member function implementation do the synchronization?  Or is it not ever legal?  Something I'll have to investigate some day, unless somebody has the answer right offhand...

Sure:

    import std.thread;

   class A
   {
       int count = 0;

       int bar ()
       {
           printf ("Bar\n");
           if (count ++ == 0)
               (new Thread (&bar)).start ();
           while (count == 1)
               Thread.yield ();
           return 0;
       }
   }

   void main ()
   {
       (new A).bar ();
   }

This prints "Bar\n" and then stalls as expected; if synchronized is removed then it goes through.

Burton Radons wrote:
> Sure:
> 
>     import std.thread;
> 
>    class A
>    {
>        int count = 0;
> 
>        int bar ()
>        {
>            printf ("Bar\n");
>            if (count ++ == 0)
>                (new Thread (&bar)).start ();
>            while (count == 1)
>                Thread.yield ();
>            return 0;
>        }
>    }
> 
>    void main ()
>    {
>        (new A).bar ();
>    }
> 
> This prints "Bar\n" and then stalls as expected; if synchronized is removed then it goes through.

Err, I mean if synchronized is ADDED then it stalls.