| Código: |
|
DIAB-04-05-1 | | Publicación: |
|
04-05-2004 | | Título: |
|
Incremental Tupling with Simplification Pre-Process | | Detalle: |
|
This paper investigates the optimization by fold/unfold
of declarative programs that integrate the best features
from both functional and logic programming. Transformation
sequences are guided by a mixed strategy that successfully
combines two well-known heuristics -composition and
tupling-, thus avoiding the construction of intermediate
data structures and redundant sub-computations. We have
decomposed the internal structure of both methods in
three low-level transformation phases in order to
analyze their main similarities and differences. In
particular, whereas composition is able to produce a
single function definition for some nested (composed)
functions, the tupling method merges non-nested functions
calls into a new function definition called eureka.
In our approach, we solve the non trivial problem of
discovering the set of calls to be tupled in an
incremental way, i.e. by iteratively chaining
different eureka definitions where only non-nested
calls sharing common variables are taken into account.
With this easy method, that complements the one done by
composition, we are able to perform powerful tupling
optimizations at a very low cost. Moreover, by
appropriately combining both strategies, together with
a simplification pre-proccess based on a kind of
normalization, we optimize a wide range of programs
(with nested and/or non-nested function calls) in a
fully automatic way. | |
![]() |
|
|
