2003/11/27 by Alberto Pettorossi, Pettorossi, Alberto, Maurizio Proietti +3
Computer Science · #Algorithms and Data Compression #D.1.2 #D.1.6 #F.3.1 #FOS: Computer and information sciences #Formal Methods in Verification #I.2.2 #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Programming Languages (cs.PL) #cs.LO #cs.PL
paper · pdf · doi:10.48550/arxiv.cs/0311044
74 pages. To appear in: Higher-Order and Symbolic Computation (Special Issue in Honor of Bob Paige)
arxiv created 2003/11/27 · openalex publication_date 2003/11/27 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.