This is mostly in response to conversations I’ve had with Mark and Geoff about programming languages.

Probably most of my programming language research for the next while will be on Haskell. There are a couple reasons for this: Haskell is active, and being researched by a large proportion of the smart languages people in the world; Haskell is usable; and Haskell is very high-level, and I want to research very high-level languages. Most importantly, though, Haskell is ideological. It is purely functional, and unapologetically so.

A hand-wavy description of my research is that it deals with the compiler doing clever things by inferring semantics from program source. In an ideological language such as Haskell, this is made much easier. Haskell enforces referential transparency—every function behaves the same way, every time it is called, because it cannot rely on state—which means that functions can be reasoned about modularly. Rather than reasoning about the program as a whole, we can reason about just one function, because we know it is impossible—due to imposed ideology—for one function to influence the behaviour of another function. Ideological languages are easier to infer stuff from, and thus are more useful in research.

So, ideological languages like Haskell are fantastic—until you try to use them. For small examples, well-suited for writing in a functional style, Haskell is fantastic and elegant. But in any real-world application, you’re not going to program with Haskell so much as program against it. There are problems in computer science which, when described functionally, are awkward.

What I like about enforcing ideology more than anything else, is that it is a tool for a weak sort of development, validation, and testing. It’s long been said about Haskell that “if your program types correctly, it’s probably correct”. It’s less often said about Haskell that “it doesn’t come with a debugger”, but the two statements are really two sides of the same thing. Coding in Haskell is probably not much faster than coding in any other language, or even less frustrating. Coding in Haskell, however, shifts coding time and frustration from run-time to compile-time. Instead of spending 1 minute fighting with the compiler and 1 day debugging, you’re now spending 1 day fighting with the compiler and 1 minute debugging.

I see this as a win, and it’s the same reason I’m hesitant about the movement that’s been brewing in the parsing community for the past decade or so, away from LL(k) and LALR(1)/LR(k) parsers towards GLR(1) parsers. LALR(1) parsers are still the current standard in parsing. Writing a complex LALR(1) grammar is an exercise in frustration, of wading through parse tables trying to figure out exactly where your “2 shift/reduce conflicts” arose. Thus come GLR(1) parsers. With GLR(1) parsers, you can write any context-free grammar, and it will parse according to that. Write your grammar as naturally as you want, and you will get your parse trees.

The problem with GLR(1) parsers is the “s” at the end of “parse trees”. Using conventional parsing techniques, it is impossible to write an ambiguous grammar. With GLR(1) parsers, not only are ambiguities allowed, but sometimes even encouraged! Why fight with boggling shift/reduce conflicts and first-set conflicts when you can just deal with ambiguity problems at run-time? This is a shift in the opposite direction: instead of fighting for 1 day with the parser, and 1 minute in debugging, we’re encouraged to fight for 1 minute with the parser, and 1 day in debugging. This I see as a shift in the wrong direction.

At some point, after I write a program, I would like to feel secure that it works reasonably well. I would like to know that it’s not going to segfault, or throw an exception, or give ambiguous parse trees. With a strict and ideological approach, as with Haskell or LALR(1) parsers, this can be guaranteed. With Java or GLR(1), your confidence is only as great as your test suite, which will rarely be absolute. (Incidentally, I don’t think LALR(1) grammars are all that great. Probably we can come up with something more flexible, but I think always it should disallow ambiguity).

Back to the more relevant topic of why Haskell sucks, the two major problems with Haskell are that its compiled binaries are fairly inefficient, and that its ideology is awkward—arguably overly strict—for a lot of problems.

The first problem is one that I hope to address in my research. I think we must make a clean break between how a program is described and how it is run. The C90 and C99 standards both include talk of a “C virtual machine” (basically an abstract von Neumann machine); Java code is always thought of in terms of the “Java virtual machine”; and, accordingly, Haskell code is always assumed to be running on a “spineless tagless G-machine”—bonus points to Haskell for a cooler name. But, there’s little distinction made between these virtual machines being models for semantics versus models for execution. For languages like C, this distinction seems very silly: C programmers are infinitely wise, and it would be suicide for a C compiler to compile t->x++ into anything other than its obvious meaning, modulo some boring micro-optimizations like CSE and pointer caching and whatnot. For high-level languages, though, it is suicide to compile down to its obvious meaning. For high-level languages, we want to compile code down to anything but what the programmer has told us to compile it down to.

So the focus in programming language design then shifts away from describing how a program should run, and more towards what a program means. I believe we’re entering an era where a compiler can write better code than a human. Period. The definition of a compiler then shifts from “a tool which translates from one programming language to another programming language” into “a tool which translates a programming description to a programming language“.

It should seem obvious at this point that I’m biased towards functional languages. “Describing what a program means” is just a mealy-mouthed way of espousing declarative languages, and thus functional languages. The emergence of functional languages will be of limited impact, though, I think. Despite my research interests, my favourite programming language is not Haskell; my favourite programming language is C. C’s victory in my mind is not making a portable assembler, but for effectively projecting the elegance of the hardware. C is an accessible, usually clear, programming language, which displays the CPU to the programmer in its most elegant form.

What we should be looking for in programming language design is the ability to provide elegance to the programmer. I have Dijkstra’s definition of “elegance” in the back of my mind as I write this. Haskell is elegant for describing some types of problems; Java is elegant for describing other types of problems. The choice of programming language should, in a perfect world, have not be based on how fast your code will be, or what windowing toolkits are available, or any such nonsense, but strictly on how elegantly you can describe it. Further, the emphasis should be on how elegantly you can describe the problem, not on how well you can describe what you think the best solution is—again, the compiler should be smarter than you.

This is why I like ideological languages. They are elegant. When you start putting impurities into a language, you are saying “I think this language should be used to solve any problem”. You get Java and C++ and languages that your boss tells you should use. I think languages, which still staying theoretically general purpose, should be targeted at what’s natural for them to target. Not to advocate a return to domain-specific languages, but we have a few paradigms which have naturally fallen out: functional, logical, object-oriented, and scripting I see as the big four.

The reason I’m focusing my research on the first of those four is because of where research has pushed it thus far, nothing more.

Programming languages of the future should be ideological. In order for this to work, though, they must interoperate with other languages. In almost every language I’ve seen so far, “interoperate with other languages” means “interoperate with C”. Either that or we get into bizarre and complicated IDLs, which require pre-processing and much carnage. This is not good enough. This is also not an easy problem. How do you tell a C function that it’s getting a pointer to a lazy, possibly infinite list? Maybe C isn’t the language to do that. But there must be some imperative, pointer-arithemeticing language of the future that is. It would be high-level and allow the programmer to elegantly describe a good range of problems.

In summary, what we need from our future languages is:

  1. the ability to describe the semantics of the problem at a very, very high-level;
  2. an ideological elegance;
  3. an ideological strictness to aid in more statically-determined correctness; and
  4. the ability to pass off parts of the problem to another programming language.

This rant wouldn’t be complete without a mention of Lisp. Lisp, for those who aren’t familiar, is a programming language. It is the only programming language I’ve discovered which is literally better than every other language at everything. It’s also not terribly ideological. Lisp is an example of a very very good language, but I still think it fits into my rant. It’s not perfect. There are still things that I would rather do in some other language than in Lisp. Even the things that Lisp does well, they might be done more elegantly in some other language.

So, I love Haskell. I love its ideological strictness. Paradoxically, it would be less useful for me if it was less pure or less ideological, I think. I see Haskell as role model for future programming languages, and hopefully not just future functional ones.

Advertisements