Relation-algebraic semantics

The first half is a tutorial on orderings, lattices, Boolean algebras, operators on Boolean algebras, Tarski's fixed point theorem, and relation algebras.

In the second half, elements of a complete relation algebra are used as “meanings” for program statements. The use of relation algebras for this purpose was pioneered by de Bakker and de Roever in [10–12]. For a class of programming languages with program schemes, single μ-recursion, while-statements, if-then-else, sequential composition, and nondeterministic choice, a definition of “correct interpretation” is given which properly reflects the intuitive (or operational) meanings of the program constructs. A correct interpretation includes for each program statement an element serving as “input/output relation” and a domain element specifying that statement's “domain of nontermination”. The derivative of Hitchcock and Park [17] is defined and a relation-algebraic version of the extension by de Bakker [8, 9] of the Hitchcock-Park theorem is proved. The predicate transformers wp_s(-) and wlp_s(-) are defined and shown to obey all the standard laws in [15]. The “law of the excluded miracle” is shown to hold for an entire language if it holds for that language's basic statements (assignment statements and so on). Determinism is defined and characterized for all the program constructs. A relation-algebraic version of the invariance theorem for while-statements is given. An alternative definition of intepretation, called “demonic”, is obtained by using “demonic union” in place of ordinary union, and “demonic composition” in place of ordinary relational composition. Such interpretations are shown to arise naturally from a special class of correct interpretations, and to obey the laws of wp_s(-).     

An interactive simulator for statistical process control

An interactive program has been developed which simulates several representative industrial processes. Specifically, the program generates product quality characteristic values which are concurrently monitored by standard control charting methods. The program requires the user to specify initial process parameter values and subsequent process adjustments; the latter is necessary in the event the process is deemed to be “out-of-control”. The effectiveness of these decisions are measured by economic criteria. The use of the software promotes a “hands-on” approach, which will better prepare the students to achieve quality improvements in an industrial environment through systematic and scientific evaluation.     

Solution of a timetable problem

Starting from a heuristic program, the author has tried to develop a timetable program which can be applied to practical cases. In constructing a timetable, conflicts usually arise as to the availability of teachers, classes and classrooms. So we set up a timetable starting from the subjects most likely to lead to conflicts. When a conflict occurs in the heuristic procedure, exchange facilities are provided for the “dead ends” with the aid of certain “alternating subgraphs”. The main procedure is followed by a program that analyses the result and uses the exchange routine for an improvement within certain limits.     

A software authentication system for information integrity

This paper describes a software authentication technique based on the public key cryptography for information integrity. The software provider can use a secret key to sign any released program and the user can verify the integrity of programs obtained from vendors or a “trusted information database”. The software provider needs to go through a registration process to become “licensed” and obtains certificates from multiple certificate centers before being able to sign any released program. Users need only one public key to verify the integrity of the programs.     

A simple way to construct interactive processors

A FORTRAN program is presented which reads instruction lines entered from a timesharing terminal, and interprets them as beginning with an instruction word and continuing with “declarations”. The instruction word and the information in the declarations are passed to a linking subroutine and thence to a set of user-supplied subroutines which act on the instruction. The program is in effect the nucleus of a processor and, when linked to a working set of subroutines, it can be made to approximate to a simple computer “language”. Any number of such languages can be built with the program as a basis. A language of this sort is unlikely to be as powerful, as versatile, or as generalized as FORTRAN, but it is certain to be simpler to work with in the user's particular context, to which it can be adjusted as nicely as programming time and costs permit. The program is not very useful for small or circumscribed tasks, or for applications already covered by standard libraries; its value lies rather in simplifying specialized tasks of moderate complexity and diversity. A companion paper illustrates a use of the program in a processor for handling data obtained with a digitizer.     

One-dimensional collision: An interactive graphics program

An interactive program with output to a graphical terminal has been developed for use in an undergraduate physics laboratory. The program computes and draws “snapshots” of one dimensional elastic collisions from data chosen by the student. The aim of the program is to come to a better understanding of the physics of collisions as seen from laboratory and center of mass reference frames. Great stress is laid upon the properties of the latter.     

FLASK-SG: A program to compute chemical equilibria in metamorphic petrology

Chemical equilibrium calculation program for metamorphic petrology, FLASK-SG, was written for Unix variants (Linux, IRIX, Tru64 UNIX). It is also ported to Windows 95/98. The user specifies a temperature, pressure, and substance amounts (in moles of any chemical formula in C–H–O–Si–Al–Ti–Fe–Mn–Mg–Ca–Na–K system) to this program, then it calculates the stable mineral assemblage, mineral amounts, and gas composition under the given conditions using Gibbs free energy minimization method with the Holland and Powell (1990) data set. Searching algorithm for the stable mineral assemblage is the Metropolis Monte Carlo method. The coding language is C++, and experimental object oriented programming style is adopted to make the main program part as a class library. Model-dependent functions such as fugacity coefficients and activities are implemented as virtual methods of the “systems” class, so they can be easily changed as methods of inherited class from the “systems” class. These characteristics are aimed for a future “simulation kit”.     

Graphic simulation of planar dynamic mechanisms

This paper describes the development of easy interactive input and graphic output for a “self-formulating” program, PLANET III, developed at the University of Waterloo. Using the vector-network model, which is a combination of the concepts of vector calculus and linear graph theory, this computer program simulates planar dynamic mechanisms. It is “self-formulating”, because it gives the illusion that the program formulates the equations of motion of the system to be simulated, thus relieving the user of this task. PLANET III can formulate and integrate the equations of motion of multirigid-body, two-dimensional systems when supplied with only the system topology and element characteristics. The versatile graphic output can show both the simulated motion of the system topology and graphs of the position, velocity, acceleration (for masses only) and forces for any system element versus any other system element or time. This permits large quantities of data to be comprehended quickly and easily. The entire process, from data input through graphic output, may be completed generally within a matter of minutes, thereby greatly reducing the time required for each design iteration. Two simulation examples illustrate the practical application of the program.     

Program complexity using Hierarchical Abstract Computers

A model of program complexity is introduced which combines structural control flow measures with data flow measures. This complexity measure is based upon the prime program decomposition of a program written for a Hierarchical Abstract Computer. It is shown that this measure is consistent with the ideas of information hiding and data abstraction. Because this measure is sensitive to the linear form of a program, it can be used to measure different concrete representations of the same algorithm, as in a structured and an unstructured version of the same program. Application of the measure as a model of system complexity is given for “upstream” processes (e.g. specification and design phases) where there is no source program to measure by other techniques.     

Interactive software to solving the resource balancing problem

The proposed paper presents a software developed for the microcomputer to solving the resource balancing problems. The developed software is an interactive concept program and can be used by people with or no experience in the computer programming. The program consists of two linked modulus which are working complementary. The program is designed in the “MENU” concept and for the practical using, the data files option proposed for the running of the program with the same production network. The designed program is flexible and with a low cost microcomputer system, the program is definitly an economic and practical tool to solving the resource balancing problems. To identify the potential ability of the proposed software and to indicate how the software can be used a complete example will be discribed.     

Graphical analysis of mortgage payments

This paper presents a computer package that performs graphical analysis of mortgage. In the computational procedure, the program calculates the monthly payment, the unpaid balance, interest charge, and equity payment for each of the months of the mortgage term. Plots of unpaid balance and total equity versus time are made for a visual analysis. The program, named GAMPS, is equally applicable to any cash flow situation involving equal periodic installments. Of particular importance is the “equity break-even point” which the program also calculates. This break-even point indicates that point in time when the unpaid balance equals the cumulative equity.     

A Calculus for “environment-aware” computation

We present a calculus for modelling “environment-aware” computations, that is computations that adapt their behaviour according to the capabilities of the environment. The calculus is an imperative, object-based language with extensible objects, equipped with a labelled transition semantics. A notion of bisimulation, lifting to computations a correspondence between the capabilities of different environments, is provided. Bisimulation can be used to prove that a program is “cross-environment”, i.e., it has the same behaviour when run in different environments.     

Deforestation, program transformation, and cut-elimination

The problem of proving that two programs, in any reasonable programming language, are equivalent is well-known to be undecidable. In a formal programming system, in which the rules for equivalence are finitely presented, the problem of provable equivalence is semi-decidable. Despite this improved situation there is a significant lack of generally accepted automated techniques for systematically searching for a proof (or disproof) of program equivalence. Techniques for searching for proofs of equivalence often stumble on the formulation of induction and, of course, coinduction (when it is present) which are often formulated in such a manner as to require inspired guesses.There are, however, well-known program transformation techniques which do address these issues. Of particular interest to this paper are the deforestation techniques introduced by Phil Wadler and the fold/unfold program transformation techniques introduced by Burstall and Darlington. These techniques are shadows of an underlying cut-elimination procedure and, as such, should be more generally recognized as proof techniques.In this paper we show that these techniques apply to languages which have both inductive and coinductive datatypes. The relationship between these program transformation techniques and cut-elimination requires a transformation from initial and final “algebra” proof rules into “circular” proof rules as introduced by Santocanale (and used implicitly in the model checking community). This transformation is only possible in certain proof systems. Here we show that it can be applied to cartesian closed categories with datatypes: closedness is an essential requirement. The cut-elimination theorems and attendant program transformation techniques presented here rely heavily on this alternate presentation of induction and coinduction.     

Sketching space

In this paper, we present a sketch modelling system which we call Stilton. The program resembles a desktop VRML browser, allowing a user to navigate a three-dimensional model in a perspective projection, or panoramic photographs, which the program maps onto the scene as a “floor” and “walls”. We place an imaginary two-dimensional drawing plane in front of the user, and any geometric information that user sketches onto this plane may be reconstructed to form solid objects through an optimisation process. We show how the system can be used to reconstruct geometry from panoramic images, or to add new objects to an existing model. While panoramic imaging can greatly assist with some aspects of site familiarisation and qualitative assessment of a site, without the addition of some foreground geometry they offer only limited utility in a design context. Therefore, we suggest that the system may be of use in “just-in-time” CAD recovery of complex environments, such as shop floors, or construction sites, by recovering objects through sketched overlays, where other methods such as automatic line-retrieval may be impossible. The result of using the system in this manner is the “sketching of space” — sketching out a volume around the user — and once the geometry has been recovered, the designer is free to quickly sketch design ideas into the newly constructed context, or analyse the space around them. Although end-user trials have not, as yet, been undertaken we believe that this implementation may afford a user-interface that is both accessible and robust, and that the rapid growth of pen-computing devices will further stimulate activity in this area.     

Internal reinforcement in a connectionist genetic programming approach

Genetic programming (GP) can learn complex concepts by searching for the target concept through evolution of a population of candidate hypothesis programs. However, unlike some learning techniques, such as Artificial Neural Networks (ANNs), GP does not have a principled procedure for changing parts of a learned structure based on that structure's performance on the training data. GP is missing a clear, locally optimal update procedure, the equivalent of gradient-descent backpropagation for ANNs. This article introduces a new algorithm, “internal reinforcement”, for defining and using performance feedback on program evolution. This internal reinforcement principled mechanism is developed within a new connectionist representation for evolving parameterized programs, namely “neural programming”. We present the algorithms for the generation of credit and blame assignment in the process of learning programs using neural programming and internal reinforcement. The article includes a comprehensive overview of genetic programming and empirical experiments that demonstrate the increased learning rate obtained by using our principled program evolution approach.     

The Master of Software Engineering (MSE) program at Seattle University

The term “software engineering” has been in use for over twenty years. Yet, it lacks a precise, generally acceptable interpretation. This situation has made it especially difficult to define and implement educational programs in this relatively new discipline. This paper discusses the experience and results of one of the first successful graduate programs in the field, the Seattle University Master of Software Engineering (MSE) program. This program was established in 1979, and the results of its first several years of operationare reviewed in this article.     

Code Annotation for Safe and Efficient Dynamic Object Resolution

The execution time of object oriented programs can be drastically reduced by transforming “non escaping” objects into a collection of its component scalar data fields. But for languages that support dynamic linking, this kind of optimization (which we call “object resolution”) can usually only be performed at runtime, when the entire program is available for analysis. In such cases, the resulting performance increases will be offset by the additional costs that arise during the analysis and restructuring phases.In this paper, we describe work in progress, which provides an annotation technique that reduces the runtime overhead required for performing object resolutions. Our method performs a partial static escape analysis of each class at compile-time and then annotates the intermediate representation of that class with information which the just-in-time (JIT) compiler can use for object resolution. We apply this technique to the safe TSA intermediate representation, producing a simple extension to safe TSA's type system that guarantees a safe and verifiable transmission of the annotated program.     

A Temporal Logic for Proving Properties of Topologically General Executions

We present a generalization of the temporal propositional logic of linear time which is useful for stating and proving properties of the generic execution sequence of a parallel program or a non-deterministic program. The formal system we present is exactly that same as the third of three logics presented by Lehmann and Shelah (Information and Control53, 165–198 (1982)), but we give it a different semantics. The models are tree models of arbitrary size similar to those used in branching time temporal logic. The formulation we use allows us to state properties of the “co-meagre” family of paths, where the term “co-meagre” refers to a set whose complement is of the first category in Baire's classification looking at the set of paths in the model as a metric space. Our system is decidable, sound, and, complete for models of arbitrary size, but it has the finite model property; namely, every sentence having a model has a finite model.     

SPHERE: A contouring program for spherical data

This paper describes a method for displaying a sample of spherical data, by computing an “optimally” smoothed estimate of the underlying distribution and making a stereographic projection of the contours of this estimate. An interactive FORTRAN program which applies this method is supplied and described and examples given of its use.