Class AREF-TEMPLATE

CL Unification: Class AREF-TEMPLATE · unified

+  #T(aref (index1 ... indexN) item)
+  
+  #T(aref index item)
+  
+  #T(aref index item) <==> #T(aref (index) item)
+  
+  cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(aref 2 ?x)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(aref 42 ?x)))
+  --> Error: index 42 out of bounds.
+
+
+  cl-prompt> (setq e (unify 42 #T(aref 42 ?x)))
+  --> Error: UNIFICATION-FAILURE
+
+
+  cl-prompt> (setq e (unify "This is a string!" #T(aref 4 ?x)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  #\Space  
+
+
+  cl-prompt> (setq e (unify #2A((1 0) (foo bar)) #T(aref (1 1) ?x)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  BAR
+
+
+  cl-prompt> (setq e (unify #2A((1 0) (foo bar)) #T(aref (1 1) baz)))
+  --> Error: UNIFICATION-FAILURE
+
+
+  cl-prompt> (setq e (unify #2A((1 0) (foo ?x)) #T(aref (1 1) baz)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  BAZ
+  
+  #T(array <shape-template>)
+  
+  #T(<CL array type specifier> <shape-template>)
+  
+  #T(array ([* | <CL type specifier>] [<dimension sped>]) <shape-template>)
+  
+  <shape-template> ::= <sequence-template>
+                   |   <destructuring template lambda list>
+                   |   (<shape-template>)
+  
+  cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(array (0 1 ?x 3 4 5))))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify #(0 1 42 3 4 5)  #T(array (0 1 "FOO" 3 4 5))))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setq e (unify #2A((0 1 42) (3 4 5)) #T(array ((0 1 ?x) (3 4 5)))))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify #2A(("foo" "bar" 42) (3 4 5)) #T(array ((_ _ ?x) (3 4 5)))))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify #2A(("foo" "bar" 42) (3 4 5)) #T(array (#T(vector _ &rest ?x) (3 4 5)))))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  #("bar" 42)
+  
+  (defun factorial (x)
+    (match-case (x)
+      (0 1)
+      (#T(number ?n) (* ?n (factorial (1- ?n))))
+      (otherwise (error "Incorrect match for ~S." x))))
+  
+  (defstruct (tree-node (:conc-name tn-)
+                        (:constructor mk-tn (color left elem right)))
+     color
+     left
+     elem
+     right)
+
+  (defun balance (&rest balancing-arguments)
+    (match-case (balancing-arguments)
+      ((:black #T(tree-node tn-color :red
+                            tn-left #T(tree-node tn-color :red
+                                                 tn-left ?a
+                                                 tn-elem ?x
+                                                 tn-right ?b)
+                            tn-elem ?y
+                            tn-right ?c)
+               ?z
+               ?d)
+        (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
+      ((:black #T(tree-node tn-color :red
+                            tn-left ?a
+                            tn-elem ?x
+                            tn-right #T(tree-node tn-color :red
+                                                  tn-left ?b
+                                                  tn-elem ?y
+                                                  tn-right ?c))
+               ?z
+               ?d)
+        (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
+      ((:black ?a
+               ?x
+               #T(tree-node tn-color :red
+                            tn-left #T(tree-node tn-color :red
+                                                 tn-left ?b
+                                                 tn-elem ?y
+                                                 tn-right ?c)
+                            tn-elem ?z
+                            tn-right ?d))
+        (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
+      ((:black ?a
+               ?x
+               #T(tree-node tn-color :red
+                            tn-left ?b
+                            tn-elem ?y
+                            tn-left #T(tree-node tn-color :red
+                                                 tn-left ?c
+                                                 tn-elem ?z
+                                                 tn-right ?d)))
+        (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
+      ((?color ?left ?elem ?right)
+        (mk-tn ?color ?left ?elem ?right))))
+  
+  U(42, 42) ==> {}
+  
+  U(42, 123) ==> <unification failure>
+  
+  U(42, x) ==> {x -> 42}
+  
+  unify x y &optional substitution
+  
+  ?A ?s ?qwe ?42z ?a-variable-with-a-very-long-name ?_
+  
+  cl-prompt> (unify 42 42)
+  #<EMPTY ENVIRONMENT xxxxxx>
+  
+  cl-prompt> (unify 42 123)
+  ==> error: unification failure
+  
+  cl-prompt> (unify 42 ?x)
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?x *)
+  42
+  
+  cl-prompt> (unify '(foo (bar frobboz) ?baz) '(foo ?gnao 42))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?gnao *)
+  (BAR FROBBOZ)
+
+  cl-prompt> (find-variable-value '?baz **)
+  42
+  
+  cl-prompt> (unify '(foo ?x 42) '(foo 42 ?x))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (unify '(foo ?x 42) '(foo baz ?x))
+  ==> error: unification failure
+  
+  cl-prompt> (unify #(1 2 3) #(1 ?x ?y))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?x *)
+  2
+  
+  cl-prompt> (unify #2A((1 2 3) (a s ?z)) #2A((1 ?x ?y) (a s d)))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?z *)
+  D
+  
+  (defstruct foo a s d)
+  
+  (unify #S(FOO A 42 S NIL D NIL) (make-foo :a 42))
+  
+  (defclass template ()
+     ((spec :accessor template-spec :type (or cons symbol number) ...)))
+  
+  #Tsomething ==> (make-instance 'template :spec something)
+  
+  (unify #(FOO A 42 S NIL D NIL) #T(foo foo-a 42))
+  
+  cl-prompt> (unify #(1 2 3 4 5) #T(vector 1 ?x &rest ?rest)) ; You get the idea...
+  #<ENVIRONMENT xxxxxxx>
+
+  cl-prompt> (find-variable-value '?rest *)
+  #(3 4 5)
+  
+  cl-prompt> (unify '(1 2 3 4 5) #T(list 1 ?x &rest ?rest))
+  #<ENVIRONMENT xxxxxxx>
+
+  cl-prompt> (find-variable-value '?rest *)
+  (3 4 5)
+  
COPYING
+  #T(elt index item)
+  
+  cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(elt 2 ?x)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(elt 42 ?x)))
+  --> Error: index 42 out of bounds.
+
+
+  cl-prompt> (setq e (unify 42 #T(elt 42 ?x)))
+  --> Error: UNIFICATION-FAILURE
+
+
+  cl-prompt> (setq e (unify "This is a string!" #T(elt 4 ?x)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  #\Space  
+  
+  find-variable-value variable-name &optional env errorp
+  => value, found
+  
+  #Tspec
+  -> template
+  
+  #Tfoo ==> #<SYMBOL-TEMPLATE FOO xxxxxx>
+  
+  #T(vector 1 2 &rest ?x) ==> #<VECTOR-TEMPLATE xxxxx>
+  
+  U(42, 42) ==> {}
+  
+  U(42, 123) ==> <unification failure>
+  
+  U(42, x) ==> {x -> 42}
+  
+  unify x y &optional substitution
+  
+  ?A ?s ?qwe ?42z ?a-variable-with-a-very-long-name ?_
+  
+  cl-prompt> (unify 42 42)
+  #<EMPTY ENVIRONMENT xxxxxx>
+  
+  cl-prompt> (unify 42 123)
+  ==> error: unification failure
+  
+  cl-prompt> (unify 42 ?x)
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?x *)
+  42
+  
+  cl-prompt> (unify '(foo (bar frobboz) ?baz) '(foo ?gnao 42))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?gnao *)
+  (BAR FROBBOZ)
+
+  cl-prompt> (find-variable-value '?baz **)
+  42
+  
+  cl-prompt> (unify '(foo ?x 42) '(foo 42 ?x))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (unify '(foo ?x 42) '(foo baz ?x))
+  ==> error: unification failure
+  
+  cl-prompt> (unify #(1 2 3) #(1 ?x ?y))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?x *)
+  2
+  
+  cl-prompt> (unify #2A((1 2 3) (a s ?z)) #2A((1 ?x ?y) (a s d)))
+  #<ENVIRONMENT xxxxxx>
+
+  cl-prompt> (find-variable-value '?z *)
+  D
+  
+  (defstruct foo a s d)
+  
+  (unify #S(FOO A 42 S NIL D NIL) (make-foo :a 42))
+  
+  (defclass template ()
+     ((spec :accessor template-spec :type (or cons symbol number) ...)))
+  
+  #Tsomething ==> (make-instance 'template :spec something)
+  
+  (unify #S(FOO A 42 S NIL D NIL) #T(foo foo-a 42))
+  
+  cl-prompt> (unify #(1 2 3 4 5) #T(vector 1 ?x &rest ?rest)) ; You get the idea...
+  #<ENVIRONMENT xxxxxxx>
+
+  cl-prompt> (find-variable-value '?rest *)
+  #(3 4 5)
+  
+  cl-prompt> (unify '(1 2 3 4 5) #T(list 1 ?x &rest ?rest))
+  #<ENVIRONMENT xxxxxxx>
+
+  cl-prompt> (find-variable-value '?rest *)
+  (3 4 5)
+  
COPYING
+  #T(list . <destructuring template lambda list>)
+  
+  cl-prompt> (setf e (unify '(0 1 42 3 4 5) #T(list 0 1 ?x 3 4 5)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setq e (unify '(0 1 42 3 4 5)  #T(list 0 1 "FOO" 3 4 5)))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setq e (unify '("foo" "bar" 42)) #T(list _ _ ?x))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setq e (unify #(1 2 3) #T(list _ &rest ?x)))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setq e (unify (list "foo" '?foo 42)) #T(list _ 33 ?x))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (find-variable-value '?foo e)
+  33
+  T
+  
+  make-empty-environment
+  => unification-environment
+  
+  make-shared-environment env
+  => unification-environment
+  
+  match-case (object &key errorp) <clause>*
+  => results*
+  
+  <clause>         ::= <regular clause> | <default clause>
+  <regular clause> ::= (template &body forms)
+  <default clause> ::= (t &body forms)
+                   |   (otherwise &body forms)
+  
+  match (template object &key substitution errorp error-value) &body forms
+  => results*
+  
+  matching (&key errorp) <clause>*
+  => results*
+  
+  <clause>         ::= <regular clause> | <default clause>
+  <regular clause> ::= ((template object) &body forms)
+  <default clause> ::= (t &body forms)
+                   |   (otherwise &body forms)
+  
+  #Tnil
+  
+  #T()
+  
+  cl-prompt> (setf e (unify nil #Tnil))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (setq e (unify 42 #T()))
+  --> Error: UNIFICATION-FAILURE
+  
+  #T(nth index item)
+  
+  cl-prompt> (setf e (unify '(0 1 42 3 4 5) #T(nth 2 ?x)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify '(0 1 42 3 4 5) #T(nth 42 ?x)))
+  --> Error: index 42 out of bounds.  FIX THIS
+
+
+  cl-prompt> (setq e (unify #(a s d) #T(nth 1 ?x)))
+  --> Error: UNIFICATION-FAILURE
+  
+  #T(nthcdr index item)
+  
+  cl-prompt> (setf e (unify '(0 1 42 3 4 5) #T(nthcdr 2 ?x)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  (42 3 4 5)
+
+  cl-prompt> (setq e (unify '(0 1 42 3 4 5) #T(nthcdr 42 ?x)))
+  --> Error: index 42 out of bounds.  FIX THIS
+
+
+  cl-prompt> (setq e (unify #(a s d) #T(nthcdr 1 ?x)))
+  --> Error: UNIFICATION-FAILURE
+  
+  #T42
+  
+  #T(number 42)
+  
+  #T(number ?num)
+  
+  #T#C(1.2 3.4)
+  
+  cl-prompt> (setf e (unify 42 #T42))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (setq e (unify 42 #T()))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setf e (unify 42 #T(number ?num)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?num e)
+  42
+  T
+  
+  #T(sequence . <destructuring template lambda list>)
+  
+  cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(sequence 0 1 ?x 3 4 5)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setq e (unify #(0 1 42 3 4 5)  #T(sequence 0 1 "FOO" 3 4 5)))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setq e (unify #("foo" "bar" 42)) #T(sequence _ _ ?x))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setq e (unify (list "foo" "bar" 42) #T(sequence _ &rest ?x)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  ("bar" 42)
+
+  cl-prompt> (setq e (unify "I am a string" #T(sequence ?I _ &rest ?x)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  "am a string"
+  T
+
+  cl-prompt> (find-variable-value '?I e)
+  #\I
+  T
+
+  cl-prompt> (setq e (unify 42 #T(sequence _ &rest ?x)))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setq e (unify #("foo" ?foo 42)) #T(sequence _ 33 ?x))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (find-variable-value '?foo e)
+  33
+  T
+  
+  #T(<CL class designator> <slot spec>*)
+
+  <slot spec> ::= <reader method> <object>
+              |   (slot-value <slot name>) <object>
+  
+  cl-prompt> (defclass foo () ((a :initform 42 :accessor foo-a)))
+  #<STANDARD-CLASS FOO XXXXX>
+
+  cl-prompt> (defclass bar (foo) ())
+  #<STANDARD-CLASS BAR XXXXX>
+
+  cl-prompt> (defclass baz ()
+               ((a :reader the-a-in-a-baz)
+                (b :accessor bazb :initarg :b)))
+  #<STANDARD-CLASS BAZ XXXXX>
+
+  cl-prompt> (setf e (unify (make-instance 'foo) #T(foo foo-a 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (setf e (unify (make-instance 'bar) #T(foo foo-a 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'bar) #T(foo foo-a 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'baz) #T(baz the-a-in-baz 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'baz) #T(baz (slot-value b) 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'baz :b '?e) #T(baz bazb 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'bar) #T(baz foo-a 42)))
+  --> Error: UNIFICATION-FAILURE
+  
+  #T(string . <destructuring template lambda list>)
+  
+  cl-prompt> (setf e (unify "foobar" #T(string "foob" ?x #\r)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  #\a
+
+  cl-prompt> (setq e (unify "foobar"  #T(string "FOO" #\b #\a #\r)))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setq e (unify "foobar") #T(string _ _ ?x _ _ _))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  #\o
+
+  cl-prompt> (setq e (unify "foobar" #T(string _ &rest ?x)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  "oobar"
+  
+  #T(<CL structure class designator> [<reader function> <object>]*)
+  
+  cl-prompt> (defstruct foo () (a 42))
+  FOO
+
+  cl-prompt> (defstruct (baz (:include foo)) (b 33))
+  BAZ
+
+  cl-prompt> (setf e (unify (make-foo) #T(foo foo-a 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (setf e (unify (make-baz) #T(foo foo-a 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'bar) #T(foo foo-a 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'baz) #T(baz the-a-in-baz 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'baz :b '?e) #T(baz bazb 42)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (setf e (unify (make-instance 'bar) #T(baz foo-a 42)))
+  --> Error: UNIFICATION-FAILURE
+  
+  #T(subseq start end . <destructuring template lambda list>)
+  
+  cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(subseq 2 4 ?x ?y)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+  T
+
+  cl-prompt> (find-variable-value '?y e)
+  3
+  T
+
+  cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(subseq 0 4 42 ?x)))
+  --> Error: UNIFICATION-FAILURE
+
+
+  cl-prompt> (setq e (unify "This is a string!" #T(subseq 4 nil &rest ?str)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?str e)
+  " is a string!"
+  
+  #T<symbol>
+  
+  #T(symbol <value>)
+  
+  template-p object
+  => result
+  
+  template-spec template
+  => spec
+  
+  (setf (template-spec template) spec)
+  => spec
+  
+  ?A ?s ?qwe ?42z ?a-variable-with-a-very-long-name ?_
+  
+  template-lambda-list ::= (<reqvars> <optvars> <restvar> <keyvars>)
+                       |   (<reqvars> <optvars> . <template>)
+
+  reqvars ::= <template>*
+
+  optvars ::= [&optional <template>*]
+
+  restvar ::= [&rest <template>]
+
+  keyvars ::= [&key {<template> | ({<template> | (<keyword-name> <template>)})}*
+              [&allow-other-keys]]
+  
+  unify object1 object2 &optional substitution
+  => substitution
+  
+  unify (s1 symbol) (s2 symbol) &optional substitution
+  => substitution
+  
+  unify (v symbol) (object t) &optional substitution
+  => substitution
+  
+  unify (n1 number) (n2 number) &optional substitution
+  => substitution
+  
+  unify (s1 string) (s2 string) &optional substitution
+  => substitution
+  
+  unify (v1 vector) (v2 vector) &optional substitution
+  => substitution
+  
+  unify (l1 list) (l2 list) &optional substitution
+  => substitution
+  
+  unify (s1 sequence) (s2 sequence) &optional substitution
+  => substitution
+  
+  unify (a1 array) (a2 array) &optional substitution
+  => substitution
+  
+  unify (object1 t) (object2 t) &optional substitution
+  => substitution
+  
+  unify (s structure-object) (st structure-object-template) &optional substitution
+  => substitution
+  
+     (<structure-class specifier> [ (<reader> <value>) ]* )
+  
+  unify (s standard-object) (st standard-object-template) &optional substitution
+  => substitution
+  
+     (<standard-class specifier> [ ([slot-value | slot-accessor] <slot-spec> <value>) ]* )
+  
+  {x₁ -> y₁, x₂ -> y₂, ..., x_k -> y_k}
+  
+  binding: variable --> value
+  
+  frame: {binding_i}
+  
+  environment: <frame₀, frame₁, ..., frame_k>
+  
+  #T(vector . <destructuring template lambda list>)
+  
+  #T(<CL vector type specifier> . <destructuring template lambda list>)
+  
+  cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(vector 0 1 ?x 3 4 5)))
+  #<ENVIRONMENT xxx>
+  
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify #(0 1 42 3 4 5)  #T(vector 0 1 "FOO" 3 4 5)))
+  --> Error: UNIFICATION-FAILURE
+
+  cl-prompt> (setq e (unify #("foo" "bar" 42)) #T(vector _ _ ?x))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  42
+
+  cl-prompt> (setq e (unify #("foo" "bar" 42) #T(vector _ &rest ?x)))
+  #<ENVIRONMENT xxx>
+
+  cl-prompt> (find-variable-value '?x e)
+  #("bar" 42)
+
+  cl-prompt> (setq e (unify #("foo" "bar" 42) #T((vector fixnum) _ &rest ?x)))
+  --> Error: UNIFICATION-FAILURE
+

+ + *CL Unification: Class AREF-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class AREF-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + AREF-TEMPLATE, ELEMENT-TEMPLATE, EXPRESSION-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The AREF-TEMPLATE class denotes those object that are used + to unify against a particular element of an ARRAY. + + Template Syntax: + + + + #T(aref (index1 ... indexN) item) + + + + + + #T(aref index item) + + + + The AREF-TEMPLATE syntax denotes the item at + index1 ... indexN of an ARRAY. An AREF-TEMPLATE must + be unified against a ARRAY object. item is unified + against the element extracted from the sequence object at + index1 ... indexN by the standard function AREF. + + The second form is a shorthand. + + + #T(aref index item) <==> #T(aref (index) item) + + + + + + Examples: + + + + cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(aref 2 ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + + cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(aref 42 ?x))) + --> Error: index 42 out of bounds. + + + cl-prompt> (setq e (unify 42 #T(aref 42 ?x))) + --> Error: UNIFICATION-FAILURE + + + cl-prompt> (setq e (unify "This is a string!" #T(aref 4 ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + #\Space + + + cl-prompt> (setq e (unify #2A((1 0) (foo bar)) #T(aref (1 1) ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + BAR + + + cl-prompt> (setq e (unify #2A((1 0) (foo bar)) #T(aref (1 1) baz))) + --> Error: UNIFICATION-FAILURE + + + cl-prompt> (setq e (unify #2A((1 0) (foo ?x)) #T(aref (1 1) baz))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + BAZ + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an AREF-TEMPLATE against a non-ARRAY object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class ARRAY-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class ARRAY-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + ARRAY-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + VECTOR-TEMPLATE. + + + + Slots: + + None. + + + Description: + + The ARRAY-TEMPLATE class denotes those object that are used + to unify against an ARRAY. + + Template Syntax: + + + + #T(array <shape-template>) + + + + + + #T(<CL array type specifier> <shape-template>) + + + + + + #T(array ([* \| <CL type specifier>] [<dimension sped>]) <shape-template>) + + + + Where <shape-template> can be: + + + + <shape-template> ::= <sequence-template> + \| <destructuring template lambda list> + \| (<shape-template>) + + + + + The ARRAY-TEMPLATE syntax denotes an ARRAY object. An + ARRAY-TEMPLATE must be unified against an ARRAY object. The elements + of the array must be unified against the + <shape-template>. Each row of the array is unified + recursively against each element of the <shape-template>. + + + + Examples: + + + + cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(array (0 1 ?x 3 4 5)))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + + cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(array (0 1 "FOO" 3 4 5)))) + --> Error: UNIFICATION-FAILURE + + cl-prompt> (setq e (unify #2A((0 1 42) (3 4 5)) #T(array ((0 1 ?x) (3 4 5))))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + + cl-prompt> (setq e (unify #2A(("foo" "bar" 42) (3 4 5)) #T(array ((_ _ ?x) (3 4 5))))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + + cl-prompt> (setq e (unify #2A(("foo" "bar" 42) (3 4 5)) #T(array (#T(vector _ &rest ?x) (3 4 5))))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + #("bar" 42) + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an ARRAY-TEMPLATE against a non-ARRAY object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + Notes: + + Syntax Note + + The ARRAY-TEMPLATE syntax tries to be easy to use, at the cost of + being overloaded. There is no actual need to have the separate + forms `(array (fixnum) ...)` and + `((array fixnum) ...)`. + + In a future release they may be conflated. For the time being + they are kept separate as it is unclear which would be better to + provide. + + Elements Unification + + It would be nice to have the possibility to unify against + slices of the array. Alas, this seems non trivial to get + right, and it is left as a future extension of the semantics of + <shape-template>. + + ARRAY Structural Properties + + There is no way to "unify" against structural properties of + vectors like fill pointers and displacements. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + CL Extensions: CONTROL FLOW + + Home + \| Downloads + \| Links + + + + + +
	+ + + + + Control Flow + + In order to make the use of the UNIFICATION library easier, a few + utility macros are provided. The macros MATCH, MATCHING, and + MATCH-CASE can be used to unify two (or more) objects and then to + build a lexical environment where the variables present in the to + objects (or templates) are bound to the values resulting from the + application of UNIFY. + + + + MATCH is a "single shot" macro. It does one unification and + executes forms in an appropriate lexical environment. + + MATCH-CASE is equivalent to CASE. It tries to match a single + object (or template) against a set of clauses. The forms associated + to the first clause for which there is a successful unification, are + then executed within an appropriate lexical environment. + + MATCHING is equivalent to COND. Each clause contains a + head + + + + Examples + + These macros allow the construction of interesting pattern + matching like code. + + + + (defun factorial (x) + (match-case (x) + (0 1) + (#T(number ?n) (* ?n (factorial (1- ?n)))) + (otherwise (error "Incorrect match for ~S." x)))) + + + + Or consider the more interesting piece of code from a not-so + hypothetical Red-Black tree implementation (cfr. [O98].) The function BALANCE is the key part of the + rebalancing act played by Red-Black trees. + + + + (defstruct (tree-node (:conc-name tn-) + (:constructor mk-tn (color left elem right))) + color + left + elem + right) + + (defun balance (&rest balancing-arguments) + (match-case (balancing-arguments) + ((:black #T(tree-node tn-color :red + tn-left #T(tree-node tn-color :red + tn-left ?a + tn-elem ?x + tn-right ?b) + tn-elem ?y + tn-right ?c) + ?z + ?d) + (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d))) + ((:black #T(tree-node tn-color :red + tn-left ?a + tn-elem ?x + tn-right #T(tree-node tn-color :red + tn-left ?b + tn-elem ?y + tn-right ?c)) + ?z + ?d) + (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d))) + ((:black ?a + ?x + #T(tree-node tn-color :red + tn-left #T(tree-node tn-color :red + tn-left ?b + tn-elem ?y + tn-right ?c) + tn-elem ?z + tn-right ?d)) + (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d))) + ((:black ?a + ?x + #T(tree-node tn-color :red + tn-left ?b + tn-elem ?y + tn-left #T(tree-node tn-color :red + tn-left ?c + tn-elem ?z + tn-right ?d))) + (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d))) + ((?color ?left ?elem ?right) + (mk-tn ?color ?left ?elem ?right)))) + + + + This version of BALANCE is more verbose than the one given in [O98], but it preserves the general elegance of the + ML implementation. + + + + Control Flow Dictionary + + + Macro MATCH + Macro MATCHING + Macro MATCH-CASE + + + + + Notes + + Other Forms + + It would be obvious to add the macros EMATCH-CASE and + CMATCH-CASE, for symmetry with ECASE and CCASE. Also, MATCHING + could be renamed to MATCH-COND. + + + Current Implementation Details + + The current implementations of MATCHING and MATCH-CASE do not + handle user supplied environments yet. + + + References + + + [O98] C. Okasaki, Purely Functional Data + Structures, Cambridge University Press, 1998. + + + + + Site Map + + + Enjoy! + + + + + Questions? Queries? Suggestions? Comments? Please direct them + at me. + + + + + +
	+ + + + + + + + + +
+ + © 2003-2011, Marco Antoniotti, all rights reserved. + +

+ + CL Extensions: UNIFICATION Dictionary + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Common Lisp Extensions: UNIFICATION Dictionary + + The notion of unification originated in the field of + formal logic (e.g. Robinson, 1956) and has been used extensively in + Computer Science and Programming Languages. Prolog + obviously uses the full power of unification, however, unification + is also at the core of type checking algorithms in the + tradition of Milner's, and a limited form - pattern + matching - is available to the user in languages of the ML and + Haskell family. + + The library presented in these pages provides a full blown + unification framework for Common Lisp. + + Writing a pattern matcher or a an unifier in Common + Lisp is easy, as long as we limit ourselves to manipulate + only ATOMs and CONSes. + + Alas, it would be much nicer if we could manipulated arbitrary + Common Lisp objects as the ML programmer can with + arbitrary ML objects. + + The library presented here is the first one (to the best of the + author's knowledge) that is capable of manipulating arbitrary + Common Lisp objects. + + The hope is that this library could be incorporated directly in + an implementation in order to provide better type checking. + + This should not come as a surprise, as a compiler like CMUCL does + include a type inference engine, which does very similar things. + + Unification Basics + + The unification process makes sure that two object + descriptions containing some holes + - i.e. variables - can be made equal (almost in the EQUALP + sense) by assigning consistent values to the variables + involved. + + Suppose we had a function U performing unification and returning + a set of variable assignments, often called a + substitution. A very simple + example involving the unification of two numbers could be + + U(42, 42) ==> {} + + The two numbers are EQL, so no variable is involved and the empty + substitution is returned. + + U(42, 123) ==> <unification failure> + + The two numbers are not EQL, so the unification fails. + + U(42, x) ==> {x -> 42} + + The only way to make the unification process to succeed is to bind + the value 42 to the variable `x`. + + The UNIFICATION library defines all the necessary functions and a + unification sub-language to handle most of Common + Lisp. + + UNIFICATION Library + + The UNIFICATION library has one main entry point, the generic function + UNIFY, and a sub-language definition that allows us to talk about + Common Lisp objects. + + The UNIFY generic function has the following signature: + + unify x y &optional substitution + + Where `x` and `y` are either + arbitrary Common Lisp objects, variables, + or object templates. These items constitute the so-called + extended terms manipulated by the unification + machinery. + + Variables are symbols with a `#\?` as the + first character of the name. This is a rather traditional choice, + although a different one based on quoted symbols is possible. + Therefore, the following are examples of variables. + + ?A ?s ?qwe ?42z ?a-variable-with-a-very-long-name ?_ + + There are two special variables, `?_` and `_`, + which are used as anonymous place holders, they match anything, but + never appear in a substitution. + + Hence, the above examples result in the following + + cl-prompt> (unify 42 42) + #<EMPTY ENVIRONMENT xxxxxx> + + + + cl-prompt> (unify 42 123) + ==> error: unification failure + + + + cl-prompt> (unify 42 ?x) + #<ENVIRONMENT xxxxxx> + + cl-prompt> (find-variable-value '?x ) + 42 + + + Where FIND-VARIABLE-VALUE is the accessor used to find the value of + a variable in a substitution. + + As a more complicated example, consider the usual CONS based + unification + + cl-prompt> (unify* '(foo (bar frobboz) ?baz) '(foo ?gnao 42)) + #<ENVIRONMENT xxxxxx> + + cl-prompt> (find-variable-value '?gnao ) + (BAR FROBBOZ)* + + cl-prompt> (find-variable-value '?baz ) + 42 + + + Of course note the following behavior + + cl-prompt> (unify** '(foo ?x 42) '(foo 42 ?x)) + #<ENVIRONMENT xxxxxx> + + cl-prompt> (unify '(foo ?x 42) '(foo baz ?x)) + ==> error: unification failure + + + + + UNIFY works also on arrays and vectors. Strings are treated as + atomic objects + + cl-prompt> (unify #(1 2 3) #(1 ?x ?y)) + #<ENVIRONMENT xxxxxx> + + cl-prompt> (find-variable-value '?x ) + 2 + + + + cl-prompt> (unify* #2A((1 2 3) (a s ?z)) #2A((1 ?x ?y) (a s d))) + #<ENVIRONMENT xxxxxx> + + cl-prompt> (find-variable-value '?z ) + D + + + + So far so good, but how can you unify two structures? First of + all there is no portable way (yet) to list all the slots of a given + structure. Secondly, by allowing the unification of arbitrary + CONSes, we have created a short-circuit in the unification + machinery. + + Dealing with object instances raises similar problems. + + Suppose we have the following definition + + (defstruct foo a s d) + + The straighforward + + (unify* #S(FOO A 42 S NIL D NIL) (make-foo :a 42)) + + cannot be built portably, besides, we do not even have the equivalent of the + `#S(...)` notation for regular CLOS objects. Moreover we want + to do other things with other data types. + + A simple solution is to define a template sub-language + to express unifications between structure objects or standard + objects (and other data types as well.) Nevertheless, the + definition of such sub-language cannot be CONS based, because in + such case, we would conflate arbitrary CONSes and the expressions of + the sub-language. + + To circumvent this problem we resort to the usual trick a ML + programmer uses to placate the type-checker: we introduce an + "intermediate" data type. Essentially the following + + (defclass template () + ((spec :accessor template-spec :type (or cons symbol number) ...))) + + + + The TEMPLATE class is accompanied by a reader macro + (`#T` for template, or type, with an + abuse of language) and an + appropriate PRINT-OBJECT method. The `#T` reader macro + expands as + + #Tsomething ==> (make-instance 'template :spec something) + + With this infrastructure we can + express the unification of the FOO instance as + + (unify #(FOO A 42 S NIL D NIL) #T(foo foo-a 42)) + + I.e. we use the actual structure accessor FOO-A to get to the the + value of the slot A in a FOO. This is an example of the template + language. + + A more interesting example, which involves vectors is the + following + + cl-prompt> (unify #(1 2 3 4 5) #T(vector 1 ?x &rest ?rest)) ; You get the idea... + #<ENVIRONMENT xxxxxxx> + + cl-prompt> (find-variable-value '?rest ) + #(3 4 5)* + + I.e. we have a DESTRUCTURING-BIND on steroids. + + Note that separataing the templates is necessary if we want to do + something like + + cl-prompt> (unify '(1 2 3 4 5) #T(list 1 ?x &rest ?rest)) + #<ENVIRONMENT xxxxxxx> + + cl-prompt> (find-variable-value '?rest ) + (3 4 5)* + + Without the template denoted by `#T(list ...)` the + unifier would have been utterly confused. + + In the following the full extent of the UNIFICATION facility is + described in its main components. + + + + Unifying Substitutions + + The Template Sub-language + + Control Flow + + The UNIFICATION Dictionary + + + + + Site Map + + + Enjoy! + + + + + Questions? Queries? Suggestions? Comments? Please direct them + at me. + + + + + +
	+ + + + + + + + +
+ + © 2003-2011, Marco Antoniotti, all rights reserved. + +

+ + CL Extensions: UNIFICATION + + Home + \| Downloads + \| Links + + + + + +
	+ + + + + CL-UNIFICATION Download Page + + + + + + DISCLAIMER: The code associated to these documents is not + completely tested and it is bound to contain errors and omissions. + This documentation may contain errors and omissions as well. + + The file `COPYING` contains a Berkeley-style license. You + are advised to use the code at your own risk. No warranty + whatsoever is provided, the author will not be held responsible for + any effect generated by your use of the library, and you can put + here the scarier extra disclaimer you can think of. + + + + + + Download and CVS Repository + + The CVS repository is here. You can download a tarball directly from there. + + + + + + + + + + Site Map + + + Enjoy! + + + + + Questions? Queries? Suggestions? Comments? Please direct them + at me. + + + + + +
	+ + + + + + + + +
+ + © 2003-2011, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class ELEMENT-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class ELEMENT-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + ELEMENT-TEMPLATE, EXPRESSION-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + AREF-TEMPLATE, ELT-TEMPLATE, NTH-TEMPLATE, NTHCDR-TEMPLATE + + + + Slots: + + None. + + + Description: + + The ELEMENT-TEMPLATE class denotes those object that are used + to unify against a particular element of an ARRAY or a SEQUENCE. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class ELT-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class ELT-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + ELT-TEMPLATE, ELEMENT-TEMPLATE, EXPRESSION-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The ELT-TEMPLATE class denotes those object that are used + to unify against a particular element of a SEQUENCE. + + Template Syntax: + + + + #T(elt index item) + + + + The ELT-TEMPLATE syntax denotes the element of item at + index. An ELT-TEMPLATE must be unified against a SEQUENCE + object. item is unified against the element + extracted from the sequence object at index by the standard + function ELT. + + + Examples: + + + + cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(elt 2 ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + + cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(elt 42 ?x))) + --> Error: index 42 out of bounds. + + + cl-prompt> (setq e (unify 42 #T(elt 42 ?x))) + --> Error: UNIFICATION-FAILURE + + + cl-prompt> (setq e (unify "This is a string!" #T(elt 4 ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + #\Space + + + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an ELT-TEMPLATE against a non-SEQUENCE object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class EXPRESSION-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class EXPRESSION-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + EXPRESSION-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + ELT-TEMPLATE, SUBSEQ-TEMPLATE. + + + + Slots: + + None. + + + Description: + + The EXPRESSION-TEMPLATE class is the root of the expression template sub-hierarchy. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Function FIND-VARIABLE-VALUE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Function FIND-VARIABLE-VALUE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + find-variable-value variable-name &optional env errorp + => value, found + + + + Arguments and Values: + + `variable-name`---a symbol denoting a unification variable + `env`---an unification-environment + `value`---an object + `found`---a boolean + + + + Description: + + The function FIND-VARIABLE-VALUE searches the environment + env for the value associated to the unification variable + variable-name. + + If there is a value associated to variable-name in + env, then it is returned; found, the second return + value, is T. + + If no value is associated to variable-name then + FIND-VARIABLE-NAME signals an error of type + UNIFICATION-VARIABLE-UNBOUND if errorp is non-NIL (the + default.) If errorp is NIL then FIND-VARIABLE-NAME returns + the values NIL and NIL. + + env defaults to NULL-ENVIRONMENT. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + UNIFY:ENVIRONMENT, BINDING, UNIFICATION-VARIABLE-UNBOUND, NULL-ENVIRONMENT + + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-09 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Standard Generic Function TEMPLATE-SPEC* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Reader Macro #T + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + #Tspec + -> template + + + + + Description: + + #Tspec expands to `(make-template + template-kind spec)`. + + + Examples: + + + + #Tfoo ==> #<SYMBOL-TEMPLATE FOO xxxxxx> + + + + + + + #T(vector 1 2 &rest ?x) ==> #<VECTOR-TEMPLATE xxxxx> + + + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + TEMPLATE, the "Template Sub-language" section. + + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-09 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + CL Unification Links + + Home + \| Downloads + \| Links + + + + + +
	+ + + + + Links + + Here are some links which are pertinent to the + CL-UNIFICATION project. + + + + common-lisp.net: the host site. + CLOCC: the site hosting MK:DEFSYSTEM. + Structure and Interpretation of Computer Programs: the SICP site, where inspiration for the unifier can be found. + Paradigms of Artificial Intelligence Programming: the PAIP site, where more inspiration for the unifier can be found. + + + + + + + + + Questions? Queries? Suggestions? Comments? Please direct them + at me. + + + + + +
	+ + + + + + + + + +
+ + © 2003-2011, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class LIST-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class LIST-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + LIST-TEMPLATE, SEQUENCE-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The LIST-TEMPLATE class denotes those object that are used + to unify against a LIST. + + + Template Syntax: + + + + #T(list . <destructuring template lambda list>) + + + + The LIST-TEMPLATE syntax denotes a LIST object. A + LIST-TEMPLATE must be unified against a LIST object. The elements + of the list must be unified against the + <destructuring template lambda list> + + + Examples: + + + + cl-prompt> (setf e (unify '(0 1 42 3 4 5) #T(list 0 1 ?x 3 4 5))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setq e (unify '(0 1 42 3 4 5) #T(list 0 1 "FOO" 3 4 5))) + --> Error: UNIFICATION-FAILURE + + cl-prompt> (setq e (unify '("foo" "bar" 42)) #T(list _ _ ?x)) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setq e (unify #(1 2 3) #T(list _ &rest ?x))) + --> Error: UNIFICATION-FAILURE + + cl-prompt> (setq e (unify (list "foo" '?foo 42)) #T(list _ 33 ?x)) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (find-variable-value '?foo e) + 33 + T + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying a LIST-TEMPLATE against a non-LIST object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + + Notes: + + Unifying a LIST-TEMPLATE against a non-proper or circular list has undefined behavior. + + The LIST-TEMPLATE class is the only one that is really needed in + order not to implode the overall unification machinery. But, since + it is needed, then it is worthwhile to build the whole template + hierarchy. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + CL Extensions: UNIFICATION + + Home + \| Downloads + \| Links + + + + + +
	+ + + + + CL-UNIFICATION Mailing Lists + + + There are three mailing lists set up at + common-lisp.net. + + cl-unification-announce: + low traffic mailing list for announcements about the library. + cl-unification-devel: + mailing list to discuss the development of the library. + cl-unification-cvs: + CVS notifications. + + + + + + + + + + + + + + Enjoy! + + + + + Questions? Queries? Suggestions? Comments? Please direct them + at me. + + + + + +
	+ + + + + + + + +
+ + © 2003-2011, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Function MAKE-EMPTY-ENVIRONMENT* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Function MAKE-EMPTY-ENVIRONMENT + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + make-empty-environment + => unification-environment + + + + Arguments and Values: + + `unification-environment`---a fresh unification-environment + + + + Description: + + The function MAKE-EMPTY-ENVIRONMENT constructs a new + object of type UNIFY:ENVIRONMENT. The new + unification-environment is empty, i.e. it does not contain + any binding. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + UNIFY:ENVIRONMENT, BINDING, FIND-VARIABLE-VALUE + + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-04-12 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Function MAKE-SHARED-ENVIRONMENT* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Function MAKE-SHARED-ENVIRONMENT + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + make-shared-environment env + => unification-environment + + + + Arguments and Values: + + `env`---an unification-environment. + `unification-environment`---a new unification-environment. + + + + Description: + + The function MAKE-SHARED-ENVIRONMENT constructs a new + object of type UNIFY:ENVIRONMENT. The new + unification-environment shares the frames already present in env. + + It is guaranteed that extending unification-environment + will not change env. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + UNIFY:ENVIRONMENT, BINDING, FIND-VARIABLE-VALUE + + + Notes: + + This function is provided to allow for the construction of + "trees" of frames for interpreter-like environments. The macros + MATCH, MATCHING, and MATCH-CASE rely on this function, as they + immediately construct a "shared" environment. + + Current Implementation Note + + MAKE-SHARED-ENVIRONMENT relies on the LIST implementation of + environments. + + The use of MAKE-SHARED-ENVIRONMENT in MATCHING and MATDCH-CASE is + still incomplete. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-11-04 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Macro MATCH-CASE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Macro MATCH-CASE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + + match-case (object &key errorp) <clause>* + => results* + + + + + + <clause> ::= <regular clause> \| <default clause> + <regular clause> ::= (template &body forms) + <default clause> ::= (t &body forms) + \| (otherwise &body forms) + + + + Arguments and Values: + + `template`---a unification template + `object`---an object + `substitution`---a substitution + `errorp`---a generalized boolean + `error-value`---an object + `forms`---an implicit progn + `results`---the values returned by forms + + + + + Description: + + MATCH-CASE sets up a CASE-like environment for multiple template matching clauses. + Each clause evaluates its forms in an environment where the variables + present in the template are bound lexically. Note that both variable + names '?FOO' and 'FOO' are bound for convenience. + + The values returned by the MATCH-CASE form are those of the last form in + the first clause that satisfies the match test. I.e. the first + clause for which the template UNIFYes against object. + + If errorp is non-NIL then if none of the regular clauses matches, then + an error of type UNIFICATION-NON-EXHAUSTIVE is signalled, regardless of + any default clause. Otherwise, the default clause behaves as a + standard COND default clause. The default value of errorp is NIL. + + Affected By: + + None. + + + Exceptional Situations: + + See above. + + + See Also: + + UNIFY, UNIFICATION-FAILURE, UNIFICATION-NON-EXHAUSTIVE + + Notes: + + Note that UNIFICATION-FAILUREs + raising from the evaluation of forms in each clause will + not be caught and handled by the enclosing MATCH-CASE block. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Macro MATCH* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Macro MATCH + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + + match (template object &key substitution errorp error-value) &body forms + => results* + + + + Arguments and Values: + + `template`---a unification template + `object`---an object + `substitution`---a substitution + `errorp`---a generalized boolean + `error-value`---an object + `forms`---an implicit progn + `results`---the values returned by forms + + + + + Description: + + + MATCH sets up a lexical environment to evaluate forms after a unification operation. + MATCH unifies a template and an object and then sets up a lexical + environment where the variables present in the template are bound + lexically. Note that both variable names '?FOO' and 'FOO' are bound + for convenience. + + The MATCH form returns the values returned by the evaluation of the + last of the forms. + + If errorp is non-NIL (the default) then the form raises a + UNIFICATION-FAILURE, otherwise the result of evaluating error-value, + whose default is NIL is returned. + + + Affected By: + + None. + + + Exceptional Situations: + + See above. + + + See Also: + + UNIFY, UNIFICATION-FAILURE + + Notes: + + Note that UNIFICATION-FAILUREs + raising from the evaluation of forms will also be caught and handled by the enclosing MATCH + according to errorp settings. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Macro MATCHING* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Macro MATCHING + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + + matching (&key errorp) <clause>* + => results* + + + + + + <clause> ::= <regular clause> \| <default clause> + <regular clause> ::= ((template object) &body forms) + <default clause> ::= (t &body forms) + \| (otherwise &body forms) + + + + Arguments and Values: + + `template`---a unification template + `object`---an object + `substitution`---a substitution + `errorp`---a generalized boolean + `error-value`---an object + `forms`---an implicit progn + `results`---the values returned by forms + + + + + Description: + + MATCHING sets up a COND-like environment for multiple template matching clauses. + Each clause evaluates its forms in an environment where the variables + present in the template are bound lexically. Note that both variable + names '?FOO' and 'FOO' are bound for convenience. + + The values returned by the MATCHING form are those of the last form in + the first clause that satisfies the match test. + + If errorp is non-NIL then if none of the regular clauses matches, then + an error of type UNIFICATION-NON-EXHAUSTIVE is signalled, regardless of + any default clause. Otherwise, the default clause behaves as a + standard COND default clause. The default value of errorp is NIL. + + Affected By: + + None. + + + Exceptional Situations: + + See above. + + + See Also: + + UNIFY, UNIFICATION-FAILURE, UNIFICATION-NON-EXHAUSTIVE + + Notes: + + Note that UNIFICATION-FAILUREs + raising from the evaluation of forms in each clause will + not be caught and handled by the enclosing MATCHING block.. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class NIL-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class NIL-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + NIL-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The NIL-TEMPLATE class denotes those object that are used + to unify against NIL. + + Template Syntax: + + + + #Tnil + + + + + + #T() + + + + + The NIL-TEMPLATE syntax denotes NIL. + NIL-TEMPLATE can only unified against NIL. + + The NIL-TEMPLATE is used for symmetry reasons, given that the + template hierarchy (almost) mirrors the regular CL + type hierarchy. + + + Examples: + + + + cl-prompt> (setf e (unify nil #Tnil)) + #<ENVIRONMENT xxx> + + cl-prompt> (setq e (unify 42 #T())) + --> Error: UNIFICATION-FAILURE + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an NIL-TEMPLATE against a non-NIL object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class NTH-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class NTH-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + NTH-TEMPLATE, ELEMENT-TEMPLATE, EXPRESSION-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The NTH-TEMPLATE class denotes those object that are used + to unify against a particular element of a LIST. + + Template Syntax: + + + + #T(nth index item) + + + + The NTH-TEMPLATE syntax denotes the item at index + a LIST. A NTH-TEMPLATE must + be unified against a LIST object. item is unified + against the element extracted from the sequence object at + index by the standard function NTH. + + + Examples: + + + + cl-prompt> (setf e (unify '(0 1 42 3 4 5) #T(nth 2 ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + + cl-prompt> (setq e (unify '(0 1 42 3 4 5) #T(nth 42 ?x))) + --> Error: index 42 out of bounds. FIX THIS + + + cl-prompt> (setq e (unify #(a s d) #T(nth 1 ?x))) + --> Error: UNIFICATION-FAILURE + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an NTH-TEMPLATE against a non-LIST object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class NTHCDR-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class NTHCDR-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + NTHCDR-TEMPLATE, ELEMENT-TEMPLATE, EXPRESSION-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The NTHCDR-TEMPLATE class denotes those object that are used + to unify against a particular CONS of a LIST. + + Template Syntax: + + + + #T(nthcdr index item) + + + + The NTHCDR-TEMPLATE syntax denotes the CONS item at index + a LIST. A NTHCDR-TEMPLATE must + be unified against a LIST object. item is unified + against the element extracted from the LIST object at + index by the standard function NTHCDR. + + + Examples: + + + + cl-prompt> (setf e (unify '(0 1 42 3 4 5) #T(nthcdr 2 ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + (42 3 4 5) + + cl-prompt> (setq e (unify '(0 1 42 3 4 5) #T(nthcdr 42 ?x))) + --> Error: index 42 out of bounds. FIX THIS + + + cl-prompt> (setq e (unify #(a s d) #T(nthcdr 1 ?x))) + --> Error: UNIFICATION-FAILURE + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an NTHCDR-TEMPLATE against a non-LIST object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class NUMBER-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class NUMBER-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + NUMBER-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The NUMBER-TEMPLATE class denotes those object that are used + to unify against a NUMBER. + + Template Syntax: + + + + #T42 + + + + + + #T(number 42) + + + + + + #T(number ?num) + + + + + + #T#C(1.2 3.4) + + + + + The NUMBER-TEMPLATE syntax denotes a NUMBER. + NUMBER-TEMPLATEs can only unified against a NUMBER. + + + Examples: + + + + cl-prompt> (setf e (unify 42 #T42)) + #<ENVIRONMENT xxx> + + cl-prompt> (setq e (unify 42 #T())) + --> Error: UNIFICATION-FAILURE + + cl-prompt> (setf e (unify 42 #T(number ?num))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?num e) + 42 + T + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an NUMBER-TEMPLATE against a non-NUMBER object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + + Notes: + + There is no COMPLEX-NUMBER-TEMPLATE class, although a case for it can be easily made. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class SEQUENCE-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class SEQUENCE-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + SEQUENCE-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + VECTOR-TEMPLATE, LIST-TEMPLATE. + + + + Slots: + + None. + + + Description: + + The SEQUENCE-TEMPLATE class denotes those object that are used + to unify against a SEQUENCE. + + Template Syntax: + + + + #T(sequence . <destructuring template lambda list>) + + + + The SEQUENCE-TEMPLATE syntax denotes a SEQUENCE object. A + SEQUENCE-TEMPLATE must be unified against a SEQUENCE object. The elements + of the sequence must be unified against the + <destructuring template lambda list> + + + Examples: + + + + cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(sequence 0 1 ?x 3 4 5))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(sequence 0 1 "FOO" 3 4 5))) + --> Error: UNIFICATION-FAILURE + + cl-prompt> (setq e (unify #("foo" "bar" 42)) #T(sequence _ _ ?x)) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setq e (unify (list "foo" "bar" 42) #T(sequence _ &rest ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + ("bar" 42) + + cl-prompt> (setq e (unify "I am a string" #T(sequence ?I _ &rest ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + "am a string" + T + + cl-prompt> (find-variable-value '?I e) + #\I + T + + cl-prompt> (setq e (unify 42 #T(sequence _ &rest ?x))) + --> Error: UNIFICATION-FAILURE + + cl-prompt> (setq e (unify #("foo" ?foo 42)) #T(sequence _ 33 ?x)) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (find-variable-value '?foo e) + 33 + T + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an SEQUENCE-TEMPLATE against a non-SEQUENCE object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class STANDARD-OBJECT-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class STANDARD-OBJECT-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + STANDARD-OBJECT-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The STANDARD-OBJECT-TEMPLATE class denotes those object that are used + to unify against any STANDARD-OBJECT. + + + Template Syntax: + + + + #T(<CL class designator> <slot spec>) + + <slot spec>* ::= <reader method> <object> + \| (slot-value <slot name>) <object> + + + + The STANDARD-OBJECT-TEMPLATE syntax denotes any + CL object that is an instance of a + STANDARD-OBJECT. The semantic of the template in a unification depends on which + <slot spec>'s appear. In the first case the meaning of + <slot spec> is such that the + <reader method> gets called against the instance + against which the STANDARD-OBJECT-TEMPLATE is being UNIFYed. In the + second case, SLOT-VALUE is called with the instance being UNIFYed + and <slot name>. The result value of the call to either + <reader method>, or SLOT-VALUE is UNIFYed against + <object>. + + <object> can be any CL object, + including a TEMPLATE (in which case the unification machinery + proceeds recursively.) + + + Examples: + + + + cl-prompt> (defclass foo () ((a :initform 42 :accessor foo-a))) + #<STANDARD-CLASS FOO XXXXX> + + cl-prompt> (defclass bar (foo) ()) + #<STANDARD-CLASS BAR XXXXX> + + cl-prompt> (defclass baz () + ((a :reader the-a-in-a-baz) + (b :accessor bazb :initarg :b))) + #<STANDARD-CLASS BAZ XXXXX> + + cl-prompt> (setf e (unify (make-instance 'foo) #T(foo foo-a 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (setf e (unify (make-instance 'bar) #T(foo foo-a 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'bar) #T(foo foo-a 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'baz) #T(baz the-a-in-baz 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'baz) #T(baz (slot-value b) 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'baz :b '?e) #T(baz bazb 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'bar) #T(baz foo-a 42))) + --> Error: UNIFICATION-FAILURE + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying a STANDARD-OBJECT-TEMPLATE against a non-STANDARD-OBJECT object results in + an UNIFICATION-FAILURE error being signaled. + + Unifying a STANDARD-OBJECT-TEMPLATE denoting an instance of class + C1 against an instance of class C2, results in + an UNIFICATION-FAILURE error being signaled, when C1 is not in the + class precedence list of C2. + + + See Also: + + UNIFY + + + Notes: + + None. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class STRING-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class STRING-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + STRING-TEMPLATE, VECTOR-TEMPLATE, SEQUENCE-TEMPLATE, ARRAY-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The STRING-TEMPLATE class denotes those object that are used + to unify against a STRING. + + Template Syntax: + + + + #T(string . <destructuring template lambda list>) + + + + + The STRING-TEMPLATE syntax denotes a STRING object. A + STRING-TEMPLATE must be unified against a CHARACTER VECTOR + object. The elements of the string must be unified against the + <destructuring template lambda list> + + The <destructuring template lambda list> has a + slight different interpretation in this case, in order to provide + more flexibility to the user. Ordinarily, each component appearing + in a <destructuring template lambda list> is unified + "element-wise" with the underlying SEQUENCE or ARRAY object. In the + case of a STRING-TEMPLATE, each component of the + <destructuring template lambda list> is allowed to be a + STRING or a STRING-TEMPLATE itself. The STRING or STRING-TEMPLATE + is unified against a subsequence of the CHARACTER VECTOR. + + + + + + + Examples: + + + + cl-prompt> (setf e (unify "foobar" #T(string "foob" ?x #\r))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + #\a + + cl-prompt> (setq e (unify "foobar" #T(string "FOO" #\b #\a #\r))) + --> Error: UNIFICATION-FAILURE + + cl-prompt> (setq e (unify "foobar") #T(string _ _ ?x _ _ _)) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + #\o + + cl-prompt> (setq e (unify "foobar" #T(string _ &rest ?x))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + "oobar" + + + + + Affected By: + + The value of the variable UNIFY-STRING-CASE-SENSITIVE-P. + + + Exceptional Situations: + + Unifying an STRING-TEMPLATE against a non CHARACTER VECTOR object + results in an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + + Notes: + + ARRAY Structural Properties + + There is no way to "unify" against structural properties of + vectors like fill pointers and displacements. + + Current Implementation Note + + The STRING-TEMPLATE class and the relevant UNIFY methods have not + been implemented yet. + + The actual semantics of the STRING-TEMPLATE class is not + completely clear yet. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

Class AREF-TEMPLATE

Package:

Class Precedence List:

Known Subclasses:

Slots:

Description:

Template Syntax:

Examples:

Affected By:

Exceptional Situations:

See Also:

Notes:

News

Class ARRAY-TEMPLATE

Package:

Class Precedence List:

Known Subclasses:

Slots:

Description:

Template Syntax:

Examples:

Affected By:

Exceptional Situations:

See Also:

Notes:

Syntax Note

Elements Unification

ARRAY Structural Properties

News

Control Flow

Examples

Control Flow Dictionary

Notes

Other Forms

Current Implementation Details

References

Site Map

Common Lisp Extensions: UNIFICATION Dictionary

Unification Basics

UNIFICATION Library

Site Map

CL-UNIFICATION Download Page

Download and CVS Repository

Site Map

Class ELEMENT-TEMPLATE

Package:

Class Precedence List:

Known Subclasses:

Slots:

Description:

Affected By:

Exceptional Situations:

See Also:

Notes:

News

Class ELT-TEMPLATE

Package:

Class Precedence List:

Known Subclasses:

Slots:

Description:

Template Syntax:

Examples:

Affected By:

Exceptional Situations:

See Also:

Notes:

News

Class EXPRESSION-TEMPLATE

Package:

Class Precedence List:

Known Subclasses:

Slots:

Description:

Affected By:

Exceptional Situations:

See Also:

Notes:

News

Function FIND-VARIABLE-VALUE

+ + *CL Unification: Class STRUCTURE-OBJECT-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class STRUCTURE-OBJECT-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + STRUCTURE-OBJECT-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STRUCTURE-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The STRUCTURE-OBJECT-TEMPLATE class denotes those object that are used + to unify against any STRUCTURE-OBJECT. + + + Template Syntax: + + + + #T(<CL structure class designator> [<reader function> <object>]) + + + + The STRUCTURE-OBJECT-TEMPLATE syntax denotes any + CL object that is an instance of a + STRUCTURE-OBJECT. The syntax is such that the <reader + function>* gets called against the instance against + which the STRUCTURE-OBJECT-TEMPLATE is being UNIFYed. + <object> can be any CL object, + including a TEMPLATE (in which case the unification machinery + proceeds recursively.) + + + Examples: + + + + cl-prompt> (defstruct foo () (a 42)) + FOO + + cl-prompt> (defstruct (baz (:include foo)) (b 33)) + BAZ + + cl-prompt> (setf e (unify (make-foo) #T(foo foo-a 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (setf e (unify (make-baz) #T(foo foo-a 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'bar) #T(foo foo-a 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'baz) #T(baz the-a-in-baz 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'baz :b '?e) #T(baz bazb 42))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (setf e (unify (make-instance 'bar) #T(baz foo-a 42))) + --> Error: UNIFICATION-FAILURE + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying a STRUCTURE-OBJECT-TEMPLATE against a non-STRUCTURE-OBJECT object results in + an UNIFICATION-FAILURE error being signaled. + + Unifying a STRUCTURE-OBJECT-TEMPLATE denoting an instance of structure + S1 against an instance of structure S2, results in + an UNIFICATION-FAILURE error being signaled, when S1 is not in the + class precedence list of S2. + + + See Also: + + UNIFY + + + Notes: + + None. + + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-30 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class SUBSEQ-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class SUBSEQ-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + SUBSEQ-TEMPLATE, ELEMENT-TEMPLATE, EXPRESSION-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The SUBSEQ-TEMPLATE class denotes those object that are used + to unify against a particular element of an ARRAY. + + Template Syntax: + + + + #T(subseq start end . <destructuring template lambda list>) + + + + + The SUBSEQ-TEMPLATE syntax is used to unify the elements of a + SEQUENCE starting from start and below end, against + the <destructuring template lambda list>. + + start and end must be supplied and must be valid + sequence indexes, i.e. most likely, FIXNUMs; however, end can + also be NIL, in which case the usual SUBSEQ semantics applies. + + + + Examples: + + + + cl-prompt> (setf e (unify #(0 1 42 3 4 5) #T(subseq 2 4 ?x ?y))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?x e) + 42 + T + + cl-prompt> (find-variable-value '?y e) + 3 + T + + cl-prompt> (setq e (unify #(0 1 42 3 4 5) #T(subseq 0 4 42 ?x))) + --> Error: UNIFICATION-FAILURE + + + cl-prompt> (setq e (unify "This is a string!" #T(subseq 4 nil &rest ?str))) + #<ENVIRONMENT xxx> + + cl-prompt> (find-variable-value '?str e) + " is a string!" + + + + + Affected By: + + None. + + + Exceptional Situations: + + Unifying an SUBSEQ-TEMPLATE against a non-SEQUENCE object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class SYMBOL-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class SYMBOL-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + SYMBOL-TEMPLATE, TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + None. + + + + Slots: + + None. + + + Description: + + The SYMBOL-TEMPLATE class is the class of the objects that UNIFY + recognizes as symbol templates. + + Template Syntax + + The specification of a SYMBOL-TEMPLATE has one of the two + forms below: + + + #T<symbol> + + + or + + + #T(symbol <value>) + + + where value must be either a unification variable or + a SYMBOL. + + + + Affected By: + + None. + + + Exceptional Situations: + + + Unifying a SYMBOL-TEMPLATE against a non-SYMBOL object results in + an UNIFICATION-FAILURE error being signaled. + + + See Also: + + UNIFY, NIL-TEMPLATE + + Notes: + + NIL-TEMPLATE should be used to specifically UNIFY against NIL. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + EXPRESSION-TEMPLATE, TYPE-TEMPLATE. + + + + Slots: + + + + SPEC + Type: (OR SYMBOL CONS) + Accessor: TEMPLATE-SPEC + Initarg: `:spec` (default NIL) + + + + + Description: + + The TEMPLATE class is the root of the template hierarchy. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Standard Generic Function TEMPLATE-P* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Generic function TEMPLATE-P + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + template-p object + => result + + + + Arguments and Values: + + `object`---an object + `result`---a generalized boolean + + + + Description: + + The generic function TEMPLATE-P is the predicate that tests + whether an object is of class TEMPLATE. If object is + an instance of TEMPLATE or one of its sub-classes, then TEMPLATE-P + returns a non-NIL value. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + TEMPLATE + + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-04-12 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Standard Generic Function TEMPLATE-SPEC* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Accessor TEMPLATE-SPEC + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + template-spec template + => spec + + + + + + (setf (template-spec template) spec) + => spec + + + + Arguments and Values: + + `template`---a template object + `spec`---a symbol, or a cons + + + Description: + + The accessor TEMPLATE-SPEC extracts the template + specification spec out of an instance of the class + TEMPLATE or one of its sub-classes. The SETF form sets the + spec. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + TEMPLATE, the "Template Sub-language" section. + + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-10-09 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + CL Extensions: UNIFICATION TEMPLATES + + Home + \| Downloads + \| Links + + + + + +
	+ + + + + The UNIFICATION TEMPLATES Sub-language + + The unification machinery relies on a template + sub-language to express structural patterns containing + unification variables. The template sub-language comprises + several objects organized in a hierarchy that parallels most of the + standard CL type hierarchy. + + + Unification Variables + + Unification variables are symbols with a `#\?` as the + first character of the name. This is a rather traditional choice, + although a different one based on quoted symbols is possible. + Therefore, the following are examples of variables. + + ?A ?s ?qwe ?42z ?a-variable-with-a-very-long-name ?_ + + There are two special variables, `?_` and `_`, + which are used as anonymous place holders, they match anything, but + never appear in a substitution. + + Destructuring Template Lambda List + + CL has the concept of destructuring lambda + list which is used in conjunction with the form + DSTRUCTURING-BIND, and, to some extent, with LOOP. The unifier + machinery relies on a related notion dubbed destructuring + template lambda list for lack of a better name. + + A destructuring template lambda list (or just + template lambda list) is just like a regular + destructuring lambda list (ANSI 3.4.5) with a number of + restrictions. The full syntax is the following. + + + + template-lambda-list ::= (<reqvars> <optvars> <restvar> <keyvars>) + \| (<reqvars> <optvars> . <template>) + + reqvars ::= <template>* + + optvars ::= [&optional <template>] + + restvar ::= [&rest <template>] + + keyvars ::= [&key {<template> \| ({<template> \| (<keyword-name> <template>)})} + [&allow-other-keys]] + + + + Where <template> is either an object with syntax + defined in the next section or it can be a normal + CL object. The remaining non terminal grammar + symbols have the usual CL interpretation. + + + + Unification Templates + + The unification templates are organized in an object + hierachy. There is a standard CLOS class for each + template kind. The hierarchy is shown below. + + + + + The template hierarchy is rooted at the TEMPLATE class. There are + two kinds of templates: type templates, and + expression templates. Type templates are used as patterns + of regular objects. Expression templates are used to unify against + a specific sub-structure of a given object. + + The predefined templates are: + + TEMPLATE + EXPRESSION-TEMPLATE + ELEMENT-TEMPLATE + AREF-TEMPLATE + ELT-TEMPLATE + NTH-TEMPLATE + + SUBSEQ-TEMPLATE + + TYPE-TEMPLATE + ARRAY-TEMPLATE + + SEQUENCE-TEMPLATE + + LIST-TEMPLATE + + VECTOR-TEMPLATE + + STRING-TEMPLATE + + NIL-TEMPLATE + + NUMBER-TEMPLATE + + STANDARD-OBJECT-TEMPLATE + STRUCTURE-OBJECT-TEMPLATE + + SYMBOL-TEMPLATE + + + + + + Site Map + + + Enjoy! + + + + + Questions? Queries? Suggestions? Comments? Please direct them + at me. + + + + + +
	+ + + + + + + + +
+ + © 2003-2011, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Class TYPE-TEMPLATE* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Class TYPE-TEMPLATE + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Class Precedence List: + + + TYPE-TEMPLATE, TEMPLATE, STANDARD-OBJECT, T. + + + Known Subclasses: + + + ARRAY-TEMPLATE, NIL-TEMPLATE, NUMBER-TEMPLATE, SEQUENCE-TEMPLATE, + STANDARD-OBJECT-TEMPLATE, STRUCTURE-OBJECT-TEMPLATE, SYMBOL-TEMPLATE. + + + + Slots: + + None. + + + Description: + + The TYPE-TEMPLATE class is the root of the type template sub-hierarchy. + + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + UNIFY + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-06-11 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Standard Generic Function UNIFY* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Generic function UNIFY + + Package: + + `COMMON-LISP.EXTENSIONS.DATA-AND-CONTROL-FLOW.UNIFICATION` + + + Syntax: + + + + unify object1 object2 &optional substitution + => substitution + + + + Arguments and Values: + + `object1`---an object + `object2`---an object + `substitution`---a substitution + + + + + Description: + + The generic function UNIFY is the entry point in the unification + machinery. It takes two CL objects, object1 + and object2 and checks whether they can be unified + by constructing a (possibly empty) consistent substitution assigning + appropriate values to the unification variables appearing + each object. The rules by which the unification process is carried + on are dependent on the types of the two objects. The known rules + are described in the "known methods" + section. + + UNIFY takes a substitution as an optional argument. The + default value is a fresh empty substitution obtained by + calling MAKE-EMPTY-ENVIRONMENT. + + Known Methods: + + Note that UNIFY is commutative in its two required arguments. Each + method listed exists also with object1 and object2 + reversed. + + First, the methods defined on standard CL types + are described, and then all the methods involving unification + templates are described. + + + + + + + + unify (s1 symbol) (s2 symbol) &optional substitution + => substitution + + + + The unification of two symbols depends on whether one (or both) + of them is a unification variable (i.e. either the symbol with name + `"_"`, or a symbol with name starting with the character + `#\?`.) + + If neither object is an unification variable, then UNIFY succeds + if and only if the two symbols s1 and s2 are EQ. + + If s1 is an unification variable, and either s1 is not + bound in substitution, or s1 is bound to s2 + then UNIFY succeds. If s1 was not bound in the + substitution, then a new binding for s1 to s2 + is created. + + The symmetric case holds if s1 is not an unification + variable but s2 is. + + Otherwise an error of type UNIFICATION-FAILURE is signaled. + + + + + + unify (v symbol) (object t) &optional substitution + => substitution + + + + The symbol v must be an unification variable. If not, an + error of type UNIFICATION-FAILURE will be signaled. + Otherwise, the a new binding for the variable v with value + object will be created in the substitution. + + The creation of the new binding for v in the + substitution is dependent on the occur check + implemented by the generic function OCCURS-IN-P. OCCURS-IN-P is + called by the unification machinery if the variable + OCCURRENCE-CHECK-P is non-NIL (the default.) If + OCCURENCE-CHECK-P is non-NIL, and if the variable + v occurs in the object (i.e. OCCURS-IN-P + returns a non-NIL value,) then an error of type UNIFICATION-FAILURE + is signaled. + + + + + + + unify (n1 number) (n2 number) &optional substitution + => substitution + + + + Two numbers unify if and only if they are =, in which case + substitution is returned unmodified. Otherwise, an error of + type UNIFICATION-FAILURE is signaled. + + + + + + + unify (s1 string) (s2 string) &optional substitution + => substitution + + + + Two strings unify only is they are "equal", under the following + condition. If the variable UNIFY-STRING-CASE-SENSITIVE-P is T + (the default) then the two strings s1 and s2 are + compared using STRING=, otherwise they are compared using STRING-EQUAL. + + + If the two strings s1 and s2 are equal then + substitution is returned unchanged, otherwise an error of type + UNIFICATION-FAILURE is signaled. + + + + + + unify (v1 vector) (v2 vector) &optional substitution + => substitution + + + + + + unify (l1 list) (l2 list) &optional substitution + => substitution + + + + + + unify (s1 sequence) (s2 sequence) &optional substitution + => substitution + + + + The "sequence" methods (and the specialized ones, mostly for + efficiency) extend the substitution by calling UNIFY + recursively on each element of the two sequences, s1 and + s2 (respectively, l1 and l2, v1 and + v2.) + + + An error of type UNIFICATION-FAILURE is signaled if the two + sequences are of different LENGTH or if any call to + UNIFY fails. + + + + + + + unify (a1 array) (a2 array) &optional substitution + => substitution + + + + Two arrays a1 and a2 UNIFY if and only if each of + the respective elements does. The two arrays are traversed using + ROW-MAJOR-AREF. Otherwise an error of type UNIFICATION-FAILURE is + signaled. + + An error of type UNIFICATION-FAILURE is also signaled if the two + arrays have different total size (as returned by ARRAY-TOTAL-SIZE.) + + + + + + + unify (object1 t) (object2 t) &optional substitution + => substitution + + + + This is the catch all method that is called as a last resort. + No recursive call to UNIFY is attempted, and the call succeeds if and + only if object1 and object2 are EQUALP. Otherwise, an + error of type UNIFICATION-FAILURE is signaled. + + + + + + The next methods all involve a unification template. + Again all these methods are commutative in their required + arguments. + + + + + + + unify (s structure-object) (st structure-object-template) &optional substitution + => substitution + + + + This method UNIFYs a s against a STRUCTURE-OBJECT-TEMPLATE + st. st has the following (general) structure. + + (<structure-class specifier> [ (<reader> <value>) ]* ) + + + The structure-class specifier is a symbol naming a + structure class, reader is one of the DEFSTRUCT-generated + accessors, and value is a regular CL object, + a unification variable, or a unification template. + + The class of s must be a subclass of structure-class + specifier. Otherwise, an + error of type UNIFICATION-FAILURE is signaled. + + UNIFY + is called recursively on each value and the result of + applying reader to s. + + If all the (recursive) calls to UNIFY succeed, then a possibly + augmented substitution is returned. Otherwise, an + error of type UNIFICATION-FAILURE is signaled. + + + + + + + unify (s standard-object) (st standard-object-template) &optional substitution + => substitution + + + + This method UNIFYs a s against a STANDARD-OBJECT-TEMPLATE + st. st has the following (general) structure. + + (<standard-class specifier> [ ([slot-value \| slot-accessor] <slot-spec> <value>) ]* ) + + + The standard-class specifier is a symbol naming a + class, slot-spec is a valid slot accessor when + `slot-value` is specified, or a valid slot name for the + class, when `slot-value` is specified, and value + is a regular CL object, + a unification variable, or a unification template. + + The class of s must be a subclass of standard-class + specifier. Otherwise, an + error of type UNIFICATION-FAILURE is signaled. + + UNIFY + is called recursively on each value and the result of + extracting the slot value from s using either the accessor + supplied, or SLOT-VALUE. + + If all the (recursive) calls to UNIFY succeed, then a possibly + augmented substitution is returned. Otherwise, an + error of type UNIFICATION-FAILURE is signaled. + + + + + + + Affected By: + + None. + + + Exceptional Situations: + + If object1 and object2 cannot be unified, then an + error of type UNIFICATION-FAILURE is signaled. + + + See Also: + + MAKE-EMPTY-ENVIRONMENT, UNIFICATION-FAILURE, + UNIFY-STRING-CASE-SENSITIVE-P, OCCURS-IN-P, + OCCURENCE-CHECK-P. + + Notes: + + The unification algorithm implemented is very flexible and + provides many hooks for customization. However, it is not + necessarily asymptotically efficient (it has a worst case + exponential time complexity.) + + It would be interesting to reimplement the kernel of the system + using a linear unification algorithm like the one described in + + [MM82] A. Martelli and U. Montanari, An Efficient Unification + Algorithm, ACM Transactions on Programming Languages and + Systems, Vol. 4, No. 2, April 1982, Pages 258--282. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-04-12 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +

+ + *CL Unification: Package CL.EXT.DACF.UNIFICATION* + + Home + \| Previous + \| Next + \| Downloads + \| Links + + + + + +
	+ + + + + Package CL.EXT.DACF.UNIFICATION + + Nicknames: + + `UNIFY` + + Uses: + + `COMMON-LISP` + + + Description: + + This package contains all the definitions necessary for the general + Common Lisp unifier to work. + + Affected By: + + None. + + + Exceptional Situations: + + None. + + + See Also: + + None. + + Notes: + + None. + +
	+ + + + + News + + News in chronological order, most recent on top. + + + + 2004-04-12 + Completed description. + + + + + + + +
+ + © 2003-2004, Marco Antoniotti, all rights reserved. + +