Thursday, December 28, 2006

2006 Year-End Language Version Wrapup

At the year end, to help give a sense of progress of time, we present the current versions of some of our programming language and tools favorites.

We close this list with a quote from the British computer scientist who created the ML programming language when asked "Did you learn Greek or Latin?":

"I learned Greek from the age of ten and Latin from the age of eight and I regarded them both as a kind of defective form of mathematics because they were taught with such accuracy."

--Robin Milner

Source: An Interview with Robin Milner by Martin Berger.

Thursday, December 21, 2006

All I want for Christmas

Attn: Request Department, Geek specialist
House of Santa Claus
North Pole

As I could not find a reputable looking web site to post my request, I'm just putting this stuff on my blog and assuming your Google alert for me will notify the right people.

Thanks for all the great stuff you got me last Christmas. Like, a new job, this blog, the chance to meet that guy from the New Zealand Supercomputing Centre, and an entertaining and thought-provoking rant in the form of The Kingdom of Nouns. It wasn't what I asked for, except for the job, but I liked it all anyway. Even the Microsoft Windows Compute Cluster 64MB promotional USB memory key that was so cheap and ubiquitous I got two at different events.

For Christmas 2006, I'd like an assortment from the following wishes:

  1. A better mental model of the web browser/web server interaction. The one I've got now is pretty rusty and broken down. I mean, how am I supposed to think about the back button in the presence of an AJAX interface? What's the right way to view multiple user browsers pointed to the same web site, as far as sharing or not sharing cookies and sessions?

  2. An elegant solution to the Tower of Babel situation regarding data representation

  3. Tab completion built in to more widgets that I use on a regular basis.

  4. Better Ant documentation

  5. Better techniques for isolating code in Java. Onejar is a pretty good start.

  6. Time to catch up on Java. I'm still stuck on 1.4.2, and now they've announced 1.6.

  7. Time to play with Ruby.

I don't know how you're going to package the "time" requests, but try to do better than giving me insomnia or something.

Tuesday, December 12, 2006

Splitting the Zip

Can you remember a time when you thought "Goodbye to splitting a file across a bunch of floppies, it all fits on a CD now"? Maybe like me you're never 100% comfortable with this form of information surgery where you split a file, usually valuable, into parts, transmit it somewhere, and reassemble. If so you blew a sigh of relief when thinking those days were over, because hey, CD's store everything. Well, it was only a matter of time before the scenario revisited me.

In this case, the patient was a 1.2GB zip file. In order to help a certain close relation meet an academic commitment at the end of the semester, I was called upon to install at home a trial version of the program used in the school lab. The problem came after the two-hour download, when the file was reported to be corrupted and we noticed about 45 megabytes were missing from the expected size.

We figured that transmitting such an enormous file was too much opportunity for error. Something got dropped in transmission. We could re-download the file on a computer with a better, faster Internet connection than our DSL hookup. We did this fairly quickly. But we still needed to get the file to our computer at home somehow. I was surprised that Firefox wasn't doing some kind of data integrity checking. My solution then was to do it manually: split the file into chunks and verify each chunk with its MD5 hash. If a chunk got transmitted correctly, it would be progress because we didn't need to start over from scratch.

Hoping to find standard Unix commands to do this, I found that split and cat both support byte mode, so they could be used. I did a quick check that the Cygwin versions worked as I thought. The procedure I used is this:

Step 1. Decide what size chunks to use

I settled on a size of 300,000,000 bytes, big enough to make five chunk files.

Step 2. Split the file

% split -b 300000000

This created a series of files xaa, xab, xac, xad, xae. The first four have the exact size specified, 300000000, and the last (xae) has the remaining bytes.

Step 3. Transmit and check integrity of the chunks

As each chunk file finished download, we ran md5sum on the chunk and compared the hash with that obtained on the originating computer.

Step 5. Reassemble the chunks

% cat -B x* >

This step took about 18 minutes on Sony Vaio laptop, and I suppose there's no surprise that virtually none of it was CPU time.

At this point we had our file back, and was full and complete. I offer this account in hopes it will be helpful. If you find it helpful, leave a comment!

Thursday, November 30, 2006

Ancient calculator

Giving new meaning to the phrase "sun microsystems", scientists have reverse engineered the utility of 82 brass pieces discovered among shipwrecked remains off the Greek island Antikythera in 1901: an astronomical calculator. Its capabilities:

The calculator could add, multiply, divide and subtract. It was also able to align the number of lunar months with years and display where the sun and the moon were in the zodiac.

Wednesday, November 22, 2006

F# -- Evil Empire's Venture into Functional Languages

One thing I heard at SC06 last week was a Microsoft developer mention F#, Microsoft's offering in the functional language arena running on the CLR (.NET runtime) that he claimed made use of the best features of Scheme, Haskell, and OCaml. I remember giving a presentation of IA+ back in 2001 to my research group, with a Microsoft researcher in the audience mention that Microsoft had grant money for developing functional languages for .NET. It's pretty rare to find funding for language development, so I'm curious to know the origins of F#, whether it is purely in-house, brought in from the outside, or a combination.

SuperComputing 2006 Retrospective

JFKBits is back from the ACM/IEEE Supercomputing 2006 Convention. I've submitted my expense report, written up my trip report, and started the follow-up process with contacts I made. Since they chased us from the exhibit hall floor as soon as it closed, and I was lodged at one of those too-expensive-to-give-free-Internet hotels, this blog didn't get the daily updates I would have liked. But here's a few moments from SC06.

Speaking of expense reports, my top expense many days was lunch. The slow yet pricey food service at the Convention center gave new meaning to the phrase "six dollar burger". I chuckled every time I stood in line, for my $10 cafeteria-quality burger-fries-coke meal, at the sign that read "Thanks to Microsoft for this food station", left over from the free reception on Monday night.

Best gaff: talking with a nice lady from the National Security Agency. My usual pattern in talking with people at our exhibit included asking where they worked and what they worked on. I knew with someone from NSA not to expect much of a detailed answer. But I didn't expect this:

Me: Ahh, the NSA. What do you work on out there? Because I have a friend who works for NSA in Security Enhanced Linux.

NSA Lady: (Brief pause) Oh yes, the SE Linux people work in another building. (Leaves it at that.)

It was only when I was reading from Applied Cryptography last night about how long it would take a certain number of computers to crack a message encrypted with a certain length key that I realized how absurd my inquiry was. I had asked an employee of the National Security Agency attending the premier supercomputing conference what she worked on. At least I feel a trifle more secure.

She did let me know there wasn't a chance that she would download any of our software from our web site, let alone install anything on a trial CD picked up at the conference.

There were a lot of other great people I met too. Three other interesting people were

  • CEO of the New Zealand Supercomputing Center. What's that? It's what you get after a prominent series of movies filmed in New Zealand pays for thousands of computers and then leaves them with nothing to work on.

  • A couple from Washington DC from a volunteer organization that helps pre-college young people in sometimes disadvantaged environments prepare for college. With supercomputers. I'm not joking -- they told me they had assembled a low-wattage Beowulf-type cluster for their kids to use, and were looking for donations of software to use on it.

  • An engineer with two young homeschooled daughters. He told me he had some spare compute power in his basement and was thinking of running an airflow simulation of a car in his spare time. I didn't tell him I someday hope to balance my checkbook in my spare time.

The Japan Aerospace Exploration Agency (JAXA) had cool videos of their rockets and cleanrooms. Another Japanese research lab was doing fluid flow analysis of how a baseball travels, and had set up a batting cage so you could hit, with a forced feedback bat, a projected virtual ball. Several 3D stereoscopic displays were set up, including one from Boston University that I thought looked like a giant shrimp (turns out to be something like magnetic field lines coming out of the earth).

Monday, November 13, 2006

SC06 Exhibit Hall Taking Shape

Tampa, FL - The SuperComputing 2006 (SC06) Exhibit Hall in the Tampa Convention Center is a crazy place this morning, littered with cranes, cables, girders, lights, posters, and plenty of silicon and copper. Languages, frameworks, alliances are on the buzzword menu. One sees a lot of exhibits that make you think "hey, I wish I'd thought of that."

One nice language feature of Mathematica I've been playing recently is the ability to make arguments of a function held in unevaluated form, essentially giving you the ability to write your own control structures. If Mathematica doesn't have a repeat-until loop, you can write your own. It's Algol-like call-by-name, in case you want to program that way.

A bit of blog administrivia, regrettably we got a bit of comment spam lately so we've reinstated the captcha requirement.

Wednesday, November 08, 2006

Making the sale

We recently bought a car (see Web Security As it Really Is for the prequel). Good car, from a high-volume dealer. That means we talked with a salesman and arrived at a decision. Yesterday a lot of people made decisions, whether to stay at home or to go to the polls, and once at the polls, what to do with the little boxes or circles or touch-screen input areas.

Today I just am reflecting on how decisions get made, and the role of the salesman and his pitch in arriving at them. I am much more an engineer than a salesman, and sometimes I think I could work as an anti-salesman, somebody you bring along to a store or a car dealership so I can explain to you why you shouldn't buy something.

Malcolm Gladwell includes the Salesman as one of three important figures in his best-selling "The Tipping Point", talking about how messages get spread in an epidemic, explosive, exponential fashion. The role of the Salesman as I gathered was to be an emotional persuader, someone who incites people to act. The Salesman is an important role in society, but by nature he represents someone else's interests, not yours.

When we bought our car we researched long and hard. We read the illuminating "Confessions of a Car Salesman" on We were prepared to deal with the car salesman, and I think we did well. I put part of the credit for our success in all the hard work we did to research our purchase before we set foot on a dealership. What caught me off-guard was the business manager, who hit us up to buy an extended warranty after our hours-long ordeal inspecting, haggling over, and agreeing to buy the car that we had researched.

We didn't buy the extended warranty. But the pressure to buy was unexpected, and was palpable to an extent made possible, I think, by my lack of preparation for it. I knew the car in very definite terms, as a matter of fact we were familiar with the same make and model. The warranty was unknown to us, familiar only in vague terms an fuzzy feelings.

I'm afraid our voting decisions are more like my experience of trying to figure out whether to buy the warranty than buying the car.

A few years ago I attended a talk by someone who works as a political analyst. He presented some research from the 1994 Illinois governor's race between Jim Edgar and Dawn Clark Netsch. It featured a fascinating experiment where people are set in a room with a joystick that lets them indicate in real-time their approval of the candidate being interviewed on a TV screen in front of them. What we watched in the talk then was an averaged graph of people's approval over time superimposed over the same video clip they watched. As soon as Netsch mentioned something about not supporting mandatory tougher sentences on a certain type of criminal conviction, viewers' approval started to drop steadily. Netsch lost the election partly due to her stance on mandatory tougher sentences. What was interesting was that when you hear Netsch explain herself on the issue, it was not as clear a difference between her and Edgar. She objected to the mandatory part of the proposal. She reasoned that by making the sentence mandatory it takes away an element of flexibility from the judges actually present and hearing the particulars of a case. She wanted the judges to retain that flexibility. You can argue with me about whether this makes Netsch "soft on crime" as the voters apparently perceived, but this subtlety in the debate was lost on me when I was watching those commercials back in 1994.

Relying on TV commericials was not a good way for me to learn about the candidates.
The salesman, and I include here the architects of political messages, are not at heart interested in reasoned debate about their product. They're interested in getting someone to make a decision.

I heard an upper level software manager relate an imaginary conversation with a customer about a certain usability issue. As a developer, I wanted to help that customer with the usability issue. But the manager's position was summed up in his question "Come on, is this issue going to stop me from getting the sale?"

Decisions play a vital role in life. But we've got to realize that when it comes time to buy or vote, you better have done your research outside of the arena where salesman are pitching and people are trying to get you to make a decision in their favor. Because as my wife observed when told that the dealership doesn't fall in love with their cars, they want to move them: "yes, but we have to live with this car after the sale."

JFKBits at Supercomputing 06

Dear JFKBits readers,

Through a series of inexplicable events, I will be attending Supercomputing 2006 in Tampa, Florida next week. Come see me in booth 1946 if you're there and ask for the Remote Services developer.

Wednesday, October 18, 2006

Of teachers and hoopsters

Let me say right off that I think teachers should be paid more.

But I'd also like to challenge an oft-spoken notion that we value sports players economically more than teachers.

What has this got to do with this technology-based blog, you ask? Well, we here at JFKBits value education, and we value sports. And we also wrote a program to arrive at our featured statistic. So, there you go. On with the show.

Have you ever thought about teacher's salaries on a very small scale? For example, have you ever thought what it would take to go in with some other parents and start your own school? How economically feasible would it be? Looking strictly at the salary cost of a school, ten families hiring one teacher for a school year might need to split a low $40,000 salary into a $4,000 per family share. A K-12 school with equal numbers of students per grade works out the same way, each grade level is essentially a one-room school where each child's family splits the teacher's salary costs, plus some fraction for administrators.

The basic idea here is the cost of supporting a teacher is proportional to class size. Or, how many customers can a teacher provide services to within a given time period.

This ratio is far different for sports players. Far, far more spectators derive entertainment per individual basketball player than children can be effectively taught by a normal human teacher.

What I wondered then was if we treat the relatively few sports players as members of our larger community, as we automatically do teachers, and divide the aggregate amount they get paid by the size of the community.

To answer that I consulted USA Today's page on NBA salaries for the 2005-06 season. I could have added the table up manually, but instead spent a few minutes using a prerelease version of my company's software to scrape the web page, get the numbers, and add them up. I was glad I did this when I later realized that I wanted to re-do the calculation for a different season.

My computer-enabled calculations tally the total NBA salaries for 2005-2006 to be in excess of $1.6 billion. Whoa, that is certainly a big number.

But so is 300 million, a number which made the news yesterday as the current estimated population of the USA. I figure that means the entire NBA payroll for last year could have come by having each US resident contribute about $5.50.

In other words, you might say that economically, we value basketball players in this country to the tune of $5.50 a person.

You think we value teachers a little more than that? I think so. Remember our earlier estimate for supporting your own private school was in the thousands of dollars per family.

Picking a number from near the top of Google's search results for "total teacher salaries", I get an estimate of $140 billion spent on K-12 salaries in 2002-2003. Using an estimate of 280 million people in the US in 2002, that's an average contribution of $500/person nationwide to teacher salaries.

I reran the basketball analysis for 2002-2003, to compare on even basis with these education numbers, and found that the NBA salaries are actually right about the same. The population was lower in 2002, so we get an average contribution figure of $5.92 per person towards NBA salaries.

By that comparison, teachers were about 84 times more important, economically, to us than basketball players in 2002-03. You could add in football, baseball and other sports to even out the comparison. But I think this is a nice way to think about the comparison.

One way of understanding the difference is the scale of service provider to customer. A sports player reaches a large audience of paying customers while one teacher can handle only 20 or 30 students, which is more or less related to salary. But this ignores the question how much sports do we consume as a nation compared with the amount of education required? I think these figures of total expenditures, or dollars per US citizen, help to combine the answer to that question with the ratio of service provider to customer. While not everyone buys basketball tickets or merchandise or greatly influences basketball advertising budgets, closer to everyone, on average, requires the services of a teacher.

My conclusion is that I find that in 2002-2003, we spent 84 times more money on teacher's salaries than NBA player's salaries, and I think that's a pretty powerful argument that we value education more than basketball. An individual teacher makes less than an individual basketball player, but we already knew that due to the nature of teaching and classroom sizes versus the nature of spectator sport and the size of arenas and TV audiences. Teachers should still be paid more, but I hope this will reassure somebody that schooling is still ahead of hoops.

Monday, October 02, 2006

Buy that garage!

CNN reports today that Google has purchased the garage where the company got started. Google bought the property from one of its employees, Susan Wojcicki, the vice president of product management who originally rented the garage to cofounders Larry Page and Sergey Brin for five months to help her pay her California-sized mortgage.

The CNN report also includes this gem:

The busloads of people that show up to take pictures of the house and garage have become such an annoyance that Google asked The Associated Press not to publish the property's address, although it can easily be found on the Internet using the company's search engine.

I wonder how long it will take before someone uses Google's Sketchup to put a 3D model of the garage on Google Maps.

Tuesday, September 12, 2006

Programmatically asking Windows how much memory you've got

If you want to know how much memory is installed in a Windows box, you can open up Task Manager and inspect the Performance tab. But what if you want your program to know how much is installed? Chances are you know what your computer has, but your program running on someone else's computer may also care to know.

Since it took just a little bit of digging, I wanted to briefly mention how to find this. The short answer is to use the GlobalMemoryStatus function.

This helpful tip is from the Win32::SystemInfo Perl module source code, the I'm Feeling Lucky link to the Google search "finding amount physical memory windows programmatically".

This is one of those things I want to put in the Software Provenance Database, a repository of information about how to find out things about your computing environment, both manually and programmatically.

Thursday, August 31, 2006

Web Security as it Really Is

I've been reading "Web Security: A Matter of Trust", the Summer 1997 issue of O'Reilly's "World Wide Web Journal". Wanting to understand the magic behind https: a little more, I read "Cryptography and the Web" by Simson Garfinkel and Gene Spafford, and "Introducing SSL and Certificates Using SSLeay" by Frederick J. Hirsch.

My knowledge of SSL and web security could be told like this. Surf to the front page of a site you use securely, You fill out your username and correct password, click "Login" (or hit tab-space, if you're a mouse avoider like me), and voila, you're securely surfing the space.

Meanwhile, my wife and I have been looking to buy a car, and I noticed something interesting about a popular car research website. I was logged in and happily doing my research, and happened to glance up at the URL. It started with "http:". With Ethereal, the free network sniffer, capturing packets, I re-accessed the front login page and examined the output. Sure enough, there was my email address, which the site uses for usernames, and my password, in very clear Courier New text. In crafting an email to their customer service, I came up with the following list of pros and cons for not using https: on this particular site:

  1. Pro: An attacker who captures your credentials and logs in can't really do much that reflects badly on you. They can do car research, and I guess they can send nasty email to customer service. The site actually does use SSL when you originally order the service and use your credit card.

  2. Pro: For such a popular site, maybe the server overhead of using https: on all the information queries is too burdensome

  3. Con: Since the usernames are email addresses, they can be collected and sold

  4. Con: Some people use the same password everywhere, so it still compromises a user's privacy and security to send it in the clear. Knowing one password may help gain entry elsewhere, especially when a username in other systems can be guessed from the email address used on the car site

This experience wasn't so bad. Plus, I like to be trusting, it wears me out to be suspicious of everyone and everything.

Then my heart skipped a beat when I noticed the same phenomenon happening with Google Mail. My wife had mentioned that she thought Gmail has an http: address after you log in, but I didn't think it possible (my faith in Google at work). But when I checked, she was right.

Ethereal was quickly called to the scene. I was horrified as the sniffer trace revealed email addresses of my quick contacts appear in clear text. But that ended up being all I found. The sniffer trace was loaded with SSL and TLS traffic. Google's extensive AJAX programming is apparently moving the sensitive pieces, such as credentials and mail content, via Javascript calls to https: addresses while keeping the main page framing the content as quickly-served static clear http.

A nice design, very economical, securing only what needs to be. Indeed, why waste Google server time encrypting who-knows how many copies of the same Gmail page with unique keys? Still, it seems to be moving in the wrong direction when a user needs a network sniffer, or an HTML/Javascript code inspection to find out what is secured and what's not. Remember, Google is not securing a list of email addresses found in my contacts list. I wonder if that's how my Gmail address finally got compromised to the spammers?

Tuesday, August 15, 2006

Kingdom of Nouns Response #1

My good friend recently mentioned the Kingdom of Nouns essay, hereafter referred to as KofN, which sparked a flurry of discussion back in March 2006.

Being both a Java programmer and a functional language programmer (I liked to tell people I wrote more lines in Standard ML during college than in any other language), I found the essay provocative and interesting. Rather than responding in kind to Steve Yegge's 3,164 word essay, I've decided to post little thoughts, this being the first.

My overall response to KofN is that Steve is right, Java is lacking in the way it works with functions, but his reasons are wrong, and the remedies he gives are not quite the remedies needed.

Nouns, Verbs, and Computation

Let's talk about where the nouns and verbs come from, first. After all this is programming we're talking about, and not linguistics. While linguistics, the study of human languages, often has compelling ideas that can be applied to computer languages, the terms noun and verb in KofN come from design analysis. When designing a new system you break down your problem domain by thinking of its nouns, and make them correspond to data, and then the verbs which become functions or code. Simple, nouns=data, verbs=code.

The basic statement from KofN I want to examine now is this one:

Nouns are things, and where would we be without things? But they're just things, that's all: the means to an end, or the ends themselves, or precious possessions, or names for the objects we observe around us. There's a building. Here's a rock. Any child can point out the nouns. It's the changes happening to those nouns that make them interesting.

I really struggle to find the point of this paragraph, the "topic sentence" as the writing teachers say. It has plenty of insinuations, like "any child can point out the nouns", which help build the emotional impact. But I think the point is that nouns are not interesting by themselves, and that they're the means to an end. Very well, if that's the point, then let me respond by invoking the simplest description of computation as

  1. Receive input

  2. Do some calculation on the input

  3. Emit some output

This doesn't say anything about functional vs. procedural, about programming language, this is how computers work. At every clock cycle (or for analog computers at every instant in time) the computer is the embodiment of a function, turning inputs into outputs. If it's a desktop or server, maybe it's sitting in an idle loop waiting for input. What people care about, the whole reason the computer is there, is the output, or information.

But KofN states "nouns are a means to an end", but I think it's the other way around. The end of a computation is the output, and the means is the function. If the point in bringing this up is to promote verbs in relation to nouns, I think the case is overstated.

In light of the above model of computation, I think the programmer's job can be phrased as modeling real-world nouns as computer data structures, and implementing the functions, the verbs, that transform those data structures. Both are important, of course. But I don't think nouns are uninteresting to the end user, and I don't think the "end" of a computation is the code, except maybe for the computer itself, if it subscribes to the life-is-a-journey-not-a-destination philosophy.

The question at hand in all this is how a programming language should be designed to help programmers get things done. The point of KofN seems to be to call for the option of invoking functions as f(x,y) rather than forcing f to be "owned" by the noun x, as in x.f(y). There's certainly a strong precedent for invoking functions as f(x,y). The static methods in java.lang.Math bear testament to that.

With that thought I leave you til next time.

Contract Violation in Tomcat or "Hey, I was still using that!"

This is a bug story. I don't have all the detail yet. But I know what I saw.

If you're really impatient, you can skip to the end ("Light Dawns").

Scene of the Crime

Picture a Java Server Page (JSP) which runs some code to check the server to see if some heavy computing job is done yet. If it is, the HTML page returned will immediately redirect to a page showing the results of the job. Otherwise the page will wait a few seconds and refresh. A polling loop.

The JSP takes two parameters, a job identifier and a status string, like this:

Now assuming that the job will take a long time, what would you expect to see on your browser? Probably not this sequence:

Fetch #1 of

Waiting on job 28.
Searching for ETs...

and three seconds later, Fetch #2 of

Waiting on job 28.
Searching for ETs...

and three seconds later, Fetch #3 of

Waiting on job null.

A program with certain inputs that produced one output the first two times it was invoked, and then a different output. Either my senses deceived me, the program had changed for some mysterious reason, or there were more inputs involved than I had in mind.

An Investigation is Opened

In trying to debug this, I found that while the HttpServletRequest's getParameter method was returning null, the getQueryString showed the right stuff, "jobid=28&whatsup=Searching%20for%20ETs...". I searched the web, and found there are categories of problems in Java servlet land where by forwarding and redirecting and various contortions you can end up losing your query string. But still, why should the result change after it was just working seconds earlier?

The Plot Thickens

The above simulated screenshots are not what I saw originally. In my JSP I had a null check, and redirected to an error page in that case. This stopped the looping. But when I removed the null check and let the polling loop continue, I found that the null condition went away. In other words, on one request the query string had the right stuff, but the request parameter map was empty. On the next request, the request parameter map was populated again.

A Correlation

This waiting page is what gets returned by a request to initiate the heavy duty compute job. What I was trying to do was emulate a common metaphor where the user makes a request of the server which will take some time to process, and a "waiting" page gets immediately returned. I decided to run Tomcat in the debugger and step through this initial request, where the waiting page URL got formulated and all that. Let's see roughly what that code looked like:

void handleSetiSearch(HttpServletRequest request, HttpServletResponse response)
String id = allocateJobId();
String waitingPage = "poller.jsp?jobid"+id

// Start heavy computing job in another thread
SearchParameters params = getSearchParameters(request);
TimerTask performSetiSearch = new SetiSearch(params,request);
Timer timer = allocateTimer();
timer.schedule(performSetiSearch, 0);

This is the method that is invoked from the servlet's doGet or doPost methods, and handles the web request. Unimportant details have been reduced to a method call above.

I put a breakpoint here and in the SetiSearch code (not the real code I was using, if you've been wondering). After the above shown method returned, so that the browser got its poller.jsp page, but with the debugger stopped at the beginning of the SetiSearch code, the browser would loop the poller page for a long time without mishap.

Only when I started stepping through the compute job code did the poller page suddenly get a null parameter.

You now have all the clues, Sherlock. If you're a Tomcat developer or a very experienced Java webapp developer, you're probably screaming the answer. But let everybody else think for a few moments to see if they can spot the error.

Light Dawns

The insight is in noticing that while the web request is handled when the handleSetiSearch method returns, the SetiSearch object running in a separate thread after the request is handled still has the request object in its hot little hands.

And guess what? Tomcat recycles HttpServletRequest objects.

As this forum discussion shows, back in Tomcat 3 they were finding a significant performance boost by recycling request and response objects, instead of always allocating and garbage collecting them.

My suspicions were confirmed when I started printing the request objects and noticed that the same request object used to handle the original "SETI search" request had been recycled into the poller.jsp request.

So, although I can't explain why I saw what I saw, I know that when I extracted, copied, cloned, and otherwise slurped all the information out of the request object that the big compute job required, and did not pass on the request object itself, all my troubles went away.


Whose mistake is this? Mine, of course. But it's a gray line. I'm sure the contract of "don't use a request or response object after the request is handled" is stated in some documentation somewhere. I just hope they add the line "Even if you're still post-processing the request."

So, even though Java has automatic garbage collection, this experience teaches me that memory management by the program can still be done.

Afterword: Functional languages

Could this have happened if I was writing in a functional language? Not nearly as likely, if requests are represented in a "usual" way of data constructed on the fly, and state updates modeled by creating new copies. The performance issue solved by Tomcat's management of its own memory would fall to the language implementation. For example, consider this SML snippet:

(* Sets a request attribute and forwards to a display JSP *)
fun valueAdd(request as HttpRequest{params=p,attrs=a},response) =
val newValue = database.getValue()
val request2 = HttpRequest{params=p, attrs=Hash.set(a,"value",newValue)}

The memory requirements are (1) the creation of a new HttpRequest record and depending on the hash implementation, (2) a new hash table with an additional value. This even though request and request2 probably share the same params value. Depending on analysis of the call chain, the system could possibly decide that request is never used by any valueAdd caller, and could perform an update in place of the original request object to create request2. But I'm not up on functional language implementations to know if such things are being done. Chez Scheme has a lot of performance enhancement built in. Does anybody know how Ruby would fare in a situation like this? Is there any language out there that would be up to the task of recycling very frequently allocated data as needed for web server request and response objects that would not try to reclaim an object in use after the immediate request was handled?

Monday, August 14, 2006

Paper and pen considered important personal coding tools

When I'm writing code, I like to keep a pen and paper handy. I find that by writing down the types of a function, or the fragment of code I'm thinking about, it somehow helps me get to the point where I'm ready to type in the code editor.

Today for example, I was contemplating some refactoring and found myself sketching a call tree, to confirm my plan would work. In my notes I also see a space where I've done some brainstorming, writing four possible names for a new class I wanted to write. There's also a spot where I jotted down the six related actions that my servlet handles which I was about to change, to help me make sure I methodically covered all of them at each stage.

Does anyone else work this way? I don't think I used to do it like that. I think it came about after grinding through my master's work where I was writing a 10,000+ line SML program and frequently needed to write down the types of functions I was planning to write.

Tuesday, July 18, 2006

Alphonse Bertillon and 19th Century Databases

Earlier I described an idea that I called the Software Provenance Database. The essence of the idea is a database of information on how to tell what version of a piece of software you're using.

I didn't like the name though, and remembered reading about Alphonse Bertillon, a French police employee who in 1882 presented "anthropometry", a technique of identifying a person based on body measurements and other observations of unchanging features such as scars.

Hence I'd like to consider using Messr. Bertillon's name or story for this database.

Further, I wanted to add that this database certainly should not be limited to determining versions of an executable. The idea is to gather in one spot any information about how you can dynamically determine the state of your computer, and this can include configuration information (how much memory is installed?) and data schemas or file formats.

If you have a few moments, it would be interesting to read this account of how Bertillon's method works, and to think about a database search which involves no computational machinery. Notice his method for partitioning the records into equal portions, for example to make the search quicker. It is to me a good example of what I think Dijkstra meant when he said "Computer Science is no more about computers than astronomy is about telescopes."

Monday, July 17, 2006

Rantlet: Look who (or what) knows so much

My CD is dirty or damaged. I knew this already. My computer knows it too:

Windows Media Player cannot play the CD. The disc might be dirty or damaged. Turn on error correction, and then try again. [Close] [More information]

So it knows the problem. I'm impressed. But I don't know how to turn on error correction. Why doesn't it do something about it? Why isn't there a button labelled "So turn on error correction already!"? I don't want to get my hopes up here, but maybe they could even just turn on error correction for me, if they think that might help.

OK, I'm calming down. I had popped in a familiar CD to help me focus, and now I'm having to write to get out my frustration. If you click "More information", it does at least tell you how to turn on error correction. And the error correction, as they tell you, doesn't always work and might cause your CD to skip when it wasn't skipping before. OK, so there's a legitimate choice involved that is best left to the user. And I'll allow that this dialog may be fitting into a standardized error dialog which always has those two buttons, "Close" and "More information". OK, no more to say. Just a vague, undefined dissatisfaction that will probably induce me to try something different if it comes along.

Friday, July 14, 2006

False friends and Picasa web movies

Yesterday I tried out Python for real, applied to a problem I have with Picasa's web page generator.

What problem? For movie files, Picasa generates an embedded Windows Media Player control that does nothing. This is easily fixed by substituting this simple embed link:

<embed src="movie-filename" width="320" height="256" />

It was an interesting, refreshing experience to write in a new language, bringing to it expectations and baggage from Perl, Scheme, ML, and Mathematica. It was a process of "how do I read command line argument?", "now how do open a file?", and "what about creating an empty list?" I could bring my assumptions about the language semantics and capabilities and ask "how do I..." over and over.

A little like learning one Romance language after knowing two or three others, yes?

I spent most of my time consulting the Quick Reference and occasionally to the full Library Reference, with a boost from Introduction to Python/Hello World! to get started.

The things that gave me the most frustration in writing my 89 line script were definitely novice mistakes. If your critical attention is on a piece of code and you say "hey, that's not right!" it's a step up from the novice who doesn't realize something is out of place.

Mistake #1: Using parens to surround list literals: list = (). Not sure where I picked this up. Just as in SML, my native language, Python lists are surrounded by square brackets: [], [1,2,3],["and","so","on"]. Parentheses surround tuples, which are fixed-length. Since Python uses dynamic types, I could write list = () and nothing bad ever happened to me until I tried to append something to it. The error message finally clued me in on what type my variable was.

Mistake #2: Using comma instead of colon in a slice. I had written an expression like line[i+1,j]. Again, not sure why my fingers glibly typed the comma. The error was TypeError: string indices must be integers. That communicated to me that a substring, which is what I meant, could only be done with literal integers, not with integer-valued expressions. Spent a bunch of time in the documentation for other ways to get a substring before figuring out I had a comma when I needed a colon: line[i+1:j]. I think a non-novice Python programmer would have spotted the mistake immediately.

I explained all this to my linguistically-minded wife, someone who actually does speak multiple languages, and she thought it sounded like I had made the "false friends" mistake. I used something with a meaning in one language, and instead of being gibberish in the current language meant something else. Something related enough to cause confusion for a while.

These trivial problems were fixed, and the script worked great.

Monday, July 10, 2006

Idea: Software Provenance Database

You know how Help -> About... tells you an application's version number? Wouldn't it be great if there was a similarly convenient way to find out, manually or programmatically, what version of something you've got whether it's an operating system, browser, virtual machine, or compiler? The idea here is a database of how-to-tell-what-it-is information. It would store ways for determining version info manually and also programatically, in as many different languages and environments as possible. For example, on a Mac you can get the OS name and version from a file. This works for both manual and programmatic access in almost any language. In Java you can also call System.getProperty("") and get the OS name (not sure about the version number though). There can be both algorithmic and heuristic ways of determining the version of something. For example of a heuristic how-to-tell, I've heard that some machines and TCP/IP stacks can be identified by examining their output with a network sniffer. These are the kinds of things that would be useful to have cataloged somewhere.

Now somebody just needs to find or create such a database.

I did find something called "bitprints" which a collection of identifying information, such as hash values, for file images. This is certainly one way to identify a piece of software, by characteristics of its bit content, e.g. 1 million bytes long with an MD5 hash value of such-and-such. But I'd want a software provenance database to record as many ways to identify it as possible.

Hopefully later I'll post a mockup of a domain model for such a database.

If you have refinements on this idea, or know of places that realize all or part of this idea, please leave a comment.

Friday, July 07, 2006

Spell checkers for language processors

I've been finding the spell checking feature of Mathematica surprisingly helpful at identifying typos in variable names. It makes me wonder why more language processors (compilers and interpreters) don't make use of this.

The feature works like this. Each new identifier reference is checked for similarity to an already known symbol. If it is similar but not the same, a warning is generated, as follows:

In[1] := rootDir = "/tmp/foo";
setup = rootdir <> "/index.html"

General::spell1 :
Possible spelling error: new symbol name "rootdir" is
similar to existing symbol "rootDir".

(For more info see the documentation for General::spell1 and its examples).

The rootdir is flagged as similar to rootDir. In Mathematica this is important because variables don't need to be declared before use, which makes sense for supporting symbolic algebra. In a language like Java where variables must be declared, the compiler would catch rootdir as undeclared, but would leave it to you to figure out why. With a spellchecker to catch the similarity you could get a possibly helpful hint.

The chief drawback I see is the noise you get from false positives, when the spell checker finds a similarity between a symbol you just wrote with an existing symbol, and you know full well that they're different and it's OK. It's a little like the Dick Van Dyke show exchange when Laura asks Rob "Do you or do you not like reminders?" and Rob replies "Only when I forget." Mathematica let you disable the spell check feature, so you don't see the warning every time you load a bit of code with a spelling similarity.

It would be cool to combine this spellchecking feature with the "Quick fix" feature in Eclipse. You make a typo in a variable name, it gets a compile error perhaps because it's not declared in its current form, and the compiler additionally warns "similar to symbol X". The quick fix would be "change to X".

Friday, June 30, 2006

MySql 5: Error No. 1045 Access denied for user 'root'@'localhost' (using password: NO)

I have been driven crazy by this issue, trying to get a MySQL 5.0.21 database created from the wizard in WinXP.

The error message was this:
#1045 - Access denied for user 'root'@'localhost' (using password: NO)

It also talks about making sure port 3306 can be opened. In one of my installations, I was using Norton Firewall and I did have to open up port 3306, but I also had this error on a machine without a software firewall and that was not the issue.

The core problem seems to be that even though you supply a root password, it does not get applied. Does this happen for everyone? I don't know. But the "using password: NO" for me suggests this is what was happening.

Solution #1

The solution in that case is to ignore the error about applying security details, log in with an empty string root password, and change the password. MySql bug#6891 tracks this for version 4.1.7. The workaround given there is this (credit Freek Bos):

So when you start the MySQL command line client.
You simply press ENTER when asked for a password.

Now you can change the password by running the following line.
SET PASSWORD FOR 'root'@'localhost' = PASSWORD('MyNewPassword');

Solution #2

I didn't try this route. The solution that worked for me was

1. Uninstall MySQL
2. Erase the MySQL installation directory, as the old database files are left around.
3. Install MySQL.
4. Choose "Standard Configuration" rather than Detailed.

Somebody had suggested (sorry, I've lost the link now) that there was a problem when using the "Detailed" configuration to create your database initially. They said to choose "Standard" initially to create it and then go back and reconfigure it as desired with the Server Instance Config Wizard. I wonder if the Detailed configuration wizard path has the problem of not applying the given password? If I get a chance I'll try these two options in a clean system and update this post if I confirm anything.

Some people run the Server Instance Config Wizard after getting this error once and find that it now can no longer start the service. This happens if the service was actually started the first time. But don't go this route! Re-running the wizard won't solve the password problem. Follow one of the two steps given here instead.

If this was helpful to you, or you have a correction, leave a comment and let me know! It looks like this is a very common error.

Thursday, June 29, 2006

Universally useful feature: go to last edit point

The Eclipse editor has a feature, activated by Ctrl-Q, of taking your cursor back to the point in your document where you last made an edit. I find this extremely useful, and started to wonder why I haven't seen it in other editors.

Regardless, I have to file this feature away under the category of "user interface best practices", along with filename completion.

Wednesday, June 28, 2006

What is a bug?

A nonprogrammer friend asked me "What causes bugs?"

My answer at the time was that they take many forms, and one form is that a program is used in a way that was not anticipated when the program was written.

For example, you write instructions for a blindfolded person seated at a desk how to get up from the desk and leave the office. The instructions work great in the office environment they were written for, but try to apply them to a different office, or even the same office after it's been "reconfigured", and your program might literally send someone running off into the weeds or stepping into an open elevator shaft.

Certainly a bug is some kind of disconnect between expected and actual behavior, so you'd have to talk about requirements. But the more interesting question is how the bug gets introduced -- how the programmer can think the job is done when it's not, and put it into a simple "cocktail party explanation" (as my econ professor used to say).

So, what's your cocktail party answer to "what causes bugs?"

Tuesday, June 27, 2006

Followup: Checking for a process running

After some very helpful feedback and further work on my own, I'd like to post an improvement to the previous entry "Checking for a process running".

The idea is to get a list of PIDs of an executable Xyz, or other string of interest, suitable for passing to xargs kill.

First, the code.

# Try to guess which ps command we have, ps -f or ps uxww
# Some ps programs accept both uxww and -f, but we prefer uxww.
if ps uxww > /dev/null 2>&1 ; then
ps -u $USER $PSOPTS | grep [X]yz | awk '{print $2}'

Now, the explanations. Except for #1, these suggestions are from Todd Eigenschink.

1. It's a script, not a one-liner. In my environment I needed to use the command on multiple platforms, and there are two different versions of the ps command on the different platforms. So a script is needed to detect which one is used so the right arguments can be passed. If you know which ps form you need, you can reduce this to a one-liner and perhaps make it an alias.

2. The -u option is supported by both flavors of ps and eliminates a separate grep call to filter out my processes. Actually, even the -u is probably unnecessary as I think ps emits only your own processes by default.

3. The [X]yz pattern is a sneaky way to eliminate the need for a separate grep to filter out the grep process itself. The pattern [X]yz matches Xyz, but now the grep process won't have Xyz in its ps entry, and thus won't include its own process in the output.

4. The awk fragment to extract the PID field from the ps output eliminates the need for the sed and cut commands I posted earlier.

Friday, June 23, 2006

Yacking about a multi-language parser generator

If you've ever written even a toy-sized compiler or interpreter, the parser is one of the first things that slows you down. You have an implementation language in mind, and you cast about for the parser generator. Maybe you're old-school with C/Lex/Yacc, maybe it's Java/JavaCC, or maybe a less mainstream pair like SML/SMLYacc. Maybe you go the route of the self-written recursive descent parser and forego a parser generator. But this choice is a bit like choosing a bank for a CD, because once you have the parser written, you get substantial penalties for early withdrawal from the language and parser implementation choice.

Enter GOLD, a multi-language parser. The concept is dirt simple: generate the DFA state tables and the LR parse table as text-formatted data, and take your lexer and parse tables to any language that has the parsing engine. Even if an engine is not available for your platform, it is not hard to write that part which accepts tokens and consults the parse tables.

The key to this is in questioning the approach of most parser generator systems which put the parsing rules in line with the code that builds the abstract syntax tree. Of course by providing a scheme for building the AST, you've tied yourself to a particular language.


By extracting the parse table data to a portable file, GOLD has opened up two different avenues of reuse:

1. GOLD parse tables can be executed in a large number of languages.

Right now, the GOLD page lists at least 7 different languages you can write your interpreter/compiler in while using a GOLD-generated parse table, including C, C++, C#, Java, and Python.

You've already written an interpreter in Java/JavaCC and want to switch to C++? Now you can switch without having to learn Lex/Yacc.

2. Because of the language portability, parsers can be shared more easily

If somebody has already written a Ruby parser or an SQL parser for sharing, you're now probably more willing to pick up the GOLD input and compiled grammar table, because you're free to drop it into the language of your choice. The GOLD site makes available grammars for about 14 major languages including C, LISP, Pascal, Smalltalk IV, and SQL 89.

GOLD as it is now

After all this talk about portability, the bad news is that the current GOLD parser builder is a closed-source Windows-only GUI application. Ouch. While obviously not a theoretical limitation, it's a practical barrier to entry for plenty of would-be adopters who may work only a Unix box or who don't want to run a Windows executable of unknown origin. The builder looks like an IDE, and one possible portable solution would be an Eclipse plug-in. There is also a command-line version of the builder, but for some reason it is also Windows-only at present.

The good news is that the builder looks fairly good. You can regression test your grammar and get fairly good visual feedback on your state tables.


GOLD looks like a great idea in a still-maturing incarnation. I like how it's taken the table-driven notion of parsing one step further. With more community support to make a portable builder to complement the portable tables and engines, I think this tool or something like it will be standard in the years to come.

Monday, June 19, 2006

Classpath not working in Ant junit task

Pop quiz: spot the error in the following Ant fragment:

<path id="common.classpath">
<!-- some classpath content -->

<path id="common.test.classpath">
<path refid="common.classpath"/>
<pathelement location="${basedir}/lib/junit.jar"/>
<pathelement location="${basedir}/build/common/test/bin"/>

<target name="test" depends="compile-tests"
<junit fork="yes" forkmode="once" printsummary="on">
<path refid="${common.test.classpath}"/>

<formatter type="plain" />

<fileset dir="common/test/java" includes="**/*.java"/>

You may not even need to know ant syntax to spot the error, since it's an internal inconsistency.

The clue is that you get "class not found" errors for all tests when you run the "test" target.

Give up?

The nested classpath element for "test" is not referring to an existing path ID. I confused an Ant property with an Ant ID. It should say

<path refid="common.test.classpath"/>

without the ${} wrappers that are used to refer to Ant properties. There's a correct path reference in the test classpath definition itself.

Friday, June 16, 2006

Checking for a process running

Recently I've been wanting to know "is process X running? If so what PID or PIDs is it running under?". Running ps piped through grep X is the usual thing. But I got really tired of staring at the extra cruft coming out of ps. I wanted to just see process IDs. So I added some extra filters:

ps auxww | grep $USER | grep X | grep -v grep | sed 's/[[:space:]][[:space:]]*/ /g' | cut -d" " -f2

This returns the PIDs for processes $USER owns with "X" in the ps output. I generally inspect the list and if needed re-run it piped to xargs kill -9:

previous-command-line | xargs kill -9

This works as-is under Linux and places where "ps" supports the "auxww" form which includes the full command line for a process. If probably works as well with the "ps -ef" variant of ps.

The extra parts of the query may deserve some explanation.

| grep $USER

Filters out processes by $USER (me).

| grep X

The critical part for filtering the process by command name or other string of interest.

| grep -v grep

My favorite first optimization: exclude this grep command, I know I don't care about it! Bad of course if X is a string with "grep" in it, or if your username is grep.

| sed 's/[[:space:]][[:space:]]*/ /g'

This sed command is in preparation for the cut about to take place. It replaces sequences of whitespace with a single space, so that space can be used as a delimiter in the cut command. If you know how to make sed understand [[:space:]]+, let me know.

| cut -d" " -f2

This extracts the second "field" of each line treated space as the field delimiter.

That's it. If you know of a decent one-liner in Python or Perl or something else, let me know.

Tuesday, June 13, 2006

Passing system properties from Ant's command line to java or junit

The other day I wanted to do something like this, and have the property passed to a junit task:

% ant -Dcom.blogspot.jfkbits.tmpfile=/tmp/grzlgmpfer-78

My task never saw the property; Ant doesn't automatically pass-through properties. That's fine, it just surprised me, coming from the shell environment variable mindset.

It turns out that sysproperty, syspropertyset, and jvmarg are the only ways to do it.

The jvmarg nested element is the simplest form, as in the example from the Ant documentation:

<jvmarg value="-Djava.compiler=NONE"/>

If you have a lot of properties this gets tedious.

If the properties you want to pass have a common prefix, as in the example com.blogspot.jfkbits, you can use syspropertyset with the prefix attribute, like this:

<classpath refid="classpath"/>
<propertyref prefix="com.blogspot.jfkbits" />

<!-- tests go here -->

Update 17 July 2006:Added text for jvmarg, since that is a way to pass system properties that I previously omitted, and tweaked the description of how to use syspropertyset.

Monday, June 12, 2006

Softcivil engineering

In his recent essay "Make Vendors Liable for Bugs", Bruce Schneier argues for software liabilities to help increase computer security by aligning the industry's capability for improving security with an interest in doing so. That is, the industry lacks a compelling interest to improve security, but it has the capability to improve, so let's make them interested by holding them liable for security issues. I'd like to apply this argument to the tension between software quality and time-to-market. To help gain insights we'll compare software development with other technical fields.

"Towers are popular in Japan: You ride to the top, look down at the city far below you, wonder if the tower is constructed according to sound engineering principles, then ride the elevator back down as soon as possible. That's what I do, anyway." -- Dave Barry, Dave Barry Does Japan

Civil engineering projects, as in Dave Barry's example, often have a public safety aspect that many software projects don't evidence. Some software is of course used in ways that obviously require a high degree of quality and it is engineered well: flight control software, medical diagnostic equipment, and public safety communications equipment. But a lot of software, and I think particularly of web commerce, has a lot of public trust bound up in it, with a marked lack of quality.

What if civil engineering were as easy to do as software? What if an engineer could sit down at his workstation, bang out an XML document describing a hierarchy of bridge members, hit a key, and suddenly a bridge is constructed over the nearby test river? The engineer and twenty of his testing friends drive freight trucks over it, iron out some vibration problems, and their manager says "ship it." Even with more extensive testing, that quick turnaround from a conceptual design to reality would say "book the customers now! more testing just increases cost and drives profits down!" a lot louder than "but it might not work all the time in the next 50 years when it will be used."

Public safety concerns aside, one reason civil engineering isn't done this way is the cost of construction. There's no "XmlToBridge" converter. That, and no chance for a version 2.0, a chance to build a basic bridge and then replace it with a refined bridge with more features in a year or two. Knowing this up front helps everyone involved in the design phase accept that the design phase is critical. The construction cost also gives a quantitative guide or bound on how long is acceptable for the design phase.

In software, the cost of production is the cost of the build process, which could be a few hours for a large product, or in the case of a hosted web application written in an interpreted language, perhaps virtually nothing. This low cost of production and copying is part of what makes software, and computers in general, practical and useful. And cheap, compared with any kind of "hardware" alternative. But if we're trying to align capability for good quality with interest in good quality, the cost of production is working against us.

Hence my claim is that one of software's key advantages, rapid change, is one of the reasons software quality is poor. It lowers the apparent cost of production to a point where it's no longer a barrier that motivates you to double-check your work. Internally a software team can recognize this and take action. Maybe we need to revert to punch-card programming. Rather than trending towards continuous integration (an automated edit-compile-test system), maybe we need a mandatory waiting period between design and coding. I'm not sure what would be effective. But any proposal you come up with to increase quality by investing more time is going directly to the bottom line of software vendors by increasing that production cost. That's why if we want higher quality, we've got to quantify the costs of lower quality, and transfer some of those costs to the software vendors to make it easier for them to decide that quality is worth it.

Wednesday, June 07, 2006

Brought to you by the letter "J"

Java has been a great boon to the popularity of the letter "J". Today I noticed a new angle on this.

In Firefox, I keep a "Reference" folder in my Bookmarks toolbar (see picture). When I added a Python link recently, I was struck by how "early" in the alphabet "P" was to be the last entry in the list. I did a double-take on what was in my list.

It's a small list, not a good sample size to draw conclusion from. Still it's funny that 8 of the 19 entries start with "J".

A quick survey of hits from Google of "english initial letter frequency" suggests that the most common letters starting English words are T,O,A,W,B,C,D,S,F,M, and R (different pages give different lists). The letter J is of course always near the bottom.

It would be interesting to see an analysis of initial letter frequency in technology names and see if there are other deviances from the standard English distribution.

Monday, June 05, 2006

Ant, the Portable Shell

Today I was considering whether to include Ant in a Java webapp, not because I wanted to run builds inside my web server, but because I wanted Ant's portable tasks like copy and replace. The Ant welcome page says this about itself:

Make-like tools are inherently shell-based -- they evaluate a set of dependencies, then execute commands not unlike what you would issue in a shell...Ant is different. Instead of a model where it is extended with shell-based commands, Ant is extended using Java classes.

Actually, it seems to me Ant hasn't gotten us away from the shell, it's provided us a new shell with portable commands. Granted there are more commands one could want but I'm pretty happy with what we've got.

Come to think of it, generating Java source and compiling it inside a webapp might be kind of interesting...

Saturday, June 03, 2006

Language-Driven Applications and the Command Pattern

When you go to write your next great application, consider imitating the work of CPU architects, where you design an Instruction Set Architecture (ISA) and programmer's register model. It would look something like this. Your application state needs to be clearly modeled, akin to the register and memory model of a CPU. Then the application operations would be distilled to a collection of commands, like machine instruction opcodes, which transform the data state. Then you provide a text interface to that command interface, like an assembly language. With this investment, consider where you'd be. First, by focusing on the application core and providing a clearly-defined way to manipulate its state, you get encapsulation from your user interface. Then, especially with the language interface, you allow extension of your application programmatically, third parties can script extensions in ways you never could have anticipated. And finally you can more easily employ the command pattern in your user interface or supporting environment to achieve features like undo/redo and macro record/playback. Do the hard work to make your application language-based, employ the command pattern, and I think you're digging a very solid foundation for a powerful application.

This language-based application is adopted by two notable applications, Emacs and Maya. Emacs, the text editor that doubles as a programming environment and mail reader, is based on Emacs Lisp, and the user interface is built around that language. Any user interface action, up to and including moving the cursor one character left or right, can be repeated by invoking the right procedure in the command window. Maya is the powerful 3D animation package that made the Lord of the Rings movie magic happen. Maya has a stunning user interface, beautiful in the way it makes users productive in an extremely complex environment. However, that interface is on top of MEL, the Maya Embedded Language, which the Lord of the Rings production team used to script "an enormous scene management system".

One benefit of the language based application is of course encapsulation. I suspect a large number of applications have major problems porting to new platforms because the application core and the user interface are too intimately tied. Mathematica, which actually is a programming language application, also happens to have an interesting and useful user interface, which handles things like typesetting and graph plotting. It goes to the extreme in encapsulation, where the user interface and command processor are actually separate processes. The command processor, or kernel, can run standalone and provides a simple text interface. There is in fact an entire transaction language (part of MathLink), for the read-eval-print loop interaction between the kernel and "the front end". It's an open standard, allowing potentially any number of completely different front ends to be built both proprietary and by third parties.

Another benefit of the language based application is future extension. Although there is the possibility of direct support for writing new commands in the language itself, exposing your application's core engine as accessible with a text-based script of commands allows people to write programs in their language of choice that generate "source code" for your application language. If you use Emacs you're probably familiar with the various modes that help you edit a particular file format or programming language, and many of these modes were not written by the same folks who wrote the Emacs core.

The command pattern opens up another handful of interesting features for your application. If your application core already has a suite of commands, they can easily be turned into function or command objects if they aren't already, each of which transforms the application from one state to another.

Probably one of the most useful features available with the command pattern is undo/redo. You keep a "command history" of the state transformations done in your application core. Undo takes the most recent entry from the command history, invokes the undo transformation, and places the entry onto the redo stack. Redo takes the most recent entry from the redo stack and invokes the original command that made the state transformation. The undo functionality may not come for free, but you may find that it's not that difficult and actually rounds out your command language. If you have an "add widget" command, you may not have noticed that your command language lacks the "remove widget" command until you need to support undo for "add widget." In other words, undo/redo commands may simply be pairs of complementary commands in your application language.

By persisting the command history entries to a file with atomic writes, you get a database-style log file. This permits you to recover from a process or machine crash, where you can start with whatever initial state is stored on disk, and replay the log to get back to the most recent log entry that made it to disk.

If you've already got a command history, you can give your application user "macros", in the style of Emacs, where the user designates points to start and stop recording user interface actions, and the resulting sequence of underlying commands can be replayed as an aggregate state transformation. It is in effect a user-defined program in your application's language. Many applications support some form of this feature, including the ability to edit the generated code after the fact.

By combining some of these notions, you get another wrinkle: incremental version control. If you're already keeping a persistent command history log, the user can specify a desired "save point" as the next version of the application state, complete with comments. Now you can provide a feature for a user to roll back to a previous application state, or even branch from a previously saved version into a new direction. This may suit your application well, if the sum of the log entries between two different versions is smaller than saving an extra complete copy of the application state, and undoing or replying those changes is not unduly time-intensive.

So, those are some thoughts I had about structuring applications. Make a clean internal design separated from the user interface and provide a text-based language interface to it.

Thursday, June 01, 2006

Idea: Google search annotations and Google Co-Op

I just had an idea, and searched looked up "Google search annotations" to find prior art. Lo and behold, the relatively new Google Co-Op has it. I can't tell if this idea is the same, or if it could be implemented with Co-op, so I'll introduce it and then discuss overlap.

The basis for the idea is the following observation: when reporting a computer problem that could remotely be considered to happen to someone else, the first thing people have been asking recently is "did you search google? what did you find?".

Based on that observation, I started to wonder what if you could take the Google search results, or at least the pages that you looked at, and edit them? You could annotate the links with comments like "this link had a good example". You could even "delete" links as irrelevant to your search, although I imagine if you gave it to someone else they'd want to look through your "recycle bin" of deleted links just in case. The edits could be done on Google's servers, or somehow you could own the data yourself --- write an application or browser plugin which would copy the downloaded search page, parse it, let you edit it, and then let you send around the annotated search results.

It looks like Google Co-Op could support something like that, because it supports adding labels and comments to search results. But it also looks like it's geared for public dissemination of the results and for the tagging to be done by experts. In what I'm picturing, you would encourage people inside your company or organization to do this, and you wouldn't necessarily want those search results to be public.

Thursday, May 25, 2006

Bright ideas

I'm really glad I have a light with a touch-sensitive switch. Last night I was holding my 2-month old daughter, who had just fallen asleep, and I wanted her to stay that way, so I went to turn off the light. With my hands full, I was able to slip out of my right house shoe and use my bare toe to turn off the light. It's irrelevant that she woke up just 20 minutes later, I was still happy about being able to turn off the light when I need to.

Saturday, May 20, 2006

Quine Dissected

A program that prints its own source code is one of the fun puzzles in computer science. I attempted this problem a couple years ago, and now I wanted to introspect a bit on the process that led me to a solution. Solutions for C++ and Standard ML are found at the end of the post.

A first attempt in some language would look something like this:


or rather it would start like this, because of course you get stuck. Your brain's Recursion Detector goes off, and you realize you just can't go on like this, into the infinite reflections of opposing mirrors, because you'll miss lunch, and your editor won't be able to hold it all anyway.

So we take a step back. We take stock of what we know:

1. The program has to start some way.
2. Similarly, the program has to end some way.
3. We assume that our technique will involve quoting something from our program. There may be quines that don't quote anything, but we'll try it.

Armed with these observations, let's go back to our program.


This looks good for the form of a program that is going to print something static (not based on any input). However, we already tried it, and ran into the recursion problem. But let's look at the program at or around the point things went wrong:


After this, our string starts recursing. You could perhaps say it starts recursing at the second Print, but that is the first time the program appears in a quoted string.

My thought was to put a variable marker ("S" for "self") in the quoted string to mark the recursion:


My idea was to write a function, let's call it f, which takes the string above and prints it contents, except when it hits the S. At that point don't print it but instead skip it and then print the remainder. Of course the function definition would need to precede the Print call, but as long as the function includes no quotes, it's static text and falls into Observation #1, the program must start some way.

I wrote a version like this, but then realized the marker was a little arbitrary, and that really you could simply split the program into two parts, the part before the recursion point, and the part after. Why not then make a function which takes two strings.

If our program had the form A"A","B"B, where A and B were arbitrary strings of source code which did not attempt to contain their own quoted source code, then we could write a function taking the strings A and B which would print this pattern: A+quote(A)+","+quote(B)+B. This function would then be printing the pattern of the source, without having to include the quoted form of the source itself. The function quote returns a quoted form of its argument string, using the type of quotation marks appropriate to the language, and including any escaping needed (e.g. if the given string includes quotation marks itself).

From here, we can deductively arrive at an actual implementation. We decompose A and B a little bit:

  • Apreamble: The code for f plus any setup or overhead needed at the beginning of a program in the language (e.g. #includes or Program SelfPrinter).

  • Bpostamble: Code to finish up the "main" part of the program and finish the program.

Hence A=[Apreamble]f(, and B=)[Bpostamble]. (If a function call looks different in the language, the f() syntax is easily changed.) Does this work? Does it solve the problem? Let's substitute these parts into the original form:

Original form:


Substitutions from A applied:


If Apreamble and Bpostamble don't include any "recursive strings", this will work. A full example will be a little difficult to read, due to the repetitions inherent in the pattern.

Enough symbolics, let's get to a real example, in Standard ML/New Jersey. The function f is given by this definition, with some supporting definitions:

val q="\""
fun quote s = concat[q,String.toString a,q]
fun f(a,b)=print(concat[a,quote a,",",quote b,b])

The code, with the string literals removed looks like this:

val q="\""
fun quote s = concat[q,String.toString s,q]
fun f(a,b)=print(concat[a,quote a,",",quote b,b])

Hopefully now you can see how A can be replaced by all the code leading up to, but not including, the quotation mark before A, and likewise B by the code after the quotation mark following B.

Finally then, here are full solutions following this pattern for SML and then C++.

SML Quine

val q="\""
fun quote s = concat[q,String.toString s,q]
fun f(a,b)=print(concat[a,quote a,",",quote b,b])
f("let\n val q=\"\\\"\"\n fun quote s = concat[q,String.toString s,q]\n fun f(a,b)=print(concat[a,quote a,\",\",quote b,b])\nin\n f(",")\nend\n")

C++ Quine

#include <iostream>
#include <string>
typedef std::string str;
str str2lit(str s)
str r;
for(str::iterator i=s.begin(); i != s.end(); ++i)
if(*i == '\n') r += "\\n";
else if(*i == '\\') r += "\\\\";
else if(*i == '\"') r += "\\\"";
else r += *i;
return r;
void p(str a,str b){ std::cout << a << str2lit(a) << "\",\"" << str2lit(b) << b; }
int main()
p("#include <iostream>\n#include <string>\ntypedef std::string str;\nstr str2lit(str s)\n{\n str r;\n for(str::iterator i=s.begin(); i != s.end(); ++i)\n if(*i == '\\n') r += \"\\\\n\";\n else if(*i == '\\\\') r += \"\\\\\\\\\";\n else if(*i == '\\\"') r += \"\\\\\\\"\";\n else r += *i;\n return r;\n}\nvoid p(str a,str b){ std::cout << a << str2lit(a) << \"\\\",\\\"\" << str2lit(b) << b; }\nint main()\n{\n p(\"","\");\n return 0;\n}\n");
return 0;

Tuesday, May 16, 2006

Java's unsigned bit shift right

Not having had the need for bit-twiddling in Java, I just now learned that Java has an "unsigned shift right" operator, >>>. The signed operator >> retains the sign bit (for turning -8 into -4, for example) and >>> shifts in a 0 to the most significant bit. This unsigned right shift operator has been part of the language since 1.0. I suppose the need for the two operators arises because all Java's integral types are signed, meant to support both signed and unsigned operations.

Friday, May 12, 2006

Functional languages in the real world

Once in the mid 1990's I was interviewing with a Fortune 500 company. "What's with all this functional programming experience?" I was asked. "What's the point? Are they really going anywhere?" Especially for this real-time embedded system company, functional programming sounded like a waste of time.

A lot of us who enjoy functional programming have wondered if it will catch on. My answer to that interviewer was that Java was catching on, and it featured garbage collection and allowed anonymous classes which can be used to imitate first-class functions. A little weak perhaps, but it did seem to make a point with him.

Then XSL/XSLT came along, and I was really happy, because here was something where you were supposed to think functionally, where you thought more about transformations and mappings than storage elements and order of evaluation.

And then recently, I finally stumbled across a truth which was out there but unknown to me: Javascript is functional. At least, it offers first-class functions, garbage collection, and lets you program in a functional style. The featured link shows how the author implemented a Lisp to Javascript translator in just a few hundred lines of Javascript, made easy in part because Javascript has anonymous functions to start with.

Then today I ran across this presentation, which shows how to do both functional and aspect-oriented programming in Javascript. The authors are behind Dojo, an open source Javascript toolkit for doing things like AJAX, eventing, and animations. I haven't examined the source for Dojo, but I presume that given the presentation, the Dojo system actually used the functional programming capabilities of Javascript.

The amazing thing is that Javascript had me fooled: in the words of one of Cryptopunk's commenters, "I thought JavaScript was just super-dumb Java". Lots of programmers and web developers use Javascript this way, tweaking HTML DOM elements, declaring variables without types, and generally writing like it was BASIC for the web. Now we find that the C-style syntax and Java-like supporting libraries were hiding our friend, the lambda.

Even neater, this blindness can go both ways. Developers who appreciate functional programming can take advantage of Javascript's functional features, perhaps incorporating Dojo to achieve some really high-quality web interfaces quickly and with some code they can possibly reuse at the end of the day. And nobody is going to ask them "what's the point". All the developer's manager probably knows is that the implementation language is Javascript, and who doesn't use that?

So have we arrived in a world where functional languages have a real-world need to justify their development and support? I think we're getting there. If you couldn't already get a job writing in OCaml for a New York securities firm or with a European firm coding in ERlang, you can almost certainly get a web monkey position hacking web pages in a functional style with the help of Dojo, and no one will know the difference.

Friday, April 28, 2006

A Night at the Opera -- They're Doing HTTP/1.1

It finally sunk in that Opera's text-to-speech feature might be useful. So I had it read some stuff to me. I listened to the news while browsing my code, but I couldn't concentrate on both. That's the trouble with not having enough mindless tasks.

Then I hit upon the perfect use. This is how I can actually get through all these RFCs I've been meaning to read. Browsing to those de-facto Internet specifications is like an insomnia cure to me lately. The sentences lull you, alternating between being impenetrably obtuse and stupifyingly obvious. But with Opera Man reading the HTTP/1.1 (he says "slash one point one" just like you'd expect) RFC while I study it, suddenly it's like I'm in a classroom. I take in the easy bits visually, and skip ahead to the hard ones, or study the diagrams. The steady voice of the reader sets a pace, helping me not to lose place if I skip ahead, or lag behind.

The text-to-speech technology is certainly adequate, and its accuracy in pronunciation, inflection, and intonation is quite good. Only once did I hear a slip-up, when "content negotiation" sounded like the negotiation was well-satisfied rather than negotiating about the innards of a resource.

So the next time you're having trouble getting through something, give the Opera reader a try. And if you need to fight insomnia, point Opera to Project Gutenberg and have it read a bedtime selection from Alice in Wonderland.

Wednesday, April 26, 2006

Chicken chicken; he declared

Give your variables meaningful names. That's Good Programming Practice. But what's "meaningful" is open to interpretation. Without "foreach", you can argue that "i" is as good as it gets in The C++ or Java array-like iteration idiom:

for(int i=0; i <> things.size(); ++i)

You can also argue that in simple mathematically-oriented functions, plain old "x" and "y" are about as meaningful as you can get:

boolean max(int x, int y)
return x > y? x : y;
A lot of the need for meaningful variable names arises for variables whose type is so common, like int or string or Object, that you need a good name to differentiate this XML attribute name string from that fully-qualified classname string we're using as a hash key.

This leads us to the gray area of variables meaning just one thing. I'm talking about variables whose type is unique in your context, there's only one database Connection object, only one Runtime, or one (shopping) Cart. In cases like these, there's a strong temptation to reuse the type name itself as the variable name:

Connection connection;
Runtime runtime;
Cart cart;
Type type;
Chicken chicken;
There's one great thing about this practice: naming is a no-brainer. A downside is the variable name is redundant, and it could carry more information.

How do you decide whether "Cart cart" or "Connection connection" is a sufficient name? This is where context comes in. If the whole purpose of a module is to take a Chicken and make Soup -- how much more information do I need to know about that Chicken? I can reasonably proceed to chicken.pluck() and all the rest, according to taste.

Perhaps then it is the variables in "supporting roles", those that exist from coding nuts-and-bolts necessity which need good names. Things like "int returnCode;" and "boolean success;" and that int returned by a substring find function could probably use better names.

P.S. Today's title is brought to you by the seminal work on Chicken.

Monday, April 24, 2006

Bug Story: When Is 9+1 not supposed to be 10

It was a simple mistake, but in an embedded system it was hard to debug and had mysterious effects. Our team had a limited region of RAM for each task to store its own copy of a fixed-sized chunk of data. (A "task" in our operating system, pSOS, is the same as a thread or process.) In a C header, we defined constants to use as the start of each tasks's fixed region of memory, something like this:


And so on. Things tooled along, we got the first features going, and quite a ways into the project we started seeing weird crashes and unexplained error conditions. We found that some of the tasks were writing past that limited region of RAM. But why? While it was limited, we had calculated it had room enough for twenty-some tasks, and we only had 18 or so in our application.

What went wrong? Well, imagine you are an engineer who has just finished some feature development, and for the next feature in the application needs to code up a new task (thread), let's say to process a new stream of input from a real-time source. One of the various things you need to do is edit that header we talked about, and add your task, let's say it's the Golf task:


Simple: it's a cut-and-paste job, you just change the name and the number of your task, so your pointer points to the next section in this self-constructed array.
Let's look at the next few entries in this progression:


and so on up to eighteen, which in this telling is the last task:


The keen-eyed C programmers among you will have seen the error. What we have here is the Sierra task addressing data that is actually 24 entries past the BASE pointer, not 18, because every one of those multipliers that a programmer had to edit has the "0x" hex prefix, that is the constant is in base 16, not base 10. So really those latter tasks were actually writing past their permitted region of memory, as if we really had 24 tasks in the system. It was a false lack of resources. We could have but didn't test for this at runtime, because we figured we had already accounted for it when we counted tasks and added up the memory.

It is interesting to see where the error crept it. The TASK_KILO_STATICS entry is most likely where things went awry, continuing the subtly wrong pattern of "8, 9, 10" when it should have been "8,9,A", or, "0x8, 0x9, 0xA".

How could this error have been prevented? Is writing our constants in hex not the best choice? What other code structures could have prevented this? The only reasonable alternative I can think of is the "previous+1" approach:


This eliminates the "9+1" problem, but did we introduce some other possible problem, like forgetting to link an entry to a previous entry, especially when rearranging the order of these entries?

If anyone can think of other ways to have avoided or tested for this problem (without resorting to another programming language), I especially invite your comments.

If you're interested in reading excerpts of other bug stories and a discussion of causal analyses, check out "My hairiest bug war stories" by Marc Eisenstadt. I like the way he refers to the "detective work" programmers do in debugging.