[om] A Proposal for extending OpenMath with structure sharing

[Andrew Solomon]

Thanks a HEAP Andreas. That was very helpful.

Andrew

On Wed, Apr 03, 2002 at 04:18:54PM -0500, Andreas Strotmann wrote:
> 
> 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

-- 
Faculty of IT, UTS                     http://www-staff.it.uts.edu.au/~andrews/
Broadway, NSW 2007, Australia          phone:+61.2.9514 7938
CRICOS Provider 00099F                 room:UTS blg 10/4.433
--
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