Operads in Ruby
Short version: I'm going to write a mildly cool and somewhat useful utility in Ruby which shows off Ruby's reflection capabilities and has something to do with my PhD thesis.
OK, first some background. A category is a directed graph for which, given any path of arrows from some vertex A to some vertex B, there's a unique way of "composing" them to give an arrow directly from A to B. This isn't the usual definition, which is given in terms of associative binary composition (f : A → B and g : B → C compose to g.f : A → C) and identities (id: A → A such that f.id = f and id.g = g for all f and g), but it's equivalent to it.
Categories are very useful, as they model all kinds of useful mathematical objects. For instance, every partially-ordered set is a category (put an arrow A → B if A ≤ B, and "compose" using transitivity), every group (closed collection of symmetries of some object) is a category with only one vertex and every arrow invertible, and so on. But they were really invented to describe entire universes of discourse: for instance, there's a category whose vertices are sets and whose arrows are functions (you have to do some fiddling to avoid Russell's Paradox: we'll take that as read), and another whose vertices are groups and whose arrows are homomorphisms, and in general there's a category whose vertices are any type of mathematical structure and whose arrows are the appropriate type of structure-preserving transformation between them. One category which has attracted considerable attention is the category Hask, whose vertices are Haskell types and whose arrows are Haskell functions.
As useful as categories are, they're not the end of the story, and several related structures are also important. For instance, you might like your "hom-sets" (sets of arrows between two specified vertices) to be something other than sets: abelian groups, say, or partially-ordered sets, or real numbers (which gives you something very close to a metric space), or even categories (which gives you the notion of "2-category"). This is called "enriched" category theory. Composition then has to respect the structure of your hom-objects: in fact, we want our composition operations to be arrows in the category of our hom-objects. Hask can be thought of as a category enriched in itself.
[Technical point: yes, you can have two categories with the same vertices but different arrows. We enrich with respect to a category, not just a collection of objects.]
Another useful generalisation is to "multicategories". Whereas in an ordinary category our arrows have one source and one target, in a multicategory our arrows have one target, but many sources. So they're something like a funnel, drawing all their sources into the target. The obvious example is functions with more than one argument: a function from AxBxC to D can be considered a funnel A,B,C → D. We have associative composition of funnels and identity funnels (of arity 1) as before:
The categorically sophisticated will be asking "what's the point? Why can't we just consider arrows whose sources are finite products?" (or tensors in some monoidal category, for the even more sophisticated): well, it turns out that multicategories are more general than that, in the sense that there are multicategories which aren't the underlying multicategory of any monoidal category. And besides, in many respects they're easier to work with, providing as they do a more minimal interface: we can see, for instance, that a multicategory provides exactly the interface we need to do enrichment. Composition of paths A → B → C → D → E is a funnel (A → B, B → C, C → D, D → E) → (A → E), where each X → Y is a vertex in your multicategory.
A useful class of multicategories are the operads, which are one-vertex multicategories (if your one vertex is *, then you have funnels from no copies of * to *, funnels from one copy of * to *, funnels (*,*) → *, funnels (*,*,*) → *, etc.). Both michiexile and I use enriched operads in our work: he tends to enrich in the multicategory of vector spaces and multilinear maps, and I tend to enrich in the multicategory of categories and functors.
OK, that's the maths out of the way, on to the code. The ability to do categorical composition of functions is useful, so maybe the multicategorical kind would be useful too? Ideally, we'd like a compose function which took a function f and a list of functions g1, g2, ... gn, and returned the function f.(g1,...gn) which takes (x11, ... xnmn) to f(g1(x11 ... x1m1) ... g1(xn1 ... xnmn)) Unpleasant multiple sequences seem to be an unfortunate fact of life when dealing with this stuff. Anyway, here's an implementation in Ruby:
class Method
def compose(*rest)
lambda {|*args|
intermediates = []
args_used = 0
for func in rest
arity = func.arity
func_args = args[args_used .. args_used + arity - 1]
intermediates.push(func.call(*func_args))
args_used += arity
end
self.call(*intermediates)
}
end
end
# Test code
def plus(x,y)
x + y
end
plusmeth = method(:plus)
addfour = plusmeth.compose(plusmeth, plusmeth)
puts addfour.call(1,1,1,1) This prints 4, as expected. addfour is the function (w,x,y,z) → (w+x)+(y+z). Making compose a method of the first function seemed a bit more Rubyish. It's a bit messier than it needs to be because in Ruby func means func(), so you have to be a bit tricksy about passing functions around as objects (thanks, ryani!). My first attempt had explicit returns for the functions, which gave me LongJumpErrors - removing the returns fixed this, for reasons I completely fail to understand. But there are compensations: you can find the arity of a function by calling its arity method, and once you've done the list-munging necessary to ensure every function gets handed the correct arguments, you can pass a function a list of arguments Perl-style by using the *-modifier.
I'm sure this code can be improved, and I'd love to hear how. I don't think it's possible to write a function like this in vanilla Haskell, and writing one in Template Haskell is beyond my template-fu. It would be possible in Perl, but because of Perl's eccentric argument-passing conventions, you'd have to manually pass the arities in. This also uglifies the code somewhat.
OK, first some background. A category is a directed graph for which, given any path of arrows from some vertex A to some vertex B, there's a unique way of "composing" them to give an arrow directly from A to B. This isn't the usual definition, which is given in terms of associative binary composition (f : A → B and g : B → C compose to g.f : A → C) and identities (id: A → A such that f.id = f and id.g = g for all f and g), but it's equivalent to it.
Categories are very useful, as they model all kinds of useful mathematical objects. For instance, every partially-ordered set is a category (put an arrow A → B if A ≤ B, and "compose" using transitivity), every group (closed collection of symmetries of some object) is a category with only one vertex and every arrow invertible, and so on. But they were really invented to describe entire universes of discourse: for instance, there's a category whose vertices are sets and whose arrows are functions (you have to do some fiddling to avoid Russell's Paradox: we'll take that as read), and another whose vertices are groups and whose arrows are homomorphisms, and in general there's a category whose vertices are any type of mathematical structure and whose arrows are the appropriate type of structure-preserving transformation between them. One category which has attracted considerable attention is the category Hask, whose vertices are Haskell types and whose arrows are Haskell functions.
As useful as categories are, they're not the end of the story, and several related structures are also important. For instance, you might like your "hom-sets" (sets of arrows between two specified vertices) to be something other than sets: abelian groups, say, or partially-ordered sets, or real numbers (which gives you something very close to a metric space), or even categories (which gives you the notion of "2-category"). This is called "enriched" category theory. Composition then has to respect the structure of your hom-objects: in fact, we want our composition operations to be arrows in the category of our hom-objects. Hask can be thought of as a category enriched in itself.
[Technical point: yes, you can have two categories with the same vertices but different arrows. We enrich with respect to a category, not just a collection of objects.]
Another useful generalisation is to "multicategories". Whereas in an ordinary category our arrows have one source and one target, in a multicategory our arrows have one target, but many sources. So they're something like a funnel, drawing all their sources into the target. The obvious example is functions with more than one argument: a function from AxBxC to D can be considered a funnel A,B,C → D. We have associative composition of funnels and identity funnels (of arity 1) as before:
The categorically sophisticated will be asking "what's the point? Why can't we just consider arrows whose sources are finite products?" (or tensors in some monoidal category, for the even more sophisticated): well, it turns out that multicategories are more general than that, in the sense that there are multicategories which aren't the underlying multicategory of any monoidal category. And besides, in many respects they're easier to work with, providing as they do a more minimal interface: we can see, for instance, that a multicategory provides exactly the interface we need to do enrichment. Composition of paths A → B → C → D → E is a funnel (A → B, B → C, C → D, D → E) → (A → E), where each X → Y is a vertex in your multicategory.
A useful class of multicategories are the operads, which are one-vertex multicategories (if your one vertex is *, then you have funnels from no copies of * to *, funnels from one copy of * to *, funnels (*,*) → *, funnels (*,*,*) → *, etc.). Both michiexile and I use enriched operads in our work: he tends to enrich in the multicategory of vector spaces and multilinear maps, and I tend to enrich in the multicategory of categories and functors.
OK, that's the maths out of the way, on to the code. The ability to do categorical composition of functions is useful, so maybe the multicategorical kind would be useful too? Ideally, we'd like a compose function which took a function f and a list of functions g1, g2, ... gn, and returned the function f.(g1,...gn) which takes (x11, ... xnmn) to f(g1(x11 ... x1m1) ... g1(xn1 ... xnmn)) Unpleasant multiple sequences seem to be an unfortunate fact of life when dealing with this stuff. Anyway, here's an implementation in Ruby:
class Method
def compose(*rest)
lambda {|*args|
intermediates = []
args_used = 0
for func in rest
arity = func.arity
func_args = args[args_used .. args_used + arity - 1]
intermediates.push(func.call(*func_args))
args_used += arity
end
self.call(*intermediates)
}
end
end
# Test code
def plus(x,y)
x + y
end
plusmeth = method(:plus)
addfour = plusmeth.compose(plusmeth, plusmeth)
puts addfour.call(1,1,1,1) This prints 4, as expected. addfour is the function (w,x,y,z) → (w+x)+(y+z). Making compose a method of the first function seemed a bit more Rubyish. It's a bit messier than it needs to be because in Ruby func means func(), so you have to be a bit tricksy about passing functions around as objects (thanks, ryani!). My first attempt had explicit returns for the functions, which gave me LongJumpErrors - removing the returns fixed this, for reasons I completely fail to understand. But there are compensations: you can find the arity of a function by calling its arity method, and once you've done the list-munging necessary to ensure every function gets handed the correct arguments, you can pass a function a list of arguments Perl-style by using the *-modifier.
I'm sure this code can be improved, and I'd love to hear how. I don't think it's possible to write a function like this in vanilla Haskell, and writing one in Template Haskell is beyond my template-fu. It would be possible in Perl, but because of Perl's eccentric argument-passing conventions, you'd have to manually pass the arities in. This also uglifies the code somewhat.