Re: Compiler Branch

[Noah Lavine]

Hello,

I'm going to try to combine the two parallel compiler threads into
one, by replying to two messages at once. I hope this makes things
simpler rather than more confusing. :-)

Message 1:

> Here is my calculus regarding this work, FWIW: it is low risk, and low
> cost, since it doesn't actually affect Tree-IL or any other part of the
> compiler.  The only cost it imposes is a coupling with Tree-IL, which is
> easy enough to deal with on that side.  So that makes me much less
> uneasy :-) And on the positive side, it has the potential to prove
> interesting things, so at this point I'm neutral about it.  If it does
> something useful, IMO we should throw it in, when you're ready for that.
> Other people's opinions are welcome as well, of course.

Well, I would hope to have it merged eventually. It will be a while
before it's ready to do that, though.

> Can you describe what the branch does, currently?

So far it doesn't do any interesting analysis - it just has
bookkeeping code and a very rough interface to an analyzer.

The function called 'go' runs everything. You give it a Scheme
expression. It compiles that expression to tree-il, then converts it
to annotated-tree-il. Then it scans the annotated-tree-il looking for
instances of the special function 'verify'.

The idea of 'verify' is that if the analyzer can't prove that things
in a verify always evaluate to true, it will throw a warning. It's a
simple way to mark up your code with your expectations. For instance,

  (verify #t)

always passes verification, and

  (verify #f)

never passes.

  (verify (some-big-expression))

might or might not pass, depending on the expression and depending on
how well we could analyze the program. I imagine that it would
primarily be used for things like this:

  (define (map proc list)
    (verify (list? list))
    ...)

If your program didn't pass the verify check, you could still run it,
but you probably shouldn't.

> What do you see it doing within three months or so?

Verifying statements, but with some actual inference.

> How long do you intend to work on it?

At least a year, and probably more if that's what it takes to make it
do what I want. I would really like to make it usable and useful.

> What do you think about the tree-il differences in master relative to
> stable-2.0?

I don't know what the differences are, since I just base all of the
work on master.

> Do you see this work as an optional pass, or a core part of the
> compiler? If the latter, what sort of algorithmic complexity are you
> envisioning for this work?  (O(n) in size of program is ideal of
> course.)

My first idea was to implement something equivalent to 0-CFA, which
unfortunately has complexity O(n^3). If there's something that's
faster and still produces useful results, that could be a good first
step. However, I also think we could get the average-case time far
below n^3 by doing inference on demand instead of calculating the type
of every binding, similar to the change that peval went through a
couple months ago.

I think the complexity really determines how it could be used in the
compiler. Ideally it would be very fast, and it could work as an
extension to peval. If it's slower, it could only be used if the user
requested that the compiler do more work. Either way, I'd like to see
it help generate native code, and ideally native binaries.

Message 2:

> This sounds cool.  I assume you're familiar with kCFA?  See
> http://matt.might.net/articles/implementation-of-kcfa-and-0cfa/, for
> example.

No, I hadn't read about it before. Thank you very much for the
pointer! I admit that I am new to writing real compilers, so pointers
to papers are great.

I have now read the first part of Matt Might's thesis, where he
describes k-CFA. 0-CFA is equivalent to what I was planning to do, I
think, but his implementation is more elegant than what I had thought
of. k >= 1 seems to have performance too slow to be useful to us. I
also think k >= 1 does some wasted work in many common cases. I have
ideas on how to fix this, but I suspect they're equivalent to the
abstract garbage collection he talks about. In any case, I think 0-CFA
is a good first step, and later I hope to get some variant of 1-CFA
that does less work than full 1-CFA.

> It doesn't seem to me that static analysis is a prerequisite for AOT
> compilation -- and indeed, the current .go compilation is an example of
> naive AOT compilation.

Yes, excellent point. I was blurring two ideas together. I would
eventually like this work to lead to an optimizing native-code
compiler, so I am planning ahead for that.

As a side note, you'll see that the current code is quite ugly in many
ways. I used to think that the best choice was to do the analysis in a
form very similar to Tree-IL, to keep from disturbing the program
structure too much. Now I suspect that it would be best to use
something like continuation-passing style, to keep the analyzer
simpler. So I hope that you'll see more elegant-looking code soon.

Best,
Noah