This document proposes an extension to Scheme as Agent Interface Description Language. Languages such as KQML and AOP are well known as agent communication/programming languages. However, KQML for example, lacks important features to the modern agent technologies specified in the FIPA's First Call for Proposals. Obviously we need a higher level of language that satisfies these criteria. Scheme is chosen for several reasons. (1) Scheme can dynamically program agent interface, communication protocol, message types and contents, security and lifecycle support to fulfill the criteria. (2) There are enormous contributions from the AI world of computer science to the agent computing technology. Scheme is compatible with most of them. (3) Scheme is a powerful language with "closure" and "continuation" to support distributed multi-agent communication model either statically or dynamically. (4) Scheme is a compact language that even a palmtop PDA can contain the interpreter. (5) You can use Scheme to program internals of your agents as well as to specify the external interface. Though this is not mandatory (not to be standardized), it proved to be an elegant and effective method to program the multi-agent communication system by the experiment of Metamedia project at Tohoku University and Comtec. The document also describes extension to Scheme, conformance to the criteria and application models mentioned in the Call for Proposals.
FIPA's First Call for Proposals (CFP1) [1] lists technologies and criteria in terms of selected applications to be realized. However, from a standpoint of language, following re-organization may be useful:
Practically any programming language can be used for Agent Programming Language. It cannot be standardized. (However, Metamedia project at Tohoku University and Comtec proved it an elegant approach to have the same language program the external interface definition and the internal implementation of agents.)
The main purpose of the Agent Interface Description Language is to define the external interface of an agent and interaction protocol among agents statically and/or dynamically in terms of syntax, semantics and pragmatics. The protocol specifies message types and contents. The language must have built-in support (or ability to extend itself to support) for security and lifecycle model.
Agent Communication Languages such as Knowledge Query and Manipulation Language (KQML) [2] produced by ARPA Knowledge Sharing Effort is well known. It provides a message format and message handling protocol supporting knowledge sharing among agents. Knowledge Interchange Format (KIF) [3] is another result of ARPA Knowledge Sharing Effort. It is designed to describe the information content transmitted between agents and shared conceptual vocabularies or ontologies that communicating agents must share in order to understand each other. However, FIPA requires more than a static sharing of knowledge and ontology for agents. FIPA's requirements include dynamic generation, relocation and destruction of an agent, authentication and integrity management, transfer of control, delegation of authority, description of execution model and coordination. KQML and KIF look good candidates for Message Types (5.3.2) and Message Contents (5.3.3) respectively, but KQML and KIF alone cannot satisfy the criteria.
In this proposal, we concentrate on 5.2.2 Agent Interface Description Language (AIDL). Other sections of the above taxonomy will be touched in the Appendix as "possible solutions."
The following picture illustrates proposed agent communications architecture.
The bottom half of the picture is internal implementation of agents. It may be written in any language. On the agent implementation, a Scheme [4] [5] interpreter manages interface definition for import and export, communication protocol, message types and contents, security support and lifecycle support.
Of course, Scheme may program agent implementation and doing so has a great advantage in this architecture. But this cannot be forced to everyone. If implementation language is not Scheme, a library to interface between Scheme and the implementation language will be required. Interfaces to popular languages such as C, C++, Java may need a standardization, which is beyond this proposal.
In either way, agent implementation passes communication parameters to Scheme interpreter and Scheme communicates with other Scheme in S-expressions (S for symbolic). An S-expression is a fully parenthesized prefix notation for lisp-based programs and data. Below are some examples:
(("London" "New York" 3460) ; distance in miles
("New York" "Tokyo" 5740) ; semicolon starts comments
("Tokyo" "Torino" 6130) )
(define (exchange lire . new-rate) ; currency exchange program
(let ((rate (if (null? new-rate) *current-rate* (car new-rate))))
(* lire rate) ))
(evaluate ; KQML example
:language KIF :ontology motors :reply-with q1
:content (val (torque motor1) (sim-time 5)) )
(reply
:language KIF :ontology motors :in-reply-to q1
:content (scalar 12 kgf) )
Note that data, program and protocol data have the same syntactical structure. An agent can send a program to another agent to be executed remotely, as well as data for regular RPC-based communication. The interface definition, communication protocol, message types and contents, security and lifecycle support can be dynamically programmed and even negotiated by agents at run-time. If an agent A sends a KQML engine and router to another agent B in the form of Scheme program to implement the protocol, B will be able to talk to A with KQML even B's original implementation did not support KQML. The same dynamic programming is possible for other elements of agent-agent interaction.
Scheme programming language is a dialect of lisp. Like most lisp siblings, it takes an S-expression as input and put out an S-expression. Scheme program is also written in S-expressions. That is, there is no syntactical distinction between program and data. A possible scenario is then agent A sends a Scheme program to other agent B and B executes (or "evaluates" in the lisp terminology) that program to communicate to A with the protocol and messages described by that program. In other words, since the program specifying the protocol and the data specified by the protocol belong to the same syntax category, the communication between agents, whichever it is a program or data, can be handled by the single presentation layer in the OSI reference model. (The presentation layer takes care of abstract and transfer syntax while the application layer deals with semantics and pragmatics.)
Not only protocol data but also protocol itself, in the form of program that describes the protocol, can be sent, negotiated and executed by distributed agents. The dynamic programming model is more abstract method of standardization than specifying a static protocol. Since agent technology is still a growing area of research and development, such a higher level of standardization will be desirable. This way, interoperability among agents for both remote procedure call model specified by static protocol and distributed mobile agent model that dynamically travels in the network can be guaranteed.
The term "agent" can be construed by many aspects: robotics, psychology, computing and communication theory, etc. Artificial Intelligence is one of the approaches that have made a great contribution to the agent technology: AOP, KQML, KIF, KRSL, Ontolingua, LOOM, to name a few. Most of them are best to be used as Interaction Protocols, Message Types and Message Contents in the CFP1. Since Scheme is a dialect of lisp, it suits well to such S-expression based technologies.
A closure is a Scheme function with its private internal binding (assignment of values to variables). In that sense, a closure can be regarded as an object or an agent that has its own internal state, program logic and external interface. The code below shows a simple example.
> ; comment: '>' is a scheme prompt
(define (add-n n)
(define (return-closure m) (+ n m)) return-closure )
> (define plus-1 (add-n 1))
> (plus-1 3)
4
> (define plus-10 (add-n 10))
> (plus-10 5)
15
> (plus-1 6)
7
> (plus-10 100)
110
The first three lines define a function named "add-n" that takes a numeric argument (n) and returns a function closure that adds the original argument (n) and an argument to the returned function (m). Then, plus-1 is a closure generated by (add-n 1), which takes an argument and add the argument to 1. In other words, add-n is an agent generator. The generated agent (plus-1) has an internal state (the original argument n = 1) and accepts a parameter (m) and does a job of addition. Closure plus-10 is another agent generated by calling add-n with parameter 10. Closures plus-1 and plus-10 do not interfere with each other. These closures are autonomous, persistent objects in a single Scheme interpreter but distributing the closures over the network with relevant network extension to Scheme makes it possible to regard them as distributed agents in the network.
One of the most powerful and unique concepts of Scheme programming language is the notion of "continuation." A continuation represents an entire future for a computation in the middle of the process. For example, Agent A can stop the current work, save the continuation to a variable, send the variable to agent B and B can continue the task from the point that A has just suspended. This idea is useful in a situation like "I have dripped a cup of coffee. Now is your turn to put a milk and sugar in it. Then pass it to the boss." Continuation can be used to implement static non-local exit (block and return-from in Common Lisp), dynamic non-local exit (catch and throw in Common Lisp) and coroutines such as generator-consumer problem as follows.
> (define (generator consumer-continuation)
(do ((output (generate-something) (generate-something)))
(#f)
(set! communication-pipe output)
(set! consumer-continuation
(call-with-current-continuation consumer-continuation) )))
> (define (consumer generator-continuation)
(do ()
(#f)
(consume-anything communication-pipe)
(set! generator-continuation
(call-with-current-continuation generator-continuation) )))
> (generator consumer)
Generator: generated: 0
Consumer: consumed: 0
Generator: generated: 1
Consumer: consumed: 1
Generator: generated: 2
Consumer: consumed: 2
:
:
Consider generator and consumer as cooperating agents. The agents can exist in a same Scheme environment or in a distributed network provided necessary extension to Scheme is made to manage shared environment and distributed continuation.
Scheme is a compact language. The IEEE standard document is just 51 pages long. The language specification is extremely compact, especially comparing it with Common Lisp [6] which official book is over a thousand pages. A paragraph that best describes the spirit of Scheme appears at the beginning of the specification:
Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary. The Scheme programming language demonstrates that a very small number of rules for forming expressions, with few restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.
An essential subset of Scheme can be implemented in less than 100 kilobytes, which is small enough to be included in even a palmtop PDA.
Scheme programming language specified in the IEEE standard needs to be extended to support shared, distributed "environment." An environment is a set of all visible bindings (assignment of values to variables) in effect at some point in a program. The shared, distributed environment is a basis for distributed continuation and distributed closure.
Metamedia project introduced a concept of "agent space" where distributed environment is maintained. The "intra agent space communication protocol" supports distributed cooperating features and "inter agent space communication protocol" does not. The project adopted a combination of URL [7] and package system found in Common Lisp to describe the agent space and distributed environment. A package is a data structure that maps print names to symbols, similar to scope operator (::) in C++. But there is a problem of inefficiency with the implementation and we are open to any suggestion that makes better implementation of distributed environment over the network.
CFP1 says:
No problem for these items.
OMG currently does not specify any mapping of CORBA components to Scheme. But we can propose to OMG the IDL mapping, pseudo objects mapping such as BOA, ORB, to support dynamic invocation and dynamic skeleton interfaces.
Any extension can be made by dynamic programming of agents.
Since the proposed scheme-based dynamic interface programming model is very flexible, virtually any application model shall be feasible including Personal Assistant reference model, Personal Travel Assistance reference model, Audio/Visual Entertainment and Broadcasting reference models and Network Provisioning and Management reference model described in CFP1. Here, as another example, let's think about Telescript application model. To quote their web page:
Telescript is an object-oriented, remote programming language. It is a platform that enables the creation of active, distributed network applications. There are three simple concepts to the language: agents, places and "go". Agents "go" to places, where they interact with other agents to get work done on a user's behalf. Agents are in fact mobile programs capable of transporting themselves from place to place in a Telescript network.
Telescript agents "go" to "places" where they "meet" each other. The picture below describes how this Scheme-based AIDL implements the mobile agent model.
A mobile agent dynamically programs in place agent by sending a Scheme code to implement the remote agent. When the dynamically programmed remote agents meet and talk to each other to do some transaction, place agent offers necessary infrastructure such as mutual exclusion, naming service and security support.
This appendix addresses AIDL-related topics that I cannot make proposals. I have some ideas and recommendations, though, which are listed here just for your information.
Currently Metamedia offers no security support. We are still investing the possibilities of Scheme-based multi-agent communication system without having to worry about security, safety and other restrictions. But we understand that the dynamic programming architecture is identical to a virus infection in essence. So I have nothing to suggest about security. However, security and safety model proposed by Telescript seems more concrete than that of Java or Safe Tcl to me and we can learn a lot from there. There is a good article about Telescript security titled "Safety and Security in Telescript."
We have KQML for the Message Types and KIF for the Message Contents. They are well matured and widely used. But there are other technologies that may apply to this area.
As mentioned before, specifying a language is a higher level of standardization than specifying a protocol because a language can dynamically establish a protocol. If we adopt such a dynamic language, we do not need to specify a protocol in a standard document statically. Agent technology is growing rapidly and we have to be very careful about establishing a standard to keep the interoperability and extensibility with existing and future technologies.
Note: An opposite example is OMG IDL in CORBA [8]. OMG IDL defines interface statically, i.e., IDL code must be compiled to run-time language code and linked in the executables. Even the dynamic invocation and dynamic skeleton interfaces require static IDL description of pseudo objects for ORB (Object Request Broker) and BOA (Basic Object Adapter). That is why OMG had to specify GIOP (General Inter-ORB Protocol) and its TCP/IP mapping, IIOP (Internet Inter-ORB Protocol) later on to maintain interoperability.
[1] Association for Foundation for Intelligent Physical Agents, FIPA's First Call for Proposals, Tokyo, Japan, October 1996. http://www.cselt.stet.it/fipa/tokyo/cfp1.htm
[2] Tim Finin et al., Specification of the KQML Agent-Communication Language, The DARPA Knowledge Sharing Initiative, External Interfaces Working Group, 1993. http://www.cs.umbc.edu/kqml/papers/kqmlspec.ps
[3] Michael R. Genesereth et al., Knowledge Interchange Format Specification, ANSI X3T2 Ad Hoc Group working draft, 1995. http://logic.stanford.edu/kif/specification.html
[4] Institute of Electrical and Electronics Engineers, Inc., IEEE Standard for the Scheme Programming Language, sponsor, Microprocessor and Microcomputer Standards Subcommittee of the IEEE Computer Society, IEEE Std 1178-1990, 1991.
[5] William Clinger and Jonathan Rees (Editors), The Revised^4 Report on the Algorithmic Language Scheme. http://www-swiss.ai.mit.edu/~jaffer/r4rs_toc.html
[6] Guy L. Steele, Jr., Common Lisp the Language, 2nd edition, Digital Press, 1990.
[7] T. Berners-Lee, et al., Uniform Resource Locators (URL), RFC 1738, December 1994. ftp://ds.internic.net/rfc/rfc1738.txt
[8] Object Management Group, The Common Object Request Broker: Architecture and Specification, Revision 2.0, July 1995. http://www.omg.org/corba2/corb2prf.htm