How are dynamic and static typings implemented?

Question

As I understand, every programming language is either statically type checked or dynamically type checked (and there are cases where these two approaches are mixed, but for simplicity I won't mention it further), and every programming language can be implemented either in a compiler or in an interpreter.

From this I conclude that there can be 4 different variants of combining these concepts – that is, we can compile statically typed languages, compile dynamically typed languages, interpret statically typed languages and interpret dynamically typed languages. So, suppose we have a program in a language L1, L1 is dynamically typed and we have a compiler for L1 language that translates the programs directly to programs in machine language. What does mean the fact that in this case type checking will happen at runtime?

For example, suppose in this L1 program we have two named objects, A and B. As I understand, if the only space needed for actual values of each of these objects is 4 bytes, compiler will produce code in machine instructions creating not two 4-bytes chunks for these variables, but two, say, 8-bytes chunks, for these two chunks to be able to contain not only the values of objects A and B per se, but type identifying value in additional 4 bytes too to enable computer to look at these additional 4 bytes and understand what type the object is. And if we have L1 instruction

take value of variable A and add it to the value of variable B

the compiled code will contain the following instructions:

Look at these 8 bytes. Remember the value of first 4 bytes of them. Look at the other 8 bytes and remember the value of first 4 bytes of them. If these 4-bytes values are identical, add to the second half of the second 8-byte value the second half of the first 8-byte value.

That is, type checking is performed during runtime by executing compiler-generated machine instructions which look into parts of objects representing type info.

And I suppose that if this L1 language was statically typed instead, the things would be something different:

The compiler would take the L1 program source code, type check it, and if there would be no type errors, the machine instructions would be generated, else compile time error would be thrown and no machine code would be generated. During generated program's execution computer memory wouldn't contatin any type-identifying fields for objects A and B, and because of it they would be not 8 bytes long, but 4-bytes long only. Generated program's instructions wouldn't contain the type checking instructions, so the resulting corresponding instructions would be:

Take these 4 bytes and add them to these 4 bytes.

Is my understanding correct? That is, is the dynamic type checking implemented using additional machine instructions in translated program, which from some additional bytes of objects understand their types, and if we use static type checking we don't need these manipulations?

Answer 1

That is generally correct. With static typing, up front optimizations are possible and it is not necessary to represent type information in memory at runtime. With dynamic typing, the relevant type information is only available at runtime because the type is part of the value. This is often the case in object-oriented languages. Then, some or all typechecking must happen at runtime. Type tagging is a common way to represent this type information, i.e. using some bytes or bits of the value to encode type information. In OOP systems the tag is usually a native pointer to a data structure representing the type, thus allowing method dispatch and reflection.

However, depending on language, the concept of a “type” is less meaningful. E.g. the expression x + y in Python does not require the operands to have a numeric type. Instead, it requires either operand to have an addition method. This is less about nominal typing or type tagging (type-oriented) but more about structural typing or duck typing (behaviour-oriented). Languages without class inheritance such as JavaScript take this to an extreme.

Which aspects of type checking or method resolution happen at compile- or run-time varies a lot, especially when considering bytecode compilers (like javac) and JIT-compilation (as used in high-performance dynamic language implementations).

For example in C++, static typechecking allows the compiler to know the layout of the object's method table (vtable) so that methods can be called with a simple indirect call. But in Java, C#, or Go, interfaces make it impossible to do a lot of work at compile time – it can be asserted that a value will implement an interface, but the runtime behaviour is very complex. It would be excessive to emit code for all code paths in a compiled implementation. Instead, the compiler will emit a call site that handles a fast path, or otherwise falls back by calling into the runtime: a supporting library that provides similar functionality as an interpreter. Especially with JIT-compilers, interpreted and compiled parts can be rather interleaved. But the JIT compiler also has access to runtime type information that is not available to a static type checker, and could thus (in theory) produce far more optimal code than an ahead of time (AOT) compiler!

So a JIT compiler for a dynamically-typed language might produce code like this for a function function myadd(a, b) { return a + b }:

// counter to detect mis-optimizations
static uint16_t __myadd_deoptimize = 0;

// store bytecode somewhere in order to fall back to interpreted mode
static bytecode[] __myadd_bytecode = {...};

Object* myadd(Object* a, Object* b) {
  // guards: assumptions that must hold for later optimizations.
  // If they fail, must fall back to less optimized path, e.g. an interpreter.
  if (UNLIKELY(!IS_NATIVE_TYPE(a, int32))) goto fallback;
  if (UNLIKELY(!IS_NATIVE_TYPE(b, int32))) goto fallback;

  __myadd_deoptimize = 0;  // the optimizations seem correct

  // optimization: use efficient native operations without extra function calls
  int32 result = *(int32*)(a) + *(int32*)(b);

  return create_object(NATIVE_TYPE(int32), result);

fallback:
  __myadd_deoptimize++;
  Object* args[] = {a, b};
  // interpreter may interpret the bytecode just this time,
  // or permanently remove the optimized compiled version
  // if the deoptimize counter crosses some threshold.
  return interpret(__myadd_bytecode, 2, args, __myadd_deoptimize);
}

An ahead of time compiler could add similar speculative optimizations, but wouldn't be able to re-optimize the function on the fly – the fallback path would instead include a generic implementation of the functionality. And instead of optimizing for a single type (monomorphic optimization), it would also be possible to optimize for multiple known types (polymorphic optimization).

Answer 2

You are correct, but it's actually easier to start with the really generic version of this concept, and then work our way towards the generic. The most generic version is

Given a desired behavior, you must have enough information to select an implementation which causes that behavior.

This is the brain-dead version -- you have to know what you want to do in order to do it. But its a useful starting point.

Now in most languages, there is a division between "code" and "data." It is that division that makes the division between "static" and "dynamic." Static properties get baked into the code while dynamic properties get baked into the data. Now in some languages we find the line between code and data can get blurred (such as in python's exec command or C#'s System.Linq.Expressions.Expression), but what you'll find is that if "code" and "data" get blurred, "static" and "dynamic" get blurred in exactly the same way. So thinking about the two concepts as totally separate does prepare you for handling these blurry cases.

One of the fundamental differences between code and data is that code has to work on all possible (valid) values of the data at runtime, while data obviously only describes the actual runtime data. A "statically typed language" is a language where one can write one implementation in code and have it work for all valid data which can be present when you run the code. For example, if we want to add one to an integer, and store the result, we have to store 1 if the integer was 0, 2 if the integer was 1, and so on and so forth. Fortunately, basically all hardware we write software for has an operation to do this. It's called "add." So if we need to write code to add one to an integer, we can write the code "add 1" once, and it works for every integer the data has to offer.

But what if we didn't always have a hardware command? What if our language has a concept of a "number", but not a concept of "integer" versus "real number" (or floating point). The hardware may have one operation which is "add 1 to an integer" and one operation which is "add 1 to a floating point." Now we need to select which instruction to use!

What we have found is that type theory is a very effective tool for answering these questions. We assign each value a "type," and use that information to decide which implementations to use for each behavior we seek. This information is kept on the "code" side of the story. It's related to the operations that are done, and what values could possibly come from them.

So in your example, the named objects A and B are not important. What matters is that the code can prove that whatever value being passed in is an integer (or prove that it is a float), and that the knowledge that it is an integer is all that is needed to do the addition besides the value itself. Since the value is 4 bytes, we tend to allocate 4 bytes of space for these objects.

Some operations in some languages do not fit this mold. In some cases the type information which you can bake into the "code" part is insufficient to choose an implementation. Now obviously there must be some code which does the desired behavior for the object, or it will fail. It just isn't immediately obvious which implementation to use. We need to inspect the object in some ways. Then we can have some branching or other flow control to decide the right implementation. For example, we might have one operation to do if a floating point number is finite, and one to do if it is infinity or NAN (not a number). So the code emitted will look at the data for information about which implementation to use, by inspecting the number, and then using an if statement to select between two implementations.

Now that example could be thought of as a dynamic typing scenario. You can think of this has having two sub-types of floats, "finite float" and "non-finite float". The algorithm dynamically inspects the data in the object to figure out which subtype we were using and then calls the right version. Why call it a "sub-type?" Because type theory is such a common way of handling situations in programming that we likely used it to specify the behavior we wanted.

However, in the more common case you are thinking of, we don't necessarily know the type of the object being operated on when writing "code." We may know a supertype (we may know it's a number, but not know if its an integer or a float), but we don't know the actual type of the object. Some operations can only be defined with respect to the actual type (such as virtual function calls or dynamic casting). And so we need a way to know what the actual type of the object is.

This is typically done by adding data into the object itself. This is the extra 4 bytes you described in your example. Now you can implement this partially dynamic operation more like a static one -- its a static operation that operates on the widened object that knows its own type, rather than just thinking of it as a dynamic operation on the narrowed object (that only has the 4 bytes of data).

In a "dynamically typed language," the majority of decision making like this is made by inspecting data tacked on by the compiler, rather than just looking at the contents of the narrow objects.

Your description of a dynamic typed language operation is pretty accurate, but it tends to be a little more complicated. Typically some information about the object is stored in a strongly-typed or more-strongly-typed form (a vtable in most C++ implementations, or a dict member in python). So the operation might look like

Look at the first 4 bytes of the object. Use it as a lookup to find the add function for whatever type this is. Execute that. That function will then look at the first 4 bytes of the other object, and using that it will decide which function to call to add the numbers.

Now I mentioned these things blur a bit. Consider C++'s virtual functions. If you call a virtual function in C++, it uses the function defined on the most-derived type. So while most of C++ is statically typed, virtual function lookup is dynamic. And, no surprise, you find that extra 4bytes (8 bytes on 64-bit machines) needed to store type information on any object that has virtual functions. However, in the name of efficiency (and matching C), if there are no virtual functions on a type, C++ won't waste any bytes describing its type at runtime in the data. So as you can see, when we blur the line between static and dynamic typing, we see the same blurring between information stored in the code and information stored in the data.

Exploring the cases you describe:

• Static typed, compiled - In these language settings, all of the information about how to do behaviors is baked into the code. Objects tend to be just large enough to store the data for the object.
• Static typed, interpreted - These are exactly identical to static typed compiled languages, except that they are interpreted. Instead of the type information being found in the compiler, it is found in data at runtime. However, instead of being in the form of "A is a floating point number," the information is stored with respect to the code: "The argument to this function, whatever object it was, is a floating point number."
• Dynamic typed, compiled - In these languages, information about the type is added to each object. That "metadata" is sufficient to decide which behavior to use. So thus, after adding this data, all operations can now be completed as-if they were static typed, just with a more complicated type that holds metadata.
• Dynamic typed, interpreted - These are exactly identical to dynamic typed compiled, except that they are interpreted, and there is no reason to go through the extra step of re-writing the operations as static-typed operations. You just operate on the data directly.

If we say "type checking will occur at runtime," we are typically talking about a static typed language that has some dynamic typing elements in it. A purely dynamic typed language will also do type checking at runtime, but that's basically the definition of a dynamic typed language so there's no reason for people to state the obvious. We tend to only state it in the static typed language case, where it isn't obvious.

In such cases, what that means is that some of the type checking could not be done at compile time. As much type checking as possible is done (and possibly causing a compiler error if the type checking fails when we expected it to succeed), and the rest of the type checking is left to runtime. What that means is that there will be some data-driven logic, using the extra information that the compiler tacked onto the objects, to do this last bit of type checking right when the code is executed. This typically comes with some definition of what should happen if types do not match (for example, C++'s dynamic_cast will return a null pointer if the object doesn't actually implement the expected type).