3 ms·
I think you need to run dataflow analysis. There is a paper I read which explains the approach, but I lost the link. It describes how to propagate types to opti
by bjourne 11y ago
I think you need to run dataflow analysis. There is a paper I read which explains the approach, but I lost the link. It describes how to propagate types to optimize code, but the exact same method can be used to type check code too.
Basically the compiler annotates each value it deals with with what it knows about it. So in your example:
(sqrt (car '(1 2 "hello"))
First '(1 2 "hello") what do we know about it? The value is of type list, the elements types are: integer, integer and string. Since it is a literal, we even know the values: 1, 2, "hello".
We record it somehow. Next we apply car to that value. What do we know about the resulting value? If car was a random function, we wouldn't know anything about the result. But car is not random. It is one of the most common Lisp functions so we have custom code for this "known" function that says that its value is the first item of its first parameter.
Therefore the type of (car '(1 2 "hello") is integer and the value is 1. Since the type of sqrt is an integer N >= 0 (let's ignore negative roots), the expression (sqrt (car '(1 2 "hello")) type checks! And if we have annotated car and sqrt as side-effect free we can fold the whole expression to 1.
Note that if the expression was (sqrt (car '(x y z)) where x, y, z are unknown variables then it would be a "maybe". We can't know if the code type checks or not. Note also that if the expression was (sqrt (car '(-1234 y z)), then the code would not type check as (sqrt -1234) has no type (ignoring complex numbers here). That is strictly more powerful than ordinary type systems which can't determine that (sqrt -1234) is a programming error.
- urs2102 11y agoI just saw this - but funnily enough, this is how I handled it. Thanks man - appreciate the comment!