Programming languages for fifth generation computers

Fifth Generation languages and computers, for use in the 1990's, may be based on significantly different concepts than traditional computing. There are four major categories of computing, each consisting of a programming style and corresponding computer. These are: procedural languages (and control flow computers); object-oriented languages (and actor computers); functional languages (and data flow or reduction computers); and logic languages (and logic computers). In the future any of these categories of languages may become “main-stream” programming styles. In this paper we briefly present these novel programming languages and examine their advantages and disadvantages for programming.     

Evaluation of the Effectiveness of Prolog for a CAD Application

Fifth-generation computers will probably be based on logic programming languages like Prolog rather than on Fortran-type languages. Are such languages suitable to 3-D CAD applications?     

Architecture-independent parallel computation

The major parallel architecture classes are considered: single-instruction multiple-data (SIMD) computers, tightly coupled multiple-instruction multiple-data (MIMD) computers, hypercuboid computers and constant-valence MIMD computers. An argument that the PRAM model is universal over tightly coupled and hypercube systems, but not over constant-valence-topology, loosely coupled-system is reviewed, showing precisely how the PRAM model is too powerful to permit broad universality. Ways in which a model of computation can be restricted to become universal over less powerful architectures are discussed. The Bird-Meertens formalism (R.S. Bird, 1989), is introduced and it is shown how it is used to express computations in a compact way. It is also shown that the Bird-Meertens formalism is universal over all four architecture classes and that nontrivial restrictions of functional programming languages exist that can be efficiently executed on disparate architectures. The use of the Bird-Meertens formalism as the basis for a programming language is discussed, and it is shown that it is expressive enough to be used for general programming. Other models and programming languages with architecture-independent properties are reviewed     

Towards a logic programming methodology based on higher-order predicates

This paper outlines a logic programming methodology which applies standardized logic program recursion forms afforded by a system of general purpose recursion schemes. The recursion schemes are conceived of as quasi higher-order predicates which accept predicate arguments, thereby representing parameterized program modules. This use of higher-order predicates is analogous to higher-order functionals in functional programming. However, these quasi higher-order predicates are handled by a metalogic programming technique within ordinary logic programming. Some of the proposed recursion operators are actualizations of mathematical induction principles (e.g. structural induction as generalization of primitive recursion). Others are heuristic schemes for commonly occurring recursive program forms. The intention is to handle all recursions in logic programs through the given repertoire of higher-order predicates. We carry out a pragmatic feasibility study of the proposed recursion operators with respect to the corpus of common textbook logic programs. This pragmatic investigation is accompanied with an analysis of the theoretical expressivity. The main theoretical results concerning computability are

1. Primitive recursive functions can be re-expressed in logic programming by predicates defined solely by non-recursive clauses augmented with afold recursion predicate akin to the fold operators in functional programming.
2. General recursive functions can be re-expressed likewise sincefold allows re-expression of alinrec recursion predicate facilitating linear, unbounded recursion.

     

函数式逻辑语言的操作语义

函数式语言和逻辑语言在下列意义上是互补的,基于归约的函数式程序设计语言具有确定和懒惰求解等性质.但同时它又缺少诸如存在量化的变量以及部分数据结构等所希望的性质.相反,基于HORN子句逻辑和消解原理的逻辑程序设计语言允许存在量化的变量和部分数据结构但又缺少确定和懒惰求解的性质.从这个角度出发,把函数和逻辑程序设计语言结合成一种范型是很自然的,这种结合提供了一种比逻辑和函数语言表达能力更强的合一语言.提出了函数式逻辑语言的操作语义,同时表明这种操作语义在实践中是可见的.     

Foundations of declarative testing in arbitrary logic programming

Declarative testing is very important in logic program developments, as without testing no one can guarantee that every program is definitely correct, no matter how elegant and high-level the programming languages used. Unfortunately, the activity of declarative testing for logic programs (or even the ordinary testing for conventional programs) has received little attention. There is little formal theory of testing, and attempts to develop a methodology of testing are rare. In this paper, we provide a theoretical foundation for declarative testing in arbitrary first order logic programming using recursion theories. In particular, we present a theoretical analysis of three kinds of declarative testing method: I/O testing, I/Y testing, and X/Y testing for logic programs.     

Towards recursive block diagrams

Block diagrams have been recently successfully applied in programming safety critical control systems. This presentation investigates the interest of using recursion within this framework. First it identifies the necessary concepts for using recursion while remaining within the domain of real-time bounded memory, bounded response time systems and then it presents examples, which hopefully illustrate the interest of the approach.     

Complexity results for answer set programming with bounded predicate arities and implications

Answer set programming is a declarative programming paradigm rooted in logic programming and non-monotonic reasoning. This formalism has become a host for expressing knowledge representation problems, which reinforces the interest in efficient methods for computing answer sets of a logic program. The complexity of various reasoning tasks for general answer set programming has been amply studied and is understood quite well. In this paper, we present a language fragment in which the arities of predicates are bounded by a constant. Subsequently, we analyze the complexity of various reasoning tasks and computational problems for this fragment, comprising answer set existence, brave and cautious reasoning, and strong equivalence. Generally speaking, it turns out that the complexity drops significantly with respect to the full non-ground language, but is still harder than for the respective ground or propositional languages. These results have several implications, most importantly for solver implementations: Virtually all currently available solvers have exponential (in the size of the input) space requirements even for programs with bounded predicate arities, while our results indicate that for those programs polynomial space should be sufficient. This can be seen as a manifestation of the “grounding bottleneck” (meaning that programs are first instantiated and then solved) from which answer set programming solvers currently suffer. As a final contribution, we provide a sketch of a method that can avoid the exponential space requirement for programs with bounded predicate arities. Some results in this paper have been presented in preliminary form at KR 2004 [15].     

A lingua franca for concurrent logic programming

Two of the more important concurrent logic programming languages with nonflat guards are GHC and Parlog. They balance the requirements of having clean semantics and providing good control facilities rather differently, and their respective merits are compared and contrasted. Since concurrent logic programming would benefit from both, but neither language is able to express all the programs expressible in the other language, a lingua franca of these languages is defined and justified. A method is given for translating GHC and Parlog to and from it. The method preserves the arities and execution conditions of each clause. It enables a lingua franca implementation to support both languages transparently, and to provide a simple concurrent logic programming language suitable for programming in its own right     

Instant replay debugging of concurrent logic programs

One problem with debugging (committed choice) concurrent logic programs is that their behaviour may be non-deterministic, in that successive executions of the same program may produce different results. We describe a scheme, based on the ‘Instant Replay’ scheme developed for more conventional parallel languages, that allows us to reproduce the execution behaviour of a concurrent logic program on subsequent executions, so that the execution may be examined for debugging purposes. The properties of concurrent logic programming languages allow us to simplify our scheme greatly. We have demonstrated our scheme with KLIC, and KL1 on the PIM multiprocessors, but it can also be applied to other committed choice concurrent logic programming languages.     

: A distributed real-time logic language

This paper presents a new language that integrates the real-time and distributed paradigms within the framework of a concurrent logic language. Concurrent logic languages (CLLs) are capable of expressing concurrence, communication and nondeterminism in a natural way. That is, the intrinsic parallel semantics of the concurrent logic languages makes them well-suited for distributed programming. The proposed language is particularly suitable for loosely coupled systems and it contains mechanisms for distributed and real-time process control. A new execution model for concurrent logic languages is presented, which enables efficient distributed execution and real-time control. The model is introduced by giving an operational semantics for the language and the new model's implementation is discussed, including the definition of a new abstract machine and its implementation on a network of Unix workstations. Although the sequential core is not optimized, some previous results are discussed, showing the feasibility of the language's execution model for distributed real-time systems. The language is currently being used as the kernel language for a distributed simulation and validation tool for communication protocols.     

: A distributed real-time logic language

This paper presents a new language that integrates the real-time and distributed paradigms within the framework of a concurrent logic language. Concurrent logic languages (CLLs) are capable of expressing concurrence, communication and nondeterminism in a natural way. That is, the intrinsic parallel semantics of the concurrent logic languages makes them well-suited for distributed programming. The proposed language is particularly suitable for loosely coupled systems and it contains mechanisms for distributed and real-time process control. A new execution model for concurrent logic languages is presented, which enables efficient distributed execution and real-time control. The model is introduced by giving an operational semantics for the language and the new model's implementation is discussed, including the definition of a new abstract machine and its implementation on a network of Unix workstations. Although the sequential core is not optimized, some previous results are discussed, showing the feasibility of the language's execution model for distributed real-time systems. The language is currently being used as the kernel language for a distributed simulation and validation tool for communication protocols.     

POW! – The Programmers Open Workbench

This paper is about POW! the Programmers Open Workbench, a flexible and extensible programming environment for personal computers. POW! has been developed for programming lectures at high schools and universities and has been used successfully for the past few years. POW! is based on a modular architecture and can be adapted to many different programming languages and compilers. Until now there are compiler modules for the languages Oberon-2, C, C++ and Java. This text covers the structure and implementation of POW! It also compares POW! with other programming environments for personal computers.     

Parallel programming with logic languages: A survey

Formal properties of logic languages are largely studied; however, their impact on the practice of software design and programming is currently minimal. In this paper we survey some interesting representatives of the family of logic languages aiming at comparing the different capabilities they offer for designing and programming parallel systems. The logic languages Prolog, Aurora, Flat Concurrent Prolog, Parlog, GHC, and DeltaProlog were chosen, because a suitable set of relevant examples has been published, mostly by the language designers themselves. A number of sample programs is used to expose and compare the languages with respect to their object oriented programming capabilities for multiprocess coordination, interprocess communication, and resource management. Special attention is devoted also to metaprogramming as well, seen as a useful technique for specifying and building the operating environments of the languages themselves. The paper ends with a discussion on positive and negative features found comparing these languages, and indicates some guidelines to be followed in the design of new logic languages.     

Computer instruction for scholars in the humanities

Conclusion The common theme running through our discussion of both modes of adaptation to computer technology and problem areas in effective computer-assisted research is the relationship between computer expertise and scholarly research. Knowledge about computers is currently gained by social scientists and humanists in a wide variety of fashions. There are very few formal instructional programs, and most computer skills are obtained on the job. Although it is impossible at this stage to specify in detail either the content or the prerequisites for computer instructional programs for scholars in the social sciences and the humanities, I would recommend for consideration on the following general points. Investigators should have a basic understanding of the design and logic of computers. This knowledge will enable them to have a clearer concept of computers as symbol manipulating devices capable of both arithmetic and logical operations. However, very few investigators will ever use a computer at the level of its basic machine language. Therefore, investigators should learn to solve problems in higher level languages. I consider it essential that they learn at least two such languages, including both numerical and character manipulations. This kind of comprehensive instructional program will assist investigators in exercising greater control over the computer-assisted phases of research; it should allow them wider flexibility in selecting computer techniques appropriate for the research design; and finally, it will allow greater ease in adapting to future advances in computers.     

多种范型程序设计中递归问题的探讨

通过几种不同范型程序设计语言（Ada、Haskell．Prolog、Smalltalk）的简要介绍、分析和研究较常见的递归算法思想,从而了解不0同范型程序设计语言的程序设计风格、特点和解决问题的思路。     

Standard forms for rational linear arithmetic in constraint logic programming

Rational (resp. real) linear arithmetic is a computation domain included in several constraint logic programming languages. The decision procedure for this computation domain is usually based on a standard form for the representation of constraints. In this paper we show that the standard form used by the simplex algorithm for the representation of equations is not appropriate for deciding systems of linear constraints including disequations. We propose a new standard form, derived from it which overcomes the difficulty. We then show that the simplex algorithm can be extended to preserve this standard form through pivoting. These results provide the basis for an efficient and incremental procedure for rational linear arithmetic inside constraint logic programming languages.This paper is a revised and extended version of [19]. Part of this work was done while the authors were at ECRC, Munich (Germany).