From: Stefan Decker (stefan@ISI.EDU)
Date: 02/25/03
Pat,
thanks a lot for your remarks!
At 03:16 PM 2/12/2003, pat hayes wrote:
>>Pat: Sending his concerns about the notion of "rules"
>
>This probably deserves a book, but I will try to summarize.
>
>Basically, I no longer know what this discussion is talking about, since
>the word "rules" has become so all-encompassing as to be effectively
>meaningless; it seems that any computation whatsoever can be classified by
>a systems of 'rules' in some sense or other. So "rules", "rule system",
>etc., have become simply words meaning 'computational specification' or
>'program'.
>
>So what? Well, there are several consequences.
>
>First, admitting that this is so (if it in fact is) frees up the
>discussion: to introduce "rules" it is not necessary to use something that
>would be classified as a 'rules language', for example: any computational
>formalism will do. Since in practice it is rather hard to stop people
>writing code in their favorite programming language, this would also have
>the effect of corresponding to social reality. In fact, the overall
>picture that one is then left with is this: the mechanisms available to
>the SW consist of content languages for expressing and transmitting
>propositional content (RDF, DAML, OWL etc) and code which is used to
>manipulate it. Any code, written in any way anyone wants to. That is a
>free-for-all kind of picture which I am reasonably happy with. It goes
>along with the let-a-thousand-flowers-bloom kind of attitude in the W3C
>community, which I find quite refreshing. However, if this is in fact the
>case, then let us be open and honest about it. In particular, any
>discussion of semantic relationships between the program code and the
>content is then out of place, or at least should be conducted entirely in
>terms of entailments in the semantics of the content language, which need
>have no relationship whatever to the semantics, if there is any, of the
>programming language used to specify the processes which act on the content.
I didn't have the impression to far that "rules" are used synonymous to
"any computational formalism".
But it is unclear to me how the different "rule styles" fit together.
Maybe the RuleML hierarchy helps:
rules
/ \
1. / \ 2.
/ \
reaction rules transformation rules
|
3. |
|
derivation rules
| |
4. | 5. |
| |
facts queries
|
6. |
|
integrity constraints
But it leaves still open which computational formalisms are useful for
which part of the tree
(and how the different rule types are exactly defined).
>Second, I have the impression - ignore this remark if this is a mistaken
>impression - that some members feel that "rules" or maybe "rule systems"
>comprise a(nother) distinctive fundamental approach to, or paradigm for,
>computational descriptions, one that can perhaps be classified with the
>Turing machine/sequential-instruction paradigm or the OOP paradigm or the
>recursive-equations paradigm, and might be seen as an extension or
>generalization of logic programming and production rules. On this view, it
>is not entirely vacuous to claim that 'rules' are an appropriate
>programming style for application to the SW; but in this case, I would
>like to see this claim defended, as I for one do not feel inclined to
>accept it, and certainly not without some detailed discussion of the
>reasons for it and the claims that this particular paradigm is supposed to
>have over many others. Certainly it cannot claim to have wider influence
>or acceptability than, say, OOP programming, so presumably the case must
>be based on some perceived technical advantage. To make this case would
>require that the nature of the paradigm be spelled out in more detail, so
>that any technical case can be adequately evaluated. In particular, I
>would want to know why the DAML committee is spending so much time on this
>topic, which seems to have nothing particularly to do with DAML.
My reply to your point goes as follows:
DAML+OIL created the prerequisites for data on the Web.
Once we have a lot of data on the Web, we want to deploy it.
Deployment requires the combination, aggregation, and transformation of data
(which is instance data complying to DAML+OIL ontologies).
Using conventional programming languages (Java, Pearl, whatever) writing
the necessary programs for combination, aggregation, and transformation of data
becomes a very time consuming and thus costly task.
Rules for data manipulation offer a promising way to reduce the cost, since
they offer an abstract computational model, which saves much of the effort
that would
otherwise go into conventional programs.
I don't know if there have been a formal evaluation of the above mentioned
claim.
It seems to be plausible, but a formal evaluation would be useful.
So much for "transformation". I'm not claiming it is the only possible
application of rules, and it is one.
>Third, there seems to be a presumption that 'rules' are somehow closer to
>logic than other programming paradigms. Words like 'assertional' were
>being used in the telecon discussion, for example, with an approving tone
>of voice. But if the term "rule" is this wide in its scope, then there is
>no particular relationship between rules and logic at all, any more than
>between rules and numerical simulation or rules and graphics
>programming. Prolog is a perfectly general-purpose programming language.
>So I would like to invite anyone who feels that there is some special
>connection between 'rules' and logic, particularly SW logic, to spell this
>connection out in enough detail that it can be examined critically.
The connection, from a logic programming point of view, is the existence of
a model theory
for logic programs.
Ignoring the non-monotonic negation for a moment, the main
differences to classical FOL is the focus on least Herbrand models.
"Least" because every Herbrand model that subsumes the least one
is also a model, and Herbrand model since Herbrand models suffice
(a set of clauses has a model iff it also has a Herbrand model).
>-----
>aside.
>I think that the presumption of such a connection is based on a series of
>historical misunderstandings.
>
>First, the word 'rule' is already used in logical metatheory but in quite
>a different sense, as in 'inference rule'. It might be worth expanding on
>this a little. The "rules" used in typical logic programming systems -
>which can be loosely identified with Horn clauses, let us suppose for the
>moment to simplify the discussion - are like logical sentences, NOT
>logical inference rules. The thing in a 'rule system' which corresponds
>most closely to a logical inference rule would be the actual code of the
>unification algorithm and the backward-chaining search process. Inference
>rules are not logical statements: to identify them is a category error.
>(Lewis Carrol wrote a famous imaginary dialog which illustrated the error
>over a century ago, and it was considered a typical elementary student
>error even then. )
>
>Second, the logic programming tradition has unfortunately confused what is
>in fact a very clear semantic distinction. Contrary to standard LP
>doctrine, logic programming is not logic. Programs are not assertions, and
>algorithms are not logic plus control. I know this goes against what
>Kowalski said; at the time I also said that, but we were both wrong. The
>analogy is seductive but fundamentally misleading, and it is misleading in
>a way that matters centrally to the semantic web. What Kowalski should
>have said was, algorithms are logic plus control modified by a
>closed-world assumption. This is why I do not feel that logical
>programming should have any central place in the SW technology, and why
>its presumptive claim to do so is based on a semantic mistake.
I don't see your point.
Logic Programming consists of a model theory (least Herbrand models) and
multiple possible inferences procedures trying to implement the
model theory (this is very clear if we are not adding
the closed world negation to our language).
Prolog is just one particular example of a possible implementation - and
maybe not the one most useful for the SW.
But even if we are adding closed world negation to our language
we still have nice model theoretic characterizations of
eg., stable and well-founded model semantics.
So I'm not seeing your point here.
>One can characterize the semantic distinction quite precisely and in very
>general terms: Ask the question, is the domain of discourse of the
>language required to satisfy the second recursion theorem (ie to be closed
>under minimal fixed-points)? If so, the language is a programming language
>of some kind, and it talks about domains which are in some sense
>computable. If not, it is an assertional logic and suffers from the
>expressive limitations enforced by Goedel's theorem. This is a
>*fundamental* semantic distinction. Logic is the latter; logic
>programming, like all other programming, the former. Closed-world
>assumptions, negation-by-failure and variety of other nonmonotonic devices
>belong naturally in the former kind of semantics framework, but are
>directly and fatally invalid in the latter. Minimal model semantics belong
>naturally in the former but are impossible to adequately formalize in the
>latter.
My theory knowledge is rusty. (I looked up the Kleen's 2nd recursion
theorem, but didn't get the relationship
to least Herbrand models).
. What are the consequences of the difference?
And why can minimal model semantics not adequately formalized? What is
"adequately formalized"?
And why is it important?
>So, are rule languages in the former or latter category? It seems that
>some are in one (Horn clauses), some in another (Production systems, logic
>programming). To me, this makes the broad categorization of 'rule system'
>worthless and potentially dangerous, since it blurs a centrally important
>semantic distinction. Content languages for the interchange of
>propositional content on the semantic web cannot be restricted to
>computable domains; to do so would be fatal for the intended uses.
>
></aside>
>----
>
>Fouth, while I am not opposed to attempts to classify kinds of "rules" or
>to give a general characterization of what "rules" are or are not, I do
>not see how any of this is centrally relevant to the DAML committee or to
>the SWeb more generally. I wish enthusiasts of the "rules" paradigm well,
>and am happy that "rules" interest groups, working consortia, etc. are
>being formed, I guess; but I do not see any particular reason why their
>business should be conducted in this forum.
DAML+OIL enabled data on the web - know we need a way to process it
decoratively.
>Amplifying this point, I think that there is an argument which has been
>implicitly accepted which goes roughly as follows: OWL is not expressive
>enough; it cannot express quite a lot of logical statements, for example.
>In order to provide the needed expressivity, we need to add the ability to
>express these 'missing' logical forms, and that is what a Rules Language
>is for. On this view, then, Rules are something like the next step on a
>process of discovery which aims to creep up Tim's famous layer cake. The
>trouble with this idea is that we do not need to inch along this slowly
>and carefully. That is like using rock-climbing tools to walk along a
>highway: we know where it goes, it has been bearing motorized traffic for
>years, there is no need to pretend to explore it carefully. It leads to
>first-order logic; and so why not just say this at once and stop
>pussyfooting around? On *this* view of "rules" , note, they really are
>just Horn clauses. They are not logic programs or a new paradigm for
>computation; they are not inference rules or production systems or
>anything else: they do not involve minimal model semantics or closed
>worlds or negation by failure. Their semantics is Tarskian, simple,
>obvious and thoroughly understood, and they are part of the content
>language, not code for manipulating the content language. If this is what
>"rules" are, then I have no problem with them, but there is no need for us
>to spend time to define them; they are already defined.
The problem is, what can you actually do with first order logic?
If you have a mission critical application, would you rely on a first-order
theorem prover?
So I guess part of the answer is, that FOL is actually more than we have
asked for.
Also is the open world semantics suitable for all applications?
(If yes, why was there so many resources wasted exploring non-monotonic
reasoning)?
>So, it seems to me, either "Rules" refers to a rather small thing which is
>already done, and which we can simply agree on, stop discussing and then
>move forward; or else it refers to something so big and so underdefined as
>to be useless and more of a distraction than of utility; or else it needs
>to be defined, and argued for, much more carefully than I have seen so far.
If it is undefined (or better, there exist multiple viewpoints) we should
list those viewpoints.
As a summary:
The "rule" notion is still unclear, and it seems that many
different interpretations are possible.
The question is which one we adopt.
I don't think it should be pure FOL, since FOL is lacking
certain properties important for industrial deployment, like
for starters, a terminating implementation.
Best,
Stefan
>Pat
>
>
>
>--
>---------------------------------------------------------------------
>IHMC (850)434 8903 or (650)494 3973 home
>40 South Alcaniz St. (850)202 4416 office
>Pensacola (850)202 4440 fax
>FL 32501 (850)291 0667 cell
>phayes@ai.uwf.edu http://www.coginst.uwf.edu/~phayes
>s.pam@ai.uwf.edu for spam
>
--
http://www.isi.edu/~stefan
This archive was generated by hypermail 2.1.4 : 02/25/03 EST