Compound Data Types
===================

This chapter describes Guile's compound data types.  By compound we mean that the primary purpose of these data types is to act as containers for other kinds of data (including other compound objects). For instance, a (non-uniform) vector with length 5 is a container that can hold five arbitrary Scheme objects.

The various kinds of container object differ from each other in how their memory is allocated, how they are indexed, and how particular values can be looked up within them.

Pairs
-----

Pairs are used to combine two Scheme objects into one compound object. Hence the name: A pair stores a pair of objects.

The data type pair is extremely important in Scheme, just like in any other Lisp dialect.  The reason is that pairs are not only used to make two values available as one object, but that pairs are used for constructing lists of values.  Because lists are so important in Scheme, they are described in a section of their own (see Lists).

Pairs can literally get entered in source code or at the REPL, in the so-called dotted list syntax.  This syntax consists of an opening parentheses, the first element of the pair, a dot, the second element and a closing parentheses.  The following example shows how a pair consisting of the two numbers 1 and 2, and a pair containing the symbols foo and bar can be entered.  It is very important to write the whitespace before and after the dot, because otherwise the Scheme parser would not be able to figure out where to split the tokens.

     (1 . 2)
     (foo . bar)

But beware, if you want to try out these examples, you have to quote the expressions.  More information about quotation is available in the section Expression Syntax.  The correct way to try these examples is as follows.

     '(1 . 2)
     =>
     (1 . 2)
     '(foo . bar)
     =>
     (foo . bar)

A new pair is made by calling the procedure cons with two arguments.  Then the argument values are stored into a newly allocated pair, and the pair is returned.  The name cons stands for "construct".  Use the procedure pair? to test whether a given Scheme object is a pair or not.

 -- Scheme Procedure: cons x y
 -- C Function: scm_cons (x, y)
     Return a newly allocated pair whose car is X and whose cdr is Y.  The pair is guaranteed to be different (in the sense of eq?) from every previously existing object.

 -- Scheme Procedure: pair? x
 -- C Function: scm_pair_p (x)
     Return #t if X is a pair; otherwise return #f.

 -- C Function: int scm_is_pair (SCM x)
     Return 1 when X is a pair; otherwise return 0.

The two parts of a pair are traditionally called car and cdr.  They can be retrieved with procedures of the same name (car and cdr), and can be modified with the procedures set-car! and set-cdr!.  Since a very common operation in Scheme programs is to access the car of a car of a pair, or the car of the cdr of a pair, etc., the procedures called caar, cadr and so on are also predefined.

 -- Scheme Procedure: car pair
 -- Scheme Procedure: cdr pair
 -- C Function: scm_car (pair)
 -- C Function: scm_cdr (pair)
     Return the car or the cdr of PAIR, respectively.

 -- C Macro: SCM SCM_CAR (SCM pair)
 -- C Macro: SCM SCM_CDR (SCM pair)
     These two macros are the fastest way to access the car or cdr of a pair; they can be thought of as compiling into a single memory reference.

     These macros do no checking at all.  The argument PAIR must be a valid pair.

 -- Scheme Procedure: cddr pair
 -- Scheme Procedure: cdar pair
 -- Scheme Procedure: cadr pair
 -- Scheme Procedure: caar pair
 -- Scheme Procedure: cdddr pair
 -- Scheme Procedure: cddar pair
 -- Scheme Procedure: cdadr pair
 -- Scheme Procedure: cdaar pair
 -- Scheme Procedure: caddr pair
 -- Scheme Procedure: cadar pair
 -- Scheme Procedure: caadr pair
 -- Scheme Procedure: caaar pair
 -- Scheme Procedure: cddddr pair
 -- Scheme Procedure: cdddar pair
 -- Scheme Procedure: cddadr pair
 -- Scheme Procedure: cddaar pair
 -- Scheme Procedure: cdaddr pair
 -- Scheme Procedure: cdadar pair
 -- Scheme Procedure: cdaadr pair
 -- Scheme Procedure: cdaaar pair
 -- Scheme Procedure: cadddr pair
 -- Scheme Procedure: caddar pair
 -- Scheme Procedure: cadadr pair
 -- Scheme Procedure: cadaar pair
 -- Scheme Procedure: caaddr pair
 -- Scheme Procedure: caadar pair
 -- Scheme Procedure: caaadr pair
 -- Scheme Procedure: caaaar pair
 -- C Function: scm_cddr (pair)
 -- C Function: scm_cdar (pair)
 -- C Function: scm_cadr (pair)
 -- C Function: scm_caar (pair)
 -- C Function: scm_cdddr (pair)
 -- C Function: scm_cddar (pair)
 -- C Function: scm_cdadr (pair)
 -- C Function: scm_cdaar (pair)
 -- C Function: scm_caddr (pair)
 -- C Function: scm_cadar (pair)
 -- C Function: scm_caadr (pair)
 -- C Function: scm_caaar (pair)
 -- C Function: scm_cddddr (pair)
 -- C Function: scm_cdddar (pair)
 -- C Function: scm_cddadr (pair)
 -- C Function: scm_cddaar (pair)
 -- C Function: scm_cdaddr (pair)
 -- C Function: scm_cdadar (pair)
 -- C Function: scm_cdaadr (pair)
 -- C Function: scm_cdaaar (pair)
 -- C Function: scm_cadddr (pair)
 -- C Function: scm_caddar (pair)
 -- C Function: scm_cadadr (pair)
 -- C Function: scm_cadaar (pair)
 -- C Function: scm_caaddr (pair)
 -- C Function: scm_caadar (pair)
 -- C Function: scm_caaadr (pair)
 -- C Function: scm_caaaar (pair)
     These procedures are compositions of car and cdr, where for example caddr could be defined by

          (define caddr (lambda (x) (car (cdr (cdr x)))))

     cadr, caddr and cadddr pick out the second, third or fourth elements of a list, respectively.  SRFI-1 provides the same under the names second, third and fourth (see SRFI-1 Selectors).

 -- Scheme Procedure: set-car! pair value
 -- C Function: scm_set_car_x (pair, value)
     Stores VALUE in the car field of PAIR.  The value returned by set-car! is unspecified.

 -- Scheme Procedure: set-cdr! pair value
 -- C Function: scm_set_cdr_x (pair, value)
     Stores VALUE in the cdr field of PAIR.  The value returned by set-cdr! is unspecified.

Lists
-----

A very important data type in Scheme---as well as in all other Lisp dialects---is the data type list. (Strictly speaking, Scheme does not have a real datatype list.  Lists are made up of chained pairs, and only exist by definition---a list is a chain of pairs which looks like a list.)

This is the short definition of what a list is:

  * Either the empty list (),

  * or a pair which has a list in its cdr.

List Read Syntax
................

The syntax for lists is an opening parentheses, then all the elements of the list (separated by whitespace) and finally a closing parentheses. (Note that there is no separation character between the list elements, like a comma or a semicolon.).

     (1 2 3)            ; a list of the numbers 1, 2 and 3
     ("foo" bar 3.1415) ; a string, a symbol and a real number
     ()                 ; the empty list

The last example needs a bit more explanation.  A list with no elements, called the empty list, is special in some ways.  It is used for terminating lists by storing it into the cdr of the last pair that makes up a list.  An example will clear that up:

     (car '(1))
     =>
     1
     (cdr '(1))
     =>
     ()

This example also shows that lists have to be quoted when written (see Expression Syntax), because they would otherwise be mistakingly taken as procedure applications (see Simple Invocation).

List Predicates
...............

Often it is useful to test whether a given Scheme object is a list or not.  List-processing procedures could use this information to test whether their input is valid, or they could do different things depending on the datatype of their arguments.

 -- Scheme Procedure: list? x
 -- C Function: scm_list_p (x)
     Return #t iff X is a proper list, else #f.

The predicate null? is often used in list-processing code to tell whether a given list has run out of elements.  That is, a loop somehow deals with the elements of a list until the list satisfies null?.  Then, the algorithm terminates.

 -- Scheme Procedure: null? x
 -- C Function: scm_null_p (x)
     Return #t iff X is the empty list, else #f.

 -- C Function: int scm_is_null (SCM x)
     Return 1 when X is the empty list; otherwise return 0.

List Constructors
.................

This section describes the procedures for constructing new lists. list simply returns a list where the elements are the arguments, cons* is similar, but the last argument is stored in the cdr of the last pair of the list.

 -- Scheme Procedure: list elem ...
 -- C Function: scm_list_1 (elem1)
 -- C Function: scm_list_2 (elem1, elem2)
 -- C Function: scm_list_3 (elem1, elem2, elem3)
 -- C Function: scm_list_4 (elem1, elem2, elem3, elem4)
 -- C Function: scm_list_5 (elem1, elem2, elem3, elem4, elem5)
 -- C Function: scm_list_n (elem1, ..., elemN, SCM_UNDEFINED)
     Return a new list containing elements ELEM ....

     scm_list_n takes a variable number of arguments, terminated by the special SCM_UNDEFINED.  That final SCM_UNDEFINED is not included in the list.  None of ELEM ... can themselves be SCM_UNDEFINED, or scm_list_n will terminate at that point.

 -- Scheme Procedure: cons* arg1 arg2 ...
     Like list, but the last arg provides the tail of the constructed list, returning (cons ARG1 (cons ARG2 (cons ... ARGN))).  Requires at least one argument.  If given one argument, that argument is returned as result.  This function is called list* in some other Schemes and in Common LISP.

 -- Scheme Procedure: list-copy lst
 -- C Function: scm_list_copy (lst)
     Return a (newly-created) copy of LST.

 -- Scheme Procedure: make-list n [init]
     Create a list containing of N elements, where each element is initialized to INIT.  INIT defaults to the empty list () if not given.

Note that list-copy only makes a copy of the pairs which make up the spine of the lists.  The list elements are not copied, which means that modifying the elements of the new list also modifies the elements of the old list.  On the other hand, applying procedures like set-cdr! or delv! to the new list will not alter the old list.  If you also need to copy the list elements (making a deep copy), use the procedure copy-tree (see Copying).

List Selection
..............

These procedures are used to get some information about a list, or to retrieve one or more elements of a list.

 -- Scheme Procedure: length lst
 -- C Function: scm_length (lst)
     Return the number of elements in list LST.

 -- Scheme Procedure: last-pair lst
 -- C Function: scm_last_pair (lst)
     Return the last pair in LST, signalling an error if LST is circular.

 -- Scheme Procedure: list-ref list k
 -- C Function: scm_list_ref (list, k)
     Return the Kth element from LIST.

 -- Scheme Procedure: list-tail lst k
 -- Scheme Procedure: list-cdr-ref lst k
 -- C Function: scm_list_tail (lst, k)
     Return the "tail" of LST beginning with its Kth element. The first element of the list is considered to be element 0.

     list-tail and list-cdr-ref are identical.  It may help to think of list-cdr-ref as accessing the Kth cdr of the list, or returning the results of cdring K times down LST.

 -- Scheme Procedure: list-head lst k
 -- C Function: scm_list_head (lst, k)
     Copy the first K elements from LST into a new list, and return it.

Append and Reverse
..................

append and append! are used to concatenate two or more lists in order to form a new list.  reverse and reverse! return lists with the same elements as their arguments, but in reverse order.  The procedure variants with an ! directly modify the pairs which form the list, whereas the other procedures create new pairs.  This is why you should be careful when using the side-effecting variants.

 -- Scheme Procedure: append lst ... obj
 -- Scheme Procedure: append
 -- Scheme Procedure: append! lst ... obj
 -- Scheme Procedure: append!
 -- C Function: scm_append (lstlst)
 -- C Function: scm_append_x (lstlst)
     Return a list comprising all the elements of lists LST ... OBJ.  If called with no arguments, return the empty list.

          (append '(x) '(y))          =>  (x y)
          (append '(a) '(b c d))      =>  (a b c d)
          (append '(a (b)) '((c)))    =>  (a (b) (c))

     The last argument OBJ may actually be any object; an improper list results if the last argument is not a proper list.

          (append '(a b) '(c . d))    =>  (a b c . d)
          (append '() 'a)             =>  a

     append doesn't modify the given lists, but the return may share structure with the final OBJ.  append! modifies the given lists to form its return.

     For scm_append and scm_append_x, LSTLST is a list of the list operands LST ... OBJ.  That LSTLST itself is not modified or used in the return.

 -- Scheme Procedure: reverse lst
 -- Scheme Procedure: reverse! lst [newtail]
 -- C Function: scm_reverse (lst)
 -- C Function: scm_reverse_x (lst, newtail)
     Return a list comprising the elements of LST, in reverse order.

     reverse constructs a new list, reverse! modifies LST in constructing its return.

     For reverse!, the optional NEWTAIL is appended to the result.  NEWTAIL isn't reversed, it simply becomes the list tail.  For scm_reverse_x, the NEWTAIL parameter is mandatory, but can be SCM_EOL if no further tail is required.

List Modification
.................

The following procedures modify an existing list, either by changing elements of the list, or by changing the list structure itself.

 -- Scheme Procedure: list-set! list k val
 -- C Function: scm_list_set_x (list, k, val)
     Set the Kth element of LIST to VAL.

 -- Scheme Procedure: list-cdr-set! list k val
 -- C Function: scm_list_cdr_set_x (list, k, val)
     Set the Kth cdr of LIST to VAL.

 -- Scheme Procedure: delq item lst
 -- C Function: scm_delq (item, lst)
     Return a newly-created copy of LST with elements eq? to ITEM removed.  This procedure mirrors memq: delq compares elements of LST against ITEM with eq?.

 -- Scheme Procedure: delv item lst
 -- C Function: scm_delv (item, lst)
     Return a newly-created copy of LST with elements eqv? to ITEM removed.  This procedure mirrors memv: delv compares elements of LST against ITEM with eqv?.

 -- Scheme Procedure: delete item lst
 -- C Function: scm_delete (item, lst)
     Return a newly-created copy of LST with elements equal? to ITEM removed.  This procedure mirrors member: delete compares elements of LST against ITEM with equal?.

     See also SRFI-1 which has an extended delete (SRFI-1 Deleting), and also an lset-difference which can delete multiple ITEMs in one call (SRFI-1 Set Operations).

 -- Scheme Procedure: delq! item lst
 -- Scheme Procedure: delv! item lst
 -- Scheme Procedure: delete! item lst
 -- C Function: scm_delq_x (item, lst)
 -- C Function: scm_delv_x (item, lst)
 -- C Function: scm_delete_x (item, lst)
     These procedures are destructive versions of delq, delv and delete: they modify the pointers in the existing LST rather than creating a new list.  Caveat evaluator: Like other destructive list functions, these functions cannot modify the binding of LST, and so cannot be used to delete the first element of LST destructively.

 -- Scheme Procedure: delq1! item lst
 -- C Function: scm_delq1_x (item, lst)
     Like delq!, but only deletes the first occurrence of ITEM from LST.  Tests for equality using eq?.  See also delv1! and delete1!.

 -- Scheme Procedure: delv1! item lst
 -- C Function: scm_delv1_x (item, lst)
     Like delv!, but only deletes the first occurrence of ITEM from LST.  Tests for equality using eqv?.  See also delq1! and delete1!.

 -- Scheme Procedure: delete1! item lst
 -- C Function: scm_delete1_x (item, lst)
     Like delete!, but only deletes the first occurrence of ITEM from LST.  Tests for equality using equal?.  See also delq1! and delv1!.

 -- Scheme Procedure: filter pred lst
 -- Scheme Procedure: filter! pred lst
     Return a list containing all elements from LST which satisfy the predicate PRED.  The elements in the result list have the same order as in LST.  The order in which PRED is applied to the list elements is not specified.

     filter does not change LST, but the result may share a tail with it.  filter! may modify LST to construct its return.

List Searching
..............

The following procedures search lists for particular elements.  They use different comparison predicates for comparing list elements with the object to be searched.  When they fail, they return #f, otherwise they return the sublist whose car is equal to the search object, where equality depends on the equality predicate used.

 -- Scheme Procedure: memq x lst
 -- C Function: scm_memq (x, lst)
     Return the first sublist of LST whose car is eq? to X where the sublists of LST are the non-empty lists returned by (list-tail LST K) for K less than the length of LST.  If X does not occur in LST, then #f (not the empty list) is returned.

 -- Scheme Procedure: memv x lst
 -- C Function: scm_memv (x, lst)
     Return the first sublist of LST whose car is eqv? to X where the sublists of LST are the non-empty lists returned by (list-tail LST K) for K less than the length of LST.  If X does not occur in LST, then #f (not the empty list) is returned.

 -- Scheme Procedure: member x lst
 -- C Function: scm_member (x, lst)
     Return the first sublist of LST whose car is equal? to X where the sublists of LST are the non-empty lists returned by (list-tail LST K) for K less than the length of LST.  If X does not occur in LST, then #f (not the empty list) is returned.

     See also SRFI-1 which has an extended member function (SRFI-1 Searching).

List Mapping
............

List processing is very convenient in Scheme because the process of iterating over the elements of a list can be highly abstracted.  The procedures in this section are the most basic iterating procedures for lists.  They take a procedure and one or more lists as arguments, and apply the procedure to each element of the list.  They differ in their return value.

 -- Scheme Procedure: map proc arg1 arg2 ...
 -- Scheme Procedure: map-in-order proc arg1 arg2 ...
 -- C Function: scm_map (proc, arg1, args)
     Apply PROC to each element of the list ARG1 (if only two arguments are given), or to the corresponding elements of the argument lists (if more than two arguments are given).  The result(s) of the procedure applications are saved and returned in a list.  For map, the order of procedure applications is not specified, map-in-order applies the procedure from left to right to the list elements.

 -- Scheme Procedure: for-each proc arg1 arg2 ...
     Like map, but the procedure is always applied from left to right, and the result(s) of the procedure applications are thrown away.  The return value is not specified.

See also SRFI-1 which extends these functions to take lists of unequal lengths (SRFI-1 Fold and Map).

Vectors
-------

Vectors are sequences of Scheme objects.  Unlike lists, the length of a vector, once the vector is created, cannot be changed.  The advantage of vectors over lists is that the time required to access one element of a vector given its position (synonymous with index), a zero-origin number, is constant, whereas lists have an access time linear to the position of the accessed element in the list.

Vectors can contain any kind of Scheme object; it is even possible to have different types of objects in the same vector.  For vectors containing vectors, you may wish to use arrays, instead.  Note, too, that vectors are the special case of one dimensional non-uniform arrays and that most array procedures operate happily on vectors (see Arrays).

Read Syntax for Vectors
.......................

Vectors can literally be entered in source code, just like strings, characters or some of the other data types.  The read syntax for vectors is as follows: A sharp sign (#), followed by an opening parentheses, all elements of the vector in their respective read syntax, and finally a closing parentheses.  The following are examples of the read syntax for vectors; where the first vector only contains numbers and the second three different object types: a string, a symbol and a number in hexadecimal notation.

     #(1 2 3)
     #("Hello" foo #xdeadbeef)

Like lists, vectors have to be quoted:

     '#(a b c) => #(a b c)

Dynamic Vector Creation and Validation
......................................

Instead of creating a vector implicitly by using the read syntax just described, you can create a vector dynamically by calling one of the vector and list->vector primitives with the list of Scheme values that you want to place into a vector.  The size of the vector thus created is determined implicitly by the number of arguments given.

 -- Scheme Procedure: vector arg ...
 -- Scheme Procedure: list->vector l
 -- C Function: scm_vector (l)
     Return a newly allocated vector composed of the given arguments.  Analogous to list.

          (vector 'a 'b 'c) => #(a b c)

The inverse operation is vector->list:

 -- Scheme Procedure: vector->list v
 -- C Function: scm_vector_to_list (v)
     Return a newly allocated list composed of the elements of V.

          (vector->list '#(dah dah didah)) =>  (dah dah didah)
          (list->vector '(dididit dah)) =>  #(dididit dah)

To allocate a vector with an explicitly specified size, use make-vector.  With this primitive you can also specify an initial value for the vector elements (the same value for all elements, that is):

 -- Scheme Procedure: make-vector len [fill]
 -- C Function: scm_make_vector (len, fill)
     Return a newly allocated vector of LEN elements.  If a second argument is given, then each position is initialized to FILL.  Otherwise the initial contents of each position is unspecified.

 -- C Function: SCM scm_c_make_vector (size_t k, SCM fill)
     Like scm_make_vector, but the length is given as a size_t.

To check whether an arbitrary Scheme value is a vector, use the vector? primitive:

 -- Scheme Procedure: vector? obj
 -- C Function: scm_vector_p (obj)
     Return #t if OBJ is a vector, otherwise return #f.

 -- C Function: int scm_is_vector (SCM obj)
     Return non-zero when OBJ is a vector, otherwise return zero.

Accessing and Modifying Vector Contents
.......................................

vector-length and vector-ref return information about a given vector, respectively its size and the elements that are contained in the vector.

 -- Scheme Procedure: vector-length vector
 -- C Function: scm_vector_length (vector)
     Return the number of elements in VECTOR as an exact integer.

 -- C Function: size_t scm_c_vector_length (SCM vec)
     Return the number of elements in VEC as a size_t.

 -- Scheme Procedure: vector-ref vec k
 -- C Function: scm_vector_ref (vec, k)
     Return the contents of position K of VEC. K must be a valid index of VEC.

          (vector-ref '#(1 1 2 3 5 8 13 21) 5) => 8
          (vector-ref '#(1 1 2 3 5 8 13 21)
              (let ((i (round (* 2 (acos -1)))))
                (if (inexact? i)
                  (inexact->exact i)
                     i))) => 13

 -- C Function: SCM scm_c_vector_ref (SCM vec, size_t k)
     Return the contents of position K (a size_t) of VEC.

A vector created by one of the dynamic vector constructor procedures (see Vector Creation) can be modified using the following procedures.

NOTE: According to R5RS, it is an error to use any of these procedures on a literally read vector, because such vectors should be considered as constants.  Currently, however, Guile does not detect this error.

 -- Scheme Procedure: vector-set! vec k obj
 -- C Function: scm_vector_set_x (vec, k, obj)
     Store OBJ in position K of VEC. K must be a valid index of VEC. The value returned by vector-set! is unspecified.

          (let ((vec (vector 0 '(2 2 2 2) "Anna")))
            (vector-set! vec 1 '("Sue" "Sue"))
            vec) =>  #(0 ("Sue" "Sue") "Anna")

 -- C Function: void scm_c_vector_set_x (SCM vec, size_t k, SCM obj)
     Store OBJ in position K (a size_t) of VEC.

 -- Scheme Procedure: vector-fill! vec fill
 -- C Function: scm_vector_fill_x (vec, fill)
     Store FILL in every position of VEC.  The value returned by vector-fill! is unspecified.

 -- Scheme Procedure: vector-copy vec
 -- C Function: scm_vector_copy (vec)
     Return a copy of VEC.

 -- Scheme Procedure: vector-move-left! vec1 start1 end1 vec2 start2
 -- C Function: scm_vector_move_left_x (vec1, start1, end1, vec2, start2)
     Copy elements from VEC1, positions START1 to END1, to VEC2 starting at position START2.  START1 and START2 are inclusive indices; END1 is exclusive.

     vector-move-left! copies elements in leftmost order. Therefore, in the case where VEC1 and VEC2 refer to the same vector, vector-move-left! is usually appropriate when START1 is greater than START2.

 -- Scheme Procedure: vector-move-right! vec1 start1 end1 vec2 start2
 -- C Function: scm_vector_move_right_x (vec1, start1, end1, vec2, start2)
     Copy elements from VEC1, positions START1 to END1, to VEC2 starting at position START2.  START1 and START2 are inclusive indices; END1 is exclusive.

     vector-move-right! copies elements in rightmost order. Therefore, in the case where VEC1 and VEC2 refer to the same vector, vector-move-right! is usually appropriate when START1 is less than START2.

Vector Accessing from C
.......................

A vector can be read and modified from C with the functions scm_c_vector_ref and scm_c_vector_set_x, for example.  In addition to these functions, there are two more ways to access vectors from C that might be more efficient in certain situations: you can restrict yourself to simple vectors and then use the very fast simple vector macros; or you can use the very general framework for accessing all kinds of arrays (see Accessing Arrays from C), which is more verbose, but can deal efficiently with all kinds of vectors (and arrays).  For vectors, you can use the scm_vector_elements and scm_vector_writable_elements functions as shortcuts.

 -- C Function: int scm_is_simple_vector (SCM obj)
     Return non-zero if OBJ is a simple vector, else return zero.  A simple vector is a vector that can be used with the SCM_SIMPLE_* macros below.

     The following functions are guaranteed to return simple vectors: scm_make_vector, scm_c_make_vector, scm_vector, scm_list_to_vector.

 -- C Macro: size_t SCM_SIMPLE_VECTOR_LENGTH (SCM vec)
     Evaluates to the length of the simple vector VEC.  No type checking is done.

 -- C Macro: SCM SCM_SIMPLE_VECTOR_REF (SCM vec, size_t idx)
     Evaluates to the element at position IDX in the simple vector VEC.  No type or range checking is done.

 -- C Macro: void SCM_SIMPLE_VECTOR_SET (SCM vec, size_t idx, SCM val)
     Sets the element at position IDX in the simple vector VEC to VAL.  No type or range checking is done.

 -- C Function: const SCM * scm_vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
     Acquire a handle for the vector VEC and return a pointer to the elements of it.  This pointer can only be used to read the elements of VEC.  When VEC is not a vector, an error is signaled.  The handle must eventually be released with scm_array_handle_release.

     The variables pointed to by LENP and INCP are filled with the number of elements of the vector and the increment (number of elements) between successive elements, respectively.  Successive elements of VEC need not be contiguous in their underlying ``root vector'' returned here; hence the increment is not necessarily equal to 1 and may well be negative too (see Shared Arrays).

     The following example shows the typical way to use this function.  It creates a list of all elements of VEC (in reverse order).

          scm_t_array_handle handle;
          size_t i, len;
          ssize_t inc;
          const SCM *elt;
          SCM list;

          elt = scm_vector_elements (vec, &handle, &len, &inc);
          list = SCM_EOL;
          for (i = 0; i < len; i++, elt += inc)
            list = scm_cons (*elt, list);
          scm_array_handle_release (&handle);

 -- C Function: SCM * scm_vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
     Like scm_vector_elements but the pointer can be used to modify the vector.

     The following example shows the typical way to use this function.  It fills a vector with #t.

          scm_t_array_handle handle;
          size_t i, len;
          ssize_t inc;
          SCM *elt;

          elt = scm_vector_writable_elements (vec, &handle, &len, &inc);
          for (i = 0; i < len; i++, elt += inc)
            *elt = SCM_BOOL_T;
          scm_array_handle_release (&handle);

Uniform Numeric Vectors
.......................

A uniform numeric vector is a vector whose elements are all of a single numeric type.  Guile offers uniform numeric vectors for signed and unsigned 8-bit, 16-bit, 32-bit, and 64-bit integers, two sizes of floating point values, and complex floating-point numbers of these two sizes. See SRFI-4, for more information.

For many purposes, bytevectors work just as well as uniform vectors, and have the advantage that they integrate well with binary input and output. See Bytevectors, for more information on bytevectors.

Bit Vectors
-----------

Bit vectors are zero-origin, one-dimensional arrays of booleans.  They are displayed as a sequence of 0s and 1s prefixed by #*, e.g.,

     (make-bitvector 8 #f) =>
     #*00000000

Bit vectors are also generalized vectors, see Generalized Vectors, and can thus be used with the array procedures, see Arrays. Bit vectors are the special case of one dimensional bit arrays.

 -- Scheme Procedure: bitvector? obj
 -- C Function: scm_bitvector_p (obj)
     Return #t when OBJ is a bitvector, else return #f.

 -- C Function: int scm_is_bitvector (SCM obj)
     Return 1 when OBJ is a bitvector, else return 0.

 -- Scheme Procedure: make-bitvector len [fill]
 -- C Function: scm_make_bitvector (len, fill)
     Create a new bitvector of length LEN and optionally initialize all elements to FILL.

 -- C Function: SCM scm_c_make_bitvector (size_t len, SCM fill)
     Like scm_make_bitvector, but the length is given as a size_t.

 -- Scheme Procedure: bitvector bit ...
 -- C Function: scm_bitvector (bits)
     Create a new bitvector with the arguments as elements.

 -- Scheme Procedure: bitvector-length vec
 -- C Function: scm_bitvector_length (vec)
     Return the length of the bitvector VEC.

 -- C Function: size_t scm_c_bitvector_length (SCM vec)
     Like scm_bitvector_length, but the length is returned as a size_t.

 -- Scheme Procedure: bitvector-ref vec idx
 -- C Function: scm_bitvector_ref (vec, idx)
     Return the element at index IDX of the bitvector VEC.

 -- C Function: SCM scm_c_bitvector_ref (SCM vec, size_t idx)
     Return the element at index IDX of the bitvector VEC.

 -- Scheme Procedure: bitvector-set! vec idx val
 -- C Function: scm_bitvector_set_x (vec, idx, val)
     Set the element at index IDX of the bitvector VEC when VAL is true, else clear it.

 -- C Function: SCM scm_c_bitvector_set_x (SCM vec, size_t idx, SCM val)
     Set the element at index IDX of the bitvector VEC when VAL is true, else clear it.

 -- Scheme Procedure: bitvector-fill! vec val
 -- C Function: scm_bitvector_fill_x (vec, val)
     Set all elements of the bitvector VEC when VAL is true, else clear them.

 -- Scheme Procedure: list->bitvector list
 -- C Function: scm_list_to_bitvector (list)
     Return a new bitvector initialized with the elements of LIST.

 -- Scheme Procedure: bitvector->list vec
 -- C Function: scm_bitvector_to_list (vec)
     Return a new list initialized with the elements of the bitvector VEC.

 -- Scheme Procedure: bit-count bool bitvector
 -- C Function: scm_bit_count (bool, bitvector)
     Return a count of how many entries in BITVECTOR are equal to BOOL.  For example,

          (bit-count #f #*000111000)  => 6

 -- Scheme Procedure: bit-position bool bitvector start
 -- C Function: scm_bit_position (bool, bitvector, start)
     Return the index of the first occurrence of BOOL in BITVECTOR, starting from START.  If there is no BOOL entry between START and the end of BITVECTOR, then return #f.  For example,

          (bit-position #t #*000101 0)  => 3
          (bit-position #f #*0001111 3) => #f

 -- Scheme Procedure: bit-invert! bitvector
 -- C Function: scm_bit_invert_x (bitvector)
     Modify BITVECTOR by replacing each element with its negation.

 -- Scheme Procedure: bit-set*! bitvector uvec bool
 -- C Function: scm_bit_set_star_x (bitvector, uvec, bool)
     Set entries of BITVECTOR to BOOL, with UVEC selecting the entries to change.  The return value is unspecified.

     If UVEC is a bit vector, then those entries where it has #t are the ones in BITVECTOR which are set to BOOL. UVEC and BITVECTOR must be the same length.  When BOOL is #t it's like UVEC is OR'ed into BITVECTOR.  Or when BOOL is #f it can be seen as an ANDNOT.

          (define bv #*01000010)
          (bit-set*! bv #*10010001 #t)
          bv
          => #*11010011

     If UVEC is a uniform vector of unsigned long integers, then they're indexes into BITVECTOR which are set to BOOL.

          (define bv #*01000010)
          (bit-set*! bv #u(5 2 7) #t)
          bv
          => #*01100111

 -- Scheme Procedure: bit-count* bitvector uvec bool
 -- C Function: scm_bit_count_star (bitvector, uvec, bool)
     Return a count of how many entries in BITVECTOR are equal to BOOL, with UVEC selecting the entries to consider.

     UVEC is interpreted in the same way as for bit-set*! above.  Namely, if UVEC is a bit vector then entries which have #t there are considered in BITVECTOR.  Or if UVEC is a uniform vector of unsigned long integers then it's the indexes in BITVECTOR to consider.

     For example,

          (bit-count* #*01110111 #*11001101 #t) => 3
          (bit-count* #*01110111 #u(7 0 4) #f)  => 2

 -- 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)
     Like scm_vector_elements (see Vector Accessing from C), but for bitvectors.  The variable pointed to by OFFP is set to the value returned by scm_array_handle_bit_elements_offset.  See scm_array_handle_bit_elements for how to use the returned pointer and the offset.

 -- 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)
     Like scm_bitvector_elements, but the pointer is good for reading and writing.

Generalized Vectors
-------------------

Guile has a number of data types that are generally vector-like: strings, uniform numeric vectors, bytevectors, bitvectors, and of course ordinary vectors of arbitrary Scheme values.  These types are disjoint: a Scheme value belongs to at most one of the five types listed above.

If you want to gloss over this distinction and want to treat all four types with common code, you can use the procedures in this section. They work with the generalized vector type, which is the union of the five vector-like types.

 -- Scheme Procedure: generalized-vector? obj
 -- C Function: scm_generalized_vector_p (obj)
     Return #t if OBJ is a vector, bytevector, string, bitvector, or uniform numeric vector.

 -- Scheme Procedure: generalized-vector-length v
 -- C Function: scm_generalized_vector_length (v)
     Return the length of the generalized vector V.

 -- Scheme Procedure: generalized-vector-ref v idx
 -- C Function: scm_generalized_vector_ref (v, idx)
     Return the element at index IDX of the generalized vector V.

 -- Scheme Procedure: generalized-vector-set! v idx val
 -- C Function: scm_generalized_vector_set_x (v, idx, val)
     Set the element at index IDX of the generalized vector V to VAL.

 -- Scheme Procedure: generalized-vector->list v
 -- C Function: scm_generalized_vector_to_list (v)
     Return a new list whose elements are the elements of the generalized vector V.

 -- C Function: int scm_is_generalized_vector (SCM obj)
     Return 1 if OBJ is a vector, string, bitvector, or uniform numeric vector; else return 0.

 -- C Function: size_t scm_c_generalized_vector_length (SCM v)
     Return the length of the generalized vector V.

 -- C Function: SCM scm_c_generalized_vector_ref (SCM v, size_t idx)
     Return the element at index IDX of the generalized vector V.

 -- C Function: void scm_c_generalized_vector_set_x (SCM v, size_t idx, SCM val)
     Set the element at index IDX of the generalized vector V to VAL.

 -- C Function: void scm_generalized_vector_get_handle (SCM v, scm_t_array_handle *handle)
     Like scm_array_get_handle but an error is signalled when V is not of rank one.  You can use scm_array_handle_ref and scm_array_handle_set to read and write the elements of V, or you can use functions like scm_array_handle_<foo>_elements to deal with specific types of vectors.

Arrays
------

Arrays are a collection of cells organized into an arbitrary number of dimensions.  Each cell can be accessed in constant time by supplying an index for each dimension.

In the current implementation, an array uses a generalized vector for the actual storage of its elements.  Any kind of generalized vector will do, so you can have arrays of uniform numeric values, arrays of characters, arrays of bits, and of course, arrays of arbitrary Scheme values.  For example, arrays with an underlying c64vector might be nice for digital signal processing, while arrays made from a u8vector might be used to hold gray-scale images.

The number of dimensions of an array is called its rank.  Thus, a matrix is an array of rank 2, while a vector has rank 1.  When accessing an array element, you have to specify one exact integer for each dimension.  These integers are called the indices of the element.  An array specifies the allowed range of indices for each dimension via an inclusive lower and upper bound.  These bounds can well be negative, but the upper bound must be greater than or equal to the lower bound minus one.  When all lower bounds of an array are zero, it is called a zero-origin array.

Arrays can be of rank 0, which could be interpreted as a scalar. Thus, a zero-rank array can store exactly one object and the list of indices of this element is the empty list.

Arrays contain zero elements when one of their dimensions has a zero length.  These empty arrays maintain information about their shape: a matrix with zero columns and 3 rows is different from a matrix with 3 columns and zero rows, which again is different from a vector of length zero.

Generalized vectors, such as strings, uniform numeric vectors, bytevectors, bit vectors and ordinary vectors, are the special case of one dimensional arrays.

Array Syntax
............

An array is displayed as # followed by its rank, followed by a tag that describes the underlying vector, optionally followed by information about its shape, and finally followed by the cells, organized into dimensions using parentheses.

In more words, the array tag is of the form

       #<rank><vectag><@lower><:len><@lower><:len>...

where <rank> is a positive integer in decimal giving the rank of the array.  It is omitted when the rank is 1 and the array is non-shared and has zero-origin (see below).  For shared arrays and for a non-zero origin, the rank is always printed even when it is 1 to distinguish them from ordinary vectors.

The <vectag> part is the tag for a uniform numeric vector, like u8, s16, etc, b for bitvectors, or a for strings.  It is empty for ordinary vectors.

The <@lower> part is a @ character followed by a signed integer in decimal giving the lower bound of a dimension.  There is one <@lower> for each dimension.  When all lower bounds are zero, all <@lower> parts are omitted.

The <:len> part is a : character followed by an unsigned integer in decimal giving the length of a dimension.  Like for the lower bounds, there is one <:len> for each dimension, and the <:len> part always follows the <@lower> part for a dimension.  Lengths are only then printed when they can't be deduced from the nested lists of elements of the array literal, which can happen when at least one length is zero.

As a special case, an array of rank 0 is printed as #0<vectag>(<scalar>), where <scalar> is the result of printing the single element of the array.

Thus,

#(1 2 3)
     is an ordinary array of rank 1 with lower bound 0 in dimension 0. (I.e., a regular vector.)

#@2(1 2 3)
     is an ordinary array of rank 1 with lower bound 2 in dimension 0.

#2((1 2 3) (4 5 6))
     is a non-uniform array of rank 2; a 3 cross3 matrix with index ranges 0..2 and 0..2.

#u32(0 1 2)
     is a uniform u8 array of rank 1.

#2u32@2@3((1 2) (2 3))
     is a uniform u8 array of rank 2 with index ranges 2..3 and 3..4.

#2()
     is a two-dimensional array with index ranges 0..-1 and 0..-1, i.e. both dimensions have length zero.

#2:0:2()
     is a two-dimensional array with index ranges 0..-1 and 0..1, i.e. the first dimension has length zero, but the second has length 2.

#0(12)
     is a rank-zero array with contents 12.

In addition, bytevectors are also arrays, but use a different syntax (see Bytevectors):

#vu8(1 2 3)
     is a 3-byte long bytevector, with contents 1, 2, 3.

Array Procedures
................

When an array is created, the range of each dimension must be specified, e.g., to create a 2 cross3 array with a zero-based index:

     (make-array 'ho 2 3) => #2((ho ho ho) (ho ho ho))

The range of each dimension can also be given explicitly, e.g., another way to create the same array:

     (make-array 'ho '(0 1) '(0 2)) => #2((ho ho ho) (ho ho ho))

The following procedures can be used with arrays (or vectors).  An argument shown as IDX... means one parameter for each dimension in the array.  A IDXLIST argument means a list of such values, one for each dimension.

 -- Scheme Procedure: array? obj
 -- C Function: scm_array_p (obj, unused)
     Return #t if the OBJ is an array, and #f if not.

     The second argument to scm_array_p is there for historical reasons, but it is not used.  You should always pass SCM_UNDEFINED as its value.

 -- Scheme Procedure: typed-array? obj type
 -- C Function: scm_typed_array_p (obj, type)
     Return #t if the OBJ is an array of type TYPE, and #f if not.

 -- C Function: int scm_is_array (SCM obj)
     Return 1 if the OBJ is an array and 0 if not.

 -- C Function: int scm_is_typed_array (SCM obj, SCM type)
     Return 0 if the OBJ is an array of type TYPE, and 1 if not.

 -- Scheme Procedure: make-array fill bound ...
 -- C Function: scm_make_array (fill, bounds)
     Equivalent to (make-typed-array #t FILL BOUND ...).

 -- Scheme Procedure: make-typed-array type fill bound ...
 -- C Function: scm_make_typed_array (type, fill, bounds)
     Create and return an array that has as many dimensions as there are BOUNDs and (maybe) fill it with FILL.

     The underlying storage vector is created according to TYPE, which must be a symbol whose name is the `vectag' of the array as explained above, or #t for ordinary, non-specialized arrays.

     For example, using the symbol f64 for TYPE will create an array that uses a f64vector for storing its elements, and a will use a string.

     When FILL is not the special unspecified value, the new array is filled with FILL.  Otherwise, the initial contents of the array is unspecified.  The special unspecified value is stored in the variable *unspecified* so that for example (make-typed-array 'u32 *unspecified* 4) creates a uninitialized u32 vector of length 4.

     Each BOUND may be a positive non-zero integer N, in which case the index for that dimension can range from 0 through N-1; or an explicit index range specifier in the form (LOWER UPPER), where both LOWER and UPPER are integers, possibly less than zero, and possibly the same number (however, LOWER cannot be greater than UPPER).

 -- Scheme Procedure: list->array dimspec list
     Equivalent to (list->typed-array #t DIMSPEC LIST).

 -- Scheme Procedure: list->typed-array type dimspec list
 -- C Function: scm_list_to_typed_array (type, dimspec, list)
     Return an array of the type indicated by TYPE with elements the same as those of LIST.

     The argument DIMSPEC determines the number of dimensions of the array and their lower bounds.  When DIMSPEC is an exact integer, it gives the number of dimensions directly and all lower bounds are zero.  When it is a list of exact integers, then each element is the lower index bound of a dimension, and there will be as many dimensions as elements in the list.

 -- Scheme Procedure: array-type array
     Return the type of ARRAY.  This is the `vectag' used for printing ARRAY (or #t for ordinary arrays) and can be used with make-typed-array to create an array of the same kind as ARRAY.

 -- Scheme Procedure: array-ref array idx ...
     Return the element at (idx ...) in ARRAY.

          (define a (make-array 999 '(1 2) '(3 4)))
          (array-ref a 2 4) => 999

 -- Scheme Procedure: array-in-bounds? array idx ...
 -- C Function: scm_array_in_bounds_p (array, idxlist)
     Return #t if the given index would be acceptable to array-ref.

          (define a (make-array #f '(1 2) '(3 4)))
          (array-in-bounds? a 2 3) => #t
          (array-in-bounds? a 0 0) => #f

 -- Scheme Procedure: array-set! array obj idx ...
 -- C Function: scm_array_set_x (array, obj, idxlist)
     Set the element at (idx ...) in ARRAY to OBJ. The return value is unspecified.

          (define a (make-array #f '(0 1) '(0 1)))
          (array-set! a #t 1 1)
          a => #2((#f #f) (#f #t))

 -- Scheme Procedure: array-shape array
 -- Scheme Procedure: array-dimensions array
 -- C Function: scm_array_dimensions (array)
     Return a list of the bounds for each dimension of ARRAY.

     array-shape gives (LOWER UPPER) for each dimension.  array-dimensions instead returns just UPPER+1 for dimensions with a 0 lower bound.  Both are suitable as input to make-array.

     For example,

          (define a (make-array 'foo '(-1 3) 5))
          (array-shape a)      => ((-1 3) (0 4))
          (array-dimensions a) => ((-1 3) 5)

 -- Scheme Procedure: array-rank array
 -- C Function: scm_array_rank (array)
     Return the rank of ARRAY.

 -- C Function: size_t scm_c_array_rank (SCM array)
     Return the rank of ARRAY as a size_t.

 -- Scheme Procedure: array->list array
 -- C Function: scm_array_to_list (array)
     Return a list consisting of all the elements, in order, of ARRAY.

 -- Scheme Procedure: array-copy! src dst
 -- Scheme Procedure: array-copy-in-order! src dst
 -- C Function: scm_array_copy_x (src, dst)
     Copy every element from vector or array SRC to the corresponding element of DST.  DST must have the same rank as SRC, and be at least as large in each dimension.  The return value is unspecified.

 -- Scheme Procedure: array-fill! array fill
 -- C Function: scm_array_fill_x (array, fill)
     Store FILL in every element of ARRAY.  The value returned is unspecified.

 -- Scheme Procedure: array-equal? array ...
     Return #t if all arguments are arrays with the same shape, the same type, and have corresponding elements which are either equal? or array-equal?.  This function differs from equal? (see Equality) in that all arguments must be arrays.

 -- Scheme Procedure: array-map! dst proc src ...
 -- Scheme Procedure: array-map-in-order! dst proc src1 ... srcN
 -- C Function: scm_array_map_x (dst, proc, srclist)
     Set each element of the DST array to values obtained from calls to PROC.  The value returned is unspecified.

     Each call is (PROC ELEM1 ... ELEMN), where each ELEM is from the corresponding SRC array, at the DST index.  array-map-in-order! makes the calls in row-major order, array-map! makes them in an unspecified order.

     The SRC arrays must have the same number of dimensions as DST, and must have a range for each dimension which covers the range in DST.  This ensures all DST indices are valid in each SRC.

 -- Scheme Procedure: array-for-each proc src1 src2 ...
 -- C Function: scm_array_for_each (proc, src1, srclist)
     Apply PROC to each tuple of elements of SRC1 SRC2 ..., in row-major order.  The value returned is unspecified.

 -- Scheme Procedure: array-index-map! dst proc
 -- C Function: scm_array_index_map_x (dst, proc)
     Set each element of the DST array to values returned by calls to PROC.  The value returned is unspecified.

     Each call is (PROC I1 ... IN), where I1...IN is the destination index, one parameter for each dimension.  The order in which the calls are made is unspecified.

     For example, to create a 4\times4, 4x4 matrix representing a cyclic group,

              / 0 1 2 3 \
              | 1 2 3 0 |
              | 2 3 0 1 |
              \ 3 0 1 2 /

          (define a (make-array #f 4 4))
          (array-index-map! a (lambda (i j)
                                (modulo (+ i j) 4)))

 -- Scheme Procedure: uniform-array-read! ra [port_or_fd [start [end]]]
 -- C Function: scm_uniform_array_read_x (ra, port_or_fd, start, end)
     Attempt to read all elements of array RA, in lexicographic order, as binary objects from PORT_OR_FD. If an end of file is encountered, the objects up to that point are put into RA (starting at the beginning) and the remainder of the array is unchanged.

     The optional arguments START and END allow a specified region of a vector (or linearized array) to be read, leaving the remainder of the vector unchanged.

     uniform-array-read! returns the number of objects read. PORT_OR_FD may be omitted, in which case it defaults to the value returned by (current-input-port).

 -- Scheme Procedure: uniform-array-write ra [port_or_fd [start [end]]]
 -- C Function: scm_uniform_array_write (ra, port_or_fd, start, end)
     Writes all elements of RA as binary objects to PORT_OR_FD.

     The optional arguments START and END allow a specified region of a vector (or linearized array) to be written.

     The number of objects actually written is returned. PORT_OR_FD may be omitted, in which case it defaults to the value returned by (current-output-port).

Shared Arrays
.............

 -- Scheme Procedure: make-shared-array oldarray mapfunc bound ...
 -- C Function: scm_make_shared_array (oldarray, mapfunc, boundlist)
     Return a new array which shares the storage of OLDARRAY. Changes made through either affect the same underlying storage.  The BOUND ... arguments are the shape of the new array, the same as make-array (see Array Procedures).

     MAPFUNC translates coordinates from the new array to the OLDARRAY.  It's called as (MAPFUNC newidx1 ...) with one parameter for each dimension of the new array, and should return a list of indices for OLDARRAY, one for each dimension of OLDARRAY.

     MAPFUNC must be affine linear, meaning that each OLDARRAY index must be formed by adding integer multiples (possibly negative) of some or all of NEWIDX1 etc, plus a possible integer offset. The multiples and offset must be the same in each call.

     One good use for a shared array is to restrict the range of some dimensions, so as to apply say array-for-each or array-fill! to only part of an array.  The plain list function can be used for MAPFUNC in this case, making no changes to the index values.  For example,

          (make-shared-array #2((a b c) (d e f) (g h i)) list 3 2)
          => #2((a b) (d e) (g h))

     The new array can have fewer dimensions than OLDARRAY, for example to take a column from an array.

          (make-shared-array #2((a b c) (d e f) (g h i))
                             (lambda (i) (list i 2))
                             '(0 2))
          => #1(c f i)

     A diagonal can be taken by using the single new array index for both row and column in the old array.  For example,

          (make-shared-array #2((a b c) (d e f) (g h i))
                             (lambda (i) (list i i))
                             '(0 2))
          => #1(a e i)

     Dimensions can be increased by for instance considering portions of a one dimensional array as rows in a two dimensional array. (array-contents below can do the opposite, flattening an array.)

          (make-shared-array #1(a b c d e f g h i j k l)
                             (lambda (i j) (list (+ (* i 3) j)))
                             4 3)
          => #2((a b c) (d e f) (g h i) (j k l))

     By negating an index the order that elements appear can be reversed. The following just reverses the column order,

          (make-shared-array #2((a b c) (d e f) (g h i))
                             (lambda (i j) (list i (- 2 j)))
                             3 3)
          => #2((c b a) (f e d) (i h g))

     A fixed offset on indexes allows for instance a change from a 0 based to a 1 based array,

          (define x #2((a b c) (d e f) (g h i)))
          (define y (make-shared-array x
                                       (lambda (i j) (list (1- i) (1- j)))
                                       '(1 3) '(1 3)))
          (array-ref x 0 0) => a
          (array-ref y 1 1) => a

     A multiple on an index allows every Nth element of an array to be taken.  The following is every third element,

          (make-shared-array #1(a b c d e f g h i j k l)
                             (lambda (i) (list (* i 3)))
                             4)
          => #1(a d g j)

     The above examples can be combined to make weird and wonderful selections from an array, but it's important to note that because MAPFUNC must be affine linear, arbitrary permutations are not possible.

     In the current implementation, MAPFUNC is not called for every access to the new array but only on some sample points to establish a base and stride for new array indices in OLDARRAY data.  A few sample points are enough because MAPFUNC is linear.

 -- Scheme Procedure: shared-array-increments array
 -- C Function: scm_shared_array_increments (array)
     For each dimension, return the distance between elements in the root vector.

 -- Scheme Procedure: shared-array-offset array
 -- C Function: scm_shared_array_offset (array)
     Return the root vector index of the first element in the array.

 -- Scheme Procedure: shared-array-root array
 -- C Function: scm_shared_array_root (array)
     Return the root vector of a shared array.

 -- Scheme Procedure: array-contents array [strict]
 -- C Function: scm_array_contents (array, strict)
     If ARRAY may be unrolled into a one dimensional shared array without changing their order (last subscript changing fastest), then array-contents returns that shared array, otherwise it returns #f.  All arrays made by make-array and make-typed-array may be unrolled, some arrays made by make-shared-array may not be.

     If the optional argument STRICT is provided, a shared array will be returned only if its elements are stored internally contiguous in memory.

 -- Scheme Procedure: transpose-array array dim1 dim2 ...
 -- C Function: scm_transpose_array (array, dimlist)
     Return an array sharing contents with ARRAY, but with dimensions arranged in a different order.  There must be one DIM argument for each dimension of ARRAY. DIM1, DIM2, ... should be integers between 0 and the rank of the array to be returned.  Each integer in that range must appear at least once in the argument list.

     The values of DIM1, DIM2, ... correspond to dimensions in the array to be returned, and their positions in the argument list to dimensions of ARRAY.  Several DIMs may have the same value, in which case the returned array will have smaller rank than ARRAY.

          (transpose-array '#2((a b) (c d)) 1 0) => #2((a c) (b d))
          (transpose-array '#2((a b) (c d)) 0 0) => #1(a d)
          (transpose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 1 0) =>
                          #2((a 4) (b 5) (c 6))

Accessing Arrays from C
.......................

For interworking with external C code, Guile provides an API to allow C code to access the elements of a Scheme array.  In particular, for uniform numeric arrays, the API exposes the underlying uniform data as a C array of numbers of the relevant type.

While pointers to the elements of an array are in use, the array itself must be protected so that the pointer remains valid.  Such a protected array is said to be reserved.  A reserved array can be read but modifications to it that would cause the pointer to its elements to become invalid are prevented.  When you attempt such a modification, an error is signalled.

(This is similar to locking the array while it is in use, but without the danger of a deadlock.  In a multi-threaded program, you will need additional synchronization to avoid modifying reserved arrays.)

You must take care to always unreserve an array after reserving it, even in the presence of non-local exits.  If a non-local exit can happen between these two calls, you should install a dynwind context that releases the array when it is left (see Dynamic Wind).

In addition, array reserving and unreserving must be properly paired.  For instance, when reserving two or more arrays in a certain order, you need to unreserve them in the opposite order.

Once you have reserved an array and have retrieved the pointer to its elements, you must figure out the layout of the elements in memory. Guile allows slices to be taken out of arrays without actually making a copy, such as making an alias for the diagonal of a matrix that can be treated as a vector.  Arrays that result from such an operation are not stored contiguously in memory and when working with their elements directly, you need to take this into account.

The layout of array elements in memory can be defined via a mapping function that computes a scalar position from a vector of indices.  The scalar position then is the offset of the element with the given indices from the start of the storage block of the array.

In Guile, this mapping function is restricted to be affine: all mapping functions of Guile arrays can be written as p = b + c[0]*i[0] + c[1]*i[1] + ... + c[n-1]*i[n-1] where i[k] is the kth index and n is the rank of the array.  For example, a matrix of size 3x3 would have b == 0, c[0] == 3 and c[1] == 1.  When you transpose this matrix (with transpose-array, say), you will get an array whose mapping function has b == 0, c[0] == 1 and c[1] == 3.

The function scm_array_handle_dims gives you (indirect) access to the coefficients c[k].

Note that there are no functions for accessing the elements of a character array yet.  Once the string implementation of Guile has been changed to use Unicode, we will provide them.

 -- C Type: scm_t_array_handle
     This is a structure type that holds all information necessary to manage the reservation of arrays as explained above.  Structures of this type must be allocated on the stack and must only be accessed by the functions listed below.

 -- C Function: void scm_array_get_handle (SCM array, scm_t_array_handle *handle)
     Reserve ARRAY, which must be an array, and prepare HANDLE to be used with the functions below.  You must eventually call scm_array_handle_release on HANDLE, and do this in a properly nested fashion, as explained above.  The structure pointed to by HANDLE does not need to be initialized before calling this function.

 -- C Function: void scm_array_handle_release (scm_t_array_handle *handle)
     End the array reservation represented by HANDLE.  After a call to this function, HANDLE might be used for another reservation.

 -- C Function: size_t scm_array_handle_rank (scm_t_array_handle *handle)
     Return the rank of the array represented by HANDLE.

 -- C Type: scm_t_array_dim
     This structure type holds information about the layout of one dimension of an array.  It includes the following fields:

     ssize_t lbnd
     ssize_t ubnd
          The lower and upper bounds (both inclusive) of the permissible index range for the given dimension.  Both values can be negative, but LBND is always less than or equal to UBND.

     ssize_t inc
          The distance from one element of this dimension to the next.  Note, too, that this can be negative.

 -- C Function: const scm_t_array_dim * scm_array_handle_dims (scm_t_array_handle *handle)
     Return a pointer to a C vector of information about the dimensions of the array represented by HANDLE.  This pointer is valid as long as the array remains reserved.  As explained above, the scm_t_array_dim structures returned by this function can be used calculate the position of an element in the storage block of the array from its indices.

     This position can then be used as an index into the C array pointer returned by the various scm_array_handle_<foo>_elements functions, or with scm_array_handle_ref and scm_array_handle_set.

     Here is how one can compute the position POS of an element given its indices in the vector INDICES:

          ssize_t indices[RANK];
          scm_t_array_dim *dims;
          ssize_t pos;
          size_t i;

          pos = 0;
          for (i = 0; i < RANK; i++)
            {
              if (indices[i] < dims[i].lbnd || indices[i] > dims[i].ubnd)
                out_of_range ();
              pos += (indices[i] - dims[i].lbnd) * dims[i].inc;
            }

 -- C Function: ssize_t scm_array_handle_pos (scm_t_array_handle *handle, SCM indices)
     Compute the position corresponding to INDICES, a list of indices.  The position is computed as described above for scm_array_handle_dims.  The number of the indices and their range is checked and an appropriate error is signalled for invalid indices.

 -- C Function: SCM scm_array_handle_ref (scm_t_array_handle *handle, ssize_t pos)
     Return the element at position POS in the storage block of the array represented by HANDLE.  Any kind of array is acceptable.  No range checking is done on POS.

 -- C Function: void scm_array_handle_set (scm_t_array_handle *handle, ssize_t pos, SCM val)
     Set the element at position POS in the storage block of the array represented by HANDLE to VAL.  Any kind of array is acceptable.  No range checking is done on POS.  An error is signalled when the array can not store VAL.

 -- C Function: const SCM * scm_array_handle_elements (scm_t_array_handle *handle)
     Return a pointer to the elements of a ordinary array of general Scheme values (i.e., a non-uniform array) for reading.  This pointer is valid as long as the array remains reserved.

 -- C Function: SCM * scm_array_handle_writable_elements (scm_t_array_handle *handle)
     Like scm_array_handle_elements, but the pointer is good for reading and writing.

 -- C Function: const void * scm_array_handle_uniform_elements (scm_t_array_handle *handle)
     Return a pointer to the elements of a uniform numeric array for reading. This pointer is valid as long as the array remains reserved.  The size of each element is given by scm_array_handle_uniform_element_size.

 -- C Function: void * scm_array_handle_uniform_writable_elements (scm_t_array_handle *handle)
     Like scm_array_handle_uniform_elements, but the pointer is good reading and writing.

 -- C Function: size_t scm_array_handle_uniform_element_size (scm_t_array_handle *handle)
     Return the size of one element of the uniform numeric array represented by HANDLE.

 -- C Function: const scm_t_uint8 * scm_array_handle_u8_elements (scm_t_array_handle *handle)
 -- C Function: const scm_t_int8 * scm_array_handle_s8_elements (scm_t_array_handle *handle)
 -- C Function: const scm_t_uint16 * scm_array_handle_u16_elements (scm_t_array_handle *handle)
 -- C Function: const scm_t_int16 * scm_array_handle_s16_elements (scm_t_array_handle *handle)
 -- C Function: const scm_t_uint32 * scm_array_handle_u32_elements (scm_t_array_handle *handle)
 -- C Function: const scm_t_int32 * scm_array_handle_s32_elements (scm_t_array_handle *handle)
 -- C Function: const scm_t_uint64 * scm_array_handle_u64_elements (scm_t_array_handle *handle)
 -- C Function: const scm_t_int64 * scm_array_handle_s64_elements (scm_t_array_handle *handle)
 -- C Function: const float * scm_array_handle_f32_elements (scm_t_array_handle *handle)
 -- C Function: const double * scm_array_handle_f64_elements (scm_t_array_handle *handle)
 -- C Function: const float * scm_array_handle_c32_elements (scm_t_array_handle *handle)
 -- C Function: const double * scm_array_handle_c64_elements (scm_t_array_handle *handle)
     Return a pointer to the elements of a uniform numeric array of the indicated kind for reading.  This pointer is valid as long as the array remains reserved.

     The pointers for c32 and c64 uniform numeric arrays point to pairs of floating point numbers.  The even index holds the real part, the odd index the imaginary part of the complex number.

 -- C Function: scm_t_uint8 * scm_array_handle_u8_writable_elements (scm_t_array_handle *handle)
 -- C Function: scm_t_int8 * scm_array_handle_s8_writable_elements (scm_t_array_handle *handle)
 -- C Function: scm_t_uint16 * scm_array_handle_u16_writable_elements (scm_t_array_handle *handle)
 -- C Function: scm_t_int16 * scm_array_handle_s16_writable_elements (scm_t_array_handle *handle)
 -- C Function: scm_t_uint32 * scm_array_handle_u32_writable_elements (scm_t_array_handle *handle)
 -- C Function: scm_t_int32 * scm_array_handle_s32_writable_elements (scm_t_array_handle *handle)
 -- C Function: scm_t_uint64 * scm_array_handle_u64_writable_elements (scm_t_array_handle *handle)
 -- C Function: scm_t_int64 * scm_array_handle_s64_writable_elements (scm_t_array_handle *handle)
 -- C Function: float * scm_array_handle_f32_writable_elements (scm_t_array_handle *handle)
 -- C Function: double * scm_array_handle_f64_writable_elements (scm_t_array_handle *handle)
 -- C Function: float * scm_array_handle_c32_writable_elements (scm_t_array_handle *handle)
 -- C Function: double * scm_array_handle_c64_writable_elements (scm_t_array_handle *handle)
     Like scm_array_handle_<kind>_elements, but the pointer is good for reading and writing.

 -- C Function: const scm_t_uint32 * scm_array_handle_bit_elements (scm_t_array_handle *handle)
     Return a pointer to the words that store the bits of the represented array, which must be a bit array.

     Unlike other arrays, bit arrays have an additional offset that must be figured into index calculations.  That offset is returned by scm_array_handle_bit_elements_offset.

     To find a certain bit you first need to calculate its position as explained above for scm_array_handle_dims and then add the offset.  This gives the absolute position of the bit, which is always a non-negative integer.

     Each word of the bit array storage block contains exactly 32 bits, with the least significant bit in that word having the lowest absolute position number.  The next word contains the next 32 bits.

     Thus, the following code can be used to access a bit whose position according to scm_array_handle_dims is given in POS:

          SCM bit_array;
          scm_t_array_handle handle;
          scm_t_uint32 *bits;
          ssize_t pos;
          size_t abs_pos;
          size_t word_pos, mask;

          scm_array_get_handle (&bit_array, &handle);
          bits = scm_array_handle_bit_elements (&handle);

          pos = ...
          abs_pos = pos + scm_array_handle_bit_elements_offset (&handle);
          word_pos = abs_pos / 32;
          mask = 1L << (abs_pos % 32);

          if (bits[word_pos] & mask)
            /* bit is set. */

          scm_array_handle_release (&handle);

 -- C Function: scm_t_uint32 * scm_array_handle_bit_writable_elements (scm_t_array_handle *handle)
     Like scm_array_handle_bit_elements but the pointer is good for reading and writing.  You must take care not to modify bits outside of the allowed index range of the array, even for contiguous arrays.

VLists
------

The (ice-9 vlist) module provides an implementation of the VList data structure designed by Phil Bagwell in 2002.  VLists are immutable lists, which can contain any Scheme object.  They improve on standard Scheme linked lists in several areas:

  * Random access has typically constant-time complexity.

  * Computing the length of a VList has time complexity logarithmic in the number of elements.

  * VLists use less storage space than standard lists.

  * VList elements are stored in contiguous regions, which improves memory locality and leads to more efficient use of hardware caches.

The idea behind VLists is to store vlist elements in increasingly large contiguous blocks (implemented as vectors here).  These blocks are linked to one another using a pointer to the next block and an offset within that block.  The size of these blocks form a geometric series with ratio block-growth-factor (2 by default).

The VList structure also serves as the basis for the VList-based hash lists or ``vhashes'', an immutable dictionary type (see VHashes).

However, the current implementation in (ice-9 vlist) has several noteworthy shortcomings:

  * It is not thread-safe.  Although operations on vlists are all referentially transparent (i.e., purely functional), adding elements to a vlist with vlist-cons mutates part of its internal structure, which makes it non-thread-safe.  This could be fixed, but it would slow down vlist-cons.

  * vlist-cons always allocates at least as much memory as cons. Again, Phil Bagwell describes how to fix it, but that would require tuning the garbage collector in a way that may not be generally beneficial.

  * vlist-cons is a Scheme procedure compiled to bytecode, and it does not compete with the straightforward C implementation of cons, and with the fact that the VM has a special cons instruction.

We hope to address these in the future.

The programming interface exported by (ice-9 vlist) is defined below. Most of it is the same as SRFI-1 with an added vlist- prefix to function names.

 -- Scheme Procedure: vlist? obj
     Return true if OBJ is a VList.

 -- Scheme Variable: vlist-null
     The empty VList.  Note that it's possible to create an empty VList not eq? to vlist-null; thus, callers should always use vlist-null? when testing whether a VList is empty.

 -- Scheme Procedure: vlist-null? vlist
     Return true if VLIST is empty.

 -- Scheme Procedure: vlist-cons item vlist
     Return a new vlist with ITEM as its head and VLIST as its tail.

 -- Scheme Procedure: vlist-head vlist
     Return the head of VLIST.

 -- Scheme Procedure: vlist-tail vlist
     Return the tail of VLIST.

 -- Scheme Variable: block-growth-factor
     A fluid that defines the growth factor of VList blocks, 2 by default.

The functions below provide the usual set of higher-level list operations.

 -- Scheme Procedure: vlist-fold proc init vlist
 -- Scheme Procedure: vlist-fold-right proc init vlist
     Fold over VLIST, calling PROC for each element, as for SRFI-1 fold and fold-right (see fold).

 -- Scheme Procedure: vlist-ref vlist index
     Return the element at index INDEX in VLIST.  This is typically a constant-time operation.

 -- Scheme Procedure: vlist-length vlist
     Return the length of VLIST.  This is typically logarithmic in the number of elements in VLIST.

 -- Scheme Procedure: vlist-reverse vlist
     Return a new VLIST whose content are those of VLIST in reverse order.

 -- Scheme Procedure: vlist-map proc vlist
     Map PROC over the elements of VLIST and return a new vlist.

 -- Scheme Procedure: vlist-for-each proc vlist
     Call PROC on each element of VLIST.  The result is unspecified.

 -- Scheme Procedure: vlist-drop vlist count
     Return a new vlist that does not contain the COUNT first elements of VLIST.  This is typically a constant-time operation.

 -- Scheme Procedure: vlist-take vlist count
     Return a new vlist that contains only the COUNT first elements of VLIST.

 -- Scheme Procedure: vlist-filter pred vlist
     Return a new vlist containing all the elements from VLIST that satisfy PRED.

 -- Scheme Procedure: vlist-delete x vlist [equal?]
     Return a new vlist corresponding to VLIST without the elements EQUAL? to X.

 -- Scheme Procedure: vlist-unfold p f g seed [tail-gen]
 -- Scheme Procedure: vlist-unfold-right p f g seed [tail]
     Return a new vlist, as for SRFI-1 unfold and unfold-right (see unfold).

 -- Scheme Procedure: vlist-append vlist ...
     Append the given vlists and return the resulting vlist.

 -- Scheme Procedure: list->vlist lst
     Return a new vlist whose contents correspond to LST.

 -- Scheme Procedure: vlist->list vlist
     Return a new list whose contents match those of VLIST.

Record Overview
---------------

Records, also called structures, are Scheme's primary mechanism to define new disjoint types.  A record type defines a list of fields that instances of the type consist of.  This is like C's struct.

Historically, Guile has offered several different ways to define record types and to create records, offering different features, and making different trade-offs.  Over the years, each ``standard'' has also come with its own new record interface, leading to a maze of record APIs.

At the highest level is SRFI-9, a high-level record interface implemented by most Scheme implementations (see SRFI-9).  It defines a simple and efficient syntactic abstraction of record types and their associated type predicate, fields, and field accessors.  SRFI-9 is suitable for most uses, and this is the recommended way to create record types in Guile.  Similar high-level record APIs include SRFI-35 (see SRFI-35) and R6RS records (see rnrs records syntactic).

Then comes Guile's historical ``records'' API (see Records).  Record types defined this way are first-class objects.  Introspection facilities are available, allowing users to query the list of fields or the value of a specific field at run-time, without prior knowledge of the type.

Finally, the common denominator of these interfaces is Guile's structure API (see Structures).  Guile's structures are the low-level building block for all other record APIs.  Application writers will normally not need to use it.

Records created with these APIs may all be pattern-matched using Guile's standard pattern matcher (see Pattern Matching).

SRFI-9 Records
--------------

SRFI-9 standardizes a syntax for defining new record types and creating predicate, constructor, and field getter and setter functions.  In Guile this is the recommended option to create new record types (see Record Overview).  It can be used with:

     (use-modules (srfi srfi-9))

 -- library syntax: define-record-type type
 (constructor fieldname ...)
 predicate
 (fieldname accessor [modifier]) ...

     Create a new record type, and make various defines for using it.  This syntax can only occur at the top-level, not nested within some other form.

     TYPE is bound to the record type, which is as per the return from the core make-record-type.  TYPE also provides the name for the record, as per record-type-name.

     CONSTRUCTOR is bound to a function to be called as (CONSTRUCTOR fieldval ...) to create a new record of this type.  The arguments are initial values for the fields, one argument for each field, in the order they appear in the define-record-type form.

     The FIELDNAMEs provide the names for the record fields, as per the core record-type-fields etc, and are referred to in the subsequent accessor/modifier forms.

     PREDICATE is bound to a function to be called as (PREDICATE obj).  It returns #t or #f according to whether OBJ is a record of this type.

     Each ACCESSOR is bound to a function to be called (ACCESSOR record) to retrieve the respective field from a RECORD.  Similarly each MODIFIER is bound to a function to be called (MODIFIER record val) to set the respective field in a RECORD.

An example will illustrate typical usage,

     (define-record-type employee-type
       (make-employee name age salary)
       employee?
       (name    get-employee-name)
       (age     get-employee-age    set-employee-age)
       (salary  get-employee-salary set-employee-salary))

This creates a new employee data type, with name, age and salary fields.  Accessor functions are created for each field, but no modifier function for the name (the intention in this example being that it's established only when an employee object is created).  These can all then be used as for example,

     employee-type => #<record-type employee-type>

     (define fred (make-employee "Fred" 45 20000.00))

     (employee? fred)        => #t
     (get-employee-age fred) => 45
     (set-employee-salary fred 25000.00)  ;; pay rise

The functions created by define-record-type are ordinary top-level defines.  They can be redefined or set! as desired, exported from a module, etc.

Non-toplevel Record Definitions
...............................

The SRFI-9 specification explicitly disallows record definitions in a non-toplevel context, such as inside lambda body or inside a LET block.  However, Guile's implementation does not enforce that restriction.

Custom Printers
...............

You may use set-record-type-printer! to customize the default printing behavior of records.  This is a Guile extension and is not part of SRFI-9.  It is located in the (srfi srfi-9 gnu) module.

 -- Scheme Syntax: set-record-type-printer! name thunk
     Where TYPE corresponds to the first argument of define-record-type, and THUNK is a procedure accepting two arguments, the record to print, and an output port.

This example prints the employee's name in brackets, for instance [Fred].

     (set-record-type-printer! employee-type
       (lambda (record port)
         (write-char #\[ port)
         (display (get-employee-name record) port)
         (write-char #\] port)))

Functional ``Setters''
......................

When writing code in a functional style, it is desirable to never alter the contents of records.  For such code, a simple way to return new record instances based on existing ones is highly desirable.

The (srfi srfi-9 gnu) module extends SRFI-9 with facilities to return new record instances based on existing ones, only with one or more field values changed---functional setters.  First, the define-immutable-record-type works like define-record-type, except that fields are immutable and setters are defined as functional setters.

 -- Scheme Syntax: define-immutable-record-type type
 (constructor fieldname ...)
 predicate
 (fieldname accessor [modifier]) ...
     Define TYPE as a new record type, like define-record-type. However, the record type is made immutable (records may not be mutated, even with struct-set!), and any MODIFIER is defined to be a functional setter---a procedure that returns a new record instance with the specified field changed, and leaves the original unchanged (see example below.)

In addition, the generic set-field and set-fields macros may be applied to any SRFI-9 record.

 -- Scheme Syntax: set-field record (field sub-fields ...) value
     Return a new record of RECORD's type whose fields are equal to the corresponding fields of RECORD except for the one specified by FIELD.

     FIELD must be the name of the getter corresponding to the field of RECORD being ``set''.  Subsequent SUB-FIELDS must be record getters designating sub-fields within that field value to be set (see example below.)

 -- Scheme Syntax: set-fields record ((field sub-fields ...) value) ...
     Like set-field, but can be used to set more than one field at a time.  This expands to code that is more efficient than a series of single set-field calls.

To illustrate the use of functional setters, let's assume these two record type definitions:

     (define-record-type <address>
       (address street city country)
       address?
       (street  address-street)
       (city    address-city)
       (country address-country))

     (define-immutable-record-type <person>
       (person age email address)
       person?
       (age     person-age set-person-age)
       (email   person-email set-person-email)
       (address person-address set-person-address))

First, note that the <person> record type definition introduces named functional setters.  These may be used like this:

     (define fsf-address
       (address "Franklin Street" "Boston" "USA"))

     (define rms
       (person 30 "rms@gnu.org" fsf-address))

     (and (equal? (set-person-age rms 60)
                  (person 60 "rms@gnu.org" fsf-address))
          (= (person-age rms) 30))
     => #t

Here, the original <person> record, to which RMS is bound, is left unchanged.

Now, suppose we want to change both the street and age of RMS. This can be achieved using set-fields:

     (set-fields rms
       ((person-age) 60)
       ((person-address address-street) "Temple Place"))
     => #<<person> age: 60 email: "rms@gnu.org"
       address: #<<address> street: "Temple Place" city: "Boston" country: "USA">>

Notice how the above changed two fields of RMS, including the street field of its address field, in a concise way.  Also note that set-fields works equally well for types defined with just define-record-type.

Records
-------

A record type is a first class object representing a user-defined data type.  A record is an instance of a record type.

Note that in many ways, this interface is too low-level for every-day use.  Most uses of records are better served by SRFI-9 records. See SRFI-9.

 -- Scheme Procedure: record? obj
     Return #t if OBJ is a record of any type and #f otherwise.

     Note that record? may be true of any Scheme value; there is no promise that records are disjoint with other Scheme types.

 -- Scheme Procedure: make-record-type type-name field-names [print]
     Create and return a new record-type descriptor.

     TYPE-NAME is a string naming the type.  Currently it's only used in the printed representation of records, and in diagnostics. FIELD-NAMES is a list of symbols naming the fields of a record of the type.  Duplicates are not allowed among these symbols.

          (make-record-type "employee" '(name age salary))

     The optional PRINT argument is a function used by display, write, etc, for printing a record of the new type.  It's called as (PRINT record port) and should look at RECORD and write to PORT.

 -- Scheme Procedure: record-constructor rtd [field-names]
     Return a procedure for constructing new members of the type represented by RTD.  The returned procedure accepts exactly as many arguments as there are symbols in the given list, FIELD-NAMES; these are used, in order, as the initial values of those fields in a new record, which is returned by the constructor procedure.  The values of any fields not named in that list are unspecified.  The FIELD-NAMES argument defaults to the list of field names in the call to make-record-type that created the type represented by RTD; if the FIELD-NAMES argument is provided, it is an error if it contains any duplicates or any symbols not in the default list.

 -- Scheme Procedure: record-predicate rtd
     Return a procedure for testing membership in the type represented by RTD.  The returned procedure accepts exactly one argument and returns a true value if the argument is a member of the indicated record type; it returns a false value otherwise.

 -- Scheme Procedure: record-accessor rtd field-name
     Return a procedure for reading the value of a particular field of a member of the type represented by RTD.  The returned procedure accepts exactly one argument which must be a record of the appropriate type; it returns the current value of the field named by the symbol FIELD-NAME in that record.  The symbol FIELD-NAME must be a member of the list of field-names in the call to make-record-type that created the type represented by RTD.

 -- Scheme Procedure: record-modifier rtd field-name
     Return a procedure for writing the value of a particular field of a member of the type represented by RTD.  The returned procedure accepts exactly two arguments: first, a record of the appropriate type, and second, an arbitrary Scheme value; it modifies the field named by the symbol FIELD-NAME in that record to contain the given value. The returned value of the modifier procedure is unspecified.  The symbol FIELD-NAME must be a member of the list of field-names in the call to make-record-type that created the type represented by RTD.

 -- Scheme Procedure: record-type-descriptor record
     Return a record-type descriptor representing the type of the given record.  That is, for example, if the returned descriptor were passed to record-predicate, the resulting predicate would return a true value when passed the given record.  Note that it is not necessarily the case that the returned descriptor is the one that was passed to record-constructor in the call that created the constructor procedure that created the given record.

 -- Scheme Procedure: record-type-name rtd
     Return the type-name associated with the type represented by rtd.  The returned value is eqv? to the TYPE-NAME argument given in the call to make-record-type that created the type represented by RTD.

 -- Scheme Procedure: record-type-fields rtd
     Return a list of the symbols naming the fields in members of the type represented by RTD.  The returned value is equal? to the field-names argument given in the call to make-record-type that created the type represented by RTD.

Structures
----------

A structure is a first class data type which holds Scheme values or C words in fields numbered 0 upwards.  A vtable is a structure that represents a structure type, giving field types and permissions, and an optional print function for write etc.

Structures are lower level than records (see Records).  Usually, when you need to represent structured data, you just want to use records.  But sometimes you need to implement new kinds of structured data abstractions, and for that purpose structures are useful.  Indeed, records in Guile are implemented with structures.

Vtables
.......

A vtable is a structure type, specifying its layout, and other information.  A vtable is actually itself a structure, but there's no need to worry about that initially (see Vtable Contents.)

 -- Scheme Procedure: make-vtable fields [print]
     Create a new vtable.

     FIELDS is a string describing the fields in the structures to be created.  Each field is represented by two characters, a type letter and a permissions letter, for example "pw".  The types are as follows.

       * p -- a Scheme value.  ``p'' stands for ``protected'' meaning it's protected against garbage collection.

       * u -- an arbitrary word of data (an scm_t_bits).  At the Scheme level it's read and written as an unsigned integer.  ``u'' stands for ``uninterpreted'' (it's not treated as a Scheme value), or ``unprotected'' (it's not marked during GC), or ``unsigned long'' (its size), or all of these things.

       * s -- a self-reference.  Such a field holds the SCM value of the structure itself (a circular reference).  This can be useful in C code where you might have a pointer to the data array, and want to get the Scheme SCM handle for the structure.  In Scheme code it has no use.

     The second letter for each field is a permission code,

       * w -- writable, the field can be read and written.

       * r -- read-only, the field can be read but not written.

       * o -- opaque, the field can be neither read nor written at the Scheme level.  This can be used for fields which should only be used from C code.

     Here are some examples.  See Tail Arrays, for information on the legacy tail array facility.

          (make-vtable "pw")      ;; one writable field
          (make-vtable "prpw")    ;; one read-only and one writable
          (make-vtable "pwuwuw")  ;; one scheme and two uninterpreted

     The optional PRINT argument is a function called by display and write (etc) to give a printed representation of a structure created from this vtable.  It's called (PRINT struct port) and should look at STRUCT and write to PORT.  The default print merely gives a form like #<struct ADDR:ADDR> with a pair of machine addresses.

     The following print function for example shows the two fields of its structure.

          (make-vtable "prpw"
                       (lambda (struct port)
                         (format port "#<~a and ~a>"
                                 (struct-ref struct 0)
                                 (struct-ref struct 1))))

Structure Basics
................

This section describes the basic procedures for working with structures.  make-struct creates a structure, and struct-ref and struct-set! access its fields.

 -- Scheme Procedure: make-struct vtable tail-size init ...
 -- Scheme Procedure: make-struct/no-tail vtable init ...
     Create a new structure, with layout per the given VTABLE (see Vtables).

     The optional INIT... arguments are initial values for the fields of the structure.  This is the only way to put values in read-only fields.  If there are fewer INIT arguments than fields then the defaults are #f for a Scheme field (type p) or 0 for an uninterpreted field (type u).

     Structures also have the ability to allocate a variable number of additional cells at the end, at their tails.  However, this legacy tail array facilty is confusing and inefficient, and so we do not recommend it.  See Tail Arrays, for more on the legacy tail array interface.

     Type s self-reference fields, permission o opaque fields, and the count field of a tail array are all ignored for the INIT arguments, ie. an argument is not consumed by such a field.  An s is always set to the structure itself, an o is always set to #f or 0 (with the intention that C code will do something to it later), and the tail count is always the given TAIL-SIZE.

     For example,

          (define v (make-vtable "prpwpw"))
          (define s (make-struct v 0 123 "abc" 456))
          (struct-ref s 0) => 123
          (struct-ref s 1) => "abc"

 -- C Function: SCM scm_make_struct (SCM vtable, SCM tail_size, SCM init_list)
 -- C Function: SCM scm_c_make_struct (SCM vtable, SCM tail_size, SCM init, ...)
 -- C Function: SCM scm_c_make_structv (SCM vtable, SCM tail_size, size_t n_inits, scm_t_bits init[])
     There are a few ways to make structures from C.  scm_make_struct takes a list, scm_c_make_struct takes variable arguments terminated with SCM_UNDEFINED, and scm_c_make_structv takes a packed array.

 -- Scheme Procedure: struct? obj
 -- C Function: scm_struct_p (obj)
     Return #t if OBJ is a structure, or #f if not.

 -- Scheme Procedure: struct-ref struct n
 -- C Function: scm_struct_ref (struct, n)
     Return the contents of field number N in STRUCT.  The first field is number 0.

     An error is thrown if N is out of range, or if the field cannot be read because it's o opaque.

 -- Scheme Procedure: struct-set! struct n value
 -- C Function: scm_struct_set_x (struct, n, value)
     Set field number N in STRUCT to VALUE.  The first field is number 0.

     An error is thrown if N is out of range, or if the field cannot be written because it's r read-only or o opaque.

 -- Scheme Procedure: struct-vtable struct
 -- C Function: scm_struct_vtable (struct)
     Return the vtable that describes STRUCT.

     The vtable is effectively the type of the structure.  See Vtable Contents, for more on vtables.

Vtable Contents
...............

A vtable is itself a structure.  It has a specific set of fields describing various aspects of its instances: the structures created from a vtable.  Some of the fields are internal to Guile, some of them are part of the public interface, and there may be additional fields added on by the user.

Every vtable has a field for the layout of their instances, a field for the procedure used to print its instances, and a field for the name of the vtable itself.  Access to the layout and printer is exposed directly via field indexes.  Access to the vtable name is exposed via accessor procedures.

 -- Scheme Variable: vtable-index-layout
 -- C Macro: scm_vtable_index_layout
     The field number of the layout specification in a vtable.  The layout specification is a symbol like pwpw formed from the fields string passed to make-vtable, or created by make-struct-layout (see Meta-Vtables).

          (define v (make-vtable "pwpw" 0))
          (struct-ref v vtable-index-layout) => pwpw

     This field is read-only, since the layout of structures using a vtable cannot be changed.

 -- Scheme Variable: vtable-index-printer
 -- C Macro: scm_vtable_index_printer
     The field number of the printer function.  This field contains #f if the default print function should be used.

          (define (my-print-func struct port)
            ...)
          (define v (make-vtable "pwpw" my-print-func))
          (struct-ref v vtable-index-printer) => my-print-func

     This field is writable, allowing the print function to be changed dynamically.

 -- Scheme Procedure: struct-vtable-name vtable
 -- Scheme Procedure: set-struct-vtable-name! vtable name
 -- C Function: scm_struct_vtable_name (vtable)
 -- C Function: scm_set_struct_vtable_name_x (vtable, name)
     Get or set the name of VTABLE.  NAME is a symbol and is used in the default print function when printing structures created from VTABLE.

          (define v (make-vtable "pw"))
          (set-struct-vtable-name! v 'my-name)

          (define s (make-struct v 0))
          (display s) -| #<my-name b7ab3ae0:b7ab3730>

Meta-Vtables
............

As a structure, a vtable also has a vtable, which is also a structure. Structures, their vtables, the vtables of the vtables, and so on form a tree of structures.  Making a new structure adds a leaf to the tree, and if that structure is a vtable, it may be used to create other leaves.

If you traverse up the tree of vtables, via calling struct-vtable, eventually you reach a root which is the vtable of itself:

     scheme@(guile-user)> (current-module)
     $1 = #<directory (guile-user) 221b090>
     scheme@(guile-user)> (struct-vtable $1)
     $2 = #<record-type module>
     scheme@(guile-user)> (struct-vtable $2)
     $3 = #<<standard-vtable> 12c30a0>
     scheme@(guile-user)> (struct-vtable $3)
     $4 = #<<standard-vtable> 12c3fa0>
     scheme@(guile-user)> (struct-vtable $4)
     $5 = #<<standard-vtable> 12c3fa0>
     scheme@(guile-user)> <standard-vtable>
     $6 = #<<standard-vtable> 12c3fa0>

In this example, we can say that $1 is an instance of $2, $2 is an instance of $3, $3 is an instance of $4, and $4, strangely enough, is an instance of itself. The value bound to $4 in this console session also bound to <standard-vtable> in the default environment.

 -- Scheme Variable: <standard-vtable>
     A meta-vtable, useful for making new vtables.

All of these values are structures.  All but $1 are vtables.  As $2 is an instance of $3, and $3 is a vtable, we can say that $3 is a meta-vtable: a vtable that can create vtables.

With this definition, we can specify more precisely what a vtable is: a vtable is a structure made from a meta-vtable.  Making a structure from a meta-vtable runs some special checks to ensure that the first field of the structure is a valid layout.  Additionally, if these checks see that the layout of the child vtable contains all the required fields of a vtable, in the correct order, then the child vtable will also be a meta-table, inheriting a magical bit from the parent.

 -- Scheme Procedure: struct-vtable? obj
 -- C Function: scm_struct_vtable_p (obj)
     Return #t if OBJ is a vtable structure: an instance of a meta-vtable.

<standard-vtable> is a root of the vtable tree.  (Normally there is only one root in a given Guile process, but due to some legacy interfaces there may be more than one.)

The set of required fields of a vtable is the set of fields in the <standard-vtable>, and is bound to standard-vtable-fields in the default environment.  It is possible to create a meta-vtable that with additional fields in its layout, which can be used to create vtables with additional data:

     scheme@(guile-user)> (struct-ref $3 vtable-index-layout)
     $6 = pruhsruhpwphuhuhprprpw
     scheme@(guile-user)> (struct-ref $4 vtable-index-layout)
     $7 = pruhsruhpwphuhuh
     scheme@(guile-user)> standard-vtable-fields
     $8 = "pruhsruhpwphuhuh"
     scheme@(guile-user)> (struct-ref $2 vtable-offset-user)
     $9 = module

In this continuation of our earlier example, $2 is a vtable that has extra fields, because its vtable, $3, was made from a meta-vtable with an extended layout.  vtable-offset-user is a convenient definition that indicates the number of fields in standard-vtable-fields.

 -- Scheme Variable: standard-vtable-fields
     A string containing the orderedq set of fields that a vtable must have.

 -- Scheme Variable: vtable-offset-user
     The first index in a vtable that is available for a user.

 -- Scheme Procedure: make-struct-layout fields
 -- C Function: scm_make_struct_layout (fields)
     Return a structure layout symbol, from a FIELDS string. FIELDS is as described under make-vtable (see Vtables).  An invalid FIELDS string is an error.

With these definitions, one can define make-vtable in this way:

     (define* (make-vtable fields #:optional printer)
       (make-struct/no-tail <standard-vtable>
         (make-struct-layout fields)
         printer))

Vtable Example
..............

Let us bring these points together with an example.  Consider a simple object system with single inheritance.  Objects will be normal structures, and classes will be vtables with three extra class fields: the name of the class, the parent class, and the list of fields.

So, first we need a meta-vtable that allocates instances with these extra class fields.

     (define <class>
       (make-vtable
        (string-append standard-vtable-fields "pwpwpw")
        (lambda (x port)
          (format port "<<class> ~a>" (class-name x)))))

     (define (class? x)
       (and (struct? x)
            (eq? (struct-vtable x) <class>)))

To make a structure with a specific meta-vtable, we will use make-struct/no-tail, passing it the computed instance layout and printer, as with make-vtable, and additionally the extra three class fields.

     (define (make-class name parent fields)
       (let* ((fields (compute-fields parent fields))
              (layout (compute-layout fields)))
         (make-struct/no-tail <class>
           layout
           (lambda (x port)
             (print-instance x port))
           name
           parent
           fields)))

Instances will store their associated data in slots in the structure: as many slots as there are fields.  The compute-layout procedure below can compute a layout, and field-index returns the slot corresponding to a field.

     (define-syntax-rule (define-accessor name n)
       (define (name obj)
         (struct-ref obj n)))

     ;; Accessors for classes
     (define-accessor class-name (+ vtable-offset-user 0))
     (define-accessor class-parent (+ vtable-offset-user 1))
     (define-accessor class-fields (+ vtable-offset-user 2))

     (define (compute-fields parent fields)
       (if parent
           (append (class-fields parent) fields)
           fields))

     (define (compute-layout fields)
       (make-struct-layout
        (string-concatenate (make-list (length fields) "pw"))))

     (define (field-index class field)
       (list-index (class-fields class) field))

     (define (print-instance x port)
       (format port "<~a" (class-name (struct-vtable x)))
       (for-each (lambda (field idx)
                   (format port " ~a: ~a" field (struct-ref x idx)))
                 (class-fields (struct-vtable x))
                 (iota (length (class-fields (struct-vtable x)))))
       (format port ">"))

So, at this point we can actually make a few classes:

     (define-syntax-rule (define-class name parent field ...)
       (define name (make-class 'name parent '(field ...))))

     (define-class <surface> #f
       width height)

     (define-class <window> <surface>
       x y)

And finally, make an instance:

     (make-struct/no-tail <window> 400 300 10 20)
     => <<window> width: 400 height: 300 x: 10 y: 20>

And that's that.  Note that there are many possible optimizations and feature enhancements that can be made to this object system, and the included GOOPS system does make most of them.  For more simple use cases, the records facility is usually sufficient.  But sometimes you need to make new kinds of data abstractions, and for that purpose, structs are here.

Tail Arrays
...........

Guile's structures have a facility whereby each instance of a vtable can contain a variable-length tail array of values.  The length of the tail array is stored in the structure.  This facility was originally intended to allow C code to expose raw C structures with word-sized tail arrays to Scheme.

However, the tail array facility is confusing and doesn't work very well.  It is very rarely used, but it insinuates itself into all invocations of make-struct.  For this reason the clumsily-named make-struct/no-tail procedure can actually be more elegant in actual use, because it doesn't have a random 0 argument stuck in the middle.

Tail arrays also inhibit optimization by allowing instances to affect their shapes.  In the absence of tail arrays, all instances of a given vtable have the same number and kinds of fields.  This uniformity can be exploited by the runtime and the optimizer.  The presence of tail arrays make some of these optimizations more difficult.

Finally, the tail array facility is ad-hoc and does not compose with the rest of Guile.  If a Guile user wants an array with user-specified length, it's best to use a vector.  It is more clear in the code, and the standard optimization techniques will do a good job with it.

That said, we should mention some details about the interface.  A vtable that has tail array has upper-case permission descriptors: W, R or O, correspoding to tail arrays of writable, read-only, or opaque elements.  A tail array permission descriptor may only appear in the last element of a vtable layout.

For exampple, pW indicates a tail of writable Scheme-valued fields.  The pW field itself holds the tail size, and the tail fields come after it.

     (define v (make-vtable "prpW")) ;; one fixed then a tail array
     (define s (make-struct v 6 "fixed field" 'x 'y))
     (struct-ref s 0) => "fixed field"
     (struct-ref s 1) => 2    ;; tail size
     (struct-ref s 2) => x    ;; tail array ...
     (struct-ref s 3) => y
     (struct-ref s 4) => #f

Dictionary Types
----------------

A dictionary object is a data structure used to index information in a user-defined way.  In standard Scheme, the main aggregate data types are lists and vectors.  Lists are not really indexed at all, and vectors are indexed only by number (e.g. (vector-ref foo 5)).  Often you will find it useful to index your data on some other type; for example, in a library catalog you might want to look up a book by the name of its author.  Dictionaries are used to help you organize information in such a way.

An association list (or alist for short) is a list of key-value pairs.  Each pair represents a single quantity or object; the car of the pair is a key which is used to identify the object, and the cdr is the object's value.

A hash table also permits you to index objects with arbitrary keys, but in a way that makes looking up any one object extremely fast.  A well-designed hash system makes hash table lookups almost as fast as conventional array or vector references.

Alists are popular among Lisp programmers because they use only the language's primitive operations (lists, car, cdr and the equality primitives).  No changes to the language core are necessary.  Therefore, with Scheme's built-in list manipulation facilities, it is very convenient to handle data stored in an association list.  Also, alists are highly portable and can be easily implemented on even the most minimal Lisp systems.

However, alists are inefficient, especially for storing large quantities of data.  Because we want Guile to be useful for large software systems as well as small ones, Guile provides a rich set of tools for using either association lists or hash tables.

Association Lists
-----------------

An association list is a conventional data structure that is often used to implement simple key-value databases.  It consists of a list of entries in which each entry is a pair.  The key of each entry is the car of the pair and the value of each entry is the cdr.

     ASSOCIATION LIST ::=  '( (KEY1 . VALUE1)
                              (KEY2 . VALUE2)
                              (KEY3 . VALUE3)
                              ...
                            )

Association lists are also known, for short, as alists.

The structure of an association list is just one example of the infinite number of possible structures that can be built using pairs and lists. As such, the keys and values in an association list can be manipulated using the general list structure procedures cons, car, cdr, set-car!, set-cdr! and so on.  However, because association lists are so useful, Guile also provides specific procedures for manipulating them.

Alist Key Equality
..................

All of Guile's dedicated association list procedures, apart from acons, come in three flavours, depending on the level of equality that is required to decide whether an existing key in the association list is the same as the key that the procedure call uses to identify the required entry.

  * Procedures with assq in their name use eq? to determine key equality.

  * Procedures with assv in their name use eqv? to determine key equality.

  * Procedures with assoc in their name use equal? to determine key equality.

acons is an exception because it is used to build association lists which do not require their entries' keys to be unique.

Adding or Setting Alist Entries
...............................

acons adds a new entry to an association list and returns the combined association list.  The combined alist is formed by consing the new entry onto the head of the alist specified in the acons procedure call.  So the specified alist is not modified, but its contents become shared with the tail of the combined alist that acons returns.

In the most common usage of acons, a variable holding the original association list is updated with the combined alist:

     (set! address-list (acons name address address-list))

In such cases, it doesn't matter that the old and new values of address-list share some of their contents, since the old value is usually no longer independently accessible.

Note that acons adds the specified new entry regardless of whether the alist may already contain entries with keys that are, in some sense, the same as that of the new entry.  Thus acons is ideal for building alists where there is no concept of key uniqueness.

     (set! task-list (acons 3 "pay gas bill" '()))
     task-list
     =>
     ((3 . "pay gas bill"))

     (set! task-list (acons 3 "tidy bedroom" task-list))
     task-list
     =>
     ((3 . "tidy bedroom") (3 . "pay gas bill"))

assq-set!, assv-set! and assoc-set! are used to add or replace an entry in an association list where there is a concept of key uniqueness.  If the specified association list already contains an entry whose key is the same as that specified in the procedure call, the existing entry is replaced by the new one. Otherwise, the new entry is consed onto the head of the old association list to create the combined alist.  In all cases, these procedures return the combined alist.

assq-set! and friends may destructively modify the structure of the old association list in such a way that an existing variable is correctly updated without having to set! it to the value returned:

     address-list
     =>
     (("mary" . "34 Elm Road") ("james" . "16 Bow Street"))

     (assoc-set! address-list "james" "1a London Road")
     =>
     (("mary" . "34 Elm Road") ("james" . "1a London Road"))

     address-list
     =>
     (("mary" . "34 Elm Road") ("james" . "1a London Road"))

Or they may not:

     (assoc-set! address-list "bob" "11 Newington Avenue")
     =>
     (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
      ("james" . "1a London Road"))

     address-list
     =>
     (("mary" . "34 Elm Road") ("james" . "1a London Road"))

The only safe way to update an association list variable when adding or replacing an entry like this is to set! the variable to the returned value:

     (set! address-list
           (assoc-set! address-list "bob" "11 Newington Avenue"))
     address-list
     =>
     (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
      ("james" . "1a London Road"))

Because of this slight inconvenience, you may find it more convenient to use hash tables to store dictionary data.  If your application will not be modifying the contents of an alist very often, this may not make much difference to you.

If you need to keep the old value of an association list in a form independent from the list that results from modification by acons, assq-set!, assv-set! or assoc-set!, use list-copy to copy the old association list before modifying it.

 -- Scheme Procedure: acons key value alist
 -- C Function: scm_acons (key, value, alist)
     Add a new key-value pair to ALIST.  A new pair is created whose car is KEY and whose cdr is VALUE, and the pair is consed onto ALIST, and the new list is returned.  This function is not destructive; ALIST is not modified.

 -- Scheme Procedure: assq-set! alist key val
 -- Scheme Procedure: assv-set! alist key value
 -- Scheme Procedure: assoc-set! alist key value
 -- C Function: scm_assq_set_x (alist, key, val)
 -- C Function: scm_assv_set_x (alist, key, val)
 -- C Function: scm_assoc_set_x (alist, key, val)
     Reassociate KEY in ALIST with VALUE: find any existing ALIST entry for KEY and associate it with the new VALUE.  If ALIST does not contain an entry for KEY, add a new one.  Return the (possibly new) alist.

     These functions do not attempt to verify the structure of ALIST, and so may cause unusual results if passed an object that is not an association list.

Retrieving Alist Entries
........................

assq, assv and assoc find the entry in an alist for a given key, and return the (KEY . VALUE) pair. assq-ref, assv-ref and assoc-ref do a similar lookup, but return just the VALUE.

 -- Scheme Procedure: assq key alist
 -- Scheme Procedure: assv key alist
 -- Scheme Procedure: assoc key alist
 -- C Function: scm_assq (key, alist)
 -- C Function: scm_assv (key, alist)
 -- C Function: scm_assoc (key, alist)
     Return the first entry in ALIST with the given KEY.  The return is the pair (KEY . VALUE) from ALIST.  If there's no matching entry the return is #f.

     assq compares keys with eq?, assv uses eqv? and assoc uses equal?.  See also SRFI-1 which has an extended assoc (SRFI-1 Association Lists).

 -- Scheme Procedure: assq-ref alist key
 -- Scheme Procedure: assv-ref alist key
 -- Scheme Procedure: assoc-ref alist key
 -- C Function: scm_assq_ref (alist, key)
 -- C Function: scm_assv_ref (alist, key)
 -- C Function: scm_assoc_ref (alist, key)
     Return the value from the first entry in ALIST with the given KEY, or #f if there's no such entry.

     assq-ref compares keys with eq?, assv-ref uses eqv? and assoc-ref uses equal?.

     Notice these functions have the KEY argument last, like other -ref functions, but this is opposite to what assq etc above use.

     When the return is #f it can be either KEY not found, or an entry which happens to have value #f in the cdr.  Use assq etc above if you need to differentiate these cases.

Removing Alist Entries
......................

To remove the element from an association list whose key matches a specified key, use assq-remove!, assv-remove! or assoc-remove! (depending, as usual, on the level of equality required between the key that you specify and the keys in the association list).

As with assq-set! and friends, the specified alist may or may not be modified destructively, and the only safe way to update a variable containing the alist is to set! it to the value that assq-remove! and friends return.

     address-list
     =>
     (("bob" . "11 Newington Avenue") ("mary" . "34 Elm Road")
      ("james" . "1a London Road"))

     (set! address-list (assoc-remove! address-list "mary"))
     address-list
     =>
     (("bob" . "11 Newington Avenue") ("james" . "1a London Road"))

Note that, when assq/v/oc-remove! is used to modify an association list that has been constructed only using the corresponding assq/v/oc-set!, there can be at most one matching entry in the alist, so the question of multiple entries being removed in one go does not arise.  If assq/v/oc-remove! is applied to an association list that has been constructed using acons, or an assq/v/oc-set! with a different level of equality, or any mixture of these, it removes only the first matching entry from the alist, even if the alist might contain further matching entries.  For example:

     (define address-list '())
     (set! address-list (assq-set! address-list "mary" "11 Elm Street"))
     (set! address-list (assq-set! address-list "mary" "57 Pine Drive"))
     address-list
     =>
     (("mary" . "57 Pine Drive") ("mary" . "11 Elm Street"))

     (set! address-list (assoc-remove! address-list "mary"))
     address-list
     =>
     (("mary" . "11 Elm Street"))

In this example, the two instances of the string "mary" are not the same when compared using eq?, so the two assq-set! calls add two distinct entries to address-list.  When compared using equal?, both "mary"s in address-list are the same as the "mary" in the assoc-remove! call, but assoc-remove! stops after removing the first matching entry that it finds, and so one of the "mary" entries is left in place.

 -- Scheme Procedure: assq-remove! alist key
 -- Scheme Procedure: assv-remove! alist key
 -- Scheme Procedure: assoc-remove! alist key
 -- C Function: scm_assq_remove_x (alist, key)
 -- C Function: scm_assv_remove_x (alist, key)
 -- C Function: scm_assoc_remove_x (alist, key)
     Delete the first entry in ALIST associated with KEY, and return the resulting alist.

Sloppy Alist Functions
......................

sloppy-assq, sloppy-assv and sloppy-assoc behave like the corresponding non-sloppy- procedures, except that they return #f when the specified association list is not well-formed, where the non-sloppy- versions would signal an error.

Specifically, there are two conditions for which the non-sloppy- procedures signal an error, which the sloppy- procedures handle instead by returning #f.  Firstly, if the specified alist as a whole is not a proper list:

     (assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
     =>
     ERROR: In procedure assoc in expression (assoc "mary" (quote #)):
     ERROR: Wrong type argument in position 2 (expecting
        association list): ((1 . 2) ("key" . "door") . "open sesame")

     (sloppy-assoc "mary" '((1 . 2) ("key" . "door") . "open sesame"))
     =>
     #f

Secondly, if one of the entries in the specified alist is not a pair:

     (assoc 2 '((1 . 1) 2 (3 . 9)))
     =>
     ERROR: In procedure assoc in expression (assoc 2 (quote #)):
     ERROR: Wrong type argument in position 2 (expecting
        association list): ((1 . 1) 2 (3 . 9))

     (sloppy-assoc 2 '((1 . 1) 2 (3 . 9)))
     =>
     #f

Unless you are explicitly working with badly formed association lists, it is much safer to use the non-sloppy- procedures, because they help to highlight coding and data errors that the sloppy- versions would silently cover up.

 -- Scheme Procedure: sloppy-assq key alist
 -- C Function: scm_sloppy_assq (key, alist)
     Behaves like assq but does not do any error checking. Recommended only for use in Guile internals.

 -- Scheme Procedure: sloppy-assv key alist
 -- C Function: scm_sloppy_assv (key, alist)
     Behaves like assv but does not do any error checking. Recommended only for use in Guile internals.

 -- Scheme Procedure: sloppy-assoc key alist
 -- C Function: scm_sloppy_assoc (key, alist)
     Behaves like assoc but does not do any error checking. Recommended only for use in Guile internals.

Alist Example
.............

Here is a longer example of how alists may be used in practice.

     (define capitals '(("New York" . "Albany")
                        ("Oregon"   . "Salem")
                        ("Florida"  . "Miami")))

     ;; What's the capital of Oregon?
     (assoc "Oregon" capitals)       => ("Oregon" . "Salem")
     (assoc-ref capitals "Oregon")   => "Salem"

     ;; We left out South Dakota.
     (set! capitals
           (assoc-set! capitals "South Dakota" "Pierre"))
     capitals
     => (("South Dakota" . "Pierre")
         ("New York" . "Albany")
         ("Oregon" . "Salem")
         ("Florida" . "Miami"))

     ;; And we got Florida wrong.
     (set! capitals
           (assoc-set! capitals "Florida" "Tallahassee"))
     capitals
     => (("South Dakota" . "Pierre")
         ("New York" . "Albany")
         ("Oregon" . "Salem")
         ("Florida" . "Tallahassee"))

     ;; After Oregon secedes, we can remove it.
     (set! capitals
           (assoc-remove! capitals "Oregon"))
     capitals
     => (("South Dakota" . "Pierre")
         ("New York" . "Albany")
         ("Florida" . "Tallahassee"))

VList-Based Hash Lists or ``VHashes''
-------------------------------------

The (ice-9 vlist) module provides an implementation of VList-based hash lists (see VLists).  VList-based hash lists, or vhashes, are an immutable dictionary type similar to association lists that maps keys to values.  However, unlike association lists, accessing a value given its key is typically a constant-time operation.

The VHash programming interface of (ice-9 vlist) is mostly the same as that of association lists found in SRFI-1, with procedure names prefixed by vhash- instead of alist- (see SRFI-1 Association Lists).

In addition, vhashes can be manipulated using VList operations:

     (vlist-head (vhash-consq 'a 1 vlist-null))
     => (a . 1)

     (define vh1 (vhash-consq 'b 2 (vhash-consq 'a 1 vlist-null)))
     (define vh2 (vhash-consq 'c 3 (vlist-tail vh1)))

     (vhash-assq 'a vh2)
     => (a . 1)
     (vhash-assq 'b vh2)
     => #f
     (vhash-assq 'c vh2)
     => (c . 3)
     (vlist->list vh2)
     => ((c . 3) (a . 1))

However, keep in mind that procedures that construct new VLists (vlist-map, vlist-filter, etc.) return raw VLists, not vhashes:

     (define vh (alist->vhash '((a . 1) (b . 2) (c . 3)) hashq))
     (vhash-assq 'a vh)
     => (a . 1)

     (define vl
       ;; This will create a raw vlist.
       (vlist-filter (lambda (key+value) (odd? (cdr key+value))) vh))
     (vhash-assq 'a vl)
     => ERROR: Wrong type argument in position 2

     (vlist->list vl)
     => ((a . 1) (c . 3))

 -- Scheme Procedure: vhash? obj
     Return true if OBJ is a vhash.

 -- Scheme Procedure: vhash-cons key value vhash [hash-proc]
 -- Scheme Procedure: vhash-consq key value vhash
 -- Scheme Procedure: vhash-consv key value vhash
     Return a new hash list based on VHASH where KEY is associated with VALUE, using HASH-PROC to compute the hash of KEY. VHASH must be either vlist-null or a vhash returned by a previous call to vhash-cons.  HASH-PROC defaults to hash (see hash procedure).  With vhash-consq, the hashq hash function is used; with vhash-consv the hashv hash function is used.

     All vhash-cons calls made to construct a vhash should use the same HASH-PROC.  Failing to do that, the result is undefined.

 -- Scheme Procedure: vhash-assoc key vhash [equal? [hash-proc]]
 -- Scheme Procedure: vhash-assq key vhash
 -- Scheme Procedure: vhash-assv key vhash
     Return the first key/value pair from VHASH whose key is equal to KEY according to the EQUAL? equality predicate (which defaults to equal?), and using HASH-PROC (which defaults to hash) to compute the hash of KEY.  The second form uses eq? as the equality predicate and hashq as the hash function; the last form uses eqv? and hashv.

     Note that it is important to consistently use the same hash function for HASH-PROC as was passed to vhash-cons.  Failing to do that, the result is unpredictable.

 -- Scheme Procedure: vhash-delete key vhash [equal? [hash-proc]]
 -- Scheme Procedure: vhash-delq key vhash
 -- Scheme Procedure: vhash-delv key vhash
     Remove all associations from VHASH with KEY, comparing keys with EQUAL? (which defaults to equal?), and computing the hash of KEY using HASH-PROC (which defaults to hash).  The second form uses eq? as the equality predicate and hashq as the hash function; the last one uses eqv? and hashv.

     Again the choice of HASH-PROC must be consistent with previous calls to vhash-cons.

 -- Scheme Procedure: vhash-fold proc init vhash
 -- Scheme Procedure: vhash-fold-right proc init vhash
     Fold over the key/value elements of VHASH in the given direction, with each call to PROC having the form (PROC key value result), where RESULT is the result of the previous call to PROC and INIT the value of RESULT for the first call to PROC.

 -- Scheme Procedure: vhash-fold* proc init key vhash [equal? [hash]]
 -- Scheme Procedure: vhash-foldq* proc init key vhash
 -- Scheme Procedure: vhash-foldv* proc init key vhash
     Fold over all the values associated with KEY in VHASH, with each call to PROC having the form (proc value result), where RESULT is the result of the previous call to PROC and INIT the value of RESULT for the first call to PROC.

     Keys in VHASH are hashed using HASH are compared using EQUAL?. The second form uses eq? as the equality predicate and hashq as the hash function; the third one uses eqv? and hashv.

     Example:

          (define vh
            (alist->vhash '((a . 1) (a . 2) (z . 0) (a . 3))))

          (vhash-fold* cons '() 'a vh)
          => (3 2 1)

          (vhash-fold* cons '() 'z vh)
          => (0)

 -- Scheme Procedure: alist->vhash alist [hash-proc]
     Return the vhash corresponding to ALIST, an association list, using HASH-PROC to compute key hashes.  When omitted, HASH-PROC defaults to hash.

Hash Tables
-----------

Hash tables are dictionaries which offer similar functionality as association lists: They provide a mapping from keys to values.  The difference is that association lists need time linear in the size of elements when searching for entries, whereas hash tables can normally search in constant time.  The drawback is that hash tables require a little bit more memory, and that you can not use the normal list procedures (see Lists) for working with them.

Guile provides two types of hashtables.  One is an abstract data type that can only be manipulated with the functions in this section.  The other type is concrete: it uses a normal vector with alists as elements.  The advantage of the abstract hash tables is that they will be automatically resized when they become too full or too empty.

Hash Table Examples
...................

For demonstration purposes, this section gives a few usage examples of some hash table procedures, together with some explanation what they do.

First we start by creating a new hash table with 31 slots, and populate it with two key/value pairs.

     (define h (make-hash-table 31))

     ;; This is an opaque object
     h
     =>
     #<hash-table 0/31>

     ;; We can also use a vector of alists.
     (define h (make-vector 7 '()))

     h
     =>
     #(() () () () () () ())

     ;; Inserting into a hash table can be done with hashq-set!
     (hashq-set! h 'foo "bar")
     =>
     "bar"

     (hashq-set! h 'braz "zonk")
     =>
     "zonk"

     ;; Or with hash-create-handle!
     (hashq-create-handle! h 'frob #f)
     =>
     (frob . #f)

     ;; The vector now contains three elements in the alists and the frob
     ;; entry is at index (hashq 'frob).
     h
     =>
     #(((braz . "zonk")) ((foo . "bar")) () () () () ((frob . #f)))

     (hashq 'frob 7)
     =>
     6

You can get the value for a given key with the procedure hashq-ref, but the problem with this procedure is that you cannot reliably determine whether a key does exists in the table.  The reason is that the procedure returns #f if the key is not in the table, but it will return the same value if the key is in the table and just happens to have the value #f, as you can see in the following examples.

     (hashq-ref h 'foo)
     =>
     "bar"

     (hashq-ref h 'frob)
     =>
     #f

     (hashq-ref h 'not-there)
     =>
     #f

Better is to use the procedure hashq-get-handle, which makes a distinction between the two cases.  Just like assq, this procedure returns a key/value-pair on success, and #f if the key is not found.

     (hashq-get-handle h 'foo)
     =>
     (foo . "bar")

     (hashq-get-handle h 'not-there)
     =>
     #f

There is no procedure for calculating the number of key/value-pairs in a hash table, but hash-fold can be used for doing exactly that.

     (hash-fold (lambda (key value seed) (+ 1 seed)) 0 h)
     =>
     3

Hash Table Reference
....................

Like the association list functions, the hash table functions come in several varieties, according to the equality test used for the keys. Plain hash- functions use equal?, hashq- functions use eq?, hashv- functions use eqv?, and the hashx- functions use an application supplied test.

A single make-hash-table creates a hash table suitable for use with any set of functions, but it's imperative that just one set is then used consistently, or results will be unpredictable.

Hash tables are implemented as a vector indexed by a hash value formed from the key, with an association list of key/value pairs for each bucket in case distinct keys hash together.  Direct access to the pairs in those lists is provided by the -handle- functions. The abstract kind of hash tables hide the vector in an opaque object that represents the hash table, while for the concrete kind the vector is the hashtable.

When the number of table entries in an abstract hash table goes above a threshold, the vector is made larger and the entries are rehashed, to prevent the bucket lists from becoming too long and slowing down accesses.  When the number of entries goes below a threshold, the vector is shrunk to save space.

A abstract hash table is created with make-hash-table.  To create a vector that is suitable as a hash table, use (make-vector SIZE '()), for example.

For the hashx- ``extended'' routines, an application supplies a HASH function producing an integer index like hashq etc below, and an ASSOC alist search function like assq etc (see Retrieving Alist Entries).  Here's an example of such functions implementing case-insensitive hashing of string keys,

     (use-modules (srfi srfi-1)
                  (srfi srfi-13))

     (define (my-hash str size)
       (remainder (string-hash-ci str) size))
     (define (my-assoc str alist)
       (find (lambda (pair) (string-ci=? str (car pair))) alist))

     (define my-table (make-hash-table))
     (hashx-set! my-hash my-assoc my-table "foo" 123)

     (hashx-ref my-hash my-assoc my-table "FOO")
     => 123

In a hashx- HASH function the aim is to spread keys across the vector, so bucket lists don't become long.  But the actual values are arbitrary as long as they're in the range 0 to SIZE-1.  Helpful functions for forming a hash value, in addition to hashq etc below, include symbol-hash (see Symbol Keys), string-hash and string-hash-ci (see String Comparison), and char-set-hash (see Character Set Predicates/Comparison).

 -- Scheme Procedure: make-hash-table [size]
     Create a new abstract hash table object, with an optional minimum vector SIZE.

     When SIZE is given, the table vector will still grow and shrink automatically, as described above, but with SIZE as a minimum. If an application knows roughly how many entries the table will hold then it can use SIZE to avoid rehashing when initial entries are added.

 -- Scheme Procedure: hash-table? obj
 -- C Function: scm_hash_table_p (obj)
     Return #t if OBJ is a abstract hash table object.

 -- Scheme Procedure: hash-clear! table
 -- C Function: scm_hash_clear_x (table)
     Remove all items from TABLE (without triggering a resize).

 -- Scheme Procedure: hash-ref table key [dflt]
 -- Scheme Procedure: hashq-ref table key [dflt]
 -- Scheme Procedure: hashv-ref table key [dflt]
 -- Scheme Procedure: hashx-ref hash assoc table key [dflt]
 -- C Function: scm_hash_ref (table, key, dflt)
 -- C Function: scm_hashq_ref (table, key, dflt)
 -- C Function: scm_hashv_ref (table, key, dflt)
 -- C Function: scm_hashx_ref (hash, assoc, table, key, dflt)
     Lookup KEY in the given hash TABLE, and return the associated value.  If KEY is not found, return DFLT, or #f if DFLT is not given.

 -- Scheme Procedure: hash-set! table key val
 -- Scheme Procedure: hashq-set! table key val
 -- Scheme Procedure: hashv-set! table key val
 -- Scheme Procedure: hashx-set! hash assoc table key val
 -- C Function: scm_hash_set_x (table, key, val)
 -- C Function: scm_hashq_set_x (table, key, val)
 -- C Function: scm_hashv_set_x (table, key, val)
 -- C Function: scm_hashx_set_x (hash, assoc, table, key, val)
     Associate VAL with KEY in the given hash TABLE.  If KEY is already present then it's associated value is changed. If it's not present then a new entry is created.

 -- Scheme Procedure: hash-remove! table key
 -- Scheme Procedure: hashq-remove! table key
 -- Scheme Procedure: hashv-remove! table key
 -- Scheme Procedure: hashx-remove! hash assoc table key
 -- C Function: scm_hash_remove_x (table, key)
 -- C Function: scm_hashq_remove_x (table, key)
 -- C Function: scm_hashv_remove_x (table, key)
 -- C Function: scm_hashx_remove_x (hash, assoc, table, key)
     Remove any association for KEY in the given hash TABLE. If KEY is not in TABLE then nothing is done.

 -- Scheme Procedure: hash key size
 -- Scheme Procedure: hashq key size
 -- Scheme Procedure: hashv key size
 -- C Function: scm_hash (key, size)
 -- C Function: scm_hashq (key, size)
 -- C Function: scm_hashv (key, size)
     Return a hash value for KEY.  This is a number in the range 0 to SIZE-1, which is suitable for use in a hash table of the given SIZE.

     Note that hashq and hashv may use internal addresses of objects, so if an object is garbage collected and re-created it can have a different hash value, even when the two are notionally eq?.  For instance with symbols,

          (hashq 'something 123)   => 19
          (gc)
          (hashq 'something 123)   => 62

     In normal use this is not a problem, since an object entered into a hash table won't be garbage collected until removed.  It's only if hashing calculations are somehow separated from normal references that its lifetime needs to be considered.

 -- Scheme Procedure: hash-get-handle table key
 -- Scheme Procedure: hashq-get-handle table key
 -- Scheme Procedure: hashv-get-handle table key
 -- Scheme Procedure: hashx-get-handle hash assoc table key
 -- C Function: scm_hash_get_handle (table, key)
 -- C Function: scm_hashq_get_handle (table, key)
 -- C Function: scm_hashv_get_handle (table, key)
 -- C Function: scm_hashx_get_handle (hash, assoc, table, key)
     Return the (KEY . VALUE) pair for KEY in the given hash TABLE, or #f if KEY is not in TABLE.

 -- Scheme Procedure: hash-create-handle! table key init
 -- Scheme Procedure: hashq-create-handle! table key init
 -- Scheme Procedure: hashv-create-handle! table key init
 -- Scheme Procedure: hashx-create-handle! hash assoc table key init
 -- C Function: scm_hash_create_handle_x (table, key, init)
 -- C Function: scm_hashq_create_handle_x (table, key, init)
 -- C Function: scm_hashv_create_handle_x (table, key, init)
 -- C Function: scm_hashx_create_handle_x (hash, assoc, table, key, init)
     Return the (KEY . VALUE) pair for KEY in the given hash TABLE.  If KEY is not in TABLE then create an entry for it with INIT as the value, and return that pair.

 -- Scheme Procedure: hash-map->list proc table
 -- Scheme Procedure: hash-for-each proc table
 -- C Function: scm_hash_map_to_list (proc, table)
 -- C Function: scm_hash_for_each (proc, table)
     Apply PROC to the entries in the given hash TABLE.  Each call is (PROC KEY VALUE).  hash-map->list returns a list of the results from these calls, hash-for-each discards the results and returns an unspecified value.

     Calls are made over the table entries in an unspecified order, and for hash-map->list the order of the values in the returned list is unspecified.  Results will be unpredictable if TABLE is modified while iterating.

     For example the following returns a new alist comprising all the entries from mytable, in no particular order.

          (hash-map->list cons mytable)

 -- Scheme Procedure: hash-for-each-handle proc table
 -- C Function: scm_hash_for_each_handle (proc, table)
     Apply PROC to the entries in the given hash TABLE.  Each call is (PROC HANDLE), where HANDLE is a (KEY . VALUE) pair. Return an unspecified value.

     hash-for-each-handle differs from hash-for-each only in the argument list of PROC.

 -- Scheme Procedure: hash-fold proc init table
 -- C Function: scm_hash_fold (proc, init, table)
     Accumulate a result by applying PROC to the elements of the given hash TABLE.  Each call is (PROC KEY VALUE PRIOR-RESULT), where KEY and VALUE are from the TABLE and PRIOR-RESULT is the return from the previous PROC call.  For the first call, PRIOR-RESULT is the given INIT value.

     Calls are made over the table entries in an unspecified order. Results will be unpredictable if TABLE is modified while hash-fold is running.

     For example, the following returns a count of how many keys in mytable are strings.

          (hash-fold (lambda (key value prior)
                       (if (string? key) (1+ prior) prior))
                     0 mytable)