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: "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: 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)
  • Re: Is the human mind/brain special wrt animal minds/brains?
    ... language, I find the author's dichotomy between humans and animals to be ... Human brains make a lot more thrombospondin, ... and common ancestors into account - maybe today all of those other ...
    (talk.origins)
  • 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)