W3C home > Mailing lists > Public > public-rif-wg@w3.org > May 2009

Re: Review of FLD

From: Michael Kifer <kifer@cs.sunysb.edu>
Date: Tue, 19 May 2009 01:11:17 -0400
To: Chris Welty <cawelty@gmail.com>
Cc: "Public-Rif-Wg (E-mail)" <public-rif-wg@w3.org>
Message-ID: <20090519011117.65abcad1@kiferserv>
Chris,
thanx for your thoughts. This is useful and maybe we can converge soon.
Pls see below.

On Mon, 18 May 2009 23:01:40 -0400
Chris Welty <cawelty@gmail.com> wrote:

> >> Common Logic allows variable symbols and constant symbols to overlap.  Do the 
> >> subsets need to be disjoint?  All these types of things can be distinguished
> >> by their syntactic context.
> > 
> > This is just an unnecessary complication, which buys you nothing.
> > In many respects, RIF is more general than Common Logic, and forcing one to
> > decide what is a variable and what isn't by the context is a huge nuisance.
> > In fact, you CANNOT determine what is a variable by the context alone.
> > Many rule languages omit quantifiers. How do you distinguish then?
> 
> As you point out below, the choice should be up to a dialect.  Allowing variable 
> and constant symbols to overlap in FLD simply means that a dialect can make that 
> choice, not that every dialect must support it.  As it is, Common Logic cannot 
> be expressed as an FLD dialect, and thus it is not more general.

FLD is a framework for exchange languages. An exchange language is a common
medium to which other languages are mapped. Are you saying that Common Logic
cannot be mapped to FLD? I don't believe it until you prove it. Good
luck! :-).

Second, I said that FLD is more general than Common Logic "in many respects."
That claim holds true. In a well-defined sense, it is also strictly more
general, since Common logic is just a first-order logic, while FLD can define
non-1st-order dialects as well.

> > Besides, we have already agreed early on that variables are prefixed with a ?,
> > and this is how one identifies them.
> 
> We agreed on that for our existing dialects.  I never agreed to that for all 
> logic languages.  I personally don't see why it is needed, unless you allow no 
> quantifiers, in which case you do.  Again, seems like its a choice in language 
> design, not something to require of all.

Not requiring variables to be disjoint from constants is an unnecessary
complication that brings NO benefits whatsoever. I can't even imagine what a
suitable XML framework would look like in that case.

> >> "A countably infinite set of quantifiers...where n ≥ 1"
> >>
> >> It seems strange to include the variables as part of the set of quantifiers. 
> >> WHy aren't the quantifiers just Exists, Forall, ...


OK, based on your subsequent message it seems to have been resolved.

> > Quantifiers can be very general with all kinds of variables in various places.
> > For instance, how would you define bounded quantifiers?  You would need to
> > invent a separate sublanguage, but this sublanguage might turn out to be too
> > restrictive. What do you do then? Reconvene the WG to extend FLD?
> > Sounds like a huge complication with no visible benefits.
> 
> I don't get your point, how does adding the variables to the elements of the set 
> of quantifiers help you with bounded quantifiers?  Bounded quantifiers need 
> another argument with each variable.  I guess I don't see how this helps you 
> differentiate between different languages with different forms of quantification.

Since everything can be packed into a symbol, a quantifier symbol can have all
the necessary information about boundedness encoded in the name of the
quantifier.

> >> 2.4 Terms
> >>
> >> "Positional terms in RIF-FLD generalize the regular notion of a term used in 
> >> first-order logic. For instance, the above definition allows variables 
> >> everywhere, as in ?X(?Y ?Z(?V "12"^^xs:integer)), where ?X, ?Y, ?Z, and ?V
> >> are > variables. Even ?X("abc"^^xs:string ?W)(?Y ?Z(?V "33"^^xs:integer)) is
> >> a positional term (as in HiLog [CKW93]). "
> >>
> >> This idea goes back at least as far as Enderton, 1972, and has been used in 
> >> implemented systems such as SNePS and Conceptual Graphs in the 80s.  Since 
> >> Enderton published in '72 what was already a "well known encoding" of
> >> predicate variables in FOL, I don't think it's accurate to say this
> >> "generalizes...FOL". 
> >> The fact is that this IS perfectly first-order.
> > 
> > The idea goes back to Henkin. However, take another look at these terms and you
> > will see that some are not expressible in Henkin's syntax or in Common Logic.
> > It is in this context that HiLog is referred to. Second-order variables by
> > themselves are not worth bothering to reference, as this is common knowledge.
> 
> Yes of course, but this example is of positional terms and is completely first 
> order.  What about it do you consider non-Henkin (other than the datatypes), or 
> non-CL?  Again, I'm just talking about the positional terms item, not FLD terms 
> in general.

Is ?X("abc"^^xs:string ?W)(?Y ?Z(?V "33"^^xs:integer)) an instance of Henkin's
or CL syntax? Hint: check what plays the role of a function here.


> >> Thus it seems reasonable to just say something like: "Positional terms in
> >> RIF-FLD are quite general, and allow variables everywhere, as in ?X(?Y ?Z(?V
> >> "12"^^xs:integer)), where ?X, ?Y, ?Z, and ?V are variables.  Even
> >> ?X("abc"^^xs:string ?W)(?Y ?Z(?V "33"^^xs:integer)) is a positional term (as
> >> in HiLog [CKW93], SNePS [SR87], and Common Logic [CL07]). "
> > 
> > 
> > See above. Also, SNePS has little to do with HiLog.
> 
> I never said it did, just that this kind of syntactic freedom (to use variables 
> in pretty much any position) was implemented in SNePS by 1985 at the latest, and 
> probably earlier.

Again, variables in different position is not the issue I am pressing here.
You need to go back and look at the form of the terms to see what I am
referring to.


> >> In a <t,u,f> valued dialect, I'm unsure what happens in this case:
> >>
> >> Exists(?x) P(?x)
> >> Exists(?x) P(a) :- P(?x)
> >>
> >> If this entails anything other than P(a), then we would have a hidden
> >> extension.
> > 
> > Did you mean this?
> > 
> >    (*)  P(a) :- Exists(?x) P(?x)
> 
> No, I meant the example I gave, though (*) is equivalent in a first-order system 
> to my second sentence, and the entailment of the two sentences would of course 
> be P(a).

No, they are NOT equivalent.

>  I'd be happy with that rewrite, but now I don't know why the rewrite 
> would make a difference.

Because they are NOT equivalent.

Your stuff is equivalent to
          P(a) :- Forall ?x p(?x).

> > First, let me say that FLD does not define entailment --- dialects do.
> > This is a MAJOR point.
> 
> I'm just wondering what the sensible entailment in a well-founded semantics 
> would be for that, and if it is the same as in a first order system.

Are you using the term "well-founded semantics" in a generic sense or in the
sense of Van Gelder et al?

>  It seemed 
> to me that you have a problem with a closed/open world and the entailments might 
> be different.

I have no problems with the laws of nature because I can't change them.

Seriously, it is not a problem with open/closed or FLD. The issue is how do you
define dialects?

If you take a first-order dialect or some subset of it with negation and put an
LP dialect on top of it as an extension then you might have a problem, if you
are not careful.

FLD has two kinds of negation, neg and naf. It is suggested that neg is
used for classical-looking negations (classical, explicit, strong) and naf for
default negation (well-founded, stable, etc.). So, the open/closed world type of
invisible extension cannot arise, if the dialect designer does it right.

I don't believe that it is possible to design a suitably general framework that
will prevent an incompetent designer to create dialects with invisible
extensions (for instance, by using neg for classical negation in one dialect and
for default negation in another).

Btw, RIFWG has not documented Sandro's rules of thumb, including what an
invisible extension means, in any official doc. This appears in no
document that has ever been reviewed and/or proposed for submission to W3C.


> > Second, if you indeed meant Exists(?x) P(a) :- P(?x) then the above does not
> > entail anything useful (not even P(a)) in any reasonably defined dialect.
> > If you meant (*), then P(a) is entailed.
> 
> For certain what I wrote entails P(a) in FOL, which is a pretty reasonably 
> defined dialect.

Not certain at all :-) See above.


> > Third, what did you mean by "anything other than P(a)"?
> > Of course, if it entails P(a) then it entails P(a) /\ P(a), P(a) \/ Exists(?x)
> > p(?x), etc. I fail to see your point here.
> 
> I was wondering if it creates an "invisible extension" where e.g. the same rule 
> means different things in different dialects.

Invisible extensions don't spring up on their own. Only if someone creates
dialects that have this property. In the absence of RIF police and rapid
deployment (educational) forces this is unavoidable. :-)
Especially if we don't officially define invisible extensions and explain their
grave danger to the rest of the humanity.


> >> I note that, like BLD, FLD avoids any notion of error.  I understand why we
> >> did that for BLD, but wonder if more expressive and complicated dialects will
> >> want it, and whether FLD should support it.
> > 
> > Do you have a proposal for how to do that specifically?
> > Of course one can think of many ways, but it is not particularly clear which is
> > the "right" one.
> > Given that our builtins do not support this notion, it is not even
> > clear what the utility of this thing would be.
> > 
> > Furthermore, FLD is general enough to allow dialects to support certain types
> > of errors. For instance, they can introduce a new truth value (and a new
> > constant for functions that return errors). However, the wisdom of imposing
> > this through FLD is unclear to me.
> 
> Well, sometimes you seem to miss the point of FLD (;-) - it shouldn't impose 
> anything but rather provide a range of options to logic dialect designers.

To propose a range of options, we need to have some up our collective sleeve.

> Anyway, I have no proposal for errors, just pointing out that some dialect 
> designers might wish for it.  I seem to recall the (lack of a) notion of error 
> we are using in BLD was my proposal anyway, so I should be happy with it...

In BLD we really had no choices, since we wanted to stay as much first-order
as possible. But to suggest something for FLD we need to have concrete
tried-and-true proposals. I believe that FLD is general enough to allow some
smart people to define what they want.  Other dialects might then copy their
ideas. A future WG might then canonize that in FLD 3.0.

-- 
    -- michael
Received on Tuesday, 19 May 2009 05:12:11 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:34:08 GMT