Hacker News Reader

Comment by paulgb | Hacker News Reader

Thanks. You're right; when I did the experiment myself (once with a Haskell program, once with a C++ one), the results definitely looked like lawyerese. Surprisingly, though, they were still shorter than the program. Maybe that just means I'm a bad Haskell/C++ coder, but I don't think that's all of it.

One point that I may not have properly gotten across is that I'm not suggesting that programming languages should approach English in form. I was just trying to establish English as a lower bound for the amount of information required to communicate an idea. (It's not even a lower bound, since English is fairly redundant, but it's an upper bound on the lower bound if you know what I mean)

If I said "until programming languages reach the information density of written English", do you think that would make more sense?

View on HN

I don't have time to write an essay about this now, and I'm not sure I'd be the right person to do so anyway, but here are some thoughts I believe to be relevant.

Real Information Theory, as opposed to Data Transmission Theory, has to take into account the receiver. The transmitter has to have a model of the receiver, and then devise the data that will transform the receiver according to the intent of the transmitter.

For example, if you're a mathematician and I talk about the topological space obtained by gluing the edge of a mobious strip to the edge of a disk being the same topological space obtained by identifying antipodal points of S^2, you'll know what I mean. If not, I have to explain further.

Similarly, a computer program can start with a top level description of your intent, and a competent programmer can then complete the steps.

But a computer is not a programmer. When you describe your algorithm in sufficient detail for a programmer, you haven't given enough information for someone who isn't a programmer. A non-programmer will look at what you've written and then say "How do I do that?" Thus you need further instructions.

So you might say "We sort this vector of numbers by picking one at random, scanning down the vector to separate into those that are smaller, equal and larger, then recurse." and a sufficiently skilled programmer who's never met the Quicksort can now implement it.

But there are details missing.

You programs should (perhaps) be arranged so that the main routine is sufficient for a very skilled programmer to complete. Each routine called then is sufficient for a slightly less skilled programmer to complete, and recurse.

The problem is that the terminating case is the computer, and not a programmer, or even a person. Thus the terminating case is a long way down.

Perhaps there is a language design that will bring the terminating case higher.

That's true, but it seems these are practical limitations, not theoretical ones.

The nice thing about the terminating case being a computer, though, is that it's a moving target (Moore's law, etc.). At the extreme case, a compiler could model every molecule in a human brain and use the simulated intelligence to convert the description into a language that it can compile.

I would be crazy to expect that any time soon, but I think it shows that in theory we can do better than existing programming languages do.

By the way, I re-worded the last sentence to "as long as programming languages are less expressive than written English, I'll keep welcoming them.", because I don't think it's inevitable that programming languages can become as expressive as natural languages. I do think that as long as they aren't, we can do better.

In my opinion expressiveness doesn't exist objectively. With that motivation for language design (achieving the expressiveness of English), I'm afraid you're running to a self-centered opinion; it is expressive only for those who have learned it since childs. The hierarchy of programming languages derives from the fact that expanding those languages is a lot of work (reimplementing the parser), in comparison with a natural one (metaphors, or neologisms). That's why, I think, a more general language (LISP, Smalltalk) is better. They don't give you expressiveness, which is only given by semantics, but at least they don't narrow those semantics. In comparison, English is a very ambiguous language which seems more expressive because it's semantics are huge. Which leads to the problem that, even if you built an artificial brain, you'd have to teach that brain ontology. Ultimately, the problem's root is not found within programming languages, but is an inertia to extend those which exist.

This ignores the fact that even if you explain quicksort to a random person and give them a list of a few thousand numbers they can only look at one at a time you will invariably find out that most of the people will get it wrong most of the time. Just because you think you can imagine the execution of an algorithm given its description doesn't mean any random human brain can; doesn't mean even you can, if pressed, executed a really complicated program without errors.

The error rates we get on modern computers are scary for most "algorithmic" problems.

> Real Information Theory, as opposed to Data Transmission Theory, has to take into account the receiver. The transmitter has to have a model of the receiver, and then devise the data that will transform the receiver according to the intent of the transmitter.

It seems that in general, for any two entities the level of the abstraction used for communication between them, should be the highest common level of abstraction that both of the two entities can operate in.

Take your example of the mathematician. If he is using an application that understands what a topological space or a mobius strip is, it seems then he can use those terms in the language that he uses to communicate to the computer.

Some computers understand what a Vector is. One can refer to vectors in the language used to communicate with that machine. For example a command like "multiply vector a and vector b" would seem reasonable. However if the machine is just a bare x86 box without any operating system, it will not "understand" what a vector is so one has to "talk" to it in terms of registers, memory and IO ports and so on.

This idea of course leads into DSLs. A machine can rise very high on the abstraction level scale today but the abstraction will be confined to a very narrow domain usually.

What you are describing is the ideal model teacher: Someone that adapts to exactly the highest level of understanding that the recipient is capable of thereby reducing the amount of information that needs to be transferred to a minimum (fastest learning) while still ensuring that the message arrives intact.

In comparison with a 3 year old as the subject (instead of a computer) the difference seems to be all in the ability of the recipient to absorb and apply contextual information.

English's 'information density' is mainly due to the inference ability of the target. A human being infers an incredible amount of nuance from words and the tone/context in which they are delivered.

Programming languages are formal specifications of instructions to a machine. They have to be incredibly deterministic/unambiguous because the machine does no inference of it's own. Even with a so called 'high level language' that handles a lot of under-the-hood stuff like memory allocation and garbage collection for you, there are no intuitive leaps. If you wrote the algorithm in English, but made sure to be rigidly unambiguous, you'd probably find the English version to be not so short.

I think what you meant was that there is a huge gap between spoken languages and programming languages, feature wise.

To make the argument more convincing, don't use English. The grammar is ambiguous. Lojban, a created language, is not. It is being used as a spoken language (though it's not very popular yet). Still, it is being used very differently from a computer program in a fundamental way.

One of the major issues is the concept of object definitions. Object-oriented languages have a very specific meaning for what an "object" is, while spoken languages do not. Rather than creating a specification for what data and functions an object contains, spoken languages group objects by properties. Ambiguity aside, it's a problem of whether you're defining it top-down, or bottom-up. Prototypes are closer to the way we use language for object definitions, but it's still not quite the same.

Another issue is how the language is used. A random portion of the source code is completely non-sensical to a computer, while a random paragraph of a book can still be meaningful. The portion of the source code could make sense to a programmer, maybe enough to reconstruct enough of it, but no computer can process it.

So, to go back to the original point, programming languages and spoken languages are both supposed to convey ideas. Spoken languages do a much better job, hands down. OP used length as a rough measure, but the idea is valid. The question is how can we make computers understand spoken languages in a meaningful way. Answer that, and you'll have a better programming language.

Reply on news.ycombinator.com