Graham addresses the point you’re making about the difference between the language being powerful vs it having a large standard library. As he says in the link, by his metric, two languages are “at the same level” if they only differ by one of them lacking a library function that the other has. His test for proving that language A is “above” B is the question: “To do a task in B, do you have to write an interpreter for A (or language on its level)?” For example, adding recursion to Basic requires going beyond writing one more library function.
After thinking about this for (a long) while, I think the most powerful languages would then be the ones that are internally extensible and allow modification of their own syntax and semantics. For instance BASIC would become a far more powerful language than C or LISP if it had a function for altering the interpreter itself. Certain versions of BASIC effectively had this by allowing functions to be written in machine language and then executed. Theoretically, the machine language snippets could extend the interpreter to add structured programming features or first class functions. The same could potentially be done with C by just including the Tiny C Compiler in the source (as both the compiled functions and C strings containing the source) and then reflexively recompiling the compiler to add features.
What is most interesting to me is that making a language that can modify itself requires a complete definition of its execution environment in order to be safely extensible. The most powerful languages would have to fully and formally define their semantics as well as their syntax and make both accessible within the language so that extension of the syntax could could safely extend the semantics to match. In other words BASIC with assembly language is not enough if you don’t know everything about the hardware and the interpreter you start with. From my CS student days I seem to recall reading that few programming languages have rigorously defined semantics (“This feature is implementation specific” and “This behavior is undefined” appears far too often in most specifications). The closest thing I can find is the Gödel machine, but that’s defined directly in terms of a Turing machine, afaict.
Graham addresses the point you’re making about the difference between the language being powerful vs it having a large standard library. As he says in the link, by his metric, two languages are “at the same level” if they only differ by one of them lacking a library function that the other has. His test for proving that language A is “above” B is the question: “To do a task in B, do you have to write an interpreter for A (or language on its level)?” For example, adding recursion to Basic requires going beyond writing one more library function.
After thinking about this for (a long) while, I think the most powerful languages would then be the ones that are internally extensible and allow modification of their own syntax and semantics. For instance BASIC would become a far more powerful language than C or LISP if it had a function for altering the interpreter itself. Certain versions of BASIC effectively had this by allowing functions to be written in machine language and then executed. Theoretically, the machine language snippets could extend the interpreter to add structured programming features or first class functions. The same could potentially be done with C by just including the Tiny C Compiler in the source (as both the compiled functions and C strings containing the source) and then reflexively recompiling the compiler to add features.
What is most interesting to me is that making a language that can modify itself requires a complete definition of its execution environment in order to be safely extensible. The most powerful languages would have to fully and formally define their semantics as well as their syntax and make both accessible within the language so that extension of the syntax could could safely extend the semantics to match. In other words BASIC with assembly language is not enough if you don’t know everything about the hardware and the interpreter you start with. From my CS student days I seem to recall reading that few programming languages have rigorously defined semantics (“This feature is implementation specific” and “This behavior is undefined” appears far too often in most specifications). The closest thing I can find is the Gödel machine, but that’s defined directly in terms of a Turing machine, afaict.