UCB策略在Prolog中的应用

Prolog(Programming in Logic)程序语言是一种逻辑程序设计语言.它是在逻辑学理论基础上建立起来的并广泛应用在人工智能研究中.这几十年已经出现了各具特色的Prolog编译器,而且各种编译器也都很成功.虽然在现阶段已经出现了各种版本Prolog编译器,但是Prolog编译器的发展空间还是很大.本文先通过现代Prolog编译器的不足,介绍了新Prolog编译器的特点,然后简单叙述了Prolog编译器词法分析和语法分析的过程,最后介绍了UCB策略.     

High-performance logic programming with the Aquarius Prologcompiler

Aquarius Prolog, a high performance compiler designed and built to test the hypothesis that Prolog can be implemented as efficiently as an imperative language by compiling the more powerful features of logic programming only where they are needed, and then only in the simplest form, is described. The authors begin with some background on logic programming and then discuss the Prolog language in more detail. They present an overview of their compiler, giving its structure and the principles underlying its high performance. They compare their system with two popular high-performance commercial systems and with two implementations of C and conclude with an overview of ways to extend this work     

QD-Janus: A sequential implementation of Janus in Prolog

Janus is a language designed for distributed constraint programming. This paper describes QD-Janus, a sequential implementation of Janus in Prolog. The compiler uses a number of novel analyses and optimizations to improve the performance of the system. The choice of Prolog as the target language for a compiler, although unusual, is motivated by the following: (i) the semantic gap between Janus and Prolog is much smaller than that between Janus and, say, C or machine language—this simplifies the compilation process significantly, and makes it possible to develop a system with reasonable performance fairly quickly; (ii) recent progress in Prolog implementation techniques, and the development of Prolog systems whose speeds are comparable to those of imperative languages, indicates that the translation to Prolog need not entail a significant performance loss compared to native code compilers; and (iii) compilation to Prolog can benefit immediately from a significant body of work on, and implementations of, parallel Prolog systems. Our experience indicates that translation of logic programming languages to Prolog, accompanied by the development of good program analysis and optimization tools, is an effective way to quickly develop flexible and portable implementations with good performance and low cost.     

Machine independent AND and OR parallel execution of logicprograms. II. Compiled execution

For pt.I. see ibid., p. 170-80. In pt.I, we presented a binding environment for the AND and OR parallel execution of logic programs. This environment was instrumental in rendering a compiler for the AND and OR parallel execution of logic programs machine independent. In this paper, we describe a compiler based on the Reduce-OR process model (ROPM) for the parallel execution of Prolog programs, and provide performance of the compiler on five parallel machines: the Encore Multimax, the Sequent Symmetry, the NCUBE 2, the Intel i860 hypercube and a network of Sun workstations. The compiler is part of a machine independent parallel Prolog development system built on top of a run time environment for parallel programming called the Chare kernel, and runs unchanged on these multiprocessors. In keeping with the objectives behind the ROPM, the compiler supports both on and independent AND parallelism in Prolog programs and is suitable for execution on both shared and nonshared memory machines. We discuss the performance of the Prolog compiler in some detail and describe how grain size can be used to deliver performance that is within 10% of the underlying sequential Prolog compiler on one processor, and scale linearly with increasing number of processors on problems exhibiting sufficient parallelism. The loose coupling between parallel and sequential components makes it possible to use the best available sequential compiler as the sequential component of our compiler     

The design of a pascal compiler

The development of a compiler for the programming language PASCAL¹ is described in some detail. Design decisions concerning the layout of program and data, the organization of the compiler including its syntax analyser, and the over-all approach to the project are discussed. The compiler is written in its own language and was implemented for the CDC 6000 computer family. The reader is expected to be familiar with Reference 1.     

A prolog constraint handling rules compiler and runtime system

The most recent and advanced implementation of constraint handling rules (CHR) is introduced in a logic programming language. The Prolog implementation consists of a runtime system and a compiler. The runtime system utilizes attributed variables for the realization of the constraint store with efficient retrieval and update mechanisms. Rules describing the interactions between constraints are compiled into Prolog clauses by a compiler, the core of which comprises a small number of compact code generating templates in the form of definite clause grammar rules.     

Extending the power of Pascal's external procedure mechanism

The CDC Pascal 6000–3.4 compiler allows external procedures to be designed and compiled separately. Such a mechanism strongly enhances the extensibility of the language. However, the external procedures are restricted to having ‘fixed’ parameter list only and is therefore unsuitable for designing I/O routines. This paper describes a cheap way to release the restriction thereby extending the power of the external procedure mechanism significantly. The method is to include a new compiler option, called the Z option, to the existing Pascal compiler. The Z option allows a user to breach the strong binding between format and actual parameters while not diminishing program reliability. The main advantage is that the I/O system can now be isolated from the compiler. I/O features can be added and removed easily as with other library routines.     

An empirical study of FORTRAN programs

A sample of programs, written in FORTRAN by a wide variety of people for a wide variety of applications, was chosen ‘at random’ in an attempt to discover quantitatively ‘what programmers really do’. Statistical results of this survey are presented here, together with some of their apparent implications for future work in compiler design. The principal conclusion which may be drawn is the importance of a program ‘profile’, namely a table of frequency counts which record how often each statement is performed in a typical run; there are strong indications that profile-keeping should become a standard practice in all computer systems, for casual users as well as system programmers. This paper is the report of a three month study undertaken by the author and about a dozen students and representatives of the software industry during the summer of 1970. It is hoped that a reader who studies this report will obtain a fairly clear conception of how FORTRAN is being used, and what compilers can do about it.     

A compiler infrastructure for embedded heterogeneous MPSoCs

Programming heterogeneous MPSoCs (Multi-Processor Systems on Chip) is a grand challenge for embedded SoC providers and users today. In this paper, we argue the need for and significance of positioning the language and tool design from the perspective of practicality to address this challenge. We motivate, describe and justify such a practical design of a compilation framework for heterogeneous MPSoCs targeting the domain of streaming applications, named MAPS (MPSoC Application Programming Studio). MAPS defines a clean, light-weight C language extension to capture streaming programming models. A retargetable source-to-source compiler is developed to provide key capabilities to construct practical compilation frameworks for real-world, complex MPSoC platforms. Our results have shown that MAPS is a promising compiler infrastructure that enables programming of heterogeneous MPSoCs and increases productivity of MPSoC software developers.     

Prolog versus Kee — A case study

The selection of the software development tool for the development of an expert system is a difficult and often disputed decision. This paper describes a comparison of a knowledge engineering tool, Kee, and a general purpose language, Prolog, on concrete and real life example from AGATHA, an electronic circuit board diagnosis expert system.Prolog is a high-level programming language with flexible and powerful inference mechanisms. Kee is a big tool that supports a frame-based knowledge representation, an object-oriented programming style and a built-in rule system. It also offers a window environment suitable for rapid development of user-interface prototypes.Prolog's representation is more succinct, implicit and uses problem specific predicates and therefore leaves more room for personal programming styles. Kee is more verbose, explicit and uses standard templates. The maintainability of a Prolog implementation relies heavily on good documentation. In Kee, the unavoidable ‘escapes to Lisp’ require a maintainer to be fluent in Kee and Lisp.Both Prolog and Kee require a considerable investment in learning time.     

网络处理器的编译器聚集

描述了针对异构多核处理器的编译器Shangri-la基于Whirl2c构建统一编译后端框架采用的编译器的聚集技术,介绍了它采用的地址转换方法来解决聚集时不同寻址方式面临的指针共享问题。这些技术的运用使Shangri-la很好地整合了两种不同内核的编译工作。这种统一的编译平台使得网络程序员从传统繁琐的网络程序编写方式中解放出来。     

Specification,Verification and Prototyping of an Optimized Compiler

This paper generalizes an algebraic method for the design of a correct compiler to tackle specification and verification of an optimized compiler. The main optimization issues of concern here include the use of existing contents of registers where possible and the identification of common expressions. A register table is introduced in the compiling specification predicates to map each register to an expression whose value is held by it. We define different kinds of predicates to specify compilation of programs, expressions and Boolean tests. A set of theorems relating to these predicates, acting as a correct compiling specification, are presented and an example proof within the refinement algebra of the programming language is given. Based on these theorems, a prototype compiler in Prolog is produced.     

Computational improvements in Prolog applications by predicatevariable pointers

The programming tradeoffs between structure-oriented and clause-oriented operations on data structures in Prolog are limited in current implementations because the assertion of clauses that include uninstantiated variables destroys any binding between these variables and those with which they are unified in the execution of the program. Built-in predicates for Prolog that allow one to assert predicate variables pointers, which are constants, rather than uninstantiated variables, are presented. The author shows: the possible performance benefits of clause-oriented implementations of data structures over equivalent structure-oriented versions, the logical implications of the proposed built-in predicates, and their practical significance by integrating them in C-Prolog and evaluating the two different implementations of the symbol table dictionary in D.H.D. Warren's pseudo-Pascal compiler example     

Throw-away compiling

A method of compiling called ‘throw-away compiling’ is presented. This combines the merits of compilation and interpretation. If enough storage is available for a program, it can be compiled in the normal way; if not, the program is stored in a concise intermediate form and compiled dynamically at run-time, making use of whatever storage is available. When this storage runs out, the previously compiled code is thrown away and the storage is re-used. The technique is specially suitable for small machines, especially those without virtual memory. The paper explains the advantages and disadvantages of throw-away compiling, and describes a project where a throw-away compiler was implemented and tested for performance.     

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.     

The robust implementation of sequence-controlled iteration

Many Pascal compilers generate incorrect code for statements. The trap that catches many implementors, whereby overflow is generated incorrectly, is explained and means for avoiding it are discussed (with attention to cost). Most common languages have a similar construct in which iteration is ‘controlled’ by a sequence of values in that a variable takes on successive values of the sequence for the several executions of the ‘body’. Often, the size step is not restricted to plus-or-minus one (as in Pascal) and the correctness situation cannot be characterized in such black and white terms. Typically, there is a range of behaviours that are valid and the compiler writer is able to choose a compromise between time-space overheads and avoidance of unnecessary overflow indications; we describe the latter behaviour as robust. We present techniques for implementation appropriate to several languages and direct comments at language designers warning against both ignoring and overestimating the cost of robustly implementing iteration statements with arbitrary step size. Lastly, we criticize the design of instructions available in some machines, ostensibly to support the implementation of such sequence controlled iteration statements.     

MUSYS: Software for an electronic music studio

MUSYS is a system of programs used to create electronic music at the computer studio of Electronic Music Studios, London. This paper describes the programming language employed by composers, and the implementation of its compiler and of other programs in the system. It is shown that by the use of a macrogenerator, an efficient and useful system can be built from simple software on a small computer.     

Compiler technology for machine-indepenent parallel programming

Historically, the principal achievement of compiler technology has been to make it possible to program in a high-level, machine-independent style. The absence of compiler technology to provide such a style for parallel computers is the main reason these systems have not found widespread acceptance. This paper examines the prospects for machine-independent parallel programming, concentrating on Fortran D and High Performance Fortran, which support machine-independent expression of “data parallelism.”     

The costs and benefits of lazy interactive input in pascal

The programming language Pascal was designed and implemented in a non-interactive programming environment. This paper surveys proposals for incorporating interaction into Pascal, and focuses on a scheme known as ‘lazy evaluation’. It presents and compares performance measurements of two Pascal run-time systems for the same compiler; a buffered, non-interactive version, and a modification of that system to support lazy evaluation.     

可视化集成软件环境VISE的研究与实现

可视化程序设计技术和软件集成技术是当今世界上最活跃的计算机应用技术之一,而编译理论的实现技术又是计算机应用的一个重要领域。文章着重介绍运用三种技术开发成功的可视化集成软件环境ＶＩＳＥ（ＶｉｓｕａｌＩｎｔｅｇｒａｔｅｄ Ｓｏｆｔｗａｒｅ Ｅｎｖｉｒｏｎｍｅｎｔ,简称ＶＩＳＥ）的设计背景及其主要功能。