Specification and correctness proof of a WAM extension with abstract type constraints

We provide a mathematical specification of an extension of Warren's Abstract Machine (WAM) for executing Prolog to type-constraint logic programming and prove its correctness. Our aim is to provide a full specification and correctness proof of a concrete system, the PROTOS Abstract Machine (PAM), an extension of the WAM by polymorphic order-sorted unification as required by the logic programming language PROTOS-L.In this paper, while leaving the details of the PAM's type constraint representation and solving facilities to a sequel to this work, we keep the notion of types and dynamic type constraints abstract to allow applications to different constraint formalisms like Prolog III or CLP(R). This generality permits us to introduce modular extensions of Börger's and Rosenzweig's formal derivation of the WAM. Since the type constraint handling is orthogonal to the compilation of predicates and clauses, we start from type-constraint Prolog algebras with compiled AND/OR structure that are derived from Börger's and Rosenzweig's corresponding compiled standard Prolog algebras. The specification of the type-constraint WAM extension is then given by a sequence of evolving algebras, each representing a refinement level, and for each refinement step a correctness proof is given. Thus, we obtain the theorem that for every such abstract type-constraint logic programming system L, every compiler to the WAM extension with an abstract notion of types which satisfies the specified conditions, is correct.The first author was partially funded by the German Ministry for Research and Technology (BMFT) in the framework of the WISPRO Project (Grant 01 IW 206). He would also like to thank the Scientific Center of IBM Germany where the work reported here was started.     

Emerald: A general-purpose programming language

Emerald is a general-purpose language with aspects of traditional object-oriented languages, such as Smalltalk, and abstract data type languages, such as Modula-2 and Ada. It is strongly typed with a non-traditional object model and type system that emphasize abstract types, allow separation of typing and implementation, and provide the flexibility of polymorphism and subtyping with compile-time checking. This paper describes the Emerald language and its programming methodology. We give examples that demonstrate Emerald's features, and compare and contrast the Emerald approach to programming with the approaches used in other similar languages.     

The systems programming language,Malus

This paper reports on the design and development of a high level language, Malus, for use in implementing a time-sharing system. Emphasized are the ways that the language and its compiler accommodate the specialized requirements of systems programming and programmers. Among these are the need to generate highly efficient object code, to allow inter-programmer communication by program self-documentation, and to define and organize system tables and data. In addition, the Malus compiler is highly modular; thus the language may be modified or augmented in response to user needs unforeseen during langauge design. Systems programs cannot be machine independent and Malus allows explicit control of emitted code when an application requires particular efficiency or use of privileged instructions. There is also a facility allowing nested redefinition of identifiers. Efficient storage management and data access is effected by the availability of based structures, a register storage class and built-in functions to facilitate their use. Malus is evaluated both in terms of some general criteria for systems implementation languages and by an appraisal of user reactions. While this assessment shows a few areas where the language might be improved, it is felt that Malus is a valuable and effective tool for systems implementation.     

On the design of a special-purpose scientific programming language

Observations on the design of the special-purpose scientific programming language SL/1 are presented. SL/1 is intended for applications programming of the Control Data Corporation Cyber 203, a very high-performance vector processor, which is mainly used for scientific computation. The language design has been heavily influenced by the hardware characteristics of this machine and the needs of the Cyber 203 user community. Various aspects of the design of SL/1 are discussed and measurements of their use are presented. In addition, unexpected similarities between the resulting design of SL/1 and the design of FORTRAN are examined and several reasons for the continued widespread use of FORTRAN are suggested.     

PEP: An interactive programming system with an Algol-like programming language

PEP (Program Editor and Processor) is an interactive programming system based on an Algol-like language. It is intended to replace BASIC as a system for interactive program development on small computers (LSI-11). The language processed by the system allows declaration of variables, constants and procedures; it has structured statements for conditional and repetitive execution of program parts. We describe design and implementation of the system and give our impressions after 1 year of experience with the system.     

An Improved Bottom-up Method for Implementing Equational Programming Language

Equational programming language (EP) is a novel intelligence language.This paper describes our EP system based on equational logic.Its execution mechanism is pattern matching.The paper focuses the discussion on the improvement to bottom-up tree pattern matching.The new bottom-up method shows high execution efficiency.     

A new programming paradigm for engineering design software

Currently available programming and database systems are insufficient for engineering applications. The authors contend that a logical progression from a formal conceptual model of the engineering domain to a computational model will lead to new programming paradigms capable of directly supporting engineering applications in a rigorous, concise manner. A formal domain model devised by the authors, theHybrid Model (HM) of design information, is briefly introduced. It is an extension of axiomatic set theory and is discussed in detail elsewhere. HM forms the basis ofDesigner, a prototype-based object-oriented programming language supporting a signature-based canonical message-passing mechanism and multiple inheritance. Designer is implemented using the Scheme programming language. Because Designer satisfies a formal conceptual model, and because it is based on a formally specified language, its robustness and logical validity are superior to those of other languages not founded on formal principles. Designer combines concepts of functional and object-oriented programming to provide the formal rigor and flexibility to capture the complex and strongly interrelated information that designers use. Examples demonstrate how Designer represents design information. The results of the authors' research indicate that Designer can capture design information (including aspects of functional requirements and design intent) effectively and efficiently.     

Using the programming walkthrough to aid in programming language design

The programming walkthrough is a method for assessing how easy or hard it will be for users to write programs in a programming language. It is intended to enable language designers to identify problems early in design and to help them choose among alternative designs. We describe the method and present experience in applying it in four language design projects. Results indicate that the method is a useful supplement to existing design approaches.     

Mixed language programming

Subroutines for numerical computation have in the past been written mainly in Fortran and in Algol 60, whereas most programming in the future is expected to be in more advanced languages, for example in Ada. It seems to be a great waste if it will become necessary to convert all existing numerical software into the new languages. What is needed is a facility to include subroutines written in the old languages into programs being written in the newer languages. In this paper an automatic procedure to facilitate the use of mixed languages is suggested, the purpose of the paper is to indicate the desirability for providing the required facilities, and to encourage discussion and further research in the area of mixed language programming.     

An optimizing compiler for the icon programming language

Compiling code for the Icon programming language presents several challenges, particularly in dealing with types and goal-directed expression evaluation. In order to produce optimized code, it is necessary for the compiler to know much more about operations than is necessary for the compilation of most programming languages. This paper describes the organization of the Icon compiler and the way it acquires and maintains information about operations. The Icon compiler generates C code, which makes it portable to a wide variety of platforms and also allows the use of existing C compilers for performing routine optimizations on the final code. A specially designed implementation language, which is a superset of C, is used for writing Icon's run-time system. This language allows the inclusion of information about the abstract semantics of Icon operations and their type-checking and conversion requirements. A translator converts code written in the run-time language to C code to provide an object library for linking with the code produced by the Icon compiler. The translation process also automatically produces a database that contains the information the Icon compiler needs to generate and optimize code. This approach allows easy extension of Icon's computational repertoire, alternate computational extensions, and cross compilation.     

Experience from the standardization of the SIMULA programming language

SIMULA is a high-level language comparable in power to PL/I or ALGOL 68. SIMULA compilers exist for eight different computer series. SIMULA is standardized by a committee mainly consisting of one representative for each implementation. This has given good compatibility between the implementations and the efficient handling of standards problems. The fact that the SIMULA language is defined in such a way that there are no undefined constructs in the language has also helped compatibility and standardization.     

The consequences of one's first programming language

After seeing many programs written in one language, but with the style and structure of another, I conducted an informal survey to determine whether this phenomenon was widespread and to determine how much a programmer's first programming language might be responsible. This paper discusses my observations, gives informal results of the survey and suggests the need for a more formal study.     

The programming language superpascal

This paper defines SuperPascal—a secure programming language for publication of parallel scientific algorithms. SuperPascal extends a subset of IEEE Standard Pascal with deterministic statements for parallel processes and synchronous message communication. A parallel statement denotes parallel execution of a fixed number of statements. A forall statement denotes parallel execution of the same statement by a dynamic number of processes. Recursive procedures may be combined with parallel and forall statements to define recursive parallel processes. Parallel processes communicate by sending typed messages through channels created dynamically. SuperPascal omits ambiguous and insecure features of Pascal. Restrictions on the use of variables enable a single-pass compiler to check that parallel processes are disjoint, even if the processes use procedures with global variables.     

C语言程序设计教学方法的现实探微

随着我国经济的快速发展,我国教育事业在发展过程中面临着新的挑战。C语言程序设计课程,是我国计算机课程中一个重要的组成部分,具有广泛的适用性与实践性;C语言程序设计课程教学效率与质量的提升,能够一定程度上促进我国计算机课程的总体发展,有效地培养学生对于计算机问题的分析与解决能力,提高学生的实践技能,科学合理的C语言程序设计教学方法,是确保教学效率与质量提升的关键,C语言程序设计课程教师应当充分重视教学方法的运用,根据实际情况选择与更变教学方法。     

UCB策略在Prolog中的应用

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

A programming language engineered for beginners

As the complexity and size of programs increase, the programmer is challenged with the task of organizing his program in a manner which will enhance intellectual manageability. Thus, the structure and style are critical in regards to writing programs and verifying their correctness. In recent years, considerable emphasis has been placed on the correctness of programs and techniques for engineering them to be correct. However, more emphasis should be placed on designing languages which facilitate constructing correct programs. In an effort to partially address this problem, a language is described which permits users the convenient development of well-structured programs that are easy to read and understand, easy to correct (debug) and modify, and easy to verify the correctness of the program. The language presented permits the use of decision tables for expressing complex logic.     

Constant-space quantum interactive proofs against multiple provers

We present upper and lower bounds of the computational complexity of the two-way communication model of multiple-prover quantum interactive proof systems whose verifiers are limited to measure-many two-way quantum finite automata. We prove that (i) the languages recognized by those multiple-prover systems running in expected polynomial time are exactly the ones in NEXP, the nondeterministic exponential-time complexity class, (ii) if we further require verifiers to be one-way quantum finite automata, then their associated proof systems recognize context-free languages but not beyond languages in NE, the nondeterministic linear exponential-time complexity class, and moreover, (iii) when no time bound is imposed, the proof systems become as powerful as Turing machines. The first two results answer affirmatively an open question, posed by Nishimura and Yamakami [J. Comput. System Sci. 75 (2009) 255–269], of whether multiple-prover quantum interactive proof systems are more powerful than single-prover ones. Our proofs are simple and intuitive, although they heavily rely on an earlier result on multiple-prover classical interactive proof systems of Feige and Shamir [J. Comput. System Sci. 44 (1992) 259–271].     

Fooling the user of a programming language

Fooling the user' of a programming language by ‘natural’ constructions can cause completely unpredictable reliability defects in software systems. Numerous examples show the extent of the problem. Two methods of overcoming it are presented: simple languages devoid of user-fooling powers, and explication languages to accompany the more powerful languages.