Lazy evaluation

[Peter Alexander]

On 23/11/11 6:10 PM, Manu wrote:
>         Perhaps if you declared some function as lazy, then the compiler
>         would
>         be expected to cache the return value
>
>
>     How does it cache it?
>
>     i.e.
>
>     - What data structure does it use?
>     - Is there a size limit, or does it just keep adding into the cache
>     until you run out of memory?
>     - What allocator does it use?
>     - If there is a size limit, what is the eviction policy?
>     - and what is the size limit?
>     - How do I manually flag the cache as dirty if I want to clear it?
>
>     There is no automatic way to do caching. Every single application of
>     caching has its own needs and you need control over that. You can't
>     just stick it all in a hash table and be done with it.
>
>
> I can imagine many possibilities. Here's one straight off the top.
>
> - The data structure is the return value of the function contained
> within its parent class/struct + any necessary dirty bits. Where you
> place those it in the containing class/struct is debatable, but sensible
> options exist.

This simply doesn't work for functions of arguments that require caching.

class FooManager
{
     class Foo { ... }

     const(Foo) getFoo(int i) const
     {
         return new Foo(i);
     }
}

Assume that constructing a Foo is expensive. How can I cache the values 
of Foo? One approach would be to use an array:

class FooManager
{
     class Foo { ... }

     const(Foo) getFoo(int i) const
     {
         if (m_foos[i] is null)
             m_foos[i] = new Foo(i); // illegal in D
         return m_foos[i];
     }

     const(Foo)[kCacheSize] m_foos;
}

Of course, this requires knowledge of the range of 'i' that can be 
received, so there is no way to automate this type of caching.

You could automatically use a hash map, but that is needlessly 
inefficient. Also, what if getFoo could be called with any value of i? 
You wouldn't want to cache all values, you'd just want to cache a subset 
using some eviction policy, perhaps the 10 most recently used values of 'i'?

There's no way to automate caching. One size does not fit all.


> - Size limit? What is the size limit of the object returned from the
> function in the first place?
> - Not really relevant, if it's a primitive type or struct, it is
> contained by the functions containing object, if it is a class, then it
> is a reference to, and it is allocated however the lazy function does.
> - I don't think this is relevant.
> - Again...
> - Fair question. Perhaps the function could have a property, or the
> containing class could have some property to access the cached object...
> but I would imagine the compiler would explicitly manage dirtying of the
> state, so that it can enforce that it is done in a '@safe' way...

All these responses assume that the function is not a function of its 
arguments (or it has no arguments).


> Am I wrong in suggesting that this is the most frequent cause of people
> raising the "D const issues' topic?

Yeah, it usually comes down to caching (or lazy computation, which is 
similar) but it's not the only thing.

Essentially, any object that contains state that is not related to its 
definition of equality is difficult to model using D's const qualifiers.