diff options
| -rw-r--r-- | srfi-214.html | 26 |
1 files changed, 13 insertions, 13 deletions
diff --git a/srfi-214.html b/srfi-214.html index 40bdb0e..cf09c1c 100644 --- a/srfi-214.html +++ b/srfi-214.html @@ -19,13 +19,13 @@ <li>Draft #2 published: 2021-01-13</li> </ul> <h2 id="abstract">Abstract</h2> -<p>A <em>flexvector</em>, also known as a dynamic array or an arraylist, is a mutable vector-like data structure with an adjustable size. Flexvectors allow fast random access and fast insertion/removal at the end. This SRFI defines a suite of operations on flexvectors, modeled after <a target="_blank" href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a>'s vector operations.</p> +<p>A <em>flexvector</em>, also known as a dynamic array or an arraylist, is a mutable vector-like data structure with an adjustable size. Flexvectors allow fast random access and fast insertion/removal at the end. This SRFI defines a suite of operations on flexvectors, modeled after <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a>'s vector operations.</p> <h2 id="rationale">Rationale</h2> -<p>Unlike the default vector datatype of many other languages, Scheme vectors have a fixed length. This makes vectors unusable as mutable stacks or queues, and is the reason that <a target="_blank" href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a> lacks common collection operations like <code>filter</code>.</p> -<p>In fact, no Scheme standard defines a mutable datatype that is suitable for this very common purpose, analogous to a Java <code>ArrayList</code> or to the default list data structure in JavaScript or Python. <a target="_blank" href="https://srfi.schemers.org/srfi-117/srfi-117.html">SRFI 117</a> defines the commonly-used "tconc" mutable queue, but it is a linked list. And <a target="_blank" href="https://srfi.schemers.org/srfi-134/srfi-134.html">SRFI 134</a> defines a deque datatype, but that datatype is immutable. Neither data structure has the (often useful) properties of being a mutable, contiguous, random-access sequence.</p> +<p>Unlike the default vector datatype of many other languages, Scheme vectors have a fixed length. This makes vectors unusable as mutable stacks or queues, and is the reason that <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a> lacks common collection operations like <code>filter</code>.</p> +<p>In fact, no Scheme standard defines a mutable datatype that is suitable for this very common purpose, analogous to a Java <code>ArrayList</code> or to the default list data structure in JavaScript or Python. <a href="https://srfi.schemers.org/srfi-117/srfi-117.html">SRFI 117</a> defines the commonly-used "tconc" mutable queue, but it is a linked list. And <a href="https://srfi.schemers.org/srfi-134/srfi-134.html">SRFI 134</a> defines a deque datatype, but that datatype is immutable. Neither data structure has the (often useful) properties of being a mutable, contiguous, random-access sequence.</p> <p>This SRFI does not define a comparator or any sorting procedures, in order to ensure that it has no dependencies. These may be defined in future SRFIs.</p> <h3 id="terminology">Terminology</h3> -<p>What this SRFI calls a <em>flexvector</em> is better known as a <a target="_blank" href="https://en.wikipedia.org/wiki/Dynamic_array"><em>dynamic array</em></a>. This data structure has a wide variety of names in different languages:</p> +<p>What this SRFI calls a <em>flexvector</em> is better known as a <a href="https://en.wikipedia.org/wiki/Dynamic_array"><em>dynamic array</em></a>. This data structure has a wide variety of names in different languages:</p> <ul> <li>JavaScript and Ruby call it an <em>array</em></li> <li>Python calls it a <em>list</em></li> @@ -33,13 +33,13 @@ </ul> <p>Scheme literature already uses the terms <em>list</em> (for <code>cons</code> lists), <em>vector</em> (for fixed-length vectors), and <em>array</em> (for fixed-length numeric arrays), so a new term is needed. Because <em>array</em> in Scheme refers to a numeric array, the term <em>dynamic array</em> is not ideal. <em>Dynamic vector</em> is a possibility, but <code>dynamic-vector</code> would be an unwieldy prefix due to its length. The newly-minted term <em>flexvector</em> communicates this data structure's flexible size and its relationship to Scheme vectors, while being only as long as an existing Scheme data type name (<code>bytevector</code>).</p> <h3 id="procedure-inclusion-and-naming">Procedure inclusion and naming</h3> -<p>This SRFI is primarily modeled on <a target="_blank" href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a>. It includes flexvector equivalents of all SRFI 133 procedures, most with the same names and argument order. There are three notable exceptions:</p> +<p>This SRFI is primarily modeled on <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a>. It includes flexvector equivalents of all SRFI 133 procedures, most with the same names and argument order. There are three notable exceptions:</p> <ol> -<li><code>flexvector-unfold</code> mimics the API of <a target="_blank" href="https://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a>'s <code>unfold</code>, not SRFI 133's <code>vector-unfold</code>. <code>vector-unfold</code> is limited by the necessity of a fixed vector length, while <code>flexvector-unfold</code> may generate a flexvector of any length, and so the <code>unfold</code> API is more useful.</li> +<li><code>flexvector-unfold</code> mimics the API of <a href="https://srfi.schemers.org/srfi-1/srfi-1.html">SRFI 1</a>'s <code>unfold</code>, not SRFI 133's <code>vector-unfold</code>. <code>vector-unfold</code> is limited by the necessity of a fixed vector length, while <code>flexvector-unfold</code> may generate a flexvector of any length, and so the <code>unfold</code> API is more useful.</li> <li>There is no flexvector equivalent of <code>vector-unfold!</code>, because flexvectors use the list version of <code>unfold</code>, which has no <code>unfold!</code> equivalent with a similar API.</li> -<li>The flexvector equivalent of <code>vector=</code> is <code>flexvector=?</code>. It is conventional for Scheme equality predicates to end in <code>=?</code> (e.g., <code>symbol=?</code>, <code>string=?</code>), and most data structure SRFIs follow this convention (see <a target="_blank" href="https://srfi.schemers.org/srfi-113/srfi-113.html">SRFI 113</a>, <a target="_blank" href="https://srfi.schemers.org/srfi-125/srfi-125.html">125</a>, <a target="_blank" href="https://srfi.schemers.org/srfi-146/srfi-146.html">146</a>). This SRFI follows established convention, even when it does not match SRFI 133's procedure names.</li> +<li>The flexvector equivalent of <code>vector=</code> is <code>flexvector=?</code>. It is conventional for Scheme equality predicates to end in <code>=?</code> (e.g., <code>symbol=?</code>, <code>string=?</code>), and most data structure SRFIs follow this convention (see <a href="https://srfi.schemers.org/srfi-113/srfi-113.html">SRFI 113</a>, <a href="https://srfi.schemers.org/srfi-125/srfi-125.html">125</a>, <a href="https://srfi.schemers.org/srfi-146/srfi-146.html">146</a>). This SRFI follows established convention, even when it does not match SRFI 133's procedure names.</li> </ol> -<p>Additionally, this SRFI includes deque-like operations that reference, add to, and remove from both ends of a flexvector. The naming convention for these operations is taken from <a target="_blank" href="https://srfi.schemers.org/srfi-134/srfi-134.html">SRFI 134</a>, which uses the terms <em>front</em> and <em>back</em>. <em>Front</em> refers to the start of the flexvector (index 0), while <em>back</em> refers to the end (index <code>(- (flexvector-length x) 1)</code>).</p> +<p>Additionally, this SRFI includes deque-like operations that reference, add to, and remove from both ends of a flexvector. The naming convention for these operations is taken from <a href="https://srfi.schemers.org/srfi-134/srfi-134.html">SRFI 134</a>, which uses the terms <em>front</em> and <em>back</em>. <em>Front</em> refers to the start of the flexvector (index 0), while <em>back</em> refers to the end (index <code>(- (flexvector-length x) 1)</code>).</p> <h2 id="specification">Specification</h2> <p>Flexvectors have the same random-access performance guarantees as ordinary vectors. In particular, if a given Scheme implements vectors with contiguous memory locations and O(1) random access and mutation, flexvectors must also have these performance characteristics. Additionally, appending to the back of a flexvector has the same (amortized) performance as setting an existing location in the same flexvector.</p> <p>In this section, the following notation is used to specify parameters and examples:</p> @@ -395,20 +395,20 @@ zot <p>Both <code>start</code> and <code>end</code> are clamped to the range [0, <code>(string-length string)</code>). It is an error if <code>end</code> is less than <code>start</code>.</p> <h4 id="flexvector-generator"><code>flexvector->generator</code></h4> <p><code>(flexvector->generator fv)</code></p> -<p>Returns a <a target="_blank" href="https://srfi.schemers.org/srfi-158/srfi-158.html">SRFI 158</a> generator that emits the elements of the flexvector <code>fv</code>, in order. If <code>fv</code> is mutated before the generator is exhausted, the generator's remaining return values are undefined.</p> +<p>Returns a <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">SRFI 158</a> generator that emits the elements of the flexvector <code>fv</code>, in order. If <code>fv</code> is mutated before the generator is exhausted, the generator's remaining return values are undefined.</p> <h4 id="generator-flexvector"><code>generator->flexvector</code></h4> <p><code>(generator->flexvector gen)</code></p> -<p>Creates a flexvector containing all elements produced by the <a target="_blank" href="https://srfi.schemers.org/srfi-158/srfi-158.html">SRFI 158</a> generator <code>gen</code>.</p> +<p>Creates a flexvector containing all elements produced by the <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">SRFI 158</a> generator <code>gen</code>.</p> <h2 id="implementation">Implementation</h2> -<p><a target="_blank" href="https://github.com/scheme-requests-for-implementation/srfi-214">A sample implementation is available on GitHub.</a> The sample implementation supports Gauche, Sagittarius, and Chibi, and includes a test suite.</p> +<p><a href="https://github.com/scheme-requests-for-implementation/srfi-214">A sample implementation is available on GitHub.</a> The sample implementation supports Gauche, Sagittarius, and Chibi, and includes a test suite.</p> <h2 id="acknowledgements">Acknowledgements</h2> -<p>Thanks to the authors of <a target="_blank" href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a> (John Cowan, and, transitively, Taylor Campbell), on whose work this SRFI is based. Much of the language in this SRFI was copied directly from 133 with only minor changes.</p> +<p>Thanks to the authors of <a href="https://srfi.schemers.org/srfi-133/srfi-133.html">SRFI 133</a> (John Cowan, and, transitively, Taylor Campbell), on whose work this SRFI is based. Much of the language in this SRFI was copied directly from 133 with only minor changes.</p> <h2 id="copyright">Copyright</h2> <p>© Adam Nelson 2020-2021.</p> <p>Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:</p> <p>The above copyright notice and this permission notice (including the next paragraph) shall be included in all copies or substantial portions of the Software.</p> <p>THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.</p> -<p>srfi-158]: <a target="_blank" href="https://srfi.schemers.org/srfi-158/srfi-158.html">https://srfi.schemers.org/srfi-158/srfi-158.html</a></p> +<p>srfi-158]: <a href="https://srfi.schemers.org/srfi-158/srfi-158.html">https://srfi.schemers.org/srfi-158/srfi-158.html</a></p> <hr> <address>Editor: <a href="mailto:srfi-editors+at+srfi+dot+schemers+dot+org">Arthur A. Gleckler</a></address> |