5 ms·

I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as

I've recently been thinking that we are looking at a situation analogous to the one Ben Franklin was in when he identified the two types of electrical charge as "positive" or "negative" pressure in the "electrical fluid" - he took a guess, which happened to be wrong, and ever since we have been stuck describing a surplus of electrons as "negative" and a deficit as "positive". This is no obstacle for the experienced but will remain an eternal hangup for beginners. By analogy, of course, I am suggesting that the Church model of computation might have served us better as a foundation than the Turing model has done, since it seems that everything's turning up lambdas as the technology S-curve for silicon computers continues to flatten out.

masak 11y ago
Or maybe we needed to scale to some point with the Turing model for the Church model to assert itself and prove its merits in comparison. It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.
- marssaxman 11y ago
  That certainly makes sense. I'm just looking ahead over the next couple of centuries and imagining generations of young programmers stumbling over all these ancient vestiges of mutable state and synchronous, batch-driven control flow which will probably still be littered around the roots of our computing systems long after the dominant paradigm has shifted. You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway. We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention. Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done. On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.
chubot 11y ago
I don't really agree... One reason is that computing models don't say anything useful about I/O, which we need in real computers. Turing machines have a straightforward extension to incorporate I/O -- execute it as a side effect at a given step. In contrast, the Church model doesn't really have any notion of time, so it's not clear how to reason about I/O. What evaluation order is used? In terms of computation, they're of course equivalent, so you can execute the Church model on the Turing-like machines (or more specifically a Von Neumann architecture). So maybe that was the right "choice" (if there ever was one). There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. Closer to the ground, there is a pattern of "throwing away information at interfaces" in computing. Interfaces like x86, C, Unix, etc. get solidified by evolutionary forces. The cost of that modularity is global inefficiency. Another good example of that is the Java code gen architecture. People say "static types in Java code let you generated better code!" Well, no. The Java compiler throws out all the type information, generating Java byte code, which is dynamically typed. Then the JIT takes the byte code and has to re-infer all the type invariants to generate machine code.
- dang 11y ago
  > There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. My understanding is that the dataflow architectures didn't fare well for technical reasons. The instruction-level parallelism they worked with turned out to be too fine-grained, i.e. the cost of scheduling was greater than the win of parallelism for many programs, especially normal sequential programs that still need to be fast. This led to research in coarse-grained dataflow, but it doesn't seem that much has come of that. https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Literature/DataFlowProgrammingLanguages.pdf https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Lit...

masak 11y ago

Or maybe we needed to scale to some point with the Turing model for the Church model to assert itself and prove its merits in comparison. It's a bit more thrilling to think of it that way, as a matter of scale. When space and time resources are scarce, thinking of the computer as a big piece of RAM that we mutate in-place makes the most sense. As we push upwards and outwards into enough resources and a bigger need for parallelism, it suddenly makes more sense to switch perspectives and reason in terms of binding and substitution.

marssaxman 11y ago
That certainly makes sense. I'm just looking ahead over the next couple of centuries and imagining generations of young programmers stumbling over all these ancient vestiges of mutable state and synchronous, batch-driven control flow which will probably still be littered around the roots of our computing systems long after the dominant paradigm has shifted. You can see the same pattern with IO models. We have programming languages descended from 50s-era concepts of computing in which the program drives the machine, but that just isn't true at all. A computer is a passive machine, not an active one: it reacts when you poke it with an interrupt, until it reaches a steady state and settles down again. Operating systems go to a great deal of trouble to simulate the kind of top-down flow control environment our imperative tradition wants to think it is operating in, but in order to get any real performance out of these systems, we all end up building asynchronous, reactive layers on top of the simulated batch-job anyway. We'd all be better off if we flipped the paradigm, imagining the process of building a program not in terms of writing instructions for the computer to perform, but in terms of creating a structure which will react appropriately in response to whichever events may be brought to its attention. Instead, we'll probably still be starting young programmers out with for-loops counting from 1 to 10 and printing the result on an imaginary console for decades to come, even though none of that is even remotely relevant to what's actually happening anymore, and once they've crossed that hurdle they'll promptly begin unlearning all that stuff in order to start getting real work done. On an unrelated note, I spent a while last fall/winter playing around with the idea of a very low level functional language - could we use these techniques in memory-constrained environments too? I didn't find the model I was looking for, but I think it's probably out there, and it would be very interesting to develop a functional/type-safe/immutable language suitable for microcontroller programming, with no garbage collection or implicit allocation. It may be that the Turing model is a better fit for computing in the small, but I suspect that we may find dataflow and functional composition to be useful at all scales. That way of looking at the world has some profound philosophical strength, after all - "you cannot step twice into the same river" and all that.

chubot 11y ago

I don't really agree... One reason is that computing models don't say anything useful about I/O, which we need in real computers. Turing machines have a straightforward extension to incorporate I/O -- execute it as a side effect at a given step. In contrast, the Church model doesn't really have any notion of time, so it's not clear how to reason about I/O. What evaluation order is used? In terms of computation, they're of course equivalent, so you can execute the Church model on the Turing-like machines (or more specifically a Von Neumann architecture). So maybe that was the right "choice" (if there ever was one). There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. Closer to the ground, there is a pattern of "throwing away information at interfaces" in computing. Interfaces like x86, C, Unix, etc. get solidified by evolutionary forces. The cost of that modularity is global inefficiency. Another good example of that is the Java code gen architecture. People say "static types in Java code let you generated better code!" Well, no. The Java compiler throws out all the type information, generating Java byte code, which is dynamically typed. Then the JIT takes the byte code and has to re-infer all the type invariants to generate machine code.

dang 11y ago
> There was an entire movement around dataflow processors AND dataflow languages in the 80's, where the instruction sets were not totally ordered (e.g. SISAL was single assignment). But these didn't fare well in the market. My understanding is that the dataflow architectures didn't fare well for technical reasons. The instruction-level parallelism they worked with turned out to be too fine-grained, i.e. the cost of scheduling was greater than the win of parallelism for many programs, especially normal sequential programs that still need to be fast. This led to research in coarse-grained dataflow, but it doesn't seem that much has come of that. https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Literature/DataFlowProgrammingLanguages.pdf https://www.cs.ucf.edu/~dcm/Teaching/COT4810-Fall%202012/Lit...