Loop handle?

[John Rose]

On Apr 8, 2010, at 11:46 PM, Charles Oliver Nutter wrote:

> In the current set of handles, I don't believe there's a way to
> construct a loop, since you can only link handles upwards from a
> target (i.e. there's no way to construct a handle to jump back to the
> condition again).

This is a good challenge for the MH API design!  I've enclosed an example of how to write a couple such combinators in user code.  I don't think they need to go into the standard, because (a) they are so easy to write and (b) they have too many degrees of design freedom.

The really subtle thing would be a guarantee that certain MH combinators are properly tail recursive, so that you could write MH trees that embody open-ended threaded interpreters.  I think all of the standard combinators should (at least as a matter of implementation quality) be properly tail-recursive in their last call when this is logically possible.  If there is a conversion to be performed after the last call, this is difficult to do.

I'm working right now on the JVM infrastructure for tail-recursive method handle adapters, and expect to make a number of built-in combinators properly tail-recursive in the RI.  Guaranteeing such things in the spec. would require all JVMs to do the extra work.  Is this worth it?  I'm thinking it's not really worth while until the bytecodes themselves can also express proper tail calls.  (I mean the "hard" version, that guarantee stack safety, not the "soft" kind that people expect from some optimizers; for the distinction, see the blog entry Emmanuel pointed out.)  Given both combinators and regular methods that can perform tail calls, you could do the same kinds of chained control structures as Scheme and Haskell programmers enjoy.

On Apr 9, 2010, at 12:58 AM, Charles Oliver Nutter wrote:
> Yes, that thought crossed my mind. If tail calling were there, the
> only missing piece would be allowing a downstream handle (toward the
> target) to be able to be rebound to an upstream handle. Currently
> handles are a one-way street.

That's like what I've been (mysteriously) calling a "ricochet" adapter method handle.  A ricochet calls two targets in succession; it feeds the result of the first target to the second, and (ideally) guarantees proper tail recursion on the second call.  Would that be the sort of upstream rebounding you are thinking of?  With an adapter like that, execution could ping-pong indefinitely through a series of first targets and ricochets; eventually a second target would return and the sequence would be over.  Here's pseudocode for a single generic ricochet combinator:

  ricochet := lambda(first, second) {
    lambda(*args) {
      temp := first(*args)
      goto second(*args, temp)
    }
  }

There are numerous variations on this, depending on how to share or split the argument list, and to merge in the temporary result value.  The pattern itself is powerful and useful (at least, in the JVM implementation).  With small variations, this is what several of the MethodHandles combinators do (notably filterArguments, but see how many others must include such logic!).

The "flyby" adapter method handle  (which I've also mentioned mysteriously at some points) would be a special kind of ricochet which reifies the argument list to the first target, and lets the target edit the arguments more or less "in place".  I don't think we need this power, so I don't plan to fully design or implement it, unless the need turns up somewhere.

At least, watch for ricochet stack frames, coming soon to a JVM near you.

-- John

P.S.  There's some chance our mail server will drop the attached zip file.  It's also posted here:
  http://blogs.sun.com/jrose/resource/jsr292/LoopHandle.zip

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20100409/aad82a2c/attachment.html 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: LoopHandle.zip
Type: application/zip
Size: 3927 bytes
Desc: not available
Url : http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20100409/aad82a2c/attachment.zip 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.openjdk.java.net/pipermail/mlvm-dev/attachments/20100409/aad82a2c/attachment-0001.html