Can Programming Be Liberated from the von Neumann Style? (1977) [pdf]
HNers, let me tell what Backus finally had in mind come to fruition; I only figured this out recently: <a href="https:&#x2F;&#x2F;www2.eecs.berkeley.edu&#x2F;Pubs&#x2F;TechRpts&#x2F;2014&#x2F;EECS-2014-130.pdf" rel="nofollow">https:&#x2F;&#x2F;www2.eecs.berkeley.edu&#x2F;Pubs&#x2F;TechRpts&#x2F;2014&#x2F;EECS-2014-...</a><p>Here&#x27;s the thing, Backus was not coming from the lisp and embryonic ML communities that were function programming research at the time. This was career-retrospective speech be a new-commer to the field. I think the existing community was surprised and bemused.<p>Certainly your regular function programminger would have chuckled at all the &quot;point-free&quot; style FP. This was a decade before Haskell mind you, and at least a decade before lots of function reuse became popular (being blocked on better strictness analysis and a lack of type classes and instances). Remember in then-cutting-edge Scheme, (define ...) has an implicit (begin ...) rather than single-expression body, and don&#x27;t get me started on the other imperative lisps. APL before FP just  made the existing community laugh harder.<p>So fast forward a while, and even today implicit parallelism is not happening much in production in Haskell. Applicative is much more popular than Arrow, and thus everyone is still writing Von Neuman code even if its dressed up functionally.<p>Well, let me tell, that thesis puts a lot of the pieces together:<p>The real genius of point-free isn&#x27;t getting rid of the names. We have debruign indices for that. Nor is it allowing other modules of computation. Computer scientists found good ole&#x27; 1970s Category Theory (In principle, Backus could have done this too!) and now we know about (symmetric) monoidal categories and their internal languages and all the stuff we need to point-free-ify the programs in lambda-calculus-influenced calculii.<p>The real genius is dealing with dynamism &#x2F; higher-order programs. With the raw lambda calculus, you are in a fun house of higher-orderism and it&#x27;s hard to jump out of the substitution &#x2F; term-rewritting mindset. CPS, which occupied much of the functional research community for at least a man-decade, only further serializes and higher-order-ifizes things. Monadic programs bind promiscuously; every step is potentially dynamic af, one again also serializing and higher-order-ifizing things.<p>With arrow-like things, however (and Control.Cateogry.* and Profunctor is really much better at distilling the concepts than the legacy Arrow class, thanks Ed), suddenly we have a decently expressive form of computation with no lambdas in site. We&#x27;ve lifted the &quot;fog of war&quot;, freeing the first order &quot;90%&quot; of the work from the higher order &quot;10%&quot;.<p>Arrow notation as implemented in Haskell today, however, abuses `arr` for the structural rules of the guest language (weakening, contraction, and exchange per Wikipedia [1]). This reshrowds everything and ruins all the promise of Arrows. Yuck.<p>Back to the thesis, there are 2 big contributions:<p>1) A practical version of Arrow which doesn&#x27;t need arr for structural rules. (Control.Cateogry.* since does this better and with more faithfulness to the math, but had to start somewhere.)<p>2) A theory of heterogenous metaprogramming so the first order and higher order bits don&#x27;t even have to be the same language. We&#x27;re talking things like and FPGA that computes its own re-flashing.<p>There is also a protoype implementation of various lambdas so humans can still use names, but I hear its bitrotted and so I can&#x27;t vouch for it.<p>So, back to John Backus. The thing is programmers are lazy. They rather write in the language they know, or learn the language their teachers know. Also, humans need at least the option of some names (even if we have to name too many things today), so mandatory combinators will cause problems as long as we struck programming in shitty, 1-dimentional text. Finally, without at least the <i>taste</i> of actually compiling to other programming models, along with scaling programs with the Von Neumann model, the economic and curiosity incentives just aren&#x27;t there. And in 1978 the Von Neuman model was still fucking killing it. Wires were fast, and components be they spinning disks, ALUs, or DRAM were all kinda slow but in similar and predictable ways. Programming DOS was a shit-show, of course, but so were non-trivial compilers. Nothing was ready.<p>Now we know how to do program better, have the power to run the compilers, and the legacy machines have a cost model I like to think of as &quot;molasses in capillaries with huge bottlenecks&quot;. We&#x27;re ready.<p>[1]: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Structural_rule" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Structural_rule</a>