Brent L Kerby — 2002-03-29 10:07:39

> > [dig, bury, peek, poke]
>
> Joy already has some of these operators (well... sort of). dig2 is
> called rolldown and bury2 is called rollup. dig3 could be implemented
> as rolldownd swap and bury3 as swap rollup.
>
> [...]
>
> Ivan

Good point. And you're also right in pointing out that programs that use deep
stack manipulation tools like these usually can be written in a simpler way
(i.e., by cutting back on the total number of stack items, so that these
heavy-duty tools become unneccessary).

Nevertheless, I see great value in studying these very interesting series of
combinators. I've been thinking a bit about "reverse" the last while, and how to
construct it. The most obvious way to me initially seemed to use this (using the
4 case as an example):

reverse4 == dig1 dig2 dig3
== [] cons dip [] cons cons dip [] cons cons cons dip

which works like this:

[d] [c] [b] [a] dig1 dig2 dig3
== [d] [c] [a] [b] dig2 dig3
== [d] [a] [b] [c] dig3
== [a] [b] [c] [d]

However, this is kind of a poor construction, since if we express things in
terms of "cons" and "dip", the size of each "reverse" grows quadratically.

But, I was playing with my old brute-force searcher (yes, it has pretty
messed-up functionality, and i cannot modify because I wrote it about 2 years
ago and it has no comments :-) but it works well for this problem), and I found
this cool other way of constructing "reverse". But to do so, first it will be
handy to define a new combinator:

[b] [a] tack == [b[a]]

The idea is that "tack" tacks on "a" inside the program "b", leaving "b"
unchanged except that it will leave a constant "a" on top of the stack. You can
see "tack" as a kind of an analogue of "cons". Here are three possible ways of
constructing tack:

tack == unit cat
== [[i] dip] cons cons
== swap [dip] cons cons

This "tack" is quite a powerful little combinator; with it we could construct
"dip" and "unit":

dip == swap tack i
unit == [] swap tack

Anyways, I've run off on a tangent with "tack" (but finding something like
"tack" was precisely what I hoped would happen in searching for a construction
of "reverse"). So here's "reverse":

reverse4 == [] swap tack swap tack swap tack swap tack i
== unit swap tack swap tack dip

It works like this:

[d] [c] [b] [a] [] swap tack swap tack swap tack swap tack i
== [d] [c] [b] [] [a] tack swap tack swap tack swap tack i
== [d] [c] [b] [[a]] swap tack swap tack swap tack i
== [d] [c] [[a]] [b] tack swap tack swap tack i
== [d] [c] [[a] [b]] swap tack swap tack i
== [d] [[a] [b]] [c] tack swap tack i
== [d] [[a] [b] [c]] swap tack i
== [[a] [b] [c]] [d] tack i
== [[a] [b] [c] [d]] i
== [a] [b] [c] [d]

In retrospect, it would have been more handy to define "swap tack" as the new
primitive, rather than "tack". Let's then define

[b] [a] take == [a[b]]

The idea is that "a" takes in the "b". This is rather nicely constructed:

take == [dip] cons cons

This makes "take" look actually more fundamental than "tack" perhaps, even
though it has a reordering effect, whereas "tack" does not. And of course it
then admits the nice construction:

reverse4 == [] take take take take i
== unit take take dip

And of course this generalizes:

reverse5 == unit take take take dip
reverse6 == unit take take take take dip
etc.

Isn't that nifty?

By the way, {take, cat, i} is a base that gives linear completeness, like {cons,
dip, i} (currently I know of no base giving linear completeness with less than 3
combinators). It isn't too hard to show that {take, cat, i} is complete. All we
have to do is construct "cons" and "dip". "dip" is easy:

dip == take i

For "cons", we'll first want to construct "swap":

swap == [] take take i

And then:

cons == swap [] take swap cat
== [] take take i [] take [] take take i cat

Isn't that neat? Well, there's probably really a neater construction of "cons"
from this base ...

(all this stuff will have to be put into the forthcoming article)

- Brent

Nick Forde — 2002-03-29 13:23:32

Hi Brent,

Brent L Kerby writes:
...

> Nevertheless, I see great value in studying these very interesting series of
> combinators. I've been thinking a bit about "reverse" the last while, and how to
> construct it. The most obvious way to me initially seemed to use this (using the
> 4 case as an example):

...

> But, I was playing with my old brute-force searcher (yes, it has pretty
> messed-up functionality, and i cannot modify because I wrote it about 2 years
> ago and it has no comments :-) but it works well for this problem), and I found
> this cool other way of constructing "reverse".

...

How does your searcher work? Does it begin by assuming a base of
{cons, dip, i} and let you extend to include others like "tack"? Do
you intend to cover this in your article?

I think it would be interesting to see the results of applying some
simple linear optimisations by deconstructing and rebuilding
expressions of Joy atoms using such a base. Where the rebuilding is
being directed through perhaps random or prioritised alternatives.

If the selection priority of atoms is specified by execution time this
would be an easy means of applying some low level performance
optimisations. Of course, this assumes that there are significant
performance differences between the various linear combinators in Joy.

If nothing else this might give some metrics on the relative
importance/usefulness of particular combinators, beyond what
programmers find most convenient.

Nick.

Brent L Kerby — 2002-03-29 18:22:10

> How does your searcher work? Does it begin by assuming a base of
> {cons, dip, i} and let you extend to include others like "tack"?

My old searcher had 9 built-in possible bases (including "dup", "swap", "cons",
"dip", "i", ...); it used to be configurable by a small hard-wired change in the
code which of these were actually treated as bases, but I forget how this is
done :-)
Anyway, the searcher proceeds basically by trying each possible expression,
first of size 1, then size 2, etc., and running each expression with a stack of
appropriate size and then checking to see if the correct results happen (or if
an error happens midway, then it just skips along to the next expression to
try).

If you'd like, the old searcher is available at
tunes.org/~iepos/joysearch-0.3.tar.gz ... Anyway, the program takes two
parameters: the first is the "arity" of the goal combinator you are looking for
(i.e., how many stack items it requires), and the second is the goal combinator
itself. The goal combinator, and also the results, are written in this
one-letter code:

i == i
w == dup
k == zap (pop)
s == swap
c == cons
d == dip
p == sip
t == cat
u == unit

Joy's "[]"'s for quotation are used exactly the normal way. For example, when I
was searching for a possible other construction of "swap [swap] dip swap" (this
is reverse3), I did:

joysearch 3 s[s]ds

And you'll get an abundance of results, perhaps so many that you'll want to
ctrl-brk and read "log" (log is a history of exactly what the program prints to
the screen).

> Do you intend to cover this in your article?
>
> [other interesting ideas ...]
> Nick.

Well, I'm hoping to eventually finish the new searcher, and then yes, I would
want to mention it in the article ...

- Brent

Brent L Kerby — 2002-03-29 18:27:15