Christopher Diggins — 2007-12-08 21:32:32

I have the following problem, and I would be most grateful for any help:

Given the following sequence of instruction:

a b m [c m d e] f g

I want an automated transform (no matter how inefficient, it just has
to be algorithmic) to rewrite the code so that each instruction
applies to the stack below the top value, except for "m".

The naive transformation would be:

[a b m [c m d e] f g] dip

However, we have a problem because the "m" instruction can't see the
top of the stack.

The next obvious transformation (which doesn't work) would then be:

[a] dip [b] dip m [[[c] dip m [d] dip [e] dip]] dip [f] dip [g] dip

However, consider if "f" is really "apply".

[a] dip [b] dip m [[[c] dip m [d] dip [e] dip]] dip [apply] dip [g] dip

You can see this won't work for the nested quotation. Informally there
is an undesirable nesting of "dip"s.

There is a very close correspondance between this problem and monads
(http://homepages.inf.ed.ac.uk/wadler/topics/monads.html).
This leads me to suspect that the solution has the form:

[a] unit [b] unit bind [m] bind [[c] unit [m] bind [d] unit bind [e]
unit bind] bind [apply] unit bind [g] unit bind

For some value of unit (a monadic transform), and bind (a monadic
composition operator).

I would be most grateful for a solution.

Thanks in advance,
Christopher

William Tanksley, Jr — 2007-12-10 19:22:27

Christopher Diggins <cdiggins@...> wrote:

> Given the following sequence of instruction:
> a b m [c m d e] f g
> I want an automated transform (no matter how inefficient, it just has
> to be algorithmic) to rewrite the code so that each instruction
> applies to the stack below the top value, except for "m".

> The naive transformation would be:
> [a b m [c m d e] f g] dip
> However, we have a problem because the "m" instruction can't see the
> top of the stack.

Okay, I see what you want, kinda.

> The next obvious transformation (which doesn't work) would then be:
> [a] dip [b] dip m [[[c] dip m [d] dip [e] dip]] dip [f] dip [g] dip

The problem here -- or one of the problems here -- is that you're
diving into the quotation as though it were transparent. It's not;
it's a unit. So the "next obvious transformation" should actually be:

[a] dip [b] dip m [[c m d e]] dip [f] dip [g] dip

At this point, though, I have to stop and wonder what your problem
really means. When you say "each function applies to the stack below
the top value", do you mean what I just wrote, or do you mean that the
ENTIRE SEQUENCE ignores the value which was on the top just prior to
execution of the sequence, except for 'm', which for some reason sees
the value but doesn't destroy it (so that the next 'm' can also see
it)? That's a very complex semantics. Why do it?

However, here's a transform which appears to meet your request.

[a] dip [b] dip dup [m] dip [[c m d e]] dip [f] dip [g] dip

Note that each occurence of m is replaced by 'dup [m] dip', while all
the other words 'x' are replaced by '[x] dip'.

I still don't see why to do this, so I don't know if I'm violating
something by failing to break into the nested quotation.

> Christopher

-Wm

Christopher Diggins — 2007-12-10 23:18:31

On Dec 10, 2007 2:22 PM, William Tanksley, Jr <wtanksleyjr@...> wrote:

> Christopher Diggins <cdiggins@...> wrote:
> > Given the following sequence of instruction:
> > a b m [c m d e] f g
> > I want an automated transform (no matter how inefficient, it just has
> > to be algorithmic) to rewrite the code so that each instruction
> > applies to the stack below the top value, except for "m".
>
> > The naive transformation would be:
> > [a b m [c m d e] f g] dip
> > However, we have a problem because the "m" instruction can't see the
> > top of the stack.
>
> Okay, I see what you want, kinda.
>
>
> > The next obvious transformation (which doesn't work) would then be:
> > [a] dip [b] dip m [[[c] dip m [d] dip [e] dip]] dip [f] dip [g] dip
>
> The problem here -- or one of the problems here -- is that you're
> diving into the quotation as though it were transparent. It's not;

I'm allowed though because it is a source code transformation that I want.

> it's a unit. So the "next obvious transformation" should actually be:
>
> [a] dip [b] dip m [[c m d e]] dip [f] dip [g] dip

This is not what I want.

> At this point, though, I have to stop and wonder what your problem
> really means. When you say "each function applies to the stack below
> the top value", do you mean what I just wrote, or do you mean that the
> ENTIRE SEQUENCE ignores the value which was on the top just prior to
> execution of the sequence, except for 'm', which for some reason sees
> the value but doesn't destroy it (so that the next 'm' can also see
> it)? That's a very complex semantics. Why do it?

Rewrite code to pass values without changing the order of operations.

> However, here's a transform which appears to meet your request.
>
> [a] dip [b] dip dup [m] dip [[c m d e]] dip [f] dip [g] dip

"c", "d", and "e" would take the top of the stack as an unintentional argument.

> Note that each occurence of m is replaced by 'dup [m] dip', while all
> the other words 'x' are replaced by '[x] dip'.
>
> I still don't see why to do this, so I don't know if I'm violating
> something by failing to break into the nested quotation.

Yeah, unfortunately. Thanks for giving it a shot though.

> > Christopher
>
> -Wm

- Christopher

William Tanksley, Jr — 2007-12-11 01:14:58

Christopher Diggins <cdiggins@...> wrote:

> William Tanksley, Jr <wtanksleyjr@...> wrote:
> > Christopher Diggins <cdiggins@...> wrote:
> > At this point, though, I have to stop and wonder what your problem
> > really means. When you say "each function applies to the stack below
> > the top value", do you mean what I just wrote, or do you mean that the
> > ENTIRE SEQUENCE ignores the value which was on the top just prior to
> > execution of the sequence, except for 'm', which for some reason sees
> > the value but doesn't destroy it (so that the next 'm' can also see
> > it)? That's a very complex semantics. Why do it?

> Rewrite code to pass values without changing the order of operations.

Oh. I don't really get it... I understand the concept of partial
application, but I don't know how you're trying to model that here. I
certainly don't see any unambiguous semantic model behind what you're
asking for, so my guess is likely going to miss the mark.

But let's see if we can figure it out anyhow.

> > However, here's a transform which appears to meet your request.
> > [a] dip [b] dip dup [m] dip [[c m d e]] dip [f] dip [g] dip

> "c", "d", and "e" would take the top of the stack as an unintentional argument.

The top of stack wouldn't be available to the function [c m d e] --
'dip' hides it.

However, I think I might be able to guess another possible semantics
you might want. You want all 'm's contained in the source to somehow
receive the one treatment, and all the other functions to receive
another treatment. The problem is that Joy's quotations make things
complex by nesting semantics. The obvious 'simple' solution is to
start by flattening your function (using the transform we talked about
earlier, while the group was discussing flatness); then replace each
function or quoted function with its new semantics. I've still got to
figure out what the correct semantics are for this transform; I
haven't figured that out.

(I also need to remember or look up HOW to flatten arbitrary Joy; we
had an algorithm for this explained to us, I believe by iepos, but I
can't seem to find it. The goal is simple enough: I want to reduce
arbitrarily nested Joy to a linear list of symbols and quoted symbols.
Doing this will allow me to figure out only four semantics: one for
'm', one for '[m]', one for 'X', and one for '[X]', where 'X' stands
for any symbol other than 'm'.)

Hmm... Let me ask you a set of questions.

What's the correct transform for an expression consisting ONLY of a
single one of the following pairs: 'm x', 'x m', '[m] x', '[x] m', 'm
[x]', 'x [m]', '[m] [x]', '[x] [m]'? Pick a few that you think are
representative, don't bother answering them all unless you want.

For example, I think the transform of 'm x' would be 'dup [m] dip [x] dip'.

While you're answering that, I'll try to derive the algorithm for
flattening a quotation.. I have a long train commute ahead of me.

> - Christopher

-Wm

Manfred Von Thun — 2007-12-11 08:37:21

On 9/12/07 8:32 AM, "Christopher Diggins" <cdiggins@...> wrote:

> I have the following problem, and I would be most grateful for any help:
> Given the following sequence of instruction:

> a b m [c m d e] f g
>
> I want an automated transform (no matter how inefficient, it just has to be
> algorithmic) to rewrite the code so that each instruction applies to the
> stack below the top value, except for "m".
>
> [..]
>

I don¹t know whether this will help with the second m inside the square
brackets.
Are we to assume that f is a combinator which executes the preceding
quotation?
Also, I¹m not offering an algorithm either.

So I¹ll change the problem to

> a b m [1 2 3] f g

I once toyed with the idea of some Joy operators which work hand in hand
with the dip combinator. Dip has to maintain a list (the dip stack) of
temporarily
hidden items that had to be removed from the Joy stack for the duration
of executing the quotation that was given to the dip combinator. When that
execution has finished, the previously dipped value has to be restored from
the dip stack to the Joy stack. During the execution of the quotation the
value that has been temporarily removed from the stack cannot be accessed.

But why not allow at least read access? Invent a new operator peek, which
can only be used inside a quotation. Its effect is to push a copy of the
dipped
value on top of the Joy stack. Example:

> 5 [10 peek /] dip ==> 5 2
>

Your example, as amended by me, then becomes:

>
> [a b peek m [1 2 3] f g] dip
>

This peek operator would not work if one wanted to access the dipped value
from an enclosing dip. (Maybe that is what your example is driving at). So
a more versatile version of peek would push not just the most recently
dipped value, but a list of all currently dipped values. Then the desired
value
might be the second, third, .. item on this list.

Maybe even a poke operator would be useful: it could pop a value off the
Joy stack and use that as a replacement for the top value of the dip stack.
I don¹t know how nested dips could be handled cleanly without thereby
introducing a rather treacherous programming device resulting in hard
to understand code.

I did not pursue these ideas because dip uses a particular internal register
(dump1, from memory), but some other operators also use it. This was just
bad planning, and I could have introduced a new dump just to handle dip.

At any rate, some versions of peek and poke might find their way into
some concatenative language that uses the dip combinator.

> - Manfred

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

William Tanksley, Jr — 2007-12-11 15:30:28

William Tanksley, Jr <wtanksleyjr@...> wrote:

> However, I think I might be able to guess another possible semantics
> you might want. You want all 'm's contained in the source to somehow
> receive the one treatment, and all the other functions to receive
> another treatment. The problem is that Joy's quotations make things
> complex by nesting semantics. The obvious 'simple' solution is to
> start by flattening your function (using the transform we talked about
> earlier, while the group was discussing flatness); then replace each
> function or quoted function with its new semantics. I've still got to
> figure out what the correct semantics are for this transform; I
> haven't figured that out.

I think I have an answer.

Let T be your transform. T(m) = dup [m] dip; T([m]) = dup [m] cons;
T(x) = [x] dip; T([x]) = [x] swap. Finally, the top-of-stack must be
dropped at the end of the transformed sequence.

But first we have to flatten the sequence, so that m appears only
naked or at the beginning of a single quotation. I'm going to describe
an algorithm for completely flattening a quotation, but when done by
hand less flattening will improve final results with less need for
cleanup.

To flatten a quotation:
for each element in the quotation,
if the element is a list,
recursively flatten that element.
break-apart the flattened result.

To break-apart a list:
if the list has one element,
if the element is an atom, return the list containing only that atom.
else return that element followed by the atom 'quote'.
else if the list has two elements,
break-apart the first element.
break-apart the second element.
return the two broken results followed by the atom 'concat'.

I admit I'm not certain of how I've written this, but it should
present the essentials.

EXAMPLE:

[a b m [c m d e] f g] flatten ==
[a b m [c] [m] concat [d] [e] concat concat f g].

Now to perform the transform.

T(a b m [c m d e] f g) ==
T([a b m [c m d e] f g] i) ==
T([a b m [c m d e] f g] flatten i) ==
T([a b m [c] [m] concat [d] [e] concat concat f g] i) ==
T(a b m [c] [m] concat [d] [e] concat concat f g) ==

Now I apply the transform, by simple substitution:

[a] dip [b] dip dup [m] dip [c] swap dup [m] cons [concat] dip [d]
swap [e] swap [concat] dip [concat] dip [f] dip [g] dip drop ==

Now I start to clean up, starting by getting rid of the drop at the
end by making the last [m] consume the input parameter ("dup [m] cons"
becomes "[m] cons", and all the words after it lose the need to
preserve the top element, so dip becomes i and swap/drop disappears):

[a] dip [b] dip dup [m] dip [c] swap [m] cons [concat] i [d] [e]
[concat] i [concat] i [f] i [g] i ==

Now simplify [x] i == x:

[a] dip [b] dip dup [m] dip [c] swap [m] cons concat [d] [e] concat concat f g.

Further automatic simplification is possible, but should be fairly
obvious. The point we're at here would be easy to reach with a smarter
algorithm that preparsed the quotation and flattened only where there
was an m. (Well, actually, the result would be even simpler if we were
to do that.. You know, I'm going to show the result.)

Copied from above:
[a] dip [b] dip dup [m] dip [c] swap [m] cons concat [d] [e] concat
concat f g ==

Folding constants:
[a b] dip dup [m] dip [c] swap [m] cons concat [d e] concat f g ==

...and there we go.

Okay, how'd that work? Did it do what you wanted?

-Wm

Christopher Diggins — 2007-12-11 15:53:58

On Dec 11, 2007 3:37 AM, Manfred Von Thun <m.vonthun@...> wrote:

> On 9/12/07 8:32 AM, "Christopher Diggins" <cdiggins@...> wrote:
>
> > I have the following problem, and I would be most grateful for any help:
> > Given the following sequence of instruction:
>
> > a b m [c m d e] f g
> >
> > I want an automated transform (no matter how inefficient, it just has to
> be
> > algorithmic) to rewrite the code so that each instruction applies to the
> > stack below the top value, except for "m".
> >
> > [..]
> >
> I don¹t know whether this will help with the second m inside the square
> brackets.
> Are we to assume that f is a combinator which executes the preceding
> quotation?

No, unfortunately we can't assume that. Otherwise I would have to
compile each word, to find out exactly what it does.

> Also, I¹m not offering an algorithm either.

:-(

> So I¹ll change the problem to
> > a b m [1 2 3] f g
>
> I once toyed with the idea of some Joy operators which work hand in hand
> with the dip combinator. Dip has to maintain a list (the dip stack) of
> temporarily
> hidden items that had to be removed from the Joy stack for the duration
> of executing the quotation that was given to the dip combinator.
>
> When that
> execution has finished, the previously dipped value has to be restored from
> the dip stack to the Joy stack. During the execution of the quotation the
> value that has been temporarily removed from the stack cannot be accessed.
>
> But why not allow at least read access? Invent a new operator peek, which
> can only be used inside a quotation. Its effect is to push a copy of the
> dipped
> value on top of the Joy stack. Example:
>
> > 5 [10 peek /] dip ==> 5 2
> >
> Your example, as amended by me, then becomes:
> >
> > [a b peek m [1 2 3] f g] dip
> >

That is an interesting approach.

> This peek operator would not work if one wanted to access the dipped value
> from an enclosing dip. (Maybe that is what your example is driving at). So
> a more versatile version of peek would push not just the most recently
> dipped value, but a list of all currently dipped values. Then the desired
> value
> might be the second, third, .. item on this list.

I am hoping for that the operators can be oblivious of their nesting.
I think there could be problems though with dynamic construction of quotation:

[a b peek m ...] quote dip.

> Maybe even a poke operator would be useful: it could pop a value off the
> Joy stack and use that as a replacement for the top value of the dip stack.
> I don¹t know how nested dips could be handled cleanly without thereby
> introducing a rather treacherous programming device resulting in hard
> to understand code.

Any transformation that I am looking at is only for compilers. Hard to
understand code is completely acceptable.

> I did not pursue these ideas because dip uses a particular internal register
> (dump1, from memory), but some other operators also use it. This was just
> bad planning, and I could have introduced a new dump just to handle dip.

Did you consider the primitive construction:

dip == swap cons i

> At any rate, some versions of peek and poke might find their way into
> some concatenative language that uses the dip combinator.
>
> > - Manfred

- Christopher

Christopher Diggins — 2007-12-12 00:12:33

On Dec 11, 2007 10:30 AM, William Tanksley, Jr <wtanksleyjr@...> wrote:

> William Tanksley, Jr <wtanksleyjr@...> wrote:
> > However, I think I might be able to guess another possible semantics
> > you might want. You want all 'm's contained in the source to somehow
> > receive the one treatment, and all the other functions to receive
> > another treatment. The problem is that Joy's quotations make things
> > complex by nesting semantics. The obvious 'simple' solution is to
> > start by flattening your function (using the transform we talked about
> > earlier, while the group was discussing flatness); then replace each
> > function or quoted function with its new semantics. I've still got to
> > figure out what the correct semantics are for this transform; I
> > haven't figured that out.
>
> I think I have an answer.
>
> Let T be your transform. T(m) = dup [m] dip; T([m]) = dup [m] cons;
> T(x) = [x] dip; T([x]) = [x] swap. Finally, the top-of-stack must be
> dropped at the end of the transformed sequence.

I really appreciate your help here. I have not yet convinced myself
that this generalizes to dynamically constructed quotations but it
looks really really close. I will try to come up with a set of
examples and tests. The insight of flattening is particularly helpful.

- Christopher

William Tanksley, Jr — 2007-12-12 01:15:54

Christopher Diggins <cdiggins@...> wrote:

> William Tanksley, Jr <wtanksleyjr@...> wrote:
> > I think I have an answer.

> > Let T be your transform. T(m) = dup [m] dip; T([m]) = dup [m] cons;
> > T(x) = [x] dip; T([x]) = [x] swap. Finally, the top-of-stack must be
> > dropped at the end of the transformed sequence.

> I really appreciate your help here. I have not yet convinced myself
> that this generalizes to dynamically constructed quotations but it
> looks really really close. I will try to come up with a set of
> examples and tests.

The tough part should be the flattening algorithm, of course. I didn't
test it at all, I merely typed it in after some thought and a few
minutes, so I may have missed some special case. I certainly didn't
make it easy to implement.

I also can't tell you whether T has the semantics you want :-). But it
should have the effect of passing a single constant value to every
appearance of m in the quotation, no matter how deeply nested.

Oh. I just thought of something -- my flattening algorithm doesn't
handle [], so that'll have to be added. Simple, perhaps trivial.
Having noticed that, I'll note the obvious: T([]) = [] swap.

What an interesting transform.

> The insight of flattening is particularly helpful.

You flatter me.

...but this may be the first time flattening has been helpful. I hope
you intend to use it for good and not evil.

> - Christopher

-Wm

Code Transformation Problem (possibly monadic?)

Christopher Diggins — 2007-12-08 21:32:32

William Tanksley, Jr — 2007-12-10 19:22:27

Christopher Diggins — 2007-12-10 23:18:31

William Tanksley, Jr — 2007-12-11 01:14:58

Manfred Von Thun — 2007-12-11 08:37:21

William Tanksley, Jr — 2007-12-11 15:30:28

Christopher Diggins — 2007-12-11 15:53:58

Christopher Diggins — 2007-12-12 00:12:33

William Tanksley, Jr — 2007-12-12 01:15:54