Status

Status update: A new library, Lathe Ordinals

I pulled out my ordinal code from Lathe Morphisms into its own library, Lathe Ordinals. It’s like a lot of ordinal number libraries out there already. This Maple documentation is a pretty thorough, if terse, description of the kind of thing I’m implementing for Racket.

The purpose of the Lathe Morphisms library has been diluting a bit, and I’m trying to rein that back in. (I might rename it in the near future, so that link might break soon.) I started Lathe Morphisms as a place to explore category-theoretic concepts so I could build up to understanding monads (in the classical mathematics sense of monads, rather than just the computer science sense popularized by Haskell, Scala, etc.) and higher categories. I figured the practical benefit for programmers would be the utilities for, say, constructing a monad on pairs (String, a) out of a monoid on String. That is, Lathe Morphisms would offer ways to represent algebraic structures (made of sets (types), structure (operations), and properties (laws that hold for the operations)) and translate between them.

I called it Lathe Morphisms because I figured if someone wasn’t interested in dense category theory terminology, they could see it wasn’t the library for them. Nevertheless, being a newcomer into a lot of this terminology myself, I also wanted to take this unique opportunity to document the terminology in the way I always hoped I’d see it documented, to help out the next person who comes along.

When various things I was doing seemed to call for ordinal arithmetic (as I discussed in my previous post) and I started implementing those operations in Racket, I put that code in Lathe Morphisms for a few reasons. One reason is that ordinal numbers correspond to “well-orders,” an algebraic structure which might be just like the ones Lathe Morphisms already deals with. The other reason was that, like the rest of the mathematical jargon in Lathe Morphisms, the term “ordinal” might be something that only a mathematically inclined programmer would be interested in.

Those ordinals didn’t quite mesh with the rest of Lathe Morphisms like I thought. I got an implementation of Cantor normal form ordinals working without really modeling an algebraic concept of “well-orders” first, and if the ordinal arithmetic operations themselves are characterized by any particular algebraic structures, I hadn’t yet explored those in Lathe Morphisms.

(I think addition and multiplication are each left-cancellative monoids, but what about exponentiation? But I don’t even know if I need multiplication for most of what I’m doing, let alone exponentiation, so I don’t know what particular kind of “ordinal arithmetic algebra” my ordinal-using code should abstract over.)

The other reason for bundling ordinals with Lathe Morphisms, that “ordinal” might be obscure terminology, didn’t really require me to put this code in Lathe Morphisms itself. I could just as well put it in a library called Lathe Ordinals, a name which would just as quickly tell programmers what they’re getting into.

So that’s what I did; I took them out of Lathe Morphisms and put them into a library called Lathe Ordinals!

Polishing ordinals for use as a Racket library

Meanwhile, I did some refactoring. I gave epsilon zero a representation for the sake of certain places where it made sense to use, I changed some naming conventions so that the library could potentially introduce support for larger ordinals in the future (exporting predicates onum<=e0? and onum<e0? rather than simply onum?), and I changed the representation of finite ordinals to coincide with Racket’s exact nonnegative integers.

Treating Racket numbers as ordinals means that if a library expects Lathe Ordinals ordinals, a user of that library can usually get by just fine if they only ever use the numbers they’re familiar with. So people hopefully won’t really need to understand ordinals to get their libraries’ basic functionality to work, which oughta make the advanced functionality more approachable if they become interested in it.

The condition Lathe Ordinals is in

I wouldn’t say Lathe Ordinals is a very stable library yet.

The naming convention in particular seems pretty awkward in places. I’m calling left division onum-untimes right now! And I’m calling left subtraction onum-drop. I might change those to onum-match-times and onum-match-plus, the idea being that these are like a generalization of pattern-matching to one well-behaved case of matching an infinitely deep pattern on an infinitely deep data structure.

There’s also a distinct lack of certain operations at this point, like the ordinal logarithm.

I’ve written some documentation, but I haven’t made a thorough pass to document all the operations yet.

So I don’t know if I’m gonna holler about Lathe Ordinals from the rooftops or anything, and I’m making this post primarily as a status update.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s