Debian Codegraph @

lib/util/unification.scm

raw
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)))