This is a question I've thought about a lot this year. How many programming paradigms are there? How will we know if/when we've discovered them all? Is there a way to arrange them so that gaps in the table predict yet-to-be-discovered paradigms in the same way the periodic table predicted elements or the square of R/C/?/L predicted memristors?
After reading some of Greg Egan's hard science fiction that explores the consequences of a universe where time is a spacelike dimension or another where there are two timelike dimensions, I wondered if programming paradigms could be categorized according to what kind of world lines data or variables may have.
For instance, in some mathematical spacetimes, the future looping back on the past is not a construct you can create. In others (such as Egan's Orthogonal universe), it is quite possible for world lines to arbitrarily loop back on the past. This could be analogous to in a programming paradigm whether statements not yet reached can affect the statement you're looking at. For instance, whether a logic program supports constraint satisfaction.
Mutability and immutability could be analogous to various ways of resolving the Grandfather Paradox. If the result is the timeline is changed/overwritten, that is analogous to a mutable programming paradigm. If the result is that you either are prevented from doing it or doing it results in spawning a duplicate timeline where history is changed, then that is analogous to an immutable or functional paradigm.
Finally, it should be noted that the program and it's entire execution state-space could be regarded as a "four dimensional object" the same way you could consider the universe + its history as a four dimensional mathematical object. (Not really "4" because the space of the program isn't necessarily 3 dimensional, but using the term as a metaphor.) In this sense, you could see the actual execution i.e. the implementation of the execution of the program as a vector or walk through this time-state-space that does not necessarily have to follow the (human) conceptual vector of time through the program! (Not to mention the lexical order of the program text.) For instance, a SQL engine might build a query plan that approaches the execution of a SQL "program's" time-state-space in a much different direction and order than what a human would call the "time vector" through the program.
In Egan's Orthogonal universe he deals with the question of how can living beings experience local time when a universe has all 4 dimensions as spacelike by making a distinction between the arrow of time defined by entropy versus "timelike" dimensions. In our universe the entropy arrow of time usually aligns with the timelike dimension, but in the Orthogonal universe the entropy arrow of time could point along any dimension, but which dimension is the "time" dimension is set by the combined entropy of the local surroundings. Similarly, in a programming paradigm you can choose to define the "time dimension" in many different ways, but there is also an entropy arrow of time.
As an example, imagine a simple imperative programming language that conceptually executes from top to bottom. You could, in principle, make a bizarre implementation that executes backwards, starting with the last instruction and all possible result states, and searches for precondition states that could have caused that result. Repeat for the second to last statement for all of the candidate results, and so forth, until we reach the most initial state.
It's clear that this is possible to implement if the language is restricted enough (for instance if it has few states, or if the only allowed operations are of a certain type). It's also clear that the big-O time/space complexity of this implementation strategy is astronomical for most complex programs. But it is instructive to look at why this is: it is because this time-reversed execution implementation strategy is going backwards against the entropy arrow of time! This is reflected in the enormous amount of energy it would require to compute (drawing on the entropy of an outside system's energy source to reverse local entropy), and/or the gargantuan amount storage it would require (increasing the entropy in space of an outside system in order to reverse local entropy).
Yet at the same time, no one would bat an eye at certain classes of "programs" "running backwards", such as a linear equation solver, or a layout engine, or a logic constraint solver, etc. (One wonders whether a nominally imperative assembly language for a machine based on reversible computing would also fall into this category.)
What I'm getting at is that there are myriad "potentially timelike" dimensions in programs: lexical order, call stack, real execution time, the programmer's conception of how time flows in the conceptual program, etc. And there's also an entropy arrow of time related to how hard/easy it is to reorder the operations. Finally, I view the execution implementation as sweeping a hyperplane (or hypermanifold) through the four dimensional time-state-space of the program & the result of its execution. Depending on the ways that the time-state-space of the program are connected (or connectible) determines along which direction(s) that sweep may or must proceed.
Programming paradigms may be understandable as rules governing how this time-state-space may be connected up, which in turn affects what the entropy arrow of time looks like in execution-implementation-space.
After reading some of Greg Egan's hard science fiction that explores the consequences of a universe where time is a spacelike dimension or another where there are two timelike dimensions, I wondered if programming paradigms could be categorized according to what kind of world lines data or variables may have.
For instance, in some mathematical spacetimes, the future looping back on the past is not a construct you can create. In others (such as Egan's Orthogonal universe), it is quite possible for world lines to arbitrarily loop back on the past. This could be analogous to in a programming paradigm whether statements not yet reached can affect the statement you're looking at. For instance, whether a logic program supports constraint satisfaction.
Mutability and immutability could be analogous to various ways of resolving the Grandfather Paradox. If the result is the timeline is changed/overwritten, that is analogous to a mutable programming paradigm. If the result is that you either are prevented from doing it or doing it results in spawning a duplicate timeline where history is changed, then that is analogous to an immutable or functional paradigm.
Finally, it should be noted that the program and it's entire execution state-space could be regarded as a "four dimensional object" the same way you could consider the universe + its history as a four dimensional mathematical object. (Not really "4" because the space of the program isn't necessarily 3 dimensional, but using the term as a metaphor.) In this sense, you could see the actual execution i.e. the implementation of the execution of the program as a vector or walk through this time-state-space that does not necessarily have to follow the (human) conceptual vector of time through the program! (Not to mention the lexical order of the program text.) For instance, a SQL engine might build a query plan that approaches the execution of a SQL "program's" time-state-space in a much different direction and order than what a human would call the "time vector" through the program.
In Egan's Orthogonal universe he deals with the question of how can living beings experience local time when a universe has all 4 dimensions as spacelike by making a distinction between the arrow of time defined by entropy versus "timelike" dimensions. In our universe the entropy arrow of time usually aligns with the timelike dimension, but in the Orthogonal universe the entropy arrow of time could point along any dimension, but which dimension is the "time" dimension is set by the combined entropy of the local surroundings. Similarly, in a programming paradigm you can choose to define the "time dimension" in many different ways, but there is also an entropy arrow of time.
As an example, imagine a simple imperative programming language that conceptually executes from top to bottom. You could, in principle, make a bizarre implementation that executes backwards, starting with the last instruction and all possible result states, and searches for precondition states that could have caused that result. Repeat for the second to last statement for all of the candidate results, and so forth, until we reach the most initial state.
It's clear that this is possible to implement if the language is restricted enough (for instance if it has few states, or if the only allowed operations are of a certain type). It's also clear that the big-O time/space complexity of this implementation strategy is astronomical for most complex programs. But it is instructive to look at why this is: it is because this time-reversed execution implementation strategy is going backwards against the entropy arrow of time! This is reflected in the enormous amount of energy it would require to compute (drawing on the entropy of an outside system's energy source to reverse local entropy), and/or the gargantuan amount storage it would require (increasing the entropy in space of an outside system in order to reverse local entropy).
Yet at the same time, no one would bat an eye at certain classes of "programs" "running backwards", such as a linear equation solver, or a layout engine, or a logic constraint solver, etc. (One wonders whether a nominally imperative assembly language for a machine based on reversible computing would also fall into this category.)
What I'm getting at is that there are myriad "potentially timelike" dimensions in programs: lexical order, call stack, real execution time, the programmer's conception of how time flows in the conceptual program, etc. And there's also an entropy arrow of time related to how hard/easy it is to reorder the operations. Finally, I view the execution implementation as sweeping a hyperplane (or hypermanifold) through the four dimensional time-state-space of the program & the result of its execution. Depending on the ways that the time-state-space of the program are connected (or connectible) determines along which direction(s) that sweep may or must proceed.
Programming paradigms may be understandable as rules governing how this time-state-space may be connected up, which in turn affects what the entropy arrow of time looks like in execution-implementation-space.