LISP and Symbolic Computation, 10(2)101-111
Partial Evaluation of the Euclidian AlgorithmOlivier Danvy, BRICS, Department of Computer Science, University of Aarhus, Ny Munkegade, Building 540, DK-8000 Aarhus C, Denmark
Mayer Goldberg, BRICS, Department of Computer Science, University of Aarhus, Ny Munkegade, Building 540, DK-8000 Aarhus C, Denmark
|
Abstract: Some programs are easily amenable to partial
evaluation because their control flow clearly depends on one of their
parameters. Specializing such programs with respect to this parameter
eliminates the associated interpretive overhead. Some other programs,
however, do not exhibit this interpreter-like behavior. Each of them
presents a challenge for partial evaluation. The Euclidian algorithm
is one of them, and in this article, we make it amenable to partial
evaluation. We observe that the number of iterations in the Euclidian
algorithm is bounded by a number that can be computed given either of
the two arguments. We thus rephrase this algorithm using bounded
recursion. The resulting program is better suited for automatic
unfolding and thus for partial evaluation. Its specialization is
efficient.
Keywords: partial evaluation, scientific computation |
This article can be downloaded [here].
![[picture of journal cover]](../LISP.JPG)