Typing expressions
In the Expressions DSL, types are not written explicitly by the programmer. However, due to the simple nature of our expressions, we can easily deduce the type of an expression by looking at its shape. In this DSL, we have a fixed set of types: string, integer, and boolean. The mechanism of deducing a type for an expression is usually called type computation or type inference.
The base cases for type computation in the Expressions DSL are constants; trivially, an integer constant has type integer, a string constant has type string, and a boolean constant has type boolean.
As for composed expressions, besides computing a type, we must also check that its sub-expressions are correct with respect to types. This mechanism is usually called type checking. For example, consider the expression !e, where e is a generic expression. We can say that it has type boolean, provided that, recursively, the sub-expression e has type boolean; otherwise, the whole expression is not well-typed...
