4 ms·
> there may really be a finite set of [control structures] Kleene Algebras (which compose via sequencing, choice, and repetition) map so well to sequential pro
by 082349872349872 4y ago
> there may really be a finite set of [control structures]
Kleene Algebras (which compose via sequencing, choice, and repetition) map so well to sequential programming that I currently believe, yeah, we have them[0]:
- cf ';', case, and while
- Hoare triples map nicely into a Kleene Algebra. I suspect the rise of structured programming tanked adoption of formal methods, because informal methods sufficed, where they may not have had we continued with spaghetti coding.
- matrices/graphs of Kleene Algebras also form a Kleene Algebra, so the state machine[2] a "structured program" compiles down to is still expressed in the same paradigm.
- Kleene himself was originally modelling neural networks, not sequential programs, and he still arrived at the same theory.
So if we're looking for new control structures, they're probably to be found in non-sequential programming.
- unix '|' is a nice example: 'f | g' is not strictly parallel, because f can only run a finite amount ahead of g, which I'm guessing was a deliberate design decision.
- and sometimes not even there? NESL had novel control, but it implicitly followed the data structure[1].
[0] modulo Duff's Device, but so far even that seems to be unique, and not a whole family of too-narrowly-useful control structures.
[1] the 1962 formulation of APL already has a number of primitives suitable for parallel jobs. I have wondered if people in the Unit Record Equipment days often sped up computations by breaking decks into pieces, running them through a gang of machines, and recombining the output decks. However, the oldest APL person I've had contact with was still too young to remember those times, so it remains a hypothesis.
Edit: [2] upon reflection, this would explain why we have these three classical control structures: anything that doesn't really fit into them gets coded as a state machine, which does. Eg. https://arxiv.org/pdf/1109.5416.pdf https://arxiv.org/pdf/1109.5416.pdf is a recent rediscovery of a program derivation technique I've seen used elsewhere by at least Hehner and (IIRC) Pratt.
One possibility for going beyond: if we think geometrically, sequencing corresponds to snapping two paths together at a common endpoint to form a new path, choice to splitting the path into multiple paths (leaving a hole instead of a face between them, where 'if' often explicitly marks the beginning of a split, but any join, unless one is using ϕ functions, remains implicit — cf "comefrom"), and repetition to joining into an ancestor, forming (per Euler) a new face. So 0-d points are sets of states (iow: predicates), 1-d paths are maps, and 2-d faces are loops.
What would a 3-d volume be, if anything?
- samatman 4y agoThis is a great comment, added to my favorites. Kleene choice doesn't map to normal imperative conditions, as you gesture at, but what does is Brian Ford's ordered choice alt combinator, '/'. When you use Kleene choice, you're in the realm of definite clauses, where control flow is deliberately underspecified.
- User23 4y agoOne sees this with Dijkstra’s guarded commands (which are heavily influenced by Hoare) as well. The conditional and loop both pick some true guard nondeterministically. It’s nice on account of it keeps the theory cleaner and of course trying the cases deterministically in program order in the implementation is fully compatible with the formal nondeterministic semantics.
- 082349872349872 4y agoI used to feel it was tragic that even languages which start with unordered choice tend to migrate to ordered choice under practitioner pressure (and I'm unaware of any language which has gone in the opposite direction). However, now I've made my peace with "working up to isomorphism", and regard ordered choice just as the popular way to specify a state space partition that may also be expressed with (more dignity[0] via) unordered choice. "How I learned to stop worrying and love IF THEN" [0] and perhaps even —if we take a moment to remember EWD— without prematurely making decisions that need not be taken... Edit: wow! we apparently owe the fatbar, ⌷, to some bikeshedding from Knuth... cf p.11 of https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD398.PDF https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD398.PDF
- haskellandchill 4y agoI feel like we have all the tools on the theory side and we just have to put them to use in real systems. I'm trying to make a system for portable computation that can be used to bootstrap a bare machines and would also be useful to offline computations using pen and paper across multiple people.