Artifact 6034df3ff363f653befe99f7c489a881db0e0726:
- File srfi/s42/design.scm — part of check-in [80c8c83034] at 2016-07-07 18:11:39 on branch trunk — initial import (user: ovenpasta@pizzahack.eu size: 12282)
0000: 3b 20 3c 50 4c 41 49 4e 54 45 58 54 3e 0a 3b 20 ; <PLAINTEXT>.; 0010: 44 65 73 69 67 6e 20 41 6c 74 65 72 6e 61 74 69 Design Alternati 0020: 76 65 73 20 66 6f 72 20 45 61 67 65 72 20 43 6f ves for Eager Co 0030: 6d 70 72 65 68 65 6e 73 69 6f 6e 73 0a 3b 20 3d mprehensions.; = 0040: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0050: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0060: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 0a 3b 0a 3b 20 ===========.;.; 0070: 73 65 62 61 73 74 69 61 6e 2e 65 67 6e 65 72 40 sebastian.egner@ 0080: 70 68 69 6c 69 70 73 2e 63 6f 6d 2c 20 45 69 6e philips.com, Ein 0090: 64 68 6f 76 65 6e 2c 20 54 68 65 20 4e 65 74 68 dhoven, The Neth 00a0: 65 72 6c 61 6e 64 73 2c 20 46 65 62 2d 32 30 30 erlands, Feb-200 00b0: 33 2e 0a 3b 20 53 63 68 65 6d 65 20 52 35 52 53 3..; Scheme R5RS 00c0: 20 28 69 6e 63 6c 2e 20 6d 61 63 72 6f 73 29 2c (incl. macros), 00d0: 20 53 52 46 49 2d 32 33 20 28 65 72 72 6f 72 29 SRFI-23 (error) 00e0: 2e 0a 3b 0a 3b 20 54 68 69 73 20 66 69 6c 65 20 ..;.; This file 00f0: 63 6f 6e 74 61 69 6e 73 20 69 6d 70 6c 65 6d 65 contains impleme 0100: 6e 74 61 74 69 6f 6e 20 61 6c 74 65 72 6e 61 74 ntation alternat 0110: 69 76 65 73 20 66 6f 72 20 65 61 67 65 72 20 63 ives for eager c 0120: 6f 6d 70 72 65 68 65 6e 73 69 6f 6e 73 0a 3b 20 omprehensions.; 0130: 61 6e 64 20 65 78 61 6d 70 6c 65 73 20 74 6f 20 and examples to 0140: 66 69 6e 64 20 6f 75 74 20 77 68 69 63 68 20 69 find out which i 0150: 73 20 62 65 74 74 65 72 20 73 75 69 74 65 64 20 s better suited 0160: 66 6f 72 20 61 20 70 61 72 74 69 63 75 6c 61 72 for a particular 0170: 20 73 79 73 74 65 6d 2e 0a 3b 0a 3b 20 4c 6f 61 system..;.; Loa 0180: 64 69 6e 67 20 74 68 65 20 61 6c 74 65 72 6e 61 ding the alterna 0190: 74 69 76 65 73 20 69 6e 20 53 63 68 65 6d 65 34 tives in Scheme4 01a0: 38 20 28 76 65 72 73 69 6f 6e 20 30 2e 35 37 29 8 (version 0.57) 01b0: 3a 0a 3b 20 20 20 2c 6f 70 65 6e 20 73 72 66 69 :.; ,open srfi 01c0: 2d 32 33 0a 3b 20 20 20 2c 6c 6f 61 64 20 65 63 -23.; ,load ec 01d0: 2e 73 63 6d 0a 3b 20 20 20 2c 6c 6f 61 64 20 64 .scm.; ,load d 01e0: 65 73 69 67 6e 2e 73 63 6d 0a 3b 0a 3b 20 4c 6f esign.scm.;.; Lo 01f0: 61 64 69 6e 67 20 74 68 65 20 61 6c 74 65 72 6e ading the altern 0200: 61 74 69 76 65 73 20 69 6e 20 50 4c 54 2f 44 72 atives in PLT/Dr 0210: 53 63 68 65 6d 65 20 28 76 65 72 73 69 6f 6e 20 Scheme (version 0220: 32 30 32 29 3a 20 0a 3b 20 20 20 3b 20 6f 70 65 202): .; ; ope 0230: 6e 20 22 65 63 2e 73 63 6d 22 2c 20 63 6c 69 63 n "ec.scm", clic 0240: 6b 20 45 78 65 63 75 74 65 0a 3b 20 20 20 28 6c k Execute.; (l 0250: 6f 61 64 20 22 64 65 73 69 67 6e 2e 73 63 6d 22 oad "design.scm" 0260: 29 0a 3b 0a 3b 20 4c 6f 61 64 69 6e 67 20 74 68 ).;.; Loading th 0270: 65 20 61 6c 74 65 72 6e 61 74 69 76 65 73 20 69 e alternatives i 0280: 6e 20 53 43 4d 20 28 76 65 72 73 69 6f 6e 20 35 n SCM (version 5 0290: 64 37 29 3a 0a 3b 20 20 20 3b 20 69 6e 76 6f 6b d7):.; ; invok 02a0: 65 20 53 43 4d 20 77 69 74 68 20 2d 76 20 6f 6e e SCM with -v on 02b0: 20 74 68 65 20 63 6f 6d 6d 61 6e 64 20 6c 69 6e the command lin 02c0: 65 0a 3b 20 20 20 28 72 65 71 75 69 72 65 20 27 e.; (require ' 02d0: 6d 61 63 72 6f 29 20 28 72 65 71 75 69 72 65 20 macro) (require 02e0: 27 72 65 63 6f 72 64 29 0a 3b 20 20 20 28 6c 6f 'record).; (lo 02f0: 61 64 20 22 65 63 2e 73 63 6d 22 29 0a 3b 20 20 ad "ec.scm").; 0300: 20 28 6c 6f 61 64 20 22 64 65 73 69 67 6e 2e 73 (load "design.s 0310: 63 6d 22 29 0a 0a 0a 3b 20 3d 3d 3d 3d 3d 3d 3d cm")...; ======= 0320: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0330: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0340: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0350: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0360: 0a 3b 20 6c 69 73 74 2d 65 63 0a 3b 20 3d 3d 3d .; list-ec.; === 0370: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0380: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0390: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 03a0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 03b0: 3d 3d 3d 3d 0a 0a 3b 20 6c 69 73 74 2d 65 63 31 ====..; list-ec1 03c0: 0a 3b 20 20 20 75 73 65 73 20 72 65 76 65 72 73 .; uses revers 03d0: 65 20 61 6e 64 20 66 6f 6c 64 2d 65 63 20 69 6e e and fold-ec in 03e0: 20 74 68 65 20 6f 62 76 69 6f 75 73 20 77 61 79 the obvious way 03f0: 2e 0a 3b 20 20 20 20 20 2b 20 6f 6e 65 2d 6c 69 ..; + one-li 0400: 6e 65 72 0a 3b 20 20 20 20 20 2b 20 72 65 76 65 ner.; + reve 0410: 72 73 65 20 63 6f 75 6c 64 20 61 6c 6c 6f 63 61 rse could alloca 0420: 74 65 20 72 65 73 75 6c 74 20 63 6f 6e 74 69 67 te result contig 0430: 75 6f 75 73 0a 3b 20 20 20 20 20 2d 20 72 65 73 uous.; - res 0440: 75 6c 74 69 6e 67 20 6c 69 73 74 20 69 73 20 61 ulting list is a 0450: 6c 6c 6f 63 61 74 65 64 20 74 77 69 63 65 20 28 llocated twice ( 0460: 75 6e 6c 65 73 73 20 72 65 76 65 72 73 65 21 20 unless reverse! 0470: 69 73 20 75 73 65 64 29 0a 0a 28 64 65 66 69 6e is used)..(defin 0480: 65 2d 73 79 6e 74 61 78 20 6c 69 73 74 2d 65 63 e-syntax list-ec 0490: 31 0a 20 20 28 73 79 6e 74 61 78 2d 72 75 6c 65 1. (syntax-rule 04a0: 73 20 28 29 0a 20 20 20 20 28 28 6c 69 73 74 2d s (). ((list- 04b0: 65 63 20 65 74 63 31 20 65 74 63 20 2e 2e 2e 29 ec etc1 etc ...) 04c0: 0a 20 20 20 20 20 28 72 65 76 65 72 73 65 20 28 . (reverse ( 04d0: 66 6f 6c 64 2d 65 63 20 27 28 29 20 65 74 63 31 fold-ec '() etc1 04e0: 20 65 74 63 20 2e 2e 2e 20 63 6f 6e 73 29 29 20 etc ... cons)) 04f0: 29 29 29 0a 0a 0a 3b 20 6c 69 73 74 2d 65 63 32 )))...; list-ec2 0500: 0a 3b 20 20 20 75 73 65 73 20 73 65 74 2d 63 64 .; uses set-cd 0510: 72 21 20 61 70 70 65 6e 64 69 6e 67 20 61 74 20 r! appending at 0520: 74 68 65 20 65 6e 64 20 6f 66 20 74 68 65 20 72 the end of the r 0530: 65 73 75 6c 74 2e 0a 3b 20 20 20 20 20 2b 20 6e esult..; + n 0540: 6f 20 63 6f 70 79 69 6e 67 20 6f 66 20 74 68 65 o copying of the 0550: 20 72 65 73 75 6c 74 0a 3b 20 20 20 20 20 2d 20 result.; - 0560: 6d 6f 72 65 20 62 6f 6f 6b 2d 6b 65 65 70 69 6e more book-keepin 0570: 67 20 69 6e 20 74 68 65 20 69 6e 6e 65 72 20 6c g in the inner l 0580: 6f 6f 70 0a 0a 28 64 65 66 69 6e 65 2d 73 79 6e oop..(define-syn 0590: 74 61 78 20 6c 69 73 74 2d 65 63 32 0a 20 20 28 tax list-ec2. ( 05a0: 73 79 6e 74 61 78 2d 72 75 6c 65 73 20 28 6e 65 syntax-rules (ne 05b0: 73 74 65 64 29 0a 20 20 20 20 28 28 6c 69 73 74 sted). ((list 05c0: 2d 65 63 32 20 28 6e 65 73 74 65 64 20 71 31 20 -ec2 (nested q1 05d0: 2e 2e 2e 29 20 71 20 65 74 63 31 20 65 74 63 20 ...) q etc1 etc 05e0: 2e 2e 2e 29 0a 20 20 20 20 20 28 6c 69 73 74 2d ...). (list- 05f0: 65 63 32 20 28 6e 65 73 74 65 64 20 71 31 20 2e ec2 (nested q1 . 0600: 2e 2e 20 71 29 20 65 74 63 31 20 65 74 63 20 2e .. q) etc1 etc . 0610: 2e 2e 29 20 29 0a 20 20 20 20 28 28 6c 69 73 74 ..) ). ((list 0620: 2d 65 63 32 20 71 31 20 71 32 20 20 20 20 20 20 -ec2 q1 q2 0630: 20 20 20 20 20 20 20 65 74 63 31 20 65 74 63 20 etc1 etc 0640: 2e 2e 2e 29 0a 20 20 20 20 20 28 6c 69 73 74 2d ...). (list- 0650: 65 63 32 20 28 6e 65 73 74 65 64 20 71 31 20 71 ec2 (nested q1 q 0660: 32 29 20 20 20 20 65 74 63 31 20 65 74 63 20 2e 2) etc1 etc . 0670: 2e 2e 29 20 29 0a 20 20 20 20 28 28 6c 69 73 74 ..) ). ((list 0680: 2d 65 63 32 20 65 78 70 72 65 73 73 69 6f 6e 29 -ec2 expression) 0690: 0a 20 20 20 20 20 28 6c 69 73 74 2d 65 63 32 20 . (list-ec2 06a0: 28 6e 65 73 74 65 64 29 20 65 78 70 72 65 73 73 (nested) express 06b0: 69 6f 6e 29 20 29 0a 0a 20 20 20 20 28 28 6c 69 ion) ).. ((li 06c0: 73 74 2d 65 63 32 20 71 75 61 6c 69 66 69 65 72 st-ec2 qualifier 06d0: 20 65 78 70 72 65 73 73 69 6f 6e 29 0a 20 20 20 expression). 06e0: 20 20 28 6c 65 74 20 28 28 72 65 73 75 6c 74 20 (let ((result 06f0: 23 66 29 20 28 74 61 69 6c 20 28 6c 69 73 74 20 #f) (tail (list 0700: 23 66 29 29 29 0a 20 20 20 20 20 20 20 28 73 65 #f))). (se 0710: 74 21 20 72 65 73 75 6c 74 20 74 61 69 6c 29 0a t! result tail). 0720: 20 20 20 20 20 20 20 28 64 6f 2d 65 63 20 71 75 (do-ec qu 0730: 61 6c 69 66 69 65 72 0a 20 20 20 20 20 20 20 20 alifier. 0740: 20 20 20 20 20 20 28 62 65 67 69 6e 20 28 73 65 (begin (se 0750: 74 2d 63 64 72 21 20 74 61 69 6c 20 28 6c 69 73 t-cdr! tail (lis 0760: 74 20 65 78 70 72 65 73 73 69 6f 6e 29 29 0a 20 t expression)). 0770: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 0780: 20 20 20 20 28 73 65 74 21 20 74 61 69 6c 20 28 (set! tail ( 0790: 63 64 72 20 74 61 69 6c 29 29 20 29 29 0a 20 20 cdr tail)) )). 07a0: 20 20 20 20 20 28 63 64 72 20 72 65 73 75 6c 74 (cdr result 07b0: 29 20 29 29 29 29 0a 0a 0a 3b 20 63 6f 6d 70 61 ) ))))...; compa 07c0: 72 69 73 6f 6e 0a 3b 20 20 20 2a 20 54 68 65 20 rison.; * The 07d0: 74 72 61 64 65 2d 6f 66 66 20 69 73 20 62 6f 6f trade-off is boo 07e0: 6b 2d 6b 65 65 70 69 6e 67 20 6f 76 65 72 68 65 k-keeping overhe 07f0: 61 64 20 76 73 2e 20 61 6c 6c 6f 63 61 74 69 6f ad vs. allocatio 0800: 6e 20 70 72 65 73 73 75 72 65 2e 0a 3b 20 20 20 n pressure..; 0810: 20 20 54 68 65 20 64 69 66 66 65 72 65 6e 63 65 The difference 0820: 20 69 6e 20 74 68 65 20 69 6e 6e 65 72 20 6c 6f in the inner lo 0830: 6f 70 20 69 73 20 28 73 65 74 2d 63 64 72 21 2c op is (set-cdr!, 0840: 20 6c 69 73 74 2c 20 73 65 74 21 29 20 76 73 2e list, set!) vs. 0850: 0a 3b 20 20 20 20 20 28 73 65 74 21 2c 20 63 6f .; (set!, co 0860: 6e 73 29 2c 20 74 68 65 20 64 69 66 66 65 72 65 ns), the differe 0870: 6e 63 65 20 0a 3b 20 20 20 2a 20 53 63 68 65 6d nce .; * Schem 0880: 65 34 38 20 30 2e 35 37 3a 20 6c 69 73 74 2d 65 e48 0.57: list-e 0890: 63 31 20 73 65 65 6d 73 20 35 25 20 70 65 72 63 c1 seems 5% perc 08a0: 65 6e 74 20 66 61 73 74 65 72 20 74 68 61 6e 20 ent faster than 08b0: 6c 69 73 74 2d 65 63 32 2e 0a 3b 20 20 20 2a 20 list-ec2..; * 08c0: 50 4c 54 20 32 30 32 3a 20 6c 69 73 74 2d 65 63 PLT 202: list-ec 08d0: 31 20 73 65 65 6d 73 20 32 35 25 20 66 61 73 74 1 seems 25% fast 08e0: 65 72 20 74 68 61 6e 20 74 68 61 6e 20 6c 69 73 er than than lis 08f0: 74 2d 65 63 32 2e 0a 0a 28 64 65 66 69 6e 65 20 t-ec2...(define 0900: 28 70 65 72 66 2d 6c 69 73 74 2d 65 63 31 20 69 (perf-list-ec1 i 0910: 74 65 72 61 74 69 6f 6e 73 20 6e 29 0a 20 20 28 terations n). ( 0920: 64 6f 2d 65 63 20 28 3a 72 61 6e 67 65 20 69 20 do-ec (:range i 0930: 69 74 65 72 61 74 69 6f 6e 73 29 20 0a 20 20 20 iterations) . 0940: 20 20 20 20 20 20 28 6c 69 73 74 2d 65 63 31 20 (list-ec1 0950: 28 3a 72 61 6e 67 65 20 6b 20 6e 29 20 6b 29 20 (:range k n) k) 0960: 29 29 0a 0a 28 64 65 66 69 6e 65 20 28 70 65 72 ))..(define (per 0970: 66 2d 6c 69 73 74 2d 65 63 32 20 69 74 65 72 61 f-list-ec2 itera 0980: 74 69 6f 6e 73 20 6e 29 0a 20 20 28 64 6f 2d 65 tions n). (do-e 0990: 63 20 28 3a 72 61 6e 67 65 20 69 20 69 74 65 72 c (:range i iter 09a0: 61 74 69 6f 6e 73 29 20 0a 20 20 20 20 20 20 20 ations) . 09b0: 20 20 28 6c 69 73 74 2d 65 63 32 20 28 3a 72 61 (list-ec2 (:ra 09c0: 6e 67 65 20 6b 20 6e 29 20 6b 29 20 29 29 0a 0a nge k n) k) )).. 09d0: 3b 20 74 72 79 3a 0a 3b 20 20 20 28 70 65 72 66 ; try:.; (perf 09e0: 2d 6c 69 73 74 2d 65 63 31 20 31 30 30 30 30 30 -list-ec1 100000 09f0: 20 31 30 29 0a 3b 20 20 20 28 70 65 72 66 2d 6c 10).; (perf-l 0a00: 69 73 74 2d 65 63 32 20 31 30 30 30 30 30 20 31 ist-ec2 100000 1 0a10: 30 29 0a 3b 20 20 20 28 70 65 72 66 2d 6c 69 73 0).; (perf-lis 0a20: 74 2d 65 63 31 20 31 30 30 20 31 30 30 30 30 29 t-ec1 100 10000) 0a30: 0a 3b 20 20 20 28 70 65 72 66 2d 6c 69 73 74 2d .; (perf-list- 0a40: 65 63 32 20 31 30 30 20 31 30 30 30 30 29 0a 0a ec2 100 10000).. 0a50: 0a 3b 20 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d .; ============= 0a60: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0a70: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0a80: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0a90: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 0a 3b 20 73 74 72 ==========.; str 0aa0: 69 6e 67 2d 65 63 0a 3b 20 3d 3d 3d 3d 3d 3d 3d ing-ec.; ======= 0ab0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0ac0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0ad0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0ae0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 0af0: 0a 0a 3b 20 73 74 72 69 6e 67 2d 65 63 31 0a 3b ..; string-ec1.; 0b00: 20 20 20 75 73 65 73 20 6c 69 73 74 2d 3e 73 74 uses list->st 0b10: 72 69 6e 67 20 61 6e 64 20 6c 69 73 74 2d 65 63 ring and list-ec 0b20: 20 69 6e 20 74 68 65 20 6f 62 76 69 6f 75 73 20 in the obvious 0b30: 77 61 79 2e 0a 3b 20 20 20 20 20 2b 20 6f 6e 65 way..; + one 0b40: 2d 6c 69 6e 65 72 0a 3b 20 20 20 20 20 2d 20 69 -liner.; - i 0b50: 6e 74 65 72 6d 65 64 69 61 74 65 20 6c 69 73 74 ntermediate list 0b60: 20 69 73 20 6d 75 63 68 20 62 69 67 67 65 72 20 is much bigger 0b70: 74 68 61 6e 20 72 65 73 75 6c 74 0a 3b 20 20 20 than result.; 0b80: 20 20 2d 20 69 6e 68 65 72 69 74 73 20 6f 76 65 - inherits ove 0b90: 72 68 65 61 64 20 6f 66 20 6c 69 73 74 2d 65 63 rhead of list-ec 0ba0: 0a 0a 28 64 65 66 69 6e 65 2d 73 79 6e 74 61 78 ..(define-syntax 0bb0: 20 73 74 72 69 6e 67 2d 65 63 31 0a 20 20 28 73 string-ec1. (s 0bc0: 79 6e 74 61 78 2d 72 75 6c 65 73 20 28 29 0a 20 yntax-rules (). 0bd0: 20 20 20 28 28 73 74 72 69 6e 67 2d 65 63 31 20 ((string-ec1 0be0: 65 74 63 31 20 65 74 63 20 2e 2e 2e 29 0a 20 20 etc1 etc ...). 0bf0: 20 20 20 28 6c 69 73 74 2d 3e 73 74 72 69 6e 67 (list->string 0c00: 20 28 6c 69 73 74 2d 65 63 20 65 74 63 31 20 65 (list-ec etc1 e 0c10: 74 63 20 2e 2e 2e 29 29 20 29 29 29 0a 0a 0a 3b tc ...)) )))...; 0c20: 20 73 74 72 69 6e 67 2d 65 63 32 0a 3b 20 20 20 string-ec2.; 0c30: 75 73 65 73 20 73 74 72 69 6e 67 2d 61 70 70 65 uses string-appe 0c40: 6e 64 20 6f 6e 20 70 69 65 63 65 73 20 6f 66 20 nd on pieces of 0c50: 74 68 65 20 72 65 73 75 6c 74 20 6f 66 20 6c 69 the result of li 0c60: 6d 69 74 65 64 20 6c 65 6e 67 74 68 3b 0a 3b 20 mited length;.; 0c70: 20 20 70 69 65 63 65 73 20 61 72 65 20 63 6f 6e pieces are con 0c80: 73 74 72 75 63 74 65 64 20 77 69 74 68 20 74 68 structed with th 0c90: 65 20 6d 65 74 68 6f 64 20 6f 66 20 73 74 72 69 e method of stri 0ca0: 6e 67 2d 65 63 31 0a 3b 20 20 20 20 20 2b 20 73 ng-ec1.; + s 0cb0: 70 61 63 65 2d 65 66 66 69 63 69 65 6e 74 20 66 pace-efficient f 0cc0: 6f 72 20 6c 6f 6e 67 20 72 65 73 75 6c 74 73 0a or long results. 0cd0: 3b 20 20 20 20 20 2d 20 6f 76 65 72 68 65 61 64 ; - overhead 0ce0: 20 66 6f 72 20 73 68 6f 72 74 20 72 65 73 75 6c for short resul 0cf0: 74 0a 3b 20 20 20 20 20 2b 20 70 6f 74 65 6e 74 t.; + potent 0d00: 69 61 6c 6c 79 20 76 65 72 79 20 65 66 66 69 63 ially very effic 0d10: 69 65 6e 74 20 69 6e 20 6e 61 74 69 76 65 20 63 ient in native c 0d20: 6f 64 65 0a 3b 20 20 20 20 20 2d 20 6d 6f 72 65 ode.; - more 0d30: 20 63 6f 6d 70 6c 69 63 61 74 65 64 20 62 6f 6f complicated boo 0d40: 6b 2d 6b 65 65 70 69 6e 67 0a 0a 28 64 65 66 69 k-keeping..(defi 0d50: 6e 65 2d 73 79 6e 74 61 78 20 73 74 72 69 6e 67 ne-syntax string 0d60: 2d 65 63 32 0a 20 20 28 73 79 6e 74 61 78 2d 72 -ec2. (syntax-r 0d70: 75 6c 65 73 20 28 29 0a 20 20 20 20 28 28 73 74 ules (). ((st 0d80: 72 69 6e 67 2d 65 63 32 20 28 6e 65 73 74 65 64 ring-ec2 (nested 0d90: 20 71 31 20 2e 2e 2e 29 20 71 20 65 74 63 31 20 q1 ...) q etc1 0da0: 65 74 63 20 2e 2e 2e 29 0a 20 20 20 20 20 28 73 etc ...). (s 0db0: 74 72 69 6e 67 2d 65 63 32 20 28 6e 65 73 74 65 tring-ec2 (neste 0dc0: 64 20 71 31 20 2e 2e 2e 20 71 29 20 65 74 63 31 d q1 ... q) etc1 0dd0: 20 65 74 63 20 2e 2e 2e 29 20 29 0a 20 20 20 20 etc ...) ). 0de0: 28 28 73 74 72 69 6e 67 2d 65 63 32 20 71 31 20 ((string-ec2 q1 0df0: 71 32 20 20 20 20 20 20 20 20 20 20 20 20 20 65 q2 e 0e00: 74 63 31 20 65 74 63 20 2e 2e 2e 29 0a 20 20 20 tc1 etc ...). 0e10: 20 20 28 73 74 72 69 6e 67 2d 65 63 32 20 28 6e (string-ec2 (n 0e20: 65 73 74 65 64 20 71 31 20 71 32 29 20 20 20 20 ested q1 q2) 0e30: 65 74 63 31 20 65 74 63 20 2e 2e 2e 29 20 29 0a etc1 etc ...) ). 0e40: 20 20 20 20 28 28 73 74 72 69 6e 67 2d 65 63 32 ((string-ec2 0e50: 20 65 78 70 72 65 73 73 69 6f 6e 29 0a 20 20 20 expression). 0e60: 20 20 28 73 74 72 69 6e 67 2d 65 63 32 20 28 6e (string-ec2 (n 0e70: 65 73 74 65 64 29 20 65 78 70 72 65 73 73 69 6f ested) expressio 0e80: 6e 29 20 29 0a 0a 20 20 20 20 28 28 73 74 72 69 n) ).. ((stri 0e90: 6e 67 2d 65 63 32 20 71 75 61 6c 69 66 69 65 72 ng-ec2 qualifier 0ea0: 20 65 78 70 72 65 73 73 69 6f 6e 29 0a 20 20 20 expression). 0eb0: 20 20 28 6c 65 74 20 28 28 72 65 73 75 6c 74 20 (let ((result 0ec0: 27 28 29 29 20 28 70 69 65 63 65 20 27 28 29 29 '()) (piece '()) 0ed0: 20 28 6c 65 6e 20 30 29 20 28 6d 61 78 2d 6c 65 (len 0) (max-le 0ee0: 6e 20 31 30 30 30 29 29 0a 20 20 20 20 20 20 20 n 1000)). 0ef0: 28 64 6f 2d 65 63 20 71 75 61 6c 69 66 69 65 72 (do-ec qualifier 0f00: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28 . ( 0f10: 62 65 67 69 6e 20 0a 20 20 20 20 20 20 20 20 20 begin . 0f20: 20 20 20 20 20 20 20 28 73 65 74 21 20 70 69 65 (set! pie 0f30: 63 65 20 28 63 6f 6e 73 20 65 78 70 72 65 73 73 ce (cons express 0f40: 69 6f 6e 20 70 69 65 63 65 29 29 0a 20 20 20 20 ion piece)). 0f50: 20 20 20 20 20 20 20 20 20 20 20 20 28 73 65 74 (set 0f60: 21 20 6c 65 6e 20 28 2b 20 6c 65 6e 20 31 29 29 ! len (+ len 1)) 0f70: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 . 0f80: 20 28 69 66 20 28 3d 20 6c 65 6e 20 6d 61 78 2d (if (= len max- 0f90: 6c 65 6e 29 0a 20 20 20 20 20 20 20 20 20 20 20 len). 0fa0: 20 20 20 20 20 20 20 20 20 28 62 65 67 69 6e 20 (begin 0fb0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 . 0fc0: 20 20 20 20 20 20 20 28 73 65 74 21 20 72 65 73 (set! res 0fd0: 75 6c 74 20 28 63 6f 6e 73 20 28 6c 69 73 74 2d ult (cons (list- 0fe0: 3e 73 74 72 69 6e 67 20 70 69 65 63 65 29 20 72 >string piece) r 0ff0: 65 73 75 6c 74 29 29 0a 20 20 20 20 20 20 20 20 esult)). 1000: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 28 73 (s 1010: 65 74 21 20 70 69 65 63 65 20 27 28 29 29 0a 20 et! piece '()). 1020: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 1030: 20 20 20 20 20 28 73 65 74 21 20 6c 65 6e 20 30 (set! len 0 1040: 29 20 29 29 29 29 0a 20 20 20 20 20 20 20 28 61 ) )))). (a 1050: 70 70 6c 79 20 73 74 72 69 6e 67 2d 61 70 70 65 pply string-appe 1060: 6e 64 20 0a 20 20 20 20 20 20 20 20 20 20 20 20 nd . 1070: 20 20 28 72 65 76 65 72 73 65 20 28 63 6f 6e 73 (reverse (cons 1080: 20 28 6c 69 73 74 2d 3e 73 74 72 69 6e 67 20 70 (list->string p 1090: 69 65 63 65 29 20 72 65 73 75 6c 74 29 29 20 29 iece) result)) ) 10a0: 29 29 29 29 0a 0a 0a 3b 20 63 6f 6d 70 61 72 69 ))))...; compari 10b0: 73 6f 6e 0a 3b 20 20 20 2a 20 54 68 65 20 6d 61 son.; * The ma 10c0: 69 6e 20 71 75 65 73 74 69 6f 6e 20 69 73 20 77 in question is w 10d0: 68 65 74 68 65 72 20 74 68 65 20 73 70 61 63 65 hether the space 10e0: 20 6f 76 65 72 68 65 61 64 20 66 6f 72 20 61 6e overhead for an 10f0: 20 69 6e 74 65 72 6d 65 64 69 61 74 65 0a 3b 20 intermediate.; 1100: 20 20 20 20 6c 69 73 74 20 69 73 20 61 63 63 65 list is acce 1110: 70 74 61 62 6c 65 2e 20 49 66 20 6e 6f 74 2c 20 ptable. If not, 1120: 73 74 72 69 6e 67 2d 65 63 31 20 69 73 20 6e 6f string-ec1 is no 1130: 20 6f 70 74 69 6f 6e 2e 0a 3b 20 20 20 2a 20 49 option..; * I 1140: 66 20 73 74 72 69 6e 67 2d 65 63 32 20 69 73 20 f string-ec2 is 1150: 75 73 65 64 2c 20 74 68 65 20 71 75 65 73 74 69 used, the questi 1160: 6f 6e 20 69 73 20 68 6f 77 20 74 6f 20 61 64 6a on is how to adj 1170: 75 73 74 20 6d 61 78 2d 6c 65 6e 2e 20 49 74 0a ust max-len. It. 1180: 3b 20 20 20 20 20 63 61 6e 20 65 69 74 68 65 72 ; can either 1190: 20 62 65 20 75 73 65 64 20 61 73 20 61 6e 20 65 be used as an e 11a0: 6d 65 72 67 65 6e 63 79 20 62 72 61 6b 65 20 66 mergency brake f 11b0: 6f 72 20 76 65 72 79 20 6c 6f 6e 67 20 69 6e 74 or very long int 11c0: 65 72 6d 65 64 69 61 74 65 0a 3b 20 20 20 20 20 ermediate.; 11d0: 6c 69 73 74 73 20 6f 72 20 69 74 20 63 61 6e 20 lists or it can 11e0: 62 65 20 75 73 65 64 20 74 6f 20 6b 65 65 70 20 be used to keep 11f0: 74 68 65 20 74 6f 74 61 6c 20 6f 76 65 72 68 65 the total overhe 1200: 61 64 20 6c 69 6d 69 74 65 64 2e 0a 3b 20 20 20 ad limited..; 1210: 2a 20 53 63 68 65 6d 65 34 38 20 30 2e 35 37 3a * Scheme48 0.57: 1220: 20 73 74 72 69 6e 67 2d 65 63 31 20 69 73 20 32 string-ec1 is 2 1230: 35 25 20 66 61 73 74 65 72 20 74 68 61 6e 20 73 5% faster than s 1240: 74 72 69 6e 67 2d 65 63 32 20 66 6f 72 20 73 68 tring-ec2 for sh 1250: 6f 72 74 20 0a 3b 20 20 20 20 20 20 20 72 65 73 ort .; res 1260: 75 6c 74 73 20 61 6e 64 20 73 74 69 6c 6c 20 31 ults and still 1 1270: 35 25 20 66 61 73 74 65 72 20 66 6f 72 20 73 74 5% faster for st 1280: 72 69 6e 67 73 20 6f 66 20 6c 65 6e 67 74 68 20 rings of length 1290: 31 30 5e 35 2e 20 48 6f 77 65 76 65 72 2c 20 0a 10^5. However, . 12a0: 3b 20 20 20 20 20 20 20 61 74 20 31 30 5e 36 20 ; at 10^6 12b0: 28 66 6f 72 20 6d 79 20 74 65 73 74 20 63 6f 6e (for my test con 12c0: 66 69 67 75 72 61 74 69 6f 6e 29 20 73 74 72 69 figuration) stri 12d0: 6e 67 2d 65 63 31 20 68 61 73 20 27 68 65 61 70 ng-ec1 has 'heap 12e0: 20 6f 76 65 72 66 6c 6f 77 27 2c 0a 3b 20 20 20 overflow',.; 12f0: 20 20 20 20 77 68 65 72 65 61 73 20 73 74 72 69 whereas stri 1300: 6e 67 2d 65 63 32 20 68 61 73 20 6e 6f 20 70 72 ng-ec2 has no pr 1310: 6f 62 6c 65 6d 2e 0a 3b 20 20 20 2a 20 50 4c 54 oblem..; * PLT 1320: 20 32 30 32 3a 20 73 74 72 69 6e 67 2d 65 63 31 202: string-ec1 1330: 20 69 73 20 35 30 25 2e 2e 37 30 25 20 66 61 73 is 50%..70% fas 1340: 74 65 72 20 74 68 61 6e 20 73 74 72 69 6e 67 2d ter than string- 1350: 65 63 32 2c 20 62 6f 74 68 20 66 6f 72 20 0a 3b ec2, both for .; 1360: 20 20 20 20 20 20 20 73 68 6f 72 74 20 61 6e 64 short and 1370: 20 66 6f 72 20 6c 6f 6e 67 20 73 74 72 69 6e 67 for long string 1380: 73 2e 0a 0a 28 64 65 66 69 6e 65 20 28 70 65 72 s...(define (per 1390: 66 2d 73 74 72 69 6e 67 2d 65 63 31 20 69 74 65 f-string-ec1 ite 13a0: 72 61 74 69 6f 6e 73 20 6e 29 0a 20 20 28 64 6f rations n). (do 13b0: 2d 65 63 20 28 3a 72 61 6e 67 65 20 69 20 69 74 -ec (:range i it 13c0: 65 72 61 74 69 6f 6e 73 29 20 0a 20 20 20 20 20 erations) . 13d0: 20 20 20 20 28 73 74 72 69 6e 67 2d 65 63 31 20 (string-ec1 13e0: 28 3a 72 61 6e 67 65 20 6b 20 6e 29 20 23 5c 61 (:range k n) #\a 13f0: 29 20 29 29 0a 0a 28 64 65 66 69 6e 65 20 28 70 ) ))..(define (p 1400: 65 72 66 2d 73 74 72 69 6e 67 2d 65 63 32 20 69 erf-string-ec2 i 1410: 74 65 72 61 74 69 6f 6e 73 20 6e 29 0a 20 20 28 terations n). ( 1420: 64 6f 2d 65 63 20 28 3a 72 61 6e 67 65 20 69 20 do-ec (:range i 1430: 69 74 65 72 61 74 69 6f 6e 73 29 20 0a 20 20 20 iterations) . 1440: 20 20 20 20 20 20 28 73 74 72 69 6e 67 2d 65 63 (string-ec 1450: 32 20 28 3a 72 61 6e 67 65 20 6b 20 6e 29 20 23 2 (:range k n) # 1460: 5c 61 29 20 29 29 0a 0a 3b 20 74 72 79 3a 0a 3b \a) ))..; try:.; 1470: 20 20 20 28 70 65 72 66 2d 73 74 72 69 6e 67 2d (perf-string- 1480: 65 63 31 20 31 30 30 30 30 30 20 31 30 29 0a 3b ec1 100000 10).; 1490: 20 20 20 28 70 65 72 66 2d 73 74 72 69 6e 67 2d (perf-string- 14a0: 65 63 32 20 31 30 30 30 30 30 20 31 30 29 0a 3b ec2 100000 10).; 14b0: 20 20 20 28 70 65 72 66 2d 73 74 72 69 6e 67 2d (perf-string- 14c0: 65 63 31 20 31 30 20 31 30 30 30 30 30 29 0a 3b ec1 10 100000).; 14d0: 20 20 20 28 70 65 72 66 2d 73 74 72 69 6e 67 2d (perf-string- 14e0: 65 63 32 20 31 30 20 31 30 30 30 30 30 29 0a 3b ec2 10 100000).; 14f0: 20 20 20 28 70 65 72 66 2d 73 74 72 69 6e 67 2d (perf-string- 1500: 65 63 31 20 31 20 31 30 30 30 30 30 30 29 0a 3b ec1 1 1000000).; 1510: 20 20 20 28 70 65 72 66 2d 73 74 72 69 6e 67 2d (perf-string- 1520: 65 63 32 20 31 20 31 30 30 30 30 30 30 29 0a 0a ec2 1 1000000).. 1530: 0a 3b 20 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d .; ============= 1540: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 1550: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 1560: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 1570: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 0a 3b 20 66 69 72 ==========.; fir 1580: 73 74 2d 65 63 0a 3b 20 3d 3d 3d 3d 3d 3d 3d 3d st-ec.; ======== 1590: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 15a0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 15b0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 15c0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 0a ===============. 15d0: 0a 3b 20 66 69 72 73 74 2d 65 63 31 0a 3b 20 20 .; first-ec1.; 15e0: 20 75 73 65 73 20 61 20 6e 6f 6e 2d 6c 6f 63 61 uses a non-loca 15f0: 6c 20 65 78 69 74 20 63 6f 6e 73 74 72 75 63 74 l exit construct 1600: 65 64 20 62 79 20 63 61 6c 6c 2d 77 69 74 68 2d ed by call-with- 1610: 63 75 72 72 65 6e 74 2d 63 6f 6e 74 69 6e 75 61 current-continua 1620: 74 69 6f 6e 2e 0a 3b 20 20 20 20 20 2d 20 73 74 tion..; - st 1630: 61 63 6b 2d 62 61 73 65 64 20 53 63 68 65 6d 65 ack-based Scheme 1640: 73 20 68 61 76 65 20 70 72 6f 62 6c 65 6d 73 20 s have problems 1650: 69 6d 70 6c 65 6d 65 6e 74 69 6e 67 20 74 68 69 implementing thi 1660: 73 20 65 66 66 69 63 69 65 6e 74 6c 79 0a 3b 20 s efficiently.; 1670: 20 20 20 20 2b 20 73 69 6d 70 6c 65 2c 20 73 74 + simple, st 1680: 72 61 69 67 68 74 2d 66 6f 72 77 61 72 64 2c 20 raight-forward, 1690: 73 63 68 65 6d 65 69 73 68 0a 0a 28 64 65 66 69 schemeish..(defi 16a0: 6e 65 2d 73 79 6e 74 61 78 20 66 69 72 73 74 2d ne-syntax first- 16b0: 65 63 31 0a 20 20 28 73 79 6e 74 61 78 2d 72 75 ec1. (syntax-ru 16c0: 6c 65 73 20 28 6e 65 73 74 65 64 29 0a 20 20 20 les (nested). 16d0: 20 28 28 66 69 72 73 74 2d 65 63 31 20 64 65 66 ((first-ec1 def 16e0: 61 75 6c 74 20 28 6e 65 73 74 65 64 20 71 31 20 ault (nested q1 16f0: 2e 2e 2e 29 20 71 20 65 74 63 31 20 65 74 63 20 ...) q etc1 etc 1700: 2e 2e 2e 29 0a 20 20 20 20 20 28 66 69 72 73 74 ...). (first 1710: 2d 65 63 31 20 64 65 66 61 75 6c 74 20 28 6e 65 -ec1 default (ne 1720: 73 74 65 64 20 71 31 20 2e 2e 2e 20 71 29 20 65 sted q1 ... q) e 1730: 74 63 31 20 65 74 63 20 2e 2e 2e 29 20 29 0a 20 tc1 etc ...) ). 1740: 20 20 20 28 28 66 69 72 73 74 2d 65 63 31 20 64 ((first-ec1 d 1750: 65 66 61 75 6c 74 20 71 31 20 71 32 20 20 20 20 efault q1 q2 1760: 20 20 20 20 20 20 20 20 20 65 74 63 31 20 65 74 etc1 et 1770: 63 20 2e 2e 2e 29 0a 20 20 20 20 20 28 66 69 72 c ...). (fir 1780: 73 74 2d 65 63 31 20 64 65 66 61 75 6c 74 20 28 st-ec1 default ( 1790: 6e 65 73 74 65 64 20 71 31 20 71 32 29 20 20 20 nested q1 q2) 17a0: 20 65 74 63 31 20 65 74 63 20 2e 2e 2e 29 20 29 etc1 etc ...) ) 17b0: 0a 20 20 20 20 28 28 66 69 72 73 74 2d 65 63 31 . ((first-ec1 17c0: 20 64 65 66 61 75 6c 74 20 65 78 70 72 65 73 73 default express 17d0: 69 6f 6e 29 0a 20 20 20 20 20 28 66 69 72 73 74 ion). (first 17e0: 2d 65 63 31 20 64 65 66 61 75 6c 74 20 28 6e 65 -ec1 default (ne 17f0: 73 74 65 64 29 20 65 78 70 72 65 73 73 69 6f 6e sted) expression 1800: 29 20 29 0a 0a 20 20 20 20 28 28 66 69 72 73 74 ) ).. ((first 1810: 2d 65 63 31 20 64 65 66 61 75 6c 74 20 71 75 61 -ec1 default qua 1820: 6c 69 66 69 65 72 20 65 78 70 72 65 73 73 69 6f lifier expressio 1830: 6e 29 0a 20 20 20 20 20 28 63 61 6c 6c 2d 77 69 n). (call-wi 1840: 74 68 2d 63 75 72 72 65 6e 74 2d 63 6f 6e 74 69 th-current-conti 1850: 6e 75 61 74 69 6f 6e 20 0a 20 20 20 20 20 20 28 nuation . ( 1860: 6c 61 6d 62 64 61 20 28 63 63 29 0a 20 20 20 20 lambda (cc). 1870: 20 20 20 20 28 64 6f 2d 65 63 20 71 75 61 6c 69 (do-ec quali 1880: 66 69 65 72 20 28 63 63 20 65 78 70 72 65 73 73 fier (cc express 1890: 69 6f 6e 29 29 0a 20 20 20 20 20 20 20 20 64 65 ion)). de 18a0: 66 61 75 6c 74 20 29 29 29 29 29 0a 0a 0a 3b 20 fault )))))...; 18b0: 66 69 72 73 74 2d 65 63 32 0a 3b 20 20 20 75 73 first-ec2.; us 18c0: 65 73 20 3a 75 6e 74 69 6c 20 74 6f 20 61 64 64 es :until to add 18d0: 20 61 6e 20 65 61 72 6c 79 20 74 65 72 6d 69 6e an early termin 18e0: 61 74 69 6f 6e 20 74 6f 20 65 61 63 68 20 67 65 ation to each ge 18f0: 6e 65 72 61 74 6f 72 2e 0a 3b 20 20 20 20 20 2b nerator..; + 1900: 20 61 73 20 66 61 73 74 20 61 73 20 69 74 20 67 as fast as it g 1910: 65 74 73 0a 3b 20 20 20 20 20 2d 20 63 6f 70 69 ets.; - copi 1920: 65 73 20 70 61 72 74 20 6f 66 20 74 68 65 20 66 es part of the f 1930: 75 6e 63 74 69 6f 6e 61 6c 69 74 79 20 6f 66 20 unctionality of 1940: 64 6f 2d 65 63 20 0a 0a 28 64 65 66 69 6e 65 2d do-ec ..(define- 1950: 73 79 6e 74 61 78 20 66 69 72 73 74 2d 65 63 32 syntax first-ec2 1960: 0a 20 20 28 73 79 6e 74 61 78 2d 72 75 6c 65 73 . (syntax-rules 1970: 20 28 6e 65 73 74 65 64 29 0a 20 20 20 20 28 28 (nested). (( 1980: 66 69 72 73 74 2d 65 63 32 20 64 65 66 61 75 6c first-ec2 defaul 1990: 74 20 28 6e 65 73 74 65 64 20 71 31 20 2e 2e 2e t (nested q1 ... 19a0: 29 20 71 20 65 74 63 31 20 65 74 63 20 2e 2e 2e ) q etc1 etc ... 19b0: 29 0a 20 20 20 20 20 28 66 69 72 73 74 2d 65 63 ). (first-ec 19c0: 32 20 64 65 66 61 75 6c 74 20 28 6e 65 73 74 65 2 default (neste 19d0: 64 20 71 31 20 2e 2e 2e 20 71 29 20 65 74 63 31 d q1 ... q) etc1 19e0: 20 65 74 63 20 2e 2e 2e 29 20 29 0a 20 20 20 20 etc ...) ). 19f0: 28 28 66 69 72 73 74 2d 65 63 32 20 64 65 66 61 ((first-ec2 defa 1a00: 75 6c 74 20 71 31 20 71 32 20 20 20 20 20 20 20 ult q1 q2 1a10: 20 20 20 20 20 20 65 74 63 31 20 65 74 63 20 2e etc1 etc . 1a20: 2e 2e 29 0a 20 20 20 20 20 28 66 69 72 73 74 2d ..). (first- 1a30: 65 63 32 20 64 65 66 61 75 6c 74 20 28 6e 65 73 ec2 default (nes 1a40: 74 65 64 20 71 31 20 71 32 29 20 20 20 20 65 74 ted q1 q2) et 1a50: 63 31 20 65 74 63 20 2e 2e 2e 29 20 29 0a 20 20 c1 etc ...) ). 1a60: 20 20 28 28 66 69 72 73 74 2d 65 63 32 20 64 65 ((first-ec2 de 1a70: 66 61 75 6c 74 20 65 78 70 72 65 73 73 69 6f 6e fault expression 1a80: 29 0a 20 20 20 20 20 28 66 69 72 73 74 2d 65 63 ). (first-ec 1a90: 32 20 64 65 66 61 75 6c 74 20 28 6e 65 73 74 65 2 default (neste 1aa0: 64 29 20 65 78 70 72 65 73 73 69 6f 6e 29 20 29 d) expression) ) 1ab0: 0a 0a 20 20 20 20 28 28 66 69 72 73 74 2d 65 63 .. ((first-ec 1ac0: 32 20 64 65 66 61 75 6c 74 20 71 75 61 6c 69 66 2 default qualif 1ad0: 69 65 72 20 65 78 70 72 65 73 73 69 6f 6e 29 0a ier expression). 1ae0: 20 20 20 20 20 28 6c 65 74 20 28 28 72 65 73 75 (let ((resu 1af0: 6c 74 20 64 65 66 61 75 6c 74 29 20 28 73 74 6f lt default) (sto 1b00: 70 20 23 66 29 29 0a 20 20 20 20 20 20 20 28 65 p #f)). (e 1b10: 63 2d 67 75 61 72 64 65 64 2d 64 6f 2d 65 63 20 c-guarded-do-ec 1b20: 0a 20 20 20 20 20 20 20 20 20 73 74 6f 70 20 0a . stop . 1b30: 20 20 20 20 20 20 20 20 20 28 6e 65 73 74 65 64 (nested 1b40: 20 71 75 61 6c 69 66 69 65 72 29 0a 20 20 20 20 qualifier). 1b50: 20 20 20 20 20 28 62 65 67 69 6e 20 28 73 65 74 (begin (set 1b60: 21 20 72 65 73 75 6c 74 20 65 78 70 72 65 73 73 ! result express 1b70: 69 6f 6e 29 0a 20 20 20 20 20 20 20 20 20 20 20 ion). 1b80: 20 20 20 20 20 28 73 65 74 21 20 73 74 6f 70 20 (set! stop 1b90: 23 74 29 20 29 29 0a 20 20 20 20 20 20 20 72 65 #t) )). re 1ba0: 73 75 6c 74 20 29 29 29 29 0a 0a 3b 20 28 65 63 sult ))))..; (ec 1bb0: 2d 67 75 61 72 64 65 64 2d 64 6f 2d 65 63 20 73 -guarded-do-ec s 1bc0: 74 6f 70 20 28 6e 65 73 74 65 64 20 71 20 2e 2e top (nested q .. 1bd0: 2e 29 20 63 6d 64 29 0a 3b 20 20 20 63 6f 6e 73 .) cmd).; cons 1be0: 74 72 75 63 74 73 20 28 64 6f 2d 65 63 20 71 20 tructs (do-ec q 1bf0: 2e 2e 2e 20 63 6d 64 29 20 77 68 65 72 65 20 74 ... cmd) where t 1c00: 68 65 20 67 65 6e 65 72 61 74 6f 72 73 20 67 65 he generators ge 1c10: 6e 20 69 6e 20 71 20 2e 2e 2e 20 61 72 65 0a 3b n in q ... are.; 1c20: 20 20 20 72 65 70 6c 61 63 65 64 20 62 79 20 28 replaced by ( 1c30: 3a 75 6e 74 69 6c 20 67 65 6e 20 73 74 6f 70 29 :until gen stop) 1c40: 2e 0a 0a 28 64 65 66 69 6e 65 2d 73 79 6e 74 61 ...(define-synta 1c50: 78 20 65 63 2d 67 75 61 72 64 65 64 2d 64 6f 2d x ec-guarded-do- 1c60: 65 63 0a 20 20 28 73 79 6e 74 61 78 2d 72 75 6c ec. (syntax-rul 1c70: 65 73 20 28 6e 65 73 74 65 64 20 69 66 20 6e 6f es (nested if no 1c80: 74 20 61 6e 64 20 6f 72 20 62 65 67 69 6e 29 0a t and or begin). 1c90: 0a 20 20 20 20 28 28 65 63 2d 67 75 61 72 64 65 . ((ec-guarde 1ca0: 64 2d 64 6f 2d 65 63 20 73 74 6f 70 20 28 6e 65 d-do-ec stop (ne 1cb0: 73 74 65 64 20 28 6e 65 73 74 65 64 20 71 31 20 sted (nested q1 1cc0: 2e 2e 2e 29 20 71 32 20 2e 2e 2e 29 20 63 6d 64 ...) q2 ...) cmd 1cd0: 29 0a 20 20 20 20 20 28 65 63 2d 67 75 61 72 64 ). (ec-guard 1ce0: 65 64 2d 64 6f 2d 65 63 20 73 74 6f 70 20 28 6e ed-do-ec stop (n 1cf0: 65 73 74 65 64 20 71 31 20 2e 2e 2e 20 71 32 20 ested q1 ... q2 1d00: 2e 2e 2e 29 20 63 6d 64 29 20 29 0a 0a 20 20 20 ...) cmd) ).. 1d10: 20 28 28 65 63 2d 67 75 61 72 64 65 64 2d 64 6f ((ec-guarded-do 1d20: 2d 65 63 20 73 74 6f 70 20 28 6e 65 73 74 65 64 -ec stop (nested 1d30: 20 28 69 66 20 74 65 73 74 29 20 71 20 2e 2e 2e (if test) q ... 1d40: 29 20 63 6d 64 29 0a 20 20 20 20 20 28 69 66 20 ) cmd). (if 1d50: 74 65 73 74 20 28 65 63 2d 67 75 61 72 64 65 64 test (ec-guarded 1d60: 2d 64 6f 2d 65 63 20 73 74 6f 70 20 28 6e 65 73 -do-ec stop (nes 1d70: 74 65 64 20 71 20 2e 2e 2e 29 20 63 6d 64 29 29 ted q ...) cmd)) 1d80: 20 29 0a 20 20 20 20 28 28 65 63 2d 67 75 61 72 ). ((ec-guar 1d90: 64 65 64 2d 64 6f 2d 65 63 20 73 74 6f 70 20 28 ded-do-ec stop ( 1da0: 6e 65 73 74 65 64 20 28 6e 6f 74 20 74 65 73 74 nested (not test 1db0: 29 20 71 20 2e 2e 2e 29 20 63 6d 64 29 0a 20 20 ) q ...) cmd). 1dc0: 20 20 20 28 69 66 20 28 6e 6f 74 20 74 65 73 74 (if (not test 1dd0: 29 20 28 65 63 2d 67 75 61 72 64 65 64 2d 64 6f ) (ec-guarded-do 1de0: 2d 65 63 20 73 74 6f 70 20 28 6e 65 73 74 65 64 -ec stop (nested 1df0: 20 71 20 2e 2e 2e 29 20 63 6d 64 29 29 20 29 0a q ...) cmd)) ). 1e00: 20 20 20 20 28 28 65 63 2d 67 75 61 72 64 65 64 ((ec-guarded 1e10: 2d 64 6f 2d 65 63 20 73 74 6f 70 20 28 6e 65 73 -do-ec stop (nes 1e20: 74 65 64 20 28 61 6e 64 20 74 65 73 74 20 2e 2e ted (and test .. 1e30: 2e 29 20 71 20 2e 2e 2e 29 20 63 6d 64 29 0a 20 .) q ...) cmd). 1e40: 20 20 20 20 28 69 66 20 28 61 6e 64 20 74 65 73 (if (and tes 1e50: 74 20 2e 2e 2e 29 20 28 65 63 2d 67 75 61 72 64 t ...) (ec-guard 1e60: 65 64 2d 64 6f 2d 65 63 20 73 74 6f 70 20 28 6e ed-do-ec stop (n 1e70: 65 73 74 65 64 20 71 20 2e 2e 2e 29 20 63 6d 64 ested q ...) cmd 1e80: 29 29 20 29 0a 20 20 20 20 28 28 65 63 2d 67 75 )) ). ((ec-gu 1e90: 61 72 64 65 64 2d 64 6f 2d 65 63 20 73 74 6f 70 arded-do-ec stop 1ea0: 20 28 6e 65 73 74 65 64 20 28 6f 72 20 74 65 73 (nested (or tes 1eb0: 74 20 2e 2e 2e 29 20 71 20 2e 2e 2e 29 20 63 6d t ...) q ...) cm 1ec0: 64 29 0a 20 20 20 20 20 28 69 66 20 28 6f 72 20 d). (if (or 1ed0: 74 65 73 74 20 2e 2e 2e 29 20 28 65 63 2d 67 75 test ...) (ec-gu 1ee0: 61 72 64 65 64 2d 64 6f 2d 65 63 20 73 74 6f 70 arded-do-ec stop 1ef0: 20 28 6e 65 73 74 65 64 20 71 20 2e 2e 2e 29 20 (nested q ...) 1f00: 63 6d 64 29 29 20 29 0a 0a 20 20 20 20 28 28 65 cmd)) ).. ((e 1f10: 63 2d 67 75 61 72 64 65 64 2d 64 6f 2d 65 63 20 c-guarded-do-ec 1f20: 73 74 6f 70 20 28 6e 65 73 74 65 64 20 28 62 65 stop (nested (be 1f30: 67 69 6e 20 65 74 63 20 2e 2e 2e 29 20 71 20 2e gin etc ...) q . 1f40: 2e 2e 29 20 63 6d 64 29 0a 20 20 20 20 20 28 62 ..) cmd). (b 1f50: 65 67 69 6e 20 65 74 63 20 2e 2e 2e 20 28 65 63 egin etc ... (ec 1f60: 2d 67 75 61 72 64 65 64 2d 64 6f 2d 65 63 20 73 -guarded-do-ec s 1f70: 74 6f 70 20 28 6e 65 73 74 65 64 20 71 20 2e 2e top (nested q .. 1f80: 2e 29 20 63 6d 64 29 29 20 29 0a 0a 20 20 20 20 .) cmd)) ).. 1f90: 28 28 65 63 2d 67 75 61 72 64 65 64 2d 64 6f 2d ((ec-guarded-do- 1fa0: 65 63 20 73 74 6f 70 20 28 6e 65 73 74 65 64 20 ec stop (nested 1fb0: 67 65 6e 20 71 20 2e 2e 2e 29 20 63 6d 64 29 0a gen q ...) cmd). 1fc0: 20 20 20 20 20 28 64 6f 2d 65 63 20 0a 20 20 20 (do-ec . 1fd0: 20 20 20 20 28 3a 75 6e 74 69 6c 20 67 65 6e 20 (:until gen 1fe0: 73 74 6f 70 29 20 0a 20 20 20 20 20 20 20 28 65 stop) . (e 1ff0: 63 2d 67 75 61 72 64 65 64 2d 64 6f 2d 65 63 20 c-guarded-do-ec 2000: 73 74 6f 70 20 28 6e 65 73 74 65 64 20 71 20 2e stop (nested q . 2010: 2e 2e 29 20 63 6d 64 29 20 29 29 0a 0a 20 20 20 ..) cmd) )).. 2020: 20 28 28 65 63 2d 67 75 61 72 64 65 64 2d 64 6f ((ec-guarded-do 2030: 2d 65 63 20 73 74 6f 70 20 28 6e 65 73 74 65 64 -ec stop (nested 2040: 29 20 63 6d 64 29 0a 20 20 20 20 20 28 64 6f 2d ) cmd). (do- 2050: 65 63 20 63 6d 64 29 20 29 29 29 0a 0a 0a 3b 20 ec cmd) )))...; 2060: 63 6f 6d 70 61 72 69 73 6f 6e 0a 3b 20 20 20 2a comparison.; * 2070: 20 54 68 65 20 6d 61 69 6e 20 71 75 65 73 74 69 The main questi 2080: 6f 6e 20 69 73 20 77 68 65 74 68 65 72 20 63 61 on is whether ca 2090: 6c 6c 2f 63 63 20 69 73 20 65 66 66 69 63 69 65 ll/cc is efficie 20a0: 6e 74 20 68 65 72 65 2e 0a 3b 20 20 20 20 20 49 nt here..; I 20b0: 66 20 69 74 20 69 73 20 6e 6f 74 2c 20 66 69 72 f it is not, fir 20c0: 73 74 2d 65 63 31 20 69 73 20 6e 6f 74 20 61 6e st-ec1 is not an 20d0: 20 6f 70 74 69 6f 6e 2e 0a 3b 20 20 20 2a 20 57 option..; * W 20e0: 65 20 73 69 6d 70 6c 79 20 72 75 6e 20 61 20 6c e simply run a l 20f0: 6f 6f 70 20 74 65 72 6d 69 6e 61 74 69 6e 67 20 oop terminating 2100: 61 66 74 65 72 20 61 20 66 65 77 20 69 74 65 72 after a few iter 2110: 61 74 69 6f 6e 73 20 61 6e 64 20 0a 3b 20 20 20 ations and .; 2120: 20 20 6d 65 61 73 75 72 65 20 74 68 65 20 74 69 measure the ti 2130: 6d 65 20 69 74 20 74 61 6b 65 73 20 69 6e 20 74 me it takes in t 2140: 6f 74 61 6c 2e 0a 3b 20 20 20 2a 20 53 63 68 65 otal..; * Sche 2150: 6d 65 34 38 20 30 2e 35 37 3a 20 66 69 72 73 74 me48 0.57: first 2160: 2d 65 63 32 20 73 65 65 6d 73 20 74 6f 20 62 65 -ec2 seems to be 2170: 20 61 62 6f 75 74 20 31 35 25 20 66 61 73 74 65 about 15% faste 2180: 72 20 74 68 61 6e 20 66 69 72 73 74 2d 65 63 31 r than first-ec1 2190: 2e 0a 3b 20 20 20 2a 20 50 4c 54 20 32 30 32 3a ..; * PLT 202: 21a0: 20 66 69 72 73 74 2d 65 63 32 20 73 65 65 6d 73 first-ec2 seems 21b0: 20 74 6f 20 62 65 20 61 62 6f 75 74 20 66 61 63 to be about fac 21c0: 74 6f 72 20 34 20 66 61 73 74 65 72 20 74 68 61 tor 4 faster tha 21d0: 6e 20 66 69 72 73 74 2d 65 63 31 2e 0a 0a 28 64 n first-ec1...(d 21e0: 65 66 69 6e 65 20 28 70 65 72 66 2d 66 69 72 73 efine (perf-firs 21f0: 74 2d 65 63 31 20 69 74 65 72 61 74 69 6f 6e 73 t-ec1 iterations 2200: 29 0a 20 20 28 64 6f 2d 65 63 20 28 3a 72 61 6e ). (do-ec (:ran 2210: 67 65 20 69 20 69 74 65 72 61 74 69 6f 6e 73 29 ge i iterations) 2220: 20 0a 20 20 20 20 20 20 20 20 20 28 66 69 72 73 . (firs 2230: 74 2d 65 63 31 20 30 20 28 3a 72 61 6e 67 65 20 t-ec1 0 (:range 2240: 78 20 31 30 29 20 28 69 66 20 28 3d 20 78 20 35 x 10) (if (= x 5 2250: 29 29 20 23 74 29 20 29 29 0a 0a 28 64 65 66 69 )) #t) ))..(defi 2260: 6e 65 20 28 70 65 72 66 2d 66 69 72 73 74 2d 65 ne (perf-first-e 2270: 63 32 20 69 74 65 72 61 74 69 6f 6e 73 29 0a 20 c2 iterations). 2280: 20 28 64 6f 2d 65 63 20 28 3a 72 61 6e 67 65 20 (do-ec (:range 2290: 69 20 69 74 65 72 61 74 69 6f 6e 73 29 20 0a 20 i iterations) . 22a0: 20 20 20 20 20 20 20 20 28 66 69 72 73 74 2d 65 (first-e 22b0: 63 32 20 30 20 28 3a 72 61 6e 67 65 20 78 20 31 c2 0 (:range x 1 22c0: 30 29 20 28 69 66 20 28 3d 20 78 20 35 29 29 20 0) (if (= x 5)) 22d0: 23 74 29 20 29 29 0a 0a 3b 20 74 72 79 3a 0a 3b #t) ))..; try:.; 22e0: 20 20 20 28 70 65 72 66 2d 66 69 72 73 74 2d 65 (perf-first-e 22f0: 63 31 20 31 30 30 30 30 30 29 0a 3b 20 20 20 28 c1 100000).; ( 2300: 70 65 72 66 2d 66 69 72 73 74 2d 65 63 32 20 31 perf-first-ec2 1 2310: 30 30 30 30 30 29 0a 0a 0a 3b 20 3d 3d 3d 3d 3d 00000)...; ===== 2320: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 2330: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 2340: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 2350: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 2360: 3d 3d 0a 3b 20 3a 76 65 63 74 6f 72 0a 3b 20 3d ==.; :vector.; = 2370: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 2380: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 2390: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 23a0: 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d 3d ================ 23b0: 3d 3d 3d 3d 3d 3d 0a 0a 0a 3b 20 3a 76 65 63 74 ======...; :vect 23c0: 6f 72 0a 3b 20 20 20 20 75 73 65 73 20 76 65 63 or.; uses vec 23d0: 74 6f 72 2d 3e 6c 69 73 74 2c 20 61 70 70 65 6e tor->list, appen 23e0: 64 20 61 6e 64 20 3a 6c 69 73 74 20 66 6f 72 20 d and :list for 23f0: 74 68 65 20 6d 75 6c 74 69 2d 61 72 67 75 6d 65 the multi-argume 2400: 6e 74 20 63 61 73 65 2e 0a 3b 20 20 20 20 20 20 nt case..; 2410: 2b 20 6f 6e 65 2d 6c 69 6e 65 72 0a 3b 20 20 20 + one-liner.; 2420: 20 20 20 2d 20 74 68 65 20 65 6e 75 6d 65 72 61 - the enumera 2430: 74 65 64 20 73 65 71 75 65 6e 63 65 20 69 73 20 ted sequence is 2440: 63 6f 70 69 65 64 0a 3b 20 20 20 20 20 20 2d 20 copied.; - 2450: 74 68 65 20 69 6e 74 65 72 6d 65 64 69 61 74 65 the intermediate 2460: 20 6c 69 73 74 20 69 73 20 6c 61 72 67 65 72 20 list is larger 2470: 74 68 61 6e 20 74 68 65 20 61 72 67 75 6d 65 6e than the argumen 2480: 74 73 0a 0a 28 64 65 66 69 6e 65 2d 73 79 6e 74 ts..(define-synt 2490: 61 78 20 3a 76 65 63 74 6f 72 31 0a 20 20 28 73 ax :vector1. (s 24a0: 79 6e 74 61 78 2d 72 75 6c 65 73 20 28 69 6e 64 yntax-rules (ind 24b0: 65 78 29 0a 20 20 20 20 28 28 3a 76 65 63 74 6f ex). ((:vecto 24c0: 72 31 20 63 63 20 76 61 72 20 28 69 6e 64 65 78 r1 cc var (index 24d0: 20 69 29 20 61 72 67 29 0a 20 20 20 20 20 28 3a i) arg). (: 24e0: 64 6f 20 63 63 0a 20 20 20 20 20 20 20 20 20 20 do cc. 24f0: 28 6c 65 74 20 28 28 76 65 63 20 61 72 67 29 20 (let ((vec arg) 2500: 28 6c 65 6e 20 30 29 29 20 0a 20 20 20 20 20 20 (len 0)) . 2510: 20 20 20 20 20 20 28 73 65 74 21 20 6c 65 6e 20 (set! len 2520: 28 76 65 63 74 6f 72 2d 6c 65 6e 67 74 68 20 76 (vector-length v 2530: 65 63 29 29 29 0a 20 20 20 20 20 20 20 20 20 20 ec))). 2540: 28 28 69 20 30 29 29 0a 20 20 20 20 20 20 20 20 ((i 0)). 2550: 20 20 28 3c 20 69 20 6c 65 6e 29 0a 20 20 20 20 (< i len). 2560: 20 20 20 20 20 20 28 6c 65 74 20 28 28 76 61 72 (let ((var 2570: 20 28 76 65 63 74 6f 72 2d 72 65 66 20 76 65 63 (vector-ref vec 2580: 20 69 29 29 29 29 0a 20 20 20 20 20 20 20 20 20 i)))). 2590: 20 23 74 0a 20 20 20 20 20 20 20 20 20 20 28 28 #t. (( 25a0: 2b 20 69 20 31 29 29 20 29 29 0a 20 20 20 20 28 + i 1)) )). ( 25b0: 28 3a 76 65 63 74 6f 72 31 20 63 63 20 76 61 72 (:vector1 cc var 25c0: 20 28 69 6e 64 65 78 20 69 29 20 61 72 67 31 20 (index i) arg1 25d0: 61 72 67 32 20 61 72 67 20 2e 2e 2e 29 0a 20 20 arg2 arg ...). 25e0: 20 20 20 28 3a 6c 69 73 74 20 63 63 20 0a 20 20 (:list cc . 25f0: 20 20 20 20 20 20 20 20 20 20 76 61 72 20 0a 20 var . 2600: 20 20 20 20 20 20 20 20 20 20 20 28 69 6e 64 65 (inde 2610: 78 20 69 29 20 0a 20 20 20 20 20 20 20 20 20 20 x i) . 2620: 20 20 28 61 70 70 6c 79 20 61 70 70 65 6e 64 20 (apply append 2630: 28 6d 61 70 20 76 65 63 74 6f 72 2d 3e 6c 69 73 (map vector->lis 2640: 74 20 28 6c 69 73 74 20 61 72 67 31 20 61 72 67 t (list arg1 arg 2650: 32 20 61 72 67 20 2e 2e 2e 29 29 29 20 29 29 0a 2 arg ...))) )). 2660: 20 20 20 20 28 28 3a 76 65 63 74 6f 72 31 20 63 ((:vector1 c 2670: 63 20 76 61 72 20 61 72 67 31 20 61 72 67 20 2e c var arg1 arg . 2680: 2e 2e 29 0a 20 20 20 20 20 28 3a 76 65 63 74 6f ..). (:vecto 2690: 72 31 20 63 63 20 76 61 72 20 28 69 6e 64 65 78 r1 cc var (index 26a0: 20 69 29 20 61 72 67 31 20 61 72 67 20 2e 2e 2e i) arg1 arg ... 26b0: 29 20 29 29 29 0a 0a 0a 3b 20 3a 76 65 63 74 6f ) )))...; :vecto 26c0: 72 32 0a 3b 20 20 20 20 72 75 6e 73 20 74 68 72 r2.; runs thr 26d0: 6f 75 67 68 20 61 20 6c 69 73 74 20 6f 66 20 76 ough a list of v 26e0: 65 63 74 6f 72 73 20 77 69 74 68 20 6e 65 73 74 ectors with nest 26f0: 65 64 20 6c 6f 6f 70 73 20 66 6f 72 20 6d 75 6c ed loops for mul 2700: 74 69 2d 61 72 67 2e 0a 3b 20 20 20 20 20 20 2b ti-arg..; + 2710: 20 6e 6f 20 73 70 61 63 65 20 6f 76 65 72 68 65 no space overhe 2720: 61 64 0a 3b 20 20 20 20 20 20 2b 20 6e 6f 20 63 ad.; + no c 2730: 6f 70 79 69 6e 67 20 6f 66 20 74 68 65 20 61 72 opying of the ar 2740: 67 75 6d 65 6e 74 73 0a 3b 20 20 20 20 20 20 2d guments.; - 2750: 20 6d 6f 72 65 20 63 6f 6d 70 6c 69 63 61 74 65 more complicate 2760: 64 20 62 6f 6f 6b 2d 6b 65 65 70 69 6e 67 0a 0a d book-keeping.. 2770: 28 64 65 66 69 6e 65 2d 73 79 6e 74 61 78 20 3a (define-syntax : 2780: 76 65 63 74 6f 72 32 0a 20 20 28 73 79 6e 74 61 vector2. (synta 2790: 78 2d 72 75 6c 65 73 20 28 69 6e 64 65 78 29 0a x-rules (index). 27a0: 20 20 20 20 28 28 3a 76 65 63 74 6f 72 32 20 63 ((:vector2 c 27b0: 63 20 76 61 72 20 61 72 67 29 0a 20 20 20 20 20 c var arg). 27c0: 28 3a 76 65 63 74 6f 72 32 20 63 63 20 76 61 72 (:vector2 cc var 27d0: 20 28 69 6e 64 65 78 20 69 29 20 61 72 67 29 20 (index i) arg) 27e0: 29 0a 20 20 20 20 28 28 3a 76 65 63 74 6f 72 32 ). ((:vector2 27f0: 20 63 63 20 76 61 72 20 28 69 6e 64 65 78 20 69 cc var (index i 2800: 29 20 61 72 67 29 0a 20 20 20 20 20 28 3a 64 6f ) arg). (:do 2810: 20 63 63 0a 20 20 20 20 20 20 20 20 20 20 28 6c cc. (l 2820: 65 74 20 28 28 76 65 63 20 61 72 67 29 20 28 6c et ((vec arg) (l 2830: 65 6e 20 30 29 29 20 0a 20 20 20 20 20 20 20 20 en 0)) . 2840: 20 20 20 20 28 73 65 74 21 20 6c 65 6e 20 28 76 (set! len (v 2850: 65 63 74 6f 72 2d 6c 65 6e 67 74 68 20 76 65 63 ector-length vec 2860: 29 29 29 0a 20 20 20 20 20 20 20 20 20 20 28 28 ))). (( 2870: 69 20 30 29 29 0a 20 20 20 20 20 20 20 20 20 20 i 0)). 2880: 28 3c 20 69 20 6c 65 6e 29 0a 20 20 20 20 20 20 (< i len). 2890: 20 20 20 20 28 6c 65 74 20 28 28 76 61 72 20 28 (let ((var ( 28a0: 76 65 63 74 6f 72 2d 72 65 66 20 76 65 63 20 69 vector-ref vec i 28b0: 29 29 29 29 0a 20 20 20 20 20 20 20 20 20 20 23 )))). # 28c0: 74 0a 20 20 20 20 20 20 20 20 20 20 28 28 2b 20 t. ((+ 28d0: 69 20 31 29 29 20 29 29 0a 0a 20 20 20 20 28 28 i 1)) )).. (( 28e0: 3a 76 65 63 74 6f 72 32 20 63 63 20 76 61 72 20 :vector2 cc var 28f0: 28 69 6e 64 65 78 20 69 29 20 61 72 67 31 20 61 (index i) arg1 a 2900: 72 67 32 20 61 72 67 20 2e 2e 2e 29 0a 20 20 20 rg2 arg ...). 2910: 20 20 28 3a 70 61 72 61 6c 6c 65 6c 20 63 63 20 (:parallel cc 2920: 28 3a 76 65 63 74 6f 72 32 20 63 63 20 76 61 72 (:vector2 cc var 2930: 20 61 72 67 31 20 61 72 67 32 20 61 72 67 20 2e arg1 arg2 arg . 2940: 2e 2e 29 20 28 3a 69 6e 74 65 67 65 72 73 20 69 ..) (:integers i 2950: 29 29 20 29 0a 20 20 20 20 28 28 3a 76 65 63 74 )) ). ((:vect 2960: 6f 72 32 20 63 63 20 76 61 72 20 61 72 67 31 20 or2 cc var arg1 2970: 61 72 67 32 20 61 72 67 20 2e 2e 2e 29 0a 20 20 arg2 arg ...). 2980: 20 20 20 28 3a 64 6f 20 63 63 0a 20 20 20 20 20 (:do cc. 2990: 20 20 20 20 20 28 6c 65 74 20 28 28 76 65 63 20 (let ((vec 29a0: 23 66 29 0a 20 20 20 20 20 20 20 20 20 20 20 20 #f). 29b0: 20 20 20 20 28 6c 65 6e 20 30 29 0a 20 20 20 20 (len 0). 29c0: 20 20 20 20 20 20 20 20 20 20 20 20 28 76 65 63 (vec 29d0: 73 20 28 65 63 2d 3a 76 65 63 74 6f 72 2d 66 69 s (ec-:vector-fi 29e0: 6c 74 65 72 20 28 6c 69 73 74 20 61 72 67 31 20 lter (list arg1 29f0: 61 72 67 32 20 61 72 67 20 2e 2e 2e 29 29 29 20 arg2 arg ...))) 2a00: 29 29 0a 20 20 20 20 20 20 20 20 20 20 28 28 6b )). ((k 2a10: 20 30 29 29 0a 20 20 20 20 20 20 20 20 20 20 28 0)). ( 2a20: 69 66 20 28 3c 20 6b 20 6c 65 6e 29 0a 20 20 20 if (< k len). 2a30: 20 20 20 20 20 20 20 20 20 20 20 23 74 0a 20 20 #t. 2a40: 20 20 20 20 20 20 20 20 20 20 20 20 28 69 66 20 (if 2a50: 28 6e 75 6c 6c 3f 20 76 65 63 73 29 0a 20 20 20 (null? vecs). 2a60: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 23 # 2a70: 66 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 f. 2a80: 20 20 20 20 28 62 65 67 69 6e 20 28 73 65 74 21 (begin (set! 2a90: 20 76 65 63 20 28 63 61 72 20 76 65 63 73 29 29 vec (car vecs)) 2aa0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 . 2ab0: 20 20 20 20 20 20 20 20 20 20 28 73 65 74 21 20 (set! 2ac0: 76 65 63 73 20 28 63 64 72 20 76 65 63 73 29 29 vecs (cdr vecs)) 2ad0: 0a 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 . 2ae0: 20 20 20 20 20 20 20 20 20 20 28 73 65 74 21 20 (set! 2af0: 6c 65 6e 20 28 76 65 63 74 6f 72 2d 6c 65 6e 67 len (vector-leng 2b00: 74 68 20 76 65 63 29 29 0a 20 20 20 20 20 20 20 th vec)). 2b10: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2b20: 20 20 28 73 65 74 21 20 6b 20 30 29 0a 20 20 20 (set! k 0). 2b30: 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2b40: 20 20 20 20 20 20 23 74 20 29 29 29 0a 20 20 20 #t ))). 2b50: 20 20 20 20 20 20 20 28 6c 65 74 20 28 28 76 61 (let ((va 2b60: 72 20 28 76 65 63 74 6f 72 2d 72 65 66 20 76 65 r (vector-ref ve 2b70: 63 20 6b 29 29 29 29 0a 20 20 20 20 20 20 20 20 c k)))). 2b80: 20 20 23 74 0a 20 20 20 20 20 20 20 20 20 20 28 #t. ( 2b90: 28 2b 20 6b 20 31 29 29 20 29 29 29 29 0a 0a 28 (+ k 1)) ))))..( 2ba0: 64 65 66 69 6e 65 20 28 65 63 2d 3a 76 65 63 74 define (ec-:vect 2bb0: 6f 72 2d 66 69 6c 74 65 72 20 76 65 63 73 29 0a or-filter vecs). 2bc0: 20 20 28 69 66 20 28 6e 75 6c 6c 3f 20 76 65 63 (if (null? vec 2bd0: 73 29 0a 20 20 20 20 20 20 27 28 29 0a 20 20 20 s). '(). 2be0: 20 20 20 28 69 66 20 28 7a 65 72 6f 3f 20 28 76 (if (zero? (v 2bf0: 65 63 74 6f 72 2d 6c 65 6e 67 74 68 20 28 63 61 ector-length (ca 2c00: 72 20 76 65 63 73 29 29 29 0a 20 20 20 20 20 20 r vecs))). 2c10: 20 20 20 20 28 65 63 2d 3a 76 65 63 74 6f 72 2d (ec-:vector- 2c20: 66 69 6c 74 65 72 20 28 63 64 72 20 76 65 63 73 filter (cdr vecs 2c30: 29 29 0a 20 20 20 20 20 20 20 20 20 20 28 63 6f )). (co 2c40: 6e 73 20 28 63 61 72 20 76 65 63 73 29 20 28 65 ns (car vecs) (e 2c50: 63 2d 3a 76 65 63 74 6f 72 2d 66 69 6c 74 65 72 c-:vector-filter 2c60: 20 28 63 64 72 20 76 65 63 73 29 29 29 20 29 29 (cdr vecs))) )) 2c70: 29 0a 0a 3b 20 63 6f 6d 70 61 72 69 73 6f 6e 0a )..; comparison. 2c80: 3b 20 20 20 2a 20 54 68 65 20 74 72 61 64 65 2d ; * The trade- 2c90: 6f 66 66 20 69 73 20 62 6f 6f 6b 2d 6b 65 65 70 off is book-keep 2ca0: 69 6e 67 20 6f 76 65 72 68 65 61 64 20 76 73 2e ing overhead vs. 2cb0: 20 61 6c 6c 6f 63 61 74 69 6f 6e 20 6f 76 65 72 allocation over 2cc0: 68 65 61 64 2e 0a 3b 20 20 20 2a 20 53 63 68 65 head..; * Sche 2cd0: 6d 65 34 38 20 30 2e 35 37 3a 20 46 6f 72 20 73 me48 0.57: For s 2ce0: 68 6f 72 74 20 76 65 63 74 6f 72 73 20 3a 76 65 hort vectors :ve 2cf0: 63 74 6f 72 31 20 69 73 20 32 30 25 20 66 61 73 ctor1 is 20% fas 2d00: 74 65 72 20 74 68 61 6e 20 0a 3b 20 20 20 20 20 ter than .; 2d10: 20 20 3a 76 65 63 74 6f 72 32 2e 20 46 6f 72 20 :vector2. For 2d20: 6c 6f 6e 67 20 76 65 63 74 6f 72 73 20 28 31 30 long vectors (10 2d30: 5e 34 29 20 3a 76 65 63 74 6f 72 32 20 69 73 20 ^4) :vector2 is 2d40: 66 61 63 74 6f 72 20 32 2e 38 20 0a 3b 20 20 20 factor 2.8 .; 2d50: 20 20 20 20 74 69 6d 65 73 20 66 61 73 74 65 72 times faster 2d60: 2e 20 42 72 65 61 6b 2d 65 76 65 6e 20 61 72 6f . Break-even aro 2d70: 75 6e 64 20 6e 20 3d 20 32 2e 0a 3b 20 20 20 2a und n = 2..; * 2d80: 20 50 4c 54 20 32 30 32 3a 20 46 6f 72 20 73 68 PLT 202: For sh 2d90: 6f 72 74 20 76 65 63 74 6f 72 73 2c 20 3a 76 65 ort vectors, :ve 2da0: 63 74 6f 72 31 20 69 73 20 66 61 63 74 6f 72 20 ctor1 is factor 2db0: 32 20 66 61 73 74 65 72 20 74 68 61 6e 0a 3b 20 2 faster than.; 2dc0: 20 20 20 20 20 20 3a 76 65 63 74 6f 72 32 2c 20 :vector2, 2dd0: 66 6f 72 20 6c 6f 6e 67 20 76 65 63 74 6f 72 73 for long vectors 2de0: 20 28 31 30 5e 34 29 20 66 61 63 74 6f 72 20 31 (10^4) factor 1 2df0: 2e 36 20 73 6c 6f 77 65 72 2e 0a 3b 20 20 20 20 .6 slower..; 2e00: 20 20 20 42 72 65 61 6b 2d 65 76 65 6e 20 69 73 Break-even is 2e10: 20 61 72 6f 75 6e 64 20 6e 20 3d 20 33 2e 0a 0a around n = 3... 2e20: 28 64 65 66 69 6e 65 20 28 70 65 72 66 2d 3a 76 (define (perf-:v 2e30: 65 63 74 6f 72 31 20 69 74 65 72 61 74 69 6f 6e ector1 iteration 2e40: 73 20 6e 29 0a 20 20 28 64 6f 2d 65 63 20 0a 20 s n). (do-ec . 2e50: 20 20 28 3a 6c 65 74 20 76 20 28 76 65 63 74 6f (:let v (vecto 2e60: 72 2d 6f 66 2d 6c 65 6e 67 74 68 2d 65 63 20 6e r-of-length-ec n 2e70: 20 28 3a 72 61 6e 67 65 20 69 20 6e 29 20 69 29 (:range i n) i) 2e80: 29 0a 20 20 20 28 3a 72 61 6e 67 65 20 69 20 69 ). (:range i i 2e90: 74 65 72 61 74 69 6f 6e 73 29 20 0a 20 20 20 28 terations) . ( 2ea0: 64 6f 2d 65 63 20 28 3a 76 65 63 74 6f 72 31 20 do-ec (:vector1 2eb0: 78 20 76 20 76 20 76 20 76 20 76 20 76 20 76 20 x v v v v v v v 2ec0: 76 20 76 20 76 29 20 78 29 20 29 29 0a 0a 28 64 v v v) x) ))..(d 2ed0: 65 66 69 6e 65 20 28 70 65 72 66 2d 3a 76 65 63 efine (perf-:vec 2ee0: 74 6f 72 32 20 69 74 65 72 61 74 69 6f 6e 73 20 tor2 iterations 2ef0: 6e 29 0a 20 20 28 64 6f 2d 65 63 20 0a 20 20 20 n). (do-ec . 2f00: 28 3a 6c 65 74 20 76 20 28 76 65 63 74 6f 72 2d (:let v (vector- 2f10: 6f 66 2d 6c 65 6e 67 74 68 2d 65 63 20 6e 20 28 of-length-ec n ( 2f20: 3a 72 61 6e 67 65 20 69 20 6e 29 20 69 29 29 0a :range i n) i)). 2f30: 20 20 20 28 3a 72 61 6e 67 65 20 69 20 69 74 65 (:range i ite 2f40: 72 61 74 69 6f 6e 73 29 20 0a 20 20 20 28 64 6f rations) . (do 2f50: 2d 65 63 20 28 3a 76 65 63 74 6f 72 32 20 78 20 -ec (:vector2 x 2f60: 76 20 76 20 76 20 76 20 76 20 76 20 76 20 76 20 v v v v v v v v 2f70: 76 20 76 29 20 78 29 20 29 29 0a 0a 3b 20 74 72 v v) x) ))..; tr 2f80: 79 3a 0a 3b 20 20 20 28 70 65 72 66 2d 3a 76 65 y:.; (perf-:ve 2f90: 63 74 6f 72 31 20 31 30 30 30 30 30 20 31 29 0a ctor1 100000 1). 2fa0: 3b 20 20 20 28 70 65 72 66 2d 3a 76 65 63 74 6f ; (perf-:vecto 2fb0: 72 32 20 31 30 30 30 30 30 20 31 29 0a 3b 20 20 r2 100000 1).; 2fc0: 20 28 70 65 72 66 2d 3a 76 65 63 74 6f 72 31 20 (perf-:vector1 2fd0: 31 30 30 20 31 30 30 30 30 29 0a 3b 20 20 20 28 100 10000).; ( 2fe0: 70 65 72 66 2d 3a 76 65 63 74 6f 72 32 20 31 30 perf-:vector2 10 2ff0: 30 20 31 30 30 30 30 29 0a 0a 0 10000)..