Browsing by Author "Cleary, John G."
Now showing 1 - 20 of 46
Results Per Page
Sort Options
- ItemOpen AccessA Graphical debugger for Prolog(1985) Dewar, Alan D. (Alan David), 1960-; Cleary, John G.
- ItemOpen AccessACQUISITION OF UNCERTAIN RULES IN A PROBABILISTIC LOGIC(1986-10-01) Cleary, John G.The problem of acquiring uncertain rules from examples is considered. The uncertain rules are expressed using a simple probabilistic logic which obeys all the axioms of propositional logic. By using three truth values (true, false, undefined) a consistent expression of contradictory evidence is obtained. As well the logic is able to express the correlations between rules and to deal both with uncertain rules and with uncertain evidence. It is shown that there is a subclass of such rules where the probabilities of correlations between the rules can be directly computed from examples.
- ItemMetadata onlyADAPTIVE TEXT COMPRESSION TO ENHANCE A MODEM(1983-10-01) Darragh, John J.; Witten, Ian H.; Cleary, John G.The design of a coding system is described and evaluated in the context of a computer-to-terminal modem connection. Unlike other compression problems, it is hard to characterise the kinds of information that may require processing. For this reason the system uses an adaptive Markov model, in conjuction with arithmetic coding. The compression performance improves with available memory. Two techniques for storing the Markov model are described. Experimental results are reported for a variety of sample texts. It is shown that effective line speeds can be at least doubled, and in some cases tripled, using less than 64 Kbytes of memory.
- ItemOpen AccessAn Implementation of ray tracing using multiprocessing and spatial subdivision(1987) Pearce, Andrew P.; Cleary, John G.
- ItemOpen AccessAn Optimistic AND-parallel Prolog implementation(1991) Olthof, Ian William; Cleary, John G.
- ItemOpen AccessANALYSIS OF AN ALGORITHM FOR FAST RAY TRACING USING UNIFORM SPACE SUBDIVISION(1987-10-01) Cleary, John G.; Wyvill, GeoffRay tracing is becoming popular as the best method of rendering high quality images from three dimensional models. Unfortunately, the computational cost is high. Recently, a number of authors have reported on ways to speed up this process by means of space subdivision which is used to minimize the number of intersection calculations. We describe such an algorithm together with an analysis of the factors which affect its performance. The critical operation of skipping an empty space subdivision can be done very quickly, using only integer addition and comparison. A theoretical analysis of the algorithm is developed. It shows how the space and time requirements vary with the number of objects in the scene.
- ItemMetadata onlyARITHMETIC, ENUMERATIVE AND ADAPTIVE CODING(1982-07-01) Cleary, John G.; Witten, Ian H.Using the close relationship between arithmetic and enumerative codes, expressions are developed for the performance of various non-adaptive codes. It is then shown that there exists adaptive codes whose performance can be guaranteed to be better than or close to these non-adaptive codes. On some actual examples the adaptive codes are significantly better than the non-adaptive ones.
- ItemOpen AccessBONSAI: A COMPACT REPRESENTATION OF TREES(1991-10-01) Witten, Ian H.; Cleary, John G.; Darragh, John J.This paper shows how trees can be stored in a very compact form, called "Bonsai", using hash tables. A method is described that is suitable for large trees that grow monotonically within a predefined maximum size limit. Using it, pointers in any tree can be represented within $6 + \s-3 left ceiling \s+3 log sub 2 n \s-3 right ceiling \s+3 $ bits per node where \fIn\fR is the maximum number of children a node can have. We first describe a general way of storing trees in hash tables, and then introduce the idea of compact hashing which underlies the Bonsai structure. These two techniques are combined to give a compact representation of trees, and a practical methodology is set out to permit the design of these structures. The new representation is compared with two conventional tree implementations in terms of the storage required per node. Examples of programs that must store large trees within a strict maximum size include those that operate on trie structures derived from natural language text. We describe how the Bonsai technique has been applied to the trees that arise in text compression and adaptive prediction, and include a discussion of the design parameters that work well in practice.
- ItemOpen AccessCOLLIDING PUCKS SOLVED USING A TEMPORAL LOGIC(1989-08-01) Cleary, John G.A Horn Clause logic programming language, called Starlog, which allows execution of programs involving time is described. A sound and complete bottom up execution procedure for the language is described. An extended example of Programming in Starlog is given in the form of a solution to the colliding pucks problem. A discussion of the features necessary for a distributed implementation of Starlog are given.
- ItemMetadata only
- ItemOpen AccessCONNECTIONIST ARCHITECTURES(1986-03-01) Cleary, John G.Many schemes for computing have been proposed and variously described as distributed, connectionist, neuron-like and massively parallel. These are difficult to implement in current technology because at the circuit level they imply very complex wiring or switching and at the system level they cannot be efficiently simulated on a traditional von Neumann computer. A VLSI based architecture which avoids some of these problems is proposed. The basic operation implemented is the weighted summing of signals from a large number (~1000) inputs using the $sum$-chip. Signals are heavily multiplexed, and the weighting coefficients are stored in shift registers on the same chip that does the summing. The result is a VLSI chip which has two ingoing signal pins and one outgoing. As an example a system using the $sum$-chip is described which solves the n-Queens logical puzzle. Its application in chess playing is also considered briefly.
- ItemMetadata onlyDATA COMPRESSION USING ADAPTIVE CODING AND PARTIAL STRING MATCHING(1982-09-01) Cleary, John G.; Witten, Ian H.The recently-developed technique of arithmetic coding, in conjunction with a Markov model of the source, is a powerful method of data compression in situations where a linear treatment is inappropriate. Adaptive coding allows the model to be constructed dynamically by both encoder and decoder during the course of the transmission, and has been shown to incur a smaller coding overhead than explicit transmission of the model's statistics. But there is a basic conflict between the desire to use high-order Markov models and the need to have them formed quickly as the initial part of the message is sent. This paper describes how the conflict can be resolved with partial string matching, and reports experimental results which show that English text can be coded in as little as 2.2 bits/character with no prior knowledge of the source.
- ItemOpen AccessTHE DESIGN OF AN OPTIMISTIC AND PARALLEL PROLOG(1992-05-01) Cleary, John G.; Olthof, Ian(This paper has been submitted to the Journal of Logic Programming) A distributed AND parallel Prolog implementation is described. The system can correctly handle all pure Prolog program. In particular, it deals with the problem of distributed backtracking. Conflicts in variable bindings are resolved by assigning a time value to every unification. Bindings with smaller time values are given precedence over those with larger time values. The algorithm is based on the optimistic Time Warp system, with Prolog-specific specializations. The result is a system which can fully exploit both dependent and independent AND parallelism.
- ItemMetadata onlyA DISTRIBUTED GRAPHICS SYSTEM IMPLEMENTED IN PROLOG(1984-11-01) Cleary, John G.The construction of complex two dimensional graphics is a computationally intensive process. This is aggravated in languages such as Prolog where it is not easy to perform the arithmetic for geometric transformations at a satisfactorily high speed. One approach to this problem is to distribute the geometric computations to a special purpose graphics processor which is tightly coupled with a display screen. Unfortunately, for complex pictures without a lot of regularity in their structure it can take more time to communicate the picture representation to the graphics processor than to generate plotting instructions directly. A high level language for two dimensional graphics (GROWL) is described. The "standard" implementation of this generates directly executable Prolog code from the GROWL source. A distributed version has been completed which compiles the original source to two programs. One is intended to run on a remote processor and includes little more than the arithmetic for geometric transformations. The other runs on the host as a Prolog program and is completely free of the overhead necessary for geometric transformations but includes all the logic necessary to direct the picture construction. A novel message passing scheme is used for communication between two components. The result is a system which gives very compact representations of pictures on the graphics processor, a very low communications overhead and a high degree of parallelism between the host and graphics processors.
- ItemOpen AccessA DISTRIBUTED IMPLEMENTATION OF AND-PARALLEL CONCURRENT PROLOG(1985-03-01) Cleary, John G.A distributed binding environment for concurrent logic programs is described. It supports the sharing of logical variables between and-parallel processes using eager structure copying. It is assumed that the system runs within a fixed number of "address spaces" with serial communication channels between them. Advantages of the system are that only local garbage collection within the individual address spaces is necessary, only a very simple blocking send message passing system is used, and message passing efficiency improves as the system becomes more heavily loaded. Message count statistics are given for a distributed program using Shapiro's Concurrent Prolog.
- ItemMetadata onlyA FAST COMPACT REPRESENTATION OF TREES USING HASH TABLES(1984-09-01) Cleary, John G.; Darragh, John J.A new representation of trees using hash tables is described. Like the usual pointer representation leaves can be reached or inserted in a time proportional to the depth of the tree. Each node uses only the space for its data plus an overhead of $10~+~left ceiling {log sub 2 n} right ceiling$ bits, where $n$ is the number of children allowed on each node. A parent node is accessible from its child, allowing an algorithm to be exhibited for traversing a tree using a small constant amount of storage and without modifying the tree itself. Expressions are given for the space and time required for traversal of trees, as well as, space and timing data from an actual implementation.
- ItemMetadata onlyFORETELLING THE FUTURE BY ADAPTIVE MODELING(1984-02-01) Witten, Ian H.; Cleary, John G.Foretelling the future is a pastime that all of us enjoy every day, but one which is not normally viewed as a scientific activity. Yet it is often quite possible to predict the future-albeit in a limited way-and to put the prediction to good use. By supplying an expected, "normal", course of events, a good prediction focuses attention on how unfolding events differ from the norm. In many cases this is more interesting than the events themselves. For example, suppose one computer is sending a stream of numbers to another. If it is possible to predict exactly what the next number is going to be, then there is no point in sending it at all! But suppose the guesses are not so reliable. Then it may be advantageous to send the difference between the guess and the actual value of the next number. The receiver-assuming it can make identical guesses-will be able to reconstruct the correct number from the difference. If the guesses are good, this scheme will reduce the amount of information that needs to be sent. In fact, the reduction achieved is a quantitative measure of success at guessing.
- ItemMetadata onlyGETTING TO GRIPS WITH A ROBOT ARM: THE RHINO XR-1(1982-10-01) Drummond, Mark; Witten, Ian H.; Cleary, John G.Most computer hobbyists know that their computers are usually harmless enough. But things are changing now with the appearance on the market of a growing number of small robot arm manipulators, targetted at home hobbyists and basement workshops. One of the first is the Rhino XR-1 from Sandhu Machine Design. We have used one for several months and would like to share with readers our experiences and provide some practical handy tips. The design philosophy behind the XR-1 has been ably described by Sandhu (1982), its inventor. He covers some trade-offs implicit in the design and describes various problems which had to be overcome during its creation. The XR-1 manual (which can be obtained separately from the arm itself) gives an excellent introduction to the operation and programming of the arm. To complement this documentation we provide here an independent review of how we have found the XR-1 to perform in practice, and discuss some of the unexpected problems that were encountered and how we solved them. It is worth saying at the outset, however, that we have been more than satisfied with the device and regard Sandhu's engineering as a fine piece of work.
- ItemOpen AccessGRAPHICAL DISPLAY OF COMPLEX INFORMATION WITHIN A PROLOG DEBUGGER(1985-12-01) Dewar, Alan D.; Cleary, John G.An interactive Prolog debugger, DEWLAP, is described. Output from the debugger is in the form of graphical displays of both the derivation tree and the parameters to procedure calls. The major advantage of such displays is that they allow important information to be displayed prominently and unimportant information to be shrunk so that it is accessible but not distracting. Other advantages include the following: the control flow in Prolog is clearly shown; the control context of a particular call is readily determined; it is easy to find out whether two uninstantiated variables are bound together; and very fine control is possible over debugging and display options. A high-level graphics language is provided to allow the user to tailor the graphical display of data structures to particular applications. A number of issues raised by the need to update such displays efficiently and to control their perceived complexity are addressed. The DEWLAP system is implemented in Prolog on relatively standard hardware with a central processor running Unix and remote workstations with bitmapped displays and mice.
- ItemMetadata onlyIMPLEMENTATION OF CONCURRENT PROLOG USING MESSAGE PASSING(1984-04-01) Cleary, John G.The design of a distributed Concurrent Prolog system is described. It is based on message passing between large processes which provide a coarse grained parallelism. The intended use of the system is in a distributed prototyping environment which supports many programming languages and allows distributed software to be developed on one system and later transported to another. The underlying message passing system used is simple and efficient and need make no provisions for buffering messages between processes. An algorithm is described for serialising variable bindings so they can be transmitted between processes. It permits free variables to be bound together and can correctly handle circular data structures. Each variable shared between processes is "located" on a single process which distributes its values whenever it is updated. This leads to an "eager" distribution system which sends updates to variables whenever they occur not when they are needed for further computation. Sometimes, as a result of garbage collection or as a result of unification of different shared variables it is necessary to relocate a variable. The mechanisms to do this are described. Some estimates of the efficiency of the system are obtained by counting the messages needed for a simple but representative program. The effects of various optimisations on the message passing protocol are also assessed.
- «
- 1 (current)
- 2
- 3
- »