letters to the editor
DOI: 10.1145/2209249.2209251
an integral number and its Consequences

Pondering Moshe Y. VArdi’s Editor’s Letter “What Is an Algorithm?” (Mar. 2012), one should consider the fact hat in its most abstract and tangible form an algorithm is simply an integral number and that an interpretation of an algorithm as an abstract state machine reflects this truth.

A researcher or engineer can then hypothesize other representations of the algorithm’s number that might enhance computational efficiency.

One truly elegant notion supporting computational theory is that each of us can interpret a number’s symbolic representation differently. Depending on which lens one uses, the view might reveal an integer, a floating-point value, a character in a collating sequence, or a computational behavior (such as function, procedure, or subroutine).

Likewise, one could take the view that an algorithm in its most abstract state is a complete collection of all the intangible thoughts and ideas that generate its design, whether based on lists of imperatives, nesting functions, states and transitions between them, transfer of tokens between containers in a Petri net, or any equivalent representation of a Turing machine. As such, an algorithm represents these ephemeral thoughts and ideas combined, ultimately resisting definitive and universal quantification and measurement.

To gain deeper insight into the abstractions surrounding a given algorithm, one would do well to also revisit earlier works on the topic. Pondering the original intent of the early visionaries of computing by republishing their work with critiques from today’s leaders would be enlightening and enjoyable. As with many advances in science, their efforts were often met with stark criticism. However, reassessing their intent today could spark further refinement of modern concepts derived from computing’s inherently iterative and optimizing research life cycle.

Jody sharpe, omaha, ne

author’s Response:

A mathematical model tries to capture (abstractly) the essence of the phenomenon being modeled. From this perspective, a person saying, “What is an algorithm?” would not be satisfied with the answer “An algorithm is an integral number.”

moshe Y. Vardi, editor-in-Chief

Give the Past its Due

David Anderson’s Historical Reflections column “The Future of the Past” (May 2012) made a persuasive case for preserving computer hardware and software artifacts. I would add that computer science has not preserved its paper well, either; for example, when The American Federation of Information Processing Societies, the parent of both ACM and IEEE, folded in 1990, its records, periodicals collection, and books went to the dump, as did the records of the Microelectronics and Computer Technology Corporation, or MCC, a major consortium for which I worked in the 1980s. I welcome efforts such as those led by Bruce Damer, whose Digibarn Museum (http://www. digibarn.com/) houses paper materials, as well as working versions of vintage PC hardware and GUI software.

Computer science can do even more to preserve its legacy, encouraging and assisting ethnographers to look into technology development and use. Otherwise, future historians, as well as computer professionals, will be left to infer or guess how preserved artifacts were designed, used, and ultimately abandoned, much as we speculate today about the use of unearthed artifacts of ancient civilizations.

Jonathan Grudin, Redmond, WA

assignment is asymmetric
When discussing a mistake in the C
language, Paul W. Abrahams in his
letter to the editor “Still Paying for a C
Mistake” (Apr. 2012) concerning Poul-
Henning Kamp’s practice article “The
Most Expensive One-Byte Mistake”
(Sept. 2011) apparently fell victim to a
C fallacy when citing the “celebrated C
one-liner”

while (*s++ = *t++);

 

explaining its effect as “copies the string at s to the string at t.” But in C it is the other way round, because *s++ = *t++ is an assignment expression that works from right to left. 1 This means the assignment is a noncommutative operation that in C would be represented by the symmetric symbol =, not by an asymmetric symbol (such as := or ←). With such a symbol this fallacy would disappear like this

 

while (*s++ := *t++); or while (*s++ ← *t++);

 

These one-liners also observe the design rule that “form follows function.” Using this notation, the statement (with the effect mentioned by Abrahams) should instead be

 

while (*s++ =: *t++); or while (*s++ → *t++);

 

Jürgen F.h. Winkler, Feldkirchen-Westerham, Germany

Reference

1. ritchie, d.M. C Reference Manual. bell telephone laboratories, Murray hill, nJ, 1975; http://cm.bell-labs.com/cm/cs/who/dmr/cman.pdf

Concerning the letter to the editor by Paul W. Abrahams (Apr. 2012), saying “C was designed with the PDP- 11 instruction set very much in mind” conflicts with the fact that the C language was based on the B language, which was written for the PDP-7; the PDP- 11 did not yet exist.

Concerning ++ and – modes, C’s creator Dennis M. Ritchie wrote, “ People often guess that they were created to use the auto-increment and auto-decrement address modes provided by the DEC PDP- 11 on which C and Unix first became popular. This is historically impossible, since there was no PDP- 11 when B was developed… Even