# Symmetric Reductions

## Christopher Diggins — 2006-05-11 02:10:44

    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] = []

    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.

    Thanks,

    Christopher Diggins

    [Non-text portions of this message have been removed]

## William Tanksley, Jr — 2006-05-11 21:51:15

    Christopher Diggins <cdiggins@...> 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

    be very boring; you'd just write any program, and then write it in

    reverse with the inverse of each word in the forward version.

    Does anyone know if anybody's actually designed a reversible language?

    Does anyone know of such a language that might be suitable for a stack

    language? That might be fun...

     > Christopher Diggins

     -Billy

## stevan apter — 2006-05-11 22:35:11

    our own brent kerby and hilton campbell:  befreak.

    http://tunes.org/~iepos/befreak.html

    and a k implementation with GUI:

    http://www.nsl.com/papers/befreak.htm

    here is a primes-generator (g-d help us):

    http://www.nsl.com/k/befreak/primes.txt

    a reversible concatenative language would surely be

    something to marvel at.

     ----- Original Message -----

    From: "William Tanksley, Jr" <wtanksleyjr@...>

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, May 11, 2006 5:51 PM

    Subject: Re: [stack] Symmetric Reductions

    Christopher Diggins <cdiggins@...> 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

    be very boring; you'd just write any program, and then write it in

    reverse with the inverse of each word in the forward version.

    Does anyone know if anybody's actually designed a reversible language?

    Does anyone know of such a language that might be suitable for a stack

    language? That might be fun...

    > Christopher Diggins

    -Billy

    Yahoo! Groups Links

## Joe Bowbeer — 2006-05-12 01:57:12

    Sort of OT, but this reminds me of a peep-hole optimizer I once

    implemented for a sliding block puzzle solver: two adjacent moves that

    move the same piece into the hole can both be elided.  (Think of a

    queue where adding a new element erases the last element instead, but

    only if it's identical to the new element.)

    This in turn reminds me of a statement I read that related

    sliding-block puzzles to computers:

    http://www.maa.org/editorial/mathgames/mathgames_12_13_04.html

    Recently, Erik Demaine and Robert Hearn proved that sliding-block

    puzzles are PSPACE-complete. In their paper, you can see the

    AND-gates, OR-gates and other wiring necessary to build a

    sliding-block puzzle that emulates a computer. In fact, a puzzle made

    just with dominoes is PSPACE-complete. Since sliding-block puzzles are

    PSPACE-complete, "hardest" is meaningless. For any question a computer

    can answer with YES or NO, an equivalent sliding-block puzzle can be

    set up whose solvability depends on the answer.

    The Complexity of Sliding-Block Puzzles and Plank Puzzles

    http://swiss.csail.mit.edu/~bob/sliding-blocks.pdf

     On 5/10/06, Christopher Diggins <cdiggins@...> 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] = []

    >

    >

    > 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.

    >

    > Thanks,

    > Christopher Diggins

    >

## stevan apter — 2006-05-12 02:10:42

    this is EXTREMELY cool.

    thanks joe

     ----- Original Message -----

    From: "Joe Bowbeer" <joe.bowbeer@...>

    To: <concatenative@yahoogroups.com>

    Sent: Thursday, May 11, 2006 9:57 PM

    Subject: Re: [stack] Symmetric Reductions

    > Sort of OT, but this reminds me of a peep-hole optimizer I once

    > implemented for a sliding block puzzle solver: two adjacent moves that

    > move the same piece into the hole can both be elided.  (Think of a

    > queue where adding a new element erases the last element instead, but

    > only if it's identical to the new element.)

    >

    > This in turn reminds me of a statement I read that related

    > sliding-block puzzles to computers:

    >

    > http://www.maa.org/editorial/mathgames/mathgames_12_13_04.html

    >

    > Recently, Erik Demaine and Robert Hearn proved that sliding-block

    > puzzles are PSPACE-complete. In their paper, you can see the

    > AND-gates, OR-gates and other wiring necessary to build a

    > sliding-block puzzle that emulates a computer. In fact, a puzzle made

    > just with dominoes is PSPACE-complete. Since sliding-block puzzles are

    > PSPACE-complete, "hardest" is meaningless. For any question a computer

    > can answer with YES or NO, an equivalent sliding-block puzzle can be

    > set up whose solvability depends on the answer.

    >

    > The Complexity of Sliding-Block Puzzles and Plank Puzzles

    > http://swiss.csail.mit.edu/~bob/sliding-blocks.pdf

    >

    >

    > On 5/10/06, Christopher Diggins <cdiggins@...> 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] = []

    > >

    > >

    > > 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.

    > >

    > > Thanks,

    > > Christopher Diggins

    > >

    >

    >

    >

    >

    > Yahoo! Groups Links

    >

    >

    >

    >

    >

    >

    >

## John Carter — 2006-05-14 22:12:39

    On Wed, 10 May 2006, Christopher Diggins 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] = []

    >

    >

    > 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, it more mathematical based. Many operations have inverse

    operations.

    You can get them in any language that copes with mathematics to some

    degree.  In fact anything that works with any of a vast range of mathematical

    objects called groups.

    http://mathworld.wolfram.com/Group.html

    Blindingly Obvious? I wouldn't call it that, rather I would call it a

    Gateway and Invitation to a vast pool of amazingly deep and powerful

    theory...

    Jump in.

    http://members.tripod.com/~dogschool/groups.html

    John Carter                             Phone : (64)(3) 358 6639

    Tait Electronics                        Fax   : (64)(3) 359 4632

    PO Box 1645 Christchurch                Email : john.carter@...

    New Zealand

    Carter's Clarification of Murphy's Law.

    "Things only ever go right so that they may go more spectacularly wrong later."

    From this principle, all of life and physics may be deduced.