What is that supposed to mean?
- Donald Knuth
Incidentally, the earliest expression of this idea that I’ve seen is from a talk by Fischer Black [0] in 1963, published a year later in a volume on LISP [1]:
Programming style is not a matter of efficiency in a program. It is a matter of how easy it is to write or read a program, how easy it is to explain the program to someone else, how easy it is to figure out what the program does a year after you've written it; and above all, style is a matter of taste, of aesthetics, of what you think looks nice, of what you think is elegant.
Although style is mainly a matter of taste, a programmer with a "good" style will find his programs easy to write, easy to read, and easy to explain to others. ...
In particular, you may have acquired special programming tricks that you are very fond of, and that aren't used by other programmers, but that don't make your programs much more efficient. I urge you to stop using those tricks. As Samuel Johnson once said, "Read over your compositions, and when you meet with a passage which you think is particularly fine, strike it out."
In other words, make your style simple, not complicated, even though the complicated style may seem to have some abstract virtues. ...
0. Yes, this is the same Fischer Black of the Black-Scholes duo of financial fame. His PhD, informally supervised by Marvin Minsky, was on artificial intelligence. Myron Scholes, for that matter, was also a good programmer and made money programming for economics professors at Chicago while he did his PhD there.
1. F. Black, “Styles of Programming in LISP,” in The Programming Language LISP: Its Operations and Applications, ed. E. Berkeley and D. Bobrow (1964), p96 (p106 of the PDF): http://www.softwarepreservation.com/projects/LISP/book/III_L... [PDF]
That's irrelevant, as early computers weren't programmed in LC, not build on such an architecture. And of course algorithms and even programs (e.g for Babbage's computer) existed before LC.
However, most programming languages(including C, Java, etc.) look much more similar to lambda calculus than a description of a Turing Machine - and for very good reason. Have you ever tried describing a TM that encodes even the simplest logic? It is a pain in the ass.
Indeed, most courses on the theory of computation that discuss Turing Machines etc. don't ever expect students to fully describe a Turing Machine. Many times they use a language reminiscent of the lambda calculus to describe Turing Machines.
Just take a look at the definition of Turing Machines on wikipedia and examples of TMs: https://en.wikipedia.org/wiki/Turing_machine#Formal_definiti...
https://en.wikipedia.org/wiki/Turing_machine_examples
That resembles no description of programs that are written by humans to run on computer systems, unlike the lambda calculus.
That's because we don't actually have tape, but random access memory. But a turing machine is just a limited form of imperative programming, and much closer to Assembly, or C, Fortran, BASIC, or even Java, than Lambda Calculus.
>That resembles no description of programs that are written by humans to run on computer systems, unlike the lambda calculus.
Actually looks like a pretty run of the mill description of working with memory locations, gotos, conditional jumps and so on. Substitute the need to run through the tape for random access memory, and you're there.
The examples don't remind you of programs written by humans mostly because they're visual examples showing the whole state configuration. If we similarly mapped the memory states during various steps of the execution of a common imperative program, it would look very much like those tables.
The beauty of a declarative notation is not that you get to ditch representation of state, is that you can represent such state in a much more compact and tractable way than what is required by theoretical representations of imperative machines. Trying to do mathematical reasoning with Hoare logic is a pain in the ass.