5.3 The Interpreter

The interpreter is the engine that actually runs the code emitted by the parser, compiler, and optimizer modules. The Parrot execution engine is a virtual CPU done completely in software. We've drawn on research in CPU and interpreter design over the past forty years to try and build the best engine to run dynamic languages.

That emphasis on dynamic languages is important. We are not trying to build the fastest C, Forth, Lisp, or Prolog engine. Each class of languages has its own quirks and emphasis, and no single engine will handle all the different types of languages well. Trying to design an engine that works equally well for all languages will get you an engine that executes all of them poorly.

That doesn't mean that we've ignored languages outside our area of primary focus—far from it. We've worked hard to make sure that we can accommodate as many languages as possible without compromising the performance of our core language set. We feel that even though we may not run Prolog or Scheme code as fast as a dedicated engine would, the flexibility Parrot provides to mix and match languages more than makes up for that.

Parrot's core design is that of a register rich CISC CPU, like many of the CISC machines of the past such as the VAX, Motorola 68000, and IBM System/3x0. Many of the core opcodes—Parrot's basic instructions—perform complex operations. It also bears some resemblance to modern RISC CPUs such as the IBM Power series and Intel Alpha,^[3] as it does all its operations on data in registers. Using a core design similar to older systems gives us decades of compiler research to draw on. Most compiler research since the early 1970s deals with targeting register systems of one sort or another.

^[3] Formerly HP, formerly Compaq, formerly Digital Alpha.

Using a register architecture as the basis for Parrot goes against the current trends in virtual machines, which favor stack-based approaches. While a stack approach is simpler to implement, a register system provides a richer set of semantics. It's also just more pleasant for us assembly old-timers to write code for. Combined with the decades of sophisticated compiler research, we feel that it's the correct design decision.

5.3.1 Registers

Parrot has four basic types of registers: PMC, string, integer, and floating-point, one for each of the core data types in Parrot. We separate them out for ease of implementation, garbage collection, and space efficiency. Since PMCs and strings are garbage-collectable entities, restricting what can access them—strings in string registers and PMCs in PMC registers—makes the garbage collector a bit faster and simpler. Having integers and floats in separate register sets makes sense from a space standpoint, since floats are normally larger than integers.

The current Parrot architecture provides 32 of each register type, for a total of 128 registers. While this may seem like overkill, compensating for running out of registers can be a significant speed hit, so it's in our best interests to make sure it happens rarely. 32 is a good compromise between performance and memory usage.

5.3.2 Stacks

Parrot has seven separate stacks, each with a specific purpose. The four register sets each have its own stack for quickly saving register contents. There is a separate stack dedicated to saving and restoring individual integers, which the regular expression system uses heavily. The control stack keeps track of control information, exception handlers, and other such things. Finally, the general-purpose typed stack stores individual values.

The backing stacks for the register sets are somewhat special. Operations on the register stacks don't act on single registers. The engine pushes and pops entire register sets in one operation. This may seem somewhat unusual, but it makes the primary use of these stacks—to save registers across function calls—very fast. A save or restore operation is essentially a single memory copy operation, something that's highly optimized just about everywhere.^[4]

^[4] The SPARC processor, for example, has a cache-friendly memory copy as a core operation.

The integer stack is specifically designed to hold integers. Since it doesn't have to be general purpose, integer stack operations can be faster than operations on the general-purpose stack—a speed gain the regular expression code makes use of. Regular expressions make heavy use of integer code, as they move back and forth within strings, and make heavy use of the integer stack to manage backtracking information.

The control stack is private to the interpreter, so user code can't directly access it. The interpreter engine uses it to manage exception handlers, return locations for function calls, and track other internal data. User code can inspect the stack through Parrot's introspective features.

Finally, the general-purpose stack is used to save and restore individual registers. It's a typed stack, so it doesn't allow you to do things like push an integer register onto the stack and pop the value into a string register. For compiled code, this stack is used if a routine needs more than 32 registers of the same type. The extra values are pushed on and popped off the stack in an operation called register spilling. This stack is also used when Parrot runs code designed for a stack machine such as the JVM or .NET. Stack-based code is less efficient than register-based code, but we can still run it.

All of Parrot's stacks are segmented—they're composed of a set of stack pieces instead of a single chunk of memory. Segmenting has a small performance impact, but it allows us to make better usage of available memory. Traditional stacks are composed of a single chunk of memory, since this makes it faster to read from and write to the stack. Usually when you run off the end of that chunk of memory your program crashes. To avoid this, most systems allocate a large stack. This isn't much of a problem if you have only a single stack, but it doesn't work well in today's multithreaded world, where each thread has to have its own stack.

Another pleasant benefit of segmenting the stacks is that it makes supporting coroutines and continuations much easier. It is much easier to save off part of a segmented stack. Combined with Parrot's copy-on-write features, this makes for efficient continuations and coroutines. It may not be a feature that many folks will use, but it's a pleasant fall-out from other things.

5.3.3 Strings

Text data is deceptively complex, so Parrot has strings as a fundamental data type. We do this out of sheer practicality. We know strings are complex and error-prone, so we implement them only once. All languages that target Parrot can share the same implementation, and don't have to make their own mistakes.

The big problem with text is the vast number of human languages and the variety of conventions around the world for dealing with it. Long ago, 7-bit ASCII with 127 characters was sufficient. Computers were limited and mostly used in English, regardless of the user's native language. These heavy restrictions were acceptable because the machines of the day were so limited that any other option was too slow. Also, most people using computers at the time were fluent in English either as their native language or a comfortable second language.

That day passed quite a few years ago. Many different ways of representing text have sprung up, from the various multibyte Japanese and Chinese representations—designed for languages with many thousands of characters—to a half dozen or so European representations, which take only a byte but disagree on what characters fit into that byte. The Unicode consortium has been working for years on the Unicode standard to try and unify all the different schemes, but full unification is years away, if it ever happens.

In the abstract, strings are a series of integers with meaning attached to them, but getting from real-world data to abstract integers isn't as simple as you might want. There are three important things associated with string data—encoding, character set, and language—and Parrot's string system knows how to deal with them.

A string's encoding says how to turn data from a stream of bytes to a stream of characters represented by integers. Something like ASCII data is simple to deal with, since each character is a single byte, and characters range in value from 0 to 255. UTF-8, one of the Unicode encodings, is more complex—a single character can take anywhere from 1 to 6 bytes.

The character set for a string tells Parrot what each of the integers actually represents. Parrot won't get too far if it doesn't know that 65 is a capital "A" in an ASCII or Unicode character stream, for example.

Finally, the language for a string determines how the string behaves in some contexts. Different languages have different rules for sorting and case-folding characters. Whether an accented character keeps its accent when upper-cased or lowercased depends on the language that the string came from.

The capability of translating strings from one encoding to another and one character set to another, and to determine when it's needed, is built into Parrot. The I/O and regular expression systems fully exploit Parrot's core string capabilities, so any language that uses Parrot's built-in string functionality gets this for free. Since properly implementing even a single system like Unicode is fraught with peril, this makes the job of people writing languages that target Parrot (including Perl 6) much easier.

5.3.4 Variables

Variables are a fundamental construct in almost all computer languages.^[5] With low-level languages such as C, variables are straightforward—they are either basic hardware constructs like a 32-bit integer, a 64-bit IEEE floating-point number, or the address of some location in memory, or they're a structure containing basic hardware constructs. Exchanging variables between low-level languages is simple because all the languages operate on essentially the same things.

^[5] With the exception of functional languages, though they can be useful there as well.

Once you get to higher-level languages, variables get more interesting. OO languages have the concept of the object as a fundamental construct, but no two OO languages seem to agree on exactly how objects should behave or how they should be implemented. Then there are higher-level languages like Perl, with complex constructs like hashes, arrays, and polymorphic scalars as fundamental constructs.

The first big issue that Parrot had to face was implementing these constructs. The second was doing it in a way that allowed Perl code to use Ruby objects, Ruby code to use Python objects, and Lisp code to use both. Parrot's solution is the PMC, or Parrot Magic Cookie.

A PMC is an abstract variable and a base data type—the same way that integers and floating-point numbers are base data types for hardware CPUs. The languages we're working to support—Perl, Python, and Ruby—have base variables that are far more complex than just an integer or floating-point number. If we want them to exchange any sort of real data, they must have a common base variable type. Parrot provides that with the PMC construct. Each language can build on this common base. More importantly, each language can make sure that their variables behave properly regardless of which language is using them.

When you think about it, there is a large list of things that a variable should be able to do. You should, for example, be able to load or store a value, add or subtract it from another variable, call a method or set a property on it, get its integer or floating-point representation, and so on. What we did was make a list of these functions and make them mandatory.

Each PMC has a vtable, a table of function pointers, attached to it. This table is fixed. The list of functions, and where they are in the table, is the same for each PMC. All the common operations a program might perform on a variable—as well as all the operators that might be overloaded for a PMC—have vtable entries.

5.3.5 Bytecode

Like any CPU, software, or hardware, Parrot needs a set of instructions to tell it what to do. For hardware, this is a stream of executable code or machine language. For Parrot, this is bytecode. Calling it bytecode isn't strictly accurate, since the individual instructions are 32 bits each rather than 8 bits each, but since it's the common term for most other virtual machines, it's the term we use.

Each instruction—also known as an "opcode"—tells the interpreter engine what to do. Some opcodes are very low level, such as the one to add two integers together. Others are significantly more complex, like the opcode to take a continuation.

Parrot's bytecode is designed to be directly executable. The code on disk can be run by the interpreter without needing any translation. This gets us a number of benefits. Loading is much faster, of course, since we don't have to do much (if any) processing on the bytecode as it's loaded. It also means we can use some special OS calls that map a file directly into the memory space of a process. Because of the way this is handled by the operating system,^[6] the bytecode file will be loaded into the system's memory only once, no matter how many processes use the file. This can save a significant amount of real RAM on server systems. Files loaded this way also get their parts loaded on demand. Since we don't need to process the bytecode in any way to execute it, if you map in a large bytecode library file, only those bits of the file your program actually executes will get read in from disk. This can save a lot of time.

^[6] Conveniently, this works the same way for all the flavors of Unix, Windows, and VMS.

Parrot creates bytecode in a format optimized for the platform it's built on, since the common case by far is executing bytecode that's been built on the system you're using. This means that floating-point numbers are stored in the current platform's native format, integers are in the native size, and both are stored in the byte order for the current platform. Parrot does have the capability of executing bytecode that uses 32-bit integers and IEEE floating-point numbers on any platform, so you can build and ship bytecode that can be run by anyone with a Parrot interpreter.

If you do use a bytecode file that doesn't match the current platform's requirements (perhaps the integers are a different size), Parrot automatically translates the bytecode file as it reads it in. In this case, Parrot does have to read in the entire file and process it. The sharing and load speed benefits are lost, but it's a small price to pay for the portability. Parrot ships with a utility to turn a portable bytecode file into a native format bytecode file if the overhead is too onerous.