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 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 * Generalized Vectors:: Treating all vector-like things uniformly.
26 * Arrays:: Matrices, etc.
27 * VLists:: Vector-like lists.
30 * Dictionary Types:: About dictionary types in general.
31 * Association Lists:: List-based dictionaries.
32 * VHashes:: VList-based dictionaries.
33 * Hash Tables:: Table-based dictionaries.
41 Pairs are used to combine two Scheme objects into one compound object.
42 Hence the name: A pair stores a pair of objects.
44 The data type @dfn{pair} is extremely important in Scheme, just like in
45 any other Lisp dialect. The reason is that pairs are not only used to
46 make two values available as one object, but that pairs are used for
47 constructing lists of values. Because lists are so important in Scheme,
48 they are described in a section of their own (@pxref{Lists}).
50 Pairs can literally get entered in source code or at the REPL, in the
51 so-called @dfn{dotted list} syntax. This syntax consists of an opening
52 parentheses, the first element of the pair, a dot, the second element
53 and a closing parentheses. The following example shows how a pair
54 consisting of the two numbers 1 and 2, and a pair containing the symbols
55 @code{foo} and @code{bar} can be entered. It is very important to write
56 the whitespace before and after the dot, because otherwise the Scheme
57 parser would not be able to figure out where to split the tokens.
64 But beware, if you want to try out these examples, you have to
65 @dfn{quote} the expressions. More information about quotation is
66 available in the section @ref{Expression Syntax}. The correct way
67 to try these examples is as follows.
78 A new pair is made by calling the procedure @code{cons} with two
79 arguments. Then the argument values are stored into a newly allocated
80 pair, and the pair is returned. The name @code{cons} stands for
81 "construct". Use the procedure @code{pair?} to test whether a
82 given Scheme object is a pair or not.
85 @deffn {Scheme Procedure} cons x y
86 @deffnx {C Function} scm_cons (x, y)
87 Return a newly allocated pair whose car is @var{x} and whose
88 cdr is @var{y}. The pair is guaranteed to be different (in the
89 sense of @code{eq?}) from every previously existing object.
93 @deffn {Scheme Procedure} pair? x
94 @deffnx {C Function} scm_pair_p (x)
95 Return @code{#t} if @var{x} is a pair; otherwise return
99 @deftypefn {C Function} int scm_is_pair (SCM x)
100 Return 1 when @var{x} is a pair; otherwise return 0.
103 The two parts of a pair are traditionally called @dfn{car} and
104 @dfn{cdr}. They can be retrieved with procedures of the same name
105 (@code{car} and @code{cdr}), and can be modified with the procedures
106 @code{set-car!} and @code{set-cdr!}. Since a very common operation in
107 Scheme programs is to access the car of a car of a pair, or the car of
108 the cdr of a pair, etc., the procedures called @code{caar},
109 @code{cadr} and so on are also predefined.
113 @deffn {Scheme Procedure} car pair
114 @deffnx {Scheme Procedure} cdr pair
115 @deffnx {C Function} scm_car (pair)
116 @deffnx {C Function} scm_cdr (pair)
117 Return the car or the cdr of @var{pair}, respectively.
120 @deftypefn {C Macro} SCM SCM_CAR (SCM pair)
121 @deftypefnx {C Macro} SCM SCM_CDR (SCM pair)
122 These two macros are the fastest way to access the car or cdr of a
123 pair; they can be thought of as compiling into a single memory
126 These macros do no checking at all. The argument @var{pair} must be a
130 @deffn {Scheme Procedure} cddr pair
131 @deffnx {Scheme Procedure} cdar pair
132 @deffnx {Scheme Procedure} cadr pair
133 @deffnx {Scheme Procedure} caar pair
134 @deffnx {Scheme Procedure} cdddr pair
135 @deffnx {Scheme Procedure} cddar pair
136 @deffnx {Scheme Procedure} cdadr pair
137 @deffnx {Scheme Procedure} cdaar pair
138 @deffnx {Scheme Procedure} caddr pair
139 @deffnx {Scheme Procedure} cadar pair
140 @deffnx {Scheme Procedure} caadr pair
141 @deffnx {Scheme Procedure} caaar pair
142 @deffnx {Scheme Procedure} cddddr pair
143 @deffnx {Scheme Procedure} cdddar pair
144 @deffnx {Scheme Procedure} cddadr pair
145 @deffnx {Scheme Procedure} cddaar pair
146 @deffnx {Scheme Procedure} cdaddr pair
147 @deffnx {Scheme Procedure} cdadar pair
148 @deffnx {Scheme Procedure} cdaadr pair
149 @deffnx {Scheme Procedure} cdaaar pair
150 @deffnx {Scheme Procedure} cadddr pair
151 @deffnx {Scheme Procedure} caddar pair
152 @deffnx {Scheme Procedure} cadadr pair
153 @deffnx {Scheme Procedure} cadaar pair
154 @deffnx {Scheme Procedure} caaddr pair
155 @deffnx {Scheme Procedure} caadar pair
156 @deffnx {Scheme Procedure} caaadr pair
157 @deffnx {Scheme Procedure} caaaar pair
158 @deffnx {C Function} scm_cddr (pair)
159 @deffnx {C Function} scm_cdar (pair)
160 @deffnx {C Function} scm_cadr (pair)
161 @deffnx {C Function} scm_caar (pair)
162 @deffnx {C Function} scm_cdddr (pair)
163 @deffnx {C Function} scm_cddar (pair)
164 @deffnx {C Function} scm_cdadr (pair)
165 @deffnx {C Function} scm_cdaar (pair)
166 @deffnx {C Function} scm_caddr (pair)
167 @deffnx {C Function} scm_cadar (pair)
168 @deffnx {C Function} scm_caadr (pair)
169 @deffnx {C Function} scm_caaar (pair)
170 @deffnx {C Function} scm_cddddr (pair)
171 @deffnx {C Function} scm_cdddar (pair)
172 @deffnx {C Function} scm_cddadr (pair)
173 @deffnx {C Function} scm_cddaar (pair)
174 @deffnx {C Function} scm_cdaddr (pair)
175 @deffnx {C Function} scm_cdadar (pair)
176 @deffnx {C Function} scm_cdaadr (pair)
177 @deffnx {C Function} scm_cdaaar (pair)
178 @deffnx {C Function} scm_cadddr (pair)
179 @deffnx {C Function} scm_caddar (pair)
180 @deffnx {C Function} scm_cadadr (pair)
181 @deffnx {C Function} scm_cadaar (pair)
182 @deffnx {C Function} scm_caaddr (pair)
183 @deffnx {C Function} scm_caadar (pair)
184 @deffnx {C Function} scm_caaadr (pair)
185 @deffnx {C Function} scm_caaaar (pair)
186 These procedures are compositions of @code{car} and @code{cdr}, where
187 for example @code{caddr} could be defined by
190 (define caddr (lambda (x) (car (cdr (cdr x)))))
193 @code{cadr}, @code{caddr} and @code{cadddr} pick out the second, third
194 or fourth elements of a list, respectively. SRFI-1 provides the same
195 under the names @code{second}, @code{third} and @code{fourth}
196 (@pxref{SRFI-1 Selectors}).
200 @deffn {Scheme Procedure} set-car! pair value
201 @deffnx {C Function} scm_set_car_x (pair, value)
202 Stores @var{value} in the car field of @var{pair}. The value returned
203 by @code{set-car!} is unspecified.
207 @deffn {Scheme Procedure} set-cdr! pair value
208 @deffnx {C Function} scm_set_cdr_x (pair, value)
209 Stores @var{value} in the cdr field of @var{pair}. The value returned
210 by @code{set-cdr!} is unspecified.
218 A very important data type in Scheme---as well as in all other Lisp
219 dialects---is the data type @dfn{list}.@footnote{Strictly speaking,
220 Scheme does not have a real datatype @dfn{list}. Lists are made up of
221 @dfn{chained pairs}, and only exist by definition---a list is a chain
222 of pairs which looks like a list.}
224 This is the short definition of what a list is:
228 Either the empty list @code{()},
231 or a pair which has a list in its cdr.
234 @c FIXME::martin: Describe the pair chaining in more detail.
236 @c FIXME::martin: What is a proper, what an improper list?
237 @c What is a circular list?
239 @c FIXME::martin: Maybe steal some graphics from the Elisp reference
243 * List Syntax:: Writing literal lists.
244 * List Predicates:: Testing lists.
245 * List Constructors:: Creating new lists.
246 * List Selection:: Selecting from lists, getting their length.
247 * Append/Reverse:: Appending and reversing lists.
248 * List Modification:: Modifying existing lists.
249 * List Searching:: Searching for list elements
250 * List Mapping:: Applying procedures to lists.
254 @subsubsection List Read Syntax
256 The syntax for lists is an opening parentheses, then all the elements of
257 the list (separated by whitespace) and finally a closing
258 parentheses.@footnote{Note that there is no separation character between
259 the list elements, like a comma or a semicolon.}.
262 (1 2 3) ; @r{a list of the numbers 1, 2 and 3}
263 ("foo" bar 3.1415) ; @r{a string, a symbol and a real number}
264 () ; @r{the empty list}
267 The last example needs a bit more explanation. A list with no elements,
268 called the @dfn{empty list}, is special in some ways. It is used for
269 terminating lists by storing it into the cdr of the last pair that makes
270 up a list. An example will clear that up:
281 This example also shows that lists have to be quoted when written
282 (@pxref{Expression Syntax}), because they would otherwise be
283 mistakingly taken as procedure applications (@pxref{Simple
287 @node List Predicates
288 @subsubsection List Predicates
290 Often it is useful to test whether a given Scheme object is a list or
291 not. List-processing procedures could use this information to test
292 whether their input is valid, or they could do different things
293 depending on the datatype of their arguments.
296 @deffn {Scheme Procedure} list? x
297 @deffnx {C Function} scm_list_p (x)
298 Return @code{#t} iff @var{x} is a proper list, else @code{#f}.
301 The predicate @code{null?} is often used in list-processing code to
302 tell whether a given list has run out of elements. That is, a loop
303 somehow deals with the elements of a list until the list satisfies
304 @code{null?}. Then, the algorithm terminates.
307 @deffn {Scheme Procedure} null? x
308 @deffnx {C Function} scm_null_p (x)
309 Return @code{#t} iff @var{x} is the empty list, else @code{#f}.
312 @deftypefn {C Function} int scm_is_null (SCM x)
313 Return 1 when @var{x} is the empty list; otherwise return 0.
317 @node List Constructors
318 @subsubsection List Constructors
320 This section describes the procedures for constructing new lists.
321 @code{list} simply returns a list where the elements are the arguments,
322 @code{cons*} is similar, but the last argument is stored in the cdr of
323 the last pair of the list.
325 @c C Function scm_list(rest) used to be documented here, but it's a
326 @c no-op since it does nothing but return the list the caller must
327 @c have already created.
329 @deffn {Scheme Procedure} list elem1 @dots{} elemN
330 @deffnx {C Function} scm_list_1 (elem1)
331 @deffnx {C Function} scm_list_2 (elem1, elem2)
332 @deffnx {C Function} scm_list_3 (elem1, elem2, elem3)
333 @deffnx {C Function} scm_list_4 (elem1, elem2, elem3, elem4)
334 @deffnx {C Function} scm_list_5 (elem1, elem2, elem3, elem4, elem5)
335 @deffnx {C Function} scm_list_n (elem1, @dots{}, elemN, @nicode{SCM_UNDEFINED})
337 Return a new list containing elements @var{elem1} to @var{elemN}.
339 @code{scm_list_n} takes a variable number of arguments, terminated by
340 the special @code{SCM_UNDEFINED}. That final @code{SCM_UNDEFINED} is
341 not included in the list. None of @var{elem1} to @var{elemN} can
342 themselves be @code{SCM_UNDEFINED}, or @code{scm_list_n} will
343 terminate at that point.
346 @c C Function scm_cons_star(arg1,rest) used to be documented here,
347 @c but it's not really a useful interface, since it expects the
348 @c caller to have already consed up all but the first argument
351 @deffn {Scheme Procedure} cons* arg1 arg2 @dots{}
352 Like @code{list}, but the last arg provides the tail of the
353 constructed list, returning @code{(cons @var{arg1} (cons
354 @var{arg2} (cons @dots{} @var{argn})))}. Requires at least one
355 argument. If given one argument, that argument is returned as
356 result. This function is called @code{list*} in some other
357 Schemes and in Common LISP.
360 @deffn {Scheme Procedure} list-copy lst
361 @deffnx {C Function} scm_list_copy (lst)
362 Return a (newly-created) copy of @var{lst}.
365 @deffn {Scheme Procedure} make-list n [init]
366 Create a list containing of @var{n} elements, where each element is
367 initialized to @var{init}. @var{init} defaults to the empty list
368 @code{()} if not given.
371 Note that @code{list-copy} only makes a copy of the pairs which make up
372 the spine of the lists. The list elements are not copied, which means
373 that modifying the elements of the new list also modifies the elements
374 of the old list. On the other hand, applying procedures like
375 @code{set-cdr!} or @code{delv!} to the new list will not alter the old
376 list. If you also need to copy the list elements (making a deep copy),
377 use the procedure @code{copy-tree} (@pxref{Copying}).
380 @subsubsection List Selection
382 These procedures are used to get some information about a list, or to
383 retrieve one or more elements of a list.
386 @deffn {Scheme Procedure} length lst
387 @deffnx {C Function} scm_length (lst)
388 Return the number of elements in list @var{lst}.
391 @deffn {Scheme Procedure} last-pair lst
392 @deffnx {C Function} scm_last_pair (lst)
393 Return the last pair in @var{lst}, signalling an error if
394 @var{lst} is circular.
398 @deffn {Scheme Procedure} list-ref list k
399 @deffnx {C Function} scm_list_ref (list, k)
400 Return the @var{k}th element from @var{list}.
404 @deffn {Scheme Procedure} list-tail lst k
405 @deffnx {Scheme Procedure} list-cdr-ref lst k
406 @deffnx {C Function} scm_list_tail (lst, k)
407 Return the "tail" of @var{lst} beginning with its @var{k}th element.
408 The first element of the list is considered to be element 0.
410 @code{list-tail} and @code{list-cdr-ref} are identical. It may help to
411 think of @code{list-cdr-ref} as accessing the @var{k}th cdr of the list,
412 or returning the results of cdring @var{k} times down @var{lst}.
415 @deffn {Scheme Procedure} list-head lst k
416 @deffnx {C Function} scm_list_head (lst, k)
417 Copy the first @var{k} elements from @var{lst} into a new list, and
422 @subsubsection Append and Reverse
424 @code{append} and @code{append!} are used to concatenate two or more
425 lists in order to form a new list. @code{reverse} and @code{reverse!}
426 return lists with the same elements as their arguments, but in reverse
427 order. The procedure variants with an @code{!} directly modify the
428 pairs which form the list, whereas the other procedures create new
429 pairs. This is why you should be careful when using the side-effecting
433 @deffn {Scheme Procedure} append lst1 @dots{} lstN
434 @deffnx {Scheme Procedure} append! lst1 @dots{} lstN
435 @deffnx {C Function} scm_append (lstlst)
436 @deffnx {C Function} scm_append_x (lstlst)
437 Return a list comprising all the elements of lists @var{lst1} to
441 (append '(x) '(y)) @result{} (x y)
442 (append '(a) '(b c d)) @result{} (a b c d)
443 (append '(a (b)) '((c))) @result{} (a (b) (c))
446 The last argument @var{lstN} may actually be any object; an improper
447 list results if the last argument is not a proper list.
450 (append '(a b) '(c . d)) @result{} (a b c . d)
451 (append '() 'a) @result{} a
454 @code{append} doesn't modify the given lists, but the return may share
455 structure with the final @var{lstN}. @code{append!} modifies the
456 given lists to form its return.
458 For @code{scm_append} and @code{scm_append_x}, @var{lstlst} is a list
459 of the list operands @var{lst1} @dots{} @var{lstN}. That @var{lstlst}
460 itself is not modified or used in the return.
464 @deffn {Scheme Procedure} reverse lst
465 @deffnx {Scheme Procedure} reverse! lst [newtail]
466 @deffnx {C Function} scm_reverse (lst)
467 @deffnx {C Function} scm_reverse_x (lst, newtail)
468 Return a list comprising the elements of @var{lst}, in reverse order.
470 @code{reverse} constructs a new list, @code{reverse!} modifies
471 @var{lst} in constructing its return.
473 For @code{reverse!}, the optional @var{newtail} is appended to the
474 result. @var{newtail} isn't reversed, it simply becomes the list
475 tail. For @code{scm_reverse_x}, the @var{newtail} parameter is
476 mandatory, but can be @code{SCM_EOL} if no further tail is required.
479 @node List Modification
480 @subsubsection List Modification
482 The following procedures modify an existing list, either by changing
483 elements of the list, or by changing the list structure itself.
485 @deffn {Scheme Procedure} list-set! list k val
486 @deffnx {C Function} scm_list_set_x (list, k, val)
487 Set the @var{k}th element of @var{list} to @var{val}.
490 @deffn {Scheme Procedure} list-cdr-set! list k val
491 @deffnx {C Function} scm_list_cdr_set_x (list, k, val)
492 Set the @var{k}th cdr of @var{list} to @var{val}.
495 @deffn {Scheme Procedure} delq item lst
496 @deffnx {C Function} scm_delq (item, lst)
497 Return a newly-created copy of @var{lst} with elements
498 @code{eq?} to @var{item} removed. This procedure mirrors
499 @code{memq}: @code{delq} compares elements of @var{lst} against
500 @var{item} with @code{eq?}.
503 @deffn {Scheme Procedure} delv item lst
504 @deffnx {C Function} scm_delv (item, lst)
505 Return a newly-created copy of @var{lst} with elements
506 @code{eqv?} to @var{item} removed. This procedure mirrors
507 @code{memv}: @code{delv} compares elements of @var{lst} against
508 @var{item} with @code{eqv?}.
511 @deffn {Scheme Procedure} delete item lst
512 @deffnx {C Function} scm_delete (item, lst)
513 Return a newly-created copy of @var{lst} with elements
514 @code{equal?} to @var{item} removed. This procedure mirrors
515 @code{member}: @code{delete} compares elements of @var{lst}
516 against @var{item} with @code{equal?}.
518 See also SRFI-1 which has an extended @code{delete} (@ref{SRFI-1
519 Deleting}), and also an @code{lset-difference} which can delete
520 multiple @var{item}s in one call (@ref{SRFI-1 Set Operations}).
523 @deffn {Scheme Procedure} delq! item lst
524 @deffnx {Scheme Procedure} delv! item lst
525 @deffnx {Scheme Procedure} delete! item lst
526 @deffnx {C Function} scm_delq_x (item, lst)
527 @deffnx {C Function} scm_delv_x (item, lst)
528 @deffnx {C Function} scm_delete_x (item, lst)
529 These procedures are destructive versions of @code{delq}, @code{delv}
530 and @code{delete}: they modify the pointers in the existing @var{lst}
531 rather than creating a new list. Caveat evaluator: Like other
532 destructive list functions, these functions cannot modify the binding of
533 @var{lst}, and so cannot be used to delete the first element of
534 @var{lst} destructively.
537 @deffn {Scheme Procedure} delq1! item lst
538 @deffnx {C Function} scm_delq1_x (item, lst)
539 Like @code{delq!}, but only deletes the first occurrence of
540 @var{item} from @var{lst}. Tests for equality using
541 @code{eq?}. See also @code{delv1!} and @code{delete1!}.
544 @deffn {Scheme Procedure} delv1! item lst
545 @deffnx {C Function} scm_delv1_x (item, lst)
546 Like @code{delv!}, but only deletes the first occurrence of
547 @var{item} from @var{lst}. Tests for equality using
548 @code{eqv?}. See also @code{delq1!} and @code{delete1!}.
551 @deffn {Scheme Procedure} delete1! item lst
552 @deffnx {C Function} scm_delete1_x (item, lst)
553 Like @code{delete!}, but only deletes the first occurrence of
554 @var{item} from @var{lst}. Tests for equality using
555 @code{equal?}. See also @code{delq1!} and @code{delv1!}.
558 @deffn {Scheme Procedure} filter pred lst
559 @deffnx {Scheme Procedure} filter! pred lst
560 Return a list containing all elements from @var{lst} which satisfy the
561 predicate @var{pred}. The elements in the result list have the same
562 order as in @var{lst}. The order in which @var{pred} is applied to
563 the list elements is not specified.
565 @code{filter} does not change @var{lst}, but the result may share a
566 tail with it. @code{filter!} may modify @var{lst} to construct its
571 @subsubsection List Searching
573 The following procedures search lists for particular elements. They use
574 different comparison predicates for comparing list elements with the
575 object to be searched. When they fail, they return @code{#f}, otherwise
576 they return the sublist whose car is equal to the search object, where
577 equality depends on the equality predicate used.
580 @deffn {Scheme Procedure} memq x lst
581 @deffnx {C Function} scm_memq (x, lst)
582 Return the first sublist of @var{lst} whose car is @code{eq?}
583 to @var{x} where the sublists of @var{lst} are the non-empty
584 lists returned by @code{(list-tail @var{lst} @var{k})} for
585 @var{k} less than the length of @var{lst}. If @var{x} does not
586 occur in @var{lst}, then @code{#f} (not the empty list) is
591 @deffn {Scheme Procedure} memv x lst
592 @deffnx {C Function} scm_memv (x, lst)
593 Return the first sublist of @var{lst} whose car is @code{eqv?}
594 to @var{x} where the sublists of @var{lst} are the non-empty
595 lists returned by @code{(list-tail @var{lst} @var{k})} for
596 @var{k} less than the length of @var{lst}. If @var{x} does not
597 occur in @var{lst}, then @code{#f} (not the empty list) is
602 @deffn {Scheme Procedure} member x lst
603 @deffnx {C Function} scm_member (x, lst)
604 Return the first sublist of @var{lst} whose car is
605 @code{equal?} to @var{x} where the sublists of @var{lst} are
606 the non-empty lists returned by @code{(list-tail @var{lst}
607 @var{k})} for @var{k} less than the length of @var{lst}. If
608 @var{x} does not occur in @var{lst}, then @code{#f} (not the
609 empty list) is returned.
611 See also SRFI-1 which has an extended @code{member} function
612 (@ref{SRFI-1 Searching}).
617 @subsubsection List Mapping
619 List processing is very convenient in Scheme because the process of
620 iterating over the elements of a list can be highly abstracted. The
621 procedures in this section are the most basic iterating procedures for
622 lists. They take a procedure and one or more lists as arguments, and
623 apply the procedure to each element of the list. They differ in their
627 @c begin (texi-doc-string "guile" "map")
628 @deffn {Scheme Procedure} map proc arg1 arg2 @dots{}
629 @deffnx {Scheme Procedure} map-in-order proc arg1 arg2 @dots{}
630 @deffnx {C Function} scm_map (proc, arg1, args)
631 Apply @var{proc} to each element of the list @var{arg1} (if only two
632 arguments are given), or to the corresponding elements of the argument
633 lists (if more than two arguments are given). The result(s) of the
634 procedure applications are saved and returned in a list. For
635 @code{map}, the order of procedure applications is not specified,
636 @code{map-in-order} applies the procedure from left to right to the list
641 @c begin (texi-doc-string "guile" "for-each")
642 @deffn {Scheme Procedure} for-each proc arg1 arg2 @dots{}
643 Like @code{map}, but the procedure is always applied from left to right,
644 and the result(s) of the procedure applications are thrown away. The
645 return value is not specified.
648 See also SRFI-1 which extends these functions to take lists of unequal
649 lengths (@ref{SRFI-1 Fold and Map}).
655 Vectors are sequences of Scheme objects. Unlike lists, the length of a
656 vector, once the vector is created, cannot be changed. The advantage of
657 vectors over lists is that the time required to access one element of a vector
658 given its @dfn{position} (synonymous with @dfn{index}), a zero-origin number,
659 is constant, whereas lists have an access time linear to the position of the
660 accessed element in the list.
662 Vectors can contain any kind of Scheme object; it is even possible to
663 have different types of objects in the same vector. For vectors
664 containing vectors, you may wish to use arrays, instead. Note, too,
665 that vectors are the special case of one dimensional non-uniform arrays
666 and that most array procedures operate happily on vectors
670 * Vector Syntax:: Read syntax for vectors.
671 * Vector Creation:: Dynamic vector creation and validation.
672 * Vector Accessors:: Accessing and modifying vector contents.
673 * Vector Accessing from C:: Ways to work with vectors from C.
674 * Uniform Numeric Vectors:: Vectors of unboxed numeric values.
679 @subsubsection Read Syntax for Vectors
681 Vectors can literally be entered in source code, just like strings,
682 characters or some of the other data types. The read syntax for vectors
683 is as follows: A sharp sign (@code{#}), followed by an opening
684 parentheses, all elements of the vector in their respective read syntax,
685 and finally a closing parentheses. The following are examples of the
686 read syntax for vectors; where the first vector only contains numbers
687 and the second three different object types: a string, a symbol and a
688 number in hexadecimal notation.
692 #("Hello" foo #xdeadbeef)
695 Like lists, vectors have to be quoted:
698 '#(a b c) @result{} #(a b c)
701 @node Vector Creation
702 @subsubsection Dynamic Vector Creation and Validation
704 Instead of creating a vector implicitly by using the read syntax just
705 described, you can create a vector dynamically by calling one of the
706 @code{vector} and @code{list->vector} primitives with the list of Scheme
707 values that you want to place into a vector. The size of the vector
708 thus created is determined implicitly by the number of arguments given.
711 @rnindex list->vector
712 @deffn {Scheme Procedure} vector . l
713 @deffnx {Scheme Procedure} list->vector l
714 @deffnx {C Function} scm_vector (l)
715 Return a newly allocated vector composed of the
716 given arguments. Analogous to @code{list}.
719 (vector 'a 'b 'c) @result{} #(a b c)
723 The inverse operation is @code{vector->list}:
725 @rnindex vector->list
726 @deffn {Scheme Procedure} vector->list v
727 @deffnx {C Function} scm_vector_to_list (v)
728 Return a newly allocated list composed of the elements of @var{v}.
731 (vector->list '#(dah dah didah)) @result{} (dah dah didah)
732 (list->vector '(dididit dah)) @result{} #(dididit dah)
736 To allocate a vector with an explicitly specified size, use
737 @code{make-vector}. With this primitive you can also specify an initial
738 value for the vector elements (the same value for all elements, that
742 @deffn {Scheme Procedure} make-vector len [fill]
743 @deffnx {C Function} scm_make_vector (len, fill)
744 Return a newly allocated vector of @var{len} elements. If a
745 second argument is given, then each position is initialized to
746 @var{fill}. Otherwise the initial contents of each position is
750 @deftypefn {C Function} SCM scm_c_make_vector (size_t k, SCM fill)
751 Like @code{scm_make_vector}, but the length is given as a @code{size_t}.
754 To check whether an arbitrary Scheme value @emph{is} a vector, use the
755 @code{vector?} primitive:
758 @deffn {Scheme Procedure} vector? obj
759 @deffnx {C Function} scm_vector_p (obj)
760 Return @code{#t} if @var{obj} is a vector, otherwise return
764 @deftypefn {C Function} int scm_is_vector (SCM obj)
765 Return non-zero when @var{obj} is a vector, otherwise return
769 @node Vector Accessors
770 @subsubsection Accessing and Modifying Vector Contents
772 @code{vector-length} and @code{vector-ref} return information about a
773 given vector, respectively its size and the elements that are contained
776 @rnindex vector-length
777 @deffn {Scheme Procedure} vector-length vector
778 @deffnx {C Function} scm_vector_length vector
779 Return the number of elements in @var{vector} as an exact integer.
782 @deftypefn {C Function} size_t scm_c_vector_length (SCM v)
783 Return the number of elements in @var{vector} as a @code{size_t}.
787 @deffn {Scheme Procedure} vector-ref vector k
788 @deffnx {C Function} scm_vector_ref vector k
789 Return the contents of position @var{k} of @var{vector}.
790 @var{k} must be a valid index of @var{vector}.
792 (vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8
793 (vector-ref '#(1 1 2 3 5 8 13 21)
794 (let ((i (round (* 2 (acos -1)))))
801 @deftypefn {C Function} SCM scm_c_vector_ref (SCM v, size_t k)
802 Return the contents of position @var{k} (a @code{size_t}) of
806 A vector created by one of the dynamic vector constructor procedures
807 (@pxref{Vector Creation}) can be modified using the following
810 @emph{NOTE:} According to R5RS, it is an error to use any of these
811 procedures on a literally read vector, because such vectors should be
812 considered as constants. Currently, however, Guile does not detect this
816 @deffn {Scheme Procedure} vector-set! vector k obj
817 @deffnx {C Function} scm_vector_set_x vector k obj
818 Store @var{obj} in position @var{k} of @var{vector}.
819 @var{k} must be a valid index of @var{vector}.
820 The value returned by @samp{vector-set!} is unspecified.
822 (let ((vec (vector 0 '(2 2 2 2) "Anna")))
823 (vector-set! vec 1 '("Sue" "Sue"))
824 vec) @result{} #(0 ("Sue" "Sue") "Anna")
828 @deftypefn {C Function} void scm_c_vector_set_x (SCM v, size_t k, SCM obj)
829 Store @var{obj} in position @var{k} (a @code{size_t}) of @var{v}.
832 @rnindex vector-fill!
833 @deffn {Scheme Procedure} vector-fill! v fill
834 @deffnx {C Function} scm_vector_fill_x (v, fill)
835 Store @var{fill} in every position of @var{vector}. The value
836 returned by @code{vector-fill!} is unspecified.
839 @deffn {Scheme Procedure} vector-copy vec
840 @deffnx {C Function} scm_vector_copy (vec)
841 Return a copy of @var{vec}.
844 @deffn {Scheme Procedure} vector-move-left! vec1 start1 end1 vec2 start2
845 @deffnx {C Function} scm_vector_move_left_x (vec1, start1, end1, vec2, start2)
846 Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
847 to @var{vec2} starting at position @var{start2}. @var{start1} and
848 @var{start2} are inclusive indices; @var{end1} is exclusive.
850 @code{vector-move-left!} copies elements in leftmost order.
851 Therefore, in the case where @var{vec1} and @var{vec2} refer to the
852 same vector, @code{vector-move-left!} is usually appropriate when
853 @var{start1} is greater than @var{start2}.
856 @deffn {Scheme Procedure} vector-move-right! vec1 start1 end1 vec2 start2
857 @deffnx {C Function} scm_vector_move_right_x (vec1, start1, end1, vec2, start2)
858 Copy elements from @var{vec1}, positions @var{start1} to @var{end1},
859 to @var{vec2} starting at position @var{start2}. @var{start1} and
860 @var{start2} are inclusive indices; @var{end1} is exclusive.
862 @code{vector-move-right!} copies elements in rightmost order.
863 Therefore, in the case where @var{vec1} and @var{vec2} refer to the
864 same vector, @code{vector-move-right!} is usually appropriate when
865 @var{start1} is less than @var{start2}.
868 @node Vector Accessing from C
869 @subsubsection Vector Accessing from C
871 A vector can be read and modified from C with the functions
872 @code{scm_c_vector_ref} and @code{scm_c_vector_set_x}, for example. In
873 addition to these functions, there are two more ways to access vectors
874 from C that might be more efficient in certain situations: you can
875 restrict yourself to @dfn{simple vectors} and then use the very fast
876 @emph{simple vector macros}; or you can use the very general framework
877 for accessing all kinds of arrays (@pxref{Accessing Arrays from C}),
878 which is more verbose, but can deal efficiently with all kinds of
879 vectors (and arrays). For vectors, you can use the
880 @code{scm_vector_elements} and @code{scm_vector_writable_elements}
881 functions as shortcuts.
883 @deftypefn {C Function} int scm_is_simple_vector (SCM obj)
884 Return non-zero if @var{obj} is a simple vector, else return zero. A
885 simple vector is a vector that can be used with the @code{SCM_SIMPLE_*}
888 The following functions are guaranteed to return simple vectors:
889 @code{scm_make_vector}, @code{scm_c_make_vector}, @code{scm_vector},
890 @code{scm_list_to_vector}.
893 @deftypefn {C Macro} size_t SCM_SIMPLE_VECTOR_LENGTH (SCM vec)
894 Evaluates to the length of the simple vector @var{vec}. No type
898 @deftypefn {C Macro} SCM SCM_SIMPLE_VECTOR_REF (SCM vec, size_t idx)
899 Evaluates to the element at position @var{idx} in the simple vector
900 @var{vec}. No type or range checking is done.
903 @deftypefn {C Macro} void SCM_SIMPLE_VECTOR_SET (SCM vec, size_t idx, SCM val)
904 Sets the element at position @var{idx} in the simple vector
905 @var{vec} to @var{val}. No type or range checking is done.
908 @deftypefn {C Function} {const SCM *} scm_vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
909 Acquire a handle for the vector @var{vec} and return a pointer to the
910 elements of it. This pointer can only be used to read the elements of
911 @var{vec}. When @var{vec} is not a vector, an error is signaled. The
912 handle must eventually be released with
913 @code{scm_array_handle_release}.
915 The variables pointed to by @var{lenp} and @var{incp} are filled with
916 the number of elements of the vector and the increment (number of
917 elements) between successive elements, respectively. Successive
918 elements of @var{vec} need not be contiguous in their underlying
919 ``root vector'' returned here; hence the increment is not necessarily
920 equal to 1 and may well be negative too (@pxref{Shared Arrays}).
922 The following example shows the typical way to use this function. It
923 creates a list of all elements of @var{vec} (in reverse order).
926 scm_t_array_handle handle;
932 elt = scm_vector_elements (vec, &handle, &len, &inc);
934 for (i = 0; i < len; i++, elt += inc)
935 list = scm_cons (*elt, list);
936 scm_array_handle_release (&handle);
941 @deftypefn {C Function} {SCM *} scm_vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
942 Like @code{scm_vector_elements} but the pointer can be used to modify
945 The following example shows the typical way to use this function. It
946 fills a vector with @code{#t}.
949 scm_t_array_handle handle;
954 elt = scm_vector_writable_elements (vec, &handle, &len, &inc);
955 for (i = 0; i < len; i++, elt += inc)
957 scm_array_handle_release (&handle);
962 @node Uniform Numeric Vectors
963 @subsubsection Uniform Numeric Vectors
965 A uniform numeric vector is a vector whose elements are all of a single
966 numeric type. Guile offers uniform numeric vectors for signed and
967 unsigned 8-bit, 16-bit, 32-bit, and 64-bit integers, two sizes of
968 floating point values, and complex floating-point numbers of these two
969 sizes. @xref{SRFI-4}, for more information.
971 For many purposes, bytevectors work just as well as uniform vectors, and have
972 the advantage that they integrate well with binary input and output.
973 @xref{Bytevectors}, for more information on bytevectors.
976 @subsection Bit Vectors
979 Bit vectors are zero-origin, one-dimensional arrays of booleans. They
980 are displayed as a sequence of @code{0}s and @code{1}s prefixed by
984 (make-bitvector 8 #f) @result{}
988 Bit vectors are also generalized vectors, @xref{Generalized
989 Vectors}, and can thus be used with the array procedures, @xref{Arrays}.
990 Bit vectors are the special case of one dimensional bit arrays.
992 @deffn {Scheme Procedure} bitvector? obj
993 @deffnx {C Function} scm_bitvector_p (obj)
994 Return @code{#t} when @var{obj} is a bitvector, else
998 @deftypefn {C Function} int scm_is_bitvector (SCM obj)
999 Return @code{1} when @var{obj} is a bitvector, else return @code{0}.
1002 @deffn {Scheme Procedure} make-bitvector len [fill]
1003 @deffnx {C Function} scm_make_bitvector (len, fill)
1004 Create a new bitvector of length @var{len} and
1005 optionally initialize all elements to @var{fill}.
1008 @deftypefn {C Function} SCM scm_c_make_bitvector (size_t len, SCM fill)
1009 Like @code{scm_make_bitvector}, but the length is given as a
1013 @deffn {Scheme Procedure} bitvector . bits
1014 @deffnx {C Function} scm_bitvector (bits)
1015 Create a new bitvector with the arguments as elements.
1018 @deffn {Scheme Procedure} bitvector-length vec
1019 @deffnx {C Function} scm_bitvector_length (vec)
1020 Return the length of the bitvector @var{vec}.
1023 @deftypefn {C Function} size_t scm_c_bitvector_length (SCM vec)
1024 Like @code{scm_bitvector_length}, but the length is returned as a
1028 @deffn {Scheme Procedure} bitvector-ref vec idx
1029 @deffnx {C Function} scm_bitvector_ref (vec, idx)
1030 Return the element at index @var{idx} of the bitvector
1034 @deftypefn {C Function} SCM scm_c_bitvector_ref (SCM obj, size_t idx)
1035 Return the element at index @var{idx} of the bitvector
1039 @deffn {Scheme Procedure} bitvector-set! vec idx val
1040 @deffnx {C Function} scm_bitvector_set_x (vec, idx, val)
1041 Set the element at index @var{idx} of the bitvector
1042 @var{vec} when @var{val} is true, else clear it.
1045 @deftypefn {C Function} SCM scm_c_bitvector_set_x (SCM obj, size_t idx, SCM val)
1046 Set the element at index @var{idx} of the bitvector
1047 @var{vec} when @var{val} is true, else clear it.
1050 @deffn {Scheme Procedure} bitvector-fill! vec val
1051 @deffnx {C Function} scm_bitvector_fill_x (vec, val)
1052 Set all elements of the bitvector
1053 @var{vec} when @var{val} is true, else clear them.
1056 @deffn {Scheme Procedure} list->bitvector list
1057 @deffnx {C Function} scm_list_to_bitvector (list)
1058 Return a new bitvector initialized with the elements
1062 @deffn {Scheme Procedure} bitvector->list vec
1063 @deffnx {C Function} scm_bitvector_to_list (vec)
1064 Return a new list initialized with the elements
1065 of the bitvector @var{vec}.
1068 @deffn {Scheme Procedure} bit-count bool bitvector
1069 @deffnx {C Function} scm_bit_count (bool, bitvector)
1070 Return a count of how many entries in @var{bitvector} are equal to
1071 @var{bool}. For example,
1074 (bit-count #f #*000111000) @result{} 6
1078 @deffn {Scheme Procedure} bit-position bool bitvector start
1079 @deffnx {C Function} scm_bit_position (bool, bitvector, start)
1080 Return the index of the first occurrence of @var{bool} in
1081 @var{bitvector}, starting from @var{start}. If there is no @var{bool}
1082 entry between @var{start} and the end of @var{bitvector}, then return
1083 @code{#f}. For example,
1086 (bit-position #t #*000101 0) @result{} 3
1087 (bit-position #f #*0001111 3) @result{} #f
1091 @deffn {Scheme Procedure} bit-invert! bitvector
1092 @deffnx {C Function} scm_bit_invert_x (bitvector)
1093 Modify @var{bitvector} by replacing each element with its negation.
1096 @deffn {Scheme Procedure} bit-set*! bitvector uvec bool
1097 @deffnx {C Function} scm_bit_set_star_x (bitvector, uvec, bool)
1098 Set entries of @var{bitvector} to @var{bool}, with @var{uvec}
1099 selecting the entries to change. The return value is unspecified.
1101 If @var{uvec} is a bit vector, then those entries where it has
1102 @code{#t} are the ones in @var{bitvector} which are set to @var{bool}.
1103 @var{uvec} and @var{bitvector} must be the same length. When
1104 @var{bool} is @code{#t} it's like @var{uvec} is OR'ed into
1105 @var{bitvector}. Or when @var{bool} is @code{#f} it can be seen as an
1109 (define bv #*01000010)
1110 (bit-set*! bv #*10010001 #t)
1112 @result{} #*11010011
1115 If @var{uvec} is a uniform vector of unsigned long integers, then
1116 they're indexes into @var{bitvector} which are set to @var{bool}.
1119 (define bv #*01000010)
1120 (bit-set*! bv #u(5 2 7) #t)
1122 @result{} #*01100111
1126 @deffn {Scheme Procedure} bit-count* bitvector uvec bool
1127 @deffnx {C Function} scm_bit_count_star (bitvector, uvec, bool)
1128 Return a count of how many entries in @var{bitvector} are equal to
1129 @var{bool}, with @var{uvec} selecting the entries to consider.
1131 @var{uvec} is interpreted in the same way as for @code{bit-set*!}
1132 above. Namely, if @var{uvec} is a bit vector then entries which have
1133 @code{#t} there are considered in @var{bitvector}. Or if @var{uvec}
1134 is a uniform vector of unsigned long integers then it's the indexes in
1135 @var{bitvector} to consider.
1140 (bit-count* #*01110111 #*11001101 #t) @result{} 3
1141 (bit-count* #*01110111 #u(7 0 4) #f) @result{} 2
1145 @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)
1146 Like @code{scm_vector_elements} (@pxref{Vector Accessing from C}), but
1147 for bitvectors. The variable pointed to by @var{offp} is set to the
1148 value returned by @code{scm_array_handle_bit_elements_offset}. See
1149 @code{scm_array_handle_bit_elements} for how to use the returned
1150 pointer and the offset.
1153 @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)
1154 Like @code{scm_bitvector_elements}, but the pointer is good for reading
1158 @node Generalized Vectors
1159 @subsection Generalized Vectors
1161 Guile has a number of data types that are generally vector-like:
1162 strings, uniform numeric vectors, bytevectors, bitvectors, and of course
1163 ordinary vectors of arbitrary Scheme values. These types are disjoint:
1164 a Scheme value belongs to at most one of the five types listed above.
1166 If you want to gloss over this distinction and want to treat all four
1167 types with common code, you can use the procedures in this section.
1168 They work with the @emph{generalized vector} type, which is the union
1169 of the five vector-like types.
1171 @deffn {Scheme Procedure} generalized-vector? obj
1172 @deffnx {C Function} scm_generalized_vector_p (obj)
1173 Return @code{#t} if @var{obj} is a vector, bytevector, string,
1174 bitvector, or uniform numeric vector.
1177 @deffn {Scheme Procedure} generalized-vector-length v
1178 @deffnx {C Function} scm_generalized_vector_length (v)
1179 Return the length of the generalized vector @var{v}.
1182 @deffn {Scheme Procedure} generalized-vector-ref v idx
1183 @deffnx {C Function} scm_generalized_vector_ref (v, idx)
1184 Return the element at index @var{idx} of the
1185 generalized vector @var{v}.
1188 @deffn {Scheme Procedure} generalized-vector-set! v idx val
1189 @deffnx {C Function} scm_generalized_vector_set_x (v, idx, val)
1190 Set the element at index @var{idx} of the
1191 generalized vector @var{v} to @var{val}.
1194 @deffn {Scheme Procedure} generalized-vector->list v
1195 @deffnx {C Function} scm_generalized_vector_to_list (v)
1196 Return a new list whose elements are the elements of the
1197 generalized vector @var{v}.
1200 @deftypefn {C Function} int scm_is_generalized_vector (SCM obj)
1201 Return @code{1} if @var{obj} is a vector, string,
1202 bitvector, or uniform numeric vector; else return @code{0}.
1205 @deftypefn {C Function} size_t scm_c_generalized_vector_length (SCM v)
1206 Return the length of the generalized vector @var{v}.
1209 @deftypefn {C Function} SCM scm_c_generalized_vector_ref (SCM v, size_t idx)
1210 Return the element at index @var{idx} of the generalized vector @var{v}.
1213 @deftypefn {C Function} void scm_c_generalized_vector_set_x (SCM v, size_t idx, SCM val)
1214 Set the element at index @var{idx} of the generalized vector @var{v}
1218 @deftypefn {C Function} void scm_generalized_vector_get_handle (SCM v, scm_t_array_handle *handle)
1219 Like @code{scm_array_get_handle} but an error is signalled when @var{v}
1220 is not of rank one. You can use @code{scm_array_handle_ref} and
1221 @code{scm_array_handle_set} to read and write the elements of @var{v},
1222 or you can use functions like @code{scm_array_handle_<foo>_elements} to
1223 deal with specific types of vectors.
1230 @dfn{Arrays} are a collection of cells organized into an arbitrary
1231 number of dimensions. Each cell can be accessed in constant time by
1232 supplying an index for each dimension.
1234 In the current implementation, an array uses a generalized vector for
1235 the actual storage of its elements. Any kind of generalized vector
1236 will do, so you can have arrays of uniform numeric values, arrays of
1237 characters, arrays of bits, and of course, arrays of arbitrary Scheme
1238 values. For example, arrays with an underlying @code{c64vector} might
1239 be nice for digital signal processing, while arrays made from a
1240 @code{u8vector} might be used to hold gray-scale images.
1242 The number of dimensions of an array is called its @dfn{rank}. Thus,
1243 a matrix is an array of rank 2, while a vector has rank 1. When
1244 accessing an array element, you have to specify one exact integer for
1245 each dimension. These integers are called the @dfn{indices} of the
1246 element. An array specifies the allowed range of indices for each
1247 dimension via an inclusive lower and upper bound. These bounds can
1248 well be negative, but the upper bound must be greater than or equal to
1249 the lower bound minus one. When all lower bounds of an array are
1250 zero, it is called a @dfn{zero-origin} array.
1252 Arrays can be of rank 0, which could be interpreted as a scalar.
1253 Thus, a zero-rank array can store exactly one object and the list of
1254 indices of this element is the empty list.
1256 Arrays contain zero elements when one of their dimensions has a zero
1257 length. These empty arrays maintain information about their shape: a
1258 matrix with zero columns and 3 rows is different from a matrix with 3
1259 columns and zero rows, which again is different from a vector of
1262 Generalized vectors, such as strings, uniform numeric vectors,
1263 bytevectors, bit vectors and ordinary vectors, are the special case of
1264 one dimensional arrays.
1268 * Array Procedures::
1270 * Accessing Arrays from C::
1274 @subsubsection Array Syntax
1276 An array is displayed as @code{#} followed by its rank, followed by a
1277 tag that describes the underlying vector, optionally followed by
1278 information about its shape, and finally followed by the cells,
1279 organized into dimensions using parentheses.
1281 In more words, the array tag is of the form
1284 #<rank><vectag><@@lower><:len><@@lower><:len>...
1287 where @code{<rank>} is a positive integer in decimal giving the rank of
1288 the array. It is omitted when the rank is 1 and the array is non-shared
1289 and has zero-origin (see below). For shared arrays and for a non-zero
1290 origin, the rank is always printed even when it is 1 to distinguish
1291 them from ordinary vectors.
1293 The @code{<vectag>} part is the tag for a uniform numeric vector, like
1294 @code{u8}, @code{s16}, etc, @code{b} for bitvectors, or @code{a} for
1295 strings. It is empty for ordinary vectors.
1297 The @code{<@@lower>} part is a @samp{@@} character followed by a signed
1298 integer in decimal giving the lower bound of a dimension. There is one
1299 @code{<@@lower>} for each dimension. When all lower bounds are zero,
1300 all @code{<@@lower>} parts are omitted.
1302 The @code{<:len>} part is a @samp{:} character followed by an unsigned
1303 integer in decimal giving the length of a dimension. Like for the lower
1304 bounds, there is one @code{<:len>} for each dimension, and the
1305 @code{<:len>} part always follows the @code{<@@lower>} part for a
1306 dimension. Lengths are only then printed when they can't be deduced
1307 from the nested lists of elements of the array literal, which can happen
1308 when at least one length is zero.
1310 As a special case, an array of rank 0 is printed as
1311 @code{#0<vectag>(<scalar>)}, where @code{<scalar>} is the result of
1312 printing the single element of the array.
1318 is an ordinary array of rank 1 with lower bound 0 in dimension 0.
1319 (I.e., a regular vector.)
1322 is an ordinary array of rank 1 with lower bound 2 in dimension 0.
1324 @item #2((1 2 3) (4 5 6))
1325 is a non-uniform array of rank 2; a 3@cross{}3 matrix with index ranges 0..2
1329 is a uniform u8 array of rank 1.
1331 @item #2u32@@2@@3((1 2) (2 3))
1332 is a uniform u8 array of rank 2 with index ranges 2..3 and 3..4.
1335 is a two-dimensional array with index ranges 0..-1 and 0..-1, i.e.@:
1336 both dimensions have length zero.
1339 is a two-dimensional array with index ranges 0..-1 and 0..1, i.e.@: the
1340 first dimension has length zero, but the second has length 2.
1343 is a rank-zero array with contents 12.
1347 In addition, bytevectors are also arrays, but use a different syntax
1348 (@pxref{Bytevectors}):
1353 is a 3-byte long bytevector, with contents 1, 2, 3.
1357 @node Array Procedures
1358 @subsubsection Array Procedures
1360 When an array is created, the range of each dimension must be
1361 specified, e.g., to create a 2@cross{}3 array with a zero-based index:
1364 (make-array 'ho 2 3) @result{} #2((ho ho ho) (ho ho ho))
1367 The range of each dimension can also be given explicitly, e.g., another
1368 way to create the same array:
1371 (make-array 'ho '(0 1) '(0 2)) @result{} #2((ho ho ho) (ho ho ho))
1374 The following procedures can be used with arrays (or vectors). An
1375 argument shown as @var{idx}@dots{} means one parameter for each
1376 dimension in the array. A @var{idxlist} argument means a list of such
1377 values, one for each dimension.
1380 @deffn {Scheme Procedure} array? obj
1381 @deffnx {C Function} scm_array_p (obj, unused)
1382 Return @code{#t} if the @var{obj} is an array, and @code{#f} if
1385 The second argument to scm_array_p is there for historical reasons,
1386 but it is not used. You should always pass @code{SCM_UNDEFINED} as
1390 @deffn {Scheme Procedure} typed-array? obj type
1391 @deffnx {C Function} scm_typed_array_p (obj, type)
1392 Return @code{#t} if the @var{obj} is an array of type @var{type}, and
1396 @deftypefn {C Function} int scm_is_array (SCM obj)
1397 Return @code{1} if the @var{obj} is an array and @code{0} if not.
1400 @deftypefn {C Function} int scm_is_typed_array (SCM obj, SCM type)
1401 Return @code{0} if the @var{obj} is an array of type @var{type}, and
1405 @deffn {Scheme Procedure} make-array fill bound @dots{}
1406 @deffnx {C Function} scm_make_array (fill, bounds)
1407 Equivalent to @code{(make-typed-array #t @var{fill} @var{bound} ...)}.
1410 @deffn {Scheme Procedure} make-typed-array type fill bound @dots{}
1411 @deffnx {C Function} scm_make_typed_array (type, fill, bounds)
1412 Create and return an array that has as many dimensions as there are
1413 @var{bound}s and (maybe) fill it with @var{fill}.
1415 The underlying storage vector is created according to @var{type},
1416 which must be a symbol whose name is the `vectag' of the array as
1417 explained above, or @code{#t} for ordinary, non-specialized arrays.
1419 For example, using the symbol @code{f64} for @var{type} will create an
1420 array that uses a @code{f64vector} for storing its elements, and
1421 @code{a} will use a string.
1423 When @var{fill} is not the special @emph{unspecified} value, the new
1424 array is filled with @var{fill}. Otherwise, the initial contents of
1425 the array is unspecified. The special @emph{unspecified} value is
1426 stored in the variable @code{*unspecified*} so that for example
1427 @code{(make-typed-array 'u32 *unspecified* 4)} creates a uninitialized
1428 @code{u32} vector of length 4.
1430 Each @var{bound} may be a positive non-zero integer @var{N}, in which
1431 case the index for that dimension can range from 0 through @var{N-1}; or
1432 an explicit index range specifier in the form @code{(LOWER UPPER)},
1433 where both @var{lower} and @var{upper} are integers, possibly less than
1434 zero, and possibly the same number (however, @var{lower} cannot be
1435 greater than @var{upper}).
1438 @deffn {Scheme Procedure} list->array dimspec list
1439 Equivalent to @code{(list->typed-array #t @var{dimspec}
1443 @deffn {Scheme Procedure} list->typed-array type dimspec list
1444 @deffnx {C Function} scm_list_to_typed_array (type, dimspec, list)
1445 Return an array of the type indicated by @var{type} with elements the
1446 same as those of @var{list}.
1448 The argument @var{dimspec} determines the number of dimensions of the
1449 array and their lower bounds. When @var{dimspec} is an exact integer,
1450 it gives the number of dimensions directly and all lower bounds are
1451 zero. When it is a list of exact integers, then each element is the
1452 lower index bound of a dimension, and there will be as many dimensions
1453 as elements in the list.
1456 @deffn {Scheme Procedure} array-type array
1457 Return the type of @var{array}. This is the `vectag' used for
1458 printing @var{array} (or @code{#t} for ordinary arrays) and can be
1459 used with @code{make-typed-array} to create an array of the same kind
1463 @deffn {Scheme Procedure} array-ref array idx @dots{}
1464 Return the element at @code{(idx @dots{})} in @var{array}.
1467 (define a (make-array 999 '(1 2) '(3 4)))
1468 (array-ref a 2 4) @result{} 999
1472 @deffn {Scheme Procedure} array-in-bounds? array idx @dots{}
1473 @deffnx {C Function} scm_array_in_bounds_p (array, idxlist)
1474 Return @code{#t} if the given index would be acceptable to
1478 (define a (make-array #f '(1 2) '(3 4)))
1479 (array-in-bounds? a 2 3) @result{} #t
1480 (array-in-bounds? a 0 0) @result{} #f
1484 @deffn {Scheme Procedure} array-set! array obj idx @dots{}
1485 @deffnx {C Function} scm_array_set_x (array, obj, idxlist)
1486 Set the element at @code{(idx @dots{})} in @var{array} to @var{obj}.
1487 The return value is unspecified.
1490 (define a (make-array #f '(0 1) '(0 1)))
1491 (array-set! a #t 1 1)
1492 a @result{} #2((#f #f) (#f #t))
1496 @deffn {Scheme Procedure} array-shape array
1497 @deffnx {Scheme Procedure} array-dimensions array
1498 @deffnx {C Function} scm_array_dimensions (array)
1499 Return a list of the bounds for each dimension of @var{array}.
1501 @code{array-shape} gives @code{(@var{lower} @var{upper})} for each
1502 dimension. @code{array-dimensions} instead returns just
1503 @math{@var{upper}+1} for dimensions with a 0 lower bound. Both are
1504 suitable as input to @code{make-array}.
1509 (define a (make-array 'foo '(-1 3) 5))
1510 (array-shape a) @result{} ((-1 3) (0 4))
1511 (array-dimensions a) @result{} ((-1 3) 5)
1515 @deffn {Scheme Procedure} array-rank obj
1516 @deffnx {C Function} scm_array_rank (obj)
1517 Return the rank of @var{array}.
1520 @deftypefn {C Function} size_t scm_c_array_rank (SCM array)
1521 Return the rank of @var{array} as a @code{size_t}.
1524 @deffn {Scheme Procedure} array->list array
1525 @deffnx {C Function} scm_array_to_list (array)
1526 Return a list consisting of all the elements, in order, of
1530 @c FIXME: Describe how the order affects the copying (it matters for
1531 @c shared arrays with the same underlying root vector, presumably).
1533 @deffn {Scheme Procedure} array-copy! src dst
1534 @deffnx {Scheme Procedure} array-copy-in-order! src dst
1535 @deffnx {C Function} scm_array_copy_x (src, dst)
1536 Copy every element from vector or array @var{src} to the corresponding
1537 element of @var{dst}. @var{dst} must have the same rank as @var{src},
1538 and be at least as large in each dimension. The return value is
1542 @deffn {Scheme Procedure} array-fill! array fill
1543 @deffnx {C Function} scm_array_fill_x (array, fill)
1544 Store @var{fill} in every element of @var{array}. The value returned
1548 @c begin (texi-doc-string "guile" "array-equal?")
1549 @deffn {Scheme Procedure} array-equal? array1 array2 @dots{}
1550 Return @code{#t} if all arguments are arrays with the same shape, the
1551 same type, and have corresponding elements which are either
1552 @code{equal?} or @code{array-equal?}. This function differs from
1553 @code{equal?} (@pxref{Equality}) in that all arguments must be arrays.
1556 @c FIXME: array-map! accepts no source arrays at all, and in that
1557 @c case makes calls "(proc)". Is that meant to be a documented
1560 @c FIXME: array-for-each doesn't say what happens if the sources have
1561 @c different index ranges. The code currently iterates over the
1562 @c indices of the first and expects the others to cover those. That
1563 @c at least vaguely matches array-map!, but is it meant to be a
1564 @c documented feature?
1566 @deffn {Scheme Procedure} array-map! dst proc src1 @dots{} srcN
1567 @deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
1568 @deffnx {C Function} scm_array_map_x (dst, proc, srclist)
1569 Set each element of the @var{dst} array to values obtained from calls
1570 to @var{proc}. The value returned is unspecified.
1572 Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})},
1573 where each @var{elem} is from the corresponding @var{src} array, at
1574 the @var{dst} index. @code{array-map-in-order!} makes the calls in
1575 row-major order, @code{array-map!} makes them in an unspecified order.
1577 The @var{src} arrays must have the same number of dimensions as
1578 @var{dst}, and must have a range for each dimension which covers the
1579 range in @var{dst}. This ensures all @var{dst} indices are valid in
1583 @deffn {Scheme Procedure} array-for-each proc src1 @dots{} srcN
1584 @deffnx {C Function} scm_array_for_each (proc, src1, srclist)
1585 Apply @var{proc} to each tuple of elements of @var{src1} @dots{}
1586 @var{srcN}, in row-major order. The value returned is unspecified.
1589 @deffn {Scheme Procedure} array-index-map! dst proc
1590 @deffnx {C Function} scm_array_index_map_x (dst, proc)
1591 Set each element of the @var{dst} array to values returned by calls to
1592 @var{proc}. The value returned is unspecified.
1594 Each call is @code{(@var{proc} @var{i1} @dots{} @var{iN})}, where
1595 @var{i1}@dots{}@var{iN} is the destination index, one parameter for
1596 each dimension. The order in which the calls are made is unspecified.
1598 For example, to create a @m{4\times4, 4x4} matrix representing a
1602 \advance\leftskip by 2\lispnarrowing {
1620 (define a (make-array #f 4 4))
1621 (array-index-map! a (lambda (i j)
1622 (modulo (+ i j) 4)))
1626 @deffn {Scheme Procedure} uniform-array-read! ra [port_or_fd [start [end]]]
1627 @deffnx {C Function} scm_uniform_array_read_x (ra, port_or_fd, start, end)
1628 Attempt to read all elements of @var{ura}, in lexicographic order, as
1629 binary objects from @var{port-or-fdes}.
1630 If an end of file is encountered,
1631 the objects up to that point are put into @var{ura}
1632 (starting at the beginning) and the remainder of the array is
1635 The optional arguments @var{start} and @var{end} allow
1636 a specified region of a vector (or linearized array) to be read,
1637 leaving the remainder of the vector unchanged.
1639 @code{uniform-array-read!} returns the number of objects read.
1640 @var{port-or-fdes} may be omitted, in which case it defaults to the value
1641 returned by @code{(current-input-port)}.
1644 @deffn {Scheme Procedure} uniform-array-write v [port_or_fd [start [end]]]
1645 @deffnx {C Function} scm_uniform_array_write (v, port_or_fd, start, end)
1646 Writes all elements of @var{ura} as binary objects to
1649 The optional arguments @var{start}
1651 a specified region of a vector (or linearized array) to be written.
1653 The number of objects actually written is returned.
1654 @var{port-or-fdes} may be
1655 omitted, in which case it defaults to the value returned by
1656 @code{(current-output-port)}.
1660 @subsubsection Shared Arrays
1662 @deffn {Scheme Procedure} make-shared-array oldarray mapfunc bound @dots{}
1663 @deffnx {C Function} scm_make_shared_array (oldarray, mapfunc, boundlist)
1664 Return a new array which shares the storage of @var{oldarray}.
1665 Changes made through either affect the same underlying storage. The
1666 @var{bound@dots{}} arguments are the shape of the new array, the same
1667 as @code{make-array} (@pxref{Array Procedures}).
1669 @var{mapfunc} translates coordinates from the new array to the
1670 @var{oldarray}. It's called as @code{(@var{mapfunc} newidx1 @dots{})}
1671 with one parameter for each dimension of the new array, and should
1672 return a list of indices for @var{oldarray}, one for each dimension of
1675 @var{mapfunc} must be affine linear, meaning that each @var{oldarray}
1676 index must be formed by adding integer multiples (possibly negative)
1677 of some or all of @var{newidx1} etc, plus a possible integer offset.
1678 The multiples and offset must be the same in each call.
1681 One good use for a shared array is to restrict the range of some
1682 dimensions, so as to apply say @code{array-for-each} or
1683 @code{array-fill!} to only part of an array. The plain @code{list}
1684 function can be used for @var{mapfunc} in this case, making no changes
1685 to the index values. For example,
1688 (make-shared-array #2((a b c) (d e f) (g h i)) list 3 2)
1689 @result{} #2((a b) (d e) (g h))
1692 The new array can have fewer dimensions than @var{oldarray}, for
1693 example to take a column from an array.
1696 (make-shared-array #2((a b c) (d e f) (g h i))
1697 (lambda (i) (list i 2))
1702 A diagonal can be taken by using the single new array index for both
1703 row and column in the old array. For example,
1706 (make-shared-array #2((a b c) (d e f) (g h i))
1707 (lambda (i) (list i i))
1712 Dimensions can be increased by for instance considering portions of a
1713 one dimensional array as rows in a two dimensional array.
1714 (@code{array-contents} below can do the opposite, flattening an
1718 (make-shared-array #1(a b c d e f g h i j k l)
1719 (lambda (i j) (list (+ (* i 3) j)))
1721 @result{} #2((a b c) (d e f) (g h i) (j k l))
1724 By negating an index the order that elements appear can be reversed.
1725 The following just reverses the column order,
1728 (make-shared-array #2((a b c) (d e f) (g h i))
1729 (lambda (i j) (list i (- 2 j)))
1731 @result{} #2((c b a) (f e d) (i h g))
1734 A fixed offset on indexes allows for instance a change from a 0 based
1738 (define x #2((a b c) (d e f) (g h i)))
1739 (define y (make-shared-array x
1740 (lambda (i j) (list (1- i) (1- j)))
1742 (array-ref x 0 0) @result{} a
1743 (array-ref y 1 1) @result{} a
1746 A multiple on an index allows every Nth element of an array to be
1747 taken. The following is every third element,
1750 (make-shared-array #1(a b c d e f g h i j k l)
1751 (lambda (i) (list (* i 3)))
1753 @result{} #1(a d g j)
1756 The above examples can be combined to make weird and wonderful
1757 selections from an array, but it's important to note that because
1758 @var{mapfunc} must be affine linear, arbitrary permutations are not
1761 In the current implementation, @var{mapfunc} is not called for every
1762 access to the new array but only on some sample points to establish a
1763 base and stride for new array indices in @var{oldarray} data. A few
1764 sample points are enough because @var{mapfunc} is linear.
1767 @deffn {Scheme Procedure} shared-array-increments array
1768 @deffnx {C Function} scm_shared_array_increments (array)
1769 For each dimension, return the distance between elements in the root vector.
1772 @deffn {Scheme Procedure} shared-array-offset array
1773 @deffnx {C Function} scm_shared_array_offset (array)
1774 Return the root vector index of the first element in the array.
1777 @deffn {Scheme Procedure} shared-array-root array
1778 @deffnx {C Function} scm_shared_array_root (array)
1779 Return the root vector of a shared array.
1782 @deffn {Scheme Procedure} array-contents array [strict]
1783 @deffnx {C Function} scm_array_contents (array, strict)
1784 If @var{array} may be @dfn{unrolled} into a one dimensional shared array
1785 without changing their order (last subscript changing fastest), then
1786 @code{array-contents} returns that shared array, otherwise it returns
1787 @code{#f}. All arrays made by @code{make-array} and
1788 @code{make-typed-array} may be unrolled, some arrays made by
1789 @code{make-shared-array} may not be.
1791 If the optional argument @var{strict} is provided, a shared array will
1792 be returned only if its elements are stored internally contiguous in
1796 @deffn {Scheme Procedure} transpose-array array dim1 @dots{}
1797 @deffnx {C Function} scm_transpose_array (array, dimlist)
1798 Return an array sharing contents with @var{array}, but with
1799 dimensions arranged in a different order. There must be one
1800 @var{dim} argument for each dimension of @var{array}.
1801 @var{dim1}, @var{dim2}, @dots{} should be integers between 0
1802 and the rank of the array to be returned. Each integer in that
1803 range must appear at least once in the argument list.
1805 The values of @var{dim1}, @var{dim2}, @dots{} correspond to
1806 dimensions in the array to be returned, and their positions in the
1807 argument list to dimensions of @var{array}. Several @var{dim}s
1808 may have the same value, in which case the returned array will
1809 have smaller rank than @var{array}.
1812 (transpose-array '#2((a b) (c d)) 1 0) @result{} #2((a c) (b d))
1813 (transpose-array '#2((a b) (c d)) 0 0) @result{} #1(a d)
1814 (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) @result{}
1815 #2((a 4) (b 5) (c 6))
1819 @node Accessing Arrays from C
1820 @subsubsection Accessing Arrays from C
1822 For interworking with external C code, Guile provides an API to allow C
1823 code to access the elements of a Scheme array. In particular, for
1824 uniform numeric arrays, the API exposes the underlying uniform data as a
1825 C array of numbers of the relevant type.
1827 While pointers to the elements of an array are in use, the array itself
1828 must be protected so that the pointer remains valid. Such a protected
1829 array is said to be @dfn{reserved}. A reserved array can be read but
1830 modifications to it that would cause the pointer to its elements to
1831 become invalid are prevented. When you attempt such a modification, an
1834 (This is similar to locking the array while it is in use, but without
1835 the danger of a deadlock. In a multi-threaded program, you will need
1836 additional synchronization to avoid modifying reserved arrays.)
1838 You must take care to always unreserve an array after reserving it,
1839 even in the presence of non-local exits. If a non-local exit can
1840 happen between these two calls, you should install a dynwind context
1841 that releases the array when it is left (@pxref{Dynamic Wind}).
1843 In addition, array reserving and unreserving must be properly
1844 paired. For instance, when reserving two or more arrays in a certain
1845 order, you need to unreserve them in the opposite order.
1847 Once you have reserved an array and have retrieved the pointer to its
1848 elements, you must figure out the layout of the elements in memory.
1849 Guile allows slices to be taken out of arrays without actually making a
1850 copy, such as making an alias for the diagonal of a matrix that can be
1851 treated as a vector. Arrays that result from such an operation are not
1852 stored contiguously in memory and when working with their elements
1853 directly, you need to take this into account.
1855 The layout of array elements in memory can be defined via a
1856 @emph{mapping function} that computes a scalar position from a vector of
1857 indices. The scalar position then is the offset of the element with the
1858 given indices from the start of the storage block of the array.
1860 In Guile, this mapping function is restricted to be @dfn{affine}: all
1861 mapping functions of Guile arrays can be written as @code{p = b +
1862 c[0]*i[0] + c[1]*i[1] + ... + c[n-1]*i[n-1]} where @code{i[k]} is the
1863 @nicode{k}th index and @code{n} is the rank of the array. For
1864 example, a matrix of size 3x3 would have @code{b == 0}, @code{c[0] ==
1865 3} and @code{c[1] == 1}. When you transpose this matrix (with
1866 @code{transpose-array}, say), you will get an array whose mapping
1867 function has @code{b == 0}, @code{c[0] == 1} and @code{c[1] == 3}.
1869 The function @code{scm_array_handle_dims} gives you (indirect) access to
1870 the coefficients @code{c[k]}.
1873 Note that there are no functions for accessing the elements of a
1874 character array yet. Once the string implementation of Guile has been
1875 changed to use Unicode, we will provide them.
1877 @deftp {C Type} scm_t_array_handle
1878 This is a structure type that holds all information necessary to manage
1879 the reservation of arrays as explained above. Structures of this type
1880 must be allocated on the stack and must only be accessed by the
1881 functions listed below.
1884 @deftypefn {C Function} void scm_array_get_handle (SCM array, scm_t_array_handle *handle)
1885 Reserve @var{array}, which must be an array, and prepare @var{handle} to
1886 be used with the functions below. You must eventually call
1887 @code{scm_array_handle_release} on @var{handle}, and do this in a
1888 properly nested fashion, as explained above. The structure pointed to
1889 by @var{handle} does not need to be initialized before calling this
1893 @deftypefn {C Function} void scm_array_handle_release (scm_t_array_handle *handle)
1894 End the array reservation represented by @var{handle}. After a call to
1895 this function, @var{handle} might be used for another reservation.
1898 @deftypefn {C Function} size_t scm_array_handle_rank (scm_t_array_handle *handle)
1899 Return the rank of the array represented by @var{handle}.
1902 @deftp {C Type} scm_t_array_dim
1903 This structure type holds information about the layout of one dimension
1904 of an array. It includes the following fields:
1909 The lower and upper bounds (both inclusive) of the permissible index
1910 range for the given dimension. Both values can be negative, but
1911 @var{lbnd} is always less than or equal to @var{ubnd}.
1914 The distance from one element of this dimension to the next. Note, too,
1915 that this can be negative.
1919 @deftypefn {C Function} {const scm_t_array_dim *} scm_array_handle_dims (scm_t_array_handle *handle)
1920 Return a pointer to a C vector of information about the dimensions of
1921 the array represented by @var{handle}. This pointer is valid as long as
1922 the array remains reserved. As explained above, the
1923 @code{scm_t_array_dim} structures returned by this function can be used
1924 calculate the position of an element in the storage block of the array
1927 This position can then be used as an index into the C array pointer
1928 returned by the various @code{scm_array_handle_<foo>_elements}
1929 functions, or with @code{scm_array_handle_ref} and
1930 @code{scm_array_handle_set}.
1932 Here is how one can compute the position @var{pos} of an element given
1933 its indices in the vector @var{indices}:
1936 ssize_t indices[RANK];
1937 scm_t_array_dim *dims;
1942 for (i = 0; i < RANK; i++)
1944 if (indices[i] < dims[i].lbnd || indices[i] > dims[i].ubnd)
1946 pos += (indices[i] - dims[i].lbnd) * dims[i].inc;
1951 @deftypefn {C Function} ssize_t scm_array_handle_pos (scm_t_array_handle *handle, SCM indices)
1952 Compute the position corresponding to @var{indices}, a list of
1953 indices. The position is computed as described above for
1954 @code{scm_array_handle_dims}. The number of the indices and their
1955 range is checked and an appropriate error is signalled for invalid
1959 @deftypefn {C Function} SCM scm_array_handle_ref (scm_t_array_handle *handle, ssize_t pos)
1960 Return the element at position @var{pos} in the storage block of the
1961 array represented by @var{handle}. Any kind of array is acceptable. No
1962 range checking is done on @var{pos}.
1965 @deftypefn {C Function} void scm_array_handle_set (scm_t_array_handle *handle, ssize_t pos, SCM val)
1966 Set the element at position @var{pos} in the storage block of the array
1967 represented by @var{handle} to @var{val}. Any kind of array is
1968 acceptable. No range checking is done on @var{pos}. An error is
1969 signalled when the array can not store @var{val}.
1972 @deftypefn {C Function} {const SCM *} scm_array_handle_elements (scm_t_array_handle *handle)
1973 Return a pointer to the elements of a ordinary array of general Scheme
1974 values (i.e., a non-uniform array) for reading. This pointer is valid
1975 as long as the array remains reserved.
1978 @deftypefn {C Function} {SCM *} scm_array_handle_writable_elements (scm_t_array_handle *handle)
1979 Like @code{scm_array_handle_elements}, but the pointer is good for
1980 reading and writing.
1983 @deftypefn {C Function} {const void *} scm_array_handle_uniform_elements (scm_t_array_handle *handle)
1984 Return a pointer to the elements of a uniform numeric array for reading.
1985 This pointer is valid as long as the array remains reserved. The size
1986 of each element is given by @code{scm_array_handle_uniform_element_size}.
1989 @deftypefn {C Function} {void *} scm_array_handle_uniform_writable_elements (scm_t_array_handle *handle)
1990 Like @code{scm_array_handle_uniform_elements}, but the pointer is good
1991 reading and writing.
1994 @deftypefn {C Function} size_t scm_array_handle_uniform_element_size (scm_t_array_handle *handle)
1995 Return the size of one element of the uniform numeric array represented
1999 @deftypefn {C Function} {const scm_t_uint8 *} scm_array_handle_u8_elements (scm_t_array_handle *handle)
2000 @deftypefnx {C Function} {const scm_t_int8 *} scm_array_handle_s8_elements (scm_t_array_handle *handle)
2001 @deftypefnx {C Function} {const scm_t_uint16 *} scm_array_handle_u16_elements (scm_t_array_handle *handle)
2002 @deftypefnx {C Function} {const scm_t_int16 *} scm_array_handle_s16_elements (scm_t_array_handle *handle)
2003 @deftypefnx {C Function} {const scm_t_uint32 *} scm_array_handle_u32_elements (scm_t_array_handle *handle)
2004 @deftypefnx {C Function} {const scm_t_int32 *} scm_array_handle_s32_elements (scm_t_array_handle *handle)
2005 @deftypefnx {C Function} {const scm_t_uint64 *} scm_array_handle_u64_elements (scm_t_array_handle *handle)
2006 @deftypefnx {C Function} {const scm_t_int64 *} scm_array_handle_s64_elements (scm_t_array_handle *handle)
2007 @deftypefnx {C Function} {const float *} scm_array_handle_f32_elements (scm_t_array_handle *handle)
2008 @deftypefnx {C Function} {const double *} scm_array_handle_f64_elements (scm_t_array_handle *handle)
2009 @deftypefnx {C Function} {const float *} scm_array_handle_c32_elements (scm_t_array_handle *handle)
2010 @deftypefnx {C Function} {const double *} scm_array_handle_c64_elements (scm_t_array_handle *handle)
2011 Return a pointer to the elements of a uniform numeric array of the
2012 indicated kind for reading. This pointer is valid as long as the array
2015 The pointers for @code{c32} and @code{c64} uniform numeric arrays point
2016 to pairs of floating point numbers. The even index holds the real part,
2017 the odd index the imaginary part of the complex number.
2020 @deftypefn {C Function} {scm_t_uint8 *} scm_array_handle_u8_writable_elements (scm_t_array_handle *handle)
2021 @deftypefnx {C Function} {scm_t_int8 *} scm_array_handle_s8_writable_elements (scm_t_array_handle *handle)
2022 @deftypefnx {C Function} {scm_t_uint16 *} scm_array_handle_u16_writable_elements (scm_t_array_handle *handle)
2023 @deftypefnx {C Function} {scm_t_int16 *} scm_array_handle_s16_writable_elements (scm_t_array_handle *handle)
2024 @deftypefnx {C Function} {scm_t_uint32 *} scm_array_handle_u32_writable_elements (scm_t_array_handle *handle)
2025 @deftypefnx {C Function} {scm_t_int32 *} scm_array_handle_s32_writable_elements (scm_t_array_handle *handle)
2026 @deftypefnx {C Function} {scm_t_uint64 *} scm_array_handle_u64_writable_elements (scm_t_array_handle *handle)
2027 @deftypefnx {C Function} {scm_t_int64 *} scm_array_handle_s64_writable_elements (scm_t_array_handle *handle)
2028 @deftypefnx {C Function} {float *} scm_array_handle_f32_writable_elements (scm_t_array_handle *handle)
2029 @deftypefnx {C Function} {double *} scm_array_handle_f64_writable_elements (scm_t_array_handle *handle)
2030 @deftypefnx {C Function} {float *} scm_array_handle_c32_writable_elements (scm_t_array_handle *handle)
2031 @deftypefnx {C Function} {double *} scm_array_handle_c64_writable_elements (scm_t_array_handle *handle)
2032 Like @code{scm_array_handle_<kind>_elements}, but the pointer is good
2033 for reading and writing.
2036 @deftypefn {C Function} {const scm_t_uint32 *} scm_array_handle_bit_elements (scm_t_array_handle *handle)
2037 Return a pointer to the words that store the bits of the represented
2038 array, which must be a bit array.
2040 Unlike other arrays, bit arrays have an additional offset that must be
2041 figured into index calculations. That offset is returned by
2042 @code{scm_array_handle_bit_elements_offset}.
2044 To find a certain bit you first need to calculate its position as
2045 explained above for @code{scm_array_handle_dims} and then add the
2046 offset. This gives the absolute position of the bit, which is always a
2047 non-negative integer.
2049 Each word of the bit array storage block contains exactly 32 bits, with
2050 the least significant bit in that word having the lowest absolute
2051 position number. The next word contains the next 32 bits.
2053 Thus, the following code can be used to access a bit whose position
2054 according to @code{scm_array_handle_dims} is given in @var{pos}:
2058 scm_t_array_handle handle;
2062 size_t word_pos, mask;
2064 scm_array_get_handle (&bit_array, &handle);
2065 bits = scm_array_handle_bit_elements (&handle);
2068 abs_pos = pos + scm_array_handle_bit_elements_offset (&handle);
2069 word_pos = abs_pos / 32;
2070 mask = 1L << (abs_pos % 32);
2072 if (bits[word_pos] & mask)
2075 scm_array_handle_release (&handle);
2080 @deftypefn {C Function} {scm_t_uint32 *} scm_array_handle_bit_writable_elements (scm_t_array_handle *handle)
2081 Like @code{scm_array_handle_bit_elements} but the pointer is good for
2082 reading and writing. You must take care not to modify bits outside of
2083 the allowed index range of the array, even for contiguous arrays.
2091 The @code{(ice-9 vlist)} module provides an implementation of the @dfn{VList}
2092 data structure designed by Phil Bagwell in 2002. VLists are immutable lists,
2093 which can contain any Scheme object. They improve on standard Scheme linked
2094 lists in several areas:
2098 Random access has typically constant-time complexity.
2101 Computing the length of a VList has time complexity logarithmic in the number of
2105 VLists use less storage space than standard lists.
2108 VList elements are stored in contiguous regions, which improves memory locality
2109 and leads to more efficient use of hardware caches.
2112 The idea behind VLists is to store vlist elements in increasingly large
2113 contiguous blocks (implemented as vectors here). These blocks are linked to one
2114 another using a pointer to the next block and an offset within that block. The
2115 size of these blocks form a geometric series with ratio
2116 @code{block-growth-factor} (2 by default).
2118 The VList structure also serves as the basis for the @dfn{VList-based hash
2119 lists} or ``vhashes'', an immutable dictionary type (@pxref{VHashes}).
2121 However, the current implementation in @code{(ice-9 vlist)} has several
2122 noteworthy shortcomings:
2127 It is @emph{not} thread-safe. Although operations on vlists are all
2128 @dfn{referentially transparent} (i.e., purely functional), adding elements to a
2129 vlist with @code{vlist-cons} mutates part of its internal structure, which makes
2130 it non-thread-safe. This could be fixed, but it would slow down
2134 @code{vlist-cons} always allocates at least as much memory as @code{cons}.
2135 Again, Phil Bagwell describes how to fix it, but that would require tuning the
2136 garbage collector in a way that may not be generally beneficial.
2139 @code{vlist-cons} is a Scheme procedure compiled to bytecode, and it does not
2140 compete with the straightforward C implementation of @code{cons}, and with the
2141 fact that the VM has a special @code{cons} instruction.
2145 We hope to address these in the future.
2147 The programming interface exported by @code{(ice-9 vlist)} is defined below.
2148 Most of it is the same as SRFI-1 with an added @code{vlist-} prefix to function
2151 @deffn {Scheme Procedure} vlist? obj
2152 Return true if @var{obj} is a VList.
2155 @defvr {Scheme Variable} vlist-null
2156 The empty VList. Note that it's possible to create an empty VList not
2157 @code{eq?} to @code{vlist-null}; thus, callers should always use
2158 @code{vlist-null?} when testing whether a VList is empty.
2161 @deffn {Scheme Procedure} vlist-null? vlist
2162 Return true if @var{vlist} is empty.
2165 @deffn {Scheme Procedure} vlist-cons item vlist
2166 Return a new vlist with @var{item} as its head and @var{vlist} as its tail.
2169 @deffn {Scheme Procedure} vlist-head vlist
2170 Return the head of @var{vlist}.
2173 @deffn {Scheme Procedure} vlist-tail vlist
2174 Return the tail of @var{vlist}.
2177 @defvr {Scheme Variable} block-growth-factor
2178 A fluid that defines the growth factor of VList blocks, 2 by default.
2181 The functions below provide the usual set of higher-level list operations.
2183 @deffn {Scheme Procedure} vlist-fold proc init vlist
2184 @deffnx {Scheme Procedure} vlist-fold-right proc init vlist
2185 Fold over @var{vlist}, calling @var{proc} for each element, as for SRFI-1
2186 @code{fold} and @code{fold-right} (@pxref{SRFI-1, @code{fold}}).
2189 @deffn {Scheme Procedure} vlist-ref vlist index
2190 Return the element at index @var{index} in @var{vlist}. This is typically a
2191 constant-time operation.
2194 @deffn {Scheme Procedure} vlist-length vlist
2195 Return the length of @var{vlist}. This is typically logarithmic in the number
2196 of elements in @var{vlist}.
2199 @deffn {Scheme Procedure} vlist-reverse vlist
2200 Return a new @var{vlist} whose content are those of @var{vlist} in reverse
2204 @deffn {Scheme Procedure} vlist-map proc vlist
2205 Map @var{proc} over the elements of @var{vlist} and return a new vlist.
2208 @deffn {Scheme Procedure} vlist-for-each proc vlist
2209 Call @var{proc} on each element of @var{vlist}. The result is unspecified.
2212 @deffn {Scheme Procedure} vlist-drop vlist count
2213 Return a new vlist that does not contain the @var{count} first elements of
2214 @var{vlist}. This is typically a constant-time operation.
2217 @deffn {Scheme Procedure} vlist-take vlist count
2218 Return a new vlist that contains only the @var{count} first elements of
2222 @deffn {Scheme Procedure} vlist-filter pred vlist
2223 Return a new vlist containing all the elements from @var{vlist} that satisfy
2227 @deffn {Scheme Procedure} vlist-delete x vlist [equal?]
2228 Return a new vlist corresponding to @var{vlist} without the elements
2229 @var{equal?} to @var{x}.
2232 @deffn {Scheme Procedure} vlist-unfold p f g seed [tail-gen]
2233 @deffnx {Scheme Procedure} vlist-unfold-right p f g seed [tail]
2234 Return a new vlist, as for SRFI-1 @code{unfold} and @code{unfold-right}
2235 (@pxref{SRFI-1, @code{unfold}}).
2238 @deffn {Scheme Procedure} vlist-append vlists ...
2239 Append the given vlists and return the resulting vlist.
2242 @deffn {Scheme Procedure} list->vlist lst
2243 Return a new vlist whose contents correspond to @var{lst}.
2246 @deffn {Scheme Procedure} vlist->list vlist
2247 Return a new list whose contents match those of @var{vlist}.
2255 A @dfn{record type} is a first class object representing a user-defined
2256 data type. A @dfn{record} is an instance of a record type.
2258 @deffn {Scheme Procedure} record? obj
2259 Return @code{#t} if @var{obj} is a record of any type and @code{#f}
2262 Note that @code{record?} may be true of any Scheme value; there is no
2263 promise that records are disjoint with other Scheme types.
2266 @deffn {Scheme Procedure} make-record-type type-name field-names [print]
2267 Create and return a new @dfn{record-type descriptor}.
2269 @var{type-name} is a string naming the type. Currently it's only used
2270 in the printed representation of records, and in diagnostics.
2271 @var{field-names} is a list of symbols naming the fields of a record
2272 of the type. Duplicates are not allowed among these symbols.
2275 (make-record-type "employee" '(name age salary))
2278 The optional @var{print} argument is a function used by
2279 @code{display}, @code{write}, etc, for printing a record of the new
2280 type. It's called as @code{(@var{print} record port)} and should look
2281 at @var{record} and write to @var{port}.
2284 @deffn {Scheme Procedure} record-constructor rtd [field-names]
2285 Return a procedure for constructing new members of the type represented
2286 by @var{rtd}. The returned procedure accepts exactly as many arguments
2287 as there are symbols in the given list, @var{field-names}; these are
2288 used, in order, as the initial values of those fields in a new record,
2289 which is returned by the constructor procedure. The values of any
2290 fields not named in that list are unspecified. The @var{field-names}
2291 argument defaults to the list of field names in the call to
2292 @code{make-record-type} that created the type represented by @var{rtd};
2293 if the @var{field-names} argument is provided, it is an error if it
2294 contains any duplicates or any symbols not in the default list.
2297 @deffn {Scheme Procedure} record-predicate rtd
2298 Return a procedure for testing membership in the type represented by
2299 @var{rtd}. The returned procedure accepts exactly one argument and
2300 returns a true value if the argument is a member of the indicated record
2301 type; it returns a false value otherwise.
2304 @deffn {Scheme Procedure} record-accessor rtd field-name
2305 Return a procedure for reading the value of a particular field of a
2306 member of the type represented by @var{rtd}. The returned procedure
2307 accepts exactly one argument which must be a record of the appropriate
2308 type; it returns the current value of the field named by the symbol
2309 @var{field-name} in that record. The symbol @var{field-name} must be a
2310 member of the list of field-names in the call to @code{make-record-type}
2311 that created the type represented by @var{rtd}.
2314 @deffn {Scheme Procedure} record-modifier rtd field-name
2315 Return a procedure for writing the value of a particular field of a
2316 member of the type represented by @var{rtd}. The returned procedure
2317 accepts exactly two arguments: first, a record of the appropriate type,
2318 and second, an arbitrary Scheme value; it modifies the field named by
2319 the symbol @var{field-name} in that record to contain the given value.
2320 The returned value of the modifier procedure is unspecified. The symbol
2321 @var{field-name} must be a member of the list of field-names in the call
2322 to @code{make-record-type} that created the type represented by
2326 @deffn {Scheme Procedure} record-type-descriptor record
2327 Return a record-type descriptor representing the type of the given
2328 record. That is, for example, if the returned descriptor were passed to
2329 @code{record-predicate}, the resulting predicate would return a true
2330 value when passed the given record. Note that it is not necessarily the
2331 case that the returned descriptor is the one that was passed to
2332 @code{record-constructor} in the call that created the constructor
2333 procedure that created the given record.
2336 @deffn {Scheme Procedure} record-type-name rtd
2337 Return the type-name associated with the type represented by rtd. The
2338 returned value is @code{eqv?} to the @var{type-name} argument given in
2339 the call to @code{make-record-type} that created the type represented by
2343 @deffn {Scheme Procedure} record-type-fields rtd
2344 Return a list of the symbols naming the fields in members of the type
2345 represented by @var{rtd}. The returned value is @code{equal?} to the
2346 field-names argument given in the call to @code{make-record-type} that
2347 created the type represented by @var{rtd}.
2352 @subsection Structures
2355 A @dfn{structure} is a first class data type which holds Scheme values
2356 or C words in fields numbered 0 upwards. A @dfn{vtable} represents a
2357 structure type, giving field types and permissions, and an optional
2358 print function for @code{write} etc.
2360 Structures are lower level than records (@pxref{Records}) but have
2361 some extra features. The vtable system allows sets of types be
2362 constructed, with class data. The uninterpreted words can
2363 inter-operate with C code, allowing arbitrary pointers or other values
2364 to be stored along side usual Scheme @code{SCM} values.
2368 * Structure Basics::
2373 @node Vtables, Structure Basics, Structures, Structures
2374 @subsubsection Vtables
2376 A vtable is a structure type, specifying its layout, and other
2377 information. A vtable is actually itself a structure, but there's no
2378 need to worry about that initially (@pxref{Vtable Contents}.)
2380 @deffn {Scheme Procedure} make-vtable fields [print]
2381 Create a new vtable.
2383 @var{fields} is a string describing the fields in the structures to be
2384 created. Each field is represented by two characters, a type letter
2385 and a permissions letter, for example @code{"pw"}. The types are as
2390 @code{p} -- a Scheme value. ``p'' stands for ``protected'' meaning
2391 it's protected against garbage collection.
2394 @code{u} -- an arbitrary word of data (an @code{scm_t_bits}). At the
2395 Scheme level it's read and written as an unsigned integer. ``u''
2396 stands for ``uninterpreted'' (it's not treated as a Scheme value), or
2397 ``unprotected'' (it's not marked during GC), or ``unsigned long'' (its
2398 size), or all of these things.
2401 @code{s} -- a self-reference. Such a field holds the @code{SCM} value
2402 of the structure itself (a circular reference). This can be useful in
2403 C code where you might have a pointer to the data array, and want to
2404 get the Scheme @code{SCM} handle for the structure. In Scheme code it
2408 The second letter for each field is a permission code,
2412 @code{w} -- writable, the field can be read and written.
2414 @code{r} -- read-only, the field can be read but not written.
2416 @code{o} -- opaque, the field can be neither read nor written at the
2417 Scheme level. This can be used for fields which should only be used
2420 @code{W},@code{R},@code{O} -- a tail array, with permissions for the
2421 array fields as per @code{w},@code{r},@code{o}.
2424 A tail array is further fields at the end of a structure. The last
2425 field in the layout string might be for instance @samp{pW} to have a
2426 tail of writable Scheme-valued fields. The @samp{pW} field itself
2427 holds the tail size, and the tail fields come after it.
2429 Here are some examples.
2432 (make-vtable "pw") ;; one writable field
2433 (make-vtable "prpw") ;; one read-only and one writable
2434 (make-vtable "pwuwuw") ;; one scheme and two uninterpreted
2436 (make-vtable "prpW") ;; one fixed then a tail array
2439 The optional @var{print} argument is a function called by
2440 @code{display} and @code{write} (etc) to give a printed representation
2441 of a structure created from this vtable. It's called
2442 @code{(@var{print} struct port)} and should look at @var{struct} and
2443 write to @var{port}. The default print merely gives a form like
2444 @samp{#<struct ADDR:ADDR>} with a pair of machine addresses.
2446 The following print function for example shows the two fields of its
2451 (lambda (struct port)
2453 (display (struct-ref struct 0) port)
2454 (display " and " port)
2455 (display (struct-ref struct 1) port)
2456 (display ">" port)))
2461 @node Structure Basics, Vtable Contents, Vtables, Structures
2462 @subsubsection Structure Basics
2464 This section describes the basic procedures for working with
2465 structures. @code{make-struct} creates a structure, and
2466 @code{struct-ref} and @code{struct-set!} access write fields.
2468 @deffn {Scheme Procedure} make-struct vtable tail-size [init...]
2469 @deffnx {C Function} scm_make_struct (vtable, tail_size, init_list)
2470 Create a new structure, with layout per the given @var{vtable}
2473 @var{tail-size} is the size of the tail array if @var{vtable}
2474 specifies a tail array. @var{tail-size} should be 0 when @var{vtable}
2475 doesn't specify a tail array.
2477 The optional @var{init}@dots{} arguments are initial values for the
2478 fields of the structure (and the tail array). This is the only way to
2479 put values in read-only fields. If there are fewer @var{init}
2480 arguments than fields then the defaults are @code{#f} for a Scheme
2481 field (type @code{p}) or 0 for an uninterpreted field (type @code{u}).
2483 Type @code{s} self-reference fields, permission @code{o} opaque
2484 fields, and the count field of a tail array are all ignored for the
2485 @var{init} arguments, ie.@: an argument is not consumed by such a
2486 field. An @code{s} is always set to the structure itself, an @code{o}
2487 is always set to @code{#f} or 0 (with the intention that C code will
2488 do something to it later), and the tail count is always the given
2494 (define v (make-vtable "prpwpw"))
2495 (define s (make-struct v 0 123 "abc" 456))
2496 (struct-ref s 0) @result{} 123
2497 (struct-ref s 1) @result{} "abc"
2501 (define v (make-vtable "prpW"))
2502 (define s (make-struct v 6 "fixed field" 'x 'y))
2503 (struct-ref s 0) @result{} "fixed field"
2504 (struct-ref s 1) @result{} 2 ;; tail size
2505 (struct-ref s 2) @result{} x ;; tail array ...
2506 (struct-ref s 3) @result{} y
2507 (struct-ref s 4) @result{} #f
2511 @deffn {Scheme Procedure} struct? obj
2512 @deffnx {C Function} scm_struct_p (obj)
2513 Return @code{#t} if @var{obj} is a structure, or @code{#f} if not.
2516 @deffn {Scheme Procedure} struct-ref struct n
2517 @deffnx {C Function} scm_struct_ref (struct, n)
2518 Return the contents of field number @var{n} in @var{struct}. The
2519 first field is number 0.
2521 An error is thrown if @var{n} is out of range, or if the field cannot
2522 be read because it's @code{o} opaque.
2525 @deffn {Scheme Procedure} struct-set! struct n value
2526 @deffnx {C Function} scm_struct_set_x (struct, n, value)
2527 Set field number @var{n} in @var{struct} to @var{value}. The first
2530 An error is thrown if @var{n} is out of range, or if the field cannot
2531 be written because it's @code{r} read-only or @code{o} opaque.
2534 @deffn {Scheme Procedure} struct-vtable struct
2535 @deffnx {C Function} scm_struct_vtable (struct)
2536 Return the vtable used by @var{struct}.
2538 This can be used to examine the layout of an unknown structure, see
2539 @ref{Vtable Contents}.
2543 @node Vtable Contents, Vtable Vtables, Structure Basics, Structures
2544 @subsubsection Vtable Contents
2546 A vtable is itself a structure, with particular fields that hold
2547 information about the structures to be created. These include the
2548 fields of those structures, and the print function for them. The
2549 variables below allow access to those fields.
2551 @deffn {Scheme Procedure} struct-vtable? obj
2552 @deffnx {C Function} scm_struct_vtable_p (obj)
2553 Return @code{#t} if @var{obj} is a vtable structure.
2555 Note that because vtables are simply structures with a particular
2556 layout, @code{struct-vtable?} can potentially return true on an
2557 application structure which merely happens to look like a vtable.
2560 @defvr {Scheme Variable} vtable-index-layout
2561 @defvrx {C Macro} scm_vtable_index_layout
2562 The field number of the layout specification in a vtable. The layout
2563 specification is a symbol like @code{pwpw} formed from the fields
2564 string passed to @code{make-vtable}, or created by
2565 @code{make-struct-layout} (@pxref{Vtable Vtables}).
2568 (define v (make-vtable "pwpw" 0))
2569 (struct-ref v vtable-index-layout) @result{} pwpw
2572 This field is read-only, since the layout of structures using a vtable
2576 @defvr {Scheme Variable} vtable-index-vtable
2577 @defvrx {C Macro} scm_vtable_index_vtable
2578 A self-reference to the vtable, ie.@: a type @code{s} field. This is
2579 used by C code within Guile and has no use at the Scheme level.
2582 @defvr {Scheme Variable} vtable-index-printer
2583 @defvrx {C Macro} scm_vtable_index_printer
2584 The field number of the printer function. This field contains @code{#f}
2585 if the default print function should be used.
2588 (define (my-print-func struct port)
2590 (define v (make-vtable "pwpw" my-print-func))
2591 (struct-ref v vtable-index-printer) @result{} my-print-func
2594 This field is writable, allowing the print function to be changed
2598 @deffn {Scheme Procedure} struct-vtable-name vtable
2599 @deffnx {Scheme Procedure} set-struct-vtable-name! vtable name
2600 @deffnx {C Function} scm_struct_vtable_name (vtable)
2601 @deffnx {C Function} scm_set_struct_vtable_name_x (vtable, name)
2602 Get or set the name of @var{vtable}. @var{name} is a symbol and is
2603 used in the default print function when printing structures created
2607 (define v (make-vtable "pw"))
2608 (set-struct-vtable-name! v 'my-name)
2610 (define s (make-struct v 0))
2611 (display s) @print{} #<my-name b7ab3ae0:b7ab3730>
2615 @deffn {Scheme Procedure} struct-vtable-tag vtable
2616 @deffnx {C Function} scm_struct_vtable_tag (vtable)
2617 Return the tag of the given @var{vtable}.
2619 @c FIXME: what can be said about what this means?
2624 @node Vtable Vtables, , Vtable Contents, Structures
2625 @subsubsection Vtable Vtables
2627 As noted above, a vtable is a structure and that structure is itself
2628 described by a vtable. Such a ``vtable of a vtable'' can be created
2629 with @code{make-vtable-vtable} below. This can be used to build sets
2630 of related vtables, possibly with extra application fields.
2632 This second level of vtable can be a little confusing. The ball
2633 example below is a typical use, adding a ``class data'' field to the
2634 vtables, from which instance structures are created. The current
2635 implementation of Guile's own records (@pxref{Records}) does something
2636 similar, a record type descriptor is a vtable with room to hold the
2637 field names of the records to be created from it.
2639 @deffn {Scheme Procedure} make-vtable-vtable user-fields tail-size [print]
2640 @deffnx {C Function} scm_make_vtable_vtable (user_fields, tail_size, print_and_init_list)
2641 Create a ``vtable-vtable'' which can be used to create vtables. This
2642 vtable-vtable is also a vtable, and is self-describing, meaning its
2643 vtable is itself. The following is a simple usage.
2646 (define vt-vt (make-vtable-vtable "" 0))
2647 (define vt (make-struct vt-vt 0
2648 (make-struct-layout "pwpw"))
2649 (define s (make-struct vt 0 123 456))
2651 (struct-ref s 0) @result{} 123
2654 @code{make-struct} is used to create a vtable from the vtable-vtable.
2655 The first initializer is a layout object (field
2656 @code{vtable-index-layout}), usually obtained from
2657 @code{make-struct-layout} (below). An optional second initializer is
2658 a printer function (field @code{vtable-index-printer}), used as
2659 described under @code{make-vtable} (@pxref{Vtables}).
2662 @var{user-fields} is a layout string giving extra fields to have in
2663 the vtables. A vtable starts with some base fields as per @ref{Vtable
2664 Contents}, and @var{user-fields} is appended. The @var{user-fields}
2665 start at field number @code{vtable-offset-user} (below), and exist in
2666 both the vtable-vtable and in the vtables created from it. Such
2667 fields provide space for ``class data''. For example,
2670 (define vt-of-vt (make-vtable-vtable "pw" 0))
2671 (define vt (make-struct vt-of-vt 0))
2672 (struct-set! vt vtable-offset-user "my class data")
2675 @var{tail-size} is the size of the tail array in the vtable-vtable
2676 itself, if @var{user-fields} specifies a tail array. This should be 0
2677 if nothing extra is required or the format has no tail array. The
2678 tail array field such as @samp{pW} holds the tail array size, as
2679 usual, and is followed by the extra space.
2682 (define vt-vt (make-vtable-vtable "pW" 20))
2683 (define my-vt-tail-start (1+ vtable-offset-user))
2684 (struct-set! vt-vt (+ 3 my-vt-tail-start) "data in tail")
2687 The optional @var{print} argument is used by @code{display} and
2688 @code{write} (etc) to print the vtable-vtable and any vtables created
2689 from it. It's called as @code{(@var{print} vtable port)} and should
2690 look at @var{vtable} and write to @var{port}. The default is the
2691 usual structure print function, which just gives machine addresses.
2694 @deffn {Scheme Procedure} make-struct-layout fields
2695 @deffnx {C Function} scm_make_struct_layout (fields)
2696 Return a structure layout symbol, from a @var{fields} string.
2697 @var{fields} is as described under @code{make-vtable}
2698 (@pxref{Vtables}). An invalid @var{fields} string is an error.
2701 (make-struct-layout "prpW") @result{} prpW
2702 (make-struct-layout "blah") @result{} ERROR
2706 @defvr {Scheme Variable} vtable-offset-user
2707 @defvrx {C Macro} scm_vtable_offset_user
2708 The first field in a vtable which is available for application use.
2709 Such fields only exist when specified by @var{user-fields} in
2710 @code{make-vtable-vtable} above.
2714 Here's an extended vtable-vtable example, creating classes of
2715 ``balls''. Each class has a ``colour'', which is fixed. Instances of
2716 those classes are created, and such each such ball has an ``owner'',
2717 which can be changed.
2720 (define ball-root (make-vtable-vtable "pr" 0))
2722 (define (make-ball-type ball-color)
2723 (make-struct ball-root 0
2724 (make-struct-layout "pw")
2726 (format port "#<a ~A ball owned by ~A>"
2730 (define (color ball)
2731 (struct-ref (struct-vtable ball) vtable-offset-user))
2732 (define (owner ball)
2733 (struct-ref ball 0))
2735 (define red (make-ball-type 'red))
2736 (define green (make-ball-type 'green))
2738 (define (make-ball type owner) (make-struct type 0 owner))
2740 (define ball (make-ball green 'Nisse))
2741 ball @result{} #<a green ball owned by Nisse>
2745 @node Dictionary Types
2746 @subsection Dictionary Types
2748 A @dfn{dictionary} object is a data structure used to index
2749 information in a user-defined way. In standard Scheme, the main
2750 aggregate data types are lists and vectors. Lists are not really
2751 indexed at all, and vectors are indexed only by number
2752 (e.g.@: @code{(vector-ref foo 5)}). Often you will find it useful
2753 to index your data on some other type; for example, in a library
2754 catalog you might want to look up a book by the name of its
2755 author. Dictionaries are used to help you organize information in
2758 An @dfn{association list} (or @dfn{alist} for short) is a list of
2759 key-value pairs. Each pair represents a single quantity or
2760 object; the @code{car} of the pair is a key which is used to
2761 identify the object, and the @code{cdr} is the object's value.
2763 A @dfn{hash table} also permits you to index objects with
2764 arbitrary keys, but in a way that makes looking up any one object
2765 extremely fast. A well-designed hash system makes hash table
2766 lookups almost as fast as conventional array or vector references.
2768 Alists are popular among Lisp programmers because they use only
2769 the language's primitive operations (lists, @dfn{car}, @dfn{cdr}
2770 and the equality primitives). No changes to the language core are
2771 necessary. Therefore, with Scheme's built-in list manipulation
2772 facilities, it is very convenient to handle data stored in an
2773 association list. Also, alists are highly portable and can be
2774 easily implemented on even the most minimal Lisp systems.
2776 However, alists are inefficient, especially for storing large
2777 quantities of data. Because we want Guile to be useful for large
2778 software systems as well as small ones, Guile provides a rich set
2779 of tools for using either association lists or hash tables.
2781 @node Association Lists
2782 @subsection Association Lists
2783 @tpindex Association Lists
2785 @cindex association List
2789 An association list is a conventional data structure that is often used
2790 to implement simple key-value databases. It consists of a list of
2791 entries in which each entry is a pair. The @dfn{key} of each entry is
2792 the @code{car} of the pair and the @dfn{value} of each entry is the
2796 ASSOCIATION LIST ::= '( (KEY1 . VALUE1)
2804 Association lists are also known, for short, as @dfn{alists}.
2806 The structure of an association list is just one example of the infinite
2807 number of possible structures that can be built using pairs and lists.
2808 As such, the keys and values in an association list can be manipulated
2809 using the general list structure procedures @code{cons}, @code{car},
2810 @code{cdr}, @code{set-car!}, @code{set-cdr!} and so on. However,
2811 because association lists are so useful, Guile also provides specific
2812 procedures for manipulating them.
2815 * Alist Key Equality::
2816 * Adding or Setting Alist Entries::
2817 * Retrieving Alist Entries::
2818 * Removing Alist Entries::
2819 * Sloppy Alist Functions::
2823 @node Alist Key Equality
2824 @subsubsection Alist Key Equality
2826 All of Guile's dedicated association list procedures, apart from
2827 @code{acons}, come in three flavours, depending on the level of equality
2828 that is required to decide whether an existing key in the association
2829 list is the same as the key that the procedure call uses to identify the
2834 Procedures with @dfn{assq} in their name use @code{eq?} to determine key
2838 Procedures with @dfn{assv} in their name use @code{eqv?} to determine
2842 Procedures with @dfn{assoc} in their name use @code{equal?} to
2843 determine key equality.
2846 @code{acons} is an exception because it is used to build association
2847 lists which do not require their entries' keys to be unique.
2849 @node Adding or Setting Alist Entries
2850 @subsubsection Adding or Setting Alist Entries
2852 @code{acons} adds a new entry to an association list and returns the
2853 combined association list. The combined alist is formed by consing the
2854 new entry onto the head of the alist specified in the @code{acons}
2855 procedure call. So the specified alist is not modified, but its
2856 contents become shared with the tail of the combined alist that
2857 @code{acons} returns.
2859 In the most common usage of @code{acons}, a variable holding the
2860 original association list is updated with the combined alist:
2863 (set! address-list (acons name address address-list))
2866 In such cases, it doesn't matter that the old and new values of
2867 @code{address-list} share some of their contents, since the old value is
2868 usually no longer independently accessible.
2870 Note that @code{acons} adds the specified new entry regardless of
2871 whether the alist may already contain entries with keys that are, in
2872 some sense, the same as that of the new entry. Thus @code{acons} is
2873 ideal for building alists where there is no concept of key uniqueness.
2876 (set! task-list (acons 3 "pay gas bill" '()))
2879 ((3 . "pay gas bill"))
2881 (set! task-list (acons 3 "tidy bedroom" task-list))
2884 ((3 . "tidy bedroom") (3 . "pay gas bill"))
2887 @code{assq-set!}, @code{assv-set!} and @code{assoc-set!} are used to add
2888 or replace an entry in an association list where there @emph{is} a
2889 concept of key uniqueness. If the specified association list already
2890 contains an entry whose key is the same as that specified in the
2891 procedure call, the existing entry is replaced by the new one.
2892 Otherwise, the new entry is consed onto the head of the old association
2893 list to create the combined alist. In all cases, these procedures
2894 return the combined alist.
2896 @code{assq-set!} and friends @emph{may} destructively modify the
2897 structure of the old association list in such a way that an existing
2898 variable is correctly updated without having to @code{set!} it to the
2904 (("mary" . "34 Elm Road") ("james" . "16 Bow Street"))
2906 (assoc-set! address-list "james" "1a London Road")
2908 (("mary" . "34 Elm Road") ("james" . "1a London Road"))
2912 (("mary" . "34 Elm Road") ("james" . "1a London Road"))
2918 (assoc-set! address-list "bob" "11 Newington Avenue")
2920 (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
2921 ("james" . "1a London Road"))
2925 (("mary" . "34 Elm Road") ("james" . "1a London Road"))
2928 The only safe way to update an association list variable when adding or
2929 replacing an entry like this is to @code{set!} the variable to the
2934 (assoc-set! address-list "bob" "11 Newington Avenue"))
2937 (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
2938 ("james" . "1a London Road"))
2941 Because of this slight inconvenience, you may find it more convenient to
2942 use hash tables to store dictionary data. If your application will not
2943 be modifying the contents of an alist very often, this may not make much
2946 If you need to keep the old value of an association list in a form
2947 independent from the list that results from modification by
2948 @code{acons}, @code{assq-set!}, @code{assv-set!} or @code{assoc-set!},
2949 use @code{list-copy} to copy the old association list before modifying
2952 @deffn {Scheme Procedure} acons key value alist
2953 @deffnx {C Function} scm_acons (key, value, alist)
2954 Add a new key-value pair to @var{alist}. A new pair is
2955 created whose car is @var{key} and whose cdr is @var{value}, and the
2956 pair is consed onto @var{alist}, and the new list is returned. This
2957 function is @emph{not} destructive; @var{alist} is not modified.
2960 @deffn {Scheme Procedure} assq-set! alist key val
2961 @deffnx {Scheme Procedure} assv-set! alist key value
2962 @deffnx {Scheme Procedure} assoc-set! alist key value
2963 @deffnx {C Function} scm_assq_set_x (alist, key, val)
2964 @deffnx {C Function} scm_assv_set_x (alist, key, val)
2965 @deffnx {C Function} scm_assoc_set_x (alist, key, val)
2966 Reassociate @var{key} in @var{alist} with @var{value}: find any existing
2967 @var{alist} entry for @var{key} and associate it with the new
2968 @var{value}. If @var{alist} does not contain an entry for @var{key},
2969 add a new one. Return the (possibly new) alist.
2971 These functions do not attempt to verify the structure of @var{alist},
2972 and so may cause unusual results if passed an object that is not an
2976 @node Retrieving Alist Entries
2977 @subsubsection Retrieving Alist Entries
2982 @code{assq}, @code{assv} and @code{assoc} find the entry in an alist
2983 for a given key, and return the @code{(@var{key} . @var{value})} pair.
2984 @code{assq-ref}, @code{assv-ref} and @code{assoc-ref} do a similar
2985 lookup, but return just the @var{value}.
2987 @deffn {Scheme Procedure} assq key alist
2988 @deffnx {Scheme Procedure} assv key alist
2989 @deffnx {Scheme Procedure} assoc key alist
2990 @deffnx {C Function} scm_assq (key, alist)
2991 @deffnx {C Function} scm_assv (key, alist)
2992 @deffnx {C Function} scm_assoc (key, alist)
2993 Return the first entry in @var{alist} with the given @var{key}. The
2994 return is the pair @code{(KEY . VALUE)} from @var{alist}. If there's
2995 no matching entry the return is @code{#f}.
2997 @code{assq} compares keys with @code{eq?}, @code{assv} uses
2998 @code{eqv?} and @code{assoc} uses @code{equal?}. See also SRFI-1
2999 which has an extended @code{assoc} (@ref{SRFI-1 Association Lists}).
3002 @deffn {Scheme Procedure} assq-ref alist key
3003 @deffnx {Scheme Procedure} assv-ref alist key
3004 @deffnx {Scheme Procedure} assoc-ref alist key
3005 @deffnx {C Function} scm_assq_ref (alist, key)
3006 @deffnx {C Function} scm_assv_ref (alist, key)
3007 @deffnx {C Function} scm_assoc_ref (alist, key)
3008 Return the value from the first entry in @var{alist} with the given
3009 @var{key}, or @code{#f} if there's no such entry.
3011 @code{assq-ref} compares keys with @code{eq?}, @code{assv-ref} uses
3012 @code{eqv?} and @code{assoc-ref} uses @code{equal?}.
3014 Notice these functions have the @var{key} argument last, like other
3015 @code{-ref} functions, but this is opposite to what @code{assq}
3018 When the return is @code{#f} it can be either @var{key} not found, or
3019 an entry which happens to have value @code{#f} in the @code{cdr}. Use
3020 @code{assq} etc above if you need to differentiate these cases.
3024 @node Removing Alist Entries
3025 @subsubsection Removing Alist Entries
3027 To remove the element from an association list whose key matches a
3028 specified key, use @code{assq-remove!}, @code{assv-remove!} or
3029 @code{assoc-remove!} (depending, as usual, on the level of equality
3030 required between the key that you specify and the keys in the
3033 As with @code{assq-set!} and friends, the specified alist may or may not
3034 be modified destructively, and the only safe way to update a variable
3035 containing the alist is to @code{set!} it to the value that
3036 @code{assq-remove!} and friends return.
3041 (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
3042 ("james" . "1a London Road"))
3044 (set! address-list (assoc-remove! address-list "mary"))
3047 (("bob" . "11 Newington Avenue") ("james" . "1a London Road"))
3050 Note that, when @code{assq/v/oc-remove!} is used to modify an
3051 association list that has been constructed only using the corresponding
3052 @code{assq/v/oc-set!}, there can be at most one matching entry in the
3053 alist, so the question of multiple entries being removed in one go does
3054 not arise. If @code{assq/v/oc-remove!} is applied to an association
3055 list that has been constructed using @code{acons}, or an
3056 @code{assq/v/oc-set!} with a different level of equality, or any mixture
3057 of these, it removes only the first matching entry from the alist, even
3058 if the alist might contain further matching entries. For example:
3061 (define address-list '())
3062 (set! address-list (assq-set! address-list "mary" "11 Elm Street"))
3063 (set! address-list (assq-set! address-list "mary" "57 Pine Drive"))
3066 (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street"))
3068 (set! address-list (assoc-remove! address-list "mary"))
3071 (("mary" . "11 Elm Street"))
3074 In this example, the two instances of the string "mary" are not the same
3075 when compared using @code{eq?}, so the two @code{assq-set!} calls add
3076 two distinct entries to @code{address-list}. When compared using
3077 @code{equal?}, both "mary"s in @code{address-list} are the same as the
3078 "mary" in the @code{assoc-remove!} call, but @code{assoc-remove!} stops
3079 after removing the first matching entry that it finds, and so one of the
3080 "mary" entries is left in place.
3082 @deffn {Scheme Procedure} assq-remove! alist key
3083 @deffnx {Scheme Procedure} assv-remove! alist key
3084 @deffnx {Scheme Procedure} assoc-remove! alist key
3085 @deffnx {C Function} scm_assq_remove_x (alist, key)
3086 @deffnx {C Function} scm_assv_remove_x (alist, key)
3087 @deffnx {C Function} scm_assoc_remove_x (alist, key)
3088 Delete the first entry in @var{alist} associated with @var{key}, and return
3089 the resulting alist.
3092 @node Sloppy Alist Functions
3093 @subsubsection Sloppy Alist Functions
3095 @code{sloppy-assq}, @code{sloppy-assv} and @code{sloppy-assoc} behave
3096 like the corresponding non-@code{sloppy-} procedures, except that they
3097 return @code{#f} when the specified association list is not well-formed,
3098 where the non-@code{sloppy-} versions would signal an error.
3100 Specifically, there are two conditions for which the non-@code{sloppy-}
3101 procedures signal an error, which the @code{sloppy-} procedures handle
3102 instead by returning @code{#f}. Firstly, if the specified alist as a
3103 whole is not a proper list:
3106 (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
3108 ERROR: In procedure assoc in expression (assoc "mary" (quote #)):
3109 ERROR: Wrong type argument in position 2 (expecting
3110 association list): ((1 . 2) ("key" . "door") . "open sesame")
3112 (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
3118 Secondly, if one of the entries in the specified alist is not a pair:
3121 (assoc 2 '((1 . 1) 2 (3 . 9)))
3123 ERROR: In procedure assoc in expression (assoc 2 (quote #)):
3124 ERROR: Wrong type argument in position 2 (expecting
3125 association list): ((1 . 1) 2 (3 . 9))
3127 (sloppy-assoc 2 '((1 . 1) 2 (3 . 9)))
3132 Unless you are explicitly working with badly formed association lists,
3133 it is much safer to use the non-@code{sloppy-} procedures, because they
3134 help to highlight coding and data errors that the @code{sloppy-}
3135 versions would silently cover up.
3137 @deffn {Scheme Procedure} sloppy-assq key alist
3138 @deffnx {C Function} scm_sloppy_assq (key, alist)
3139 Behaves like @code{assq} but does not do any error checking.
3140 Recommended only for use in Guile internals.
3143 @deffn {Scheme Procedure} sloppy-assv key alist
3144 @deffnx {C Function} scm_sloppy_assv (key, alist)
3145 Behaves like @code{assv} but does not do any error checking.
3146 Recommended only for use in Guile internals.
3149 @deffn {Scheme Procedure} sloppy-assoc key alist
3150 @deffnx {C Function} scm_sloppy_assoc (key, alist)
3151 Behaves like @code{assoc} but does not do any error checking.
3152 Recommended only for use in Guile internals.
3156 @subsubsection Alist Example
3158 Here is a longer example of how alists may be used in practice.
3161 (define capitals '(("New York" . "Albany")
3162 ("Oregon" . "Salem")
3163 ("Florida" . "Miami")))
3165 ;; What's the capital of Oregon?
3166 (assoc "Oregon" capitals) @result{} ("Oregon" . "Salem")
3167 (assoc-ref capitals "Oregon") @result{} "Salem"
3169 ;; We left out South Dakota.
3171 (assoc-set! capitals "South Dakota" "Pierre"))
3173 @result{} (("South Dakota" . "Pierre")
3174 ("New York" . "Albany")
3175 ("Oregon" . "Salem")
3176 ("Florida" . "Miami"))
3178 ;; And we got Florida wrong.
3180 (assoc-set! capitals "Florida" "Tallahassee"))
3182 @result{} (("South Dakota" . "Pierre")
3183 ("New York" . "Albany")
3184 ("Oregon" . "Salem")
3185 ("Florida" . "Tallahassee"))
3187 ;; After Oregon secedes, we can remove it.
3189 (assoc-remove! capitals "Oregon"))
3191 @result{} (("South Dakota" . "Pierre")
3192 ("New York" . "Albany")
3193 ("Florida" . "Tallahassee"))
3197 @subsection VList-Based Hash Lists or ``VHashes''
3199 @cindex VList-based hash lists
3202 The @code{(ice-9 vlist)} module provides an implementation of @dfn{VList-based
3203 hash lists} (@pxref{VLists}). VList-based hash lists, or @dfn{vhashes}, are an
3204 immutable dictionary type similar to association lists that maps @dfn{keys} to
3205 @dfn{values}. However, unlike association lists, accessing a value given its
3206 key is typically a constant-time operation.
3208 The VHash programming interface of @code{(ice-9 vlist)} is mostly the same as
3209 that of association lists found in SRFI-1, with procedure names prefixed by
3210 @code{vhash-} instead of @code{alist-} (@pxref{SRFI-1 Association Lists}).
3212 In addition, vhashes can be manipulated using VList operations:
3215 (vlist-head (vhash-consq 'a 1 vlist-null))
3218 (define vh1 (vhash-consq 'b 2 (vhash-consq 'a 1 vlist-null)))
3219 (define vh2 (vhash-consq 'c 3 (vlist-tail vh1)))
3228 @result{} ((c . 3) (a . 1))
3231 However, keep in mind that procedures that construct new VLists
3232 (@code{vlist-map}, @code{vlist-filter}, etc.) return raw VLists, not vhashes:
3235 (define vh (alist->vhash '((a . 1) (b . 2) (c . 3)) hashq))
3240 ;; This will create a raw vlist.
3241 (vlist-filter (lambda (key+value) (odd? (cdr key+value))) vh))
3243 @result{} ERROR: Wrong type argument in position 2
3246 @result{} ((a . 1) (c . 3))
3249 @deffn {Scheme Procedure} vhash? obj
3250 Return true if @var{obj} is a vhash.
3253 @deffn {Scheme Procedure} vhash-cons key value vhash [hash-proc]
3254 @deffnx {Scheme Procedure} vhash-consq key value vhash
3255 @deffnx {Scheme Procedure} vhash-consv key value vhash
3256 Return a new hash list based on @var{vhash} where @var{key} is associated with
3257 @var{value}, using @var{hash-proc} to compute the hash of @var{key}.
3258 @var{vhash} must be either @code{vlist-null} or a vhash returned by a previous
3259 call to @code{vhash-cons}. @var{hash-proc} defaults to @code{hash} (@pxref{Hash
3260 Table Reference, @code{hash} procedure}). With @code{vhash-consq}, the
3261 @code{hashq} hash function is used; with @code{vhash-consv} the @code{hashv}
3262 hash function is used.
3264 All @code{vhash-cons} calls made to construct a vhash should use the same
3265 @var{hash-proc}. Failing to do that, the result is undefined.
3268 @deffn {Scheme Procedure} vhash-assoc key vhash [equal? [hash-proc]]
3269 @deffnx {Scheme Procedure} vhash-assq key vhash
3270 @deffnx {Scheme Procedure} vhash-assv key vhash
3271 Return the first key/value pair from @var{vhash} whose key is equal to @var{key}
3272 according to the @var{equal?} equality predicate (which defaults to
3273 @code{equal?}), and using @var{hash-proc} (which defaults to @code{hash}) to
3274 compute the hash of @var{key}. The second form uses @code{eq?} as the equality
3275 predicate and @code{hashq} as the hash function; the last form uses @code{eqv?}
3278 Note that it is important to consistently use the same hash function for
3279 @var{hash-proc} as was passed to @code{vhash-cons}. Failing to do that, the
3280 result is unpredictable.
3283 @deffn {Scheme Procedure} vhash-delete key vhash [equal? [hash-proc]]
3284 @deffnx {Scheme Procedure} vhash-delq key vhash
3285 @deffnx {Scheme Procedure} vhash-delv key vhash
3286 Remove all associations from @var{vhash} with @var{key}, comparing keys with
3287 @var{equal?} (which defaults to @code{equal?}), and computing the hash of
3288 @var{key} using @var{hash-proc} (which defaults to @code{hash}). The second
3289 form uses @code{eq?} as the equality predicate and @code{hashq} as the hash
3290 function; the last one uses @code{eqv?} and @code{hashv}.
3292 Again the choice of @var{hash-proc} must be consistent with previous calls to
3296 @deffn {Scheme Procedure} vhash-fold proc init vhash
3297 @deffnx {Scheme Procedure} vhash-fold-right proc init vhash
3298 Fold over the key/value elements of @var{vhash} in the given direction,
3299 with each call to @var{proc} having the form @code{(@var{proc} key value
3300 result)}, where @var{result} is the result of the previous call to
3301 @var{proc} and @var{init} the value of @var{result} for the first call
3305 @deffn {Scheme Procedure} vhash-fold* proc init key vhash [equal? [hash]]
3306 @deffnx {Scheme Procedure} vhash-foldq* proc init key vhash
3307 @deffnx {Scheme Procedure} vhash-foldv* proc init key vhash
3308 Fold over all the values associated with @var{key} in @var{vhash}, with each
3309 call to @var{proc} having the form @code{(proc value result)}, where
3310 @var{result} is the result of the previous call to @var{proc} and @var{init} the
3311 value of @var{result} for the first call to @var{proc}.
3313 Keys in @var{vhash} are hashed using @var{hash} are compared using @var{equal?}.
3314 The second form uses @code{eq?} as the equality predicate and @code{hashq} as
3315 the hash function; the third one uses @code{eqv?} and @code{hashv}.
3321 (alist->vhash '((a . 1) (a . 2) (z . 0) (a . 3))))
3323 (vhash-fold* cons '() 'a vh)
3326 (vhash-fold* cons '() 'z vh)
3331 @deffn {Scheme Procedure} alist->vhash alist [hash-proc]
3332 Return the vhash corresponding to @var{alist}, an association list, using
3333 @var{hash-proc} to compute key hashes. When omitted, @var{hash-proc} defaults
3339 @subsection Hash Tables
3340 @tpindex Hash Tables
3342 Hash tables are dictionaries which offer similar functionality as
3343 association lists: They provide a mapping from keys to values. The
3344 difference is that association lists need time linear in the size of
3345 elements when searching for entries, whereas hash tables can normally
3346 search in constant time. The drawback is that hash tables require a
3347 little bit more memory, and that you can not use the normal list
3348 procedures (@pxref{Lists}) for working with them.
3350 Guile provides two types of hashtables. One is an abstract data type
3351 that can only be manipulated with the functions in this section. The
3352 other type is concrete: it uses a normal vector with alists as
3353 elements. The advantage of the abstract hash tables is that they will
3354 be automatically resized when they become too full or too empty.
3357 * Hash Table Examples:: Demonstration of hash table usage.
3358 * Hash Table Reference:: Hash table procedure descriptions.
3362 @node Hash Table Examples
3363 @subsubsection Hash Table Examples
3365 For demonstration purposes, this section gives a few usage examples of
3366 some hash table procedures, together with some explanation what they do.
3368 First we start by creating a new hash table with 31 slots, and
3369 populate it with two key/value pairs.
3372 (define h (make-hash-table 31))
3374 ;; This is an opaque object
3379 ;; We can also use a vector of alists.
3380 (define h (make-vector 7 '()))
3384 #(() () () () () () ())
3386 ;; Inserting into a hash table can be done with hashq-set!
3387 (hashq-set! h 'foo "bar")
3391 (hashq-set! h 'braz "zonk")
3395 ;; Or with hash-create-handle!
3396 (hashq-create-handle! h 'frob #f)
3400 ;; The vector now contains three elements in the alists and the frob
3401 ;; entry is at index (hashq 'frob).
3404 #(((braz . "zonk")) ((foo . "bar")) () () () () ((frob . #f)))
3412 You can get the value for a given key with the procedure
3413 @code{hashq-ref}, but the problem with this procedure is that you
3414 cannot reliably determine whether a key does exists in the table. The
3415 reason is that the procedure returns @code{#f} if the key is not in
3416 the table, but it will return the same value if the key is in the
3417 table and just happens to have the value @code{#f}, as you can see in
3418 the following examples.
3429 (hashq-ref h 'not-there)
3434 Better is to use the procedure @code{hashq-get-handle}, which makes a
3435 distinction between the two cases. Just like @code{assq}, this
3436 procedure returns a key/value-pair on success, and @code{#f} if the
3440 (hashq-get-handle h 'foo)
3444 (hashq-get-handle h 'not-there)
3449 There is no procedure for calculating the number of key/value-pairs in
3450 a hash table, but @code{hash-fold} can be used for doing exactly that.
3453 (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h)
3458 @node Hash Table Reference
3459 @subsubsection Hash Table Reference
3461 @c FIXME: Describe in broad terms what happens for resizing, and what
3462 @c the initial size means for this.
3464 Like the association list functions, the hash table functions come in
3465 several varieties, according to the equality test used for the keys.
3466 Plain @code{hash-} functions use @code{equal?}, @code{hashq-}
3467 functions use @code{eq?}, @code{hashv-} functions use @code{eqv?}, and
3468 the @code{hashx-} functions use an application supplied test.
3470 A single @code{make-hash-table} creates a hash table suitable for use
3471 with any set of functions, but it's imperative that just one set is
3472 then used consistently, or results will be unpredictable.
3474 Hash tables are implemented as a vector indexed by a hash value formed
3475 from the key, with an association list of key/value pairs for each
3476 bucket in case distinct keys hash together. Direct access to the
3477 pairs in those lists is provided by the @code{-handle-} functions.
3478 The abstract kind of hash tables hide the vector in an opaque object
3479 that represents the hash table, while for the concrete kind the vector
3480 @emph{is} the hashtable.
3482 When the number of table entries in an abstract hash table goes above
3483 a threshold, the vector is made larger and the entries are rehashed,
3484 to prevent the bucket lists from becoming too long and slowing down
3485 accesses. When the number of entries goes below a threshold, the
3486 vector is shrunk to save space.
3488 A abstract hash table is created with @code{make-hash-table}. To
3489 create a vector that is suitable as a hash table, use
3490 @code{(make-vector @var{size} '())}, for example.
3492 For the @code{hashx-} ``extended'' routines, an application supplies a
3493 @var{hash} function producing an integer index like @code{hashq} etc
3494 below, and an @var{assoc} alist search function like @code{assq} etc
3495 (@pxref{Retrieving Alist Entries}). Here's an example of such
3496 functions implementing case-insensitive hashing of string keys,
3499 (use-modules (srfi srfi-1)
3502 (define (my-hash str size)
3503 (remainder (string-hash-ci str) size))
3504 (define (my-assoc str alist)
3505 (find (lambda (pair) (string-ci=? str (car pair))) alist))
3507 (define my-table (make-hash-table))
3508 (hashx-set! my-hash my-assoc my-table "foo" 123)
3510 (hashx-ref my-hash my-assoc my-table "FOO")
3514 In a @code{hashx-} @var{hash} function the aim is to spread keys
3515 across the vector, so bucket lists don't become long. But the actual
3516 values are arbitrary as long as they're in the range 0 to
3517 @math{@var{size}-1}. Helpful functions for forming a hash value, in
3518 addition to @code{hashq} etc below, include @code{symbol-hash}
3519 (@pxref{Symbol Keys}), @code{string-hash} and @code{string-hash-ci}
3520 (@pxref{String Comparison}), and @code{char-set-hash}
3521 (@pxref{Character Set Predicates/Comparison}).
3524 @deffn {Scheme Procedure} make-hash-table [size]
3525 Create a new abstract hash table object, with an optional minimum
3528 When @var{size} is given, the table vector will still grow and shrink
3529 automatically, as described above, but with @var{size} as a minimum.
3530 If an application knows roughly how many entries the table will hold
3531 then it can use @var{size} to avoid rehashing when initial entries are
3535 @deffn {Scheme Procedure} hash-table? obj
3536 @deffnx {C Function} scm_hash_table_p (obj)
3537 Return @code{#t} if @var{obj} is a abstract hash table object.
3540 @deffn {Scheme Procedure} hash-clear! table
3541 @deffnx {C Function} scm_hash_clear_x (table)
3542 Remove all items from @var{table} (without triggering a resize).
3545 @deffn {Scheme Procedure} hash-ref table key [dflt]
3546 @deffnx {Scheme Procedure} hashq-ref table key [dflt]
3547 @deffnx {Scheme Procedure} hashv-ref table key [dflt]
3548 @deffnx {Scheme Procedure} hashx-ref hash assoc table key [dflt]
3549 @deffnx {C Function} scm_hash_ref (table, key, dflt)
3550 @deffnx {C Function} scm_hashq_ref (table, key, dflt)
3551 @deffnx {C Function} scm_hashv_ref (table, key, dflt)
3552 @deffnx {C Function} scm_hashx_ref (hash, assoc, table, key, dflt)
3553 Lookup @var{key} in the given hash @var{table}, and return the
3554 associated value. If @var{key} is not found, return @var{dflt}, or
3555 @code{#f} if @var{dflt} is not given.
3558 @deffn {Scheme Procedure} hash-set! table key val
3559 @deffnx {Scheme Procedure} hashq-set! table key val
3560 @deffnx {Scheme Procedure} hashv-set! table key val
3561 @deffnx {Scheme Procedure} hashx-set! hash assoc table key val
3562 @deffnx {C Function} scm_hash_set_x (table, key, val)
3563 @deffnx {C Function} scm_hashq_set_x (table, key, val)
3564 @deffnx {C Function} scm_hashv_set_x (table, key, val)
3565 @deffnx {C Function} scm_hashx_set_x (hash, assoc, table, key, val)
3566 Associate @var{val} with @var{key} in the given hash @var{table}. If
3567 @var{key} is already present then it's associated value is changed.
3568 If it's not present then a new entry is created.
3571 @deffn {Scheme Procedure} hash-remove! table key
3572 @deffnx {Scheme Procedure} hashq-remove! table key
3573 @deffnx {Scheme Procedure} hashv-remove! table key
3574 @deffnx {Scheme Procedure} hashx-remove! hash assoc table key
3575 @deffnx {C Function} scm_hash_remove_x (table, key)
3576 @deffnx {C Function} scm_hashq_remove_x (table, key)
3577 @deffnx {C Function} scm_hashv_remove_x (table, key)
3578 @deffnx {C Function} scm_hashx_remove_x (hash, assoc, table, key)
3579 Remove any association for @var{key} in the given hash @var{table}.
3580 If @var{key} is not in @var{table} then nothing is done.
3583 @deffn {Scheme Procedure} hash key size
3584 @deffnx {Scheme Procedure} hashq key size
3585 @deffnx {Scheme Procedure} hashv key size
3586 @deffnx {C Function} scm_hash (key, size)
3587 @deffnx {C Function} scm_hashq (key, size)
3588 @deffnx {C Function} scm_hashv (key, size)
3589 Return a hash value for @var{key}. This is a number in the range
3590 @math{0} to @math{@var{size}-1}, which is suitable for use in a hash
3591 table of the given @var{size}.
3593 Note that @code{hashq} and @code{hashv} may use internal addresses of
3594 objects, so if an object is garbage collected and re-created it can
3595 have a different hash value, even when the two are notionally
3596 @code{eq?}. For instance with symbols,
3599 (hashq 'something 123) @result{} 19
3601 (hashq 'something 123) @result{} 62
3604 In normal use this is not a problem, since an object entered into a
3605 hash table won't be garbage collected until removed. It's only if
3606 hashing calculations are somehow separated from normal references that
3607 its lifetime needs to be considered.
3610 @deffn {Scheme Procedure} hash-get-handle table key
3611 @deffnx {Scheme Procedure} hashq-get-handle table key
3612 @deffnx {Scheme Procedure} hashv-get-handle table key
3613 @deffnx {Scheme Procedure} hashx-get-handle hash assoc table key
3614 @deffnx {C Function} scm_hash_get_handle (table, key)
3615 @deffnx {C Function} scm_hashq_get_handle (table, key)
3616 @deffnx {C Function} scm_hashv_get_handle (table, key)
3617 @deffnx {C Function} scm_hashx_get_handle (hash, assoc, table, key)
3618 Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
3619 given hash @var{table}, or @code{#f} if @var{key} is not in
3623 @deffn {Scheme Procedure} hash-create-handle! table key init
3624 @deffnx {Scheme Procedure} hashq-create-handle! table key init
3625 @deffnx {Scheme Procedure} hashv-create-handle! table key init
3626 @deffnx {Scheme Procedure} hashx-create-handle! hash assoc table key init
3627 @deffnx {C Function} scm_hash_create_handle_x (table, key, init)
3628 @deffnx {C Function} scm_hashq_create_handle_x (table, key, init)
3629 @deffnx {C Function} scm_hashv_create_handle_x (table, key, init)
3630 @deffnx {C Function} scm_hashx_create_handle_x (hash, assoc, table, key, init)
3631 Return the @code{(@var{key} . @var{value})} pair for @var{key} in the
3632 given hash @var{table}. If @var{key} is not in @var{table} then
3633 create an entry for it with @var{init} as the value, and return that
3637 @deffn {Scheme Procedure} hash-map->list proc table
3638 @deffnx {Scheme Procedure} hash-for-each proc table
3639 @deffnx {C Function} scm_hash_map_to_list (proc, table)
3640 @deffnx {C Function} scm_hash_for_each (proc, table)
3641 Apply @var{proc} to the entries in the given hash @var{table}. Each
3642 call is @code{(@var{proc} @var{key} @var{value})}. @code{hash-map->list}
3643 returns a list of the results from these calls, @code{hash-for-each}
3644 discards the results and returns an unspecified value.
3646 Calls are made over the table entries in an unspecified order, and for
3647 @code{hash-map->list} the order of the values in the returned list is
3648 unspecified. Results will be unpredictable if @var{table} is modified
3651 For example the following returns a new alist comprising all the
3652 entries from @code{mytable}, in no particular order.
3655 (hash-map->list cons mytable)
3659 @deffn {Scheme Procedure} hash-for-each-handle proc table
3660 @deffnx {C Function} scm_hash_for_each_handle (proc, table)
3661 Apply @var{proc} to the entries in the given hash @var{table}. Each
3662 call is @code{(@var{proc} @var{handle})}, where @var{handle} is a
3663 @code{(@var{key} . @var{value})} pair. Return an unspecified value.
3665 @code{hash-for-each-handle} differs from @code{hash-for-each} only in
3666 the argument list of @var{proc}.
3669 @deffn {Scheme Procedure} hash-fold proc init table
3670 @deffnx {C Function} scm_hash_fold (proc, init, table)
3671 Accumulate a result by applying @var{proc} to the elements of the
3672 given hash @var{table}. Each call is @code{(@var{proc} @var{key}
3673 @var{value} @var{prior-result})}, where @var{key} and @var{value} are
3674 from the @var{table} and @var{prior-result} is the return from the
3675 previous @var{proc} call. For the first call, @var{prior-result} is
3676 the given @var{init} value.
3678 Calls are made over the table entries in an unspecified order.
3679 Results will be unpredictable if @var{table} is modified while
3680 @code{hash-fold} is running.
3682 For example, the following returns a count of how many keys in
3683 @code{mytable} are strings.
3686 (hash-fold (lambda (key value prior)
3687 (if (string? key) (1+ prior) prior))
3694 @c TeX-master: "guile.texi"