Sequential algorithms on concrete data structures

We provide a sequential denotational semantics for sequential programming languages, based on a new notion of sequential algorithm on the Kahn-Plotkin concrete data structures. Intuitively an algorithm may be seen either as a concrete object—a “program” in a simple output-driven language — or as an abstract object — the pair of a sequential function and of a computation strategy for it. The concrete and abstract presentations are equivalent, as shown by a representation theorem. The algorithms form a cartesian closed category with straightforward solutions to recursive domain equations. Hence they may replace functions in the denotational semantics of any sequential language. An applicative programming language based on sequential algorithms is presented in a companion paper.     

Teaching problem solving and structured programming in FORTRAN

This paper describes an approach to teaching problem solving in an introductory programming course using the FORTRAN language. The course is oriented around a set of problems which are used to illustrate a problem solving methodology. Three pedagogic aids (data table, flow diagram, and program system chart) and two control structure extensions to the FORTRAN language are used in order to provide a more convenient framework in which students can practice good problem solving and programming techniques. The control structure extensions facilitate structured programming in FORTRAN. The use of the control structures and the pedagogic aids is illustrated in the solution of a simple statistics problem: the benefits derived from using these aids are also discussed.     

DTL: A language for the design and implementation of concurrent programs as structured networks

DTL is an experimental programming language which has developed from an investigation of data structured design methods and data driven programming techniques. A DTL program is derived from a specification of the structure of its valid input and output languages. The program function is defined as a translation between these languages. A complex translation can be hierarchically structured into a network of simpler translations by stepwise refinement.     

一种实用的读C程序方法

C语言是一门结构化程序设计语言,读程序能力的提高对于学好C语言很有帮助,对培养程序设计思想也很重要,只有读程序的能力提高了,才能写出好的程序来。列表分析法可以记录下程序执行过程中变量值的变化,从而很从容地读懂C程序。     

一种实用的读C程序方法

C语言是一门结构化程序设计语言，读程序能力的提高对于学好C语言很有帮助，对培养程序设计思想也很重要，只有读程序的能力提高了，才能写出好的程序来。列表分析法可以记录下程序执行过程中变量值的变化，从而很从容地读懂C程序。     

Object-oriented programming with class dictionaries

A class dictionary defines all data structures that appear in a program as well as a language for describing data specified by the data structures. We demonstrate that class dictionaries are ideal for simplifying object-oriented programming. Our class dictionary-based approach to object-oriented programming is independent of any particular programming language, so it is applicable to a large variety of object-oriented systems. The experience in designing and using over one hundred class dictionaries has resulted in a set of useful design techniques. This novel approach to object-oriented programming makes interesting links between language design, data structure design, and data-base design.     

COMAL 80—Adding structure to BASIC

BASIC has developed almost lo the status of a standard language in many areas of educational computing, despite strong criticism by theoreticians and considerable weaknesses (in particular, the lack of facilities for “structured programming”) which are handicaps when writing all but the most elementary programs.Some of the features of BASIC which have led to its considerable popularity are examined. These features together with the widespread use of BASIC suggest that if a more appropriate introductory programming language is to be developed and accepted it must build on rather than replace BASIC.A programming language is described which was designed to remedy the weaknesses of BASIC by adding structured constructs and other desirable improvements, whilst retaining its major features and overall spirit.This language—known as COMAL 80—was developed in Denmark and is proposed as a significant yet realistic improvement on BASIC as a programming language for schools.     

Record manipulation in prolog

Prolog is a relatively new programming language that has proved excellent for symbolic computation. However, Prolog was not specifically designed for industrial scale work and it lacks some standard features that are useful for reading, maintaining and debugging large programs. In particular, Prolog has no record mechanism, and programs often require major changes when data structures are modified. The record is a standard data abstraction concept that improves the robustness of programs. The main advantage in using records is that data structures can be modified and extended with minimal repercussion to program code. Furthermore, the use of significant names to access data fields means that the intent of code is generally clearer. We present a set of primitive operators that support a readable and robust programming style for the manipulation of record data structures in standard Prolog. The proposal covers both simple and imbricated record types and handles selective modification of records cleanly. We also treat property lists and records in a uniform way. These benefits are achieved with minimal overhead while retaining the traditional Prolog non-deterministic style.     

Effective strategic programming for Java developers

In object programming languages, the Visitor design pattern allows separation of algorithms and data structures. When applying this pattern to tree‐like structures, programmers are always confronted with the difficulty of making their code evolve. One reason is that the code implementing the algorithm is interwound with the code implementing the traversal inside the visitor. When implementing algorithms such as data analyses or transformations, encoding the traversal directly into the algorithm turns out to be cumbersome as this type of algorithm only focuses on a small part of the data‐structure model (e.g., program optimization). Unfortunately, typed programming languages like Java do not offer simple solutions for expressing generic traversals. Rewrite‐based languages like ELAN or Stratego have introduced the notion of strategies to express both generic traversal and rule application control in a declarative way. Starting from this approach, our goal was to make the notion of strategic programming available in a widely used language such as Java and thus to offer generic traversals in typed Java structures. In this paper, we present the strategy language SL that provides programming support for strategies in Java. Copyright © 2012 John Wiley & Sons, Ltd.     

Parameterized Programming

Parameterized programming is a powerful technique for the reliable reuse of software. In this technique, modules are parameterized over very general interfaces that describe what properties of an environment are required for the module to work correctly. Reusability is enhanced by the flexibility of the parameterization mechanism proposed here. Reliability is further enhanced by permitting interface requirements to include more than purely syntactic information. This paper introduces three new ideas that seem especially useful in supporting parameterized programming: 1) theories, which declare global properties of program modules and interfaces; 2) views, which connect theories with program modules in an elegant way; and 3) module expressions, a kind of general structured program transformation which produces new modules by modifying and combining existing modules. Although these ideas are illustrated with some simple examples in the OBJ programming language, they should also be taken as proposals for an Ada¹ library system, for adding modules to Prolog, and as considerations for future language design efforts. OBJ is an ultra-high level programming language, based upon rewrite rules, that incorporates these ideas, and many others from modern programming methodology.     

TuringTool: a user interface to aid in the software maintenancetask

TuringTool is a source program viewing and editing system specifically designed to support the software maintenance task. TuringTool bases all of its views of the program on a single comprehensive viewing paradigm borrowed from program development environments: source text elision. It is shown how this paradigm can be used to represent several kinds of views appropriate to the maintenance of large source programs, including structural views and nonstructural views appropriate to the maintenance task and how it can be extended to allow dynamic creation of complex programmer-specified views using simple set theoretic operators to combine the effects of several views into one. The system exploits the highly structured nature of the Turing programming language to allow seamless viewing of programs consisting of many separately compiled source modules as one uniform source     

Staple,an experimental structured programming language

STAPLE is a structured programming language with nested block structure in the source language to indicate flow of control. The semantics of the non-control structures are essentially the same as FORTRAN. The design goals were an easily implemented, easily modified tool for experiments and demonstrations of structured versus unstructured programming techniques.     

The development of complex GPSS programs: An empirical assessment

The underlying theme of this paper is that highly disciplined and well thought out modeling and programming practices are as important to the successful development of a complex simulation program in a structured language, such as GPSS, as they are in an unstructured language, such as FORTRAN. To support this contention, the validation and verification process of a rather challenging GPSS program is described in detail. This is followed by a discussion of the processing environment decision (i.e. batch, on-line or interactive) as it affects most program development activities. Next, based upon the experience with this project, a structured and staged program development approach is suggested. This iterative method calls for simultaneous conceptual modeling and architectural (i.e. macro) coding. Strategic, tactical as well as operational planning considerations associated with this approach are presented.     

Adaptation of the IBM 7535 robot for use as a slave in a hierarchical master/slave relationship

A new programming environment for the IBM 7535 robot is introduced. AML/E is replaced by a hierarchical control scheme involving a host and a subservient robot. Application programs are developed on the host, an IBM-PC XT, in an extended version of the “C” programming language. These extensions allow an application program to be composed of several concurrent processes, one of which is responsible for commanding the robot. To configure the robot as a slave in this relationship, a new operating system was developed for its controller. Written in the same language employed at the host level, it is structured as four concurrent processes managing the robot's resources. An interprocess message-passing scheme provides a path for master/slave communication. The resultant environment is believed to be superior to the original language AML/E for the following reasons: Concurrency, along with the data and control structures of “C,” is made available to the application programmer. Communication is well structured. The robot's operating system is documented, written in a high-level language, and open to the user for modification. Due to the significance of integrating the robot into more complex applications involving sensors, these characteristics are felt to be essential in future robots.     

Imperative abstractions for functional actions

We elaborate our relational model of non-strict, imperative computations. The theory is extended to support infinite data structures. To facilitate their use in programs, we extend the programming language by concepts such as procedures, parameters, partial application, algebraic data types, pattern matching and list comprehensions. For each concept, we provide a relational semantics. Abstraction is further improved by programming patterns such as fold, unfold and divide-and-conquer. To support program reasoning, we prove laws such as fold–map fusion, otherwise known from functional programming languages. We give examples to show the use of our concepts in programs.     

The Unix System and Software Reusability

The Unix system contains a variety of facilities that enhance the reuse of software. These vary from the utterly conventional, such as function libraries, to basic architectural mechanisms, such as the Unix pipe. The Unix pipe, which makes whole programs building blocks of larger computational structures, has been the primary reason for the development of a literature of useful, but specialized programs-programs that would be too costly to write in a conventional programming language such as C. It has led to high levels of program reuse both by the nature of its operation and through its effect on programming conventions (e.g., programs structured as simple filters). Another facility enhancing reuse on Unix is the on-line C source code for Unix system programs. This has led to a shared style of programming in which existing programs are used as models for new programs, allowing the reuse of ideas, algorithms and source code. Finally, the Unix system contains many other reuse enhancing facilities, such as generic facilities for screen management (curses and termcap) and program generators (lex and yacc).     

On removing the machine from the language

Summary Many of the problems in programming languages today are a result of the model of computation offered by our machines. Structured programming combats these problems by restricting flow of control and storage references to a relatively safe set of control and data structures. Some current research attempts to aid programming reliability by enforcing such restrictions in the programming language. This paper proposes a simpler view of some basic language elements (variable, assignment, parameter), not based on our machines, that is safe without restriction. Structuring is then defined independently of what is being structured. A single, simple structure, applied to both values and assignments, yields equivalents for the safe set of data and control structures.This work was supported by the National Research Council of Canada     

Mixed programming metaphors in a shared dataspace model ofconcurrency

A simple language called Swarm is used as a vehicle for the investigation of the shared dataspace approach to concurrent computation. An important feature of Swarm is its ability to bring a variety of programming paradigms under a single, unified model. In a series of related examples Swarm's capacity to express shared-variable, message-passing, and rule-based computations; to specify synchronous and asynchronous processing modes; and to accommodate highly dynamic program and data structure is explored. Several illustrations make use of a programming construct unique to Swarm, the synchrony relation and explain how this feature can be used to construct dynamically structured, partially synchronous computations. An overview of the Swarm programming notation, an examination of Swarm programming strategies via a series of related example programs, and a discussion of the distinctive features of the shared dataspace model are given. A formal operational model for Swarm is presented     

Object-oriented programming—what for?

Object-oriented programming can improve the structure of a program as well as its extensibility and re-usability. However, it can also cause problems: one has to master large class libraries; the control flow of a program is cluttered among many small operations; and accessing all data via procedures reduces efficiency. Therefore, objectoriented programming cannot always be recommended. It is well suited for interactive applications and for programs which maintain heterogeneous data structures where additional variants of the data may be added later. It should not be used for closed algorithms which work on simple data or for time-critical applications. This paper deals with the following questions: When should classes be used? What are the typical application areas of object-oriented programming? Examples are included which demonstrate problems that can be solved elegantly with classes. The language Object Oberon is introduced.     

Extended unification algorithms for the integration of functional programming into logic programming

Extended unification algorithms are considered for the integration of a functional language into a logic programming language. The extended language is a particular case of logic programming language with equality. A comprehensive survey is given which is structured following the procedural semantics taken for the functional language. This survey includes past works based on evaluation and derivation (as procedural semantics of the functional language) and new algorithms based on surderivation. These algorithms are compared especially regarding their completeness. Also, we discuss issues arising in practice when different surderivation strategies are used, as these influence directly efficiency and especially termination. This leads us to propose an algorithm based on lazy surderivation which compares favorably with the others and endows logic programming with two advanced features of functional programming: automatic coroutining and handling of infinite data structures without extra control.