Synergy : A Conceptual Graph Activation-Based Language
INSEA,
Fax : (212) 7 77 94 57
akabbaj@insea.ac.ma
Abstract. This paper presents the core of Synergy; an implemented visual multi-paradigm programming language based on executable Conceptual Graph (CG). Execution is based on a CG-activation mechanism for which concept lifecycle, relation propagation rules and referent instantiation constitute the key elements. In this paper we define the activation mechanism and the CG structure (concept, relation, context, co-reference) used in Synergy as well as the concept type definition, the encapsulation mechanism and the knowledge base of Synergy. Examples are given to illustrate some aspects of the language. Hybrid object-oriented and concurrent object-oriented use of Synergy are presented in other papers [9, 10].
Note: This paper has been
published in ICCS’99 Proceedings by Springer-Verlag:
1 Introduction
Conceptual Graph (CG) theory is proposed by Sowa [18, 19] as a graphic system of logic and recently as a CG Interchange Format (CGIF) [21]. In [19], Sowa notes that many popular diagrams (e.g., type hierarchies, dataflow diagrams, state-transition diagrams, Petri-Nets, etc.) can be mapped to CG and in [20] he proposes CG as a logical foundation for object-oriented systems. Thus, CG is presented by Sowa as a formalism for the representation of knowledge (both declarative and procedural) with a logical interpretation; execution should be done with proof techniques of logic using rules of inference. Other CG execution mechanisms have been proposed in literature [1, 3, 4, 7, 13, 14, 15, 16].
In [7, 8] a CG activation-based mechanism is proposed as a computation model for executable conceptual graphs. Unlike the other proposed mechanisms, our CG activation mechanism has been used to produce an implemented CG general-purpose programming language.
Activation-based computation is an approach used in visual programming, simulation and system analysis where graphs are used to describe and simulate sequential and/or parallel tasks of different kinds : procedural, process, functional, event-driven, logical and object oriented tasks [2, 11, 12, 17, 23, 24].
Activation-based interpretation of CG [7, 8] is based on concept lifecycle, relation propagation rules and referent instantiation. A concept has a state (which replaces and extends the notion of control mark used by Sowa [18]) and the concept lifecycle is defined on the possible states of a concept. Concept lifecycle is similar to process lifecycle (in process programming) and to active-object lifecycle (in concurrent object oriented programming), while relation propagation rules are similar to propagation or firing rules of procedural graphs, dataflow graphs and Petri Nets [8].
Since 1995, we have designed and implemented a visual language, called Synergy that is based on such an activation mechanism. Synergy is a visual multi-paradigm programming language; it integrates functional, procedural, process, reactive, object-oriented and concurrent object-oriented paradigms. The integration is done using CG as the basis knowledge structure, without actors or other external notation.
Synergy is designed for visual programming, modeling and simulation. It can be used for different purposes and in many fields : programming languages, simulation, database, information systems, software engineering, knowledge acquisition, knowledge base systems, intelligent tutoring systems and multi-agent systems. Synergy has been used for the development of a concurrent-object oriented application (e.g., a visual agent-oriented modeling of the Intensive Care Unit) and in modeling some components of an intelligent tutoring system [9]. It has been used also for the specification of a multi-agent system [25]. A hybrid object-oriented use of Synergy is illustrated in [10].
The Synergy language constitutes the main part of the SYNERGY environment [8] ; a CG tool composed of a CG graphic editor, the Synergy language, an engine for dynamic formation of knowledge bases and an information retrieval process [8]. The Synergy language and its environment have been implemented with Microsoft Visual C++ and a Visual J++ implementation will be available in summer 1999. The web SYNERGY site (www.insea.ac.ma/InseaCGTools/Synergy.html) is under construction and a SYNERGY group is being formed to enhance, extend and use SYNERGY in many ways.
This paper presents the core of the current version of Synergy. Section 2 defines the notion of Synergy application (e.g., a Synergy program) and the CG structure used in Synergy. It introduces also and briefly the primitive operations of the language. Section 3 introduces type definitions and encapsulation that enables the definition of a modular knowledge base. The use of co-references in Synergy is introduced in section 4. Section 5 describes the CG activation mechanism of Synergy and its interpreter; how CGs are executed. Concept lifecycle and relation propagation rules are introduced in this section. As an illustrative example, section 6 presents an application in project management. Finally section 7 gives a conclusion with an outline of some current and future works.
2 The basic elements of Synergy
Definition 1. An application (e.g., a program) in Synergy is represented as a CG with two concepts/contexts : [LongTermMemory] and [WorkingMemory]. The description of the first context represents the knowledge base (KB) of the application and the description of the second represents the working space where the user specifies his requests. A Request is represented by a CG and it is interpreted or executed according to the content of the KB and to the primitive types (built-in) hierarchy.
Definition 2. The context [LongTermMemory] contains the knowledge base (KB) of a Synergy application which is represented by a CG. The KB corresponds to concept types hierarchy augmented by type definitions, individual specification, types schemas and types synonyms.
In this paper, we consider a KB composed of concept types hierarchy with only type definitions and individual specifications. The KB of a new application will contain only the concept [Universal]. Using the CG graphic editor of SYNERGY, the user can add new concept types with their definitions eventually. Fig. 1 shows the new application “Sample1.syn” with the content of its [LongTermMemory] (e.g., its KB) after the addition of some concept types with definitions of some of them (like [BscProc :_BasicProcedures] and [Factorial :_Fct]).
To have a concise KB, a Synergy KB (for instance, the KB in Fig. 1) contains only the information given by the user, the primitive types are kept apart in the primitive types (built_in) hierarchy.
Definition 3. A CG in Synergy is a set of concepts related eventually by dyadic relations.
Fig. 1 illustrates different cases of CG : a) the top-level description of an application (like “Sample.syn”) is a CG composed of two concepts without relations, b) the contain of the context [LongTermMemory] is a connected CG (which represents the KB) and c) the definition of “Factorial” contains a connected CG with three unconnected concepts.
Definition 4. A concept is described by four fields :
[Type :Referent =Description #State]. The referent, if specified, can be an identifier of an instance, a variable identifier (that can be bound to a referent) or a co-referent. A description, if specified, can be a simple data (for example, a real, a boolean or a string) or a composed data (a CG). The state field is defined on the following set : {steady, trigger, check-preconditions, wait-preconditions, wait-value, in-activation, wait-affectation, wait-end-affectation}.
Remarks: Nothing is really specific to Synergy in definition 4 ; the description field of a concept is already used by Sowa [19, 20], Esch [5], Ellis [4] and others. The state field can be viewed as a generalization of the control mark introduced by Sowa in [18].
Remark. As illustrated by Fig. 1, the CG graphic editor of SYNERGY represents a concept by a rectangle. To have a concise description of a CG, a relation is not encircled with a circle and the description and the state of a concept are hidden. They are shown as required by the user. An iconic indication is given however : if the concept has a description, a small triangle is shown at the left-bottom of the rectangle. If the description is a CG then the surface of the triangle is red and it is blue if the description is a simple data (unfortunately the colors are not printed !). Also, each state of a concept has a visual representation. For instance, the rectangle is green if the concept state is “trigger” and it is red if the state is “in_activation”.
Fig. 1. The “Sample1.syn” application.
The type of a concept can be a primitive type, specified in the Synergy primitive types hierarchy, or it can be a defined type, specified by the user in the KB of the application. A concept type definition is considered in section 3.
Definition 5. The primitive concept types hierarchy is composed of primitive data types (“Int”, “Real”, “String”, “Bool”, “CG”, “Image”, “Sound”, “Video”, “Text”, “Window”) and primitive operation types (assignation, I/O, arithmetic, relational, boolean, list, CG, type_hierarchy, concept, relation and Multi-Media) :
- A list is represented as a CG and list operations manipulate the CG as a list of elements.
- CG operations correspond to “ExpandConcept”, “ContractDef” and to the generic operation “MatchCG” and the derived ones (Project, Subsume, Unify, MaximalJoin, Specialize, Generalize and other variants). CG operations are defined on simple and compound CG with co-referents.
- Type_hierarchy operations are “IsSuperTypeOf”, “MinimalCommonSuperType” and “MaximalCommonSubType”.
- Concept operations are subdivided in two categories : operations that have an access to a specific field of a concept (especially the type, the referent or the state fields like the operations “GetType”, “SetType”, “GetState” and “SetState”) and operations that delete or add a new concept to a given CG.
- Relation operations correspond to delete or to add a new relation between two concepts of a given CG.
- Multi-Media operations : the Visual C++ implementation of these operations is based on a subset of the Microsoft device-independent “Media Control Interface” (MCI). With these operations, Synergy enables the user to create multi-media applications. We are considering the implementation of these operations with Visual J++.
Beside the primitive data and operation types, Synergy provides a set of “primitive” relations, called the Synergy-Relation-Set (SRS) = {“in”, “out”, “grd”, “next”, “sp”, “inst”, “sta”, “synm”}.
Definition 6. A relation between two concepts can be either an element of the Synergy-Relation-Set (SRS) or it can be an identifier provided by the user. The primitive relations “in”, “out” “grd” (guard) and “next” are data/control relations and the primitive relations “sp” (specializationOf/generalizationOf), “inst” (instanceOf), “sta” (situationFor) and “synm” (synonymOf) are “knowledge base relations”; they are used to organize a KB of a Synergy application.
Note : in each of the following statements, C and C’ represent respectively the source and the target concepts of the relation in question.
C —in® C’ : C is an input argument for C’.
C —out® C’ : C has C’ as an output argument.
C —grd® C’ : C is a precondition for the execution of C’.
C —next® C’ : After the execution of C, execute C’.
C —sp® C’ : the type of C’ is a sub-type of the type of C and the description of C’ is
a specialization of the description of C. The two descriptions represent the
definition bodies of the types of the two concepts.
C —inst® C’ : C’ represents a specific referent of the type of C.
C —sta® C’ : C’ represents a situation (e.g., a schema) for the type of C.
C —synm® C’ : C’ represents the list of synonyms for the type of C.
C —R[,a]*® C’ : R represents a data/control relation (“in”, “out” or “grd”) and a is either “f” the functional attribute, “/” the cut_forward_propagation attribute or, “\” the cut_backward_propagation attribute. R[,a]* means that the relation R can have zero-to-many (three) of the above attributes (for instance, C —in,f,/® C’ means that C’ will consume the description of C –according to the semantic of the functional attribute– and that the computation of a new value for C will not trigger C’ –due to the presence of the cut_forward_propagation “/” attribute–).
Multiple-assignment and procedural interpretation of “in”, “out” and “grd” relations are considered by default in Synergy : for instance, with C1—in®C2 or C3—grd®C4, the concept C2 (or C4) will consult the description of C1 (or of C3 for C4) without consuming it. Also, with C5—out®C6, C5 can assign a new description (value) to C6 even if this later has already one.
Functional interpretation of the above three relations will be adopted however if the user post-fixes the relation name with the optional functional attribute “f” : with C1—in,f®C2 or C3—grd,f®C4, the concept C2 (or C4) will consult the description of C1 (or of C3 for C4) and consume it. And with C5—out,f®C6, C5 can assign a new description to C6 only if C6 has not one, otherwise C5 will wait for the consumption of C6 description.
Fig. 1 illustrates the use of the relation “sp” to describe the KB and the use of data relations (“in” and “out”) to relate input and output arguments to the corresponding operations. For instance, the definition of the operation [Dec :_Decrement] contains a call to the primitive operation [-] which has two inputs and one output arguments. Data and control relations are illustrated more fully in section 6.
3 Concept type definition and encapsulation
Definition 7. Concept type definition “type Type(_x) is CG” is represented in Synergy as a concept : [Type :_x = CG]. The concept type with its definition should be added to the KB of the application and it should be related to its super-type(s) with the relation “sp”.
Fig. 1 gives the definition of three types : “BscProc”, “Dec” and “Factorial”.
If the defined type represents a treatment, then the user should specify the concept [Operation :super] or [Process :super] in its definition to indicate how the type should be interpreted. For instance, the types “Factorial” and “Dec” in Fig. 1 are defined as a kind of operation (e.g., once the operation terminates its execution, its description is destroyed as the case for the “record activation” of a procedure in procedural programming. This is not the case however if the treatment is defined as a process).
Also, if a concept type represents a treatment with arguments, then the corresponding parameters should be specified in the definition of the type. The type “Factorial” for instance (Fig. 1) has one input parameter ([Int: in|_X]; its referent is prefixed with “in|”) and one output parameter ([Int :out|_R]; its referent is prefixed with “out|”).
Synergy enables the user to define new concept types and moreover, the type can be defined in the context of another type definition. Fig. 1 shows an example: the operations [If] and [Dec] are defined in the context [BscProc].
Definition 8. Encapsulation/Modularity principle is incorporated in Synergy by allowing a concept type to be defined in the context of another concept type definition.
Such a contextual definition of a concept type has been proposed and used by Sowa [20] to model object-oriented encapsulation principle. The same use of context is done in Synergy, for both object-based and object-oriented programming. The encapsulation principle is very relevant to the efficient organization of a KB; very often “auxiliary” concept types are defined only to enable an abstract definition of other concept types. Those auxiliary types should be encapsulated to allow for a more concise KB. With definition 8, Synergy provides such a possibility.
Definition 8 above leads to the following extension in the formulation of a concept type :
Definition 9. The type of a concept can be simple, of the form “Id” where “Id” is the identifier of a primitive or defined type, or it can be composed, of the form “Id1.Id2” where “Id1” is either a type identifier or an instance identifier, and “Id2” a type identifier. If “Id1” is a type identifier then “Id2” is defined in the context of “Id1” definition. If “Id1” is an instance identifier then “Id2” is defined in the class of the instance “Id1”.
In the definition of “Factorial” (Fig. 1), the concept [BscProc.If] has a composed type, e.g., the type “If” is defined in the context [BscProc]. Composed type “Id1.Id2” where “Id1” is an instance identifier concerns message or method call and it is considered in [10].
4 The use of co-reference in Synergy
In the CG theory, the pair (*x, ?x) shows a co-reference link between co-referent concepts : the concept with referent “*x” indicates the first occurrence or the defining node of the variable x while a concept with referent “?x” is a bound node and it indicates a subsequent reference to the concept where the variable is defined [19, 20]. In [5] Esch notes that “the basic thing to remember about contexts and co-reference is that it closely models scope of variables in block structured languages”. This remark is especially true for Synergy and as discussed below, it is extended to other situations.
In Synergy, the pair (x, x.) is used instead of (*x, ?x). For instance, the concept [Employee : Employee2] is the defining concept for the referent “Employee2” while the concept [Employee : Employee2.] is a reference concept.
Synergy provides an extended form of co-reference called composed co-reference : the concept [String : Employee2.Address.Zip] (e.g., a reference to the “Zip of the Address of Employee2”) is a reference to the defining concept of the referent “Zip” which is (or should be) contained in the description of the defining concept of the referent “Address” which is (or should be) itself contained in the description of the defining concept of the referent “Employee2”.
A composed co-referent, like “Employee2.Address.Zip” is similar to the composed identifier in Pascal for example (e.g., Employee2.Address.Zip : Zip could be a field of the record Address which is a field of the record Employee2).
Definition 10. A co-referent can be simple, of the form “
The example of section 6 illustrates the use of composed co-referents. A more detailed illustration is given in [7, 8, 9, 10] where composed co-referents are used in the context of object-oriented and concurrent object-oriented applications.
Composed co-referent is an important feature specific to Synergy. It enhances the expressive power of the language and it enables the specification of a reference to a concept that is not present at the specification time. A simple or composed co-referent in Synergy specifies how to determine at the execution time the defining concept. Co-referent resolution procedure interprets the co-referent identifier to establish, at the execution time, the co-reference link. Co-referent resolution is described in [8, 10].
5 The CG activation mechanism and the interpreter of Synergy
Interpretation in Synergy is based on CG or context activation. Indeed, initially the Synergy interpreter starts with the interpretation of the working memory context [WorkingMemory]; the first active context. This latter contains the user requests.
Context activation or interpretation corresponds to the interpretation of its description ; the activation of a CG (which could be set of CGs). CG activation begins with the parallel interpretation of some concepts of the CG, then data and control relations (if they are present) spread or propagate the activation through the graph. Interpretation of a concept is done according to its lifecycle while the spreading activation is conform to the relations propagation rules.
We explain briefly the notion of parallelism in Synergy and then we define the notions of concept lifecycle and relations propagation rules.
Parallelism and the Synergy interpreter
As noted above, the activation of a context
involves parallel activation of some
of its concepts, each concept is activated according
to its lifecycle. Thus, the interpreter
has to simulate a parallel interpretation of concept lifecycles.
More specifically, a concept can represent a primitive operation or a context. Hence, the Synergy interpreter should manage the parallel activation of several contexts and/or the execution of several primitive operations.
The association of a state to a concept is the main reason that makes such a parallelism possible. In effect, each concept is interpreted (e.g., evolves, changes) according to its lifecycle, the activation (or interpretation) of the context is thus decentralized.
As a parallel language, Synergy enables the user to write parallel programs, its interpreter is able to execute those programs and its graphical environment allows the user to see and debug the parallel activation of those programs. This “conceptual parallelism” is at the design/language level. It can be implemented on a parallel machine (e.g., “physical parallelism”) or it can be interpreted and simulated on a sequential machine. In our current implementation of Synergy, we have considered the second option. Of course, some constraints have been assumed, especially for parallel execution of primitive operations. For instance, we assumed that during the execution of a primitive, no interaction could occur between the primitive and the other parts of the Synergy “program”.
Concept lifecycle
Concept lifecycle is a state transition diagram where states correspond to the possible states of a concept and transitions to the conditions/actions on the concept and on the data/control relations linked to the concept.
The concept C in the “trigger” state is asked to “determine its description and to execute it”. The concept C can have already a description, or (if not) its type is defined and in this case the description will be determined by instantiation, or its type is a primitive operation type. If none of these possibilities hold, the interpreter will attempt to compute the description by backward propagation (through the “out” relation) and the concept C becomes at state “wait-value”.
Once C has a description or its type is a primitive operation type, its state changes in general from “trigger” to “check-preconditions”; the state where the concept C checks its preconditions (e.g., C’ is a precondition for C if : C’ —in® C or C’ —grd® C). A concept C’ that represents a precondition for the concept C can be triggered (by backward propagation through the “in” or “grd” relation) and C changes its state to “wait-preconditions”.
If all the pre-conditions are satisfied, C becomes at state “in-activation” and its description is executed. If the type of C is a primitive operation then the primitive is executed, if the description of C is a CG then the CG is executed (in parallel to other active CGs), if the description is a primitive data (like an integer or a string) then its execution is null.
Once the concept C terminates its execution, its state changes to “wait-affectation” if it has results to affect to the corresponding output arguments. After the affectation step, the concept C returns to the “steady” state.
A more detailed description of concept lifecycle is given in [8].
Data/control relations propagation rules
Relation propagation rules apply only to data and control relations as well as co-reference link (viewed as a “virtual” data relation between a bound node C1 and its defining node C2 : C1 –coref® C2).
A data/control relation can propagate a state forward (from the source to the target concept of the relation) and/or backward (from the target to the source of the relation).
Forward propagation rule. If an active context contains a branch C1 –Rel® C2 where the state of C1 is “trigger” and Rel Î {"in", "out", "next", "coref"} then the relation Rel will propagate forward the state “trigger” to the concept C2.If Rel = “grd” then the propagation will be done only if the description of C1 is different from “false”.
Backward propagation rule. If an active context contains a branch C1 –Rel® C2 where the state of C2 is “trigger” and Rel Î {"in", "out", "grd", "coref"} then the relation Rel will propagate backward the state “trigger” to C1 if one of the following conditions is satisfied :
- Rel = "in" and the type of C2 is a strict activity (e.g., C2 description can be executed only if all its input arguments have a description) and C1 is at state “steady” and it hasn’t a description.
- Rel = "out" or "coref" and C2 hasn’t a description, its type isn’t a primitive operation and it isn’t defined (e.g., its description cannot be determined by instantiation).
- Rel = "grd" and C1 is at state “steady” and it hasn’t a description.
Forward and backward propagation role of a relation Rel can be inhibited by the optional attribute “cut_forward_propagation; /” (“Rel,/”) or “cut_backward_ propagation, \” (“Rel,\”). For instance, if an active context contains C1 –in,/® C2 and the concept C1 is at state “trigger” then the relation “in,/” will not propagate the state “trigger” to the concept C2.
With the optional attributes “/” and “\”, the user can control the propagation of concepts activation in a CG. This is similar to the use of the “cut” to control the backtracking in the PROLOG language.
A more detailed description of CG activation and
the Synergy interpreter is given in [8].
6 An example : a method for project schedule
To improve the skills and techniques for project management, Spinner [22] presents a method for developing the project schedule. We describe briefly this method and then its implementation with Synergy. Several features of the core of Synergy are illustrated by this example : data and control relations, co-references, operation treatment, process treatment and lazy treatment, forward and backward activation and other features.
Project schedule is based on the specification of the project network which describes the dependence between several activities. Each activity is associated to an arc and it has two attributes : the “time estimate” for the activity (which is given) and the “total float” which is computed. Each node of the network is described by two attributes too: the “earliest start time” and the “latest finish time” which are also computed, except for the earliest start time of the first node.
The first step of the method is to calculate the timing of each activity : compute for each node the earliest start and the latest finish times. The computation of the earliest start time (identified later by Erlst_st) for each node N is defined as follows :
If the node N is the
target of only one arc : M –ActivityM® N Then
N.Erlst_st :=
M.Erlst_st + ActivityM.TimeEstimate; /* TimeEstimate of ActivityM */
Else N.Erlst_st :=
Maximum((M1.Erlst_st + ActivityM1.TimeEstimate), …,
(Mj.Erlst_st + ActivityMj.TimeEstimate)); /* we
consider all the predecessor nodes of N */
The value of the earliest time (Erlst_st) attribute of a node depends on the values of the Erlst_st attributes of the predecessor nodes. Hence, with a kind of forward propagation starting from the first node, the Erlst_st attribute of each node can be computed. The computation of the latest finish time (Ltst_ft) attribute of each node is defined as follows :
If the node N is the
end node of the network Then
N.Ltst_ft := N.Erlst_st
Else If the node N is the
source of only one arc : N –ActivityM® M Then
N.Ltst_ft := M.Ltst_ft
- ActivityM.TimeEstimate;
Else N.Ltst_ft := Minimum((M1.Ltst_ft
- ActivityM1.TimeEstimate), …,
(Mj.Ltst_ft
- ActivityMj.TimeEstimate)); /* we consider all the
successor nodes of N */
The value of the latest finish time (Ltst_ft) attribute of a node depends on the values of the Ltst_ft attributes of the successor nodes. With a kind of forward propagation starting from the end node, the Ltst_ft attribute of each node can be computed. Note that the value of the Ltst_ft of the end node corresponds to the value of its Erlst_st attribute.
Thus, the first forward propagation should be done first, to compute the Erlst_st of each node and then the second forward propagation should follow to compute the Ltst_ft attribute as well as the “total float” of each activity M –Activity® N : N.Ltst_ft - M.Erlst_st.
Our approach in the implementation of this method is to incorporate this latter in the project network so that the network could perform itself the steps of the method.
To perform the two forward activation of the project network, we introduce a process P as indicated in Fig. 2.
Fig. 2. A simple project network that incorporates directly, thanks to the process P, the Spinner method. In this Fig., activity DPS stands for “Design Pump System”, WrtSpec for “Write Specifications” and InstSyst for “Install System”.
During the first forward activation of the network, the process P will take as inputs the Erlst_st attribute of a node Nj (Nj « P « Nj+1) and the TimeEstimate of the corresponding activity to compute the Erlst_st attribute of Nj+1. And during the second forward activation of the network, P will take as inputs the Ltst_ft attribute of Nj+1 and the TimeEstimate of the corresponding activity to compute the Ltst_ft attribute of Nj and then to compute the TotalFloat attribute of the activity.
The first forward activation is triggered by the value of the Erlst_st attribute of the first node N1 and the second forward activation is triggered by the value of the Ltst_ft attribute of the end node which is equal to the value of its Erlst_st attribute.
Fig. 3 shows the KB (knowledge base) of the Synergy application that implements the above approach. The type “Node” is defined as an abstract entity with two attributes (the concept [Int: Erst] which represents the Erlst_st attribute and the concept [Int: Lft] which represents the Ltst_ft attribute). A similar definition is given for the type “Job” with its two attributes (the attribute TimeEstimate represented by the concept [Int: Etm] and the attribute TotalFloat represented by the concept [Int: TFlt]).
Fig. 3 shows also the description of the simple project network of Fig. 2 ([Project_Network: ProjNetwork1] in Fig. 3). The network is represented as a CG and the abstract bi-directional link used in Fig. 2 («) is replaced by the detail of the connection; connections between the process P and its arguments.
Fig. 3. Formulation in Synergy of the Project Network of Fig. 2
Let us consider now the definition of the process P (Fig. 4). P should be defined as a lazy process :
- P should be a process : the same description of [P] could be executed twice; in the first and the second forward steps. Thus, the description of [P] should not be destroyed after its first execution. This process interpretation will be adopted for a concept [P] since the definition of its type contains the concept [Process: super] (Fig. 4).
- P should be a lazy process : P does not need all its input arguments and should not wait for all their values to start its execution. In fact, only some input arguments (the two first) will be used in the first execution while others (the second and the third input arguments) will be used in the second execution. Since the definition of the type “P” contains the concept [Lazy: super], the Synergy interpreter will adopt a lazy evaluation for a concept [P]; once triggered by an argument, [P] can begin its execution without asking and waiting for the values of its input arguments.
The process P plays two roles (see its definition in Fig. 4) :
- If it is triggered by the forward propagation from its first input argument (which corresponds to its parameter [Int: in1|_N1Erst]), then only the left part of its description will be executed ! Indeed, the state of the concept [Int: in1|_N1Erst] will be propagated to the concept [CT] through the relation “in3” (Fig. 4). Note that the state of [Int: in1|_N1Erst] will not be propagated to the concept [Ms] through the relation “in2,/” because this latter has the “cut_forward_propagation” attribute “/”. The activation of the triggered [CT] will involve the computation of the value of the output parameter [Int: out1|_N2Erst] (Fig. 4). No other activity or animation will exist in the description of [P] in this case. Thus, after the termination of the activated [CT], the activation of [P] will terminate too.
- If it is triggered by the forward propagation from its third input argument (which corresponds to its parameter [Int: in3|_N2Lft]), then the left part of its description will not be considered ! Indeed, the state of the concept [Int: in3|_N2Lft] will be propagated to the second concept [CT] through the relation “in3” and to the concept [Ms] through the relation “in1” (Fig. 4). The parallel activation of [CT] and [Ms] will involve the computation of the values of [Int: out2|_N1Lft] and [Int: out3|_JbTFlt].
Let us consider now the type “CT” (Fig. 4). “CT” is called twice in the body of the process P (Fig. 4): CT(“>”, “+”, _N1Erst, _JbEtm, _N2Erst) and CT(“<”, “-”, _N2Lft, _JbEtm, _N1Lft). The operation/type CT has two operations/types as arguments. A pseudo-code definition of the operation CT can be expressed as follows :
define CT(in
Type:_SupInf,
Type: _PlusSubst, Int:_X, Int: _Y;
inout Int: _Z)
is begin
Int Tp := _X _PlusSubst
_Y; /** the value of _PlusSubst is either “+” or “-”
**/
If (Tp _SupInf _Z) Then
_Z := Tp; /** the value of _SupInf is either “>”
or “<” **/
end;
Fig. 4 gives a Synergy reformulation of the above pseudo-code for the definition of the type “CT”. We use the Synergy primitive operation “SetType” to implement the possibility of modifying the type of a concept at the execution time (for instance, to change the type of [Action] with the type “+” or “-”).
Fig. 4. The Project Schedule application (suite)
Now that the specification in Synergy of the project schedule application was given, let us follow its use (e.g., its execution). To initiate the activation of the project network, the request composed of the concept [Project_Network :ProjNetwork1. #?] should be added to the context [WorkingMemory].
The concept [Project_Network :ProjNetwork1. #?] is a reference to the description of the individual “ProjNetwork1” (Fig. 3). Being at state “trigger; ?”, this concept will be considered by the Synergy interpreter (once activated). The first action concerning the interpretation of the concept [Project_Network:ProjNetwork1. #?] is to resolve the co-reference “ProjNetwork1.”. Since no concept with the referent “ProjNetwork1” exists in the current context ([WorkingMemory]), the search will continue in the “father” context (in this case [LongTermMemory]). This context contains the required concept (Fig. 3).
Once the description is located, the next action is to interpret it. At this time, the state of [Project_Network :ProjNetwork1. ] becomes “in-activation; !@”. At start, the concept [InitializeProj #?] in [Project_Network :ProjNetwork1] is the only concept to be interpreted; the other concepts are in state “steady” (Fig. 3). The function of [InitializeProj] is basically to initialize the Erlst_st of the first node N1 and the TimeEstimate of each job.
Once the execution of [InitializeProj] is terminated, the relation “next” will propagate forward the state “trigger” to the concept [Int: N1.Erst] (Fig. 3). The resolution of the composed co-reference “N1.Erst” will enable the localization of its description which corresponds to the value 0. Since this latter is a simple data, its execution is null and then the relation “in1” will propagate forward the state “trigger” to the concept [P] (Fig. 3). At this moment, the first forward step of the method (compute the Erlst_st attribute of each node) will be performed, thanks to the lazy definition of the process P and to the forward propagation role of the relation “in”. When the Erlst_st attribute of the end node N4 is computed, the description of the node N4 will be interpreted involving the execution of the assignment operation. This latter will assign the value of the Erlst_st attribute to the Ltst_ft attribute of the same node N4. As a result, the concept [Int: N4.Lft] will be triggered (Fig. 3). Being an input argument of [P], this latter will be triggered in turn (through the relation “in3”), initiating the second forward activation of the network to compute the value of the Ltst_ft (Lft) attribute of all the nodes as well as the “total float” attribute of all the jobs.
It is more easy to see the activation then to comment it !
7 Conclusion, current and future works
This paper introduced the core of the language Synergy which illustrates how the CG formalism can be used as a visual multi-paradigm language with an activation-based interpretation.
Synergy makes use of the CG formalism as a uniform foundation for the integration of sequential and/or parallel procedural, process, functional, event-driven, object oriented and concurrent-object oriented paradigms. Indeed, programs according to these paradigms can be represented and integrated in Synergy using a minimum of basic notions common to them all. Those notions correspond to the basic elements of the CG theory : CG structure, context, co-reference, type hierarchy, conceptual structures and knowledge base.
Several current and future works are underway or planned to enhance, extend and use different components of the SYNERGY CG tool. One of the current projects is to re-implement SYNERGY with Java. Other projects concern the use of SYNERGY in the development of several applications : object-oriented applications, concurrent object-oriented and multi-agents applications, multi-media applications, intelligent tutoring and training applications, case-based reasoning, etc.
References
1.
Bos C., B. Botella, and P. Vanheeghe, Modeling
and Simulating Human Behaviors with Conceptual Graphs, in Proc. Of the Fifth
International Conference on Conceptual Structures, ICCS’97, Springer (1997)
2.
Brauer W., W. Reisig and G. Rozenberg (eds.),
Petri Nets: Applications and Relationships to Other Models of Concurrency,
Springer-Verlag (1986)
3.
Cyre W. R., Executing Conceptual Graphs, in
Proc. Of the 6th International Conference on Conceptual Structures,
ICCS’98, Springer (1998)
4.
Ellis G., Object-Oriented Conceptual Graphs,
in Proc. of the Third Intern. Conf. on Conceptual Structures, ICCS'95,
5.
Esch J., Contexts, Canons and Coreferent
Types, Proc. Second International Conference on Conceptual Structures, ICCS’94,
6.
Hee K. M., P. M. P. Rambags and P. A. C.
Verkoulen, Specification and Simulation with ExSpect, in Lauer (Ed), Functional
Programming, Concurrency, Simulation and Automated Reasoning, Springer-Verlag
(1993)
7.
Kabbaj A. and C. Frasson, Dynamic CG: Toward a
General Model of Computation, Proc. Third
International Conference on Conceptual Structures, ICCS’95, Santa Cruz,
CA (1995)
8.
Kabbaj A., Un système
multi-paradigme pour la manipulation des connaissances utilisant la théorie des
graphes conceptuels, Ph.D Thesis, DIRO, Université de Montréal, June (1996)
9.
Kabbaj A., Rouane K. and Frasson C., The use
of a semantic network activation language in an ITS project, Third
International Conference on Intelligent Tutoring Systems, ITS’96,
Springer-Verlag (1996)
10.
Kabbaj A., Synergy as an Hybrid
Object-Oriented Conceptual Graph Language, Seventh International Conference on
Conceptual Structures, ICCS’99 this
volume.
11.
Lakos C., From Coloured Petri Nets to Object
Petri Nets, in Michelis G. and M. Diaz (Eds.), Application and Theory of Petri
Nets, Springer (1995)
12.
Liddle S. W., D. W. Embley and S. N.
Woodfield, A Seamless Model for Object-Oriented System development, Bertino E.
and S. Urban (Eds.), Object-Oriented Methodologies and Systems, Springer-Verlag
(1994)
13.
Lukose D., Executable conceptual structures,
Proc. First International Conference on
Conceptual Structures, ICCS’93,
14.
Lukose D., Complex Modelling Constructs in
MODEL-ECS, in Proc. Of the Fifth International Conference on Conceptual
Structures, ICCS’97, Springer (1997)
15.
Mineau G. W., From Actors to Processes : The Representation of Dynamic Knowledge Using
Conceptual Graphs, in Proc. Of the 6th International Conference on
Conceptual Structures, ICCS’98, Springer (1998)
16.
Raban and Delugach, Animating Conceptual
Graphs, in Proc. Of the Fifth International Conference on Conceptual
Structures, ICCS’97, Springer (1997)
17.
Shlaer S. and S. J. Mellor, Object Lifecycles
- Modeling the World in States, Prentice-Hall (1992)
18.
Sowa J. F., Conceptual Structures :
Information Processing in Mind and Machine, Addison-Wesley (1984)
19.
Sowa J. F., Relating Diagrams to Logic, Proc.
First International Conference on Conceptual Structures, ICCS’93,
20.
Sowa J. F., Logical foundations for
representing object-oriented systems, J. of Experimental and Theoretical AI, 5
(1993b)
21.
Sowa J. F., Conceptual Graph Standard and
Extensions, in Proc. Of the 6th International Conference on
Conceptual Structures, ICCS’98, Springer (1998)
22.
Spinner M. P., Improving Project Management
Skills and Techniques, Prentice-Hall (1989)
23.
Thakkar S. S. (ed.), Selected Reprints on
Dataflow and Reduction Architectures, IEEE Computer Society Press (1987)
24.
Törn A., Systems Modelling and Analysis Using
Simulation Nets, in C. A. Kulikowski and al. (eds.), AI and ES Languages in
Modelling and Simulation, North-Holland (1988)
25.
Zouaq A., Modélisation en
Synergy d’un système multi-agents, Mémoire de fin d’étude, INSEA, Rabat,
Morocco (1998)