particular problem, but we often forget
that a data structure also contains explanatory power.
The choice of data structures helps
convey the meaning. You could store
a bunch of elements in an array, but
what if you need to ensure the elements are unique? Isn’t that what sets
are for? The underlying representation of your set can still be backed by
a plain array, but now your program
expresses its intentions in a clearer
way. Whenever other programmers
read it, they will understand that the
elements in your collection must be
unique. It is important to realize that a
program is just another succession of
bits that a computer needs to process.
It is the programmer who gives meaning to those bits, so you have to use the
right metaphor on top of them to make
your program clearer. As has been said,
“no one has seen a program which the
machine could not comprehend but
which humans did.”
You must strive to make your program as easy as possible for other programmers to understand. Ease of comprehension should be the standard by
which programs are measured. Keep
in mind that you can arrange code in
many different ways to solve a computing problem, but not all those arrangements will favor human communication and understanding. You must ask
yourself: By reading my code, will others understand how I solved this particular problem?
Just as metaphors enable certain
ways of understanding and limit others, so do data structures. Earlier we
saw the problem with using direct
metaphors such as the original tele-graph. When it comes to data structures, you can see that a set will reveal
that its elements are unique, and it
will allow you to test if an element is a
member of the set. With a linked list,
however, you get the idea of traversing its elements one after the other,
without being able to skip them.
With an array you get the idea that
you can address its elements by index.
The same can be seen with queues
and stacks, two of the most fundamental data structures taught in any
algorithms course. Each can be implemented using an array—the difference is that one returns the elements
in FIFO (first in, first out) order, while
ematical Theory of Communication, put
forth the basic elements of communication: information must be encoded
first, then sent into a channel to be decoded at the other end, so the destination receives it.
Metaphors and Code
A well-known unattributed quote (often
misattributed to Charles Baker) is, “To
program is to write to another program-
mer about our solution to a problem.”
A program is an explanation of how a
problem might be solved; it’s a meta-
phor that stands in place of a person’s
understanding. For metaphors to be
effective, however, they need to con-
vey meaning using concepts already
known to us. The explanatory power of
a particular program can be used as a
measure of its own elegance.
Consider the following example.
Say you could program a computer to
command other computers to perform
tasks, respecting their arrival order.
This description is already difficult
to understand. On the other hand,
you could describe the solution by
describing a queue server that assigns
jobs to workers based on a first come
first served queue discipline.
A queue is a familiar concept from
daily life, seen at the supermarket, the
bank, airports, and train stations. Peo-
ple know how they work, so for some-
one reading your code, it might be eas-
ier to talk about queues, workers, and
jobs than trying to explain this setting
without using the queue metaphor.
By choosing the right metaphor,
your program reaches a level of abstraction that requires the least
amount of effort for someone foreign
to the problem to understand the solution. Also, solving the problem with
queues provides a whole mathematical
theory for free. Mathematics is itself a
field where problems are tackled only
when an appropriately expressive language is available to approach them.
With the queue metaphor, you are no
longer punching blindly in the dark.
Now you can analyze and understand
the problem with all the tools provided
by queueing theory.
Data Structures as Metaphors
Analyzing data structures helps us
to see which would be a better fit for
the performance characteristics of a
the right metaphor,
reaches a level of
requires the least
amount of effort
for someone foreign
to the problem