09/01/1994 09:00 AM
Computer Science
Logic programming is based on the idea that inference can be viewed as a computation. The fact that both programs and their specifications can be expressed in the same language makes logic programming very useful for program development. But it is also known that clarity and efficiency are two rather incompatible demands to put on a programming language. It is thus important to develop techniques for systematically transforming clear but inefficient programs into efficient (although probably rather opaque) final programs. This thesis contains some contributions that hopefully bring us closer to this goal. Before transformation can take place the input program must be parsed and analyzed to extract properties that are not explicit in the program itself. Parsing is an area of computer science well understood, but with the advent of modern languages, like Prolog and ML, the programmer was able to introduce and change operator symbols. On one hand, operator symbols made the code more readable but it also complicated the parsing job; standard parsing techniques cannot accommodate dynamic grammars. In the first part of this thesis we present an LR parsing methodology, called ``deferred decision parsing\", that handles dynamic operator declarations, that is, operators that are declared at run time. It uses a parser generator much like Yacc. Shift/reduce conflicts that involve dynamic operators are resolved at parse time rather than at parser construction time. As an example of our parser generator we present a grammar for Prolog, a language that has been in use for almost twenty years but still lacks a precise formal syntactic definition. The parser generator can also serve as a replacement implementation for Definite Clause Grammars, a novel parsing feature of Prolog. However, an LR parser does not normally support inherited attributes. In the next part of the thesis we present two transformation methods for (strong) non-circular attribute grammars that allows them to be evaluated within the environment of an LR parser. Our methods represent a compromise in that attribute evaluation is normally performed on the fly except when, in some evaluation rule, the referenced attributes are unavailable, and the execution of the rule has to be postponed. Suspension and resumption points for these evaluation rules can either be determined statically (method 1) or dynamically (method 2). For both methods we guarantee that resumption takes place as soon as possible. In the final part of the thesis we present a technique to detect that pairs of rules in a logic program are ``mutually exclusive\'\'. In contrast to previous work our algorithm derives mutual exclusion by looking not only at built-in, but also user-defined predicates. This technique has applications to optimization of the execution of programs containing these rules. Additionally, the programmer is less dependent on non-logical language features, such as Prolog\'s ``cut\'\', thus creating more opportunities for parallel execution strategies. Notes: Ph.D. Thesis
