• Home
• All tickets
• All wiki pages

Source for wiki NumericVectorsCowan version 24

author

cowan

comment

ipnr

127.11.51.1

name

NumericVectorsCowan

readonly

0

text

This SRFI provides an API for specialized numeric vectors distinguished by their ''representation type''.  The `u8` type is the same as the R7RS bytevector type, but the other types are all disjoint from all other Scheme types.  It may be useful for Schemes on the JVM or the CLR to use this SRFI to provide access to the platform's native numeric vectors.

This design subsumes [http://srfi.schemers.org/srfi-4/srfi-4.html SRFI 4].  There are many procedures, but many of them can be easily inlined by even a very dumb compiler, providing high efficiency.   The procedures provided in the present proposal are the numeric-vector analogues of the R7RS-small vector API plus [http://srfi.schemers.org/srfi-133/srfi-133.html SRFI 133].

== Representation types ==

The [type] values are:

 `u1`::
  unsigned 1-bit integer (bit)
 `u8`::
  unsigned 8-bit integer
 `s8`::
  signed 8-bit integer
 `u16`::
  unsigned 16-bit integer
 `s16`::
  signed 16-bit integer
 `u32`::
  unsigned 32-bit integer
 `s32`::
  signed 32-bit integer
 `u64`::
  unsigned 64-bit integer
 `s64`::
  signed 64-bit integer
 `f32`::
  32-bit float
 `f64`::
  64-bit float
 `c64`::
  64-bit complex number
 `c128`::
  128-bit complex number

== Constructors ==

`(make-[type]vector `''k'' [ ''fill'' ]`)`

Returns a newly allocated numeric vector of length ''k''.  ''Fill'' is converted to a binary value according to [type] and used to fill the vector; if ''fill'' is not specified, the values of the elements are unspecified.  It is an error if ''fill'' cannot be converted to [type].

`([type]vector ` ''v'' ... `)`

Returns a newly allocated numeric vector of length ''k'', where ''k'' is the number of arguments to the procedure.  It is filled with the binary values resulting from encoding the ''v'' arguments according to [type].  It is an error if an argument cannot be converted to [type].

`([type]vector-unfold `''proc length initial-seed''`)`

Returns a newly allocated [type]vector whose length is ''length'' and iterates across each index ''k'' between 0 and ''length'', applying ''proc'' at each iteration to the current index and current seed, in that order, to receive 2 values: first, the element to put in the ''k''th slot of the new vector and a new seed for the next iteration.  Note that the termination condition is different from the unfold procedure of SRFI 1. 

Examples: 

{{{
(s8vector-unfold (lambda (i x) (values x (- x 1))) 
                 10 0) 
=> #s8(0 -1 -2 -3 -4 -5 -6 -7 -8 -9)
}}}

Construct a vector of the sequence of integers in the range [0,n).

{{{
(u8vector-unfold values n) 
=> #u8(0 1 2 ... n-2 n-1)
}}} 

Copy vector. 

{{{
(f64vector-unfold (lambda (i) (vector-ref vector i)) 
                 (vector-length vector))
}}} 

`([type]vector-unfold-right `''proc length initial-seed''`)`

Like `[type]vector-unfold`, but it uses ''proc'' to generate elements from right-to-left, rather than left-to-right. The first index used is ''length'' - 1. Note that the termination condition is different from the unfold-right procedure of SRFI 1. 

Examples: 

Construct a vector of pairs of non-negative integers whose values sum to 4. 

{{{
(u8vector-unfold-right (lambda (i x) (values (cons i x) (+ x 1))) 5 0) 
=> #u8((0 . 4) (1 . 3) (2 . 2) (3 . 1) (4 . 0)) 
}}}

Reverse vector. 

{{{
(float64-vector-unfold-right (lambda (i x) (values (f64vector-ref vector x) (+ x 1))) 
                       (f64vector-length vector) 
                       0)
}}}

`([type]vector-copy `''[type]vec'' [''start'' [''end'']]`)`

Allocates a new [type]vector whose length is ''end - start'' and fills it with elements from ''[type]vec''.
Examples: 

`([type]vector-reverse-copy [type]vec `[''start'' [''end'']]`)`

Like `[type]vector-copy`, but it copies the elements in the reverse order from ''[type]vec''. 

`([type]vector-append `''[type]vec'' ...`)`

Returns a newly allocated vector that contains all elements in order from the locations in the ''[type]vec''s.

`([type]vector-concatenate `''list-of-[type]vectors''`)`

Appends each vector in ''list-of-[type]vectors''. This is equivalent to: `(apply [type]vector-append list-of-[type]vectors)`.  However, it may be implemented better. 

`([type]vector-append-subvectors `[ ''[type]vec start end'' ] ...`)`

Returns a vector that contains every element of each ''[type]vec'' from ''start'' to ''end'' in the specified order. This procedure is a generalization of `vector-append`. 

== Predicates ==

`([type]vector? `''obj''`)`

Returns `#t` if ''obj'' is a [type]vector, and `#f` if it is not.

`([type]vector-empty? ` ''[type]vector''`)`

Returns `#t` if ''[type]vector'' has length 0, and `#f` otherwise.

`(vector= `''elt=? [type]vec'' ...`)`

Vector structure comparator, generalized across user-specified element comparators. [Type]vectors ''a'' and ''b'' are considered equal by `[type]vector=` iff their lengths are the same, and if for each respective element ''Ea'' and ''Eb'', `(`''elt=? Ea Eb''`)` returns a true value. The ''elt='' procedure is always applied to two arguments. Element comparison must be consistent with `eq`; that is, if `(eq? `''Ea Eb''`)` results in a true value, then `(`''elt=? Ea Eb''`)` must also result in a true value. This may be exploited to avoid unnecessary element comparisons.

If there are only zero or one [type]vector arguments, `#t` is automatically returned. The dynamic order in which comparisons of elements and of [type]vectors are performed is left completely unspecified; do not rely on a particular order. 

== Selectors ==

`([type]vector-ref` ''[type]vector k''`)`

Returns a Scheme number corresponding to the ''k''th element of ''[type]vector''.  Note that `u8vector-ref` is the same as the R7RS-small procedure `bytevector-u8-ref`.

`([type]vector-length ` ''[type]vector''`)`

Returns the length of ''[type]vector''.

== Iteration ==

`([type]vector-fold `''kons knil vec,,1,, vec,,2,,'' ...`)`

The fundamental [type]vector iterator. ''Kons'' is iterated over each value in all of the [type]vectors, stopping at the end of the shortest; ''kons'' is applied as `(''kons state'' `(`''[type]vector-ref vec,,1,, i''`) (`''[type]vector-ref vec,,2,, i''`)` ...`)` where ''state'' is the current state value — the current state begins with ''knil'', and becomes whatever ''kons'' returned on the previous iteration — and ''i'' is the current index. 

The iteration is strictly left-to-right. 

`([type]vector-fold `''kons knil [type]vec,,1,, [type]vec,,2,,'' ...`)`

Similar to `[type]vector-fold`, but it iterates right to left instead of left to right. 

`([type]vector-map `''proc [type]vector'' ...`)`

Returns a newly allocated [type]vector which contains the results of applying ''proc'' to the elements of the ''[type]vectors'' in an unspecified order.

`([type]vector-map! `''proc output-[type]vector [type]vector'' ...`)`

Writes the results of applying ''proc'' to the elements of the ''[type]vectors'' into the corresponding elements of ''output-[type]vector'' in an unspecified order.  It is not an error for ''output-[type]vector'' to be the same as one of the ''[type]vectors''.  Returns an unspecified value.

`([type]vector-for-each `''proc [type]vector'' ...`)`

Applies ''proc'' to the elements of the ''[type]vectors'' in order from first to last and discards the results.  Returns an unspecified value.

`([type]vector-count `''pred? vec,,1,, vec,,2,,'' ...`)`

Counts the number of parallel elements in the [type]vectors that satisfy ''pred?'', which is applied, for each index ''i'' in the range [0, ''length'') where ''length'' is the length of the smallest vector argument, to each parallel element in the [type]vectors, in order. 

`([type]vector-cumulate `''f vec knil''`)`

Returns a newly allocated [type]vector ''new'' with the same length as ''[type]vec''. Each element ''i'' of ''new'' is set to the result of invoking ''f'' on ''new,,i-1,, and vec,,i,,.  However, for the first call on ''f'', the first argument is ''knil''. The new [type]vector is returned.

== Searching ==

FIXME: markup

`(vector-index `pred? vec1 vec2 ...)

Finds & returns the index of the first elements in vec1 vec2 ... that satisfy pred?. If no matching element is found by the end of the shortest vector, #f is returned. 

`(vector-index-right `pred? vec1 vec2 ...)

Like vector-index, but it searches right-to-left, rather than left-to-right, and all of the vectors must have the same length. 

`(vector-skip `pred? vec1 vec2 ...)

Finds & returns the index of the first elements in vec1 vec2 ... that do not satisfy pred?. If all the values in the vectors satisfy pred? until the end of the shortest vector, this returns #f.

(vector-skip-right pred? vec1 vec2 ...)

Like vector-skip, but it searches for a non-matching element right-to-left, rather than left-to-right, and it is an error if all of the vectors do not have the same length. 

(vector-binary-search vec value cmp)

Similar to vector-index and vector-index-right, but instead of searching left to right or right to left, this performs a binary search. If there is more than one element of vec that matches value in the sense of cmp, vector-binary-search may return the index of any of them.

cmp should be a procedure of two arguments and return a negative integer, which indicates that its first argument is less than its second, zero, which indicates that they are equal, or a positive integer, which indicates that the first argument is greater than the second argument.

(vector-any pred? vec1 vec2 ...)

Finds the first set of elements in parallel from vec1 vec2 ... for which pred? returns a true value. If such a parallel set of elements exists, vector-any returns the value that pred? returned for that set of elements. The iteration is strictly left-to-right. 

(vector-every pred? vec1 vec2 ...)

If, for every index i between 0 and the length of the shortest vector argument, the set of elements (vector-ref vec1 i) (vector-ref vec2 i) ... satisfies pred?, vector-every returns the value that pred? returned for the last set of elements, at the last index of the shortest vector. The iteration is strictly left-to-right. 

(vector-partition pred? vec)

A vector the same size as vec is newly allocated and filled with all the elements of vec that satisfy pred? in their original order followed by all the elements that do not satisfy pred, also in their original order.  Two values are returned, the newly allocated vector and the index of the leftmost element that does not satisfy pred. 

== Mutators ==

These procedures return an unspecified value.

`([type]vector-set!` ''[type]vector k v''`)`

Converts ''v'' to a binary value encoded according to [type] and places it into the ''k''th element of ''[type]vector''.  It is an error if ''v'' cannot be converted to [type].  Note that `u8vector-set!` is the same as the R7RS-small procedure `bytevector-u8-set!`.

`(vector-swap! `''[type]vec i j''`)` 

Swaps or exchanges the values of the locations in ''[type]vec'' at ''i'' and ''j''.

`(vector-fill! `''[type]vec fill'' [ ''start'' [ ''end'' ]]`)`

Assigns the value of every location in [type]vec between ''start'', which defaults to 0 and ''end'', which defaults to the length of ''vec'', to ''fill''.   It is an error if ''fill'' cannot be converted to [type].

`(vector-reverse! `[type]vec '' [ ''start'' [ ''end'' ]]`)`

Destructively reverses the contents of the sequence of locations in ''[type]vec'' between ''start'' and ''end''.

`(vector-copy! `''to at from '' [ ''start'' [ ''end'' ]]`)`

Copies the elements of [type]vector ''from'' between ''start'' and ''end'' to [type]vector ''to'', starting at ''at''. The order in which elements are copied is unspecified, except that if the source and destination overlap, copying takes place as if the source is first copied into a temporary vector and then into the destination. This can be achieved without allocating storage by making sure to copy in the correct direction in such circumstances. 

`(vector-reverse-copy! `''to at from '' [ ''start'' [ ''end'' ]]`)`

Like ``vector-copy`, but the elements appear in ''to'' in reverse order.

== Conversions to numeric vectors ==

It is an error if a value being used to fill an element of a [type]vector cannot be converted to [type].

`(vector->[type]vector `''vector'' [''start'' [ ''end'' ] ]`)`

Returns a newly allocated [type]vector of length ''end - start'', filled with the corresponding elements of ''vector''.

`(list->[type]vector `''list''`)`

Returns a newly allocated [type]vector whose length is the length of ''list'', filled with the elements of ''list''.

`(vector->[type]vector! `''[type]vector at vector'' [''start'' [ ''end'' ] ]`)`

Writes the elements of ''vector'' from ''start'' to ''end'' into ''[type]vector'' starting at ''at''.

`(list->[type]vector! `''list [type]vector at''`)`

Writes the elements of ''list'' into ''[type]vector'' starting at ''at''.

== Conversions from numeric vectors ==

`([type]vector->vector `''[type]vector'' [ ''start'' [ ''end'' ] ]`)`

`([type]vector->list `''[type]vector'' [ ''start'' [ ''end'' ] ]`)`

Returns a newly allocated vector or list of length ''end - start'' with the elements of ''[type]vector'' from ''start'' to ''end''.

`([type]vector->vector! `''vector at [type]vector'' [''start'' [ ''end'' ] ]`)`

Writes the elements of ''[type]vector'' from ''start'' to ''end'' into ''vector'' starting at ''at''.

== Textual input and output ==

The external representation of a numeric vector consists of a `#` character followed by the two- to four-character representation of [type] with no intervening whitespace.  This prefix is followed, after optional whitespace, by the representation of a list produced as if by `[type]vector->list`.  The prefix is interpreted case-insensitively.

`(array-read ` [ ''input-port'' ]`)`

Reads the external representation of a [type]vector from ''input-port'' (the current input port if ''input-port'' is not specified) and returns the corresponding [type]vector. 

`([type]vector-write `''[type]vector'' [ ''stream'' ]`)`

Writes the external representation of ''[type]vector'' from ''output-port'' (the current output port if ''output-port'' is not specified) and returns an unspecified value.

This SRFI recommends, but does not require, that the standard Scheme procedures `read`, `write`, and `display` be extended to deal with external representations of [type]vectors.  On R7RS systems, if `read` accepts the external representation of [type]vectors, it must also be allowed in Scheme code, in which case array constants are self-quoting.

== Binary input and output ==

For the procedures in this section, ''b'' is a constant whose value depends on the type, representing the number of bytes required for the type.  Thus it is 1 for types `u8` and `s8`, 2 for types `u16` and `s16`, and so on up to 16 for type `c128`.

`(input-[type]vector `''k'' [ ''port'' ]`)`

`(input-[type]vector-be `''k'' [ ''port'' ]`)`

`(input-[type]vector-le `''k'' [ ''port'' ]`)`

Read ''k'' * ''b'' bytes from ''port'' into a newly allocated [type]vector using native/big-endian/little-endian order and returns it.

`(input-[type]vector! `''[type]vector'' [ ''port'' [ ''start'' [ ''end'' ] ] ]`)`

`(input-[type]vector-le! `''[type]vector'' [ ''port'' [ ''start'' [ ''end'' ] ] ]`)`

`(input-[type]vector-be! `''[type]vector'' [ ''port'' [ ''start'' [ ''end'' ] ] ]`)`

Read ''end * b - start * b'' bytes from ''port'' into ''[type]vector'' starting at ''start'' using native/big-endian/little-endian order.  Returns the number of bytes read divided by ''b'', or an eof object if no bytes are available.  If the number of bytes available is not a multiple of ''b'', the value of the element of ''[type]vector'' for which ''b'' bytes are not available is unspecified.

`(output-[type]vector `''[type]vector [ ''port'' [ ''start'' [ ''end'' ] ] ]`)`

`(output-[type]vector-le `''[type]vector [ ''port'' [ ''start'' [ ''end'' ] ] ]`)`

`(output-[type]vector-be `''[type]vector [ ''port'' [ ''start'' [ ''end'' ] ] ]`)`

Write ''end * b - start * b'' bytes to ''port'' from ''[type]vector'' starting at ''start'' using native/big-endian/little-endian order.  Returns an unspecified value.

== Packaging ==

SRFI 4 provides just 8 procedures per type: the basic and multi-argument constructors, the predicate, the basic accessor, the basic mutator, length, and conversion to and from lists.  Since there are many more procedures, it makes sense to factor this into separate libraries.  Most programs won't require all the representation types, so factoring horizontally into 12 libraries based on `[type]` is a simple approach.  

== Implementation ==

[https://gist.github.com/ijp/1e0e67ff93c486f66fc8 This syntax-rules macro by Ian Price] will be helpful in implementing lots of similar but not identical procedures for the 12 types.

time

2017-03-24 23:18:20

version

24