It occurred to me while reading this how deeply weird it is that we have entrenched a single data structure as the abstract model on which we build control flow. Church has a lot to answer for.
What’s bad about that? I think we have a great desire to keep things simple, so if we can reduce something down to a single data structure, why wouldn’t we want to do that?
Hmmm, that’s an interesting observation. It seems to me that CPS and models involving concurrency are both more capable extensions, but is there any truly orthogonal alternative?
I think it’s less “we entrenched it” and more that there’s no other data structure that fits the requirements for the kinds of control flow we want to model.
First thought: Yes there is, it’s called a tree. Or sometimes a graph, but usually a function call chain ends up being a tree.
Second thought: Yeah but implementing trees at a low level is complicated. Stacks are nice and dense and seldom need memory management besides “push” and “pop”. So, stacks are an optimization.
Third thought: …and how do you do a depth-first traversal of a tree? With a stack.
…you know, I think we might be onto a Deep Truth here.
Ding ding ding! I spent the better part of 2018 in an existential crisis over that. ;)
It’s also no coincidence that a dual-stack automaton or a queue automaton are equivalent to Turing Machines. It all falls out in some beautiful, scary ways.
Some languages replace the notion of a stack with a list of activation records. This makes forking structures quite easy but the compiler generally tries to represent it as a stack in the common case. Some Lisp machines with hardware-assisted GC did this more natively, but you need some integration between control flow and memory allocation, and a single register containing an address is the simplest. There’s no conceptual reason that it needs to be a single stack. There have been multi-stack stack machines, for example, though they aren’t a good fit for Algol-style languages.
Coroutines, asynchronous message sending, and so on are all interesting control-flow models, but the prevalence of the stack (and, especially, the hardware support) means that they’re second class.
I find this particularly interesting in light of a paper I read around 15 years ago that looked at organisational models and found that only around 10-20z of the population naturally thought in terms of hierarchies for organisation. This is a big part of the reason that iTunes was so popular: it gave you tags and filtering instead of folders. Gmail learned the same lesson and was hugely popular. The paper didn’t notice a couple of things:
Their proportion of the population that thinks in terms of hierarchy is roughly the same as other studies reported for the proportion that finds it easy to learn to program.
The people who complain most about the non-hierarchical systems tend to be programmers (when iTunes came out, for example, Slashdot was full of people saying that. Their music was already organised in folders and iTunes was stupid to not show this hierarchy).
My conjecture is that we have, for the last 60 years, built programming languages around a mode of thought that is not natural for around 85% of the population. It’s not that they find programming hard, it’s that they find programming in languages where control flow is expressed in lexical hierarchies difficult. Unfortunately, there aren’t enough languages that don’t do be able to make a good comparison (though, from my memory of the ‘80s, more people found BASIC easy before the introduction of GOSUB). I keep trying to persuade people doing programming usability to test this hypothesis.
Coroutines, asynchronous message sending, and so on are all interesting control-flow models, but the prevalence of the stack (and, especially, the hardware support) means that they’re second class.
Yeah, coroutines with forking stacks or their own contexts is the first thing I thought of too…
I find this particularly interesting in light of a paper I read around 15 years ago that looked at organisational models and found that only around 10-20z of the population naturally thought in terms of hierarchies for organisation.
…and I have a real hard time thinking about how to use coroutines effectively because they’re not hierarchical. XD This is a real interesting insight! I haven’t had coffee yet and so am somewhat tempted to dismiss part of it by saying “80-90% of humanity also sucks at everything”, but while that’s true it also may or may not be correlated. :P Let me try harder:
To look at other fields of human endeavor… hierarchies get used a lot for organizing large, complex systems. Companies, electronic components, city design, political systems… all are usually built with hierarchies. But on the flip side, there’s lots of things that aren’t: Houses are usually built using a fairly flat hierarchy: you have one node at the top that consists of the architect, general contractor, and other organizers/planners, and then you have a handful of specialist teams beneath them that do framing, electrical, plumbing, etc. I’ve been watching a lot of woodworking videos on youtube lately and those are generally fairly complex and intricate human artifacts built with a huge amount of skill, that are also mostly non-hierarchical. Unless it needs to be moved and gets too big to be moved, the cabinet or tree house or bowl or whatever is usually made as a single tightly-integrated piece. And so on.
So what’s the difference? The one I can see is that hierarchical systems are also big and involve many, many people, while the non-hierarchical ones are smaller. You can have small hierarchical systems and big non-hierarchical systems but they tend to be less common. So hierarchies are a pretty good way of communicating and dividing work among many people.
…this means that the CPU’s stack pointer is an incarnation of Conway’s Law. :O
So if we assume this is correct, are we indeed Doing Something Wrong? If hierarchies are an okay way to organize a lot of monkeys, and most software is made by large groups of monkeys, then organizing our software around hierarchies makes a lot of sense. BUT, there’s plenty of perfectly cromulent software out there that has been made, or is yet to be made, by small numbers of monkeys that don’t need that kind of organization. And there may be good ways of organizing monkeys out there besides hierarchies: Morning Star Company is one quite interesting case study.
So with this in mind I wouldn’t necessarily say that a hierarchical organization of programs is bad, but it would certainly seem to be leaving a lot on the table in terms of optimizing for a specific, fairly narrow use-case: large companies/projects with lots of people working together. Since a lot of modern computing grew out of exactly those kinds of systems (government, large companies, military) this makes perfect sense, but it also suggests we can do better. So… it’s a very interesting hypothesis and I would love to learn more!
including the relationship of the “Stackless” Python fork (green threads that don’t use the C stack) to Lua coroutines, etc.
I read this a long time ago, and don’t remember all the possibilities … it would be nice if someone dug up this knowledge, especially now that async/await seems (weirdly?) popular / dominant
I like async/await, it just seems more understandable than other kinds of async to me (note that I am mostly familiar with JS async), since it’s basically sugar over promises which are sugar over callbacks which are as simple as it gets.
Coroutines are really cool compared to async/await because they don’t suffer from the function coloring problem. In fact an asynchronous runtime can be built on top of coroutines entirely.
At a language level you can kind of imagine coroutines as having any and all functions implicitly marked with async, as well as any and all function calls implicitly awaited, so any function may await for a result at will and so the coloring disappears completely. Though the runtime implements it more efficiently than a classic async/await system would be implemented (ie. sugar for callbacks/promises) - basically a coroutine is like a separate VM that can be suspended and resumed on demand.
So to implement an async runtime you’d have a main loop which waits for events to come in, and resumes awaiting coroutines in response to those events. Then when writing an async task, you just write linear code as if you were using blocking operations, but at the points where the thread would otherwise block and wait for a result, the coroutine’s execution pauses (it yields) and control is passed back to the main loop, which can then resume another coroutine and let it run, and so on and so forth. And it all doesn’t result in any annotation creep :)
I think function coloring is valuable, mostly as a “will this function potentially take a significant amount of time” indicator. I guess coroutines are better when you have threads and async/await is better when you don’t. Also, how do you call multiple functions in parallel with coroutines?
I think function coloring is valuable, mostly as a “will this function potentially take a significant amount of time” indicator.
I think you’re right about the explicitness aspect here, it can impact your understanding of the code. On the other hand an analogous explicitness argument can be made about eg. automatic closure captures - they can make the lifetime of your objects unpredictable, yet we all use them because the convenience factor greatly outweighs this disadvantage.
I guess coroutines are better when you have threads and async/await is better when you don’t. Also, how do you call multiple functions in parallel with coroutines?
Coroutines are not the same as system threads; they implement cooperative multithreading. Hence why they’re analogous to async/await in terms of functionality - they’re mostly good for I/O or other non-CPU bound latent tasks. Just like with async/await you have to mark your pause points with something, like a call to coroutine.yield in Lua, to pause execution and let the calling coroutine take over.
It occurred to me while reading this how deeply weird it is that we have entrenched a single data structure as the abstract model on which we build control flow. Church has a lot to answer for.
What’s bad about that? I think we have a great desire to keep things simple, so if we can reduce something down to a single data structure, why wouldn’t we want to do that?
Hmmm, that’s an interesting observation. It seems to me that CPS and models involving concurrency are both more capable extensions, but is there any truly orthogonal alternative?
I think it’s less “we entrenched it” and more that there’s no other data structure that fits the requirements for the kinds of control flow we want to model.
First thought: Yes there is, it’s called a tree. Or sometimes a graph, but usually a function call chain ends up being a tree.
Second thought: Yeah but implementing trees at a low level is complicated. Stacks are nice and dense and seldom need memory management besides “push” and “pop”. So, stacks are an optimization.
Third thought: …and how do you do a depth-first traversal of a tree? With a stack.
…you know, I think we might be onto a Deep Truth here.
Ding ding ding! I spent the better part of 2018 in an existential crisis over that. ;)
It’s also no coincidence that a dual-stack automaton or a queue automaton are equivalent to Turing Machines. It all falls out in some beautiful, scary ways.
cough Forth cough
Some languages replace the notion of a stack with a list of activation records. This makes forking structures quite easy but the compiler generally tries to represent it as a stack in the common case. Some Lisp machines with hardware-assisted GC did this more natively, but you need some integration between control flow and memory allocation, and a single register containing an address is the simplest. There’s no conceptual reason that it needs to be a single stack. There have been multi-stack stack machines, for example, though they aren’t a good fit for Algol-style languages.
Coroutines, asynchronous message sending, and so on are all interesting control-flow models, but the prevalence of the stack (and, especially, the hardware support) means that they’re second class.
I find this particularly interesting in light of a paper I read around 15 years ago that looked at organisational models and found that only around 10-20z of the population naturally thought in terms of hierarchies for organisation. This is a big part of the reason that iTunes was so popular: it gave you tags and filtering instead of folders. Gmail learned the same lesson and was hugely popular. The paper didn’t notice a couple of things:
My conjecture is that we have, for the last 60 years, built programming languages around a mode of thought that is not natural for around 85% of the population. It’s not that they find programming hard, it’s that they find programming in languages where control flow is expressed in lexical hierarchies difficult. Unfortunately, there aren’t enough languages that don’t do be able to make a good comparison (though, from my memory of the ‘80s, more people found BASIC easy before the introduction of GOSUB). I keep trying to persuade people doing programming usability to test this hypothesis.
One of my earliest experiments with concurrency was modeling on-demand function calls in lieu of actual functions.
That was enough to convince me that stack-oriented control flow was ideal for that kind of program organization.
It was also enough to convince me we haven’t fully explored concurrency as a general method of modeling flow control yet.
Yeah, coroutines with forking stacks or their own contexts is the first thing I thought of too…
…and I have a real hard time thinking about how to use coroutines effectively because they’re not hierarchical. XD This is a real interesting insight! I haven’t had coffee yet and so am somewhat tempted to dismiss part of it by saying “80-90% of humanity also sucks at everything”, but while that’s true it also may or may not be correlated. :P Let me try harder:
To look at other fields of human endeavor… hierarchies get used a lot for organizing large, complex systems. Companies, electronic components, city design, political systems… all are usually built with hierarchies. But on the flip side, there’s lots of things that aren’t: Houses are usually built using a fairly flat hierarchy: you have one node at the top that consists of the architect, general contractor, and other organizers/planners, and then you have a handful of specialist teams beneath them that do framing, electrical, plumbing, etc. I’ve been watching a lot of woodworking videos on youtube lately and those are generally fairly complex and intricate human artifacts built with a huge amount of skill, that are also mostly non-hierarchical. Unless it needs to be moved and gets too big to be moved, the cabinet or tree house or bowl or whatever is usually made as a single tightly-integrated piece. And so on.
So what’s the difference? The one I can see is that hierarchical systems are also big and involve many, many people, while the non-hierarchical ones are smaller. You can have small hierarchical systems and big non-hierarchical systems but they tend to be less common. So hierarchies are a pretty good way of communicating and dividing work among many people.
…this means that the CPU’s stack pointer is an incarnation of Conway’s Law. :O
So if we assume this is correct, are we indeed Doing Something Wrong? If hierarchies are an okay way to organize a lot of monkeys, and most software is made by large groups of monkeys, then organizing our software around hierarchies makes a lot of sense. BUT, there’s plenty of perfectly cromulent software out there that has been made, or is yet to be made, by small numbers of monkeys that don’t need that kind of organization. And there may be good ways of organizing monkeys out there besides hierarchies: Morning Star Company is one quite interesting case study.
So with this in mind I wouldn’t necessarily say that a hierarchical organization of programs is bad, but it would certainly seem to be leaving a lot on the table in terms of optimizing for a specific, fairly narrow use-case: large companies/projects with lots of people working together. Since a lot of modern computing grew out of exactly those kinds of systems (government, large companies, military) this makes perfect sense, but it also suggests we can do better. So… it’s a very interesting hypothesis and I would love to learn more!
Not sure if I get your point, but this “Coroutines in Lua” paper has a good discussion of alternative control flow structures
https://www.lua.org/doc/jucs04.pdf
including the relationship of the “Stackless” Python fork (green threads that don’t use the C stack) to Lua coroutines, etc.
I read this a long time ago, and don’t remember all the possibilities … it would be nice if someone dug up this knowledge, especially now that async/await seems (weirdly?) popular / dominant
I like async/await, it just seems more understandable than other kinds of async to me (note that I am mostly familiar with JS async), since it’s basically sugar over promises which are sugar over callbacks which are as simple as it gets.
Coroutines are really cool compared to async/await because they don’t suffer from the function coloring problem. In fact an asynchronous runtime can be built on top of coroutines entirely.
At a language level you can kind of imagine coroutines as having any and all functions implicitly marked with
async, as well as any and all function calls implicitlyawaited, so any function may await for a result at will and so the coloring disappears completely. Though the runtime implements it more efficiently than a classicasync/awaitsystem would be implemented (ie. sugar for callbacks/promises) - basically a coroutine is like a separate VM that can be suspended and resumed on demand.So to implement an async runtime you’d have a main loop which waits for events to come in, and resumes awaiting coroutines in response to those events. Then when writing an async task, you just write linear code as if you were using blocking operations, but at the points where the thread would otherwise block and wait for a result, the coroutine’s execution pauses (it yields) and control is passed back to the main loop, which can then resume another coroutine and let it run, and so on and so forth. And it all doesn’t result in any annotation creep :)
I think function coloring is valuable, mostly as a “will this function potentially take a significant amount of time” indicator. I guess coroutines are better when you have threads and async/await is better when you don’t. Also, how do you call multiple functions in parallel with coroutines?
I think you’re right about the explicitness aspect here, it can impact your understanding of the code. On the other hand an analogous explicitness argument can be made about eg. automatic closure captures - they can make the lifetime of your objects unpredictable, yet we all use them because the convenience factor greatly outweighs this disadvantage.
Coroutines are not the same as system threads; they implement cooperative multithreading. Hence why they’re analogous to
async/awaitin terms of functionality - they’re mostly good for I/O or other non-CPU bound latent tasks. Just like withasync/awaityou have to mark your pause points with something, like a call tocoroutine.yieldin Lua, to pause execution and let the calling coroutine take over.