Merge lp:~rotty/scheme-libraries/srfi into lp:~scheme-libraries-team/scheme-libraries/srfi
- srfi
- Merge into srfi
Proposed by
Andreas Rottmann
Status: | Merged |
---|---|
Approved by: | Derick Eddington |
Approved revision: | 94 |
Merged at revision: | 94 |
Proposed branch: | lp:~rotty/scheme-libraries/srfi |
Merge into: | lp:~scheme-libraries-team/scheme-libraries/srfi |
Diff against target: |
386 lines (+337/-1) 6 files modified
%3a45.sls (+10/-0) %3a45/lazy.sls (+71/-0) README (+1/-0) compile-all.ikarus.sps (+2/-0) private/registry.sls (+1/-1) tests/lazy.sps (+252/-0) |
To merge this branch: | bzr merge lp:~rotty/scheme-libraries/srfi |
Related bugs: |
Reviewer | Review Type | Date Requested | Status |
---|---|---|---|
Derick Eddington | Approve | ||
Review via email: mp+25709@code.launchpad.net |
Commit message
Description of the change
Added SRFI 45 (Primitives for Expressing Iterative Lazy Algorithms)
I think I've now addressed all the issues pointed out by Derick in my first attempt.
To post a comment you must log in.
Preview Diff
[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1 | === added directory '%3a45' | |||
2 | === added file '%3a45.sls' | |||
3 | --- %3a45.sls 1970-01-01 00:00:00 +0000 | |||
4 | +++ %3a45.sls 2010-05-20 18:00:56 +0000 | |||
5 | @@ -0,0 +1,10 @@ | |||
6 | 1 | #!r6rs | ||
7 | 2 | ;; Automatically generated by private/make-aliased-libraries.sps | ||
8 | 3 | (library (srfi :45) | ||
9 | 4 | (export | ||
10 | 5 | delay | ||
11 | 6 | eager | ||
12 | 7 | force | ||
13 | 8 | lazy) | ||
14 | 9 | (import (srfi :45 lazy)) | ||
15 | 10 | ) | ||
16 | 0 | 11 | ||
17 | === added file '%3a45/lazy.sls' | |||
18 | --- %3a45/lazy.sls 1970-01-01 00:00:00 +0000 | |||
19 | +++ %3a45/lazy.sls 2010-05-20 18:00:56 +0000 | |||
20 | @@ -0,0 +1,71 @@ | |||
21 | 1 | #!r6rs | ||
22 | 2 | ;; lazy.sls -- SRFI 45 (Primitives for Expressing Iterative Lazy Algorithms) | ||
23 | 3 | |||
24 | 4 | ;; Copyright (C) André van Tonder (2003). All Rights Reserved. | ||
25 | 5 | |||
26 | 6 | ;; Permission is hereby granted, free of charge, to any person | ||
27 | 7 | ;; obtaining a copy of this software and associated documentation | ||
28 | 8 | ;; files (the "Software"), to deal in the Software without | ||
29 | 9 | ;; restriction, including without limitation the rights to use, copy, | ||
30 | 10 | ;; modify, merge, publish, distribute, sublicense, and/or sell copies | ||
31 | 11 | ;; of the Software, and to permit persons to whom the Software is | ||
32 | 12 | ;; furnished to do so, subject to the following conditions: | ||
33 | 13 | |||
34 | 14 | ;; The above copyright notice and this permission notice shall be | ||
35 | 15 | ;; included in all copies or substantial portions of the Software. | ||
36 | 16 | |||
37 | 17 | ;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | ||
38 | 18 | ;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | ||
39 | 19 | ;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND | ||
40 | 20 | ;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS | ||
41 | 21 | ;; BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN | ||
42 | 22 | ;; ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | ||
43 | 23 | ;; CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | ||
44 | 24 | ;; SOFTWARE. | ||
45 | 25 | |||
46 | 26 | (library (srfi :45 lazy) | ||
47 | 27 | (export delay | ||
48 | 28 | lazy | ||
49 | 29 | force | ||
50 | 30 | eager) | ||
51 | 31 | (import (rnrs base) | ||
52 | 32 | (rnrs records syntactic)) | ||
53 | 33 | |||
54 | 34 | (define-record-type promise | ||
55 | 35 | (fields (mutable val))) | ||
56 | 36 | |||
57 | 37 | (define-record-type value | ||
58 | 38 | (fields (mutable tag) | ||
59 | 39 | (mutable proc))) | ||
60 | 40 | |||
61 | 41 | (define-syntax lazy | ||
62 | 42 | (syntax-rules () | ||
63 | 43 | ((lazy exp) | ||
64 | 44 | (make-promise (make-value 'lazy (lambda () exp)))))) | ||
65 | 45 | |||
66 | 46 | (define (eager x) | ||
67 | 47 | (make-promise (make-value 'eager x))) | ||
68 | 48 | |||
69 | 49 | (define-syntax delay | ||
70 | 50 | (syntax-rules () | ||
71 | 51 | ((delay exp) (lazy (eager exp))))) | ||
72 | 52 | |||
73 | 53 | (define (force promise) | ||
74 | 54 | (let ((content (promise-val promise))) | ||
75 | 55 | (case (value-tag content) | ||
76 | 56 | ((eager) (value-proc content)) | ||
77 | 57 | ((lazy) (let* ((promise* ((value-proc content))) | ||
78 | 58 | (content (promise-val promise))) ; * | ||
79 | 59 | (if (not (eqv? (value-tag content) 'eager)) ; * | ||
80 | 60 | (begin (value-tag-set! content | ||
81 | 61 | (value-tag (promise-val promise*))) | ||
82 | 62 | (value-proc-set! content | ||
83 | 63 | (value-proc (promise-val promise*))) | ||
84 | 64 | (promise-val-set! promise* content))) | ||
85 | 65 | (force promise)))))) | ||
86 | 66 | |||
87 | 67 | ;; (*) These two lines re-fetch and check the original promise in case | ||
88 | 68 | ;; the first line of the let* caused it to be forced. For an example | ||
89 | 69 | ;; where this happens, see reentrancy test 3 below. | ||
90 | 70 | |||
91 | 71 | ) | ||
92 | 0 | 72 | ||
93 | === modified file 'README' | |||
94 | --- README 2010-03-05 08:11:29 +0000 | |||
95 | +++ README 2010-05-20 18:00:56 +0000 | |||
96 | @@ -32,6 +32,7 @@ | |||
97 | 32 | (srfi :41 streams) | 32 | (srfi :41 streams) |
98 | 33 | (srfi :42 eager-comprehensions) | 33 | (srfi :42 eager-comprehensions) |
99 | 34 | (srfi :43 vectors) | 34 | (srfi :43 vectors) |
100 | 35 | (srfi :45 lazy) | ||
101 | 35 | (srfi :48 intermediate-format-strings) | 36 | (srfi :48 intermediate-format-strings) |
102 | 36 | (srfi :61 cond) | 37 | (srfi :61 cond) |
103 | 37 | (srfi :64 testing) | 38 | (srfi :64 testing) |
104 | 38 | 39 | ||
105 | === modified file 'compile-all.ikarus.sps' | |||
106 | --- compile-all.ikarus.sps 2010-03-05 08:11:29 +0000 | |||
107 | +++ compile-all.ikarus.sps 2010-05-20 18:00:56 +0000 | |||
108 | @@ -47,6 +47,8 @@ | |||
109 | 47 | (only (srfi :42 eager-comprehensions)) | 47 | (only (srfi :42 eager-comprehensions)) |
110 | 48 | (only (srfi :43)) | 48 | (only (srfi :43)) |
111 | 49 | (only (srfi :43 vectors)) | 49 | (only (srfi :43 vectors)) |
112 | 50 | (only (srfi :45)) | ||
113 | 51 | (only (srfi :43 lazy)) | ||
114 | 50 | (only (srfi :48)) | 52 | (only (srfi :48)) |
115 | 51 | (only (srfi :48 intermediate-format-strings)) | 53 | (only (srfi :48 intermediate-format-strings)) |
116 | 52 | (only (srfi :48 intermediate-format-strings compat)) | 54 | (only (srfi :48 intermediate-format-strings compat)) |
117 | 53 | 55 | ||
118 | === modified file 'private/registry.sls' | |||
119 | --- private/registry.sls 2010-03-05 08:11:29 +0000 | |||
120 | +++ private/registry.sls 2010-05-20 18:00:56 +0000 | |||
121 | @@ -44,7 +44,7 @@ | |||
122 | 44 | (42 eager-comprehensions) | 44 | (42 eager-comprehensions) |
123 | 45 | (43 vectors) | 45 | (43 vectors) |
124 | 46 | #;(44 collections) | 46 | #;(44 collections) |
126 | 47 | #;(45 lazy) | 47 | (45 lazy) |
127 | 48 | #;(46 syntax-rules) | 48 | #;(46 syntax-rules) |
128 | 49 | #;(47 arrays) | 49 | #;(47 arrays) |
129 | 50 | (48 intermediate-format-strings) | 50 | (48 intermediate-format-strings) |
130 | 51 | 51 | ||
131 | === added file 'tests/lazy.sps' | |||
132 | --- tests/lazy.sps 1970-01-01 00:00:00 +0000 | |||
133 | +++ tests/lazy.sps 2010-05-20 18:00:56 +0000 | |||
134 | @@ -0,0 +1,252 @@ | |||
135 | 1 | #!r6rs | ||
136 | 2 | ;; Copyright (C) André van Tonder (2003, 2010). All Rights Reserved. | ||
137 | 3 | |||
138 | 4 | ;; Permission is hereby granted, free of charge, to any person | ||
139 | 5 | ;; obtaining a copy of this software and associated documentation | ||
140 | 6 | ;; files (the "Software"), to deal in the Software without | ||
141 | 7 | ;; restriction, including without limitation the rights to use, copy, | ||
142 | 8 | ;; modify, merge, publish, distribute, sublicense, and/or sell copies | ||
143 | 9 | ;; of the Software, and to permit persons to whom the Software is | ||
144 | 10 | ;; furnished to do so, subject to the following conditions: | ||
145 | 11 | |||
146 | 12 | ;; The above copyright notice and this permission notice shall be | ||
147 | 13 | ;; included in all copies or substantial portions of the Software. | ||
148 | 14 | |||
149 | 15 | ;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | ||
150 | 16 | ;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | ||
151 | 17 | ;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND | ||
152 | 18 | ;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS | ||
153 | 19 | ;; BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN | ||
154 | 20 | ;; ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | ||
155 | 21 | ;; CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | ||
156 | 22 | ;; SOFTWARE. | ||
157 | 23 | |||
158 | 24 | ;========================================================================= | ||
159 | 25 | ; TESTS AND BENCHMARKS: | ||
160 | 26 | ;========================================================================= | ||
161 | 27 | |||
162 | 28 | (import (rnrs) | ||
163 | 29 | (only (rnrs r5rs) modulo) | ||
164 | 30 | (srfi :64 testing) | ||
165 | 31 | (srfi :45 lazy)) | ||
166 | 32 | |||
167 | 33 | (define-syntax test-output | ||
168 | 34 | (syntax-rules () | ||
169 | 35 | ((_ expected proc) | ||
170 | 36 | (test-equal expected | ||
171 | 37 | (call-with-string-output-port proc))))) | ||
172 | 38 | |||
173 | 39 | (define (test-leak thunk) | ||
174 | 40 | (display | ||
175 | 41 | "Leak test, please watch memory consumption; press C-c when satisfied\n") | ||
176 | 42 | (guard (c (#t 'aborted)) | ||
177 | 43 | (thunk))) | ||
178 | 44 | |||
179 | 45 | (test-begin "lazy-tests") | ||
180 | 46 | |||
181 | 47 | ;========================================================================= | ||
182 | 48 | ; Memoization test 1: | ||
183 | 49 | |||
184 | 50 | (test-output "hello" | ||
185 | 51 | (lambda (port) | ||
186 | 52 | (define s (delay (begin (display 'hello port) 1))) | ||
187 | 53 | (test-equal 1 (force s)) | ||
188 | 54 | (force s))) | ||
189 | 55 | |||
190 | 56 | ;========================================================================= | ||
191 | 57 | ; Memoization test 2: | ||
192 | 58 | |||
193 | 59 | (test-output "bonjour" | ||
194 | 60 | (lambda (port) | ||
195 | 61 | (let ((s (delay (begin (display 'bonjour port) 2)))) | ||
196 | 62 | (test-equal 4 (+ (force s) (force s)))))) | ||
197 | 63 | |||
198 | 64 | ;========================================================================= | ||
199 | 65 | ; Memoization test 3: (pointed out by Alejandro Forero Cuervo) | ||
200 | 66 | |||
201 | 67 | (test-output "hi" | ||
202 | 68 | (lambda (port) | ||
203 | 69 | (define r (delay (begin (display 'hi port) 1))) | ||
204 | 70 | (define s (lazy r)) | ||
205 | 71 | (define t (lazy s)) | ||
206 | 72 | (test-equal 1 (force t)) | ||
207 | 73 | (test-equal 1 (force r)))) | ||
208 | 74 | |||
209 | 75 | ;========================================================================= | ||
210 | 76 | ; Memoization test 4: Stream memoization | ||
211 | 77 | |||
212 | 78 | (define (stream-drop s index) | ||
213 | 79 | (lazy | ||
214 | 80 | (if (zero? index) | ||
215 | 81 | s | ||
216 | 82 | (stream-drop (cdr (force s)) (- index 1))))) | ||
217 | 83 | |||
218 | 84 | (define (ones port) | ||
219 | 85 | (delay (begin | ||
220 | 86 | (display 'ho port) | ||
221 | 87 | (cons 1 (ones port))))) | ||
222 | 88 | |||
223 | 89 | (test-output "hohohohoho" | ||
224 | 90 | (lambda (port) | ||
225 | 91 | (define s (ones port)) | ||
226 | 92 | (test-equal 1 | ||
227 | 93 | (car (force (stream-drop s 4)))) | ||
228 | 94 | (test-equal 1 | ||
229 | 95 | (car (force (stream-drop s 4)))))) | ||
230 | 96 | |||
231 | 97 | ;========================================================================= | ||
232 | 98 | ; Reentrancy test 1: from R5RS | ||
233 | 99 | |||
234 | 100 | (letrec ((count 0) | ||
235 | 101 | (p (delay (begin (set! count (+ count 1)) | ||
236 | 102 | (if (> count x) | ||
237 | 103 | count | ||
238 | 104 | (force p))))) | ||
239 | 105 | (x 5)) | ||
240 | 106 | (test-equal 6 (force p)) | ||
241 | 107 | (set! x 10) | ||
242 | 108 | (test-equal 6 (force p))) | ||
243 | 109 | |||
244 | 110 | ;========================================================================= | ||
245 | 111 | ; Reentrancy test 2: from SRFI 40 | ||
246 | 112 | |||
247 | 113 | (letrec ((f (let ((first? #t)) | ||
248 | 114 | (delay | ||
249 | 115 | (if first? | ||
250 | 116 | (begin | ||
251 | 117 | (set! first? #f) | ||
252 | 118 | (force f)) | ||
253 | 119 | 'second))))) | ||
254 | 120 | (test-equal 'second (force f))) | ||
255 | 121 | |||
256 | 122 | ;========================================================================= | ||
257 | 123 | ; Reentrancy test 3: due to John Shutt | ||
258 | 124 | |||
259 | 125 | (let* ((q (let ((count 5)) | ||
260 | 126 | (define (get-count) count) | ||
261 | 127 | (define p (delay (if (<= count 0) | ||
262 | 128 | count | ||
263 | 129 | (begin (set! count (- count 1)) | ||
264 | 130 | (force p) | ||
265 | 131 | (set! count (+ count 2)) | ||
266 | 132 | count)))) | ||
267 | 133 | (list get-count p))) | ||
268 | 134 | (get-count (car q)) | ||
269 | 135 | (p (cadr q))) | ||
270 | 136 | |||
271 | 137 | (test-equal 5 (get-count)) | ||
272 | 138 | (test-equal 0 (force p)) | ||
273 | 139 | (test-equal 10 (get-count))) | ||
274 | 140 | |||
275 | 141 | ;========================================================================= | ||
276 | 142 | ; Test leaks: All the leak tests should run in bounded space. | ||
277 | 143 | |||
278 | 144 | ;========================================================================= | ||
279 | 145 | ; Leak test 1: Infinite loop in bounded space. | ||
280 | 146 | |||
281 | 147 | (define (loop) (lazy (loop))) | ||
282 | 148 | (test-leak (lambda () (force (loop)))) ;==> bounded space | ||
283 | 149 | |||
284 | 150 | ;========================================================================= | ||
285 | 151 | ; Leak test 2: Pending memos should not accumulate | ||
286 | 152 | ; in shared structures. | ||
287 | 153 | |||
288 | 154 | (let () | ||
289 | 155 | (define s (loop)) | ||
290 | 156 | (test-leak (lambda () (force s)))) ;==> bounded space | ||
291 | 157 | |||
292 | 158 | ;========================================================================= | ||
293 | 159 | ; Leak test 3: Safely traversing infinite stream. | ||
294 | 160 | |||
295 | 161 | (define (from n) | ||
296 | 162 | (delay (cons n (from (+ n 1))))) | ||
297 | 163 | |||
298 | 164 | (define (traverse s) | ||
299 | 165 | (lazy (traverse (cdr (force s))))) | ||
300 | 166 | |||
301 | 167 | (test-leak (lambda () (force (traverse (from 0))))) ;==> bounded space | ||
302 | 168 | |||
303 | 169 | ;========================================================================= | ||
304 | 170 | ; Leak test 4: Safely traversing infinite stream | ||
305 | 171 | ; while pointer to head of result exists. | ||
306 | 172 | |||
307 | 173 | (let () | ||
308 | 174 | (define s (traverse (from 0))) | ||
309 | 175 | (test-leak (lambda () (force s)))) ;==> bounded space | ||
310 | 176 | |||
311 | 177 | ;========================================================================= | ||
312 | 178 | ; Convenient list deconstructor used below. | ||
313 | 179 | |||
314 | 180 | (define-syntax match | ||
315 | 181 | (syntax-rules () | ||
316 | 182 | ((match exp | ||
317 | 183 | (() exp1) | ||
318 | 184 | ((h . t) exp2)) | ||
319 | 185 | (let ((lst exp)) | ||
320 | 186 | (cond ((null? lst) exp1) | ||
321 | 187 | ((pair? lst) (let ((h (car lst)) | ||
322 | 188 | (t (cdr lst))) | ||
323 | 189 | exp2)) | ||
324 | 190 | (else 'match-error)))))) | ||
325 | 191 | |||
326 | 192 | ;======================================================================== | ||
327 | 193 | ; Leak test 5: Naive stream-filter should run in bounded space. | ||
328 | 194 | ; Simplest case. | ||
329 | 195 | |||
330 | 196 | (define (stream-filter p? s) | ||
331 | 197 | (lazy (match (force s) | ||
332 | 198 | (() (delay '())) | ||
333 | 199 | ((h . t) (if (p? h) | ||
334 | 200 | (delay (cons h (stream-filter p? t))) | ||
335 | 201 | (stream-filter p? t)))))) | ||
336 | 202 | |||
337 | 203 | (test-leak | ||
338 | 204 | (lambda () | ||
339 | 205 | (force (stream-filter (lambda (n) (= n 10000000000)) | ||
340 | 206 | (from 0))))) | ||
341 | 207 | ;==> bounded space | ||
342 | 208 | |||
343 | 209 | ;======================================================================== | ||
344 | 210 | ; Leak test 6: Another long traversal should run in bounded space. | ||
345 | 211 | |||
346 | 212 | ; The stream-ref procedure below does not strictly need to be lazy. | ||
347 | 213 | ; It is defined lazy for the purpose of testing safe compostion of | ||
348 | 214 | ; lazy procedures in the times3 benchmark below (previous | ||
349 | 215 | ; candidate solutions had failed this). | ||
350 | 216 | |||
351 | 217 | (define (stream-ref s index) | ||
352 | 218 | (lazy | ||
353 | 219 | (match (force s) | ||
354 | 220 | (() 'error) | ||
355 | 221 | ((h . t) (if (zero? index) | ||
356 | 222 | (delay h) | ||
357 | 223 | (stream-ref t (- index 1))))))) | ||
358 | 224 | |||
359 | 225 | ; Check that evenness is correctly implemented - should terminate: | ||
360 | 226 | |||
361 | 227 | (test-equal 0 | ||
362 | 228 | (force (stream-ref (stream-filter zero? (from 0)) | ||
363 | 229 | 0))) | ||
364 | 230 | |||
365 | 231 | (let () | ||
366 | 232 | (define s (stream-ref (from 0) 100000000)) | ||
367 | 233 | (test-leak (lambda () (force s)))) ;==> bounded space | ||
368 | 234 | |||
369 | 235 | ;====================================================================== | ||
370 | 236 | ; Leak test 7: Infamous example from SRFI 40. | ||
371 | 237 | |||
372 | 238 | (define (times3 n) | ||
373 | 239 | (stream-ref (stream-filter | ||
374 | 240 | (lambda (x) (zero? (modulo x n))) | ||
375 | 241 | (from 0)) | ||
376 | 242 | 3)) | ||
377 | 243 | |||
378 | 244 | (force (times3 7)) | ||
379 | 245 | (test-leak (lambda () | ||
380 | 246 | (force (times3 100000000)))) ;==> bounded space | ||
381 | 247 | |||
382 | 248 | (test-end "lazy-tests") | ||
383 | 249 | |||
384 | 250 | ;; Local Variables: | ||
385 | 251 | ;; scheme-indent-styles: ((test-output 1) (test-equal 1)) | ||
386 | 252 | ;; End: |
Thanks!