wip

2 files changed, 53 insertions, 171 deletions

diff --git a/srfi-225.html b/srfi-225.html
index bc4de96..674af54 100644
--- a/srfi-225.html
+++ b/srfi-225.html
@@ -54,8 +54,7 @@ same key, which makes them atypical instances of persistent dictionaries.</p>
   provided that a <em>dictionary type object</em> (DTO) is available for it:
   either exported from this SRFI, or from other SRFIs or libraries, or created by the user.
   DTOs are of an unspecified type.</p>
-<p>This in turn requires that the DTO provides at least a predicate that can recognize its dictionaries
-  and several primitive generic procedures.</p>
+<h2 id="specification">Specification</h2>
 <p>By using the procedures of this SRFI, a procedure can take a DTO and a dictionary as arguments
   and make flexible use of the dictionary without knowing its exact type.
   For the purposes of this SRFI, such a procedure is called a <em>generic procedure</em>.
@@ -63,9 +62,19 @@ same key, which makes them atypical instances of persistent dictionaries.</p>
   A pure dictionary type either exposes pure functional update operations or no update operations at all,
   whereas an impure dictionary type exposes mutation operations.
   Note that if an instance of an impure dictionary type like SRFI 126 is in fact immutable, it still counts as impure.
-<p>In addition, there are constructors and the predicate <code>dict-pure?</code>,
-which require only a <em>dto</em> argument.</p>
-<h2 id="specification">Specification</h2>
+The generic predicate <code>dto-pure?</code>
+can be used to distinguish the two types.</p>
+<p>Note that there are no generic constructors:
+dictionaries need to be constructed by type-specific procedures.
+Consequently, there are no <code>make-dict</code>,
+<code>dict</code>, or <code>dict-unfold</code> generic procedures.
+It is just as convenient to call <code>make-hash-table</code>,
+for instance, as to call a <code>make-dict</code> procedure
+and pass it <code>hash-table-dto</code> as an argument.
+It is the procedure that constructs a dictionary that knows
+which type of dictionary is needed, rather than the caller
+of that procedure.</p>
+<h3 id="definitions">Definitions</h3>
 <p>We call a specific key-value combination an <em>association</em>.
   (This is why an alist, or association list, is called that; it is a list of associations represented as pairs.)</p>
 <p>A <em>dictionary</em> or <em>dict</em> is a collection of associations which may or may not be inherently ordered by their keys.
@@ -77,11 +86,11 @@ which require only a <em>dto</em> argument.</p>
   Two dictionaries are <em>similar</em> if they have the same DTO
   and have the same equality predicate and the same ordering predicate and/or hash function.</p>
 <h3 id="notations">Notations</h3>
-<p>JSON notation is used to represent a dictionary of an unspecified
-type in this SRFI: thus <code>{1:2, 3:4, 5:6}</code> represents a dictionary with
+<p>JSON notation is used in this SRFI to represent a dictionary of an unspecified
+type: thus <code>{1:2, 3:4, 5:6}</code> represents a dictionary with
 three associations.
 However, the appearance of JSON notation in the examples of this SRFI
-is purely abstract and does not mean that it can be used in actual code
+is purely conventional and does not mean that it can be used in actual code
 to represent a dictionary.</p>
 
 <p>Each of the following examples is assumed to be prefixed by the following definitions:</p>
@@ -112,6 +121,16 @@ Consequently, previous examples don't affect later ones.
 <blockquote><pre>
 (dict=? dto = dict {5:6, 3:4, 1:2})> #t
 (dict=? dto = dict {1:2, 3:5}) => #f</pre></blockquote>
+<p><code>(dict-pure?</code>&nbsp;<em>dto dict</em><code>)</code></p>
+<p>Returns <code>#t</code> if <em>dto</em> describes pure dictionaries.
+A pure dictionary either does not support updates at all,
+or else updates are persistent so that a new dictionary is
+returned by an update that can share storage with the original
+dictionary but is distinct from it.  Impure dictionaries,
+on the other hand, perform updates by mutation.  SRFI 146
+mappings are pure dictionaries; SRFI 125 hash tables are impure.
+The <em>dict</em> argument is required for the sake of uniformity
+with other generic procedures, but it can have any value.</p>
 <h3 id="lookup-procedures">Lookup procedures</h3>
 <p><code>(dict-ref</code>&nbsp;<em>dto dict key</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p>
 <p>If <em>key</em> is the same as some key of <em>dict</em>, then invokes <em>success</em>
@@ -128,16 +147,11 @@ Consequently, previous examples don't affect later ones.
 <blockquote><pre>(dict-ref/default dto dict 1 #f) =&gt; 1
 (dict-ref/default dto dict 1 #f) =&gt; #f</pre></blockquote>
 <h3 id="update-procedures">Update procedures</h3>
-<p>All update procedures exist in pairs, with and without a final <code>!</code>.
-  The descriptions apply to the procedures without <code>!</code>;
-  the procedures with <code>!</code> mutate their dictionary argument and do not return a dictionary value.
-  Only one set of procedures is supported by any dictionary type:
-  for example, SRFI 125 hash tables are impure and support only mutation,
-  whereas SRFI 146 mappings are pure and support only functional update.
-  The <code>dict-pure?</code> procedure can be used to determine which set is usable.</p>
+<p>Note that the following procedures apply to both pure and impure
+dictionaries (see <code>dict-pure?</code>: the <code>!</code>
+convention is not used in this SRFI.</p>
 <p>Updates are not permitted while any generic procedure is running that takes a procedure argument.</p>
 <p><code>(dict-set</code>&nbsp;<em>dto dict obj</em> …<code>)</code><br>
-<code>(dict-set!</code>&nbsp;<em>dto dict obj</em> …<code>)</code></p>
 <p>Returns a dictionary that contains all the associations of <em>dict</em>
   plus those specified by <em>objs</em>, which alternate between keys and values.
   If a key to be added already exists in <em>dict</em>, the new value prevails.</p>
@@ -146,17 +160,14 @@ Consequently, previous examples don't affect later ones.
 (dict-set dto dict 3 5) =&gt;
    {1:2, 3:5, 5:6})</pre></blockquote>
 <p><code>(dict-adjoin</code>&nbsp;<em>dto dict obj</em> ...<code>)</code><br>
-<code>(dict-adjoin!</code>&nbsp;<em>dto dict obj</em> ...<code>)</code></p>
 <p>Returns a dictionary that contains all the associations of <em>dict</em>
   plus those specified by <em>objs</em>, which alternate between keys and values.
   If a key to be added already exists in <em>dict</em>, the old value prevails.</p>
-<blockquote><pre>; new values are prepended to alists
-(dict-adjoin dto dict 7 8) =&gt;
-  ((7 . 8) (1 . 2) (3 . 4) (5 . 6))
+<blockquote><pre> (dict-adjoin dto dict 7 8) =&gt;
+  {1:2, 3:4, 5:6, 7:8}
 (dict-adjoin dto dict 3 5) =&gt;
-  ((1 . 2) (3 . 4) (5 . 6))</pre></blockquote>
-<p><code>(dict-delete</code>&nbsp;<em>dto dict key</em> …<code>)</code><br>
-<code>(dict-delete!</code>&nbsp;<em>dto dict key</em> …<code>)</code></p>
+  {1:2, 3:4, 5:6}</pre></blockquote>
+<p><code>(dict-delete</code>&nbsp;<em>dto dict key</em> …<code>)</code></p>
 <p>Returns a dictionary that contains all the associations of <em>dict</em>
   except those whose keys are the same as one of the <em>keys</em>.
 <blockquote><pre>; new values are prepended
@@ -164,12 +175,10 @@ Consequently, previous examples don't affect later ones.
   {5:6}
 (dict-delete dto dict 5) =&gt;
   {1:2, 3:4}</pre></blockquote>
-<p><code>(dict-delete-all</code>&nbsp;<em>dto dict keylist</em><code>)</code><br>
-<code>(dict-delete-all!</code>&nbsp;<em>dto dict keylist</em><code>)</code></p>
+<p><code>(dict-delete-all</code>&nbsp;<em>dto dict keylist</em><code>)</code></p>
 <p>The same as <code>dict-delete</code>, except that the keys to be deleted are in the list <em>keylist</em>.</p>
 <blockquote><pre>(dict-delete-all dto dict '(1 3)) =&gt; {5:6}</pre></blockquote>
-<p><code>(dict-replace</code>&nbsp;<em>dto dict key value</em><code>)</code><br>
-<code>(dict-replace!</code>&nbsp;<em>dto dict key value</em><code>)</code></p>
+<p><code>(dict-replace</code>&nbsp;<em>dto dict key value</em><code>)</code></p>
 <p>Returns a dictionary that contains all the associations of <em>dict</em> except as follows:
 If <em>key</em> is the same as a key of <em>dict</em>,
   then the association for that key is omitted and replaced by the association
@@ -177,8 +186,7 @@ If <em>key</em> is the same as a key of <em>dict</em>,
 If there is no such key in <em>dict</em>, then dictionary is returned unchanged.</p>
 <blockquote><pre>(dict-replace dto dict 1 3) =&gt;
   {1:3, 3:4, 5:6}} </pre></blockquote>
-<p><code>(dict-intern</code>&nbsp;<em>dto dict key failure</em>)<br>
-<code>(dict-intern!</code>&nbsp;<em>dto dict key failure</em>)</p>
+<p><code>(dict-intern</code>&nbsp;<em>dto dict key failure</em>)</p>
 <p>If there is a key in <em>dict</em> that is the same as <em>key</em>, returns two values,
   <em>dict</em> and the value associated with <em>key</em>.
 Otherwise, returns two values, a dictionary that contains
@@ -190,8 +198,7 @@ Otherwise, returns two values, a dictionary that contains
 (dict-intern dto dict 2 (lambda () 10)) =&gt; ; 2 values
   {1:2, 2:10, 3:4, 5:6}
   #f</pre></blockquote>
-<p><code>(dict-update</code>&nbsp;<em>dto dict key updater</em> [<em>failure</em> [<em>success</em>] ]<code>)</code><br>
-<code>(dict-update!</code>&nbsp;<em>dto dict key updater</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p>
+<p><code>(dict-update</code>&nbsp;<em>dto dict key updater</em> [<em>failure</em> [<em>success</em>] ]<code>)</code></p>
 <p>Retrieves the value of <em>key</em> as if by <code>dict-ref</code>, invokes <em>updater</em> on it, and sets the value of <em>key</em> to be the result of calling <em>updater</em> as if by <code>dict-set</code>, but may do so more efficiently. Returns the updated dictionary. The default value of <em>failure</em> signals an error; the default value of <em>success</em> is the identity procedure.</p>
 <blockquote><pre>
 (dict-update dto dict 1 (lambda (x) (+ 1 x))) =&gt;
@@ -199,8 +206,7 @@ Otherwise, returns two values, a dictionary that contains
 (dict-update dto dict 2 (lambda (x) (+ 1 x))) =&gt;
   <em>error</em>
 </pre></blockquote>
-<p><code>(dict-update/default</code>&nbsp;<em>dto dict key updater default</em><code>)</code><br>
-<code>(dict-update/default!</code>&nbsp;<em>dto dict key updater default</em><code>)</code></p>
+<p><code>(dict-update/default</code>&nbsp;<em>dto dict key updater default</em><code>)</code></p>
 <p>Retrieves the value of <em>key</em> as if by <code>dict-ref/default</code>, invokes <em>updater</em> on it,
   and sets the value of <em>key</em> to be the result of calling <em>updater</em> as if by <code>dict-set</code>,
   but may do so more efficiently. Returns the updated dictionary.</p>
@@ -212,8 +218,7 @@ Otherwise, returns two values, a dictionary that contains
   (lambda (x) (+ 1 x)) 0) =&gt;
   {1:0, 3:4, 5:6}
 </pre></blockquote>
-<p><code>(dict-pop</code>&nbsp;<em>dto dict</em><code>)</code><br>
-<code>(dict-pop!</code>&nbsp;<em>dto dict</em><code>)</code></p>
+<p><code>(dict-pop</code>&nbsp;<em>dto dict</em><code>)</code></p>
 <p>Chooses an association from <em>dict</em> and returns three values:
   a dictionary that contains all associations of <em>dict</em> except the chosen one,
   the key, and the value of the association chosen.
@@ -224,16 +229,13 @@ Otherwise, returns two values, a dictionary that contains
   {3:4, 5:6}
   1
   2</pre></blockquote>
-<p><code>(dict-map</code>&nbsp;<em>dto proc dict</em><code>)</code><br>
-<code>(dict-map!</code>&nbsp;<em>dto proc dict</em><code>)</code></p>
+<p><code>(dict-map</code>&nbsp;<em>dto proc dict</em><code>)</code></p>
 <p>Returns a dictionary similar to <em>dict</em> that maps each  of <em>dict</em>
   to the result of applying <em>proc</em> to the key and corresponding value of <em>dict</em>.</p>
 <blockquote><pre>(dict-map (lambda (k v) (cons v k)) dto dict) =&gt;
-   ((2 . 1) (4 . 3) (6 . 5))</pre></blockquote>
-<p><code>(dict-filter</code>&nbsp;<em>dto pred dict</em><code>)</code><br>
-<code>(dict-filter!</code>&nbsp;<em>dto pred dict</em><code>)</code><br>
-<code>(dict-remove</code>&nbsp;<em>dto pred dict</em><code>)</code><br>
-<code>(dict-remove!</code>&nbsp;<em>dto pred dict</em><code>)</code></p>
+   {2:1, 4:3, 6:5}</pre></blockquote>
+<p><code>(dict-filter</code>&nbsp;<em>dto pred dict</em><code>)</code></p>
+<code>(dict-remove</code>&nbsp;<em>dto pred dict</em><code>)</code></p>
 <p>Returns a dictionary similar to <em>dict</em> that contains
   just the associations of <em>dict</em> that satisfy / do not satisfy <em>pred</em>
   when it is invoked on the key and value of the association.</p>
@@ -241,8 +243,7 @@ Otherwise, returns two values, a dictionary that contains
   {1:2}
 (dict-remove (lambda (k) (= k 1)) dto dict) =&gt;
   {3:4, 5:6}</pre></blockquote>
-<p><code>(dict-find-update</code>&nbsp;<em>dto dict key failure success</em><code>)</code><br>
-<code>(dict-find-update!</code>&nbsp;<em>dto dict key failure success</em><code>)</code></p>
+<p><code>(dict-find-update</code>&nbsp;<em>dto dict key failure success</em><code>)</code></p>
 <p>This procedure is a workhorse for dictionary lookup, insert, and delete.
   The dictionary <em>dict</em> is searched for an association whose key is the same as <em>key</em>.
   If one is not found, then the <em>failure</em> procedure is tail-called with two procedure arguments,
@@ -265,45 +266,6 @@ sense of the dictionary’s equality predicate.</p></li>
 <li><p>Invoking <code>(</code><em>delete</em><code>)</code> returns a dictionary that contains all the associations of <em>dict</em>, except for the association with
 key <em>key</em>.
 </ul>
-<p>Here are four examples of <code>dict-find-update</code>,
-one for each of the four procedures:
-<blockquote><pre>
-     ;; ignore
-     (define-values
-       (dict value)
-       (dict-find-update {a:b} 'c
-              (lambda (insert ignore)
-                (ignore))
-              (lambda args
-                (error))))) => {a:b}
-
-     ;; insert
-     (define-values
-       (dict value)
-       (dict-find-update {a:b} 'c
-              (lambda (insert ignore)
-                (insert 'd))
-              (lambda args
-                (error))))) => {a:b, c:d}
-
-     ;; update
-     (define-values
-       (dict value)
-       (dict-find-update {a:b} 'a
-              (lambda args
-                (error))
-              (lambda (key value update delete)
-                (update 'a2 'b2))))) => {a2:b2}
-
-     ;; delete
-     (define-values
-       (dict value)
-       (dict-find-update {a:b, c:d} 'a
-              (lambda args
-                (error))
-              (lambda (key value update delete)
-                (delete))))) => {c:d}
-</pre></blockquote>
 <h3 id="the-whole-dictionary">The whole dictionary</h3>
 <p><code>(dict-size</code>&nbsp;<em>dto dict</em><code>)</code></p>
 <p>Returns an exact integer representing the number of associations in <em>dict</em>.</p>
@@ -364,6 +326,10 @@ one for each of the four procedures:
 </pre></blockquote>
 <p><code>(dict-&gt;alist</code>&nbsp;<em>dto dict</em><code>)</code></p>
 <p>Returns an alist whose keys and values are the keys and values of <em>dict</em>.</p>
+<blockquote><pre>
+(dict-&gt;alist dto dict) =&gt;
+  {1:2, 3:4, 5:6}
+</pre></blockquote>
 <p><code>(dict-comparator</code>&nbsp;<em>dto dict</em><code>)</code></p>
 <p>Return a comparator representing the type predicate, equality predicate,
   ordering predicate, and hash function of <em>dict</em>.
@@ -422,7 +388,7 @@ one for each of the four procedures:
 <p>There are additional proc-id variables that may be provided with corresponding procedures
   in order to increase efficiency.
   For example, it is not necessary to provide a <code>dict-ref</code> procedure,
-  because the default version is built on top of <code>dict-find-update</code> or <code>dict-find-update!</code>.
+  because the default version is built on top of <code>dict-find-update</code>.
   But if the underlying dictionary provides its own <code>-ref</code> procedure,
   it may be more efficient to specify it to <code>make-dto</code> using <code>dict-ref-id</code>.
   Here is the list of additional proc-id variables:</p>
@@ -477,10 +443,8 @@ and <code>#f</code> otherwise.
 <h3 id="exported-dtos">Exported DTOs</h3>
 <p>The following DTOs are exported from this SRFI:
 <code>srfi-69-dto</code>, <code>hash-table-dto</code>, <code>srfi-126-dto</code>,
-<code>mapping-dto</code>, <code>hash-mapping-dto</code>,
-<code>alist-eqv-dto</code>, and <code>alist-equal-dto</code>.
-The last two provide DTOs for alists using <code>eqv?</code>
-and <code>equal?</code> respectively.</p>
+<code>mapping-dto</code>, and <code>hash-mapping-dto</code>,
+provided that the corresponding libraries are available.</p>
 <h2 id="implementation">Implementation</h2>
 
 <p>The sample implementation is found in the <a href="https://github.com/scheme-requests-for-implementation/srfi-225">GitHub repository</a>.</p>
@@ -502,7 +466,7 @@ new dictionary types that may not have complete dictionary APIs:</p>
 
     <dt>dict-ref</dt>
     <dd>dict-pure?</dd>
-    <dd>dict-find-update or dict-find-update!</dd>
+    <dd>dict-find-update</dd>
 
     <dt>dict-ref/default</dt>
     <dd>dict-ref</dd>
diff --git a/srfi/alist-impl.scm b/srfi/alist-impl.scm
deleted file mode 100644
index 80b449d..0000000
--- a/srfi/alist-impl.scm
+++ /dev/null
@@ -1,82 +0,0 @@
-(define (make-alist-dto key=)
-
-  (define (alist? dto l)
-    (and (list? l)
-         (or (null? l)
-             (pair? (car l)))))
-
-  (define (alist-pure? dto alist)
-    #t)
-
-  (define (alist-map dto proc alist)
-    (map
-     (lambda (e)
-       (define key (car e))
-       (define value (cdr e))
-       (cons key (proc key value)))
-     alist))
-
-  (define (alist-filter dto pred alist)
-    (filter
-     (lambda (e)
-       (pred (car e) (cdr e)))
-     alist))
-
-  (define (alist-delete dto key alist)
-    (filter
-     (lambda (entry)
-       (not (key= (car entry) key)))
-     alist))
-
-  (define (alist-find-update dto alist key failure success)
-    (define (handle-success pair)
-      (define old-key (car pair))
-      (define old-value (cdr pair))
-      (define (update new-key new-value)
-        (cond
-         ((and (eq? old-key
-                    new-key)
-               (eq? old-value
-                    new-value))
-          alist)
-         (else
-          (let ((new-list
-                 (alist-cons
-                  new-key new-value
-                  (alist-delete dto old-key alist))))
-            new-list))))
-      (define (remove)
-        (alist-delete dto old-key alist))
-      (success old-key old-value update remove))
-
-    (define (handle-failure)
-      (define (insert value)
-        (alist-cons key value alist))
-      (define (ignore)
-        alist)
-      (failure insert ignore))
-    (cond
-     ((assoc key alist key=) => handle-success)
-     (else (handle-failure))))
-
-  (define (alist-size dto alist)
-    (length alist))
-
-  (define (alist->alist dto alist)
-    alist)
-
-  (define (alist-comparator dto dictionary)
-    #f)
-
-  (make-dto
-   dictionary?-id alist?
-   dict-pure?-id alist-pure?
-   dict-map-id alist-map
-   dict-filter-id alist-filter
-   dict-find-update-id alist-find-update
-   dict-size-id alist-size
-   dict->alist-id alist->alist
-   dict-comparator-id alist-comparator))
-
-(define alist-eqv-dto (make-alist-dto eqv?))
-(define alist-equal-dto (make-alist-dto equal?))