### Re: [stack] Symmetric Reductions

William Tanksley, Jr <wtanksleyjr <at> gmail.com>

2006-05-11 21:51:15 GMT

Christopher Diggins <cdiggins <at> gmail.com> wrote:
> I notice in stack based languages certain symmetric programs reduce to
> no-ops:
> f1 = [swap swap] = []
> f2 = [dup pop] = []
> f3 = [cons uncons] = []
> f4 = [dup swap cons uncons swap pop] = [dup swap swap pop] = [dup pop] = []
Well, by definition if a word has a "symmetric" counterpart -- a
mirror-image reversal -- then following the word with its mirror image
would be a no-op. The interesting thing is that these are mostly not
perfectly symmetric -- "swap swap" is, of course, but "dup pop" acts
completely different in a mirror world. In mathematical jargon, "swap
swap" is reversible, while "dup pop" isn't.
So there's two interesting sets of symmetric no-ops -- reversible and
non-reversible. Oh, and then of the reversible ones, there's the set
of nihilistic palindromes: phrases which do nothing and read the same
forward and backward. "swap swap" is obviously one of these.
> So how much of this is blindingly obvious to the research community? It
> seems that this must be much harder to detect in non-stack based languages.
Well, yes. The part that makes it easy to detect is actually the
compositional nature of the language rather than just the
stack-basedness . Manfred wrote a bit about identities like these
in some of his work on the mathematical basis of Joy -- IMO
interesting reading.
Of course, in a completely reversible language such explorations would

(Continue reading)