In computer science, threaded code is a programming technique where the code has a form that essentially consists entirely of calls to subroutines. It is often used in compilers, which may generate code in that form or be implemented in that form themselves. The code may be processed by an interpreter or it may simply be a sequence of machine code call instructions.
Threaded code has better density than code generated by alternative generation techniques and by alternative calling conventions. In cached architectures, it may execute slightly slower. However, a program that is small enough to fit in a computer processor's cache may run faster than a larger program that suffers many cache misses. Small programs may also be faster at thread switching, when other programs have filled the cache.
Threaded code is best known for its use in many compilers of programming languages, such as Forth, many implementations of BASIC, some implementations of COBOL, early versions of B, and other languages for small minicomputers and for amateur radio satellites.
History
The common way to make computer programs is to use a compiler to translate source code (written in some symbolic language) to machine code. The resulting executable is typically fast but, because it is specific to a hardware platform, it isn't portable. A different approach is to generate instructions for a virtual machine and to use an interpreter on each hardware platform. The interpreter instantiates the virtual machine environment and executes the instructions. Thus, only the interpreter must be compiled.
Early computers had relatively little memory. For example, most Data General Nova, IBM 1130, and many of the first microcomputers had only 4 kB of RAM installed. Consequently, a lot of time was spent trying to find ways to reduce a program's size, to fit in the available memory.
One solution is to use an interpreter which reads the symbolic language a bit at a time, and calls functions to perform the actions. As the source code is typically much denser than the resulting machine code, this can reduce overall memory use. This was the reason Microsoft BASIC is an interpreter: its own code had to share the 4 kB memory of machines like the Altair 8800 with the user's source code. A compiler translates from a source language to machine code, so the compiler, source, and output must all be in memory at the same time. In an interpreter, there is no output.
Threaded code is a formatting style for compiled code that minimizes memory use. Instead of writing out every step of an operation at its every occurrence in the program, as was common in macro assemblers for instance, the compiler writes each common bit of code into a subroutine. Thus, each bit exists in only one place in memory (see "Don't repeat yourself"). The top-level application in these programs may consist of nothing but subroutine calls. Many of these subroutines, in turn, also consist of nothing but lower-level subroutine calls.
Mainframes and some early microprocessors such as the RCA 1802 required several instructions to call a subroutine. In the top-level application and in many subroutines, that sequence is constantly repeated, with only the subroutine address changing from one call to the next. This means that a program consisting of many function calls may have considerable amounts of repeated code as well.
To address this, threaded code systems used pseudo-code to represent function calls in a single operator. At run time, a tiny "interpreter" would scan over the top-level code, extract the subroutine's address in memory, and call it. In other systems, this same basic concept is implemented as a branch table, dispatch table, or virtual method table, all of which consist of a table of subroutine addresses.
During the 1970s, hardware designers spent considerable effort to make subroutine calls faster and simpler. On the improved designs, only a single instruction is expended to call a subroutine, so the use of a pseudo-instruction saves no room. Additionally, the performance of these calls is almost free of additional overhead. Today, though almost all programming languages focus on isolating code into subroutines, they do so for code clarity and maintainability, not to save space.
Threaded code systems save room by replacing that list of function calls, where only the subroutine address changes from one call to the next, with a list of execution tokens, which are essentially function calls with the call opcode(s) stripped off, leaving behind only a list of addresses.