| 1 |
;;; |
| 2 |
;;; Matrix operations on arrays |
| 3 |
;;; |
| 4 |
;;; |
| 5 |
;;; Copyright (C) 2004 Alex Shinn ([email protected]) |
| 6 |
;;; |
| 7 |
;;; Permission to use, copy, modify, distribute this software and |
| 8 |
;;; accompanying documentation for any purpose is hereby granted, |
| 9 |
;;; provided that existing copyright notices are retained in all |
| 10 |
;;; copies and that this notice is included verbatim in all |
| 11 |
;;; distributions. |
| 12 |
;;; This software is provided as is, without express or implied |
| 13 |
;;; warranty. In no circumstances the author(s) shall be liable |
| 14 |
;;; for any damages arising out of the use of this software. |
| 15 |
;;; |
| 16 |
|
| 17 |
(select-module gauche.array) |
| 18 |
|
| 19 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 20 |
;; general array manipulation |
| 21 |
|
| 22 |
(define (array-concatenate a b :optional (dimension 0)) |
| 23 |
(let* ([a-start (start-vector-of a)] |
| 24 |
[a-end (end-vector-of a)] |
| 25 |
[b-start (start-vector-of b)] |
| 26 |
[b-end (end-vector-of b)] |
| 27 |
[diff (s32vector->vector (s32vector-sub a-start b-start))] |
| 28 |
[a-rank (s32vector-length a-start)] |
| 29 |
[b-rank (s32vector-length b-start)]) |
| 30 |
(unless (= a-rank b-rank) |
| 31 |
(error "rank mismatch")) |
| 32 |
(unless (every (^d (or (= d dimension) |
| 33 |
(= (- (s32vector-ref a-end d) (s32vector-ref a-start d)) |
| 34 |
(- (s32vector-ref b-end d) (s32vector-ref b-start d))))) |
| 35 |
(iota a-rank)) |
| 36 |
(error "shape mismatch")) |
| 37 |
(let ([c-start (s32vector-copy a-start)] |
| 38 |
[c-end (s32vector-copy a-end)]) |
| 39 |
(s32vector-set! c-end dimension (+ (s32vector-ref c-end dimension) |
| 40 |
(- (s32vector-ref b-end dimension) |
| 41 |
(s32vector-ref b-start dimension)))) |
| 42 |
(let ([c (make-minimal-backend-array |
| 43 |
(list a b) (start/end-vector->shape c-start c-end))] |
| 44 |
[off (- (s32vector-ref a-end dimension) (s32vector-ref a-start dimension))]) |
| 45 |
(array-for-each-index a |
| 46 |
(^i (array-set! c i (array-ref a i))) |
| 47 |
(make-vector a-rank)) |
| 48 |
(array-for-each-index b |
| 49 |
(^i (let1 j (vector-copy i) |
| 50 |
(dotimes [dim a-rank] |
| 51 |
(vector-set! j dim (+ (vector-ref j dim) (vector-ref diff dim)))) |
| 52 |
(vector-set! j dimension (+ off (vector-ref j dimension))) |
| 53 |
(array-set! c j (array-ref b i)))) |
| 54 |
(make-vector b-rank)) |
| 55 |
c)))) |
| 56 |
|
| 57 |
(define (array-transpose a :optional (dim1 0) (dim2 1)) |
| 58 |
(let* ([sh (array-copy (array-shape a))] |
| 59 |
[rank (array-rank a)] |
| 60 |
[tmp0 (array-ref sh dim1 0)] |
| 61 |
[tmp1 (array-ref sh dim1 1)]) |
| 62 |
(array-set! sh dim1 0 (array-ref sh dim2 0)) |
| 63 |
(array-set! sh dim1 1 (array-ref sh dim2 1)) |
| 64 |
(array-set! sh dim2 0 tmp0) |
| 65 |
(array-set! sh dim2 1 tmp1) |
| 66 |
(rlet1 res (make-array-internal (class-of a) sh) |
| 67 |
(array-for-each-index a |
| 68 |
(^[vec1] (let* ([vec2 (vector-copy vec1)] |
| 69 |
[tmp (vector-ref vec2 dim1)]) |
| 70 |
(vector-set! vec2 dim1 (vector-ref vec2 dim2)) |
| 71 |
(vector-set! vec2 dim2 tmp) |
| 72 |
(array-set! res vec2 (array-ref a vec1)))) |
| 73 |
(make-vector rank))))) |
| 74 |
|
| 75 |
(define (array-rotate-90 a :optional (dim1 0) (dim2 1)) |
| 76 |
(let* ([sh (array-copy (array-shape a))] |
| 77 |
[rank (array-rank a)] |
| 78 |
[tmp0 (array-ref sh dim1 0)] |
| 79 |
[tmp1 (array-ref sh dim1 1)] |
| 80 |
[off (- (array-ref sh dim1 1) 1)]) |
| 81 |
(array-set! sh dim1 0 (array-ref sh dim2 0)) |
| 82 |
(array-set! sh dim1 1 (array-ref sh dim2 1)) |
| 83 |
(array-set! sh dim2 0 tmp0) |
| 84 |
(array-set! sh dim2 1 tmp1) |
| 85 |
(rlet1 res (make-array-internal (class-of a) sh) |
| 86 |
(array-for-each-index a |
| 87 |
(^[vec1] (let* ([vec2 (vector-copy vec1)] |
| 88 |
[tmp (vector-ref vec2 dim1)]) |
| 89 |
(vector-set! vec2 dim1 (vector-ref vec2 dim2)) |
| 90 |
(vector-set! vec2 dim2 (- off tmp)) |
| 91 |
(array-set! res vec2 (array-ref a vec1)))) |
| 92 |
(make-vector rank))))) |
| 93 |
|
| 94 |
(define (array-flip! a :optional (dimension 0)) |
| 95 |
(let* ([lo (s32vector-ref (start-vector-of a) dimension)] |
| 96 |
[end (end-vector-of a)] |
| 97 |
[hi (s32vector-ref end dimension)] |
| 98 |
[half (quotient hi 2)] |
| 99 |
[rank (s32vector-length end)]) |
| 100 |
(array-for-each-index-by-dimension a (delete! dimension (iota rank)) |
| 101 |
(^[vec1] |
| 102 |
(do ([i lo (+ i 1)]) |
| 103 |
[(= i half)] |
| 104 |
(vector-set! vec1 dimension i) |
| 105 |
(let* ([j (- hi i 1)] |
| 106 |
[vec2 (vector-copy vec1)] |
| 107 |
[tmp (array-ref a vec1)]) |
| 108 |
(vector-set! vec2 dimension j) |
| 109 |
(array-set! a vec1 (array-ref a vec2)) |
| 110 |
(array-set! a vec2 tmp)))) |
| 111 |
(make-vector rank)) |
| 112 |
a)) |
| 113 |
|
| 114 |
(define (array-flip a . args) |
| 115 |
(rlet1 res (array-copy a) |
| 116 |
(apply array-flip! res args))) |
| 117 |
|
| 118 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 119 |
;; linear algebra |
| 120 |
|
| 121 |
(define (identity-array n :optional (class <array>)) |
| 122 |
(let1 res (make-array-internal class (shape 0 n 0 n) 0) |
| 123 |
(do ([i 0 (+ i 1)]) |
| 124 |
[(= i n) res] |
| 125 |
(array-set! res i i 1)))) |
| 126 |
|
| 127 |
;; Gaussian elimination, returns factor applied to determinant |
| 128 |
(define (array-row-echelon! a) |
| 129 |
(let* ([start (start-vector-of a)] |
| 130 |
[row-start (s32vector-ref start 0)] |
| 131 |
[col-start (s32vector-ref start 1)] |
| 132 |
[end (end-vector-of a)] |
| 133 |
[row-end (s32vector-ref end 0)] |
| 134 |
[col-end (s32vector-ref end 1)] |
| 135 |
[row-col-offset (- row-start col-start)]) |
| 136 |
(define (row-swap! i j) |
| 137 |
(do ([k col-start (+ k 1)]) |
| 138 |
[(= k col-end)] |
| 139 |
(let1 temp (array-ref a i k) |
| 140 |
(array-set! a i k (array-ref a j k)) |
| 141 |
(array-set! a j k temp)))) |
| 142 |
(define (row-sub! i j factor) |
| 143 |
(do ([k col-start (+ k 1)]) |
| 144 |
[(= k col-end)] |
| 145 |
(array-set! a i k (- (array-ref a i k) (* factor (array-ref a j k)))))) |
| 146 |
(let loop ([i row-start] [factor 1]) |
| 147 |
(let1 col (- i row-col-offset) |
| 148 |
(cond [(= i row-end) factor] |
| 149 |
[(zero? (array-ref a i col)) |
| 150 |
;; pivot non-zero row to top |
| 151 |
(let loop2 ((j (+ i 1))) |
| 152 |
(cond [(= j row-end) 0] |
| 153 |
[(zero? (array-ref a j col)) |
| 154 |
(loop2 (+ j 1))] |
| 155 |
[else |
| 156 |
(row-swap! j i) |
| 157 |
(loop i (* factor -1))]))] |
| 158 |
[else |
| 159 |
;; eliminate other non-zero rows |
| 160 |
(let loop2 ([j (+ i 1)]) |
| 161 |
(cond [(= j row-end) (loop (+ i 1) factor)] |
| 162 |
[(zero? (array-ref a j col)) |
| 163 |
(loop2 (+ j 1))] |
| 164 |
[else |
| 165 |
(let1 factor (/ (array-ref a j col) |
| 166 |
(array-ref a i col)) |
| 167 |
(row-sub! j i factor) |
| 168 |
(loop2 (+ j 1)))]))]))))) |
| 169 |
|
| 170 |
(define (array-solve-left-identity! a) |
| 171 |
(array-row-echelon! a) |
| 172 |
(let* ([start (start-vector-of a)] |
| 173 |
[row-start (s32vector-ref start 0)] |
| 174 |
[col-start (s32vector-ref start 1)] |
| 175 |
[end (end-vector-of a)] |
| 176 |
[row-end (s32vector-ref end 0)] |
| 177 |
[col-end (s32vector-ref end 1)] |
| 178 |
[row-col-offset (- row-start col-start)]) |
| 179 |
;; zero-out |
| 180 |
(do ([i (- row-end 1) (- i 1)]) ; for-each row in reverse |
| 181 |
[(< i row-start)] |
| 182 |
(let1 divisor (array-ref a i (- i row-col-offset)) |
| 183 |
(unless (zero? divisor) |
| 184 |
(do ([j (- i 1) (- j 1)]) ; for-each lower row |
| 185 |
[(< j row-start)] |
| 186 |
(let1 factor (/ (array-ref a j (- i row-col-offset)) divisor) |
| 187 |
(array-set! a i (- j row-col-offset) 0) |
| 188 |
(do ([k (- j row-col-offset) (+ k 1)]) ; for-each column |
| 189 |
[(= k col-end)] |
| 190 |
(array-set! a j k (- (array-ref a j k) |
| 191 |
(* factor (array-ref a i k)))))))))) |
| 192 |
;; reduce |
| 193 |
(do ([i row-start (+ i 1)]) ; for-each row |
| 194 |
[(= i row-end)] |
| 195 |
(let1 divisor (array-ref a i (- i row-col-offset)) |
| 196 |
(unless (or (zero? divisor) (= divisor 1)) |
| 197 |
(array-set! a i (- i row-col-offset) 1) |
| 198 |
(do ([j (- i row-col-offset -1) (+ j 1)]) ; for-each higher column |
| 199 |
[(= j col-end)] |
| 200 |
(array-set! a i j (/ (array-ref a i j) divisor)))))))) |
| 201 |
|
| 202 |
(define (array-inverse a) |
| 203 |
(let* ([start (start-vector-of a)] |
| 204 |
[end (end-vector-of a)] |
| 205 |
[rank (s32vector-length start)] |
| 206 |
[n (- (s32vector-ref end 0) (s32vector-ref start 0))] |
| 207 |
[m (- (s32vector-ref end 1) (s32vector-ref start 1))]) |
| 208 |
(unless (= 2 rank) |
| 209 |
(error "can only compute inverses of 2D arrays")) |
| 210 |
(unless (= n m) |
| 211 |
(error "can only compute inverses of square matrices")) |
| 212 |
(let* ([class (class-of a)] |
| 213 |
[id (identity-array n (if (or (eq? class <f32array>) |
| 214 |
(eq? class <f64array>)) |
| 215 |
class <array>))] |
| 216 |
[tmp (array-concatenate a id 1)]) |
| 217 |
(array-solve-left-identity! tmp) |
| 218 |
(and (= 1 (array-ref tmp (- (s32vector-ref end 0) 1) |
| 219 |
(- (s32vector-ref end 1) 1))) |
| 220 |
(subarray tmp (shape (s32vector-ref start 0) (s32vector-ref end 0) |
| 221 |
(s32vector-ref end 1) (+ (s32vector-ref end 1) n))))))) |
| 222 |
|
| 223 |
|
| 224 |
(define (determinant! a) |
| 225 |
(let* ([start (s32vector->list (start-vector-of a))] |
| 226 |
[end (s32vector->list (end-vector-of a))] |
| 227 |
[row-col-offset (- (car start) (cadr start))] |
| 228 |
[factor (array-row-echelon! a)]) |
| 229 |
(unless (= 2 (length start)) ; add determinant for the 2x2x2 case? |
| 230 |
(error "can't compute hyperdeterminants in the general case")) |
| 231 |
(unless (apply = (map - end start)) |
| 232 |
(error "can't compute determinants of non-square matrices")) |
| 233 |
(apply * factor (map (^i (array-ref a i (- i row-col-offset))) |
| 234 |
(map (cute + <> (car start)) |
| 235 |
(iota (- (car end) (car start)))))))) |
| 236 |
|
| 237 |
(define (determinant a) |
| 238 |
(let1 class (class-of a) |
| 239 |
(if (or (eq? class <f32array>) |
| 240 |
(eq? class <f64array>) |
| 241 |
(eq? class <array>)) |
| 242 |
(determinant! (array-copy a)) |
| 243 |
(let* ([rank (s32vector-length (start-vector-of a))] |
| 244 |
[b (tabulate-array (array-shape a) |
| 245 |
(^[ind] (array-ref a ind)) |
| 246 |
(make-vector rank))]) |
| 247 |
(determinant! b))))) |
| 248 |
|
| 249 |
|
| 250 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 251 |
;; matrix arithmetic |
| 252 |
|
| 253 |
(define (%array-mul r a b) ; NxM * MxP => NxP |
| 254 |
(let ([a-start (start-vector-of a)] |
| 255 |
[a-end (end-vector-of a)] |
| 256 |
[b-start (start-vector-of b)] |
| 257 |
[b-end (end-vector-of b)]) |
| 258 |
(unless (= 2 (s32vector-length a-start) (s32vector-length b-start)) |
| 259 |
(error "array-mul matrices must be of rank 2")) |
| 260 |
(let ([a-start-row (s32vector-ref a-start 0)] |
| 261 |
[a-end-row (s32vector-ref a-end 0)] |
| 262 |
[a-start-col (s32vector-ref a-start 1)] |
| 263 |
[a-end-col (s32vector-ref a-end 1)] |
| 264 |
[b-start-col (s32vector-ref b-start 1)] |
| 265 |
[b-end-col (s32vector-ref b-end 1)]) |
| 266 |
(let ([n (- a-end-row a-start-row)] |
| 267 |
[m (- a-end-col a-start-col)] |
| 268 |
[p (- b-end-col b-start-col)] |
| 269 |
[a-col-b-row-off (- a-start-col (s32vector-ref b-start 0))]) |
| 270 |
(unless (= m (- (s32vector-ref b-end 0) (s32vector-ref b-start 0))) |
| 271 |
(errorf "dimension mismatch: can't multiply shapes ~S and ~S" |
| 272 |
(array-shape a) (array-shape b))) |
| 273 |
'(when (and r (not (and (= n (array-length r 0)) |
| 274 |
(= p (array-length r 1))))) |
| 275 |
(errof "result array can't hold the result of multiplication")) |
| 276 |
(rlet1 res (or r (make-minimal-backend-array (list a b) (shape 0 n 0 p))) |
| 277 |
(do ([i a-start-row (+ i 1)]) ; for-each row of a |
| 278 |
[(= i a-end-row)] |
| 279 |
(do ([k b-start-col (+ k 1)]) ; for-each col of b |
| 280 |
[(= k b-end-col)] |
| 281 |
(let1 tmp 0 |
| 282 |
(do ([j a-start-col (+ j 1)]) ; for-each col of a & row of b |
| 283 |
[(= j a-end-col)] |
| 284 |
(inc! tmp (* (array-ref a i j) |
| 285 |
(array-ref b (- j a-col-b-row-off) k)))) |
| 286 |
(array-set! res (- i a-start-row) (- k b-start-col) tmp))))))))) |
| 287 |
|
| 288 |
(define (array-mul a b) (%array-mul #f a b)) |
| 289 |
|
| 290 |
;; array and vector multiplication utility |
| 291 |
;; We can do better to avoid runtime dispatching every time. Optimization |
| 292 |
;; will come later. |
| 293 |
(define (vref v i) |
| 294 |
(if (vector? v) |
| 295 |
(vector-ref v i) |
| 296 |
(uvector-ref v i))) |
| 297 |
|
| 298 |
(define (vset! v i n) |
| 299 |
(if (vector? v) |
| 300 |
(vector-set! v i n) |
| 301 |
(uvector-set! v i n))) |
| 302 |
|
| 303 |
(define (vlen v) |
| 304 |
(if (vector? v) |
| 305 |
(vector-length v) |
| 306 |
(uvector-length v))) |
| 307 |
|
| 308 |
(define (make-v class len) |
| 309 |
(if (eq? class <vector>) |
| 310 |
(make-vector len 0) |
| 311 |
(make-uvector class len 0))) |
| 312 |
|
| 313 |
;; Array x vector |
| 314 |
(define (%array-vector-mul r a v) |
| 315 |
(let ([a-start (start-vector-of a)] |
| 316 |
[a-end (end-vector-of a)]) |
| 317 |
(assume (= 2 (s32vector-length a-start)) |
| 318 |
"array-vector-mul matrices must be of rank 2") |
| 319 |
(assume (or (vector? v) (uvector? v)) |
| 320 |
"vector or uvector required, but got:" v) |
| 321 |
(let ([a-start-row (s32vector-ref a-start 0)] |
| 322 |
[a-end-row (s32vector-ref a-end 0)] |
| 323 |
[a-start-col (s32vector-ref a-start 1)] |
| 324 |
[a-end-col (s32vector-ref a-end 1)]) |
| 325 |
(let ([n (- a-end-row a-start-row)] |
| 326 |
[m (- a-end-col a-start-col)]) |
| 327 |
(unless (= m (vlen v)) |
| 328 |
(errorf "dimension mismatch: can't multiply shapes ~S and ~S" |
| 329 |
(array-shape a) (vlen v))) |
| 330 |
(rlet1 r (or r (make-v (class-of v) n)) |
| 331 |
(do ([i a-start-row (+ i 1)]) ; for-each row of a |
| 332 |
[(= i a-end-row)] |
| 333 |
(let1 tmp 0 |
| 334 |
(do ([j a-start-col (+ j 1)] ; for-each col of a & b |
| 335 |
[k 0 (+ k 1)]) |
| 336 |
[(= j a-end-col)] |
| 337 |
(inc! tmp (* (array-ref a i j) (vref v k)))) |
| 338 |
(vset! r i tmp)))))))) |
| 339 |
|
| 340 |
(define (array-vector-mul a v) (%array-vector-mul #f a v)) |
| 341 |
|
| 342 |
;; Vector x array |
| 343 |
(define (%vector-array-mul r v a) |
| 344 |
(let ([a-start (start-vector-of a)] |
| 345 |
[a-end (end-vector-of a)]) |
| 346 |
(assume (= 2 (s32vector-length a-start)) |
| 347 |
"array-vector-mul matrices must be of rank 2") |
| 348 |
(assume (or (vector? v) (uvector? v)) |
| 349 |
"vector or uvector required, but got:" v) |
| 350 |
(let ([a-start-row (s32vector-ref a-start 0)] |
| 351 |
[a-end-row (s32vector-ref a-end 0)] |
| 352 |
[a-start-col (s32vector-ref a-start 1)] |
| 353 |
[a-end-col (s32vector-ref a-end 1)]) |
| 354 |
(let ([n (- a-end-row a-start-row)] |
| 355 |
[m (- a-end-col a-start-col)]) |
| 356 |
(unless (= n (vlen v)) |
| 357 |
(errorf "dimension mismatch: can't multiply shapes ~S and ~S" |
| 358 |
(vlen v) (array-shape a))) |
| 359 |
(rlet1 r (or r (make-v (class-of v) m)) |
| 360 |
(do ([i a-start-col (+ i 1)]) ; for-each col of a |
| 361 |
[(= i a-end-col)] |
| 362 |
(let1 tmp 0 |
| 363 |
(do ([j a-start-row (+ j 1)] ; for-each row of a & b |
| 364 |
[k 0 (+ k 1)]) |
| 365 |
[(= j a-end-row)] |
| 366 |
(inc! tmp (* (vref v k) (array-ref a j i)))) |
| 367 |
(vset! r i tmp)))))))) |
| 368 |
|
| 369 |
(define (vector-array-mul a v) (%vector-array-mul #f a v)) |
| 370 |
|
| 371 |
(define (array-div-left a b) |
| 372 |
(if-let1 b-1 (array-inverse b) |
| 373 |
(array-mul b-1 a) |
| 374 |
(error "Matrix is not regular:" b))) |
| 375 |
|
| 376 |
(define (array-div-right a b) |
| 377 |
(if-let1 b-1 (array-inverse b) |
| 378 |
(array-mul a b-1) |
| 379 |
(error "Matrix is not regular:" b))) |
| 380 |
|
| 381 |
(define (array-expt ar pow) |
| 382 |
(let loop ([a ar] [n pow]) |
| 383 |
(case n |
| 384 |
[(0) (identity-array (s32vector-length (start-vector-of a)) (class-of a))] |
| 385 |
[(1) a] |
| 386 |
[(2) (array-mul a a)] |
| 387 |
[(3) (array-mul (array-mul a a) a)] |
| 388 |
[else |
| 389 |
(let* ([res1 (loop a (ash n -1))] |
| 390 |
[res (array-mul res1 res1)]) |
| 391 |
(if (odd? n) |
| 392 |
(array-mul res a) |
| 393 |
res))]))) |
| 394 |
|
| 395 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 396 |
;; element-wise operations (advantage over a direct array-map! is |
| 397 |
;; ability to intermingle scalars) |
| 398 |
|
| 399 |
;; add |
| 400 |
|
| 401 |
(define-method array-add-elements! ((a <array-base>) b c . rest) |
| 402 |
(array-add-elements! a b) |
| 403 |
(apply array-add-elements! a c rest)) |
| 404 |
|
| 405 |
(define-method array-add-elements! ((a <array-base>)) |
| 406 |
a) |
| 407 |
|
| 408 |
(define-method array-add-elements! ((a <array-base>) (b <number>)) |
| 409 |
(array-map! a (^i (+ b i)) a) |
| 410 |
a) |
| 411 |
|
| 412 |
(define-method array-add-elements! ((a <number>) (b <array-base>)) |
| 413 |
(rlet1 res (array-copy b) |
| 414 |
(array-map! res (^i (+ a i)) b))) |
| 415 |
|
| 416 |
(define-method array-add-elements! ((a <array-base>) (b <array-base>)) |
| 417 |
(array-map! a (^[i j] (+ i j)) a b) |
| 418 |
a) |
| 419 |
|
| 420 |
(define (array-add-elements a . rest) |
| 421 |
(if (null? rest) |
| 422 |
(begin (assume (array? a)) a) |
| 423 |
(apply array-add-elements! (array-copy a) rest))) |
| 424 |
|
| 425 |
;; sub |
| 426 |
|
| 427 |
(define-method array-sub-elements! ((a <array-base>)) a) |
| 428 |
|
| 429 |
|
| 430 |
(define-method array-sub-elements! ((a <array-base>) b c . rest) |
| 431 |
(array-sub-elements! a b) |
| 432 |
(apply array-sub-elements! a c rest)) |
| 433 |
|
| 434 |
(define-method array-sub-elements! ((a <array-base>) (b <number>)) |
| 435 |
(array-map! a (^i (- i b)) a) |
| 436 |
a) |
| 437 |
|
| 438 |
(define-method array-sub-elements! ((a <number>) (b <array-base>)) |
| 439 |
(rlet1 res (array-copy b) |
| 440 |
(array-map! res (^i (- a i)) b))) |
| 441 |
|
| 442 |
(define-method array-sub-elements! ((a <array-base>) (b <array-base>)) |
| 443 |
(array-map! a (^[i j] (- i j)) a b) |
| 444 |
a) |
| 445 |
|
| 446 |
(define (array-sub-elements a . rest) |
| 447 |
(if (null? rest) |
| 448 |
(begin (assume (array? a)) a) |
| 449 |
(apply array-sub-elements! (array-copy a) rest))) |
| 450 |
|
| 451 |
(define (array-negate-elements! a) (array-sub-elements! 0 a)) |
| 452 |
(define (array-negate-elements a) (array-sub-elements! 0 (array-copy a))) |
| 453 |
|
| 454 |
;; mul |
| 455 |
|
| 456 |
(define-method array-mul-elements! ((a <array-base>) b c . rest) |
| 457 |
(array-mul-elements! a b) |
| 458 |
(apply array-mul-elements! a c rest)) |
| 459 |
|
| 460 |
(define-method array-mul-elements! ((a <array-base>)) |
| 461 |
a) |
| 462 |
|
| 463 |
(define-method array-mul-elements! ((a <array-base>) (b <number>)) |
| 464 |
(array-map! a (^i (* b i)) a) |
| 465 |
a) |
| 466 |
|
| 467 |
(define-method array-mul-elements! ((a <number>) (b <array-base>)) |
| 468 |
(rlet1 res (array-copy b) |
| 469 |
(array-map! res (^i (* a i)) b))) |
| 470 |
|
| 471 |
(define-method array-mul-elements! ((a <array-base>) (b <array-base>)) |
| 472 |
(array-map! a (^[i j] (* i j)) a b) |
| 473 |
a) |
| 474 |
|
| 475 |
(define (array-mul-elements a . rest) |
| 476 |
(if (null? rest) |
| 477 |
(begin (assume (array? a)) a) |
| 478 |
(apply array-mul-elements! (array-copy a) rest))) |
| 479 |
|
| 480 |
;; div |
| 481 |
|
| 482 |
(define-method array-div-elements! ((a <array-base>) b c . rest) |
| 483 |
(array-div-elements! a b) |
| 484 |
(apply array-div-elements! a c rest)) |
| 485 |
|
| 486 |
(define-method array-div-elements! ((a <array-base>)) |
| 487 |
a) |
| 488 |
|
| 489 |
(define-method array-div-elements! ((a <array-base>) (b <number>)) |
| 490 |
(array-map! a (^i (/ i b)) a) |
| 491 |
a) |
| 492 |
|
| 493 |
(define-method array-div-elements! ((a <number>) (b <array-base>)) |
| 494 |
(rlet1 res (array-copy b) |
| 495 |
(array-map! res (^i (/ a i)) b))) |
| 496 |
|
| 497 |
(define-method array-div-elements! ((a <array-base>) (b <array-base>)) |
| 498 |
(array-map! a (^[i j] (/ i j)) a b) |
| 499 |
a) |
| 500 |
|
| 501 |
(define (array-div-elements a . rest) |
| 502 |
(if (null? rest) |
| 503 |
(begin (assume (array? a)) a) |
| 504 |
(apply array-div-elements! (array-copy a) rest))) |
| 505 |
|
| 506 |
(define (array-reciprocate-elements! a) (array-div-elements! 1 a)) |
| 507 |
(define (array-reciprocate-elements a) (array-div-elements! 1 (array-copy a))) |
| 508 |
|
| 509 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 510 |
;; utilities |
| 511 |
|
| 512 |
;; Nicely formatted printing for arrays of any rank, by default both |
| 513 |
;; readable (using #,() syntax) and filled so columns line up. Ranks |
| 514 |
;; higher than 2 are represented as successive 2D drawings. |
| 515 |
;; |
| 516 |
;; Can generate (generally non-readable) box drawings with :left, |
| 517 |
;; :right, etc. keywords. For examples, Jacal-style matrix output can |
| 518 |
;; be done with: |
| 519 |
;; |
| 520 |
;; (pretty-print-array a #t :readable? #f :left "[" :right "]") |
| 521 |
;; |
| 522 |
;; and a tic-tac-toe board can be printed with |
| 523 |
;; |
| 524 |
;; (pretty-print-array a #t :readable? #f :line-char "|" |
| 525 |
;; :top "-" :middle-col "|" :center-row "-") |
| 526 |
;; |
| 527 |
;; The API is subject to change. |
| 528 |
|
| 529 |
(define (pretty-print-array a :optional (port (current-output-port)) |
| 530 |
:key (readable? #t) (fill? #t) |
| 531 |
(line-char #f) (left line-char) (right left) |
| 532 |
(middle-col #\space) (top line-char) |
| 533 |
(bottom top) (center-row #f) (pad-char #\space)) |
| 534 |
(let* ([p (cond [(port? port) port] |
| 535 |
[port (current-output-port)] |
| 536 |
[else (open-output-string)])] |
| 537 |
[rank (array-rank a)] |
| 538 |
[row-dim (- rank 2)] |
| 539 |
[col-dim (- rank 1)] |
| 540 |
[shape (array-shape a)] |
| 541 |
[shape-list (array->list shape)] |
| 542 |
[inner-shape (take-right shape-list 4)] |
| 543 |
[nrows (cadr inner-shape)] |
| 544 |
[ncols (cadddr inner-shape)]) |
| 545 |
|
| 546 |
(define (replicate x width) |
| 547 |
(if (char? x) |
| 548 |
(make-string width x) |
| 549 |
(let1 len (string-length x) |
| 550 |
(if (eq? len 1) |
| 551 |
(make-string width (string-ref x 0)) |
| 552 |
(receive (quot rem) (quotient&remainder width len) |
| 553 |
(string-append |
| 554 |
(apply string-append (map (^n x) (iota quot))) |
| 555 |
(substring x 0 rem))))))) |
| 556 |
(define (pad x width) |
| 557 |
(let* ([res (x->string x)] |
| 558 |
[len (string-length res)]) |
| 559 |
(if (< len width) |
| 560 |
(string-append (make-string (- width len) pad-char) res ) |
| 561 |
res))) |
| 562 |
(define (print-width x) |
| 563 |
(cond [(char? x) 1] |
| 564 |
[(string? x) (string-length x)] |
| 565 |
[else (string-length (x->string x))])) |
| 566 |
(let1 fixed-width (+ (if left (print-width left) 0) |
| 567 |
(if right (print-width right) 0) |
| 568 |
(if middle-col (* (- ncols 1) (print-width middle-col)) 0)) |
| 569 |
(define (column-widths vec) |
| 570 |
(let loop1 ([col (caddr inner-shape)] [res '()]) |
| 571 |
(cond |
| 572 |
[(< col ncols) |
| 573 |
(vector-set! vec col-dim col) |
| 574 |
(let loop2 ([row (car inner-shape)] [x 0]) |
| 575 |
(cond |
| 576 |
[(< row nrows) |
| 577 |
(vector-set! vec row-dim row) |
| 578 |
(loop2 (+ row 1) (max x (print-width (array-ref a vec))))] |
| 579 |
[else |
| 580 |
(loop1 (+ col 1) (cons x res))]))] |
| 581 |
[else (reverse res)]))) |
| 582 |
(define (print2d vec) |
| 583 |
(newline p) |
| 584 |
(let* ([widths (if fill? (column-widths (vector-copy vec)) '())] |
| 585 |
[total-width (apply + fixed-width widths)]) |
| 586 |
(when top |
| 587 |
(display (if fill? (replicate top total-width) top) p) |
| 588 |
(newline p)) |
| 589 |
(let loop1 ([row (car inner-shape)]) |
| 590 |
(when (< row nrows) |
| 591 |
(when left (display left p)) |
| 592 |
(vector-set! vec row-dim row) |
| 593 |
(let loop2 ([col (caddr inner-shape)] [w widths]) |
| 594 |
(when (< col ncols) |
| 595 |
(vector-set! vec col-dim col) |
| 596 |
(display (if (pair? w) |
| 597 |
(pad (array-ref a vec) (car w)) |
| 598 |
(array-ref a vec)) |
| 599 |
p) |
| 600 |
(when (and middle-col (< (+ col 1) ncols)) |
| 601 |
(display middle-col p)) |
| 602 |
(loop2 (+ col 1) (if (pair? w) (cdr w) w)))) |
| 603 |
(when right (display right p)) |
| 604 |
(newline p) |
| 605 |
(when (and center-row (< (+ row 1) nrows)) |
| 606 |
(display (if fill? (replicate bottom total-width) bottom)) |
| 607 |
(newline p)) |
| 608 |
(loop1 (+ row 1)))) |
| 609 |
(when bottom |
| 610 |
(display (if fill? (replicate bottom total-width) bottom) p) |
| 611 |
(newline p)))) |
| 612 |
(cond |
| 613 |
[(< rank 2) |
| 614 |
(if readable? (write a p) (display a p))] |
| 615 |
[else |
| 616 |
(when readable? |
| 617 |
(format p "#,(~A ~S" (class-name (class-of a)) shape-list)) |
| 618 |
(if (= rank 2) |
| 619 |
(print2d (make-vector rank)) |
| 620 |
(array-for-each-index-by-dimension |
| 621 |
a (drop-right (iota rank) 2) |
| 622 |
print2d |
| 623 |
(make-vector rank))) |
| 624 |
(when readable? |
| 625 |
(format p " )")) |
| 626 |
(newline p)]) |
| 627 |
(if (not port) (get-output-string p))))) |
| 628 |
|
| 629 |
|
| 630 |
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; |
| 631 |
;; internal utility to keep arrays uniform when possible |
| 632 |
|
| 633 |
(define *signed-arrays* |
| 634 |
(list <s64array> <s32array> <s16array> <s8array>)) |
| 635 |
|
| 636 |
(define (make-minimal-backend-array ls sh . args) |
| 637 |
(define (return class) |
| 638 |
(apply make-array-internal class sh args)) |
| 639 |
(define (signed? x) |
| 640 |
(member x *signed-arrays*)) |
| 641 |
(define (size x) |
| 642 |
(cond [(or (eq? x <s64array>) (eq? x <u64array>)) 64] |
| 643 |
[(or (eq? x <s32array>) (eq? x <u32array>)) 32] |
| 644 |
[(or (eq? x <s16array>) (eq? x <u16array>)) 16] |
| 645 |
[(or (eq? x <s8array>) (eq? x <u8array>)) 8] |
| 646 |
[else 0])) |
| 647 |
(define (backend signed? size) |
| 648 |
(if signed? |
| 649 |
(case size |
| 650 |
[(64) <s64array>] [(32) <s32array>] [(16) <s16array>] [(8) <s8array>] [else <array>]) |
| 651 |
(case size |
| 652 |
[(64) <u64array>] [(32) <u32array>] [(16) <u16array>] [(8) <u8array>] [else <array>]))) |
| 653 |
(define (join a b) |
| 654 |
(cond [(or (eq? a <array>) (eq? b <array>)) <array>] |
| 655 |
[(or (eq? a <f32array>) (eq? a <f64array>)) |
| 656 |
(if (or (eq? b <f32array>) (eq? b <f64array>)) |
| 657 |
(if (eq? a b) a <f64array>) |
| 658 |
<array>)] |
| 659 |
[else |
| 660 |
(let ([a-s? (signed? a)] |
| 661 |
[a-size (size a)] |
| 662 |
[b-s? (signed? b)] |
| 663 |
[b-size (size b)]) |
| 664 |
(if (or (zero? a-size) (zero? b-size)) |
| 665 |
<array> |
| 666 |
(let1 res-size (max a-size b-size) |
| 667 |
(backend (or a-s? b-s?) |
| 668 |
(if (if a-s? (not b-s?) b-s?) |
| 669 |
(* 2 res-size) ; signs differ, double size |
| 670 |
res-size)))))])) |
| 671 |
(let loop ([class (class-of (car ls))] [l ls]) |
| 672 |
(if (null? l) |
| 673 |
(return class) |
| 674 |
(let1 next (join class (class-of (car l))) |
| 675 |
(if (eq? next <array>) |
| 676 |
(return <array>) ; already most general array |
| 677 |
(loop next (cdr l))))))) |