2 @c This is part of the GNU Guile Reference Manual.
3 @c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
4 @c 2007, 2009, 2010, 2011, 2012, 2013 Free Software Foundation, Inc.
5 @c See the file guile.texi for copying conditions.
7 @node Compound Data Types
8 @section Compound Data Types
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.
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.
21 * Pairs:: Scheme's basic building block.
22 * Lists:: Special list functions supported by Guile.
23 * Vectors:: One-dimensional arrays of Scheme objects.
24 * Bit Vectors:: Vectors of bits.
25 * Arrays:: Matrices, etc.
26 * VLists:: Vector-like lists.
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.
31 * Dictionary Types:: About dictionary types in general.
32 * Association Lists:: List-based dictionaries.
33 * VHashes:: VList-based dictionaries.
34 * Hash Tables:: Table-based dictionaries.
42 Pairs are used to combine two Scheme objects into one compound object.
43 Hence the name: A pair stores a pair of objects.
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}).
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.
65 But beware, if you want to try out these examples, you have to
66 @dfn{quote} the expressions. More information about quotation is
67 available in the section @ref{Expression Syntax}. The correct way
68 to try these examples is as follows.
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.
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.
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
100 @deftypefn {C Function} int scm_is_pair (SCM x)
101 Return 1 when @var{x} is a pair; otherwise return 0.
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
107 @code{set-car!} and @code{set-cdr!}.
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}).
118 @deffn {Scheme Procedure} car pair
119 @deffnx {Scheme Procedure} cdr pair
120 @deffnx {C Function} scm_car (pair)
121 @deffnx {C Function} scm_cdr (pair)
122 Return the car or the cdr of @var{pair}, respectively.
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
131 These macros do no checking at all. The argument @var{pair} must be a
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
147 @deffnx {Scheme Procedure} cddddr pair
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)
191 These procedures are compositions of @code{car} and @code{cdr}, where
192 for example @code{caddr} could be defined by
195 (define caddr (lambda (x) (car (cdr (cdr x)))))
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}).
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.
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.
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.}
229 This is the short definition of what a list is:
233 Either the empty list @code{()},
236 or a pair which has a list in its cdr.
239 @c FIXME::martin: Describe the pair chaining in more detail.
241 @c FIXME::martin: What is a proper, what an improper list?
242 @c What is a circular list?
244 @c FIXME::martin: Maybe steal some graphics from the Elisp reference
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.
259 @subsubsection List Read Syntax
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.}.
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}
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:
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
292 @node List Predicates
293 @subsubsection List Predicates
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.
301 @deffn {Scheme Procedure} list? x
302 @deffnx {C Function} scm_list_p (x)
303 Return @code{#t} if @var{x} is a proper list, else @code{#f}.
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.
312 @deffn {Scheme Procedure} null? x
313 @deffnx {C Function} scm_null_p (x)
314 Return @code{#t} if @var{x} is the empty list, else @code{#f}.
317 @deftypefn {C Function} int scm_is_null (SCM x)
318 Return 1 when @var{x} is the empty list; otherwise return 0.
322 @node List Constructors
323 @subsubsection List Constructors
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.
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.
334 @deffn {Scheme Procedure} list elem @dots{}
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})
342 Return a new list containing elements @var{elem} @enddots{}.
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
346 not included in the list. None of @var{elem} @dots{} can
347 themselves be @code{SCM_UNDEFINED}, or @code{scm_list_n} will
348 terminate at that point.
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
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.
365 @deffn {Scheme Procedure} list-copy lst
366 @deffnx {C Function} scm_list_copy (lst)
367 Return a (newly-created) copy of @var{lst}.
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.
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}).
385 @subsubsection List Selection
387 These procedures are used to get some information about a list, or to
388 retrieve one or more elements of a list.
391 @deffn {Scheme Procedure} length lst
392 @deffnx {C Function} scm_length (lst)
393 Return the number of elements in list @var{lst}.
396 @deffn {Scheme Procedure} last-pair lst
397 @deffnx {C Function} scm_last_pair (lst)
398 Return the last pair in @var{lst}, signalling an error if
399 @var{lst} is circular.
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}.
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.
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}.
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
427 @subsubsection Append and Reverse
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
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!
442 @deffnx {C Function} scm_append (lstlst)
443 @deffnx {C Function} scm_append_x (lstlst)
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.
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))
453 The last argument @var{obj} may actually be any object; an improper
454 list results if the last argument is not a proper list.
457 (append '(a b) '(c . d)) @result{} (a b c . d)
458 (append '() 'a) @result{} a
461 @code{append} doesn't modify the given lists, but the return may share
462 structure with the final @var{obj}. @code{append!} modifies the
463 given lists to form its return.
465 For @code{scm_append} and @code{scm_append_x}, @var{lstlst} is a list
466 of the list operands @var{lst} @dots{} @var{obj}. That @var{lstlst}
467 itself is not modified or used in the return.
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.
477 @code{reverse} constructs a new list, @code{reverse!} modifies
478 @var{lst} in constructing its return.
480 For @code{reverse!}, the optional @var{newtail} is appended to the
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.
486 @node List Modification
487 @subsubsection List Modification
489 The following procedures modify an existing list, either by changing
490 elements of the list, or by changing the list structure itself.
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}.
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}.
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?}.
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
513 @code{eqv?} to @var{item} removed. This procedure mirrors
514 @code{memv}: @code{delv} compares elements of @var{lst} against
515 @var{item} with @code{eqv?}.
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
521 @code{equal?} to @var{item} removed. This procedure mirrors
522 @code{member}: @code{delete} compares elements of @var{lst}
523 against @var{item} with @code{equal?}.
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}).
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.
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!}.
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!}.
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!}.
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.
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
578 @subsubsection List Searching
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.
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
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
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.
618 See also SRFI-1 which has an extended @code{member} function
619 (@ref{SRFI-1 Searching}).
624 @subsubsection List Mapping
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
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
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.
655 See also SRFI-1 which extends these functions to take lists of unequal
656 lengths (@ref{SRFI-1 Fold and Map}).
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.
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,
672 that vectors are the special case of one dimensional non-uniform arrays
673 and that most array procedures operate happily on vectors
677 * Vector Syntax:: Read syntax for vectors.
678 * Vector Creation:: Dynamic vector creation and validation.
679 * Vector Accessors:: Accessing and modifying vector contents.
680 * Vector Accessing from C:: Ways to work with vectors from C.
681 * Uniform Numeric Vectors:: Vectors of unboxed numeric values.
686 @subsubsection Read Syntax for Vectors
688 Vectors can literally be entered in source code, just like strings,
689 characters or some of the other data types. The read syntax for vectors
690 is as follows: A sharp sign (@code{#}), followed by an opening
691 parentheses, all elements of the vector in their respective read syntax,
692 and finally a closing parentheses. The following are examples of the
693 read syntax for vectors; where the first vector only contains numbers
694 and the second three different object types: a string, a symbol and a
695 number in hexadecimal notation.
699 #("Hello" foo #xdeadbeef)
702 Like lists, vectors have to be quoted:
705 '#(a b c) @result{} #(a b c)
708 @node Vector Creation
709 @subsubsection Dynamic Vector Creation and Validation
711 Instead of creating a vector implicitly by using the read syntax just
712 described, you can create a vector dynamically by calling one of the
713 @code{vector} and @code{list->vector} primitives with the list of Scheme
714 values that you want to place into a vector. The size of the vector
715 thus created is determined implicitly by the number of arguments given.
718 @rnindex list->vector
719 @deffn {Scheme Procedure} vector arg @dots{}
720 @deffnx {Scheme Procedure} list->vector l
721 @deffnx {C Function} scm_vector (l)
722 Return a newly allocated vector composed of the
723 given arguments. Analogous to @code{list}.
726 (vector 'a 'b 'c) @result{} #(a b c)
730 The inverse operation is @code{vector->list}:
732 @rnindex vector->list
733 @deffn {Scheme Procedure} vector->list v
734 @deffnx {C Function} scm_vector_to_list (v)
735 Return a newly allocated list composed of the elements of @var{v}.
738 (vector->list '#(dah dah didah)) @result{} (dah dah didah)
739 (list->vector '(dididit dah)) @result{} #(dididit dah)
743 To allocate a vector with an explicitly specified size, use
744 @code{make-vector}. With this primitive you can also specify an initial
745 value for the vector elements (the same value for all elements, that
749 @deffn {Scheme Procedure} make-vector len [fill]
750 @deffnx {C Function} scm_make_vector (len, fill)
751 Return a newly allocated vector of @var{len} elements. If a
752 second argument is given, then each position is initialized to
753 @var{fill}. Otherwise the initial contents of each position is
757 @deftypefn {C Function} SCM scm_c_make_vector (size_t k, SCM fill)
758 Like @code{scm_make_vector}, but the length is given as a @code{size_t}.
761 To check whether an arbitrary Scheme value @emph{is} a vector, use the
762 @code{vector?} primitive:
765 @deffn {Scheme Procedure} vector? obj
766 @deffnx {C Function} scm_vector_p (obj)
767 Return @code{#t} if @var{obj} is a vector, otherwise return
771 @deftypefn {C Function} int scm_is_vector (SCM obj)
772 Return non-zero when @var{obj} is a vector, otherwise return
776 @node Vector Accessors
777 @subsubsection Accessing and Modifying Vector Contents
779 @code{vector-length} and @code{vector-ref} return information about a
780 given vector, respectively its size and the elements that are contained
783 @rnindex vector-length
784 @deffn {Scheme Procedure} vector-length vector
785 @deffnx {C Function} scm_vector_length (vector)
786 Return the number of elements in @var{vector} as an exact integer.
789 @deftypefn {C Function} size_t scm_c_vector_length (SCM vec)
790 Return the number of elements in @var{vec} as a @code{size_t}.
794 @deffn {Scheme Procedure} vector-ref vec k
795 @deffnx {C Function} scm_vector_ref (vec, k)
796 Return the contents of position @var{k} of @var{vec}.
797 @var{k} must be a valid index of @var{vec}.
799 (vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8
800 (vector-ref '#(1 1 2 3 5 8 13 21)
801 (let ((i (round (* 2 (acos -1)))))
808 @deftypefn {C Function} SCM scm_c_vector_ref (SCM vec, size_t k)
809 Return the contents of position @var{k} (a @code{size_t}) of
813 A vector created by one of the dynamic vector constructor procedures
814 (@pxref{Vector Creation}) can be modified using the following
817 @emph{NOTE:} According to R5RS, it is an error to use any of these
818 procedures on a literally read vector, because such vectors should be
819 considered as constants. Currently, however, Guile does not detect this
823 @deffn {Scheme Procedure} vector-set! vec k obj
824 @deffnx {C Function} scm_vector_set_x (vec, k, obj)
825 Store @var{obj} in position @var{k} of @var{vec}.
826 @var{k} must be a valid index of @var{vec}.
827 The value returned by @samp{vector-set!} is unspecified.
829 (let ((vec (vector 0 '(2 2 2 2) "Anna")))
830 (vector-set! vec 1 '("Sue" "Sue"))
831 vec) @result{} #(0 ("Sue" "Sue") "Anna")
835 @deftypefn {C Function} void scm_c_vector_set_x (SCM vec, size_t k, SCM obj)
836 Store @var{obj} in position @var{k} (a @code{size_t}) of @var{vec}.
839 @rnindex vector-fill!
840 @deffn {Scheme Procedure} vector-fill! vec fill
841 @deffnx {C Function} scm_vector_fill_x (vec, fill)
842 Store @var{fill} in every position of @var{vec}. The value
843 returned by @code{vector-fill!} is unspecified.
846 @deffn {Scheme Procedure} vector-copy vec
847 @deffnx {C Function} scm_vector_copy (vec)
848 Return a copy of @var{vec}.
851 @deffn {Scheme Procedure} vector-move-left! vec1 start1 end1 vec2 start2
852 @deffnx {C Function} scm_vector_move_left_x (vec1, start1, end1, vec2, start2)
853 Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
854 to @var{vec2} starting at position @var{start2}. @var{start1} and
855 @var{start2} are inclusive indices; @var{end1} is exclusive.
857 @code{vector-move-left!} copies elements in leftmost order.
858 Therefore, in the case where @var{vec1} and @var{vec2} refer to the
859 same vector, @code{vector-move-left!} is usually appropriate when
860 @var{start1} is greater than @var{start2}.
863 @deffn {Scheme Procedure} vector-move-right! vec1 start1 end1 vec2 start2
864 @deffnx {C Function} scm_vector_move_right_x (vec1, start1, end1, vec2, start2)
865 Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
866 to @var{vec2} starting at position @var{start2}. @var{start1} and
867 @var{start2} are inclusive indices; @var{end1} is exclusive.
869 @code{vector-move-right!} copies elements in rightmost order.
870 Therefore, in the case where @var{vec1} and @var{vec2} refer to the
871 same vector, @code{vector-move-right!} is usually appropriate when
872 @var{start1} is less than @var{start2}.
875 @node Vector Accessing from C
876 @subsubsection Vector Accessing from C
878 A vector can be read and modified from C with the functions
879 @code{scm_c_vector_ref} and @code{scm_c_vector_set_x}, for example. In
880 addition to these functions, there are two more ways to access vectors
881 from C that might be more efficient in certain situations: you can
882 restrict yourself to @dfn{simple vectors} and then use the very fast
883 @emph{simple vector macros}; or you can use the very general framework
884 for accessing all kinds of arrays (@pxref{Accessing Arrays from C}),
885 which is more verbose, but can deal efficiently with all kinds of
886 vectors (and arrays). For vectors, you can use the
887 @code{scm_vector_elements} and @code{scm_vector_writable_elements}
888 functions as shortcuts.
890 @deftypefn {C Function} int scm_is_simple_vector (SCM obj)
891 Return non-zero if @var{obj} is a simple vector, else return zero. A
892 simple vector is a vector that can be used with the @code{SCM_SIMPLE_*}
895 The following functions are guaranteed to return simple vectors:
896 @code{scm_make_vector}, @code{scm_c_make_vector}, @code{scm_vector},
897 @code{scm_list_to_vector}.
900 @deftypefn {C Macro} size_t SCM_SIMPLE_VECTOR_LENGTH (SCM vec)
901 Evaluates to the length of the simple vector @var{vec}. No type
905 @deftypefn {C Macro} SCM SCM_SIMPLE_VECTOR_REF (SCM vec, size_t idx)
906 Evaluates to the element at position @var{idx} in the simple vector
907 @var{vec}. No type or range checking is done.
910 @deftypefn {C Macro} void SCM_SIMPLE_VECTOR_SET (SCM vec, size_t idx, SCM val)
911 Sets the element at position @var{idx} in the simple vector
912 @var{vec} to @var{val}. No type or range checking is done.
915 @deftypefn {C Function} {const SCM *} scm_vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
916 Acquire a handle for the vector @var{vec} and return a pointer to the
917 elements of it. This pointer can only be used to read the elements of
918 @var{vec}. When @var{vec} is not a vector, an error is signaled. The
919 handle must eventually be released with
920 @code{scm_array_handle_release}.
922 The variables pointed to by @var{lenp} and @var{incp} are filled with
923 the number of elements of the vector and the increment (number of
924 elements) between successive elements, respectively. Successive
925 elements of @var{vec} need not be contiguous in their underlying
926 ``root vector'' returned here; hence the increment is not necessarily
927 equal to 1 and may well be negative too (@pxref{Shared Arrays}).
929 The following example shows the typical way to use this function. It
930 creates a list of all elements of @var{vec} (in reverse order).
933 scm_t_array_handle handle;
939 elt = scm_vector_elements (vec, &handle, &len, &inc);
941 for (i = 0; i < len; i++, elt += inc)
942 list = scm_cons (*elt, list);
943 scm_array_handle_release (&handle);
948 @deftypefn {C Function} {SCM *} scm_vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
949 Like @code{scm_vector_elements} but the pointer can be used to modify
952 The following example shows the typical way to use this function. It
953 fills a vector with @code{#t}.
956 scm_t_array_handle handle;
961 elt = scm_vector_writable_elements (vec, &handle, &len, &inc);
962 for (i = 0; i < len; i++, elt += inc)
964 scm_array_handle_release (&handle);
969 @node Uniform Numeric Vectors
970 @subsubsection Uniform Numeric Vectors
972 A uniform numeric vector is a vector whose elements are all of a single
973 numeric type. Guile offers uniform numeric vectors for signed and
974 unsigned 8-bit, 16-bit, 32-bit, and 64-bit integers, two sizes of
975 floating point values, and complex floating-point numbers of these two
976 sizes. @xref{SRFI-4}, for more information.
978 For many purposes, bytevectors work just as well as uniform vectors, and have
979 the advantage that they integrate well with binary input and output.
980 @xref{Bytevectors}, for more information on bytevectors.
983 @subsection Bit Vectors
986 Bit vectors are zero-origin, one-dimensional arrays of booleans. They
987 are displayed as a sequence of @code{0}s and @code{1}s prefixed by
991 (make-bitvector 8 #f) @result{}
995 Bit vectors are the special case of one dimensional bit arrays, and can
996 thus be used with the array procedures, @xref{Arrays}.
998 @deffn {Scheme Procedure} bitvector? obj
999 @deffnx {C Function} scm_bitvector_p (obj)
1000 Return @code{#t} when @var{obj} is a bitvector, else
1004 @deftypefn {C Function} int scm_is_bitvector (SCM obj)
1005 Return @code{1} when @var{obj} is a bitvector, else return @code{0}.
1008 @deffn {Scheme Procedure} make-bitvector len [fill]
1009 @deffnx {C Function} scm_make_bitvector (len, fill)
1010 Create a new bitvector of length @var{len} and
1011 optionally initialize all elements to @var{fill}.
1014 @deftypefn {C Function} SCM scm_c_make_bitvector (size_t len, SCM fill)
1015 Like @code{scm_make_bitvector}, but the length is given as a
1019 @deffn {Scheme Procedure} bitvector bit @dots{}
1020 @deffnx {C Function} scm_bitvector (bits)
1021 Create a new bitvector with the arguments as elements.
1024 @deffn {Scheme Procedure} bitvector-length vec
1025 @deffnx {C Function} scm_bitvector_length (vec)
1026 Return the length of the bitvector @var{vec}.
1029 @deftypefn {C Function} size_t scm_c_bitvector_length (SCM vec)
1030 Like @code{scm_bitvector_length}, but the length is returned as a
1034 @deffn {Scheme Procedure} bitvector-ref vec idx
1035 @deffnx {C Function} scm_bitvector_ref (vec, idx)
1036 Return the element at index @var{idx} of the bitvector
1040 @deftypefn {C Function} SCM scm_c_bitvector_ref (SCM vec, size_t idx)
1041 Return the element at index @var{idx} of the bitvector
1045 @deffn {Scheme Procedure} bitvector-set! vec idx val
1046 @deffnx {C Function} scm_bitvector_set_x (vec, idx, val)
1047 Set the element at index @var{idx} of the bitvector
1048 @var{vec} when @var{val} is true, else clear it.
1051 @deftypefn {C Function} SCM scm_c_bitvector_set_x (SCM vec, size_t idx, SCM val)
1052 Set the element at index @var{idx} of the bitvector
1053 @var{vec} when @var{val} is true, else clear it.
1056 @deffn {Scheme Procedure} bitvector-fill! vec val
1057 @deffnx {C Function} scm_bitvector_fill_x (vec, val)
1058 Set all elements of the bitvector
1059 @var{vec} when @var{val} is true, else clear them.
1062 @deffn {Scheme Procedure} list->bitvector list
1063 @deffnx {C Function} scm_list_to_bitvector (list)
1064 Return a new bitvector initialized with the elements
1068 @deffn {Scheme Procedure} bitvector->list vec
1069 @deffnx {C Function} scm_bitvector_to_list (vec)
1070 Return a new list initialized with the elements
1071 of the bitvector @var{vec}.
1074 @deffn {Scheme Procedure} bit-count bool bitvector
1075 @deffnx {C Function} scm_bit_count (bool, bitvector)
1076 Return a count of how many entries in @var{bitvector} are equal to
1077 @var{bool}. For example,
1080 (bit-count #f #*000111000) @result{} 6
1084 @deffn {Scheme Procedure} bit-position bool bitvector start
1085 @deffnx {C Function} scm_bit_position (bool, bitvector, start)
1086 Return the index of the first occurrence of @var{bool} in
1087 @var{bitvector}, starting from @var{start}. If there is no @var{bool}
1088 entry between @var{start} and the end of @var{bitvector}, then return
1089 @code{#f}. For example,
1092 (bit-position #t #*000101 0) @result{} 3
1093 (bit-position #f #*0001111 3) @result{} #f
1097 @deffn {Scheme Procedure} bit-invert! bitvector
1098 @deffnx {C Function} scm_bit_invert_x (bitvector)
1099 Modify @var{bitvector} by replacing each element with its negation.
1102 @deffn {Scheme Procedure} bit-set*! bitvector uvec bool
1103 @deffnx {C Function} scm_bit_set_star_x (bitvector, uvec, bool)
1104 Set entries of @var{bitvector} to @var{bool}, with @var{uvec}
1105 selecting the entries to change. The return value is unspecified.
1107 If @var{uvec} is a bit vector, then those entries where it has
1108 @code{#t} are the ones in @var{bitvector} which are set to @var{bool}.
1109 @var{uvec} and @var{bitvector} must be the same length. When
1110 @var{bool} is @code{#t} it's like @var{uvec} is OR'ed into
1111 @var{bitvector}. Or when @var{bool} is @code{#f} it can be seen as an
1115 (define bv #*01000010)
1116 (bit-set*! bv #*10010001 #t)
1118 @result{} #*11010011
1121 If @var{uvec} is a uniform vector of unsigned long integers, then
1122 they're indexes into @var{bitvector} which are set to @var{bool}.
1125 (define bv #*01000010)
1126 (bit-set*! bv #u(5 2 7) #t)
1128 @result{} #*01100111
1132 @deffn {Scheme Procedure} bit-count* bitvector uvec bool
1133 @deffnx {C Function} scm_bit_count_star (bitvector, uvec, bool)
1134 Return a count of how many entries in @var{bitvector} are equal to
1135 @var{bool}, with @var{uvec} selecting the entries to consider.
1137 @var{uvec} is interpreted in the same way as for @code{bit-set*!}
1138 above. Namely, if @var{uvec} is a bit vector then entries which have
1139 @code{#t} there are considered in @var{bitvector}. Or if @var{uvec}
1140 is a uniform vector of unsigned long integers then it's the indexes in
1141 @var{bitvector} to consider.
1146 (bit-count* #*01110111 #*11001101 #t) @result{} 3
1147 (bit-count* #*01110111 #u(7 0 4) #f) @result{} 2
1151 @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)
1152 Like @code{scm_vector_elements} (@pxref{Vector Accessing from C}), but
1153 for bitvectors. The variable pointed to by @var{offp} is set to the
1154 value returned by @code{scm_array_handle_bit_elements_offset}. See
1155 @code{scm_array_handle_bit_elements} for how to use the returned
1156 pointer and the offset.
1159 @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)
1160 Like @code{scm_bitvector_elements}, but the pointer is good for reading
1168 @dfn{Arrays} are a collection of cells organized into an arbitrary
1169 number of dimensions. Each cell can be accessed in constant time by
1170 supplying an index for each dimension.
1172 In the current implementation, an array uses a vector of some kind for
1173 the actual storage of its elements. Any kind of vector will do, so you
1174 can have arrays of uniform numeric values, arrays of characters, arrays
1175 of bits, and of course, arrays of arbitrary Scheme values. For example,
1176 arrays with an underlying @code{c64vector} might be nice for digital
1177 signal processing, while arrays made from a @code{u8vector} might be
1178 used to hold gray-scale images.
1180 The number of dimensions of an array is called its @dfn{rank}. Thus,
1181 a matrix is an array of rank 2, while a vector has rank 1. When
1182 accessing an array element, you have to specify one exact integer for
1183 each dimension. These integers are called the @dfn{indices} of the
1184 element. An array specifies the allowed range of indices for each
1185 dimension via an inclusive lower and upper bound. These bounds can
1186 well be negative, but the upper bound must be greater than or equal to
1187 the lower bound minus one. When all lower bounds of an array are
1188 zero, it is called a @dfn{zero-origin} array.
1190 Arrays can be of rank 0, which could be interpreted as a scalar.
1191 Thus, a zero-rank array can store exactly one object and the list of
1192 indices of this element is the empty list.
1194 Arrays contain zero elements when one of their dimensions has a zero
1195 length. These empty arrays maintain information about their shape: a
1196 matrix with zero columns and 3 rows is different from a matrix with 3
1197 columns and zero rows, which again is different from a vector of
1200 The array procedures are all polymorphic, treating strings, uniform
1201 numeric vectors, bytevectors, bit vectors and ordinary vectors as one
1206 * Array Procedures::
1208 * Accessing Arrays from C::
1212 @subsubsection Array Syntax
1214 An array is displayed as @code{#} followed by its rank, followed by a
1215 tag that describes the underlying vector, optionally followed by
1216 information about its shape, and finally followed by the cells,
1217 organized into dimensions using parentheses.
1219 In more words, the array tag is of the form
1222 #<rank><vectag><@@lower><:len><@@lower><:len>...
1225 where @code{<rank>} is a positive integer in decimal giving the rank of
1226 the array. It is omitted when the rank is 1 and the array is non-shared
1227 and has zero-origin (see below). For shared arrays and for a non-zero
1228 origin, the rank is always printed even when it is 1 to distinguish
1229 them from ordinary vectors.
1231 The @code{<vectag>} part is the tag for a uniform numeric vector, like
1232 @code{u8}, @code{s16}, etc, @code{b} for bitvectors, or @code{a} for
1233 strings. It is empty for ordinary vectors.
1235 The @code{<@@lower>} part is a @samp{@@} character followed by a signed
1236 integer in decimal giving the lower bound of a dimension. There is one
1237 @code{<@@lower>} for each dimension. When all lower bounds are zero,
1238 all @code{<@@lower>} parts are omitted.
1240 The @code{<:len>} part is a @samp{:} character followed by an unsigned
1241 integer in decimal giving the length of a dimension. Like for the lower
1242 bounds, there is one @code{<:len>} for each dimension, and the
1243 @code{<:len>} part always follows the @code{<@@lower>} part for a
1244 dimension. Lengths are only then printed when they can't be deduced
1245 from the nested lists of elements of the array literal, which can happen
1246 when at least one length is zero.
1248 As a special case, an array of rank 0 is printed as
1249 @code{#0<vectag>(<scalar>)}, where @code{<scalar>} is the result of
1250 printing the single element of the array.
1256 is an ordinary array of rank 1 with lower bound 0 in dimension 0.
1257 (I.e., a regular vector.)
1260 is an ordinary array of rank 1 with lower bound 2 in dimension 0.
1262 @item #2((1 2 3) (4 5 6))
1263 is a non-uniform array of rank 2; a 3@cross{}3 matrix with index ranges 0..2
1267 is a uniform u8 array of rank 1.
1269 @item #2u32@@2@@3((1 2) (2 3))
1270 is a uniform u8 array of rank 2 with index ranges 2..3 and 3..4.
1273 is a two-dimensional array with index ranges 0..-1 and 0..-1, i.e.@:
1274 both dimensions have length zero.
1277 is a two-dimensional array with index ranges 0..-1 and 0..1, i.e.@: the
1278 first dimension has length zero, but the second has length 2.
1281 is a rank-zero array with contents 12.
1285 In addition, bytevectors are also arrays, but use a different syntax
1286 (@pxref{Bytevectors}):
1291 is a 3-byte long bytevector, with contents 1, 2, 3.
1295 @node Array Procedures
1296 @subsubsection Array Procedures
1298 When an array is created, the range of each dimension must be
1299 specified, e.g., to create a 2@cross{}3 array with a zero-based index:
1302 (make-array 'ho 2 3) @result{} #2((ho ho ho) (ho ho ho))
1305 The range of each dimension can also be given explicitly, e.g., another
1306 way to create the same array:
1309 (make-array 'ho '(0 1) '(0 2)) @result{} #2((ho ho ho) (ho ho ho))
1312 The following procedures can be used with arrays (or vectors). An
1313 argument shown as @var{idx}@dots{} means one parameter for each
1314 dimension in the array. A @var{idxlist} argument means a list of such
1315 values, one for each dimension.
1318 @deffn {Scheme Procedure} array? obj
1319 @deffnx {C Function} scm_array_p (obj, unused)
1320 Return @code{#t} if the @var{obj} is an array, and @code{#f} if
1323 The second argument to scm_array_p is there for historical reasons,
1324 but it is not used. You should always pass @code{SCM_UNDEFINED} as
1328 @deffn {Scheme Procedure} typed-array? obj type
1329 @deffnx {C Function} scm_typed_array_p (obj, type)
1330 Return @code{#t} if the @var{obj} is an array of type @var{type}, and
1334 @deftypefn {C Function} int scm_is_array (SCM obj)
1335 Return @code{1} if the @var{obj} is an array and @code{0} if not.
1338 @deftypefn {C Function} int scm_is_typed_array (SCM obj, SCM type)
1339 Return @code{0} if the @var{obj} is an array of type @var{type}, and
1343 @deffn {Scheme Procedure} make-array fill bound @dots{}
1344 @deffnx {C Function} scm_make_array (fill, bounds)
1345 Equivalent to @code{(make-typed-array #t @var{fill} @var{bound} ...)}.
1348 @deffn {Scheme Procedure} make-typed-array type fill bound @dots{}
1349 @deffnx {C Function} scm_make_typed_array (type, fill, bounds)
1350 Create and return an array that has as many dimensions as there are
1351 @var{bound}s and (maybe) fill it with @var{fill}.
1353 The underlying storage vector is created according to @var{type},
1354 which must be a symbol whose name is the `vectag' of the array as
1355 explained above, or @code{#t} for ordinary, non-specialized arrays.
1357 For example, using the symbol @code{f64} for @var{type} will create an
1358 array that uses a @code{f64vector} for storing its elements, and
1359 @code{a} will use a string.
1361 When @var{fill} is not the special @emph{unspecified} value, the new
1362 array is filled with @var{fill}. Otherwise, the initial contents of
1363 the array is unspecified. The special @emph{unspecified} value is
1364 stored in the variable @code{*unspecified*} so that for example
1365 @code{(make-typed-array 'u32 *unspecified* 4)} creates a uninitialized
1366 @code{u32} vector of length 4.
1368 Each @var{bound} may be a positive non-zero integer @var{n}, in which
1369 case the index for that dimension can range from 0 through @var{n}-1; or
1370 an explicit index range specifier in the form @code{(LOWER UPPER)},
1371 where both @var{lower} and @var{upper} are integers, possibly less than
1372 zero, and possibly the same number (however, @var{lower} cannot be
1373 greater than @var{upper}).
1376 @deffn {Scheme Procedure} list->array dimspec list
1377 Equivalent to @code{(list->typed-array #t @var{dimspec}
1381 @deffn {Scheme Procedure} list->typed-array type dimspec list
1382 @deffnx {C Function} scm_list_to_typed_array (type, dimspec, list)
1383 Return an array of the type indicated by @var{type} with elements the
1384 same as those of @var{list}.
1386 The argument @var{dimspec} determines the number of dimensions of the
1387 array and their lower bounds. When @var{dimspec} is an exact integer,
1388 it gives the number of dimensions directly and all lower bounds are
1389 zero. When it is a list of exact integers, then each element is the
1390 lower index bound of a dimension, and there will be as many dimensions
1391 as elements in the list.
1394 @deffn {Scheme Procedure} array-type array
1395 @deffnx {C Function} scm_array_type (array)
1396 Return the type of @var{array}. This is the `vectag' used for
1397 printing @var{array} (or @code{#t} for ordinary arrays) and can be
1398 used with @code{make-typed-array} to create an array of the same kind
1402 @deffn {Scheme Procedure} array-ref array idx @dots{}
1403 @deffnx {C Function} scm_array_ref (array, idxlist)
1404 Return the element at @code{(idx @dots{})} in @var{array}.
1407 (define a (make-array 999 '(1 2) '(3 4)))
1408 (array-ref a 2 4) @result{} 999
1412 @deffn {Scheme Procedure} array-in-bounds? array idx @dots{}
1413 @deffnx {C Function} scm_array_in_bounds_p (array, idxlist)
1414 Return @code{#t} if the given indices would be acceptable to
1418 (define a (make-array #f '(1 2) '(3 4)))
1419 (array-in-bounds? a 2 3) @result{} #t
1420 (array-in-bounds? a 0 0) @result{} #f
1424 @deffn {Scheme Procedure} array-set! array obj idx @dots{}
1425 @deffnx {C Function} scm_array_set_x (array, obj, idxlist)
1426 Set the element at @code{(idx @dots{})} in @var{array} to @var{obj}.
1427 The return value is unspecified.
1430 (define a (make-array #f '(0 1) '(0 1)))
1431 (array-set! a #t 1 1)
1432 a @result{} #2((#f #f) (#f #t))
1436 @deffn {Scheme Procedure} array-shape array
1437 @deffnx {Scheme Procedure} array-dimensions array
1438 @deffnx {C Function} scm_array_dimensions (array)
1439 Return a list of the bounds for each dimension of @var{array}.
1441 @code{array-shape} gives @code{(@var{lower} @var{upper})} for each
1442 dimension. @code{array-dimensions} instead returns just
1443 @math{@var{upper}+1} for dimensions with a 0 lower bound. Both are
1444 suitable as input to @code{make-array}.
1449 (define a (make-array 'foo '(-1 3) 5))
1450 (array-shape a) @result{} ((-1 3) (0 4))
1451 (array-dimensions a) @result{} ((-1 3) 5)
1455 @deffn {Scheme Procedure} array-length array
1456 @deffnx {C Function} scm_array_length (array)
1457 @deffnx {C Function} size_t scm_c_array_length (array)
1458 Return the length of an array: its first dimension. It is an error to
1459 ask for the length of an array of rank 0.
1462 @deffn {Scheme Procedure} array-rank array
1463 @deffnx {C Function} scm_array_rank (array)
1464 Return the rank of @var{array}.
1467 @deftypefn {C Function} size_t scm_c_array_rank (SCM array)
1468 Return the rank of @var{array} as a @code{size_t}.
1471 @deffn {Scheme Procedure} array->list array
1472 @deffnx {C Function} scm_array_to_list (array)
1473 Return a list consisting of all the elements, in order, of
1477 @c FIXME: Describe how the order affects the copying (it matters for
1478 @c shared arrays with the same underlying root vector, presumably).
1480 @deffn {Scheme Procedure} array-copy! src dst
1481 @deffnx {Scheme Procedure} array-copy-in-order! src dst
1482 @deffnx {C Function} scm_array_copy_x (src, dst)
1483 Copy every element from vector or array @var{src} to the corresponding
1484 element of @var{dst}. @var{dst} must have the same rank as @var{src},
1485 and be at least as large in each dimension. The return value is
1489 @deffn {Scheme Procedure} array-fill! array fill
1490 @deffnx {C Function} scm_array_fill_x (array, fill)
1491 Store @var{fill} in every element of @var{array}. The value returned
1495 @c begin (texi-doc-string "guile" "array-equal?")
1496 @deffn {Scheme Procedure} array-equal? array @dots{}
1497 Return @code{#t} if all arguments are arrays with the same shape, the
1498 same type, and have corresponding elements which are either
1499 @code{equal?} or @code{array-equal?}. This function differs from
1500 @code{equal?} (@pxref{Equality}) in that all arguments must be arrays.
1503 @c FIXME: array-map! accepts no source arrays at all, and in that
1504 @c case makes calls "(proc)". Is that meant to be a documented
1507 @c FIXME: array-for-each doesn't say what happens if the sources have
1508 @c different index ranges. The code currently iterates over the
1509 @c indices of the first and expects the others to cover those. That
1510 @c at least vaguely matches array-map!, but is it meant to be a
1511 @c documented feature?
1513 @deffn {Scheme Procedure} array-map! dst proc src @dots{}
1514 @deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
1515 @deffnx {C Function} scm_array_map_x (dst, proc, srclist)
1516 Set each element of the @var{dst} array to values obtained from calls
1517 to @var{proc}. The value returned is unspecified.
1519 Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})},
1520 where each @var{elem} is from the corresponding @var{src} array, at
1521 the @var{dst} index. @code{array-map-in-order!} makes the calls in
1522 row-major order, @code{array-map!} makes them in an unspecified order.
1524 The @var{src} arrays must have the same number of dimensions as
1525 @var{dst}, and must have a range for each dimension which covers the
1526 range in @var{dst}. This ensures all @var{dst} indices are valid in
1530 @deffn {Scheme Procedure} array-for-each proc src1 src2 @dots{}
1531 @deffnx {C Function} scm_array_for_each (proc, src1, srclist)
1532 Apply @var{proc} to each tuple of elements of @var{src1} @var{src2}
1533 @dots{}, in row-major order. The value returned is unspecified.
1536 @deffn {Scheme Procedure} array-index-map! dst proc
1537 @deffnx {C Function} scm_array_index_map_x (dst, proc)
1538 Set each element of the @var{dst} array to values returned by calls to
1539 @var{proc}. The value returned is unspecified.
1541 Each call is @code{(@var{proc} @var{i1} @dots{} @var{iN})}, where
1542 @var{i1}@dots{}@var{iN} is the destination index, one parameter for
1543 each dimension. The order in which the calls are made is unspecified.
1545 For example, to create a @m{4\times4, 4x4} matrix representing a
1549 \advance\leftskip by 2\lispnarrowing {
1567 (define a (make-array #f 4 4))
1568 (array-index-map! a (lambda (i j)
1569 (modulo (+ i j) 4)))
1573 @deffn {Scheme Procedure} uniform-array-read! ra [port_or_fd [start [end]]]
1574 @deffnx {C Function} scm_uniform_array_read_x (ra, port_or_fd, start, end)
1575 Attempt to read all elements of array @var{ra}, in lexicographic order, as
1576 binary objects from @var{port_or_fd}.
1577 If an end of file is encountered,
1578 the objects up to that point are put into @var{ra}
1579 (starting at the beginning) and the remainder of the array is
1582 The optional arguments @var{start} and @var{end} allow
1583 a specified region of a vector (or linearized array) to be read,
1584 leaving the remainder of the vector unchanged.
1586 @code{uniform-array-read!} returns the number of objects read.
1587 @var{port_or_fd} may be omitted, in which case it defaults to the value
1588 returned by @code{(current-input-port)}.
1591 @deffn {Scheme Procedure} uniform-array-write ra [port_or_fd [start [end]]]
1592 @deffnx {C Function} scm_uniform_array_write (ra, port_or_fd, start, end)
1593 Writes all elements of @var{ra} as binary objects to
1596 The optional arguments @var{start}
1598 a specified region of a vector (or linearized array) to be written.
1600 The number of objects actually written is returned.
1601 @var{port_or_fd} may be
1602 omitted, in which case it defaults to the value returned by
1603 @code{(current-output-port)}.
1607 @subsubsection Shared Arrays
1609 @deffn {Scheme Procedure} make-shared-array oldarray mapfunc bound @dots{}
1610 @deffnx {C Function} scm_make_shared_array (oldarray, mapfunc, boundlist)
1611 Return a new array which shares the storage of @var{oldarray}.
1612 Changes made through either affect the same underlying storage. The
1613 @var{bound} @dots{} arguments are the shape of the new array, the same
1614 as @code{make-array} (@pxref{Array Procedures}).
1616 @var{mapfunc} translates coordinates from the new array to the
1617 @var{oldarray}. It's called as @code{(@var{mapfunc} newidx1 @dots{})}
1618 with one parameter for each dimension of the new array, and should
1619 return a list of indices for @var{oldarray}, one for each dimension of
1622 @var{mapfunc} must be affine linear, meaning that each @var{oldarray}
1623 index must be formed by adding integer multiples (possibly negative)
1624 of some or all of @var{newidx1} etc, plus a possible integer offset.
1625 The multiples and offset must be the same in each call.
1628 One good use for a shared array is to restrict the range of some
1629 dimensions, so as to apply say @code{array-for-each} or
1630 @code{array-fill!} to only part of an array. The plain @code{list}
1631 function can be used for @var{mapfunc} in this case, making no changes
1632 to the index values. For example,
1635 (make-shared-array #2((a b c) (d e f) (g h i)) list 3 2)
1636 @result{} #2((a b) (d e) (g h))
1639 The new array can have fewer dimensions than @var{oldarray}, for
1640 example to take a column from an array.
1643 (make-shared-array #2((a b c) (d e f) (g h i))
1644 (lambda (i) (list i 2))
1649 A diagonal can be taken by using the single new array index for both
1650 row and column in the old array. For example,
1653 (make-shared-array #2((a b c) (d e f) (g h i))
1654 (lambda (i) (list i i))
1659 Dimensions can be increased by for instance considering portions of a
1660 one dimensional array as rows in a two dimensional array.
1661 (@code{array-contents} below can do the opposite, flattening an
1665 (make-shared-array #1(a b c d e f g h i j k l)
1666 (lambda (i j) (list (+ (* i 3) j)))
1668 @result{} #2((a b c) (d e f) (g h i) (j k l))
1671 By negating an index the order that elements appear can be reversed.
1672 The following just reverses the column order,
1675 (make-shared-array #2((a b c) (d e f) (g h i))
1676 (lambda (i j) (list i (- 2 j)))
1678 @result{} #2((c b a) (f e d) (i h g))
1681 A fixed offset on indexes allows for instance a change from a 0 based
1685 (define x #2((a b c) (d e f) (g h i)))
1686 (define y (make-shared-array x
1687 (lambda (i j) (list (1- i) (1- j)))
1689 (array-ref x 0 0) @result{} a
1690 (array-ref y 1 1) @result{} a
1693 A multiple on an index allows every Nth element of an array to be
1694 taken. The following is every third element,
1697 (make-shared-array #1(a b c d e f g h i j k l)
1698 (lambda (i) (list (* i 3)))
1700 @result{} #1(a d g j)
1703 The above examples can be combined to make weird and wonderful
1704 selections from an array, but it's important to note that because
1705 @var{mapfunc} must be affine linear, arbitrary permutations are not
1708 In the current implementation, @var{mapfunc} is not called for every
1709 access to the new array but only on some sample points to establish a
1710 base and stride for new array indices in @var{oldarray} data. A few
1711 sample points are enough because @var{mapfunc} is linear.
1714 @deffn {Scheme Procedure} shared-array-increments array
1715 @deffnx {C Function} scm_shared_array_increments (array)
1716 For each dimension, return the distance between elements in the root vector.
1719 @deffn {Scheme Procedure} shared-array-offset array
1720 @deffnx {C Function} scm_shared_array_offset (array)
1721 Return the root vector index of the first element in the array.
1724 @deffn {Scheme Procedure} shared-array-root array
1725 @deffnx {C Function} scm_shared_array_root (array)
1726 Return the root vector of a shared array.
1729 @deffn {Scheme Procedure} array-contents array [strict]
1730 @deffnx {C Function} scm_array_contents (array, strict)
1731 If @var{array} may be @dfn{unrolled} into a one dimensional shared array
1732 without changing their order (last subscript changing fastest), then
1733 @code{array-contents} returns that shared array, otherwise it returns
1734 @code{#f}. All arrays made by @code{make-array} and
1735 @code{make-typed-array} may be unrolled, some arrays made by
1736 @code{make-shared-array} may not be.
1738 If the optional argument @var{strict} is provided, a shared array will
1739 be returned only if its elements are stored internally contiguous in
1743 @deffn {Scheme Procedure} transpose-array array dim1 dim2 @dots{}
1744 @deffnx {C Function} scm_transpose_array (array, dimlist)
1745 Return an array sharing contents with @var{array}, but with
1746 dimensions arranged in a different order. There must be one
1747 @var{dim} argument for each dimension of @var{array}.
1748 @var{dim1}, @var{dim2}, @dots{} should be integers between 0
1749 and the rank of the array to be returned. Each integer in that
1750 range must appear at least once in the argument list.
1752 The values of @var{dim1}, @var{dim2}, @dots{} correspond to
1753 dimensions in the array to be returned, and their positions in the
1754 argument list to dimensions of @var{array}. Several @var{dim}s
1755 may have the same value, in which case the returned array will
1756 have smaller rank than @var{array}.
1759 (transpose-array '#2((a b) (c d)) 1 0) @result{} #2((a c) (b d))
1760 (transpose-array '#2((a b) (c d)) 0 0) @result{} #1(a d)
1761 (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) @result{}
1762 #2((a 4) (b 5) (c 6))
1766 @node Accessing Arrays from C
1767 @subsubsection Accessing Arrays from C
1769 For interworking with external C code, Guile provides an API to allow C
1770 code to access the elements of a Scheme array. In particular, for
1771 uniform numeric arrays, the API exposes the underlying uniform data as a
1772 C array of numbers of the relevant type.
1774 While pointers to the elements of an array are in use, the array itself
1775 must be protected so that the pointer remains valid. Such a protected
1776 array is said to be @dfn{reserved}. A reserved array can be read but
1777 modifications to it that would cause the pointer to its elements to
1778 become invalid are prevented. When you attempt such a modification, an
1781 (This is similar to locking the array while it is in use, but without
1782 the danger of a deadlock. In a multi-threaded program, you will need
1783 additional synchronization to avoid modifying reserved arrays.)
1785 You must take care to always unreserve an array after reserving it,
1786 even in the presence of non-local exits. If a non-local exit can
1787 happen between these two calls, you should install a dynwind context
1788 that releases the array when it is left (@pxref{Dynamic Wind}).
1790 In addition, array reserving and unreserving must be properly
1791 paired. For instance, when reserving two or more arrays in a certain
1792 order, you need to unreserve them in the opposite order.
1794 Once you have reserved an array and have retrieved the pointer to its
1795 elements, you must figure out the layout of the elements in memory.
1796 Guile allows slices to be taken out of arrays without actually making a
1797 copy, such as making an alias for the diagonal of a matrix that can be
1798 treated as a vector. Arrays that result from such an operation are not
1799 stored contiguously in memory and when working with their elements
1800 directly, you need to take this into account.
1802 The layout of array elements in memory can be defined via a
1803 @emph{mapping function} that computes a scalar position from a vector of
1804 indices. The scalar position then is the offset of the element with the
1805 given indices from the start of the storage block of the array.
1807 In Guile, this mapping function is restricted to be @dfn{affine}: all
1808 mapping functions of Guile arrays can be written as @code{p = b +
1809 c[0]*i[0] + c[1]*i[1] + ... + c[n-1]*i[n-1]} where @code{i[k]} is the
1810 @nicode{k}th index and @code{n} is the rank of the array. For
1811 example, a matrix of size 3x3 would have @code{b == 0}, @code{c[0] ==
1812 3} and @code{c[1] == 1}. When you transpose this matrix (with
1813 @code{transpose-array}, say), you will get an array whose mapping
1814 function has @code{b == 0}, @code{c[0] == 1} and @code{c[1] == 3}.
1816 The function @code{scm_array_handle_dims} gives you (indirect) access to
1817 the coefficients @code{c[k]}.
1820 Note that there are no functions for accessing the elements of a
1821 character array yet. Once the string implementation of Guile has been
1822 changed to use Unicode, we will provide them.
1824 @deftp {C Type} scm_t_array_handle
1825 This is a structure type that holds all information necessary to manage
1826 the reservation of arrays as explained above. Structures of this type
1827 must be allocated on the stack and must only be accessed by the
1828 functions listed below.
1831 @deftypefn {C Function} void scm_array_get_handle (SCM array, scm_t_array_handle *handle)
1832 Reserve @var{array}, which must be an array, and prepare @var{handle} to
1833 be used with the functions below. You must eventually call
1834 @code{scm_array_handle_release} on @var{handle}, and do this in a
1835 properly nested fashion, as explained above. The structure pointed to
1836 by @var{handle} does not need to be initialized before calling this
1840 @deftypefn {C Function} void scm_array_handle_release (scm_t_array_handle *handle)
1841 End the array reservation represented by @var{handle}. After a call to
1842 this function, @var{handle} might be used for another reservation.
1845 @deftypefn {C Function} size_t scm_array_handle_rank (scm_t_array_handle *handle)
1846 Return the rank of the array represented by @var{handle}.
1849 @deftp {C Type} scm_t_array_dim
1850 This structure type holds information about the layout of one dimension
1851 of an array. It includes the following fields:
1856 The lower and upper bounds (both inclusive) of the permissible index
1857 range for the given dimension. Both values can be negative, but
1858 @var{lbnd} is always less than or equal to @var{ubnd}.
1861 The distance from one element of this dimension to the next. Note, too,
1862 that this can be negative.
1866 @deftypefn {C Function} {const scm_t_array_dim *} scm_array_handle_dims (scm_t_array_handle *handle)
1867 Return a pointer to a C vector of information about the dimensions of
1868 the array represented by @var{handle}. This pointer is valid as long as
1869 the array remains reserved. As explained above, the
1870 @code{scm_t_array_dim} structures returned by this function can be used
1871 calculate the position of an element in the storage block of the array
1874 This position can then be used as an index into the C array pointer
1875 returned by the various @code{scm_array_handle_<foo>_elements}
1876 functions, or with @code{scm_array_handle_ref} and
1877 @code{scm_array_handle_set}.
1879 Here is how one can compute the position @var{pos} of an element given
1880 its indices in the vector @var{indices}:
1883 ssize_t indices[RANK];
1884 scm_t_array_dim *dims;
1889 for (i = 0; i < RANK; i++)
1891 if (indices[i] < dims[i].lbnd || indices[i] > dims[i].ubnd)
1893 pos += (indices[i] - dims[i].lbnd) * dims[i].inc;
1898 @deftypefn {C Function} ssize_t scm_array_handle_pos (scm_t_array_handle *handle, SCM indices)
1899 Compute the position corresponding to @var{indices}, a list of
1900 indices. The position is computed as described above for
1901 @code{scm_array_handle_dims}. The number of the indices and their
1902 range is checked and an appropriate error is signalled for invalid
1906 @deftypefn {C Function} SCM scm_array_handle_ref (scm_t_array_handle *handle, ssize_t pos)
1907 Return the element at position @var{pos} in the storage block of the
1908 array represented by @var{handle}. Any kind of array is acceptable. No
1909 range checking is done on @var{pos}.
1912 @deftypefn {C Function} void scm_array_handle_set (scm_t_array_handle *handle, ssize_t pos, SCM val)
1913 Set the element at position @var{pos} in the storage block of the array
1914 represented by @var{handle} to @var{val}. Any kind of array is
1915 acceptable. No range checking is done on @var{pos}. An error is
1916 signalled when the array can not store @var{val}.
1919 @deftypefn {C Function} {const SCM *} scm_array_handle_elements (scm_t_array_handle *handle)
1920 Return a pointer to the elements of a ordinary array of general Scheme
1921 values (i.e., a non-uniform array) for reading. This pointer is valid
1922 as long as the array remains reserved.
1925 @deftypefn {C Function} {SCM *} scm_array_handle_writable_elements (scm_t_array_handle *handle)
1926 Like @code{scm_array_handle_elements}, but the pointer is good for
1927 reading and writing.
1930 @deftypefn {C Function} {const void *} scm_array_handle_uniform_elements (scm_t_array_handle *handle)
1931 Return a pointer to the elements of a uniform numeric array for reading.
1932 This pointer is valid as long as the array remains reserved. The size
1933 of each element is given by @code{scm_array_handle_uniform_element_size}.
1936 @deftypefn {C Function} {void *} scm_array_handle_uniform_writable_elements (scm_t_array_handle *handle)
1937 Like @code{scm_array_handle_uniform_elements}, but the pointer is good
1938 reading and writing.
1941 @deftypefn {C Function} size_t scm_array_handle_uniform_element_size (scm_t_array_handle *handle)
1942 Return the size of one element of the uniform numeric array represented
1946 @deftypefn {C Function} {const scm_t_uint8 *} scm_array_handle_u8_elements (scm_t_array_handle *handle)
1947 @deftypefnx {C Function} {const scm_t_int8 *} scm_array_handle_s8_elements (scm_t_array_handle *handle)
1948 @deftypefnx {C Function} {const scm_t_uint16 *} scm_array_handle_u16_elements (scm_t_array_handle *handle)
1949 @deftypefnx {C Function} {const scm_t_int16 *} scm_array_handle_s16_elements (scm_t_array_handle *handle)
1950 @deftypefnx {C Function} {const scm_t_uint32 *} scm_array_handle_u32_elements (scm_t_array_handle *handle)
1951 @deftypefnx {C Function} {const scm_t_int32 *} scm_array_handle_s32_elements (scm_t_array_handle *handle)
1952 @deftypefnx {C Function} {const scm_t_uint64 *} scm_array_handle_u64_elements (scm_t_array_handle *handle)
1953 @deftypefnx {C Function} {const scm_t_int64 *} scm_array_handle_s64_elements (scm_t_array_handle *handle)
1954 @deftypefnx {C Function} {const float *} scm_array_handle_f32_elements (scm_t_array_handle *handle)
1955 @deftypefnx {C Function} {const double *} scm_array_handle_f64_elements (scm_t_array_handle *handle)
1956 @deftypefnx {C Function} {const float *} scm_array_handle_c32_elements (scm_t_array_handle *handle)
1957 @deftypefnx {C Function} {const double *} scm_array_handle_c64_elements (scm_t_array_handle *handle)
1958 Return a pointer to the elements of a uniform numeric array of the
1959 indicated kind for reading. This pointer is valid as long as the array
1962 The pointers for @code{c32} and @code{c64} uniform numeric arrays point
1963 to pairs of floating point numbers. The even index holds the real part,
1964 the odd index the imaginary part of the complex number.
1967 @deftypefn {C Function} {scm_t_uint8 *} scm_array_handle_u8_writable_elements (scm_t_array_handle *handle)
1968 @deftypefnx {C Function} {scm_t_int8 *} scm_array_handle_s8_writable_elements (scm_t_array_handle *handle)
1969 @deftypefnx {C Function} {scm_t_uint16 *} scm_array_handle_u16_writable_elements (scm_t_array_handle *handle)
1970 @deftypefnx {C Function} {scm_t_int16 *} scm_array_handle_s16_writable_elements (scm_t_array_handle *handle)
1971 @deftypefnx {C Function} {scm_t_uint32 *} scm_array_handle_u32_writable_elements (scm_t_array_handle *handle)
1972 @deftypefnx {C Function} {scm_t_int32 *} scm_array_handle_s32_writable_elements (scm_t_array_handle *handle)
1973 @deftypefnx {C Function} {scm_t_uint64 *} scm_array_handle_u64_writable_elements (scm_t_array_handle *handle)
1974 @deftypefnx {C Function} {scm_t_int64 *} scm_array_handle_s64_writable_elements (scm_t_array_handle *handle)
1975 @deftypefnx {C Function} {float *} scm_array_handle_f32_writable_elements (scm_t_array_handle *handle)
1976 @deftypefnx {C Function} {double *} scm_array_handle_f64_writable_elements (scm_t_array_handle *handle)
1977 @deftypefnx {C Function} {float *} scm_array_handle_c32_writable_elements (scm_t_array_handle *handle)
1978 @deftypefnx {C Function} {double *} scm_array_handle_c64_writable_elements (scm_t_array_handle *handle)
1979 Like @code{scm_array_handle_<kind>_elements}, but the pointer is good
1980 for reading and writing.
1983 @deftypefn {C Function} {const scm_t_uint32 *} scm_array_handle_bit_elements (scm_t_array_handle *handle)
1984 Return a pointer to the words that store the bits of the represented
1985 array, which must be a bit array.
1987 Unlike other arrays, bit arrays have an additional offset that must be
1988 figured into index calculations. That offset is returned by
1989 @code{scm_array_handle_bit_elements_offset}.
1991 To find a certain bit you first need to calculate its position as
1992 explained above for @code{scm_array_handle_dims} and then add the
1993 offset. This gives the absolute position of the bit, which is always a
1994 non-negative integer.
1996 Each word of the bit array storage block contains exactly 32 bits, with
1997 the least significant bit in that word having the lowest absolute
1998 position number. The next word contains the next 32 bits.
2000 Thus, the following code can be used to access a bit whose position
2001 according to @code{scm_array_handle_dims} is given in @var{pos}:
2005 scm_t_array_handle handle;
2009 size_t word_pos, mask;
2011 scm_array_get_handle (&bit_array, &handle);
2012 bits = scm_array_handle_bit_elements (&handle);
2015 abs_pos = pos + scm_array_handle_bit_elements_offset (&handle);
2016 word_pos = abs_pos / 32;
2017 mask = 1L << (abs_pos % 32);
2019 if (bits[word_pos] & mask)
2022 scm_array_handle_release (&handle);
2027 @deftypefn {C Function} {scm_t_uint32 *} scm_array_handle_bit_writable_elements (scm_t_array_handle *handle)
2028 Like @code{scm_array_handle_bit_elements} but the pointer is good for
2029 reading and writing. You must take care not to modify bits outside of
2030 the allowed index range of the array, even for contiguous arrays.
2038 The @code{(ice-9 vlist)} module provides an implementation of the @dfn{VList}
2039 data structure designed by Phil Bagwell in 2002. VLists are immutable lists,
2040 which can contain any Scheme object. They improve on standard Scheme linked
2041 lists in several areas:
2045 Random access has typically constant-time complexity.
2048 Computing the length of a VList has time complexity logarithmic in the number of
2052 VLists use less storage space than standard lists.
2055 VList elements are stored in contiguous regions, which improves memory locality
2056 and leads to more efficient use of hardware caches.
2059 The idea behind VLists is to store vlist elements in increasingly large
2060 contiguous blocks (implemented as vectors here). These blocks are linked to one
2061 another using a pointer to the next block and an offset within that block. The
2062 size of these blocks form a geometric series with ratio
2063 @code{block-growth-factor} (2 by default).
2065 The VList structure also serves as the basis for the @dfn{VList-based hash
2066 lists} or ``vhashes'', an immutable dictionary type (@pxref{VHashes}).
2068 However, the current implementation in @code{(ice-9 vlist)} has several
2069 noteworthy shortcomings:
2074 It is @emph{not} thread-safe. Although operations on vlists are all
2075 @dfn{referentially transparent} (i.e., purely functional), adding elements to a
2076 vlist with @code{vlist-cons} mutates part of its internal structure, which makes
2077 it non-thread-safe. This could be fixed, but it would slow down
2081 @code{vlist-cons} always allocates at least as much memory as @code{cons}.
2082 Again, Phil Bagwell describes how to fix it, but that would require tuning the
2083 garbage collector in a way that may not be generally beneficial.
2086 @code{vlist-cons} is a Scheme procedure compiled to bytecode, and it does not
2087 compete with the straightforward C implementation of @code{cons}, and with the
2088 fact that the VM has a special @code{cons} instruction.
2092 We hope to address these in the future.
2094 The programming interface exported by @code{(ice-9 vlist)} is defined below.
2095 Most of it is the same as SRFI-1 with an added @code{vlist-} prefix to function
2098 @deffn {Scheme Procedure} vlist? obj
2099 Return true if @var{obj} is a VList.
2102 @defvr {Scheme Variable} vlist-null
2103 The empty VList. Note that it's possible to create an empty VList not
2104 @code{eq?} to @code{vlist-null}; thus, callers should always use
2105 @code{vlist-null?} when testing whether a VList is empty.
2108 @deffn {Scheme Procedure} vlist-null? vlist
2109 Return true if @var{vlist} is empty.
2112 @deffn {Scheme Procedure} vlist-cons item vlist
2113 Return a new vlist with @var{item} as its head and @var{vlist} as its tail.
2116 @deffn {Scheme Procedure} vlist-head vlist
2117 Return the head of @var{vlist}.
2120 @deffn {Scheme Procedure} vlist-tail vlist
2121 Return the tail of @var{vlist}.
2124 @defvr {Scheme Variable} block-growth-factor
2125 A fluid that defines the growth factor of VList blocks, 2 by default.
2128 The functions below provide the usual set of higher-level list operations.
2130 @deffn {Scheme Procedure} vlist-fold proc init vlist
2131 @deffnx {Scheme Procedure} vlist-fold-right proc init vlist
2132 Fold over @var{vlist}, calling @var{proc} for each element, as for SRFI-1
2133 @code{fold} and @code{fold-right} (@pxref{SRFI-1, @code{fold}}).
2136 @deffn {Scheme Procedure} vlist-ref vlist index
2137 Return the element at index @var{index} in @var{vlist}. This is typically a
2138 constant-time operation.
2141 @deffn {Scheme Procedure} vlist-length vlist
2142 Return the length of @var{vlist}. This is typically logarithmic in the number
2143 of elements in @var{vlist}.
2146 @deffn {Scheme Procedure} vlist-reverse vlist
2147 Return a new @var{vlist} whose content are those of @var{vlist} in reverse
2151 @deffn {Scheme Procedure} vlist-map proc vlist
2152 Map @var{proc} over the elements of @var{vlist} and return a new vlist.
2155 @deffn {Scheme Procedure} vlist-for-each proc vlist
2156 Call @var{proc} on each element of @var{vlist}. The result is unspecified.
2159 @deffn {Scheme Procedure} vlist-drop vlist count
2160 Return a new vlist that does not contain the @var{count} first elements of
2161 @var{vlist}. This is typically a constant-time operation.
2164 @deffn {Scheme Procedure} vlist-take vlist count
2165 Return a new vlist that contains only the @var{count} first elements of
2169 @deffn {Scheme Procedure} vlist-filter pred vlist
2170 Return a new vlist containing all the elements from @var{vlist} that satisfy
2174 @deffn {Scheme Procedure} vlist-delete x vlist [equal?]
2175 Return a new vlist corresponding to @var{vlist} without the elements
2176 @var{equal?} to @var{x}.
2179 @deffn {Scheme Procedure} vlist-unfold p f g seed [tail-gen]
2180 @deffnx {Scheme Procedure} vlist-unfold-right p f g seed [tail]
2181 Return a new vlist, as for SRFI-1 @code{unfold} and @code{unfold-right}
2182 (@pxref{SRFI-1, @code{unfold}}).
2185 @deffn {Scheme Procedure} vlist-append vlist @dots{}
2186 Append the given vlists and return the resulting vlist.
2189 @deffn {Scheme Procedure} list->vlist lst
2190 Return a new vlist whose contents correspond to @var{lst}.
2193 @deffn {Scheme Procedure} vlist->list vlist
2194 Return a new list whose contents match those of @var{vlist}.
2197 @node Record Overview
2198 @subsection Record Overview
2203 @dfn{Records}, also called @dfn{structures}, are Scheme's primary
2204 mechanism to define new disjoint types. A @dfn{record type} defines a
2205 list of @dfn{fields} that instances of the type consist of. This is like
2208 Historically, Guile has offered several different ways to define record
2209 types and to create records, offering different features, and making
2210 different trade-offs. Over the years, each ``standard'' has also come
2211 with its own new record interface, leading to a maze of record APIs.
2213 At the highest level is SRFI-9, a high-level record interface
2214 implemented by most Scheme implementations (@pxref{SRFI-9 Records}). It
2215 defines a simple and efficient syntactic abstraction of record types and
2216 their associated type predicate, fields, and field accessors. SRFI-9 is
2217 suitable for most uses, and this is the recommended way to create record
2218 types in Guile. Similar high-level record APIs include SRFI-35
2219 (@pxref{SRFI-35}) and R6RS records (@pxref{rnrs records syntactic}).
2221 Then comes Guile's historical ``records'' API (@pxref{Records}). Record
2222 types defined this way are first-class objects. Introspection
2223 facilities are available, allowing users to query the list of fields or
2224 the value of a specific field at run-time, without prior knowledge of
2227 Finally, the common denominator of these interfaces is Guile's
2228 @dfn{structure} API (@pxref{Structures}). Guile's structures are the
2229 low-level building block for all other record APIs. Application writers
2230 will normally not need to use it.
2232 Records created with these APIs may all be pattern-matched using Guile's
2233 standard pattern matcher (@pxref{Pattern Matching}).
2236 @node SRFI-9 Records
2237 @subsection SRFI-9 Records
2242 SRFI-9 standardizes a syntax for defining new record types and creating
2243 predicate, constructor, and field getter and setter functions. In Guile
2244 this is the recommended option to create new record types (@pxref{Record
2245 Overview}). It can be used with:
2248 (use-modules (srfi srfi-9))
2251 @deffn {Scheme Syntax} define-record-type type @* (constructor fieldname @dots{}) @* predicate @* (fieldname accessor [modifier]) @dots{}
2253 Create a new record type, and make various @code{define}s for using
2254 it. This syntax can only occur at the top-level, not nested within
2257 @var{type} is bound to the record type, which is as per the return
2258 from the core @code{make-record-type}. @var{type} also provides the
2259 name for the record, as per @code{record-type-name}.
2261 @var{constructor} is bound to a function to be called as
2262 @code{(@var{constructor} fieldval @dots{})} to create a new record of
2263 this type. The arguments are initial values for the fields, one
2264 argument for each field, in the order they appear in the
2265 @code{define-record-type} form.
2267 The @var{fieldname}s provide the names for the record fields, as per
2268 the core @code{record-type-fields} etc, and are referred to in the
2269 subsequent accessor/modifier forms.
2271 @var{predicate} is bound to a function to be called as
2272 @code{(@var{predicate} obj)}. It returns @code{#t} or @code{#f}
2273 according to whether @var{obj} is a record of this type.
2275 Each @var{accessor} is bound to a function to be called
2276 @code{(@var{accessor} record)} to retrieve the respective field from a
2277 @var{record}. Similarly each @var{modifier} is bound to a function to
2278 be called @code{(@var{modifier} record val)} to set the respective
2279 field in a @var{record}.
2283 An example will illustrate typical usage,
2286 (define-record-type <employee>
2287 (make-employee name age salary)
2289 (name employee-name)
2290 (age employee-age set-employee-age!)
2291 (salary employee-salary set-employee-salary!))
2294 This creates a new employee data type, with name, age and salary
2295 fields. Accessor functions are created for each field, but no
2296 modifier function for the name (the intention in this example being
2297 that it's established only when an employee object is created). These
2298 can all then be used as for example,
2301 <employee> @result{} #<record-type <employee>>
2303 (define fred (make-employee "Fred" 45 20000.00))
2305 (employee? fred) @result{} #t
2306 (employee-age fred) @result{} 45
2307 (set-employee-salary! fred 25000.00) ;; pay rise
2310 The functions created by @code{define-record-type} are ordinary
2311 top-level @code{define}s. They can be redefined or @code{set!} as
2312 desired, exported from a module, etc.
2314 @unnumberedsubsubsec Non-toplevel Record Definitions
2316 The SRFI-9 specification explicitly disallows record definitions in a
2317 non-toplevel context, such as inside @code{lambda} body or inside a
2318 @var{let} block. However, Guile's implementation does not enforce that
2321 @unnumberedsubsubsec Custom Printers
2323 You may use @code{set-record-type-printer!} to customize the default printing
2324 behavior of records. This is a Guile extension and is not part of SRFI-9. It
2325 is located in the @nicode{(srfi srfi-9 gnu)} module.
2327 @deffn {Scheme Syntax} set-record-type-printer! name proc
2328 Where @var{type} corresponds to the first argument of @code{define-record-type},
2329 and @var{proc} is a procedure accepting two arguments, the record to print, and
2334 This example prints the employee's name in brackets, for instance @code{[Fred]}.
2337 (set-record-type-printer! <employee>
2338 (lambda (record port)
2339 (write-char #\[ port)
2340 (display (employee-name record) port)
2341 (write-char #\] port)))
2344 @unnumberedsubsubsec Functional ``Setters''
2346 @cindex functional setters
2348 When writing code in a functional style, it is desirable to never alter
2349 the contents of records. For such code, a simple way to return new
2350 record instances based on existing ones is highly desirable.
2352 The @code{(srfi srfi-9 gnu)} module extends SRFI-9 with facilities to
2353 return new record instances based on existing ones, only with one or
2354 more field values changed---@dfn{functional setters}. First, the
2355 @code{define-immutable-record-type} works like
2356 @code{define-record-type}, except that fields are immutable and setters
2357 are defined as functional setters.
2359 @deffn {Scheme Syntax} define-immutable-record-type type @* (constructor fieldname @dots{}) @* predicate @* (fieldname accessor [modifier]) @dots{}
2360 Define @var{type} as a new record type, like @code{define-record-type}.
2361 However, the record type is made @emph{immutable} (records may not be
2362 mutated, even with @code{struct-set!}), and any @var{modifier} is
2363 defined to be a functional setter---a procedure that returns a new
2364 record instance with the specified field changed, and leaves the
2365 original unchanged (see example below.)
2369 In addition, the generic @code{set-field} and @code{set-fields} macros
2370 may be applied to any SRFI-9 record.
2372 @deffn {Scheme Syntax} set-field record (field sub-fields ...) value
2373 Return a new record of @var{record}'s type whose fields are equal to
2374 the corresponding fields of @var{record} except for the one specified by
2377 @var{field} must be the name of the getter corresponding to the field of
2378 @var{record} being ``set''. Subsequent @var{sub-fields} must be record
2379 getters designating sub-fields within that field value to be set (see
2383 @deffn {Scheme Syntax} set-fields record ((field sub-fields ...) value) ...
2384 Like @code{set-field}, but can be used to set more than one field at a
2385 time. This expands to code that is more efficient than a series of
2386 single @code{set-field} calls.
2389 To illustrate the use of functional setters, let's assume these two
2390 record type definitions:
2393 (define-record-type <address>
2394 (address street city country)
2396 (street address-street)
2398 (country address-country))
2400 (define-immutable-record-type <person>
2401 (person age email address)
2403 (age person-age set-person-age)
2404 (email person-email set-person-email)
2405 (address person-address set-person-address))
2409 First, note that the @code{<person>} record type definition introduces
2410 named functional setters. These may be used like this:
2414 (address "Franklin Street" "Boston" "USA"))
2417 (person 30 "rms@@gnu.org" fsf-address))
2419 (and (equal? (set-person-age rms 60)
2420 (person 60 "rms@@gnu.org" fsf-address))
2421 (= (person-age rms) 30))
2426 Here, the original @code{<person>} record, to which @var{rms} is bound,
2429 Now, suppose we want to change both the street and age of @var{rms}.
2430 This can be achieved using @code{set-fields}:
2435 ((person-address address-street) "Temple Place"))
2436 @result{} #<<person> age: 60 email: "rms@@gnu.org"
2437 address: #<<address> street: "Temple Place" city: "Boston" country: "USA">>
2441 Notice how the above changed two fields of @var{rms}, including the
2442 @code{street} field of its @code{address} field, in a concise way. Also
2443 note that @code{set-fields} works equally well for types defined with
2444 just @code{define-record-type}.
2449 A @dfn{record type} is a first class object representing a user-defined
2450 data type. A @dfn{record} is an instance of a record type.
2452 Note that in many ways, this interface is too low-level for every-day
2453 use. Most uses of records are better served by SRFI-9 records.
2454 @xref{SRFI-9 Records}.
2456 @deffn {Scheme Procedure} record? obj
2457 Return @code{#t} if @var{obj} is a record of any type and @code{#f}
2460 Note that @code{record?} may be true of any Scheme value; there is no
2461 promise that records are disjoint with other Scheme types.
2464 @deffn {Scheme Procedure} make-record-type type-name field-names [print]
2465 Create and return a new @dfn{record-type descriptor}.
2467 @var{type-name} is a string naming the type. Currently it's only used
2468 in the printed representation of records, and in diagnostics.
2469 @var{field-names} is a list of symbols naming the fields of a record
2470 of the type. Duplicates are not allowed among these symbols.
2473 (make-record-type "employee" '(name age salary))
2476 The optional @var{print} argument is a function used by
2477 @code{display}, @code{write}, etc, for printing a record of the new
2478 type. It's called as @code{(@var{print} record port)} and should look
2479 at @var{record} and write to @var{port}.
2482 @deffn {Scheme Procedure} record-constructor rtd [field-names]
2483 Return a procedure for constructing new members of the type represented
2484 by @var{rtd}. The returned procedure accepts exactly as many arguments
2485 as there are symbols in the given list, @var{field-names}; these are
2486 used, in order, as the initial values of those fields in a new record,
2487 which is returned by the constructor procedure. The values of any
2488 fields not named in that list are unspecified. The @var{field-names}
2489 argument defaults to the list of field names in the call to
2490 @code{make-record-type} that created the type represented by @var{rtd};
2491 if the @var{field-names} argument is provided, it is an error if it
2492 contains any duplicates or any symbols not in the default list.
2495 @deffn {Scheme Procedure} record-predicate rtd
2496 Return a procedure for testing membership in the type represented by
2497 @var{rtd}. The returned procedure accepts exactly one argument and
2498 returns a true value if the argument is a member of the indicated record
2499 type; it returns a false value otherwise.
2502 @deffn {Scheme Procedure} record-accessor rtd field-name
2503 Return a procedure for reading the value of a particular field of a
2504 member of the type represented by @var{rtd}. The returned procedure
2505 accepts exactly one argument which must be a record of the appropriate
2506 type; it returns the current value of the field named by the symbol
2507 @var{field-name} in that record. The symbol @var{field-name} must be a
2508 member of the list of field-names in the call to @code{make-record-type}
2509 that created the type represented by @var{rtd}.
2512 @deffn {Scheme Procedure} record-modifier rtd field-name
2513 Return a procedure for writing the value of a particular field of a
2514 member of the type represented by @var{rtd}. The returned procedure
2515 accepts exactly two arguments: first, a record of the appropriate type,
2516 and second, an arbitrary Scheme value; it modifies the field named by
2517 the symbol @var{field-name} in that record to contain the given value.
2518 The returned value of the modifier procedure is unspecified. The symbol
2519 @var{field-name} must be a member of the list of field-names in the call
2520 to @code{make-record-type} that created the type represented by
2524 @deffn {Scheme Procedure} record-type-descriptor record
2525 Return a record-type descriptor representing the type of the given
2526 record. That is, for example, if the returned descriptor were passed to
2527 @code{record-predicate}, the resulting predicate would return a true
2528 value when passed the given record. Note that it is not necessarily the
2529 case that the returned descriptor is the one that was passed to
2530 @code{record-constructor} in the call that created the constructor
2531 procedure that created the given record.
2534 @deffn {Scheme Procedure} record-type-name rtd
2535 Return the type-name associated with the type represented by rtd. The
2536 returned value is @code{eqv?} to the @var{type-name} argument given in
2537 the call to @code{make-record-type} that created the type represented by
2541 @deffn {Scheme Procedure} record-type-fields rtd
2542 Return a list of the symbols naming the fields in members of the type
2543 represented by @var{rtd}. The returned value is @code{equal?} to the
2544 field-names argument given in the call to @code{make-record-type} that
2545 created the type represented by @var{rtd}.
2550 @subsection Structures
2553 A @dfn{structure} is a first class data type which holds Scheme values
2554 or C words in fields numbered 0 upwards. A @dfn{vtable} is a structure
2555 that represents a structure type, giving field types and permissions,
2556 and an optional print function for @code{write} etc.
2558 Structures are lower level than records (@pxref{Records}). Usually,
2559 when you need to represent structured data, you just want to use
2560 records. But sometimes you need to implement new kinds of structured
2561 data abstractions, and for that purpose structures are useful. Indeed,
2562 records in Guile are implemented with structures.
2566 * Structure Basics::
2574 @subsubsection Vtables
2576 A vtable is a structure type, specifying its layout, and other
2577 information. A vtable is actually itself a structure, but there's no
2578 need to worry about that initially (@pxref{Vtable Contents}.)
2580 @deffn {Scheme Procedure} make-vtable fields [print]
2581 Create a new vtable.
2583 @var{fields} is a string describing the fields in the structures to be
2584 created. Each field is represented by two characters, a type letter
2585 and a permissions letter, for example @code{"pw"}. The types are as
2590 @code{p} -- a Scheme value. ``p'' stands for ``protected'' meaning
2591 it's protected against garbage collection.
2594 @code{u} -- an arbitrary word of data (an @code{scm_t_bits}). At the
2595 Scheme level it's read and written as an unsigned integer. ``u''
2596 stands for ``uninterpreted'' (it's not treated as a Scheme value), or
2597 ``unprotected'' (it's not marked during GC), or ``unsigned long'' (its
2598 size), or all of these things.
2601 @code{s} -- a self-reference. Such a field holds the @code{SCM} value
2602 of the structure itself (a circular reference). This can be useful in
2603 C code where you might have a pointer to the data array, and want to
2604 get the Scheme @code{SCM} handle for the structure. In Scheme code it
2608 The second letter for each field is a permission code,
2612 @code{w} -- writable, the field can be read and written.
2614 @code{r} -- read-only, the field can be read but not written.
2616 @code{o} -- opaque, the field can be neither read nor written at the
2617 Scheme level. This can be used for fields which should only be used
2621 Here are some examples. @xref{Tail Arrays}, for information on the
2622 legacy tail array facility.
2625 (make-vtable "pw") ;; one writable field
2626 (make-vtable "prpw") ;; one read-only and one writable
2627 (make-vtable "pwuwuw") ;; one scheme and two uninterpreted
2630 The optional @var{print} argument is a function called by
2631 @code{display} and @code{write} (etc) to give a printed representation
2632 of a structure created from this vtable. It's called
2633 @code{(@var{print} struct port)} and should look at @var{struct} and
2634 write to @var{port}. The default print merely gives a form like
2635 @samp{#<struct ADDR:ADDR>} with a pair of machine addresses.
2637 The following print function for example shows the two fields of its
2642 (lambda (struct port)
2643 (format port "#<~a and ~a>"
2644 (struct-ref struct 0)
2645 (struct-ref struct 1))))
2650 @node Structure Basics
2651 @subsubsection Structure Basics
2653 This section describes the basic procedures for working with
2654 structures. @code{make-struct} creates a structure, and
2655 @code{struct-ref} and @code{struct-set!} access its fields.
2657 @deffn {Scheme Procedure} make-struct vtable tail-size init @dots{}
2658 @deffnx {Scheme Procedure} make-struct/no-tail vtable init @dots{}
2659 Create a new structure, with layout per the given @var{vtable}
2662 The optional @var{init}@dots{} arguments are initial values for the
2663 fields of the structure. This is the only way to
2664 put values in read-only fields. If there are fewer @var{init}
2665 arguments than fields then the defaults are @code{#f} for a Scheme
2666 field (type @code{p}) or 0 for an uninterpreted field (type @code{u}).
2668 Structures also have the ability to allocate a variable number of
2669 additional cells at the end, at their tails. However, this legacy
2670 @dfn{tail array} facilty is confusing and inefficient, and so we do not
2671 recommend it. @xref{Tail Arrays}, for more on the legacy tail array
2674 Type @code{s} self-reference fields, permission @code{o} opaque
2675 fields, and the count field of a tail array are all ignored for the
2676 @var{init} arguments, ie.@: an argument is not consumed by such a
2677 field. An @code{s} is always set to the structure itself, an @code{o}
2678 is always set to @code{#f} or 0 (with the intention that C code will
2679 do something to it later), and the tail count is always the given
2685 (define v (make-vtable "prpwpw"))
2686 (define s (make-struct v 0 123 "abc" 456))
2687 (struct-ref s 0) @result{} 123
2688 (struct-ref s 1) @result{} "abc"
2692 @deftypefn {C Function} SCM scm_make_struct (SCM vtable, SCM tail_size, SCM init_list)
2693 @deftypefnx {C Function} SCM scm_c_make_struct (SCM vtable, SCM tail_size, SCM init, ...)
2694 @deftypefnx {C Function} SCM scm_c_make_structv (SCM vtable, SCM tail_size, size_t n_inits, scm_t_bits init[])
2695 There are a few ways to make structures from C. @code{scm_make_struct}
2696 takes a list, @code{scm_c_make_struct} takes variable arguments
2697 terminated with SCM_UNDEFINED, and @code{scm_c_make_structv} takes a
2701 @deffn {Scheme Procedure} struct? obj
2702 @deffnx {C Function} scm_struct_p (obj)
2703 Return @code{#t} if @var{obj} is a structure, or @code{#f} if not.
2706 @deffn {Scheme Procedure} struct-ref struct n
2707 @deffnx {C Function} scm_struct_ref (struct, n)
2708 Return the contents of field number @var{n} in @var{struct}. The
2709 first field is number 0.
2711 An error is thrown if @var{n} is out of range, or if the field cannot
2712 be read because it's @code{o} opaque.
2715 @deffn {Scheme Procedure} struct-set! struct n value
2716 @deffnx {C Function} scm_struct_set_x (struct, n, value)
2717 Set field number @var{n} in @var{struct} to @var{value}. The first
2720 An error is thrown if @var{n} is out of range, or if the field cannot
2721 be written because it's @code{r} read-only or @code{o} opaque.
2724 @deffn {Scheme Procedure} struct-vtable struct
2725 @deffnx {C Function} scm_struct_vtable (struct)
2726 Return the vtable that describes @var{struct}.
2728 The vtable is effectively the type of the structure. See @ref{Vtable
2729 Contents}, for more on vtables.
2733 @node Vtable Contents
2734 @subsubsection Vtable Contents
2736 A vtable is itself a structure. It has a specific set of fields
2737 describing various aspects of its @dfn{instances}: the structures
2738 created from a vtable. Some of the fields are internal to Guile, some
2739 of them are part of the public interface, and there may be additional
2740 fields added on by the user.
2742 Every vtable has a field for the layout of their instances, a field for
2743 the procedure used to print its instances, and a field for the name of
2744 the vtable itself. Access to the layout and printer is exposed directly
2745 via field indexes. Access to the vtable name is exposed via accessor
2748 @defvr {Scheme Variable} vtable-index-layout
2749 @defvrx {C Macro} scm_vtable_index_layout
2750 The field number of the layout specification in a vtable. The layout
2751 specification is a symbol like @code{pwpw} formed from the fields
2752 string passed to @code{make-vtable}, or created by
2753 @code{make-struct-layout} (@pxref{Meta-Vtables}).
2756 (define v (make-vtable "pwpw" 0))
2757 (struct-ref v vtable-index-layout) @result{} pwpw
2760 This field is read-only, since the layout of structures using a vtable
2764 @defvr {Scheme Variable} vtable-index-printer
2765 @defvrx {C Macro} scm_vtable_index_printer
2766 The field number of the printer function. This field contains @code{#f}
2767 if the default print function should be used.
2770 (define (my-print-func struct port)
2772 (define v (make-vtable "pwpw" my-print-func))
2773 (struct-ref v vtable-index-printer) @result{} my-print-func
2776 This field is writable, allowing the print function to be changed
2780 @deffn {Scheme Procedure} struct-vtable-name vtable
2781 @deffnx {Scheme Procedure} set-struct-vtable-name! vtable name
2782 @deffnx {C Function} scm_struct_vtable_name (vtable)
2783 @deffnx {C Function} scm_set_struct_vtable_name_x (vtable, name)
2784 Get or set the name of @var{vtable}. @var{name} is a symbol and is
2785 used in the default print function when printing structures created
2789 (define v (make-vtable "pw"))
2790 (set-struct-vtable-name! v 'my-name)
2792 (define s (make-struct v 0))
2793 (display s) @print{} #<my-name b7ab3ae0:b7ab3730>
2799 @subsubsection Meta-Vtables
2801 As a structure, a vtable also has a vtable, which is also a structure.
2802 Structures, their vtables, the vtables of the vtables, and so on form a
2803 tree of structures. Making a new structure adds a leaf to the tree, and
2804 if that structure is a vtable, it may be used to create other leaves.
2806 If you traverse up the tree of vtables, via calling
2807 @code{struct-vtable}, eventually you reach a root which is the vtable of
2811 scheme@@(guile-user)> (current-module)
2812 $1 = #<directory (guile-user) 221b090>
2813 scheme@@(guile-user)> (struct-vtable $1)
2814 $2 = #<record-type module>
2815 scheme@@(guile-user)> (struct-vtable $2)
2816 $3 = #<<standard-vtable> 12c30a0>
2817 scheme@@(guile-user)> (struct-vtable $3)
2818 $4 = #<<standard-vtable> 12c3fa0>
2819 scheme@@(guile-user)> (struct-vtable $4)
2820 $5 = #<<standard-vtable> 12c3fa0>
2821 scheme@@(guile-user)> <standard-vtable>
2822 $6 = #<<standard-vtable> 12c3fa0>
2825 In this example, we can say that @code{$1} is an instance of @code{$2},
2826 @code{$2} is an instance of @code{$3}, @code{$3} is an instance of
2827 @code{$4}, and @code{$4}, strangely enough, is an instance of itself.
2828 The value bound to @code{$4} in this console session also bound to
2829 @code{<standard-vtable>} in the default environment.
2831 @defvr {Scheme Variable} <standard-vtable>
2832 A meta-vtable, useful for making new vtables.
2835 All of these values are structures. All but @code{$1} are vtables. As
2836 @code{$2} is an instance of @code{$3}, and @code{$3} is a vtable, we can
2837 say that @code{$3} is a @dfn{meta-vtable}: a vtable that can create
2840 With this definition, we can specify more precisely what a vtable is: a
2841 vtable is a structure made from a meta-vtable. Making a structure from
2842 a meta-vtable runs some special checks to ensure that the first field of
2843 the structure is a valid layout. Additionally, if these checks see that
2844 the layout of the child vtable contains all the required fields of a
2845 vtable, in the correct order, then the child vtable will also be a
2846 meta-table, inheriting a magical bit from the parent.
2848 @deffn {Scheme Procedure} struct-vtable? obj
2849 @deffnx {C Function} scm_struct_vtable_p (obj)
2850 Return @code{#t} if @var{obj} is a vtable structure: an instance of a
2854 @code{<standard-vtable>} is a root of the vtable tree. (Normally there
2855 is only one root in a given Guile process, but due to some legacy
2856 interfaces there may be more than one.)
2858 The set of required fields of a vtable is the set of fields in the
2859 @code{<standard-vtable>}, and is bound to @code{standard-vtable-fields}
2860 in the default environment. It is possible to create a meta-vtable that
2861 with additional fields in its layout, which can be used to create
2862 vtables with additional data:
2865 scheme@@(guile-user)> (struct-ref $3 vtable-index-layout)
2866 $6 = pruhsruhpwphuhuhprprpw
2867 scheme@@(guile-user)> (struct-ref $4 vtable-index-layout)
2868 $7 = pruhsruhpwphuhuh
2869 scheme@@(guile-user)> standard-vtable-fields
2870 $8 = "pruhsruhpwphuhuh"
2871 scheme@@(guile-user)> (struct-ref $2 vtable-offset-user)
2875 In this continuation of our earlier example, @code{$2} is a vtable that
2876 has extra fields, because its vtable, @code{$3}, was made from a
2877 meta-vtable with an extended layout. @code{vtable-offset-user} is a
2878 convenient definition that indicates the number of fields in
2879 @code{standard-vtable-fields}.
2881 @defvr {Scheme Variable} standard-vtable-fields
2882 A string containing the orderedq set of fields that a vtable must have.
2885 @defvr {Scheme Variable} vtable-offset-user
2886 The first index in a vtable that is available for a user.
2889 @deffn {Scheme Procedure} make-struct-layout fields
2890 @deffnx {C Function} scm_make_struct_layout (fields)
2891 Return a structure layout symbol, from a @var{fields} string.
2892 @var{fields} is as described under @code{make-vtable}
2893 (@pxref{Vtables}). An invalid @var{fields} string is an error.
2896 With these definitions, one can define @code{make-vtable} in this way:
2899 (define* (make-vtable fields #:optional printer)
2900 (make-struct/no-tail <standard-vtable>
2901 (make-struct-layout fields)
2906 @node Vtable Example
2907 @subsubsection Vtable Example
2909 Let us bring these points together with an example. Consider a simple
2910 object system with single inheritance. Objects will be normal
2911 structures, and classes will be vtables with three extra class fields:
2912 the name of the class, the parent class, and the list of fields.
2914 So, first we need a meta-vtable that allocates instances with these
2920 (string-append standard-vtable-fields "pwpwpw")
2922 (format port "<<class> ~a>" (class-name x)))))
2926 (eq? (struct-vtable x) <class>)))
2929 To make a structure with a specific meta-vtable, we will use
2930 @code{make-struct/no-tail}, passing it the computed instance layout and
2931 printer, as with @code{make-vtable}, and additionally the extra three
2935 (define (make-class name parent fields)
2936 (let* ((fields (compute-fields parent fields))
2937 (layout (compute-layout fields)))
2938 (make-struct/no-tail <class>
2941 (print-instance x port))
2947 Instances will store their associated data in slots in the structure: as
2948 many slots as there are fields. The @code{compute-layout} procedure
2949 below can compute a layout, and @code{field-index} returns the slot
2950 corresponding to a field.
2953 (define-syntax-rule (define-accessor name n)
2955 (struct-ref obj n)))
2957 ;; Accessors for classes
2958 (define-accessor class-name (+ vtable-offset-user 0))
2959 (define-accessor class-parent (+ vtable-offset-user 1))
2960 (define-accessor class-fields (+ vtable-offset-user 2))
2962 (define (compute-fields parent fields)
2964 (append (class-fields parent) fields)
2967 (define (compute-layout fields)
2969 (string-concatenate (make-list (length fields) "pw"))))
2971 (define (field-index class field)
2972 (list-index (class-fields class) field))
2974 (define (print-instance x port)
2975 (format port "<~a" (class-name (struct-vtable x)))
2976 (for-each (lambda (field idx)
2977 (format port " ~a: ~a" field (struct-ref x idx)))
2978 (class-fields (struct-vtable x))
2979 (iota (length (class-fields (struct-vtable x)))))
2983 So, at this point we can actually make a few classes:
2986 (define-syntax-rule (define-class name parent field ...)
2987 (define name (make-class 'name parent '(field ...))))
2989 (define-class <surface> #f
2992 (define-class <window> <surface>
2996 And finally, make an instance:
2999 (make-struct/no-tail <window> 400 300 10 20)
3000 @result{} <<window> width: 400 height: 300 x: 10 y: 20>
3003 And that's that. Note that there are many possible optimizations and
3004 feature enhancements that can be made to this object system, and the
3005 included GOOPS system does make most of them. For more simple use
3006 cases, the records facility is usually sufficient. But sometimes you
3007 need to make new kinds of data abstractions, and for that purpose,
3011 @subsubsection Tail Arrays
3013 Guile's structures have a facility whereby each instance of a vtable can
3014 contain a variable-length tail array of values. The length of the tail
3015 array is stored in the structure. This facility was originally intended
3016 to allow C code to expose raw C structures with word-sized tail arrays
3019 However, the tail array facility is confusing and doesn't work very
3020 well. It is very rarely used, but it insinuates itself into all
3021 invocations of @code{make-struct}. For this reason the clumsily-named
3022 @code{make-struct/no-tail} procedure can actually be more elegant in
3023 actual use, because it doesn't have a random @code{0} argument stuck in
3026 Tail arrays also inhibit optimization by allowing instances to affect
3027 their shapes. In the absence of tail arrays, all instances of a given
3028 vtable have the same number and kinds of fields. This uniformity can be
3029 exploited by the runtime and the optimizer. The presence of tail arrays
3030 make some of these optimizations more difficult.
3032 Finally, the tail array facility is ad-hoc and does not compose with the
3033 rest of Guile. If a Guile user wants an array with user-specified
3034 length, it's best to use a vector. It is more clear in the code, and
3035 the standard optimization techniques will do a good job with it.
3037 That said, we should mention some details about the interface. A vtable
3038 that has tail array has upper-case permission descriptors: @code{W},
3039 @code{R} or @code{O}, correspoding to tail arrays of writable,
3040 read-only, or opaque elements. A tail array permission descriptor may
3041 only appear in the last element of a vtable layout.
3043 For exampple, @samp{pW} indicates a tail of writable Scheme-valued
3044 fields. The @samp{pW} field itself holds the tail size, and the tail
3045 fields come after it.
3048 (define v (make-vtable "prpW")) ;; one fixed then a tail array
3049 (define s (make-struct v 6 "fixed field" 'x 'y))
3050 (struct-ref s 0) @result{} "fixed field"
3051 (struct-ref s 1) @result{} 2 ;; tail size
3052 (struct-ref s 2) @result{} x ;; tail array ...
3053 (struct-ref s 3) @result{} y
3054 (struct-ref s 4) @result{} #f
3058 @node Dictionary Types
3059 @subsection Dictionary Types
3061 A @dfn{dictionary} object is a data structure used to index
3062 information in a user-defined way. In standard Scheme, the main
3063 aggregate data types are lists and vectors. Lists are not really
3064 indexed at all, and vectors are indexed only by number
3065 (e.g.@: @code{(vector-ref foo 5)}). Often you will find it useful
3066 to index your data on some other type; for example, in a library
3067 catalog you might want to look up a book by the name of its
3068 author. Dictionaries are used to help you organize information in
3071 An @dfn{association list} (or @dfn{alist} for short) is a list of
3072 key-value pairs. Each pair represents a single quantity or
3073 object; the @code{car} of the pair is a key which is used to
3074 identify the object, and the @code{cdr} is the object's value.
3076 A @dfn{hash table} also permits you to index objects with
3077 arbitrary keys, but in a way that makes looking up any one object
3078 extremely fast. A well-designed hash system makes hash table
3079 lookups almost as fast as conventional array or vector references.
3081 Alists are popular among Lisp programmers because they use only
3082 the language's primitive operations (lists, @dfn{car}, @dfn{cdr}
3083 and the equality primitives). No changes to the language core are
3084 necessary. Therefore, with Scheme's built-in list manipulation
3085 facilities, it is very convenient to handle data stored in an
3086 association list. Also, alists are highly portable and can be
3087 easily implemented on even the most minimal Lisp systems.
3089 However, alists are inefficient, especially for storing large
3090 quantities of data. Because we want Guile to be useful for large
3091 software systems as well as small ones, Guile provides a rich set
3092 of tools for using either association lists or hash tables.
3094 @node Association Lists
3095 @subsection Association Lists
3096 @tpindex Association Lists
3098 @cindex association List
3102 An association list is a conventional data structure that is often used
3103 to implement simple key-value databases. It consists of a list of
3104 entries in which each entry is a pair. The @dfn{key} of each entry is
3105 the @code{car} of the pair and the @dfn{value} of each entry is the
3109 ASSOCIATION LIST ::= '( (KEY1 . VALUE1)
3117 Association lists are also known, for short, as @dfn{alists}.
3119 The structure of an association list is just one example of the infinite
3120 number of possible structures that can be built using pairs and lists.
3121 As such, the keys and values in an association list can be manipulated
3122 using the general list structure procedures @code{cons}, @code{car},
3123 @code{cdr}, @code{set-car!}, @code{set-cdr!} and so on. However,
3124 because association lists are so useful, Guile also provides specific
3125 procedures for manipulating them.
3128 * Alist Key Equality::
3129 * Adding or Setting Alist Entries::
3130 * Retrieving Alist Entries::
3131 * Removing Alist Entries::
3132 * Sloppy Alist Functions::
3136 @node Alist Key Equality
3137 @subsubsection Alist Key Equality
3139 All of Guile's dedicated association list procedures, apart from
3140 @code{acons}, come in three flavours, depending on the level of equality
3141 that is required to decide whether an existing key in the association
3142 list is the same as the key that the procedure call uses to identify the
3147 Procedures with @dfn{assq} in their name use @code{eq?} to determine key
3151 Procedures with @dfn{assv} in their name use @code{eqv?} to determine
3155 Procedures with @dfn{assoc} in their name use @code{equal?} to
3156 determine key equality.
3159 @code{acons} is an exception because it is used to build association
3160 lists which do not require their entries' keys to be unique.
3162 @node Adding or Setting Alist Entries
3163 @subsubsection Adding or Setting Alist Entries
3165 @code{acons} adds a new entry to an association list and returns the
3166 combined association list. The combined alist is formed by consing the
3167 new entry onto the head of the alist specified in the @code{acons}
3168 procedure call. So the specified alist is not modified, but its
3169 contents become shared with the tail of the combined alist that
3170 @code{acons} returns.
3172 In the most common usage of @code{acons}, a variable holding the
3173 original association list is updated with the combined alist:
3176 (set! address-list (acons name address address-list))
3179 In such cases, it doesn't matter that the old and new values of
3180 @code{address-list} share some of their contents, since the old value is
3181 usually no longer independently accessible.
3183 Note that @code{acons} adds the specified new entry regardless of
3184 whether the alist may already contain entries with keys that are, in
3185 some sense, the same as that of the new entry. Thus @code{acons} is
3186 ideal for building alists where there is no concept of key uniqueness.
3189 (set! task-list (acons 3 "pay gas bill" '()))
3192 ((3 . "pay gas bill"))
3194 (set! task-list (acons 3 "tidy bedroom" task-list))
3197 ((3 . "tidy bedroom") (3 . "pay gas bill"))
3200 @code{assq-set!}, @code{assv-set!} and @code{assoc-set!} are used to add
3201 or replace an entry in an association list where there @emph{is} a
3202 concept of key uniqueness. If the specified association list already
3203 contains an entry whose key is the same as that specified in the
3204 procedure call, the existing entry is replaced by the new one.
3205 Otherwise, the new entry is consed onto the head of the old association
3206 list to create the combined alist. In all cases, these procedures
3207 return the combined alist.
3209 @code{assq-set!} and friends @emph{may} destructively modify the
3210 structure of the old association list in such a way that an existing
3211 variable is correctly updated without having to @code{set!} it to the
3217 (("mary" . "34 Elm Road") ("james" . "16 Bow Street"))
3219 (assoc-set! address-list "james" "1a London Road")
3221 (("mary" . "34 Elm Road") ("james" . "1a London Road"))
3225 (("mary" . "34 Elm Road") ("james" . "1a London Road"))
3231 (assoc-set! address-list "bob" "11 Newington Avenue")
3233 (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
3234 ("james" . "1a London Road"))
3238 (("mary" . "34 Elm Road") ("james" . "1a London Road"))
3241 The only safe way to update an association list variable when adding or
3242 replacing an entry like this is to @code{set!} the variable to the
3247 (assoc-set! address-list "bob" "11 Newington Avenue"))
3250 (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
3251 ("james" . "1a London Road"))
3254 Because of this slight inconvenience, you may find it more convenient to
3255 use hash tables to store dictionary data. If your application will not
3256 be modifying the contents of an alist very often, this may not make much
3259 If you need to keep the old value of an association list in a form
3260 independent from the list that results from modification by
3261 @code{acons}, @code{assq-set!}, @code{assv-set!} or @code{assoc-set!},
3262 use @code{list-copy} to copy the old association list before modifying
3265 @deffn {Scheme Procedure} acons key value alist
3266 @deffnx {C Function} scm_acons (key, value, alist)
3267 Add a new key-value pair to @var{alist}. A new pair is
3268 created whose car is @var{key} and whose cdr is @var{value}, and the
3269 pair is consed onto @var{alist}, and the new list is returned. This
3270 function is @emph{not} destructive; @var{alist} is not modified.
3273 @deffn {Scheme Procedure} assq-set! alist key val
3274 @deffnx {Scheme Procedure} assv-set! alist key value
3275 @deffnx {Scheme Procedure} assoc-set! alist key value
3276 @deffnx {C Function} scm_assq_set_x (alist, key, val)
3277 @deffnx {C Function} scm_assv_set_x (alist, key, val)
3278 @deffnx {C Function} scm_assoc_set_x (alist, key, val)
3279 Reassociate @var{key} in @var{alist} with @var{value}: find any existing
3280 @var{alist} entry for @var{key} and associate it with the new
3281 @var{value}. If @var{alist} does not contain an entry for @var{key},
3282 add a new one. Return the (possibly new) alist.
3284 These functions do not attempt to verify the structure of @var{alist},
3285 and so may cause unusual results if passed an object that is not an
3289 @node Retrieving Alist Entries
3290 @subsubsection Retrieving Alist Entries
3295 @code{assq}, @code{assv} and @code{assoc} find the entry in an alist
3296 for a given key, and return the @code{(@var{key} . @var{value})} pair.
3297 @code{assq-ref}, @code{assv-ref} and @code{assoc-ref} do a similar
3298 lookup, but return just the @var{value}.
3300 @deffn {Scheme Procedure} assq key alist
3301 @deffnx {Scheme Procedure} assv key alist
3302 @deffnx {Scheme Procedure} assoc key alist
3303 @deffnx {C Function} scm_assq (key, alist)
3304 @deffnx {C Function} scm_assv (key, alist)
3305 @deffnx {C Function} scm_assoc (key, alist)
3306 Return the first entry in @var{alist} with the given @var{key}. The
3307 return is the pair @code{(KEY . VALUE)} from @var{alist}. If there's
3308 no matching entry the return is @code{#f}.
3310 @code{assq} compares keys with @code{eq?}, @code{assv} uses
3311 @code{eqv?} and @code{assoc} uses @code{equal?}. See also SRFI-1
3312 which has an extended @code{assoc} (@ref{SRFI-1 Association Lists}).
3315 @deffn {Scheme Procedure} assq-ref alist key
3316 @deffnx {Scheme Procedure} assv-ref alist key
3317 @deffnx {Scheme Procedure} assoc-ref alist key
3318 @deffnx {C Function} scm_assq_ref (alist, key)
3319 @deffnx {C Function} scm_assv_ref (alist, key)
3320 @deffnx {C Function} scm_assoc_ref (alist, key)
3321 Return the value from the first entry in @var{alist} with the given
3322 @var{key}, or @code{#f} if there's no such entry.
3324 @code{assq-ref} compares keys with @code{eq?}, @code{assv-ref} uses
3325 @code{eqv?} and @code{assoc-ref} uses @code{equal?}.
3327 Notice these functions have the @var{key} argument last, like other
3328 @code{-ref} functions, but this is opposite to what @code{assq}
3331 When the return is @code{#f} it can be either @var{key} not found, or
3332 an entry which happens to have value @code{#f} in the @code{cdr}. Use
3333 @code{assq} etc above if you need to differentiate these cases.
3337 @node Removing Alist Entries
3338 @subsubsection Removing Alist Entries
3340 To remove the element from an association list whose key matches a
3341 specified key, use @code{assq-remove!}, @code{assv-remove!} or
3342 @code{assoc-remove!} (depending, as usual, on the level of equality
3343 required between the key that you specify and the keys in the
3346 As with @code{assq-set!} and friends, the specified alist may or may not
3347 be modified destructively, and the only safe way to update a variable
3348 containing the alist is to @code{set!} it to the value that
3349 @code{assq-remove!} and friends return.
3354 (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
3355 ("james" . "1a London Road"))
3357 (set! address-list (assoc-remove! address-list "mary"))
3360 (("bob" . "11 Newington Avenue") ("james" . "1a London Road"))
3363 Note that, when @code{assq/v/oc-remove!} is used to modify an
3364 association list that has been constructed only using the corresponding
3365 @code{assq/v/oc-set!}, there can be at most one matching entry in the
3366 alist, so the question of multiple entries being removed in one go does
3367 not arise. If @code{assq/v/oc-remove!} is applied to an association
3368 list that has been constructed using @code{acons}, or an
3369 @code{assq/v/oc-set!} with a different level of equality, or any mixture
3370 of these, it removes only the first matching entry from the alist, even
3371 if the alist might contain further matching entries. For example:
3374 (define address-list '())
3375 (set! address-list (assq-set! address-list "mary" "11 Elm Street"))
3376 (set! address-list (assq-set! address-list "mary" "57 Pine Drive"))
3379 (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street"))
3381 (set! address-list (assoc-remove! address-list "mary"))
3384 (("mary" . "11 Elm Street"))
3387 In this example, the two instances of the string "mary" are not the same
3388 when compared using @code{eq?}, so the two @code{assq-set!} calls add
3389 two distinct entries to @code{address-list}. When compared using
3390 @code{equal?}, both "mary"s in @code{address-list} are the same as the
3391 "mary" in the @code{assoc-remove!} call, but @code{assoc-remove!} stops
3392 after removing the first matching entry that it finds, and so one of the
3393 "mary" entries is left in place.
3395 @deffn {Scheme Procedure} assq-remove! alist key
3396 @deffnx {Scheme Procedure} assv-remove! alist key
3397 @deffnx {Scheme Procedure} assoc-remove! alist key
3398 @deffnx {C Function} scm_assq_remove_x (alist, key)
3399 @deffnx {C Function} scm_assv_remove_x (alist, key)
3400 @deffnx {C Function} scm_assoc_remove_x (alist, key)
3401 Delete the first entry in @var{alist} associated with @var{key}, and return
3402 the resulting alist.
3405 @node Sloppy Alist Functions
3406 @subsubsection Sloppy Alist Functions
3408 @code{sloppy-assq}, @code{sloppy-assv} and @code{sloppy-assoc} behave
3409 like the corresponding non-@code{sloppy-} procedures, except that they
3410 return @code{#f} when the specified association list is not well-formed,
3411 where the non-@code{sloppy-} versions would signal an error.
3413 Specifically, there are two conditions for which the non-@code{sloppy-}
3414 procedures signal an error, which the @code{sloppy-} procedures handle
3415 instead by returning @code{#f}. Firstly, if the specified alist as a
3416 whole is not a proper list:
3419 (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
3421 ERROR: In procedure assoc in expression (assoc "mary" (quote #)):
3422 ERROR: Wrong type argument in position 2 (expecting
3423 association list): ((1 . 2) ("key" . "door") . "open sesame")
3425 (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
3431 Secondly, if one of the entries in the specified alist is not a pair:
3434 (assoc 2 '((1 . 1) 2 (3 . 9)))
3436 ERROR: In procedure assoc in expression (assoc 2 (quote #)):
3437 ERROR: Wrong type argument in position 2 (expecting
3438 association list): ((1 . 1) 2 (3 . 9))
3440 (sloppy-assoc 2 '((1 . 1) 2 (3 . 9)))
3445 Unless you are explicitly working with badly formed association lists,
3446 it is much safer to use the non-@code{sloppy-} procedures, because they
3447 help to highlight coding and data errors that the @code{sloppy-}
3448 versions would silently cover up.
3450 @deffn {Scheme Procedure} sloppy-assq key alist
3451 @deffnx {C Function} scm_sloppy_assq (key, alist)
3452 Behaves like @code{assq} but does not do any error checking.
3453 Recommended only for use in Guile internals.
3456 @deffn {Scheme Procedure} sloppy-assv key alist
3457 @deffnx {C Function} scm_sloppy_assv (key, alist)
3458 Behaves like @code{assv} but does not do any error checking.
3459 Recommended only for use in Guile internals.
3462 @deffn {Scheme Procedure} sloppy-assoc key alist
3463 @deffnx {C Function} scm_sloppy_assoc (key, alist)
3464 Behaves like @code{assoc} but does not do any error checking.
3465 Recommended only for use in Guile internals.
3469 @subsubsection Alist Example
3471 Here is a longer example of how alists may be used in practice.
3474 (define capitals '(("New York" . "Albany")
3475 ("Oregon" . "Salem")
3476 ("Florida" . "Miami")))
3478 ;; What's the capital of Oregon?
3479 (assoc "Oregon" capitals) @result{} ("Oregon" . "Salem")
3480 (assoc-ref capitals "Oregon") @result{} "Salem"
3482 ;; We left out South Dakota.
3484 (assoc-set! capitals "South Dakota" "Pierre"))
3486 @result{} (("South Dakota" . "Pierre")
3487 ("New York" . "Albany")
3488 ("Oregon" . "Salem")
3489 ("Florida" . "Miami"))
3491 ;; And we got Florida wrong.
3493 (assoc-set! capitals "Florida" "Tallahassee"))
3495 @result{} (("South Dakota" . "Pierre")
3496 ("New York" . "Albany")
3497 ("Oregon" . "Salem")
3498 ("Florida" . "Tallahassee"))
3500 ;; After Oregon secedes, we can remove it.
3502 (assoc-remove! capitals "Oregon"))
3504 @result{} (("South Dakota" . "Pierre")
3505 ("New York" . "Albany")
3506 ("Florida" . "Tallahassee"))
3510 @subsection VList-Based Hash Lists or ``VHashes''
3512 @cindex VList-based hash lists
3515 The @code{(ice-9 vlist)} module provides an implementation of @dfn{VList-based
3516 hash lists} (@pxref{VLists}). VList-based hash lists, or @dfn{vhashes}, are an
3517 immutable dictionary type similar to association lists that maps @dfn{keys} to
3518 @dfn{values}. However, unlike association lists, accessing a value given its
3519 key is typically a constant-time operation.
3521 The VHash programming interface of @code{(ice-9 vlist)} is mostly the same as
3522 that of association lists found in SRFI-1, with procedure names prefixed by
3523 @code{vhash-} instead of @code{alist-} (@pxref{SRFI-1 Association Lists}).
3525 In addition, vhashes can be manipulated using VList operations:
3528 (vlist-head (vhash-consq 'a 1 vlist-null))
3531 (define vh1 (vhash-consq 'b 2 (vhash-consq 'a 1 vlist-null)))
3532 (define vh2 (vhash-consq 'c 3 (vlist-tail vh1)))
3541 @result{} ((c . 3) (a . 1))
3544 However, keep in mind that procedures that construct new VLists
3545 (@code{vlist-map}, @code{vlist-filter}, etc.) return raw VLists, not vhashes:
3548 (define vh (alist->vhash '((a . 1) (b . 2) (c . 3)) hashq))
3553 ;; This will create a raw vlist.
3554 (vlist-filter (lambda (key+value) (odd? (cdr key+value))) vh))
3556 @result{} ERROR: Wrong type argument in position 2
3559 @result{} ((a . 1) (c . 3))
3562 @deffn {Scheme Procedure} vhash? obj
3563 Return true if @var{obj} is a vhash.
3566 @deffn {Scheme Procedure} vhash-cons key value vhash [hash-proc]
3567 @deffnx {Scheme Procedure} vhash-consq key value vhash
3568 @deffnx {Scheme Procedure} vhash-consv key value vhash
3569 Return a new hash list based on @var{vhash} where @var{key} is associated with
3570 @var{value}, using @var{hash-proc} to compute the hash of @var{key}.
3571 @var{vhash} must be either @code{vlist-null} or a vhash returned by a previous
3572 call to @code{vhash-cons}. @var{hash-proc} defaults to @code{hash} (@pxref{Hash
3573 Table Reference, @code{hash} procedure}). With @code{vhash-consq}, the
3574 @code{hashq} hash function is used; with @code{vhash-consv} the @code{hashv}
3575 hash function is used.
3577 All @code{vhash-cons} calls made to construct a vhash should use the same
3578 @var{hash-proc}. Failing to do that, the result is undefined.
3581 @deffn {Scheme Procedure} vhash-assoc key vhash [equal? [hash-proc]]
3582 @deffnx {Scheme Procedure} vhash-assq key vhash
3583 @deffnx {Scheme Procedure} vhash-assv key vhash
3584 Return the first key/value pair from @var{vhash} whose key is equal to @var{key}
3585 according to the @var{equal?} equality predicate (which defaults to
3586 @code{equal?}), and using @var{hash-proc} (which defaults to @code{hash}) to
3587 compute the hash of @var{key}. The second form uses @code{eq?} as the equality
3588 predicate and @code{hashq} as the hash function; the last form uses @code{eqv?}
3591 Note that it is important to consistently use the same hash function for
3592 @var{hash-proc} as was passed to @code{vhash-cons}. Failing to do that, the
3593 result is unpredictable.
3596 @deffn {Scheme Procedure} vhash-delete key vhash [equal? [hash-proc]]
3597 @deffnx {Scheme Procedure} vhash-delq key vhash
3598 @deffnx {Scheme Procedure} vhash-delv key vhash
3599 Remove all associations from @var{vhash} with @var{key}, comparing keys with
3600 @var{equal?} (which defaults to @code{equal?}), and computing the hash of
3601 @var{key} using @var{hash-proc} (which defaults to @code{hash}). The second
3602 form uses @code{eq?} as the equality predicate and @code{hashq} as the hash
3603 function; the last one uses @code{eqv?} and @code{hashv}.
3605 Again the choice of @var{hash-proc} must be consistent with previous calls to
3609 @deffn {Scheme Procedure} vhash-fold proc init vhash
3610 @deffnx {Scheme Procedure} vhash-fold-right proc init vhash
3611 Fold over the key/value elements of @var{vhash} in the given direction,
3612 with each call to @var{proc} having the form @code{(@var{proc} key value
3613 result)}, where @var{result} is the result of the previous call to
3614 @var{proc} and @var{init} the value of @var{result} for the first call
3618 @deffn {Scheme Procedure} vhash-fold* proc init key vhash [equal? [hash]]
3619 @deffnx {Scheme Procedure} vhash-foldq* proc init key vhash
3620 @deffnx {Scheme Procedure} vhash-foldv* proc init key vhash
3621 Fold over all the values associated with @var{key} in @var{vhash}, with each
3622 call to @var{proc} having the form @code{(proc value result)}, where
3623 @var{result} is the result of the previous call to @var{proc} and @var{init} the
3624 value of @var{result} for the first call to @var{proc}.
3626 Keys in @var{vhash} are hashed using @var{hash} are compared using @var{equal?}.
3627 The second form uses @code{eq?} as the equality predicate and @code{hashq} as
3628 the hash function; the third one uses @code{eqv?} and @code{hashv}.
3634 (alist->vhash '((a . 1) (a . 2) (z . 0) (a . 3))))
3636 (vhash-fold* cons '() 'a vh)
3639 (vhash-fold* cons '() 'z vh)
3644 @deffn {Scheme Procedure} alist->vhash alist [hash-proc]
3645 Return the vhash corresponding to @var{alist}, an association list, using
3646 @var{hash-proc} to compute key hashes. When omitted, @var{hash-proc} defaults
3652 @subsection Hash Tables
3653 @tpindex Hash Tables
3655 Hash tables are dictionaries which offer similar functionality as
3656 association lists: They provide a mapping from keys to values. The
3657 difference is that association lists need time linear in the size of
3658 elements when searching for entries, whereas hash tables can normally
3659 search in constant time. The drawback is that hash tables require a
3660 little bit more memory, and that you can not use the normal list
3661 procedures (@pxref{Lists}) for working with them.
3664 * Hash Table Examples:: Demonstration of hash table usage.
3665 * Hash Table Reference:: Hash table procedure descriptions.
3669 @node Hash Table Examples
3670 @subsubsection Hash Table Examples
3672 For demonstration purposes, this section gives a few usage examples of
3673 some hash table procedures, together with some explanation what they do.
3675 First we start by creating a new hash table with 31 slots, and
3676 populate it with two key/value pairs.
3679 (define h (make-hash-table 31))
3681 ;; This is an opaque object
3686 ;; Inserting into a hash table can be done with hashq-set!
3687 (hashq-set! h 'foo "bar")
3691 (hashq-set! h 'braz "zonk")
3695 ;; Or with hash-create-handle!
3696 (hashq-create-handle! h 'frob #f)
3701 You can get the value for a given key with the procedure
3702 @code{hashq-ref}, but the problem with this procedure is that you
3703 cannot reliably determine whether a key does exists in the table. The
3704 reason is that the procedure returns @code{#f} if the key is not in
3705 the table, but it will return the same value if the key is in the
3706 table and just happens to have the value @code{#f}, as you can see in
3707 the following examples.
3718 (hashq-ref h 'not-there)
3723 Better is to use the procedure @code{hashq-get-handle}, which makes a
3724 distinction between the two cases. Just like @code{assq}, this
3725 procedure returns a key/value-pair on success, and @code{#f} if the
3729 (hashq-get-handle h 'foo)
3733 (hashq-get-handle h 'not-there)
3738 Interesting results can be computed by using @code{hash-fold} to work
3739 through each element. This example will count the total number of
3743 (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h)
3748 The same thing can be done with the procedure @code{hash-count}, which
3749 can also count the number of elements matching a particular predicate.
3750 For example, count the number of elements with string values:
3753 (hash-count (lambda (key value) (string? value)) h)
3758 Counting all the elements is a simple task using @code{const}:
3761 (hash-count (const #t) h)
3766 @node Hash Table Reference
3767 @subsubsection Hash Table Reference
3769 @c FIXME: Describe in broad terms what happens for resizing, and what
3770 @c the initial size means for this.
3772 Like the association list functions, the hash table functions come in
3773 several varieties, according to the equality test used for the keys.
3774 Plain @code{hash-} functions use @code{equal?}, @code{hashq-}
3775 functions use @code{eq?}, @code{hashv-} functions use @code{eqv?}, and
3776 the @code{hashx-} functions use an application supplied test.
3778 A single @code{make-hash-table} creates a hash table suitable for use
3779 with any set of functions, but it's imperative that just one set is
3780 then used consistently, or results will be unpredictable.
3782 Hash tables are implemented as a vector indexed by a hash value formed
3783 from the key, with an association list of key/value pairs for each
3784 bucket in case distinct keys hash together. Direct access to the
3785 pairs in those lists is provided by the @code{-handle-} functions.
3787 When the number of entries in a hash table goes above a threshold, the
3788 vector is made larger and the entries are rehashed, to prevent the
3789 bucket lists from becoming too long and slowing down accesses. When the
3790 number of entries goes below a threshold, the vector is shrunk to save
3793 For the @code{hashx-} ``extended'' routines, an application supplies a
3794 @var{hash} function producing an integer index like @code{hashq} etc
3795 below, and an @var{assoc} alist search function like @code{assq} etc
3796 (@pxref{Retrieving Alist Entries}). Here's an example of such
3797 functions implementing case-insensitive hashing of string keys,
3800 (use-modules (srfi srfi-1)
3803 (define (my-hash str size)
3804 (remainder (string-hash-ci str) size))
3805 (define (my-assoc str alist)
3806 (find (lambda (pair) (string-ci=? str (car pair))) alist))
3808 (define my-table (make-hash-table))
3809 (hashx-set! my-hash my-assoc my-table "foo" 123)
3811 (hashx-ref my-hash my-assoc my-table "FOO")
3815 In a @code{hashx-} @var{hash} function the aim is to spread keys
3816 across the vector, so bucket lists don't become long. But the actual
3817 values are arbitrary as long as they're in the range 0 to
3818 @math{@var{size}-1}. Helpful functions for forming a hash value, in
3819 addition to @code{hashq} etc below, include @code{symbol-hash}
3820 (@pxref{Symbol Keys}), @code{string-hash} and @code{string-hash-ci}
3821 (@pxref{String Comparison}), and @code{char-set-hash}
3822 (@pxref{Character Set Predicates/Comparison}).
3825 @deffn {Scheme Procedure} make-hash-table [size]
3826 Create a new hash table object, with an optional minimum
3829 When @var{size} is given, the table vector will still grow and shrink
3830 automatically, as described above, but with @var{size} as a minimum.
3831 If an application knows roughly how many entries the table will hold
3832 then it can use @var{size} to avoid rehashing when initial entries are
3836 @deffn {Scheme Procedure} hash-table? obj
3837 @deffnx {C Function} scm_hash_table_p (obj)
3838 Return @code{#t} if @var{obj} is a abstract hash table object.
3841 @deffn {Scheme Procedure} hash-clear! table
3842 @deffnx {C Function} scm_hash_clear_x (table)
3843 Remove all items from @var{table} (without triggering a resize).
3846 @deffn {Scheme Procedure} hash-ref table key [dflt]
3847 @deffnx {Scheme Procedure} hashq-ref table key [dflt]
3848 @deffnx {Scheme Procedure} hashv-ref table key [dflt]
3849 @deffnx {Scheme Procedure} hashx-ref hash assoc table key [dflt]
3850 @deffnx {C Function} scm_hash_ref (table, key, dflt)
3851 @deffnx {C Function} scm_hashq_ref (table, key, dflt)
3852 @deffnx {C Function} scm_hashv_ref (table, key, dflt)
3853 @deffnx {C Function} scm_hashx_ref (hash, assoc, table, key, dflt)
3854 Lookup @var{key} in the given hash @var{table}, and return the
3855 associated value. If @var{key} is not found, return @var{dflt}, or
3856 @code{#f} if @var{dflt} is not given.
3859 @deffn {Scheme Procedure} hash-set! table key val
3860 @deffnx {Scheme Procedure} hashq-set! table key val
3861 @deffnx {Scheme Procedure} hashv-set! table key val
3862 @deffnx {Scheme Procedure} hashx-set! hash assoc table key val
3863 @deffnx {C Function} scm_hash_set_x (table, key, val)
3864 @deffnx {C Function} scm_hashq_set_x (table, key, val)
3865 @deffnx {C Function} scm_hashv_set_x (table, key, val)
3866 @deffnx {C Function} scm_hashx_set_x (hash, assoc, table, key, val)
3867 Associate @var{val} with @var{key} in the given hash @var{table}. If
3868 @var{key} is already present then it's associated value is changed.
3869 If it's not present then a new entry is created.
3872 @deffn {Scheme Procedure} hash-remove! table key
3873 @deffnx {Scheme Procedure} hashq-remove! table key
3874 @deffnx {Scheme Procedure} hashv-remove! table key
3875 @deffnx {Scheme Procedure} hashx-remove! hash assoc table key
3876 @deffnx {C Function} scm_hash_remove_x (table, key)
3877 @deffnx {C Function} scm_hashq_remove_x (table, key)
3878 @deffnx {C Function} scm_hashv_remove_x (table, key)
3879 @deffnx {C Function} scm_hashx_remove_x (hash, assoc, table, key)
3880 Remove any association for @var{key} in the given hash @var{table}.
3881 If @var{key} is not in @var{table} then nothing is done.
3884 @deffn {Scheme Procedure} hash key size
3885 @deffnx {Scheme Procedure} hashq key size
3886 @deffnx {Scheme Procedure} hashv key size
3887 @deffnx {C Function} scm_hash (key, size)
3888 @deffnx {C Function} scm_hashq (key, size)
3889 @deffnx {C Function} scm_hashv (key, size)
3890 Return a hash value for @var{key}. This is a number in the range
3891 @math{0} to @math{@var{size}-1}, which is suitable for use in a hash
3892 table of the given @var{size}.
3894 Note that @code{hashq} and @code{hashv} may use internal addresses of
3895 objects, so if an object is garbage collected and re-created it can
3896 have a different hash value, even when the two are notionally
3897 @code{eq?}. For instance with symbols,
3900 (hashq 'something 123) @result{} 19
3902 (hashq 'something 123) @result{} 62
3905 In normal use this is not a problem, since an object entered into a
3906 hash table won't be garbage collected until removed. It's only if
3907 hashing calculations are somehow separated from normal references that
3908 its lifetime needs to be considered.
3911 @deffn {Scheme Procedure} hash-get-handle table key
3912 @deffnx {Scheme Procedure} hashq-get-handle table key
3913 @deffnx {Scheme Procedure} hashv-get-handle table key
3914 @deffnx {Scheme Procedure} hashx-get-handle hash assoc table key
3915 @deffnx {C Function} scm_hash_get_handle (table, key)
3916 @deffnx {C Function} scm_hashq_get_handle (table, key)
3917 @deffnx {C Function} scm_hashv_get_handle (table, key)
3918 @deffnx {C Function} scm_hashx_get_handle (hash, assoc, table, key)
3919 Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
3920 given hash @var{table}, or @code{#f} if @var{key} is not in
3924 @deffn {Scheme Procedure} hash-create-handle! table key init
3925 @deffnx {Scheme Procedure} hashq-create-handle! table key init
3926 @deffnx {Scheme Procedure} hashv-create-handle! table key init
3927 @deffnx {Scheme Procedure} hashx-create-handle! hash assoc table key init
3928 @deffnx {C Function} scm_hash_create_handle_x (table, key, init)
3929 @deffnx {C Function} scm_hashq_create_handle_x (table, key, init)
3930 @deffnx {C Function} scm_hashv_create_handle_x (table, key, init)
3931 @deffnx {C Function} scm_hashx_create_handle_x (hash, assoc, table, key, init)
3932 Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
3933 given hash @var{table}. If @var{key} is not in @var{table} then
3934 create an entry for it with @var{init} as the value, and return that
3938 @deffn {Scheme Procedure} hash-map->list proc table
3939 @deffnx {Scheme Procedure} hash-for-each proc table
3940 @deffnx {C Function} scm_hash_map_to_list (proc, table)
3941 @deffnx {C Function} scm_hash_for_each (proc, table)
3942 Apply @var{proc} to the entries in the given hash @var{table}. Each
3943 call is @code{(@var{proc} @var{key} @var{value})}. @code{hash-map->list}
3944 returns a list of the results from these calls, @code{hash-for-each}
3945 discards the results and returns an unspecified value.
3947 Calls are made over the table entries in an unspecified order, and for
3948 @code{hash-map->list} the order of the values in the returned list is
3949 unspecified. Results will be unpredictable if @var{table} is modified
3952 For example the following returns a new alist comprising all the
3953 entries from @code{mytable}, in no particular order.
3956 (hash-map->list cons mytable)
3960 @deffn {Scheme Procedure} hash-for-each-handle proc table
3961 @deffnx {C Function} scm_hash_for_each_handle (proc, table)
3962 Apply @var{proc} to the entries in the given hash @var{table}. Each
3963 call is @code{(@var{proc} @var{handle})}, where @var{handle} is a
3964 @code{(@var{key} . @var{value})} pair. Return an unspecified value.
3966 @code{hash-for-each-handle} differs from @code{hash-for-each} only in
3967 the argument list of @var{proc}.
3970 @deffn {Scheme Procedure} hash-fold proc init table
3971 @deffnx {C Function} scm_hash_fold (proc, init, table)
3972 Accumulate a result by applying @var{proc} to the elements of the
3973 given hash @var{table}. Each call is @code{(@var{proc} @var{key}
3974 @var{value} @var{prior-result})}, where @var{key} and @var{value} are
3975 from the @var{table} and @var{prior-result} is the return from the
3976 previous @var{proc} call. For the first call, @var{prior-result} is
3977 the given @var{init} value.
3979 Calls are made over the table entries in an unspecified order.
3980 Results will be unpredictable if @var{table} is modified while
3981 @code{hash-fold} is running.
3983 For example, the following returns a count of how many keys in
3984 @code{mytable} are strings.
3987 (hash-fold (lambda (key value prior)
3988 (if (string? key) (1+ prior) prior))
3993 @deffn {Scheme Procedure} hash-count pred table
3994 @deffnx {C Function} scm_hash_count (pred, table)
3995 Return the number of elements in the given hash @var{table} that cause
3996 @code{(@var{pred} @var{key} @var{value})} to return true. To quickly
3997 determine the total number of elements, use @code{(const #t)} for
4002 @c TeX-master: "guile.texi"