| 1 |
;;; |
| 2 |
;;; util.unification - Basic unification algorithm |
| 3 |
;;; |
| 4 |
;;; Copyright (c) 2016-2024 Shiro Kawai <[email protected]> |
| 5 |
;;; |
| 6 |
;;; Redistribution and use in source and binary forms, with or without |
| 7 |
;;; modification, are permitted provided that the following conditions |
| 8 |
;;; are met: |
| 9 |
;;; |
| 10 |
;;; 1. Redistributions of source code must retain the above copyright |
| 11 |
;;; notice, this list of conditions and the following disclaimer. |
| 12 |
;;; |
| 13 |
;;; 2. Redistributions in binary form must reproduce the above copyright |
| 14 |
;;; notice, this list of conditions and the following disclaimer in the |
| 15 |
;;; documentation and/or other materials provided with the distribution. |
| 16 |
;;; |
| 17 |
;;; 3. Neither the name of the authors nor the names of its contributors |
| 18 |
;;; may be used to endorse or promote products derived from this |
| 19 |
;;; software without specific prior written permission. |
| 20 |
;;; |
| 21 |
;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| 22 |
;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| 23 |
;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| 24 |
;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| 25 |
;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| 26 |
;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED |
| 27 |
;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
| 28 |
;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF |
| 29 |
;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
| 30 |
;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
| 31 |
;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| 32 |
;;; |
| 33 |
|
| 34 |
(define-module util.unification |
| 35 |
(use gauche.dictionary) |
| 36 |
(use util.match) |
| 37 |
(export unify unify-merge)) |
| 38 |
(select-module util.unification) |
| 39 |
|
| 40 |
;; Unify two trees. |
| 41 |
;; |
| 42 |
;; Tree : Variable | Value | Tuple |
| 43 |
;; Tuple : {Tree ...} |
| 44 |
;; |
| 45 |
;; The algorithm is independent of the actual representation of the trees |
| 46 |
;; to unify. The caller must provide the following parameters that abstracts |
| 47 |
;; the representation of the target tree T. |
| 48 |
;; |
| 49 |
;; var-cmpr A comparator to test, compare and hash "variables". |
| 50 |
;; Must be hashable. |
| 51 |
;; val-cmpr A comparator to test and compare "values". Values |
| 52 |
;; are non-variable terminals. A tree node that are |
| 53 |
;; neither a variable nor a value is a tuple. |
| 54 |
;; (tuple-fold proc seed x [y]) |
| 55 |
;; :: (Tree a -> a) a Tree -> a |
| 56 |
;; or (Tree Tree a -> a) a Tree Tree -> a |
| 57 |
;; Fold elements in the tuple, applying PROC, just like |
| 58 |
;; fold. It must be able to fold over one or two tuples. |
| 59 |
|
| 60 |
;; API |
| 61 |
;; Unify two trees A and B, and returns a substition dictionary |
| 62 |
;; If A and B are not unifyable, returns #t. |
| 63 |
(define (unify a b var-cmpr val-cmpr tuple-fold) |
| 64 |
|
| 65 |
(define variable? (comparator-type-test-predicate var-cmpr)) |
| 66 |
(define value? (comparator-type-test-predicate val-cmpr)) |
| 67 |
(define (tuple? x) (and (not (variable? x)) (not (value? x)))) |
| 68 |
|
| 69 |
(define (unify-rec a b dict) ;-> Maybe dict |
| 70 |
(and dict |
| 71 |
(cond [(variable? a) (unify-var a b dict)] |
| 72 |
[(variable? b) (unify-var b a dict)] |
| 73 |
[(and (value? a) (value? b)) (and (=? val-cmpr a b) dict)] |
| 74 |
[(and (tuple? a) (tuple? b)) |
| 75 |
(tuple-fold (^[a b dict] (and dict (unify-rec a b dict))) |
| 76 |
dict a b)] |
| 77 |
[else #f]))) |
| 78 |
|
| 79 |
(define (unify-var var x dict) ;-> Maybe dict |
| 80 |
(cond [(and (variable? x) (=? var-cmpr var x)) dict] |
| 81 |
[(dict-exists? dict var) (unify-rec (dict-get dict var) x dict)] |
| 82 |
[(and (variable? x) (dict-exists? dict x)) |
| 83 |
(unify-rec var (dict-get dict x) dict)] |
| 84 |
[(occurs? var x dict) #f] |
| 85 |
[else (dict-put! dict var x) dict])) |
| 86 |
|
| 87 |
(define (occurs? var x dict) ;-> bool |
| 88 |
(cond [(variable? x) |
| 89 |
(cond [(=? var-cmpr var x) #t] |
| 90 |
[(dict-exists? dict x) (occurs? var (dict-get dict x) dict)] |
| 91 |
[else #f])] |
| 92 |
[(tuple? x) |
| 93 |
(tuple-fold (^[a flag] (or flag (occurs? var a dict))) #f x)] |
| 94 |
[else #f])) |
| 95 |
|
| 96 |
(unify-rec a b (make-hash-table var-cmpr))) |
| 97 |
|
| 98 |
;; API |
| 99 |
;; Run unification on two trees A and B, and if they are unifiable, |
| 100 |
;; returns a merged tree where variables in both trees are eliminated. |
| 101 |
;; In addition to the parameters for unify, it must provide a tuple |
| 102 |
;; constructor: |
| 103 |
;; |
| 104 |
;; (make-tuple proto elements) :: Tree [Tree] -> Tree |
| 105 |
;; Returns a tuple which is the same as PROTO (e.g. number of |
| 106 |
;; elements, auxiliary attributes, etc) except its elements |
| 107 |
;; are substituted with ELEMENTS. |
| 108 |
;; |
| 109 |
(define (unify-merge a b var-cmpr val-cmpr tuple-fold make-tuple) |
| 110 |
|
| 111 |
(define variable? (comparator-type-test-predicate var-cmpr)) |
| 112 |
(define value? (comparator-type-test-predicate val-cmpr)) |
| 113 |
(define (tuple? x) (and (not (variable? x)) (not (value? x)))) |
| 114 |
|
| 115 |
(define dict (unify a b var-cmpr val-cmpr tuple-fold)) |
| 116 |
|
| 117 |
(define (subst x) |
| 118 |
(cond [(variable? x) |
| 119 |
(if (dict-exists? dict x) |
| 120 |
(subst (dict-get dict x)) |
| 121 |
x)] |
| 122 |
[(tuple? x) |
| 123 |
(let* ([elts0 (reverse (tuple-fold cons '() x))] |
| 124 |
[elts1 (map subst elts0)]) |
| 125 |
(if (every eq? elts0 elts1) |
| 126 |
x |
| 127 |
(make-tuple x elts1)))] |
| 128 |
[else x])) |
| 129 |
|
| 130 |
(and dict (subst a))) |