Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1980. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: leaves 365-371. / by Guy Lewis Steele, Jr. / Ph.D.

We present an extension of the Godel logic programming language code generator which compiles user-defined functions. These functions may be used as arguments in predicate or goal clauses. They are defined in extended Godel as rewrite rules. A translation scheme is introduced to convert function definitions into predicate clauses for compilation. This translation scheme and the compilation of functional arguments both employ leftmost-innermost narrowing. As function declarations are indistinguishable from constructor declarations, a function detection method is implemented. The ultimate goal of this research is the implementation of extended Godel using needed narrowing. The work presented here is an intermediate step in creating a functional-logic language which expands the expressiveness of logic programming and streamlines its execution.

A programming language that combines the best aspects of both the functional and logic paradigms with a complete evaluation strategy has been a goal of a Portland State University project team for the last several years. I present the third in a series of modifications to the compiler of the logic programming language Goedel which reaches this goal. This enhancement of Goedel's compiler translates user-defined functions in the form of rewrite rules into code that performs evaluation of these functions by the strategy of needed narrowing. In addition, Goedel's mechanism that evaluates predicates is supplemented so that needed narrowing is still maintained as the evaluation strategy when predicates possess functional arguments.

The temporal behavior in applications involving visual data can be critical for the correctness of some programs. Forms/3 allows the user to specify temporal behaviors in an independent way, without introducing extraneous code in the original spreadsheet, whereas some other languages define new language devices specific to time. In this thesis, we present the implementation of a new user interface for temporal programming in Forms/3 and the results of two empirical studies. The results of the first study show that one of the models for temporal programing in Forms/3 is more suitable for end users than a traditional stream-based approach representative of the approach used by many other languages. The results of our second experiment show that the explicit information provided by the approach can help the users to judge the correctness of their spreadsheets. / Graduation date: 2002

Test case generation in software testing is a process of developing a set of test data that satisfies a particular test adequacy criterion. It is desirable to automate this process since doing it manually is not only technically difficult but also tedious and time-consuming. Although there has been considerable research in automatic test case generation directed at imperative languages, we find no research exists addressing the problem for spreadsheet languages. This problem is particularly important for spreadsheet languages, since spreadsheet languages are widely used by end users and most of them lack testing backgrounds. To address this need, in this thesis, we present an automatic test case generation methodology for spreadsheet languages. Based on an analysis of the differences between imperative languages and spreadsheet languages, we developed our methodology by properly adapting existing test case generation techniques for imperative languages. Our methodology is integrated with a previously developed methodology for testing spreadsheets, and supports incremental automatic test case generation and visual feedback. We have conducted a family of empirical studies to assess the effectiveness and the efficiency of the essential techniques underlying our methodology. The results of our studies show that the test cases generated by our methodology can exercise a large percentage of a spreadsheet under test. The results also provide insights into the tradeoffs between two test case generation techniques for spreadsheet languages. / Graduation date: 2001

Exception handling is a programming language feature that can help increase the reliability of programs. However, not much work has been done on exception handling in visual programming languages. We present an approach for improving the exception handling mechanism in Forms/3, a declarative visual programming language based on the spreadsheet paradigm. We show how this approach can be added without sacrificing referential transparency and lazy evaluation in Forms/3. We then present a comparison of the Forms/3 exception handling mechanism with the mechanisms available in Java, C++, Prograph, Haskell and Microsoft Excel, based on their expressive powers. / Graduation date: 1998

Visual programming languages employ visual representation to make programming easier and make programs more reliable and more accessible. Visual program testing becomes increasingly important as more and more visual programming languages and visual programming environments come into real use. In this work, we focus on one important class of visual programming languages: form-based visual programming languages. This class of languages includes electronic spreadsheets and a variety of research systems that have had a substantial impact on end-user computing. Research shows that form-based visual programs often contain faults, but that their creators often have unwarranted confidence in the reliability of their programs. Despite this evidence, we find no discussion in the research literature of techniques for testing or assessing the reliability of form-based visual programs. This lack will hinder the real use of visual programming languages. Our work addresses the lack of testing methodologies for form-based visual programs. In this document, we first examine differences between the form-based and imperative programming paradigms, discuss effects these differences have on methodologies for testing form-based programs, and analyze challenges and opportunities for form-based program testing. We then present several criteria for measuring test adequacy for form-based programs, and illustrate their application. We show that an analogue to the traditional "all-uses" dataflow test adequacy criterion is well suited for testing form-based visual programs: it provides important error-detection ability, and can be applied more easily to form-based programs than to imperative programs. Finally, we present a testing methodology that we have developed for form-based visual programs. To accommodate the evaluation model used with these programs, and the interactive process by which they are created, our methodology is validation-driven and incremental. To accommodate the user base of these languages, we provide an interface to the methodology that does not require an understanding of testing theory. We discuss our implementation of this methodology, its time costs, the mapping from our approach to the user interface, and empirical results achieved in its use. / Graduation date: 1998

Declarative visual programming languages (VPLs), including spreadsheets, make up a large portion of both research and commercial VPLs. Spreadsheets in particular enjoy a wide audience, including end users. Unfortunately, spreadsheets and most other declarative VPLs still suffer from some of the problems that have been solved in other languages, such as ad-hoc (cut-and-paste) reuse of code which has been remedied in object-oriented languages, for example, through the code-reuse mechanism of inheritance. We believe spreadsheets and other declarative VPLs can benefit from the addition of an inheritance-like mechanism for fine-grained code reuse. This dissertation first examines the opportunities for supporting reuse inherent in declarative VPLs, and then introduces similarity inheritance and describes a prototype of this model in the research spreadsheet language Forms/3. Similarity inheritance is very flexible, allowing multiple granularities of code sharing and even mutual inheritance; it includes explicit representations of inherited code and all sharing relationships, and it subsumes the current spreadsheet mechanisms for formula propagation, providing a gradual migration from simple formula reuse to more sophisticated uses of inheritance among objects. Since the inheritance model separates inheritance from types, we investigate what notion of types is appropriate to support reuse of functions on different types (operation polymorphism). Because it is important to us that immediate feedback, which is characteristic of many VPLs, be preserved, including feedback with respect to type errors, we introduce a model of types suitable for static type inference in the presence of operation polymorphism with similarity inheritance. / Graduation date: 1999

Until now, attempts to extend the one-way constraint evaluation model of the spreadsheet paradigm to support complex objects, such as colored circles or user-defined types, have led to approaches featuring either a direct way of creating objects graphically or strong compatibility with the spreadsheet paradigm, but not both. This inability to conveniently go beyond numbers and strings without straying outside the spreadsheet paradigm has been a limiting factor in the applicability of spreadsheets. In this thesis we present a technique that removes this limitation, allowing complex objects to be programmed directly--and in a manner that fits seamlessly within the spreadsheet paradigm--using direct manipulation and gestures. We also present the results of an empirical study which suggests that programmers can use this technique to program complex objects faster and with fewer errors. The graphical definitions technique not only expands the applicability of spreadsheet languages, it also adds to their support for exploratory programming and to their scalability. / Graduation date: 1997

There are a number of well known techniques for extracting parallelism from a given program. They range from hardware implementations, building restructuring compilers or reorganizing of programs so as to specify all the available parallelism. The success rate of any of the known techniques is rather poor over all types of programs. This has pushed the research community to explore new languages and design different architectures to exploit program parallelism. The principles of dataflow architectures have addressed the problem of exploiting parallelism in systems by executing dataflow graphs. These graphs or programs represent data dependencies among instructions and execution of the graph proceeds in a data-driven manner. That is, an instruction is executed as soon as all its operands are available, without waiting for any program counter to sequence its execution, as is the case in conventional von Neumann architectures. In this thesis, data flow graphs are generated during the intermediate compilation of a functional language called SISAL (Streams and Iterations in a Single Assignment Language). The Intermediate Form (IFl) is a graphical language consisting of multiple acyclic function graphs that represent a given program. Each graph consists of a sequence of nodes and edges. The nodes specify the operation and the edges indicate the dependencies between the nodes. The graphs are further connected to each other by means of implicit dependencies. The Automator package developed in this project, preprocesses these multiple IF1 graphs and translates them into a single connected graph. It converts all implicit dependencies into actual ones. Additionally, complex language constructs like For All, loops and if-then-else are treated in special ways together with their nested levels by the Automator. There is virtually no limit to the number of nested levels that can be translated by this package. The Automator's prime contribution is in translating real programs written in SISAL into a specified format required by an allocation algorithm called the Balanced Layered Allocation Scheme (BLAS). BLAS partitions a connected graph into independent tasks and assigns them to processors in a multicomputer system. The problem of program allocation lies in maximizing parallelism while minimizing interprocessor communication costs. Hence, allocation is based on the best choice of communication to execution ratio for each task. BLAS utilizes heuristic rules to find a balance between computation and communication costs in the target system. Here the target architecture is a simulated nCUBE 3E computer, having a hypercube topology. Simulations show that, BLAS is effective in reducing the overall execution time of a program by considering the communication costs on the execution times. The results will help in understanding the effects in packing nodes (grain-packing), routing issues in the network and in general, the allocation problem to any processor in a network. In addition, tasks have also been assigned to adjacent processors only, instead of any processor on the hypercube network. The adjacent allocation to processors helps to determine trade-offs required between achieved speed-ups and the time it takes to completely allocate large graphs on compilation. / Graduation date: 1994