Forward-chaining beneath first search in lisp












0















i'm trying to find the problem in fugiring out the stack over flow problem
the alogrithm is clear but it and the recursive call is made in an if satetment so i can't figure out why is it going bad 



(defparameter BF '(B C) )

(defparameter BR '((R1(B D E) F )(R2( D G) A )(R3(C F) A )(R4(C) D)

                     (R5(D ) E )(R6(A) H ) (R7(B ) X) (R8(X C) A ) ))

(defun chain_av (BF BR F)

(loop 

    (unless (member F BF)

      (dolist (R  BR)

        (when (actionable  R BF)

          (remove R BR)

          (append BF (conclusion-part R)))

      (if (member F BF) (return "yes")

        (or(chain_av BF BR F) (return nil)))))))





(defun conclusion-part( r)

(caddr r)

)

(write (chain_av BF BR 'H ))

    (defun actionable (r facts)

        (let ((ok t))

            (dolist (p (cadr r) ok)

                (if (not (member p facts))

                    (setq ok nil)))

                ok))


and i'm still not sure if it's really beneath first search
and should'i prove that by having a variable that keeps track of the elements that it when by
and thanks in advance






lisp common-lisp stack-overflow







share|improve this question




















  • 4





    to ask a question you need to post formatted code. Your code is not formatted. Second: you need a description of the error and the code you used, which causes this error and a reproducible way.

    – Rainer Joswig
    Jan 1 at 20:26








  • 1





    The code uses free variables: maybe there was a problem when renaming variables for this question (e.g. "but" should be "F"?). What is part_conclusion? Should BF be *BF*?

    – coredump
    Jan 1 at 20:30











  • the stars have nothing to do and part-conclusion is missing an R

    – saitama
    Jan 1 at 20:58











  • i'm trying to make a inference engine algorthim and the rules A and B => C are represented by (R1 ( A B) C) ( it's a valid way to represent rules in a rule based expert system )

    – saitama
    Jan 1 at 21:23








  • 1





    append returns a new list; it doesn't modify any of its arguments. If a Lisp program calls append such that the return value is ignored, that call is useless.

    – Kaz
    Jan 2 at 6:57


















0















i'm trying to find the problem in fugiring out the stack over flow problem
the alogrithm is clear but it and the recursive call is made in an if satetment so i can't figure out why is it going bad 



(defparameter BF '(B C) )

(defparameter BR '((R1(B D E) F )(R2( D G) A )(R3(C F) A )(R4(C) D)

                     (R5(D ) E )(R6(A) H ) (R7(B ) X) (R8(X C) A ) ))

(defun chain_av (BF BR F)

(loop 

    (unless (member F BF)

      (dolist (R  BR)

        (when (actionable  R BF)

          (remove R BR)

          (append BF (conclusion-part R)))

      (if (member F BF) (return "yes")

        (or(chain_av BF BR F) (return nil)))))))





(defun conclusion-part( r)

(caddr r)

)

(write (chain_av BF BR 'H ))

    (defun actionable (r facts)

        (let ((ok t))

            (dolist (p (cadr r) ok)

                (if (not (member p facts))

                    (setq ok nil)))

                ok))


and i'm still not sure if it's really beneath first search
and should'i prove that by having a variable that keeps track of the elements that it when by
and thanks in advance






lisp common-lisp stack-overflow







share|improve this question




















  • 4





    to ask a question you need to post formatted code. Your code is not formatted. Second: you need a description of the error and the code you used, which causes this error and a reproducible way.

    – Rainer Joswig
    Jan 1 at 20:26








  • 1





    The code uses free variables: maybe there was a problem when renaming variables for this question (e.g. "but" should be "F"?). What is part_conclusion? Should BF be *BF*?

    – coredump
    Jan 1 at 20:30











  • the stars have nothing to do and part-conclusion is missing an R

    – saitama
    Jan 1 at 20:58











  • i'm trying to make a inference engine algorthim and the rules A and B => C are represented by (R1 ( A B) C) ( it's a valid way to represent rules in a rule based expert system )

    – saitama
    Jan 1 at 21:23








  • 1





    append returns a new list; it doesn't modify any of its arguments. If a Lisp program calls append such that the return value is ignored, that call is useless.

    – Kaz
    Jan 2 at 6:57
















0












0








0








i'm trying to find the problem in fugiring out the stack over flow problem
the alogrithm is clear but it and the recursive call is made in an if satetment so i can't figure out why is it going bad 



(defparameter BF '(B C) )

(defparameter BR '((R1(B D E) F )(R2( D G) A )(R3(C F) A )(R4(C) D)

                     (R5(D ) E )(R6(A) H ) (R7(B ) X) (R8(X C) A ) ))

(defun chain_av (BF BR F)

(loop 

    (unless (member F BF)

      (dolist (R  BR)

        (when (actionable  R BF)

          (remove R BR)

          (append BF (conclusion-part R)))

      (if (member F BF) (return "yes")

        (or(chain_av BF BR F) (return nil)))))))





(defun conclusion-part( r)

(caddr r)

)

(write (chain_av BF BR 'H ))

    (defun actionable (r facts)

        (let ((ok t))

            (dolist (p (cadr r) ok)

                (if (not (member p facts))

                    (setq ok nil)))

                ok))


and i'm still not sure if it's really beneath first search
and should'i prove that by having a variable that keeps track of the elements that it when by
and thanks in advance






lisp common-lisp stack-overflow







share|improve this question
















i'm trying to find the problem in fugiring out the stack over flow problem
the alogrithm is clear but it and the recursive call is made in an if satetment so i can't figure out why is it going bad 



(defparameter BF '(B C) )

(defparameter BR '((R1(B D E) F )(R2( D G) A )(R3(C F) A )(R4(C) D)

                     (R5(D ) E )(R6(A) H ) (R7(B ) X) (R8(X C) A ) ))

(defun chain_av (BF BR F)

(loop 

    (unless (member F BF)

      (dolist (R  BR)

        (when (actionable  R BF)

          (remove R BR)

          (append BF (conclusion-part R)))

      (if (member F BF) (return "yes")

        (or(chain_av BF BR F) (return nil)))))))





(defun conclusion-part( r)

(caddr r)

)

(write (chain_av BF BR 'H ))

    (defun actionable (r facts)

        (let ((ok t))

            (dolist (p (cadr r) ok)

                (if (not (member p facts))

                    (setq ok nil)))

                ok))


and i'm still not sure if it's really beneath first search
and should'i prove that by having a variable that keeps track of the elements that it when by
and thanks in advance






lisp common-lisp stack-overflow




lisp common-lisp stack-overflow






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Jan 2 at 9:36









Rainer Joswig

112k8169286




112k8169286










asked Jan 1 at 20:03









saitamasaitama

64




64








  • 4





    to ask a question you need to post formatted code. Your code is not formatted. Second: you need a description of the error and the code you used, which causes this error and a reproducible way.

    – Rainer Joswig
    Jan 1 at 20:26








  • 1





    The code uses free variables: maybe there was a problem when renaming variables for this question (e.g. "but" should be "F"?). What is part_conclusion? Should BF be *BF*?

    – coredump
    Jan 1 at 20:30











  • the stars have nothing to do and part-conclusion is missing an R

    – saitama
    Jan 1 at 20:58











  • i'm trying to make a inference engine algorthim and the rules A and B => C are represented by (R1 ( A B) C) ( it's a valid way to represent rules in a rule based expert system )

    – saitama
    Jan 1 at 21:23








  • 1





    append returns a new list; it doesn't modify any of its arguments. If a Lisp program calls append such that the return value is ignored, that call is useless.

    – Kaz
    Jan 2 at 6:57
















  • 4





    to ask a question you need to post formatted code. Your code is not formatted. Second: you need a description of the error and the code you used, which causes this error and a reproducible way.

    – Rainer Joswig
    Jan 1 at 20:26








  • 1





    The code uses free variables: maybe there was a problem when renaming variables for this question (e.g. "but" should be "F"?). What is part_conclusion? Should BF be *BF*?

    – coredump
    Jan 1 at 20:30











  • the stars have nothing to do and part-conclusion is missing an R

    – saitama
    Jan 1 at 20:58











  • i'm trying to make a inference engine algorthim and the rules A and B => C are represented by (R1 ( A B) C) ( it's a valid way to represent rules in a rule based expert system )

    – saitama
    Jan 1 at 21:23








  • 1





    append returns a new list; it doesn't modify any of its arguments. If a Lisp program calls append such that the return value is ignored, that call is useless.

    – Kaz
    Jan 2 at 6:57










4




4





to ask a question you need to post formatted code. Your code is not formatted. Second: you need a description of the error and the code you used, which causes this error and a reproducible way.

– Rainer Joswig
Jan 1 at 20:26







to ask a question you need to post formatted code. Your code is not formatted. Second: you need a description of the error and the code you used, which causes this error and a reproducible way.

– Rainer Joswig
Jan 1 at 20:26






1




1





The code uses free variables: maybe there was a problem when renaming variables for this question (e.g. "but" should be "F"?). What is part_conclusion? Should BF be *BF*?

– coredump
Jan 1 at 20:30





The code uses free variables: maybe there was a problem when renaming variables for this question (e.g. "but" should be "F"?). What is part_conclusion? Should BF be *BF*?

– coredump
Jan 1 at 20:30













the stars have nothing to do and part-conclusion is missing an R

– saitama
Jan 1 at 20:58





the stars have nothing to do and part-conclusion is missing an R

– saitama
Jan 1 at 20:58













i'm trying to make a inference engine algorthim and the rules A and B => C are represented by (R1 ( A B) C) ( it's a valid way to represent rules in a rule based expert system )

– saitama
Jan 1 at 21:23







i'm trying to make a inference engine algorthim and the rules A and B => C are represented by (R1 ( A B) C) ( it's a valid way to represent rules in a rule based expert system )

– saitama
Jan 1 at 21:23






1




1





append returns a new list; it doesn't modify any of its arguments. If a Lisp program calls append such that the return value is ignored, that call is useless.

– Kaz
Jan 2 at 6:57







append returns a new list; it doesn't modify any of its arguments. If a Lisp program calls append such that the return value is ignored, that call is useless.

– Kaz
Jan 2 at 6:57














1 Answer
1






active

oldest

votes


















8














Here are some general remarks about some mistakes in your code, followed by hints about how to implement forward chaining.



Code formatting



It is important you format your code properly, otherwise you or your peers won't be able to read it back easily. See for example https://lisp-lang.org/style-guide/:



(defun conclusion-part( r)

(caddr r)

)


The above has parentheses on their own lines, which is very not idiomatic. Also, Common Lisp has a function named THIRD that is easier to understand than CADDR for most people. Indent properly and put parentheses at the end. Use an editor like Emacs which can indent the code automatically: that helps identifying cases where what you write is different from what you intended to write, because auto-indentation follows the list structure and can help spot misplaced parentheses.



(defun conclusion-part (rule)

  (third rule))


Accessor functions



What you did good is to define a conclusion-part accessor function to access part of your rule ad-hoc data structure. Having a distinct set of accessors that are not tied to a specific implementation helps, and is a good opportunity to introduce meaningful names. You should do the same for all parts of the rule (you use CADR directly elsewhere, which is not as clean).



For example (feel free to find better names):



(defun rule-name (rule) (first rule))

(defun rule-antecedent (rule) (second rule))

(defun rule-consequent (rule) (cddr rule))


Notice that rule-consequent is my rewrite of conclusion-part, except it always returns a list with a single element (can you see why?). This is useful later when you call append, and it is consistent with rule-antecedent which returns a list.



Actionability of rules



Functions that return either true or false are called predicates and are by convention suffixed with -p in Lisp (and -? in Scheme). You may or may not follow that rule, but please introduce more meaningful variable names. Here is how you could rewrite it:



(defun actionablep (rule facts)

  (dolist (term (rule-antecedent rule) t)

    (unless (member term facts)

      (return nil))))


Since you already know loop, you could also write:



(defun actionablep (rule facts)

  (loop

    :for term :in (rule-antecedent rule)

    :always (member term facts)))


Forward chaining



There are some problems here too:




  • you do not use the return value of REMOVE or APPEND, which are functions that are guaranteed to not mutate their arguments (unlike DELETE and NCONC, and even for those functions only the returned value matters, the ability that is granted to mutate the existing storage is implementation-defined and only there to allow efficient reuse of memory).


  • In some branch you want to return "yes", in another nil; CL might be dynamically typed, but there is no need for a string return value here.


  • A return form only exist the innermost nil block. In your case that means you return from the implicit block established by DOLIST, not the one from the LOOP. You could name your loop but this is in fact not necessary here, you can write the whole thing without return. More generally, you can have a purely functional approach.



Hint



I wrote a forward-chaining function, and traced it; in the REPL:



CL-USER> (trace forward-chaining)


Here is how I tested my implementation:



(forward-chaining '(B C)

                  '((R1 (B D E) F)

                    (R2 (D G) A)

                    (R3 (C F) A)

                    (R4 (C) D)

                    (R5 (D) E)

                    (R6 (A) H)

                    (R7 (B) X)

                    (R8 (X C) A))

                  'H)


I am testing the code with SBCL, the actual output might differ in your Lisp implementation:



  0: (FORWARD-CHAINING (B C) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R4 (C) D) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

    1: (FORWARD-CHAINING (B C D) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

      2: (FORWARD-CHAINING (B C D E) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

        3: (FORWARD-CHAINING (B C D E F) ((R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

          4: (FORWARD-CHAINING (B C D E F A) ((R2 (D G) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

            5: (FORWARD-CHAINING (B C D E F A H) ((R2 (D G) A) (R7 (B) X) (R8 (X C) A)) H)

            5: FORWARD-CHAINING returned (H)

          4: FORWARD-CHAINING returned (H)

        3: FORWARD-CHAINING returned (H)

      2: FORWARD-CHAINING returned (H)

    1: FORWARD-CHAINING returned (H)

  0: FORWARD-CHAINING returned (H)


The basic structure of the program is:



(defun forward-chaining (rules facts goal)

  (or ...

      (loop 

        for ... in ...

        thereis (and (actionablep ... ...)

                     (forward-chaining ... ... ...)))))


In other words: either the goal is already a known fact, or there is an actionable rule by which goal is transitively reachable. Note that you might have an infinite recursion if your rules are non-terminating.



The order by which you visit rules determines if your strategy is depth-first (always follow the last tried rule and progress from that one, using the list of rules as a stack), or breadth-first (apply all activable rules for a given fact, using the list of rules as a queue). I don't know where the term "beneath"-first search comes from, I found no serious reference from it (there is one paper that references Leiserson & Schardl 2010 when talking about beneath first search, but the referenced article has no mention of it, only breadth-first, which is well-known).






share|improve this answer


























  • can'u give me a hint how can'i guess the type of the search ( depth first or beneath first search ) and if i happen to formulate the code so it falls in one of these cases how can' i proove that ( is the code you tested depth first or beneath first )?

    – saitama
    Jan 1 at 22:28











  • No that you say it, I think my example is depth-first, I start from one fact and follow rules recursively before trying other rules at the same level of search. For breadth-first search, I guess that means all actionable rules at a given search level should be applied and the resulting facts appended at the end of the current facts, before entering the next fixpoint loop. I'll update the answer.

    – coredump
    Jan 1 at 22:49











  • I think that ,inorder to simulate the breadth-first search u need to go though the collected-factes and for each rule test if the goal exists in the facts base after activation it and empty the queue when you leave each level and so you can call the main function recursively with the updaed facts-base ( = facts + new-facts)

    – saitama
    Jan 2 at 14:19











  • cam anyone ell m what i the difference between depth first or bemath first ?

    – saitama
    Jan 7 at 10:14











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53998558%2fforward-chaining-beneath-first-search-in-lisp%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









8














Here are some general remarks about some mistakes in your code, followed by hints about how to implement forward chaining.



Code formatting



It is important you format your code properly, otherwise you or your peers won't be able to read it back easily. See for example https://lisp-lang.org/style-guide/:



(defun conclusion-part( r)

(caddr r)

)


The above has parentheses on their own lines, which is very not idiomatic. Also, Common Lisp has a function named THIRD that is easier to understand than CADDR for most people. Indent properly and put parentheses at the end. Use an editor like Emacs which can indent the code automatically: that helps identifying cases where what you write is different from what you intended to write, because auto-indentation follows the list structure and can help spot misplaced parentheses.



(defun conclusion-part (rule)

  (third rule))


Accessor functions



What you did good is to define a conclusion-part accessor function to access part of your rule ad-hoc data structure. Having a distinct set of accessors that are not tied to a specific implementation helps, and is a good opportunity to introduce meaningful names. You should do the same for all parts of the rule (you use CADR directly elsewhere, which is not as clean).



For example (feel free to find better names):



(defun rule-name (rule) (first rule))

(defun rule-antecedent (rule) (second rule))

(defun rule-consequent (rule) (cddr rule))


Notice that rule-consequent is my rewrite of conclusion-part, except it always returns a list with a single element (can you see why?). This is useful later when you call append, and it is consistent with rule-antecedent which returns a list.



Actionability of rules



Functions that return either true or false are called predicates and are by convention suffixed with -p in Lisp (and -? in Scheme). You may or may not follow that rule, but please introduce more meaningful variable names. Here is how you could rewrite it:



(defun actionablep (rule facts)

  (dolist (term (rule-antecedent rule) t)

    (unless (member term facts)

      (return nil))))


Since you already know loop, you could also write:



(defun actionablep (rule facts)

  (loop

    :for term :in (rule-antecedent rule)

    :always (member term facts)))


Forward chaining



There are some problems here too:




  • you do not use the return value of REMOVE or APPEND, which are functions that are guaranteed to not mutate their arguments (unlike DELETE and NCONC, and even for those functions only the returned value matters, the ability that is granted to mutate the existing storage is implementation-defined and only there to allow efficient reuse of memory).


  • In some branch you want to return "yes", in another nil; CL might be dynamically typed, but there is no need for a string return value here.


  • A return form only exist the innermost nil block. In your case that means you return from the implicit block established by DOLIST, not the one from the LOOP. You could name your loop but this is in fact not necessary here, you can write the whole thing without return. More generally, you can have a purely functional approach.



Hint



I wrote a forward-chaining function, and traced it; in the REPL:



CL-USER> (trace forward-chaining)


Here is how I tested my implementation:



(forward-chaining '(B C)

                  '((R1 (B D E) F)

                    (R2 (D G) A)

                    (R3 (C F) A)

                    (R4 (C) D)

                    (R5 (D) E)

                    (R6 (A) H)

                    (R7 (B) X)

                    (R8 (X C) A))

                  'H)


I am testing the code with SBCL, the actual output might differ in your Lisp implementation:



  0: (FORWARD-CHAINING (B C) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R4 (C) D) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

    1: (FORWARD-CHAINING (B C D) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

      2: (FORWARD-CHAINING (B C D E) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

        3: (FORWARD-CHAINING (B C D E F) ((R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

          4: (FORWARD-CHAINING (B C D E F A) ((R2 (D G) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

            5: (FORWARD-CHAINING (B C D E F A H) ((R2 (D G) A) (R7 (B) X) (R8 (X C) A)) H)

            5: FORWARD-CHAINING returned (H)

          4: FORWARD-CHAINING returned (H)

        3: FORWARD-CHAINING returned (H)

      2: FORWARD-CHAINING returned (H)

    1: FORWARD-CHAINING returned (H)

  0: FORWARD-CHAINING returned (H)


The basic structure of the program is:



(defun forward-chaining (rules facts goal)

  (or ...

      (loop 

        for ... in ...

        thereis (and (actionablep ... ...)

                     (forward-chaining ... ... ...)))))


In other words: either the goal is already a known fact, or there is an actionable rule by which goal is transitively reachable. Note that you might have an infinite recursion if your rules are non-terminating.



The order by which you visit rules determines if your strategy is depth-first (always follow the last tried rule and progress from that one, using the list of rules as a stack), or breadth-first (apply all activable rules for a given fact, using the list of rules as a queue). I don't know where the term "beneath"-first search comes from, I found no serious reference from it (there is one paper that references Leiserson & Schardl 2010 when talking about beneath first search, but the referenced article has no mention of it, only breadth-first, which is well-known).






share|improve this answer


























  • can'u give me a hint how can'i guess the type of the search ( depth first or beneath first search ) and if i happen to formulate the code so it falls in one of these cases how can' i proove that ( is the code you tested depth first or beneath first )?

    – saitama
    Jan 1 at 22:28











  • No that you say it, I think my example is depth-first, I start from one fact and follow rules recursively before trying other rules at the same level of search. For breadth-first search, I guess that means all actionable rules at a given search level should be applied and the resulting facts appended at the end of the current facts, before entering the next fixpoint loop. I'll update the answer.

    – coredump
    Jan 1 at 22:49











  • I think that ,inorder to simulate the breadth-first search u need to go though the collected-factes and for each rule test if the goal exists in the facts base after activation it and empty the queue when you leave each level and so you can call the main function recursively with the updaed facts-base ( = facts + new-facts)

    – saitama
    Jan 2 at 14:19











  • cam anyone ell m what i the difference between depth first or bemath first ?

    – saitama
    Jan 7 at 10:14
















8














Here are some general remarks about some mistakes in your code, followed by hints about how to implement forward chaining.



Code formatting



It is important you format your code properly, otherwise you or your peers won't be able to read it back easily. See for example https://lisp-lang.org/style-guide/:



(defun conclusion-part( r)

(caddr r)

)


The above has parentheses on their own lines, which is very not idiomatic. Also, Common Lisp has a function named THIRD that is easier to understand than CADDR for most people. Indent properly and put parentheses at the end. Use an editor like Emacs which can indent the code automatically: that helps identifying cases where what you write is different from what you intended to write, because auto-indentation follows the list structure and can help spot misplaced parentheses.



(defun conclusion-part (rule)

  (third rule))


Accessor functions



What you did good is to define a conclusion-part accessor function to access part of your rule ad-hoc data structure. Having a distinct set of accessors that are not tied to a specific implementation helps, and is a good opportunity to introduce meaningful names. You should do the same for all parts of the rule (you use CADR directly elsewhere, which is not as clean).



For example (feel free to find better names):



(defun rule-name (rule) (first rule))

(defun rule-antecedent (rule) (second rule))

(defun rule-consequent (rule) (cddr rule))


Notice that rule-consequent is my rewrite of conclusion-part, except it always returns a list with a single element (can you see why?). This is useful later when you call append, and it is consistent with rule-antecedent which returns a list.



Actionability of rules



Functions that return either true or false are called predicates and are by convention suffixed with -p in Lisp (and -? in Scheme). You may or may not follow that rule, but please introduce more meaningful variable names. Here is how you could rewrite it:



(defun actionablep (rule facts)

  (dolist (term (rule-antecedent rule) t)

    (unless (member term facts)

      (return nil))))


Since you already know loop, you could also write:



(defun actionablep (rule facts)

  (loop

    :for term :in (rule-antecedent rule)

    :always (member term facts)))


Forward chaining



There are some problems here too:




  • you do not use the return value of REMOVE or APPEND, which are functions that are guaranteed to not mutate their arguments (unlike DELETE and NCONC, and even for those functions only the returned value matters, the ability that is granted to mutate the existing storage is implementation-defined and only there to allow efficient reuse of memory).


  • In some branch you want to return "yes", in another nil; CL might be dynamically typed, but there is no need for a string return value here.


  • A return form only exist the innermost nil block. In your case that means you return from the implicit block established by DOLIST, not the one from the LOOP. You could name your loop but this is in fact not necessary here, you can write the whole thing without return. More generally, you can have a purely functional approach.



Hint



I wrote a forward-chaining function, and traced it; in the REPL:



CL-USER> (trace forward-chaining)


Here is how I tested my implementation:



(forward-chaining '(B C)

                  '((R1 (B D E) F)

                    (R2 (D G) A)

                    (R3 (C F) A)

                    (R4 (C) D)

                    (R5 (D) E)

                    (R6 (A) H)

                    (R7 (B) X)

                    (R8 (X C) A))

                  'H)


I am testing the code with SBCL, the actual output might differ in your Lisp implementation:



  0: (FORWARD-CHAINING (B C) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R4 (C) D) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

    1: (FORWARD-CHAINING (B C D) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

      2: (FORWARD-CHAINING (B C D E) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

        3: (FORWARD-CHAINING (B C D E F) ((R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

          4: (FORWARD-CHAINING (B C D E F A) ((R2 (D G) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

            5: (FORWARD-CHAINING (B C D E F A H) ((R2 (D G) A) (R7 (B) X) (R8 (X C) A)) H)

            5: FORWARD-CHAINING returned (H)

          4: FORWARD-CHAINING returned (H)

        3: FORWARD-CHAINING returned (H)

      2: FORWARD-CHAINING returned (H)

    1: FORWARD-CHAINING returned (H)

  0: FORWARD-CHAINING returned (H)


The basic structure of the program is:



(defun forward-chaining (rules facts goal)

  (or ...

      (loop 

        for ... in ...

        thereis (and (actionablep ... ...)

                     (forward-chaining ... ... ...)))))


In other words: either the goal is already a known fact, or there is an actionable rule by which goal is transitively reachable. Note that you might have an infinite recursion if your rules are non-terminating.



The order by which you visit rules determines if your strategy is depth-first (always follow the last tried rule and progress from that one, using the list of rules as a stack), or breadth-first (apply all activable rules for a given fact, using the list of rules as a queue). I don't know where the term "beneath"-first search comes from, I found no serious reference from it (there is one paper that references Leiserson & Schardl 2010 when talking about beneath first search, but the referenced article has no mention of it, only breadth-first, which is well-known).






share|improve this answer


























  • can'u give me a hint how can'i guess the type of the search ( depth first or beneath first search ) and if i happen to formulate the code so it falls in one of these cases how can' i proove that ( is the code you tested depth first or beneath first )?

    – saitama
    Jan 1 at 22:28











  • No that you say it, I think my example is depth-first, I start from one fact and follow rules recursively before trying other rules at the same level of search. For breadth-first search, I guess that means all actionable rules at a given search level should be applied and the resulting facts appended at the end of the current facts, before entering the next fixpoint loop. I'll update the answer.

    – coredump
    Jan 1 at 22:49











  • I think that ,inorder to simulate the breadth-first search u need to go though the collected-factes and for each rule test if the goal exists in the facts base after activation it and empty the queue when you leave each level and so you can call the main function recursively with the updaed facts-base ( = facts + new-facts)

    – saitama
    Jan 2 at 14:19











  • cam anyone ell m what i the difference between depth first or bemath first ?

    – saitama
    Jan 7 at 10:14














8












8








8







Here are some general remarks about some mistakes in your code, followed by hints about how to implement forward chaining.



Code formatting



It is important you format your code properly, otherwise you or your peers won't be able to read it back easily. See for example https://lisp-lang.org/style-guide/:



(defun conclusion-part( r)

(caddr r)

)


The above has parentheses on their own lines, which is very not idiomatic. Also, Common Lisp has a function named THIRD that is easier to understand than CADDR for most people. Indent properly and put parentheses at the end. Use an editor like Emacs which can indent the code automatically: that helps identifying cases where what you write is different from what you intended to write, because auto-indentation follows the list structure and can help spot misplaced parentheses.



(defun conclusion-part (rule)

  (third rule))


Accessor functions



What you did good is to define a conclusion-part accessor function to access part of your rule ad-hoc data structure. Having a distinct set of accessors that are not tied to a specific implementation helps, and is a good opportunity to introduce meaningful names. You should do the same for all parts of the rule (you use CADR directly elsewhere, which is not as clean).



For example (feel free to find better names):



(defun rule-name (rule) (first rule))

(defun rule-antecedent (rule) (second rule))

(defun rule-consequent (rule) (cddr rule))


Notice that rule-consequent is my rewrite of conclusion-part, except it always returns a list with a single element (can you see why?). This is useful later when you call append, and it is consistent with rule-antecedent which returns a list.



Actionability of rules



Functions that return either true or false are called predicates and are by convention suffixed with -p in Lisp (and -? in Scheme). You may or may not follow that rule, but please introduce more meaningful variable names. Here is how you could rewrite it:



(defun actionablep (rule facts)

  (dolist (term (rule-antecedent rule) t)

    (unless (member term facts)

      (return nil))))


Since you already know loop, you could also write:



(defun actionablep (rule facts)

  (loop

    :for term :in (rule-antecedent rule)

    :always (member term facts)))


Forward chaining



There are some problems here too:




  • you do not use the return value of REMOVE or APPEND, which are functions that are guaranteed to not mutate their arguments (unlike DELETE and NCONC, and even for those functions only the returned value matters, the ability that is granted to mutate the existing storage is implementation-defined and only there to allow efficient reuse of memory).


  • In some branch you want to return "yes", in another nil; CL might be dynamically typed, but there is no need for a string return value here.


  • A return form only exist the innermost nil block. In your case that means you return from the implicit block established by DOLIST, not the one from the LOOP. You could name your loop but this is in fact not necessary here, you can write the whole thing without return. More generally, you can have a purely functional approach.



Hint



I wrote a forward-chaining function, and traced it; in the REPL:



CL-USER> (trace forward-chaining)


Here is how I tested my implementation:



(forward-chaining '(B C)

                  '((R1 (B D E) F)

                    (R2 (D G) A)

                    (R3 (C F) A)

                    (R4 (C) D)

                    (R5 (D) E)

                    (R6 (A) H)

                    (R7 (B) X)

                    (R8 (X C) A))

                  'H)


I am testing the code with SBCL, the actual output might differ in your Lisp implementation:



  0: (FORWARD-CHAINING (B C) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R4 (C) D) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

    1: (FORWARD-CHAINING (B C D) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

      2: (FORWARD-CHAINING (B C D E) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

        3: (FORWARD-CHAINING (B C D E F) ((R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

          4: (FORWARD-CHAINING (B C D E F A) ((R2 (D G) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

            5: (FORWARD-CHAINING (B C D E F A H) ((R2 (D G) A) (R7 (B) X) (R8 (X C) A)) H)

            5: FORWARD-CHAINING returned (H)

          4: FORWARD-CHAINING returned (H)

        3: FORWARD-CHAINING returned (H)

      2: FORWARD-CHAINING returned (H)

    1: FORWARD-CHAINING returned (H)

  0: FORWARD-CHAINING returned (H)


The basic structure of the program is:



(defun forward-chaining (rules facts goal)

  (or ...

      (loop 

        for ... in ...

        thereis (and (actionablep ... ...)

                     (forward-chaining ... ... ...)))))


In other words: either the goal is already a known fact, or there is an actionable rule by which goal is transitively reachable. Note that you might have an infinite recursion if your rules are non-terminating.



The order by which you visit rules determines if your strategy is depth-first (always follow the last tried rule and progress from that one, using the list of rules as a stack), or breadth-first (apply all activable rules for a given fact, using the list of rules as a queue). I don't know where the term "beneath"-first search comes from, I found no serious reference from it (there is one paper that references Leiserson & Schardl 2010 when talking about beneath first search, but the referenced article has no mention of it, only breadth-first, which is well-known).






share|improve this answer















Here are some general remarks about some mistakes in your code, followed by hints about how to implement forward chaining.



Code formatting



It is important you format your code properly, otherwise you or your peers won't be able to read it back easily. See for example https://lisp-lang.org/style-guide/:



(defun conclusion-part( r)

(caddr r)

)


The above has parentheses on their own lines, which is very not idiomatic. Also, Common Lisp has a function named THIRD that is easier to understand than CADDR for most people. Indent properly and put parentheses at the end. Use an editor like Emacs which can indent the code automatically: that helps identifying cases where what you write is different from what you intended to write, because auto-indentation follows the list structure and can help spot misplaced parentheses.



(defun conclusion-part (rule)

  (third rule))


Accessor functions



What you did good is to define a conclusion-part accessor function to access part of your rule ad-hoc data structure. Having a distinct set of accessors that are not tied to a specific implementation helps, and is a good opportunity to introduce meaningful names. You should do the same for all parts of the rule (you use CADR directly elsewhere, which is not as clean).



For example (feel free to find better names):



(defun rule-name (rule) (first rule))

(defun rule-antecedent (rule) (second rule))

(defun rule-consequent (rule) (cddr rule))


Notice that rule-consequent is my rewrite of conclusion-part, except it always returns a list with a single element (can you see why?). This is useful later when you call append, and it is consistent with rule-antecedent which returns a list.



Actionability of rules



Functions that return either true or false are called predicates and are by convention suffixed with -p in Lisp (and -? in Scheme). You may or may not follow that rule, but please introduce more meaningful variable names. Here is how you could rewrite it:



(defun actionablep (rule facts)

  (dolist (term (rule-antecedent rule) t)

    (unless (member term facts)

      (return nil))))


Since you already know loop, you could also write:



(defun actionablep (rule facts)

  (loop

    :for term :in (rule-antecedent rule)

    :always (member term facts)))


Forward chaining



There are some problems here too:




  • you do not use the return value of REMOVE or APPEND, which are functions that are guaranteed to not mutate their arguments (unlike DELETE and NCONC, and even for those functions only the returned value matters, the ability that is granted to mutate the existing storage is implementation-defined and only there to allow efficient reuse of memory).


  • In some branch you want to return "yes", in another nil; CL might be dynamically typed, but there is no need for a string return value here.


  • A return form only exist the innermost nil block. In your case that means you return from the implicit block established by DOLIST, not the one from the LOOP. You could name your loop but this is in fact not necessary here, you can write the whole thing without return. More generally, you can have a purely functional approach.



Hint



I wrote a forward-chaining function, and traced it; in the REPL:



CL-USER> (trace forward-chaining)


Here is how I tested my implementation:



(forward-chaining '(B C)

                  '((R1 (B D E) F)

                    (R2 (D G) A)

                    (R3 (C F) A)

                    (R4 (C) D)

                    (R5 (D) E)

                    (R6 (A) H)

                    (R7 (B) X)

                    (R8 (X C) A))

                  'H)


I am testing the code with SBCL, the actual output might differ in your Lisp implementation:



  0: (FORWARD-CHAINING (B C) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R4 (C) D) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

    1: (FORWARD-CHAINING (B C D) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R5 (D) E) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

      2: (FORWARD-CHAINING (B C D E) ((R1 (B D E) F) (R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

        3: (FORWARD-CHAINING (B C D E F) ((R2 (D G) A) (R3 (C F) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

          4: (FORWARD-CHAINING (B C D E F A) ((R2 (D G) A) (R6 (A) H) (R7 (B) X) (R8 (X C) A)) H)

            5: (FORWARD-CHAINING (B C D E F A H) ((R2 (D G) A) (R7 (B) X) (R8 (X C) A)) H)

            5: FORWARD-CHAINING returned (H)

          4: FORWARD-CHAINING returned (H)

        3: FORWARD-CHAINING returned (H)

      2: FORWARD-CHAINING returned (H)

    1: FORWARD-CHAINING returned (H)

  0: FORWARD-CHAINING returned (H)


The basic structure of the program is:



(defun forward-chaining (rules facts goal)

  (or ...

      (loop 

        for ... in ...

        thereis (and (actionablep ... ...)

                     (forward-chaining ... ... ...)))))


In other words: either the goal is already a known fact, or there is an actionable rule by which goal is transitively reachable. Note that you might have an infinite recursion if your rules are non-terminating.



The order by which you visit rules determines if your strategy is depth-first (always follow the last tried rule and progress from that one, using the list of rules as a stack), or breadth-first (apply all activable rules for a given fact, using the list of rules as a queue). I don't know where the term "beneath"-first search comes from, I found no serious reference from it (there is one paper that references Leiserson & Schardl 2010 when talking about beneath first search, but the referenced article has no mention of it, only breadth-first, which is well-known).







share|improve this answer














share|improve this answer



share|improve this answer








edited Jan 8 at 14:47

























answered Jan 1 at 22:16









coredumpcoredump

22k43047




22k43047













  • can'u give me a hint how can'i guess the type of the search ( depth first or beneath first search ) and if i happen to formulate the code so it falls in one of these cases how can' i proove that ( is the code you tested depth first or beneath first )?

    – saitama
    Jan 1 at 22:28











  • No that you say it, I think my example is depth-first, I start from one fact and follow rules recursively before trying other rules at the same level of search. For breadth-first search, I guess that means all actionable rules at a given search level should be applied and the resulting facts appended at the end of the current facts, before entering the next fixpoint loop. I'll update the answer.

    – coredump
    Jan 1 at 22:49











  • I think that ,inorder to simulate the breadth-first search u need to go though the collected-factes and for each rule test if the goal exists in the facts base after activation it and empty the queue when you leave each level and so you can call the main function recursively with the updaed facts-base ( = facts + new-facts)

    – saitama
    Jan 2 at 14:19











  • cam anyone ell m what i the difference between depth first or bemath first ?

    – saitama
    Jan 7 at 10:14



















  • can'u give me a hint how can'i guess the type of the search ( depth first or beneath first search ) and if i happen to formulate the code so it falls in one of these cases how can' i proove that ( is the code you tested depth first or beneath first )?

    – saitama
    Jan 1 at 22:28











  • No that you say it, I think my example is depth-first, I start from one fact and follow rules recursively before trying other rules at the same level of search. For breadth-first search, I guess that means all actionable rules at a given search level should be applied and the resulting facts appended at the end of the current facts, before entering the next fixpoint loop. I'll update the answer.

    – coredump
    Jan 1 at 22:49











  • I think that ,inorder to simulate the breadth-first search u need to go though the collected-factes and for each rule test if the goal exists in the facts base after activation it and empty the queue when you leave each level and so you can call the main function recursively with the updaed facts-base ( = facts + new-facts)

    – saitama
    Jan 2 at 14:19











  • cam anyone ell m what i the difference between depth first or bemath first ?

    – saitama
    Jan 7 at 10:14

















can'u give me a hint how can'i guess the type of the search ( depth first or beneath first search ) and if i happen to formulate the code so it falls in one of these cases how can' i proove that ( is the code you tested depth first or beneath first )?

– saitama
Jan 1 at 22:28





can'u give me a hint how can'i guess the type of the search ( depth first or beneath first search ) and if i happen to formulate the code so it falls in one of these cases how can' i proove that ( is the code you tested depth first or beneath first )?

– saitama
Jan 1 at 22:28













No that you say it, I think my example is depth-first, I start from one fact and follow rules recursively before trying other rules at the same level of search. For breadth-first search, I guess that means all actionable rules at a given search level should be applied and the resulting facts appended at the end of the current facts, before entering the next fixpoint loop. I'll update the answer.

– coredump
Jan 1 at 22:49





No that you say it, I think my example is depth-first, I start from one fact and follow rules recursively before trying other rules at the same level of search. For breadth-first search, I guess that means all actionable rules at a given search level should be applied and the resulting facts appended at the end of the current facts, before entering the next fixpoint loop. I'll update the answer.

– coredump
Jan 1 at 22:49













I think that ,inorder to simulate the breadth-first search u need to go though the collected-factes and for each rule test if the goal exists in the facts base after activation it and empty the queue when you leave each level and so you can call the main function recursively with the updaed facts-base ( = facts + new-facts)

– saitama
Jan 2 at 14:19





I think that ,inorder to simulate the breadth-first search u need to go though the collected-factes and for each rule test if the goal exists in the facts base after activation it and empty the queue when you leave each level and so you can call the main function recursively with the updaed facts-base ( = facts + new-facts)

– saitama
Jan 2 at 14:19













cam anyone ell m what i the difference between depth first or bemath first ?

– saitama
Jan 7 at 10:14





cam anyone ell m what i the difference between depth first or bemath first ?

– saitama
Jan 7 at 10:14




















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid …



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53998558%2fforward-chaining-beneath-first-search-in-lisp%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

MongoDB - Not Authorized To Execute Command

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
Read more

How to fix TextFormField cause rebuild widget in Flutter

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I've got the same issue at #9280. I tried all solutions from that topic with/without GlobalKey for Scaffold and Form but the problem wasn't fixed. I tried to build a authentication form with login and signup. But the keyboard doesn't show when I tap the TextFormField at the first time. Then I try to input some letter from physical keyboard, the widget is rebuilt. Like this: login screen Nothing to be log when I run flutter run --verbose, so I logged manually. Every tapping on field, the widget called dispose -> init -> build. [√] Flutter (Channel beta, v1.0.0, on Microsoft Windows [Version 10.0.17763.195], ...
Read more

in spring boot 2.1 many test slices are not allowed anymore due to multiple @BootstrapWith

Image
1 I tried to upgrade a yummy sandwich made of two test slices (@JsonTest and @JdbcTest in my case, crunchy test code in between) adding spring boot 2.1 flavour to it. But it seems it was not much of a success. I cannot annotate my tests with many @...Test since they are now each bringing their own XxxTestContextBootstrapper. It used to work when they all used same SpringBootTestContextBootstrapper. @RunWith(SpringRunner.class) @JdbcTest @JsonTest public class Test { @Test public void test() { System.out.printn("Hello, World !"); } } The error I get from BootstrapUtils is illegalStateException : Configuration error: found multiple declarations of @BootstrapWith for test class I understand I might be doing something wrong here but is there an easy way I could load both Json and Jdbc contex...
Read more