Advanced Models and Programs F2007
----------------------------------
sestoft@itu.dk 2007-03-26 *


ASSIGNMENT 9 (program generation, Scheme, runtime code generation)

There are 3 subproblems (with many subsubproblems) that should be
adequately answered.  In addition there are some bonus problems that
need not be answered.

The assignment is due Wednesday 11 April 2007.

You may hand in a physical document with solutions and brief
descriptions in Danish or English, stating your name and the
assignment number.  


PROBLEM 9.1: SCHEME

GETTING STARTED

Install a Scheme system, such as DrScheme Jaffer's scm system.  To
check that everything works out of the box, start the Scheme system
and enter this expression:

  (define (fac n) (if (= n 0) 1 (* n (fac (- n 1)))))

and then compute 

  (fac 10)

The result should be 3628800.  For kicks, try also (fac 1000).

Each subproblem below can be solved by a function definition 4 to 7
lines long, but you are welcome to define auxiliary functions for
clarity.  Apart from the new syntax and lack of pattern matching and
type checking, this sort of programming is very close to Standard ML.

PROBLEM 9.1.1: Define a function (prod xs) that returns the product of
the numbers in xs.  It is reasonable to define the product of an empty
list to be 1.

PROBLEM 9.1.2: Define a function (makelist n) that returns the
n-element list (n ... 3 2 1).

PROBLEM 9.1.3: Define a function (makelist n) that returns the
n-element list (1 2 3 ... n).

This can be done by defining an auxiliary function (makeaux i n) that
returns the list (i ... n) and then calling that auxiliary function
from (makelist n).  Note that the result of (makeaux i n) should be
the empty list if i>n.

PROBLEM 9.1.4: The function (filter p xs) returns a list consisting of
those elements of list xs for which predicate p is true.

Thus if xs is '(2 3 5 6 8 9 10 12 15) 
then (filter (lambda (x) (> x 10)) xs) should give (12 15)
and  (filter (lambda (x) (= 0 (remainder x 4))) xs) should give (8 12)

Define function (filter p xs).

PROBLEM 9.1.5: More recursion.  A list can contain a mixture of
numbers and sublists, as in

  (define list1 '(1 (1 2) (1 2 3)))
and 
  (define list2 '(1 (1 (6 7) 2) (1 2 3)))    
  
Write a function (numbers mylist) that counts the number of numbers in
mylist.

Hint: The predicate (number? x) is true if x is a number, not a list.

The result of (numbers list1) should be 6, 
and that of (numbers list2) should be 8.


PROBLEM 9.2: The exponential function e^x can be approximated by the
expression

1 + x/1 * (1 + x/2 * (1 + x/3 * (1 + x/4 * (1 + x/5 * (...)))))

Define a Scheme function (makeexp i n) that returns a Scheme
expression containing the terms from 1+x/i to 1+x/n of the above
expression 1, replacing ... at the end with 1.  Note the similarity to
Problem 9.1.3.

Thus (makeexp 1 0) should be the expression 1,
 and (makeexp 1 1) should be the expression 1 + x * 1/1 * 1, 
 and (makeexp 1 2) should be 1 + x * 1/1 * (1 + x * 1/2 * 1), 
 and so on.

Hint: In Scheme, multiplication may be applied to any number of
arguments, so x * y * z can be written (* x y z).

Hence, in Scheme the three expressions shown above can be written:

  1
  (+ 1 (* x 1 (+ 1 0)))
  (+ 1 (* x 1 (+ 1 (* x 0.5 (+ 1 0)))))

Check that (makeexp 1 n) produces these results for n = 0, 1, 2.

Then define x to be 2 and compute (eval (makeexp 1 n)) for n being 1,
10 and 20.  The correct result is close to 7.38905609893065.

Finally, use (makeexp 1 n) to define a function (myexp x) that
computes e^x using n terms of the above expansion.


PROBLEM 9.3: .NET RUNTIME CODE GENERATION

GETTING STARTED

 * Download examples the example file RTCG.zip and unpack it
 * Compile RTCG2D.cs and run it
 * Look at the RTCG2D.cs

For the exercises below, you are advised to use the DynamicMethod
approach (from .NET version 2.0) when generating new methods at
runtime.  Using class DynamicMethod is from namespace
System.Reflection.Emit one can generate a method that can be turned
into a delegate, which can then be called as any other delegate.
Methods generated this way can also be collected by the garbage
collector when no longer in use.  The only downside is that delegate
calls appear to be somewhat slower than interface calls.

All the example files with "D" suffix: RTCG1D.cs, RTCG2D.cs, ... use
the DynamicMethod approach.


PROBLEM 9.3.1:

Modify the RTCG2D.cs example so that it generates a method
corresponding to this one:

  public static double MyMethod1(double x) { 
    Console.WriteLine("MyMethod1() was called");
    return x * 4.5;
  }

Hint: The bytecode instruction for multiplication is OpCodes.Mul, from
the System.Reflection.Emit namespace.

Check that the new method works by calling it with arguments 1.0 and
10.0.


PROBLEM 9.3.2:

Modify the RTCG2D.cs example so that it generates a method
corresponding to this one:

  public static double MyMethod2(double x, double y) { 
    Console.WriteLine("MyMethod2() was called");
    return x * 4.5 + y;
  }

Note that you need a new delegate type DD2D like this 

  public delegate double DD2D(double x, double y);

and you need to change the generated method's signature also.


PROBLEM 9.3.3:

Write a C# method 

  public static I2I MakeMultiplier(int c) { ... }

that takes as argument an int c, and then generates and returns a
delegate of type I2I corresponding to a method declared like this:

  public static int MyMultiplier_c(int x) { 
    return x * c;
  }

where delegate type I2I is declared like this:

  public delegate int I2I(int x);

Hint: The MakeMultiplier method must include everything needed to
generate a MyMultiplier_c method.  The generated method's return type
and its parameter type should be int.


PROBLEM 9.3.4: 

The exponential function e^x can be computed by the expression 

  1 + x/1 * (1 + x/2 * (1 + x/3 * (1 + x/4 * (1 + x/5 * (...)))))

Write a C# method 

  public static D2D MakeExp(int n) { ... }

that takes as argument an integer n and uses runtime code generation
to generate and return a delegate of type D2D corresponding to a
method declared like this:

  public static double MyExp_n(int x) { 
    ... compute res as first n terms of the above product ...
    return res;
  }

Hint (a): If you were to compute the term instead of generating code
for it, you might do it like this:

  double res = 1;
  for (int i=n; i>0; i--)
    res = 1 + x / i * res;
  return res;

The generated code should contain no for-loop and no manipulation of
i, only the sequence of computations on res performed by the
iterations of the loop body.

Hint (b): To push integer i as a double, use

  ilg.Emit(OpCodes.Ldc_R8, (double)i);


PROBLEM 9.3.5: 

Write a C# method 

  public static D2D MakePower(int n) { ... }

that takes as argument an int n, and uses runtime code generation to
generate and return a delegate of type D2D corresponding to a method
declared like this:

  public static double MyPower_n(int x) { 
    ... compute res as x to the n'th power ...
    return res;
  }

Hint (a): If you were to compute the n'th power of x instead of
generating code for it, you might do it like this:

  double res = 1;
  for (int i=0; i<n; i++)
    res = res * x;
  return res;

The generated code should contain no for-loop and no manipulation of
n, only the sequence of computations on res performed by the loop's
body.

Hint (b): A much faster way of doing the same -- time O(log(n))
instead of time O(n) -- is this:

  double res = 1;
  while (n != 0) {
    if (n % 2 == 0) {
      x = x * x; 
      n = n / 2;
    } else {
      res = res * x;
      n = n - 1;
    }
  }
  return res;

Again, the generated code should contain no loop and no manipulations
of n; only the sequence of operations on x and res performed by the
loop body.


BONUS PROBLEM 9.4: 

File RTCG.cs implements the lecture's technique for runtime generation
of methods that can be called via an interface call, which sometimes
is faster than a delegate call.  Do not modify RTCG.cs (unless you
find a bug) but use it to compile example RTCG2G.cs, a variant of
RTCG2D.cs:

   csc /t:library RTCG.cs
   csc /r:RTCG.dll RTCG2G.cs

BONUS PROBLEM 9.4.1:

Solve some of the 9.3.x exercises using RTCG.cs and the lecture's
technique for runtime code generation.  The main advantage is that
generated methods can be called by interface calls, which may be
faster than delegate calls.

BONUS PROBLEM 9.4.2:

Consider example RTCG6D.cs which evaluates an expression by generating
bytecode code for it.  Change this example to use RTCG.cs and the
lecture's technique.  Measure whether this speeds up the computation
relative to the DynamicMethod technique.


BONUS PROJECT 9.5: 

Use runtime code generation to generate a fast serialization and
deserialization library, which creates specialized serialization and
deserialization methods for each type, and hence avoids reflection.
(This has been done before, but is a challenging and instructive
task).