[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Compiler Branch
From: |
Noah Lavine |
Subject: |
Re: Compiler Branch |
Date: |
Sun, 8 Jan 2012 16:15:47 -0500 |
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