Debugging Lisp Function. Any Help out There?

[Power User]

--I am trying to debug my pattern matcher match function.
-- Am trying to implement * symbol as a Generic Wildcard, such:
--(match '(likes I computing) '(likes I *))
--Such that anything before and or after is considered.
--The bottom most function is from George F Luger, Antificial Intelligence 4th Ed.
--For the record, I am not a Student.

-- implement the * variable. (..... * .....)
-- (cond (t (+ 1 2)))
-- returns 3


(defun variable-p (x) (equal x '?))

(defun generic-a (x) (equal x '*))

(defun match-atom (pattern1 pattern2)
(or (equal pattern1 pattern2)
(variable-p pattern1)
(variable-p pattern2)
(generic-a pattern1)
(generic-a pattern2)))

--Having trouble with this function. HELP?
(defun match (pattern1 pattern2)
(cond ((or (atom pattern1) (atom pattern2)) (match-atom pattern1 pattern2))
(cond ((generic-a pattern1) (setq pattern1 (car pattern2)(setq pattern2 (cdr pattern2)))
(t (and (match (car pattern1) (car pattern2)) (match (cdr pattern1) (cdr pattern2))))))
(cond ((generic-a pattern2) (setq pattern1 (car pattern1)(setq pattern1 (cdr pattern2)))
(t (and (match (car pattern1) (car pattern2)) (match (cdr pattern1) (cdr pattern2)))))))))



--(defun match (pattern1 pattern2)
--(cond ((or (atom pattern1) (atom pattern1))
--(match-atom pattern1 pattern2))
--(t (and (match (car pattern1) (car pattern2))
--(match (cdr pattern1) (cdr pattern2))))))

[Jasper]

Indenting that MATCH function, it doesn't seem like correct use of the COND and SETQ macro, and the parenthesis don't match.(Please indent your code and use the \[code\] tags)

Code: Select all

(defun match (pattern1 pattern2)
  (cond ((or (atom pattern1) (atom pattern2))
    (match-atom pattern1 pattern2))
   (cond ((generic-a pattern1)
          (setq pattern1 (car pattern2)
           (setq pattern2 (cdr pattern2)))
          (t
      (and (match (car pattern1) (car pattern2))
           (match (cdr pattern1) (cdr pattern2))))))
   (cond ((generic-a pattern2)
          (setq pattern1 (car pattern1)
           (setq pattern1 (cdr pattern2)))
          (t (and (match (car pattern1) (car pattern2))
             (match (cdr pattern1) (cdr pattern2)))))))))

I don't quite know what to turn that into if i were to try fix it.. The MATCH after that does seem to be correct lisp though. For that one ? seems to work, but * doesn't; assuming it is to mean that an arbitrary list is to fit in there.

I wrote an implementation of MATCH, incase you're just exercising, i won't post it here yet. (It does seem like a good exercise) I did it recursively. If one side is '*, then a * or ? on the other side doesn't matter. So then it either matches right now (match (cdr pattern1) pattern2) or later (match pattern1(cdr pattern2)), or you need to check if it is the end of the list.(most tricky bit)

If one side is '? then the other side being '? similarly doesn't matter. (But * does, must be excluded at that point.)

The rest is just checking equality with EQL, it can also easily be extended to lists, just by on checking, if both lists, match them as you match normally. Of course you have to track the end of the list in order not to infinite loop. Both NULL, then true, only one, that depends if you've seen a '*.

[Power User]

What I want is for (..... * ........) to work as the any number of items wildcard,
but performing normally where there is any content before or after the *.

I understand the algorithmic steps for what I am trying to do: I am simply
getting lost in brackets/recursion/associative confusion.

I simply need some debugging aid. I wish to stick to

car & cdr recursion, and not use an iterative approach.

Some help at all, please?

my examples:

(match '(likes fred bread) '(likes ? bread))
T

(match '(likes *) '(likes fred bread))
T

(match '(likes fred bread) '(likes fred pizza))
NIL

[Jasper]

Strictly speaking it isn't debugging. It just doesn't implement what * does. Actually, look at it, ? and * are treated exactly the same. (Assuming the latter MATCH definition in OP.) For it to implement what * you want it to do, it must be able to go forward in the in the list, and it is apparent it cannot, because CDR is always called for both patterns.

Anyway, one thing that helps me in making function likes these is to think what choices to make locally, in this case:(go by the clauses with a COND

• Both null, then T; nil and nil match.
• (eql (car pattern1) '*) then what if (car pattern2) * or ?, ah, that doesn't matter. * means 'any substring between here', but this is equivalent to: either it first here or it fits in one of the next ones:

  Code: Select all

  (or (match (cdr pattern1) pattern2)) ;Forget the *, see if it fits here.
     (match pattern1 (cdr pattern2))) ;If not, it either doesn't fit, or it fits in the next one.

  Technicality here: it silently assumes pattern2 is not null, if it should be checked that (cdr pattern1) matches with nil. Thusly it may only be a list of * or nil. You need to check this if pattern2 is nil before this point.
• (eql (car pattern2) '*) since MATCH is symmetric. Just reverse.
• (and (eql (car pattern1) '?) (eql (car pattern2) '?)) We know we can ignore both '? and the other side. Just go to the next; (match (cdr pattern1) (cdr pattern2))
• Finally: These this arent ? or *, they're just elements. Check their equality with EQL, or MATCH again if both sides are sublists. Then procede with the rest of the list, again; (match (cdr pattern1) (cdr pattern2))

Some help at all, please?

I am trying.. Please respond in kind.. I guess i could just give you the code, but i prefer to see an attempt. What i wrote before is entirely recursive, btw.

One thing not entirely clear about what you want; is end-of-list to be taken as nil? I argue not. The result of (match '(lots a things ?) '(lots a things)) depends on it.

[gugamilare]

Strictly speaking it isn't debugging. It just doesn't implement what * does. Actually, look at it, ? and * are treated exactly the same.

I guess not. It looks like * matches zero or more items (or would it be one or more items?), while ? matches only one item.

So, I think it would be:

• If pattern1 and patern2 are NIL, then return T;
• (eql (car pattern1) '*) or (eql (car pattern2) '*) then T;
• If, at this point, either is NIL, they don't match - NIL;
• if (eql (car pattern1) '?) or (eql (car pattern2) '?) then this element matches, but we need to test if the rest match, so (match (cdr pattern1) (cdr pattern2));
• then you need to test if (car pattern1) and (car pattern2) as lists; if they are, you need to (match (car pattern1) (car pattern2)) before (match (cdr pattern1) (cdr pattern2));
• finally, since (car pattern1) and (car pattern2) are just common elements, so you need to test if they are eql and again (match (cdr pattern1) (cdr pattern2))

One hint, Power User, don't use setq or setf. You don't need those, not for this function, not for most simple functions. Your code will look a lot cleaner. I'm saying this because 99% of newbies' mistakes come from misusing setq or setf.

EDIT: It is a good idea to replace the calls (eql (car pattern1) '?) with (variable-p (car pattern1)) and replace (eql (car pattern1) '*) with (generic-p (car pattern1)). This way you could redefine what symbols are defined as variables or generics more easily.

[Power User]

Code: Select all

(defun variable-p (x) (equal x '?))

(defun generic-a (x) (equal x '*))

(defun match-atom (pattern1 pattern2)
       (or (equal pattern1 pattern2)
       (variable-p pattern1)
       (variable-p pattern2)
       (generic-a pattern1)
       (generic-a pattern2)))

(defun match (pattern1 pattern2)
(cond ((or (atom pattern1) (atom pattern1))
(match-atom pattern1 pattern2))
....
(match (cdr pattern1) (cdr pattern2))))))

I understand the suggested approach, that a match of * means that
the present state of both lists should just be silently advanced by one,
and the search for * or ? continued.
This is a cutdown version of my match function. Are there any syntax suggestions?

[Jasper]

What are you editing with? I suggest something that helps with indentation, it'll kindah show you how it is usually done. (Usually used with Tab) About 'syntax'.(insofar lisp has it) Having the whitespace only Spaces and Newlines is handy too. (In linux, and emacs in .emacs (setq indent-tabs-mode nil) is handy for posting online.) two spaces are usual after a defun.(or more generally when it is a body.) Other wise they are aligned, or if first argument on other line than function name, one space extra indentation.

The MATCH-ATOM function is still wrong in-principle, as it doesn't distinguish between * and ?, it can only handle the latter. The bit you cut out was kindah the bit that isn't working. Could you write a MATCH function with a COND each clause going point by point of this list:(and post it here)

• (possibly two clauses)One side NULL, then other side either also NULL, or other side only contains '*.
• (possibly two clauses)First of one side *, then either match now, or match one later on the other list;

  Code: Select all

  (or (match (cdr pattern1) pattern2) ;Match right now.
      (match pattern1 (cdr pattern2)))) ;Or match later

  Where in that case pattern1 is the one starting with *.
• One of the sides '? then this element doesn't matter.
• Treat elements where none of the above applies. EQL them.

It doesn't necessarily have to work, but it would give me something to help with.

[Power User]

The following code of mine is more along the lines I am trying to go. This simply needs
debugging, I believe. Aid, anyone?

Code: Select all

(defun variable-p (x) (equal x '?))

(defun generic-a (x) (equal x '*))

(defun post-a  (x)   (generic-a (car (cdr x))))

(defun match-atom (pattern1 pattern2)
       (or (equal pattern1 pattern2)
       (variable-p pattern1)
       (variable-p pattern2)))


 (defun match (pattern1 pattern2)
(cond ((or (atom pattern1) (atom pattern1))
(match-atom pattern1 pattern2)))
(cond ((generic-a pattern1)
(t (and (match pattern1 (post-a pattern2))  (match (cdr pattern1) (cdr pattern2))))))
(cond ((generic-a pattern2)
(t (and (match pattern2 (post-a pattern1))  (match (cdr (cdr pattern1)) (cdr (cdr pattern2)))))))
(t (and (match (car pattern1) (car pattern2))(match (cdr pattern1) (cdr pattern2)))))


[Jasper]

You're misunderstanding how a body and cond works. Are you using some book like PCL? Just trying stuff is inefficient, there are texts to explain it to you. Cond goes like (cond (cond ..body..) (cond ...body..) ..etc..) Only the body of the first clause that returns true is actually executed. Each (cond ..body..) is often called a clause.

Bodies generally only return the last element(though that may depend on the macro.) so does the DEFUN body, so (cond ((or (atom pattern1) (atom pattern1)) (match-atom pattern1 pattern2))) won't do anything in this case; the function doesn't change anything, and the returned value is discarded. Your MATCH is equivalent to:

Code: Select all

(defun match (pattern1 pattern2)
  (cond ((generic-a pattern2)
                (t (and (match pattern2 (post-a pattern1))  (match (cdr (cdr pattern1)) (cdr (cdr pattern2))))))) ;the (T ...) here is in a body, not a clause; 'T is not a function' error if here.
              (t (and (match (car pattern1) (car pattern2))(match (cdr pattern1) (cdr pattern2)))))

I am sorry, you've got to read the book. This still doesn't need 'just debugging'. Debugging is when something usually works, but sometimes it doesn't, this doesn't even run. Why did you think you needed an AND there?

Btw i am assuming you are using CL, but afaik no lisp uses COND like that.

Looking at your code:(If the cond was correctly written)

• First clause matched atoms. Problem is '* and '? are also atoms, and if the COND was correct, it would immediately and incorrectly just return the match-atom of that.
• Second clause, condition (generic-a pattern1) but it seems to me that pattern is a list here, and that generic-a is designed for atoms. And then the 'clause' inside the bode with T not a function.
• Third clause, condition T. So the condition is always true, and if the previous conditions are false, this one is the one that will be run.
  I don't get why you're ANDing them together, and why you're reading (car(cdr x)) in POST-A, or why you're trying to match POST-A, which is to return a BOOLEAN, and subsequently matching it..
• Last clause won't ever be executed. Don't get what it is trying to do either

Essentially, i think you've got to read the book and how these things work. Then you can just make small stuff, and see what they actually do.

[Power User]

;; Referenced lisp source code from Luger 2nd Edition, "Artificial Intelligence 4th Edition"
;; lisp pattern matcher code.
;; implement the * wild card. (..... * .....)



(defun variable-q (x) (equal x '?))

(defun variable-a (x) (equal x '*))

(defun match-atom (pattern1 pattern2)
(or (equal pattern1 pattern2)
(variable-q pattern1)
(variable-q pattern2)))

(defun find-post (x y) (cond (((not (eq x (car y)))) find-post(x (cdr y))) (cond ((eq x (car y)) (setvar pattern2 (cdr y))))))


(defun match (pattern1 pattern2)
(cond ((or (atom pattern1) (atom pattern1))
(match-atom pattern1 pattern2))
(cond ((and (listp pattern1) (variable-a (car pattern1))) (and (setvar pattern1 (cdr pattern1)) (find-post pattern1 pattern2))))
(cond ((and (listp pattern2) (variable-a (car pattern2))) (and (setvar pattern2 (cdr pattern2)) (find-post pattern2 pattern1))))
(t (and (match (car pattern1) (car pattern2))(match (cdr pattern1) (cdr pattern2))))))


;This code works on the assumption that setvar is a global variable, with scope outside the function.
; eg.
;(match '(likes bill wine) '(likes bill wine)) T
;(match '(likes bill wine) '(likes bill beer)) nil
;(match '(likes ? wine) '(likes bill wine)) T
;(match '(likes ? wine) '(likes anything)) nil
;(match '(likes *) '(likes bill wine)) T
;(match '(likes *) '(dislikes bill lemon-lime-bitters)) nil