Little Lisps: Programming Candy or Spinach?

Last time (StreamTokenizer and Declarative Lexing), I mentioned an idea of presenting language designs in this space as a puzzle to be solved, like a crossword puzzle. I invented the idea there and its been growing on me.

The previous week or so I'd been reading Sam Kamin's "Programming Languages: An Interpreter-Based Approach", so this didn't seem like such a crazy idea as it may sound. In "Programming Languages", Kamin starts with an interpreter for an extremely simple language using Lisp syntax, and procedes with each chapter to show what modifications need to be made to get interpreters for Lisp, Scheme, SASL, APL, Smalltalk, Prolog and others. They all use Lisp syntax, so the code changes are kept quite manageable, and the reader can focus on the essential differences in scoping, evaluation strategies, and the like.

It seems, as a first step, if the Language Design Crossword Puzzle were to be a reality, that making available a standard interpreter source such as Kamin's is a reasonable idea. "Given interpreter0, add macros" would be a puzzle. "Given interpreter0, add object serialization." This is similar in spirit to comments I made earlier about the utility of lambda calculus for studying language features.

But is the Language Design Crossword Puzzle a good idea? What's the point? Arcane Sentiment, a blog I discovered and subscribed to today, introspects on writing little language implementations. He describes certain parts of the exercise as "programming candy", and ironically, they're often the parts written in C, a series of little programming victories. The hard, ill-defined problems to be written in Lisp are the parts that tend to slow him down and demotivate him. (Arcane, I hope I'm fairly characterizing that post. Please correct me if not.)

I had to chuckle in self-recognition, as earlier this week I was watching the first few SICP videos, evaluating the examples in a Scheme-ish interpreter I'd whipped up on Monday and Tuesday, extending it during pauses in dialog while Sussman wrote on the blackboard. Until he hit the pi fraction example and I realized I wasn't at all sure if I wanted to right at that moment be writing code to rationalize denominators and factor fractions or whatever else Scheme might do to support exact rational number (fraction) arithmetic (e.g. (/ 1/2 (+ 1/8 1/3))). That problem at that moment was not interesting for me, and was not well-specified; are rationals always reduced to lowest terms? How is conversion to and from reals handled? I'd have to go study R5RS to learn the expected behavior. Handling the number tower was not my goal going into this project.

Why does Arcane Sentiment dabble in Lispy implementations? Why do I? Why reinvent the wheel? For me, it's a way to learn, to study. Toy implementations are rewarding, as they let you discard parts of a language implementation system that are indeed hard, and focus on particular points of interest. You need to be careful not to oversimplify, if you intend to take your lessons back to a real system. But this approach is something we advise junior programmers all the time: if you're struggling with how a library or language feature is working in the application, try writing a small example program first until you understand how it works.

So, I propose we have the best of both world. Language design problems can be programming candy, as well as programming spinach, that is something good for you. My wife has been making a spinach recipe from her Spain and Portugal cookbook which features raisins and pine nuts. It rocks.

The other question is, is there interest in a "language design puzzle" feature? Before we get to that, let me ask a more relevant question: what aspects of programming language implementation or operation are of interest to you? Macros? Evaluation strategy? Optimizations? Drop me a line to the Google mail account jfkbits and let me know.

---

Blog challenge: write a post using the phrase "free as in spinach".

StreamTokenizer and Declarative Lexing

One thing I've noticed about marketing is how frequently an appeal is made to change your lifestyle to include more of whatever is being sold. I first noticed this when I read in a catalog that Ikea wants me out of that rat race of the outside world, so I can spend more time at home. And by the way, don't I want my home to be a comfortable inviting place to spend time? After that, I've seen it everywhere. Here at JFKBits we want to know why the world doesn't write more language processors. Everyone can enjoy a world of recreational symbol translation. I was on vacation last week, reading a programming language book by the beach. Maybe someday we'll run programming language designs in this space and JFKBits readers can implement them as a kind of crossword puzzle of the day, in an hour on the train home from work. So today, we're thinking about how to get a lexer up and going more quickly.

---

When you're designing a syntax, it's typically done at a high-level:

• Comment syntax: line-oriented or delimited, or both? do comments nest?


• Identifier syntax: Limited choice for the first character (e.g. letters and '_'), followed by mix of alphanumeric and underscore. In Lisp, symbols syntax is much more flexible.


• Operators and grouping syntax: parentheses, brackets, multi-character operators like ++, ->, and &&=.

It might be useful, in terms of quickly prototyping a domain-specific language or language-aware utility (e.g. a tool that finds buggy code patterns), to have a lexer generator that lets you declare properties in these terms rather than translating to regular expressions.

Java's StreamTokenizer, while not a universal tool, is a step in that direction.

What I like about StreamTokenizer is that it raises the level of programming closer to the problem domain. Regular expressions are the traditional and well-understood means of specifying a lexer's accepted language, but this declarative style is possibly a better programmer's tool. (Note well that I'm talking about StreamTokenizer, not StringTokenizer which is a much simpler state machine.)

For example, in playing with Kamin's interpreters with their S-expression-based syntax, I've been using this configuration to scan LISP-type code in Java:

tokenizer = new StreamTokenizer(new BufferedReader(reader));
tokenizer.resetSyntax(); // We don't like the default settings
tokenizer.whitespaceChars(0, ' ');
tokenizer.wordChars(' '+1,255);
tokenizer.ordinaryChar('(');
tokenizer.ordinaryChar(')');
tokenizer.commentChar(';');
tokenizer.quoteChar('"');

The basic idea is that StreamTokenizer is a state machine with hard-coded states and transition arcs, and you configure it with what characters are in the relevant character classes. For example, from the state of skipping whitespace, there's a transition to a string literal state, when a character from the "quoteChar" class is encountered. The string literal state accumulates, transitioning back to itself on characters not in the quoteChar class. It's simply up to you to configure which character or characters constitute a quote delimiter. The essential observation is that lexers for many useful languages share state machines of identical shapes, and they differ only in the definitions of character classes.

Of course, not every language fits the preprogrammed state machine shape. StreamTokenizer can't even handle Java, because it has no capacity for multi-character operators. It can be configured so that '+' is an "ordinary character", meaning it is lexed as a single-character token, but there's no way for a parser to know if two '+' tokens in sequence came from the input "++" or "+ +". This is what I mean when I say StreamTokenizer is not a universal lexing tool.

But I still wonder if there's room for this declarative manner of input, building on higher-level concepts like identifiers and operators, for a more general lexing tool. This could be combined with a programmatic knowledge base of some of the standard lexical idioms running around. You could say "give me Python-style identifiers, with the standard Java operators except these four which don't apply to my language." I'm not at all sure there is need for such generality, but I think it's worth writing down, as an idea for future inspiration.

Type Directed Code Search

We live in a Golden Age. You can buy Ubuntu desktop computers at Wal*Mart for under $200, there are more choices of programming language than ever, and their software libraries are rich and well-designed with lots of orthogonality. Let's say you're learning one of these new libraries, you're feeling all baroque and XMLish, and you set your heart on acquiring an org.w3c.dom.Document object. Where do people get those, anyway? Where's the parser that spits it out? After much digging, you find that a javax.xml.parsers.DocumentBuilder will make you your document. Ah, but that's an abstract class. Now, who makes DocumentBuilders? DocumentBuilderFactory, of course. This kind of searching gets old quickly.

Maybe this kind of run-around is unavoidable when learning libraries, and documentation and books can certainly help orient you, but there's another tool for our kit which may help in some cases. What might be useful is an index keyed by type that points to methods using the type, either in parameters or in the return type. This index could answer the question "where can I find methods that return type X?" or "what are all the methods that take an X as an argument?" Such an index could help both in learning as described above but in any activity where you need to search the code.

Eclipse goes pretty far in implementing this, not far enough, but enough to hint at what we could do. In the dialog below I've typed to search for "DocumentBuilder", selected to Search For "Type", and limited the search to "References". Ideally I'd like to limit the search to methods returning the given type; I want to know what methods generate this type. Also note that we've checked "JRE libraries" because we want to know what built-in library generates the DocumentBuilder:

The search results:
This feature seems a natural for Java since it is both statically typed and has the necessary reflection to allow a tool to do the analysis. However, it looks like type inference is coming to the dynamically typed languages too, including Ruby and Javascript and even Wasabi. Since types are not as much part of their language, it may not be as natural to think of searching this way, but the need will grow as more and bigger applications get written in these languages.

With a type-informed search, you can do debugging research. One thing I've seen with large team projects is the bug that has an exact duplicate lurking elsewhere. For example, you find a URL object for a web server has omitted setting the port number via the config.getPortNumber() call. Since everybody tests with the well-known default port 80, things appear to work, but a real customer configures with a different port and suddenly links break. You track it down, add the right calls, and close the bug only to have the customer call back with a different broken link, same root cause but in a different spot in the code. Once you identify a bad pattern like that, you typically want to look for other places it might occur. To find this pattern you could do a text search for URL, but a type-informed one or an AST-search is likely to cut down on unrelated references to "URL" in comments and other areas.

In conclusion, this is yet another application of type information. It's a little on the fringes, perhaps not an everyday tool, but for learning a new library, for doing research prior to refactoring or for debugging, it could be a standard feature in IDEs of the future.

Remove This - A Search Interface Improvement

The computer world has a lot of search interfaces these days, and I don't mean just GOOG (732.94 down 8.85 in heavy trading). I'm talking about things like "Search Messages" in Thunderbird and product searches in pricegrabber. In the old library search style, you had to think about what property you wanted to search by: Title, Author, Subject, depending on which index you wanted. Google let us focus on the search term and let the computer search all the indexes.

Either way, the user interface for reporting results is the same: you get a big list to sort through.

And either way, if you find your search isn't working, you start a new, slightly different search.

But I'd like to a twist: a "remove this" button to exclude certain results.

Deleting...From What? with Thunderbird

I should explain how I got this idea: I thought Thunderbird already did it, and wound up deleting some of my email.

I set up some elegant query, and still got back a whole lot of results in the nice table view. I noticed the Delete button, so I selected a number of them that were not relevant, and clicked it, thinking that would remove them from the search view. Ho, ho, ho. They were list traffic archived elsewhere, so no biggie. But then I wondered why not also offer the feature I thought it was offering.

Remove This

This got me wishing that all search interfaces would work like that - with a Remote This button or link. If you know you don't want a result, eliminate it from consideration in future variations of your query. It helps remove the clutter of seeing the same undesired but superficially-related result come back each time you refine your query.

Of course this implies some state to track your list of exclusions, and some way to clear or manage the exclusions. For an application, e.g. Thunderbird, it's no problem, and for product searches as in PriceGrabber that already support a complex filtering system, it's a logical extension. For Google, I'm not sure if it makes sense, interface issues aside, but I think it's worth considering for the uncluttering effect it can have.

(Above is an Artists Conception of how Remove This could appear in a Google search result.)

As a footnote, Supercomputing 2007 kicks off this weekend in Reno, Nevada. I'm not going this year, but I hear my software is, and I wish everyone attending a fun and productive time.

Franchised web apps

It's time for another free-for-the-implementing business idea. This one: web site franchises.

Take the software that runs flickr or reddit or any of a thousand other things, and package it so it can be installed on a server farm elsewhere and customized. The example of reddit is perhaps most compelling to me as regards customization, because it's easy to see that the format of the software is so independent of its content, yet the social way reddit functions could be adapted to other groups of people. Right now it would be hard to grow a home improvement user base on reddit because of the slant of the existing user base. But somebody could buy a home improvement reddit franchise and start it up. This would be a way for the creators of a web application to get into markets they know little about.

I can think of two possible drawbacks for franchising a given web application. The first drawback is the financial aspect. If the application is having problems turning a profit with the existing international user base, fragmenting it would not be an option. There would have to be the potential for customizing the application in a way that adds value. The second potential drawback is the task of packaging the web application for replication. In most cases, this would be a non-trivial development cost. Designing 3D buttons and Javascript animations is fun and can be taken to show-and-tell, writing install scripts can be a tedious and under-appreciated chore.

Another angle to the web app franchise idea is some things may be salable to large corporations and government agencies for internal use without concerns about compromising confidential information over public networks.

As with most (all) of my ideas posted here, I expect this one is so good it was done long ago and I just now finally forgot enough of its origins that I think it's new. Please correct me. If I happen to be wrong, and you make some real money with this idea, I'd appreciate a link back to this blog, with due credit: "Thanks to JFKBits, whoever or whatever that is" would be fine.

Adding value with programming languages and their tools

Languages of any kind are a two-edged sword. With the cooperative edge, you communicate. With the political edge, you control, using the utility of and dependence on communication to suit your interests. We who are involved in developing language processors and related tools can do well to keep these two edges in mind as we seek to add value with our work.

What is adding value

Clearly programming languages add value in terms of productivity. Even if we're fighting about the finer points of static versus dynamic typing, or Perl vs. Python vs. Pure LISP, almost anything is better than the truly low level of pointing and grunting the computer uses. For most purposes today a FORTRAN or C compiler is better than an assembler.

I've been dwelling on the proposition "programming languages as notation" (my wording) as summarized by Tablizer thus:

Most of the CS literature fits the pattern found in a typical book or chapter on Boolean algebra. Generally this is the order and nature of the presentation:

1. Givens - lay out base idioms or assumptions
2. Play around with those idioms and assumptions to create a math or notation
3. Show (somewhat) practical examples using the new notation or math
4. Introduce or reference related or derived topics

Step 2 is where the value is added, and it boils down down to a "math or notation". In my experience with programming languages, I'd reinterpret that as meaning

• math: give a mapping from one semantic domain to another (direct language translation)
• notation: programming language syntax
  

With that as a working definition, we can see analytically how the first FORTRAN compiler added value. It gave programmers a more familiar notation (syntax) in that they could write expressions ("FORmulas") with infix arithmetic operators and it provided the math (mapping) from that syntax to the lower level assembly or machine language.

We've been getting lots of new languages since FORTRAN, C and LISP. Justifications for new languages have included these ideas, "closing the semantic gap" between programmer and application. The hope is to achieve similar leaps of productivity as those initial leaps from the baseline of panel switches and card readers. It's the churn to gimme a better notation. The notation isn't the only thing of course, we want a decent mapping from the syntax to the semantic domain, to meet our performance requirements, and later, our software quality requirements: "let's eliminate whole categories of errors".

One curious result of the productivity leaps made by our newer languages is that they just make us want to write even bigger programs. We're not satisfied to write the old applications in an elegant, maintainable way using the new idioms and language features. We say "well, now we can do that project we only dreamed of," and proceed to applications with ever-increasing scope. (An entertaining take on this can be found in the Law of Leaky Abstractions).

With that said, I want to present a few ideas where language tools can be applied to the productivity challenge. These are opportunities for people with knowledge of compiler and interpreter internals but does not involve yet another new language. With acknowledgment of the irony in presenting these after just bemoaning application bloat, here are a few ideas for areas that could be improved in the practice of programming:

#1: Automatic refactoring support, like Danny Dig's refactoring engine which is included in Eclipse 3.2. This helps make progress in the old can't-refactor-because-it's-not-backwards-compatible problem by providing automatic tools to upgrade client code when shipping libraries with changes in APIs.

#2: Code visualization - tools to understand the static structure and dynamic flow of code . We can also improve in historical visualization, or how code has changed between revisions.

#3: Data visualization - Debuggers let you examine and even edit data structures at runtime, why not provide similar capabilities at code writing time? Why not let programs be specified by something like Emacs record-and-play macros where you "edit" the data structures? I think part of what makes programming difficult because it's hard to automate something without seeing what's being automated. While visual languages have not really taken off, I think it's an untapped potential, for some domains anyway.

#4: Automatic test generation - automatic creation of tests based on static inspection, to supplement hand-written tests.

#5: Machine-learning helpers for programming - instead of programming directly, use a tool that accepts examples of inputs and outputs and generates rules as starter code.

#6: Integration of coding environments with networked repositories - This means things like direct interfacing of language and tools help with team wikis to help share experience between programmers. Microsoft tools have started to do this, and there is room for growth. Instead of static coding style checkers definitions, what about augmenting them with networked information? Worse than Failure's Code Snippet of the Day could be formally encoded to flag catch ridiculous code patterns immediately.

#7: Easier ways to search code by pattern, not just textually, but by structure

These tools don't need to apply to new languages. As we found with AnnoDomini, a Y2K tool for fixing COBOL programs employing type theory and itself written using a functional language, tools can follow many years after their target language.

What adding value is not

We started by mentioning the two-edged sword of languages. The second side of languages, their use as a political tool, is not necessarily a way to add value, but it is to control. This phenomenon is studied in sociolinguistics, and you may have personal knowledge of it. What languages should be taught in schools? What languages can you get in trouble for speaking? What is the "official" language, or languages? What are the motivations for the proscribing or forbidding other people to use or not use a language?

While you think about that, let's talk about plugs and sockets. Let's say we make laptops. We will need to make a power supply, something that has two plugs. One is the AC side that plugs into the wall outlet using a standard connector. The other is the DC side that plugs into the laptop. For this DC connector, we have a choice of going standard, with an off-the-shelf standard size and shape, or going proprietary, designing a unique size and shape, possibly protected by patent. (For the record, I don't actually make laptop power supplies. So if they don't, for some reason, ever ever use standard connectors, I'd love to know, but I don't think it affects the analogy.) We can see the two edges of the language blade. As long as the DC plug and the laptops connector match, they cooperate, it works; the two side "communicate" power. The shape largely doesn't matter to the function of communication. But the choice of shape does affect what other laptops the power supply works with. By choosing a standard shape, we open the possibility of wider interconnectivity. By choosing proprietary, we restrict the possibilities. If someone needs a new power supply, now you have to come to us to buy it, or to a another vendor who licenses our connector patent.

The open vs. closed DC connector choice will sound like a familiar dichotomy from many technical fields, perhaps most familiar as the operating system question. I bring it up for the programming language audience as a reminder that any programming language represents a particular shape of interface, and we need to be aware of its potential for use as a political tool.

Back to human languages. We need to be aware of who is agitating for adoption of a language, and why they are doing it. Hear these motives with an ear for the programming language arena. "You may not use that language spoken by our enemies" emphasizes the enmity on a personal level. "You must now speak our language, vanquished foe" is part of a takeover plan. Language promotion can be sinister, as when members of an ethnic faction seek independence from a larger nation. They may appeal to ethnic identity as leverage to gain power, promoting the household ethnic language over the national one taught in schools. Language promotion need not be sinister. In an extremely fragmented situation it can achieve the communication productivity we spoke of before. Papua New Guinea is actively promoting Tok Pisin as a means of unifying its citizens who natively speak thousands of quite different languages, a situation created in part by its poor network connectivity. No, that's not it, I mean by the rugged terrain and isolated mountain villages. You may see language promotion taking place, and wonder what the language itself does for people. But we need to look for the bigger picture, which includes understanding who is behind the promotion and what they are trying to achieve. "You must use this language because you belong to this group" plays up uniqueness of the group, as with Finnish. Modern Finnish was developed in the 19th century as part of a growing nationalism to help distinguish it from neighboring Sweden and Russia. The emphasis on uniqueness, of preserving culture is interesting. Cultural forms involving language include expressions, wise sayings, jokes, stories, songs and poetry. These form a body of useful works. Preserving them is valuable for those steeped in the culture. You could say they have a vested interest in the culture.

Among other reasons, I think one reason languages are given away for free by businesses is that it helps spread adoption of the interface, creating a hook to create business in other forms. Once a customer has paid to develop working code in a language, it represents a vested interest in that language. We can think of the vast collection of COBOL applications as the prime example.

New languages have had it tough. In the 80's and 90's, without an absolutely killer feature, such as infix expressions when the alternative is per line arithmetic, new languages were being developed, but perhaps not rapidly. I'd venture that new languages are only good for new projects and new people (called "youth"). The rise of the web has brought with it a slew of opportunities for both those factors to coexist, giving rising to a growth in the number of available languages to use both browser side and server side. As the web matures, I see companies still trying to take advantage of the momentum to adopt new languages (*cough* Adobe Flex *cough*), and while it's exciting I'm starting to see the other side. Is it really a boost in productivity if we're retooling our businesses and schools to use a new language and environment every few years? Or are we moving sandpiles around, taking the same basic program (no pun intended) from one person's vested interests to another? Be aware of the other edge of the language blade. Adopting or creating a new language may not be adding value. Or if it is, you need to know, adding value for whom?

---

For more reading:
Cylindrical types of DC connectors at Wikipedia

Language politics at Wikipedia

Culture of Finland at Wikipedia

Algorithm Derby

How many of us have had this idea? You have a problem to solve, and more than one way to do it. You're not sure which is fastest, so you hold a race. Let all your algorithms take a whack at it on parallel processors and use whichever result shows up first.

Well, the patent for that idea was issued to NCR in 1997.

From the abstract:

A parallel search method for a parallel processing computer which employs different and competing search procedures to search a collection of data. A search problem is formulated by a data management application. The competing search procedures are created from the formulation of the search problem and pre-existing rules. The competing procedures are executed. Additionally, execution of the competing search procedures may be monitored to obtain information about the effectiveness of the competing procedures, and the competing procedures may be changed based upon the information. In those search cases where a time limit is necessary, a timer is started at the start of execution, and a solution is returned to the data management application.

At this point I have no word on whether NCR is licensing this patent or not.

Identifiers in any language

You might be a language geek if you ever thought...

Wouldn't it be great if there was a program that you could feed an identifier, tell it a language, and it would tell you if that identifier was valid for the given language? Or tell you useless stuff like all the languages the identifier is valid in? Wouldn't it be great if this program knew all about identifiers in any programming language you could think of?

You might also just be too lazy to memorize the rules or try running a program with it, and too particular to go with something safe, an identifier you know will work.

The inspiration for this idea: I want to know if hyphens are OK in CSS identifiers. It turns out they are (the W3.org syntax reference says so).

This sort of question pops up a lot in my experience, and I suppose the identifier question is not that critical. But the idea of a one-stop language reference with some level of interactivity is appealing. So, I think there's room for a C3PO "protocol droid" program that just knows stuff about all the languages out there. Rules for identifiers would be a decent place to start, followed by rules and information for simple stuff like constants and literals.

As is often the case with my ideas, they've already been done, marketed, and obsoleted by something better, so if you know of an implementation of this idea, leave a comment.

Marketable language names

OK, it's Friday afternoon on a spring-like day and the Editorial Staff is in a goofy mood. In case you didn't realize, we had about a thousand visitors this week thanks to a couple of posts being picked up by reddit and dzone.

This discussion of marketable names for programming languages draws a parallel between the success of Coca Cola and its name, and the opposite effect for Slug Cola, despite the latter's being regarded as tasting better.

"A Nickel's Worth" approves of the names C, C++, FORTRAN, and Java (I would also add Ruby and perhaps Perl). He disapproves of most other names, apparently, including ERLang, Smalltalk (doesn't sit well with managers and executives), and LISP (obvious reasons?).

One of the reasons given for the approval of "Java" is "It's short, it's cryptic, it's friendly; it implies a connection with a caffeinated beverage." Other good ones that fit the same description could be Cola and Jolt. But I thought of another good one.

Darjeeling.

Stop that sniggering, and let me finish. It's Friday, remember? I gotta get home.

Darjeeling is a real place, like Java. It's associated with a caffeinated beverage. It has a great filename extension: drj. I like to think it's got a more sophisticated ring than Java, so obviously it needs to support the Thinking Programmer's language features like lambdas and sum types.

It does have some down sides. It's not short, that part is true. Nobody knows how to pronounce it. Rather than jars, people would want to know whether to ship their code in .bags or as loose leaf...

OK, so this is harder than it looked at first. You got any bright ideas?

Quick Reference Reference

Just stumbled across this page of links to "quick reference" cards and pages:

http://www.digilife.be/quickreferences/quickrefs.htm

I think it would be a cool thing to have a web application which lets you build a customizable quick reference guide. From a grand master template, you would pick tools for which you wanted quick reference guides, and then within the guide itself you would pick which features you wanted included on the guide, so you only include reminders for what you tend to forget.

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("os.name") 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.

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". More...

(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".

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.