Debian Codegraph @

src/libbool.scm

raw
1 ;;;
2 ;;; libbool.scm - builtin boolean/comparison procedures
3 ;;;
4 ;;; Copyright (c) 2000-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 (select-module gauche.internal)
35
36 (inline-stub
37 (.include "gauche/priv/configP.h"
38 "gauche/vminsn.h")
39 )
40
41 ;;
42 ;; Equivalence predicates
43 ;;
44
45 (select-module scheme)
46 (define-cproc eqv? (obj1 obj2) ::<boolean> :fast-flonum :constant
47 (inliner EQV) Scm_EqvP)
48 (define-cproc eq? (obj1 obj2) ::<boolean> :fast-flonum :constant
49 (inliner EQ) SCM_EQ)
50 (define-cproc equal? (obj1 obj2) ::<boolean> :fast-flonum Scm_EqualP)
51
52 ;; This is used for the default comparator (see libomega.scm)
53 (select-module gauche.internal)
54 (define-cproc default-comparator-equal? (obj1 obj2) ::<boolean> :fast-flonum
55 (if (SCM_NUMBERP obj1)
56 (if (SCM_NUMBERP obj2)
57 (return (Scm_NumEq obj1 obj2))
58 (return FALSE))
59 (return (Scm_EqualP obj1 obj2))))
60
61 ;;
62 ;; Booleans
63 ;;
64
65 (select-module scheme)
66 (define-cproc not (obj) ::<boolean> :fast-flonum :constant
67 (inliner NOT) SCM_FALSEP)
68 (define-cproc boolean? (obj) ::<boolean> :fast-flonum :constant SCM_BOOLP)
69
70 (select-module gauche)
71 ;; a convenient coercer
72 (define-cproc boolean (obj) ::<boolean> :constant
73 (return (not (SCM_FALSEP obj))))
74
75 ;; R7RS
76 (define (boolean=? a b . args)
77 (if-let1 z (find ($ not $ boolean? $) (list* a b args))
78 (error "boolean value required, but got:" z))
79 (if a
80 (and b (every identity args))
81 (and (not b) (every not args))))
82
83 ;; Circular-safe equal?
84 ;; Based on Michael D. Adams and R. Kent Dybvig: Efficient Nondestructive
85 ;; Equality Checking for Trees and Graphs, Proceedings of ICFP 08, pp. 179-188.
86 ;; http://www.cs.indiana.edu/~dyb/pubs/equal.pdf
87 ;;
88 ;; NB: To choose restart value of K0, (modulo (sys-random) (* 2 K0)) isn't
89 ;; strictly uniform, but for our purpose it's ok. We chose K0 to be prime
90 ;; so that it would compensate if the quality of randomness of low-bits of
91 ;; sys-random is not good.
92 ;;
93 ;; %interleave-equal? is invoked from C routine Scm_EqualP, which handles
94 ;; non-aggregate values and user-defined datatypes, so we recurse to equal?
95 ;; instead of using eqv? for such case (strings are also handled in equal?).
96
97 (select-module gauche.internal)
98 (define-constant K0 401)
99 (define-constant Kb -40)
100 (define (%interleave-equal? x y) (%interleave? x y K0))
101
102 (define (%interleave? x y k)
103 (let1 ht #f
104 (define (call-union-find x y)
105 (unless ht (set! ht (make-hash-table 'eq?)))
106 (%union-find ht x y))
107 (define (e? x y k)
108 (if (<= k 0)
109 (if (= k Kb)
110 (fast? x y (modulo (sys-random) (* 2 K0)))
111 (slow? x y k))
112 (fast? x y k)))
113 (define (slow? x y k)
114 (cond
115 [(eqv? x y) k]
116 [(pair? x)
117 (and (pair? y)
118 (if (call-union-find x y)
119 0
120 (and-let* ([k (e? (car x) (car y) (- k 1))])
121 (e? (cdr x) (cdr y) k))))]
122 [(vector? x)
123 (and (vector? y)
124 (let1 n (vector-length x)
125 (and (= (vector-length y) n)
126 (if (call-union-find x y)
127 0
128 (let loop ([i 0] [k (- k 1)])
129 (if (= i n)
130 k
131 (and-let* ([k (e? (vector-ref x i)
132 (vector-ref y i) k)])
133 (loop (+ i 1) k))))))))]
134 [else (and (equal? x y) k)]))
135 (define (fast? x y k)
136 (let1 k (- k 1)
137 (cond
138 [(eqv? x y) k]
139 [(pair? x)
140 (and-let* ([ (pair? y) ]
141 [k (e? (car x) (car y) k)])
142 (e? (cdr x) (cdr y) k))]
143 [(vector? x)
144 (and (vector? y)
145 (let1 n (vector-length x)
146 (and (= (vector-length y) n)
147 (let loop ([i 0] [k k])
148 (if (= i n)
149 k
150 (and-let* ([k (e? (vector-ref x i)
151 (vector-ref y i) k)])
152 (loop (+ i 1) k)))))))]
153 [else (and (equal? x y) k)])))
154 (boolean (e? x y k))))
155
156 (define (%union-find ht x y)
157 (define (find b)
158 (let1 n (unbox b)
159 (if (box? n)
160 (let loop ([b b] [n n])
161 (let1 nn (unbox n)
162 (if (box? nn)
163 (begin
164 (set-box! b nn)
165 (loop n nn))
166 n)))
167 b)))
168 (let ([bx (hash-table-get ht x #f)]
169 [by (hash-table-get ht y #f)])
170 (if (not bx)
171 (if (not by)
172 (let1 b (box 1)
173 (hash-table-put! ht x b)
174 (hash-table-put! ht y b)
175 #f)
176 (let1 ry (find by)
177 (hash-table-put! ht x ry)
178 #f))
179 (if (not by)
180 (let1 rx (find bx)
181 (hash-table-put! ht y rx)
182 #f)
183 (let ([rx (find bx)] [ry (find by)])
184 (or (eq? rx ry)
185 (let ([nx (unbox rx)]
186 [ny (unbox ry)])
187 (if (> nx ny)
188 (begin
189 (set-box! ry rx)
190 (set-box! rx (+ nx ny))
191 #f)
192 (begin
193 (set-box! rx ry)
194 (set-box! ry (+ ny nx))
195 #f)))))))))