From: lucky_therock
Subject: knowledge base in FOL
Date: 
Message-ID: <1177639483.085952.154940@b40g2000prd.googlegroups.com>
well am newbie here in LISP..!! so i wanna have to make a code for
knowledge base in first order logic where all facts are horn clauses
and input to the program are sequence of keywords..!! please help me
out in writing functions for it.

From: D Herring
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <Y4ednYP1upXS7KzbnZ2dnUVZ_jidnZ2d@comcast.com>
lucky_therock wrote:
> well am newbie here in LISP..!! so i wanna have to make a code for
> knowledge base in first order logic where all facts are horn clauses
> and input to the program are sequence of keywords..!! please help me
> out in writing functions for it.

http://norvig.com/paip.html
From: Thomas A. Russ
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <ymislalxr2i.fsf@sevak.isi.edu>
lucky_therock <·················@gmail.com> writes:

> well am newbie here in LISP..!! so i wanna have to make a code for
> knowledge base in first order logic where all facts are horn clauses
> and input to the program are sequence of keywords..!! please help me
> out in writing functions for it.

Well, you could get an already built one by looking for Prolog
implementation in Common Lisp:
   <http://www.faqs.org/faqs/lisp-faq/part6/section-5.html>

If you don't mind not being restricted to Horn clauses, then there's 
 
   <http://www.isi.edu/isd/LOOM/PowerLoom>

If you absolutely feel you have to write it yourself, there was the
other poster's suggestion of Peter Norvig's code.  If you are interested
in this stuff, you should get Peter Norvig's book, too.  I strongly
recommend it as worthwhile to read.

-- 
Thomas A. Russ,  USC/Information Sciences Institute
From: Mark Tarver
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <1177759264.053261.273920@u30g2000hsc.googlegroups.com>
On 27 Apr, 03:04, lucky_therock <·················@gmail.com> wrote:
> well am newbie here in LISP..!! so i wanna have to make a code for
> knowledge base in first order logic where all facts are horn clauses
> and input to the program are sequence of keywords..!! please help me
> out in writing functions for it.

OK; check out www.lambdassociates.org/prolog.htm for a Prolog in Lisp
which allows embedded function calls.  This is actually used as the
object
code from the Qi type checker.

If you want to code it yourself then check out the Abstract
Unification Machine
(AUM) http://www.lambdassociates.org/aum.pdf which generates virtual
machine
instructions from an extended lambda calculus for compiling Horn
clauses.
The paper gives the CLI (Current Lisp Implementation) of AUM
instructions
which is used in Qi.

Horn clauses are not complete for FOL so if you want that you need to
extend
the model.  This is not hard - look up PTTP in http://www.ai.sri.com/~stickel/pttp.html.

Mark
From: Mark Tarver
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <1177769842.903803.170760@n59g2000hsh.googlegroups.com>
On 27 Apr, 03:04, lucky_therock <·················@gmail.com> wrote:
> well am newbie here in LISP..!! so i wanna have to make a code for
> knowledge base in first order logic where all facts are horn clauses
> and input to the program are sequence of keywords..!! please help me
> out in writing functions for it.

I'm guessing what you want is a Prolog interpreter - a much smaller
deal than what I had assumed.

I do have one of these - written in Qi though but not in Lisp.  It was
put together for teaching students at Stony Brook.  However you can
run it through the Qi compiler and get the Lisp.  Note if this is
homework then your Lisp code will look decidedly machine-like (no
surprise) and you won't get it past your instructor nor will it run
straight away without some Qi system functions.  But the Qi program
may give you some ideas about how to write it yourself.  Here it is
(hope formatting is OK)

Mark

\Tiny Prolog in Qi\

\Invoke Tiny Prolog\
(define tinyprolog
  -> (do (output "~%Tiny Prolog~%")
         (tiny-prolog-loop)))

\Prolog query-deduce-answer loop\
(define tiny-prolog-loop
  -> (do (tiny-prolog-evaluate (tiny-prolog-read) (value *clauses*))
         (tiny-prolog-loop)))

\Read in input and produce answer.\
(define tiny-prolog-read
  -> (do (output "~%?- ") (insert_answer_literal (input))))

\Put in an answer literal\
(define insert_answer_literal
  Goal -> [Goal | (answer-literal (variables-in Goal))])

\Find the variables in an expression\
(define variables-in
  X -> [X]	where (variable? X)
  [X | Y] -> (union (variables-in X) (variables-in Y))
  _ -> [])

\Make an answer literal\
(define answer-literal
  [] -> []
  X -> [[answer | X]])

\Evaluate the query - Tiny Prolog reads in files of clauses.\
(define tiny-prolog-evaluate
  [[consult Filename] | _] _
  -> (do (set *clauses* (append (read-file Filename) (value
*clauses*)))
         (output "yes~%"))
  Goals Clauses <- (prolog-evaluate-help Goals Clauses Clauses [])
  _ _ -> (output "no~%"))

(define prolog-evaluate-help
\If answer literal - then show answer.\
  [[answer | Answers]] _ _ Bindings
  -> (do (show-answer Answers Bindings)
         (if (y-or-n? "~%More? ")
             #\Escape
             (output "yes~%")))
 \If goals solved - print yes.\
  [] _ _ _ -> (output "yes~%")
  \Try to solve the first goal with the first clauses in the KB
   if unification fails - then skip to the next line in this function
   else recurse with the new goals.\
  [Goal | Goals] [Clause | _] AllClauses Bindings
  <- (let NewClause (st Clause Clause)
        (let Mgu (unify (deref Goal Bindings) (head NewClause)
Bindings)
           (if (= Mgu fail)
               #\Escape
               (prolog-evaluate-help (append (body NewClause) Goals)
                                     AllClauses
                                     AllClauses
                                     Mgu))))
  \Skip the first clause and try the rest.\
  Goals [_ | Clauses] AllClauses Bindings
  -> (prolog-evaluate-help Goals Clauses AllClauses Bindings)
  \Just fail if you get here!\
  _ _ _ _ -> #\Escape)

\The body of the clause\
(define body
  [_ <= | Body] -> Body)

\Standardise a clause apart\
(define st
  X StClause -> (subst (gensym "X") X StClause) where (variable? X)
  [X | Y] StClause -> (st X (st Y StClause))
  _ StClause -> StClause)

\Print the answer\
(define show-answer
  [] _ -> []
  [X | Answers] Bindings
 -> (do (output "~%~A = ~A~%" X (deref X Bindings))
          (show-answer Answers Bindings)))

\Unify two terms\
(define unify
  X X Mgu -> Mgu
  [X | Y] [W | Z] Mgu
  -> (let NewMgu (unify (deref X Mgu) (deref W Mgu) Mgu)
                            (if (= NewMgu fail)
                                 fail
                                (unify Y Z NewMgu)))
  X Y Mgu -> [[X Y] | Mgu]
             where (and (variable? X) (not (occurs? X Y)))
  Y X Mgu -> [[X Y] | Mgu]
       where (and (variable? X) (not (occurs? X Y)))
  _ _ _ -> fail)

\Dereference a variable\
(define deref
  [X | Y] Mgu -> [(deref X Mgu) | (deref Y Mgu)]
  X Mgu -> (let Val (assoc X Mgu)
              (if (empty? Val) X (deref (head (tail Val)) Mgu))))

\Occurs check\
(define occurs?
  X X -> true
  X [Y | Z] -> (or (occurs? X Y) (occurs? X Z))
  _ _ -> false)

\Sample set of clauses\
(set *clauses* [   [[member X [X | Y]] <=]
                   [[member X [Y | Z]] <= [member X Z]]

                   [[append [] X X] <=]
                   [[append [X | Y] W [X | Z]] <= [append Y W Z]]])

===============================================
FYI - in the outputted Lisp it is

(DEFUN tinyprolog NIL (do (output "~%Tiny Prolog~%") (tiny-prolog-
loop)))

(DEFUN tiny-prolog-loop NIL
 (do (tiny-prolog-evaluate (tiny-prolog-read) *clauses*) (tiny-prolog-
loop)))

(DEFUN tiny-prolog-read NIL
 (do (output "~%?- ") (insert_answer_literal (input))))

(DEFUN insert_answer_literal (V6011)
 (CONS V6011 (answer-literal (variables-in V6011))))

(DEFUN variables-in (V6016)
 (COND ((qi::wrapper (variable? V6016)) (CONS V6016 NIL))
  ((CONSP V6016)
   (THE LIST (union (variables-in (CAR V6016)) (variables-in (CDR
V6016)))))
  (T NIL)))

(DEFUN answer-literal (V6018)
 (COND ((NULL V6018) NIL) (T (CONS (CONS 'answer V6018) NIL))))

(DEFUN tiny-prolog-evaluate (V6032 V6033)
 (PROG (choicepoint6031)
  (RETURN
   (COND
    ((AND (CONSP V6032) (CONSP (CAR V6032)) (EQ 'consult (CAR (CAR
V6032)))
      (CONSP (CDR (CAR V6032))) (NULL (CDR (CDR (CAR V6032)))))
     (do
      (SETQ *clauses*
       (APPEND (THE LIST (read-file (CAR (CDR (CAR V6032)))))
*clauses*))
      (output "yes~%")))
    ((qi::wrapper
      (not
       (qi::escape?
        (SETQ choicepoint6031 (prolog-evaluate-help V6032 V6033 V6033
NIL)))))
     choicepoint6031)
    (T (output "no~%"))))))

(DEFUN prolog-evaluate-help (V6065 V6066 V6067 V6068)
 (PROG (choicepoint6064)
  (RETURN
   (COND
    ((AND (CONSP V6065) (CONSP (CAR V6065)) (EQ 'answer (CAR (CAR
V6065)))
      (NULL (CDR V6065)))
     (do (show-answer (CDR (CAR V6065)) V6068)
      (IF (EQ 'true (THE SYMBOL (y-or-n? "~%More? "))) qi::*qi-failure-
object*
       (output "yes~%"))))
    ((NULL V6065) (output "yes~%"))
    ((AND (CONSP V6065) (CONSP V6066)
      (qi::wrapper
       (not
        (qi::escape?
         (SETQ choicepoint6064
          (LET ((NewClause (st (CAR V6066) (CAR V6066))))
           (LET
            ((Mgu (unify (deref (CAR V6065) V6068) (head NewClause)
V6068)))
            (IF (EQ 'true (qi_= Mgu 'fail)) qi::*qi-failure-object*
             (prolog-evaluate-help (APPEND (body NewClause) (CDR
V6065)) V6067
              V6067 Mgu)))))))))
     choicepoint6064)
    ((CONSP V6066) (prolog-evaluate-help V6065 (CDR V6066) V6067
V6068))
    (T qi::*qi-failure-object*)))))

(DEFUN body (V6073)
 (COND
  ((AND (CONSP V6073) (CONSP (CDR V6073)) (EQ 'qi_<= (CAR (CDR
V6073))))
   (CDR (CDR V6073)))
  (T (qi::f_error 'body))))

(DEFUN st (V6078 V6079)
 (COND
  ((qi::wrapper (variable? V6078))
   (subst (THE SYMBOL (gensym "X")) V6078 V6079))
  ((CONSP V6078) (st (CAR V6078) (st (CDR V6078) V6079))) (T V6079)))

(DEFUN show-answer (V6082 V6083)
 (COND ((NULL V6082) NIL)
  ((CONSP V6082)
   (LET* ((V6084 (CAR V6082)))
    (do (output "~%~A = ~A~%" V6084 (deref V6084 V6083))
     (show-answer (CDR V6082) V6083))))
  (T (qi::f_error 'show-answer))))

(DEFUN unify (V6098 V6099 V6100)
 (COND ((qi::wrapper (qi_= V6098 V6099)) V6100)
  ((AND (CONSP V6098) (CONSP V6099))
   (LET
    ((NewMgu
      (unify (deref (CAR V6098) V6100) (deref (CAR V6099) V6100)
V6100)))
    (IF (EQ 'true (qi_= NewMgu 'fail)) 'fail
     (unify (CDR V6098) (CDR V6099) NewMgu))))
  ((qi::wrapper (and (variable? V6098) (not (occurs? V6098 V6099))))
   (CONS (CONS V6098 (CONS V6099 NIL)) V6100))
  ((qi::wrapper (and (variable? V6099) (not (occurs? V6099 V6098))))
   (CONS (CONS V6099 (CONS V6098 NIL)) V6100))
  (T 'fail)))

(DEFUN deref (V6101 V6102)
 (COND
  ((CONSP V6101) (CONS (deref (CAR V6101) V6102) (deref (CDR V6101)
V6102)))
  (T
   (LET ((Val (assoc V6101 V6102)))
    (IF (EQ 'true (THE SYMBOL (empty? Val))) V6101
     (deref (head (THE LIST (tail Val))) V6102))))))

(DEFUN occurs? (V6115 V6116)
 (COND ((qi::wrapper (qi_= V6115 V6116)) 'true)
  ((CONSP V6116)
   (THE SYMBOL (or (occurs? V6115 (CAR V6116)) (occurs? V6115 (CDR
V6116)))))
  (T 'false)))
From: Mark Tarver
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <1177770228.658814.28210@e65g2000hsc.googlegroups.com>
On 27 Apr, 03:04, lucky_therock <·················@gmail.com> wrote:
> well am newbie here in LISP..!! so i wanna have to make a code for
> knowledge base in first order logic where all facts are horn clauses
> and input to the program are sequence of keywords..!! please help me
> out in writing functions for it.

I should have added a test run

(83-) (tinyprolog)

Tiny Prolog

?- [append X Y [1 2 3 4]]

X = []

Y = [1 2 3 4]

More?  (y/n) y

X = [1]

Y = [2 3 4]

More?  (y/n) y

X = [1 2]

Y = [3 4]

More?  (y/n) y

X = [1 2 3]

Y = [4]

More?  (y/n) y

X = [1 2 3 4]

Y = []

More?  (y/n) y
no

?- [member 1 [X]]

X = 1

More?  (y/n) y
no

?- [member 1 [0 3 4]]
no

?-

Mark
From: Frank Buss
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <zy1f35r8g0bk.94415qbqexwq.dlg@40tude.net>
lucky_therock wrote:

> well am newbie here in LISP..!! so i wanna have to make a code for
> knowledge base in first order logic where all facts are horn clauses
> and input to the program are sequence of keywords..!! please help me
> out in writing functions for it.

This sounds like a homework, because a similar problem were posted some
time ago (being a teacher looks like an easy job...). I assume the hints
for reading PAIP or using Prolog weren't very helpful for you, because as a
Lisp newbie you'll need at least some weeks to understand it (and as a
programmer newbie some months). But your problem is much simpler.

Usually we don't post solutions to homeworks (only if we want to fool
students, because teachers will see it immediatly that you didn't wrote it
yourself), but if you show some engagement, some code and where your
problems are, we'll help.

-- 
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
From: Mark Tarver
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <1177767568.133748.140740@q75g2000hsh.googlegroups.com>
On 28 Apr, 13:11, Frank Buss <····@frank-buss.de> wrote:
> lucky_therock wrote:
> > well am newbie here in LISP..!! so i wanna have to make a code for
> > knowledge base in first order logic where all facts are horn clauses
> > and input to the program are sequence of keywords..!! please help me
> > out in writing functions for it.
>
> This sounds like a homework, because a similar problem were posted some
> time ago (being a teacher looks like an easy job...). I assume the hints
> for reading PAIP or using Prolog weren't very helpful for you, because as a
> Lisp newbie you'll need at least some weeks to understand it (and as a
> programmer newbie some months). But your problem is much simpler.
>
> Usually we don't post solutions to homeworks (only if we want to fool
> students, because teachers will see it immediatly that you didn't wrote it
> yourself), but if you show some engagement, some code and where your
> problems are, we'll help.
>
> --
> Frank Buss, ····@frank-buss.dehttp://www.frank-buss.de,http://www.it4-systems.de

Actually yes, thinking about it, if this guy is a newbie then building
a Prolog compiler is rather a tough assignment.  I expect what he
wants is a Prolog interpreter.

Mark
From: Frank Buss
Subject: Re: knowledge base in FOL
Date: 
Message-ID: <18gtymvm6xmoq.1jp637n37voi9.dlg@40tude.net>
Mark Tarver wrote:

> Actually yes, thinking about it, if this guy is a newbie then building
> a Prolog compiler is rather a tough assignment.  I expect what he
> wants is a Prolog interpreter.

You are right, writing a Prolog interpreter is no problem at all for a Lisp
newbie and you certainly need it to solve this problem :-)

-- 
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de