Debian Codegraph @

lib/data/random.scm

raw
1 ;;;
2 ;;; data.random - Random data genarators
3 ;;;
4 ;;; Copyright (c) 2013-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (define-module data.random
35 (use scheme.list)
36 (use scheme.charset)
37 (use srfi.27)
38 (use srfi.42)
39 (use util.match)
40 (use math.const)
41 (use math.mt-random)
42 (use gauche.uvector)
43 (use gauche.generator)
44 (use gauche.sequence)
45
46 (export random-data-random-source
47
48 integers$ integers-between$ fixnums$ chars$
49 samples$ booleans$
50 int8s$ uint8s$ int16s$ uint16s$ int32s$ uint32s$ int64s$ uint64s$
51 reals$ reals-between$ finite-flonums$
52 complexes-rectangular$ complexes-polar$
53 reals-normal$ reals-exponential$ reals-power-law$
54 integers-geometric$ integers-poisson$
55 regular-strings$
56
57 ;; preconstructed
58 fixnums booleans
59 int8s uint8s int16s uint16s int32s uint32s int64s uint64s
60
61 default-sizer
62 samples-from pairs-of tuples-of lists-of vectors-of strings-of
63 sequences-of
64 permutations-of combinations-of weighted-samples-from
65
66 ;; Deprecated API
67 random-data-seed with-random-data-seed
68 ))
69 (select-module data.random)
70
71 ;; API
72 ;; Use SRFI-27's default-random-source as the default, for the compatibility
73 ;; to SRFI-194.
74 ;; In the current implementation, this is <mersenne-twister> instance, and
75 ;; unless the user explicitly randomize it, it uses a fixed predetermined
76 ;; seed. It guarantees reproducibility.
77 (define random-data-random-source
78 (make-parameter default-random-source
79 (^x (assume (random-source? x)) x)))
80
81 ;; Deprecated API
82 ;; This is no longer useful, for the construted generators capture the
83 ;; random source at the time of construction and won't be affected
84 ;; by the changes of random-data-random-source afterwards.
85 (define random-data-seed
86 (getter-with-setter
87 (^[] (let1 rs (random-data-random-source)
88 (if (is-a? rs <mersenne-twister>)
89 (mt-random-get-seed rs)
90 (undefined))))
91 (^[seed] (random-data-random-source
92 (make <mersenne-twister> :seed seed)))))
93
94 ;; Deprecated API
95 (define (with-random-data-seed seed thunk)
96 ;; create st here so that reentering thunk retains the state.
97 (let1 st (make <mersenne-twister> :seed seed)
98 (parameterize ([random-data-random-source st])
99 (thunk))))
100
101 (define (%rand-int n s) (mt-random-integer s n))
102 (define (%rand-real0 s) (mt-random-real0 s))
103 (define (%rand-real s) (mt-random-real s))
104
105 ;;;
106 ;;; Primitive generators
107 ;;;
108
109 ;;
110 ;; Uniform distribution
111 ;;
112
113 ;; API. Generate integers uniformly in [start, start+size)
114 (define (integers$ size :optional (start 0))
115 (let1 s (random-data-random-source)
116 (^[] (+ (%rand-int size s) start))))
117
118 ;; API. Generate integers uniformly in [lb ub]
119 ;; (We avoid 'integer-range', for 'range' API takes exclusive upper bound.)
120 (define (integers-between$ lb ub)
121 (let ([s (random-data-random-source)]
122 [range (- ub lb -1)])
123 (^[] (+ (%rand-int range s) lb))))
124
125 ;; API.
126 (define (fixnums$) (integers-between$ (least-fixnum) (greatest-fixnum)))
127 (define (int8s$) (integers$ 256 -128))
128 (define (uint8s$) (integers$ 256))
129 (define (int16s$) (integers$ 65536 -32768))
130 (define (uint16s$) (integers$ 65536))
131 (define (int32s$) (integers$ (expt 2 32) (- (expt 2 31))))
132 (define (uint32s$) (integers$ (expt 2 32)))
133 (define (int64s$) (integers$ (expt 2 64) (- (expt 2 63))))
134 (define (uint64s$) (integers$ (expt 2 64)))
135 (define (booleans$) (let1 g (integers$ 2) (cut zero? (g))))
136
137 ;; API
138 ;; Preconstructed generators. They use default random source.
139 (define fixnums (fixnums$))
140 (define int8s (int8s$))
141 (define uint8s (uint8s$))
142 (define int16s (int16s$))
143 (define uint16s (uint16s$))
144 (define int32s (int32s$))
145 (define uint32s (uint32s$))
146 (define int64s (int64s$))
147 (define uint64s (uint64s$))
148 (define booleans (booleans$))
149
150 ;; API.
151 ;; The default value of cset is debatable. We play "safe" here, limiting
152 ;; ascii alphabets and digits, which would satisfy typical use cases without
153 ;; worrying character encodings too much.
154 (define (chars$ :optional (cset #[A-Za-z0-9]))
155 ;; We map the integer within the total # of chars in CSET into
156 ;; the delimited ranges of characters in CSET. For example, if CSET
157 ;; is splitted into a ranges ((48 . 57) (65 . 90) (97 . 122)),
158 ;; the table has the following mappings:
159 ;; 0 -> 48 (for range 48-57)
160 ;; 10 -> (- 65 10) (for range 65-90)
161 ;; 36 -> (- 97 36) (for range 97-122)
162 ;; We generate a random integer in [0, 61], that is, the size same as
163 ;; the # of chars in the CSET, then use tree-map-floor to find where it
164 ;; belongs; that gives us an offset to add to the sample number to get
165 ;; the char code.
166 ;;
167 ;; If CSET has only one range, however, we use simpler sampling
168 ;; for optimization.
169 (let ([ranges ((with-module gauche.internal %char-set-ranges) cset)]
170 [s (random-data-random-source)])
171 (if (null? (cdr ranges))
172 ;; simple case
173 (let* ([lb (caar ranges)]
174 [ub (cdar ranges)]
175 [size (- (+ ub 1) lb)])
176 (^[] (integer->char (+ (%rand-int size s) lb))))
177 ;; general case
178 (let* ([tab (make-tree-map)]
179 [total (do ([ranges ranges (cdr ranges)]
180 [cumu 0 (+ cumu (- (+ (cdar ranges) 1) (caar ranges)))])
181 [(null? ranges) cumu]
182 (tree-map-put! tab cumu (- (caar ranges) cumu)))])
183 (^[] (let1 p (%rand-int total s)
184 (receive (_ off) (tree-map-floor tab p)
185 (integer->char (+ p off)))))))))
186
187 ;; API. Choose one of the elements from collection randomly.
188 ;; NB: Not to be confused with samples-from below.
189 (define (samples$ coll)
190 (let* ([vs (coerce-to <vector> coll)]
191 [index-gen (integers$ (vector-length vs))])
192 (^[] (vector-ref vs (index-gen)))))
193
194 ;; API. Extra clamp ensures fp errors won't cause out-of-range value.
195 ;; NB: We clamp instead of rejecting the out-of-range value---since such
196 ;; value can only be produced on the FP values on the edge, and we should
197 ;; regard it inappropriate rounding (for our purpose). If we reject them,
198 ;; it will skew the distribution.
199 (define (reals$ :optional (size 1.0) (start 0.0))
200 (let ([ub (+ size start)]
201 [s (random-data-random-source)])
202 (^[] (clamp (+ start (* size (%rand-real0 s))) start ub))))
203 (define (reals-between$ lb ub)
204 (assume (<= lb ub))
205 (let1 s (random-data-random-source)
206 ;; lb + t*(ub-lb) = (1-t)*lb + t*ub
207 ;; The first way may overflow when lb << ub, and suffer precision
208 ;; loss if |lb| << |ub|.
209 (^[] (let1 t (%rand-real0 s)
210 (+ (* (- 1.0 t) lb) (* t ub))))))
211
212 ;; API. Uniformly sample from all possible finite flonums.
213 ;; The distribution is not uniform in mathematical sense, since flonums
214 ;; are denser when it's closer to zero.
215 ;; The imlementation assumes IEEE double.
216 ;; NB: We generate zeros with non-zero exponents, but they are coerced
217 ;; to the canonical zeros internally. That makes zeros appear x2000 likely
218 ;; than other numbers. Whether it is an issue or not depends on the
219 ;; application; we leave it as it is for now.
220 (define (finite-flonums$)
221 (let ([expgen (integers-between$ -1074 971)]
222 [sgngen (samples$ '#(1 -1))]
223 [mntgen (integers$ (real-expt 2 52))])
224 (^[]
225 (let ([exp (expgen)]
226 [mantissa (mntgen)]
227 [sign (sgngen)])
228 (if (or (= -1074 exp) (zero? mantissa))
229 (encode-float (vector mantissa exp sign)) ;denormalized or zero
230 (encode-float (vector (+ (real-expt 2 52) mantissa) exp sign)))))))
231
232 ;; rational
233
234 (define (complexes-rectangular$ re-lb re-ub im-lb im-ub)
235 (assume (<= re-lb re-ub))
236 (assume (<= im-lb im-ub))
237 (let ([rgen (reals-between$ re-lb re-ub)]
238 [igen (reals-between$ im-lb im-ub)])
239 (^[] (make-rectangular (rgen) (igen)))))
240
241 (define complexes-polar$
242 (case-lambda
243 [(mag-lb mag-ub)
244 (complexes-polar$ 0 mag-lb mag-ub 0 (* 2 pi))]
245 [(origin mag-lb mag-ub)
246 (complexes-polar$ origin mag-lb mag-ub 0 (* 2 pi))]
247 [(mag-lb mag-ub ang-lb ang-ub)
248 (complexes-polar$ 0 mag-lb mag-ub ang-lb ang-ub)]
249 [(origin mag-lb mag-ub ang-lb ang-ub)
250 (assume (<= mag-lb mag-ub))
251 (assume (<= ang-lb ang-ub))
252 (let* ([b (square mag-lb)]
253 [m (- (square mag-ub) b)]
254 [maggen (reals$ m b)]
255 [anggen (reals-between$ ang-lb ang-ub)])
256 (^[] (+ origin (make-polar (sqrt (maggen)) (anggen)))))]))
257
258 ;;
259 ;; Nonuniform distributions
260 ;;
261
262 ;; Normal distribution (continuous - generates real numbers)
263 ;; Box-Muller algorithm
264 ;; NB: We tested Ziggurat method, too (see git repo for the code),
265 ;; only to find out Box-Muller is faster about 12% - presumably
266 ;; the overhead of each ops is larger in Gauche than C/C++, and
267 ;; so the difference of cost of log or sin from the primitive
268 ;; addition/multiplication are negligible.
269 (define (reals-normal$ :optional (mean 0) (deviation 1))
270 (let1 s (random-data-random-source)
271 (^[] (let ([r (real-sqrt (* -2 (real-ln (%rand-real s))))]
272 [theta (* 2pi (%rand-real s))])
273 (+ mean (* deviation r (real-sin theta)))))))
274
275 #|
276 Simple test of gaussian sampling: Generate some data with this:
277
278 (with-output-to-file "tmp"
279 (^[] (let1 g (normal$ 2 3) (dotimes [i 1000000] (print (g))))))
280
281 Then plot with gnuplot:
282
283 binwidth=0.025
284 bin(x,width)=width*floor(x/width)
285 plot 'tmp' using (bin($1,binwidth)):(1.0) smooth freq with boxes
286 |#
287
288 ;; Exponential distribution - continuous
289 (define (reals-exponential$ m)
290 (let1 s (random-data-random-source)
291 (^[] (- (* m (log (%rand-real s)))))))
292
293 ;; Power-law distribution
294 ;; p(x) = (α-1)/xmin (x/xmin)^{-α} x >= xmin, α > 1
295 ;; We use method described in Appendix D of
296 ;; Aaron Clauset, Cosma Rohilla Shalizi, M.E.J.Newman, Power-Law Distributions
297 ;; in Empirical Data, SIAM Review, 51(4) pp.661--703, Dec. 2009.
298 ;; Preprint https://arxiv.org/abs/0706.1062
299 (define (reals-power-law$ xmin power)
300 (assume (positive? xmin))
301 (assume (> power 1))
302 (let ([s (random-data-random-source)]
303 [exponent (- (/ (- power 1)))])
304 (^[] (* xmin (expt (- 1 (%rand-real s)) exponent)))))
305
306
307 ;; Draw from geometric distribution, with success probability p.
308 ;; Mean is 1/p, variance is (1-p)/p^2
309 (define (integers-geometric$ p)
310 (let ([c (/ (log (- 1.0 p)))]
311 [s (random-data-random-source)])
312 (^[] (ceiling->exact (* c (log (%rand-real s)))))))
313
314 ;; Draw from poisson distribution with mean L, variance L.
315 ;; For small L, we use Knuth's method. For larger L, we use rejection
316 ;; method by Atkinson, The Computer Generation of Poisson Random Variables,
317 ;; J. of the Royal Statistical Society Series C (Applied Statistics), 28(1),
318 ;; pp29-35, 1979. The code here is a port by John D Cook's C++ implementation
319 ;; (http://www.johndcook.com/stand_alone_code.html )
320 (define (integers-poisson$ L)
321 (define s (random-data-random-source))
322 (if (< L 36)
323 (^[] (do ([exp-L (exp (- L))]
324 [k 0 (+ k 1)]
325 [p 1.0 (* p (%rand-real s))])
326 [(<= p exp-L) (- k 1)]))
327 (let* ([c (- 0.767 (/ 3.36 L))]
328 [beta (/ pi (sqrt (* 3 L)))]
329 [alpha (* beta L)]
330 [k (- (log c) L (log beta))])
331 (rec (loop)
332 (let* ([u (%rand-real s)]
333 [x (/ (- alpha (log (/ (- 1.0 u) u))) beta)]
334 [n (floor->exact (+ x 0.5))])
335 (if (< n 0)
336 (loop)
337 (let* ([v (%rand-real s)]
338 [y (- alpha (* beta x))]
339 [t (+ 1.0 (exp y))]
340 [lhs (+ y (log (/ v (* t t))))]
341 [rhs (+ k (* n (log L)) (- (lgamma (+ n 1))))])
342 (if (<= lhs rhs)
343 n
344 (loop)))))))))
345
346 #|
347 ;; This generates histograms of samples
348 ;; e.g. (gen-hist 1000 (poisson$ 5) (poisson$ 10) (poisson$ 20) (poisson$ 50))
349 (define (gen-hist count . thunks)
350 (let ([bins (map (^_ (make-hash-table 'eqv?)) thunks)]
351 [maxkey 0])
352 (dotimes [n count]
353 (do-ec (:parallel (: thunk thunks)
354 (: bin bins))
355 (let1 key (thunk)
356 (when (> key maxkey) (set! maxkey key))
357 (hash-table-update! bin key (cut + <> 1) 0))))
358 (dotimes [n (+ maxkey 1)]
359 (print
360 (string-join (cons (x->string n)
361 (map (^[bin] (x->string (hash-table-get bin n 0)))
362 bins))
363 " ")))))
364 |#
365
366 ;; API.
367 ;; Generate strings that is accepted with a regular expression regex
368 ;;
369 ;; We construct NFA from regex AST. Each node is a closure that emits
370 ;; character(s), and optionally calls other node.
371
372 (define (regular-strings$ regex)
373 (assume-type regex <regexp>)
374 (let1 nfa (%regex->nfa (regexp-ast regex))
375 (^[] (with-output-to-string (cut nfa #f)))))
376
377 (define (%regex->nfa ast)
378 (define s (random-data-random-source))
379 (define (%emit c case-fold)
380 (let1 cc (if (and case-fold (zero? (%rand-int 2 s)))
381 (cond [(char-lower-case? c) (char-upcase c)]
382 [(char-upper-case? c) (char-downcase c)]
383 [else c])
384 c)
385 (display cc))
386 #t)
387 (define (rec a)
388 (match a
389 [(? char?) (cut %emit a <>)]
390 [(? char-set?) (let1 g (chars$ a) (cut %emit (g) <>))]
391 ['any (let1 g (chars$ char-set:full) (cut %emit (g) <>))]
392 [(or 'bol 'wb 'nwb) (^[case-fold] #t)]
393 ['eol (^[case-fold] #f)]
394 [('seq . as) (let1 nodes (map rec as)
395 (^[case-fold] (every (cut <> case-fold) nodes)))]
396 [('seq-uncase . as) (let1 nodes (map rec as)
397 (^_ (every (cut <> #t) nodes)))]
398 [('seq-case . as) (let1 nodes (map rec as)
399 (^_ (every (cut <> #f) nodes)))]
400 [('alt . as) (let1 choice-gen (samples$ (map rec as))
401 (^[case-fold] ((choice-gen) case-fold)))]
402 [((or 'rep 'rep-min 'rep-while) m n . as)
403 (let1 nodes (map rec as)
404 (^[case-fold]
405 (let loop ([k 1])
406 (and (every (cut <> case-fold) nodes)
407 (cond [(< k m) (loop (+ k 1))]
408 [(or (not n) (< k n))
409 (if (zero? (%rand-int 2 s))
410 (loop (+ k 1))
411 #t)]
412 [else #t])))))]
413 [('comp . cs) (let1 g (chars$ (char-set-complement cs))
414 (cut %emit (g) <>))]
415 [('cpat _ _ _)
416 (error "Conditional regexp can't be used (yet) to generate strings:"
417 (regexp-unparse ast))]
418 [('once . as) (let1 nodes (map rec as)
419 (^[case-fold] (every (cut <> case-fold) nodes)))]
420 [((or 'assert 'nassert) . _)
421 (error "Lookahead/behind assertion can't be used (yet) to \
422 generate strings:" (regexp-unparse ast))]
423 [((? integer? n) _ . as)
424 (let1 nodes (map rec as)
425 (^[case-fold] (every (cut <> case-fold) nodes)))]
426 [_ (error "Unsupported regexp to generate strings:"
427 (regexp-unparse ast))]))
428
429 (rec ast))
430
431 ;;;
432 ;;; Generator combinators
433 ;;;
434
435 ;; API
436 (define (samples-from seq-of-gen)
437 (let* ([sources (coerce-to <vector> seq-of-gen)]
438 [num-sources (vector-length sources)])
439 (case num-sources
440 [(0) eof-object]
441 [(1) (~ sources 0)]
442 [else
443 (let ([num-active num-sources]
444 [exhausted (make-vector num-sources #f)]
445 [s (random-data-random-source)])
446 (^[]
447 (let loop ()
448 (if (zero? num-active)
449 (eof-object)
450 (let* ([choice (%rand-int num-sources s)]
451 [r ((vector-ref sources choice))])
452 (if (eof-object? r)
453 (begin
454 (unless (vector-ref exhausted choice)
455 (vector-set! exhausted choice #t)
456 (dec! num-active))
457 (loop))
458 r))))))])))
459
460 ;; API
461 ;; weight&gens :: ((<real> . <generator>) ...)
462 (define (weighted-samples-from weight&gens)
463 (let* ([tab (make-tree-map)]
464 [total (do [(w&g weight&gens (cdr w&g))
465 (cumu 0 (+ cumu (caar w&g)))]
466 [(null? w&g) cumu]
467 (tree-map-put! tab cumu (cdar w&g)))]
468 [s (random-data-random-source)])
469 (^[] (receive (_ gen) (tree-map-floor tab (* (%rand-real0 s) total))
470 (gen)))))
471
472 ;; API
473 (define (pairs-of car-gen cdr-gen) (^[] (cons (car-gen) (cdr-gen))))
474
475 ;; API
476 (define (tuples-of . gens) (^[] (map (^g (g)) gens)))
477
478 ;; We accept constant integer or generator
479 (define-syntax %with-sizer
480 (syntax-rules ()
481 [(_ sizer . body)
482 (let1 sizer (if (integer? sizer) (^[] sizer) sizer)
483 . body)]))
484
485 (define default-sizer (make-parameter (integers-poisson$ 4)))
486
487 ;; API
488 (define lists-of
489 (case-lambda
490 [(item-gen) (lists-of (default-sizer) item-gen)]
491 [(sizer item-gen)
492 (%with-sizer sizer (^[] (list-tabulate (sizer) (^_ (item-gen)))))]))
493
494 ;; API
495 (define vectors-of
496 (case-lambda
497 [(item-gen) (vectors-of (default-sizer) item-gen)]
498 [(sizer item-gen)
499 (%with-sizer sizer
500 (^[] (let1 len (sizer)
501 (rlet1 vec (make-vector len)
502 (do-ec (: i len) (vector-set! vec i (item-gen)))))))]))
503
504 ;; API
505 (define strings-of
506 (case-lambda
507 [() (strings-of (default-sizer) (chars$))]
508 [(item-gen) (strings-of (default-sizer) item-gen)]
509 [(sizer item-gen)
510 (%with-sizer sizer
511 (^[] (let1 len (sizer)
512 (with-output-to-string
513 (^[] (do-ec (: i len) (display (item-gen))))))))]))
514
515 ;; API
516 (define sequences-of
517 (case-lambda
518 [(class item-gen) (sequences-of class (default-sizer) item-gen)]
519 [(class sizer item-gen)
520 (%with-sizer sizer
521 (^[] (let1 len (sizer)
522 (with-builder (class add! get :size len)
523 (dotimes [len] (add! (item-gen)))
524 (get)))))]))
525
526 ;; API
527 (define (permutations-of seq)
528 (let1 s (random-data-random-source)
529 (cut shuffle seq s)))
530
531 ;; API
532 (define (combinations-of len seq)
533 (let1 indices (list->vector (iota (size-of seq)))
534 (^[] (let1 ix (shuffle indices)
535 (coerce-to (class-of seq)
536 (list-ec (: i len) (ref seq (vector-ref ix i))))))))