Re: A Plan for Hacking

[ludo@gnu.org (Ludovic Courtès)]

Hi Noah!

Noah Lavine <noah.b.lavine@gmail.com> skribis:

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

That would be cool.  However, I suspect that for best results you’d want
procedures to have type annotations, as in Racket’s Typed Scheme and
Bigloo; otherwise it may be impossible to determine type info most of
the time—e.g., a public top-level procedure used in another module.

(It’s not clear to me whether this can be done without seriously
compromising on dynamic module composition.)

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

These three items seem “off-topic” and less important to me.

>   - You write a compiler for Guile code. You'd like to infer the types
> of variables at compile-time.

Cool!

[...]

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

Sounds like a nice plan.  :-)

To reduce frustration, I would narrow the use cases a bit, or define
short-term milestones.  For instance, you could decide to focus solely
on type inference, or have type inference one of your major milestones.

Kanren [0] and its companion book look like nice starting points to me.
In particular, there’s a simple type inference engine written in Kanren
that is actually usable with Guile 2.0 out of the box and could serve as
a starting point.

And before that, make sure PEG actually gets merged.  ;-)

Thanks,
Ludo’.

[0] http://kanren.sourceforge.net/