Compiler Branch

Compiler Branch

[Noah Lavine]

Hello Guile developers,

Following up on my last email, I am nervously announcing a new branch,
'wip-compiler'. I hope that in a few months this branch will contain a
working compiler. For now, it contains a few new data structures and a
function that converts Tree-IL to a form that will be nicer for
analysis.

I hope making a new branch for this was the right thing to do. I would
have liked to wait and talk about it, but I had a friend ask me if he
could also work on the compiler, so I thought it was time to make it
public, and this seemed like the way to do that. If you don't want the
branch, I suppose it can always be deleted on Savannah. (I would of
course love help from anyone and everyone else, but I was planning to
wait on publicizing it until it was in a less embarrassing state. See
the git log for more information on that. :-) )

My last email contains some information on my ideas. I hope you can
see some of that in the code that's there, especially the
annotated-tree-il data structure, but if not, I plan to add more soon.

Noah

Re: Compiler Branch

[Andy Wingo]

On Tue 13 Dec 2011 05:39, Noah Lavine <noah.b.lavine@gmail.com> writes:

> Following up on my last email, I am nervously announcing a new branch,
> 'wip-compiler'. I hope that in a few months this branch will contain a
> working compiler. For now, it contains a few new data structures and a
> function that converts Tree-IL to a form that will be nicer for
> analysis.

Cool.  As a quick reaction, I have some doubts about this project.  But,
I guess a WIP branch would be a good thing to have, and it would make
the discussion more concrete.

Andy
-- 
http://wingolog.org/

Re: Compiler Branch

[Noah Lavine]

> Cool.  As a quick reaction, I have some doubts about this project.  But,
> I guess a WIP branch would be a good thing to have, and it would make
> the discussion more concrete.

Probably so. But if you have time, what are your doubts? I would much
rather talk about problems now than after I've implemented something
that we'll have to change.

Noah

Re: Compiler Branch

[Ludovic Courtès]

Hi Noah!

This sounds like exciting work, although there’s not much yet to comment
on I suppose.  ;-)

Please keep informing the list so we can see what you’re up to (even if
we don’t necessary reply in a timely fashion...)

Thanks, and happy compiler hacking!

Ludo’.

Re: Compiler Branch

[Andy Wingo]

Hi Noah!

On Tue 13 Dec 2011 14:52, Noah Lavine <noah.b.lavine@gmail.com> writes:

>> Cool.  As a quick reaction, I have some doubts about this project.  But,
>> I guess a WIP branch would be a good thing to have, and it would make
>> the discussion more concrete.
>
> Probably so. But if you have time, what are your doubts? I would much
> rather talk about problems now than after I've implemented something
> that we'll have to change.

OK, I've taken a look at it now.  I apologize for my negativity, first
of all.  I'm not sure exactly where you're going with this, but it was
wrong for me to be a wet blanket about it.  So sorry about that!

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.

Can you describe what the branch does, currently?  What do you see it
doing within three months or so?  How long do you intend to work on it?

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

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.)

Cheers,

Andy
-- 
http://wingolog.org/

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

Re: Compiler Branch

[Andy Wingo]

Hi Noah :)

On Sun 08 Jan 2012 01:42, Noah Lavine <noah.b.lavine@gmail.com> writes:

> 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,

Interesting.  `verify' seems to be a form of contracts:

  http://ftp.ccs.northeastern.edu/scheme/pubs/icfp2002-ff.pdf

Does `verify' have runtime semantics?  Under what situations, if any,
would the compiler insert runtime checks?

As that paper indicates, two issues you will have to deal with are
higher-order functions and blame.

Your interest in static analysis naturally raises the question of types.
You might like this paper:

  http://www.ccs.neu.edu/racket/pubs/dls06-tf.pdf

I'm glad to hear of your interest in the problem, it's a good one.

>> 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.

Ah, I was just curious.  I made some small changes relative to
stable-2.0 (primcall and seq), and wondered if they were a good idea or
not.

I was also considering a move to a CPS-based intermediate language.
Some links are here:

  http://wingolog.org/archives/2011/07/12/static-single-assignment-for-functional-programmers

>> 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.

Yes, this is my thought as well.  Note also that peval is described by
waddell and dybvig as being a kind of special-purpose sub-0CFA.

> 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.

Yes, that would be great.

> 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'm still new to them too, so consider it a joint learning process :-)
Note that the kCFA algorithms, though proven, are not the last word; see
for example CFA2, http://arxiv.org/pdf/1102.3676.  Dimitris Vardoulakis
applied CFA2 to JavaScript last summer, in work at Mozilla.

>> 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.

Great.

Happy hacking,

Andy
-- 
http://wingolog.org/

Re: Compiler Branch

[Noah Lavine]

Hello,

> Interesting.  `verify' seems to be a form of contracts:
>
>  http://ftp.ccs.northeastern.edu/scheme/pubs/icfp2002-ff.pdf
>
> Does `verify' have runtime semantics?  Under what situations, if any,
> would the compiler insert runtime checks?

It has no runtime semantics right now. I considered making it like
'assert', but I'm not sure that's right. I will look at that paper.

> As that paper indicates, two issues you will have to deal with are
> higher-order functions and blame.
>
> Your interest in static analysis naturally raises the question of types.
> You might like this paper:
>
>  http://www.ccs.neu.edu/racket/pubs/dls06-tf.pdf

I will look at that too; thank you.

> Ah, I was just curious.  I made some small changes relative to
> stable-2.0 (primcall and seq), and wondered if they were a good idea or
> not.
>
> I was also considering a move to a CPS-based intermediate language.
> Some links are here:
>
>  http://wingolog.org/archives/2011/07/12/static-single-assignment-for-functional-programmers

Oh, this is interesting. I was just wondering if I needed a CPS-type
representation to write the analyzer reasonably elegantly. If you
think the main compiler also needs it, then perhaps I should work on
that first, and then come back to the analyzer question.

I do think there's a problem with plain CPS, though - it forces you to
pick an order for the evaluation of function arguments. I would like
to use CPS with some sort of parallel-call operator, so we can leave
the order undefined (maybe at some point an optimizer will want to
adjust the order). What do you think?

I also noticed that at the end of that blog post you said you were
considering ANF versus CPS for Guile (I assume you'd already decided
that you didn't like Tree-IL). Does this mean you decided on CPS?

>> 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.
>
> Yes, this is my thought as well.  Note also that peval is described by
> waddell and dybvig as being a kind of special-purpose sub-0CFA.

That makes sense. What I'd *really* like to do is make the analyzer
use the same on-demand-calculation infrastructure as peval, but it
might be really tricky to make them fit together. I am planning to
leave that project for much later.

Noah

Re: Compiler Branch

[Andy Wingo]

Heya Noah,

A brief note:

On Sun 08 Jan 2012 22:15, Noah Lavine <noah.b.lavine@gmail.com> writes:

> I do think there's a problem with plain CPS, though - it forces you to
> pick an order for the evaluation of function arguments. I would like
> to use CPS with some sort of parallel-call operator, so we can leave
> the order undefined (maybe at some point an optimizer will want to
> adjust the order). What do you think?
>
> I also noticed that at the end of that blog post you said you were
> considering ANF versus CPS for Guile (I assume you'd already decided
> that you didn't like Tree-IL). Does this mean you decided on CPS?

I guess I'd like to see if it's a good idea or not.  We definitely do
need a parallel binding operator.  I haven't already decided on it but I
am interested.

Andy
-- 
http://wingolog.org/