| 1 |
;; tests for delayed evaluation constructs |
| 2 |
|
| 3 |
(use gauche.test) |
| 4 |
|
| 5 |
(test-start "lazy evaluation") |
| 6 |
|
| 7 |
;;---------------------------------------------------------------- |
| 8 |
(test-section "lazy, delay & force") |
| 9 |
|
| 10 |
;; Note: thread-safety of force is tested in ext/threads. |
| 11 |
|
| 12 |
(test* "simple delay" 3 |
| 13 |
(force (delay (+ 1 2)))) |
| 14 |
|
| 15 |
(test* "delay w/state" 3 |
| 16 |
(let1 x 9 |
| 17 |
(let1 d (delay (/ x 3)) |
| 18 |
(force d) |
| 19 |
(set! x 99) |
| 20 |
(force d)))) |
| 21 |
|
| 22 |
(test* "delay recursive" 6 ;; R5RS 6.4 |
| 23 |
(letrec ([count 0] |
| 24 |
[x 5] |
| 25 |
[p (delay (begin (set! count (+ count 1)) |
| 26 |
(if (> count x) |
| 27 |
count |
| 28 |
(force p))))]) |
| 29 |
(force p) |
| 30 |
(set! x 10) |
| 31 |
(force p))) |
| 32 |
|
| 33 |
;; check to see the compiler does the right thing about expanding |
| 34 |
;; (delay x) to (lazy (eager x)). |
| 35 |
(test* "delay compilation" 3 |
| 36 |
(force |
| 37 |
(let ([lazy list] |
| 38 |
[eager list]) |
| 39 |
(delay (force 3))))) |
| 40 |
|
| 41 |
(let* ([count 0] |
| 42 |
[sentinel #t] |
| 43 |
[z (delay (if (= count 0) |
| 44 |
(begin (set! count 1) (raise 'foo) (set! sentinel #f)) |
| 45 |
'ok))]) |
| 46 |
(test* "delay exception handling" '(foo #t) |
| 47 |
(begin |
| 48 |
(guard (e [else #f]) (force z)) |
| 49 |
(guard (e [(eq? e 'foo) (list e sentinel)]) (force z))))) |
| 50 |
|
| 51 |
|
| 52 |
;; srfi.45 test suite |
| 53 |
(test* "memoize 1" 1 |
| 54 |
(let1 count 0 |
| 55 |
(define s (delay (begin (set! count (+ count 1)) 1))) |
| 56 |
(force s) |
| 57 |
(force s) |
| 58 |
count)) |
| 59 |
|
| 60 |
(test* "memoize 2" 1 |
| 61 |
(let1 count 0 |
| 62 |
(define s (delay (begin (set! count (+ count 1)) 1))) |
| 63 |
(+ (force s) (force s)) |
| 64 |
count)) |
| 65 |
|
| 66 |
(test* "memoize 3" 1 ;; (Alejandro Forero Cuervo) |
| 67 |
(let1 count 0 |
| 68 |
(let* ([r (delay (begin (set! count (+ count 1)) 1))] |
| 69 |
[s (lazy r)] |
| 70 |
[t (lazy s)]) |
| 71 |
(force t) |
| 72 |
(force r) |
| 73 |
count))) |
| 74 |
|
| 75 |
(test* "memoize 4" 5 ;; stream memoization |
| 76 |
(let1 count 0 |
| 77 |
(define (stream-drop s index) |
| 78 |
(lazy |
| 79 |
(if (zero? index) |
| 80 |
s |
| 81 |
(stream-drop (cdr (force s)) (- index 1))))) |
| 82 |
(define (ones) |
| 83 |
(delay (begin |
| 84 |
(set! count (+ count 1)) |
| 85 |
(cons 1 (ones))))) |
| 86 |
(let1 s (ones) |
| 87 |
(car (force (stream-drop s 4))) |
| 88 |
(car (force (stream-drop s 4))) |
| 89 |
count))) |
| 90 |
|
| 91 |
(test* "reentrancy 1" 'second ;; see srfi.40 post-discussion |
| 92 |
(let () |
| 93 |
(define f |
| 94 |
(let1 first? #t |
| 95 |
(delay |
| 96 |
(if first? |
| 97 |
(begin |
| 98 |
(set! first? #f) |
| 99 |
(force f)) |
| 100 |
'second)))) |
| 101 |
(force f))) |
| 102 |
|
| 103 |
(test* "reentrancy 2" '(5 0 10) ;; (John Shutt) |
| 104 |
(let () |
| 105 |
(define q |
| 106 |
(let1 count 5 |
| 107 |
(define (get-count) count) |
| 108 |
(define p (delay (if (<= count 0) |
| 109 |
count |
| 110 |
(begin (set! count (- count 1)) |
| 111 |
(force p) |
| 112 |
(set! count (+ count 2)) |
| 113 |
count)))) |
| 114 |
(list get-count p))) |
| 115 |
(let* ([get-count (car q)] |
| 116 |
[p (cadr q)] |
| 117 |
[a (get-count)] |
| 118 |
[b (force p)] |
| 119 |
[c (get-count)]) |
| 120 |
(list a b c)))) |
| 121 |
|
| 122 |
;; This leak test takes long time, so we exclude it by default. |
| 123 |
;; If you run this on pre-0.8.6 Gauche (with replacing lazy by delay+force), |
| 124 |
;; it'll bust the memory. |
| 125 |
'(test* "leak 1" 10000000 |
| 126 |
(let () |
| 127 |
(define (stream-filter p? s) |
| 128 |
(lazy |
| 129 |
(let1 lis (force s) |
| 130 |
(if (null? lis) |
| 131 |
(delay '()) |
| 132 |
(let ([h (car lis)] |
| 133 |
[t (cdr lis)]) |
| 134 |
(if (p? h) |
| 135 |
(delay (cons h (stream-filter p? t))) |
| 136 |
(stream-filter p? t))))))) |
| 137 |
(define (from n) |
| 138 |
(delay (cons n (from (+ n 1))))) |
| 139 |
(car (force (stream-filter (^n (= n 10000000)) |
| 140 |
(from 0)))))) |
| 141 |
|
| 142 |
(test* "multi-valued delay" '(1 2 3) |
| 143 |
(let ((z (delay (values 1 2 3)))) |
| 144 |
(values->list (force z)))) |
| 145 |
|
| 146 |
(test* "multi-valued delay" '() |
| 147 |
(let ((z (delay (values)))) |
| 148 |
(values->list (force z)))) |
| 149 |
|
| 150 |
;;---------------------------------------------------------------- |
| 151 |
(test-section "lazy pairs") |
| 152 |
|
| 153 |
;; It is easier to use gauche.generator to test lazy pairs, |
| 154 |
;; but gauche.generator test is done in ext/gauche. Here |
| 155 |
;; we roll our own generators. We also have some tests for |
| 156 |
;; thread safety of lazy pairs in ext/threads. |
| 157 |
|
| 158 |
(define (gnull) (eof-object)) |
| 159 |
|
| 160 |
(define (giota n) |
| 161 |
(let1 cnt 0 |
| 162 |
(^[] (if (< cnt n) |
| 163 |
(begin0 cnt (inc! cnt)) |
| 164 |
(eof-object))))) |
| 165 |
|
| 166 |
(define (gerr n) ;; raise an error after generating n items |
| 167 |
(let1 cnt 0 |
| 168 |
(^[] (if (< cnt n) |
| 169 |
(begin0 cnt (inc! cnt)) |
| 170 |
(error "oof"))))) |
| 171 |
|
| 172 |
(test* "pair?" #t (pair? (generator->lseq 0 gnull))) |
| 173 |
(test* "car" 0 (car (generator->lseq 0 gnull))) |
| 174 |
(test* "cdr" '() (cdr (generator->lseq 0 gnull))) |
| 175 |
|
| 176 |
(test* "lazyness" 0 (car (generator->lseq 0 (gerr 1)))) |
| 177 |
(test* "lazyness" 1 (caddr (generator->lseq 0 (gerr 3)))) |
| 178 |
(test* "lazyness" (test-error) (cadddr (generator->lseq 0 (gerr 3)))) |
| 179 |
(test* "lazyness string?" #f (string? (generator->lseq 0 (gerr 0)))) |
| 180 |
(test* "lazyness pair?" (test-error) (pair? (generator->lseq 0 (gerr 0)))) |
| 181 |
(test* "lazyness list?" (test-error) (list? (generator->lseq 0 (gerr 10)))) |
| 182 |
|
| 183 |
(test* "apply robustness" '(0) (apply list (generator->lseq 0 gnull))) |
| 184 |
(test* "apply robustness" '(0 1) (apply list 0 (generator->lseq 1 gnull))) |
| 185 |
(test* "apply robustness" (test-error) (apply list 0 (generator->lseq 1 (gerr 10)))) |
| 186 |
(test* "object-apply robustness" (test-error) ((generator->lseq 0 gnull))) |
| 187 |
|
| 188 |
(test* "eq? doesn't force lazy pair" #f (eq? '(0) (generator->lseq 0 (gerr 0)))) |
| 189 |
(test* "eqv? doesn't force lazy pair" #f (eqv? '(0) (generator->lseq 0 (gerr 0)))) |
| 190 |
(test* "forcing lazy pair doen't change the identity" #t |
| 191 |
(let* ([p0 (cons 0 (generator->lseq 0 gnull))] |
| 192 |
[p1 (cdr p0)]) |
| 193 |
(and (length p0) (eq? (cdr p0) p1)))) |
| 194 |
|
| 195 |
;; We don't recommend mutating lazy pairs, but we can't enforce it anyway, |
| 196 |
;; so we better check it won't break. |
| 197 |
(test* "lazy pair and mutation" '(1) |
| 198 |
(rlet1 p (generator->lseq 0 gnull) |
| 199 |
(set! (car p) 1))) |
| 200 |
(test* "lazy pair and mutation" '(0 . 1) |
| 201 |
(rlet1 p (generator->lseq 0 gnull) |
| 202 |
(set! (cdr p) 1))) |
| 203 |
|
| 204 |
(test* "class-of" <pair> (class-of (generator->lseq 0 (gerr 0)))) |
| 205 |
(test* "is-a?" #f (is-a? (generator->lseq 0 gnull) <null>)) |
| 206 |
(test* "is-a?" #t (is-a? (generator->lseq 0 (gerr 0)) <pair>)) |
| 207 |
|
| 208 |
;; Forcing lazy pair during builtin insturction evaluation. |
| 209 |
;; For memq & memv test, we coerce the result to boolean so that |
| 210 |
;; the result check won't force the rest of the seq. |
| 211 |
(let () |
| 212 |
(define (t nam p) |
| 213 |
(test* nam #t (boolean (p 'c (generator->lseq 'a 'b 'c gnull)))) |
| 214 |
(test* #"~nam (lazyness)" #t |
| 215 |
(boolean (p 'b (generator->lseq 'a 'b 'c (gerr 0))))) |
| 216 |
(test* nam #f (boolean (p 'z (generator->lseq 'a 'b 'c gnull))))) |
| 217 |
(t "memq" memq) |
| 218 |
(t "memv" memv)) |
| 219 |
(let () |
| 220 |
(define (t nam p) |
| 221 |
(test* nam '(c . 2) |
| 222 |
(p 'c (generator->lseq '(a . 0) '(b . 1) '(c . 2) gnull))) |
| 223 |
(test* #"~nam (lazyness)" '(b . 1) |
| 224 |
(p 'b (generator->lseq '(a . 0) '(b . 1) '(c . 2) (gerr 0)))) |
| 225 |
(test* nam #f (p 'z (generator->lseq 'a 'b 'c gnull)))) |
| 226 |
(t "assq" assq) |
| 227 |
(t "assv" assv)) |
| 228 |
(test* "reverse" '(4 3 2 1 0) (reverse (generator->lseq (giota 5)))) |
| 229 |
(test* "append" '(0 1 2 0 1 2 3 0 1 2 3 4) |
| 230 |
(append (generator->lseq (giota 3)) |
| 231 |
(generator->lseq (giota 4)) |
| 232 |
(generator->lseq (giota 5)))) |
| 233 |
(test* "APPEND instruction for quasiquoting" '(0 1 2 0 1 2 3 0 1 2 3 4) |
| 234 |
`(,@(generator->lseq (giota 3)) |
| 235 |
,@(generator->lseq (giota 4)) |
| 236 |
,@(generator->lseq (giota 5)))) |
| 237 |
(test* "APP-VEC instruction for quasiquoting" '#(0 1 2 0 1 2 3 0 1 2 3 4) |
| 238 |
`#(,@(generator->lseq (giota 3)) |
| 239 |
,@(generator->lseq (giota 4)) |
| 240 |
,@(generator->lseq (giota 5)))) |
| 241 |
(test* "CONS instruction" '(2 1 . 0) |
| 242 |
(cons 2 (cons 1 (car (generator->lseq 0 gnull))))) |
| 243 |
|
| 244 |
(test* "CAR-PUSH instruction" 1 |
| 245 |
(abs (car (lcons -1 '())))) |
| 246 |
(test* "CDR-PUSH instruction" #t |
| 247 |
(let1 x (cdr (lcons -1 '())) |
| 248 |
(null? x))) |
| 249 |
|
| 250 |
(test* "length" 10 (length (generator->lseq (giota 10)))) |
| 251 |
(test* "fold" 45 (fold + 0 (generator->lseq (giota 10)))) |
| 252 |
(test* "equal?" #t (equal? '(0 1 2 3 4) (generator->lseq (giota 5)))) |
| 253 |
|
| 254 |
(test* "liota" '(0 1 2 3 4) (liota 5)) |
| 255 |
(test* "liota" '(0.0 1.0 2.0 3.0 4.0) (liota 5 0.0)) |
| 256 |
(test* "liota" '(0 1 2 3 4) (take (liota) 5)) |
| 257 |
(test* "liota" '(1/2 7/6 11/6 5/2 19/6) (liota 5 1/2 2/3)) |
| 258 |
(test* "liota" '(1.0 0.9 0.8 0.7 0.6) (liota 5 1.0 -0.1)) |
| 259 |
|
| 260 |
(test* "lrange" '(1 2 3 4 5) (take (lrange 1) 5)) |
| 261 |
(test* "lrange" '(1 2 3 4 5) (lrange 1 6)) |
| 262 |
(test* "lrange" '(1 2 3 4 5) (lrange 1 6 1)) |
| 263 |
(test* "lrange" '(1 3 5) (lrange 1 6 2)) |
| 264 |
(test* "lrange" '() (lrange 6 1)) |
| 265 |
(test* "lrange" '(6 5 4 3 2) (lrange 6 1 -1)) |
| 266 |
(test* "lrange" '(6 4 2) (lrange 6 1 -2)) |
| 267 |
(test* "lrange" '(6 4 2) (lrange 6 0 -2)) |
| 268 |
(test* "lrange" '() (lrange 1 6 -1)) |
| 269 |
(test* "lrange" '(1 1 1 1) (take (lrange 1 5 0) 4)) |
| 270 |
(test* "lrange" '(5 5 5 5) (take (lrange 5 1 0) 4)) |
| 271 |
(test* "lrange" '(1 13/7 19/7 25/7 31/7 37/7) (lrange 1 6 6/7)) |
| 272 |
(test* "lrange" '(1.0 1.5 2.0 2.5) (lrange 1 3 0.5)) |
| 273 |
(test* "lrange" '(3.0 2.5 2.0 1.5) (lrange 3 1 -0.5)) |
| 274 |
|
| 275 |
;; Interference with partial continuations |
| 276 |
(use gauche.partcont) |
| 277 |
(let () |
| 278 |
(define (inv lis) |
| 279 |
(define (kk) |
| 280 |
(reset (for-each (^e (shift k (set! kk k) e)) lis) |
| 281 |
(set! kk (^[] (eof-object))) |
| 282 |
(eof-object))) |
| 283 |
(^[] (kk))) |
| 284 |
(define (mux g0 g1) |
| 285 |
(define flag #t) |
| 286 |
(^[] (begin0 (if flag (g0) (g1)) |
| 287 |
(set! flag (not flag))))) |
| 288 |
(define (make-seq) |
| 289 |
(generator->lseq 0 (mux (inv '(a b c d e)) (inv '(1 2 3 4 5))))) |
| 290 |
(test* "interference with partcont" '(z 0 a 1 b 2 c 3 d 4 e 5) |
| 291 |
(cons 'z (make-seq))) |
| 292 |
) |
| 293 |
|
| 294 |
;; lcons |
| 295 |
(let () |
| 296 |
(define (take xs n) ; avoid depending SRFI-1 |
| 297 |
(if (= n 0) |
| 298 |
'() |
| 299 |
(cons (car xs) (take (cdr xs) (- n 1))))) |
| 300 |
(define (fib a b) |
| 301 |
(let1 n (+ a b) |
| 302 |
(lcons n (fib b n)))) |
| 303 |
(define (weird-fib a b) ; generates ordinary pairs as well |
| 304 |
(let1 n (+ a b) |
| 305 |
(if (odd? n) |
| 306 |
(lcons n (weird-fib b n)) |
| 307 |
(cons n (weird-fib b n))))) |
| 308 |
(define (lim-fib a b k) |
| 309 |
(if (= k 0) |
| 310 |
'yay ;returning any non-pair terminates the sequence |
| 311 |
(let1 n (+ a b) |
| 312 |
(lcons n (lim-fib b n (- k 1)))))) |
| 313 |
|
| 314 |
(test* "corecursion with lcons" |
| 315 |
'(1 2 3 5 8 13 21 34 55 89 144 233 377 610 987) |
| 316 |
(take (fib 0 1) 15)) |
| 317 |
|
| 318 |
(test* "corecursion with lcons, mixed" |
| 319 |
'(1 2 3 5 8 13 21 34 55 89 144 233 377 610 987) |
| 320 |
(take (weird-fib 0 1) 15)) |
| 321 |
|
| 322 |
;; NB: we may make this an error in the future versions. |
| 323 |
(test* "corecursion doesn't allow dotted list" |
| 324 |
'(1 2 3 5 8 13 21 34 55 89) |
| 325 |
(lim-fib 0 1 10)) |
| 326 |
|
| 327 |
;; See Scm_ForceLazyPair(); internally used second return value from |
| 328 |
;; the generator shouldn't be leaked out. |
| 329 |
(test* "make sure internal stuff won't leak out" '(3) |
| 330 |
(receive x (list-ref (fib 0 1) 2) x)) |
| 331 |
) |
| 332 |
|
| 333 |
;; preventing recursive forcing |
| 334 |
(let () |
| 335 |
(define (lmap+ fn a b) ; we haven't tested gauche.lazy, so roll our own. |
| 336 |
(lcons (fn (car a) (car b)) |
| 337 |
(lmap+ fn (cdr a) (cdr b)))) |
| 338 |
(define fib-bad (cons 1 (lcons 1 (lmap+ + fib-bad (cdr fib-bad))))) |
| 339 |
|
| 340 |
(test* "catch recursive forcing a lazy-pair" #t |
| 341 |
(guard (e [(#/Attempt to recursively force a lazy pair/ (~ e'message)) |
| 342 |
=> boolean] |
| 343 |
[else e]) |
| 344 |
(cadr fib-bad))) |
| 345 |
) |
| 346 |
|
| 347 |
(test* "lcons*" 1 (car (lcons* 1 2 (error "ouch")))) |
| 348 |
(test* "lcons*" *test-error* (cadr (lcons* 1 2 (error "ouch")))) |
| 349 |
|
| 350 |
;; See if a lazy pair becomes an extended pair |
| 351 |
(test* "lazy pair -> extended pair" '((ping . pong)) |
| 352 |
(let1 z (lcons 'a '()) |
| 353 |
(pair-attribute-set! z 'ping 'pong) |
| 354 |
(pair-attributes z))) |
| 355 |
(test* "lazy pair -> extended pair (attrs)" |
| 356 |
'((1 (count . 1)) |
| 357 |
(2 (count . 2)) |
| 358 |
(3 (count . 3)) |
| 359 |
(4 (count . 4)) |
| 360 |
(5 (count . 5))) |
| 361 |
(let* ([count 0] |
| 362 |
[z (generator->lseq (^[] |
| 363 |
(inc! count) |
| 364 |
(values count `((count . ,count)))))]) |
| 365 |
(map cons |
| 366 |
(take z 5) |
| 367 |
(map (^i (pair-attributes (drop z i))) (iota 5))))) |
| 368 |
(test* "lazy pair -> extended pair (robustness against invalid attrs 1)" |
| 369 |
'() |
| 370 |
(let1 z (generator->lseq (^[] (values 1 'a))) |
| 371 |
(pair-attributes z))) |
| 372 |
(test* "lazy pair -> extended pair (robustness against invalid attrs 2)" |
| 373 |
'((a . b) (d . e)) |
| 374 |
(let1 z (generator->lseq (^[] (values 1 '((a . b) c (d . e) . f)))) |
| 375 |
(pair-attributes z))) |
| 376 |
|
| 377 |
(test* "lazy pair -> extended pair (using lcons)" |
| 378 |
'((0 (x . 0)) |
| 379 |
(1 (x . 2)) |
| 380 |
(2 (x . 4)) |
| 381 |
(3 (x . 6)) |
| 382 |
(4 (x . 8))) |
| 383 |
(let1 z (let loop ((n 0)) |
| 384 |
(lcons n (loop (+ n 1)) `((x . ,(* n 2))))) |
| 385 |
(map cons |
| 386 |
(take z 5) |
| 387 |
(map (^i (pair-attributes (drop z i))) (iota 5))))) |
| 388 |
|
| 389 |
(test-end) |