John Lindal’s Blog

Lisp

While driving to work this morning, I finally separated out what has been bothering me about Lisp. Functional programming proponents tend to make a big deal about avoiding side effects because it avoids long range coupling between functions and it makes list iteration trivially parallelizable. This is good for program maintenance and effective utilization of all the cores in a CPU.

Side effects are eliminated by avoiding (1) global variables and (2) functions that modify their arguments.

Point #1 is relatively easy in any language (except assembly), but it does require discipline, since global resources like files and databases are in principle always directly accessible, even if an encapsulating interface exists.

Point #2 is very difficult/painful in strongly typed languages like C++ and Java but very easy in untyped languages like Lisp, Perl, and JavaScript, mainly because untyped languages make it very easy to return a heterogeneous list of values/objects.

This is what has been bothering me about Lisp in the back of my mind: a list is the most natural return value, both because the syntax is simple and because most standard functions operate on lists. A homogeneous list is fine, of course, but a list of heterogenous values is terrible because (1) it is hard to remember what is returned in each slot and (2) without compile time checks, modifying a function to insert a new value into the returned list creates a maintenance nightmare. You have to manually find and update every use of the modified function, and if you miss one, you have a subtle bug.

How can we avoid all this trouble? Using a map instead of a list alleviates the problems because (1) well chosen key names are easier to remember and (2) most of the existing uses of the function probably will not need to be updated because they do not care about the new value and the original values will still be accessible via the same keys.

Unfortunately, working with maps (or hash tables) in Lisp is a lot messier than working with lists. In Perl and JavaScript maps are part of the language syntax.

The Long Road to Hell

A friend just introduced me to Variadic Templates in C++0x. When will they admit that they just plain started from the wrong place? Their example of how to print a comma-separated list of arbitrary values, which is impossible in C++ without variadic templates, is so trivial in an untyped language that nobody would bother to discuss it.

Has it really never occurred to the C++ crowd that they should start with a loosely typed language and then add in an option for compile-time type checking? Objective C actually does this. A function parameter can be id, which means it accepts anything, or it can be a type, which means that it accepts that class or any subclass, or it can be a Protocol, which means that it accepts any class which implements the required methods. (Protocols also feature prominently in the new language, Go.)

The only flaws I can see in Objective C are (1) id only accepts objects, not primitives, and (2) constructors return id, so there is no type checking when an object is created. Java fixes the former this via autoboxing, but Java doesn’t have the concept of a Protocol and reflection is very painful.

One could argue that another flaw in Objective C is the lack of private functions. However, this can be solved the same was as in JavaScript: static functions, which are accessible only to other functions declared in the same source file.

Encapsulation & Polymorphism

Most programmers nowadays are educated with Java. As Joel discusses, this eliminates the need to teach many difficult topics such as pointers. Two topics that Joel does not dig into are encapsulation and polymorphism.

Encapsulation is the fundamental concept of Object Oriented Programming (OOP). In C++ and Java, this translates to objects encapsulating tightly coupled data and functions. However, since all messages between objects are function calls, it is very easy for tight coupling to creep in. This is why some people campaign against getters and setters: overuse can lead to tightly coupled data and functions residing in separate objects.

In addition, C++ and Java force concepts to be mixed together because polymorphism is implemented primarily via inheritance. Polymorphism boils down to different behavior in response to the same message. Coupling this with inheritance, which is merely one way to re-use code, requires programmers to either get stuck in a straight jacket of single inheritance or go hog wild with mix-in interfaces. The latter is better, but it can still get very confusing.

To see encapsulation and polymorphism clearly, it helps to consider other implementations.

The purest forms of encapsulation occur when the boundaries are strongest: interacting processes on separate machines, e.g., web services or XHR/JSONRequest. In this context, interaction requires network traffic, and efficient systems strive to minimize this. Interestingly, this does not lead to minimal interfaces such as what you find in C libraries where each function does one small, simple operation. Instead, each interaction accomplishes as much as possible to minimize the network traffic. Getters and setters are non-existent, except in special cases when that is all that is required.

The purest forms of polymorphism occur in weakly typed languages. Objective C allows any message to be sent to any object. If the object does not implement the message, it can either delegate it to another object or throw a run-time error. The same is true for JavaScript, Perl, Python, etc., though language support for delegation varies.

How can we apply this to C++ or Java? Since encapsulation is weakly enforced by the language, it helps to encapsulate functionality, i.e., modules, instead of individual classes. Modules are much less likely to need getters or setters. Instead, they normally expose higher level actions. Messaging frameworks similiar to Objective C can been built in strongly typed languages, e.g., signals-and-slots or JBroadcaster, but it typically requires manually writing or automatically generating dispatching and receiving code.

Along with questions about pointers and functional programming, digging into a person’s understanding of encapsulation and polymorphism makes for a good technical interview.

C++

Lots of smart people hate C++, but I cannot get myself to agree. It’s true that C++ is vastly more complex than C, but this complexity can be managed. When managed properly, the additional features of C++ are very powerful extensions to C. Because one must be careful, many people seem to feel that Java is much easier, but that is really a people problem. Bad programmers can write spaghetti in any language.

Let’s examine the alternatives to C++. Java is the closest one. I believe it has everything C++ has. It also has garbage collection. This beats manual memory management hands down. Garbage collection enables usable exceptions. Java generics are definitely easier to use than C++ templates, but I feel that this is mostly due to the system linker still being in the stone age — though there is virtue in simplicity. Java also has reflection, which is way beyond the primitive RTTI support in C++: dynamic_cast and type_info. But the reflection API is bulky and very tricky to use with generics. In a strongly typed language, it is best to avoid the need for run-time type information and rely instead on polymorphism. Also, Java comes with a huge run time, the JVM, and this does not run lean, though the need to package it with your program has thankfully disappeared on many platforms.

Another class of alternatives is weakly typed languages such as JavaScript, Objective C, Perl, and Python. These are wonderful for smaller programs. Their expressiveness is much higher than C++, so the source code is much shorter. Since they are weakly typed, polymorphism does not rely on inheritance. You can invoke any method on any object. The cost of this flexibility is that everything is a run-time error. There is no way to know whether or not a call will succeed. In the worst case, it depends on the state of the program when the call is made, so you must have integration tests (not units tests) that exercise every conceivable code path. As with C++, this complexity can and must be managed, but unlike the static complexity of the C++ language, this complexity is dynamic, so it grows exponentially with the size of the program.

Given the alternatives, I think that C++ still has a place, just as C does. When C++ does make sense, it is always worth asking whether Java is a better choice, but I do not think the answer is always yes.

Update (10/18/2009): After reading this post and remembering some of the features of C++ that I suppressed after reading Meyers’ Effective C++, I have to admit there is much to hate about C++. The only explanation for why it doesn’t bother me day-to-day is that I am using a very carefully selected subset of the language. I’m certainly using more than 20%, but all of what I use, I use in moderation.

YUI 3

I finally got a chance to study the API for YUI 3, and it is beautiful. I can’t wait for them to port the widgets from YUI 2!

The Unknown OS

Before the internet, everybody always worried about getting their desktop applications to run on multiple operating systems. If it ran natively on Linux, Mac, and Windows, it was a marvel. Nowadays, everybody worries about getting their web applications to run on multiple browsers. If it runs equally well in Firefox, IE, Opera, Safari across Linux, Mac, Windows, it’s a marvel.

But there is another, virtually unknown OS, exclusive to Unix: the window manager.

Getting a Unix desktop application to work correctly across the myriad of window managers (AfterStep, blackbox, Enlightenment, fvwm, icewm, Metacity, OpenStep, Sawfish, WindowMaker, XQuartz, etc, etc, etc.) is almost impossible since each seems to have its own unique ideas about how to position decorated windows. There are thankfully some standards, but not all window managers support these. Some do their own thing, while others support older standards. Metacity on Eeebuntu doesn’t make the window a child of the frame. Sawfish on my version of Eeebuntu locks up when it receives a _NET_WM_DESKTOP client message!

In addition, getting a Unix application to interoperate with all the various desktop environments (CDE, Gnome, KDE, XFCE, etc.) is also pretty much hopeless. When I tested an edge case in the reference implementation of XDND against Konqueror in Eeebuntu, it was almost impossible to get the reference implementation to accept the drop from Konqueror. When I tested the default file manager in Eeebuntu, it accepted files dropped via XDND, but it did not use XDND when dragging files!

No wonder so many people stick to Windows…

Update: Further testing reveals that Konqueror only seems to send a single message to the target window instead of a continuous stream as the mouse moves!

The Joy of Hacking

I’ve spent quite a bit of time over the past couple of years writing layout managers in JavaScript. If you happen to have access to Yahoo! APT, then every time you resize your browser window and everything expands or shrinks to fit the available space — that’s mah baby. I sometimes joke that the layout manager is going to put my daughter through college, because it’s on version 3 already and my next project is version 3a. But I digress…

All sizes in version 3 are percentages. This keeps the math and the configuration simple. (Version 2 let you use any unit, %/em/px, and it was a bear.) Recently, somebody asked if it would be possible to mix in fixed size elements. After thinking about it, I realized that I could treat fixed size elements the same way that I already handle collapsed elements, since collapsed elements are a (small) fixed size. A long day and a few judiciously placed statements later, and it works!

And the really cool part is that instead of making a complete mess of the configuration by introducing units, I simply added a keep your grubby paws off this element flag. The element’s size can then be set via CSS, the good old-fashioned way

Erlang Message Passing

I’ve only just started learning Erlang, so I certainly don’t know all the tricks, but when I found a blog post claiming that message passing between actors made deadlock less likely, it got me thinking. A classic deadlock occurs when A and B both want to aquire locks X and Y, and A gets X while B gets Y. In Erlang, it seems that the equivalent can happen if A is waiting for a message from B while B is simultaneously waiting for a message from A. Message passing is neat, but concurrency is still just plain hard

On the subject of message passing, I’ve noticed several libraries for implementing message passing in Java, but they all seem overly complex. A simple base class which manages a message queue for each actor should be sufficient. The only public API is the function to send a message and functions for telling actors about one another. All derived class functions should be private, protected, or at worst package-public.

Of course, you also need some discipline. The messages must be send-and-forget. Once a message has been sent, the sender should discard all references to it and everything inside it. Otherwise, you are back to standard shared objects which require locking.

This produces a system where all state is stored in messages. State can only be modified by the single actor which has a reference to it. I doubt if everything can be implemented this way, but it is a good exercise to try!

I’ve posted the code on github

JSLint

On the advice of my esteemed colleague, Eric G., I tried JSLint recently, just for kicks.

I’ve never been a big fan of lint programs, since in any sane language, if it compiles, then the syntax is valid, and the important bugs require execution, not static code analysis.

While JSLint did find a couple of minor issues, I had to wade through a sea of “unnecessary semicolon” messages to find those issues. WTF? This is JavaScript, the language that finally managed to make programmers paranoid about semicolon placement. In any other language, if you miss a semicolon, the compiler will complain, but JavaScript is practically a random semicolon generator. If you miss one, anything could happen: it might work, it might crash, or it might launch a nuclear strike against Albania.

So I didn’t get my feelings hurt. Instead, I concluded that JSLint isn’t any more useful than any other lint program, despite JavaScript being insane.

Programming Languages

Hex is like starting with Carbon, Hydrogen, Oxygen and Nitrogen to evolve sheep to get wool to make clothing.

Assembly is like starting with some basic, biological molecules, but you still don’t have RNA or DNA. You still have to evolve sheep to get wool to make clothing.

C is like raising sheep to get wool to make clothing.

Java is like using a loom to weave cloth to make clothing.

Your favorite framework is like using a pattern to make clothing.

But most people just go to Kmart, or Gap, or Macy’s and buy clothing because they don’t care about how it’s made. Even starting from a pattern requires knowing how to use a sewing machine.

So now you know why most people click the e to get to Google and then type AOL to read their mail!