VIM: A Virtual Multicomputer for Symbolic Applications
Contract: CHRX-CT93-0401

Annual Progress Report for 1996 (Year 3 of 4)

The three topics which bind this network together are parallel systems, advanced compilation techniques and artificial intelligence (AI) with a common substrate in the programming language Lisp. The research aim of this project is to demonstrate the advantages accruing from the combination of these three technologies to build a virtual multicomputer for large scale symbolic applications. A virtual multicomputer is an ephemeral, persistent machine of available heterogeneous computing resources (workstation, shared-memory multiprocessor, distributed memory multiprocessor, array processor). The system supports a virtual processor abstraction to distribute data and tasks across the multicomputer, the actual physical composition of which may change dynamically. Our practical objective is to assist the prototyping of dynamic distributed symbolic applications in artificial intelligence and computer algebra using whatever resources are available (probably networked workstations), but so that the developed program can also be run on more exotic hardware without reprogramming.

Examining the six areas of the work plan (work has not started on items which are not mentioned and items refer to the numbered topics on the original work plan):

Reflective architectures:
  1. Analysis of the reflective aspects of Omega (Pisa), KRS (VUB), Babylon (GMD-FIT.KI) to find out the differences and commonalities and subsequently to synthesize a requirements definition for a new reflective architecture (Warwick).

    Dropped (see 1995 report).

  2. Development of a logic-based semantics to describe reflective systems (IIIA, Pisa, Warwick).

    This is complete with two publications from IIIA, but since these are not joint with other partners, they do not appear in the list below.

  3. Development of the EuLisp object system and its meta-object protocol through experience of a wider variety of applications (GMD-FIT.KI, ILOG, Warwick).

    This is complete with the release of the youtoo system, bindings to a number of packages and some significant applications (Noostoo, a re-implementation of the NOOS knowledge representation language in EuLisp and an object-oriented reconstruction of the OPS5 expert system shell). This has also served to demonstrate the practicability of importing Common Lisp code into EuLisp, as well as developing a sufficient compatibility module for the implementation of NOOS.

  4. Applications of reflection (and reification) to task migration, constraint satisfaction, cross-language calling and distributed multi-language client-server programs (Southampton, Bath, INRIA, ILOG).

    This continues with the development of cross-language bindings between EuLisp and C and the integration of EuLisp with operating system thread libraries, permitting multi-lingual threading within the same process. Meanwhile the DMeroon system now supports the migration of objects between machines based on a carefully defined serialization/deserialization process.

  5. Applications of reflection on knowledge level models (in components of expertise) for integrated life-cycle support in KBS development, e.g. for knowledge level modeling, validation and verification. (VUB, UPC, URV, Warwick, IIIA).

    This continues, a notable demonstrator being NOOSWeb (IIIA), a WWW interface to the NOOS knowledge representation system.

Knowledge representation and knowledge bases:
  1. Comparison of Omega (Pisa), Milord II (IIIA) and Elektra (Warwick) systems to discover in which ways they differ and in which ways they are the same, then analysis of the approaches to determine advantages and disadvantages (Salerno).

    Completed (see 1994 report).

  2. Investigation of the use of Milord II (IIIA) in implementing the ``components of expertise approach'' developed at VUB (UPC, URV).

    Completed (see 1995 report).

  3. Definition of requirements for a language well-suited to the components of expertise approach (IIIA, VUB).

    Completed (see 1995 report).

  4. Development and application of an object-oriented knowledge representation formalism (GMD-FIT.KI, VUB, Pisa, IIIA, UPC, URV).

    The Fish market model in Descriptive Dynamic Logic (DDL) has been completed and has been reported in the Proceedings of ECAI'96 and more general paper on DDL and its application to reflective architectures is to appear in the Future Generation Computer Systems Journal. There is on-going work on modelling using Common Knowledge and this may also be applied to the Fish market scenario, while work at URV has focussed on belief modelling in multi-agent systems.

  5. Application of new forms of knowledge representation in intelligent tutoring systems (Salerno, GMD-FIT.KI, IIIA, UPC).

    This theme has been refocussed on to the development of multi-agent architecture for navigation systems in museums. This is seen as a natural evolution of existing intelligent tutorial systems towards new architectures, in which the technology is applied to teaching about the objects contained in the museum.

  6. Development of a methodology for the automatic generation and validation of knowledge bases from observations (URV, UPC, Pisa, VUB, Warwick).

    There has been continued progress on the methodology for automatic generation and validation of KBS, the results of which are reported in several papers from URV. In particular, a semantics for linguistic labels has been developed, and applied to knowledge acquisition. Work is in progress on merging knowledge from several experts. and on the combination of several sources of fuzzy information (in collaboration with IIIA).

  7. A workshop on knowledge representation (in conjunction with that on parallelism in AI).

    A workshop including this theme is taking place in May 1997.

Static analysis:
  1. Examination of the effectiveness of and subsequent refinement of automatic mapping and dynamic load balancing techniques by application to parallelized versions of existing AI programs (GMD-FIRST, CNR, IIIA, Pisa, UPC).

    This has resulted in two technical reports [2], [3] below (joint between URV and GMD-FIRST) and is now completed.

  2. Examination of the effectiveness of and subsequent refinement of automatic parallelization techniques applied to existing AI programs (GMD-FIRST, IIIA, Pisa, UPC).

    Work is in progress at GMD-FIRST and a paper will appear in the Proceedings of PPoPP'97.

  3. Development of a type inference tool for EuLisp to assist in static method selection and total compilation (Bath, GMD-FIT.KI, Kiel, Southampton).

    Exploration of this problem, based on a re-implementation and extension of the techniques developed in the APPLY project, concluded that the approach would only bring minor benefits unless the dynamic nature of the language was seriously compromised. Consequently the work has refocussed on dynamic optimisation of method invocation which is proving very fruitful.

  4. Development of an abstract interpretation tool for EuLisp as a basis for advanced source-level optimizations (Southampton, Bath, Kiel).

    Although the immediate goal is not abstract interpretation, work is in progress on rule-based specification of source-level improvement of programs.

  5. Development of a restructuring tool for sequential programs to generate hierarchical task graphs for concurrent execution (CNR, GMD-FIRST).

    Dropped due to partners' changed interests and objectives.

  6. Comparison of the use of advanced module compilation techniques (ILOG) with static verification techniques (Kiel) with the aim of deriving benefit from their combination.

    A feasible technique has been developed at Kiel for rigorous compiler verification with respect to a compiling specification and an implementation as a binary program executable, in the setting of a carefully defined subset of Lisp. The key to its success is modularization and a combination of mathematical proof, formal methods and mechanical support.

  7. A workshop on advanced compilation techniques (in conjunction with that on parallel systems).

    A workshop including this theme is taking place in May 1997.

Semantics and verification:
  1. Investigation of the implications of parallelism for the techniques employed in total compilation (Kiel, INRIA, Bath, Southampton).

    Dropped due to partners' changed interests and objectives.

  2. Development of a formal semantics for a concurrent object-oriented Lisp (Bath, INRIA, Kiel, Southampton).

    A formal semantics of a distributed notion of the future construct (for spawning concurrent processes) has been developed at Southampton and was presented at ICFP'96.

  3. Development of an animator for pi-calculus specification (Southampton, Bath, Pisa).

    Completed (see 1995 report).

  4. Application of techniques developed in the ProCoS project to concurrent object oriented programs and the development of a verifiable target abstract machine for the total compilation of concurrent object-oriented programs (Kiel, Southampton, Bath, INRIA).

    Work in progress on the development of executable rule-based specifications of operational semantics which can be separated automatically into a compiler and an executor, hence deriving a virtual machine for the source language.

  5. Application of verified implementation to at least one fair-sized AI program (Kiel, Southampton, Bath, INRIA).

    Work is in progress in particular on the rigorous implementation verification of transformational Lisp programs (Kiel). Techniques for implementation verification have been applied to Lisp compilers.

Parallel models and systems:
  1. Comparison of parallel Lisp systems developed at Bath, GMD-FIRST, INRIA, Pisa, Southampton and CNR (i) to identify a set of primitive operations for the implementation of concurrent (distributed) systems; (ii) to construct extensions to support mixed control and data parallel paradigms; (iii) to assess them in the light of practical situations (Salerno).

    This work is still in progress in the form of the youtoo and DMeroon systems and more recently the requirements for agent architectures derived from the Fish market developments.

  2. Comparison of the distributed virtual shared memory (DVSM) systems developed at Bath, GMD-FIRST and CNR and definition of a primitive functional model for DVSM (Southampton, INRIA).

    See next item.

  3. Comparison of the approaches to distributed garbage collection at Bath, GMD-FIRST and INRIA, and investigation of its interaction with DVSM, leading to a model integrating both facilities (CNR, Southampton).

    Although the notion of Distributed Virtual Shared Memory is now regarded as inappropriate, work is in progress on analysing and prototyping distributed garbage collection techniques.

  4. Demonstration of distributed execution of several small and at least one medium-sized Lisp application using nodes at more than one partner site (INRIA, Bath, Pisa, GMD-FIRST, Warwick, Southampton).

    This work is still in progress and should be completed shortly using a recently developed Internet data store for uncoupled communications between remote processes

  5. Investigation of the requirements for the construction of a real-time implementation of EuLisp for use in the control of autonomous agents (Bath, VUB, Southampton).

    Dropped as it is now considered inappropriate.

  6. Transfer of the results of the language design work into the ISO process for the standardization of Lisp (WG16) (ILOG, Southampton, Bath, GMD-FIT.KI).

    Complete. The Draft International Standard for ISLISP should be published by ISO in the next few months.

  7. A workshop on parallel systems (in conjunction with that on advanced compilation techniques).

    A workshop including this theme is taking place in May 1997.

Parallel applications:
  1. Retargetting the data-parallel classification program developed at GMD-FIRST, for the EuLisp environment (Bath), rewriting it to utilize higher level parallel constructs (Bath, CNR) and comparing its capabilities with LINNEO+ (GMD-FIRST, Bath, UPC).

    Completed (see 1995 report).

  2. Application of control and data parallel paradigms in existing AI applications (CNR, IIIA, UPC).

    This theme has begun with the re-implementation of NOOS (developed at IIIA) in EuLisp and the concurrent development of the WWW interface to NOOS. A parallel version of the POSSCAUSE system (developed at UPC) is being planned.

  3. Development of a concurrent implementation of LINNEO+ in EuLisp (UPC, Bath) and its application to the classification of marine sponges.

    Dropped as it is now considered inappropriate.

  4. Integration of LINNEO+, Milord II and GAR (UPC, IIIA, URV, INRIA, Bath) and their combined application to problems in urban waste water treatment plants.

    This work is proceeding at UPC and URV, but now using a new formalism for rule generation, instead of Milord II. A research report will appear in 1997.

  5. Integration of LINNEO+ with the LATIDO (intensive care monitoring) project (UPC, URV, IIIA) as a distributed application.

    Dropped due to partners' changed interests and objectives.

  6. Performance analysis over distributed systems of and by the LISPSTAT package (Southampton, Bath, GMD-FIRST).

    In progress.

  7. Development of an intelligent tutoring system as a distributed application and its integration with other components, such as Milord II (Salerno, IIIA).

    See {\bf Knowledge representation and knowledge bases}, item 5.

  8. Development of a process enactment environment with application to multiple information servers (multi-media) and distributed working (Southampton, INRIA).

    At GMD FIT.KI, the ZENO system aims to provide shared workspaces for people cooperating in a distributed, heterogeneous environment. ZENO, which is a WWW-based application, can be used to upload and download multi-media documents, and it also provides advanced discussion and negotiation support. In the context of GeoMed, ZENO is being applied for real urban and regional planning projects and for environmental decision procedures.

  9. A workshop on the application of parallelism in AI (in conjunction with that on knowledge representation).

    A workshop including this theme is taking place in May 1997.

Commentary

Parallel Models and Systems

There are two strands of development under this heading: the youtoo system at Bath and the DMeroon system at INRIA. Youtoo has stabilized significantly in the past year and interfaces to the Message Passing Interface (MPI), the Tcl/Tk graphics library and the Nexus distributed programming library have been completed and linkages to a SQL database (mSQL) and to the daVinci graph drawing package are in development. An internet data store and MUD architecture have also been prototyped with a view to support wide area distributed applications and specifically a demonstrator based on the fish market work (see below).

Development has continued of the distributed programming system reported last year, in particular, the emphasis on interoperability is making it relatively straightforward to construct bindings between youtoo (the new implementation of EuLisp) and existing packages (Tk widget library, the Message Passing Interface (MPI) standard for distributed processing, and the Multipol distributed data structure library). At the same time, work has continued at INRIA on weakly coherent distributed memory systems, distributed garbage collection and the provision of these facilities as an Applications Program Interface (API). We hope to link these complementary lines of research in the coming year.

Reflective Architectures and Knowledge Representation

Under the headings of Reflective Architectures and of Knowledge Representation, there is considerable interest in, and a shift towards, multi-agent systems, which fits well with the developments on language systems noted above. Specifically, there is activity looking at frameworks for parallel and distributed processing, social issues in multi-agent systems (Warwick), the logical formalism of reflective architectures, based on using Dynamic Logic as a common logical framework to describe and identify the most relevant formal characteristics of Multi-Language Logical Architectures (MLA) and then to investigate the expressive power of the Knowledge Bases that can be built upon them (IIIA), a reflective blackboard architecture (Pisa and Warwick), agent applications in administration (funded by the Belgian Government at VUB), and electronic commerce and electronic negotiation and mediation (GEOMED - GEOgraphical MEDiation) funded by the EC Telematics Programme, Information Engineering, DGXIII (VUB, GMD).

Multi-agent systems

A particularly strong collaboratory theme in the past year has been the modelling of the Spanish fishmarket (la lonja) as a multi-agent system. The first version of this was developed between CNR Naples and IIIA Bellaterra and reported in publication [1] below. Subsequently, young researchers from IIIA came to Bath to develop further versions - using the distributed programming environment reported earlier - the results of which are to be published in a paper to appear in the 1997 report. This theme continues to provide a fruitful line of development as we explore formalization of different bidding protocols for electronic auction houses.

During his stage in Bath, Juan A. Rodriguez, along with Julian Padget, concentrated on the analysis, design and implementation of the Spanish fish market, which had been previously formalized by Pablo Noriega and Carles Sierra, since this was regarded as a good example of a multi-agent negotiation environment. Initially, two versions of the Spanish fish market were developed in C: the first one was almost functionally equivalent to that developed in PVM by Maurizio Giordano at IIIA last year, whereas the second extended the model implemented by the first, while also investigating the capabilities of MPI. A third version was then built using youtoo and MPI. Finally, a Java version of the fish market was developed in order to investigate the possibility of running electronic markets on the Internet.

Francisco Martín's visit to Bath was primarily spent developing Noostoo. Noostoo is a new version of the Noos representation language implemented in youtoo. As a result, knowledge systems developed in Noos can profit from features of youtoo such as method migration, threads, byte-code generation, stand-alone applications, and Tcl/Tk and MPI interfaces. In addition, the creation of Noostoo demonstrates both that youtoo is a useful tool to develop artificial intelligence applications such as Noos, and that Common Lisp applications can be translated relatively easily into EuLisp.

Future directions and further information

Fuller and up-to-date details of activities (past and present) are held on the World Wide Web. In particular, an online repository of project software and information is available at Southampton. The repository may be accessed directly with the URL: 
http://vim.ecs.soton.ac.uk/
or via the VIM WWW home page: 
http://www.maths.bath.ac.uk/~jap/VIM

Number of research staff working in each team of the network

The data in this section are compiled from the individual annex B forms completed by the partners, errors and ommissions excepted.

Names and nationalities of staff seconded from one partner to another during the reporting period and the duration of their secondments;

The data in this section are compiled from the individual annex B forms completed by the partners, errors and ommissions excepted.

Names and nationalities of additional staff in each team (visiting scientists, fellows) financed by the network contract and the duration of their stays;

The data in this section are compiled from the individual annex B forms completed by the partners, errors and ommissions excepted.

For each scientific meeting for which mobility was financed by the contract, date, location, purpose and nature of the meeting, and names of the scientists attending with the name of the team they represented;

The data in this section are compiled from the individual annex B forms completed by the partners, errors and ommissions excepted.

Conferences

8-9 February, Berlin

Purpose
compilation for parallel execution
Nature
technical discussion
Participants
Julian Padget (Bath), Angela Sodan (GMD-FIRST).

25-26 March, Paris

Purpose
ISO WG16 working group held at ILOG s.a.
Nature
standards meeting
Participants
Julian Padget (Bath), David DeRoure (Southampton), Pierre Parquier (ILOG), Bruno Haible (ILOG), Ulises Cortes (UPC)

22-27 June, Barcelona

Purpose
preparation of joint paper
Nature
technical discussion
Participants
Antonio Gisolfi (Salerno), Vincenzo Loia (Salerno), Ulises Cortes (UPC), Ramon Sangüesa (UPC).

1-2 July, Kiel

Purpose
Compiler correctness and staging transformations
Nature
technical discussion
Participants
Julian Padget (Bath), Wolfgang Goerigk (Kiel), Friedemann Simon (Kiel), Hans Langmaack (Kiel).

23-25 September, Tarragona

Purpose
Fuzzy inference
Nature
technical discussion
Participants
Angela Sodan (GMD-FIRST), Vicenç Torra (URV).

26-28 September, Barcelona

Purpose
project workshop
Nature
workshop
Participants
Julian Padget (Bath), David Riaño (URV), Antonio Moreno (URV), Vicenç Torra (URV), Carles Sierra (IIIA), Pablo Noriega (IIIA), Ramon Lopez de Manataras (IIIA), Joan Rodriguez (IIIA), Franciso Martín (IIIA), Angela Sodan (GMD-FIRST), Hans Voß (GMD-FIT.KI), Nikos Karacapilidis (GMD-FIT.KI), Markus Mueller Ulm (Kiel), Edwin de Jong (VUB), Mario Mango Furnari (CNR Naples), Maurizio Giordano (CNR Naples), Giuseppe Attardi (Pisa).

30 September-2 October, Salerno

Purpose
planning for exchanges later in the year
Nature
technical discussion
Participants
Ulises Cortes (UPC), Ramon Sangüesa (UPC), Antonio Gisolfi (Salerno), Vincenzo Loia (Salerno).

1-4 November, Paris

Purpose
preparation of joint paper
Nature
technical discussion
Participants
Luc Moreau (Southampton) and Christian Queinnec (INRIA)

Joint publications authored by scientists from more than one of the participating teams;

  1. Napoli, C., Giordano, M., Furnari, M., Sierra, C., and Noriega, P. A PVM Implementation of the Fishmarket Multiagent System in the proceedings of ISAI/IFIS 1996, Cancún, Maxico, Nov. 12-15 1996, pp. 68-76

  2. Torra V. and Sodan A., A multi-stage system in compilation environments, Report de Recerca, DEI-RR-97-001, Universidad Rovira i Virgili, 1997.

  3. Sodan A. and Torra V., Configuration Decisions for Mapping by Fuzzy Inference, Technical Report, GMD-FIRST, Berlin.

  4. Queinnec C. and DeRoure D., Sharing code through first-class environments, Proceedings of 1996 ACM SIGPLAN International Conference on Functional Programming, pp251-261., ACM Press, New York.

  5. Queinnec C. and Moreau L., On the Finiteness of Resources in Distributed Computing, INRIA Research Report 3147, 1997.

Julian Padget, jap@maths.bath.ac.uk, this version April 29, 1997