Integrals etc.

My experiments with prolog have been progressing.

    See     http://www.w3.org/pub/WWW/MarkUp/Math/Group/math.pl

Prolog allows you to define operators and provides the operator
precedence parser that parses input strings into prolog terms.
Its not precisely what we need but close enough to experiment with.

First there are some operator definitions, covering + - / etc.
which are built into prolog. I have extended this set:

        ?-op(980, xfy, becomes).
        ?-op(800, xfy, over).
        ?-op(650, yfx, of).
        ?-op(650, yfx, wrt).
        ?-op(650, yfx, from).
        ?-op(650, yfx, to).
        ?-op(550, fy, sqrt).
        ?-op(200, xfy, up).
        ?-op(200, xfy, down).

Here, the number defines the precedence as an integer in the range
0 to 1200. The next argument determines whether the operator is
prefix, infix or postfix and how it associates. The third argument
gives the name of the operator.

I have defined a number of assertions that say how to map terms into
an internal representation:

    map(var(a) * var(b) becomes times(var(a), var(b))).
    map(var(a) + var(b) becomes plus(var(a), var(b))).
    map((var(a)/var(b)) becomes div(var(a), var(b))).
    map((var(a) over var(b)) becomes over(var(a), var(b))).
    map((sqrt var(v)) becomes sqrt(var(v))).
    map((var(a)^var(b)) becomes up(var(a), var(b))).
    map((var(a) up var(b)) becomes up(var(a), var(b))).
    map((var(a) down var(b)) becomes down(var(a), var(b))).

    map(integral of var(a) wrt var(b) becomes integral(var(a), var(b))).
    map(integral of var(a) becomes integral(var(a))).
    map(integral from var(a) to var(b) of var(c) wrt var(d)
         becomes integral(var(a), var(b), var(c), var(d))).

Non-terminals are represented using var(slot-name). These assertions
are compiled into rules that can be executed to reduce input terms.

This allows you to make queries like:

  a)    ?- reduce(1/2, X).

        X = div(1, 2).

  b)    ?- reduce((integral from 0 to pi/2 of sin(x) wrt x), X).

        X = integral(0, div(pi, 2), sin(x), x)

The reduce predicate maps the input term into the internal
representation. The mapping rules provide a knowledgebase
with which to interpret the input strings allowing us to
end up with a representation in which the semantics are
more clearly defined than when we started.

The mapping rule:

    map(var(a) * var(b) becomes times(var(a), var(b))).

is compiled into:

    (X*Y) becomes times(X1, Y1) :- reduce(X, X1), reduce(Y, Y1).

This is used by the reduce predicate to solve the query.

    reduce(X, Y) :-
        X becomes Y, !.
    reduce(X, X).

Notice that the prolog cut operator is used to prune search to
the first solution. In otherwords search is depth-first and
deterministic. This means we could use Java or C++ for applying
the rules.

The internal representation used above is based on the following:

    plus(X, Y)      e.g.    X + Y
    minus(X, Y)     e.g.    X - Y
    times(X, Y)     e.g.    X * Y
    div(X, Y)       e.g.    X / Y
    over(X, Y)      e.g.    X / Y
    sqrt(X)         e.g.    sqrt X
    up(Base, Script)        e.g.    X up 2
    down(Base, Script)      e.g.    X down 1

    integral(Integrand, X)  e.g.    integral of sin(x) wrt x
    integral(Lower, Upper, Integrand, WRT)
            e.g. integral from 0 to pi/2 of sin(x) wrt x        
    
Note that I haven't yet explored the practicalities of multiple
integrals, but full nesting will certainly work, e.g.

 integral from l to u of (integral from l1 to u1 of f(x, y) wrt x) wrt y

This becomes:

 integral(l, u, integral(l1, u1, f(x, y), x), y).

Which is isomorphic to Patrick's example:

    Int[l, u, Int[l1, u1, f(x, y), dx], dy]

Except that my representation uses x and y instead of dx and dy.
It would be nice to weaken the need for explicit nesting but this
can't be done while I continue to rely on prolog's in-built
term parser.

My goal is to be very flexible as to the syntax for such things.
The important part is the internal representation not the surface
syntax, as the internal representation is the basis for rendering
and exchange with math manipulation packages.

The next step is to define the lexical syntax and to create
a full blown operator precedence parser which will allow us
to implement the full notation, without the restrictions
imposed by the syntax for prolog terms, e.g. prolog won't let
you use `_' as an operator.

Once this has been done, then I will be in a position to experiment
with inferring times(x, y) from "x y", and to support `_' for subscripts
and `{' and `}' for invisible brackets etc. I also look forward to
experimenting with how identifier declarations can be exploited to
control inference of semantics, e.g. for raising and lowering operators.

Note that the internal representation has some redundancies
(e.g. div and over) that are needed to preserve the visual distinctions
for rendering purposes.

-- Dave Raggett <dsr@w3.org> tel: +1 (617) 258 5741 fax: +1 (617) 258 5999
   World Wide Web Consortium, 545 Technology Square, Cambridge, MA 02139
   url = http://www.w3.org/People/Raggett