I don’t understand why he has chosen to conflate compilers with programming languages; the latter is a much bigger concept than what he discusses. Apart from the omission of systems that can perform compilation at runtime I felt like his list was pretty good.
You have a point. Short Code was a programming language that predated compilers, as one example; and there are programming languages that we don’t compile. However, there aren’t that many of those: APL, sometimes Brainfuck, maybe BASIC, arguably SQL, arguably PostScript, old versions of Tcl, and MS-DOS batch files. The design, implementation, and user experience of all other programming languages is intimately tied up with compiler technology, even if the compiler output is just an AST that the interpreter walks.
So I think programming languages are a slightly bigger concept rather than a much bigger one. But maybe I’m not sharp enough to pick up the hint about how big the concept of a programming language is; can you elaborate?
Well, I was thinking primarily of the fact that a programming language is an abstract thing, and a compiler is a specific piece of code. A programming language can have zero to N implementations, some compiled and some not. Lambda calculus is a language that predates the invention of compilers by decades. Heck, even the original design for Lisp was never intended to be implemented; that idea came a while later.
While in theory this is true, just as the calculus and classical physics are totally separate things, historically they developed together, each feeding off the other, and they’re actually quite intertwined intellectually.
I agree that Church’s λ-calculus is indeed a programming language. Church separated out the programming-language part as a thing-in-itself in 1936. Turing also published his Turing-machine paper in 1936. Turing’s 1936 paper has an appendix that shows how to translate functions written in the λ-calculus into Turing-machine definitions, which is to say, it provides a formal procedure for compiling the λ-calculus into the instruction set of a hypothetical computer. The paper also argues that any such formal procedure can be computed by a Turing machine. Turing did not actually write the specific piece of code that would carry out that compilation, but perhaps we can forgive him that, since he didn’t build a Turing machine either, and so he didn’t have a computer to run a compiler on.
It’s probably not a coincidence that Church published the first programming language as such in the same year that his student Turing explained how it could be compiled.
Only 16 years later, Grace Hopper wrote the A-0 compiler, in 1952, over the objections of her superiors who claimed that computers couldn’t write programs. Apparently they hadn’t read Turing’s paper. I think the EDVAC, delivered in 1949, was the first computer that you could conceivably have written a compiler for.
The Lisp story is really interesting. It’s true that the original design for Lisp notation was never intended to be implemented, but Lisp itself was inspired by the news of the Fortran compiler. At first, McCarthy wanted to augment Fortran with list-processing capabilities (the linked list had been invented shortly before), but once he started thinking about list processing, it occurred to him that maybe it would be a good idea to develop a notation for general recursive functions using it, and for that purpose, he developed the metacircular interpreter as a sort of informal proof of computational universality. The metacircular interpreter, of course, needs a homoiconic representation, and that’s where the Lisp notation we use today came from. The recursive-function theorists basically ignored McCarthy’s work, unfortunately, because they weren’t actually interested in writing down recursive functions most of the time, but just proving that they existed.
So there’s this fascinating and very intimate interplay between the idea of the compiler and the idea of the programming language, even from the earliest days.
So that’s why I don’t think programming languages are that independent of compilers, or that much bigger a thing.
I don’t understand why he has chosen to conflate compilers with programming languages; the latter is a much bigger concept than what he discusses. Apart from the omission of systems that can perform compilation at runtime I felt like his list was pretty good.
You have a point. Short Code was a programming language that predated compilers, as one example; and there are programming languages that we don’t compile. However, there aren’t that many of those: APL, sometimes Brainfuck, maybe BASIC, arguably SQL, arguably PostScript, old versions of Tcl, and MS-DOS batch files. The design, implementation, and user experience of all other programming languages is intimately tied up with compiler technology, even if the compiler output is just an AST that the interpreter walks.
So I think programming languages are a slightly bigger concept rather than a much bigger one. But maybe I’m not sharp enough to pick up the hint about how big the concept of a programming language is; can you elaborate?
Well, I was thinking primarily of the fact that a programming language is an abstract thing, and a compiler is a specific piece of code. A programming language can have zero to N implementations, some compiled and some not. Lambda calculus is a language that predates the invention of compilers by decades. Heck, even the original design for Lisp was never intended to be implemented; that idea came a while later.
While in theory this is true, just as the calculus and classical physics are totally separate things, historically they developed together, each feeding off the other, and they’re actually quite intertwined intellectually.
I agree that Church’s λ-calculus is indeed a programming language. Church separated out the programming-language part as a thing-in-itself in 1936. Turing also published his Turing-machine paper in 1936. Turing’s 1936 paper has an appendix that shows how to translate functions written in the λ-calculus into Turing-machine definitions, which is to say, it provides a formal procedure for compiling the λ-calculus into the instruction set of a hypothetical computer. The paper also argues that any such formal procedure can be computed by a Turing machine. Turing did not actually write the specific piece of code that would carry out that compilation, but perhaps we can forgive him that, since he didn’t build a Turing machine either, and so he didn’t have a computer to run a compiler on.
It’s probably not a coincidence that Church published the first programming language as such in the same year that his student Turing explained how it could be compiled.
Only 16 years later, Grace Hopper wrote the A-0 compiler, in 1952, over the objections of her superiors who claimed that computers couldn’t write programs. Apparently they hadn’t read Turing’s paper. I think the EDVAC, delivered in 1949, was the first computer that you could conceivably have written a compiler for.
The Lisp story is really interesting. It’s true that the original design for Lisp notation was never intended to be implemented, but Lisp itself was inspired by the news of the Fortran compiler. At first, McCarthy wanted to augment Fortran with list-processing capabilities (the linked list had been invented shortly before), but once he started thinking about list processing, it occurred to him that maybe it would be a good idea to develop a notation for general recursive functions using it, and for that purpose, he developed the metacircular interpreter as a sort of informal proof of computational universality. The metacircular interpreter, of course, needs a homoiconic representation, and that’s where the Lisp notation we use today came from. The recursive-function theorists basically ignored McCarthy’s work, unfortunately, because they weren’t actually interested in writing down recursive functions most of the time, but just proving that they existed.
So there’s this fascinating and very intimate interplay between the idea of the compiler and the idea of the programming language, even from the earliest days.
So that’s why I don’t think programming languages are that independent of compilers, or that much bigger a thing.