Monday, April 30, 2007
If you reside in the USA, please don't read this post
Update: The 128-bit Programming Challenge!
You probably don’t want to be caught with the following hexadecimal codes in your possession: by downloading this post in your browser you have already participated in their transmission!
If you are in the USA, please stop reading immediately.
Jump to another web page. Clear your cache. Do not read further.
While you’re protecting yourself against these codes, you should also be careful to remove any code from your system that generates irrational numbers. Such numbers must contain these codes in their expansion.
It is reasonable, therefore, to assume that a program for generating an irrational number such as π is a program for generating these codes, and therefore it is not safe to have this type of program on your computer.
Update: while you’re at it, you should probably be wary of programs that search for large primes. You never know when a prime number will be declared illegal!
This warning provided as a public service by your Canadian friend.
You probably don’t want to be caught with the following hexadecimal codes in your possession: by downloading this post in your browser you have already participated in their transmission!
If you are in the USA, please stop reading immediately.
Jump to another web page. Clear your cache. Do not read further.
09 F9 11 02 9D 74 E3 5B D8 41 56 C5 63 56 88 C0
While you’re protecting yourself against these codes, you should also be careful to remove any code from your system that generates irrational numbers. Such numbers must contain these codes in their expansion.
It is reasonable, therefore, to assume that a program for generating an irrational number such as π is a program for generating these codes, and therefore it is not safe to have this type of program on your computer.
Update: while you’re at it, you should probably be wary of programs that search for large primes. You never know when a prime number will be declared illegal!
This warning provided as a public service by your Canadian friend.
Sunday, April 29, 2007
Writing programs for people to read
This is about writing programs in a style that favours human comprehension over the convenience of the machine.1
Norbert Winklareth recently raised the question of minimizing the semantic distance between the program as written and the solution to the problem as conceived by the programmer.
Norbert was talking about comparing the capabilities of programming languages, but the idea of semantic distance is also useful for comparing programs to each other. Although this is not the entirety of writing good programs, let’s examine this idea in more detail.
Indeed, let’s look at one very simple, very powerful, way of writing programs that are as semantically close to the solution in the mind of the programmer.
Code that resembles its result
A template is a blueprint for describing the result you want, where instead of embedding data inside executable code, you turn things inside out and embed executable code inside data.
Templates are very popular in programs that generate markup:
It’s obvious what result you want, much more obvious than if you tried the following:
This code produces its results as a side effect of its execution. The code itself doesn’t directly describe the result, whereas the first example directly describes the result we wish to generate.
Sometimes you need to generate the result as a side effect of the code. You needn’t write code as opaque as the answer above, instead you can organize your code so that its form resembles the form of the result you are generating, such as this Scriptaculous code:
That produces this HTML:
Just like the template example, you don’t need to run a simulation in your head to try to figure out what the code produces.
Is this just cancer of the semicolon?
What’s the difference between these two code samples?
…and…
Is the second just syntactic sugar for the first? No. It’s more than just syntactic sugar. People have a habit of saying “syntactic sugar” in a dismissive way. It’s another argument that since an underlying language is Turing Equivalent, there is no need for a particular language feature.
Not all language features are just syntactic sugar. True syntactic sugar features are local features: you can replace the feature with some other equivalent code without having to change a bunch of stuff elsewhere.
Lazy evaluation and garbage collected memory management are not syntactic sugar: they require wholesale changes to the underlying model of computation to work. The abbreviated
Okay, non-local features are not syntactic sugar. When is a local feature “just” syntactic sugar and when is it something more than that?
Let’s compare these two language features. Consider this Smalltalk code:
This shows a series of “cascading messages” to the same receiver. It saves you having to type the word “window” again, and it is a lot easier to read, because it lets you group messages that obviously belong together.
And earlier, we saw:
This is String Interpolation.2 It’s an “abbreviation” for a longer sequence of
The difference between these two trivial cases is that the first example doesn’t change your mental model of what’s going on when you read the code: you’re simply sending a bunch of messages to the
The Ruby Way is the perfect second Ruby book for serious programmers. The Ruby Way contains more than four hundred examples explaining how to do everything from distribute Ruby with Rinda to dynamic programming techniques just like these.
The second example is different in a very important way: honestly, when you read the second example, do you think “Aha! Start with a string, get Time.now(), append it to that string, then append a period”?
No way! You think “A String with Time.now() stuck in it.”
That’s a huge difference mentally, it’s not just shorter, it’s semantically closer to your mental model of the result you’re trying to achieve.
Wrapping up code that resembles its result
In summary, one way to write code that is comprehensible is to make sure that the form of the code matches the data the code generates. This is a very general principle, it can be found in web templates (like PHP and ASP pages), markup builder libraries, and even String or List Interpolation.
Features that support this style of writing code are more than simple syntactic sugar, because they alter the reader’s mental model, lowering the semantic distance between the code and the code’s result.
Bonus! Order now, and we’ll throw in these free Domain Specific Languages!
We saw that organizing code so that it resembles the result it generates lowers the semantic distance between the code and the solution. We saw two ways to do this: we can use templates or interpolation (if our language permits interpolation) to produce data, and where templates won’t work we can structure our code to resemble its result.
Well, we needn’t stop there. Domain-specific languages can provide this exact benefit.
The general purpose of a DSL is to write programs, or parts of programs, where the form of the code matches the mental model of domain experts or programmers. And here is one specific use for a DSL: to write code that closely matches the result it generates.
List Comprehensions model lists after mathematical notation.
There are many valuable uses for DSLs. One of them is to create programs that closely resemble the results achieve, such as the HTML builder we see earlier, list comprehensions, and regular expressions. DSLs can increase human comprehension by representing the desired result directly.
And if you call in the next fifteen minutes, you’ll membership in the Pattern Matching family at no extra cost!
There’s another significant opportunity for writing code that increases human comprehension. We saw how to write code where the form of the code resembles its result. You can also write code where the form of the code resembles the data it consumes.
In ML, patterns allow us to make our functions resemble the different values they consume:
If you are not familiar with pattern matching, and especially with how languages like ML and Haskell combine patterns with their type checking system, maybe today is the day to spend a little time looking into this powerful idea for making comprehensible programs.
Programs must be written for people to read, and only incidentally for machines to execute.
Abelson & Sussman, Structure and Interpretation of Computer Programs
This is about writing programs in a style that favours human comprehension over the convenience of the machine.1
Norbert Winklareth recently raised the question of minimizing the semantic distance between the program as written and the solution to the problem as conceived by the programmer.
Norbert was talking about comparing the capabilities of programming languages, but the idea of semantic distance is also useful for comparing programs to each other. Although this is not the entirety of writing good programs, let’s examine this idea in more detail.
Indeed, let’s look at one very simple, very powerful, way of writing programs that are as semantically close to the solution in the mind of the programmer.
Code that resembles its result
A template is a blueprint for describing the result you want, where instead of embedding data inside executable code, you turn things inside out and embed executable code inside data.
Templates are very popular in programs that generate markup:
Hello World
Hello, Example. Today's date and time is .
It’s obvious what result you want, much more obvious than if you tried the following:
page = Page();
head = new Head();
title = new Title();
title.setText("Hello World")
head.add(title);
page.add(head);
body = new Body();
preamble = new StringBuffer();
preamble.append("Hello, Example. Today's date and time is ");
preamble.append(Time.now().toString());
preamble.append(".");
body.add(preamble.toString());
page.add(body);
This code produces its results as a side effect of its execution. The code itself doesn’t directly describe the result, whereas the first example directly describes the result we wish to generate.
Sometimes you need to generate the result as a side effect of the code. You needn’t write code as opaque as the answer above, instead you can organize your code so that its form resembles the form of the result you are generating, such as this Scriptaculous code:
element = Builder.node('div',{id:'ghosttrain'},[
Builder.node('div',{className:'controls',style:'font-size:11px'},[
Builder.node('h1','Ghost Train'),
"testtext", 2, 3, 4,
Builder.node('ul',[
Builder.node('li',{className:'active', onclick:'test()'},'Record')
]),
]),
]);
That produces this HTML:
<div id="ghosttrain">
<div class="controls" style="font-size:11px">
<h1>Ghost Train</h1>
testtext234
<ul>
<li class="active" onclick="test()">Record</li>
</ul>
</div>
</div>
Just like the template example, you don’t need to run a simulation in your head to try to figure out what the code produces.
Is this just cancer of the semicolon?
What’s the difference between these two code samples?
preamble = new StringBuffer();
preamble.append("Hello, Example. Today's date and time is ");
preamble.append(Time.now().toString());
preamble.append(".");
…and…
"Hello, Example. Today's date and time is #{Time.now}."
Is the second just syntactic sugar for the first? No. It’s more than just syntactic sugar. People have a habit of saying “syntactic sugar” in a dismissive way. It’s another argument that since an underlying language is Turing Equivalent, there is no need for a particular language feature.
Not all language features are just syntactic sugar. True syntactic sugar features are local features: you can replace the feature with some other equivalent code without having to change a bunch of stuff elsewhere.
Lazy evaluation and garbage collected memory management are not syntactic sugar: they require wholesale changes to the underlying model of computation to work. The abbreviated
for loop in Java 1.5 is syntactic sugar: you can translate each loop into the equivalent old-style iterator loop without any additional support. For that matter, Java enums are also syntactic sugar, they’re a way to write the Type Safe Enum idiom with less boilerplate.Okay, non-local features are not syntactic sugar. When is a local feature “just” syntactic sugar and when is it something more than that?
Let’s compare these two language features. Consider this Smalltalk code:
window
position: 80@80;
extent: 320@90;
backcolor: Color blue;
caption: 'My Blue Test Window'.
This shows a series of “cascading messages” to the same receiver. It saves you having to type the word “window” again, and it is a lot easier to read, because it lets you group messages that obviously belong together.
And earlier, we saw:
"Hello, Example. Today's date and time is #{Time.now}."
This is String Interpolation.2 It’s an “abbreviation” for a longer sequence of
appends onto a StringBuffer.The difference between these two trivial cases is that the first example doesn’t change your mental model of what’s going on when you read the code: you’re simply sending a bunch of messages to the
window.The Ruby Way
is the perfect second Ruby book for serious programmers. The Ruby Way contains more than four hundred examples explaining how to do everything from distribute Ruby with Rinda to dynamic programming techniques just like these.No way! You think “A String with Time.now() stuck in it.”
That’s a huge difference mentally, it’s not just shorter, it’s semantically closer to your mental model of the result you’re trying to achieve.
Wrapping up code that resembles its result
In summary, one way to write code that is comprehensible is to make sure that the form of the code matches the data the code generates. This is a very general principle, it can be found in web templates (like PHP and ASP pages), markup builder libraries, and even String or List Interpolation.
Features that support this style of writing code are more than simple syntactic sugar, because they alter the reader’s mental model, lowering the semantic distance between the code and the code’s result.
Bonus! Order now, and we’ll throw in these free Domain Specific Languages!
We saw that organizing code so that it resembles the result it generates lowers the semantic distance between the code and the solution. We saw two ways to do this: we can use templates or interpolation (if our language permits interpolation) to produce data, and where templates won’t work we can structure our code to resemble its result.
Well, we needn’t stop there. Domain-specific languages can provide this exact benefit.
The general purpose of a DSL is to write programs, or parts of programs, where the form of the code matches the mental model of domain experts or programmers. And here is one specific use for a DSL: to write code that closely matches the result it generates.
List Comprehensions model lists after mathematical notation.
list { [x, y, x * y] }.given(:x => 1..12, :y => 1..12) directly describes a list of multiplicands and results.(19|20)\d\d[- /.](0[1-9]|1[012])[- /.](0[1-9]|[12][0-9]|3[01]) is a regular expression that matches dates.3 Do you think it is hard to read? What would happen if you “compile” that expression into procedural code with side effects? Which program would be easier to understand, debug, and modify?There are many valuable uses for DSLs. One of them is to create programs that closely resemble the results achieve, such as the HTML builder we see earlier, list comprehensions, and regular expressions. DSLs can increase human comprehension by representing the desired result directly.
And if you call in the next fifteen minutes, you’ll membership in the Pattern Matching family at no extra cost!
There’s another significant opportunity for writing code that increases human comprehension. We saw how to write code where the form of the code resembles its result. You can also write code where the form of the code resembles the data it consumes.
In ML, patterns allow us to make our functions resemble the different values they consume:
fun factorial 0 = 1
| factorial n = n * factorial (n - 1)
If you are not familiar with pattern matching, and especially with how languages like ML and Haskell combine patterns with their type checking system, maybe today is the day to spend a little time looking into this powerful idea for making comprehensible programs.
- In my personal experience, “favouring human comprehension” does not mean favouring readability over writability—in order to write a program that solves a problem, I have to understand the solution, so comprehensibility applies to the act of composing and of reading programs by humans.
Now about machines: In this day and age, “The convenience of the machine” is often a way of saying, “the convenience of the layer of abstraction just below your program.” In a sense, every layer of abstraction above the silicon is a kind of virtual machine.
“Remember, it’s all software, it just depends on when you crystallize it.”—Alan Kay, as quoted by Andy Hertzfeld - List Interpolation actually predates String Interpolation, but most people recognize String Interpolation. Lispers have a little thing called a quasiquote or backquote that builds lists or vectors in a template form.
- Early feedback suggested this is a poor example of a regular expression, because it looks obtuse. I could have selected something much simpler, however I wanted something that really would be incredibly obtuse if you tried to code it procedurally. (Not counting using built-in library functions for parsing dates, of course).
The point is that this regex is readable, and you can see out all of the special cases, right where they belong in their place in the pattern. If readers can post some imperative code that does the same thing in a more readable form, that would be a very interesting lesson.
Labels: popular
Wednesday, April 25, 2007
Rails-style creators in Java, or, how I learned to stop worrying and love anonymous inner classes
Let’s begin with a well-known problem: creating a
Although this works, the problem with the naïve code is that it does not say with conviction that the two
Most Java programmers1 are familiar with the Map Initializer Idiom:
This creates a new
If you’re into the details, it actually creates a new anonymous inner class that extends
Note that your new Map isn’t exactly equal to any HashMap, because it has a different class. That sometimes matters.
POJOs
Many Java programmers labour with applications where the original architect wielded the Golden POJO Hammer: absolutely everything in the application looked like a POJO nail. I work with one such code base: it is obviously a traditional Procedural application. Getting anything done involves calling a global procedure and passing in a bunch of arguments.
The original architects worked for one of those Global Services companies, and you can’t charge hundreds of dollars an hour2 writing programs that our grandparents would recognize from the sixties. So to add a layer of OO, they turned every procedure call into a method, so a simple call like:
became:
(The nice thing about using this “OO Style” is that you get named parameters and multiple return values. I shall leave it to the static type checking enthusiasts to point out the drawbacks of this approach.)
Well, we can use the same initializer idiom with POJOs like
A Little Java, a Few Patterns is brought to you by the authors of The Little Schemer
, a book that teaches recursion and first-class functions: it is no surprise to discover that their book about Java eschews the same old, same old Hello World approach in favour of teaching deep ideas about Object-Oriented design and Pattern-Oriented design using Java as the language of instruction.
Again, you get a more literate snippet of code: the initialization and invocation all belong together, and you have put them together. If you move this around, you won’t drop an important line by mistake. And you get to save some keystrokes if there are a lot of fields to initialize.
If you dare to use
I prefer that form, it looks a lot more like what you are trying to say: this field has this value for this
Remember, your new object is an instance of an anonymous inner class, not of the original POJO class. This matters greatly if you test for class membership with
What does this have to do with Rails?
This is where we could go off on a long essay about how using things like Lisp, Smalltalk, and Ruby on Rails opens your mind to possibilities. That when you get used to
But honestly, you knew that already, didn’t you?
Update: Writing programs for people to read.
Map that is to be pre-populated with a few values. Here is some naïve code that creates a Map and then puts two values into it:
final Map<String, Object> mm = new HashMap<String, Object>();
mm.put("foo", "Strive To Finish Up");
mm.put("bar", "Public House");
Although this works, the problem with the naïve code is that it does not say with conviction that the two
put calls are part of the creation of the Map. If you move code around, it’s easy to drop a line. This code is literal, but it is not literate. Most Java programmers1 are familiar with the Map Initializer Idiom:
final Map<String, Object> m = new HashMap<String, Object>() {{
put("bar", "saloon");
put("bash", 7);
}};
This creates a new
Map and populates it with two members. This is a big improvement. The initialization is clearly embedded in the line of code that creates the Map. Thanks to a small syntax hack, it is (by Java standards) concise.If you’re into the details, it actually creates a new anonymous inner class that extends
HashMap. The inner class doesn’t add any new instance members, but it does contain an initializer: code between braces is run when instances are initialized. That’s why there are double braces: the outer set delineates the body of the anonymous inner class, the inner set delineates the initializer block.Note that your new Map isn’t exactly equal to any HashMap, because it has a different class. That sometimes matters.
POJOs
Many Java programmers labour with applications where the original architect wielded the Golden POJO Hammer: absolutely everything in the application looked like a POJO nail. I work with one such code base: it is obviously a traditional Procedural application. Getting anything done involves calling a global procedure and passing in a bunch of arguments.
The original architects worked for one of those Global Services companies, and you can’t charge hundreds of dollars an hour2 writing programs that our grandparents would recognize from the sixties. So to add a layer of OO, they turned every procedure call into a method, so a simple call like:
final BigDecimal balance = AccountModule.getAccountBalance("12345-678");
became:
final BalanceDoer doer = new BalanceDoer();
doer.setAccountNumber("12345-678");
doer.doit();
final BigDecimal balance = doer.getBalance();
(The nice thing about using this “OO Style” is that you get named parameters and multiple return values. I shall leave it to the static type checking enthusiasts to point out the drawbacks of this approach.)
Well, we can use the same initializer idiom with POJOs like
BalanceDoer (although you may have to move doit() outside of the initializer if you need checked exceptions):
final BalanceDoer doer = new BalanceDoer() {{
setAccountNumber("12345-678");
doit();
}};
final BigDecimal balance = doer.getBalance();
A Little Java, a Few Patterns is brought to you by the authors of The Little Schemer
, a book that teaches recursion and first-class functions: it is no surprise to discover that their book about Java eschews the same old, same old Hello World approach in favour of teaching deep ideas about Object-Oriented design and Pattern-Oriented design using Java as the language of instruction.If you dare to use
protected fields in POJOs (this is heresy to the “lock everything down so that other programmers subclassing your stuff can’t actually change anything” zealots), you can even write accountNumber = "12345-678"; in the initializer instead of using a setter.I prefer that form, it looks a lot more like what you are trying to say: this field has this value for this
doit call. That may be a matter of taste, or I may be overlooking something important.Remember, your new object is an instance of an anonymous inner class, not of the original POJO class. This matters greatly if you test for class membership with
equals instead of substitutability with instanceof.What does this have to do with Rails?
This is where we could go off on a long essay about how using things like Lisp, Smalltalk, and Ruby on Rails opens your mind to possibilities. That when you get used to
MyModel.create(:foo => 'Shove That Fish Under'), you look for ways to make your Java code easier, and so forth.But honestly, you knew that already, didn’t you?
Update: Writing programs for people to read.
- Where by “most,” I mean those who haven’t been hiding under the “Java-programs-must-only-contain-approved®-design-patterns: all-other-idioms-are-considered-hard-to-read-by-mediocre-colleagues” rock.
In my experience, that is the majority of good programmers. If reading blogs convinces you otherwise, remember that many of the best people are too busy building good stuff to write about building good stuff.
Update: A commenter expressed some surprise that this is a well-known idiom. Have a look at Double Brace Initialization.
The other Java people, the ones with time on their hands, or the ones that consider themselves “too good to program,” are the ones that write posts explaining why Java programs must be dumbed down to the lowest common denominator. I also blog. Draw your own conclusions from the evidence. - Not this company, although that’s an amusing post.
Labels: java
Saturday, April 21, 2007
We don't need no stinkin' Scientific Method
Update I:
This post has been removed.
Originally, it was a critique of Does Functional Programming Really Matter?. However, since I wrote the original post, the authors have added a disclaimer—this is not a real attempt at a scientific paper—it's just a class project. Speaking for myself, I didn't believe the conclusions of this paper even when I wrote it, and doubly so now—to their document.
Under the circumstances, there is nothing left to dispute and I have removed my words.
I’ve been asked why I didn’t leave the critique on line so that people can “see what the fuss was all about.” Here’s the thing: now that the document has that disclaimer front and centre, the most interesting things to talk about have to do with Universities and grades and intellectual rigor and a bunch of other things that are not about programming.
Since this is a programming blog... this was an easy decision. If the original document was not written in earnest, it’s no longer of interest to me.
Update II:
All right, all right, I give. Here’s what I originally wrote, more or less. Remember, when I wrote this there was no disclaimer on the original article, so I was under the impression that the authors actually believed what they were saying (imagine that), and that the authors were writing a paper to academic standards.
It turns out that’s not the case, so now I’m the one making disclaimers. The following represented my view given the information available at the time. Now that I have new information, my belief is that the paper is a NOOP: It says, in effect, “the following is not true: X, Y, Z.” Such a statement is neither supportable nor refutable.
Anyhoo, here’s what I still have of the original post:
We don’t need no stinkin’ Scientific Method
Here’s a paper worth reading: “Does Functional Programming Really Matter? Two Approaches to Comparing Functional and Object-Oriented Programming.”
The authors show how the important ideas in Why Functional Programming Matters can be reproduced in Java programs.
Let me summarize the paper:
Despite the fact that the document is formulated in a pseudo-academic style, I personally conclude this is junk science. I don’t argue with the authors’ conclusions: I enjoy writing mixed programs in Ruby, and on this very blog I showed how to emulate lazy evaluation using objects.
I do think it’s valuable to show techniques like this. I think it reaches out to the Blub community and shows them that you can expand your horizons without having to throw away everything you’ve learned about your current programming language.
If it gets even one person to read WhyFP for themselves, it’s a net win to share these thoughts with the world.
But conducting research with a bias, performing an experiment that disproves your conjecture, then hand waving the experiment’s results away is not science. It’s just an opinion, nothing more, no different than the stuff I write here in raganwald.
The value of the authors’ academic experience ought to be to teach them how to do basic scientific research.
Where is the study conducted on carefully balanced groups, some who complete a task in pure idiomatic Java, some who complete the same task in Haskell, and some who mix techniques?
Where are the tables showing comparative program lengths, running times, average number of bugs needing correction, or other hard metrics comparing programs to each other?
This “paper” should not be confused with science.
Originally, it was a critique of Does Functional Programming Really Matter?. However, since I wrote the original post, the authors have added a disclaimer—this is not a real attempt at a scientific paper—it's just a class project. Speaking for myself, I didn't believe the conclusions of this paper even when I wrote it, and doubly so now—to their document.
Under the circumstances, there is nothing left to dispute and I have removed my words.
I’ve been asked why I didn’t leave the critique on line so that people can “see what the fuss was all about.” Here’s the thing: now that the document has that disclaimer front and centre, the most interesting things to talk about have to do with Universities and grades and intellectual rigor and a bunch of other things that are not about programming.
Since this is a programming blog... this was an easy decision. If the original document was not written in earnest, it’s no longer of interest to me.
Update II:
All right, all right, I give. Here’s what I originally wrote, more or less. Remember, when I wrote this there was no disclaimer on the original article, so I was under the impression that the authors actually believed what they were saying (imagine that), and that the authors were writing a paper to academic standards.
It turns out that’s not the case, so now I’m the one making disclaimers. The following represented my view given the information available at the time. Now that I have new information, my belief is that the paper is a NOOP: It says, in effect, “the following is not true: X, Y, Z.” Such a statement is neither supportable nor refutable.
Anyhoo, here’s what I still have of the original post:
We don’t need no stinkin’ Scientific Method
Here’s a paper worth reading: “Does Functional Programming Really Matter? Two Approaches to Comparing Functional and Object-Oriented Programming.”
The authors show how the important ideas in Why Functional Programming Matters can be reproduced in Java programs.
Let me summarize the paper:
Java is Turing Complete. Therefore, all of the ideas in FP can be reproduced in Java. We show this by Greenspunning the important ideas in WhyFP. In essence, we show how to write a poorly specified, buggy implementation, of half of Haskell in Java.
We discover that Java is a cumbersome language for implementing functional programming. Instead of stopping right there, we show our bias by saying that writing programs in an object-oriented language is superior to a purely functional approach, but excuse our problems by saying that Java is at fault, not the premise of embedding FP in OOP.
We do not give examples of embedding FP in other OOP languages that might have radically different models, such as Ruby, SmallTalk, Self, Dylan, Ocaml, or CLOS, leaving the reader to perform their own experimentation. But we claim that a mixed approach is obviously superior to a pure FP approach.
Despite the fact that the document is formulated in a pseudo-academic style, I personally conclude this is junk science. I don’t argue with the authors’ conclusions: I enjoy writing mixed programs in Ruby, and on this very blog I showed how to emulate lazy evaluation using objects.
I do think it’s valuable to show techniques like this. I think it reaches out to the Blub community and shows them that you can expand your horizons without having to throw away everything you’ve learned about your current programming language.
If it gets even one person to read WhyFP for themselves, it’s a net win to share these thoughts with the world.
But conducting research with a bias, performing an experiment that disproves your conjecture, then hand waving the experiment’s results away is not science. It’s just an opinion, nothing more, no different than the stuff I write here in raganwald.
The value of the authors’ academic experience ought to be to teach them how to do basic scientific research.
Where is the study conducted on carefully balanced groups, some who complete a task in pure idiomatic Java, some who complete the same task in Haskell, and some who mix techniques?
Where are the tables showing comparative program lengths, running times, average number of bugs needing correction, or other hard metrics comparing programs to each other?
This “paper” should not be confused with science.
Friday, April 20, 2007
Recursion
In a certain University’s Computer Science program, you have a choice between following a “Theoretical Computer Science” track and a “Computer Engineering” track. The theoretical track starts with Scheme, moves into ML and Haskell, and drops into languages like Joy along the way for constructing certain proofs.
The practical track is a fairly standard JavaSchools approach, starting with Java, moving smoothly into Java with generics, and finishing with a big XML bang.
Most students entering the program have no trouble selecting the best track for themselves. The vast majority take the engineering course, mostly motivated by the promise of being sent into the bowels of BigCo on work terms. They pack into cavernous lecture halls and memorize design patterns, then spend days typing up verbose “Hello World” programs on their Dell laptops. The highly nerd-oriented remainder tend to jump into the theory track. They’re the ones reading “Good Math, Bad Math” over WiFi on their MacBooks.
A lonely few don’t know quite what to do. They might want to start a company, they might want to become consultants, and they enjoy a little recreational computing. They’re the ones who read raganwald, as a matter of fact. To help them out, the administration has constructed a little aptitude test.
They are placed in a testing hall, and each applicant is given two numbered envelopes. They are told that each envelope contains instructions. They are to follow them as best they can. The proctor calls out “Open the first envelope,” and they get started.
Inside is a piece of paper torn into large shards. The paper has writing on it, but you can’t read the instructions without piecing the paper back together. The students busy themselves with the puzzle, and in a few minutes almost all have fit the pieces back together and can read the single sentence on the page: “open the second envelope and follow its instructions.”
Well, this is a time limited examination and they immediately open the second envelope. Inside is a single sheet of paper with writing on it. And do you know what? Most of the applicants follow its instructions: they write their name and student number on the back of the paper and hand it into the proctor. These students are immediately sent into the Computer Engineering track, where they go on to be fine members of our profession: intelligent and practical.
A few, however, open the second envelope and their eyes light up immediately. Without pausing, they tear the page into strips, reducing it to a problem they have already solved!
The proctor guides these students gently from the room, and they are marked down for Theoretical Computer Science.
And we got Sheena
The practical track is a fairly standard JavaSchools approach, starting with Java, moving smoothly into Java with generics, and finishing with a big XML bang.
Most students entering the program have no trouble selecting the best track for themselves. The vast majority take the engineering course, mostly motivated by the promise of being sent into the bowels of BigCo on work terms. They pack into cavernous lecture halls and memorize design patterns, then spend days typing up verbose “Hello World” programs on their Dell laptops. The highly nerd-oriented remainder tend to jump into the theory track. They’re the ones reading “Good Math, Bad Math” over WiFi on their MacBooks.
A lonely few don’t know quite what to do. They might want to start a company, they might want to become consultants, and they enjoy a little recreational computing. They’re the ones who read raganwald, as a matter of fact. To help them out, the administration has constructed a little aptitude test.
They are placed in a testing hall, and each applicant is given two numbered envelopes. They are told that each envelope contains instructions. They are to follow them as best they can. The proctor calls out “Open the first envelope,” and they get started.
Inside is a piece of paper torn into large shards. The paper has writing on it, but you can’t read the instructions without piecing the paper back together. The students busy themselves with the puzzle, and in a few minutes almost all have fit the pieces back together and can read the single sentence on the page: “open the second envelope and follow its instructions.”
Well, this is a time limited examination and they immediately open the second envelope. Inside is a single sheet of paper with writing on it. And do you know what? Most of the applicants follow its instructions: they write their name and student number on the back of the paper and hand it into the proctor. These students are immediately sent into the Computer Engineering track, where they go on to be fine members of our profession: intelligent and practical.
A few, however, open the second envelope and their eyes light up immediately. Without pausing, they tear the page into strips, reducing it to a problem they have already solved!
The proctor guides these students gently from the room, and they are marked down for Theoretical Computer Science.
And we got Sheena
99% of programmers are law-abiding citizens...
When dispensing advice, people often pluck the proportion “99%” out of the air as a way of saying “overwhelmingly likely.” As in:
Now 99% is obviously a junk number, just like 199/200. But let’s hand wave and say that it’s close enough to the truth. What does that mean?
For example, if you’re deciding how to build persistence into a web application, what does “99%” tell us about using an RDBMS? I’d say, not very much. For starters, if you build seventy web application in your entire career, there’s a fifty-fifty chance one of them should have used something other than an RDBMS.
That tells me that you can’t discard other options and just say that “every web application should use an RDBMS.” 99% is a lot of them, but not so many that we can afford to ignore the 1%.
Society of Mind is Marvin Minsky’s legendary explanation of how the human brain solves problems. It’s a fascinating book, not least because of its unusual structure: lasvishly illustrated with diagrams, each page is a self-contained chapter and links between ideas form a dense network rather than a linear chain.
If we were buying one hundred stocks, we would do very well if ninety-nine of them make money and one loses… unless the one loser loses us more money than the other ninety-nine make for us. When it comes to technology choices, we don’t just make a single wild bet (“every application will have an RDBMS”). We have the option of investigating the application and our options before making a choice.
So when I read a SWAG like “iteration works just fine for 99% of the things you do with collections,” I make a mental note to look for the 1% of the cases where iteration doesn’t work.
They may be few and far between, but they’ll pop up enough to make knowing how to use map, reduce, and recursion worthwhile.
That being said, “99% of businesses should run on lock-in, proprietary operating systems and platforms” is a very interesting case. There’s really very little cost in learning how to roll your own persistence for the cases where an RDBMS is not the right choice (even if you need transactional semantics). And it is surprisingly easy to use map, reduce, and recursion… it turns out to be easier than iteration, not harder.
But learning entire platforms is an expensive proposition. It may make sense to focus on one platform where you can accumulate high expertise. After all, a programming language takes ten years to master, can an entire OS and its ecosystem be any easier? And even if it is possible to learn a new platform on the fly, employers may prefer to hire for experience rather than pay you to learn.
That doesn’t tell me that you should go with the 99% solution. The 1% of companies out there that are best served with other technologies still need to hire employees, engage suppliers, and purchase software that runs on their systems. Game theory tells us that the optimum strategy for a worker, contractor, or supplier is to roll a one hundred sided die and pick the 1% platform if they roll a “one.”
What I find really interesting is that the marketplace is highly inefficient. Given one platform having 99% share, far more than 99% of the people will choose to “specialize” in the 99% solution, creating a commodity marketplace. The very few that serve the 1% of the market enjoy disproportionally higher salaries and profits.
For this reason, when I read that 99% of the web applications should use an RDBMS, I am very interested in the 1% that shouldn’t… and figuring out how I can manoeuvre myself into a position to build one. And the news that one company has a near-monopolistic lock on the business operating system business? I consider this an opportunity for those of us comfortable with the alternatives.
So the next time you hear the magic words, “99% of…”, I encourage you to do as I do: start asking questions about the other one percent.
- 99% of the web applications out there should use an RDBMS as their back end store, not some roll-your-own persistence mechanism, or;
- Iteration works just fine for 99% of the things you do with collections, or;
- 99% of businesses should run on lock-in, proprietary operating systems and platforms.
Now 99% is obviously a junk number, just like 199/200. But let’s hand wave and say that it’s close enough to the truth. What does that mean?
For example, if you’re deciding how to build persistence into a web application, what does “99%” tell us about using an RDBMS? I’d say, not very much. For starters, if you build seventy web application in your entire career, there’s a fifty-fifty chance one of them should have used something other than an RDBMS.
That tells me that you can’t discard other options and just say that “every web application should use an RDBMS.” 99% is a lot of them, but not so many that we can afford to ignore the 1%.
Society of Mind
is Marvin Minsky’s legendary explanation of how the human brain solves problems. It’s a fascinating book, not least because of its unusual structure: lasvishly illustrated with diagrams, each page is a self-contained chapter and links between ideas form a dense network rather than a linear chain.So when I read a SWAG like “iteration works just fine for 99% of the things you do with collections,” I make a mental note to look for the 1% of the cases where iteration doesn’t work.
They may be few and far between, but they’ll pop up enough to make knowing how to use map, reduce, and recursion worthwhile.
That being said, “99% of businesses should run on lock-in, proprietary operating systems and platforms” is a very interesting case. There’s really very little cost in learning how to roll your own persistence for the cases where an RDBMS is not the right choice (even if you need transactional semantics). And it is surprisingly easy to use map, reduce, and recursion… it turns out to be easier than iteration, not harder.
But learning entire platforms is an expensive proposition. It may make sense to focus on one platform where you can accumulate high expertise. After all, a programming language takes ten years to master, can an entire OS and its ecosystem be any easier? And even if it is possible to learn a new platform on the fly, employers may prefer to hire for experience rather than pay you to learn.
That doesn’t tell me that you should go with the 99% solution. The 1% of companies out there that are best served with other technologies still need to hire employees, engage suppliers, and purchase software that runs on their systems. Game theory tells us that the optimum strategy for a worker, contractor, or supplier is to roll a one hundred sided die and pick the 1% platform if they roll a “one.”
What I find really interesting is that the marketplace is highly inefficient. Given one platform having 99% share, far more than 99% of the people will choose to “specialize” in the 99% solution, creating a commodity marketplace. The very few that serve the 1% of the market enjoy disproportionally higher salaries and profits.
For this reason, when I read that 99% of the web applications should use an RDBMS, I am very interested in the 1% that shouldn’t… and figuring out how I can manoeuvre myself into a position to build one. And the news that one company has a near-monopolistic lock on the business operating system business? I consider this an opportunity for those of us comfortable with the alternatives.
So the next time you hear the magic words, “99% of…”, I encourage you to do as I do: start asking questions about the other one percent.
Thursday, April 19, 2007
Pop culture lives in the present, it doesn't really live in the future or want to know about great ideas from the past
What other treasure troves of useful knowledge and wisdom are out there? Please post suggestions in the comments! (By the way, you can embed HTML anchors in comments, so don’t be shy about including links).
In the last few years I’ve been asking computer scientists and programmers whether they’ve ever typed E-N-G-E-L-B-A-R-T into Google—and none of them have. I don’t think you could find a physicist who has not gone back and tried to find out what Newton actually did. It’s unimaginable. Yet the computing profession acts as if there isn’t anything to learn from the past, so most people haven’t gone back and referenced what Engelbart thought.
The things that are wrong with the Web today are due to this lack of curiosity in the computing profession. And it’s very characteristic of a pop culture. Pop culture lives in the present; it doesn’t really live in the future or want to know about great ideas from the past.
I’m saying there’s a lot of useful knowledge and wisdom out there for anybody who is curious, and who takes the time to do something other than just executing on some current plan. Cicero said, “Who knows only his own generation remains always a child.” People who live in the present often wind up exploiting the present to an extent that it starts removing the possibility of having a future.
—Alan Kay: The PC Must Be Revamped—Now, via discuss.joelonsoftware.com.
What other treasure troves of useful knowledge and wisdom are out there? Please post suggestions in the comments! (By the way, you can embed HTML anchors in comments, so don’t be shy about including links).
Wednesday, April 18, 2007
Yeomanry and Exploding Brains
Note: I wrote this post very quickly last evening, in an almost stream-of-conciousness style. I had just endured some particularly frustrating client issues, and I really, really wanted to focus on a few bright moments that I had enjoyed that day. You know, trying to be a good dog.
After publishing it, I felt unsatisfied with the post. It didn’t feel like I was saying or thinking anything particularly new, just the same old, same old thing about stretching the mind and looking for the elusive “quality without a name” that lies behind well-written software.
So I yanked it and went home. I was talking with a friend who writes for a living, and she quoted a great aphorism: “All writing is rewriting.” She suggested I rework it, not discard it. So here it is again, and I hope to rework it until I’m satisfied. The first major change will probably be to cut it in half.
We’ll see about the rest.
I finished reading The Little MLer
this morning. This is a wonderful book. It’s obviously valuable if you want to learn something about SML or Ocaml. But having read it, I’d argue that it’s a great introduction to strongly typed functional languages, period.
In fact, it’s probably the very best first book to read before learning Haskell if you haven’t already used a language that combines first-class functions and strong, static typing. If you read this first, you can concentrate on lazy evaluation and monads without having to grok currying and other first-class functional ideas at the same time.
Stars, Arrows, and Elegance
Two things jumped out at me this morning. The first was chapter eight, “Bows and Arrows.” This was an introduction to currying and partial function application. When I say it that way, it sounds rather dry. But it rolled along quite pleasantly. The material will be familiar to anyone with a passing familiarity with the idea of a function returning a function. It has the same ideas you’ll find in Structure and Interpretation of Computer Programs
, but delivered with static typing.
This alone is worth the price of the book: I came to the subject with an impoverished experience set: I had used latently typed languages like Scheme and Ruby, as well as static and declaratively typed languages like C++ and Java. Although I knew “intellectually” how languages like Ocaml and Haskell deliver some of the power of Scheme along with the benefits of compile-time type checking, there is no substitute for walking through the examples to spark the “Aha!” feeling. Incredibly, chapter eight got better. It finished with a real bang:
The examples in the chapter constructed various functions that took multiple arguments, then constructed their equivalents by combining smaller functions with partial evaluation. Then it closed with The Eighth Moral:
In other words, first-class functions let you break monolithic functions that take a lot of arguments into smaller components that can be combined and recombined. This is a deep idea in writing programs. We often see the tension between programs as collections of small pieces that fit together and black boxes that are configured by means of switches and dials on the outside.
This is a good tension: we call the black box approach “abstraction” and we call the combinatory approach “bottom-up programming.” Both produce programs that are expressed economically, but the black box does so by sweeping the complexity “under the carpet” and bottom-up programming does so by identifying and combining the simple constituent elements of a program in an economical way.
I think of black box abstractions like inventing new nouns for new ideas. A web server? We’ll call that a “Fizbuhlsweepnik.” A REST server? We’ll call that a “Harkonnensmelt.” Whereas I think of bottom-up programming as inventing smaller nouns, verbs, adjectives, and adverbs, so we can say a “web server” or a “REST server” or even a “Caching REST server.” Being able to combine the small words gives us more to say with much less effort. (I am not a linguist, so this argument is suspect!)
Giles Bowkett nailed this idea when he wondered whether languages like Scheme are actually easier to learn than languages like Java.1 This makes a lot of sense from the perspective of simplicity. Pure Scheme is based on just five axiomatic “special forms” plus macros to build almost everything else out of the five axioms. That’s a lot easier to learn than a language that tries to provide the same power with a plethora of knobs and switches like
This tells us something about ecosystems versus languages. Lately, quite reasonable people have wondered aloud whether the ecosystem of frameworks and libraries are more important than the languages themselves. As we’re beginning to see with multiple languages running on common VMs, the point may become moot very shortly. But for now, it is easy to see that libraries tend to look like black boxes. When they do exactly what you need, they save time and trouble. But they tend to be wide and shallow, just like Java. They have a lot of knobs and switches.
Good languages, OTOH, give you power that can be combined and recombined like first-class functions. They let you tame the black boxes by wrapping up the parts you need and combining them in simple ways. With currying, a function with twenty arguments can be transformed into a function with one argument. With powerful languages, a baroque library can be deftly specialized to fit your program.
My Brain Explodes
In the same chapter, the authors talked about extensional equivalence.2 This is the idea of two functions that can have the exact same behaviour as each other, even though they are defined in different ways. As the authors point out, proving that two functions are extensionally equivalent is impossible in the general case.
That shouldn’t stop anyone with a taste for reading esoteric programming weblogs.3 Something was tickling the back of my mind about this problem. Yes, it had to do with rewinding into the past to correct mistakes, something like backtracking in a reasoning system.
So perhaps we want an equivalence function that takes two functions “p” and “q” and returns a Boolean. Both functions must have the same signature, obviously. How can we write such a function? Here’s one approach: Scan the history of the program for calls to
If there are no differences, return
That does not guarantee equivalence, of course, they may differ for some set of inputs that you never tested in your program. But if they are equivalent for the set of inputs you actually run, what do you care if they differ for inputs outside of the “event horizon” of your program?
Now quite honestly, I cannot think of a practical use for this “rewinding extensional equivalence predicate.” I mention it only because the thought captures for me one of the benefits of reading certain kinds of books: they provoke you into thinking about new things in new ways. They may be useful immediately, or they may pop up down the road. Or maybe they were just a passing thought that amounted to nothing of grave importance.
But overall, my experience is that people and writing that pushes you into unfamiliar thinking territory is good for you. And in that spirit, I recommend The Little MLer4 with as much enthusiasm as I recommend writing your own version of the Y Combinator.
After publishing it, I felt unsatisfied with the post. It didn’t feel like I was saying or thinking anything particularly new, just the same old, same old thing about stretching the mind and looking for the elusive “quality without a name” that lies behind well-written software.
So I yanked it and went home. I was talking with a friend who writes for a living, and she quoted a great aphorism: “All writing is rewriting.” She suggested I rework it, not discard it. So here it is again, and I hope to rework it until I’m satisfied. The first major change will probably be to cut it in half.
We’ll see about the rest.
I finished reading The Little MLer
this morning. This is a wonderful book. It’s obviously valuable if you want to learn something about SML or Ocaml. But having read it, I’d argue that it’s a great introduction to strongly typed functional languages, period.In fact, it’s probably the very best first book to read before learning Haskell if you haven’t already used a language that combines first-class functions and strong, static typing. If you read this first, you can concentrate on lazy evaluation and monads without having to grok currying and other first-class functional ideas at the same time.
Stars, Arrows, and Elegance
Two things jumped out at me this morning. The first was chapter eight, “Bows and Arrows.” This was an introduction to currying and partial function application. When I say it that way, it sounds rather dry. But it rolled along quite pleasantly. The material will be familiar to anyone with a passing familiarity with the idea of a function returning a function. It has the same ideas you’ll find in Structure and Interpretation of Computer Programs
, but delivered with static typing.This alone is worth the price of the book: I came to the subject with an impoverished experience set: I had used latently typed languages like Scheme and Ruby, as well as static and declaratively typed languages like C++ and Java. Although I knew “intellectually” how languages like Ocaml and Haskell deliver some of the power of Scheme along with the benefits of compile-time type checking, there is no substitute for walking through the examples to spark the “Aha!” feeling. Incredibly, chapter eight got better. It finished with a real bang:
The examples in the chapter constructed various functions that took multiple arguments, then constructed their equivalents by combining smaller functions with partial evaluation. Then it closed with The Eighth Moral:
Replace stars by arrows to reduce the number of values consumed and to increase the generality of the function defined.
In other words, first-class functions let you break monolithic functions that take a lot of arguments into smaller components that can be combined and recombined. This is a deep idea in writing programs. We often see the tension between programs as collections of small pieces that fit together and black boxes that are configured by means of switches and dials on the outside.
This is a good tension: we call the black box approach “abstraction” and we call the combinatory approach “bottom-up programming.” Both produce programs that are expressed economically, but the black box does so by sweeping the complexity “under the carpet” and bottom-up programming does so by identifying and combining the simple constituent elements of a program in an economical way.
I think of black box abstractions like inventing new nouns for new ideas. A web server? We’ll call that a “Fizbuhlsweepnik.” A REST server? We’ll call that a “Harkonnensmelt.” Whereas I think of bottom-up programming as inventing smaller nouns, verbs, adjectives, and adverbs, so we can say a “web server” or a “REST server” or even a “Caching REST server.” Being able to combine the small words gives us more to say with much less effort. (I am not a linguist, so this argument is suspect!)
Giles Bowkett nailed this idea when he wondered whether languages like Scheme are actually easier to learn than languages like Java.1 This makes a lot of sense from the perspective of simplicity. Pure Scheme is based on just five axiomatic “special forms” plus macros to build almost everything else out of the five axioms. That’s a lot easier to learn than a language that tries to provide the same power with a plethora of knobs and switches like
package, static, and main.This tells us something about ecosystems versus languages. Lately, quite reasonable people have wondered aloud whether the ecosystem of frameworks and libraries are more important than the languages themselves. As we’re beginning to see with multiple languages running on common VMs, the point may become moot very shortly. But for now, it is easy to see that libraries tend to look like black boxes. When they do exactly what you need, they save time and trouble. But they tend to be wide and shallow, just like Java. They have a lot of knobs and switches.
Good languages, OTOH, give you power that can be combined and recombined like first-class functions. They let you tame the black boxes by wrapping up the parts you need and combining them in simple ways. With currying, a function with twenty arguments can be transformed into a function with one argument. With powerful languages, a baroque library can be deftly specialized to fit your program.
My Brain Explodes
In the same chapter, the authors talked about extensional equivalence.2 This is the idea of two functions that can have the exact same behaviour as each other, even though they are defined in different ways. As the authors point out, proving that two functions are extensionally equivalent is impossible in the general case.
That shouldn’t stop anyone with a taste for reading esoteric programming weblogs.3 Something was tickling the back of my mind about this problem. Yes, it had to do with rewinding into the past to correct mistakes, something like backtracking in a reasoning system.
So perhaps we want an equivalence function that takes two functions “p” and “q” and returns a Boolean. Both functions must have the same signature, obviously. How can we write such a function? Here’s one approach: Scan the history of the program for calls to
p. For each call, call q and compare the results. If they differ, return false. Do the same for each call to q, comparing its result to the result of calling p with the same arguments.If there are no differences, return
true. But wait, maybe your sample size is insufficient. No problem, continue forward in the program, and every time p or q are called in the future, compare the results from both functions again. If they are the same, continue on. But if they differ, rewind back to when the equivalence function was called and return false.That does not guarantee equivalence, of course, they may differ for some set of inputs that you never tested in your program. But if they are equivalent for the set of inputs you actually run, what do you care if they differ for inputs outside of the “event horizon” of your program?
Now quite honestly, I cannot think of a practical use for this “rewinding extensional equivalence predicate.” I mention it only because the thought captures for me one of the benefits of reading certain kinds of books: they provoke you into thinking about new things in new ways. They may be useful immediately, or they may pop up down the road. Or maybe they were just a passing thought that amounted to nothing of grave importance.
But overall, my experience is that people and writing that pushes you into unfamiliar thinking territory is good for you. And in that spirit, I recommend The Little MLer
4 with as much enthusiasm as I recommend writing your own version of the Y Combinator.- See also: Giles Bowkett turns language elitism upside down
- Equivalence has been on my mind recently!
- And you wonder why I have been doing this since the seventies but somehow managed to miss out on earning a Turing Award while utterly failing to amass a small private fortune?
- Judging by the click-throughs on my blog in the last year, there are plenty of people who can’t quite bring themselves to pick up a book about ML. Don’t fret, the authors have also written The Seasoned Schemer
for your first-class functional pleasure. In an effort to expand my own mind, I will be starting their book about logic programming, The Reasoned Schemer
tomorrow.
Ryan Tomayko on Friction and Frameworks
When I consider what contributed to the unravelling of J2EE, one thing that stands out is that it tried to do too much. The promise was that of infinite scalability based on tooling, which assumes that designing scalable systems is a general case problem. I now firmly believe that this is flawed reasoning. Frameworks don’t solve scalability problems, design solves scalability problems.
I picked up a word from Joe a few years back and find myself using it a lot: “friction.” When referring to framework and tooling, “friction” is a (subjective) measure of how much the tooling gets in your way when trying to solve a specific-case problem.
I’ve come to evaluate frameworks based on two rough metrics: how far the framework goes in solving the general case problem out of the box and how little friction the framework creates when you have to solve the specific-case problem yourself. When a framework finds a balance between these two areas, we call it “well designed.”
—Ryan Tomayko, Rails and Scaling with Multiple Databases
Having fun
I’m just going to keep trying to find interesting problems to work on, and if one of them happens to change the world, then great. And if not, at least I’ll have had fun trying to solve some hard problems.
—a comment from “28/w” on discuss.joelonsoftware.com
Labels: passion
Sunday, April 15, 2007
What does Barbara Liskov have to say about Equality in Java?
Erick Reid posted some code showing his standard implementations of
Here’s a shorter version of his equality method for a class,
The interesting part for me is the test for class equality:
This works when
For example:
Does this sound farfetched? What if it doesn’t even have any different members, it only varies in some subtle implementation way? For example, what if
All equalities are equal, but some are more equal than others
If you program in Java, you probably already know that
Value equality is where the interesting problem lies. There are two kinds of value equalities: physical equality (“these two are identical copies of the same object in every respect”) and logical equality (“for my purposes, these two are equivalent”).
A Little Java, a Few Patterns is brought to you by the authors of The Little Schemer, a book that teaches recursion and first-class functions, as well as The Little MLer, a book that teaches you how to design programs with a powerful strong, static type system.
So it is no surprise to discover that their book about Java eschews the same old, same old Hello World approach in favour of teaching deep ideas about Object-Oriented design and Pattern-Oriented design using Java as the language of instruction.
The basic problem here is that
(I think a lot of the problem starts when people conflate interfaces with classes. There’s a big difference between saying “this is the interface TempBean, and here is how to tell if any two TempBeans are equals to each other” and saying “this is an implementation of a TempBean, and if you want to know whether it is the exact same thing as another implementation, here is how to do it.”
The former ought to be very common, and the latter quite rare in OO programs.)
It isn’t easy to fix the physical equality problem. If you use the second form of code, you get an equals method that is not symmetric (thanks, Marc!). In the examples above,
This last question is another way of pointing out that equality is not an easy thing to define if you mix the notion of polymorphism into a language. Do you always want logical equality? I can easily think of code that would break horribly if you made a
What can we do about this?
To make equality adhere to the Liskov Substitution Method in a language like Java, you can’t make it an object method. One of the other cherished notions in OO design is that every object ought to know everything about its behaviour. But this objects can’t know how much detail a client wants in making the comparison.
The piece of code that ought to know how to compare two
Now you can write code like:
Without worrying about whether either variable holds a
equals and hashCode in Java (updated link). His implementations draw heavily on Joshua Bloch’s principles. I think he’s done a great job in implementing the Java standard implementation of equality. On the other hand, I’m a little disquieted by the way equality works in Java.Here’s a shorter version of his equality method for a class,
TempBean, that has members _foo, and _bar:
public boolean equals(Object object) {
if (object != this) {
if (object != null && getClass().equals(object.getClass())) {
final TempBean other = (TempBean) object;
return (_foo == null ? other._foo == null : _foo.equals(other._foo)) &&
(_bar == null ? other._bar == null : _bar.equals(other._bar));
}
return false;
}
return true;
}
The interesting part for me is the test for class equality:
getClass().equals(object.getClass()). Compare and contrast to:
public boolean equals(Object object) {
if (object != this) {
if (object != null && object instanceof TempBean) {
final TempBean other = (TempBean) object;
return (_foo == null ? other._foo == null : _foo.equals(other._foo)) &&
(_bar == null ? other._bar == null : _bar.equals(other._bar));
}
return false;
}
return true;
}
This works when
object is a TempBean. That’s almost the same as the first code. It’s different when object is an instance of TempBean but not a TempBean.For example:
void doSomethingSeussian (final TempBean thingOne) {
final TempBean thingTwo = TempBean.getThingFromBox(/* ... */);
if (thingTwo.equals(thingOne)) {
// ...
}
}
thingTwo is obviously a TempBean. Or is it? What does the factory method getThingFromBox do? And what if thingOne is an instance of a subclass of TempBean? What if it has exactly the same _foo and _bar as thingTwo? Why isn’t it equals? Does this sound farfetched? What if it doesn’t even have any different members, it only varies in some subtle implementation way? For example, what if
thingOne is a ThreadSafeTempBean that guarantees thread safety in a way that is otherwise transparent to clients? Or a MockTempBean that is used for unit tests?All equalities are equal, but some are more equal than others
If you program in Java, you probably already know that
== is not the same thing as equals. One measures identity , whether two objects are the exact same identical object in memory at the same location. (Unless they are those dratted primitives, in which case it measures value equality). Identity is almost useless in Java, it breaks all over the place, and that’s why it’s rightfully rare.Value equality is where the interesting problem lies. There are two kinds of value equalities: physical equality (“these two are identical copies of the same object in every respect”) and logical equality (“for my purposes, these two are equivalent”).
A Little Java, a Few Patterns is brought to you by the authors of The Little Schemer
, a book that teaches recursion and first-class functions, as well as The Little MLer, a book that teaches you how to design programs with a powerful strong, static type system.So it is no surprise to discover that their book about Java eschews the same old, same old Hello World approach in favour of teaching deep ideas about Object-Oriented design and Pattern-Oriented design using Java as the language of instruction.
equals captures physical equality, which ignores the Liskov Substitution Principle, one of the fundamental principles in OO design. It is leaking the implementation, just like a leaky abstraction.(I think a lot of the problem starts when people conflate interfaces with classes. There’s a big difference between saying “this is the interface TempBean, and here is how to tell if any two TempBeans are equals to each other” and saying “this is an implementation of a TempBean, and if you want to know whether it is the exact same thing as another implementation, here is how to do it.”
The former ought to be very common, and the latter quite rare in OO programs.)
It isn’t easy to fix the physical equality problem. If you use the second form of code, you get an equals method that is not symmetric (thanks, Marc!). In the examples above,
thingOne.eqauls(thingTwo) is not always the same as thingTwo.equals(thingOne)! And if you’re implementing a HashMap, which kind of equality do you want to use for deciding whether a key is already in the collection?This last question is another way of pointing out that equality is not an easy thing to define if you mix the notion of polymorphism into a language. Do you always want logical equality? I can easily think of code that would break horribly if you made a
HashMap that respected the Liskov Substitution Principle for keys. And I can also think of code where I want a map or set that respects the Liskov substitution principle.What can we do about this?
To make equality adhere to the Liskov Substitution Method in a language like Java, you can’t make it an object method. One of the other cherished notions in OO design is that every object ought to know everything about its behaviour. But this objects can’t know how much detail a client wants in making the comparison.
The piece of code that ought to know how to compare two
TempBeans is the TempBean class (which is also the TempBean interface in Java, but Java doesn’t allow code in interfaces). We’re off to a good start, the code for equals is in the TempBean class. But where we went wrong is making it an instance method. What happens if it’s a static method?
public static boolean equivalent(TeampBean left, TempBean right) {
if (left != right) {
if (left != null && right != null) {
return (left._foo == null ? right._foo == null : left._foo.equals(right._foo)) &&
(left._bar == null ? right._bar == null :left. _bar.equals(right._bar));
}
return false;
}
return true;
}
Now you can write code like:
void doSomethingSeussian (final TempBean thingOne) {
final TempBean thingTwo = TempBean.getThingFromBox(/* ... */);
if (TempBean.equivalent(thingTwo, thingOne)) {
// ...
}
}
Without worrying about whether either variable holds a
TempBean, a ThreadSafeTempBean, or a MockTempBean. It’s true that sometimes you care very deeply about the difference. But most of the time, you probably do not, and using an equals method that does care is wrong.Labels: java
Friday, April 13, 2007
From Abstraction to Zipf
Alpha…
Damien Katz raised an interesting question the other day: he wondered whether elements of computer programs followed a Zipf distribution. In other words, he wondered whether the most frequently used item occurred a lot more than the next most frequent, which occurs a lot more than the third most frequent, and so forth.
That’s an interesting question. Is it true? And if it is, what does that tell us about composing programs?
Looking at computer programs, some things seem to follow Zipf’s law and others don’t. In C++ programs, loop indices called
If we step up a level and look at idioms, my gut tells me that there is a strong Zipf distribution. Although each program will differ, some programs might make heavy use of lists, others of maps. Some might do a lot with closures, others with objects. These are fairly generic, of course.
If we have a look at the more domain-specific items in a program, we really see a Zipf distribution. Some things pop up again and again and again in a program, others are rare.
Why Abstract?1
The most important tool we have for composing programs is abstraction. When we create an abstraction for something, we get one and a half wins (a sesqui-win).
The Ruby Way is the perfect second Ruby book for serious programmers. The Ruby Way contains more than four hundred examples explaining how to implement advanced ideas like metaprogramming.
The full win is that we get to take a common element and place its responsibility in once place. For example, if your language gives you a
The half win is that we don’t need to understand its implementation, we only need to understand its interface. I honestly don’t know whether Ruby’s built-in
This is only half a win, because for anything too complicated to explain on a PowerPoint slide where you are promising the newest silver bullet, abstractions have a nasty habit of leaking. Leaky abstractions force you to understand the implementation to use them.
There are some drawbacks to abstractions. As noted, sometimes the abstraction leaks. In that case, you often have to look up what an abstraction does. If there was no abstraction and the implementation was right there in the middle of your code, you wouldn’t have to look it up. So when you see:
You obviously to need to know that
You get much the same thing if you build a Java class hierarchy that is umpteen levels deep festooned with abstract base classes, factories, and dependency injection. In one sense you get a really tight abstraction. In another sense, you have a big leak: you need to know its internals to get any real work done.
Another drawback to abstractions fall out of their strength. If you haven’t seen a particular abstraction before, you don’t know what it does and how it works. Contrary to popular hype, self-documenting names are not enough. If you are a Rails user, raise your hand if you can tell me what all of the various options for
The win (not having to know how it works) is also a loss (not knowing what it does).
An abstraction is an abstraction is an abstraction
I think most people agree that named subroutines (or functions, or procedures) are an excellent abstraction. First-class functions and anonymous functions seem to be an acquired taste (just one taste, and your programs will quickly acquire them). Objects—in the strong sense of polymorphic programs—are well-regarded abstractions.
What these all have in common is that these functional abstractions live happily within the syntax provided by the host programming language. They abstract function without abstracting syntax. For the most part, non-syntactic abstraction is uncontroversial.
There seems to be debate over syntactic abstraction. Macros, DSLs, and other means of writing your own mini-language provoke the wildest claims of productivity and equally baseless fears of unreadable, fragile, “magic” code built out of gossamer dreams. The basic “problem” with syntactic abstractions like
They are right in your face, especially if they are very brief. Consider:
Don’t bother searching for the
All the same, syntactic abstractions are just like functional abstractions. You get some wins, and you pay some costs in understanding and potential “leakiness.”
Zipf to the rescue
So should we zealously abstract everything we can? Or should we conservatively avoid “magic” like syntactic abstractions?
Every abstraction has a fixed learning cost. That cost is amortized over all of the instances we’ll encounter. So you need to learn how
An abstraction built into a framework like
The Art of the Metaobject Protocol is one of the most important books ever written on the subject of building abstractions with objects. If the idea that there is more than one way to structure objects and classes seems surprising, then learning about the Meta-Object protocol will teach you what your language has kept secret.
Of course, that distribution is self-similar: the abstractions within a program follow the same distribution as the abstractions within an organization. So even if you aren’t inventing a new programming language, Zipf can help.
Quite simply, it pays to aggressively abstract the few things that are encountered the most frequently. In a CRUD web application, schema relationships like
Note that we aren’t saying that
But should you create a DSL for list comprehensions in your CRUD application or just use the language’s built-in collections? I would say, you would need an application that uses an awful lot of lists before a syntactic abstraction for lists is a win.
It might be, but the nice thing is, it probably won’t be close: Zipf’s law tells us that each application only needs a very few new kinds of abstractions to get most of the benefits. There are only a few low-hanging fruits, but each is plump and juicy.
…Omega
I think it is a win to use aggressive abstraction techniques like metaprogramming, but only if you restrain yourself to abstracting the very few things that appear most frequently in your code base. The things that are used less frequently should be abstracted using less aggressive techniques.
The resulting program may not be magically 50% shorter than an unabstracted program, because the “long tail” of idioms and patterns are simply not worth abstracting away even though we have the tools for doing so.
You can probably tell whether a program has the proper level of abstraction just by checking its distribution.
If you find a big abstraction framework for one thing while frequently used idioms are expressed using patterns instead of abstractions, you are probably looking at an improperly abstracted program. You have to wade through verbiage to read everything, and the one time you don't need to abstract the code away, you have to chase definitions through indirection.
And in a well-written program, I would expect that the things that occur most frequently are expressed at the highest and most powerful levels of abstraction, while things that happen infrequently are expressed in a more direct and explicit way. Such a program would be easy to read throughout.
Damien Katz raised an interesting question the other day: he wondered whether elements of computer programs followed a Zipf distribution. In other words, he wondered whether the most frequently used item occurred a lot more than the next most frequent, which occurs a lot more than the third most frequent, and so forth.
That’s an interesting question. Is it true? And if it is, what does that tell us about composing programs?
Looking at computer programs, some things seem to follow Zipf’s law and others don’t. In C++ programs, loop indices called
i probably are an order of magnitude more common than those called j. Unless you use Apps Hungarian, of course. But are for loops that much more common than if statements? That might vary from place to place within a single program, but overall they might be roughly equal in frequency.If we step up a level and look at idioms, my gut tells me that there is a strong Zipf distribution. Although each program will differ, some programs might make heavy use of lists, others of maps. Some might do a lot with closures, others with objects. These are fairly generic, of course.
If we have a look at the more domain-specific items in a program, we really see a Zipf distribution. Some things pop up again and again and again in a program, others are rare.
Why Abstract?1
The most important tool we have for composing programs is abstraction. When we create an abstraction for something, we get one and a half wins (a sesqui-win).
The Ruby Way
is the perfect second Ruby book for serious programmers. The Ruby Way contains more than four hundred examples explaining how to implement advanced ideas like metaprogramming.map function or method, there is one place for the code that applies a function to each element of a collection and produces a collection of the results. Unlike a “pattern,” you don’t have to re-implement map every time you use it, you just use it. The centralization of responsibility in a single place is very powerful way to separate concerns.The half win is that we don’t need to understand its implementation, we only need to understand its interface. I honestly don’t know whether Ruby’s built-in
map method applies itself to a collection one at a time from the start to the end or in some other order. I suspect it’s from start to end for ordered collections, but I don’t know and I don’t have to know.This is only half a win, because for anything too complicated to explain on a PowerPoint slide where you are promising the newest silver bullet, abstractions have a nasty habit of leaking. Leaky abstractions force you to understand the implementation to use them.
There are some drawbacks to abstractions. As noted, sometimes the abstraction leaks. In that case, you often have to look up what an abstraction does. If there was no abstraction and the implementation was right there in the middle of your code, you wouldn’t have to look it up. So when you see:
class BlogPost << ActiveRecord::Base
has_many :comments
# ...
end
You obviously to need to know that
has_many creates methods like comments, comment_ids= and comments<< automagically for you. In fact, that is kind of the point of has_many. But if you are doing anything non-trivial, you also need to know whether has_many actually defined comments, comment_ids= and comments<< or whether it has merely modified BlogPost to handle those messages. In that sense, the abstraction leaks.You get much the same thing if you build a Java class hierarchy that is umpteen levels deep festooned with abstract base classes, factories, and dependency injection. In one sense you get a really tight abstraction. In another sense, you have a big leak: you need to know its internals to get any real work done.
Another drawback to abstractions fall out of their strength. If you haven’t seen a particular abstraction before, you don’t know what it does and how it works. Contrary to popular hype, self-documenting names are not enough. If you are a Rails user, raise your hand if you can tell me what all of the various options for
has_many are and what they do. You have to learn each abstraction’s interface, just as you had to learn what a for loop does for you.The win (not having to know how it works) is also a loss (not knowing what it does).
An abstraction is an abstraction is an abstraction
I think most people agree that named subroutines (or functions, or procedures) are an excellent abstraction. First-class functions and anonymous functions seem to be an acquired taste (just one taste, and your programs will quickly acquire them). Objects—in the strong sense of polymorphic programs—are well-regarded abstractions.
Macros, DSLs, and other means of writing your own mini-language provoke the wildest claims of productivity and equally baseless fears of unreadable, fragile, “magic” code built out of gossamer dreams.
What these all have in common is that these functional abstractions live happily within the syntax provided by the host programming language. They abstract function without abstracting syntax. For the most part, non-syntactic abstraction is uncontroversial.
There seems to be debate over syntactic abstraction. Macros, DSLs, and other means of writing your own mini-language provoke the wildest claims of productivity and equally baseless fears of unreadable, fragile, “magic” code built out of gossamer dreams. The basic “problem” with syntactic abstractions like
has_many in Rails or let in Scheme is that syntactic abstractions force you to learn their interface.They are right in your face, especially if they are very brief. Consider:
BlogPost.find_or_create_by_name('From Abstraction to Zipf').comments << Comment.new('bleh!', 'anonymous')
Don’t bother searching for the
find_or_create_by_name method or the comments<< method in the code base.All the same, syntactic abstractions are just like functional abstractions. You get some wins, and you pay some costs in understanding and potential “leakiness.”
Zipf to the rescue
So should we zealously abstract everything we can? Or should we conservatively avoid “magic” like syntactic abstractions?
Every abstraction has a fixed learning cost. That cost is amortized over all of the instances we’ll encounter. So you need to learn how
has_many works just once, and then you benefit every time you read it or write it. This is why abstractions built into a programming language are big wins: you amortize their cost over every program written in the language. Isn’t that why Java and C# look so much like C++ which looks so much like C? They were offering abstractions that have been paid up for years.Zipf’s law tells us that each application only needs a very few new kinds of abstractions to get most of the benefits. There are only a few low-hanging fruits, but each is plump and juicy.
An abstraction built into a framework like
Rinda or MapReduce is amortized over fewer programs. A domain-specific abstraction for a single organization is amortized over a very few programs, and an abstraction built into one program is only amortized over instances in the one code base. Unsurprisingly, opportunities for abstraction follow the Zipf distribution.The Art of the Metaobject Protocol
is one of the most important books ever written on the subject of building abstractions with objects. If the idea that there is more than one way to structure objects and classes seems surprising, then learning about the Meta-Object protocol will teach you what your language has kept secret.Quite simply, it pays to aggressively abstract the few things that are encountered the most frequently. In a CRUD web application, schema relationships like
belongs_to are incredibly frequent. There’s a big win from creating a syntactic abstraction, even if the learning curve looks daunting to newcomers. Creating a domain-specific language for database schema changes is also a big win.Note that we aren’t saying that
has_one, belongs_to, and has_many appear more than 50% of the time. They may be quite infrequent. The point is that they are far more frequent than something else you could abstract, and the other thing will take just as much time to learn to read but will pay off far less often.But should you create a DSL for list comprehensions in your CRUD application or just use the language’s built-in collections? I would say, you would need an application that uses an awful lot of lists before a syntactic abstraction for lists is a win.
It might be, but the nice thing is, it probably won’t be close: Zipf’s law tells us that each application only needs a very few new kinds of abstractions to get most of the benefits. There are only a few low-hanging fruits, but each is plump and juicy.
…Omega
I think it is a win to use aggressive abstraction techniques like metaprogramming, but only if you restrain yourself to abstracting the very few things that appear most frequently in your code base. The things that are used less frequently should be abstracted using less aggressive techniques.
The resulting program may not be magically 50% shorter than an unabstracted program, because the “long tail” of idioms and patterns are simply not worth abstracting away even though we have the tools for doing so.
You can probably tell whether a program has the proper level of abstraction just by checking its distribution.
If you find a big abstraction framework for one thing while frequently used idioms are expressed using patterns instead of abstractions, you are probably looking at an improperly abstracted program. You have to wade through verbiage to read everything, and the one time you don't need to abstract the code away, you have to chase definitions through indirection.
And in a well-written program, I would expect that the things that occur most frequently are expressed at the highest and most powerful levels of abstraction, while things that happen infrequently are expressed in a more direct and explicit way. Such a program would be easy to read throughout.
- Why Abstract?
is a delightful and wonderfully brief book that explains the appeal of abstract art in a simple and direct way. It’s one of the treasures on my bookshelf and I urge you to find a copy through a used book seller.
- Suprised? There is no footnote two. But if there was, it would be to mention that Paul Graham’s incredible book On LISP: Advanced Techniques for Common LISP
is freely available online. This is a must read for anyone interested in composing syntactic abstractions in any language.
Tuesday, April 10, 2007
Off topic: "Fanboy" considered tired
I really said all this before, but it seems that the world does not hang on my every utterance for guidance in their affairs.
So I’ll say it again: Calling someone a “fanboy” weakens your argument, not strengthens it. It makes your argument look like it emerged straight from an AOL chat room.
Compare:
And:
Does the second one really make its author seem hip and cool and smart at the expense of those hapless Apple fanboys? I didn’t think so either.
Look, if not wanting to be mistaken for an immature kid isn’t enough reason to avoid this word, I have a much better reason.
In any conflict, there is a strategic advantage for one side or the other to increase volatility. If you have a lead and a small advantage in games, you want to settle things down and let statistics do their thing. In match-play backgammon, for example, when you have match equity on your side you want to be very conservative with the cube.
You want to reduce volatility when you have an advantage and increase volatility when you’re behind.
Inflammatory labels are a way of increasing volatility, of shaking things up. And the same rule applies: if you’re in the right, if your arguments are cogent, you want to keep things rational and logical.
But if you’re weak, if your ideas are not sound, the only way to win is to turn a discussion into a brawl, and hope you catch a break.
I trust that your ideas are sound. So don’t fall into the trap of increasing volatility.
p.s. And if someone else hangs that label on you? Take satisfaction in the fact that they just admitted that their ideas are too weak to stand alone.
So I’ll say it again: Calling someone a “fanboy” weakens your argument, not strengthens it. It makes your argument look like it emerged straight from an AOL chat room.
Compare:
Surprisingly, more than half of the labels on the iTunes Music Store are either exclusive or with at most one other store.
And:
It may surprise Apple fanboys, but more than half of the labels on the iTunes Music Store are either exclusive or with at most one other store.
Does the second one really make its author seem hip and cool and smart at the expense of those hapless Apple fanboys? I didn’t think so either.
Look, if not wanting to be mistaken for an immature kid isn’t enough reason to avoid this word, I have a much better reason.
In any conflict, there is a strategic advantage for one side or the other to increase volatility. If you have a lead and a small advantage in games, you want to settle things down and let statistics do their thing. In match-play backgammon, for example, when you have match equity on your side you want to be very conservative with the cube.
You want to reduce volatility when you have an advantage and increase volatility when you’re behind.
Inflammatory labels are a way of increasing volatility, of shaking things up. And the same rule applies: if you’re in the right, if your arguments are cogent, you want to keep things rational and logical.
But if you’re weak, if your ideas are not sound, the only way to win is to turn a discussion into a brawl, and hope you catch a break.
I trust that your ideas are sound. So don’t fall into the trap of increasing volatility.
p.s. And if someone else hangs that label on you? Take satisfaction in the fact that they just admitted that their ideas are too weak to stand alone.
Monday, April 09, 2007
Quote. Unquote.
Ok, take a deep breath. Forget about whether you find these statements arrogant or elitist. Forget about whether you think they are true or not today. Forget about whether they were once true (I know that on Saturday, November 9th, 2002, they were absolutely true).
The question I ask myself, and that I think you might want to try asking yourself, is this:
Am I developing the ideas, technologies, and products today that the rest of the world will be using in ten years?
If not, what’s stopping me?
p.s. Don’t miss the comments!
p.p.s. And of course, this is not an orginal thought on my part.
I admit I live in a bubble. The thing is, my bubble is the one where they develop the technologies that you’ll be using in your bubble in ten years.
Basically, I hang around with people who are good programmers. I realize this is not a random cross section of computer users. But it is a disproportionately important subset, because what they use, other people will be using later. These were the people who were using microcomputers in 1980; now everyone is; the people who were using email in 1988; now everyone is; the people who were using the Web in 1995; now everyone is; etc etc.
—Two of user paulgraham’s comments on reddit.com
Ok, take a deep breath. Forget about whether you find these statements arrogant or elitist. Forget about whether you think they are true or not today. Forget about whether they were once true (I know that on Saturday, November 9th, 2002, they were absolutely true).
The question I ask myself, and that I think you might want to try asking yourself, is this:
Am I developing the ideas, technologies, and products today that the rest of the world will be using in ten years?
If not, what’s stopping me?
p.s. Don’t miss the comments!
p.p.s. And of course, this is not an orginal thought on my part.
Labels: passion
Sunday, April 08, 2007
Reduce. Reuse. Recycle.
Don't forget, all of your passion for software is wasted if you don't eat a good lunch.
Saturday, April 07, 2007
I wanted to be on the side that was right, even if I didn’t win
This is where I am great. I am great at being very, very stubborn and ignoring all sorts of reasons why you should change your goal, reasons that many other people will be susceptible to. Many people want to be on the winning side. I didn’t give a damn about that. I wanted to be on the side that was right, and even if I didn’t win, at least I was going to give it a good try.
—RMS, as quoted in Be Realistic. Demand the Impossible
Labels: passion
A Venture Capitalist passes away peacefully, and...
After a long and profitable life, a venture capitalist passes away peacefully in his sleep. To his surprise, death is not the end and his spirit hovers like an invisible ghost as his family grieves. He is pleased to see so many friends and business partners from the industry attend his funeral, and the eulogies are touching.
“I have lived a worthy life,” he thinks, “but it’s time to let go. I am ready.” With that thought, he finds himself sinking deep into the earth, through rock and magma, until he reaches a series of caverns, lit by an eerie glow. He sinks through the first and second levels, then alights in the third.
The Reckoning
He is facing an ancient writing desk, ornately carved. Seated at the desk, and brandishing a feather quill, is a man who appears (from what he can see) to be in great shape. He could effortlessly paste a drive 500 yards straight down the fairway. His eyes are pure white, with neither irises nor pupils.
“I have been waiting for you,” the man says, kindly, “you have served me well and earned your reward.”
Well, the venture capitalist isn’t quite expecting this. Quite honestly, he always thought that there was no afterlife, and he isn’t quite sure if this is real, a nightmare, or a few neurones flickering as his brain chills, but if there is a kind of afterlife, it may as well be the one his parents lectured him about. Unfortunately, he seems to have wound up in the Bad Place, but he made his fortune in life by turning situations around, and he puts a brave face on it.
“Umm, sure, pleased to meet you at last.”
The white eyes half close, then turn down to a scroll on the desk marked with an ancient writing. The man purses his thin, obsidian lips and speaks.
“I accept your service. Proceed to Venture Capitalist Hell.”
Well, that’s the sentence, but devils do not materialize to flay his skin and the room is comfortably warm but not hot, so maybe things aren’t as bad as people say. Perhaps he can make a few discrete inquiries, maybe volunteer to help with deal flow, even talk someone else into exchanging places with him. One, two centuries at the most and he’ll be out of this place.
He hasn’t moved, and while the lips do not move, the voice speaks again.
“Through the archway, down the hall, door on the left.”
Our venture capitalist is about to ask, “what archway?” but he realizes that there is an archway in front of him and that there has always been an archway in front of him. It all feels very dream-like, especially as he seems to float down a passage that reminds him of his offices on Sand Hill Road. It’s a broad, opulent hallway with fashionable lighting decorated with “tombstones,” the Lucite trophies of successful business deals.
At the end of the hallway there is a massive picture window and a door on either side. Through the window he can see blue sky and clouds, and without looking directly he is suddenly certain that they are on the top floor of the tallest and most prestigious business tower in the biggest and most powerful business city on this or any world. He knows without question that people who have lived lesser lives enjoy their rewards beneath his feet, and this just and proper.
“This is more like it,” he thinks. Although he didn’t really believe in such things, if there’s a choice in the matter, it’s better to reign in Hell than to serve in Heaven. Maybe he could learn a few things. Going by the legends, his new boss is the undisputed champion of devious term sheets.
He alights again, and opening the door on the left, peeks in.
VC Hell
It is an enormous conference room, so enormous than there appear to be an infinite number of board meetings going on simultaneously. He listens in with a growing sense of dread. Every single deal is going bad.
In one meeting, VCs are looking at the trends and realizing that companies are—and this is pure sacrilege—starting up without raising money! In another, the founders are laughing and celebrating actual revenues: they don’t need to raise a second round, and what will it take to buy their VCs out?
In another meeting, government officials are doing unspeakable things to the tax code. Why, they are tying tax breaks to the creation of jobs. Those Mandarins are actually expecting companies to grow the economy instead of just being shells for buzzword-compliant press releases!
And—this is too much—one pair of founders are shuttering their unsuccessful ventures and putting their patents and code into the public domain instead of merging together, raising a diluting round, and spending the proceeds on public relations and an expensive VP of Sales.
It’s all unspeakably horrible and he knows with certainty that he really is in Hell.
He gulps and looks around. There is nobody in the hallway and nobody has noticed him. He shuts the door carefully. He needs to get out of there, and he can’t go back to the man at the desk. What about the other door?
He carefully opens the door on the right and peeks in. This is much better! It’s another enormous conference room, and there is another infinitude of board meetings. But these meetings are going the right way!
Behind the other door
In one meeting, founders are supplicating themselves in the hope of getting funded. And the VCs are responding appropriately: “How will you make money if Google, Yahoo!, and Microsoft merge and devote their 40,000 engineers and $100 billion in cash to putting you out of business? What will you do if the entire Internet goes down? How do you know that someone won’t get a patent on binary logic?” The hapless founders are actually crying. This is great.
In my twenty years of business experience, Growing a Business is absolutely the best book on founding and running a business organically that I have ever read. And I read a lot of books. “Growing a Business” is not about scoring business coups or raising money. It is not about sales tactics or innovation. It is about growing a business step by step, customer by customer. It is about expanding at a sane rate and getting rich the old-fashioned way: one satisfied customer at a time.
Growing a Business is a must-read for anyone who wants to build a business rather than “do a deal.”
Unbelievably, it gets better. Nearby, a VC is toying cruelly with a portfolio company, demanding that they partner with other companies in her portfolio and add expensive buzzword compliance to their offering, for no other reason than to legitimize her investment in companies producing those very same buzzwords. And the founders are nodding gratefully, as if it was in their best interests!
And another VC is complaining that although the company is hitting every engineering deadline, they don’t have enough metrics. He demands that they start shopping for some “grey hair” to supervise engineering. They need “adult supervision” in the form of an industry veteran with a long list of failed and bloated projects on their resumé to show them what they’re doing wrong and shake everything up before it’s too late and they ship a product.
Are the founders arguing? Noooo, they’re listening respectfully, and all the while the VC is charging them a management fee for the time he spends telling them what to do. This is just great, our VC thinks, how much better can it get?
In one corner the VCs are agreeing that a company needs “a professional profile.” They are stuffing the company with HR, PR, and Business Development, all front jobs for the VCs’ lovers and mistresses. Everyone knows that jobs without performance metrics or quotas exist so that companies will be forced to dilute themselves sooner, and the founders are just sitting there and taking it while their burn rate triples.
Our VC practically wets himself with glee. Just a few months before his demise he had spent nearly an hour convincing a company in his portfolio to hire a marketing firm that happened to be run by his personal trainer and full-release masseuse. Here in Hell VCs could do as they please!
Well, does he need to hear more? Does he need to see the comely “assistant investment bankers” hired to satisfy the VC’s every need in exchange for directing public offerings to the bank? Does he need to watch as the photographers take yet another “Man of the Year” cover photo? No, this is great. There must have been some mistake at the desk, this is the place for him.
He swings the door wide open and prepares for the adulation and welcome he deserves. He is ready for his just reward.
But as he does so, there is a clap of thunder and the hallway shakes. A booming voice rings out:
“You belong to Venture Capitalist Hell. Don’t go in there, that’s Sbhaqre Uryy!!”
“I have lived a worthy life,” he thinks, “but it’s time to let go. I am ready.” With that thought, he finds himself sinking deep into the earth, through rock and magma, until he reaches a series of caverns, lit by an eerie glow. He sinks through the first and second levels, then alights in the third.
The Reckoning
He is facing an ancient writing desk, ornately carved. Seated at the desk, and brandishing a feather quill, is a man who appears (from what he can see) to be in great shape. He could effortlessly paste a drive 500 yards straight down the fairway. His eyes are pure white, with neither irises nor pupils.
“I have been waiting for you,” the man says, kindly, “you have served me well and earned your reward.”
Well, the venture capitalist isn’t quite expecting this. Quite honestly, he always thought that there was no afterlife, and he isn’t quite sure if this is real, a nightmare, or a few neurones flickering as his brain chills, but if there is a kind of afterlife, it may as well be the one his parents lectured him about. Unfortunately, he seems to have wound up in the Bad Place, but he made his fortune in life by turning situations around, and he puts a brave face on it.
“Umm, sure, pleased to meet you at last.”
The white eyes half close, then turn down to a scroll on the desk marked with an ancient writing. The man purses his thin, obsidian lips and speaks.
“I accept your service. Proceed to Venture Capitalist Hell.”
Well, that’s the sentence, but devils do not materialize to flay his skin and the room is comfortably warm but not hot, so maybe things aren’t as bad as people say. Perhaps he can make a few discrete inquiries, maybe volunteer to help with deal flow, even talk someone else into exchanging places with him. One, two centuries at the most and he’ll be out of this place.
He hasn’t moved, and while the lips do not move, the voice speaks again.
“Through the archway, down the hall, door on the left.”
Our venture capitalist is about to ask, “what archway?” but he realizes that there is an archway in front of him and that there has always been an archway in front of him. It all feels very dream-like, especially as he seems to float down a passage that reminds him of his offices on Sand Hill Road. It’s a broad, opulent hallway with fashionable lighting decorated with “tombstones,” the Lucite trophies of successful business deals.
At the end of the hallway there is a massive picture window and a door on either side. Through the window he can see blue sky and clouds, and without looking directly he is suddenly certain that they are on the top floor of the tallest and most prestigious business tower in the biggest and most powerful business city on this or any world. He knows without question that people who have lived lesser lives enjoy their rewards beneath his feet, and this just and proper.
“This is more like it,” he thinks. Although he didn’t really believe in such things, if there’s a choice in the matter, it’s better to reign in Hell than to serve in Heaven. Maybe he could learn a few things. Going by the legends, his new boss is the undisputed champion of devious term sheets.
He alights again, and opening the door on the left, peeks in.
VC Hell
It is an enormous conference room, so enormous than there appear to be an infinite number of board meetings going on simultaneously. He listens in with a growing sense of dread. Every single deal is going bad.
In one meeting, VCs are looking at the trends and realizing that companies are—and this is pure sacrilege—starting up without raising money! In another, the founders are laughing and celebrating actual revenues: they don’t need to raise a second round, and what will it take to buy their VCs out?
In another meeting, government officials are doing unspeakable things to the tax code. Why, they are tying tax breaks to the creation of jobs. Those Mandarins are actually expecting companies to grow the economy instead of just being shells for buzzword-compliant press releases!
And—this is too much—one pair of founders are shuttering their unsuccessful ventures and putting their patents and code into the public domain instead of merging together, raising a diluting round, and spending the proceeds on public relations and an expensive VP of Sales.
It’s all unspeakably horrible and he knows with certainty that he really is in Hell.
He gulps and looks around. There is nobody in the hallway and nobody has noticed him. He shuts the door carefully. He needs to get out of there, and he can’t go back to the man at the desk. What about the other door?
He carefully opens the door on the right and peeks in. This is much better! It’s another enormous conference room, and there is another infinitude of board meetings. But these meetings are going the right way!
Behind the other door
In one meeting, founders are supplicating themselves in the hope of getting funded. And the VCs are responding appropriately: “How will you make money if Google, Yahoo!, and Microsoft merge and devote their 40,000 engineers and $100 billion in cash to putting you out of business? What will you do if the entire Internet goes down? How do you know that someone won’t get a patent on binary logic?” The hapless founders are actually crying. This is great.
In my twenty years of business experience, Growing a Business
is absolutely the best book on founding and running a business organically that I have ever read. And I read a lot of books. “Growing a Business” is not about scoring business coups or raising money. It is not about sales tactics or innovation. It is about growing a business step by step, customer by customer. It is about expanding at a sane rate and getting rich the old-fashioned way: one satisfied customer at a time.Growing a Business
is a must-read for anyone who wants to build a business rather than “do a deal.”And another VC is complaining that although the company is hitting every engineering deadline, they don’t have enough metrics. He demands that they start shopping for some “grey hair” to supervise engineering. They need “adult supervision” in the form of an industry veteran with a long list of failed and bloated projects on their resumé to show them what they’re doing wrong and shake everything up before it’s too late and they ship a product.
Are the founders arguing? Noooo, they’re listening respectfully, and all the while the VC is charging them a management fee for the time he spends telling them what to do. This is just great, our VC thinks, how much better can it get?
In one corner the VCs are agreeing that a company needs “a professional profile.” They are stuffing the company with HR, PR, and Business Development, all front jobs for the VCs’ lovers and mistresses. Everyone knows that jobs without performance metrics or quotas exist so that companies will be forced to dilute themselves sooner, and the founders are just sitting there and taking it while their burn rate triples.
Our VC practically wets himself with glee. Just a few months before his demise he had spent nearly an hour convincing a company in his portfolio to hire a marketing firm that happened to be run by his personal trainer and full-release masseuse. Here in Hell VCs could do as they please!
Well, does he need to hear more? Does he need to see the comely “assistant investment bankers” hired to satisfy the VC’s every need in exchange for directing public offerings to the bank? Does he need to watch as the photographers take yet another “Man of the Year” cover photo? No, this is great. There must have been some mistake at the desk, this is the place for him.
He swings the door wide open and prepares for the adulation and welcome he deserves. He is ready for his just reward.
But as he does so, there is a clap of thunder and the hallway shakes. A booming voice rings out:
“You belong to Venture Capitalist Hell. Don’t go in there, that’s Sbhaqre Uryy!!”
Wednesday, April 04, 2007
Don't have a COW, man? What Haskell teaches us about writing Enterprise-scale software
Berlin Brown asked:
Yes, I use what I read on programming.reddit.com in my day job. That’s one of the reasons I have this day job: it’s part of what I do to sift through all of the cool stuff and find the things that are practical today.
Since you mentioned Haskell:
Consider a multi-threaded application with shared memory, like a really big web server that has some big shared collection of things in memory. From time to time you add things to the big collection, from time to time you remove them.
Pessimism and coarse-grained locking
One way to arbitrate multiple threads is to have one copy of the collection with strict locking protocols that apply to its coarse-grained operations like
In a language like Java, you can
That sucks tbng qvpx, especially if you do lots of reading: why should thread
Read and write locks
The next improvement is to have two kinds of locks: read locks and write locks. Two or more threads can lock the collection for reading, but if any thread locks the collection for writing, all of the other threads have to wait until it is done.
This works for about 17 clock ticks, and then you fix the bug by adding a new rule: if a thread wants a write lock but one or more threads have read locks, it has to wait, but any other threads that want read locks can’t have them. Even though the only threads with locks have read locks, they still have to wait.
The thread waiting to write gets a kind of pending write lock that blocks all other threads from taking out new locks. And then you fix the next bug by saying that all threads waiting wait in a priority queue so that the read threads aren’t starved by write threads and the write threads aren’t starved by read threads.
Purely Functional Data Structures takes you step by step through the design and implementation of copy on write collections. These collections can be used in purely functional languages, but they are just as useful in multi-paradigm languages like Java, Ruby, or Python handling multiple threads and performance optimization. The author’s thesis is available on line for free.
You now have a system that is pretty fast a long as you don’t write things very often. For example, you could build a fairly nice cache using read-write locking provided it is tuned so that you get lots of hits and only rarely have to drop things from the cache or add things to the cache. But if you’re doing something like maintaining a big index in memory where you have to make lots of updates, the writes will slow everything down.
These kinds of locking protocols are called pessimistic protocols: you assume bad things will happen and prevent them from happening up front by blocking threads from executing until it is safe to proceed.
Multi-version concurrency control
Another way to arbitrate multiple threads is to make copies of the collection whenever you perform an update.2 You maintain multiple versions of the collection. When a thread needs the collection, it grabs the latest copy. When it wants to
This works really well in that threads that only want to read are never blocked. They always run at full speed, even if another thread is in the middle of an update. Hand-waving over how you figure out the whole “latest copy” thing, this scheme doesn’t work so well for threads that write.
The problem is one of serialization: this word means, if some set of operations takes place on the collection, the result must be the same as if the operations were conducted one at a time on the collection. There is no guarantee of the order of the operations, just that the result is the same as if they had been carried out in some order.
Let’s use an example. Say our collection is a Map. It starts empty:
Operation
As does operation
And operation
If we start with an empty hash and perform all three operations, the result should be
We can fix this problem in a couple of ways. One way is to keep the versions so that reading threads work at full speed, but use mutexes for write locks so that only one thread can write at a time. That’s simple, and if you can figure out a cheap way to make copies, works pretty well.
That’s your pessimistic protocol again (threads that write have to wait on other threads that write), but it’s a huge win for threads that read.
Making this work is tricky. Copying the entire thing is expensive, so you need to do clever tricks where you only copy the things that change and share the things that don’t change. And you can get a big, big win if you can avoid write conflicts by arbitrating conflict at a finer grain. For example, a
One of the best books ever written on the subject of implementing fault tolerant concurrency (either on a single system or a distributed network) is Concurrency Control and Recovery in Database Systems
.
Don’t be fooled by the word “database”—the techniques described are just as useful for implementing distributed algorithms like MapReduce, concurrent data structures like high-performance collections, or for building multi-threaded communication systems based on queues.
Like all classics, it’s also available online for free.
There is a lot of extra overhead for this if a thread wants to write while another thread is reading a version, so it is only a big win if writes are fairly rare. Remember, one of the big wins is that reads never wait on writes because they work with immutable versions of the collection.
Depending on how many threads you have, what kinds of operations are most likely, and other factors, this kind of system can be orders of magnitude faster than coarse-grained pessimistic locking.
Sometimes you want a slightly different protocol. The aforementioned is often called single write, many reads. It requires threads that plan on writing to know in advance they need to write. But for something like a cache, you don’t know you need to write until you miss the cache. And then it’s too late to get a write lock.
Optimism and many writes, many reads
The easiest way to avoid having to pre-declare whether a thread is a reader or a writer is by letting all of the threads do as they please. They all get the latest version and chug happily along.
When they are finished, if they never executed an
Now, if a thread has executed a write (an
For example, we can number our versions. Let’s say that
Next
This many reads, many writes strategy is called an optimistic protocol because you do work in the hope that nothing will cause you to throw it out and try again. It’s a big win if writes do happen at the same time, but they rarely conflict.
For example, if you have a good strategy for merging writes, this is huge.
So what?
Well, it would be great if you didn’t have to reinvent the wheel and have to work out all of the implications when you want to make a really fast shared collection in a multi-threaded environment. What you want is someone to share a wealth of experience about how to make really fast copies of things by only changing the little bits that you change instead of the whole thing, and so forth.
Where do you go for that kind of information? How about to people who spend all day thinking about collections that cannot change because their programming languages are purely functional?
Yes, what I’ve just described is exactly how languages like Haskell implement mutable collections like dictionaries and lists. In purely functional languages, collections never change. Adding something to a collection is really creating a new collection with an extra element. This is the exact same implementation that we need for building optimistically locked collections in a multi-threaded environment!
Haskell teaches us extremely useful techniques for writing Enterprise-scale software.
And more techniques: Hard-core concurrency considerations
I read programming.reddit religiously but I rarely see something that could be used in a non-startup environment. Am I wrong, or are you considering deploying a haskell enterprise web application? And if the stuff discussed isn’t relevant for the next 5 years (i.e. an erlang based webapp) will it ever be relevant?
Yes, I use what I read on programming.reddit.com in my day job. That’s one of the reasons I have this day job: it’s part of what I do to sift through all of the cool stuff and find the things that are practical today.
Since you mentioned Haskell:
Consider a multi-threaded application with shared memory, like a really big web server that has some big shared collection of things in memory. From time to time you add things to the big collection, from time to time you remove them.
Pessimism and coarse-grained locking
One way to arbitrate multiple threads is to have one copy of the collection with strict locking protocols that apply to its coarse-grained operations like
add, remove, and fetch.In a language like Java, you can
synchonize those methods and you’re done. You have just implemented mutex locking: only one thread can use the collection at a time. If one thread is fetching something from the collection, all other threads must wait, even if all they want to do is fetch things as well.That sucks tbng qvpx, especially if you do lots of reading: why should thread
546 have to wait to fetch something just because thread 532 is currently fetching something?1Read and write locks
The next improvement is to have two kinds of locks: read locks and write locks. Two or more threads can lock the collection for reading, but if any thread locks the collection for writing, all of the other threads have to wait until it is done.
This works for about 17 clock ticks, and then you fix the bug by adding a new rule: if a thread wants a write lock but one or more threads have read locks, it has to wait, but any other threads that want read locks can’t have them. Even though the only threads with locks have read locks, they still have to wait.
The thread waiting to write gets a kind of pending write lock that blocks all other threads from taking out new locks. And then you fix the next bug by saying that all threads waiting wait in a priority queue so that the read threads aren’t starved by write threads and the write threads aren’t starved by read threads.
Purely Functional Data Structures
takes you step by step through the design and implementation of copy on write collections. These collections can be used in purely functional languages, but they are just as useful in multi-paradigm languages like Java, Ruby, or Python handling multiple threads and performance optimization. The author’s thesis is available on line for free.These kinds of locking protocols are called pessimistic protocols: you assume bad things will happen and prevent them from happening up front by blocking threads from executing until it is safe to proceed.
Multi-version concurrency control
Another way to arbitrate multiple threads is to make copies of the collection whenever you perform an update.2 You maintain multiple versions of the collection. When a thread needs the collection, it grabs the latest copy. When it wants to
remove or add elements, it writes a new copy without disturbing an existing copy.This works really well in that threads that only want to read are never blocked. They always run at full speed, even if another thread is in the middle of an update. Hand-waving over how you figure out the whole “latest copy” thing, this scheme doesn’t work so well for threads that write.
The problem is one of serialization: this word means, if some set of operations takes place on the collection, the result must be the same as if the operations were conducted one at a time on the collection. There is no guarantee of the order of the operations, just that the result is the same as if they had been carried out in some order.
Let’s use an example. Say our collection is a Map. It starts empty:
{ }
Operation
A adds an element:{...a: "A"...}
As does operation
B:{...b: "B"...}
And operation
C:{...c: "C"...}
If we start with an empty hash and perform all three operations, the result should be
{ a: "A", b: "B", c: "C" }, exactly the same result as if each operation were performed serially, one after the other. But what happens if each operation is performed by a thread that grabs the initial copy, {} and writes its result back to the collection? Something called a race condition: the result will be { a: "A" }, { b: "B" }, or { c: "C" }, with the “winner” being the last one to write its result.We can fix this problem in a couple of ways. One way is to keep the versions so that reading threads work at full speed, but use mutexes for write locks so that only one thread can write at a time. That’s simple, and if you can figure out a cheap way to make copies, works pretty well.
That’s your pessimistic protocol again (threads that write have to wait on other threads that write), but it’s a huge win for threads that read.
Making this work is tricky. Copying the entire thing is expensive, so you need to do clever tricks where you only copy the things that change and share the things that don’t change. And you can get a big, big win if you can avoid write conflicts by arbitrating conflict at a finer grain. For example, a
HashMap uses a set of linked lists. If two different threads write to different “buckets,” you can merge their results rather than rolling one back and starting again.One of the best books ever written on the subject of implementing fault tolerant concurrency (either on a single system or a distributed network) is Concurrency Control and Recovery in Database Systems
.Don’t be fooled by the word “database”—the techniques described are just as useful for implementing distributed algorithms like MapReduce, concurrent data structures like high-performance collections, or for building multi-threaded communication systems based on queues.
Like all classics, it’s also available online for free.
Depending on how many threads you have, what kinds of operations are most likely, and other factors, this kind of system can be orders of magnitude faster than coarse-grained pessimistic locking.
Sometimes you want a slightly different protocol. The aforementioned is often called single write, many reads. It requires threads that plan on writing to know in advance they need to write. But for something like a cache, you don’t know you need to write until you miss the cache. And then it’s too late to get a write lock.
Optimism and many writes, many reads
The easiest way to avoid having to pre-declare whether a thread is a reader or a writer is by letting all of the threads do as they please. They all get the latest version and chug happily along.
When they are finished, if they never executed an
add or remove we let go of the copy of the collection and we’re done. If a thread wants to write, it makes a copy as above and writes to its copy. But it doesn’t have to grab a lock while it is writing, so writes don’t wait on other writes.Now, if a thread has executed a write (an
add or remove), when it is done we check the result to see if it violates serializability.For example, we can number our versions. Let’s say that
{} is version 0. The first thread to finish, let’s say it’s the thread performing operation B, creates its result: { b: "B" }. Now it checks the collection to see if anyone has updated it since B read the collection. The collection is still at version 0, so B can write its result. B writes { b: "B" } to the collection and calls it version 1.Next
A finishes and notices that the collection is at version 1. This is a problem, because A is working with an updated version 0, so it has to throw out its work, fetch version 1, and try again. This is exactly the same thing as using a source code control system like Subversion to resolve conflicts.This many reads, many writes strategy is called an optimistic protocol because you do work in the hope that nothing will cause you to throw it out and try again. It’s a big win if writes do happen at the same time, but they rarely conflict.
For example, if you have a good strategy for merging writes, this is huge.
So what?
Well, it would be great if you didn’t have to reinvent the wheel and have to work out all of the implications when you want to make a really fast shared collection in a multi-threaded environment. What you want is someone to share a wealth of experience about how to make really fast copies of things by only changing the little bits that you change instead of the whole thing, and so forth.
I like languages which say, “No, you don't want to write it the way you’re thinking. There’s a vastly better way to solve this whole class of problems.” Me: brain explodes
Where do you go for that kind of information? How about to people who spend all day thinking about collections that cannot change because their programming languages are purely functional?
Yes, what I’ve just described is exactly how languages like Haskell implement mutable collections like dictionaries and lists. In purely functional languages, collections never change. Adding something to a collection is really creating a new collection with an extra element. This is the exact same implementation that we need for building optimistically locked collections in a multi-threaded environment!
Haskell teaches us extremely useful techniques for writing Enterprise-scale software.
And more techniques: Hard-core concurrency considerations
- Now, you might be saying, “what a waste, this is like locking a table in a database when we should be locking rows.” But if you look at the database closely, it does lock the table when you perform certain actions like deleting a row. Or it does something more complicated, and now that you’ve read the entire post, you know what it really does.
- Making Copies on Writes is called copy on write semantics, or COW for short. Chew on that for a while.
Tuesday, April 03, 2007
We haven't heard it all before
I used to travel the commuter train in Ontario. They work on an honour system: if you don’t purchase and punch a ticket (or purchase a monthly pass), you get a $90 ticket if a transit police officer spot checks you.
One of these officers told me that he had a standing policy of overlooking anyone who told him a new story. But he really had “heard it all.”
When, I asked, was the last time he heard a new one? It seems a few months previously a woman had said—with a straight face—that she had just polished her nails and couldn’t get her ticket out of her purse to punch it.
He laughed and let her go, nobody had dared to say anything so narcissistic before.
Perhaps that is the new FizzBuzz rule: by all means let yourself go, but if we’ve seen substantially the same thing before… prepare for flames.
Solving FizzBuzz using compiler error messages
One of these officers told me that he had a standing policy of overlooking anyone who told him a new story. But he really had “heard it all.”
When, I asked, was the last time he heard a new one? It seems a few months previously a woman had said—with a straight face—that she had just polished her nails and couldn’t get her ticket out of her purse to punch it.
He laughed and let her go, nobody had dared to say anything so narcissistic before.
Perhaps that is the new FizzBuzz rule: by all means let yourself go, but if we’ve seen substantially the same thing before… prepare for flames.
Solving FizzBuzz using compiler error messages
Hypergame II
Reg! An occasional rant on etiquette is interesting, but I read your blog to reconnect with my love of software. Do you still love what you do, or have you turned into one of those incoherent rage artists that has nothing better to do than stir up wasp nests and trade flames on programming.reddit.com?
Err, thanks. I’ve been chewing Kibble for a few days, and I needed to get back to what I love.1 So here’s a meandering dump of something on my mind. There is no particular point to this post, it’s just a way I have of reminding myself how much fun being well enough to wonder “why?” really is.
My brother-in-law was in town this past weekend, and we enjoyed a Sunday afternoon game of Acquire
. Formal games are much on my mind lately, thanks to the last Amazon delivery dropping On Numbers and Games
on my doorstep.
Thinking about games reminded me William Zwicker’s Hypergame pseudo-paradox, and that made me wonder how to describe it using programs instead of games. I came up with the following:
“You have a computer. By which I mean any computer, real, imaginary, even an idealized Turing machine. It runs programs, obviously. Now programs on this computer are finite or infinite. By which I mean, a finite program always halts eventually, and an infinite program does not always halt eventually. Note that an infinite program might halt or it might not. perhaps it contains some randomization element. Perhaps it has different inputs that cause it to do different things.
“Now let’s posit the idea of an algorithm that can examine a program for this machine and determine whether it is finite or infinite. Note that this algorithm need not be a program that runs on the machine, we allow that it can live “outside” the machine.
“I ask you this question: the computer you are thinking of, can we write a bootstrap program (or “bootstrapper”) for this computer? In other words, can we write a program that loads and executes other programs? Or more generally, does this computer support self-reference in programs?
“Consider a general bootstrapper for the computer. Is it a finite program or an infinite program? Obviously, it is an infinite program, because it can load and execute any other program, and if it loads an infinite program, then its own execution will be infinite.
“But what if we write a restricted version of the bootstrapper: it will only load finite programs. Maybe we mark those programs with a special bit, maybe it just trusts us not to cheat and give it an infinite program.
Is the restricted bootstrapper a finite program?
“If it only loads finite programs, you would think it is finite. After all, it loads and executes a program that runs in finite time, so it must execute in finite time. But if that’s the case, why can’t the restricted boostrapper load itself? It loads and runs finite programs, and if it’s a finite program then it can load and execute itself!
“In that case, it isn’t a finite program. Whew! Wait a second, if it isn’t a finite program, then the pseudo-paradox disappears, and we’re back to the fact that it must run in finite time. So it is a finite program!”
Well, there are lots of ways to explain this, and they’re all interesting. You can posit that the halting problem is undecidable, as Alan Turing
did. If so, we have just proven it for an interesting case, where we allow the computation of whether a program halts outside of the computation space of our machine.
You can also note that the problem goes away if our computer is too simple to allow self-reference. That’s an important result in its own right.
You can wonder whether “finite” is one of those things that has at least three states: true, false, and “strange.” Does allowing “strange” as the result of your “finite test algorithm” remove the paradox?
Err, thanks. I’ve been chewing Kibble for a few days, and I needed to get back to what I love.1 So here’s a meandering dump of something on my mind. There is no particular point to this post, it’s just a way I have of reminding myself how much fun being well enough to wonder “why?” really is.
My brother-in-law was in town this past weekend, and we enjoyed a Sunday afternoon game of Acquire
. Formal games are much on my mind lately, thanks to the last Amazon delivery dropping On Numbers and Games on my doorstep.Thinking about games reminded me William Zwicker’s Hypergame pseudo-paradox, and that made me wonder how to describe it using programs instead of games. I came up with the following:
“You have a computer. By which I mean any computer, real, imaginary, even an idealized Turing machine. It runs programs, obviously. Now programs on this computer are finite or infinite. By which I mean, a finite program always halts eventually, and an infinite program does not always halt eventually. Note that an infinite program might halt or it might not. perhaps it contains some randomization element. Perhaps it has different inputs that cause it to do different things.
“Now let’s posit the idea of an algorithm that can examine a program for this machine and determine whether it is finite or infinite. Note that this algorithm need not be a program that runs on the machine, we allow that it can live “outside” the machine.
“I ask you this question: the computer you are thinking of, can we write a bootstrap program (or “bootstrapper”) for this computer? In other words, can we write a program that loads and executes other programs? Or more generally, does this computer support self-reference in programs?
“Consider a general bootstrapper for the computer. Is it a finite program or an infinite program? Obviously, it is an infinite program, because it can load and execute any other program, and if it loads an infinite program, then its own execution will be infinite.
“But what if we write a restricted version of the bootstrapper: it will only load finite programs. Maybe we mark those programs with a special bit, maybe it just trusts us not to cheat and give it an infinite program.
Is the restricted bootstrapper a finite program?
“If it only loads finite programs, you would think it is finite. After all, it loads and executes a program that runs in finite time, so it must execute in finite time. But if that’s the case, why can’t the restricted boostrapper load itself? It loads and runs finite programs, and if it’s a finite program then it can load and execute itself!
“In that case, it isn’t a finite program. Whew! Wait a second, if it isn’t a finite program, then the pseudo-paradox disappears, and we’re back to the fact that it must run in finite time. So it is a finite program!”
Well, there are lots of ways to explain this, and they’re all interesting. You can posit that the halting problem is undecidable, as Alan Turing
did. If so, we have just proven it for an interesting case, where we allow the computation of whether a program halts outside of the computation space of our machine.You can also note that the problem goes away if our computer is too simple to allow self-reference. That’s an important result in its own right.
You can wonder whether “finite” is one of those things that has at least three states: true, false, and “strange.” Does allowing “strange” as the result of your “finite test algorithm” remove the paradox?
- Speaking of which, Purely Functional Data Structures
Monday, April 02, 2007
Whither professionalism in our profession?
The title of this blog post on 37Signals is unprofessional. They are not alone: lots of CEOs curse, wear jeans, and commit other sacrileges against the code of conduct we call “professionalism.”
What happened?
First, there is nothing new about this. Do you consider The Beatles to be “old fashioned?” Did you know that at one time they were the drug using symbols of counter-culturalism?
Revolution in the Valley tells the incredible story of the creation of the Macintosh, from the perspectives of the people who were actually there. It’s packed with behind-the-scenes anecdotes and little-known secrets.
Much of the material is available on line for free. Speaking of counter-culturalism and revolutionaries, here is the story of the legendary Pirate Flag.
There is a certain appeal to being a symbol of upheaval. Every generation has had its rebels. In fact, a major component of fashion in clothes, music, and programming languages is the degree to which it irritates the “establishment.”
Why do you think there are so many people deriding the Ruby Community?1 They aren’t making this irritation up: part of the appeal of the Ruby on Rails ecosystem to certain people is that Matthew Huntbach doesn’t like it!
Feel free to say that Java doesn’t work this way. Like people discovering The Beatles late in life, you missed the nineties when Java was the agent of change and some C++ people were deriding it and its supporters as being unprofessional.
I’m not saying Ruby lacks objective value. In case you haven’t noticed, The Beatles made wonderful music that has passed the test of time. Even though some of their appeal was that parents hated their long hair. And 37Signals have something important to say. Even if they say it in an unprofessional way from time to time.
People being people, the long-term forecast is for sustained tension between conservatives who lament the erosion of professionalism and rebels who wear their unprofessionalism on their sleeve.
And the irony is, the unprofessionals of today will be the stodgy old codgers of tomorrow.
Just ask David Gilmour, CBE.
p.s. Sure, there’s an argument about professionalism somehow being correlated with competence. If you wish to make this argument, please be so kind as to provide some empirical evidence in support of your claim. For example, show that programmers wearing a suit to work outperform their colleagues who do not.
What happened?
First, there is nothing new about this. Do you consider The Beatles to be “old fashioned?” Did you know that at one time they were the drug using symbols of counter-culturalism?
Revolution in the Valley tells the incredible story of the creation of the Macintosh, from the perspectives of the people who were actually there. It’s packed with behind-the-scenes anecdotes and little-known secrets.
Much of the material is available on line for free. Speaking of counter-culturalism and revolutionaries, here is the story of the legendary Pirate Flag.
Why do you think there are so many people deriding the Ruby Community?1 They aren’t making this irritation up: part of the appeal of the Ruby on Rails ecosystem to certain people is that Matthew Huntbach doesn’t like it!
Feel free to say that Java doesn’t work this way. Like people discovering The Beatles late in life, you missed the nineties when Java was the agent of change and some C++ people were deriding it and its supporters as being unprofessional.
I’m not saying Ruby lacks objective value. In case you haven’t noticed, The Beatles made wonderful music that has passed the test of time. Even though some of their appeal was that parents hated their long hair. And 37Signals have something important to say. Even if they say it in an unprofessional way from time to time.
People being people, the long-term forecast is for sustained tension between conservatives who lament the erosion of professionalism and rebels who wear their unprofessionalism on their sleeve.
And the irony is, the unprofessionals of today will be the stodgy old codgers of tomorrow.
Just ask David Gilmour, CBE.
p.s. Sure, there’s an argument about professionalism somehow being correlated with competence. If you wish to make this argument, please be so kind as to provide some empirical evidence in support of your claim. For example, show that programmers wearing a suit to work outperform their colleagues who do not.
- I have no idea what the “Ruby Community” is. How do you define membership in this community? Matz is obviously in, but after that, who? Why the Lucky Stiff? DHH? Me? I don’t recall being asked to join.
Sunday, April 01, 2007
Effing A!
I think a lot of people get too serious in their lives and stop trying to do something cool. I mean come on, we’re taking man-made machines that traditionally speak ones and zeros, but we write code in a sexy language and some stuff happens.
THAT'S SO COOL!!
If that’s not your reaction, you shouldn’t be a programmer.
Either you decide to stay in the shallow end of the pool or you go out in the ocean... So many of our dreams at first seem impossible, then they seem improbable, and then when we summon the will, they soon become inevitable.
Christopher Reeve, 1952 – 2004
You think, “I could sit at a desk and poke at a computer all day.”
I forget there is a desk, what day it is,
or that my chair's been broken since I started here.
Always have a vision. Why spend your life making other people’s dreams?
Orson Welles 1915 – 1985
