[tikhonj]

Turing-completeness is a red herring. All it talks about is what a machine can compute, not how. This is an important distinction because libraries can be used for things like meta-programming.

It's completely possible to have a Turing-complete method of computation that does not allow the equivalent of self-modification, for example. And then you won't be able to write a library for self-modifying code!

You can't retrofit Java with a macro system without writing a preprocessor, for example. So it is impossible to have a whole bunch of useful constructs in a library.

Essentially, as soon as you consider "self-reference"--that is, programs that depend on details of the machine itself--Turing-completeness stops mattering. And this is still important; programmers care about more than just what the program does, after all!

[lutusp]

> Turing-completeness is a red herring.

No, as a matter of fact, it's the point. A Turing-complete system can compute anything that any other Turing-complete system can.

> It's completely possible to have a Turing-complete method of computation that does not allow the equivalent of self-modification ...

Speaking of red herrings?

[tikhonj]

It's a red herring because the original claim was not "Haskell can compute function Java cannot" but rather "there are many libraries in Haskell which aren't even possible to write in Java".

The point is that libraries do more than just compute stuff. If all we cared about was what you could compute, there are plenty of interesting libraries that wouldn't count for anything! Any library exporting new types of control flow, for example.

The argument is that there are libraries you can write in Haskell that you can't write in Java. And since libraries can do meta-programming which is possible in Haskell but not in Java, this is accurate. Similarly, since self-modification is something a library can do, possible on one model but not another, it isn't a red-herring.

Hmm, how can I make my point clearer? Let me give you a very specific example then: a library with new syntax sugar would be impossible to write in Java. Sure, this does not allow you to compute anything different, but it's still very important and has a practical effect. Let's take a very trivial library of this sort: a library only providing an "unless" statement like Perl's. Possible in some languages, not possible in others.

Some of the examples in the original post also fall into this category. The lenses library, for example, just allows you to write composable accessors and mutators. It does not compute anything new. But it's still very useful because it makes your code simpler and gives you new ways to express yourself. You could not write anything like it in Java.

Hopefully that cleared things up a bit.

[lutusp]

> It's a red herring because the original claim was not "Haskell can compute function Java cannot" but rather "there are many libraries in Haskell which aren't even possible to write in Java".

That's false. It's as false as the other claims.

> The argument is that there are libraries you can write in Haskell that you can't write in Java.

Still false.

> Similarly, since self-modification is something a library can do, possible on one model but not another, it isn't a red-herring.

It's a red herring because libraries do not ever self-modify. Not. Ever.

> Hopefully that cleared things up a bit.

Oh, it definitely did.

[tikhonj]

False, is it? I'm quoting the opening comment directly: "There are many libraries in Haskell which aren't even possible to write in Java". So that is the initial argument. It says nothing about computable functions and everything about possible libraries.

Or do you mean the argument itself is false? Well, a library providing new control structures certainly fits that! But yes, it's as false as my other claims--not false at all.

There are Turing-complete languages where you cannot add new control structures. (Or even ones where the concept of "control structure" does not apply.) So a library providing control structures would be impossible. And Haskell has a slew of libraries for control flow: everything in the Control.* namespace.

So both languages are Turing-complete and equally powerful, and yet certain libraries can only be written in one. This only makes sense for self-referential things, where the library somehow affects the language.

As far as self modifying code goes--it's not that the library modifies itself; rather, the library gives you tools for writing self-modifying code. If your language does not have this capability, such a library could not exist. But the language would still be Turing-complete!

The post seems to have cleared up nothing. Ah well, c'est la vie.