On Tuesday I gave a tutorial on partial evaluation, called "Build your own partial evaluator in 90 minutes" at the working conference on domain specific languages (DSL 2011) in Bordeaux. The lecture notes benefited greatly by help from Ralf Lämmel. I've given this talk a few times before, but have not suggested that the audience actually implement a partial evaluator during the tutorial, as I did this time. Several people complete the task during the talk, and many more completed it in the following few hours. Solutions were done in Haskell, Rascal, and Scheme, and maybe more languages.
Working in Scheme, Ludovic Courtès finished the code that evening. He then checked it in to the code base of the GNU Guile compiler. I suspect that it needs a little more engineering to make it completely robust, but there is nothing that can't be taken care of with a little care.
This is a very fun example of practical impact: lecture to deployment in less than 24 hours. Thanks to everyone who attended, and to Ludovic for his extra efforts!
How does the partial evaluator handle this one:
ReplyDeletef(n,k) = if n > k then 0 else f(n+1,k)
Now specialize f(0,k). If I am understanding your description correctly then the partial evaluator will evaluate f(1,k) then f(2,k) ... and it will not terminate.
Hi Jules,
ReplyDeleteYes, you are correct that some programs do not terminate when partially evaluated. Techniques for ensuring termination have been studied extensively. My own work takes the pragmatic approach of making it the responsibility of the programmer to ensure termination. This is true in C++ templates, for example, which can cause the C++ compiler not to terminate. For this to work, the programmer must also be able to control where partial evaluation is applied. The simple approach described in this tutorial does not cover these more advanced topics. But they are discussed in more detail in the paper on Hybrid Partial Evaluation.