ObRandom: A rather detailed view of how duct tape was used during the Apollo moon landings.
Categories
Month: December 2008
Over the last year, I’ve got a lot more picky about how I spend my ‘free’ time – I think all new fathers encounter this! I used to read reddit and follow all the latest k3wl happenings in the programming world. Occasionally, I’d read something that was really insightful but mostly it was just here-today-gone-tomorrow fluff .. “my way is more awesomer that yrs” kinda stuff. So I decide to try and ignore the fluff by thinking “will this be interesting in a year from now?” before I start reading. And pretty soon afterwards, I decided to commit time to watching the videos of the SICP lecture series.
SICP (see amazon.com
The course explores “programming languages” as a concept, not “programming as an activity”. It’s a lesson in how to make tools, not just how to use those tools. So, you won’t learn how to build a big object oriented application. But you will learn different ways to implement support for “objects” in a language – eg. different ways to do method dispatch. If you know about C++ or Java, this kind of thing is baked into the language. SICP will show you ways to to mix the cookie dough, rather than just describing the cookies. And it’ll also tell you how to make a mixing bowl out of cookie dough too!
The course uses the scheme language. The choice of language isn’t shockingly important – it’s just a vehicle for making the concepts discussed in the course concrete. The real concepts – abstraction, combination and naming – are the fundamental ideas and transcend languages. Scheme is just a convenient way of talking about these concepts. The scheme language (its pretty simple) is explained as you go along anyway.
The videos were made in 1986, so they provide an interesting snapshot in time. The vast majority of the content is still 100% relevant today. The lectures on logic programming and streams (lazy evaluation) are interesting because in 1986 it wasn’t so clear how these ideas would turn out – eg. Miranda is mentioned, but Haskell was still to come. For example, the lecturer motivates the introduction of mutable state by showing how threading state between pure functions breaks encapsulation – whereas today you could use monads to make this more manageable.
With the benefit of 20 years of hindsight, there’s a few things that come across as being klunky. There’s a lot of interesting discussion about the relationship between car/cdr/cons and how you could realize those concepts. However, when we get on to more implementation heavy stuff, car/cadr/etc are used purely as the way to pluck data out of lists. Coming from an ML/haskell background, I was crying out for pattern matching. Ironically, pattern matching is covered in lecture 4, but it’s not added into the standard vocabulary. Instead the lecturer keeps saying “to find the foo, we need to take the car of the cadr of the list”. It made me miss pattern matching a lot!
The video series is also a reflection of the MIT research interests of the time. If you’ve only ever used one language before, it’s difficult to understand how that language affects the way you express and understand things. In the early days, it wasn’t clear what the ‘best way to program computers’ was. It probably still isn’t clear today. But in the 70’s and 80’s MIT was busy churning out language after language to try to better solve the “difficult AI problems” of the day. People were trying lots of different ideas – procedural style, rule-based systems, logic systems, objects, lazy evaluation etc- and consequently there was a rich ecosystem of programming languages which acted as vehicles to try these ideas out. This is the culture in which scheme was developed, and the choice of topics covered in SICP reflects this period.
So what are the good bits of the lecture series? Higher order function are introduced early as a basic building block and thereafter taken for granted. I think that somewhat sets the tone as far as this ‘introductory’ course goes! The benefits of decoupling interfaces/contracts from concrete implementation is covered repeatedly via examples. And the lectures are peppered with “shocking” examples – eg. implementing car/cdr/cons just using lambda – which serve to illustrate the current topic but also tie together the deeper overall themes of the course.
I enjoyed the wide range of topics covered, and way that main themes continually recur throughout the lectures (abstraction and combination). I feel that this was a well-constructed course, carefully designed to lead students on a journey by showing them many facets of programming, whilst continually explaining how they interrelate. Additionally, I think that it all feels very genuine – it’s a reflection of what Sussman and Abelson were working on at the time. They often stress that the examples they use aren’t just toy examples. The metacircular evaluator isn’t there just for teaching purposes – it’s how these guys experimented with possible language features (say, call-by-name vs call-by-value).
The questions at the end of the lectures are often the best bit – they’re often “uhh, I didn’t understand this bit”, but the answers often shed new light on an area so I’m glad that the questions were asked!
Any downsides? The final lectures on interpretation and compilation gets somewhat bogged down in prolonged hand-cranked examples. In an introductory course, it’s good to illustrate how to make abstract language concepts realizable in real hardware. But even allowing for that, I think they overstretched somewhat.
I was sad when I finished watching the last video. These videos may be twenty years old, but I enjoyed watching them and learned a lot. Mr Sussman and Mr Abelson: thank you for sharing your knowledge and understanding so effectively! 🙂
Categories
Decentralized monitoring
Occasionally, one of the three computers in my flat will crash or hang in some way. When this happens, it’d be nice to be notified. For example, if the MythTV host crashes it’ll stop recording any TV programs until I notice and kick it. So I could just install one of the many network monitoring packages out there. But as far as I can see, they all want me to choose one ‘master’ host and have the other machines report their statistics into the master. That sounds awfully oldskool. Which of my three machines should I pick as ‘master’? They’re all equally likely to go down, and when the master goes down, I won’t get any notifications.
What I really want is a “neighbourhood watch” scheme, where each host watches the others. Or, in posher language, I want a decentralized monitoring solution. Here’s how it’d work. Each host would announce ‘I’m still running’ or ‘My load is 50%’ every few seconds, and the other hosts will listen and record the message to disk. If any one machine bursts into flames, the other two should still have a complete record (including the fact that the failed host stopped talking at 15:30).
Ideally, hosts should be able to add themselves to the party without much hassle. Announcing the messages via IP broadcast would fit the bill, but it’d only work on one LAN segment. Also, the hosts might end up being fairly busy if they have to handle status updates from all other hosts all the time.
Sounds like an ideal application of gossip protocols. When a node first joins the monitoring party, it needs to be told about at least one other participating node. The nodes can subsequently exchange occasional ‘gossip’ messages with a few of their neighbours, telling them about the state of the world. The gossip message can also contain information about other nearby participants. In this way, information gradually spreads out around the network. Network partitions are a minor pain, but so long as there’s at least one other host still around to notice any explosions, they’ll still be noted.
This seems to fit the bill nicely: decentralized, unlikely to lose data, and robust to hosts appearing and disappearing.
So that’s the monitoring and data recording side dealt with (ha, no lines of code written!). But what about the alerting? If one host goes down, I don’t really want N other hosts all to start spamming me with duplicate notifications. I guess neighbourhood watch scheme suffer this problem – everyone in the street hears a window smash and the police get twenty phone calls! But can a decentralized mob temporarily appoint one of their number as a leader in order to send out a single notification? Yes, that’s exactly what distributed ‘election’ algorithms are designed to do. If all the hosts can talk to each other, they’ll manage to agree on a single leader. If there’s been a network partition, at worst we’ll get one leader in each partition and so get a few notifications (ie. the right hand says ‘I can’t see the left hand!’ whilst the left hand says ‘I can’t see the right hand!’).
There’s maybe a bit of tension here. You could write a gossip protocol where a node only keeps track of a few neighbours at any given time. But, for an election, you’ll need to know about everyone in the network. And even in a gossip system where nodes do eventually learn about the whole network, there’s going to be a startup period where the new node does know about everyone. Hmm, but I guess the election process might be able to handle this if it can gather together all the partial knowledge about who’s in the election. Ah, more detailed reading required!
Surely this system already exists? Well, the closest I could find was GEMS which doesn’t appear to handle the single-notification problem. All very interesting stuff though!