What is the common procedure used when compilers statically type check "complex" expressions?

Question

Note: When I used "complex" in the title, I mean that the expression has many operators and operands. Not that the expression itself is complex.

---

I've recently been working on a simple compiler to x86-64 assembly. I've finished the compiler's main front end - the lexer and parser - and am now able to generate an Abstract Syntax Tree representation of my program. And since my language will be statically typed, I am now doing the next phase: type checking the source code. However, I've come to a problem and have not been able to reasonably solve it myself.

Consider the following example:

My compiler's parser has read this line of code:

int a = 1 + 2 - 3 * 4 - 5

And converted it to the following AST:

       =
     /   \
  a(int)  \
           -
         /   \
        -     5
      /   \
     +     *
    / \   / \
   1   2 3   4

Now it must type check the AST. it starts by first type checking the = operator. It first checks the left hand side of the operator. It sees that the variable a is declared as an integer. So it must now verify that the right hand side expression evaluates to an integer.

I understand how this could be done if the expression was just a single value, such as 1 or 'a'. But how would this be done for expressions with multiple values and operands - a complex expression - such as the one above? To correctly determine the value of the expression, it seems like the type checker would actual have to execute the expression itself and record the result. But this obviously seems to defeat the purpose of separating the compilation and execution phases.

The only other way I imagine this could be done is to recursively check the leaf of each subexpression in the AST and verify all of the leaf's types match the expected operator type. So starting with the = operator, the type checker would then scan all of the left hand side's AST and verify that the leafs are all integers. It would then repeat this for each operator in the subexpression.

I've tried researching the topic in my copy of "The Dragon Book", but it doesn't seem go in to much detail, and simply reiterates what I already know.

What is the usual method used when a compiler is type checking expressions with many operators and operands? Are any of the methods I mentioned above used? If not, what are the methods and how exactly would they work?

Answer 1

Recursion is the answer, but you descend into each subtree before handling the operation:

int a = 1 + 2 - 3 * 4 - 5

to tree form:

(assign (a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

Inferring the type happens by first walking the left hand side, then the right hand side, and then handling the operator as soon as the operands' types are inferred:

(assign*(a) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> descend into lhs

(assign (a*) (sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> infer a. a is known to be int. We're back in the assign node now:

(assign (int:a)*(sub (sub (add (1) (2)) (mul (3) (4))) (5))

-> descend into rhs, then into the lhs of the inner operators until we hit something interesting

(assign (int:a) (sub*(sub (add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub*(add (1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add*(1) (2)) (mul (3) (4))) (5))
(assign (int:a) (sub (sub (add (1*) (2)) (mul (3) (4))) (5))

-> infer the type of 1, which is int, and return to the parent

(assign (int:a) (sub (sub (add (int:1)*(2)) (mul (3) (4))) (5))

-> go into the rhs

(assign (int:a) (sub (sub (add (int:1) (2*)) (mul (3) (4))) (5))

-> infer the type of 2, which is int, and return to the parent

(assign (int:a) (sub (sub (add (int:1) (int:2)*) (mul (3) (4))) (5))

-> infer the type of add(int, int), which is int, and return to the parent

(assign (int:a) (sub (sub (int:add (int:1) (int:2))*(mul (3) (4))) (5))

-> descend into the rhs

(assign (int:a) (sub (sub (int:add (int:1) (int:2)) (mul*(3) (4))) (5))

etc., until you end up with

(assign (int:a) (int:sub (int:sub (int:add (int:1) (int:2)) (int:mul (int:3) (int:4))) (int:5))*

Whether the assignment itself is also an expression with a type depends on your language.

The important takeaway: to determine the type of any operator node in the tree, you only have to look at its immediate children, which need to have a type assigned to them already.

Answer 2

What is the usually method used when a compiler is type checking expressions with many operators and operands.

Read wikipages on type system and type inference and on Hindley-Milner type system, which uses unification. Read also about denotational semantics and operational semantics.

Type checking can be simpler if:

• all your variables like a are explicitly declared with a type. This is like C or Pascal or C++98, but not like C++11 which has some type inference with auto.
• all literal values like 1, 2, or 'c' have an inherent type: an int literal always has type int, a character literal always has type char, ….
• functions and operators are not overloaded, e.g. the + operator always has type (int, int) -> int. C has overloading for operators (+ works for signed and unsigned integer types and for doubles) but no overloading of functions.

Under these constraints, a bottom up recursive AST type decoration algorithm could be enough (this only cares about types, not about concrete values, so is a compile-time approach):

• For each scope, you keep a table for the types of all visible variables (called the environment). After a declaration int a, you would add the entry a: int to the table.

• Typing of leaves is the trivial recursion base case: the type of literals like 1 is already known, and the type of variables like a can be looked up in the environment.

• To type a expression with some operator and operands according to the previously computed types of the (nested sub-expressions) operands, we use recursion on the operands (so we type first these sub-expressions) and follow the typing rules related to the operator.

So in your example, 4 * 3 and 1 + 2 are typed int because 4 & 3 and 1 & 2 have been previously typed int and your typing rules say that the sum or product of two int-s is an int, and so on for (4 * 3) - (1 + 2).

Then Read Pierce's Types and Programming Languages book. I recommend to learn a tiny bit of Ocaml and λ-calculus

For more dynamically typed languages (Lisp like) read also Queinnec's Lisp In Small Pieces

Read also Scott's Programming Languages Pragmatics book

BTW, you can't have a language agnostic typing code, because the type system is an essential part of the language's semantics.

Answer 3

In C (and frankly most statically typed languages based on C) every operator can be seen as syntactic sugar for a function call.

So your expression can be rewritten as:

int a{operator-(operator-(operator+(1,2),operator*(3,4)),5)};

Then overload resolution will kick in and decide that every function is of the (int, int) or (const int&, const int&) type.

This way makes type resolution easy to understand and follow and (more importantly) easy to implement. Information about types only flows in 1 way (from the inner expressions outwards).

That is the reason why double x = 1/2; will result in x == 0 because 1/2 is evaluated as an int expression.

Answer 4

Focusing on your algorithm, try changing it to bottom-up. You know the type pf variables and constants; tag the node bearing the operator with the result type. Let the leaf determine the operator’s type, also the opposite of your idea.

Answer 5

It's actually quite easy, as long as you think of + as being a variety of functions rather than a single concept.

    int operator=(int)
     /   \
  a(int)  \
        int operator-(int,int)
         /                  \
    int operator-(int,int)    5
         /              \
int operator+(int,int) int operator*(int,int)
    / \                      / \
   1   2                    3   4

During the parsing stage of the right hand side, the parser retrieves 1, knows that's an int, then parses +,and stores that as an "unresolved function name", then it parses the 2, knows that's an int, and then returns that up the stack. The + function node now knows both parameter types, so can resolve the + into int operator+(int, int), so now it knows the type of this sub-expression, and the parser continues on it's merry way.

As you can see, once the tree is fully constructed, each node, including the function calls, knows its types. This is key because it allows for functions that return different types than their parameters.

char* ptr = itoa(3);

Here, the tree is:

    char* itoa(int)
     /           \
  ptr(char*)      3

Answer 6

The basis for type checking is not what the compiler does, it is what the language defines.

In the C language, every operand has a type. "abc" has type "array of const char". 1 has type "int". 1L has type "long". If x and y are expressions, then there are rules for the type of x + y and so on. So the compiler obviously has to follow the rules of the language.

On modern languages like Swift, the rules are much more complicated. Some cases are simple like in C. Other cases, the compiler sees an expression, has been told beforehand what type the expression should have, and determines the types of subexpressions based on that. If x and y are variables of different types, and an identical expression is assigned, that expression might be evaluated in a different way. For example assigning 12 * (2 / 3) will assign 8.0 to a Double and 0 to an Int. And you have cases where the compiler knows that two types are related and figures out what types they are based on that.

Swift example:

var x: Double
var y: Int

x = 12 * (2 / 3)
y = 12 * (2 / 3)

print (x, y)

prints "8.0, 0".

In the assignment x = 12 * (2 / 3): The left hand side has a known type Double, therefore the right hand side must have type Double. There is only one overload for the "*" operator returning Double, and that is Double * Double -> Double. Therefore 12 must have type Double, as well as 2 / 3. 12 supports the "IntegerLiteralConvertible" protocol. Double has an initialiser taking an argument of type "IntegerLiteralConvertible", so 12 is converted to Double. 2 / 3 must have type Double. There is only one overload for the "/" operator returning Double, and that is Double / Double -> Double. 2 and 3 are converted to Double. The result of 2 / 3 is 0.6666666. The result of 12 * (2 / 3) is 8.0. 8.0 is assigned to x.

In the assignment y = 12 * (2 / 3), y on the left hand side has type Int, so the right hand side must have type Int, so 12, 2, 3 are converted to Int with the result 2 / 3 = 0, 12 * (2 / 3) = 0.

Answer 7

I wish I'd found this conversation earlier! By the time I found this I had mostly worked it all out for myself, but it had taken me some time to get here. A few years ago I stared a project to write a source to source translator for an Algol60-like language (Imp) into C. My translator handled most of the language but had a few remaining problems caused by my not having a good handle on these very issues - because I wasn't consistent about enforcing types top-down or bottom up, but primarily had been trying to enforce the type matching and coercion top-down.

Now that I'm percolating the type information up from the leaves, I've made a lot more progress and in a few weeks have brought a rewrite of the whole system up to the same level as the original failed implementation was after about a year.

Here's the sort of debate I had had with myself when I was unsure of whether I should be enforcing types top-down or bottom-up: when setting the type of an AST operation node to whatever is demanded by its operators, I've been assigning the smallest integer type that a constant can fit in to the literal constant - so "-100" would be marked as a signed 8 bit integer quantity and could be stored in a C "signed char". The problem came when adding two nodes together such as (-100) + (-100) - do I say that the "+" node result type is a 16 bit signed quantity, and postpone overflow checking and reporting until the eventual top-level assignment, which could be to a signed 32 bit int - but equally could be to a signed 8 bit int... one option allows the assignment, the other option requires an integer overflow event to be signalled - but the arithmetic calculation has already been made by this point so an explicit range test would have to be added. But if we had been enforcing types top-down, then that overflow would have been detected more naturally at the actual point where the (-100) + (-100) was calculated and would have allowed for a more informative diagnostic backtrace to be generated.

It was all rather messy and there were so many special cases that I got to that point like in the old IBM fortran compiler where adding one fix would create more than one new bug! Hence why I decided to rewrite from scratch because not only is the bottom-up type system cleaner and easier, I had since also created a better parser generator and found ways to simplify other components of the compiler such as block scoping, so rewriting turned out to be the right thing to do.

And the comments of earlier posters are accurate - this is not an area that is well covered by most compiler books, and although one poster pointed out the similarity with some of the type systems work from the theoretical side of computer science (which I'm familiar with - I was a student under both Robin Milner and Rod Burstall) it's not an obvious mapping from those subjects to practical compiler writing. I just mention this as a hint for the next person who takes on writing a practical compiler book! (Btw of the books I've read, Bornat is quite good for practical hints, and to some extent Nils Holms books although they're maybe dumbed down a little too far. I think there's still room for a well written book of practical advice.).

Anyway, bottom line: assign a type to the leaves - usually already defined for variables, but inferred for literal constants. Use the smallest type that is compatible. Whenever you synthesize a new object from operations on leaves, determine the smallest type which that compound object could be; when you get to a point working up the tree where a type is enforced (usually at the top where an expression is assigned to a variable or a procedure parameter) then either coerce the expression from the synthesized type to the expected type if possible (eg by widening) or report an error if the synthesized type can't fit in the required destination (possibly only if the value actually exceeds the capacity, possibly always - the choice depends on the semantics of the language).

G