This is guile-ref.info, produced by Makeinfo version 3.12a from guile-ref.texi. INFO-DIR-SECTION Scheme Programming START-INFO-DIR-ENTRY * guile-ref: (guile-ref). The Guile Reference Manual. END-INFO-DIR-ENTRY Guile Reference Manual Copyright (C) 1996 Free Software Foundation Copyright (C) 1997 Free Software Foundation Permission is granted to make and distribute verbatim copies of this manual provided the copyright notice and this permission notice are preserved on all copies. Permission is granted to copy and distribute modified versions of this manual under the conditions for verbatim copying, provided that the entire resulting derived work is distributed under the terms of a permission notice identical to this one. Permission is granted to copy and distribute translations of this manual into another language, under the above conditions for modified versions, except that this permission notice may be stated in a translation approved by the Free Software Foundation.  File: guile-ref.info, Node: Lists, Next: Data Structures, Prev: Evaluation, Up: Top Lists ***** This chapter describes Guile list functions not found in standard Scheme. -- primitive: append! [lst...] A destructive version of `append' (*note Pairs and Lists: (r4rs)Pairs and Lists.). The cdr field of each list's final pair is changed to point to the head of the next list, so no consing is performed. Return a pointer to the mutated list. -- primitive: last-pair lst Return a pointer to the last pair in LST, signalling an error if LST is circular. -- primitive: reverse! lst [newtail] A destructive version of `reverse' (*note Pairs and Lists: (r4rs)Pairs and Lists.). The cdr of each cell in LST is modified to point to the previous list element. Return a pointer to the head of the reversed list. Caveat: because the list is modified in place, the tail of the original list now becomes its head, and the head of the original list now becomes the tail. Therefore, the LST symbol to which the head of the original list was bound now points to the tail. To ensure that the head of the modified list is not lost, it is wise to save the return value of `reverse!' -- primitive: list-set! lst k val Set the Kth element of LST to VAL. -- primitive: list-cdr-ref lst k -- primitive: 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-cdr-ref' and `list-tail' 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. -- primitive: list-cdr-set! lst k val Set the Kth cdr of LST to VAL. -- primitive: list-head lst k Copy the first K elements from LST into a new list, and return it. -- primitive: list-copy lst Return a (newly-created) copy of LST. -- primitive: delq item lst -- primitive: delv item lst -- primitive: delete item lst Return a newly-created copy of LST with ITEM removed. These procedures mirror `memq', `memv' and `member': `delq' compares elements of LST against ITEM with `eq?', `delv' uses `eqv?' and `delete' uses `equal?' -- primitive: delq! item lst -- primitive: delv! item lst -- primitive: delete! 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. [FIXME: is there any reason to have the `sloppy' functions available at high level at all? Maybe these docs should be relegated to a "Guile Internals" node or something. -twp] -- primitive: sloppy-memq -- primitive: sloppy-memv -- primitive: sloppy-member These procedures behave like `memq', `memv' and `member' (*note Pairs and Lists: (r4rs)Pairs and Lists.), but do not perform any type or error checking. Their use is recommended only in writing Guile internals, not for high-level Scheme programs.  File: guile-ref.info, Node: Data Structures, Next: Strings, Prev: Lists, Up: Top Data Structures *************** To make it easier to write powerful applications, Guile provides many data structures not found in standard Scheme. * Menu: * Records:: * Structures:: * Arrays:: * Association Lists and Hash Tables::  File: guile-ref.info, Node: Records, Next: Structures, Up: Data Structures Records ======= [FIXME: this is pasted in from Tom Lord's original guile.texi and should be reviewed] A "record type" is a first class object representing a user-defined data type. A "record" is an instance of a record type. -- procedure: record? obj Returns `#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. -- procedure: make-record-type type-name field-names Returns a "record-type descriptor", a value representing a new data type disjoint from all others. The TYPE-NAME argument must be a string, but is only used for debugging purposes (such as the printed representation of a record of the new type). The FIELD-NAMES argument is a list of symbols naming the "fields" of a record of the new type. It is an error if the list contains any duplicates. It is unspecified how record-type descriptors are represented. -- procedure: record-constructor rtd [field-names] Returns 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. -- procedure: record-predicate rtd Returns 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. -- procedure: record-accessor rtd field-name Returns 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. -- procedure: record-modifier rtd field-name Returns 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. -- procedure: record-type-descriptor record Returns 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. -- procedure: record-type-name rtd Returns 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. -- procedure: record-type-fields rtd Returns 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.  File: guile-ref.info, Node: Structures, Next: Arrays, Prev: Records, Up: Data Structures Structures ========== [FIXME: this is pasted in from Tom Lord's original guile.texi and should be reviewed] A "structure type" is a first class user-defined data type. A "structure" is an instance of a structure type. A structure type is itself a structure. Structures are less abstract and more general than traditional records. In fact, in Guile Scheme, records are implemented using structures. * Menu: * Structure Concepts:: The structure of Structures * Structure Layout:: Defining the layout of structure types * Structure Basics:: make-, -ref and -set! procedures for structs * Vtables:: Accessing type-specific data  File: guile-ref.info, Node: Structure Concepts, Next: Structure Layout, Up: Structures Structure Concepts ------------------ A structure object consists of a handle, structure data, and a vtable. The handle is a Scheme value which points to both the vtable and the structure's data. Structure data is a dynamically allocated region of memory, private to the structure, divided up into typed fields. A vtable is another structure used to hold type-specific data. Multiple structures can share a common vtable. Three concepts are key to understanding structures. * "layout specifications" Layout specifications determine how memory allocated to structures is divided up into fields. Programmers must write a layout specification whenever a new type of structure is defined. * "structural accessors" Structure access is by field number. There is only one set of accessors common to all structure objects. * "vtables" Vtables, themselves structures, are first class representations of disjoint sub-types of structures in general. In most cases, when a new structure is created, programmers must specifiy a vtable for the new structure. Each vtable has a field describing the layout of its instances. Vtables can have additional, user-defined fields as well.  File: guile-ref.info, Node: Structure Layout, Next: Structure Basics, Prev: Structure Concepts, Up: Structures Structure Layout ---------------- When a structure is created, a region of memory is allocated to hold its state. The "layout" of the structure's type determines how that memory is divided into fields. Each field has a specified type. There are only three types allowed, each corresponding to a one letter code. The allowed types are: * 'u' -- unprotected The field holds binary data that is not GC protected. * 'p' -- protected The field holds a Scheme value and is GC protected. * 's' -- self The field holds a Scheme value and is GC protected. When a structure is created with this type of field, the field is initialized to refer to the structure's own handle. This kind of field is mainly useful when mixing Scheme and C code in which the C code may need to compute a structure's handle given only the address of its malloced data. Each field also has an associated access protection. There are only three kinds of protection, each corresponding to a one letter code. The allowed protections are: * 'w' -- writable The field can be read and written. * 'r' -- readable The field can be read, but not written. * 'o' -- opaque The field can be neither read nor written. This kind of protection is for fields useful only to built-in routines. A layout specification is described by stringing together pairs of letters: one to specify a field type and one to specify a field protection. For example, a traditional cons pair type object could be described as: ; cons pairs have two writable fields of Scheme data "pwpw" A pair object in which the first field is held constant could be: "prpw" Binary fields, (fields of type "u"), hold one _word_ each. The size of a word is a machine dependent value defined to be equal to the value of the C expression: `sizeof (long)'. The last field of a structure layout may specify a tail array. A tail array is indicated by capitalizing the field's protection code ('W', 'R' or 'O'). A tail-array field is replaced by a read-only binary data field containing an array size. The array size is determined at the time the structure is created. It is followed by a corresponding number of fields of the type specified for the tail array. For example, a conventional Scheme vector can be described as: ; A vector is an arbitrary number of writable fields holding Scheme ; values: "pW" In the above example, field 0 contains the size of the vector and fields beginning at 1 contain the vector elements. A kind of tagged vector (a constant tag followed by conventioal vector elements) might be: "prpW" Structure layouts are represented by specially interned symbols whose name is a string of type and protection codes. To create a new structure layout, use this procedure: -- primitive: make-struct-layout fields Return a new structure layout object. FIELDS must be a read-only string made up of pairs of characters strung together. The first character of each pair describes a field type, the second a field protection. Allowed types are 'p' for GC-protected Scheme data, 'u' for unprotected binary data, and 's' for fields that should point to the structure itself. Allowed protections are 'w' for mutable fields, 'r' for read-only fields, and 'o' for opaque fields. The last field protection specification may be capitalized to indicate that the field is a tail-array.  File: guile-ref.info, Node: Structure Basics, Next: Vtables, Prev: Structure Layout, Up: Structures Structure Basics ---------------- This section describes the basic procedures for creating and accessing structures. -- primitive: make-struct type tail-elts . inits Create a new structure. TYPE must be a vtable structure (*Note Vtables::). TAIL-ELTS must be a non-negative integer. If the layout specification indicated by TYPE includes a tail-array, this is the number of elements allocated to that array. The INITS are optional arguments describing how successive fields of the structure should be initialized. Only fields with protection 'r' or 'w' can be initialized -- fields of protection 's' are automatically initialized to point to the new structure itself; fields of protection 'o' can not be initialized by Scheme programs. -- primitive: struct? obj Return #t iff OBJ is a structure object. -- primitive: struct-ref struct n -- primitive: struct-set! struct n value Access (or modify) the Nth field of STRUCT. If the field is of type 'p', then it can be set to an arbitrary value. If the field is of type 'u', then it can only be set to a non-negative integer value small enough to fit in one machine word.  File: guile-ref.info, Node: Vtables, Prev: Structure Basics, Up: Structures Vtables ------- Vtables are structures that are used to represent structure types. Each vtable contains a layout specification in field `vtable-index-layout' -- instances of the type are laid out according to that specification. Vtables contain additional fields which are used only internally to libguile. The variable `vtable-offset-user' is bound to a field number. Vtable fields at that position or greater are user definable. -- primitive: struct-vtable struct Return the vtable structure that describes the type of STRUCT. -- primitive: struct-vtable? obj Return #t iff obj is a vtable structure. If you have a vtable structure, `V', you can create an instance of the type it describes by using `(make-struct V ...)'. But where does `V' itself come from? One possibility is that `V' is an instance of a user-defined vtable type, `V'', so that `V' is created by using `(make-struct V' ...)'. Another possibility is that `V' is an instance of the type it itself describes. Vtable structures of the second sort are created by this procedure: -- primitive: make-vtable-vtable new-fields tail-size . inits Return a new, self-describing vtable structure. NEW-FIELDS is a layout specification describing fields of the resulting structure beginning at the position bound to `vtable-offset-user'. TAIL-SIZE specifies the size of the tail-array (if any) of this vtable. INITS initializes the fields of the vtable. Minimally, one initializer must be provided: the layout specification for instances of the type this vtable will describe. If a second initializer is provided, it will be interpreted as a print call-back function. ;;; loading ,a... (define x (make-vtable-vtable (make-struct-layout (quote pw)) 0 'foo)) (struct? x) => #t (struct-vtable? x) => #t (eq? x (struct-vtable x)) => #t (struct-ref x vtable-offset-user) => foo (struct-ref x 0) => pruosrpwpw (define y (make-struct x 0 (make-struct-layout (quote pwpwpw)) 'bar)) (struct? y) => #t (struct-vtable? y) => #t (eq? x y) => () (eq? x (struct-vtable y)) => #t (struct-ref y 0) => pwpwpw (struct-ref y vtable-offset-user) => bar (define z (make-struct y 0 'a 'b 'c)) (struct? z) => #t (struct-vtable? z) => () (eq? y (struct-vtable z)) => #t (map (lambda (n) (struct-ref z n)) '(0 1 2)) => (a b c)  File: guile-ref.info, Node: Arrays, Next: Association Lists and Hash Tables, Prev: Structures, Up: Data Structures Arrays ====== [FIXME: this is pasted in from Tom Lord's original guile.texi and should be reviewed] * Menu: * Conventional Arrays:: * Array Mapping:: * Uniform Array:: * Bit Vectors::  File: guile-ref.info, Node: Conventional Arrays, Next: Array Mapping, Up: Arrays Conventional Arrays ------------------- "Arrays" read and write as a `#' followed by the "rank" (number of dimensions) followed by what appear as lists (of lists) of elements. The lists must be nested to the depth of the rank. For each depth, all lists must be the same length. (make-array 'ho 3 3) => #2((ho ho ho) (ho ho ho) (ho ho ho)) Unshared conventional (not uniform) 0-based arrays of rank 1 (dimension) are equivalent to (and can't be distinguished from) vectors. (make-array 'ho 3) => (ho ho ho) When constructing an array, BOUND is either an inclusive range of indices expressed as a two element list, or an upper bound expressed as a single integer. So (make-array 'foo 3 3) == (make-array 'foo '(0 2) '(0 2)) -- primitive: array? obj Returns `#t' if the OBJ is an array, and `#f' if not. -- procedure: make-array initial-value bound1 bound2 ... Creates and returns an array that has as many dimensions as there are BOUNDs and fills it with INITIAL-VALUE. -- primitive: array-ref array index1 index2 ... Returns the element at the `(index1, index2)' element in ARRAY. -- primitive: array-in-bounds? array index1 index2 ... Returns `#t' if its arguments would be acceptable to array-ref. -- primitive: array-set! array new-value index1 index2 ... Sets the element at the `(index1, index2)' element in ARRAY to NEW-VALUE. The value returned by array-set! is unspecified. -- primitive: make-shared-array array mapper bound1 bound2 ... `make-shared-array' can be used to create shared subarrays of other arrays. The MAPPER is a function that translates coordinates in the new array into coordinates in the old array. A MAPPER must be linear, and its range must stay within the bounds of the old array, but it can be otherwise arbitrary. A simple example: (define fred (make-array #f 8 8)) (define freds-diagonal (make-shared-array fred (lambda (i) (list i i)) 8)) (array-set! freds-diagonal 'foo 3) (array-ref fred 3 3) => foo (define freds-center (make-shared-array fred (lambda (i j) (list (+ 3 i) (+ 3 j))) 2 2)) (array-ref freds-center 0 0) => foo -- primitive: transpose-array array dim0 dim1 ... Returns 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. DIM0, DIM1, ... 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 DIM0, DIM1, ... correspond to dimensions in the array to be returned, 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. examples: (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)) -- primitive: enclose-array array dim0 dim1 ... DIM0, DIM1 ... should be nonnegative integers less than the rank of ARRAY. ENCLOSE-ARRAY returns an array resembling an array of shared arrays. The dimensions of each shared array are the same as the DIMth 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 DIM. An enclosed array is not a general Scheme array. Its elements may not be set using `array-set!'. Two references to the same element of an enclosed array will be `equal?' but will not in general be `eq?'. The value returned by ARRAY-PROTOTYPE when given an enclosed array is unspecified. examples: (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1) => # (enclose-array '#3(((a b c) (d e f)) ((1 2 3) (4 5 6))) 1 0) => # -- procedure: array-shape array Returns a list of inclusive bounds of integers. (array-shape (make-array 'foo '(-1 3) 5)) => ((-1 3) (0 4)) -- primitive: array-dimensions array `Array-dimensions' is similar to `array-shape' but replaces elements with a `0' minimum with one greater than the maximum. So: (array-dimensions (make-array 'foo '(-1 3) 5)) => ((-1 3) 5) -- primitive: array-rank obj Returns the number of dimensions of OBJ. If OBJ is not an array, `0' is returned. -- primitive: array->list array Returns a list consisting of all the elements, in order, of ARRAY. -- primitive: array-copy! source destination Copies every element from vector or array SOURCE to the corresponding element of DESTINATION. DESTINATION must have the same rank as SOURCE, and be at least as large in each dimension. The order is unspecified. -- primitive: serial-array-copy! source destination Same as `array-copy!' but guaranteed to copy in row-major order. -- primitive: array-fill! array fill Stores FILL in every element of ARRAY. The value returned is unspecified. -- primitive: array-equal? array0 array1 ... Returns `#t' iff 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?' in that a one dimensional shared array may be ARRAY-EQUAL? but not EQUAL? to a vector or uniform vector. -- primitive: array-contents array -- primitive: 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-UNIFORM-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.  File: guile-ref.info, Node: Array Mapping, Next: Uniform Array, Prev: Conventional Arrays, Up: Arrays Array Mapping ------------- -- primitive: array-map! array0 proc array1 ... ARRAY1, ... must have the same number of dimensions as ARRAY0 and have a range for each index which includes the range for the corresponding index in ARRAY0. PROC is applied to each tuple of elements of ARRAY1 ... and the result is stored as the corresponding element in ARRAY0. The value returned is unspecified. The order of application is unspecified. -- primitive: serial-array-map! array0 proc array1 ... Same as ARRAY-MAP!, but guaranteed to apply PROC in row-major order. -- primitive: array-for-each proc array0 ... PROC is applied to each tuple of elements of ARRAY0 ... in row-major order. The value returned is unspecified. -- primitive: array-index-map! array proc applies PROC to the indices of each element of ARRAY in turn, storing the result in the corresponding element. The value returned and the order of application are unspecified. One can implement ARRAY-INDEXES as (define (array-indexes array) (let ((ra (apply make-array #f (array-shape array)))) (array-index-map! ra (lambda x x)) ra)) Another example: (define (apl:index-generator n) (let ((v (make-uniform-vector n 1))) (array-index-map! v (lambda (i) i)) v))  File: guile-ref.info, Node: Uniform Array, Next: Bit Vectors, Prev: Array Mapping, Up: Arrays Uniform Array ------------- "Uniform Array" and vectors are arrays whose elements are all of the same type. Uniform vectors occupy less storage than conventional vectors. Uniform Array procedures also work on vectors, uniform-vectors, bit-vectors, and strings. PROTOTYPE arguments in the following procedures are interpreted according to the table: prototype type printing character #t boolean (bit-vector) b #\a char (string) a integer >0 unsigned integer u integer <0 signed integer e 1.0 float (single precision) s 1/3 double (double precision float) i +i complex (double precision) c () conventional vector Unshared uniform character 0-based arrays of rank 1 (dimension) are equivalent to (and can't be distinguished from) strings. (make-uniform-array #\a 3) => "$q2" Unshared uniform boolean 0-based arrays of rank 1 (dimension) are equivalent to (and can't be distinguished from) *Note bit-vectors: Bit Vectors. (make-uniform-array #t 3) => #*000 == #b(#f #f #f) => #*000 == #1b(#f #f #f) => #*000 Other uniform vectors are written in a form similar to that of vectors, except that a single character from the above table is put between `#' and `('. For example, `'#e(3 5 9)' returns a uniform vector of signed integers. -- primitive: array? obj prototype Returns `#t' if the OBJ is an array of type corresponding to PROTOTYPE, and `#f' if not. -- procedure: make-uniform-array prototype bound1 bound2 ... Creates and returns a uniform array of type corresponding to PROTOTYPE that has as many dimensions as there are BOUNDs and fills it with PROTOTYPE. -- primitive: array-prototype array Returns an object that would produce an array of the same type as ARRAY, if used as the PROTOTYPE for `make-uniform-array'. -- primitive: list->uniform-array rank prot lst -- procedure: list->uniform-vector prot lst Returns a uniform array of the type indicated by prototype PROT with elements the same as those of LST. Elements must be of the appropriate type, no coercions are done. -- primitive: uniform-vector-fill! uve fill Stores FILL in every element of UVE. The value returned is unspecified. -- primitive: uniform-vector-length uve Returns the number of elements in UVE. -- primitive: dimensions->uniform-array dims prototype [fill] -- primitive: make-uniform-vector length prototype [fill] Creates and returns a uniform array or vector of type corresponding to PROTOTYPE with dimensions DIMS or length LENGTH. If the FILL argument is supplied, the returned array is filled with this value. -- primitive: uniform-array-read! ura [port-or-fdes] [start] [end] -- primitive: uniform-vector-read! uve [port-or-fdes] [start] [end] Attempts to read all elements of URA, in lexicographic order, as binary objects from PORT-OR-FDES. If an end of file is encountered during uniform-array-read! the objects up to that point only are put into URA (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-FDES may be omitted, in which case it defaults to the value returned by `(current-input-port)'. -- primitive: uniform-array-write ura [port-or-fdes] [start] [end] -- primitive: uniform-vector-write uve [port-or-fdes] [start] [end] Writes all elements of URA as binary objects to PORT-OR-FDES. 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-FDES may be omitted, in which case it defaults to the value returned by `(current-output-port)'.  File: guile-ref.info, Node: Bit Vectors, Prev: Uniform Array, Up: Arrays Bit Vectors ----------- Bit vectors can be written and read as a sequence of `0's and `1's prefixed by `#*'. #b(#f #f #f #t #f #t #f) => #*0001010 Some of these operations will eventually be generalized to other uniform-arrays. -- primitive: bit-count bool bv Returns the number occurrences of BOOL in BV. -- primitive: bit-position bool bv k Returns the minimum index of an occurrence of BOOL in BV which is at least K. If no BOOL occurs within the specified range `#f' is returned. -- primitive: bit-invert! bv Modifies BV by replacing each element with its negation. -- primitive: bit-set*! bv uve bool If uve is a bit-vector BV and uve must be of the same length. If BOOL is `#t', uve is OR'ed into BV; If BOOL is `#f', the inversion of uve is AND'ed into BV. If uve is a unsigned integer vector all the elements of uve must be between 0 and the `LENGTH' of BV. The bits of BV corresponding to the indexes in uve are set to BOOL. The return value is unspecified. -- primitive: bit-count* bv uve bool Returns (bit-count (bit-set*! (if bool bv (bit-invert! bv)) uve #t) #t). BV is not modified.  File: guile-ref.info, Node: Association Lists and Hash Tables, Prev: Arrays, Up: Data Structures Association Lists and Hash Tables ================================= This chapter discusses dictionary objects: data structures that are useful for organizing and indexing large bodies of information. * Menu: * Dictionary Types:: About dictionary types; what they're good for. * Association Lists:: * Hash Tables::  File: guile-ref.info, Node: Dictionary Types, Next: Association Lists, Up: Association Lists and Hash Tables 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.  File: guile-ref.info, Node: Association Lists, Next: Hash Tables, Prev: Dictionary Types, Up: Association Lists and Hash Tables Association Lists ----------------- -- primitive: acons key value alist Adds 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. -- primitive: assq key alist -- primitive: assv key alist -- primitive: assoc key alist Fetches the entry in ALIST that is associated with KEY. To decide whether the argument KEY matches a particular entry in ALIST, `assq' compares keys with `eq?', `assv' uses `eqv?' and `assoc' uses `equal?'. If KEY cannot be found in ALIST (according to whichever equality predicate is in use), then `#f' is returned. These functions return the entire alist entry found (i.e. both the key and the value). -- primitive: assq-ref alist key -- primitive: assv-ref alist key -- primitive: assoc-ref alist key Like `assq', `assv' and `assoc', except that only the value associated with KEY in ALIST is returned. These functions are equivalent to (let ((ent (ASSOCIATOR KEY ALIST))) (and ent (cdr ent))) where ASSOCIATOR is one of `assq', `assv' or `assoc'. -- primitive: assq-set! alist key value -- primitive: assv-set! alist key value -- primitive: assoc-set! alist key value 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. -- primitive: assq-remove! alist key -- primitive: assv-remove! alist key -- primitive: assoc-remove! alist key Delete any entry in ALIST associated with KEY, and return the resulting alist. *Caution:* it is important to remember that the SET! and REMOVE! functions do not always operate as intended. In some circumstances, the functions will try to modify the first element in the list; for example, when adding a new entry to an alist, `assoc-set!' conses the new key-value pair on to the beginning of the alist. However, when this happens, the symbol to which the alist is bound has not been modified---it still points to the old ``beginning'' of the list, which still does not contain the new entry. In order to be sure that these functions always succeed, even when modifying the beginning of the alist, you will have to rebind the alist symbol explicitly to point to the value returned by `assoc-set!', like so: (set! my-alist (assq-set! my-alist 'sun4 "sparc-sun-solaris")) Because of this restriction, 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. 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" "Bismarck")) capitals => (("South Dakota" . "Bismarck") ("New York" . "Albany") ("Oregon" . "Salem") ("Florida" . "Miami")) ;; And we got Florida wrong. (set! capitals (assoc-set! capitals "Florida" "Tallahassee")) capitals => (("South Dakota" . "Bismarck") ("New York" . "Albany") ("Oregon" . "Salem") ("Florida" . "Tallahassee")) ;; After Oregon secedes, we can remove it. (set! capitals (assoc-remove! capitals "Oregon")) capitals => (("South Dakota" . "Bismarck") ("New York" . "Albany") ("Florida" . "Tallahassee"))  File: guile-ref.info, Node: Hash Tables, Prev: Association Lists, Up: Association Lists and Hash Tables Hash Tables ----------- Like the association list functions, the hash table functions come in several varieties: `hashq', `hashv', and `hash'. The `hashq' functions use `eq?' to determine whether two keys match. The `hashv' functions use `eqv?', and the `hash' functions use `equal?'. In each of the functions that follow, the TABLE argument must be a vector. The KEY and VALUE arguments may be any Scheme object. -- primitive: hashq-ref table key [default] -- primitive: hashv-ref table key [default] -- primitive: hash-ref table key [default] Look up KEY in the hash table TABLE, and return the value (if any) associated with it. If KEY is not found, return DEFAULT (or `#f' if no DEFAULT argument is supplied). -- primitive: hashq-set! table key value -- primitive: hashv-set! table key value -- primitive: hash-set! table key value Find the entry in TABLE associated with KEY, and store VALUE there. -- primitive: hashq-remove! table key -- primitive: hashv-remove! table key -- primitive: hash-remove! table key Remove KEY (and any value associated with it) from TABLE. The standard hash table functions may be too limited for some applications. For example, you may want a hash table to store strings in a case-insensitive manner, so that references to keys named ``foobar'', ``FOOBAR'' and ``FooBaR'' will all yield the same item. Guile provides you with "extended" hash tables that permit you to specify a hash function and associator function of your choosing. The functions described in the rest of this section can be used to implement such custom hash table structures. If you are unfamiliar with the inner workings of hash tables, then this facility will probably be a little too abstract for you to use comfortably. If you are interested in learning more, see an introductory textbook on data structures or algorithms for an explanation of how hash tables are implemented. -- primitive: hashq key size -- primitive: hashv key size -- primitive: hash key size Default hash functions for Guile hash tables. KEY is the object to be hashed, and SIZE is the size of the target hash table. Each function returns an integer in the range 0 to SIZE-1. -- primitive: hashx-ref hasher assoc table key [default] -- primitive: hashx-set! hasher assoc table key value -- primitive: hashx-remove! hasher assoc table key These behave the same way as the corresponding `ref' and `set!' functions described above, but use HASHER as a hash function and ASSOC to compare keys. `hasher' must be a function that takes two arguments, a key to be hashed and a table size. `assoc' must be an associator function, like `assoc', `assq' or `assv'. By way of illustration, `hashq-ref table key' is equivalent to `hashx-ref hashq assq table key'. -- primitive: hashq-get-handle table key -- primitive: hashv-get-handle table key -- primitive: hash-get-handle table key -- primitive: hashx-get-handle hasher assoc table key These procedures are similar to their `-ref' cousins, but return a "handle" from the hash table rather than the value associated with KEY. By convention, a handle in a hash table is the pair which associates a key with a value. Where `hashq-ref table key' returns only a `value', `hashq-get-handle table key' returns the pair `(key . value)'. -- primitive: hashq-create-handle! table key init -- primitive: hashv-create-handle! table key init -- primitive: hash-create-handle! table key init -- primitive: hashx-create-handle! hasher assoc table key init These functions look up KEY in TABLE and return its handle, If KEY is not already present, a new handle is created which associates KEY with INIT.  File: guile-ref.info, Node: Strings, Next: Characters, Prev: Data Structures, Up: Top Strings ******* [FIXME: this is pasted in from Tom Lord's original guile.texi and should be reviewed] For the sake of efficiency, two special kinds of strings are available in Guile: shared substrings and the misleadingly named ``read-only'' strings. It is not necessary to know about these to program in Guile, but you are likely to run into one or both of these special string types eventually, and it will be helpful to know how they work. * Menu: * String Fun:: New functions for manipulating strings. * Shared Substrings:: Strings which share memory with each other. * Read Only Strings:: Treating certain non-strings as strings.  File: guile-ref.info, Node: String Fun, Next: Shared Substrings, Up: Strings String Fun ========== -- primitive: string-index str chr [frm [to]] Return the index of the first occurrence of CHR in STR. The optional integer arguments FRM and TO limit the search to a portion of the string. This procedure essentially implements the `index' or `strchr' functions from the C library. -- primitive: string-rindex str chr [frm [to]] Like `string-index', but search from the right of the string rather than from the left. This procedure essentially implements the `rindex' or `strrchr' functions from the C library. -- primitive: substring-move-right! str1 start1 end1 str2 start2 -- primitive: substring-move-left! str1 start1 end1 str2 start2 Copy the substring of STR1 bounded by START1 and END1 into STR2 beginning at position END2. `substring-move-right!' begins copying from the rightmost character and moves left, and `substring-move-left!' copies from the leftmost character moving right. It is useful to have two functions that copy in different directions so that substrings can be copied back and forth within a single string. If you wish to copy text from the left-hand side of a string to the right-hand side of the same string, and the source and destination overlap, you must be careful to copy the rightmost characters of the text first, to avoid clobbering your data. Hence, when STR1 and STR2 are the same string, you should use `substring-move-right!' when moving text from left to right, and `substring-move-left!' otherwise. If `str1' and `str2' are different strings, it does not matter which function you use. -- primitive: vector-move-right! vec1 start1 end1 vec2 start2 -- primitive: vector-move-left! vec1 start1 end1 vec2 start2 Vector versions of `substring-move-right!' and `substring-move-left!' -- primitive: substring-fill! str start end fill-char Change every character in STR between START and END to FILL-CHAR. -- primitive: string-null? str Return `#t' if STR's length is nonzero, and `#f' otherwise. -- primitive: string-upcase! str -- primitive: string-downcase! str Upcase or downcase every character in `str', respectively.  File: guile-ref.info, Node: Shared Substrings, Next: Read Only Strings, Prev: String Fun, Up: Strings Shared Substrings ================= Whenever you extract a substring using `substring', the Scheme interpreter allocates a new string and copies data from the old string. This is expensive, but `substring' is so convenient for manipulating text that programmers use it often. Guile Scheme provides the concept of the "shared substring" to improve performance of many substring-related operations. A shared substring is an object that mostly behaves just like an ordinary substring, except that it actually shares storage space with its parent string. -- primitive: make-shared-substring str start [end] Return a shared substring of STR. The semantics are the same as for the `substring' function: the shared substring returned includes all of the text from STR between indexes START (inclusive) and END (exclusive). If END is omitted, it defaults to the end of STR. The shared substring returned by `make-shared-substring' occupies the same storage space as STR. Example: (define foo "the quick brown fox") (define bar (make-shared-substring some-string 4 9)) foo => "t h e q u i c k b r o w n f o x" bar =========> |---------| The shared substring BAR is not given its own storage space. Instead, the Guile interpreter notes internally that BAR points to a portion of the memory allocated to FOO. However, BAR behaves like an ordinary string in most respects: it may be used with string primitives like `string-length', `string-ref', `string=?'. Guile makes the necessary translation between indices of BAR and indices of FOO automatically. (string-length? bar) => 5 ; bar only extends from indices 4 to 9 (string-ref bar 3) => #\c ; same as (string-ref foo 7) (make-shared-substring bar 2) => "ick" ; can even make a shared substring! Because creating a shared substring does not require allocating new storage from the heap, it is a very fast operation. However, because it shares memory with its parent string, a change to the contents of the parent string will implicitly change the contents of its shared substrings. (string-set! foo 7 #\r) bar => "quirk" Guile considers shared substrings to be immutable. This is because programmers might not always be aware that a given string is really a shared substring, and might innocently try to mutate it without realizing that the change would affect its parent string. (We are currently considering a "copy-on-write" strategy that would permit modifying shared substrings without affecting the parent string.) In general, shared substrings are useful in circumstances where it is important to divide a string into smaller portions, but you do not expect to change the contents of any of the strings involved.  File: guile-ref.info, Node: Read Only Strings, Prev: Shared Substrings, Up: Strings Read Only Strings ================= Type-checking in Guile primitives distinguishes between mutable strings and read only strings. Mutable strings answer `#t' to `string?' while read only strings may or may not. All kinds of strings, whether or not they are mutable return #t to this: -- primitive: read-only-string? OBJ Return true of OBJ can be read as a string, This illustrates the difference between `string?' and `read-only-string?': (string? "a string") => #t (string? 'a-symbol") => #f (read-only-string? "a string") => #t (read-only-string? 'a-symbol") => #t "Read-only" refers to how the string will be used, not how the string is permitted to be used. In particular, all strings are "read-only strings" even if they are mutable, because a function that only reads from a string can certainly operate on even a mutable string. Symbols are an example of read-only strings. Many string functions, such as `string-append' are happy to operate on symbols. Many functions that expect a string argument, such as `open-file', will accept a symbol as well. Shared substrings, discussed in the previous chapter, also happen to be read-only strings.