A Note on Language / Complier Theory

It dawned on me tonight, while working on some code, that there are statements that will compile in a language, but cannot be expressed without running the complier twice, once to generate code, and the second time, to run the generated code. I’ll simply provide a more academic version of the exact problem I had, which was specifying a statement that could be generated using the text processing functions of a language, but cannot be directly expressed in the language itself as a general matter. To make things concrete, consider a set of natural numbers, and assume that is an infinite, and non-computable subset of the natural numbers, which must exist, since the set of all subsets of the natural numbers is uncountable, whereas the set of all programs is of course countable. Now assume you want to generate exactly the following statement:

,

where is the i-th number in the set . Because is a non-computable subset, there is no general equation that will allow you to generate the entries in , and so as a consequence, you cannot generate the statement above, as a general matter, without first generating the first entries of . As a consequence, as a general matter, you must run the compiler twice, in order to generate a statement that is nonetheless accepted in the language of the complier. This might be a known result, but I’ve never heard of it before, and as a general matter, it suggests a useful method of programming, that uses the text processing functions of a language to generate statements that will compile, but would otherwise be impossible to generate. And though it’s not impossible to generate the code in my A.I. software, it turns out, this is exactly how the front-end GUI for Black Tree works, in that the user makes a series of selections, which causes the GUI to generate the relevant code.

Advertisement