-
Notifications
You must be signed in to change notification settings - Fork 1
/
srfi-118-1.1.html
206 lines (192 loc) · 8.49 KB
/
srfi-118-1.1.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
<!--
SPDX-FileCopyrightText: 2015 Per Bothner <per@bothner.com>
SPDX-License-Identifier: MIT
-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>SRFI 118: Simple adjustable-size strings</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<style type="text/css">
div.title h1 { font-size: small; color: blue }
div.title { font-size: xx-large; color: blue; font-weight: bold }
h1 { font-size: x-large; color: blue }
h2 { font-size: large; color: blue }
/* So var inside pre gets same font as var in paragraphs. */
var { font-family: monospace; }
em.non-terminal { }
em.non-termina-def { }
code.literal { font-style: normal; }
code.literal:before { content: "“" }
code.literal:after { content: "”" }
</style>
</head>
<body>
<div class="title">
<H1>Title</H1>
Simple adjustable-size strings
</div>
<H1>Author</H1>
<p>Per Bothner
<code><a href="mailto:per@bothner.com"><per@bothner.com></a></code></p>
<p>
This SRFI is currently in ``draft'' status.
To see an explanation of
each status that a SRFI can hold, see <a
href="http://srfi.schemers.org/srfi-process.html">here</a>.
To provide input on this SRFI, please
<a href="mailto:srfi minus 118 at srfi dot schemers dot org">mail to
<code><srfi minus 118 at srfi dot schemers dot org></code></a>. See
<a href="../../srfi-list-subscribe.html">instructions here</a> to
subscribe to the list. You can access previous messages via
<a href="mail-archive/maillist.html">the archive of the mailing list</a>.
</p><ul>
<li>Received: <a
href="http://srfi.schemers.org/srfi-118/srfi-118-1.1.html">2014/12/20</a></li>
<li>Draft: 2014/12/20-2015/02/20</li>
</ul>
<h1>Abstract</h1>
<p>
Scheme specifies mutable fixed-length strings.
We add two procedures <code>string-append!</code> and
<code>string-replace!</code> which allow the size of the string to change.
We also require that standard Scheme procedures that return mutable strings
(such as <code>make-string</code>) return variable-size strings.
<h1>Rationale</h1>
<p>
Historically Scheme has only supported fixed-length strings.
Conceptually, strings can be <dfn>immutable</dfn> (read-only)
or <dfn>mutable</dfn> (writable).
Unfortunately, the usefulness of a fixed-size mutable string is
extremely minimal: The main use is for a buffer to which one incrementally
adds more data. So why not fold that functionality into the string API?
I.e. why can't you add just data to the end of a string?
<p>
The implementation difficulty with variable-size strings is you need some kind of
indirection, so you can re-allocate the data when you run out of space.
However, many implementation of string already use such indirection for
various reasons, such as memory management.
<p>
It is worth noting that some string representations use UTF-8
or UTF-16 encoding, for reasons of compactness or compatibility with
other APIs. The obvious disadvantage is that <code>string-ref</code>
is no longer a constant-time operation, but there are ways to work
around that; <code>string-ref</code> isn't really an important operation
for typical string manipulation.
Note that in such an implementation a mutable string is inherently
variable-size. For example, if you replace a 1-byte character with
a 2-byte character then the stored size changes. So you might as well
expose this functionality to the Scheme programmer.
<p>
Common Lisp supports this functionality with an optional
fill-pointer, combined with using <code>adjust-array</code> when
the allocated string fills up.
<p>
One option is to specify 3 kinds of strings: immutable strings,
mutable fixed-size strings, and mutable variable-size strings.
I've argued that the use-case for fixed-size mutable strings is so limited
(and maybe better supported by character uniform arrays)
that mutable strings should by default be variable-size.
Specifically, standard Scheme functions that return mutable strings
should return variable-size mutable strings.
An implementation may provide a mechanism to explicitly create
a fixed-size mutable string (or a character uniform vector); however,
this specification does not propose or recommend that.
<p>
It has <a href="http://trac.sacrideo.us/wg/wiki/BuffersCowan">been suggested</a>
that a more general <q>buffer</q> API might be better than tweaking
the old-fashioned (and potentially inefficient) integer-index-oriented
string APIs. This proposal is much more modest - it just adds two
new procedures. Thus it should be much easier to learn,
and easier to modify Scheme programs to use it.
<h1>Specification</h1>
<p>
We add 2 new functions. The most frequently used is likely to be
<code>string-append!</code>, while <code>string-replace!</code>
handles the general case of in-place replacement of a substring
with another string of possibly different size.
<p>
Standard Scheme functions that return mutable strings,
such as <code>make-string</code> or <code>string-copy</code>,
are specified to return variable-size mutable strings by default.
<pre>
(<b>string-append!</b> <var>string</var> <var>value</var> ...)
</pre>
<blockquote>
<p>
The <var>string</var> must be a variable-size mutable string.
The <code>string-append!</code> procedure extends <var>string</var> by
appending each <var>value</var> (in order) to the end of <var>string</var>.
A <var>value</var> can be a character or a string.
<p>
The following example show to to process a string using
<code>string-for-each</code> and incrementally <q>building</q> a result string
using <code>string-append!</code>:
<pre>
(define (translate-space-to-newline str)
(let ((result (make-string 0)))
(string-for-each
(lambda (ch)
(cond ((char=? ch #\Space)
(string-append! result #\Newline))
((char=? ch #\Return)) ; Ignore
(else
(string-append! result ch))))
str)
result))
</pre>
</blockquote>
<pre>
(<b>string-replace!</b> <var>dst</var> <var>dst-start</var> <var>dst-end</var> <var>src</var> [<var>src-start</var> [<var>src-end</var>]])
</pre>
<blockquote>
Replaces the characters of the variable-size string <var>dst</var> (between
<var>dst-start</var> and <var>dst-end</var>) with the characters of the string
<var>src</var> (between <var>src-start</var> and <var>src-end</var>).
The number of characters from <var>src</var> may be different than the
number replaced in <var>dst</var>, so the string may grow or contract.
The special case where <var>dst-start</var> is equal to <var>dst-end</var>
corresponds to insertion; the case where <var>src-start</var> is equal
to <var>src-end</var> corresponds to deletion.
The order in which characters 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 string and
then into the destination. (This can be achieved without allocating
storage by making sure to copy in the correct direction in such circumstances.)
</blockquote>
<h1>Implementation</h1>
<p>
The implementation is trivial, assuming there is some indirection
between the string object header and the actual stored characters.
<p>
If you have cheap Smalltalk-style <code>becomes:</code> (which is admittedly
unlikely these days) then you can use that when you run out of room.
<p>
Kawa 2.0 implements the functionality of this SRFI.
<h1>Copyright</h1>
<p>
Copyright (C) Per Bothner 2015</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 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>
<hr>
<address>Author: <a href="mailto:per@bothner.com">Per Bothner</a></address>
<address>Editor: <a href="mailto:srfi-editors at srfi dot schemers dot org">Michael Sperber</a></address>
</body>
</html>