Commit | Line | Data |
---|---|---|
4c731ece NJ |
1 | @page |
2 | @node Compound Data Types | |
3 | @chapter Compound Data Types | |
4 | ||
5 | This chapter describes Guile's compound data types. By @dfn{compound} | |
6 | we mean that the primary purpose of these data types is to act as | |
7 | containers for other kinds of data (including other compound objects). | |
8 | For instance, a (non-uniform) vector with length 5 is a container that | |
9 | can hold five arbitrary Scheme objects. | |
10 | ||
11 | The various kinds of container object differ from each other in how | |
12 | their memory is allocated, how they are indexed, and how particular | |
13 | values can be looked up within them. | |
14 | ||
15 | @menu | |
16 | * Pairs:: Scheme's basic building block. | |
17 | * Lists:: Special list functions supported by Guile. | |
18 | * Vectors:: One-dimensional arrays of Scheme objects. | |
19 | * Records:: | |
20 | * Structures:: | |
21 | * Arrays:: Arrays of values. | |
22 | * Association Lists and Hash Tables:: Dictionary data types. | |
23 | @end menu | |
24 | ||
25 | ||
26 | @node Pairs | |
27 | @section Pairs | |
28 | @tpindex Pairs | |
29 | ||
30 | @c FIXME::martin: Review me! | |
31 | ||
32 | Pairs are used to combine two Scheme objects into one compound object. | |
33 | Hence the name: A pair stores a pair of objects. | |
34 | ||
35 | The data type @dfn{pair} is extremely important in Scheme, just like in | |
36 | any other Lisp dialect. The reason is that pairs are not only used to | |
37 | make two values available as one object, but that pairs are used for | |
38 | constructing lists of values. Because lists are so important in Scheme, | |
39 | they are described in a section of their own (@pxref{Lists}). | |
40 | ||
41 | Pairs can literally get entered in source code or at the REPL, in the | |
42 | so-called @dfn{dotted list} syntax. This syntax consists of an opening | |
43 | parentheses, the first element of the pair, a dot, the second element | |
44 | and a closing parentheses. The following example shows how a pair | |
45 | consisting of the two numbers 1 and 2, and a pair containing the symbols | |
46 | @code{foo} and @code{bar} can be entered. It is very important to write | |
47 | the whitespace before and after the dot, because otherwise the Scheme | |
85a9b4ed | 48 | parser would not be able to figure out where to split the tokens. |
4c731ece NJ |
49 | |
50 | @lisp | |
51 | (1 . 2) | |
52 | (foo . bar) | |
53 | @end lisp | |
54 | ||
55 | But beware, if you want to try out these examples, you have to | |
56 | @dfn{quote} the expressions. More information about quotation is | |
57 | available in the section (REFFIXME). The correct way to try these | |
58 | examples is as follows. | |
59 | ||
60 | @lisp | |
61 | '(1 . 2) | |
62 | @result{} | |
63 | (1 . 2) | |
64 | '(foo . bar) | |
65 | @result{} | |
66 | (foo . bar) | |
67 | @end lisp | |
68 | ||
69 | A new pair is made by calling the procedure @code{cons} with two | |
70 | arguments. Then the argument values are stored into a newly allocated | |
71 | pair, and the pair is returned. The name @code{cons} stands for | |
72 | "construct". Use the procedure @code{pair?} to test whether a | |
73 | given Scheme object is a pair or not. | |
74 | ||
75 | @rnindex cons | |
76 | @deffn {Scheme Procedure} cons x y | |
77 | @deffnx {C Function} scm_cons (x, y) | |
78 | Return a newly allocated pair whose car is @var{x} and whose | |
79 | cdr is @var{y}. The pair is guaranteed to be different (in the | |
80 | sense of @code{eq?}) from every previously existing object. | |
81 | @end deffn | |
82 | ||
83 | @rnindex pair? | |
84 | @deffn {Scheme Procedure} pair? x | |
85 | @deffnx {C Function} scm_pair_p (x) | |
86 | Return @code{#t} if @var{x} is a pair; otherwise return | |
87 | @code{#f}. | |
88 | @end deffn | |
89 | ||
90 | The two parts of a pair are traditionally called @dfn{car} and | |
91 | @dfn{cdr}. They can be retrieved with procedures of the same name | |
92 | (@code{car} and @code{cdr}), and can be modified with the procedures | |
93 | @code{set-car!} and @code{set-cdr!}. Since a very common operation in | |
94 | Scheme programs is to access the car of a pair, or the car of the cdr of | |
95 | a pair, etc., the procedures called @code{caar}, @code{cadr} and so on | |
96 | are also predefined. | |
97 | ||
98 | @rnindex car | |
99 | @rnindex cdr | |
100 | @deffn {Scheme Procedure} car pair | |
101 | @deffnx {Scheme Procedure} cdr pair | |
102 | Return the car or the cdr of @var{pair}, respectively. | |
103 | @end deffn | |
104 | ||
105 | @deffn {Scheme Procedure} caar pair | |
106 | @deffnx {Scheme Procedure} cadr pair @dots{} | |
107 | @deffnx {Scheme Procedure} cdddar pair | |
108 | @deffnx {Scheme Procedure} cddddr pair | |
109 | These procedures are compositions of @code{car} and @code{cdr}, where | |
110 | for example @code{caddr} could be defined by | |
111 | ||
112 | @lisp | |
113 | (define caddr (lambda (x) (car (cdr (cdr x))))) | |
114 | @end lisp | |
115 | @end deffn | |
116 | ||
117 | @rnindex set-car! | |
118 | @deffn {Scheme Procedure} set-car! pair value | |
119 | @deffnx {C Function} scm_set_car_x (pair, value) | |
120 | Stores @var{value} in the car field of @var{pair}. The value returned | |
121 | by @code{set-car!} is unspecified. | |
122 | @end deffn | |
123 | ||
124 | @rnindex set-cdr! | |
125 | @deffn {Scheme Procedure} set-cdr! pair value | |
126 | @deffnx {C Function} scm_set_cdr_x (pair, value) | |
127 | Stores @var{value} in the cdr field of @var{pair}. The value returned | |
128 | by @code{set-cdr!} is unspecified. | |
129 | @end deffn | |
130 | ||
131 | ||
132 | @node Lists | |
133 | @section Lists | |
134 | @tpindex Lists | |
135 | ||
136 | @c FIXME::martin: Review me! | |
137 | ||
138 | A very important data type in Scheme---as well as in all other Lisp | |
139 | dialects---is the data type @dfn{list}.@footnote{Strictly speaking, | |
140 | Scheme does not have a real datatype @dfn{list}. Lists are made up of | |
141 | @dfn{chained pairs}, and only exist by definition---a list is a chain | |
142 | of pairs which looks like a list.} | |
143 | ||
144 | This is the short definition of what a list is: | |
145 | ||
146 | @itemize @bullet | |
147 | @item | |
148 | Either the empty list @code{()}, | |
149 | ||
150 | @item | |
151 | or a pair which has a list in its cdr. | |
152 | @end itemize | |
153 | ||
154 | @c FIXME::martin: Describe the pair chaining in more detail. | |
155 | ||
156 | @c FIXME::martin: What is a proper, what an improper list? | |
157 | @c What is a circular list? | |
158 | ||
159 | @c FIXME::martin: Maybe steal some graphics from the Elisp reference | |
160 | @c manual? | |
161 | ||
162 | @menu | |
163 | * List Syntax:: Writing literal lists. | |
164 | * List Predicates:: Testing lists. | |
165 | * List Constructors:: Creating new lists. | |
166 | * List Selection:: Selecting from lists, getting their length. | |
167 | * Append/Reverse:: Appending and reversing lists. | |
168 | * List Modification:: Modifying existing lists. | |
169 | * List Searching:: Searching for list elements | |
170 | * List Mapping:: Applying procedures to lists. | |
171 | @end menu | |
172 | ||
173 | @node List Syntax | |
174 | @subsection List Read Syntax | |
175 | ||
176 | @c FIXME::martin: Review me! | |
177 | ||
178 | The syntax for lists is an opening parentheses, then all the elements of | |
179 | the list (separated by whitespace) and finally a closing | |
180 | parentheses.@footnote{Note that there is no separation character between | |
181 | the list elements, like a comma or a semicolon.}. | |
182 | ||
183 | @lisp | |
184 | (1 2 3) ; @r{a list of the numbers 1, 2 and 3} | |
185 | ("foo" bar 3.1415) ; @r{a string, a symbol and a real number} | |
186 | () ; @r{the empty list} | |
187 | @end lisp | |
188 | ||
189 | The last example needs a bit more explanation. A list with no elements, | |
190 | called the @dfn{empty list}, is special in some ways. It is used for | |
191 | terminating lists by storing it into the cdr of the last pair that makes | |
192 | up a list. An example will clear that up: | |
193 | ||
194 | @lisp | |
195 | (car '(1)) | |
196 | @result{} | |
197 | 1 | |
198 | (cdr '(1)) | |
199 | @result{} | |
200 | () | |
201 | @end lisp | |
202 | ||
203 | This example also shows that lists have to be quoted (REFFIXME) when | |
204 | written, because they would otherwise be mistakingly taken as procedure | |
205 | applications (@pxref{Simple Invocation}). | |
206 | ||
207 | ||
208 | @node List Predicates | |
209 | @subsection List Predicates | |
210 | ||
211 | @c FIXME::martin: Review me! | |
212 | ||
213 | Often it is useful to test whether a given Scheme object is a list or | |
214 | not. List-processing procedures could use this information to test | |
215 | whether their input is valid, or they could do different things | |
216 | depending on the datatype of their arguments. | |
217 | ||
218 | @rnindex list? | |
219 | @deffn {Scheme Procedure} list? x | |
220 | @deffnx {C Function} scm_list_p (x) | |
221 | Return @code{#t} iff @var{x} is a proper list, else @code{#f}. | |
222 | @end deffn | |
223 | ||
224 | The predicate @code{null?} is often used in list-processing code to | |
225 | tell whether a given list has run out of elements. That is, a loop | |
226 | somehow deals with the elements of a list until the list satisfies | |
227 | @code{null?}. Then, the algorithm terminates. | |
228 | ||
229 | @rnindex null? | |
230 | @deffn {Scheme Procedure} null? x | |
231 | @deffnx {C Function} scm_null_p (x) | |
232 | Return @code{#t} iff @var{x} is the empty list, else @code{#f}. | |
233 | @end deffn | |
234 | ||
235 | @node List Constructors | |
236 | @subsection List Constructors | |
237 | ||
238 | This section describes the procedures for constructing new lists. | |
239 | @code{list} simply returns a list where the elements are the arguments, | |
240 | @code{cons*} is similar, but the last argument is stored in the cdr of | |
241 | the last pair of the list. | |
242 | ||
243 | @rnindex list | |
244 | @deffn {Scheme Procedure} list . objs | |
245 | @deffnx {C Function} scm_list (objs) | |
246 | Return a list containing @var{objs}, the arguments to | |
247 | @code{list}. | |
248 | @end deffn | |
249 | ||
250 | @deffn {Scheme Procedure} cons* arg1 arg2 @dots{} | |
251 | @deffnx {C Function} scm_cons_star (arg1, rest) | |
252 | Like @code{list}, but the last arg provides the tail of the | |
253 | constructed list, returning @code{(cons @var{arg1} (cons | |
254 | @var{arg2} (cons @dots{} @var{argn})))}. Requires at least one | |
255 | argument. If given one argument, that argument is returned as | |
256 | result. This function is called @code{list*} in some other | |
257 | Schemes and in Common LISP. | |
258 | @end deffn | |
259 | ||
260 | @deffn {Scheme Procedure} list-copy lst | |
261 | @deffnx {C Function} scm_list_copy (lst) | |
262 | Return a (newly-created) copy of @var{lst}. | |
263 | @end deffn | |
264 | ||
265 | @deffn {Scheme Procedure} make-list n [init] | |
266 | Create a list containing of @var{n} elements, where each element is | |
267 | initialized to @var{init}. @var{init} defaults to the empty list | |
268 | @code{()} if not given. | |
269 | @end deffn | |
270 | ||
271 | Note that @code{list-copy} only makes a copy of the pairs which make up | |
272 | the spine of the lists. The list elements are not copied, which means | |
85a9b4ed | 273 | that modifying the elements of the new list also modifies the elements |
4c731ece NJ |
274 | of the old list. On the other hand, applying procedures like |
275 | @code{set-cdr!} or @code{delv!} to the new list will not alter the old | |
276 | list. If you also need to copy the list elements (making a deep copy), | |
277 | use the procedure @code{copy-tree} (@pxref{Copying}). | |
278 | ||
279 | @node List Selection | |
280 | @subsection List Selection | |
281 | ||
282 | @c FIXME::martin: Review me! | |
283 | ||
284 | These procedures are used to get some information about a list, or to | |
285 | retrieve one or more elements of a list. | |
286 | ||
287 | @rnindex length | |
288 | @deffn {Scheme Procedure} length lst | |
289 | @deffnx {C Function} scm_length (lst) | |
290 | Return the number of elements in list @var{lst}. | |
291 | @end deffn | |
292 | ||
293 | @deffn {Scheme Procedure} last-pair lst | |
294 | @deffnx {C Function} scm_last_pair (lst) | |
295 | Return a pointer to the last pair in @var{lst}, signalling an error if | |
296 | @var{lst} is circular. | |
297 | @end deffn | |
298 | ||
299 | @rnindex list-ref | |
300 | @deffn {Scheme Procedure} list-ref list k | |
301 | @deffnx {C Function} scm_list_ref (list, k) | |
302 | Return the @var{k}th element from @var{list}. | |
303 | @end deffn | |
304 | ||
305 | @rnindex list-tail | |
306 | @deffn {Scheme Procedure} list-tail lst k | |
307 | @deffnx {Scheme Procedure} list-cdr-ref lst k | |
308 | @deffnx {C Function} scm_list_tail (lst, k) | |
309 | Return the "tail" of @var{lst} beginning with its @var{k}th element. | |
310 | The first element of the list is considered to be element 0. | |
311 | ||
312 | @code{list-tail} and @code{list-cdr-ref} are identical. It may help to | |
313 | think of @code{list-cdr-ref} as accessing the @var{k}th cdr of the list, | |
314 | or returning the results of cdring @var{k} times down @var{lst}. | |
315 | @end deffn | |
316 | ||
317 | @deffn {Scheme Procedure} list-head lst k | |
318 | @deffnx {C Function} scm_list_head (lst, k) | |
319 | Copy the first @var{k} elements from @var{lst} into a new list, and | |
320 | return it. | |
321 | @end deffn | |
322 | ||
323 | @node Append/Reverse | |
324 | @subsection Append and Reverse | |
325 | ||
326 | @c FIXME::martin: Review me! | |
327 | ||
328 | @code{append} and @code{append!} are used to concatenate two or more | |
329 | lists in order to form a new list. @code{reverse} and @code{reverse!} | |
330 | return lists with the same elements as their arguments, but in reverse | |
331 | order. The procedure variants with an @code{!} directly modify the | |
332 | pairs which form the list, whereas the other procedures create new | |
333 | pairs. This is why you should be careful when using the side-effecting | |
334 | variants. | |
335 | ||
336 | @rnindex append | |
337 | @deffn {Scheme Procedure} append . args | |
338 | @deffnx {C Function} scm_append (args) | |
339 | Return a list consisting of the elements the lists passed as | |
340 | arguments. | |
341 | @lisp | |
342 | (append '(x) '(y)) @result{} (x y) | |
343 | (append '(a) '(b c d)) @result{} (a b c d) | |
344 | (append '(a (b)) '((c))) @result{} (a (b) (c)) | |
345 | @end lisp | |
346 | The resulting list is always newly allocated, except that it | |
347 | shares structure with the last list argument. The last | |
348 | argument may actually be any object; an improper list results | |
349 | if the last argument is not a proper list. | |
350 | @lisp | |
351 | (append '(a b) '(c . d)) @result{} (a b c . d) | |
352 | (append '() 'a) @result{} a | |
353 | @end lisp | |
354 | @end deffn | |
355 | ||
356 | @deffn {Scheme Procedure} append! . lists | |
357 | @deffnx {C Function} scm_append_x (lists) | |
358 | A destructive version of @code{append} (@pxref{Pairs and | |
359 | Lists,,,r5rs, The Revised^5 Report on Scheme}). The cdr field | |
360 | of each list's final pair is changed to point to the head of | |
361 | the next list, so no consing is performed. Return a pointer to | |
362 | the mutated list. | |
363 | @end deffn | |
364 | ||
365 | @rnindex reverse | |
366 | @deffn {Scheme Procedure} reverse lst | |
367 | @deffnx {C Function} scm_reverse (lst) | |
368 | Return a new list that contains the elements of @var{lst} but | |
369 | in reverse order. | |
370 | @end deffn | |
371 | ||
372 | @c NJFIXME explain new_tail | |
373 | @deffn {Scheme Procedure} reverse! lst [new_tail] | |
374 | @deffnx {C Function} scm_reverse_x (lst, new_tail) | |
375 | A destructive version of @code{reverse} (@pxref{Pairs and Lists,,,r5rs, | |
376 | The Revised^5 Report on Scheme}). The cdr of each cell in @var{lst} is | |
377 | modified to point to the previous list element. Return a pointer to the | |
378 | head of the reversed list. | |
379 | ||
380 | Caveat: because the list is modified in place, the tail of the original | |
381 | list now becomes its head, and the head of the original list now becomes | |
382 | the tail. Therefore, the @var{lst} symbol to which the head of the | |
383 | original list was bound now points to the tail. To ensure that the head | |
384 | of the modified list is not lost, it is wise to save the return value of | |
385 | @code{reverse!} | |
386 | @end deffn | |
387 | ||
388 | @node List Modification | |
389 | @subsection List Modification | |
390 | ||
391 | The following procedures modify an existing list, either by changing | |
392 | elements of the list, or by changing the list structure itself. | |
393 | ||
394 | @deffn {Scheme Procedure} list-set! list k val | |
395 | @deffnx {C Function} scm_list_set_x (list, k, val) | |
396 | Set the @var{k}th element of @var{list} to @var{val}. | |
397 | @end deffn | |
398 | ||
399 | @deffn {Scheme Procedure} list-cdr-set! list k val | |
400 | @deffnx {C Function} scm_list_cdr_set_x (list, k, val) | |
401 | Set the @var{k}th cdr of @var{list} to @var{val}. | |
402 | @end deffn | |
403 | ||
404 | @deffn {Scheme Procedure} delq item lst | |
405 | @deffnx {C Function} scm_delq (item, lst) | |
406 | Return a newly-created copy of @var{lst} with elements | |
407 | @code{eq?} to @var{item} removed. This procedure mirrors | |
408 | @code{memq}: @code{delq} compares elements of @var{lst} against | |
409 | @var{item} with @code{eq?}. | |
410 | @end deffn | |
411 | ||
412 | @deffn {Scheme Procedure} delv item lst | |
413 | @deffnx {C Function} scm_delv (item, lst) | |
414 | Return a newly-created copy of @var{lst} with elements | |
415 | @code{eqv?} to @var{item} removed. This procedure mirrors | |
416 | @code{memv}: @code{delv} compares elements of @var{lst} against | |
417 | @var{item} with @code{eqv?}. | |
418 | @end deffn | |
419 | ||
420 | @deffn {Scheme Procedure} delete item lst | |
421 | @deffnx {C Function} scm_delete (item, lst) | |
422 | Return a newly-created copy of @var{lst} with elements | |
423 | @code{equal?} to @var{item} removed. This procedure mirrors | |
424 | @code{member}: @code{delete} compares elements of @var{lst} | |
425 | against @var{item} with @code{equal?}. | |
426 | @end deffn | |
427 | ||
428 | @deffn {Scheme Procedure} delq! item lst | |
429 | @deffnx {Scheme Procedure} delv! item lst | |
430 | @deffnx {Scheme Procedure} delete! item lst | |
431 | @deffnx {C Function} scm_delq_x (item, lst) | |
432 | @deffnx {C Function} scm_delv_x (item, lst) | |
433 | @deffnx {C Function} scm_delete_x (item, lst) | |
434 | These procedures are destructive versions of @code{delq}, @code{delv} | |
435 | and @code{delete}: they modify the pointers in the existing @var{lst} | |
436 | rather than creating a new list. Caveat evaluator: Like other | |
437 | destructive list functions, these functions cannot modify the binding of | |
438 | @var{lst}, and so cannot be used to delete the first element of | |
439 | @var{lst} destructively. | |
440 | @end deffn | |
441 | ||
442 | @deffn {Scheme Procedure} delq1! item lst | |
443 | @deffnx {C Function} scm_delq1_x (item, lst) | |
444 | Like @code{delq!}, but only deletes the first occurrence of | |
445 | @var{item} from @var{lst}. Tests for equality using | |
446 | @code{eq?}. See also @code{delv1!} and @code{delete1!}. | |
447 | @end deffn | |
448 | ||
449 | @deffn {Scheme Procedure} delv1! item lst | |
450 | @deffnx {C Function} scm_delv1_x (item, lst) | |
451 | Like @code{delv!}, but only deletes the first occurrence of | |
452 | @var{item} from @var{lst}. Tests for equality using | |
453 | @code{eqv?}. See also @code{delq1!} and @code{delete1!}. | |
454 | @end deffn | |
455 | ||
456 | @deffn {Scheme Procedure} delete1! item lst | |
457 | @deffnx {C Function} scm_delete1_x (item, lst) | |
458 | Like @code{delete!}, but only deletes the first occurrence of | |
459 | @var{item} from @var{lst}. Tests for equality using | |
460 | @code{equal?}. See also @code{delq1!} and @code{delv1!}. | |
461 | @end deffn | |
462 | ||
463 | @node List Searching | |
464 | @subsection List Searching | |
465 | ||
466 | @c FIXME::martin: Review me! | |
467 | ||
468 | The following procedures search lists for particular elements. They use | |
469 | different comparison predicates for comparing list elements with the | |
470 | object to be searched. When they fail, they return @code{#f}, otherwise | |
471 | they return the sublist whose car is equal to the search object, where | |
472 | equality depends on the equality predicate used. | |
473 | ||
474 | @rnindex memq | |
475 | @deffn {Scheme Procedure} memq x lst | |
476 | @deffnx {C Function} scm_memq (x, lst) | |
477 | Return the first sublist of @var{lst} whose car is @code{eq?} | |
478 | to @var{x} where the sublists of @var{lst} are the non-empty | |
479 | lists returned by @code{(list-tail @var{lst} @var{k})} for | |
480 | @var{k} less than the length of @var{lst}. If @var{x} does not | |
481 | occur in @var{lst}, then @code{#f} (not the empty list) is | |
482 | returned. | |
483 | @end deffn | |
484 | ||
485 | @rnindex memv | |
486 | @deffn {Scheme Procedure} memv x lst | |
487 | @deffnx {C Function} scm_memv (x, lst) | |
488 | Return the first sublist of @var{lst} whose car is @code{eqv?} | |
489 | to @var{x} where the sublists of @var{lst} are the non-empty | |
490 | lists returned by @code{(list-tail @var{lst} @var{k})} for | |
491 | @var{k} less than the length of @var{lst}. If @var{x} does not | |
492 | occur in @var{lst}, then @code{#f} (not the empty list) is | |
493 | returned. | |
494 | @end deffn | |
495 | ||
496 | @rnindex member | |
497 | @deffn {Scheme Procedure} member x lst | |
498 | @deffnx {C Function} scm_member (x, lst) | |
499 | Return the first sublist of @var{lst} whose car is | |
500 | @code{equal?} to @var{x} where the sublists of @var{lst} are | |
501 | the non-empty lists returned by @code{(list-tail @var{lst} | |
502 | @var{k})} for @var{k} less than the length of @var{lst}. If | |
503 | @var{x} does not occur in @var{lst}, then @code{#f} (not the | |
504 | empty list) is returned. | |
505 | @end deffn | |
506 | ||
507 | [FIXME: Is there any reason to have the `sloppy' functions available at | |
508 | high level at all? Maybe these docs should be relegated to a "Guile | |
509 | Internals" node or something. -twp] | |
510 | ||
511 | @deffn {Scheme Procedure} sloppy-memq x lst | |
512 | This procedure behaves like @code{memq}, but does no type or error checking. | |
513 | Its use is recommended only in writing Guile internals, | |
514 | not for high-level Scheme programs. | |
515 | @end deffn | |
516 | ||
517 | @deffn {Scheme Procedure} sloppy-memv x lst | |
518 | This procedure behaves like @code{memv}, but does no type or error checking. | |
519 | Its use is recommended only in writing Guile internals, | |
520 | not for high-level Scheme programs. | |
521 | @end deffn | |
522 | ||
523 | @deffn {Scheme Procedure} sloppy-member x lst | |
524 | This procedure behaves like @code{member}, but does no type or error checking. | |
525 | Its use is recommended only in writing Guile internals, | |
526 | not for high-level Scheme programs. | |
527 | @end deffn | |
528 | ||
529 | @node List Mapping | |
530 | @subsection List Mapping | |
531 | ||
532 | @c FIXME::martin: Review me! | |
533 | ||
534 | List processing is very convenient in Scheme because the process of | |
535 | iterating over the elements of a list can be highly abstracted. The | |
536 | procedures in this section are the most basic iterating procedures for | |
537 | lists. They take a procedure and one or more lists as arguments, and | |
538 | apply the procedure to each element of the list. They differ in their | |
539 | return value. | |
540 | ||
541 | @rnindex map | |
542 | @c begin (texi-doc-string "guile" "map") | |
543 | @deffn {Scheme Procedure} map proc arg1 arg2 @dots{} | |
544 | @deffnx {Scheme Procedure} map-in-order proc arg1 arg2 @dots{} | |
545 | @deffnx {C Function} scm_map (proc, arg1, args) | |
546 | Apply @var{proc} to each element of the list @var{arg1} (if only two | |
547 | arguments are given), or to the corresponding elements of the argument | |
548 | lists (if more than two arguments are given). The result(s) of the | |
549 | procedure applications are saved and returned in a list. For | |
550 | @code{map}, the order of procedure applications is not specified, | |
551 | @code{map-in-order} applies the procedure from left to right to the list | |
552 | elements. | |
553 | @end deffn | |
554 | ||
555 | @rnindex for-each | |
556 | @c begin (texi-doc-string "guile" "for-each") | |
557 | @deffn {Scheme Procedure} for-each proc arg1 arg2 @dots{} | |
558 | Like @code{map}, but the procedure is always applied from left to right, | |
559 | and the result(s) of the procedure applications are thrown away. The | |
560 | return value is not specified. | |
561 | @end deffn | |
562 | ||
563 | ||
564 | @node Vectors | |
565 | @section Vectors | |
566 | @tpindex Vectors | |
567 | ||
568 | @c FIXME::martin: Review me! | |
569 | ||
570 | @c FIXME::martin: Should the subsections of this section be nodes | |
571 | @c of their own, or are the resulting nodes too short, then? | |
572 | ||
573 | Vectors are sequences of Scheme objects. Unlike lists, the length of a | |
574 | vector, once the vector is created, cannot be changed. The advantage of | |
575 | vectors over lists is that the time required to access one element of a vector | |
576 | given its @dfn{position} (synonymous with @dfn{index}), a zero-origin number, | |
577 | is constant, whereas lists have an access time linear to the position of the | |
578 | accessed element in the list. | |
579 | ||
580 | Vectors can contain any kind of Scheme object; it is even possible to have | |
581 | different types of objects in the same vector. For vectors containing | |
582 | vectors, you may wish to use arrays, instead. Note, too, that some array | |
583 | procedures operate happily on vectors (@pxref{Arrays}). | |
584 | ||
585 | @subsection Vector Read Syntax | |
586 | ||
587 | Vectors can literally be entered in source code, just like strings, | |
588 | characters or some of the other data types. The read syntax for vectors | |
589 | is as follows: A sharp sign (@code{#}), followed by an opening | |
590 | parentheses, all elements of the vector in their respective read syntax, | |
591 | and finally a closing parentheses. The following are examples of the | |
592 | read syntax for vectors; where the first vector only contains numbers | |
593 | and the second three different object types: a string, a symbol and a | |
594 | number in hexadecimal notation. | |
595 | ||
596 | @lisp | |
597 | #(1 2 3) | |
598 | #("Hello" foo #xdeadbeef) | |
599 | @end lisp | |
600 | ||
601 | @subsection Vector Predicates | |
602 | ||
603 | @rnindex vector? | |
604 | @deffn {Scheme Procedure} vector? obj | |
605 | @deffnx {C Function} scm_vector_p (obj) | |
606 | Return @code{#t} if @var{obj} is a vector, otherwise return | |
607 | @code{#f}. | |
608 | @end deffn | |
609 | ||
610 | @subsection Vector Constructors | |
611 | ||
612 | @rnindex make-vector | |
613 | @deffn {Scheme Procedure} make-vector k [fill] | |
614 | @deffnx {C Function} scm_make_vector (k, fill) | |
615 | Return a newly allocated vector of @var{k} elements. If a | |
616 | second argument is given, then each position is initialized to | |
617 | @var{fill}. Otherwise the initial contents of each position is | |
618 | unspecified. | |
619 | @end deffn | |
620 | ||
621 | @rnindex vector | |
622 | @rnindex list->vector | |
623 | @deffn {Scheme Procedure} vector . l | |
624 | @deffnx {Scheme Procedure} list->vector l | |
625 | @deffnx {C Function} scm_vector (l) | |
626 | Return a newly allocated vector composed of the | |
627 | given arguments. Analogous to @code{list}. | |
628 | ||
629 | @lisp | |
630 | (vector 'a 'b 'c) @result{} #(a b c) | |
631 | @end lisp | |
632 | @end deffn | |
633 | ||
634 | @rnindex vector->list | |
635 | @deffn {Scheme Procedure} vector->list v | |
636 | @deffnx {C Function} scm_vector_to_list (v) | |
637 | Return a newly allocated list composed of the elements of @var{v}. | |
638 | ||
639 | @lisp | |
640 | (vector->list '#(dah dah didah)) @result{} (dah dah didah) | |
641 | (list->vector '(dididit dah)) @result{} #(dididit dah) | |
642 | @end lisp | |
643 | @end deffn | |
644 | ||
645 | @subsection Vector Modification | |
646 | ||
647 | A vector created by any of the vector constructor procedures | |
648 | (@pxref{Vectors}) documented above can be modified using the | |
649 | following procedures. | |
650 | ||
651 | @emph{NOTE:} According to R5RS, using any of these procedures on | |
652 | literally entered vectors is an error, because these vectors are | |
653 | considered to be constant, although Guile currently does not detect this | |
654 | error. | |
655 | ||
656 | @rnindex vector-set! | |
657 | @deffn {Scheme Procedure} vector-set! vector k obj | |
658 | Store @var{obj} in position @var{k} of @var{vector}. | |
659 | @var{k} must be a valid index of @var{vector}. | |
660 | The value returned by @samp{vector-set!} is unspecified. | |
661 | @lisp | |
662 | (let ((vec (vector 0 '(2 2 2 2) "Anna"))) | |
663 | (vector-set! vec 1 '("Sue" "Sue")) | |
664 | vec) @result{} #(0 ("Sue" "Sue") "Anna") | |
665 | @end lisp | |
666 | @end deffn | |
667 | ||
668 | @rnindex vector-fill! | |
669 | @deffn {Scheme Procedure} vector-fill! v fill | |
670 | @deffnx {C Function} scm_vector_fill_x (v, fill) | |
671 | Store @var{fill} in every position of @var{vector}. The value | |
672 | returned by @code{vector-fill!} is unspecified. | |
673 | @end deffn | |
674 | ||
675 | @deffn {Scheme Procedure} vector-move-left! vec1 start1 end1 vec2 start2 | |
676 | @deffnx {C Function} scm_vector_move_left_x (vec1, start1, end1, vec2, start2) | |
677 | Copy elements from @var{vec1}, positions @var{start1} to @var{end1}, | |
678 | to @var{vec2} starting at position @var{start2}. @var{start1} and | |
679 | @var{start2} are inclusive indices; @var{end1} is exclusive. | |
680 | ||
681 | @code{vector-move-left!} copies elements in leftmost order. | |
682 | Therefore, in the case where @var{vec1} and @var{vec2} refer to the | |
683 | same vector, @code{vector-move-left!} is usually appropriate when | |
684 | @var{start1} is greater than @var{start2}. | |
685 | @end deffn | |
686 | ||
687 | @deffn {Scheme Procedure} vector-move-right! vec1 start1 end1 vec2 start2 | |
688 | @deffnx {C Function} scm_vector_move_right_x (vec1, start1, end1, vec2, start2) | |
689 | Copy elements from @var{vec1}, positions @var{start1} to @var{end1}, | |
690 | to @var{vec2} starting at position @var{start2}. @var{start1} and | |
691 | @var{start2} are inclusive indices; @var{end1} is exclusive. | |
692 | ||
693 | @code{vector-move-right!} copies elements in rightmost order. | |
694 | Therefore, in the case where @var{vec1} and @var{vec2} refer to the | |
695 | same vector, @code{vector-move-right!} is usually appropriate when | |
696 | @var{start1} is less than @var{start2}. | |
697 | @end deffn | |
698 | ||
699 | @subsection Vector Selection | |
700 | ||
701 | These procedures return information about a given vector, such as the | |
702 | size or what elements are contained in the vector. | |
703 | ||
704 | @rnindex vector-length | |
705 | @deffn {Scheme Procedure} vector-length vector | |
706 | Return the number of elements in @var{vector} as an exact integer. | |
707 | @end deffn | |
708 | ||
709 | @rnindex vector-ref | |
710 | @deffn {Scheme Procedure} vector-ref vector k | |
711 | Return the contents of position @var{k} of @var{vector}. | |
712 | @var{k} must be a valid index of @var{vector}. | |
713 | @lisp | |
714 | (vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8 | |
715 | (vector-ref '#(1 1 2 3 5 8 13 21) | |
716 | (let ((i (round (* 2 (acos -1))))) | |
717 | (if (inexact? i) | |
718 | (inexact->exact i) | |
719 | i))) @result{} 13 | |
720 | @end lisp | |
721 | @end deffn | |
722 | ||
723 | ||
724 | @node Records | |
725 | @section Records | |
726 | ||
727 | A @dfn{record type} is a first class object representing a user-defined | |
728 | data type. A @dfn{record} is an instance of a record type. | |
729 | ||
730 | @deffn {Scheme Procedure} record? obj | |
731 | Return @code{#t} if @var{obj} is a record of any type and @code{#f} | |
732 | otherwise. | |
733 | ||
734 | Note that @code{record?} may be true of any Scheme value; there is no | |
735 | promise that records are disjoint with other Scheme types. | |
736 | @end deffn | |
737 | ||
738 | @deffn {Scheme Procedure} make-record-type type-name field-names | |
739 | Return a @dfn{record-type descriptor}, a value representing a new data | |
740 | type disjoint from all others. The @var{type-name} argument must be a | |
741 | string, but is only used for debugging purposes (such as the printed | |
742 | representation of a record of the new type). The @var{field-names} | |
743 | argument is a list of symbols naming the @dfn{fields} of a record of the | |
744 | new type. It is an error if the list contains any duplicates. It is | |
745 | unspecified how record-type descriptors are represented. | |
746 | @end deffn | |
747 | ||
748 | @deffn {Scheme Procedure} record-constructor rtd [field-names] | |
749 | Return a procedure for constructing new members of the type represented | |
750 | by @var{rtd}. The returned procedure accepts exactly as many arguments | |
751 | as there are symbols in the given list, @var{field-names}; these are | |
752 | used, in order, as the initial values of those fields in a new record, | |
753 | which is returned by the constructor procedure. The values of any | |
754 | fields not named in that list are unspecified. The @var{field-names} | |
755 | argument defaults to the list of field names in the call to | |
756 | @code{make-record-type} that created the type represented by @var{rtd}; | |
757 | if the @var{field-names} argument is provided, it is an error if it | |
758 | contains any duplicates or any symbols not in the default list. | |
759 | @end deffn | |
760 | ||
761 | @deffn {Scheme Procedure} record-predicate rtd | |
762 | Return a procedure for testing membership in the type represented by | |
763 | @var{rtd}. The returned procedure accepts exactly one argument and | |
764 | returns a true value if the argument is a member of the indicated record | |
765 | type; it returns a false value otherwise. | |
766 | @end deffn | |
767 | ||
768 | @deffn {Scheme Procedure} record-accessor rtd field-name | |
769 | Return a procedure for reading the value of a particular field of a | |
770 | member of the type represented by @var{rtd}. The returned procedure | |
771 | accepts exactly one argument which must be a record of the appropriate | |
772 | type; it returns the current value of the field named by the symbol | |
773 | @var{field-name} in that record. The symbol @var{field-name} must be a | |
774 | member of the list of field-names in the call to @code{make-record-type} | |
775 | that created the type represented by @var{rtd}. | |
776 | @end deffn | |
777 | ||
778 | @deffn {Scheme Procedure} record-modifier rtd field-name | |
779 | Return a procedure for writing the value of a particular field of a | |
780 | member of the type represented by @var{rtd}. The returned procedure | |
781 | accepts exactly two arguments: first, a record of the appropriate type, | |
782 | and second, an arbitrary Scheme value; it modifies the field named by | |
783 | the symbol @var{field-name} in that record to contain the given value. | |
784 | The returned value of the modifier procedure is unspecified. The symbol | |
785 | @var{field-name} must be a member of the list of field-names in the call | |
786 | to @code{make-record-type} that created the type represented by | |
787 | @var{rtd}. | |
788 | @end deffn | |
789 | ||
790 | @deffn {Scheme Procedure} record-type-descriptor record | |
791 | Return a record-type descriptor representing the type of the given | |
792 | record. That is, for example, if the returned descriptor were passed to | |
793 | @code{record-predicate}, the resulting predicate would return a true | |
794 | value when passed the given record. Note that it is not necessarily the | |
795 | case that the returned descriptor is the one that was passed to | |
796 | @code{record-constructor} in the call that created the constructor | |
797 | procedure that created the given record. | |
798 | @end deffn | |
799 | ||
800 | @deffn {Scheme Procedure} record-type-name rtd | |
801 | Return the type-name associated with the type represented by rtd. The | |
802 | returned value is @code{eqv?} to the @var{type-name} argument given in | |
803 | the call to @code{make-record-type} that created the type represented by | |
804 | @var{rtd}. | |
805 | @end deffn | |
806 | ||
807 | @deffn {Scheme Procedure} record-type-fields rtd | |
808 | Return a list of the symbols naming the fields in members of the type | |
809 | represented by @var{rtd}. The returned value is @code{equal?} to the | |
810 | field-names argument given in the call to @code{make-record-type} that | |
811 | created the type represented by @var{rtd}. | |
812 | @end deffn | |
813 | ||
814 | ||
815 | @node Structures | |
816 | @section Structures | |
817 | @tpindex Structures | |
818 | ||
819 | [FIXME: this is pasted in from Tom Lord's original guile.texi and should | |
820 | be reviewed] | |
821 | ||
822 | A @dfn{structure type} is a first class user-defined data type. A | |
823 | @dfn{structure} is an instance of a structure type. A structure type is | |
824 | itself a structure. | |
825 | ||
826 | Structures are less abstract and more general than traditional records. | |
827 | In fact, in Guile Scheme, records are implemented using structures. | |
828 | ||
829 | @menu | |
830 | * Structure Concepts:: The structure of Structures | |
831 | * Structure Layout:: Defining the layout of structure types | |
832 | * Structure Basics:: make-, -ref and -set! procedures for structs | |
833 | * Vtables:: Accessing type-specific data | |
834 | @end menu | |
835 | ||
836 | @node Structure Concepts | |
837 | @subsection Structure Concepts | |
838 | ||
839 | A structure object consists of a handle, structure data, and a vtable. | |
840 | The handle is a Scheme value which points to both the vtable and the | |
841 | structure's data. Structure data is a dynamically allocated region of | |
842 | memory, private to the structure, divided up into typed fields. A | |
843 | vtable is another structure used to hold type-specific data. Multiple | |
844 | structures can share a common vtable. | |
845 | ||
846 | Three concepts are key to understanding structures. | |
847 | ||
848 | @itemize @bullet{} | |
849 | @item @dfn{layout specifications} | |
850 | ||
851 | Layout specifications determine how memory allocated to structures is | |
852 | divided up into fields. Programmers must write a layout specification | |
853 | whenever a new type of structure is defined. | |
854 | ||
855 | @item @dfn{structural accessors} | |
856 | ||
857 | Structure access is by field number. There is only one set of | |
858 | accessors common to all structure objects. | |
859 | ||
860 | @item @dfn{vtables} | |
861 | ||
862 | Vtables, themselves structures, are first class representations of | |
863 | disjoint sub-types of structures in general. In most cases, when a | |
85a9b4ed | 864 | new structure is created, programmers must specify a vtable for the |
4c731ece NJ |
865 | new structure. Each vtable has a field describing the layout of its |
866 | instances. Vtables can have additional, user-defined fields as well. | |
867 | @end itemize | |
868 | ||
869 | ||
870 | ||
871 | @node Structure Layout | |
872 | @subsection Structure Layout | |
873 | ||
874 | When a structure is created, a region of memory is allocated to hold its | |
875 | state. The @dfn{layout} of the structure's type determines how that | |
876 | memory is divided into fields. | |
877 | ||
878 | Each field has a specified type. There are only three types allowed, each | |
879 | corresponding to a one letter code. The allowed types are: | |
880 | ||
881 | @itemize @bullet{} | |
882 | @item 'u' -- unprotected | |
883 | ||
884 | The field holds binary data that is not GC protected. | |
885 | ||
886 | @item 'p' -- protected | |
887 | ||
888 | The field holds a Scheme value and is GC protected. | |
889 | ||
890 | @item 's' -- self | |
891 | ||
892 | The field holds a Scheme value and is GC protected. When a structure is | |
893 | created with this type of field, the field is initialized to refer to | |
894 | the structure's own handle. This kind of field is mainly useful when | |
895 | mixing Scheme and C code in which the C code may need to compute a | |
85a9b4ed | 896 | structure's handle given only the address of its malloc-ed data. |
4c731ece NJ |
897 | @end itemize |
898 | ||
899 | ||
900 | Each field also has an associated access protection. There are only | |
901 | three kinds of protection, each corresponding to a one letter code. | |
902 | The allowed protections are: | |
903 | ||
904 | @itemize @bullet{} | |
905 | @item 'w' -- writable | |
906 | ||
907 | The field can be read and written. | |
908 | ||
909 | @item 'r' -- readable | |
910 | ||
911 | The field can be read, but not written. | |
912 | ||
913 | @item 'o' -- opaque | |
914 | ||
915 | The field can be neither read nor written. This kind | |
916 | of protection is for fields useful only to built-in routines. | |
917 | @end itemize | |
918 | ||
919 | A layout specification is described by stringing together pairs | |
920 | of letters: one to specify a field type and one to specify a field | |
921 | protection. For example, a traditional cons pair type object could | |
922 | be described as: | |
923 | ||
924 | @example | |
925 | ; cons pairs have two writable fields of Scheme data | |
926 | "pwpw" | |
927 | @end example | |
928 | ||
929 | A pair object in which the first field is held constant could be: | |
930 | ||
931 | @example | |
932 | "prpw" | |
933 | @end example | |
934 | ||
935 | Binary fields, (fields of type "u"), hold one @dfn{word} each. The | |
936 | size of a word is a machine dependent value defined to be equal to the | |
937 | value of the C expression: @code{sizeof (long)}. | |
938 | ||
939 | The last field of a structure layout may specify a tail array. | |
940 | A tail array is indicated by capitalizing the field's protection | |
941 | code ('W', 'R' or 'O'). A tail-array field is replaced by | |
942 | a read-only binary data field containing an array size. The array | |
943 | size is determined at the time the structure is created. It is followed | |
944 | by a corresponding number of fields of the type specified for the | |
945 | tail array. For example, a conventional Scheme vector can be | |
946 | described as: | |
947 | ||
948 | @example | |
949 | ; A vector is an arbitrary number of writable fields holding Scheme | |
950 | ; values: | |
951 | "pW" | |
952 | @end example | |
953 | ||
954 | In the above example, field 0 contains the size of the vector and | |
955 | fields beginning at 1 contain the vector elements. | |
956 | ||
85a9b4ed | 957 | A kind of tagged vector (a constant tag followed by conventional |
4c731ece NJ |
958 | vector elements) might be: |
959 | ||
960 | @example | |
961 | "prpW" | |
962 | @end example | |
963 | ||
964 | ||
965 | Structure layouts are represented by specially interned symbols whose | |
966 | name is a string of type and protection codes. To create a new | |
967 | structure layout, use this procedure: | |
968 | ||
969 | @deffn {Scheme Procedure} make-struct-layout fields | |
970 | @deffnx {C Function} scm_make_struct_layout (fields) | |
971 | Return a new structure layout object. | |
972 | ||
973 | @var{fields} must be a string made up of pairs of characters | |
974 | strung together. The first character of each pair describes a field | |
975 | type, the second a field protection. Allowed types are 'p' for | |
976 | GC-protected Scheme data, 'u' for unprotected binary data, and 's' for | |
977 | a field that points to the structure itself. Allowed protections | |
978 | are 'w' for mutable fields, 'r' for read-only fields, and 'o' for opaque | |
979 | fields. The last field protection specification may be capitalized to | |
980 | indicate that the field is a tail-array. | |
981 | @end deffn | |
982 | ||
983 | ||
984 | ||
985 | @node Structure Basics | |
986 | @subsection Structure Basics | |
987 | ||
988 | This section describes the basic procedures for creating and accessing | |
989 | structures. | |
990 | ||
991 | @deffn {Scheme Procedure} make-struct vtable tail_array_size . init | |
992 | @deffnx {C Function} scm_make_struct (vtable, tail_array_size, init) | |
993 | Create a new structure. | |
994 | ||
995 | @var{type} must be a vtable structure (@pxref{Vtables}). | |
996 | ||
997 | @var{tail-elts} must be a non-negative integer. If the layout | |
998 | specification indicated by @var{type} includes a tail-array, | |
999 | this is the number of elements allocated to that array. | |
1000 | ||
1001 | The @var{init1}, @dots{} are optional arguments describing how | |
1002 | successive fields of the structure should be initialized. Only fields | |
1003 | with protection 'r' or 'w' can be initialized, except for fields of | |
1004 | type 's', which are automatically initialized to point to the new | |
1005 | structure itself; fields with protection 'o' can not be initialized by | |
1006 | Scheme programs. | |
1007 | ||
1008 | If fewer optional arguments than initializable fields are supplied, | |
1009 | fields of type 'p' get default value #f while fields of type 'u' are | |
1010 | initialized to 0. | |
1011 | ||
1012 | Structs are currently the basic representation for record-like data | |
1013 | structures in Guile. The plan is to eventually replace them with a | |
1014 | new representation which will at the same time be easier to use and | |
1015 | more powerful. | |
1016 | ||
1017 | For more information, see the documentation for @code{make-vtable-vtable}. | |
1018 | @end deffn | |
1019 | ||
1020 | @deffn {Scheme Procedure} struct? x | |
1021 | @deffnx {C Function} scm_struct_p (x) | |
1022 | Return @code{#t} iff @var{x} is a structure object, else | |
1023 | @code{#f}. | |
1024 | @end deffn | |
1025 | ||
1026 | ||
1027 | @deffn {Scheme Procedure} struct-ref handle pos | |
1028 | @deffnx {Scheme Procedure} struct-set! struct n value | |
1029 | @deffnx {C Function} scm_struct_ref (handle, pos) | |
1030 | @deffnx {C Function} scm_struct_set_x (struct, n, value) | |
1031 | Access (or modify) the @var{n}th field of @var{struct}. | |
1032 | ||
1033 | If the field is of type 'p', then it can be set to an arbitrary value. | |
1034 | ||
1035 | If the field is of type 'u', then it can only be set to a non-negative | |
1036 | integer value small enough to fit in one machine word. | |
1037 | @end deffn | |
1038 | ||
1039 | ||
1040 | ||
1041 | @node Vtables | |
1042 | @subsection Vtables | |
1043 | ||
1044 | Vtables are structures that are used to represent structure types. Each | |
1045 | vtable contains a layout specification in field | |
1046 | @code{vtable-index-layout} -- instances of the type are laid out | |
1047 | according to that specification. Vtables contain additional fields | |
1048 | which are used only internally to libguile. The variable | |
1049 | @code{vtable-offset-user} is bound to a field number. Vtable fields | |
1050 | at that position or greater are user definable. | |
1051 | ||
1052 | @deffn {Scheme Procedure} struct-vtable handle | |
1053 | @deffnx {C Function} scm_struct_vtable (handle) | |
1054 | Return the vtable structure that describes the type of @var{struct}. | |
1055 | @end deffn | |
1056 | ||
1057 | @deffn {Scheme Procedure} struct-vtable? x | |
1058 | @deffnx {C Function} scm_struct_vtable_p (x) | |
1059 | Return @code{#t} iff @var{x} is a vtable structure. | |
1060 | @end deffn | |
1061 | ||
1062 | If you have a vtable structure, @code{V}, you can create an instance of | |
1063 | the type it describes by using @code{(make-struct V ...)}. But where | |
1064 | does @code{V} itself come from? One possibility is that @code{V} is an | |
1065 | instance of a user-defined vtable type, @code{V'}, so that @code{V} is | |
1066 | created by using @code{(make-struct V' ...)}. Another possibility is | |
1067 | that @code{V} is an instance of the type it itself describes. Vtable | |
1068 | structures of the second sort are created by this procedure: | |
1069 | ||
1070 | @deffn {Scheme Procedure} make-vtable-vtable user_fields tail_array_size . init | |
1071 | @deffnx {C Function} scm_make_vtable_vtable (user_fields, tail_array_size, init) | |
1072 | Return a new, self-describing vtable structure. | |
1073 | ||
1074 | @var{user-fields} is a string describing user defined fields of the | |
1075 | vtable beginning at index @code{vtable-offset-user} | |
1076 | (see @code{make-struct-layout}). | |
1077 | ||
1078 | @var{tail-size} specifies the size of the tail-array (if any) of | |
1079 | this vtable. | |
1080 | ||
1081 | @var{init1}, @dots{} are the optional initializers for the fields of | |
1082 | the vtable. | |
1083 | ||
1084 | Vtables have one initializable system field---the struct printer. | |
1085 | This field comes before the user fields in the initializers passed | |
1086 | to @code{make-vtable-vtable} and @code{make-struct}, and thus works as | |
1087 | a third optional argument to @code{make-vtable-vtable} and a fourth to | |
1088 | @code{make-struct} when creating vtables: | |
1089 | ||
1090 | If the value is a procedure, it will be called instead of the standard | |
1091 | printer whenever a struct described by this vtable is printed. | |
1092 | The procedure will be called with arguments STRUCT and PORT. | |
1093 | ||
1094 | The structure of a struct is described by a vtable, so the vtable is | |
1095 | in essence the type of the struct. The vtable is itself a struct with | |
1096 | a vtable. This could go on forever if it weren't for the | |
1097 | vtable-vtables which are self-describing vtables, and thus terminate | |
1098 | the chain. | |
1099 | ||
1100 | There are several potential ways of using structs, but the standard | |
1101 | one is to use three kinds of structs, together building up a type | |
1102 | sub-system: one vtable-vtable working as the root and one or several | |
1103 | "types", each with a set of "instances". (The vtable-vtable should be | |
1104 | compared to the class <class> which is the class of itself.) | |
1105 | ||
1106 | @lisp | |
1107 | (define ball-root (make-vtable-vtable "pr" 0)) | |
1108 | ||
1109 | (define (make-ball-type ball-color) | |
1110 | (make-struct ball-root 0 | |
1111 | (make-struct-layout "pw") | |
1112 | (lambda (ball port) | |
1113 | (format port "#<a ~A ball owned by ~A>" | |
1114 | (color ball) | |
1115 | (owner ball))) | |
1116 | ball-color)) | |
1117 | (define (color ball) (struct-ref (struct-vtable ball) vtable-offset-user)) | |
1118 | (define (owner ball) (struct-ref ball 0)) | |
1119 | ||
1120 | (define red (make-ball-type 'red)) | |
1121 | (define green (make-ball-type 'green)) | |
1122 | ||
1123 | (define (make-ball type owner) (make-struct type 0 owner)) | |
1124 | ||
1125 | (define ball (make-ball green 'Nisse)) | |
1126 | ball @result{} #<a green ball owned by Nisse> | |
1127 | @end lisp | |
1128 | @end deffn | |
1129 | ||
1130 | @deffn {Scheme Procedure} struct-vtable-name vtable | |
1131 | @deffnx {C Function} scm_struct_vtable_name (vtable) | |
1132 | Return the name of the vtable @var{vtable}. | |
1133 | @end deffn | |
1134 | ||
1135 | @deffn {Scheme Procedure} set-struct-vtable-name! vtable name | |
1136 | @deffnx {C Function} scm_set_struct_vtable_name_x (vtable, name) | |
1137 | Set the name of the vtable @var{vtable} to @var{name}. | |
1138 | @end deffn | |
1139 | ||
1140 | @deffn {Scheme Procedure} struct-vtable-tag handle | |
1141 | @deffnx {C Function} scm_struct_vtable_tag (handle) | |
1142 | Return the vtable tag of the structure @var{handle}. | |
1143 | @end deffn | |
1144 | ||
1145 | ||
1146 | @node Arrays | |
1147 | @section Arrays | |
1148 | @tpindex Arrays | |
1149 | ||
1150 | @menu | |
1151 | * Conventional Arrays:: Arrays with arbitrary data. | |
1152 | * Array Mapping:: Applying a procedure to the contents of an array. | |
1153 | * Uniform Arrays:: Arrays with data of a single type. | |
1154 | * Bit Vectors:: Vectors of bits. | |
1155 | @end menu | |
1156 | ||
1157 | @node Conventional Arrays | |
1158 | @subsection Conventional Arrays | |
1159 | ||
1160 | @dfn{Conventional arrays} are a collection of cells organized into an | |
1161 | arbitrary number of dimensions. Each cell can hold any kind of Scheme | |
1162 | value and can be accessed in constant time by supplying an index for | |
1163 | each dimension. This contrasts with uniform arrays, which use memory | |
1164 | more efficiently but can hold data of only a single type, and lists | |
1165 | where inserting and deleting cells is more efficient, but more time | |
1166 | is usually required to access a particular cell. | |
1167 | ||
1168 | A conventional array is displayed as @code{#} followed by the @dfn{rank} | |
1169 | (number of dimensions) followed by the cells, organized into dimensions | |
1170 | using parentheses. The nesting depth of the parentheses is equal to | |
1171 | the rank. | |
1172 | ||
1173 | When an array is created, the number of dimensions and range of each | |
1174 | dimension must be specified, e.g., to create a 2x3 array with a | |
1175 | zero-based index: | |
1176 | ||
1177 | @example | |
1178 | (make-array 'ho 2 3) @result{} | |
1179 | #2((ho ho ho) (ho ho ho)) | |
1180 | @end example | |
1181 | ||
1182 | The range of each dimension can also be given explicitly, e.g., another | |
1183 | way to create the same array: | |
1184 | ||
1185 | @example | |
1186 | (make-array 'ho '(0 1) '(0 2)) @result{} | |
1187 | #2((ho ho ho) (ho ho ho)) | |
1188 | @end example | |
1189 | ||
1190 | A conventional array with one dimension based at zero is identical to | |
1191 | a vector: | |
1192 | ||
1193 | @example | |
1194 | (make-array 'ho 3) @result{} | |
1195 | #(ho ho ho) | |
1196 | @end example | |
1197 | ||
1198 | The following procedures can be used with conventional arrays (or vectors). | |
1199 | ||
1200 | @deffn {Scheme Procedure} array? v [prot] | |
1201 | @deffnx {C Function} scm_array_p (v, prot) | |
1202 | Return @code{#t} if the @var{obj} is an array, and @code{#f} if | |
1203 | not. The @var{prototype} argument is used with uniform arrays | |
1204 | and is described elsewhere. | |
1205 | @end deffn | |
1206 | ||
1207 | @deffn {Scheme Procedure} make-array initial-value bound1 bound2 @dots{} | |
1208 | Create and return an array that has as many dimensions as there are | |
1209 | @var{bound}s and fill it with @var{initial-value}. Each @var{bound} | |
1210 | may be a positive non-zero integer @var{N}, in which case the index for | |
1211 | that dimension can range from 0 through @var{N-1}; or an explicit index | |
1212 | range specifier in the form @code{(LOWER UPPER)}, where both @var{lower} | |
1213 | and @var{upper} are integers, possibly less than zero, and possibly the | |
1214 | same number (however, @var{lower} cannot be greater than @var{upper}). | |
1215 | @end deffn | |
1216 | ||
1217 | @c array-ref's type is `compiled-closure'. There's some weird stuff | |
1218 | @c going on in array.c, too. Let's call it a primitive. -twp | |
1219 | ||
1220 | @deffn {Scheme Procedure} uniform-vector-ref v args | |
1221 | @deffnx {Scheme Procedure} array-ref v . args | |
1222 | @deffnx {C Function} scm_uniform_vector_ref (v, args) | |
1223 | Return the element at the @code{(index1, index2)} element in | |
1224 | @var{array}. | |
1225 | @end deffn | |
1226 | ||
1227 | @deffn {Scheme Procedure} array-in-bounds? v . args | |
1228 | @deffnx {C Function} scm_array_in_bounds_p (v, args) | |
1229 | Return @code{#t} if its arguments would be acceptable to | |
1230 | @code{array-ref}. | |
1231 | @end deffn | |
1232 | ||
1233 | @c fixme: why do these sigs differ? -ttn 2001/07/19 01:14:12 | |
1234 | @deffn {Scheme Procedure} array-set! v obj . args | |
1235 | @deffnx {Scheme Procedure} uniform-array-set1! v obj args | |
1236 | @deffnx {C Function} scm_array_set_x (v, obj, args) | |
1237 | Set the element at the @code{(index1, index2)} element in @var{array} to | |
1238 | @var{new-value}. The value returned by array-set! is unspecified. | |
1239 | @end deffn | |
1240 | ||
1241 | @deffn {Scheme Procedure} make-shared-array oldra mapfunc . dims | |
1242 | @deffnx {C Function} scm_make_shared_array (oldra, mapfunc, dims) | |
1243 | @code{make-shared-array} can be used to create shared subarrays of other | |
1244 | arrays. The @var{mapper} is a function that translates coordinates in | |
1245 | the new array into coordinates in the old array. A @var{mapper} must be | |
1246 | linear, and its range must stay within the bounds of the old array, but | |
1247 | it can be otherwise arbitrary. A simple example: | |
1248 | @lisp | |
1249 | (define fred (make-array #f 8 8)) | |
1250 | (define freds-diagonal | |
1251 | (make-shared-array fred (lambda (i) (list i i)) 8)) | |
1252 | (array-set! freds-diagonal 'foo 3) | |
1253 | (array-ref fred 3 3) @result{} foo | |
1254 | (define freds-center | |
1255 | (make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j))) 2 2)) | |
1256 | (array-ref freds-center 0 0) @result{} foo | |
1257 | @end lisp | |
1258 | @end deffn | |
1259 | ||
1260 | @deffn {Scheme Procedure} shared-array-increments ra | |
1261 | @deffnx {C Function} scm_shared_array_increments (ra) | |
1262 | For each dimension, return the distance between elements in the root vector. | |
1263 | @end deffn | |
1264 | ||
1265 | @deffn {Scheme Procedure} shared-array-offset ra | |
1266 | @deffnx {C Function} scm_shared_array_offset (ra) | |
1267 | Return the root vector index of the first element in the array. | |
1268 | @end deffn | |
1269 | ||
1270 | @deffn {Scheme Procedure} shared-array-root ra | |
1271 | @deffnx {C Function} scm_shared_array_root (ra) | |
1272 | Return the root vector of a shared array. | |
1273 | @end deffn | |
1274 | ||
1275 | @deffn {Scheme Procedure} transpose-array ra . args | |
1276 | @deffnx {C Function} scm_transpose_array (ra, args) | |
1277 | Return an array sharing contents with @var{array}, but with | |
1278 | dimensions arranged in a different order. There must be one | |
1279 | @var{dim} argument for each dimension of @var{array}. | |
1280 | @var{dim0}, @var{dim1}, @dots{} should be integers between 0 | |
1281 | and the rank of the array to be returned. Each integer in that | |
1282 | range must appear at least once in the argument list. | |
1283 | ||
1284 | The values of @var{dim0}, @var{dim1}, @dots{} correspond to | |
1285 | dimensions in the array to be returned, their positions in the | |
1286 | argument list to dimensions of @var{array}. Several @var{dim}s | |
1287 | may have the same value, in which case the returned array will | |
1288 | have smaller rank than @var{array}. | |
1289 | ||
1290 | @lisp | |
1291 | (transpose-array '#2((a b) (c d)) 1 0) @result{} #2((a c) (b d)) | |
1292 | (transpose-array '#2((a b) (c d)) 0 0) @result{} #1(a d) | |
1293 | (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) @result{} | |
1294 | #2((a 4) (b 5) (c 6)) | |
1295 | @end lisp | |
1296 | @end deffn | |
1297 | ||
1298 | @deffn {Scheme Procedure} enclose-array ra . axes | |
1299 | @deffnx {C Function} scm_enclose_array (ra, axes) | |
1300 | @var{dim0}, @var{dim1} @dots{} should be nonnegative integers less than | |
1301 | the rank of @var{array}. @var{enclose-array} returns an array | |
1302 | resembling an array of shared arrays. The dimensions of each shared | |
1303 | array are the same as the @var{dim}th dimensions of the original array, | |
1304 | the dimensions of the outer array are the same as those of the original | |
1305 | array that did not match a @var{dim}. | |
1306 | ||
1307 | An enclosed array is not a general Scheme array. Its elements may not | |
1308 | be set using @code{array-set!}. Two references to the same element of | |
1309 | an enclosed array will be @code{equal?} but will not in general be | |
1310 | @code{eq?}. The value returned by @var{array-prototype} when given an | |
1311 | enclosed array is unspecified. | |
1312 | ||
1313 | examples: | |
1314 | @lisp | |
1315 | (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1) @result{} | |
1316 | #<enclosed-array (#1(a d) #1(b e) #1(c f)) (#1(1 4) #1(2 5) #1(3 6))> | |
1317 | ||
1318 | (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 0) @result{} | |
1319 | #<enclosed-array #2((a 1) (d 4)) #2((b 2) (e 5)) #2((c 3) (f 6))> | |
1320 | @end lisp | |
1321 | @end deffn | |
1322 | ||
1323 | @deffn {Scheme Procedure} array-shape array | |
1324 | Return a list of inclusive bounds of integers. | |
1325 | @example | |
1326 | (array-shape (make-array 'foo '(-1 3) 5)) @result{} ((-1 3) (0 4)) | |
1327 | @end example | |
1328 | @end deffn | |
1329 | ||
1330 | @deffn {Scheme Procedure} array-dimensions ra | |
1331 | @deffnx {C Function} scm_array_dimensions (ra) | |
1332 | @code{Array-dimensions} is similar to @code{array-shape} but replaces | |
1333 | elements with a @code{0} minimum with one greater than the maximum. So: | |
1334 | @lisp | |
1335 | (array-dimensions (make-array 'foo '(-1 3) 5)) @result{} ((-1 3) 5) | |
1336 | @end lisp | |
1337 | @end deffn | |
1338 | ||
1339 | @deffn {Scheme Procedure} array-rank ra | |
1340 | @deffnx {C Function} scm_array_rank (ra) | |
1341 | Return the number of dimensions of @var{obj}. If @var{obj} is | |
1342 | not an array, @code{0} is returned. | |
1343 | @end deffn | |
1344 | ||
1345 | @deffn {Scheme Procedure} array->list v | |
1346 | @deffnx {C Function} scm_t_arrayo_list (v) | |
1347 | Return a list consisting of all the elements, in order, of | |
1348 | @var{array}. | |
1349 | @end deffn | |
1350 | ||
1351 | @deffn {Scheme Procedure} array-copy! src dst | |
1352 | @deffnx {Scheme Procedure} array-copy-in-order! src dst | |
1353 | @deffnx {C Function} scm_array_copy_x (src, dst) | |
1354 | Copy every element from vector or array @var{source} to the | |
1355 | corresponding element of @var{destination}. @var{destination} must have | |
1356 | the same rank as @var{source}, and be at least as large in each | |
1357 | dimension. The order is unspecified. | |
1358 | @end deffn | |
1359 | ||
1360 | @deffn {Scheme Procedure} array-fill! ra fill | |
1361 | @deffnx {C Function} scm_array_fill_x (ra, fill) | |
1362 | Store @var{fill} in every element of @var{array}. The value returned | |
1363 | is unspecified. | |
1364 | @end deffn | |
1365 | ||
1366 | @c begin (texi-doc-string "guile" "array-equal?") | |
1367 | @deffn {Scheme Procedure} array-equal? ra0 ra1 | |
1368 | Return @code{#t} iff all arguments are arrays with the same shape, the | |
1369 | same type, and have corresponding elements which are either | |
1370 | @code{equal?} or @code{array-equal?}. This function differs from | |
1371 | @code{equal?} in that a one dimensional shared array may be | |
1372 | @var{array-equal?} but not @var{equal?} to a vector or uniform vector. | |
1373 | @end deffn | |
1374 | ||
1375 | @deffn {Scheme Procedure} array-contents array [strict] | |
1376 | @deffnx {C Function} scm_array_contents (array, strict) | |
1377 | If @var{array} may be @dfn{unrolled} into a one dimensional shared array | |
1378 | without changing their order (last subscript changing fastest), then | |
1379 | @code{array-contents} returns that shared array, otherwise it returns | |
1380 | @code{#f}. All arrays made by @var{make-array} and | |
1381 | @var{make-uniform-array} may be unrolled, some arrays made by | |
1382 | @var{make-shared-array} may not be. | |
1383 | ||
1384 | If the optional argument @var{strict} is provided, a shared array will | |
1385 | be returned only if its elements are stored internally contiguous in | |
1386 | memory. | |
1387 | @end deffn | |
1388 | ||
1389 | @node Array Mapping | |
1390 | @subsection Array Mapping | |
1391 | ||
1392 | @deffn {Scheme Procedure} array-map! ra0 proc . lra | |
1393 | @deffnx {Scheme Procedure} array-map-in-order! ra0 proc . lra | |
1394 | @deffnx {C Function} scm_array_map_x (ra0, proc, lra) | |
1395 | @var{array1}, @dots{} must have the same number of dimensions as | |
1396 | @var{array0} and have a range for each index which includes the range | |
1397 | for the corresponding index in @var{array0}. @var{proc} is applied to | |
1398 | each tuple of elements of @var{array1} @dots{} and the result is stored | |
1399 | as the corresponding element in @var{array0}. The value returned is | |
1400 | unspecified. The order of application is unspecified. | |
1401 | @end deffn | |
1402 | ||
1403 | @deffn {Scheme Procedure} array-for-each proc ra0 . lra | |
1404 | @deffnx {C Function} scm_array_for_each (proc, ra0, lra) | |
1405 | Apply @var{proc} to each tuple of elements of @var{array0} @dots{} | |
1406 | in row-major order. The value returned is unspecified. | |
1407 | @end deffn | |
1408 | ||
1409 | @deffn {Scheme Procedure} array-index-map! ra proc | |
1410 | @deffnx {C Function} scm_array_index_map_x (ra, proc) | |
1411 | Apply @var{proc} to the indices of each element of @var{array} in | |
1412 | turn, storing the result in the corresponding element. The value | |
1413 | returned and the order of application are unspecified. | |
1414 | ||
1415 | One can implement @var{array-indexes} as | |
1416 | @lisp | |
1417 | (define (array-indexes array) | |
1418 | (let ((ra (apply make-array #f (array-shape array)))) | |
1419 | (array-index-map! ra (lambda x x)) | |
1420 | ra)) | |
1421 | @end lisp | |
1422 | Another example: | |
1423 | @lisp | |
1424 | (define (apl:index-generator n) | |
1425 | (let ((v (make-uniform-vector n 1))) | |
1426 | (array-index-map! v (lambda (i) i)) | |
1427 | v)) | |
1428 | @end lisp | |
1429 | @end deffn | |
1430 | ||
1431 | @node Uniform Arrays | |
1432 | @subsection Uniform Arrays | |
1433 | @tpindex Uniform Arrays | |
1434 | ||
1435 | @noindent | |
1436 | @dfn{Uniform arrays} have elements all of the | |
1437 | same type and occupy less storage than conventional | |
1438 | arrays. Uniform arrays with a single zero-based dimension | |
1439 | are also known as @dfn{uniform vectors}. The procedures in | |
1440 | this section can also be used on conventional arrays, vectors, | |
1441 | bit-vectors and strings. | |
1442 | ||
1443 | @noindent | |
1444 | When creating a uniform array, the type of data to be stored | |
1445 | is indicated with a @var{prototype} argument. The following table | |
1446 | lists the types available and example prototypes: | |
1447 | ||
1448 | @example | |
1449 | prototype type printing character | |
1450 | ||
1451 | #t boolean (bit-vector) b | |
1452 | #\a char (string) a | |
1453 | #\nul byte (integer) y | |
1454 | 's short (integer) h | |
1455 | 1 unsigned long (integer) u | |
1456 | -1 signed long (integer) e | |
1457 | 'l signed long long (integer) l | |
1458 | 1.0 float (single precision) s | |
1459 | 1/3 double (double precision float) i | |
1460 | 0+i complex (double precision) c | |
1461 | () conventional vector | |
1462 | @end example | |
1463 | ||
1464 | @noindent | |
1465 | Unshared uniform arrays of characters with a single zero-based dimension | |
1466 | are identical to strings: | |
1467 | ||
1468 | @example | |
1469 | (make-uniform-array #\a 3) @result{} | |
1470 | "aaa" | |
1471 | @end example | |
1472 | ||
1473 | @noindent | |
1474 | Unshared uniform arrays of booleans with a single zero-based dimension | |
1475 | are identical to @ref{Bit Vectors, bit-vectors}. | |
1476 | ||
1477 | @example | |
1478 | (make-uniform-array #t 3) @result{} | |
1479 | #*111 | |
1480 | @end example | |
1481 | ||
1482 | @noindent | |
1483 | Other uniform vectors are written in a form similar to that of vectors, | |
1484 | except that a single character from the above table is put between | |
1485 | @code{#} and @code{(}. For example, a uniform vector of signed | |
1486 | long integers is displayed in the form @code{'#e(3 5 9)}. | |
1487 | ||
1488 | @deffn {Scheme Procedure} array? v [prot] | |
1489 | Return @code{#t} if the @var{obj} is an array, and @code{#f} if not. | |
1490 | ||
1491 | The @var{prototype} argument is used with uniform arrays and is described | |
1492 | elsewhere. | |
1493 | @end deffn | |
1494 | ||
1495 | @deffn {Scheme Procedure} make-uniform-array prototype bound1 bound2 @dots{} | |
1496 | Create and return a uniform array of type corresponding to | |
1497 | @var{prototype} that has as many dimensions as there are @var{bound}s | |
1498 | and fill it with @var{prototype}. | |
1499 | @end deffn | |
1500 | ||
1501 | @deffn {Scheme Procedure} array-prototype ra | |
1502 | @deffnx {C Function} scm_array_prototype (ra) | |
1503 | Return an object that would produce an array of the same type | |
1504 | as @var{array}, if used as the @var{prototype} for | |
1505 | @code{make-uniform-array}. | |
1506 | @end deffn | |
1507 | ||
1508 | @deffn {Scheme Procedure} list->uniform-array ndim prot lst | |
1509 | @deffnx {Scheme Procedure} list->uniform-vector prot lst | |
1510 | @deffnx {C Function} scm_list_to_uniform_array (ndim, prot, lst) | |
1511 | Return a uniform array of the type indicated by prototype | |
1512 | @var{prot} with elements the same as those of @var{lst}. | |
1513 | Elements must be of the appropriate type, no coercions are | |
1514 | done. | |
1515 | @end deffn | |
1516 | ||
1517 | @deffn {Scheme Procedure} uniform-vector-fill! uve fill | |
1518 | Store @var{fill} in every element of @var{uve}. The value returned is | |
1519 | unspecified. | |
1520 | @end deffn | |
1521 | ||
1522 | @deffn {Scheme Procedure} uniform-vector-length v | |
1523 | @deffnx {C Function} scm_uniform_vector_length (v) | |
1524 | Return the number of elements in @var{uve}. | |
1525 | @end deffn | |
1526 | ||
1527 | @deffn {Scheme Procedure} dimensions->uniform-array dims prot [fill] | |
1528 | @deffnx {Scheme Procedure} make-uniform-vector length prototype [fill] | |
1529 | @deffnx {C Function} scm_dimensions_to_uniform_array (dims, prot, fill) | |
1530 | Create and return a uniform array or vector of type | |
1531 | corresponding to @var{prototype} with dimensions @var{dims} or | |
1532 | length @var{length}. If @var{fill} is supplied, it's used to | |
1533 | fill the array, otherwise @var{prototype} is used. | |
1534 | @end deffn | |
1535 | ||
1536 | @c Another compiled-closure. -twp | |
1537 | ||
1538 | @deffn {Scheme Procedure} uniform-array-read! ra [port_or_fd [start [end]]] | |
1539 | @deffnx {Scheme Procedure} uniform-vector-read! uve [port-or-fdes] [start] [end] | |
1540 | @deffnx {C Function} scm_uniform_array_read_x (ra, port_or_fd, start, end) | |
1541 | Attempt to read all elements of @var{ura}, in lexicographic order, as | |
1542 | binary objects from @var{port-or-fdes}. | |
1543 | If an end of file is encountered, | |
1544 | the objects up to that point are put into @var{ura} | |
1545 | (starting at the beginning) and the remainder of the array is | |
1546 | unchanged. | |
1547 | ||
1548 | The optional arguments @var{start} and @var{end} allow | |
1549 | a specified region of a vector (or linearized array) to be read, | |
1550 | leaving the remainder of the vector unchanged. | |
1551 | ||
1552 | @code{uniform-array-read!} returns the number of objects read. | |
1553 | @var{port-or-fdes} may be omitted, in which case it defaults to the value | |
1554 | returned by @code{(current-input-port)}. | |
1555 | @end deffn | |
1556 | ||
1557 | @deffn {Scheme Procedure} uniform-array-write v [port_or_fd [start [end]]] | |
1558 | @deffnx {Scheme Procedure} uniform-vector-write uve [port-or-fdes] [start] [end] | |
1559 | @deffnx {C Function} scm_uniform_array_write (v, port_or_fd, start, end) | |
1560 | Writes all elements of @var{ura} as binary objects to | |
1561 | @var{port-or-fdes}. | |
1562 | ||
1563 | The optional arguments @var{start} | |
1564 | and @var{end} allow | |
1565 | a specified region of a vector (or linearized array) to be written. | |
1566 | ||
1567 | The number of objects actually written is returned. | |
1568 | @var{port-or-fdes} may be | |
1569 | omitted, in which case it defaults to the value returned by | |
1570 | @code{(current-output-port)}. | |
1571 | @end deffn | |
1572 | ||
1573 | @node Bit Vectors | |
1574 | @subsection Bit Vectors | |
1575 | ||
1576 | @noindent | |
1577 | Bit vectors are a specific type of uniform array: an array of booleans | |
1578 | with a single zero-based index. | |
1579 | ||
1580 | @noindent | |
1581 | They are displayed as a sequence of @code{0}s and | |
1582 | @code{1}s prefixed by @code{#*}, e.g., | |
1583 | ||
1584 | @example | |
1585 | (make-uniform-vector 8 #t #f) @result{} | |
1586 | #*00000000 | |
1587 | ||
1588 | #b(#t #f #t) @result{} | |
1589 | #*101 | |
1590 | @end example | |
1591 | ||
1592 | @deffn {Scheme Procedure} bit-count b bitvector | |
1593 | @deffnx {C Function} scm_bit_count (b, bitvector) | |
1594 | Return the number of occurrences of the boolean @var{b} in | |
1595 | @var{bitvector}. | |
1596 | @end deffn | |
1597 | ||
1598 | @deffn {Scheme Procedure} bit-position item v k | |
1599 | @deffnx {C Function} scm_bit_position (item, v, k) | |
1600 | Return the minimum index of an occurrence of @var{bool} in | |
1601 | @var{bv} which is at least @var{k}. If no @var{bool} occurs | |
1602 | within the specified range @code{#f} is returned. | |
1603 | @end deffn | |
1604 | ||
1605 | @deffn {Scheme Procedure} bit-invert! v | |
1606 | @deffnx {C Function} scm_bit_invert_x (v) | |
1607 | Modify @var{bv} by replacing each element with its negation. | |
1608 | @end deffn | |
1609 | ||
1610 | @deffn {Scheme Procedure} bit-set*! v kv obj | |
1611 | @deffnx {C Function} scm_bit_set_star_x (v, kv, obj) | |
1612 | If uve is a bit-vector @var{bv} and uve must be of the same | |
1613 | length. If @var{bool} is @code{#t}, uve is OR'ed into | |
1614 | @var{bv}; If @var{bool} is @code{#f}, the inversion of uve is | |
1615 | AND'ed into @var{bv}. | |
1616 | ||
1617 | If uve is a unsigned long integer vector all the elements of uve | |
1618 | must be between 0 and the @code{length} of @var{bv}. The bits | |
1619 | of @var{bv} corresponding to the indexes in uve are set to | |
1620 | @var{bool}. The return value is unspecified. | |
1621 | @end deffn | |
1622 | ||
1623 | @deffn {Scheme Procedure} bit-count* v kv obj | |
1624 | @deffnx {C Function} scm_bit_count_star (v, kv, obj) | |
1625 | Return | |
1626 | @lisp | |
1627 | (bit-count (bit-set*! (if bool bv (bit-invert! bv)) uve #t) #t). | |
1628 | @end lisp | |
1629 | @var{bv} is not modified. | |
1630 | @end deffn | |
1631 | ||
1632 | ||
1633 | @node Association Lists and Hash Tables | |
1634 | @section Association Lists and Hash Tables | |
1635 | ||
1636 | This chapter discusses dictionary objects: data structures that are | |
1637 | useful for organizing and indexing large bodies of information. | |
1638 | ||
1639 | @menu | |
1640 | * Dictionary Types:: About dictionary types; what they're good for. | |
1641 | * Association Lists:: List-based dictionaries. | |
1642 | * Hash Tables:: Table-based dictionaries. | |
1643 | @end menu | |
1644 | ||
1645 | @node Dictionary Types | |
1646 | @subsection Dictionary Types | |
1647 | ||
1648 | A @dfn{dictionary} object is a data structure used to index | |
1649 | information in a user-defined way. In standard Scheme, the main | |
1650 | aggregate data types are lists and vectors. Lists are not really | |
1651 | indexed at all, and vectors are indexed only by number | |
1652 | (e.g. @code{(vector-ref foo 5)}). Often you will find it useful | |
1653 | to index your data on some other type; for example, in a library | |
1654 | catalog you might want to look up a book by the name of its | |
1655 | author. Dictionaries are used to help you organize information in | |
1656 | such a way. | |
1657 | ||
1658 | An @dfn{association list} (or @dfn{alist} for short) is a list of | |
1659 | key-value pairs. Each pair represents a single quantity or | |
1660 | object; the @code{car} of the pair is a key which is used to | |
1661 | identify the object, and the @code{cdr} is the object's value. | |
1662 | ||
1663 | A @dfn{hash table} also permits you to index objects with | |
1664 | arbitrary keys, but in a way that makes looking up any one object | |
1665 | extremely fast. A well-designed hash system makes hash table | |
1666 | lookups almost as fast as conventional array or vector references. | |
1667 | ||
1668 | Alists are popular among Lisp programmers because they use only | |
1669 | the language's primitive operations (lists, @dfn{car}, @dfn{cdr} | |
1670 | and the equality primitives). No changes to the language core are | |
1671 | necessary. Therefore, with Scheme's built-in list manipulation | |
1672 | facilities, it is very convenient to handle data stored in an | |
1673 | association list. Also, alists are highly portable and can be | |
1674 | easily implemented on even the most minimal Lisp systems. | |
1675 | ||
1676 | However, alists are inefficient, especially for storing large | |
1677 | quantities of data. Because we want Guile to be useful for large | |
1678 | software systems as well as small ones, Guile provides a rich set | |
1679 | of tools for using either association lists or hash tables. | |
1680 | ||
1681 | @node Association Lists | |
1682 | @subsection Association Lists | |
1683 | @tpindex Association Lists | |
1684 | @tpindex Alist | |
1685 | ||
1686 | @cindex Association List | |
1687 | @cindex Alist | |
1688 | @cindex Database | |
1689 | ||
1690 | An association list is a conventional data structure that is often used | |
1691 | to implement simple key-value databases. It consists of a list of | |
1692 | entries in which each entry is a pair. The @dfn{key} of each entry is | |
1693 | the @code{car} of the pair and the @dfn{value} of each entry is the | |
1694 | @code{cdr}. | |
1695 | ||
1696 | @example | |
1697 | ASSOCIATION LIST ::= '( (KEY1 . VALUE1) | |
1698 | (KEY2 . VALUE2) | |
1699 | (KEY3 . VALUE3) | |
1700 | @dots{} | |
1701 | ) | |
1702 | @end example | |
1703 | ||
1704 | @noindent | |
1705 | Association lists are also known, for short, as @dfn{alists}. | |
1706 | ||
1707 | The structure of an association list is just one example of the infinite | |
1708 | number of possible structures that can be built using pairs and lists. | |
1709 | As such, the keys and values in an association list can be manipulated | |
1710 | using the general list structure procedures @code{cons}, @code{car}, | |
1711 | @code{cdr}, @code{set-car!}, @code{set-cdr!} and so on. However, | |
1712 | because association lists are so useful, Guile also provides specific | |
1713 | procedures for manipulating them. | |
1714 | ||
1715 | @menu | |
1716 | * Alist Key Equality:: | |
1717 | * Adding or Setting Alist Entries:: | |
1718 | * Retrieving Alist Entries:: | |
1719 | * Removing Alist Entries:: | |
1720 | * Sloppy Alist Functions:: | |
1721 | * Alist Example:: | |
1722 | @end menu | |
1723 | ||
1724 | @node Alist Key Equality | |
1725 | @subsubsection Alist Key Equality | |
1726 | ||
1727 | All of Guile's dedicated association list procedures, apart from | |
85a9b4ed | 1728 | @code{acons}, come in three flavors, depending on the level of equality |
4c731ece NJ |
1729 | that is required to decide whether an existing key in the association |
1730 | list is the same as the key that the procedure call uses to identify the | |
1731 | required entry. | |
1732 | ||
1733 | @itemize @bullet | |
1734 | @item | |
1735 | Procedures with @dfn{assq} in their name use @code{eq?} to determine key | |
1736 | equality. | |
1737 | ||
1738 | @item | |
1739 | Procedures with @dfn{assv} in their name use @code{eqv?} to determine | |
1740 | key equality. | |
1741 | ||
1742 | @item | |
1743 | Procedures with @dfn{assoc} in their name use @code{equal?} to | |
1744 | determine key equality. | |
1745 | @end itemize | |
1746 | ||
1747 | @code{acons} is an exception because it is used to build association | |
1748 | lists which do not require their entries' keys to be unique. | |
1749 | ||
1750 | @node Adding or Setting Alist Entries | |
1751 | @subsubsection Adding or Setting Alist Entries | |
1752 | ||
1753 | @code{acons} adds a new entry to an association list and returns the | |
1754 | combined association list. The combined alist is formed by consing the | |
1755 | new entry onto the head of the alist specified in the @code{acons} | |
1756 | procedure call. So the specified alist is not modified, but its | |
1757 | contents become shared with the tail of the combined alist that | |
1758 | @code{acons} returns. | |
1759 | ||
1760 | In the most common usage of @code{acons}, a variable holding the | |
1761 | original association list is updated with the combined alist: | |
1762 | ||
1763 | @example | |
1764 | (set! address-list (acons name address address-list)) | |
1765 | @end example | |
1766 | ||
1767 | In such cases, it doesn't matter that the old and new values of | |
1768 | @code{address-list} share some of their contents, since the old value is | |
1769 | usually no longer independently accessible. | |
1770 | ||
1771 | Note that @code{acons} adds the specified new entry regardless of | |
1772 | whether the alist may already contain entries with keys that are, in | |
1773 | some sense, the same as that of the new entry. Thus @code{acons} is | |
1774 | ideal for building alists where there is no concept of key uniqueness. | |
1775 | ||
1776 | @example | |
1777 | (set! task-list (acons 3 "pay gas bill" '())) | |
1778 | task-list | |
1779 | @result{} | |
1780 | ((3 . "pay gas bill")) | |
1781 | ||
1782 | (set! task-list (acons 3 "tidy bedroom" task-list)) | |
1783 | task-list | |
1784 | @result{} | |
1785 | ((3 . "tidy bedroom") (3 . "pay gas bill")) | |
1786 | @end example | |
1787 | ||
1788 | @code{assq-set!}, @code{assv-set!} and @code{assoc-set!} are used to add | |
1789 | or replace an entry in an association list where there @emph{is} a | |
1790 | concept of key uniqueness. If the specified association list already | |
1791 | contains an entry whose key is the same as that specified in the | |
1792 | procedure call, the existing entry is replaced by the new one. | |
1793 | Otherwise, the new entry is consed onto the head of the old association | |
1794 | list to create the combined alist. In all cases, these procedures | |
1795 | return the combined alist. | |
1796 | ||
1797 | @code{assq-set!} and friends @emph{may} destructively modify the | |
1798 | structure of the old association list in such a way that an existing | |
1799 | variable is correctly updated without having to @code{set!} it to the | |
1800 | value returned: | |
1801 | ||
1802 | @example | |
1803 | address-list | |
1804 | @result{} | |
1805 | (("mary" . "34 Elm Road") ("james" . "16 Bow Street")) | |
1806 | ||
1807 | (assoc-set! address-list "james" "1a London Road") | |
1808 | @result{} | |
1809 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
1810 | ||
1811 | address-list | |
1812 | @result{} | |
1813 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
1814 | @end example | |
1815 | ||
1816 | Or they may not: | |
1817 | ||
1818 | @example | |
1819 | (assoc-set! address-list "bob" "11 Newington Avenue") | |
1820 | @result{} | |
1821 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
1822 | ("james" . "1a London Road")) | |
1823 | ||
1824 | address-list | |
1825 | @result{} | |
1826 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
1827 | @end example | |
1828 | ||
1829 | The only safe way to update an association list variable when adding or | |
1830 | replacing an entry like this is to @code{set!} the variable to the | |
1831 | returned value: | |
1832 | ||
1833 | @example | |
1834 | (set! address-list | |
1835 | (assoc-set! address-list "bob" "11 Newington Avenue")) | |
1836 | address-list | |
1837 | @result{} | |
1838 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
1839 | ("james" . "1a London Road")) | |
1840 | @end example | |
1841 | ||
1842 | Because of this slight inconvenience, you may find it more convenient to | |
1843 | use hash tables to store dictionary data. If your application will not | |
1844 | be modifying the contents of an alist very often, this may not make much | |
1845 | difference to you. | |
1846 | ||
1847 | If you need to keep the old value of an association list in a form | |
1848 | independent from the list that results from modification by | |
1849 | @code{acons}, @code{assq-set!}, @code{assv-set!} or @code{assoc-set!}, | |
1850 | use @code{list-copy} to copy the old association list before modifying | |
1851 | it. | |
1852 | ||
1853 | @deffn {Scheme Procedure} acons key value alist | |
1854 | @deffnx {C Function} scm_acons (key, value, alist) | |
1855 | Add a new key-value pair to @var{alist}. A new pair is | |
1856 | created whose car is @var{key} and whose cdr is @var{value}, and the | |
1857 | pair is consed onto @var{alist}, and the new list is returned. This | |
1858 | function is @emph{not} destructive; @var{alist} is not modified. | |
1859 | @end deffn | |
1860 | ||
1861 | @deffn {Scheme Procedure} assq-set! alist key val | |
1862 | @deffnx {Scheme Procedure} assv-set! alist key value | |
1863 | @deffnx {Scheme Procedure} assoc-set! alist key value | |
1864 | @deffnx {C Function} scm_assq_set_x (alist, key, val) | |
1865 | @deffnx {C Function} scm_assv_set_x (alist, key, val) | |
1866 | @deffnx {C Function} scm_assoc_set_x (alist, key, val) | |
85a9b4ed | 1867 | Re-associate @var{key} in @var{alist} with @var{value}: find any existing |
4c731ece NJ |
1868 | @var{alist} entry for @var{key} and associate it with the new |
1869 | @var{value}. If @var{alist} does not contain an entry for @var{key}, | |
1870 | add a new one. Return the (possibly new) alist. | |
1871 | ||
1872 | These functions do not attempt to verify the structure of @var{alist}, | |
1873 | and so may cause unusual results if passed an object that is not an | |
1874 | association list. | |
1875 | @end deffn | |
1876 | ||
1877 | @node Retrieving Alist Entries | |
1878 | @subsubsection Retrieving Alist Entries | |
1879 | @rnindex assq | |
1880 | @rnindex assv | |
1881 | @rnindex assoc | |
1882 | ||
1883 | @code{assq}, @code{assv} and @code{assoc} take an alist and a key as | |
1884 | arguments and return the entry for that key if an entry exists, or | |
1885 | @code{#f} if there is no entry for that key. Note that, in the cases | |
1886 | where an entry exists, these procedures return the complete entry, that | |
1887 | is @code{(KEY . VALUE)}, not just the value. | |
1888 | ||
1889 | @deffn {Scheme Procedure} assq key alist | |
1890 | @deffnx {Scheme Procedure} assv key alist | |
1891 | @deffnx {Scheme Procedure} assoc key alist | |
1892 | @deffnx {C Function} scm_assq (key, alist) | |
1893 | @deffnx {C Function} scm_assv (key, alist) | |
1894 | @deffnx {C Function} scm_assoc (key, alist) | |
1895 | Fetch the entry in @var{alist} that is associated with @var{key}. To | |
1896 | decide whether the argument @var{key} matches a particular entry in | |
1897 | @var{alist}, @code{assq} compares keys with @code{eq?}, @code{assv} | |
1898 | uses @code{eqv?} and @code{assoc} uses @code{equal?}. If @var{key} | |
1899 | cannot be found in @var{alist} (according to whichever equality | |
1900 | predicate is in use), then return @code{#f}. These functions | |
1901 | return the entire alist entry found (i.e. both the key and the value). | |
1902 | @end deffn | |
1903 | ||
1904 | @code{assq-ref}, @code{assv-ref} and @code{assoc-ref}, on the other | |
1905 | hand, take an alist and a key and return @emph{just the value} for that | |
1906 | key, if an entry exists. If there is no entry for the specified key, | |
1907 | these procedures return @code{#f}. | |
1908 | ||
1909 | This creates an ambiguity: if the return value is @code{#f}, it means | |
1910 | either that there is no entry with the specified key, or that there | |
1911 | @emph{is} an entry for the specified key, with value @code{#f}. | |
1912 | Consequently, @code{assq-ref} and friends should only be used where it | |
1913 | is known that an entry exists, or where the ambiguity doesn't matter | |
1914 | for some other reason. | |
1915 | ||
1916 | @deffn {Scheme Procedure} assq-ref alist key | |
1917 | @deffnx {Scheme Procedure} assv-ref alist key | |
1918 | @deffnx {Scheme Procedure} assoc-ref alist key | |
1919 | @deffnx {C Function} scm_assq_ref (alist, key) | |
1920 | @deffnx {C Function} scm_assv_ref (alist, key) | |
1921 | @deffnx {C Function} scm_assoc_ref (alist, key) | |
1922 | Like @code{assq}, @code{assv} and @code{assoc}, except that only the | |
1923 | value associated with @var{key} in @var{alist} is returned. These | |
1924 | functions are equivalent to | |
1925 | ||
1926 | @lisp | |
1927 | (let ((ent (@var{associator} @var{key} @var{alist}))) | |
1928 | (and ent (cdr ent))) | |
1929 | @end lisp | |
1930 | ||
1931 | where @var{associator} is one of @code{assq}, @code{assv} or @code{assoc}. | |
1932 | @end deffn | |
1933 | ||
1934 | @node Removing Alist Entries | |
1935 | @subsubsection Removing Alist Entries | |
1936 | ||
1937 | To remove the element from an association list whose key matches a | |
1938 | specified key, use @code{assq-remove!}, @code{assv-remove!} or | |
1939 | @code{assoc-remove!} (depending, as usual, on the level of equality | |
1940 | required between the key that you specify and the keys in the | |
1941 | association list). | |
1942 | ||
1943 | As with @code{assq-set!} and friends, the specified alist may or may not | |
1944 | be modified destructively, and the only safe way to update a variable | |
1945 | containing the alist is to @code{set!} it to the value that | |
1946 | @code{assq-remove!} and friends return. | |
1947 | ||
1948 | @example | |
1949 | address-list | |
1950 | @result{} | |
1951 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
1952 | ("james" . "1a London Road")) | |
1953 | ||
1954 | (set! address-list (assoc-remove! address-list "mary")) | |
1955 | address-list | |
1956 | @result{} | |
1957 | (("bob" . "11 Newington Avenue") ("james" . "1a London Road")) | |
1958 | @end example | |
1959 | ||
1960 | Note that, when @code{assq/v/oc-remove!} is used to modify an | |
1961 | association list that has been constructed only using the corresponding | |
1962 | @code{assq/v/oc-set!}, there can be at most one matching entry in the | |
1963 | alist, so the question of multiple entries being removed in one go does | |
1964 | not arise. If @code{assq/v/oc-remove!} is applied to an association | |
1965 | list that has been constructed using @code{acons}, or an | |
1966 | @code{assq/v/oc-set!} with a different level of equality, or any mixture | |
1967 | of these, it removes only the first matching entry from the alist, even | |
1968 | if the alist might contain further matching entries. For example: | |
1969 | ||
1970 | @example | |
1971 | (define address-list '()) | |
1972 | (set! address-list (assq-set! address-list "mary" "11 Elm Street")) | |
1973 | (set! address-list (assq-set! address-list "mary" "57 Pine Drive")) | |
1974 | address-list | |
1975 | @result{} | |
1976 | (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street")) | |
1977 | ||
1978 | (set! address-list (assoc-remove! address-list "mary")) | |
1979 | address-list | |
1980 | @result{} | |
1981 | (("mary" . "11 Elm Street")) | |
1982 | @end example | |
1983 | ||
1984 | In this example, the two instances of the string "mary" are not the same | |
1985 | when compared using @code{eq?}, so the two @code{assq-set!} calls add | |
1986 | two distinct entries to @code{address-list}. When compared using | |
1987 | @code{equal?}, both "mary"s in @code{address-list} are the same as the | |
1988 | "mary" in the @code{assoc-remove!} call, but @code{assoc-remove!} stops | |
1989 | after removing the first matching entry that it finds, and so one of the | |
1990 | "mary" entries is left in place. | |
1991 | ||
1992 | @deffn {Scheme Procedure} assq-remove! alist key | |
1993 | @deffnx {Scheme Procedure} assv-remove! alist key | |
1994 | @deffnx {Scheme Procedure} assoc-remove! alist key | |
1995 | @deffnx {C Function} scm_assq_remove_x (alist, key) | |
1996 | @deffnx {C Function} scm_assv_remove_x (alist, key) | |
1997 | @deffnx {C Function} scm_assoc_remove_x (alist, key) | |
1998 | Delete the first entry in @var{alist} associated with @var{key}, and return | |
1999 | the resulting alist. | |
2000 | @end deffn | |
2001 | ||
2002 | @node Sloppy Alist Functions | |
2003 | @subsubsection Sloppy Alist Functions | |
2004 | ||
2005 | @code{sloppy-assq}, @code{sloppy-assv} and @code{sloppy-assoc} behave | |
2006 | like the corresponding non-@code{sloppy-} procedures, except that they | |
2007 | return @code{#f} when the specified association list is not well-formed, | |
2008 | where the non-@code{sloppy-} versions would signal an error. | |
2009 | ||
2010 | Specifically, there are two conditions for which the non-@code{sloppy-} | |
2011 | procedures signal an error, which the @code{sloppy-} procedures handle | |
2012 | instead by returning @code{#f}. Firstly, if the specified alist as a | |
2013 | whole is not a proper list: | |
2014 | ||
2015 | @example | |
2016 | (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame")) | |
2017 | @result{} | |
2018 | ERROR: In procedure assoc in expression (assoc "mary" (quote #)): | |
2019 | ERROR: Wrong type argument in position 2 (expecting NULLP): "open sesame" | |
2020 | ABORT: (wrong-type-arg) | |
2021 | ||
2022 | (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame")) | |
2023 | @result{} | |
2024 | #f | |
2025 | @end example | |
2026 | ||
2027 | @noindent | |
2028 | Secondly, if one of the entries in the specified alist is not a pair: | |
2029 | ||
2030 | @example | |
2031 | (assoc 2 '((1 . 1) 2 (3 . 9))) | |
2032 | @result{} | |
2033 | ERROR: In procedure assoc in expression (assoc 2 (quote #)): | |
2034 | ERROR: Wrong type argument in position 2 (expecting CONSP): 2 | |
2035 | ABORT: (wrong-type-arg) | |
2036 | ||
2037 | (sloppy-assoc 2 '((1 . 1) 2 (3 . 9))) | |
2038 | @result{} | |
2039 | #f | |
2040 | @end example | |
2041 | ||
2042 | Unless you are explicitly working with badly formed association lists, | |
2043 | it is much safer to use the non-@code{sloppy-} procedures, because they | |
2044 | help to highlight coding and data errors that the @code{sloppy-} | |
2045 | versions would silently cover up. | |
2046 | ||
2047 | @deffn {Scheme Procedure} sloppy-assq key alist | |
2048 | @deffnx {C Function} scm_sloppy_assq (key, alist) | |
2049 | Behaves like @code{assq} but does not do any error checking. | |
2050 | Recommended only for use in Guile internals. | |
2051 | @end deffn | |
2052 | ||
2053 | @deffn {Scheme Procedure} sloppy-assv key alist | |
2054 | @deffnx {C Function} scm_sloppy_assv (key, alist) | |
2055 | Behaves like @code{assv} but does not do any error checking. | |
2056 | Recommended only for use in Guile internals. | |
2057 | @end deffn | |
2058 | ||
2059 | @deffn {Scheme Procedure} sloppy-assoc key alist | |
2060 | @deffnx {C Function} scm_sloppy_assoc (key, alist) | |
2061 | Behaves like @code{assoc} but does not do any error checking. | |
2062 | Recommended only for use in Guile internals. | |
2063 | @end deffn | |
2064 | ||
2065 | @node Alist Example | |
2066 | @subsubsection Alist Example | |
2067 | ||
2068 | Here is a longer example of how alists may be used in practice. | |
2069 | ||
2070 | @lisp | |
2071 | (define capitals '(("New York" . "Albany") | |
2072 | ("Oregon" . "Salem") | |
2073 | ("Florida" . "Miami"))) | |
2074 | ||
2075 | ;; What's the capital of Oregon? | |
2076 | (assoc "Oregon" capitals) @result{} ("Oregon" . "Salem") | |
2077 | (assoc-ref capitals "Oregon") @result{} "Salem" | |
2078 | ||
2079 | ;; We left out South Dakota. | |
2080 | (set! capitals | |
5ad5a7b6 | 2081 | (assoc-set! capitals "South Dakota" "Pierre")) |
4c731ece | 2082 | capitals |
5ad5a7b6 | 2083 | @result{} (("South Dakota" . "Pierre") |
4c731ece NJ |
2084 | ("New York" . "Albany") |
2085 | ("Oregon" . "Salem") | |
2086 | ("Florida" . "Miami")) | |
2087 | ||
2088 | ;; And we got Florida wrong. | |
2089 | (set! capitals | |
2090 | (assoc-set! capitals "Florida" "Tallahassee")) | |
2091 | capitals | |
5ad5a7b6 | 2092 | @result{} (("South Dakota" . "Pierre") |
4c731ece NJ |
2093 | ("New York" . "Albany") |
2094 | ("Oregon" . "Salem") | |
2095 | ("Florida" . "Tallahassee")) | |
2096 | ||
2097 | ;; After Oregon secedes, we can remove it. | |
2098 | (set! capitals | |
2099 | (assoc-remove! capitals "Oregon")) | |
2100 | capitals | |
5ad5a7b6 | 2101 | @result{} (("South Dakota" . "Pierre") |
4c731ece NJ |
2102 | ("New York" . "Albany") |
2103 | ("Florida" . "Tallahassee")) | |
2104 | @end lisp | |
2105 | ||
2106 | @node Hash Tables | |
2107 | @subsection Hash Tables | |
2108 | @tpindex Hash Tables | |
2109 | ||
2110 | @c FIXME::martin: Review me! | |
2111 | ||
2112 | Hash tables are dictionaries which offer similar functionality as | |
2113 | association lists: They provide a mapping from keys to values. The | |
2114 | difference is that association lists need time linear in the size of | |
2115 | elements when searching for entries, whereas hash tables can normally | |
2116 | search in constant time. The drawback is that hash tables require a | |
2117 | little bit more memory, and that you can not use the normal list | |
2118 | procedures (@pxref{Lists}) for working with them. | |
2119 | ||
2120 | @menu | |
2121 | * Hash Table Examples:: Demonstration of hash table usage. | |
2122 | * Hash Table Reference:: Hash table procedure descriptions. | |
2123 | @end menu | |
2124 | ||
2125 | ||
2126 | @node Hash Table Examples | |
2127 | @subsubsection Hash Table Examples | |
2128 | ||
2129 | @c FIXME::martin: Review me! | |
2130 | ||
2131 | For demonstration purposes, this section gives a few usage examples of | |
2132 | some hash table procedures, together with some explanation what they do. | |
2133 | ||
2134 | First we start by creating a new hash table with 31 slots, and | |
2135 | populate it with two key/value pairs. | |
2136 | ||
2137 | @lisp | |
2138 | (define h (make-hash-table 31)) | |
2139 | ||
2140 | (hashq-create-handle! h 'foo "bar") | |
2141 | @result{} | |
2142 | (foo . "bar") | |
2143 | ||
2144 | (hashq-create-handle! h 'braz "zonk") | |
2145 | @result{} | |
2146 | (braz . "zonk") | |
2147 | ||
2148 | (hashq-create-handle! h 'frob #f) | |
2149 | @result{} | |
2150 | (frob . #f) | |
2151 | @end lisp | |
2152 | ||
2153 | You can get the value for a given key with the procedure | |
2154 | @code{hashq-ref}, but the problem with this procedure is that you | |
2155 | cannot reliably determine whether a key does exists in the table. The | |
2156 | reason is that the procedure returns @code{#f} if the key is not in | |
2157 | the table, but it will return the same value if the key is in the | |
2158 | table and just happens to have the value @code{#f}, as you can see in | |
2159 | the following examples. | |
2160 | ||
2161 | @lisp | |
2162 | (hashq-ref h 'foo) | |
2163 | @result{} | |
2164 | "bar" | |
2165 | ||
2166 | (hashq-ref h 'frob) | |
2167 | @result{} | |
2168 | #f | |
2169 | ||
2170 | (hashq-ref h 'not-there) | |
2171 | @result{} | |
2172 | #f | |
2173 | @end lisp | |
2174 | ||
2175 | Better is to use the procedure @code{hashq-get-handle}, which makes a | |
2176 | distinction between the two cases. Just like @code{assq}, this | |
2177 | procedure returns a key/value-pair on success, and @code{#f} if the | |
2178 | key is not found. | |
2179 | ||
2180 | @lisp | |
2181 | (hashq-get-handle h 'foo) | |
2182 | @result{} | |
2183 | (foo . "bar") | |
2184 | ||
2185 | (hashq-get-handle h 'not-there) | |
2186 | @result{} | |
2187 | #f | |
2188 | @end lisp | |
2189 | ||
2190 | There is no procedure for calculating the number of key/value-pairs in | |
2191 | a hash table, but @code{hash-fold} can be used for doing exactly that. | |
2192 | ||
2193 | @lisp | |
2194 | (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h) | |
2195 | @result{} | |
2196 | 3 | |
2197 | @end lisp | |
2198 | ||
2199 | @node Hash Table Reference | |
2200 | @subsubsection Hash Table Reference | |
2201 | ||
2202 | Like the association list functions, the hash table functions come | |
2203 | in several varieties: @code{hashq}, @code{hashv}, and @code{hash}. | |
2204 | The @code{hashq} functions use @code{eq?} to determine whether two | |
2205 | keys match. The @code{hashv} functions use @code{eqv?}, and the | |
2206 | @code{hash} functions use @code{equal?}. | |
2207 | ||
2208 | In each of the functions that follow, the @var{table} argument | |
2209 | must be a vector. The @var{key} and @var{value} arguments may be | |
2210 | any Scheme object. | |
2211 | ||
2212 | @deffn {Scheme Procedure} make-hash-table size | |
2213 | Create a new hash table of @var{size} slots. Note that the number of | |
2214 | slots does not limit the size of the table, it just tells how large | |
2215 | the underlying vector will be. The @var{size} should be similar to | |
2216 | the expected number of elements which will be added to the table, but | |
2217 | they need not match. For good performance, it might be a good idea to | |
2218 | use a prime number as the @var{size}. | |
2219 | @end deffn | |
2220 | ||
2221 | @deffn {Scheme Procedure} hashq-ref table key [dflt] | |
2222 | @deffnx {C Function} scm_hashq_ref (table, key, dflt) | |
2223 | Look up @var{key} in the hash table @var{table}, and return the | |
2224 | value (if any) associated with it. If @var{key} is not found, | |
2225 | return @var{default} (or @code{#f} if no @var{default} argument | |
2226 | is supplied). Uses @code{eq?} for equality testing. | |
2227 | @end deffn | |
2228 | ||
2229 | @deffn {Scheme Procedure} hashv-ref table key [dflt] | |
2230 | @deffnx {C Function} scm_hashv_ref (table, key, dflt) | |
2231 | Look up @var{key} in the hash table @var{table}, and return the | |
2232 | value (if any) associated with it. If @var{key} is not found, | |
2233 | return @var{default} (or @code{#f} if no @var{default} argument | |
2234 | is supplied). Uses @code{eqv?} for equality testing. | |
2235 | @end deffn | |
2236 | ||
2237 | @deffn {Scheme Procedure} hash-ref table key [dflt] | |
2238 | @deffnx {C Function} scm_hash_ref (table, key, dflt) | |
2239 | Look up @var{key} in the hash table @var{table}, and return the | |
2240 | value (if any) associated with it. If @var{key} is not found, | |
2241 | return @var{default} (or @code{#f} if no @var{default} argument | |
2242 | is supplied). Uses @code{equal?} for equality testing. | |
2243 | @end deffn | |
2244 | ||
2245 | @deffn {Scheme Procedure} hashq-set! table key val | |
2246 | @deffnx {C Function} scm_hashq_set_x (table, key, val) | |
2247 | Find the entry in @var{table} associated with @var{key}, and | |
2248 | store @var{value} there. Uses @code{eq?} for equality testing. | |
2249 | @end deffn | |
2250 | ||
2251 | @deffn {Scheme Procedure} hashv-set! table key val | |
2252 | @deffnx {C Function} scm_hashv_set_x (table, key, val) | |
2253 | Find the entry in @var{table} associated with @var{key}, and | |
2254 | store @var{value} there. Uses @code{eqv?} for equality testing. | |
2255 | @end deffn | |
2256 | ||
2257 | @deffn {Scheme Procedure} hash-set! table key val | |
2258 | @deffnx {C Function} scm_hash_set_x (table, key, val) | |
2259 | Find the entry in @var{table} associated with @var{key}, and | |
2260 | store @var{value} there. Uses @code{equal?} for equality | |
2261 | testing. | |
2262 | @end deffn | |
2263 | ||
2264 | @deffn {Scheme Procedure} hashq-remove! table key | |
2265 | @deffnx {C Function} scm_hashq_remove_x (table, key) | |
2266 | Remove @var{key} (and any value associated with it) from | |
2267 | @var{table}. Uses @code{eq?} for equality tests. | |
2268 | @end deffn | |
2269 | ||
2270 | @deffn {Scheme Procedure} hashv-remove! table key | |
2271 | @deffnx {C Function} scm_hashv_remove_x (table, key) | |
2272 | Remove @var{key} (and any value associated with it) from | |
2273 | @var{table}. Uses @code{eqv?} for equality tests. | |
2274 | @end deffn | |
2275 | ||
2276 | @deffn {Scheme Procedure} hash-remove! table key | |
2277 | @deffnx {C Function} scm_hash_remove_x (table, key) | |
2278 | Remove @var{key} (and any value associated with it) from | |
2279 | @var{table}. Uses @code{equal?} for equality tests. | |
2280 | @end deffn | |
2281 | ||
2282 | The standard hash table functions may be too limited for some | |
2283 | applications. For example, you may want a hash table to store | |
2284 | strings in a case-insensitive manner, so that references to keys | |
2285 | named ``foobar'', ``FOOBAR'' and ``FooBaR'' will all yield the | |
2286 | same item. Guile provides you with @dfn{extended} hash tables | |
2287 | that permit you to specify a hash function and associator function | |
2288 | of your choosing. The functions described in the rest of this section | |
2289 | can be used to implement such custom hash table structures. | |
2290 | ||
2291 | If you are unfamiliar with the inner workings of hash tables, then | |
2292 | this facility will probably be a little too abstract for you to | |
2293 | use comfortably. If you are interested in learning more, see an | |
2294 | introductory textbook on data structures or algorithms for an | |
2295 | explanation of how hash tables are implemented. | |
2296 | ||
2297 | @deffn {Scheme Procedure} hashq key size | |
2298 | @deffnx {C Function} scm_hashq (key, size) | |
2299 | Determine a hash value for @var{key} that is suitable for | |
85a9b4ed | 2300 | lookups in a hash table of size @var{size}, where @code{eq?} is |
4c731ece NJ |
2301 | used as the equality predicate. The function returns an |
2302 | integer in the range 0 to @var{size} - 1. Note that | |
2303 | @code{hashq} may use internal addresses. Thus two calls to | |
2304 | hashq where the keys are @code{eq?} are not guaranteed to | |
2305 | deliver the same value if the key object gets garbage collected | |
2306 | in between. This can happen, for example with symbols: | |
2307 | @code{(hashq 'foo n) (gc) (hashq 'foo n)} may produce two | |
2308 | different values, since @code{foo} will be garbage collected. | |
2309 | @end deffn | |
2310 | ||
2311 | @deffn {Scheme Procedure} hashv key size | |
2312 | @deffnx {C Function} scm_hashv (key, size) | |
2313 | Determine a hash value for @var{key} that is suitable for | |
85a9b4ed | 2314 | lookups in a hash table of size @var{size}, where @code{eqv?} is |
4c731ece NJ |
2315 | used as the equality predicate. The function returns an |
2316 | integer in the range 0 to @var{size} - 1. Note that | |
2317 | @code{(hashv key)} may use internal addresses. Thus two calls | |
2318 | to hashv where the keys are @code{eqv?} are not guaranteed to | |
2319 | deliver the same value if the key object gets garbage collected | |
2320 | in between. This can happen, for example with symbols: | |
2321 | @code{(hashv 'foo n) (gc) (hashv 'foo n)} may produce two | |
2322 | different values, since @code{foo} will be garbage collected. | |
2323 | @end deffn | |
2324 | ||
2325 | @deffn {Scheme Procedure} hash key size | |
2326 | @deffnx {C Function} scm_hash (key, size) | |
2327 | Determine a hash value for @var{key} that is suitable for | |
85a9b4ed | 2328 | lookups in a hash table of size @var{size}, where @code{equal?} |
4c731ece NJ |
2329 | is used as the equality predicate. The function returns an |
2330 | integer in the range 0 to @var{size} - 1. | |
2331 | @end deffn | |
2332 | ||
2333 | @deffn {Scheme Procedure} hashx-ref hash assoc table key [dflt] | |
2334 | @deffnx {C Function} scm_hashx_ref (hash, assoc, table, key, dflt) | |
2335 | This behaves the same way as the corresponding @code{ref} | |
2336 | function, but uses @var{hash} as a hash function and | |
2337 | @var{assoc} to compare keys. @code{hash} must be a function | |
2338 | that takes two arguments, a key to be hashed and a table size. | |
2339 | @code{assoc} must be an associator function, like @code{assoc}, | |
2340 | @code{assq} or @code{assv}. | |
2341 | ||
2342 | By way of illustration, @code{hashq-ref table key} is | |
2343 | equivalent to @code{hashx-ref hashq assq table key}. | |
2344 | @end deffn | |
2345 | ||
2346 | @deffn {Scheme Procedure} hashx-set! hash assoc table key val | |
2347 | @deffnx {C Function} scm_hashx_set_x (hash, assoc, table, key, val) | |
2348 | This behaves the same way as the corresponding @code{set!} | |
2349 | function, but uses @var{hash} as a hash function and | |
2350 | @var{assoc} to compare keys. @code{hash} must be a function | |
2351 | that takes two arguments, a key to be hashed and a table size. | |
2352 | @code{assoc} must be an associator function, like @code{assoc}, | |
2353 | @code{assq} or @code{assv}. | |
2354 | ||
2355 | By way of illustration, @code{hashq-set! table key} is | |
2356 | equivalent to @code{hashx-set! hashq assq table key}. | |
2357 | @end deffn | |
2358 | ||
2359 | @deffn {Scheme Procedure} hashq-get-handle table key | |
2360 | @deffnx {C Function} scm_hashq_get_handle (table, key) | |
2361 | This procedure returns the @code{(key . value)} pair from the | |
2362 | hash table @var{table}. If @var{table} does not hold an | |
2363 | associated value for @var{key}, @code{#f} is returned. | |
2364 | Uses @code{eq?} for equality testing. | |
2365 | @end deffn | |
2366 | ||
2367 | @deffn {Scheme Procedure} hashv-get-handle table key | |
2368 | @deffnx {C Function} scm_hashv_get_handle (table, key) | |
2369 | This procedure returns the @code{(key . value)} pair from the | |
2370 | hash table @var{table}. If @var{table} does not hold an | |
2371 | associated value for @var{key}, @code{#f} is returned. | |
2372 | Uses @code{eqv?} for equality testing. | |
2373 | @end deffn | |
2374 | ||
2375 | @deffn {Scheme Procedure} hash-get-handle table key | |
2376 | @deffnx {C Function} scm_hash_get_handle (table, key) | |
2377 | This procedure returns the @code{(key . value)} pair from the | |
2378 | hash table @var{table}. If @var{table} does not hold an | |
2379 | associated value for @var{key}, @code{#f} is returned. | |
2380 | Uses @code{equal?} for equality testing. | |
2381 | @end deffn | |
2382 | ||
2383 | @deffn {Scheme Procedure} hashx-get-handle hash assoc table key | |
2384 | @deffnx {C Function} scm_hashx_get_handle (hash, assoc, table, key) | |
2385 | This behaves the same way as the corresponding | |
2386 | @code{-get-handle} function, but uses @var{hash} as a hash | |
2387 | function and @var{assoc} to compare keys. @code{hash} must be | |
2388 | a function that takes two arguments, a key to be hashed and a | |
2389 | table size. @code{assoc} must be an associator function, like | |
2390 | @code{assoc}, @code{assq} or @code{assv}. | |
2391 | @end deffn | |
2392 | ||
2393 | @deffn {Scheme Procedure} hashq-create-handle! table key init | |
2394 | @deffnx {C Function} scm_hashq_create_handle_x (table, key, init) | |
2395 | This function looks up @var{key} in @var{table} and returns its handle. | |
2396 | If @var{key} is not already present, a new handle is created which | |
2397 | associates @var{key} with @var{init}. | |
2398 | @end deffn | |
2399 | ||
2400 | @deffn {Scheme Procedure} hashv-create-handle! table key init | |
2401 | @deffnx {C Function} scm_hashv_create_handle_x (table, key, init) | |
2402 | This function looks up @var{key} in @var{table} and returns its handle. | |
2403 | If @var{key} is not already present, a new handle is created which | |
2404 | associates @var{key} with @var{init}. | |
2405 | @end deffn | |
2406 | ||
2407 | @deffn {Scheme Procedure} hash-create-handle! table key init | |
2408 | @deffnx {C Function} scm_hash_create_handle_x (table, key, init) | |
2409 | This function looks up @var{key} in @var{table} and returns its handle. | |
2410 | If @var{key} is not already present, a new handle is created which | |
2411 | associates @var{key} with @var{init}. | |
2412 | @end deffn | |
2413 | ||
2414 | @deffn {Scheme Procedure} hashx-create-handle! hash assoc table key init | |
2415 | @deffnx {C Function} scm_hashx_create_handle_x (hash, assoc, table, key, init) | |
2416 | This behaves the same way as the corresponding | |
2417 | @code{-create-handle} function, but uses @var{hash} as a hash | |
2418 | function and @var{assoc} to compare keys. @code{hash} must be | |
2419 | a function that takes two arguments, a key to be hashed and a | |
2420 | table size. @code{assoc} must be an associator function, like | |
2421 | @code{assoc}, @code{assq} or @code{assv}. | |
2422 | @end deffn | |
2423 | ||
2424 | @deffn {Scheme Procedure} hash-fold proc init table | |
2425 | @deffnx {C Function} scm_hash_fold (proc, init, table) | |
2426 | An iterator over hash-table elements. | |
2427 | Accumulates and returns a result by applying PROC successively. | |
2428 | The arguments to PROC are "(key value prior-result)" where key | |
2429 | and value are successive pairs from the hash table TABLE, and | |
2430 | prior-result is either INIT (for the first application of PROC) | |
2431 | or the return value of the previous application of PROC. | |
2432 | For example, @code{(hash-fold acons '() tab)} will convert a hash | |
2433 | table into an a-list of key-value pairs. | |
2434 | @end deffn | |
2435 | ||
2436 | ||
2437 | @c Local Variables: | |
2438 | @c TeX-master: "guile.texi" | |
2439 | @c End: |