MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > March-April 2007 > Article Detail

COMPUTING SCIENCE

# Trains of Thought

Computing with locomotives and box cars takes a one-track mind

Tracking Data

Sidings, wyes and other devices for directing trains inspired some of the earliest ideas about managing the flow of information through a computer program. In 1961 Edsger W. Dijkstra included a diagram of a railroad wye in a memorandum about methods of translating the new programming language Algol 60. In parsing an expression such as 3x(5+2), the seven symbols are read from left to right, but they must be acted on in a different order: First the subexpression inside the parentheses is evaluated by adding 5 and 2, then the result of this operation is multiplied by 3. Dijkstra showed that the reordering can be accomplished by temporarily storing the operators (such as x and +) in a data structure called a stack. The stack is a first-in, last-out storage device; in this case the x sign goes in first, followed by the + sign, but they come out in the opposite order. Dijkstra chose to explain this principle in terms of a railroad wye. One of the three tracks serves as input, one as output, and the third provides the first-in, last-out storage.

A few years later Donald E. Knuth, in the first volume of The Art of Computer Programming, gave railroading interpretations of three important data structures: the stack, the queue and the double-ended queue, or deque. The queue is the simplest of these—at least for railroaders. A queue is a first-in, first-out data structure, and so it is represented by a simple straight length of track. Cars put in at one end of the queue come out the other end in the same order. A deque is an arrangement of tracks allowing cars to be added at either end and removed from either end (but there is no access to cars in the middle of the train). Knuth illustrates a deque by a complicated layout of two back-to-back jug-handle loops, requiring four switches. The same functions can also be accomplished by an ordinary siding, provided that trains are allowed to back up in order to pass through a trailing-point switch. (The siding and the double-jug-handle layouts differ in their effect on the orientation of the cars.)