Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism

Details Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism

2003-11-27

arxiv.org/abs/cs/0311044v1

Computer Science

Programming Languages

74 pages. To appear in: Higher-Order and Symbolic Computation (Special Issue in Honor of Bob Paige)

Scientific paper

Program specialization is a program transformation methodology which improves program efficiency by exploiting the information about the input data which are available at compile time. We show that current techniques for program specialization based on partial evaluation do not perform well on nondeterministic logic programs. We then consider a set of transformation rules which extend the ones used for partial evaluation, and we propose a strategy for guiding the application of these extended rules so to derive very efficient specialized programs. The efficiency improvements which sometimes are exponential, are due to the reduction of nondeterminism and to the fact that the computations which are performed by the initial programs in different branches of the computation trees, are performed by the specialized programs within single branches. In order to reduce nondeterminism we also make use of mode information for guiding the unfolding process. To exemplify our technique, we show that we can automatically derive very efficient matching programs and parsers for regular languages. The derivations we have performed could not have been done by previously known partial evaluation techniques.

Affiliated with

Also associated with

No associations

Rating

Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Derivation of Efficient Logic Programs by Specialization and Reduction of Nondeterminism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-518834