1
$\begingroup$

A Type-0 language (in the Chomsky hierarchy) is Turing complete and so you can encode all machines in them - you only need a compiler which translates it to the respective machine code. Appearently, there are categories which also represent programming languages. So how do you encode a programm in a category?

I guess this relates most to functional programming languages. Is (my idea) every machine code equivalent to some morphism? Can I define a category with enough structure such that there a functors to specific categories which equal specific programs? (I see that categories in the theory of computations seem to be used in at least two way, one is related to automata, on to types and monads.)

The question arose when reading cs.stackexchange.com ... is-category-theory-useful-for-learning-functional-programming? and the links there, like the Haskell category tutorial.

$\endgroup$
2
  • $\begingroup$ You can encode programs as numbers, and you can encode numbers as sets, and you can encode sets as categories, so yes, technically, you can encode programs as categories. This is totally unhelpful, however. $\endgroup$
    – Zhen Lin
    Oct 17, 2012 at 14:48
  • $\begingroup$ @ZhenLin: ...yes, I'm more expecting the algebra to mirror the functional properties. Of course, you could always say "Hey, SET contains practically everything you've seen before, so question answered!". :P $\endgroup$
    – Nikolaj-K
    Oct 17, 2012 at 15:02

1 Answer 1

Reset to default
3
$\begingroup$

I don't know how to give an answer that is much more helpful than Zhen Lin's comment, but I'll try.

Categories are very general things, and programs are very varied things, so there are many, many ways one could "encode" (I would say "describe") a program as a category. As long as you can define a set of objects which are relevant to the program somehow, and a set of morphisms between those objects which are closed under composition (and composition is associative), you've described the program as a category.

The objects could be possible inputs and outputs of the program, and the morphisms could represent the way the program maps inputs to outputs. Or, I suppose the program states could be the objects with the morphisms being the allowable transitions between those states. (The requirement for an identity morphism means that a state would be allowed to transition to itself, which might be a bit odd.)

Yes, once you've described your program as a category, you could define functors between it and other categories (which may be other programs) but there is similarly no "standard" way to do this that I've seen. Which objects and morphisms (and functors) you choose will influence what kinds of further things you can model about your program once you've described it as a category.

(Note that I've talked about describing a program as a category, since that seemed to be what you were asking about, but now I'm not so sure. You could also describe a programming language as a category, in which case your program would simply be one of the objects (or morphisms) in that category.)

Edit: I'd just like to add that if you are talking about describing a program as an object or morphism in a category for a programming language (such as a function in Hask), then the term "encode" sounds even less appropriate. Objects in category theory are quite opaque -- there's no way to examine them except to say things about the morphisms that apply to them.

I should also mention for completeness (though I know very little about it) that any category with sufficient structure supports an internal logic, which may even be as powerful as the lambda calculus (which is Turing-complete); so there is this (very different!) sense in which one may have "programs" with respect to a category.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .