Joachim's web pages [Home] [Math] [Cat] [Zoom]

The calculus of opetopes in XML using Tcl and tDOM

Read the man pages for the opetope scrips
See examples of opetopes in high dimension
Download package of scripts and example XML files

Overview

The notion of opetope (invented by J.Baez and J.Dolan [BD]) and the algorithms implemented in the scripts in this package refer to the paper Polynomial functors and opetopes by J.Kock, A.Joyal, M.Batanin, and J.-F.Mascari.

Opetopes can be regarded as certain sequences of trees, and it is easy to encode them in XML. The algorithms are implemented in Tcl using the tDOM extension. Furthermore there is support for translation into the dot language, and automated graphical rendering via a dot interpreter.

File format

XML (Extensible Mark-up Language, cf. http://www.w3.org/XML/) is a lot like HTML, except that you define your own tags to express a grammar. This is done in a Document Type Definition (DTD). The opetope DTD looks like this:

<!ELEMENT opetope (constellation+)>
<!ELEMENT constellation (dot|leaf)>
<!ELEMENT dot (dot|leaf)*>
<!ELEMENT leaf EMPTY>

<!ATTLIST opetope name CDATA #REQUIRED>
<!ATTLIST constellation name CDATA #REQUIRED>
<!ATTLIST dot name CDATA #REQUIRED ref CDATA #IMPLIED>
<!ATTLIST leaf name CDATA #REQUIRED>

The first block declares the tags for opetope, constellation, dot, and leaf, specifying which sort of children they can have. In the second block it is specified that each tag must have a name attribute, and that the dot tag is also allowed an optional ref attribute, used only for stopdots.

Click here to see an example of a big opetope encoded in XML.

Scripts

The algorithms for sphere operations have been implemented in the scripting language Tcl, using the tDOM extension (cf. http://www.tdom.org/) for parsing and manipulating XML. There are among other things procedures for computing sources, targets, and compositions, and writing the results back to new XML files. These scripts can be run from the unix prompt, provided Tcl and the tDOM extension are available on the system. The script computeAllFacets takes as argument the name of an opetope XML file, and computes all its codimension-1 faces, writing the resulting opetopes to separate XML files. The script glueOnto takes three arguments: the bottom opetope (name of XML file), the name of the gluing locus, and the top opetope (as XML file). The result is written to a new XML file.

Prerequisites

Tcl and tDOM

To use these scripts you need Tcl installed together with the tDOM extension. For the graphical rendering you also need a dot interpreter.

Most unix systems, including Mac OSX, come with Tcl installed, but typically without tDOM. Windows computers, on the other hand, typically haven't got Tcl, but it is very easy to install it, and then you get tDOM into the bargain.

More information about Tcl, see http://tcl.tk/ and http://wiki.tcl.tk/.

More information about tDOM, see http://www.tdom.org/.

To download Tcl (for all main platforms) together with tDOM, go to http://www.activestate.com/Products/ActiveTcl/ and follow the instructions.

To check that the installation is OK, go to the command line and type tclsh, this will give you a tcl prompt %, in which you type package require tdom. If everything is OK, you should get the message 0.8 or some similar number, indicating that this is the version of tDOM loaded.

In case you are not allowed to install Tcl in its standard location /usr/bin/tclsh, you can install it anywhere else, but in that case there is a risk that it will not be found first in you PATH variable. Rather than modifying your PATH settings you can just modify one configuration file that only affects the opetope scripts: the file is opetope-scripts/tcl/configuration, and the required modification is just to uncomment the second-to-last line and write the full path to the newly installed Tcl.

dot

If you want to take advantage of the graphical capabilities of the scripts, one more ingredient is needed, namely a dot interpreter. DOT is a language for specifying abstract graphs in terms of node-edge incidences, and also an interpreter that can generate a graphical representation of the graph, for example in JPG or PDF format. See for example the paper Drawing graphs with DOT by E.Gansner, E.Koutsofios, and S.North.

The script opetope2dot produces a DOT file from an opetope XML file (this is independent of the presence of dot). There is also a wrapper script opetope2pdf which outputs pdf directly, but this script requires the dot interpreter. The graphical output can be very helpful to get an overview of a complicated opetope and its faces, but unfortunately the output is not quite as nice as the drawings in [KJBM]; Specifically, there is no support for drawing the spheres.

The best thing is to get Graphviz, a graphical interface to dot (and other graph-drawing languages) which includes a dot interpreter. Graphviz is available for all major platforms from the web page http://www.graphviz.org/

One last bit of tinkering is needed: although Graphviz contains the dot executable, it is typically not placed in your PATH, so the opetope scripts cannot find it. The dot executable is hidden somewhere inside the Graphviz bundle. In the Mac OSX version of Graphviz (from Pixelglow), dot is found at /Applications/graphviz/Graphviz.app/Contents/MacOS/dot, while if you install a unix-style version of Graphviz, dot will end up at some place like /usr/local/graphviz-2.9/bin/dot. In any case, you can copy it to somewhere in your path (or make a link to it), or you can include the relevant path in your PATH variable. However, a more convenient method is provided, which avoids messing with your PATH variable: simply edit the last line of the file opetope-scripts/tcl/configuration, telling where dot lives.

Alpha

It is also possible to run everything from within the text editor Alpha (see http://alphatcl.sourceforge.net/). The advantage is that you can have all the involved xml and tcl files open for editing and inspection and control the scripts from the Alpha Tcl Shell, which is far more powerful than a standard tclsh. Alpha sports special editing modes for XML and dot files, and close interaction with Graphviz and pdf viewers, and a convenient keyboard shortcut is set up: Cmd-T will produce a pdf rendering of the frontmost XML file and open it for viewing.

Usage

Basic usage: from the command line

Assuming you stand in the directory opetope-scripts/xml where the example files are, you can invoke the scripts like this (the string [%] represents the prompt):
   [%] ../tcl/listSources Q.xml
   23 24 25 30 31 32 33 34 35 36 37 26 29 27 28
   [%] ../tcl/computeOneSource Q.xml 29
   Q-29.xml
   [%] ../tcl/opetope2pdf Q-29.xml
This sequence of commands will produce a pdf file of source 13 of the opetope Q.

It may be felt clumsy to have to include the ../tcl/ in every command invocation. It is probably practical to append opetope-scripts/tcl to your PATH. You can achieve this temporarily by running the script opetope-scripts/tcl/setOP: it will start a new shell, in which the tcl directory is appended to the PATH. When you have finished, just exit this shell.

The provided commandline scripts are

   checkOpetopeFile  XMLFILE
   areIsomorphic  XMLFILE0 XMLFILE1
   listSources  XMLFILE
   computeOneSource  XMLFILE SOURCENAME ?-o OUTPUTPATH?
   computeTarget  XMLFILE ?-o OUTPUTPATH?
   computeAllFacets  XMLFILE
   glueOnto  BOTTOMXMLFILE SOURCENAME TOPXMLFILE ?-o OUTPUTPATH?

   opetope2dot  XMLFILE
   opetope2pdf  XMLFILE
See the manual pages for details.

More refined operation: from the tclsh shell (or from within Alpha)

The scripts listed above are only wrappers for much more functionality, which however it would not be convenient to use in shell scripts. To access the full functionality, open a tclsh and source the file opetope-scripts/tcl/opetopes.tcl. Now the convenience is that you can keep the opetopes in memory, assigned to variables, and apply operations step by step. This will generally require some basic knowledge about Tcl and the tDOM extension.

The basic sequence of operations is

   set OP [readOpetope XMLFILE]
This will create a dom tree in memory corresponding to the XML file, and this dom tree can be accessed and manipulated with standard Tcl and tDOM techniques. For example
   set ct [$OP lastChild]
   set leafList [$ct selectNodes descendant::leaf]
will produce a list of leaves of the composition tree of the opetope. Many specific opetope operations are implemented as domNode methods and can be applied to modify the dom trees in place or to produce new dom trees. In particular, the four basic sphere operations (described in [KJBM]) are available. The last step in the sequence of operations may then typically be
   writeOpetope $OP SOMEXMLFILE
if the opetope resulting from the transformations is desired saved to disc.

For the specifications and syntax of the provided procedures, see the source file itself which it carefully documented throughout.


Read the man pages for the opetope scrips

See examples of opetopes in high dimension

Download package of scripts and example XML files


Last updated: 2006-12-22 by Joachim Kock.