- Its All Bits and Bytes
- The Rise of Structure
- Higher Abstractions
- Rise of the Type Theorists
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
The Rise of Structure
The only kind of flow control available in a simple assembly language is the jump. As Edsger Dijkstra famously wrote in his paper "GOTO Considered Harmful," this is not a very good way of structuring programs.
The proposed solution to this was to introduce subroutines (also often called functions or procedures) and a stack for flow control.
A subroutine is a block of code that you would jump to, and then have control returned to the place of the call afterward.
The first way of implementing them was to write the return address just before the first instruction in the subroutine. This is very easy to do, but there is a problem: there is no way for a subroutine to call itself.
The solution was to use a stack, which is a simple data structure in which values are retrieved in the opposite order to their insertion.
When you were about to jump to a subroutine, you would push the return address onto a stack and then jump to the start of the subroutine. At the end of the subroutine, it would get the top value from the stack and jump to it. This allowed a procedure to call itself as many times as you have stack space to store addresses. Some architectures, such as x86, include instructions for performing these operations.
This idea was extended to enable other values to be stored on the call stack. If a subroutine needed some private space, it would move the location of the top of the stack up a bit, and use the gap.
This turned out to be a spectacularly bad idea because it meant that small bugs in a program could make it easy for specially crafted input to overwrite the return address.
A better solution would have been to use a separate stack, but this has not proved popular. The stack is also used for passing parameters to and from functions.
The archetypal stack-based language is Forth, which provides separate stacks for data and flow control. In Forth, the language itself is stack-based, resembling reverse polish notation.
Subroutines in Forth are known as words because this is how they are represented in the code. The interpreter simply scans a line of input, pushing the values onto the stack or executing a subroutine when a word is encountered.
The ability to add words to Forth makes it well suited to metaprogramming because new words (subroutines) are indistinguishable from the core language to a programmer.
Forth is used in OpenFirmware, a firmware standard used for PowerPC and SPARC (with an x86 implementation available from the OpenBIOS project). This allows Forth programs to be stored on expansion cards, and then compiled (or interpreted) for the host architecture at runtime, giving CPU architecture and operating-system–independent device drivers.
A related construct that gained some popularity at the same time was the coroutine. While a subroutine is good for two pieces of code where one is subordinate to the other, coroutines work better when there is not such a clear division between the two.
Coroutines are often used to simulate parallelism. While most modern languages don’t have support for coroutines directly, they are common at the framework level for GUI programming, in which events are tied to particular actions.
These event handlers are run to completion by some form of run loop, which is often hidden from the developer, giving the appearance of events happening independently.