Joy, Dig, Bury (and Dip): Correction
iepos@tunes.org
iepos@tunes.org
Sat, 25 Mar 2000 18:34:46 -0800 (PST)
In my last post, I claimed that "bury3" could be constructed as
dig3 dig2 dig1
but this is not correct. Oops. However, "bury3" _can_ be constructed as
dig3 dig3 dig3
Might as well give a proof this time...
The essential rule of "bury3" is that:
[f] [g] [h] [x] bury3 == [x] [f] [g] [h]
This is satisfied if we replace "bury3" with "dig3 dig3 dig3":
[f] [g] [h] [x] dig3 dig3 dig3
== [g] [h] [x] [f] dig3 dig3 (dig3)
== [h] [x] [f] [g] dig3 (dig3)
== [x] [f] [g] [h] (dig3)
After a bit of thought, I think I understand a little bit better
the relation between "dig" and "bury"...
It was mentioned before that "dig3", for instance, could be constructed as
[] cons cons cons dip
Ran with "x", "f", "g", and "h" on the stack, it would work like this:
[x] [f] [g] [h] [] cons cons cons dip
== [x] [f] [g] [[h]] cons cons dip (cons)
== [x] [f] [[g] [h]] cons dip (cons)
== [x] [[f] [g] [h]] dip (cons)
== [f] [g] [h] [x] (dip)
Now, what if we wanted to dig up two or three things instead of just one?
We can use essentially the same technique except that we use dip2 or dip3
instead of just dip... For instance,
[] cons cons cons dip2
is a program that digs up two things that are buried underneath
three things. It would work like this
[x] [y] [f] [g] [h] [] cons cons cons dip2
== [x] [y] [f] [g] [[h]] cons cons dip2 (cons)
== [x] [y] [f] [[g] [h]] cons dip2 (cons)
== [x] [y] [[f] [g] [h]] dip2 (cons)
== [f] [g] [h] [x] [y] (dip2)
Of course, this relies on the "dip-n" series of combinators; all
these can be constructed from "dip" and "cons"; in the Joy standard
library, I saw this:
dip2 == [dip] cons dip
dig3 == [dip2] cons dip
suggesting the series:
dip2 == [dip] cons dip
dip3 == [dip2] cons dip
dip4 == [dip3] cons dip
...
or in other words:
dip2 == [dip] cons dip
dip3 == [[dip] cons dip] cons dip
dip4 == [[[dip] cons dip] cons dip] cons dip
However, it is also possible to use this:
dip2 == [dip] cons dip
dip3 == [dip] cons dip2
dip4 == [dip] cons dip3
or in other words:
dip2 == [dip] cons dip
dip3 == [dip] cons [dip] cons dip
dip4 == [dip] cons [dip] cons [dip] cons dip
This might be preferred because it does not require nested quotations...
Anyway, I'm going way off on a tangent... back to "dig" and "bury".
Mainly, what I wanted to say is that digging up 2 things buried 3 deep
is the same as burying 3 things 2 deep. And the pattern could be
generalized but I won't explicitly state a generalized version because
it would require variables and you'd probably just skip over it;
an example is all one really needs, anyway :-)
Anyway, as a special case, burying 1 thing 3 deep is the same as
digging 3 things 1 deep, hence the construction of "dig3 dig3 dig3"
for burying one thing three deep. In light of the technique of using
a generalized "dip" for digging multiple things, a more proper
construction could be made:
bury3 == [] cons dip3
or substituting the constructed "dip3":
bury3 == [] cons [dip] cons [dip] cons dip
writting the lame way as "dig3 dig3 dig3", we'd have:
bury3 == [] cons cons cons dip [] cons cons cons dip [] cons cons cons dip
Anyway, this is making me dizzy. "cons", "dip", and "i" are fun;
they're really all you need as long as you don't mind not having
duplications; if you want duplications, then you could add
"dup" or "sip". Then, you really have all you need; unless,
of course you want destructions, in which case you could add
"pop"... but who would want destructions anyway... what is the
point of pushing something onto the stack if you're just going to
pop it off without using it... ?
Just kidding... of course you need "pop". In particular, for
"true" and "false" one would probably want to use "dip pop" and
"pop i". However, any program (err.. pure program, at least)
which uses "pop" but which has no external popping effect can be
rewritten without "pop", by instead using "cons", "dip", "i", and the
like. A similar thing could be said for programs that use "dup"
unnecessarily, making copies of things which don't really need to
be copied because they are just going to be popped off; abuses of
"dup" and "pop" often come in pairs... one good example is
your construction of "i" :-)
i == dup dip pop
This is a horrible abuse of "dup" and "pop" which would probably
result in much slowness if it was ever used. Anyway, "i" could
be constructed abusing just "pop" and at least not "dup" as:
i == [foo] swap dip pop
This would work for any "foo", for instance:
i == [dip] swap dip pop
or one could write it without "swap" as
i == [[dip]] dip dip pop
Well, that's enough for now...
- "iepos" (Brent Kerby)