Program specialization is a collection of program transformation techniques for improving program efficiency by exploiting some information available at compile-time about the input data. 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 to direct the application of these extended rules so to derive very efficient specialized programs. The efficiency improvements which may even be exponential, are achieved because the derived programs are semi-deterministic and the operations which are performed by the initial programs in different branches of the computation trees, are performed in the specialized programs within single branches. We also make use of mode information to guide the unfolding process and to reduce nondeterminism. To exemplify our technique, we show that we can automatically derive very efficient semi-deterministic matching programs and semi-deterministic parsers for regular languages. The derivations we have performed could not have been done by previously known partial evaluation techniques.

Among the various tasks involved in SE & KE, requirements engineering, specification, prototyping, and validation are regarded as crucial since they decide whether a software system fulfills the users’ expectations. Formal methods provide a rigorous framework to guaranteed. Logic Programming has been recently shown as a promising candidate support these tasks and some relevant features can be in that way captured and formally regarding these concerns. Nevertheless, formalism does need some explanation to let it be more readable and understandable. This paper focuses on a specification design method which mixes formal text (represented by a logic program) and comments (using either formal or informal assertions). By the design of a specification we refer to the intertwined tasks of describing the specification and improving it by the investigation of proofs. These proofs aim to verify the link between the specification and the comments, and are partly automated. Then we present our practical experience in the use of an interacti ve proof system. As an example, we show how this methodology is currently applied to the draft of standard Prolog.