E1AR0002@SMUVM1.BITNET (03/05/86)
-----------------------------------------------------------------------------
Technical Reports
Department of Computer Science
University of Melbourne
This is a list of Technical Reports from the Department of Computer Science
at the University of Melbourne from 1980 to the present. To obtain copies of
the reports, write to:
Technical Reports Secretary
Department of Computer Science
University of Melbourne
Parkville, Victoria, 3052
AUSTRALIA
or E-mail to:
CSNET: techreps%mulga.oz@australia
ARPA: techreps%mulga.oz@seismo.css.gov
UUCP: {seismo,ukc,ubc-vision,mcvax}!munnari!mulga!techreps
Please note that some of the reports (notably those dealing with Titan, and
the Logic Programming Bibliography) are covered by copyright and cannot be
obtained directly from the Department.
-----------------------------------------------------------------------------
%A Prabhaker Mateti
%T Specification Schema for Indenting Programs
%R Technical Report 80/1
%I Department of Computer Science, University of Melbourne
%D September 1980
%P 30
%K verification, functional specifications, correctness proofs,
pretty printing,pascal
%O also in Software - Practice and Experience
%X
A two level specification of the functional behaviour of a class of
indenting programs for Pascal is presented. The transformation that these
programs perform on the input text is a composition of splitting input
lines, altering the blank space between lexical tokens and computing the
margin required in front of each of the split lines. The high level
specification is given as a stylised Pascal grammar in extended BNF.
In contrast, the low level specifications, which are operationally closer
to a program, and which define how syntactically invalid text is dealt with,
require several mathematical functions which capture the essence of these
basic transformations. The specfications for an indeting program for Pascal
are then obtained as a further elaboration of these functions. Most
indentation styles appearing in the literature can be specified with
precision using the methods developed in this paper. Our experience in
this case study indicates that while specifications for real-life programs
can be given using simple mathematics, the effort required is still
considerable.
%A Prabhaker Mateti
%T Correctness Proof of an Indenting Program
%R Technical Report 80/2
%I Department of Computer Science, University of Melbourne
%D September 1980
%P 59
%K verification, correctness proof, pretty printing, pascal
%O also in Software - Practice and Experience
%X
The correctness of an indenting program for Pascal is proven at an
intermediate level of rigour. The specifications of the program are given
in the companion paper [TR 80/1]. The program is approximately 330 lines
long and consists of four modules: io, lex, stack, and indent. We prove
first that the individual procedures contained in these modules meet their
specifications as given by the entry and exit assertions. A global proof
of the main routine then establishes that the interaction between modules
is such that the main routine meets the specifcation of the entire program.
We argue that correctness proofs at the level of rigour used here serve
very well to transfer one's understanding of a program to others. We believe
that proofs at this level should become commonplace before more formal
proofs can take over to reduce traditional testing to an inconsequential
place.
%A John W. Lloyd
%T Optimal Partial-match Retrieval
%R Technical Report 80/3
%I Department of Computer Science, University of Melbourne
%D September 1980
%P 14
%K partial match retrieval, file design, secondary key retrieval
%O also in BIT, vol.20, 1980
%X
This paper studies the design of a system to handle partial-match
queries from a file. A partial-match query is a specification of the value
of zero or more fields in a record. An answer to a query consists of a listing
of all records in a file satisfying the values specified.
Aho and Ullman have considered the case when the probability that a
field is specified in a query is independent of which other fields are
specified. We consider here the more realistic case where the independence
assumption is dropped. This leads to an optimisation problem more general
than that considered by Aho and Ullman. The major part of the paper is the
presentation of an efficient algorithm for solving this optimisation problem.
%A John W. Lloyd
%T Partial-match Retrieval for Dynamic Files
%R Technical Report 80/4
%I Department of Computer Science, University of Melbourne
%D September 1980
%P ?
%K partial match retrieval, file design, secondary key retrieval
%A Jean-Louis Lassez
%T Transfinite Computational Induction and a Dual Problem to Least Fixed Points
%R Technical Report 80/5
%I Department of Computer Science, University of Melbourne
%D December 1980
%P 30
%K theory of computation, fixed-points
%O also in Theoretical Computer Science, vol.16, 1981
%A Joxan Jaffar
%T Presburger Arithmetic with Array Segments
%R Technical Report 81/1
%I Department of Computer Science, University of Melbourne
%D January 1981
%P 8
%K verification, assertion language, decision procedure
%A Kotagiri Ramamohanarao
%T Hardware Address Translation for Machines with a Large Virtual Memory
%R Technical Report 81/2
%I Department of Computer Science, University of Melbourne
%D February 1981
%P 18
%K address translation, hashing, virtual memory, rao
%O also in Information Processing Letters, vol.13, 1981
%A John W. Lloyd
%T An Introduction to Deductive Database Systems
%R Technical Report 81/3
%I Department of Computer Science, University of Melbourne
%D April 1981 (revised April 1983)
%P 24
%K prolog
%O also in Australian Computer Journal, vol.15, 1983
%X
This paper gives a tutorial introduction to deductive database systems.
Such systems have developed largely from the combined application of the
ideas of logic programming and relational databases. The elegant theoretical
framework for deductive database systems is provided by first order logic.
Logic is used as a uniform language for data, programs, queries, views
and integrity constraints. It is stressed that it is possible to build
practical and efficient database systems using these ideas.
%A John W. Lloyd
%T Implementing Clause Indexing for Deductive Database Systems
%R Technical Report 81/4
%I Department of Computer Science, University of Melbourne
%D October 1981
%P 22
%K partial match retrieval, prolog
%X
The paper presents a file design for handling partial-match
queries which has wide application to knowledge-based artificial
intelligence systems and relational database systems. The
advantages of the design are simplicity of implementation, the
ability to cope with dynamic files and the ability to optimize
performance with respect to the average number of disk access
required to answer a query.
%A John W. Lloyd
%A Kotagiri Ramamohanarao
%T Partial-match Retrieval for Dynamic Files
%R Technical Report 81/5
%I Department of Computer Science, University of Melbourne
%D September 1981
%P 18
%K partial-match retrieval, dynamic files, extendible hashing,
linear hashing, rao
%X
This paper studies file designs for answering partial-match queries
for dynamic files. A partial-match query is a specification of the
value of zero or more fields in a record. An answer to a query
consists of a listing of all records in the file satisfying the values
specified.
The main contribution is a general method whereby certain primary
key hashing schemes can be extended to partial-match retrieval schemes.
These partial-match retrieval designs can handle arbitrarily dynamic
files and can be optimized with respect to the number of page faults
required to answer a query.
We illustrate the method by considering in detail the extension of two
recent dynamic primary key hashing schemes.
%A Kotagiri Ramamohanarao
%A John W. Lloyd
%T Dynamic Hashing Schemes
%R Technical Report 81/6
%I Department of Computer Science, University of Melbourne
%D January 1982
%P 29
%K hashing, primary key, dynamic file, rao
%O also in The Computer Journal, vol.25, 1982
%X
In this paper, we study two new dynamic hashing schemes for
primary key retrieval. The schemes are related to those
of Scholl, Litwin and Larson. The first scheme is
simple and elegant and has certain performance advantages over
earlier schemes. We give a detailed mathematical analysis of this
scheme and also present simulation results. The second scheme is
essentially that of Larson. However, we have made a number of changes
which simplify his scheme.
%A Joxan Jaffar
%A Jean-Louis Lassez
%T A Decision Procedure for Theorems about Multisets
%R Technical Report 81/7
%I Department of Computer Science, University of Melbourne
%D July 1981
%P 37
%K automatic theorem proving, verification, domain dependent reasoning
%A Kotagiri Ramamohanarao
%A John W. Lloyd
%A James A. Thom
%T Partial-match Retrieval using Hashing and Descriptors
%R Technical Report 82/1
%I Department of Computer Science, University of Melbourne
%D February 1982
%P 39
%K deductive databases, partial match retrieval, hashing, descriptors,
dynamic file, optimization, rao
%O also in ACM Transactions on Database Systems, vol.8, 1983
%X
This paper studies a partial-match retrieval scheme based on hash
functions and descriptors. The emphasis is placed on showing how
the use of a descriptor file can improve the performance of the
scheme. Records in the file are given addresses according to hash
functions for each field in the record. Furthermore, each page of
the file has associated with it a descriptor, which is a fixed length
bit string, determined by the records actually present in the page.
Before a page is accessed to see if it contains records in the
answer to a query, the descriptor for the page is checked. This
check may show that no relevant records are on the page and hence, the
page does not have to be accessed. The method is shown to have a very
substantial performance advantage over pure hashing schemes, when
some fields in the records have large key spaces. A mathematical
model of the scheme, plus an algorithm for optimizing performance, is
given.
%A Lee Naish
%T An Introduction to MU-Prolog
%R Technical Report 82/2
%I Department of Computer Science, University of Melbourne
%D March 1982 (Revised July 1983)
%P 16
%K prolog, muprolog, logic programming, control, negation
%X
As a logic programming language, PROLOG is deficient in two areas:
negation and control facilities. Unsoundly implemented negation
affects the correctness of programs and poor control facilities
affect the termination and efficiency. These problems are illustrated
by examples.
MU-PROLOG is then introduced. It implements negation soundly and
has more control facilities. Control information can be added
automatically. This can be used to avoid infinite loops and find
efficient algorithms from simple logic. MU-PROLOG is closer to the
ideal of logic programming.
%A Elizabeth A. Sonenberg
%T Using Computers in Teaching Mathematics and Statistics:
A Selected Introduction
%R Technical Report 82/3
%I Department of Computer Science, University of Melbourne
%D April 1982
%P 13
%K computer aided assisted learning instruction
%A Joseph Stoegerer
%T An Annotated Bibliography of Software Engineering
Emphasising Software Systems Analysis and Design Aspects
%R Technical Report 82/4
%I Department of Computer Science, University of Melbourne
%D June 1982
%P 126
%K reqirements, analysis, design, development methodologies,
software management, human aspects, structured programming,
programming methodologies, testing, debugging, maintenance
%A Joseph Stoegerer
%T Specification Languages - A Survey
%R Technical Report 82/5
%I Department of Computer Science, University of Melbourne
%D June 1982
%P 62
%K software specification, requirements languages, software development tools,
integrated software development support systems, non-procedural languages,
automated analysis tools
%A Jean-Louis Lassez
%A Michael J. Maher
%T Chaotic Semantics of Programming Logic
%R Technical Report 82/6
%I Department of Computer Science, University of Melbourne
%D July 1982
%P 26
%K theory, fixed points, fixed-points
%A John W. Lloyd
%T Foundations of Logic Programming
%R Technical Report 82/7
%I Department of Computer Science, University of Melbourne
%D September 1982 (revised May 1983)
%P 57
%K theory
%O an extended version appeared as Foundations
%A Richard G. Hamlet
%T Theoretical Issues in Software Engineering
%R Technical Report 82/8
%I Department of Computer Science, University of Melbourne
%D September 1982
%P 28
%K software engineering, testing theory, software development, specification
%A Trevor I. Dix
%T Exceptions and Interrupts in CSP
%R Technical Report 82/9
%I Department of Computer Science, University of Melbourne
%D October 1982
%P ?
%K ?
%A Ron Sacks-Davis
%A Kotagiri Ramamohanarao
%T A Two-Level Superimposed Coding Scheme for Partial-match Retrieval
%R Technical Report 82/10
%I Department of Computer Science, University of Melbourne
%D November 1982
%P 17
%K deductive databases, rao
%O also in Information Systems, vol.8, 1983
%A James A. Thom
%A Peter G. Thorne
%T Deductive Databases and the Nature of Personal Information
%R Technical Report 82/11
%I Department of Computer Science, University of Melbourne
%D October 1982
%P 17
%K human factors, legal aspects, security, privacy, deductive database,
personal information, implicit information
%O a revised version appeared as Privacy Legislation and the Right of
Access'' in Australian Computer Journal, vol.15, 1983
%A Ian G. Richards
%T Unifying Software Objects
%R Technical Report 82/12
%I Department of Computer Science, University of Melbourne
%D December 1982
%P 13
%K object oriented programming, virtual memory, operating systems,
file system, module, software engineering protection
%X
A model is proposed for the structure and protection of software
objects which reside in a large virtual memory. A possible
implementation of the model is briefly mentioned and then the
operating system facilities to manage such objects are described.
The applicability of the model to various traditional software
objects, eg. programs, files, subroutine libraries, operating system
modules, is discussed.
%A Richard G. Hamlet
%T Testing of Concurrent Programs and Partial Specifications
%R Technical Report 82/13
%I Department of Computer Science, University of Melbourne
%D December 1982
%P 12
%K software engineering, testing concurrent systems
%A Richard G. Hamlet
%T An Overview of Program Testing
%R Technical Report 82/14
%I Department of Computer Science, University of Melbourne
%D December 1982
%P 9
%K software engineering, testing theory, testing practice
%A Richard G. Hamlet
%T Three Approaches to Testing Theory
%R Technical Report 82/15
%I Department of Computer Science, University of Melbourne
%D December 1982
%P 12
%K software engineering, testing specifications, program correctness
%A Richard G. Hamlet
%T Step-wise Debugging
%R Technical Report 82/16
%I Department of Computer Science, University of Melbourne
%D December 1982
%P 10
%K software engineering, stepwise refinement, program testing, module testing
%A Joxan Jaffar
%A Jean-Louis Lassez
%A John W. Lloyd
%T Completeness of the Negation-as-failure Rule
%R Technical Report 83/1
%I Department of Computer Science, University of Melbourne
%D January 1983
%P 20
%O also in Proceedings of the Eigth International Joint Conference
on Artificial Intelligence, Karlsruhe, Germany, 1983
%K logic programming theory, finite failure, completion of a program
%X
Let P be a Horn clause logic program and comp(P) be its completion in the
sense of Clark. Clark gave a justification for the negation as failure rule
by showing that if a ground atom A is in the finite failure set of P, then
~A is a logical consequence of comp(P), that is, the negation as failure
rule is sound. We prove here that the converse also holds, that is, the
negation as failure rule is complete.
%A Elizabeth A. Sonenberg
%T The use of Matrix'' in Mathematics Courses: Part I
%R Technical Report 83/2
%I Department of Computer Science, University of Melbourne
%D January 1983
%P 44
%K computer assisted aided learning teaching
%A Jean-Louis Lassez
%A Michael J. Maher
%T Closures and Fairness in the Semantics of Logic Programming
%R Technical Report 83/3
%I Department of Computer Science, University of Melbourne
%D March 1983
%P 17
%K semantics, chaotic iteration, SLD resolution, finite failure, Prolog
%O also in Theoretical Computer Science, vol.29, 1984
%A Jean-Louis Lassez
%A Michael J. Maher
%T Optimal Fixedpoints of Logic Programming
%R Technical Report 83/4
%I Department of Computer Science, University of Melbourne
%D March 1983
%P 15
%K theory, semantics
%O also in Theoretical Computer Science, vol.30, 1985
%X
From a declarative programming point of view, Manna and Shamir's
optimal fixedpoint semantics is more appealing than the least
fixedpoint semantics. However in standard formalisms of recursive
programming the optimal fixedpoint is not computable while the least
fixedpoint is. In the context of logic programming we show that the
optimal fixedpoint is equal to the least fixedpoint and is computable.
Furthermore the optimal fixedpoint semantics is consistent with Van Emden
and Kowalski's semantics of logic programs.
%A Trevor I. Dix
%T Preemptive Guards in CSP
%R Technical Report 83/5
%I Department of Computer Science, University of Melbourne
%D May 1983
%P 14
%K preemption, exception, interrupt, communicating sequential processes, concurr
ent processes
%A Lee Naish
%T Automatic Generation of Control for Logic Programming
%R Technical Report 83/6
%I Department of Computer Science, University of Melbourne
%D July 1983 (Revised September 1984)
%P 24
%K prolog muprolog, control facilities, coroutines, automatic programming
%O also as Automating Control for Logic Programs'' in Journal of Logic Progrmm
ing, vol.5, 1985
%X
A model for the coroutined execution of PROLOG programs is presented
and two control primitives are described. Heuristics for the control
of database and recursive procedures are given, which lead to algorithms
for generating control information. These algorithms can be incorporated
into a pre-processor for logic programs. It is argued that automatic
generation should be an important consideration when designing control
primitives and is a significant step towards simplifying the task of
programming.
%A Kotagiri Ramamohanarao
%A Glenn A. Farrall
%T A Cache for Non-aligned Accesses in Large Virtual Address Spaces
%R Technical Report 83/7
%I Department of Computer Science, University of Melbourne
%D September 1983
%P 25
%K performance, vitrual memory, prefetching, translation lookahead buffer, rao
%A Isaac Balbin
%T A Users Guide to FSL
%R Technical Report 83/8
%I Department of Computer Science, University of Melbourne
%D September 1983
%P 52
%K office automation forms specification language tps
%X ?
%A Christopher J. Stuart
%T Transaction Processing in a Multi-user Environment using Forms
%R Technical Report 83/9
%I Department of Computer Science, University of Melbourne
%D September 1983
%P 65
%K office automation tps
%X ?
%A Lee Naish
%A James A. Thom
%T The MU-Prolog Deductive Database
%R Technical Report 83/10
%I Department of Computer Science, University of Melbourne
%D November 1983
%P 16
%K prolog, muprolog, partial match retrieval, unix
%X
This paper describes the implementation and an application of a
deductive database being developed at the University of Melbourne.
The system is implemented by adding a partial match retrieval system
to the MU-PROLOG interpreter.
%A Alain Legrand
%T Automatic Routing for VLSI in a Hierachical Design Environment
%R Technical Report 83/11
%I Department of Computer Science, University of Melbourne
%D December 1983
%P 20
%K MOS IC processing, layout, chip design
%A David A. Wolfram
%A Jean-Louis Lassez
%A Michael J. Maher
%T A Unified Treament of Resolution Strategies for Logic Programs
%R Technical Report 83/12
%I Department of Computer Science, University of Melbourne
%D December 1983
%P 25
%K soundness, completeness, unification, negation as failure
%O also in Proceedings of the Second International Logic Programming Confernce,
Uppsala, Sweden, 1984
%A Elizabeth A. Sonenberg
%T The use of Matrix'' in Mathematics Courses: Part II
%R Technical Report 83/13
%I Department of Computer Science, University of Melbourne
%D December 1983
%P 29
%K computer assisted aided learning teaching
%A Lee Naish
%T Heterogeneous SLD Resolution
%R Technical Report 84/1
%I Department of Computer Science, University of Melbourne
%D January 1984
%P 11
%K logic programming, PROLOG, resolution, control facilities, intelligent backtr
acking
%O also in Journal of Logic Programming, vol.4, 1984
%X Due to a significant oversight in the definition of computation rules,
the current theory of SLD resolution is not general enough
to model the behaviour of some PROLOG implementations with advanced
control facilities.
In this paper, Heterogeneous SLD resolution is defined.
It is an extension of SLD resolution which increases the \*(lqdon't care\*(rq
non-determinism of computation
rules and can decrease the size of the search space.
Soundness and completeness, for success and finite failure, are
proved using similar results from SLD resolution.
Though Heterogeneous SLD resolution was originally devised to model current
systems, it can be exploited more fully than it is now.
As an example, an interesting new computation rule is described. It can be seen
as a simple form of intelligent backtracking with few overheads.
%A Mark S. Davoren
%T The Portability of the Unix Operating System
%R Technical Report 84/2
%I Department of Computer Science, University of Melbourne
%D March 1984
%P 21
%K software engineering, unix history
%X The properties which affect the portability of Unix system and
in particular the Unix kernel are studied. A history of Unix is
presented and a number of ports are studied to locate those areas
of the operating system which are particularly machine dependent
and to predict the future trends in Unix's portability. A guide to
porting Unix is presented which contains a suggested sequence of
steps aimed at reducing the effort required to port Unix.
%A Koenraad Lecot
%A Isaac Balbin
%T Prolog & Logic Programming Bibliography
%R Technical Report 84/3
%I Department of Computer Science, University of Melbourne
%D May 1984
%P 55
%K classified bibliography
%O a considerably expanded version appeared as Logic Programming:
A Classified Bibliography'', Wildgrass Books, 1985
%A Lee Naish
%T All Solutions Predicates in Prolog
%R Technical Report 84/4
%I Department of Computer Science, University of Melbourne
%D June 1984
%P 15
%K logic programming, negation, coroutines
%O also in Proceedings of IEEE Symposium on Logic Programming, Boston, 1985
%A Michael J. Maher
%A Jean-Louis Lassez
%A Kmball G. Marriott
%T Antiunification
%R Technical Report 84/5
%I Department of Computer Science, University of Melbourne
%I Department of Computer Science, University of Melbourne
%D to appear
%P ?
%K logic programming theory, unification
%A Lee Naish
%A Jean-Louis Lassez
%T Most Specific Logic Programs
%R Technical Report 84/6
%I Department of Computer Science, University of Melbourne
%D to appear
%P ?
%K ?
%A Rodney W. Topor
%A Teresa Keddis
%A Derek W. Wright
%T Deductive Database Tools
%R Technical Report 84/7
%I Department of Computer Science, University of Melbourne
%D June 1984 (revised August 1985)
%P 27
%K database management, deductive database, query language,
integrity constraint, logic programming, Prolog
%O also in Australian Computer Journal, vol.?, 1985
%X
A deductive database is a database in which data can be represented
both explicitly by facts and implicitly by general rules. The use of
typed first order logic as a definition and manipulation language for
such deductive databases is advocated and illustrated by examples.
Such a language has a well-understood theory and provides a uniform
notation for data, queries, integrity constraints, views and programs.
We present algorithms for implementing domains, for using atoms with
named attributes, for evaluating queries, and for checking static and
transition integrity constraints. The implementation is by translation
into Prolog and can be performed using a standard Prolog system. The
paper assumes some familiarity with relational databases, logic and Prolog.
%A John W. Lloyd
%A Rodney W. Topor
%T Making Prolog More Expressive
%R Technical Report 84/8
%I Department of Computer Science, University of Melbourne
%D June 1984
%P 22
%K first order logic, programming in logic, deductive databases,
query language
%O also in Journal of Logic Programming, vol.4, 1984
%X This paper introduces extended programs and extended goals for logic
programming. A clause in an extended program can have an arbitrary first
order formula as its body. Similarly, an extended goal can have an arbitrary
first order formula as its body. The main results of the paper are the
soundness of the negation as failure rule and SLDNF-resolution for extended
programs and goals. We show how the increased expressibility of extended
programs and goals can be easily implemented in any PROLOG system which has
a sound implementation of the negation as failure rule. We also show how
these ideas can be used to implement first order logic as a query language
in a deductive database system. An application to integrity constraints in
deductive database systems is also given.
%A James A. Thom
%A Peter G. Thorne
%T Privacy, Technological Change and Law Reform
%R Technical Report 84/9
%I Department of Computer Science, University of Melbourne
%D July 1984
%P 27
%K personal information, privacy principles, data protection,
freedom of information, deductive databases, free text retrieval,
distributed databases
%A Jacek Gibert
%T J-Machine User's Manual
%R Technical Report 84/10
%I Department of Computer Science, University of Melbourne
%D November 1984
%P 42
%K functional programming, graph reduction machines, combinators
%X
This manual describes an experimental software implementation of a
combinatory reduction machine called the J-Machine. The J-Machine is
mainly oriented towards symbol manipulation and it aims at exposing
flows of data, and a high degree of parallelism in ordinary functional
programs. It executes directly the J'' reduction language which is
based upon a variant of the full combinatory theory. The J'' language
has an associated algebra of functions which allows a user to prove
properties of functional programs with the assistance of the J-Machine.
With the advent of hardware concepts like data driven reduction
architectures, VLSI implementation of the J-Machine appears to be an
attractive proposition. But at the present, the J-Machine is an
interactive interpreter written in the C programming language under
the Unix operating system.
%A Kotagiri Ramamohanarao
%A Ron Sacks-Davis
%T Partial-match Retrieval using Recursive Linear Hashing
%R Technical Report 84/11
%I Department of Computer Science, University of Melbourne
%D September 1984
%P 12
%K partial match retrieval, dynamic files, rao
%A Ian G. Richards
%A K. Robert Elz
%T Implementation of an X.25 Interface to AUSTPAC
%R Technical Report 84/12
%I Department of Computer Science, University of Melbourne
%D to appear
%P 25
%K Networks, VAX, UNIX, X.25
%X
Details are presented of the implementation of hardware and
software to allow a Unix host to interwork with other hosts over
the AUSTPAC X.25 Network. The hardware comprises a Motorola 68000
based interface to a Digital Equipment VAX 11/780 or PDP11 via its
UNIBUS. The interface uses a Western Digital LAPB chip to implement
the Link Level X.25 protocol. Software running on the MC68000
implements the Network Level.
%A Lee Naish
%T Prolog Control Rules
%R Technical Report 84/13
%I Department of Computer Science, University of Melbourne
%D September 1984
%P 12
%K logic programming, computational rules
%O a shortened version appeared in Proceedings of the International
Joint Conference on Artificial Intelligence, Los Angeles, 1985
%A Elizabeth A. Sonenberg
%T Computer Based Teaching Developments in the Departments of
Computer Science, Mathematics and Statistics: Final Report
%R Technical Report 84/14
%I Department of Computer Science, University of Melbourne
%D December 1984
%P 23
%K computer aided assisted learning instruction
%A Joxan Jaffar
%A Jean-Louis Lassez
%A Michael J. Maher
%T A Logic Programming Language Scheme
%R Technical Report 84/15
%I Department of Computer Science, University of Melbourne
%D November 1984
%P 22
%K theory, semantics
%O also appeared in Logic Programming: Relations, Functions and Equations'',
D.DeGroot and G.Lindstrom (eds.), Prentice-Hall, 1985
%X Numerous extended versions of PROLOG are now emerging. Im order to
provide greater versatility and expressive power, some versions allow
functional programming features, others allow infinite data structures.
However, there is concern that such languages may have little connection
left with logic. In some instances, various logical frameworks have been
proposed to solve this problem. Nevertheless, the crucial point has not
been addressed: the preservation of the unique semantic properties of
logic programs. The significance of our effort here is twofold:
(1) There is a natural logic programming language scheme wherein these
properties hold. (2) Formal foundations for extended versions of
traditional PROLOG can be obtained as instances of this scheme. They
automatically enjoy its properties.
%A T. Y. Chen
%A Jean-Louis Lassez
%A Graeme S. Port
%T Maximal Unifiable Subsets and Minimal Non-unifiable Subsets
%R Technical Report 84/16
%I Department of Computer Science, University of Melbourne
%D November 1984
%P 20
%K unification, backtracking, resolution
%A John W. Lloyd
%A Rodney W. Topor
%T A Basis for Deductive Database Systems
%R Technical Report 85/1
%I Department of Computer Science, University of Melbourne
%D February 1985 (revised April 1985)
%P 22
%K logic programming, first order logic, soundness, integrity constraints
%X
This paper provides a theoretical basis for deductive database systems.
A deductive database consists of closed typed first order logic formulas
of the form A<-W, where A is an atom and W is a typed first order formula.
A typed first order formula can be used as a query and a closed typed first
order formula can be used as an integrity constraint. Functions are allowed
to appear in formulas. Such a deductive database system can be implemented
using a PROLOG system. The main results are the soundness of the query
evaluation process, the soundness of the implementation of integrity
constraints, and a simplification theorem for implementing integrity
constraints. A short list of open problems is also presented.
%A Kotagiri Ramamohanarao
%A Ron Sacks-Davis
%T Partial-match retrieval for Dynamic Files using Linear Hashing
with Partial Expansions
%R Technical Report 85/2
%I Department of Computer Science, University of Melbourne
%D to appear
%P ?
%K recursive linear hashing, rao
%A Richard A. Helm
%A Catherine Lassez
%A Kimball G. Marriott
%T Prolog for Expert Systems: An Evaluation
%R Technical Report 85/3
%I Department of Computer Science, University of Melbourne
%D June 1985
%P 20
%K TEAS, MARLOWE, knowledge representation
%O also in Proceedings of Expert Systems in Government'', Virginia, 1985
%A Tony Boon Chuan Puah
%T IMAGE Version 2.1: The System
%R Technical Report 85/4
%I Department of Computer Science, University of Melbourne
%D June 1985
%P 33
%K interactive graph manipulation, UNIX, PC-DOS
%A Tony Boon Chuan Puah
%T IMAGE Version 2.1: User Manual
%R Technical Report 85/5
%I Department of Computer Science, University of Melbourne
%D June 1985
%P 69
%K interactive graph manipulation
%A John W. Lloyd
%A Rodney W. Topor
%T A Basis for Deductive Database Systems II
%R Technical Report 85/6
%I Department of Computer Science, University of Melbourne
%D February 1985 (revised April 1985)
%P 17
%K logic programming, first order logic, soundness, integrity constraints,
query evaluation
%X
This paper is the third in a series providing a theoretical basis for
deductive database systems. A deductive database consists of closed typed
first order logic formulas of the form A<-W, where A is an atom and W is a
typed first order formula. A typed first order formula can be used as a
query and a closed typed first order formula can be used as an integrity
constraint. Functions are allowed to appear in formulas. Such a deductive
database system can be implemented using a PROLOG system. The main results
of this paper are concerned with the non-floundering and completeness of
query evaluation. We also introduce an alternative query evaluation process
and show that corresponding versions of the earlier results can be obtained.
Finally, we summarize the results of the three papers and discuss the
attractive properties of the deductive database system approach based on
first order logic.
%A John F. Doolan
%A Michael C. Flower
%A Bernard J. Marshall
%A Ian W. Turnbull
%T Titan User's Manual
%R Technical Report 85/7
%I Department of Computer Science, University of Melbourne
%D September 1985
%P 89
%K partial match retrieval, interactive forms editor, PMR, IFE, MENU
%A John F. Doolan
%A Michael C. Flower
%A Bernard J. Marshall
%A Ian W. Turnbull
%T Titan Administrator's Manual
%R Technical Report 85/8
%I Department of Computer Science, University of Melbourne
%D September 1985
%P 133
%K partial match retrieval, interactive forms editor, PMR, IFE, MENU
%A Rohan McColl
%A Ian W. Turnbull
%T Titan User's Tutorial
%R Technical Report 85/9
%I Department of Computer Science, University of Melbourne
%D to appear
%P ?
%K partial match retrieval, interactive forms editor, PMR, IFE, MENU
%A Rohan McColl
%A Michael C. Flower
%T Tital Administrator's Tutorial
%R Technical Report 85/10
%I Department of Computer Science, University of Melbourne
%D to appear
%P ?
%K partial match retrieval, interactive forms editor, PMR, IFE, MENU
%A Lee Naish
%T The MU-Prolog 3.2 Reference Manual
%R Technical Report 85/11
%I Department of Computer Science, University of Melbourne
%D October 1985
%P 17
%K logic programming, Prolog
%X
MU-PROLOG is (almost) upward compatible with DEC-10 PROLOG, C-PROLOG
and (PDP-11) UNIX PROLOG. The syntax and built-in predicates are therefore
very similar. A small number of DEC-10 predicates are not available and
some have slightly different effects. There are also some MU-PROLOG
predicates which are not defined in DEC-10 PROLOG. However most DEC-10
programs should run with few, if any, alterations.
However, MU-PROLOG is not intended to be a UNIX PROLOG look-alike.
MU-PROLOG programs should be written in a more declarative style.
The non-logical predicates'' such as cut (!), \\=, not and var are
rarely needed and should be avoided. Instead, the soundly implemented
not (~), not equals (~=) and if-then-else should be used and wait
declarations should be added where they can increase efficiency.
This is a reference manual only, not a guide to writing PROLOG programs.
%A Lee Naish
%T Negation and Control in PROLOG
%R Technical Report 85/12
%I Department of Computer Science, University of Melbourne
%D September 1985
%P 108
%K logic programming, resolution, PhD thesis
%X
We investigate ways of bringing PROLOG closer to the ideals of logic
programming, by improving its facilities for negation and control.
The forms of negation available in conventional PROLOG systems are
implemented unsoundly, and can lead to incorrect solutions. We discuss
several ways in which negation as failure can be implemented soundly.
The main forms of negation considered are not'', not-equals'',
if-then-else'' and all solutions predicates. The specification and
implementation of all solutions predicates is examined in detail.
Allowing quantifiers in negated calls is an extension which is easily
implemented and we stress its desirability, for all forms of negation.
We propose other enhancements to current implementations, to prevent
the computation aborting or looping infinitely, and also outline
a new technique for implementing negation by program transformation.
Finally, we suggest what forms of negation should be implemented in
future PROLOG systems.
%A Lee Naish
%T Negation and Quantifiers in NU-Prolog
%R Technical Report 85/13
%I Department of Computer Science, University of Melbourne
%D October 1985
%P 12
%K logic programming, control
%X We briefly discuss the shortcomings of negation
in conventional Prolog systems. The design and implementation of the
negation constructs in NU-Prolog are then presented. The major difference
is the presence of explicit quantifiers. However, several other
innovations are used to extract the maximum flexibility from current
implementation techniques. These result in improved treatment of
\*(lqif\*(rq, existential quantifiers, inequality and non-logical primitives.
We also discuss how the negation primitives of NU-Prolog can be
added to conventional systems, and how they can improve the
implementation of higher level constructs.
%A Michael J. Maher
%T Semantics of Logic Programs
%R Technical Report 85/14
%I Department of Computer Science, University of Melbourne
%D September 1985
%P 77
%K logic programming theory, fixed points, fixedpoints, PhD thesis
%X
This thesis deals with the semantics of definite clause logic programs
in the presence of an equality theory.
Definite clauses are the formal foundation of the PROLOG
programming language.
Definitions of functions and abstract data types use equality.
Many have suggested the incorporation of these features
into a logic programming language
and already there are many of these languages.
This thesis provides a formal foundation for such languages.
The treatment consistently factors out the equality
theory to obtain the effect of a scheme:
any equality theory which satisfies some appropriate conditions
can be used as part of the programming language.
%A Zoltan Somogyi
%T A new approach to type equivalence
%R Technical report 85/15
%I Department of Computer Science, University of Melbourne
%D October 1985
%P 7
%K greedy equivalence, name equivalence, structural equivalence
%X
Greedy equivalence is a new approach to types that combines the best
features of structural and name equivalence. Its most important property
is that it supports the definition of semantically distinct types
without preventing their manipulation by shared procedures.
%A Philip W. Dart
%A Justin A. Zobel
%T Conceptual Schemas Applied to Deductive Databases
%R Technical Report 85/16
%I Department of Computer Science, University of Melbourne
%D November 1985
%P 29
%K prolog, query language, graphical interface, conceptual schema,
deductive database
%X Much of the information required in the formulation of a query
is inherent in the database structure.
First order logic is a powerful query language, but does not exploit
this structure or provide an accessible interface for naive users.
A new conceptual schema formalism, based directly on logic, provides
the necessary description of the database structure.
Its graphical representation is
the basis for a simple, concise graphical query language with
the expressive power of first order logic.
%A Kotagiri Ramamohanarao
%A John A. Shepherd
%T A Superimposed Codeword Indexing Scheme for Very Large Prolog Databases
%R Technical Report 85/17
%I Department of Computer Science, University of Melbourne
%D November 1985
%P 20
%K partial match retrieval, Prolog, hashing, descriptors, optimisation
%X This paper describes a database indexing scheme,
based on the method of superimposed codewords,
which is suitable for dealing with very large databases of Prolog clauses.
Superimposed codeword schemes provide a very efficient method of retrieving
records from large databases in only a small number of disk accesses.
This system supports the storage and retrieval of general Prolog terms,
including functors and variables,
and it is possible to store Prolog rules in the database.
%A James A. Thom
%A Kotagiri Ramamohanarao
%A Lee Naish
%T A Superjoin Algorithm for Deductive Databases
%R Technical Report 86/1
%I Department of Computer Science, University of Melbourne
%D February 1986
%P 10
%K partial match retrieval, prolog, hashing, joins, optimization, database
relational, deductive
%X
This paper describes a join algorithm suitable for deductive and
also relational databases which are accessed by computers
with large main memories.
Using multi-key hashing and appropriate buffering, joins can be performed
on very large relations more efficiently than with existing methods.
Furthermore, this algorithm fits naturally into a Prolog top-down computation
and can be made very flexible by incorporating additional Prolog features.
%A Ian G. Richards
%T Review of OSI Standards
%R Technical Report 86/2
%I Department of Computer Science, University of Melbourne
%D January 1986
%P 25
%K Networks, Open Systems Interconnection, Protocols
%X This report examines the current state of development of standards for
Open Systems Interconnection (OSI).
Since the well known seven layer OSI Reference Model was first
proposed during the late 1970's, a wide variety of standards have
appeared for protocols in conformance with the model.
The concepts ond terminology of the Reference Model are first
introduced and then many of the standards are discussed in some detail.
The report concludes that the majority of standards are either in
place or sufficiently stable to allow full OSI implementations to be
undertaken.
%A Lee Naish
%T Don't Care Nondeterminism in Logic Programming
%R Technical Report 86/?
%I Department of Computer Science, University of Melbourne
%D February 1986
%P 10
%K indeterminism, incompleteness, cut, commit, trust, parallel, proving
%X
Prolog and its variants are based on SLD resolution, which uses don't know
nondeterminism to explore the search space. Don't care nondeterminism, or
indeterminism, can be introduced by operations such as
commit in Concurrent Prolog, cut in sequential Prolog
and incomplete system predicates. This prevents the whole SLD tree
from being examined. The effect on completeness of programs is of
major importance.
This paper presents a theoretical model of \fIGuarded Clauses\fP, which
subsumes the main features of sequential and concurrent Prologs.
Next, we investigate proving properties of Guarded Clause programs
with restricted input-output modes. We present a methodology for proving
that the indeterminism does not cause finite failure, given certain
input conditions.
%A John W. Lloyd
%T Declarative Error Diagnosis
%R Technical Report 86/?
%I Department of Computer Science, University of Melbourne
%D February 1986
%P 20
%K algorithmic debugging, logic programming
%X
This paper presents an error diagnoser which finds errors in extended logic
programs and also logic programs which use advanced
control facilities.
The diagnoser is declarative'', in the sense that the programmer
need only know the intended interpretation of an incorrect program
to use the diagnoser. In particular, the programmer needs no
understanding whatever of the underlying computational behaviour
of the PROLOG system which runs the program.
It is argued that declarative error diagnosers will be indispensable
components of advanced logic programming systems, which are currently
under development.