Assignment Partial Evaluation

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:

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

(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:

  tigerfof-specialize -i power.tig -o power9.tig --arg2 9

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:

  tigerfof-specialize -i power-bta.tig -o power9.tig --arg2 9 --bta off

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

To test binding-time analysis you can turn off specialization:

  tigerfof-specialize -i power.tig -o power9-bta.tig --arg2 9 --pe off

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:

  tigerfof-specialize -i power-bta.tig -o power9.tig --arg2 9 --bta off --pp off -ensugar off

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:

  run-tiger -i power.tig --arg1 2 --arg2 8

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:

  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 

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.

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

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

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

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:

  tigerfof-specialize -i power-bta.tig -o power9.tig --arg2 9 --bta off

the result is the residual program:

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

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:

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

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

• 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:

• Eval-Operator.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

  function f(x1 : t1, x2 : t2) : t3 = e

replace a function call f(e1,e2) by

  let var x1 : t1 := e1
      var x2 : t2 := e2
   in e 
  end

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

  let var x := ~e1 in e2

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

  <f(e1,~e2)>

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

  <g(e1)>

Given the definition of function f:

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

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

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

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:

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

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

  <power_ds(x,~5)>

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.

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

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

   f(<~g(<e1>,e2)>, e3)

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:

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

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