Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

common lisp: acons in matching lists? – Artificial Intelligence

I’m working through The Elements of Artificial Intelligence Using Common Lisp by Steven Tanimoto and I can’t figure out his match program. So far the idea is to gradually improve upon a self-rolled list match, starting with not very good

(defun match1 (p s) (equalp p s))

Here’s match3:

 (defun match3 (p s)
      (cond
        ((null p) (null s))            ;null clause
        ((or (atom p) (atom s)) nil)   ;atom clause
        ((equalp (first p) (first s))  ;equal CAR clause
         (match3 (rest p) (rest s)))   
        ((eql (first p) '?)            ; joker clause  
         (match3 (rest p) (rest s)))
        (t nil)))                      ;extremal clause

the so-called joker clause should match, i.e.,

(match3 '(a b ? d) '(a b c d))  ; yields t

but then the next version should “match” this

(match4 '((? x) b c (? y)) '(a b c d))

I quote

This would permit, for example, the (above) form to not only return
true, but also return the association of a with x and the
association of d with y. In that way, if the match is used as a
condition in a production rule, the action part of the rule can
manipulate the values matching the variable elements in the pattern.

…and then it goes on talking about alist things. Then the rewrite of match:

(defun4 match4 (p s)
      (cond
        ((and (null p) (null s))
         '((:yes . :yes)))
        ((or (atom p) (atom s)) nil)
        ((equalp (first p) (first s))
         (match4 (rest p) (rest s)))

        ((and
          (equalp (length (first p)) 2)
          (eql (first (first p)) '?)
          (let ((rest-match
                 (match4 (rest p) (rest s))))
            (if rest-match
                (acons (first (rest (first p)))
                       (first s)
                       rest-match)))))
        (t nil)))

…so if someone could get me started by first telling me why we want to compare (? x) to a in the example above, that would help. Basically, I’m not clear on what the goal is here. If someone could explain the motivation behind this, I think I could pick apart the code. Otherwise, I’m totally lost.

Tags:

2

Answers


  1. 0

    I have tanimoto’s book, but won’t have access to it until tomorrow at the earliest, but the example mentioned in the quote is actually a good one:

    in that way, if the match is used as a condition in a production rule, the action part of the rule can manipulate the values matching the variable elements in the pattern.

    Production rule systems are a good example of where this kind of matching is useful. It lets rule writers focus on domain knowledge, and to keep algorithms for processing rules separate.

    Some approaches to functional programming also make heavy use of pattern matching. Programing language support varies, though. Common Lisp makers it easy to wrote your own though.

    Login or Signup to reply.
  2. 0

    match3 introduces simple pattern matching between two lists, where the symbol ? in the first list can match any single symbol in the second list. For this reason the function returns T or NIL, to denote the success or the failure of the matching process.

    Then a new kind of match is introduced in match4, through the use of what appear to be a match variable. (? x) is simply a way of introducing a match variable, that in other languages could be written as ?x, or something similar. The idea is that this variable “captures” the symbol matched on the second list, so that, for instance, you could later use it in a way similar to this:

    (match '(a (? x) (? y) (? x) b) '(a c d c b)) ; yes, since ‘c’ matches ‘?x’
(match '(a (? x) (? y) (? x) b) '(a c d e b)) ; no, since ‘c’ and ‘e’ are different

    For this to be used effectively, the function match must give, when a match is found, not simply the value T, but the couple (match variable, symbol matched), and build with it an associative list of matches found. So, match4 returns such list through the use of acons, in the last branch of the cond (first it gets rest-match, than “aconses” over it the pair given by the match variable and the symbol found). The special pair (:yes . :yes) is simply a way of terminating this list of matches.

    I suppose that later in the book will be presented another version of the match function in which the matches found will be used in the subsequent part of the process.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search