I always carry a book in my backpack so I have something to do while sitting on the bus, the subway or in a waiting room. It took me almost a year to read this one, but I was determined to get through it. I wanted to know more about the mythical figure that is Alan Turing, often cited as the father of computer science. I’ll begin by saying that Alan Turing: The Enigma is a remarkably well-researched book, with all references provided for the reader. It’s obvious that many years of work went into its making. The author, Andrew Hodges, is a mathematician, which makes him particularly well-placed to discuss the many creative ideas of Alan Turing.
The book of course discusses in detail Alan Turing’s seminal On Computable Numbers paper, as well as his involvement in the breaking of German cryptography (and the Enigma machine) during World War II, but also paints a very intimate and human picture of Alan Turing, a picture which includes character flaws and vulnerabilities. Alan Turing was an introvert, a man of few friends, stubborn, often dismissive, and probably quite lonely at times. He seems to have struggled to understand societal norms, and had the boldness (or perhaps foolishness) to be quite open about his homosexuality decades before it became acceptable to do so. His eventual fall from grace is a cruel tragedy which he never saw coming.
This book also reveals many interesting facts about Turing’s life. Contrarily to what I had assumed based on my introduction to Turing Machines in computer science classes, Alan Turing was not just a pure theoretical mathematician. He was also interested in relativity and quantum physics. He dabbled in chemistry as a hobby. He understood electronics well enough to design complex analog circuits, and was capable of using a soldering iron to assemble them as well. Alan Turing also had a crucial role in the design of an actual digital computer: the ACE (Automatic Computing Engine). Finally, while working at the University of Manchester, Turing had the opportunity to program a working computer to test theories about morphogenesis (his last published works) in simulations.
I would recommend this book to anyone who’s curious to know more about Alan Turing, or just interested in reading a good biography. If you’re cheap like me, you can acquire this book used on Amazon or AbeBooks for only a few dollars after shipping.
I own a small Revlon branded makeup mirror with a lightbulb and reflector inside. I find it fairly convenient as I can apply makeup while sitting at my desk and listening to music or watching videos online. Unfortunately, it has issues. It’s not very bright, and so doesn’t really give you an accurate image of your finished look. It also generates a fair bit of heat, which makes it uncomfortable to use in the summer. Recently, I found out that there are 12V LED light strips of many colors available on eBay for cheap (usually less than $10 for a 5 meter roll, that’s about 15 feet). I figured that with a cool-white LED strip, a little dimmer switch, some wire, some glue, and a source of 12V DC power, I could turn the vertical wall mirror I own into a giant lit makeup mirror.
I acquired a 5 meter cool-white LED strip with 300 LEDs per meter. The LEDs are of the “5050″ variety, which are a bit more expensive but much brighter than the alternative “3528″ kind. The total cost of the strip after shipping was about $9. The dimmer I bought is a digital part, that is, it controls brightness through pulse-width modulation (PWM), and is specifically made for 12V LED systems. I found it on ebay for less than $2 shipped. The total cost of all the parts for this project, including the glue and wire and clamps, is about $30. It’s important to note though that I still have leftover LED strip, glue, wire and of course the clamps to use on other projects.
Once the strip segments were glues down, I soldered wires in the corners of the mirror, connecting the strips to each other, and also to the dimmer. I applied epoxy glue over the connections to solidify and insulate them. I also added a long wire at the back of the mirror, which goes from the dimmer’s input to a female DC power jack, the kind one would connect to a typical wall-wart power adapter.
Assembly was more time-consuming than I expected, it took me about 4 total hours of work, and was done over 3 days, since I needed to leave time for the glue to solidify. I started by drilling a hole on the side so I could make the power input wires of the dimmer go to the back of the mirror, I then glued the dimmer over this hole. The second step was cutting the LED strips to length. These can only be cut every 3 LEDs, and so it wasn’t possible to make them go exactly all around the mirror, covering the whole perimeter, I needed to leave gaps, and connect the multiple pieces of strips with wire.
The LED strips found on eBay have an “auto-adhesive” backing, you’re supposed to be able to just peel off the protective tape, and stick them to things. In my experience, this adhesive backing is very much worthless, the strips will peel off immediately, and so some other kind of glue is needed. I decided to go with epoxy, which is sold at the dollar stores here. I also purchased two adjustable clamps to hold the strips in place while the epoxy solidifies. Epoxy glues have several advantages: they solidify quickly, the resin they form is extremely solid, and they are not electrically conductive. In my experience, epoxy can solidify in as little as 15-20 minutes.
The total power consumption for the mirror, when on maximum brightness, is less than two amps. I hooked it to the 12V 15A DC power distribution box I already built for other LED lighting shenanigans. Your bedroom probably doesn’t come with one of these, but fortunately you can get by with a good old 12V 2A DC wall-wart, which you can find on eBay for about $5 shipped. Just make sure to get one that fits your country’s electrical outlets.
The finished product, once wired up, can put out quite a bit of light: about 3000 lumens, which is more than a 100W incandescent lightbulb. Fortunately, the dimmer allows tuning down the brightness to the point where you can look at the LEDs directly without visual discomfort. I usually just leave it on maximum brightness, however. I’ve found the lights are not blinding if you get up close to the mirror to look at your face. The cool-white color also seems to have a pleasant daylight-like glow. I’m actually considering buying more of this strip just to make my bedroom brighter.
I submitted a conference paper to Compiler Construction 2014 (part of ETAPS) just two weeks ago. This paper details my recent work on compilation with the basic block versioning algorithm, an alternative to tracing. This work was briefly explained in my DConf 2013 presentation, as well as the talk I gave at Strange Loop, which should hopefully be made available online on InfoQ within a few weeks. I unfortunately won’t know if my paper makes it into CC 2014 until mid-late December, but in the meantime, while keeping my fingers crossed, I’m already planning the third iteration of the Higgs JIT compiler.
Basic block versioning can compile multiple versions of a given basic block based on context information (e.g.: type information) accumulated during compilation. It’s a formalized algorithm for tail duplication which allows a compiler to eliminate type tests, hoist type tests out of loops, and duplicate code paths where multiple types are possible at run time. This approach is similar to tracing JIT compilation in that, like tracing, it’s preoccupied with accumulating type information along linear sequences of code, and using this accumulated information to specialize code farther along, with the important difference that we’re working at a lower granularity, that of basic blocks, instead of traces. I believe that the paper on basic block versioning my advisor and I submitted is an original and interesting contribution, but I’m not stopping there, I already have many improvements planned.
The next iteration of Higgs will try to solve this problem by moving away from method-based compilation. The new Higgs JIT will lazily and incrementally compile functions one basic block at a time. Parts of functions that are not executed will never be compiled. I intend to push this approach further, and inline function calls incrementally as well, which means that in many cases, only small parts of functions will actually be inlined. There is significant potential for compilation time savings. There is also the potential for making better inlining and optimization decisions, through smart use of profiling during incremental compilation. Basic blocks, when first compiled, can be made to collect profiling information. These same blocks can then trigger recompilation later to produce more efficient code.
Won’t incremental compilation result in a horrible mess of machine code, you ask? I devised a scheme where blocks can be recompiled, garbage collected and relocated so as to make the machine code more efficient. I won’t get into all the details just yet, but I’ve started examining the technical challenges and I’m quite convinced this is possible. Not only is it possible, it will mesh with basic block versioning in very interesting ways, and open up many possibilities. As far as I know, Higgs is going to be the first compiler to feature incremental lazy compilation of functions and incremental inlining (if anyone has references to prior art, please let me know). Even if Higgs isn’t the first at this though, the combination of lazy incremental compilation and basic block versioning will make it a truly unique beast.
A special thanks to Marc Feeley, Paul Khuong, Luke Wagner, Benjamin Cerat, Tom Brasington and Erinn Di Staulo for helping me review my CC 2014 paper prior to submission.
There’s an amazing variety of electronic and microcontroller parts on eBay, and they’re amazingly cheap. A little while back, I found out that you can get 5 meter (15ft) rolls of color-changing LED strips from China for less than $10, shipping cost included. These are flexible strips with RGB (red-green-blue) LED lights placed at regular intervals (usually 60 per meter). They are made to light up indoor spaces and produce quite a bit of light at about 800 lumens per meter, about half of what a 100W incandescent bulb puts out, meaning you could conceivably light up a room with one or two 5 meter rolls.
What occurred to me was that these LED strips are flexible and light enough that they could be installed on clothing or accessories. They are extremely bright, and the ability to change color rapidly could make for a very interesting display, especially say, if the lights pulsed along with music. Coincidentally, friends visiting from out of town invited me to join them at the Bal en Blanc (White Ball), a huge rave party happening once a year in Montreal. I decided to try and build something extravagant to accessorize my outfit. My idea was simple: glue LED strips around the sole of a pair of running shoes and have some kind of beat detection to make them flash to music.
There were a few issues to overcome, however. For one, the LED strips run off of 12V, while the microcontroller I wanted to use for beat detection runs on 5V. The LED strips also draw quite a bit of power (around 2 amps at peak intensity for the length I was going to use). This means that if I were to run this setup off of say, 9V batteries, I could only expect about one hour of light. I was able to find a suitable battery on eBay: a 4800mAh rechargeable lithium-polymer battery pack intended to serve as backup power for security cameras, only about $17 shipped. Powerful enough to last through the 8-12 hours of a rave party (you can totally dance that long without drugs, right?). Unfortunately, this battery pack was clearly much too big to fit on shoes.
I decided to go for a simple solution, which was to wear the microcontroller and battery on a belt, and run cables through the legs of my pants. I lucked out and found a pair of generic white sneakers on sale for $10 at Payless. I installed connectors on the shoes so I could easily disconnect the cables when I wanted to take the shoes off, and glued the strips to the shoes using a hot glue gun. The strips can be cut to the desired length every 3 LEDs.
For the controller, I tried both an off-the-shelf music-reactive controller, and also built my own using an atmega8, a simple preamplifier circuit, and some 2n7000 MOSFETs. The off-the-shelf controller seemed to behave well in my living room, but worked terribly in a club setting, where the volume was much louder and there were lots of people talking/shouting. It basically would hold a solid color and not react to the music anymore. The controller I built used relative measures to try and adapt to the ambient volume, and only sampled the sound a few hundred times per second, so as to use low-frequency (bass) information only.
The shoes were very bright and got me lots of compliments. Unfortunately, they didn’t quite last the whole night. The hot glue wasn’t strong enough, and after a few hours of dancing, the LED strips started coming off the shoes. If I ever do this again, I’ll probably use epoxy to glue the strips instead, and possibly cut the strips at the middle of the shoes and connect the two parts with flexible wires. The strips don’t bend very well from side to side, and I suspect this contributed to them coming off faster, as the shoes need to bend in the middle when you walk or dance.
In the meantime, I’ve begun designing a new project in the same vein. It’s going to be a glove with an LED strip and an accelerometer that can sense your movements. The big advantage here is that you’ll be able to control the lights directly with your dancing, possibly even specific gestures. This has the nice added benefit that it circumvents all the complexities of beat detection, which is hard to do properly and often unreliable. I’m also thinking of installing a large 10W RGB LED in the palm (like a rainbow rave version of Iron Man’s weapon). My tentative name for this project is the Power Glove.
I recently got to thinking about the future of programming. I believe that as systems grow ever more complex and networked, we’re headed for a future where programming won’t be about editing code in text files, compiling them, and restarting programs (wash-rinse-repeat), but rather, incrementally building live systems, and performing microsurgery on running programs, without interrupting them. As we work on ever bigger systems, we’ll need all the debugging help we can get, and type systems sure would come in handy, but there’s just one issue with that: I think that static type systems, and type inference as implemented in languages like Haskell won’t work so well with such a model. I think the truth is that dynamic languages are much better suited to the incremental, organic model of software development we’re getting pushed into. Dynamic languages are here to stay. They’ve been gaining in popularity, and this trend isn’t going to reverse, it’s only going to grow stronger.
Imagine you’re working on a live system. You’re modifying the code for a program that’s currently running on some remote server. Now imagine this system is statically typed. You want to make a change to a method somewhere, but unfortunately, this small change would cause a type error. You need to modify several other functions elsewhere in the system, as well as schema/record declarations. The statically typed approach would probably involve making all of your code changes, changing the schema declarations, running some kind of type inference algorithm, verifying that everything checked, and then running some sort of “commit” that recompiles the needed code on the remote machine and translates your records to the new format, probably interrupting the program while this is happening (and who knows how long this might take, could be hours). The big issue here is that with current static type systems, you can only go from one statically valid program to another statically valid program, which seems poorly suited to the incremental modification of a running system.
The dynamically typed approach approach might be to write code to handle the new schema before it’s even introduced, then run some code to translate from the old schema format to the new (all on-the-fly), and watch the system adapt, translating your records without a pause. Once all records are translated, you can then remove the code that deals with the old schema. I think the great advantage here is that a dynamic language allows you more wiggle room to make things temporarily inconsistent and refactor the system in an incremental manner. With dynamic languages, you can have two record formats for the same data at the same time, and code that has typing errors won’t cause the system to fail so long as it’s not executed. It’s a more organic approach to the problem, and I think that programming live systems might actually be inherently organic in nature.
Now, I stated early in this post that I believe type systems and type inference are actually quite helpful. You could actually make the argument that organically modifying massive online systems on-the-fly without type checking is about as safe as riding a dirt bike through a Serbian minefield or playing Russian roulette everyday for a year. My answer would be that type inference isn’t fundamentally incompatible with dynamic typing. The unification-based type inference algorithms that Haskell and ML use don’t apply to dynamic languages, because they’re trying to solve a system of constraints where every variable has one single type, but unification isn’t the only type inference algorithm in existence. It’s quite possible to create a dynamic language VM that does type inference, and warns you about possible type errors. The difference is that the dynamic language VM will let you have temporary type errors, so long as you know you can make things eventually consistent.
What if you were modifying a live system, and introduced some crash bug? If you were working on a large production system, this could have terrible consequences. I would argue that if we’re going to modify live systems, we probably need to introduce live debugging tools. Things such as the ability to snapshot the system before introducing code changes, recording traces and being able to backtrack execution some large number of steps should a crash occur. It may also be interesting to be able to install monitoring on new pieces of code to keep track of what these specific pieces of code are doing after their introduction. Ultimately, however, with live systems, we should be prepared to have programmers directly intervening at the moment of a crash to repair the system on-the-fly and resume its execution. With the ability to backtrack execution and examine the live heap, this might actually turn out to be a rather comfortable way of debugging programs.
In order to inline code into running functions, their execution has to be momentarily suspended, the code modified, and execution resumed. In the case of Higgs, suspending and resuming execution is done simply: functions run in the interpreter until a counter (either at the function entry or at a loop header) hits a threshold, the JIT compiler then kicks in and does its job, and execution resumes in compiled x86 code. The complex bit is that the compiled code is going to be very different from the original function. It will have new instructions from inlined functions, new SSA phi nodes, some instructions potentially removed, and most importantly: the stack frame layout likely won’t match what we had to begin with. The technique to replace stack frames of running functions is called On-Stack-Replacement (OSR), and it is notoriously difficult to implement.
I decided to simplify things a little bit by restricting Higgs to only do OSR for functions that are on the very top of the stack. This prevents inlining from happening inside recursive functions, which isn’t too much of an issue with the benchmarks I’ve been working with. Things are still not simple, however. Liveness information needs to be taken into account when doing OSR, because multiple values may map to the same stack slot, and just looking at the code doesn’t tell us which values need to be written into updated stack frames: we have to know what was live before inlining, at the time the function was interrupted. Another issue is that new phi nodes may be introduced as a result of inlining, these phi nodes have no direct analog in the original function. Fortunately, one can logically conclude that these must take the value of the inlined call site they correspond to. I probably spent about 12 hours debugging this, but I eventually got it all to work.
My quest did not stop once OSR was working. I wanted to be able to run a peephole optimization pass on the intermediate representation of functions after inlining was done. This is to help remove phi nodes, remove dead code, simplify control flow, and do simple constant propagation. The complexity lies in the fact that since the function we’re modifying is currently executing, we can’t just make any transformation we want. It’s not valid, for example, to replace a value that’s currently live by another value that’s no longer live at the moment where the execution was stopped. A static compiler wouldn’t have to worry about such execution-time constraints, but we do. Fortunately, I found that in practice such limitations don’t really seem to affect the peephole optimizer much, it remains very effective.
I decided to spend some time and try to improve the code generated for a very simple microbenchmark: a for-loop that increments an integer counter from zero to 2 billion. The results are very encouraging: it’s over 10 times faster with inlining than without, and the code generated for the loop is fairly tight (ignoring suboptimal register allocation):
mov r8, 0; IF_TRUE(2EF9)(7): cmp r8d, 2000000000; jge FOR_EXIT(2DFB)(219) mov ebx, r8d; add ebx, 1; jo ADD_OVER(169); mov r8, rbx;
On my Core 2 Quad 2.4GHz, the loop executes in 3.2s, which puts it at around 625M iterations per second, or less than 4 CPU cycles per iteration, not bad! This microbenchmark is obviously a near-ideal test case, and I can’t claim performance gains anywhere near 1000% on more realistic benchmarks, but every benchmark I tested so far benefits from inlining. There’s still many simple things I can do to improve the speed of the generated code. For one, the heuristics I use to choose what to inline are fairly naive at the moment. Still, all of this is very good progress towards the paper I’m working on.