Suppose you’re a tourist in an unfamiliar country and want to plan a road trip to another town. How will you decide which route to take? A direct solution is to jump into your rental car and drive in whichever direction seems the most promising. Depending on how lucky you are, and on how much help the foreign road signs give you, this brute-force exploration of an unknown road network might eventually get you to your destination. But it’s an expensive strategy, and it’s likely that you’ll just get more and more lost until you give up completely.

Using a map to plan your trip is a much more sensible idea. A printed road atlas is an abstraction that sacrifices a lot of the detail of the physical road network. It doesn’t tell you what the traffic is like, which roads are currently closed, where individual buildings are, or anything at all about the third dimension; it is, crucially, much smaller and flatter than the real thing. But a map does retain the most important information required for journey planning: the relative positions of all the towns, which roads lead to each town, and how those roads are connected to each other.

Despite all of this missing detail, an accurate map is useful, because the route you plan with it is likely to be valid in reality, not just in the abstract world of the map. A cartographer has done the expensive work of creating a model of reality, giving you the opportunity to perform a computation on that model by looking at a simplified representation of the road network and planning your route on it. You can then transfer the result of that computation back into the real world when you actually get in your car and drive to your destination, allowing cheap decisions made in the abstract world of the map to prevent you from having to make expensive decisions on the physical roads.

The approximations used by a map make navigational computations much easier without fatally compromising the fidelity of their results. There are plenty of circumstances in which decisions made with a map might turn out to be wrong—there is no guarantee that a map has told you absolutely everything you need to know about your journey—but planning your route in advance lets you rule out particular kinds of mistakes and makes the whole problem of getting from one place to another much more manageable.

Planning a route with a printed map is a real application of abstract interpretation, but it’s also very informal. For a more formal example, we can look at the multiplication of numbers; although it’s still only a toy example, multiplication gives us a chance to start writing code to investigate these ideas.

Pretend for a moment that multiplying two numbers is a difficult or expensive operation, and that we’re interested in finding out some information about the result of a multiplication without having to actually perform it. Specifically: what is the sign of the result? Is it a negative number, zero, or a positive number?

The notionally expensive way of finding out is to compute in the concrete world, using the standard interpretation of multiplication: multiply the numbers for real, look at the resulting number, and decide whether that result is negative, zero, or positive. In Ruby, for example:

>> 6 * -9
=> -54

-54 is negative, so we’ve learned that the product of 6 and -9 is a negative number. Job done.

However, it’s also possible to discover the same information by computing in an abstract world, using an abstract interpretation of multiplication. Just as a map uses lines on a flat page to represent roads in the real world, we can use abstract values to represent numbers; we can plan a route on a map instead of finding our way by trial and error on real roads, and we can define an abstract multiplication operation on abstract values instead of using concrete multiplication on concrete numbers.

To do this, we need to design abstract values that make the calculation simpler while still retaining enough information to be a useful answer. We can take advantage of the fact that the absolute values^[86] of two multiplied numbers don’t make any difference to the sign of the result:

>> (6 * -9) < 0
=> true
>> (1000 * -5) < 0
=> true
>> (1 * -1) < 0
=> true

As young children, we’re taught that it’s only the signs of the arguments that matter: the product of two positive numbers, or two negative numbers, is always a positive number; the product of one positive and one negative number is always negative; and the product of zero with any other number is always zero.

So let’s use these different kinds of number—“negative,” “zero,” and “positive”—as our abstract values. We can do this in Ruby by defining a Sign class and creating three instances of it:

class Sign < Struct.new(:name)
  NEGATIVE, ZERO, POSITIVE = [:negative, :zero, :positive].map { |name| new(name) }

  def inspect
    "#<Sign #{name}>"
  end
end

This gives us Ruby objects that we can use as our abstract values: Sign::NEGATIVE represents “any negative number,” Sign::ZERO represents “the number zero,” and Sign::POSITIVE represents “any positive number.” These three Sign objects make up the tiny abstract world where we’ll perform abstract calculations, while our concrete world consists of the virtually unlimited supply of Ruby integers.^[87]

We can define abstract multiplication for Sign values by implementing just the sign-related aspect of concrete multiplication:

class Sign
  def *(other_sign)
    if [self, other_sign].include?(ZERO)
      ZERO
    elsif self == other_sign
      POSITIVE
    else
      NEGATIVE
    end
  end
end

Instances of Sign can now be “multiplied” together just like numbers, and our implementation of Sign#* produces answers that are consistent with multiplication of actual numbers:

>> Sign::POSITIVE * Sign::POSITIVE
=> #<Sign positive>
>> Sign::NEGATIVE * Sign::ZERO
=> #<Sign zero>
>> Sign::POSITIVE * Sign::NEGATIVE
=> #<Sign negative>

For example, the last line above asks the question: what do we get when we multiply any positive number by any negative number? The answer comes back: a negative number. This is still a kind of multiplication, but it’s much simpler than the kind we’re used to, and it only works on “numbers” that have had almost all of their identifying information removed. If we’re still imagining that real multiplication is expensive, this seems like a cut-down version of multiplication that could be considered cheap.

Armed with our abstract world of numbers and an abstract interpretation of multiplication for those numbers, we can tackle the original problem in a different way. Rather than multiplying two numbers directly to find out the sign of their result, we can convert the numbers into their abstract counterparts and multiply those instead. First we need a way to convert concrete numbers into abstract ones:

class Numeric
  def sign
    if self < 0
      Sign::NEGATIVE
    elsif zero?
      Sign::ZERO
    else
      Sign::POSITIVE
    end
  end
end

Now we can convert two numbers and do the multiplication in the abstract world:

>> 6.sign
=> #<Sign positive>
>> -9.sign
=> #<Sign negative>
>> 6.sign * -9.sign
=> #<Sign negative>

Again we’ve calculated that 6 * -9 produces a negative number, but this time we’ve done it without any multiplication of actual numbers. Stepping up into the abstract world gives us an alternative way of performing the computation, and crucially, the abstract result can be translated back down into the concrete world so we can make sense of it, although we can only get an approximate concrete answer because of the detail we sacrificed in making the abstraction. In this case, the abstract result Sign::NEGATIVE tells us that any of the concrete numbers -1, -2, -3, etc., might be the answer to 6 * -9, but that the answer is definitely not 0 or any positive number like 1 or 500.

Note that, because Ruby values are objects—data structures that carry their operations with them—we can use the same Ruby expression to perform either a concrete or an abstract computation depending on whether we provide concrete (Fixnum) or abstract (Sign) objects as arguments. Take a #calculate method that multiplies three numbers in a particular way:

def calculate(x, y, z)
  (x * y) * (x * z)
end

If we call #calculate with Fixnum objects, the calculation will be done by Fixnum#* and we’ll get a concrete Fixnum result. If we call it with Sign instances instead, the Sign#* operation will be used and produce a Sign result.

>> calculate(3, -5, 0)
=> 0
>> calculate(Sign::POSITIVE, Sign::NEGATIVE, Sign::ZERO)
=> #<Sign zero>

This gives us a limited opportunity to perform abstract interpretation within real Ruby programs by replacing concrete arguments with their abstract counterparts and running the rest of the code without modification.

So far we’ve seen that a computation in the abstract world will produce less precise results than its concrete counterpart, because an abstraction throws away detail: a route we plan on a map will tell us which way to turn but not which lane to drive in, and a multiplication between two Sign objects will tell us which side of zero the answer lies on but not its actual value.

A lot of the time, it’s fine for a result to be imprecise, but for an abstraction to be useful, it’s important that this imprecision is safe. Safety means that the abstraction always tells the truth: the result of an abstract computation must agree with the result of its concrete counterpart. If not, the abstraction is giving us unreliable information and is probably worse than useless.

Our Sign abstraction is safe because converting numbers into Signs and multiplying them together always gives us the same result as calculating with the numbers themselves and just converting the final result into a Sign:

>> (6 * -9).sign == (6.sign * -9.sign)
=> true
>> (100 * 0).sign == (100.sign * 0.sign)
=> true
>> calculate(1, -2, -3).sign == calculate(1.sign, -2.sign, -3.sign)
=> true

In this respect, our Sign abstraction is actually quite precise. It retains exactly the right amount of information and preserves it perfectly throughout abstract computations. The safety issue becomes more significant when the abstraction doesn’t match up quite so perfectly with the computations we want to perform, as we can see by experimenting with abstract addition.

There are some rules about how the signs of two numbers can determine the sign of the number we get when we add them together, but they don’t work for all possible combinations of signs. We know that the sum of two positive numbers must be positive, and that the sum of a negative number and zero must be negative, but what about when we add a negative and a positive number? In that case, the sign of the result depends on the relationship between the two numbers’ absolute values: if the positive number has a larger absolute value than the negative number, we’ll get a positive answer (−20 + 30 = 10), if the negative number’s absolute value is larger, then we’ll get a negative answer (−30 + 20 = −10), and if they are exactly equal, we’ll get zero. But of course the absolute value of each number is precisely the information that our abstraction has discarded, so we can’t make this sort of decision in the abstract world.

This is a problem for our abstraction because it’s too abstract to be able to compute addition accurately in every situation. How do we handle this? We could botch the definition of abstract addition just to get it to return some result—return Sign::ZERO, say, whenever we don’t know what the right answer is—but that would be unsafe, because it would mean the abstract computation was giving an answer that might actively disagree with the one we’d get by doing the concrete computation instead.

The solution is to expand the abstraction to accommodate this uncertainty. Just as we have Sign values that mean “any positive number” and “any negative number,” we can introduce a new one that simply means “any number.” This is really the only honest answer that we can give when we’re asked a question that we don’t have enough detail to answer: the result could be negative, zero, or positive, no guarantees either way. Let’s call this new value Sign::UNKNOWN:

class Sign
  UNKNOWN = new(:unknown)
end

This gives us what we need to implement abstract addition safely. The rules for calculating the sign of the sum of two numbers x and y are:

We can turn that into an implementation of Sign#+ easily enough:

class Sign
  def +(other_sign)
    if self == other_sign || other_sign == ZERO
      self
    elsif self == ZERO
      other_sign
    else
      UNKNOWN
    end
  end
end

This gives us the behavior we want:

>> Sign::POSITIVE + Sign::POSITIVE
=> #<Sign positive>
>> Sign::NEGATIVE + Sign::ZERO
=> #<Sign negative>
>> Sign::NEGATIVE + Sign::POSITIVE
=> #<Sign unknown>

In fact, this implementation happens to do the right thing when the sign of one of the inputs is unknown:

>> Sign::POSITIVE + Sign::UNKNOWN
=> #<Sign unknown>
>> Sign::UNKNOWN + Sign::ZERO
=> #<Sign unknown>
>> Sign::POSITIVE + Sign::NEGATIVE + Sign::NEGATIVE
=> #<Sign unknown>

We do need to go back and fix up our implementation of Sign#*, though, so that it handles Sign::UNKNOWN correctly:

class Sign
  def *(other_sign)
    if [self, other_sign].include?(ZERO)
      ZERO
    elsif [self, other_sign].include?(UNKNOWN)
      UNKNOWN
    elsif self == other_sign
      POSITIVE
    else
      NEGATIVE
    end
  end
end

This gives us two abstract operations to play around with. Notice that Sign::UNKNOWN isn’t totally contagious; even an unknown number multiplied by zero is still zero, so any uncertainty that creeps in partway through a computation may get swallowed up by the time it finishes:

>> (Sign::POSITIVE + Sign::NEGATIVE) * Sign::ZERO + Sign::POSITIVE
=> #<Sign positive>

We also need to adjust our idea of correctness to deal with the imprecision introduced by Sign::UNKNOWN. Because our abstraction sometimes doesn’t have enough information to give a precise answer, it’s no longer true that the abstract and concrete versions of a computation always give exactly matching results:

>> (10 + 3).sign == (10.sign + 3.sign)
=> true
>> (-5 + 0).sign == (-5.sign + 0.sign)
=> true
>> (6 + -9).sign == (6.sign + -9.sign)
=> false
>> (6 + -9).sign
=> #<Sign negative>
>> 6.sign + -9.sign
=> #<Sign unknown>

So what’s going on here? Is our abstraction still safe? Well, yes, because in the cases where it loses precision and returns Sign::UNKNOWN, the abstract computation is still telling us something true: “the result is a negative number, zero, or a positive number.” It’s not as useful as the answer we can get by doing the concrete computation, but it’s not wrong, and it’s as good as we’re going to get without adding more information to our abstract values and making abstract computations more complex.

We can express this in code by having a better way of comparing Signs than #==, which is now too unforgiving for the safety check. What we want to know is: does the result of the concrete computation fall within the result predicted by the abstract one? If the abstract computation says that a few different results are possible, does the concrete computation actually produce one of those results, or something else entirely?

Let’s define an operation on Signs that can tell us whether two abstract values relate to each other in this way. Since what we’re testing is whether one Sign value “fits inside” another, let’s make it the #<= method:

class Sign
  def <=(other_sign)
    self == other_sign || other_sign == UNKNOWN
  end
end

This gives us the test we want:

>> Sign::POSITIVE <= Sign::POSITIVE
=> true
>> Sign::POSITIVE <= Sign::UNKNOWN
=> true
>> Sign::POSITIVE <= Sign::NEGATIVE
=> false

Now we can check for safety by seeing whether each concrete computation’s result falls within the abstract computation’s prediction:

>> (6 * -9).sign <= (6.sign * -9.sign)
=> true
>> (-5 + 0).sign <= (-5.sign + 0.sign)
=> true
>> (6 + -9).sign <= (6.sign + -9.sign)
=> true

This safety property holds for any computation involving addition and multiplication, because we’ve designed an abstraction that falls back to a safe approximation when it can’t give a precise answer.

Incidentally, having access to this abstraction lets us do simple analysis of Ruby code that adds and multiplies numbers. As an example, here’s a method that sums the squares of its arguments:

def sum_of_squares(x, y)
  (x * x) + (y * y)
end

If we want to automatically analyze this method to learn something about how it behaves, we have a choice: we can treat it as a black box and run it for all possible arguments, which would take forever, or we can inspect its source code and try to use mathematical reasoning to deduce some of its properties, which is complicated. (And, in the general case, doomed to failure because of Rice’s theorem.) Abstract interpretation gives us the third option of calling the method with abstract values to see what outputs are produced by an abstract version of the computation, and it’s practical to do this for all possible inputs, because there are only a small number of potential combinations of abstract values.

Each of the arguments x and y can be a negative, zero, or positive number, so let’s see what the possible outputs can be:

>> inputs = Sign::NEGATIVE, Sign::ZERO, Sign::POSITIVE
=> [#<Sign negative>, #<Sign zero>, #<Sign positive>]
>> outputs = inputs.product(inputs).map { |x, y| sum_of_squares(x, y) }
=> [
     #<Sign positive>, #<Sign positive>, #<Sign positive>,
     #<Sign positive>, #<Sign zero>, #<Sign positive>,
     #<Sign positive>, #<Sign positive>, #<Sign positive>
   ]
>> outputs.uniq
=> [#<Sign positive>, #<Sign zero>]

Without having done any clever analysis, this tells us that #sum_of_squares can only produce zero or positive numbers, never negative numbers—a fairly boring property that’s obvious to an educated human reading the source code, but not something that would be immediately evident to a machine. Of course, this kind of trick only works for very simple code, but despite being a toy, it shows how abstraction can make a difficult problem more tractable.

Let’s make these ideas concrete by building a type system for the Simple language from Chapter 2. Superficially, this will look like a big-step operational semantics from Big-Step Semantics: we’ll implement a method on each of the classes representing the syntax of Simple programs (Number, Add, and so on), and calling the method will return a final result. In the dynamic semantics, that method is called #evaluate, and its result is either a fully evaluated Simple value or an environment associating names with Simple values, depending on whether we evaluate an expression or a statement:

>> expression = Add.new(Variable.new(:x), Number.new(1))
=> «x + 1»
>> expression.evaluate({ x: Number.new(2) })
=> «3»
>> statement = Assign.new(:y, Number.new(3))
=> «y = 3»
>> statement.evaluate({ x: Number.new(1) })
=> {:x=>«1», :y=>«3»}

For our static semantics, we’ll implement a different method that does less work and returns a more abstract result. Instead of concrete values and environments, our abstract values will be types. A type represents many possible values: a Simple expression can evaluate to a number or a Boolean, so for expressions, our types will be “any number” and “any Boolean.” These types are similar to the Sign values we saw earlier, especially Sign::UNKNOWN, which really does mean “any number.” As with Sign, we can introduce types by defining a class called Type and creating some instances:

class Type < Struct.new(:name)
  NUMBER, BOOLEAN = [:number, :boolean].map { |name| new(name) }

  def inspect
    "#<Type #{name}>"
  end
end

Our new method will return a type, so let’s call it #type. It’s supposed to answer a question: when this Simple syntax is evaluated, what type of value will it return? This is very easy to implement for Simple’s Number and Boolean syntax classes, because numbers and Booleans evaluate to themselves, so we know exactly what type of value we’ll get:

class Number
  def type
    Type::NUMBER
  end
end

class Boolean
  def type
    Type::BOOLEAN
  end
end

For operations like Add, Multiply, and LessThan, it’s slightly more complicated. We know that evaluating Add returns a number, for example, but we also know that evaluation will only succeed if both arguments to Add also evaluate to a number, otherwise the Simple interpreter will fail with an error:

>> Add.new(Number.new(1), Number.new(2)).evaluate({})
=> «3»
>> Add.new(Number.new(1), Boolean.new(true)).evaluate({})
TypeError: true can't be coerced into Fixnum

How can we find out whether an argument will evaluate to a number? That’s what its type tells us. So for Add, the rule is something like: if the type of both arguments is Type::NUMBER, the type of the overall result is Type::NUMBER; otherwise, the result is no type at all, because the evaluation of any expression that tries to add nonnumeric values will fail before it can return anything. For simplicity, we’ll let the #type method return nil to indicate this failure, although in other circumstances, we might have chosen to raise an exception or return some special error value instead (Type::ERROR, for instance) if that made the overall implementation more convenient.

The code for Add looks like this:

class Add
  def type
    if left.type == Type::NUMBER && right.type == Type::NUMBER
      Type::NUMBER
    end
  end
end

The implementation of Multiply#type is identical, and LessThan#type is very similar, except that it returns Type::BOOLEAN instead of Type::NUMBER:

class LessThan
  def type
    if left.type == Type::NUMBER && right.type == Type::NUMBER
      Type::BOOLEAN
    end
  end
end

On the console, we can see that this is enough to distinguish between expressions that will evaluate successfully and those that won’t, even though the syntax of Simple allows both:

>> Add.new(Number.new(1), Number.new(2)).type
=> #<Type number>
>> Add.new(Number.new(1), Boolean.new(true)).type
=> nil
>> LessThan.new(Number.new(1), Number.new(2)).type
=> #<Type boolean>
>> LessThan.new(Number.new(1), Boolean.new(true)).type
=> nil

>> bad_expression = Add.new(Number.new(true), Number.new(1)) 
=> «true + 1»
>> bad_expression.type
=> #<Type number> 
>> bad_expression.evaluate({})
NoMethodError: undefined method `+' for true:TrueClass 

This is a more general version of the earlier trick with addition, multiplication, and Sign. Even though we’re not doing any actual addition or comparison of numbers, the static semantics gives us an alternative way of “executing” the program that still returns a useful result.

Instead of interpreting the expression «1 + 2» as a program about values, we’re throwing away some detail and interpreting it as a program about types, and the static semantics provides the alternative interpretations of «1», «2», and «+», which let us run this program-about-types to see what its result is. That result is less specific—more abstract—than the one we’d get by running the program normally according to the dynamic semantics, but it’s nonetheless a useful result, because we have a way of translating it into something meaningful in the concrete world: Type::NUMBER means “calling #evaluate on this expression will return a Number,” and nil means “calling #evaluate may cause an error.”

We almost have the complete static semantics of Simple expressions now, but we haven’t looked at variables. What should Variable#type return? It depends what value the variable contains: in a program like «x = 5; y = x + 1» the variable y has the type Type::NUMBER, but in «x = 5; y = x < 1» it has the type Type::BOOLEAN. How can we handle this?

We saw in Small-Step Semantics that the dynamic semantics of Variable uses an environment hash to map variable names onto their values, and the static semantics needs something similar: a mapping from variable names onto types. We could call this a “type environment,” but let’s use the name type context to avoid getting the two kinds of environment mixed up. If we pass a type context into Variable#type, all it has to do is look up that variable in the context:

class Variable
  def type(context)
    context[name]
  end
end

Now that #type expects a context argument, we need to go back and revise the other implementations of #type to accept a type context:

class Number
  def type(context)
    Type::NUMBER
  end
end

class Boolean
  def type(context)
    Type::BOOLEAN
  end
end

class Add
  def type(context)
    if left.type(context) == Type::NUMBER && right.type(context) == Type::NUMBER
      Type::NUMBER
    end
  end
end

class LessThan
  def type(context)
    if left.type(context) == Type::NUMBER && right.type(context) == Type::NUMBER
      Type::BOOLEAN
    end
  end
end

This lets us ask for the type of expressions that involve variables, as long as we provide a context that gives them the right types:

>> expression = Add.new(Variable.new(:x), Variable.new(:y))
=> «x + y»
>> expression.type({})
=> nil
>> expression.type({ x: Type::NUMBER, y: Type::NUMBER })
=> #<Type number>
>> expression.type({ x: Type::NUMBER, y: Type::BOOLEAN })
=> nil

That gives us implementations of #type for all forms of expression syntax, so what about statements? Evaluating a Simple statement returns an environment, not a value, so how do we express that in the static semantics?

The easiest way to handle statements is to treat them as a kind of inert expression: assume that they don’t return a value (which is true) and ignore the effect they have on the environment. We can come up with a new type that means “doesn’t return a value” and associate that type with any statement as long as all its subparts have the right types. Let’s give this new type the name Type::VOID:

class Type
  VOID = new(:void)
end

Implementations of #type for DoNothing and Sequence are easy. Evaluation of DoNothing will always succeed, and evaluation of Sequence will succeed as long as the statements it’s connecting don’t have anything wrong with them:

class DoNothing
  def type(context)
    Type::VOID
  end
end

class Sequence
  def type(context)
    if first.type(context) == Type::VOID && second.type(context) == Type::VOID
      Type::VOID
    end
  end
end

If and While are slightly more discerning. They both contain an expression that acts as a condition, and for the program to work properly, the condition has to evaluate to a Boolean:

class If
  def type(context)
    if condition.type(context) == Type::BOOLEAN &&
      consequence.type(context) == Type::VOID &&
      alternative.type(context) == Type::VOID
      Type::VOID
    end
  end
end

class While
  def type(context)
    if condition.type(context) == Type::BOOLEAN && body.type(context) == Type::VOID
      Type::VOID
    end
  end
end

This lets us distinguish between a statement that will go wrong during evaluation and one that won’t:

>> If.new(
     LessThan.new(Number.new(1), Number.new(2)), DoNothing.new, DoNothing.new
   ).type({})
=> #<Type void>
>> If.new(
     Add.new(Number.new(1), Number.new(2)), DoNothing.new, DoNothing.new
   ).type({})
=> nil
>> While.new(Variable.new(:x), DoNothing.new).type({ x: Type::BOOLEAN })
=> #<Type void>
>> While.new(Variable.new(:x), DoNothing.new).type({ x: Type::NUMBER })
=> nil

The only method left to implement is Assign#type. We know it should return Type::VOID, but under what circumstances? How do we decide if an assignment is well-behaved or not? We’ll want to check that the expression on the righthand side of the assignment is sensible according to the static semantics, but do we care what type it is?

These questions lead us to make some design decisions about what should be considered valid Simple programs. For example, is «x = 1; y = 2; x = x < y» okay? It’s certainly fine according to the dynamic semantics—nothing bad happens when it’s executed—but we might (or might not!) be uncomfortable with allowing programs where the variables change from holding one type of value to another during execution. That kind of flexibility might be valuable to some programmers, but for others, it could act as a source of accidental errors.

From the perspective of someone designing the static semantics, it’s also more difficult to handle a language where variables can change their types. At the moment, we’re assuming that the type context arrives from some external source and remains unchanged throughout the program, but we could opt for a more sophisticated system where the context is empty at the beginning of the program and gradually builds up as variables are declared or assigned, in the same way that the dynamic semantics gradually builds up the value environment as the program executes. But this gets complicated: if statements could modify the type context, then we’d need the #type method to return both a type and a context, in the same way that the dynamic semantics’ #reduce method returns a reduced program and an environment, so that an earlier statement can pass an updated context to a later one. We’d also have to deal with situations like «if (b) { x = 1 } else { y = 2 }» where different execution paths produce different type contexts, as well as ones like «if (b) { x = 1 } else { x = true }» where those different contexts actively contradict each other.^[89]

Fundamentally, there is a tension between the restrictiveness of a type system and the expressiveness of the programs we can write within it. A restrictive type system can be good, because it provides strong guarantees that rule out lots of possible errors, but it’s bad when it prevents us from writing the programs we want to write. A good type system finds an acceptable compromise between restrictiveness and expressiveness, ruling out enough problems to be worthwhile without getting in the way, while being simple enough for programmers to understand.

We’ll resolve this tension by sticking with the uncomplicated idea of a type context that’s provided by something outside the program itself and doesn’t get updated by individual statements. This does rule out certain kinds of program, and definitely avoids the problem of how and where this type context originates, but it keeps the static semantics simple and gives us a rule we can easily work with.

For assignment statements, then, let’s say that the type of the expression should match the type of the variable to which its value is being assigned:

class Assign
  def type(context)
    if context[name] == expression.type(context)
      Type::VOID
    end
  end
end

This rule is good enough for all programs where we can decide the type of each variable upfront and have it stay the same, which is a tolerable constraint. For example, we can check the While loop whose dynamic semantics we implemented in Chapter 2:

>> statement =
     While.new(
       LessThan.new(Variable.new(:x), Number.new(5)),
       Assign.new(:x, Add.new(Variable.new(:x), Number.new(3)))
     )
=> «while (x < 5) { x = x + 3 }»
>> statement.type({})
=> nil
>> statement.type({ x: Type::NUMBER })
=> #<Type void>
>> statement.type({ x: Type::BOOLEAN })
=> nil

The type system we’ve built can prevent basic errors. By running a toy version of a program according to these static semantics, we can find out what types of value can appear at each point in the original program, and check that these types match up correctly with what the dynamic semantics is going to try to do when we run it. The simplicity of this toy interpretation means that we get only limited information about what might happen when the program is evaluated, but it also means that we can do our checking easily and without complications. For example, we can check a program that runs forever:

>> statement =
     Sequence.new(
       Assign.new(:x, Number.new(0)),
       While.new(
         Boolean.new(true),
         Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))
       )
     )
=> «x = 0; while (true) { x = x + 1 }»
>> statement.type({ x: Type::NUMBER })
=> #<Type void>
>> statement.evaluate({})
SystemStackError: stack level too deep

That program is definitely stupid, but it doesn’t contain any type errors: the loop condition is a Boolean, and the variable x is consistently used to store a number. Of course, the type system isn’t clever enough to tell us whether a program is doing what we meant it to do, or even doing anything useful at all, only whether its parts match up in the right way. And because it needs to be safe, just like our Sign abstraction, it will sometimes give us an overly pessimistic answer about whether a program contains any errors. We can see this if we extend the above program with an extra statement:

>> statement = Sequence.new(statement, Assign.new(:x, Boolean.new(true)))
=> «x = 0; while (true) { x = x + 1 }; x = true»
>> statement.type({ x: Type::NUMBER })
=> nil

The #type method returns nil to indicate an error because there’s a statement that assigns a Boolean value to x, but there’s no way this could actually cause a problem at runtime, because this statement will never get executed. Our type system isn’t clever enough to spot this, but it gives us a safe answer, “this program might go wrong,” which is overly cautious but not incorrect. Something in the program tries to assign a Boolean value to a numeric variable, so part of it has the potential to go wrong, but for other reasons it never actually will.

It’s not just infinite loops that cause problems. The dynamic semantics has no problem with a program like this:

>> statement =
     Sequence.new(
       If.new(
         Variable.new(:b),
         Assign.new(:x, Number.new(6)),
         Assign.new(:x, Boolean.new(true))
       ),
       Sequence.new(
         If.new(
           Variable.new(:b),
           Assign.new(:y, Variable.new(:x)),
           Assign.new(:y, Number.new(1))
         ),
         Assign.new(:z, Add.new(Variable.new(:y), Number.new(1)))
       )
     )
=> «if (b) { x = 6 } else { x = true }; if (b) { y = x } else { y = 1 }; z = y + 1»
>> statement.evaluate({ b: Boolean.new(true) })
=> {:b=>«true», :x=>«6», :y=>«6», :z=>«7»}
>> statement.evaluate({ b: Boolean.new(false) })
=> {:b=>«false», :x=>«true», :y=>«1», :z=>«2»}

The variable x is used to store a number or a Boolean depending on whether b is true or false, which is never a problem during evaluation, because the program consistently uses either one or the other; there’s no possible execution path where x is treated as both a number and a Boolean. But the abstract values used by the static semantics don’t have enough detail to be able to show that this is okay,^[90] so the safe approximation is to always say “this program might go wrong”:

>> statement.type({})
=> nil
>> context = { b: Type::BOOLEAN, y: Type::NUMBER, z: Type::NUMBER }
=> {:b=>#<Type boolean>, :y=>#<Type number>, :z=>#<Type number>}
>> statement.type(context)
=> nil
>> statement.type(context.merge({ x: Type::NUMBER }))
=> nil
>> statement.type(context.merge({ x: Type::BOOLEAN }))
=> nil

This system is focused on programs going wrong in a specific way: the dynamic semantics of each piece of syntax has certain expectations about what types of values it will be handling, and the type system checks those expectations to make sure that a number won’t show up where a Boolean is expected and vice versa. But there are other ways for a program to go wrong, and this static semantics doesn’t check for them. For example, the type system pays no attention to whether a variable has actually been given a value before it’s used, so any program containing uninitialized variables will pass the type checker and still fail during evaluation:

>> statement = Assign.new(:x, Add.new(Variable.new(:x), Number.new(1)))
=> «x = x + 1»
>> statement.type({ x: Type::NUMBER })
=> #<Type void>
>> statement.evaluate({})
NoMethodError: undefined method `value' for nil:NilClass

Any information we get from the type system has to be taken with a pinch of salt, and we have to pay attention to its limitations when deciding how much faith to put in it. A successful execution of a program’s static semantics doesn’t mean “this program will definitely work,” only “this program definitely won’t fail in a particular way.” It would be great to have an automated system that can tell us that a program is free of any conceivable kind of bug or error, but as we saw in Chapter 8, the universe just isn’t that convenient.