A Code Workaround for a Busted Furnace

warmup.cpp: [code]

Late last December, I woke up and it was freezing in my apartment. I checked the thermostat, and it was already less than 60 degrees! I turned it from hot to cold to hot. And again. I turned it all the way up. The furnace never clicked on. COME ON! I checked, and the pilot light was on, so I had no choice but to call maintenance to get it fixed.

Most days this wouldn’t have been a problem, since it would be fixed while I was at work, but I was in my end-of-year vacation-burning crunch. Maintenance always fix minor problems really fast, so I knew it would take all day to come and fix the heater. Sure enough, help didn’t arrive until 6PM.

I tried lying motionless on the floor under some blankets and played some Assassin’s Creed 2. This worked for an hour or so, but if I’m at home all day and not working on something on the computer, I start to feel like a waste. This was in the middle of trying to get a side project of mine off the ground, and I wanted to get a beta version working before returning to work in January.

Could I use my laptop as a heater? It gets pretty warm when the CPU runs at full blast on one core. If I kept both going for hours, would that be enough?

8 minutes later, I had a C++ program that ran 2 CPUs at full blast. I hate picking C++ for a personal project, but I’ve used it for 10 years and I’m just not familiar enough with any other language’s CPU usage patterns to do the work that quickly. I probably didn’t have to worry, but I was cold!

The program, warmup, runs NUM_CPU copies of this thread:

int fn(bool *go)
{
  double a = 0;
  static mt19937 rng(static_cast<unsigned> (std::time(0)));
  normal_distribution<double> norm_dist(1.0, 1.0);
  variate_generator<mt19937&, normal_distribution<double> >
  normal_sampler(rng, norm_dist);
 
  while(*go){
    double val = normal_sampler();
    a += val;
  }
  return 0;
}

I already had Boost, and I’d never used their pRNGs before, so I decided if it was a copy/paste job, I would give them a test run. Sure enough, it plugged right in.

The main function is even simpler:

int main()
{
  bool go = true;
  boost::scoped_ptr<boost::thread> threads[NUM_THREADS];
 
  for(int i=0; i<NUM_THREADS; ++i)
  threads[i].reset(new boost::thread(fn, &go));
 
  std::string asdf;
  cout<<"enter any input and hit <Enter> to kill"<<endl;
  cin>>asdf;
 
  go = false;
 
  for(int i=0; i<NUM_THREADS; ++i)
    threads[i]->join();
 
  return 0;
}

Within 12 minutes of starting, I was nice and toasty!

I posted the code on Github in case I needed it somewhere else: [code]


Popularity: 1% [?]

A Wrinkle in (Deconstructed) Time

Or, “Hey, you blogged again! It’s about time!”

In “Are We There Yet? A Deconstruction of Object Oriented Time,”[slides] [interview] Clojure creator Rich Hickey looks beyond concurrency support in popular programming languages to see what’s on the horizon. He asserts that wrapping our objects in locks – the popular solution – is an attempt to treat concurrent objects as if they were accessed by a single thread. Hickey describes the problems with this approach in two slides:

We don’t make decisions about things in the world by taking turns rubbing our brains on them.

Nor do we get to stop the world when we want to look around.

Instead of this awkward locking model, he suggests a versioned approach to representing object instances. He also presents some programming constructs to be used in his versioned model.

Below, I present his idea of a pure function to update the view of objects to a new state. I also introduce a problem that this doesn’t handle, the expiration problem, that language designers should either address or state they don’t handle.

Background

In Java and C++ (and many other languages), it’s very easy to write concurrent code that causes inconsistent results across multiple reads. So easy, in fact, that it’s the default for everything! You’d have to do external locking or go to heroic lengths to avoid doing it. It happens regardless of the thread safety of the underlying class!

Let’s look at an example: Assume that some Evil Crime Syndicate is trying to kill me. Even worse, they have cracked all government mainframes and always possess my contact information. Like all Evil Crime Syndicates, they have a gigantic code base written in Java that runs the whole operation. To save themselves some personnel costs, they wrote an automated assassin dispatching system.

Let’s look at a scenario where the assassin acts on an inconsistent kill order:

Assassin code

  class Assassin
  {
    void killPerson(Person person)
    {
      String personAddress = person.getAddress();
 
      // --- INTERMEDIATE ACTION BY ANOTHER THREAD ---
      // I enter the Witness Protection Program, and my
      // name and address are changed.
 
      String personName = person.getName();
 
      // Some private method
      actOnKillOrder(personName, personAddress);
    }
  }

Application code

Person nextTarget = TargetFactory.makeTarget("Jake");
 
// Not shown: logging, passing the target info to a central
// database, etc
 
currentAssassin.killPerson(nextTarget);

If I officially enter the Witness Protection Program while killPerson() performs sequential reads, the assassin will look for a new name at an old address. In the best case, he’ll get some puzzled looks when he asks around for a new identity at the old location.

We’ll call the worst case deadlock

A second chance for the Evil Crime Syndicate

Could language features help the Evil Crime Syndicate kill me? Hickey proposes that instead of looking at objects as a single mutable data point, we treat objects as a succession of states. Each view perceives an immutable state at some point in time, and references it until it is updated. If the view needs to know the current state of the object, then it can call a function that returns the object’s newest state. If the object is constantly being updated by other views, you won’t see any of these changes until you call this function and get the new version of the object.

This is a version control system for objects. You query the object once and do stuff with the data that you get back. When you want to pull the current updates for the new object, just call the system’s update command and get a new version! The system handles all of the reads and writes behind the scene, just like a real database. Interesting aside, databases and version control systems concurrent systems that Joe Coder already uses on a massive scale with minimal concurrency problems.

To imagine this feature in Java, let’s call our pure function Update(). It takes the current view of a Java object and returns the newest value of the object. Yes, I know that adding a function to Java completely breaks the consistency of Java’s all-object model, but you’ll notice that I have no control over the language features added to Java. This continues to be a good decision made by Sun Microsystems.

It turns out that Update() makes it easy to show that the assassin always acts on consistent data!

Assassin code

  class Assassin
  {
    void killPerson(Person person)
    {
      String personAddress = person.GetAddress();
 
      // If my data is updated here, this view's
      // view of 'person' doesn't change. All reads
      // are consistent!
 
      String personName = person.GetName();
      actOnKillOrder(personName, personAddress);
    }
  }

Application code

Person nextTarget = TargetFactory.makeTarget("That Jake guy");
 
// Not shown: passing the target to a central database, etc
 
person = Update(person);
currentAssassin.killPerson(nextTarget);

In this code snippet, the fact that Update() is called before dispatching the assassin ensures that the assassin is acting on a consistent and relatively recent view of me. I mean, I could enter Witness Protection as the assassin travels, or immediately after Update() is called. However, that’s a logistics problem for the assassin, and he won’t get any sympathy from me!

The Expiration Problem

Now the wrinkle! What if we query real-world objects for their state? Let’s say that you have an atomic clock hooked up to your computer via a serial port.

     AtomicTime time = atomicClock.queryTime();

Let’s assume that the delta between the AtomicClock time and the system time is known and constant, which is not usually a reasonable assumption. For the sake of discussion, let’s also assume that Update() can update an AtomicTime to the most recent value pulled from the AtomicClock. How does Update() interact with this real-time object?

Most of the time, it works very well. We can use Update() to ensure that our view of the time is consistent if we read hours, microseconds, and nanoseconds sequentially.

As we use it more, we run into a problem! Let’s assume that we want to display the atomic time to the user. We could just constantly Update() the time returned from the atomic clock, but I’m not a big fan of polling. Why? If we hit unexpected latency or blocking and we poll slower than we expect, we’re going to display times to the user that are no longer accurate. The data changed and nobody told us.

I call this the expiration problem. Sometimes it’s easy to fix — dude, just poll the clock faster. Duh. — and other times it’s not so easy. Just look at the assassin example. Even when we could show the function always worked consistently, the assassin could still be dispatched to an old address looking for an old name. This is obviously bad: the data rotted and the programming language stayed silent. The system knows everything it needs to say, “Hey, by the way, this data isn’t good anymore,” but it doesn’t.

The front office of the Evil Crime Syndicate naturally doesn’t understand the distinction and will totally give my would-be assassin a hard time. “What do you mean you killed the wrong person? Our system always gives a consistent and up-to-date target. Obviously this is your fault. You’re getting a pay cut after you finish this assignment.”

Of course, there are also problems introduced when values are allowed to expire. The data doesn’t always need to expire! An assassin could gather clues from old aliases and residences, for instance. You could want to store a list of AtomicTimes for processing elsewhere.

Any language that uses expiration as an explicit action needs to also allow the programmer to differentiate between the following:

• Hard expiration: Occurs when using a dated value could be expensive or harmful. An exception is thrown if you attempt to use the object after expiration.
• Soft expiration: The programmer wants to know if the value goes bad, but the value is still usable in some views. This could be implemented through either callback handlers or exceptions.
• No expiration:  The default for most data.

Ideally, this would be settable per each view of the data.

Conclusion

Concurrent programming has a lot of inherent wrinkles, and trying to remove all of them out is a very deep rabbit hole. Each solution usually points to another problem. Sometimes they don’t really matter, like showing an atomic clock time for an extra few nanoseconds. Sometimes they could cause expensive mistakes, like sending an assassin to the wrong place for the wrong target.

Rich Hickey’s pure function that returns the future as a function of the present is a great idea, and I’d love to see Hickey implement something like it in Clojure. It may also be possible to implement expiration! I recall that Clojure allows validators to be attached to objects to check for consistency across updates. I don’t see why expiration couldn’t be handled similarly to check for staleness on reads.

I would love to see some other language-level ideas and implementations for aborting a current action if the data fails a staleness check. “Data is guaranteed consistent and up-to-date!” would be a pretty good selling point for a language, even if the utility of having both at the same time is often low.

The expiration problem exists in every language, but if we’re actively trying to ease the pain of concurrent programming, it’s something that needs to be explicitly formalized and addressed. In fact, I’d bet a dollar that there are already 5 different formalizations for this phenomena. Does anyone know if this has been discussed in a more professional or academic publication?

Special thanks to Sarah Braun and Greg Molyneux for reading drafts

Popularity: 3% [?]

Languages and Axioms

I learned Common Lisp last summer. I had been using some combination of Python, C++, C, and Java for about 8 years, and I wanted to break out of my popular language box. I was more or less attracted to the “data as code” idea, but really it had a bunch of selling points that I would have appreciated:

• Its data was stored in the same structures as its program.
• It had macros that were powerful and simple. That’s huge coming from C++.
• It was REPL-based, something I never took advantage of with Python.
• You could create new code on-the-fly at runtime from lists.
• Completely dynamic and backed by garbage collection.
• The language itself is very mutable.

The sum of its parts was greater than anything that I had ever used before, and it quickly became my favorite language. I learned quite a bit about functional programming techniques, did some experimentation with image processing and database application programming, and worked through all of Graham’s  ANSI Common Lisp and large swaths of Norvig’s Paradigms of Artificial Intelligence Programming.

Recently, a nagging though started to cross my mind: What if I didn’t go far enough to break out of my box?

That didn’t happen until two weeks ago, when I started porting Genesis, my toy genetic algorithm framework, to Clojure for fun. I wasn’t very aware of the features of Clojure: I knew that it was a Lisp on the JVM and that it supported Software Transactional Memory, but I didn’t think it would be that different from Common Lisp aside from Java interoperability.

To clarify, I expected that the primary method of manipulating Clojure would be list-based, and that it would still mostly turn a blind eye towards mutable data and multithreading issues, with the option of phrasing memory updates in terms of transactions if you were using multithreaded applications.

Clojure turned out to be different than any language that I had ever tried – save my forays into Haskell to grok enough syntax to follow sigfpe’s easier articles.  If you trust the language and work with the core Clojure data structures, it takes a lot of the worrying about parallel programming out of your hands. Its creator, Rich Hickey, ended up with a language that has a good balance between functional programming and practicality. It is definitely a good Modern Programming Language.

You Said Something About A Box..?

Right, I said I didn’t go far enough outside of my comfort zone when learning Common Lisp. That’s really only half true.

From the perspective of programming, Common Lisp is a great language. Using the functional programming primitives provided on top of lists feels very natural, and I was able to work on complicated problems with relative ease. Even though I don’t use the macro system in Common Lisp very often, it usually provides a great fallback for either refactoring or changing the way the problem can be represented. The REPL is just icing on the cake.

However, not all is flowers and roses. Looking at Common Lisp from perspectives other than single-threaded programming, it begins to look mortal! For instance, the Common Lisp standard was written without a thought to having multiple threads of execution. Although most implementations provide extra support for multithreading, you’re back in the same locking boat that you were with any of the other popular languages once you need to share mutable data. Naturally, the syntax for things like grabbing mutexes is easier with Lisp than with other languages thanks to the “with-” design pattern for macro writing, but you’re not gaining much with respect to avoiding race conditions.

Looking at it from a data-processing perspective, functional programming is easy in Common Lisp, but it isn’t required at all. There’s nothing stopping the programmer from falling back into using local mutable state, functions with side-effects on global variables, and destructive functions. Combined with the single-thread design, that’s fine. You can’t avoid state all of the time, and I don’t go out of my way to be strictly functional. That’s how most other languages are designed. Hell, the Common Lisp standard even offers a whole slew of functions that are destructive for the sake of efficiency!

I’m only really getting at the fact that even the ultra-flexible of Common Lisp wasn’t written to handle all computing scenarios.

Some languages have support for neat automatic threading features: Haskell has extensions where type annotations can allow automatic parallelization, and you can use OpenMP in C++ for automatic parallel processing. For those wondering, Erlang is somewhere on my list of languages to take a look at, but it has to wait its turn! I’m still having too much fun with Lisps.

Axiomization and Language Design

Love him or hate him, Paul Graham has written quite a bit about the design of Arc. I’m not going to talk about it directly, but I will borrow his idea of reaxiomizing the core of a language as a means of producing better code on top of it. He mentions axioms as neither primitives nor library functions, but I will consider primitives as well.

I’ve talked about this a little in the past. For instance, I’ve made the case for operator overloading in Java. It was explicitly verboten in Java, as decreed by the designers. In fact, written in an early Java whitepaper titled “The Java Language Environment“,

2.2.7 No More Operator Overloading

There are no means provided by which programmers can overload the standard arithmetic operators. Once again, the effects of operator overloading can be just as easily achieved by declaring a class, appropriate instance variables, and appropriate methods to manipulate those variables. Eliminating operator overloading leads to great simplification of code.

By the letter of their assertions, they were correct. A lot of programmers would never need operator overloading to produce good code. In fact, if you’re using it just for the sake of expressiveness, you’re going to produce an unintuitive hodgepodge most of the time. However, a small but powerful minority – particularly those who do mathematical work for a living – would absolutely benefit from being able to write inline operators. I mean honestly, have you ever tried to use a BigInteger to implement something more complicated than RSA? The best that will happen is that it will end up… verbose.

Essentially, leaving out operator overloading forced Java to be more verbose and/or less readable than it needed to be. Leaving it in as an ‘axiom’ could measurably produce more compact, readable code for programmers who used it judiciously.

As an aside for those who think I’m just trolling Java, there is definitely a great Java feature for each one that misses the mark. For instance, the enums in Java follow the idea to its logical conclusion.

If you’ve been incensed by my Java discussion or are otherwise unsure that axiomization could lead to a better language, let’s look back at Lisp. Lisp changes quite a bit if you remove utility functions like reduce: it would break a lot of the compactness of the language and ruin some otherwise good functional programming. Now, it doesn’t support operator overloading, per se, but there’s nothing stopping you from changing the language to support it.

Where the Hell is All of This Going?

Back to Clojure! Clojure is based on a much different set of axioms than many of the popular languages. At its core, we see support for thread-safe data structures whose data are immutable and persistent. These were written in as axioms to the language, and you can make some good predictions for the language, assuming people stick with it.

The biggest one is that as libraries are converted to Clojure or abstract away their Java API, Clojure will develop a large set of libraries that could be given a thread-safe guarantee.  For my day job, I work in a C++ shop that uses a bunch of C libraries, and we need to constantly be aware of whether or not our base libraries are thread-safe. My workplace recently developed a non-Clapack fork of our linear algebra abstraction for this reason: using libraries that aren’t designed to be threadsafe in a multithreaded environment builds bombs.

I’m too young to get a sense of what the next 10 years of programming languages might look like – but if you pressed me, it would look a lot like it does today, and we wouldn’t be better off for it. The languages that are currently in the design phase are slowly adding quite a bit of features while remaining mostly the same: for instance, C++ is getting a makeover that includes concepts, lambdas, futures, and a multithreading primitive.  I’ve known C++ for over half of my life (holy shit!), and a lot of the features are sorely needed. However, it’ll be an incremental improvement at the cost of obscure compiler bugs and increased complexity.

These aren’t easy problems: for instance, if you didn’t care a lick about any external concerns like backwards compatibility and wanted to change C++ to support lambdas, how could you without just tacking it on? However, we have new languages that can pick up where the old languages left off, and continuing Fred Brooks’ prediction, there will be no silver bullet, only incremental improvements. Languages like Clojure are a step in the right direction as far as testing new computing ideas.

Popularity: 20% [?]