Debian Codegraph @

test/lazy.scm

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