Avoiding the axiom of choice, part I

I’m hard at work on my dissertation, and plan to get back to doing a bit of blogging based on stuff I’m writing and thinking about, as a way of forcing myself to explain things clearly and to potentially get some useful feedback. Yes, this means you can expect more on species! But first, I’ll write a few posts about the axiom of choice and anafunctors, which have turned out to be fundamental to some of the work I’ve been doing. If you look at the nLab page for anafunctors, linked above, you could be forgiven for thinking this is a pretty esoteric corner of category theory, but in fact it’s not too bad once you grasp the essentials, and is quite relevant for anyone interested in category theory and constructive/computational foundations (such as homotopy type theory (HoTT)).

The Axiom of Choice

The (in)famous Axiom of Choice (hereafter, AC) can be formulated in a number of equivalent ways. Perhaps the most well-known is:

The Cartesian product of any collection of non-empty sets is non-empty.

Given a family of sets \{X_i \mid i \in I\}, an element of their Cartesian product is some I-indexed tuple \{x_i \mid i \in I\} where x_i \in X_i for each i. Such a tuple can be thought of as a function (called a choice function) which picks out some particular x_i from each X_i.

The Axiom of Choice in type theory, take 1

We can express this in type theory as follows. First, we assume we have some type I which indexes the collection of sets; that is, there will be one set for each value of type I. Given some type A, we can define a subset of the values of type A using a predicate, that is, a function P : A \to \star (where \star denotes the universe of types). For some particular a : A, applying P to a yields a type, which can be thought of as the type of evidence that a is in the subset P; a is in the subset if and only if P\ a is inhabited. An I-indexed collection of subsets of A can then be expressed as a function C : I \to A \to \star. In particular, C(i,a) is the type of evidence that a is in the subset indexed by i. (Note that we could also make A into a family of types indexed by I, that is, A : I \to \star, but it wouldn’t add anything to this discussion.)

A set is nonempty if it has at least one element, so the fact that all the sets in C are nonempty can be modeled by a dependent function which yields an element of A for each index, along with a proof that it is contained in the corresponding subset.

(i : I) \to (a : A) \times C(i,a)

(Note I’m using the notation (x:X) \to T(x) for dependent function types instead of \prod_{x:X} T(x), and (x:X) \times T(x) for dependent pairs instead of \sum_{x:X} T(x).) An element of the Cartesian product of C can be expressed as a function I \to A that picks out an element for each I (the choice function), together with a proof that the chosen elements are in the appropriate sets:

(g : I \to A) \times ((i : I) \to C(i, g(i)))

Putting these together, apparently the axiom of choice can be modelled by the type

((i : I) \to (a : A) \times C(i,a)) \to (g : I \to A) \times ((i : I) \to C(i, g(i)))

Converting back to \Pi and \Sigma notation and squinting actually gives some good insight into what is going on here:

\left( \prod_{i : I} \sum_{a : A} C(i,a) \right) \to \left( \sum_{g : I \to A} \prod_{i : I} C(i, g(i)) \right)

Essentially, this says that we can “turn a (dependent) product of sums into a (dependent) sum of products”. This sounds a lot like distributivity, and indeed, the strange thing is that this is simply true: implementing a function of this type is a simple exercise! If you aren’t familiar with dependent type theory, you can get the intuitive idea by implementing a non-dependent Haskell analogue, namely something of type

(i -> (a,c)) -> (i -> a, i -> c).

Not too hard, is it? (The implementation of the dependent version is essentially the same; it’s only the types that get more complicated, not the implementation.) So what’s going on here? Why is AC so controversial if it is simply true in type theory?

The Axiom of Choice in type theory, take 2

This is not the axiom of choice you’re looking for. — Obi-Wan Funobi

The problem, it turns out, is that we’ve modelled the axiom of choice improperly, and it all boils down to how non-empty is defined. When a mathematician says “S is non-empty”, they typically don’t actually mean “…and here is an element of S to prove it”; instead, they literally mean “it is not the case that S is empty”, that is, assuming S is empty leads to a contradiction. (Actually, it is a bit more subtle yet, but this is a good first approximation.) In classical logic, these viewpoints are equivalent; in constructive logic, however, they are very different! In constructive logic, knowing that it is a contradiction for S to be empty does not actually help you find an element of S. We modelled the statement “this collection of non-empty sets” essentially by saying “here is an element in each set”, but in constructive logic that is a much stronger statement than simply saying that each set is not empty.

(I should mention at this point that when working in HoTT, the best way to model what classical mathematicians mean when they say “S is non-empty” is probably not with a negation, but instead with the propositional truncation of the statement that S contains an element. Explaining this would take us too far afield; if you’re interested, you can find details in Chapter 3 of the HoTT book, where all of this and much more is explained in great detail.)

From this point of view, we can see why the “AC” in the previous section was easy to implement: it had to produce a function choosing a bunch of elements, but it was given a bunch of elements to start! All it had to do was shuffle them around a bit. The “real” AC, on the other hand, has a much harder job: it is told some sets are non-empty, but without any actual elements being mentioned, and it then has to manufacture a bunch of elements out of thin air. This is why it has to be taken as an axiom; we can also see that it doesn’t fit very well in a constructive/computational context. Although it is logically consistent to assume it as an axiom, it has no computational interpretation, so anything we define using it will just get stuck operationally.

So, we’ll just avoid using AC. No problem, right?

Don’t look now, but AC is behind you

The problem is that AC is really sneaky. It tends to show up all over the place, but disguised so that you don’t even realize it’s there. You really have to train yourself to think in a fundamentally constructive way before you start to notice the places where it is used. Next time I’ll explain one place it shows up a lot, namely, when defining functors in category theory (though thankfully, not when defining Functor instances in Haskell).

Posted in category theory, math, species | Tagged , , , , , | 17 Comments

Diagrams 1.0

The diagrams team is very pleased to announce the 1.0 release of diagrams, a framework and embedded domain-specific language for declarative drawing in Haskell. Check out the gallery for some examples of what it can do. Diagrams can be used for a wide range of purposes, from data visualization to illustration to art, and diagrams code can be seamlessly embedded in blog posts, LaTeX documents, and Haddock documentation, making it easy to incorporate diagrams into your documents with minimal extra work.

       

What’s new

Brent recently gave a talk at the New York Haskell Users’ Group presenting the new release. You can find videos of the talk on vimeo: part 1 presents a basic introduction to the library, and part 2 talks about mathematical abstraction and DSL design. The slides are also available.

This release includes a number of significant new features and improvements. Highlights include:

  • Support for drawing arrows between given points or between diagrams, with many options for customization (tutorial, documentation, API).

  • A new framework for creating custom command-line-driven executables for diagram generation (tutorial, API).

  • Offsets of trails and paths, i.e. compute the trail or path lying a constant distance from the given one (documentation, API).

  • A new API, based on Metafont, for constructing cubic splines with control over things like tangents and “tension” (tutorial, API).

  • Tangent and normal vectors of segments and trails (API).

  • Alignment can now be done by trace in addition to envelope (API).

  • The lens package is now used consistently for record fields throughout the library (documentation).

  • Across-the-board improvements in performance and size of generated files.

See the release notes for full details, and the migration guide for help porting your diagrams 0.7 code to work with diagrams 1.0.

Try it out

For the truly impatient:

cabal install diagrams

Diagrams is supported under GHC 7.4 and 7.6.

To get started, read the quick start tutorial, which will introduce you to the fundamentals of the framework and provide links for further reading.

For those who are less impatient and want to really dig in and use the power features, read the extensive user manual. There is also a growing collection of tutorials on specific topics.

Get involved

Diagrams has a friendly and growing community of users and developers. To connect with the community, subscribe to the project mailing list, and/or come hang out in the #diagrams IRC channel on freenode.org for help and discussion. Development continues stronger than ever, and there are a wide range of projects available for new contributors of all levels of Haskell skill. Make some diagrams. Fix some bugs. Submit your cool examples for inclusion in the gallery or your cool code for inclusion in the diagrams-contrib package.

Happy diagramming!

Brought to you by the diagrams team:

  • Daniel Bergey
  • Jeff Rosenbluth
  • Ryan Yates
  • Brent Yorgey

with contributions from:

  • Jan Bracker
  • Conal Elliott
  • Daniil Frumin
  • Sam Griffin
  • Niklas Haas
  • Peter Hall
  • Claude Heiland-Allen
  • Deepak Jois
  • John Lato
  • Felipe Lessa
  • Chris Mears
  • Ian Ross
  • Carlos Scheidegger
  • Vilhelm Sjöberg
  • Michael Sloan
  • Jim Snavely
  • Luite Stegeman
  • Kanchalai Suveepattananont
  • Michael Thompson
  • Scott Walck
Posted in diagrams, haskell, projects | Tagged , , | 2 Comments

Catsters guide

tl;dr: https://byorgey.wordpress.com/catsters-guide-2/

In an attempt to solidify and extend my knowledge of category theory, I have been working my way through the excellent series of category theory lectures posted on Youtube by Eugenia Cheng and Simon Willerton, aka the Catsters.

Edsko de Vries used to have a listing of the videos, but it is no longer available. After wresting a copy from a Google cache, I began working my way through the videos, but soon discovered that Edsko’s list was organized by subject, not topologically sorted. So I started making my own list, and have put it up here in the hopes that it may be useful to others. Suggestions, corrections, improvements, etc. are of course welcome!

As far as possible, I have tried to arrange the order so that each video only depends on concepts from earlier ones. Along with each video you can also find my cryptic notes; I make no guarantee that they will be useful to anyone (even me!), but hopefully they will at least give you an idea of what is in each video.

I have a goal to watch two videos per week (at which rate it will take me about nine months to watch all of them); I will keep the list updated with new video links and notes as I go.

Posted in haskell, math, teaching | Tagged | 1 Comment

In defense of drawing by coding

Just some half-baked thoughts in repsonse to Bret Victor’s talk, Drawing Dynamic Visualizations (along with his addendum here). As usual, it is a fun and inspiring talk, so if you haven’t seen it I highly recommend it; but I will summarize it here.

He starts by surveying the state-of-the-art in options for the creative scientist who wants to visualize some data. The options he outlines are:

  1. Use some program like Excel which has a standard repertoire of graphs it can generate. The problem with this approach is that it completely stifles any creativity and freedom in visualizing data.

  2. Use a drawing program like Illustrator or Inkscape. This gives more freedom, of course, but the process is tedious and the results cannot easily be modified.

  3. The final option is to write some code in a framework like Processing or d3.js. The problem here, Victor says, is that you are just staring at a mass of symbols with no immediate, dynamic feedback.

He then goes on to demo a really cool prototype tool that allows drawing using a graphical interface, a bit like Illustrator or Inkscape. But the similarity is only surface deep: where those programs are restrictive and inflexible, Victor’s is richly interactive and editable. Instead of drawing concretely located lines, circles, and so on, it infers the relationships between things you are drawing, so updating the characteristics or positioning of one element automatically updates all the others which depend on it as well. In other words, one can construct a generic, editable visualization just by drawing one particular example of it.

Victor is quite negative about option (3) above—drawing by coding—referring to programming as “blindly manipulating symbols”: “blind” because you can’t actually see the picture you are creating while writing the program.

What I would like to point out is that in fact, despite his negativity about drawing by programming, when using his graphical tool Victor is still programming! It’s just that he has a graphical interface which allows him to construct certain sorts of programs, instead of writing the programs directly. In fact, you can see the programs he constructs on the left side of the screen in his tool. They appear to be structured imperative programs, consisting of sequences of drawing instructions together with things like loops and conditionals.

The problem is that this kind of higher-level interface cannot provide for all possible circumstances (unless you somehow make it Turing complete, but in that case it probably ceases to be at all intuitive). For example, Victor impressively drags and drops some spreadsheet data into his application. But what if I want to use data which is structured in some other format? What if I need to preprocess the data in some computationally nontrivial way? Or on the drawing end, what if I want to draw some shapes or compute some positions in a way that the interface does not provide for? We can’t completely get away from the need to write code in the service of visualization.

What we really need is a more inclusive idea of “programming”, and a continuum between direct manipulation of images and manipulation of symbols to produce images. Symbolic methods, of course, can be incredibly powerful—there is nothing inherently wrong with manipulating symbols.

More specifically, I am proposing something like the following:

  1. First, I am all for making elegant and powerful high-level graphical interfaces for constructing interactive, editable drawings—and not just drawings but code that generates drawings. This can probably be pushed quite far, and there is lots of HCI research to be done here. There are also some very interesting questions relating to bidirectional computation here: making an edit via the graphical interface corresponds to some sort of edit to the code; how can this be done in a sensible and consistent way?

  2. Recognizing, however, that sometimes you do need to actually write some code, how can we make the underlying language as beautiful as possible, and how can we make the interaction between the two systems (code and higher-level graphical interface) as elegant and seamless as possible? The ideal is for a user to be able to flow easily back and forth between the two modes, ideally spending much of their time in a high-level graphical mode.

Of course, if you hadn’t guessed by now, in the long term this is the sort of direction I would love to go with diagrams… though I need to finish my dissertation first (more on that subject soon).

Posted in diagrams | Tagged , , , , , , , | 3 Comments

Come visit the FARM!

Registration is now open for the first (!) ACM SIGPLAN Workshop on Functional Art, Music, Modeling and Design (FARM), to be held in Boston on September 28 (the day after ICFP). I’m really excited—it’s shaping up to be a really awesome event. Check out the list of accepted papers and demos:

  • Samuel Aaron and Alan F. Blackwell. From Sonic Pi to Overtone: Creative Musical Experiences with Domain-Specific and Functional Languages
  • Henrik Bäärnhielm, Mikael Vejdemo-Johansson and Daniel Sundström. Using Haskell as DSL for controlling immersive media experiences (Demo)
  • Guillaume Baudart, Louis Mandel and Marc Pouzet. Programming Mixed Music in ReactiveML
  • Jean Bresson, Raphael Foulon and Marco Stroppa. Reduction as a Transition Controller for Sound Synthesis Events
  • Kelsey D’Souza. PySTEMM – A STEM Learning Tool for Exploring and Building Executable Concept Models (Demo)
  • Andy Gill and Brent A. Yorgey. Functional active animation (Demo)
  • Jason Hemann and Eric Holk. Visualizing the Turing Tarpit
  • Paul Hudak. Euterpea: From Signals to Symphonies (Demo)
  • David Janin, Florent Berthaut, Myriam Desainte-Catherine, Yann Orlarey and Sylvain Salvati. The T-Calculus : towards a structured programing of (musical) time and space
  • David Janin and Florent Berthaut. LiveTuiles for tiled composition of audio patterns (Demo)
  • Thomas Jordan. Spontaneous Musical Explorations of Visible Symmetric Structures (Demo)
  • Hendrik Vincent Koops, José Pedro Magalhães and W. Bas de Haas. A Functional Approach To Automatic Melody Harmonisation
  • José Pedro Magalhães, Bas De Haas, Gijs Bekenkamp, Dion ten Heggeler and Tijmen Ruizendaal. Chordify: Chord Transcription for the Masses (Demo)
  • Donya Quick and Paul Hudak. Grammar-Based Automated Music Composition in Haskell
  • Chung‐chieh Shan and Dylan Thurston. Braiding in circles (Demo)

Note the early registration deadline is August 22, so don’t delay! In case you’re not already convinced, here’s a short description of the workshop and what it’s trying to accomplish:

The functional programming community is largely interested in writing beautiful programs. This workshop is intended to gather researchers and practitioners interested in writing beautiful programs that generate beautiful artifacts. Such artifacts may include visual art, music, 3D sculptures, animations, GUIs, video games, physical models, architectural models, choreographies for dance, poetry, and even physical objects such as VLSI layouts, GPU configurations, or mechanical engineering designs.

The goal of FARM is to gather together researchers, practitioners, and educators in this interdisciplinary field, as well as anyone else with even a casual interest in the area. We wish to share ideas, look for common ground, and encourage more activity. We also hope to legitimize work in the field and facilitate potential collaboration among the participants.

Posted in haskell | Leave a comment

FARM 2013: call for demonstration proposals

Do you enjoy writing beautiful code to produce beautiful artifacts? Have something cool to show off at the intersection of functional programming and visual art, music, sound, modeling, visualization, or design?

The deadline for submitting a paper has passed, but the Workshop on Functional Art, Music, Modeling and Design (FARM 2013) is currently seeking proposals for 10-20 minute demonstrations to be given during the workshop. For example, a demonstration could consist of a short tutorial, an exhibition of some work, or even a livecoding performance. Slots for demonstrations will be shorter than slots for accepted papers, and will not be published as part of the formal proceedings, but can be a great way to show off interesting work and get feedback from other workshop participants. A demonstration slot could be a particularly good way to get feedback on work-in-progress.

A demo proposal should consist of a 1 page abstract, in PDF format, explaining the proposed content of the demonstration and why it would be of interest to the attendees of FARM. Proposals will be judged on interest and relevance to the stated goals and themes of the workshop.

Submissions can be made via EasyChair.

Posted in meta | Tagged , , , , , , , , | Leave a comment

Workshop on Functional Art, Music, Modeling and Design

I’m helping organize a new workshop, FARM, to be held in Boston this September (right after ICFP). Many readers of this blog may have already seen the announcement, but I thought it worth saying a bit more about it here, in the spirit of trying to spread the word as widely as possible.

The short of it is—it should be super interesting and a lot of fun. If you are at all interested in the intersection of functional programming and design, art, music—anything that has to do with using beautiful code to produce beautiful artifacts—you should consider submitting a paper, or planning to attend! Papers can be submitted in two categories, full papers novel research contribution) and “aesthetic applications” (which should describe some sort of beautiful way to produce something beautiful). The deadline for submissions is June 14. See the website for more details.

Posted in meta | Tagged , , , , , , , , | 2 Comments