[stack] a concatenative language for the Semantic Web

Hi all,

I'd like to introduce a new RDF query language, called Ripple, which
applies the basic ideas of concatenative languages to the Semantic
Web.  The Semantic Web is a network of machine-understandable data
which is to a software agent what the hypertext Web is to a person.
It replaces the unconstrained, natural language text of HTML web pages
with the software-friendly subject-predicate-object triples of RDF,
enabling specialized applications to make more intelligent use of the
vast amounts of information on the Web (or at least, that's the
vision).  Personally, I'm very interested in the procedural aspect of
the Semantic Web, or the logic and algorithms which drive the
crawlers, reasoners, and innovative mashups that consume and do useful
things with the data.  I also like functional programming, so
expressing Semantic Web programs as Semantic Web data seemed to me
like a natural thing to do: Ripple programs are both expressed in RDF
and operate upon RDF metadata.  I decided to make Ripple a
concatenative language because of the simplicity of concatenative
programs and because of their resemblance to path expressions, which
are very appropriate for the labeled graph model of RDF.  There's some
documentation on Ripple here:

    http://ripple.projects.semwebcentral.org/

The Java implementation is available here:

    http://projects.semwebcentral.org/frs/?group_id=125

Ripple's syntax and query model borrow heavily from Joy, with a few
key differences:

1) There is only one "operator" (a dispatch function called op) in the
language; everything else is treated as a constant.  For instance,
whereas in Joy you would write

    2 dup

In Ripple, you might write

    2 dup op

In Ripple, dup is a "passive" stack item just like the literal value
2.  We need an operator, op, to consume dup and push a dup "filter" to
the stack, which then consumes the 2.  Ripple draws in programs and
data from the Semantic Web on the fly, so the op symbol potentially
saves on a lot of comparison operations by telling the evaluator
exactly when it needs to examine a resource and treat it as a program.

Since op is so common, Ripple's notation allows for its abbreviation
as a prefix (the slash character).  Thus, the above could (and usually
would) be written:

    2 /dup


2) Quotations (indicated with parentheses rather than square
brackets), primitive functions, and RDF properties are
interchangeable.  In Ripple, combinators such as i and dip have a
slightly different mode of operation than they do in Joy, in that they
push op to the stack instead of applying functions directly.  So, for
instance,

    3 (1 2) /dip  -- or:  3 (1 2) dip op

is equivalent to

    /(1 2) 3  -- or:  (1 2) op 3

And this is where evaluation stops.  If anything beneath the topmost
item on the stack is needed for the subsequent application of a
function, then the stack will be further reduced to

    1 2 3

I called op a dispatch function because, having consumed an argument,
it applies a function to the remainder of the stack which depends on
the type of that argument.  If op is applied to a primitive function,
it in turn applies the function to the rest of the stack.  A
construction like the following is legal in Ripple (think of dup as
[dup] in Joy):

    2 dup/i   -- or:  2 dup i op

which becomes

    2/dup   -- or:  2 dup op

which becomes

    2 2

When applied to an RDF property, op yields an atomic RDF path
operation.  For example:

    :arthur/foaf:name   -- or:  :arthur foaf:name op

becomes

    "Arthur Dent"

This is a program which takes us from the resource identified by
:arthur to a value associated with :arthur by a foaf:name edge in the
global RDF graph we're querying.  The foaf:name operation behaves like
a partial function over all of the resources in the graph.

3) There is no single global stack in Ripple.  Instead, Ripple is
geared towards "streams" of stacks in order to deal with RDF's
multivalued relations.   Filters may consume more than one stack, and
produce any number of stacks.  E.g.

    (1 2 3)/each   -- or:  (1 2 3) each op

This program yields not one, but three values, each in its own stack:

    1
    2
    3

The three stacks continue down the evaluation "pipeline" individually,
and further operations are applied to each of them in turn.

    (1 2 3)/each 100/add   -- or:  (1 2 3) each op 100 add op

becomes

    101
    102
    103


Here's the definition of a simple program in Ripple:

@define fib:
    0 1 /rolldown     # push initial value pair and put n on top
    (/swap/dupd/add)  # push the step function
    /swap/times       # execute the step function n times
    /pop.             # select the low value

Here's another which uses "stream" primitives and RDF properties:

@define foafStep:   # iterator for a FOAF crawler
    (   id          # include foaf1 itself
        owl:sameAs  # include nodes identified with foaf1
        foaf:knows  # include those foaf:known by foaf1
    )/each/i        # apply all three patterns at once
    /unique.        # eliminate duplicate results


That's all for now :-)  I hope this was interesting.  Comments and
criticism are very welcome.

Josh