Daniel's Blog

Complexity and the Engine of Evaluation

Posted by Daniel Lyons Tue, 12 Aug 2008 17:23:00 GMT

So we find ourselves up against complexity itself, again.

Prolog, which I used the other day, is essentially abandoned. Paul Graham said it best:

“If high-level languages are better to program in than assembly language, then you might expect that the higher-level the language, the better. Ordinarily, yes, but not always. A language can be very abstract, but offer the wrong abstractions. I think this happens in Prolog, for example. It has fabulously powerful abstractions for solving about 2% of problems, and the rest of the time you’re bending over backwards to misuse these abstractions to write de facto Pascal programs.”—“Programming Languages Explained,” Hackers and Painters.

Interestingly, this is a problem Haskell shares a problem with Prolog: it’s very hard to control the order of evaluation. Of course, they both do what they can to ameliorate the situation. Prolog offers you the cut operator, and Haskell offers you quite a bit more: monads, do notation, unsafePerformIO, some interesting tracing functions, strictness annotations, etc. Will it be enough?

Consider the people using C++; some use just the templates, others use it as C, some try to use it as an OOP language. The language encompasses all of these communities. Natural languages are vast for the same reason. Is this a positive attribute? Does it take a complex programming language to have a large and thriving community? Recent examples seem to indicate so.

One problem with Prolog is that, apart from the novel evaluation mechanism, there isn’t a whole lot to recommend it. You get most of the same features in Lisp, but LIsp has a lot more other features. And, as Paul Graham and Peter Norvig attest, it’s famously easy to implement the unification algorithm in Lisp: have you cake and eat it too.

Haskell has a lot more than just laziness going for it. It’s the flagship of the FP world. The type system is shockingly impressive and fairly complicated by itself. You could have that without the laziness. Haskell has more than one appeal. No wonder its audience is larger and expanding. These days we expect languages to implement themselves. Imagine what it would be like to implement Prolog in Prolog, versus Haskell in Haskell.

Look at cool term rewriting systems, of which there are really only two worth talking about (Pure and its ancestor Q). They certainly have their appeal. But this also boils down to a fundamentally different engine of computation. Declarative logic programming seems to have found a niche in database querying and occasionally template expansion (XSLT). What will term rewriting’s niche be?

I’m not sure what people really want, or what I want. We seem to be pretty happy with a procedural view of things, with the occasional departure into declarative-land when querying databases and the occasional departure into functional-land when dealing with collections. We like polymorphism, we like sharing code, but this-then-that seems to be the only evaluation strategy we like. So we see laziness as libraries or corner cases for lots of languages—Lisp has SERIES, Q and many Schemes have lazy lists but very few people use Haskell or lazy Scheme. The story is the same for parallelism. People using Erlang make lots of use of it. Everyone else does not. But people seldom think to use Erlang to solve their problems, thinking they don’t need to the parallel features to solve a problem, preferring their native tools.

There is a sense that learning and then using an obscure language like Prolog to solve a tiny problem somehow adds complexity before you even start. Is that true? If only complexity could be quantified. It’s true that the I/O in my last post’s code was ungainly and a little gross, but it wasn’t especially complex. A lot of people would have stuck to the language they know, Ruby for example, and implemented a whole search method in it. Is that better or worse?

There’s something repugnant about these questions. Why are languages so hard to interface without becoming soulless CLR/JVM parasites or tiny portals sending and receiving strings? Why is it so hard to have a polyglot system? Yet, on the web we have a very pluralistic society down to the technology level, yet all the options in all their diversity suck?