COMPUTING SCIENCE
Trains of Thought
Computing with locomotives and box cars takes a one-track mind
Brian Hayes
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.)
» Post Comment