Curry [HAK 
99]
is a functional logic programming language based on needed narrowing
which combines the best ideas of declarative languages such as
Haskell [HPW92] and SML [MTH90] (functional languages),
Gödel [HL94] and 
Prolog [NM88] (logic languages),
and ALF [HS91], Babel [KA96] and
[LS99] (functional logic languages).
UPV-Curry is a new interpreter of Curry
which provides an
almost complete implementation
of the language
according to [HAK 99] (it lacks Curry modules and
encapsulated search).
The system is written in SICStus Prolog v3.6 and
consists of about 250 clauses (3000 lines of code).
The parser is expressed by 95 clauses, the typechecker
module by 55 clauses, the algorithm which builds definitional trees by 20
clauses, the execution module by 45 clauses, and the interface and
some other utilities by 35 clauses.
See [EAL98] for a complete description.
We have performed an empirical comparison of
the original needed narrowing strategy and the optimized definition
when used in the implementation of Curry (see Table 1).
We first consider a basic UPV-Curry implementation
which mechanizes the standard function, and the original
definitional trees.
A second UPV-Curry implementation
includes the refinement due to the incremental
definitional trees.
The third UPV-Curry implementation includes the incremental
strategy 
,
but it considers the original definitional trees.
We finally consider a completely refined implementation,
including all optimizations.
Times were measured on a SUN SparcStation,
running under UNIX System V Release 4.0.
They are expressed in milliseconds and are the
average of 10 executions.
The benchmarks used for the analysis are given in Appendix; most of
them are standard Curry test programs. The
functions ackermann, fibonacci,
last, quicksort and mergesort are the standard ones;
horseman computes, by means of
constraints, the number of men and horses that have a certain
number of heads and feet;
finally, iter produces
a sequence of n nested calls to a given function
and is used to set
the potentiality of our method off.
Table 1: Comparison between UPV-Curry optimizations (in ms.)
Runtime input goals were chosen to give a reasonably long overall time, and are shown in Table 2. Natural numbers are implemented using Z/S-terms, and lists are shown within goals by using a subindex which represents its size. L is [10,9,8,7,6,5,4,3,2,1,0] in the goal for quicksort.
Table 2: Comparison with other Curry interpreters (in ms.)
The figures in Table 1 reveal that the proposed refinements are actually (and independently) effective. The goals which require much computation, such as ackermann, fibonacci, quicksort, and mergesort get a substained speed-up when incrementality is used (e.g. 3.20 for the ackermann example). Indeed, the iter benchmark highlights the benefits which are brought by the incremental evaluation when the goal contains some nested calls and the innermost one must be evaluated first. On the other hand, even in the cases when no significant speed-up is obtained (this is the case of last), execution is not punished with any appreciable overhead. In other words, the use of incremental definitional trees causes no overload, which substantiate the idea that they are simply an apt shortening of the standard definitional trees. On the other hand, the incremental evaluation leads on its own to considerable speed-ups in program execution while still guaranteeing no appreciable slowdown.
Table 2 compares the fully optimized UPV-Curry
implementation and other Curry interpreters.
Namely, the figures in Table 2 correspond to the
runtimes of the benchmarks
for UPV-Curry, TasteCurry, and PACS-TasteCurry interpreters.
These results show that the incremental UPV-Curry implementation
performs very well in comparison to the other
Curry interpreters. In overall, it takes about 80% the
time needed by PACS-TasteCurry\
and about 38% the time needed by TasteCurry\
to evaluate the queries. These results seem to substantiate the
advantages
of using the proposed incremental techniques.
Another interesting aspect for the comparison concerns the spatial
savings due to the use of incremental definitional trees.
For the comparison, we strictly consider the information which is necessary for
defining the needed narrowing strategy.
Table 3 shows the ratio between the number of symbols of
inner nodes of standard definitional trees and incremental
definitional trees, respectively.
The results of Table 3 clearly evidence that incremental
definitional trees can also bring substantial savings in memory
space (up to 
in these tests).
