Thu Feb 4 07:26:20 CET 2010
Simple numeric abstract interpretation: implementation
The idea is to translate the code in staapl/algebra/staged-number.ss
to a typed representation, such that operations respect the Num type
The idea is that the "number" represented by the new datatype is
actually an environment of memoized expressions. If an expression
corresponds to a value, it can be reduced at compile time (Haskell run
time), otherwise it needs to be postponed to run time (of the
generated C program).
So, performing a binary operation consists of somehow joining two
environments (possibly eliminating common subexpressions) and
extending it with a new expression.
To avoid common subexpression elimination it might be required that
the environment is always shared, i.e. that it is threaded through the
computation in the same way it will be threaded at run-time when local
variables are initialized sequentially.
So the question arises: how to represent the environment and values?
It would be simplest to use a model that directly corresponds to the
generated C code, i.e. to use symbolic names and shadowing.
So, datatypes are: Env, Expr
Can environment be reused? (Is there a type class for environments?)
Let's keep it simple:
type Op = [Char]
type Ref = [Char]
type Env = [(Ref, Expr)]
type Closure = (Expr, Env)
data Expr = Unop Op Ref
| Binop Op Ref Ref