An Advanced Diagram Markup Language

LPCA seminar, April 13, 1996.

Based on invited talk for ECCT, Tours, July 25, 1994
see also the paper and Xy-pic home page

Abstract: Discusses textual notation for categorical diagrams as developed for the diagram typesetting package Xy-pic. The emphasis is on designing notations that are suitable for people, not only to write but also to read other's diagrams. (In particular, this is not a talk on the typesetting system TeX on top of which Xy-pic is run.)

» Overview of this presentation:

On markup, in particular for live documents.
Survey of notations (w/Xy-pic examples):
- Positional (example: `kernel' notation).
- Visual (example: `matrix' notation).
- Conceptual (example: `graph' notation).
On orthogonal design, in particular embedding and consistency of features.
Examples.
Conclusions.

. . . with Ross Moore; supported by ARC, MURG.
Presentation partially supported by Torkil Holms Fond.

» On Markup . . .

Purpose is to separate text in contents and markup (originally the separation was between typewritten text and hand-added annotations in manuscripts):

Contents:

Text: words and punctuation.
Math: symbols.
Diagrams: ?

Markup:

Text: emphasis, heading levels, footnotes, etc.
Math: sub/superscripts, sizes, parenthesis interpretation.
Diagrams: ?

Divided into logical and physical.

» Markup on live documents

For continuous editing of a document with markup it is particularly important that the markup is as transparent to the `real' contents as possible:

See the dicussion of conceptual diagram notation later.

» Positional notations

Separates location and shape:

Coordinates (cartesian).
Objects (text boxes and graphics).

References:

PIC Kernighan 82.
\point Knuth 84.
LaTeX picture environment Lamport 86 (sample) and derivatives.
PiCTeX Wichura 87.
catmac Reynolds 87.
Xy-pic (version 1) Holm&Dybkjær 90.

» Xy-pic positional `kernel' notation

`Object oriented' language maintaining `graphic state' (similar to PIC Kernighan 82 and catmac Reynolds 87) with

Coordinates in a variety of formats.
`Current' and `previous' object.
Last connections between them (for finding location `along' it).

Kernel example:

» was typeset by

\def\Lab#1{{\scriptstyle #1}}
\def\Arr#1#2{\POS**\dir{-}
 ?>*\dir{>} ?+/#1 1ex/*{\Lab{#2}}\POS}
\xy<0.3pc,0pc>:
  (0,20)*+{U}="u" ,
 (15,10)*+{X \times_Z Y}="xy" ,
 (30,10)*+{X}="x" ,
 (15,0) *+{Y}="y" ,
 (30,0) *+{Z}="z" ,
 "u";"xy" **{}?*{\Lab{(x,y)}}="u-xy" ,
  "u";"u-xy" **\dir{-}, "u-xy";"xy" **\dir{-} ?>*\dir{>},
 "u";"x" \save **{}?+/^1pc/="c" \restore \curve{"c"}\POS
  ?>*\dir{>} ?+/^1ex/*{\Lab{x}} ,
 "u";"y" \save **{}?+/_1pc/="c" \restore \curve{"c"}\POS
  ?>*\dir{>} ?+/_1ex/*{\Lab{y}} ,
 "xy";"x" \Arr_p ,
 "xy";"y" \Arr^q ,
 "x";"z"  \Arr_f ,
 "y";"z"  \Arr^g \endxy

» Analysis:

Contents: Ordinary (TeX) math objects in *{_}.

Logical markup: Naming of entries with ="_", special objects *_{_}.

Physical markup: The rest: (_,_) for cartesian coordinates, <_,_> for absolute vectors, /_/ for directional vectors, : to set the coordinate system, ; to swap current/previous object, ** for connections, ? to locate point on last connection, . . .

Note: lower level than LaTeX picture mode.

» Visual notations

Use visual pattern in desired diagram to structure input:

Implicit alignment grid of entries (matrix).
Objects (text and graphics).

References:

\CD...\endCD Spivak 82.
Exercise 18.46 Knuth 84.
Diagram Borceux 88 (sample).
diagrams Taylor 90 (sample).
Xy-pic (version 2) Rose 91 . . .

» Xy-pic visual `matrix' notation

Distinguish between

Ordinary objects in entries.
Arrows from one entry to another (or several), with labels Rose 92.

Different from Borceux 88, Taylor 90 by exploiting that the `orientation' of arrows is virtually the same as the `hop' from its source to its target.

» Matrix example:

was typeset by

\xy\xymatrix{
 U \arrow @/^.5pc/ [drr] ^x 
   \arrow @{-->} [dr] |-{(x,y)}
   \arrow @/_.5pc/ [ddr] _y                             \\
   & X\times_Z Y \arrow[d]^q \arrow[r]_p & X \arrow[d]_f\\
   & Y \arrow[r]^g                       & Z            }
\endxy

» Analysis:

Contents: Ordinary (TeX) math entries.

Logical markup: & and \\ delimiting entries; @{-->} for dashed arrows, ^/_/| for labels in super/sub/break position.

Physical markup: @/^ and @/_ for arrow `curvature'; - for centering label on arrow rather than entries.

» Conceptual Notations

Use inherent (= intuitive) structure as notation skeleton:

Mimic drawing process.
Notation customisation.

References:

(PIC Kernighan 82.)
diagram Barr 88 (sample).
Xy-pic (version 3) `graph' feature Rose 94 . . .

» Xy-pic conceptual `graph' notation

Motto: Don't ask the experts - ask the teachers!

Ideas as present in pullback development (w/source).

» Graph example:

» was typeset by

\xy\xygraph{!{0;<5em,0pc>:<0pc,4em>::0}
 []   Z                   ( [u]X :_f ? , [l]Y :^g ? )
 [ul] {X \times_Z Y}="xy" ( ? :_p "X" , ? :^q "Y" )
 [ul] U  ( ? :@/^.5pc/ ^x "X" , ? :@/_.5pc/ _y "Y" ,
           ? :@{-->}   |-{(x,y)} "xy" )               }
\endxy

Analysis:

Contents: Letters and {_}s are nodes with ordinary (TeX) math.

Logical markup:

[_] for relative moves.
"_" for move to previously typeset _.
(_,...,_) means map current node over the sequence of `subgraph abstractions' (wherein ? refers to it).
@{-->} for dashed arrows, ^/_/| for labels in super/sub/break position (as matrices).

Physical markup: @/^ and @/_ for arrow `curvature'; grid dimensions.

» Conceptual vs. Visual notation

Which one?

Visual more immediate - use for `one-shot' diagrams.
Conceptual easier to maintain - use for diagram development.
Also allows different interpretations of diagram: Check out the animation of the above diagram (w/source) !!

» On orthogonal design

Motto: Choose freely, then combine!

Example: independence of direction.

Considerations when adding a new feature:

Should combine with existing features.
Should use notation consistent with existing features.
Should not solve problems already solved.

» Embeddings in Xy-pic

Positional (kernel) in Visual (matrix): here.
Positional (kernel) in Conceptual (graph) here.
Visual (matrix) in Conceptual (graph):

» was typeset by

\xy\xygraph{
 !M{ X \times_Z Y \="xy" \:[r]_p \:[d]^q
                     & X \="X" \:[d]_f \\
     Y \="Y" \:[r]^g & Z }
 [ul]U   ( ? :@/^1ex/ ^x        "X" ,
           ? :@{-->}   |-{(x,y)} "xy" ,
           ? :@/_1ex/ _y        "Y" )
}\endxy

using !M{_} to first build the matrix as a unit and then `ordinary' graph construction to add the pullback. Note: the combination is more than the sum of the components, for example the base used for [_] by graphs is set by the last matrix. . .

» Consistency

Xy-pic uses some generic symbol conventions:

^ means `superscript label' (as TeX).
_ means `subscript label' (as TeX).
| means `break label'.
@ means `variation'.
+ means `add' or `increase'.

and many others. Consistency is best achieved by defining things on the lowest possible level:

Present Xy-pic kernel is mostly a synthesis of such things.
The `arrow' feature is an extraction of `segmented arrows' Rose 92 used by several other features.

» Examples

Double Lie Algebroid.
TeX flow.
Double cube.
Pasting diagram.
Idea/think/do from above.
Ross Moore's paper on typesetting Neural Nets.
Ross Street's book on Quantum Groups: section 10(src) and 11(src).

« Conclusion

Xy-pic is mature to serve as a tool for textual notations for diagrams (with TeX).

What needs to be done:

Document the advanced features for users.

Graphic interface.

Investigate further use of animation (like this).

Xy-pic is available (as `free software') for anonymous ftp along with my other TeX-related stuff on ftp.diku.dk in /diku/users/kris/TeX, or through my W3 link below.

Kristoffer Høgsbro Rose / kris@diku.dk / Oct 25, 1995.