# [om] A Proposal for extending OpenMath with structure sharing

Richard Fateman fateman at cs.berkeley.edu
Tue Apr 2 18:45:16 CEST 2002

```It seems to me to be a mistake for a phrasebook to
"explode" an object if there is any way of representing
the shared structure in the eventual host system.

The host system could explode the object if it chose to
do so.  The reverse transformation may be impossible.

As far as Steve's interpretation, I disagree.
There are not two kinds of intervals.  The interval
notation [-1,1] is the set {x |  -1<=x<=1}.
And anything said of this interval should be true
"for every x where -1<=x<=1"

The other notation that Steve is thinking of is
"There exists an x in [-1,1] .... "

In programming terms, descending to pseudo Lisp, you
could perhaps do this by analogy with lambda do this:

( (choose-element-from-set(x) "say something here about x")
(theinterval -1 1))

In the world of mathematics, the notion of equality is different
from the data representation notion(s) of equality. That is,
mathematically 2+2=4.
In OM this is presumably false.

In common lisp there are a host of equality relations, including
eq  meaning  "occupies same memory location"
=   meaning   "is a number and has same value, e.g. 0.0 and 0"
as well as
eql
equal
etc.

For what it is worth, (I don't know if there are people here who
don't know lisp...)
with *circle-print* set to true, lisp
works this way
(setf r '(a b c))              ;;; set r to the list (a b c)
(a b c)                        ;;; this is the displayed result
(cons r r)                    ;;; make a pair whose head and tail are r
(#1=(a b c) . #1#)             ;;; this is the displayed result
;;; which can be read back in to create same
;;; sharing.

Michael Kohlhase wrote:

> I think that Steve's Response to James objection makes the issue very
> clear. The term "syntactic sharing" coincides with my view on sharing, and
> I really think it is unproblematic, as it is only a matter of the XML
> encoding. If this change were adopted, we should maybe add James' example
> as an explanatory note.
>
> However, this does raise the question of what a phrasebook (e.g. for maple)
> should do upon receiving a syntactically shared OM object. Should it
> explode the object, just to be sure to adhere to the semantics?
>
>      Michael
>
>
>
>
>>Delivered-To: kohlhase+ at cs.cmu.edu
>>Sender:  owner-om at openmath.org
>>Precedence: bulk
>>
>>
>>>I assume that JHD mean the interval from -1 to 1  by [-1,1].
>>>Then JHD asserts that if x= [-1,1],  then  x-x is zero, while
>>>[-1,1]- [-1,1]  is [-2,2].
>>>I think that x-x pretty much has to be [-2,2],  which of course includes
>>>one
>>>value of  0.
>>>Consider the extension of JHD's rule yielding 0:  p(x) where p is a
>>>program
>>>would not be the result of evaluating each operation as an interval
>>>operation,
>>>but the value [a,b] where a= min(p(x),x in [-1,1]), b = max ....
>>>Now this would be very neat, but might not be computable.
>>>
>>>
>>I think this tells us that there are two notions of interval needed here. One
>>trully represents the whole set, and the x= [-1,1], x-x  should be [-2,2]. The
>>other represents an unknown value in the set, and then x = [-1,1], x-x should
>>be 0.
>>
>>Regarding sharing, I can see no possible problem with a  "syntactic" sharing,
>>wherte the OM tree is the unshared one, but repeated, syntactically identical
>>subtrees are merged for economy of space or bandwidth.  On the other hand,
>>gzip will more-or-less do this for you anyway.
>>
>>A "sematic" sharing, creating an OM DAG is a little bit tricky, because
>>existing CDs have not been written with it in mind, so, for instance, we are
>>not clear which kind of intervals we have. Since we don't have a notion of
>>evaluation at OM level at all, the problem passes down to individual symbols,
>>and we would have to go through our whole collection of such checking for any
>>issues. That would not be a huge job. but it would be a job.
>>
>>	Steve
>>
>>
>>--
>>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
>>
> --
> 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
>

--
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

```