books chapter seven
Simon Peyton Jones doesn’t even have a PhD, but he’s got something even better: GHC. Pure and functional Haskell is radical and elegant and just what we all need to avoid getting stuck in a local optimum of imperative programming. One of the nice properties of a lazy evaluated language is that it’s easy to make it modular. It’s not hard to make a generator in a stricter language, but there’s less guarantee that the interface will be accepted by all your other components. I hadn’t really considered this before, but a C function that takes an array is not trivially converted to taking a generator struct. Or one could start by making every function take a generator, but that’s a lot of work. But then we only need to step up to C++ to get iterators and the dilemma fades again.
Simon is finally the STM (software transactional memory) advocate that Seibel has been searching for. They then discuss a kind of elaborate and stretched metaphor of reorganizing a library while permitting simultaneous checkouts. With primitive locks, the patron would have to wait until the whole reorganization is done to check out a book. So locks are subject to high latency. With STM, the librarian would finish organizing the library only to discover somebody checked out a book and then start over from the very beginning. So STM is subject to starvation. With a wave of the hand, they reduce the scale of the reorganization and replace the books with placeholders, and the operation completes successfully. But then they have to admit the same rewrite of the problem would improve the lock based version as well. Ah, but with STM you only have to make sure everything is in a well defined transaction that states all your invariants. So I think there’s a certain amount of optimism that if everything is correct then everything will be correct.
On the subject of STM, it came to Haskell from Java, but then they refined the concept, and pushed their ideas and improvements back to Java. So even if nobody uses Haskell, and they avoid success at all cost, there’s a benefit to having this weird research language out there. They don’t just create new ideas, but they take other new ideas and make them work in another context, which refines them.
He has some ideas on program bloat, that it doesn’t really matter how large a program is, because it still only spends most of its cycles in a tiny core. The problem arises when performing an action requires many, many abstraction layers to complete. So we might say the problem is not the width of the program, but the depth. I think sometimes we’re building in the wrong direction. And the fact we’re never satisfied. “The more robust your materials, the less you need to concentrate on the minutia instead of the larger-scale structures. Of course that will just make us more ambitious to build larger structures until we get to the point where they fall apart again.”
Steve Perlman founded WebTV, bringing the tubes to your tube, but he’s got a long history of working on computer graphics and interaction projects that were just a little too soon. He did some video on demand work at Apple, before the hardware was really ready for it, but that eventually resulted in QuickTime. You reach forward, a little too far perhaps, and have to build up a lot of your own technology, but that technology has merit on its own.
Then he went to Catapault, which added modem based multiplayer support to Nintendo games. The games weren’t built to support this, but they reverse engineered the cartridge and somehow tricked it into treating the modem as a second controller. They only needed to develop the hardware and some communication code, though, because it worked with (a select few) games that people already owned. One way to solve the bootstrapping problem. Add a feature to an existing product. I wish there had been some more detail about this project; it sounds awesome. Apart from the working conditions. “My admin, who came with me from General Magic, tells stories about coming in in the morning and trying to clean up. She’d pick up a folded pizza box and get scared because she’d find a guy sleeping underneath it - it was covering his face.”
After that, it came time to make WebTV. It’s about 1995, and Campbell’s Soup has a website with some recipes on it, but the people most likely to benefit from those recipes don’t necessarily have computers, and they aren’t buying one just to get dialup access just to download some recipes. So another bootstrapping problem. But everybody has a TV. Just a little extra hardware, a basic browser (the glorious golden days of the web when that’s all you needed), and a subscription service, and you’ve got AOL for people who aren’t even ready for AOL.
At one point, as they’re about to run out of funding and are desperate for a business partnership, they get a call that the Sony CTO is coming to visit. Coming to visit as in is currently on a private jet and will be landing in two hours, so get the demo ready. But the codebase was full of bugs because they were in the middle of a rewrite, and it took the whole two hours just to compile, and nobody knew if it was going to work. So a hard lesson in always keeping the source tree in a working state. And compile times kill!
Mike Ramsay founded that other TV tech company, TiVo. It’s funny to read, because he’s talking about how fast seek times are for hard drives, which sounds strange today, but of course he’s comparing to tape. The entire TiVo concept depends on hard drives becoming available in large capacities for cheap pricing. The original concept was actually a home server that would do all sorts of things, but the DVR aspect of it caught on and took over. The idea that you could pause live TV and resume it was so unbelievable to many people, they refused to believe it until demonstrated. In hindsight it seems like a fairly straightforward application of the technology, but I guess we’re not always good at recognizing when the impossible becomes possible.
Possible doesn’t mean easy, though. A common theme for many interviews is to get the hard part right, and then the easy parts will be easy. TiVo spent a lot of time on pause, they apparently didn’t get record working. (Not sure how that’s possible, one seems to rely on the other, but maybe he’s referring to a specific aspect.) So I think the lesson is to not ignore the easy parts too completely, just in case you have misjudged what’s easy and hard.
One of the important features of TiVo is they added the season pass feature, to record every episode of a show. But no duplicates. Also, if the season finale is two hours, you want to record all of it. They spent a lot of time getting the data for this, and massaging it, and making it work. I think it’s interesting to reflect that user interface aside (though also worth considering!) it’s easy to program a VCR to record one hour every Friday night. But adding just a small semantic layer, record The X-Files, which is what the user really wants, requires way more effort.
Calling the shot contains some notes on programmer productivity. Key formula: effort = (constant) x (number of instructions) ^ 1.5. Independent of increased communication and networking costs, it takes more work to get anything done the larger a program gets.
Brooks reviews various studies which conclude that productivity ranges from high hundreds to low thousands of instructions per man year. Which sounds really low. But then we end with a study about PL/I for MULTICS which found programmers produced the same number of lines per year, and each line might turn into three to five instructions. The miracle of programming in a higher level language. Humans can only process and track so many items of information at a time, whether they be instructions or statements.
Some lessons in writing software that isn’t going to work. Expect the worst and prepare for it.
21. Design by Contract. Every function should have some invariants preconditions and postconditions, which will keep your program from going too far off course. One way to achieve this is to program in Eiffel, though I think that’s been relegated to the lolwut category these days. The rest of us will have to add invariants to our code by hand, although this is an area where tooling can help.
22. Dead Programs Tell No Lies. It’s better for a program to crash than to continue running. This combines well with invariants. Add lots of invariants, when they’re violated, crash hard. Even if there’s no way for the invariant to be violated, software is complex and you never know what’s going to happen. Many times the initial error goes undetected, and the program continues running before something goes really wrong. We obviously want to reduce the time spent in a broken but still running state.
In Chapter 12 we build a binary adding machine. If we take another look at our binary addition table, we can separate it into a sum table for the low bit and a carry table for the other bit. We’re also going to need to build a new gate, the XOR gate, which is a combination of OR, NAND, and AND. With this we can build up a half adder. This can add two binary digits and produce a sum bit and carry bit. Works great for the first bit of a number, but the later bits are also going to have a carry bit coming in. So we need two half adders to make a full adder. Eight of those and we can add some modestly sized numbers. Building one by hand would be kind of tedious, however, because it requires 144 gates. The advantages of modular composition.
But what about subtraction? We return to the classroom to dissect subtraction into minuends and subtrahends. Subtraction by borrowing is too complex for a computer. Too many decisions. But if rearrange things to work with the nine’s complement (for base ten) it becomes much easier. There are a few more steps involved, but it’s pretty mechanical. We can do the same for binary using one’s complement. But wait, there’s more. If we decide to discard the sign bit and assume large numbers are actually negative, we can use two’s complement. This simplifies working with subtraction and negative numbers quite a bit, with one new problem. The interpretation of bits as signed or unsigned requires additional information not contained within the number.
“That’s the trouble with bits: They’re just zeros and ones and don’t tell you anything about themselves.”
Sometimes a failed, or even just unpopular, idea is simply ahead of its time. This doesn’t really make it work any better, but perhaps some of it can be salvaged and reused in another context.