Compilers – Cool Type Checking & Runtime Organization: my study notes

These notes are from the Week 6 of the Compilers course by Stanford. This week is going over how the Cool type checking and runtime organization are going to be organized.

Static and Dynamic typing

Dynamic and Static types vary in which time they are evaluated. Static typing is evaluated in compile-time without knowing any input from the user. On the other hand, dynamic typing can only be evaluated at the time the program is run. It is important to know, that those terms can be related to the same programming language, depending on what you are talking about.

For example, let’s consider an Object-Oriented language:

class A {}
class B extends A {}

...
x: A = new A(); <- A is both the dynamic and the static type
...
x = new B(); <- A is the static type whereas B is the dynamic type
...

So for a language that doesn’t support inheritance, for example, we can say the dynamic_type(E) = static_type(E) on the other hand, for OO languages we can say dynamic_type(E) <= static_type(E).

Self Type

The self type is needed to enforce static checking for methods that return their own class. We can have a method A::inc(): A and when we inherit A on B, we would fail on type checking if we want to use something like b: B = (new B).inc() because the inc method returns anything that inherits A or is A, which is not what the assignment expects. To solve that, we could have a definition like A::inc(): self which would be able to check in compile time the previous example.

To recover from errors of type checking a NoType that inherits from every type can be introduced.

Runtime Organization

This is the first phase of the back-end of the compiler. All previous steps (lexical analysis, parsing, and semantic analysis) are the compiler’s front-end and serve the purpose of enforcing the language definition. On the other hand, the back-end of the compiler is responsible for optimization and, of course, code generation.

To really grasp compilers, it is important to understand the difference between static data structures and dynamic ones. The first ones are used during the compilation process whereas the second ones are used during the execution of the program.

Memory

The first thing to happen when a program starts running is that the OS allocates a space of memory and the code is loaded in the low portion of it. The rest of the memory allocated is reserved for other uses during the execution of the program.

Activation procedures are things that happen in runtime that are necessary for a program to run (e.g., a method call). The activation tree of a program can be represented as a tree with several siblings, but for practical purposes, only the current state is usually represented and the data structure chosen is a stack.

Representation of the memory during the execution of a program

The records produced by the activation procedures are commonly called frames and contain all the data necessary for the program to correctly make that activation. The frames usually contain information about the caller and the function that is being called. One example might be a data structure like this:

struct frame {
  result,
  arguments,
  caller_frame,
  caller_address
}

The first field, result, is responsible for storing the return value of the function that is being called. It is important to keep it in the first position because it makes it easier for the caller to find this value when necessary. The second field, arguments, stores the arguments that the function has been called with. The third, which is caller_frame, points to the address which the frame of the caller is stored. And last, the caller_address, points to the address in code which the code must resume executing should this function returns.

Regions of memory

So we can divide the memory during the execution of a program into four regions: code, static data, heap, and stack. All, but the third were mentioned previously. The heap is usually where all dynamically allocated objects live. So whenever a C program calls malloc and free it is in the heap that this data will live.

One important concept is alignment, which is basically to keep data aligned in memory with the size of the word of the machine.

Leave a Reply

Your email address will not be published. Required fields are marked *