Lies, damn lies!

[Jecel Assumpcao Jr]

Francois-Rene Rideau wrote:
> 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.

Now you got me really confused! Every explanation I have ever seen
of Turing Machines have always presented them with a Harvard
Architecture instead of a Von Neumann one: they store their state
in an infinite tape of symbols and their code in a separate table
representing a finite state machine. Only the tape can be accessed
and changed, not the table.

> In the case of prefix machines,

Excuse my ignorance - I am not familiar with this term in this
context.

> where the "source" is a finite bit (or byte, or foo) stream

That would be our friendly Von Neumann?

> [considered as a cons list from left to right],

Here I am confused again - I think of a foo stream as one thing,
but a cons list as another (though it can be built from a foo
stream).

> this means that the "rest of the bit stream" can be fully reified.

I can see this for the cons: the "rest" is represented by the CDR
pointer.

> The only standard language that does it is FORTH.

Because of the inner interpreter/outer interpreter (compiler) stuff?

> 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.

A Turing Machine is not universal either, by your new definition.
Sure, I can build an interpreter in it that will simulate a given
Von Neumann machine which can run self modifying code and other
stuff that the Turing Machine can't do directly, but that "is very
difficult and inefficient" :-)

I can write a Z80 emulator in Pascal and run Forth on top of that.
The Pascal/Z80emu/Forth combo can do anything (supposing no stupid
memory limits and stuff) that Forth can do directly, so that makes
Pascal universal in my book.

Your mention of I/O libraries leads me to think that you may have
a very different definition of universality: that a language should
be able to do *everything* the underlying hardware allows it to do.
We would have a "machine language equivalence" instead of Turing
Machine equivalence. But it can't be that, since then Forth would be
no better than the rest and you are saying it is special.

The part about Lisp and Shell languages that I deleted really showed
that you are worried about something else. While I didn't quite get
what you are after, I think you might find Smalltalk-74 to be your
ideal language!

-- Jecel