Etymon

Reading a File to a String in one line in Java

2010-05-19T09:36:00.002+10:00

http://weblogs.java.net/blog/pat/archive/2004/10/stupid_scanner_1.html

String text = new Scanner(new File("poem.txt")).useDelimiter("\\A").next();

JRuby and JNI and OS X.

2009-11-25T09:59:00.008+10:00

Like practically everyone I sat down a few years back and picked up enough Ruby to write an address-book app in Rails. Nice enough language, a few nice features[0]. Still at the end of the day... YADTL, so ultimately YAWN[1].

All this is to say that I found myself yesterday facing the need to convert a trivial rails app into a java servlet, with the added complication that it uses a third-party C++ library to do the bulk of the work.

JRuby is a trivial install, and the application in question didn't make use of continuations, so rip out all the Rails code, and replace with a simple loop that takes requests from the cmdline instead of a POST parameter, and we're in business.

Well up to the point where it falls over because it needs the C++ library. Here's the first real hurdle. Apple's JDK for OS X is compiled as a 64-bit binary which can't link against 32-bit libraries[2], and by default the C compiler only produces 32-bit libraries.

$ file /usr/local/lib/libcrfpp.dylib 
/usr/local/lib/libcrfpp.dylib: Mach-O dynamically linked shared library i386

A quick check on google yields these pages that suggest that I need to add -arch i386 -arch x86_64 to the CXXFLAGS and LDFLAGS. So after modifying the Makefile to compile the library with the above flags and install it in /opt/local we have:

$ file /opt/local/lib/libcrfpp.dylib 
/opt/local/lib/libcrfpp.dylib: Mach-O universal binary with 2 architectures
/opt/local/lib/libcrfpp.dylib (for architecture i386): Mach-O dynamically linked shared library i386
/opt/local/lib/libcrfpp.dylib (for architecture x86_64): Mach-O 64-bit dynamically linked shared library x86_64

Then we need to compile the SWIG generated JNI wrapper, which will also require the above parameters, but also needs to link against Apples JNI installation. Back to Google which provides this page from Apple that describes how to compile JNI on Darwin, which provides the include path and an additional link flag.

The command lines to compile the wrapper in question becomes:

g++ -arch i386 -arch x86_64 -c -I/System/Library/Frameworks/JavaVM.framework/Headers CRFPP_wrap.cxx
g++ -arch i386 -arch x86_64 -dynamiclib -L/opt/local/lib -lcrfpp -o libCRFPP.jnilib CRFPP_wrap.o -framework JavaVM

Wanting to avoid calling System.loadLibrary from ruby code I wrote a quick wrapper class that could make the call in a static block:

package crfppwrapper;

import org.chasen.crfpp.Tagger;

public class CRFPP {
    public static Tagger newTagger(String args) {
        return new Tagger(args);
    }

    static {
        System.loadLibrary("CRFPP");
    }
}

Finally modify the relevant ruby file to link to the jar file:

require 'java'
require 'lib/CRFPP-0.53.jar'

and call the wrapper:

crfppwrapper.CRFPP.newTagger("...");

Finally modify the toplevel jruby script to pass the necessary java parameters to the jvm:

#!/usr/bin/env jruby -J-Djava.library.path=/opt/local/lib -J-cp .:lib/CRFPP-0.53.jar -w

And it worked. No more Rails; migrated to jruby; and ready to bundle into a trivial servlet that will reintroduce the POST parameter to the mix.

[0] The implicit closure parameter to every function and an elegant brace syntax for creating the closures themselves does lend itself to some wonderfully elegant idioms.

[1] Of course if you were coming from J2EE you were probably more than happy to exchange static-typing for configuration-by-convention.

[2] And all of a sudden I'm having flashbacks to horror of IRIX binary toolchain management in the late 90's.

ldd equivalent under Darwin (OS X)

2009-09-08T10:44:00.003+10:00

ldd is an incredibly useful command under linux. It lists the shared-libraries required by an executable, and exactly which .so file each dependency is currently resolved to.

A similarly useful tool is od, which permits inspection of object files, especially executable and shared-libraries, extracting things like the string-table, symbol-table, and various headers and sections.

Under Darwin these tools are combined in otool. ldd can be duplicated by otool -L.

Gov2.0 and Open-Source - a response

2009-08-26T14:25:00.004+10:00

Cross-posted from Data.gov and lessons from the open-source world at the Gov2.0 Taskforce blog.

My biggest worry is that the government's response to this initiative will be the announcement of some $multi-million grand-gesture. Big press-conference; Minister announcing the 'grand vision'; and the possible benefits we could see, lost in the maze that is large-scale government procurement.

The key insight of CatB is the extent to which redundancy is a benefit in exploratory development.

For the moment, we have no idea of the correct model for Gov2.0 - we have some understanding of what has worked outside of government, and a few promising avenues of approach, but no actual answers.

So I think we want to recommend that different Agencies experiment with different approaches and that the OIC be tasked with:

Examining the success/failure of the different attempts, and eventually start to help agencies improve the success rate.
Ensuring that the legal and regulatory requirements for aggregation and interoperability of/between these different services is standardised, as these are the issues that will derail bazaar development.
Acting as a central clearing house where agencies/organisations/individuals can choose to self-publish interface descriptions, custom schema, metadata element schemes, vocabularies etc
Providing a collaboration and mediation service to allow the reconciliation of conflicting interface/schema/scheme/vocab's.

The result would hopefully be a myriad of exploratory projects, some of which would fail, most of which would be ho-hum, but many of which would succeed.

The OIC would act as an institutional memory, learning and recording the lessons learnt; an institutional coordinator, making sure that people wanting to aggregate/integrate the different data-sources aren't forbidden from doing so; and an institutional mediator, assisting the different projects in finding and working together when they would like to.

Please post any comments to the gov2.0 site listed above, not here

Google’s new OS could hit Microsoft where it hurts

2009-07-13T09:45:00.002+10:00

Quoted in a blog post by Andy Goldberg, Andy provides a quote that I suspect a lot of Microsoft sycophants will be telling themselves over the next year:

"Google may or may not have the experience and capability of actually producing an operating system and getting it deployed," he said. "It may not realise how hard it is."

Anyone who takes this line should remind themselves: Chrome OS is not an operating system! - it is browser-based windowing system running on top of an open-source OS; and Google can definitely handle that. Moreover, google has spent the better part of the past decade doing OS design and implementation. It's just that they haven't been selling it, they have been using it internally.

How to Write an Equality Method in Java

2009-07-10T14:33:00.002+10:00

Martin Odersky, Lex Spoon, and Bill Venners have written an article on How to Write an Equality Method in Java. Given the amount of traffic my post on the same topic has attracted, I thought I might take a look. Their solution is the best I have seen, and well worth a look, but the article suffers the same problem as every article I've read on this topic: it fails to properly define equals().

A Java equals() method should implement a test for bisimulation.

To me, the remarkable thing about the Artima article is that it provides and example where the traditional getClass() approach I have previously recommended fails to implement bisimulation. The good-news is that this is a rather artificial use-case, and as such isn't going to be causing many bugs. The bad-news is that the fix requires a helper method defined at the topmost concrete class, and the need for it isn't intuitive.

Anyway, if you program in Java you need to read and understand this article.

Scala and Various Things.

2009-07-02T15:30:00.004+10:00

Not quite ready to move across yet - however capturing some links to make life that little bit easier when I do. I'm hoping these approaches will work as well for Elmo/OTM as they do for Hibernate.

I'll be updating this with any more links I want to save for a sunny day.

A couple more links worthy of rereading:

Looking for JSON, ReST, (and in-memory RDF) frameworks

2009-06-17T15:20:00.003+10:00

Currently writing a number of small web-services to do various informatics tasks (more detailed post to come). Fortunately I'm not the one having to deal with 3rd-party SOAP apis! Still I do need to do various XML and JSON parsing, and not having addressed the latter before I've gone looking for libraries.

Currently I am about to start using Jackson, but was wondering if anyone had any warnings, advice, or recommended alternatives? In the course of looking at what was out there I have also come across Restlet, a ReST framework that seems like it is well worth the time to figure out and deploy, so I will probably be doing that soon as well, any warnings or advice on this will be welcome.

One of the nice things about Restlet is its support for RDF. Granted it doesn't support querying, and the terminology in the interface is a bit confused, but it does use its native Resource interface for URIRefs, so it should integrate well. OTOH, if it does prove useful as a ReST framework, I can see myself writing a quick Sesame or Mulgara extension, as there is only so much you can do with RDF before you need a query and/or data-binding interface.

Deploying to tomcat using maven

2009-06-04T15:13:00.003+10:00

This is a note to capture the process I am currently using to build and deploy a basic web application to tomcat for development.

Create simple web app using archetype.

mvn archetype:create ... -DarchetypeArtifactId=maven-archetype-webapp

Add server to ~/.m2/settings.xml

  <servers>
    <server>
      <id>local-tomcat</id>
      <username>username</username>
      <password>password</password>
    </server>
  </servers>

Add server to toplevel pom.xml

  <build>
    ...
    <plugins>
      <plugin>
        <groupId>org.codehaus.mojo</groupId>
        <artifactId>tomcat-maven-plugin</artifactId>
        <version>1.0-beta-1</version>
        <configuration>
          <server>local-tomcat</server>
        </configuration>
      </plugin>
    </plugins>
  </build>

compile, test, deploy, and subsequently redeploy

  $ mvn compile
  $ mvn test
  $ mvn tomcat:deploy
  $ mvn tomcat:redeploy

Of course what I would dearly love to know is how you configure a server url in the settings.xml file. The documentation I can find (http://mojo.codehaus.org/tomcat-maven-plugin/configuration.html) describes how to use a custom url, and how to configure authentication information. What it doesn't do is explain how you can do both at the same time, and all my attempts have resulted in XML validation errors when trying to run maven --- if I figure it out I'll update this post.

ANTLR: an exercise in pain.

2009-05-27T10:01:00.002+10:00

Ok, so for my current project I need to either build heuristic or machine learning based fuzzy parser. As someone who has written numerous standard parsers before, this qualifies as interesting. Current approaches I'm considering include cascading concrete grammars; stochastic context-free grammars; and various forms of hidden-markov-model based recognisers. Whatever approach ends up working best, the first stage for all is a scanner.

So I start building a jflex lexer, and make reasonable progress when I find out that we are already using ANTLR for other projects, so I should probably use it as well. Having experienced mulgara's peak of 5 different parser generators - this does eventually become ridiculous - I was more than willing to use ANTLR. Yes it's LL, and yes I have previously discussed my preference for LR; but, it does support attaching semantic actions to productions, so my primary requirement of a parser-generator is met; and anyway, it has an excellent reputation, and a substantial active community.

What I am now stunned by, is just how bad the documentation can be for such a popular tool. One almost non-existent wiki; a FAQ; and a woefully incomplete doxygen dump, does not substitute for a reference. ANTLR has worse documentation than sablecc had when it consisted of an appendix to a masters thesis!

My conclusion: If you have any choice don't use ANTLR. For Java: if you must use LL I currently recommend JavaCC; if you can use an LALR parser do so, my current preference is Beaver.

So why can't google provide html for 40% of pdfs?

2008-05-19T19:38:00.002+10:00

A google search for opensource filetype:pdf returns the standard 10 results on the front page, but only 6 of them offer a "View as HTML" link. Is it just me, or has this become more prevalent recently? And what is the common property that results in this behaviour?

If anyone has any clues or ideas I would love to hear them.

Now this is how conference videos should be presented

2008-01-15T10:40:00.000+10:00

A great collection of conference presentations and interviews (mostly on java topics) Parleys - but of particular interest to me is the presentation, the best I have seen.

How to start thinking about RDF.

2007-11-29T16:27:00.000+10:00

While trying to understand RDF, its capabilities and its limitations I have done a lot of reading of earlier work on semi-structured data management. It occurs to me that I haven't blogged a paragraph from an 1995 paper on heterogeneous information sources that really crystalised for me the crucial difference between RDF and previous attempts at semi-structured data (especially XML and friends) - better late than never I suppose...

We need note define in advance the structure of an object ... no notion of a fixed schema or object class. A label can play two roles: identifying an object (component) and identifying the meaning of an object (component). If an information source exports objects with a particular label, then we assume that the source can answer the question "What does this label mean?". It is particularly important to note that labels are relative to the source that exports them. That is, we do not expect labels to be drawn from an ontology shared by all information sources.

Papakonstantinou, Y. et al. "Object Exchange Across Heterogeneous Information Sources", 11th Conference on Data Engineering, IEEE Computer Society, 251-260, 1995.

The actual framework presented in the paper is focused on intraorganisational integration and so doesn't have the property of anarchic scalability required if it is to be applied to the internet - however it does express clearly this need for source-defined semantics if semi-structured data is to be tractable.

Implementing a Resource Manger for the Java Transaction API.

2007-10-17T15:03:00.000+10:00

One would hope that when an organisation like Sun specifies a standard as important as a transaction api they might take the time to ensure they do a reasonable effort -- unfortunately you would be wrong. The JTA specification is freely available from Sun, however the document is extremely vague and requires the reader to infer the underlying transaction state machine - with the unsurprising result that the corner cases are left completely unspecified. So having waded through this morass myself, I include here my advice on what you need to do to understand JTA, in the hope that anyone else coming to this standard won't have to waste as much time as I have understanding it.

Read the JTA spec last. JTA is a little more than a thin wrapper around the Object Transaction Service 1.1 published by the OMG. This is one of the CORBA standards published in the late 90's and early 2000's - and like most of the early CORBA specs, it is well written; easy to read; and pretty complete. Unfortunately it too leaves the underlying state-machine and some of the corner-cases (especially those to do with recovery) underspecified. As a result I recommend printing this out and referring to it as an adjunct to the JTA spec.

Fortunately the CORBA-OTS is itself an object-oriented wrapper around another spec, the Distributed Transaction Processing: The XA Specification spec' published by X/Open (now The Open Group). There in Chapter 2 you will find most of the definitions missing from the other two specs; and in Chapter 6 the state-tables that provide definitive semantics for the various operations you will need to implement. You will also find a reference to another related X/Open specification - Distributed Transaction Processing: Reference Model - which contains all the remaining definitions and assumptions missing from the the JTA/OTS specs.

So if you do need to implement a JTA interface I strongly recommend you start with the X/Open reference model; then read the X/Open XA Spec; and only then read the JTA specification alongside the OTS spec for elaboration.

Model-URI/URL Use-cases and Requirements and Proposal

2007-09-19T22:01:00.000+10:00

Just posted this to mulgara-general - posting here to provide readily accessible permanent reference. I would greatly appreciate any comments anyone may have - please also feel free to solicit comments from outside the mulgara community if there is interest.

The Use Cases and Requirements
The three key requirements of a model-URI proposal are:

1. Protocol/Scheme independence
2. Model/Server mobility
3. URI-standards compliance (ie. no fragment)

Also desirable are

4. Unique-name
5. Namespaced to allow a) potential resolution; b) predicable, human-readable URI's.

The context of the most complex use-case involves 4 models and 4 machines (and assumes a Distributed or Federated Resolver)

:modelA is on server1 on host1 and needs 
     to reference :modelB and :modelC
:modelB is on server2 on host2
:modelC is on server3 on host3
:modelD is on server4 on host4 run by an unrelated organisation

The application needs to perform the query:

select $id subquery(
  select $s $p $o 
  where $s $p $o in $locn and 
        $id <mulgara:locatedAt> $locn in <mulgara:modelURLResolver>)
from host1:modelA
where [ <:useModel> $identifier ] ;

Which queries each model listed in :modelA after converting their identifier into a URL via a posited resolution mechanism.

Now host2 fails, and we restore server2 on host3 to run alongside server3.

We would like to be able to have the query run unmodified.

What this means is that :modelB cannot encode host2 in its URI.

The URI does need to encode some sort of server-id as servers are guaranteed to use the same model-names at least some of the time (consider all system-model's have the name "").

Also because :modelD and :modelA-C are managed by unrelated organisations we must somehow encode the organisation in the model's URI-stem as they may well decide to use the same server-id ("server1" or "database" anyone?).

Also consider that any encoding of the organisation must also allow that organisation to maintain their own independent registry, or the proposal ceases to be scale-free (it's on this that the original UUID proposal floundered).

I have considered abandoning requirement 4, and just using URL's. However ultimately we require a canonical name for internal purposes (even if it isn't exposed externally), and so even using URL's we would have to pick a designated 'unique name' for the model - we can't escape that - so we might as well save ourselves the headache and make it unambiguous.

So a summary of my thinking on the use-cases/requirements for rdf model-names - we desire:

1. Unambiguously an identifier
2. Encodes organisation
3. Encodes server-id
4. Doesn't encode hostname
5. Potentially resolvable via a per-organisation registry

* Proposal

If we wish to be unambiguous then we should use our own URI-scheme. This has the added benefit that once we use our own scheme we have a lot more flexibility regarding how we structure the rest of the URI to meet our requirements.

I am proposing to use the scheme 'rdfdb' - as did the original UUID proposal.

I would prefer to avoid the use of opaque URI's; there is no reason why our URI can't be introspected if we structure it sanely - so the structure according to RFC2396 will be 'rdfdb://authority/path'.

Logically the model-name itself makes a good path so we arrive at 'rdfdb://authority/modelName'. Leaving the need to encode an organisation and a server-id in the authority in a fashion that will potentially permit resolution via a registry.

Now as the authority is not a hostname, RFC2396 identifies us as a "Registry-based Naming Authority". As such, the characters we have permitted to us are [ - _ . ! ~ * ' ( ) $ , ; : @ & = + ] (excluding the []'s) - and the characters reserved are [ ? / ].

I therefore propose to structure the authority 'server-id~organisation-id' (that is the server-id and org-id separated by a tilde).

At the moment we don't support hierarchical server-id's; but I would like to leave us the option of doing so once we start supporting more aggressive distribution. We also need to consider that it needs to remain a valid path-element for use in our existing model-URL's. So for now I would like to limit server-id to what we currently use, but ultimately I think we should consider some sort of delimited hierarchical form (probably dotted).

The organisation-id should be something that will eventually permit the identification of a registry. For now a dotted hierarchical form should suffice - although I will make sure the implementation leaves this as open as possible (the use of a tilde makes this possible).

It has also been suggested that to make it unambiguously clear we are *not* encoding a hostname as the organisation-id we should invert the traditional dns-style representation.

So putting all the pieces together: If I am running a mulgara server -

host:         pneuma.netymon.com
organisation: netymon.com
server-id:    rdfDatabase
model-name:   addressBook

The model URL for addressBook remains: rmi://pneuma.netymon.com/rdfDatabase#addressBook
or: soap://pneuma.netymon.com/rdfDatabase#addressBook ...etc...

and the model URL for the model is: rdfdb://rdfDatabase~com.netymon/addressBook

Operational vs. Denotational Semantics

2007-09-17T20:48:00.001+10:00

Spent a little time this afternoon discussing several topics with LB and SR. One topic we touched on was our continuing efforts to understand the distinction between denotational and operational semantics - I continue to be surprised at just how hard it's proving to nail down the precise distinction.

Looking at the various scrawls on my whiteboard that are the only physical remnants of what was a fascinating discussion, I gave some more thought to the distinction, and I believe it can be described thus:

Operational : M ( P ) |= σ -> σ'
Denotational : M ( P ) |= κ -> P'

ie. In Operational semantics the meaning of a program is a transition function on a virtual machine.
in Denotational semantics the meaning of a program is a mapping from an initial basis to a new (simplified) program.

Now this is confused by most operational semantics being "small-step", where the meaning is defined via structural recursion on the abstract grammar:

M ( ρ ) |- σ -> M (ρ') σ' { the meaning of an AST production is a transition function from an initial VM state to the meaning of a (simplified) production applied to a new VM state. }

Which end up looking very similar to denotational semantics as denotational semantics are normally defined via structural recursion.

But even for the similarity there remains the core distinction (as I understand it) - Denotational Semantics are defined in terms of a reduction-semantics from program+basis to a simplified program (although normally a program in a different, mathematically tractable language such as the lambda-calculus) whereas Operational Semantics are defined in terms of a transition-semantics from a program+initial-state to a new state (although normally a state extended with function-values defined in a mathematically tractable language such as the lambda-calculus).

Now of course Interpreter Semantics is a whole different kettle of fish, and of course leaves you facing the 'turtle problem' - you can try for 'turtles all the way down' if you like, but once you hit the metal you've pretty much lost the point of a semantics in the first place. I must admit admiring the way ECMAscript handled it - an interpreter semantics in SML, which has an operational semantics of its own avoiding the problem.

RDF, Document Repositories

2007-08-30T17:23:00.000+10:00

I have recently had several discussions with people working on/with various document repository projects. One thing I hear is the increasing understanding of the importance of semantics in repository metadata management. I'm naturally pleased to see this because storage, query, and management of semantics is precisely where projects like mulgara come in.

Now digital repositories are alot more than just a semantic store, there are also issues associated with the actual document storage, retrieval, and the QA, workflow, and various metadata extraction tasks. However these days most repository projects include some sort of semantic store to manage metadata, and the question is reasonably asked - why not just use that?

The reason I recommend considering using mulgara to augment a document repository is due to the additional flexibility gained by doing so. When a repository developer approaches the metadata problem they have a natural tendency to view adopt an 'instance-focused' view of metadata. This is where the focus is on the 'document', where each document is of a given 'document type', and each 'document type' implies corresponding 'attributes'. In contrast, RDF is 'property-focused' --- where the focus is on defining the 'meaning' of 'properties', and a 'document' having a given property 'classifies' the document as belonging to a given 'class of documents'.

While the two are duals they do influence design. If you are taking an instance-focused approach you will find yourself heading towards document-type hierarchies and defined attribute lists. If you take a property-focused approach you will find yourself defining lexicons and ontologies. The former tends towards relational approaches, the latter towards semantic approaches such as RDF. The reason why I believe the semantic approach to be superior is in its flexibility. Hierarchies are predicated on centralised control. Even if you can maintain central control over the document type definitions and their attributes, the very act of standardisation in this manner leaves your project with the unfortunate choice of 'scale' or 'responsive to change'.

RDF and its related standards allow the decentralisation of attribute/property definition, while providing the tools to manage the resulting 'mess'. With the combination of namespaces, RDFS, and assuming the provision of schema repositories, it becomes possible to allow global use and reuse of locally defined 'models'. This is especially relevant when you consider that 'local' should be considered in both temporal and spatial senses - keeping the system responsive both to the differing needs of independent organisations, and the changing requirements of a single entity.

The result is the need for two additional boxes in your architecture diagram. The first, a vocabulary server that allows users to define their own vocabulary extensions, and makes those definitions available to applications and critically capable of management and eventual rationalisation. The second is a metadata server that can store the resulting data and permit ad-hoc querying by applications, and the inferencing required by vocabulary rationalisation. One of the reasons mulgara exists is to provide the storage and query engine required by these components - and so I do enjoy having the chance to talk to people about it.

The Effect of File Sharing on Record Sales: An Empirical Analysis

2007-02-14T13:22:00.000+10:00

Felix Oberholzer-Gee Harvard University and Koleman Strumpf University of Kansas

Abstract

For industries ranging from software to pharmaceuticals and entertainment, there is an intense debate about the appropriate level of protection for intellectual property. The Internet provides a natural crucible to assess the implications of reduced protection because it drastically lowers the cost of copying information. In this paper, we analyze whether file sharing has reduced the legal sales of music. While this question is receiving considerable attention in academia, industry, and Congress, we are the first to study the phenomenon employing data on actual downloads of music files. We match an extensive sample of downloads to U.S. sales data for a large number of albums. To establish causality, we instrument for downloads using data on international school holidays. Downloads have an effect on sales that is statistically indistinguishable from zero. Our estimates are inconsistent with claims that file sharing is the primary reason for the decline in music sales during our study period.

In the Journal of Political Economy.

Available in Volume 115, Number 1, February 2007

From Ars Technica via Lawrence Lessig

Java generics and the covariance and contravariance of arguments

2007-02-13T21:08:00.000+10:00

Well given we require 1.5 now for other reasons, and 1.5 does complain if you don't constrain generic classes I have finally bitten the bullet and started using generics. Unfortunately I just got bitten by what I suspect is going to be a very common mistake - in this case by failing to properly consider the type equivalence of parametrised method calls.

Consider the following code:

public interface TestInterface { }

public class TestClass implements TestInterface { }

import java.util.ArrayList;
import java.util.List;

public class Test {
 private List<testclass> list;

 public TestInterface test() {
   list = new ArrayList<testclass>();
   list.add(new TestClass());

   return covariant(list);
 }

 public TestInterface covariant(List<testinterface> ilist) {
   return ilist.remove(0);
 }
}

Now there is absolutely no reason why this should not work. It is trivially inferable that the above code treats ilist as covariant in the list-type - and that therefore this code is statically correct.

Of course Java's typing has never been particularly smart. List<t1>.add(T1) is contra-variant in t1, and T2 List<t2>.get(int) is co-variant in t2; so the Java compiler is correct to infer that in the general case List<t1> and List<t2> are substitutable iff t1 == t2.

If we can't declare a generic parameter to be covariant in its type parameter we have a serious problem - it means that any non-trivial algorithm involving collections is going to run afoul of this. You might consider trying to cast your way around it:

 public TestInterface test() {
   list = new ArrayList<testclass>();
   list.add(new TestClass());

   return covariant((List<testinterface>)list);
 }

but not surprisingly that didn't work.

Test.java:11: inconvertible types
found   : java.util.List<testclass>
required: java.util.List<testinterface>
 return convariant((List<testinterface>)list);
                                       ^
1 error

If you continue to hack at it you might try a double cast via a non-generic List.

 public TestInterface test() {
   list = new ArrayList<testclass>();
   list.add(new TestClass());

   return covariant((List<testinterface>)((List)list));
 }

This works but leaves us with the unchecked/unsafe operation warning:

Note: Test.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Now this is a perfectly reasonable warning - it is unchecked; it is unsafe; and more importantly it does violate encapsulation. The problem here is that the caller should not be defining the type invariants of the callee - that's the job of the method signature!

The correct solution is to allow us to declare covariant() to be covariant in its argument; and fortunately Java does support this.

To declare an argument to be covariant in its type parameter you can use the extends keyword:

 public TestInterface covariant(List<? extends TestInterface> ilist) {
   return ilist.remove(0);
 }

To declare an argument to be contravariant in its type parameter you use the super keyword:

 public void contravariant(List<? super TestClass> clist, TestClass c) {
   clist.add(c);
 }

Without these two facilities generics would be badly broken, so I am glad Sun had the presence of mind to include them - btw if you are using Java 1.5 I strongly recommend you read the Java Generics Tutorial

As an aside it is worth noting that as Java includes a Top type 'Object', List is a common covariant type - sufficiently common that Sun has included a syntactic sugar for it, List. Personally I'm not sure this was such a good idea, List would work anyway, and I think I would prefer to have kept the covariance explicit.

Update: Corrected capitalisation error in initial java example.

Five things to consider when writing a Mulgara Resolver

2007-02-06T18:11:00.000+10:00

Ended up writing a longer response than I had planned to a query about writing a resolver in Mulgara today. I'm putting it here to keep a handle to it as it does cover the basic structure of the resolve() method in reasonable detail.

First it is important to realise that resolvers *don't* return triples - they return Resolutions. These are Tuples that provide bindings for the variables in the Constraint passed to resolve(). So in the case of <http://www.example.com/path/subpath> $predicate $object the resulting Resolution should have two variables ($predicate $object). In the case of <../subpath> <http://www.schema.com#parent> $subpath it will have one ($subpath).

You should also be aware that a Resolution can be unevaluated! It is not uncommon for bindings, required to evaluate the constraint, come from other parts of the query. Consider the following where clause:

$url $p $o in <rmi://localhost/server1#sample> 
and 
<myfile> <hasurl> $url

in this case your resolver will be asked to resolve ($url $p $o), return a Resolution that will later be passed the $url in the prefix argument to beforeFirst(). Evaluation would then occur either in beforeFirst() or in the calls to next() - we prefer it to happen in beforeFirst if the memory requirement isn't unreasonable, our algorithmic reasoning assumes a comparatively cheap next().

If you require that a particular variable be bound prior to final evaluation then you need to provide a MandatoryBindingAnnotation - this indicates to the join logic that it must ensure a specific binding is satisfied by other constraints in the query before you are evaluated (in this case $url).

It is also worth noting that due to the support of intervals and the resulting interaction with query transformations, the XSDResolver is quite complicated as resolvers go. Without that a call to resolve consists of:

Obtaining the model (constraint.getModel()).
Do any preparatory work, especially any work that might be able to prove the result Empty (or a singleton).
If you can't prove the result empty (or singleton), defer further evaluation to the returned Resolution.

Then inside the Resolution you need to consider how you implement the following four key methods

MandatoryBindingAnnotation: are there any variables that *must* be bound for the deferred evaluation to terminate.
DefinablePrefixAnnotation: can you cheaply reorder the variables in the result (log n or less)
ReresolvableResolution: can you cheaply reresolve the constraint if additional information becomes available (again log n or less) [note: this will become an Annotation like the other two in the Mulgara 1.2 dev-cycle]
beforeFirst(): you can ignore the suffixTruncation arg, but you can't ignore the prefix - these *are* the values of the first N variables of the resolution - if all the variables are passed as a prefix your only decision is 1 row or 0 - but most of the time you will be passed less than this.

At this point you have either performed the evaluation, or you have setup the evaluation and deferred the rest to be done incrementally on each call to next().

next(): does whatever is required to ensure that calls to getColumnValue().

There is only one Tuple class that defers evaluation beyond this point (the implementation of count()). Naturally we don't want to go to the effort of evaluating an entire subquery until the user actually goes to use it - so we defer evaluation of the count() until the call to getColumnValue().

getColumnValue(): normally this is a matter of returning values calculated in either beforeFirst() or next() - occasionally this amounts to evaluating it but this is uncommon.

The whole point of the Resolution/Tuples/beforeFirst/next bother is to implement lazy-evaluation in java. We only scale to bignum-levels when all query evaluation is done on a call-by-need basis.

Ok now this is too cool for words.

2007-02-02T22:07:00.000+10:00

If you are a fan of Pratchett you have to checkout The Great A'Tuin as a wedding cake!

Umm, would you mind if we borrowed your DPP?

2007-01-25T10:17:00.000+10:00

from boingboing

Finally a public official has the courage to speak sense.

"London is not a battlefield. Those innocents who were murdered on July 7 2005 were not victims of war. And the men who killed them were not, as in their vanity they claimed on their ludicrous videos, 'soldiers'. They were deluded, narcissistic inadequates. They were criminals. They were fantasists. We need to be very clear about this. On the streets of London, there is no such thing as a 'war on terror', just as there can be no such thing as a 'war on drugs'. "The fight against terrorism on the streets of Britain is not a war. It is the prevention of crime, the enforcement of our laws and the winning of justice for those damaged by their infringement."

If this was the only sentiment I would applaud, but to see his respect for the rule of law gives me hope our nations can come through this intact.

"We wouldn't get far in promoting a civilising culture of respect for rights amongst and between citizens if we set about undermining fair trials in the simple pursuit of greater numbers of inevitably less safe convictions. On the contrary, it is obvious that the process of winning convictions ought to be in keeping with a consensual rule of law and not detached from it. Otherwise we sacrifice fundamental values critical to the maintenance of the rule of law - upon which everything else depends."

There is no right, no principle, no aspect of our 'way of life' that isn't completely dependent on the rule of law. Without rule of law every other guarantee, social contract, or bill of rights is moot - completely and absolutely unenforcable and thereby irrelevant.

Note to any political types who might read this: This is a vote swinger. The courage to respect and maintain rule of law in the face of fear is my definition of leadership, and what I am looking for above all when deciding my vote.

Erlang in 5 seconds.

2006-09-13T18:08:00.000+10:00

There was recently a thread on erlang-questions that discussed how you would present Erlang in 5 seconds. In an unrelated thread it is possible Richard Carlsson managed to nail it:

In most respects, Erlang _is_ a concurrent, nondestructive Lisp with a Prolog-inspired syntax that focuses on pattern matching and rules.

For my own reference he original email:

Nick Linker wrote:
I wonder why Erlang is not Lisp? I mean why inventors of Erlang chose
to create its own language instead of creating just ERTS-specific
library for LISP (or at least Scheme)?

Here are some reasons why Lisp might not be a perfect match to
the problem they wanted to solve:
 - no built-in concurrency
 - destructive updates abound (in Scheme, too)
 - no pattern matching

And if you're going to fix those things, you might as well use a syntax
that feels more comfortable to you. In particular, pattern matching
makes function definitions and selective receives much more readable,
which I assume was an important goal for the kind of industrial
applications that Erlang was created for.

In most respects, Erlang _is_ a concurrent, nondestructive Lisp with
a Prolog-inspired syntax that focuses on pattern matching and rules.

 /Richard

The Monad Laws

2006-09-13T11:26:00.000+10:00

Every now and then I come across a post that explains a concept so clearly it is inspiring. I'd like to thank Albert Lai for just such a post. Re: [Haskell-cafe] Monad laws

Deokhwan Kim  writes:
>
>What is the practical meaning of monad laws?
>
>  1. (return x) >>= f == f x
>  2. m >>= return == m
>  3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)

I offer to re-write the laws in do-notation.  (Please view with a
fixed-width (non-proportional) font.)

1. do { x' <- return x            do { f x
      ; f x'               ==        }
      }

2. do { x <- m             ==     do { m
      ; return x }                   }

3. do { y <- do { x <- m          do { x <- m
                ; f x                ; do { y <- f x
                }          ==             ; g y
      ; g y                               }
      }                              }

                                  do { x <- m
                    using 3.14       ; y <- f x
                           ==        ; g y
                                     }

I think in this notation everyone sees the laws as plain common sense.
If you do write a monad that doesn't follow some common sense, the
dire consequence (practical or theoretical) is obvious.

Just in case it is still not obvious to somebody...

When we see a program written in a form on the LHS, we expect it to do
the same thing as the corresponding RHS; and vice versa.  And in
practice, people do write like the lengthier LHS once in a while.
First example: beginners tend to write

  skip_and_get = do { unused <- getLine
                    ; line <- getLine
                    ; return line
                    }

and it would really throw off both beginners and veterans if that did
not act like (by law #2)

  skip_and_get = do { unused <- getLine
                    ; getLine
                    }

Second example: Next, you go ahead to use skip_and_get:

  main = do { answer <- skip_and_get
            ; putStrLn answer
            }

The most popular way of comprehending this program is by inlining
(whether the compiler does or not is an orthogonal issue):

  main = do { answer <- do { unused <- getLine
                           ; getLine
                           }
            ; putStrLn answer
            }

and applying law #3 so you can pretend it is

  main = do { unused <- getLine
            ; answer <- getLine
            ; putStrLn answer
            }

Law #3 is amazingly pervasive: you have always assumed it, and you
have never noticed it.  (To put it into perspective, you hardly notice
yourself breathing, but this only makes the practical meaning of
breathing more profound, not less.)

Whether compilers exploit the laws or not, you still want the laws for
your own sake, just so you can avoid pulling your hair for
counter-intuitive program behaviour that brittlely depends on how many
redundant "return"s you insert or how you nest your do-blocks.

It is also worth reading apfelmus' followup for further elaboration on the intuition behind the monad laws.

Deokhwan Kim wrote:
> But what practical problems can unsatisfying them cause? In other words,
> I wonder if declaring a instance of the Monad class but not checking it
> for monad laws may cause any problems, except for not being qualified as
> a theoretical monad?

This question is likely to be a result of an unlucky introduction to
monads where they are introduced top down: "Hear ye, a monad, this is
some mystic thing obeying the spiritual laws 1.,2. and 3.", isn't it?
It is this way that monads get the attribute "theoretical".

Asking what the practical meaning of the monad laws might be is like
asking what the practical meaning of the laws for natural number
addition could be: what does
i)  a + (b+c) == (a+b) + c mean?
How can i understand
ii)  a + 0 == a ?
What does
iii)  a + b == b + a signify?

These question are unlikely to arise because you have an intuition of
what a natural number is: a number of bullets in sack, coins in your
pocket, people in the mailing-list etc. With this knowledge, you will
most likely not have any problems explaining the laws i),ii),iii) to
somebody else and most likely you will have not doubt about *why* they
must be true.

For monads, my intuition is as following: a value of type (M a) is an
action, something producing a value of type  a  and (or by) executing a
side-effect like drawing on the screen or screwing up the hard drive.

With the operator >>=, I can execute such actions in a specific
sequence. For the sequence, it is of course unimportant how i group my
actions: i can group actions act1 and act2 first and then postpend act3,
or i can group act2 and act3 first and then prepend it with act1.

To simplify writing down a formular corresponding to this fact, we
introduce the operator >> defined by
    act1 >> act2 = act1 >>= \x -> act2
which sequences actions but for simplicity discards the computed value x
of type a. It is only the side-effect of act1 we are interested in.

Now, the thought about grouping written does as formular is just
    (act1 >> act2) >> act3  ==  act1 >> (act2 >> act3)
and this is the simplified version of law 3. Of course, we know that
this is coined "associativity".

The actual law 3 is just a formulation for >>= that takes proper care of
the intermediate calculation result x.

With  return x , we can create an action which computes the value x but
 has absolutely no side-effects.
This can also be stated in formulas, as Mr "return" explains:
1. "if i am prepended to guys doing side-effects, i give them the value
x but do not take any responsibility for side-effects happening"
   (return x) >>= (\y -> f y) ==  f x
2. "if i am postponed to an action which computes a value x, i don't do
any additional side-effects but just return the value i have been given"
   m >>= (\x -> return x)  ==  m
which is of course equivalent to
   m >>= return  ==  m

So to answer your question:
> In other words, I wonder if declaring a instance of the Monad class
> but not checking it for monad laws may cause any problems, except for not
> being qualified as a theoretical monad?
A thing you declare to be an instance of the Monad class, but one that
does not fulfill the three laws above, simply does not match the
intuition behind a monad. I.e. your definitions of (>>=) and (return)
are most likely to be void of the intended meaning.

Why I prefer LALR parsers

2006-09-01T01:34:00.000+10:00

I was asked on a mailing list why I prefer LALR to LL based parser generators. I ended up spending enough time on it to justify posting it here. Summary: "Reduced complexity in the semantic analyser is well worth the 'cost' of thinking bottom-up in the parser."

How come you prefer LALR? What about LR(k)?

I haven't really found the need for the added expressiveness of LR(k); this combined with the dearth of good GLR and LR(k) generators for many languages means that I haven't ended up using one for a project yet. When people write production generators (as opposed to experimental), they seem to be either LL(k) or yacc+.

I'm not surprised at the popularity of LL, as you say, if you're going to write your parser by hand you're going to use top-down, recursive decent - ie LL. Consequently for people coming to the problem of parsing for the first time, they are much easier to visualise, and as you point-out consequently to debug. I recently had to assist a colleague with a couple of sablecc[0] bugs that were a direct result of visualising the parse top-down, while using a bottom-up parser.

However once you've written a handful of parsers, the expressive limitations of LL(k), and the software engineering challenges top-down imposes on semantic analysis quickly teach you to appreciate LALR. Consequently I do not voluntarily use LL parsers in new projects.

I prefer LL(k) as it generates code similar to that you'd write yourself (top down parser) and that's useful when you are debugging. LL(k) is quicker :).

You're right, debugging of the parser is simpler with LL(k). That of course is beside the point, as I mentioned in my original email, the parser is the easy stage - the hard part is the semantic analysis, and LL makes this tougher. Simplifying the parser at the expense of the SA is false economy.

The added complexity derives from two places. The first derives from the additional information available with non-terminal productions in bottom-up parsers. Because bottom-up parsers reduce non-terminals after their children are fully parsed. This additional information makes using S or L-attribute grammars feasible for the first stage of SA. When working with LL I have come across three ways of dealing with this:

Don't use attribute grammars, and use gradually (ie. most of the time, partially) initialised parser-global mutable state.
Use nested parsers as accumulators.
Use a eulers walk to convert top-down into bottom-up by attaching the SA to the post-order events.

In my experience the general approach is a combination of 1 and 2 - and they both cause serious structural problems in the resulting code, which all manner of coupling and structural aliasing between the parser and the SA that complicate ongoing maintenance. 3 wastes alot of memory (although admittably that is less of a problem now), but more importantly you have thrown away the very reason you went LL(k) in the first-place - top-down parsing.

The second source of complexity is the consequence of losing access to left-recursive grammars - which has two key impacts.

Elimination of left-recursion replaces one simple rule with two coupled rules.
This elimination is achieved by converting left-recursion to right-recursion; which will always[4] convert an S-attribute grammar into an L-attribute grammar; and seriously complicate any L-attribute grammar.

This causes problems analogous to the interaction of non-associative operators with foldr.
Consider the following grammar (where n is a terminal matching {digit}+ )

E -> E - n | n

converted[1] becomes

E -> nT*
T -> - n

"10 - 5 - 3" is then parsed:

L-recursive : (((10) - 5) - 3)
R-recusive : (10 (- 5 (- 3)))

Now of course SA can evaluate the R-form correctly, it just takes more work[2]; less intuitive code[3]; greater coupling; greater complexity.

LL parsers can't handle the L-recursive grammar, LR parsers can.

Reduced complexity in the SA is well worth the 'cost' of thinking bottom-up; seriously, it's not that difficult to do.

[1] The kleene star simplifies this a bit, using e for the empty match the classic conversion is

    E -> nE'
    E' -> - nE' | e

See Aho et al for details.

[2] The L-recursive SA is a trivial S-attribute grammar defined as

E -> E' - n { E.val := E'.val - n.val }
E -> n      { E.val := n.val }

[3] In this case the L-recursive form is so trivial that the resulting R-form produces a trivial accumulator based SA. However note that even at this basic level, we have converted a simple declarative form into a recursive form that is fundamentally more complex. In cases where the L-form is naturally recursive, the resulting R-form invariably introduces mutable shared state, with it's attendant complications.

[4] I'm reasonably certain this is the case, I don't however have time to double check this. Presumably someone will correct me if I'm mistaken here.

Open Recursion: a definition.

2006-04-21T08:56:00.000+10:00

I've been asked a couple of times now about my use of "open recursion". It's covered in some detail by Pierce in "Types and Programming Languages"; I've included the one paragraph definition he gives below.

Open recursion. Another handy feature offered by most languages with objects and classes is the ability for one method body to invoke another method of the same object via a special variable called self or, in some langauges, this. The special behavior of self is that it is late-bound, allowing a method defined in one class to invoke another method that is defined later, in some subclass of the first.

Types and Programming Lanauges, Benjamin C. Pierce, 2002, MIT Press, pg 227.

What is Object-Oriented Programming

2006-04-20T10:31:00.000+10:00

Ok, so I've spent the past few days ragging on various applications of object-oriented programming. So what do I consider OOP good for? Well the answer naturally depends on what you consider OOP to be. So before I attempt to ask "What is it good for?", I will prepare the way by looking at "What is Object Oriented Programming"?

The biggest problem with giving a definition for object-oriented programming is that there are so many to choose from. Worse, the vast majority consist of little more than vague handwaving giving little or no thought to the existence of non-OO techniques. Consider the list of features listed by Johnathan Rees on Paul Graham's site.

Consider the first example. Encapsulation is not a distinguishing feature of OOP. Not only is it common in numerous non-OO languages, but it is not supported by many OO languages including both Smalltalk and Python! Moreover encapsulation is a friendly name given to existentially quantified types, which are the underlying theory used to understand Modules. Ie. when you see a feature offering encapsulation, what you are really seeing is a module/package system (possibly in disguise). Yes that does mean that Java/C#/C++ classes are doing double duty as both a type definition AND a module system. Yes that is the cause of several problems you are probably experiencing. No it doesn't have to be that way, there are languages that successfully seperate the two orthoginal concepts.

I make use of theory here because it allows me to avoid handwaving. Specifically it allows me to avoid the trap of promoting specific language features to the status of paradigm definition just because they are favoured, or even common in OOP languages. Using this approach I can quickly eliminate Encapsulation, Protection, Ad hoc Polymorphism, Parametric Polymorphism, and Sum-of-Product-of-Function from Ree's list. This leaves us with only "Everything is an object", "All you can do is send a message", Specification Inheritance, and Implementation Inheritance to consider. So lets map these to theory and see what we have left:

Everything is an object: This is literally a meaningless phrase as either it is strictly a matter of syntax (2.add(3) vs. 2 + 3); or it is a matter of purity, at which point it begs the question.
All You can do is send a message: Message Passing. You can take your pick of various algebras and calculi to model this. CSP was popular for a while; Process Algebra has its admirers; but my favourate is the pi-calculus.
Specification Inheritance: This is subtype-polymorphism using subsumption.
Implementation Inheritance: Open Recursion. Not alot of use if you don't have subtype-polymorphism as well, and proves difficult to model when you do. The simplest treatments use a least-fixed-type operator applied to a 'self' abstraction.

Ultimately the above three concepts coalese into two conceptualisations of OOP.

The first focuses on the 'object', considering them as identifiable, autonomous, finite automatons communicating via message-passing. Conceptually we are talking about highly concurrent actor based models. This approach is the once taken by Simula, Erlang, Pick, and friends. However while it corresponds closest to the original conception of OOP, it is barely recognisable in modern mainstream OOP languages. In fact these languages are more likely to be described as concurrency-oriented than object-oriented.

The second focuses on the 'class', considering OOP in terms inheritance and subtyping. Conceptually we are talking about languages that provide records containing function typed attributes that are parametised by a recursive 'self' parameter that provides for 'late-binding'. The conventional way to model this theoretically is via Abardi and Cardelli's Object Calculus (or you could try one of the papers available online ie A Theory of Primitive Objects (second order systems) or An Imperative Object Calculus). Representitive languages include all the usual suspects: Java, C++, C#, Smalltalk, etc.

While concurrent agents with message passing might be the original definition of OO, as mentioned above most programmers who consider themselves OO wouldn't recognise this as OO; certainly almost none of the languages traditionally considered OO would fit this definition. So it is pointless to pursue it further. That leaves us with a single definition.

Object Oriented Programming is any programming based on a combination of subtype polymorphism and open recursion

Translated back into more common terms - programming based on a combination of

Polymorphic functions that accept as actual parameters values of any subtype of their formal parameters, and
Late binding, based on a distinguished 'self' parameter to functions that provides access to attributes of a record/object based on its runtime type.

Which is consise, precise, and coincides with our intuition --- even if it does leave out a few 'traditional' aspects commonly included in definitions of OOP. Now to produce an object oriented language you need to add at least the idea of functions and function application without which you are not turing complete and you will need records, without which you can't define subtyping. These don't belong to any paradigm rather they are what it means to be a programming language. You probably want to add a store and references, but again these do not belong to OO rather they belong to the super-paradigm Iterative Programming. There are all sorts of features you can add to your language but only two, subtype-polymorphism and open recursion, make you Object Oriented.

Interpreter Pattern and Structural Recursion

2006-04-19T09:49:00.000+10:00

I have previously discussed the flaws and limitations of the Visitor Pattern; criticised the Singleton Patterm as a global variable in disguise; and dismissed all but one of the rest as kludges to work around the GoF's languages-of-choice. That leaves the Interpreter.

This is a critically important pattern, if you only learn one pattern, make it this one! It is so fundamental to what we do to be different in kind from the other patterns in the book. In fact it is so critical that Gamma et al would probably have been better off ignoring the other patterns and writing their book exclusively on the Interpreter. In a very real sense this is exactly what Daniel Friedman did in "Essentials of Programming Languages" (EoPL).

If nothing else, the fact that you can comfortably write an entire book introducing the basics of the Interpreter Pattern is a good sign we're dealing with a different beast here to the rest of the GoF. Can you imagine writing a 300 page book introducing the basics of the factory-method?

The reason why the interpreter pattern is so important is that it amounts to designing a language, and language is our primary tool as programmers. We solve problems with computers, ultimately we do so with sequences of opcodes passed to the execution unit of our cpus; but the number of concepts we can express in a single sentence in machine code is limited, and the amount of detail we can choose to ignore when it is irrelevant to our solution is minimal. The act of climbing the language stack, (machine code -> symbolic assembly -> macro assembly -> C -> libc -> [java, Scheme, ML, etc]) is an exercise in increasing these two measures. Note I included libc in that list. I did that because language is the core abstraction being invoked in library, module, and macro systems as Kernighan and Pike discuss in "The Practice of Programming".

Now for the bad news. Yes the interpreter pattern is all goodness and light, but the unfortunately the sample implementation provided by GoF is crap. It's crap for exactly the same reason the visitor pattern is an inappropriate approach for parse-tree manipulation. This is a symbolic transformation, and as a problem is decidedly non-object-oriented. I'll go into exactly what an object-oriented problem looks like another time, but suffice to say that there is a good reason why LISP has survived 50 years, and the applicability of functional programming techniques to symbolic programming is a major part of it.

The solution offered in Design Patterns is an excelent piece of OO design. The problem: You have an AST you wish to execute. The solution: encapsulate the knowledge of how each different node-type should be evaluated in an 'evaluate' method on each node-type's associated class. Below is an example calculator implemented in Java using this exact design:

$cat test/*.java

/**
 * test/Add.java
 */
package test;

public class Add implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Add(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() + this.rhs.calc();
  }
}

/**
 * test/Div.java
 */
package test;

public class Div implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Div(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() / this.rhs.calc();
  }
}

/**
 * test/Expression.java
 */
package test;

public interface Expression {
  public int calc();
}

/**
 * test/Main.java
 */
package test;

public class Main {
  public static void main(String[] args) {
    System.out.println(Integer.toString(
        new Mul(
          new Sub(new Num(6), new Num(2)),
          new Add(new Num(2), new Num(3))).calc()));
  }
}

/**
 * test/Mul.java
 */
package test;

public class Mul implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Mul(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() * this.rhs.calc();
  }
}

/**
 * test/Num.java
 */
package test;

public class Num implements Expression {
  private int num;

  public Num(int num) {
    this.num = num;
  }

  public int calc() {
    return this.num;
  }
}

/**
 * test/Sub.java
 */
package test;

public class Sub implements Expression {
  private Expression lhs;
  private Expression rhs;

  public Sub(Expression lhs, Expression rhs) {
    this.lhs = lhs;
    this.rhs = rhs;
  }

  public int calc() {
    return this.lhs.calc() - this.rhs.calc();
  }
}

and indeed this does print '20' as expected.

Compare this with the ML code below, or the far more complex interpreter on page 74 of EoPL, and the problem is immedately clear. With symbolic transformation we are invariably performing 'structual recursion'. We have a data-structure, that is indeed a structure, defined recursively that is then processed by following the structure of the data, possibly performing an operation at each step. Consequently it is the structure that is important in comprehending the code, and ensuring a perfect match between data-structure and code-structure that is required to get it right. By scattering the code across multiple files, it makes it much more difficult to understand the structure of the code, and impossible to verify that this matches the structure of the data without signifigant effort.

$cat calc.ml

(* Calculator *)

type expression =
  | Num of int
  | Add of expression * expression
  | Sub of expression * expression
  | Mul of expression * expression
  | Div of expression * expression ;;

let rec calc expr =
  match expr with
    | Num n -> n
    | Add (e1, e2) -> calc e1 + calc e2
    | Sub (e1, e2) -> calc e1 - calc e2
    | Mul (e1, e2) -> calc e1 * calc e2
    | Div (e1, e2) -> calc e1 / calc e2

let main () =
  print_int(calc(Mul(Sub(Num 6, Num 2), Add(Num 2, Num 3))));
  print_newline();
  exit 0 ;;
main() ;;

and it is now trivial to inspect the code and the data and verify that the structures are identical. In fact it is so trivial the compiler will warn us of our mistake.

$ diff calc.ml calc-broken.ml 15c15
<     | Mul (e1, e2) -> calc e1 * calc e2
---
> (*    | Mul (e1, e2) -> calc e1 * calc e2 *)
$ ocamlc -o calc-broken calc-broken.ml 
File "calc-broken.ml", line 11, characters 2-199:
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
Mul (_, _)
$ ./calc-broken
Fatal error: exception Match_failure("calc-broken.ml", 11, 2)

Now if you are stuck in an OO-world then the closest you can get to the above is to use either the visitor pattern or dynamic double dispatch. Not as neat, and a scary amount of boilerplate, but it works, and it is definately preferable to the example given in GoF; and when the time comes that you are not compelled to consign yourself to the OOP-only gulag you now know that there is something worth escaping to.

Back working on Kowari.

2006-04-18T16:00:00.000+10:00

I am very grateful that I have been able to obtain another contract to work full-time on Kowari, so we should be seeing several fixes, changes, and enhancements flow into kowari over the next 3 months. The first installment is an enhancement to iTql to permit the convenient expression of compound constraints and existentials within the query.

{ s p1 o1 : p2 o1,o2 in m}
  is expanded to 
s p1 o1 in m and 
s p2 o1 in m and 
s p2 o2 in m

  and
[ p1 o1 : p2 o1,o2 in m ] 
  is expanded to 
$av__X p1 o1 in m and 
$av__X p2 o1 in m and 
$av__X p2 o2 in m ; 

for some value of X

This syntax is derived directly from N3/SPARQL, with the only exception being that we use colons instead of semicolons to separate predicates because kowari uses ';' as a query seperator.

Anyone doing large conjunctions on custom resolvers will be particularly pleased to see this, and this is my first step towards better custom resolver support in general.

In other news I feel I should point people at the Netymon Public Repository which is currently home to any kowari improvements made by Netymon until such a time as the future of the sourceforge project is determined.

The perils of avoiding heresy (or "What are Design Patterns")

2006-04-18T11:29:00.000+10:00

My last two posts have been rather critical of the Visitor Pattern as described in "Design Patterns" more commonly known as GoF (Gang of Four). So the question is reasonably asked, do I consider the other patterns similarly flawed? If anyone is interested in the answer, it's yes. In fact rather than being subtitled "Elements of Reusable Object-Oriented Software", it should have been "21 reasons C++ sucks; 1 embarassment; and an Abstract Syntax Tree".

First the embarassment: Singleton.
This is a global variable. It should be treated in your design as a global variable; a useful hack sometimes, but always undesirable. Singleton is more honestly described as "Abusing your languages class system to provide namespacing for global variables". Just say no.

Regarding the 21 other patterns, let me just add that most of them apply to Java equally to C++, but Java simply wasn't a serious contender when the book was written; and of course the examples are mostly C++ (all of them except a few in smalltalk). Ponder this question: Why isn't 'Constructor' a creational pattern? Then ask yourself, why are the OO-community the only programming community to name the Factory Method, or Command patterns? The answers are simple, but the ramifications profound.

In a language with first-class constructors, the Factory Method Pattern consists of

factory = MyClass.constructor

In a language with closures the Command Pattern consists of

menuItem.clicked = lambda : ...do stuff...

In a langauge with constructors, the Constructor Pattern consists of

obj = new MyClass()

The final pattern is the OO version of the fundamental 'design pattern', elsewhere known as 'language'. The Interpreter Pattern was first applied, in it's non-OO form, during the 1950's, most famously in the development of symbolic assembly language, FORTRAN and Lisp. Since then it has found wide application being used in such diverse domains as database-querying, and printf format strings. The pattern is simultaneously both the most signifigant, cross-language, powerful pattern in Computer Science, and the biggest 'DUH' in the GoF's book. Of course, as with Visitor, the pattern in GoF is a near perfect example of the results of trying to shoehorn a non-OO problem into an OO-design; however I'll leave analysis of that for another time.

So if the book is predominately a catalogue of unfortunately necessary kludges around the semantic weaknesses of mainstream OO-languages, why do I still highly recommend it to new programmers?

Well for starters, precisely because it is a catalogue of necessary kludges. The book does capture (with the exception of Singleton) good work arounds for the weaknesses a programmer is going to face when working with C++/Java/C# (and to a lesser extent Python/Ruby/Smalltalk/etc). We all find ourselves needing to work in these languages from time to time, and it is well worth knowing cleaner kludges.

Secondly, along with "Refactoring" by Martin Fowler, GoF provides the reader with a solid introduction to good OO design. Combined, these two books will guide the new programmer into a solid understanding of classic object orientation. Given OO is the dominant paradigm behind all the current mainstream languages (unless you consider VB mainstream), this is worthwhile. That there are far better, cleaner, and safer alternative designs available outside the mainstream is beside the point when a new programmer is going to face Java or C# (or heaven forbid C++). Where a skilled programmer will translate these alternatives into a clean non-OO implementation within a mainstream language (see previous discussion regarding Visitor pattern and parser generators); this is simply not a reasonable expectation of a new programmer who is still mastering their first or second language.

Read them, learn them, even use them. Still you should always remember, these are kludges, and there are generally better alternatives available - the proof of you skill as a programmer is you understanding of what they are.

More on the visitor pattern

2006-04-13T11:11:00.000+10:00

The primary reason I started this blog was that I occasionally spend non-trivial amounts of time contributing to mailing lists discussions. Some of those emails approach short articles and I got fustrated having them disappear into list-archives, sometimes never to be seen again (even when I've gone looking for them).

Not surprisingly my recent blog entry, and associated post to the kowari mailing lists has led to a need to respond with a more carefully reasoned, and less emotional defense than yesterdays rant.

First it has been pointed out that I used the term Abstract Syntax Tree when it would be more correct to refer to the output of sablecc as a Concrete Syntax Tree. I acknowledge this, although I have always found the distinction vague. It always seems to rely on the semantics of the grammar not the syntax. The closest I've come to definition that doesn't make reference to semantics is: "An AST is a CST missing some bits"; which of course implies CST is a subtype of AST forall values of some == none.

However as this post is not dealing specifically with sablecc, but rather with parser generators in general, and with their interaction with the visitor pattern in particular, I will continue to use the more general term AST as it is more appropriate given the existence of tools such as javacc that permit the definition of an AST directly within the grammar file.

I was pointed at http://nat.truemesh.com/archives/000531.html for a discussion of new features in sablecc to make the use of the visitor pattern more palateable. Indeed these features are going to be useful, however they only demonstrate my point.

Defining the abstract syntax tree and writing transformations from to concrete to abstract tree is quite an effort, and then you have to write your own visitor classes to process that tree.

Exactly the same argument applies if what you are wanting is 3-address code, or a rmi-enabled Query object (which is want Kowari is generating). What the author of sablecc is slowly learning is that the authors of cups, yacc, and antlr whose products he dismissed so casually in his thesis actually did know what they were doing.

Ultimately the Lex -> Parse -> Semantic Analysis stage of a compiler is not suited to an OO based design, and no attempt to shoehorn this into an OO framework is going to be as effective as recognising this and working with the grain of the problem. You can see this clearly illustrated if you look at the actual Parser.java file generated by sablecc. It is not object oriented in the slightest, rather it is a massive automaton (itql has 205 states), with each state associated with a small fragment of functional code. This accurately reflects the nature of the problem. That the the user is then presented an interface that ignores this underlying reality in favour of ideological purity is unfortunate.

The only justification given is that it allows the semantic analysis to be seperated from the grammar defintion. But then the seperation of the first stage SA from grammar is undesirable, so this is a moot point. A stage-1 SA must follow the exact shape of the productions in the grammar. As structure is very awkward to keep synchronised, DRY dictates that this structure should be defined in exactly one place. Moreover the as the parser is completely defined by the structure, don't think of the 'grammar' file as the parser's grammar; think of it as the stage-1 SA definition. The parser just happens to be generated directly from a simple structural analysis of the SA definition. I have written numerous parsers, they cease being difficult when you stop trying to think of them in imperative terms, but consider them as declarative definitions of symbolic tree transformations. Anyone having trouble with this concept should reread sections 5.1-5.4 of Aho/Sethi/Ullman (Dragon Book).

Parsing is easy. Semantics is not. The visitor pattern results in a very clean elegant interface to the parser, and makes the parser writers life easy. However it wasn't a fundamentally hard life to begin with, and the decision results in scattering the semantic analysis code as 1-3 line fragments across dozens of files (unless you do what kowari does and breaks encapsulation). To the extent you follow the pattern, you need a visitor for each unique synthesised attribute. What is generally a one line annotation on an EBNF grammar becomes an entire class. If you allow apply() to return a synthesised attribute, you can normally reduce the number of classes by combining visitors. Be aware though that having used this approach myself the price is in maintainability and flexibility as you have to be very careful you avoid undesired interactions between the combined visitors.

Parsing is only occasionally hard; Semantic Analysis is only occasionally easy. We should not be trying to find ways of making parsing easier just because it is easy; rather we should be trying to find ways to make semantic analysis easier precisely because it is hard. We are dealing with a functional problem and trying to find an object-oriented imperative solution is working against the grain, and it leaves me wondering, "Why you would bother?".

Visitor Pattern and Trees Considered Harmful

2006-04-11T13:20:00.000+10:00

I have just finished a very fustrating week fighting a parser generator implementing some syntactic sugar for Kowari. The reason why it's been so fustrating is simply because it should have taken one day to implement, test, and document, except that the parser generator was sablecc.

Now sablecc has been stable, featureful, and reasonably performant. Documentation is a minor problem given that it really only consists of a tutorial and the author's masters thesis; still it's a LALR parser generator once you have an EBNF exactly how hard can it be? As a parser generator sablecc works wonderfully.

Unfortunately that's also where the trouble starts, because it's very rare for someone to only want a parser. Generally someone is using a parser generator because they are writing some sort of compiler, and so the parser generator feeds into some sort of semantic analysis stage. And this is where sablecc fails, cf. the topic of todays post.

Sablecc generates an AST. Sablecc always generates an AST! And of course how does your hard working, OOP entrenched, lemming of an author support inspection of this tree? Well as with all well behaved OOP lemmings the author parrots off in the true unquestioning drone of the acolyte, "The visitor pattern of course". Think I'm joking? The thesis was called "SABLECC, AN OBJECT-ORIENTED COMPILER FRAMEWORK"! At this point swearing would be appropriate.

Let's step back and look at the problem we are actually trying to solve. We have an context-free grammar that describes how we can generate an abstract syntax tree from a given input. Semantic Analysis is effectively a transform applied to the AST. Now the nature of this transform is remarkably consistent across compilers. Occasionally it amounts to a eulers walk over the tree, but generally it is a straight forward post-order traversal generating what are called 'Synthsised Attributes' at each production from it and it's children[0]. The result is called an 'Annotated Syntax Tree', and generally the attribute derivations are defined to ensure that the desired output of the semantic analyser is an attribute at the root of the AST.

Attribute derivation defintions are routinely defined as code snippets that convert child attributes into production attributes. In other words we have a series of functions that are dispatched on the AST node type, are called within the context of the results of the child production's functions, and are called as a post-order traversal.

Finally we have the added advantage that each node in the AST corresponds to a reduction in the LALR bottom-up shift-reduce parser that is the ultimate goal of an LALR parser generator. Being bottom-up, this is automatically a post-order sequence of reductions. Consequently we can choose to forgo the generation of the AST altogether and associate the functions directly with the reductions if we so desire. (and why wouldn't we?)

Now generating an AST is sometimes desirable, for instance when you require the afore mentioned eulers walk based traversal, or if you are wanting to unparse the AST back into source-code again later. But regardless of if you generate an AST or not, most compilations are a simple bottom-up generation of the root anntoation in an annotated syntax tree based on associating functions with AST-nodes/parser-reductions.

So that is the problem we want to solve, and in the strictest possible sense it is fundamentally functional in nature. This of course poses a serious problem to our aforementioned object-oriented-lemming, because the natural, straight forward solution is not object-oriented. So the lemming spits out a tree and of course doesn't even need to think about the next step. After all "the object-oriented way to traverse a tree is the visitor pattern", so we'll disregard the fact that the problem is functional in nature --- we have this hammer and by george if we aren't going to make this problem fit our solution.

The visitor pattern is kludge used by programmers in a language that doesn't support multiple-dispatch to provide themselves with a static version of double-dispatch. The cannonical example that was used by the GoF when they documented the pattern is tree traversal. And ever since that fateful day no OOL has dared consider anything else (feh). Note there is no mention of trees in the definition above. Trees are a datastructure. The visitor pattern is a language semantics idiom. THEY ARE NOT RELATED CONCEPTS! Maybe if you are implementing dynamic traversals over a static tree (which does require double-dispatch to do cleanly) you might consider the visitor pattern as a solution to THIS problem; but only if you are willing to bet the life of your first born to guarentee that you will never ever want to introduce a new tree-node type into your design.

For LALR parsers using code definitions for synthesised attributes, this problem has been solved for decades. Yacc got it right. The limitations and difficulties that programmers have with yacc fall into 2 categories: Memory management - garbage collection neatly solves that problem; Conceptual vagueness - a tool can only rarely even help you understand the problem you are trying to solve.

Why is this the right approach? Because the attribute derivations are generally trivial calls to constructors or functions --- along the lines of foobar = new Foobar(token), or combined = combineFoobars(child1.foobar, child2.foobar). And these derivations are intimately associated with individual productions (as discussed above). Consequently it is extremely awkward to seperate the grammar definition from the attribute derivation definition, as they needs must have an identical structure, and hence seperation violates the DRY principle and makes debugging/enhancement a right royal pain.

So why have I suffered this week? Because OO-Lemmings can't be bothered to consider if OO is an appropriate paradigm for the problem that presents itself to us; and because of this unfortunate association of tree-traversal with the visitor pattern. Now I can't do anything about the prevalence of lemmings that won't get me arrested, but please please please stop using the visitor pattern to traverse trees.

[0] If an attribute derivation requires information from a parent or sibling then it is referred to as an 'Inherited Attribute', and this is when you require a dependency aware eulers walk instead of a post-order traversal.

Amusing: seen on LtU

2006-03-23T16:00:00.000+10:00

Here's the condensed LtU guide to the static types vs dynamic types debate: * Haskell-vs-Scheme is an issue on which reasonable people differ. * Ruby-vs-Java is an issue on which unreasonable people differ. Everything else is details.

Hint to new programmers

2006-02-10T15:46:00.000+10:00

So I'm working my way through code written by a recent grad.... this sucks! So to all new programmers out there...

RETURN TAKES A PARAMETER FOR A REASON!

Just because you CAN return void and use an object field as an implicit return parameter DOESN'T MEAN YOU SHOULD!

....and I suppose some lawyer would decide it was murder.....

Loops Considered Harmful (personal reprise)

2006-01-23T09:58:00.000+10:00

Paul Gearon posted a short rant on Java's verbosity and general clunkiness. The problem is to write a function that takes a string and returns a string containing the distinct characters of that string in sorted order. While Paul does provide a solution in java, he only alludes to the sort of function you might expect to write. So I thought I might have a go at the problem:

Assuming we have a string type, and a sorted-set in our standard library:

(lambda str (reverse-list->string
                (sorted-set-fold (compose cons flip) '()
                     (string-fold insert (sorted-set) str))))

Note: The reverse reduces the complexity from O(n^2 log m) to O(n log m)
3 lines. No mess, no fuss.

Trouble in Kowari-land

2006-01-10T09:53:00.000+10:00

Times of transition are always hard, and cultures do not always mix without conflict. The past year has been a time of transition for Kowari, as we have had to move from a close-knit circle of developers mostly working in the same room, to a distributed open-source community. It has of course been complicated by the need to try and reach an understanding with the new copyright owners of much of the kowari codebase, Northrup Grumman.

Yesterday I had the unpleasant duty of accepting the resignation of a good friend, colleague, and co-developer/admin from the Kowari project after he received legal threats from Northrup. I remember watching these sorts of tussles go down in my years within the OSS community. I have always felt sympathy for those volunteers who find themselves in the way of corporate lawyers. Now as the maintainer who has to sit and wait for NG's response I realise just how important the freedom in free-software really is. The MPL 1.1 is now the only thing standing between me and the loss of the Kowari project.

It's not really surprising that this story is starting to find its way onto the blogsphere. I would like to thank the SOFA community for their note of support. In response to Clark Parsia's questions about the legal status of kowari:

The copyright in the vast majority of Kowari as of Jan 2005, and consequently the majority of Kowari now was owned by Tucana Technologies, and hence now by NG. However the majority of the work done in 2005 was done by parties unassociated with NG, and this work is copyright the authors (or in some cases the parties that paid for the work). Of particular note is the work done by Paul Gearon on the krule engine, and the work commissioned by the DSTO on the query rewriting. The former particularly is perfectly capable of independent existence, and while it currently lives in the kowari sourcetree is not derivative.
There have been no releases since Tucana went insolvent. It took 6 months to reorganise after Tucana's fold, and another 3-4 months to prepare for release. We were ready for release in November, however held off at the explicit (and inconvenient) request of NG in an effort to support there integration into the community. I should be clear here; The 9th of January release date was requested by Northrup, and acceeded to by the Kowari administrators as a sign of good-faith. We had originally planned to release 1.1 in November.
IANAL, but my understanding of the MPL --- and my personal first-hand knowledge of the express intent of Tucana when the MPL was chosen as a license --- is that anyone who cares to has the right to take a snapshot of the sourceforge repository; label it MyKowariRelease1.1; and release it to the public. And indeed if open-source means anything, it means the right to fork. However at the present point in time, I am the administrator of the kowari project, and Northrup have the same right to fork from Kowari as anyone else does.

As is clear in Clark Parsia's blog post above, this uncertainty is hurting Kowari so I will do whatever I can to ensure it is resolved promptly. All I can ask is to please be patient and lets see if we can't help Northrup to become a productive member of the opensource community.

Humourous post on ocaml-list

2005-12-23T11:45:00.000+10:00

Ok so the fact that I found this hilarious probably suggests I need my head examined... I still thought I'd share it though.

From: hars@bik-gmbh.de
Subject: Re: [Caml-list] Camlp4 in a Unix pipe
Message-Id: <4383605A.7030309@bik-gmbh.de>

Alessandro Baretta wrote:
Cool command line! How did you discover the '-' option? 

Out of habit? In the the unix shell monad, "foo >>= bar" happens to be written
as "foo | bar -" ("return" is written "cat", in case you wondered. So "Hey,
that is a useless use of cat!" really means 'Hey, you ignored the monad laws!")

Yours, Florian (time to go home, I know).

So yeah at this point I probably have to conceed I'm strange :).

Alternative Logics

2005-12-16T17:44:00.000+10:00

Found via Google Blogs: A Neighbourhood of Infinity: Alternative Logic.

An interesting read.

Google Blogging and an interesting assertion.

2005-12-16T10:50:00.000+10:00

Read Paul's post on the latest addition to Google Labs. Installed Google Blogger, and WOW this is cool. Naturally first stop was to check out etymon (disappointing), and second to visit sites I visit regularly. Stumbled upon this quote recounted by Martin Fowler; would love to see some measurements.

While I'm on the topic of concurrency I should mention my far too brief chat with Doug Lea. He commented that multi-threaded Java these days far outperforms C, due to the memory management and a garbage collector. If I recall correctly he said "only 12 times faster than C means you haven't started optimizing".

Reading List Reprise

2005-12-13T10:46:00.000+10:00

When I started this blog I posted my reading list, having recently finished Types and Programming Languages I thought it was probably time to revisit the reading list.

Essentials of Programming Languages, Daniel Freidman: I finished this early in the year. Unfortunately I never did finish working the examples beyond the first couple of chapters. There is some very interesting material in this book, particularly the last couple of chapters.
Types and Programming Languages, Benjamin Pierce: I recently finished this (back in October), and loved it. This book is illuminating, and it definately achieved its goal. This book is a superb example of how to introduce a reader to a field, and provide the necessary preparation for accessing further works.
Introduction to Graph Theory, Richard J. Trudeau: Read, and yes it was a fun book, but unfortunately did not ever really reach the depth I needed for it to be immediately applicable. What I received from this book was mostly vocab.
Making reliable distributed systems in the presesnce of software errors, Joe Armstrong: I know Greg was annoyed by some trivial errors in some of the example code; however I am very glad I've read this thesis. This is the closest I have seen to practical self-reparing systems. An gentle and easy read, it lays out a practicioners framework for designing reliable systems. Highly recommended.
The Polyadic PI Calculus : A Tutorial, Robin Milner: Never did finish reading this as I ended up borrowing Milner's book and reading it instead. I'm curious to know if there has been any work on the relationship between PI-calculus processes and continuations.
Genuinely Functional User Interfaces, Antony Courtney, Conal Elliott: As I said this is my primary area of interest, and it remains the long-term focus of my efforts. This paper remains a core influence on my interest in Type-Theory, Category Theory, and Language Semantics
Arrows, Robots, and Functional Reactive Programming, Paul Hudak, Henrik Nilsson, Antony Courtney, John Peterson: Opps, that's right I was going to read this one... I'll have to carry this one over to my new reading list...

Other works read worthy of note include:

Purely Functional Data Structures, Chris Okasaki: This book stands alongside my copies of Cormen, Date, Brooks, and K&R without shame. Only a year old and already starting to wear from use. Personally I consider it essential reading for anyone serious about programming. I am seriously considering buying a second copy so I can lend one without losing it from my library. This book is important enough that I will be posting seperately about it.

Kowari insert/select and blank-nodes.

2005-12-07T14:48:00.000+10:00

I was asked recently to justify Kowari's decision to maintain blank-node identity across an insert/select command. My response was along the lines of treating kowari as a 4-graph partitionable as rdf-compliant 3-graphs (actually technically a superset as we don't restrict the domains of subjects and predicates as rdf does). At this point the entire 4-graph is within the scope of the existential, and consequently it is valid to retain blank-node identity between the rdf-partitions (kowari models).

However it did send me back to the RDF-SEMANTICS spec again where I found the following in 1.5. Blank Nodes as Existential Variables

This effectively treats all blank nodes as having the same meaning as existentially quantified variables in the RDF graph in which they occur, and which have the scope of the entire graph. In terms of the N-Triples syntax, this amounts to the convention that would place the quantifiers just outside, or at the outer edge of, the N-Triples document corresponding to the graph. This in turn means that there is a subtle but important distinction in meaning between the operation of forming the union of two graphs and that of forming the merge. The simple union of two graphs corresponds to the conjunction ( 'and' ) of all the triples in the graphs, maintaining the identity of any blank nodes which occur in both graphs. This is appropriate when the information in the graphs comes from a single source, or where one is derived from the other by means of some valid inference process, as for example when applying an inference rule to add a triple to a graph. Merging two graphs treats the blank nodes in each graph as being existentially quantified in that graph, so that no blank node from one graph is allowed to stray into the scope of the other graph's surrounding quantifier. This is appropriate when the graphs come from different sources and there is no justification for assuming that a blank node in one refers to the same entity as any blank node in the other.

(emphasis added)

Later in 2. Simple Entailment between RDF graphs we come across the Merging Lemma

Merging lemma. The merge of a set S of RDF graphs is entailed by S, and entails every member of S. [Proof] This means that a set of graphs can be treated as equivalent to its merge, i.e. a single graph, as far as the model theory is concerned. This can be used to simplify the terminology somewhat: for example, the definition of S entails E, above, can be paraphrased by saying that S entails E when every interpretation which satisfies S also satisfies E. The example given in section 1.5 shows that it is not the case, in general, that the simple union of a set of graphs is entailed by the set. The main result for simple RDF inference is:

This is relevant because an alternative view of kowari is as a set of named graphs.

Last time I read this document was when I first started with Tucana, and hadn't heard of RDF before. It is amazing how much more understandable the rdf-semantics document once you've spent some time working with RDF.

Persistent Datastructures

2005-08-17T12:10:00.000+10:00

Many moons ago I wrote a short tutorial on pthreads. It was adopted (with permission) by a number of universities to provide a brief introduction for their students doing pthread based coursework. It strikes me as bizzare, but the tutorial remains the top google hit for 'pthreads tutorial'. Consequently I periodically get requests for help with threading issues.

When I wrote the tutorial I was still enamoured with threads, an infatuation that didn't last very long :). Since then, my experience working with pthreads, auto-parallelising compilers, java, erlang, kowari, and 10 years of professional programming, have fundamentally changed my perspective on how to approach concurrency.

Concurrency bad
See 1
Shared-memory concurrency very very bad
see 3

However we can't always avoid concurrency so:

Process isolation good
Message-Passing/Rendevous good
Co-routine/Continuation good

Again, sometimes we can't avoid shared-memory concurrency if we want to make good use of some modern cpu architectures so:

Locks are bad - you've accepted all the pain and suffering associated with shared-memory concurrency, and now you're going to SERIALISE operations!!

Assuming you are stuck using shared-memory threads, what do you do now? Well first hope like hell you have a garbage collector. If you don't it is going to hurt enough I would suggest you give up now and go back and reconsider the reasons why you discounted the other options above -- anything is better than this. If you do have a garbage collector, start reading up on persistent datastructures.

Persistent datastructures are very important in safe efficient thread-based design because they don't require locking. They are called persistant because they are immutable. Once you have a reference to a structure that structure is guaranteed const. What this means is that any method that would mutate an empherial (ie, what you are used to) structure returns a new structure.

As an example consider a list

x = []              | x = null 
y = x.prepend(1)    | y = { 1, x }
z = y.prepend(2)    { z = { 2, y }

Now if you need the rest of your program to see the updated list you use some sort of reference cell. The simplest is just a one element queue. This is a classic reader-writer problem; except you don't have to worry about evicting readers before the writer does his thing.

RefCell:
  init(T data);   // Initialises the cell with data.  All subsequent access to data must originate with this cell.
  T read();       // Returns the current value of data (internally access is protected by the 'access lock').
  T writeLock();  // Obtains the 'write lock' (or blocks), and returns the current value of data.
  unLock(T data); // Updates the current value of data under the 'access lock', and releases the 'write lock'.

Note there is almost no contention for readers, no book-keeping, and once a reader has a reference to data, all further access to the structure is lock-free.

However take another look at it. Step back and think about what this is and you will realise that what we have written here is a transaction based datastore. What this means is that you can now go examine all your transaction management theory and introduce multiple-writers, lock-stealing, etc, et al. Now as long as T is persistent, you are atomic, consistent, and isolated. If you ensure unLock flushes the structure to disk you now have an ACID datastore (surprised? :). Add consistency checks to the mutation operations and you can call it a database :).

Granted, without a garbage collector, memory management is a bitch. The standard reference on persistent structures is Chris Okasaki. A quick google will get you a fair way; however citeseer is the motherlode. If you have access to a university library, I would lookup his book (Purely Functional Data Structures), which will save you alot of searching on citeseer :).

Another thing worth noting is that it is worth noting is that once you leave the ephemeral space, you need to start making decisions beyond the simple "Vector/List/Hash/Tree". There are alot more tradeoffs to consider. Do you really need the efficient random-access of a vector, or are you actually using it as a queue, or dqueue? A persistent queue can be implemented with O(1) amortized operations, but the best I have been able to find (quickly) for a true 'vector' is log(i) access (i = index) [citeseer]. Just as importantly, a persistant queue is very simple, almost identical in fact to an efficient ephemeral queue; whereas a persistant random-access-list much more complicated than a vector.

Using Jabber as a communications framework

2005-06-04T08:38:00.000+10:00

Adrian Sutton asks about using Jabber as a communications framework for developing a bug-tracking/QA application. Two items immediately spring to mind.

ACME: Toward a LL Testing Framework for Large Distributed Systems
- Dana Moore and Bill Wright
ejabberd and J-EAI - which uses it as it's message bus.

I haven't had any experience with jabber except as a casual user, however these are projects that have caught my eye as things I would like to investigate when/if I ever have time. So Adrian, if you do check them out, let me know how you go :).

Silly old lady

2005-05-25T09:49:00.000+10:00

There was an old lady who swallowed a bird;
How absurd, to swallow a bird!
She swallowed the bird to catch the spider
That wriggled and jiggled and wiggled inside her.
She swallowed the spider to catch the fly.
But I dunno why she swallowed that fly -
Perhaps she'll die

Long Time no See

2005-01-13T19:37:00.000+10:00

I realise it has been almost two months since I last blogged, I can only plead two excuses for this lapse. The first reason is that I have met an incredible woman and have dedicated a substantial amount of time recently in getting to know her better. The second is that on the 26th of December, Tucana Technologies (my employer) closed its doors. This is an incredible blow as without reservation, this was the best job I have ever had. I can only hope that I will be able to find something half as involving, challanging, and inspiring as my work on Kowari and RDF. Anyway, unless I should suddenly find myself with employment I should be able to address some of the unfinished posts I have lined up for this blog over the next week or two.

On that note, I have spent some time trying to install GHC under OSX 10.2, unfortunately the only install I have been able to find and install thus far is for 10.3. If anyone out there knows of a package or install method for 10.2 it would be much appreciated.

Finally if anyone is interested in employing a Senior Computer Systems Engineer with a strong background in metadata, RDF, and in the use and design of more languages than you can poke a stick at, feel free to contact me on andrae@humbug.org.au; CV available on request.

Well worth the time.

2004-11-25T10:10:00.000+10:00

Went back and watched two of the Little Languages 2 Workshop presentations. Specifically Joe Armstrong and Todd Proebsting's presentations on "Concurrency Orientated Programming", and "Disruptive Programming Language Technologies" respectively. I highly recommend both these talks to anyone who is the slightest bit interested in programming languages, or has any serious involvement in development. It is just unfortunate that they are only available as real-video. Still if you have r-v installed, they are both well worth the time.

Note these are links to the two sessions of the workshop. It's convenient that both my favourite talks from this workshop happen to be first in each session.

The Theory of Classification.

2004-11-23T11:11:00.000+10:00

Andrew Newman came across this set of articles on OO theory. I stumbled across them about a year ago, read the first few, changed jobs, and promptly forgot to go find them again. I remember them as well worth the time to read.

This is the first article in a regular series on object-oriented type theory, aimed specifically at non-theoreticians. The object-oriented notion of classification has for long been a fascinating issue for type theory, chiefly because no other programming paradigm has so sought to establish systematic sets of relationships between all of its types. Over the series, we shall seek to find answers to questions such as: What is the difference between a type and a class? What do we mean by the the notion of plug-in compatibility? What is the difference between subtyping and subclassing? Can we explain inheritance, method combination and template instantiation? Along the way, we shall survey a number of different historical approaches, such as subtyping, F-bounds, matching and state machines and seek to show how these models explain the differences in the behaviour of popular object-oriented languages such as Java, C++, Smalltalk and Eiffel. The series is titled "The Theory of Classification", because we believe that all of these concepts can be united in a single theoretical model, demonstrating that the object-oriented notion of class is a first-class mathematical concept!

Anyway, the links:

"The Theory of Classification"

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, and 15.

Links found.

2004-11-15T17:30:00.000+10:00

Just noting that I have updated the Arrows 'n Robots summary with links to citeseer and Wan's thesis page on the Yale-group pages. Also wanted to dump the url to the Yale group here so next time I can find it more easily.

http://haskell.cs.yale.edu/yale/ http://haskell.cs.yale.edu/yale/publications.html

Category Theory

2004-11-15T13:38:00.000+10:00

I have had a few people ask me to explain the utility and signifigance of category theory. This proves rather difficult given I am a complete novice in this area myself; desprately trying to keep my head above water in the simplest of papers. Still I found this paragraph useful, and I decided to post it here so I can find it again.

Category theory unifies mathematical structures in a second, perhaps even more important, manner. Once a type of structure has been defined, it quickly becomes imperative to determine how new structures can be constructed out of the given one and how given structures can be decomposed into more elementary substructures. For instance, given two sets A and B, set theory allows us to construct their cartesian product A X B. For an example of the second sort, given a finite abelian group, it can be decomposed into a product of some of its subgroups. In both cases, it is necessary to know how structures of a certain kind combine. The nature of these combinations might appear to be considerably different when looked at from too close. Category theory reveals that many of these constructions are in fact special cases of objects in a category with what is called a "universal property". Indeed, from a categorical point of view, a set-theoretical cartesian product, a direct product of groups, a direct product of abelian groups, a product of topological spaces and a conjunction of propositions in a deductive system are all instances of a categorical concept: the categorical product. What characterizes the latter is a universal property. Formally, a product for two objects a and b in a category C is an object c of C together with two morphisms, called the projections, p: c → a and q: c → b such that, and this is the universal property, for all object d with morphisms f: d → a and g: d → b, there is a unique morphism h: d → c such that p o h = f and q o h = g. Notice that we have defined a product for a and b and not the product for a and b. Indeed, products and, in fact, every object with a universal property, are defined up to (a unique) isomorphism. Thus, in category theory, the nature of the elements constituting a certain construction is irrelevant. What matters is the way an object is related to the other objects of the category, that is, the morphisms going in and the morphisms going out, or, put differently, how certain structures can be mapped into it and how it can map its structure into other structures of the same kind.

Jean-Pierre Marquis, Stanford Encyclopedia of Philosophy: Category Theory

Arrows, Robots, and Functional Reactive Programming --- Summary

2004-11-12T16:55:00.000+10:00

First some background reading from the bibliography I'll have to read eventually:

John Hughes. Generalising monads to arrows. Science of Computer Programming, 37:67-111, May 2000
Ross Paterson. A Notation for Arrow-based Libraries. In ICFP'01: International Conference on Functional Programming, pages 229-240, Firenze, Italy, 2001
Zhanyong Wan. Functional Reactive Programming for Real-Time Embedded Systems. PhD thesis, Department of Computer Science, Yale University, December 2002
Zhanyong Wan, Walid Taha, and Paul Hudak. Real-time FRP. In Proceedings of Sixth ACM SIGPLAN '00 Conference on Programming Language Design and Implementation (PLDI), pages 242-252, Vancouver, BC, Canada, June 2000. ACM, ACM Press.
Zhanyong Wan, Walid Taha, and Paul Hudak. Event-driven FRP. In Proceedings of Fourth International Symposium on Practical Aspects of Declarative Languages. ACM, Jan 2002

Naturally when you are using FRP the core concept is that of the signal. So we define signal to have the type Signal a = Time -> a, ie a function of Time returning a value of type 'a'; s(t). The robot used throughout the paper is a simple differential drive with a handful of basic sensors. So given two signals vr(t) -> vr::Signal Double and vl(t)vl::Signal Double which are the velocities of the right and left wheels respectively we can write an reactive program for calculating the robots position:

x     = (1 / 2) * integral ((vr + vl) * sin theta)
y     = (1 / 2) * integral ((vr + vl) * cos theta)
theta = (1 / l) * integral (vr - vl)

Of course the nice thing about this program is that it is a direct transliteration of the physics equations governing the motion of such a robot! This is why FRP is important.

Such programs are clear, consise, correct, and unfortunately completely unworkable in the general case. The problem is that while in the small (with simple toy examples) you couldn't get better than this, larger programs tend to lead to opaque space and time management with the resultant space and time leaks. The focus on this paper is how to retain most of the legibility and good domain match of FRP while preventing leaks. The FRP DSL developed in this paper is called Yampa, and it solves the leak problem by disallowing signals as first class values. Instead signals are manipulated indirectly via set of combinators called signal transformers or signal functions.

SF a b = Signal a -> Signal b

This of course is very similar to the Haskell IO or State monads, and reminisent of Hutton's Monadic Parser Combinators. On the other hand, as presaged by the subject, the authors use Arrows rather than Monads as the basis for their combinator library.

A good analogy for this idea is a state or IO monad, where the state is hidden, and a program consists of a linear sequencing of actions that are eventually run by an interpreter or the operating system. But in fact arrows are more general than monads, and in particular the composition of signal functions does not have to be completely linear

Specifically Arrow contains a fixedpoint combinator loop which provides access to recursion.

The basic combinators include.

lift function: arr :: ( a -> b ) -> SF a b: Takes a normal function from type 'a' to 'b', and returns a signal-function/transformer that will convert a signal of type 'Signal a' to 'Signal b'.
compose: (>>>) :: SF a b -> SF b c -> SF a c: Takes two signal functions and returns the composition of them
tuping: (&&&) :: SF a b -> SF a c -> SF a (b, c): This permits you to take one signal and apply two functions to it similtaniously producing two signals both independently derived from the input. And of course, once you have tupled outputs....
tuple-transform: (***) :: SF a b -> SF c d -> SF (a c) (b d): Take two signal functions and returns a transformer that applies them to the respective signals in a tupled signal.

Now arr, (>>>), and (&&&) form a minimal universal set. However to fit the Arrow framework defined by Hughes, we use the original minimal set defined as arr, (>>>), and first (which only takes one argument, and applies it to the first signal in the tuple, passing the second unchanged).

Some standard combinators provided:


identity :: SF a a
constant :: b -> SF a b
time :: SF a Time

Also the standard arrow combinators (remember, when thinking of FRP, just substitute 'SF' for 'a' in the type-sigs):



arr :: Arrow a => (b -> c) -> a b c
arr2 :: Arrow a => (b -> c -> d) -> a (b, c) d
(>>>) :: Arrow a => a b c -> a c d -> a b d
(<<<) :: Arrow a => a c d -> a b c -> a b d
first :: Arrow a => a b c -> a (b, d) (c, d)
second :: Arrow a => a b c -> a (d, b) (d, c)
(***) :: Arrow a => a b c -> a b' c' ->a (b, b') (c, c')
(&&&) :: Arrow a => a b c -> a b c' -> a b (c, c')
loop :: Arrow a => a (b, d) (c, d) -> a b c

Note that with loop, 'd' provides a channel for feedback, and hence recursion. Notice also the strong streamish feel to the api. I would like to see a Arrow based treatment of the unix-pipe concept. I think it could result in a powerful scripting framework. Also worth noting that some signal functions are stateful (integral is one example), and as such cannot be defined without access to the underlying signals (forbidden). Hence they must either be pre-defined, or defined as a combination of pre-defined stateful signal functions.

So now convert the original FRP expression for x(t) to raw arrow-form:

x = (1/2) * integral ((vr + vl) * cos theta)

given: vrSF :: SF RobotInput Velocity  (SF that extracts vr from a RobotInput)
   and vlSF :: SF RobotInput Velocity  (SF that extracts vl from a RobotInput)
   and thetaSF :: SF RobotInput Angle

xSF :: SF RobotInput Distance   -- Signal Function transforming RobotInput -> Distance
xSF = (((vrSF && vlSF) >>> arr2 (+)) &&& (thetaSF >>> arr cos)) >>> arr2 (*) >>> integral >>> arr (/2)
  or slightly more legible:
xSF = let v = (vrSF &&& vlSF) >>> arr2 (+)
          t = thetaSF >>> arr cos
      in (v &&& t) >>> arr2 (*) >>> integral >>> arr (/2)
  which isn't all that much better.

So what we have gained above is the ability to mediate access to signals behind a reasonably safe, yet complete abstraction. However the loss in clarity is striking. Fortunately there is a proposed arrow-syntax that is similar to Haskell's monadic do-syntax.

xSF' :: SF RobotInput Distance
xSF' = proc inp -> do
  vr    <- vrSF     -< inp
  vl    <- vlSF     -< inp
  theta <- thetaSF  -< inp
  i     <- integral -< (vr + vl) * cos theta
  returnA -< (i / 2)

Which while not as nice as the original FRP, has the triple advantage of being declarative, legible, and safe!

It is important to note that the arrow syntax allows one to get a handle on a signal's values (or samples), but not on the signals themselves. In other words, first recalling that a signal function SF a can be thought of as a type Signal a -> Signal b, which in turn can be thought of as type (Time -> a) -> (Time -> b), the syntax allows getting a handle on values of type a and b, but not on values of type Time -> a or Time -> b.

Although I can't reproduce it here, Fig 2 is dramatic. The correspondance between arrow-based signal-functions, and the signal-flow-diagrams shown is striking, and exciting. I have been excited about the potential of FRP to liberate UI programming from the tyranny of the state-machine; Fig 2 amazed at the clarity available. I am now, more than ever, convinced that I am on the right track.

Events diverge from Signals slightly in that while they are also temporal values, event's don't so much change from one value to another over time, as simply not exist between 'impulses' (in the signal processing sense). In fact their is an isomorphism between impulse-streams vs. continuous-signals and event-streams vs. signals. In previous papers the authors accepted this distinction as signifigant, and the two were treated seperately. However by noting an isomorphism between Event a and Maybe a they are able to define a signal of type Signal (Event b) ie. an event stream, which becomes a signal that can be thought of as alternating between Nothing and Just a. A signal function of type SF a (Event b) generates an event stream, and is called an event source.

There are a number of combinators for use with event-streams. I'm just going to list them with minimal discussion, for more than that see the paper.

switch, dSwitch :: SF a (b, Event c) -> (c -> SF a b) -> SF a b  
        -- switch or delayed-switch.  Note the function from the event payload to a new SF a b.

rSwitch, drSwitch :: SF a b -> SF (a, Event (SF a b)) b 
        -- note event is defined to carry an SF (possibly inserted by tag), this allows for recurring switch.

tag :: Event a -> b -> Event b

mergeBy :: (a -> a -> a) -> Event a -> Event a -> Event a
lMerge, rMerge :: Event a -> Event a -> Event a
  -- Different ways of handing event collision.

-- Useful event-sources:

edge :: SF Bool (Event ())
  -- Obtain an edge trigged event-stream from a (Signal Boolean)

never :: SF a (Event b)
now :: b -> SF a (Event b)
after :: Time -> b -> SF a (Event b)
repeatably :: Time -> b -> SF a (Event b)

-- Useful event-stream transform back to signal space:

hold :: a -> SF (Event a) a
accum :: a -> SF (Event (a -> a)) (Event a)

accumHold :: a -> SF (Event (a -> a)) a
accumHold init = accum init >>> hold init

Finally just to show how it goes together, the paper implements a few robot controllers. First you implement your robot's controller as a signal function from RobotInput to RobotOutput. So a FRP mapping from the robots sensor-signals to signals which the signal-function-processor will apply to the robot's actuators. This controller is actually parametised by the robots properties, but that isn't surprising:

type RobotController = RobotProperties -> SF RobotInput RobotOutput.

Finally the FRP engine is implemented as a function from a controller to IO(). In the case of the RobotSimulator implemented for the paper, the engine also takes a second controller and a world description.

runSim :: Maybe WorldTemplate -> RobotController -> RobotController -> IO ()

Of course, returning the IO monad, this can be trivially instansated as as Haskell main function.

All in all a fascinating paper --- well worth the time to read.

Arrows, Robots, and Functional Reactive Programming --- Prelude

2004-11-11T11:38:00.000+10:00

Now this is a fun paper. I mean, Category Theory, FRP, and you get to play with Robots! What more could you want? So lets take these three elements individually, and then I will try and summarise the paper.

Category Theory

My understanding of Category Theory is as a systematic treatment of abstraction and generalisation. It allows us to take collections of mathmatical proofs and theorms that have the same structure/form, abstract them into a categorical notation, and then generalise them by providing mappings from the categorial constructs to concepts in specific domains. This is naturally of signifigant interest to type-theorists who treat programs as proofs and want access to the power of parametic/polymorphic types and functions without sacrificing rigor. Arrows are a concept from category theory, a generalisation of Monads which beyond just lifting sequencing to a first-class object, allow parametised composition of sequencing. This gives us the ability to support the more complex temporal sequencing of operations required by...

Functional Reactive Programming

Or as that is a bit of a mouthful, FRP; is one of the most intuitive and widespread programming paradigms in use today. It is an approach to programming that has been made so unobtrusive that four of the five other members of my family use it (in the form of a spreadsheet) without realising they are programming. At a basic level, FRP introduces a new paramatised datatype into the language, the time-varying 'signal'. By then permitting functions to be defined that accept these signals and return time-varying signals, you eliminate the shared-state, duplicated-logic, fragmented code paths, and explicit state-machines spawned by current, traditional event-driven approaches. As a basis for comparison, just imagine comparing a traditional spreadsheet with one where to implement a formula for a cell you would have to attach an 'onChange' callback to each referenced cell that recalculated the value.

Robots

Robots have a number of constraints that have not been traditionally considered strengths of functional programming.

Large numbers of discrete and continuous time-varying inputs that are most definately *note* referentially transparent.
Real-time constraints that impose a requirement to avoid time-leaks, which encourages the use of imperative operation sequences. Execution of which can be easilly suspended and resumed as higher priority tasks require resources.
Extensive use of embedded controllers and limited compuational resources that place a premium on transparency of resource use and strict avoidance of space-leaks.
A history of research largely based on low level system languages (ie MIML) and assembly, which makes for a hostile reception for many of the assumptions of higher-level functional programming

Of course FRP is a natural fit to the first problem. However it has traditionally done so by trading off certainty and predictability in both time and space analysis. This paper attempts to address these two problems in order to allow the exploitation of FRP's natural (theoretical) fit to robotics to be exploited.

Bananas, Lenses, Envelopes, and Barbed Wire --- Finale

2004-11-11T11:36:00.000+10:00

Finished the Bananas and Lenses paper on the weekend, along with another on FRP that I'll summarise later. Section 4 takes the previous work based on Lists from section 2 and combines it with the category-theory results from section 3 to develop a theory of cata/ana/hylo/para -morphisms over arbitary datatypes. Section 5 is a very brief extension to parametric types.

Unfortunately I simply don't have enough category theory to follow the discussion properly, let alone explain it here. I think it is probably time to make another visit to Amazon and pick up a book or two on category theory. I'm thinking probably Pierce's introduction, and possibly Crole's "Categories for Types" on the basis of the review there. I've already read Pierce's intro, and it is mercifully brief and yet even from a quick reading I found I remembered enough to follow fragments of the paper. Unfortunately I found it too brief to allow me to learn enough to follow the rest :/.

Anyway, this paper was just for fun; fun was had; and I come away with a fresh perspective on recursion. That counts as a win for me.

Back.

2004-10-06T13:18:00.000+10:00

Got back on saturday from a week long holiday helping run a holiday computer-camp for high-school kids. Now mostly recovered, and will probably blog a little on it later.

In the meantime thought I might quickly point at an interesting Wired article I found on slashdot. Looking at one of the most interesting economic effects of the net, the growth of niche markets. Recommended reading The Long Tail.

Just how stupid do you think we are?

2004-09-20T13:42:00.000+10:00

Seen on #prolog on freenode:

--> Initial_KK (noemail@CPE00e0292573fd-CM400026081604.cpe.net.cable.rogers.com) has joined #prolog
<Initial_KK> hi All
<Initial_KK> what's this program do?
<Initial_KK> member(X,[X|_]).
<Initial_KK> member(X,[_|T]) :- member(X,T).

My guess? Your Homework you lazy slob.

Orthogonality == Flexible ?

2004-09-17T14:38:00.000+10:00

As a core developer of Kowari I am regularly faced with both the good and the unfortunate aspects of RDF. One thing I continually run up against is the seemingly arbitary distinctions between subject, predicate, and object nodes. In this particular case, I still can't find out why RDF won't permit blank nodes as predicates. The same goes for Literals as subjects and predicates. Having a string literal as a predicate or subject is a little strange, and almost certainly bad style, but a typed literal most certainly makes sense. If I want to make statements about the number 5 (LT 6, GT 4, isPrime, isOdd, etc) currently we either have to use bnodes, or fake URIs, so we get:

_:bnA <owl:sameAs> '5'^^<xmls:decimal>
_:bnB <owl:sameAs> '4'^^<xmls:decimal>
_:bnC <owl:sameAs> '6'^^<xmls:decimal>
_:bnA <lessThan> _:bnC
_:bnA <greaterThan> _:bnB
....

vs.

'5'^^<xmls:decimal> <lessThan> '6'^^<xmls:decimal>
'5'^^<xmls:decimal> <greaterThan> '4'^^<xmls:decimal>
...

This is particularly important when you consider what's involved in merging two such documents. Consider trying to insert a document containing primes, with a document containing prime-factors. As we are currently forced to use bnodes, and bnode-refid's are only valid within a single document we are going to have to stuff around doing bnode unification.

Finally the fact that a URI is itself perfectly fine as a typed literal, suggests that all we really need is bnodes and typed literals (and a fair bit of syntactic sugar, but that's a serialisation issue, so we can ignore that for semantics). At the end of the day, RDF is very cool, but I suspect a fully orthogonal triple-store is even cooler. I suppose it's just fortunate that Kowari is an RDF-store built on top of a generic triple-store ;)

Reading

2004-09-10T11:34:00.000+10:00

Sometimes life throws you a curve ball. The past week I have been scrambling to help my parents respond to their landlords reasonable, yet highly inconvenient, desire to sell their house vacant possession. Consequently my blog has been neglected of late.

I enjoy reading essays, and I have definately enjoyed reading some of Malcolm Gladwell's contributions to the New Yorker (Gladwell also wrote The Tipping Point, a book I am going to have to read that discusses the effects of non-linearity in social systems). I particularly enjoyed Blowing Up, a look at non-linearity applied to the stock-market; The Mosquito Killer, a facinating look at the anti-malaria campaigns of the 20th century, and DDT in particular; The Dead Zone, the hunt for the Spanish Flu; The Coolhunt, a curious look into the 'cool hunters', a profession I never realised existed. Finally The Tipping Point, an article written four years before the publication of Gladwell's book, a reminder that non-linearity is a fact of life, and humans are particularly bad at anticipating the ramifications.

Scheme Cookbook.

2004-09-02T21:07:00.000+10:00

A few of my friends are also in the process of learning scheme. Stumbled across this interesting site which will not doubt be useful: The Scheme Cookbook. Greg, with his habit of implementing cat will likely be particularly interested in the chapter on Files and Directories.

Paul Graham is at it again.

2004-09-02T16:52:00.000+10:00

Paul Graham has published yet another essay. This time the topic is, not inappropriately, essays. As expected, the essay is worth the time to read --- if nothing else his essays are entertaining. Graham presents the essay as a form of exploratory reasoning, attempting to differentiate it from the dissertation which he presents as far more rhetorical in nature. To illustrate this he draws an analogy between the relationship between thought and essay and between conversation and dialogue.

Fundamentally an essay is a train of thought-- but a cleaned-up train of thought, as dialogue is cleaned-up conversation. Real thought, like real conversation, is full of false starts. It would be exhausting to read. You need to cut and fill to emphasize the central thread, like an illustrator inking over a pencil drawing. But don't change so much that you lose the spontaneity of the original.

I couldn't help wondering if a better analogy would be the relationship between blog and essay. I certainly don't take the time to polish my blog posts Paul takes to polish his essays.

I personally found it thought provoking, and if that is a common experience, I guess that would make it a successful essay. I certainly wasn't surprised to see it dwell on Graham's other bug-bear, the shocking state of the modern high-school curricula. Still I find some irony in my main response: pondering the possibility that the internet may trigger a resurgence in the importance placed on rhetoric and the essayist in our society; this would certainly be no bad thing.

Equality and Equivalence.

2004-09-01T22:14:00.000+10:00

My previous entry on the implementation of Object.equals() has attracted some comment, but the principle response was from Adrian Sutton, who objected to my example of a buggy equals implementation.

In one respect his criticism is valid; in general a subclass should delegate to its superclass for inheritited state equality. To do otherwise is to break encapsulation, and duplicate code. On the otherhand his complaint misses the point:

Class B is incorrectly assuming that it knows how to compare class A's data, and more importantly class B is changing the behavior of A in a way that is not compatible with the original model. Essentially, class A defines equality as having the same n1 values and class B is in the wrong for changing that. [emph added]

What Adrian misses is that if B is unable to meaningfully extend A's definition of equality then A should indicate that by declaring its implementation final, in the absence of a final declaration, B is entitled to extend it. I give an example of a meaningful use of final/instanceof in the Shape/Circle/Ellipse example at the end of the post, which I chose as it conveniently demonstrates all three cases associated with appropriate use of instanceof:

Abstract class implementing equals using instanceof to allow proper delegation of equality in subclasses.
Extensible concrete class, uses instanceof to allow subclassing; equals declared final to enforce contract
Subclassing the concrete class, overriding accessors permitting inherited (unoverridable) equals method to operate correctly (besides meeting the superclass contract ;).

On the other hand Adrian is mistaken when he suggests that the use of getClass() in equals is a bug. There are two flaws with his reasoning. The first arises from a confusion between syntax and semantics. Adrian offers a code fragment, suggesting that it would need A to use instanceof for correctness:

class C extends A {
  public getValue() {
    return n1;
  }
}

The confusion is in thinking this defines a new class. This is a discussion of semantics, hence any class offered as a counter example must needs be a new class semantically, while the above is strictly syntax. The easiest way to approach the semantics of a class is as a function constructing independent, concurrent, finite automata. Now C doesn't define any new states, and doesn't define any new behaviour (state transitions), semantically then it doesn't define a new class --- mathmatically, C is still isomorphic up to congruence with A, so in a very real sense they are the same class. What C actually defines is a function. A new, if rather clumsy, projection on A returning n1. I had better make it clear that I'm not suggesting there is a non-clumsy way of doing this, rather that the reason why it is valid to want an C to be equivalent to a A is that C doesn't define a new class, just a new function. Hence it is a completely different case to B, which is a non-congruent class. If you have a concrete class that must support subclassing, instanceof is a bug.

Moreover this is exactly what we would expect when we consider what it actually means for two objects to be equivalent. Remember, an object is an FA, and as such there is a well established body of work on the meaning of equivalence, anyone interested should read up on simulation and bisimulation. Informally however the key is recognising that the bundling of state and behaviour provided by an object is not just something we get to ignore when it becomes inconvenient, at least not without losing correctness. That if we are serious about OO, we are not just answering the question "are we currently in the same state?", but "are we in the same state, and will we remain in the same state in response to the same stimula?". In other words, it doesn't matter that B.n1 == A.n1, if A and B have different behaviours they aren't the same object.

It becomes particularly important to recognise this when you face the prospect of also implementing Comparable. The problem here is that the contract for compareTo is that of a Total Order. The best you can manage on A U B is a Pre-order, and once again you are left with the prospect of subtle and obscure bugs. From the javadoc for Comparable:

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class's natural ordering, and the class's compareTo method is referred to as its natural comparison method. ... For the mathematically inclined, the relation that defines the natural ordering on a given class C is:
       {(x, y) such that x.compareTo((Object)y) <= 0}.
The quotient for this total order is:
       {(x, y) such that x.compareTo((Object)y) == 0}.
It follows immediately from the contract for compareTo that the quotient is an equivalence relation on C, and that the natural ordering is a total order on C. When we say that a class's natural ordering is consistent with equals, we mean that the quotient for the natural ordering is the equivalence relation defined by the class's equals(Object) method:
     {(x, y) such that x.equals((Object)y)}.

Yet after all this, I do share Adrian's pain in this. The unfortunate fact is that if the author implemented A.equals properly, but forgot to include an accessor to A.n1, there is no clean way of gaining access to it. If you do find yourself in this fix, you are left with either direct bytecode hacking (the JVM doesn't know about the access permissions, so you can just access n1 directly), or package injection (if n1 doesn't have private scope). Alternatively, if the author has followed Adrian's advice, it becomes impossible to implement B correctly, and as Adrian's use of instanceof is wrong at a semantic level, no amount of bytecode hackery will save you.

So yet again we come back to my original point. Either you are implementing an abstract class; or you are writing a concrete class and can support either subclass equivalence, or polymorphic equality. "But I need both"!? Tough; Java doesn't support both, and a good engineer knows to work within the limitations of their tools. That a sizable segment of the java community continues to ignore the limitations of their language by presenting incorrect code, pretending that both are achievable, is a sad indictment on the state of that community.

Bananas, Lenses, Envelopes, and Barbed Wire --- Section 3

2004-08-31T23:57:00.000+10:00

Apparently the paper gives all it's definitions in terms of the category CPO (Complete Partial Orders); not entirely sure what the difference is between a complete and an incomplete partial-order is, so the signifigance probably escapes me. Alot of this section is also reminisent of Piece's Introduction to Category Theory, so I should probably go back and reread that.

Functors: I remember functors being fun reading in Pierce. In this case we are interested in bifunctors and monofunctors; being types into types and functions into functions; and just functions into functions respectively. Both cases preserve id and compose.

Products: Standard category fare. We have the bifunctor (at least I assume it's a bifunctor, the paper dosn't say, but it meets the defn' above) || which takes two types and maps to the type of pairs of those two types (the paper's example: D||D' = {(d,d') | d <- D, d <- D'} --- I'm using <- instead of the 'element of' symbol, I really need to get a better blog editor, one I can type symbols into easily; (f||g)(x,x') = (f x, g x') ) and the expected projection and tupling combinators.

Sum: Interesting, latent-typing as a functor, or at least something that looks like latent-typing to me. Also interesting to note the use of bottom (_|_) to include undecidability.

 D|D'          = ({tag0}||D}) U ({tag1}||D'}) U {_|_}
(f|g) _|_      = _|_
(f|g) (tag0,x) = (tag0, f x)
(f|g) (tag1,x) = (tag1, g x)

Also worth noting the injection and selection operators:

i0 x = ({tag0},x)
i1 y = ({tag1},y)
f v g --- which applies f to arguments tagged 0,
                and g to arguments tagged 1.

Arrow: Some type of 'wrapping' function. The example given is (f -> g) h = g $ h $ f. This suggests some sort of injection into f -> g, but I'm not entirely sure how. Apparently this is related to curry, uncurry, and eval, but again I don't see the relationship.

Identity, Constants: Pretty much as expected. Lifting and Sectioning, will require a little more thought.

Interesting definition of a constant as a function of 1 -> A. 1 of course having only a single member void. Also given p::A->bool, and p? a = i0 a or i1 a if p a is true/false respectively, you have f v g $ p? modeling if p then f else g.

The rest of section 3 easily exceeds my grasp of category theory. We define a representation for categorical recursion, then move on to recursive types, specifically the least-fixed-point of a monofunctor. Three examples given are cons-lists, binary trees, and natural numbers.

Having covered to background theory, the paper moves on to definitions of our operators over arbitary data types. That will have to wait until I've recovered from section 3 ;).

Bananas, Lenses, Envelopes, and Barbed Wire.

2004-08-30T13:18:00.000+10:00

Read the first two sections of "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" over lunch. So far a very interesting paper, although looking ahead, I suspect it will probably endup exausting my understanding of category theory reasonably soon.

The paper has 6 sections. Section 1 is a short introduction, motivation, and review of the literature; section 2, a short introduction to the four recursion operators cata, ana, hylo, and para; section 3 draws from category theory to outline a theory of algebraic data types used in the rest of the paper; section 4, a formal definition of the operators introduced in Sect2 using the theory developed in Sect3; section 5 extends some of sect4 to parametized types; section 6 is the conclusion, acknowlegements, and references.

The paper aims to define a series of four 'recursion operators'; cata, ana, hylo, and para, and then use them as the basis for a functional programming calculus. These operators correspond to constructors for cata-, ana-, hylo-, and paramorphisms respectively. The reason for doing this is that unstructured recursion isn't amenable to structual analysis and manipulation, so it is preferable to generalise various recursive forms into various forms of structured recursion before trying to develop the calculus.

The examples given are all with respect to your standard inductive list data-type:

A* -> Nil | Cons(A A*)

(It's possibly worth noting that this is a direct algebraic analogue to your standard linked-list definition in an imperative language)

Cata

Constructs a catamorphism, more generally known as a right fold. Think of it as collapsing a list into a value. It takes two parameters, a binary function and an identity.

h = cata(b, .) 
  ->  h Nil          = b
      h (Cons(a,as)) = a . h(as)

and

h :: A* -> B
b :: B
. :: A -> B -> B

cata is denoted using 'banana brackets': (|b, a|). A good example of a catamorphism is length().

length = cata(0, (+) $ 1)  
  note: (+) $ 1  is the right assoc composition of addition and the 1
        function (which ignores its argument and returns 1)
 
proof by substitution:

length Nil = 0
length (Cons(a,as)) =  ((+) $ 1) a length(as)
                    => (+) 1(a) length(as)
                    => 1 + length(as)

Which is of course the standard definition of length::A* -> N

Ana

Constructs an anamorphism, more generally known as an unfold. This is naturally the inverse of a fold, and expands a value into a list. It takes two parameters, an induction function and a termination predicate.

h = ana(g, p) 
  ->  h b = | p b  -> Nil
            | else -> Cons(a, h b') where (a, b') = g b

and

h :: B -> A*
g :: B -> (A B)
p :: A -> boolean

ana is denoted with 'lense brackets' ([g, p]). A good example of an anamorphism is zip, an easier one to follow is count(n), which returns the list of numbers incrementing from n.

count n = ana(g, False) where False a = false,
                              g a = (a, a + 1)

Hylo

Constructs a hylomorphism. This is your classic inductive recursion from one value to another (think factorial, or fibonacci). This can be represented as an anamorphism that builds the recursive call-stack, followed by an catamorphism that folds the stack into a result.

h = hylo(c, ., g, p) 
  ->  h a = | p a  -> c
            | else -> b . (h a') where (b, a') = g a

and

h :: A -> C
c :: C
. :: B -> C -> C


g :: A -> (B A)
p :: A -> boolean

hylo is denoted using 'envelope brackets': [|(c, .), (g, p)|]. A good example of a hylomorphism is factorial.

fact n = [|(1, *),(g, p)|] where g n -> (n, n - 1),
                                 p = | 0    -> true
                                     | else -> false

substitute:

fact = hylo(c, ., g, p) 
  ->  fact n = | n == 0  -> 1
               | else    -> b * (fact a') where (b, a') = (n, n - 1)
            => | else    -> n * (fact (n - 1)).

Which is of course the classic factorial

Para

Constructs a paramorphism. This is the weakest description of any of the four. I can't really claim to understand para, but it is immediately recognisable as structured recursion over inductive datatypes. I'm hoping that the definition will be provided later in the paper, but unlike the other three, this intro section only provided examples. It does however cite another paper by one of the authors Meertens, Paramorphisms. The example for numbers (Num ::= 0 | 1 + num):

h = para(b, .) 
  ->  h 0       = b
      h (1 + n) = n . (h n)

para is denoted using 'barbed-wire brackets': [<b, .>]. Factorial can be written as a paramorphism as:

fact n = [< 1, (g) >] where n g m -> (1 + n) * m

Object.equals()

2004-08-27T23:48:00.000+10:00

Like many languages Java provides two equality methods to test objects for equivalence. The first is accessed via the '==' operator and does a simple heap reference comparison. The other is a standard method on Object, equals() which is intended to be overridden by the programmer to perform a value-based comparison. Now the equivalence operator is defined by the language spec, and ultimately implemented by the JVM developers, hence not our concern. Unfortunately the java community has failed to properly document the subtleties involved in writing a correct equals method, and so I continue to come across incorrect implementations and worse, incorrect recommendations.

But first we have to understand what we are dealing with. Fundamentally when we are defining an equals method on a class A, what we are defining is an Equivalence Relation over the set of all objects of class A. This is important because it highlights that we can define our equals method to return anything we want provided we meet three rules.

Reflexivity: a.equals(a) -> true
Symmetry: a.equals(b) <-> b.equals(a)
Transitivity: a.equals(b) && b.equals(c) -> a.equals(c)

If we break any of these rules someone will suffer subtle and devious bugs.

Node: To save typing I'm going to leave out the hashCode method in each of these examples, but be aware if you override equals() you *must* override hashCode() to match.

One consequence of the requirements is that we must ensure that any test we use in our equals implementation meets these requirements as well. So lets consider the standard mistake:

class A {
  int n1;
  public boolean equals(Object o) {
    if (!(o instanceof A)) {
      return false;
    } else {
      A rhs = (A)o;
      return this.n1 == rhs.n1;
    }
  }
}

This is a very common implementation of equals, it has even made its way into a number of Java books. Worse, the bug only manifests in the presence of implementation inheritance of concrete classes.

class B extends A { 
  int n2;
  public boolean equals(Object o) {
    if (!(o instanceof B)) {
      return false;
    } else {
      B rhs = (B)o;
      return this.n1 == rhs.n1 && this.n2 == rhs.n2;
    }
  }
}

To demonstrate the bug lets define a simple function on A's:

static printEqual(A a1, A a2) {
  if (a1.equals(a2)) {
    System.out.println("EQUAL");
  } else {
    System.out.println("NOT-EQUAL");
  }
}

And test it:

  A test1 = new A();
  A test2 = new B();
  printEqual(test1, test2);
      => Prints "EQUAL"
  printEqual(test2, test1);
      => Prints "NOT-EQUAL" !!!!

And we've broken symmetry. This will bite you. There is no situation when an asymmetrical equality is not a bug. Unfortunately it is scary how many places on the net this is presented as the exemplar equals() implementation.

So what does a correct equals method look like. Well there are two. The first is very straight forward, and should be the default choice.

class A {
  int n1;
  public boolean equals(Object o) {
    if (o == this) {
      return true;
    } else if (o == null || !getClass().equals(o.getClass())) {
      return false;
    } else {
      A rhs = (A)o;
      return this.n1 == rhs.n1;
    }
  }
}

class B extends A { 
  int n2;
  public boolean equals(Object o) {
    if (!super.equals(o)) {
      return false;
    } else {
      B rhs = (B)o;
      return this.n2 == rhs.n2;


    }
  }
}

Now test1 != test2 AND test2 != test1. Also, by delegating from B to A at the start of B::equals() we ensure any inaccessible state in A is handled appropriately, and more importantly, that the equality code for A isn't duplicated in B. If you can't delegate from B->A like this, then it suggests that your B isn't actually an A, and you should check your class design (you probably should be using delegation rather than inheritance).

There are times however when you would really like an B to compare equal to an A. The classic example is the circle/ellipse or square/rectangle shape examples. It would be really nice if an ellipse with equal axes compared equal to an equivalent instance of a circle sub-class. The way we can achieve this is to recognise that the core requirement of a correct equals implementation is that the operations we use to implement meet the same reflexivity/symmetry/transitivity requirements as the method itself. Next note that instanceof is only asymmetric in the subclass; and in fact any operation in the subclass will lead to asymmetry! So if we do need subclassed equality, we can't permit a subclass to override the equals() method.

abstract class Shape {
  public boolean equals(Object o) {
    if (o == this) {
      return true;
    } else if (o instanceof Shape) {
      // !! Note: instanceof is safe here as Shape is abstract.
      Shape rhs = (Shape)o;
      return [shape specific comparison --- maybe position];
    } else {
      return false;
    }
  }
}

class Ellipse extends Shape { 
  int minor, major;

  public int getMinor() { return minor; }
  public int getMajor() { return major; }

  // !!! NOTE THE USE OF *final* to prevent asymmetry!
  // Also note the exclusive use of accessors.
  public final boolean equals(Object o) {
    if (!super.equals(o)) {
      return false;
    } else if (getClass().equals(o.getClass())) {
      Eclipse rhs = (Eclipse)o;
      return this.getMajor == rhs.getMajor()
          && this.getMinor == rhs.getMinor();
    } else {
      return false;
    }
  }
}

public Circle extends Ellipse {
  public Circle(int radius) { major = minor = radius; }
  public int getRadius()    { return major; }
}

Note that this is probably a rather clumbersome hierachy. A better approach would be:

public abstract class Ellipse {
  public abstract int getMajor();
  public abstract int getMinor();
  public final boolean equals(Object o) {
    if (!super.equals(o)) {
      return false;
    } else {
      Eclipse rhs = (Eclipse)o;
      return this.getMajor == rhs.getMajor()
          && this.getMinor == rhs.getMinor();
    }
  }
}

public class EllipseImpl {
  int major, minor;
  ...
}

public class CircleImpl {
  int radius;
  public int getMajor() { return radius; }
  ...
}

Note that an CircleImpl will still compare equal with an appropriate EllipseImpl.

Please. If you are programming Java, believe me, these really are the only two options open to you. I really am very tired of tracking down the subtle bugs that result when this advice is ignored.

SICP Lectures.

2004-08-12T23:41:00.000+10:00

A friend of mine is studying CS at UQ, and this year they are using The Structure and Interpretation of Computer Programs as a first year text. I am personally pleased to see UQ buck the 'vocational education' trend that has been decimating IT degree courses recently. OTOH it does make life a little tougher on the students, and although this is a good thing, there are ways of making life a little easier. One is to point students at the videos of SICP lectures given by Abelson and Sussman at MIT. I have watched them and they are very good, I highly recommend them to anyone approaching the book looking for some extra insight into the material. It is also worth pointing at the online version of the book in case anyone wasn't aware it was available.

Cale the Corporatist Corsair

2004-08-12T18:49:00.000+10:00

Apparently the BSA are looking for a new name for their new mascot. I'm a little surprised at their honesty, personally I find a corporate extortionist weasel who attempts to indoctrinate tech-savvy kids into acquiescing to the corporatist annexation of their public-domain rights, rather appropriate for the BSA.

Personally I'm pushing for "Cale the Corporatist Corsair".

Why Java sucks.

2004-08-09T18:01:00.000+10:00

Ok, so this could just have easily titled 'Why [C/C++/Ada/...] sucks', but I use Java more than either of these atm, so I went with Java. Back on lambda the 'Why types are interesting' thread continues unabated. However this post by Paul Snively grabbed my attention. It is definately worth reading in its entirety, but two paragraphs in particular stand out.

[Alan] Kay takes a hard opposite perspective to mine on the static typing vs. late binding question, saying, in summary (not a direct quote), "What to do until software engineering is invented... do late binding, which means being able to make the changes easily." Actually, perhaps it's not really opposite, since he could be interpreted to mean "either do software engineering if you can or make the cost of changes as low as possible, which is best done at the current state of the art with late binding." That is, get out of these tools that do neither software engineering nor dynamic change well (C, C++, Java...) and either head for software engineering (SML, O'Caml, Haskell, Concurrent Clean, Epigram, Alice...) or head for late binding (Common Lisp, Scheme, Smalltalk, Oz...). Formulated that way, I can't help but agree with him, and merely choose to focus on heading towards software engineering after spending decades in late binding.

At the end of the day, I want modern type theoretic ideas in my programming language so that, at compile time, I can:

Know that my code is deadlock-free.

Know that my code is race-condition free

Know that my code doesn't leak authority.

Know that my code is upgradable without violating encapsulation or leaking authority.

Will parallelize across multiple processors automagically when possible and serialize when it's not.

Will not throw an exception that will not be caught and handled.

Will have inferred all memory allocation and deallocation and do it automagically for me, letting me know if the dynamic characteristics of my code require the linking of a garbage collector.

Will let me know if I attempt to take the tail of an empty list. :-)

In case anyone dosn't realise, all the above points are already possible, although AFAIK not yet demonstrated possible at the same time.

Interesting scripting language for Java.

2004-08-09T12:57:00.000+10:00

I had a quick look at groovy a few months back when it was announced on lambda. To be perfectly honest I wasn't particularly impressed. If I want a latent-typed, 'agile' scripting language, and don't want to fight too hard to be allowed to use it, I will use Jython; or if I'm writing for myself, or have a tech-savy boss, I'll use the scripting language, aka scheme (specifically: SISC or possibly JScheme). As far as I can tell it's just Yet Another Scripting Language. I mean, what's the point!?

Then I came across a comparison between groovy and another JVM scripting language, Nice. Bryn Keller does a quick comparison between groovy and nice on his blog. So what makes nice interesting, when groovy is so yawn-worthy? Well nice is statically typed! It looks like a serious attempt at dragging the java world into the world of real compile time type safety --- a world without NullPointer/ClassCastExceptions, and with the free-flowing syntactic style of your traditional latent-typed languages.

As an example compare the following (from the xoltar post):

Groovy

if (customer.orders.any { it.amount > 1000 && 
	it.product.type == "cheese"} ) {
  doSomething();
}

Nice

if (customers.orders.any(Order ord => ord.amount > 1000 && 
	ord.product.type == "cheese")) {
  doSomething();
}

Which given you can infer the type of ord from its use is intended to shortly become:

if (customers.orders.any(ord => ord.amount > 1000 && 
	ord.product.type == "cheese")) {
  doSomething();
}

Which differs from the groovy example in only the trivial matter of being able to name the parameter to the closure; and in the not-at-all-trivial matter that the compiler will ensure static type saftey at compile time!.

Just skimming the nice website, I still suspect I will find ML a nicer language, still a language targeted at interoperation with Java that supports: real parametric-types, proper closures, multiple-dispatch (goodbye visitor pattern ;), and tuples; all in a statically typed language with HM inferencing. What's not to like?

Tired.

2004-08-07T23:07:00.000+10:00

I just finished my third first-aid duty at the queensland royal show (aka Ekka). It was only 6 hours, so I don't know why I'm feeling so exhausted. For some reason duties seem to tire me out, this one wasn't even particularly eventful (fortunately); I wrote up incident reports for two almost identical injuries from one of the sideshow rides when I learnt there had been more than my two cases. Hopefully something will be done about it, I hate to see kids hurt. Was assigned ringside during the leadup and through the fireworks which was nice, although the fireworks were rather disappointing they were still fun.

I wrote some quick examples of continuation passing style over lunch before I went on duty, but I'm too tired to write the commentary now, so I'll do that tommorrow or monday and post part-3 then. Byron will be pleased though, one of them is a simple regex engine which I think comes out rather nicely using CPS.

For now it's bedtime I think ;).

Continuations - part 2

2004-08-06T00:42:00.000+10:00

Back to my attempt to explain continuations.

What is a continuation? The short answer is "What the program should do next". Another way of putting it would be "Everything the program hasn't done yet, wrapped up in something that looks sort-of like a function". Now I'm going to make the possibly arrogant assumption that as that wasn't sufficient explaination for me, that wasn't sufficient here.

Let's go back and reconsider an LCO example, this time we want to write a sigma function: takes a non-empty list of numbers and returns the sum of the list.

; (sigma '(1 2 3 4)) -> 10
(define (sigma lst)
  (if (null? (cdr lst))
      (car lst)
      (+ (car lst) (sigma (cdr list)))))

Now the astute reader will be wondering why I've defined sigma like this, associating to the right, rather than to the left (which would have been simpler). The reason for this is that this function cannot be trivially converted into the accumulator form we used in the previous LCO example. More importantly, there are a number of recursive functions which are easier to define associating to the right than the left (I recommend trying to use append in place of + to define map in this manner). Now it would be nice to be able to manage this sort of function in constant stack, and this is a nice simple example to demonstrate how we can do exactly this. In case any readers are wondering what I mean by associating left vs. right, I suggest you compare the above to the left-associative version below and consider the order in which the elements of the list are combined.

(1 + (2 + (3 + 4))) - right assoc
(((1 + 2) + 3) + 4) - left assoc

; Left associative
(define (sigma lst)
  (letrec ((sigma-iter
    (lambda (lst accum)
       (if (null? lst)
           accum
           (sigma-iter (cdr lst) (+ accum (car lst)))))))
  (sigma-iter (cdr lst) (car lst))))

(Note we could have defined sigma-iter the same way we did earlier, as a global with (define...), however it really is a helper function, and so is better defined locally to sigma. --- besides, it also gives me a chance to introduce lambda, which we will be using later)

The secret to converting the right-associative version into LCO is to recognise that the last thing we want to do before returning is call sigma on the tail of the list. Now this looks difficult, as the last thing we need to do is the addition. Still, I'm a great believer in wishful thinking, so I'm going to pretend I have an function that will take the result of the recursive call and finish off everything I was supposed to do next for me. Then I can pass that into the next call to sigma and have it finish for me.

(define (sigma lst finisher)
  (if (null? (cdr lst))
      (finisher (car lst))
      (finisher (sigma (cdr lst) finishing-function))))

Opps, now we have a call to 'finisher' in the road. Still that's ok, we can just pretend that we have a new finishing-function each time that will both handle the addition for this call, and the call to the finisher we were passed.

(define (sigma lst finisher)
  (if (null? (cdr lst))
      (finisher (car lst))
      (sigma (cdr lst) new-finishing-function)))

Now this is looking better, all we have to do is work out how to define an appropriate finishing function and we're done. Before we do that however it is worth noting (as most of you will have noticed by now anyway) that the new-finishing-function's definition "finish off everything I want to do next" is just a rephrasing of the definition I gave for a continuation at the start.

Lets compare the non-tail-recursive call to the continuation based tail-recursive call:

; non-tail-recursive
(+ (car lst) (sigma (cdr lst)))
; tail-recursive
(sigma (cdr lst) continuation)

Remember the definition of the continuation is that it will be receiving the result of the recursive call to sigma as a parameter so lets call that x and substitute into the non-tail-recursive version:

; let x <- (sigma (cdr lst))
(+ (car lst) x)

This will calcuate the result of our call, but we have one thing left to do, we have to return the result to our caller. However our caller has finished (its call to us was a tail-call remember), and the destination of our result was passed as a continuation. So we don't actually return as much as make a tail-call to the continuation (note this is a major reason why LCO is so useful, if we didn't have LCO our stack frame would be leaked, but with LCO there is no leak).

; pass (+ (car lst) x) to the continuation.
(continuation (+ (car lst) x))

So what we need is to define a small function that can capture this idea and pass this into the recursive call to sigma.

; Scheme
(lambda (x) (continuation (+ (car lst) x)))

# Python - just in case it's useful understanding the closure above.
# NOTE: As python dosn't provide LCO this *will* leak stack.
lambda x: continuation(lst[0] + x)

Now put the pieces together and we're almost there:

(define (sigma lst continuation)
  (if (null? (cdr lst))
      (continuation (car lst))
      (sigma (cdr lst)
	     (lambda (x) (continuation (+ (car lst) x))))))

The next step is to restore the original signature, and make this CPS version a helper function (along the way we rename continuation to k, it's shorter ;).

(define (sigma-helper lst k)
  (if (null? (cdr lst))
      (k (car lst))
      (sigma (cdr lst) (lambda (x) (k (+ (car lst) x))))))

(define (sigma lst)
  (sigma-helper lst initial-continuation))

Final step.... what do we want as the initial-continuation? Well it will be passed the result of the outer sigma, and what we want is the result of the outer sigma.... sounds like a job for the most trivial function you can think of; also known as the I combinator, let me introduce id()

(define (id x) x)

(define sigma lst)
  (sigma-helper lst id))

And we're done. Lets step back and take a look at what we've done. We have taken a non-tail-recursive function and split into two pieces seperated by a tail-call. We execute the first half, and pass the second half as a parameter, a continuation, to the tail-call. It is worth noting three points:

There is nothing special about the precise point we decided to split the function, at any point we could have wrapped the rest of the function in a continuation and passed it into another function, we'll come back to this when we discuss call-with-current-continuation later
The continuation ends up being an ordinary function. We can save this function and call it as many times as we like; from other places than inside the sigma call. After all, once we have it, it's just a function. This dosn't make much sense with sigma, but other algorithms do make use of this trick. Again, we will come back to this with call/cc.
The sigma-helper function never returns! In every case the helper function substitutes return with a call to its continuation parameter. For this reason the sort of continuation used in this example is called a return-continuation. Every return in every function can be treated as a call to an implicit return-continuation. There are other uses for continuations, return-continuations are just the easiest to grasp, hence the subject of this post. Again, I'll come back to other uses when I discuss call/cc.

This technique where you pass return-continuations around instead of returning normally is called CPS. It is a powerful approach to programming that is a common transformation, especially in compilers for functional languages.

I would also appreciate any feedback on this introduction, both positive and suggestions for improvement. Hopefully I'll have time to do a worked example and a discussion on call/cc soon.

Python and LCO.

2004-08-05T13:35:00.002+10:00

Clinton makes a valid point I should have made clear myself. Python dosn't support LCO, and probably never will. I am only using python as a convenient language to provide anyone who dosn't already know scheme with a parallel implementation to help them pick up enough of the language to follow my later discussions on continuations.

I apologise to anyone who may have been confused.

Continuations - part 1.

2004-08-05T00:24:00.000+10:00

Ok, so why did I write a post on last-call-optimisation? Well I find it very difficult to explain continuations to someone who dosn't understand LCO, so I thought I should post a quick example of LCO before this. Of course the reason behind this sudden urge to actually fulfil my promise to explain continuations here is Lambda again. This time an extended discussion on continuations sparked by Keith Devens' request for help understanding the things. Itself sparked by a particularly interesting analogy by Luke Palmer in news:perl.perl6.language, now forever dubbed the "Continuation Sandwich" --- the relevant part of his post is:

Say you're in the kitchen in front of the refrigerator, thinking about a sandwitch. You take a continuation right there and stick it in your pocket. Then you get some turkey and bread out of the refrigerator and make yourself a sandwitch, which is now sitting on the counter. You invoke the continuation in your pocket, and you find yourself standing in front of the refrigerator again, thinking about a sandwitch. But fortunately, there's a sandwitch on the counter, and all the materials used to make it are gone. So you eat it. :-)

Now before we begin I'm going to deal with continuation-passing-style and call-with-current-continuation seperately, but as a taste of what we're in for interested parties can check my CPS-in-Java example on the haskell.org wiki, or the most lucid description of call/cc in Chapter 13 of Teach Yourself Scheme in Fixnum Days.

In the meantime, it's 0021 hours here, so I'm going to sleep first, and finish this later.

Last-Call-Optimisation

2004-08-05T00:11:00.000+10:00

First lets consider the old hoary chestnut, the factorial.

; Scheme
(define (fact n)
  (if (zero? n)
      1
      (* n (fact (- n 1)))))

# Python
define fact(n):
  if not n:
    return 1
  else:
    return n * fact(n - 1)

Note: I am going to have to use scheme later, so for the next few examples I'll be using scheme and python together to give non-schemers a basis for comparason.

Now this is a very straight forward recursive definition of the function. The only trouble is that we are going to grow the stack proportional to n. So we end up with the following (abbreviated) call-tree:

fact 4
  fact 3
    fact 2
      fact 1
        fact 0
        * 1 1
      * 2 1
    * 3 2
  * 6 4
-> 24

Note that for (fact 4) we end up with five stack frames on our call stack, and unfortunately there is no alternative as the code is written. We can however eliminate this efficiency by converting to an iterative version:

; Scheme
(define (fact-iter n accum)
  (if (zero? n)
      accum
      (fact-iter (- n 1) (* n accum))))

(define (fact n)
  (fact-iter n 1)

# Python
def factiter(n, accum):
  if n == 0:
    return accum
  else:
    return factiter(n - 1, n * accum)

def fact(n):
  return factiter(n, 1)

Now the call stack looks like:

fact 4
  fact-iter 4 1
    fact-iter 3 4
      fact-iter 2 12
        fact-iter 1 24
          fact-iter 0 24
-> 24

Which dosn't look very useful until you consider that as each call to fact-iter returns, it's caller simply passes the resulting value up the call-chain. In otherwords, the caller's stack-frame is never used after it calls the next fact-iter in the chain; and what is never used dosn't need to be kept. This is called last-call-optimisation, and is a very common optimisation used by many languages to make the above code as efficient as the while loop solution traditionally taught in imperative languages:

/* C */
int fact(n) {
  int accum = 1;
  while (n) {
    accum = accum * n;
    n--;
  }
  return accum;
}

In fact the traditional code generated by a LCO supporting compiler looks alot like this:

/* MIML ;) */
int fact(n) {
  int accum = 1;
factiter:
  if (n == 0)
    return accum;
  else
    accum = n * accum;
    n = n - 1;
    goto factiter;
}

Which is pretty much exactly what the while loop would compile to. This still leaves the question: "Why?", what's wrong with the while loop?

The answer to this is that factorial is defined recursively:

       / 0 -> 1
  n! = |
       \ n -> n * (n - 1)

and it is trivial to compare this definition to the first recursive example and check it is correct. The tail-recursive expression in the second example isn't as easy to confirm, but it is at least in a form amenable to a trivial inductive proof by inspection. Because the while loop dosn't abstract away the inductive step but incorperates it into the loop pre/post-conditions and invariants, it is less amenible to proof. In fact the three examples can be seen as reducing levels of abstraction: moving away from the problem domain (a maths definition) towards the raw metal; and almost a tautology, the closer we can stay to the problem domain the better.

Now this is great for linear algorithms, or algorithms that process linearly recursive datastructures (fancy name for linked-lists ;). However consider a pre-order traversal of a binary tree? This can be made tail-recusive, but it is a fair bit more involved, and the subject of my next post.

Rdf, indices, hypergraphs, and iTql

2004-08-04T15:45:00.000+10:00

An rdf database is a set of declarative statements: [subject predicate object]. Now the traditional way of representing this is as a traditional directed-graph with 'object' nodes with 'predicate' edges linking them. This is a useful representation which successfully visualises most rdf-graphs. Unfortunately for visualisers, for rdf to be useful you need to be able to attach semantics to predicates, and the logical way to do this is to make statements. A quick example:

Fred parentOf John
John parentOf Lucy
John parentOf Jane

This becomes much more useful if we can utilise statements such as

parentOf   subsetOf    relativeOf
relativeOf hasProperty transitive
relativeOf hasProperty symmetric

which allows us to match against match(Jane relativeOf $x) and get back { x=Fred, John, Lucy, Jane }

This is all well and good until you try and visualise the union of these two graphs (often called base-facts, and schema). The first problem you face is multiple edges between the verticies - forcing you to move to a 'directed-graph with named edges'; not too hard to visualise, but it isn't looking too much like a traditional graph anymore. The real kicker comes when you try and visualise the relationship between parentOf and relativeOf, now you have an edge between two edges -- and we're not in Kansas anymore Toto.

So what do we have? It is certainly 'graph-like', but it long ago ceased to be a traditional graph. More importantly, we haven't started considering 'statings', 'named-graphs', or 'reification'. The real problem is that a predicate is a valid vertex in the graph; an equal partner (conceptually) with its more numerous subject and object bretheren. Fortunately we're not the first to consider this problem. First consider the definition of a graph (preempting my summary of Trudeau Ch 2).

A graph is an object consisting of two sets called its vertex set and its edge set. The vertex set is a finite nonempty set. The edge set is a set of two-element subsets of the vertex set.

Looking at the definition, it becomes quite obvious that what we need is for the edge set to contain three-element subsets of the vertex set. This conveniently has a name: a 3-hypergraph. More importantly it can be easilly expanded to support named-graphs by using a 4-hypergraph, and as Paul Gearon noted, this has immediate relevance to the indicies kowari uses. It also has immediate relevance to crystalising iTql's semantics, allowing us to integrate the trans(), walk(), and the new ???() graph constraints --- we're still arguing over a name for what I like to call exclude(); and the original Constraint constraint (include()???). Each of these then returns an element of the powerset of VxVxV (where V is the vertex set). The elements of these resolved constraints are then statements, and as such amenable to predicate logic; and iTql provides conjunction and disjunction operations (and, or) and returns a sum-of-products solution to the resulting compound predicate.

So iTql provides four levels of operations:

Graph Operations: union, intersection, and disjoint-union of 3-hypergraphs in the FROM clause. Note the result of this is actually a 4-hypergraph.
Graph Constraints: inclusive, transitive, reachability, and soon exclusive constraints against a specific 4-hypergraph (by default the graph returned from the FROM clause). Note these are parametised by variables, and the result is a set of variable bindings that substitute to statisfy the constraint. These form the primitive constraints in an iTql WHERE clause.
Predicate Logic Expressions: conjunction and disjunction of variable binding sets, and type specific boolean functions (ie. comparison operators >, <, ==, etc) forming the rest of the WHERE clause. The result of this is a product-of-sums we represent as an implementation of the 'Tuples' interface. It is probably worth noting two things. First, a Tuples fails to be a relation only because the individual variable binding sets have differing cardinalities; we fake this by padding with a unique UNBOUND value which carries DONT-CARE semantics. Second, this can only happen when the expression includes a non-union compatable disjunction.
Projection, Aggregation, and Subqueries: ie. the SELECT clause: a list of functions to apply to the padded-product-of-sums returned by the WHERE clause; the results of which are zip'ed into the conventional tabular format most application developers find most useful.

Normal people in bad situations.

2004-07-31T22:09:00.000+10:00

Clinton wonders aloud about the behaviour of the Khmer Rouge interrogators. Unfortunately this sort of behaviour is both normal, and predicted; anyone who doesn't understand this needs to take the time to read about such experiments as "The Stanford Prison Experiment"

Welcome to the Stanford Prison Experiment web site, which features an extensive slide show and information about this classic psychology experiment, including parallels with the recent abuse of Iraqi prisoners. What happens when you put good people in an evil place? Does humanity win over evil, or does evil triumph? These are some of the questions we posed in this dramatic simulation of prison life conducted in the summer of 1971 at Stanford University.

Why types? -- lambda, the main course

2004-07-30T23:41:00.000+10:00

First the surreal, then possibly one of the most interesting threads I think I've seen on lambda. Probably why I'm now clocking 10 hours catching up on lambda, and not only am I still at it, but I'm still motivated.

In Why type systems are interesting, Anton van Straaten lifted a comment by Luke Gorrie to a toplevel discussion:

If someone could next show what makes type systems so interesting in terms that I'll understand then I'll be well on my way into the modern functional programming world.. :-)

and in doing so launched a fascinating thread that has seen 44 posts so far and launched at least one independent thread. I seriously recommend this thread to anyone who considers themselves a serious programmer. A few highlights:

Anton managed to summarise the thread in the introduction:

When you write code, even in the most dynamic language, you always know something about the types of the values you're operating on. You couldn't write useful code otherwise - if you doubt that, try coming up with some examples of operations you can perform on a value without knowing something about the type of that value. Type systems provide a way to encode, manipulate, communicate and check this type knowledge. In an earlier thread, you mentioned that you write the types of functions in the comments. That's an informal type system! Why do you do use a type system? Because type systems are useful, important, and as a result, interesting.

Note that the first paragraph is deceptively simple. Consider the most common example of a generic data-structure, the list. If you have a truely hetrogeneous list, one whose contents are truely untyped, you your list is actually indistinguishable from a natural number! The only operations you can perform on a completely typeless list form the monoid ([], Lists, concat) which of course form a monoid isomorphic with (0, Naturals, +), and supports the Isomorphic Arrow length() mapping lists and naturals. For a fuller discussion of this I recommend Basic Category Theory for Computer Scientists, Benjamin Pierce (and before I get asked, I borrowed it from my local university library).

Anyone who has been reading lambda much immediately recognises Frank Atanassow, his writing style is distinctive, and his opinions both strongly held, and consistent. One of the really exciting things about this thread was that Frank's comment Rebuttal finally managed to clarify for me, what he has been talking about these past months. Although if you haven't been reading lambda much and intend to read that post I would strongly advise you read No contraints[sic], and keep in mind Anton's comment in Constraints

if b then 42 else "ha!" becomes something like: if b then Num 42 else Str "ha!" ...where Num and Str are type constructors for the Univ type. This is kind of ironic, considering that it's the latter language that's supposed to be able to inference types. You can think of dynamically-typed languages as a shortcut syntax for creating programs which rely on a universal type. This demonstrates that statically-typed languages can be less expressive than dynamically-typed ones. emphasis mine

It was also very amusing to watch a curveball from Julian Squires who wanted to know how static type systems interact with his desire to actively develop an executing application (think smalltalk, or possibly php) in Re: Software development as a static activity. Personally I'm not sure any existing languages combine a modern static type system with the ability to do runtime modifications. Still even if you only consider static type checking a safety net, surely one time you would really really like to have it is when doing something as delicate as runtime development.

Just surreal.

2004-07-30T22:40:00.000+10:00

The past couple of evengings have been 'catch up on lambda' evenings. So I only just stumbled across one of the most surreal threads I think I've ever read. Old computer science and technical books worth searching for certainly looked promising. It started will, and I will definately have to keep an eye out for "ACM Turing Award Lectures: The First Twenty Years". Then someone mentioned generating functions and type derivatives, and before too long I end up ambushed with

The |x| < 1 condition is a red herring in this case. It is quite standard to work with generating functions in the context of the ring of formal power series k[[x]] with coefficients in a field k. (You can generalize the heck out of this definition.) A formal power series is a polynomial except for the fact that we don't require the elements of its coefficient sequence to become zero after a certain point. We define addition in this ring in the obvious way and multiplication by convolution of the coefficient sequences, just like you would in a polynomial ring.

Ouch! My poor head. I still need warning and a good runup when approaching this sort of thing.

Trudeau: Ch 1. Maths, Games, and Education.

2004-07-30T22:13:00.000+10:00

I'm currently reading chapter 4 of Trudeau, but lets do this properly and I'll start with chapter 1.

Chapter 1 is the introduction, and like all introductions everywhere, is largely content free --- or more precisely, is the realm of opinion and motivation. But, before I discuss Trudeau's opinion of why I should read this book, Introduction to Graph Theory has what is probably the most excuberant blurb I think I have ever read on a textbook.

This delightfully written introduction to graph theory offers a stimulating excursion into pure mathematics. It is aimed at those whom the author calls "the mathematically traumatized," but it is a treasury of challenging fun ... "The topics are so well motivated, the exposition so lucid and delightful, that the book's appeal should be virtually universal....[sic] Every library should have several copies"

Wow, somebody was certainly in a good mood. You could almost be forgiven for forgetting that you're actually reading about a textbook. I think this gives new meaning to 'rave review'.

Anyway, back on topic, Trudeau would like us to approach pure mathematics as a game.

Basically pure mathmatics is a box of games. At last count it contained more than eighty of them. One of the is called "Euclidean geometry".

He then goes on to approach the closed-world nature of pure maths; something I as an engineer struggle to deal with.

Games have one more feature in common with pure mathematics. It is subtle but important. It is that the objects with which a game is played have no meaning outside the context of the game. ... You may balk at this, since for historical reasons, chessmen have names and shapes that imply an essential correspondence with the external world. The key word is "essential"; there is indeed a correspondence, but it is inessential. ...this interpretation of the gaem, like all others, has nothing to do with chess per se.

So in a similar way, while the words plane, point, and line suggest real-world analogues, it is only an implied interpretation. In Euclidean geometry they are axiomatic, with specific properties, but without definition.

...no one knows what planes, points or lines are, except to say that they are objects which are related to one another in accordance with the axioms. The three words are merely convenient names for the three types of object geometers play with. Any other names would do as well.

Still the most interesting paragraph in the introduction is right at the beginning. Along with a number of my peers, I cruised through High School mathematics. In fact I largely finished read Lord of the Rings, and War and Peace in my maths classes. It seemed that my teachers would take about a week to teach a days work, and yet it was obvious that dispite the slow pace many of my classmates were still being left behind. Naturally as a geek, I have spent a fair amount of time analysing and self analysing to try and understand the difference. While I was still at school, I just assumed I was just more intelligent. However experience has since taught me I wasn't. Which reopens the question, "What was I doing that made me so much more effective at learning High School maths?". I certainly didn't work harder. I believe Trudeau's introduction gives us a clue:

To understand what mathematics is, you need to understand what pure mathematics is. Unfortunately, most people have either seen no pure mathematics at all, or so little that they have no real feeling for it. Consequently most people don't really udnerstand mathematics; I think this is why many people are afraid of mathematics and quick to proclaim themselves mathematically stupid. Of course, since pure mathematics is the foundation of applied mathematics, you can see the pure mathematics beneath the applications if you look hard enough. But what people see, and remember, is a matter of emphasis. People are told about bridges and missiles and computers. Usually they don't hear about the fascinating intellectual game that lies beneath it all.

My current hypothesis is that my gift was the ability to see past the smokescreen of 'applications', and rote-work, to the fundamental patterns and structure of the pure mathematics underneath. This would also explain why I find such a return on time spent studying Computer Science --- and consequently my interest in language semantics and hence why I'm reading a book on graph theory largely for fun. So assuming I am right, can this insight into how a 'naturally gifted' high-school maths student attains their aptitude be used to improve the pedalogy of our existing maths curriculums?

Shiny Papers.

2004-07-30T11:32:00.000+10:00

I'm a reading magpie. I find it almost impossible to browse citeseer, or a amazon without walking away with at least a half dozen new books, and twenty or thirty new papers to read. Citeseer is particularly bad... 'Ooo shiny paper', , , and I have yet another pdf to add to my already impossibly huge collection. So I've decided to be a little more systematic about my reading.

I'm going to start posting summaries of the articles, papers, and books I'm reading. This will hopefully result in a permanant record for my own reference, and if I'm lucky, suggestions for additional reading.

So for starters I thought I would post my current (heavilly abbreviated) reading list.

Essentials of Programming Languages, Daniel Freidman: I'll be working through this one concurrently with the other papers as I want to work the examples, and that will slow down the reading. I would be interested in advice; this is a textbook widely used in CS courses, would it be inappropriate for me to post my solutions?
Types and Programming Languages, Benjamin Pierce: I will be starting this as soon as I finish EOPL. Again I expect to work the examples, and a similar question arises, except that this is a graduate text so hopefully less chance of encouraging cheating

And concurrently with this:

Introduction to Graph Theory, Richard J. Trudeau
Making reliable distributed systems in the presesnce of software errors, Joe Armstrong
The Polyadic PI Calculus : A Tutorial, Robin Milner: I'll be rereading this one in order to summarise it properly. I'm finding it too useful as a framework for thinking about OOP to not want a more concrete reference to my own understanding of this topic.
Genuinely Functional User Interfaces, Antony Courtney, Conal Elliott: This is my primary area of interest, so I am particularly interested in any interesting references on FRP, Arrows, and FRP/Arrows applied to GUI's
Arrows, Robots, and Functional Reactive Programming, Paul Hudak, Henrik Nilsson, Antony Courtney, John Peterson

There are more, but that will do for now. I'll keep this list updated as I find other 'shiny papers', receive recommendations, or actually finish reading some of them ;).

It's not as scary as it sounds.

2004-07-29T22:52:00.000+10:00

Greg Black comments that he took a look at Joe Armstrong's thesis I linked to below. Just in case his discription makes it sound intimidating, the error handling philosophy discussion --- let it crash --- is one section of chapter 4 (ie. about 3 pages). Of course, handling errors is only one step towards a reliable system.

In fact, the chapters of the thesis are largely approachable independently of each other. Chapters 2 and 4 (Architecture and Programming Principles) are particularly good in this regard.

In the meantime for those who are feeling too lazy to read the actual pdf, an executive summary:

We don't know how to write bug-free programs
So every substantial program will have bugs
Even if we are lucky enough to miss our bugs, unexpected interactions with the outside world (including the hardware we are running on) will cause periodic failures in any long-running process
So make sure any faults that do occur can't interfere with the execution of your program
Faults are nasty, subtle, vicious creatures with thousands of non-deterministic side-effects to compensate for
So the only safe way to handle a bug is to terminate the buggy process
So don't program defensively: Just let it crash, and make sure
1. Your runtime provides adequate logging/tracing/hot-upgrade support to detect/debug/repair the running system
2. You run multiple levels of supervisor/watchdog all the way from supervisor trees to automatic, hot-failover hardware clusters

Simple really ;)

Let it crash

2004-07-28T10:41:00.000+10:00

Martin Pool links to a usenix paper from last year on Crash only software. It is an interesting paper, the first I have seen applying this principle to J2EE. Still I was rather disappointed that the only prior work on supervisorary fault recovery cited seem to be their own. For instance the erlang community has made this a fundamental part of their culture, and the approach is pervasive from the language primitves thru standard libraries to system architecture recommendations and community norms.

Anyone who might be interested in more detail on how this philosophy works in practice is encouraged to check out Joe Armstrong's PhD thesis Making reliable systems in the presence of software errors.

The importance of checking references.

2004-07-22T11:09:00.000+10:00

Jeff Pollock has responded to Paul Gearon's post on Jeff's recent comments to the RDF DAWG list. In doing so he makes three points, I will address his other two points another time (if Paul dosn't beat me to it), but wanted to make a quick note here regarding the first.

Jeff's quote from the dawg charter didn't ring true to me in light of various comments on the dawg list, so I went and checked. Jeff wrote:

the DAWG charter says "It is a requirement that the query language be compatible with an XQuery context"

The charter reads:

There is a requirement for RDF data to be accessable within an XML Query context.

And in fact even this snipet looses signifigant, and important context. A true contextual quote reads:

At this stage, it is not clear to what extent XQuery technology is applicable to the task of querying RDF datasets. The RDF DAWG should aim to maximize W3C technology re-use, while also taking account of differences between the RDF graph data model and the XQuery data model. There is a requirement for RDF data to be accessable within an XML Query context. The working group should specify at least one mechanism for exposing RDF query facilities in an XQuery environment; that is, a way to take a piece of RDF Query abstract syntax and map it into a piece of XML Query using some form of extension to XQuery. ... While the data model of the query language of this protocol is dissimilar to that of XQuery, a non-XML concrete syntax might reuse syntactic elements from XQuery to aid learning time, even if XQuery is not chosen as the strawman.

Note that the sentence Jeff quoted is referring to an extension to XQuery to allow an RDF query to be embedded in, and accessed by, an XQuery. This is very different from a requirement for compatibility, and falls far short of requiring the use of an XQuery syntax for the rdf query language.

It is also worth noting here that the charter explictly recognises the difficulty in mapping XML-infoset semantics to rdf.

At this stage, it is not clear to what extent XQuery technology is applicable to the task of querying RDF datasets. ... While the data model of the query language of this protocol is dissimilar to that of XQuery, ... While RDF query addresses a different data domain (the RDF graph),

On the other hand, the charter also naturally recognises the value in cohesive standards that leverage off each other:

The RDF DAWG should aim to maximize W3C technology re-use, while also taking account of differences between the RDF graph data model and the XQuery data model. ... a non-XML concrete syntax might reuse syntactic elements from XQuery to aid learning time ... any query mechanisms defined by this group must leverage off, and, where possible, interoperate with, the related XML recommendations

In conclusion I will repeat what I said in my first post on this subject.

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.

Update Andy Seabourne has posted a link to a paper by the jena team which nicely illustrates how BRDF can be made accessable to XQuery/XSLT.

Watch this space.

2004-07-20T18:26:00.000+10:00

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

2004-07-17T19:03:00.000+10:00

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

2004-07-17T08:22:00.000+10:00

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

2004-07-16T23:37:00.000+10:00

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.

2004-07-16T13:51:00.000+10:00

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?

2004-07-14T10:45:00.000+10:00

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

2004-07-13T10:25:00.000+10:00

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.

2004-07-12T16:12:00.000+10:00

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.

2004-07-12T14:20:00.000+10:00

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.

2004-07-12T10:44:00.000+10:00

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.

2004-07-09T13:14:00.000+10:00

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.

2004-07-07T12:43:00.000+10:00

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

2004-06-30T22:45:00.000+10:00

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:

Introduction
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.)
Names, Scopes, and Bindings. (Value lifetime; garbage collection; different scoping rules; different implementation approaches to scoping.)
Semantic Analysis. (Attribute grammars; attribute flow. While well written, I personally found this one of the weaker chapters.)
Assembly-Level Computer Architecture. (Effectively a one chapter synopsis of Hennersey and Patterson.)
Control Flow. (Selection; Iteration; Recursion; and Non-determinisim)
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.)
Subroutines and Control Abstraction. (Calling sequences and conventions; call-stack/tree management; exceptions - including continuations; coroutines.)
Building a running program. (Compiler backends; intermediate code; register allocation; linking - including dynamic linking and pic.)
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).
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).
Concurrency. (Background; Theory; Shared-memory; and Message-Passing. A very impressive introduction to concurrency.)
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

2004-06-29T11:20:00.000+10:00

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.

2004-06-28T22:09:00.000+10:00

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?"

2004-06-28T08:24:00.000+10:00

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

2004-06-25T08:50:00.000+10:00

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.