A Plan for Hacking

[Noah Lavine]

Hello all,

It looks to me like the PEG project is wrapping up. We're talking
about what to name things now, which means the library is likely
pretty close to inclusion in Guile. After this I will want another
Guile project to work on. My original intention was to work on a JIT
compiler for Guile, but after following the list for a while, it seems
like work on an ahead-of-time compiler might be more useful in the
long term. This email is about my idea for what I will spend time on
over the next several months. I'd like to talk about it beforehand to
make sure that what I do will be useful, and so that I can coordinate
with other people. This is especially important because I think we
should use an unusual architecture for our compiler.

I think the next step is to write a static analyzer. This analyzer
will be used by the compiler, but it will not just be for the compiler
- it will also be available to users. I think of it as a tool for
writing correct programs. Here are some use-cases for a static
analyzer:
  - You write a function that assumes its arguments are of a certain
type. You'd like to be sure this is true, so your program won't throw
exceptions in the middle.
  - You write a program with more than one thread, which includes a
series of mutexes. You'd like to verify that if a thread grabs more
than one of these mutexes, then it always does so in a certain order.
  - You write a program that will respond to HTTP requests. You'd like
to verify that information from a certain set of variables only
influences your response packets if the user has a certain cookie
(i.e. verify that your web server is secure).
  - You write some C code that manipulates Guile values. You'd like to
be sure that the code does all of the appropriate Guile typechecks
before using Guile library functions. (This is taken from the Guile
to-do list, on the website.)
  - You write a compiler for Guile code. You'd like to infer the types
of variables at compile-time.

I also have three design considerations that I think are important for
an analyzer like this:
  - For any given proposition to be checked, it should say either
"yes, this is true", "not true, and here's how it might fail", or "I
can't tell if this is true or false". We cannot omit the last
condition, because an analyzer without that option that can satisfy
all of these use-cases is impossible (Godel's theorem).
  - It should work for multiple languages. This is necessary to do the
C typechecks from the last use case, but I also hope it will be
expanded to more languages as part of Guile integrating its compiler
with GCC someday.
  - It should integrate nicely with all languages it supports. If it
isn't easy to use, people will be less likely to use it.

I said we should use an unusual compiler architecture because I think
that the static analyzer, which is normally part of the compiler,
should be thought of as its own component, which can be used
independently of the compiler. I hope the use-cases above have
convinced you that having an analyzer around could be a useful thing,
but if not, I'm happy to discuss it more. (I will also make an
argument that a static analyzer should be part of the interface to the
compiler, if you are interested.)

So this is my proposal for the next several months: I work on a static
analyzer for Guile, hoping to expand it to other languages as well.
The main goal will be to make it very easy to use this analyzer in
code, including providing helpful feedback to users when their
assertions fail. While developing this, I will make sure that it can
check things that would be useful to a compiler. Once we have a static
analyzer, we can use it as the first step in an optimizing compiler.

What do you think?
Noah