) [GK94]. This is an interesting definition, but not one we
have grounds for adopting this early in the thesis. Consequently we
avoid the added complexity, and continue to concentrate on the simple
term of ``agent''.
Fred Johansen
Department of Informatics
Norwegian University of Science and Technology (NTNU)
7055 Dragvoll
NORWAY
This thesis discusses knowledge agents and software for their implementation. The term knowledge agent is defined as a particular kind of intelligent computer agent that deals in knowledge, in the way of keeping, querying, distributing it or communicating it, whether as a primary or secondary function. Such an agent is viewed as a member of a community of similar entities, some of which may be interfaces to human users, typically in a networking environment.
Apart from a general introduction to the field, our treatment in this thesis will be twofold; one an outline of the issue's underlying theoretical framework within the field of Artificial Intelligence (AI), another a look at software for practical implementations.
Within the latter we concentrate on KQML, a language for inter-agent knowledge communication, and its use over the Internet. Also, self-constructed example programs in the languages C and Perl will be included that demonstrate how Unix system programming may be used to establish such a kind of communication.
We conclude the thesis with a discussion on the benefits of employing intelligent agent technology within the field of Case-Based Reasoning. Although this is a research direction which has emerged only recently, we think that it is a fruitful one, in that the distributed computing scheme of agents will lend itself well to the segregation of represented memories into separate non-generalized cases.
The first thing I did as an AI major was to attend a meeting with my advisor, professor Agnar Aamodt, to discuss the preliminary subject of my thesis. Naturally enough, this meeting staked out a course that combined my own interests with the Department's. One theme has remained in focus throughout the development since then, namely that of Case-Based Reasoning (CBR).
Another early idea was to look at the associations between cases in a semantic net perspective, and at what kinds of methods of inference that could be employed on these associations. The very first work title of the thesis was in fact ``Methods of inference for combined case-based and semantic net reasoning''. But this approach has been altered somewhat during the last two years, to the effect that the resulting thesis only hints of possibilities in this direction, rather than examining them thoroughly.
Because, as time passed, I discovered that the approach I would like to take to these issues was one related to intelligent agents. In a greater perspective, such intelligent programs operating on a computer network and the associations that can be established between them could conceivably be used to implement semantic associations between abstract concepts and individual cases from a large number of case-bases (or knowledge-bases). One might envision a semantic net, or a ``net of knowledge'', spread out over a great number of agents on the Internet, for example.
Whether such ideas are feasible or not, and whether they may represent an improvement over current-day AI programs, are both questions that will be discussed in this thesis.
Right from the start, my interest in agents was related to another, in networking and network programming. My curiosity in that area provided me with some basic understanding of the programming issues involved in establishing an agent technology -- from bottom-up, so to speak. This thesis is in fact like a ladder, with the basic issues of agents at the bottom, and with the main part of the climb concerned with the introduction of some aspect of intelligence into these agents. And at the top of this ladder, at the end of the thesis, is the place of a discussion of the application of intelligent agents in CBR.
Actually, combining these two themes has been a great challenge. There is only so much you can do within the time to write a Master's thesis, and some hard choices has had to be made. Among them is the fact that not CBR, but agents will be the main focus of most parts of this work.
As the reader will understand, the thesis is a product of both high- and low-level aspects. But it is also an attempt to create an organic whole from these aspects. I personally never merely wanted to piece some fragments together and proceed to call the result a thesis. Better to present a continuous path from start to finish, that could conceivably lead the reader to a heightened understanding of the field.
Therefore the work do not start on a high level, but instead introduces the reader to the field of agents in a very general way. This is not a doctoral thesis or a research application. It is, in my humble opinion, a natural forum in which to present my own understanding of the subject matter, right from the basics on up to the highest level. This is the way I hope to demonstrate that the money and efforts spent on my education have not been wasted, and that some real competence has resulted from it all, in knowledge as well as in practical ability.
Producing this thesis as a work in print, as well as represented in hypertext, involved a few tools and languages which are generally useful in programming and document typesetting. I find it natural to give these a mention, especially since the subject matter of the thesis includes not only AI agent programming with high-level languages like KQML, but also conventional programming with symbol-level languages like Perl[WS91]. As we shall see, Perl was also used in the production process.
The formats and languages involved might also be considered to be of some interest in a representational perspective. The representation of knowledge is a subject of section 3.3, and translation between representation formats is generally central in regards to the issue of knowledge communication between intelligent agents.
Instead of using a WYSIWYG editor in which to write the thesis, I chose to use a typesetting system in which I would have a more flexible control over the appearance of the result. Perhaps not the easiest of approaches, but no doubt one of the more interesting ones.
The natural choice of such a typesetting system was TeX, or rather, LaTeX[Lam94], which is a macro package for use with the former. (The point of a macro package in this context is to be able to employ logic names like ``header'' in the source text, instead of having to specify the exact visual appearance of each header. This separates the task of writing the text from the task of designing its appearance.)
PostScript is a format for device-independent graphical document representation for use in the production of printed documents. I converted the LaTeX files into PostScript with the available standard software. This process was fully automated, so any and all tweaking I had to do could be done on the LaTeX files. The conversion to PostScript was totally transparent to the production process.
SGML [Gol90] (Standard Generalized Markup Language) is a standard for definition of document structures, as described in the ISO 8879 standard. I'd already had some experience in SGML in terms of writing my own document types. (Ie. document structure definitions for a group of document instances.) Therefore I found it natural to do the actual writing in the Qwertz SGML document type.
Qwertz [Gor92] is a document type defined at the German National Research Center for Computer Science (GMD), specially tailored for documents to be translated to LaTeX. It handles articles, reports and books etc., and is well suited for writing a thesis. There are software available for automatic conversion from Qwertz to LaTeX. While Qwertz may be criticized for being too heavily linked to LaTeX, making it difficult to draw upon SGML's full possibilities, it suffices nicely as long as one is writing something which is intended purely for printed publication.
Still there was the matter of learning LaTeX in order to get the exact result I wanted, but now this could be delegated to the conversion process without interfering with the creative process.
One more thing I used SGML for in this thesis was literate programming. This is a programming method aimed at making the documentation of programs easily available. In short, literate programming means that one includes the source code within the documentation, which is opposite of the conventional way of doing it. Tradition says that you should insert all your source-code documentation into comments, which are themselves placed within the source-code. The compiler typically ignores all such comments. Their only use is for the programmer in the process of writing the code. And as a result of this, the programmer often has to duplicate the documentation somewhere else, for instance in written reports or manuals.
The point with literate programming, on the other hand, is to be able to present the documentation in such a way that you will not have to scan through dozens of pages with more or less cryptic source code in order to find it.
Using a SGML document type to make documentation and source code distinct from each other, and a simple script to extract these in the form and order I wanted, I could present the program in an easy-to-understand way, with documentation and code in different typing styles. It would also be fairly simple to extract the documentation only, if there were a need for that.
Qwertz did in fact already support a simple kind of literate programming where you could extract the source code from a Qwertz document. But this didn't put a special tag on the program documentation as such, which means it was poorly designed for a large document where the program was but a small part. This prompted me to write a simple SGML DTD (Document Type Definition) myself, called Litprog. (See Appendix C.)
The programs included in this thesis were written in Litprog. I only had to write small Perl scripts to translate each Litprog version to two other versions -- first and foremost the program itself, with documentation included as comments formatted appropriately for the programming language in question, second a Qwertz version to be included in this thesis with the documentation included in a special typing style.
Snippets of these versions are included in Appendix A.
HTML (Hyper Text Markup Language -- itself a SGML document type, by the way) is the document format of the World Wide Web. There exists many converters to HTML from all kinds of other formats. I choose the program LaTeX2HTML for conversion from LaTeX to HTML, so that my thesis could be made available on the Web. It can be reached from our Department's AI Group Publications list at <http://www.ifi.ntnu.no/grupper/ai/pubs.html> .
Since the programming language Perl is a good tool for text filtering and conversion, I augmented the automatic conversion process with a couple of small Perl filter scripts to do fixes to the text where needed, thereby still producing the desired result automatically, no matter how many times I changed the source document.
The Unix Make program was used to ease the conversion and bundle together the sets of commands that I used to run it. Thus I had only to type ``make'' in order to instigate the following conversion process:
The source document (Qwertz SGML) was converted to LaTeX, which itself was converted into 1) PostScript and 2) HTML.
Using SGML meant I could write the source document in any editor that was capable of handling plain-text ASCII.
I wrote parts of this thesis at home in the vim editor (a modified version of VI) on an 286 Commodore PC running DOS. While this machine did not have the software to convert the text to graphics and present it, this could easily be done on other machines. (Like the Sun SparcStations at the university.) For my last semester I bought a Pentium PC that could perform the full set of operations itself, but before that it would not have been practical for me to write at home if I had not benefited from the use of SGML.
The last months were spent writing in the custom SGML mode in the GNU Emacs editor.
My thanks to Agnar Aamodt for being a constant source of new insights and inspiration. And to the Department as such, for making my four years there a time well spent.
Finally I would like to dedicate this thesis to my parents, who have always encouraged me to think for myself.
Fred Johansen
Trondheim, Norway
November, 1996
This thesis is a work comprised of several elements. Allow us to describe it with reference to a couple of axes (dimensions).
On the theoretical/practical axis, the thesis has first and foremost a theoretical focus on a specific theme in the field of Artificial Intelligence (AI), namely the field of agents. This is the main thread of the work. While all its other elements do contribute to the sum of the thesis as a whole, they must in the final analysis be measured against how well they support this theoretical focus.
At the other end of this axis, we include practical considerations on implementation issues, with regards not only to programs strictly within the field of building and maintaining AI agents, but also with respect to related tasks, like networking.
Another axis is the granularity of focus, ie. whether one concentrates on miniscule details or presents the field from a bird's-eye view. Now, in chapter 2 we will be introducing the concept of an ``agent'' and trying to convey to the reader a general idea about the field it represents. It is only natural to do this by giving our version of the ``big picture'', that is, by using a broad focus. Later, in chapter 4, we will be taking the same approach when explaining some basic aspects of the programming of networking agents. This latter chapter will serve as a kind of general ``bottom-up'' introduction to the technical side of the subject matter.
But, we cannot keep a broad focus throughout the whole of this work. If we were to do that, we would need the space of a large book and not simply that of a Master's thesis. Our special interest here is not, after all, to describe the whole field of agents. It is, in fact, to investigate a particular group of agents -- namely those agents that communicate knowledge. This is the ``intention'' of our work, if you will. There is no fundamental reason why we have chosen this initial interest before any other; it is simply a fact that every work starts out with one, and this is ours. (Though we hope to be able to conclude it with some predictions of promising application areas for knowledge-communicating agents.)
Guided by this initial interest, as the thesis progresses it starts concentrating on only one kind of agent, or rather, on one specific method of communicating knowledge between agents. When we delve into this subject matter, especially in chapter 5, our focus becomes increasingly narrow.
However, there may be some repeated widening of the focus when we're nearing the end of the thesis, as we go into the research field of utilizing agents within the field of Case-Based Reasoning (CBR). This is a research direction that has been formed only quite recently, so our treatment of it will consist of a general discussion on the theme, and not so much a precise description of its state, simply because this has not been developed into any great detail. Hence the difficulty in keeping a narrow focus through the latter parts of this work.
So far we have mentioned a lot of terms that are central to our work, but without explicitly defining them. And most central of those is of course that of an ``agent''.
The field of agents is a large research area within Artificial Intelligence. Naturally, we will not try to cover the whole of it. Neither will we be attempting to give definitions accurately corresponding to the ``sum'' of the conceptions currently held in the field, whatever they might be. However, what we do need to do is to arrive at some definitions of terms for the scope of the thesis, so that we may get on with the job of concentrating on our main subject, namely that of knowledge-communicating agents.
The next chapter will start exploring the term of ``agent'', around which the whole of this work revolves. But we do not start without any preconceptions about it at all. As with every other complex subject, there are several points of view from which to approach it. And the point of view we're going to start out from relates to our initial interest; the communication of knowledge. Please keep this in mind during the following discussion.
To sum all of this up, chapter 2 introduces the term ``agent'', chapter 3 investigates the aspects of intelligence and knowledge in relation to agents, chapter 4 looks at some basic networking issues, and chapter 5 describes knowledge-communicating agents using the language KQML. Finally, chapter 6 discusses the use of intelligent agents in Case-Based Reasoning.
What is an agent? From our current initial standpoint, this is a difficult question indeed. If we want to answer it thoroughly, we have take it step-by-step. First, we should establish a general context, so that we have something to start from. Secondly, we should outline all the assumptions we have about the term, so that we may gain an idea about the approximate terrain and determine in which direction to go. Only when we have completed both of these tasks may we start to give an exact answer to the question.
One common definition of ``agent'' is ``one who exerts power or produces an effect'', ie. an entity that performs an action and thus initiates a (shorter or longer) chain of events.
This is as good a base definition as any. But we cannot stop here. We want to proceed to construct a definition of ``agent'' in our particular context, or a definition of some other term representing the specific kind of agent that we have in mind.
But as of yet we do not know exactly what we want. We have not even established what ``action'' means in this context.
Yet we have got to start somewhere. As a context, we consider these couple of definitions (or presuppositions) as fundamental for this thesis:
By this we mean that our discussion about agents will be limited to the sphere of computers and computer software. If not explicitly stated otherwise, everything we have to say about agents must be understood within this context. The terms ``agent'' and ``computer agent'' are thus pretty much equivalent in this thesis. (Though we will concentrate on the former.)
While parts of the Computer Science literature admittedly also uses the term ``agent'' for humans working alongside with computers or computer agents in a ``mixed'' agent environment, we intend to focus on the following kind of statement as a partial definition of our subject:
That is, an agent is not a computer, it is a piece of software running on a computer. Even though it is possible to implement an agent as a robot, where the computer hardware's only function is to run its agent software, we feel that the term agent is best used only to characterize the software in question, not the synthesis of hardware and software. We reserve the term ``robot'' for the latter.
In one sense the term ``agent'' as we construe it is equivalent
with ``software agent'', the simplest interpretation of which is
that of an agent ``made up'' of software.
However, ``software agent'' is a term being given various
definitions by researchers. One is that of ``a software component
which communicates with its peers by exchanging message in an
expressive agent communication language'' (like ACL) [GK94]. This is an interesting definition, but not one we
have grounds for adopting this early in the thesis. Consequently we
avoid the added complexity, and continue to concentrate on the simple
term of ``agent''.
Another conception of an agent is that of a ``personal assistant who is collaborating with the user in the same work environment'' [Mae94]. We will remember this definition for later -- in fact we will be taking a peek at one such personal assistant agent in section 2.3.
For now we stick to our basic definitions, the last of which simply
defines an agent as a computer program.
Now that we have a basis for the following discussion, we may ask: What kind of expectations do we have about agents? Instead of trying to put a strict definition on the term right away, let's try giving words to our basic assumptions regarding the subject, be those as vague as they may. Be aware of that this is only a preliminary investigation, and that we will be returning to the subject later.
Our initial assumptions are:
This assumption is related to the base definition above, obviously. But we need to distance ourselves somewhat from the overlap with ``human agents'' or ``actors''. Anyone interpreting the definition in a human context would naturally associate it with the concept of free will. But for us to assume that computer agents have free will (or that they will get it in the future) would be highly controversial, to say the least. We cannot base ourselves on an understanding of the concept where free will is necessary, although we have no reason for ruling it out, either.
Instead we use the term autonomous, which we in this context
define as ``self-governing'' or ``self-sufficient''
. In other words, when we speak of a computer
program as an autonomous entity, we mean an object which is separate
from the environment in which it is situated (typically the operating
system), operates under its own set of rules, and can initiate
operations by itself. This is not to be taken as absolute, in that
such programs must be isolated from other programs, but simply that
the boundaries between those and other programs are
well-defined. (An operation may be triggered by incoming
data as well as by internal calculations, etc., as long as this is in
accordance with the ``rules'' of the program.)
--
Having formulated our fist assumptions, a brief pause for reflection is in order. What characterizes our line of reasoning so far? We realize that our assumptions are not built on very solid foundations. Despite of this, they are not groundless.
The thought process so far has been guided by two requirements: 1) The base definition from every-day language. 2) Our partial definition of ``agent'' as a computer program.
What we are actually doing, then, is building assumptions about computer agents on the basis of an analogy with humans or ``human agents''.
This is an observation which makes it easy to continue formulating assumptions:
--
By the analogy with ``human agents'', an agent is a kind of individual, however primitive it may be. And it does not make much sense to view a program as any kind of individual without any other individuals of the same type it can relate to.
Put simply, we assume that the way an agent relates to other agents (ref. the previous item) must be by various means of communication.
These last couple of ``requirements'' are in fact very easy to fulfill if interpreted loosely. (And we do keep all interpretations open at this time.) It only takes a computer program that can be run by itself and is capable of performing certain calculations, as well as sending messages about them to somewhere. Indeed, both are fulfilled by most programs in existence, if we consider all kinds of output as a kind of ``sending of messages''.
The agent naturally has some function for which it was constructed to perform. Therefore, we assume it has one or more goals which it sets out to fulfill. In this sense it has intentions of reaching its goals or intentional states favoring or disfavoring certain paths to its goals before others.
It is natural to assume that for an agent to reach its goals, it has to have at least some knowledge about how to get there.
And likewise with intelligence. We naturally assume that the agent must have some kind of intelligence in order to reach its goals; in order to choose between different paths. As to exactly what kind of intelligence this requires, we leave that question open for the moment. -- Just as we do with the details of all the other assumptions. Specifying something also rules out that which falls on the other side of the specification, and it is not our intention to rule anything out at this early stage.
Where the intelligence of computer programs is concerned, we come face to face with the field of Artificial Intelligence (AI). One might suspect that insofar as a human-made program can possess intelligence, it is artificial intelligence. But whether AI as a field subsumes all the kinds of intelligence an ``agent'' may have remains to be seen.
...
As the reader probably have understood already, this list of assumptions is open-ended. There is a lot that is uncertain here, but it is not our intention now to restrict the concept in any way, but rather to describe what kind of interpretation one might put into it.
Does this mean we now know a bit more about agents? Not really, but at least we have an idea about what to look for. In the next section we will do just that; -- ie. search for something that matches our expectations of an agent.
When searching, how will we find a match? Isn't this list of assumptions too vague to act as a set of requirements? Well, certainly. Parts of what we need to investigate is how the term is actually being used, not only what we would like it to mean. Our initial assumptions are only the guidelines for this search.
Another problem is: To what extent should our expectations be taken literally? When we say, for instance, that an agent has ``intelligence'', does this necessarily mean that it has some characteristics that must be called intelligent in the same way a human being is intelligent? Or should we view this way of speaking only as a ``convenient'' interpretation of agents that may not correspond to their actual nature?
We leave this and other related questions unanswered at this time. Whether we will answer them at all in the course of the thesis remains to be seen. As for now, we proceed to investigate the actual use of the term ``agent''.
We want to find some agents. Where do we start?
The obvious answer is: On the Internet. The reason being that, not only does the net contain information about almost everything, but also that the subject of agents involves the study of computer software and communication, which are two essential concepts for the operation of the net. It is therefore very likely that we can use it to find some information about agents.
Now, how do we search for anything on the net? The natural place to start is a World Wide Web search engine.
As a starting-point for our search we chose the AltaVista WWW search engine, which is maintained by Digital Equipment Corporation (DEC). Its URL is <http://altavista.digital.com/> .
On the 22nd of May 1996 we performed some simple string searches for agents on AltaVista. Here are the strings we searched for and the number of documents that was found:
Found approx. 200.000 documents.
Found 75 documents.
Found approx. 1.000 documents.
Found approx. 3.000 documents.
Found 52 documents.
The explanation for the low score on ``computer agent'' is that this term isn't very much used in the agent literature. We shall ignore this term in the following.
As for ``knowledge agent'', only a few of the 52 pages returned used this term in an Artificial Intelligence perspective. The majority therefore failed to define it in the way we intend to do in this thesis. But more about that term later.
For now, we conclude that there is indeed a whole heap of information about agents on the web. Our biggest problem won't be to locate it, but to navigate in it.
We have to start somewhere in order to form an initial opinion about agents. Out of all the pages returned by AltaVista, we pick one describing the well-known Firefly agent. Its principal designer is Pattie Maes, known as one of the pioneers in the field of agents. We hope that this page will give us some idea of what characteristics an agent may or may not have.
We locate information about Firefly on the ``Software Agents Group'' page (<http://lcs.www.media.mit.edu/groups/agents/research.html>) at the Massachusetts Institute of Technology (MIT). One of the projects outlined by it is Pattie Maes's Firefly agent.
Firefly is a personalized music agent. It remembers your taste in music and recommends new albums to you according to how much it expects they will satisfy your taste. The basic technique used is a kind of ``word of mouth'', in that each Firefly agent communicates with other such agents and exchanges information on their users' musical preferences, ie. what albums he or she enjoys. When a user that likes many of the same albums as you do adds a new album to his or her ``like''-list, there is an increased likelihood that this album will be recommended to you by your agent.
We won't go into the mechanics of Firefly' here. Let us instead have a look at the terminology used on the Autonomous Agent Page. The term software agent is particularly interesting. In one place the page seems to state that the type of agent is distinguished by what kind of environment it operates in, to quote:
An autonomous agent is a computational system that inhabits a complex, dynamic environment. The agent can sense, and act on, its environment, and has a set of goals or motivations that it tries to achieve through these actions. Depending on the type of environment, an agent can take different forms. Autonomous robots are agents that inhabit the physical world; computer-animated characters inhabit simulated 3-D worlds; while software agents inhabit the world of computer networks.
While under a section titled Modeling Software Agents, it is stated that:
``Software agents'' provide active, personalized assistance to a person engaged in the use of a particular computer application.
Clearly, neither the term ``software agent'' nor ``agent'' is being used in any particularly consistent way here. It is nevertheless interesting that the emphasis is being put on the what instead of the how, as regards to the operation of agents. In addition to other external attributes, the kind of jobs they perform is emphasized before the manner in which they perform them.
If we were looking for a clear definition of what kind of intelligence agents may exhibit, this page doesn't give us much to go on. Instead, we may suspect that agents like Firefly are not highly intelligent computer agents that exchange knowledge (in the true sense) with each other, but more or less simple assistance programs designed to answer to some user-specific needs. (Although they might be very sophisticated in their internal operations.)
In order to affirm or deny this hunch we must obtain some kind of overview over the agent universe. Can we locate a more authoritative source on agents, ie. on the types that exist and how they differ from each other?
Tracking some agent WWW links to the Department of Computer Science of the University of Maryland Baltimore County (UMBC), we discover the AgentNews newsletter.
The AgentNews newsletter is a source for information about agents and agent technology. It is available both as a mailing list and on the World Wide Web -- at <http://www.cs.umbc.edu/agentnews/> . To quote its first issue, Volume 1, Number 1, January 1996:
AgentNews is one way to track what is happening with agent-based ideas, technologies and applications as well as related topics such as knowledge sharing, intelligent information systems, and information retrieval.
It is published on a monthly basis. All issues so far have been crammed with short pointers to what's going on in the current agent research. Reading it, it becomes apparent that the field spans a broad array of software, which may partly be due to that some of the people writing said software is using terms like ``agent'' and ``robot'' very indiscriminately.
Based on the information in the newsletter and what it leads us to find on the WWW and Usenet (news) about agents, it quickly becomes clear that there is much confusion around central terms.
There are many strange animals in the world of agents. We have for example ShopBots, ie. ``robots'' for shopping on the WWW, and WWW interface programs, and information navigators that perform simple text searches (eg. based on regular expressions) on the Web or on Usenet news. There are mail filters, meeting schedulers and planners, et cetera. But what constitutes the ``status'' of such programs as agents is difficult to establish. They are often nothing more than programs with a novel, or merely ``clever'', use of old programming techniques and algorithms.
Many of them have very little intelligence -- and even less to do with the field of AI. What we have to face is that ``agent'' is no precise term, and that there are no standard requirements that products needs to satisfy in order to earn the label.
Consequently, there are a variety of definitions of the term as well. Some researchers define it as an user-assistance program which is supposed to work alongside the user in the ``same environment'' as him or her. -- And parallel to the new promising market that is currently opening up in software for navigating large information spaces, there is a more specific (and much used) definition saying that an agent is a kind of program that helps its user in navigating information spaces according to his or her specific needs.
Neither of these are of course ``faulty'' definitions. They represent more of a shift in the way of looking at programs, and at what they can (or are supposed to) do, as opposed to the traditional view of programs as ``software machines'', than a statement about their actual abilities. Surely this is partly motivated by what people expect AI to do in the next millennium. But it doesn't imply that all the agent products that are being put out today actually exploits state-of-the-art AI technology. Clearly some of them do, but we'll get back to some of those later.
In the mean time we will have a peek at another major direction in agent research which gets a lot of publicity without necessarily having much to do with Artificial Intelligence, namely that of mobile agents.
In the past couple of years or so the word JAVA has been a highly marketed buzzword on the Internet. Basically, JAVA is a platform-independent programming language partly designed for use over the World Wide Web. JAVA programs, called applets, are compiled into byte-code and may be sent over the net to be executed on any site which has a JAVA byte-code interpreter. (Naturally, interpreting byte-code is much faster than interpreting ordinary code.)
Such interpreters have been built into WWW browsers like the Netscape Navigator, so that JAVA code may be automatically transferred from WWW servers to your browser and executed there as you ``surf'' the Web.
One other employment of JAVA technology is to send self-navigating applets out on the net. Such mobile agents can choose their own way across the net and perform each task where the conditions are most ideal, or split itself into several agents to do a job, dividing the workload over several machines and sending messages to each other to delegate the work.
Such work sharing is not a new thing, but instead of executing such programs on a multi-processor machine or on a special-purpose cluster of machines, the mobile agent's playground is the entire net. This certainly increases the possibilities inherent in such technology, though it is also leading to a few novel security problems.
JAVA is not the only available software for mobile agents, but by far the most well-known.
What is interesting about this for our discussion is not so much the technology itself, but rather the use of terms. Again we see that what is perceived as an agent need not be particularly intelligent. Indeed, the central point with the mobile agents is merely the fact that they are self-transportable. Certainly this opens up a whole new field of intelligent behavior from programs, in that it provides a basis for powerful network-wide architectures which all kinds of applications might be built on. But the intelligence itself we will have to find somewhere else.
So far we have not found a clear definition of the term agent. This is mostly due to the large amount of independent definitions in circulation, in that the term seems to have about as many definitions as there are projects (or people) associated with it.
We are not satisfied with the kinds of intelligence performed by many of the ``agents'' we have found. Therefore we decide it is time to increase our demands in this respect. The path we will follow from now on is that of seeking agents that are intelligent in the true, although general, sense of the word. In order to do that we must first have a look at the concept of intelligence itself. We dedicate the next chapter to the search for, and definition of, intelligence in agents. If we succeed in these respects we have hope of finding some agents which correspond to all of our initial expectations. -- That the other ``high-level'' level assumptions (intentions, knowledge etc.) are closely linked with intelligence should be fairly obvious.
To be fair, some of the agents and agent software packages that are mentioned in the AgentNews newsletter do seem to be within the scope of high-level AI. But seeing the way the term ``agent'' is hyped-up by some almost to the point of being misused, we see no point in trying to put an exact definition on it.
Still, we want to investigate a particular brand of agent, as mentioned in the previous chapters, and therefore we need a more precise term for that type. In order to resolve any ambiguity with regards to other kinds of agents we introduce the term intelligent agent, as a candidate for describing the sort of knowledge-communicating type of agent that we mentioned as our goal as early as in chapter 1.
In order to reach our goal we have to know more about exactly what kind of intelligence we are after. Therefore we ask ourselves: What is intelligent behavior in agents?
At this point we are well into the realm of AI. (Which we understand as the research field occupied with the construction of artifacts with one or more intelligent features.) It is therefore necessary to inquire as to how terms like ``intelligence'' and ``intelligent agent'' may be used in this field. Also, the concept of communication is of some importance. So, let us look at a few alternatives for a definition.
One possible viewpoint is that any kind of program can be said to be an intelligent agent if and only if it has some sort of communicative competence as well as some sort of intelligence. Since most AI programs already can be said to communicate with their users in one way or other, there are two ways to go with this view: Either to define all of these programs as intelligent agents, or to define the term of ``communication'' in this context as the exchange of information with a host of other agents over a network, and accordingly reward the term only to network-communicating AI programs. But both of these are perhaps a little non-descriptive, the former especially so. They are not the kinds of definition we are looking for.
Another option is to define communicative competence as the knowledge about communication. This is impractical though, for it would imply that only programs which act in accordance with a knowledge model of the subject of communication could be counted as intelligent agents.
Another distinct possibility is to view an intelligent agent as an entity operating on the Knowledge Level, which is a conceptual level different from, and higher than, the Symbol Level. (Ref. Allen Newell's famous 1982 article [New82].) The traditional way is to interpret a computer program as a symbolic machine, ie. as an entity on the Symbol Level. But in accordance with the Knowledge Level view we may define the term ``intelligent agent'' as representing a higher-level entity instead, an entity of a kind that possesses knowledge, goals, constraints, and methods to follow in order to reach its goals. There is also a principle of rationality associated with this level, which dictates that an agent will always use its knowledge in a way that ensures the achievement of its goals -- provided the agent has the knowledge needed.
Although Newell's initial notion of the knowledge level represented a highly intentional and purpose-oriented way of describing a system, there has been some modification of the idea over the years since its conception. More recent advances in the areas of knowledge acquisition and knowledge modeling have made this notion of the knowledge level more concrete and directly applicable for systems analysis and design, as exemplified by methodologies such as KADS [WSB92], Generic Tasks [Cha86] and Components of Expertise [Ste90b].
In chapter 2, we posed several assumptions about agents, and left open the question of whether we should understand our assumptions literally or not. Were they merely convenient ways of thinking about agents or would they prove to be related to their essential nature? This sort of question may be rephrased and re-directed at the Knowledge Level viewpoint. When we describe an object in terms of this viewpoint, do we gain anything at all in terms of information value, or do we simply paint the object in a different light? That is, is there a sense to this viewpoint, or is it just a useless anthropomorphism?
Although we will not try to show conclusive evidence for this, we assume that there is a sense to it. What we gain by using it is power of expression. Parallel to, for instance, the gain from thinking in higher-level programming languages instead of lower-level ones, and from reasoning about human actions instead of about chemical reactions in our bodies, we gain the advantages of enhancing our own tools of reasoning about agents. And since this is a design issue, we therefore stand to increase the height of performance to which agents might attain.
This is not to say that at the present or at anytime in the future, all the ways of speaking of human reasoning will apply equally well to agents. But it means that the vocabulary that we need is more or less in place already, although it could maybe need some tweaking to fit this new context. It remains only to be seen how well the construction and actions of agents answer to the meanings of the words in such a vocabulary. This is a multifaceted question; partly theoretical -- for instance: May agents have the capability to have the same type of ``cognition'' as humans?
But there are also questions like: May agents have both general and specific knowledge? The only aspect of this question which is of any relevance here is in fact more of a practical than a theoretical nature. We will explain why:
First, be aware of that we have already answered the question of whether agents may have knowledge at all, viz. the the concept of the Knowledge Level itself. Representing specific knowledge in agents is not a problem either. Such representations have been in use for a long time, for instance in conventional database technology. And although there is a rather fundamental conceptual boundary between general and specific knowledge, they are not at all distinct. The one rely on the other, so to speak, and if one can represent knowledge about specific objects, one can just as well represent knowledge about general ones. (Consider the numbers in mathematics, for example.) There may still be unsurmountable practical difficulties in representing all general (or specific) knowledge. But actually representing some of it is no problem at all.
Therefore, the real remaining question for us here is a practical one: Can future agents be relied upon to use knowledge bases that are sufficiently large for real applications, and can they combine their specific and general knowledge in a sufficiently fruitful way to be of any real benefit to human users?
Whether or not we ought to say that this has already been achieved comes down to how we should interpret ``sufficient'' in this regard. Many researchers would say that it already has been done. But the interesting part here is just how successfully agents can combine different kinds of knowledge on a large scale. This is a large research field in itself, quite independently of whether one considers it an ``agent issue'' or not.
One focus of such research is that of Knowledge Representation. We'll not go into it in any great detail here. Suffice it to say that the currently most used knowledge representation method is that of symbolic representation. One typically writes statements as symbolic strings in a human-readable form, akin to natural language. For instance, the chemical rule that element X reacts with element Y to produce the element Z might be represented as ``(reaction-pair-produces X Y Z)''.
As a simple example, consider that one agent is given a large knowledge base of such chemical rules and data about some particular objects made up of some of these materials. The agent could then produce guidelines for the placement of different groups of these objects in a research lab, for instance. It is conceivable that the results produced by the agent is new knowledge, and that it only could arrive at them through reasoning along far more rules than a human could possible hold in his or hers short-time memory.
These are well-known AI techniques, and function nicely within small domains. The problem is to give agents common sense. Our agent in the example above should preferably know something about the common sense of placing things in a room, as well as merely knowing chemical rules. This way it should avoid suggesting solutions that would be impractical for common-sense reasons, solutions that you and I would instantly spot as bad ones.
So far, common-sense is one of the areas within AI that has failed to reach up to expectations. That such an obviously practical field has not yet bloomed is perhaps the reason that a lot of people are talking about an ``AI Winter''. It would seem that many feel the lack in this area very strongly, and are waiting for some sort of breakthrough [Rie94].
One project that is trying to improve this situation is the CyC project [GL93], which basically consists of compiling a large number of common-sense rules into one big reasoning knowledge base. It is an immense task, for to be able to make decisions as a human would, an artificial reasoner would need to know a great deal of details about the practicalities of human life.
This should make it evident why a focus on agents is needed. To be able to put the knowledge in such large knowledge bases into use, it needs to be communicated to lesser systems and applications. It also needs to be reasoned about. As an agent's knowledge store increases, it should be able to use what it has already got to verify what it receives. And if it lacks some crucial information, it ought to be able to ask for it and get it from other agents. This clearly indicates that the subjects of common-sense reasoning, shared knowledge and agents are closely linked, if not by essence, then at least by the necessity of finding practical solutions.
All we have said here gives us a foundation for defining the term of ``intelligent agent''.
As for the term intelligence itself, we naturally do not propose to exhaustively explain or define it. It represents a big research issue in itself, which is not the focus of this thesis. Although there is much controversy around it, at least it is possible to utilize the common concept of intelligence which is used in everyday language. We claim that for a program to be called an intelligent agent, it should display a kind of behavior that could, reasonably, be called intelligent regardless of where it was found, according to the conventional meaning of the term. This ought at least to rid us of the ``problems'' from all the hype around various information filter programs that are being marketed as ``intelligent agents'' with little other reason behind such a name than a wish for publicity.
We also find it natural to associate intelligent agents with the Knowledge Level, which is a concept central to our understanding of the elements involved.
Last but not least, one has to be aware of that ``intelligent agent'' is, after all, a term that is increasingly often used in AI. This means we cannot just put down a normative definition and expect it to make sense for all existing intelligent agents. Not to mention that other researchers may have very different opinions about the term.
Keeping in mind these various difficulties with regards to a definition for this thesis, we select as the best alternative this fairly simple, straightforward descriptive definition:
An intelligent agent is a computer program describable on the Knowledge Level which has a behavior that can reasonably be called intelligent, including the ability to communicate intelligently.
On the other hand, such a descriptive definition as the above is too general for our specific purposes. As we stated in chapter 1 we are particularly interested in the communication of knowledge by intelligent agents. We need a more specific definition to describe what we have in mind.
But what exactly is that? What does ``communication of knowledge'' really mean? Communication takes place by agents sending data to each other. But how does the data become information for an agent, and how does the information turn into knowledge?
In the context of an agent (as a computational system) in a decision-making process, the terms of data, information and knowledge may be defined like this [AN95]:
In this view, knowledge has the following three roles:
In light of this we choose to understand the ``communication of knowledge'' as the process by which one agent formulates its knowledge into information and sends it as data to another agent, which on its part interprets this data into information and learns it, that is, integrates it into its own knowledge. (This is knowledge where the agent itself is the frame of reference, ie. is the entity that ``knows''.) Thus the input can be seen as both data, information and knowledge for the sending and the receiving agent.
On this basis we choose to concentrate on the type of agent described by the following normative definition:
A knowledge agent is a type of intelligent agent that deals in knowledge, in the way of keeping, querying, distributing it or communicating it, whether as a primary or secondary function.
That agents should have knowledge does of course not mean that each agent should know everything. In the world of agents there will be experts on various fields, just as there are human experts. When an agent A working in field F discovers that it lacks a certain piece of knowledge, it should make an inquiry to some other agent X that is an expert in field F. Agent X should then pass the requested piece of knowledge back to agent A. Possibly, agent X could be an knowledge broker agent, which redirects the query to those agents it knows to be the real experts.
At any rate, both agent A and X fall in under our definition of knowledge agent, even if agent A only needs the knowledge in order to perform some external, non-theoretical task. If it can utilize knowledge qua knowledge, then it is a knowledge agent.
Agent X is the more interesting, though. Knowledge agents acting as
knowledge bases or knowledge servers for other
agents is a promising research direction. The idea behind such
Shared Reusable Knowledge Bases
(SRKBs) is to store knowledge in such a way that agents of different
types can utilize it. This is no small task, as there are significant
problems with translating knowledge from one type of representation to
another. In fact, the current status of this research is to
concentrate on specific knowledge representation languages and try to
build SRKBs for use by agents all speaking the same language but
possibly occupied with dissimilar types of tasks. That is, one
haven't reached the point where the translation from any one
knowledge format to another is possible. And maybe one never will.
Some researchers is of the opinion that disparate kinds of knowledge
cannot be reduced to a common representation.
But nevertheless -- if one can establish SRKBs that are usable by a multitude of agents, it is easy to envision knowledge agents in any task or field being able to significantly improve their performance, due to taking advantage of knowledge servers. One can imagine, for instance, a group of user-specific (learning) information filter agents collaborating by letting a powerful reasoning agent draw conclusions for them about the general behavior of humans in valuing information.
In order to reach this stage the first thing one needs to do is to develop the technology to allow agents to exchange knowledge with each other.
What is needed, then, is to build an agent that can ``speak'' about language, in the sense of communicating in some knowledge representation format. Or in other words, to make something that we from the Knowledge Level would view as an intelligent, knowledgeable, and communicating entity.
This is a tall order, naturally. To get to this point one has to construct a program that on one level is an ``ordinary'' networking program, and on another level a knowledge agent. One must be able to make the abstraction from one level to the other.
Abstractions are well-known in Computer Science. When we program in any modern programming language, we perform abstractions all the time. In a sense all programming languages are abstractions. A programmer does not (anymore) write instructions about what the CPU should do in terms of moving data in and out of registers, but writes about variables, abstract data types, objects, abstract classes of objects and generic functions, et cetera.
So one should not concern oneself about how to turn 1's and 0's into knowledge. As we noted earlier, this is simply interpretation and learning, and is no more mysterious than that the ink in books may ``contain'' knowledge. What one should work on is simply the creation of formats or ``languages'' for representing and exchanging knowledge, and the creation of software for agents to operate with these formats in the way one intends.
Such formats and agents do in fact already exist.
As for the former, there are already dozens of knowledge representation formats available. Examples are KIF[GFea92], LOOM[MB87], etc. The problem here is not finding one, but rather deciding on the best one. (This is not an issue in this thesis.)
There also exists a language for communicating knowledge, rather than merely representing it. This language is called KQML. We will get back to KQML in greater detail later. For now, suffice it to say that it can handle any kind of knowledge representation format, by packaging represented knowledge in a ``content'' field as part of the complete message one KQML agent sends to another. This leaves us free to use any representation available we need at any time, and means that we can in this thesis concentrate on the mechanisms of the exchange itself.
Presently we will look into the elements of programming needed for this kind of agent technology, in a bottom-up approach. Starting with the basics of network programming needed to enable agents to communicate with each other, we will explain how programs operate on the network to send and receive data. This is naturally also central to the implementation of the ``lower'' levels of KQML. And when this foundation is laid will we turn to the higher levels of KQML, ie. its handling of knowledge-level messages.
This chapter will present a self-constructed example program showing how Unix system programming can be used to establish the kind of low-level network communication which are needed for a group of agents. Instead of only thinking in AI terms, we will also use conventional programming terms and techniques in looking at the issue of setting up some agents on the net.
This is so to speak a first step in order to get to the point of having true networking knowledge agents. And in order to make this step, let us first cover the basics.
The concept of communication is central to our view of agents. Traditional computer programs communicate with their user via the screen and keyboard, but when we envision a set of agents communicating with each other it would be far from ideal to confine them all to one and the same computer, sending messages to each other only within the memory of that computer.
With the advent of large computer networks such as the Internet it is quite obvious where the road from here on must go. We must give our agents the ability to talk with each other over the net.
This leads to the requirement of giving our agents basic Internet communication capabilities, so they can reside on different machines, conceivably all over the world, while exchanging information and knowledge with each other.
Let us concentrate on the issue of Internet communication software. The basic situation where it is needed is as follows: We have two programs, each on a separate Internet-connected machine. One of these programs contacts the other by sending it a message. The one making the initial contact is called the client, the other the server.
Computers providing servers need to have the software to be listening for arriving messages, as well as delivering them to the appropriate server program when they arrive. This needs to be fast and therefore preferably independent of any other activities the machine needs to perform. Therefore it is best that it runs a multitasking operative system, which can manage several processes of execution which are more or less independent of each other.
Unix is such an operative system, or rather a family of such operative systems. Unix uses a type of multitasking called pre-emptive, which means that the core of the OS (the kernel) has control over when a process gets to use the CPU and for how long, as opposed to letting the process itself decide when to release control. This makes Unix a fairly good OS to run servers on, since we are under normal circumstances guaranteed that the software listening for connections will be able to perform its duties with regular intervals. (With current technology these intervals last only micro-seconds, which means that a connection is handled virtually the instant it is established.)
To simplify things, in the remainder of this thesis we will assume that, if not noted otherwise, any server computer runs Unix. Also, most if not all of our examples of clients can be construed as Unix-based. Our self-constructed example programs in appendices A and B have both been programmed using Unix software and networking capabilities.
Sockets [Pre92] represent one of the ways Unix programs use to communicate with each other, and is in fact the most common way of implementing such a network-communication program in Unix. Basically, a socket can be described as an endpoint of communication.
In order for two socket-using programs to communicate, they both have to establish their own specific socket. The server program listens on its socket, awaiting a connection, thus establishing a service defined by what action it takes on receiving a connection. (For instance, a web server program establishes the service of delivering web documents etc. on request.)
The address of the server's socket must be well-known, for instance by having been advertised, so that the client somehow knows it. (This may come about in various ways, for instance by the address being a part of the code as written by the client programmer, or by the user giving the address to the client, etc.) The client program uses its own socket to connect to the server's. And what happens from there, in terms of what data is passed to and fro, is dependent on what kind of service the server provides and how the client requests it.
Sockets may be of different types and exist in various domains. The sockets we will be using in our examples are the common variety used by application programs, namely of the stream type, and existing in the Internet domain. This means we are guaranteed a reliable, sequenced and unduplicated flow of data, (ie. we need not concern ourselves with data error-checking,) and that the server we set up may be connected to by any machine on the Internet.
In Unix we have to our disposal various system calls to establish a socket, bind it to an (local) socket address, connect to another (remote) socket and so on. We will be using some of these system calls in our example programs.
For our example, we will put a Lisp interpreter on the net, as described in the following.
Lisp [Ste90a] is a programming language much used in AI. Given that we have available a Lisp program which implements some functionality that we may call intelligent, and also has the ability to communicate in one way or other, we may call this program an intelligent agent of sorts. For this we need not require that it is a ``knowledge agent'' as we define the term, nor that it communicates with any other ``agents'' than a user.
Let's assume that we have a need for getting our Lisp agent to communicate not only with the user, but also with another computer program. This other program is not necessarily an agent, in fact it may be just a interface to a user. But nevertheless -- this is the first step in giving our agent the possibility to communicate with a multiplicity of other agents.
All we need to do to get our Lisp program on the net, is to get a Lisp interpreter on the net.
This I have done in a simple fashion, namely by writing a program called setserver, in the C language [KR88]. (See Appendix A.) In short, setserver starts up another program, in this case a Lisp interpreter, in such a way that it can write to and read from it, and makes a socket available over the network with a service tailored to be connected to with the well-known telnet program. When a connection is made, setserver passes the data it gets from the connection on to the Lisp interpreter, and sends the data it gets in return back over the connection.
In addition, I implemented a simple client in the Perl language [WS91], called setserver-talk. Its purpose was to establish a connection to setserver, so that the Lisp interpreter could be easily used by other programs, like a World Wide Web interface. (See Appendix B.) This can be useful for several reasons, though its value in this thesis is as an example of a kind of client using the Lisp server, in addition to the standard telnet program.
For additional clarification, appendix A includes a short example session with a setserver process through the WWW interface. In this example we see that the Lisp interpreter being run by setserver returns an evaluated result from a simple Lisp expression query. (Which means there is no AI of any kind in the appendix.)
Though setserver is merely an example implementation of basic network programming techniques, and in no way sufficiently secure or error-free to be used in any kind of real applications, there has been some interest at our Department of Informatics here at NTNU in its ability to make a Lisp interpreter available over the net. One of the reasons I implemented it was in fact a need to get a specific Lisp program on the net, namely the CREEK system [Aam91]. CREEK is a knowledge-based Case-Based Reasoning system for decision support, complete with its own knowledge representation language called CreekL. CREEK is under implementation, but a large enough number of its modules have been implemented for working version to be able to run under both MacIntosh and Unix Common Lisp.
A Case-Based Reasoning system such as CREEK may be viewed as a reasoning knowledge base, as it contains both general and specific knowledge (cases) and the reasoning powers to match new problem instances with old cases and explain the match. It can be viewed as a knowledge base acting as a server. In this case this means that the exact status of the memory of one instance of the program at any time constitutes what it ``knows''. The setserver program may be used to set up any such individual CREEK servers, so that their knowledge is independent of the other servers' knowledge.
One major at our department, Jan Ståle Berg, has been looking into the use of setserver in running a CREEK server as a module in an Intelligent Tutoring system to be available through the World Wide Web. The Intelligent Tutoring system would of course be implemented in CREEK (and CreekL) itself, but my setserver and setserver-talk programs could be used for the interface between the World Wide Web and the Lisp interpreter running CREEK. These example programs of ours may not prove to be the most practical way of doing this, but at least it shows what such kinds of programs might do.
However, using setserver to get a program on the net doesn't mean that the result is a full-fledged intelligent agent. So far all we have done is to look into some basics of network communication, and as a part of this thesis, it qualifies as nothing more than a rather simple example of network programming. In section 5.5 we will briefly sketch how such a kind of program might be used in a KQML context, but only to give the reader a general idea of how our example program relates to the more AI-oriented parts of the thesis.
What we have not yet touched upon is the ability of agents to exchange knowledge with each other. Agents need to share some form of language in which to talk about and exchange their knowledge, and this will be the focus of the next chapter.
In order for agents to exchange knowledge with each other, they have to satisfy at least the following two requirements; 1) An correct internal representation of knowledge, and 2) A correct interpretation of knowledge received from external sources.
The first of these is the theme for an old research direction within AI, and there currently exists a lot of knowledge representation languages. Yet no standard of representation has emerged that allows translation between such languages without loss of information or danger of misrepresentation. If anything, the research has shown that different kinds of knowledge needs different kinds of representation, and that there is no guarantee that a general basis for knowledge representation or a secure translation method between them can be found.
This means the AI community cannot reasonably hope to have this problem solved within the foreseeable future, but has to cope with a host of different knowledge representation languages for a long time. This is no great obstacle for most of today's agent projects, of course. Within the boundaries of a particular project, the various agents naturally share a representation formalism. Interpretation is not a problem in their communication.
Still, there are indications that such schemes will not be enough for the future. As we've mentioned before, much research is being put into the subject of Shared Reusable Knowledge Bases (SRKBs). One would like to see large data bases of knowledge being usable for several purposes, or by several types of agents. Ideally, a Case-Based Reasoning agent, a logic agent and a text search agent, for instance, should be equally capable of making use of such a knowledge base, by sending queries to it in some standard format.
To do this, one needs to establish a basis for communication in a ``multi-lingual'' agent environment. Even though no translation filters may exist, at least our infrastructure must be able to handle communication in several knowledge formalisms.
In terms of actual research, the ARPA Knowledge Sharing Effort (KSE) is a consortium working to develop conventions in this area -- for the facilitation of sharing and reuse of knowledge bases and knowledge based systems [FFMM94]. The KSE is organized around four working groups:
From the last of these, the External Interfaces group, has come the KQML language.
Knowledge Query and Manipulation Language (KQML) is a language constructed to deal with the problems of exchanging knowledge between different types of agents and in different representation formats [Ini92] [FFMM94] [LF94] [Lab96]. Allowing for content messages of any formalism, it handles knowledge in the way of ``speaking about it''.
That is, it is directed at the manipulation of knowledge through speech acts. A speech act is a the kind of act one makes when one utters an expression, either by making a statement, asking a question, commanding someone to do something, expressing an intention, et cetera. One of the leading philosophers in this field, John Searle [Sea69], differs between the sentence content and its illocutionary force, a distinction that has also been adopted by KQML.
In order to visualize this concept, let's consider the fact of a person P lifting an object O. Such a sentence content that this fact represents can be expressed with different kinds of illocutionary force. For example:
``P lifts O.''
``Is P lifting O?''
``P, lift O!''
Consequently, the philosophy behind KQML is to differ between the message content and the kind of speech act the sender agent is performing with it. The whole of a KQML message represents a speech act; a so-called performative. Its top-level structure indicates the type of speech act, and its body is divided into fields that further characterize it. One of those is the content field, containing the message content in some knowledge representation format or other. Another field describes the sender, another the receiver, and so on. Since the content is ``packaged'' within the message in this manner one may easily distinguish between the content and the kind of speech act that is being performed with it.
This should be obvious from the following example of a typical KQML message. It is one of the most basic types, the tell performative, which is used when a sender wants to inform a receiver about a fact the sender believes to be true.
As for the syntax, it is a Lisp-style parenthesized list. This is due to that most, if not all, current implementations of KQML use such Lisp syntax. (Mostly for historical reasons -- but it has also shown to be a practical format for this task.) Also note that the knowledge representation language is named in the :language field, so that the receiving agent will know how to interpret the content field.
(tell :receiver CarAgent158
:sender GeographyAgent51
:language Lisp
:content (statistics-item
(traffic-density
(route 'e6)
(crossing 'trondheim)
(density ((entities 523)
(entity-type 'car)
(time-span 'minute)))
(type 'year-average)
(basis 1995)))
)
Here we see that the performative is ``tell'' and that the sender and receiver are given in the first two fields. The content message is a Lisp structure describing an item of statistical knowledge which a car agent may use to aid a navigation process through an unfamiliar area.
But the language of KQML is not concerned with the content as such.
We can only assume that the sender and receiver agents can understand
it. But it can be written in any kind of language or
format, and it is not of interest to any pure KQML agents
handling the message, in forwarding tasks and the like. The only
thing a message-handling KQML agent needs to know about the content
message is where it starts and ends, so that it can correctly read the
message as a whole.
This separation between the communicating agents (sender and receiver) and the KQML message handling agents will be looked into later. Currently we will deal with further details of the language.
First of all, be aware of that the set of KQML performatives is not a closed set. In designing the performatives so far the KQML designers have been trying to respond to a need for communication capabilities. This means that many of the existing performatives are related directly to the practical task of agent communication. The fact that communication technology as well as the science of intelligent agents is constantly developing means that no list of performatives should be seen as absolute. However, the one we intend to present here is taken from the latest specification of the language [Lab96], and thus is the nearest we can currently get to a absolutely correct account.
It's natural that our presentation start out from the tell example above. Evidently, that and all other kind of messages that pass back and forth between agents are part of conversations, of which the simplest kind is one query and one reply. Therefore it is not sufficient to view one message in and for itself. It has to be interpreted in the light of the ongoing conversation. If there is no conversation beforehand, the message has the role of initiating one. So, both pragmatics as well as semantics play an important role here.
In the traditional client-server model, a session consists of the simplest possible kind of ``conversation'', where the client queries the server and in return receives some kind of feedback. In most agent conversations, however, various practical considerations may necessitate that both parties be able to initiate connections. One of those considerations is that the calculations being done by one agent in some cases may be so time-consuming that it is practical to close the current connection and wait until the agent has completed its task, whereupon it should initiate a new connection to the agent that asked for the calculation results in the first place, and feed it the results.
Such results may by their very size suggest sending it in parts, with time-delays interposed, so that the receiver has time to process the information. Or, the querying agent might need results as quickly as possible, and some parts might therefore be produced and sent more swiftly than others. Consequently, KQML agents needs to be able to handle asynchronous as well as synchronous communication
Another consideration is that the answering agent may need to query other agents to collect all the information it needs, and thus needs the capability to initiate connections itself, as well as receiving them. In short, there are many reasons intelligent networking agents should have both client and server capabilities, and this is why this approach has been adopted by the KQML designers.
Discourse performatives
Intervention and Mechanics of conversation performatives
Facilitation and Networking performatives
Note that we use the agents S and R as sender and receiver, respectively, in the following explanations. The use of S(ender) and R(eceiver) is local to each explanation.
Our first example, tell, is one of the discourse performatives, which contains all performatives that can reasonably be seen as regular speech acts. This group contains at least the following:
S informs R that S believes the content to be true.
S informs R that S does not believe the content to be true.
S informs R that S believes the content to be false.
(Note that this is stronger than the untell performative above, which only says that it is not the case that S believes the content to be true. With the deny performative, however, S states explicitly that it believes the content to be the opposite of true, ie. false.)
S asks R to declare its belief about the truth status of the content.
S asks R to reply with all of the responses that would make the content true.
(In this case, R would return a collection of responses bundled together.)
S asks R to reply with one response that would make the content true.
As ask-all, but the responses are to be delivered one by one as an asynchronous stream of tells, with an eos control message to terminate the stream.
S informs R that the stream (of responses to a stream-all) currently being sent from S to R is at an end.
S asks R to insert the content into its knowledge-base.
S asks R to reverse the act of a previous insert.
S wants R to remove one response (representing an answer to the content query) from its knowledge-base.
S wants R to remove all responses (matching an answer to the content query) from its knowledge-base.
S wants R to reverse the act of a previous delete.
S wants R to make something true of its physical environment.
S wants R to reverse the act of a previous achieve.
All the performatives up until now have been based on a simple point-to-point protocol, namely that of the sender S communicating directly with the receiver R. But how does the actual connecting take place? And how does the sender know which agent to contact?
In the current implementations of KQML, this is solved by two special-purpose programs, the router and the facilitator, respectively.
Every router is an identical copy of the same program, each associated with one particular KQML agent. The agent's router takes care of the sending and receiving of messages, in both an synchronous and asynchronous fashion. Thus the router provides the agent with a single interface to the rest of the network. To send a message to another particular agent, all our agent has to do is to give the router the address of the receiver. The router handles the rest.
By wrapping all the mundane tasks of networking into the router in this way, we free the agent itself to work on its primary task, namely that of utilizing the information and knowledge it receives from other agents.
The facilitator has a more interesting function. Whenever our agent does not know exactly which other agent to query about a certain piece of information, the facilitator may help to establish contact with a suitable agent. This may happen in various ways. Basically, the facilitator has some sort of access to information about various agents, their network addresses and fields of expertise, and picks among them the best candidate. It is itself a network agent of sorts, that is, it is resident on the agent's local network, where it lies on a socket and listens for connections from local agents. When it gets a request, it tries to provide some sort of matchmaking between the querying agent and a suitable (expert) agent to answer the query.
There are many practical considerations here. One is whether the facilitator should keep a database (cache) of information it has received from expert agents. If it does, it may provide instant answers to certain queries, but this is perhaps only a wise tactic if the relevant information is very static by nature. Another consideration is, should the facilitator tell the various agents about each others' addresses, or should it route all messages through itself?
Because it is important that the agent that makes the initial query has a lot of control over such matters, the various tactics available to a facilitator are associated with performatives the agents can use. Thus, in choosing a performative by which to query a facilitator, our agent has a great deal of control over the practical process of locating and receiving the information.
The advertise performative is used when an information-providing agent S announces to another agent R or to a facilitator F that S is willing to answer queries about some subject. For example, advertise with content (ask-if(X)) tells the receiver that S will answer queries regarding ask-if(X).
When S has registered with the receiver like this, the receiver may benefit from S's services itself, or if it is a facilitator, may inform other agents about S's services. See the broker-, recruit- or recommend- performatives for possible ways of achieving this.
With this performative, the agent S asks another agent R or a facilitator F to keep S informed about any changes in its available knowledge relating to a specific query. For example, subscribe with content (ask-if(X)) tells the receiver to give S the answer to the question X, not only once, but every time this answer changes. In other words, S ``subscribes'' to news about X.
S informs R that R's (previous) message to S was not processed by S.
S informs R that R's (previous) message was processed by S, but that it could not provide a more informative response.
This performative has a stream-all KQML message as the content. With this the sender S tells the receiver R to hold the stream of answers and release them one by one when S sends a next performative. This way S is in control of the data stream. The exchange will continue until S sends either a discard or a rest message, or until R announces the end of the stream with an eos message.
This performative is an acknowledgment from S to R after R has sent S a standby message. With it, S announces that it is ready with the stream of answers and waiting for next messages to release them.
S tells R to take the next answer in the stream and send it to S.
S tells R to send all the remaining answers in the stream to S in one bundle.
S tells R to discard all the remaining answers in the stream, and to stop processing next messages with regards to this stream.
In the above we have silently assumed that the agents S and R (or their routers, rather) naturally knows how to find their local facilitator. But how does this happen in practice? In the KQML API which we will be looking at later, agents register with their local facilitator at startup, and unregister at shutdown. Such actions are not relevant to the intra-agent communication, but relate merely to the practicalities of networking. They are no less important for that.
It is quite conceivable that an agent must have control over its networking at some point, for instance if it is too overworked to handle incoming connections, or is obliged to shutdown for some reason. To keep consistency, it is natural to let the agent enact such operations through a set of networking performatives.
The agent S tells F that it is now available on the net. F can proceed to route messages to it, or to give other agents its address.
This performative reverses the effect of a register operation.
S wants R to forward a message to the agent named in the :to field. (R may be a facilitator, or the intended addressee agent.)
S wants R to send a the content performative to all agents that R knows of.
S associates its symbolic name with a new transport address.
Instead of letting F keep the information in its own knowledge-base, S may use the broker-one performative to ask it to locate an agent which can process the query, whereupon F should receive the result and forward it back to S.
For example, broker-one with content (ask-if(X)) tells F to locate a suitable agent (R) to ask about X. When R has been found, it is sent the ask query, and finally F tells S about R's answer.
Like broker-one, but S wants F to respond with all responses to the content query.
This performative is used instead of recruit when the agent S wants the address of R, so that S can initiate a conversation with R on its own. With recommend-one with content (ask-if(X)), S asks F to find a suitable R and reply with R's address. After that, S sends the ask-if(X) performative directly to R. The advantage of this tactic is that it minimizes the amount of traffic passing through F.
On the downside, we may not want to let S know about any specific expert agents, because this undermines the intention of the facilitator architecture. Facilitators provide an interface for locating agents and routing information. This is a service that could (or should) include deleting old information regularly, so that querying agents won't be directed to ``expert'' agents with out-of-date knowledge.
So, if S stores an expert agent's address, it must be S's responsibility to delete this address when it no longer can verify that the expert agent's knowledge is up-to-date. Although current KQML implementations do not include such verification, we suggest that it could be made a part of the facilitator services sometime in the future.
Like recommend-one, but S wants to learn of all agents that may respond to the content query.
This is a variation of the tactics used with the broker performative. With recruit, the agent S tells F to forward the query to an agent R in such a way that R replies directly to S. This is practical if the size of the answer message will be so large that handling it would heavily task F's resources.
Like recruit-one, but S wants to get answers from all agents that can respond to the content query.
The KQML API (or KAPI) is one of the current implementations of KQML. It is not flawless, but we include it here as an example demonstrating how the language may be implemented and how the basics of KQML networking and communication may be handled.
We downloaded the KAPI version 2.6e Beta, Copyright 1994, 1995 by Enterprise Integration Technologies, Corporation and Lockheed Missiles and Space Company, Inc. (Although not strictly necessary, we have included the license in Appendix D.)
The basic setup in this rather simple version of KQML is that when an agent starts up, its router module announces itself to the local facilitator, which is also called an Agent Name Server (ANS). When the agent exits it announces this as well. Both are enacted with the help of the register and unregister performatives, which we explained in the previous section.
The kind of facilitator/ANS this version supports is that of a regular HTTP server (WWW server). The source code includes two CGI-BIN scripts, kapi_register and kapi_unregister. (CGI stands for Common Gateway Interface and is a protocol used by web servers to communicate with applications that it launches when receiving certain queries, in this case register and unregister queries.) These two scripts maintain the registration of agents in files with their symbolic names and TCP address in URL form. For example, ``HeleneAgent tcp://helene:3123'' represents an agent called HeleneAgent residing on TCP port 3123 on the local machine helene. Other protocols than TCP may be used with the KQML API, among them email and MBus, but TCP is the most basic, and was thus the most easy for us to test.
We set up two of the test agents supplied with the source code, and named them HeleneAgent and NikeAgent, running on the machines helene and nike, respectively. On startup they automatically registered themselves with the ANS, which was running on another machine entirely. After that, the user was free to make one of the two agents (the one set up to act as ``client'') send any number of KQML-compliant messages to the other (set up to act as ``server''), using only their symbolic names and the URL to the ANS. The ``server'' then replied to each message with a message_received acknowledgment performative. (This is just a convenient solution intended for testing purposes, of course, as was the roles of ``client'' and ``server''.)
The details of the above methods of registration and communication is not important. Moreover, it is a very preliminary arrangement. This kind of ANS is for example by no means a complete facilitator according to KQML specifications.
By convention, KQML facilitators should in fact be running on a host machine with the symbolic name (or alias) of facilitator.local.domain and be listening on a standard KQML port. For example, in the IP domain of our department, ifi.ntnu.no, the facilitator should be running on a host aliased to facilitator.ifi.ntnu.no. Also, one particular TCP (socket) port number should be reserved for KQML agents, the same way the number 23 is reserved for the telnet server and 80 is reserved for HTTP servers, namely by the convention of an Internet standard, so that all KQML agents would know how to find and connect to their local facilitators. (Such a standard has to our knowledge not yet been adopted.)
It is also a clear goal for KQML research and development that facilitators should be full KQML-speaking agents. And the ANS of the 2.6e KAPI version provides no other performatives than the register and unregister performatives, as well as some more simpler services of agent name lookup etc. Technically it could provide more performatives, by adding more CGI-BIN scripts to the ANS HTTP server, but rather than using such make-shift solutions the ANS ought to be implemented as a separate program.
Nevertheless, despite its obvious shortcomings this KQML version has managed to get the basic networking framework in place. Having programmed our example program in Appendix A we are fully aware of the complexity of this task alone. And not only has the 2.6e version the capabilities to let agents find each other easily through an ANS, it also aids programmers turn their programs into KQML-speaking agents.
That is, the KAPI 2.6e version takes the form of a set of library of functions in various languages for KQML message sending, receiving, parsing, etc. The languages of libraries include C, Lisp, Tcl and Tk, as well as C for Windows NT. This means that KQML agents can easily be written in any of those languages. The most practical of these is probably the Lisp interface. As an AI language it is the natural choice in which to write intelligent agents of any type, including KQML agents. And with packages such as the KAPI, this task can be performed without having to go through the drudgery of implementing the KQML language and networking capabilities from scratch.
While we're on the subject of implementations, a brief glance back at our own example program seems appropriate.
The reader may have wondered about how the setserver program relates to the rest of the thesis in terms of its practical use. As we stated earlier, the program is presented mainly in order to demonstrate the technical programming issues involved here. What it lacks is a knowledge agent level. However, this may be remedied with the following strategy.
Since setserver is intended as a way of getting a Lisp interpreter on the net, any and all intelligent functionality exhibited by a running version of the program must be implemented in Lisp. The setserver code contributes with the networking communication needed to get the resulting intelligent agent in contact with other agents.
Now, consider the case where the Lisp program is an implementation of the KQML language, complete with an internal ``knowledge base'' where facts may be entered and retracted. The agent could be implemented with a subset of KQML ``functionality'', in that, for example, it could act as a ``knowledge server'', and take the role of an expert agent in a particular field, replying to relevant queries on request.
In its present form, our program lacks the functionality of a router module and is therefore ill equipped to initiate connections with other agents by itself. But serving as an expert resource for another KQML agent or facilitator is a perfectly possible, and practical, realization of its potential.
Even though the Lisp program would only have to read KQML messages from its standard input data channel and write KQML responses to its standard output data channel (stdin and stdout in Unix terminology), the setserver program code would ensure that this would in fact result in communication with the network agent that contacted the program.
What we have shown so far is not so much how to use agents in real AI systems. We'll try to correct this right away, by looking at possible improvements this technology might offer the field of Case-Based Reasoning.
One may suspect that the main applicability of the methods we have been talking about so far is in the enabling of communication between already existing reasoning agents (or systems); not so much in guiding the reasoning within those systems. Or is this an improperly balanced viewpoint? The question we must ask ourselves is: May intelligent agent technology aid the very problem solving of intelligent systems, (in this case CBR systems) and if so, how?
There is an important distinction here between the concepts of Distributed Processing and Distributed Problem Solving [PP96].
Distributed processing is characterized by a complete independence of subproblems, where each agent needs nothing other than its own local knowledge and methods in order to arrive at a solution to the subproblem. In such a multi-agent scheme, tasks are split into separate subtasks and delegated to the various expert agents in the system, whereupon the final results may be assembled into one answer.
In contrast, there is the notion of Distributed Problem Solving. It is characterized by the existence of interdependencies between the subproblems assigned to the individual agents, so that cooperation is necessary in order to solve the problem.
There is not much new with distributed processing, as opposed to the traditional processing of computational systems. Each agent solves its subproblem independently of the rest of the system. One may compare this with a group of traditional programs each working on one task, with the added feature of ``distribution'' of the system only in terms of the communication of results to a central result-collector. This is not very interesting in terms of the potential of agent technology.
To rephrase our question in accordance with the concepts of distributed processing and distributed problem solving, we ask: Can distributed problem solving improve the performance of AI systems?
We will attempt to investigate this on a theoretical level, by looking at the potential inherent in the distributed problem solving scheme. Since this scheme represents a certain way of exploiting agent technology, any conclusions we may reach about its potential will be valid for intelligent agents and hence for ``knowledge agents'' in the way we have defined them, including the more specific KQML agents.
In this endeavor we will be using Case-Based Reasoning as our example AI field. As we shall see, the utilization of agent technology in CBR is quite promising in terms of improving performance.
Although we have touched upon the subject of CBR previously (in chapter 4, for example), an introduction to the field is in order. For obvious reasons we will limit ourselves to the basics, plus those issues that are of special interest to our focus.
In section 3.3 we briefly sketched an example agent in the domain of chemistry which reasoned with the help of general rules. The use of such general rules is representative of a great deal of AI, expert systems in particular.
An expert system is a rule-based program that provides ``expert'' solutions to problems in a specific domain. But it differs from a human expert in two major respects [LS93, p.308-309,]. Firstly, it does not learn from experience. Its knowledge must be ``translated'' from the elaborations of the real experts into a set of rules on which the system can operate. (This translation process has been called the ``Knowledge Acquisition Bottleneck''.) Secondly, its reasoning does not model human reasoning, but uses heuristic strategies to navigate in a space of rules. Accordingly there is a lack of flexibility and robustness. (The only way to make a rule-based system more flexible is to make it learn more rules, and more often than not, the only way to make it learn is to manually update its rule-base.)
Obviously, both of these facts make expert systems in their present form less than ideal for common-sense reasoning.
Machine learning [SL92] is the subfield of AI that studies the automated acquisition of domain-specific knowledge. One of its aims is to alleviate the shortcomings of expert systems.
There are several paradigms for Machine Learning, one of which is the case-based approach [SL92, p.797-800,]. The core of this approach is the storing of individual problem-solving cases and using lazy generalization to classify and solve new problem cases.
This means that, rather than ``aggressively'' generalizing experience in anticipation of future use, case-based methods typically save a great amount of their specific experience, so as to draw directly upon it as a resource when solving new problems. This may span from saving all problem-cases to postponing the merging of cases into more generalized ones until a specific need for such an abstraction arises.
The generalization itself takes place as a natural part of the problem solving process, in the matching of the new case against old ones. When a matching old case has been selected, the solution in the old case is reused with regards to the new problem case. This solution in a sense represents the categorization of the problem case, in that it is generalized to account for the the new case as well.
In contrast to expert systems, this approach has a greater resemblance to human reasoning, as there is mounting evidence that human experts at least partly rely on their memory of individual cases. (E.g. common patterns of pawns remembered by chess experts [And90].)
In addition it incorporates learning, in that the accumulated experience of a CBR system improves its performance over time. If a new case matches an old one perfectly, the new one may be deleted, otherwise it will probably be stored as a unique case. Some CBR approaches also aid the learning process with use of general knowledge about the domain. (We will look at various CBR approaches shortly.)
In terms of the concepts of data, information and knowledge (section 3.5), cases may have the roles of all three of these [AN95]. (The cases are of course input data to the system, but may also have other roles.)
The CBR methods of lazy generalization and learning differs from that which is called ``generalization-based'' learning. The latter involves generalizing new information continuously as it is presented to the system, and incorporating the results into a knowledge-base. There are no problems with such an approach in domains with ``strong'' domain theories, ie. where most if not all inferences from the new information can be drawn directly from its readily apparent (superficial) features. But in domains where this is not the case, ie. in so-called weak theory domains, one can only perform such generalizations at the danger of loss of information. Consequently, learning in weak theory domains is better served with methods that do not generalize at once [PBH90]. -- Like lazy generalization, for instance. Also, one should be aware of that weak-theory domains are in fact more common than domains where the corresponding theories are both strong and tractable. (``Tractable'' meaning that the calculations of the theory in practical cases are executable within reasonable amounts of time.)
CBR is therefore a promising method of reasoning for weak-theory domains like medical diagnosis, geological interpretation, investment planning, law and engineering, et cetera. It has been employed in large-scale practical applications with respect to optimization of autoclave loading in airplane parts construction [HH92] and selection of mechanical equipment in ship construction [BL91]. Significant improvements in efficiency have been made in both of these applications.
The main issues that a CBR system has to deal with relates to the following [SL92]:
The various approaches by which to deal with these issues can be subdivided into the following main categories. (Although there are some overlaps, at least in that there are systems that embody aspects from several categories.)
Exemplar-based methods concentrate on the learning of concept
definitions, where a ``concept'' is defined
extensionally, ie. as the set of its
exemplars.
In this approach, the solving of a new case is seen as a classification task, in that the class of the most similar past case becomes the class of the new case.
Early papers by Kibler and Aha [KA87], and Porter and Bareiss (the PROTOS system) [PB86] are representative of this approach.
This is a specialization of the exemplar-based view into a highly syntactic approach. Instead of using general knowledge it relies on a large number of instances to match the new case, and in this way obtains a classification. This approach enables an increased focus on automated learning, and unlike some systems (PROTOS for example) does not need a user in the reasoning loop. More recent work by Kibler and Aha and colleagues [KAA91] are representative of this paradigm.
This approach views the set of cases as a large memory, and reasoning as a process of accessing and searching in this memory. Parallel processing techniques are being used in order to attain a high level of efficiency in the case matching process.
The MBR-Talk system [SW88] is one of the memory-based reasoning systems. In addition to the above mentioned characteristics, it uses purely syntactical matching criteria.
There is also a lot of work being done in Japan in this area (on ``massive parallel memories'' [Kit93]), but this also focuses on the integration of general domain knowledge with the methods described.
The term of ``case-based reasoning'' is also used in a narrower sense, to describe what we may call the ``typical'' CBR approaches. These are characterized by having quite large and complex cases, rich on information, and also use general domain knowledge in their reasoning processes. Partly due to this, such methods are able to modify a retrieved (solution) case within a specific problem-solving context.
This is the CBR approach we will be focusing on in the rest of this thesis. Its utilization of general knowledge on processes dealing in specific knowledge is particularly interesting for our focus on knowledge communication.
Whereas the typical case-based reasoning methods may be viewed as the use of intra-domain analogies (ie.- analogies within the current domain of knowledge), so-called ``analogy-based'' reasoning methods focus on solving new problems with the help of cases from different domains. This approach is therefore concerned with mechanisms for identification and utilization of cross-domain analogies [Hal89] [KC88].
This ends our account of the various CBR approaches. From this point on, when we talk about CBR we will mainly be referring to the ``typical'' case-based reasoning methods, though some of what we have to say may to some degree apply to the other approaches as well.
Aamodt and Plaza [AP94] stress the importance of integrating the use of specific knowledge (cases) with other and more general kinds of knowledge. The tasks of case retrieval, case matching and learning etc. may all benefit from drawing upon the resources of general domain-dependent knowledge. [AP94] describes a framework of CBR where the various issues of CBR we mentioned above are expanded into four processes.
This framework consists of two views on these processes:
The process model views the four processes as ``stages'' in a general CBR cycle, the RETRIEVE - REUSE - REVISE - RETAIN cycle:
The task-method view, on the other hand, is better suited to describing the details of the mechanisms involved in the reasoning process. It divides each of the top-level tasks into subtasks and methods of performing these subtasks. We will not go into those details here.
In [Aam95] Aamodt goes on to further describe this framework and its realization in the CREEK[Aam91] system. At the top level CREEK contains four modules, each representing a sub-model of knowledge. They are
The object level knowledge model is that of a single, unified semantic network consisting of concepts and associations as well as all the cases in the ``case-base''. These elements are all linked ``tightly'' together, in that all the knowledge is represented as frames in the same knowledge representation language (CreekL), and all the concepts used to characterize the attributes of specific cases have their definition in this knowledge model by way of semantic associations with other concepts. This enables CREEK to reason about all the characteristics of a case and thus to utilize general domain knowledge in every parts of the CBR cycle.
More specifically, each stage of the cycle is in fact executed by specializations of an ``explanation engine'' which itself is a cycle; the ACTIVATE-EXPLAIN-FOCUS cycle.
Typically, general knowledge is used in the activation step, in order to determine the context of knowledge in which to solve the current problem. Cases are used for the step of generating hypotheses, and a limited number of cases together with general knowledge are used in the focusing step. This tactic distinguishes CREEK from other CBR systems in that it represents an extensive and powerful explanation-driven way of utilizing general domain knowledge in the CBR tasks.
In addition, the general domain knowledge may be used for an extra problem-solving mechanism, if the case-based method fails to generate a satisfying solution. In such a situation the general knowledge is used to generate a solution from deep, semantical relationships or rules in the object level model.
By way of its extensive use of general knowledge, CREEK is particularly interesting to our agent-based focus.
The system represents an approach to integrated problem solving and learning. This is very suitable for an agent-based view, in that an intelligent agent should preferably be learning as a side-effect of its problem solving. This is directly related to the concept of autonomous behavior.
The notion of a tightly linked object level model may be transferred to a set of agents collaborating by communicating their knowledge in a common representation format. An attribute (feature descriptor) in a CREEK case refers semantically to the abstract concept of this attribute, while the concept is itself described by associative references to other concepts. Such a set of references within a tightly linked body of knowledge may be realized in an agent-based context only if we may distribute the knowledge over a set of agents with the references still intact. And in a KQML-based setup, such references may be encoded as implicit ``pointers'' to knowledge servers specializing in the various sub-domains of the relevant general knowledge.
This is one way of realizing a distributed processing scheme in a CREEK-like CBR system. But does taking such an agent-based approach to these issues constitute a potential improvement in the general behavior of such intelligent systems? The answer to this question follows from whether or not distributed processing per se represents a performance improvement. -- Which we will be looking into shortly.
What we may preliminary conclude at this point is that the structure of the memory model of such a system as CREEK do enable us to split it up and distribute it over a set of agents. There are already some ``dividing lines'' in the body of knowledge, so to speak, not only between the cases, but also between the cases and the general knowledge. One may easily imagine types of specialized agents working with, and reasoning about, each of these kinds of knowledge, in such a way that the strengths of each type of agent help in making the system greater than the sum of its parts.
So the question is not, ``can it be done?'' but ``may it improve the reasoning?''
Plaza, Arcos and Martín start out with an outlook similar to our current one in the article ``Cooperation Modes among Case-Based Reasoning Agents'' [PAM96]. The framework they are looking into is called Federated Peer Learning, and aims to study cooperative problem solving among a set of homogeneous peer CBR agents that all learn from experience and are all able to solve the problems presented to them on their own, at least most of the time.
More specifically, the authors discuss the use of the Plural Noos representation language for CBR agents within such a framework. This language is an extension of Noos, which is tailored for integrating learning and problem solving, and has been used to build several CBR systems [AP96].
As the article's title indicates, Plural Noos supports two modes of cooperation among CBR agents; DistCBR (Distributed Case-Based Reasoning) and ColCBR (Collective Case-Based Reasoning).
In DistCBR, the originating agent delegates authority to the agents it queries in the sense that it allows them to choose their own methods for finding a solution to the problem. Whereas in ColCBR, the originating agent maintains control by supplying the reasoning agent with the method to be used. The latter method thus supports a kind of collective experience in the agent community which any one agent can utilize as a resource in its own methods of solution finding. (Even though those methods are performed by another agent.)
What's interesting here is that the real power of ColCBR relates to the basis of CBR itself, namely the aspect of lazy generalization. It is only due to the fact that each CBR agent has not generalized its experiences beforehand according to its own private methods that any other agent is enabled to utilize the full potential of the sum of stored cases -- namely by processing them in accordance with its own methods of reasoning.
Whereas with DistCBR, it may make sense for each agent to generalize its experiences beforehand, since it is given the authority of deciding the reasoning method to use, anyway. In this case, other agents would not have access to the agent's ``initial experiences''.
From the existence of cooperation modes like ColCBR, then, we infer the answer to our question from the start of this chapter. By allowing each agent access to the collective memory so that it can make its own kinds of generalizations from it, we clearly gain much from the intelligent agent technology in the way of reasoning capabilities. Obviously, a multitude of agents with possibly quite diverse reasoning methods and with access to the experiences of all agents is a lot stronger resource than a set of agents that can only employ their reasoning methods on their individual experiences.
The approach of the collective memory is not interchangeable with one monolithic system, either, precisely because each agent has its own methods of reasoning. It is very doubtful whether any one program, however powerful, could ever incorporate all possible methods of reasoning and all the possible interpretations and generalizations of initial data that a group of agents with different reasoning methods can. (Not to mention negative effects of bottlenecks, positive effects of having different implementations of similar programs, etc., which all conspire to make a group of reasoning agents more flexible and powerful than one monolithic system.)
In [PAM96] the authors mention KQML as an approach similar to their own, but state that since they themselves are concentrating on homogeneous peer agents, they had no need for KQML's more general features. This is evidently true, especially since their application of Plural Noos is kept within the bounds of a single domain (the task of protein purification).
On the other hand, we see no reason why a language similar to Plural Noos could not be used as a content language in KQML messages. (Plural Noos has been implemented with RPC, which is an implementation method that doubtfully will scale up to all the possible applications of KQML.) This would enable an implementation of the same kind of cooperation between CBR agents as in the Plaza et.al. article.
In [PP96], Prasad and Plaza describe an additional method of cooperation between case-based agents, the Negotiated Retrieval method for distributed problem solving.
Negotiated retrieval represents a way of making various specialist agents cooperate on forming a mutually acceptable overall case, by merging sub-cases supplied by each agent. Whenever there is a conflict or constraint coming into play from one or more agents, various tactics of conflict resolution is being used in order for the agents to reach consensus about the relevant feature of the case.
An example of a situation where such a tactic might be used is when the system as a whole is set to assemble a group of people with different backgrounds into a functional team. (Each agent specializing in one field knows how to pick the right person for one particular job, in addition to generating constraints in terms of who that person prefers to work with, for instance.) But in general, it would be useful in any situation where there were a set of specialist agents each capable of solving a certain subtask of the larger task, but where there nevertheless were interdependencies between the subtasks in terms of constraints.
Negotiated Retrieval is therefore also one method which may improve the reasoning of a CBR system, more specifically in its case retrieval face. It is a distributed problem solving scheme which distinguishes it clearly from simple distributed processing. Not only does it take advantage of the various expert abilities of the individual agents, but it also enables inter-agent cooperation in order to solve interdependencies between subtasks.
Looking back, we find that our preliminary conclusion about the ``dividing lines'' within the memory model of certain CBR systems do represent an advantage to the agent-based approach. It is mainly through the fact that the separate cases qua non-generalized knowledge are being stored in CBR case-bases that agent technology may manage to utilize their potential to an extent that may not be possible for any one program.
Specifically, it is through the segregation of memory into cases and the distinction between general and specific knowledge that agents can step in and improve the process. One aspect here is that the various agents may divide all the cases between themselves, (for instance according to the requirements of various subtasks, ref. Negotiated Retrieval,) another that knowledge server agents (experts in different fields) may supply the various general knowledge needed for the reasoning processes in each agent.
Our conclusion is, then, that CBR clearly stands to benefit from the utilization of agent technology.
In the preface we compared the thesis with a ladder, and at this point we are standing on the top, gazing back down.
In chapter 2, we explored our assumptions about the term of ``agent''. This was our main starting point, and it gave us an indication of which way to go as we investigated the existing uses of the term. We concluded that the vocabulary is not clearly defined, and that people sometimes use the term to refer to what is in fact less than intelligent programs.
Chapter 3 discussed the aspect of intelligence in agents. We defined the terms of intelligent agent and knowledge agent in order to get at the specific kind of agent we were aiming for. Through an understanding of the differences between data, information and knowledge, together with a Knowledge Level view, the latter of these definitions became meaningful enough to meet our goal, namely that of a program able to communicate knowledge in an intelligent manner.
In Chapter 4 we looked into the technical side of such a program, that is, the networking code which is necessary to establish communication among programs in the biggest forum of the world, the Internet. This is the level at the ``bottom'' of the abstraction which represents the knowledge agent.
Chapter 5 looked at this abstraction from above. Specifically, we investigated the KQML language for knowledge communication among agents. We included a discussion on an existing KQML implementation (KAPI), and one discussion on how to make a KQML agent out of our example program from chapter 4, both of which demonstrated the reliance of the agent's knowledge level on the level(s) beneath.
In chapter 6 we introduced Case-Based Reasoning and discussed whether the field could benefit from the use of agent technology. Our conclusion was that it could, due to that the memory model of a typical CBR system can be distributed among a group of agents in a way that may improve the reasoning process as a whole.
Further work in this direction should include the implementation of a CBR system as a set of KQML agents, in such a way that it exploits the inherent possibilities in such a scheme. But there may be many ways of doing this, and future research should attempt to discover the advantages and disadvantages of various agent hierarchies, various configurations and various methods of distributing tasks and memories between agents.
The setserver.c program represents an example of how you can put another program (like a Lisp interpreter) on the net, thereby making it possible for it to act like an network agent in the sense that it is possible to connect to it and communicate with it over the net.
Below is a very simple example session with a setserver process running a Lisp interpreter. It shows a test being performed in Lisp syntax, in order to see that the interpreter returns the correct text. Note however, as is mentioned in section 5.5, that if the Lisp interpreter had been running a KQML-reading program, the process could in fact have been a proper knowledge agent.
As mentioned earlier in Appendix 
, a self-made
SGML document type called Litprog was used to actually write the
program. (The file defining Litprog is included in Appendix C.) From this a C program version and a Qwertz format
version was automatically produced. The latter of these I structured
for ease of reading, and it is included in its entirety below.
Although the details of the literate programming used here is of
little consequence to the subject matter of this thesis, I also
include a snippet of the program in Litprog and C versions for
illustrative purposes. Note that as the documentation is defined in
the Litprog version with logical tags like <func> and
<desc>, it is only visually emphasized in the presentation of
the Qwertz version, while in the C version it is enclosed within
proper C commenting.
Test of Lisp Interface
* Type in your name...........: CreekLWarrior_______
* Type in your email..........: ____________________
* Type in your password.......: ____________________
* Type in a lisp expression...: (list 6 2 6)________
Submit
It is the parenthesis ``(list 6 2 6)'' which is the Lisp expression that is being sent to the Lisp interpreter. The result from the interpreter's evaluation of that expression is presented in the response screen below:
Lisp Interface Input (list 6 2 6) Response (6 2 6)
setserver
C
Fred Johansen <fredj@pvv.ntnu.no>
setserver <program> <port>
(See: #define CORRECT_SYNTAX )
Sets up a server on port argv[2] that gives you a (one) connection to the argv[1] program.
Authentication: Such a server is a potential security problem since it has the read and write permissions of its user id. Therefore you have to give a username and password for authentication when initiating the connection, thereby proving that you are an authorized server-user.
Processes: This program mainly operates with 4 types of processes; the Socket_listener (original parent process), the Connection_handler process (a child of Socket_listener which handles a connection to Program_server), the Program_server process (a child of Socket_listener which execs into the program set up as requested on the command line argv[]), and the Response_handler (a child of Connection_handler which handles response from the Program_server).
The Socket_listener listens on a socket and forks off connection handling processes. Only *one* of the connection handling processes can write to the Program_server at a time (because of inconsistency problems), so while there already exists a process called Connection_handler, all other connection handlers being forked off quickly exits, after writing back a 'busy' message on the socket.
If no Connection_handler currently exists, the forked-off connection handler is named Connection_handler and set up to write to and read from the Program_server. The Program_server has exec'ed into the requested program, which means that after we exec it, all we can do with it is to write to it and read from it. The Connection_handler also forks off a Response_handler handling response from the Program_server. When a connection is finished, Connection_handler and Response_handler exits, leaving the Socket_listener free to make a new Connection_handler when getting a new connection.
An authenticated user can also shutdown the server. When a shutdown is initiated, all the processes exit, either by themselves, or by being forced to by a signal from another process.
#include <crypt.h> #include <errno.h> #include <fcntl.h> #include <netdb.h> #include <netinet/in.h> #include <signal.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <sys/socket.h> #include <sys/stat.h> #include <sys/time.h> #include <sys/types.h> #include <unistd.h> #include <wait.h> /* * We follow the telnet protocol when negotiating * the toggling of local echo for password input: */ #include "telnet.h"
/****** Macros: ******/ #define CORRECT_SYNTAX "Syntax: 'setserver <program> <port>'\n" #define CORRECT_ARGC_NUMBER 3 #define SOCKET_LISTENER_LOG \ "/home/hades/a/prosjekt/creekl/log/setserver/socket-listener.log" #define CONNECTION_HANDLER_LOG \ "/home/hades/a/prosjekt/creekl/log/setserver/connection-handler.log" #define PROGRAM_SERVER_LOG \ "/home/hades/a/prosjekt/creekl/log/setserver/program-server.log" #define RESPONSE_HANDLER_LOG \ "/home/hades/a/prosjekt/creekl/log/setserver/response-handler.log" #define TMP_CONNECTION_HANDLER_LOG \ "/home/hades/a/prosjekt/creekl/log/setserver/tmp-connection-handler.log" #if 1 /* Turning authentication on or off? */ #define AUTH_ON #else #undef AUTH_ON #endif #define AUTH_FILE "/home/hades/a/prosjekt/creekl/passwd/passwords" #define AUTH_MAX_USERS 32 /* Max number of users in the auth file. */ /* Simple sanity checking on passwords: */ #define MIN_PASSWD_LEN 8 #define MAX_PASSWD_LEN 32 #define AUTH_MAX_TRIES 3 #define QUIT_CMD "quit" #define SHUTDOWN_CMD "shutdown" #define SHUTDOWN_LISP_CMD "(exit)" #define BUSY_MESSAGE "Server busy - try again.\n" #define BUFSIZE 4096 /* TRUE and FALSE may be previously #defined. */ #ifndef FALSE #define FALSE 0 #endif #ifndef TRUE #define TRUE !FALSE #endif
enum read_or_write { /* Pipe indexing. */
READ = 0,
WRITE
};
enum connection_status { /* Connection status handling. */
CONN_CONTINUE = 0,
CONN_QUIT,
CONN_SHUTDOWN,
CONN_BUSY,
};
enum exit_codes { /* Codes for the program's exit status. */
EXIT_OK = 0,
EXIT_SYNTAX_ERROR = 1,
EXIT_PIPE_ERROR = 2,
EXIT_FORK_ERROR = 3,
EXIT_ACCEPT_ERROR = 4,
EXIT_SOCKET_ERROR = 5,
EXIT_SETSOCKOPT_ERROR = 6,
EXIT_BIND_ERROR = 7,
EXIT_GETSOCKNAME_ERROR = 8,
EXIT_SIGNAL_ERROR = 9,
EXIT_OUT_OF_MEMORY = 10,
/* EXIT_EOF_NOT_EXPECTED = 11, */
EXIT_SIGSEGV_RECEIVED = 12,
EXIT_SIGINT_RECEIVED = 13,
EXIT_NO_LOG = 14,
EXIT_ID_BEWILDERMENT = 15,
EXIT_CANNOT_OPEN = 16,
EXIT_ON_QUIT = 17,
EXIT_ON_SHUTDOWN = 18,
EXIT_ON_BUSY = 19,
EXIT_ON_UNKNOWN_STATUS = 20,
};
enum kill_returns { /* Return values for kill(). */
KILL_RETURN_ERR = -1,
KILL_RETURN_OK = 0
};
typedef char AuthBuf[AUTH_MAX_USERS][BUFSIZE]; typedef char CharBuf[BUFSIZE];
int main (int argc, char *argv[]) ;
int handle_sockets (int our_port_no) ;
void connection_handler_func (int users,
AuthBuf user, AuthBuf passwd) ;
int authenticate (int users, AuthBuf user, AuthBuf pass);
int query_password (int users, char* given_user,
AuthBuf user, AuthBuf pass, char *password);
void get_line_from_socket (char *line);
int read_socket_write_program (void) ;
void response_handler_func (void);
void do_exit (int e) ;
void write_back (char *write_arg);
int setup_authentication (AuthBuf user, AuthBuf pass) ;
void setup_socket (int ourportno, int *mainsock, int *portno);
void setup_pipes (void);
void dup_it (int fd, int fd2);
int set_echo (int onf, FILE *read_socket);
int do_kill (int pid, int sig);
int do_accept (void);
void setup_signal_handlers (void);
void sigpipe_handler (void) ;
void sigsegv_handler (void) ;
void sigint_handler (void) ;
void sigusr1_handler (void) ;
void sigusr2_handler (void) ;
void log_it (char *log_arg) ;
void log_errno (char *logerr_arg) ;
void write_errno (char *str) ;
void do_open_log (char *filename) ;
void do_close_log (void) ;
/****** Global Variables (Capitalized): ******/ int Send_pipe[2]; /* [0]:READ, [1]:WRITE */ int Recv_pipe[2]; /* [0]:READ, [1]:WRITE */ int Mainsocket, Mesgsocket, Is_busy; int Socket_listener_pid, Connection_handler_pid, Program_server_pid, Response_handler_pid; int Log_file; CharBuf Log_buf; CharBuf Filename;
The main function. It gets called with the arguments given to the program at the command line. First we check these, and then we call functions setting up the pipes which we will be using to write to and read from the Program_server process later. We do one fork(), splitting the program into two processes, the first of which (parent process) will be the Socket_listener process, the second of which (child process) exec's into the Program_server, ie. the program whose filename was given as an argument.
int
main (int argc, char *argv[]) {
char *str;
if (argc != CORRECT_ARGC_NUMBER) {
/* This is a daemon, so we won't have stdout and stderr,
but we'll use stderr here anyway in case we start it up
from the shell command line when debugging. */
fprintf(stderr, CORRECT_SYNTAX);
exit(EXIT_SYNTAX_ERROR);
}
if ((str = strrchr(argv[0],'/')) != NULL) {
strcpy(Filename,++str);
}
else {
strcpy(Filename, argv[0]);
}
setup_pipes();
setup_signal_handlers();
Mainsocket = Mesgsocket = Is_busy = 0;
Connection_handler_pid = Program_server_pid =
Response_handler_pid = 0;
Socket_listener_pid = getpid(); /* Parent process. */
Log_file = -1; /* No log initially. */
do_open_log(SOCKET_LISTENER_LOG);
log_it("Socket_listener's log opened for append.\n");
if ((Program_server_pid = fork()) < 0) {
log_errno("main(): Error in Program_server_pid = fork()");
do_exit(EXIT_FORK_ERROR);
}
else if (Program_server_pid > 0) { /* Parent process. */
sprintf(Log_buf, "Parent process forked "
"Program_server_pid %d\n", Program_server_pid);
log_it(Log_buf);
close(Send_pipe[READ]);
close(Recv_pipe[WRITE]);
handle_sockets(atoi(argv[2]));
}
else { /********* Program_server process. *********/
do_open_log(PROGRAM_SERVER_LOG);
log_it("Program_server running...\n");
fflush(NULL);
/* Dup STDIN to the READ end of the Send_pipe: */
close(Send_pipe[WRITE]);
if (Send_pipe[READ] != STDIN_FILENO) {
dup_it(Send_pipe[READ],STDIN_FILENO);
close(Send_pipe[READ]);
}
/* Dup STDOUT to the WRITE end of the Recv_pipe: */
close(Recv_pipe[READ]);
if (Recv_pipe[WRITE] != STDOUT_FILENO) {
dup_it(Recv_pipe[WRITE],STDOUT_FILENO);
close(Recv_pipe[WRITE]);
}
/* Exec into the program given at the argument line: */
execlp(argv[1],argv[1],(char*)0);
}
log_it("Impossible to reach this line!\n");
}
This is the most important function of the Socket_listener process. First it sets up the authentication, meaning that it calls setup_authentication(), which reads from a config file containing allowed names and passwords. Secondly, it sets up the socket to listen to by calling setup_socket(). Then it enters a infinite loop listening for connections on the socket. Whenever it gets a connection it forks off a Connection_handler process (which immediately enters the connection_handler_func() function) to deal with it.
int
handle_sockets (int our_port_no) {
int i, idx, users, portno;
AuthBuf user, passwd;
#ifdef AUTH_ON
users = setup_authentication(user, passwd);
for (i=1,idx=0; i<=users; i++,idx++) {
sprintf(Log_buf, "Auth: user %2d: '%s' passwd '%s'\n",
i, user[idx], passwd[idx]);
log_it(Log_buf);
}
#endif
setup_socket (our_port_no, &Mainsocket, &portno);
sprintf(Log_buf, "Server on port %d.\n", portno);
log_it(Log_buf);
/*** Start accepting connections: ***/
Is_busy = FALSE;
listen(Mainsocket, 5);
do {
if (Mesgsocket = do_accept()) {
/* fork() on accept(): */
if ((Connection_handler_pid = fork()) < 0) {
log_errno("Connection_handler_pid = fork()");
do_exit(EXIT_FORK_ERROR);
}
/* Socket_listener process: */
else if (Connection_handler_pid > 0) {
Is_busy = TRUE;
/* Is_busy is only set back to FALSE by SIGUSR1. */
sprintf(Log_buf, "Forked connection handler %d\n",
Connection_handler_pid);
log_it(Log_buf);
}
else { /* Connection handler process. */
connection_handler_func(users, user, passwd);
log_it("Impossible to reach this line!\n");
}
}
} while (TRUE);
}
This is the most important function of the Connection_handler process. It handles the connection to Program_server. If the user that is connected supplies the correct name and password, we do a fork(), forking off a Response_handler function which handles the *response* from the Program_server. The parent process (still the Connection_handler process) calls read_socket_write_program(), which does the *writing* to the Program_server. When the connection ends we call do_exit() with the proper argument, depending on the status we have, ie. whether the user just quits, or is shutting down the server, or whether this is only a temporary connection due to the Program_server being busy.
void
connection_handler_func (int users,
AuthBuf user, AuthBuf passwd) {
int conn_status;
if (Is_busy) {
/*
* What about sending SIGUSR1 instead *when*
* we become busy?
*/
do_open_log(TMP_CONNECTION_HANDLER_LOG);
write_back(BUSY_MESSAGE);
conn_status = CONN_BUSY;
log_it("Server is busy - closing down temporary "
"conncection...\n");
}
else {
do_open_log(CONNECTION_HANDLER_LOG);
if ((conn_status = authenticate(users, user, passwd))
== CONN_CONTINUE) {
if ((Response_handler_pid = fork()) < 0) {
log_errno("Error in Response_handler_pid = fork()");
do_exit(EXIT_FORK_ERROR);
}
else if (Response_handler_pid > 0) {
sprintf(Log_buf, "Forked Response_handler_pid %d\n",
Response_handler_pid);
log_it(Log_buf);
conn_status = read_socket_write_program();
}
else { /* Response_handler process. */
response_handler_func ();
do_exit(EXIT_OK);
}
}
}
sprintf(Log_buf, "Quitting current connection on "
"conn_status %d\n", conn_status);
log_it(Log_buf);
write_back("Good-bye!\n");
if (shutdown(Mesgsocket,2)) {
log_errno("shutdown(Mesgsocket,2)");
}
if (close(Mesgsocket) < 0) {
log_errno("close(Mesgsocket)");
}
log_it("Connection: close().\n");
switch (conn_status) {
case CONN_SHUTDOWN: do_exit(EXIT_ON_SHUTDOWN);
case CONN_QUIT: do_exit(EXIT_ON_QUIT);
case CONN_BUSY: do_exit(EXIT_ON_BUSY);
default:
sprintf(Log_buf, "Exiting on unknown connection "
"status: %d\n", conn_status);
log_it(Log_buf);
do_exit(EXIT_ON_UNKNOWN_STATUS);
}
}
Handles exiting for the processes Connection_handler, Socket_listener and Response_handler. When Connection_handler exits, if it was not just a temporary connection it has to let the Socket_listener know that the Program_server is no longer busy with a connection. In this case it sends a SIGUSR1 to the Socket_listener. When Socket_listener exits, it has to make sure the Program_server is done. If not, it kills it. When Response_handler exits, it's because it has got a SIGINT from Connection_handler, so it exits without doing anything else. (Except logging, which all the processes do. )
void
do_exit (int e) {
sprintf(Log_buf, "do_exit(%d)...\n\t%s:%d\n\t"
"%s:%d\n\t%s:%d\n\t%s:%d\n", e,
"Socket_listener_pid", Socket_listener_pid,
"Connection_handler_pid", Connection_handler_pid,
"Response_handler_pid", Response_handler_pid,
"Program_server_pid", Program_server_pid);
log_it(Log_buf);
if (getppid() == Socket_listener_pid) {
/*** We are Connection_handler. ***/
log_it("Connection_handler do_exit()\n");
if (Response_handler_pid) {
log_it("Killing Response_handler...\n");
do_kill(Response_handler_pid, SIGINT);
wait(NULL);
}
if (e == EXIT_ON_SHUTDOWN) {
log_it("Shutting down Socket_listener...\n");
do_kill(Socket_listener_pid, SIGINT);
}
else if (e == EXIT_ON_QUIT) {
log_it("Informing Socket_listener that we're done.\n");
log_it("sleep(1)...\n");
sleep(1);
/* Telling Socket_listener we are no longer busy with a
connection: */
do_kill(Socket_listener_pid, SIGUSR1);
}
else if (e == EXIT_ON_BUSY) {
sprintf(Log_buf, "Temporary connection closed.\n%s\n",
"Exiting because server is busy with another "
"connection.\n");
log_it(Log_buf);
sleep(1);
/* Telling parent (Socket_listener) to wait(): */
do_kill(Socket_listener_pid, SIGUSR2);
}
else {
log_it("Unexpected exit code.\n");
/* Telling parent (Socket_listener) to wait(): */
do_kill(Socket_listener_pid, SIGUSR2);
}
}
else if (getpid() == Socket_listener_pid) {
/*** We are Socket_listener. ***/
log_it("Socket_listener do_exit()\n");
if (close(Mainsocket) < 0) {
log_errno("close(Mainsocket)");
}
else {
log_it("Mainsocket close() ok.\n");
}
log_it("sleep(2)...\n");
/* Program_server gets a chance to go down on CONN_SHUTDOWN: */
sleep(2);
if (do_kill(Program_server_pid,SIGUSR1) == KILL_RETURN_OK) {
/* The process exists. */
log_it("Killing Program_server_pid\n");
do_kill(Program_server_pid, SIGKILL); /* whack! */
}
log_it("wait()ing for Program_server to exit.\n");
wait(NULL);
log_it("wait()ing for Connection_handler to exit.\n");
wait(NULL);
}
else { /*** We are Response_handler. ***/
log_it("Response_handler do_exit()\n");
}
sprintf(Log_buf, "Calling exit(%d):\n%s\n", e,
"******************************************\n");
log_it(Log_buf);
fflush(NULL);
do_close_log();
exit(e);
}
Authenticate the user 'user' with password 'pass'. Returns either CONN_CONTINUE (meaning we are authenticated) or CONN_QUIT (meaning we are not authenticated, and the connection should be closed subsequently). authenticate() cannot return CONN_SHUTDOWN because an unauthenticated user should not be able to shutdown the server.
int
authenticate (int users, AuthBuf user, AuthBuf pass) {
CharBuf given_user, given_passwd, correct_crypted;
int authenticated, tries, quit_conn;
FILE *read_s;
#ifndef AUTH_ON
return CONN_CONTINUE;
#else
authenticated = FALSE; /* Not authenticated as default. */
tries = 1;
if ((read_s = fdopen(Mesgsocket, "r")) == NULL) {
log_errno("fdopen(Mesgsocket,\"r\")\n");
do_exit(EXIT_CANNOT_OPEN);
}
/* Prompt for Username and Password until we are
authenticated: */
while (!authenticated && (tries <= AUTH_MAX_TRIES)) {
write_back("Username: ");
get_line_from_socket(given_user);
if (strcmp(given_user, QUIT_CMD) == 0) { /* == "quit" */
return CONN_QUIT;
}
if ((quit_conn = set_echo(FALSE, read_s)) != CONN_CONTINUE) {
sprintf(Log_buf, "set_echo() returned %d\n", quit_conn);
log_it(Log_buf);
return quit_conn;
}
write_back("Password: ");
get_line_from_socket(given_passwd);
write_back("\n");
if ((quit_conn = set_echo(TRUE, read_s)) != CONN_CONTINUE) {
sprintf(Log_buf, "set_echo() returned %d\n", quit_conn);
log_it(Log_buf);
return quit_conn;
}
if (strcmp(given_passwd, QUIT_CMD) == 0) { /* == "quit" */
return CONN_QUIT;
}
if (query_password(users,given_user,user,pass,correct_crypted)) {
if (strcmp(correct_crypted, crypt(given_passwd,correct_crypted))
== 0) {
authenticated = 1;
}
}
else {
sprintf(Log_buf, "Attempted login by *UNKNOWN* user '%s'.\n",
given_user);
log_it(Log_buf);
}
if (!authenticated) {
sprintf(Log_buf, "User '%s' failed authentication.\n",
given_user);
log_it(Log_buf);
tries++;
sleep(1);
}
}
if (!authenticated && (tries > AUTH_MAX_TRIES)) {
write_back("Too many tries. User not authenticated.\n");
}
else if (authenticated) {
sprintf(Log_buf, "Connection authenticated for user '%s'.\n",
given_user);
log_it(Log_buf);
write_back("Connection authenticated.\n");
}
if (authenticated) {
return CONN_CONTINUE;
}
else {
return CONN_QUIT;
}
#endif
}
Looks in the arrays 'user' and 'pass' to see if the given 'given_user' and 'password' are present and linked to each other. (That the user with exactly that name is registered with exactly that password.) If there is a match, the function returns TRUE, otherwise it returns FALSE.
int
query_password (int users, char* given_user,
AuthBuf user, AuthBuf pass, char *password) {
int i, idx;
for (i=1,idx=0; i<=users; i++,idx++) {
if (strcmp(given_user, user[idx]) == 0) {
strcpy(password, pass[idx]);
return TRUE;
}
}
return FALSE;
}
Returns a line of input, minus newline character, that has been read from the socket.
void
get_line_from_socket (char *line) {
char strchar[2], *eol;
int c;
memset(line, 0, BUFSIZE);
if (read(Mesgsocket, line, BUFSIZE) < 0) {
log_errno("get_line_from_socket(): read(Mesgsocket)");
}
if (((eol = strrchr(line,'\r')) != NULL)
|| ((eol = strrchr(line,'\f')) != NULL)
|| ((eol = strrchr(line,'\n')) != NULL)) {
strcpy(eol,"\0"); /* Truncating. */
}
log_it(Log_buf);
}
Reads from the socket and writes to the Program_server process, via the pipe set up in main().
int
read_socket_write_program (void) {
CharBuf buf;
char strchar[2];
int c, do_write, quit;
FILE *read_socket, *write_program;
if ((read_socket = fdopen(Mesgsocket, "r")) == NULL) {
log_errno("fdopen(Mesgsocket,\"r\")\n");
do_exit(EXIT_CANNOT_OPEN);
}
if ((write_program = fdopen(Send_pipe[WRITE], "w"))
== NULL) {
log_errno("fdopen(Send_pipe[WRITE],\"w\")\n");
do_exit(EXIT_CANNOT_OPEN);
}
strcpy(buf, "\0");
quit = CONN_CONTINUE;
while ((quit==CONN_CONTINUE)
&& ((c = getc(read_socket)) != EOF)) {
do_write = 0;
if (c == '\r') { /* carriage return */
do_write = 0;
}
/* form feed / newline: */
else if ((c == '\f') || (c == '\n')) {
do_write = 1;
}
else {
sprintf(strchar, "%c", c);
strcat(buf, strchar); /* append */
do_write = 0;
}
if (do_write) {
if (strcmp(buf,QUIT_CMD) == 0) {
/* == "quit" */
quit = CONN_QUIT;
}
else {
if (strcmp(buf,SHUTDOWN_CMD) == 0) {
/* == "shutdown" */
strcpy(buf,SHUTDOWN_LISP_CMD);
quit = CONN_SHUTDOWN;
}
sprintf(Log_buf, "Giving '%s' to Program_server.\n",
buf);
log_it(Log_buf);
strcat(buf,"\n");
if (write(Send_pipe[WRITE], buf, strlen(buf)) < 0) {
log_errno("write(Send_pipe[WRITE])");
}
strcpy(buf,"\0");
}
}
}
if ((c == EOF) && (quit != CONN_SHUTDOWN)) {
quit = CONN_QUIT;
}
if ((strlen(buf) > 0) && (quit != CONN_QUIT) && (quit != CONN_SHUTDOWN)) {
sprintf(Log_buf, "LAST: Giving '%s' to Program_server.\n",
buf);
log_it(Log_buf);
fprintf(write_program, "%s\n", buf);
}
if ((quit != CONN_QUIT) && (quit != CONN_SHUTDOWN)) {
log_it("read_socket_write_program() returned neither "
"CONN_QUIT nor CONN_SHUTDOWN!\n");
}
fflush(write_program);
return quit;
}
Reads from Program_server, writes to socket.
void
response_handler_func (void) {
char buf[2];
CharBuf big_buf;
int c, last_c, do_write;
int ret;
do_open_log(RESPONSE_HANDLER_LOG);
log_it("Response_handler running...\n");
ret = 1;
while (ret >= 0) {
memset(big_buf, 0, BUFSIZE);
if (ret = read(Recv_pipe[READ], big_buf, BUFSIZE) < 0) {
log_errno("read");
}
if (write(Mesgsocket, big_buf, strlen(big_buf)) < 0) {
log_errno("write");
}
}
}
Writes a string back on the socket.
void
write_back (char *write_arg) {
if ((write_arg != NULL) && Mesgsocket) {
if (write(Mesgsocket, write_arg, strlen(write_arg)) < 0) {
log_errno("write");
}
}
}
Sets up authentication by reading a config file of names with passwords and putting this information into a couple of arrays. These arrays thus represents names of users that are allowed to connect to the Program_server, if they give the correct password.
int
setup_authentication (AuthBuf user, AuthBuf pass) {
CharBuf buf, u;
int read_colons, line_no, c, i, users;
FILE *auth_file;
char strchar[2];
for (i=0; i<AUTH_MAX_USERS; i++) {
strcpy(user[i],"\0");
strcpy(pass[i],"\0");
}
/* Read the authentication file: */
auth_file = fopen(AUTH_FILE, "r");
users = read_colons = 0;
line_no = 1;
strcpy(u,"\0");
strcpy(buf,"\0");
while ((c = getc(auth_file)) != EOF) {
if (c == '\r') { /* carriage return */
}
else if ((c == '\f') || (c == '\n')) {
/* form feed or newline */
if (read_colons != 1) {
sprintf(Log_buf, "%s: %d colons line %d user '%s'\n",
"setup_authentication()", read_colons, line_no, u);
log_it(Log_buf);
}
else if ((strlen(buf) < MIN_PASSWD_LEN) ||
(strlen(buf) > MAX_PASSWD_LEN)) {
sprintf(Log_buf, "setup_authentication(): Unexpected passwd "
"length line %d user '%s'\n", line_no, u);
log_it(Log_buf);
}
else { /* ok passwd line */
strcpy(user[users],u); /* Setting user. */
strcpy(pass[users],buf); /* Setting password. */
users++;
}
read_colons = 0;
strcpy(buf,"\0"); /* Cleaning buffer for new user. */
line_no++;
}
else { /* Reading a character on the line. */
if (c == ':') { /* Skipping colon. */
read_colons++;
strcpy(u,buf); /* Remembering user. */
strcpy(buf,"\0"); /* Cleaning buffer for password. */
}
else {
sprintf(strchar, "%c", c);
strcat(buf, strchar); /* append */
}
}
}
if (fclose(auth_file) == EOF) {
log_errno("fclose(auth_file)");
}
return users;
}
Sets up a socket of the 'stream' type in the Internet domain. This makes our program into a server which any other client program using sockets on the Internet can connect to.
void
setup_socket (int ourportno, int *mainsock, int *portno) {
struct sockaddr_in server;
int optval, length;
/*** Create socket: ***/
(*mainsock) = socket(AF_INET, SOCK_STREAM, 0);
if ( (*mainsock) < 0) {
log_errno("setup_socket(): opening stream socket");
do_exit(EXIT_SOCKET_ERROR);
}
/*** Enable local address reuse: ***/
optval = 1;
if(setsockopt((*mainsock), SOL_SOCKET, SO_REUSEADDR,
(char *)&optval, sizeof(optval)) == -1){
log_errno("setup_socket(): setsockopt");
do_exit(EXIT_SETSOCKOPT_ERROR);
}
/*** Name socket with our port number: ***/
server.sin_family = AF_INET;
server.sin_port = htons(ourportno);
if (bind((*mainsock),(struct sockaddr *)&server, sizeof server)
< 0) {
log_errno("setup_socket(): binding stream socket");
do_exit(EXIT_BIND_ERROR);
}
/*** Inquire about assigned port number: ***/
length = sizeof server;
if (getsockname((*mainsock),(struct sockaddr *)&server,
&length) < 0) {
log_errno("setup_socket(): getsockname");
do_exit(EXIT_GETSOCKNAME_ERROR);
}
(*portno) = ntohs(server.sin_port);
}
Sets up signal handlers, ie. functions to be called when the process receives certain signals. This is necessary since we use several processes, and these have to communicate with each other in some way. For the functionality of the various signals, see the signal handlers themselves and the do_exit() function.
void
setup_signal_handlers (void) {
/* signal() for one-time signal handlers.
*/
/* Register signal handler for SIGSEGV: */
if(signal(SIGSEGV,(void *) (sigsegv_handler)) == SIG_ERR){
log_errno("signal(SIGSEGV)");
do_exit(EXIT_SIGNAL_ERROR);
}
/* Register signal handler for SIGINT: */
if(signal(SIGINT,(void *) (sigint_handler)) == SIG_ERR){
log_errno("signal(SIGINT)");
do_exit(EXIT_SIGNAL_ERROR);
}
/* sigset() makes the signal_handlers permanent,
* and blocks the signal (for later delivery) while
* the signal_handlers are being executed.
*/
/* Register signal handler for SIGPIPE: */
if(sigset(SIGPIPE,(void *) (sigpipe_handler)) == SIG_ERR){
log_errno("signal(SIGPIPE)");
do_exit(EXIT_SIGNAL_ERROR);
}
/* Register signal handler for SIGUSR1: */
if(sigset(SIGUSR1,(void *) (sigusr1_handler)) == SIG_ERR){
log_errno("signal(SIGUSR1)");
do_exit(EXIT_SIGNAL_ERROR);
}
/* Register signal handler for SIGUSR2: */
if(sigset(SIGUSR2,(void *) (sigusr2_handler)) == SIG_ERR){
log_errno("signal(SIGUSR2)");
do_exit(EXIT_SIGNAL_ERROR);
}
}
Signal handler for the SIGSEGV signal (segment violation). (See the setup_signal_handlers() and do_exit() functions for details.)
void
sigsegv_handler (void) {
log_it("SIGSEGV received\n");
do_exit(EXIT_SIGSEGV_RECEIVED);
}
Signal handler for the SIGINT signal (interupt). (See the setup_signal_handlers() and do_exit() functions for details.)
void
sigint_handler (void) {
log_it("SIGINT received\n");
do_exit(EXIT_SIGINT_RECEIVED);
}
Signal handler for the SIGPIPE signal (data written to a pipe without an end). (See the setup_signal_handlers() and do_exit() functions for details.)
void
sigpipe_handler (void) {
log_it("SIGPIPE received\n");
/* We don't exit on receiving SIGPIPE. */
}
Signal handler for the SIGUSR1 signal (user defined signal #1). (See the setup_signal_handlers() and do_exit() functions for details.)
void
sigusr1_handler (void) {
log_it("SIGUSR1 received, saying connection is not busy.\n");
if (getpid() == Socket_listener_pid) {
wait(NULL); /* Waiting for Connection_handler to exit. */
log_it("wait() performed.\n");
Is_busy = FALSE;
}
}
Signal handler for the SIGUSR2 signal (user defined signal #2). (See the setup_signal_handlers() and do_exit() functions for details.)
void
sigusr2_handler (void) {
log_it("SIGUSR2 received, saying temporary connection "
"ended\n due to server being busy. Doing "
"wait() to make the\n process disappear "
"correctly.\n");
wait(NULL);
}
Sets up the pipes to be used for writing and reading from the Program_server process. See main().
void
setup_pipes (void) {
/* Send_pipe is for sending output to the Program_server
* process.
*/
if (pipe(Send_pipe) < 0) {
log_errno("Error in pipe(Send_pipe)");
do_exit(EXIT_PIPE_ERROR);
}
/* Recv_pipe is for getting output back from the Program_server
* process.
*/
if (pipe(Recv_pipe) < 0) {
log_errno("Error in pipe(Recv_pipe)");
do_exit(EXIT_PIPE_ERROR);
}
}
Duplicates a file descriptor. Contains some additional error checking and logging if there is an error.
void
dup_it (int fd, int fd2) {
int r;
r = dup2(fd,fd2);
if (r < 0) {
sprintf(Log_buf, "dup_it(): dup2() returned %d\n", r);
log_it(Log_buf);
}
}
Toggles local echo in the client (for password input). Uses the TELNET protocol for this, so we can talk to telnet programs. (Needs to #include telnet.h.)
int
set_echo (int on, FILE *read_socket) {
char send[3];
int resp[3], wrong_code, ret;
sprintf(Log_buf, "set_echo(%d)...\n", on);
log_it(Log_buf);
ret = CONN_CONTINUE;
wrong_code = FALSE;
send[0] = IAC;
if (on) {
send[1] = WONT ;
}
else {
send[1] = WILL ;
}
send[2] = TELOPT_ECHO;
if (write(Mesgsocket, send, 3) < 0) {
log_errno("writing echo cmd on the stream socket");
}
if (((resp[0] = getc(read_socket)) != EOF)
&& ((resp[1] = getc(read_socket)) != EOF)
&& ((resp[2] = getc(read_socket)) != EOF)) {
/* The response is supposed to be: IAC DO/DONT TELOPT_ECHO
(DO if turning echo off, DONT if turning it on.) */
if (resp[0] != IAC) {
sprintf(Log_buf, "Didn't get IAC (telnet code) "
"when expected!\n");
log_it(Log_buf);
wrong_code = TRUE;
}
if (!on) { /* Turning echo off. */
if (resp[1] != DO) {
sprintf(Log_buf, "Didn't get DO (telnet code) "
"when expected!\n");
log_it(Log_buf);
wrong_code = TRUE;
}
}
else if (on) { /* Turning echo on. (This is the norm.) */
if (resp[1] != DONT) {
sprintf(Log_buf, "Didn't get DONT (telnet code) "
"when expected!\n");
log_it(Log_buf);
wrong_code = TRUE;
}
}
if (resp[2] != TELOPT_ECHO) {
sprintf(Log_buf, "Didn't get TELOPT_ECHO (telnet code) "
"when expected!\n");
log_it(Log_buf);
wrong_code = TRUE;
}
sprintf(Log_buf, "Got telnet codes: %d %d %d\n",
resp[0], resp[1], resp[2] );
log_it(Log_buf);
}
else {
sprintf(Log_buf, "Got EOF instead of telnet code "
"response!\n");
log_it(Log_buf);
ret = CONN_QUIT;
}
if (wrong_code) {
sprintf(Log_buf, "wrong_code: %d\n", wrong_code);
log_it(Log_buf);
write_back("Warning: Local echo toggling may have "
"failed.\n");
}
return ret;
}
Kills a process, ie. sends it a signal. Calls the kill() system call, but also does some logging, for debugging purposes.
int
do_kill (int pid, int sig) {
int ret;
sprintf(Log_buf, "kill(%d,%d)...\n", pid, sig);
log_it(Log_buf);
if (ret = kill(pid,sig) != 0) {
sprintf(Log_buf, "kill(%d,%d)\n", pid, sig);
log_errno(Log_buf);
}
return ret;
}
Accepts a connection on the socket, by calling the accept() system call. Usually, accept() returns when the process receives a signal, but this program (in the Socket_listener process) ignores signals in this case, as we expect to get SIGUSR1 sooner or later, telling us that the previous connection has finished. (When the Connection_handler exits.)
int
do_accept (void) {
int msgsock;
msgsock = accept(Mainsocket, (struct sockaddr *)0, (int *)0);
if (msgsock == -1) {
log_errno("accept");
if (errno == EINTR) {
log_it("do_accept() does not exit on receiving a "
"signal.\n");
/* Because we expect to get SIGUSR1 signifying that the
previous connection is finished. */
msgsock = FALSE;
}
else {
do_exit(EXIT_ACCEPT_ERROR);
}
}
else {
log_it("Connection accepted.\n");
}
return msgsock;
}
Logs the argument to the current process' log file. If an error in writing occurs, try to alarm the user instead. (Writing to stdout/err makes no sense in a daemon like this, all we've got is the log file and the socket.) The reason we're using a local buf instead of Log_buf here is that the argument is probably pointing to it already. We don't want to copy a string onto itself.
void
log_it (char *log_arg) {
CharBuf buf, errbuf;
sprintf(buf, "%s pid %d: %s", Filename, getpid(), log_arg);
if (write(Log_file, buf, strlen(buf)) < 0) {
if (Mesgsocket) {
sprintf(errbuf, "SERVER INTERNAL ERROR: Couldn't "
"write(%d,%s,%d)\n",
Log_file, buf, strlen(buf));
write_errno(errbuf);
}
}
}
Logs the string argument together with the current errno (error number) and its appropriate error message. Calls log_it() to do the actual logging.
void
log_errno (char *logerr_arg) {
CharBuf buf;
sprintf(buf, "%s: %s (errno %d)\n",
logerr_arg, strerror(errno), errno);
log_it(buf);
}
Called instead of log_errno() in cases where we have no log to log to, but instead have to write the error message back on the socket, for lack of a better thing to do with it.
void
write_errno (char *write_err_arg) {
CharBuf buf;
sprintf(buf, "%s: %s (errno %d)\n",
write_err_arg, strerror(errno), errno);
write_back(buf);
}
Opens this process' log file for appending. (Each process has its own log file.)
void
do_open_log (char *filename) {
CharBuf buf;
if (Log_file >= 0) {
do_close_log(); /* Change log. */
}
if ((Log_file = open(filename, O_WRONLY|O_APPEND)) < 0 ) {
sprintf(buf, "Pid %d couldn't open(%s,O_WRONLY|O_APPEND)",
getpid(), filename);
/* Can't log this as the log isn't open. */
write_errno(buf);
do_exit(EXIT_NO_LOG);
}
sprintf(Log_buf, "\n\nThis log (fd %d) opened for append.\n",
Log_file);
log_it(Log_buf);
}
Closes the process' log file. (Each process has its own log file.)
void
do_close_log (void) {
CharBuf buf;
if (close(Log_file) < 0) {
sprintf(buf, "Couldn't close log %d.\n", Log_file);
write_errno(buf);
}
}
Here we use SGML entities for ``unusual'' characters, like
< and > for less-than(<) and
greater-than(>) respectively, & for ampersand(&)
and \ for backslash(\). This is the standard in SGML
files, in order to ease translation of all characters in the file to
any other format.
<!doctype litprog SYSTEM "litprog.dtd">
<title> setserver
<lang> C
<author> Fred Johansen <fredj@pvv.ntnu.no>
<syntax> setserver <program> <port>
(See: #define CORRECT_SYNTAX )
<!-- [....] -->
<func> do_close_log
<desc> Closes the process' log file.(Each process has its own log file.)
<code>
void
do_close_log (void) {
CharBuf buf;
if (close(Log_file) < 0) {
sprintf(buf, "Couldn't close log %d.\n", Log_file);
write_errno(buf);
}
}
/* Program Title: setserver
* Program Language: C
* Author: Fred Johansen <fredj@pvv.ntnu.no>
* Syntax: setserver <program> <port>
(See: #define CORRECT_SYNTAX )
/***** [....] *****/
/* FUNC: do_close_log
* DESC: Closes the process' log file.
* (Each process has its own log file.)
*/
void
do_close_log (void) {
CharBuf buf;
if (close(Log_file) < 0) {
sprintf(buf, "Couldn't close log %d.\n", Log_file);
write_errno(buf);
}
}
The setserver-talk.pl program is a simple client to talk to setserver. Simple because it implements a Perl subroutine to send a certain expression to the server (in our case a Lisp interpreter) and get a reply back. The total message sent consists of, as follows: A user name, a password, the (Lisp) expression, and then the string ``quit'', which makes setserver close the connection.
The subroutine is invoked with arguments describing the details of where to find the setserver program to connect to, the user name and password to use and the expression itself. Thus this program implements a connection-less interface to the setserver, if you will. This makes it suitable for use by a WWW program like a CGI script, which need only refer to this program as a Perl library file and use its main subroutine, called get_response.
The program has been written in Litprog, the same self-made SGML document type as was used with the setserver program in Appendix A. The Qwertz version that was automatically generated from it is presented below.
setserver-talk
Perl
Fred Johansen <fredj@pvv.ntnu.no>
To talk with the setserver program, require this file and call get_response() with the following arguments:
get_response($telnet_host, $telnet_port, $user, $passwd, $message).
Examples of the arguments:
$telnet_host : ``nike.ifi.unit.no''
$telnet_port : 2938
$user : ugla
$passwd : urkeburk
$message : (setq x 2346)
The function will return the message the setserver server gives as response.
Author: Fred Johansen <fredj@pvv.unit.no>
# Whether we fork to receive response or not:
# The value of this variable should normally be 0.
# It can be set to 1 for debugging purposes, if we want to #
# the response from the server independently of what we write
# to it and when:
$SETSERVER_TALK__GLOBAL_VAR__RESPONSE_FORK = 0;
$SETSERVER_TALK__GLOBAL_VAR__FILENAME = __FILE__ ;
$SETSERVER_TALK__GLOBAL_VAR__PARENT_LOG =
"/home/hades/a/prosjekt/creekl/log/interface/parent.log" ;
$SETSERVER_TALK__GLOBAL_VAR__TELNET_CMD = "/usr/ucb/telnet" ;
# Cmd to quit the connection:
$SETSERVER_TALK__GLOBAL_VAR__QUIT_CMD = "quit";
# Cmd to shut down the server:
$SETSERVER_TALK__GLOBAL_VAR__SHUTDOWN_CMD = "shutdown";
%SETSERVER_TALK__GLOBAL_VAR__Pids = (); # Process ids.
$SETSERVER_TALK__GLOBAL_VAR__BUFSIZE = 8192;
The only func that should be called from elsewhere. See description at the head of this file.
sub get_response {
local($telnet_host, $telnet_port, $user, $passwd, $msg_to_child) = @_;
local($got_response, $prog, $pid);
$got_response = "" ;
open(SETSERVER_TALK__LOG_FD, ">>$SETSERVER_TALK__GLOBAL_VAR__PARENT_LOG")
|| return &SETSERVER_TALK__report("Couldn't open log!\n");
select(SETSERVER_TALK__LOG_FD); $| = 1; select(STDOUT);
&SETSERVER_TALK__log("\$telnet_host: '$telnet_host'\n");
&SETSERVER_TALK__log("\$telnet_port: '$telnet_port'\n");
&SETSERVER_TALK__log("\$user: '$user'\n");
&SETSERVER_TALK__log("\$msg_to_child: '$msg_to_child'\n");
$msg_to_child =~ !s/\s+$// ; # Chop off whitespace at the end.
$prog = "$SETSERVER_TALK__GLOBAL_VAR__TELNET_CMD $telnet_host $telnet_port" ;
#$prog = "/home/hades/b/ifi-hf/fredj/creekl/bin/myecho.pl" ;
### Setting up a pipe for use between parent and child: ###
pipe(SEND_READ, SEND_WRITE); # Pipe for sending data to Prog_child.
pipe(RECV_READ, RECV_WRITE); # Pipe for receiving data from Prog_child.
pipe(REC2_READ, REC2_WRITE); # Pipe for receiving data from Response_child.
select(SEND_WRITE); $| = 1; # Make SEND_WRITE unbuffered.
select(RECV_WRITE); $| = 1; # Make RECV_WRITE unbuffered.
select(REC2_WRITE); $| = 1; # Make REC2_WRITE unbuffered.
select(SEND_READ); $| = 1; # Make SEND_READ unbuffered.
select(RECV_READ); $| = 1; # Make RECV_READ unbuffered.
select(REC2_READ); $| = 1; # Make REC2_READ unbuffered.
select(STDOUT); $| = 1; # Make STDOUT unbuffered.
### Setting up signal handling: ###
$SIG{'INT'} = 'SETSERVER_TALK__sigint';
$SIG{'PIPE'} = 'SETSERVER_TALK__sigpipe';
### Forking the Prog_child: ###
if ($pid = fork()) { # Parent process.
&SETSERVER_TALK__set_pid("prog_child", $pid);
close(SEND_READ);
close(RECV_WRITE);
# Forking to handle in- & output. (FOR DEBUGGING):
if ($SETSERVER_TALK__GLOBAL_VAR__RESPONSE_FORK) {
if ($pid = fork()) {
&SETSERVER_TALK__set_pid("response_child", $pid);
close(REC2_WRITE);
&SETSERVER_TALK__write_child($user, $passwd, $msg_to_child);
}
else { # child from fork #2.
close(REC2_READ);
$got_response =
&SETSERVER_TALK__read_child_give_response($telnet_host);
# Sending response from Prog_child back to parent.
print REC2_WRITE $got_response;
exit;
}
sleep 1;
&SETSERVER_TALK__dokill;
}
else { # Does *not* fork to handle in- & output.
$got_response =
&SETSERVER_TALK__write_and_read($user, $passwd,
$msg_to_child, $telnet_host);
}
}
else { # Prog_child process.
close(SEND_WRITE);
close(RECV_READ);
open (STDIN, ">&SEND_READ") || die "Can't dup SEND_READ!\n";
open (STDOUT, ">&RECV_WRITE") || die "Can't dup RECV_WRITE!\n";
close(SEND_READ);
close(RECV_WRITE);
&SETSERVER_TALK__log("execing \$prog: '$prog'\n");
exec $prog ;
}
if (!length($got_response)) {
# Finally, the parent has to get the response received (from Prog_child)
# by Response_child:
$got_response = "";
while (<REC2_READ>) {
$got_response .= $_ ;
}
}
return $got_response ;
}
sub SETSERVER_TALK__write_child {
# Argument to the subroutine:
local($username, $passwd, $msg) = @_;
# The command to quit the connection:
local($quit) = $SETSERVER_TALK__GLOBAL_VAR__QUIT_CMD;
local($response) ;
&SETSERVER_TALK__log("sub SETSERVER_TALK__write_child()...\n");
&SETSERVER_TALK__log("\$username: '$username\n");
&SETSERVER_TALK__log("\$msg: '$msg\n");
if ($username && $passwd) {
&SETSERVER_TALK__log("printing \$username " .
"'$username'\n");
print SEND_WRITE "$username\n" ;
sleep 1;
&SETSERVER_TALK__log("printing \$passwd ******\n");
print SEND_WRITE "$passwd\n" ;
sleep 1;
}
&SETSERVER_TALK__log("printing \$msg '$msg'\n");
print SEND_WRITE "$msg\n" ;
sleep 1;
&SETSERVER_TALK__log("printing \$quit '$quit'\n");
print SEND_WRITE "$quit\n" ;
sleep 1;
}
sub SETSERVER_TALK__write_and_read {
# Argument to the subroutine_
local($username, $passwd, $msg, $telnet_to_host) = @_;
# The command to quit the connection.
local($quit) = $SETSERVER_TALK__GLOBAL_VAR__QUIT_CMD;
local($response, $got_response) ;
&SETSERVER_TALK__log("sub SETSERVER_TALK__write_child()...\n");
&SETSERVER_TALK__log("\$username: '$username\n");
&SETSERVER_TALK__log("\$msg: '$msg\n");
if ($username && $passwd) {
&SETSERVER_TALK__log("printing \$username '$username'\n");
print SEND_WRITE "$username\n" ;
sleep 1;
sysread(RECV_READ, $response, $SETSERVER_TALK__GLOBAL_VAR__BUFSIZE);
$got_response = $response;
if ($response =~ m/Server busy - try again/) {
return &SETSERVER_TALK__strip_response($got_response,
$telnet_to_host);
}
&SETSERVER_TALK__log("printing \$passwd ******\n");
print SEND_WRITE "$passwd\n" ;
sleep 1;
sysread(RECV_READ, $response, $SETSERVER_TALK__GLOBAL_VAR__BUFSIZE);
$got_response .= $response;
if ($response =~ m/Server busy - try again/) {
return &SETSERVER_TALK__strip_response($got_response,
$telnet_to_host);
}
### The Lisp expression! :::
&SETSERVER_TALK__log("printing \$msg '$msg'\n");
print SEND_WRITE "$msg\n" ;
sleep 1;
while (sysread(RECV_READ, $response,
$SETSERVER_TALK__GLOBAL_VAR__BUFSIZE)) {
$got_response .= $response;
if ($response =~ m/Server busy - try again/) {
return &SETSERVER_TALK__strip_response($got_response,
$telnet_to_host);
}
if (&SETSERVER_TALK__is_prompt($response)) {
&SETSERVER_TALK__log("printing \$quit '$quit'\n");
print SEND_WRITE "$quit\n" ;
sleep 1;
return &SETSERVER_TALK__strip_response($got_response,
$telnet_to_host);
}
}
}
}
sub SETSERVER_TALK__is_prompt {
local($line) = $_[0];
# Either: [1] USER(48): :res
# Or: USER(49):
if ($line =~ m/\[\d+\]\s+USER\(\d+\):/ ||
$line =~ m/USER\(\d+\):/ ) {
return 1;
}
return 0;
}
sub SETSERVER_TALK__read_child_give_response {
local($telnet_to_host) = @_;
local($buf, $response);
$response = "" ;
&SETSERVER_TALK__log("calling sysread(RECV_READ, \$buf, " .
"$SETSERVER_TALK__GLOBAL_VAR__BUFSIZE)\n");
while(sysread(RECV_READ, $buf, $SETSERVER_TALK__GLOBAL_VAR__BUFSIZE)) {
$response .= $buf;
}
&SETSERVER_TALK__log("\$response: '$response'\n");
return &SETSERVER_TALK__strip_response($response, $telnet_to_host);
}
sub SETSERVER_TALK__strip_response {
local($response, $telnet_to_host) = @_;
&SETSERVER_TALK__log("stripping \$response: '$response'..." .
"\$telnet_to_host: '$telnet_to_host'\n");
# Telnet response scrapped:
#Trying 129.241.163.98 ...
#Connected to nike.ifi.unit.no.
#Escape character is '^]'.
$response =~ s/^Trying\s\d+\.\d+\.\d+\.\d+\s+\.\.\.\s*\n// ;
$response =~ s/^Connected\s+to\s+$telnet_to_host\.\s*\n// ;
$response =~ s/^Escape\s+character\s+is.*\n// ;
# Authentication prompts scrapped: (example)
#Username: CreekLWarrior
#Password: ******
$response =~ s/^Username:\s+.*\n// ;
$response =~ s/^Password:\s+.*\n// ;
# 'Connection authenticated.' message from setserver:
$response =~ s/^Connection authenticated\.\s*\n// ;
# 'USER' LISP prompt:
$response =~ s/\[\d+\]\s+USER\(\d+\)://;
$response =~ s/USER\(\d+\):// ;
# 'Good-bye!' message from setserver:
$response =~ s/\s*Good-bye!\s*\n// ;
&SETSERVER_TALK__log("stripped \$response: '$response'\n");
return $response;
}
sub SETSERVER_TALK__sigint {
&SETSERVER_TALK__log("Received SIGINT.\n");
&SETSERVER_TALK__dokill;
}
sub SETSERVER_TALK__sigpipe {
&SETSERVER_TALK__log("Received SIGPIPE.\n");
# We don't exit on receiving SIGPIPE.
}
sub SETSERVER_TALK__dokill {
local($prog_child, $response_child);
$prog_child = &SETSERVER_TALK__query_pid("prog_child");
$response_child = &SETSERVER_TALK__query_pid("response_child");
kill 'KILL', $prog_child if $prog_child;
kill 'KILL', $response_child if $response_child;
}
sub SETSERVER_TALK__set_pid {
local($pidname, $pidno) = @_;
&SETSERVER_TALK__log("Setting '$pidname' pid to '$pidno'\n");
$SETSERVER_TALK__GLOBAL_VAR__Pids{$pidname} = $pidno;
}
sub SETSERVER_TALK__query_pid {
local($pidname) = @_;
local($pidno);
$pidno = $SETSERVER_TALK__GLOBAL_VAR__Pids{$pidname};
$pidno = 0 if !$pidno;
return $pidno;
}
sub SETSERVER_TALK__report {
local($str) = @_;
return "$SETSERVER_TALK__GLOBAL_VAR__FILENAME: $str";
}
sub SETSERVER_TALK__log {
local($str) = @_;
print SETSERVER_TALK__LOG_FD "CGI pid $$: $str";
}
1;
The litprog.dtd file is the SGML document type definition I authored for use when writing source code for this thesis. It defines the Litprog document type. By using it for this thesis I made easy the extraction and emphasizing of code and documentation respectively, as explained in the preface and source code appendices.
The file is included as is.
<!-- DTD for simple literate programming, by Fred Johansen. -->
<!ENTITY % doctype "LITPROG" -- document type generic identifier -->
<!-- ENTITY % ISOnum PUBLIC
"ISO 8879:1986//ENTITIES Numeric and Special Graphic//EN" -->
<!ENTITY % ISOnum SYSTEM "ISOnum">
%ISOnum;
<!--ENTITY nl "\n" -->
<!ENTITY psplit "</p><p>" >
<!ENTITY null "" >
<!--SHORTREF globmap
"B" null-->
<!-- "
" nl -->
<!SHORTREF pmap
"B
" psplit
"
" psplit >
<!-- ELEMENTS MIN CONTENT (EXCEPTIONS) -->
<!ELEMENT %doctype; O O (HEAD,BODY) >
<!-- USEMAP GLOBMAP LITPROG -->
<!ELEMENT HEAD - O (TITLE, LANG, AUTHOR?, SYNTAX?, PDESC?, INCL?,
MACRO?, ENUM?, TYPEDEF?, HEADERS?, VARS?) >
<!ELEMENT BODY - O (VARS?, FUNC, DESC, CODE)* >
<!-- HEAD elements: -->
<!ELEMENT TITLE - O (#PCDATA) >
<!ELEMENT LANG - O (#PCDATA) >
<!ELEMENT AUTHOR - O (#PCDATA) >
<!ELEMENT SYNTAX - O (#PCDATA) >
<!ELEMENT PDESC - O (#PCDATA | P)* >
<!ELEMENT P O O (#PCDATA) >
<!--USEMAP pmap p-->
<!ELEMENT INCL - O (#PCDATA) >
<!ELEMENT MACRO - O (#PCDATA) >
<!ELEMENT ENUM - O (#PCDATA) >
<!ELEMENT TYPEDEF - O (#PCDATA) >
<!ELEMENT HEADERS - O (#PCDATA) >
<!ELEMENT VARS - O (#PCDATA) >
<!-- BODY elements: -->
<!ELEMENT FUNC - O (#PCDATA) >
<!ELEMENT DESC - O (#PCDATA) >
<!ELEMENT CODE - O (#PCDATA) >
Copyright 1994, 1995 Enterprise Integration Technologies Corporation and Lockheed Missiles and Space Company, Inc. Enterprise Integration Technologies Corporation (EIT) and Lockheed Missiles and Space Company, Inc. (Lockheed) grant to the possessor of this copy (the Licensee) a royalty-free, nonexclusive license to use, copy, modify and distribute both the binary and source code of the KQML KAPI and any related documentation (the Software) for academic, research and internal business purposes only and subject to the following conditions: 1. By using or copying the Software, Licensee agree to abide by the terms of this Agreement. 2. Title and copyright to the Software remain with EIT and Lockheed and Licensee agrees to preserve the same. 3. Licensee acknowledges that the Software is still in the development stage and that it is being supplied "as is", without any accompanying services from EIT or Lockheed. EIT and Lockheed MAKE NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. By way of example, but not limitation, EIT and Lockheed MAKE NO REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR THAT THE USE THE SOFTWARE WILL NOT INFRINGE ON ANY PATENTS OR OTHER RIGHTS. EIT and Lockheed shall not be held liable for any liability nor for any direct, indirect or consequential damages with respect to any claim by Licensee or any third party with respect to this Agreement or any use of the Software. 4. Licensee may distribute the Software or any derivative work based on the the Software to third parties provided (1) all copyright notices and this Agreement appear on all copies, and (2) no charge is associated with such copies. Unless Licensee labels the derivative work with the notice "No Grantback", Licensee agrees to grant EIT and Lockheed a royalty-free nonexclusive license to use, copy, modify and distribute any modifications to the Software owned by Licensee and distributed to third parties as a derivative work under this Agreement. 5. If Licensee distributes a derivative work, then Licensee also agrees to (1) notify EIT and Lockheed of the distribution, and (2) clearly notify users that such derivative work is a modified version and not the original EIT and Lockheed Software. 6. Any Licensee wishing to make commercial use of the Software should contact EIT and Lockheed to negotiate an appropriate license. Commercial use includes (1) integration of all or part of the source code into a product for sale or license by or on behalf of Licensee to third parties, or (2) distribution of the binary or source code to third parties that need it to utilize a commercial product sold or licensed by or on behalf of Licensee. 7. Licensee agrees to abide by all applicable laws of the United States, including, but not limited to, copyright and export control laws. 8. EIT and Lockheed have the right to terminate this license immediately by written notice upon Licensee's breach of, or non-compliance with any of its terms. Licensee may be held legally responsible for any copyright infringement that is caused or encouraged by licensee's failure to abide by the terms of this license.
Software for Networking Knowledge Agents
A Master's thesis
by
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 thesis.tex.
The translation was initiated by Fred Johansen on Wed Nov 20 10:43:48 MET 1996