Commit | Line | Data |
---|---|---|
07d83abe MV |
1 | @c -*-texinfo-*- |
2 | @c This is part of the GNU Guile Reference Manual. | |
2b509a2e MW |
3 | @c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, |
4 | @c 2009, 2010, 2011, 2012, 2013, 2014 Free Software Foundation, Inc. | |
07d83abe MV |
5 | @c See the file guile.texi for copying conditions. |
6 | ||
07d83abe MV |
7 | @node Compound Data Types |
8 | @section Compound Data Types | |
9 | ||
10 | This chapter describes Guile's compound data types. By @dfn{compound} | |
11 | we mean that the primary purpose of these data types is to act as | |
12 | containers for other kinds of data (including other compound objects). | |
13 | For instance, a (non-uniform) vector with length 5 is a container that | |
14 | can hold five arbitrary Scheme objects. | |
15 | ||
16 | The various kinds of container object differ from each other in how | |
17 | their memory is allocated, how they are indexed, and how particular | |
18 | values can be looked up within them. | |
19 | ||
20 | @menu | |
21 | * Pairs:: Scheme's basic building block. | |
22 | * Lists:: Special list functions supported by Guile. | |
23 | * Vectors:: One-dimensional arrays of Scheme objects. | |
e6b226b9 MV |
24 | * Bit Vectors:: Vectors of bits. |
25 | * Arrays:: Matrices, etc. | |
22ec6a31 | 26 | * VLists:: Vector-like lists. |
ec7e4f77 LC |
27 | * Record Overview:: Walking through the maze of record APIs. |
28 | * SRFI-9 Records:: The standard, recommended record API. | |
29 | * Records:: Guile's historical record API. | |
30 | * Structures:: Low-level record representation. | |
07d83abe MV |
31 | * Dictionary Types:: About dictionary types in general. |
32 | * Association Lists:: List-based dictionaries. | |
22ec6a31 | 33 | * VHashes:: VList-based dictionaries. |
07d83abe MV |
34 | * Hash Tables:: Table-based dictionaries. |
35 | @end menu | |
36 | ||
37 | ||
38 | @node Pairs | |
39 | @subsection Pairs | |
40 | @tpindex Pairs | |
41 | ||
42 | Pairs are used to combine two Scheme objects into one compound object. | |
43 | Hence the name: A pair stores a pair of objects. | |
44 | ||
45 | The data type @dfn{pair} is extremely important in Scheme, just like in | |
46 | any other Lisp dialect. The reason is that pairs are not only used to | |
47 | make two values available as one object, but that pairs are used for | |
48 | constructing lists of values. Because lists are so important in Scheme, | |
49 | they are described in a section of their own (@pxref{Lists}). | |
50 | ||
51 | Pairs can literally get entered in source code or at the REPL, in the | |
52 | so-called @dfn{dotted list} syntax. This syntax consists of an opening | |
53 | parentheses, the first element of the pair, a dot, the second element | |
54 | and a closing parentheses. The following example shows how a pair | |
55 | consisting of the two numbers 1 and 2, and a pair containing the symbols | |
56 | @code{foo} and @code{bar} can be entered. It is very important to write | |
57 | the whitespace before and after the dot, because otherwise the Scheme | |
58 | parser would not be able to figure out where to split the tokens. | |
59 | ||
60 | @lisp | |
61 | (1 . 2) | |
62 | (foo . bar) | |
63 | @end lisp | |
64 | ||
65 | But beware, if you want to try out these examples, you have to | |
66 | @dfn{quote} the expressions. More information about quotation is | |
51ee57a4 KR |
67 | available in the section @ref{Expression Syntax}. The correct way |
68 | to try these examples is as follows. | |
07d83abe MV |
69 | |
70 | @lisp | |
71 | '(1 . 2) | |
72 | @result{} | |
73 | (1 . 2) | |
74 | '(foo . bar) | |
75 | @result{} | |
76 | (foo . bar) | |
77 | @end lisp | |
78 | ||
79 | A new pair is made by calling the procedure @code{cons} with two | |
80 | arguments. Then the argument values are stored into a newly allocated | |
81 | pair, and the pair is returned. The name @code{cons} stands for | |
82 | "construct". Use the procedure @code{pair?} to test whether a | |
83 | given Scheme object is a pair or not. | |
84 | ||
85 | @rnindex cons | |
86 | @deffn {Scheme Procedure} cons x y | |
87 | @deffnx {C Function} scm_cons (x, y) | |
88 | Return a newly allocated pair whose car is @var{x} and whose | |
89 | cdr is @var{y}. The pair is guaranteed to be different (in the | |
90 | sense of @code{eq?}) from every previously existing object. | |
91 | @end deffn | |
92 | ||
93 | @rnindex pair? | |
94 | @deffn {Scheme Procedure} pair? x | |
95 | @deffnx {C Function} scm_pair_p (x) | |
96 | Return @code{#t} if @var{x} is a pair; otherwise return | |
97 | @code{#f}. | |
98 | @end deffn | |
99 | ||
7f4c83e3 MV |
100 | @deftypefn {C Function} int scm_is_pair (SCM x) |
101 | Return 1 when @var{x} is a pair; otherwise return 0. | |
102 | @end deftypefn | |
103 | ||
07d83abe MV |
104 | The two parts of a pair are traditionally called @dfn{car} and |
105 | @dfn{cdr}. They can be retrieved with procedures of the same name | |
106 | (@code{car} and @code{cdr}), and can be modified with the procedures | |
44cd5575 LC |
107 | @code{set-car!} and @code{set-cdr!}. |
108 | ||
109 | Since a very common operation in Scheme programs is to access the car of | |
110 | a car of a pair, or the car of the cdr of a pair, etc., the procedures | |
111 | called @code{caar}, @code{cadr} and so on are also predefined. However, | |
112 | using these procedures is often detrimental to readability, and | |
113 | error-prone. Thus, accessing the contents of a list is usually better | |
114 | achieved using pattern matching techniques (@pxref{Pattern Matching}). | |
07d83abe MV |
115 | |
116 | @rnindex car | |
117 | @rnindex cdr | |
118 | @deffn {Scheme Procedure} car pair | |
119 | @deffnx {Scheme Procedure} cdr pair | |
7f4c83e3 MV |
120 | @deffnx {C Function} scm_car (pair) |
121 | @deffnx {C Function} scm_cdr (pair) | |
07d83abe MV |
122 | Return the car or the cdr of @var{pair}, respectively. |
123 | @end deffn | |
124 | ||
35f957b2 MV |
125 | @deftypefn {C Macro} SCM SCM_CAR (SCM pair) |
126 | @deftypefnx {C Macro} SCM SCM_CDR (SCM pair) | |
127 | These two macros are the fastest way to access the car or cdr of a | |
128 | pair; they can be thought of as compiling into a single memory | |
129 | reference. | |
130 | ||
131 | These macros do no checking at all. The argument @var{pair} must be a | |
132 | valid pair. | |
133 | @end deftypefn | |
134 | ||
7f4c83e3 MV |
135 | @deffn {Scheme Procedure} cddr pair |
136 | @deffnx {Scheme Procedure} cdar pair | |
137 | @deffnx {Scheme Procedure} cadr pair | |
138 | @deffnx {Scheme Procedure} caar pair | |
139 | @deffnx {Scheme Procedure} cdddr pair | |
140 | @deffnx {Scheme Procedure} cddar pair | |
141 | @deffnx {Scheme Procedure} cdadr pair | |
142 | @deffnx {Scheme Procedure} cdaar pair | |
143 | @deffnx {Scheme Procedure} caddr pair | |
144 | @deffnx {Scheme Procedure} cadar pair | |
145 | @deffnx {Scheme Procedure} caadr pair | |
146 | @deffnx {Scheme Procedure} caaar pair | |
07d83abe | 147 | @deffnx {Scheme Procedure} cddddr pair |
7f4c83e3 MV |
148 | @deffnx {Scheme Procedure} cdddar pair |
149 | @deffnx {Scheme Procedure} cddadr pair | |
150 | @deffnx {Scheme Procedure} cddaar pair | |
151 | @deffnx {Scheme Procedure} cdaddr pair | |
152 | @deffnx {Scheme Procedure} cdadar pair | |
153 | @deffnx {Scheme Procedure} cdaadr pair | |
154 | @deffnx {Scheme Procedure} cdaaar pair | |
155 | @deffnx {Scheme Procedure} cadddr pair | |
156 | @deffnx {Scheme Procedure} caddar pair | |
157 | @deffnx {Scheme Procedure} cadadr pair | |
158 | @deffnx {Scheme Procedure} cadaar pair | |
159 | @deffnx {Scheme Procedure} caaddr pair | |
160 | @deffnx {Scheme Procedure} caadar pair | |
161 | @deffnx {Scheme Procedure} caaadr pair | |
162 | @deffnx {Scheme Procedure} caaaar pair | |
163 | @deffnx {C Function} scm_cddr (pair) | |
164 | @deffnx {C Function} scm_cdar (pair) | |
165 | @deffnx {C Function} scm_cadr (pair) | |
166 | @deffnx {C Function} scm_caar (pair) | |
167 | @deffnx {C Function} scm_cdddr (pair) | |
168 | @deffnx {C Function} scm_cddar (pair) | |
169 | @deffnx {C Function} scm_cdadr (pair) | |
170 | @deffnx {C Function} scm_cdaar (pair) | |
171 | @deffnx {C Function} scm_caddr (pair) | |
172 | @deffnx {C Function} scm_cadar (pair) | |
173 | @deffnx {C Function} scm_caadr (pair) | |
174 | @deffnx {C Function} scm_caaar (pair) | |
175 | @deffnx {C Function} scm_cddddr (pair) | |
176 | @deffnx {C Function} scm_cdddar (pair) | |
177 | @deffnx {C Function} scm_cddadr (pair) | |
178 | @deffnx {C Function} scm_cddaar (pair) | |
179 | @deffnx {C Function} scm_cdaddr (pair) | |
180 | @deffnx {C Function} scm_cdadar (pair) | |
181 | @deffnx {C Function} scm_cdaadr (pair) | |
182 | @deffnx {C Function} scm_cdaaar (pair) | |
183 | @deffnx {C Function} scm_cadddr (pair) | |
184 | @deffnx {C Function} scm_caddar (pair) | |
185 | @deffnx {C Function} scm_cadadr (pair) | |
186 | @deffnx {C Function} scm_cadaar (pair) | |
187 | @deffnx {C Function} scm_caaddr (pair) | |
188 | @deffnx {C Function} scm_caadar (pair) | |
189 | @deffnx {C Function} scm_caaadr (pair) | |
190 | @deffnx {C Function} scm_caaaar (pair) | |
07d83abe MV |
191 | These procedures are compositions of @code{car} and @code{cdr}, where |
192 | for example @code{caddr} could be defined by | |
193 | ||
194 | @lisp | |
195 | (define caddr (lambda (x) (car (cdr (cdr x))))) | |
196 | @end lisp | |
23f2b9a3 KR |
197 | |
198 | @code{cadr}, @code{caddr} and @code{cadddr} pick out the second, third | |
199 | or fourth elements of a list, respectively. SRFI-1 provides the same | |
200 | under the names @code{second}, @code{third} and @code{fourth} | |
201 | (@pxref{SRFI-1 Selectors}). | |
07d83abe MV |
202 | @end deffn |
203 | ||
204 | @rnindex set-car! | |
205 | @deffn {Scheme Procedure} set-car! pair value | |
206 | @deffnx {C Function} scm_set_car_x (pair, value) | |
207 | Stores @var{value} in the car field of @var{pair}. The value returned | |
208 | by @code{set-car!} is unspecified. | |
209 | @end deffn | |
210 | ||
211 | @rnindex set-cdr! | |
212 | @deffn {Scheme Procedure} set-cdr! pair value | |
213 | @deffnx {C Function} scm_set_cdr_x (pair, value) | |
214 | Stores @var{value} in the cdr field of @var{pair}. The value returned | |
215 | by @code{set-cdr!} is unspecified. | |
216 | @end deffn | |
217 | ||
218 | ||
219 | @node Lists | |
220 | @subsection Lists | |
221 | @tpindex Lists | |
222 | ||
223 | A very important data type in Scheme---as well as in all other Lisp | |
224 | dialects---is the data type @dfn{list}.@footnote{Strictly speaking, | |
225 | Scheme does not have a real datatype @dfn{list}. Lists are made up of | |
226 | @dfn{chained pairs}, and only exist by definition---a list is a chain | |
227 | of pairs which looks like a list.} | |
228 | ||
229 | This is the short definition of what a list is: | |
230 | ||
231 | @itemize @bullet | |
232 | @item | |
233 | Either the empty list @code{()}, | |
234 | ||
235 | @item | |
236 | or a pair which has a list in its cdr. | |
237 | @end itemize | |
238 | ||
239 | @c FIXME::martin: Describe the pair chaining in more detail. | |
240 | ||
241 | @c FIXME::martin: What is a proper, what an improper list? | |
242 | @c What is a circular list? | |
243 | ||
244 | @c FIXME::martin: Maybe steal some graphics from the Elisp reference | |
245 | @c manual? | |
246 | ||
247 | @menu | |
248 | * List Syntax:: Writing literal lists. | |
249 | * List Predicates:: Testing lists. | |
250 | * List Constructors:: Creating new lists. | |
251 | * List Selection:: Selecting from lists, getting their length. | |
252 | * Append/Reverse:: Appending and reversing lists. | |
253 | * List Modification:: Modifying existing lists. | |
254 | * List Searching:: Searching for list elements | |
255 | * List Mapping:: Applying procedures to lists. | |
256 | @end menu | |
257 | ||
258 | @node List Syntax | |
259 | @subsubsection List Read Syntax | |
260 | ||
261 | The syntax for lists is an opening parentheses, then all the elements of | |
262 | the list (separated by whitespace) and finally a closing | |
263 | parentheses.@footnote{Note that there is no separation character between | |
264 | the list elements, like a comma or a semicolon.}. | |
265 | ||
266 | @lisp | |
267 | (1 2 3) ; @r{a list of the numbers 1, 2 and 3} | |
268 | ("foo" bar 3.1415) ; @r{a string, a symbol and a real number} | |
269 | () ; @r{the empty list} | |
270 | @end lisp | |
271 | ||
272 | The last example needs a bit more explanation. A list with no elements, | |
273 | called the @dfn{empty list}, is special in some ways. It is used for | |
274 | terminating lists by storing it into the cdr of the last pair that makes | |
275 | up a list. An example will clear that up: | |
276 | ||
277 | @lisp | |
278 | (car '(1)) | |
279 | @result{} | |
280 | 1 | |
281 | (cdr '(1)) | |
282 | @result{} | |
283 | () | |
284 | @end lisp | |
285 | ||
51ee57a4 KR |
286 | This example also shows that lists have to be quoted when written |
287 | (@pxref{Expression Syntax}), because they would otherwise be | |
288 | mistakingly taken as procedure applications (@pxref{Simple | |
289 | Invocation}). | |
07d83abe MV |
290 | |
291 | ||
292 | @node List Predicates | |
293 | @subsubsection List Predicates | |
294 | ||
295 | Often it is useful to test whether a given Scheme object is a list or | |
296 | not. List-processing procedures could use this information to test | |
297 | whether their input is valid, or they could do different things | |
298 | depending on the datatype of their arguments. | |
299 | ||
300 | @rnindex list? | |
301 | @deffn {Scheme Procedure} list? x | |
302 | @deffnx {C Function} scm_list_p (x) | |
a4b4fbbd | 303 | Return @code{#t} if @var{x} is a proper list, else @code{#f}. |
07d83abe MV |
304 | @end deffn |
305 | ||
306 | The predicate @code{null?} is often used in list-processing code to | |
307 | tell whether a given list has run out of elements. That is, a loop | |
308 | somehow deals with the elements of a list until the list satisfies | |
309 | @code{null?}. Then, the algorithm terminates. | |
310 | ||
311 | @rnindex null? | |
312 | @deffn {Scheme Procedure} null? x | |
313 | @deffnx {C Function} scm_null_p (x) | |
a4b4fbbd | 314 | Return @code{#t} if @var{x} is the empty list, else @code{#f}. |
07d83abe MV |
315 | @end deffn |
316 | ||
7f4c83e3 MV |
317 | @deftypefn {C Function} int scm_is_null (SCM x) |
318 | Return 1 when @var{x} is the empty list; otherwise return 0. | |
319 | @end deftypefn | |
320 | ||
321 | ||
07d83abe MV |
322 | @node List Constructors |
323 | @subsubsection List Constructors | |
324 | ||
325 | This section describes the procedures for constructing new lists. | |
326 | @code{list} simply returns a list where the elements are the arguments, | |
327 | @code{cons*} is similar, but the last argument is stored in the cdr of | |
328 | the last pair of the list. | |
329 | ||
330 | @c C Function scm_list(rest) used to be documented here, but it's a | |
331 | @c no-op since it does nothing but return the list the caller must | |
332 | @c have already created. | |
333 | @c | |
df0a1002 | 334 | @deffn {Scheme Procedure} list elem @dots{} |
07d83abe MV |
335 | @deffnx {C Function} scm_list_1 (elem1) |
336 | @deffnx {C Function} scm_list_2 (elem1, elem2) | |
337 | @deffnx {C Function} scm_list_3 (elem1, elem2, elem3) | |
338 | @deffnx {C Function} scm_list_4 (elem1, elem2, elem3, elem4) | |
339 | @deffnx {C Function} scm_list_5 (elem1, elem2, elem3, elem4, elem5) | |
340 | @deffnx {C Function} scm_list_n (elem1, @dots{}, elemN, @nicode{SCM_UNDEFINED}) | |
341 | @rnindex list | |
df0a1002 | 342 | Return a new list containing elements @var{elem} @enddots{}. |
07d83abe MV |
343 | |
344 | @code{scm_list_n} takes a variable number of arguments, terminated by | |
345 | the special @code{SCM_UNDEFINED}. That final @code{SCM_UNDEFINED} is | |
df0a1002 | 346 | not included in the list. None of @var{elem} @dots{} can |
07d83abe MV |
347 | themselves be @code{SCM_UNDEFINED}, or @code{scm_list_n} will |
348 | terminate at that point. | |
349 | @end deffn | |
350 | ||
351 | @c C Function scm_cons_star(arg1,rest) used to be documented here, | |
352 | @c but it's not really a useful interface, since it expects the | |
353 | @c caller to have already consed up all but the first argument | |
354 | @c already. | |
355 | @c | |
356 | @deffn {Scheme Procedure} cons* arg1 arg2 @dots{} | |
357 | Like @code{list}, but the last arg provides the tail of the | |
358 | constructed list, returning @code{(cons @var{arg1} (cons | |
359 | @var{arg2} (cons @dots{} @var{argn})))}. Requires at least one | |
360 | argument. If given one argument, that argument is returned as | |
361 | result. This function is called @code{list*} in some other | |
362 | Schemes and in Common LISP. | |
363 | @end deffn | |
364 | ||
365 | @deffn {Scheme Procedure} list-copy lst | |
366 | @deffnx {C Function} scm_list_copy (lst) | |
367 | Return a (newly-created) copy of @var{lst}. | |
368 | @end deffn | |
369 | ||
370 | @deffn {Scheme Procedure} make-list n [init] | |
371 | Create a list containing of @var{n} elements, where each element is | |
372 | initialized to @var{init}. @var{init} defaults to the empty list | |
373 | @code{()} if not given. | |
374 | @end deffn | |
375 | ||
376 | Note that @code{list-copy} only makes a copy of the pairs which make up | |
377 | the spine of the lists. The list elements are not copied, which means | |
378 | that modifying the elements of the new list also modifies the elements | |
379 | of the old list. On the other hand, applying procedures like | |
380 | @code{set-cdr!} or @code{delv!} to the new list will not alter the old | |
381 | list. If you also need to copy the list elements (making a deep copy), | |
382 | use the procedure @code{copy-tree} (@pxref{Copying}). | |
383 | ||
384 | @node List Selection | |
385 | @subsubsection List Selection | |
386 | ||
387 | These procedures are used to get some information about a list, or to | |
388 | retrieve one or more elements of a list. | |
389 | ||
390 | @rnindex length | |
391 | @deffn {Scheme Procedure} length lst | |
392 | @deffnx {C Function} scm_length (lst) | |
393 | Return the number of elements in list @var{lst}. | |
394 | @end deffn | |
395 | ||
396 | @deffn {Scheme Procedure} last-pair lst | |
397 | @deffnx {C Function} scm_last_pair (lst) | |
cdf1ad3b | 398 | Return the last pair in @var{lst}, signalling an error if |
07d83abe MV |
399 | @var{lst} is circular. |
400 | @end deffn | |
401 | ||
402 | @rnindex list-ref | |
403 | @deffn {Scheme Procedure} list-ref list k | |
404 | @deffnx {C Function} scm_list_ref (list, k) | |
405 | Return the @var{k}th element from @var{list}. | |
406 | @end deffn | |
407 | ||
408 | @rnindex list-tail | |
409 | @deffn {Scheme Procedure} list-tail lst k | |
410 | @deffnx {Scheme Procedure} list-cdr-ref lst k | |
411 | @deffnx {C Function} scm_list_tail (lst, k) | |
412 | Return the "tail" of @var{lst} beginning with its @var{k}th element. | |
413 | The first element of the list is considered to be element 0. | |
414 | ||
415 | @code{list-tail} and @code{list-cdr-ref} are identical. It may help to | |
416 | think of @code{list-cdr-ref} as accessing the @var{k}th cdr of the list, | |
417 | or returning the results of cdring @var{k} times down @var{lst}. | |
418 | @end deffn | |
419 | ||
420 | @deffn {Scheme Procedure} list-head lst k | |
421 | @deffnx {C Function} scm_list_head (lst, k) | |
422 | Copy the first @var{k} elements from @var{lst} into a new list, and | |
423 | return it. | |
424 | @end deffn | |
425 | ||
426 | @node Append/Reverse | |
427 | @subsubsection Append and Reverse | |
428 | ||
429 | @code{append} and @code{append!} are used to concatenate two or more | |
430 | lists in order to form a new list. @code{reverse} and @code{reverse!} | |
431 | return lists with the same elements as their arguments, but in reverse | |
432 | order. The procedure variants with an @code{!} directly modify the | |
433 | pairs which form the list, whereas the other procedures create new | |
434 | pairs. This is why you should be careful when using the side-effecting | |
435 | variants. | |
436 | ||
437 | @rnindex append | |
df0a1002 BT |
438 | @deffn {Scheme Procedure} append lst @dots{} obj |
439 | @deffnx {Scheme Procedure} append | |
440 | @deffnx {Scheme Procedure} append! lst @dots{} obj | |
441 | @deffnx {Scheme Procedure} append! | |
07d83abe MV |
442 | @deffnx {C Function} scm_append (lstlst) |
443 | @deffnx {C Function} scm_append_x (lstlst) | |
df0a1002 BT |
444 | Return a list comprising all the elements of lists @var{lst} @dots{} |
445 | @var{obj}. If called with no arguments, return the empty list. | |
07d83abe MV |
446 | |
447 | @lisp | |
448 | (append '(x) '(y)) @result{} (x y) | |
449 | (append '(a) '(b c d)) @result{} (a b c d) | |
450 | (append '(a (b)) '((c))) @result{} (a (b) (c)) | |
451 | @end lisp | |
452 | ||
df0a1002 | 453 | The last argument @var{obj} may actually be any object; an improper |
07d83abe MV |
454 | list results if the last argument is not a proper list. |
455 | ||
456 | @lisp | |
457 | (append '(a b) '(c . d)) @result{} (a b c . d) | |
458 | (append '() 'a) @result{} a | |
459 | @end lisp | |
460 | ||
461 | @code{append} doesn't modify the given lists, but the return may share | |
b57162c3 MW |
462 | structure with the final @var{obj}. @code{append!} is permitted, but |
463 | not required, to modify the given lists to form its return. | |
07d83abe MV |
464 | |
465 | For @code{scm_append} and @code{scm_append_x}, @var{lstlst} is a list | |
df0a1002 | 466 | of the list operands @var{lst} @dots{} @var{obj}. That @var{lstlst} |
07d83abe MV |
467 | itself is not modified or used in the return. |
468 | @end deffn | |
469 | ||
470 | @rnindex reverse | |
471 | @deffn {Scheme Procedure} reverse lst | |
472 | @deffnx {Scheme Procedure} reverse! lst [newtail] | |
473 | @deffnx {C Function} scm_reverse (lst) | |
474 | @deffnx {C Function} scm_reverse_x (lst, newtail) | |
475 | Return a list comprising the elements of @var{lst}, in reverse order. | |
476 | ||
b57162c3 MW |
477 | @code{reverse} constructs a new list. @code{reverse!} is permitted, but |
478 | not required, to modify @var{lst} in constructing its return. | |
07d83abe | 479 | |
72b3aa56 | 480 | For @code{reverse!}, the optional @var{newtail} is appended to the |
07d83abe MV |
481 | result. @var{newtail} isn't reversed, it simply becomes the list |
482 | tail. For @code{scm_reverse_x}, the @var{newtail} parameter is | |
483 | mandatory, but can be @code{SCM_EOL} if no further tail is required. | |
484 | @end deffn | |
485 | ||
486 | @node List Modification | |
487 | @subsubsection List Modification | |
488 | ||
489 | The following procedures modify an existing list, either by changing | |
490 | elements of the list, or by changing the list structure itself. | |
491 | ||
492 | @deffn {Scheme Procedure} list-set! list k val | |
493 | @deffnx {C Function} scm_list_set_x (list, k, val) | |
494 | Set the @var{k}th element of @var{list} to @var{val}. | |
495 | @end deffn | |
496 | ||
497 | @deffn {Scheme Procedure} list-cdr-set! list k val | |
498 | @deffnx {C Function} scm_list_cdr_set_x (list, k, val) | |
499 | Set the @var{k}th cdr of @var{list} to @var{val}. | |
500 | @end deffn | |
501 | ||
502 | @deffn {Scheme Procedure} delq item lst | |
503 | @deffnx {C Function} scm_delq (item, lst) | |
504 | Return a newly-created copy of @var{lst} with elements | |
505 | @code{eq?} to @var{item} removed. This procedure mirrors | |
506 | @code{memq}: @code{delq} compares elements of @var{lst} against | |
507 | @var{item} with @code{eq?}. | |
508 | @end deffn | |
509 | ||
510 | @deffn {Scheme Procedure} delv item lst | |
511 | @deffnx {C Function} scm_delv (item, lst) | |
512 | Return a newly-created copy of @var{lst} with elements | |
23f2b9a3 | 513 | @code{eqv?} to @var{item} removed. This procedure mirrors |
07d83abe MV |
514 | @code{memv}: @code{delv} compares elements of @var{lst} against |
515 | @var{item} with @code{eqv?}. | |
516 | @end deffn | |
517 | ||
518 | @deffn {Scheme Procedure} delete item lst | |
519 | @deffnx {C Function} scm_delete (item, lst) | |
520 | Return a newly-created copy of @var{lst} with elements | |
23f2b9a3 | 521 | @code{equal?} to @var{item} removed. This procedure mirrors |
07d83abe MV |
522 | @code{member}: @code{delete} compares elements of @var{lst} |
523 | against @var{item} with @code{equal?}. | |
23f2b9a3 KR |
524 | |
525 | See also SRFI-1 which has an extended @code{delete} (@ref{SRFI-1 | |
526 | Deleting}), and also an @code{lset-difference} which can delete | |
527 | multiple @var{item}s in one call (@ref{SRFI-1 Set Operations}). | |
07d83abe MV |
528 | @end deffn |
529 | ||
530 | @deffn {Scheme Procedure} delq! item lst | |
531 | @deffnx {Scheme Procedure} delv! item lst | |
532 | @deffnx {Scheme Procedure} delete! item lst | |
533 | @deffnx {C Function} scm_delq_x (item, lst) | |
534 | @deffnx {C Function} scm_delv_x (item, lst) | |
535 | @deffnx {C Function} scm_delete_x (item, lst) | |
536 | These procedures are destructive versions of @code{delq}, @code{delv} | |
537 | and @code{delete}: they modify the pointers in the existing @var{lst} | |
538 | rather than creating a new list. Caveat evaluator: Like other | |
539 | destructive list functions, these functions cannot modify the binding of | |
540 | @var{lst}, and so cannot be used to delete the first element of | |
541 | @var{lst} destructively. | |
542 | @end deffn | |
543 | ||
544 | @deffn {Scheme Procedure} delq1! item lst | |
545 | @deffnx {C Function} scm_delq1_x (item, lst) | |
546 | Like @code{delq!}, but only deletes the first occurrence of | |
547 | @var{item} from @var{lst}. Tests for equality using | |
548 | @code{eq?}. See also @code{delv1!} and @code{delete1!}. | |
549 | @end deffn | |
550 | ||
551 | @deffn {Scheme Procedure} delv1! item lst | |
552 | @deffnx {C Function} scm_delv1_x (item, lst) | |
553 | Like @code{delv!}, but only deletes the first occurrence of | |
554 | @var{item} from @var{lst}. Tests for equality using | |
555 | @code{eqv?}. See also @code{delq1!} and @code{delete1!}. | |
556 | @end deffn | |
557 | ||
558 | @deffn {Scheme Procedure} delete1! item lst | |
559 | @deffnx {C Function} scm_delete1_x (item, lst) | |
560 | Like @code{delete!}, but only deletes the first occurrence of | |
561 | @var{item} from @var{lst}. Tests for equality using | |
562 | @code{equal?}. See also @code{delq1!} and @code{delv1!}. | |
563 | @end deffn | |
564 | ||
565 | @deffn {Scheme Procedure} filter pred lst | |
566 | @deffnx {Scheme Procedure} filter! pred lst | |
567 | Return a list containing all elements from @var{lst} which satisfy the | |
568 | predicate @var{pred}. The elements in the result list have the same | |
569 | order as in @var{lst}. The order in which @var{pred} is applied to | |
570 | the list elements is not specified. | |
571 | ||
d8e49e6b KR |
572 | @code{filter} does not change @var{lst}, but the result may share a |
573 | tail with it. @code{filter!} may modify @var{lst} to construct its | |
574 | return. | |
07d83abe MV |
575 | @end deffn |
576 | ||
577 | @node List Searching | |
578 | @subsubsection List Searching | |
579 | ||
580 | The following procedures search lists for particular elements. They use | |
581 | different comparison predicates for comparing list elements with the | |
582 | object to be searched. When they fail, they return @code{#f}, otherwise | |
583 | they return the sublist whose car is equal to the search object, where | |
584 | equality depends on the equality predicate used. | |
585 | ||
586 | @rnindex memq | |
587 | @deffn {Scheme Procedure} memq x lst | |
588 | @deffnx {C Function} scm_memq (x, lst) | |
589 | Return the first sublist of @var{lst} whose car is @code{eq?} | |
590 | to @var{x} where the sublists of @var{lst} are the non-empty | |
591 | lists returned by @code{(list-tail @var{lst} @var{k})} for | |
592 | @var{k} less than the length of @var{lst}. If @var{x} does not | |
593 | occur in @var{lst}, then @code{#f} (not the empty list) is | |
594 | returned. | |
595 | @end deffn | |
596 | ||
597 | @rnindex memv | |
598 | @deffn {Scheme Procedure} memv x lst | |
599 | @deffnx {C Function} scm_memv (x, lst) | |
600 | Return the first sublist of @var{lst} whose car is @code{eqv?} | |
601 | to @var{x} where the sublists of @var{lst} are the non-empty | |
602 | lists returned by @code{(list-tail @var{lst} @var{k})} for | |
603 | @var{k} less than the length of @var{lst}. If @var{x} does not | |
604 | occur in @var{lst}, then @code{#f} (not the empty list) is | |
605 | returned. | |
606 | @end deffn | |
607 | ||
608 | @rnindex member | |
609 | @deffn {Scheme Procedure} member x lst | |
610 | @deffnx {C Function} scm_member (x, lst) | |
611 | Return the first sublist of @var{lst} whose car is | |
612 | @code{equal?} to @var{x} where the sublists of @var{lst} are | |
613 | the non-empty lists returned by @code{(list-tail @var{lst} | |
614 | @var{k})} for @var{k} less than the length of @var{lst}. If | |
615 | @var{x} does not occur in @var{lst}, then @code{#f} (not the | |
616 | empty list) is returned. | |
23f2b9a3 KR |
617 | |
618 | See also SRFI-1 which has an extended @code{member} function | |
619 | (@ref{SRFI-1 Searching}). | |
07d83abe MV |
620 | @end deffn |
621 | ||
622 | ||
623 | @node List Mapping | |
624 | @subsubsection List Mapping | |
625 | ||
626 | List processing is very convenient in Scheme because the process of | |
627 | iterating over the elements of a list can be highly abstracted. The | |
628 | procedures in this section are the most basic iterating procedures for | |
629 | lists. They take a procedure and one or more lists as arguments, and | |
630 | apply the procedure to each element of the list. They differ in their | |
631 | return value. | |
632 | ||
633 | @rnindex map | |
634 | @c begin (texi-doc-string "guile" "map") | |
635 | @deffn {Scheme Procedure} map proc arg1 arg2 @dots{} | |
636 | @deffnx {Scheme Procedure} map-in-order proc arg1 arg2 @dots{} | |
637 | @deffnx {C Function} scm_map (proc, arg1, args) | |
638 | Apply @var{proc} to each element of the list @var{arg1} (if only two | |
639 | arguments are given), or to the corresponding elements of the argument | |
640 | lists (if more than two arguments are given). The result(s) of the | |
641 | procedure applications are saved and returned in a list. For | |
642 | @code{map}, the order of procedure applications is not specified, | |
643 | @code{map-in-order} applies the procedure from left to right to the list | |
644 | elements. | |
645 | @end deffn | |
646 | ||
647 | @rnindex for-each | |
648 | @c begin (texi-doc-string "guile" "for-each") | |
649 | @deffn {Scheme Procedure} for-each proc arg1 arg2 @dots{} | |
650 | Like @code{map}, but the procedure is always applied from left to right, | |
651 | and the result(s) of the procedure applications are thrown away. The | |
652 | return value is not specified. | |
653 | @end deffn | |
654 | ||
23f2b9a3 KR |
655 | See also SRFI-1 which extends these functions to take lists of unequal |
656 | lengths (@ref{SRFI-1 Fold and Map}). | |
07d83abe MV |
657 | |
658 | @node Vectors | |
659 | @subsection Vectors | |
660 | @tpindex Vectors | |
661 | ||
662 | Vectors are sequences of Scheme objects. Unlike lists, the length of a | |
663 | vector, once the vector is created, cannot be changed. The advantage of | |
664 | vectors over lists is that the time required to access one element of a vector | |
665 | given its @dfn{position} (synonymous with @dfn{index}), a zero-origin number, | |
666 | is constant, whereas lists have an access time linear to the position of the | |
667 | accessed element in the list. | |
668 | ||
e6b226b9 MV |
669 | Vectors can contain any kind of Scheme object; it is even possible to |
670 | have different types of objects in the same vector. For vectors | |
671 | containing vectors, you may wish to use arrays, instead. Note, too, | |
52d28fc2 MV |
672 | that vectors are the special case of one dimensional non-uniform arrays |
673 | and that most array procedures operate happily on vectors | |
01e6d0ec MV |
674 | (@pxref{Arrays}). |
675 | ||
2b509a2e MW |
676 | Also see @ref{SRFI-43}, for a comprehensive vector library. |
677 | ||
07d83abe MV |
678 | @menu |
679 | * Vector Syntax:: Read syntax for vectors. | |
680 | * Vector Creation:: Dynamic vector creation and validation. | |
681 | * Vector Accessors:: Accessing and modifying vector contents. | |
52d28fc2 | 682 | * Vector Accessing from C:: Ways to work with vectors from C. |
27219b32 | 683 | * Uniform Numeric Vectors:: Vectors of unboxed numeric values. |
07d83abe MV |
684 | @end menu |
685 | ||
686 | ||
687 | @node Vector Syntax | |
688 | @subsubsection Read Syntax for Vectors | |
689 | ||
690 | Vectors can literally be entered in source code, just like strings, | |
691 | characters or some of the other data types. The read syntax for vectors | |
692 | is as follows: A sharp sign (@code{#}), followed by an opening | |
693 | parentheses, all elements of the vector in their respective read syntax, | |
c9e3266c IP |
694 | and finally a closing parentheses. Like strings, vectors do not have to |
695 | be quoted. | |
696 | ||
697 | The following are examples of the read syntax for vectors; where the | |
698 | first vector only contains numbers and the second three different object | |
699 | types: a string, a symbol and a number in hexadecimal notation. | |
07d83abe MV |
700 | |
701 | @lisp | |
702 | #(1 2 3) | |
703 | #("Hello" foo #xdeadbeef) | |
704 | @end lisp | |
705 | ||
07d83abe MV |
706 | @node Vector Creation |
707 | @subsubsection Dynamic Vector Creation and Validation | |
708 | ||
709 | Instead of creating a vector implicitly by using the read syntax just | |
710 | described, you can create a vector dynamically by calling one of the | |
711 | @code{vector} and @code{list->vector} primitives with the list of Scheme | |
712 | values that you want to place into a vector. The size of the vector | |
713 | thus created is determined implicitly by the number of arguments given. | |
714 | ||
715 | @rnindex vector | |
716 | @rnindex list->vector | |
df0a1002 | 717 | @deffn {Scheme Procedure} vector arg @dots{} |
07d83abe MV |
718 | @deffnx {Scheme Procedure} list->vector l |
719 | @deffnx {C Function} scm_vector (l) | |
720 | Return a newly allocated vector composed of the | |
721 | given arguments. Analogous to @code{list}. | |
722 | ||
723 | @lisp | |
724 | (vector 'a 'b 'c) @result{} #(a b c) | |
725 | @end lisp | |
726 | @end deffn | |
727 | ||
07d83abe MV |
728 | The inverse operation is @code{vector->list}: |
729 | ||
730 | @rnindex vector->list | |
731 | @deffn {Scheme Procedure} vector->list v | |
732 | @deffnx {C Function} scm_vector_to_list (v) | |
733 | Return a newly allocated list composed of the elements of @var{v}. | |
734 | ||
735 | @lisp | |
c9e3266c | 736 | (vector->list #(dah dah didah)) @result{} (dah dah didah) |
07d83abe MV |
737 | (list->vector '(dididit dah)) @result{} #(dididit dah) |
738 | @end lisp | |
739 | @end deffn | |
740 | ||
741 | To allocate a vector with an explicitly specified size, use | |
742 | @code{make-vector}. With this primitive you can also specify an initial | |
743 | value for the vector elements (the same value for all elements, that | |
744 | is): | |
745 | ||
746 | @rnindex make-vector | |
61eed960 MV |
747 | @deffn {Scheme Procedure} make-vector len [fill] |
748 | @deffnx {C Function} scm_make_vector (len, fill) | |
749 | Return a newly allocated vector of @var{len} elements. If a | |
07d83abe MV |
750 | second argument is given, then each position is initialized to |
751 | @var{fill}. Otherwise the initial contents of each position is | |
752 | unspecified. | |
753 | @end deffn | |
754 | ||
61eed960 MV |
755 | @deftypefn {C Function} SCM scm_c_make_vector (size_t k, SCM fill) |
756 | Like @code{scm_make_vector}, but the length is given as a @code{size_t}. | |
757 | @end deftypefn | |
758 | ||
07d83abe MV |
759 | To check whether an arbitrary Scheme value @emph{is} a vector, use the |
760 | @code{vector?} primitive: | |
761 | ||
762 | @rnindex vector? | |
763 | @deffn {Scheme Procedure} vector? obj | |
764 | @deffnx {C Function} scm_vector_p (obj) | |
765 | Return @code{#t} if @var{obj} is a vector, otherwise return | |
766 | @code{#f}. | |
767 | @end deffn | |
768 | ||
61eed960 MV |
769 | @deftypefn {C Function} int scm_is_vector (SCM obj) |
770 | Return non-zero when @var{obj} is a vector, otherwise return | |
771 | @code{zero}. | |
772 | @end deftypefn | |
07d83abe MV |
773 | |
774 | @node Vector Accessors | |
775 | @subsubsection Accessing and Modifying Vector Contents | |
776 | ||
777 | @code{vector-length} and @code{vector-ref} return information about a | |
778 | given vector, respectively its size and the elements that are contained | |
779 | in the vector. | |
780 | ||
781 | @rnindex vector-length | |
782 | @deffn {Scheme Procedure} vector-length vector | |
5f6ffd66 | 783 | @deffnx {C Function} scm_vector_length (vector) |
07d83abe MV |
784 | Return the number of elements in @var{vector} as an exact integer. |
785 | @end deffn | |
786 | ||
64de6db5 BT |
787 | @deftypefn {C Function} size_t scm_c_vector_length (SCM vec) |
788 | Return the number of elements in @var{vec} as a @code{size_t}. | |
61eed960 MV |
789 | @end deftypefn |
790 | ||
07d83abe | 791 | @rnindex vector-ref |
64de6db5 | 792 | @deffn {Scheme Procedure} vector-ref vec k |
5f6ffd66 | 793 | @deffnx {C Function} scm_vector_ref (vec, k) |
64de6db5 BT |
794 | Return the contents of position @var{k} of @var{vec}. |
795 | @var{k} must be a valid index of @var{vec}. | |
07d83abe | 796 | @lisp |
c9e3266c IP |
797 | (vector-ref #(1 1 2 3 5 8 13 21) 5) @result{} 8 |
798 | (vector-ref #(1 1 2 3 5 8 13 21) | |
07d83abe MV |
799 | (let ((i (round (* 2 (acos -1))))) |
800 | (if (inexact? i) | |
801 | (inexact->exact i) | |
802 | i))) @result{} 13 | |
803 | @end lisp | |
804 | @end deffn | |
805 | ||
64de6db5 | 806 | @deftypefn {C Function} SCM scm_c_vector_ref (SCM vec, size_t k) |
52d28fc2 | 807 | Return the contents of position @var{k} (a @code{size_t}) of |
64de6db5 | 808 | @var{vec}. |
61eed960 MV |
809 | @end deftypefn |
810 | ||
07d83abe MV |
811 | A vector created by one of the dynamic vector constructor procedures |
812 | (@pxref{Vector Creation}) can be modified using the following | |
813 | procedures. | |
814 | ||
815 | @emph{NOTE:} According to R5RS, it is an error to use any of these | |
816 | procedures on a literally read vector, because such vectors should be | |
817 | considered as constants. Currently, however, Guile does not detect this | |
818 | error. | |
819 | ||
820 | @rnindex vector-set! | |
64de6db5 | 821 | @deffn {Scheme Procedure} vector-set! vec k obj |
5f6ffd66 | 822 | @deffnx {C Function} scm_vector_set_x (vec, k, obj) |
64de6db5 BT |
823 | Store @var{obj} in position @var{k} of @var{vec}. |
824 | @var{k} must be a valid index of @var{vec}. | |
07d83abe MV |
825 | The value returned by @samp{vector-set!} is unspecified. |
826 | @lisp | |
827 | (let ((vec (vector 0 '(2 2 2 2) "Anna"))) | |
828 | (vector-set! vec 1 '("Sue" "Sue")) | |
829 | vec) @result{} #(0 ("Sue" "Sue") "Anna") | |
830 | @end lisp | |
831 | @end deffn | |
832 | ||
64de6db5 BT |
833 | @deftypefn {C Function} void scm_c_vector_set_x (SCM vec, size_t k, SCM obj) |
834 | Store @var{obj} in position @var{k} (a @code{size_t}) of @var{vec}. | |
61eed960 MV |
835 | @end deftypefn |
836 | ||
07d83abe | 837 | @rnindex vector-fill! |
64de6db5 BT |
838 | @deffn {Scheme Procedure} vector-fill! vec fill |
839 | @deffnx {C Function} scm_vector_fill_x (vec, fill) | |
840 | Store @var{fill} in every position of @var{vec}. The value | |
07d83abe MV |
841 | returned by @code{vector-fill!} is unspecified. |
842 | @end deffn | |
843 | ||
673ba2da MV |
844 | @deffn {Scheme Procedure} vector-copy vec |
845 | @deffnx {C Function} scm_vector_copy (vec) | |
846 | Return a copy of @var{vec}. | |
847 | @end deffn | |
848 | ||
07d83abe MV |
849 | @deffn {Scheme Procedure} vector-move-left! vec1 start1 end1 vec2 start2 |
850 | @deffnx {C Function} scm_vector_move_left_x (vec1, start1, end1, vec2, start2) | |
851 | Copy elements from @var{vec1}, positions @var{start1} to @var{end1}, | |
852 | to @var{vec2} starting at position @var{start2}. @var{start1} and | |
853 | @var{start2} are inclusive indices; @var{end1} is exclusive. | |
854 | ||
855 | @code{vector-move-left!} copies elements in leftmost order. | |
856 | Therefore, in the case where @var{vec1} and @var{vec2} refer to the | |
857 | same vector, @code{vector-move-left!} is usually appropriate when | |
858 | @var{start1} is greater than @var{start2}. | |
859 | @end deffn | |
860 | ||
861 | @deffn {Scheme Procedure} vector-move-right! vec1 start1 end1 vec2 start2 | |
862 | @deffnx {C Function} scm_vector_move_right_x (vec1, start1, end1, vec2, start2) | |
863 | Copy elements from @var{vec1}, positions @var{start1} to @var{end1}, | |
864 | to @var{vec2} starting at position @var{start2}. @var{start1} and | |
865 | @var{start2} are inclusive indices; @var{end1} is exclusive. | |
866 | ||
867 | @code{vector-move-right!} copies elements in rightmost order. | |
868 | Therefore, in the case where @var{vec1} and @var{vec2} refer to the | |
869 | same vector, @code{vector-move-right!} is usually appropriate when | |
870 | @var{start1} is less than @var{start2}. | |
871 | @end deffn | |
872 | ||
52d28fc2 MV |
873 | @node Vector Accessing from C |
874 | @subsubsection Vector Accessing from C | |
01e6d0ec | 875 | |
52d28fc2 MV |
876 | A vector can be read and modified from C with the functions |
877 | @code{scm_c_vector_ref} and @code{scm_c_vector_set_x}, for example. In | |
878 | addition to these functions, there are two more ways to access vectors | |
879 | from C that might be more efficient in certain situations: you can | |
880 | restrict yourself to @dfn{simple vectors} and then use the very fast | |
881 | @emph{simple vector macros}; or you can use the very general framework | |
882 | for accessing all kinds of arrays (@pxref{Accessing Arrays from C}), | |
883 | which is more verbose, but can deal efficiently with all kinds of | |
86ccc354 MV |
884 | vectors (and arrays). For vectors, you can use the |
885 | @code{scm_vector_elements} and @code{scm_vector_writable_elements} | |
886 | functions as shortcuts. | |
52d28fc2 MV |
887 | |
888 | @deftypefn {C Function} int scm_is_simple_vector (SCM obj) | |
889 | Return non-zero if @var{obj} is a simple vector, else return zero. A | |
890 | simple vector is a vector that can be used with the @code{SCM_SIMPLE_*} | |
891 | macros below. | |
01e6d0ec | 892 | |
52d28fc2 MV |
893 | The following functions are guaranteed to return simple vectors: |
894 | @code{scm_make_vector}, @code{scm_c_make_vector}, @code{scm_vector}, | |
895 | @code{scm_list_to_vector}. | |
01e6d0ec MV |
896 | @end deftypefn |
897 | ||
52d28fc2 MV |
898 | @deftypefn {C Macro} size_t SCM_SIMPLE_VECTOR_LENGTH (SCM vec) |
899 | Evaluates to the length of the simple vector @var{vec}. No type | |
900 | checking is done. | |
01e6d0ec MV |
901 | @end deftypefn |
902 | ||
52d28fc2 MV |
903 | @deftypefn {C Macro} SCM SCM_SIMPLE_VECTOR_REF (SCM vec, size_t idx) |
904 | Evaluates to the element at position @var{idx} in the simple vector | |
905 | @var{vec}. No type or range checking is done. | |
906 | @end deftypefn | |
01e6d0ec | 907 | |
1b09b607 | 908 | @deftypefn {C Macro} void SCM_SIMPLE_VECTOR_SET (SCM vec, size_t idx, SCM val) |
52d28fc2 MV |
909 | Sets the element at position @var{idx} in the simple vector |
910 | @var{vec} to @var{val}. No type or range checking is done. | |
01e6d0ec MV |
911 | @end deftypefn |
912 | ||
d1f9e107 | 913 | @deftypefn {C Function} {const SCM *} scm_vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp) |
d98e8fc1 | 914 | Acquire a handle for the vector @var{vec} and return a pointer to the |
52d28fc2 | 915 | elements of it. This pointer can only be used to read the elements of |
86ccc354 | 916 | @var{vec}. When @var{vec} is not a vector, an error is signaled. The |
ecb87335 | 917 | handle must eventually be released with |
86ccc354 | 918 | @code{scm_array_handle_release}. |
52d28fc2 MV |
919 | |
920 | The variables pointed to by @var{lenp} and @var{incp} are filled with | |
d34bd7d4 MV |
921 | the number of elements of the vector and the increment (number of |
922 | elements) between successive elements, respectively. Successive | |
923 | elements of @var{vec} need not be contiguous in their underlying | |
924 | ``root vector'' returned here; hence the increment is not necessarily | |
925 | equal to 1 and may well be negative too (@pxref{Shared Arrays}). | |
52d28fc2 MV |
926 | |
927 | The following example shows the typical way to use this function. It | |
d34bd7d4 | 928 | creates a list of all elements of @var{vec} (in reverse order). |
52d28fc2 MV |
929 | |
930 | @example | |
931 | scm_t_array_handle handle; | |
932 | size_t i, len; | |
933 | ssize_t inc; | |
934 | const SCM *elt; | |
935 | SCM list; | |
936 | ||
937 | elt = scm_vector_elements (vec, &handle, &len, &inc); | |
938 | list = SCM_EOL; | |
939 | for (i = 0; i < len; i++, elt += inc) | |
940 | list = scm_cons (*elt, list); | |
86ccc354 | 941 | scm_array_handle_release (&handle); |
52d28fc2 MV |
942 | @end example |
943 | ||
01e6d0ec MV |
944 | @end deftypefn |
945 | ||
d1f9e107 | 946 | @deftypefn {C Function} {SCM *} scm_vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp) |
52d28fc2 MV |
947 | Like @code{scm_vector_elements} but the pointer can be used to modify |
948 | the vector. | |
949 | ||
950 | The following example shows the typical way to use this function. It | |
951 | fills a vector with @code{#t}. | |
952 | ||
953 | @example | |
954 | scm_t_array_handle handle; | |
955 | size_t i, len; | |
956 | ssize_t inc; | |
957 | SCM *elt; | |
958 | ||
35f957b2 | 959 | elt = scm_vector_writable_elements (vec, &handle, &len, &inc); |
52d28fc2 MV |
960 | for (i = 0; i < len; i++, elt += inc) |
961 | *elt = SCM_BOOL_T; | |
86ccc354 | 962 | scm_array_handle_release (&handle); |
52d28fc2 MV |
963 | @end example |
964 | ||
01e6d0ec MV |
965 | @end deftypefn |
966 | ||
61eed960 | 967 | @node Uniform Numeric Vectors |
27219b32 | 968 | @subsubsection Uniform Numeric Vectors |
07d83abe | 969 | |
61eed960 | 970 | A uniform numeric vector is a vector whose elements are all of a single |
52d28fc2 MV |
971 | numeric type. Guile offers uniform numeric vectors for signed and |
972 | unsigned 8-bit, 16-bit, 32-bit, and 64-bit integers, two sizes of | |
973 | floating point values, and complex floating-point numbers of these two | |
27219b32 | 974 | sizes. @xref{SRFI-4}, for more information. |
673ba2da | 975 | |
27219b32 AW |
976 | For many purposes, bytevectors work just as well as uniform vectors, and have |
977 | the advantage that they integrate well with binary input and output. | |
978 | @xref{Bytevectors}, for more information on bytevectors. | |
673ba2da | 979 | |
e6b226b9 MV |
980 | @node Bit Vectors |
981 | @subsection Bit Vectors | |
07d83abe | 982 | |
e6b226b9 | 983 | @noindent |
61eed960 MV |
984 | Bit vectors are zero-origin, one-dimensional arrays of booleans. They |
985 | are displayed as a sequence of @code{0}s and @code{1}s prefixed by | |
986 | @code{#*}, e.g., | |
07d83abe | 987 | |
e6b226b9 | 988 | @example |
61eed960 | 989 | (make-bitvector 8 #f) @result{} |
e6b226b9 MV |
990 | #*00000000 |
991 | @end example | |
07d83abe | 992 | |
118ff892 AW |
993 | Bit vectors are the special case of one dimensional bit arrays, and can |
994 | thus be used with the array procedures, @xref{Arrays}. | |
2c5d049c | 995 | |
61eed960 MV |
996 | @deffn {Scheme Procedure} bitvector? obj |
997 | @deffnx {C Function} scm_bitvector_p (obj) | |
998 | Return @code{#t} when @var{obj} is a bitvector, else | |
999 | return @code{#f}. | |
1000 | @end deffn | |
1001 | ||
2c5d049c MV |
1002 | @deftypefn {C Function} int scm_is_bitvector (SCM obj) |
1003 | Return @code{1} when @var{obj} is a bitvector, else return @code{0}. | |
1004 | @end deftypefn | |
1005 | ||
61eed960 MV |
1006 | @deffn {Scheme Procedure} make-bitvector len [fill] |
1007 | @deffnx {C Function} scm_make_bitvector (len, fill) | |
1008 | Create a new bitvector of length @var{len} and | |
1009 | optionally initialize all elements to @var{fill}. | |
1010 | @end deffn | |
1011 | ||
2c5d049c MV |
1012 | @deftypefn {C Function} SCM scm_c_make_bitvector (size_t len, SCM fill) |
1013 | Like @code{scm_make_bitvector}, but the length is given as a | |
1014 | @code{size_t}. | |
1015 | @end deftypefn | |
1016 | ||
df0a1002 | 1017 | @deffn {Scheme Procedure} bitvector bit @dots{} |
61eed960 MV |
1018 | @deffnx {C Function} scm_bitvector (bits) |
1019 | Create a new bitvector with the arguments as elements. | |
1020 | @end deffn | |
1021 | ||
1022 | @deffn {Scheme Procedure} bitvector-length vec | |
1023 | @deffnx {C Function} scm_bitvector_length (vec) | |
1024 | Return the length of the bitvector @var{vec}. | |
1025 | @end deffn | |
1026 | ||
2c5d049c MV |
1027 | @deftypefn {C Function} size_t scm_c_bitvector_length (SCM vec) |
1028 | Like @code{scm_bitvector_length}, but the length is returned as a | |
1029 | @code{size_t}. | |
1030 | @end deftypefn | |
1031 | ||
61eed960 MV |
1032 | @deffn {Scheme Procedure} bitvector-ref vec idx |
1033 | @deffnx {C Function} scm_bitvector_ref (vec, idx) | |
1034 | Return the element at index @var{idx} of the bitvector | |
1035 | @var{vec}. | |
1036 | @end deffn | |
1037 | ||
64de6db5 | 1038 | @deftypefn {C Function} SCM scm_c_bitvector_ref (SCM vec, size_t idx) |
2c5d049c MV |
1039 | Return the element at index @var{idx} of the bitvector |
1040 | @var{vec}. | |
1041 | @end deftypefn | |
1042 | ||
61eed960 MV |
1043 | @deffn {Scheme Procedure} bitvector-set! vec idx val |
1044 | @deffnx {C Function} scm_bitvector_set_x (vec, idx, val) | |
1045 | Set the element at index @var{idx} of the bitvector | |
1046 | @var{vec} when @var{val} is true, else clear it. | |
1047 | @end deffn | |
1048 | ||
64de6db5 | 1049 | @deftypefn {C Function} SCM scm_c_bitvector_set_x (SCM vec, size_t idx, SCM val) |
2c5d049c MV |
1050 | Set the element at index @var{idx} of the bitvector |
1051 | @var{vec} when @var{val} is true, else clear it. | |
1052 | @end deftypefn | |
1053 | ||
61eed960 MV |
1054 | @deffn {Scheme Procedure} bitvector-fill! vec val |
1055 | @deffnx {C Function} scm_bitvector_fill_x (vec, val) | |
1056 | Set all elements of the bitvector | |
1057 | @var{vec} when @var{val} is true, else clear them. | |
1058 | @end deffn | |
1059 | ||
1060 | @deffn {Scheme Procedure} list->bitvector list | |
1061 | @deffnx {C Function} scm_list_to_bitvector (list) | |
1062 | Return a new bitvector initialized with the elements | |
1063 | of @var{list}. | |
1064 | @end deffn | |
1065 | ||
1066 | @deffn {Scheme Procedure} bitvector->list vec | |
1067 | @deffnx {C Function} scm_bitvector_to_list (vec) | |
1068 | Return a new list initialized with the elements | |
1069 | of the bitvector @var{vec}. | |
1070 | @end deffn | |
1071 | ||
e6b226b9 MV |
1072 | @deffn {Scheme Procedure} bit-count bool bitvector |
1073 | @deffnx {C Function} scm_bit_count (bool, bitvector) | |
1074 | Return a count of how many entries in @var{bitvector} are equal to | |
1075 | @var{bool}. For example, | |
07d83abe | 1076 | |
e6b226b9 MV |
1077 | @example |
1078 | (bit-count #f #*000111000) @result{} 6 | |
1079 | @end example | |
1080 | @end deffn | |
07d83abe | 1081 | |
e6b226b9 MV |
1082 | @deffn {Scheme Procedure} bit-position bool bitvector start |
1083 | @deffnx {C Function} scm_bit_position (bool, bitvector, start) | |
72b3aa56 | 1084 | Return the index of the first occurrence of @var{bool} in |
e6b226b9 MV |
1085 | @var{bitvector}, starting from @var{start}. If there is no @var{bool} |
1086 | entry between @var{start} and the end of @var{bitvector}, then return | |
1087 | @code{#f}. For example, | |
07d83abe | 1088 | |
e6b226b9 MV |
1089 | @example |
1090 | (bit-position #t #*000101 0) @result{} 3 | |
1091 | (bit-position #f #*0001111 3) @result{} #f | |
1092 | @end example | |
1093 | @end deffn | |
07d83abe | 1094 | |
e6b226b9 MV |
1095 | @deffn {Scheme Procedure} bit-invert! bitvector |
1096 | @deffnx {C Function} scm_bit_invert_x (bitvector) | |
1097 | Modify @var{bitvector} by replacing each element with its negation. | |
1098 | @end deffn | |
07d83abe | 1099 | |
e6b226b9 MV |
1100 | @deffn {Scheme Procedure} bit-set*! bitvector uvec bool |
1101 | @deffnx {C Function} scm_bit_set_star_x (bitvector, uvec, bool) | |
1102 | Set entries of @var{bitvector} to @var{bool}, with @var{uvec} | |
1103 | selecting the entries to change. The return value is unspecified. | |
07d83abe | 1104 | |
e6b226b9 MV |
1105 | If @var{uvec} is a bit vector, then those entries where it has |
1106 | @code{#t} are the ones in @var{bitvector} which are set to @var{bool}. | |
1107 | @var{uvec} and @var{bitvector} must be the same length. When | |
1108 | @var{bool} is @code{#t} it's like @var{uvec} is OR'ed into | |
1109 | @var{bitvector}. Or when @var{bool} is @code{#f} it can be seen as an | |
1110 | ANDNOT. | |
07d83abe | 1111 | |
e6b226b9 MV |
1112 | @example |
1113 | (define bv #*01000010) | |
1114 | (bit-set*! bv #*10010001 #t) | |
1115 | bv | |
1116 | @result{} #*11010011 | |
1117 | @end example | |
07d83abe | 1118 | |
e6b226b9 MV |
1119 | If @var{uvec} is a uniform vector of unsigned long integers, then |
1120 | they're indexes into @var{bitvector} which are set to @var{bool}. | |
07d83abe | 1121 | |
e6b226b9 MV |
1122 | @example |
1123 | (define bv #*01000010) | |
1124 | (bit-set*! bv #u(5 2 7) #t) | |
1125 | bv | |
1126 | @result{} #*01100111 | |
1127 | @end example | |
1128 | @end deffn | |
07d83abe | 1129 | |
e6b226b9 MV |
1130 | @deffn {Scheme Procedure} bit-count* bitvector uvec bool |
1131 | @deffnx {C Function} scm_bit_count_star (bitvector, uvec, bool) | |
1132 | Return a count of how many entries in @var{bitvector} are equal to | |
1133 | @var{bool}, with @var{uvec} selecting the entries to consider. | |
07d83abe | 1134 | |
e6b226b9 MV |
1135 | @var{uvec} is interpreted in the same way as for @code{bit-set*!} |
1136 | above. Namely, if @var{uvec} is a bit vector then entries which have | |
1137 | @code{#t} there are considered in @var{bitvector}. Or if @var{uvec} | |
1138 | is a uniform vector of unsigned long integers then it's the indexes in | |
1139 | @var{bitvector} to consider. | |
07d83abe | 1140 | |
e6b226b9 | 1141 | For example, |
07d83abe MV |
1142 | |
1143 | @example | |
e6b226b9 | 1144 | (bit-count* #*01110111 #*11001101 #t) @result{} 3 |
d40b0538 | 1145 | (bit-count* #*01110111 #u32(7 0 4) #f) @result{} 2 |
07d83abe | 1146 | @end example |
e6b226b9 | 1147 | @end deffn |
07d83abe | 1148 | |
d1f9e107 | 1149 | @deftypefn {C Function} {const scm_t_uint32 *} scm_bitvector_elements (SCM vec, scm_t_array_handle *handle, size_t *offp, size_t *lenp, ssize_t *incp) |
d34bd7d4 MV |
1150 | Like @code{scm_vector_elements} (@pxref{Vector Accessing from C}), but |
1151 | for bitvectors. The variable pointed to by @var{offp} is set to the | |
1152 | value returned by @code{scm_array_handle_bit_elements_offset}. See | |
1153 | @code{scm_array_handle_bit_elements} for how to use the returned | |
1154 | pointer and the offset. | |
86ccc354 MV |
1155 | @end deftypefn |
1156 | ||
d1f9e107 | 1157 | @deftypefn {C Function} {scm_t_uint32 *} scm_bitvector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *offp, size_t *lenp, ssize_t *incp) |
86ccc354 MV |
1158 | Like @code{scm_bitvector_elements}, but the pointer is good for reading |
1159 | and writing. | |
1160 | @end deftypefn | |
de26705f | 1161 | |
e6b226b9 MV |
1162 | @node Arrays |
1163 | @subsection Arrays | |
1164 | @tpindex Arrays | |
07d83abe | 1165 | |
2c5d049c MV |
1166 | @dfn{Arrays} are a collection of cells organized into an arbitrary |
1167 | number of dimensions. Each cell can be accessed in constant time by | |
1168 | supplying an index for each dimension. | |
1169 | ||
118ff892 AW |
1170 | In the current implementation, an array uses a vector of some kind for |
1171 | the actual storage of its elements. Any kind of vector will do, so you | |
1172 | can have arrays of uniform numeric values, arrays of characters, arrays | |
1173 | of bits, and of course, arrays of arbitrary Scheme values. For example, | |
1174 | arrays with an underlying @code{c64vector} might be nice for digital | |
1175 | signal processing, while arrays made from a @code{u8vector} might be | |
1176 | used to hold gray-scale images. | |
d7f6cbd9 | 1177 | |
5e7b8a3d MV |
1178 | The number of dimensions of an array is called its @dfn{rank}. Thus, |
1179 | a matrix is an array of rank 2, while a vector has rank 1. When | |
1180 | accessing an array element, you have to specify one exact integer for | |
1181 | each dimension. These integers are called the @dfn{indices} of the | |
1182 | element. An array specifies the allowed range of indices for each | |
1183 | dimension via an inclusive lower and upper bound. These bounds can | |
1184 | well be negative, but the upper bound must be greater than or equal to | |
1185 | the lower bound minus one. When all lower bounds of an array are | |
1186 | zero, it is called a @dfn{zero-origin} array. | |
1187 | ||
1188 | Arrays can be of rank 0, which could be interpreted as a scalar. | |
1189 | Thus, a zero-rank array can store exactly one object and the list of | |
1190 | indices of this element is the empty list. | |
1191 | ||
1192 | Arrays contain zero elements when one of their dimensions has a zero | |
1193 | length. These empty arrays maintain information about their shape: a | |
1194 | matrix with zero columns and 3 rows is different from a matrix with 3 | |
39b6cb86 MV |
1195 | columns and zero rows, which again is different from a vector of |
1196 | length zero. | |
5e7b8a3d | 1197 | |
118ff892 AW |
1198 | The array procedures are all polymorphic, treating strings, uniform |
1199 | numeric vectors, bytevectors, bit vectors and ordinary vectors as one | |
1200 | dimensional arrays. | |
d7f6cbd9 | 1201 | |
52d28fc2 | 1202 | @menu |
e2535ee4 KR |
1203 | * Array Syntax:: |
1204 | * Array Procedures:: | |
1205 | * Shared Arrays:: | |
1206 | * Accessing Arrays from C:: | |
52d28fc2 MV |
1207 | @end menu |
1208 | ||
1209 | @node Array Syntax | |
1210 | @subsubsection Array Syntax | |
2c5d049c MV |
1211 | |
1212 | An array is displayed as @code{#} followed by its rank, followed by a | |
1d20a495 MV |
1213 | tag that describes the underlying vector, optionally followed by |
1214 | information about its shape, and finally followed by the cells, | |
1215 | organized into dimensions using parentheses. | |
2c5d049c MV |
1216 | |
1217 | In more words, the array tag is of the form | |
1218 | ||
1219 | @example | |
1d20a495 | 1220 | #<rank><vectag><@@lower><:len><@@lower><:len>... |
2c5d049c MV |
1221 | @end example |
1222 | ||
1223 | where @code{<rank>} is a positive integer in decimal giving the rank of | |
1224 | the array. It is omitted when the rank is 1 and the array is non-shared | |
1225 | and has zero-origin (see below). For shared arrays and for a non-zero | |
72b3aa56 | 1226 | origin, the rank is always printed even when it is 1 to distinguish |
2c5d049c MV |
1227 | them from ordinary vectors. |
1228 | ||
1229 | The @code{<vectag>} part is the tag for a uniform numeric vector, like | |
1230 | @code{u8}, @code{s16}, etc, @code{b} for bitvectors, or @code{a} for | |
1231 | strings. It is empty for ordinary vectors. | |
1232 | ||
1d20a495 MV |
1233 | The @code{<@@lower>} part is a @samp{@@} character followed by a signed |
1234 | integer in decimal giving the lower bound of a dimension. There is one | |
2c5d049c MV |
1235 | @code{<@@lower>} for each dimension. When all lower bounds are zero, |
1236 | all @code{<@@lower>} parts are omitted. | |
1237 | ||
e581845a | 1238 | The @code{<:len>} part is a @samp{:} character followed by an unsigned |
1d20a495 | 1239 | integer in decimal giving the length of a dimension. Like for the lower |
1f69b364 | 1240 | bounds, there is one @code{<:len>} for each dimension, and the |
1d20a495 MV |
1241 | @code{<:len>} part always follows the @code{<@@lower>} part for a |
1242 | dimension. Lengths are only then printed when they can't be deduced | |
1243 | from the nested lists of elements of the array literal, which can happen | |
1244 | when at least one length is zero. | |
1245 | ||
5e7b8a3d | 1246 | As a special case, an array of rank 0 is printed as |
1d20a495 | 1247 | @code{#0<vectag>(<scalar>)}, where @code{<scalar>} is the result of |
5e7b8a3d MV |
1248 | printing the single element of the array. |
1249 | ||
2c5d049c | 1250 | Thus, |
07d83abe | 1251 | |
2c5d049c MV |
1252 | @table @code |
1253 | @item #(1 2 3) | |
1254 | is an ordinary array of rank 1 with lower bound 0 in dimension 0. | |
1255 | (I.e., a regular vector.) | |
07d83abe | 1256 | |
2c5d049c MV |
1257 | @item #@@2(1 2 3) |
1258 | is an ordinary array of rank 1 with lower bound 2 in dimension 0. | |
07d83abe | 1259 | |
2c5d049c MV |
1260 | @item #2((1 2 3) (4 5 6)) |
1261 | is a non-uniform array of rank 2; a 3@cross{}3 matrix with index ranges 0..2 | |
1262 | and 0..2. | |
1263 | ||
1264 | @item #u32(0 1 2) | |
1265 | is a uniform u8 array of rank 1. | |
1266 | ||
1267 | @item #2u32@@2@@3((1 2) (2 3)) | |
1268 | is a uniform u8 array of rank 2 with index ranges 2..3 and 3..4. | |
1269 | ||
1d20a495 | 1270 | @item #2() |
679cceed NJ |
1271 | is a two-dimensional array with index ranges 0..-1 and 0..-1, i.e.@: |
1272 | both dimensions have length zero. | |
1d20a495 MV |
1273 | |
1274 | @item #2:0:2() | |
679cceed | 1275 | is a two-dimensional array with index ranges 0..-1 and 0..1, i.e.@: the |
1d20a495 MV |
1276 | first dimension has length zero, but the second has length 2. |
1277 | ||
5e7b8a3d MV |
1278 | @item #0(12) |
1279 | is a rank-zero array with contents 12. | |
1280 | ||
2c5d049c | 1281 | @end table |
07d83abe | 1282 | |
438974d0 LC |
1283 | In addition, bytevectors are also arrays, but use a different syntax |
1284 | (@pxref{Bytevectors}): | |
1285 | ||
1286 | @table @code | |
1287 | ||
1288 | @item #vu8(1 2 3) | |
1289 | is a 3-byte long bytevector, with contents 1, 2, 3. | |
1290 | ||
1291 | @end table | |
1292 | ||
52d28fc2 MV |
1293 | @node Array Procedures |
1294 | @subsubsection Array Procedures | |
07d83abe MV |
1295 | |
1296 | When an array is created, the range of each dimension must be | |
1297 | specified, e.g., to create a 2@cross{}3 array with a zero-based index: | |
1298 | ||
1299 | @example | |
1300 | (make-array 'ho 2 3) @result{} #2((ho ho ho) (ho ho ho)) | |
1301 | @end example | |
1302 | ||
1303 | The range of each dimension can also be given explicitly, e.g., another | |
1304 | way to create the same array: | |
1305 | ||
1306 | @example | |
1307 | (make-array 'ho '(0 1) '(0 2)) @result{} #2((ho ho ho) (ho ho ho)) | |
1308 | @end example | |
1309 | ||
2c5d049c MV |
1310 | The following procedures can be used with arrays (or vectors). An |
1311 | argument shown as @var{idx}@dots{} means one parameter for each | |
1312 | dimension in the array. A @var{idxlist} argument means a list of such | |
07d83abe MV |
1313 | values, one for each dimension. |
1314 | ||
2c5d049c | 1315 | |
d7f6cbd9 MV |
1316 | @deffn {Scheme Procedure} array? obj |
1317 | @deffnx {C Function} scm_array_p (obj, unused) | |
07d83abe MV |
1318 | Return @code{#t} if the @var{obj} is an array, and @code{#f} if |
1319 | not. | |
1320 | ||
d7f6cbd9 MV |
1321 | The second argument to scm_array_p is there for historical reasons, |
1322 | but it is not used. You should always pass @code{SCM_UNDEFINED} as | |
1323 | its value. | |
1324 | @end deffn | |
1325 | ||
1326 | @deffn {Scheme Procedure} typed-array? obj type | |
1327 | @deffnx {C Function} scm_typed_array_p (obj, type) | |
1328 | Return @code{#t} if the @var{obj} is an array of type @var{type}, and | |
1329 | @code{#f} if not. | |
1330 | @end deffn | |
1331 | ||
1332 | @deftypefn {C Function} int scm_is_array (SCM obj) | |
1333 | Return @code{1} if the @var{obj} is an array and @code{0} if not. | |
1334 | @end deftypefn | |
1335 | ||
1336 | @deftypefn {C Function} int scm_is_typed_array (SCM obj, SCM type) | |
1337 | Return @code{0} if the @var{obj} is an array of type @var{type}, and | |
1338 | @code{1} if not. | |
7cf2d3d5 | 1339 | @end deftypefn |
2c5d049c MV |
1340 | |
1341 | @deffn {Scheme Procedure} make-array fill bound @dots{} | |
d7f6cbd9 MV |
1342 | @deffnx {C Function} scm_make_array (fill, bounds) |
1343 | Equivalent to @code{(make-typed-array #t @var{fill} @var{bound} ...)}. | |
07d83abe MV |
1344 | @end deffn |
1345 | ||
d7f6cbd9 MV |
1346 | @deffn {Scheme Procedure} make-typed-array type fill bound @dots{} |
1347 | @deffnx {C Function} scm_make_typed_array (type, fill, bounds) | |
07d83abe | 1348 | Create and return an array that has as many dimensions as there are |
d7f6cbd9 | 1349 | @var{bound}s and (maybe) fill it with @var{fill}. |
07d83abe | 1350 | |
72b3aa56 | 1351 | The underlying storage vector is created according to @var{type}, |
d7f6cbd9 MV |
1352 | which must be a symbol whose name is the `vectag' of the array as |
1353 | explained above, or @code{#t} for ordinary, non-specialized arrays. | |
2c5d049c | 1354 | |
d7f6cbd9 MV |
1355 | For example, using the symbol @code{f64} for @var{type} will create an |
1356 | array that uses a @code{f64vector} for storing its elements, and | |
1357 | @code{a} will use a string. | |
1358 | ||
1281f0fc MV |
1359 | When @var{fill} is not the special @emph{unspecified} value, the new |
1360 | array is filled with @var{fill}. Otherwise, the initial contents of | |
1361 | the array is unspecified. The special @emph{unspecified} value is | |
1362 | stored in the variable @code{*unspecified*} so that for example | |
1363 | @code{(make-typed-array 'u32 *unspecified* 4)} creates a uninitialized | |
1364 | @code{u32} vector of length 4. | |
2c5d049c | 1365 | |
64de6db5 BT |
1366 | Each @var{bound} may be a positive non-zero integer @var{n}, in which |
1367 | case the index for that dimension can range from 0 through @var{n}-1; or | |
2c5d049c MV |
1368 | an explicit index range specifier in the form @code{(LOWER UPPER)}, |
1369 | where both @var{lower} and @var{upper} are integers, possibly less than | |
1370 | zero, and possibly the same number (however, @var{lower} cannot be | |
1371 | greater than @var{upper}). | |
1372 | @end deffn | |
1373 | ||
1374 | @deffn {Scheme Procedure} list->array dimspec list | |
d7f6cbd9 | 1375 | Equivalent to @code{(list->typed-array #t @var{dimspec} |
2c5d049c MV |
1376 | @var{list})}. |
1377 | @end deffn | |
1378 | ||
d7f6cbd9 MV |
1379 | @deffn {Scheme Procedure} list->typed-array type dimspec list |
1380 | @deffnx {C Function} scm_list_to_typed_array (type, dimspec, list) | |
1381 | Return an array of the type indicated by @var{type} with elements the | |
2c5d049c MV |
1382 | same as those of @var{list}. |
1383 | ||
1384 | The argument @var{dimspec} determines the number of dimensions of the | |
1385 | array and their lower bounds. When @var{dimspec} is an exact integer, | |
1386 | it gives the number of dimensions directly and all lower bounds are | |
1387 | zero. When it is a list of exact integers, then each element is the | |
1388 | lower index bound of a dimension, and there will be as many dimensions | |
1389 | as elements in the list. | |
07d83abe MV |
1390 | @end deffn |
1391 | ||
d7f6cbd9 | 1392 | @deffn {Scheme Procedure} array-type array |
73994167 | 1393 | @deffnx {C Function} scm_array_type (array) |
d7f6cbd9 MV |
1394 | Return the type of @var{array}. This is the `vectag' used for |
1395 | printing @var{array} (or @code{#t} for ordinary arrays) and can be | |
1396 | used with @code{make-typed-array} to create an array of the same kind | |
1397 | as @var{array}. | |
2c5d049c | 1398 | @end deffn |
07d83abe MV |
1399 | |
1400 | @deffn {Scheme Procedure} array-ref array idx @dots{} | |
73994167 | 1401 | @deffnx {C Function} scm_array_ref (array, idxlist) |
07d83abe MV |
1402 | Return the element at @code{(idx @dots{})} in @var{array}. |
1403 | ||
1404 | @example | |
1405 | (define a (make-array 999 '(1 2) '(3 4))) | |
1406 | (array-ref a 2 4) @result{} 999 | |
1407 | @end example | |
1408 | @end deffn | |
1409 | ||
1410 | @deffn {Scheme Procedure} array-in-bounds? array idx @dots{} | |
1411 | @deffnx {C Function} scm_array_in_bounds_p (array, idxlist) | |
73994167 | 1412 | Return @code{#t} if the given indices would be acceptable to |
07d83abe MV |
1413 | @code{array-ref}. |
1414 | ||
1415 | @example | |
1416 | (define a (make-array #f '(1 2) '(3 4))) | |
b83ecb8f | 1417 | (array-in-bounds? a 2 3) @result{} #t |
07d83abe MV |
1418 | (array-in-bounds? a 0 0) @result{} #f |
1419 | @end example | |
1420 | @end deffn | |
1421 | ||
07d83abe | 1422 | @deffn {Scheme Procedure} array-set! array obj idx @dots{} |
07d83abe MV |
1423 | @deffnx {C Function} scm_array_set_x (array, obj, idxlist) |
1424 | Set the element at @code{(idx @dots{})} in @var{array} to @var{obj}. | |
1425 | The return value is unspecified. | |
1426 | ||
1427 | @example | |
1428 | (define a (make-array #f '(0 1) '(0 1))) | |
1429 | (array-set! a #t 1 1) | |
1430 | a @result{} #2((#f #f) (#f #t)) | |
1431 | @end example | |
1432 | @end deffn | |
1433 | ||
07d83abe MV |
1434 | @deffn {Scheme Procedure} array-shape array |
1435 | @deffnx {Scheme Procedure} array-dimensions array | |
1436 | @deffnx {C Function} scm_array_dimensions (array) | |
72b3aa56 | 1437 | Return a list of the bounds for each dimension of @var{array}. |
07d83abe MV |
1438 | |
1439 | @code{array-shape} gives @code{(@var{lower} @var{upper})} for each | |
1440 | dimension. @code{array-dimensions} instead returns just | |
1441 | @math{@var{upper}+1} for dimensions with a 0 lower bound. Both are | |
1442 | suitable as input to @code{make-array}. | |
1443 | ||
1444 | For example, | |
1445 | ||
1446 | @example | |
1447 | (define a (make-array 'foo '(-1 3) 5)) | |
1448 | (array-shape a) @result{} ((-1 3) (0 4)) | |
1449 | (array-dimensions a) @result{} ((-1 3) 5) | |
1450 | @end example | |
1451 | @end deffn | |
1452 | ||
73994167 DL |
1453 | @deffn {Scheme Procedure} array-length array |
1454 | @deffnx {C Function} scm_array_length (array) | |
1455 | @deffnx {C Function} size_t scm_c_array_length (array) | |
1456 | Return the length of an array: its first dimension. It is an error to | |
1457 | ask for the length of an array of rank 0. | |
1458 | @end deffn | |
1459 | ||
64de6db5 BT |
1460 | @deffn {Scheme Procedure} array-rank array |
1461 | @deffnx {C Function} scm_array_rank (array) | |
39b6cb86 | 1462 | Return the rank of @var{array}. |
07d83abe MV |
1463 | @end deffn |
1464 | ||
ca6a8a38 | 1465 | @deftypefn {C Function} size_t scm_c_array_rank (SCM array) |
39b6cb86 MV |
1466 | Return the rank of @var{array} as a @code{size_t}. |
1467 | @end deftypefn | |
1468 | ||
07d83abe MV |
1469 | @deffn {Scheme Procedure} array->list array |
1470 | @deffnx {C Function} scm_array_to_list (array) | |
1471 | Return a list consisting of all the elements, in order, of | |
1472 | @var{array}. | |
1473 | @end deffn | |
1474 | ||
1475 | @c FIXME: Describe how the order affects the copying (it matters for | |
1476 | @c shared arrays with the same underlying root vector, presumably). | |
1477 | @c | |
1478 | @deffn {Scheme Procedure} array-copy! src dst | |
1479 | @deffnx {Scheme Procedure} array-copy-in-order! src dst | |
1480 | @deffnx {C Function} scm_array_copy_x (src, dst) | |
1481 | Copy every element from vector or array @var{src} to the corresponding | |
1482 | element of @var{dst}. @var{dst} must have the same rank as @var{src}, | |
1483 | and be at least as large in each dimension. The return value is | |
1484 | unspecified. | |
1485 | @end deffn | |
1486 | ||
1487 | @deffn {Scheme Procedure} array-fill! array fill | |
1488 | @deffnx {C Function} scm_array_fill_x (array, fill) | |
1489 | Store @var{fill} in every element of @var{array}. The value returned | |
1490 | is unspecified. | |
1491 | @end deffn | |
1492 | ||
1493 | @c begin (texi-doc-string "guile" "array-equal?") | |
df0a1002 | 1494 | @deffn {Scheme Procedure} array-equal? array @dots{} |
07d83abe MV |
1495 | Return @code{#t} if all arguments are arrays with the same shape, the |
1496 | same type, and have corresponding elements which are either | |
1497 | @code{equal?} or @code{array-equal?}. This function differs from | |
a587d6a9 | 1498 | @code{equal?} (@pxref{Equality}) in that all arguments must be arrays. |
07d83abe MV |
1499 | @end deffn |
1500 | ||
07d83abe MV |
1501 | @c FIXME: array-map! accepts no source arrays at all, and in that |
1502 | @c case makes calls "(proc)". Is that meant to be a documented | |
1503 | @c feature? | |
1504 | @c | |
1505 | @c FIXME: array-for-each doesn't say what happens if the sources have | |
1506 | @c different index ranges. The code currently iterates over the | |
1507 | @c indices of the first and expects the others to cover those. That | |
b3da54d1 | 1508 | @c at least vaguely matches array-map!, but is it meant to be a |
07d83abe MV |
1509 | @c documented feature? |
1510 | ||
df0a1002 | 1511 | @deffn {Scheme Procedure} array-map! dst proc src @dots{} |
07d83abe MV |
1512 | @deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN |
1513 | @deffnx {C Function} scm_array_map_x (dst, proc, srclist) | |
1514 | Set each element of the @var{dst} array to values obtained from calls | |
1515 | to @var{proc}. The value returned is unspecified. | |
1516 | ||
1517 | Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})}, | |
1518 | where each @var{elem} is from the corresponding @var{src} array, at | |
1519 | the @var{dst} index. @code{array-map-in-order!} makes the calls in | |
1520 | row-major order, @code{array-map!} makes them in an unspecified order. | |
1521 | ||
1522 | The @var{src} arrays must have the same number of dimensions as | |
1523 | @var{dst}, and must have a range for each dimension which covers the | |
1524 | range in @var{dst}. This ensures all @var{dst} indices are valid in | |
1525 | each @var{src}. | |
1526 | @end deffn | |
1527 | ||
df0a1002 | 1528 | @deffn {Scheme Procedure} array-for-each proc src1 src2 @dots{} |
07d83abe | 1529 | @deffnx {C Function} scm_array_for_each (proc, src1, srclist) |
df0a1002 BT |
1530 | Apply @var{proc} to each tuple of elements of @var{src1} @var{src2} |
1531 | @dots{}, in row-major order. The value returned is unspecified. | |
07d83abe MV |
1532 | @end deffn |
1533 | ||
1534 | @deffn {Scheme Procedure} array-index-map! dst proc | |
1535 | @deffnx {C Function} scm_array_index_map_x (dst, proc) | |
1536 | Set each element of the @var{dst} array to values returned by calls to | |
1537 | @var{proc}. The value returned is unspecified. | |
1538 | ||
1539 | Each call is @code{(@var{proc} @var{i1} @dots{} @var{iN})}, where | |
1540 | @var{i1}@dots{}@var{iN} is the destination index, one parameter for | |
1541 | each dimension. The order in which the calls are made is unspecified. | |
1542 | ||
1543 | For example, to create a @m{4\times4, 4x4} matrix representing a | |
1544 | cyclic group, | |
1545 | ||
1546 | @tex | |
1547 | \advance\leftskip by 2\lispnarrowing { | |
1548 | $\left(\matrix{% | |
1549 | 0 & 1 & 2 & 3 \cr | |
1550 | 1 & 2 & 3 & 0 \cr | |
1551 | 2 & 3 & 0 & 1 \cr | |
1552 | 3 & 0 & 1 & 2 \cr | |
1553 | }\right)$} \par | |
1554 | @end tex | |
1555 | @ifnottex | |
1556 | @example | |
1557 | / 0 1 2 3 \ | |
1558 | | 1 2 3 0 | | |
1559 | | 2 3 0 1 | | |
1560 | \ 3 0 1 2 / | |
1561 | @end example | |
1562 | @end ifnottex | |
1563 | ||
1564 | @example | |
1565 | (define a (make-array #f 4 4)) | |
1566 | (array-index-map! a (lambda (i j) | |
1567 | (modulo (+ i j) 4))) | |
1568 | @end example | |
1569 | @end deffn | |
1570 | ||
07d83abe | 1571 | @deffn {Scheme Procedure} uniform-array-read! ra [port_or_fd [start [end]]] |
07d83abe | 1572 | @deffnx {C Function} scm_uniform_array_read_x (ra, port_or_fd, start, end) |
64de6db5 BT |
1573 | Attempt to read all elements of array @var{ra}, in lexicographic order, as |
1574 | binary objects from @var{port_or_fd}. | |
07d83abe | 1575 | If an end of file is encountered, |
64de6db5 | 1576 | the objects up to that point are put into @var{ra} |
07d83abe MV |
1577 | (starting at the beginning) and the remainder of the array is |
1578 | unchanged. | |
1579 | ||
1580 | The optional arguments @var{start} and @var{end} allow | |
1581 | a specified region of a vector (or linearized array) to be read, | |
1582 | leaving the remainder of the vector unchanged. | |
1583 | ||
1584 | @code{uniform-array-read!} returns the number of objects read. | |
64de6db5 | 1585 | @var{port_or_fd} may be omitted, in which case it defaults to the value |
07d83abe MV |
1586 | returned by @code{(current-input-port)}. |
1587 | @end deffn | |
1588 | ||
64de6db5 BT |
1589 | @deffn {Scheme Procedure} uniform-array-write ra [port_or_fd [start [end]]] |
1590 | @deffnx {C Function} scm_uniform_array_write (ra, port_or_fd, start, end) | |
1591 | Writes all elements of @var{ra} as binary objects to | |
1592 | @var{port_or_fd}. | |
07d83abe MV |
1593 | |
1594 | The optional arguments @var{start} | |
1595 | and @var{end} allow | |
1596 | a specified region of a vector (or linearized array) to be written. | |
1597 | ||
1598 | The number of objects actually written is returned. | |
64de6db5 | 1599 | @var{port_or_fd} may be |
07d83abe MV |
1600 | omitted, in which case it defaults to the value returned by |
1601 | @code{(current-output-port)}. | |
1602 | @end deffn | |
1603 | ||
e2535ee4 KR |
1604 | @node Shared Arrays |
1605 | @subsubsection Shared Arrays | |
1606 | ||
1607 | @deffn {Scheme Procedure} make-shared-array oldarray mapfunc bound @dots{} | |
1608 | @deffnx {C Function} scm_make_shared_array (oldarray, mapfunc, boundlist) | |
b4b78f5d KR |
1609 | Return a new array which shares the storage of @var{oldarray}. |
1610 | Changes made through either affect the same underlying storage. The | |
64de6db5 | 1611 | @var{bound} @dots{} arguments are the shape of the new array, the same |
b4b78f5d KR |
1612 | as @code{make-array} (@pxref{Array Procedures}). |
1613 | ||
1614 | @var{mapfunc} translates coordinates from the new array to the | |
1615 | @var{oldarray}. It's called as @code{(@var{mapfunc} newidx1 @dots{})} | |
1616 | with one parameter for each dimension of the new array, and should | |
1617 | return a list of indices for @var{oldarray}, one for each dimension of | |
1618 | @var{oldarray}. | |
1619 | ||
1620 | @var{mapfunc} must be affine linear, meaning that each @var{oldarray} | |
1621 | index must be formed by adding integer multiples (possibly negative) | |
1622 | of some or all of @var{newidx1} etc, plus a possible integer offset. | |
1623 | The multiples and offset must be the same in each call. | |
1624 | ||
1625 | @sp 1 | |
1626 | One good use for a shared array is to restrict the range of some | |
1627 | dimensions, so as to apply say @code{array-for-each} or | |
1628 | @code{array-fill!} to only part of an array. The plain @code{list} | |
1629 | function can be used for @var{mapfunc} in this case, making no changes | |
1630 | to the index values. For example, | |
e2535ee4 | 1631 | |
b4b78f5d KR |
1632 | @example |
1633 | (make-shared-array #2((a b c) (d e f) (g h i)) list 3 2) | |
1634 | @result{} #2((a b) (d e) (g h)) | |
1635 | @end example | |
1636 | ||
1637 | The new array can have fewer dimensions than @var{oldarray}, for | |
1638 | example to take a column from an array. | |
1639 | ||
1640 | @example | |
1641 | (make-shared-array #2((a b c) (d e f) (g h i)) | |
1642 | (lambda (i) (list i 2)) | |
1643 | '(0 2)) | |
1644 | @result{} #1(c f i) | |
1645 | @end example | |
1646 | ||
1647 | A diagonal can be taken by using the single new array index for both | |
1648 | row and column in the old array. For example, | |
1649 | ||
1650 | @example | |
1651 | (make-shared-array #2((a b c) (d e f) (g h i)) | |
1652 | (lambda (i) (list i i)) | |
1653 | '(0 2)) | |
1654 | @result{} #1(a e i) | |
1655 | @end example | |
1656 | ||
1657 | Dimensions can be increased by for instance considering portions of a | |
1658 | one dimensional array as rows in a two dimensional array. | |
1659 | (@code{array-contents} below can do the opposite, flattening an | |
1660 | array.) | |
1661 | ||
1662 | @example | |
1663 | (make-shared-array #1(a b c d e f g h i j k l) | |
1664 | (lambda (i j) (list (+ (* i 3) j))) | |
1665 | 4 3) | |
1666 | @result{} #2((a b c) (d e f) (g h i) (j k l)) | |
1667 | @end example | |
1668 | ||
1669 | By negating an index the order that elements appear can be reversed. | |
1670 | The following just reverses the column order, | |
1671 | ||
1672 | @example | |
1673 | (make-shared-array #2((a b c) (d e f) (g h i)) | |
1674 | (lambda (i j) (list i (- 2 j))) | |
1675 | 3 3) | |
1676 | @result{} #2((c b a) (f e d) (i h g)) | |
1677 | @end example | |
1678 | ||
1679 | A fixed offset on indexes allows for instance a change from a 0 based | |
1680 | to a 1 based array, | |
1681 | ||
1682 | @example | |
1683 | (define x #2((a b c) (d e f) (g h i))) | |
1684 | (define y (make-shared-array x | |
1685 | (lambda (i j) (list (1- i) (1- j))) | |
1686 | '(1 3) '(1 3))) | |
1687 | (array-ref x 0 0) @result{} a | |
1688 | (array-ref y 1 1) @result{} a | |
1689 | @end example | |
1690 | ||
1691 | A multiple on an index allows every Nth element of an array to be | |
1692 | taken. The following is every third element, | |
1693 | ||
1694 | @example | |
1695 | (make-shared-array #1(a b c d e f g h i j k l) | |
1b09b607 | 1696 | (lambda (i) (list (* i 3))) |
b4b78f5d KR |
1697 | 4) |
1698 | @result{} #1(a d g j) | |
1699 | @end example | |
1700 | ||
1701 | The above examples can be combined to make weird and wonderful | |
1702 | selections from an array, but it's important to note that because | |
1703 | @var{mapfunc} must be affine linear, arbitrary permutations are not | |
1704 | possible. | |
1705 | ||
1706 | In the current implementation, @var{mapfunc} is not called for every | |
1707 | access to the new array but only on some sample points to establish a | |
1708 | base and stride for new array indices in @var{oldarray} data. A few | |
1709 | sample points are enough because @var{mapfunc} is linear. | |
e2535ee4 KR |
1710 | @end deffn |
1711 | ||
1712 | @deffn {Scheme Procedure} shared-array-increments array | |
1713 | @deffnx {C Function} scm_shared_array_increments (array) | |
1714 | For each dimension, return the distance between elements in the root vector. | |
1715 | @end deffn | |
1716 | ||
1717 | @deffn {Scheme Procedure} shared-array-offset array | |
1718 | @deffnx {C Function} scm_shared_array_offset (array) | |
1719 | Return the root vector index of the first element in the array. | |
1720 | @end deffn | |
1721 | ||
1722 | @deffn {Scheme Procedure} shared-array-root array | |
1723 | @deffnx {C Function} scm_shared_array_root (array) | |
1724 | Return the root vector of a shared array. | |
1725 | @end deffn | |
1726 | ||
d8c3fde9 KR |
1727 | @deffn {Scheme Procedure} array-contents array [strict] |
1728 | @deffnx {C Function} scm_array_contents (array, strict) | |
1729 | If @var{array} may be @dfn{unrolled} into a one dimensional shared array | |
1730 | without changing their order (last subscript changing fastest), then | |
1731 | @code{array-contents} returns that shared array, otherwise it returns | |
1732 | @code{#f}. All arrays made by @code{make-array} and | |
35f957b2 | 1733 | @code{make-typed-array} may be unrolled, some arrays made by |
d8c3fde9 KR |
1734 | @code{make-shared-array} may not be. |
1735 | ||
1736 | If the optional argument @var{strict} is provided, a shared array will | |
1737 | be returned only if its elements are stored internally contiguous in | |
1738 | memory. | |
1739 | @end deffn | |
1740 | ||
df0a1002 | 1741 | @deffn {Scheme Procedure} transpose-array array dim1 dim2 @dots{} |
e2535ee4 KR |
1742 | @deffnx {C Function} scm_transpose_array (array, dimlist) |
1743 | Return an array sharing contents with @var{array}, but with | |
1744 | dimensions arranged in a different order. There must be one | |
1745 | @var{dim} argument for each dimension of @var{array}. | |
1746 | @var{dim1}, @var{dim2}, @dots{} should be integers between 0 | |
1747 | and the rank of the array to be returned. Each integer in that | |
1748 | range must appear at least once in the argument list. | |
1749 | ||
1750 | The values of @var{dim1}, @var{dim2}, @dots{} correspond to | |
1751 | dimensions in the array to be returned, and their positions in the | |
1752 | argument list to dimensions of @var{array}. Several @var{dim}s | |
1753 | may have the same value, in which case the returned array will | |
1754 | have smaller rank than @var{array}. | |
1755 | ||
1756 | @lisp | |
1757 | (transpose-array '#2((a b) (c d)) 1 0) @result{} #2((a c) (b d)) | |
1758 | (transpose-array '#2((a b) (c d)) 0 0) @result{} #1(a d) | |
1759 | (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) @result{} | |
1760 | #2((a 4) (b 5) (c 6)) | |
1761 | @end lisp | |
1762 | @end deffn | |
1763 | ||
52d28fc2 MV |
1764 | @node Accessing Arrays from C |
1765 | @subsubsection Accessing Arrays from C | |
1766 | ||
66c33af0 NJ |
1767 | For interworking with external C code, Guile provides an API to allow C |
1768 | code to access the elements of a Scheme array. In particular, for | |
1769 | uniform numeric arrays, the API exposes the underlying uniform data as a | |
1770 | C array of numbers of the relevant type. | |
52d28fc2 MV |
1771 | |
1772 | While pointers to the elements of an array are in use, the array itself | |
1773 | must be protected so that the pointer remains valid. Such a protected | |
86ccc354 MV |
1774 | array is said to be @dfn{reserved}. A reserved array can be read but |
1775 | modifications to it that would cause the pointer to its elements to | |
1776 | become invalid are prevented. When you attempt such a modification, an | |
1777 | error is signalled. | |
52d28fc2 MV |
1778 | |
1779 | (This is similar to locking the array while it is in use, but without | |
1780 | the danger of a deadlock. In a multi-threaded program, you will need | |
1781 | additional synchronization to avoid modifying reserved arrays.) | |
1782 | ||
661ae7ab | 1783 | You must take care to always unreserve an array after reserving it, |
dd57ddd5 NJ |
1784 | even in the presence of non-local exits. If a non-local exit can |
1785 | happen between these two calls, you should install a dynwind context | |
1786 | that releases the array when it is left (@pxref{Dynamic Wind}). | |
1787 | ||
1788 | In addition, array reserving and unreserving must be properly | |
1789 | paired. For instance, when reserving two or more arrays in a certain | |
1790 | order, you need to unreserve them in the opposite order. | |
52d28fc2 MV |
1791 | |
1792 | Once you have reserved an array and have retrieved the pointer to its | |
1793 | elements, you must figure out the layout of the elements in memory. | |
1794 | Guile allows slices to be taken out of arrays without actually making a | |
86ccc354 MV |
1795 | copy, such as making an alias for the diagonal of a matrix that can be |
1796 | treated as a vector. Arrays that result from such an operation are not | |
1797 | stored contiguously in memory and when working with their elements | |
1798 | directly, you need to take this into account. | |
1799 | ||
1800 | The layout of array elements in memory can be defined via a | |
1801 | @emph{mapping function} that computes a scalar position from a vector of | |
1802 | indices. The scalar position then is the offset of the element with the | |
1803 | given indices from the start of the storage block of the array. | |
1804 | ||
1805 | In Guile, this mapping function is restricted to be @dfn{affine}: all | |
661ae7ab | 1806 | mapping functions of Guile arrays can be written as @code{p = b + |
86ccc354 | 1807 | c[0]*i[0] + c[1]*i[1] + ... + c[n-1]*i[n-1]} where @code{i[k]} is the |
661ae7ab MV |
1808 | @nicode{k}th index and @code{n} is the rank of the array. For |
1809 | example, a matrix of size 3x3 would have @code{b == 0}, @code{c[0] == | |
1810 | 3} and @code{c[1] == 1}. When you transpose this matrix (with | |
86ccc354 MV |
1811 | @code{transpose-array}, say), you will get an array whose mapping |
1812 | function has @code{b == 0}, @code{c[0] == 1} and @code{c[1] == 3}. | |
1813 | ||
1814 | The function @code{scm_array_handle_dims} gives you (indirect) access to | |
1815 | the coefficients @code{c[k]}. | |
1816 | ||
1817 | @c XXX | |
1818 | Note that there are no functions for accessing the elements of a | |
1819 | character array yet. Once the string implementation of Guile has been | |
1820 | changed to use Unicode, we will provide them. | |
1821 | ||
1822 | @deftp {C Type} scm_t_array_handle | |
1823 | This is a structure type that holds all information necessary to manage | |
1824 | the reservation of arrays as explained above. Structures of this type | |
1825 | must be allocated on the stack and must only be accessed by the | |
1826 | functions listed below. | |
1827 | @end deftp | |
1828 | ||
1829 | @deftypefn {C Function} void scm_array_get_handle (SCM array, scm_t_array_handle *handle) | |
1830 | Reserve @var{array}, which must be an array, and prepare @var{handle} to | |
1831 | be used with the functions below. You must eventually call | |
1832 | @code{scm_array_handle_release} on @var{handle}, and do this in a | |
1833 | properly nested fashion, as explained above. The structure pointed to | |
1834 | by @var{handle} does not need to be initialized before calling this | |
1835 | function. | |
1836 | @end deftypefn | |
1837 | ||
1838 | @deftypefn {C Function} void scm_array_handle_release (scm_t_array_handle *handle) | |
1839 | End the array reservation represented by @var{handle}. After a call to | |
1840 | this function, @var{handle} might be used for another reservation. | |
1841 | @end deftypefn | |
1842 | ||
1843 | @deftypefn {C Function} size_t scm_array_handle_rank (scm_t_array_handle *handle) | |
1844 | Return the rank of the array represented by @var{handle}. | |
1845 | @end deftypefn | |
1846 | ||
1847 | @deftp {C Type} scm_t_array_dim | |
1848 | This structure type holds information about the layout of one dimension | |
1849 | of an array. It includes the following fields: | |
1850 | ||
1851 | @table @code | |
1852 | @item ssize_t lbnd | |
1853 | @itemx ssize_t ubnd | |
1854 | The lower and upper bounds (both inclusive) of the permissible index | |
1855 | range for the given dimension. Both values can be negative, but | |
1856 | @var{lbnd} is always less than or equal to @var{ubnd}. | |
1857 | ||
1858 | @item ssize_t inc | |
1859 | The distance from one element of this dimension to the next. Note, too, | |
1860 | that this can be negative. | |
1861 | @end table | |
1862 | @end deftp | |
1863 | ||
d1f9e107 | 1864 | @deftypefn {C Function} {const scm_t_array_dim *} scm_array_handle_dims (scm_t_array_handle *handle) |
86ccc354 MV |
1865 | Return a pointer to a C vector of information about the dimensions of |
1866 | the array represented by @var{handle}. This pointer is valid as long as | |
1867 | the array remains reserved. As explained above, the | |
1868 | @code{scm_t_array_dim} structures returned by this function can be used | |
1869 | calculate the position of an element in the storage block of the array | |
1870 | from its indices. | |
1871 | ||
1872 | This position can then be used as an index into the C array pointer | |
1873 | returned by the various @code{scm_array_handle_<foo>_elements} | |
1874 | functions, or with @code{scm_array_handle_ref} and | |
1875 | @code{scm_array_handle_set}. | |
1876 | ||
1877 | Here is how one can compute the position @var{pos} of an element given | |
1878 | its indices in the vector @var{indices}: | |
1879 | ||
1880 | @example | |
1881 | ssize_t indices[RANK]; | |
1882 | scm_t_array_dim *dims; | |
1883 | ssize_t pos; | |
1884 | size_t i; | |
1885 | ||
1886 | pos = 0; | |
1887 | for (i = 0; i < RANK; i++) | |
1888 | @{ | |
1889 | if (indices[i] < dims[i].lbnd || indices[i] > dims[i].ubnd) | |
1890 | out_of_range (); | |
1891 | pos += (indices[i] - dims[i].lbnd) * dims[i].inc; | |
1892 | @} | |
1893 | @end example | |
1894 | @end deftypefn | |
1895 | ||
87894590 MV |
1896 | @deftypefn {C Function} ssize_t scm_array_handle_pos (scm_t_array_handle *handle, SCM indices) |
1897 | Compute the position corresponding to @var{indices}, a list of | |
1898 | indices. The position is computed as described above for | |
1899 | @code{scm_array_handle_dims}. The number of the indices and their | |
72b3aa56 | 1900 | range is checked and an appropriate error is signalled for invalid |
87894590 MV |
1901 | indices. |
1902 | @end deftypefn | |
1903 | ||
86ccc354 MV |
1904 | @deftypefn {C Function} SCM scm_array_handle_ref (scm_t_array_handle *handle, ssize_t pos) |
1905 | Return the element at position @var{pos} in the storage block of the | |
1906 | array represented by @var{handle}. Any kind of array is acceptable. No | |
1907 | range checking is done on @var{pos}. | |
1908 | @end deftypefn | |
1909 | ||
1910 | @deftypefn {C Function} void scm_array_handle_set (scm_t_array_handle *handle, ssize_t pos, SCM val) | |
1911 | Set the element at position @var{pos} in the storage block of the array | |
1912 | represented by @var{handle} to @var{val}. Any kind of array is | |
1913 | acceptable. No range checking is done on @var{pos}. An error is | |
1914 | signalled when the array can not store @var{val}. | |
1915 | @end deftypefn | |
1916 | ||
d1f9e107 | 1917 | @deftypefn {C Function} {const SCM *} scm_array_handle_elements (scm_t_array_handle *handle) |
86ccc354 MV |
1918 | Return a pointer to the elements of a ordinary array of general Scheme |
1919 | values (i.e., a non-uniform array) for reading. This pointer is valid | |
1920 | as long as the array remains reserved. | |
1921 | @end deftypefn | |
52d28fc2 | 1922 | |
d1f9e107 | 1923 | @deftypefn {C Function} {SCM *} scm_array_handle_writable_elements (scm_t_array_handle *handle) |
86ccc354 MV |
1924 | Like @code{scm_array_handle_elements}, but the pointer is good for |
1925 | reading and writing. | |
1926 | @end deftypefn | |
1927 | ||
d1f9e107 | 1928 | @deftypefn {C Function} {const void *} scm_array_handle_uniform_elements (scm_t_array_handle *handle) |
86ccc354 MV |
1929 | Return a pointer to the elements of a uniform numeric array for reading. |
1930 | This pointer is valid as long as the array remains reserved. The size | |
1931 | of each element is given by @code{scm_array_handle_uniform_element_size}. | |
1932 | @end deftypefn | |
1933 | ||
d1f9e107 | 1934 | @deftypefn {C Function} {void *} scm_array_handle_uniform_writable_elements (scm_t_array_handle *handle) |
86ccc354 MV |
1935 | Like @code{scm_array_handle_uniform_elements}, but the pointer is good |
1936 | reading and writing. | |
1937 | @end deftypefn | |
1938 | ||
1939 | @deftypefn {C Function} size_t scm_array_handle_uniform_element_size (scm_t_array_handle *handle) | |
1940 | Return the size of one element of the uniform numeric array represented | |
1941 | by @var{handle}. | |
1942 | @end deftypefn | |
1943 | ||
d1f9e107 KR |
1944 | @deftypefn {C Function} {const scm_t_uint8 *} scm_array_handle_u8_elements (scm_t_array_handle *handle) |
1945 | @deftypefnx {C Function} {const scm_t_int8 *} scm_array_handle_s8_elements (scm_t_array_handle *handle) | |
1946 | @deftypefnx {C Function} {const scm_t_uint16 *} scm_array_handle_u16_elements (scm_t_array_handle *handle) | |
1947 | @deftypefnx {C Function} {const scm_t_int16 *} scm_array_handle_s16_elements (scm_t_array_handle *handle) | |
1948 | @deftypefnx {C Function} {const scm_t_uint32 *} scm_array_handle_u32_elements (scm_t_array_handle *handle) | |
1949 | @deftypefnx {C Function} {const scm_t_int32 *} scm_array_handle_s32_elements (scm_t_array_handle *handle) | |
1950 | @deftypefnx {C Function} {const scm_t_uint64 *} scm_array_handle_u64_elements (scm_t_array_handle *handle) | |
1951 | @deftypefnx {C Function} {const scm_t_int64 *} scm_array_handle_s64_elements (scm_t_array_handle *handle) | |
1952 | @deftypefnx {C Function} {const float *} scm_array_handle_f32_elements (scm_t_array_handle *handle) | |
1953 | @deftypefnx {C Function} {const double *} scm_array_handle_f64_elements (scm_t_array_handle *handle) | |
1954 | @deftypefnx {C Function} {const float *} scm_array_handle_c32_elements (scm_t_array_handle *handle) | |
1955 | @deftypefnx {C Function} {const double *} scm_array_handle_c64_elements (scm_t_array_handle *handle) | |
86ccc354 MV |
1956 | Return a pointer to the elements of a uniform numeric array of the |
1957 | indicated kind for reading. This pointer is valid as long as the array | |
1958 | remains reserved. | |
1959 | ||
1960 | The pointers for @code{c32} and @code{c64} uniform numeric arrays point | |
1961 | to pairs of floating point numbers. The even index holds the real part, | |
1962 | the odd index the imaginary part of the complex number. | |
1963 | @end deftypefn | |
1964 | ||
d1f9e107 KR |
1965 | @deftypefn {C Function} {scm_t_uint8 *} scm_array_handle_u8_writable_elements (scm_t_array_handle *handle) |
1966 | @deftypefnx {C Function} {scm_t_int8 *} scm_array_handle_s8_writable_elements (scm_t_array_handle *handle) | |
1967 | @deftypefnx {C Function} {scm_t_uint16 *} scm_array_handle_u16_writable_elements (scm_t_array_handle *handle) | |
1968 | @deftypefnx {C Function} {scm_t_int16 *} scm_array_handle_s16_writable_elements (scm_t_array_handle *handle) | |
1969 | @deftypefnx {C Function} {scm_t_uint32 *} scm_array_handle_u32_writable_elements (scm_t_array_handle *handle) | |
1970 | @deftypefnx {C Function} {scm_t_int32 *} scm_array_handle_s32_writable_elements (scm_t_array_handle *handle) | |
1971 | @deftypefnx {C Function} {scm_t_uint64 *} scm_array_handle_u64_writable_elements (scm_t_array_handle *handle) | |
1972 | @deftypefnx {C Function} {scm_t_int64 *} scm_array_handle_s64_writable_elements (scm_t_array_handle *handle) | |
1973 | @deftypefnx {C Function} {float *} scm_array_handle_f32_writable_elements (scm_t_array_handle *handle) | |
1974 | @deftypefnx {C Function} {double *} scm_array_handle_f64_writable_elements (scm_t_array_handle *handle) | |
1975 | @deftypefnx {C Function} {float *} scm_array_handle_c32_writable_elements (scm_t_array_handle *handle) | |
1976 | @deftypefnx {C Function} {double *} scm_array_handle_c64_writable_elements (scm_t_array_handle *handle) | |
86ccc354 MV |
1977 | Like @code{scm_array_handle_<kind>_elements}, but the pointer is good |
1978 | for reading and writing. | |
1979 | @end deftypefn | |
1980 | ||
d1f9e107 | 1981 | @deftypefn {C Function} {const scm_t_uint32 *} scm_array_handle_bit_elements (scm_t_array_handle *handle) |
86ccc354 MV |
1982 | Return a pointer to the words that store the bits of the represented |
1983 | array, which must be a bit array. | |
1984 | ||
1985 | Unlike other arrays, bit arrays have an additional offset that must be | |
1986 | figured into index calculations. That offset is returned by | |
1987 | @code{scm_array_handle_bit_elements_offset}. | |
1988 | ||
1989 | To find a certain bit you first need to calculate its position as | |
1990 | explained above for @code{scm_array_handle_dims} and then add the | |
1991 | offset. This gives the absolute position of the bit, which is always a | |
1992 | non-negative integer. | |
1993 | ||
1994 | Each word of the bit array storage block contains exactly 32 bits, with | |
1995 | the least significant bit in that word having the lowest absolute | |
1996 | position number. The next word contains the next 32 bits. | |
1997 | ||
1998 | Thus, the following code can be used to access a bit whose position | |
1999 | according to @code{scm_array_handle_dims} is given in @var{pos}: | |
2000 | ||
2001 | @example | |
2002 | SCM bit_array; | |
2003 | scm_t_array_handle handle; | |
2004 | scm_t_uint32 *bits; | |
2005 | ssize_t pos; | |
2006 | size_t abs_pos; | |
2007 | size_t word_pos, mask; | |
2008 | ||
2009 | scm_array_get_handle (&bit_array, &handle); | |
2010 | bits = scm_array_handle_bit_elements (&handle); | |
2011 | ||
2012 | pos = ... | |
2013 | abs_pos = pos + scm_array_handle_bit_elements_offset (&handle); | |
2014 | word_pos = abs_pos / 32; | |
2015 | mask = 1L << (abs_pos % 32); | |
2016 | ||
2017 | if (bits[word_pos] & mask) | |
2018 | /* bit is set. */ | |
2019 | ||
2020 | scm_array_handle_release (&handle); | |
2021 | @end example | |
2022 | ||
2023 | @end deftypefn | |
2024 | ||
d1f9e107 | 2025 | @deftypefn {C Function} {scm_t_uint32 *} scm_array_handle_bit_writable_elements (scm_t_array_handle *handle) |
86ccc354 MV |
2026 | Like @code{scm_array_handle_bit_elements} but the pointer is good for |
2027 | reading and writing. You must take care not to modify bits outside of | |
2028 | the allowed index range of the array, even for contiguous arrays. | |
2029 | @end deftypefn | |
52d28fc2 | 2030 | |
22ec6a31 LC |
2031 | @node VLists |
2032 | @subsection VLists | |
2033 | ||
2034 | @cindex vlist | |
2035 | ||
2036 | The @code{(ice-9 vlist)} module provides an implementation of the @dfn{VList} | |
2037 | data structure designed by Phil Bagwell in 2002. VLists are immutable lists, | |
2038 | which can contain any Scheme object. They improve on standard Scheme linked | |
2039 | lists in several areas: | |
2040 | ||
2041 | @itemize | |
2042 | @item | |
2043 | Random access has typically constant-time complexity. | |
2044 | ||
2045 | @item | |
2046 | Computing the length of a VList has time complexity logarithmic in the number of | |
2047 | elements. | |
2048 | ||
2049 | @item | |
2050 | VLists use less storage space than standard lists. | |
2051 | ||
2052 | @item | |
2053 | VList elements are stored in contiguous regions, which improves memory locality | |
2054 | and leads to more efficient use of hardware caches. | |
2055 | @end itemize | |
2056 | ||
2057 | The idea behind VLists is to store vlist elements in increasingly large | |
2058 | contiguous blocks (implemented as vectors here). These blocks are linked to one | |
2059 | another using a pointer to the next block and an offset within that block. The | |
2060 | size of these blocks form a geometric series with ratio | |
2061 | @code{block-growth-factor} (2 by default). | |
2062 | ||
2063 | The VList structure also serves as the basis for the @dfn{VList-based hash | |
2064 | lists} or ``vhashes'', an immutable dictionary type (@pxref{VHashes}). | |
2065 | ||
2066 | However, the current implementation in @code{(ice-9 vlist)} has several | |
2067 | noteworthy shortcomings: | |
2068 | ||
2069 | @itemize | |
2070 | ||
2071 | @item | |
2072 | It is @emph{not} thread-safe. Although operations on vlists are all | |
2073 | @dfn{referentially transparent} (i.e., purely functional), adding elements to a | |
2074 | vlist with @code{vlist-cons} mutates part of its internal structure, which makes | |
2075 | it non-thread-safe. This could be fixed, but it would slow down | |
2076 | @code{vlist-cons}. | |
2077 | ||
2078 | @item | |
2079 | @code{vlist-cons} always allocates at least as much memory as @code{cons}. | |
2080 | Again, Phil Bagwell describes how to fix it, but that would require tuning the | |
2081 | garbage collector in a way that may not be generally beneficial. | |
2082 | ||
2083 | @item | |
2084 | @code{vlist-cons} is a Scheme procedure compiled to bytecode, and it does not | |
2085 | compete with the straightforward C implementation of @code{cons}, and with the | |
2086 | fact that the VM has a special @code{cons} instruction. | |
2087 | ||
2088 | @end itemize | |
2089 | ||
2090 | We hope to address these in the future. | |
2091 | ||
2092 | The programming interface exported by @code{(ice-9 vlist)} is defined below. | |
2093 | Most of it is the same as SRFI-1 with an added @code{vlist-} prefix to function | |
2094 | names. | |
2095 | ||
2096 | @deffn {Scheme Procedure} vlist? obj | |
2097 | Return true if @var{obj} is a VList. | |
2098 | @end deffn | |
2099 | ||
2100 | @defvr {Scheme Variable} vlist-null | |
2101 | The empty VList. Note that it's possible to create an empty VList not | |
2102 | @code{eq?} to @code{vlist-null}; thus, callers should always use | |
2103 | @code{vlist-null?} when testing whether a VList is empty. | |
2104 | @end defvr | |
2105 | ||
2106 | @deffn {Scheme Procedure} vlist-null? vlist | |
2107 | Return true if @var{vlist} is empty. | |
2108 | @end deffn | |
2109 | ||
2110 | @deffn {Scheme Procedure} vlist-cons item vlist | |
2111 | Return a new vlist with @var{item} as its head and @var{vlist} as its tail. | |
2112 | @end deffn | |
2113 | ||
2114 | @deffn {Scheme Procedure} vlist-head vlist | |
2115 | Return the head of @var{vlist}. | |
2116 | @end deffn | |
2117 | ||
2118 | @deffn {Scheme Procedure} vlist-tail vlist | |
2119 | Return the tail of @var{vlist}. | |
2120 | @end deffn | |
2121 | ||
2122 | @defvr {Scheme Variable} block-growth-factor | |
2123 | A fluid that defines the growth factor of VList blocks, 2 by default. | |
2124 | @end defvr | |
2125 | ||
2126 | The functions below provide the usual set of higher-level list operations. | |
2127 | ||
2128 | @deffn {Scheme Procedure} vlist-fold proc init vlist | |
2129 | @deffnx {Scheme Procedure} vlist-fold-right proc init vlist | |
2130 | Fold over @var{vlist}, calling @var{proc} for each element, as for SRFI-1 | |
2131 | @code{fold} and @code{fold-right} (@pxref{SRFI-1, @code{fold}}). | |
2132 | @end deffn | |
2133 | ||
2134 | @deffn {Scheme Procedure} vlist-ref vlist index | |
2135 | Return the element at index @var{index} in @var{vlist}. This is typically a | |
2136 | constant-time operation. | |
2137 | @end deffn | |
2138 | ||
2139 | @deffn {Scheme Procedure} vlist-length vlist | |
2140 | Return the length of @var{vlist}. This is typically logarithmic in the number | |
2141 | of elements in @var{vlist}. | |
2142 | @end deffn | |
2143 | ||
2144 | @deffn {Scheme Procedure} vlist-reverse vlist | |
2145 | Return a new @var{vlist} whose content are those of @var{vlist} in reverse | |
2146 | order. | |
2147 | @end deffn | |
2148 | ||
2149 | @deffn {Scheme Procedure} vlist-map proc vlist | |
2150 | Map @var{proc} over the elements of @var{vlist} and return a new vlist. | |
2151 | @end deffn | |
2152 | ||
2153 | @deffn {Scheme Procedure} vlist-for-each proc vlist | |
2154 | Call @var{proc} on each element of @var{vlist}. The result is unspecified. | |
2155 | @end deffn | |
2156 | ||
2157 | @deffn {Scheme Procedure} vlist-drop vlist count | |
2158 | Return a new vlist that does not contain the @var{count} first elements of | |
2159 | @var{vlist}. This is typically a constant-time operation. | |
2160 | @end deffn | |
2161 | ||
2162 | @deffn {Scheme Procedure} vlist-take vlist count | |
2163 | Return a new vlist that contains only the @var{count} first elements of | |
2164 | @var{vlist}. | |
2165 | @end deffn | |
2166 | ||
2167 | @deffn {Scheme Procedure} vlist-filter pred vlist | |
2168 | Return a new vlist containing all the elements from @var{vlist} that satisfy | |
2169 | @var{pred}. | |
2170 | @end deffn | |
2171 | ||
2172 | @deffn {Scheme Procedure} vlist-delete x vlist [equal?] | |
2173 | Return a new vlist corresponding to @var{vlist} without the elements | |
2174 | @var{equal?} to @var{x}. | |
2175 | @end deffn | |
2176 | ||
2177 | @deffn {Scheme Procedure} vlist-unfold p f g seed [tail-gen] | |
2178 | @deffnx {Scheme Procedure} vlist-unfold-right p f g seed [tail] | |
2179 | Return a new vlist, as for SRFI-1 @code{unfold} and @code{unfold-right} | |
2180 | (@pxref{SRFI-1, @code{unfold}}). | |
2181 | @end deffn | |
2182 | ||
df0a1002 | 2183 | @deffn {Scheme Procedure} vlist-append vlist @dots{} |
22ec6a31 LC |
2184 | Append the given vlists and return the resulting vlist. |
2185 | @end deffn | |
2186 | ||
2187 | @deffn {Scheme Procedure} list->vlist lst | |
2188 | Return a new vlist whose contents correspond to @var{lst}. | |
2189 | @end deffn | |
2190 | ||
2191 | @deffn {Scheme Procedure} vlist->list vlist | |
2192 | Return a new list whose contents match those of @var{vlist}. | |
2193 | @end deffn | |
2194 | ||
ec7e4f77 LC |
2195 | @node Record Overview |
2196 | @subsection Record Overview | |
2197 | ||
2198 | @cindex record | |
2199 | @cindex structure | |
2200 | ||
2201 | @dfn{Records}, also called @dfn{structures}, are Scheme's primary | |
2202 | mechanism to define new disjoint types. A @dfn{record type} defines a | |
2203 | list of @dfn{fields} that instances of the type consist of. This is like | |
2204 | C's @code{struct}. | |
2205 | ||
2206 | Historically, Guile has offered several different ways to define record | |
2207 | types and to create records, offering different features, and making | |
2208 | different trade-offs. Over the years, each ``standard'' has also come | |
2209 | with its own new record interface, leading to a maze of record APIs. | |
2210 | ||
2211 | At the highest level is SRFI-9, a high-level record interface | |
71539c1c MW |
2212 | implemented by most Scheme implementations (@pxref{SRFI-9 Records}). It |
2213 | defines a simple and efficient syntactic abstraction of record types and | |
2214 | their associated type predicate, fields, and field accessors. SRFI-9 is | |
ec7e4f77 LC |
2215 | suitable for most uses, and this is the recommended way to create record |
2216 | types in Guile. Similar high-level record APIs include SRFI-35 | |
2217 | (@pxref{SRFI-35}) and R6RS records (@pxref{rnrs records syntactic}). | |
2218 | ||
2219 | Then comes Guile's historical ``records'' API (@pxref{Records}). Record | |
2220 | types defined this way are first-class objects. Introspection | |
2221 | facilities are available, allowing users to query the list of fields or | |
2222 | the value of a specific field at run-time, without prior knowledge of | |
2223 | the type. | |
2224 | ||
2225 | Finally, the common denominator of these interfaces is Guile's | |
2226 | @dfn{structure} API (@pxref{Structures}). Guile's structures are the | |
2227 | low-level building block for all other record APIs. Application writers | |
2228 | will normally not need to use it. | |
2229 | ||
2230 | Records created with these APIs may all be pattern-matched using Guile's | |
2231 | standard pattern matcher (@pxref{Pattern Matching}). | |
2232 | ||
2233 | ||
2234 | @node SRFI-9 Records | |
2235 | @subsection SRFI-9 Records | |
2236 | ||
2237 | @cindex SRFI-9 | |
2238 | @cindex record | |
2239 | ||
2240 | SRFI-9 standardizes a syntax for defining new record types and creating | |
2241 | predicate, constructor, and field getter and setter functions. In Guile | |
2242 | this is the recommended option to create new record types (@pxref{Record | |
2243 | Overview}). It can be used with: | |
2244 | ||
2245 | @example | |
2246 | (use-modules (srfi srfi-9)) | |
2247 | @end example | |
2248 | ||
c548da69 | 2249 | @deffn {Scheme Syntax} define-record-type type @* (constructor fieldname @dots{}) @* predicate @* (fieldname accessor [modifier]) @dots{} |
ec7e4f77 LC |
2250 | @sp 1 |
2251 | Create a new record type, and make various @code{define}s for using | |
2252 | it. This syntax can only occur at the top-level, not nested within | |
2253 | some other form. | |
2254 | ||
2255 | @var{type} is bound to the record type, which is as per the return | |
2256 | from the core @code{make-record-type}. @var{type} also provides the | |
2257 | name for the record, as per @code{record-type-name}. | |
2258 | ||
2259 | @var{constructor} is bound to a function to be called as | |
2260 | @code{(@var{constructor} fieldval @dots{})} to create a new record of | |
2261 | this type. The arguments are initial values for the fields, one | |
2262 | argument for each field, in the order they appear in the | |
2263 | @code{define-record-type} form. | |
2264 | ||
2265 | The @var{fieldname}s provide the names for the record fields, as per | |
2266 | the core @code{record-type-fields} etc, and are referred to in the | |
2267 | subsequent accessor/modifier forms. | |
2268 | ||
2269 | @var{predicate} is bound to a function to be called as | |
2270 | @code{(@var{predicate} obj)}. It returns @code{#t} or @code{#f} | |
2271 | according to whether @var{obj} is a record of this type. | |
2272 | ||
2273 | Each @var{accessor} is bound to a function to be called | |
2274 | @code{(@var{accessor} record)} to retrieve the respective field from a | |
2275 | @var{record}. Similarly each @var{modifier} is bound to a function to | |
2276 | be called @code{(@var{modifier} record val)} to set the respective | |
2277 | field in a @var{record}. | |
2278 | @end deffn | |
2279 | ||
2280 | @noindent | |
2281 | An example will illustrate typical usage, | |
2282 | ||
2283 | @example | |
c548da69 | 2284 | (define-record-type <employee> |
ec7e4f77 LC |
2285 | (make-employee name age salary) |
2286 | employee? | |
c548da69 LC |
2287 | (name employee-name) |
2288 | (age employee-age set-employee-age!) | |
2289 | (salary employee-salary set-employee-salary!)) | |
ec7e4f77 LC |
2290 | @end example |
2291 | ||
2292 | This creates a new employee data type, with name, age and salary | |
2293 | fields. Accessor functions are created for each field, but no | |
2294 | modifier function for the name (the intention in this example being | |
2295 | that it's established only when an employee object is created). These | |
2296 | can all then be used as for example, | |
2297 | ||
2298 | @example | |
c548da69 | 2299 | <employee> @result{} #<record-type <employee>> |
ec7e4f77 LC |
2300 | |
2301 | (define fred (make-employee "Fred" 45 20000.00)) | |
2302 | ||
2303 | (employee? fred) @result{} #t | |
c548da69 LC |
2304 | (employee-age fred) @result{} 45 |
2305 | (set-employee-salary! fred 25000.00) ;; pay rise | |
ec7e4f77 LC |
2306 | @end example |
2307 | ||
2308 | The functions created by @code{define-record-type} are ordinary | |
2309 | top-level @code{define}s. They can be redefined or @code{set!} as | |
2310 | desired, exported from a module, etc. | |
2311 | ||
2312 | @unnumberedsubsubsec Non-toplevel Record Definitions | |
2313 | ||
2314 | The SRFI-9 specification explicitly disallows record definitions in a | |
2315 | non-toplevel context, such as inside @code{lambda} body or inside a | |
2316 | @var{let} block. However, Guile's implementation does not enforce that | |
2317 | restriction. | |
2318 | ||
2319 | @unnumberedsubsubsec Custom Printers | |
2320 | ||
2321 | You may use @code{set-record-type-printer!} to customize the default printing | |
2322 | behavior of records. This is a Guile extension and is not part of SRFI-9. It | |
2323 | is located in the @nicode{(srfi srfi-9 gnu)} module. | |
2324 | ||
67768115 | 2325 | @deffn {Scheme Syntax} set-record-type-printer! name proc |
ec7e4f77 | 2326 | Where @var{type} corresponds to the first argument of @code{define-record-type}, |
67768115 | 2327 | and @var{proc} is a procedure accepting two arguments, the record to print, and |
ec7e4f77 LC |
2328 | an output port. |
2329 | @end deffn | |
2330 | ||
2331 | @noindent | |
2332 | This example prints the employee's name in brackets, for instance @code{[Fred]}. | |
2333 | ||
2334 | @example | |
c548da69 | 2335 | (set-record-type-printer! <employee> |
ec7e4f77 LC |
2336 | (lambda (record port) |
2337 | (write-char #\[ port) | |
c548da69 | 2338 | (display (employee-name record) port) |
ec7e4f77 LC |
2339 | (write-char #\] port))) |
2340 | @end example | |
22ec6a31 | 2341 | |
a144a7a8 LC |
2342 | @unnumberedsubsubsec Functional ``Setters'' |
2343 | ||
2344 | @cindex functional setters | |
2345 | ||
2346 | When writing code in a functional style, it is desirable to never alter | |
2347 | the contents of records. For such code, a simple way to return new | |
2348 | record instances based on existing ones is highly desirable. | |
2349 | ||
2350 | The @code{(srfi srfi-9 gnu)} module extends SRFI-9 with facilities to | |
2351 | return new record instances based on existing ones, only with one or | |
2352 | more field values changed---@dfn{functional setters}. First, the | |
2353 | @code{define-immutable-record-type} works like | |
2354 | @code{define-record-type}, except that fields are immutable and setters | |
2355 | are defined as functional setters. | |
2356 | ||
2357 | @deffn {Scheme Syntax} define-immutable-record-type type @* (constructor fieldname @dots{}) @* predicate @* (fieldname accessor [modifier]) @dots{} | |
2358 | Define @var{type} as a new record type, like @code{define-record-type}. | |
2359 | However, the record type is made @emph{immutable} (records may not be | |
2360 | mutated, even with @code{struct-set!}), and any @var{modifier} is | |
2361 | defined to be a functional setter---a procedure that returns a new | |
2362 | record instance with the specified field changed, and leaves the | |
2363 | original unchanged (see example below.) | |
2364 | @end deffn | |
2365 | ||
2366 | @noindent | |
2367 | In addition, the generic @code{set-field} and @code{set-fields} macros | |
2368 | may be applied to any SRFI-9 record. | |
2369 | ||
5ec8fc21 | 2370 | @deffn {Scheme Syntax} set-field record (field sub-fields ...) value |
a144a7a8 LC |
2371 | Return a new record of @var{record}'s type whose fields are equal to |
2372 | the corresponding fields of @var{record} except for the one specified by | |
2373 | @var{field}. | |
2374 | ||
2375 | @var{field} must be the name of the getter corresponding to the field of | |
2376 | @var{record} being ``set''. Subsequent @var{sub-fields} must be record | |
2377 | getters designating sub-fields within that field value to be set (see | |
2378 | example below.) | |
2379 | @end deffn | |
2380 | ||
2381 | @deffn {Scheme Syntax} set-fields record ((field sub-fields ...) value) ... | |
2382 | Like @code{set-field}, but can be used to set more than one field at a | |
2383 | time. This expands to code that is more efficient than a series of | |
2384 | single @code{set-field} calls. | |
2385 | @end deffn | |
2386 | ||
2387 | To illustrate the use of functional setters, let's assume these two | |
2388 | record type definitions: | |
2389 | ||
2390 | @example | |
2391 | (define-record-type <address> | |
2392 | (address street city country) | |
2393 | address? | |
2394 | (street address-street) | |
2395 | (city address-city) | |
2396 | (country address-country)) | |
2397 | ||
2398 | (define-immutable-record-type <person> | |
2399 | (person age email address) | |
2400 | person? | |
2401 | (age person-age set-person-age) | |
2402 | (email person-email set-person-email) | |
2403 | (address person-address set-person-address)) | |
2404 | @end example | |
2405 | ||
2406 | @noindent | |
2407 | First, note that the @code{<person>} record type definition introduces | |
2408 | named functional setters. These may be used like this: | |
2409 | ||
2410 | @example | |
2411 | (define fsf-address | |
2412 | (address "Franklin Street" "Boston" "USA")) | |
2413 | ||
2414 | (define rms | |
2415 | (person 30 "rms@@gnu.org" fsf-address)) | |
2416 | ||
2417 | (and (equal? (set-person-age rms 60) | |
2418 | (person 60 "rms@@gnu.org" fsf-address)) | |
2419 | (= (person-age rms) 30)) | |
2420 | @result{} #t | |
2421 | @end example | |
2422 | ||
2423 | @noindent | |
2424 | Here, the original @code{<person>} record, to which @var{rms} is bound, | |
2425 | is left unchanged. | |
2426 | ||
2427 | Now, suppose we want to change both the street and age of @var{rms}. | |
2428 | This can be achieved using @code{set-fields}: | |
2429 | ||
2430 | @example | |
2431 | (set-fields rms | |
2432 | ((person-age) 60) | |
2433 | ((person-address address-street) "Temple Place")) | |
2434 | @result{} #<<person> age: 60 email: "rms@@gnu.org" | |
2435 | address: #<<address> street: "Temple Place" city: "Boston" country: "USA">> | |
2436 | @end example | |
2437 | ||
2438 | @noindent | |
2439 | Notice how the above changed two fields of @var{rms}, including the | |
2440 | @code{street} field of its @code{address} field, in a concise way. Also | |
2441 | note that @code{set-fields} works equally well for types defined with | |
2442 | just @code{define-record-type}. | |
22ec6a31 | 2443 | |
e6b226b9 MV |
2444 | @node Records |
2445 | @subsection Records | |
07d83abe | 2446 | |
e6b226b9 MV |
2447 | A @dfn{record type} is a first class object representing a user-defined |
2448 | data type. A @dfn{record} is an instance of a record type. | |
07d83abe | 2449 | |
febc7d2f AW |
2450 | Note that in many ways, this interface is too low-level for every-day |
2451 | use. Most uses of records are better served by SRFI-9 records. | |
71539c1c | 2452 | @xref{SRFI-9 Records}. |
febc7d2f | 2453 | |
e6b226b9 MV |
2454 | @deffn {Scheme Procedure} record? obj |
2455 | Return @code{#t} if @var{obj} is a record of any type and @code{#f} | |
2456 | otherwise. | |
07d83abe | 2457 | |
e6b226b9 MV |
2458 | Note that @code{record?} may be true of any Scheme value; there is no |
2459 | promise that records are disjoint with other Scheme types. | |
2460 | @end deffn | |
07d83abe | 2461 | |
bf5df489 KR |
2462 | @deffn {Scheme Procedure} make-record-type type-name field-names [print] |
2463 | Create and return a new @dfn{record-type descriptor}. | |
2464 | ||
2465 | @var{type-name} is a string naming the type. Currently it's only used | |
2466 | in the printed representation of records, and in diagnostics. | |
2467 | @var{field-names} is a list of symbols naming the fields of a record | |
2468 | of the type. Duplicates are not allowed among these symbols. | |
2469 | ||
2470 | @example | |
2471 | (make-record-type "employee" '(name age salary)) | |
2472 | @end example | |
2473 | ||
2474 | The optional @var{print} argument is a function used by | |
2475 | @code{display}, @code{write}, etc, for printing a record of the new | |
2476 | type. It's called as @code{(@var{print} record port)} and should look | |
2477 | at @var{record} and write to @var{port}. | |
07d83abe MV |
2478 | @end deffn |
2479 | ||
e6b226b9 MV |
2480 | @deffn {Scheme Procedure} record-constructor rtd [field-names] |
2481 | Return a procedure for constructing new members of the type represented | |
2482 | by @var{rtd}. The returned procedure accepts exactly as many arguments | |
2483 | as there are symbols in the given list, @var{field-names}; these are | |
2484 | used, in order, as the initial values of those fields in a new record, | |
2485 | which is returned by the constructor procedure. The values of any | |
2486 | fields not named in that list are unspecified. The @var{field-names} | |
2487 | argument defaults to the list of field names in the call to | |
2488 | @code{make-record-type} that created the type represented by @var{rtd}; | |
2489 | if the @var{field-names} argument is provided, it is an error if it | |
2490 | contains any duplicates or any symbols not in the default list. | |
2491 | @end deffn | |
07d83abe | 2492 | |
e6b226b9 MV |
2493 | @deffn {Scheme Procedure} record-predicate rtd |
2494 | Return a procedure for testing membership in the type represented by | |
2495 | @var{rtd}. The returned procedure accepts exactly one argument and | |
2496 | returns a true value if the argument is a member of the indicated record | |
2497 | type; it returns a false value otherwise. | |
07d83abe MV |
2498 | @end deffn |
2499 | ||
e6b226b9 MV |
2500 | @deffn {Scheme Procedure} record-accessor rtd field-name |
2501 | Return a procedure for reading the value of a particular field of a | |
2502 | member of the type represented by @var{rtd}. The returned procedure | |
2503 | accepts exactly one argument which must be a record of the appropriate | |
2504 | type; it returns the current value of the field named by the symbol | |
2505 | @var{field-name} in that record. The symbol @var{field-name} must be a | |
2506 | member of the list of field-names in the call to @code{make-record-type} | |
2507 | that created the type represented by @var{rtd}. | |
07d83abe MV |
2508 | @end deffn |
2509 | ||
e6b226b9 MV |
2510 | @deffn {Scheme Procedure} record-modifier rtd field-name |
2511 | Return a procedure for writing the value of a particular field of a | |
2512 | member of the type represented by @var{rtd}. The returned procedure | |
2513 | accepts exactly two arguments: first, a record of the appropriate type, | |
2514 | and second, an arbitrary Scheme value; it modifies the field named by | |
2515 | the symbol @var{field-name} in that record to contain the given value. | |
2516 | The returned value of the modifier procedure is unspecified. The symbol | |
2517 | @var{field-name} must be a member of the list of field-names in the call | |
2518 | to @code{make-record-type} that created the type represented by | |
2519 | @var{rtd}. | |
2520 | @end deffn | |
07d83abe | 2521 | |
e6b226b9 MV |
2522 | @deffn {Scheme Procedure} record-type-descriptor record |
2523 | Return a record-type descriptor representing the type of the given | |
2524 | record. That is, for example, if the returned descriptor were passed to | |
2525 | @code{record-predicate}, the resulting predicate would return a true | |
2526 | value when passed the given record. Note that it is not necessarily the | |
2527 | case that the returned descriptor is the one that was passed to | |
2528 | @code{record-constructor} in the call that created the constructor | |
2529 | procedure that created the given record. | |
2530 | @end deffn | |
2531 | ||
2532 | @deffn {Scheme Procedure} record-type-name rtd | |
2533 | Return the type-name associated with the type represented by rtd. The | |
2534 | returned value is @code{eqv?} to the @var{type-name} argument given in | |
2535 | the call to @code{make-record-type} that created the type represented by | |
2536 | @var{rtd}. | |
2537 | @end deffn | |
2538 | ||
2539 | @deffn {Scheme Procedure} record-type-fields rtd | |
2540 | Return a list of the symbols naming the fields in members of the type | |
2541 | represented by @var{rtd}. The returned value is @code{equal?} to the | |
2542 | field-names argument given in the call to @code{make-record-type} that | |
2543 | created the type represented by @var{rtd}. | |
2544 | @end deffn | |
2545 | ||
2546 | ||
2547 | @node Structures | |
2548 | @subsection Structures | |
2549 | @tpindex Structures | |
2550 | ||
bf5df489 | 2551 | A @dfn{structure} is a first class data type which holds Scheme values |
febc7d2f AW |
2552 | or C words in fields numbered 0 upwards. A @dfn{vtable} is a structure |
2553 | that represents a structure type, giving field types and permissions, | |
2554 | and an optional print function for @code{write} etc. | |
e6b226b9 | 2555 | |
febc7d2f AW |
2556 | Structures are lower level than records (@pxref{Records}). Usually, |
2557 | when you need to represent structured data, you just want to use | |
2558 | records. But sometimes you need to implement new kinds of structured | |
2559 | data abstractions, and for that purpose structures are useful. Indeed, | |
2560 | records in Guile are implemented with structures. | |
e6b226b9 MV |
2561 | |
2562 | @menu | |
41a9e882 AW |
2563 | * Vtables:: |
2564 | * Structure Basics:: | |
2565 | * Vtable Contents:: | |
2566 | * Meta-Vtables:: | |
2567 | * Vtable Example:: | |
2568 | * Tail Arrays:: | |
e6b226b9 MV |
2569 | @end menu |
2570 | ||
d1927913 | 2571 | @node Vtables |
bf5df489 | 2572 | @subsubsection Vtables |
e6b226b9 | 2573 | |
bf5df489 KR |
2574 | A vtable is a structure type, specifying its layout, and other |
2575 | information. A vtable is actually itself a structure, but there's no | |
ecb87335 | 2576 | need to worry about that initially (@pxref{Vtable Contents}.) |
e6b226b9 | 2577 | |
bf5df489 KR |
2578 | @deffn {Scheme Procedure} make-vtable fields [print] |
2579 | Create a new vtable. | |
ad97642e | 2580 | |
bf5df489 KR |
2581 | @var{fields} is a string describing the fields in the structures to be |
2582 | created. Each field is represented by two characters, a type letter | |
2583 | and a permissions letter, for example @code{"pw"}. The types are as | |
2584 | follows. | |
e6b226b9 MV |
2585 | |
2586 | @itemize @bullet{} | |
bf5df489 KR |
2587 | @item |
2588 | @code{p} -- a Scheme value. ``p'' stands for ``protected'' meaning | |
2589 | it's protected against garbage collection. | |
e6b226b9 | 2590 | |
bf5df489 KR |
2591 | @item |
2592 | @code{u} -- an arbitrary word of data (an @code{scm_t_bits}). At the | |
2593 | Scheme level it's read and written as an unsigned integer. ``u'' | |
2594 | stands for ``uninterpreted'' (it's not treated as a Scheme value), or | |
2595 | ``unprotected'' (it's not marked during GC), or ``unsigned long'' (its | |
2596 | size), or all of these things. | |
e6b226b9 | 2597 | |
bf5df489 KR |
2598 | @item |
2599 | @code{s} -- a self-reference. Such a field holds the @code{SCM} value | |
2600 | of the structure itself (a circular reference). This can be useful in | |
2601 | C code where you might have a pointer to the data array, and want to | |
2602 | get the Scheme @code{SCM} handle for the structure. In Scheme code it | |
2603 | has no use. | |
e6b226b9 MV |
2604 | @end itemize |
2605 | ||
bf5df489 | 2606 | The second letter for each field is a permission code, |
e6b226b9 MV |
2607 | |
2608 | @itemize @bullet{} | |
bf5df489 KR |
2609 | @item |
2610 | @code{w} -- writable, the field can be read and written. | |
2611 | @item | |
2612 | @code{r} -- read-only, the field can be read but not written. | |
2613 | @item | |
2614 | @code{o} -- opaque, the field can be neither read nor written at the | |
2615 | Scheme level. This can be used for fields which should only be used | |
2616 | from C code. | |
e6b226b9 MV |
2617 | @end itemize |
2618 | ||
febc7d2f AW |
2619 | Here are some examples. @xref{Tail Arrays}, for information on the |
2620 | legacy tail array facility. | |
e6b226b9 | 2621 | |
bf5df489 KR |
2622 | @example |
2623 | (make-vtable "pw") ;; one writable field | |
2624 | (make-vtable "prpw") ;; one read-only and one writable | |
2625 | (make-vtable "pwuwuw") ;; one scheme and two uninterpreted | |
bf5df489 | 2626 | @end example |
e6b226b9 | 2627 | |
bf5df489 KR |
2628 | The optional @var{print} argument is a function called by |
2629 | @code{display} and @code{write} (etc) to give a printed representation | |
2630 | of a structure created from this vtable. It's called | |
2631 | @code{(@var{print} struct port)} and should look at @var{struct} and | |
2632 | write to @var{port}. The default print merely gives a form like | |
2633 | @samp{#<struct ADDR:ADDR>} with a pair of machine addresses. | |
e6b226b9 | 2634 | |
bf5df489 KR |
2635 | The following print function for example shows the two fields of its |
2636 | structure. | |
e6b226b9 | 2637 | |
bf5df489 KR |
2638 | @example |
2639 | (make-vtable "prpw" | |
2640 | (lambda (struct port) | |
41a9e882 AW |
2641 | (format port "#<~a and ~a>" |
2642 | (struct-ref struct 0) | |
2643 | (struct-ref struct 1)))) | |
bf5df489 KR |
2644 | @end example |
2645 | @end deffn | |
e6b226b9 | 2646 | |
e6b226b9 | 2647 | |
d1927913 | 2648 | @node Structure Basics |
bf5df489 | 2649 | @subsubsection Structure Basics |
07d83abe | 2650 | |
bf5df489 KR |
2651 | This section describes the basic procedures for working with |
2652 | structures. @code{make-struct} creates a structure, and | |
febc7d2f | 2653 | @code{struct-ref} and @code{struct-set!} access its fields. |
bf5df489 | 2654 | |
df0a1002 | 2655 | @deffn {Scheme Procedure} make-struct vtable tail-size init @dots{} |
febc7d2f | 2656 | @deffnx {Scheme Procedure} make-struct/no-tail vtable init @dots{} |
bf5df489 KR |
2657 | Create a new structure, with layout per the given @var{vtable} |
2658 | (@pxref{Vtables}). | |
2659 | ||
bf5df489 | 2660 | The optional @var{init}@dots{} arguments are initial values for the |
febc7d2f | 2661 | fields of the structure. This is the only way to |
bf5df489 KR |
2662 | put values in read-only fields. If there are fewer @var{init} |
2663 | arguments than fields then the defaults are @code{#f} for a Scheme | |
2664 | field (type @code{p}) or 0 for an uninterpreted field (type @code{u}). | |
2665 | ||
febc7d2f AW |
2666 | Structures also have the ability to allocate a variable number of |
2667 | additional cells at the end, at their tails. However, this legacy | |
2668 | @dfn{tail array} facilty is confusing and inefficient, and so we do not | |
2669 | recommend it. @xref{Tail Arrays}, for more on the legacy tail array | |
2670 | interface. | |
2671 | ||
bf5df489 KR |
2672 | Type @code{s} self-reference fields, permission @code{o} opaque |
2673 | fields, and the count field of a tail array are all ignored for the | |
2674 | @var{init} arguments, ie.@: an argument is not consumed by such a | |
2675 | field. An @code{s} is always set to the structure itself, an @code{o} | |
2676 | is always set to @code{#f} or 0 (with the intention that C code will | |
2677 | do something to it later), and the tail count is always the given | |
2678 | @var{tail-size}. | |
07d83abe | 2679 | |
bf5df489 | 2680 | For example, |
07d83abe MV |
2681 | |
2682 | @example | |
bf5df489 KR |
2683 | (define v (make-vtable "prpwpw")) |
2684 | (define s (make-struct v 0 123 "abc" 456)) | |
2685 | (struct-ref s 0) @result{} 123 | |
2686 | (struct-ref s 1) @result{} "abc" | |
07d83abe | 2687 | @end example |
bf5df489 | 2688 | @end deffn |
e6b226b9 | 2689 | |
febc7d2f AW |
2690 | @deftypefn {C Function} SCM scm_make_struct (SCM vtable, SCM tail_size, SCM init_list) |
2691 | @deftypefnx {C Function} SCM scm_c_make_struct (SCM vtable, SCM tail_size, SCM init, ...) | |
2692 | @deftypefnx {C Function} SCM scm_c_make_structv (SCM vtable, SCM tail_size, size_t n_inits, scm_t_bits init[]) | |
2693 | There are a few ways to make structures from C. @code{scm_make_struct} | |
2694 | takes a list, @code{scm_c_make_struct} takes variable arguments | |
2695 | terminated with SCM_UNDEFINED, and @code{scm_c_make_structv} takes a | |
2696 | packed array. | |
2697 | @end deftypefn | |
2698 | ||
bf5df489 KR |
2699 | @deffn {Scheme Procedure} struct? obj |
2700 | @deffnx {C Function} scm_struct_p (obj) | |
2701 | Return @code{#t} if @var{obj} is a structure, or @code{#f} if not. | |
2702 | @end deffn | |
e6b226b9 | 2703 | |
bf5df489 KR |
2704 | @deffn {Scheme Procedure} struct-ref struct n |
2705 | @deffnx {C Function} scm_struct_ref (struct, n) | |
2706 | Return the contents of field number @var{n} in @var{struct}. The | |
2707 | first field is number 0. | |
07d83abe | 2708 | |
bf5df489 KR |
2709 | An error is thrown if @var{n} is out of range, or if the field cannot |
2710 | be read because it's @code{o} opaque. | |
2711 | @end deffn | |
e6b226b9 | 2712 | |
bf5df489 KR |
2713 | @deffn {Scheme Procedure} struct-set! struct n value |
2714 | @deffnx {C Function} scm_struct_set_x (struct, n, value) | |
2715 | Set field number @var{n} in @var{struct} to @var{value}. The first | |
2716 | field is number 0. | |
e6b226b9 | 2717 | |
bf5df489 KR |
2718 | An error is thrown if @var{n} is out of range, or if the field cannot |
2719 | be written because it's @code{r} read-only or @code{o} opaque. | |
2720 | @end deffn | |
e6b226b9 | 2721 | |
bf5df489 KR |
2722 | @deffn {Scheme Procedure} struct-vtable struct |
2723 | @deffnx {C Function} scm_struct_vtable (struct) | |
febc7d2f | 2724 | Return the vtable that describes @var{struct}. |
e6b226b9 | 2725 | |
febc7d2f AW |
2726 | The vtable is effectively the type of the structure. See @ref{Vtable |
2727 | Contents}, for more on vtables. | |
e6b226b9 MV |
2728 | @end deffn |
2729 | ||
2730 | ||
d1927913 | 2731 | @node Vtable Contents |
bf5df489 | 2732 | @subsubsection Vtable Contents |
e6b226b9 | 2733 | |
41a9e882 AW |
2734 | A vtable is itself a structure. It has a specific set of fields |
2735 | describing various aspects of its @dfn{instances}: the structures | |
2736 | created from a vtable. Some of the fields are internal to Guile, some | |
2737 | of them are part of the public interface, and there may be additional | |
2738 | fields added on by the user. | |
e6b226b9 | 2739 | |
41a9e882 AW |
2740 | Every vtable has a field for the layout of their instances, a field for |
2741 | the procedure used to print its instances, and a field for the name of | |
2742 | the vtable itself. Access to the layout and printer is exposed directly | |
2743 | via field indexes. Access to the vtable name is exposed via accessor | |
2744 | procedures. | |
e6b226b9 | 2745 | |
bf5df489 KR |
2746 | @defvr {Scheme Variable} vtable-index-layout |
2747 | @defvrx {C Macro} scm_vtable_index_layout | |
2748 | The field number of the layout specification in a vtable. The layout | |
2749 | specification is a symbol like @code{pwpw} formed from the fields | |
2750 | string passed to @code{make-vtable}, or created by | |
41a9e882 | 2751 | @code{make-struct-layout} (@pxref{Meta-Vtables}). |
e6b226b9 | 2752 | |
bf5df489 KR |
2753 | @example |
2754 | (define v (make-vtable "pwpw" 0)) | |
2755 | (struct-ref v vtable-index-layout) @result{} pwpw | |
2756 | @end example | |
e6b226b9 | 2757 | |
bf5df489 KR |
2758 | This field is read-only, since the layout of structures using a vtable |
2759 | cannot be changed. | |
2760 | @end defvr | |
e6b226b9 | 2761 | |
bf5df489 KR |
2762 | @defvr {Scheme Variable} vtable-index-printer |
2763 | @defvrx {C Macro} scm_vtable_index_printer | |
2764 | The field number of the printer function. This field contains @code{#f} | |
2765 | if the default print function should be used. | |
e6b226b9 | 2766 | |
bf5df489 KR |
2767 | @example |
2768 | (define (my-print-func struct port) | |
2769 | ...) | |
2770 | (define v (make-vtable "pwpw" my-print-func)) | |
2771 | (struct-ref v vtable-index-printer) @result{} my-print-func | |
2772 | @end example | |
e6b226b9 | 2773 | |
bf5df489 KR |
2774 | This field is writable, allowing the print function to be changed |
2775 | dynamically. | |
2776 | @end defvr | |
e6b226b9 | 2777 | |
bf5df489 KR |
2778 | @deffn {Scheme Procedure} struct-vtable-name vtable |
2779 | @deffnx {Scheme Procedure} set-struct-vtable-name! vtable name | |
2780 | @deffnx {C Function} scm_struct_vtable_name (vtable) | |
2781 | @deffnx {C Function} scm_set_struct_vtable_name_x (vtable, name) | |
2782 | Get or set the name of @var{vtable}. @var{name} is a symbol and is | |
2783 | used in the default print function when printing structures created | |
2784 | from @var{vtable}. | |
e6b226b9 | 2785 | |
bf5df489 KR |
2786 | @example |
2787 | (define v (make-vtable "pw")) | |
2788 | (set-struct-vtable-name! v 'my-name) | |
e6b226b9 | 2789 | |
bf5df489 KR |
2790 | (define s (make-struct v 0)) |
2791 | (display s) @print{} #<my-name b7ab3ae0:b7ab3730> | |
2792 | @end example | |
2793 | @end deffn | |
e6b226b9 | 2794 | |
e6b226b9 | 2795 | |
41a9e882 AW |
2796 | @node Meta-Vtables |
2797 | @subsubsection Meta-Vtables | |
e6b226b9 | 2798 | |
41a9e882 AW |
2799 | As a structure, a vtable also has a vtable, which is also a structure. |
2800 | Structures, their vtables, the vtables of the vtables, and so on form a | |
2801 | tree of structures. Making a new structure adds a leaf to the tree, and | |
2802 | if that structure is a vtable, it may be used to create other leaves. | |
e6b226b9 | 2803 | |
41a9e882 AW |
2804 | If you traverse up the tree of vtables, via calling |
2805 | @code{struct-vtable}, eventually you reach a root which is the vtable of | |
2806 | itself: | |
e6b226b9 | 2807 | |
bf5df489 | 2808 | @example |
41a9e882 AW |
2809 | scheme@@(guile-user)> (current-module) |
2810 | $1 = #<directory (guile-user) 221b090> | |
2811 | scheme@@(guile-user)> (struct-vtable $1) | |
2812 | $2 = #<record-type module> | |
2813 | scheme@@(guile-user)> (struct-vtable $2) | |
2814 | $3 = #<<standard-vtable> 12c30a0> | |
2815 | scheme@@(guile-user)> (struct-vtable $3) | |
2816 | $4 = #<<standard-vtable> 12c3fa0> | |
2817 | scheme@@(guile-user)> (struct-vtable $4) | |
2818 | $5 = #<<standard-vtable> 12c3fa0> | |
2819 | scheme@@(guile-user)> <standard-vtable> | |
2820 | $6 = #<<standard-vtable> 12c3fa0> | |
bf5df489 | 2821 | @end example |
e6b226b9 | 2822 | |
41a9e882 AW |
2823 | In this example, we can say that @code{$1} is an instance of @code{$2}, |
2824 | @code{$2} is an instance of @code{$3}, @code{$3} is an instance of | |
2825 | @code{$4}, and @code{$4}, strangely enough, is an instance of itself. | |
2826 | The value bound to @code{$4} in this console session also bound to | |
2827 | @code{<standard-vtable>} in the default environment. | |
e6b226b9 | 2828 | |
41a9e882 AW |
2829 | @defvr {Scheme Variable} <standard-vtable> |
2830 | A meta-vtable, useful for making new vtables. | |
2831 | @end defvr | |
e6b226b9 | 2832 | |
41a9e882 AW |
2833 | All of these values are structures. All but @code{$1} are vtables. As |
2834 | @code{$2} is an instance of @code{$3}, and @code{$3} is a vtable, we can | |
2835 | say that @code{$3} is a @dfn{meta-vtable}: a vtable that can create | |
2836 | vtables. | |
bf5df489 | 2837 | |
41a9e882 AW |
2838 | With this definition, we can specify more precisely what a vtable is: a |
2839 | vtable is a structure made from a meta-vtable. Making a structure from | |
2840 | a meta-vtable runs some special checks to ensure that the first field of | |
2841 | the structure is a valid layout. Additionally, if these checks see that | |
2842 | the layout of the child vtable contains all the required fields of a | |
2843 | vtable, in the correct order, then the child vtable will also be a | |
2844 | meta-table, inheriting a magical bit from the parent. | |
2845 | ||
2846 | @deffn {Scheme Procedure} struct-vtable? obj | |
2847 | @deffnx {C Function} scm_struct_vtable_p (obj) | |
2848 | Return @code{#t} if @var{obj} is a vtable structure: an instance of a | |
2849 | meta-vtable. | |
2850 | @end deffn | |
2851 | ||
2852 | @code{<standard-vtable>} is a root of the vtable tree. (Normally there | |
2853 | is only one root in a given Guile process, but due to some legacy | |
2854 | interfaces there may be more than one.) | |
2855 | ||
2856 | The set of required fields of a vtable is the set of fields in the | |
2857 | @code{<standard-vtable>}, and is bound to @code{standard-vtable-fields} | |
2858 | in the default environment. It is possible to create a meta-vtable that | |
2859 | with additional fields in its layout, which can be used to create | |
2860 | vtables with additional data: | |
e6b226b9 | 2861 | |
bf5df489 | 2862 | @example |
41a9e882 AW |
2863 | scheme@@(guile-user)> (struct-ref $3 vtable-index-layout) |
2864 | $6 = pruhsruhpwphuhuhprprpw | |
2865 | scheme@@(guile-user)> (struct-ref $4 vtable-index-layout) | |
2866 | $7 = pruhsruhpwphuhuh | |
2867 | scheme@@(guile-user)> standard-vtable-fields | |
2868 | $8 = "pruhsruhpwphuhuh" | |
2869 | scheme@@(guile-user)> (struct-ref $2 vtable-offset-user) | |
2870 | $9 = module | |
bf5df489 | 2871 | @end example |
e6b226b9 | 2872 | |
41a9e882 AW |
2873 | In this continuation of our earlier example, @code{$2} is a vtable that |
2874 | has extra fields, because its vtable, @code{$3}, was made from a | |
2875 | meta-vtable with an extended layout. @code{vtable-offset-user} is a | |
2876 | convenient definition that indicates the number of fields in | |
2877 | @code{standard-vtable-fields}. | |
2878 | ||
2879 | @defvr {Scheme Variable} standard-vtable-fields | |
2880 | A string containing the orderedq set of fields that a vtable must have. | |
2881 | @end defvr | |
2882 | ||
2883 | @defvr {Scheme Variable} vtable-offset-user | |
2884 | The first index in a vtable that is available for a user. | |
2885 | @end defvr | |
e6b226b9 | 2886 | |
bf5df489 KR |
2887 | @deffn {Scheme Procedure} make-struct-layout fields |
2888 | @deffnx {C Function} scm_make_struct_layout (fields) | |
2889 | Return a structure layout symbol, from a @var{fields} string. | |
2890 | @var{fields} is as described under @code{make-vtable} | |
2891 | (@pxref{Vtables}). An invalid @var{fields} string is an error. | |
41a9e882 AW |
2892 | @end deffn |
2893 | ||
2894 | With these definitions, one can define @code{make-vtable} in this way: | |
e6b226b9 | 2895 | |
bf5df489 | 2896 | @example |
41a9e882 AW |
2897 | (define* (make-vtable fields #:optional printer) |
2898 | (make-struct/no-tail <standard-vtable> | |
2899 | (make-struct-layout fields) | |
2900 | printer)) | |
bf5df489 | 2901 | @end example |
e6b226b9 | 2902 | |
bf5df489 | 2903 | |
41a9e882 AW |
2904 | @node Vtable Example |
2905 | @subsubsection Vtable Example | |
e6b226b9 | 2906 | |
41a9e882 AW |
2907 | Let us bring these points together with an example. Consider a simple |
2908 | object system with single inheritance. Objects will be normal | |
2909 | structures, and classes will be vtables with three extra class fields: | |
2910 | the name of the class, the parent class, and the list of fields. | |
2911 | ||
2912 | So, first we need a meta-vtable that allocates instances with these | |
2913 | extra class fields. | |
2914 | ||
2915 | @example | |
2916 | (define <class> | |
2917 | (make-vtable | |
2918 | (string-append standard-vtable-fields "pwpwpw") | |
2919 | (lambda (x port) | |
2920 | (format port "<<class> ~a>" (class-name x))))) | |
2921 | ||
2922 | (define (class? x) | |
2923 | (and (struct? x) | |
2924 | (eq? (struct-vtable x) <class>))) | |
2925 | @end example | |
2926 | ||
2927 | To make a structure with a specific meta-vtable, we will use | |
2928 | @code{make-struct/no-tail}, passing it the computed instance layout and | |
2929 | printer, as with @code{make-vtable}, and additionally the extra three | |
2930 | class fields. | |
2931 | ||
2932 | @example | |
2933 | (define (make-class name parent fields) | |
2934 | (let* ((fields (compute-fields parent fields)) | |
2935 | (layout (compute-layout fields))) | |
2936 | (make-struct/no-tail <class> | |
2937 | layout | |
2938 | (lambda (x port) | |
2939 | (print-instance x port)) | |
2940 | name | |
2941 | parent | |
2942 | fields))) | |
2943 | @end example | |
2944 | ||
2945 | Instances will store their associated data in slots in the structure: as | |
2946 | many slots as there are fields. The @code{compute-layout} procedure | |
2947 | below can compute a layout, and @code{field-index} returns the slot | |
2948 | corresponding to a field. | |
2949 | ||
2950 | @example | |
2951 | (define-syntax-rule (define-accessor name n) | |
2952 | (define (name obj) | |
2953 | (struct-ref obj n))) | |
2954 | ||
2955 | ;; Accessors for classes | |
2956 | (define-accessor class-name (+ vtable-offset-user 0)) | |
2957 | (define-accessor class-parent (+ vtable-offset-user 1)) | |
2958 | (define-accessor class-fields (+ vtable-offset-user 2)) | |
2959 | ||
2960 | (define (compute-fields parent fields) | |
2961 | (if parent | |
2962 | (append (class-fields parent) fields) | |
2963 | fields)) | |
2964 | ||
2965 | (define (compute-layout fields) | |
2966 | (make-struct-layout | |
2967 | (string-concatenate (make-list (length fields) "pw")))) | |
2968 | ||
2969 | (define (field-index class field) | |
2970 | (list-index (class-fields class) field)) | |
2971 | ||
2972 | (define (print-instance x port) | |
2973 | (format port "<~a" (class-name (struct-vtable x))) | |
2974 | (for-each (lambda (field idx) | |
2975 | (format port " ~a: ~a" field (struct-ref x idx))) | |
2976 | (class-fields (struct-vtable x)) | |
2977 | (iota (length (class-fields (struct-vtable x))))) | |
2978 | (format port ">")) | |
2979 | @end example | |
2980 | ||
2981 | So, at this point we can actually make a few classes: | |
2982 | ||
2983 | @example | |
2984 | (define-syntax-rule (define-class name parent field ...) | |
2985 | (define name (make-class 'name parent '(field ...)))) | |
2986 | ||
2987 | (define-class <surface> #f | |
2988 | width height) | |
2989 | ||
2990 | (define-class <window> <surface> | |
2991 | x y) | |
2992 | @end example | |
2993 | ||
2994 | And finally, make an instance: | |
2995 | ||
2996 | @example | |
2997 | (make-struct/no-tail <window> 400 300 10 20) | |
2998 | @result{} <<window> width: 400 height: 300 x: 10 y: 20> | |
2999 | @end example | |
3000 | ||
3001 | And that's that. Note that there are many possible optimizations and | |
3002 | feature enhancements that can be made to this object system, and the | |
3003 | included GOOPS system does make most of them. For more simple use | |
3004 | cases, the records facility is usually sufficient. But sometimes you | |
3005 | need to make new kinds of data abstractions, and for that purpose, | |
3006 | structs are here. | |
07d83abe | 3007 | |
febc7d2f AW |
3008 | @node Tail Arrays |
3009 | @subsubsection Tail Arrays | |
3010 | ||
3011 | Guile's structures have a facility whereby each instance of a vtable can | |
3012 | contain a variable-length tail array of values. The length of the tail | |
3013 | array is stored in the structure. This facility was originally intended | |
3014 | to allow C code to expose raw C structures with word-sized tail arrays | |
3015 | to Scheme. | |
3016 | ||
3017 | However, the tail array facility is confusing and doesn't work very | |
3018 | well. It is very rarely used, but it insinuates itself into all | |
3019 | invocations of @code{make-struct}. For this reason the clumsily-named | |
3020 | @code{make-struct/no-tail} procedure can actually be more elegant in | |
3021 | actual use, because it doesn't have a random @code{0} argument stuck in | |
3022 | the middle. | |
3023 | ||
3024 | Tail arrays also inhibit optimization by allowing instances to affect | |
3025 | their shapes. In the absence of tail arrays, all instances of a given | |
3026 | vtable have the same number and kinds of fields. This uniformity can be | |
3027 | exploited by the runtime and the optimizer. The presence of tail arrays | |
3028 | make some of these optimizations more difficult. | |
3029 | ||
3030 | Finally, the tail array facility is ad-hoc and does not compose with the | |
3031 | rest of Guile. If a Guile user wants an array with user-specified | |
3032 | length, it's best to use a vector. It is more clear in the code, and | |
3033 | the standard optimization techniques will do a good job with it. | |
3034 | ||
3035 | That said, we should mention some details about the interface. A vtable | |
3036 | that has tail array has upper-case permission descriptors: @code{W}, | |
3037 | @code{R} or @code{O}, correspoding to tail arrays of writable, | |
3038 | read-only, or opaque elements. A tail array permission descriptor may | |
3039 | only appear in the last element of a vtable layout. | |
3040 | ||
3041 | For exampple, @samp{pW} indicates a tail of writable Scheme-valued | |
3042 | fields. The @samp{pW} field itself holds the tail size, and the tail | |
3043 | fields come after it. | |
3044 | ||
3045 | @example | |
3046 | (define v (make-vtable "prpW")) ;; one fixed then a tail array | |
3047 | (define s (make-struct v 6 "fixed field" 'x 'y)) | |
3048 | (struct-ref s 0) @result{} "fixed field" | |
3049 | (struct-ref s 1) @result{} 2 ;; tail size | |
3050 | (struct-ref s 2) @result{} x ;; tail array ... | |
3051 | (struct-ref s 3) @result{} y | |
3052 | (struct-ref s 4) @result{} #f | |
3053 | @end example | |
3054 | ||
07d83abe MV |
3055 | |
3056 | @node Dictionary Types | |
3057 | @subsection Dictionary Types | |
3058 | ||
3059 | A @dfn{dictionary} object is a data structure used to index | |
3060 | information in a user-defined way. In standard Scheme, the main | |
3061 | aggregate data types are lists and vectors. Lists are not really | |
3062 | indexed at all, and vectors are indexed only by number | |
679cceed | 3063 | (e.g.@: @code{(vector-ref foo 5)}). Often you will find it useful |
07d83abe MV |
3064 | to index your data on some other type; for example, in a library |
3065 | catalog you might want to look up a book by the name of its | |
3066 | author. Dictionaries are used to help you organize information in | |
3067 | such a way. | |
3068 | ||
3069 | An @dfn{association list} (or @dfn{alist} for short) is a list of | |
3070 | key-value pairs. Each pair represents a single quantity or | |
3071 | object; the @code{car} of the pair is a key which is used to | |
3072 | identify the object, and the @code{cdr} is the object's value. | |
3073 | ||
3074 | A @dfn{hash table} also permits you to index objects with | |
3075 | arbitrary keys, but in a way that makes looking up any one object | |
3076 | extremely fast. A well-designed hash system makes hash table | |
3077 | lookups almost as fast as conventional array or vector references. | |
3078 | ||
3079 | Alists are popular among Lisp programmers because they use only | |
3080 | the language's primitive operations (lists, @dfn{car}, @dfn{cdr} | |
3081 | and the equality primitives). No changes to the language core are | |
3082 | necessary. Therefore, with Scheme's built-in list manipulation | |
3083 | facilities, it is very convenient to handle data stored in an | |
3084 | association list. Also, alists are highly portable and can be | |
3085 | easily implemented on even the most minimal Lisp systems. | |
3086 | ||
3087 | However, alists are inefficient, especially for storing large | |
3088 | quantities of data. Because we want Guile to be useful for large | |
3089 | software systems as well as small ones, Guile provides a rich set | |
3090 | of tools for using either association lists or hash tables. | |
3091 | ||
3092 | @node Association Lists | |
3093 | @subsection Association Lists | |
3094 | @tpindex Association Lists | |
3095 | @tpindex Alist | |
2c1c0b1f KR |
3096 | @cindex association List |
3097 | @cindex alist | |
ecb87335 | 3098 | @cindex database |
07d83abe MV |
3099 | |
3100 | An association list is a conventional data structure that is often used | |
3101 | to implement simple key-value databases. It consists of a list of | |
3102 | entries in which each entry is a pair. The @dfn{key} of each entry is | |
3103 | the @code{car} of the pair and the @dfn{value} of each entry is the | |
3104 | @code{cdr}. | |
3105 | ||
3106 | @example | |
3107 | ASSOCIATION LIST ::= '( (KEY1 . VALUE1) | |
3108 | (KEY2 . VALUE2) | |
3109 | (KEY3 . VALUE3) | |
3110 | @dots{} | |
3111 | ) | |
3112 | @end example | |
3113 | ||
3114 | @noindent | |
3115 | Association lists are also known, for short, as @dfn{alists}. | |
3116 | ||
3117 | The structure of an association list is just one example of the infinite | |
3118 | number of possible structures that can be built using pairs and lists. | |
3119 | As such, the keys and values in an association list can be manipulated | |
3120 | using the general list structure procedures @code{cons}, @code{car}, | |
3121 | @code{cdr}, @code{set-car!}, @code{set-cdr!} and so on. However, | |
3122 | because association lists are so useful, Guile also provides specific | |
3123 | procedures for manipulating them. | |
3124 | ||
3125 | @menu | |
3126 | * Alist Key Equality:: | |
3127 | * Adding or Setting Alist Entries:: | |
3128 | * Retrieving Alist Entries:: | |
3129 | * Removing Alist Entries:: | |
3130 | * Sloppy Alist Functions:: | |
3131 | * Alist Example:: | |
3132 | @end menu | |
3133 | ||
3134 | @node Alist Key Equality | |
3135 | @subsubsection Alist Key Equality | |
3136 | ||
3137 | All of Guile's dedicated association list procedures, apart from | |
3138 | @code{acons}, come in three flavours, depending on the level of equality | |
3139 | that is required to decide whether an existing key in the association | |
3140 | list is the same as the key that the procedure call uses to identify the | |
3141 | required entry. | |
3142 | ||
3143 | @itemize @bullet | |
3144 | @item | |
3145 | Procedures with @dfn{assq} in their name use @code{eq?} to determine key | |
3146 | equality. | |
3147 | ||
3148 | @item | |
3149 | Procedures with @dfn{assv} in their name use @code{eqv?} to determine | |
3150 | key equality. | |
3151 | ||
3152 | @item | |
3153 | Procedures with @dfn{assoc} in their name use @code{equal?} to | |
3154 | determine key equality. | |
3155 | @end itemize | |
3156 | ||
3157 | @code{acons} is an exception because it is used to build association | |
3158 | lists which do not require their entries' keys to be unique. | |
3159 | ||
3160 | @node Adding or Setting Alist Entries | |
3161 | @subsubsection Adding or Setting Alist Entries | |
3162 | ||
3163 | @code{acons} adds a new entry to an association list and returns the | |
3164 | combined association list. The combined alist is formed by consing the | |
3165 | new entry onto the head of the alist specified in the @code{acons} | |
3166 | procedure call. So the specified alist is not modified, but its | |
3167 | contents become shared with the tail of the combined alist that | |
3168 | @code{acons} returns. | |
3169 | ||
3170 | In the most common usage of @code{acons}, a variable holding the | |
3171 | original association list is updated with the combined alist: | |
3172 | ||
3173 | @example | |
3174 | (set! address-list (acons name address address-list)) | |
3175 | @end example | |
3176 | ||
3177 | In such cases, it doesn't matter that the old and new values of | |
3178 | @code{address-list} share some of their contents, since the old value is | |
3179 | usually no longer independently accessible. | |
3180 | ||
3181 | Note that @code{acons} adds the specified new entry regardless of | |
3182 | whether the alist may already contain entries with keys that are, in | |
3183 | some sense, the same as that of the new entry. Thus @code{acons} is | |
3184 | ideal for building alists where there is no concept of key uniqueness. | |
3185 | ||
3186 | @example | |
3187 | (set! task-list (acons 3 "pay gas bill" '())) | |
3188 | task-list | |
3189 | @result{} | |
3190 | ((3 . "pay gas bill")) | |
3191 | ||
3192 | (set! task-list (acons 3 "tidy bedroom" task-list)) | |
3193 | task-list | |
3194 | @result{} | |
3195 | ((3 . "tidy bedroom") (3 . "pay gas bill")) | |
3196 | @end example | |
3197 | ||
3198 | @code{assq-set!}, @code{assv-set!} and @code{assoc-set!} are used to add | |
3199 | or replace an entry in an association list where there @emph{is} a | |
3200 | concept of key uniqueness. If the specified association list already | |
3201 | contains an entry whose key is the same as that specified in the | |
3202 | procedure call, the existing entry is replaced by the new one. | |
3203 | Otherwise, the new entry is consed onto the head of the old association | |
3204 | list to create the combined alist. In all cases, these procedures | |
3205 | return the combined alist. | |
3206 | ||
3207 | @code{assq-set!} and friends @emph{may} destructively modify the | |
3208 | structure of the old association list in such a way that an existing | |
3209 | variable is correctly updated without having to @code{set!} it to the | |
3210 | value returned: | |
3211 | ||
3212 | @example | |
3213 | address-list | |
3214 | @result{} | |
3215 | (("mary" . "34 Elm Road") ("james" . "16 Bow Street")) | |
3216 | ||
3217 | (assoc-set! address-list "james" "1a London Road") | |
3218 | @result{} | |
3219 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
3220 | ||
3221 | address-list | |
3222 | @result{} | |
3223 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
3224 | @end example | |
3225 | ||
3226 | Or they may not: | |
3227 | ||
3228 | @example | |
3229 | (assoc-set! address-list "bob" "11 Newington Avenue") | |
3230 | @result{} | |
3231 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
3232 | ("james" . "1a London Road")) | |
3233 | ||
3234 | address-list | |
3235 | @result{} | |
3236 | (("mary" . "34 Elm Road") ("james" . "1a London Road")) | |
3237 | @end example | |
3238 | ||
3239 | The only safe way to update an association list variable when adding or | |
3240 | replacing an entry like this is to @code{set!} the variable to the | |
3241 | returned value: | |
3242 | ||
3243 | @example | |
3244 | (set! address-list | |
3245 | (assoc-set! address-list "bob" "11 Newington Avenue")) | |
3246 | address-list | |
3247 | @result{} | |
3248 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
3249 | ("james" . "1a London Road")) | |
3250 | @end example | |
3251 | ||
3252 | Because of this slight inconvenience, you may find it more convenient to | |
3253 | use hash tables to store dictionary data. If your application will not | |
3254 | be modifying the contents of an alist very often, this may not make much | |
3255 | difference to you. | |
3256 | ||
3257 | If you need to keep the old value of an association list in a form | |
3258 | independent from the list that results from modification by | |
3259 | @code{acons}, @code{assq-set!}, @code{assv-set!} or @code{assoc-set!}, | |
3260 | use @code{list-copy} to copy the old association list before modifying | |
3261 | it. | |
3262 | ||
3263 | @deffn {Scheme Procedure} acons key value alist | |
3264 | @deffnx {C Function} scm_acons (key, value, alist) | |
3265 | Add a new key-value pair to @var{alist}. A new pair is | |
3266 | created whose car is @var{key} and whose cdr is @var{value}, and the | |
3267 | pair is consed onto @var{alist}, and the new list is returned. This | |
3268 | function is @emph{not} destructive; @var{alist} is not modified. | |
3269 | @end deffn | |
3270 | ||
3271 | @deffn {Scheme Procedure} assq-set! alist key val | |
3272 | @deffnx {Scheme Procedure} assv-set! alist key value | |
3273 | @deffnx {Scheme Procedure} assoc-set! alist key value | |
3274 | @deffnx {C Function} scm_assq_set_x (alist, key, val) | |
3275 | @deffnx {C Function} scm_assv_set_x (alist, key, val) | |
3276 | @deffnx {C Function} scm_assoc_set_x (alist, key, val) | |
3277 | Reassociate @var{key} in @var{alist} with @var{value}: find any existing | |
3278 | @var{alist} entry for @var{key} and associate it with the new | |
3279 | @var{value}. If @var{alist} does not contain an entry for @var{key}, | |
3280 | add a new one. Return the (possibly new) alist. | |
3281 | ||
3282 | These functions do not attempt to verify the structure of @var{alist}, | |
3283 | and so may cause unusual results if passed an object that is not an | |
3284 | association list. | |
3285 | @end deffn | |
3286 | ||
3287 | @node Retrieving Alist Entries | |
3288 | @subsubsection Retrieving Alist Entries | |
3289 | @rnindex assq | |
3290 | @rnindex assv | |
3291 | @rnindex assoc | |
3292 | ||
b167633c KR |
3293 | @code{assq}, @code{assv} and @code{assoc} find the entry in an alist |
3294 | for a given key, and return the @code{(@var{key} . @var{value})} pair. | |
3295 | @code{assq-ref}, @code{assv-ref} and @code{assoc-ref} do a similar | |
3296 | lookup, but return just the @var{value}. | |
07d83abe MV |
3297 | |
3298 | @deffn {Scheme Procedure} assq key alist | |
3299 | @deffnx {Scheme Procedure} assv key alist | |
3300 | @deffnx {Scheme Procedure} assoc key alist | |
3301 | @deffnx {C Function} scm_assq (key, alist) | |
3302 | @deffnx {C Function} scm_assv (key, alist) | |
3303 | @deffnx {C Function} scm_assoc (key, alist) | |
b167633c KR |
3304 | Return the first entry in @var{alist} with the given @var{key}. The |
3305 | return is the pair @code{(KEY . VALUE)} from @var{alist}. If there's | |
3306 | no matching entry the return is @code{#f}. | |
3307 | ||
3308 | @code{assq} compares keys with @code{eq?}, @code{assv} uses | |
23f2b9a3 KR |
3309 | @code{eqv?} and @code{assoc} uses @code{equal?}. See also SRFI-1 |
3310 | which has an extended @code{assoc} (@ref{SRFI-1 Association Lists}). | |
b167633c | 3311 | @end deffn |
07d83abe MV |
3312 | |
3313 | @deffn {Scheme Procedure} assq-ref alist key | |
3314 | @deffnx {Scheme Procedure} assv-ref alist key | |
3315 | @deffnx {Scheme Procedure} assoc-ref alist key | |
3316 | @deffnx {C Function} scm_assq_ref (alist, key) | |
3317 | @deffnx {C Function} scm_assv_ref (alist, key) | |
3318 | @deffnx {C Function} scm_assoc_ref (alist, key) | |
b167633c KR |
3319 | Return the value from the first entry in @var{alist} with the given |
3320 | @var{key}, or @code{#f} if there's no such entry. | |
07d83abe | 3321 | |
b167633c KR |
3322 | @code{assq-ref} compares keys with @code{eq?}, @code{assv-ref} uses |
3323 | @code{eqv?} and @code{assoc-ref} uses @code{equal?}. | |
3324 | ||
3325 | Notice these functions have the @var{key} argument last, like other | |
72b3aa56 | 3326 | @code{-ref} functions, but this is opposite to what @code{assq} |
b167633c | 3327 | etc above use. |
07d83abe | 3328 | |
b167633c KR |
3329 | When the return is @code{#f} it can be either @var{key} not found, or |
3330 | an entry which happens to have value @code{#f} in the @code{cdr}. Use | |
3331 | @code{assq} etc above if you need to differentiate these cases. | |
07d83abe MV |
3332 | @end deffn |
3333 | ||
b167633c | 3334 | |
07d83abe MV |
3335 | @node Removing Alist Entries |
3336 | @subsubsection Removing Alist Entries | |
3337 | ||
3338 | To remove the element from an association list whose key matches a | |
3339 | specified key, use @code{assq-remove!}, @code{assv-remove!} or | |
3340 | @code{assoc-remove!} (depending, as usual, on the level of equality | |
3341 | required between the key that you specify and the keys in the | |
3342 | association list). | |
3343 | ||
3344 | As with @code{assq-set!} and friends, the specified alist may or may not | |
3345 | be modified destructively, and the only safe way to update a variable | |
3346 | containing the alist is to @code{set!} it to the value that | |
3347 | @code{assq-remove!} and friends return. | |
3348 | ||
3349 | @example | |
3350 | address-list | |
3351 | @result{} | |
3352 | (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road") | |
3353 | ("james" . "1a London Road")) | |
3354 | ||
3355 | (set! address-list (assoc-remove! address-list "mary")) | |
3356 | address-list | |
3357 | @result{} | |
3358 | (("bob" . "11 Newington Avenue") ("james" . "1a London Road")) | |
3359 | @end example | |
3360 | ||
3361 | Note that, when @code{assq/v/oc-remove!} is used to modify an | |
3362 | association list that has been constructed only using the corresponding | |
3363 | @code{assq/v/oc-set!}, there can be at most one matching entry in the | |
3364 | alist, so the question of multiple entries being removed in one go does | |
3365 | not arise. If @code{assq/v/oc-remove!} is applied to an association | |
3366 | list that has been constructed using @code{acons}, or an | |
3367 | @code{assq/v/oc-set!} with a different level of equality, or any mixture | |
3368 | of these, it removes only the first matching entry from the alist, even | |
3369 | if the alist might contain further matching entries. For example: | |
3370 | ||
3371 | @example | |
3372 | (define address-list '()) | |
3373 | (set! address-list (assq-set! address-list "mary" "11 Elm Street")) | |
3374 | (set! address-list (assq-set! address-list "mary" "57 Pine Drive")) | |
3375 | address-list | |
3376 | @result{} | |
3377 | (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street")) | |
3378 | ||
3379 | (set! address-list (assoc-remove! address-list "mary")) | |
3380 | address-list | |
3381 | @result{} | |
3382 | (("mary" . "11 Elm Street")) | |
3383 | @end example | |
3384 | ||
3385 | In this example, the two instances of the string "mary" are not the same | |
3386 | when compared using @code{eq?}, so the two @code{assq-set!} calls add | |
3387 | two distinct entries to @code{address-list}. When compared using | |
3388 | @code{equal?}, both "mary"s in @code{address-list} are the same as the | |
3389 | "mary" in the @code{assoc-remove!} call, but @code{assoc-remove!} stops | |
3390 | after removing the first matching entry that it finds, and so one of the | |
3391 | "mary" entries is left in place. | |
3392 | ||
3393 | @deffn {Scheme Procedure} assq-remove! alist key | |
3394 | @deffnx {Scheme Procedure} assv-remove! alist key | |
3395 | @deffnx {Scheme Procedure} assoc-remove! alist key | |
3396 | @deffnx {C Function} scm_assq_remove_x (alist, key) | |
3397 | @deffnx {C Function} scm_assv_remove_x (alist, key) | |
3398 | @deffnx {C Function} scm_assoc_remove_x (alist, key) | |
3399 | Delete the first entry in @var{alist} associated with @var{key}, and return | |
3400 | the resulting alist. | |
3401 | @end deffn | |
3402 | ||
3403 | @node Sloppy Alist Functions | |
3404 | @subsubsection Sloppy Alist Functions | |
3405 | ||
3406 | @code{sloppy-assq}, @code{sloppy-assv} and @code{sloppy-assoc} behave | |
3407 | like the corresponding non-@code{sloppy-} procedures, except that they | |
3408 | return @code{#f} when the specified association list is not well-formed, | |
3409 | where the non-@code{sloppy-} versions would signal an error. | |
3410 | ||
3411 | Specifically, there are two conditions for which the non-@code{sloppy-} | |
3412 | procedures signal an error, which the @code{sloppy-} procedures handle | |
3413 | instead by returning @code{#f}. Firstly, if the specified alist as a | |
3414 | whole is not a proper list: | |
3415 | ||
3416 | @example | |
3417 | (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame")) | |
3418 | @result{} | |
3419 | ERROR: In procedure assoc in expression (assoc "mary" (quote #)): | |
45867c2a NJ |
3420 | ERROR: Wrong type argument in position 2 (expecting |
3421 | association list): ((1 . 2) ("key" . "door") . "open sesame") | |
07d83abe MV |
3422 | |
3423 | (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame")) | |
3424 | @result{} | |
3425 | #f | |
3426 | @end example | |
3427 | ||
3428 | @noindent | |
3429 | Secondly, if one of the entries in the specified alist is not a pair: | |
3430 | ||
3431 | @example | |
3432 | (assoc 2 '((1 . 1) 2 (3 . 9))) | |
3433 | @result{} | |
3434 | ERROR: In procedure assoc in expression (assoc 2 (quote #)): | |
45867c2a NJ |
3435 | ERROR: Wrong type argument in position 2 (expecting |
3436 | association list): ((1 . 1) 2 (3 . 9)) | |
07d83abe MV |
3437 | |
3438 | (sloppy-assoc 2 '((1 . 1) 2 (3 . 9))) | |
3439 | @result{} | |
3440 | #f | |
3441 | @end example | |
3442 | ||
3443 | Unless you are explicitly working with badly formed association lists, | |
3444 | it is much safer to use the non-@code{sloppy-} procedures, because they | |
3445 | help to highlight coding and data errors that the @code{sloppy-} | |
3446 | versions would silently cover up. | |
3447 | ||
3448 | @deffn {Scheme Procedure} sloppy-assq key alist | |
3449 | @deffnx {C Function} scm_sloppy_assq (key, alist) | |
3450 | Behaves like @code{assq} but does not do any error checking. | |
3451 | Recommended only for use in Guile internals. | |
3452 | @end deffn | |
3453 | ||
3454 | @deffn {Scheme Procedure} sloppy-assv key alist | |
3455 | @deffnx {C Function} scm_sloppy_assv (key, alist) | |
3456 | Behaves like @code{assv} but does not do any error checking. | |
3457 | Recommended only for use in Guile internals. | |
3458 | @end deffn | |
3459 | ||
3460 | @deffn {Scheme Procedure} sloppy-assoc key alist | |
3461 | @deffnx {C Function} scm_sloppy_assoc (key, alist) | |
3462 | Behaves like @code{assoc} but does not do any error checking. | |
3463 | Recommended only for use in Guile internals. | |
3464 | @end deffn | |
3465 | ||
3466 | @node Alist Example | |
3467 | @subsubsection Alist Example | |
3468 | ||
3469 | Here is a longer example of how alists may be used in practice. | |
3470 | ||
3471 | @lisp | |
3472 | (define capitals '(("New York" . "Albany") | |
3473 | ("Oregon" . "Salem") | |
3474 | ("Florida" . "Miami"))) | |
3475 | ||
3476 | ;; What's the capital of Oregon? | |
3477 | (assoc "Oregon" capitals) @result{} ("Oregon" . "Salem") | |
3478 | (assoc-ref capitals "Oregon") @result{} "Salem" | |
3479 | ||
3480 | ;; We left out South Dakota. | |
3481 | (set! capitals | |
3482 | (assoc-set! capitals "South Dakota" "Pierre")) | |
3483 | capitals | |
3484 | @result{} (("South Dakota" . "Pierre") | |
3485 | ("New York" . "Albany") | |
3486 | ("Oregon" . "Salem") | |
3487 | ("Florida" . "Miami")) | |
3488 | ||
3489 | ;; And we got Florida wrong. | |
3490 | (set! capitals | |
3491 | (assoc-set! capitals "Florida" "Tallahassee")) | |
3492 | capitals | |
3493 | @result{} (("South Dakota" . "Pierre") | |
3494 | ("New York" . "Albany") | |
3495 | ("Oregon" . "Salem") | |
3496 | ("Florida" . "Tallahassee")) | |
3497 | ||
3498 | ;; After Oregon secedes, we can remove it. | |
3499 | (set! capitals | |
3500 | (assoc-remove! capitals "Oregon")) | |
3501 | capitals | |
3502 | @result{} (("South Dakota" . "Pierre") | |
3503 | ("New York" . "Albany") | |
3504 | ("Florida" . "Tallahassee")) | |
3505 | @end lisp | |
3506 | ||
22ec6a31 LC |
3507 | @node VHashes |
3508 | @subsection VList-Based Hash Lists or ``VHashes'' | |
3509 | ||
3510 | @cindex VList-based hash lists | |
3511 | @cindex VHash | |
3512 | ||
3513 | The @code{(ice-9 vlist)} module provides an implementation of @dfn{VList-based | |
3514 | hash lists} (@pxref{VLists}). VList-based hash lists, or @dfn{vhashes}, are an | |
3515 | immutable dictionary type similar to association lists that maps @dfn{keys} to | |
3516 | @dfn{values}. However, unlike association lists, accessing a value given its | |
3517 | key is typically a constant-time operation. | |
3518 | ||
3519 | The VHash programming interface of @code{(ice-9 vlist)} is mostly the same as | |
3520 | that of association lists found in SRFI-1, with procedure names prefixed by | |
d5f76917 | 3521 | @code{vhash-} instead of @code{alist-} (@pxref{SRFI-1 Association Lists}). |
22ec6a31 LC |
3522 | |
3523 | In addition, vhashes can be manipulated using VList operations: | |
3524 | ||
3525 | @example | |
3526 | (vlist-head (vhash-consq 'a 1 vlist-null)) | |
3527 | @result{} (a . 1) | |
3528 | ||
3529 | (define vh1 (vhash-consq 'b 2 (vhash-consq 'a 1 vlist-null))) | |
3530 | (define vh2 (vhash-consq 'c 3 (vlist-tail vh1))) | |
3531 | ||
3532 | (vhash-assq 'a vh2) | |
3533 | @result{} (a . 1) | |
3534 | (vhash-assq 'b vh2) | |
3535 | @result{} #f | |
3536 | (vhash-assq 'c vh2) | |
3537 | @result{} (c . 3) | |
3538 | (vlist->list vh2) | |
3539 | @result{} ((c . 3) (a . 1)) | |
3540 | @end example | |
3541 | ||
3542 | However, keep in mind that procedures that construct new VLists | |
3543 | (@code{vlist-map}, @code{vlist-filter}, etc.) return raw VLists, not vhashes: | |
3544 | ||
3545 | @example | |
3546 | (define vh (alist->vhash '((a . 1) (b . 2) (c . 3)) hashq)) | |
3547 | (vhash-assq 'a vh) | |
3548 | @result{} (a . 1) | |
3549 | ||
3550 | (define vl | |
3551 | ;; This will create a raw vlist. | |
3552 | (vlist-filter (lambda (key+value) (odd? (cdr key+value))) vh)) | |
3553 | (vhash-assq 'a vl) | |
3554 | @result{} ERROR: Wrong type argument in position 2 | |
3555 | ||
3556 | (vlist->list vl) | |
3557 | @result{} ((a . 1) (c . 3)) | |
3558 | @end example | |
3559 | ||
3560 | @deffn {Scheme Procedure} vhash? obj | |
3561 | Return true if @var{obj} is a vhash. | |
3562 | @end deffn | |
3563 | ||
3564 | @deffn {Scheme Procedure} vhash-cons key value vhash [hash-proc] | |
3565 | @deffnx {Scheme Procedure} vhash-consq key value vhash | |
3566 | @deffnx {Scheme Procedure} vhash-consv key value vhash | |
3567 | Return a new hash list based on @var{vhash} where @var{key} is associated with | |
3568 | @var{value}, using @var{hash-proc} to compute the hash of @var{key}. | |
3569 | @var{vhash} must be either @code{vlist-null} or a vhash returned by a previous | |
3570 | call to @code{vhash-cons}. @var{hash-proc} defaults to @code{hash} (@pxref{Hash | |
3571 | Table Reference, @code{hash} procedure}). With @code{vhash-consq}, the | |
3572 | @code{hashq} hash function is used; with @code{vhash-consv} the @code{hashv} | |
3573 | hash function is used. | |
3574 | ||
3575 | All @code{vhash-cons} calls made to construct a vhash should use the same | |
3576 | @var{hash-proc}. Failing to do that, the result is undefined. | |
3577 | @end deffn | |
3578 | ||
3579 | @deffn {Scheme Procedure} vhash-assoc key vhash [equal? [hash-proc]] | |
3580 | @deffnx {Scheme Procedure} vhash-assq key vhash | |
3581 | @deffnx {Scheme Procedure} vhash-assv key vhash | |
3582 | Return the first key/value pair from @var{vhash} whose key is equal to @var{key} | |
3583 | according to the @var{equal?} equality predicate (which defaults to | |
3584 | @code{equal?}), and using @var{hash-proc} (which defaults to @code{hash}) to | |
3585 | compute the hash of @var{key}. The second form uses @code{eq?} as the equality | |
3586 | predicate and @code{hashq} as the hash function; the last form uses @code{eqv?} | |
3587 | and @code{hashv}. | |
3588 | ||
3589 | Note that it is important to consistently use the same hash function for | |
3590 | @var{hash-proc} as was passed to @code{vhash-cons}. Failing to do that, the | |
3591 | result is unpredictable. | |
3592 | @end deffn | |
3593 | ||
3594 | @deffn {Scheme Procedure} vhash-delete key vhash [equal? [hash-proc]] | |
3595 | @deffnx {Scheme Procedure} vhash-delq key vhash | |
3596 | @deffnx {Scheme Procedure} vhash-delv key vhash | |
3597 | Remove all associations from @var{vhash} with @var{key}, comparing keys with | |
3598 | @var{equal?} (which defaults to @code{equal?}), and computing the hash of | |
3599 | @var{key} using @var{hash-proc} (which defaults to @code{hash}). The second | |
3600 | form uses @code{eq?} as the equality predicate and @code{hashq} as the hash | |
3601 | function; the last one uses @code{eqv?} and @code{hashv}. | |
3602 | ||
3603 | Again the choice of @var{hash-proc} must be consistent with previous calls to | |
3604 | @code{vhash-cons}. | |
3605 | @end deffn | |
3606 | ||
2f50d0a8 MW |
3607 | @deffn {Scheme Procedure} vhash-fold proc init vhash |
3608 | @deffnx {Scheme Procedure} vhash-fold-right proc init vhash | |
3609 | Fold over the key/value elements of @var{vhash} in the given direction, | |
3610 | with each call to @var{proc} having the form @code{(@var{proc} key value | |
3611 | result)}, where @var{result} is the result of the previous call to | |
3612 | @var{proc} and @var{init} the value of @var{result} for the first call | |
3613 | to @var{proc}. | |
22ec6a31 LC |
3614 | @end deffn |
3615 | ||
927bf5e8 LC |
3616 | @deffn {Scheme Procedure} vhash-fold* proc init key vhash [equal? [hash]] |
3617 | @deffnx {Scheme Procedure} vhash-foldq* proc init key vhash | |
3618 | @deffnx {Scheme Procedure} vhash-foldv* proc init key vhash | |
3619 | Fold over all the values associated with @var{key} in @var{vhash}, with each | |
3620 | call to @var{proc} having the form @code{(proc value result)}, where | |
3621 | @var{result} is the result of the previous call to @var{proc} and @var{init} the | |
3622 | value of @var{result} for the first call to @var{proc}. | |
3623 | ||
3624 | Keys in @var{vhash} are hashed using @var{hash} are compared using @var{equal?}. | |
3625 | The second form uses @code{eq?} as the equality predicate and @code{hashq} as | |
3626 | the hash function; the third one uses @code{eqv?} and @code{hashv}. | |
3627 | ||
3628 | Example: | |
3629 | ||
3630 | @example | |
3631 | (define vh | |
3632 | (alist->vhash '((a . 1) (a . 2) (z . 0) (a . 3)))) | |
3633 | ||
3634 | (vhash-fold* cons '() 'a vh) | |
3635 | @result{} (3 2 1) | |
3636 | ||
3637 | (vhash-fold* cons '() 'z vh) | |
3638 | @result{} (0) | |
3639 | @end example | |
3640 | @end deffn | |
3641 | ||
22ec6a31 LC |
3642 | @deffn {Scheme Procedure} alist->vhash alist [hash-proc] |
3643 | Return the vhash corresponding to @var{alist}, an association list, using | |
3644 | @var{hash-proc} to compute key hashes. When omitted, @var{hash-proc} defaults | |
3645 | to @code{hash}. | |
3646 | @end deffn | |
3647 | ||
3648 | ||
07d83abe MV |
3649 | @node Hash Tables |
3650 | @subsection Hash Tables | |
3651 | @tpindex Hash Tables | |
3652 | ||
07d83abe MV |
3653 | Hash tables are dictionaries which offer similar functionality as |
3654 | association lists: They provide a mapping from keys to values. The | |
3655 | difference is that association lists need time linear in the size of | |
3656 | elements when searching for entries, whereas hash tables can normally | |
3657 | search in constant time. The drawback is that hash tables require a | |
3658 | little bit more memory, and that you can not use the normal list | |
3659 | procedures (@pxref{Lists}) for working with them. | |
3660 | ||
3661 | @menu | |
3662 | * Hash Table Examples:: Demonstration of hash table usage. | |
3663 | * Hash Table Reference:: Hash table procedure descriptions. | |
3664 | @end menu | |
3665 | ||
3666 | ||
3667 | @node Hash Table Examples | |
3668 | @subsubsection Hash Table Examples | |
3669 | ||
07d83abe MV |
3670 | For demonstration purposes, this section gives a few usage examples of |
3671 | some hash table procedures, together with some explanation what they do. | |
3672 | ||
3673 | First we start by creating a new hash table with 31 slots, and | |
3674 | populate it with two key/value pairs. | |
3675 | ||
3676 | @lisp | |
3677 | (define h (make-hash-table 31)) | |
3678 | ||
35f957b2 MV |
3679 | ;; This is an opaque object |
3680 | h | |
07d83abe | 3681 | @result{} |
35f957b2 MV |
3682 | #<hash-table 0/31> |
3683 | ||
35f957b2 MV |
3684 | ;; Inserting into a hash table can be done with hashq-set! |
3685 | (hashq-set! h 'foo "bar") | |
3686 | @result{} | |
3687 | "bar" | |
07d83abe | 3688 | |
35f957b2 | 3689 | (hashq-set! h 'braz "zonk") |
07d83abe | 3690 | @result{} |
35f957b2 | 3691 | "zonk" |
07d83abe | 3692 | |
35f957b2 | 3693 | ;; Or with hash-create-handle! |
07d83abe MV |
3694 | (hashq-create-handle! h 'frob #f) |
3695 | @result{} | |
3696 | (frob . #f) | |
3697 | @end lisp | |
3698 | ||
3699 | You can get the value for a given key with the procedure | |
3700 | @code{hashq-ref}, but the problem with this procedure is that you | |
3701 | cannot reliably determine whether a key does exists in the table. The | |
3702 | reason is that the procedure returns @code{#f} if the key is not in | |
3703 | the table, but it will return the same value if the key is in the | |
3704 | table and just happens to have the value @code{#f}, as you can see in | |
3705 | the following examples. | |
3706 | ||
3707 | @lisp | |
3708 | (hashq-ref h 'foo) | |
3709 | @result{} | |
3710 | "bar" | |
3711 | ||
3712 | (hashq-ref h 'frob) | |
3713 | @result{} | |
3714 | #f | |
3715 | ||
3716 | (hashq-ref h 'not-there) | |
3717 | @result{} | |
3718 | #f | |
3719 | @end lisp | |
3720 | ||
3721 | Better is to use the procedure @code{hashq-get-handle}, which makes a | |
3722 | distinction between the two cases. Just like @code{assq}, this | |
3723 | procedure returns a key/value-pair on success, and @code{#f} if the | |
3724 | key is not found. | |
3725 | ||
3726 | @lisp | |
3727 | (hashq-get-handle h 'foo) | |
3728 | @result{} | |
3729 | (foo . "bar") | |
3730 | ||
3731 | (hashq-get-handle h 'not-there) | |
3732 | @result{} | |
3733 | #f | |
3734 | @end lisp | |
3735 | ||
3330f00f DH |
3736 | Interesting results can be computed by using @code{hash-fold} to work |
3737 | through each element. This example will count the total number of | |
3738 | elements: | |
07d83abe MV |
3739 | |
3740 | @lisp | |
3741 | (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h) | |
3742 | @result{} | |
3743 | 3 | |
3744 | @end lisp | |
3745 | ||
3330f00f DH |
3746 | The same thing can be done with the procedure @code{hash-count}, which |
3747 | can also count the number of elements matching a particular predicate. | |
3748 | For example, count the number of elements with string values: | |
3749 | ||
3750 | @lisp | |
3751 | (hash-count (lambda (key value) (string? value)) h) | |
3752 | @result{} | |
3753 | 2 | |
3754 | @end lisp | |
3755 | ||
3756 | Counting all the elements is a simple task using @code{const}: | |
3757 | ||
3758 | @lisp | |
3759 | (hash-count (const #t) h) | |
3760 | @result{} | |
3761 | 3 | |
3762 | @end lisp | |
3763 | ||
07d83abe MV |
3764 | @node Hash Table Reference |
3765 | @subsubsection Hash Table Reference | |
3766 | ||
3767 | @c FIXME: Describe in broad terms what happens for resizing, and what | |
3768 | @c the initial size means for this. | |
3769 | ||
3770 | Like the association list functions, the hash table functions come in | |
3771 | several varieties, according to the equality test used for the keys. | |
3772 | Plain @code{hash-} functions use @code{equal?}, @code{hashq-} | |
3773 | functions use @code{eq?}, @code{hashv-} functions use @code{eqv?}, and | |
3774 | the @code{hashx-} functions use an application supplied test. | |
3775 | ||
3776 | A single @code{make-hash-table} creates a hash table suitable for use | |
3777 | with any set of functions, but it's imperative that just one set is | |
3778 | then used consistently, or results will be unpredictable. | |
3779 | ||
07d83abe MV |
3780 | Hash tables are implemented as a vector indexed by a hash value formed |
3781 | from the key, with an association list of key/value pairs for each | |
3782 | bucket in case distinct keys hash together. Direct access to the | |
3783 | pairs in those lists is provided by the @code{-handle-} functions. | |
35f957b2 | 3784 | |
e6a730b2 DH |
3785 | When the number of entries in a hash table goes above a threshold, the |
3786 | vector is made larger and the entries are rehashed, to prevent the | |
3787 | bucket lists from becoming too long and slowing down accesses. When the | |
3788 | number of entries goes below a threshold, the vector is shrunk to save | |
3789 | space. | |
07d83abe | 3790 | |
07d83abe MV |
3791 | For the @code{hashx-} ``extended'' routines, an application supplies a |
3792 | @var{hash} function producing an integer index like @code{hashq} etc | |
3793 | below, and an @var{assoc} alist search function like @code{assq} etc | |
3794 | (@pxref{Retrieving Alist Entries}). Here's an example of such | |
3795 | functions implementing case-insensitive hashing of string keys, | |
3796 | ||
3797 | @example | |
3798 | (use-modules (srfi srfi-1) | |
3799 | (srfi srfi-13)) | |
3800 | ||
3801 | (define (my-hash str size) | |
3802 | (remainder (string-hash-ci str) size)) | |
3803 | (define (my-assoc str alist) | |
3804 | (find (lambda (pair) (string-ci=? str (car pair))) alist)) | |
3805 | ||
3806 | (define my-table (make-hash-table)) | |
3807 | (hashx-set! my-hash my-assoc my-table "foo" 123) | |
3808 | ||
3809 | (hashx-ref my-hash my-assoc my-table "FOO") | |
3810 | @result{} 123 | |
3811 | @end example | |
3812 | ||
3813 | In a @code{hashx-} @var{hash} function the aim is to spread keys | |
3814 | across the vector, so bucket lists don't become long. But the actual | |
3815 | values are arbitrary as long as they're in the range 0 to | |
3816 | @math{@var{size}-1}. Helpful functions for forming a hash value, in | |
3817 | addition to @code{hashq} etc below, include @code{symbol-hash} | |
3818 | (@pxref{Symbol Keys}), @code{string-hash} and @code{string-hash-ci} | |
4a3057fc | 3819 | (@pxref{String Comparison}), and @code{char-set-hash} |
5354f4ab | 3820 | (@pxref{Character Set Predicates/Comparison}). |
07d83abe | 3821 | |
07d83abe MV |
3822 | @sp 1 |
3823 | @deffn {Scheme Procedure} make-hash-table [size] | |
e6a730b2 | 3824 | Create a new hash table object, with an optional minimum |
35f957b2 | 3825 | vector @var{size}. |
07d83abe MV |
3826 | |
3827 | When @var{size} is given, the table vector will still grow and shrink | |
3828 | automatically, as described above, but with @var{size} as a minimum. | |
3829 | If an application knows roughly how many entries the table will hold | |
3830 | then it can use @var{size} to avoid rehashing when initial entries are | |
3831 | added. | |
5063f0a9 DT |
3832 | @end deffn |
3833 | ||
3834 | @deffn {Scheme Procedure} alist->hash-table alist | |
3835 | @deffnx {Scheme Procedure} alist->hashq-table alist | |
3836 | @deffnx {Scheme Procedure} alist->hashv-table alist | |
3837 | @deffnx {Scheme Procedure} alist->hashx-table hash assoc alist | |
3838 | Convert @var{alist} into a hash table. When keys are repeated in | |
3839 | @var{alist}, the leftmost association takes precedence. | |
3840 | ||
3841 | @example | |
3842 | (use-modules (ice-9 hash-table)) | |
3843 | (alist->hash-table '((foo . 1) (bar . 2))) | |
3844 | @end example | |
3845 | ||
3846 | When converting to an extended hash table, custom @var{hash} and | |
3847 | @var{assoc} procedures must be provided. | |
3848 | ||
3849 | @example | |
3850 | (alist->hashx-table hash assoc '((foo . 1) (bar . 2))) | |
3851 | @end example | |
3852 | ||
07d83abe MV |
3853 | @end deffn |
3854 | ||
cdf1ad3b MV |
3855 | @deffn {Scheme Procedure} hash-table? obj |
3856 | @deffnx {C Function} scm_hash_table_p (obj) | |
35f957b2 | 3857 | Return @code{#t} if @var{obj} is a abstract hash table object. |
cdf1ad3b MV |
3858 | @end deffn |
3859 | ||
3860 | @deffn {Scheme Procedure} hash-clear! table | |
3861 | @deffnx {C Function} scm_hash_clear_x (table) | |
35f957b2 | 3862 | Remove all items from @var{table} (without triggering a resize). |
cdf1ad3b MV |
3863 | @end deffn |
3864 | ||
07d83abe MV |
3865 | @deffn {Scheme Procedure} hash-ref table key [dflt] |
3866 | @deffnx {Scheme Procedure} hashq-ref table key [dflt] | |
3867 | @deffnx {Scheme Procedure} hashv-ref table key [dflt] | |
3868 | @deffnx {Scheme Procedure} hashx-ref hash assoc table key [dflt] | |
3869 | @deffnx {C Function} scm_hash_ref (table, key, dflt) | |
3870 | @deffnx {C Function} scm_hashq_ref (table, key, dflt) | |
3871 | @deffnx {C Function} scm_hashv_ref (table, key, dflt) | |
3872 | @deffnx {C Function} scm_hashx_ref (hash, assoc, table, key, dflt) | |
3873 | Lookup @var{key} in the given hash @var{table}, and return the | |
3874 | associated value. If @var{key} is not found, return @var{dflt}, or | |
3875 | @code{#f} if @var{dflt} is not given. | |
3876 | @end deffn | |
3877 | ||
3878 | @deffn {Scheme Procedure} hash-set! table key val | |
3879 | @deffnx {Scheme Procedure} hashq-set! table key val | |
3880 | @deffnx {Scheme Procedure} hashv-set! table key val | |
3881 | @deffnx {Scheme Procedure} hashx-set! hash assoc table key val | |
3882 | @deffnx {C Function} scm_hash_set_x (table, key, val) | |
3883 | @deffnx {C Function} scm_hashq_set_x (table, key, val) | |
3884 | @deffnx {C Function} scm_hashv_set_x (table, key, val) | |
3885 | @deffnx {C Function} scm_hashx_set_x (hash, assoc, table, key, val) | |
3886 | Associate @var{val} with @var{key} in the given hash @var{table}. If | |
3887 | @var{key} is already present then it's associated value is changed. | |
3888 | If it's not present then a new entry is created. | |
3889 | @end deffn | |
3890 | ||
3891 | @deffn {Scheme Procedure} hash-remove! table key | |
3892 | @deffnx {Scheme Procedure} hashq-remove! table key | |
3893 | @deffnx {Scheme Procedure} hashv-remove! table key | |
35f957b2 | 3894 | @deffnx {Scheme Procedure} hashx-remove! hash assoc table key |
07d83abe MV |
3895 | @deffnx {C Function} scm_hash_remove_x (table, key) |
3896 | @deffnx {C Function} scm_hashq_remove_x (table, key) | |
3897 | @deffnx {C Function} scm_hashv_remove_x (table, key) | |
35f957b2 | 3898 | @deffnx {C Function} scm_hashx_remove_x (hash, assoc, table, key) |
07d83abe MV |
3899 | Remove any association for @var{key} in the given hash @var{table}. |
3900 | If @var{key} is not in @var{table} then nothing is done. | |
3901 | @end deffn | |
3902 | ||
3903 | @deffn {Scheme Procedure} hash key size | |
3904 | @deffnx {Scheme Procedure} hashq key size | |
3905 | @deffnx {Scheme Procedure} hashv key size | |
3906 | @deffnx {C Function} scm_hash (key, size) | |
3907 | @deffnx {C Function} scm_hashq (key, size) | |
3908 | @deffnx {C Function} scm_hashv (key, size) | |
3909 | Return a hash value for @var{key}. This is a number in the range | |
3910 | @math{0} to @math{@var{size}-1}, which is suitable for use in a hash | |
3911 | table of the given @var{size}. | |
3912 | ||
3913 | Note that @code{hashq} and @code{hashv} may use internal addresses of | |
3914 | objects, so if an object is garbage collected and re-created it can | |
3915 | have a different hash value, even when the two are notionally | |
3916 | @code{eq?}. For instance with symbols, | |
3917 | ||
3918 | @example | |
3919 | (hashq 'something 123) @result{} 19 | |
3920 | (gc) | |
3921 | (hashq 'something 123) @result{} 62 | |
3922 | @end example | |
3923 | ||
3924 | In normal use this is not a problem, since an object entered into a | |
3925 | hash table won't be garbage collected until removed. It's only if | |
3926 | hashing calculations are somehow separated from normal references that | |
3927 | its lifetime needs to be considered. | |
3928 | @end deffn | |
3929 | ||
3930 | @deffn {Scheme Procedure} hash-get-handle table key | |
3931 | @deffnx {Scheme Procedure} hashq-get-handle table key | |
3932 | @deffnx {Scheme Procedure} hashv-get-handle table key | |
3933 | @deffnx {Scheme Procedure} hashx-get-handle hash assoc table key | |
3934 | @deffnx {C Function} scm_hash_get_handle (table, key) | |
3935 | @deffnx {C Function} scm_hashq_get_handle (table, key) | |
3936 | @deffnx {C Function} scm_hashv_get_handle (table, key) | |
3937 | @deffnx {C Function} scm_hashx_get_handle (hash, assoc, table, key) | |
3938 | Return the @code{(@var{key} . @var{value})} pair for @var{key} in the | |
3939 | given hash @var{table}, or @code{#f} if @var{key} is not in | |
3940 | @var{table}. | |
3941 | @end deffn | |
3942 | ||
3943 | @deffn {Scheme Procedure} hash-create-handle! table key init | |
3944 | @deffnx {Scheme Procedure} hashq-create-handle! table key init | |
3945 | @deffnx {Scheme Procedure} hashv-create-handle! table key init | |
3946 | @deffnx {Scheme Procedure} hashx-create-handle! hash assoc table key init | |
3947 | @deffnx {C Function} scm_hash_create_handle_x (table, key, init) | |
3948 | @deffnx {C Function} scm_hashq_create_handle_x (table, key, init) | |
3949 | @deffnx {C Function} scm_hashv_create_handle_x (table, key, init) | |
3950 | @deffnx {C Function} scm_hashx_create_handle_x (hash, assoc, table, key, init) | |
3951 | Return the @code{(@var{key} . @var{value})} pair for @var{key} in the | |
3952 | given hash @var{table}. If @var{key} is not in @var{table} then | |
3953 | create an entry for it with @var{init} as the value, and return that | |
3954 | pair. | |
3955 | @end deffn | |
3956 | ||
3957 | @deffn {Scheme Procedure} hash-map->list proc table | |
3958 | @deffnx {Scheme Procedure} hash-for-each proc table | |
3959 | @deffnx {C Function} scm_hash_map_to_list (proc, table) | |
3960 | @deffnx {C Function} scm_hash_for_each (proc, table) | |
3961 | Apply @var{proc} to the entries in the given hash @var{table}. Each | |
3962 | call is @code{(@var{proc} @var{key} @var{value})}. @code{hash-map->list} | |
3963 | returns a list of the results from these calls, @code{hash-for-each} | |
3964 | discards the results and returns an unspecified value. | |
3965 | ||
3966 | Calls are made over the table entries in an unspecified order, and for | |
3967 | @code{hash-map->list} the order of the values in the returned list is | |
3968 | unspecified. Results will be unpredictable if @var{table} is modified | |
3969 | while iterating. | |
3970 | ||
3971 | For example the following returns a new alist comprising all the | |
3972 | entries from @code{mytable}, in no particular order. | |
3973 | ||
3974 | @example | |
3975 | (hash-map->list cons mytable) | |
3976 | @end example | |
3977 | @end deffn | |
3978 | ||
3979 | @deffn {Scheme Procedure} hash-for-each-handle proc table | |
3980 | @deffnx {C Function} scm_hash_for_each_handle (proc, table) | |
3981 | Apply @var{proc} to the entries in the given hash @var{table}. Each | |
3982 | call is @code{(@var{proc} @var{handle})}, where @var{handle} is a | |
3983 | @code{(@var{key} . @var{value})} pair. Return an unspecified value. | |
3984 | ||
3985 | @code{hash-for-each-handle} differs from @code{hash-for-each} only in | |
3986 | the argument list of @var{proc}. | |
3987 | @end deffn | |
3988 | ||
3989 | @deffn {Scheme Procedure} hash-fold proc init table | |
3990 | @deffnx {C Function} scm_hash_fold (proc, init, table) | |
3991 | Accumulate a result by applying @var{proc} to the elements of the | |
3992 | given hash @var{table}. Each call is @code{(@var{proc} @var{key} | |
3993 | @var{value} @var{prior-result})}, where @var{key} and @var{value} are | |
3994 | from the @var{table} and @var{prior-result} is the return from the | |
3995 | previous @var{proc} call. For the first call, @var{prior-result} is | |
3996 | the given @var{init} value. | |
3997 | ||
3998 | Calls are made over the table entries in an unspecified order. | |
3999 | Results will be unpredictable if @var{table} is modified while | |
4000 | @code{hash-fold} is running. | |
4001 | ||
4002 | For example, the following returns a count of how many keys in | |
4003 | @code{mytable} are strings. | |
4004 | ||
4005 | @example | |
4006 | (hash-fold (lambda (key value prior) | |
4007 | (if (string? key) (1+ prior) prior)) | |
4008 | 0 mytable) | |
4009 | @end example | |
4010 | @end deffn | |
4011 | ||
3330f00f DH |
4012 | @deffn {Scheme Procedure} hash-count pred table |
4013 | @deffnx {C Function} scm_hash_count (pred, table) | |
4014 | Return the number of elements in the given hash @var{table} that cause | |
4015 | @code{(@var{pred} @var{key} @var{value})} to return true. To quickly | |
4016 | determine the total number of elements, use @code{(const #t)} for | |
4017 | @var{pred}. | |
4018 | @end deffn | |
07d83abe MV |
4019 | |
4020 | @c Local Variables: | |
4021 | @c TeX-master: "guile.texi" | |
4022 | @c End: |