Re: [stack] Code Transformation Problem (possibly monadic?)

William Tanksley, Jr <[email protected]> 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