@c -*-texinfo-*-
@c This is part of the GNU Guile Reference Manual.
-@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2009
-@c Free Software Foundation, Inc.
+@c Copyright (C) 1996, 1997, 2000, 2001, 2002, 2003, 2004, 2005, 2006,
+@c 2007, 2009, 2010, 2011, 2012 Free Software Foundation, Inc.
@c See the file guile.texi for copying conditions.
-@page
@node Compound Data Types
@section Compound Data Types
* Pairs:: Scheme's basic building block.
* Lists:: Special list functions supported by Guile.
* Vectors:: One-dimensional arrays of Scheme objects.
-* Uniform Numeric Vectors:: Vectors with elements of a single numeric type.
* Bit Vectors:: Vectors of bits.
* Generalized Vectors:: Treating all vector-like things uniformly.
* Arrays:: Matrices, etc.
+* VLists:: Vector-like lists.
* Records::
* Structures::
* Dictionary Types:: About dictionary types in general.
* Association Lists:: List-based dictionaries.
+* VHashes:: VList-based dictionaries.
* Hash Tables:: Table-based dictionaries.
@end menu
@c no-op since it does nothing but return the list the caller must
@c have already created.
@c
-@deffn {Scheme Procedure} list elem1 @dots{} elemN
+@deffn {Scheme Procedure} list elem @dots{}
@deffnx {C Function} scm_list_1 (elem1)
@deffnx {C Function} scm_list_2 (elem1, elem2)
@deffnx {C Function} scm_list_3 (elem1, elem2, elem3)
@deffnx {C Function} scm_list_5 (elem1, elem2, elem3, elem4, elem5)
@deffnx {C Function} scm_list_n (elem1, @dots{}, elemN, @nicode{SCM_UNDEFINED})
@rnindex list
-Return a new list containing elements @var{elem1} to @var{elemN}.
+Return a new list containing elements @var{elem} @enddots{}.
@code{scm_list_n} takes a variable number of arguments, terminated by
the special @code{SCM_UNDEFINED}. That final @code{SCM_UNDEFINED} is
-not included in the list. None of @var{elem1} to @var{elemN} can
+not included in the list. None of @var{elem} @dots{} can
themselves be @code{SCM_UNDEFINED}, or @code{scm_list_n} will
terminate at that point.
@end deffn
variants.
@rnindex append
-@deffn {Scheme Procedure} append lst1 @dots{} lstN
-@deffnx {Scheme Procedure} append! lst1 @dots{} lstN
+@deffn {Scheme Procedure} append lst @dots{} obj
+@deffnx {Scheme Procedure} append
+@deffnx {Scheme Procedure} append! lst @dots{} obj
+@deffnx {Scheme Procedure} append!
@deffnx {C Function} scm_append (lstlst)
@deffnx {C Function} scm_append_x (lstlst)
-Return a list comprising all the elements of lists @var{lst1} to
-@var{lstN}.
+Return a list comprising all the elements of lists @var{lst} @dots{}
+@var{obj}. If called with no arguments, return the empty list.
@lisp
(append '(x) '(y)) @result{} (x y)
(append '(a (b)) '((c))) @result{} (a (b) (c))
@end lisp
-The last argument @var{lstN} may actually be any object; an improper
+The last argument @var{obj} may actually be any object; an improper
list results if the last argument is not a proper list.
@lisp
@end lisp
@code{append} doesn't modify the given lists, but the return may share
-structure with the final @var{lstN}. @code{append!} modifies the
+structure with the final @var{obj}. @code{append!} modifies the
given lists to form its return.
For @code{scm_append} and @code{scm_append_x}, @var{lstlst} is a list
-of the list operands @var{lst1} @dots{} @var{lstN}. That @var{lstlst}
+of the list operands @var{lst} @dots{} @var{obj}. That @var{lstlst}
itself is not modified or used in the return.
@end deffn
@code{reverse} constructs a new list, @code{reverse!} modifies
@var{lst} in constructing its return.
-For @code{reverse!}, the optional @var{newtail} is appended to to the
+For @code{reverse!}, the optional @var{newtail} is appended to the
result. @var{newtail} isn't reversed, it simply becomes the list
tail. For @code{scm_reverse_x}, the @var{newtail} parameter is
mandatory, but can be @code{SCM_EOL} if no further tail is required.
* Vector Creation:: Dynamic vector creation and validation.
* Vector Accessors:: Accessing and modifying vector contents.
* Vector Accessing from C:: Ways to work with vectors from C.
+* Uniform Numeric Vectors:: Vectors of unboxed numeric values.
@end menu
@rnindex vector
@rnindex list->vector
-@deffn {Scheme Procedure} vector . l
+@deffn {Scheme Procedure} vector arg @dots{}
@deffnx {Scheme Procedure} list->vector l
@deffnx {C Function} scm_vector (l)
Return a newly allocated vector composed of the
@rnindex vector-length
@deffn {Scheme Procedure} vector-length vector
-@deffnx {C Function} scm_vector_length vector
+@deffnx {C Function} scm_vector_length (vector)
Return the number of elements in @var{vector} as an exact integer.
@end deffn
-@deftypefn {C Function} size_t scm_c_vector_length (SCM v)
-Return the number of elements in @var{vector} as a @code{size_t}.
+@deftypefn {C Function} size_t scm_c_vector_length (SCM vec)
+Return the number of elements in @var{vec} as a @code{size_t}.
@end deftypefn
@rnindex vector-ref
-@deffn {Scheme Procedure} vector-ref vector k
-@deffnx {C Function} scm_vector_ref vector k
-Return the contents of position @var{k} of @var{vector}.
-@var{k} must be a valid index of @var{vector}.
+@deffn {Scheme Procedure} vector-ref vec k
+@deffnx {C Function} scm_vector_ref (vec, k)
+Return the contents of position @var{k} of @var{vec}.
+@var{k} must be a valid index of @var{vec}.
@lisp
(vector-ref '#(1 1 2 3 5 8 13 21) 5) @result{} 8
(vector-ref '#(1 1 2 3 5 8 13 21)
@end lisp
@end deffn
-@deftypefn {C Function} SCM scm_c_vector_ref (SCM v, size_t k)
+@deftypefn {C Function} SCM scm_c_vector_ref (SCM vec, size_t k)
Return the contents of position @var{k} (a @code{size_t}) of
-@var{vector}.
+@var{vec}.
@end deftypefn
A vector created by one of the dynamic vector constructor procedures
error.
@rnindex vector-set!
-@deffn {Scheme Procedure} vector-set! vector k obj
-@deffnx {C Function} scm_vector_set_x vector k obj
-Store @var{obj} in position @var{k} of @var{vector}.
-@var{k} must be a valid index of @var{vector}.
+@deffn {Scheme Procedure} vector-set! vec k obj
+@deffnx {C Function} scm_vector_set_x (vec, k, obj)
+Store @var{obj} in position @var{k} of @var{vec}.
+@var{k} must be a valid index of @var{vec}.
The value returned by @samp{vector-set!} is unspecified.
@lisp
(let ((vec (vector 0 '(2 2 2 2) "Anna")))
@end lisp
@end deffn
-@deftypefn {C Function} void scm_c_vector_set_x (SCM v, size_t k, SCM obj)
-Store @var{obj} in position @var{k} (a @code{size_t}) of @var{v}.
+@deftypefn {C Function} void scm_c_vector_set_x (SCM vec, size_t k, SCM obj)
+Store @var{obj} in position @var{k} (a @code{size_t}) of @var{vec}.
@end deftypefn
@rnindex vector-fill!
-@deffn {Scheme Procedure} vector-fill! v fill
-@deffnx {C Function} scm_vector_fill_x (v, fill)
-Store @var{fill} in every position of @var{vector}. The value
+@deffn {Scheme Procedure} vector-fill! vec fill
+@deffnx {C Function} scm_vector_fill_x (vec, fill)
+Store @var{fill} in every position of @var{vec}. The value
returned by @code{vector-fill!} is unspecified.
@end deffn
@end deftypefn
@deftypefn {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 @var{vec} and return a pointer to the
+Acquire a handle for the vector @var{vec} and return a pointer to the
elements of it. This pointer can only be used to read the elements of
@var{vec}. When @var{vec} is not a vector, an error is signaled. The
-handle mustr eventually be released with
+handle must eventually be released with
@code{scm_array_handle_release}.
The variables pointed to by @var{lenp} and @var{incp} are filled with
@end deftypefn
@node Uniform Numeric Vectors
-@subsection Uniform Numeric Vectors
+@subsubsection 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.
-
-Strings could be regarded as uniform vectors of characters,
-@xref{Strings}. Likewise, bit vectors could be regarded as uniform
-vectors of bits, @xref{Bit Vectors}. Both are sufficiently different
-from uniform numeric vectors that the procedures described here do not
-apply to these two data types. However, both strings and bit vectors
-are generalized vectors, @xref{Generalized Vectors}, and arrays,
-@xref{Arrays}.
-
-Uniform numeric vectors are the special case of one dimensional uniform
-numeric arrays.
-
-Uniform numeric vectors can be useful since they consume less memory
-than the non-uniform, general vectors. Also, since the types they can
-store correspond directly to C types, it is easier to work with them
-efficiently on a low level. Consider image processing as an example,
-where you want to apply a filter to some image. While you could store
-the pixels of an image in a general vector and write a general
-convolution function, things are much more efficient with uniform
-vectors: the convolution function knows that all pixels are unsigned
-8-bit values (say), and can use a very tight inner loop.
-
-That is, when it is written in C. Functions for efficiently working
-with uniform numeric vectors from C are listed at the end of this
-section.
-
-Procedures similar to the vector procedures (@pxref{Vectors}) are
-provided for handling these uniform vectors, but they are distinct
-datatypes and the two cannot be inter-mixed. If you want to work
-primarily with uniform numeric vectors, but want to offer support for
-general vectors as a convenience, you can use one of the
-@code{scm_any_to_*} functions. They will coerce lists and vectors to
-the given type of uniform vector. Alternatively, you can write two
-versions of your code: one that is fast and works only with uniform
-numeric vectors, and one that works with any kind of vector but is
-slower.
-
-One set of the procedures listed below is a generic one: it works with
-all types of uniform numeric vectors. In addition to that, there is a
-set of procedures for each type that only works with that type. Unless
-you really need to the generality of the first set, it is best to use
-the more specific functions. They might not be that much faster, but
-their use can serve as a kind of declaration and makes it easier to
-optimize later on.
-
-The generic set of procedures uses @code{uniform} in its names, the
-specific ones use the tag from the following table.
-
-@table @nicode
-@item u8
-unsigned 8-bit integers
-
-@item s8
-signed 8-bit integers
-
-@item u16
-unsigned 16-bit integers
-
-@item s16
-signed 16-bit integers
-
-@item u32
-unsigned 32-bit integers
-
-@item s32
-signed 32-bit integers
-
-@item u64
-unsigned 64-bit integers
-
-@item s64
-signed 64-bit integers
-
-@item f32
-the C type @code{float}
-
-@item f64
-the C type @code{double}
-
-@item c32
-complex numbers in rectangular form with the real and imaginary part
-being a @code{float}
-
-@item c64
-complex numbers in rectangular form with the real and imaginary part
-being a @code{double}
-
-@end table
-
-The external representation (ie.@: read syntax) for these vectors is
-similar to normal Scheme vectors, but with an additional tag from the
-table above indiciating the vector's type. For example,
-
-@lisp
-#u16(1 2 3)
-#f64(3.1415 2.71)
-@end lisp
-
-Note that the read syntax for floating-point here conflicts with
-@code{#f} for false. In Standard Scheme one can write @code{(1 #f3)}
-for a three element list @code{(1 #f 3)}, but for Guile @code{(1 #f3)}
-is invalid. @code{(1 #f 3)} is almost certainly what one should write
-anyway to make the intention clear, so this is rarely a problem.
-
-@deffn {Scheme Procedure} uniform-vector? obj
-@deffnx {Scheme Procedure} u8vector? obj
-@deffnx {Scheme Procedure} s8vector? obj
-@deffnx {Scheme Procedure} u16vector? obj
-@deffnx {Scheme Procedure} s16vector? obj
-@deffnx {Scheme Procedure} u32vector? obj
-@deffnx {Scheme Procedure} s32vector? obj
-@deffnx {Scheme Procedure} u64vector? obj
-@deffnx {Scheme Procedure} s64vector? obj
-@deffnx {Scheme Procedure} f32vector? obj
-@deffnx {Scheme Procedure} f64vector? obj
-@deffnx {Scheme Procedure} c32vector? obj
-@deffnx {Scheme Procedure} c64vector? obj
-@deffnx {C Function} scm_uniform_vector_p (obj)
-@deffnx {C Function} scm_u8vector_p (obj)
-@deffnx {C Function} scm_s8vector_p (obj)
-@deffnx {C Function} scm_u16vector_p (obj)
-@deffnx {C Function} scm_s16vector_p (obj)
-@deffnx {C Function} scm_u32vector_p (obj)
-@deffnx {C Function} scm_s32vector_p (obj)
-@deffnx {C Function} scm_u64vector_p (obj)
-@deffnx {C Function} scm_s64vector_p (obj)
-@deffnx {C Function} scm_f32vector_p (obj)
-@deffnx {C Function} scm_f64vector_p (obj)
-@deffnx {C Function} scm_c32vector_p (obj)
-@deffnx {C Function} scm_c64vector_p (obj)
-Return @code{#t} if @var{obj} is a homogeneous numeric vector of the
-indicated type.
-@end deffn
-
-@deffn {Scheme Procedure} make-u8vector n [value]
-@deffnx {Scheme Procedure} make-s8vector n [value]
-@deffnx {Scheme Procedure} make-u16vector n [value]
-@deffnx {Scheme Procedure} make-s16vector n [value]
-@deffnx {Scheme Procedure} make-u32vector n [value]
-@deffnx {Scheme Procedure} make-s32vector n [value]
-@deffnx {Scheme Procedure} make-u64vector n [value]
-@deffnx {Scheme Procedure} make-s64vector n [value]
-@deffnx {Scheme Procedure} make-f32vector n [value]
-@deffnx {Scheme Procedure} make-f64vector n [value]
-@deffnx {Scheme Procedure} make-c32vector n [value]
-@deffnx {Scheme Procedure} make-c64vector n [value]
-@deffnx {C Function} scm_make_u8vector n [value]
-@deffnx {C Function} scm_make_s8vector n [value]
-@deffnx {C Function} scm_make_u16vector n [value]
-@deffnx {C Function} scm_make_s16vector n [value]
-@deffnx {C Function} scm_make_u32vector n [value]
-@deffnx {C Function} scm_make_s32vector n [value]
-@deffnx {C Function} scm_make_u64vector n [value]
-@deffnx {C Function} scm_make_s64vector n [value]
-@deffnx {C Function} scm_make_f32vector n [value]
-@deffnx {C Function} scm_make_f64vector n [value]
-@deffnx {C Function} scm_make_c32vector n [value]
-@deffnx {C Function} scm_make_c64vector n [value]
-Return a newly allocated homogeneous numeric vector holding @var{n}
-elements of the indicated type. If @var{value} is given, the vector
-is initialized with that value, otherwise the contents are
-unspecified.
-@end deffn
-
-@deffn {Scheme Procedure} u8vector value @dots{}
-@deffnx {Scheme Procedure} s8vector value @dots{}
-@deffnx {Scheme Procedure} u16vector value @dots{}
-@deffnx {Scheme Procedure} s16vector value @dots{}
-@deffnx {Scheme Procedure} u32vector value @dots{}
-@deffnx {Scheme Procedure} s32vector value @dots{}
-@deffnx {Scheme Procedure} u64vector value @dots{}
-@deffnx {Scheme Procedure} s64vector value @dots{}
-@deffnx {Scheme Procedure} f32vector value @dots{}
-@deffnx {Scheme Procedure} f64vector value @dots{}
-@deffnx {Scheme Procedure} c32vector value @dots{}
-@deffnx {Scheme Procedure} c64vector value @dots{}
-@deffnx {C Function} scm_u8vector (values)
-@deffnx {C Function} scm_s8vector (values)
-@deffnx {C Function} scm_u16vector (values)
-@deffnx {C Function} scm_s16vector (values)
-@deffnx {C Function} scm_u32vector (values)
-@deffnx {C Function} scm_s32vector (values)
-@deffnx {C Function} scm_u64vector (values)
-@deffnx {C Function} scm_s64vector (values)
-@deffnx {C Function} scm_f32vector (values)
-@deffnx {C Function} scm_f64vector (values)
-@deffnx {C Function} scm_c32vector (values)
-@deffnx {C Function} scm_c64vector (values)
-Return a newly allocated homogeneous numeric vector of the indicated
-type, holding the given parameter @var{value}s. The vector length is
-the number of parameters given.
-@end deffn
-
-@deffn {Scheme Procedure} uniform-vector-length vec
-@deffnx {Scheme Procedure} u8vector-length vec
-@deffnx {Scheme Procedure} s8vector-length vec
-@deffnx {Scheme Procedure} u16vector-length vec
-@deffnx {Scheme Procedure} s16vector-length vec
-@deffnx {Scheme Procedure} u32vector-length vec
-@deffnx {Scheme Procedure} s32vector-length vec
-@deffnx {Scheme Procedure} u64vector-length vec
-@deffnx {Scheme Procedure} s64vector-length vec
-@deffnx {Scheme Procedure} f32vector-length vec
-@deffnx {Scheme Procedure} f64vector-length vec
-@deffnx {Scheme Procedure} c32vector-length vec
-@deffnx {Scheme Procedure} c64vector-length vec
-@deffnx {C Function} scm_uniform_vector_length (vec)
-@deffnx {C Function} scm_u8vector_length (vec)
-@deffnx {C Function} scm_s8vector_length (vec)
-@deffnx {C Function} scm_u16vector_length (vec)
-@deffnx {C Function} scm_s16vector_length (vec)
-@deffnx {C Function} scm_u32vector_length (vec)
-@deffnx {C Function} scm_s32vector_length (vec)
-@deffnx {C Function} scm_u64vector_length (vec)
-@deffnx {C Function} scm_s64vector_length (vec)
-@deffnx {C Function} scm_f32vector_length (vec)
-@deffnx {C Function} scm_f64vector_length (vec)
-@deffnx {C Function} scm_c32vector_length (vec)
-@deffnx {C Function} scm_c64vector_length (vec)
-Return the number of elements in @var{vec}.
-@end deffn
-
-@deffn {Scheme Procedure} uniform-vector-ref vec i
-@deffnx {Scheme Procedure} u8vector-ref vec i
-@deffnx {Scheme Procedure} s8vector-ref vec i
-@deffnx {Scheme Procedure} u16vector-ref vec i
-@deffnx {Scheme Procedure} s16vector-ref vec i
-@deffnx {Scheme Procedure} u32vector-ref vec i
-@deffnx {Scheme Procedure} s32vector-ref vec i
-@deffnx {Scheme Procedure} u64vector-ref vec i
-@deffnx {Scheme Procedure} s64vector-ref vec i
-@deffnx {Scheme Procedure} f32vector-ref vec i
-@deffnx {Scheme Procedure} f64vector-ref vec i
-@deffnx {Scheme Procedure} c32vector-ref vec i
-@deffnx {Scheme Procedure} c64vector-ref vec i
-@deffnx {C Function} scm_uniform_vector_ref (vec i)
-@deffnx {C Function} scm_u8vector_ref (vec i)
-@deffnx {C Function} scm_s8vector_ref (vec i)
-@deffnx {C Function} scm_u16vector_ref (vec i)
-@deffnx {C Function} scm_s16vector_ref (vec i)
-@deffnx {C Function} scm_u32vector_ref (vec i)
-@deffnx {C Function} scm_s32vector_ref (vec i)
-@deffnx {C Function} scm_u64vector_ref (vec i)
-@deffnx {C Function} scm_s64vector_ref (vec i)
-@deffnx {C Function} scm_f32vector_ref (vec i)
-@deffnx {C Function} scm_f64vector_ref (vec i)
-@deffnx {C Function} scm_c32vector_ref (vec i)
-@deffnx {C Function} scm_c64vector_ref (vec i)
-Return the element at index @var{i} in @var{vec}. The first element
-in @var{vec} is index 0.
-@end deffn
-
-@deffn {Scheme Procedure} uniform-vector-set! vec i value
-@deffnx {Scheme Procedure} u8vector-set! vec i value
-@deffnx {Scheme Procedure} s8vector-set! vec i value
-@deffnx {Scheme Procedure} u16vector-set! vec i value
-@deffnx {Scheme Procedure} s16vector-set! vec i value
-@deffnx {Scheme Procedure} u32vector-set! vec i value
-@deffnx {Scheme Procedure} s32vector-set! vec i value
-@deffnx {Scheme Procedure} u64vector-set! vec i value
-@deffnx {Scheme Procedure} s64vector-set! vec i value
-@deffnx {Scheme Procedure} f32vector-set! vec i value
-@deffnx {Scheme Procedure} f64vector-set! vec i value
-@deffnx {Scheme Procedure} c32vector-set! vec i value
-@deffnx {Scheme Procedure} c64vector-set! vec i value
-@deffnx {C Function} scm_uniform_vector_set_x (vec i value)
-@deffnx {C Function} scm_u8vector_set_x (vec i value)
-@deffnx {C Function} scm_s8vector_set_x (vec i value)
-@deffnx {C Function} scm_u16vector_set_x (vec i value)
-@deffnx {C Function} scm_s16vector_set_x (vec i value)
-@deffnx {C Function} scm_u32vector_set_x (vec i value)
-@deffnx {C Function} scm_s32vector_set_x (vec i value)
-@deffnx {C Function} scm_u64vector_set_x (vec i value)
-@deffnx {C Function} scm_s64vector_set_x (vec i value)
-@deffnx {C Function} scm_f32vector_set_x (vec i value)
-@deffnx {C Function} scm_f64vector_set_x (vec i value)
-@deffnx {C Function} scm_c32vector_set_x (vec i value)
-@deffnx {C Function} scm_c64vector_set_x (vec i value)
-Set the element at index @var{i} in @var{vec} to @var{value}. The
-first element in @var{vec} is index 0. The return value is
-unspecified.
-@end deffn
-
-@deffn {Scheme Procedure} uniform-vector->list vec
-@deffnx {Scheme Procedure} u8vector->list vec
-@deffnx {Scheme Procedure} s8vector->list vec
-@deffnx {Scheme Procedure} u16vector->list vec
-@deffnx {Scheme Procedure} s16vector->list vec
-@deffnx {Scheme Procedure} u32vector->list vec
-@deffnx {Scheme Procedure} s32vector->list vec
-@deffnx {Scheme Procedure} u64vector->list vec
-@deffnx {Scheme Procedure} s64vector->list vec
-@deffnx {Scheme Procedure} f32vector->list vec
-@deffnx {Scheme Procedure} f64vector->list vec
-@deffnx {Scheme Procedure} c32vector->list vec
-@deffnx {Scheme Procedure} c64vector->list vec
-@deffnx {C Function} scm_uniform_vector_to_list (vec)
-@deffnx {C Function} scm_u8vector_to_list (vec)
-@deffnx {C Function} scm_s8vector_to_list (vec)
-@deffnx {C Function} scm_u16vector_to_list (vec)
-@deffnx {C Function} scm_s16vector_to_list (vec)
-@deffnx {C Function} scm_u32vector_to_list (vec)
-@deffnx {C Function} scm_s32vector_to_list (vec)
-@deffnx {C Function} scm_u64vector_to_list (vec)
-@deffnx {C Function} scm_s64vector_to_list (vec)
-@deffnx {C Function} scm_f32vector_to_list (vec)
-@deffnx {C Function} scm_f64vector_to_list (vec)
-@deffnx {C Function} scm_c32vector_to_list (vec)
-@deffnx {C Function} scm_c64vector_to_list (vec)
-Return a newly allocated list holding all elements of @var{vec}.
-@end deffn
-
-@deffn {Scheme Procedure} list->u8vector lst
-@deffnx {Scheme Procedure} list->s8vector lst
-@deffnx {Scheme Procedure} list->u16vector lst
-@deffnx {Scheme Procedure} list->s16vector lst
-@deffnx {Scheme Procedure} list->u32vector lst
-@deffnx {Scheme Procedure} list->s32vector lst
-@deffnx {Scheme Procedure} list->u64vector lst
-@deffnx {Scheme Procedure} list->s64vector lst
-@deffnx {Scheme Procedure} list->f32vector lst
-@deffnx {Scheme Procedure} list->f64vector lst
-@deffnx {Scheme Procedure} list->c32vector lst
-@deffnx {Scheme Procedure} list->c64vector lst
-@deffnx {C Function} scm_list_to_u8vector (lst)
-@deffnx {C Function} scm_list_to_s8vector (lst)
-@deffnx {C Function} scm_list_to_u16vector (lst)
-@deffnx {C Function} scm_list_to_s16vector (lst)
-@deffnx {C Function} scm_list_to_u32vector (lst)
-@deffnx {C Function} scm_list_to_s32vector (lst)
-@deffnx {C Function} scm_list_to_u64vector (lst)
-@deffnx {C Function} scm_list_to_s64vector (lst)
-@deffnx {C Function} scm_list_to_f32vector (lst)
-@deffnx {C Function} scm_list_to_f64vector (lst)
-@deffnx {C Function} scm_list_to_c32vector (lst)
-@deffnx {C Function} scm_list_to_c64vector (lst)
-Return a newly allocated homogeneous numeric vector of the indicated type,
-initialized with the elements of the list @var{lst}.
-@end deffn
-
-@deffn {Scheme Procedure} any->u8vector obj
-@deffnx {Scheme Procedure} any->s8vector obj
-@deffnx {Scheme Procedure} any->u16vector obj
-@deffnx {Scheme Procedure} any->s16vector obj
-@deffnx {Scheme Procedure} any->u32vector obj
-@deffnx {Scheme Procedure} any->s32vector obj
-@deffnx {Scheme Procedure} any->u64vector obj
-@deffnx {Scheme Procedure} any->s64vector obj
-@deffnx {Scheme Procedure} any->f32vector obj
-@deffnx {Scheme Procedure} any->f64vector obj
-@deffnx {Scheme Procedure} any->c32vector obj
-@deffnx {Scheme Procedure} any->c64vector obj
-@deffnx {C Function} scm_any_to_u8vector (obj)
-@deffnx {C Function} scm_any_to_s8vector (obj)
-@deffnx {C Function} scm_any_to_u16vector (obj)
-@deffnx {C Function} scm_any_to_s16vector (obj)
-@deffnx {C Function} scm_any_to_u32vector (obj)
-@deffnx {C Function} scm_any_to_s32vector (obj)
-@deffnx {C Function} scm_any_to_u64vector (obj)
-@deffnx {C Function} scm_any_to_s64vector (obj)
-@deffnx {C Function} scm_any_to_f32vector (obj)
-@deffnx {C Function} scm_any_to_f64vector (obj)
-@deffnx {C Function} scm_any_to_c32vector (obj)
-@deffnx {C Function} scm_any_to_c64vector (obj)
-Return a (maybe newly allocated) uniform numeric vector of the indicated
-type, initialized with the elements of @var{obj}, which must be a list,
-a vector, or a uniform vector. When @var{obj} is already a suitable
-uniform numeric vector, it is returned unchanged.
-@end deffn
-
-@deftypefn {C Function} int scm_is_uniform_vector (SCM uvec)
-Return non-zero when @var{uvec} is a uniform numeric vector, zero
-otherwise.
-@end deftypefn
-
-@deftypefn {C Function} SCM scm_take_u8vector (const scm_t_uint8 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_s8vector (const scm_t_int8 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_u16vector (const scm_t_uint16 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_s16vector (const scm_t_int16 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_u32vector (const scm_t_uint32 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_s32vector (const scm_t_int32 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_u64vector (const scm_t_uint64 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_s64vector (const scm_t_int64 *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_f32vector (const float *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_f64vector (const double *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_c32vector (const float *data, size_t len)
-@deftypefnx {C Function} SCM scm_take_c64vector (const double *data, size_t len)
-Return a new uniform numeric vector of the indicated type and length
-that uses the memory pointed to by @var{data} to store its elements.
-This memory will eventually be freed with @code{free}. The argument
-@var{len} specifies the number of elements in @var{data}, not its size
-in bytes.
-
-The @code{c32} and @code{c64} variants take a pointer to a C array of
-@code{float}s or @code{double}s. The real parts of the complex numbers
-are at even indices in that array, the corresponding imaginary parts are
-at the following odd index.
-@end deftypefn
-
-@deftypefn {C Function} size_t scm_c_uniform_vector_length (SCM uvec)
-Return the number of elements of @var{uvec} as a @code{size_t}.
-@end deftypefn
-
-@deftypefn {C Function} {const void *} scm_uniform_vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_uint8 *} scm_u8vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_int8 *} scm_s8vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_uint16 *} scm_u16vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_int16 *} scm_s16vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_uint32 *} scm_u32vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_int32 *} scm_s32vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_uint64 *} scm_u64vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const scm_t_int64 *} scm_s64vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const float *} scm_f23vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const double *} scm_f64vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const float *} scm_c32vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {const double *} scm_c64vector_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-Like @code{scm_vector_elements} (@pxref{Vector Accessing from C}), but
-returns a pointer to the elements of a uniform numeric vector of the
-indicated kind.
-@end deftypefn
-
-@deftypefn {C Function} {void *} scm_uniform_vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_uint8 *} scm_u8vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_int8 *} scm_s8vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_uint16 *} scm_u16vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_int16 *} scm_s16vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_uint32 *} scm_u32vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_int32 *} scm_s32vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_uint64 *} scm_u64vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {scm_t_int64 *} scm_s64vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {float *} scm_f23vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {double *} scm_f64vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {float *} scm_c32vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-@deftypefnx {C Function} {double *} scm_c64vector_writable_elements (SCM vec, scm_t_array_handle *handle, size_t *lenp, ssize_t *incp)
-Like @code{scm_vector_writable_elements} (@pxref{Vector Accessing from
-C}), but returns a pointer to the elements of a uniform numeric vector
-of the indicated kind.
-@end deftypefn
-
-Uniform numeric vectors can be written to and read from input/output
-ports using the procedures listed below. However, bytevectors may often
-be more convenient for binary input/output since they provide more
-flexibility in the interpretation of raw byte sequences
-(@pxref{Bytevectors}).
-
-@deffn {Scheme Procedure} uniform-vector-read! uvec [port_or_fd [start [end]]]
-@deffnx {C Function} scm_uniform_vector_read_x (uvec, port_or_fd, start, end)
-Fill the elements of @var{uvec} by reading
-raw bytes from @var{port-or-fdes}, using host byte order.
-
-The optional arguments @var{start} (inclusive) and @var{end}
-(exclusive) allow a specified region to be read,
-leaving the remainder of the vector unchanged.
-
-When @var{port-or-fdes} is a port, all specified elements
-of @var{uvec} are attempted to be read, potentially blocking
-while waiting formore input or end-of-file.
-When @var{port-or-fd} is an integer, a single call to
-read(2) is made.
-
-An error is signalled when the last element has only
-been partially filled before reaching end-of-file or in
-the single call to read(2).
-
-@code{uniform-vector-read!} returns the number of elements
-read.
-
-@var{port-or-fdes} may be omitted, in which case it defaults
-to the value returned by @code{(current-input-port)}.
-@end deffn
-
-@deffn {Scheme Procedure} uniform-vector-write uvec [port_or_fd [start [end]]]
-@deffnx {C Function} scm_uniform_vector_write (uvec, port_or_fd, start, end)
-Write the elements of @var{uvec} as raw bytes to
-@var{port-or-fdes}, in the host byte order.
-
-The optional arguments @var{start} (inclusive)
-and @var{end} (exclusive) allow
-a specified region to be written.
-
-When @var{port-or-fdes} is a port, all specified elements
-of @var{uvec} are attempted to be written, potentially blocking
-while waiting for more room.
-When @var{port-or-fd} is an integer, a single call to
-write(2) is made.
-
-An error is signalled when the last element has only
-been partially written in the single call to write(2).
-
-The number of objects actually written is returned.
-@var{port-or-fdes} may be
-omitted, in which case it defaults to the value returned by
-@code{(current-output-port)}.
-@end deffn
+sizes. @xref{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.
+@xref{Bytevectors}, for more information on bytevectors.
@node Bit Vectors
@subsection Bit Vectors
#*00000000
@end example
-Bit vectors are are also generalized vectors, @xref{Generalized
+Bit vectors are also generalized vectors, @xref{Generalized
Vectors}, and can thus be used with the array procedures, @xref{Arrays}.
Bit vectors are the special case of one dimensional bit arrays.
@code{size_t}.
@end deftypefn
-@deffn {Scheme Procedure} bitvector . bits
+@deffn {Scheme Procedure} bitvector bit @dots{}
@deffnx {C Function} scm_bitvector (bits)
Create a new bitvector with the arguments as elements.
@end deffn
@var{vec}.
@end deffn
-@deftypefn {C Function} SCM scm_c_bitvector_ref (SCM obj, size_t idx)
+@deftypefn {C Function} SCM scm_c_bitvector_ref (SCM vec, size_t idx)
Return the element at index @var{idx} of the bitvector
@var{vec}.
@end deftypefn
@var{vec} when @var{val} is true, else clear it.
@end deffn
-@deftypefn {C Function} SCM scm_c_bitvector_set_x (SCM obj, size_t idx, SCM val)
+@deftypefn {C Function} SCM scm_c_bitvector_set_x (SCM vec, size_t idx, SCM val)
Set the element at index @var{idx} of the bitvector
@var{vec} when @var{val} is true, else clear it.
@end deftypefn
@deffn {Scheme Procedure} bit-position bool bitvector start
@deffnx {C Function} scm_bit_position (bool, bitvector, start)
-Return the index of the first occurrance of @var{bool} in
+Return the index of the first occurrence of @var{bool} in
@var{bitvector}, starting from @var{start}. If there is no @var{bool}
entry between @var{start} and the end of @var{bitvector}, then return
@code{#f}. For example,
where @code{<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 dinstinguish
+origin, the rank is always printed even when it is 1 to distinguish
them from ordinary vectors.
The @code{<vectag>} part is the tag for a uniform numeric vector, like
is a uniform u8 array of rank 2 with index ranges 2..3 and 3..4.
@item #2()
-is a two-dimensional array with index ranges 0..-1 and 0..-1, i.e. both
-dimensions have length zero.
+is a two-dimensional array with index ranges 0..-1 and 0..-1, i.e.@:
+both dimensions have length zero.
@item #2:0:2()
-is a two-dimensional array with index ranges 0..-1 and 0..1, i.e. the
+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.
@item #0(12)
Create and return an array that has as many dimensions as there are
@var{bound}s and (maybe) fill it with @var{fill}.
-The underlaying storage vector is created according to @var{type},
+The underlying storage vector is created according to @var{type},
which must be a symbol whose name is the `vectag' of the array as
explained above, or @code{#t} for ordinary, non-specialized arrays.
@code{(make-typed-array 'u32 *unspecified* 4)} creates a uninitialized
@code{u32} vector of length 4.
-Each @var{bound} may be a positive non-zero integer @var{N}, in which
-case the index for that dimension can range from 0 through @var{N-1}; or
+Each @var{bound} may be a positive non-zero integer @var{n}, in which
+case the index for that dimension can range from 0 through @var{n}-1; or
an explicit index range specifier in the form @code{(LOWER UPPER)},
where both @var{lower} and @var{upper} are integers, possibly less than
zero, and possibly the same number (however, @var{lower} cannot be
@end example
@end deffn
-@deffn {Scheme Procedure} enclose-array array dim1 @dots{}
-@deffnx {C Function} scm_enclose_array (array, dimlist)
-@var{dim1}, @var{dim2} @dots{} should be nonnegative integers less than
-the rank of @var{array}. @code{enclose-array} returns an array
-resembling an array of shared arrays. The dimensions of each shared
-array are the same as the @var{dim}th dimensions of the original array,
-the dimensions of the outer array are the same as those of the original
-array that did not match a @var{dim}.
-
-An enclosed array is not a general Scheme array. Its elements may not
-be set using @code{array-set!}. Two references to the same element of
-an enclosed array will be @code{equal?} but will not in general be
-@code{eq?}. The value returned by @code{array-prototype} when given an
-enclosed array is unspecified.
-
-For example,
-
-@lisp
-(enclose-array '#3(((a b c)
- (d e f))
- ((1 2 3)
- (4 5 6)))
- 1)
-@result{}
-#<enclosed-array (#1(a d) #1(b e) #1(c f))
- (#1(1 4) #1(2 5) #1(3 6))>
-
-(enclose-array '#3(((a b c)
- (d e f))
- ((1 2 3)
- (4 5 6)))
- 1 0)
-@result{}
-#<enclosed-array #2((a 1) (d 4))
- #2((b 2) (e 5))
- #2((c 3) (f 6))>
-@end lisp
-@end deffn
-
@deffn {Scheme Procedure} array-shape array
@deffnx {Scheme Procedure} array-dimensions array
@deffnx {C Function} scm_array_dimensions (array)
-Return a list of the bounds for each dimenson of @var{array}.
+Return a list of the bounds for each dimension of @var{array}.
@code{array-shape} gives @code{(@var{lower} @var{upper})} for each
dimension. @code{array-dimensions} instead returns just
@end example
@end deffn
-@deffn {Scheme Procedure} array-rank obj
-@deffnx {C Function} scm_array_rank (obj)
+@deffn {Scheme Procedure} array-rank array
+@deffnx {C Function} scm_array_rank (array)
Return the rank of @var{array}.
@end deffn
@end deffn
@c begin (texi-doc-string "guile" "array-equal?")
-@deffn {Scheme Procedure} array-equal? array1 array2 @dots{}
+@deffn {Scheme Procedure} array-equal? array @dots{}
Return @code{#t} if all arguments are arrays with the same shape, the
same type, and have corresponding elements which are either
@code{equal?} or @code{array-equal?}. This function differs from
-@code{equal?} (@pxref{Equality}) in that a one dimensional shared
-array may be @code{array-equal?} but not @code{equal?} to a vector or
-uniform vector.
+@code{equal?} (@pxref{Equality}) in that all arguments must be arrays.
@end deffn
@c FIXME: array-map! accepts no source arrays at all, and in that
@c FIXME: array-for-each doesn't say what happens if the sources have
@c different index ranges. The code currently iterates over the
@c indices of the first and expects the others to cover those. That
-@c at least vaguely matches array-map!, but is is meant to be a
+@c at least vaguely matches array-map!, but is it meant to be a
@c documented feature?
-@deffn {Scheme Procedure} array-map! dst proc src1 @dots{} srcN
+@deffn {Scheme Procedure} array-map! dst proc src @dots{}
@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN
@deffnx {C Function} scm_array_map_x (dst, proc, srclist)
Set each element of the @var{dst} array to values obtained from calls
each @var{src}.
@end deffn
-@deffn {Scheme Procedure} array-for-each proc src1 @dots{} srcN
+@deffn {Scheme Procedure} array-for-each proc src1 src2 @dots{}
@deffnx {C Function} scm_array_for_each (proc, src1, srclist)
-Apply @var{proc} to each tuple of elements of @var{src1} @dots{}
-@var{srcN}, in row-major order. The value returned is unspecified.
+Apply @var{proc} to each tuple of elements of @var{src1} @var{src2}
+@dots{}, in row-major order. The value returned is unspecified.
@end deffn
@deffn {Scheme Procedure} array-index-map! dst proc
@deffn {Scheme Procedure} uniform-array-read! ra [port_or_fd [start [end]]]
@deffnx {C Function} scm_uniform_array_read_x (ra, port_or_fd, start, end)
-Attempt to read all elements of @var{ura}, in lexicographic order, as
-binary objects from @var{port-or-fdes}.
+Attempt to read all elements of array @var{ra}, in lexicographic order, as
+binary objects from @var{port_or_fd}.
If an end of file is encountered,
-the objects up to that point are put into @var{ura}
+the objects up to that point are put into @var{ra}
(starting at the beginning) and the remainder of the array is
unchanged.
leaving the remainder of the vector unchanged.
@code{uniform-array-read!} returns the number of objects read.
-@var{port-or-fdes} may be omitted, in which case it defaults to the value
+@var{port_or_fd} may be omitted, in which case it defaults to the value
returned by @code{(current-input-port)}.
@end deffn
-@deffn {Scheme Procedure} uniform-array-write v [port_or_fd [start [end]]]
-@deffnx {C Function} scm_uniform_array_write (v, port_or_fd, start, end)
-Writes all elements of @var{ura} as binary objects to
-@var{port-or-fdes}.
+@deffn {Scheme Procedure} uniform-array-write ra [port_or_fd [start [end]]]
+@deffnx {C Function} scm_uniform_array_write (ra, port_or_fd, start, end)
+Writes all elements of @var{ra} as binary objects to
+@var{port_or_fd}.
The optional arguments @var{start}
and @var{end} allow
a specified region of a vector (or linearized array) to be written.
The number of objects actually written is returned.
-@var{port-or-fdes} may be
+@var{port_or_fd} may be
omitted, in which case it defaults to the value returned by
@code{(current-output-port)}.
@end deffn
@deffnx {C Function} scm_make_shared_array (oldarray, mapfunc, boundlist)
Return a new array which shares the storage of @var{oldarray}.
Changes made through either affect the same underlying storage. The
-@var{bound@dots{}} arguments are the shape of the new array, the same
+@var{bound} @dots{} arguments are the shape of the new array, the same
as @code{make-array} (@pxref{Array Procedures}).
@var{mapfunc} translates coordinates from the new array to the
memory.
@end deffn
-@deffn {Scheme Procedure} transpose-array array dim1 @dots{}
+@deffn {Scheme Procedure} transpose-array array dim1 dim2 @dots{}
@deffnx {C Function} scm_transpose_array (array, dimlist)
Return an array sharing contents with @var{array}, but with
dimensions arranged in a different order. There must be one
@node Accessing Arrays from C
@subsubsection Accessing Arrays from C
-Arrays, especially uniform numeric arrays, are useful to efficiently
-represent large amounts of rectangularily organized information, such as
-matrices, images, or generally blobs of binary data. It is desirable to
-access these blobs in a C like manner so that they can be handed to
-external C code such as linear algebra libraries or image processing
-routines.
+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
Compute the position corresponding to @var{indices}, a list of
indices. The position is computed as described above for
@code{scm_array_handle_dims}. The number of the indices and their
-range is checked and an approrpiate error is signalled for invalid
+range is checked and an appropriate error is signalled for invalid
indices.
@end deftypefn
the allowed index range of the array, even for contiguous arrays.
@end deftypefn
+@node VLists
+@subsection VLists
+
+@cindex vlist
+
+The @code{(ice-9 vlist)} module provides an implementation of the @dfn{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:
+
+@itemize
+@item
+Random access has typically constant-time complexity.
+
+@item
+Computing the length of a VList has time complexity logarithmic in the number of
+elements.
+
+@item
+VLists use less storage space than standard lists.
+
+@item
+VList elements are stored in contiguous regions, which improves memory locality
+and leads to more efficient use of hardware caches.
+@end itemize
+
+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
+@code{block-growth-factor} (2 by default).
+
+The VList structure also serves as the basis for the @dfn{VList-based hash
+lists} or ``vhashes'', an immutable dictionary type (@pxref{VHashes}).
+
+However, the current implementation in @code{(ice-9 vlist)} has several
+noteworthy shortcomings:
+
+@itemize
+
+@item
+It is @emph{not} thread-safe. Although operations on vlists are all
+@dfn{referentially transparent} (i.e., purely functional), adding elements to a
+vlist with @code{vlist-cons} mutates part of its internal structure, which makes
+it non-thread-safe. This could be fixed, but it would slow down
+@code{vlist-cons}.
+
+@item
+@code{vlist-cons} always allocates at least as much memory as @code{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.
+
+@item
+@code{vlist-cons} is a Scheme procedure compiled to bytecode, and it does not
+compete with the straightforward C implementation of @code{cons}, and with the
+fact that the VM has a special @code{cons} instruction.
+
+@end itemize
+
+We hope to address these in the future.
+
+The programming interface exported by @code{(ice-9 vlist)} is defined below.
+Most of it is the same as SRFI-1 with an added @code{vlist-} prefix to function
+names.
+
+@deffn {Scheme Procedure} vlist? obj
+Return true if @var{obj} is a VList.
+@end deffn
+
+@defvr {Scheme Variable} vlist-null
+The empty VList. Note that it's possible to create an empty VList not
+@code{eq?} to @code{vlist-null}; thus, callers should always use
+@code{vlist-null?} when testing whether a VList is empty.
+@end defvr
+
+@deffn {Scheme Procedure} vlist-null? vlist
+Return true if @var{vlist} is empty.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-cons item vlist
+Return a new vlist with @var{item} as its head and @var{vlist} as its tail.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-head vlist
+Return the head of @var{vlist}.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-tail vlist
+Return the tail of @var{vlist}.
+@end deffn
+
+@defvr {Scheme Variable} block-growth-factor
+A fluid that defines the growth factor of VList blocks, 2 by default.
+@end defvr
+
+The functions below provide the usual set of higher-level list operations.
+
+@deffn {Scheme Procedure} vlist-fold proc init vlist
+@deffnx {Scheme Procedure} vlist-fold-right proc init vlist
+Fold over @var{vlist}, calling @var{proc} for each element, as for SRFI-1
+@code{fold} and @code{fold-right} (@pxref{SRFI-1, @code{fold}}).
+@end deffn
+
+@deffn {Scheme Procedure} vlist-ref vlist index
+Return the element at index @var{index} in @var{vlist}. This is typically a
+constant-time operation.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-length vlist
+Return the length of @var{vlist}. This is typically logarithmic in the number
+of elements in @var{vlist}.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-reverse vlist
+Return a new @var{vlist} whose content are those of @var{vlist} in reverse
+order.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-map proc vlist
+Map @var{proc} over the elements of @var{vlist} and return a new vlist.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-for-each proc vlist
+Call @var{proc} on each element of @var{vlist}. The result is unspecified.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-drop vlist count
+Return a new vlist that does not contain the @var{count} first elements of
+@var{vlist}. This is typically a constant-time operation.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-take vlist count
+Return a new vlist that contains only the @var{count} first elements of
+@var{vlist}.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-filter pred vlist
+Return a new vlist containing all the elements from @var{vlist} that satisfy
+@var{pred}.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-delete x vlist [equal?]
+Return a new vlist corresponding to @var{vlist} without the elements
+@var{equal?} to @var{x}.
+@end deffn
+
+@deffn {Scheme Procedure} vlist-unfold p f g seed [tail-gen]
+@deffnx {Scheme Procedure} vlist-unfold-right p f g seed [tail]
+Return a new vlist, as for SRFI-1 @code{unfold} and @code{unfold-right}
+(@pxref{SRFI-1, @code{unfold}}).
+@end deffn
+
+@deffn {Scheme Procedure} vlist-append vlist @dots{}
+Append the given vlists and return the resulting vlist.
+@end deffn
+
+@deffn {Scheme Procedure} list->vlist lst
+Return a new vlist whose contents correspond to @var{lst}.
+@end deffn
+
+@deffn {Scheme Procedure} vlist->list vlist
+Return a new list whose contents match those of @var{vlist}.
+@end deffn
+
+
+
@node Records
@subsection Records
A @dfn{record type} is a first class object representing a user-defined
data type. A @dfn{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.
+@xref{SRFI-9}.
+
@deffn {Scheme Procedure} record? obj
Return @code{#t} if @var{obj} is a record of any type and @code{#f}
otherwise.
@tpindex Structures
A @dfn{structure} is a first class data type which holds Scheme values
-or C words in fields numbered 0 upwards. A @dfn{vtable} represents a
-structure type, giving field types and permissions, and an optional
-print function for @code{write} etc.
+or C words in fields numbered 0 upwards. A @dfn{vtable} is a structure
+that represents a structure type, giving field types and permissions,
+and an optional print function for @code{write} etc.
-Structures are lower level than records (@pxref{Records}) but have
-some extra features. The vtable system allows sets of types be
-constructed, with class data. The uninterpreted words can
-inter-operate with C code, allowing arbitrary pointers or other values
-to be stored along side usual Scheme @code{SCM} values.
+Structures are lower level than records (@pxref{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.
@menu
-* Vtables::
-* Structure Basics::
-* Vtable Contents::
-* Vtable Vtables::
+* Vtables::
+* Structure Basics::
+* Vtable Contents::
+* Meta-Vtables::
+* Vtable Example::
+* Tail Arrays::
@end menu
-@node Vtables, Structure Basics, Structures, Structures
+@node Vtables
@subsubsection 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 worray about that initially (@pxref{Vtable Contents}.)
+need to worry about that initially (@pxref{Vtable Contents}.)
@deffn {Scheme Procedure} make-vtable fields [print]
Create a new vtable.
@code{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.
-@item
-@code{W},@code{R},@code{O} -- a tail array, with permissions for the
-array fields as per @code{w},@code{r},@code{o}.
@end itemize
-A tail array is further fields at the end of a structure. The last
-field in the layout string might be for instance @samp{pW} to have a
-tail of writable Scheme-valued fields. The @samp{pW} field itself
-holds the tail size, and the tail fields come after it.
-
-Here are some examples.
+Here are some examples. @xref{Tail Arrays}, for information on the
+legacy tail array facility.
@example
(make-vtable "pw") ;; one writable field
(make-vtable "prpw") ;; one read-only and one writable
(make-vtable "pwuwuw") ;; one scheme and two uninterpreted
-
-(make-vtable "prpW") ;; one fixed then a tail array
@end example
The optional @var{print} argument is a function called by
@example
(make-vtable "prpw"
(lambda (struct port)
- (display "#<" port)
- (display (struct-ref struct 0) port)
- (display " and " port)
- (display (struct-ref struct 1) port)
- (display ">" port)))
+ (format port "#<~a and ~a>"
+ (struct-ref struct 0)
+ (struct-ref struct 1))))
@end example
@end deffn
-@node Structure Basics, Vtable Contents, Vtables, Structures
+@node Structure Basics
@subsubsection Structure Basics
This section describes the basic procedures for working with
structures. @code{make-struct} creates a structure, and
-@code{struct-ref} and @code{struct-set!} access write fields.
+@code{struct-ref} and @code{struct-set!} access its fields.
-@deffn {Scheme Procedure} make-struct vtable tail-size [init...]
-@deffnx {C Function} scm_make_struct (vtable, tail_size, init_list)
+@deffn {Scheme Procedure} make-struct vtable tail-size init @dots{}
+@deffnx {Scheme Procedure} make-struct/no-tail vtable init @dots{}
Create a new structure, with layout per the given @var{vtable}
(@pxref{Vtables}).
-@var{tail-size} is the size of the tail array if @var{vtable}
-specifies a tail array. @var{tail-size} should be 0 when @var{vtable}
-doesn't specify a tail array.
-
The optional @var{init}@dots{} arguments are initial values for the
-fields of the structure (and the tail array). This is the only way to
+fields of the structure. This is the only way to
put values in read-only fields. If there are fewer @var{init}
arguments than fields then the defaults are @code{#f} for a Scheme
field (type @code{p}) or 0 for an uninterpreted field (type @code{u}).
+Structures also have the ability to allocate a variable number of
+additional cells at the end, at their tails. However, this legacy
+@dfn{tail array} facilty is confusing and inefficient, and so we do not
+recommend it. @xref{Tail Arrays}, for more on the legacy tail array
+interface.
+
Type @code{s} self-reference fields, permission @code{o} opaque
fields, and the count field of a tail array are all ignored for the
@var{init} arguments, ie.@: an argument is not consumed by such a
(struct-ref s 0) @result{} 123
(struct-ref s 1) @result{} "abc"
@end example
-
-@example
-(define v (make-vtable "prpW"))
-(define s (make-struct v 6 "fixed field" 'x 'y))
-(struct-ref s 0) @result{} "fixed field"
-(struct-ref s 1) @result{} 2 ;; tail size
-(struct-ref s 2) @result{} x ;; tail array ...
-(struct-ref s 3) @result{} y
-(struct-ref s 4) @result{} #f
-@end example
@end deffn
+@deftypefn {C Function} SCM scm_make_struct (SCM vtable, SCM tail_size, SCM init_list)
+@deftypefnx {C Function} SCM scm_c_make_struct (SCM vtable, SCM tail_size, SCM init, ...)
+@deftypefnx {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. @code{scm_make_struct}
+takes a list, @code{scm_c_make_struct} takes variable arguments
+terminated with SCM_UNDEFINED, and @code{scm_c_make_structv} takes a
+packed array.
+@end deftypefn
+
@deffn {Scheme Procedure} struct? obj
@deffnx {C Function} scm_struct_p (obj)
Return @code{#t} if @var{obj} is a structure, or @code{#f} if not.
@deffn {Scheme Procedure} struct-vtable struct
@deffnx {C Function} scm_struct_vtable (struct)
-Return the vtable used by @var{struct}.
+Return the vtable that describes @var{struct}.
-This can be used to examine the layout of an unknown structure, see
-@ref{Vtable Contents}.
+The vtable is effectively the type of the structure. See @ref{Vtable
+Contents}, for more on vtables.
@end deffn
-@node Vtable Contents, Vtable Vtables, Structure Basics, Structures
+@node Vtable Contents
@subsubsection Vtable Contents
-A vtable is itself a structure, with particular fields that hold
-information about the structures to be created. These include the
-fields of those structures, and the print function for them. The
-variables below allow access to those fields.
-
-@deffn {Scheme Procedure} struct-vtable? obj
-@deffnx {C Function} scm_struct_vtable_p (obj)
-Return @code{#t} if @var{obj} is a vtable structure.
+A vtable is itself a structure. It has a specific set of fields
+describing various aspects of its @dfn{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.
-Note that because vtables are simply structures with a particular
-layout, @code{struct-vtable?} can potentially return true on an
-application structure which merely happens to look like a vtable.
-@end deffn
+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.
@defvr {Scheme Variable} vtable-index-layout
@defvrx {C Macro} scm_vtable_index_layout
The field number of the layout specification in a vtable. The layout
specification is a symbol like @code{pwpw} formed from the fields
string passed to @code{make-vtable}, or created by
-@code{make-struct-layout} (@pxref{Vtable Vtables}).
+@code{make-struct-layout} (@pxref{Meta-Vtables}).
@example
(define v (make-vtable "pwpw" 0))
cannot be changed.
@end defvr
-@defvr {Scheme Variable} vtable-index-vtable
-@defvrx {C Macro} scm_vtable_index_vtable
-A self-reference to the vtable, ie.@: a type @code{s} field. This is
-used by C code within Guile and has no use at the Scheme level.
-@end defvr
-
@defvr {Scheme Variable} vtable-index-printer
@defvrx {C Macro} scm_vtable_index_printer
The field number of the printer function. This field contains @code{#f}
@end example
@end deffn
-@deffn {Scheme Procedure} struct-vtable-tag vtable
-@deffnx {C Function} scm_struct_vtable_tag (vtable)
-Return the tag of the given @var{vtable}.
-@c
-@c FIXME: what can be said about what this means?
-@c
-@end deffn
+@node Meta-Vtables
+@subsubsection Meta-Vtables
-@node Vtable Vtables, , Vtable Contents, Structures
-@subsubsection Vtable 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.
-As noted above, a vtable is a structure and that structure is itself
-described by a vtable. Such a ``vtable of a vtable'' can be created
-with @code{make-vtable-vtable} below. This can be used to build sets
-of related vtables, possibly with extra application fields.
+If you traverse up the tree of vtables, via calling
+@code{struct-vtable}, eventually you reach a root which is the vtable of
+itself:
-This second level of vtable can be a little confusing. The ball
-example below is a typical use, adding a ``class data'' field to the
-vtables, from which instance structures are created. The current
-implementation of Guile's own records (@pxref{Records}) does something
-similar, a record type descriptor is a vtable with room to hold the
-field names of the records to be created from it.
+@example
+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>
+@end example
-@deffn {Scheme Procedure} make-vtable-vtable user-fields tail-size [print]
-@deffnx {C Function} scm_make_vtable_vtable (user_fields, tail_size, print_and_init_list)
-Create a ``vtable-vtable'' which can be used to create vtables. This
-vtable-vtable is also a vtable, and is self-describing, meaning its
-vtable is itself. The following is a simple usage.
+In this example, we can say that @code{$1} is an instance of @code{$2},
+@code{$2} is an instance of @code{$3}, @code{$3} is an instance of
+@code{$4}, and @code{$4}, strangely enough, is an instance of itself.
+The value bound to @code{$4} in this console session also bound to
+@code{<standard-vtable>} in the default environment.
-@example
-(define vt-vt (make-vtable-vtable "" 0))
-(define vt (make-struct vt-vt 0
- (make-struct-layout "pwpw"))
-(define s (make-struct vt 0 123 456))
+@defvr {Scheme Variable} <standard-vtable>
+A meta-vtable, useful for making new vtables.
+@end defvr
-(struct-ref s 0) @result{} 123
-@end example
+All of these values are structures. All but @code{$1} are vtables. As
+@code{$2} is an instance of @code{$3}, and @code{$3} is a vtable, we can
+say that @code{$3} is a @dfn{meta-vtable}: a vtable that can create
+vtables.
-@code{make-struct} is used to create a vtable from the vtable-vtable.
-The first initializer is a layout object (field
-@code{vtable-index-layout}), usually obtained from
-@code{make-struct-layout} (below). An optional second initializer is
-a printer function (field @code{vtable-index-printer}), used as
-described under @code{make-vtable} (@pxref{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.
-@sp 1
-@var{user-fields} is a layout string giving extra fields to have in
-the vtables. A vtable starts with some base fields as per @ref{Vtable
-Contents}, and @var{user-fields} is appended. The @var{user-fields}
-start at field number @code{vtable-offset-user} (below), and exist in
-both the vtable-vtable and in the vtables created from it. Such
-fields provide space for ``class data''. For example,
+@deffn {Scheme Procedure} struct-vtable? obj
+@deffnx {C Function} scm_struct_vtable_p (obj)
+Return @code{#t} if @var{obj} is a vtable structure: an instance of a
+meta-vtable.
+@end deffn
-@example
-(define vt-of-vt (make-vtable-vtable "pw" 0))
-(define vt (make-struct vt-of-vt 0))
-(struct-set! vt vtable-offset-user "my class data")
-@end example
+@code{<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.)
-@var{tail-size} is the size of the tail array in the vtable-vtable
-itself, if @var{user-fields} specifies a tail array. This should be 0
-if nothing extra is required or the format has no tail array. The
-tail array field such as @samp{pW} holds the tail array size, as
-usual, and is followed by the extra space.
+The set of required fields of a vtable is the set of fields in the
+@code{<standard-vtable>}, and is bound to @code{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:
@example
-(define vt-vt (make-vtable-vtable "pW" 20))
-(define my-vt-tail-start (1+ vtable-offset-user))
-(struct-set! vt-vt (+ 3 my-vt-tail-start) "data in tail")
+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
@end example
-The optional @var{print} argument is used by @code{display} and
-@code{write} (etc) to print the vtable-vtable and any vtables created
-from it. It's called as @code{(@var{print} vtable port)} and should
-look at @var{vtable} and write to @var{port}. The default is the
-usual structure print function, which just gives machine addresses.
-@end deffn
+In this continuation of our earlier example, @code{$2} is a vtable that
+has extra fields, because its vtable, @code{$3}, was made from a
+meta-vtable with an extended layout. @code{vtable-offset-user} is a
+convenient definition that indicates the number of fields in
+@code{standard-vtable-fields}.
+
+@defvr {Scheme Variable} standard-vtable-fields
+A string containing the orderedq set of fields that a vtable must have.
+@end defvr
+
+@defvr {Scheme Variable} vtable-offset-user
+The first index in a vtable that is available for a user.
+@end defvr
@deffn {Scheme Procedure} make-struct-layout fields
@deffnx {C Function} scm_make_struct_layout (fields)
Return a structure layout symbol, from a @var{fields} string.
@var{fields} is as described under @code{make-vtable}
(@pxref{Vtables}). An invalid @var{fields} string is an error.
+@end deffn
+
+With these definitions, one can define @code{make-vtable} in this way:
@example
-(make-struct-layout "prpW") @result{} prpW
-(make-struct-layout "blah") @result{} ERROR
+(define* (make-vtable fields #:optional printer)
+ (make-struct/no-tail <standard-vtable>
+ (make-struct-layout fields)
+ printer))
@end example
-@end deffn
-@defvr {Scheme Variable} vtable-offset-user
-@defvrx {C Macro} scm_vtable_offset_user
-The first field in a vtable which is available for application use.
-Such fields only exist when specified by @var{user-fields} in
-@code{make-vtable-vtable} above.
-@end defvr
-@sp 1
-Here's an extended vtable-vtable example, creating classes of
-``balls''. Each class has a ``colour'', which is fixed. Instances of
-those classes are created, and such each such ball has an ``owner'',
-which can be changed.
+@node Vtable Example
+@subsubsection Vtable Example
-@lisp
-(define ball-root (make-vtable-vtable "pr" 0))
-
-(define (make-ball-type ball-color)
- (make-struct ball-root 0
- (make-struct-layout "pw")
- (lambda (ball port)
- (format port "#<a ~A ball owned by ~A>"
- (color ball)
- (owner ball)))
- ball-color))
-(define (color ball)
- (struct-ref (struct-vtable ball) vtable-offset-user))
-(define (owner ball)
- (struct-ref ball 0))
-
-(define red (make-ball-type 'red))
-(define green (make-ball-type 'green))
-
-(define (make-ball type owner) (make-struct type 0 owner))
-
-(define ball (make-ball green 'Nisse))
-ball @result{} #<a green ball owned by Nisse>
-@end lisp
+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.
+
+@example
+(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>)))
+@end example
+
+To make a structure with a specific meta-vtable, we will use
+@code{make-struct/no-tail}, passing it the computed instance layout and
+printer, as with @code{make-vtable}, and additionally the extra three
+class fields.
+
+@example
+(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)))
+@end example
+
+Instances will store their associated data in slots in the structure: as
+many slots as there are fields. The @code{compute-layout} procedure
+below can compute a layout, and @code{field-index} returns the slot
+corresponding to a field.
+
+@example
+(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 ">"))
+@end example
+
+So, at this point we can actually make a few classes:
+
+@example
+(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)
+@end example
+
+And finally, make an instance:
+
+@example
+(make-struct/no-tail <window> 400 300 10 20)
+@result{} <<window> width: 400 height: 300 x: 10 y: 20>
+@end example
+
+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.
+
+@node Tail Arrays
+@subsubsection 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 @code{make-struct}. For this reason the clumsily-named
+@code{make-struct/no-tail} procedure can actually be more elegant in
+actual use, because it doesn't have a random @code{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: @code{W},
+@code{R} or @code{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, @samp{pW} indicates a tail of writable Scheme-valued
+fields. The @samp{pW} field itself holds the tail size, and the tail
+fields come after it.
+
+@example
+(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) @result{} "fixed field"
+(struct-ref s 1) @result{} 2 ;; tail size
+(struct-ref s 2) @result{} x ;; tail array ...
+(struct-ref s 3) @result{} y
+(struct-ref s 4) @result{} #f
+@end example
@node Dictionary Types
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. @code{(vector-ref foo 5)}). Often you will find it useful
+(e.g.@: @code{(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
@tpindex Alist
@cindex association List
@cindex alist
-@cindex aatabase
+@cindex database
An association list is a conventional data structure that is often used
to implement simple key-value databases. It consists of a list of
@code{eqv?} and @code{assoc-ref} uses @code{equal?}.
Notice these functions have the @var{key} argument last, like other
-@code{-ref} functions, but this is opposite to what what @code{assq}
+@code{-ref} functions, but this is opposite to what @code{assq}
etc above use.
When the return is @code{#f} it can be either @var{key} not found, or
("Florida" . "Tallahassee"))
@end lisp
+@node VHashes
+@subsection VList-Based Hash Lists or ``VHashes''
+
+@cindex VList-based hash lists
+@cindex VHash
+
+The @code{(ice-9 vlist)} module provides an implementation of @dfn{VList-based
+hash lists} (@pxref{VLists}). VList-based hash lists, or @dfn{vhashes}, are an
+immutable dictionary type similar to association lists that maps @dfn{keys} to
+@dfn{values}. However, unlike association lists, accessing a value given its
+key is typically a constant-time operation.
+
+The VHash programming interface of @code{(ice-9 vlist)} is mostly the same as
+that of association lists found in SRFI-1, with procedure names prefixed by
+@code{vhash-} instead of @code{alist-} (@pxref{SRFI-1 Association Lists}).
+
+In addition, vhashes can be manipulated using VList operations:
+
+@example
+(vlist-head (vhash-consq 'a 1 vlist-null))
+@result{} (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)
+@result{} (a . 1)
+(vhash-assq 'b vh2)
+@result{} #f
+(vhash-assq 'c vh2)
+@result{} (c . 3)
+(vlist->list vh2)
+@result{} ((c . 3) (a . 1))
+@end example
+
+However, keep in mind that procedures that construct new VLists
+(@code{vlist-map}, @code{vlist-filter}, etc.) return raw VLists, not vhashes:
+
+@example
+(define vh (alist->vhash '((a . 1) (b . 2) (c . 3)) hashq))
+(vhash-assq 'a vh)
+@result{} (a . 1)
+
+(define vl
+ ;; This will create a raw vlist.
+ (vlist-filter (lambda (key+value) (odd? (cdr key+value))) vh))
+(vhash-assq 'a vl)
+@result{} ERROR: Wrong type argument in position 2
+
+(vlist->list vl)
+@result{} ((a . 1) (c . 3))
+@end example
+
+@deffn {Scheme Procedure} vhash? obj
+Return true if @var{obj} is a vhash.
+@end deffn
+
+@deffn {Scheme Procedure} vhash-cons key value vhash [hash-proc]
+@deffnx {Scheme Procedure} vhash-consq key value vhash
+@deffnx {Scheme Procedure} vhash-consv key value vhash
+Return a new hash list based on @var{vhash} where @var{key} is associated with
+@var{value}, using @var{hash-proc} to compute the hash of @var{key}.
+@var{vhash} must be either @code{vlist-null} or a vhash returned by a previous
+call to @code{vhash-cons}. @var{hash-proc} defaults to @code{hash} (@pxref{Hash
+Table Reference, @code{hash} procedure}). With @code{vhash-consq}, the
+@code{hashq} hash function is used; with @code{vhash-consv} the @code{hashv}
+hash function is used.
+
+All @code{vhash-cons} calls made to construct a vhash should use the same
+@var{hash-proc}. Failing to do that, the result is undefined.
+@end deffn
+
+@deffn {Scheme Procedure} vhash-assoc key vhash [equal? [hash-proc]]
+@deffnx {Scheme Procedure} vhash-assq key vhash
+@deffnx {Scheme Procedure} vhash-assv key vhash
+Return the first key/value pair from @var{vhash} whose key is equal to @var{key}
+according to the @var{equal?} equality predicate (which defaults to
+@code{equal?}), and using @var{hash-proc} (which defaults to @code{hash}) to
+compute the hash of @var{key}. The second form uses @code{eq?} as the equality
+predicate and @code{hashq} as the hash function; the last form uses @code{eqv?}
+and @code{hashv}.
+
+Note that it is important to consistently use the same hash function for
+@var{hash-proc} as was passed to @code{vhash-cons}. Failing to do that, the
+result is unpredictable.
+@end deffn
+
+@deffn {Scheme Procedure} vhash-delete key vhash [equal? [hash-proc]]
+@deffnx {Scheme Procedure} vhash-delq key vhash
+@deffnx {Scheme Procedure} vhash-delv key vhash
+Remove all associations from @var{vhash} with @var{key}, comparing keys with
+@var{equal?} (which defaults to @code{equal?}), and computing the hash of
+@var{key} using @var{hash-proc} (which defaults to @code{hash}). The second
+form uses @code{eq?} as the equality predicate and @code{hashq} as the hash
+function; the last one uses @code{eqv?} and @code{hashv}.
+
+Again the choice of @var{hash-proc} must be consistent with previous calls to
+@code{vhash-cons}.
+@end deffn
+
+@deffn {Scheme Procedure} vhash-fold proc init vhash
+@deffnx {Scheme Procedure} vhash-fold-right proc init vhash
+Fold over the key/value elements of @var{vhash} in the given direction,
+with each call to @var{proc} having the form @code{(@var{proc} key value
+result)}, where @var{result} is the result of the previous call to
+@var{proc} and @var{init} the value of @var{result} for the first call
+to @var{proc}.
+@end deffn
+
+@deffn {Scheme Procedure} vhash-fold* proc init key vhash [equal? [hash]]
+@deffnx {Scheme Procedure} vhash-foldq* proc init key vhash
+@deffnx {Scheme Procedure} vhash-foldv* proc init key vhash
+Fold over all the values associated with @var{key} in @var{vhash}, with each
+call to @var{proc} having the form @code{(proc value result)}, where
+@var{result} is the result of the previous call to @var{proc} and @var{init} the
+value of @var{result} for the first call to @var{proc}.
+
+Keys in @var{vhash} are hashed using @var{hash} are compared using @var{equal?}.
+The second form uses @code{eq?} as the equality predicate and @code{hashq} as
+the hash function; the third one uses @code{eqv?} and @code{hashv}.
+
+Example:
+
+@example
+(define vh
+ (alist->vhash '((a . 1) (a . 2) (z . 0) (a . 3))))
+
+(vhash-fold* cons '() 'a vh)
+@result{} (3 2 1)
+
+(vhash-fold* cons '() 'z vh)
+@result{} (0)
+@end example
+@end deffn
+
+@deffn {Scheme Procedure} alist->vhash alist [hash-proc]
+Return the vhash corresponding to @var{alist}, an association list, using
+@var{hash-proc} to compute key hashes. When omitted, @var{hash-proc} defaults
+to @code{hash}.
+@end deffn
+
+
@node Hash Tables
@subsection Hash Tables
@tpindex Hash Tables
;; entry is at index (hashq 'frob).
h
@result{}
-#(() () () () ((frob . #f) (braz . "zonk")) () ((foo . "bar")))
+#(((braz . "zonk")) ((foo . "bar")) () () () () ((frob . #f)))
-(hashq 'frob)
+(hashq 'frob 7)
@result{}
-4
+6
@end lisp
HCoop / bpt / guile.git / blobdiff