Thesis (M.S.)--Rochester Institute of Technology 1987. / Includes bibliographical references (leaves 86-88).

Thesis (Ph. D.)--Virginia Polytechnic Institute and State University, 1991. / Vita. Abstract. Bibliographies. Also available via the Internet.

Thesis (M.S.)--Rochester Institute of Technology, 1987. / Typescript. Includes bibliographical references (leaves 56-57).

Adhering to the principles of logic programming results in greater expressiveness than is obtained by using the many non-logical features which have been grafted onto current logic programming languages such as Prolog. This report describes an alternative approach to high performance logic programming in which the language and its implementation were designed together. Prolog's non-logical features are discarded and new logical ones are added. Extended pure Prolog (xpProlog) is a superset of conventional Prolog; it is sufficient in itself, without any need for "impure" non-logical predicates. This gives both greater expressiveness and better performance than conventional Prologs. XpProlog programs have the following advantages over conventional Prolog programs: • They are often easier to understand because their meaning does not rely on the underlying computational mechanism. • Coroutining, automatic delaying and sound negation are available. • As technology improves, better implementations and optimization techniques can be used without affecting existing programs. This report covers: • The proper use of logic programming. • How Prolog must be changed to become a good logic programming language (xpProlog). • Sound negation and coroutining. • An efficient abstract machine (xpPAM) which can be efficiently emulated on conventional machines, translated to conventional machine code, or implemented in special purpose hardware. • How to compile extended Prolog and functional (applicative) languages to the abstract machine or to conventional machine code. • Discussion of alternative Prolog abstract machine designs. The xpProlog Abstract Machine's design allows: • Performance similar to the Warren Abstract Machine (WAM) for sequential programs. • Tail recursion optimization (TRO). • Parallelism and coroutining with full backtracking. • Dynamic optimization of clause order. • Efficient if-then-else ("shallow" backtracking). • Simple, regular instruction set for easily optimized compilation. • Efficient memory utilization. • Integrated object-oriented virtual memory. • Predicates as first-class objects. • Simple extension to functional programming. C.R. categories: 1.2.5: Prolog; D.1.3: concurrent programming; D.3.2: very high level languages; D.3.3: language constructs: coroutines, backtracking; D.3.4: 1 interpreters.; 1.2.3: logic programming. / Science, Faculty of / Computer Science, Department of / Graduate

The fact and rule list internal to Prolog is capable of handling as many facts as available memory resources permit. A solution to this limitation is to store facts on disk, retrieving them into a main memory database buffer only as needed. Allocating a fixed portion of main memory to buffer database facts frees up scarce main memory for more frequently accessed rules and data structures internal to Prolog. The Prolog Database System built in connection with this project transparently stores and retrieves facts on disk and evaluates them in the order they were asserted allowing for the transfer of existing small scale prototypes into large scale production systems. <p>Since existing relational database techniques were not designed to function in a Prolog environment where facts are evaluated in database facilities were designed, developed, and integrated into Prolog. These database facilities include a unique page replacement policy designed to minimize expensive page faults during the execution of a Prolog program. The look ahead page replacement policy looks ahead on database pages while they are in main memory in order to determine whether they are likely to be accessed again in the future. In this way, a near optimal working set of database pages is maintained in the database buffer, assisting with minimizing expensive page faults. / Master of Science

Prolog is a symbolic logic language presently emerging among numerous expert system designs. The architecture for a microsequenced Prolog machine (UPM) capable of providing the basic language features to a host computer is proposed. The Prolog machine functions are portioned into three processor components – Input/Output, Memory, and Central (CPU), where the design of the Central Processor is emphasized. Detailed discussion outlines the CPU facilities used to implement the forward-chaining and backtracking functions for the UPM. The UPM features are compared to the PLM-1, a microsequenced Prolog inference engine under development at University of California, Berkley. An emulation of the entire algorithm is provided, as well as a proposed microengine and associated microstore.

A developmental Prolog language interpreter is constructed in the C programming language. The data type format is a subset of that of the Project Aquarius Prolog Engine proposed and under development at the University of California, Berkley. The design of the Prolog interpreter is part of an investigation at UCF in design of expert system architecture for real time applications. The interpreter facilities of data structure definition and manipulation are developed and applied. The list data structure is used as an example data structure. The scheme for representing structured data is based on the Lisp cons cell. Run-time generated lists are represented by car and cdr pairs and are maintained separately from data structures which are part of the prolog program. A data memory is used to augment the environment memory of the Prolog interpreter. The advantages and disadvantages of the proposed structure and implementation scheme are discussed.

Prolog is a logic programming language based on first order logic. It uses resolution as a rule of inference, and unification is the heart of resolution. The unification algorithm is a syntactic process and hence attaches no meaning to function and predicate symbols. We incorporate arithmetic into unification by simultaneously solving linear equations that are created during the unification of partially instantiated numeric expressions. Prolog operates on the Herbrand universe, which is a single unstructured domain. In case of large structured domains, the number of resolution steps required for inference is large. We have incorporated type inheritance into Prolog to exploit large structured domains. Types are subuniverses corresponding to sets of objects. The subset of relation between types induces a hierarchy on the universe. Using the property of inheritance it is possible to obtain shorter proofs in inference. We used the constraint satisfaction model and the hierarchical constraint satisfaction concept to incorporate these extensions to Prolog. Thus, we succeeded in obtaining a logic programming language with arithmetic and type inheritance. This implementation extends standard Prolog and can be directly added to the WAM concept. / Master of Science

Prolog is a linear resolution theorem prover with restrictions on the form of the clauses to prune the search space. Although Prolog has been widely used for implementing natural language systems, database systems, knowledge based expert systems and other A.I tasks, it has many limitations. The inferencing is symbolic and all the computations are performed in the Herbrand universe. Prolog has no notion of function evaluation. The uniform parameter passing mechanism, viz unification, is syntactic and too restrictive in nature. Moreover, Prolog uses a depth first search strategy combined with chronological backtracking which renders the SLD-Resolution incomplete. In this thesis, we study the incorporation of a constraints solver into Prolog. The generalization of unification into a constraints satisfaction algorithm allows the incorporation of function evaluation into unification. Constraint satisfaction is used to replace unification thus enhancing the power of Prolog. This idea could possibly be extended to other contexts where unification is used. Constraints can also appear as goals in the body of a rule. We discuss the enhancement in expressive power leading to an efficient solution of a larger class of problems. We also discuss ways of compiling the constraint solver and the modifications that are needed to be made in the Warren abstract machine for Prolog. An interpreter for the extended Prolog (written in Prolog) incorporating a constraint solver is presented along with examples illustrating its power. / Master of Science

Operatorless Prolog text is LL(1) in nature and any standard LL parser generator tool can be used to parse it. However, the Prolog text that conforms to the ISO Prolog standard allows the definition of dynamic operators. Since Prolog operators can be defined at run-time, operator symbols are not present in the grammar rules of the language. Unless the parser generator allows for some flexibility in the specification of the grammar rules, it is very difficult to generate a parser for such text. In this thesis we discuss the existing parsing methods and their modified versions to parse languages with dynamic operator capabilities. Implementation details of a parser using Javacc as a parser generator tool to parse standard Prolog text is provided. The output of the parser is an “Abstract Syntax Tree” that reflects the correct precedence and associativity rules among the various operators (static and dynamic) of the language. Empirical results are provided that show that a Prolog parser that is generated by the parser generator like Javacc is comparable in efficiency to a hand-coded parser.