[om] A Proposal for extending OpenMath with structure sharing

[Andreas Strotmann]

Andrew Solomon wrote:

> Now that everyone else has understood this, can someone explain it to me?:)
>
> So, if someone would be so kind, I would like to have:
> an example of syntactic sharing, an example of semantic sharing, and
> an explanation of where they differ.

Here's an explanation by John Abbott from a comment in an August '95
draft version of an OpenMath Standard that I found in my files:

"We illustrate the notion of `semantic sharing' by considering the formula
for the solution of a cubic using radicals. This has the form

 cuberoot(gamma + sqrt(delta)) - beta / cuberoot(gamma + sqrt(delta))

This formula always yields a root of the cubic no matter which choice of
square root and cube root is made *provided* the choices are made
consistently (otherwise the value produced is not generally a root). A
"consistent choice" means we must pick the same square root of delta, and
the same cube root of (gamma + sqrt(delta)); hence it is important that
the "two instances" of cuberoot(...) in the root formula above refer to a
single (shared) cube root.  A classical way of expressing this would be

  alpha - beta/alpha  where  alpha = cuberoot(...)"


Note that the last sentence says that "semantic sharing" can typically be
expressed in OpenMath using variables (and lambda binding to hide them).


Now consider a program that returns a list of all cube roots, each of them
in the above form:

 {cuberoot(...) - beta/cuberoot(...),
  cuberoot(...) - beta/cuberoot(...),
  cuberoot(...) - beta/cuberoot(...) }

[I don't know off-hand if the three beta's are the same here, but that
doesn't matter in the discussion right now.]

In this case it is important that within each expression the two
occurences of cuberoot(...) are *semantically* shared (mathematically
identical), but those in two different elements of this set are *not*
(unless you have a double or triple root, of course).

However, a *syntactically* shared version of this expression (assuming the
parameters beta, gamma, and delta are the same in all three members of the
set -- as I said, this may not be true) might still be:

 { #1: ( #2: cuberoot(gamma + sqrt(delta)) - beta / #2 ),
   #1,
   #1  }

(using an obvious label/reference syntax).


The notion that syntactic sharing does not necessarily imply semantic
sharing (see Gaston's comment) corresponds to saying that, in OpenMath, if
semantic sharing is *required* to correctly interpret the formula, it is
necessary to use OpenMath variables to force identity:

 { #1: (lambda a. a-beta/a) (gamma + sqrt(delta)),
   #1,
   #1  }

would be syntactically shared wrt to the three elements of the set of
roots (with no implied semantic sharing), and semantically shared wrt the
two occurences of the cube root within each set element.


I hope this re-iteration of our discussion from seven years ago on the
public openmath-developers' list (is its archive available somewhere,
BTW?) helps.


In the OpenMath Objectives we recommended having a "data-structure" level
(corresponding to what Gaston called REPRESENTATION in his post) in
addition to the semantic level that OpenMath 1.0 defines, and we
recommended that that level be a DAG rather than a tree.  Faithful
encodings of DAGs require some kind of label/reference mechanism.

Since OpenMath 1.0 does not have a data-structure level, the OpenMath
Standard can only describe semantic sharing (via variables).  "Syntactic"
or REPRESENTATION level sub-structure sharing can thus only be done on a
per-encoding basis as Michael now proposes to do with the XML encoding --
and indeed the binary encoding for OpenMath already has some structure
sharing mechanisms installed.


  --  Andreas

--
om at openmath.org  -  general discussion on OpenMath
Post public announcements to om-announce at openmath.org
Automatic list maintenance software at majordomo at openmath.org
Mail om-owner at openmath.org for assistance with any problems