Partial evaluation - vilinski/nemerle GitHub Wiki

We will discuss one of the possible applications of Nemerle meta-programming system in partial evaluation. This process is based on specializing given algorithm with some of its inputs, which are known statically (at compile time).

This is particularly useful when we have some general algorithm for solving a problem, but most of the time we use its special case. For example we have a procedure search to search for arbitrary pattern in a string, but 98% of its uses are with "what is The Answer" pattern. It would be nice to have the search_answer procedure, which would be highly optimized version of our general algorithm.

The methodology we will use here is general and can be used for various problems like: specializing numerical algorithms, pattern matching, generating compilers from interpreters, efficient embedding of domain-specific languages.

Let us consider a general power function. One of the most efficient ways of computing it is the logarithmic power algorithm.

Its implementation in Nemerle is presented below:

static power (x : double, n : int) : double
 {
   if (n == 0)
     1.0
   else
     if (n % 2 == 0) // even
       Sqr (power (x, n / 2))
     else
       x * power (x, n - 1)
 }

where Sqr is a standard method defined like:

static Sqr (x : double) : double { x * x }

As we can see it divides n by 2 if it is even and decrements by 1 if it is odd. In former case it performs square operation and in latter multiplication by x parameter. Note that the pattern of those operation depends only on n - x and n parameters are independent.

Here we come to the point - when we want to have specialized power function for some n, then we know exactly what operations it will perform on second argument. For example optimal pattern for x⁵ is x*(x²)². Now we want compiler to be able to generate this optimal set of operations for us. Here is the code to perform it:

macro power1 (x, n : int) 
{
  def pow (n) {
    if (n == 0)
      <[ 1.0 ]>
    else
      if (n % 2 == 0) // even
        <[ Sqr ($(pow (n / 2))) ]>
      else
        <[ $x * $(pow (n - 1)) ]>
  }
  pow (n);
}

We will give two different, but in general equivalent descriptions of what is happening here.

First you can view this as staged computation. We defere performing of Sqr and * operations until x is known at runtime, but we are free to perform all the others like comparisons of n and recursion at earlier stage. In the result only the optimal pattern of multiplication and square operations will be executed at runtime. The power macro is just a function, which performs first stage of computation (at compile time). The result of using this macro is inserting the second stage operations at the place of usage. This way the <[]> brackets can be considered as markers of second stage computation.

The other way of understanding the example is by its implementation in Nemerle compiler. It is a function generating code, which will be substituted at the place of its usage. The pow function simply generates the code of arithmetic expression composed of multiplications and square operations. As mentioned earlier we utilize the fact, that n is independent from x and basing on it we know exactly how resulting expression should look like. Here we can view <[]> brackets as what they really are - syntax for constructing parts of new Nemerle code.

The macro above can be easily used to create specialized method

static power74 (x : double) : double
{
  power1 (x, 74);
}

or directly in code (which would yield direct inlining of expressions and might be not a good idea for large chunks of generated code).

Just a little digression. The power macro could be written as:

macro power2 (x, n : int) 
{
  if (n == 0)
    <[ 1.0 ]>
  else
    if (n % 2 == 0) // even
      <[ Sqr (power2 ($x, $(n / 2 : int))) ]>
    else
      <[ $x * power2 ($x, $(n - 1 : int)) ]>
}

The resulting generated code would be identical, but here we see usage of some different features of macro system. In single macro execution we generate code, which contains invocation of this very macro. Note that it is not a direct recursive call, like in previous implementation. Although the result is the same, we encourage the former style, as it encapsulates all the macro's computations in single macro expansion, while the second way forces compiler to interleave many macro expansions. The latter way is slower and infinite loops here are harder to notice / debug.

Now we will show a little more evolved example, which shows that sometimes it is useful to explicitly store parts of code in collection, creating final computation from it.

Let us consider a function for computing permutation of given array. It takes input array as first parameter and array specifying the permutation as second parameter:

permute (data : array [int], permutation : array [int]) : void { ... }

where permutation array describes permutation as positions at which elements of input should appear in output (like for 3, 2, 1 and permutation 2, 1, 3, the output will be 2, 3, 1). The algorithm utilizes the fact that this representation directly exposes cycles of permutation and to permute elements we must simply move them by one position on its cycle. It is presented below:

permute (data : array [int], permutation : array [int]) : void
{
  def visited = array (permutation.Length);

  // we visit each cycle once using this top loop
  for (mutable i = 0; i < permutation.Length; i++) 
  {
    mutable pos = i;
    // we walk through one cycle
    while (!visited [pos]) 
    {
      visited [pos] = true;
      // moving its elements by one position
      def next_pos = permutation [pos];
      unless (visited [next_pos]) {
        data [pos] <-> data [next_pos];
        pos = next_pos;
      }
    }
  }
}

As we can see this algorithm does some operations of data only in one line

data [pos] <-> data [next_pos]

which is the swap operation on elements of array. The rest of its steps are performed only basing on contents of permutation. This quickly leads us to conclusion, that if we statically know this array, we can have highly optimized version of permute, which performs only sequence of swaps.

This is exactly what partial evaluation does, removing overhead of computations dependant only on static parameters. How do we code it using macros in Nemerle? It is almost as simple as deffering <-> operation with <[]>, but two more technical issues must be addressed.

First we must obtain the value of permutation array inside our first stage function (a macro). The simplest way would be to store it in some static field visible to the macro, but we chose to pass it directly as its parameter. Second one is that original permute function uses imperative style, so we must deffer computation also in this style, explicitly building sequence of final computations.

macro permute1 (data, p_expr)
{
  def permutation = expr_to_array (p_expr); // new

  def visited = array (permutation.Length);
  mutable result = [];                      // new

  for (mutable i = 0; i < permutation.Length; i++) {
    mutable pos = i;
    while (!visited [pos]) {
      visited [pos] = true;
      def next_pos = permutation [pos];
      unless (visited [next_pos]) {
        result = <[ 
          $data [$(pos : int)] <-> $data [$(next_pos : int)] 
        ]> :: result;                       // new
         pos = next_pos;
      }
    }
  }
  <[ {..$result } ]>                        // new
}

// technical function used to decompose expression
// holding contant array of ints
expr_to_array (expr : PExpr) : array [int] 
{
  // we must convert syntax tree of array into array itself
  | <[ array [..$p_list] ]> =>
    def permutation = array (p_list.Length);
    mutable count = 0;
    foreach (<[ $(x : int) ]> in p_list) {
      permutation [count] = x;
      count++;
    }
    permutation

  | _ => throw System.ArgumentException ("only constant arrays are allowed")
}

As we can see the function didn't change much. We must have added the variable result, which is the list of resulting expressions to execute. It is used at the end in <[{..]> expression - the sequence of swaps on data is the result of macro.

permute and permute can be used as follows:

permute_specialized (data : array [int]) : void
{
  permute1 (data, array [10, 7, 11, 0, 12, 5, 14, 6, 9, 4, 13, 2, 1, 8, 3]);
}
  
public Run (data : array [int]) : void {
  def perm = array [10, 7, 11, 0, 12, 5, 14, 6, 9, 4, 13, 2, 1, 8, 3];
  permute (arr, perm);
  permute_specialized (arr);
}

public class Robot
{
  public mutable Orientation : byte;
  public mutable X : int;
  public mutable Y : int;

  public IsDown : bool
  {
    get { Orientation == 1 }
  }

  public override ToString () : string
  {
    $"($X, $Y)"
  }
}

public variant Expr {
  | MoveBy { steps : int; }
  | Left
  | Right
  | Value { prop : string; }
  | If { cond : Expr.Value; then : Expr; els : Expr; }
}

public module Scripts 
{
  public Run (obj : Robot, expr : Expr) : void
  {
    def check_value (val) {
      System.Convert.ToBoolean (obj.GetType ().GetProperty (val.prop).GetValue (obj, null))
    }

    match (expr) {
      | Expr.MoveBy (steps) =>
        match (obj.Orientation) {
          | 0 => obj.X += steps
          | 1 => obj.Y += steps
          | 2 => obj.X -= steps
          | _ => obj.Y -= steps
        }

      | Expr.Left => obj.Orientation = ((obj.Orientation + 3) % 4) :> byte;
      | Expr.Right => obj.Orientation = ((obj.Orientation + 1) % 4) :> byte;

      | Expr.Value as val => _ = check_value (val)

      | Expr.If (val, e1, e2) =>
        if (check_value (val))
          Run (obj, e1)
        else
          Run (obj, e2)
    }
  }

  public Run (obj : Robot, name : string) : void
  {
    def script = GetScript (name);
    foreach (e in script) Run (obj, e)
  }
}

public module Scripts 
{
  public GenerateRun (obj : PExpr, expr : Expr) : PExpr
  {
    def check_value (val) {
      <[ $obj.$(val.prop : dyn) ]>
    }

    match (expr) {
      | Expr.MoveBy (steps) =>
        <[ match ($obj.Orientation) {
             | 0 => $obj.X += $(steps : int) 
             | 1 => $obj.Y += $(steps : int) 
             | 2 => $obj.X -= $(steps : int) 
             | _ => $obj.Y -= $(steps : int)
           }
        ]>

      | Expr.Left => <[ $obj.Orientation = (($obj.Orientation + 3) % 4) :> byte ]>;
      | Expr.Right => <[ $obj.Orientation = (($obj.Orientation + 1) % 4) :> byte ]>;
      | Expr.Value as val => <[ _ = $(check_value (val)) ]>

      | Expr.If (val, e1, e2) =>
        <[ if ($(check_value (val)))
             $(GenerateRun (obj, e1))
           else
             $(GenerateRun (obj, e2))
        ]>
    }
  }
}

macro GenerateRun (obj, name : string)
{
  def script = Scripts.GetScript (name);
  def exprs = List.Map (script, fun (e) { Scripts.GenerateRun (obj, e) });
  <[ { ..$exprs } ]>
}

def x = Robot ();
Scripts.Run (x, "myscript1");
System.Console.WriteLine (x);    
GenerateRun (x, "myscript1");    
System.Console.WriteLine (x);