The development of inexpensive but powerful micro-processors, together with high bandwidth communication technologies, has the potential for changing the ground rules for the design of computing systems. A network of small specialised machines may have several advantages over a large general purpose computer in trying to satisfy a variety of demands from a large number of users. Since each machine is physically separate, the choice of hardware and software for its realisation may be independent of what exists elsewhere in the network and dependent on the current state-of-the-art. Software maintenance and upgrading on the separate machines will be simpler than on the traditional central mainframe (whose operating system may contain millions of lines of code). Extension of the network facilities may be made gradually and in line with user demand. Finally, because of the true parallelism with which the network services may be performed, the response time to user demand should be quicker.
This research is investigating the economics and feasibility of compiling servers on a network such as the Cambridge Ring [1]. The idea of a compiling server can best be understood by relating it to a printer server. The latter provides a specialised piece of equipment, a line printer, that can be employed by any users on the Ring when they want to do printing. Recently, specialised pieces of equipment have been built to do compiling of particular programming languages. Assume such a machine exists for compiling a language L. Then this machine could be connected to the Ring to provide an L compiling service for all Ring users. Instead of having several L compilers running on different machines on the Ring, there is this one L server. The advantages lie in standardisation and in performance. The specialised machine for compiling L should be better at doing this task than a general purpose machine.
This technique and its implementation in our environment is described in [2]. A similar approach may be used to provide other types of service, eg text processing, and these will be investigated if time permits.
A portable package (known as the Kent Ring Handler [3]) has been supplied to the SERC to be made available to other SERC sponsored research groups. This implements, in Pascal, all the Cambridge Ring protocols in common use at the University of Kent. The package was developed on a Pascal MICROENGINE (a trademark of the Western Digital Corporation) where it forms the basis for a multi-server [4] which includes general file transfer utilities and a preliminary compiler server. A report on the performance obtained and experience gained in implementing these protocols has been published [5]. Experimental compiler servers for Pascal and Hope have been built, and several other services provided.
Work has been transferred from the MICROENGINE to the SAGE computer, in order to overcome certain problems with the former. Now this has been done, the project can begin to provide production services. An important aim of the project is to evaluate the practical usage of compiler servers, and the production servers will be used for this evaluation.
The aim of this research is to develop techniques for the distribution of software services to micro-processors around a local area network and determine the effectiveness of the resulting system. If the results are positive there is no limit to the type of services which it might then be profitable to distribute.
1. A. Hopper, The Cambridge Ring - a Local Network, lEE Micro School (Easter, 1980).
2. R. P. Bird, A Compiler Server Node in a Local Area Network, Proceedings of International Computing Symposium, B.G. Teubner, Stuttgart, 1983.
3. T. E. Schutt, Ring Handler [1.0] - User Manual University of Kent (1981).
4. T. E. Schutt and Dr P. H. Welch. Applying Micro-Computers in a Local Area Network, Conference Proceedings, Local Networks and Distributed Office Systems, Online Publications Ltd, (1981).
5. T. E. Shutt and Dr P. H. Welch. Byte Streams on a Micro-Computer, Conference Proceedings, Struktur und Betrieb von Rechensystemen. NTG/GIFachtagung, VDE-Verlag GmbH (March, 1982).
Computer document preparation and typesetting systems have grown up in two separate worlds. In the publishing world the emphasis is on quality and flexibility. but systems are typically tied to a particular typesetter. In the general computing and office world the emphasis is more on ease of creation and updating, but output is restricted to single-font lineprinters or daisy-wheel printers. Hardware developments are such that specialised typesetting systems are becoming almost indistinguishable from general purpose computer systems equipped with a high quality printing device. Thus it should now be possible to bring the best of the two worlds together to create high quality document preparation systems which are not tied to a particular typesetter.
The initial aim of the project is to concentrate all the necessary specialised hardware and software into a typesetting server for the Cambridge Ring - thus providing a high quality service to a large community of users at a moderate cost. The long term aims are to investigate the best way to integrate such a server into a distributed system, and to develop more interactive and user-friendly typesetting systems.
Only systems producing device-independent output will be implemented or developed. This will ensure that documents can be created or previewed on a graphics screen before printing and that a higher resolution printer or typesetter can be incorporated into the server.
The initial version of the server - based on an ICL PERQ and a Canon LBP-10 laser printer (240 dots/inch) - has been set up. The Canon LBP-10 has been interfaced to the Cambridge Ring via an Orbis 68000 which acts as an intelligent controller in DTF via the ring.
A preliminary version of Professor Knuth's TEX typesetting system has been implemented on the PERQ; TEX output can be previewed on the PERQ screen and printed on the Canon LBP-10. In addition, the new typesetter-independent version of the UNIX troff has been implemented on a VAX 11/780. An experimental troff-to-Canon service with 30 users is in operation.
The server is currently being integrated properly into the ring. This includes providing better error reporting and recovery facilities, and making use of a file server on the ring to hold font libraries.
At the moment. the preliminary version of TEX runs under the POS system on the PERQ. As soon as PERQ UNIX with Pascal becomes available TEX will be re-implemented and integrated properly into the server. Work is also under way to allow output from both TEX and troff to be printed on a Monotype Lasercomp.
Improved techniques for document preparation are clearly needed for office systems, for in-house printing facilities, and for interfacing office systems with publishers systems.
One practical problem in the development of artificial intelligence systems over the past twenty years has been the immense amount of processing power necessary to implement relatively simple systems. Since computer hardware, including processors, is not relatively cheap, it seems worthwhile considering the use of coupled microprocessors to meet the need for intensive computation. This project has been exploring such an approach, both theoretically and practically. Since the particular interest was the possibility of coupling large numbers of processors (eg several hundred), it was necessary to impose the further requirement that the processors be loosely-coupled. so that arbitrarily many units could be connected without introduction problems of hardware memory access. The intention was to develop general principles as far as possible. rather than simply constructing a single ad hoc system.
The first stage of the project (October 1977 to August 1980) involved the design and implementation (hardware and software) of a multiprocessor, multiprocessing system based on Motorola 6800s. The system included three loosely-coupled processors, each containing an identical list-oriented multi-processing interpreter, with a fourth processor to handle data communications. Inter-process communication was effected by passing arguments to procedures in remote environments, and there were facilities for parallel evaluation of arguments and for parallel execution of statements [1]. This implementation demonstrated that all these ideas could be combined in a working system, but the result was not particularly suitable for large knowledge representation applications, owing to memory limitations.
The second stage of the project began in July 1979. It has now been decided that any further implementations were to be carried out on DEC LSI-11s. and so a revised implementation was required.
No significant problems of a practical nature were encountered in either implementation, leading to the conclusion that the main issue involved constructing distributed knowledge representation systems lay in the efficiency of the resulting programs dynamic behaviour. It was not a problem to implement a system on multiple processors, but it might be difficult to do so efficiently; moreover, it might be very difficult to prove (even informally) that a distributed implementation was efficient.
This led to a detailed survey of recent artificial intelligence work, in order to find either a suitably substantial test program for the knowledge representation language, or some theoretical basis for proving mathematical results (about the efficiency of possible implementations). Unfortunately, there is a severe lack, within artificial intelligence, of medium-sized, portable, documented, knowledge-representation programs which actually work. The conclusion of this part of the investigation was that most knowledge representation systems are in fact large., arbitrary, fragile programs which embody few theoretical principles.
Another area examined was that of database models, since it seemed likely that there might be some connections between distributed database work and distributed knowledge representation. In fact, database models seemed to be better defined than artificial intelligence notations, and they differ only slightly in the range of facilities they attempt to provide [5]. Since most artificial intelligence formalisms are not specified in database terms, it is difficult to translate database techniques directly for use in artificial intelligence programming, but in principle this approach should be possible. Many of the distribution techniques (eg for maintaining consistency) could then be applied directly to distributed knowledge representation programs.
The issues involved in knowledge representation are so ill-understood at present that it is unrealistic to consider distributing existing systems, since they are generally ad hoc programs. Particular applications in which there is a natural multi-dimensional structure (eg a distributed formation net, as in the large project at Carnegie-Mellon University) may lend themselves to distributed implementations, but in the area examined in this project (general semantic network representations of knowledge) the problem reduces to the less specific issue of how to implement a distributed list-processing system. Even then, the question of a realistic bench mark for such a system is difficult to resolve, in the absence of suitable test programs.
1. G. G. Coghill. Pleiades - A Multi-microprocessor System for Knowledge Manipulation, PhD Thesis. University of Kent. 1980.
2. F. K. Hanna and G. D. Ritchie. AM: A Case Study in AI Methodology, Internal report. University of Kent.
3. F. K. Hanna and G. D. Ritchie. Time-Efficient Implementation of Data Structures using Multiple Processors, Internal report, University of Kent.
4. G. D. Ritchie and F. K. Hanna. Semantic Networks - A General Definition and a Survey, Internal report. University of Kent.
5. G. D. Ritchie and F. K. Hanna, Structural Models in Databases and in Artificial Intelligence, Internal report, University of Kent.
Denotational languages are very high level programming languages without any explicit control structure - the two main groups of languages of this class are the logic languages (such as PROLOG) and functional languages. The investigator has been the designer of the functional language, SASL [1], and the purpose of the project has been to investigate the extent to which this language could be adapted to be the main programming language for a parallel computer architecture, such as a dataflow machine. The work was begun in liaison with Ronan Sleep of East Anglia, who adopted SASL for his work on parallel architectures [2]. The funds awarded were primarily travel money, to enable the investigator to visit other sites both in the UK and abroad (primarily the U.S.) to exchange ideas and to pursue the further development of the SASL language.
A great deal of progress has been made. First there have been some improvements in the underlying implementation technique (combinator reduction) that should ease its adaptation to parallel hardware. Secondly the investigator has developed a successor language to SASL, called KRC [3], which incorporates ideas based on set theory which greatly increase its programming power. During the past year, several papers were published by the investigator describing various aspects of the research [4][5][6]. A paper has also been prepared giving a fully formal proof of the correctness of the SASL compiler, and this is awaiting publication.
A major follow-up project has now begun, involving the construction at Kent of a large micro programmed combinator reduction machine and the development on it of a complete operating system written in a functional language.
1. D. A. Turner, SASL Language Manual, St. Andrews University, December 1976.
2. M. R. Sleep, Applicative Languages, Dataflow and Pure Combinatory Code, IEEE 20th Spring Computer Conference, San Francisco, 1980.
3. D. A. Turner, KRC Manual, University of Kent, in preparation.
4. D. A. Turner, Prospects for Non-Procedural and Dataflow Languages, Infotech State of the Art Report, London, June 1981.
5. eds J. Darlington, P. Henderson and D. A. Turner, Recursion Equations as a Programming Language, in Functional Programming and its Applications. Cambridge University Press, February 1982.
6. ed Neel Functional Programs and Proofs of Program Correctness, in Tools and Notions for Programming Construction, Cambridge University Press, August 1982.
7. G. M. Holms, Edit - As an Application of Functional Programming, University of Kent M.Sc. Thesis, October 1982.
8. S. Meira, Sorting Algorithms Implemented in a Functional Programming System, University of Kent Technical Report, June 1982.
Applicative (or functional) languages are very high level languages without any explicit control structure. They are related to logic languages, such as PROLOG, but differ in being based on functions rather than relations and in being higher order (so functions may be passed as parameters or returned as results). Their potential future importance to the software industry lies in the fact that applicative programs can be much shorter and easier to reason about than conventional ones and also in their capacity for parallel execution which should make them a natural fit for novel highly concurrent architectures. The investigator has played a leading role in the development of applicative languages and their implementations [1][2][3] and has received SERC support under the DCS programme since 1960.
The purpose of the current project is to demonstrate the practical viability of applicative languages for systems programming by producing a complete multi-user operating system. with a UNIX-style filing system and a variety of production programs, all written entirely in an applicative language. This has never been done before and will involve overcoming a number of theoretical and practical problems. The work is being carried out on an ORION supermini computer, supplied by High Level Hardware of Oxford, which is being microprogrammed for the project as a combinator reduction machine [2] (an abstract machine designed to support applicative languages).
The project team consists of the investigator, two research associates, and several postgraduate students. So far an editor and a compiler have been written, and work carried out on the complexity of functional programs [4][5].
There is a developing interest in industry in practical applications of functional programming and the investigator is involved in regular discussions and exchange of information with a number of industrial firms including Burroughs Corporation, ICL, and L M Ericsson (the telecommunications company).
1. D. A. Turner, SASL Language Manual, St Andrews University. December 1976.
2. D. A. Turner, A New Implementation Technique for Applicative Languages, Software Practice and Experience. January 1979.
3. (eds) J. Darlington. P. Henderson and D. A. Turner, Functional Programming and its Applications, Cambridge University Press. February 1962.
4. G. M. Holmes. Edit - An Application of Functional Programming, University of Kent M.Sc Thesis. October 1962.
5. S. Meira. The Complexity of Sorting Algorithms Implemented in a Functional Programming System, University of Kent Technical Report. June 1962.
