Re: Compiler Branch

[Noah Lavine <noah.b.lavine@gmail.com>]

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