Assignment Partial Evaluation

Pt04
%TOC%

-----------------------------++ Assignment

The goal of the lab assignment for the second half of this course is
to write a partial evaluator for Tiger. You will have to hand in your
implementation at the end. For your convenience the development is
broken down in small steps.

We start with Tiger-FOF, the restriction of Tiger to a first-order
functional language, i.e., without the imperative constructs
(assignments, loops) and without arrays and records. Once you have a
partial evaluator for that language it can be extended in various
directions.

The Tiger-FOF specializer can be further decomposed into binding-time
analysis and specialization proper (and a bunch of standard
components). These tasks can also be approached separately by using an
intermediate format in which binding-time analysis has been made
explicit using annotations.

So the first task is to write a specializer for Tiger (FOF) programs
with binding-time annotations.

---------+++ Components of the Partial Evaluator

The complete partial evaluator for Tiger-FOF consists of the following
components:

   * parse-tiger : parser
   * Tiger-Desugar : desugaring
   * FOF-Format : a format checker that checks the language restrictions
   * Tigerfof-BTA : binding-time analysis
   * Tigerfof-PE : partial evaluation
   * ... : optional transformations
   * Tiger-Ensugar : undo some desugarings to produce readable code
   * pp-tiger : pretty-print tiger program

Most of these components are available in the standard Tiger
distribution. The composition is made with XTC, the transformation
tool composition framework.

---------+++ Template Package

Since the composition of a complete transformation framework is too
complex for command-line build-management, we have constructed a
template package for your development, containing the composition,
template modules for specializer components, and some tests.

You can get the package at

   * http://www.cs.uu.nl/docs/vakken/pt/partial-eval-0.3.tar.gz

The package should be configured as follows:

<verbatim>
tar zxf partial-eval-0.3.tar.gz
cd partial-eval-0.3
./configure --prefix=/tmp/$HOME --with-xt=/usr --with-tiger=/projects/stratego/tiger
make 
make install
</verbatim>

(Assuming that you work on the Linux machines in the lab. Of course
you can use a different installation directory.)

---------+++ Version Management

Create a subversion repository pt03-name1-name2 at http://svn.cs.uu.nl
for your project and import the source of the template package in
it. Commit regularly and make tags of working versions. Make the
repository readable for visser and mbravenboer so that we can access
it.

---------+++ Using the Partial Evaluator

The package implements the composition described above via the
=tigerfof-specialize= tool. Eventually, you should be able to
completely specialize programs as follows:

<verbatim>
  tigerfof-specialize -i power.tig -o power9.tig --arg2 9
</verbatim>

The tool can also be used to only specialization or only binding-time
analysis, by turning off the appropriate tools. Thus, to only specialize
turn off binding-time analysis:

<verbatim>
  tigerfof-specialize -i power-bta.tig -o power9.tig --arg2 9 --bta off
</verbatim>

This assumes that =power-bta.tig= is a program with binding-time
annotations.

To test binding-time analysis you can turn off specialization:
<verbatim>
  tigerfof-specialize -i power.tig -o power9-bta.tig --arg2 9 --pe off
</verbatim>

It is even possible to turn off pretty-printing and ensugaring in order
to inspect the raw ATerms produced by your transformation. For
instance to see the result specialization:

<verbatim>
  tigerfof-specialize -i power-bta.tig -o power9.tig --arg2 9 --bta off --pp off -ensugar off
</verbatim>

-----------------------------++ Command-line Arguments in Tiger

Tiger programs can read command-line arguments with the built-in
function =argv(i)=, which returns the value (a string) of the i-th
argument. For example, the =power.tig= program below reads two
arguments, converts them to integers (using =string2int=) and computes
the power of the first argument to the second argument. To run the
program with the interpreter arguments should be passed to it as
=--argi val=. For example, to compute the 8th power of 2, run
=power.tig= as:

<verbatim>
  run-tiger -i power.tig --arg1 2 --arg2 8
</verbatim>

Now the point of partial evaluation is that a program can be
specialized to one or more of its arguments. Thus, the partial
evaluator should also interpret the command-line arguments and
incorporate them in the specialized program. For example, the power
program can be specialized to its second argument, and the specialized
program can then be run with different values for its first argument
and _no_ value for its second argument:

<verbatim>
  tigerfof-specialize -i power.tig -o power9.tig --arg2 9
  run-tiger -i power9.tig --arg1 2 
  run-tiger -i power9.tig --arg1 4
  run-tiger -i power9.tig --arg1 6 
</verbatim>

---------+++ The power Program

The following program is the basic example that your partial evaluator
should work on. It reads two strings from the command-line, converts
them to integeres, and then computes the power using the =power=
function, which calls several auxiliary functions.

<verbatim>
---------------------------------
let

function mod(x : int, y : int) : int =
  x - ((x / y) * y)

function even(x : int) : int =
  mod(x, 2) = 0

function square(x : int) : int =
  x * x

function power(x : int, n : int) : int =
  if n = 0 then 1
  else if even(n) then square(power(x, n / 2))
  else x * power(x, n - 1)

function main() =
  printint(power(string2int(argv(1)), string2int(argv(2))))

in main() end
---------------------------------
</verbatim>

Note the convention of having a call to the function =main()= as the
body of the (outermost) let.

-----------------------------++ Binding-Time Annotations

Partial evaluation is split into two phases: binding-time analysis and
specialization.  The process of binding-time analysis produces a
program with _binding-time annotations_. Code between =<...>=
indicates _dynamic_ code, which should be evaluated at run-time, and
code in =~...= is _static_ code, which should be evaluated during
specialization. (This notation is copied from the <nop>MetaML language.)

Here is the power program with binding-time annotations which indicate
that the second argument is provided at specialization-time and the
first at run-time. The rest of the program is annotated consistently:

<verbatim>
---------------------------------
let

function mod(x : int, y : int) : int =
  x - ((x / y) * y)

function even(x : int) : int =
  mod(x, 2) = 0

function square(x : <int>) : int =
  <x * x>

function power(x : <int>, n : int) : <int> =
  if n = 0 then <1>
  else if even(n) then square(power(<x>, n / 2))
  else <x * ~power(<x>, n - 1)>

function main() =
  <printint(power(string2int(argv(1)), ~string2int(argv(2))))>

in main() end
---------------------------------
</verbatim>

Note that the types of dynamic function arguments are annotated to
indicate their binding-times.

A program with binding-time annotations can be `run', resulting in a
specialized `residual' program. For example, when specializing the
program above as:

<verbatim>
  tigerfof-specialize -i power-bta.tig -o power9.tig --arg2 9 --bta off
</verbatim>

the result is the residual program:

<verbatim>
---------------------------------
let function k_0(e_0 : int) =
      let var q_1 : int := e_0 * 1
          var r_1 : int := q_1 * q_1
          var s_1 : int := r_1 * r_1
      in e_0 * (s_1 * s_1)
      end
in printint(k_0(string2int(argv(1))))
end
---------------------------------
</verbatim>

Note that a new function =k_0= has been generated that computes =e_0=
to the power of 9.


-----------------------------++ Specialization

The first part of the assignment is to write the specializer component
=Tigerfof-PE.str=.  The test script =xmpl/fof/power-test= applies the
tool in various configurations to the power example program. As usual
you should develop your own additional (smaller) test programs to test
specific situations. By all means add these to your repository.

---------+++ Step 1: Incorporate Static Arguments

The start of partial evaluation is the incorporation of the static
arguments of a program. This can be done by evaluating the =argv(i)=
expressions in the program. Command-line arguments are processed using
the 'command-line-options' strategy in the template module
=Tigerfof-PE.str=.  An argument can be obtained by looking it up in
the configuration table:

<verbatim>
  <conc-strings; get-config> ("--arg", <int-to-string>i) => s
</verbatim>

But you can reuse the implementation in module =Eval-Primitive.str=
from the tiger installation. It defines a rule =EvalPrim= for
evaluating expressions =argv(i)=. See

   * [[https://svn.cs.uu.nl:12443/repos/StrategoXT/trunk/tiger/tiger-front/eval/Eval-Primitive.str][Eval-Primitive.str]]

Write a strategy for tiger-pe that replaces all =argv(i)= expressions
by their value on the command-line, if provided of course.

---------+++ Step 2: Evaluate Static Code, Residualize Dynamic Code

The next step is to evaluate those expressions that should be
evaluated statically (the code in =~...=) and produce a residual
expression in which static expressions have been replaced with their
value. You can use the evaluation rules in the following modules:

   * [[https://svn.cs.uu.nl:12443/repos/StrategoXT/trunk/tiger/tiger-front/eval/Eval-Operator.str][Eval-Operator.str]]
   * [[https://svn.cs.uu.nl:12443/repos/StrategoXT/trunk/tiger/tiger-front/eval/Eval-Conditional.str][Eval-Conditional.str]]

It is useful to write _two_ strategies _reduce-static_ and
reduce-dynamic_ which reduce static and dynamic code, respectively.

(See also Figure 5.7 on page 115 in the partial evaluation book.)

---------+++ Step 3: Unfold Static Function Calls

Next extend the =reduce-static= strategy such that static function
calls are unfolded (inlined). Use the approach to inlining described
in Chapter 11 (Scoped Dynamic Rewrite Rules). That is, generate an
unfolding rule when encountering a function definition and use it at
its (static) call sites. Create =let var= declarations to bind the
actual parameters to the formal parameters of the function. That is,
if the function definition is

<verbatim>
  function f(x1 : t1, x2 : t2) : t3 = e
</verbatim> 

replace a function call =f(e1,e2)= by

<verbatim>
  let var x1 : t1 := e1
      var x2 : t2 := e2
   in e 
  end
</verbatim>

---------+++ Step 4: Propagate Static Let Bindings

Variables that are bound to a constant expression can be substituted in the
body of the let. That is, a variable declaration
<verbatim>
  let var x := ~e1 in e2
</verbatim> 

can be reduced to =e2= in which =x= is replaced by =e1=.

Note that you can use a dynamic rule rewriting =x= to =e1= 
for this substitution.

---------+++ Step 5: Specialize Dynamic Function Calls

Dynamic function calls should not be unfolded, but rather specialized. That is,
a new function definition should be created that specializes the function to
the static arguments used in the call. Thus, a call

<verbatim>
  <f(e1,~e2)>
</verbatim> 

should be replaced with a call to a new function =g= with the dynamic argument
=e1=:

<verbatim>
  <g(e1)>
</verbatim> 

Given the definition of function =f=:

<verbatim>
  function f(x1 : <tid1>, x2 : tid2) : <tid3> = e
</verbatim> 

a new function definition for =g= should be generated, which binds
the static argument =e2= to the corresponding parameter =x2=:

<verbatim>
  function g(x : tid1) : tid3 =
    let var x2 : tid2 := e2 in e end
</verbatim> 

The body of this specialized function should of course be reduced in order
to propagate the static parameter.

You can collect all specializations for a function using a dynamic
rule. Make sure to memoize a generated specialization such that the
next time a call to the same function with the same static parameters
is encountered, a call to the same new function is produced.

-----------------------------++ Binding-Time Analysis

Binding-time analyis works similarly to specialization. Instead of
reducing an expression to a value, it is reduced to an expression
with binding-time annotations.

---------+++ Plain Binding-Time Analysis

Start with a simple binding-time analysis that attaches binding-time
annotations to expressions according to the following rules:

   * A constant is static
   * A function call / operator / record access is static if all its arguments are static
   * A record creation is static if all its field initializations are static
   * A conditional is static if its condition is static

In all other cases the expression is dynamic.

The binding-time of a variable is determined by the function
parameter or variable declaration that it corresponds to and
should be propagated from the declaration to the use site
(using a dynamic rule of course). 

---------+++ Binding-Time Analysis by Transformation

Binding-time analysis can be implemented by a program transformation
that propagates binding-time annotations. For example, an
annotation of the arguments of a function, is transformed to an
annotation of the function call as follows:

<verbatim>
  f(<e1>,~e2) ---> <f(e1,~e2)>
</verbatim>

Here the call becomes dynamic, since one of its arguments is. This
propagation can be expressed using simple rewrite rules.

---------+++ Specializing Functions to Binding-Time

To achieve _poly-variant_ binding-time analysis, each combination
of binding-times for the arguments of a function should be used
to generate a new function declaration, in which the body is annotated
according to the binding-times of the parameters. The function should
be given a new name to avoid name clashes. A good convention is to 
use the letters =d= and =s= to indicate the static and dynamic parameters.
Thus, =power(x,5)= is annotated as 
<verbatim>
  <power_ds(x,~5)>
</verbatim>

Note that for each function call an corresponding function should be
generated. Of course, only one function should be generated for
each combination of binding times, and all other calls with the
same binding times should be replaced with a call to that function.
Dynamic rules come in handy to memoize the specialization of 
a function call and to collect all specializations of a function
declaration.

The following is the =power= program with binding-time annotations
assuming that the second argument is static.

<verbatim>
---------------------------------
let

function mod_s(x : int, y : int) : int =
  x - ((x / y) * y)

function even_s(x : int) : int =
  mod(x, 2) = 0

function square_d(x : <int>) : <int> =
  <x * x>

function power_ds(x : <int>, n : int) : <int> =
  if n = 0 then <1>
  else if even_s(n) then <square_d(power_ds(x, ~(n / 2)))>
  else <x * power_ds(x, ~(n - 1))>

function main_s() =
  <printint(power_ds(string2int(argv(1)), ~string2int(argv(2))))>

in main_s() end
---------------------------------
</verbatim>

---------+++ Maximize Call Unfolding (Transition Compression)

In order to reduce the number of specialized functions, it is
attractive to inline as many function calls as possible. This
can be achieved by adapting the binding-time analysis to make
all calls that are dynamic, but do not occur under a dynamic
conditional 'static'. This indicates to the specializer that
it can be inlined. Since dynamic functions expect (some of)
their parameters to be dynamic, these should be annotated as
<verbatim>
   f(<~g(<e1>,e2)>, e3)
</verbatim>
to indicate that the call to =g= should be unfolded, but that
the result is _code_ that should be passed to function =f=.

This can be achieved by a transformation on the plain binding-time
annoation described above. For the =power= program this results
in:

<verbatim>
---------------------------------
let

function mod_s(x : int, y : int) : int =
  x - ((x / y) * y)

function even_s(x : int) : int =
  mod(x, 2) = 0

function square_d(x : <int>) : <int> =
  <x * x>

function power_ds(x : <int>, n : int) : <int> =
  if n = 0 then <1>
  else if even_s(n) then <square_d(<~power_ds(<x>, (n / 2))>)>
  else <x * <~power_ds(<x>, (n - 1))>>

function main() =
  <printint(<~power_ds(<string2int(argv(1))>, string2int(argv(2)))>)>

in main() end
---------------------------------
</verbatim>

-----------------------------++ Strategies

There are many variations on the basic strategies for binding-time analysis and specialization.

---------+++ Unfold All Static Calls

When applying the transition compression transformation described above it is safest to
leave calls under dynamic conditionals untouched, i.e., dynamic. Sometimes, a dynamic
conditional has internal static code; in a variation calls in such static parts can be made
static.

---------+++ Unfold All Calls

Alternatively _all_ function calls can be unfolded during specialization. This only works
with the following option.

---------+++ Memoize Unfolding

Often it is not possible to determine during binding-time analysis whether a specific
call can be safely unfolded or not. An alternative strategy is to unfold all/more calls,
but to fall back to specialization if it turns out that there where more calls to
the same function with the same static parameters; in which case code duplication is
avoided by specialization.

---------+++ Substitute Values

The values and which are substituted for variables can also be varied. Code with records
yield a nicer program (not necessarily more efficient) when record accesses of the form
=lv.x= are propagated to their usess.

---------+++ Additional Transformations

Finally, the offline partial evaluator described here uses only limited program analysis
to make decisions about unfolding versus specialization, since only limited information
is available dusing binding-time analysis. Therefore, specialization can be complemeneted
with additional transformations. Some example transformation components that could be
applied are 

   * Tiger-Inline: inlines function declarations which are 'simple' or which are called only once
   * Tiger-ElimDead: eliminates function and variable declarations that are not used in the program

-----------------------------++ Testing the Partial Evaluator

A new template package is available with a number of test programs and scripts to apply the
partial evaluator to the programs. The new package also contains an extension of the driver
program with switches to turn on or off the strategies discussed above. The new programs
are in subdirectory fofrec, which you can add to your own codebase. The examples are in
directory =xmpl/fof=.

   * http://www.cs.uu.nl/docs/vakken/pt/partial-eval-template-0.4.tar.gz