🚀 go-pugleaf

In article <1992Oct26.141803.22591@cs.tulane.edu> fs@cs.tulane.edu (Frank Silbermann) writes:
>By the way, I didn't carefully read the details of your
>imperative-to-functional transformatioon, but what is
>the simple way to transform a procedure call with six arguments,
>where each subexpression has side-effects affecting evaluation
>of the other arguments?

Like this C-like code?

         A = P(*A++ = 0, *A++ = 1, *--A = 2, *A++ = 3, *--A = 4, *--A = 5);

You need to first impose a set of transformation rules for side-effects.  Then
transform away all the side-effects.

In general, every implementation of the language (every compiler) will have
its own set of transformation rules for eliminating side-effects.  It won't
be uniform across the board because the Standard will usually carry the phrase
"implementation dependent".  What this is really saying is that an entire
family of languages are being defined by the Standard each which differs in
its "implementation dependent" features from the others.

But each language in the family, having its own set of transformation rules,
will not have any indeterminacy associated with multiple side effects.  This
is preferrable to treating translations as partial mappings that are undefined
over implementation-dependent features.

(10) Side-effect elimination
So this is actually a preprocessing phase.  The resulting mapping would look
something like this:

        Imperative Lamguage
                |
                | 
                |  Side-effect elimination
                |
                v
     Side-effect free language --------------------->  Functional language
         Concrete syntax                                 Abstract syntax

If the compiler evaluated them left to right you could state a transformation
rule to the effect:

         A = P(*A++ = 0, *A++ = 1, *--A = 2, *A++ = 3, *--A = 4, *--A = 5);
-->
         x0 = (*A++ = 0); x1 = (*A++ = 1); x2 = (*--A = 2);
         x3 = (*A++ = 3); x4 = (*--A = 4); x5 = (*--A = 5);
         A = P(x0, x1, x2, x3, x4, x5);

where x0, ..., x5 are "fresh" variables.  Assume for this example that P is
purely functional: i.e. that it affects no global variables and it returns
only A.

A corresponding set of transformation rules for ++ and -- would result in:

          x0 = (*A++ = 0); x1 = (*A++ = 1); x2 = (*--A = 2);
          x3 = (*A++ = 3); x4 = (*--A = 4); x5 = (*--A = 5);
          A = P(x0, x1, x2, x3, x4, x5);
-->
         x0 = (*A = 0); A = A + 1;
         x1 = (*A = 1); A = A + 1;
         A = A - 1; x2 = (*A = 2);
         x3 = (*A = 3); A = A + 1;
         A = A - 1; x4 = (*A = 4);
         A = A - 1; x5 = (*A = 5);
         A = P(x0, x1, x2, x3, x4, x5);

A transformation rule for multiple assignments would result in:

         x0 = (*A = 0); A = A + 1;
         x1 = (*A = 1); A = A + 1;
         A = A - 1;     x2 = (*A = 2);
         x3 = (*A = 3); A = A + 1;
         A = A - 1;     x4 = (*A = 4);
         A = A - 1;     x5 = (*A = 5);
         A = P(x0, x1, x2, x3, x4, x5);
-->
         *A = 0;    x0 = *A;  A = A + 1;
         *A = 1;    x1 = *A;  A = A + 1;
         A = A - 1; *A = 2;   x2 = *A;
         *A = 3;    x3 = *A;  A = A + 1;
         A = A - 1; *A = 4;   x4 = *A;
         A = A - 1; *A = 5;   x5 = *A;
         A = P(x0, x1, x2, x3, x4, x5);

Which would be translated as:
         let *A <- 0 in   let x0 = *A in   let A = A + 1 in
         let *A <- 1 in   let x1 = *A in   let A = A + 1 in
         let A = A - 1 in let *A <- 2 in   let x2 = *A in
         let *A <- 3 in   let x3 = *A in   let A = A + 1 in
         let A = A - 1 in let *A <- 4 in   let x4 = *A in
         let A = A - 1 in let *A <- 5 in   let  x5 = *A in
         let A = p(x0, x1, x2, x3, x4, x5)              in q.

which is beta equivalent to:

          let *(A + 1) <- 4 in
          let *A <- 5 in
          let A = p(0, 1, 2, 3, 4, 5) in q


where p is the translation of P and q is the translation of whatever sequence
of statements follows (as outlined in the prior 2 articles).

   This result is also the translation of:

          *(A + 1) = 4; *A = 5;
          A = P(0, 1, 2, 3, 4, 5);

So, one of the things that emerges from this discussion is that you can see
the potential for realising different program transformation and optimization
systems all within this common framework, based on both the side-effect
elimination rules and on beta reduction. 

   In a way, it's a necessary concept here.  In order to avoid the bottleneck
above, you have to interleave beta reduction with side-effect elimination so
that you can go directly from:

         A = P(*A++ = 0, *A++ = 1, *--A = 2, *A++ = 3, *--A = 4, *--A = 5);

to:
         *(A + 1) = 4; *A = 5;
         A = P(0, 1, 2, 3, 4, 5);