hexencodings

Ripping and Burning DVDs with Mac OS X

2011-04-20T22:27:00.004-06:00

The simplest way I've found doesn't require installing any additional third-party software at all. Just use Disk Utility.

2010-10-31T14:18:00.009-06:00

A number of people told us how much they enjoyed the poems and songs at our wedding in October. We'd like to share them with you here, including the opening remarks by Whit and the amazing toast by Cheng-Hsi's father.

Whit's opening remarks.

Welcome friends and family to this glorious day here in Boulder, Colorado. We all want to acknowledge the parents of the bride, Sobee and James, and those of the groom, Bob and Ginny. And of course, this could not occur without the entire cast of family and friends.

This is a great day. Let the celebration begin.

The great German philosopher Goethe said “Love is an ideal thing, marriage is a real thing”. Today we gather here to witness the marriage vows of Nicholas Andrew Dronen and Cheng-Hsi Ho. This marriage, my friends, is the real thing. It is no accident.

A very smart individual, Dr. Albert Einstein, commented: “Graviation can not be held responsible for people falling in love”. This marriage is far more profound than the passive forces on this earth. Nick and Cheng-Hsi – their relationship – is far more stunning than chance.

Nick met Ms. Cheng-Hsi Ho relatively recently. They had a very comfortable friendship. One evening my wife Mary and I had a dinner with the now bride and groom. We were at our home, and could recognize something very special between these two. Nick, at that time, did not. Yes, he thought Cheng-Hsi was a great woman and a fine friend.

But give Nicholas credit. He dug deep (at times, over the years, we weren’t sure he would or could), and he recognized that Cheng-Hsi was a really special woman. Someone he could love, cherish, and most importantly, share his life with. This is Nick's part on this specialday. He recognized Cheng-Hsi Ho. He saw deeper than just the everyday activities, the meals they were sharing. If this would not have happened – recognition – we would not be gathered here today.

Cheng-Hsi as well had her part to play to bring us all together today. Recognition of Nick of course was essential to walk the path of marriage. But let’s look closely at Ms Cheng-Hsi Ho. Cheng means receiving something old and making it better. Hsi means happiness. I have studied Chinese philosphy and the traditional medicine of China for my entire adult life. However, I don’t have command of the language, so please, give me some leeway here in my interpretations. With Cheng, we are talking about a process of transformation ... of taking the routine daily activities of life, sometimes not all that glamorous, and making them into glorious events. Making better old routines, old patterns of behaviour.

Cheng-- receiving, transforming. Hsi-- Happiness. Who could ask for anything more?

And that is where we, the community of friends and family, come in. We have the job of recognizing the marriage of Nick Dronen and Cheng-Hsi Ho. It is our job, as their friends and family, to witness the commitments and the vows that we are about to hear. And we need to embrace them, in support of our dear friends. Because, God knows, there will be times they may forget how happy they are in this moment Let’s make sure we remind them, and reflect this back to them, to support them, to nourish their marriage.

Interestingly, Nicholas, from the Greek language, comes from two root words – Victory and People. We are the community – The People – and this sure feels like Victory to me.

May Nicholas and Cheng-Hsi succeed beyond our and their wildest dreams. The great Chinese philosopher, Lao Tze, says: “Nature does not hurry, yet everything is accomplished.” We have the entire Universe supporting us. There is nothing to worry about.

Friends, let us continue with the Celebration. I call forth my wife, Mary Saunders, to read several poems.

Poetry read by Mary Saunders.

I cursed the rain for
pounding upon my roof and driving
away sleep.

I cursed the wind
for ravaging my garden.

Then you entered; and I gave thanks
to the rain because you must put off
your wet dress; and I gave thanks to
the wind
that he came and blew out my lamp.

-- Chang Wu-Chien

O Marvel! a garden amidst the flames.
My heart has become capable of every form:
it is a pasture for gazelles and a convent for Christian monks,
and a temple for idols and the pilgrim's Ka’ba,
and the tables of the T
orah and the book of the Quran.
I follow the religion of Love: whatever way Love's camels take,
that is my religion and my faith.

-- Ibn Arabi

The TrueLove

There is a faith in loving fiercely
the one who is rightfully yours,
especially if you have
waited years and especially
if part of you never believed
you could deserve this
loved and beckoning hand
held out to you this way.

I am thinking of faith now
and the testament of loneliness
and what we feel we are
worthy of in this world.

Years ago in the Hebrides
I remember an old man
who walked every morning
on the grey stones
to the shore of baying seals,

who would press his hat
to his chest in the blustering
salt wind and say his prayer
to the turbulent Jesus
hidden in the water,

and I think of the story
of the storm and everyone
waking and seeing
the distant
yet familiar figure
far across the water
calling to them,

and how we are all
preparing for that
abrupt waking,
and that calling,
and that moment
we have to say yes,
except it will not come so grandly,
so Biblically,
but more subtly
and intimately in the face
of the one you know
you have to love,

so that when
we finally step out of the boat
toward them, we find
everything holds
us, and everything confirms
our courage, and if you wanted
to drown you could,
but you don’t

because finally
after all this struggle
and all these years, you don’t want to any more, you’ve
simply had enough
of drowning, and you want to live and you
want to love and you will
walk across any territory
and any darkness,
however fluid and however
dangerous, to take the
one hand you know
belongs in yours.

-- David Whyte

Poety read by Jeff Pontillo

You know, my Friends, how bravely in my House
For a new Marriage I did make Carouse;
Divorced old barren Reason from my Bed
And took the Daughter of the Vine to Spouse.

For "Is" and "Is-NOT" though with Rule and Line,
And "UP-AND-DOWN" by Logic I define,
Of all that one should care to fathom, I
Was never deep in anything but -- Wine.

-- Rubaiyat by Omar Khayyam

The song performed by Wendy Lewis (vocals, guitar), Kitty Jenson (vocals), and Ted Dronen (guitar) was "True Love Will Find You in The End," composed by the gifted songwriter Daniel Johnston:

True love will find you in the end
You'll find out just who was your friend
Don’t be sad, I know you will,
But don’t give up until
True love finds you in the end.

This is a promise with a catch
Only if you're looking will it find you
‘Cause true love is searching too
But how can it recognize you
Unless you step out into the light?
But don’t give up until
True love finds you in the end.

Here's a version performed by Beck (Amazon, Nick's web server). I encourage you to buy the MP3 from your favorite download site.

Finally, the magnificent toast by Cheng-Hsi's father, James Ho.

Ladies and gentlemen, I am Cheng-Hsi's father. Please look at me carefully. Today is a big day. It is also an historical moment. We are so glad to attend this wedding ceremony. Congratulations! Nick, you are so lucky to marry my daughter, Cheng-Hsi. She is very kind, diligent, and humble. Also she is as beautiful as an angel. You are now building a home, a sweet home, and a family. I love her so deep and so much. She is my heart. Please love one another ever and forever. Well, if i were President Obama, I would speak fluent English. If you do not understand what I say, please pretend to understand. Ginny! Bob! I really love my daughter. Please love her as your own. Nick! I trust you and believe you are a good husband. And certainly Cheng-Hsi is a good wife. I promise you, Nick! You have something to do, whatever that is, to contribute to your family, society, nation, and all mankind. That is my wish. God bless you! Thank you.

Who is Don Draper?

2010-08-01T17:12:00.005-06:00

Even Don Draper probably doesn't know who Don Draper is, but what we know is that he has two selves -- a private self and a public one, a past self and a present one, one that he is and one that he pretends to be -- and what's withheld and revealed about them constitute much of the show's appeal. You have to give Matthew Weiner credit for creating a great character. I suspect he put a lot of thought into Don, and I'm certain that Don's names -- Dick Whitman and Don Draper -- are deliberately crafted as hints to the answer to the question, who is Don Draper? Certainly, other characters have names that somehow give you a sense of who the character is in their particular world -- Peggy Olson and Pete Campbell come to mind -- but Don is a man with more names than one, and he's the simmering star of the show (except for Peggy, of course), so without further ado, I'll explain them.

Dick Whitman. First name first. This one needs no explanation, just the background, but I really have to wonder whether Don's philandering (or, this season, general man whorishness) is motivated by a desire to connect in some way to his late mother. Whitman. This one's hard to explain, but I've come to think of his advertising genius as a kind of American poetry, sort of like this guy's. It's almost messianic, like he sees his role as the caretaker of the American psyche. Take, for instance, the first line in this important moment between Don and Peggy last season:

Don Draper: No. Because there are people out there who buy things, people like you and me. And something happened. Something terrible. And the way that they saw themselves is gone. And nobody understands that. But you do. And that’s very valuable.

Peggy Olson: Is it?

Don: With you or without you I’m moving on. And I don’t know if I can do it alone. Will you help me?

Peggy: What if I say no? You’ll never speak to me again.

Don: No. I will spend the rest of my life trying to hire you.

And finally, Don Draper. This one's actually pretty easy. From Webster's Ninth New Collegiate Dictionary:

don vt 1: to put on (an article of wear) 2: to envelop oneself in :ASSUME

draper n, chiefly Brit: a dealer in cloth and sometimes also in clothing and dry goods

drapery n 2: a: a decorative piece of material usu. hung in loose folds and arranged in a graceful design b: hangings of heavy fabric used as a curtain

The idea being, of course, that Don Draper -- the cipher, as he's called in the fourth season's first episode -- is a facade.

The Wrongness, The Wrongness!

2010-06-17T19:10:00.004-06:00

This is so wrong. NCAR, the National Center for Atmospheric Research, in Boulder is opening a supercomputing facility in Wyoming. Their facility in Boulder isn't suited to house the massive clusters of computers needed to support the center's research, which includes the study of climate change. A mere 10% of the Wyoming facility's power will come from wind. The remaining 90%, presumably from coal. Armageddon reimagined: supercomputers dedicated to research on climate change consume more and more coal-generated electricity, which adds more carbon to the atmosphere, thus accelerating the warming of the planet, resulting in gobs more federal funding for the study of climate change, and more supercomputers, with the concomitant carbon -- an accelerating cycle of supercomputers, carbon, and rising temperatures.

These Made Me Ha-a-appy

2010-05-31T18:51:00.003-06:00

I'm putting together a list of flicks for a fellow cinephile. The criteria for the list are (1) it should be something I think he hasn't seen and (2) it should have been made in the last ten years. There will be exceptions to the second criterion. It was originally going to be all Asian films, too, but there are just too many good ones made everywhere. Ultimately, they're in the list because watching them was profoundly pleasurable.

You, the Living Sweden, 2007
Silent Light Mexico 2007
Memories of Murder Korea, 2003
Mother Korea, 2009
Yi Yi Taiwan, 2000
Goodbye Solo USA, 2008
Cache France, 2005
Syndromes and a Century Thailand, 2006
Beau Travail France, 1999
Zatoichi Japan, 2003
Let the Right One In Sweden, 2008
Private Fear in Public Places France, 2006
Waltz with Bashir Israel, 2008
Taste of Cherry Iran, 1997

Enjoy!

When 5% is too much

2010-05-30T09:13:00.000-06:00

It's just criminal that a single industry generates %5 of man-made carbon:

Cement manufacture contributes greenhouse gases both directly through the production of carbon dioxide when calcium carbonate is heated, producing lime and carbon dioxide, and also indirectly through the use of energy, particularly if the energy is sourced from fossil fuels. The cement industry produces about 5% of global man-made CO2 emissions, of which 50% is from the chemical process, and 40% from burning fuel. The amount of CO2 emitted by the cement industry is nearly 900 kg of CO2 for every 1000 kg of cement produced.

Why do News Corp editorials hate reality?

2010-05-29T07:35:00.002-06:00

In an interview in this week's edition of Barron's, Ray Dalio of Bridgewater Associates, a fund with institutional assets of $75 billion, explains in six simple sentences why inflation is not a problem right now. This is from the print edition; the interview is available online to subscribers.

Explain why the printing of money won't cause inflation.

The printing of money will offset the deflation that is coming from the weak demand for goods and services due to weak credit growth. For example, in March of 1933 the U.S. printed a whole lot of money, and that had the effect of converting deflation into modest inflation, but not a high rate of inflation.... My point is, in developed countries there is too much of most things at the moment, ad that's creating a deflationary environment. There is too much manufacturing capacity. There is too much labor. There is too much housing stock.

Six sentences, including actual facts, spoken by someone who is actually responsible for other people's money (and a lot of it). Compare this to last week's inflation hawk editorial by Barron's editor Tom Donlan, in which he seems to desire to make the opposite case -- an argument for contractionary policies -- but instead wanders off on an embarrassing digression about old bonds and barely manages to burp out some you'll-be-sorry warnings about inflation.

This is another case of a financial paper's journalism being sane and the editorial pages being completely unhinged from reality. Where else does this happen? Why, Wall Street Journal, which is owned by News Corp, which owns Fox News and, of course, Barron's.

2010-05-22T08:24:00.005-06:00

You would think that an editorial that's subtitled "If the Fed won't tighten up, we'll pay the price" would present a case for why the Fed should abandon the current policy of quantitative easing in favor of something more contractionary. That's what I expected when I turned to the last page of this week's print edition of Barron's, but that's not what found. Instead, Tom Donlan fills most of the page with a story about bonds issued three decades ago, the point of which appears to be that things don't always turn out as you expect. But saying, in short, "shit happens" isn't a compelling argument in favor of any particular policy, much less the one that the editorial piece ostensibly advocates. Does journalism get any lazier?

The article isn't completely free of argument. There is an inkling of one towards the end, where he writes "Wall Street doesn't have a money market; its interest rates reflect Fed policy, as do Main Street consumer prices." Now this isn't really an argument, but it's the closest Donlan gets to the kind of writing one expects in a piece advocating a Fed policy change. The dependent clause -- "as do Main Street consumer prices" -- is an assertion. And it's not false; Fed rates and the state of the economy as a whole are correlated. When the economy overheats, the Fed raises interest rates, and there's a recession of some magnitude. The Fed eventually responds by lowering rates, which lets economic growth resume. That's the standard picture.

From there, though, it just gets childish:

It's easy to imagine that inflation is irrelevant to a U.S. economy that's posting the lowest increases in consumer prices in 44 years. But "imagination is funny; it makes a cloudy day sunny," as Johnny Burke wrote for Frank Sinatra in 1940.

Sunny days of low inflation won't last.

And it would be easier for us to imagine that what he says actually matters if Donlan had bothered to make an argument. Low inflation won't last. So what? When inflation becomes palpable to Fed policy makers, they'll raise interest rates. But if there's no sign of inflation now, what reason is there for Fed policy to become contractionary now? Hello?

UPDATE: The New York Fed chairman disagrees with Donlan too.

2010-05-06T08:10:00.001-06:00

I saw Bong Joon-Ho's "Mother" last night at the Lyric Cinema Cafe in Fort Collins. The style, theme, and humor are similar to his "The Host" and "Memories of Murder".

They're all awesome. "Memories of Murder" should have been on at least one major critic's best-of-decade list, but perhaps it was elided because Bong plays with genre too much to be considered alongside the directors of consistently sublime movies like "Syndromes and a Century" or "Yi Yi". In any case, if you like yourself some Asian cinema, watch "The Host", "Memories of Murder", and "Mother" (in order of accessibility).

iPhone, Safari, and tel URI's

2010-05-01T09:57:00.003-06:00

I think it's very cool that tapping a tel URI in Safari on an iPhone allows you to actually call the number. (A "tel URI" is basically a phone number link, similar to an "http:" or" mailto:" link, except it starts with "tel:".) Because not all phone numbers start with "tel:" on the Web, Safari tries to detect them so you can just tap and call, but it needs to be improved. For example, document citations often contain text that Safari wrongly believes is a phone number, such as the text after the comma in this fragment of a review: "No. 4, 541-578 (2009)". My phone thinks this is the number (541) 578-2009.

Futher brokenness is evident when I tap and hold the link: a pop-up menu appears with the option to "Call 541-578 (2009" (with no parenthesis at the end).

Rewatching Mad Men (cont.)

2010-01-27T19:56:00.005-07:00

I believe this scene is key to understanding why Campbell shows up at Peggy's apartment that night. Here's the pattern. First, Draper thwarts Campbell's desire to engage in a sort of corporate-ladder-climbing intercourse. Clearly, given the way the scene is shot, and given the bile of Campbell's "f*ck you" at the end, sex is a weapon for Campbell. Later, when the other Sterling Cooper lads take him out for his stag party, Campbell brazenly puts the moves on one of the gals who joins the lads at the strip club. Here again he confuses force for flattery, and again he's rejected and humiliated, only this time in front of his peers.

Campbell mixes desire and power to the point that they're indistinguishable. Being humiliated by Draper in the afternoon, and in front of his peers at the strip club, forces his hand. He goes to Peggy's apartment not -- or not strictly -- because he wants some wanton nookie before he gets hitched, but to get something that Draper has (or so he thinks). Sleeping with Draper's secretary is Campbell's way of getting revenge. Again, sex to him is only a weapon. This is, in part, why Peggy's speech at the end of the second season -- the one that left me and probably you breathless -- is so powerful: what she tells Campbell shocks him; he's surprised; but it's not about the baby. It's about what she says and how she says it and the fact that she is a woman. And it's about Campbell's idea of who he is.

Shots from "Syndromes and a Century"

2010-01-17T19:39:00.005-07:00

I watched "Syndromes and a Century" again last night after seeing it about a year ago. Something about it is so fresh and vibrant, even after multiple viewings.

Here are two powerful shots -- the first is from the rural vignette, the second from the urban one -- posted just because I think they're beautiful.

2010-01-17T19:39:00.001-07:00

Readings on Analogy

2010-01-14T08:53:00.003-07:00

I'm thinking about analogy at work. Some

Rewatching Mad Men

2010-01-12T18:42:00.010-07:00

It may be cheap sport, playing spot the symbols of sex and power in an episode of "Mad Men," but rewatching the first episode, it's too obvious to pass up. It's about at the 24-minute mark, right after the distasterous meeting with Rachel Menken.

Campbell: I'm not going to pretend I don't want your job, but you were right, I'm not great with people, and you are, I mean, not counting that meeting we were just in, so I'm kinda counting on you to help me out.... There's plenty of room at the top.

Draper: Look, I'm sorry I was so hard on you before. It's just this damn tobacco thing.

Campbell: You'll think of something. [Emboldened.] A man like you I'd follow into combat blindfolded, and I wouldn't be the first. Am I right buddy? [Presents hand to shake.]

Draper: Let's take it a little slower, I don't want to wake up pregnant. [Walks away.]

Campbell: [Under his breath.] F*** you.

Sometimes a cigar is just a cigar and sometimes the outstretched hand of your weasel of an underling is just a phallic symbol appearing on your TV screen.

Oh, and would it be too much to note that the previous scene features Peggy Olsen being humiliated by the gynecologist when she goes to him to get oral contraceptives? I think not.

Independent Study Reading List, Spring 2010

2010-01-12T09:27:00.008-07:00

A Memory of Vic Chesnutt

2009-12-25T19:28:00.001-07:00

After I graduated from high school, I got on a bus and went to Athens for two weeks, and had the best possible experience an 18-year-old music junkie could have had at the time. It's unbelievable but true. I met Michael Stipe (how exactly is a story in itself) and ended up spending almost a half day with him. We hung out in the R.E.M. office in downtown Athens while listening to Pylon rehearse in the basement. We went to his house and had a drink. We went to a cafe and later, before he dropped me off at the city park where I was camping, a bar. The next morning I got kicked out of the park and ended up camping uninvited on the roof of the R.E.M. office. The woman who ran the fan club noticed me through a window sleeping in the sun. I woke up with a bag next to me; it had a tube of sunscreen and some fruit. Turns out her boyfriend, Armistead Wellford, was the bass player in Love Tractor. She arranged for me to stay in a big old house where a lot of the band members lived. All of that was more than I imagined would happen when I got on the Greyhound bus in Fargo, North Dakota.

But in retrospect the most significant thing I saw there was when Stipe and I were at the cafe. He introduced me to some people at a table -- two women who I don't remember, and a man in a wheelchair, Vic Chesnutt. A cassette player played recording of one of Vic's live performances. While we sat at the table and talked, Stipe told Chesnutt that he'd like to help him record a record. It was the summer of 1988. Two years later New West Records released Chesnutt's Little, which Stipe produced.

Wiki terminology, like wikipedia, not optimized for search.

2009-12-01T11:12:00.003-07:00

In MediaWiki terms, including a page in another page is called transclusion, an accurate word, but not one that automatically comes to mind. I searched for "macros" and "include" for a while and, after a few minutes, found a page that mentions transclusion.

Independent Study: Concolic testing for web applications

2009-11-29T09:00:00.006-07:00

Dynamic Test Input Generation for Web Applications, Wasserman, et al
Finding Bugs in Dynamic Web Applications, Artzi, et al

Dynamic Test Input Generation for Web Applications

Here the authors use the concolic testing method pioneered in the seminal paper on Directed Automated Randomized Testing (PDF) to generate tests automatically for web applications written in PHP.

Use a taint-based (clarify) PHP runtime environment as the test oracle (which determines whether a failure occurs). The purpose of automatically generating tests is to automatically identify bugs in the program and, narrowly, the type of bugs the authors are trying to identify are SQL injection vulnerabilities. To that end, they iteratively construct (what they call) an approximate backward slice of the PHP program by (loosely speaking):

identify statements where such vulnerabilities may cause undesired behavior (viz. database library calls where the injected SQL can ultimately do harm),
add the functions where such statements occur to a set of functions to be analyzed,
execute the program by loading it in a browser
resolve control dependencies by recording stack trace at the beginning
analyze data dependencies
repeating (with some variations) until all data dependencies are resolved

The purpose of the preceding steps is to exclude from the analysis aspects of the program that won't help identify SQL vulnerabilities in the code.

Section 3 of the paper discusses the authors' algorithm for generating constraints for PHP.

Section 4 evaluates the system. Constraint generation is accomplished by a plugin to phc, a PHP compiler front-end. The plugin "wraps each statement in a function call"; the function call logs a trace of the program's execution to a file. They deal with eval by passing the string to be eval-ed through the plugin, so each statement in the eval-ed string is wrapped in a function call which logs a trace to the same file. Constraints are resolved by reading and symbolically executing the trace file. The result is "a list of Boolean control expressions where each subexpression is annotated with a concrete value from the execution."

An interesting aspect of the authors' evaluation is the overhead of the tracing process. When they evaluated an entire PHP program, the trace file for loading a single web page was almost 3 GB and the page load timed out. So the iterative process of limiting the scope of their analysis mentioned above was necessary for obvious practical reasons.

Previous work on leveraging symbolic and runtime values for input test generation falls back on concrete values when the symbolic value being addressed lies outside the theory of the resolution algorithm’s decision procedure. Our constraint resolution algorithm generates constraints only based on one variable instance per value. Therefore it may underapproximate the symbolic values of variables when program predicates depend on multiple variables, and it may miss paths that other resolution algorithms would find. In principle our constraint resolution algorithm could be enhanced to include multivariate constraints in some cases, but we leave that to future work.

An object-oriented web test model for testing web applications, Kung, et al, may be interesting reading:

This paper describes an Object-Oriented test model that captures both structural and behavioral test artifacts of Web applications. The model represents the entities of Web applications as objects and describes their structures, relationships, and dynamic behaviors. Based on the test model, test methods are presented to derive test cases automatically for ensuring the structures and behaviors of Web applications

Finding Bugs in Dynamic Web Applications

The previous paper focused on web application security. This paper focuses on web application reliability. Where the previous paper's goal was to identify vulnerabilities to SQL-injection attacks, this paper's goal is to identify bugs that cause web applications to crash or generate invalid HTML. (Web application crashes that can be triggered by user input become denial-of-service attack vulnerabilities once they become known to bad actors.) Similarly, where the test oracle of the previous paper is a PHP runtime environment that supports checking strings for taintedness (failure being defined as the use of an untained string in an SQL statement), the test oracle of this paper is an HTML validator (failure being defined as the web application generating invalid HTML).

Testing whether a web application generates valid HTML is hard for dynamic web pages. Systems exist for validating dynamically-generated web pages, but the require the tester to create tests manually. Here the authors present a system, Apollo, for automatically generating tests for dynamic pages.

Something I don't understand. Here's a passage from the paper:

The HTML pages generated by a PHP applications may contain buttons that—when pressed by the user—result in the loading and execution of additional PHP source files. We simulate such user input by transforming the source code. Specifically, for each page h that contains N buttons, we add an additional input parameter p to the PHP program, whose values may range from 1 through N. Then, at the place where page p is generated, a switch statement is inserted that includes the appropriate PHP source file, depending on the value supplied for p. The steps of the user input simulator are fully mechanic, and the required modifications are minimal, but for the evaluation we performed the program transformation by hand (due to time constraints).

Normally, submit buttons result in an HTML form being POST'ed to the web application. From the context, it's not clear why the system wouldn't simply POST the form. An additional passage

The stand-alone component of the User Input Simulator performs a transformation of the program that models interactive user input by way of additional parameters.

Still a little confused. :-)

Ah, I get it:


  <?php echo "<h2>WebChess ".$Version." Login"</h2>;?>
  <form method="post" action="mainmenu.php">
      <p>
          Nick: <input name="txtNick" type="text" size="15"/><br/>
          Password: <input name="pwdPassword" type="password" size="15"/>
      </p>
      <p>
          <input name="login" value="login" type="submit"/>
          <input name="newAccount" value="New Account"
                type="button" onClick="window.open('newuser.php', '_self')"/>
      </p>
   </form>

Nothing else very interesting here. They evaluate their system, present the results, related work, etc.

Other reading:

Improving test case generation for web applications using automated interface discovery, Halfond, et al, focuses on JavaScript.

Notes for Information Retrieval Quiz #3

2009-11-26T07:18:00.013-07:00

Some things to review before the Information Retrieval quiz:

Lecture 18, Collaborative Filtering and Recommender Systems

Pearson correlation

Lecture 19, Information Extraction

Named entity recognition: find and classify (i.e. determine the category of) all the named entities in a text. Two approaches to named entity recognition:
Rule-based (regular expressions)

Lists of names
Patterns to match things that look like names
Patterns to match the environments that classes of names tend to occur in

ML-based

Get annotated training data
Extract features
Train systems to replicate the annotation

Relation analysis consists of two tasks:

determine if two entities are related
if they are, classify the relation

Features in relation analysis (for each of the above tasks) are:

Features of the named entities involved (their types [concatenation of the types, headwords of the entities)
Features derived from the words between and around the named entities (+- 1, 2, 3; bag of words between)
Features derived from the syntactic environment that governs the two entities (constituent path through the tree from one entity to the other; base syntactic chunk sequence from one to the other; dependency path)

Template filling

Rules and cascades of rules
Supervised ML as sequence labeling

One sequence classifier per slot
One big sequence classifier

Lecture 20, Sentiment Analysis

Classification in sentiment analysis

Coarse classification of sentiment

Document-level classification according to some simple (usually binary) scheme
- Political bias
- Likes/hates
Fine-grained classification of sentiment-bearing mentions in a text

Positive/negative classifichttp://www.blogger.com/post-edit.g?blogID=35269538&postID=7962329312778949245ations of opinions about entities mentioned in a text
Perhaps with intensity

Choosing a vocabulary

Essentially feature selection
Previous examples used all words
Can we do better by focusing on subset of words?
How to find words, phrases, patterns that express sentiment or polarity?
Adjectives

positive: honest important mature large patient
negative: harmful hypocritical inefficient insecure

Verbs

positive: praise, love
negative: blame, criticize

Nouns

positive: pleasure, enjoyment
negative: pain, criticism

Lecture 21, Sentiment Analysis (cont.)

Identifying polarity words

Assume that generating exhaustive lists of polarity words is too hard
Assume contexts are coherent with respect to polarity
Fair and legitimate, corrupt and brutal
But not: fair and brutal, corrupt and legitimate
Example:

Extract all adjectives with > 20 frequency from WSJ corpus
Label them for polarity
Extract all conjoined adjectives
A supervised learning algorithm builds a graph of adjectives linked by the same or different semantic orientation
A clustering algorithm partitions the adjectives into two subsets

Challenges

Mixed sentiment: The steering is accurate but feels somewhat anesthetized.
Sentiment inverters: ... never seen any RWD cars can handle well on snow even
just few inches.
Anaphora and meronymy:

It's a great car for just about anything. The mkVI is pretty
much a mkv but ironing out all the small problems.
Hey is the back seat comfortable? In my MkV it feels like
you're sitting on a vat of acid.

Independent Study: Concepts and Experiments in Computational Reflection

2009-11-22T08:49:00.010-07:00

(This is one of a series of posts about papers I'm reading for an independent study with Prof. Evan Chang at the University of Colorado, Boulder. The format is similar to that of a review of a paper submitted to a computer science conference. There are already-published papers, so I'll be writing with the benefit of hindsight, especially when the paper was published at least several years ago.) (I've written most of these posts in the form of a review of a conference paper, but I'm going to use a free-form style this time.)

Pattie Maes's wonderful paper on reflection is a perfect follow-on to my reading about traits. My motivation for reading the traits paper was that Perl's Moose (Perl 6, too!) has traits (it calls them roles). I've been using Moose at lot at work and I wanted to catch up with the research behind traits to prepare for a short talk I gave about it to my colleagues. After the talk, a colleague who was at Bell Labs in the 80's mentioned a paper about reflection by Pattie Maes at OOPSLA in '87 which led to the MetaObject Protocol in the Common Lisp Object System (CLOS), which in part inspired Moose, so Maes's paper closes the loop, ices the cake, etc.

Many programmers know of reflection from the java.lang.reflect package in the Java API. Suffice it to say for the moment that Maes' reflection is expansive and Java's reflection is by comparison quite limited. However, reflection in Java does serve as a good starting point for understanding Maes. What the Java API does provide is programmatic access to information about objects at runtime by exposing an interface to what Maes calls the "self-representation of the system ... which makes it possible for the system to answer questions about itself and support actions on itself." To wit, java.lang.reflect allows the Java programmer to find out which methods or constructors, etc., exist for a given object, and to invoke them.

However, Maes goes a step further (or, more appropriately, Java didn't go as far as Maes imagined, for better or worse) by asserting that "a computational system can actually bring modifications to itself by virtue of its own computation." The modifications Maes envisions are pervasive. In her experimental object-oriented language, 3-KRS, reflection on an object occurs by way of a meta-object associated with the object. (The motivation for performing reflection on an object through a separate entity, its meta-object, may not have been obvious before Maes' paper, but in retrospect it's a clear case of separation of concerns.) Since everything is an object in a pure object-oriented language, meta-objects are everywhere:

[T]he self-representation of an object-oriented system is uniform. Every entity in a 3-KRS system is an object: instances, classes, slots, methods, meta-objects, messages, etc. Consequently every aspect of a 3-KRS system can be reflected upon. All these objects have meta-objects which represent the self-representation corresponding to that object.

For the uninitiated (including me), a slot is, loosely, an instance variable. And I suspect that the difference between a method and message is that a method defines a method (pardon the circularity) and a message "calls" a method. (The notion of a message likely goes back to Smalltalk.)

Further, meta-objects are manipulable at runtime, so — to borrow an example from Maes — a language that supports reflection in all its glory allows the programmer to modify meta-objects to provide support for multiple inheritance. Intuitively, a complete reflective system is an API for the semantics of a programming language. (See also: "A metaobject protocol (MOP) is an interpreter of the semantics of a program that is open and extensible.")

Two aspects of Maes's reflection which are not true for popular statically-typed languages, then, are:

meta-objects are pervasive
meta-objects are mutable

Obviously for, say, Java or C#, this is true by design. Enterprises of all kinds are often hard-pressed to find programmers who can understand the source code of their larger applications. Some managers are left in the lurch when a key employee departs. Self-modifying code, one might say, is job security. So clarity, explicitness, consistency, readability — these language properties are desirable for production software. A complete reflective system violates them. The flip side of this is expressiveness. Domain-specific languages (DSLs) come to mind. Being able to define little languages to solve a particular problem, and to compose larger applications from modules written in little languages, is an attractive idea. I'd like to say more about DSLs and how they relate to reflective systems, but I don't know much more than that they've been seeping into programming culture for quite some time.

Incidentally, Aspect-Oriented Programming (AOP) exists to address the fact that cross-cutting concerns — any application requirements that cause code to be scattered throughout a code base (e.g. logging, security) — violate modularity. However, it also bridges the gap between the limited form of reflection that exists in Java and some of the more interesting uses of reflection Maes mentions — such as being able to trace the execution of a program (with e.g. print statements) without modifying the program itself. This is no coincidence. Gregor Kiczales, the author of a book about the MetaObject Protocol, which was inspired by Maes' paper, is a coauthor of the earliest paper on AOP. In a sense, implementations of AOP attempt to augment a language with a meta-object protocol without changing the language itself.

A Little History of Electronic SEC Filings

2009-11-12T08:21:00.002-07:00

In 1986, the Securities and Exchange Commission started to accept SEC filings — 10-K forms and the like — electronically. Between '86 and '92, only a handful of companies filed their 10-K electronically. The companies?

1986
Medical Monitors, Inc.

1987
Medical Monitors, Inc.

1988
Medical Monitors, Inc.
Fast Eddie Racing Stables, Inc.

1989
Medical Monitors, Inc.
Fast Eddie Racing Stables, Inc,.
Jilco Industries, Inc.
Whitney American Corp.
Filmagic Entertainment Corp.
First Boston Mortgage Sec. Corp. Con Mor Pas Thr Cer CR 1989-2
First Boston Mortgage Sec. Corp. Con Mor Pas Thr Cer CR 1989-3
First Boston Mortgage Sec. Corp. Con Mor Pas Thr Cer CR 1989-5

1990
Medical Monitors, Inc.
Fast Eddie Racing Stables, Inc,.
Jilco Industries, Inc.
Filmagic Entertainment Corp.
Xanthic Enterprises, Inc.
First Boston Mortgage Sec. Corp. Con Mor Pas Thr Cer CR 1988-1
First Boston Mortgage Sec. Corp. Con Mor Pas Thr Cer CR 1988-2

1991
Medical Monitors, Inc.
Fast Eddie Racing Stables, Inc,.
Jilco Industries, Inc.
Filmagic Entertainment Corp.
Xanthic Enterprises, Inc.
Admiral Financial Corp.
Quad Metals Corp.
First Boston Mortgage Sec. Corp. Con Mor Pas Thr Cer CR 1988-4

1992
Medical Monitors, Inc.
Fast Eddie Racing Stables, Inc,.
Jilco Industries, Inc.
Filmagic Entertainment Corp.
Xanthic Enterprises, Inc.
Admiral Financial Corp.
Quad Metals Corp.
American Housing Partners
First Boston Mortgage Sec. Corp. Con Mor Pas Thr Cer CR 1992-3

While I get the obvious kick out of Fast Eddie Racing Stables, Inc. — that it's publicly traded and was an early-comer to electronic SEC filing — my hunch is that these early companies are there not necessarily because of who runs them (although it's certainly possible that Medical Monitors, Inc. has a techno-saavy CEO) but more likely because 86-92 was a period of controlled introduction. In the following years, the number of electronically-filed 10-Ks were:

Year # of filings
1993 1305
1994 1249
1995 3460
1996 6482

I suspect that the SEC opened the flood gates only partially in 93-94, a bit more in 95, and completely in 96. On the other hand, this was the era during which the Internet was really taking off, so it's hard to distinguish between what the SEC mandated and what it allowed.

If you're wondering what those First Boston Mortgage things are, they're probably asset-backed securities, which are by far the largest class of securities regulated by the SEC. Commercial state banks are up there, too. But it's interesting that the largest group of securities aren't even operating companies — they're just a publicly-traded piece of paper that represents a share of ownership in some asset.

Modeling the World Wide Web

2009-11-08T18:40:00.007-07:00

Just so I don't forget, some papers by Filippo Menczer, who appears to be doing work related to an idea I've been mulling over for a while.

Informally, consider the World Wide Web as a graph with web pages as nodes and hyperlinks as edges, label each node with some value derived from the contents of the web page (e.g. the length of the page, the set of terms in the page, or the term vector for the page), then define the value of an edge as the difference between the nodes it connects. This basically yields a geometric representation of the web graph by mapping it into some metric space. (If the idea is still fuzzy, imagine a hyperlink as a function from the document that contains it to the document to which it points.)

Now that I've found some already-published work on this model, I'll have to spend next semester learning what people have already done so I can do something new.

Independent Study: Traits: Composable Units of Behaviour

2009-11-06T19:54:00.015-07:00

If you start with the reasonable assumption that code reuse improves programmer productivity, an important question is how to increase code reuse. Historically, inheritance — both single and multiple — has been a mechanism for code reuse, in as much as it has allowed classes to be composed at least in part from other classes. Mixins solve some of the problems of single and multiple inheritance, but they don't work well when a class uses two or more mixins containing identically-named methods. Traits solve the same problems as mixins, but don't suffer from their limitations.

What is the strength of this paper (1-3 sentences):

Traits solve the problems of previous attempts to facilitate code reuse. Further, they suggest a style of designing software — as collections of traits (which ideally define only a single method) instead of collections of classes — that may be useful in its own right.

What is the weakness of this paper (1-3 sentences):

None noted.

Evaluation:

Wonderful!

Novelty:

The authors note that traits are inspired by mixins, and in one (arguably incorrect) sense, traits are merely an incremental improvement on mixins; however, the deficiencies the authors identify in mixins are real (and especially important for large, complex applications) and require solving, so the fact that traits aren't light years ahead of mixins is irrelevant, as the improvements traits provide are necessary.

Convincing:

Yes. The refactoring example helps the authors make a stong case for traits.

Worth solving:

See my response about novelty above.

Confidence:

I'm confident in the material in this paper.

Detailed comments:

The notion that code reuse improves programmer productivity is non-controversial. A library of well-tested and widely-used classes in a language's ecosystem provides not only implementations of common functionality (thereby relieving programmers of having to implement and test that functionality themselves) but also (because classes and methods are named) a common language for communication among programmers — both of which reduce "friction" during software development.

A problem for API designers is that code reuse in most common object-oriented languages is done at the level of the class definition — a client class T of the some API class U reuses U either by extending U or by otherwise referring to U (e.g. statically, as the type of a local variable, as the type of a member variable). This can lead to an undesirable decoupling of generic functionality, making it hard for programmers to discover reusable code. For example, in Java, to sort an object of the type of a class which implements java.util.List, one needs to know to use the sort method of the Collections class. Acquiring this knowledge isn't necessarily onerous for a programmer, but it likely leads novice programmers to implement their own sorting methods. A language with mixins or traits does not have this problem. In such a language, a class C that can be sorted uses the mixin or trait that provides a generic sorting routine (as long as C provides whatever methods the mixin or trait requires [e.g. something akin to the compareTo of Java's Comparable]), and discovering that C can be sorted is a matter of invoking an IDE's method autocomplete feature or, absent IDE support, a cursory examination of the definition of C. This is similar to the problem of jungloid navigation, where a programmer knows what kind of object she wants, but doesn't know how to get it, except in this case a programmer knows what she wants to do with an object (i.e. sort a list), but doesn't know how to do it (i.e. call Collections.sort).

A little history on multiple inheritance, interfaces, and mixins. So far as I've been able to find, interfaces first appeared in Modula-2 (1978), where they're called definition modules. From the Modula-3 report (I wasn't able to find one for Modula-2): "An interface is a group of declarations. Declarations in interfaces are the same as in blocks, except that any variable initializations must be constant and procedure declarations must specify only the signature, not the body." Modula-3 (1980s) also had multiple inheritance. Mixins first appeared in an OO extension to LISP (called Flavors [circa 1980]). Flavors fed into the Common Lisp Object System, where the concept of a Meta-Object Protocol was first implemented. Perl's Moose is built atop Class::MOP, which was inspired by the CLOS MOP.

It's Expensive Being Rich

2009-11-01T10:58:00.002-07:00

When you open a web page in a browser, the browser loads the page and all other resources to which the page refers. Some of those resources are files containing JavaScript code, and those files keep getting larger. Some of them can be large enough to noticeably delay the complete loading of the web page, which is a real problem for web site operators. Their dilemma is that users demand features, and JavaScript is a way to provide lots of features, but users also demand that pages load quickly, and adding more and more JavaScript increases the time it takes a page to load. Without changing the underlying technology, it's akin to a zero-sum game, or a game of Whack-a-Mole, or whatever notion you prefer for identifying a situation like this. The two requirements — provide a rich end-user experience, provide it quickly — are to some degree at odds with one another.

Recently James Hamilton pointed out a cool research project which transformed JavaScript source files into a form that allows the source code to be loaded only when needed. Another approach to dealing with this problem — an approach that is complementary to the approach mentioned by Hamilton — is to modify the HTML script element to indicate whether the JavaScript source file needs to be loaded immediately or can be loaded "lazily." This approach exists in the script element section of the HTML 5 draft specification.

Meditations on Meat

2009-11-01T10:18:00.004-07:00

Exhibit #1: "My childhood was typical, summers in Rangoon, luge lessons. In the spring we'd make meat helmets."

Exhibit #2: Turducken

Exhibit #3: Report: Meat Now America's No. 2 Condiment

Discuss.

Avoid the Lippis Report

2009-11-01T09:08:00.011-07:00

My last job was in the telecommunications sector and I had an interest in keeping abreast of developments in the industry. At the time some people at work were subscribed to Nick Lippis's mailing list, so I subscribed too. Gotta know what's known by those in the know. Now I work in a different business, but I'm finding that the cost of unsubscribing from the list is torture (whether it's eternal torture, I don't know yet, as I've still not been able to unsubscribe).

First thing I tried was clicking the "unsubscribe" link at the bottom of his emails. All that did was load the URL http://lippisreport.com/wp-admin/profile.php#delete. Here's a screenshot:

The next logical thing to try was the instructions right above the unsubscribe link, which read:

Login to your Lippis account at http://lippisreport.com/wp-login.php with username "ndronen," or delete your account by clicking the link below.

Since it's been quite a while since I subscribed, I didn't remember my password, so I opted to have the site change my password. A new password arrived shortly thereafter, but logging in with it yielded no joy. Another screenshot:

So I'm stuck — can't unsubscribe with the unsubscribe link, can't login and unsubscribe — so I can only resort to emailing the site directly. Thanks for wasting my time, Mr. Lippis.

Incidentally, the message "You do not have sufficient permissions to access this page" does not mean that I entered an invalid password. As you can see here, entering an invalid password causes an entirely different message.

Update (9:49 MST): It gets better. I sent email to the contact address listed in the "Lippis Report" email (info@lippis.com) and it bounced.

So now I'm sending email using the web form on the site.

Update (8:41 MST 11/02/2009): I've received a gracious email from Nick Lippis. They've removed me from the mailing list and are looking into the problem with the unsubscribe process.

Notes on Content Security Policy

2009-10-30T17:44:00.006-06:00

It seems I learn better when I write things down, so I'm taking notes as I read the spec for Content Security Policy.

It's opt-in on a per-site basis.
It is initially activated in the browser by the presence of an X-Content-Security-Policy header field in an HTTP response. The value of the header field must be either contain a policy specification or a policy-uri field which denotes the URI from which the browser should fetch the policy.
The header field must not be in the trailer headers (i.e. it must be at the top of the HTTP response). I surmise the purpose of this constraint is that existing browsers may evaluate inline JavaScript as they can, so if the X-Content-Security-Policy field is in the trailer, it's too late.
There are two URI types in CSP: policy-uri and report-uri. The former defines a URI from which a security policy must be fetched. The latter defines a URI to which violations of the policy should be reported (using e.g. an HTTP POST).
This is interesting. If there's more than one X-Content-Security-Policy in a response, the browser complies with the intersection of the policies.
If there's more than one report-uri, the browser reports violations to each unique URI — if there are duplicate URIs, the browser only sends one report to it.
A policy-uri or report-uri is only legal if it complies with the conventional same-origin policy — that is, if the URI refers to the same scheme/host/port as the page itself.
Inline JavaScript won't execute when CSP is enabled. The presence of inline JavaScript in a page for which CSP is in effect is a violation and causes a report to be sent to each report-uri.
Eval and any other mechanism for creating code from data (e.g. new Function("i'm evil code masquerading as data")) are not allowed to execute. They trigger a report to the report-uri, too.
CSP has options for stating different sources for different media types (e.g. img-src for images, media-src for audio/video, script-src for JavaScript, object-src for applets and the like, frame-src for frame and iframe elements, font-src for fonts, xhr-src for XMLHttpRequest, style-src for stylesheets)

The spec also contains examples of policy definitions.

Independent Study: Web Application Security

2009-10-16T17:14:00.010-06:00

To get a flavor of US-CERT data, here are 2009 current activity reports:
January
February
March
April
May
June
July
August
September
October

Feeds

Web Application Security Consortium feed
Security Focus feeds
Common Vulnerabilities and Exposures
SANS Internet Storm Center
SANS: @RISK: The Consensus Security Vulnerability Alert
US-CERT

File Under Very Useful

The Web Application Security Consortium has statistics (which appear to be actively maintained) on website vulnerabilities. The WASC describes the data as the result of "a collaborative industry wide effort to pool together sanitized website vulnerability data and to gain a better understanding about the web application vulnerability landscape."

For tracking web application (i.e. web app framework and web browser) security vulnerabilities, SANS's @RISK: The Consensus Security Vulnerability Alert seems to be quite useful. It compiles reports from a number of commercial security sources. Here's an example of the web application section of a recent report:

Web Application - Cross-Site Scripting
09.28.24 - Zoph Unspecified Cross-Site Scripting
09.28.25 - Microsoft Internet Explorer "javascript:" URI in "Refresh" Header Cross-Site Scripting
09.28.26 - Opera Web Browser "javascript:" URI in "Refresh" Header Cross-Site Scripting
09.28.27 - Google Chrome "javascript:" URI in "Refresh" Header Cross-Site Scripting
09.28.28 - Horde "Passwd" Module Cross-Site Scripting
09.28.29 - CMME "admin.php" Parameter Cross-Site Scripting
Web Application - SQL Injection
09.28.30 - Opial "admin/index.php" SQL Injection
09.28.31 - ConPresso CMS "detail.php" SQL Injection
09.28.32 - Opial "albumdetail.php" SQL Injection
09.28.33 - ClanSphere Multiple SQL Injection Vulnerabilities
09.28.34 - Siteframe "document.php" SQL Injection
Web Application
09.28.35 - Drupal Cross-Site Scripting, Code Injection and Information Disclosure Vulnerabilities
09.28.36 - phion airlock Remote Command Execution and Denial of Service
09.28.37 - art of defence hyperguard Remote Denial of Service
09.28.38 - Radware AppWall Source Code Information Disclosure
09.28.39 - ADbNewsSender "path_to_lang" Parameter Local File Include
09.28.40 - Siteframe "phpinfo.php" Information Disclosure

JavaScript

The advice everyone who knows anything gives to anyone who wants to be safer online is to use NoScript. I use it. You should too. But it's only for Firefox, not all the other browsers out there, and discretionary plugins only get adopted so far. That leaves a whole lot of browsers (many of which have unpatched vulnerabilities) running on the desktops and laptops of the world. Further, most Internet users aren't sophisticated enough to know when they need to enable JavaScript, and since there's not a WWW cop to enforce the unobtrusive use of JavaScript, it's just easier for people to allow JavaScript from every site on the web, which gets us back to square one.

A few weeks ago I reviewed a system for detecting and containing JavaScript worms which mentions the MySpace JavaScript worm. Here are some more recent incidents. The Reddit incident was only a few weeks ago.

2009
Somebody's made a javascript worm
source code for the reddit/firefox [sic] exploit

2008
JavaScript worm from late 2007 happily frolicking in 2008
JavaScript worm still spreading, infection origin unknown

2007
More on Orkut worm

2006
JavaScript worm targets Yahoo!

2005
I'm Popular
Technical explanation of the MySpace Worm

Buffer Overflows, Oh My!

Because they manage memory on behalf of the programmer, dynamic languages may be thought of being invulnerable to buffer overflow attacks. However, the runtimes of some dynamic languages are implemented in C, which is itself subject to buffer overflow attacks, so programs executing in such runtimes may themselves be vulnerable. This is illustrated by these Ruby, Perl, Python, and PHP vulnerabilities, all reported in 2008.

The same is true of JavaScript running in Firefox, Internet Explorer, and WebKit/Safari.

Indepent Study: Defending against Injection Attacks through Context-Sensitive String Evaluation

2009-10-09T17:10:00.013-06:00

Its strength is that the authors present a simple but general analysis of all kinds of injection attacks (e.g. SQL, shell, and others), and implement a system for preventing and detecting those attacks. Their system is completely automated, requiring the programmer to make no decisions (and hence make no mistakes), and its generality is extremely appealing.

What is the weakness of this paper (1-3 sentences):

The runtime overhead of CSSE is a bit steep.

Evaluation:

Excellent. This paper should be presented at POOPSLA '99!

Novelty:

All told, the approach the authors take to solving the problem of injection attacks is similar to Perl's taint mode, but the context-appropriate escaping mechanism is unique to CSSE.

Convincing:

I'm convinced.

Worth solving:

Definitely. And I love the way they've solved it. It's general and it requires no programmer input.

Confidence:

High.

Detailed comments:

One thing I should note about this paper is that it is beautifully written. Killer paragraph (but you have to ignore the superfluous comma after "prevention method"):

This paper introduces Context-Sensitive String Evaluation (CSSE), which is an intrusion detection and prevention method, for injection attacks. It offers several advantages over existing techniques: it requires no knowledge of the application or application source code modiﬁcations and can therefore also be used with legacy applications. It is highly effective against most types of injection attacks, not merely the most common ones. It does not rely on the application developer, which makes it less error-prone. Finally, it is not tied to any programming language and can be implemented on a variety of platforms.

Asking programmers to help validate the security of their application -- as in last week's paper's attempt to disambiguate the purpose of regular expressions by prompting the programmer for input -- is invariably bound to fail.

The authors analyze injection attacks in general, SQL and shell e.g., focusing on how these attacks exploit assumptions about the syntactic content of user input.

More great paragraphs:

A common property of injection vulnerabilities is the use of textual representations of output expressions constructed from user-provided input. Textual representations are representations in a human-readable text form. Output expressions are expressions that are handled by an external component (e.g., database server, shell interpreter).

User input is typically used in the data parts of output expressions, as opposed to developer-provided constants, which are also used in the control parts. Therefore, user input should not carry syntactic content. In the event of an injection attack, specially crafted user input inﬂuences the syntax, resulting in a change of the semantics of the output expression. We will refer to this process as mixing of control and data channels.

The authors define a framework for understanding the sundry injection attacks in more general terms, identifying sets of input and output vectors. For most web applications, there's only a single input vector, HTTP operations. The output vectors for SQL injection attacks are the execution of SQL statements against a database, and for command injection attacks, the output vector is a call to execute a command, such as with system() or exec().

They describe existing approaches to this problem as either safe ad-hoc serialization or serialization APIs. Safe ad-hoc serialization includes manual input validation (i.e. the programmer is solely responsible for validating the safeness of the input), automated input validation (e.g. MagicQuotes in PHP), and variable tainting (e.g. Perl's -T flag), and, lastly, the approach of SQLrand, which requires that all SQL commands executed by an application must be encoded as constants in the application. Serialization APIs include DOM APIs for XML and, for SQL, any API which requires prepared statements. Examples of the latter are Java's PreparedStatement and the prepare_statement method of Perl's DBI module.

The authors propose to assign metadata to all strings in a program in order to track its origin. Strings read from a TCP/IP socket are tagged as untrusted. Strings that are constants in the source code are tagged as trusted. Their system, Context Sensitive String Evaluation (CSSE), tracks the untrusted string fragments at runtime. When an untrusted fragment is included in an expression passed to a function which interacts with the external resources (e.g. mysql_query(), exec()), CSSE can escape the untrusted fragment in a context-appropriate way (e.g. escape SQL in the case of mysql_query() and escape shell in the case of exec()), block the request, or raise an alarm.

This feature can be implemented using Aspect-Oriented Programming (AOP), but the authors note that at the time of their writing the AOP library for PHP did not support the interception of string operations, which is necessary to implement CSSE.

Independent Study: Static detection of security vulnerabilities in scripting languages

2009-10-04T07:43:00.007-06:00

SQL injection and other string-based exploits to which web applications are vulnerable can be detected by performing static analysis on web applications written in dynamic languages. The static analysis is supplemented with information gleaned from the symbolic execution of the source code.

What is the strength of this paper (1-3 sentences):

Techniques for automatically detecting SQL injection attacks in web applications written in dynamic languages are sorely needed.

What is the weakness of this paper (1-3 sentences):

I am skeptical of the usefulness of the interactive mode of the checker -- which is triggered when regular expressions are used to validate unsafe data -- for the average PHP programmer. Also, while the authors refer to Perl's taint mode (man perlsec) as an alternative way of sanitizing data, it would be useful if they were to compare the effectiveness of their approach to Perl's built-in approach.

Evaluation

Excellent.

Novelty

Symbolic execution has been used before in the DART paper, but there the purpose was to determine what input values would cause a statically-typed program to take certain paths during automated testing; here the purpose is to determine whether any memory locations are untrusted.

Convincing

The authors describe a checker that is effective at detecting SQL injection vulnerabilities.

Worth Solving

This problem is worth solving. It is all too easy for programmers to fail to untaint input received from the user of a web application, so a reliable, automated way of detecting such exploits is necessary.

Confidence

Reasonably confident

Detailed Comments

Analysis starts with block-level symbolic execution, which generates a block summary. Intraprocedural analysis takes block summaries (a six-tuple, described below) as input and generates a four-tuple, which is consumed by the intraprocedural analysis phase.

The use of symbolic execution here reminds me of the DART paper. Here symbolic execution is used to understand the functioning of a program written in a dynamic language. In the DART paper, it was used to force a statically typed language to take different paths during automated testing.

Block Analysis

At the block level, the code is executed symbolically, and the resulting summary is used to perform analysis at intra- and interprocedural levels. Using a summary at the higher levels expedites the analysis.

The authors define a language to model what they believe is an appropriate subset of PHP for detecting SQL injection attacks with their simulator (i.e. the component of their checker which symbolically executes blocks of PHP code).

They devote particular attention to how they model strings, because strings are such essential types in dynamic languages: "Strings are typically constructed through concatenation. For example, user inputs (via HTTP get and post methods) are often concatenated with a pre-constructed skeleton to form an SQL query.... String values are represented as an unordered concatenation of string segments, which can be one of the following: a string constant, the initial value of a memory location on entry to the current block (l_0), or a string that contains initial values of zero or more elements from a set of memory locations (contains(sigma))." The latter part of the definition of strings in this model allows the cheker to track the flow of untainted data through a web application.

The motivation for and definition of untaint (as related to the definition of the Boolean type) in the modelling language is unclear to me.

The untainting of strings "occur[s] via function calls, casting to safe types (e.g. int, etc), regular expression matching (!), and other types."

The result of the block-level analysis is a six-tuple consisting of an error set ("the set of input variables that must be sanitized before entering the current block"), definitions ("the set of memory locations defined in the current block"), value flow ("the set of pairs of [memory] locations (l_1, l_2) where the string value of l_1 on entry becomes a substring of l_2 on exit"), termination predicate (whether the current block causes the program to exit), return value (undefined if and only if the termination predicate is true), and an untaint set (the set of [memory] locations that are sanitized by the current block, for each of the block's successors).

Intraprocedural Analysis

This phase of the analysis uses the six-tuple block summaries generated by the previous phase to generate a four-tuple consisting of an error set ("the set of memory locations ... whose value may flow into a database query, and therefore must be sanitized before invoking the current function"), return set ("the set of parameters or global values that may be a substring of the return value" of the function), sanitized values ("the set of parameters or global variables that are sanitized on function exit"), and program exit ("whether the current function terminates program execution on all paths").

Interprocedural Analysis

This phase involves using the previously-generated function-level tuple to substitute actual for formal parameters in the error set and marking memory locations as safe when they are unconditionally untainted. It also involves the use of the Boolean-related notion of untaint that I still don't understand.

In what order are functions analyzed? "Our algorithm analyzes the source codebase in topological order based on the static function call graph." Recursion doesn't compute fixed-point; the system inserts a no-op summary when it encounters recursion.

Since regular expressions are self-contained automata, little computational devices, I was surprised when the authors remarked that strings can be marked as untainted when they are checked by regular expressions. It sounded almost magical. It's not quite that. "Some regular expressions match well-formed input while others detect malformed input; assuming one way or the other results in either false positives or false negatives.... To make it easy for the user to specify the sanitization effects of regular expressions, the checker has an interactive mode where the user is prompted when the analysis encounters a previously unseen regular expression and the user's answers are recorded for future reference."

The authors mention the built-in Perl taint mode (man perlsec). This suggests that the proper way of implementing a checker like the one described here is to integrate it into the language runtime.

Independent Study: Ripley: Automatically Securing Web 2.0 Applications Through Replicated Execution

2009-09-27T09:17:00.010-06:00

AJAX or Web 2.0 applications provider richer end-user experience by moving computations to the browser, but the results of those computations are vulnerable to manipulation by known tools. Since client-side computations often cause server-side events, such as modifying or removing data in a database, it's important for the server to be able to validate the integrity of the client's computations. The authors present RIPLEY, a system for replaying client-side computations in the server to reestablish the lower bound on computational integrity that was lost by moving code to the client.

What is the strength of this paper (1-3 sentences):

The architecture of RIPLEY is sound for preventing the problem the authors identify, and the empirical results of deploying the system are sufficiently promising for internet application providers to consider investigating this approach to the problem.

What is the weakness of this paper (1-3 sentences):

The authors don't provide a compelling case that this problem needs to be solved. In their paper on Spectator, they refer to specific JavaScript worms that have caused damage to Web site operators. Here they don't refer to specific large-scale exploits that their approach solves. This makes the problem they're solving seem less pressing.

Evaluation

It's an interesting solution but the problem, while real, doesn't seem to have been exploited in any significant way. The fact that the server-side code can anticipate client actions, pre-compute their results, and send them to the client before the client takes the given action, thus increasing client-side responsiveness, is a lovely way to improve the user experience, one that should pique the interest of Web site operators making heavy use of client-side JavaScript.

Novelty

RIPLEY is novel. The authors note that an alternative approach (explored here and here) is to require the client to send to the server a computed proof of the correctness of its current state (e.g. the client could intermittently send a stack trace to the server). Unlike RIPLEY, these approaches only provide a degree of assurance, not a guarantee, of the correctness of the client-side computations.

Convincing

The architecture, implementation details, and runtime performance

Worth Solving

The problem is worth solving, but not as pressing as the problem of JavaScript worms that the authors solve in their work on Spectator.

Confidence

95% +- 2

Detailed Comments

See citations 27, 29 for vulnerabilities to code modification in browser.

See citation 20 for, more generally, AJAX vulnerabilities and exploits.

Volta, a distributing compiler -- in some respects similar to Google Web Toolkit, which generates JavaScript code from Java. The idea of GWT is to allow the user to write dynamically-typed code in a statically-typed language -- the GWT compiler can reason about the statically-typed code and emits code that's known to be safe. While Volta appears to be designed to work in a more general way than GWT -- generating code for multiple languages (more than just JavaScript) via the Microsoft Common Language Runtime intermediate representation, for example -- the basic idea is similar. One feature of Volta is that because it can reason about the statically-typed program, it can divide the computations in the statically-typed code to be divided between the server and client.

A developer who wishes to use RIPLEY applies class-level annotations to identify which code runs on the client, which on the server. The code is then converted to .NET bytecode, at which point Volta reads the bytecode (which contains the annotations), and generates the appropriate client- or server-side code, introducing RPCs between client and server when necessary. RIPLEY is implemented as a tweak to this phase of Volta's execution. The authors added a feature to Volta to generates additional server-side code for validating the client-side computations.

RIPLEY is intended to enforce the integrity of the original application in the face of the vulnerability of the client-side code. It accomplishes this by reproducing each client-side computation on the server; if the results of a client-side computation cannot be reproduced on the server, this is reason to believe that something faulty or malicious occurred in the client.

In the RIPLEY architecture, a browser emulator runs on the server, validating the client-side computations by replaying them. Since the browser emulator runs in a .NET virtual machine, which uses JIT, sometimes the server-side validations can anticipate client-side events, and the server can push pre-computed results to the client.

Independent Study: Spectator: Detection and Containment of JavaScript Worms

2009-09-20T09:40:00.012-06:00

Detecting JavaScript worms can be accomplished by adding a tag to content uploaded to a Web server, associating the tag with the IP address of the client that originated the upload, and using tags to identify propagation chains. A long chain of propagation is a signature of JavaScript worms, so identifying a long chain (where length is user-defined) should be sufficient for detecting JavaScript worms. One a worm has been identified, containment is a matter of disallowing further uploads along the chain of known-infected clients until an administrator tells the Spectator proxy that the chain is safe.

What is the strength of this paper (1-3 sentences):

The strength of this paper is that it proposes a solution which can be implemented simply as a proxy server in the domain of a Web site operator, and which doesn't require any modifications or plug-ins in the web browser. With a reasonable amount of time and capital, a large Web site operator can implement this solution today.

What is the weakness of this paper (1-3 sentences):

Not to be so generous, but I don't find any problems with it.

Evaluation

This is on the whole an excellent paper. I would like to see it in SIGFOO this year.

Novelty

I'm not sure how novel this is, as XSS attacks and JavaScript worms aren't my specialty, but naively, it seems novel. In the spirit of many useful papers in computer science, it combines a number of sound techniques to solve an important problem.

Convincing

I'm convinced not only that the detection and containment algorithms work correctly and efficiently, but also that the author of a JavaScript worm would have a hard time subverting the system. The authors' approach is essentially invisible to the browser, with the exception of some JavaScript injected by the Spectator proxy (Figure 5) (which appears to be designed so as to prevent subversion by malicious code).

While the empirical data in section 5.2 (Overhead and Scalability) is encouraging, a Web site operator would obviously want to subject any implementation of this system to rigorous testing before deploying it.

Worth Solving

Very much so!

Confidence

Medium.

Detailed Comments

I'm curious whether it's possible for each page downloaded from a site to contain JavaScript code to validate that only Web site operator-provided JavaScript is executing in that page. Something like an unmodifiable onload event handler similar to the unload event handler in Figure 5.

Some papers to follow up on:

S. Meschkat. JSON RPC: Cross site scripting and client side Web services. In 23rd Chaos Communication Congress, 12 2006.

T. Pietraszek and C. V. Berghe. Defending against injection attacks through context-sensitive string evaluation [PDF]. In Proceedings of the Recent Advances in Intrusion Detection, Sept. 2005.

Y. Xie and A. Aiken. Static detection of security vulnerabilities in scripting languages [PDF]. In Proceedings of the Usenix Security Symposium, pages 271–286, Aug. 2006.

Y.-W. Huang, F. Yu, C. Hang, C.-H. Tsai, D.-T. Lee, and S.-Y. Kuo. Securing Web application code by static analysis and runtime protection. In Proceedings of the Conference on World Wide Web, pages 40–52, May 2004.

Fibonacci Strings and Performance

2009-09-16T09:38:00.019-06:00

Fibonacci strings are related to Fibonacci numbers in that the length of the nth Fibonacci string is the nth Fibonacci number. Here's pseudocode for a function that generates them:


 fibstr: int -> string
   if n is 0
     return the empty string
   else if n is 1
     return the string "b"
   else if n is 2
     return the string "a"
   else
     return fibstr(n-1) concatenated with fibstr(n-2)

The strings generated by this function for n > 2 have the interesting property that if you delete the last two letters the resulting string is a palindrome. Anyway, for kicks I decided to use Fibonacci strings to test the string performance of popular programming languages. The test was simple: run fibstr(31) 31 times. I was lazy in writing the tests, but the results were consistent across many cups of Bhakti chai and many executions of the test yesterday morning , so as far as I'm concerned they're valid representations of the relative performance of the languages with respect to string concatenation and, to some extent, memory management.

Language	Real	User	System
C	0.809s	0.800s	0.000s
Java (StringBuilder w/JIT	2.807s	2.652s	0.084s
Java (String w/JIT)	2.819s	2.692s	0.076s
JavaScript (Rhino 1.6.r5-3	4.240s	4.100s	0.080s
Python (2.4.4)	4.708s	3.992s	0.012s
Perl (5.8.8)	7.528s	7.484s	0.008s
Java (StringBuilder w/o JIT)	8.171s	8.053s	0.040s
Java (String w/o JIT)	11.707s	11.553s	0.068s
Ruby (1.8.6)	21.348s	18.565s	2.488s

Off-the-cuff ... Ruby's performance speaks for itself. I expected Perl to do better, since it's been around quite a while. I can see why Sun responded to early complaints about Java's performance with JIT. It's clearly effective, but I'd like to know more about how the JRE decides to compile to native code. With JIT, StringBuilder doesn't buy you anything if it's compiled to native code; without it, StringBuilder can make a noticeable (on paper) difference over plain String, but I wonder whether the difference shows up much in real workloads. If a string-manipulating function is a hot spot, it'll probably be compiled to native code. I suppose one would have to examine the memory impact of String v. StringBuilder as well.

I wouldn't be surprised if most of the time a language spends in system mode comes from calls to brk(2).

Independent Study: A Universal Modular ACTOR Formalism for Artificial Intelligence

2009-09-13T09:18:00.008-06:00

(This is one of a series of posts about papers I'm reading for an independent study with Prof. Evan Chang at the University of Colorado, Boulder. The format of this and subsequent papers will be similar to that of a review of a paper submitted to a conference. These are already-published papers, so I'll be writing with the obvious benefit of hindsight.)

Submission: A Universal Modular ACTOR Formalism for Artificial Intelligence [PDF]

Reviewer: Nicholas Dronen

Please give a brief, 2-3 sentence summary of the main ideas of this paper:

The authors present their notion of an actor, a formalism which unifies control flow and data flow. Actors allow programs to achieve a high degree of parallelism without the explicit use of semaphores. Actors accomplish this by being free of side effects and communicating with other actors only by passing messages.

What is the strength of this paper (1-3 sentences):

The paper's greatest impact is the scalability (i.e. degree of parallelism) and reliability (discussed below) of actors.

What is the weakness of this paper (1-3 sentences):

While the ambition of the paper is admirable, it nonetheless casts too wide a net, covering topics from hardware design to formal representations of knowledge and belief. Historically, the value of actors as a way to reason about the properties of programs isn't clear, considering that other approaches, such as the pi calculus, have seen wider adoption.

Evaluation

In retrospect, a great deal of this paper could be removed without harm. Specifically, the idea of actors as an appropriate abstraction for hardware (e.g. removing interrupts) and the discussion of using actors to represent knowledge could be completely removed. The remaining material could then be expanded, ideally covering in more depth the concurrency-related aspects of actors.

Novelty

Some aspects of actors -- such as message passing and perhaps pattern matching -- are not original. What is novel in this paper is the combination of these techniques into a scheme that provides a high degree of concurrency.

Convincing

Quite.

Worth Solving

Yes.

Confidence

I am very confident in my evaluation of this paper. I've been thinking about actors for a year or so.

Detailed Comments

To understand actors, consider a thread. Its stack is finite, but it's undecidable how much stack space a function running in a thread requires, so system designers allocate a constant amount of stack space for each thread -- enough for well-behaved programs, but still too much to allow even tens of thousands of threads on a reasonably-equipped machine. It's conventional for 2 MB to be allocated to a thread on a 32-bit machine running Linux. If a process is limited to 2 GB of memory, and assuming for the sake of discussion that no other implementation issues (such as the placement of the heap) interfere, a process can have at most ~1000 threads. Actors solve this problem, which is admittedly not an enormous problem, but the solution to this problem solves another huge problem -- the high degree of concurrency that programs will require in order to exploit the large number of cores of future processors.

An actor is a user space thread, the stack of which doesn't grow -- essentially a tail-recursive function. So the system designer only has to allocate an extremely small amount of stack space -- basically enough for an activation record and local variables -- which means that a single process can contain many thousands of actors. For example, a benchmark has run with 20 million Erlang processes (the Erlang term for an actor).

An actor contains only local state, so it has no side effects. Since there's no shared state, the programmer doesn't have to concern herself with error-prone synchronization primitives, such as semaphores. Actors communicate with each other by sending messages. The incoming messages for an actor are placed in an actor's mailbox (this term doesn't appear in the paper but is in common use today). When an actor receives a message, it uses pattern matching (in the style of Haskell and ML) to determine the type of the message.

One would be wrong to infer that synchronization primitives are not necessary for a runtime system that supports actor-based programs in a single operating system process on an SMP or multicore machine. Imagine a program running on a multicore machine with 10,000 actors, and 9,999 are sending messages to the remaining one (who we'll call A). The actor A's mailbox will be filling up with messages, and it's possible that two actors executing concurrently can send a message to A at the same time, which implies that the scheduler for A has to be capable of handling two requests at once without corrupting A's mailbox.

The paper's authors found inspiration for actors in packet-switched networks, which in part explains why a program written in actor-based language seems so much like a distributed system. Where the program has actors sending messages to each other, the distributed system has nodes exchanging packets. In the domain of software architecture, there is an interesting analogue between REpresentational State Transfer (REST) and the actor model, which is mentioned during the question and answer period of a recent presentation by REST advocate Steve Vinoski.

Additional benefits of actors: since they contain only local state, they can be terminated if an error occurs. This effectively isolates errors. A small amount of data may be lost, but the program continues to run. Since actors consume so little memory, each actor can be monitored by another actor. The monitoring actor can be notified when the "child" actor dies, and it can restart the child. This increases the reliability of programs. Another consequence of the lack of global state in actor-based programs is the ease with which code can be reloaded into a running program without consequences. This increases availability, which is especially important in systems that are supposed to be fault tolerant.

Independent Study: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

2009-09-07T08:03:00.017-06:00

(This is one of a series of posts about papers I'm reading for an independent study with Prof. Evan Chang at the University of Colorado, Boulder. The format of this and subsequent papers will be similar to that of a review of a paper submitted to a conference. These are already-published papers, so I'll be writing with the obvious benefit of hindsight.)

Submission: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part 1

Reviewer: Nicholas Dronen

Please give a brief, 2-3 sentence summary of the main ideas of this paper:

The author presents the basic symbols, syntax, and semantics of a Turing-complete programming language, LISP, providing compelling examples of the language's expressiveness. He then discusses how it is implemented on the IBM 704 computer.

What is the strength of this paper (1-3 sentences):

It describes a new programming language based in part on Church's lambda calculus which can be applied in both practical and theoretical domains.

What is the weakness of this paper (1-3 sentences):

Being such a seminal paper in the PL literature, it's hard to find fault with it. It is interesting that the author doesn't himself discuss deficiencies in the language or its implementation.

Evaluation

This paper is excellent. The author explains his ideas clearly and comprehensively.

The contemporary reader does have to adjust his vocabulary at times, because McCarthy's terminology is outdated — for example, where a contemporary paper would use the term memory cells, McCarthy says registers.

Novelty

To my knowledge, there was only one other functional programming language at the time of publication, IPL, but LISP was a big improvement. LISP's garbage collection is extremely useful to programmers, freeing them from having to manage memory explicitly.

Convincing

Extremely.

Worth Solving

This paper is seminal in part because it solves several problems at once.

Confidence

How confident are you in your evaluation of this paper?

Detailed Comments

This paper is exemplary in the literature of programming languages. It sets the standard for the formal definition of a programming language: present the basic symbols and syntax, define the semantics, discuss implementation issues.

I'm fascinated by the fact that the LISP function apply "plays the theoretical role of a universal Turing machine and the practical role of an interpreter." Since LISP is based at least in part on the lambda calculus, and the untyped lambda calculus is Turing-complete, it's fair to assume that the universality of apply follows as a consequence, but I'm not capable of providing a proof, nor, if I were capable of such, would I have time to do so. However, it's clear that the built-in substitution function subst has the same role as substitution in the lambda calculus. Another connection between LISP and formal representations of programming languages is that the function eval seems to be a handmaiden of the operational semantics of the language. The signature of the function is eval[e; a], where e is an expression to be evaluated, and a is list consisting of pairs, the items of which are, first, an atomic symbol, second, the expression for which the symbol stands.

And, practically speaking, apply is a function implemented in LISP that interprets LISP — highlighting the bootstrap problem that early computer science students grapple with, if only briefly: how do you compile a compiler? But further, one can view it as a virtual machine for LISP. The language's use of Polish notation reminds me of the stack-oriented nature of the Java virtual machine.

One of the questions I had from last week's paper is whether LISP was, as the paper described, actually capable of performing symbolic differentiation of functions. This paper provides a concrete answer. LISP is indeed capable of evaluating the derivative of a symbolic expression with respect to a variable. It's surprisingly simple, amounting approximately to replacing occurrences of the variable with ZERO or ONE, depending on whether they are being added or multiplied, respectively. So, for, example, the derivative of (PLUS 9 y) with respect to y is (PLUS 9 0) and the derivative of (TIMES 5 z) with respect to z is (TIMES 5 1).

Some of the built-in functions are named poorly: car is a mnemonic for "contents of the address part of register" and cdr stands for "contents of the decrement part of register." Today a language designer would give those functions names in harmony with their semantics, not their implementation. I believe this deficiency in early LISP was corrected at some point (with car replaced by first and cdr by rest), but I don't know what Scheme or Common LISP use.

Garbage collection does not occur intermittently. Rather, it occurs when the program needs memory but free memory has been exhausted. It does a simple reachability analysis. In the IBM 704, characters are 6 bits, and a machine word is 36 bits. A string of characters like "DIFFERENTIATE" is represented by a linked list of structures. The first field of each structure is a pointer to a 6-character memory cell. The second is a pointer to the cell of the next structure. The string "DIFFERENTIATE" decomposes to cells containing "DIFFER", "ENTIAT", and "E."

Internet of Things

2009-09-04T15:05:00.005-06:00

Some quick thoughts on machine-generated and -consumed data (as opposed to documents) being the next phase of the development of the web. First thing that comes to mind is, this will require our infrastructure to be more intelligent, such as using feedback control systems to regulate the machine-to-machine flow of data. See, for example, "Black-Box Performance Control for High-Volume Non-Interactive Systems". Also, a human user navigating pages on the web (or using a search engine to go directly to the desired content) is a request-response style of interaction. HTTP does this quite well. However, data being generated by machines in the real world and consumed by machines suggests a publish-subscribe or at least a hybrid request-response, publish-subscribe style of interaction, a task for which protocols like XMPP are suited.

Independent Study: Early LISP History

2009-08-30T09:36:00.010-06:00

(This is one in a series of posts about papers I'm reading for an independent study with Prof. Evan Chang at the University of Colorado, Boulder. I'll try to follow the same format in each post — a general discussion, followed by specific points of interest, and finally questions.)

Discussion

Herbert Stoyan's version of the early history of LISP faces hagiographic challenges. Some of the source material from which he works is undated, giving him the task of having to deduce its significance in the conception and development of LISP. The second of the AI Memos that John McCarthy, Nathaniel Rochester, and perhaps others wrote at the MIT AI Lab in the late 1950's is undated. In another case, a graduate student enrolled in one of Minsky's courses wrote the following during a guest lecture by McCarthy:

FORTRAN plus variable functions, composite functions (Church lambda), multiple functions, several valued functions of several variables, direct sum of functions, label portion of program with facility to make symbolic substitutions therein ...

This rather sketchy note, however, contains information of use to one of Stoyan's opening arguments. Citing this note, Stoyan mentions that this guest lecture is the first time that the lambda calculus appears in relation to the language that was to become LISP, reinforcing the point he makes at the beginning of his history — to wit, that LISP was not, as some believe, originally 'a clean "pure" language design in the functional direction which was comprised by AI-programmers in search of efficiency.' The original goal was simply a language to serve the ends of the Artificial Intelligence Laboratory at MIT. Indeed, Stoyan's history of the language shows that McCarthy arrived as the design of early LISP in a somewhat ad hoc manner. The language's built-in functions car (first element of list) and cdr (rest of list) were first implemented on top of an imperative FORTRAN. Furthermore, a language that inspired LISP was imperative, not functional. Quoting Stoyan,

It is one of the most important events in the history of programming that McCarthy, who was looking for a mathematical-logical programming language, found interesting elements of it in FORTRAN. He was fascinated by the idea of writing programs with "algebraic" means, i.e. mathematical expressions.

(The expressions McCarthy eventually settled on were symbolic expressions, or S-expressions, the subject of next week's paper.)

LISP as a Functional Language

While McCarthy didn't conceive LISP simply as an implementation of the lambda calculus, it is a mixed-paradigm language, containing both functional and non-functional features. A brief examination of the functional features of early LISP follows:

Higher-order functions: early LISP has a built-in functions maplist, which takes a function as an argument, so clearly it has higher-order functions.
Pure functions: I can't tell from the history whether invoking a function in early LISP could have side effects.
Recursion: definitely.
Strict vs. non-strict (lazy) evaluation: the implementation of LISP discussed by Stoyan used lazy evaluation, judging by the following sentence: "If we imagine a correct substitution function and accept the necessity for quoting all constants then there remains the well-known problem of free variables moved to wrong environments because of the lazy evaluation."
Type systems and pattern matching: it's hard to determine based on the contents of the history, but my impression is that early LISP was untyped.

LISP as a Dynamic Language

Dynamic programming languages are loosely defined, more like one of Wittgenstein's family resemblances than one of Aristotle's essences. What follows are some characteristics of dynamic programming languages, and whether and/or how they exist in LISP:

Eval: the ability to take a string representation of a program and execute (or evaluate) it. This concept originated with LISP. The fact that eval converts data (a string) into code (an execution) seems to be essential to dynamic programming languages in one respect — to wit, that what is executed does not exist at the beginning of a program's execution in a form that is directly executable by the underlying hardware. This is a characteristic of any language that executes in a virtual machine.
Higher-order functions: Yes (covered above).
Object runtime alteration: Objects do not exist in LISP, so this item does not apply.
Closures: In contemporary usage, a "closure" requires lexical (i.e. static) scope. Scoping in early LISP was dynamic, a wildly different beast, so these don't exist.
Continuations: Early LISP isn't purely functional, and the first paper on continuations was delivered in 1964 (a few years before the first implementation of LISP), so continuations were likely not part of early LISP. Further evidence for this is the fact that it had labels and iteration constructs: "Besides the `arithmentical (sic.) or replacement statement' the following kinds of statements were thought to be available.: A GO-statements (sic. -- likely "GOTO statement"), compound statements, statements for iteration, declarative statements (describing property lists) and statements for the definition of subprograms (and functions)."
Reflection: it's not clear from the history whether early LISP had anything like Common Lisp's find-symbol.

Points of Interest

One of the features of early LISP was symbolic differentiation and integration of functions? This might become clearer with next week's reading.
Dynamic scoping — not carried over to Common LISP or Scheme.
Parentheses determined by external constraint: "Therefore, the reason for selecting parentheses ... instead of brackets or braces was only a matter of chance because in 1958 the usual devices had only parentheses and nothing else."
"It turned out that the realization of recursive function was the most complicate (sic) problem in translating the LISP-programs into SAP-routines." The question was how to implement the runtime stack. McCarthy considered following the example of IPL and — as implied by the history — implementing the stack as lists. He also considered implementing the stack as something private to each function. He finally settled on using a "public push-down list" for the runtime stack.

Questions

The difference between maplist and apply is not obvious from Stoyan's discussion. I know that maplist takes a list L and a function F as arguments, applies F to each element of L, and returns a list L' containing of the return value of each invocation of F. In more recent languages (e.g. Python), maplist is called map. The meaning of apply is likely found in recent languages as well. Python has a (deprecated) apply function, which takes two arguments — a function F and a list A containing arguments to be passed as separate actual parameters to F. JavaScript's apply method (which is a callable property of a Function object, not a function properly speaking) with essentially the same signature. (JavaScript's Function object also has a call method, but unlike JavaScript's apply it takes a variable number of actual parameters instead of a single actual parameter. (I answered this question for myself before writing the discussion.)

Independent Study Schedule

2009-07-18T08:23:00.011-06:00

This semester I'll be doing an independent study -- a survey of "dynamic languages" -- with Evan Chang. Each week I'll read a paper, and write a discussion of it, which he and I will use as a starting point for an hour-long weekly meeting. I'll post the discussion notes on this blog. The papers are listed here. Some of them are quite long and may have to be covered in halves.

Herbert Stoyan, "Early LISP History", date unknown, pages unknown
John McCarthy, "Recursive functions of symbolic expressions and their computation by machine, Part I", 1960, 34 pages
Carl Hewitt, Peter Bishop and Richard Steiger, "A Universal Modular Actor Formalism for Artificial Intelligence", 1973, 11 pages.
John Backus, "Can programming be liberated from the von Neumann style?", 1978, 28 pages
Ken Iverson, "Notation as a tool of thought", 1980, 22 pages
Pattie Maes, "Concepts and experiments in computational reflection", 1987, 8 pages
Alan C. Kay, "An Early History of Smalltalk", 1993, 40 pages
L. Peter Deutsch and Allan M. Schiffman, "Efficient implementation of the Smalltalk-80 system", 1984, 5 pages
David Ungar and Randall B. Smith, "SELF: The power of simplicity", 1991, 18 pages
Craig Chambers, David Ungar, and Elgin Lee, "An efficient implementation of SELF, a dynamically-typed object-oriented language based on prototypes", 1991, 38 pages.
Cartwright and Fagan. "Soft Typing", 1991, 16 pages.
Aiken, Wimmers, and Lakshman. "Soft Typing with Conditional Types", 1994, 10 pages.

Ten papers to read

2009-07-13T09:44:00.003-06:00

For future reference, ten papers from the programming languages and programming canon.

My "Playtime"

2009-06-12T17:14:00.003-06:00

In the mid- to late-60s, Jacques Tati produced and directed a kind of slapstick comedy about modern architecture, "Playtime." It was a commercial bomb, and bankrupted his family, but it's truly a great film. After seeing it a few times, it dawned on me that the office where I work -- which is all metal and glitter and glass -- could have been a set for the film. Compare Tati's set to mine.

Lonesome Prairie Dog

2009-05-31T22:20:00.010-06:00

I got some cables and things today so I could start recording music in beginner's style, sitting at my kitchen table playing things into my laptop. The first song I wrote, probably two years ago, is "Lonesome Prairie Dog," a kind of cowboy song with some irregular meter, so far as I remember. It's the only thing I've written that I've bothered to name.

You can't upload MP3s to blogger, so I made a video of this using a recent photo. There's not a hidden musical gem at the end; GarageBand just padded the last forty-five seconds with silence. I've found that I've had to click the play button a few times to get it working, too, so don't give up.

I hope you like it.

Summer, Night

2009-05-20T23:06:00.004-06:00

DSC_0004
Originally uploaded by ndronen

I was stunned by the shadow cast by a tree onto the sidewalk tonight. A few blocks away I was thinking about the shadows and about movies, and how the movies I enjoy most assume not that this is a world of objects, but that this is a world of light. Those directors and cinematographers and set designers and lighting people seem to understand that light pays objects courtesy by making it possible for them to manifest themselves to us. So I turned around and visited that tree again.

Functional Programming is Fun(ctional Programming)

2009-04-01T08:38:00.002-06:00

The ball keeps rolling. Microsoft has has F#, a functional language for the Common Language Runtime (CLR, the .NET virtual machine) for a while. Then there's LINQ, the functionally-inspired generic data query mechanism built into C# 3.0. Now Microsoft is involved with Haskell, one of the better-known purely functional languages of recent vintage.

One reason for the increasing interest in and support of functional programming languages is that they have some characteristics that are very beneficial when attempting to scale to a large number of cores. In particular, since all data is immutable, there are no locks. Also, unlike imperative languages (which includes Java, despite its object-orientedness), programs written in functional languages say what to do, not how to do it, which gives the compiler and runtime system freedom to, say, run parts of a loop on different cores. Anders Hejlsberg, one of the designers of C#, talks about that aspect of functional languages here (starting around 20:45).

For applications that need to run efficiently on many cores, the general migration path I see is from using threads explicitly, to using tasks (e.g. Java's Executor framework, where the application doesn't explicity create threads itself), to writing in a concurrency-oriented fashion, whether in a purely functional language using some hybrid approach. For the hybrid approach, here's a write up of some ways to do concurrency-oriented programming in Java.

(This post is based on an email I sent to my group at work. It's a Java shop.)

Hang 'Em High

2009-03-27T06:11:00.002-06:00

For such a crisp thinker as Willem Buiter, these words, with which I agree, are extremely harsh:

Too many bank insiders have exploited their monopoly of information and the control it bestows on them, to enrich themselves by robbing their shareholders blind. There has been a spectacular failure of corporate governance. Boards have foresaken their fiduciary duties. Surely, even the liability insurance taken out by board members ought not to shelter those who are guilty of, at best, such willfull negligence and dereliction of duty? Where are the class actions suits by disgruntled shareholders? Where are the board members in handcuffs?

Now that there is no meat left on the shareholder drumstick, the rogue managers and employees are going after a piece of the really juicy bird - the ever-patient tax payer. I hope they choke on it.

Governance lies as the heart of the mess. It was broken before the house of cards collapsed, and it's broken now, too, because the people responsible for the status quo are either still in power, or not on trial, or both.

I'm Looking Forward to This

2009-03-26T10:39:00.002-06:00

Be Honest But Mysterious

2009-03-26T09:56:00.001-06:00

Your boss wants to know where the reports that you were supposed to have on his desk are? Be honest with him: "I don't have them." But, instead of full disclosure, leave a little to the imagination: "And I'm not sure why." If he presses, be nice but firm: "I don't feel comfortable giving them to you yet, but I'm flattered that you're looking for them." "Who is this wild creature who doesn't have the reports?" he'll be wondering. Sure, it will feel uncomfortable for you at first, but, trust us, it'll drive him crazy. He'll probably have to contact you every hour. You won't be able to get rid of him!

First Impressions of Structural Computing

2009-03-23T17:57:00.002-06:00

A lot of research is computer science is sort of boilerplate. Like when a graduate student incrementally improves a known solution to a given problem in an established area of research. Even when it's hard, that's the easy stuff, it seems. The hard stuff involves creating a new area of research altogether. That's what Peter J. Nürnberg is up to with his idea of "structural computing." So far, a couple of pages into a couple of his papers, and really not being familiar with the hypermedia corpus, the first thing that comes to mind is a data structure in which every element is connected to every other element by way of common data structures -- e.g. array, list, hash table -- so as to enable on-the-fly views of the data to be created. And this suggests the need to transform one view into another view arbitrarily, which in turn reminds me of category theory, data provenance, and the stuff that Benjamin Pierce has been working on, but not necessarily in that order and not to imply a relationship among those things that doesn't exist.

What was Universal thinking?

2009-03-22T13:55:00.001-06:00

I love The Big Lebowski as much as the next guy, but the marketing department at Universal Studios really went too far with the their 10th Anniversary Limited Edition DVD. Come on. A bowling ball as a DVD case? Why not just give us the two disks with the bonus materials, etc, etc, and be done with it? What value does the bowling ball add exactly? What's worse, there's not even a symbol on the bottom of the plastic ball indicating how to recycle it.

2009-03-21T08:53:00.000-06:00

And on the occasion of my 39th birthday, a colleague sent me this:

Once a cuckoo told me it was my birthday and flew away.
I asked myself Have you no regard for yourself to celebrate your birthday?
Then the cuckoo came back and told my brain Birthdays are for fathers and mothers.

2009-03-21T08:36:00.000-06:00

Yesterday I turned 39. No surprises or revelations, just a sense of what it's like to keep growing older, an understanding that the tired phrase life goes on is tired because it's true. Of course, one's sense of time fluctuates, expanding and contracting, depending on the intensity of experience at that moment, depending on how much the world is defying or agreeing with you, but in all cases, things keep happening. Somewhat like no matter where you go, there you are. Both phrases are trivially true in an all-too-universal way. Perhaps the thing that distinguishes the old from the young is the knowledge that the truth of these phrases isn't trivial, because having a sense of how they are true only comes with experience, and experience only comes with age, and age implies death.

2009-03-12T08:05:00.000-06:00

Back when Todd Mytkowitz and I were looking into the feasibility of using Amazon Web Services to run a not-for-profit scientific compute service, Todd explained the idea of the service to some scientists at a conference at the Santa Fe Institute. The most surprising part of their response was that a pay-as-you-go model doesn't always fit well with the way researchers spend money, since grant money comes with an expiration date; the money must be spent within some window of time. Since it's easy to justify the purchase of computing equipment, research money sometimes goes into a new, albeit small, compute cluster. Utility compute services like AWS are metered; using them doesn't require a large initial capital outlay. So it's not possible -- or at least hasn't been possible -- to park your money there. I think a similar dynamic is at work with corporate managers and directors, who are the marketing target of Amazon's push into the enterprise: the pay-as-you-go model just doesn't fit well with the budgeting practices of large institutions. Hence, ladies and gentelmen, Amazon's new pricing model.

2009-03-06T13:24:00.000-07:00

The scary thing is I almost actually understood this.

Better Gmail is Not Better

2009-03-05T18:25:00.001-07:00

CPU consumption by Firefox 3.0.7 with:

No pages loaded 1-3%
Old version of Gmail 1-3%
New version of Gmail 4-5%
New version of Gmail (with Better Gmail 2) 73-85%

2009-02-26T11:40:00.000-07:00

It turns out that TestNG has built-in support for the functionality I just implemented for our JUnit tests.

2009-02-11T08:25:00.000-07:00

At work the time to execute all of our our growing set of JUnit tests has slowly crept up. In 2005 it took 25 minutes to build and test everything. Now it takes 65 minutes, most of which is spent running tests. So we decided to run the longest-running tests (defined at test classes which take > 30 seconds to execute) only once a week. So by default when one of these long-running test is run as part of a group of tests, it doesn't execute; to cause those long-running tests to run within Ant, you'd set a property to indicate this. However, we still wanted to run those tests in, say, Eclipse, because presumably someone who tries to run the test in Eclipse really wants it to run; one way to make this work is to check whether the value of the TERM environment variable is set to "dumb."

I created an annotation called IntegrationTest, which can only be applied to types, not methods. A nice enhancement could be to apply the annotation to methods, too, so that only certain long-running test methods are excluded or included as desired.

To mark test classes as long-running and I annotated each one like so:

@IntegrationTest
@RunWith(JUnit4ClassRunner.class)

The code for JUnit4ClassRunner is (approximately):

package com.example.build;

import java.util.logging.Level;
import java.util.logging.Logger;

import org.junit.runner.Description;
import org.junit.runner.notification.RunNotifier;
import org.junit.runners.BlockJUnit4ClassRunner;
import org.junit.runners.model.FrameworkMethod;
import org.junit.runners.model.InitializationError;

public final class JUnit4ClassRunner extends BlockJUnit4ClassRunner {
private static final String TEST_TYPE_KEY = "test.type";

private static final Logger log =
  Logger.getLogger(JUnit4ClassRunner.class.getName());

public JUnit4ClassRunner(Class<?> klass) throws InitializationError {
  super(klass);
}

@Override
protected void runChild(FrameworkMethod method, RunNotifier notifier) {
  if (shouldRun(method)) {
      super.runChild(method, notifier);
  } else {
      log.info("Not running integration test: " + method.getMethod());
      Description desc = Description.createTestDescription(
          method.getMethod().getDeclaringClass(), "Integration test");
      notifier.fireTestIgnored(desc);
  }
}

protected boolean shouldRun(FrameworkMethod method) {
  final TestType type = getTestType();

  switch (type) {
  case UNIT_ONLY:
      return !isIntegrationTest(method);
  case INTEGRATION_ONLY:
      return isIntegrationTest(method);
  case ALL:
      return true;
  default:
      return true;
  }
}

protected TestType getTestType() {
  if (isIntegrationOnly()) {
      return TestType.INTEGRATION_ONLY;
  } else if (isEclipse() || isAllTests()) {
      return TestType.ALL;
  } else {
      return TestType.UNIT_ONLY;
  }
}

/**
     * This is a bit of a hack, but seems to work.  Eclipse sets the TERM
     * environment variable to "dumb"; it's quite unlikely that a user would
     * be running tests from the command line with their TERM set to "dumb."
     * 
     * @return true if TERM is "dumb"
     */
protected boolean isEclipse() {
  String value = System.getenv("TERM") == null ?
          "" : System.getenv("TERM");
  return value.equals("dumb");
}

protected boolean isIntegrationOnly() {
  String value = System.getProperty(TEST_TYPE_KEY, "");
  return value.equals("integration");
}

protected boolean isAllTests() {
  String value = System.getProperty(TEST_TYPE_KEY, "");
  return value.equals("all");
}

/**
     * @param method The FrameworkMethod of some JUnit test method (i.e.
     * a method annotated with @Test)
     * @return true if the class in which the method is declared is annotated
     * with @IntegrationTest
     */
protected boolean isIntegrationTest(FrameworkMethod method) {
  Class<?> klass = method.getMethod().getDeclaringClass();
  return klass.isAnnotationPresent(IntegrationTest.class);
}
}

2009-02-08T14:24:00.000-07:00

When I was in grad school, I cooked, but it usually wasn't very good. Hamburgers, mac and cheese, spaghetti, stuff like that. Since I finished grad school a few years ago, I haven't had to scrimp, so I haven't cooked much at all. For lunch I've usually gone to the burrito joint across the street. That changed this Christmas when I got a Cuisinart and a bunch of cook books and cooking gear. I've been making my own sorbets for a few weeks now. So far I've made batches of lime-basil, honeydew melon-mint, and raspberry-anise. And for lunch I've found two recipes that taste good reheated. Here's one of them, an Orange Sizhuan Chicken, before it goes into the fridge.

To top it off, eating this way is usually cheaper than going out, although I do have to be careful when I go to Whole Foods. Change is good.

2009-02-07T07:29:00.001-07:00

There's an article over at TPMMuckraker that got me thinking. It's a bit of a digression, but bear with me.

There seem to be two understandings of "bureaucracy," one pejorative, one objective. In the pejorative version, bureaucracy is an organization -- typically governmental, like a regulatory agency, or that pot-bellied guy who works in the zoning department -- characterized by a terrifyingly blind, sometimes petty dedication to, say, filing all of the necessary paper work for your boat license. In the objective version, which I expect is more common amongst social scientists and the like, bureaucracy is an organization characterized by a formal structure, with rules guiding how it is supposed to go about accomplishing its mission.

I prefer the objective one; it's less driven by animus and, being more generic, it lends itself to broader application. It's more useful. With that definition, a corporation is a bureaucracy, which only makes sense: it's an organization with a blind, sometimes petty dedication to profit (if, of course, you assume that corporate governance is not completely broken, which it is). Or an army: an organization with a blind, petty dedication to killing (in the national interest).

There's a stereotype that government bureaucracies are extremely inefficient, but I think that's the wrong way to look at it. They are typically just as efficient at accomplishing the goals of the organization as corporations, the military, and other institutions. They just operate under different resource constraints. A well-run military given the right resources is an efficient killing machine. A well-run technology company given the right size (e.g. IBM) or right position in the technology life cycle (e.g. the early Cisco) is an efficient profit-making machine. And a well-run regulatory agency given the right authority is an efficient regulator of whatever it's regulating.

But like it or not, that's all they do. They don't know how to handle things that conflict with their mission; when that happens, people outside the bureaucracy may have to apply force to cause it to behave correctly. Depending on the degree of asymmetry of power between the outside group and the bureaucracy, something terrible might happen before the outside group succeeds, if they succeed at all.

So, with that in mind, please, dear reader, do remember that while bureaucracies serve a useful function within their own domain, they do little else. Banks, for example, do not love you. They're financial intermediaries, run for a profit, and they want your money; they don't give a damn whether your mother just died of cancer. Actually, I take that back, they do care if your mother just died of cancer, because that may make you more vulnerable and increase the chance that they can trick you into to giving them money to which they have no rightful claim. Bastards.

2009-02-05T19:56:00.001-07:00

Global cooling is not, mmkay?

2009-01-31T07:45:00.000-07:00

Looks like someone deployed a new feature too soon: Google is telling me that Google may be running malicious code.

2009-01-26T18:06:00.000-07:00

It sure would be cool to be able to say that you devised a way to sequester carbon dioxide created in the production of cement; creating something that useful is a progressive engineer's dream.

2009-01-26T03:21:00.000-07:00

What a meaningless exercise:

Yet one man’s flexibility is another man’s wishy-washiness, and Mr. Obama’s willingness to adapt carries the risk that he will either alienate his liberal base or fail to convert Republicans whose support he hopes to win. During his transition, Mr. Obama managed to charm conservatives; he wooed them at one dinner honoring Mr. McCain, and at another at the home of the columnist George F. Will.
But just days into the Obama presidency, some conservatives sound wary.

“I thought he did very well during the transition on things like the dinner with George Will, and all the words sounded good,” said Newt Gingrich, the Republican former speaker of the House. “But I think they are right at the cusp of either sliding down into a world where their words have no meaning or having to follow up their words with real behavior.”

There was a campaign, then an election, a transition period, and an inauguration. Unsurprisingly, the new administration is new. But note the melodramatic tone: "just days into Obama presidency," "the cusp of sliding down into a world where their words have no meaning." Sigh.

2008-12-01T09:43:00.001-07:00

The early reviews of Amazon's CloudFront are in. The question is will Akamai do business differently now? Is Amazon going to eat Akamai's business from the bottom up, much like Windows NT and Linux did (in different ways) for the UNIX workstation market? Akamai's CDN includes real-time communications like VOIP and conferencing. I wonder if Amazon wants into that space too.

2008-11-18T07:04:00.000-07:00

The opening salvo in the coming war between Amazon and Akamai.

2008-11-05T05:05:00.001-07:00

That went well, at least for pollster.com. Predicted:

Actual:

2008-09-27T19:17:00.001-06:00

Went hiking in the mountains today with the folks and my nephew. The colors are changing beautifully.

2008-09-20T14:23:00.000-06:00

Rereading an old networking textbook this afternoon, I ran across this passage:

There is frequently a trade-off between some sort of optimality and scalability. When hierarchy is introduced, information is hidden from some nodes in the network, hindering their ability to make perfectly optimal decisions. However, information hiding is essential to scalability, since it saves all nodes from having global knowledge. It is invariably true in large networks that scalability is a more pressing design goal than perfect optimality.

Computer Networks, A Systems Approach, 3rd ed., p. 318

Larry L. Peterson and Bruce S. Davie

This reminds me of an idea I and a friend have been kicking around lately: software can be optimal only within its own domain, where a domain amounts to a layer in some software stack. Kernels optimize, say, the mappings between virtual and physical pages. Compilers optimize register allocation. Application writers optimize data structures and algorithms. And that's about as good as it gets. As a counterexample, if an application writer were also to have control over and knowledge of register allocation, page tables, i/o buffering, and so on down the stack, she might be able to create a maximally optimal application, but it would come at the cost of scalability of her own productivity. It would take her longer. So efficient use of programmer time requires layering.

At first glance I thought that layering also requires software reuse, but perhaps it doesn't. An ISV, for example, could ship an application for which it wrote a one-off operating system and compiler, with layering dictated by the fact that the application, operating system, and compiler teams were completely separate and communicated only by design specs. But that's inefficient as well. So the spirit of the law of layering requires software reuse, which in turn requires that each layer be as general as possible.

All of which reminds me of the argument David Clark made back in the 80s about layering in networks. I suppose there are equivalent papers about layering in software architecture as well, the most likely (canonical) one being Douglas McIlroy's Mass Produced Software Components.

2008-09-04T12:13:00.000-06:00

Sometimes -- okay, usually -- it seems the Republic Party (might as well return the favor for "Democrat Party") thinks drilling constitutes a comprehensive energy policy. And as if that wasn't apparent before, it sure was clear after Guliani's speech last night in St. Paul:

John McCain will bring about the change that will create jobs and prosperity…let’s talk specifics…John McCain will lower taxes so our economy can grow. He will reduce government spending to strengthen our dollar. He will expand free trade so we can be even more competitive. He will lead us to energy independence so we can be free of foreign oil. And he’ll do it with an all-of-the-above approach, including nuclear power and off-shore drilling.

[ chants of “Drill, baby, drill”]

Giuliani laughs as the audience chants.

2008-08-28T07:31:00.001-06:00

In case you're wondering about the differences among select(2), poll(2), and the device-based polling approaches, they all do fundamentally the same thing -- notify the program when a socket is ready for reading or writing or when an error occurs on a socket. Select() came first in the history of UNIX, but it has a basic limitation on the number of sockets that can be monitored. It's 1024 in most cases, unless you recompile. Poll() solves this problem; it requires the programmer to allocate the array of socket structures that she passes to the system call, so in theory you can monitor an arbitrary number of sockets. (Poll() is also superior to select() in that it gives the programmer finer control over the kinds of events to watch for.) The problem that poll() has only really occurs on servers that handle an enormous number of sockets. That problem is, simply, that the array of socket structures must be copied from user space to kernel space and back again every time you call poll(). So far as I recall, this performance bottleneck came to light in the early 2000s when people were doing research on the scalability of Linux, but that's just a vague memory. The first implementation could have been done in FreeBSD or Solaris. At any rate, the user-kernel-user copy problem is the reason for what I call the device-based approaches (because they involve a file in /dev). With epoll (as it's known on Linux), the program tells the operating system which particular sockets to monitor, and the operating system tells the program when a particular socket has changed. It only tells the program that that particular socket changed. It doesn't say, "Hey, here is the entire of array of sockets you care about, and it's up to you to examine the structures to figure out which ones changed." So device-based polling is useful if you are polling a large number of sockets. Otherwise, plain old poll() should work just fine.

2008-08-15T14:28:00.000-06:00

Thinking about domain-specific languages (DSLs) ... Generally, it is easier to keep track of the role of each argument to some function/method in languages with keyword parameters (e.g. Python, Ruby). Names are easier to remember than positions in a parameter list. In a language without keyword parameters, how do you make it easy to remember which parameter is what (putting aside for the moment the usefulness of IDEs in displaying the function/method signature for you)? Here's an example of how to do that in Java. Take this function:

public void validateState(PBXConference conference, int added, int connecting, int connected, int disconnecting, int disconected) {
   assertEquals(conference.added(), added);
   assertEquals(conference.connecting(), connecting);
   assertEquals(conference.connected(), connected);
   assertEquals(conference.disconnecting(), disconnecting);
   assertEquals(conference.disconnected(), disconnecting);
}

A client would invoke it like:

validateState(conference, 2, 1, 1, 0, 0);

but that sequence of numbers doesn't help the readability of the test. So instead, while it's a bit more verbose, we can change the function definition to:

public class ConferenceStateValidator {
   private PBXConference conference;

   private ConferenceStateValidator(PBXConference conference) {
       this.conference = conference;
   }

   public ConferenceStateValidator added(int n) {
       assertEquals(conference.added(), n);
       return this;
   }

   public ConferenceStateValidator connecting(int n) {
       assertEquals(conference.connecting(), n);
       return this;
   }

   public ConferenceStateValidator connected(int n) {
       assertEquals(conference.connected(), n);
       return this;
   }

   public ConferenceStateValidator disconnecting(int n) {
       assertEquals(conference.disconnecting(), n);
       return this;
   }

   public ConferenceStateValidator disconnected(int n) {
       assertEquals(conference.disconnected(), n);
       return this;
   }

   public static ConferenceStateValidator validateState(PBXConference conference) {
       return new ConferenceStateValidator(conference);
   }
}

And the client (assuming they've statically imported validateState), can do:

validateState(conference).added(2)
   .connected(1).connecting(1)
   .disconnected(0).disconnecting(0);

which is much cleaner.

2008-08-13T14:35:00.000-06:00

From Mozilla Labs, an idea whose time is coming. I was struck by this bit though.

Our next step is to gather feedback on the prototype and the ideas behind it. We want to know if the concept has promise and is worth pursuing further. We’re particularly interested in feedback on how messaging might fit into the browsing experience and if there are other interfaces (or refinements to the two interfaces built into the prototype) that would make it easier for users to have online conversations.

We’re still considering what may come after that, but possible extensions to the Snowl prototype include:

support for additional message sources, e.g. Facebook, AIM, Google Talk, etc.;
an interface for writing and sending messages to enable true two-way conversations;

Since Facebook and Google Talk already support or are going to support XMPP, the only question is whether Snowl will support it too. Other chat services should just follow suit. In other words, there's no point in mentioning "additional message sources" when all of those sources use XMPP. Just mention XMPP!

2008-08-07T11:48:00.000-06:00

Maybe a couple of months ago some blogger whose feed is aggregated at Planet Intertwingly (I don't remember who) wrote a post summarizing his complaints about Erlang. One complaint was about extracting a value from a tuple. Say you assign a tuple to some variable, as in

1> X = {a, 10}.
{a,10}

and you want the value of the second element of the tuple. How do you do that? Conventionally,

2> {_, Y} = X.
{a,10}
3> Y.
10

Now the variable Y has the value 10. (In Erlang, the underscore is the anonymous variable.) If a tuple has a large number of fields or contains nested tuples, such tuple-unpacking statements are unwieldy. And that's what the guy objected to. It's too verbose and easy to botch.

Fortunately, pattern matching provides a simple way to work around this. Define a function that matches the tuple (particularly the first atom)

4> ValueOf = fun({a, Value}) -> Value end.
#Fun
5> ValueOf(X).
10

If you define one function for each element in a tuple, you get accessor methods for the tuple and you don't have to continue writing long expressions with a lot of anonymous variables.

2008-08-02T21:56:00.000-06:00

Here's the second GPS email for Bob's hike:

SPOT Check OK. All is well !! Bob
ESN:0-7425741
Latitude:43.9801
Longitude:-121.8084
Nearest Location: Elk Lake, United States
Distance: 0 km(s)
Time:07/31/2008 22:35:38 (US/Mountain)
http://maps.google.com/maps?f=q&hl=en&geocode=&q=43.9801,-121.8084&ie=UTF8&z=12&om=1

2008-08-02T21:41:00.000-06:00

A while ago I tweeted about the possibility of the growth of more continental/regional/local manufacturing in response to the growing costs of transportation. Twitter has some problems preventing me from getting the permalink; even so, it sort of goes without saying that that will happen. Anyway, the Times now has an article about the phenomenon.

2008-07-31T08:11:00.000-06:00

My stepdad Bob and stepsister Heather are hiking a section of the Pacific Crest Trail this month. Bob signed up for a location service that emails his friends his current location and a simple status message. I just got the first one. Here's what it looks like, including the link to the map:

SPOT Check OK. All is well !! Bob
ESN:0-7425741
Latitude:44.1548
Longitude:-121.8187
Nearest Location: Belknap Springs, United States
Distance: 19 km(s)
Time:07/31/2008 08:04:40 (US/Mountain)
http://maps.google.com/maps?f=q&hl=en&geocode=&q=44.1548,-121.8187&ie=UTF8&z=12&om=1

2008-07-30T11:23:00.000-06:00

Why are there such long delays in anaconda when upgrading from RedHat Enterprise Linux 4.x to 5.0? For a while there, restorecon(1) and find(1) were taking up most of the CPU, which I assume had something to do with setting default modes on certain files, but other than that it's just been anaconda in the process table, sometimes with awkward, crickets-chirping silences.

2008-06-03T16:20:00.000-06:00

Funny thing, I was just thinking that it's not possible to unit test C programs because, for example, a system call like read(2) just takes primitive arguments, which doesn't give you much opportunity for mocking. Then I had a small epiphany: use LD_PRELOAD to mock out external functions, including system calls.

2007-06-02T07:04:00.000-06:00

I just love this scene with Grace Kelly and Cary Grant in To Catch a Thief. There's a double entendre woven into it: Frances Stevens somewhat mockingly acts out the allure of her diamond necklace to former "cat burglar" John Robie but the scene is really about her seduction of him. The fireworks in the background emphasize this throughout the scene, but Hitchcock sort of blows their beautiful subtlety by cutting between increasingly close shots of the display and, as they become more intimate, Stevens and Robie.

2007-05-27T09:54:00.000-06:00

It was a such a pleasure to see Into Great Silence at the Chez Artiste in Denver yesterday. It's long. "Three hours, with trailers," said the guy at the ticket counter. At some point after the two-hour mark I bobbed in and out of wakefulness a few times. With the exception of some popcorn munchers (myself included) and a man across the aisle who kept talking (not whispering) into his wife's ear (who, to her credit, shushed him), the audience was as quiet as the monks on the screen. It was so quiet that at times we could hear the soundtrack of the movie playing in the theater next to us.

Most of the people there were elderly. A white-haired woman with a mobile oxygen supply was in the audience with her white-haired friend. I think I was the youngest one, and I'm thirty-seven. It's sad that apparently one's interest in otherworldly things exists generally only in proportion to one's proximity to death.

Jim Emerson's review of the movie is worth reading if you're wondering what the movie is about. Gröning spent six months living in the monastery, a film crew of one. His compositions of the monks and the monastery are masterful and gentle. Some of the lovely outdoor footage of the French Alps is presumably the work of the credited second crew.

If you have a chance to see this while it's playing in a theater, do so. Like Playtime, this is best experienced on a big screen – the bigger the better. Without that, the sense of the film being like a monastery, not just about a monastery, may not seize you.

Update: a load of Into Great Silence links, including one to an interview with Gröning, at GreenCine.

2007-04-29T07:35:00.000-06:00

2007-03-19T22:27:00.000-06:00

The farm house was gone long ago, lifted on beams and towed off to some other lot. The barn is next. They're disassembling it now, day by day, board by board. When the last red rib of this empty rib cage is taken down, they'll dig up the land, cover it with cement, and when it's all done, they will have replaced the old homestead with rows of storage for all our extra stuff. Amen.

2007-03-11T19:50:00.000-06:00

Light and lines.

2007-03-11T15:50:00.000-06:00

One thing I failed to say the last time I mentioned Truffaut is that Claude Jade is extraordinarily beautiful. A shot of her from Stolen Kisses:

What a woman.

2007-03-11T09:56:00.000-06:00

My favorite exercise in macro photography so far. I think I'm actually starting to understand aperture.

2007-03-10T18:04:00.000-07:00

I went into the mountains with my step dad Bob this morning. On the drive up, it started to drizzle....

Then it started to snow....

Bob is a volunteer with the US Forest Service. He goes into the Roosevelt National Forest in northern Colorado and does various things that I normally would think that only a retired guy would have time to do. But Bob has been volunteering his whole life. When he was young, he volunteered to go to Vietnam. Twice. On his second tour he was in a LRRP unit. At some point the unit's mission changed from conventional LRRP stuff (being dropped by helicopter into hostile territory with a small crew, sleeping outdoors, radioing in coordinates for bombing missions, hightailing it into helicopters in fields of elephant grass while being shot at by NVA, and so on) to rapid deployment support for other units in distress. He was wounded in an ambush in one such mission and lost his right calf. When he returned home, he met a man who taught him how to ski on one leg. Since then he's been helping handicapped kids learn out to enjoy the outdoors. A few years ago I remember being blown away when my mom told me on the phone that Bob was out showing a blind kid how to hunt with a bow and arrow. Unbelievable. And that's just one example.

We stopped at some Forest Service facilities and Bob shoveled their walk ways and made sure they weren't out of supplies. We went snowshoeing. At one point he stopped in his tracks. I stopped, too. "What do you hear?" I listened. He listened. We listened. "A bird chirping...." "The wind through the treetops...." "A car's tires on the paved road below...no an airplane above."

After a while we walked back down the trail to the truck. Bob recorded information about the trek — what the trail was like, the number of people he saw on the trail, the number of cars in the parking lot — in a Forest Service log book. We stopped at another USFS facility on the drive down. A little Boy Scout troop was digging a shelter in a snow bank near the parking lot.

Further down the road, Bob told me about the three ways to hunt an antelope. Spot it and loop back through a dry creek bed or other stealthy means. Set up a blind and wait. Wave a flag over a ridge to attract the animal, which is naturally curious. He offered a fourth possibility, which he'd heard of but was skeptical about: make a cardboard cut-out shaped like a cow, paint it black and white, and hide behind it while you walk at an angle towards the antelope. He also told me the reason birds eat pebbles. Being toothless, they need something to grind the food in their bellies. All this stuff I don't know. Thanks, Bob.

2007-02-25T08:15:00.000-07:00

Monster House has something for all ages, so much so that it can be seen as being about different things depending on the age of the viewer. (BEWARE: Spoilers ahead.) For the growing-ups, there are the three protagonists (two boys and a girl, in classic Hollywood fashion). Their coming-of-age adventure happens in the absence of anyone past puberty; the parents are gone for all of the action, and the teenage babysitter disappears right when things get going. For the grown-ups, there's a fairly conspicuous theme about real estate, which fits nicely with the gluttonous housing development of the past eight years. Connecting the adult and adolescent themes are the ideas of change and constance (or Constance, a character who appears late in the movie). The movie opens with a shot of a yellow leaf falling from a tree, a symbol of natural change. In the background is another symbol of change, man-made this time, a large construction crane.

The leaf floats to the ground and follows a little girl riding her tricycle along a sidewalk. She gets stuck in Mr. Nebbercracker's lawn. The old man emerges from the house and (in the movie's first line of dialogue) screams "Get off my lawn!" Then he confiscates her tricycle. This, it seems, is a man in love with what he owns.

Later, the male protagonists DJ and Chowder lose a basketball on Nebbercracker's lawn, and we get this startling shot exposing the underbelly of the property (the ball is center and the boys are to left).

The view of the pipeworks below ground sets up something that the house does later, so it's not gratuitous. Nebbercracker comes out of the house again and, after shouting at DJ, has a heart attack and apparantly dies. That night DJ becomes convinced that Nebbercracker is seeking revenge from beyond the grave. He calls Chower and arranges to meet him at the nearby housing development where we saw the crane in the opening shot. The sign outside the development cheekily boasts "Mayville Luxury Towers ... Coming Soon ... We've Drained the Lake!"

The kids decide on a scheme to destroy the house, which they now believe is possessed by the soul of Nebbercracker, but they're stopped by the local police, who "arrest" the kids. "We're supercops," says the rookie, feeling emboldened by the arrest. The old-timer responds, his head down: "Yeah, that's why I live in a condo."

In a sense the dual aspect of the movie (it's one thing for kids and another for adults) derives from a play on the word possession. For kids, it's a scary and funny coming-of-age movie about a house that's possessed by the soul of a human being. For adults, it's a tale about being controlled by your possessions. However you watch it, it's a damn fine film.

2007-02-18T20:32:00.000-07:00

Sometimes at basketball games the spectators are more interesting than the players.

2007-02-13T19:02:00.000-07:00

A frame from Truffaut's Bed and Board.

It pretty much sums up the way I feel about his films. Their gentleness and unsentimental simplicity stupefies me.

2007-02-10T09:45:00.000-07:00

My friend Wendy edits for an online zine called Mental Contagion. Last fall she asked me to write a short story for it. After a few false starts, I finished it in time for the December issue. It helps to have a deadline. Don't be fooled by the title.

2007-01-21T10:14:00.000-07:00

The first movie Alan Arkin directed was Little Murders. It's based on a play, so it's somewhat talkie, but the dialogue itself is very entertaining. Take this scene in which Alfred, a nihilist, meets the family of Patsy, his optimistic girlfriend.

MRS. NEWQUIST:

Exactly what sort of work do you do?

ALFRED

Oh, it's very complicated. You don't really want to know.

PATSY

You may as well....

ALFRED

Well, I began as a commercial photographer.

PATSY

He began as a painter.

ALFRED

Oh, I was a bad painter.

PATSY

Says you!

MR. NEWQUIST

Jesus Christ, would you let the boy finish? (Looking at his wife.) Well?

ALFRED

I began as a commercial photographer and was doing sort of well at it.

PATSY

Sort of well? You should see his portfolio. He has work in Holiday, Esquire, The New Yorker, Vogue...

MR. NEWQUIST

Vogue?

KENNY NEWQUIST (with mock excitement)

Woo! Woo!

ALFRED

It's an overrated business. But after a couple of years of doing sort of well at it, things began to go wrong. I began losing my people. Somehow I got my heads chopped off. Or out of focus. Or terrible expressions on my models. I'd have them examining a client's product like this.

Like that. A face would be really ... The agencies began to wonder if I didn't have some editorial motive in mind.

Suddenly the apartment shakes from a small earthquake, as though expressing the anger that the Gods of Advertising harbored against Albert.

ALBERT (cont.)

Which was not true, but once they planted the idea.

The lights in the apartment go out.

MRS. NEWQUIET

Oh, I didn't mean to interrupt, dear. How far better it is to strike a match than curse the darkness -- my mother always told us that ... Go on, dear.

ALBERT

Well, my career suffered but there was nothing I could do about it. You see, the harder I tried to straighten out, the fuzzier my people got, and the clearer my objects. Soon my people disappeared entirely. They just somehow never came out. But the objects I was shooting ...

... brilliantly clear. So I began to do a lot of catalog work.

The lights come on again.

ALBERT (cont.)

Pictures of medical instruments -- things like that. It was boring but it kept me alive. (Takes a deep breath.) I suppose the real break came with the SEM show. They had me shoot thirty of their new models. They hired a gallery and put on a computer show. One hundred and twenty color pictures of computers! It got some very strange notices, the upshot of which was that the advertising business went thing crazy and I became commercial again.

MRS. NEWQUIST

You must be extremely talented.

ALBERT

I got sick of it. Where the hell are standards? That's what I kept asking myself. I mean those people will take anything. Hell, if I give them a picture of shit, they'll probably give me an award for it.

MRS. NEWQUIST

Language, young man.

ALBERT

So that's what I do now.

(Silence.)

MR. NEWQUIST

What?

ALBERT

Take pictures of shit.

2007-01-07T12:19:00.000-07:00

Ah, the Presidential Inauguration of 2001; I remember it well. It was a new beginning for a nation. The Mall hummed with hope and good cheer. So much potential! So many possibilities!

If only George W. Bush had the vision and courage at the time to give the following speech:

My fellow Americans, the United States of America is and has always been the land of opportunity. From all over the world, immigrants come to America full of hope, looking forward to a future that exists in their hearts, a future that America will allow them to create with the determination of their hands and the ingenuity of their minds. The people of our beloved country were blessed with that opportunity at the birth of this great nation, thanks to the wisdom of our founding fathers and the Grace of our Lord. It is my wish that we will continue to enjoy this opportunity. Therefore, I will not take the Oath of the Office of the President of the United States of America. I'm just not cut out for it. I was thinking, maybe I'll shoot for Baseball Commissioner instead. Thank you and God bless America.

2007-01-01T08:56:00.000-07:00

There were different things about Christmas this year. It was Mom and Bob's first Christmas in their new house in Loveland. And for the first time I met Heather, my first step sister (first sister of any kind, actually, and who happens to have wicked Scattergories kung fu, so watch out), and her daughter Katie. Without further ado, the photos....

The cute and imaginative Katie looking adorable in front of the tree.

Looking even adorabler.

With her excellent mom, Heather.

Peeking!

And all of the above plus Mom and Bob.

Happy New Year, everybody!

2006-12-31T15:52:00.000-07:00

2006-12-31T15:50:00.000-07:00

2006-12-21T18:55:00.000-07:00

The crew just finished clearing the snow from the parking lot with a Bobcat. They worked all day, some with shovels. Last night the air filled with flakes. Tonight it's fog.

2006-12-21T07:53:00.000-07:00

We've had two or so feet of snow around Denver since Wednesday morning. I took these last night right before going to sleep.

2006-12-20T09:41:00.000-07:00

2006-12-19T06:00:00.000-07:00

As if on cue, Paul Matwychuk writes about Christopher Guest's antipathy.

2006-12-16T19:24:00.000-07:00

Early last January at the Hotel Donaldson in downtown Fargo, I promised to write something to convince a friend, John Lamb, of the reasonableness of the claim that the Coen brothers are sometimes unsympathetic to their on-screen subjects. I don't know that I can present an airtight case for the claim, but I'll kick the idea around for a while and see what happens.

I first heard the claim a few years ago at the University of Colorado, during a "Cinema Interruptus" -- a viewing of a film during which anyone in the audience can yell "stop" at any time in order to air a comment or question -- hosted by Roger Ebert. There were five sessions. On Monday we watched Fight Club from beginning to end, no interruptions. From Thursday to Friday we watched it again, interruptions allowed, for an hour or so each day. (Ebert's been doing this every year for a while. The schedule for that event isn't online, but last year's is [PDF].)

Anyway, that week Ebert mentioned that some people have criticized the Coen brothers for lacking sympathy for their characters. I think he said it during the scene in which The Narrator, Edward Norton's character, beats the blond character to a bloody pulp and justified it with, "I wanted to destroy something beautiful." Ebert elaborated on his statement for a moment, no one had anything to say in response, and so he pressed play on the DVD player and Fight Club resumed. I don't remember his elaboration, but I remember finding it convincing and I was foolish enough to pass on the idea to John, who immediately attacked it with the simple rejoinder: Tom Reagan (Gabriel Byrne) in Miller's Crossing.

In the world of Miller's Crossing, Tom is real, no doubt about it. On the surface, he's as cold as ice, a man seemingly without a heart, an idea that is repeated in his separate conversations with Verna Bernbaum (Marcia Gay Harden) and her brother Bernie (John Turturro). The opening shot of the movie even makes this point. The counterpoint is that he refuses to kill even a rat like Bernie. Bernie plays his virtue into a weakness, and Tom turns Bernie's play into an advantage in the magnificent game he plays in order to save Leo (Albert Finney), the man he seemingly betrays, from himself. A man does what he has to survive, but what he does to survive is, as Johnny Caspar (Jon Polito) says in the opening scene, "a question of ethics." Tom's dream about watching the wind take his hat away illustrates the sacrifice that he makes for Leo. Initially we're led to believe that the dream has something to do with what happens at Miller's Crossing. At the end we can see that the hat has something to do with Leo. Tom was doubly-bound. He was bound by loyalty to help Leo, and his own notion of manhood bound him to not try to hold onto him even after helping him, because "there's nothing more pathetic than a man chasing his hat." On the other hand, the deliberate and obvious downward push of the camera in the closing shot emphasizes the knowing look that Tom gives from under the brim of his hat. Perhaps Tom's nightmare about his hat didn't come true after all.

What the Coen brothers did with Miller's Crossing has the weight of Coppola's Godfather, but where Coppola made a gorgeous movie about family as a metaphor for capitalism in America (to verify, see The Kid Stays in the Picture)), the Coens made a gorgeous movie about loyalty, ethics, and a man with a hat. A token of the excellence of the movie is the fact that the meaning of the title is overloaded: while Miller's Crossing is the place where Tom Reagan is supposed to kill Bernie, it also alludes to Tom's deliberate double-crossing of Johnny Caspar and to the ideas at the heart of the film.

Having said that, I think that what Ebert said about the Coens should not be taken to mean that they are incapable of creating believable, complex characters. Rather, it should be taken to mean that aspects of the films of the Coen brothers betray a certain schadenfreude.

Kirkegaard objected to schadenfreude on the grounds that, in his estimation, it presupposes the incorrect metaphysical assumption that subject (laugher or audience) and object (laughee or character) are distinct. If you consider film to be the medium that most closely resembles human consciousness, then choices of lighting, camera placement, composition, sound, and editing are equivalent to aspects of consciousness (e.g. sense perception, feeling, memory, and so on). Film being a collective effort, the minds that make these choices are often distributed rather than centralized. However, there are certain directors whose discipline and aesthetic sense are strong enough to leave a signature on their films. The Coen brothers are among them. It makes sense to say that the Coen brothers are an auteur (singular, not plural) in so far as they share the same filmic vision. People who've worked with them say that it doesn't matter which one of them you ask, you'll get the same answer either way. As for discipline, like Hitchcock, the Coen brothers shoot cut-to-cut, storyboarding every scene in advance and sticking to them.

Something that is, at most, evidence of this metaphysical sense of distance in Coen movies or, at least, allows the distance to exist in the first place is the self-conscious indebtedness of their films to early cinema. Many of their stories and characters are lifted directly from stories and characters from movies of the 30s and 40s, especially film noir. The Big Lebowski is based on Raymond Chandler's The Big Sleep. The Hudsucker Proxy is an homage to Frank Capra. There are riffs on the classics, too. Blood Simple plays on the two-men-and-a-woman convention of Double Indemnity and The Postman Always Rings Twice, but Abby (Frances McDormand) is less of a femme fatale and more of a horror flick survivor, like Jaime Lee Curtis's character in Halloween. The femme fatale character appears in disguise in The Man Who Wasn't There -- another stab at the Double Indemnity and The Postman Always Rings Twice -- in the form of the homosexual man seeking venture capital funding for his dry cleaning enterprise. The relationship between Ed Crane (Billy Bob Thornton) and Birdy Abundas (Scarlett Johansson) is obviously taken from Double Indemnity, with attempted fellatio and a car accident thrown in for fun. Another aspect of this indebtedness is the way characters are dressed up in stylistic accessories from the art of the past: the rapid-fire speech of Barton Fink and The Hudsucker Proxy; the precious (although lovely) use of the Chandleresque phrase "on account of" twice in The Man Who Wasn't There; the hyperbolic characterization of the wide-eyed Norville Barnes in The Hudsucker Proxy.

Some Coen characters, such as Tom Reagan, feel real. Others, however, feel like artifacts -- entertaining artifacts, well-executed artifacts, but artifacts nonetheless -- from the Golden Age of Hollywood.

Moving on to something funner: violence. Consider this passage about The Rock (not a Coen movie) from Eric Lichtenfeld's Action Speaks Louder:

Stylistically, the scene is mostly just overwrought; that is, except for one bit of business that is so nasty, it is outright soulless. One of Hummel's men throws a guard out of a guard tower window. After the toss, [director Michael] Bay and [editor Richard] Francis-Bruce double-cut the impact; that is, they cut to two -- two -- close-ups of the guard's face as he strikes the rain-lashed asphalt, amid shards of glass. Certainly, there have been action films as violent as The Rock, but what makes this act so wanton is that it happens not to a character the audience has grown to love or hate, but to one who is inconsequential. We can find an action film's conscience, or lack thereof, in how it treats its noncombatants, because here is how the filmmakers choose to present life and death as an abstract, or pure value -- that is, as a value uncomplicated by the story. For instance, the last act of Lethal Weapon surges with violence -- violence at a crowded nightclub and on crowded city streets. But only the police and the villains sustain serious damage.

Lichtenfeld argues that portrayals of violence against certain subjects, such as innocent bystanders, are unconscionable in action films. Another example of this kind of violence occurs in Pulp Fiction, where a noncombatant is wounded in the intersection shootout between Butch Coolidge (Bruce Willis) and Marsellus Wallace (Ving Rhames). Early in the passage, by emphasizing the quality of shot (close-up) and their quantity (two), he implies that the manner of the portrayal is relevant as well. When talking about schadenfreude in Coen brothers movies, then, a relevant question is who suffers and how do they suffer?

With that in mind, let's look at some instances of fatal violence in Coen brothers movies. An event that I'll call the Ridiculous Death occurs in at least three of their movies. In the Ridiculous Death, a character's demise is drawn out for comic effect. Take the famous "Danny Boy" scene in Miller's Crossing. Two goons armed with Tommy guns attempt to hit Leo in his house. Leo shoots and kills one of the goons with a revolver. He escapes, along with the dead goon's Tommy, by sliding down the roof to the yard. From Leo's point of view on the ground, we see the second goon appear in the window. Leo pulls the trigger on the Tommy and holds it, spewing fire and bullets into the back of the second goon. The goon's body bounces and twists. While Leo holds the trigger of his gun consciously, the goon does so out of reflex. His body is being demolished, so his hands clench, causing the Tommy to fire. Where a puppet master uses strings or wires, here the Coen brothers use bullets. As his body spasms, his Tommy gun becomes a loose cannon, shooting a trail of bullets up a wall, along a painting, around a chandelier, and even through both of his feet.

Obviously, the death of the goon in the window is complicated by the story. By virtue of his particular embroilment, the goon is not exempt, in Lichtenfeld's formula, from being an appropriate subject for a portrayal of violence. He tried to kill Leo; in turn, Leo kills him. He's fair game. However, the amount of time spent on the shooting of just that goon (twenty seconds, forever in movie time) and the detail that went in the sequence (i.e. the painting, the chandelier, and the shoes) are completely out of proportion to the significance of the character. Draw your own conclusion.

Another death in Miller's Crossing that I think is important is Eddie Dane's (J.E. Freeman). Here Johnny Caspar executes "the Dane" in his study.

I wouldn't say that this shot is characteristic of the shootings in Miller's Crossing. There are several shots in which the Coen brothers cut away from the victim before or as the trigger is pulled, sparing the audience the sort of gruesomeness on display here. Moreover, the Dane is a villain who hounds Tom during the whole movie, so the level of gore at the end of the movie is appropriate. What is important to me about this shot is the position of the Dane's body, which reminds me of the Ridiculous Deaths of characters in two other Coen brothers movies.

In Blood Simple, Ray (John Getz) finds Marty (Dan Hedaya) with a bullet in his chest along with the weapon, a gun that belongs to Abby, Ray's lover and Marty's wife. Thinking that Abby shot Marty, and wanting to protect Abby, Ray takes Marty's body to a field to bury him. Here we see Marty, barely alive, try to escape.

The scene is particularly disturbing. Marty can barely drag himself along the road. His chest is covered with blood. He's almost dead. Ray gets in the car to run him over and decides against it. He gets a shovel out of the car and walks over to Marty, thinking he'll smash his head with it. He decides against that, too. Ultimately, Ray chooses to bury Marty alive.

In The Man Who Wasn't There, Big Dave Brewster (James Gandolfini) enacts another Ridiculous Death. Here we see his last moments alive. He is sinking into unconsciousness and death after Ed Crane severed his jugular vein with a small knife during a struggle. We hear him gurgling, presumably choking on his own blood, as he goes down.

The Ridiculous Death: face-down, ass-up, going to the grave like a dog.

There are critics who see the cruelty here, although their emphasis is different than what I've talked about so far. Jane Dark calls a subset of the Coen brothers' movies a '"let's mock the rubes" cycle.' Jim Emerson recognizes that there's a bit shadenfruede at work in the Coen movies. Here he's addressing complaints by Christopher Hitchens and David Brooks about the sensibilities of Borat:

Both Hitchens and Brooks appear to have thought "Borat" was funny, but don't feel comfortable with that feeling. Laughing appears to have been a sin that requires some sort of confession. I have a feeling they would say the same things about Christopher Guest or Coen Bros. movies -- that they are about mocking, ridiculing, tearing down the characters so that the audience can feel superior. It does not seem to have occurred to either of them that it might be possible to laugh at -- even mock -- someone, while still feeling sympathy or even empathy. And that such feelings, as opposed to sheer derision, make the comedy even funnier.

Going back to Kirkegaard, Emerson's argument implies that shadenfreude does not necessarily presume a metaphysical error. That is, contra Kirkegaard, shadenfreude can coexist with a unicity in which self and other are metaphysically one and the same. Watching someone else suffer, we identify with them and we laugh. This is possible because -- just like a person can laugh at their own pain when it has passed -- there's an ontological distance between us and, say, the mosquito bites on Barton Fink's face. The laughter is the same, the type of distance different.

Before I wrote this, I watched (again) all of the movies I cite. That process made me realize just how good the Coen brothers are. I used to love their movies, but watching them again after studying the art/craft of filmmaking for a year or so, some of them are absolutely breathtaking to me now. I'm still convinced of a particular lack of sympathy in the Coen brothers' body of work. Shadenfreude sums that up for me. Emerson's view of that, however, shows that there's more than one way to interpret the phenomenon of shadenfreude in their movies. Maybe I'll have more to say, or less, in the future; for now, I'm content.

John?

hexencodings

Ripping and Burning DVDs with Mac OS X

Who is Don Draper?

The Wrongness, The Wrongness!

These Made Me Ha-a-appy

When 5% is too much

Why do News Corp editorials hate reality?

iPhone, Safari, and tel URI's

Rewatching Mad Men (cont.)

Shots from "Syndromes and a Century"

Readings on Analogy

Rewatching Mad Men

Independent Study Reading List, Spring 2010

A Memory of Vic Chesnutt

Wiki terminology, like wikipedia, not optimized for search.

More papers to read

Independent Study: Concolic testing for web applications

Notes for Information Retrieval Quiz #3

Independent Study: Concepts and Experiments in Computational Reflection

A Little History of Electronic SEC Filings

Modeling the World Wide Web

Independent Study: Traits: Composable Units of Behaviour

It's Expensive Being Rich

Meditations on Meat

Avoid the Lippis Report

Notes on Content Security Policy

Independent Study: Web Application Security

Indepent Study: Defending against Injection Attacks through Context-Sensitive String Evaluation

Independent Study: Static detection of security vulnerabilities in scripting languages

Independent Study: Ripley: Automatically Securing Web 2.0 Applications Through Replicated Execution

Independent Study: Spectator: Detection and Containment of JavaScript Worms

Fibonacci Strings and Performance

Independent Study: A Universal Modular ACTOR Formalism for Artificial Intelligence

Independent Study: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

Internet of Things

Independent Study: Early LISP History

Independent Study Schedule

Ten papers to read

My "Playtime"

Lonesome Prairie Dog

Summer, Night

Functional Programming is Fun(ctional Programming)

Hang 'Em High

I'm Looking Forward to This

Be Honest But Mysterious

First Impressions of Structural Computing

What was Universal thinking?

Better Gmail is Not Better