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
Here are some general remarks about some mistakes in your code, followed by hints about how to implement forward chaining.
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))
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.
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)))
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.
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).