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

Annual Progress Report for 1997 (Year 4 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).

    Completed (see 1996 report).

  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).

    Completed (see 1996 report).

  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).

    The final work on this topic was completed this year with the new stream model for EuLisp (developed in collaboration with Pisa and Southampton) and support for the serialization and deserialization of objects in communication between EuLisp and Java.

  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).

    The knowledge-level approach has been applied to the design of distributed knowledge systems (knowledge based multi-agent systems), which allows to cope nicely with the inherent complexity of dynamic task decomposition and allocation. Thanks to the explicit modelling of cooperation strategies, agents and meta-agents can cooperate to self-configure and re-configure according to an on-the-fly analysis of problem instances. Reflection is seen as a local analysis activity, each agent having its own partial view on the problem. The cooperation strategy is then the glue that lets all the partial competencies integrate into an implicit global problem solver.

    This approach provides two-level life-cycle support: firstly, the running systems are compiled from a high-level model and operate according to the goals declared in this model. The system as a whole may be considered as using its own model for self-validation. Secondly, meta-level agents are fully empowered for reporting discrepancies between the agent activities and their model, which is the kind of feed-back a knowledge-engineer expects from such systems.

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).

    VUB has been working on a conceptual design paradigm for agent-based multi-media applications, called 'Competition for attention'. Agents are active in a virtual world that is loosely coupled with the real world. Rather than a replica of the real world, the agents world is intended to support users in information rich environments (managing the information push). While competing amongst each other for the attention of the user, agents in the virtual world will contribute to providing the user with the right information at the right moment. Real and virtual agents co-habit in this mixed reality. The approach has been presented at the 4th Intl. Agent Theories and Languages Workshop

    Furthermore, a model for designing multi-agent systems has been developed. This model is called the Coordination Signal Framework (CSF), and defines classes for an Environment, the Agents in it, and the Interaction between these, and has been described in the OMT formalism. The method is general (i.e. not restricted to an application domain), and has as one of its main benefits that domain-specific information is modeled only in the Environment and Agent classes, thus allowing general purpose agents to inhabit and adapt to unknown environments.

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

    The new theme centred on teaching about objects in museums, mentioned in last year's report, has seen further development, including the prototyping of an agent-based tutoring architecture and a first demonstrator of the concepts.

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

    A novel approach to this problem is being explored at VUB and by a research student at Bath, looking at the origins of language. A set of principles and a general architecture is proposed that may explain how language and meaning may originate and complexify in a group of physically grounded distributed agents. An experimental setup is introduced for concretising and validating specific mechanisms based on these principles. The first results from experiments show the emergence of distinctions, of a lexicon and of primitive syntactic structures.

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

    Workshops including this theme took place in May and December 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).

    Completed (see 1996 report).

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

    Completed. A paper was published 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).

    The technique of quasi-in-line method caching, indicated in the 1996 report, has proven very effective, with a cache miss rate of less than 2% measured over a range of applications. The virtue of the technique is that is does not require code to be stored in writable memory as in standard method-caching, because the cache is keyed by the program counter. Although the answer is not one to the original question, we consider the task satisfactorily completed.

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

    Work has progressed on tools for constructing rule-based interpreters and the staging of computations, but the task above has barely begun.

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

    Dropped (see 1996 report).

  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.

    Completed (see 1996 report).

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

    Two workshops including this theme took place in May and December 1997.

Semantics and verification:

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

    Dropped (see 1996 report).

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

    Completed (see 1996 report).

  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 is still in progress on the development of executable rule-based specifications of operational semantics which can be separated automatically into a compiler and an executor.

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

    Major progress has been achieved on rigorous compiler and compiler implementation verification for transformational Lisp programs, in particular for a verified Lisp compiler (Kiel). It will be used for rigorous checker based verification of an expert system implementation for quality assurance of safety critical railway control system components.

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).

    A number of demonstrator distributed applications have been developed in NeXeme (Southamton), DMeroon (INRIA) and youtoo (Bath). In particular, NeXeme and DMeroon have demonstrated distributed garbage collection, while youtoo has been the basis for several implementations of the Fishmarket electronic trading scenario, support for multi-lingual multi-threaded programs and a pi-calculus interpreter is under development.

  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).

    Distributed garbage collectors have been demonstrated for DMeroon (INRIA) and NeXeme (Southampton). Completed.

  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).

    An Internet data store demonstrator was developed last year based on the Harvest HTTP cache, but it has not yet been possible to integrate this with any of the existing distributed systems. Unfortunately, problems with firewalls have prevented multi-site operation.

  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 (see 1996 report).

  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 (see 1996 report).

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

    Two workshops including this theme took place in May and December 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 continued with a visiting researcher (Enric Mor) beginning the implementation of the Milord II knowledge based systems architecture in EuLisp. Unfortunately, this was not completed due to illness.

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

    Dropped (see 1996 report).

  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.

    Completed. See the report Rule generation from real data: GAR meets LINNEO+ list below.

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

    Dropped (see 1996 report).

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

    Work continues on this subject at Southampto, funded by a UK government project.

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

    See 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).

    Work continues on Zeno under the EC-funded GEOMED project.

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

    Two workshops including this theme took place in May 1997 and December 1997.

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

while this report and its embedded links can be viewd via:

http://www.maths.bath.ac.uk/~jap/VIM/report97.html

The project is currently negotiating with Springer to publish the combined proceedings of the two workshops in the Lecture Notes in Computer Science series. Meanwhile, two papers on agent interaction for electronic commerce are to appear in the journal AI Communications.

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

Meetings

10-11 January, Barcelona

Purpose:planning for TMR application
Nature:technical discussions
Participants:Tom Gordon, Hans Voss, Julian Padget, Carles Sierra, Enric PLaza, Ulises Cortes

23-25 January, Cambridge

Purpose:planning TMR application
Nature:technical discussions
Participants:Julian Padget, Carles Sierra, Pablo Noriega

13-14 February, Berlin

Purpose:mapping work to processors in distributed systems
Nature:technical discussion
Participants:Julian Padget (Bath), Angela Sodan (GMD-FIRST)

13-14 March, Pisa

Purpose:(de)serialization of Java/EuLisp objects and EuLisp/Java interoperability
Nature:technical discussion
Participants:Julian Padget (Bath), Giuseppe Attardi (Pisa), Maria Simi (Pisa), Andreas Kind (Pisa)

7-11 April, Naples/Milan

Purpose:shared distributed memory
Nature:technical discussion
Participants:Furnari, Queinnec

1-3 May, Lanjarón

Purpose: project workshop
Nature: workshop with invited speakers: Nick Jennings (Queen Mary and Westfield College, University of London) Henry Prakken (Vrije Universitet, Amsterdam), Jean-Pierre Briot (Université Paris 6)
Participants:all partners - full programme available at http://www.maths.bath.ac.uk/~jap/VIM 37 people in total.

16-18 May, Southampton

Purpose:multi-energy programming
Nature:technical discussion
Participants:Moreau, Queinnec

25 May, Lausanne

Purpose:argumentation-based and decision making support system (Hermes) for preventive medicine
Nature:technical discussion
Participants:Karacapilidis, Trousse

23-30 July, Barcelona

Purpose:preparation of joint papers
Nature:technical discussion
Participants:Gisolfi, Cortes, Sangüesa

21 August-12 September, Paris

Purpose:object serialization, origins of language
Nature:technical discussion
Participants:Steels, Queinnec, Attardi, Simi

5 November, Rocquencourt

Purpose:argumentation-based and descision making support system (Hermes) for complex software engeneering
Nature:technical discussion
Participants:Trousse, Psycho-ERGO members (Detienne, Visser)

28 November, Berlin

Purpose:total compilation techniques
Nature:technical discussion
Participants:Goerigk, Sodan

4-6 December, Ravello

Purpose: project workshop
Nature: workshop with invited speakers: Stefano Cerri (Universitá degli Studi di Milano), François Pachet (Sony CSL, Paris)
Participants:all partners - full programme available at http://www.maths.bath.ac.uk/~jap/VIM 29 people in total.

April, May, September, December, Bellaterra

Purpose:knowledge representation
Nature:one day technical discussions
Participants:Torra, Godo

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

  1. Luc Moreau and Christian Queinnec, On the Finiteness of Resources in Distributed Computing, INRIA Research Report 3147, April 1997.
  2. Luc Moreau and Christian Queinnec, Design and Semantics of Quantum: a Language to Control Resource Consumption in Distributed Computing published in proceedings of Usenix Conference on Domain Specific Language, DSL'97, pp183-197.
  3. Luc Moreau and Christian Queinnec, Distributed Computations Driven by Resource Consumption, In IEEE International Conference on Computer Languages (ICCL'98), Chicago, USA, May 1998. Also University of Southampton Technical Report, April 1997.
  4. Riaño D., Cortes U., Rule generation from real data: GAR meets LINNEO+, Research report LSI-97-17-R, Universitat Politecnica de Catalunya, 1997.
  5. Riaño D., Cortes U., Rule generation and compactation in the WWTP problem. Computacion y Sistemas v1 n2. 1997
  6. Torra V.,Godo L., On defuzzification with continuous WOWA operators, Report de Recerca, DEI-RR-97-006, Universitat Rovira i Virgili, 1997.
  7. Torra V.,Godo L., On defuzzification with continuous WOWA operators, Actas del VII Congreso Espanol sobre Tecnologias y Logica Fuzzy (ESTYLF'97), 227-232, Tarragona, 1997.
  8. Torra V., Godo L., Averaging continuous distributions with the WOWA operator proceedings of the Second European Workshop on Fuzzy Decision Analysis and Neural Networks for Management, Planning and Optimization (EDFAN'97), Dortmund, 1997.
  9. Sodan A. and Torra V., A multi-stage system in compilation environment, Fuzzy Sets and Systems Journal, accepted for publication.
  10. Sodan A. and Torra V., Mapping Decisions by Fuzzy Inference, proceedings of ICA3PP'97, Melbourne/Australia, December 1997.
  11. A. Kind, G. Attardi, Interoperability between the EuLisp and Java Programming Languages, Technical Report, Dipartimento di Informatica, Universitá di Pisa.

Julian Padget, jap@maths.bath.ac.uk, this version April 20, 1998