Artisan Coder

While I wait for my 1-hour mobile phone software compilation to finish I decided to drop a quick post about something that has been on my mind lately. In his nice PhD thesis (that I had to read five times to finally understand it), Dybvig (the implementor of Chez Scheme) shows a compiler that rewards the pure functional use of the Scheme language. The compiler scans for free variables in lambda forms and, when creating the respective closures, put the values of the variables directly in the closure activation frame. The references to the free variables in the closure are then changed to references to the stack locations. Accessing the variables is then pretty fast. Besides, when a first-class continuation is created, it suffices to blindingly copy the execution stack because all closures will carry their free variables with them. Assignment is then added at a later section of the thesis. To support it the compiler scans the code for set! forms, gathering the variables that are ever assigned, and compiling them to indirections to heap memory. When a continuation is created the indirection box is copied, not the actual variable, which lives in the heap. So access to assigned variables is much slower.

Although the focus of Dybvig’s thesis is not on concurrency, I cannot help but think that his compiler could work very well for this too with just minor modifications. If variables (local or free) are never assigned, they could be replaced by their values and several different threads with different execution stacks could run in parallel. If a variable is assigned, the access to its indirection box could be protected by a mutex or similar synchronisation primitive. Of course this would make access to assigned variables even slower, because even variables ever used by only one single thread would need mutex lock/unlock operations. On the other hand, isn’t assignment discouraged in Scheme? The overall execution time would compensate for this, if the rest of the program was parallelised.

But surely I am missing something, because no one ever seems to think Scheme can be a contender in the massive-parallelised future. What bugs me is that I don’t know what it is that I am not taking in consideration.