Editing Threaded code (section)

==History==
{{Original research section|date=February 2020}}
The common way to make computer programs is to use a [[compiler]] to translate [[source code]] (written in some [[Symbolic language (programming)|symbolic language]]) to [[machine code]]. The resulting [[executable]] is typically fast but, because it is specific to a [[computer hardware|hardware]] platform, it isn't portable. A different approach is to generate [[instruction set|instructions]] for a [[virtual machine]] and to use an [[interpreter (computing)|interpreter]] on each hardware platform. The interpreter instantiates the virtual machine environment and executes the instructions.  Thus the interpreter, compiled to machine code, provides an abstraction layer for "interpreted languages" that only need little compilation to conform to that layer (compilation may be confined to generating an [[Abstract Syntax Tree]]) or even need no compilation at all (if the layer is designed to consume raw source code.)

Early computers had relatively little memory. For example, most [[Data General Nova]], [[IBM 1130]], and many of the first [[microcomputer]]s had only 4&nbsp;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 [[code density|denser]] than the resulting machine code, this can reduce overall memory use. This was the reason [[Microsoft BASIC]] is an interpreter:{{efn|[[Dartmouth BASIC]], upon which [[Microsoft BASIC]] is ultimately based, was a compiler that ran on mainframe machines.}} its own code had to share the 4&nbsp;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 assembler]]s 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.{{Citation needed|date=March 2020|reason=storing only the address of the subroutine actually does save room compared to storing a call instruction, which necessarily must contain something in addition to the address of the subroutine.}} 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.<ref>
David Frech.
[https://muforth.nimblemachines.com/readme/ "muforth readme"].
section "Simple and tail-recursive native compiler".
</ref><ref name="heller">
Steve Heller.
[https://books.google.com/books?id=gaajBQAAQBAJ "Efficient C/C++ Programming: Smaller, Faster, Better"].
2014.
Chapter 5: "Do you need an interpreter?"
p. 195.
</ref><ref>
Jean-Paul Tremblay; P. G. Sorenson.
[https://books.google.com/books?id=MacmAAAAMAAJ "The Theory and Practice of Compiler Writing"].
1985.
p. 527
</ref><ref>
[https://books.google.com/books?id=4WJVAAAAYAAJ "Wireless World: Electronics, Radio, Television, Volume 89"].
p. 73.
</ref><ref>
[https://books.google.com/books?id=ZWIfAAAAMAAJ "Byte, Volume 5"].
1980.
p. 212
</ref>

Over the years, programmers have created many variations on that "interpreter" or "small selector". The particular address in the list of addresses may be extracted using an index, [[general-purpose register]] or [[pointer (computer programming)|pointer]]. The addresses may be direct or indirect, contiguous or non-contiguous (linked by pointers), relative or absolute, resolved at compile time or dynamically built. No single variation is "best" for all situations.