Merge lp:~rotty/scheme-libraries/srfi into lp:~scheme-libraries-team/scheme-libraries/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
Reviewer Review Type Date Requested Status
Derick Eddington Approve
Review via email: mp+25709@code.launchpad.net

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.
Revision history for this message
Derick Eddington (derick-eddington) wrote :

Thanks!

review: Approve

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
=== added directory '%3a45'
=== added file '%3a45.sls'
--- %3a45.sls 1970-01-01 00:00:00 +0000
+++ %3a45.sls 2010-05-20 18:00:56 +0000
@@ -0,0 +1,10 @@
1#!r6rs
2;; Automatically generated by private/make-aliased-libraries.sps
3(library (srfi :45)
4 (export
5 delay
6 eager
7 force
8 lazy)
9 (import (srfi :45 lazy))
10)
011
=== added file '%3a45/lazy.sls'
--- %3a45/lazy.sls 1970-01-01 00:00:00 +0000
+++ %3a45/lazy.sls 2010-05-20 18:00:56 +0000
@@ -0,0 +1,71 @@
1#!r6rs
2;; lazy.sls -- SRFI 45 (Primitives for Expressing Iterative Lazy Algorithms)
3
4;; Copyright (C) André van Tonder (2003). All Rights Reserved.
5
6;; Permission is hereby granted, free of charge, to any person
7;; obtaining a copy of this software and associated documentation
8;; files (the "Software"), to deal in the Software without
9;; restriction, including without limitation the rights to use, copy,
10;; modify, merge, publish, distribute, sublicense, and/or sell copies
11;; of the Software, and to permit persons to whom the Software is
12;; furnished to do so, subject to the following conditions:
13
14;; The above copyright notice and this permission notice shall be
15;; included in all copies or substantial portions of the Software.
16
17;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
21;; BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
22;; ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
23;; CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24;; SOFTWARE.
25
26(library (srfi :45 lazy)
27 (export delay
28 lazy
29 force
30 eager)
31 (import (rnrs base)
32 (rnrs records syntactic))
33
34 (define-record-type promise
35 (fields (mutable val)))
36
37 (define-record-type value
38 (fields (mutable tag)
39 (mutable proc)))
40
41 (define-syntax lazy
42 (syntax-rules ()
43 ((lazy exp)
44 (make-promise (make-value 'lazy (lambda () exp))))))
45
46 (define (eager x)
47 (make-promise (make-value 'eager x)))
48
49 (define-syntax delay
50 (syntax-rules ()
51 ((delay exp) (lazy (eager exp)))))
52
53 (define (force promise)
54 (let ((content (promise-val promise)))
55 (case (value-tag content)
56 ((eager) (value-proc content))
57 ((lazy) (let* ((promise* ((value-proc content)))
58 (content (promise-val promise))) ; *
59 (if (not (eqv? (value-tag content) 'eager)) ; *
60 (begin (value-tag-set! content
61 (value-tag (promise-val promise*)))
62 (value-proc-set! content
63 (value-proc (promise-val promise*)))
64 (promise-val-set! promise* content)))
65 (force promise))))))
66
67 ;; (*) These two lines re-fetch and check the original promise in case
68 ;; the first line of the let* caused it to be forced. For an example
69 ;; where this happens, see reentrancy test 3 below.
70
71 )
072
=== modified file 'README'
--- README 2010-03-05 08:11:29 +0000
+++ README 2010-05-20 18:00:56 +0000
@@ -32,6 +32,7 @@
32 (srfi :41 streams)32 (srfi :41 streams)
33 (srfi :42 eager-comprehensions)33 (srfi :42 eager-comprehensions)
34 (srfi :43 vectors)34 (srfi :43 vectors)
35 (srfi :45 lazy)
35 (srfi :48 intermediate-format-strings)36 (srfi :48 intermediate-format-strings)
36 (srfi :61 cond)37 (srfi :61 cond)
37 (srfi :64 testing)38 (srfi :64 testing)
3839
=== modified file 'compile-all.ikarus.sps'
--- compile-all.ikarus.sps 2010-03-05 08:11:29 +0000
+++ compile-all.ikarus.sps 2010-05-20 18:00:56 +0000
@@ -47,6 +47,8 @@
47 (only (srfi :42 eager-comprehensions))47 (only (srfi :42 eager-comprehensions))
48 (only (srfi :43))48 (only (srfi :43))
49 (only (srfi :43 vectors))49 (only (srfi :43 vectors))
50 (only (srfi :45))
51 (only (srfi :43 lazy))
50 (only (srfi :48))52 (only (srfi :48))
51 (only (srfi :48 intermediate-format-strings))53 (only (srfi :48 intermediate-format-strings))
52 (only (srfi :48 intermediate-format-strings compat))54 (only (srfi :48 intermediate-format-strings compat))
5355
=== modified file 'private/registry.sls'
--- private/registry.sls 2010-03-05 08:11:29 +0000
+++ private/registry.sls 2010-05-20 18:00:56 +0000
@@ -44,7 +44,7 @@
44 (42 eager-comprehensions)44 (42 eager-comprehensions)
45 (43 vectors)45 (43 vectors)
46 #;(44 collections)46 #;(44 collections)
47 #;(45 lazy)47 (45 lazy)
48 #;(46 syntax-rules)48 #;(46 syntax-rules)
49 #;(47 arrays)49 #;(47 arrays)
50 (48 intermediate-format-strings)50 (48 intermediate-format-strings)
5151
=== added file 'tests/lazy.sps'
--- tests/lazy.sps 1970-01-01 00:00:00 +0000
+++ tests/lazy.sps 2010-05-20 18:00:56 +0000
@@ -0,0 +1,252 @@
1#!r6rs
2;; Copyright (C) André van Tonder (2003, 2010). All Rights Reserved.
3
4;; Permission is hereby granted, free of charge, to any person
5;; obtaining a copy of this software and associated documentation
6;; files (the "Software"), to deal in the Software without
7;; restriction, including without limitation the rights to use, copy,
8;; modify, merge, publish, distribute, sublicense, and/or sell copies
9;; of the Software, and to permit persons to whom the Software is
10;; furnished to do so, subject to the following conditions:
11
12;; The above copyright notice and this permission notice shall be
13;; included in all copies or substantial portions of the Software.
14
15;; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16;; EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17;; MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18;; NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19;; BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20;; ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21;; CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22;; SOFTWARE.
23
24;=========================================================================
25; TESTS AND BENCHMARKS:
26;=========================================================================
27
28(import (rnrs)
29 (only (rnrs r5rs) modulo)
30 (srfi :64 testing)
31 (srfi :45 lazy))
32
33(define-syntax test-output
34 (syntax-rules ()
35 ((_ expected proc)
36 (test-equal expected
37 (call-with-string-output-port proc)))))
38
39(define (test-leak thunk)
40 (display
41 "Leak test, please watch memory consumption; press C-c when satisfied\n")
42 (guard (c (#t 'aborted))
43 (thunk)))
44
45(test-begin "lazy-tests")
46
47;=========================================================================
48; Memoization test 1:
49
50(test-output "hello"
51 (lambda (port)
52 (define s (delay (begin (display 'hello port) 1)))
53 (test-equal 1 (force s))
54 (force s)))
55
56;=========================================================================
57; Memoization test 2:
58
59(test-output "bonjour"
60 (lambda (port)
61 (let ((s (delay (begin (display 'bonjour port) 2))))
62 (test-equal 4 (+ (force s) (force s))))))
63
64;=========================================================================
65; Memoization test 3: (pointed out by Alejandro Forero Cuervo)
66
67(test-output "hi"
68 (lambda (port)
69 (define r (delay (begin (display 'hi port) 1)))
70 (define s (lazy r))
71 (define t (lazy s))
72 (test-equal 1 (force t))
73 (test-equal 1 (force r))))
74
75;=========================================================================
76; Memoization test 4: Stream memoization
77
78(define (stream-drop s index)
79 (lazy
80 (if (zero? index)
81 s
82 (stream-drop (cdr (force s)) (- index 1)))))
83
84(define (ones port)
85 (delay (begin
86 (display 'ho port)
87 (cons 1 (ones port)))))
88
89(test-output "hohohohoho"
90 (lambda (port)
91 (define s (ones port))
92 (test-equal 1
93 (car (force (stream-drop s 4))))
94 (test-equal 1
95 (car (force (stream-drop s 4))))))
96
97;=========================================================================
98; Reentrancy test 1: from R5RS
99
100(letrec ((count 0)
101 (p (delay (begin (set! count (+ count 1))
102 (if (> count x)
103 count
104 (force p)))))
105 (x 5))
106 (test-equal 6 (force p))
107 (set! x 10)
108 (test-equal 6 (force p)))
109
110;=========================================================================
111; Reentrancy test 2: from SRFI 40
112
113(letrec ((f (let ((first? #t))
114 (delay
115 (if first?
116 (begin
117 (set! first? #f)
118 (force f))
119 'second)))))
120 (test-equal 'second (force f)))
121
122;=========================================================================
123; Reentrancy test 3: due to John Shutt
124
125(let* ((q (let ((count 5))
126 (define (get-count) count)
127 (define p (delay (if (<= count 0)
128 count
129 (begin (set! count (- count 1))
130 (force p)
131 (set! count (+ count 2))
132 count))))
133 (list get-count p)))
134 (get-count (car q))
135 (p (cadr q)))
136
137 (test-equal 5 (get-count))
138 (test-equal 0 (force p))
139 (test-equal 10 (get-count)))
140
141;=========================================================================
142; Test leaks: All the leak tests should run in bounded space.
143
144;=========================================================================
145; Leak test 1: Infinite loop in bounded space.
146
147(define (loop) (lazy (loop)))
148(test-leak (lambda () (force (loop)))) ;==> bounded space
149
150;=========================================================================
151; Leak test 2: Pending memos should not accumulate
152; in shared structures.
153
154(let ()
155 (define s (loop))
156 (test-leak (lambda () (force s)))) ;==> bounded space
157
158;=========================================================================
159; Leak test 3: Safely traversing infinite stream.
160
161(define (from n)
162 (delay (cons n (from (+ n 1)))))
163
164(define (traverse s)
165 (lazy (traverse (cdr (force s)))))
166
167(test-leak (lambda () (force (traverse (from 0))))) ;==> bounded space
168
169;=========================================================================
170; Leak test 4: Safely traversing infinite stream
171; while pointer to head of result exists.
172
173(let ()
174 (define s (traverse (from 0)))
175 (test-leak (lambda () (force s)))) ;==> bounded space
176
177;=========================================================================
178; Convenient list deconstructor used below.
179
180(define-syntax match
181 (syntax-rules ()
182 ((match exp
183 (() exp1)
184 ((h . t) exp2))
185 (let ((lst exp))
186 (cond ((null? lst) exp1)
187 ((pair? lst) (let ((h (car lst))
188 (t (cdr lst)))
189 exp2))
190 (else 'match-error))))))
191
192;========================================================================
193; Leak test 5: Naive stream-filter should run in bounded space.
194; Simplest case.
195
196(define (stream-filter p? s)
197 (lazy (match (force s)
198 (() (delay '()))
199 ((h . t) (if (p? h)
200 (delay (cons h (stream-filter p? t)))
201 (stream-filter p? t))))))
202
203(test-leak
204 (lambda ()
205 (force (stream-filter (lambda (n) (= n 10000000000))
206 (from 0)))))
207 ;==> bounded space
208
209;========================================================================
210; Leak test 6: Another long traversal should run in bounded space.
211
212; The stream-ref procedure below does not strictly need to be lazy.
213; It is defined lazy for the purpose of testing safe compostion of
214; lazy procedures in the times3 benchmark below (previous
215; candidate solutions had failed this).
216
217(define (stream-ref s index)
218 (lazy
219 (match (force s)
220 (() 'error)
221 ((h . t) (if (zero? index)
222 (delay h)
223 (stream-ref t (- index 1)))))))
224
225; Check that evenness is correctly implemented - should terminate:
226
227(test-equal 0
228 (force (stream-ref (stream-filter zero? (from 0))
229 0)))
230
231(let ()
232 (define s (stream-ref (from 0) 100000000))
233 (test-leak (lambda () (force s)))) ;==> bounded space
234
235;======================================================================
236; Leak test 7: Infamous example from SRFI 40.
237
238(define (times3 n)
239 (stream-ref (stream-filter
240 (lambda (x) (zero? (modulo x n)))
241 (from 0))
242 3))
243
244(force (times3 7))
245(test-leak (lambda ()
246 (force (times3 100000000)))) ;==> bounded space
247
248(test-end "lazy-tests")
249
250;; Local Variables:
251;; scheme-indent-styles: ((test-output 1) (test-equal 1))
252;; End:

Subscribers

People subscribed via source and target branches

to status/vote changes: