Exercise 1: Specialising the power function

The purpose of this exercise is for you to try out a partial evaluator for a small subset of Haskell. Place the following definition in a file Power.hs: 
module Power where
power n x = if n==0 then 1 else x*power (n-1) x
and check that you can specialize it as follows, where you type the parts in bold. 
muppet30> ./PE Power
Loading..Power..
power 3 x
power_0 3 x

module Power where
power_0 n x = if n == 0 then 1 else x * power_0 (n - 1) x
As you can see, no interesting specialisation happens, because nothing is annotated as static. Try the following experiments. At each step, use the annotated program from the previous step as your starting point for the next one.
  1. Annotate power so that the first parameter is static, and the conditional expression is simplified. Remember to annotate the initial call correctly also. What happens when you specialise power to the value -1?
  2. Annotate the recursive call so that it is unfolded.
  3. Annotate the definition and calls so that both parameters are bound by static lambda expressions. (Don't forget the initial call!). How does the residual program change?
  4. Now change the annotations so that the first parameter becomes dynamic again, but the second parameter becomes static.
Last modified: Fri Sep 19 12:16:27 MET DST 1997