COMPUTER SCIENCE RESEARCH SEMINARS AUTUMN TERM 1993 Programme Coordinator: John D Hollows (email J.D.Hollows, phone 4777) Time/Venue: 1400hr, each Tuesday during term time, in G33. (Occasionally a speaker is available who cannot manage the regular seminar date/time, in which case alternative arrangements will be made) Any proposals for visiting speakers should be discussed with the Programme Coordinator to ensure that there is no time-table clash. Whoever invites a speaker is expected to "host" the speaker on the day, as well as obtaining a title and abstract in time for prior circulation. The host can also take the speaker and one or two other people to lunch before the seminar and charge the cost to the School seminar budget. Travel expenses for speakers will also be covered. Do not invite anyone to travel from overseas without first discussing budgetary arrangements with the Coordinator, who will consult as necessary with the Head of School. PROGRAMME FOR THE AUTUMN TERM, 1993 12th October : "A Logic for Qualitative Spatial Representation" Tony Cohn (Leeds) (agc@scs.leeds.ac.uk) Abstract: In this talk I will describe an ontology for space based on the notion of spatial regions; I will present a taxonomy of spatial relations which may hold between such regions and will consider inference mechanisms for the calculus including a simulation procedure which evolves state descriptions over time. The work is related to that of Allen's temporal calculus. 19th October : "Text Recognition for Historical Documents" Susan Laflin Abstract: Recognition of handwritten text by computers has long been an ideal. For the on-line case, where the shape traced out by the pen is recorded as it is written, much success has been achieved. It is now possible to train a computer system to recognise its owner's handwriting (most of the time) and many systems have recently been advertised which make use of this and allow handwritten input using the pad and stylus provided. Off-line recognition, where the manuscript has already been written before it comes anywhere near the computer is a much more difficult problem. In this case, the completed document has to be scanned into the computer and the programs have only the image of the written page to analyse. It makes no difference if the manuscript is centuries old or has only been finished seconds before. This talk gives a survey of recent work in this area and describes one approach currently being researched. 26th October : "Implementing an incremental Haskell compiler in the Poplog Virtual Machine.", Prof Robin Popplestone, Univ of Massachusetts at Amherst (Currently visiting Glasgow University) Abstract: Haskell is a non-strict purely functional language. Computer Scientists are interested in functional languages because the simple and elegant semantics of such languages support the proof of program properties in a natural way and thus offer a route to engineering software which meets formal specifications. The formal basis of these languages is Church's Lambda Calculus, and its typed extensions. Today Hindley-Milner typing is the usual choice. Here "non-strict" means in effect that the arguments of functions are only evaluated when they are known to be needed, so that by default function arguments are called -by name-. Non-strictness, which is essential if a language is to have semantics corresponding to beta-reduction in the lambda calculus, is hard to implement efficiently, because of a profusion of suspended computations, called "thunks" since the days of Algol-60 implementations. The Glasgow Haskell Compiler (GHC) represents a significant milestone in implementing functional languages because of the careful attention that has been given to various aspects of efficiency. However user-friendliness is constrained by its dependence upon those antediluvian monsters, linkers and loaders, conceived in the dark days of -batch- before the liberating flood of computation piped to every office-chair. Thus Poplog offers a chance of putting Haskell in an up-to-date environment supporting incremental compilation. Conversely, the GHC offers pointers towards being able to generate better code in Poplog.The GHC uses an intermediate form, the STG language, from which it generates C code. STG stands for "Spineless Tagless G-machine". The STG language is in effect a lambda-calculus augmented with case-statements and flattened by systematic let-binding of sub-expressions. It is "spineless" because it avoids the overhead of operating on an explicit representation of a lambda-calculus term whose "spine" is stacked up and reduced. It is called tagless because -only- closures are put in the heap; primitive values like floats and ints are separately stacked from non-primitives, so that no tagging is required. Heap objects in the GHC are managed like the original POP-2 items; each has a data-area and a pointer to a key-cell. The key-cell contains methods for garbage collection. However it also has a slot corresponding to the Poplog "class_apply" slot, which defines its behaviour when evaluated. This behaviour is -always- to dump the "contents" of the object into standard registers. In effect it is a -destructor- (used of course in its original sense, and not that of C++). My approach to porting the Glasgow Haskell Compiler to the Poplog environment is to implement an interface at the STG level to Poplog Virtual Machine code. In other words, replace the sequence of transformations: Haskell -> ..... -> STG Code -> ... C ... Machine code by: Haskell -> ..... -> STG Code -> POPLOG VM Code -> Machine code The capabilities of the Poplog VM match the requirements of STG quite accurately, so the translation is not difficult. Practically, to compile a Haskell module, a GHC process is spawned from Poplog with compile-flags which specify that STG code is to be output, the output being redirected into a file. The STG form is parsed by a small parser written in -parse_gen-, thus reconstituting a POP-11 equivalent of the STG internal form. PVM code is generated from the STG. Ultimately it should be possible to pass the GHC itself through this process, giving a native Poplog implementation. Top-level functions in a module are bound to PVM variables created with -sysVARS-. The names of these variables are drawn from the flat name-space intended for the linker. This means that a Haskell -program- can usually be modified and run simply by recompiling a -module- and calling the -main- function. Interaction can be provided by providing POP-11 bindings for those Haskell functions whose arguments can be derived from standard POP-11 datatypes, such as dynamic (i.e. tail-lazy) lists. I will discuss the current state of this port and how the efficiency of PVM code should compare with that generated from C. 2nd November: P. Hancox (MSc's) 9th November: "Haskell and Type Classes", Kevin Hammond (Glasgow) Abstract: A funny thing happened on the way to Haskell. The goal of the Haskell committee was to design a standard non-strict pure functional language, applying existing, well-understood methods. To the committee's surprise, it emerged that there was no standard way to provide overloaded operations such as equality (==), arithmetic (+), and conversion to a string (show). This talk describes the Haskell language and its implementation, with particular emphasis on how ad-hoc polymorphism was used to provide uniform overloading via *type classes*, and how an efficient implementation can be produced. 16th November: "What is Wrong with Functional Programming Languages? - A Personal View", Tom Axford Abstract: Functional programming languages have been promoted by their supporters as superior to conventional imperative languages in a number of fundamental ways. Yet modern functional languages such as Haskell are not being adopted by large numbers of commercial programmers - they remain the preserve of a small band of enthusiasts. What has gone wrong and what does the future hold for functional languages? Will they just fade into oblivion, or are they on the verge of breaking through into the big time? 23rd November: "The development of swath bathymetry" (or what I did on my Summer Holidays) Russell Beale Abstract: Measuring the depths of the deepest oceans is a difficult thing to do. Earlier this year I was involved in an expedition to the South-East Pacific to develop a surveying system that could achieve this task. This talk presents the results of the expedition. It will give an overview of the workings of the GLORIA system, and describe the swath bathymetric system that was developed. This system is the first of its kind ever developed. (Swath bathymetry refers to the process of producing a depth map in the form of a wide ribbon rather than a single line - much more useful when you have to survey a wide area). It will also present the general results from the expedition, such as the probable method of formation of Easter Island, as well as giving insights into what it is like to live on board a ship for 3 months, an impression of the South East Pacific, and the difficulties of developing software in a hurry. The talk will not require any prior knowledge, and is unlikely to be overly technical, concentrating instead on the principles behind the systems and on the fascinating results obtained. It ought to be of interest to computer scientists, physcists, geophyscists, oceanographers, engineers, ethnographers, explorers and other such parties. 30th November: "THE AUTOMATIC PARALLELISATION OF LISP PROGRAMS" Edmund Furse, University Of Glamorgan. Abstract AUTO PARALLEL LISP is a system for automatically parallelising and running Common LISP programs over a network of computers. Firstly, the functions are analysed to determine which functions are totally functional in design. Functions which have side effects are run locally, whilst functional designs can be run remotely. Secondly, functions are identified which can be parallelised because of functions with two or more arguments which are totally functional calls, or CDR recursions which can be transformed into divide and conquer parallel algorithms. Thirdly, using example calls of the top level function provided by the user, timing analysis is performed of the functions which can be parallelised to determine which functions should be parallelised. Fourthly, the functions to be parallelised are transformed into a parallel form using the PARALLEL macro to run on the PARALLEL subsystem. The PARALLEL subsystem uses a main node, a farmer and a number of monitor nodes. When a PARALLEL call is encountered the arguments are executed in parallel over the network by requesting a free node from the farmer, or else performing the task locally. 7th December: Peter Jarratt CANCELLED 14th December: Jorge Bocca