Talk:Cabra

I wonder if Cabra's multiplication (parallel execution) is really associative.

Counterexample: Let a, b and c three Cabra programs, such that a is shorter to execute than b if n is set and b is shorter to execute than a if n is not set. Assume further that, in any case c is longer than both a and b and that b sets n. Now run the program on an input not containing n. Then a+b executes as a and (a+b)+c is the same as a. On the other hand b+c execute like b, which sets n, so that a+(b+c) is the same as a.

In mathematical terms, by identifying two Cabra programs which gives the same output, you assimilate Cabra programs with transformations on P(N), the set of set of integers. The product of programs is the composition (perform one transformation, then the other). It is well known to be associative but not commutative. Burro follows the same idea and restricts the potential transformations to be invertible, leading to a group.

I do not know of any composition law that would qualify for a suitable addition. I neither do know of a proof showing that there is none.

AlainD 12:13, 9 April 2009 (UTC)

I'm pretty confused, on two points: (1) multiplication in Cabra is sequential execution, not parallel, and (2) showing that (a+b)+c is the same as a, while a+(b+c) is the same as a, is not a counterexample to the claim that + is associative.

Your second paragraph is a little less confusing, but multiplication is not claimed to be commutative in either Cabra or Burro, so it still is kind of confusing. Chris Pressey (talk) 15:18, 7 December 2012 (UTC)

Since I really don't like Cabra's "race" for parallel composition (because one branch is more complicated, you simply discard its result?), I've tried to think about other ways parallel composition could be done. The obvious approach is to make both calculations, then apply an operation to the result (and hopefully that operation is not just f(x, y) = x).

• Well the easiest way to keep two results is to... keep two results. In a pair. So we'd have a language working on pairs. I'm guessing the data would be a tree

Tree ::= "Nil" | "(" Tree ", " Tree ")".

So a program p maps a tree t to a tree p(t); sequential composition a.b of two programs maps t to b(a(t)); parallel composition a|b maps t to (a(t), b(t)). This is trivially left-distributed:

a.(b|c) (t) = (b(a(t)), c(a(t))) = (a.b|a.c) (t)

Right-distributivity, on the other hand, is more problematic: it would basically mean that applying a program p to a pair would be exactly the same as applying p to each member of the pair; so programs would only be able to apply an operation to leaves (any program p would be unambiguously described by p(Nil)). This sounds boring, so I guess we'd have to do without right-distributivity.

• Other interesting operations can be boolean operations like nor, nand, etc. I was thinking maybe we could have programs be operation over queues of bits, and parallel composition would be something like (a||b) (q) = a(q) BITWISE-NOR b(q) or whatever other operation. I'm not sure, though, what "bitwise" would mean for two queues of different size - if they were stack I'd have no problem with considering the empty stack equivalent to "a stack filled with an infinity of zeros" but for queues it doesn't work that easily.

With that said, "parallel composition" needs not necessarily be the other operation on programs. What about, for instance, conditionals? If the data structure you're manipulating is some sort of queue or stack, you can define:

(a?b) (q) = { a(q) if head(q) = 1
            { b(q) if head(q) = 0

--Koen (talk) 23:09, 6 December 2012 (UTC)

The tl;dr reason for "why Cabra is hard/ugly" is that if one program halts and the other doesn't, it's kind of awkward to relate them with any operation. "Parallel race" just has the advantage that you can determine it as soon as either of the programs halts. "Parallel" in general just has the advantage that it's an easy way to get commutivity (the ? operator you propose isn't commutative unless you do something fancy about which side is checked against 1 and which against 0... that I can't immediately see a nice solution to.)

I haven't had any further ideas in this area since I left it, except that you could probably turn for-programs (representing p.r. functions) into a full-on ring, with multiplication as concatenation/composition, and addition being pairwise addition of variables in the result states. But that's probably nowhere near interesting. Chris Pressey (talk) 15:38, 7 December 2012 (UTC)

Actually, I don't see a way to get proper distributivity, even out of that. In a⋅(b+c) you "run" a once. In (a⋅b)+(a⋅c) you "run" a twice. That nudges you towards using idempotent operations, which nudges you towards a idempotent algebra like a dioid (to put it in very fluffy terms.) Chris Pressey (talk) 13:26, 10 December 2012 (UTC)

You don't actually need to run a twice, since it's performed before b or c: if you want to compute b(a(x)) + c(a(x)) you can do something like:

let A = (compute a(x)) in b(A) + c(A)

Whether or not to compute a twice is a choice; I'm not sure what would idempotent mean in that situation, but whether let A = a(x) in b(A) + c(A) is equivalent to b(a(x)) + c(a(x)) or not depends entirely on whether a(x) has 'side effects' when evaluated; for instance if a is the function x -> x + 1 then it's equivalent but if a is the function x -> print x; x + 1 then it's not. Now for right-distributivity that'd be different, since the a in a(b(x)) and the a in a(c(x)) are not (necessarily) applied to the same argument. I guess that depends how you define your operations; in the 'pairs' example I gave, for instance, a would be defined by what it does to the first and second elements of the pair, taken individually, so there would be no real distinction between "running it twice" and "running it once". Though that wouldn't be very interesting. --Koen (talk) 02:41, 11 December 2012 (UTC)

Well, OK. You don't need to run a twice. But running (a⋅b)+(a⋅c) needs to have the same effect as running a⋅(b+c). Maybe "say" would be a better verb than "run"; you need to be able to say a twice -- or just once, in a different context -- and have it mean the same thing in both contexts. In a lot of languages, saying something in a program means running it, and most of my thoughts in this area have been with machine-y models of computation where this is the case. But, yes, let (without side effects) is an extremely good example where left-distributivity works. Not sure offhand how you'd go about generalizing it to get right-distributivity too; could be interesting to try. I should also say that pairs are probably quite handy too, they've come up in some related thoughts I've had but it's all very vague to me right now as I haven't really been able to focus on it. Chris Pressey (talk) 18:36, 11 December 2012 (UTC)

Well pairs I mentioned in the example above: So a program p maps a tree t to a tree p(t); sequential composition a.b of two programs maps t to b(a(t)); parallel composition a|b maps t to (a(t), b(t)). This is trivially left-distributed:

a.(b|c) (t) = (b(a(t)), c(a(t))) = (a.b|a.c) (t)

As for right-distributivity it would be embarrassing:

a(b(t), c(t)) = (b|c).a (t) = (b.a|c.a)(t) = (a(b(t)), a(c(t)))

So basically for any (?) pair (x, y) and program a, you must have a(x, y) = (a(x), a(y)) which I believe would make all programs a very boring - they would be entirely defined by what they do to leaves, which sounds very very boring and means you can't actually manipulate trees themselves. Well I'm assuming for any pair (x, y) there is a tree t and two programs b and c such that (x, y) = (b(t), c(t)), but that looks like a very reasonable assumption, because otherwise it would mean x and y cannot be 'built' in the first place. --Koen (talk) 23:43, 11 December 2012 (UTC)

"Very boring" may just be the best we can do here, unfortunately. I read something somewhere recently (that I cannot find again, naturally) where someone described the relationship between algebra and computation as awkward because algebra is really about equational theories, while computation is not limited to equation. (Or something along those lines.) To put it in some very fluffy way, when you base languages on algebras, every axiom you add to an algebra makes the language more "boring" (or maybe "tame" would be a better word) because more and more things in the language are restricted to "playing nicely" with other things. (e.g. invertibility -> reversibility -> bijections -> a rather meagre subset of what an unrestricted Turing machine can do.) Of course, that doesn't mean it's not worth doing, and indeed it provides a nice constraint to try to work around. But it's clear that monoids are easy, groups are possible, and anything with more structure than a group gets very difficult; this makes me wonder if the smaller but stranger structures (like loops) are worthwhile targets. (Looking at loops, I have no immediate ideas.) Chris Pressey (talk) 13:33, 12 December 2012 (UTC)