| HN Mirror

> There are many libraries in Haskell which aren't even possible to write in Java (automatic differentiation, parser combinators, lenses, etc.)

So you're saying Alan Turing was wrong? Publish your finding, win a Nobel Prize.

You didn't say it would be difficult, you said it wasn't possible.

Here's the breakdown:

1. Haskell is compiled into machine code.

2. Machine code doesn't care or reveal where it came from.

3. Points (1) and (2) demonstrate that any algorithm that can be written in Haskell, can also be written in machine code.

4. Therefore the claim that Haskell's libraries cannot be written in Java is false.

tikhonj 4855 days ago

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!

> 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 4855 days ago

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.

> 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 4854 days ago

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.

> So you're saying Alan Turing was wrong?

Nope! The Turing-completeness of Haskell and Java means they can both compute the same functions. However, there are certain things which are just not possible to express directly in some languages. Possible to compute, but not express directly.

Instead of Java, consider Brainfuck. It's a turing-complete language and certainly has no notion of what a function is. There's simply no way in Brainfuck to directly express that idea.

Another example, this time with Java and Haskell. In Haskell, I can write a function to add any two numbers (regardless of their type) like this:

add' :: Num a => a -> a -> a

add' x y = x + y

As far as I'm aware in Java, there's no way to write a function with a signature that says "Take two numeric arguments of any type". Certainly pre-generics, this is impossible.

Edits: markup

lelele 4855 days ago

> This isn't really relevant to the thread of discussion.

It was, before I got carried away: I was going to say that Turing-completeness does not translate to practice. And whoever chooses a language according to its Turing-completeness is missing the big picture.

Ah I see- sorry to've misinterpreted that! I definitely agree- brainfuck being the best example in favour of that argument :)

Java can produce any result that Haskell can produce. End of story, full stop. All non-broken computer languages are Turing machines.

This is not to suggest that someone would want to use Java for anything sufficiently sophisticated, unless one is a masochist, but then, that wasn't your claim.

> As far as I'm aware in Java, there's no way to write a function with a signature that says "Take two numeric arguments of any type". Certainly pre-generics, this is impossible.

A separate claim with no meaningful relation to the original one. This claim is that it would be inconvenient, not impossible.

> Java can produce any result that Haskell can produce. End of story, full stop.

Yes, I'm not disputing this- I'm fully in agreement that all turing-complete languages can compute all turing-computable computations. I've never been trying to argue against that. I'm sorry if I haven't explained myself clearly enough- let me give it another shot.

In Haskell, I can write a function operating on numbers like this:

    f x = x**2 + x + 1

The AD library means I can do this:

    g = diff f

and g will behave as if I'd declared

    g x = 2 * x + 1

As far as I'm aware, it's not possible to write this code in Java- you can't get the differentiated version of a Java function this way.

You can compute the same results, of course. You just can't write a library that will accept a function and give back its differentiation.

You can write a function that takes some representation of a mathematical function, for example as a string, and build a function from that to compute the same results, but you can't pass in an actual Java function- so you can't write the library. You can write a library which differentiates string-representations-of-functions, but you can't write one that differentiates first-class-Java-functions (well, objects with functions on, but you get the idea. I hope.)

https://code.google.com/p/javacalculus/

> As far as I'm aware, it's not possible to write this code in Java- you can't get the differentiated version of a Java function this way.

No. The algorithms for symbolic differentiation are well-known, they aren't unique to Haskell. They happen not to be present in any Java library AFAIK, but that's because no one is sufficiently masochistic to code them there.

(long pause ...)

Whoops -- I was wrong:

> You can write a library which differentiates string-representations-of-functions, but you can't write one that differentiates first-class-Java-functions ...

I think we're getting into a moot area now. If the end result is symbolic differentiation, the specifics become irrelevant. And, since Java bytecode can be converted into a textual representation, it can also be symbolically differentiated by conventional means.

Also, we've left the original topic, which was that Haskell has properties not present in other languages and/or outcomes not possible in other languages.

In a larger sense, wouldn't it be more praiseworthy to say that Haskell does exactly what other languages do, but much better? That time spent programming in Haskell is more productive when measured by bug-free lines of code and concise expressions? Or that, when parallel processing finally arrives in full force, functional programming will not longer be optional?

> If the end result is symbolic differentiation (...)

Ah, I see the problem- automatic differentiation is not the same as symbolic differentiation- see wikipedia: http://en.wikipedia.org/wiki/Automatic_differentiation This certainly isn't a moot point :)

> Also, we've left the original topic (...)

No- again, I've been saying the same thing all along. In fact I'm only using Haskell as an example. There are things which cannot be expressed in Haskell, too- for example dependent typed programs as you might find in Agda or Idris.

> In a larger sense, wouldn't it be more praiseworthy to say that Haskell does exactly what other languages do, but much better?

This is a separate conversation entirely. My aim is not to "praise Haskell". I have used Haskell and Java only as examples.

tikhonj 4855 days ago

There are completely reasonable languages (distinctly non-broken) that are not Turing complete like Coq and Agda. You can still use them to write interesting, non-trivial programs! In fact, their limitations aren't immediately obvious--the only interesting program it's obvious they can't write is an interpreter for themselves or another programming language at least as powerful.

lelele 4855 days ago

> Java can produce any result that Haskell can produce. End of story, full stop.

But can average Java programmers produce any result that average Haskell programmers can produce? I'd bet they can't. Haskell programmers are self-selecting: if you can grasp Haskell and be productive in it then you are an elite programmer. Not so if you can grasp Java.

> if you can grasp Haskell and be productive in it then you are an elite programmer.

Somehow I knew this was where it was going.

> Not so if you can grasp Java.

Compared to a cabbage or a turnip? I've been told you can't teach calculus to a horse. Elitism is like an onion ... and feel free to imagine that tedious conversation.

This isn't really relevant to the thread of discussion.