Debian Codegraph @

lib/gambit/list/list.scm-new

raw
1 ;;;============================================================================
2
3 ;;; File: "list.scm"
4
5 ;;; Copyright (c) 2020 by Marc Feeley, All Rights Reserved.
6
7 ;;;============================================================================
8
9 ;;; List operations.
10
11 (##include "list#.scm")
12
13 ;;;----------------------------------------------------------------------------
14
15 (define-prim (##pair? obj))
16
17 (define-prim (pair? obj)
18 (macro-force-vars (obj)
19 (##pair? obj)))
20
21 (define-prim (##cons obj1 obj2))
22
23 (define-prim (cons obj1 obj2)
24 (##cons obj1 obj2))
25
26 (##define-macro (define-prim-c...r-procedures from-length to-length)
27
28 (define (gen-name pattern)
29
30 (define (ads pattern)
31 (if (= pattern 1)
32 ""
33 (string-append (ads (quotient pattern 2))
34 (if (odd? pattern) "d" "a"))))
35
36 (string->symbol (string-append "c" (ads pattern) "r")))
37
38 (define (gen3 i j)
39 (if (> i j)
40 `()
41 (let* ((name
42 (gen-name i))
43 (##name
44 (string->symbol (string-append "##" (symbol->string name)))))
45
46 (define (gen1 var pattern)
47 (if (<= pattern 3)
48 (if (= pattern 3) `(##cdr ,var) `(##car ,var))
49 `(let ((x ,(if (odd? pattern) `(##cdr ,var) `(##car ,var))))
50 ,(gen1 'x (quotient pattern 2)))))
51
52 (define (gen2 var pattern)
53 `(macro-check-pair ,var 1 (,name pair);;TODO: error message confusing?
54 ,(if (<= pattern 3)
55 (if (= pattern 3) `(##cdr ,var) `(##car ,var))
56 `(let ((x ,(if (odd? pattern) `(##cdr ,var) `(##car ,var))))
57 (macro-force-vars (x)
58 ,(gen2 'x (quotient pattern 2)))))))
59
60 `((define-prim (,##name pair)
61 ,(gen1 'pair i))
62
63 (define-prim (,name pair)
64 (macro-force-vars (pair)
65 ,(gen2 'pair i)))
66
67 ,@(gen3 (+ i 1) j)))))
68
69 `(begin ,@(gen3 (expt 2 from-length) (- (expt 2 (+ to-length 1)) 1))))
70
71 (define-prim-c...r-procedures 1 4) ;; define car to cddddr
72
73 (define-prim (##set-car! pair val))
74
75 (define-prim (set-car! pair val)
76 (macro-force-vars (pair)
77 (macro-check-pair pair 1 (set-car! pair val)
78 (macro-check-mutable pair 1 (set-car! pair val)
79 (begin
80 (##set-car! pair val)
81 (##void))))))
82
83 (define-prim (##set-cdr! pair val))
84
85 (define-prim (set-cdr! pair val)
86 (macro-force-vars (pair)
87 (macro-check-pair pair 1 (set-cdr! pair val)
88 (macro-check-mutable pair 1 (set-cdr! pair val)
89 (begin
90 (##set-cdr! pair val)
91 (##void))))))
92
93 (define-prim (##null? obj)
94 (##eq? obj '()))
95
96 (define-prim (null? obj)
97 (macro-force-vars (obj)
98 (##null? obj)))
99
100 (define-prim (##list? lst)
101
102 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
103
104 ;; This procedure may get into an infinite loop if another thread
105 ;; mutates "lst" (if lst1 and lst2 each point to disconnected cycles).
106
107 (let loop ((lst1 lst) (lst2 lst))
108 (macro-force-vars (lst1)
109 (if (not (pair? lst1))
110 (null? lst1)
111 (let ((lst1 (cdr lst1)))
112 (macro-force-vars (lst1 lst2)
113 (cond ((eq? lst1 lst2)
114 #f)
115 ((not (pair? lst2))
116 ;; this case is possible if other threads mutate the list
117 (null? lst2))
118 ((pair? lst1)
119 (loop (cdr lst1) (cdr lst2)))
120 (else
121 (null? lst1)))))))))
122
123 (define-prim (list? lst)
124 (##list? lst))
125
126 (define-prim (##list . lst)
127 lst)
128
129 (define-prim (list . lst)
130 lst)
131
132 (define-prim (##length lst)
133
134 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
135
136 (let loop ((x lst) (n 0))
137 (if (pair? x)
138 (loop (cdr x) (fx+ n 1))
139 n)))
140
141 (define-prim (length lst)
142
143 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
144 (namespace ("" length)) ;; but not length to ##length
145
146 (let loop ((x lst) (n 0))
147 (macro-force-vars (x)
148 (if (pair? x)
149 (loop (cdr x) (fx+ n 1))
150 (macro-check-list x 1 (length lst)
151 n)))))
152
153 (define-prim (##append2 lst1 lst2)
154
155 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
156
157 (if (pair? lst1)
158 (cons (car lst1) (##append2 (cdr lst1) lst2))
159 lst2))
160
161 (define-prim (##append-lists lst)
162
163 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
164
165 (if (pair? lst)
166 (let ((rev-lst (reverse lst)))
167 (let loop ((rev-lst (cdr rev-lst)) (result (car rev-lst)))
168 (if (pair? rev-lst)
169 (loop (cdr rev-lst)
170 (##append2 (car rev-lst) result))
171 result)))
172 '()))
173
174 (define-prim (##append
175 #!optional
176 (lst1 (macro-absent-obj))
177 (lst2 (macro-absent-obj))
178 #!rest
179 others)
180
181 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
182
183 (if (eq? lst2 (macro-absent-obj))
184 (if (eq? lst1 (macro-absent-obj))
185 '()
186 lst1)
187 (##append-lists (cons lst1 (cons lst2 others)))))
188
189 (define-prim (append
190 #!optional
191 (lst1 (macro-absent-obj))
192 (lst2 (macro-absent-obj))
193 #!rest
194 others)
195
196 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
197 (namespace ("" append)) ;; but not append to ##append
198
199 (define (append-multiple head tail arg-num)
200 (if (null? tail)
201 head
202 (macro-force-vars (head)
203 (if (null? head)
204 (append-multiple (car tail) (cdr tail) (fx+ arg-num 1))
205 (list-expected-check
206 (append-multiple-non-null head
207 tail
208 arg-num
209 (fx+ arg-num 1)))))))
210
211 (define (append-multiple-non-null x lsts arg-num1 arg-num2)
212 ;; x!=(), returns fixnum on error
213 (let ((head (car lsts))
214 (tail (cdr lsts)))
215 (if (null? tail)
216 (append-2-non-null x head arg-num1)
217 (macro-force-vars (head)
218 (if (null? head)
219 (append-multiple-non-null x
220 tail
221 arg-num1
222 (fx+ arg-num2 1))
223 (let ((result
224 (append-multiple-non-null head
225 tail
226 arg-num2
227 (fx+ arg-num2 1))))
228 (macro-if-checks
229 (if (fixnum? result)
230 result
231 (append-2-non-null x result arg-num1))
232 (append-2-non-null x result arg-num1))))))))
233
234 (define (append-2-non-null x y arg-num)
235 ;; x!=(), returns fixnum on error
236 (if (pair? x)
237 (let ((result (cons (car x) '())))
238 (let loop ((last result) (tail (cdr x)))
239 (macro-force-vars (tail)
240 (if (pair? tail)
241 (let ((next (cons (car tail) '())))
242 (set-cdr! last next)
243 (loop next (cdr tail)))
244 (begin
245 (set-cdr! last y)
246 (macro-if-checks
247 (if (null? tail)
248 result
249 arg-num) ;; error: list expected
250 result))))))
251 (macro-if-checks
252 arg-num ;; error: list expected
253 y)))
254
255 (define (list-expected-check result)
256 (macro-if-checks
257 (if (fixnum? result)
258 (macro-fail-check-list result (append lst1 lst2 . others))
259 result)
260 result))
261
262 (cond ((eq? lst2 (macro-absent-obj))
263 (if (eq? lst1 (macro-absent-obj))
264 '()
265 lst1))
266 ((null? others)
267 (macro-force-vars (lst1)
268 (if (null? lst1)
269 lst2
270 (list-expected-check (append-2-non-null lst1 lst2 1)))))
271 (else
272 (append-multiple lst1 (cons lst2 others) 1))))
273
274 (define-prim (##reverse lst #!optional (tail '()))
275
276 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
277
278 (let loop ((x lst) (result tail))
279 (if (pair? x)
280 (loop (cdr x) (cons (car x) result))
281 result)))
282
283 (define-prim (reverse lst)
284
285 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
286 (namespace ("" reverse)) ;; but not reverse to ##reverse
287
288 (let loop ((x lst) (result '()))
289 (macro-force-vars (x)
290 (if (pair? x)
291 (loop (cdr x) (cons (car x) result))
292 (macro-check-list x 1 (reverse lst)
293 result)))))
294
295 (define-prim (##list-ref lst k)
296
297 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
298 (namespace ("" list-ref)) ;; but not list-ref to ##list-ref
299
300 (let loop ((x lst) (i k))
301 (if (fx< 0 i)
302 (loop (cdr x) (fx- i 1))
303 (car x))))
304
305 (define-prim (list-ref lst k)
306
307 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
308 (namespace ("" list-ref)) ;; but not list-ref to ##list-ref
309
310 (macro-force-vars (k)
311 (macro-check-index k 2 (list-ref lst k)
312 (let loop ((x lst) (i k))
313 (macro-force-vars (x)
314 (macro-check-pair x 1 (list-ref lst k);;;;;;;error message confusing?
315 (if (fx< 0 i)
316 (loop (cdr x) (fx- i 1))
317 (car x))))))))
318
319 (define-prim (##list-set! lst k val)
320
321 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
322
323 (let loop ((x lst) (i k))
324 (if (fx< 0 i)
325 (loop (cdr x) (fx- i 1))
326 (begin
327 (set-car! x val)
328 (void)))))
329
330 (define-prim (list-set! lst k val)
331
332 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
333 (namespace ("" list-set!)) ;; but not list-set! to ##list-set!
334
335 (macro-force-vars (k)
336 (macro-check-index k 2 (list-set! lst k val)
337 (let loop ((x lst) (i k))
338 (macro-force-vars (x)
339 (macro-check-pair x 1 (list-set! lst k val)
340 (if (fx< 0 i)
341 (loop (cdr x) (fx- i 1))
342 (macro-check-mutable x 1 (list-set! lst k val)
343 (begin
344 (set-car! x val)
345 (void))))))))))
346
347 (define-prim (##list-set lst k val)
348
349 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
350
351 (define (set x i)
352 (if (fx< 0 i)
353 (cons (car x) (set (cdr x) (fx- i 1)))
354 (cons val (cdr x))))
355
356 (set lst k))
357
358 (define-prim (list-set lst k val)
359
360 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
361 (namespace ("" list-set)) ;; but not list-set to ##list-set
362
363 (macro-force-vars (k)
364 (macro-check-index k 2 (list-set lst k val)
365
366 (let ()
367
368 (define (set x i)
369 (macro-force-vars (x)
370 (if (pair? x)
371 (if (fx< 0 i)
372 (let ((r (set (cdr x) (fx- i 1))))
373 (if (pair? r)
374 (cons (car x) r)
375 r))
376 (cons val (cdr x)))
377 #f)))
378
379 (or (set lst k)
380 (##fail-check-pair 1 list-set lst k val))))))
381
382 (define-prim (##memq obj lst)
383
384 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
385
386 (let loop ((x lst))
387 (if (pair? x)
388 (if (eq? obj (car x))
389 x
390 (loop (cdr x)))
391 #f)))
392
393 (define-prim (memq obj lst)
394
395 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
396 (namespace ("" memq)) ;; but not memq to ##memq
397
398 (macro-force-vars (obj)
399 (let loop ((x lst))
400 (macro-force-vars (x)
401 (if (pair? x)
402 (let ((y (car x)))
403 (macro-force-vars (y)
404 (if (eq? obj y)
405 x
406 (loop (cdr x)))))
407 (macro-check-list x 2 (memq obj lst)
408 #f))))))
409
410 (define-prim (##memv obj lst)
411
412 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
413
414 (let loop ((x lst))
415 (if (pair? x)
416 (if (let ()
417 (##declare (generic)) ;; avoid fixnum specific eqv?
418 (eqv? obj (car x)))
419 x
420 (loop (cdr x)))
421 #f)))
422
423 (define-prim (memv obj lst)
424
425 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
426 (namespace ("" memv)) ;; but not memv to ##memv
427
428 (macro-force-vars (obj)
429 (let loop ((x lst))
430 (macro-force-vars (x)
431 (if (pair? x)
432 (let ((y (car x)))
433 (macro-force-vars (y)
434 (if (let ()
435 (##declare (generic)) ;; avoid fixnum specific eqv?
436 (eqv? obj y))
437 x
438 (loop (cdr x)))))
439 (macro-check-list x 2 (memv obj lst)
440 #f))))))
441
442 (define-prim (##member obj lst #!optional (compare ##equal?))
443
444 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
445
446 (let loop ((x lst))
447 (if (pair? x)
448 (if (compare obj (car x))
449 x
450 (loop (cdr x)))
451 #f)))
452
453 (define-prim (member obj lst #!optional (c (macro-absent-obj)))
454
455 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
456 (namespace ("" member)) ;; but not member to ##member
457
458 (macro-force-vars (c)
459 (let ((compare (if (eq? c (macro-absent-obj)) ##equal? c)))
460 (macro-check-procedure compare 3 (member obj lst c)
461 (let loop ((x lst))
462 (macro-force-vars (x)
463 (if (pair? x)
464 (let ((y (car x)))
465 (if (compare obj y)
466 x
467 (loop (cdr x))))
468 (macro-check-list x 2 (member obj lst c)
469 #f))))))))
470
471 ;; ##assq defined in _kernel.scm
472
473 (define-prim (assq obj lst)
474
475 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
476 (namespace ("" assq)) ;; but not assq to ##assq
477
478 (macro-force-vars (obj)
479 (let loop ((x lst))
480 (macro-force-vars (x)
481 (if (pair? x)
482 (let ((couple (car x)))
483 (macro-force-vars (couple)
484 (macro-check-pair-list couple 2 (assq obj lst)
485 (let ((y (car couple)))
486 (macro-force-vars (y)
487 (if (eq? obj y)
488 couple
489 (loop (cdr x))))))))
490 (macro-check-list x 2 (assq obj lst)
491 #f))))))
492
493 (define-prim (##assv obj lst)
494
495 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
496
497 (let loop ((x lst))
498 (if (pair? x)
499 (let ((couple (car x)))
500 (if (let ()
501 (##declare (generic)) ;; avoid fixnum specific eqv?
502 (eqv? obj (car couple)))
503 couple
504 (loop (cdr x))))
505 #f)))
506
507 (define-prim (assv obj lst)
508
509 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
510 (namespace ("" assv)) ;; but not assv to ##assv
511
512 (macro-force-vars (obj)
513 (let loop ((x lst))
514 (macro-force-vars (x)
515 (if (pair? x)
516 (let ((couple (car x)))
517 (macro-force-vars (couple)
518 (macro-check-pair-list couple 2 (assv obj lst)
519 (let ((y (car couple)))
520 (macro-force-vars (y)
521 (if (let ()
522 (##declare (generic)) ;; avoid fixnum specific eqv?
523 (eqv? obj y))
524 couple
525 (loop (cdr x))))))))
526 (macro-check-list x 2 (assv obj lst)
527 #f))))))
528
529 (define-prim (##assoc obj lst #!optional (compare ##equal?))
530
531 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
532
533 (let loop ((x lst))
534 (if (pair? x)
535 (let ((couple (car x)))
536 (if (compare obj (car couple))
537 couple
538 (loop (cdr x))))
539 #f)))
540
541 (define-prim (assoc obj lst #!optional (c (macro-absent-obj)))
542
543 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
544 (namespace ("" assoc)) ;; but not assoc to ##assoc
545
546 (macro-force-vars (c)
547 (let ((compare (if (eq? c (macro-absent-obj)) ##equal? c)))
548 (macro-check-procedure compare 3 (assoc obj lst c)
549 (let loop ((x lst))
550 (macro-force-vars (x)
551 (if (pair? x)
552 (let ((couple (car x)))
553 (macro-force-vars (couple)
554 (macro-check-pair-list couple 2 (assoc obj lst c)
555 (let ((y (car couple)))
556 (if (compare obj y)
557 couple
558 (loop (cdr x)))))))
559 (macro-check-list x 2 (assoc obj lst c)
560 #f))))))))
561
562 (define-prim (##remq elem lst)
563
564 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
565
566 (define (rem elem lst)
567 (if (pair? lst)
568 (let* ((lst2 (rem elem (cdr lst)))
569 (x (car lst)))
570 (if (eq? x elem)
571 lst2
572 (if (eq? lst2 (cdr lst))
573 lst
574 (cons x lst2))))
575 '()))
576
577 (rem elem lst))
578
579 ;;;----------------------------------------------------------------------------
580
581 (define ##allow-length-mismatch? #t)
582
583 (define-prim (##allow-length-mismatch?-set! x)
584 (set! ##allow-length-mismatch? x))
585
586 (define (##proper-list-length lst)
587
588 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
589
590 (let loop ((lst lst) (n 0))
591 (macro-force-vars (lst)
592 (cond ((pair? lst)
593 (loop (cdr lst) (fx+ n 1)))
594 ((null? lst)
595 n)
596 (else
597 #f)))))
598
599 (define (##cars lsts end)
600
601 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
602
603 (define (cars lsts end) ;; assumes lsts is a list of pairs
604 (if (pair? lsts)
605 (let ((lst1 (car lsts)))
606 (macro-force-vars (lst1)
607 (cons (car lst1)
608 (cars (cdr lsts) end))))
609 end))
610
611 (cars lsts end))
612
613 (define (##cdrs lsts)
614
615 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
616
617 (define (cdrs lsts)
618 (if (pair? lsts)
619 (let ((tail (cdrs (cdr lsts))))
620
621 ;; tail is either
622 ;; 1) () : (cdr lsts) is ()
623 ;; 2) #f : all the elements of (cdr lsts) are not pairs
624 ;; 3) a pair : all the elements of (cdr lsts) are pairs
625 ;; 4) a fixnum >= 0 : at least one of (cdr lsts) is ()
626 ;; and at index tail of (cdr lsts) is a pair
627 ;; 5) a fixnum < 0 : at least one of (cdr lsts) is not a pair and
628 ;; at index tail - ##min-fixnum of (cdr lsts) is
629 ;; the first element that is neither a pair or ()
630
631 (let ((lst1 (car lsts)))
632 (macro-force-vars (lst1)
633 (cond ((pair? lst1)
634 (cond ((fixnum? tail)
635 (if (fx< tail 0)
636 (fx+ tail 1)
637 0))
638 ((not tail)
639 (if ##allow-length-mismatch?
640 #f
641 0))
642 (else
643 (cons (cdr lst1) tail))))
644 ((null? lst1)
645 (cond ((fixnum? tail)
646 (fx+ tail 1))
647 ((pair? tail)
648 (if ##allow-length-mismatch?
649 #f
650 1))
651 (else
652 #f)))
653 (else
654 ##min-fixnum)))))
655 '()))
656
657 (cdrs lsts))
658
659 (define-prim (##map proc x . y)
660
661 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
662
663 (define (map-1 x)
664
665 (define (map-1 lst1)
666 (if (pair? lst1)
667 (let* ((result (proc (car lst1)))
668 (tail (map-1 (cdr lst1))))
669 (cons result tail))
670 '()))
671
672 (map-1 x))
673
674 (define (map-n x-y)
675
676 (define (map-n lsts)
677 (let ((rests (##cdrs lsts)))
678 (if (not rests)
679 '()
680 (if (pair? rests)
681 (let* ((args (##cars lsts '()))
682 (result (apply proc args))
683 (tail (map-n rests)))
684 (cons result tail))
685 '()))))
686
687 (map-n x-y))
688
689 (if (null? y)
690 (map-1 x)
691 (map-n (cons x y))))
692
693 (define-prim (map proc x . y)
694
695 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
696 (namespace ("" map)) ;; but not map to ##map
697
698 (macro-force-vars (proc)
699 (macro-check-procedure proc 1 (map proc x . y)
700 (let ()
701
702 (define (map-1 x)
703
704 (define (map-1 lst1)
705 (macro-force-vars (lst1)
706 (if (pair? lst1)
707 (let* ((result (proc (car lst1)))
708 (tail (map-1 (cdr lst1))))
709 (macro-if-checks
710 (and tail
711 (cons result tail))
712 (cons result tail)))
713 (macro-if-checks
714 (if (null? lst1)
715 '()
716 #f)
717 '()))))
718
719 (macro-if-checks
720 (let ((result (map-1 x)))
721 (or result
722 (macro-fail-check-list
723 2
724 (map proc x))))
725 (map-1 x)))
726
727 (define (map-n x-y)
728
729 (define (map-n lsts)
730 (let ((rests (##cdrs lsts)))
731 (if (not rests)
732 '()
733 (if (pair? rests)
734 (let* ((args (##cars lsts '()))
735 (result (apply proc args))
736 (tail (map-n rests)))
737 (macro-if-checks
738 (if (fixnum? tail)
739 tail
740 (cons result tail))
741 (cons result tail)))
742 (macro-if-checks
743 rests
744 '())))))
745
746 (macro-if-checks
747 (let ((result (map-n x-y)))
748 (if (fixnum? result)
749 (if (fx< result 0)
750 (macro-fail-check-list
751 (fx- (fx+ 2 result) ##min-fixnum)
752 (map proc . x-y))
753 (##raise-length-mismatch-exception
754 (fx+ 2 result)
755 '()
756 map
757 proc
758 x-y))
759 result))
760 (map-n x-y)))
761
762 (if (null? y)
763 (map-1 x)
764 (map-n (cons x y)))))))
765
766 (define-prim (##for-each proc x . y)
767
768 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
769
770 (define (for-each-1 x)
771
772 (define (for-each-1 lst1)
773 (if (pair? lst1)
774 (begin
775 (proc (car lst1))
776 (for-each-1 (cdr lst1)))
777 (void)))
778
779 (for-each-1 x))
780
781 (define (for-each-n x-y)
782
783 (define (for-each-n lsts)
784 (let ((rests (##cdrs lsts)))
785 (if (not rests)
786 (void)
787 (if (pair? rests)
788 (begin
789 (apply proc (##cars lsts '()))
790 (for-each-n rests))
791 (void)))))
792
793 (for-each-n x-y))
794
795 (if (null? y)
796 (for-each-1 x)
797 (for-each-n (cons x y))))
798
799 (define-prim (for-each proc x . y)
800
801 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
802 (namespace ("" for-each)) ;; but not for-each to ##for-each
803
804 (macro-force-vars (proc)
805 (macro-check-procedure proc 1 (for-each proc x . y)
806 (let ()
807
808 (define (for-each-1 x)
809
810 (define (for-each-1 lst1)
811 (macro-force-vars (lst1)
812 (if (pair? lst1)
813 (begin
814 (proc (car lst1))
815 (for-each-1 (cdr lst1)))
816 (macro-check-list lst1 2 (for-each proc x)
817 (void)))))
818
819 (for-each-1 x))
820
821 (define (for-each-n x-y)
822
823 (define (for-each-n lsts)
824 (let ((rests (##cdrs lsts)))
825 (if (not rests)
826 (void)
827 (if (pair? rests)
828 (begin
829 (apply proc (##cars lsts '()))
830 (for-each-n rests))
831 (macro-if-checks
832 (if (fx< rests 0)
833 (macro-fail-check-list
834 (fx- (fx+ 2 rests) ##min-fixnum)
835 (for-each proc . x-y))
836 (##raise-length-mismatch-exception
837 (fx+ 2 rests)
838 '()
839 for-each
840 proc
841 x-y))
842 (void))))))
843
844 (for-each-n x-y))
845
846 (if (null? y)
847 (for-each-1 x)
848 (for-each-n (cons x y)))))))
849
850 ;;;----------------------------------------------------------------------------
851
852 ;; R4RS Scheme procedures:
853
854 (define-prim (##list-tail lst k)
855
856 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
857
858 (let loop ((x lst) (i k))
859 (if (fx< 0 i)
860 (loop (cdr x) (fx- i 1))
861 x)))
862
863 (define-prim (list-tail lst k)
864
865 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
866 (namespace ("" list-tail)) ;; but not list-tail to ##list-tail
867
868 (macro-force-vars (k)
869 (macro-check-index k 2 (list-tail lst k)
870 (let loop ((x lst) (i k))
871 (if (fx< 0 i)
872 (macro-force-vars (x)
873 (macro-check-pair x 1 (list-tail lst k);;TODO: error message confusing?
874 (loop (cdr x) (fx- i 1))))
875 x)))))
876
877 ;;;----------------------------------------------------------------------------
878
879 ;; SRFI-1 procedures:
880
881 (define-prim (##xcons d a)
882
883 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
884
885 (cons a d))
886
887 (define-prim (xcons d a)
888
889 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
890
891 (cons a d))
892
893 (define-prim (##cons*-aux x rest)
894
895 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
896
897 (if (pair? rest)
898 (let loop ((x x) (probe rest))
899 (let ((y (car probe))
900 (tail (cdr probe)))
901 (set-car! probe x)
902 (if (pair? tail)
903 (loop y tail)
904 (begin
905 (set-cdr! probe y)
906 rest))))
907 x))
908
909 (define-prim (##cons* x . rest)
910 (##cons*-aux x rest))
911
912 (define-prim (cons* x . rest)
913 (##cons*-aux x rest))
914
915 (define-prim (##make-list n #!optional (fill 0))
916
917 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
918
919 (let loop ((i n) (result '()))
920 (if (fx> i 0)
921 (loop (fx- i 1) (cons fill result))
922 result)))
923
924 (define-prim (make-list n #!optional (fill (macro-absent-obj)))
925
926 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
927 (namespace ("" make-list)) ;; but not make-list to ##make-list
928
929 (macro-force-vars (n fill)
930 (macro-check-index n 1 (make-list n fill)
931 (if (eq? fill (macro-absent-obj))
932 (##make-list n)
933 (##make-list n fill)))))
934
935 (define-prim (##list-tabulate n init-proc)
936
937 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
938
939 (let loop ((i n) (result '()))
940 (if (fx> i 0)
941 (let ((i (fx- i 1)))
942 (loop i (cons (init-proc i) result)))
943 result)))
944
945 (define-prim (list-tabulate n init-proc)
946 (macro-force-vars (n init-proc)
947 (macro-check-index n 1 (list-tabulate n init-proc)
948 (macro-check-procedure init-proc 2 (list-tabulate n init-proc)
949 (##list-tabulate n init-proc)))))
950
951 (define-prim (##proper-list-copy lst)
952
953 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
954
955 (let loop ((lst lst) (rev-result '()))
956 (macro-force-vars (lst)
957 (if (pair? lst)
958 (loop (cdr lst) (cons (car lst) rev-result))
959 (and (null? lst)
960 (reverse! rev-result))))))
961
962 (define-prim (##list-copy lst)
963
964 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
965
966 (let loop ((lst lst) (rev-result '()))
967 (macro-force-vars (lst)
968 (if (pair? lst)
969 (loop (cdr lst) (cons (car lst) rev-result))
970 (append-reverse! rev-result lst)))))
971
972 (define-prim (list-copy lst)
973 (##list-copy lst))
974
975 (define-prim (##circular-list x . rest)
976
977 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
978
979 (let ((result (cons x rest)))
980 (set-cdr! (last-pair result) result)
981 result))
982
983 (define-prim (circular-list x . rest)
984
985 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
986
987 (let ((result (cons x rest)))
988 (set-cdr! (last-pair result) result)
989 result))
990
991 (define-prim (##iota count #!optional (start 0) (step 1))
992
993 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
994 (namespace ("" step)) ;; but not step to ##step
995
996 (if (and (eqv? step 1)
997 (fixnum? start)
998 (##fx+? (fx- count 1) start))
999
1000 (let loop ((i count) (result '()))
1001 (if (fx> i 0)
1002 (let ((i (fx- i 1)))
1003 (loop i (cons (fx+ start i) result)))
1004 result))
1005
1006 (let loop ((i count) (result '()))
1007 (if (fx> i 0)
1008 (let ((i (fx- i 1)))
1009 (loop i (cons (+ start (* step i)) result)))
1010 result))))
1011
1012 (define-prim (iota count
1013 #!optional
1014 (start (macro-absent-obj))
1015 (step (macro-absent-obj)))
1016
1017 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1018 (namespace ("" iota step)) ;; but not iota to ##iota, and step to ##step
1019
1020 (macro-force-vars (count start step)
1021 (macro-check-index count 1 (iota count start step)
1022 (if (eq? start (macro-absent-obj))
1023 (##iota count 0 1)
1024 (if (not (number? start))
1025 (##fail-check-number 2 iota count start step)
1026 (if (eq? step (macro-absent-obj))
1027 (##iota count start 1)
1028 (if (not (number? step))
1029 (##fail-check-number 3 iota count start step)
1030 (##iota count start step))))))))
1031
1032 (define-prim (##take x i)
1033
1034 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1035
1036 (let loop ((probe x)
1037 (j i)
1038 (rev-result '()))
1039 (if (fx> j 0)
1040 (loop (cdr probe)
1041 (fx- j 1)
1042 (cons (car probe) rev-result))
1043 (reverse! rev-result))))
1044
1045 (define-prim (take x i)
1046
1047 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1048 (namespace ("" take)) ;; but not take to ##take
1049
1050 (macro-force-vars (i)
1051 (macro-check-index i 2 (take x i)
1052 (let loop ((probe x)
1053 (j i)
1054 (rev-result '()))
1055 (if (fx> j 0)
1056 (macro-force-vars (probe)
1057 (macro-check-pair probe 1 (take x i)
1058 (loop (cdr probe)
1059 (fx- j 1)
1060 (cons (car probe) rev-result))))
1061 (reverse! rev-result))))))
1062
1063 (define-prim (##drop x i)
1064
1065 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1066
1067 (let loop ((probe x)
1068 (j i))
1069 (if (fx> j 0)
1070 (loop (cdr probe)
1071 (fx- j 1))
1072 probe)))
1073
1074 (define-prim (drop x i)
1075
1076 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1077 (namespace ("" drop)) ;; but not drop to ##drop
1078
1079 (macro-force-vars (i)
1080 (macro-check-index i 2 (drop x i)
1081 (let loop ((probe x)
1082 (j i))
1083 (if (fx> j 0)
1084 (macro-force-vars (probe)
1085 (macro-check-pair probe 1 (drop x i)
1086 (loop (cdr probe)
1087 (fx- j 1))))
1088 probe)))))
1089
1090 (define-prim (##last-pair lst)
1091
1092 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1093
1094 (let loop ((lst lst))
1095 (let ((tail (cdr lst)))
1096 (if (pair? tail)
1097 (loop tail)
1098 lst))))
1099
1100 (define-prim (last-pair lst)
1101
1102 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1103 (namespace ("" last-pair)) ;; but not last-pair to ##last-pair
1104
1105 (macro-force-vars (lst)
1106 (macro-check-pair lst 1 (last-pair lst)
1107 (let loop ((lst lst))
1108 (let ((tail (cdr lst)))
1109 (macro-force-vars (tail)
1110 (if (pair? tail)
1111 (loop tail)
1112 lst)))))))
1113
1114 (define-prim (##last lst)
1115
1116 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1117
1118 (car (##last-pair lst)))
1119
1120 (define-prim (last lst)
1121
1122 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1123 (namespace ("" last)) ;; but not last to ##last
1124
1125 (macro-force-vars (lst)
1126 (macro-check-pair lst 1 (last lst)
1127 (let loop ((lst lst))
1128 (let ((tail (cdr lst)))
1129 (macro-force-vars (tail)
1130 (if (pair? tail)
1131 (loop tail)
1132 (car lst))))))))
1133
1134 (define-prim (##butlast lst)
1135
1136 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1137
1138 (define (butlast lst)
1139 (if (pair? (cdr lst))
1140 (cons (car lst) (butlast (cdr lst)))
1141 '()))
1142
1143 (butlast lst))
1144
1145 ;; ##reverse! and ##append-reverse! defined in _kernel.scm
1146
1147 (define-prim (reverse! lst)
1148
1149 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1150 (namespace ("" reverse!)) ;; but not reverse! to ##reverse!
1151
1152 (let loop ((prev '()) (curr lst))
1153 (macro-force-vars (curr)
1154 (if (pair? curr)
1155 (let ((next (cdr curr)))
1156 (set-cdr! curr prev)
1157 (loop curr next))
1158 (macro-check-list curr 1 (reverse! lst)
1159 prev)))))
1160
1161 (define-prim (append-reverse lst tail)
1162
1163 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1164 (namespace ("" append-reverse)) ;; but not append-reverse to ##append-reverse
1165
1166 (let loop ((x lst) (result '()))
1167 (macro-force-vars (x)
1168 (if (pair? x)
1169 (loop (cdr x) (cons (car x) result))
1170 (macro-check-list x 1 (append-reverse lst tail)
1171 result)))))
1172
1173 (define-prim (append-reverse! lst tail)
1174
1175 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1176 (namespace ("" append-reverse!)) ;; but not append-reverse! to ##append-reverse!
1177
1178 (let loop ((prev tail) (curr lst))
1179 (macro-force-vars (curr)
1180 (if (pair? curr)
1181 (let ((next (cdr curr)))
1182 (set-cdr! curr prev)
1183 (loop curr next))
1184 (macro-check-list curr 1 (append-reverse! lst tail)
1185 prev)))))
1186
1187 (define-prim (##fold proc base lst)
1188
1189 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1190
1191 (let loop ((r base) (x lst))
1192 (if (pair? x)
1193 (loop (proc (car x) r)
1194 (cdr x))
1195 r)))
1196
1197 (define-prim (fold proc base x . y)
1198
1199 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1200 (namespace ("" fold)) ;; but not fold to ##fold
1201
1202 (macro-force-vars (proc)
1203 (macro-check-procedure proc 1 (fold proc base x . y)
1204 (let ()
1205
1206 (define (fold-1 x)
1207
1208 (define (fold-1 r lst1)
1209 (macro-force-vars (lst1)
1210 (if (pair? lst1)
1211 (fold-1 (proc (car lst1) r)
1212 (cdr lst1))
1213 (macro-check-list lst1 3 (fold proc base x)
1214 r))))
1215
1216 (fold-1 base x))
1217
1218 (define (fold-n x-y)
1219
1220 (define (fold-n r lsts)
1221 (let ((rests (##cdrs lsts)))
1222 (if (not rests)
1223 r
1224 (if (pair? rests)
1225 (fold-n (apply proc (##cars lsts (list r)))
1226 rests)
1227 (macro-if-checks
1228 (if (fx< rests 0)
1229 (macro-fail-check-list
1230 (fx- (fx+ 3 rests) ##min-fixnum)
1231 (fold proc base . x-y))
1232 (##raise-length-mismatch-exception
1233 (fx+ 3 rests)
1234 '()
1235 fold
1236 proc
1237 base
1238 x-y))
1239 r)))))
1240
1241 (fold-n base x-y))
1242
1243 (if (null? y)
1244 (fold-1 x)
1245 (fold-n (cons x y)))))))
1246
1247 (define-prim (##fold-right proc base lst)
1248
1249 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1250
1251 (define (fold-right x)
1252 (if (pair? x)
1253 (proc (car x)
1254 (fold-right (cdr x)))
1255 base))
1256
1257 (fold-right lst))
1258
1259 (define-prim (fold-right proc base x . y)
1260
1261 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1262 (namespace ("" fold-right)) ;; but not fold-right to ##fold-right
1263
1264 (macro-force-vars (proc)
1265 (macro-check-procedure proc 1 (fold-right proc base x . y)
1266 (let ()
1267
1268 (define (fold-right-1 x)
1269
1270 (define (fold-right-1 lst1)
1271 (macro-force-vars (lst1)
1272 (if (pair? lst1)
1273 (let ((tail (fold-right-1 (cdr lst1))))
1274 (macro-if-checks
1275 (and tail
1276 (list (proc (car lst1) (car tail))))
1277 (proc (car lst1) tail)))
1278 (macro-if-checks
1279 (if (null? lst1)
1280 (list base)
1281 #f)
1282 (list base)))))
1283
1284 (macro-if-checks
1285 (let ((result (fold-right-1 x)))
1286 (if result
1287 (car result)
1288 (macro-fail-check-list
1289 3
1290 (fold-right proc base x))))
1291 (fold-right-1 x)))
1292
1293 (define (fold-right-n x-y)
1294
1295 (define (fold-right-n lsts)
1296 (let ((rests (##cdrs lsts)))
1297 (if (not rests)
1298 (macro-if-checks
1299 (list base)
1300 base)
1301 (if (pair? rests)
1302 (let ((tail (fold-right-n rests)))
1303 (macro-if-checks
1304 (if (fixnum? tail)
1305 tail
1306 (list (apply proc (##cars lsts tail))))
1307 (apply proc (##cars lsts (list tail)))))
1308 (macro-if-checks
1309 rests
1310 base)))))
1311
1312 (macro-if-checks
1313 (let ((result (fold-right-n x-y)))
1314 (if (fixnum? result)
1315 (if (fx< result 0)
1316 (macro-fail-check-list
1317 (fx- (fx+ 3 result) ##min-fixnum)
1318 (fold-right proc base . x-y))
1319 (##raise-length-mismatch-exception
1320 (fx+ 3 result)
1321 '()
1322 fold-right
1323 proc
1324 base
1325 x-y))
1326 (car result)))
1327 (fold-right-n x-y)))
1328
1329 (if (null? y)
1330 (fold-right-1 x)
1331 (fold-right-n (cons x y)))))))
1332
1333 ;;;----------------------------------------------------------------------------
1334
1335 ;;; Sorting.
1336
1337 (define-prim (##list-sort! proc lst)
1338
1339 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1340
1341 ;; Stable mergesort algorithm
1342
1343 (define (sort lst len)
1344 (if (fx= len 1)
1345 (begin
1346 (set-cdr! lst '())
1347 lst)
1348 (let ((len1 (fxarithmetic-shift-right len 1)))
1349 (let loop ((n len1) (tail lst))
1350 (if (fx> n 0)
1351 (loop (fx- n 1) (cdr tail))
1352 (let ((x (sort tail (fx- len len1))))
1353 (merge (sort lst len1) x)))))))
1354
1355 (define (merge lst1 lst2)
1356 (if (pair? lst1)
1357 (if (pair? lst2)
1358 (let ((x1 (car lst1))
1359 (x2 (car lst2)))
1360 (if (proc x2 x1)
1361 (merge-loop lst2 lst2 lst1 (cdr lst2))
1362 (merge-loop lst1 lst1 (cdr lst1) lst2)))
1363 lst1)
1364 lst2))
1365
1366 (define (merge-loop result prev lst1 lst2)
1367 (if (pair? lst1)
1368 (if (pair? lst2)
1369 (let ((x1 (car lst1))
1370 (x2 (car lst2)))
1371 (if (proc x2 x1)
1372 (begin
1373 (set-cdr! prev lst2)
1374 (merge-loop result lst2 lst1 (cdr lst2)))
1375 (begin
1376 (set-cdr! prev lst1)
1377 (merge-loop result lst1 (cdr lst1) lst2))))
1378 (begin
1379 (set-cdr! prev lst1)
1380 result))
1381 (begin
1382 (set-cdr! prev lst2)
1383 result)))
1384
1385 (let ((len (##proper-list-length lst)))
1386 (and len
1387 (if (fx= len 0)
1388 '()
1389 (sort lst len)))))
1390
1391 (define-prim (##list-sort proc lst)
1392 (##list-sort! proc (##list-copy lst)))
1393
1394 (define-prim (list-sort proc lst)
1395
1396 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1397 (namespace ("" list-sort)) ;; but not list-sort to ##list-sort
1398
1399 (macro-force-vars (proc)
1400 (macro-check-procedure proc 1 (list-sort proc lst)
1401 (macro-if-checks
1402 (let ((lst-copy (##proper-list-copy lst)))
1403 (if lst-copy
1404 (##list-sort! proc lst-copy)
1405 (macro-fail-check-list
1406 2
1407 (list-sort proc lst))))
1408 (##list-sort! proc (##list-copy lst))))))
1409
1410 (define-prim (list-sort! proc lst)
1411
1412 (include "~~lib/gambit/prim/prim#.scm") ;; map fx+ to ##fx+, etc
1413 (namespace ("" list-sort!)) ;; but not list-sort! to ##list-sort!
1414
1415 (macro-force-vars (proc)
1416 (macro-check-procedure proc 1 (list-sort! proc lst)
1417 (let ((result (##list-sort! proc lst)))
1418 (or result
1419 (macro-fail-check-list
1420 2
1421 (list-sort! proc lst)))))))
1422
1423 ;;;============================================================================