Wed Jan 16 22:15:53 CET 2013
Abstract interpretation in Racket
Let's start with a simple language with forms: `function', `locals'
and `op'. This covers most of the necessary functionality and would
be a good start to define abstract interpretations for:
- type checking / inference
- typed code generation for C
The first extension for this would be to lift functions over streams
instead of scalars.
The first significant representation decision is to represent outputs
explicitly, i.e. use "node form" instead of lambda/let form, since
lambda form is easily expanded as:
(let ((z (op + a b))) ...) ->
(op + (a b c) (z))
However, the main trick in embedding is to use the host language's
binding structure. So let's stick to expression form. The AI layer
can easily perform transformations to "node form" if that's necessary.
In racket, to add multiple interpretations, the options are to use
lambda expressions (low level) or the module system. To start out it
seems easiest to use plain lambdas.
One of the simplest AI requirements is the need for mapping a program
to nb of i/o, preferrably with type (if input types or some other
inference root are given).
Should this go on top of typed scheme?