Computer language and category theory

From: Jon Haugsand (jonhaug_at_ifi.uio.no)
Date: 11/18/04 

Date: 18 Nov 2004 16:40:33 +0100

Is there any work done one computer languages and category theory? To
clarify, what I am looking into is something like the following:

Given the language

  S ::= A | B
  A ::= aa | ba | A-aa | B-ba
  B ::= ab | bb | A-ab | B-bb

 Thus, the set of sentences in S is sequences
 {a,b}{a,b}-{a,b}{a,b}-... such that the letter in front of the dash
 (-) is the same as the letter behind it.

I think this language can be described as a category as follows:

C=<Obj,Morph,*>

  Obj={A,B}
  Morph=Hom(A,A) U Hom(A,B) U Hom(B,A) U Hom(B,B)
  Hom(x,y) = any sentence s in S such that it starts with an x and
             ends with an y.

             E.g. bb-ba, ba, ba-aa-ab-ba \in Hom(B,A)

The operator * is defined as follows:
  Given x \in Hom(X,Y) and y \in Hom(Y,Z) such that neither x nor y
  is a unit morphism. Then x*y = x-y

The unit elements of Hom(A,A) and Hom(B,B) is just an empty sentence
handled specially:

  x * e = e * x = x

(a) Does this look sensible?

However, I don't have such a simple language, but rather a slightly
more complicated one:

  T ::= A | B
  A ::= aa | ba | A-aa | B-ba
  B ::= ab | bb | A-ab | B-bb | A-K
  K ::= ( A )-B | ( B )-B

The K, introduced in order to be able to create a tree-like structure,
makes the elements of T unsuited to form a set of morphisms, as
each morphism in a category have excactly one source object and one
destination object.

(b) What kind of mathematical tools should I study to handle language
constructs like the language T?

In reality, our objects are a little different, but not in essence.
My collegue wants to define something like a "partial parametriced
monoid", an animal I never before have encountered. Partiality
follows from the fact that you cannot take two arbitrary elements of S
(or T) and form a new element of S (or T). Parametrization does
occure in some sense in the language T, where we must choose whether
to insert an A sentence into the ( A )-B or a B into the same meta
sentence. (Was this understandable?)

However, I don't like such animals. So I wonder if there is some use
of category theory or something else that have been used to model
language like constructs. 

-- 
Jon Haugsand
  Dept. of Informatics, Univ. of Oslo, Norway, mailto:jonhaug@ifi.uio.no
  http://www.ifi.uio.no/~jonhaug/, Phone: +47 22 85 24 92

Relevant Pages

  • Computer language and category theory
    ... I think this language can be described as a category as follows: ... is a unit morphism. ... each morphism in a category have excactly one source object and one ... I don't like such animals. ...
    (sci.math)
  • Re: early language
    ... or are they asking about language in general? ... those of other animals and correlated with certain lifestyles. ... cannot breathe whenever they want to, but they breathe deeper & faster when ... completely & close their mouth in order not to let water in. ...
    (sci.anthropology.paleo)
  • Re: "Its uncertain whether intelligence has any long term
    ... There is ample evidence that "intelligence" has had considerable ... > with other animals run up against a critical problem - we are capable ... > of things that other animals are not (language being the obvious ... Natural selection propels some species along a ...
    (sci.bio.evolution)
  • Re: early language
    ... or are they asking about language in general? ... those of other animals and correlated with certain lifestyles. ... cannot breathe whenever they want to, but they breathe deeper & faster when ... completely & close their mouth in order not to let water in. ...
    (sci.anthropology.paleo)
  • Re: Is the human mind/brain special wrt animal minds/brains?
    ... language, I find the author's dichotomy between humans and animals to be ... But the reorganization of the human brain has not ... quantity has a quality all its own, but that's not what he was claiming. ...
    (talk.origins)