Communications of the ACM
The Imperativity of Algorithms
An issue crossing both philosophy and computing is the ontology of algorithms, and my claim that their proper characterization is imperative crosses into linguistics as well. As the philosophy of computing develops into a respectable field, or so we adherents claims, more attention is directed toward algorithms. The word "algorithm" carries unfortunate ambiguity. I want to focus on the algorithm as a robust sequence of control structures (the real meaning of algorithm, or the i-algorithm, as I refer to it [Hill2021])—big enough to have a name. I'm talking about Binary Search, A*, the Simplex Algorithm, Run-Length Compression, and so forth. These comprise a class of things that is significant but not sharply defined, the constituents of which are well-known but not sharply distinguished, and to which we refer in perfect confidence is discussion with each other. What I have in mind are the kind of things on this list [Koutchan], tools of our trade.
Readers may benefit from thinking of "Binary Search" or "Heap Sort" (or their own favorites) when a general algorithm is mentioned here. The scope of this discussion is those big fat algorithms, the subjects, by name, of academic and professional discourse. To repeat, we refer to them in perfect confidence. They can be programmed in any Turing-complete language. They are instantiated and deployed routinely. So these algorithms exist, and they enjoy an existence independent of any written version. Therefore we can interrogate their ontology.
An algorithm, construed in this sense, must have characteristics. An earlier work [Hill2016] delves into those characteristics of the algorithm as an abstract procedure, but only one of those characteristics is considered here, that the abstraction is imperative. The reasoning is developed along two paths: (1) Declaratives objects don't do anything, and (2) We talk that way; we explain an algorithm by telling what to do.
The most contentious—to me, the most daring—implication is that the algorithm is not a Turing Machine. A Turing Machine is a static object, a declarative, a quintuple or septuple of the necessary components. The object δ that consititutes the transistion function that describes the action is itself a set of tuples. All of this is written in appropriate symbols, and just sits there. A Turing Machine may implement one of the algorithms examined here. But the TM itself does not do anything.
Defense of that claim can be found in the paper cited. But what's up with this—analyzing computability via moods and modes of language? I appeal to the imperative as the most ready and useful representation of the idea of command and control, which seems essential to algorithm-hood. As Strachey says, it is the inclusion of commands, in addition to expressions, that makes programming different from mathematics [Strachey, Sec 3.1]. Hamblin refers to commanding, requesting, or instructing in his account of the imperative mood in English: "[T]he most natural way of telling someone how to do something is in the imperative mood: Do it such-and-such a way." That's certainly how we teach Binary Search or Heap Sort. But the imperative is a parameter of sentences, not smoothly transferred to computational objects.
Linguistics has shed light on many questions of cognition, but does the linguistic turn in philosophy justify wholesale application of language concepts to other realms? In English, the imperative is present tense, second person, an expression of a state not known to be fact, but to be brought about by the recipient of the utterance, which suits the directive thrust of an algorithm. But even on its own academic home turf, linguistics, the imperative is suspect. Hamblin notes that validation of the scientific soundness of the imperative is deemed sketchy and ill formed [Hamblin]. We hesitate to apply a label that undermines the reputation of the algorithm.
Of course, no one ever said (to my knowledge) that an algorithm was declarative (or indicative), so the discomfort expressed here is not with the attribution of imperativity as such, but the attenuated chain of reasoning that leads from grammar to mood to directive to algorithm and bypasses Turing Machine. Somebody should think more about that.
What about embracing the grammatical analogy? Work on formalizing the imperative and nearby constructs can also be found in Sosa [Sosa], Goddard [Goddard], Žarnić [Žarnić] and others. Consider attempts to develop a logic of the imperative sentence, which would interpret "Grin and bear it!" in such a way that "Grin!" gets the same alethic semantics, and that "Don't grin!" gets some opposing semantics. The control structures that make up algorithms also include conjunction and negation. But is that a weak prop or a strong support?
This author has already revealed her willingness to press quotes into service if they make her point, so.... here is Kant: "All sciences have a practical part, consisting of problems expressing that some end is possible for us, and of imperatives directing how it may be attained." Sounds right! If, given the expression of some end that is possible, an algorithm is not exactly a direction on how it may be attained, then what could it be?
References
[Goddard] Goddard, Ian Williams. 2008. A logic and semantics for imperatives. In Noesis, the journal of the Mega Society, issue 187.
[Hamblin] Hamblin, C.L. 1987. Imperatives. Basil Blackwell.
[Kant] Kant, Immanuel. Fundamental Principles of the Metaphysic of Ethics, 5th Edition. Translated by Thomas Kingsmill Abbott. Note says [Extracted from "Kant's Critique of Practical Reason, and other Works on the Theory of Ethics"]. Pg 38[40] In Section 3. Hypothetical and Categorical Imperatives. Longmans, Green, and Co. 1916
[Koutchan] Koutschan, Christoph. The Most Important Algorithms. http://www.koutschan.de/misc/algorithms.php. Accessed 31 March 2023.
[Hill2016] Hill, R. What An Algorithm Is. Philosophy & Technology, March 2016, 29:1, 35-59, DOI:10.1007/s13347-014-0184-5.
[Hill2021] Hill, R. Misnomer and Malgorithm. Blog@CACM, March 27, 2021.
[Sosa] Sosa, Ernest. 1967. The Semantics of Imperatives. American Philosophical Quarterly. Oxford. 4 (1), p. 57.
[Strachey] Strachey, Christopher. 1967. Lecture notes printed in: Fundamental Concepts in Programming Languages. Higher-Order and Symbolic Computation. 2000. 01:13, 11--49.
Žarnić, Berislav. 2003. Imperative Negation and Dynamic Semantics. In Meaning: The Dynamic Turn, ed. Jaroslav Peregrin
Robin K. Hill is a lecturer in the Department of Computer Science and an affiliate of both the Department of Philosophy and Religious Studies and the Wyoming Institute for Humanities Research at the University of Wyoming. She has been a member of ACM since 1978.
No entries found