Watch this space.

I've been rather busy this week trying to hammer the new Kowari Resolver SPI into shape, so I don't have time to comment properly on the DAWG discussions regarding NI's recent XQuery proposals. I'll do that as soon as I can. In the meantime Kendall Clark was kind enough to correct some inaccuracies in my earlier post, and I feel it is appropiate to give his corrections equal billing to my errors.

Objects and Relational Databases

Ben Carlyle has been rusing recently about Object-Orientation and Relational (or at least SQL) databases. I suggested that some background reading on some of the theory supporting the two worlds might be useful. As he didn't have pen and paper handy I'm blogging it.

For OO, Actor theory and the Pi-Calculus: Robin Milner, Communicating and Mobile Systems: the Pi-Calculus and Robin Milner, The Polyadic pi-Calculus: a Tutorial (1991)

For Relational Theory: Chris Date, Introduction to Database Systems, Eighth Edition and Chris Date, The Third Manifesto (1995).

Update on XQuery - RDF

As expected the DAWG has rejected Network Inferencing's proposal. Jeff Pollock has responded on the public-rdf-dawg list. While Jeff is obviously disappointed, I suspect that the dawg hasn't rejected XQuery. NI's proposal was a syntactic one, and the DAWG decided months ago to defer syntax until after the semantics are decided.

Two weeks ago I wrote a new rdf-query language - it took me about half a day. The parser was trivial, and the semantics a subset of iTql (Tucana's rdf query language implemented in Kowari). At the end of the day, syntax isn't as important as semantics.

MIML

Machine Independent Machine Language. AKA C.

Somehow I've managed to come across this acronymn twice today from independent sources. I still find it a beautifully accurate description of both C's greatest strength, and it's greatest weakness.

Still, somehow regardless of how many new languages I learn, I still seem to have a soft spot for C --- it is a remarkably elegant MIML.

Jumping the gun.

Well the Data Access Working Group (DAWG) of the W3C is working towards standardising a query language for RDF. Jeff Pollock from Network Inferencing recently posted to the DAWG mailing list Post/Attached Proposal

Therefore, NI proposes that a new requirement be considered by this group: "The query language shall have an XQuery compatible concrete language syntax."

I don't think you could make a more premature proposal. The DAWG is trying to avoid syntax issues, preferring to get the semantics right first --- a good idea. To be proposing concrete syntax requirements at this stage is surely jumping the gun. I am even more surprised to see a proposal to mandate as poor a prima-facie case as XQuery.

XML has a document centric, single-rooted, hierachial view of its data; and XQuery reflects that. RDF on the other hand is a open-world, non-rooted, cyclic directional graph-based view. It is not immediately obvious how to reconcile these two approaches; neither is it apparent that a syntax designed to query the former, will be appropriate for the latter. This becomes particularly apparent when you look at the block-and-layer diagram in Jeff's proposal pdf. The only link between the XQ Data Model, and the RDF Triples is that both are sometimes serialised as XML --- ok XML tends to be serialised as XML, but lets not quibble, RDF often isn't.

On the other hand, XQuery is itself quite a nice solution to its problem. Particularly nice is its definition of two isomorphic concrete grammars sharing a common semantic model. I would have absolutely not problem with discovering that XQuery can be married with the semantics required by an RDF query language, in fact that would be great. Still I would like to see the DAWG finalise the required semantics first.

I would be concerned if XQuery was even considered desirable at this stage, let alone a requirement.

When is an infinite loop not an infinite loop?

When it's body takes enough time that the transaction times out before the stack overflows.

This of course was aggrivated by the fact that everytime I identified precisely when the transaction was marked for rollback, it was iterating over a Tuples. This isn't surprising given we spend alot of our time iterating over Tuples. Not that that occurred to me until after I found the bug. Hence I spent all of yesterday looking inside the TuplesOperations and half a dozen Tuples subclasses.

Yesterday was definately the most fustrating days I've had in some time.

UML Editors

Sometimes all you want to do is draw a diagram. I have periodically wanted a simple UML editor to allow me to produce diagrams to help explain the occasionally complicated class and message structures periodically required by the OO paradigm. UML does a good job of providing a vocabulary to support such informal, explainatory diagrams. Unfortunately UML comes from a high-ceremony community that inspired and supports RUP, Rational Rose, and is currently pursuing executable UML and MDA with a vengence. Hence every UML product I have been able to find is either a high-ceremony UML based IDE (ie. ArgoUML, Rational Rose), or an extension to a traditional charting program (ie. Visio, Dia). All of them suck if all you want is to quickly draw a single sequence diagram to enhance some documentation; Visio even manages the worst of both worlds, by trying to play the pseudo-ide game while retaining the lack of structured assistance of your charting programs.

Why mention this? Because I have finally found a UML program that is probably close-enough that I can live with it's short-comings; and shows sufficient promise that I might even be convinced it's worth contributing to.

So I would like to recommend that the next time you want to throw together a quick UML diagram, you check out Violet.

Continuations.

I wrote these a while back, and I make reference to them occasionally. Now I have a blog, I should probably blog them properly.

Continuation Passing Style in Java

Continuation Passing Style in C

One of these days I'll actually get around to setting up my own wiki :).

Worthwhile languages.

There are literally thousands of computer languages, and several paradigms. Here's a few languages I consider worth looking at. Languages I know, use, and admire:

C - Some people describe this as portable assembly. They are right. C feels remarkably close to the ideal minimal abstraction from the concerns of computer architecture. I can't think of a good programmer who dosn't know C well, there is a good reason for this.

Python - Possibly the most pleasant language I know. Also by far the easiest language I know of to teach to absolute beginners. Python has the advantage of supporting both imperative, functional, and object-oriented paradigms. However it's best feature is its truely remarkable community. I am unaware of any community that has such a healthy focus on usability, readability, and statistics-driven optimisation. I don't do much python programming anymore, but I still enjoy reading the community.

Scheme - Take one very powerful language; add very simple syntax; mixin safe syntactic closure and you get scheme. Hence it is widely used in the language research community, where people are understandably more interested in the power and facilities of their language than popularity.

Languages I know, want to use, and admire:

Erlang - One of the nicest languages I've come across. Scalable, safe concurrency, with pattern matching, and a whole gamult of features supporting fault-tolerant computing all the way down to low-level wire-protocol work.

Haskell - This is a language for thinking outside the box. Lazy, pure-functional, static-strong typing, advanced HM type inferencing, monads, arrows, the list goes on. If you have only ever done imperative procedual or object-oriented code (read java, C, C++, smalltalk, python, perl, etc) learn the exceptions to most of the rules you have osmosed.

SML/OCaml; Clean, elegant, safe, and fast! What's not to like about ML? Yes you can pick a single metric on which your language of choice wins against ML, but you'll be hard pressed to find two.

Yes, I recognise the distinct lack of logic and constraint languages in this list so I'll just point at two I have been recommended but haven't found time to investigate sufficiently to add to the list above: Mercury, Mozart, and one that looks very promising Paul Reppy's Moby.

An impressive rant.

I mentioned this amusing rant to Steve last friday night, and promised to provide a link. I'm just going to assume that blogging it counts as fulfilling that promise :). I came across this on the c2 wiki, it is probably the most impressive and entertaining anti-C++ rant I've ever read.

Erik Naggum on C++

C++ is philosophically and cognitively unsound as it forces a violation of all known epistemological processes on the programmer. as a language, it requires you to specify in great detail what you do not know in order to obtain the experience necessary to learn it. C++ has taken premature optimization to the level of divine edict since it _cannot_ be vague in the way the state of the system necessarily is.

C++ is a language strongly optimized for liars and people who go by guesswork and ignorance.

C++ turns otherwise good people into paranoid, insecure prostitutes, and it comes from creating such horrible living environments for themselves and compounded by trying to explain to themselves that "it's OK, really".

Database Abstraction Layers.

Interesting post on lambda regarding database abstraction layers. For quite a while I have been wondering about clean ways to provide persistency in modern languages. Specifically you want to provide:

• Persistence
• Integrity
• Closure

I dicuss these issues later, but for now the link to the existing discussion

Database Abstraction Layers and Programming Languages

Mnemosyne, the best persistence/query/language integration attempt I am personally aware of.

A very cute use for egrep.

Local UUG is currently in the midst of a cascade on funky shell tricks; I found this one from Russell Stuart, particularly cool.

tr "[:print:]" "[x*]" < FILE | egrep -vno '^(..+)\1+$'

[H-CHAT] What's your top three shell tricks?

The thread explains what it does, and I would probably replace the .'s in the egrep pattern with x's; still very cute.

It can also provide a good example of when cs theory can occasionally be useful: Given the provided solution uses a gnu-extensions to regex(7), can this be done with a pure POSIX regular expression?

Programming Language Pragmatics

Programming Language Pragmatics
Michael Scott; Morgan Kaufmann; 1-55860-442-1

I recently finished reading this and thought I should provide a review as it is a truely remarkable book. Fundamentally the book is an informal survey of the various fields of computer science and engineering that impact the design and implementation of programming languages, their interpreters, and compilers --- and it succeeds admirably. Specifically the chapters include:

1. Introduction
2. Programming Language Syntax. (FA/PDA's; regular expressions; context-free grammars; LL/LR parsers, including one of the clearest descriptions of LR parsing I have come across.)
3. Names, Scopes, and Bindings. (Value lifetime; garbage collection; different scoping rules; different implementation approaches to scoping.)
4. Semantic Analysis. (Attribute grammars; attribute flow. While well written, I personally found this one of the weaker chapters.)
5. Assembly-Level Computer Architecture. (Effectively a one chapter synopsis of Hennersey and Patterson.)
6. Control Flow. (Selection; Iteration; Recursion; and Non-determinisim)
7. Data Types. (Static and Dynamic checking; discussion of implementation; A short discussion of HM-style type inference; as well as discussions on the particular issues associated with Records, Arrays, Pointers, Lists, and IO.)
8. Subroutines and Control Abstraction. (Calling sequences and conventions; call-stack/tree management; exceptions - including continuations; coroutines.)
9. Building a running program. (Compiler backends; intermediate code; register allocation; linking - including dynamic linking and pic.)
10. Data Abstraction and Object Orientation. (OOP, including semantics and implementation concerns of encapsulation; inheritance; finalisation; polymorphism. All discusses with reference to a multitude of different languages and approaches to OOP).
11. Nonimperative Programming Models: Functional and Logic Languages. (Split into two sections, one on functional and one on logic programming. Of particular interest are introductions to both the lambda and first-order predicate calculi; and discussions on the advantages these mathmatical groundings provide programmers).
12. Concurrency. (Background; Theory; Shared-memory; and Message-Passing. A very impressive introduction to concurrency.)
13. Code Improvement. (By necessity of space, a very limited introduction to code optimisation. Still it manages to cover a reasonable amount of ground, although I would have liked more discussion on cache optimisation techniques. Peephole Optimisation; Global Redundancy; Data Flow Analysis; Loop Invariants and Unrolling; Instruction Scheduling; Register Allocation).

Given the breadth of the coverage, the reader will require additional reading to gain any appreciable capacity in any specific area. However this book does provide a very reasonable introduction to areas that will provide much needed context when approaching any more focused work. It's not going to replace the Dragon Book, but it will make the Dragon Book far more approachable, and I wish I had read PLP before I had to wade my way through the much less approachable prose of Aho, Sethi and Ullman. Similarly, the reader is still going to want to read Patterson and Hennersey. However the discussions of language semantics and their associated demands on computer architecture will answer many questions of motivation given short treatment in the more advanced work.

In conclusion, I would highly recommend this to any programmer who has experience in only one or two languages; any undergraduate wanting to broaden their understanding of programming; any professional wanting to learn more about compiler/interpreter/parser theory and implementation and wants context for the more focuses works in this field.

5-stars.

Domain Specific Languages

I came across this article on Lambda by Simon Johnston on DSL's. He takes two examples from the world of art, and asks that we consider possible parallels in software.

1. My son and I recently read a book on Leonardo da Vinci (great link), in particular looking at the way Leonardo’s work contained a great body of work from very rough sketches to beautiful and complete works of art. Explaining how artists start with rough pencil sketches, refining the lines, the perspective and then move onto oil to complete was a particularly interesting discussion. 2. I know there are many analogies that we in computer science draw between our world and that of construction – here’s another. Look at how buildings are really constructed, the architect does not build blue prints, they draw or make a model of the envisioned building (some of these drawings have become as well known as the actual buildings themselves). For example, Frank Lloyd Wright’s Fallingwater started with a truly beautiful drawing that sold the client. Then followed floor plans and blueprints. Only then did wiring diagrams, plumbing details and specific engineering drawings for features such as the cantilevered balconies complete the story.

Simon then goes on to state his position:

My position is that the creation of domain specific languages that do not seamlessly support the ability to transform information along the refinement scale are not helpful to us. So, for example, a component designer that is a stand alone tool unconnected to the class designer that provides the next logical level of refinement (classes being used to construct components) is a pot hole in the road from concept to actual implementation. Now, this is not as I have said to indicate that domain specific languages are bad, just that many of us in this industry love to create new languages be they graphical, textual or conceptual. We have to beware of the tendency to build these disjoint languages that force the user to keep stopping and jumping across another gap.

I couldn't read this and not immediately be struck by Paul Graham's reflections on creating what became Yahoo Store, specifically his comments regarding lisp. Writing this it also occurred to me that RMS's comment in Why you should not use Tcl is also appropriate:

The principal lesson of Emacs is that a language for extensions should not be a mere "extension language". It should be a real programming language, designed for writing and maintaining substantial programs. Because people will want to do that! Extensions are often large, complex programs in their own right, and the people who write them deserve the same facilities that other programmers rely on.

...which can only apply doubly for applications written in a DSL.

It also brings to mind the miriad of embedded dsl's spawned by the Haskell community though their wholesale adoption and exploitation of monads (and more recently arrows).

It only reinforces my increasing belief that the biggest gap in many popular modern languages is the lack of syntactic closure; the ability to introduce new syntatic support for a feature that becomes a first-class citizen of your programming environment.

...but at least it's done.

In the original, memory based, version of tks queryies returned answers; and answers had a method getRowCount() which did exactly that. The problem with that is that memory dosn't scale as well as disk does. So we moved to a disk backed architecture. Now when you are memory based, you want to release your memory as soon as possible, so you want to resolve (and subsequently release) any intermediate results immediately. Once you are backed by disk, you have much better uses for memory than storing an answer the user isn't using yet, so you want to evaluate your query as lazilly as possible. Hence Kowari/TKS has this concept of a Tuples, which is a thunked, localised, intermediate result. This gets wrapped in an Answer object, which is returned to the user, and resolves the Tuples by need.

The problem is that calculating an accurate row count becomes a potentially expensive operation; you can generally only afford an upper-bound instead. So unfortunately while the semantics changed, the name stayed the same, to the general confusion of all.

Subsequentely I have spent the past 2.5 days reverting the semantics, and introducing new methods to access the upper-bound (and cardinality). Tedious work, but at least it's done.

Now on to getting resolvers to play nicely with transactions.

"So, what do you do for a living?"

Like most people I am forever being asked to explain what I do for a living. Answering that question got harder when I started my current job.

My last job was with a company called Braintree, who make world class communication gateways --- mainly for the eftpos and financial industry. So I could always answer "I help design boxes to connect old EFTPOS machines to the bank using new technologies". It glosses over a lot, is largely incomplete, but remains something most people could comprehend. The worst job I've had to try and explain was my first. "I am writing the user-interface to an Electron Paramagnetic Resonance simulation"? I've seen geeks eyes glaze over on that one :).

So far for my current job I've had to revert to the classic "I'm a programmer in an IT company", which is sufficiently devoid of information to be mutually unsatisfying. So what am I currently working on? I am employed by Tucana Technologies to work on an open-source RDF database Kowari. Kowari is used by Tucana as the base on which we build our enterprise rdf-datastore TKS. OTOH, if having difficuty explaining my job is the price to pay for having this much fun I suppose it's worth it. Tucana is a great company to work for, and Kowari is really fun engineering. Still, if anyone can think of a one or two sentence description that isn't quite as insipid I would appreciate it.

Once more with feeling...

Well not an auspicious start for blogger. I posted a short note last night, mainly to avoid leaving an empty blog. Somehow blogger has managed to lose it.

Let us start with my morning reading:

• Lambda The Ultimate - Probably the premiere blog on the topic of computer languages; their design, semantics, and implementation.
• Squawks of the Parrot - The blog of Dan Suglaski, the lead developer on parrot --- the new perl-6 vm.
• About Kim - Another blog. Kim's posts invariably betray a striking intelligence; are always thought provoking; and periodically on programming language topics.
• Groklaw - Because even geeks need soap-opera sometimes.
• Irregular Web Comic - There are other web comics I enjoy, but this has rapidly become my favourate.