The Joys of Java (not!)

Oh, the joys of Java (and most of its peers): You can't really separate theory from algorithm.

For example, if you want to use an idea from graph theory, you need to either go fetch a graph-algorithms library or cruft one up yourself. So, let's say you need the shortest path from one node to another. Well, maybe your graph library has an implementation of Dijkstra's Single-Source Shortest-Path (SSSP) algorithm. That's well and good, but now your library might give you the path with the fewest edges, or it might support a notion of edge costs, and now you can specify edge costs and then get SSSP as modified to take edge costs into account, and get the lowest-cost path from node A to node B. But maybe your library requires costs as double-precision floating point values, and maybe your application provides a cost function which depends (say) on the mode of transport, or even on the time of day at which you arrive at a node (which might reflect bus or train trip routing ideas). In that case, there's no fixed cost for any given edge, so the notion of providing a double-precision number to each edge is suddenly useless.

By the way, when you're running SSSP, you probably want to know what the actual path was and not just the cost to get there, so for the duration of the algorithm, you'll want to adorn each node with a reference to the previous node on the shortest path. But once you've read off your path, the adornments are just noise, and may be forgotten. Of course, your graph library could provide for a field in each node to reflect this adornment, and then just make sure to clear it in all nodes before running SSSP, which is fine in small graphs or if you want the shortest path to everywhere all the time (neither of which is usually true). Or, it could use the notion that each run of SSSP may be numbered, and, assuming you run it less that four billion times, it can use the predicate (this_run_number == node.SSSP_run_number) to decide if the node has been visited yet (and therefore if the back-pointer and path-cost fields contain valid data). (There's little point continuing a run when everything in the work queue is more costly than the best known cost to the intended target node. This means you won't visit every node every run, so it's more trouble than it's worth to clear a flag in every node. You could instead clear them all only when the run count wraps, but I digress from the main point.)

All this discounts the notion that you might be interested in running the A* algorithm instead, which uses a priority queue for which nodes to examine based on how close they are to the destination (and which therefore requires that your nodes have position in a metric space). See, the A* algorithm is a lot faster than SSSP because it tends to look only at nodes that are worth looking at. It is therefore much better for path-finding when the nodes represent points on a surface of some kind. But guess what? Your favorite graph library probably doesn't adorn nodes with XY position. And if it does, what if you need XYZ position? What if you're interested in city-block-distance instead of Euclidean distance?

I've said nothing yet of node labels, edge labels, graph colorings, directed vs. undirected edges, unique vs. non-unique edges, nodes with data records in them, finding connected components, finding convex hulls, or any of six dozen other interesting things you can do with ideas from graph theory.

Depending on what algorithms you want to run, your nodes will need different data in them. There's no universal answer: no matter what sort of node your graph library provides, there's some application for which it is inadequate.

One approach that came to mind is for all the algorithms to work by keeping a HashMap from the domain objects to the particular data created and maintained by the algorithm, and then require the client programmer to pass in an adapter from the domain to the information needed by the algorithm, similar to the way the Comparator interface works. And this may turn out OK in the specific case of widely-popular and generic graph algorithms, but:

• It creates a fairly significant cost in run time. Granted, it's (approximately) a constant multiplier, but it's still a pain.
• It's easy to do a bad job designing the interfaces involved.
• It still doesn't address the real problem, which is that data is kept around for different reasons, but it's all got to be declared in the same place.

A sufficiently well-designed notation for programming would let different parts of your program specify adornments to structures as needed for different purposes. A compiler for such a notation would then stitch all the adornments together into sensible run-time structures. The algorithm adapter idea is probably still a good one, but if it's integrated into the design of the language, then you won't have the clerical pain of writing a bunch of stuff like

new FavoriteAlgorithmAdapter() { 
    public double foo(DomainObject ob) { return ob.foo; }
    public int bar(DomainObject ob) { return ob.bar; }
    ... etc ...
}

most of which could be (and should be!) inferred from context.

So that's my rant for the day. I hope you like it.

Classically, there have been two schools of language design: the Lisp approach and the Fortran approach.

The Lisp school starts with the pure mathematical notion of a function, and then develop everything around the idea of evaluating recursive functions. There are also functions that return other functions, and so on. In this model, explicit assignment of variable values is not absolutely necessary, because you have parameter binding and presumably solve the "tail recursion" problem etc. Adherents to the Lisp school insist that LISP is far and away the highest-level programming language that could ever exist on a machine, and that they only deal with an inconvenient, ugly, illegible, and very consistent syntax because they don't want to incur the costs of machine-parsing something more "complicated".

But this is not the path I mean to advocate.

The Fortran school builds successive layers of abstraction atop the bare machine, progressively inching the syntax and semantics closer to what seems natural for practical programmers to design practical programs in. The only trouble is that practical programmers are the ones that have already been using the lower-level languages that Fortran and its successors were meant to replace. Therefore, you have all these notions of what is practical in a computer programming language: the system should result in programs that execute quickly; structuring notions should be embedded in the grammar so they cannot be confused; and so forth.

This isn't quite the ideal either.

History has shown a certain amount of convergence of these two schools. But I think they are converging toward a third point, and it's that point I mean to advocate. In particular, we should:
1. design our languages so that it's easy to express and reason about our desired programs,
2. axiomatically define the language independently of its realization in a programming system, and
3. value an implementation by its fidelity to the standard -- not any "reference implementation".

The first step is really one of the great open problems in computing science. It's complicated in part by disagreement over which programs are worth expressing. But I have some opinions on the matter, and I believe that the expression of these opinions in the form of language definitions is the first step towards testing them. The second, of course, is trying the new languages out in a community. But to get participants, you pretty much need a practical realization of the language.

Possibly the greatest example of this approach to language design is given by Pascal. It was designed from first principles for the approach of stepwise design refinement and sensible reasoning about the workings of a program. It turned out to be excellent in an educational context for just that reason, and it was also a significant improvement over virtually everything that came after it. Sadly, politics and advertising eventually trumped Pascal's dominance in the hobby-programming space, so that it was replaced by the likes of C++ and Java.

Realizing a new programming language is not a trivial endeavor by any measure. It's quite a lot of work to get any significant portion of a new system up and running. But let us recognize some facts:
1. We can work in an existing very-high-level language just to get things off the ground.
2. We don't need amazing speed from a proof-of-concept prototype; we can optimize later.
3. When you have -- and understand -- the source code to the compiler or interpreter, then it's easy to add features as necessary or desirable.
4. If you have a working interpreter for the interesting subset of your language, then you're really only a few steps from a working compiler. The difference is generating code to compute results instead of computing results directly. The complexity of generating that code depends on a lot of factors, though; it can be a major effort to make the conversion, but certain object-oriented methods can help the process along.

In any event, a programming language needs at least seven things to be "real":

input/output
mathematical and symbolic manipulation
temporal grouping of operations
selection of one possible operation out of more options
bounded repetition
functional/procedural abstraction
data abstraction

Of these, the last two seem the most difficult to realize because they have the greatest impact on how all the other parts fit together. But is there a way to factor this difficulty out of the way, so that we can change (for example) the mechanics of the data abstraction mechanism without (too much) changing everything else?

If so, then it becomes possible to develop a straw-man programming system and then successively improve upon its faults until you have the sort of programming system that people would like to use in the development of serious software projects.

An open letter to my legislators and yours:

---

There's a food and nutrition "safety" bill running through the system right now, and I have to ask your  help to kill it off. The DSSA (Dietary Supplement Safety Act) would hurt voters by reducing consumer freedoms and wasting tax dollars through needless policing of the nutritional  supplements market.

Let me explain what I think is sensible in a food and food supplement system:

1. If there is a material misrepresentation about the CONTENT of a supplement, that should  be a crime. So we need to see all ingredients, not just "active" or "inactive" ones, on  every processed product offered for sale for consumption. (Existing law already requires this, I think.)

2. Don't put health claims on foods or food supplements. In fact, don't even put anything  that hints at a health claim. If you've seen those claims about breakfast cereal lowering  your risk of one or another disease, or the "nourish your brain" juice in the produce aisle,  you know what I'm talking about.

3. If there's a controversial ingredient (say, stevia, trans-fats, aspartame, diacetates, bisphenol-A, genetic modification, or byproducts of ionizing radiation) then don't regulate it, label it. And label it boldly. Until the academics can come to a consensus untainted by concerns about the sources of funding for research, the best thing is to make the consumer fully aware of what's in the food he buys. Treat the issue similar to the way we treat common food allergens: A labeling requirement.

4. The G.R.A.S. doctrine: A food we've used safely for generations should be GENERALLY RECOGNIZED AS SAFE. Additionally, true hybrid crops (not genetically modified ones) are most likely also safe, but should be labelled as a recent hybrid, along with parentage, to facilitate allergy safety.

5. No favors for centralized efforts. For example, if there's a fixed fee to certify a supplement farm, then a large conglomerate farm has an advantage. If there are large barriers to entry, it creates conditions for monopolies to take wealth away from society.

Please take a close look at any so-called "safety" bill to ensure that none of these common-sense ideas are violated.

Thank you.