# Ticket #141: svn-16552-16579.patch.txt

File svn-16552-16579.patch.txt, 175.1 KB (added by , 14 years ago) |
---|

Line | |
---|---|

1 | From 306942a604d69beefa5522d8623060ce1a83b57c Mon Sep 17 00:00:00 2001 |

2 | Message-Id: <306942a604d69beefa5522d8623060ce1a83b57c.1260078974.git.zbigniewsz@gmail.com> |

3 | In-Reply-To: <cover.1260078974.git.zbigniewsz@gmail.com> |

4 | References: <cover.1260078974.git.zbigniewsz@gmail.com> |

5 | From: zbigniew <zbigniewsz@gmail.com> |

6 | Date: Sat, 5 Dec 2009 23:34:34 -0600 |

7 | Subject: Sync changes from wiki manual to core: SVN 16552-16559 (R5RS standard) |

8 | Status: O |

9 | |

10 | |

11 | Signed-off-by: zbigniew <zbigniewsz@gmail.com> |

12 | --- |

13 | manual/Supported language | 1 + |

14 | manual/The R5RS standard | 3060 +++++++++++++++++++++++++++++++++++++++++++++ |

15 | 2 files changed, 3061 insertions(+), 0 deletions(-) |

16 | create mode 100644 manual/The R5RS standard |

17 | |

18 | diff --git a/manual/Supported language b/manual/Supported language |

19 | index 8f546a1..4ffdd9d 100644 |

20 | --- a/manual/Supported language |

21 | +++ b/manual/Supported language |

22 | @@ -2,6 +2,7 @@ |

23 | |

24 | == Supported language |

25 | |

26 | +* [[The R5RS standard]] |

27 | * [[Deviations from the standard]] |

28 | * [[Extensions to the standard]] |

29 | * [[Non-standard read syntax]] |

30 | diff --git a/manual/The R5RS standard b/manual/The R5RS standard |

31 | new file mode 100644 |

32 | index 0000000..adb4091 |

33 | --- /dev/null |

34 | +++ b/manual/The R5RS standard |

35 | @@ -0,0 +1,3060 @@ |

36 | +This document describes Chicken's R5RS support, with a heavy emphasis |

37 | +on syntax and procedures. It is based directly on the |

38 | +''Revised^5 Report on the Algorithmic Language Scheme''. |

39 | +[[toc:]] |

40 | +== Overview of Scheme |

41 | +== Lexical conventions |

42 | +== Basic concepts |

43 | +== Expressions |

44 | + |

45 | +Expression types are categorized as primitive or derived. Primitive |

46 | +expression types include variables and procedure calls. Derived |

47 | +expression types are not semantically primitive, but can instead be |

48 | +defined as macros. With the exception of quasiquote, whose macro |

49 | +definition is complex, the derived expressions are classified as |

50 | +library features. Suitable definitions are given in section 7.3. |

51 | + |

52 | +=== Primitive expression types |

53 | + |

54 | +==== Variable references |

55 | + |

56 | +<macro><variable></macro><br> |

57 | + |

58 | +An expression consisting of a variable (section 3.1) is a variable |

59 | +reference. The value of the variable reference is the value stored in |

60 | +the location to which the variable is bound. It is an error to |

61 | +reference an unbound variable. |

62 | + |

63 | + (define x 28) |

64 | + x ===> 28 |

65 | + |

66 | +==== Literal expressions |

67 | + |

68 | +<macro>(quote <datum>)</macro><br> |

69 | +<macro>'<datum></macro><br> |

70 | +<macro><constant></macro><br> |

71 | + |

72 | +(quote <datum>) evaluates to <datum>. <Datum> may be any external |

73 | +representation of a Scheme object (see section 3.3). This notation is |

74 | +used to include literal constants in Scheme code. |

75 | + |

76 | + (quote a) ===> a |

77 | + (quote #(a b c)) ===> #(a b c) |

78 | + (quote (+ 1 2)) ===> (+ 1 2) |

79 | + |

80 | +(quote <datum>) may be abbreviated as '<datum>. The two notations are |

81 | +equivalent in all respects. |

82 | + |

83 | + 'a ===> a |

84 | + '#(a b c) ===> #(a b c) |

85 | + '() ===> () |

86 | + '(+ 1 2) ===> (+ 1 2) |

87 | + '(quote a) ===> (quote a) |

88 | + "a ===> (quote a) |

89 | + |

90 | +Numerical constants, string constants, character constants, and boolean |

91 | +constants evaluate "to themselves"; they need not be quoted. |

92 | + |

93 | + '"abc" ===> "abc" |

94 | + "abc" ===> "abc" |

95 | + '145932 ===> 145932 |

96 | + 145932 ===> 145932 |

97 | + '#t ===> #t |

98 | + #t ===> #t |

99 | + |

100 | +As noted in section 3.4, it is an error to alter a constant (i.e. the |

101 | +value of a literal expression) using a mutation procedure like set-car! |

102 | +or string-set!. |

103 | + |

104 | +==== Procedure calls |

105 | + |

106 | +<macro>(<operator> <operand[1]> ...)</macro><br> |

107 | + |

108 | +A procedure call is written by simply enclosing in parentheses |

109 | +expressions for the procedure to be called and the arguments to be |

110 | +passed to it. The operator and operand expressions are evaluated (in an |

111 | +unspecified order) and the resulting procedure is passed the resulting |

112 | +arguments. |

113 | + |

114 | + (+ 3 4) ===> 7 |

115 | + ((if #f + *) 3 4) ===> 12 |

116 | + |

117 | +A number of procedures are available as the values of variables in the |

118 | +initial environment; for example, the addition and multiplication |

119 | +procedures in the above examples are the values of the variables + and *. |

120 | +New procedures are created by evaluating lambda expressions (see |

121 | +section 4.1.4). Procedure calls may return any number of values (see |

122 | +values in section 6.4). With the exception of values the procedures |

123 | +available in the initial environment return one value or, for |

124 | +procedures such as apply, pass on the values returned by a call to one |

125 | +of their arguments. |

126 | + |

127 | +Procedure calls are also called combinations. |

128 | + |

129 | +Note: In contrast to other dialects of Lisp, the order of |

130 | +evaluation is unspecified, and the operator expression and the |

131 | +operand expressions are always evaluated with the same evaluation |

132 | +rules. |

133 | + |

134 | +Note: Although the order of evaluation is otherwise unspecified, |

135 | +the effect of any concurrent evaluation of the operator and operand |

136 | +expressions is constrained to be consistent with some sequential |

137 | +order of evaluation. The order of evaluation may be chosen |

138 | +differently for each procedure call. |

139 | + |

140 | +Note: In many dialects of Lisp, the empty combination, (), is a |

141 | +legitimate expression. In Scheme, combinations must have at least |

142 | +one subexpression, so () is not a syntactically valid expression. |

143 | + |

144 | +==== Procedures |

145 | + |

146 | +<macro>(lambda <formals> <body>)</macro><br> |

147 | + |

148 | +Syntax: <Formals> should be a formal arguments list as described below, |

149 | +and <body> should be a sequence of one or more expressions. |

150 | + |

151 | +Semantics: A lambda expression evaluates to a procedure. The |

152 | +environment in effect when the lambda expression was evaluated is |

153 | +remembered as part of the procedure. When the procedure is later called |

154 | +with some actual arguments, the environment in which the lambda |

155 | +expression was evaluated will be extended by binding the variables in |

156 | +the formal argument list to fresh locations, the corresponding actual |

157 | +argument values will be stored in those locations, and the expressions |

158 | +in the body of the lambda expression will be evaluated sequentially in |

159 | +the extended environment. The result(s) of the last expression in the |

160 | +body will be returned as the result(s) of the procedure call. |

161 | + |

162 | + (lambda (x) (+ x x)) ===> a procedure |

163 | + ((lambda (x) (+ x x)) 4) ===> 8 |

164 | + |

165 | + (define reverse-subtract |

166 | + (lambda (x y) (- y x))) |

167 | + (reverse-subtract 7 10) ===> 3 |

168 | + |

169 | + (define add4 |

170 | + (let ((x 4)) |

171 | + (lambda (y) (+ x y)))) |

172 | + (add4 6) ===> 10 |

173 | + |

174 | +<Formals> should have one of the following forms: |

175 | + |

176 | +* (<variable[1]> ...): The procedure takes a fixed number of |

177 | + arguments; when the procedure is called, the arguments will be |

178 | + stored in the bindings of the corresponding variables. |

179 | + |

180 | +* <variable>: The procedure takes any number of arguments; when the |

181 | + procedure is called, the sequence of actual arguments is converted |

182 | + into a newly allocated list, and the list is stored in the binding |

183 | + of the <variable>. |

184 | + |

185 | +* (<variable[1]> ... <variable[n]> . <variable[n+1]>): If a |

186 | + space-delimited period precedes the last variable, then the |

187 | + procedure takes n or more arguments, where n is the number of |

188 | + formal arguments before the period (there must be at least one). |

189 | + The value stored in the binding of the last variable will be a |

190 | + newly allocated list of the actual arguments left over after all |

191 | + the other actual arguments have been matched up against the other |

192 | + formal arguments. |

193 | + |

194 | +It is an error for a <variable> to appear more than once in <formals>. |

195 | + |

196 | + ((lambda x x) 3 4 5 6) ===> (3 4 5 6) |

197 | + ((lambda (x y . z) z) |

198 | + 3 4 5 6) ===> (5 6) |

199 | + |

200 | +Each procedure created as the result of evaluating a lambda expression |

201 | +is (conceptually) tagged with a storage location, in order to make eqv? |

202 | +and eq? work on procedures (see section 6.1). |

203 | + |

204 | +==== Conditionals |

205 | + |

206 | +<macro>(if <test> <consequent> <alternate>)</macro><br> |

207 | +<macro>(if <test> <consequent>)</macro><br> |

208 | + |

209 | +Syntax: <Test>, <consequent>, and <alternate> may be arbitrary |

210 | +expressions. |

211 | + |

212 | +Semantics: An if expression is evaluated as follows: first, <test> is |

213 | +evaluated. If it yields a true value (see section 6.3.1), then |

214 | +<consequent> is evaluated and its value(s) is(are) returned. Otherwise |

215 | +<alternate> is evaluated and its value(s) is(are) returned. If <test> |

216 | +yields a false value and no <alternate> is specified, then the result |

217 | +of the expression is unspecified. |

218 | + |

219 | + (if (> 3 2) 'yes 'no) ===> yes |

220 | + (if (> 2 3) 'yes 'no) ===> no |

221 | + (if (> 3 2) |

222 | + (- 3 2) |

223 | + (+ 3 2)) ===> 1 |

224 | + |

225 | +==== Assignments |

226 | + |

227 | +<macro>(set! <variable> <expression>)</macro><br> |

228 | + |

229 | +<Expression> is evaluated, and the resulting value is stored in the |

230 | +location to which <variable> is bound. <Variable> must be bound either |

231 | +in some region enclosing the set! expression or at top level. The |

232 | +result of the set! expression is unspecified. |

233 | + |

234 | + (define x 2) |

235 | + (+ x 1) ===> 3 |

236 | + (set! x 4) ===> unspecified |

237 | + (+ x 1) ===> 5 |

238 | + |

239 | +=== Derived expression types |

240 | + |

241 | +The constructs in this section are hygienic, as discussed in section |

242 | +4.3. For reference purposes, section 7.3 gives macro definitions that |

243 | +will convert most of the constructs described in this section into the |

244 | +primitive constructs described in the previous section. |

245 | + |

246 | +==== Conditionals |

247 | + |

248 | +<macro>(cond <clause[1]> <clause[2]> ...)</macro><br> |

249 | + |

250 | +Syntax: Each <clause> should be of the form |

251 | + |

252 | + (<test> <expression[1]> ...) |

253 | + |

254 | +where <test> is any expression. Alternatively, a <clause> may be of the |

255 | +form |

256 | + |

257 | + (<test> => <expression>) |

258 | + |

259 | +The last <clause> may be an "else clause," which has the form |

260 | + |

261 | + (else <expression[1]> <expression[2]> ...). |

262 | + |

263 | +Semantics: A cond expression is evaluated by evaluating the <test> |

264 | +expressions of successive <clause>s in order until one of them |

265 | +evaluates to a true value (see section 6.3.1). When a <test> evaluates |

266 | +to a true value, then the remaining <expression>s in its <clause> are |

267 | +evaluated in order, and the result(s) of the last <expression> in the |

268 | +<clause> is(are) returned as the result(s) of the entire cond |

269 | +expression. If the selected <clause> contains only the <test> and no |

270 | +<expression>s, then the value of the <test> is returned as the result. |

271 | +If the selected <clause> uses the => alternate form, then the |

272 | +<expression> is evaluated. Its value must be a procedure that accepts |

273 | +one argument; this procedure is then called on the value of the <test> |

274 | +and the value(s) returned by this procedure is(are) returned by the |

275 | +cond expression. If all <test>s evaluate to false values, and there is |

276 | +no else clause, then the result of the conditional expression is |

277 | +unspecified; if there is an else clause, then its <expression>s are |

278 | +evaluated, and the value(s) of the last one is(are) returned. |

279 | + |

280 | + (cond ((> 3 2) 'greater) |

281 | + ((< 3 2) 'less)) ===> greater |

282 | + (cond ((> 3 3) 'greater) |

283 | + ((< 3 3) 'less) |

284 | + (else 'equal)) ===> equal |

285 | + (cond ((assv 'b '((a 1) (b 2))) => cadr) |

286 | + (else #f)) ===> 2 |

287 | + |

288 | +<macro>(case <key> <clause[1]> <clause[2]> ...)</macro><br> |

289 | + |

290 | +Syntax: <Key> may be any expression. Each <clause> should have the form |

291 | + |

292 | + ((<datum[1]> ...) <expression[1]> <expression[2]> ...), |

293 | + |

294 | +where each <datum> is an external representation of some object. All |

295 | +the <datum>s must be distinct. The last <clause> may be an "else |

296 | +clause," which has the form |

297 | + |

298 | + (else <expression[1]> <expression[2]> ...). |

299 | + |

300 | +Semantics: A case expression is evaluated as follows. <Key> is |

301 | +evaluated and its result is compared against each <datum>. If the |

302 | +result of evaluating <key> is equivalent (in the sense of eqv?; see |

303 | +section 6.1) to a <datum>, then the expressions in the corresponding |

304 | +<clause> are evaluated from left to right and the result(s) of the last |

305 | +expression in the <clause> is(are) returned as the result(s) of the |

306 | +case expression. If the result of evaluating <key> is different from |

307 | +every <datum>, then if there is an else clause its expressions are |

308 | +evaluated and the result(s) of the last is(are) the result(s) of the |

309 | +case expression; otherwise the result of the case expression is |

310 | +unspecified. |

311 | + |

312 | + (case (* 2 3) |

313 | + ((2 3 5 7) 'prime) |

314 | + ((1 4 6 8 9) 'composite)) ===> composite |

315 | + (case (car '(c d)) |

316 | + ((a) 'a) |

317 | + ((b) 'b)) ===> unspecified |

318 | + (case (car '(c d)) |

319 | + ((a e i o u) 'vowel) |

320 | + ((w y) 'semivowel) |

321 | + (else 'consonant)) ===> consonant |

322 | + |

323 | +<macro>(and <test[1]> ...)</macro><br> |

324 | + |

325 | +The <test> expressions are evaluated from left to right, and the value |

326 | +of the first expression that evaluates to a false value (see section |

327 | +6.3.1) is returned. Any remaining expressions are not evaluated. If all |

328 | +the expressions evaluate to true values, the value of the last |

329 | +expression is returned. If there are no expressions then #t is |

330 | +returned. |

331 | + |

332 | + (and (= 2 2) (> 2 1)) ===> #t |

333 | + (and (= 2 2) (< 2 1)) ===> #f |

334 | + (and 1 2 'c '(f g)) ===> (f g) |

335 | + (and) ===> #t |

336 | + |

337 | +<macro>(or <test[1]> ...)</macro><br> |

338 | + |

339 | +The <test> expressions are evaluated from left to right, and the value |

340 | +of the first expression that evaluates to a true value (see section |

341 | +6.3.1) is returned. Any remaining expressions are not evaluated. If all |

342 | +expressions evaluate to false values, the value of the last expression |

343 | +is returned. If there are no expressions then #f is returned. |

344 | + |

345 | + (or (= 2 2) (> 2 1)) ===> #t |

346 | + (or (= 2 2) (< 2 1)) ===> #t |

347 | + (or #f #f #f) ===> #f |

348 | + (or (memq 'b '(a b c)) |

349 | + (/ 3 0)) ===> (b c) |

350 | + |

351 | +==== Binding constructs |

352 | + |

353 | +The three binding constructs let, let*, and letrec give Scheme a block |

354 | +structure, like Algol 60. The syntax of the three constructs is |

355 | +identical, but they differ in the regions they establish for their |

356 | +variable bindings. In a let expression, the initial values are computed |

357 | +before any of the variables become bound; in a let* expression, the |

358 | +bindings and evaluations are performed sequentially; while in a letrec |

359 | +expression, all the bindings are in effect while their initial values |

360 | +are being computed, thus allowing mutually recursive definitions. |

361 | + |

362 | +<macro>(let <bindings> <body>)</macro><br> |

363 | + |

364 | +Syntax: <Bindings> should have the form |

365 | + |

366 | + ((<variable[1]> <init[1]>) ...), |

367 | + |

368 | +where each <init> is an expression, and <body> should be a sequence of |

369 | +one or more expressions. It is an error for a <variable> to appear more |

370 | +than once in the list of variables being bound. |

371 | + |

372 | +Semantics: The <init>s are evaluated in the current environment (in |

373 | +some unspecified order), the <variable>s are bound to fresh locations |

374 | +holding the results, the <body> is evaluated in the extended |

375 | +environment, and the value(s) of the last expression of <body> is(are) |

376 | +returned. Each binding of a <variable> has <body> as its region. |

377 | + |

378 | + (let ((x 2) (y 3)) |

379 | + (* x y)) ===> 6 |

380 | + |

381 | + (let ((x 2) (y 3)) |

382 | + (let ((x 7) |

383 | + (z (+ x y))) |

384 | + (* z x))) ===> 35 |

385 | + |

386 | +See also named let, section 4.2.4. |

387 | + |

388 | +<macro>(let* <bindings> <body>)</macro><br> |

389 | + |

390 | +Syntax: <Bindings> should have the form |

391 | + |

392 | + ((<variable[1]> <init[1]>) ...), |

393 | + |

394 | +and <body> should be a sequence of one or more expressions. |

395 | + |

396 | +Semantics: Let* is similar to let, but the bindings are performed |

397 | +sequentially from left to right, and the region of a binding indicated |

398 | +by (<variable> <init>) is that part of the let* expression to the right |

399 | +of the binding. Thus the second binding is done in an environment in |

400 | +which the first binding is visible, and so on. |

401 | + |

402 | + (let ((x 2) (y 3)) |

403 | + (let* ((x 7) |

404 | + (z (+ x y))) |

405 | + (* z x))) ===> 70 |

406 | + |

407 | +<macro>(letrec <bindings> <body>)</macro><br> |

408 | + |

409 | +Syntax: <Bindings> should have the form |

410 | + |

411 | + ((<variable[1]> <init[1]>) ...), |

412 | + |

413 | +and <body> should be a sequence of one or more expressions. It is an |

414 | +error for a <variable> to appear more than once in the list of |

415 | +variables being bound. |

416 | + |

417 | +Semantics: The <variable>s are bound to fresh locations holding |

418 | +undefined values, the <init>s are evaluated in the resulting |

419 | +environment (in some unspecified order), each <variable> is assigned to |

420 | +the result of the corresponding <init>, the <body> is evaluated in the |

421 | +resulting environment, and the value(s) of the last expression in |

422 | +<body> is(are) returned. Each binding of a <variable> has the entire |

423 | +letrec expression as its region, making it possible to define mutually |

424 | +recursive procedures. |

425 | + |

426 | + (letrec ((even? |

427 | + (lambda (n) |

428 | + (if (zero? n) |

429 | + #t |

430 | + (odd? (- n 1))))) |

431 | + (odd? |

432 | + (lambda (n) |

433 | + (if (zero? n) |

434 | + #f |

435 | + (even? (- n 1)))))) |

436 | + (even? 88)) |

437 | + ===> #t |

438 | + |

439 | +One restriction on letrec is very important: it must be possible to |

440 | +evaluate each <init> without assigning or referring to the value of any |

441 | +<variable>. If this restriction is violated, then it is an error. The |

442 | +restriction is necessary because Scheme passes arguments by value |

443 | +rather than by name. In the most common uses of letrec, all the <init>s |

444 | +are lambda expressions and the restriction is satisfied automatically. |

445 | + |

446 | +==== Sequencing |

447 | + |

448 | +<macro>(begin <expression[1]> <expression[2]> ...)</macro><br> |

449 | + |

450 | +The <expression>s are evaluated sequentially from left to right, and |

451 | +the value(s) of the last <expression> is(are) returned. This expression |

452 | +type is used to sequence side effects such as input and output. |

453 | + |

454 | + (define x 0) |

455 | + |

456 | + (begin (set! x 5) |

457 | + (+ x 1)) ===> 6 |

458 | + |

459 | + (begin (display "4 plus 1 equals ") |

460 | + (display (+ 4 1))) ===> unspecified |

461 | + and prints 4 plus 1 equals 5 |

462 | + |

463 | +==== Iteration |

464 | + |

465 | +<macro>(do ((<variable[1]> <init[1]> <step[1]>) ...) (<test> <expression> ...) <command> ...)</macro><br> |

466 | + |

467 | +Do is an iteration construct. It specifies a set of variables to be |

468 | +bound, how they are to be initialized at the start, and how they are to |

469 | +be updated on each iteration. When a termination condition is met, the |

470 | +loop exits after evaluating the <expression>s. |

471 | + |

472 | +Do expressions are evaluated as follows: The <init> expressions are |

473 | +evaluated (in some unspecified order), the <variable>s are bound to |

474 | +fresh locations, the results of the <init> expressions are stored in |

475 | +the bindings of the <variable>s, and then the iteration phase begins. |

476 | + |

477 | +Each iteration begins by evaluating <test>; if the result is false (see |

478 | +section 6.3.1), then the <command> expressions are evaluated in order |

479 | +for effect, the <step> expressions are evaluated in some unspecified |

480 | +order, the <variable>s are bound to fresh locations, the results of the |

481 | +<step>s are stored in the bindings of the <variable>s, and the next |

482 | +iteration begins. |

483 | + |

484 | +If <test> evaluates to a true value, then the <expression>s are |

485 | +evaluated from left to right and the value(s) of the last <expression> |

486 | +is(are) returned. If no <expression>s are present, then the value of |

487 | +the do expression is unspecified. |

488 | + |

489 | +The region of the binding of a <variable> consists of the entire do |

490 | +expression except for the <init>s. It is an error for a <variable> to |

491 | +appear more than once in the list of do variables. |

492 | + |

493 | +A <step> may be omitted, in which case the effect is the same as if |

494 | +(<variable> <init> <variable>) had been written instead of (<variable> |

495 | +<init>). |

496 | + |

497 | + (do ((vec (make-vector 5)) |

498 | + (i 0 (+ i 1))) |

499 | + ((= i 5) vec) |

500 | + (vector-set! vec i i)) ===> #(0 1 2 3 4) |

501 | + |

502 | + (let ((x '(1 3 5 7 9))) |

503 | + (do ((x x (cdr x)) |

504 | + (sum 0 (+ sum (car x)))) |

505 | + ((null? x) sum))) ===> 25 |

506 | + |

507 | +<macro>(let <variable> <bindings> <body>)</macro><br> |

508 | + |

509 | +"Named let" is a variant on the syntax of let which provides a more |

510 | +general looping construct than do and may also be used to express |

511 | +recursions. It has the same syntax and semantics as ordinary let except |

512 | +that <variable> is bound within <body> to a procedure whose formal |

513 | +arguments are the bound variables and whose body is <body>. Thus the |

514 | +execution of <body> may be repeated by invoking the procedure named by |

515 | +<variable>. |

516 | + |

517 | + (let loop ((numbers '(3 -2 1 6 -5)) |

518 | + (nonneg '()) |

519 | + (neg '())) |

520 | + (cond ((null? numbers) (list nonneg neg)) |

521 | + ((>= (car numbers) 0) |

522 | + (loop (cdr numbers) |

523 | + (cons (car numbers) nonneg) |

524 | + neg)) |

525 | + ((< (car numbers) 0) |

526 | + (loop (cdr numbers) |

527 | + nonneg |

528 | + (cons (car numbers) neg))))) |

529 | + ===> ((6 1 3) (-5 -2)) |

530 | + |

531 | +==== Delayed evaluation |

532 | + |

533 | +<macro>(delay <expression>)</macro><br> |

534 | + |

535 | +The delay construct is used together with the procedure force to |

536 | +implement lazy evaluation or call by need. (delay <expression>) returns |

537 | +an object called a promise which at some point in the future may be |

538 | +asked (by the force procedure) to evaluate <expression>, and deliver |

539 | +the resulting value. The effect of <expression> returning multiple |

540 | +values is unspecified. |

541 | + |

542 | +See the description of force (section 6.4) for a more complete |

543 | +description of delay. |

544 | + |

545 | +==== Quasiquotation |

546 | + |

547 | +<macro>(quasiquote <qq template>)</macro><br> |

548 | +<macro>`<qq template></macro><br> |

549 | + |

550 | +"Backquote" or "quasiquote" expressions are useful for constructing |

551 | +a list or vector structure when most but not all of the desired |

552 | +structure is known in advance. If no commas appear within the <qq |

553 | +template>, the result of evaluating `<qq template> is equivalent to the |

554 | +result of evaluating '<qq template>. If a comma appears within the <qq |

555 | +template>, however, the expression following the comma is evaluated |

556 | +("unquoted") and its result is inserted into the structure instead of |

557 | +the comma and the expression. If a comma appears followed immediately |

558 | +by an at-sign (@), then the following expression must evaluate to a |

559 | +list; the opening and closing parentheses of the list are then |

560 | +"stripped away" and the elements of the list are inserted in place of |

561 | +the comma at-sign expression sequence. A comma at-sign should only |

562 | +appear within a list or vector <qq template>. |

563 | + |

564 | + `(list ,(+ 1 2) 4) ===> (list 3 4) |

565 | + (let ((name 'a)) `(list ,name ',name)) |

566 | + ===> (list a (quote a)) |

567 | + `(a ,(+ 1 2) ,@(map abs '(4 -5 6)) b) |

568 | + ===> (a 3 4 5 6 b) |

569 | + `(( foo ,(- 10 3)) ,@(cdr '(c)) . ,(car '(cons))) |

570 | + ===> ((foo 7) . cons) |

571 | + `#(10 5 ,(sqrt 4) ,@(map sqrt '(16 9)) 8) |

572 | + ===> #(10 5 2 4 3 8) |

573 | + |

574 | +Quasiquote forms may be nested. Substitutions are made only for |

575 | +unquoted components appearing at the same nesting level as the |

576 | +outermost backquote. The nesting level increases by one inside each |

577 | +successive quasiquotation, and decreases by one inside each |

578 | +unquotation. |

579 | + |

580 | + `(a `(b ,(+ 1 2) ,(foo ,(+ 1 3) d) e) f) |

581 | + ===> (a `(b ,(+ 1 2) ,(foo 4 d) e) f) |

582 | + (let ((name1 'x) |

583 | + (name2 'y)) |

584 | + `(a `(b ,,name1 ,',name2 d) e)) |

585 | + ===> (a `(b ,x ,'y d) e) |

586 | + |

587 | +The two notations `<qq template> and (quasiquote <qq template>) are |

588 | +identical in all respects. ,<expression> is identical to (unquote |

589 | +<expression>), and ,@<expression> is identical to (unquote-splicing |

590 | +<expression>). The external syntax generated by write for two-element |

591 | +lists whose car is one of these symbols may vary between |

592 | +implementations. |

593 | + |

594 | + (quasiquote (list (unquote (+ 1 2)) 4)) |

595 | + ===> (list 3 4) |

596 | + '(quasiquote (list (unquote (+ 1 2)) 4)) |

597 | + ===> `(list ,(+ 1 2) 4) |

598 | + i.e., (quasiquote (list (unquote (+ 1 2)) 4)) |

599 | + |

600 | +Unpredictable behavior can result if any of the symbols quasiquote, |

601 | +unquote, or unquote-splicing appear in positions within a <qq template> |

602 | +otherwise than as described above. |

603 | + |

604 | +=== Macros |

605 | + |

606 | +Scheme programs can define and use new derived expression types, called |

607 | +macros. Program-defined expression types have the syntax |

608 | + |

609 | + (<keyword> <datum> ...) |

610 | + |

611 | +where <keyword> is an identifier that uniquely determines the |

612 | +expression type. This identifier is called the syntactic keyword, or |

613 | +simply keyword, of the macro. The number of the <datum>s, and their |

614 | +syntax, depends on the expression type. |

615 | + |

616 | +Each instance of a macro is called a use of the macro. The set of rules |

617 | +that specifies how a use of a macro is transcribed into a more |

618 | +primitive expression is called the transformer of the macro. |

619 | + |

620 | +The macro definition facility consists of two parts: |

621 | + |

622 | +* A set of expressions used to establish that certain identifiers are |

623 | + macro keywords, associate them with macro transformers, and control |

624 | + the scope within which a macro is defined, and |

625 | + |

626 | +* a pattern language for specifying macro transformers. |

627 | + |

628 | +The syntactic keyword of a macro may shadow variable bindings, and |

629 | +local variable bindings may shadow keyword bindings. All macros defined |

630 | +using the pattern language are "hygienic" and "referentially |

631 | +transparent" and thus preserve Scheme's lexical scoping: |

632 | + |

633 | +* If a macro transformer inserts a binding for an identifier |

634 | + (variable or keyword), the identifier will in effect be renamed |

635 | + throughout its scope to avoid conflicts with other identifiers. |

636 | + Note that a define at top level may or may not introduce a binding; |

637 | + see section 5.2. |

638 | + |

639 | +* If a macro transformer inserts a free reference to an identifier, |

640 | + the reference refers to the binding that was visible where the |

641 | + transformer was specified, regardless of any local bindings that |

642 | + may surround the use of the macro. |

643 | + |

644 | +==== Binding constructs for syntactic keywords |

645 | + |

646 | +Let-syntax and letrec-syntax are analogous to let and letrec, but they |

647 | +bind syntactic keywords to macro transformers instead of binding |

648 | +variables to locations that contain values. Syntactic keywords may also |

649 | +be bound at top level; see section 5.3. |

650 | + |

651 | +<macro>(let-syntax <bindings> <body>)</macro><br> |

652 | + |

653 | +Syntax: <Bindings> should have the form |

654 | + |

655 | + ((<keyword> <transformer spec>) ...) |

656 | + |

657 | +Each <keyword> is an identifier, each <transformer spec> is an instance |

658 | +of syntax-rules, and <body> should be a sequence of one or more |

659 | +expressions. It is an error for a <keyword> to appear more than once in |

660 | +the list of keywords being bound. |

661 | + |

662 | +Semantics: The <body> is expanded in the syntactic environment obtained |

663 | +by extending the syntactic environment of the let-syntax expression |

664 | +with macros whose keywords are the <keyword>s, bound to the specified |

665 | +transformers. Each binding of a <keyword> has <body> as its region. |

666 | + |

667 | + (let-syntax ((when (syntax-rules () |

668 | + ((when test stmt1 stmt2 ...) |

669 | + (if test |

670 | + (begin stmt1 |

671 | + stmt2 ...)))))) |

672 | + (let ((if #t)) |

673 | + (when if (set! if 'now)) |

674 | + if)) ===> now |

675 | + |

676 | + (let ((x 'outer)) |

677 | + (let-syntax ((m (syntax-rules () ((m) x)))) |

678 | + (let ((x 'inner)) |

679 | + (m)))) ===> outer |

680 | + |

681 | +<macro>(letrec-syntax <bindings> <body>)</macro><br> |

682 | + |

683 | +Syntax: Same as for let-syntax. |

684 | + |

685 | +Semantics: The <body> is expanded in the syntactic environment obtained |

686 | +by extending the syntactic environment of the letrec-syntax expression |

687 | +with macros whose keywords are the <keyword>s, bound to the specified |

688 | +transformers. Each binding of a <keyword> has the <bindings> as well as |

689 | +the <body> within its region, so the transformers can transcribe |

690 | +expressions into uses of the macros introduced by the letrec-syntax |

691 | +expression. |

692 | + |

693 | + (letrec-syntax |

694 | + ((my-or (syntax-rules () |

695 | + ((my-or) #f) |

696 | + ((my-or e) e) |

697 | + ((my-or e1 e2 ...) |

698 | + (let ((temp e1)) |

699 | + (if temp |

700 | + temp |

701 | + (my-or e2 ...))))))) |

702 | + (let ((x #f) |

703 | + (y 7) |

704 | + (temp 8) |

705 | + (let odd?) |

706 | + (if even?)) |

707 | + (my-or x |

708 | + (let temp) |

709 | + (if y) |

710 | + y))) ===> 7 |

711 | + |

712 | +==== Pattern language |

713 | + |

714 | +A <transformer spec> has the following form: |

715 | + |

716 | + (syntax-rules <literals> <syntax rule> ...) |

717 | + |

718 | +Syntax: <Literals> is a list of identifiers and each <syntax rule> |

719 | +should be of the form |

720 | + |

721 | + (<pattern> <template>) |

722 | + |

723 | +The <pattern> in a <syntax rule> is a list <pattern> that begins with |

724 | +the keyword for the macro. |

725 | + |

726 | +A <pattern> is either an identifier, a constant, or one of the |

727 | +following |

728 | + |

729 | + (<pattern> ...) |

730 | + (<pattern> <pattern> ... . <pattern>) |

731 | + (<pattern> ... <pattern> <ellipsis>) |

732 | + #(<pattern> ...) |

733 | + #(<pattern> ... <pattern> <ellipsis>) |

734 | + |

735 | +and a template is either an identifier, a constant, or one of the |

736 | +following |

737 | + |

738 | + (<element> ...) |

739 | + (<element> <element> ... . <template>) |

740 | + #(<element> ...) |

741 | + |

742 | +where an <element> is a <template> optionally followed by an <ellipsis> |

743 | +and an <ellipsis> is the identifier "..." (which cannot be used as an |

744 | +identifier in either a template or a pattern). |

745 | + |

746 | +Semantics: An instance of syntax-rules produces a new macro transformer |

747 | +by specifying a sequence of hygienic rewrite rules. A use of a macro |

748 | +whose keyword is associated with a transformer specified by |

749 | +syntax-rules is matched against the patterns contained in the <syntax |

750 | +rule>s, beginning with the leftmost <syntax rule>. When a match is |

751 | +found, the macro use is transcribed hygienically according to the |

752 | +template. |

753 | + |

754 | +An identifier that appears in the pattern of a <syntax rule> is a |

755 | +pattern variable, unless it is the keyword that begins the pattern, is |

756 | +listed in <literals>, or is the identifier "...". Pattern variables |

757 | +match arbitrary input elements and are used to refer to elements of the |

758 | +input in the template. It is an error for the same pattern variable to |

759 | +appear more than once in a <pattern>. |

760 | + |

761 | +The keyword at the beginning of the pattern in a <syntax rule> is not |

762 | +involved in the matching and is not considered a pattern variable or |

763 | +literal identifier. |

764 | + |

765 | +Rationale: The scope of the keyword is determined by the |

766 | +expression or syntax definition that binds it to the associated |

767 | +macro transformer. If the keyword were a pattern variable or |

768 | +literal identifier, then the template that follows the pattern |

769 | +would be within its scope regardless of whether the keyword were |

770 | +bound by let-syntax or by letrec-syntax. |

771 | + |

772 | +Identifiers that appear in <literals> are interpreted as literal |

773 | +identifiers to be matched against corresponding subforms of the input. |

774 | +A subform in the input matches a literal identifier if and only if it |

775 | +is an identifier and either both its occurrence in the macro expression |

776 | +and its occurrence in the macro definition have the same lexical |

777 | +binding, or the two identifiers are equal and both have no lexical |

778 | +binding. |

779 | + |

780 | +A subpattern followed by ... can match zero or more elements of the |

781 | +input. It is an error for ... to appear in <literals>. Within a pattern |

782 | +the identifier ... must follow the last element of a nonempty sequence |

783 | +of subpatterns. |

784 | + |

785 | +More formally, an input form F matches a pattern P if and only if: |

786 | + |

787 | +* P is a non-literal identifier; or |

788 | + |

789 | +* P is a literal identifier and F is an identifier with the same |

790 | + binding; or |

791 | + |

792 | +* P is a list (P[1] ... P[n]) and F is a list of n forms that match P |

793 | + [1] through P[n], respectively; or |

794 | + |

795 | +* P is an improper list (P[1] P[2] ... P[n] . P[n+1]) and F is a list |

796 | + or improper list of n or more forms that match P[1] through P[n], |

797 | + respectively, and whose nth "cdr" matches P[n+1]; or |

798 | + |

799 | +* P is of the form (P[1] ... P[n] P[n+1] <ellipsis>) where <ellipsis> |

800 | + is the identifier ... and F is a proper list of at least n forms, |

801 | + the first n of which match P[1] through P[n], respectively, and |

802 | + each remaining element of F matches P[n+1]; or |

803 | + |

804 | +* P is a vector of the form #(P[1] ... P[n]) and F is a vector of n |

805 | + forms that match P[1] through P[n]; or |

806 | + |

807 | +* P is of the form #(P[1] ... P[n] P[n+1] <ellipsis>) where |

808 | + <ellipsis> is the identifier ... and F is a vector of n or more |

809 | + forms the first n of which match P[1] through P[n], respectively, |

810 | + and each remaining element of F matches P[n+1]; or |

811 | + |

812 | +* P is a datum and F is equal to P in the sense of the equal? |

813 | + procedure. |

814 | + |

815 | +It is an error to use a macro keyword, within the scope of its binding, |

816 | +in an expression that does not match any of the patterns. |

817 | + |

818 | +When a macro use is transcribed according to the template of the |

819 | +matching <syntax rule>, pattern variables that occur in the template |

820 | +are replaced by the subforms they match in the input. Pattern variables |

821 | +that occur in subpatterns followed by one or more instances of the |

822 | +identifier ... are allowed only in subtemplates that are followed by as |

823 | +many instances of .... They are replaced in the output by all of the |

824 | +subforms they match in the input, distributed as indicated. It is an |

825 | +error if the output cannot be built up as specified. |

826 | + |

827 | +Identifiers that appear in the template but are not pattern variables |

828 | +or the identifier ... are inserted into the output as literal |

829 | +identifiers. If a literal identifier is inserted as a free identifier |

830 | +then it refers to the binding of that identifier within whose scope the |

831 | +instance of syntax-rules appears. If a literal identifier is inserted |

832 | +as a bound identifier then it is in effect renamed to prevent |

833 | +inadvertent captures of free identifiers. |

834 | + |

835 | +As an example, if let and cond are defined as in section 7.3 then they |

836 | +are hygienic (as required) and the following is not an error. |

837 | + |

838 | + (let ((=> #f)) |

839 | + (cond (#t => 'ok))) ===> ok |

840 | + |

841 | +The macro transformer for cond recognizes => as a local variable, and |

842 | +hence an expression, and not as the top-level identifier =>, which the |

843 | +macro transformer treats as a syntactic keyword. Thus the example |

844 | +expands into |

845 | + |

846 | + (let ((=> #f)) |

847 | + (if #t (begin => 'ok))) |

848 | + |

849 | +instead of |

850 | + |

851 | + (let ((=> #f)) |

852 | + (let ((temp #t)) |

853 | + (if temp ('ok temp)))) |

854 | + |

855 | +which would result in an invalid procedure call. |

856 | + |

857 | +== Program structure |

858 | + |

859 | +== Standard procedures |

860 | + |

861 | +This chapter describes Scheme's built-in procedures. The initial (or |

862 | +"top level") Scheme environment starts out with a number of variables |

863 | +bound to locations containing useful values, most of which are |

864 | +primitive procedures that manipulate data. For example, the variable |

865 | +abs is bound to (a location initially containing) a procedure of one |

866 | +argument that computes the absolute value of a number, and the variable |

867 | ++ is bound to a procedure that computes sums. Built-in procedures that |

868 | +can easily be written in terms of other built-in procedures are |

869 | +identified as "library procedures". |

870 | + |

871 | +A program may use a top-level definition to bind any variable. It may |

872 | +subsequently alter any such binding by an assignment (see 4.1.6). These |

873 | +operations do not modify the behavior of Scheme's built-in procedures. |

874 | +Altering any top-level binding that has not been introduced by a |

875 | +definition has an unspecified effect on the behavior of the built-in |

876 | +procedures. |

877 | + |

878 | +=== Equivalence predicates |

879 | + |

880 | +A predicate is a procedure that always returns a boolean value (#t or #f). |

881 | +An equivalence predicate is the computational analogue of a |

882 | +mathematical equivalence relation (it is symmetric, reflexive, and |

883 | +transitive). Of the equivalence predicates described in this section, |

884 | +eq? is the finest or most discriminating, and equal? is the coarsest. |

885 | +eqv? is slightly less discriminating than eq?. |

886 | + |

887 | +<procedure>(eqv? obj[1] obj[2])</procedure><br> |

888 | + |

889 | +The eqv? procedure defines a useful equivalence relation on objects. |

890 | +Briefly, it returns #t if obj[1] and obj[2] should normally be regarded |

891 | +as the same object. This relation is left slightly open to |

892 | +interpretation, but the following partial specification of eqv? holds |

893 | +for all implementations of Scheme. |

894 | + |

895 | +The eqv? procedure returns #t if: |

896 | + |

897 | +* obj[1] and obj[2] are both #t or both #f. |

898 | + |

899 | +* obj[1] and obj[2] are both symbols and |

900 | + |

901 | + (string=? (symbol->string obj1) |

902 | + (symbol->string obj2)) |

903 | + ===> #t |

904 | + |

905 | +Note: This assumes that neither obj[1] nor obj[2] is an |

906 | +"uninterned symbol" as alluded to in section 6.3.3. This |

907 | +report does not presume to specify the behavior of eqv? on |

908 | +implementation-dependent extensions. |

909 | + |

910 | +* obj[1] and obj[2] are both numbers, are numerically equal (see =, |

911 | + section 6.2), and are either both exact or both inexact. |

912 | + |

913 | +* obj[1] and obj[2] are both characters and are the same character |

914 | + according to the char=? procedure (section 6.3.4). |

915 | + |

916 | +* both obj[1] and obj[2] are the empty list. |

917 | + |

918 | +* obj[1] and obj[2] are pairs, vectors, or strings that denote the |

919 | + same locations in the store (section 3.4). |

920 | + |

921 | +* obj[1] and obj[2] are procedures whose location tags are equal |

922 | + (section 4.1.4). |

923 | + |

924 | +The eqv? procedure returns #f if: |

925 | + |

926 | +* obj[1] and obj[2] are of different types (section 3.2). |

927 | + |

928 | +* one of obj[1] and obj[2] is #t but the other is #f. |

929 | + |

930 | +* obj[1] and obj[2] are symbols but |

931 | + |

932 | + (string=? (symbol->string obj[1]) |

933 | + (symbol->string obj[2])) |

934 | + ===> #f |

935 | + |

936 | +* one of obj[1] and obj[2] is an exact number but the other is an |

937 | + inexact number. |

938 | + |

939 | +* obj[1] and obj[2] are numbers for which the = procedure returns #f. |

940 | + |

941 | +* obj[1] and obj[2] are characters for which the char=? procedure |

942 | + returns #f. |

943 | + |

944 | +* one of obj[1] and obj[2] is the empty list but the other is not. |

945 | + |

946 | +* obj[1] and obj[2] are pairs, vectors, or strings that denote |

947 | + distinct locations. |

948 | + |

949 | +* obj[1] and obj[2] are procedures that would behave differently |

950 | + (return different value(s) or have different side effects) for some |

951 | + arguments. |

952 | + |

953 | + (eqv? 'a 'a) ===> #t |

954 | + (eqv? 'a 'b) ===> #f |

955 | + (eqv? 2 2) ===> #t |

956 | + (eqv? '() '()) ===> #t |

957 | + (eqv? 100000000 100000000) ===> #t |

958 | + (eqv? (cons 1 2) (cons 1 2)) ===> #f |

959 | + (eqv? (lambda () 1) |

960 | + (lambda () 2)) ===> #f |

961 | + (eqv? #f 'nil) ===> #f |

962 | + (let ((p (lambda (x) x))) |

963 | + (eqv? p p)) ===> #t |

964 | + |

965 | +The following examples illustrate cases in which the above rules do not |

966 | +fully specify the behavior of eqv?. All that can be said about such |

967 | +cases is that the value returned by eqv? must be a boolean. |

968 | + |

969 | + (eqv? "" "") ===> unspecified |

970 | + (eqv? '#() '#()) ===> unspecified |

971 | + (eqv? (lambda (x) x) |

972 | + (lambda (x) x)) ===> unspecified |

973 | + (eqv? (lambda (x) x) |

974 | + (lambda (y) y)) ===> unspecified |

975 | + |

976 | +The next set of examples shows the use of eqv? with procedures that |

977 | +have local state. Gen-counter must return a distinct procedure every |

978 | +time, since each procedure has its own internal counter. Gen-loser, |

979 | +however, returns equivalent procedures each time, since the local state |

980 | +does not affect the value or side effects of the procedures. |

981 | + |

982 | + (define gen-counter |

983 | + (lambda () |

984 | + (let ((n 0)) |

985 | + (lambda () (set! n (+ n 1)) n)))) |

986 | + (let ((g (gen-counter))) |

987 | + (eqv? g g)) ===> #t |

988 | + (eqv? (gen-counter) (gen-counter)) |

989 | + ===> #f |

990 | + (define gen-loser |

991 | + (lambda () |

992 | + (let ((n 0)) |

993 | + (lambda () (set! n (+ n 1)) 27)))) |

994 | + (let ((g (gen-loser))) |

995 | + (eqv? g g)) ===> #t |

996 | + (eqv? (gen-loser) (gen-loser)) |

997 | + ===> unspecified |

998 | + |

999 | + (letrec ((f (lambda () (if (eqv? f g) 'both 'f))) |

1000 | + (g (lambda () (if (eqv? f g) 'both 'g)))) |

1001 | + (eqv? f g)) |

1002 | + ===> unspecified |

1003 | + |

1004 | + (letrec ((f (lambda () (if (eqv? f g) 'f 'both))) |

1005 | + (g (lambda () (if (eqv? f g) 'g 'both)))) |

1006 | + (eqv? f g)) |

1007 | + ===> #f |

1008 | + |

1009 | +Since it is an error to modify constant objects (those returned by |

1010 | +literal expressions), implementations are permitted, though not |

1011 | +required, to share structure between constants where appropriate. Thus |

1012 | +the value of eqv? on constants is sometimes implementation-dependent. |

1013 | + |

1014 | + (eqv? '(a) '(a)) ===> unspecified |

1015 | + (eqv? "a" "a") ===> unspecified |

1016 | + (eqv? '(b) (cdr '(a b))) ===> unspecified |

1017 | + (let ((x '(a))) |

1018 | + (eqv? x x)) ===> #t |

1019 | + |

1020 | +Rationale: The above definition of eqv? allows implementations |

1021 | +latitude in their treatment of procedures and literals: |

1022 | +implementations are free either to detect or to fail to detect that |

1023 | +two procedures or two literals are equivalent to each other, and |

1024 | +can decide whether or not to merge representations of equivalent |

1025 | +objects by using the same pointer or bit pattern to represent both. |

1026 | + |

1027 | +<procedure>(eq? obj[1] obj[2])</procedure><br> |

1028 | + |

1029 | +Eq? is similar to eqv? except that in some cases it is capable of |

1030 | +discerning distinctions finer than those detectable by eqv?. |

1031 | + |

1032 | +Eq? and eqv? are guaranteed to have the same behavior on symbols, |

1033 | +booleans, the empty list, pairs, procedures, and non-empty strings and |

1034 | +vectors. Eq?'s behavior on numbers and characters is |

1035 | +implementation-dependent, but it will always return either true or |

1036 | +false, and will return true only when eqv? would also return true. Eq? |

1037 | +may also behave differently from eqv? on empty vectors and empty |

1038 | +strings. |

1039 | + |

1040 | + (eq? 'a 'a) ===> #t |

1041 | + (eq? '(a) '(a)) ===> unspecified |

1042 | + (eq? (list 'a) (list 'a)) ===> #f |

1043 | + (eq? "a" "a") ===> unspecified |

1044 | + (eq? "" "") ===> unspecified |

1045 | + (eq? '() '()) ===> #t |

1046 | + (eq? 2 2) ===> unspecified |

1047 | + (eq? #\A #\A) ===> unspecified |

1048 | + (eq? car car) ===> #t |

1049 | + (let ((n (+ 2 3))) |

1050 | + (eq? n n)) ===> unspecified |

1051 | + (let ((x '(a))) |

1052 | + (eq? x x)) ===> #t |

1053 | + (let ((x '#())) |

1054 | + (eq? x x)) ===> #t |

1055 | + (let ((p (lambda (x) x))) |

1056 | + (eq? p p)) ===> #t |

1057 | + |

1058 | +Rationale: It will usually be possible to implement eq? much more |

1059 | +efficiently than eqv?, for example, as a simple pointer comparison |

1060 | +instead of as some more complicated operation. One reason is that |

1061 | +it may not be possible to compute eqv? of two numbers in constant |

1062 | +time, whereas eq? implemented as pointer comparison will always |

1063 | +finish in constant time. Eq? may be used like eqv? in applications |

1064 | +using procedures to implement objects with state since it obeys the |

1065 | +same constraints as eqv?. |

1066 | + |

1067 | +<procedure>(equal? obj[1] obj[2])</procedure><br> |

1068 | + |

1069 | +Equal? recursively compares the contents of pairs, vectors, and |

1070 | +strings, applying eqv? on other objects such as numbers and symbols. A |

1071 | +rule of thumb is that objects are generally equal? if they print the |

1072 | +same. Equal? may fail to terminate if its arguments are circular data |

1073 | +structures. |

1074 | + |

1075 | + (equal? 'a 'a) ===> #t |

1076 | + (equal? '(a) '(a)) ===> #t |

1077 | + (equal? '(a (b) c) |

1078 | + '(a (b) c)) ===> #t |

1079 | + (equal? "abc" "abc") ===> #t |

1080 | + (equal? 2 2) ===> #t |

1081 | + (equal? (make-vector 5 'a) |

1082 | + (make-vector 5 'a)) ===> #t |

1083 | + (equal? (lambda (x) x) |

1084 | + (lambda (y) y)) ===> unspecified |

1085 | + |

1086 | +=== Numbers |

1087 | + |

1088 | +Numerical computation has traditionally been neglected by the Lisp |

1089 | +community. Until Common Lisp there was no carefully thought out |

1090 | +strategy for organizing numerical computation, and with the exception |

1091 | +of the MacLisp system [20] little effort was made to execute numerical |

1092 | +code efficiently. This report recognizes the excellent work of the |

1093 | +Common Lisp committee and accepts many of their recommendations. In |

1094 | +some ways this report simplifies and generalizes their proposals in a |

1095 | +manner consistent with the purposes of Scheme. |

1096 | + |

1097 | +It is important to distinguish between the mathematical numbers, the |

1098 | +Scheme numbers that attempt to model them, the machine representations |

1099 | +used to implement the Scheme numbers, and notations used to write |

1100 | +numbers. This report uses the types number, complex, real, rational, |

1101 | +and integer to refer to both mathematical numbers and Scheme numbers. |

1102 | +Machine representations such as fixed point and floating point are |

1103 | +referred to by names such as fixnum and flonum. |

1104 | + |

1105 | +==== Numerical types |

1106 | + |

1107 | +Mathematically, numbers may be arranged into a tower of subtypes in |

1108 | +which each level is a subset of the level above it: |

1109 | + |

1110 | + number |

1111 | + complex |

1112 | + real |

1113 | + rational |

1114 | + integer |

1115 | + |

1116 | +For example, 3 is an integer. Therefore 3 is also a rational, a real, |

1117 | +and a complex. The same is true of the Scheme numbers that model 3. For |

1118 | +Scheme numbers, these types are defined by the predicates number?, |

1119 | +complex?, real?, rational?, and integer?. |

1120 | + |

1121 | +There is no simple relationship between a number's type and its |

1122 | +representation inside a computer. Although most implementations of |

1123 | +Scheme will offer at least two different representations of 3, these |

1124 | +different representations denote the same integer. |

1125 | + |

1126 | +Scheme's numerical operations treat numbers as abstract data, as |

1127 | +independent of their representation as possible. Although an |

1128 | +implementation of Scheme may use fixnum, flonum, and perhaps other |

1129 | +representations for numbers, this should not be apparent to a casual |

1130 | +programmer writing simple programs. |

1131 | + |

1132 | +It is necessary, however, to distinguish between numbers that are |

1133 | +represented exactly and those that may not be. For example, indexes |

1134 | +into data structures must be known exactly, as must some polynomial |

1135 | +coefficients in a symbolic algebra system. On the other hand, the |

1136 | +results of measurements are inherently inexact, and irrational numbers |

1137 | +may be approximated by rational and therefore inexact approximations. |

1138 | +In order to catch uses of inexact numbers where exact numbers are |

1139 | +required, Scheme explicitly distinguishes exact from inexact numbers. |

1140 | +This distinction is orthogonal to the dimension of type. |

1141 | + |

1142 | +==== Exactness |

1143 | + |

1144 | +Scheme numbers are either exact or inexact. A number is exact if it was |

1145 | +written as an exact constant or was derived from exact numbers using |

1146 | +only exact operations. A number is inexact if it was written as an |

1147 | +inexact constant, if it was derived using inexact ingredients, or if it |

1148 | +was derived using inexact operations. Thus inexactness is a contagious |

1149 | +property of a number. If two implementations produce exact results for |

1150 | +a computation that did not involve inexact intermediate results, the |

1151 | +two ultimate results will be mathematically equivalent. This is |

1152 | +generally not true of computations involving inexact numbers since |

1153 | +approximate methods such as floating point arithmetic may be used, but |

1154 | +it is the duty of each implementation to make the result as close as |

1155 | +practical to the mathematically ideal result. |

1156 | + |

1157 | +Rational operations such as + should always produce exact results when |

1158 | +given exact arguments. If the operation is unable to produce an exact |

1159 | +result, then it may either report the violation of an implementation |

1160 | +restriction or it may silently coerce its result to an inexact value. |

1161 | +See section 6.2.3. |

1162 | + |

1163 | +With the exception of inexact->exact, the operations described in this |

1164 | +section must generally return inexact results when given any inexact |

1165 | +arguments. An operation may, however, return an exact result if it can |

1166 | +prove that the value of the result is unaffected by the inexactness of |

1167 | +its arguments. For example, multiplication of any number by an exact |

1168 | +zero may produce an exact zero result, even if the other argument is |

1169 | +inexact. |

1170 | + |

1171 | +==== Implementation restrictions |

1172 | + |

1173 | +Implementations of Scheme are not required to implement the whole tower |

1174 | +of subtypes given in section 6.2.1, but they must implement a coherent |

1175 | +subset consistent with both the purposes of the implementation and the |

1176 | +spirit of the Scheme language. For example, an implementation in which |

1177 | +all numbers are real may still be quite useful. |

1178 | + |

1179 | +Implementations may also support only a limited range of numbers of any |

1180 | +type, subject to the requirements of this section. The supported range |

1181 | +for exact numbers of any type may be different from the supported range |

1182 | +for inexact numbers of that type. For example, an implementation that |

1183 | +uses flonums to represent all its inexact real numbers may support a |

1184 | +practically unbounded range of exact integers and rationals while |

1185 | +limiting the range of inexact reals (and therefore the range of inexact |

1186 | +integers and rationals) to the dynamic range of the flonum format. |

1187 | +Furthermore the gaps between the representable inexact integers and |

1188 | +rationals are likely to be very large in such an implementation as the |

1189 | +limits of this range are approached. |

1190 | + |

1191 | +An implementation of Scheme must support exact integers throughout the |

1192 | +range of numbers that may be used for indexes of lists, vectors, and |

1193 | +strings or that may result from computing the length of a list, vector, |

1194 | +or string. The length, vector-length, and string-length procedures must |

1195 | +return an exact integer, and it is an error to use anything but an |

1196 | +exact integer as an index. Furthermore any integer constant within the |

1197 | +index range, if expressed by an exact integer syntax, will indeed be |

1198 | +read as an exact integer, regardless of any implementation restrictions |

1199 | +that may apply outside this range. Finally, the procedures listed below |

1200 | +will always return an exact integer result provided all their arguments |

1201 | +are exact integers and the mathematically expected result is |

1202 | +representable as an exact integer within the implementation: |

1203 | + |

1204 | + + - * |

1205 | + quotient remainder modulo |

1206 | + max min abs |

1207 | + numerator denominator gcd |

1208 | + lcm floor ceiling |

1209 | + truncate round rationalize |

1210 | + expt |

1211 | + |

1212 | +Implementations are encouraged, but not required, to support exact |

1213 | +integers and exact rationals of practically unlimited size and |

1214 | +precision, and to implement the above procedures and the / procedure in |

1215 | +such a way that they always return exact results when given exact |

1216 | +arguments. If one of these procedures is unable to deliver an exact |

1217 | +result when given exact arguments, then it may either report a |

1218 | +violation of an implementation restriction or it may silently coerce |

1219 | +its result to an inexact number. Such a coercion may cause an error |

1220 | +later. |

1221 | + |

1222 | +An implementation may use floating point and other approximate |

1223 | +representation strategies for inexact numbers. This report recommends, |

1224 | +but does not require, that the IEEE 32-bit and 64-bit floating point |

1225 | +standards be followed by implementations that use flonum |

1226 | +representations, and that implementations using other representations |

1227 | +should match or exceed the precision achievable using these floating |

1228 | +point standards [12]. |

1229 | + |

1230 | +In particular, implementations that use flonum representations must |

1231 | +follow these rules: A flonum result must be represented with at least |

1232 | +as much precision as is used to express any of the inexact arguments to |

1233 | +that operation. It is desirable (but not required) for potentially |

1234 | +inexact operations such as sqrt, when applied to exact arguments, to |

1235 | +produce exact answers whenever possible (for example the square root of |

1236 | +an exact 4 ought to be an exact 2). If, however, an exact number is |

1237 | +operated upon so as to produce an inexact result (as by sqrt), and if |

1238 | +the result is represented as a flonum, then the most precise flonum |

1239 | +format available must be used; but if the result is represented in some |

1240 | +other way then the representation must have at least as much precision |

1241 | +as the most precise flonum format available. |

1242 | + |

1243 | +Although Scheme allows a variety of written notations for numbers, any |

1244 | +particular implementation may support only some of them. For example, |

1245 | +an implementation in which all numbers are real need not support the |

1246 | +rectangular and polar notations for complex numbers. If an |

1247 | +implementation encounters an exact numerical constant that it cannot |

1248 | +represent as an exact number, then it may either report a violation of |

1249 | +an implementation restriction or it may silently represent the constant |

1250 | +by an inexact number. |

1251 | + |

1252 | +==== Syntax of numerical constants |

1253 | + |

1254 | +The syntax of the written representations for numbers is described |

1255 | +formally in section 7.1.1. Note that case is not significant in |

1256 | +numerical constants. |

1257 | + |

1258 | +A number may be written in binary, octal, decimal, or hexadecimal by |

1259 | +the use of a radix prefix. The radix prefixes are #b (binary), #o |

1260 | +(octal), #d (decimal), and #x (hexadecimal). With no radix prefix, a |

1261 | +number is assumed to be expressed in decimal. |

1262 | + |

1263 | +A numerical constant may be specified to be either exact or inexact by |

1264 | +a prefix. The prefixes are #e for exact, and #i for inexact. An |

1265 | +exactness prefix may appear before or after any radix prefix that is |

1266 | +used. If the written representation of a number has no exactness |

1267 | +prefix, the constant may be either inexact or exact. It is inexact if |

1268 | +it contains a decimal point, an exponent, or a "#" character in the |

1269 | +place of a digit, otherwise it is exact. In systems with inexact |

1270 | +numbers of varying precisions it may be useful to specify the precision |

1271 | +of a constant. For this purpose, numerical constants may be written |

1272 | +with an exponent marker that indicates the desired precision of the |

1273 | +inexact representation. The letters s, f, d, and l specify the use of |

1274 | +short, single, double, and long precision, respectively. (When fewer |

1275 | +than four internal inexact representations exist, the four size |

1276 | +specifications are mapped onto those available. For example, an |

1277 | +implementation with two internal representations may map short and |

1278 | +single together and long and double together.) In addition, the |

1279 | +exponent marker e specifies the default precision for the |

1280 | +implementation. The default precision has at least as much precision as |

1281 | +double, but implementations may wish to allow this default to be set by |

1282 | +the user. |

1283 | + |

1284 | + 3.14159265358979F0 |

1285 | + Round to single --- 3.141593 |

1286 | + 0.6L0 |

1287 | + Extend to long --- .600000000000000 |

1288 | + |

1289 | +==== Numerical operations |

1290 | + |

1291 | +The reader is referred to section 1.3.3 for a summary of the naming |

1292 | +conventions used to specify restrictions on the types of arguments to |

1293 | +numerical routines. The examples used in this section assume that any |

1294 | +numerical constant written using an exact notation is indeed |

1295 | +represented as an exact number. Some examples also assume that certain |

1296 | +numerical constants written using an inexact notation can be |

1297 | +represented without loss of accuracy; the inexact constants were chosen |

1298 | +so that this is likely to be true in implementations that use flonums |

1299 | +to represent inexact numbers. |

1300 | + |

1301 | +<procedure>(number? obj)</procedure><br> |

1302 | +<procedure>(complex? obj)</procedure><br> |

1303 | +<procedure>(real? obj)</procedure><br> |

1304 | +<procedure>(rational? obj)</procedure><br> |

1305 | +<procedure>(integer? obj)</procedure><br> |

1306 | + |

1307 | +These numerical type predicates can be applied to any kind of argument, |

1308 | +including non-numbers. They return #t if the object is of the named |

1309 | +type, and otherwise they return #f. In general, if a type predicate is |

1310 | +true of a number then all higher type predicates are also true of that |

1311 | +number. Consequently, if a type predicate is false of a number, then |

1312 | +all lower type predicates are also false of that number. If z is an |

1313 | +inexact complex number, then (real? z) is true if and only if (zero? |

1314 | +(imag-part z)) is true. If x is an inexact real number, then (integer? |

1315 | +x) is true if and only if (= x (round x)). |

1316 | + |

1317 | + (complex? 3+4i) ===> #t |

1318 | + (complex? 3) ===> #t |

1319 | + (real? 3) ===> #t |

1320 | + (real? -2.5+0.0i) ===> #t |

1321 | + (real? #e1e10) ===> #t |

1322 | + (rational? 6/10) ===> #t |

1323 | + (rational? 6/3) ===> #t |

1324 | + (integer? 3+0i) ===> #t |

1325 | + (integer? 3.0) ===> #t |

1326 | + (integer? 8/4) ===> #t |

1327 | + |

1328 | +Note: The behavior of these type predicates on inexact numbers is |

1329 | +unreliable, since any inaccuracy may affect the result. |

1330 | + |

1331 | +Note: In many implementations the rational? procedure will be the |

1332 | +same as real?, and the complex? procedure will be the same as |

1333 | +number?, but unusual implementations may be able to represent some |

1334 | +irrational numbers exactly or may extend the number system to |

1335 | +support some kind of non-complex numbers. |

1336 | + |

1337 | +<procedure>(exact? z)</procedure><br> |

1338 | +<procedure>(inexact? z)</procedure><br> |

1339 | + |

1340 | +These numerical predicates provide tests for the exactness of a |

1341 | +quantity. For any Scheme number, precisely one of these predicates is |

1342 | +true. |

1343 | + |

1344 | +<procedure>(= z[1] z[2] z[3] ...)</procedure><br> |

1345 | +<procedure>(< x[1] x[2] x[3] ...)</procedure><br> |

1346 | +<procedure>(> x[1] x[2] x[3] ...)</procedure><br> |

1347 | +<procedure>(<= x[1] x[2] x[3] ...)</procedure><br> |

1348 | +<procedure>(>= x[1] x[2] x[3] ...)</procedure><br> |

1349 | + |

1350 | +These procedures return #t if their arguments are (respectively): |

1351 | +equal, monotonically increasing, monotonically decreasing, |

1352 | +monotonically nondecreasing, or monotonically nonincreasing. |

1353 | + |

1354 | +These predicates are required to be transitive. |

1355 | + |

1356 | +Note: The traditional implementations of these predicates in |

1357 | +Lisp-like languages are not transitive. |

1358 | + |

1359 | +Note: While it is not an error to compare inexact numbers using |

1360 | +these predicates, the results may be unreliable because a small |

1361 | +inaccuracy may affect the result; this is especially true of = and |

1362 | +zero?. When in doubt, consult a numerical analyst. |

1363 | + |

1364 | +<procedure>(zero? z)</procedure><br> |

1365 | +<procedure>(positive? x)</procedure><br> |

1366 | +<procedure>(negative? x)</procedure><br> |

1367 | +<procedure>(odd? n)</procedure><br> |

1368 | +<procedure>(even? n)</procedure><br> |

1369 | + |

1370 | +These numerical predicates test a number for a particular property, |

1371 | +returning #t or #f. See note above. |

1372 | + |

1373 | +<procedure>(max x[1] x[2] ...)</procedure><br> |

1374 | +<procedure>(min x[1] x[2] ...)</procedure><br> |

1375 | + |

1376 | +These procedures return the maximum or minimum of their arguments. |

1377 | + |

1378 | + (max 3 4) ===> 4 ; exact |

1379 | + (max 3.9 4) ===> 4.0 ; inexact |

1380 | + |

1381 | +Note: If any argument is inexact, then the result will also be |

1382 | +inexact (unless the procedure can prove that the inaccuracy is not |

1383 | +large enough to affect the result, which is possible only in |

1384 | +unusual implementations). If min or max is used to compare numbers |

1385 | +of mixed exactness, and the numerical value of the result cannot be |

1386 | +represented as an inexact number without loss of accuracy, then the |

1387 | +procedure may report a violation of an implementation restriction. |

1388 | + |

1389 | +<procedure>(+ z[1] ...)</procedure><br> |

1390 | +<procedure>(* z[1] ...)</procedure><br> |

1391 | + |

1392 | +These procedures return the sum or product of their arguments. |

1393 | + |

1394 | + (+ 3 4) ===> 7 |

1395 | + (+ 3) ===> 3 |

1396 | + (+) ===> 0 |

1397 | + (* 4) ===> 4 |

1398 | + (*) ===> 1 |

1399 | + |

1400 | +<procedure>(- z[1] z[2])</procedure><br> |

1401 | +<procedure>(- z)</procedure><br> |

1402 | +<procedure>(- z[1] z[2] ...)</procedure><br> |

1403 | +<procedure>(/ z[1] z[2])</procedure><br> |

1404 | +<procedure>(/ z)</procedure><br> |

1405 | +<procedure>(/ z[1] z[2] ...)</procedure><br> |

1406 | + |

1407 | +With two or more arguments, these procedures return the difference or |

1408 | +quotient of their arguments, associating to the left. With one |

1409 | +argument, however, they return the additive or multiplicative inverse |

1410 | +of their argument. |

1411 | + |

1412 | + (- 3 4) ===> -1 |

1413 | + (- 3 4 5) ===> -6 |

1414 | + (- 3) ===> -3 |

1415 | + (/ 3 4 5) ===> 3/20 |

1416 | + (/ 3) ===> 1/3 |

1417 | + |

1418 | +<procedure>(abs x)</procedure><br> |

1419 | + |

1420 | +Abs returns the absolute value of its argument. |

1421 | + |

1422 | + (abs -7) ===> 7 |

1423 | + |

1424 | +<procedure>(quotient n[1] n[2])</procedure><br> |

1425 | +<procedure>(remainder n[1] n[2])</procedure><br> |

1426 | +<procedure>(modulo n[1] n[2])</procedure><br> |

1427 | + |

1428 | +These procedures implement number-theoretic (integer) division. n[2] |

1429 | +should be non-zero. All three procedures return integers. If n[1]/n[2] |

1430 | +is an integer: |

1431 | + |

1432 | + (quotient n[1] n[2]) ===> n[1]/n[2] |

1433 | + (remainder n[1] n[2]) ===> 0 |

1434 | + (modulo n[1] n[2]) ===> 0 |

1435 | + |

1436 | +If n[1]/n[2] is not an integer: |

1437 | + |

1438 | + (quotient n[1] n[2]) ===> n[q] |

1439 | + (remainder n[1] n[2]) ===> n[r] |

1440 | + (modulo n[1] n[2]) ===> n[m] |

1441 | + |

1442 | +where n[q] is n[1]/n[2] rounded towards zero, 0 < |n[r]| < |n[2]|, 0 < |

1443 | +|n[m]| < |n[2]|, n[r] and n[m] differ from n[1] by a multiple of n[2], |

1444 | +n[r] has the same sign as n[1], and n[m] has the same sign as n[2]. |

1445 | + |

1446 | +From this we can conclude that for integers n[1] and n[2] with n[2] not |

1447 | +equal to 0, |

1448 | + |

1449 | + (= n[1] (+ (* n[2] (quotient n[1] n[2])) |

1450 | + (remainder n[1] n[2]))) |

1451 | + ===> #t |

1452 | + |

1453 | +provided all numbers involved in that computation are exact. |

1454 | + |

1455 | + (modulo 13 4) ===> 1 |

1456 | + (remainder 13 4) ===> 1 |

1457 | + |

1458 | + (modulo -13 4) ===> 3 |

1459 | + (remainder -13 4) ===> -1 |

1460 | + |

1461 | + (modulo 13 -4) ===> -3 |

1462 | + (remainder 13 -4) ===> 1 |

1463 | + |

1464 | + (modulo -13 -4) ===> -1 |

1465 | + (remainder -13 -4) ===> -1 |

1466 | + |

1467 | + (remainder -13 -4.0) ===> -1.0 ; inexact |

1468 | + |

1469 | +<procedure>(gcd n[1] ...)</procedure><br> |

1470 | +<procedure>(lcm n[1] ...)</procedure><br> |

1471 | + |

1472 | +These procedures return the greatest common divisor or least common |

1473 | +multiple of their arguments. The result is always non-negative. |

1474 | + |

1475 | + (gcd 32 -36) ===> 4 |

1476 | + (gcd) ===> 0 |

1477 | + (lcm 32 -36) ===> 288 |

1478 | + (lcm 32.0 -36) ===> 288.0 ; inexact |

1479 | + (lcm) ===> 1 |

1480 | + |

1481 | +<procedure>(numerator q)</procedure><br> |

1482 | +<procedure>(denominator q)</procedure><br> |

1483 | + |

1484 | +These procedures return the numerator or denominator of their argument; |

1485 | +the result is computed as if the argument was represented as a fraction |

1486 | +in lowest terms. The denominator is always positive. The denominator of |

1487 | +0 is defined to be 1. |

1488 | + |

1489 | + (numerator (/ 6 4)) ===> 3 |

1490 | + (denominator (/ 6 4)) ===> 2 |

1491 | + (denominator |

1492 | + (exact->inexact (/ 6 4))) ===> 2.0 |

1493 | + |

1494 | +<procedure>(floor x)</procedure><br> |

1495 | +<procedure>(ceiling x)</procedure><br> |

1496 | +<procedure>(truncate x)</procedure><br> |

1497 | +<procedure>(round x)</procedure><br> |

1498 | + |

1499 | +These procedures return integers. Floor returns the largest integer not |

1500 | +larger than x. Ceiling returns the smallest integer not smaller than x. |

1501 | +Truncate returns the integer closest to x whose absolute value is not |

1502 | +larger than the absolute value of x. Round returns the closest integer |

1503 | +to x, rounding to even when x is halfway between two integers. |

1504 | + |

1505 | +Rationale: Round rounds to even for consistency with the default |

1506 | +rounding mode specified by the IEEE floating point standard. |

1507 | + |

1508 | +Note: If the argument to one of these procedures is inexact, then |

1509 | +the result will also be inexact. If an exact value is needed, the |

1510 | +result should be passed to the inexact->exact procedure. |

1511 | + |

1512 | + (floor -4.3) ===> -5.0 |

1513 | + (ceiling -4.3) ===> -4.0 |

1514 | + (truncate -4.3) ===> -4.0 |

1515 | + (round -4.3) ===> -4.0 |

1516 | + |

1517 | + (floor 3.5) ===> 3.0 |

1518 | + (ceiling 3.5) ===> 4.0 |

1519 | + (truncate 3.5) ===> 3.0 |

1520 | + (round 3.5) ===> 4.0 ; inexact |

1521 | + |

1522 | + (round 7/2) ===> 4 ; exact |

1523 | + (round 7) ===> 7 |

1524 | + |

1525 | +<procedure>(rationalize x y)</procedure><br> |

1526 | + |

1527 | +Rationalize returns the simplest rational number differing from x by no |

1528 | +more than y. A rational number r[1] is simpler than another rational |

1529 | +number r[2] if r[1] = p[1]/q[1] and r[2] = p[2]/q[2] (in lowest terms) |

1530 | +and |p[1]| < |p[2]| and |q[1]| < |q[2]|. Thus 3/5 is simpler than 4/7. |

1531 | +Although not all rationals are comparable in this ordering (consider 2/ |

1532 | +7 and 3/5) any interval contains a rational number that is simpler than |

1533 | +every other rational number in that interval (the simpler 2/5 lies |

1534 | +between 2/7 and 3/5). Note that 0 = 0/1 is the simplest rational of |

1535 | +all. |

1536 | + |

1537 | + (rationalize |

1538 | + (inexact->exact .3) 1/10) ===> 1/3 ; exact |

1539 | + (rationalize .3 1/10) ===> #i1/3 ; inexact |

1540 | + |

1541 | +<procedure>(exp z)</procedure><br> |

1542 | +<procedure>(log z)</procedure><br> |

1543 | +<procedure>(sin z)</procedure><br> |

1544 | +<procedure>(cos z)</procedure><br> |

1545 | +<procedure>(tan z)</procedure><br> |

1546 | +<procedure>(asin z)</procedure><br> |

1547 | +<procedure>(acos z)</procedure><br> |

1548 | +<procedure>(atan z)</procedure><br> |

1549 | +<procedure>(atan y x)</procedure><br> |

1550 | + |

1551 | +These procedures are part of every implementation that supports general |

1552 | +real numbers; they compute the usual transcendental functions. Log |

1553 | +computes the natural logarithm of z (not the base ten logarithm). Asin, |

1554 | +acos, and atan compute arcsine (sin^-1), arccosine (cos^-1), and |

1555 | +arctangent (tan^-1), respectively. The two-argument variant of atan |

1556 | +computes (angle (make-rectangular x y)) (see below), even in |

1557 | +implementations that don't support general complex numbers. |

1558 | + |

1559 | +In general, the mathematical functions log, arcsine, arccosine, and |

1560 | +arctangent are multiply defined. The value of log z is defined to be |

1561 | +the one whose imaginary part lies in the range from -pi |

1562 | +(exclusive) to pi (inclusive). log 0 is undefined. With log |

1563 | +defined this way, the values of sin^-1 z, cos^-1 z, and tan^-1 z are |

1564 | +according to the following formulae: |

1565 | + |

1566 | + sin^-1 z = - i log (i z + (1 - z^2)^1/2) |

1567 | + |

1568 | + cos^-1 z = pi / 2 - sin^-1 z |

1569 | + |

1570 | + tan^-1 z = (log (1 + i z) - log (1 - i z)) / (2 i) |

1571 | + |

1572 | +The above specification follows [27], which in turn cites [19]; refer |

1573 | +to these sources for more detailed discussion of branch cuts, boundary |

1574 | +conditions, and implementation of these functions. When it is possible |

1575 | +these procedures produce a real result from a real argument. |

1576 | + |

1577 | +<procedure>(sqrt z)</procedure><br> |

1578 | + |

1579 | +Returns the principal square root of z. The result will have either |

1580 | +positive real part, or zero real part and non-negative imaginary part. |

1581 | + |

1582 | +<procedure>(expt z[1] z[2])</procedure><br> |

1583 | + |

1584 | +Returns z[1] raised to the power z[2]. For z[1] != 0 |

1585 | + |

1586 | + z[1]^z[2] = e^z[2] log z[1] |

1587 | + |

1588 | +0^z is 1 if z = 0 and 0 otherwise. |

1589 | + |

1590 | +<procedure>(make-rectangular x[1] x[2])</procedure><br> |

1591 | +<procedure>(make-polar x[3] x[4])</procedure><br> |

1592 | +<procedure>(real-part z)</procedure><br> |

1593 | +<procedure>(imag-part z)</procedure><br> |

1594 | +<procedure>(magnitude z)</procedure><br> |

1595 | +<procedure>(angle z)</procedure><br> |

1596 | + |

1597 | +These procedures are part of every implementation that supports general |

1598 | +complex numbers. Suppose x[1], x[2], x[3], and x[4] are real numbers |

1599 | +and z is a complex number such that |

1600 | + |

1601 | + z = x[1] + x[2]i = x[3] . e^i x[4] |

1602 | + |

1603 | +Then |

1604 | + |

1605 | + (make-rectangular x[1] x[2]) ===> z |

1606 | + (make-polar x[3] x[4]) ===> z |

1607 | + (real-part z) ===> x[1] |

1608 | + (imag-part z) ===> x[2] |

1609 | + (magnitude z) ===> |x[3]| |

1610 | + (angle z) ===> x[angle] |

1611 | + |

1612 | +where - pi < x[angle] < pi with x[angle] = x[4] + 2 pi n |

1613 | +for some integer n. |

1614 | + |

1615 | +Rationale: Magnitude is the same as abs for a real argument, but |

1616 | +abs must be present in all implementations, whereas magnitude need |

1617 | +only be present in implementations that support general complex |

1618 | +numbers. |

1619 | + |

1620 | +<procedure>(exact->inexact z)</procedure><br> |

1621 | +<procedure>(inexact->exact z)</procedure><br> |

1622 | + |

1623 | +Exact->inexact returns an inexact representation of z. The value |

1624 | +returned is the inexact number that is numerically closest to the |

1625 | +argument. If an exact argument has no reasonably close inexact |

1626 | +equivalent, then a violation of an implementation restriction may be |

1627 | +reported. |

1628 | + |

1629 | +Inexact->exact returns an exact representation of z. The value returned |

1630 | +is the exact number that is numerically closest to the argument. If an |

1631 | +inexact argument has no reasonably close exact equivalent, then a |

1632 | +violation of an implementation restriction may be reported. |

1633 | + |

1634 | +These procedures implement the natural one-to-one correspondence |

1635 | +between exact and inexact integers throughout an |

1636 | +implementation-dependent range. See section 6.2.3. |

1637 | + |

1638 | +==== Numerical input and output |

1639 | + |

1640 | +<procedure>(number->string z)</procedure><br> |

1641 | +<procedure>(number->string z radix)</procedure><br> |

1642 | + |

1643 | +Radix must be an exact integer, either 2, 8, 10, or 16. If omitted, radix |

1644 | +defaults to 10. The procedure number->string takes a number and a |

1645 | +radix and returns as a string an external representation of the given |

1646 | +number in the given radix such that |

1647 | + |

1648 | + (let ((number number) |

1649 | + (radix radix)) |

1650 | + (eqv? number |

1651 | + (string->number (number->string number |

1652 | + radix) |

1653 | + radix))) |

1654 | + |

1655 | +is true. It is an error if no possible result makes this expression |

1656 | +true. |

1657 | + |

1658 | +If z is inexact, the radix is 10, and the above expression can be |

1659 | +satisfied by a result that contains a decimal point, then the result |

1660 | +contains a decimal point and is expressed using the minimum number of |

1661 | +digits (exclusive of exponent and trailing zeroes) needed to make the |

1662 | +above expression true [3, 5]; otherwise the format of the result is |

1663 | +unspecified. |

1664 | + |

1665 | +The result returned by number->string never contains an explicit radix |

1666 | +prefix. |

1667 | + |

1668 | +Note: The error case can occur only when z is not a complex |

1669 | +number or is a complex number with a non-rational real or imaginary |

1670 | +part. |

1671 | + |

1672 | +Rationale: If z is an inexact number represented using flonums, |

1673 | +and the radix is 10, then the above expression is normally |

1674 | +satisfied by a result containing a decimal point. The unspecified |

1675 | +case allows for infinities, NaNs, and non-flonum representations. |

1676 | + |

1677 | +<procedure>(string->number string)</procedure><br> |

1678 | +<procedure>(string->number string radix)</procedure><br> |

1679 | + |

1680 | +Returns a number of the maximally precise representation expressed by |

1681 | +the given string. Radix must be an exact integer, either 2, 8, 10, or |

1682 | +16. If supplied, radix is a default radix that may be overridden by an |

1683 | +explicit radix prefix in string (e.g. "#o177"). If radix is not |

1684 | +supplied, then the default radix is 10. If string is not a |

1685 | +syntactically valid notation for a number, then string->number |

1686 | +returns #f. |

1687 | + |

1688 | + (string->number "100") ===> 100 |

1689 | + (string->number "100" 16) ===> 256 |

1690 | + (string->number "1e2") ===> 100.0 |

1691 | + (string->number "15##") ===> 1500.0 |

1692 | + |

1693 | +Note: The domain of string->number may be restricted by |

1694 | +implementations in the following ways. String->number is permitted |

1695 | +to return #f whenever string contains an explicit radix prefix. If |

1696 | +all numbers supported by an implementation are real, then string-> |

1697 | +number is permitted to return #f whenever string uses the polar or |

1698 | +rectangular notations for complex numbers. If all numbers are |

1699 | +integers, then string->number may return #f whenever the fractional |

1700 | +notation is used. If all numbers are exact, then string->number may |

1701 | +return #f whenever an exponent marker or explicit exactness prefix |

1702 | +is used, or if a # appears in place of a digit. If all inexact |

1703 | +numbers are integers, then string->number may return #f whenever a |

1704 | +decimal point is used. |

1705 | + |

1706 | +=== Other data types |

1707 | + |

1708 | +This section describes operations on some of Scheme's non-numeric data |

1709 | +types: booleans, pairs, lists, symbols, characters, strings and |

1710 | +vectors. |

1711 | + |

1712 | +==== Booleans |

1713 | + |

1714 | +The standard boolean objects for true and false are written as #t and #f. |

1715 | +What really matters, though, are the objects that the Scheme |

1716 | +conditional expressions (if, cond, and, or, do) treat as true or false. |

1717 | +The phrase "a true value" (or sometimes just "true") means any |

1718 | +object treated as true by the conditional expressions, and the phrase |

1719 | +"a false value" (or "false") means any object treated as false by |

1720 | +the conditional expressions. |

1721 | + |

1722 | +Of all the standard Scheme values, only #f counts as false in |

1723 | +conditional expressions. Except for #f, all standard Scheme values, |

1724 | +including #t, pairs, the empty list, symbols, numbers, strings, |

1725 | +vectors, and procedures, count as true. |

1726 | + |

1727 | +Note: Programmers accustomed to other dialects of Lisp should be |

1728 | +aware that Scheme distinguishes both #f and the empty list from the |

1729 | +symbol nil. |

1730 | + |

1731 | +Boolean constants evaluate to themselves, so they do not need to be |

1732 | +quoted in programs. |

1733 | + |

1734 | + #t ===> #t |

1735 | + #f ===> #f |

1736 | + '#f ===> #f |

1737 | + |

1738 | +<procedure>(not obj)</procedure><br> |

1739 | + |

1740 | +Not returns #t if obj is false, and returns #f otherwise. |

1741 | + |

1742 | + (not #t) ===> #f |

1743 | + (not 3) ===> #f |

1744 | + (not (list 3)) ===> #f |

1745 | + (not #f) ===> #t |

1746 | + (not '()) ===> #f |

1747 | + (not (list)) ===> #f |

1748 | + (not 'nil) ===> #f |

1749 | + |

1750 | +<procedure>(boolean? obj)</procedure><br> |

1751 | + |

1752 | +Boolean? returns #t if obj is either #t or #f and returns #f otherwise. |

1753 | + |

1754 | + (boolean? #f) ===> #t |

1755 | + (boolean? 0) ===> #f |

1756 | + (boolean? '()) ===> #f |

1757 | + |

1758 | +==== Pairs and lists |

1759 | + |

1760 | +A pair (sometimes called a dotted pair) is a record structure with two |

1761 | +fields called the car and cdr fields (for historical reasons). Pairs |

1762 | +are created by the procedure cons. The car and cdr fields are accessed |

1763 | +by the procedures car and cdr. The car and cdr fields are assigned by |

1764 | +the procedures set-car! and set-cdr!. |

1765 | + |

1766 | +Pairs are used primarily to represent lists. A list can be defined |

1767 | +recursively as either the empty list or a pair whose cdr is a list. |

1768 | +More precisely, the set of lists is defined as the smallest set X such |

1769 | +that |

1770 | + |

1771 | +* The empty list is in X. |

1772 | +* If list is in X, then any pair whose cdr field contains list is |

1773 | + also in X. |

1774 | + |

1775 | +The objects in the car fields of successive pairs of a list are the |

1776 | +elements of the list. For example, a two-element list is a pair whose |

1777 | +car is the first element and whose cdr is a pair whose car is the |

1778 | +second element and whose cdr is the empty list. The length of a list is |

1779 | +the number of elements, which is the same as the number of pairs. |

1780 | + |

1781 | +The empty list is a special object of its own type (it is not a pair); |

1782 | +it has no elements and its length is zero. |

1783 | + |

1784 | +Note: The above definitions imply that all lists have finite |

1785 | +length and are terminated by the empty list. |

1786 | + |

1787 | +The most general notation (external representation) for Scheme pairs is |

1788 | +the "dotted" notation (c[1] . c[2]) where c[1] is the value of the |

1789 | +car field and c[2] is the value of the cdr field. For example (4 . 5) |

1790 | +is a pair whose car is 4 and whose cdr is 5. Note that (4 . 5) is the |

1791 | +external representation of a pair, not an expression that evaluates to |

1792 | +a pair. |

1793 | + |

1794 | +A more streamlined notation can be used for lists: the elements of the |

1795 | +list are simply enclosed in parentheses and separated by spaces. The |

1796 | +empty list is written () . For example, |

1797 | + |

1798 | + (a b c d e) |

1799 | + |

1800 | +and |

1801 | + |

1802 | + (a . (b . (c . (d . (e . ()))))) |

1803 | + |

1804 | +are equivalent notations for a list of symbols. |

1805 | + |

1806 | +A chain of pairs not ending in the empty list is called an improper |

1807 | +list. Note that an improper list is not a list. The list and dotted |

1808 | +notations can be combined to represent improper lists: |

1809 | + |

1810 | + (a b c . d) |

1811 | + |

1812 | +is equivalent to |

1813 | + |

1814 | + (a . (b . (c . d))) |

1815 | + |

1816 | +Whether a given pair is a list depends upon what is stored in the cdr |

1817 | +field. When the set-cdr! procedure is used, an object can be a list one |

1818 | +moment and not the next: |

1819 | + |

1820 | + (define x (list 'a 'b 'c)) |

1821 | + (define y x) |

1822 | + y ===> (a b c) |

1823 | + (list? y) ===> #t |

1824 | + (set-cdr! x 4) ===> unspecified |

1825 | + x ===> (a . 4) |

1826 | + (eqv? x y) ===> #t |

1827 | + y ===> (a . 4) |

1828 | + (list? y) ===> #f |

1829 | + (set-cdr! x x) ===> unspecified |

1830 | + (list? x) ===> #f |

1831 | + |

1832 | +Within literal expressions and representations of objects read by the |

1833 | +read procedure, the forms '<datum>, `<datum>, ,<datum>, and ,@<datum> |

1834 | +denote two-element lists whose first elements are the symbols quote, |

1835 | +quasiquote, unquote, and unquote-splicing, respectively. The second |

1836 | +element in each case is <datum>. This convention is supported so that |

1837 | +arbitrary Scheme programs may be represented as lists. That is, |

1838 | +according to Scheme's grammar, every <expression> is also a <datum> |

1839 | +(see section 7.1.2). Among other things, this permits the use of the |

1840 | +read procedure to parse Scheme programs. See section 3.3. |

1841 | + |

1842 | +<procedure>(pair? obj)</procedure><br> |

1843 | + |

1844 | +Pair? returns #t if obj is a pair, and otherwise returns #f. |

1845 | + |

1846 | + (pair? '(a . b)) ===> #t |

1847 | + (pair? '(a b c)) ===> #t |

1848 | + (pair? '()) ===> #f |

1849 | + (pair? '#(a b)) ===> #f |

1850 | + |

1851 | +<procedure>(cons obj[1] obj[2])</procedure><br> |

1852 | + |

1853 | +Returns a newly allocated pair whose car is obj[1] and whose cdr is |

1854 | +obj[2]. The pair is guaranteed to be different (in the sense of eqv?) |

1855 | +from every existing object. |

1856 | + |

1857 | + (cons 'a '()) ===> (a) |

1858 | + (cons '(a) '(b c d)) ===> ((a) b c d) |

1859 | + (cons "a" '(b c)) ===> ("a" b c) |

1860 | + (cons 'a 3) ===> (a . 3) |

1861 | + (cons '(a b) 'c) ===> ((a b) . c) |

1862 | + |

1863 | +<procedure>(car pair)</procedure><br> |

1864 | + |

1865 | +Returns the contents of the car field of pair. Note that it is an error |

1866 | +to take the car of the empty list. |

1867 | + |

1868 | + (car '(a b c)) ===> a |

1869 | + (car '((a) b c d)) ===> (a) |

1870 | + (car '(1 . 2)) ===> 1 |

1871 | + (car '()) ===> error |

1872 | + |

1873 | +<procedure>(cdr pair)</procedure><br> |

1874 | + |

1875 | +Returns the contents of the cdr field of pair. Note that it is an error |

1876 | +to take the cdr of the empty list. |

1877 | + |

1878 | + (cdr '((a) b c d)) ===> (b c d) |

1879 | + (cdr '(1 . 2)) ===> 2 |

1880 | + (cdr '()) ===> error |

1881 | + |

1882 | +<procedure>(set-car! pair obj)</procedure><br> |

1883 | + |

1884 | +Stores obj in the car field of pair. The value returned by set-car! is |

1885 | +unspecified. |

1886 | + |

1887 | + (define (f) (list 'not-a-constant-list)) |

1888 | + (define (g) '(constant-list)) |

1889 | + (set-car! (f) 3) ===> unspecified |

1890 | + (set-car! (g) 3) ===> error |

1891 | + |

1892 | +<procedure>(set-cdr! pair obj)</procedure><br> |

1893 | + |

1894 | +Stores obj in the cdr field of pair. The value returned by set-cdr! is |

1895 | +unspecified. |

1896 | + |

1897 | +<procedure>(caar pair)</procedure><br> |

1898 | +<procedure>(cadr pair)</procedure><br> |

1899 | +<procedure>(cdddar pair)</procedure><br> |

1900 | +<procedure>(cddddr pair)</procedure><br> |

1901 | + |

1902 | +These procedures are compositions of car and cdr, where for example |

1903 | +caddr could be defined by |

1904 | + |

1905 | + (define caddr (lambda (x) (car (cdr (cdr x))))). |

1906 | + |

1907 | +Arbitrary compositions, up to four deep, are provided. There are |

1908 | +twenty-eight of these procedures in all. |

1909 | + |

1910 | +<procedure>(null? obj)</procedure><br> |

1911 | + |

1912 | +Returns #t if obj is the empty list, otherwise returns #f. |

1913 | + |

1914 | +<procedure>(list? obj)</procedure><br> |

1915 | + |

1916 | +Returns #t if obj is a list, otherwise returns #f. By definition, all |

1917 | +lists have finite length and are terminated by the empty list. |

1918 | + |

1919 | + (list? '(a b c)) ===> #t |

1920 | + (list? '()) ===> #t |

1921 | + (list? '(a . b)) ===> #f |

1922 | + (let ((x (list 'a))) |

1923 | + (set-cdr! x x) |

1924 | + (list? x)) ===> #f |

1925 | + |

1926 | +<procedure>(list obj ...)</procedure><br> |

1927 | + |

1928 | +Returns a newly allocated list of its arguments. |

1929 | + |

1930 | + (list 'a (+ 3 4) 'c) ===> (a 7 c) |

1931 | + (list) ===> () |

1932 | + |

1933 | +<procedure>(length list)</procedure><br> |

1934 | + |

1935 | +Returns the length of list. |

1936 | + |

1937 | + (length '(a b c)) ===> 3 |

1938 | + (length '(a (b) (c d e))) ===> 3 |

1939 | + (length '()) ===> 0 |

1940 | + |

1941 | +<procedure>(append list ...)</procedure><br> |

1942 | + |

1943 | +Returns a list consisting of the elements of the first list followed by |

1944 | +the elements of the other lists. |

1945 | + |

1946 | + (append '(x) '(y)) ===> (x y) |

1947 | + (append '(a) '(b c d)) ===> (a b c d) |

1948 | + (append '(a (b)) '((c))) ===> (a (b) (c)) |

1949 | + |

1950 | +The resulting list is always newly allocated, except that it shares |

1951 | +structure with the last list argument. The last argument may actually |

1952 | +be any object; an improper list results if the last argument is not a |

1953 | +proper list. |

1954 | + |

1955 | + (append '(a b) '(c . d)) ===> (a b c . d) |

1956 | + (append '() 'a) ===> a |

1957 | + |

1958 | +<procedure>(reverse list)</procedure><br> |

1959 | + |

1960 | +Returns a newly allocated list consisting of the elements of list in |

1961 | +reverse order. |

1962 | + |

1963 | + (reverse '(a b c)) ===> (c b a) |

1964 | + (reverse '(a (b c) d (e (f)))) |

1965 | + ===> ((e (f)) d (b c) a) |

1966 | + |

1967 | +<procedure>(list-tail list k)</procedure><br> |

1968 | + |

1969 | +Returns the sublist of list obtained by omitting the first k elements. |

1970 | +It is an error if list has fewer than k elements. List-tail could be |

1971 | +defined by |

1972 | + |

1973 | + (define list-tail |

1974 | + (lambda (x k) |

1975 | + (if (zero? k) |

1976 | + x |

1977 | + (list-tail (cdr x) (- k 1))))) |

1978 | + |

1979 | +<procedure>(list-ref list k)</procedure><br> |

1980 | + |

1981 | +Returns the kth element of list. (This is the same as the car of |

1982 | +(list-tail list k).) It is an error if list has fewer than k elements. |

1983 | + |

1984 | + (list-ref '(a b c d) 2) ===> c |

1985 | + (list-ref '(a b c d) |

1986 | + (inexact->exact (round 1.8))) |

1987 | + ===> c |

1988 | + |

1989 | +<procedure>(memq obj list)</procedure><br> |

1990 | +<procedure>(memv obj list)</procedure><br> |

1991 | +<procedure>(member obj list)</procedure><br> |

1992 | + |

1993 | +These procedures return the first sublist of list whose car is obj, |

1994 | +where the sublists of list are the non-empty lists returned by |

1995 | +(list-tail list k) for k less than the length of list. If obj does not |

1996 | +occur in list, then #f (not the empty list) is returned. Memq uses eq? |

1997 | +to compare obj with the elements of list, while memv uses eqv? and |

1998 | +member uses equal?. |

1999 | + |

2000 | + (memq 'a '(a b c)) ===> (a b c) |

2001 | + (memq 'b '(a b c)) ===> (b c) |

2002 | + (memq 'a '(b c d)) ===> #f |

2003 | + (memq (list 'a) '(b (a) c)) ===> #f |

2004 | + (member (list 'a) |

2005 | + '(b (a) c)) ===> ((a) c) |

2006 | + (memq 101 '(100 101 102)) ===> unspecified |

2007 | + (memv 101 '(100 101 102)) ===> (101 102) |

2008 | + |

2009 | +<procedure>(assq obj alist)</procedure><br> |

2010 | +<procedure>(assv obj alist)</procedure><br> |

2011 | +<procedure>(assoc obj alist)</procedure><br> |

2012 | + |

2013 | +Alist (for "association list") must be a list of pairs. These |

2014 | +procedures find the first pair in alist whose car field is obj, and |

2015 | +returns that pair. If no pair in alist has obj as its car, then #f (not |

2016 | +the empty list) is returned. Assq uses eq? to compare obj with the car |

2017 | +fields of the pairs in alist, while assv uses eqv? and assoc uses |

2018 | +equal?. |

2019 | + |

2020 | + (define e '((a 1) (b 2) (c 3))) |

2021 | + (assq 'a e) ===> (a 1) |

2022 | + (assq 'b e) ===> (b 2) |

2023 | + (assq 'd e) ===> #f |

2024 | + (assq (list 'a) '(((a)) ((b)) ((c)))) |

2025 | + ===> #f |

2026 | + (assoc (list 'a) '(((a)) ((b)) ((c)))) |

2027 | + ===> ((a)) |

2028 | + (assq 5 '((2 3) (5 7) (11 13))) |

2029 | + ===> unspecified |

2030 | + (assv 5 '((2 3) (5 7) (11 13))) |

2031 | + ===> (5 7) |

2032 | + |

2033 | +Rationale: Although they are ordinarily used as predicates, memq, |

2034 | +memv, member, assq, assv, and assoc do not have question marks in |

2035 | +their names because they return useful values rather than just #t |

2036 | +or #f. |

2037 | + |

2038 | +==== Symbols |

2039 | + |

2040 | +Symbols are objects whose usefulness rests on the fact that two symbols |

2041 | +are identical (in the sense of eqv?) if and only if their names are |

2042 | +spelled the same way. This is exactly the property needed to represent |

2043 | +identifiers in programs, and so most implementations of Scheme use them |

2044 | +internally for that purpose. Symbols are useful for many other |

2045 | +applications; for instance, they may be used the way enumerated values |

2046 | +are used in Pascal. |

2047 | + |

2048 | +The rules for writing a symbol are exactly the same as the rules for |

2049 | +writing an identifier; see sections 2.1 and 7.1.1. |

2050 | + |

2051 | +It is guaranteed that any symbol that has been returned as part of a |

2052 | +literal expression, or read using the read procedure, and subsequently |

2053 | +written out using the write procedure, will read back in as the |

2054 | +identical symbol (in the sense of eqv?). The string->symbol procedure, |

2055 | +however, can create symbols for which this write/read invariance may |

2056 | +not hold because their names contain special characters or letters in |

2057 | +the non-standard case. |

2058 | + |

2059 | +Note: Some implementations of Scheme have a feature known as |

2060 | +"slashification" in order to guarantee write/read invariance for |

2061 | +all symbols, but historically the most important use of this |

2062 | +feature has been to compensate for the lack of a string data type. |

2063 | + |

2064 | +Some implementations also have "uninterned symbols", which defeat |

2065 | +write/read invariance even in implementations with slashification, |

2066 | +and also generate exceptions to the rule that two symbols are the |

2067 | +same if and only if their names are spelled the same. |

2068 | + |

2069 | +<procedure>(symbol? obj)</procedure><br> |

2070 | + |

2071 | +Returns #t if obj is a symbol, otherwise returns #f. |

2072 | + |

2073 | + (symbol? 'foo) ===> #t |

2074 | + (symbol? (car '(a b))) ===> #t |

2075 | + (symbol? "bar") ===> #f |

2076 | + (symbol? 'nil) ===> #t |

2077 | + (symbol? '()) ===> #f |

2078 | + (symbol? #f) ===> #f |

2079 | + |

2080 | +<procedure>(symbol->string symbol)</procedure><br> |

2081 | + |

2082 | +Returns the name of symbol as a string. If the symbol was part of an |

2083 | +object returned as the value of a literal expression (section 4.1.2) or |

2084 | +by a call to the read procedure, and its name contains alphabetic |

2085 | +characters, then the string returned will contain characters in the |

2086 | +implementation's preferred standard case -- some implementations will |

2087 | +prefer upper case, others lower case. If the symbol was returned by |

2088 | +string->symbol, the case of characters in the string returned will be |

2089 | +the same as the case in the string that was passed to string->symbol. |

2090 | +It is an error to apply mutation procedures like string-set! to strings |

2091 | +returned by this procedure. |

2092 | + |

2093 | +The following examples assume that the implementation's standard case |

2094 | +is lower case: |

2095 | + |

2096 | + (symbol->string 'flying-fish) |

2097 | + ===> "flying-fish" |

2098 | + (symbol->string 'Martin) ===> "martin" |

2099 | + (symbol->string |

2100 | + (string->symbol "Malvina")) |

2101 | + ===> "Malvina" |

2102 | + |

2103 | +<procedure>(string->symbol string)</procedure><br> |

2104 | + |

2105 | +Returns the symbol whose name is string. This procedure can create |

2106 | +symbols with names containing special characters or letters in the |

2107 | +non-standard case, but it is usually a bad idea to create such symbols |

2108 | +because in some implementations of Scheme they cannot be read as |

2109 | +themselves. See symbol->string. |

2110 | + |

2111 | +The following examples assume that the implementation's standard case |

2112 | +is lower case: |

2113 | + |

2114 | + (eq? 'mISSISSIppi 'mississippi) |

2115 | + ===> #t |

2116 | + (string->symbol "mISSISSIppi") |

2117 | + ===> the symbol with name "mISSISSIppi" |

2118 | + (eq? 'bitBlt (string->symbol "bitBlt")) |

2119 | + ===> #f |

2120 | + (eq? 'JollyWog |

2121 | + (string->symbol |

2122 | + (symbol->string 'JollyWog))) |

2123 | + ===> #t |

2124 | + (string=? "K. Harper, M.D." |

2125 | + (symbol->string |

2126 | + (string->symbol "K. Harper, M.D."))) |

2127 | + ===> #t |

2128 | + |

2129 | +==== Characters |

2130 | + |

2131 | +Characters are objects that represent printed characters such as |

2132 | +letters and digits. Characters are written using the notation #\ |

2133 | +<character> or #\<character name>. For example: |

2134 | + |

2135 | + #\a ; lower case letter |

2136 | + #\A ; upper case letter |

2137 | + #\( ; left parenthesis |

2138 | + #\ ; the space character |

2139 | + #\space ; the preferred way to write a space |

2140 | + #\newline ; the newline character |

2141 | + |

2142 | +Case is significant in #\<character>, but not in #\<character name>. If |

2143 | +<character> in #\<character> is alphabetic, then the character |

2144 | +following <character> must be a delimiter character such as a space or |

2145 | +parenthesis. This rule resolves the ambiguous case where, for example, |

2146 | +the sequence of characters "#\space" could be taken to be either a |

2147 | +representation of the space character or a representation of the |

2148 | +character "#\s" followed by a representation of the symbol "pace." |

2149 | + |

2150 | +Characters written in the #\ notation are self-evaluating. That is, |

2151 | +they do not have to be quoted in programs. Some of the procedures that |

2152 | +operate on characters ignore the difference between upper case and |

2153 | +lower case. The procedures that ignore case have "-ci" (for "case |

2154 | +insensitive") embedded in their names. |

2155 | + |

2156 | +<procedure>(char? obj)</procedure><br> |

2157 | + |

2158 | +Returns #t if obj is a character, otherwise returns #f. |

2159 | + |

2160 | +<procedure>(char=? char[1] char[2])</procedure><br> |

2161 | +<procedure>(char<? char[1] char[2])</procedure><br> |

2162 | +<procedure>(char>? char[1] char[2])</procedure><br> |

2163 | +<procedure>(char<=? char[1] char[2])</procedure><br> |

2164 | +<procedure>(char>=? char[1] char[2])</procedure><br> |

2165 | + |

2166 | +These procedures impose a total ordering on the set of characters. It |

2167 | +is guaranteed that under this ordering: |

2168 | + |

2169 | +* The upper case characters are in order. For example, (char<? #\A #\ |

2170 | + B) returns #t. |

2171 | +* The lower case characters are in order. For example, (char<? #\a #\ |

2172 | + b) returns #t. |

2173 | +* The digits are in order. For example, (char<? #\0 #\9) returns #t. |

2174 | +* Either all the digits precede all the upper case letters, or vice |

2175 | + versa. |

2176 | +* Either all the digits precede all the lower case letters, or vice |

2177 | + versa. |

2178 | + |

2179 | +Some implementations may generalize these procedures to take more than |

2180 | +two arguments, as with the corresponding numerical predicates. |

2181 | + |

2182 | +<procedure>(char-ci=? char[1] char[2])</procedure><br> |

2183 | +<procedure>(char-ci<? char[1] char[2])</procedure><br> |

2184 | +<procedure>(char-ci>? char[1] char[2])</procedure><br> |

2185 | +<procedure>(char-ci<=? char[1] char[2])</procedure><br> |

2186 | +<procedure>(char-ci>=? char[1] char[2])</procedure><br> |

2187 | + |

2188 | +These procedures are similar to char=? et cetera, but they treat upper |

2189 | +case and lower case letters as the same. For example, (char-ci=? #\A #\ |

2190 | +a) returns #t. Some implementations may generalize these procedures to |

2191 | +take more than two arguments, as with the corresponding numerical |

2192 | +predicates. |

2193 | + |

2194 | +<procedure>(char-alphabetic? char)</procedure><br> |

2195 | +<procedure>(char-numeric? char)</procedure><br> |

2196 | +<procedure>(char-whitespace? char)</procedure><br> |

2197 | +<procedure>(char-upper-case? letter)</procedure><br> |

2198 | +<procedure>(char-lower-case? letter)</procedure><br> |

2199 | + |

2200 | +These procedures return #t if their arguments are alphabetic, numeric, |

2201 | +whitespace, upper case, or lower case characters, respectively, |

2202 | +otherwise they return #f. The following remarks, which are specific to |

2203 | +the ASCII character set, are intended only as a guide: The alphabetic |

2204 | +characters are the 52 upper and lower case letters. The numeric |

2205 | +characters are the ten decimal digits. The whitespace characters are |

2206 | +space, tab, line feed, form feed, and carriage return. |

2207 | + |

2208 | +<procedure>(char->integer char)</procedure><br> |

2209 | +<procedure>(integer->char n)</procedure><br> |

2210 | + |

2211 | +Given a character, char->integer returns an exact integer |

2212 | +representation of the character. Given an exact integer that is the |

2213 | +image of a character under char->integer, integer->char returns that |

2214 | +character. These procedures implement order-preserving isomorphisms |

2215 | +between the set of characters under the char<=? ordering and some |

2216 | +subset of the integers under the <= ordering. That is, if |

2217 | + |

2218 | + (char<=? a b) ===> #t and (<= x y) ===> #t |

2219 | + |

2220 | +and x and y are in the domain of integer->char, then |

2221 | + |

2222 | + (<= (char->integer a) |

2223 | + (char->integer b)) ===> #t |

2224 | + |

2225 | + (char<=? (integer->char x) |

2226 | + (integer->char y)) ===> #t |

2227 | + |

2228 | +<procedure>(char-upcase char)</procedure><br> |

2229 | +<procedure>(char-downcase char)</procedure><br> |

2230 | + |

2231 | +These procedures return a character char[2] such that (char-ci=? char |

2232 | +char[2]). In addition, if char is alphabetic, then the result of |

2233 | +char-upcase is upper case and the result of char-downcase is lower |

2234 | +case. |

2235 | + |

2236 | +==== Strings |

2237 | + |

2238 | +Strings are sequences of characters. Strings are written as sequences |

2239 | +of characters enclosed within doublequotes ("). A doublequote can be |

2240 | +written inside a string only by escaping it with a backslash (\), as in |

2241 | + |

2242 | +"The word \"recursion\" has many meanings." |

2243 | + |

2244 | +A backslash can be written inside a string only by escaping it with |

2245 | +another backslash. Scheme does not specify the effect of a backslash |

2246 | +within a string that is not followed by a doublequote or backslash. |

2247 | + |

2248 | +A string constant may continue from one line to the next, but the exact |

2249 | +contents of such a string are unspecified. The length of a string is |

2250 | +the number of characters that it contains. This number is an exact, |

2251 | +non-negative integer that is fixed when the string is created. The |

2252 | +valid indexes of a string are the exact non-negative integers less than |

2253 | +the length of the string. The first character of a string has index 0, |

2254 | +the second has index 1, and so on. |

2255 | + |

2256 | +In phrases such as "the characters of string beginning with index |

2257 | +start and ending with index end," it is understood that the index |

2258 | +start is inclusive and the index end is exclusive. Thus if start and |

2259 | +end are the same index, a null substring is referred to, and if start |

2260 | +is zero and end is the length of string, then the entire string is |

2261 | +referred to. |

2262 | + |

2263 | +Some of the procedures that operate on strings ignore the difference |

2264 | +between upper and lower case. The versions that ignore case have |

2265 | +"-ci" (for "case insensitive") embedded in their names. |

2266 | + |

2267 | +<procedure>(string? obj)</procedure><br> |

2268 | + |

2269 | +Returns #t if obj is a string, otherwise returns #f. |

2270 | + |

2271 | +<procedure>(make-string k)</procedure><br> |

2272 | +<procedure>(make-string k char)</procedure><br> |

2273 | + |

2274 | +Make-string returns a newly allocated string of length k. If char is |

2275 | +given, then all elements of the string are initialized to char, |

2276 | +otherwise the contents of the string are unspecified. |

2277 | + |

2278 | +<procedure>(string char ...)</procedure><br> |

2279 | + |

2280 | +Returns a newly allocated string composed of the arguments. |

2281 | + |

2282 | +<procedure>(string-length string)</procedure><br> |

2283 | + |

2284 | +Returns the number of characters in the given string. |

2285 | + |

2286 | +<procedure>(string-ref string k)</procedure><br> |

2287 | + |

2288 | +k must be a valid index of string. String-ref returns character k of |

2289 | +string using zero-origin indexing. |

2290 | + |

2291 | +<procedure>(string-set! string k char)</procedure><br> |

2292 | + |

2293 | +k must be a valid index of string. String-set! stores char in element k |

2294 | +of string and returns an unspecified value. |

2295 | + |

2296 | + (define (f) (make-string 3 #\*)) |

2297 | + (define (g) "***") |

2298 | + (string-set! (f) 0 #\?) ===> unspecified |

2299 | + (string-set! (g) 0 #\?) ===> error |

2300 | + (string-set! (symbol->string 'immutable) |

2301 | + 0 |

2302 | + #\?) ===> error |

2303 | + |

2304 | +<procedure>(string=? string[1] string[2])</procedure><br> |

2305 | +<procedure>(string-ci=? string[1] string[2])</procedure><br> |

2306 | + |

2307 | +Returns #t if the two strings are the same length and contain the same |

2308 | +characters in the same positions, otherwise returns #f. String-ci=? |

2309 | +treats upper and lower case letters as though they were the same |

2310 | +character, but string=? treats upper and lower case as distinct |

2311 | +characters. |

2312 | + |

2313 | +<procedure>(string<? string[1] string[2])</procedure><br> |

2314 | +<procedure>(string>? string[1] string[2])</procedure><br> |

2315 | +<procedure>(string<=? string[1] string[2])</procedure><br> |

2316 | +<procedure>(string>=? string[1] string[2])</procedure><br> |

2317 | +<procedure>(string-ci<? string[1] string[2])</procedure><br> |

2318 | +<procedure>(string-ci>? string[1] string[2])</procedure><br> |

2319 | +<procedure>(string-ci<=? string[1] string[2])</procedure><br> |

2320 | +<procedure>(string-ci>=? string[1] string[2])</procedure><br> |

2321 | + |

2322 | +These procedures are the lexicographic extensions to strings of the |

2323 | +corresponding orderings on characters. For example, string<? is the |

2324 | +lexicographic ordering on strings induced by the ordering char<? on |

2325 | +characters. If two strings differ in length but are the same up to the |

2326 | +length of the shorter string, the shorter string is considered to be |

2327 | +lexicographically less than the longer string. |

2328 | + |

2329 | +Implementations may generalize these and the string=? and string-ci=? |

2330 | +procedures to take more than two arguments, as with the corresponding |

2331 | +numerical predicates. |

2332 | + |

2333 | +<procedure>(substring string start end)</procedure><br> |

2334 | + |

2335 | +String must be a string, and start and end must be exact integers |

2336 | +satisfying |

2337 | + |

2338 | + 0 < start < end < (string-length string) |

2339 | + |

2340 | +Substring returns a newly allocated string formed from the characters |

2341 | +of string beginning with index start (inclusive) and ending with index |

2342 | +end (exclusive). |

2343 | + |

2344 | +<procedure>(string-append string ...)</procedure><br> |

2345 | + |

2346 | +Returns a newly allocated string whose characters form the |

2347 | +concatenation of the given strings. |

2348 | + |

2349 | +<procedure>(string->list string)</procedure><br> |

2350 | +<procedure>(list->string list)</procedure><br> |

2351 | + |

2352 | +String->list returns a newly allocated list of the characters that make |

2353 | +up the given string. List->string returns a newly allocated string |

2354 | +formed from the characters in the list list, which must be a list of |

2355 | +characters. String->list and list->string are inverses so far as equal? |

2356 | +is concerned. |

2357 | + |

2358 | +<procedure>(string-copy string)</procedure><br> |

2359 | + |

2360 | +Returns a newly allocated copy of the given string. |

2361 | + |

2362 | +<procedure>(string-fill! string char)</procedure><br> |

2363 | + |

2364 | +Stores char in every element of the given string and returns an |

2365 | +unspecified value. |

2366 | + |

2367 | +==== Vectors |

2368 | + |

2369 | +Vectors are heterogenous structures whose elements are indexed by |

2370 | +integers. A vector typically occupies less space than a list of the |

2371 | +same length, and the average time required to access a randomly chosen |

2372 | +element is typically less for the vector than for the list. |

2373 | + |

2374 | +The length of a vector is the number of elements that it contains. This |

2375 | +number is a non-negative integer that is fixed when the vector is |

2376 | +created. The valid indexes of a vector are the exact non-negative |

2377 | +integers less than the length of the vector. The first element in a |

2378 | +vector is indexed by zero, and the last element is indexed by one less |

2379 | +than the length of the vector. |

2380 | + |

2381 | +Vectors are written using the notation #(obj ...). For example, a |

2382 | +vector of length 3 containing the number zero in element 0, the list (2 |

2383 | +2 2 2) in element 1, and the string "Anna" in element 2 can be written |

2384 | +as following: |

2385 | + |

2386 | + #(0 (2 2 2 2) "Anna") |

2387 | + |

2388 | +Note that this is the external representation of a vector, not an |

2389 | +expression evaluating to a vector. Like list constants, vector |

2390 | +constants must be quoted: |

2391 | + |

2392 | + '#(0 (2 2 2 2) "Anna") |

2393 | + ===> #(0 (2 2 2 2) "Anna") |

2394 | + |

2395 | +<procedure>(vector? obj)</procedure><br> |

2396 | + |

2397 | +Returns #t if obj is a vector, otherwise returns #f. |

2398 | + |

2399 | +<procedure>(make-vector k)</procedure><br> |

2400 | +<procedure>(make-vector k fill)</procedure><br> |

2401 | + |

2402 | +Returns a newly allocated vector of k elements. If a second argument is |

2403 | +given, then each element is initialized to fill. Otherwise the initial |

2404 | +contents of each element is unspecified. |

2405 | + |

2406 | +<procedure>(vector obj ...)</procedure><br> |

2407 | + |

2408 | +Returns a newly allocated vector whose elements contain the given |

2409 | +arguments. Analogous to list. |

2410 | + |

2411 | + (vector 'a 'b 'c) ===> #(a b c) |

2412 | + |

2413 | +<procedure>(vector-length vector)</procedure><br> |

2414 | + |

2415 | +Returns the number of elements in vector as an exact integer. |

2416 | + |

2417 | +<procedure>(vector-ref vector k)</procedure><br> |

2418 | + |

2419 | +k must be a valid index of vector. Vector-ref returns the contents of |

2420 | +element k of vector. |

2421 | + |

2422 | + (vector-ref '#(1 1 2 3 5 8 13 21) |

2423 | + 5) |

2424 | + ===> 8 |

2425 | + (vector-ref '#(1 1 2 3 5 8 13 21) |

2426 | + (let ((i (round (* 2 (acos -1))))) |

2427 | + (if (inexact? i) |

2428 | + (inexact->exact i) |

2429 | + i))) |

2430 | + ===> 13 |

2431 | + |

2432 | +<procedure>(vector-set! vector k obj)</procedure><br> |

2433 | + |

2434 | +k must be a valid index of vector. Vector-set! stores obj in element k |

2435 | +of vector. The value returned by vector-set! is unspecified. |

2436 | + |

2437 | + (let ((vec (vector 0 '(2 2 2 2) "Anna"))) |

2438 | + (vector-set! vec 1 '("Sue" "Sue")) |

2439 | + vec) |

2440 | + ===> #(0 ("Sue" "Sue") "Anna") |

2441 | + |

2442 | + (vector-set! '#(0 1 2) 1 "doe") |

2443 | + ===> error ; constant vector |

2444 | + |

2445 | +<procedure>(vector->list vector)</procedure><br> |

2446 | +<procedure>(list->vector list)</procedure><br> |

2447 | + |

2448 | +Vector->list returns a newly allocated list of the objects contained in |

2449 | +the elements of vector. List->vector returns a newly created vector |

2450 | +initialized to the elements of the list list. |

2451 | + |

2452 | + (vector->list '#(dah dah didah)) |

2453 | + ===> (dah dah didah) |

2454 | + (list->vector '(dididit dah)) |

2455 | + ===> #(dididit dah) |

2456 | + |

2457 | +<procedure>(vector-fill! vector fill)</procedure><br> |

2458 | + |

2459 | +Stores fill in every element of vector. The value returned by |

2460 | +vector-fill! is unspecified. |

2461 | + |

2462 | +=== Control features |

2463 | + |

2464 | +This chapter describes various primitive procedures which control the |

2465 | +flow of program execution in special ways. The procedure? predicate is |

2466 | +also described here. |

2467 | + |

2468 | +<procedure>(procedure? obj)</procedure><br> |

2469 | + |

2470 | +Returns #t if obj is a procedure, otherwise returns #f. |

2471 | + |

2472 | + (procedure? car) ===> #t |

2473 | + (procedure? 'car) ===> #f |

2474 | + (procedure? (lambda (x) (* x x))) |

2475 | + ===> #t |

2476 | + (procedure? '(lambda (x) (* x x))) |

2477 | + ===> #f |

2478 | + (call-with-current-continuation procedure?) |

2479 | + ===> #t |

2480 | + |

2481 | +<procedure>(apply proc arg[1] ... args)</procedure><br> |

2482 | + |

2483 | +Proc must be a procedure and args must be a list. Calls proc with the |

2484 | +elements of the list (append (list arg[1] ...) args) as the actual |

2485 | +arguments. |

2486 | + |

2487 | + (apply + (list 3 4)) ===> 7 |

2488 | + |

2489 | + (define compose |

2490 | + (lambda (f g) |

2491 | + (lambda args |

2492 | + (f (apply g args))))) |

2493 | + |

2494 | + ((compose sqrt *) 12 75) ===> 30 |

2495 | + |

2496 | +<procedure>(map proc list[1] list[2] ...)</procedure><br> |

2497 | + |

2498 | +The lists must be lists, and proc must be a procedure taking as many |

2499 | +arguments as there are lists and returning a single value. If more than |

2500 | +one list is given, then they must all be the same length. Map applies |

2501 | +proc element-wise to the elements of the lists and returns a list of |

2502 | +the results, in order. The dynamic order in which proc is applied to |

2503 | +the elements of the lists is unspecified. |

2504 | + |

2505 | + (map cadr '((a b) (d e) (g h))) |

2506 | + ===> (b e h) |

2507 | + |

2508 | + (map (lambda (n) (expt n n)) |

2509 | + '(1 2 3 4 5)) |

2510 | + ===> (1 4 27 256 3125) |

2511 | + |

2512 | + (map + '(1 2 3) '(4 5 6)) ===> (5 7 9) |

2513 | + |

2514 | + (let ((count 0)) |

2515 | + (map (lambda (ignored) |

2516 | + (set! count (+ count 1)) |

2517 | + count) |

2518 | + '(a b))) ===> (1 2) or (2 1) |

2519 | + |

2520 | +<procedure>(for-each proc list[1] list[2] ...)</procedure><br> |

2521 | + |

2522 | +The arguments to for-each are like the arguments to map, but for-each |

2523 | +calls proc for its side effects rather than for its values. Unlike map, |

2524 | +for-each is guaranteed to call proc on the elements of the lists in |

2525 | +order from the first element(s) to the last, and the value returned by |

2526 | +for-each is unspecified. |

2527 | + |

2528 | + (let ((v (make-vector 5))) |

2529 | + (for-each (lambda (i) |

2530 | + (vector-set! v i (* i i))) |

2531 | + '(0 1 2 3 4)) |

2532 | + v) ===> #(0 1 4 9 16) |

2533 | + |

2534 | +<procedure>(force promise)</procedure><br> |

2535 | + |

2536 | +Forces the value of promise (see delay, section 4.2.5). If no value has |

2537 | +been computed for the promise, then a value is computed and returned. |

2538 | +The value of the promise is cached (or "memoized") so that if it is |

2539 | +forced a second time, the previously computed value is returned. |

2540 | + |

2541 | + (force (delay (+ 1 2))) ===> 3 |

2542 | + (let ((p (delay (+ 1 2)))) |

2543 | + (list (force p) (force p))) |

2544 | + ===> (3 3) |

2545 | + |

2546 | + (define a-stream |

2547 | + (letrec ((next |

2548 | + (lambda (n) |

2549 | + (cons n (delay (next (+ n 1))))))) |

2550 | + (next 0))) |

2551 | + (define head car) |

2552 | + (define tail |

2553 | + (lambda (stream) (force (cdr stream)))) |

2554 | + |

2555 | + (head (tail (tail a-stream))) |

2556 | + ===> 2 |

2557 | + |

2558 | +Force and delay are mainly intended for programs written in functional |

2559 | +style. The following examples should not be considered to illustrate |

2560 | +good programming style, but they illustrate the property that only one |

2561 | +value is computed for a promise, no matter how many times it is forced. |

2562 | + |

2563 | + (define count 0) |

2564 | + (define p |

2565 | + (delay (begin (set! count (+ count 1)) |

2566 | + (if (> count x) |

2567 | + count |

2568 | + (force p))))) |

2569 | + (define x 5) |

2570 | + p ===> a promise |

2571 | + (force p) ===> 6 |

2572 | + p ===> a promise, still |

2573 | + (begin (set! x 10) |

2574 | + (force p)) ===> 6 |

2575 | + |

2576 | +Here is a possible implementation of delay and force. Promises are |

2577 | +implemented here as procedures of no arguments, and force simply calls |

2578 | +its argument: |

2579 | + |

2580 | + (define force |

2581 | + (lambda (object) |

2582 | + (object))) |

2583 | + |

2584 | +We define the expression |

2585 | + |

2586 | + (delay <expression>) |

2587 | + |

2588 | +to have the same meaning as the procedure call |

2589 | + |

2590 | + (make-promise (lambda () <expression>)) |

2591 | + |

2592 | +as follows |

2593 | + |

2594 | + (define-syntax delay |

2595 | + (syntax-rules () |

2596 | + ((delay expression) |

2597 | + (make-promise (lambda () expression))))), |

2598 | + |

2599 | +where make-promise is defined as follows: |

2600 | + |

2601 | + (define make-promise |

2602 | + (lambda (proc) |

2603 | + (let ((result-ready? #f) |

2604 | + (result #f)) |

2605 | + (lambda () |

2606 | + (if result-ready? |

2607 | + result |

2608 | + (let ((x (proc))) |

2609 | + (if result-ready? |

2610 | + result |

2611 | + (begin (set! result-ready? #t) |

2612 | + (set! result x) |

2613 | + result)))))))) |

2614 | + |

2615 | +Rationale: A promise may refer to its own value, as in the last |

2616 | +example above. Forcing such a promise may cause the promise to be |

2617 | +forced a second time before the value of the first force has been |

2618 | +computed. This complicates the definition of make-promise. |

2619 | + |

2620 | +Various extensions to this semantics of delay and force are supported |

2621 | +in some implementations: |

2622 | + |

2623 | +* Calling force on an object that is not a promise may simply return |

2624 | + the object. |

2625 | + |

2626 | +* It may be the case that there is no means by which a promise can be |

2627 | + operationally distinguished from its forced value. That is, |

2628 | + expressions like the following may evaluate to either #t or to #f, |

2629 | + depending on the implementation: |

2630 | + |

2631 | + (eqv? (delay 1) 1) ===> unspecified |

2632 | + (pair? (delay (cons 1 2))) ===> unspecified |

2633 | + |

2634 | +* Some implementations may implement "implicit forcing," where the |

2635 | + value of a promise is forced by primitive procedures like cdr and |

2636 | + +: |

2637 | + |

2638 | + (+ (delay (* 3 7)) 13) ===> 34 |

2639 | + |

2640 | +<procedure>(call-with-current-continuation proc)</procedure><br> |

2641 | + |

2642 | +Proc must be a procedure of one argument. The procedure |

2643 | +call-with-current-continuation packages up the current continuation |

2644 | +(see the rationale below) as an "escape procedure" and passes it as |

2645 | +an argument to proc. The escape procedure is a Scheme procedure that, |

2646 | +if it is later called, will abandon whatever continuation is in effect |

2647 | +at that later time and will instead use the continuation that was in |

2648 | +effect when the escape procedure was created. Calling the escape |

2649 | +procedure may cause the invocation of before and after thunks installed |

2650 | +using dynamic-wind. |

2651 | + |

2652 | +The escape procedure accepts the same number of arguments as the |

2653 | +continuation to the original call to call-with-current-continuation. |

2654 | +Except for continuations created by the call-with-values procedure, all |

2655 | +continuations take exactly one value. The effect of passing no value or |

2656 | +more than one value to continuations that were not created by |

2657 | +call-with-values is unspecified. |

2658 | + |

2659 | +The escape procedure that is passed to proc has unlimited extent just |

2660 | +like any other procedure in Scheme. It may be stored in variables or |

2661 | +data structures and may be called as many times as desired. |

2662 | + |

2663 | +The following examples show only the most common ways in which |

2664 | +call-with-current-continuation is used. If all real uses were as simple |

2665 | +as these examples, there would be no need for a procedure with the |

2666 | +power of call-with-current-continuation. |

2667 | + |

2668 | + (call-with-current-continuation |

2669 | + (lambda (exit) |

2670 | + (for-each (lambda (x) |

2671 | + (if (negative? x) |

2672 | + (exit x))) |

2673 | + '(54 0 37 -3 245 19)) |

2674 | + #t)) ===> -3 |

2675 | + |

2676 | + (define list-length |

2677 | + (lambda (obj) |

2678 | + (call-with-current-continuation |

2679 | + (lambda (return) |

2680 | + (letrec ((r |

2681 | + (lambda (obj) |

2682 | + (cond ((null? obj) 0) |

2683 | + ((pair? obj) |

2684 | + (+ (r (cdr obj)) 1)) |

2685 | + (else (return #f)))))) |

2686 | + (r obj)))))) |

2687 | + |

2688 | + (list-length '(1 2 3 4)) ===> 4 |

2689 | + |

2690 | + (list-length '(a b . c)) ===> #f |

2691 | + |

2692 | +Rationale: |

2693 | + |

2694 | +A common use of call-with-current-continuation is for structured, |

2695 | +non-local exits from loops or procedure bodies, but in fact |

2696 | +call-with-current-continuation is extremely useful for implementing |

2697 | +a wide variety of advanced control structures. |

2698 | + |

2699 | +Whenever a Scheme expression is evaluated there is a continuation |

2700 | +wanting the result of the expression. The continuation represents |

2701 | +an entire (default) future for the computation. If the expression |

2702 | +is evaluated at top level, for example, then the continuation might |

2703 | +take the result, print it on the screen, prompt for the next input, |

2704 | +evaluate it, and so on forever. Most of the time the continuation |

2705 | +includes actions specified by user code, as in a continuation that |

2706 | +will take the result, multiply it by the value stored in a local |

2707 | +variable, add seven, and give the answer to the top level |

2708 | +continuation to be printed. Normally these ubiquitous continuations |

2709 | +are hidden behind the scenes and programmers do not think much |

2710 | +about them. On rare occasions, however, a programmer may need to |

2711 | +deal with continuations explicitly. Call-with-current-continuation |

2712 | +allows Scheme programmers to do that by creating a procedure that |

2713 | +acts just like the current continuation. |

2714 | + |

2715 | +Most programming languages incorporate one or more special-purpose |

2716 | +escape constructs with names like exit, return, or even goto. In |

2717 | +1965, however, Peter Landin [16] invented a general purpose escape |

2718 | +operator called the J-operator. John Reynolds [24] described a |

2719 | +simpler but equally powerful construct in 1972. The catch special |

2720 | +form described by Sussman and Steele in the 1975 report on Scheme |

2721 | +is exactly the same as Reynolds's construct, though its name came |

2722 | +from a less general construct in MacLisp. Several Scheme |

2723 | +implementors noticed that the full power of the catch construct |

2724 | +could be provided by a procedure instead of by a special syntactic |

2725 | +construct, and the name call-with-current-continuation was coined |

2726 | +in 1982. This name is descriptive, but opinions differ on the |

2727 | +merits of such a long name, and some people use the name call/cc |

2728 | +instead. |

2729 | + |

2730 | +<procedure>(values obj ...)</procedure><br> |

2731 | + |

2732 | +Delivers all of its arguments to its continuation. Except for |

2733 | +continuations created by the call-with-values procedure, all |

2734 | +continuations take exactly one value. Values might be defined as |

2735 | +follows: |

2736 | + |

2737 | + (define (values . things) |

2738 | + (call-with-current-continuation |

2739 | + (lambda (cont) (apply cont things)))) |

2740 | + |

2741 | +<procedure>(call-with-values producer consumer)</procedure><br> |

2742 | + |

2743 | +Calls its producer argument with no values and a continuation that, |

2744 | +when passed some values, calls the consumer procedure with those values |

2745 | +as arguments. The continuation for the call to consumer is the |

2746 | +continuation of the call to call-with-values. |

2747 | + |

2748 | + (call-with-values (lambda () (values 4 5)) |

2749 | + (lambda (a b) b)) |

2750 | + ===> 5 |

2751 | + |

2752 | + (call-with-values * -) ===> -1 |

2753 | + |

2754 | +<procedure>(dynamic-wind before thunk after)</procedure><br> |

2755 | + |

2756 | +Calls thunk without arguments, returning the result(s) of this call. |

2757 | +Before and after are called, also without arguments, as required by the |

2758 | +following rules (note that in the absence of calls to continuations |

2759 | +captured using call-with-current-continuation the three arguments are |

2760 | +called once each, in order). Before is called whenever execution enters |

2761 | +the dynamic extent of the call to thunk and after is called whenever it |

2762 | +exits that dynamic extent. The dynamic extent of a procedure call is |

2763 | +the period between when the call is initiated and when it returns. In |

2764 | +Scheme, because of call-with-current-continuation, the dynamic extent |

2765 | +of a call may not be a single, connected time period. It is defined as |

2766 | +follows: |

2767 | + |

2768 | +* The dynamic extent is entered when execution of the body of the |

2769 | + called procedure begins. |

2770 | + |

2771 | +* The dynamic extent is also entered when execution is not within the |

2772 | + dynamic extent and a continuation is invoked that was captured |

2773 | + (using call-with-current-continuation) during the dynamic extent. |

2774 | + |

2775 | +* It is exited when the called procedure returns. |

2776 | + |

2777 | +* It is also exited when execution is within the dynamic extent and a |

2778 | + continuation is invoked that was captured while not within the |

2779 | + dynamic extent. |

2780 | + |

2781 | +If a second call to dynamic-wind occurs within the dynamic extent of |

2782 | +the call to thunk and then a continuation is invoked in such a way that |

2783 | +the afters from these two invocations of dynamic-wind are both to be |

2784 | +called, then the after associated with the second (inner) call to |

2785 | +dynamic-wind is called first. |

2786 | + |

2787 | +If a second call to dynamic-wind occurs within the dynamic extent of |

2788 | +the call to thunk and then a continuation is invoked in such a way that |

2789 | +the befores from these two invocations of dynamic-wind are both to be |

2790 | +called, then the before associated with the first (outer) call to |

2791 | +dynamic-wind is called first. |

2792 | + |

2793 | +If invoking a continuation requires calling the before from one call to |

2794 | +dynamic-wind and the after from another, then the after is called |

2795 | +first. |

2796 | + |

2797 | +The effect of using a captured continuation to enter or exit the |

2798 | +dynamic extent of a call to before or after is undefined. |

2799 | + |

2800 | + (let ((path '()) |

2801 | + (c #f)) |

2802 | + (let ((add (lambda (s) |

2803 | + (set! path (cons s path))))) |

2804 | + (dynamic-wind |

2805 | + (lambda () (add 'connect)) |

2806 | + (lambda () |

2807 | + (add (call-with-current-continuation |

2808 | + (lambda (c0) |

2809 | + (set! c c0) |

2810 | + 'talk1)))) |

2811 | + (lambda () (add 'disconnect))) |

2812 | + (if (< (length path) 4) |

2813 | + (c 'talk2) |

2814 | + (reverse path)))) |

2815 | + |

2816 | + ===> (connect talk1 disconnect |

2817 | + connect talk2 disconnect) |

2818 | + |

2819 | +=== Eval |

2820 | + |

2821 | +<procedure>(eval expression environment-specifier)</procedure><br> |

2822 | + |

2823 | +Evaluates expression in the specified environment and returns its |

2824 | +value. Expression must be a valid Scheme expression represented as |

2825 | +data, and environment-specifier must be a value returned by one of the |

2826 | +three procedures described below. Implementations may extend eval to |

2827 | +allow non-expression programs (definitions) as the first argument and |

2828 | +to allow other values as environments, with the restriction that eval |

2829 | +is not allowed to create new bindings in the environments associated |

2830 | +with null-environment or scheme-report-environment. |

2831 | + |

2832 | + (eval '(* 7 3) (scheme-report-environment 5)) |

2833 | + ===> 21 |

2834 | + |

2835 | + (let ((f (eval '(lambda (f x) (f x x)) |

2836 | + (null-environment 5)))) |

2837 | + (f + 10)) |

2838 | + ===> 20 |

2839 | + |

2840 | +<procedure>(scheme-report-environment version)</procedure><br> |

2841 | +<procedure>(null-environment version)</procedure><br> |

2842 | + |

2843 | +Version must be the exact integer 5, corresponding to this revision of |

2844 | +the Scheme report (the Revised^5 Report on Scheme). |

2845 | +Scheme-report-environment returns a specifier for an environment that |

2846 | +is empty except for all bindings defined in this report that are either |

2847 | +required or both optional and supported by the implementation. |

2848 | +Null-environment returns a specifier for an environment that is empty |

2849 | +except for the (syntactic) bindings for all syntactic keywords defined |

2850 | +in this report that are either required or both optional and supported |

2851 | +by the implementation. |

2852 | + |

2853 | +Other values of version can be used to specify environments matching |

2854 | +past revisions of this report, but their support is not required. An |

2855 | +implementation will signal an error if version is neither 5 nor another |

2856 | +value supported by the implementation. |

2857 | + |

2858 | +The effect of assigning (through the use of eval) a variable bound in a |

2859 | +scheme-report-environment (for example car) is unspecified. Thus the |

2860 | +environments specified by scheme-report-environment may be immutable. |

2861 | + |

2862 | +<procedure>(interaction-environment)</procedure><br> |

2863 | + |

2864 | +This procedure returns a specifier for the environment that contains |

2865 | +implementation-defined bindings, typically a superset of those listed |

2866 | +in the report. The intent is that this procedure will return the |

2867 | +environment in which the implementation would evaluate expressions |

2868 | +dynamically typed by the user. |

2869 | + |

2870 | +=== Input and output |

2871 | + |

2872 | +==== Ports |

2873 | + |

2874 | +Ports represent input and output devices. To Scheme, an input port is a |

2875 | +Scheme object that can deliver characters upon command, while an output |

2876 | +port is a Scheme object that can accept characters. |

2877 | + |

2878 | +<procedure>(call-with-input-file string proc)</procedure><br> |

2879 | +<procedure>(call-with-output-file string proc)</procedure><br> |

2880 | + |

2881 | +String should be a string naming a file, and proc should be a procedure |

2882 | +that accepts one argument. For call-with-input-file, the file should |

2883 | +already exist; for call-with-output-file, the effect is unspecified if |

2884 | +the file already exists. These procedures call proc with one argument: |

2885 | +the port obtained by opening the named file for input or output. If the |

2886 | +file cannot be opened, an error is signalled. If proc returns, then the |

2887 | +port is closed automatically and the value(s) yielded by the proc is |

2888 | +(are) returned. If proc does not return, then the port will not be |

2889 | +closed automatically unless it is possible to prove that the port will |

2890 | +never again be used for a read or write operation. |

2891 | + |

2892 | +Rationale: Because Scheme's escape procedures have unlimited |

2893 | +extent, it is possible to escape from the current continuation but |

2894 | +later to escape back in. If implementations were permitted to close |

2895 | +the port on any escape from the current continuation, then it would |

2896 | +be impossible to write portable code using both |

2897 | +call-with-current-continuation and call-with-input-file or |

2898 | +call-with-output-file. |

2899 | + |

2900 | +<procedure>(input-port? obj)</procedure><br> |

2901 | +<procedure>(output-port? obj)</procedure><br> |

2902 | + |

2903 | +Returns #t if obj is an input port or output port respectively, |

2904 | +otherwise returns #f. |

2905 | + |

2906 | +<procedure>(current-input-port)</procedure><br> |

2907 | +<procedure>(current-output-port)</procedure><br> |

2908 | + |

2909 | +Returns the current default input or output port. |

2910 | + |

2911 | +<procedure>(with-input-from-file string thunk)</procedure><br> |

2912 | +<procedure>(with-output-to-file string thunk)</procedure><br> |

2913 | + |

2914 | +String should be a string naming a file, and proc should be a procedure |

2915 | +of no arguments. For with-input-from-file, the file should already |

2916 | +exist; for with-output-to-file, the effect is unspecified if the file |

2917 | +already exists. The file is opened for input or output, an input or |

2918 | +output port connected to it is made the default value returned by |

2919 | +current-input-port or current-output-port (and is used by (read), |

2920 | +(write obj), and so forth), and the thunk is called with no arguments. |

2921 | +When the thunk returns, the port is closed and the previous default is |

2922 | +restored. With-input-from-file and with-output-to-file return(s) the |

2923 | +value(s) yielded by thunk. If an escape procedure is used to escape |

2924 | +from the continuation of these procedures, their behavior is |

2925 | +implementation dependent. |

2926 | + |

2927 | +<procedure>(open-input-file filename)</procedure><br> |

2928 | + |

2929 | +Takes a string naming an existing file and returns an input port |

2930 | +capable of delivering characters from the file. If the file cannot be |

2931 | +opened, an error is signalled. |

2932 | + |

2933 | +<procedure>(open-output-file filename)</procedure><br> |

2934 | + |

2935 | +Takes a string naming an output file to be created and returns an |

2936 | +output port capable of writing characters to a new file by that name. |

2937 | +If the file cannot be opened, an error is signalled. If a file with the |

2938 | +given name already exists, the effect is unspecified. |

2939 | + |

2940 | +<procedure>(close-input-port port)</procedure><br> |

2941 | +<procedure>(close-output-port port)</procedure><br> |

2942 | + |

2943 | +Closes the file associated with port, rendering the port incapable of |

2944 | +delivering or accepting characters. These routines have no effect if |

2945 | +the file has already been closed. The value returned is unspecified. |

2946 | + |

2947 | +==== Input |

2948 | + |

2949 | +<procedure>(read)</procedure><br> |

2950 | +<procedure>(read port)</procedure><br> |

2951 | + |

2952 | +Read converts external representations of Scheme objects into the |

2953 | +objects themselves. That is, it is a parser for the nonterminal <datum> |

2954 | +(see sections 7.1.2 and 6.3.2). Read returns the next object parsable |

2955 | +from the given input port, updating port to point to the first |

2956 | +character past the end of the external representation of the object. |

2957 | + |

2958 | +If an end of file is encountered in the input before any characters are |

2959 | +found that can begin an object, then an end of file object is returned. |

2960 | +The port remains open, and further attempts to read will also return an |

2961 | +end of file object. If an end of file is encountered after the |

2962 | +beginning of an object's external representation, but the external |

2963 | +representation is incomplete and therefore not parsable, an error is |

2964 | +signalled. |

2965 | + |

2966 | +The port argument may be omitted, in which case it defaults to the |

2967 | +value returned by current-input-port. It is an error to read from a |

2968 | +closed port. |

2969 | + |

2970 | +<procedure>(read-char)</procedure><br> |

2971 | +<procedure>(read-char port)</procedure><br> |

2972 | + |

2973 | +Returns the next character available from the input port, updating the |

2974 | +port to point to the following character. If no more characters are |

2975 | +available, an end of file object is returned. Port may be omitted, in |

2976 | +which case it defaults to the value returned by current-input-port. |

2977 | + |

2978 | +<procedure>(peek-char)</procedure><br> |

2979 | +<procedure>(peek-char port)</procedure><br> |

2980 | + |

2981 | +Returns the next character available from the input port, without |

2982 | +updating the port to point to the following character. If no more |

2983 | +characters are available, an end of file object is returned. Port may |

2984 | +be omitted, in which case it defaults to the value returned by |

2985 | +current-input-port. |

2986 | + |

2987 | +Note: The value returned by a call to peek-char is the same as |

2988 | +the value that would have been returned by a call to read-char with |

2989 | +the same port. The only difference is that the very next call to |

2990 | +read-char or peek-char on that port will return the value returned |

2991 | +by the preceding call to peek-char. In particular, a call to |

2992 | +peek-char on an interactive port will hang waiting for input |

2993 | +whenever a call to read-char would have hung. |

2994 | + |

2995 | +<procedure>(eof-object? obj)</procedure><br> |

2996 | + |

2997 | +Returns #t if obj is an end of file object, otherwise returns #f. The |

2998 | +precise set of end of file objects will vary among implementations, but |

2999 | +in any case no end of file object will ever be an object that can be |

3000 | +read in using read. |

3001 | + |

3002 | +<procedure>(char-ready?)</procedure><br> |

3003 | +<procedure>(char-ready? port)</procedure><br> |

3004 | + |

3005 | +Returns #t if a character is ready on the input port and returns #f |

3006 | +otherwise. If char-ready returns #t then the next read-char operation |

3007 | +on the given port is guaranteed not to hang. If the port is at end of |

3008 | +file then char-ready? returns #t. Port may be omitted, in which case it |

3009 | +defaults to the value returned by current-input-port. |

3010 | + |

3011 | +Rationale: Char-ready? exists to make it possible for a program |

3012 | +to accept characters from interactive ports without getting stuck |

3013 | +waiting for input. Any input editors associated with such ports |

3014 | +must ensure that characters whose existence has been asserted by |

3015 | +char-ready? cannot be rubbed out. If char-ready? were to return #f |

3016 | +at end of file, a port at end of file would be indistinguishable |

3017 | +from an interactive port that has no ready characters. |

3018 | + |

3019 | +==== Output |

3020 | + |

3021 | +<procedure>(write obj)</procedure><br> |

3022 | +<procedure>(write obj port)</procedure><br> |

3023 | + |

3024 | +Writes a written representation of obj to the given port. Strings that |

3025 | +appear in the written representation are enclosed in doublequotes, and |

3026 | +within those strings backslash and doublequote characters are escaped |

3027 | +by backslashes. Character objects are written using the #\ notation. |

3028 | +Write returns an unspecified value. The port argument may be omitted, |

3029 | +in which case it defaults to the value returned by current-output-port. |

3030 | + |

3031 | +<procedure>(display obj)</procedure><br> |

3032 | +<procedure>(display obj port)</procedure><br> |

3033 | + |

3034 | +Writes a representation of obj to the given port. Strings that appear |

3035 | +in the written representation are not enclosed in doublequotes, and no |

3036 | +characters are escaped within those strings. Character objects appear |

3037 | +in the representation as if written by write-char instead of by write. |

3038 | +Display returns an unspecified value. The port argument may be omitted, |

3039 | +in which case it defaults to the value returned by current-output-port. |

3040 | + |

3041 | +Rationale: Write is intended for producing machine-readable |

3042 | +output and display is for producing human-readable output. |

3043 | +Implementations that allow "slashification" within symbols will |

3044 | +probably want write but not display to slashify funny characters in |

3045 | +symbols. |

3046 | + |

3047 | +<procedure>(newline)</procedure><br> |

3048 | +<procedure>(newline port)</procedure><br> |

3049 | + |

3050 | +Writes an end of line to port. Exactly how this is done differs from |

3051 | +one operating system to another. Returns an unspecified value. The port |

3052 | +argument may be omitted, in which case it defaults to the value |

3053 | +returned by current-output-port. |

3054 | + |

3055 | +<procedure>(write-char char)</procedure><br> |

3056 | +<procedure>(write-char char port)</procedure><br> |

3057 | + |

3058 | +Writes the character char (not an external representation of the |

3059 | +character) to the given port and returns an unspecified value. The port |

3060 | +argument may be omitted, in which case it defaults to the value |

3061 | +returned by current-output-port. |

3062 | + |

3063 | +==== System interface |

3064 | + |

3065 | +Questions of system interface generally fall outside of the domain of |

3066 | +this report. However, the following operations are important enough to |

3067 | +deserve description here. |

3068 | + |

3069 | +<procedure>(load filename)</procedure><br> |

3070 | + |

3071 | +Filename should be a string naming an existing file containing Scheme |

3072 | +source code. The load procedure reads expressions and definitions from |

3073 | +the file and evaluates them sequentially. It is unspecified whether the |

3074 | +results of the expressions are printed. The load procedure does not |

3075 | +affect the values returned by current-input-port and |

3076 | +current-output-port. Load returns an unspecified value. |

3077 | + |

3078 | +Rationale: For portability, load must operate on source files. |

3079 | +Its operation on other kinds of files necessarily varies among |

3080 | +implementations. |

3081 | + |

3082 | +<procedure>(transcript-on filename)</procedure><br> |

3083 | +<procedure>(transcript-off)</procedure><br> |

3084 | + |

3085 | +(These procedures are not implemented in Chicken.) |

3086 | + |

3087 | +Filename must be a string naming an output file to be created. The |

3088 | +effect of transcript-on is to open the named file for output, and to |

3089 | +cause a transcript of subsequent interaction between the user and the |

3090 | +Scheme system to be written to the file. The transcript is ended by a |

3091 | +call to transcript-off, which closes the transcript file. Only one |

3092 | +transcript may be in progress at any time, though some implementations |

3093 | +may relax this restriction. The values returned by these procedures are |

3094 | +unspecified. |

3095 | + |

3096 | -- |

3097 | 1.6.5.2 |

3098 | |

3099 | |

3100 | From a4d5e7089fe1d919e795a904e22b4e65b41e744c Mon Sep 17 00:00:00 2001 |

3101 | Message-Id: <a4d5e7089fe1d919e795a904e22b4e65b41e744c.1260078974.git.zbigniewsz@gmail.com> |

3102 | In-Reply-To: <cover.1260078974.git.zbigniewsz@gmail.com> |

3103 | References: <cover.1260078974.git.zbigniewsz@gmail.com> |

3104 | From: zbigniew <zbigniewsz@gmail.com> |

3105 | Date: Sat, 5 Dec 2009 23:37:11 -0600 |

3106 | Subject: Sync changes from wiki manual to core: SVN 16559-16579 (SRFI-1 import) |

3107 | Status: O |

3108 | |

3109 | |

3110 | Signed-off-by: zbigniew <zbigniewsz@gmail.com> |

3111 | --- |

3112 | manual/Unit srfi-1 | 1354 +++++++++++++++++++++++++++++++++++++++++++++++++++- |

3113 | 1 files changed, 1349 insertions(+), 5 deletions(-) |

3114 | |

3115 | diff --git a/manual/Unit srfi-1 b/manual/Unit srfi-1 |

3116 | index 6881a6d..b601f73 100644 |

3117 | --- a/manual/Unit srfi-1 |

3118 | +++ b/manual/Unit srfi-1 |

3119 | @@ -2,10 +2,1354 @@ |

3120 | |

3121 | == Unit srfi-1 |

3122 | |

3123 | -List library, see the documentation for |

3124 | -[[http://srfi.schemers.org/srfi-1/srfi-1.html|SRFI-1]] |

3125 | +SRFI 1 (List Library) procedures. For more information, see the |

3126 | +[[http://srfi.schemers.org/srfi-1/srfi-1.html|SRFI 1]] document. |

3127 | |

3128 | ---- |

3129 | -Previous: [[Unit regex]] |

3130 | +[[toc:]] |

3131 | +=== Constructors |

3132 | |

3133 | -Next: [[Unit srfi-4]] |

3134 | +<procedure>(xcons d a) -> pair</procedure><br> |

3135 | + |

3136 | + (lambda (d a) (cons a d)) |

3137 | + |

3138 | +Of utility only as a value to be conveniently passed to |

3139 | +higher-order procedures. |

3140 | + |

3141 | + (xcons '(b c) 'a) => (a b c) |

3142 | + |

3143 | +The name stands for "eXchanged CONS." |

3144 | + |

3145 | +<procedure>(cons* elt[1] elt[2] ...) -> object</procedure><br> |

3146 | + |

3147 | +Like list, but the last argument provides the tail of the |

3148 | +constructed list, returning |

3149 | + (cons elt[1] (cons elt[2] (cons ... elt[n]))) |

3150 | + |

3151 | +This function is called list* in Common Lisp and about half of the |

3152 | +Schemes that provide it, and cons* in the other half. |

3153 | + |

3154 | + (cons* 1 2 3 4) => (1 2 3 . 4) |

3155 | + (cons* 1) => 1 |

3156 | + |

3157 | +<procedure>(make-list n [fill]) -> list</procedure><br> |

3158 | +Returns an n-element list, whose elements are all the value fill. |

3159 | +If the fill argument is not given, the elements of the list may be |

3160 | +arbitrary values. |

3161 | + |

3162 | + (make-list 4 'c) => (c c c c) |

3163 | + |

3164 | +<procedure>(list-tabulate n init-proc) -> list</procedure><br> |

3165 | + |

3166 | +Returns an n-element list. Element i of the list, where 0 <= i < n, |

3167 | +is produced by (init-proc i). No guarantee is made about the |

3168 | +dynamic order in which init-proc is applied to these indices. |

3169 | + |

3170 | + (list-tabulate 4 values) => (0 1 2 3) |

3171 | + |

3172 | +<procedure>(list-copy flist) -> flist</procedure><br> |

3173 | + |

3174 | +Copies the spine of the argument. |

3175 | + |

3176 | +<procedure>(circular-list elt[1] elt[2] ...) -> list</procedure><br> |

3177 | + |

3178 | +Constructs a circular list of the elements. |

3179 | + |

3180 | + (circular-list 'z 'q) => (z q z q z q ...) |

3181 | + |

3182 | +<procedure>(iota count [start step]) -> list</procedure><br> |

3183 | + |

3184 | +Returns a list containing the elements |

3185 | + |

3186 | + (start start+step ... start+(count-1)*step) |

3187 | + |

3188 | +The start and step parameters default to 0 and 1, respectively. |

3189 | +This procedure takes its name from the APL primitive. |

3190 | + |

3191 | + (iota 5) => (0 1 2 3 4) |

3192 | + (iota 5 0 -0.1) => (0 -0.1 -0.2 -0.3 -0.4) |

3193 | + |

3194 | +=== Predicates |

3195 | + |

3196 | +Note: the predicates proper-list?, circular-list?, and dotted-list? |

3197 | +partition the entire universe of Scheme values. |

3198 | + |

3199 | +<procedure>(proper-list? x) -> boolean</procedure><br> |

3200 | + |

3201 | +Returns true iff x is a proper list -- a finite, nil-terminated |

3202 | +list. |

3203 | + |

3204 | +More carefully: The empty list is a proper list. A pair whose cdr |

3205 | +is a proper list is also a proper list: |

3206 | + |

3207 | + <proper-list> ::= () (Empty proper list) |

3208 | + | (cons <x> <proper-list>) (Proper-list pair) |

3209 | + |

3210 | +Note that this definition rules out circular lists. This function |

3211 | +is required to detect this case and return false. |

3212 | + |

3213 | +Nil-terminated lists are called "proper" lists by R5RS and Common |

3214 | +Lisp. The opposite of proper is improper. |

3215 | + |

3216 | +R5RS binds this function to the variable list?. |

3217 | + |

3218 | + (not (proper-list? x)) = (or (dotted-list? x) (circular-list? x)) |

3219 | + |

3220 | +<procedure>(circular-list? x) -> boolean</procedure><br> |

3221 | + |

3222 | +True if x is a circular list. A circular list is a value such that |

3223 | +for every n >= 0, cdr^n(x) is a pair. |

3224 | + |

3225 | +Terminology: The opposite of circular is finite. |

3226 | + |

3227 | + (not (circular-list? x)) = (or (proper-list? x) (dotted-list? x)) |

3228 | + |

3229 | +<procedure>(dotted-list? x) -> boolean</procedure><br> |

3230 | + |

3231 | +True if x is a finite, non-nil-terminated list. That is, there |

3232 | +exists an n >= 0 such that cdr^n(x) is neither a pair nor (). This |

3233 | +includes non-pair, non-() values (e.g. symbols, numbers), which are |

3234 | +considered to be dotted lists of length 0. |

3235 | + |

3236 | + (not (dotted-list? x)) = (or (proper-list? x) (circular-list? x)) |

3237 | + |

3238 | +<procedure>(not-pair? x) -> boolean</procedure><br> |

3239 | + |

3240 | + (lambda (x) (not (pair? x))) |

3241 | + |

3242 | +Provided as a procedure as it can be useful as the termination |

3243 | +condition for list-processing procedures that wish to handle all |

3244 | +finite lists, both proper and dotted. |

3245 | + |

3246 | +<procedure>(list= elt= list[1] ...) -> boolean</procedure><br> |

3247 | + |

3248 | +Determines list equality, given an element-equality procedure. |

3249 | +Proper list A equals proper list B if they are of the same length, |

3250 | +and their corresponding elements are equal, as determined by elt=. |

3251 | +If the element-comparison procedure's first argument is from list |

3252 | +[i], then its second argument is from list[i+1], i.e. it is always |

3253 | +called as (elt= a b) for a an element of list A, and b an element |

3254 | +of list B. |

3255 | + |

3256 | +In the n-ary case, every list[i] is compared to list[i+1] (as |

3257 | +opposed, for example, to comparing list[1] to every list[i], for i> |

3258 | +1). If there are no list arguments at all, list= simply returns |

3259 | +true. |

3260 | + |

3261 | +It is an error to apply list= to anything except proper lists. |

3262 | +While implementations may choose to extend it to circular lists, |

3263 | +note that it cannot reasonably be extended to dotted lists, as it |

3264 | +provides no way to specify an equality procedure for comparing the |

3265 | +list terminators. |

3266 | + |

3267 | +Note that the dynamic order in which the elt= procedure is applied |

3268 | +to pairs of elements is not specified. For example, if list= is |

3269 | +applied to three lists, A, B, and C, it may first completely |

3270 | +compare A to B, then compare B to C, or it may compare the first |

3271 | +elements of A and B, then the first elements of B and C, then the |

3272 | +second elements of A and B, and so forth. |

3273 | + |

3274 | +The equality procedure must be consistent with eq?. That is, it |

3275 | +must be the case that |

3276 | + |

3277 | + (eq? x y) => (elt= x y). |

3278 | + |

3279 | +Note that this implies that two lists which are eq? are always list=, |

3280 | +as well; implementations may exploit this fact to "short-cut" |

3281 | +the element-by-element comparisons. |

3282 | + |

3283 | + (list= eq?) => #t ; Trivial cases |

3284 | + (list= eq? '(a)) => #t |

3285 | + |

3286 | +=== Selectors |

3287 | + |

3288 | +<procedure>(first pair) -> object</procedure><br> |

3289 | +<procedure>(second pair) -> object</procedure><br> |

3290 | +<procedure>(third pair) -> object</procedure><br> |

3291 | +<procedure>(fourth pair) -> object</procedure><br> |

3292 | +<procedure>(fifth pair) -> object</procedure><br> |

3293 | +<procedure>(sixth pair) -> object</procedure><br> |

3294 | +<procedure>(seventh pair) -> object</procedure><br> |

3295 | +<procedure>(eighth pair) -> object</procedure><br> |

3296 | +<procedure>(ninth pair) -> object</procedure><br> |

3297 | +<procedure>(tenth pair) -> object</procedure><br> |

3298 | + |

3299 | +Synonyms for car, cadr, caddr, ... |

3300 | + |

3301 | + (third '(a b c d e)) => c |

3302 | + |

3303 | +<procedure>(car+cdr pair) -> [x y]</procedure><br> |

3304 | + |

3305 | +The fundamental pair deconstructor: |

3306 | + |

3307 | + (lambda (p) (values (car p) (cdr p))) |

3308 | + |

3309 | +This can, of course, be implemented more efficiently by a compiler. |

3310 | + |

3311 | +<procedure>(take x i) -> list</procedure><br> |

3312 | +<procedure>(drop x i) -> object</procedure><br> |

3313 | + |

3314 | +take returns the first i elements of list x. |

3315 | +drop returns all but the first i elements of list x. |

3316 | + |

3317 | + (take '(a b c d e) 2) => (a b) |

3318 | + (drop '(a b c d e) 2) => (c d e) |

3319 | + |

3320 | +x may be any value -- a proper, circular, or dotted list: |

3321 | + |

3322 | + (take '(1 2 3 . d) 2) => (1 2) |

3323 | + (drop '(1 2 3 . d) 2) => (3 . d) |

3324 | + (take '(1 2 3 . d) 3) => (1 2 3) |

3325 | + (drop '(1 2 3 . d) 3) => d |

3326 | + |

3327 | +For a legal i, take and drop partition the list in a manner which |

3328 | +can be inverted with append: |

3329 | + |

3330 | + (append (take x i) (drop x i)) = x |

3331 | + |

3332 | +drop is exactly equivalent to performing i cdr operations on x; the |

3333 | +returned value shares a common tail with x. If the argument is a |

3334 | +list of non-zero length, take is guaranteed to return a |

3335 | +freshly-allocated list, even in the case where the entire list is |

3336 | +taken, e.g. (take lis (length lis)). |

3337 | + |

3338 | +<procedure>(take-right flist i) -> object</procedure><br> |

3339 | +<procedure>(drop-right flist i) -> list</procedure><br> |

3340 | + |

3341 | +take-right returns the last i elements of flist. |

3342 | +drop-right returns all but the last i elements of flist. |

3343 | + |

3344 | + (take-right '(a b c d e) 2) => (d e) |

3345 | + (drop-right '(a b c d e) 2) => (a b c) |

3346 | + |

3347 | +The returned list may share a common tail with the argument list. |

3348 | + |

3349 | +flist may be any finite list, either proper or dotted: |

3350 | + |

3351 | + (take-right '(1 2 3 . d) 2) => (2 3 . d) |

3352 | + (drop-right '(1 2 3 . d) 2) => (1) |

3353 | + (take-right '(1 2 3 . d) 0) => d |

3354 | + (drop-right '(1 2 3 . d) 0) => (1 2 3) |

3355 | + |

3356 | +For a legal i, take-right and drop-right partition the list in a |

3357 | +manner which can be inverted with append: |

3358 | + |

3359 | + (append (take flist i) (drop flist i)) = flist |

3360 | + |

3361 | +take-right's return value is guaranteed to share a common tail with |

3362 | +flist. If the argument is a list of non-zero length, drop-right is |

3363 | +guaranteed to return a freshly-allocated list, even in the case |

3364 | +where nothing is dropped, e.g. (drop-right lis 0). |

3365 | + |

3366 | +<procedure>(take! x i) -> list</procedure><br> |

3367 | +<procedure>(drop-right! flist i) -> list</procedure><br> |

3368 | + |

3369 | +take! and drop-right! are "linear-update" variants of take and |

3370 | +drop-right: the procedure is allowed, but not required, to alter |

3371 | +the argument list to produce the result. |

3372 | + |

3373 | +If x is circular, take! may return a shorter-than-expected list: |

3374 | + |

3375 | + (take! (circular-list 1 3 5) 8) => (1 3) |

3376 | + (take! (circular-list 1 3 5) 8) => (1 3 5 1 3 5 1 3) |

3377 | + |

3378 | +<procedure>(split-at x i) -> [list object]</procedure><br> |

3379 | +<procedure>(split-at! x i) -> [list object]</procedure><br> |

3380 | + |

3381 | +split-at splits the list x at index i, returning a list of the |

3382 | +first i elements, and the remaining tail. It is equivalent to |

3383 | + |

3384 | + (values (take x i) (drop x i)) |

3385 | + |

3386 | +split-at! is the linear-update variant. It is allowed, but not |

3387 | +required, to alter the argument list to produce the result. |

3388 | + |

3389 | + (split-at '(a b c d e f g h) 3) => |

3390 | + (a b c) |

3391 | + (d e f g h) |

3392 | + |

3393 | +<procedure>(last pair) -> object</procedure><br> |

3394 | +<procedure>(last-pair pair) -> pair</procedure><br> |

3395 | + |

3396 | +last returns the last element of the non-empty, finite list pair. |

3397 | +last-pair returns the last pair in the non-empty, finite list pair. |

3398 | + |

3399 | + (last '(a b c)) => c |

3400 | + (last-pair '(a b c)) => (c) |

3401 | + |

3402 | +=== Miscellaneous |

3403 | + |

3404 | +<procedure>(length list) -> integer</procedure><br> |

3405 | +<procedure>(length+ clist) -> integer or #f</procedure><br> |

3406 | + |

3407 | +Both length and length+ return the length of the argument. It is an |

3408 | +error to pass a value to length which is not a proper list (finite |

3409 | +and nil-terminated). In particular, this means an implementation |

3410 | +may diverge or signal an error when length is applied to a circular |

3411 | +list. |

3412 | + |

3413 | +length+, on the other hand, returns #F when applied to a circular |

3414 | +list. |

3415 | + |

3416 | +The length of a proper list is a non-negative integer n such that |

3417 | +cdr applied n times to the list produces the empty list. |

3418 | + |

3419 | +<procedure>(append! list[1] ...) -> list</procedure><br> |

3420 | + |

3421 | +append! is the "linear-update" variant of append -- it is allowed, |

3422 | +but not required, to alter cons cells in the argument lists to |

3423 | +construct the result list. The last argument is never altered; the |

3424 | +result list shares structure with this parameter. |

3425 | + |

3426 | +<procedure>(concatenate list-of-lists) -> value</procedure><br> |

3427 | +<procedure>(concatenate! list-of-lists) -> value</procedure><br> |

3428 | + |

3429 | +These functions append the elements of their argument together. |

3430 | +That is, concatenate returns |

3431 | + |

3432 | + (apply append list-of-lists) |

3433 | + |

3434 | +or, equivalently, |

3435 | + |

3436 | + (reduce-right append '() list-of-lists) |

3437 | + |

3438 | +concatenate! is the linear-update variant, defined in terms of |

3439 | +append! instead of append. |

3440 | + |

3441 | +Note that some Scheme implementations do not support passing more |

3442 | +than a certain number (e.g., 64) of arguments to an n-ary |

3443 | +procedure. In these implementations, the (apply append ...) idiom |

3444 | +would fail when applied to long lists, but concatenate would |

3445 | +continue to function properly. |

3446 | + |

3447 | +As with append and append!, the last element of the input list may |

3448 | +be any value at all. |

3449 | + |

3450 | +<procedure>(reverse! list) -> list</procedure><br> |

3451 | + |

3452 | +reverse! is the linear-update variant of reverse. It is permitted, |

3453 | +but not required, to alter the argument's cons cells to produce the |

3454 | +reversed list. |

3455 | + |

3456 | +<procedure>(append-reverse rev-head tail) -> list</procedure><br> |

3457 | +<procedure>(append-reverse! rev-head tail) -> list</procedure><br> |

3458 | + |

3459 | +append-reverse returns (append (reverse rev-head) tail). It is |

3460 | +provided because it is a common operation -- a common |

3461 | +list-processing style calls for this exact operation to transfer |

3462 | +values accumulated in reverse order onto the front of another list, |

3463 | +and because the implementation is significantly more efficient than |

3464 | +the simple composition it replaces. (But note that this pattern of |

3465 | +iterative computation followed by a reverse can frequently be |

3466 | +rewritten as a recursion, dispensing with the reverse and |

3467 | +append-reverse steps, and shifting temporary, intermediate storage |

3468 | +from the heap to the stack, which is typically a win for reasons of |

3469 | +cache locality and eager storage reclamation.) |

3470 | + |

3471 | +append-reverse! is just the linear-update variant -- it is allowed, |

3472 | +but not required, to alter rev-head's cons cells to construct the |

3473 | +result. |

3474 | + |

3475 | +<procedure>(zip clist[1] clist[2] ...) -> list</procedure><br> |

3476 | + |

3477 | + (lambda lists (apply map list lists)) |

3478 | + |

3479 | +If zip is passed n lists, it returns a list as long as the shortest |

3480 | +of these lists, each element of which is an n-element list |

3481 | +comprised of the corresponding elements from the parameter lists. |

3482 | + |

3483 | + (zip '(one two three) |

3484 | + '(1 2 3) |

3485 | + '(odd even odd even odd even odd even)) |

3486 | + => ((one 1 odd) (two 2 even) (three 3 odd)) |

3487 | + |

3488 | + (zip '(1 2 3)) => ((1) (2) (3)) |

3489 | + |

3490 | +At least one of the argument lists must be finite: |

3491 | + |

3492 | + (zip '(3 1 4 1) (circular-list #f #t)) |

3493 | + => ((3 #f) (1 #t) (4 #f) (1 #t)) |

3494 | + |

3495 | +<procedure>(unzip1 list) -> list</procedure><br> |

3496 | +<procedure>(unzip2 list) -> [list list]</procedure><br> |

3497 | +<procedure>(unzip3 list) -> [list list list]</procedure><br> |

3498 | +<procedure>(unzip4 list) -> [list list list list]</procedure><br> |

3499 | +<procedure>(unzip5 list) -> [list list list list list]</procedure><br> |

3500 | + |

3501 | +unzip1 takes a list of lists, where every list must contain at |

3502 | +least one element, and returns a list containing the initial |

3503 | +element of each such list. That is, it returns (map car lists). |

3504 | +unzip2 takes a list of lists, where every list must contain at |

3505 | +least two elements, and returns two values: a list of the first |

3506 | +elements, and a list of the second elements. unzip3 does the same |

3507 | +for the first three elements of the lists, and so forth. |

3508 | + |

3509 | + (unzip2 '((1 one) (2 two) (3 three))) => |

3510 | + (1 2 3) |

3511 | + (one two three) |

3512 | + |

3513 | +<procedure>(count pred clist[1] clist[2]) -> integer</procedure><br> |

3514 | + |

3515 | +pred is a procedure taking as many arguments as there are lists and |

3516 | +returning a single value. It is applied element-wise to the |

3517 | +elements of the lists, and a count is tallied of the number of |

3518 | +elements that produce a true value. This count is returned. count |

3519 | +is "iterative" in that it is guaranteed to apply pred to the list |

3520 | +elements in a left-to-right order. The counting stops when the |

3521 | +shortest list expires. |

3522 | + |

3523 | + (count even? '(3 1 4 1 5 9 2 5 6)) => 3 |

3524 | + (count < '(1 2 4 8) '(2 4 6 8 10 12 14 16)) => 3 |

3525 | + |

3526 | +At least one of the argument lists must be finite: |

3527 | + |

3528 | + (count < '(3 1 4 1) (circular-list 1 10)) => 2 |

3529 | + |

3530 | +=== Fold, unfold & map |

3531 | + |

3532 | +<procedure>(fold kons knil clist[1] clist[2] ...) -> value</procedure><br> |

3533 | + |

3534 | +The fundamental list iterator. |

3535 | + |

3536 | +First, consider the single list-parameter case. If |

3537 | +clist[1] = (e[1] e[2] ... e[n]), then this procedure returns |

3538 | + |

3539 | + (kons e[n] ... (kons e[2] (kons e[1] knil)) ... ) |

3540 | + |

3541 | +That is, it obeys the (tail) recursion |

3542 | + |

3543 | + (fold kons knil lis) = (fold kons (kons (car lis) knil) (cdr lis)) |

3544 | + (fold kons knil '()) = knil |

3545 | + |

3546 | +Examples: |

3547 | + |

3548 | + (fold + 0 lis) ; Add up the elements of LIS. |

3549 | + (fold cons '() lis) ; Reverse LIS. |

3550 | + (fold cons tail rev-head) ; See APPEND-REVERSE. |

3551 | + |

3552 | + ;; How many symbols in LIS? |

3553 | + (fold (lambda (x count) (if (symbol? x) (+ count 1) count)) |

3554 | + 0 |

3555 | + lis) |

3556 | + |

3557 | + ;; Length of the longest string in LIS: |

3558 | + (fold (lambda (s max-len) (max max-len (string-length s))) |

3559 | + 0 |

3560 | + lis) |

3561 | + |

3562 | +If n list arguments are provided, then the kons function must take |

3563 | +n+1 parameters: one element from each list, and the "seed" or fold |

3564 | +state, which is initially knil. The fold operation terminates when |

3565 | +the shortest list runs out of values: |

3566 | + |

3567 | + (fold cons* '() '(a b c) '(1 2 3 4 5)) => (c 3 b 2 a 1) |

3568 | + |

3569 | +At least one of the list arguments must be finite. |

3570 | + |

3571 | +<procedure>(fold-right kons knil clist[1] clist[2] ...) -> value</procedure><br> |

3572 | + |

3573 | +The fundamental list recursion operator. |

3574 | + |

3575 | +First, consider the single list-parameter case. If |

3576 | +clist[1] = (e[1] e[2] ... e[n]), then this procedure returns |

3577 | + |

3578 | + (kons e[1] (kons e[2] ... (kons e[n] knil))) |

3579 | + |

3580 | +That is, it obeys the recursion |

3581 | + |

3582 | + (fold-right kons knil lis) = (kons (car lis) (fold-right kons knil (cdr lis))) |

3583 | + (fold-right kons knil '()) = knil |

3584 | + |

3585 | +Examples: |

3586 | + |

3587 | + (fold-right cons '() lis) ; Copy LIS. |

3588 | + |

3589 | + ;; Filter the even numbers out of LIS. |

3590 | + (fold-right (lambda (x l) (if (even? x) (cons x l) l)) '() lis)) |

3591 | + |

3592 | +If n list arguments are provided, then the kons function must take |

3593 | +n+1 parameters: one element from each list, and the "seed" or fold |

3594 | +state, which is initially knil. The fold operation terminates when |

3595 | +the shortest list runs out of values: |

3596 | + |

3597 | + (fold-right cons* '() '(a b c) '(1 2 3 4 5)) => (a 1 b 2 c 3) |

3598 | + |

3599 | +At least one of the list arguments must be finite. |

3600 | + |

3601 | +<procedure>(pair-fold kons knil clist[1] clist[2] ...) -> value</procedure><br> |

3602 | + |

3603 | +Analogous to fold, but kons is applied to successive sublists of |

3604 | +the lists, rather than successive elements -- that is, kons is |

3605 | +applied to the pairs making up the lists, giving this (tail) |

3606 | +recursion: |

3607 | + |

3608 | + (pair-fold kons knil lis) = (let ((tail (cdr lis))) |

3609 | + (pair-fold kons (kons lis knil) tail)) |

3610 | + (pair-fold kons knil '()) = knil |

3611 | + |

3612 | +For finite lists, the kons function may reliably apply set-cdr! to |

3613 | +the pairs it is given without altering the sequence of execution. |

3614 | + |

3615 | +Example: |

3616 | + |

3617 | + ;;; Destructively reverse a list. |

3618 | + (pair-fold (lambda (pair tail) (set-cdr! pair tail) pair) '() lis)) |

3619 | + |

3620 | +At least one of the list arguments must be finite. |

3621 | + |

3622 | +<procedure>(pair-fold-right kons knil clist[1] clist[2] ...) -> value</procedure><br> |

3623 | + |

3624 | +Holds the same relationship with fold-right that pair-fold holds |

3625 | +with fold. Obeys the recursion |

3626 | + |

3627 | + (pair-fold-right kons knil lis) = |

3628 | + (kons lis (pair-fold-right kons knil (cdr lis))) |

3629 | + (pair-fold-right kons knil '()) = knil |

3630 | + |

3631 | +Example: |

3632 | + |

3633 | + (pair-fold-right cons '() '(a b c)) => ((a b c) (b c) (c)) |

3634 | + |

3635 | +At least one of the list arguments must be finite. |

3636 | + |

3637 | +<procedure>(reduce f ridentity list) -> value</procedure><br> |

3638 | + |

3639 | +reduce is a variant of fold. |

3640 | + |

3641 | +ridentity should be a "right identity" of the procedure f -- that |

3642 | +is, for any value x acceptable to f, |

3643 | + |

3644 | + (f x ridentity) = x |

3645 | + |

3646 | +reduce has the following definition: |

3647 | + |

3648 | + If list = (), return ridentity; |

3649 | + Otherwise, return (fold f (car list) (cdr list)). |

3650 | + |

3651 | +...in other words, we compute (fold f ridentity list). |

3652 | + |

3653 | +Note that ridentity is used only in the empty-list case. You |

3654 | +typically use reduce when applying f is expensive and you'd like to |

3655 | +avoid the extra application incurred when fold applies f to the |

3656 | +head of list and the identity value, redundantly producing the same |

3657 | +value passed in to f. For example, if f involves searching a file |

3658 | +directory or performing a database query, this can be significant. |

3659 | +In general, however, fold is useful in many contexts where reduce |

3660 | +is not (consider the examples given in the fold definition -- only |

3661 | +one of the five folds uses a function with a right identity. The |

3662 | +other four may not be performed with reduce). |

3663 | + |

3664 | +Note: MIT Scheme and Haskell flip F's arg order for their reduce |

3665 | +and fold functions. |

3666 | + |

3667 | + ;; Take the max of a list of non-negative integers. |

3668 | + (reduce max 0 nums) ; i.e., (apply max 0 nums) |

3669 | + |

3670 | +<procedure>(reduce-right f ridentity list) -> value</procedure><br> |

3671 | + |

3672 | +reduce-right is the fold-right variant of reduce. It obeys the |

3673 | +following definition: |

3674 | + |

3675 | + (reduce-right f ridentity '()) = ridentity |

3676 | + (reduce-right f ridentity '(e[1])) = (f e[1] ridentity) = e[1] |

3677 | + (reduce-right f ridentity '(e[1] e[2] ...)) = |

3678 | + (f e[1] (reduce f ridentity (e[2] ...))) |

3679 | + |

3680 | +...in other words, we compute (fold-right f ridentity list). |

3681 | + |

3682 | + ;; Append a bunch of lists together. |

3683 | + ;; I.e., (apply append list-of-lists) |

3684 | + (reduce-right append '() list-of-lists) |

3685 | + |

3686 | +<procedure>(unfold p f g seed [tail-gen]) -> list</procedure><br> |

3687 | + |

3688 | +unfold is best described by its basic recursion: |

3689 | + |

3690 | + (unfold p f g seed) = |

3691 | + (if (p seed) (tail-gen seed) |

3692 | + (cons (f seed) |

3693 | + (unfold p f g (g seed)))) |

3694 | + |

3695 | +; p : Determines when to stop unfolding. |

3696 | +; f : Maps each seed value to the corresponding list element. |

3697 | +; g : Maps each seed value to next seed value. |

3698 | +; seed : The "state" value for the unfold. |

3699 | +; tail-gen : Creates the tail of the list; defaults to (lambda (x) '()) |

3700 | + |

3701 | +In other words, we use g to generate a sequence of seed values |

3702 | + seed, g(seed), g^2(seed), g^3(seed), ... |

3703 | + |

3704 | +These seed values are mapped to list elements by f, producing the |

3705 | +elements of the result list in a left-to-right order. P says when |

3706 | +to stop. |

3707 | + |

3708 | +unfold is the fundamental recursive list constructor, just as |

3709 | +fold-right is the fundamental recursive list consumer. While unfold |

3710 | +may seem a bit abstract to novice functional programmers, it can be |

3711 | +used in a number of ways: |

3712 | + |

3713 | + ;; List of squares: 1^2 ... 10^2 |

3714 | + (unfold (lambda (x) (> x 10)) |

3715 | + (lambda (x) (* x x)) |

3716 | + (lambda (x) (+ x 1)) |

3717 | + 1) |

3718 | + |

3719 | + (unfold null-list? car cdr lis) ; Copy a proper list. |

3720 | + |

3721 | + ;; Read current input port into a list of values. |

3722 | + (unfold eof-object? values (lambda (x) (read)) (read)) |

3723 | + |

3724 | + ;; Copy a possibly non-proper list: |

3725 | + (unfold not-pair? car cdr lis |

3726 | + values) |

3727 | + |

3728 | + ;; Append HEAD onto TAIL: |

3729 | + (unfold null-list? car cdr head |

3730 | + (lambda (x) tail)) |

3731 | + |

3732 | +Interested functional programmers may enjoy noting that fold-right |

3733 | +and unfold are in some sense inverses. That is, given operations |

3734 | +knull?, kar, kdr, kons, and knil satisfying |

3735 | + (kons (kar x) (kdr x)) = x and (knull? knil) = #t |

3736 | + |

3737 | +then |

3738 | + (fold-right kons knil (unfold knull? kar kdr x)) = x |

3739 | + |

3740 | +and |

3741 | + (unfold knull? kar kdr (fold-right kons knil x)) = x |

3742 | + |

3743 | +This combinator sometimes is called an "anamorphism;" when an |

3744 | +explicit tail-gen procedure is supplied, it is called an |

3745 | +"apomorphism." |

3746 | + |

3747 | +<procedure>(unfold-right p f g seed [tail]) -> list</procedure><br> |

3748 | + |

3749 | +unfold-right constructs a list with the following loop: |

3750 | + |

3751 | + (let lp ((seed seed) (lis tail)) |

3752 | + (if (p seed) lis |

3753 | + (lp (g seed) |

3754 | + (cons (f seed) lis)))) |

3755 | + |

3756 | +; p : Determines when to stop unfolding. |

3757 | +; f : Maps each seed value to the corresponding list element. |

3758 | +; g : Maps each seed value to next seed value. |

3759 | +; seed : The "state" value for the unfold. |

3760 | +; tail : list terminator; defaults to '(). |

3761 | + |

3762 | +In other words, we use g to generate a sequence of seed values |

3763 | + seed, g(seed), g^2(seed), g^3(seed), ... |

3764 | + |

3765 | +These seed values are mapped to list elements by f, producing the |

3766 | +elements of the result list in a right-to-left order. P says when |

3767 | +to stop. |

3768 | + |

3769 | +unfold-right is the fundamental iterative list constructor, just as |

3770 | +fold is the fundamental iterative list consumer. While unfold-right |

3771 | +may seem a bit abstract to novice functional programmers, it can be |

3772 | +used in a number of ways: |

3773 | + |

3774 | + ;; List of squares: 1^2 ... 10^2 |

3775 | + (unfold-right zero? |

3776 | + (lambda (x) (* x x)) |

3777 | + (lambda (x) (- x 1)) |

3778 | + 10) |

3779 | + |

3780 | + ;; Reverse a proper list. |

3781 | + (unfold-right null-list? car cdr lis) |

3782 | + |

3783 | + ;; Read current input port into a list of values. |

3784 | + (unfold-right eof-object? values (lambda (x) (read)) (read)) |

3785 | + |

3786 | + ;; (append-reverse rev-head tail) |

3787 | + (unfold-right null-list? car cdr rev-head tail) |

3788 | + |

3789 | +Interested functional programmers may enjoy noting that fold and |

3790 | +unfold-right are in some sense inverses. That is, given operations |

3791 | +knull?, kar, kdr, kons, and knil satisfying |

3792 | + (kons (kar x) (kdr x)) = x and (knull? knil) = #t |

3793 | + |

3794 | +then |

3795 | + (fold kons knil (unfold-right knull? kar kdr x)) = x |

3796 | + |

3797 | +and |

3798 | + (unfold-right knull? kar kdr (fold kons knil x)) = x |

3799 | + |

3800 | +This combinator presumably has some pretentious mathematical name; |

3801 | +interested readers are invited to communicate it to the author. |

3802 | + |

3803 | +<procedure>(map proc clist[1] clist[2] ...) -> list</procedure><br> |

3804 | + |

3805 | +This procedure is extended from its R5RS specification to allow the |

3806 | +arguments to be of unequal length; it terminates when the shortest |

3807 | +list runs out. |

3808 | + |

3809 | +At least one of the argument lists must be finite: |

3810 | + |

3811 | + (map + '(3 1 4 1) (circular-list 1 0)) => (4 1 5 1) |

3812 | + |

3813 | +<procedure>(for-each proc clist[1] clist[2] ...) -> unspecified</procedure><br> |

3814 | + |

3815 | +This procedure is extended from its R5RS specification to allow the |

3816 | +arguments to be of unequal length; it terminates when the shortest |

3817 | +list runs out. |

3818 | + |

3819 | +At least one of the argument lists must be finite. |

3820 | + |

3821 | +<procedure>(append-map f clist[1] clist[2] ...) -> value</procedure><br> |

3822 | +<procedure>(append-map! f clist[1] clist[2] ...) -> value</procedure><br> |

3823 | + |

3824 | +Equivalent to |

3825 | + (apply append (map f clist[1] clist[2] ...)) |

3826 | +and |

3827 | + (apply append! (map f clist[1] clist[2] ...)) |

3828 | + |

3829 | +Map f over the elements of the lists, just as in the map function. |

3830 | +However, the results of the applications are appended together to |

3831 | +make the final result. append-map uses append to append the results |

3832 | +together; append-map! uses append!. |

3833 | + |

3834 | +The dynamic order in which the various applications of f are made |

3835 | +is not specified. |

3836 | + |

3837 | +Example: |

3838 | + |

3839 | + (append-map! (lambda (x) (list x (- x))) '(1 3 8)) |

3840 | + => (1 -1 3 -3 8 -8) |

3841 | + |

3842 | +At least one of the list arguments must be finite. |

3843 | + |

3844 | +<procedure>(map! f list[1] clist[2] ...) -> list</procedure><br> |

3845 | + |

3846 | +Linear-update variant of map -- map! is allowed, but not required, |

3847 | +to alter the cons cells of list[1] to construct the result list. |

3848 | + |

3849 | +The dynamic order in which the various applications of f are made |

3850 | +is not specified. In the n-ary case, clist[2], clist[3], ... must |

3851 | +have at least as many elements as list[1]. |

3852 | + |

3853 | +<procedure>(map-in-order f clist[1] clist[2] ...) -> list</procedure><br> |

3854 | + |

3855 | +A variant of the map procedure that guarantees to apply f across |

3856 | +the elements of the list[i] arguments in a left-to-right order. |

3857 | +This is useful for mapping procedures that both have side effects |

3858 | +and return useful values. |

3859 | + |

3860 | +At least one of the list arguments must be finite. |

3861 | + |

3862 | +<procedure>(pair-for-each f clist[1] clist[2] ...) -> unspecific</procedure><br> |

3863 | + |

3864 | +Like for-each, but f is applied to successive sublists of the |

3865 | +argument lists. That is, f is applied to the cons cells of the |

3866 | +lists, rather than the lists' elements. These applications occur in |

3867 | +left-to-right order. |

3868 | + |

3869 | +The f procedure may reliably apply set-cdr! to the pairs it is |

3870 | +given without altering the sequence of execution. |

3871 | + |

3872 | + (pair-for-each (lambda (pair) (display pair) (newline)) '(a b c)) ==> |

3873 | + (a b c) |

3874 | + (b c) |

3875 | + (c) |

3876 | + |

3877 | +At least one of the list arguments must be finite. |

3878 | + |

3879 | +<procedure>(filter-map f clist[1] clist[2] ...) -> list</procedure><br> |

3880 | + |

3881 | +Like map, but only true values are saved. |

3882 | + |

3883 | + (filter-map (lambda (x) (and (number? x) (* x x))) '(a 1 b 3 c 7)) |

3884 | + => (1 9 49) |

3885 | + |

3886 | +The dynamic order in which the various applications of f are made |

3887 | +is not specified. |

3888 | + |

3889 | +At least one of the list arguments must be finite. |

3890 | + |

3891 | +=== Filtering & partitioning |

3892 | + |

3893 | +<procedure>(filter pred list) -> list</procedure><br> |

3894 | + |

3895 | +Return all the elements of list that satisfy predicate pred. The |

3896 | +list is not disordered -- elements that appear in the result list |

3897 | +occur in the same order as they occur in the argument list. The |

3898 | +returned list may share a common tail with the argument list. The |

3899 | +dynamic order in which the various applications of pred are made is |

3900 | +not specified. |

3901 | + |

3902 | + (filter even? '(0 7 8 8 43 -4)) => (0 8 8 -4) |

3903 | + |

3904 | +<procedure>(partition pred list) -> [list list]</procedure><br> |

3905 | + |

3906 | +Partitions the elements of list with predicate pred, and returns |

3907 | +two values: the list of in-elements and the list of out-elements. |

3908 | +The list is not disordered -- elements occur in the result lists in |

3909 | +the same order as they occur in the argument list. The dynamic |

3910 | +order in which the various applications of pred are made is not |

3911 | +specified. One of the returned lists may share a common tail with |

3912 | +the argument list. |

3913 | + |

3914 | + (partition symbol? '(one 2 3 four five 6)) => |

3915 | + (one four five) |

3916 | + (2 3 6) |

3917 | + |

3918 | +<procedure>(remove pred list) -> list</procedure><br> |

3919 | + |

3920 | +Returns list without the elements that satisfy predicate pred: |

3921 | + |

3922 | + (lambda (pred list) (filter (lambda (x) (not (pred x))) list)) |

3923 | + |

3924 | +The list is not disordered -- elements that appear in the result |

3925 | +list occur in the same order as they occur in the argument list. |

3926 | +The returned list may share a common tail with the argument list. |

3927 | +The dynamic order in which the various applications of pred are |

3928 | +made is not specified. |

3929 | + |

3930 | + (remove even? '(0 7 8 8 43 -4)) => (7 43) |

3931 | + |

3932 | +<procedure>(filter! pred list) -> list</procedure><br> |

3933 | +<procedure>(partition! pred list) -> [list list]</procedure><br> |

3934 | +<procedure>(remove! pred list) -> list</procedure><br> |

3935 | + |

3936 | +Linear-update variants of filter, partition and remove. These |

3937 | +procedures are allowed, but not required, to alter the cons cells |

3938 | +in the argument list to construct the result lists. |

3939 | + |

3940 | +=== Searching |

3941 | + |

3942 | +<procedure>(find pred clist) -> value</procedure><br> |

3943 | + |

3944 | +Return the first element of clist that satisfies predicate pred; |

3945 | +false if no element does. |

3946 | + |

3947 | + (find even? '(3 1 4 1 5 9)) => 4 |

3948 | + |

3949 | +Note that find has an ambiguity in its lookup semantics -- if find |

3950 | +returns #f, you cannot tell (in general) if it found a #f element |

3951 | +that satisfied pred, or if it did not find any element at all. In |

3952 | +many situations, this ambiguity cannot arise -- either the list |

3953 | +being searched is known not to contain any #f elements, or the list |

3954 | +is guaranteed to have an element satisfying pred. However, in cases |

3955 | +where this ambiguity can arise, you should use find-tail instead of |

3956 | +find -- find-tail has no such ambiguity: |

3957 | + |

3958 | + (cond ((find-tail pred lis) => (lambda (pair) ...)) ; Handle (CAR PAIR) |

3959 | + (else ...)) ; Search failed. |

3960 | + |

3961 | +<procedure>(find-tail pred clist) -> pair or false</procedure><br> |

3962 | + |

3963 | +Return the first pair of clist whose car satisfies pred. If no pair |

3964 | +does, return false. |

3965 | + |

3966 | +find-tail can be viewed as a general-predicate variant of the |

3967 | +member function. |

3968 | + |

3969 | +Examples: |

3970 | + |

3971 | + (find-tail even? '(3 1 37 -8 -5 0 0)) => (-8 -5 0 0) |

3972 | + (find-tail even? '(3 1 37 -5)) => #f |

3973 | + |

3974 | + ;; MEMBER X LIS: |

3975 | + (find-tail (lambda (elt) (equal? x elt)) lis) |

3976 | + |

3977 | +In the circular-list case, this procedure "rotates" the list. |

3978 | + |

3979 | +Find-tail is essentially drop-while, where the sense of the |

3980 | +predicate is inverted: Find-tail searches until it finds an element |

3981 | +satisfying the predicate; drop-while searches until it finds an |

3982 | +element that doesn't satisfy the predicate. |

3983 | + |

3984 | +<procedure>(take-while pred clist) -> list</procedure><br> |

3985 | +<procedure>(take-while! pred clist) -> list</procedure><br> |

3986 | + |

3987 | +Returns the longest initial prefix of clist whose elements all |

3988 | +satisfy the predicate pred. |

3989 | + |

3990 | +Take-while! is the linear-update variant. It is allowed, but not |

3991 | +required, to alter the argument list to produce the result. |

3992 | + |

3993 | + (take-while even? '(2 18 3 10 22 9)) => (2 18) |

3994 | + |

3995 | +<procedure>(drop-while pred clist) -> list</procedure><br> |

3996 | + |

3997 | +Drops the longest initial prefix of clist whose elements all |

3998 | +satisfy the predicate pred, and returns the rest of the list. |

3999 | + |

4000 | + (drop-while even? '(2 18 3 10 22 9)) => (3 10 22 9) |

4001 | + |

4002 | +The circular-list case may be viewed as "rotating" the list. |

4003 | + |

4004 | +<procedure>(span pred clist) -> [list clist]</procedure><br> |

4005 | +<procedure>(span! pred list ) -> [list list]</procedure><br> |

4006 | +<procedure>(break pred clist) -> [list clist]</procedure><br> |

4007 | +<procedure>(break! pred list ) -> [list list]</procedure><br> |

4008 | + |

4009 | +Span splits the list into the longest initial prefix whose elements |

4010 | +all satisfy pred, and the remaining tail. Break inverts the sense |

4011 | +of the predicate: the tail commences with the first element of the |

4012 | +input list that satisfies the predicate. |

4013 | + |

4014 | +In other words: span finds the intial span of elements satisfying |

4015 | +pred, and break breaks the list at the first element satisfying |

4016 | +pred. |

4017 | + |

4018 | +Span is equivalent to |

4019 | + |

4020 | + (values (take-while pred clist) |

4021 | + (drop-while pred clist)) |

4022 | + |

4023 | +Span! and break! are the linear-update variants. They are allowed, |

4024 | +but not required, to alter the argument list to produce the result. |

4025 | + |

4026 | + (span even? '(2 18 3 10 22 9)) => |

4027 | + (2 18) |

4028 | + (3 10 22 9) |

4029 | + |

4030 | + (break even? '(3 1 4 1 5 9)) => |

4031 | + (3 1) |

4032 | + (4 1 5 9) |

4033 | + |

4034 | +<procedure>(any pred clist[1] clist[2] ...) -> value</procedure><br> |

4035 | + |

4036 | +Applies the predicate across the lists, returning true if the |

4037 | +predicate returns true on any application. |

4038 | + |

4039 | +If there are n list arguments clist[1] ... clist[n], then pred must |

4040 | +be a procedure taking n arguments and returning a boolean result. |

4041 | + |

4042 | +any applies pred to the first elements of the clist[i] parameters. |

4043 | +If this application returns a true value, any immediately returns |

4044 | +that value. Otherwise, it iterates, applying pred to the second |

4045 | +elements of the clist[i] parameters, then the third, and so forth. |

4046 | +The iteration stops when a true value is produced or one of the |

4047 | +lists runs out of values; in the latter case, any returns #f. The |

4048 | +application of pred to the last element of the lists is a tail |

4049 | +call. |

4050 | + |

4051 | +Note the difference between find and any -- find returns the |

4052 | +element that satisfied the predicate; any returns the true value |

4053 | +that the predicate produced. |

4054 | + |

4055 | +Like every, any's name does not end with a question mark -- this is |

4056 | +to indicate that it does not return a simple boolean (#t or #f), |

4057 | +but a general value. |

4058 | + |

4059 | + (any integer? '(a 3 b 2.7)) => #t |

4060 | + (any integer? '(a 3.1 b 2.7)) => #f |

4061 | + (any < '(3 1 4 1 5) |

4062 | + '(2 7 1 8 2)) => #t |

4063 | + |

4064 | +<procedure>(every pred clist[1] clist[2] ...) -> value</procedure><br> |

4065 | + |

4066 | +Applies the predicate across the lists, returning true if the |

4067 | +predicate returns true on every application. |

4068 | + |

4069 | +If there are n list arguments clist[1] ... clist[n], then pred must |

4070 | +be a procedure taking n arguments and returning a boolean result. |

4071 | + |

4072 | +every applies pred to the first elements of the clist[i] |

4073 | +parameters. If this application returns false, every immediately |

4074 | +returns false. Otherwise, it iterates, applying pred to the second |

4075 | +elements of the clist[i] parameters, then the third, and so forth. |

4076 | +The iteration stops when a false value is produced or one of the |

4077 | +lists runs out of values. In the latter case, every returns the |

4078 | +true value produced by its final application of pred. The |

4079 | +application of pred to the last element of the lists is a tail |

4080 | +call. |

4081 | + |

4082 | +If one of the clist[i] has no elements, every simply returns #t. |

4083 | + |

4084 | +Like any, every's name does not end with a question mark -- this is |

4085 | +to indicate that it does not return a simple boolean (#t or #f), |

4086 | +but a general value. |

4087 | + |

4088 | +<procedure>(list-index pred clist[1] clist[2] ...) -> integer or false</procedure><br> |

4089 | + |

4090 | +Return the index of the leftmost element that satisfies pred. |

4091 | + |

4092 | +If there are n list arguments clist[1] ... clist[n], then pred must |

4093 | +be a function taking n arguments and returning a boolean result. |

4094 | + |

4095 | +list-index applies pred to the first elements of the clist[i] |

4096 | +parameters. If this application returns true, list-index |

4097 | +immediately returns zero. Otherwise, it iterates, applying pred to |

4098 | +the second elements of the clist[i] parameters, then the third, and |

4099 | +so forth. When it finds a tuple of list elements that cause pred to |

4100 | +return true, it stops and returns the zero-based index of that |

4101 | +position in the lists. |

4102 | + |

4103 | +The iteration stops when one of the lists runs out of values; in |

4104 | +this case, list-index returns #f. |

4105 | + |

4106 | + (list-index even? '(3 1 4 1 5 9)) => 2 |

4107 | + (list-index < '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => 1 |

4108 | + (list-index = '(3 1 4 1 5 9 2 5 6) '(2 7 1 8 2)) => #f |

4109 | + |

4110 | +<procedure>(member x list [=]) -> list</procedure><br> |

4111 | + |

4112 | +member is extended from its R5RS definition to allow the client to |

4113 | +pass in an optional equality procedure = used to compare keys. |

4114 | + |

4115 | +The comparison procedure is used to compare the elements e[i] of |

4116 | +list to the key x in this way: |

4117 | + (= x e[i]) ; list is (E1 ... En) |

4118 | + |

4119 | +That is, the first argument is always x, and the second argument is |

4120 | +one of the list elements. Thus one can reliably find the first |

4121 | +element of list that is greater than five with |

4122 | + (member 5 list <) |

4123 | + |

4124 | +Note that fully general list searching may be performed with the |

4125 | +find-tail and find procedures, e.g. |

4126 | + |

4127 | + (find-tail even? list) ; Find the first elt with an even key. |

4128 | + |

4129 | +=== Deletion |

4130 | + |

4131 | +<procedure>(delete x list [=]) -> list</procedure><br> |

4132 | +<procedure>(delete! x list [=]) -> list</procedure><br> |

4133 | + |

4134 | +delete uses the comparison procedure =, which defaults to equal?, |

4135 | +to find all elements of list that are equal to x, and deletes them |

4136 | +from list. The dynamic order in which the various applications of = |

4137 | +are made is not specified. |

4138 | + |

4139 | +The list is not disordered -- elements that appear in the result |

4140 | +list occur in the same order as they occur in the argument list. |

4141 | +The result may share a common tail with the argument list. |

4142 | + |

4143 | +Note that fully general element deletion can be performed with the |

4144 | +remove and remove! procedures, e.g.: |

4145 | + |

4146 | + ;; Delete all the even elements from LIS: |

4147 | + (remove even? lis) |

4148 | + |

4149 | +The comparison procedure is used in this way: (= x e[i]). That is, |

4150 | +x is always the first argument, and a list element is always the |

4151 | +second argument. The comparison procedure will be used to compare |

4152 | +each element of list exactly once; the order in which it is applied |

4153 | +to the various e[i] is not specified. Thus, one can reliably remove |

4154 | +all the numbers greater than five from a list with |

4155 | + (delete 5 list <) |

4156 | + |

4157 | +delete! is the linear-update variant of delete. It is allowed, but |

4158 | +not required, to alter the cons cells in its argument list to |

4159 | +construct the result. |

4160 | + |

4161 | +<procedure>(delete-duplicates list [=]) -> list</procedure><br> |

4162 | +<procedure>(delete-duplicates! list [=]) -> list</procedure><br> |

4163 | + |

4164 | +delete-duplicates removes duplicate elements from the list |

4165 | +argument. If there are multiple equal elements in the argument |

4166 | +list, the result list only contains the first or leftmost of these |

4167 | +elements in the result. The order of these surviving elements is |

4168 | +the same as in the original list -- delete-duplicates does not |

4169 | +disorder the list (hence it is useful for "cleaning up" association |

4170 | +lists). |

4171 | + |

4172 | +The = parameter is used to compare the elements of the list; it |

4173 | +defaults to equal?. If x comes before y in list, then the |

4174 | +comparison is performed (= x y). The comparison procedure will be |

4175 | +used to compare each pair of elements in list no more than once; |

4176 | +the order in which it is applied to the various pairs is not |

4177 | +specified. |

4178 | + |

4179 | +Implementations of delete-duplicates are allowed to share common |

4180 | +tails between argument and result lists -- for example, if the list |

4181 | +argument contains only unique elements, it may simply return |

4182 | +exactly this list. |

4183 | + |

4184 | +Be aware that, in general, delete-duplicates runs in time O(n^2) |

4185 | +for n-element lists. Uniquifying long lists can be accomplished in |

4186 | +O(n lg n) time by sorting the list to bring equal elements |

4187 | +together, then using a linear-time algorithm to remove equal |

4188 | +elements. Alternatively, one can use algorithms based on |

4189 | +element-marking, with linear-time results. |

4190 | + |

4191 | +delete-duplicates! is the linear-update variant of |

4192 | +delete-duplicates; it is allowed, but not required, to alter the |

4193 | +cons cells in its argument list to construct the result. |

4194 | + |

4195 | + (delete-duplicates '(a b a c a b c z)) => (a b c z) |

4196 | + |

4197 | + ;; Clean up an alist: |

4198 | + (delete-duplicates '((a . 3) (b . 7) (a . 9) (c . 1)) |

4199 | + (lambda (x y) (eq? (car x) (car y)))) |

4200 | + => ((a . 3) (b . 7) (c . 1)) |

4201 | + |

4202 | +=== Association lists |

4203 | + |

4204 | +An "association list" (or "alist") is a list of pairs. The car of each |

4205 | +pair contains a key value, and the cdr contains the associated data |

4206 | +value. They can be used to construct simple look-up tables in Scheme. |

4207 | +Note that association lists are probably inappropriate for |

4208 | +performance-critical use on large data; in these cases, hash tables or |

4209 | +some other alternative should be employed. |

4210 | + |

4211 | +<procedure>(assoc key alist [=]) -> pair or #f</procedure><br> |

4212 | + |

4213 | +assoc is extended from its R5RS definition to allow the client to |

4214 | +pass in an optional equality procedure = used to compare keys. |

4215 | + |

4216 | +The comparison procedure is used to compare the elements e[i] of |

4217 | +list to the key parameter in this way: |

4218 | + (= key (car e[i])) ; list is (E1 ... En) |

4219 | +That is, the first argument is always key, and the second argument |

4220 | +is one of the list elements. Thus one can reliably find the first |

4221 | +entry of alist whose key is greater than five with |

4222 | + (assoc 5 alist <) |

4223 | + |

4224 | +Note that fully general alist searching may be performed with the |

4225 | +find-tail and find procedures, e.g. |

4226 | + |

4227 | + ;; Look up the first association in alist with an even key: |

4228 | + (find (lambda (a) (even? (car a))) alist) |

4229 | + |

4230 | +<procedure>(alist-cons key datum alist) -> alist</procedure><br> |

4231 | + |

4232 | + (lambda (key datum alist) (cons (cons key datum) alist)) |

4233 | + |

4234 | +Cons a new alist entry mapping key -> datum onto alist. |

4235 | +<procedure>(alist-copy alist) -> alist</procedure><br> |

4236 | +Make a fresh copy of alist. This means copying each pair that forms |

4237 | +an association as well as the spine of the list, i.e. |

4238 | + |

4239 | + (lambda (a) (map (lambda (elt) (cons (car elt) (cdr elt))) a)) |

4240 | + |

4241 | +<procedure>(alist-delete key alist [=]) -> alist</procedure><br> |

4242 | +<procedure>(alist-delete! key alist [=]) -> alist</procedure><br> |

4243 | + |

4244 | +alist-delete deletes all associations from alist with the given |

4245 | +key, using key-comparison procedure =, which defaults to equal?. |

4246 | +The dynamic order in which the various applications of = are made |

4247 | +is not specified. |

4248 | + |

4249 | +Return values may share common tails with the alist argument. The |

4250 | +alist is not disordered -- elements that appear in the result alist |

4251 | +occur in the same order as they occur in the argument alist. |

4252 | + |

4253 | +The comparison procedure is used to compare the element keys k[i] |

4254 | +of alist's entries to the key parameter in this way: (= key k[i]). |

4255 | +Thus, one can reliably remove all entries of alist whose key is |

4256 | +greater than five with (alist-delete 5 alist <) |

4257 | + |

4258 | +alist-delete! is the linear-update variant of alist-delete. It is |

4259 | +allowed, but not required, to alter cons cells from the alist |

4260 | +parameter to construct the result. |

4261 | + |

4262 | +=== Set operations on lists |

4263 | + |

4264 | +Be aware that these procedures typically run in time O(n * m) for n- |

4265 | +and m-element list arguments. Performance-critical applications |

4266 | +operating upon large sets will probably wish to use other data |

4267 | +structures and algorithms. |

4268 | + |

4269 | +<procedure>(lset<= = list[1] ...) -> boolean</procedure><br> |

4270 | + |

4271 | +Returns true iff every list[i] is a subset of list[i+1], using = |

4272 | +for the element-equality procedure. List A is a subset of list B if |

4273 | +every element in A is equal to some element of B. When performing |

4274 | +an element comparison, the = procedure's first argument is an |

4275 | +element of A; its second, an element of B. |

4276 | + |

4277 | + (lset<= eq? '(a) '(a b a) '(a b c c)) => #t |

4278 | + (lset<= eq?) => #t ; Trivial cases |

4279 | + (lset<= eq? '(a)) => #t |

4280 | + |

4281 | +<procedure>(lset= = list[1] list[2] ...) -> boolean</procedure><br> |

4282 | + |

4283 | +Returns true iff every list[i] is set-equal to list[i+1], using = |

4284 | +for the element-equality procedure. "Set-equal" simply means that |

4285 | +list[i] is a subset of list[i+1], and list[i+1] is a subset of list |

4286 | +[i]. The = procedure's first argument is an element of list[i]; its |

4287 | +second is an element of list[i+1]. |

4288 | + |

4289 | + (lset= eq? '(b e a) '(a e b) '(e e b a)) => #t |

4290 | + (lset= eq?) => #t ; Trivial cases |

4291 | + (lset= eq? '(a)) => #t |

4292 | + |

4293 | +<procedure>(lset-adjoin = list elt[1] ...) -> list</procedure><br> |

4294 | + |

4295 | +Adds the elt[i] elements not already in the list parameter to the |

4296 | +result list. The result shares a common tail with the list |

4297 | +parameter. The new elements are added to the front of the list, but |

4298 | +no guarantees are made about their order. The = parameter is an |

4299 | +equality procedure used to determine if an elt[i] is already a |

4300 | +member of list. Its first argument is an element of list; its |

4301 | +second is one of the elt[i]. |

4302 | + |

4303 | +The list parameter is always a suffix of the result -- even if the |

4304 | +list parameter contains repeated elements, these are not reduced. |

4305 | + |

4306 | + (lset-adjoin eq? '(a b c d c e) 'a 'e 'i 'o 'u) => (u o i a b c d c e) |

4307 | + |

4308 | +<procedure>(lset-union = list[1] ...) -> list</procedure><br> |

4309 | + |

4310 | +Returns the union of the lists, using = for the element-equality |

4311 | +procedure. |

4312 | + |

4313 | +The union of lists A and B is constructed as follows: |

4314 | +* If A is the empty list, the answer is B (or a copy of B). |

4315 | +* Otherwise, the result is initialised to be list A (or a copy of |

4316 | +A). |

4317 | +* Proceed through the elements of list B in a left-to-right |

4318 | +order. If b is such an element of B, compare every element r of |

4319 | +the current result list to b: (= r b). If all comparisons fail, |

4320 | +b is consed onto the front of the result. |

4321 | + |

4322 | +However, there is no guarantee that = will be applied to every pair |

4323 | +of arguments from A and B. In particular, if A is eq? to B, the |

4324 | +operation may immediately terminate. |

4325 | + |

4326 | +In the n-ary case, the two-argument list-union operation is simply |

4327 | +folded across the argument lists. |

4328 | + |

4329 | + (lset-union eq? '(a b c d e) '(a e i o u)) => |

4330 | + (u o i a b c d e) |

4331 | + |

4332 | + ;; Repeated elements in LIST1 are preserved. |

4333 | + (lset-union eq? '(a a c) '(x a x)) => (x a a c) |

4334 | + |

4335 | + ;; Trivial cases |

4336 | + (lset-union eq?) => () |

4337 | + (lset-union eq? '(a b c)) => (a b c) |

4338 | + |

4339 | +<procedure>(lset-intersection = list[1] list[2] ...) -> list</procedure><br> |

4340 | + |

4341 | +Returns the intersection of the lists, using = for the |

4342 | +element-equality procedure. |

4343 | + |

4344 | +The intersection of lists A and B is comprised of every element of |

4345 | +A that is = to some element of B: (= a b), for a in A, and b in B. |

4346 | +Note this implies that an element which appears in B and multiple |

4347 | +times in list A will also appear multiple times in the result. |

4348 | + |

4349 | +The order in which elements appear in the result is the same as |

4350 | +they appear in list[1] -- that is, lset-intersection essentially |

4351 | +filters list[1], without disarranging element order. The result may |

4352 | +share a common tail with list[1]. |

4353 | + |

4354 | +In the n-ary case, the two-argument list-intersection operation is |

4355 | +simply folded across the argument lists. However, the dynamic order |

4356 | +in which the applications of = are made is not specified. The |

4357 | +procedure may check an element of list[1] for membership in every |

4358 | +other list before proceeding to consider the next element of list |

4359 | +[1], or it may completely intersect list[1] and list[2] before |

4360 | +proceeding to list[3], or it may go about its work in some third |

4361 | +order. |

4362 | + |

4363 | + (lset-intersection eq? '(a b c d e) '(a e i o u)) => (a e) |

4364 | + |

4365 | + ;; Repeated elements in LIST1 are preserved. |

4366 | + (lset-intersection eq? '(a x y a) '(x a x z)) => '(a x a) |

4367 | + |

4368 | + (lset-intersection eq? '(a b c)) => (a b c) ; Trivial case |

4369 | + |

4370 | +<procedure>(lset-difference = list[1] list[2] ...) -> list</procedure><br> |

4371 | + |

4372 | +Returns the difference of the lists, using = for the |

4373 | +element-equality procedure -- all the elements of list[1] that are |

4374 | +not = to any element from one of the other list[i] parameters. |

4375 | + |

4376 | +The = procedure's first argument is always an element of list[1]; |

4377 | +its second is an element of one of the other list[i]. Elements that |

4378 | +are repeated multiple times in the list[1] parameter will occur |

4379 | +multiple times in the result. The order in which elements appear in |

4380 | +the result is the same as they appear in list[1] -- that is, |

4381 | +lset-difference essentially filters list[1], without disarranging |

4382 | +element order. The result may share a common tail with list[1]. The |

4383 | +dynamic order in which the applications of = are made is not |

4384 | +specified. The procedure may check an element of list[1] for |

4385 | +membership in every other list before proceeding to consider the |

4386 | +next element of list[1], or it may completely compute the |

4387 | +difference of list[1] and list[2] before proceeding to list[3], or |

4388 | +it may go about its work in some third order. |

4389 | + |

4390 | + (lset-difference eq? '(a b c d e) '(a e i o u)) => (b c d) |

4391 | + (lset-difference eq? '(a b c)) => (a b c) ; Trivial case |

4392 | + |

4393 | +<procedure>(lset-xor = list[1] ...) -> list</procedure><br> |

4394 | + |

4395 | +Returns the exclusive-or of the sets, using = for the |

4396 | +element-equality procedure. If there are exactly two lists, this is |

4397 | +all the elements that appear in exactly one of the two lists. The |

4398 | +operation is associative, and thus extends to the n-ary case -- the |

4399 | +elements that appear in an odd number of the lists. The result may |

4400 | +share a common tail with any of the list[i] parameters. |

4401 | + |

4402 | +More precisely, for two lists A and B, A xor B is a list of |

4403 | +* every element a of A such that there is no element b of B such |

4404 | +that (= a b), and |

4405 | +* every element b of B such that there is no element a of A such |

4406 | +that (= b a). |

4407 | + |

4408 | +However, an implementation is allowed to assume that = is symmetric-- |

4409 | +that is, that |

4410 | + (= a b) => (= b a). |

4411 | + |

4412 | +This means, for example, that if a comparison (= a b) produces true |

4413 | +for some a in A and b in B, both a and b may be removed from |

4414 | +inclusion in the result. |

4415 | + |

4416 | +In the n-ary case, the binary-xor operation is simply folded across |

4417 | +the lists. |

4418 | + |

4419 | + (lset-xor eq? '(a b c d e) '(a e i o u)) => (d c b i o u) |

4420 | + |

4421 | + ;; Trivial cases. |

4422 | + (lset-xor eq?) => () |

4423 | + (lset-xor eq? '(a b c d e)) => (a b c d e) |

4424 | + |

4425 | +<procedure>(lset-diff+intersection = list[1] list[2] ...) -> [list list]</procedure><br> |

4426 | + |

4427 | +Returns two values -- the difference and the intersection of the |

4428 | +lists. Is equivalent to |

4429 | + |

4430 | + (values (lset-difference = list[1] list[2] ...) |

4431 | + (lset-intersection = list[1] |

4432 | + (lset-union = list[2] ...))) |

4433 | + |

4434 | +but can be implemented more efficiently. |

4435 | + |

4436 | +The = procedure's first argument is an element of list[1]; its |

4437 | +second is an element of one of the other list[i]. |

4438 | + |

4439 | +Either of the answer lists may share a common tail with list[1]. |

4440 | +This operation essentially partitions list[1]. |

4441 | + |

4442 | +<procedure>(lset-union! = list[1] ...) -> list</procedure><br> |

4443 | +<procedure>(lset-intersection! = list[1] list[2] ...) -> list</procedure><br> |

4444 | +<procedure>(lset-difference! = list[1] list[2] ...) -> list</procedure><br> |

4445 | +<procedure>(lset-xor! = list[1] ...) -> list</procedure><br> |

4446 | +<procedure>(lset-diff+intersection! = list[1] list[2] ...) -> [list list]</procedure><br> |

4447 | + |

4448 | +These are linear-update variants. They are allowed, but not |

4449 | +required, to use the cons cells in their first list parameter to |

4450 | +construct their answer. lset-union! is permitted to recycle cons |

4451 | +cells from any of its list arguments. |

4452 | + |

4453 | +=== Author |

4454 | + |

4455 | +[[http://www.ai.mit.edu/~shivers/|Olin Shivers]] |

4456 | + |

4457 | +== License |

4458 | + |

4459 | + Copyright (C) Olin Shivers (1998, 1999). All Rights Reserved. |

4460 | + |

4461 | + Permission is hereby granted, free of charge, to any person obtaining a |

4462 | + copy of this software and associated documentation files (the |

4463 | + "Software"), to deal in the Software without restriction, including |

4464 | + without limitation the rights to use, copy, modify, merge, publish, |

4465 | + distribute, sublicense, and/or sell copies of the Software, and to |

4466 | + permit persons to whom the Software is furnished to do so, subject to |

4467 | + the following conditions: |

4468 | + |

4469 | + The above copyright notice and this permission notice shall be included |

4470 | + in all copies or substantial portions of the Software. |

4471 | + |

4472 | + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS |

4473 | + OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |

4474 | + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |

4475 | + IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY |

4476 | + CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, |

4477 | + TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE |

4478 | + SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |

4479 | -- |

4480 | 1.6.5.2 |

4481 | |

4482 |