A. Strotmann: Proposal presented at 5th OpenMath Workshop, Bath.

# OpenMath Layer: Expression

• Basic "Categories"
• Constructor "Categories"
• Rules of Composition
• Representation Rules and Interpretation Rules
• Relation to Contexts
• Some Reasons
• Some Issues
Note: I'm still trying to find a good name for the components that make up the expression layer. The problem is that all the "good" names I can think of carry specific meaning in some area of mathematics and computer science or other. Possiblities include "fundamental concepts", "class", "fundamental mathematical structures".

For want of a better alternative so far, I reluctantly call them "category" here.

## An SGML example

```     <apply>
<function  context=user> f </function>
<to>
<constant  context=RealTrig> π </constant>
<to>
<constant  context=arith> 234 </constant>
</apply>
```

## Basic "Categories"

• Representation (uninterpreted data)
• Domain (or Type)
• Constant (or domain element)
• Function
• Relation (or predicate)
• Truth Value
• Conjunctions (and, or, not, ...)
• Quantifier
• Variable
• Operator
• Sectioning Command
• Operation (command)
• ... others ... ?

## Constructor "Categories"

• Application
Scope, binding, structure sharing

## Expression and Data Structure

An example ("X+1000"):

```expression =        application
/   |   \
/    |    \
fn   var   dom.el.
+     x     1000

data-structure=       -------   (i.e. non-homogeneous sequence)
/   |   \
/    |      \
/     |         \
symb      symb       -----------
/  |        /\        /  |   \   \
/   |       /  \      /   |    \    \
ctx  entry  ctx entry symb int32 bool vector-of-int32
/ |             [.|.|.|.|...]
/  |
ctx entry

[where "ctx" is short for "context"; a 'bigint' is used for
illustration purposes]
```
i.e. the data structure level provides more detail.

Interpretation Rules govern the mapping from data-structure to expression level.

Representation Rules govern the mapping from expression to data structure.

Example representation rules:

```     apply(f, x1, x2, ... xn)  -->  (f x1 x2 ... xn)
symbol                    -->  triple(name, context, category)
```
where (a b ... c) is a shorthand notation for a non-homogeneous sequence with elements a,b,...,c .

Example interpretation rules are the inverse mappings of above rules.

NOTE: Streamlined implementations may not need to generate separate data structures for these levels. The separate layers may either be realized in a single complex data structure with separate fields for the components of each layer, or the data structures and expressions may in fact be "real" only by virtue of a calling graph of the encoding API functions.

## Rules of Composition

Examples:

APPLICATION of FUNCTION to DOMAIN ELEMENT yields DOMAIN ELEMENT

APPLICATION of FUNCTION to DOMAIN yields DOMAIN

APPLICATION of DOMAIN to DOMAIN ELEMENT yields DOMAIN ELEMENT

APPLICATION of PREDICATE to DOMAIN ELEMENTS yields TRUTH VALUE

## Some Reasons

• help user understand the mathematical structure of a document without having to understand all the details
• Useful for SGML markup (see example earlier)
• default handling of 'user' or 'unknown' symbols of a "category" (e.g. printing function symbols different from variable symbols).
• facilitate cooperation between computational logic and computer algebra systems: Roughly, each side leaves the other's components of an object untouched when processing, and each side may possibly disregard certain information not in its realm when it doesn't understand it in full detail. Similarly, a graphics system might just disregard anything but the image data embedded.
• provide a common framework for those who need to define model-theoretic semantics for their Contexts (e.g. ANSI working group in the area of knowledge interchange)
• try to capture a usefully small and intuitive set of "categories" that are pervasive in mathematical papers or software. As a guideline, it should be hard to imagine any field of mathematics that does not require instances of such a "category" in marking up a paper from that field.

## Some Issues

Is it really necessary...
• ... to have more than a minimalistic expression layer (which would just say that sequence (a b ...) represents application of a to b,...)
• ... to have, in particular, ...
• ... logic "categories"? E.g.: one could get away with just boolean functions instead of predicates and conjunctions
• "category" APPLICATION instead of specific "categories" such as, e.g., FUNCTION APPLICATION, QUANTIFICATION, PREDICATION...
• ... structured symbols (we could keep that additional information in the corresponding Context instead)
• CONSTANTS (as opposed to zero-argument functions)
• ... to consider "Is it really necessary" questions?
Other issues include:
• handling scoping and binding of variables and structure sharing
• are Domain and Type the same (or close enough)?
• doing it right...
Some guidelines that might help decide:
• try for an "intuitive" user interface for marking up mathematical documents
• provide support for important clients of OpenMath (databases/searching, typesetting, formula display, computational logic, numerics, graphics ...)
• not too much, not too little...

This page is part of the OpenMath Web archive, and is no longer kept up to date.