Paper Review: The Paradigms of Programming
Title and Author of Paper
Robert W. Floyd. 1979. The Paradigms of Programming. Communications of ACM 22, 8 (1979), 455-460.
Summary
These are interesting times! We are in the middle of programming language boom. There are a lot of programming languages out there, each language with its own history, background, language syntax, semantics and pragmatics. Many of these languages support various paradigms (declarative, imperative, functional, object oriented, etc), as well as many programming concepts (state and name state, records and indexed data structures, lexically scoped closures, laziness/lazy evaluation, recursion and tail optimization, garbage collection, etc).
One approach to studying computer programming is to study programming languages. But there are a tremendously large number of programming languages, so large that it is impractical to study them all! How can we tackle this immensity? We could pick a small number of languages that are representative of different programming paradigms. But this gives little insight into programming as a unified discipline. There is a dire need for a clear path on how to reason about programming as a unified field without being burdened by the myriad of programming languages.
This paper by Robert W. Floyd gives a perspective on reasoning about programming through programming paradigms. The content of this paper is divided into four interesting parts, each with sufficient example to broaden the concepts discussed:
- Paradigms of Programming.
- Effects of paradigms of programs on our success as designers of programs.
- How paradigms of programs should be taught.
- How paradigms should be embodied in our programming languages.
Each of these points are clearly discussed in the sections that follow. Key points made by Robert Floyd are highlighted for emphasis.
Paradigms of Programming
According to Robert Floyd, Paradigms of programming are general rules for attacking similar problems that would lead a program designer to approach the given problem in the most efficient way the first time.
Robert gives an example using Structured programming paradigm though not popular, has its application to some problems such as allowing the construction of programs that are too complicated to be designed efficiently and reliably without methodological support, thereby extending ones power of design. Structured programming consist of two phases which makes this possible: In the first phase which consist of top-down design or step-wise refinement, the problem is decomposed into a very small number of simpler subproblems. This gradual decomposition is continued until the subproblems that arise are simple enough to cope with directly. The second phase entails working upwards from the concrete objects and functions of the underlying machine to the more abstract objects and functions used throughout the modules produced by the top-down design. Other paradigms often referred to as specialized high-level paradigms such as branch-and-bound, divide-and-conquer are equally essential and perhaps more popular.
Robert Floyd uses a material by the philosopher of science Thomas Khun titled “The Structure of Scientific Revolutions” to emphasize that:
Computer programming content is not only about the knowledge of algorithms and language definitions described in the pages of a textbook.
The study of paradigms that are far more specialized than the popular ones, rather than what is being purported by certain communities, is what mainly prepares the student for membership in the particular scientific community with which he will later practice.
Effect of paradigms on our success as designers of programs
Discussing the effects of programming paradigms on the success of designers of programs; Robert Floyd gave two cases in point:
Case 1
Robert Floyd uses the problem of parsing of context-free language which is of pressing importance to compiler development and natural linguistics.
To illustrate this effect, Floyd examines the solution of John Cocke to this problem. In his solution, Cocke applied dynamic programming paradigm to this problem. Dynamic programming paradigm solves a problem for a given input by first iteratively solving it for smaller inputs. Cocke’s algorithm successively found all parsings of all substrings of the input, however, his algorithm could only run in polynomial time and the solution was sometimes incorrect. Robert Floyd attacked this problem by inventing the paradigm of finding a hierarchical organization of processor that could solve the problem, and then simulating the behavior of this organization. Simulation of such a multiple recursive processes led Robert Floyd to the use of recursive coroutines as a control structure.
Conclusion: from these two approaches, Floyd concluded that John Cocke’s experience and his illustrate the likelihood that continued advance in programming will require the continuing invention, elaboration, and communication of new paradigms.
Case 2
Another example of the effective elaboration of a paradigm is the work of Shortliffe and Davis on the MYCIN program.
MYCIN is a rule-based system, based on a large set of independent rules, each with a testable condition of applicability and resulting simple action when the condition is satisfied. MYCIN was built on the Rule-based paradigm, but Davis elaborates this paradigm by tracing responsibility backwards from an undesired result through the rules and conditions that permitted it, until an unsatisfactory rule yielding the invalid results from the valid hypothesis is reached. By this means, it has become technically feasible for a medical expert who is not a programmer to improve MYCIN’s diagnostic capabilities. Davis called this program TEIRESIAS. The use of rule-based paradigm, with the subsequent elaboration for self-modification, makes the interactive improvement of the MYCIN program possible.
Conclusion: Floyd concluded that: “ if the advancement of the general art of programming requires the continuing invention and elaboration of paradigms, advancement of the art of the individual programmer requires that he expands his reparatory of paradigms. Furthermore, the acquisition of new paradigms by the individual programmer may be encouraged by reading other people’s programs.”
Floyd also shared his experience and technique for expanding his own capabilities when designing difficult algorithms:
“After solving a challenging problem, I solve it again from scratch, retracing only the insight of the earlier solution. I repeat this until the solution is as clear and direct as I can hope for. Then I look for a general rule for attacking similar problems that would have led me to approach the given problem in the most efficient way the first time.”
How Programming Paradigms should be embodied in new programming languages
Floyd begins to illustrate the importance of how paradigms should be embodied in new programming languages by stating that:
Programming languages should be classified by the extent to which they permit and encourage the use of effective programming paradigms. When a language makes a paradigm convenient, we say the language supports the paradigm. When a language makes a paradigm feasible but not convenient, we say the language weakly supports the paradigm.
Floyd believes that the continual advancement of programming as a craft requires the development and dissemination of languages which supports the major paradigms of their user’s communities. The design of a language should be preceded by the enumeration of their user’s paradigms, including a study of the deficiencies in programming caused by discouragement of unsupported paradigms. If there is ever a science of programming language design, it will probably consist of largely matching languages to the design methods they support. The environment in which we program should also be analyzed as supporting or failing to support the methods of design or programs, such environments includes file systems, editors, diagnostic systems, etc.
How Paradigms of Programs should be taught
Most of the classical algorithms found in texts on computer programming can be viewed as instances of broader paradigms. For example, Merge sort algorithm is an instance of divide-and-conquer paradigm. For every such classical algorithm, one can ask “How could I have invented this,” and recover what should be an equally classic paradigm.
Floyd advises that the teachers of programming identify the paradigms they use, as fully as they can, and teach them explicitly. Paradigms outlive programming languages.
To sum up, my message to the serious programmer is: spend a part of your working day examining and refining your own methods despite future or past dead-lines. Methodological abstraction is a wise long term investment.
Floyds paper is a source of calm in this era of programming language boom where programming language wars are very common amongst programmers.
I hope you find some time to dig deep into this paper and extract some ideas that my review might have unknowingly omitted and share with the community at large.
Contributions are welcome and comments are appreciated.
Thanks to the NP-CORE community for the opportunity to publish this paper review.
