[bitc-dev] Iterators

Geoffrey Irving irving at naml.us
Thu Feb 26 22:18:04 EST 2009


On Thu, Feb 26, 2009 at 6:58 PM, Jonathan S. Shapiro <shap at eros-os.com> wrote:
> On Thu, Feb 26, 2009 at 8:10 PM, Geoffrey Irving <irving at naml.us> wrote:
>> Unfortunately, since there is no primitive language construct for
>> looping other than tail-recursion, efficient compilation of any higher
>> order construct like forall requires partial specialization, not just
>> inlining.  It might not be too bad since the partial specialization is
>> almost inlining in the sense of being inlining that results in tail
>> recursive structures, but still scary.
>
> But BitC has (and will retain) a first-class looping construct. We saw
> this particular oncoming train early. We also have labeled block
> escape, which is sometimes useful in these situations.
>
>> I think that as a user of the language, I would only feel secure if I
>> could be completely sure that the important usages of forall were
>> partially specialized.
>
> Yes. The way I sometimes try to express this is that certain
> simplifications of the language are only acceptable in practice if we
> can successfully specify and mandate the corresponding optimizations
> that make them efficient.
>
> But there is another hidden issue here: it is most unfortunate if the
> implementation of these optimizations cannot be done by a BitC->BitC
> transform. I touched on this in a note a day or so ago in the context
> of unboxing. This is another good example.

I'm not sure that's true.  In the same email you noted that you could
express SSA form in BitC, and I assumed you were referring to the fact
that tail calls are essentially the same thing as SSA.  If so, you can
definitely translate all of this into tail calls.

If you don't count tail call form as SSA, can you explain what form
you imagine compiling control flow contacts into at the lowest level
(before conversion to C)?

If you imagine compiling into a conventional basic block graph form,
you could consider adding a "goto" construct to the language.  I was
actually about to suggest that a few emails ago before I remembered
the tail-call = SSA thing.  Same semantics for goto are easy to
express and would be easy to add to the compiler (you can even compile
them into tail-calls with a simple data flow analysis).

Also, in case someone hasn't seen it:
http://www.ecn.purdue.edu/ParaMount/papers/rubin87goto.pdf

>> This means ... partially specialize every
>> occurrence of forall.  Neither one is very attractive.
>
> Actually, in this case we can simply identify forall as a procedure
> whose inlining is mandatory and we're done.

What if someone stores a reference to forall in a higher order variable?

>> Actually, a syntactical for-loop construct _is_ a programmer annotated
>> version of forall, so that might be the way to go....
>
> I tend to see it the other way around. Forall is a convenience syntax
> around a syntactical for-loop construct. But that's the processor
> architect in me talking. I think we're in peaceable agreement about
> all this.

If you want to talk processor architect, goto is the one true way. :)

Geoffrey


More information about the bitc-dev mailing list