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.