Talk:Burro

I think it might not be a group because the anti-program of a condition isn't a program itself, because a anti-condition by it-self doesn't mean anything. But Revaver2pi is a group (if you don't use I/O commands), and in Revaver2pi each command is the reverse of itself. In Revaver2pi each program has an anti-program that is made by reversing the order of all the lines in the program, and you can put it at the beginning or end of any program to make it a no operation program. Revaver2pi was invented even before Burro was, but I didn't think of a group until now. --Zzo38 21:53, 4 December 2007 (UTC)

Ignore the message about it not being a group, because that has now been corrected. --Zzo38 22:04, 20 February 2011 (UTC)

I didn't actually see this until now, but now I know you are among the people who noticed this (along with ais523 and Quintopia.) It was from ais523 that I got the first direct "bug report" about this. Chris Pressey (talk) 18:56, 30 November 2012 (UTC)

Concatenative explication

I won't claim Burro is a concatenative language, but it's clear that you can use ideas from concatenative languages to explain it -- maybe clearer, or maybe it loses something, I don't know, but let's try it.

• The set of Burro program texts is the subset of strings over the alphabet of symbols used in Burro programs which conform to Burro's syntax.
• Burro program texts form a monoid under concatenation.
  • (But note that this monoid is not finitely generated! There's no way to assemble (+/-) from smaller parts using only concatenation. Chris Pressey (talk) 16:41, 1 December 2012 (UTC))
    • Hm, from similar discussions about Underload I recall that its monoid is finitely generated, because you can use a and * commands to build any program from single-character elements. Although I also recall having trouble seeing how to make something like that work in a reversible language. --Ørjan (talk) 21:19, 1 December 2012 (UTC)
      • I'm not sure what I meant by "finitely generated" there, I think I was confused in using that term. The monoid is indeed finitely generated, it just has a lot of elements which are syntactically invalid programs like (+ and /. You could wallpaper over this by saying those are actually valid Burro programs and they all represent e.g. the identity function, but it remains that you can concatenate two syntactically invalid programs and obtain a syntactically valid program, and that messes up the homomorphism, doesn't it? I think I meant something like that. --Chris Pressey (talk) 09:19, 11 June 2020 (UTC)
        • Underload's monoid is finitely generated, but as far as I know, Burro's isn't. On the other hand, Underload doesn't form a group because programs like ! and (:^):^ have no inverse. --ais523 00:44, 12 June 2020 (UTC)
          • The set of Burro program texts, if looked at as a monoid, is finitely generated, because there are only a finite number of characters, and from these characters you can construct any desired program text. The set of syntactically valid Burro program texts though, if looked at as a monoid, is not finitely generated, because you can find any number of elements (program texts) where it's not possible to construct that element from other elements using only concatenation. I think that's the distinction that was missing. --Chris Pressey (talk) 08:18, 15 June 2020 (UTC)
• There is a monoid homomorphism from this monoid to a monoid of functions under composition (the primitive functions that the primitive Burro operations and structures represent.)
• This monoid of functions under composition is in fact a group, as every function in it has an inverse.
• The monoid of program texts has the following property w.r.t. this homomorphism: for every program text a, there exists a program text b such that if the interpretation of a is the function f, the interpretation of b is its inverse, the function f^-1; thus the interpretation of ab is the identity function. We call b the annihilator of a.
• As long as f isn't the identity function, f^-1 is unique. Given a, its annihilator b is not a unique program text. But all possible annihilators of a are in an equivalence class, and their interpretations are all f^-1.
• A canonical annihilator b can also be derived for any a. (The reference implementation includes a Haskell function which does this.) Chris Pressey (talk) 19:13, 30 November 2012 (UTC)

There's more:

• The homomorphism induces an equivalence class on the program texts; all program texts which map to the same function are in the same class. This is the equivalence class that the original explanation means when it says "over computational equivalence".
• There's a catch. The interpretation of a program text is a function, but actually executing this function is not just a matter of applying it. Instead, it is applied repeatedly, until the halt flag is false. But we can still shoehorn this into the concatenative paradigm, sort of: this is an iterated map, which is just a potentially infinite composition of a function with itself.
• Is it possible to assign every function in the group a canonical program text? Maybe we can pick the lexicographically first one. In general this would not be possible, but (because the "real work" is done by the iterated map) all of the functions that program texts map to are total functions, and not even particularly complex ones. So it might be possible. Chris Pressey (talk) 21:30, 30 November 2012 (UTC)