Yashar is a rule based meta-tool for rapidly producing tools to increase programming speed through automating restructuring of existing source code modules so they can be reused, generating of syntax-directed tools, language-to-language translation, automated document generation , and various debugging tools. The main significance of Yashar is that it can...
The term object-oriented is defined. This definition is then related to message-passing, inheritance, polymorphism, data abstraction, generics, and overloading.
A software system to study network algorithms was implemented on UNIX. Each part of a network algorithm can be written as a single C program which becomes a virtual node in the network. During a simulation all virtualized nodes run as separate processes on a single PDP 11/44. Inter-node communication...
This report describes "VIGRAM" (Visual Programming) which is a program understanding and complexity metric analysis tool for Pascal programs. VIGRAM is implemented on the Macintosh as one part of the "O.S.U." (Qregon Speedcode Universe) project. With VIGRAM, the source code of a Pascal procedure can be displayed as a visual...
In this dissertation we consider the problem of
automating the design of access structures for relational
database systems. The main considerations are effective
and rigorous utilization of the users' usage patterns,
global treatment of the whole design and utilizing most of
the commonly known access structures.
We represent the usage...
In recent papers on machine learning, the term 'operationalization' has been used to describe the purpose of the learning process. In particular, explanation-based learning systems are said to 'operationalize' the given target concept. Unfortunately, the exact meaning of this term has varied from one paper to another, and frequently the...
Summary of results. After implementing the plain ID3 algorithm, I experimented with
various modifi cations. Two improvements of the process of finding a legal phoneme/stress
could be made by using statistical information about the letter to phoneme/stress-mapping
in the training set.
Adding the CHI-SQUARE test to the ID3 algorithm was...
An extensive theory of symmetric error control coding has been developed in the last few decades. The recently developed VLSI circuits, ROM, and RAM memories have given an impetus to the extension of error control coding to include asymmetric and unidirectional types of error control. The maximal numbers of unidirectional...
There is disagreement about the role and importance of typographic style (source code formatting and commenting) in program comprehension. Results from experiments and opinions in programming style books are mixed.
This paper presents principles of typographic style consistent and compatible with the results of program comprehension studies. It introduces the...
Three different approaches to type checking have been taken in object-oriented programming languages. Smalltalk-80 uses run-time type checking. C++ uses subtypes. A third alternative is to use parameterized types. We examine the difficulties of programming in an object-oriented fashion with compile-time type checking and argue that parameterized types are better...
A method for implementing parameterized types is given. Two simplifying restrictions are assumed: types are only parameterized with other types, and assignment is like that of SNOBOL, CLU, and Smalltalk. An algorithm for type checking that handles parameterized types and overloading is presented .
This technical report reprints two articles that appeared in Proceedings of the Third International Machine Learning Workshop at Skytop, Pennsylvania, June 24-26, 1985. The first paper, The EG Project: Recent Progress, summarizes work on the EG project, which is investigating the role of active experimentation in aiding machine learning programs....
A concurrency and resiliency control scheme for a distributed database system with replicated data is discussed. The scheme, true-copy token scheme, uses true-copy tokens in order to designate the physical data copies (true copies) that can be identified with the current logical data that are globally unique, and then it...
Topological Sorting is a standard computation performed on finite partial order relations, for which efficient algorithms are well known.
This work is a study of using a depth-first search of a directed graph to implement topological sorting algorithms. A new algorithm is presented, along with a discussion of how it...
Test incorporations are program transformations that improve the performance of generate-and-test procedures by moving information out of the "test" and into the "generator." The test information is said to be "incorporated" into the generator so that items produced by the generator are guaranteed to satisfy the incorporated test. This article...
This paper reports the findings of two studies conducted at Oregon State University. The first set of studies compares use of header comments versus mnemonic procedure and function names by programmers performing tasks relating to modification tasks. The second study compares the use of header comments versus in-line comments when...
A decision support system (DSS) incorporating domain
expertise guides, tutors, and consults a decision maker in
opportunity, problem, and crisis identification activities. The
objective for the system is to promote improved decision making.
Using an "Independent Groups" design, an experimental study was
conducted to investigate the effects of DSS use...
Display, which is the function for displaying the
schema of the network at the conceptual level, is implemented
to enhance the network database system ALLEGRO.
To display the schema is one step towards modifiable
schemas in the network model. The problem of updating a
schema is examined at all three...
The design of an experimental object-based programming language is discussed. The language is intended for investigating techniques for organization of programs.
Object oriented programming languages are noted for their ability to allow users to quickly construct large software systems. They achieve this ability by allowing the programmer to concentrate on what it is they want to do, ignoring details of how that functionality is achieved. Such characteristics should make the object...
This research solves the problem of connecting a Macintosh to a Unix machine and presenting the Macintosh Desktop to Unix. Unix Files can be viewed. copied. renamed and opened in the same manner as Macintosh files. Unix programs and shell commands can be defined and attached to Macintosh menus and...
An automated library system should be capable of providing at least all of the information and capabilities of existing manual catalogs. In addition, an automated system must provide the capability of manipulating that information to produce varying types of reports and statistics. This paper briefly:
- describes historical representations of...
Parallel programming is the major stumbling block preventing the parallel processing industry from quickly satisfying the demand for parallel computer software. This research is aimed at solving some of the problems of software development for parallel computers. ELGDF is a graphical language for designing parallel programs. The goal of ELGDF...
This report presents a graphical tool for implementation of the scheduling heuristics provided by Kruatrachue. The input of scheduling is a task graph and the output is a schedule in the form of a Gantt chart. The implemented scheduling heuristics are: 1) Hu's HLF (highest level first) algorithm. 2) Yu's...
Stella Bridge is a program for converting mathematical models designed with STELLA For Business into object-based source programs written in Pascal. The input to Stella Bridge is a series of tables1 functions, and initial conditions generated by STELLA For Business. The output from Stella Bridge is a collection of Pascal...
In von Neumann Languages, side effects occur if one or more non local variables change value(s) during the execution of a procedure or a function. Side effects can occur only if the programming language provides a notion of memory (or state) where the effect will be stored. Side effects complicate...
This research work investigates the use of production
systems as a model of parallel processing. The purpose of
the model is to provide a suitable medium within which parallel
processing systems can be systematically specified,
analyzed, and designed. Furthermore, the model provides a
suitable means for deriving implementations of synchronization...
The need for graphical presentation arises in many disciplines. This thesis describes a prototype software system, the graph creation system, which gives unspecialized users the ability to create and display a variety of graphical figures. Templates for types of graphical figures, and the user interactions for creating instances of a...
ELGDF (Extended Large Grain Data Flow) is a design language that allows representation of a wide variety of parallel programs. The syntax is graphical and hierarchical to allow construction and viewing of realistically sized programs. ELGDF language facilitates describing parallel programs in a natural way for both shared memory model...
In most technical fields, a certain amount of practical application is necessary to master the important concepts and acquire basic problem solving skills. Computer science is no different, and this is reflected in the frequent programming assignments given in programming and data structures courses. The basic skills and concepts gained...
Using Smalltalk-80, programmers can produce prototypes much faster than with C or Pascal. What techniques do Smalltalk-80 programmers use to produce these prototypes? What is special about Smalltalk-80 that enables them to uses these techniques? Can these techniques be used with conventional languages such as C? In an attempt to...
This is an attempt to deal with interface problems of interacting modules in a large simulation system.
In simulation, scientists require routine substitution of modules for comparison of alternative models. These changes have propagating side affects and from a programmer's point of view are essentially system redesigns.
This paper presents...
This paper presents a model for deterministic parsing which was designed to simplify the task or writing and understanding a deterministic grammar. While retaining structures and operations similar to those or Marcus's PARSIFAL parser [Marcus 80] the grammar language incorporates the following changes. (1) The use or productions operating in...
A new class of information intensive applications is emerging [Fuch82;
Ohsu82] for which neither Artificial Intelligence (AI) nor Database technologies
alone are well suited. Database systems do not provide the general inferential
capabilities required for problem solving, while AI techniques have not been
adapted to handle massive amounts of structured...
Tbc expanding complexity of database application worlds, and the accelerating pace of change of these worlds mandate data models which support some of the tasks of data interpretation which formerly were borne by the applications programs. Chief among these are the support for virtual data, definition of transactions, and enforcement...
In process control systems where an entire process
is being controlled by a computer, the component tasks of
the system have to be monitored. An efficient message
oriented environment could be an important factor in the
optimization of such systems. In this paper we discuss
the design of a real...
The task of inductive learning from examples places constraints on the representation of training instances and concepts. These constraints are different from, and often incompatible with, the constraints placed on the representation by the performance task. This incompatibility explains why previous researchers have found it so difficult to construct good...
Seed-Lab, is a software system for managing seed laboratory information. It was developed at the Oregon State University Seed Testing Laboratory. Seed-Lab was built around a database development package Revelation, which provides its own programming language.
Seed-Lab shields the user from the complexities of database management by supporting menu driven...
The SEAS Directory and File Manager is a multiple window interactive tool to assist users in modifying and maintaining UNIX files and directories. This tool includes a show directory utility, a show file utility, a type file utility and provides access to the UNIX shell.
This paper describes Schemer, a hierarchical software architecture for Real Time problem solving. Real time applications must be able to react to critical events quickly, and be able to explore simultaneous solutions in response to, or, in anticipation of such events.
Schemer, which is a Blackboard-like architecture, addresses the aforementioned...
The Sacagawea testbed has been designed to support testing and development of decision making models, and associated uncertainty management techniques, that are appropriate under real-time problem solving constraints. Conceptually, it provides a simulated temporal and spatial environment, the latter consisting of a terrain grid of elevation and tree cover data,...
The Sacagawea testbed has been designed to support testing and development of decision making models, and associated uncertainty management techniques, that are appropriate under real-time problem solving constraints. Conceptually, it provides a simulated temporal and spatial environment, the latter consisting of a terrain grid of elevation and tree cover data,...
Traditional database management systems have been deemed unsuitable for use in the Computer Aided Engineering environment Object-oriented data models with project management features have been proposed as an alternative. The Distributed Hypothetical Storage System is intended to serve as the underlying storage mechanism for an object-oriented data model. The storage...
Computer networking research has been going on for almost twenty years; however, most of the protocols concern high and low speed synchronous transmission. All synchronous communication needs special transmission lines. The TCP/IP (Transmission Control Protocol/Internet Protocol) protocols, Ethernet, X.25, X windows system are very successful protocols. Less work has been...
RezDez is a Macintosh program for designing Macintosh resources through direct manipulation of graphical objects. Specifically, RezDez allows a designer to construct:
Windows : Any of the six standard Macintosb windows with the designer choosing the location, size and title of the window.
Menus : With upto twenty menu items...
We have identified a "book paradigm" for source code formatting which improves program comprehension and assists in maintenance work. The book paradigm can be implemented by reverse engineering code listings into a "book" with preface, tab1es of contents, chapters, sections, indices and pagination. This reverse engineering effectively reorganizes source code...
Over the past few years Qualitative Reasoning about physical systems has emerged strongly as an important area in Artificial Intelligence. Many qualitative reasoning formalisms have been developed and applied to varied domains, namely, hydraulic systems, electrical systems, industrial control etc.
This paper examines Qualitative Process Theory [Forbus 84] formalism in...
QCritic is a rule-based critic for analog bipolar circuits. It functions as a post-processor for the SPICE simulator, making use of netlist, current, and voltage data. The program was written in OPS83, and demonstrates good run-time performance on a VAX 11/780. At present, the system contains rules for analyzing circuits...
Production Systems are languages widely used for the implementation of Artificial Intelligence projects. They support programs in which the sequence of instructions is not fully determined at the beginning of their execution, as well as 'event driven' programs (i.e. the occurrence of a particular element in the data set determines...
Oregon Speedcode Universe (OSU) is a software development system employing on-screen editing of standard graphical user interface objects, prototyping, program generation, and automatic analysis tools which are typically used to accelerate the production of running applications. A programmer uses OSU to design and implement all user interface objects such as...
Detecting instances of software theft and plagiarism is a difficult problem. The statistical analysis of peculiar words or phrases known to be used by an author is a common method of settling authorship disputes in English literature. This paper presents a similar method for identifying authorship of programs. The method...
This paper describes the program transformation method used in DataLab, a general-purpose system for the specification and synthesis of abstract data types (ADTs). We present a model for transforming visual specifications of ADTs to imperative code. This model includes two forms of internal representations: one for the ADTs visual specifications...
Many studies have shown that expert programmers are more effective at debugging programs than novice programmers. These studies have suggested that the major reason for this difference is due to the experts' superior comprehension of the program. This paper reports two experiments which investigated expert and novice student programmers program...
We will describe two known strategies for static processor
allocation in an n-cube multiprocessor, namely the buddy system
strategy and the gray code strategy, and then propose a new strategy
that outperforms the first by (n-k+1) and the second by (n-k+1)/2 in
cube recognition. Furthermore, our strategy is suitable for...
A process-resource graph is a directed graph with m
resource nodes and n process nodes. A request edge is
directed from a process to a resource. An assignment edge
is directed from a resource to a process. A cycle in the
process-resource graph is a necessary and sufficient condition for...
X2 is an object-oriented programming language. Object-oriented programming models everything in the world as objects that have some local state that may vary with time. If the state of an object varies with time the object is mutable. If the state is time independent the object is immutable. Each object's...
This paper presents the initial results from an empirical study of mechanical design engineers. In this study, six engineers were video-taped solving real mechanical design problems. Preliminary analysis of this protocol data has yielded several important findings, including (a) mechanical designers progress from systematic to opportunistic behavior as the design...
Acoustic position estimation is used where high accuracy navigation is required over a small area, such as for searching or for collecting gravitational or geomagnetic data. In this position estimation method, a surface ship or submersible periodically sends out a high-frequency acoustic 'ping' at a prearranged frequency. This ping is...
System architectures for interconnecting large numbers of processors are being widely studied [AG82,TH75,TR82]. Of particular interest in such architectures is the exploitation of concurrency among processors. This concurrency can be parallelism, in which different parts of a single data case are processed at the same time, or pipelining, in which...
Caesar is an interactive graphic editor that is used to generate layouts for VLSI circuits . It runs on a VAX-11/780 under the UNIX operating system with Berkeley extensions. Caesar has a unique and simple user interface. Phled is an enhanced version of Caesar
that runs on a M68000-based engineering...
A database to be used by electrical circuit design, test, and repair expert systems must support both structural data and inferential data about the circuit. It is well known that engineering databases must support dynamic schema (re)definition of the structural data and entity-based access to it. We analyze this requirement...
Two methods for parallelizing WHILE loops are presented. The first method converts a WHILE loop into a FORALL construct, and the second method pipelines a WHILE loop. Each of the methods is based on a transformation that makes explicit the loop counting. Also, we propose two parallel WHILE constructs.
Object oriented programming features information hiding and encapsulation, meaning that 1) each object hides the the implementation details tram access from outside and only a set of methods (interface routines) are visible outside of the object, and 2) changes to the implementation of the object do not require changes to...
Parallel solutions for two classes of linear programs are
presented. First we parallelized the two-phase revised simplex
algorithm and showed that it is possible to get linear improvement in
performance. The simplex algorithm is the best known algorithm for
solving linear programs, and we claim our result is the best...
This project is concerned with the optimal distribution of the computation and the data in parallelized Simplex algorithms. Test cases were implemented on a 16-processor Transputer system from INMOS Corporation. By careful consideration of distribution of computations and data, a nearly linear speedup pattern was obtained. The most
interesting thing...
A translator has been designed and implemented which generates parallel code for a long instruction word parallel computer with local memories. Its main methods are to translate the sequential source code into single assignment, two-operand form, and to then assign the operations to processors so as to minimize the number...
New parallel algorithms for solving the decomposed linear programs are developed. Direct parallelization of the sequential algorithm results in very limited performance improvement using multiple processors. By redesigning the algorithm, we achieved more than 2*P times performance improvement over the sequential algorithm, where P is the number of processors used...
Oregon Speedcode Universe (OSU) is a software development environment for design, implementation, and maintenance of large soft.ware systems. Designed to be highly visual, OSU combines traditional structured analysis techniques found in most CASE tools with advanced graphical user interface management systems (UIMS) found on most contemporary workstations. This paper describes...
Several problems with user interface design and implementation have been identified: (1) user interfaces are difficult and time-consuming to design and implement; (2) most user interface management systems (UIMS) are themselves difficult to use by a programmer; (3) UIMS's have not been integrated with other tools that support structured design,...
Various problems related to systematic error-detecting
and error-correcting unidirectional codes are discussed.
Systematic codes with r check bits are the main topic of
the thesis. Classes of codes are presented which work for
specific numbers of information bits and then a class of
codes is given which detects the same...
A new algorithm, the Horizontal and Vertical Algorithm, for
on-line detection of deadlocks in distributed computer systems, is
presented. Two protocols for implementing the algorithm are given.
The first protocol, the centralized protocol, is based on the
assumption that one site in the network acts as the controller for
global...
We investigate the use of automata theory to model strategies for nonzero-sum two-person games such as the Prisoner's Dilemma. We are particularly interested in infinite tournaments of such games. In the case of finite-state strategies (such as ALL D or TIT FOR TAT) we use graph traversal techniques to show...
Historically, coding theory has dealt with binary
codes correcting symmetric errors, in which errors are
made in both 0 and 1 bits with equal likelihood.
Within the past ten years, some study has been made of
asymmetric codes, under the assumption that the only
errors which occur are errors in...
Object files are named active entities (processes) in the UNIX file system graph which provide services. Services are solicited by using the object file's pathname in any system call. Other continuing services can be obtained by opening an object file (which creates an communication path to the object) or by...
Recently generalized Fibonacci numbers have received increasing attention. Some properties that are well known for traditional Fibonacci numbers do not generalize easily, some others do not generalize at all. In this paper we report some properties that we have generalized. Section 1 introduces the notation and a theorem due to...
The bulk of the theory on error control codes has been developed under the
fault assumption of random (symmetric) errors, where 1 → 0 and 0 → 1 errors are
equally likely. In the past few years, several applications have emerged in which the
observed errors are highly asymmetric. This...
This paper presents a Hypothetical Storage Server for an experimental design database system. The storage server provides unified management of historical versions and hypothetical versions of objects in a design database. The extension of each database object is man.aged as a tree of multiple distinct representatives. One branch of the...
A typical database system maintains target data, which contain information useful for users, and access path data, which facilitate faster accesses to target data. Further, most large database systems support concurrent processing of multiple transactions. For a static database system model, where units of concurrency control are not dynamically created...
Cichelli gave a simple machine independent minimal perfect hashing function for small static sets. The hash function value for a word is computed as the sum of the length of the word and the values associated with the first and last letters of the word. Cichelli's algorithm (word-oriented) to find...
Parallel computers have generated a great deal of excitement and interest in the computer industry as well as the computer user industries. Parallel computers offer the promise of enormous gains in computing speeds by allowing multiple processors to work on different pieces of the same problem at the same time....
The Macintosh revolutionary interface sets it apart from all other personal computers. The Macintosh designers made the Macintosh easy to learn, understand, and use.
To ensure correct implementation of their User interface, Apple provided Macintosh programmers with "Inside Macintosh". Inside Macintosh is a complete detailed manual which contains recommendations and...
We describe a. new approach to implementing functions as first class values. Using this technique, there is no additional overhead imposed for the most common case, that of non-nested functions bound at compile time. Invoking function values assigned to variables requires two additional instructions. It is only when functions are...
Information is often incomplete in databases, and nulls are required to represent missing or unknown data; however, many difficulties occur with nulls. In his 1983 text, C. J . Date rejected outer join of relations with nulls mainly due to a perceived problem with functional dependencies (FDs): when nulls are...
High-level languages provide a convenient environment for program development as well as ease of source code portability. Unfortunately the degree of portability of the programs written in conventional high-level languages change depending on the programming style of the programmer. The Operating System interface also has an effect on the ease...
X2 [4] is a Smalltalk-like programming environment [1]. As it has grown in size and complexity the existing organizational tools have become inadequate for user and system needs. This project addresses this deficiency and some of its important consequences.
The entities to be organized are those that are a fixed...