From: Tim Bradshaw
Subject: `Strength' o boolean combinations
Date: 
Message-ID: <fbc0f5d1.0111020335.1545fc8c@posting.google.com>
This isn't really a lisp-specific question but the implementation is
in Lisp, and I suspect c.l.l's readership correlates quite well with
people who will know the right answer.

I have a system for setting parameters for various programs.  These
things are actually just stored in an alist/hashtable somewhere, and
you can get at them with something like:

    (get-parameter :source-file-type) -> "lisp"

for instance.

Parameters are read from parameter files under the control of
`features' which are *not* the elements of *FEATURES* (although those
are all features in this sense).  A sample form in a parameter file
might be:

(:cl
 :fasl-file-type "fasl"
 (:lw
  :fasl-file-type "fsl")
 (:genera
  (:ivory
   :fasl-file-type "ibin")
  :fasl-file-type "bin"))

The exact syntax doesn't matter, but the idea is that the car of each
form is a feature, and if it's true then the rest of the form is
processed.  As the thing descends nesting levels the `strength' of the
feature increases, so in the above, if :CL and :LW are both true, :LW
wins because it's more nested.  Similarlt for the genera section,
genera beats CL and ivory beats genera (note that in this case the
result is different than just left-to-right and last assignment wins).

An additional thing is that a feature can be assigned a strength which
is summed to the nesting strength (each level of nesting increments
the strength by 1) - this is normaly 0, but can be a real or T
(meaning stronger than any finite number) or NIL (meaning weaker than
any finite number).  There are defined features :OVERRIDE with
strength T, :DEFAULT with NIL, and PROGN with -1.  :OVERRIDE can be
given to insist on a value:

(:cl
 (:override
  :foo 3)
 (:acl
  (:acl-6
   :foo 4)))

means :FOO is 3, not 4.  :DEFAULT provides default values since it
loses to any
other feature.  PROGN is a devious trick:

(...
 :foo 1
 (progn
  :bar 3))

is the same as 

(...
 :foo 1
 :bar 3)

except that this works:

(...
 :foo 1
 #+only-in-one-implementation
 (progn
  :bar impl-package:crun))

So that's why I want to have real values for strength (I'm not sure
that any value other than -1 is ever useful in practice).

OK, so I hope that makes some kind of sense.  Now I want to add
boolean combinations of features:

((or :acl :lw ...)
 ...
 ((not :acl)
  ...)
 ((not :lw)
  ...))

Now the question is: what should the strength of a boolean combination
be?
I think for AND it's clear that it should be the strength of the
weakest thing being combined.  But OR I'm not sure about: for a while
I thought of making it be the strength of the first thing to be true
but this is awful because it means that:

(or :always-true-but-weak :strong)

and 

(or :strong :always-true-but-weak)

have different strengths, which is horrid.  NOT I haven't even thought
about - I think that it should be 0, since it is only true when the
feature if false and false features have no strength.

So does anyone have any idea what OR should do?  Maybe there is no
coherent solution for it, I'm not sure (isn't this kind of like one of
these fuzzy logic things where there are always holes you can fall
down?).

Thanks

--tim

From: Espen Vestre
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <w6u1wdl63u.fsf@wallace.ws.nextra.no>
··········@tfeb.org (Tim Bradshaw) writes:

> So does anyone have any idea what OR should do?  Maybe there is no
> coherent solution for it, I'm not sure (isn't this kind of like one of
> these fuzzy logic things where there are always holes you can fall
> down?).

What you do looks a lot like nonmonotonic logic. More specifically,
your system can be viewed as kind of "Belief Revision System", where
formulae update a "belief state" consisting of atomic formulae with
annotated strengths. When I used to work on this stuff (a never
finished Ph.D....*sigh*) I think one of my conclusions was that you
can't have a really useful "revision rule" for disjunctions with
a simple state model like yours, since the information the disjunction
gives you can be regarded as "metainformation about future states".

Regarding NOT, there are at least two versions of negation which
are useful in such systems: One is a pure "epistemic NOT", which
only acts as a test on your knowledge collected so far, the other
version of NOT actively adds the negative information to your "belief
state", which then has to be able to encode it somehow.

(I hope this wasn't too confusing, I haven't been working actively
 on this topic for more than 7 years)
-- 
  (espen)
From: Tim Bradshaw
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <ey3y9lp9wfx.fsf@cley.com>
* Espen Vestre wrote:

> What you do looks a lot like nonmonotonic logic. More specifically,
> your system can be viewed as kind of "Belief Revision System", where
> formulae update a "belief state" consisting of atomic formulae with
> annotated strengths. When I used to work on this stuff (a never
> finished Ph.D....*sigh*) I think one of my conclusions was that you
> can't have a really useful "revision rule" for disjunctions with
> a simple state model like yours, since the information the disjunction
> gives you can be regarded as "metainformation about future states".

This is what I was worried about, having had some small exposure to
this kind of stuff.  Curses...

--tim
From: Sashank Varma
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <sashank.varma-0211011554430001@129.59.212.53>
In article <····························@posting.google.com>,
··········@tfeb.org (Tim Bradshaw) wrote:

>Now the question is: what should the strength of a boolean combination
>be?
>I think for AND it's clear that it should be the strength of the
>weakest thing being combined.  But OR I'm not sure about: for a while
>I thought of making it be the strength of the first thing to be true
>but this is awful because it means that:
>
>(or :always-true-but-weak :strong)
>
>and 
>
>(or :strong :always-true-but-weak)
>
>have different strengths, which is horrid.  NOT I haven't even thought
>about - I think that it should be 0, since it is only true when the
>feature if false and false features have no strength.

i don't preted to fully understand your problem.  that said, what if
OR is the strength of the strongest thing being combined?  this is
nicely symmetric with your definition of AND and solves the tricky case
above.

i suspect you're going to want definitions that follow those
standard rules of algebras and relations that i've forgotten.
surely any definition you adopt will respect:

(1) associativity: (OR A (OR B C)) = (OR (OR A B) C).
    (mine does; your's does but 'incorrectly' -- it always returns A)

(2) commutativity: (OR A B) = (OR B A)
    (again, mine does, your's doesn't).

etc.  gotta go.

sashank

ps: i think your definition of NOT may be wrong too unfortunately.
From: Tim Bradshaw
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <fbc0f5d1.0111050145.36a121d9@posting.google.com>
·············@vanderbilt.edu (Sashank Varma) wrote in message news:<······························@129.59.212.53>...
> 
> (1) associativity: (OR A (OR B C)) = (OR (OR A B) C).
>     (mine does; your's does but 'incorrectly' -- it always returns A)

No, it always returns the strength of the first true thing, so it's
always right.

> 
> (2) commutativity: (OR A B) = (OR B A)
>     (again, mine does, your's doesn't).
> 

Yes, it gets this wrong.  I think your suggestion of strongest may be
more nearly correct.
> 
> ps: i think your definition of NOT may be wrong too unfortunately.

Well, for NOT you *have* to pull the strength out of the air, because
features that are not true have no strength, and if the feature is
true then it doesn't matter.  So 0 seems the most neutral value.  It
would be different if I had degrees of not-trueness, but I don't - if
something not true processing just stops (which is what I want!).
From: Sashank Varma
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <sashank.varma-0511011019540001@129.59.212.53>
In article <····························@posting.google.com>,
··········@tfeb.org (Tim Bradshaw) wrote:

>> ps: i think your definition of NOT may be wrong too unfortunately.
>
>Well, for NOT you *have* to pull the strength out of the air, because
>features that are not true have no strength, and if the feature is
>true then it doesn't matter.  So 0 seems the most neutral value.  It
>would be different if I had degrees of not-trueness, but I don't - if
>something not true processing just stops (which is what I want!).
                                           ^^^^^^^^^^^^^^^^^^^^^
i was afraid i had missing something in your message.
From: Kenny Tilton
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <3BE6CB17.5000704@nyc.rr.com>
Tim Bradshaw wrote:

> Well, for NOT you *have* to pull the strength out of the air,


never a good sign :)

 > because

> features that are not true have no strength, and if the feature is
> true then it doesn't matter.  So 0 seems the most neutral value.


but then doesn't :default lose to any NOT'ed feature?

kenny
clinisys
From: Tim Bradshaw
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <fbc0f5d1.0111060128.7909bdac@posting.google.com>
Kenny Tilton <·······@nyc.rr.com> wrote in message news:<················@nyc.rr.com>...
> Tim Bradshaw wrote:
> 
> > Well, for NOT you *have* to pull the strength out of the air,
> 
> 
> never a good sign :)

Well, there's not much choice, since there are an infinite number of
false features!  I need to define some default strength for the
negation of one.
> 
> but then doesn't :default lose to any NOT'ed feature?

Yes.  I think this is OK, probably.

--tim
From: Kenny Tilton
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <3BE7ECCE.6F5C238F@nyc.rr.com>
Tim Bradshaw wrote:
> 
> Kenny Tilton <·······@nyc.rr.com> wrote in message news:<················@nyc.rr.com>...
> > Tim Bradshaw wrote:
> >
> > > Well, for NOT you *have* to pull the strength out of the air,
> >
> >
> > never a good sign :)
> 
> Well, there's not much choice, since there are an infinite number of
> false features!  I need to define some default strength for the
> negation of one.

I was too obscure. What I meant was that when I have to start pulling
things out of the air I take that as a sign that I have strayed from the
Tao. :) 

What I see is that you understand perfectly well what semantics you want
from NOT, AND and OR and the rest but that the arbitrary commitment to
#'> for determining outcomes makes it is necessary to get from the
slightly hairy logic language you are building to simple ordinal values.
It isn't always clear how to compile the language into numerical
strengths or strength increments or strength choices, so strengths start
getting picked out of the air trying to keep the whole wadge from
collapsing. 

The Real Problem was when the need to compile was created by choosing to
have #'> decide the outcome. That forces the compilation into ordinals,
which is not always clear how to do because #'> is not as rich as AND,
OR, NOT, :default, :override and nesting depth. So one loses
information. 

btw, about NOT, if you want to stick with this scheme (which I still
don't fully get) did you mean that zero becomes the net summed strength
or that zero is the increment applied to the summed strength? The latter
sounds right, tho I found myself wondering if a PROGN-like -1 might not
be in order. Depends on the code.

kenny
clinisys
From: Kenny Tilton
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <3BE42139.ACA9C401@nyc.rr.com>
Tim Bradshaw wrote:

<snip>

> The exact syntax doesn't matter, but the idea is that the car of each
> form is a feature, and if it's true 

What makes a feature true? I am guessing this is something decided some
other way which does not matter to the problem at had, just checking my
understanding.

> 
> (:cl
>  (:override
>   :foo 3)
>  (:acl
>   (:acl-6
>    :foo 4)))
> 
> means :FOO is 3, not 4.  :DEFAULT provides default values since it
> loses to any
> other feature.

Just to see if I understand, would :default work like this?

(:default
 :foo 7
 (:cl
  (:override
   :foo 3)
  (:acl
   (:acl-6
    :foo 4)))

> ((or :acl :lw ...)
>  ...
>  ((not :acl)
>   ...)
>  ((not :lw)
>   ...))
> 
> Now the question is: what should the strength of a boolean combination
> be?
> I think for AND it's clear that it should be the strength of the
> weakest thing being combined.

But i thought the features being and'ed or or'ed were either true or
not, and that strength was just a measure of search depth (except for
:override and :default).

Overall I think translating branching logic to numerical strength is
artificial and will create difficulties, but then again I do not yet
fully understand what you are up to. Looks like fun though. :)

kenny
clinisys
From: Tim Bradshaw
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <fbc0f5d1.0111050158.3fd2be97@posting.google.com>
Kenny Tilton <·······@nyc.rr.com> wrote in message news:<·················@nyc.rr.com>...
> What makes a feature true? I am guessing this is something decided some
> other way which does not matter to the problem at had, just checking my
> understanding.
> 

Yes, you define features with a macro somewhere, it looks like

(declare-feature :foo
 (:aliases :bar :zig)
 (:strength ...))


> Just to see if I understand, would :default work like this?
> 
> (:default
>  :foo 7
>  (:cl
>   (:override
>    :foo 3)
>   (:acl
>    (:acl-6
>     :foo 4)))

I'm actually not sure what the answer is here, or rather I'm not sure
what it would be if there was any setting for FOO which was outside
the default clause.  It hangs basically on what the value of (+
-infinity 1) is.  I think all these values are infinitely weak, but
probably this is just not well-defined, and I don't have the
implementation to hand.

The *intention* was that you would not do this, but do something like

(:acl ...)
(:my-system ...)

(:default ...)

and the default clause just makes sure that anything not set elsewhere
does get set somewhere.

 
> But i thought the features being and'ed or or'ed were either true or
> not, and that strength was just a measure of search depth (except for
> :override and :default).

Yes, *except* that it turns out to be useful to have a -1 strength to
handle the case of PROGN.  I want

(...
 :a b
 (progn
  :c d))

to be exactly the same as

(...
 :a b
 :c d)

so I can use PROGN as a pure-grouping operator, which is very
convenient as it lets you use #+ and #- easily.  So rather than
special-case PROGN I implemented this general
arbitrary-finite-strength thing which is now causing me problems.
Perhaps I should decide not to do this and go back to the simpler
design!

--tim
From: Kenny Tilton
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <3BE6AB98.90802@nyc.rr.com>
Tim Bradshaw wrote:

> 
> Yes, you define features with a macro somewhere, it looks like
> 
> (declare-feature :foo
>  (:aliases :bar :zig)
>  (:strength ...))


My bad. I read your original post too fast, missed where you mentioned 
initial feature strengths could be plusp. So now I see what the OR and 
NOT issue is about...


> Perhaps I should decide not to do this and go back to the simpler
> design!
> 


I spent months struggling in vein with a system like this. I won't go 
into the whole thing, but like you I had a bunch of code deciding one 
thing and then expressing it numerically for a blind numerical 
comparison to work off to decide actual outcomes. Life got much better 
when I had the first bunch of code just decide the outcome.


The "strength" concept in your scheme looks fishy. I am bothered by 
nesting depth contributing to strength. Having to assign progn a 
strength of -1 may be a message from god. And combining nesting depth 
with possible initial strengths for a feature sounds like apples and 
oranges. Finally you have special cases :override and :default, a tip 
off to me that the nunerical strength is a sham. By which I mean...

I once saw the SEC rules for risk assessment. You took any given bond 
with it's value and date and other stuff, then possibly hedged it 
against another bond under all sorts of rules about when two bonds could 
be considered offsetting, then you came up with a number. But this 
number was no sham, it was a best-guess at how much the bank stood to 
lose on that bond and could be sensibly added up for all the banks 
holdings to calculate a net position.

Anyway, as for your original query, you are inventing the scheme so you 
can do what you want, right? You can use OR to return the first plusp 
(not minusp? non-nil?) feature, then introduce MAX to pick out the 
strongest. (Come to think of it, not sure why AND picks out the weakest.)

Difficulty deciding the semantics of the operators of this scheme might 
be an indictment of the scheme itself,  certainly of your present 
undertsanding of the scheme.

kenny
clinisys
From: Juliusz Chroboczek
Subject: Re: `Strength' o boolean combinations
Date: 
Message-ID: <87pu6uustp.fsf@pps.jussieu.fr>
Tim Bradshaw:

TB> (:cl
TB>  :fasl-file-type "fasl"
TB>  (:lw
TB>   :fasl-file-type "fsl")
TB>  (:genera
TB>   (:ivory
TB>    :fasl-file-type "ibin")
TB>   :fasl-file-type "bin"))

Kripke frames?

                                        Juliusz