Cplire.ru

SOFTWARE AND HARDWARE
IN PATTERN RECOGNITION
AND IMAGE ANALYSIS SYSTEMS
Logic Object-Oriented Model
of Asynchronous Concurrent Computations1
A. A. Morozov
Institute of Radio Engineering and Electronics, Russian Academy of Sciences, ul. Mokhovaya 11, Moscow, 125009 Russia Abstract—In this paper, we consider the model of concurrent computations developed for logic programming
of Internet agents. The purpose of creating this model of computations is to ensure the mathematical strictness
of searching and recognizing information on the Internet. In the developed model of computations, the inter-
acting concurrent processes have classical model-theoretic semantics. The model of computations is based on
the new principle of interaction of processes, which do not require delay for synchronization. On the basis of
this model, we have developed and implemented the concurrent object-oriented logic language and also the
tools for visual logic programming of Internet agents.
also the notions of soundness and completeness of logicprograms.
Internet agents are programs that automate retrieval, recognition, extraction, and analysis of information on Over the past decade, a large number of methods the Internet oriented toward the needs of an individual and means of logic programming of Internet agents user (or group of users). Agents differ from the widely were developed. They are based on different modifica- used Internet retrieval systems in the following: tions and extensions of the Prolog language and also on (1) they can autonomously operate during long peri- nonclassical logics (linear, modal, F-Logic, etc.) [1, 3, ods of time (days, weeks, or more) for performing the 4, 24]). However, up to now, no mathematical apparatus which could provide sound and complete work of logic (2) as any other program, once created, an agent can programs (agents) in a dynamic external environment be used many times, whereas a query to a universal (i.e., in conditions of permanent change and augmenta- retrieval system invokes a single operation of informa- tion of information in the Internet) was created.
To solve this problem, we have developed the logic At present, no universally accepted definition of agents exists. However, programs that are autonomous, model of concurrent computations based on the princi- reactive (i.e., react to external stimuli), proactive (e.g., ple of repeated proving of subgoals [21–26]. In the capable of planning further actions themselves), and framework of our model, the Internet agent is a system exhibit a social behavior (if there is a system of several of interacting concurrent processes. The main distinc- agents) [1, 2] are conventionally called agents.
tion of the developed model is the fact that it presumesthe existence of classical model-theoretic semantics of One of the most interesting and perspective approaches to programming Internet agents is logic Internet agents functioning under conditions of infor- programming of agents [1, 3, 4]. The urgency of this mation change and augmentation. For this purpose, in approach is determined, in particular, by the fact that the framework of the model, the classical model-theo- the ideology and principles of logic programming cor- retic semantics of individual concurrent processes and respond to the problems of retrieval, recognition, and of the system of interacting processes as a whole are analysis of ill-structured and also hypertext informa- tion [24, 26]. However, the main advantage of logicprogramming is the fact that, in the framework of this In the first section of the paper, we consider the prin- approach, there exist criteria for evaluating the mathe- cipal elements of our computational model: processes, matical strictness of information processing methods, messages, and the so-called “residents.” In the second namely, the model-theoretic semantics of programs and section, we consider the declarative semantics andmathematical properties of concurrent programs. In the 1 This work was supported by the Russian Foundation for Basic third section, we discuss the use of the developed Research, project nos. 00-01-00560 and 03-01-00256.
model for the visual component-oriented programmingof Internet agents. In the fourth section, our approach toprogramming Internet agents is compared with other Pattern Recognition and Image Analysis, Vol. 13, No. 4, 2003, pp. 640–649.
Original Text Copyright 2003 by Pattern Recognition and Image Analysis. English Translation Copyright 2003 by MAIK “Nauka /Interperiodica” (Russia). LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS The principle of interaction of concurrent processes developed by the author and his colleagues is a gener-alization of the method of speculative computationsapplied to the field of artificial intelligence and also to Fig. 1. States of the process. (a) Proven process, (b) failed
the hardware implementation of computing devices.
The idea of speculative computations implies that cer-tain branches of the algorithm can be implemented inadvance, prior to the moment when it becomes clear (3) We have developed a special mechanism to whether the obtained data are needed for further pro- transfer information between processes (the so-called gram execution. The use of this idea and the mathemat- residents) resembling the setof statement of the stan- ical apparatus of logic programming makes it possible not to delay concurrent processes for their synchroniza- Thus, the processes can interact through common tion. Instead of delaying the processes, we use a modi- variables and also by means of predicate calls. That is fication of logic inference; as a result, the general why, in contrast to the classical object-oriented compu- scheme of interaction of concurrent processes can be tational model using only one kind of message, two kinds of messages are distinguished in our model, Each process performs computations with data available at the present moment. If some data are not When a process handles the obtained message, its yet received, the process performs computations with state changes. The period of process execution corre- incomplete data. As is shown below, the developed sponding to the processing of a certain message is strategy of execution of logic programs is sound with called a phase of process execution. At each phase of respect to their declarative semantics; therefore, any the process execution, the corresponding subgoals of results obtained during computations are correct with the proof (logic actors [21–26]) are proved in accor- respect to the declarative semantics of the program.
dance with the information that has come from the out- Computations with incomplete input data can be side. Depending on the results of repeated proving of regarded as a certain form of computing by default.
actors, the process is transferred into one of the follow- Subsequently, when new or modified input data arrive in the process, the conducted computations are modi- (1) A proven process. This state is characterized by fied and the earlier obtained results are refined.
the consistency of all actors of the process (the proof of Modification of logic inference in our computation model is based on the principle of the repeated proving (2) A failed process. This state is characterized by of subgoals [21–26]. The developed model is imple- the fact that actors of the process are inconsistent.
mented in the concurrent version of the object-oriented (3) An unused process. The unused process can be Actor Prolog logic language [21, 26]. Therefore, to considered as some offline component of a computing simplify the presentation in this paper, we will use the device. The processes automatically pass into the notions and syntactic notation of this language.
unused state and automatically recover from this statewhen certain special flow messages are obtained. These The process in the concurrent Actor Prolog is the The process in the unused state performs no opera- class instance, whose clauses are executed concurrently tions, and all messages sent to it are accumulated in the relative to clauses of other processes. In the Actor Pro- buffer. Using the unused processes, the agent changes log, the processes are denoted by enclosing the con- its structure in the course of execution.
structor of the class instance in double parentheses: The difference between flow and direct messages The transmission of information between processes in our model is carried out by means of the following (1) Direct messages are passed directly from one process to another (in the form of the predicate call), (1) A process can perform an asynchronous predi- while the flow messages are passed from one to many processes (by changing the values of common vari-ables).
(2) A process can pass information to other pro- cesses by changing the value of their common variable.
2 In the definition of the Actor Prolog [21], one more auxiliary state The arguments of the corresponding constructors of arising in the course of process construction is considered addi- class instances can be such common variables.
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 Fig. 2. Flow messages.
Fig. 3. Ports of processes.
(2) Direct messages are not lost in the course of empty value is received through the suspending port, communication, while the flow messages can cancel the process is automatically passed to the unused state.
one another if a new (updated) value of a common vari- When the values of all suspending ports of a process able arrives before the processing of the previous value become not equal to # and to empty values, it will auto- Before the direct and flow messages are transmitted, Using the suspending ports, one can create recursive all unbound variables in the composition of the corre- definitions of processes, i.e., definitions of classes sponding predicate and terms are replaced by a special which recursively include the constructors of instances constant #. This prevents the chaining of variables that of the same class. In the general case, an attempt to cre- belong to different processes. This transformation does ate the instance of such a class leads to the construction not violate the soundness of the logic program in of an infinitely large number of processes and to mem- respect to its declarative semantics.
ory overflow. However, the use of suspending ports Flow messages are processed in the Actor Prolog in makes it possible to gradually construct new processes the following way. When the value of the common vari- as information arrives at the suspending ports of the able V that links the recipient process P to other pro- corresponding constructors. Thus, the Actor Prolog cesses is changed, the destructive assignment V := makes it possible to describe systems consisting of infi- NewValue is performed in the process P. The result of nite number of processes and create new processes as this operation is the repetitive proving of certain actors of the process P. In Fig. 2, we present the graphic sym-bols used to denote flow messages.
The ports which are neither protecting nor suspend- Common variables that connect processes are called ing are called plain (simple). In Fig. 3, we present ports. In our computational model, special means for graphic notation for different ports of processes.
controlling flow message transmission are introduced.
In our computing model, direct messages are asyn- The process can declare a certain value of the common chronous, as also are the flow messages. In the course variable protected. In this case, other processes are for- of execution of clauses of a process, it can call the pred- bidden to assign this variable the ordinary (unpro- icate of another process (i.e., send a direct message) by tected) values. A protected value of a common variable using special operations of sending direct messages: can only be replaced by another protected value. In the
Actor Prolog, the special keyword protecting is intro-
Target << predicate (A, B, …, C), duced for creating protected values of common vari-ables. The keyword is assigned to the definitions of Target <– predicate (A, B, …, C).
slots of class instances and also to the arguments of theconstructors of processes, i.e., Such an operation is always successful and does not affect the further execution of the sending process. The ((ClassName,…, protecting: attributeN=ValueN,…)).
sending of direct messages is suspended up to the com- Note that, in the case where the process passes to the pletion of the current phase of process execution and is state failed or unused, the flow messages transmitted by performed if and only if this phase is completed suc- it (including protected ones) are canceled. To do this, cessfully. In addition, the operations of sending direct special empty values are sent through all the ports of messages are canceled in the backtracking of the logic the process; these values can be further replaced by any protected or unprotected values by other processes.
The infix << denotes the co-called informational Another keyword, suspending, is used to declare
direct messages, and the infix <– denotes the switching the so-called suspending (switching off) ports: direct messages. These kinds of direct messages differ ((ClassName,…, suspending: attributeN=ValueN,…)).
Suspending ports serve for automatic passing of (1) As a result of processing of a switching direct processes in the unused state and for their automatic message, the process can become either proven or recovering from this state. When a special constant # or failed, while after processing of an informational direct PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS Fig. 4. Direct messages.
Fig. 5. Resident.
message, the process is always proven. If the execution of the function to its owner in the form of a protected of an informational direct message fails, this message is simply ignored and the process restores its former state.
The resident permanently observes the state of the (2) In contrast to switching direct messages, pro- assigned target process. After each change in the state cessing of informational direct messages is suspended of the target process, the resident repeats the construc- until the recipient process becomes proven. The sus- tion and sending of the list of values of the function. In pended messages are accumulated in the buffer.
addition, the resident can receive the information from In Fig. 4, we present the graphic notation used for its owner in the form of flow messages through the arguments of the corresponding atomic formula. When Note that the rules of processing flow messages cor- new values of arguments are received, the resident also respond to the rules of processing switching direct mes- performs the repetitive execution of the assigned func- sages considered above. Thus, the flow messages can tion and sends the collected information.
Figure 5 gives a graphic representation of the resi- In our computing model, the resident is a certain active entity observing the state of the assigned (target) 1.4. An Example of the Graphic Description process and sending the collected information to its owner. The owner of a resident is a certain process. Inthe Actor Prolog, the residents are defined via special Let us consider an example of the graphic descrip- tion of the Internet agent collecting data with the use ofthe Google and Rambler search engines. In Fig. 6, the slot = target_world ?? function (A, B, …, C).
functional diagram is presented. It uses the notation Such a formula can be assigned in the form of the argument of the constructor of the class instance or as a Process 1 performs the interaction with a user. It definition of a slot as a part of the class. In the general inputs the list of keywords and sends to Processes 2 and case, the following correspond to each resident of the 3 the switching direct message, which starts up the search process. Processes 2 and 3 interact with the cor- (1) The owner of the resident. The owner of the res- responding search engines and accumulate the received ident is the process that has created it.
addresses in local databases. The collected addresses (2) The atomic formula function(A, B, …, C). This are included into lists by residents and passed to Pro- formula denotes the call of a certain function (nondeter- cess 4 in the form of flow messages. Process 4 merges ministic in the general case) which must be executed in the lists of addresses and passes them to Process 5, the target process. The functions in the Actor Prolog are which performs additional filtering of the received ref- implemented with the help of the standard technique of erences. The necessary technique of checking Web pages is implemented in Process 6. Note that Process 6 (3) The target process of a resident, target_world.
passes itself into Process 5 via the flow message inorder that Process 5 uses it as a filtering instrument. The (4) A certain common variable slot. Using this vari- list of checked addresses is passed to Process 7, which able, the resident sends the collected information to its demonstrates the found addresses in the dialog box and makes it possible for the user to look through the found A resident automatically executes the assigned resources with the use of a standard Internet browser.
function in the search space of the target process. Theresident creates the list of all computed values of the In the next section, we consider the declarative function and then orders this list and deletes repeated semantics of the elements of the computing model out- elements. After that, the resident sends the list of values PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 Fig. 6. Graphic description of the Internet agent.
cesses of a program that has reached a successful final Model-theoretic semantics will be defined in the fol- The model-theoretic semantics of logic programs is lowing way. Below, we will define the scheme of trans- an important instrument evaluating the mathematical formations of an arbitrary concurrent logic program P strictness of implemented algorithms. Using the model- into a sequential program P', for which the existence of theoretic semantics, one can evaluate the following: the classical model-theoretic semantics is guaranteed.
(1) Soundness of algorithms. As will be shown The declarative semantics of the program P' will be below, the Actor Prolog ensures the soundness of pro- taken as the semantics of the source program P.
grams (including concurrent ones) with respect to their To construct the desired program P', we perform the model-theoretic semantics. Thus, we can be sure that the program will never compute (incorrect) values that (1) We remove from the text of the program P all do not belong to its model-theoretic semantics.
(2) Completeness of algorithms. Provided that cer- (2) We replace all the constructors of processes in tain conditions are fulfilled, we can guarantee the com- the text of the program by usual constructors of class pleteness of the logic program. This means that the pro- instances (that is, in the constructors of processes, we gram implements an exhaustive search and finds all replace double parentheses by ordinary ones). Thereby existing solutions of the posed problem. Unfortunately, the concurrent logic program will be transformed into a far from all logic programs are complete in respect to (3) We model the operation of suspending ports via An important merit of our computing model is the auxiliary predicates. For example, the behavior of the fact that it ensures the existence of classical (that is, process with the goal statement goal and two suspend- based on the first-order predicate logic) model-theo- ing ports x and y will be modeled by means of redefin- retic semantics of concurrent programs.
ing the goal statement. The new goal statement goal'will be defined in the following way:3 Definition 2.1. We say that the logic program has
attained its successful final state if (i) all the processes of the program are proven or unused, (ii) activation ofresidents is not required, and (iii) the processing of no messages by processes and residents is required.
Definition 2.2. The result computed by the program
3 In the Actor Prolog, the operator == corresponds to the ordinary is the values of common variables connecting the pro- PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS point of view of the declarative semantics, these mes- not x == #,
(6) We remove from the text of the program the key- words protecting.
(7) We have obtained a sequential object-oriented not y == #,
program. The object-oriented constructions of the Old goal statement.
Actor Prolog can be easily modeled in the pure Prolog The auxiliary predicate ground_term is nondeter- by simple renaming the predicates and adding certain ministic; it bounds the argument with all elements of auxiliary arguments. The detailed algorithm of such the Herbran universe. This predicate is necessary in transformations can be found in [22].
order to guarantee the correctness of using the state- As a result of transformations, we obtain the ment not at the given point of computations. In the gen-
sequential program P' in the pure Prolog with the not
eral case, this predicate outputs an infinite number of statement. The not statement is not used in the Actor
answers; therefore, this transformation can lead to infi- Prolog language. Thus, in the program P', the not state-
nite loop in the case where the standard control strategy ment is used only for modeling the special construc- of Prolog is used. However, at the moment, the only tions of the language considered above. Therefore, P' is thing that matters is the presence of the declarative stratifiable and, hence, possesses the classical model- (4) The operation of residents will be also modeled Definition 2.3. The model-theoretic semantics of
by redefining goal statements and auxiliary predicates.
the concurrent program P is the model-theoretic For instance, if the initializer of one of the slots is a con- semantics of the sequential program P' constructed structor of the resident of the form slot = target ?? func- tion(a, b, …, c), we redefine the goal statement goal of Theorem 2.1. A concurrent logic program is sound
in respect to its model-theoretic semantics.
Sketch of a proof. Considering the AND-tree of the program P in the course of transformations (1)–(7), one can verify that it can only decrease (at Step 1). Thus, the AND-tree of the program P' covers by no means lesssolutions than the program P. That is, the program P The operation of constructing the list of solutions cannot compute the solutions not covered by the pro- returned by the function function(A, B, …, C) will be gram P' (and, therefore, incorrect with respect to the implemented according to the following scheme: Of course, in the general case, the concurrent pro- gram P does not possess the completeness relative to its model-theoretic semantics. To ensure the complete- not is_element(Result, Results),
ness, it is necessary to impose constraints on the syntaxof the program.
setof(A, B,…, C,[Result | Results], Total); Theorem 2.2. The concurrent program P is com-
plete in respect to its model-theoretic semantics if we not has_another_solution(A, B,…, C, R),
(1) There are no nonlogic built-in predicates in the has_another_solution(A, B,…, C, Results) :- (2) Direct messages are not used. Information between processes is transmitted only via the flow mes-sages.
not is_element (Result, Results).
(3) The program does not get caught in an endless The auxiliary predicate is_element checks whether loop in the course of executing goal statements and the value Result is contained in the list. The auxiliary predicate sort puts the elements of the list in order andremoves the repeated elements. For sorting the ele- (4) The functions called by residents always return ments of the list, we use the lexicographic ordering.
The auxiliary predicate ground_term guarantees the (5) Predicates computing data which are then sent correctness of the use of the not statement.
by means of flow messages are deterministic.
(5) We remove all operations of sending direct mes- (6) Information is transmitted between processes sages from the text of the program. As was already along one-direction channels only. The unidirectional noted, direct messages in our model are strictly asyn- data transmission in the Actor Prolog can be modeled chronous and are always successful. Thus, from the by means of the keyword protecting.
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 (7) There is a partial ordering of processes exchang- achieve a real economic effect from using agents, it is ing information. That is, there is no recursive transmis- necessary to create technologies for programming sion of data between the processes and residents in the agents which would maximally facilitate and simplify the development of such programs by final unskilled (8) All values computed by processes and residents users. Ideally, the creation of the Internet agent must be which must be passed to other processes and residents as simple as the compilation of the query to the general- are ground (i.e., they do not contain unbound vari- purpose retrieval system. The developed methods and means of logic programming create necessary prerequi-sites for the solution of this problem. Based on the cre- Sketch of the proof. There are five possible reasons ated mathematical apparatus, the Actor Prolog, concur- for incompleteness of the concurrent program in rent object-oriented logic language, is developed (the respect to the declarative semantics. The first reason is definition of the language including all new features incompleteness of computations performed inside can be found on the site listed in [21]). In the recent ver- some process. To eliminate this reason, conditions (1) sions of the language, special means for supporting the and (3) are introduced. The second possible reason is development of the Internet agents were introduced: the impossibility to transfer the backtracking betweenprocesses. Conditions (5) and (6) guarantee that if a (1) predefined classes for getting information process has computed and passed a certain solution into according to HTTP and FTP Internet protocols; another process, then no other solution exists. There- (2) visual programming means including the trans- fore, the backtracking is not necessary since it all the lator of SADT diagrams into the concurrent Actor Pro- same would not help to find other solutions. The third log and the user interface management system based on possible reason for incompleteness is the replacement of unbound variables by the constant # during informa- (3) packages and other syntactic means necessary tion transmission between processes. Condition (8) for the implementation of the visual component-ori- removes this reason. The fourth reason is infinite com- putations which may arise in the course of programexecution. Such infinite loops of a program are pre- At present, we have implemented the operating pro- vented by conditions (3), (4), and (7). The fifth possible totype of the system of logic programming of Internet reason is the presence of several successful final states intelligent agents on the basis of the developed mathe- of a program. Specifically, the program can have sev- matical apparatus and the Actor Prolog language. The eral final states if (a) the direct messages with a gener- developed system makes it possible to create agents for ally unpredictable order of the processing are used in it; the retrieval and analysis of information on the Internet.
and (b) data are transmitted recursively and it is impos- The use of the object-oriented logic approach substan- sible to predict the order in which the processes related tially simplifies the creation of Internet agents and also by common variables will be executed. To prevent these their subsequent support and modification.
cases, we have introduced conditions (2) and (7),respectively. Therefore, provided that the enumeratedconditions (1)–(8) are met, the program will be com- plete in respect to the model-theoretic semantics.
The developed method of programming the Internet Thus, the concurrent computations in our model agents and the model of concurrent computations possess not only the operational but also the model-the- embodies several ideas, each of which must be consid- oretic semantics. The soundness of the program is guar- ered separately and compared with earlier approaches.
anteed, and, under certain conditions, the completenessof the program with respect to the model-theoreticsemantics is also guaranteed. This means, in particular, 4.1. Visual Programming of Internet Agents that the logic language can be used for writing concur- rent programs that perform an exhaustive search. This The idea of visual programming of Internet agents makes it possible to conclude that the developed model via functional diagrams was successfully realized ear- of concurrent computations and the concurrent object- lier by Mosconi and Porta [6]. They developed the oriented logic language implement the principles of VIPERS system [6] on the basis of a special kind of data logic programming mathematically strictly.
flow diagrams. As compared with our system of visualprogramming of Internet agents, the VIPERS systempossesses better graphic interface, but the blocks of dia- grams are implemented in the imperative language.
Thus, the VIPERS system does not support the declara- In the majority of cases, the tasks of collecting and tive semantics of Internet agents and does not ensure processing information which require automation with the mathematical strictness of procedures of search and the help of intelligent agents have individual character recognition of information in the dynamic Internet and are formulated by concrete users. Therefore, to PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS 4.2. Concurrent Programming of Agents putations is used in the OZ language [14] instead ofbacktracking.
The expedience of using the flow parallelism for the development of languages for programming Internet Our model can also be considered as the implemen- agents was also demonstrated in the WebL project of tation of the idea of speculative computations, since the Kistler and Marais [7] (on the basis of combinators synchronization of concurrent processes is not used in developed by Cardelli and Davies [8]), Webstream by the Actor Prolog. This means that, in our model of com- Hong and Clark [9], WebScript by Zhang and Keshav puting, concurrent processes never wait for data from [10], and information gathering plans by Barish and other processes and all computations performed by the Knoblock [11]. The listed languages are imperative program are in fact speculative computations. Thus, our and, thus, have the same drawback as the system model of computing is a mathematical basis for imple- menting speculative computations in multiagent sys-tems.
The logic programming languages for the Internet agents developed earlier, such as the concurrent Log-icWeb developed by Davison and Loke [5], W-ACE by Pontelli and Gupta [12], Jinni by P. Tarau [13], OZ [14]developed under the direction of G. Smolka, DLP The mathematical apparatus of logic programming developed by Eliens and de Vink [15], ObjVProlog-D of intelligent agents performing the search and recogni- by Malenfant, Lapalme, and Vaucher [16], etc. [4], tion of information in a complex structured dynamic ensure the existence of the declarative semantics of Internet environment is developed. The developed agents but do not support the modification of logic mathematical apparatus is based on the principle of the inference in the dynamic external environment and, repetitive proving of subgoals, which makes it possible therefore, do not ensure the mathematical strictness of to modify the logic reasoning during and after the exe- cution of logic programs by putting them in correspon-dence with the new information incoming from outside.
Based on the developed apparatus of modifiable rea- 4.3. Modifiable Reasoning in Multiagent Systems soning, we have created the Actor Prolog, concurrent As a promising approach to the logic programming object-oriented logic language, which ensures the cor- of Internet agents in the dynamic external environment, rectness of logic programs (intelligent agents) function- the use of nonclassical (and, in particular, nonmono- ing under conditions of permanent change and updating tonic logic systems) [3, 17, 18] is considered. We have chosen a principally different way, strictly adhering to The developed tools make it possible to create per- the formalism of classical first-order logic. In our sonal systems (agents) for gathering and analyzing model of computations, the modification of reasoning information on the Internet. The use of the object-ori- necessary for the correct logic interpretation of changes ented logic approach substantially simplifies the cre- in the external world is implemented via a special con- ation of Internet agents, as well as their subsequent sup- trol strategy of logic language based on the principle of port and modification. The developed approach sup- repeated proofs. This made it possible to mathemati- ports visual and component-oriented programming of cally strictly interpret the dynamic character of the Internet environment without loosing the expressiveand deductive properties of the classical first-orderpredicate logic. Note that our approach is free from the drawbacks of nonmonotonic logic systems, such as The author is grateful to Doctor of Physics and absense of general validity of deduced formulas (in the Mathematics Yu. V. Obukhov for help and support in classical sense), dependence of the result on the order implementing the project, to Academician Yu.I. Zhuravlev of application of the inference rules, and the high prob- and Professor V. A. Zakharov for fruitful discussions of ability of looping of logic programs.
the problem of describing the declarative semantics ofmultiagent systems, and also to Candidate of Physicsand Mathematics S. V. Remizov, who provided soft- 4.4. Speculative Computations in Multiagent Systems ware for debugging the prototype of the Actor Prolog.
One of the most interesting directions in the pro- gramming of agents is speculative computations. Usingthis principle for the control of the process of gathering data from the Internet, Barish and Knoblock [11] 1. Sadri, F. and Toni, F., Computational Logic and Multi- achieved a significant increase in Internet agent speed.
agent Systems: A Roadmap, 1999; available at The same idea at a higher level of abstraction was stud- http://citeseer.nj.nec.com/sadri99computational.html.
ied in the work of Inoue, Kawaguchi, and Haneda [19] 2. Huang, Z., Eliens, A., van Ballegooij, A., and and also in the work of Satoh and Yamamoto [20]. It de Bra, P., A Taxonomy of Web Agents, IEEE Proc.
should be also noted that the idea of speculative com- First Int. Workshop on Web Agent Systems and PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 Applications (WASA 2000), 2000; available at 15. Eliens, A. and de Vink, E.P., Asynchronous Rendez- http://wasp.cs.vu.nl/wasp/papers/wasa2000.ps.
Vouz in Distributed Logic Programming, in de Bak-ker, J.W, de Roever, W.P., and Rozenberg, G., 3. Eiter, T., Fink, M., Sabbatini, G., Tompits, H., Using Methods of Declarative Logic Programming for Intelli- Springer, 1993, pp. 174–203; available at http:// gent Information Agents, Theory and Practice of Logic Programming, 2002, vol. 2, no. 6, pp. 645–709; avail-able at http://arxiv.org/abs/cs.MA/0108008.
16. Malenfant, J., Lapalme, G., and Vaucher, J., 4. Davison, A., Logic Programming Languages for the ObjVProlog-D: Distributed Object-Oriented Pro- Internet, in Kakas, A. and Sadri, F., Eds., Invited Submis- gramming in Logic, Object Oriented Systems, 1996, sions for Computational Logic: From Logic Program- vol. 3, no. 2, pp. 61–86; available at http://compscinet.
ming into the Future, Springer, 2001; available at dcs.kcl.ac.uk/OO/PDFPapers/oo030202.pdf.
http://fivedots.coe.psu.ac.th/~ad/papers/summBob.ps.gt.
17. Alferes, J.J. and Pereira, L.M., Logic Programming 5. Davison, A. and Loke, S.W., A Concurrent Logic Updating: A Guided Approach, in Kakas, A. and Programming Model of the Web, Tech. Rep. 98/23, Sadri, F., Eds., Computational Logic: From Logic Pro- Department of Comput. Sci., Univ. of Melbourne, gramming into the Future, Essays in Honor of Robert Kowalski, Springer, 2002, vol. 2, pp. 382–412; available http://www.cs.mu.oz.au/tr_submit/test/tr_db/mu_TR_ at http://citeseer.nj.nec.com/alferes02logic.html.
18. Dix, J., Furbach, U., and Niemelae, I., Nonmonotonic 6. Mosconi, M. and Porta M., A Visual Approach to Inter- Reasoning: Towards Efficient Calculi and Implementa- net Applications Development, Proc. 8th Int. Conf. on tions, in Voronkov, A. and Robinson, Eds., Handbook of Human–Computer Interaction (HCI’99), Munich, Automated Reasoning, Elsevier, 2001, vol. 2, ch. 18, 1999, vol. 1, pp. 600–604; available at pp. 1121–1234; available at http://www.cs.man.ac.uk/~ http://vision.unipv.it/research/papers/99p-webappl/ 19. Inoue, K., Kawaguchi, S., and Haneda, H., Controlling 7. Kistler, T. and Marais, H., WebL—A Programming Speculative Computation in Multiagent Environments, Language for the Web, Elsevier, 1998, pp. 259–270; Proc. Second Int. Workshop on Computational Logic in available at http://gatekeeper.research.
Multiagent Systems (CLIMA-01), 2001, pp. 9–18; available compaq.com/pub/DEC/SRC/technical-notes/SRC-1997- at http://citeseer.nj.nec.com/inoue01controlling.html.
20. Satoh, K. and Yamamoto, K., Speculative Computations 8. Cardelli, L. and Davies, R., Service Combinators for with Multiagent Belief Revision, Proc. First Int. Joint Web Computing, Software Engineering, 1999, vol. 25, Conf. on Autonomous Agents and Multiagent Systems, no. 3, pp. 309–316; available at http:// Bologna, ACM Press, 2002, pp. 897–904; available at citeseer.nj.nec.com/cardelli97service.html.
http://agents.umbc.edu/papers/satoh.pdf.
9. Hong, T.W. and Clark, K.L., Concurrent Programming 21. Morozov, A.A. and Obukhov, Yu.V., Actor Prolog: The on the Web with Webstream, Tech. Rep., Department of Definition of the Programming Language, Preprint of Computing, Imperial College, 2000; available at Inst. of Radio Engineering and Electronics, Russ. Acad. http://www-lp.doc.ic.ac.uk/~klc/webstream.html.
Sci., Moscow, 1996 no. 2(613); the new version of the 10. Zhang, Y. and Keshav, S., WebScript—A Scripting definition of the language is available at our site Language for the Web, Tech. Rep., Cotrnell CS Tech.
http://www.cplire.ru/Lab144/index.html.
22. Morozov, A.A., Logic Analysis of Functional Dia- http://www.research.att.com/~yzhang/papers/webscript- grams in the Process of Interactive Design of Infor- mation Systems, Cand. Sci. (Phys.-Mat) Disserta- 11. Barish, G. and Knoblock, C.A., Speculative Execution for Information Gathering Plans, Proc. 6th Int. Conf. on http://www.cplire.ru/Lab144/auto.html.
AI Planning and Scheduling (AIPS-2002), Toulouse, 23. Morozov, A.A., Actor Prolog: An Object-Oriented 2002; available at http://www.isi.edu/info- Language with the Classical Declarative Semantics, Proc. IDL’99 Workshop, Paris, 1999; available at 12. Pontelli, E., Gupta G., ACE: A Logic Language for http://www.cplire.ru/Lab144/paris.pdf.
Intelligent Internet Programming / Department of 24. Morozov, A.A., Obukhov, Yu.V., and Gulyaev, Yu.V., Comput. Sci., New Mexico State Univ., Las Cruces, On The Problem of Using Logic Object-Oriented Pro- 1997; available at http://www.cs.nmsu.edu/lldap/ gramming in the World Wide Web, Proc. Special Rus- sian Session “The Internet Development in Russia”, 13. Tarau, P., Jinni: Intelligent Mobile Agent Program- First IEEE/Popov Workshop on Internet Technol. ming at the Intersection of Java and Prolog, Proc. of and Services, Moscow, 1999, pp. 54–59; available at PAAM’99, London, 1999; available at http:// http://www.cplire.ru/Lab144/internet.pdf.
citeseer.nj.nec.com/tarau99jinni.html.
25. Morozov, A.A. and Obukhov, Yu.V., On the Problem of 14. Smolka, G., The Oz Programming Model, in van Leeu- Logical Recognition in the Dynamic Internet Environ- wen J., Ed., Computer Science Today, LNCS 1000, ment, Pattern Recognit. Image Anal., 2001, vol. 11, Springer, 1995, pp. 324–343; available at http:// www.mozart-oz.org/papers/abstracts/volume1000.html.
http://www.cplire.ru/Lab144/pria5.pdf.
PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003 LOGIC OBJECT-ORIENTED MODEL OF ASYNCHRONOUS CONCURRENT COMPUTATIONS 26. Morozov, A.A. and Obukhov, Yu.V., An Approach to Aleksei A. Morozov. Born 1968.
Logic Programming of Intelligent Agents for Searching and Recognizing Information in the Internet, Pattern Rec- ognit. Image Anal., 2001, vol. 11, no. 3, pp. 570– 582; available at http://www.cplire.ru/Lab144/pria570m.pdf.
degree in Physics and Mathematics in1998. Senior Researcher at the Insti- 27. Morozov, A.A., On Semantic Link Between Logic, Object-Oriented, Functional, and Constraint Pro- gramming, Proc. MultiCPL Workshop, Ithaca, USA, 2002; available at http://www.cplire.ru/Lab144/ PATTERN RECOGNITION AND IMAGE ANALYSIS Vol. 13 No. 4 2003

Source: http://www.cplire.ru/Lab144/pria640.pdf