Lies, damn lies!

[Francois-Rene Rideau]

Dear Tunespeople,
   I'm sorry for my long silence. I've been busy with some conferences,
papers to write, depression, etc. Now it's sunny, and I feel more productive.

I'm back from a conference on Algorithmic Information Theory,
	http://www.loria.fr/conferences/TAI99/tai.html
where there were lots of top scientists on Kolmogorov Complexity.
I learnt a lot about K-complexity and its applications
from the very masters of the science,
and gave myself a truly petty speech about metaprogramming and complexity,
with ideas excerpted from my paper on metaprogramming and free availability
of sources. The prepared text for my speech and the slides
will be available together with the sources of that former article, from
	http://www.tunes.org/~fare/articles/ll99/ll99-fare.tar.gz
before tonight.

A relevant speech to us was by John Tromp, who wrote a universal prefix
function based on SK-combinators (test it on the web!):
	http://www.cwi.nl/~tromp
In this formalism, successive self-applications of the universal function
are fully done in finite time and only induce a constant time additive
overhead to the evaluation of the code that is to be evaluated.

A common conclusion of John's and my studies is that a language,
to be universal (== Turing-equivalent), must be able to quote code
non-intrusively in a source-code-structure-preserving way,
so as to write metaprograms that manipulate the quoted code.
In the case of prefix machines,
where the "source" is a finite bit (or byte, or foo) stream
[considered as a cons list from left to right],
this means that the "rest of the bit stream" can be fully reified.
The only standard language that does it is FORTH.

My! FORTH is the only standard language that is universal!!!
In particular, the core of the C language (without additional I/O primitives),
that of ML, of Java, or of just ANY language of the languages you learnt,
is conspicuously NOT universal. Only through the use of awkward non-portable
fragile and extra-language I/O libraries can you achieve universality.
None of the languages you learnt was truly Turing-equivalent!
My friends, we were lied upon; we were deluded!
We were presented tools and were led to sincerely believe
that they had all the power required. Only they hadn't!
The only way for all these languages to be truly universal
is to allow for writing interpreters or compilers in these languages.
only the former is very difficult and inefficient, and the latter is
completely impossible to do standardly. And even then, you must rely
on the OS infrastructure to provide with files et al, which in turn
has non-portable and completely unreliable semantics.

CommonLISP, Scheme, and languages of the LISP family, ARE universal,
but only if you consider the source as being S-expressions
rather than a text stream. Which implies that grammar irregularities
such as comments, Scheme argument syntax restriction, conditional #+parsing,
and suches, should be removed from the language and/or replaced.
Shells are universal in as much as you can quote here-text << END,
if you consider text as appendable both ways (rather than
merely prefixable text, aka consable lists).
Only they are VERY awkward universal languages,
and only in as much as you use non-standard external commands,
and use files as unsafe variables (that external processes could modify!).
Oh, and NUL character handling is dubious in shells.
Perl is somewhat a better universal language, although its semantics
is so complicated that no one has been able to build any perl semantic
analyzing tool yet.

Hum. I think I should write a paper on this very important theoretical result.
The whole world has been crooked. Now just WHO would publish such a paper?

Well, I have lots of things to write this week.
I'll also try to reply to the most significant e-mails of previous months
on the list, unless they were conclusive, or were already replied correctly
by e.g. Tril. Read you soon!

[ "Faré" | VN: Уng-Vû Bân | Join the TUNES project!   http://www.tunes.org/  ]
[ FR: François-René Rideau | TUNES is a Useful, Nevertheless Expedient System ]
[ Reflection&Cybernethics  | Project for  a Free Reflective  Computing System ]
...so this guy walks into a bar.
"The usual, Mr. Descartes?" the barman asked.
"I think not," Rene replied, and promptly disappeared.