[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Compiler Branch

From: Andy Wingo
Subject: Re: Compiler Branch
Date: Sun, 08 Jan 2012 15:53:05 +0100
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux)

Hi Noah :)

On Sun 08 Jan 2012 01:42, Noah Lavine <address@hidden> 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:

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:

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

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

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


Happy hacking,


reply via email to

[Prev in Thread] Current Thread [Next in Thread]