## April 7, 2009

### Graphical Category Theory Demonstrations

#### Posted by Urs Schreiber

guest post by Jocelyn Paine

If you could commission a computer demonstration of any categorical idea, what would you ask for? Could such demonstrations have helped you, or your students, learn tricky ideas? And, would you be willing to share the visualisations and metaphors that you have devised to explain these ideas to yourself or others?

Ways of explaining categorical ideas have been discussed here and there in the Café — for example, in Gerbes in the Guardian. But it would be good to devote a single thread to “how to explain” and how we can use the computer to help us do so.

Last year in fact, I implemented some Web-based category theory demonstrations of products, coproducts, and other constructions; and Urs suggested that it would be really nice to combine my work with nLab by making applet demonstrations for the nLab:product and nLab:coproduct pages. So I’ve asked Urs to guest-post this and start the thread.

I’ll just mention that one hope I have is that one could eventually build up a “metaphor repository”: a computerised stock of mappings from categorical ideas to their depictions on screen, including how these relate to animation space and time. From this, one would, with help from the computer, select ideas to be demonstrated and ways to demonstrate them, then piece these together into a complete demonstration. It would be a huge project — perhaps only an order of magnitude smaller than Douglas Lenat’s logic-based encyclopaedia of common-sense knowledge Cyc — but I’m convinced it’s doable, and that someone ought to be doing it. Perhaps it could be a first step to Greg Egan’s Truth Mines! This is his virtual landscape for learning maths, that John Baez mentions near the top of This Week’s Finds in Mathematical Physics (Week 115).

When I have time, I’ll post some ideas on how I think one might implement a “metaphor repository”. But anyway, do please post suggestions for applets that you’d like to see in nLab.

And here are some questions to start off with. At the moment, my Web-page demonstrations use finite sets. The limits demo, for example, randomly chooses sets and arrows between them, generates a limit, then depicts the limit cone using a graph-drawing program called GraphViz. It lists the sets and arrows, so the reader can check that things commute as they should. Sets and set functions are easy to calculate with. But what other categories could I use, whose objects and arrows would also be easy to depict, and easy for a reader to calculate with? Is this anyway too “low-level” a way to show what limits do, paying too much attention to calculation and not enough to the essence of the idea? Probably. And, how much could one really convey in an nLab limit applet, given the size and resolution of current laptop screens and the need to reserve some space for controls and the nLab page text around the applet?

Posted at April 7, 2009 7:37 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1946

### Re: Graphical Category Theory Demonstrations

I applaud your Java applets, Jocelyn! This is the sort of thing where it’s very easy for mathematicians to dream big — but only a few brave people dare to actually do something.

But what other categories could I use, whose objects and arrows would also be easy to depict, and easy for a reader to calculate with?

A possibility that leaps to mind is finite-dimensional vector spaces, perhaps over the rational numbers. By picking bases for all these vector spaces, morphisms between them can be described as matrices of rational numbers.

An amusing about this example is that the coproduct is the same as the product, unlike in the category of finite sets. They’re both the ‘direct sum’ of vector spaces.

Taking an equalizer of two linear maps

$V \stackrel{\to}{\to} W$

amounts to solving a system of linear equations. If there are $n$ linearly independent solutions, you can say the equalizer is $\mathbb{Q}^n$, and specify the actual solutions by giving a matrix to describe the inclusion

$\mathbb{Q}^n \to V$

There could be software packages for solving systems of linear equations that would reduce the amount of programming you need to do.

If you want a more ‘finitistic’ example along the same lines, you could use finite-dimensional vector spaces over a finite field — for example the integers mod 2, which should please your programmer’s heart!

Is this anyway too “low-level” a way to show what limits do, paying too much attention to calculation and not enough to the essence of the idea?

Maybe they’re “low-level” — but maybe that’s great! A lot of people think category theory is “too abstract”. Seeing limits worked out in a very low-level concrete way should correct any misimpression that they’re some sort of airy nonsense.

Posted by: John Baez on April 7, 2009 8:13 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

John, that’s really useful. Yours and the other comments are just the kind of discussion I hoped to provoke. The categories you suggest — finite-dimensional vector spaces over the rationals or a finite field — sound feasible, and as I explain below, it shouldn’t be a problem to tie in software for solving systems of linear equations.

As Aaron Denney says below, my current demonstrations aren’t applets. It might be useful if I explain the difference, and also the various programming methods available for writing such demonstrations. Each has its pros and cons.

Firstly, how do my demonstrations work? When you press a button on my input form, your Web browser sends the name of the button to my Web server. It also sends whichever inputs I ask you to type, such as the two sets wanted by the product and coproduct demonstrations.

When my Web server gets this data, it runs a little program — a “script” — that I wrote in a language called PHP. The script finds the Prolog program I wrote to do my calculations, and runs it. More precisely, it runs one of the predicates in it, such as the one that makes and explains a product cone.

That predicate does the following. It makes a data structure holding the product cone. It adds other categorical stuff lying around the environs, such as a second product and the isomorphism between it and the first. It converts the product cone to input for GraphViz, then runs GraphViz to generate a categorical diagram image file. And finally, it spits out a load of HTML into a text file. That HTML is my results page, containing: my explanatory text; listings of the objects and arrows; and a link to the diagram. The Prolog program then halts, and the script tells my Web server to send, to your browser, a version of my demonstration page similar to the one whose button you pressed, but with a link near the top pointing to the results page.

Having Web pages be generated by programs in this “one-shot” fashion is what Aaron Denney refers to when he talks about “going through a CGI call”: “CGI” stands for Common Gateway Interface, and is a standard protocol for interfacing programs such as my PHP script to a Web server. Its advantage is that everything happens on one Web server, which is completely under my control. So I could indeed call a program for solving linear-equation systems, or anything else, without needing to implement anything new on the user’s computer.

(In fact, I have done something vaguely similar. Colleagues and I once built a Web-based simulation of the UK economy, and for several years thereafter, put a copy on the BBC’s servers each Budget Day, as a game called “Be Your Own Chancellor”. This ran: a microeconomic model; a macroeconomic model; a graph plotter; code for turning Web pages into printable output; scripts for passing data between these; and a package for solving the Treasury equations that defined the macroeconomic model. Probably very few of the thousands of people who ran our simulation knew how many different programs were co-operating inside it.)

The disadvantage of doing things this way is that interaction is coarse-grained. Fill in a form; submit it; get back a page of output. You can’t draw diagrams in your browser and pick up arrows with your mouse and probe objects with them, and so on. Which I suspect is what Urs has in mind when he says below “I’d imagine the more ‘hands on’ such an application is, the more it would serve the intended purpose”.

Such coarse-grained-ness is why programmers got excited when Sun brought out Java in 1995, then demonstrated Java “applets”: Java programs running inside a Web browser, doing graphics that you could interact with, such as these nifty examples by Ken Perlin. By the way, part of the word “applet“‘s meaning is that the Java program must be coded according to certain conventions, so not every Java program is an applet.

Applet interaction is much finer-grained than what my demonstrations currently have; but a disadvantage would be that I’d have to rewrite most of my Prolog program, especially the categorical calculations and the example generator, in Java. Or would I? An applet can be programmed to request data from a Web server. So I could continue to do the calculations on my Web server, but implement the graphics in the applet in the browser.

But this raises another question. Even graphics as simple as drawing an ellipse with nice-looking letters inside it is hard to program using only the primitives Java provides for drawing. My demonstrations use Graphviz suite: I’d have to find or write a substitute for that, and as Aaron Denny says in another comment, that would not be much fun.

Moreover, what level of rendering do I want? Suppose I want to make a really memorable demonstration by having a knight “probe” an object with a map depicted as a lance, or a physicist “probe” an object with maps depicted as particles flung out by a cyclotron. I’d have to find an artist to draw and animate all these: sadly, depicting reality in pictures is much harder than doing so in words.

But perhaps not for much longer. I’m going to devote the next few paragraphs to the Java-based Alice, “an innovative 3D programming environment that makes it easy to create an animation for telling a story, playing an interactive game, or a video to share on the web”. Alice may eventually be extremely useful to those building maths animations, so I’ll explain a bit more. Alice is intended for teaching programming to novices. It contains a stock of “objects” — some of which are people, such as an ice-skater. You program these by dragging-and-dropping tiles representing actions (for the skater, these include spinning on the ice) and events such as mouse clicks. Thus you build “worlds” inhabited by animated objects that react to one another and to a user. Alice includes a 3D rendering engine — so if you program the ice-skater to spin, you’ll get a nicely rendered view, including details such as hair, tutu, and bare legs bending.

Alice has a built-in tutorial, which invited me to extend some supplied animations. One animation features a bunny whose nap is disturbed by a mobile phone; you have to make him jump up and down on the phone and squash it. Another has coloured penguins, and you have to make each one play a note when the mouse clicks on it. It only took five minutes or so to do these, by following the tutorial.

It sounds silly to be writing in a category theory blog about ice-skaters in tutus, bunnies jumping on mobile phones, and musical penguins that play scales when you hit them. But the point is that to make programming fun, and to concretely represent object-oriented “objects”, Alice’s creators are tying up with Electronic Arts’s video game The Sims. The next version of Alice, Alice 3.0, will let users build Sim-style animations using The Sims characters. And, I hope, Sims furniture, houses, etc. And, I also hope, simple shapes with which we can depict (categorical) objects and various types of arrow.

Alice runs in Java, so I’m hoping that those of us who don’t have the artistic and computer-game-programming skills to animate our ideas, will be able to do so with Alice, and make some really nice instructional applets. (And perhaps even a category theory visualisation kit, to help professionals express their ideas more efficiently than with LaTeXed diagrams? I recall reading a story, perhaps by Greg Egan, where mathematicians routinely built such animations to accompany published papers.) Anyway, to quote from Alice Press Release - 03/10/06:

EA [Electronic Arts] has agreed to help underwrite the development of Alice 3.0 — a popular, object-oriented, Java-based computer-programming environment created by Carnegie Mellon researchers — and provide essential arts assets from “The Sims™” — the best selling PC video game of all time.

The Sims content will transform the Alice software from a crude, 3D programming tool into a compelling and user-friendly programming environment. … Experts say that when the transformation is complete, the new programming environment will be in position to become the national standard for teaching software programming.

… “Getting the chance to use the characters and animations from The Sims is like teaching at an art school and having Disney give you Mickey Mouse,” said Computer Science Professor Randy Pausch, director of the Alice Project at Carnegie Mellon.

Getting back to methods for delivering demonstrations over the Web, I’ve talked about interactive Web pages like my demonstrations, and about Java applets. There’s also a programming language named JavaScript — no relation to Java, despite the confusing similarity in name — which is implemented to run inside Web browsers. It’s more closely integrated with them than Java is, and can do things like changing the colour of buttons when you click them — all the rather pointless special effects that many commercial Web sites seem to like. The Web browsers available when JavaScript first came out didn’t enable it to do graphics; newer ones can, by using either “SVG” (scaleable vector graphics) or the “CANVAS” element. These are what Jacques Distler refers to in his comment below that “ or Javascript+SVG seem like a much better bet, for this sort of thing, than Java/Flash”. The demo he points to is of Penrose tiling, implemented both ways.

I’m no expert on using these in JavaScript, but a Google search for “SVG Canvas” found me several comparative evaluations. The trouble with both is the same as for Java graphics: you must either code all the higher-level stuff, or find a rendering engine to do it.

Finally, Mike Stay commented that “For all practical purposes, Flash is available everywhere.
Flash 8 is in more than 99% of all browser installations.” The link is to a survey by Adobe, Flash’s makers, about the market “penetration” of Flash. That’s something I’ve no experience with yet.

Posted by: Jocelyn Paine on April 15, 2009 1:49 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

I just wanted to clarify that these aren’t Java Applets – they go through a CGI call to a server that does the computation instead of doing it on each user’s computer.

Posted by: Aaron Denney on April 7, 2009 10:48 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

I just wanted to clarify that these aren’t Java Applets – they go through a CGI call to a server that does the computation instead of doing it on each user’s computer.

Would it still be possible to maybe have the output more directly related to the input? Maybe it’s just my system, but for me when I hit one of these buttons I am eventually presented with a page that asks me to follow a link, and there finally the output if visisble.

I can’t tell about the technical problems faced here, but I’d imagine the more “hand on” such an application is, the more it would serve the intended purpose.

There are other aspects that don’t quite seem to work for me:

for instance I just hit “colimit” and the output displays a single arrow from one bubble to another. Is that intended?

The output of “terminal object” is similar, but I take it that here it is intended.

Posted by: Urs Schreiber on April 7, 2009 11:37 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

I’m sure it’s possible. The two most common approaches would be doing it as either flash, or a java applet. The question is really ease of implementation. These currently use the rather nice GraphViz suite, and a substitute would have to be found or written, and the code rewritten from prolog. None of which sounds much fun, frankly.

In addition, java and flash are still not guaranteed to be available on a significant minority of browsers.

Posted by: Aaron Denney on April 8, 2009 2:54 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

<canvas> or Javascript+SVG seem like a much better bet, for this sort of thing, than Java/Flash.

Posted by: Jacques Distler on April 8, 2009 5:02 PM | Permalink | PGP Sig | Reply to this

### Re: Graphical Category Theory Demonstrations

For all practical purposes, Flash is available everywhere. Flash 8 is in more than 99% of all browser installations.

Posted by: Mike Stay on April 8, 2009 11:05 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

Would it still be possible to maybe have the output more directly related to the input? Maybe it’s just my system, but for me when I hit one of these buttons I am eventually presented with a page that asks me to follow a link, and there finally the output if visible.

No, it’s not a problem with your system, everyone will see such a page. I’ve just written a long reply to John’s posting, where I explain how my demonstrations work and what the alternatives are. When a Web server follows the “CGI” style of interaction that my demonstrations use, it can only send back one page to the browser — although that page can link to others that the server also generates.

So amongst my alternatives were: (1) send back the input page but with a link to the results, as I do; or (2) send back the input page with the output embedded somewhere in it; or (3) send back an output page which links back to the input. Originally, I did (2), but changed it to (1) after these comments by John. Actually, I can’t now think why I didn’t do (3), which seems better than either.

for instance I just hit “colimit” and the output displays a single arrow from one bubble to another. Is that intended?

Yes, but you won’t see that every time. The colimit demonstration first generates a random diagram and a random functor into FiniteSet, and then takes the colimit. Limit works the same way. I’d have preferred to find a way for the user to draw their own diagrams, but from what I’ve explained about Web interaction, you can see why that’s harder. When you ran the demo and got your single arrow from one bubble to another, the generator must just happened to generate a particularly simple diagram. I’ll check that the demo gives the right output with these special cases, but that’s why.

The output of “terminal object” is similar, but I take it that here it is intended.

Yes, it is. There, it will happen every time.

By the way, I notice you use the word “eventually” about getting back the output. The demos are rather slow, for which I apologise. The only server I have access to is a commercial one, which is shared with a lot of business and personal users. Because people using the demos might want to generate a number of examples in quick succession, I had to reduce their process priority to avoid interfering with other users. (And sometimes the machine gets heavily loaded anyway, which slows things down.) So that’s why they don’t always run so fast.

Posted by: Jocelyn Paine on April 15, 2009 2:27 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

I was thinking that maybe it would be a good idea to seriously start an $n$Lab entry that provides detailed pedagical explanation and introdcution to limits and colimits by way of illustrated examples.

I created a template entry

$n$Lab: limits and colimits by example

which at the moment just tries to indicate what it might once contain. I was thinking that we could start adding simple examples of the kind that Jocelyn’s program generates illustrations for, and maybe include such illustrations in the page if possible, or at least link to them.

I should find time myself to add some content to this entry later, but maybe somebody else already feels inspired.

Posted by: Urs Schreiber on April 20, 2009 8:24 AM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

I was thinking that maybe it would be a good idea to seriously start an nLab entry that provides detailed pedagical explanation and introduction to limits and colimits by way of illustrated examples.

I created a template entry nLab: limits and colimits by example

Urs, what a nice idea! If anybody wants output from my program for specific limits or colimits in FiniteSet, send me a specification of them - hand- or machine-drawn diagrams would be fine, annotated with the sets and functions to use.

For my Dobbs blog, I’ve started writing an explanation of coproducts and pushouts for programmers, with examples in the Python programming language. Like the rest of this, that’s a spare-time thing at the moment, so may take a bit of time, but I’ll point you at it when it’s finished in case the nLab page could use it.

I’m writing it so that I can explain these concepts to programmers in a notation they’re happy with — Python, using only elementary sets and functions. I want to encourage readers to understand how the concepts work in good old FiniteSet, and then try using them to “glue” other kinds of data together. Especially, the kinds of data one finds in modelling cognition, such as neural nets. One paper that inspired to do this is:

Posted by: Jocelyn Paine on April 20, 2009 5:07 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

send me a specification

Or maybe you want to ahead yourself and start filling material at that entry?

Just if you have time. I’ll try to get back to that entry later today or tomorrow after I have finished something else.

Posted by: Urs Schreiber on April 20, 2009 5:38 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

This is a very nice start! What I would really like to see eventually is demonstrations in the bicategories rel and spn (over set, or maybe even over grpd), in particular residuations (right liftings and extensions), preferably even in graph form. I’m just terrible doing these computations by hand… Another useful thing for the teaching of category theory might be the conversion of the limit of some finite diagram (in set) into the canonical form using just products and equalizers, or pullbacks and the terminal object. It would also be nice if one could interactively change individual items (sets or functions / relations / spans) and see the desired construct update right away. Not sure, if these goals are too ambitious.

– Jürgen

Posted by: Jürgen Koslowski on May 5, 2009 12:36 AM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

Has anyone here had experience with crowd funding services?

After I wrote my Web-based category theory demonstrations, I thought with them as a proof of concept, it would be possible to get funding for improvements: tidying up the code, publishing it, adding other categories such as those suggested by John, doing applets and examples for nLab, writing articles to promote category theory in computing and cognitive science. It wasn’t. I contacted a lot of people for advice, and to discuss, for example, applying for collaborative grants.

One disheartener was the lack of response even amongst some who had told me how much they liked the demos. Others included the maths-department chairman who wouldn’t advertise the demos to his mathematicians because he didn’t think category theory was of interest, and the PhD who wanted all my source code for her thesis, but wasn’t willing to pay or get her department to pay. Plus the people who just didn’t answer emails. Kills enthusiasm, such things do, so eventually I got fed up and stopped.

However, one reader of the categories mailing list has suggested that I try crowd funding, perhaps through Indiegogo. This would be partly to pay for my time in supporting the software, which includes answering users’ questions about how it works and why their results are as they are, as well as about categorical matters related to the results. I’d also like to tidy up the source code and publish it, move it to a faster server, and perhaps attach a discussion forum. At the moment, all such activities come out of my unpaid spare time.

Any thoughts?

Posted by: Jocelyn Ireson-Paine on April 14, 2013 1:41 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

If you’d like collaborators, the trendy way to get them these days is to open-source your project and put it on GitHub. Does that appeal to you?

Posted by: Tom E on April 14, 2013 3:24 PM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

That’s a useful suggestion Tom, thanks. I’d need to do some work on the code first, to make it easier for other eyes to read.

Posted by: Jocelyn Ireson-Paine on April 25, 2013 7:18 AM | Permalink | Reply to this

### Re: Graphical Category Theory Demonstrations

What would you choose for a picture to symbolise category theory? Courtney Gibbon’s cartoon of Category and the Funky Functors? The Catsters having fun with adjunctions? The cover of Categories for the Working Mathematician? The aliens from Greg Egan’s Incandescence having an “AHA!” moment as they gaze at Interesting Truths in a suitably warped categorical mirror?

I ask because I’m trying to decide on a cover picture (similar to a Facebook cover picture) for the Indiegogo campaign I mentioned above. I’ll probably draw a cartoon, perhaps of human mathematicians having an “AHA!” moment as they gaze at a chain of transformations. But I’d be interested in other ideas.

Posted by: Jocelyn Ireson-Paine on May 28, 2013 5:21 PM | Permalink | Reply to this

Post a New Comment