From: ·············@gmail.com
Subject: Another Lisp problem
Date: 
Message-ID: <6f7e1956-5de5-429f-aeb1-900e75395dbe@i37g2000hsd.googlegroups.com>
> Write code that will answer if the given sentence S of the
> form A --> B is entailed
> by a propositional KB that consists of such sentences.
> Your program should have two inputs: S and the KB.
> KB will contain sentences that are in the form X --> Y only.
> A,B,X and Y are propositions or negated propositions only.

You may represent the KB a -> b, b -> c, m -> n as
((a b) (b c) (m n)). You can create a copy of the KB and fatten
the copy with additional sentences entailed by the previous copy.
For example, the KB also entails (a c) (which is my Lisp
representation
for a --> c). So the fattened copy will be
((a b) (b c) (m n) (a c)). Now see if the fattened copy has
(x y) (y k) and if so, fatten the copy further by adding
( x k). You will reach a point where the fattening is impossible
(like the transitive closure of relations). Then check if given
sentence is in the fattest copy. If so, it is entailed by the KB
else it is not.

From: Slobodan Blazeski
Subject: Re: Another Lisp problem
Date: 
Message-ID: <a62de365-ffb5-4ebf-b61b-434941b9f690@l1g2000hsa.googlegroups.com>
On Nov 20, 3:53 pm, ·············@gmail.com wrote:
> > Write code that will answer if the given sentence S of the
> > form A --> B is entailed
> > by a propositional KB that consists of such sentences.
> > Your program should have two inputs: S and the KB.
> > KB will contain sentences that are in the form X --> Y only.
> > A,B,X and Y are propositions or negated propositions only.
>
> You may represent the KB a -> b, b -> c, m -> n as
> ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> the copy with additional sentences entailed by the previous copy.
> For example, the KB also entails (a c) (which is my Lisp
> representation
> for a --> c). So the fattened copy will be
> ((a b) (b c) (m n) (a c)). Now see if the fattened copy has
> (x y) (y k) and if so, fatten the copy further by adding
> ( x k). You will reach a point where the fattening is impossible
> (like the transitive closure of relations). Then check if given
> sentence is in the fattest copy. If so, it is entailed by the KB
> else it is not.

Write the test cases, I don't understand  what are you trying to say
nor what the problem is .
What book do you use for learning lisp?

Slobodan
From: Mark Tarver
Subject: Re: Another Lisp problem
Date: 
Message-ID: <7df68bde-90bd-4281-9013-9dccc23c9bbf@l22g2000hsc.googlegroups.com>
On 20 Nov, 16:18, Slobodan Blazeski <·················@gmail.com>
wrote:
> On Nov 20, 3:53 pm, ·············@gmail.com wrote:
>
>
>
>
>
> > > Write code that will answer if the given sentence S of the
> > > form A --> B is entailed
> > > by a propositional KB that consists of such sentences.
> > > Your program should have two inputs: S and the KB.
> > > KB will contain sentences that are in the form X --> Y only.
> > > A,B,X and Y are propositions or negated propositions only.
>
> > You may represent the KB a -> b, b -> c, m -> n as
> > ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> > the copy with additional sentences entailed by the previous copy.
> > For example, the KB also entails (a c) (which is my Lisp
> > representation
> > for a --> c). So the fattened copy will be
> > ((a b) (b c) (m n) (a c)). Now see if the fattened copy has
> > (x y) (y k) and if so, fatten the copy further by adding
> > ( x k). You will reach a point where the fattening is impossible
> > (like the transitive closure of relations). Then check if given
> > sentence is in the fattest copy. If so, it is entailed by the KB
> > else it is not.
>
> Write the test cases, I don't understand  what are you trying to say
> nor what the problem is .
> What book do you use for learning lisp?
>
> Slobodan- Hide quoted text -
>
> - Show quoted text -

He wants a foward-chaining reasoning engine that derives implications.

Mark
From: Mark Tarver
Subject: Re: Another Lisp problem
Date: 
Message-ID: <a7c0596d-f650-447c-a7ab-c2d25867ac80@d61g2000hsa.googlegroups.com>
On 20 Nov, 14:53, ·············@gmail.com wrote:
> > Write code that will answer if the given sentence S of the
> > form A --> B is entailed
> > by a propositional KB that consists of such sentences.
> > Your program should have two inputs: S and the KB.
> > KB will contain sentences that are in the form X --> Y only.
> > A,B,X and Y are propositions or negated propositions only.
>
> You may represent the KB a -> b, b -> c, m -> n as
> ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> the copy with additional sentences entailed by the previous copy.
> For example, the KB also entails (a c) (which is my Lisp
> representation
> for a --> c). So the fattened copy will be
> ((a b) (b c) (m n) (a c)). Now see if the fattened copy has
> (x y) (y k) and if so, fatten the copy further by adding
> ( x k). You will reach a point where the fattening is impossible
> (like the transitive closure of relations). Then check if given
> sentence is in the fattest copy. If so, it is entailed by the KB
> else it is not.

Here is an 11 line solution in Qi.  It uses the system fix which
iterates
a function over its argument until no change can be achieved.

(define atp
  KB S -> (element? S (fix fchain-kb KB)))

(define fchain-kb
  KB -> (mapcan (/. X (fchain X KB KB)) KB))

(define mapcan
  _ [] -> []
  F [X | Y] -> (append (F X) (mapcan F Y)))

(define fchain
  X [] _ -> [X]
  [X Y] [[Y Z] | _] KB -> [[X Y] [X Z]] where (not (element? [X Z]
KB))
  X [_ | Y] KB -> (fchain X Y KB))
________________________________________________
(15-) (atp [[a b] [b c] [c d]] [a d])
true

(16-) (atp [[a b] [b c] [c d]] [a e])
false

Its not hard to write the corresponding Lisp.

Mark
From: Kaz Kylheku
Subject: Re: Another Lisp problem
Date: 
Message-ID: <a0959440-b9d6-433a-955c-d81027806b43@a39g2000pre.googlegroups.com>
On Nov 20, 6:53 am, ·············@gmail.com wrote:
> > Write code that will answer if the given sentence S of the
> > form A --> B is entailed
> > by a propositional KB that consists of such sentences.
> > Your program should have two inputs: S and the KB.
> > KB will contain sentences that are in the form X --> Y only.
> > A,B,X and Y are propositions or negated propositions only.
>
> You may represent the KB a -> b, b -> c, m -> n as
> ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> the copy with additional sentences entailed by the previous copy.
> For example, the KB also entails (a c) (which is my Lisp
> representation
> for a --> c). So the fattened copy will be
> ((a b) (b c) (m n) (a c)).

I can see why you  might be attracted to this type of solution.

However, I would argue that it's a kind of optimization which
sacrifices space for time.

It can potentially explode the memory requirements by a huge factor.

Suppose you had a KB with N million entries in it, of this form:

  ((A B) (B C) (C D) ...)

The space of all possible (X Y) pairs is large. In fact it is N(N - 1)/
2.

Suppose that N is large, like say ten million entries. The ``fat''
knowledge base then contains 50,000,005,000,000 entries.

That's a huge freaking amount of memory.

In general, you rarely have the luxury of creating a database of all
possible answers to all possible search queries.

Now if you had that much memory, and you had some very tight real-time
requirements for searching, you might have an engineering case for
precomputing such a database and indexing it for rapid access.

The underlying problem is basically a graph search. Every entry of the
form A -> B is actually an edge of a graph joining vertices A and B.

The query X -> Y calls for a graph search which determines whether
there is a path from vertex X to vertex Y, either directly or through
any number of intermediate vertices.

You should look up algorithms for the representation of graphs and for
doing graph searching.
From: Rainer Joswig
Subject: Re: Another Lisp problem
Date: 
Message-ID: <joswig-3EADF3.15553720112007@news-europe.giganews.com>
In article 
<····································@i37g2000hsd.googlegroups.com>,
 ·············@gmail.com wrote:

> > Write code that will answer if the given sentence S of the
> > form A --> B is entailed
> > by a propositional KB that consists of such sentences.
> > Your program should have two inputs: S and the KB.
> > KB will contain sentences that are in the form X --> Y only.
> > A,B,X and Y are propositions or negated propositions only.
> 
> You may represent the KB a -> b, b -> c, m -> n as
> ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> the copy with additional sentences entailed by the previous copy.
> For example, the KB also entails (a c) (which is my Lisp
> representation
> for a --> c). So the fattened copy will be
> ((a b) (b c) (m n) (a c)). Now see if the fattened copy has
> (x y) (y k) and if so, fatten the copy further by adding
> ( x k). You will reach a point where the fattening is impossible
> (like the transitive closure of relations). Then check if given
> sentence is in the fattest copy. If so, it is entailed by the KB
> else it is not.

More homework?

Show your solution first.

-- 
http://lispm.dyndns.org/
From: ·············@gmail.com
Subject: Re: Another Lisp problem
Date: 
Message-ID: <3451b317-928c-443e-b785-0ebfc2bfd328@y43g2000hsy.googlegroups.com>
On Nov 20, 8:55 am, Rainer Joswig <······@lisp.de> wrote:
> In article
> <····································@i37g2000hsd.googlegroups.com>,
>
>
>
>  ·············@gmail.com wrote:
> > > Write code that will answer if the given sentence S of the
> > > form A --> B is entailed
> > > by a propositional KB that consists of such sentences.
> > > Your program should have two inputs: S and the KB.
> > > KB will contain sentences that are in the form X --> Y only.
> > > A,B,X and Y are propositions or negated propositions only.
>
> > You may represent the KB a -> b, b -> c, m -> n as
> > ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> > the copy with additional sentences entailed by the previous copy.
> > For example, the KB also entails (a c) (which is my Lisp
> > representation
> > for a --> c). So the fattened copy will be
> > ((a b) (b c) (m n) (a c)). Now see if the fattened copy has
> > (x y) (y k) and if so, fatten the copy further by adding
> > ( x k). You will reach a point where the fattening is impossible
> > (like the transitive closure of relations). Then check if given
> > sentence is in the fattest copy. If so, it is entailed by the KB
> > else it is not.
>
> More homework?
>
> Show your solution first.
>
> --http://lispm.dyndns.org/

Thats what ive come up with first
From: John Thingstad
Subject: Re: Another Lisp problem
Date: 
Message-ID: <op.t13tt6mmut4oq5@pandora.alfanett.no>
P� Tue, 20 Nov 2007 15:53:25 +0100, skrev <·············@gmail.com>:

>> Write code that will answer if the given sentence S of the
>> form A --> B is entailed
>> by a propositional KB that consists of such sentences.
>> Your program should have two inputs: S and the KB.
>> KB will contain sentences that are in the form X --> Y only.
>> A,B,X and Y are propositions or negated propositions only.
>
> You may represent the KB a -> b, b -> c, m -> n as
> ((a b) (b c) (m n)). You can create a copy of the KB and fatten
> the copy with additional sentences entailed by the previous copy.
> For example, the KB also entails (a c) (which is my Lisp
> representation
> for a --> c). So the fattened copy will be
> ((a b) (b c) (m n) (a c)). Now see if the fattened copy has
> (x y) (y k) and if so, fatten the copy further by adding
> ( x k). You will reach a point where the fattening is impossible
> (like the transitive closure of relations). Then check if given
> sentence is in the fattest copy. If so, it is entailed by the KB
> else it is not.

Now that's a tough one so perhaps you could use some help.
Here is what I came up with.
It follows the recommendations given.
A more efficent way to do this for a large set is to view the relations as  
a graph and only study the ways to get from one symbol to the next instead  
of going over the entire set. This is called the RETE algorithm.

(defpackage :my-user (:use :cl :iterate))

(in-package :my-user)

(defparameter test-data '((a b) (b c) (m n)))

(defstruct (clause (:type list)) predicate conclusion)

(defun collect-transition (p1 list)
   (declare (type (clause p1)))
   (iter
     (for (the clause p2) in list)
     (when (equalp (clause-predicate p2)
                   (clause-conclusion p1))
       (collect (make-clause
                 :predicate (clause-predicate p1)
                 :conclusion (clause-conclusion p2))))))

(defun collect-transitions (list)
   (let ((transition list))
     (iter
       (for ((the clause p1) . sublist) on transition)
       (setf transition
             (union transition
                    (collect-transition p1 sublist)
                    :test #'equalp)))
     transition))

(defun transitive-closure (list)
   (let ((old-transitions)
         (transitions list))
     (iter
       (setf old-transitions transitions
             transitions (collect-transitions transitions))
       (never (equalp old-transitions transitions)))
     transitions))

(defun match (clause list)
   (find-if
    (lambda (element) (equal clause element))
    (transitive-closure list)))

Examples:

MY-USER 99 > (match '(a b) '((a b) (b c) (c d)))
(A B)

MY-USER 100 > (match '(c d) '((a b) (b c) (c d)))
(C D)

MY-USER 101 > (match '(a d) '((a b) (b c) (c d)))
(A D)

MY-USER 102 > (match '(a c) '((a b) (b c) (c d)))
(A C)

MY-USER 103 > (match '(a e) '((a b) (b c) (c d)))
NIL

MY-USER 104 > (match '(a c) test-data)
(A C)

MY-USER 105 > (match '(m n) test-data)
(M N)

MY-USER 106 > (match '(a d) test-data)
NIL


--------------
John Thingstad
From: John Thingstad
Subject: Re: Another Lisp problem
Date: 
Message-ID: <op.t13x4ihput4oq5@pandora.alfanett.no>
P� Tue, 20 Nov 2007 20:02:20 +0100, skrev John Thingstad  
<·······@online.no>:

>
> (defun collect-transitions (list)
>    (let ((transition list))
>      (iter
>        (for ((the clause p1) . sublist) on transition)
>        (setf transition
>              (union transition
>                     (collect-transition p1 sublist)
>                     :test #'equalp)))
>      transition))
>

urr.. This seems a bit more sane.

(defun collect-transitions (list)
   (let ((transition (copy-list list)))
     (iter
       (for ((the clause p1) . sublist) on list)
       (setf transition
             (union transition
                    (collect-transition p1 sublist)
                    :test #'equalp)))
     transition))

--------------
John Thingstad