[e-lang] Q: asynchronous tail recursion?

[Kevin Reid]

On Dec 28, 2006, at 7:26, Constantine Plotnikov wrote:
> On 12/28/06, Kevin Reid <kpreid at mac.com> wrote:
>> On Dec 27, 2006, at 9:21, Kevin Reid wrote:
>>> *If* this is in fact a problem, which I'm not sure about, then I
>>> think it can be fixed as part of the implementation: any time a
>>> promise is resolved to another promise, the resolved-ref should do a
>>> whenMoreResolved on its target, changing its target whenever it gets
>>> a response. This would ensure that there is at most one layer of
>>> resolved promise in any such resolution chain.
>> ...
>> As above, except that instead of using __whenMoreResolved, promises
>> have a weak set or weak-keyed map containing all forwarding
>> references (former promises, what I called resolved-ref above) which
>> refer to that promise.
>>
>> When a promise is resolved, it updates (shortens) every forwarding-
>> ref to point to its resolution (and discards the set).
>
> I do not understand how the solution that you are proposing will work.
> Could you please elaborate?

The situation we're trying to avoid is:

   +-----------+  +-----------+       +---------+
   | forwarder |->| forwarder |->...->| promise |
   +-----------+  +-----------+       +---------+

(A forwarder is a resolved promise.)

What I propose is that every promise has a weak table recording the  
forwarders which refer to it directly:

          . . . . . . .
         v             .
   +-------------+  +-----------+
   | forwarder A |->| promise B |
   +-------------+  +-----------+

When promise B is resolved (in the case we're working with, to  
another promise), besides the ordinary conversion to a forwarding ref,

          . . . . . . .     . . . . . . .
         v             .   v             .
   +-------------+  +-------------+  +-----------+
   | forwarder A |->| forwarder B |->| promise C |
   +-------------+  +-------------+  +-----------+

the back-reference table is used to notify all direct forwarders to  
B, and then discarded. The forwarders shorten themselves to point to C.

           . . . . . . . . . . . . . . . .
          v                v              .
   +-------------+  +-------------+  +-----------+
   | forwarder A |  | forwarder B |->| promise C |
   +-------------+  +-------------+  +-----------+
                \                    /\
                 \------------------/

Now, forwarder B is garbage, since the only reference to it is weak.

           . . . . . . .
          v             .
   +-------------+  +-----------+
   | forwarder A |->| promise C |
   +-------------+  +-----------+

We now have the same situation as we started with, so there will be  
no accumulation of forwarders.

In the multiple-vat case, this same algorithm should work given that  
support for inter-vat weak references is provided, which seems doable  
(with one extra reference table pair added to CapTP and the weak ref  
system being aware of far refs).

-- 
Kevin Reid                            <http://homepage.mac.com/kpreid/>