Re: using @inert with collection APIs

On Fri, Sep 26, 2008 at 2:47 PM, Kevin Reid <[email protected]> wrote:
> On Sep 24, 2008, at 16:45, Tyler Close wrote:
>> 1. We were unable to use the standard iteration API, since it uses a
>> mutable iterator object. So the following code would generate a
>> verifier error:
>>
>>    Iterator<SomeMutable> i = someKeys.iterator();    // cannot hold
>> return value in non-@inert variable
>>
>> and so would:
>>
>>    @inert Iterator<SomeMutable> i = someKeys.iterator();
>>    i.next();    // cannot call non-@inert method on @inert reference.
>
> It seems to me that what you want to express here is
>
>   Iterator<@inert SomeMutable> i = someKeys.iterator();

That's interesting, but not quite what is needed. We need to know that
the iterator itself won't mutate the values in the map, not just that
it won't let the caller mutate the returned values. For example, what
if the Iterator.next() implementation was:

T next() {
    this.underlyingMap.get(0).sneakyModification();
    T r = ...  // get next value.
    return r;
}

> Whether something equivalent to this is possible in Java I don't know.

Unfortunately, the syntax also doesn't support this expression.

>> ... If not, this also means we need to make the ConstArray.with()
>> implementation efficient enough for this task. If we do so, we might
>> as well deprecate the ArrayBuilder interface.
>
> In case the example is useful, I'd like to point out that E-on-CL
> already implements the O(n^2)->O(n) 'with' optimization for arrays and
> maps.
>
> The relevant code is in
>   svn://www.slimy.com/cl-e/cl-e/trunk/lisp/elib-values.lisp
>   svn://www.slimy.com/cl-e/cl-e/trunk/lisp/tables2.lisp
>   svn://www.slimy.com/cl-e/cl-e/trunk/lisp/lazy.lisp
> ; search for "with-node" in the first two.

Thanks.

I've implemented optimized const collections in the past. The
trickiest part is making them still appear to be const even when
accessed by multiple threads. This is needed to use them in a boot
comm protocol, where arguments are passed by reference, instead of
being copied. The current naive implementation works fine with
multiple threads.

--Tyler