A metalogic programming approach: language,semantics and applications

Abstract

This paper presents a logic programming language of novel conception, called Reflective Prolog, which allows declarative metaknowledge representation and metareasoning. The language is defined by augmenting pure Prolog (Horn clauses) with capabilities of self-reference and logical reflection. Self-reference is designed as a quotation device (a carefully defined naming relation) which allows the construction of metalevel terms that refer to object-level terms and atoms. Logical reflection is designed as an unquotation mechanism (a distinguished truth predicate) which relates names to what is named, thus extending the meaning of domain predicates. The reflection mechanism is embodied in an extended resolution procedure which automatically switches the context between levels. This implicit reflection relieves the programmer from having to explicitly deal with control aspects of the inference process. The declarative semantics of a Reflective Prolog definite program P is provided in terms of the least reflective Herbrand model of P, characterized by means of a suitable mapping defined over the Herbrand interpretations of P. The extended resolution is proved sound and complete with respect to the least reflective Herbrand model. By illustrating Reflective Prolog solutions to an organic set of problems, and by discussing the main differences with respect to other approaches to logic metaprogramming, we show that the proposed language deploys, within its field of action, greater expressive and inferential power than those available till now. The interpreter of the language has been fully implemented. Because of its enhanced power, logic semantics and working interpreter, Reflective Prolog is offered as a contribution toward making the declarative approach of logic programming applicable to the development of increasingly sophisticated knowledge-based systems.     

Static analysis of a parallel logic language based on the blackboard model

Shared Prolog is a parallel logic language based on the blackboard interpretation of logic programming. In such an interpretation a logic program is seen as a set of rules executed by a set of agents cooperating via a shared working memory called the blackboard. A distributed interpreter for Shared Prolog was implemented and described in another paper, where the blackboard was a centralized data structure. In this paper we show how the blackboard can be distributed using some static analysis techniques. The basic idea is to perform an abstract interpretation starting from the Shared Prolog operational semantics to generate data structures which represent possible interactions and links among agents. The resulting data structures are used to reduce the number of run time communication operations in an implementation distributed over a network of workstations.     

时序Agent程序设计语言TAOPLID的离线解释器

AOPLID是一种面向agent程序设计语言。本文旨在对AOPLID语言进行时序扩充,使之能表达并处理带时间参数的并发行动,基于离线方式下AOPLID程序的语义,用Prolog语言实现时序AOPLID语言(TAOPLID)的离线解释嚣。首先,我们对经典情境演算进行适当改造,使之能描述合时间变元的行动,因为持续行动一般可认为是具有瞬时开始行动和瞬时终止行动的过程,所以可以将一个持续动作分解为两个时间上互不相交的瞬时动作,再引入一个新的关系流刻画这两个瞬时动作的执行情况,从而可在扩充后的情境演算中表达带时间参数的并发行动。其次,为使TAOPLID离线解释嚣方便处理以集合方式表示的TAOPLID程序,设计并实现了TAOPLID预处理嚣,它将TAO—PLID程序的集合形式转换成Prolog子句形式,然后通过TAPOLID离线解释嚣对其解释生成一可执行的原子行动序列。     

A list processing language TAO with multiple programming paradigms

This paper describes an interpreter-centered list processing language TAO which supports the logic programming paradigm and the object-oriented programming paradigm together with the conventional procedural programming paradigm in the framework of the Lisp language. TAO allows the user to mix these programming paradigms in solving complicated and multifaceted AI problems. The fundamentals of these programing paradigms, namely, unification, message passing and function call can nest each other in an expression. Thus, the user can use the result of a function call or a message passing in a unification straightforwardly and vice versa. TAO also supports the concurrent programming. The implementation of the TAO interpreter on a Lisp machine called ELIS achieves a remarkable efficiency.     

Executing continuation semantics: A comparison

Several authors have suggested translating denotational semantics into prototype interpreters written in high-level programming languages to provide evaluation tools for language designers. These implementations have generally been understandable when restricted to direct denotational semantics. This paper considers using two declarative programming languages, Prolog and Standard ML, to implement an interpreter that follows the continuation semantics of a small imperative programming language, called Gull. Each of the two declarative languages presents certain difficulties related to evaluation strategies and expressiveness. The implementations are compared in terms of their ease of use for prototyping, their resemblance to the denotational definitions, and their efficiency.     

Specifying Byrd's Box Model with a Continuation Semantics

We give a formal specification of Byrd's box model. This specification is based on a on a Prolog operational semantics with continuations. We also show how this specification can be executed by a direct translation into λProlog, leading to a Prolog interpreter that produces execution traces. This interpreter can be used both to experiment various trace models to validate them. We have hence a formal framework to specify and prototype trace models.     

Oracle Semantics for Prolog

This paper proposes to specify semantic definitions for logic programming languages such as Prolog in terms of an oracle which specifies the control strategy and identifies which clauses are to be applied to resolve a given goal. The approach is quite general. It can be applied to Prolog to specify both operational and declarative semantics as well as other logic programming languages. Previous semantic definitions for Prolog typically encode the sequential depth-first search of the language into various mathematical frameworks. Such semantics mimic a Prolog interpreter in the sense that following the "leftmost" infinite path in the computation tree excludes computation to the right of this path from being considered by the semantics. The basic idea in this paper is to abstract away from the sequential control of Prolog and to provide a declarative characterization of the clauses to apply to a given goal. The decision whether or not to apply a clause is viewed as a query to an oracle which is specified from within the semantics and reasoned about from outside. This approach results in simple and concise semantic definitions which are more useful for arguing the correctness of program transformations and providing the basis for abstract interpretations than previous proposals.     

Translating a Linear Logic Programming Language into Java

There have been several proposals for logic programming language based on linear logic: Lolli [8], Lygon [7], LO [3], LinLog [2], Forum [11], HACL [10]. In these languages, it is possible to create and consume resources dynamically as logical formulas. The efficient handling of resource formulas is, therefore, an important issue in the implementation of these languages. Lolli, Lygon, and Forum are implemented as interpreter systems; Lolli is on SML and λProlog, Lygon is on Prolog, Forum is on SML, λProlog and Prolog. However, none of them have been implemented in Java.In this paper, we describe the Prolog Café ¹ system which translates a linear logic programming language called LLP to Java via the LLPAM [12] [5], an extension of the standard WAM [16] [1] for LLP. LLP is a superset of Prolog and a subset of Lolli. The main difference from the first implementation [4] is resource compilation. That is to say, resource formulas are compiled into closures which consist of a reference of compiled code and a set of bindings for free variables. Calling these resources is integrated with the ordinary predicate invocation.Prolog Café is portable to any platform supporting Java and easily expandable with increasing Java's class libraries. In performance, on average, Prolog Café generate 2.2 times faster code for a set of classical Prolog benchmarks compared with jProlog.     

A polymorphic type system for prolog

We describe a polymorphic type scheme for Prolog which makes static type checking possible. Polymorphism gives a good degree of flexibility to the type system, and makes it intrude very little on a user's programming style. The only additions to the language are type declarations, which an interpreter can ignore if it so desires, with the guarantee that a well-typed program will behave identically with or without type checking. Our implementation is discussed and we observe that the type resolution problem for a Prolog program is another Prolog (meta)program.     

High-level management of computation history for the design and implementation of a prolog system

We present the implementation of a Prolog system composed of interpreter and compiler. The originality of our work consists in the adoption of a new framework to realize the main components of the system. The framework relies on new mechanisms, called sleepers. With their help we have developed a complete Prolog interpreter in which all the control activities, from backtracking up to last-call optimization, are performed by the sleeper mechanism. We have also produced a Prolog compiler by using a philosophy and tactics that are completely independent of hardware constraints; it exploits an incremental and abstract implementation technique, based on a delayed non-local execution protocol. Our approach to Prolog system implementation has been extremely useful both in terms of software design and overall performance.     

Object oriented programming in Concurrent Prolog

It is shown that the basic operations of object-oriented programming languages — creating an, object, sending and receiving messages, modifying an object’s state, and forming class-superclass hierarchies — can be implemented naturally in Concurrent Prolog. In addition, a new object-oriented programming paradigm, called incomplete messages, is presented. This paradigm subsumes stream communication, and greatly simplifies the complexity of programs defining communication networks and protocols for managing shared resources. Several interesting programs are presented, including a multiple-window manager. All programs have been developed and tested using the Concurrent Prolog interpreter described in.¹⁾     

A framework for execution monitoring in icon

Execution monitors are widely used during software development for tasks that require an understanding of program behavior, such as debugging and profiling. The Icon programming language has been enhanced with a framework that supports execution monitoring. Under the enhanced translator and interpreter, neither source modification nor any special compiler command-line option is required in order to monitor an Icon program. Execution monitors are written in the source language, instead of the implementation language. Performance, portability, and detailed access to the monitored program's state are achieved using a coroutine model and dynamic loading rather than the separate-process model employed by many conventional monitoring systems.     

A visual debugger for pure Prolog

This work involves the design and coding of an interpreter for pure Prolog and building a visual debugger for it. Most of the available Prolog interpreters contain some tracing facilities. They do not incorporate, however, a comprehensive visual debugger. The interpreter performs the operations of parsing, unification, resolution, and search in a state-space representation of the Prolog program. The visual debugger incorporates the graphical visualization and the manipulation of the SLD resolution tree. The user visualizes the execution of a pure Prolog program and interacts with the program inside a windowing environment. The program execution may be viewed without interruption or the execution can be stopped at any moment in time. At this point the “snapshot” can be scrutinized with the help of break-points and data displays. This software aims itself to those who wish to observe the actual process of predicate unification, substitution, resolution and goal matching in a Prolog program and to visually interact with the interpreter using a highly friendly and pleasing user interface. An advanced feature, referred to as debugging on the tree, provides the user with the ability to insert break-points directly on the SLD tree, to choose the path of execution, and change the search mode. The resultant search algorithm can be a mixture of depth-first and breadth-first search, avoiding infinite search paths.     

Result sequences

Expression evaluation in conventional programming languages may be viewed as a simplification of expression evaluation in the Icon programming language. The evaluation of an expression in Icon may yield a sequence of results. Goal-directed evaluation causes expressions to produce these results in an attempt to produce the successful evaluation of an enclosing expression. There are control operations that operate on result sequences. The study of expression evaluation in Icon therefore is more interesting than it is in most programming languages. This paper introduces a notation for result sequences and shows how it can be used to describe the static aspects of expression evaluation. Equivalences among control operations and expressions are demonstrated.     

A fact dependency system for the logic programmer

We describe experimental work in logic programming for architects, leading to the setting up of a fact dependency system. The system operates as an interpreter of the user's instructions, storing his decision and the conclusions inferred from those decisions. Consistency from a user's point of view is automatically maintained. A separate introduction to the Prolog logic programming language is appended to this paper.     

Definitional Interpreters for Higher-Order Programming Languages

Higher-order programming languages (i.e., languages in which procedures or labels can occur as values) are usually defined by interpreters that are themselves written in a programming language based on the lambda calculus (i.e., an applicative language such as pure LISP). Examples include McCarthy's definition of LISP, Landin's SECD machine, the Vienna definition of PL/I, Reynolds' definitions of GEDANKEN, and recent unpublished work by L. Morris and C. Wadsworth. Such definitions can be classified according to whether the interpreter contains higher-order functions, and whether the order of application (i.e., call by value versus call by name) in the defined language depends upon the order of application in the defining language. As an example, we consider the definition of a simple applicative programming language by means of an interpreter written in a similar language. Definitions in each of the above classifications are derived from one another by informal but constructive methods. The treatment of imperative features such as jumps and assignment is also discussed.     

Flat Concurrent Prolog on transputers

Flat Concurrent Prolog (FCP) is a general purpose logic programming language designed for concurrent programming and parallel execution. Staring with a concise introduction of the language and its underlying computational model we describe how to implement a distributed FCP interpreter on a transputer environment using OCCAM. Basic techniques we used for exploiting and controlling parallelism are explained in terms of an abstract architecture. The result of mapping this abstract model on transputers is presented as concrete architecture. Substantial design issues are considered in detail.     

Compiling OR-parallelism into AND-parallelism

This paper suggests a general method for compiling OR-parallelism into AND-parallelism. An interpreter for an AND/OR-parallel language written in the AND-parallel subset of the language induces a source-to-source transformation from the full language into the AND-parallel subset. This transformation can be identified and implemented as a special purpose compiler or applied using a general purpose partial evaluator. The method is demonstrated to compile a variant of Concurrent Prolog into an AND-parallel subset of the language called Flat Concurrent Prolog (FCP). It is also shown applicable to the compilation of OR-parallel Prolog to FCP. The transformation identified is simple and efficient. The performance of the method is discussed in the context of programming examples. These compare well with conventionally compiled Prolog programs.