Programming Paradigms, Turing Completeness and Computational Thinking (2020)
programming-journal.org
programming-journal.org
You can use C++ to write C-style procedural code, or object-oriented code, or functional code. You could use it to write stack-oriented code in the Forth style. With the help of a library you could even use the logic programming style of Prolog. C++ compilers also tend to support assembly. Of course, the list goes on. You could implement a Turing machine, or a one-instruction-set computer, or Game of Life, or Langton's Ant, and use that as your computational paradigm.
The distinctions between the programming paradigms are often a fuzzy matter of emphasis and idiom, it's not precise and unambiguous.
I hadn't encountered the term hypercomputation before. [0]
> The notion of distinct programming paradigms, as opposed to permeable traditions of programming languages and methodologies, now seems anachronistic in Computer Science curricula, and should be revisited. In particular, the inconsistent uses in the influential ACM/IEEE Curricula should be addressed.
I'm not convinced. It makes good sense to have a course on functional programming, to introduce students to its concepts. The concepts aren't easy, and it makes sense to dedicate a whole course to them. What does it matter that the distinctions between programming paradigms are ultimately imprecise? The same is true for just about everything.
Also, the paper didn't mention the related concept of the Rule of least power: choose the least powerful computer language suitable for a given purpose. [1]
> this notion [of programming paradigms] sits ill with Kuhn’s classic conceptualisation of a scientific paradigm as a dominant world view, which supersedes its predecessors through superior explanatory power.
That much is (almost trivially) true: all of the programming paradigms are within a single scientific paradigm (the current one). (Even Logic Programming, which otherwise could be considered as close to a true superseding paradigm, if it ever actually supersedes the functional/imperative paradigm.)
You have to look to Cybernetics to find mechanisms from beyond the current scientific paradigm.
Cybernetics is about how humans interact with technology, so it doesn't even have a resemblance to control theory (and it's a human science by the way).
What makes your impression is probably that the cybernetics literature has a passion to try solving all its problems with control theory. But control theory here is just a tool, not the science.
Not easily, but I'll try. And thanks for asking.
> It's "just" control theory no?
That's the view from the old paradigm looking "forward". From the new paradigm looking "backward" control theory is the beginning of the new paradigm. To me feedback and control theory looks like a slow and painful rediscovery of Wiener and company.
Cybernetics grew out of the study of "loops of causality". In logic, "A = not A" is a contradiction, in cybernetics it's an oscillator.
It's very difficult to describe the paradigmatic shift. I could point to Shannon and Wiener. Shannon's paper is in many ways the epitome of the scientific paradigm that started with Newton and could be demarcated by Einstein. Already with Quantum Mechanics we're starting to get into the new thing (but the name "mechanics" kind of points to the old way still.) The crux is the change of emphasis from concrete and static to context and relationship, the "verbs" rather than the "nouns".
Consider the cannon vs. the heat-seeking missile. In the first case the science is ballistics, in the second it is feedback and control (with ballistics as a kind of substrate) and the physical properties of the mechanism are secondary to the metaphysical properties (the "causal loops" embodied in the mechanism.) Note that the cannon also has its feedback loops. After you fire you measure the result and adjust the aim and so on. The paradigms aren't separate, they all co-exist, it's a change of attention and emphasis. And speed, of course.
It almost doesn't matter what the missile is made of, electric circuits, clockwork, fluidics, etc. The crucial aspects of it that define its behaviour are intangible not physical. That's why Cybernetics can be applied to living systems just as well as machines.
(FWIW, I never went in much for the "Second-order" cybernetics, it got too metaphysical for my taste.)
Anyhow, I hope that makes more (rather than less) sense. :)
In re: Cybernetics in general I always recommend "Introduction to Cybernetics" by W. Ross Ashby. It's a whole book but I find it to be the most direct and concrete exposition of Cybernetics.
http://pespmc1.vub.ac.be/ASHBBOOK.html http://pespmc1.vub.ac.be/books/IntroCyb.pdf
In re: paradigm shift, I don't really know of a single good source for that, but the works of Gregory Bateson, specifically "Steps to an Ecology of Mind" and "Mind and Nature: A Necessary Unity", were useful to me.
https://en.wikipedia.org/wiki/Gregory_Bateson
(Also see my earlier comment here: https://news.ycombinator.com/item?id=26248362)
I think this is spot-on. We have relatively fixed mental models for what computing should look like which are really just based on a few accidents of history. Bret Victor's famous "The Future of Programming" talk is a great reminder that our ambitions for what computing could be were once much broader than they are today.
Can someone elaborate? How do we have unbounded computations and unbounded values?
For this reason, ordinary Turing-complete programming languages allow (at least in principle, i.e. assuming infinite RAM) valid, provably terminating programs with arbitrarily high, unbounded complexity, unlike other formalisms such as regular expressions, which do not allow the same level of generality.
So in a more practical sense, for example in application programming, unbounded computations/values could be compared to users continually adding/retrieving data against application database - as long as the server is up, the process never stops?
Imagine a function written in any Turing-complete programming language, Java, for example. Let's say that you can see the API but not the implementation. Can you bound the space or time that the function call will take?
The answer is no, because there exist correctly written and terminating Java functions with arbitrarily high running time. You can write functions with running time O(n^100), O(2^n), O(n!), O(((n!)!)!)... there is no limit. The crucial observation is that this property is necessary for a language to be as powerful as Java, because there exist problems that require such a high running time and that couldn't be solved if the Java compiler enforced a hard limit on the running time or memory. (System resources such as physical RAM are obviously limited, we are thinking of an hypotetical computer with infinite RAM).
The same isn't true for computational models that aren't Turing complete. For example, regular expression searches are guaranteed to terminate in a certain amount of time and using a certain amount of space (what exactly is this limit depends on the algorithm you're using to implement regexes, but there definitely is one).
The 'tradeoff' at play here is that by using a less powerful tool, i.e. regexes instead of a Java program, you are gaining guarantees about the maximum running time and memory usage, but you are losing the ability to solve certain types of problems.
A common example that can be solved by a Java program but not by any regular expression is determining whether a string of parentheses is correctly matched.
The idea, of course, is not that either tool is 'better' or 'worse', but simply that Turing-complete programming languages can solve problems that non-Turing-complete languages can't, at the expense of being 'more dangerous', because you can't a-priori guarantee how much time they'll take to terminate (if at all!) or how much memory they'll require.
"Paradigm" is something science historians talk about.
We can talk about objects, functions, data structures, abstractions, interfaces, complex compositions, etc. without mentioning paradigms. We can plan software that follows rules without involving a paradigm. We can teach a course just on functional programming and still not talk about it as a paradigm.
With all the words we have to describe the parts of programming, "paradigm" seems as generic and vague as "concept" or "thing". But "paradigm" does have a specific meaning, and it's not relevant in practice.
> The notion of distinct programming paradigms, as opposed to permeable traditions of programming languages and methodologies, now seems anachronistic in Computer Science curricula, and should be revisited. In particular, the inconsistent uses in the influential ACM/IEEE Curricula should be addressed.
When institutions knowingly teaching people bad theory because they don't have better frames I think that means that our research has missed some good opportunities for exploration. The academy is setting people up to answer the questions "how do we improve the task of programming?" rather than exploring the more fundamental question of "what could/should programming be?".
A genuinely new programming paradigm would not be the same as just a new methodology - it would have to be accompanies by a new theory of programming itself (not just computation). I think the breakthrough comes from modeling programming not around conceptual frameworks of computation but instead around our own human process of cognition. If we create languages which provide the optimal expressiveness of the problem/solution from the point of view of the human writing the program - this could transform what programming itself means. This is where I think the majority of impactful innovation will come from in the next couple of decades.
How would this be different from, e.g. the development of modern high-level programming languages? To a certain extent, structured programming exists because we find it cognitively easier to express our programs in terms of if/then/else statements or loops as opposed to conditional jumps.
I don't think the "algorithmic" type of thinking is really escapable if you want to end up with code that actually executes.
Higher-level languages really should mean languages that operate on another level of abstraction - programs that themselves are interpreted by other programs. Raising the level of abstraction requires also hiding details that aren't important at a higher level so, arguably, modern high-level languages are rarely all that much higher-level than C (even if they are safer/easier/faster).
Knowing a Turing complete language will probably always be a valued skill but it might one day become similar to knowing Assembly today - it's important to know if you care a lot about implementation details but it's not the language you use to reason about the overall program. Libraries, frameworks and system components all need to be able to express a level of detail which makes algorithmic thinking ideal but it's not necessarily the best model for specifying the behavior of information systems or making devices end-user programmable. There's a whole world of relatively unexplored possibilities here for language designers to explore.
(NOTE: I'm using a backup account to work around my anti-procrastination settings but I'm the author of the original comment)
A lot of what we do today is not algorithmic in nature. Arguably the majority. For example, take your phone and tell me how many apps follow a computational/algorithmic paradigm, that is, you give them some parameters, they compute an answer and then terminate. But we have to express all of this algorithmically, and the mismatch is a source of a lot of the pain we have in software development today, IMHO.
I am not sure that Turing completeness is really the main driver here, but it is at least a symptom.
As Guy Steele put it:
Another weakness of procedural and functional programming is that their viewpoint assumes a process by which "inputs" are transformed into "outputs"; there is equal concern for correctness and for termination (and proofs thereof). But as we have connected millions of computers to form the Internet and the World Wide Web, as we have caused large independent sets of state to interact–I am speaking of databases, automated sensors, mobile devices, and (most of all) people–in this highly interactive, distributed setting, the procedural and functional models have failed, another reason why objects have become the dominant model. Ongoing behavior, not completion, is now of primary interest. Indeed, object-oriented programming had its origins in efforts to simulate the ongoing behavior of interacting real-world entities–thus the programming language SIMULA was born.
https://dreamsongs.com/ObjectsHaveNotFailedNarr.html
But of course objects are also highly procedural, at least as we have conceived and implemented them today:
Instead, objects use procedural abstraction to hide behavior. This difference has significant consequences for use of the two forms of data abstraction. Object interfaces are essentially higher-order types, in the same sense that passing functions as values is higher-order. Any time an object is passed as a value, or returned as a value, the object-oriented program is passing functions as values and returning functions as values. The fact that the functions are collected into records and called methods is irrelevant. As a result, the typical object-oriented program makes far more use of higher-order values than many functional programs.
William Cook, On understanding data abstraction, revisited
More here: https://2020.programming-conference.org/details/salon-2020-p...
My current attempt at overcoming: http://objective.st
What about the differences? How are students supposed to learn if not for making contrasts between patterns and explore each one separately to get an idea of what makes them tick?