# Code Transformation Problem (possibly monadic?)

## 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