09 April 2007

SPARQL S-expressions

I'm interested in exposing the SPARQL algebra support in ARQ for others (and me!) to experiment with SPARQL and SPARQL extensions.

Having a syntax to be able to write algebra expressions is useful and makes writing test cases of the algebra easier. ARQ already uses S-expressions to detail the syntax tree so it was natural to use S-expressions for algebra expressions.

I split the lowest levels of syntax out, to avoid having to write a many parsers. The result - SSE (SPARQL S-Expressions), a vaguely lisp-ish syntax. It consists of lists, RDF terms (IRIs, blank nodes, prefixed names and literals) in SPARQL syntax, and also words which are plain symbols without colon.

Given this universal syntax, it's a matter of building code libraries to build the Java data structures from SSE. This is mundane but being able to do this without rebuilding a parser each time is easier.

Example query:

 PREFIX : <http://example/> 

 SELECT ?x ?v
 { ?x :p ?v 
   OPTIONAL { ?v :q ?w }
 }

which is the algebra expression:

 (project (?x ?v)
   (leftjoin
     (bgp [triple ?x <http://example/p> ?v])
     (bgp [triple ?v <http://example/q> ?w])))

The use of either () or [] for lists, where beginning and end must match, aids readability but has no other significance.

Another example: 'prefix' defines namespaces for the enclosed body:

 (prefix ((: <http://example/>))
   (project (?c)
     (filter (= ?c "world")
       (bgp [triple ?s :p ?c]) )))

It doesn't just capture strict SPARQL: tables-as-constants mean an SSE file can contain data as well

(prefix ((x: <http://example/>))
  (join
    (table
      (row [?x 1] [?y x:g])
      (row [?x 2] ))
    (table 
      (row [?y x:g])
      (row [?x 2] ))
  ))

evaluating to:

 --------------------------
 | y                  | x |
 ==========================
 | <http://example/g> | 1 |
 | <http://example/g> | 2 |
 |                    | 2 |
 --------------------------

It's still "work in progress" and a bit rough - it can be inconsistent in layout, mainly due to slipping in a quick bit of hacking between doing other things; and also this leads to different coding styles in different places. But it's already proved to be an efficient way to write SPARQL algebra expressions and evaluate them for testing.

And doing an Emacs mode for SSE is trivial.

As an aside - I did a little web-trawling for the lisp information and gathered my links together.

Some Lisp Links

A partial, incomplete set of links to things about Lisp from a couple hours of web wandering. It's a bit of a change to be linking to web pages from the last millennium.

Lisp / General

The function/value namespace thing:: Scheme vs Common Lisp: http://www.nhplace.com/kent/Papers/Technical-Issues.html. Some of the arguments look a bit dated by modern standards.

Scheme

http://swiss.csail.mit.edu/projects/scheme/

Wikipedia - Scheme

http://www.r6rs.org/ - The latest Scheme definition. The nice thing, from a purely practical point of view, in this round of agreement is the definition of the library system.

Online books:

CMU Scheme repository: ftp://ftp.cs.cmu.edu/user/ai/lang/scheme/0.html

Community: http://community.schemewiki.org/

Object-oriented programming and Scheme

SLIB (A portable scheme library - "portable" seems to mean "it can be ported"). Included in SISC. http://swissnet.ai.mit.edu/~jaffer/SLIB

Websites:

Scheme / JVM Implementations

Access to access to ARQ for a SPARQL engine is important.

Scheme / Eclipse

One of things that Java does have going for it is a free, sophisticated IDEs.  Eclipse makes refactoring easy enough so as to encourage it as the project grows. For a project like ARQ, it's near essential to keep the naming and structure aligned to current terminology. Writing lisp in Emacs does not count as an IDE these days.

http://schemeway.sourceforge.net/ - not investigated yet.

http://schemeway.sourceforge.net/update-site/

Other Eclipse plug-ins? Other free, refactoring IDEs for Lisp?

Common Lisp / CLOS

Wikipedia - Common Lisp

Wikipedia - CLOS

Book: Common Lisp the Language, 2nd Edition

A Brief Guide to CLOS

http://jatha.sourceforge.net/ Common LISP library in Java (LGPL)

Common Lisp Wiki - http://www.cliki.net/

Lisp and .net

ARQ runs fine on .Net, so a CLR (.net and mono) lisp implementation is also interesting.

I didn't have time for much of a look around but did find Common Larceny: http://www.ccs.neu.edu/home/will/Larceny/CommonLarceny/download.html

Not scheme nor Common Lisp: http://dotlisp.sourceforge.net/dotlisp.htm (BSD) but last release: July 9, 2003. Patches from the authors home page.

Other

Bigloo: can call Java. Compiles scheme to the JVM (?? and CLR), can link in Java classes but I couldn't find a clear statement as to how to use in a mixed environment.

Download link to Bigloo 2.9a for the JVM broken (2007-04-08)

http://www-sop.inria.fr/mimosa/fp/Bigloo/ (GPL/LGPL)