Compilers, Interpreters and Portability

Once upon a time there were three different ways to implement a programming language, and typically a given language was implemented in only one of these ways. Compiled languages were translated into machine language. An assignment statement would pretty reliably get translated into a piece of code ending in a memory store or a register load. An addition expression would pretty reliably get translated into a piece of code ending in a machine ADD instruction.

But compilation was a lot harder to do for languages such as Lisp that didn’t have fixed declared types. In Lisp an addition expression requires some runtime decision making to decide exactly what it means at that point in the code on that particular execution. So we had interpreted languages which were translated into code for a virtual machine and then we had an interpreter which would execute this virtual machine code.

And finally there were the scripting languages which were not translated at all. Instead an interpreter would read the text representation of the program and interpret it directly.

Over time a lot of these distinctions have faded. A lot of scripting languages are now translated into a VM language and interpreted. A lot of languages that started out as interpreted languages now have compilers and those that still have interpreters sometimes also have just-in-time (JIT) compilers which compile the VM code into machine code. There are even interpreters that interpret compiled languages like C for use in debuggers and related tools.

The tradeoff between compilers and interpreters is that compiled code tends to be faster while interpreted code tends to be more portable. Interpreted code is more portable in the sense that you have to write just one portable program --the interpreter itself-- and then every machine that has an interpreter can execute the VM code, which is the same for all machines.

Interpreters typically have a execution loop which reads each VM instruction, figures out what the instruction means, and then does what the VM instruction says to do. It isn’t unusual for it to take dozens of machine instructions to execute one VM instruction. On the other hand, VM instructions tend to do more than machine instructions do so the interpreted language needn’t be dozens of times slower than compiled. As a rule of thumb, interpreted programs tend to be about an order of magnitude slower than compiled programs.

JIT is designed to give the best of both worlds --you build a compiler into the interpreter and then you can have portable compiled code. But taking a VM that was designed for an interpreter and compiling it is not an ideal solution because there are different requirements for a VM language that is to be interpreted vs. one that is to be compiled. A VM language that is to be interpreted should be compact so that the VM code itself does not take up so much of the data cache. The VM should be designed so that instructions can be analyzed quickly and efficiently so that the interpreter loop can be fast. Finally, the VM language should be high-level, letting you do a lot of work with a smaller set of instructions. This helps out with the data cache and also means that you have fewer instructions to interpret so there is less overhead from the interpreter loop. Also, a high-level interpreted language means that more work is done as part of the interpreter code which is compiled and therefore faster.

By contrast, a VM that is meant to be compiled has none of those requirements. A VM for compiling should be low-level to support low-level optimization and this is in conflict with the requirement for interpreted VMs to have high-level code. Also, the requirements for compact code and quick analysis of instructions suggests that you need a stack-based VM or a VM with a small fixed set of registers. This is not compatible with a compilable VM --at least not a portable one, which can be compiled for machined with greatly varying numbers of registers and greatly varying register characteristics.

So a VM designed to be portable and to be compiled rather than interpreted looks a lot different from a VM designed to be interpreted. I know of two different VM architectures designed to be portable and to be compilable. One project called Tendra was based on a format called ANDF --the Architecture-Neutral Distribution Format. Unfortunately, Tendra never gathered much of a following and it has largely died out.

A more recent and very active project is LLVM which is gaining steam very rapidly. In my view, this sort of technology should have been adopted a decade ago but there was just no stopping the juggernaut that was Java and the JVM. Still, things are looking up with LLVM and I have high hopes for more efficient portable programs in the near future.

Parameter Passing and Assigment

An initialization is an expression that introduces a new name and sets it to some value. For example in C we can write something like this:

int x = 5;

This declares a new variable x and sets the value to 5.

Parameter passing is similar to initialization in the sense that it introduces a new name and gives it a value. The primary difference between parameter passing and initialization is where you write the expression that the name gets initialized with. In an initialization the expression is right there in the initialization; in parameter passing, the expression is the actual parameter at the call site.

Parameter passing can also have variations such as pass-by-var and pass-by-thunk. The same sorts of variations could apply to initialization although these variations are not as widely supported in programming languages. C++ does have a construct that is equivalent to a pass-by-var initialization. In C++, the way that you show pass-by-var parameter passing is by declaring the formal parameter as a reference variable:

int f(int& ref) { ref = 10;}

When you call f, you have to call it with a variable as the actual parameter, and you get pass-by-var:

int x = 5;

f(x);

// here the value of x is 10

The same rule applies to initialization. You can declare a local variable as a reference. In this case you need to initialize  with a variable and it makes the new name an alias for the name that you use to initialize with, exactly as pass-by-var does:

int x = 5;

int& ref = x;

ref = 10;

// here the value of x is 10

In some languages such as Pascal, when you call a function with no arguments, you just use the function name:

function f begin write(‘hello’); end;

begin

 f;

end;

Such function definitions behave similarly to initialize-by-thunk.

Here is another example of unusual initialization: the C preprocessor gives an effect similar to initialize-by-text. A preprocessor directive like

#define f while

lets you write a statement like this:

f(x<0) {...}

and it gets treated just ilke

while (x < 0) {...}

So although there are ways in various languages to get some of the different parameter passing effects in initializations, it is generally ad hoc. What Unobtainabol needs is a generic binding mechanism that includes both parameter passing and initialization in the same framework with the same features. But there are a more issues to deal with before we can suggest such a mechanism. In particular, the name-binding mechanism needs to address logical variables and types as values because these are important features that no perfect language can do without.

Log Forwarding for Text Editors III

In a previous post, I discussed how to handle failures of the commit message. This post will discuss failures of the editing process.

The editing process is just the time between commit messages. It involves the user typing, the client/editor updating the screen, the client sending redo log messages to the server, the client saving redo log messages, and the server receiving and saving redo log messages.

The failures that can occur during this process are:

The client might crash. If the client crashes then it either loses data or it doesn’t. If the client does not lose data then we can recover the editing state by starting with the latest checkpoint and apply the redo log up to the point of the crash. If the client loses data then we recover from the log on the server. The recovery process has to detect whether there was data loss on the client and to properly apply the redo log either from the client or the server.

The network might not deliver the a message. In this case, the client has the correct data on it and the user can continue to work but the server gets out of sync. This situation has to be detected and corrected before applying a checkpoint.

The server might crash. If the server loses data in the crash, then the data has to be recovered from the client as part of the recovery process. If the server does not lose data, then it still needs to be brought up to date with any work that the user continued to do after the crash.

One way to handle network failures is to use a reliable connection-based network protocol like TCP. These protocols use their own techniques, designed, implemented, and tested by experts to ensure that no information gets lost, and if we could assume a moderately reliable network then that would be my choice. But this application is intended to work on poor networks with unreliable connections, and such networks give fits to TCP.

Instead, I’m going to use TCP only for short special sessions like going through the recovery process, and the rest of the time I’ll assume a network protocol that does not guarantee that all packets get delivered but does offer some assurance that that if a packet gets delivered then it is correct; that is, the packet that gets delivered is the one that the sender sent.

To handle the above situations, we are adding a serial number to the redo log messages and also attaching the serial number of the previous checkpoint. In other words, Each redo log message comes with two serial numbers. One is a checkpoint serial number and the other is a message serial number that increases with each log message after a checkpoint. The message serial number gets reset to 0 after a checkpoint. The checkpoint message also gets a new field --the largest message serial number in the list of log messages for the checkpoint. This way the server can verify that it has all of the redo log that it needs for the checkpoint.

The client increments the message serial number for each log message and sends it to the server, recording the message itself in a list. The server also keeps a list of log messages that it receives so that it knows if a message is missing. Periodically, the server will send the client a list of log messages that it is missing. The client will receive these messages and resend the missing log messages. Notice that since we are dealing with a network failure situation, the server’s message back the client asking for missing messages can get lost and the client’s response to such a message can get lost. We can’t assume that any of it is reliable.

I’m not an expert on designing protocols for unreliable networks, so that’s all the farther I’m going to go with fixing packet losses. When the server receives a checkpoint message, if it does not have all of the packets it needs for the checkpoint, it will wait a few seconds for more packets to come in. If it still does not have all of the messages it needs, then it will send back a failure message to the client.

At this point, the client will attempt to open a TCP connection to the server to fix the problem. If it can’t open the connection or the connection drops while the fix is taking place, then the client acts as if there has been a total network failure. The user can continue to work without the backup of having a server and the client will still keep trying to contact the server every few minutes, but now it is sending recovery messages, not log messages.

A recovery message is a message from the client to the server that says basically: “I am on checkpoint X, log message Y”. The server has three potential replies:

1. I am up to date.
2. I am missing log messages A,B,C,...
3. My checkpoint is older than yours.
4. You are missing log numbers from Y to Z
5. My checkpoint is newer than yours.

If the client receives reply 1 then it resumes sending redo log messages. If it receives any other reply or the reply times out, then it tries to open a TCP connection to resolve the issue. It resolves the issue by copying the missing data from the source with the newer data to the one with the out-of-date data. If it ends up with a message serial number greater than 0 (that is, there are redo log messages that have not been appied to a checkpoint) then it sends a checkpoint message.

Every time the user opens an existing file, the client begins by sending the server a recovery message to make sure things are up to date.

Definitions, Declarations, and Constraints

If you know anything about programming languages, the title of this section probably strikes you as strange. It is common to group definitions and declarations together, but constraints are usually considered an entirely different topic. However, declarations in common programming languages are rather complex creatures and a part of what they do is very much like a constraint.

This section will analyze the three concepts and see how they are related. All of the concepts involve namespaces, so first lets talk about namespaces.

Namespaces

A namespace is any sort of mapping from names to denotations. It may be a package, module, class, function body or block among other things. Anything that maps names to denotations is a namespace. The mapping is also called a binding.

Here is an example from Java

class C {

 int j;

 int f(int x) {int y; y = j; return x+y;}

 static int g() {}

};

In this example there are many namespaces:

1. The global namespace (or more properly the package namespace) maps C to a class. The phrase beginning with “class C” introduces that binding into the global namespace.
2. The class C itself is a namespace that maps g to a static function. The phrase beginning with “static int g” introduces that name.
3. When the class is instantiated into an object obj, then obj will be a namespace that maps j to a location. Note that the phrase “int j” introduces the name j into a runtime namespace when it gets executed, not a static namespace like the previous two definitions.
4. When f is called, it will create a runtime namespace to hold local variables x.
5. When control enters the body of f, it will create another runtime namespace in the block, and this namespace is where y is bound.
6. When g is called it will create a runtime namespace with no members.

There are two ways to view f in the above example. In Java, C++ and many other languages one would say that f is a function that is a member of the class namespace C. When you call the function in an expression like obj.f(3), this is treated as a call to a function that looks like it has only one argument but really has two: obj and 3. You could rewrite the call to something like f(obj,3), and change the definition of f to something like

int f(C o, int x) {int y; y = o.j; return x+y;}

All I did was add o as an argument and replace the unbound variable j with o.j.

That is the C++ and Java way to view member functions. There is another way to view them and that is to say that when the class is created, it creates a closure for each member function and binds the function name to the closure in the object namespace. More on that when I get around to discussing SL5.

Definitions

A definition is a phrase that gives a name a denotation in a namespace. We say that the definition binds the name in the namespace. For example

const x=100;

binds the name x to the number 100 and the definition

function sum(x,y,z) {return x+y+z;}

finds the name sum to a function.

Variable declarations are also definitions because they bind a name to a location:

var x,y;

var z:integer;

Constraints

There is a class of programming language called constraint programming languages that use constraints as the primary programming paradigm (a logic programming language is a type of constraint programming language where the constraints look a bit like predicate logic). Constraints can be useful even if they don’t form the primary programming paradigm, but I don’t know of any languages that use general constraints in the more limited way that I will discuss in this subsection.

A constraint is a condition that is enforced by the language implementation. For example, in a language with constraints you might be able to write something like this:

constraint x < 0;

and this would cause the compiler to always ensure that x is a negative number. It might do this by checking the value every time x changes, or it might use some sort of logic to prove that the algorithm can never assign a non-negative number.

Constraints like the one above primarily apply to variables. After all, what’s the point of constraining the value of a constant?

But there are other constraints like this:

constraint y = 2*x;

where the compiler could implement the constraint by treating y as another name for 2*x. In this case y would not be a variable (a name that denotes a location) because it denotes twice the value of whatever x denotes.

As you can see, a constant definition looks a lot like a special case of a constraint. For example

constraint y = 2;

seems to have the same effect as

const y = 2;

The only difference is that the definition introduces a new name while a constraint does not. A constraint works on names that are already in scope. Otherwise, consider the problem of deciding what names the following constraint would introduce into scope:

constraint x=y and z=2 and y<3

Declarations

A declaration is a phrase that describes the features of a name that a language needs in order to use the name. In statically typed languages, the language cannot use a name unless the type is known, so a name declares the type of the name. In C, for example you have declarations like this:

extern int x;

extern void f(int);

These declarations do not define anything; all they do is tell the following code how to use the names. They tell the following code that x is an integer variable and that f is a function that takes one integer argument and returns no value.

In other cases, a declaration is combined with a definition:

var x:integer;

This phrase does four different things:

1. Introduces a new name, x, into the namespace of the innermost block.
2. Binds x to a new location.
3. Attaches the signature, integer, to x.
4. Constrains x so that it can only reference an integer.

The difference between 3 and 4 involves overloaded functions and operators. In a language with static types and overloading, the particular function or operator that is chosen for an expression depends on the signature of the expression. But there is nothing inherent in a signature that constrains the type of values put into a variable. There is nothing logically contradictory about telling the compiler “always use floating point computations on x” and then putting an integer value in x. It may be error-prone and machine-dependent, but it isn’t contradictory. In fact, C and C++ allow doing just that.

In C and C++, a declaration

int x;

assigns a signature to a variable and that signature means that an assignment to the variable such as

x = 4.0;

uses a branch that converts the value to an integer before assigning it to the location. This is one way that a language might enforce a constraint, but it isn’t reliable enforcement when the language has other ways to assign a value to a location. In the ultimate programming language, a constraint must be fully enforced. So in C and C++, a type declaration only attaches a signature to a name and does not impose a constraint.

In other languages such as Common Lisp, a declaration only imposes a constraint and does not attach a signature. In Common Lisp if you declare a variable:

(declare (type integer x))

Then try to assign a non-integer to the variable:

(setf x "foo")

it raises an error. This is the constraint-checking in action. However, such a declaration does not attach a signature to x. Signatures have no meaning in Common Lisp because there is no overloading of functions. When you add x to another number:

(+ x 1)

there is only one branch of + and it uses that branch regardless of any declarations (although + is defined to dynamically check the types of its arguments and do the right thing, and this type checking might be in-lined and then the in-lined tests might be solved at compile-time and then removed).