Permanent URI for this collection
Browse
Recent Submissions
Publication Proceedings of the First New Zealand Formal Program Development Colloquium(Working Paper, 1994-11) Reeves, SteveThis volume gathers together papers presented at the first in what is planned to be a series of annual meetings which aim to bring together people within New Zealand who have an interest in the use of formal ideas to enhance program development. Throughout the World work is going on under the headings of "formal methods", "programming foundations", "formal software engineering". All these names are meant to suggest the use of soundly-based, broadly mathematical ideas for improving the current methods used to develop software. There is every reason for New Zealand to be engaged in this sort of research and, of growing importance, its application. Formal methods have had a large, and growing, influence on the software industry in Europe, and lately in the U.S.A. it is being seen as important. An article in September's "Scientific American" (leading with the Denver Airport debacle) gives an excellent overview of the way in which these ideas are seen as necessary for the future of the industry. Nearer to home and more immediate are current speculations about problems with the software running New Zealand's telephone system. The papers in this collection give some idea of the sorts of areas which people are working on in the expectation that other people will be encouraged to start work or continue current work in this area. We also want the fact that this works is going on to be made known to the New Zealand computer science community at large.Publication Providing integrated support for multiple development notations(Working Paper, 1994-11) Grundy, John C.; Venable, John R.A new method for providing integrated support for multiple development notations (including analysis, design, and implementation) within Information Systems Engineering Environments (ISEEs) is described. This method supports both static integration of multiple notations and the implementation of dynamic support for them within an integrated ISEE. First, conceptual data models of different analysis and design notations are identified and modelled, which are then merged into an integrated conceptual data model. Second, mappings are derived from the integrated conceptual data model, which translate data changes in one notation to appropriate data changes in the other notations. Third, individual ISEEs for each notation are developed. Finally, the individual ISEEs are integrated via an integrated data dictionary based on the integrated conceptual data model and mappings. An environment supporting integrated tools for Object-Oriented Analysis and Extended Entity-Relationship diagrams is described, which has been built using this technique.Publication The architecture of an optimistic CPU: the WarpEngine(Working Paper, 1994-09) Cleary, John G.; Pearson, Murray W.; Kinawi, HusamThe architecture for a shared memory CPU is described. The CPU allows for parallelism down to the level of single instructions and is tolerant of memory latency. All executable instructions and memory accesses are time stamped. The TimeWarp algorithm is used for managing synchronisation. This algorithm is optimistic and requires that all computations can be rolled back. The basic functions required for implementing the control and memory system used by TimeWarp are described. The memory model presented to the programmer is a single linear address space modified by a single thread of control. Thus, at the software level there is no need for explicit synchronising actions when accessing memory. The physical implementation, however, is multiple CPUs with their own caches and local memory with each CPU simultaneously executing multiple threads of control.Publication Data transformation: a semantically-based approach to function discovery(Working Paper, 1994-08) Phan, Thong H.; Witten, Ian H.This paper presents the method of data transformation for discovering numeric functions from their examples. Based on the idea of transformations between functions, this method can be viewed as a semantic counterpart to the more common approach of formula construction used in most previous discovery systems. Advantages of the new method include a flexible implementation through the design of transformation rules, and a sound basis for rigorous mathematical analysis to characterize what can be discovered. The method has been implemented in a discovery system called "LINUS," which can identify a wide range of functions: rational functions, quadratic relations, and many transcendental functions, as well as those that can be transformed to rational functions by combinations of differentiation, logarithm and function inverse operations.Publication Survival of the species vs survival of the individual(Working Paper, 1994-08) Barbour, Robert H.; Hopper, KeithThis paper examines the relationships between human and computing entities. It develops the biological ethical imperative towards survival into a study of the forms inherent in human beings and implied in computer systems. The theory of paradoxes is used to show that a computer system cannot in general make a self-referential decision. Based upon this philosophical analysis it is argued that human and machine forms of survival are fundamentally different. Further research into the consequences of this fundamental difference is needed to ensure the diversity necessary for human survival.Publication Applying machine learning to agricultural data(Working Paper, 1994-07) McQueen, Robert J.; Garner, Stephen R.; Nevill-Manning, Craig G.; Witten, Ian H.Many techniques have been developed for abstracting, or "learning," rules and relationships from diverse data sets, in the hope that machines can help in the often tedious and error-prone process of acquiring knowledge from empirical data. While these techniques are plausible, theoretically well-founded, and perform well on more or less artificial test data sets, they stand or fall on their ability to make sense of real-world data. This paper describes a project that is applying a range of learning strategies to problems in primary industry, in particular agriculture and horticulture. We briefly survey some of the more readily applicable techniques that are emerging from the machine learning research community, describe a software workbench that allows users to experiment with a variety of techniques on real-world data sets, and detail the problems encountered and solutions developed in a case study of dairy herd management in which culling rules were inferred from a medium-sized database of herd information.Publication WEKA machine learning project: cow culling(Working Paper, 1994-07) De War, Rhys; Neal, Donna LianeThis report describes an investigation into the application of machine learning tools in the area of agricultural database information. The Weka workbench is a set of machine learning software tools with a common data input and operation interface which has been developed by a research team at the University of Waikato, Department of Computer Science. An extract of a database containing information on dairy cows was processed by various tools in the Weka workbench over a three month period in early 1994.Publication The architecture of an optimistic CPU: the WarpEngine(Working Paper, 1994-07) Cleary, John G.; Pearson, Murray W.; Kinawi, HusamThe architecture for an optimistic, highly parallel, scalable, shared memory CPU - the WarpEngine - is described. The WarpEngine CPU allows for parallelism down to the level of single instructions and is tolerant of memory latency. Its design is based around time stamping executable instructions and all memory accesses. The TimeWarp algorithm [Jefferson 1985, 1989] is used for managing the time stamps and synchronisation. This algorithm is optimistic and requires that all computations can be rolled back. The basic functions required for implementing the control and memory system used by TimeWarp are described. The WarpEngine memory model presented to the programmer, is a single linear address space which is modified by a single thread of execution. Thus, at the software level there is no need for locks or other explicit synchronising actions when accessing the memory. The actual physical implementation, however, is multiple CPUs with their own caches and local memory with each CPU simultaneously executing multiple threads of control. Reads from memory are optimistic, that is, if there is a local copy of a memory location it is taken as the current value. However, sometimes there will be a write with an earlier time stamp in transit in the system. When it arrives it causes the original read and any dependent calculations to be re-executed.Publication Navigating the virtual library: a 3D browsing interface for information retrieval(Working Paper, 1994-07) Rogers, Bill; Cunningham, Sally Jo; Holmes, GeoffreyAn interface is described for graphically navigating a large collection of documents, as in a library. Its design is based on the metaphor of traversing a landscape. Documents are depicted as buildings, clustered to form 'towns'. A network of 'roads' connects these towns according to the classification hierarchy of the document set. A three-dimensional scene rendering technique allows the user to view this landscape from different perspectives, and at different levels of detail. At one level, the appearance of the buildings provides information like document size and age, at a glance. At higher levels, we provide the user with a visualisation of the structure and extent of the document set that is impossible with a traditional 'shelf' presentation. At all levels, a sense of physical context is maintained, encouraging and supporting browsing.Publication WEKA: a machine learning workbench(Working Paper, 1994-07) Holmes, Geoffrey; Donkin, Andrew; Witten, Ian H.Weka is a workbench for machine learning that is intended to aid in the application of machine learning techniques to a variety of real-world problems, in particular, those arising from agricultural and horticultural domains. Unlike other machine learning projects, the emphasis is on providing a working environment for the domain specialist rather than the machine learning expert. Lessons learned include the necessity of providing a wealth of interactive tools for data manipulation, result visualization, database linkage, and cross-validation and comparison of rule sets, to complement the basic machine learning tools.Publication A calculator for supporting derivation in constructive type-theory: PICTCalc(Working Paper, 1994-06) Reeves, StevePICTCalc is an interactive program written in LPA Prolog which has encoded within it the rules of Martin-Löf's constructive type theory (CTT), a formal system based on the constructive or intuitionistic mathematics of Brouwer, Heyting and others. It allows us to specify and express any total, computable function, so from a computer science point of view we can write both specifications and programs, along with the derivations which lead from one to the other, in a single language. PICTCalc is a more recent version of MacPICT which is itself a reconstruction of PICT [Ham92] and is intended as a test-bed for providing formal support for work within CTT. Many of the developments and improvements were suggested by students since they used the system to work on substantial courseworks. As we shall see, PICTCalc can be used to assist in the development of derivations in CTT and so it is called a derivation assistant (DA). In this paper I show how PICTCalc can be used for supporting derivations in CTT and consider what current experience suggests for future improvement. The examples in this paper will not require any knowledge of CTT since the meaning will either be clear to anyone with experience of logic and programming notations in general or will be explained as necessary.Publication On the insecurity of arithmetic coding(Working Paper, 1994-06) Cleary, John G.; Irvine, Sean A.; Rinsma-Melchert, IngridArithmetic coding is a technique which converts a given probability distribution into an optimal code and is commonly used in compression schemes. The use of arithmetic coding as an encryption scheme is considered. The simple case of a single binary probability distribution with a fixed (but unknown) probability is considered. We show that for a chosen plaintext attack w+ 2 characters is sufficient to uniquely determine a w-bit probability. For many known plaintexts w+ m+ O(log m) symbols where mis the length of an initial sequence containing just one of (the two possible) symbols is sufficient. It is noted that many extensions to this basic scheme are vulnerable to the same attack provided the arithmetic coder can be repeatedly reset to its initial state. If it cannot be reset then their vulnerability remains an open question.Publication Collaborative, integrated software development with multiple views(Working Paper, 1994-05) Grundy, John C.; Hosking, John G.; Mugridge, Warwick B.; Armor, Robert W.This paper presents a new model for supporting collaborative, integrated software development utilising multiple textual and graphical views. Views can be asynchronously edited by different developers using separate versions. Versions can be incrementally merged, with merge conflicts detected and presented. Synchronous editing of views by different developers is also supported. View updates are broadcast to other users and are incrementally incorporated as required in their alternative versions. The new model is illustrated by its use in a software development environment for an object-oriented language.Publication MiraCalc: the Miranda Calculator, the Unix version(Working Paper, 1994-04) Goldson, Doug; Hopkins, Mike; Reeves, SteveThose of you who already have some experience of programming, or experience of simply using a computer, will know that computers can be very unforgiving. They are fussy, and unless you get things exactly right they will complain. The program described in this document has grown out of an attempt to help you to understand what is going on when the computer complains. It is designed to help you with the Miranda scripts that you will be writing as part of the process of learning Miranda (or indeed any other similar functional programming language like Gofer or Haskell).Publication Constructing integrated software development environments with dependency graphs(Working Paper, 1994-03) Grundy, John C.; Hosking, John G.Integrated software development environments need to support multiple textual and graphical views of software products under development. MViews, a new model for constructing such environments, provides abstractions for representing the abstract syntax of a program as graphs and for viewing and manipulating these graphs in concrete textual and graphical forms. Graphs are used to represent software system structures using components (graph nodes) and relationships (graph edges). These graph components are modified by graph operations to construct and modify a program. Views of these graph components are rendered and manipulated in either graphical or textual forms. Consistency management between updated graph components is supported by a novel update record mechanism. MViews graphs are dependency graphs: updates to graph components are broadcast to related components as update records. These dependent components, or the inter-connecting relationships, respond to these update records and update the dependent components appropriately. This mechanism is used to support inter-component consistency management, and in particular provides a novel way keeping textual and graphical views of software development consistent. This mechanism can also be used as the basis of a wide range of other software development environment facilities. MViews has been reused to implement a variety of integrated environments and examples of these environments are discussed.Publication Chinks in the armor of public key cryptosystems(Working Paper, 1994-03) Wilson, William J.Potential weaknesses in public key cryptosystem design and use are identified with emphasis on a particular vulnerability resulting from the encryption of ordinary natural language plaintext. This weakness occurs when an insufficiently long block length is used to encrypt low entropy natural language and ordinary numeric plaintext rendered in 8-bit character sets such as ASCII or EBCDIC. A computer-assisted, semi-exhaustive chosen plaintext attack is defined and shown to defeat such systems. Several methods are suggested for thwarting such attacks by maximizing input plaintext entropy prior to encryption.Publication The induction and professional development of academics(Working Paper, 1994-02) Barbour, Robert H.This paper makes suggestions for the induction and professional development of staff at the University of Waikato. The context of the University as a community of scholars and administrators is outlined. A number of possible induction strategies are put forward for consideration in text and diagrammatic form.Publication Character-less programming(Working Paper, 1994-02) Hopper, Keith; Barbour, Robert H.This paper proposes a mechanism for the definition and implementation of programming languages. Culturally-dependent aspects of the definition, such as the language and character set, can be separated from the process of translating programs and from the execution of a translated program.