Supervisor trees

In my past few posts, I have focused on fault tolerant distributed systems as implemented through cluster managers. Apache Mesos, Kubernetes, and many others all attempt to support fault tolerance by auto-restarting and other self-healing techniques at the cluster manager level. As such, they rightly claim that they are the new operating systems of the cloud. It turns out, however, cluster managers certainly do not have a monopoly on fault tolerance features. Long before Mesos, Kubernetes, and possibly even University of Wisconsin's Condor, a distributed processing system with considerable more pedigree, Erlang had supervisor trees and supervisor behaviors (a kind of language interface) in the runtime thus supporting large, highly fault tolerant distributed systems decades ago.

Experimental Human Factors Take on Functional Programming

As a functional programmer, one often takes the productivity advantages of functional programming as an article of faith: Versus imperative and object-oriented counterparts, functional programs must be shorter, more robust, quicker to develop, and easier to maintain. Designers of programming languages and compilers harp on the supposed benefits of their languages and implementations. But when it comes down to it, where is the evidence? There is admittedly a lot of problems when forming a rigorous question and experiment to compare languages. An empirical study is even more difficult because there are really few large software systems that are implemented equivalently in multiple languages. Still, there turns out to be a few studies on the productivity and usability side of functional languages and mixed paradigm languages (e.g., Pankratius et al's "On the Benefits of Combining Functional and Imperative Programming for Multicore Software"). The results appear to be quite consistent: functional programs are shorter but they aren't any quicker to develop for even relatively skilled programmers. Performance is generally found to be on par. Moreover, fancy type systems have the disadvantage in that they could complicate the programmer's understanding of the program and prolong the debugging process.

C++ Parsing Gotchas

C++ is a complicated language. Even just parsing the language is troublesome. Scott Meyer included the most vexing parse as part of his Effective STL book (Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library ). Recently, I encountered another parse issue that ultimately warranted new syntax in recent C++ revisions: the dependent type parse. The idea is simple, type names and value names (i.e., functions or variables) may overlap. That is to say, one might have a type t and a function or variable t in the same namespace. Thus, the parser has to disambiguate. This potential overlap comes up when parsing dependent type names (e.g., set<T>::iterator). Specifically, when declaring a function with a dependent type parameter such as void f(set>T<::iterator I), the compiler will complain that the keyword typename must be inserted in front of the whole dependent type name. Thus, void f(typename set>T<::iterator I) compiles.

What C++ parse gotchas have you encountered?

Compiler Intermediate Representations

Recently I have been studying up on various intermediate representations for compilers. Heads and shoulders above the rest in popularity is of course LLVM. Interestingly, the more I read about and work with LLVM, the more I see the parallels with the FLINT intermediate representation used in Standard ML of New Jersey (SML/NJ). One of LLVM's key features is the so-called language-independent type system. This type system enables overloading of LLVM instruction opcodes to keep the instruction set small. The type system is also supposed to help debug optimizers. At least in terms of this application, FLINT's typed intermediate representation was also intended to help debug optimizer phases.

Apart from garbage collection, the other common facility intermediate representations and virtual machines must support is exception handling. LLVM supports exception handling and other forms of non-standard control flow through something evocative of delimited continuations in the form of two instructions invoke and unwind.

High-Level Programming Languages for Embedded Systems: Garbage Collection and FPGAs

Just when it looked like the big guys (well, basically Apple, that big chunk of the NASDAQ) were moving away from tracing garbage collectors, researchers from IBM Research has taken the leap to bring garbage collection to FPGAs [PDF]. Though hardware-assisted garbage collection isn't new, this degree of implementation of a complete concurrent garbage collector on an FPGA is. The authors consider this a first step in bringing high-level languages to the FPGA and embedded computing realm. It should be interesting to see where this goes.

JavaScript Anti-Patterns

An unfortunate side-effect of JavaScript becoming pretty much the most widely used programming language of all time is that the community has expanded in such a way that there is a lot of bad advice going around. The distribution of skills in JavaScript programmers likely varies widely (anyone have any hard data on this?). The more I study JavaScript JITs and the community, the more I realize that JavaScript is truly the assembler of our time. The big catch is that back in the days of assembler, you didn't have millions of inexperienced people putting out code.

The problem is this. So-called JavaScript patterns nearly all have to do with micro-optimizations. So many micro-optimizations have turned into folklore in the JavaScript community. Due to the inefficiency of early JavaScript interpreters, things such as hoisting array range/bounds checks have become quite widespread. If all these micro-optimizations actually made things better, no one would question the whole endeavor. However, I dare say that most beginning JavaScript programmers don't have a good handle on all the caveats and provisos which come along with each of the micro-optimizations. Micro-optimizations are being marketed as something that will always make your code faster and implicitly never breaking code. This is how beginners will understand micro-optimizations. This is unfortunately quite a bit removed from the truth. Optimizations have provisos. Modern JITs are actually quite good at squeezing every little bit of performance out of JavaScript code. It those cases where a construct cannot be optimized in general, it may be due to a lack of information, especially domain knowledge, on the part of the JIT compiler. But when the compiler doesn't optimize, the programmer cannot blindly optimize either. In the range check example, the programmer must be certain that the body of the for loop does not modify the size of the array. If this weren't the case, then checking the array length just once won't cut it.

for (var i=0, len=arr.length; i<len; i++) {
  console.log(arr[i]);
  arr.pop();
}

The above code will print out a lot of undefineds. Leaving the range check optimization to the JIT compiler would avoid this error. Fortunately, threading is not in JavaScript. If your typical JavaScript program were multi-threaded, this so-called optimization may cause even more deleterious behavior since the value of the property arr.len is no longer clear from looking only at the body of the loop.

Formal Semantics for Top 5 Programming Languages

A recent blog post on undefined behavior in C got me thinking. Being from the ML community, I have a certain appreciation for rigorous formal semantics that can be machine checked. Though practical machine checking is largely a new development, rigorous formal semantics has been with us for decades. Standard ML is the epitome of this approach to language design. The 48-page (128-pp total when including appendices and TOC/index) The Definition of Standard ML - Revised formally specifies the entirety of the language¹. Don't get me wrong. The Standard isn't perfect. Indeed, it has some bugs of its own [PDF]. Nevertheless, for the most part, the Standard has raised the level of discourse and enabled succinct yet precise descriptions of a powerful higher-order typed language possible. This approach to modeling, defining, and evolving programming languages has in recent years taken a life of its own having been applied to both new experimental languages as well as time-tested existing languages.

The Scala Ecosystem

Scala certainly has a lot going for it these days. They have the enthusiasm of at least a couple of the hottest tech companies out there in Twitter and Foursquare. Even Sony is using Scala in some of its systems. There are at least two fairly usable web frameworks, Lift and Play. Akka middleware provides a scalable lock-free concurrency abstraction. XML support is built-in. Interoperability with Java is standard, thus giving Scala access to important systems and APIs such as Hadoop, JSoup, Mahout, Pig, and the numerous Apache Java projects. There is even a linear algebra package Scalala. What is going to take it to the next level?

I've read posts about people recommending Python over Ruby due to the comprehensiveness of the platform given Scipy/Numpy/matplotlib and Django. Ruby, of course, has Rails to really turbocharge its audience. Objective-C remains the lingua franca of iOS due to fiat. The interesting observation is that the software development world has become very diverse. The proliferation of web services certainly helped because instead of having to interface with binary libraries and structured foreign function interfaces, new languages and platforms only have to interface with HTTP, XML, and JSON to achieve harmony with the Web 2.0 ecosystem. This lowers the legacy compatibility bar for new programming languages considerably. Considering how difficult developing good foreign function interfaces and runtime support for mediating between garbage collected (aka managed) languages and the previous lingua franca C was, this must be quite a relief to language designers. However, harmony with Web 2.0 isn't enough to achieve widespread acceptance.

Garbage Collection in JavaScript, Part 1

A recent post on Scirra claimed that reusing long-lived objects was an ingredient to good JavaScript garbage collection behavior. That made me curious. This claim is generally true when the garbage collector in question is a generational one. Generational garbage collectors split the heap (memory from where all non-stack allocated things are allocated from) into several "generations". The "generational assumption" is that short-lived objects tend to be collected more frequently than long-lived objects in the heap. Upon each garbage collection, any objects which aren't collected can be promoted to the long-lived generation. The idea is that by running garbage collection less frequently on longer-lived generations, garbage collection can feel more responsive.

The problem is that generational garbage collection isn't universal. It isn't the most responsive form of garbage collection or memory management either (concurrent and incremental garbage collectors are more advanced and optimized for realtime/low-latency applications). Furthermore, although generational garbage collectors for the major browsers are in the works [Firefox, WebKit/Safari], it appears that currently only Chrome deploys one in the release browser. In fact, Chrome V8 cites generational collection as one of the main features of V8 enabling high-performance JavaScript. Around 7/20/2012, Mozilla added an Incremental Garbage Collector to Firefox 16, which reduces GC pause times by incrementalizing collection rounds, but this says nothing of and does not rely on the generation assumption. In Lisp (the first implementations of "generation" garbage collectors by Lieberman and Hewitt [PDF] and Moon [PDF]), Smalltalk (one of the first languages with generational collectors [David Ungar's paper Generation Scavenging: A Non-disruptlve High Perfornmance Storage Reclamation Algorithm, PDF]) and the higher-order typed language work (Haskell, OCaml, Standard ML, etc.), we have been using generational collectors for quite a while.

The Scirra post suggests attempting to avoid garbage collection, but that is a very tricky matter. I think the realtime performance of such an approach would be very sensitive to the design of the garbage collector and any related heuristics. Moreover, if JavaScript interpreters move beyond generational collectors at some point, programming styles exploiting the generational assumption won't have the same payoff as before.

Continue to Part 2 in this series where I introduce profiling and benchmarking features in the Chrome V8 garbage collector.

Academic Programming Languages in Mainstream Use

It is said that once a programming language is born, it never really dies. That may be so, but popularity can still be a fickle thing. I think it is safe to say that most academic programming languages never make it out of the lab in a serious way. However, there are a few prominent exceptions to this observation, some of which were and are wildly successful: