The July 08 (Vol. 30, #7) IEEE Transactions on Pattern Analysis and Machine Intelligence has an incredible paper by Raykar, Duraiswami, and Krishnapuram. A Fast Algorithm for Learning a Ranking Function from Large-Scale Data Sets appears to be a game-changer for an incredibly important problem in machine learning. Basically, they use a "fast multipole method" developed for computational physics to rapidly estimate (to arbitrary precision) the conjugate gradient of an error function. (In other words, they tweak the parameters and "get a little better" the next time through the training data.)

The precise calculation of the conjugate gradient is O(m^2). This estimation algorithm is O(m)! (That's an exclamation point, not a factorial!)

On a first reading, I don't grok how the crucial transform necessarily moves towards an error minimum, but the algorithm looks (surprisingly) easy to implement and their benchmark results are jaw-dropping. Of course, others will have to implement it and analyze it for applicability across different types of data sets, but this is one of the most impressive algorithmic claims I've seen in years.

Once upon a time, I had the great fortune to write a column for a magazine on artificial intelligence and could justify spending huge amounts of time implementing AI algorithms (well, I think I was paid $450 per month for my column, so I'm not really sure that "justified" 80 hours of programming, but I was young). Man, would I love to see how this algorithm works for training a neural network...

I recently wrote an encomium to ResolverOne, the IronPython-based spreadsheet:

[T]heir use of pair programming and test-driven development has delivered high productivity; of the 140,000 lines of code, 110,000 are tests....ResolverOne has been in development for roughly two years, is written in a language without explicit type declarations, and is on an implementation that itself is in active development. It’s been brought to beta in a credible (if not downright impressive) amount of time despite being developed by pairs of programmers writing far more lines of test than application. Yet no one can credibly dismiss the complexity of 30,000 lines of application logic or spreadsheet functionality, much less the truly innovative spreadsheet-program features.

ResolverOne is easily the most compelling data point I’ve heard for the practices of Extreme Programming.

[Extreme Program, SD Times]

Allen Holub sees the glass as half-empty, writing:

I want to take exception to the notion that Python is adequate for a real programming project. The fact that 30K lines of code took 110K lines of tests is a real indictment of the language. My guess is that a significant portion of those tests are addressing potential errors that the compiler would have found in C# or Java. Moreover, all of those unnecessary tests take a lot of time to write, time that could have been spent working on the application.

I was taken aback by this, perhaps because it's been a good while since I've heard someone characterize tests as evidence of trouble as opposed to evidence of quality.

There are (at least) two ways of looking at tests:

1. Tools for discovering errors, or
2. Quality gates (they're one way -- are they quality diodes?)

There's no doubt that the software development tradition has favored the former view (once you've typed a line, everything you do next is "debugging"). However, the past decade has seen a ... wait for it ... paradigm shift.

The Agile Paradigm views change over time as a central issue; if it were still the 90s, I would undoubtedly refer to it as Change-Oriented Programming (COP). Tests are the measure of change -- not lines of code, not cyclomatic complexity, not object hierarchies, not even deployments.

(Perhaps "User stories" or scenarios are the "yard-stick" of change, tests are the "inch-stick" of change, and deployments are the "milestone" of change.)

So from within the Agile Paradigm / COP, a new test is written that fails, some new code is written, the test passes -- a one-way gate has been passed through, progress has been made, and credit accrues. From outside the paradigm, a test is seen as indicative of a problem that ought not to exist in the first place. The passing of the test is not seen as the salient point, the "need" for (i.e., existence of) the test is seen as evidence of low quality.

In true test-driven development, every pass fails at least once, because the tests are written before the code. What is perhaps not appreciated by those outside the Agile Paradigm, however, is that tests are written that one expects to run from the moment the relevant code is created. For instance, if one had fields for sub-total, taxes, and total, one would certainly write a test that confirmed that total = sub-total + taxes. One would also certainly expect that test to pass as soon as the code had been written.

As is often the case with paradigms, often just realizing that there are different mental models / worldviews in play is crucial to communication.

Update: This relates to Martin Fowler's recent post on Schools of Software Development.

StartKey will be a technology that allows you to carry your Windows logon around on a USB keychain. Early reaction is mixed as to the value of this, but I loved something similar when I worked for a company developing software for Sun JavaStation network computers.

With JavaStation's, you had a smartcard that you plugged in and, after 10 seconds or so, up would come your desktop. Since most of the time you work at your desk, most of the time this was not particularly valuable. But let me tell you -- it was fantastic for meetings and presentations. No messing around with cables and display settings, no hand-waving when trying to describe an issue you were talking about when you happened to be on the other side of the office.

The difference is that the JavaStations were uniform hardware, too, and all your software lived on the server (which, it turned out at 7AM the morning of a major trade show, is a single point of failure). While you might have a good experience assuming that a random machine has Office on it (a smile creeps across Microsoft's face), there would presumably have to be a solution for specialist software such as Visual Studio or Photoshop that could not be assumed to be local.

I would think the problem with that is that although memory sticks are probably getting capacious enough, the bus connection between the memory sticks and the main computer are going to be bottlenecks.

http://barrkel.blogspot.com/2008/02/langnet-symposium-videos-are-up-in-wmv.html

Recommendations :

http://langnetsymposium.com/talks/Videos/1-05 - Lively Kernel - Dan Ingalls - Sun.wmv

http://langnetsymposium.com/talks/Videos/2-01 - Newspeak - Gilad Braha - Cadence.wmv

http://langnetsymposium.com/talks/Videos/3-08 - Cobra - Chuck Esterbrook.wmv http://langnetsymposium.com/talks/Videos/3-09 - Intentional - Magnus Christerson.wmv

http://langnetsymposium.com/talks/Videos/3-00 - IronRuby - John Lam.wmv

http://langnetsymposium.com/talks/Videos/3-03 - Parsing Expression Grammars in FSharp - Harry Pierson.wmv

I was reading PC Magazine's 25th anniversary issue in which they have the evergreen "what will the future bring?" essays. I was struck by how much talk of medical stuff (nanobots, non-invasive diagnosis, ubiquitous this-and-that) there was. And then it struck me:

Boomers.

Just as they do with every damn thing, boomers define the mainstream concern as "What does this mean to me?" In the past 25 years (to take PC Mag's benchmark) it went from work (what is technology about? Business productivity!) to family (what is technology about? HDTVs, Internet predators, and bluetooth-enabled minivans!) and now, of course, it will shift again.

What will technology be about for the 25 years? Getting old.

Just as you wish you'd written a spreadsheet program 25 years ago or Facebook 10 years ago (well, you would have been flushed away in the dot-com bust, but aside from that...), the thing to think about now are the killer applications for aging, whether that's medical support, post-retirement money management, or Am I Wrinkly Or Not?

Wes Moise's musings on Supercompilation led me to this discussion of the the myth of the sufficiently smart compiler.

The "sufficiently smart compiler" is still trotted out regularly, even though the market has moved away from demanding even moderate attention to performance at the compiler level. Have you timed your rectangular arrays in C# lately? Or, to be inclusive, have you looked at what's (not) hoisted out of loops in Java?

The existence of the Iron* languages from Microsoft stems from Jim Hugunin's discovery that adding moderate smarts allowed dynamic languages to run fast on the CLR:

1. Use native CLR constructs whenever possible. These constructs are all heavily optimized by the underlying runtime engine. Sometimes these constructs will have to be used creatively to properly match Python's dynamic semantics.
2. Use code generation to produce fast-paths for common cases. This can either be development-time code generation with Python scripts creating C# code or run-time code generation using System.Reflection.Emit to produce IL on the fly.
3. Include fall-backs to dynamic implementations for less common cases or for cases where Python's semantics requires a fully dynamic implementation.
4. Finally, test the performance of every CLR construct used and find alternatives when performance is unacceptable. Type.InvokeMember is a great example a a function that must never be used in code that cares about performance.

That's hardly the stuff of PhD theses (don't misunderstand me: Hugunin's paper, which actually said something important, is more valuable than 99% of CS theses).

The point, though, is that we are in a time of high tension between what is possible and what is practiced. This gives me hope that we might see true breakthroughs in programming languages. Fred Brooks spoke of a silver bullet defined as a "single development, in either technology or in management technique, that by itself promises even one order-of-magnitude improvement in productivity, in reliability, in simplicity." [my emphasis]). I don't believe in silver bullets, but I think there's a possibility of shiny buckshot.

On the discouraging side, I think there are great difficulties to building such a system: the development of a shiny shotgun is, I think, the work of double-digit person-years. It's work that's too far over the horizon for VC funding, too pragmatic for grants, and too dependent on brilliant execution by a small, high-performance team for Open Source.

With the release to public beta of Popfly, Microsoft's mashup editor, I'll reiterate my theory that mashups are the UNIX shell of the Internet. The corollary is that we need a suite of command equivalents:

Right now, everyone's concentrating on what output the mashup editors can produce or what the component manipulation looks like. I think the winner of the mashup evolution will be the one that provides the most flexible suite of components.

[C]omputer-science grads saw their average starting salary offers grow by 4.5 percent last year alone. The new average salary for a job right out of college is now $53,051. That's the highest amount this decade.

Starting salaries surge for computer science grads [Ars Technica]

Interesting. I still think that the future is mixed-at-best for United States programmers (with our relatively high cost), but at least for now there's some good news.

Yuriy Solodkyy demonstrates the combination of LINQ and Reflection APIs, a technique which could prove to be tremendously powerful and which strikes me as allowing LINQ-enabled languages to have a level of "dynamism" that puts to shame duck-typing.

Could this simply replace the Visitor pattern with an approach that needs no cooperation from the data structure?

Would this allow an Abstract Factory that allowed you to dynamically find all products of one Factory and replace them with those of another?

 [via Steve Pietrek]

The working groups of the C++0x committee are working hard to complete a major new standard for C++ (there's a big meeting here in Kona in October). If you're not intimate with C++, you may be surprised that such an important language has not had a standard threading model and that such a model is a major part of the C++0x version. This is actually part-and-parcel of the design philosophy that made C and C++ so important: the number of libraries dictated by the standard for C and C++ is much smaller than the BCL or Java's SE libraries. This allows standard C and C++ to be available for hundreds of processors.

I recently read the public C++0x papers on threading (links below). The proposed threading model is non-radical and is based on Boost.Thread. The reasonable perspective is that this is a conservative decision thoroughly in keeping with C/C++'s long tradition of minimal hardware/OS assumptions.

The emotional perspective is that they've let slip by a golden opportunity to incorporate the best thinking about memory models. "Multi-threading and locking" is, I would argue, demonstrably broken for business programming. It just doesn't work in a world of systems built from a combination of libraries and user-code; while you can create large applications based on this model, large multithreaded applications based on locking require not just care, but sophistication, at every level of coding. By standardizing an established systems-level model, C++0x foregoes an opportunity for leadership, albeit radical.

One of the real thought leaders when it comes to more sophisticated concurrency semantics is Herb Sutter. His Concur model (here's a talk on Concur from PDC '05) is, I think, a substantial step forward and I've really hoped to see it influence language design. Is Sutter, though, just an academic with flighty thoughts and little understanding of the difficulties of implementation? It seems unlikely, given that he's the Chair of the ISO C++ standards committee. So you can see why there might have been an opportunity.

Multithreading proposals for C++0x:

• http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2320.html
• http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2334.htm
• http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2338.html
• http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2381.html
• http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2382.html

Looks like the only programming tools for Tilera's 64-Core CPU is a C compiler, but the day is fast approaching when we're going to start seeing more and more of these types of tools in the mainstream.

Bill de hÓra makes an intriguing pitch that programming will be impacted by increasing data volumes more than by the transition to multi-/many-core. His basis is anecdotal -- we don't have the same metaphysical certainty that all of us will be dealing with much-larger datasets as we have the certainty that we will all be dealing with multiple and then many cores -- but is logical. The speed of a single stream of in-cache instructions is blazing: short of chaotic functions, it's hard to imagine perceptibly-slow scenarios that don't involve large amounts of data.

What I find especially thought-provoking about this argument is that it stands in opposition to another post I was going to make about YAGNI infrastructure. Not long ago, Alan Zeichick ranked databases and Ian Griffiths questioned whether he took price-performance into account. Even allowing that there are costs for OSS (training, tools, administration, etc.), I've noticed that few real-world CEOs understand where their companies stand in relationship to scaling. In my experience, they often over-buy software- and hardware- capacity and under-buy contingency capacity.

It seems to me that nowadays we work more and more with data streams and not data sets. On a transaction-to-transaction basis, I think it's an uncommon application that uses more data than can fit into several gigabytes of RAM (obvious exception: multimedia data). Never mind multi-node Map-Reduce; I'm saying that it seems to me that many "real" business systems could have a single-node non-relational data access layer.

It seems that what I'm saying is in direct contrast to what de hÓra is describing, and yet points to the same "maybe we ought not to start from the assumption of a relational DB" heresy. No conclusion... food for thought ...

Reflection: I think I let my attention wander -- the world de hÓra is describing is that high-performance computing and I wandered into general business-computing. The two intersect, of course, but are not generally the same. So the thought then becomes that powerful relational databases are being squeezed from both the low-end ("eh, just put in memory") and the high-end ("ok, so this is our distributed tuple-space...").

Maybe the readers of my blog are more astute (and better looking!) than average, but I was happy that several comments to my recent post on type inference were properly dismissive of what one called "the static vs. dynamic holy war." As I said when writing about the myth of better programming languages last year, different programming languages engage your mind in different ways and that is what is worth pursuing. There was a time when I was programming professionally in two languages: C and Prolog. They engaged my mind in such profoundly different ways that shifting between them felt like the clutch on the '77 Ford van I was driving at the time (three-on-the-tree, baby), but in terms of problem solving, I felt like Superman.

Now, first-class functions have entered the mainstream (primarily via C#) and that, in combination with an influential paper about Google's MapReduce programming model has led people to begin to see what functional programming advocates have been talking about lo these many years.

Similarly, people are beginning to realize that concurrency models just might be important in the coming years and are beginning to pay attention to languages like Erlang. (Incidentally, O'Reilly & Associates seems to be betting that "shared nothing" is the way to go, a conclusion that I think is certainly too sweeping and premature. ORA is the most influential publishing house in software development right now, so the biases of their editors in this area will have a noticeable impact on the debate in the years to come.)

Update: No sooner had I written this post when I see in my Inbox that Pragmatic Bookshelf has published Programming Erlang. Look for a review in the coming weeks...

I agree with Alan Zeichick's analysis of IBM's acquisition of modeling tool vendor Telelogic:  the overlap with IBM's Rational product line is high, the acquisition "is a bid to buy market share....we’ve taken a powerful innovator and strong IBM competitor out of the market."

The software development industry typically pendulums on modeling tools: excess, backlash, abandonment, code is king, frustration, some modeling helps, we can model everything, excess ...

Right now, modeling is not popular. But I think it's actually passed its nadir and, if history holds, we should see modeling increase in popularity. The problem for IBM and Rational is that part of the pendulum is the embrace of new modeling graphics/languages.

Michael Seuss ponders one of my favorite questions: How much of the software industry will have to deal with the concurrent computing [opportunity]? He hits the vital points:

• 2, 4, and maybe 8 cores may be usefully exploited by system services (anti-virus, disk indexing and searching, etc.), but when you get beyond that, any program for which performance is any kind of issue simply cannot ignore the capacity (this is why I distinguish between our current "multicore" transitional phase and the coming "manycore" era).
• Media programming (games, A/V processing) have an essentially infinite appetite for processing
• The manycore era provides an opportunity for new types of functionality. He mentions concurrent semantic analysis of your input, both typing and spoken, and the accumulation of context documents. For instance, as I type this, my computer might be gathering all my blog posts, OneNote notes, source code, etc. relating to concurrency. (And then wouldn't it be cool if it offered them for my perusal, maybe with, I dunno', a goggle-eyed paperclip?).

But I think the $64 question is whether such services will be provided in a service-oriented, cross-application manner, or whether it will be the case that we find broad opportunities for them within applications. For instance, mail programs and word processors have had search functionality for a long time, but if you were designing such a program from scratch, you would probably be better advised to say "Hey, I won't implement a complete search subsystem, I'll just make sure I can be indexed by Windows and Google Desktop Search. If I want to add value, I'll layer on top of those systems if at all possible."

Conversely, if you had some powerful new value proposition (semantic analysis, task recognition, visual input), wouldn't it be vastly better for you and your customers if you could provide it to applications other than those that you happen to have written? In other words, of course value in the manycore era will derive from increased parallelism but maybe that parallelism will still be very coarse-grained. Maybe software organizations will face a choice: "Either develop client-oriented value with the best practices of "traditional" non-parallel development or develop broader, system-oriented value using whatever is the emerging set of best practices for system-level parallel development." Maybe that choice will become increasingly orthogonal.

Now, the final part of the thought experiment is this: if that scenario is reasonable, what kind of platform services / APIs would one desire?

Popfly is the name (and URL) of Microsoft's new non-professional developer community, a Windows Live site whose flashiest feature is a Silverlight-based "mashup editor" that facilitates pipes-and-filters development. Before reviewing the gratuitous 3-D spinning cubes, though, pay attention to the context:

• Visual Studio Express has had 14,000,000 downloads (source: Dan Fernandez personal communication). Of course that translates to something far less than 14M users, but it ain't hay;
• The Popfly mashups run inside Silverlight, so anyone wishing to view their friends' / child's / grandkid's project is going to have to install the Silverlight runtime;  
• Silverlight is going to rapidly evolve to incorporate the Dynamic Language Runtime. Silverlight + CoreCLR + DLR == Microsoft's platform play for dynamic languages, which have crossed the chasm and, whatever their other strengths or weaknesses, are easier to learn than explicitly typed or Pascal-like highly-structured languages

Microsoft is on the verge of restoring the bridge between power users and programmers.

The collapse of that bridge -- the disappearance of macro-based automation during the DOS-Windows transition and the removal of Hypercard from the Mac -- was the greatest setback the professional programming community has ever suffered (#insert COBOL or C++ joke here#).

Pipes-and-filters mashups are the UNIX shell-commands of the Web. The next step is automation -- after you start figuring out how to pipe commands, you start writing shell scripts, at which point you're programming the platform at a higher abstraction level. That's a crucial point: we're not talking about flow-control and manipulation within the pipes-and-filter components, but at the platform level. That's why it's huge that the Popfly mashups are executed on the client (within Silverlight) and not on the CPUs of the host. Mainframes->Minis->PCs: empowered users require and embrace personal resources. This is the salient distinction between Popfly and Yahoo Pipes (Popfly also works with more types of data, but Yahoo could address that). It's not just that there's a resource-consumption scaling problem that might be solvable by the host absorbing hardware costs, it's that there's a Big O scaling problem: to the extent that mashups are used to program the Web, as soon as people start looping/recursing, you're talking about non-linear increases in resource consumption.

To be clear, I don't think Popfly is the Bourne Shell of the Web -- that hasn't been written yet. But I think Popfly's the | and Silverlight's the $

I'm dying because I've just had a long talk with two of Microsoft's heavy hitters on the Dynamic Languages Runtime (DLR) team and have much to discuss, yet I am in a frenzy preparing for a business trip and cannot yet take the time to do the discussion any kind of justice.

The single-most important quote, I think, was the statement that "no one will take [our implementations] seriously until we can run-- / We aren't done until we can run--" [Django | Rails]. That was contrasted with important libraries that were heavily dependent themselves upon C-based libraries (Zope, in particular). It was also contrasted with libraries that rely on unusual language quirks or implementation details; the touchpoint on that was Ruby's ... shoot, I thought Lam said "objectspaces" but I don't see that in the standard library ... maybe he said "ObjectSpaces-like ability to traverse the entire in-memory object graph" (Anyone know what lib that would be?) ... Anyway, the point was that this was an example of something that would be very difficult to implement within the constraints of the CLR.

I'll update this entry when I can report in more detail...