Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
hekate:xtt2 [2008/11/18 16:33]
ligeza
hekate:xtt2 [2019/06/27 15:49] (current)
Line 9: Line 9:
 It is aimed to be as the final version for the official HeKatE project (grant). It is aimed to be as the final version for the official HeKatE project (grant).
  
 +//Please put bigger remarks/​discussusion,​ to the [[hekatedev:​xtt2|XTT2 development page]]//
 ===== Introduction ===== ===== Introduction =====
  
Line 16: Line 16:
  
 In contrast to traditional rulebases design approaches allowing for a //flat// (single-level) set of rules (e.g. using the Rete-based inference engines) XTT introduces an explicit //​structure//​ in the rulebase, by introducing:​ In contrast to traditional rulebases design approaches allowing for a //flat// (single-level) set of rules (e.g. using the Rete-based inference engines) XTT introduces an explicit //​structure//​ in the rulebase, by introducing:​
-  * //tables//, used to represent groups of rules working in the same context ​and hence having similar structure of preconditions,​+  * //tables//, used to represent groups of rules working in the same context ​(having similar structure of preconditions),
   * //​intertable links//, used to provide explicit specification of inference control, namely switching between tables, that allow for decision-tree like structure.   * //​intertable links//, used to provide explicit specification of inference control, namely switching between tables, that allow for decision-tree like structure.
  
Line 29: Line 29:
  
 XTT is a formal method based on an expressive logical calculus called //​Attributive Logic// (or //Attribute Logic//). XTT is a formal method based on an expressive logical calculus called //​Attributive Logic// (or //Attribute Logic//).
- 
 ==== History and Related Documents ==== ==== History and Related Documents ====
 +FIXME
 +mscs, regulus, kheops, ijis, ecai96, oat, dexa
 +
 XTT (also referred to as XTT1) has been first formulated by Grzegorz J. Nalepa in [[hekate:​bib:​hekate_bibliography#​gjn2004phd|(gjn2004phd)]],​ and later described in [[hekate:​bib:​hekate_bibliography#​gjn2005sysci:​xtt|(gjn2005SystemScienceXTT)]],​ and [[hekate:​bib:​hekate_bibliography#​gjn2005compsci:​mirella|gjn2005CompSciMirella]]. XTT (also referred to as XTT1) has been first formulated by Grzegorz J. Nalepa in [[hekate:​bib:​hekate_bibliography#​gjn2004phd|(gjn2004phd)]],​ and later described in [[hekate:​bib:​hekate_bibliography#​gjn2005sysci:​xtt|(gjn2005SystemScienceXTT)]],​ and [[hekate:​bib:​hekate_bibliography#​gjn2005compsci:​mirella|gjn2005CompSciMirella]].
  
Line 64: Line 66:
 However, in the future the ARD+ shall be replaced by more advanced methods. However, in the future the ARD+ shall be replaced by more advanced methods.
  
-Basing ​on the above experiences,​ the current version of XTT known as XTT^2 has been proposed for the HeKatE project by Grzegorz J. Nalepa and Antoni Ligęza in 2008.+Based on the above experiences,​ the current version of XTT known as XTT^2 has been proposed for the HeKatE project by Grzegorz J. Nalepa and Antoni Ligęza in 2008.
 XTT^2 uses ALSV(FD) (//​Attributive Logic with Set Variables over Finite Domains//) as the formal foundation. XTT^2 uses ALSV(FD) (//​Attributive Logic with Set Variables over Finite Domains//) as the formal foundation.
  
Line 98: Line 100:
  
 ==== XTT Constraints ==== ==== XTT Constraints ====
-Rule prototypes ​these hint for XTT tables:+Rule prototypes ​provide hints for XTT tables:
   * structure -> what attributes are in the condidtion and conclusion   * structure -> what attributes are in the condidtion and conclusion
   * state changes in conclusion -> in the value modification only attributes present in the given table may be used   * state changes in conclusion -> in the value modification only attributes present in the given table may be used
-  * relations (inference order) -> default links (table2table) can be inferred ​FIXME this requires some research+  * relations (inference order) -> [[hekate:​xtt2#​links|default links (table2table)]] can be inferred
  
 (Please discuss at the [[hekatedev:​xtt2#​XTT constraints]] page.) (Please discuss at the [[hekatedev:​xtt2#​XTT constraints]] page.)
Line 164: Line 166:
  
 See [[hekate:​xtt2#​Inference]] for more details. See [[hekate:​xtt2#​Inference]] for more details.
- 
 ==== Rule RHS ==== ==== Rule RHS ====
  
Line 174: Line 175:
  
 The rule RHS can contain: The rule RHS can contain:
-  * state changes, that is attribute values modifications (with use of retract/​assert),​+  * state changes, that is attribute values modifications (with use of retract/​assert, FIXME by iw: there is no assert/​retract anymore, assuming that attributes can be multivalued,​ there are only set operations, an assert is represented as a sum: assert(A(1)) <=> A =  A u {1}), possibly with use of any predefined predicates/​functions etc. for now we assume all the results are explicitly represented in state!
   * external actions execution, that do not change attribute values, thus do not change the system state; these include output values definition and export,   * external actions execution, that do not change attribute values, thus do not change the system state; these include output values definition and export,
   * link that specifies inference control (e.g. a switch/case or a loop),   * link that specifies inference control (e.g. a switch/case or a loop),
-  * execution of any well-defined procedure for calculation of a function defined for input attribute values FIXME (//chain calculationsloop/​iterative calculationstransactions,​ control parameter calculations//;​ problem of bactracking! Do we have to put all the values to the state???).+ 
 +++++Some consequences ​backtracking| 
 +no parameter passing, 
 +no backtracking, 
 +simple solution 
 +++++
  
 === Attribute value modification === === Attribute value modification ===
Line 197: Line 203:
  
  
-2.2) Algebraic expressions in case of numeric attributes only; the expression can contain numbers, predefined algebraic operators and functions, as well as attribute values (Prolog //is//).+2.2) Algebraic expressions in case of numeric attributes only; the expression can contain numbers, predefined algebraic operators and functions/predicates, as well as attribute values (Prolog //is//).
  
 3) External action specification; ​ 3) External action specification; ​
Line 228: Line 234:
 A table provides a //visual// representation of rules, as below. A table provides a //visual// representation of rules, as below.
  
-{{xttp-table-new.png|XTT table new format}}+{{xttp-table-new.png|XTT table new format}} ​FIXME
  
 Rules in the table are interpreted one by one in a given way (see [[hekate:​xtt2#​Inference]]),​ this is the Table Inference. Rules in the table are interpreted one by one in a given way (see [[hekate:​xtt2#​Inference]]),​ this is the Table Inference.
Line 234: Line 240:
 Table rows (rules) may be connected to other tables (rows) by links. Table rows (rules) may be connected to other tables (rows) by links.
 This forms a tree-like structure. This forms a tree-like structure.
-This is the Tree Inference. ​FIXME (//In fact, it is more close to a **graph** representing a partial order of inference//​).+This is the Tree-like Inference. 
 +(//In fact, it is more close to a **graph** representing a partial order of inference//​).
  
 ==== Table Scheme ==== ==== Table Scheme ====
Line 255: Line 262:
   * //​functional calculation//​ i.e. a table performing any well-defined calculation,​.   * //​functional calculation//​ i.e. a table performing any well-defined calculation,​.
  
-This should be reconsidered with the above material.+This should be reconsidered with the above material ​on Rule RHS.
  
 ===== Inference ===== ===== Inference =====
Line 285: Line 292:
  
 This mechanism saves computational effort corresponding to repeated precondition checking and saves time in case some preconditions are logically dependent (one is logical consequence of the other or they are mutually exclusive). This mechanism saves computational effort corresponding to repeated precondition checking and saves time in case some preconditions are logically dependent (one is logical consequence of the other or they are mutually exclusive).
 +
 +FIXME
 +In fact this can be made even more general:
 +  * positive --> positive,
 +  * positive --> negative (exclusion of rules),
 +  * negative --> positive,
 +  * negative --> negative (exclusion of rules).
 +
 +This is to be reexamined and restated; a comparison to Rete may be in order.
  
  
Line 298: Line 314:
 partial order. partial order.
  
-In general we consider //positive links//, that  is links that are followed where a rule is fired. 
  
 Links are deterministic,​ that is a single rule decision can have a //single// link only. Links are deterministic,​ that is a single rule decision can have a //single// link only.
  
-FIXME ALi +In general ​we consider ​//positive links//, that  is links that are followed where a rule is fired. 
-It should be decided whether ​we consider explicit negative (else) ​linkspossibly at the table2table level.+ 
 +The designer can introduce //explicit negative ​links// by 
 +using an explicitly defined positive construction of the following scheme: 
 +<​code>​ 
 +precondtions --> conclusion| next(table.rule) 
 +true         ​--> ​          ​| ​else(table.rule) 
 +</​code>​ 
 + 
 +FIXME 
 +We can consider introducing number of global meta-interference attributes, 
 +such as "​mode_of_operation",​ "​task",​ "​did_any_rule_in_table_fired",​ etc. 
 + 
  
 === Links === === Links ===
 In general, the following //link classes// are considered: In general, the following //link classes// are considered:
   * //​rule-table//​ (r2t) a given rule in a given table when fired, transfers control to another table, meaning the inference starts at the first rule of the destination table. This is considered the //default// for XTT^2.   * //​rule-table//​ (r2t) a given rule in a given table when fired, transfers control to another table, meaning the inference starts at the first rule of the destination table. This is considered the //default// for XTT^2.
-  * //​rule-rule//​ (r2r) a given rule in a given table when fired, transfers control to another rule in another table +  * //​rule-rule//​ (r2r) a given rule in a given table when fired, transfers control to another rule in another table, or possibly ​//the same table// (inside ​table link. 
-  * //table-table// (t2t) the link is established at the table levelmeaning when all rules in the table fire the control is transfered ​to another tableThis is a casewhere a negative t2t link could be considered.+ 
 +FIXME: iw: I'm still not convinced about rule-rule linksany advantages? There are some disadvantages though, ie: if we change ​the rule firing order (let's say bottom-up instead of top-down,) rule-rule links can screw us really bad. Having rule-table links only forces designer ​to come up with well designed conditionsSobecause there are some doubts I would recommend not implementing it for time being at all.
  
 +++++More on intertable links|
 +In general, we should have inter-tables links and inside-table links. ​
 +Both of them can be defined with TableOut.RuleOut --> TableIN.RuleIN model. ​
 +However, for the inside table links we can define simple policies, such as a top-bottom order, top-first-fired order, without without circular interpretation.
 +++++
  
 === Link implementation === === Link implementation ===
Line 321: Line 354:
 Problem: In a general case, there might be multiple entry points in the XTT structure. Problem: In a general case, there might be multiple entry points in the XTT structure.
  
-Consider a tree (Ts are XTT tables) structure like this: +(See the discussion at the [[hekatedev:xtt2#​Branching]] page.)
-  T1- +
-      > T5 - +
-  T2-        \ +
-              T7 +
-  T3-        / +
-      > T6 -   +
-  T4-+
  
-//fired table// is a table already interpreted by the engine.+//A temporary semi-parallel solution//:  
 +ARD introduces partial order in tables, 
 +tables can be fired in any way, 
 +as long as this contstraint holds.
  
-To handle this we might introduce a simple backward-chaining approach. +FIXME: iw: not really there might be more than one table with input attributes (or rorw) in the condition ​partsit might be not doable ​to infer which table should be run first
-  * build a list of tables that can be fired +There might be an algorithm implemented which finds an order of execution (which ​table to start with), but any conditions using N/D value can screw it.  
-  * fire any table with no preceeding table, no incoming links or mark a selected table as a start table, +I'd suggest choosing an entry table, the one that the inference ​process starts withexplicitly.
-  * follow links to fire subsequent tables +
-  * to fire a table, no attributes ​in the condition ​can have the //​NOT_DEFINED//​ valuein case of such a table backtrack ​to another ​table preceeding this one +
-  * another solution, suitable for a single pass interpreter is to keep track of fired tables+
- +
-Another approach would be to predetermine the sets of tables can be fired at the beginning of the inference by a backward-chaining analysis ​of table schemes (ARD prototypes)+
- +
-The above problem seem to apply only to the initial inferencenot to general branching structure like this: +
-       Tj +
-        \ +
-  ​Ti ​      Tl +
-     ​\ ​  / +
-       Tk +
-In this case the inference ​is deterministicand depends on which rules in the first table Ti are fired. +
- +
-FIXME ALi +
- +
-(Please discuss at the [[hekatedev:​xtt2#​Branching]] page.)+
  
 ==== Interpreter Scenarios ==== ==== Interpreter Scenarios ====
Line 392: Line 404:
  
 For sanity, it should be assumed, that no attributes input/​communication attributes are updated during the inference. For sanity, it should be assumed, that no attributes input/​communication attributes are updated during the inference.
 +
 +FIXME Here we can think about a //​transaction-like mode// and possible //attribute freezing// or more lively models. Various possibilities of separation both among tables and tables vs. environment can be considered.
  
 This is the basic mode, that should be considered, ​ implemented,​ and analyzed before any other options. This is the basic mode, that should be considered, ​ implemented,​ and analyzed before any other options.
Line 437: Line 451:
   * communication (comm) (S <-> E)    * communication (comm) (S <-> E) 
 Arrows indicate the System/​Environment interaction. Arrows indicate the System/​Environment interaction.
 +
 +FIXME: iw: what's happened to ''​ro,​ rw, wo, state''​ classes?
  
 Discuss ideas here: [[hekatedev:​xtt2#​Attribute Classes]]. Discuss ideas here: [[hekatedev:​xtt2#​Attribute Classes]].
Line 449: Line 465:
  
 ===== HeKatE Meta Representation ===== ===== HeKatE Meta Representation =====
- 
-FIXME ALi 
  
 The following textual algebraic representation is provided. The following textual algebraic representation is provided.
Line 468: Line 482:
  
 Fact: Fact:
-FIXME ALi+
  
 ===== XTT Analysis ===== ===== XTT Analysis =====
Line 478: Line 492:
  
 Appropriate algorithms for XTT^2 should be developed. Appropriate algorithms for XTT^2 should be developed.
 +
 +In general, there are at least the follwoing possibilities:​
 +  * rule-rule (pairwise) analysis (e.g. identical rules, subsumption,​ exclusive rules - determinism),​
 +  * rules-in-table (all) analysis (e.g. local, contextual completeness,​ determinism),​
 +  * chains-of tables/​rules analysis (unprovided facts, unused conditions, unreachable conclusions,​ etc.).
 +
 +Further, any path should be analyzed for //​calculability//​ or //​executability//,​ i.e. if it can be followd (no part of information is missing) and -- if parallel action are allowed -- for determinism and deadlocks.
  
 ===== XTT^2 Markup ===== ===== XTT^2 Markup =====
Line 505: Line 526:
  
 ==== Possible ==== ==== Possible ====
 +
 +=== Inference with backtracking and cut===
  
 === Hierarchical types === === Hierarchical types ===
Line 515: Line 538:
 This could be possibly cobmined with the so-called //scope// from the XTT+. This could be possibly cobmined with the so-called //scope// from the XTT+.
  
 +=== Link labeling ===
 +If it is of ANY use?
  
 ==== Deprecated ==== ==== Deprecated ====
Line 531: Line 556:
 declarative ​ inference control spec declarative ​ inference control spec
  
 +FIXME
 +This perhaps we should leave as a //research thread// only.
 +
 +Fixed, simple declaration of control inference (with a few parameters only + the links) should be sufficient to demonstrate the power of XTT!
  
 +On the other hand we have to re-think the problems and advanatges of using cut (!) and similar mechanism (e.g. fail, exit).
hekate/xtt2.1227022384.txt.gz · Last modified: 2019/06/27 16:00 (external edit)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0