Am Do., 29. Juli 2021 um 23:51 Uhr schrieb John Cowan <xxxxxx@ccil.org>:

On Wed, Jul 28, 2021 at 2:19 AM Marc Nieper-Wißkirchen <xxxxxx@nieper-wisskirchen.de> wrote:

To be able to be used in generically polymorphic code, `make-dict' should be implementation-agnostic, but it isn't in the current form.

So make-dict would accept only a DTD?

Yes. Or any arguments should be key/value pairs to populate the newly created dictionary.

When the SRFI talks about "initial capacity", etc. in the second paragraph of the entry to `make-dict', it is obvious. Moreover, any `comparator' does not make sense with any DTD. For example, a given dictionary type represented by the DTD may only support a single equality predicate.

Quite so, although it is certainly proper to signal a dictionary-error if the comparator contains an incompatible value. But I don't yet understand what you are proposing as the alternative.

The alternative is that a dict-type specific `make-dtd' procedure accepts all these implementation-dependent parameters (and stores them in the DTD).

Or, when using this SRFI in R6RS code, `make-dict' cannot be supported by its native hashtables (because to know whether an "eq-" or "eqv-hashtable" has to be created, one has to check the equality predicate in the comparator but the result of procedure comparison in R6RS is unspecified.

In principle, yes. But I have found that when dealing with top-level procedures (with empty closures), the R[57]RS rules apply in all known R6RS implementations: (eq? car car) => #t and (eq? car cdr) => #f.

The reasoning behind the approach R6RSs takes is that procedures should be fully equivalent under eta-conversion.  (Will Clinger once explained this and gave a motivation for this.)  Even if current R6RS implementations give predictable results, this doesn't mean that they will do so in the future; if they have a source-level optimizer, the optimizer could be extended in a way to make use of unlimited eta-conversion.

Besides, given a primitive form `(%car <expr>)', which open-codes taking the car, an efficient definition of `car` in `(rnrs base (6))` could look like follows:

(define-syntax car

  (lambda (stx)

    (syntax-case stx ()

[id

       (identifier? #'id) 

       #'(lambda (pair) (%car pair))]

      [(_ expr)

       #'(%car expr)]

      [(_ expr* ...)

       #'(assertion-violation 'car "wrong number of arguments" expr* ...)]

[_

       #'(syntax-violation 'car "invalid application syntax" stx)])))

This is a reasonable definition of `car' but you would probably have that `(eq? car car)' evaluates to `#f'.

Anyway, by dropping the comparator argument from `make-dict', this problem is gone as well.

I am repeating myself but to solve this problem, remove the implementation-specific parameters (comparator, extra arguments) from `make-dict'. When a specific dictionary type needs specific parameters (like a comparator), give them when the DTD is constructed (which is necessarily non-generic).

Would these additional parameters be added to make-dtd? If so, how does make-dict get access to them? As an alist or plist? Or would the user write a different make-dict procedure for each combination of arguments they need?

A type-specific `make-XXX-dtd' takes these additional parameters and generates a suitable DTD.

For example:

(define make-hash-table-dtd

  (lambda (comparator . arg*)

    (define make-dict

      (lambda ()

        (apply make-hash-table comparator arg*)))

    (define dict-size

      (lambda (ht)

        (hash-table-size ht)))

...

    (make-dtd 

      'make-dict make-dict

      'dict-size? dict-size

      ...)))

Note: What's yet not clarified by the SRFI (or in case it actually is, I have overlooked it) is whether the methods to be provided take a DTD or not. On theoretical grounds, I'd say they shouldn't.

I think for this to work, we need an operation that returns a DTD from an existing DTD, with the ability to override individual procedures. Thus there might be a partial DTD for SRFI 125 with make-dict omitted, which would be usable as a template.

I don't think this would be necessary for the above approach.  In general, of course, it would a good addition to be able to derive specialized DTDs.

PS The explanation for `dictionary?' has to be updated.
PPS Something has gone wrong with the `dict-empty?' entry.

Fixed.
PPPS It is still missing that `dict-ref' calls SUCCESS and FAILURE in tail context.

As I said before, there is no way to guarantee this, because it depends on the underlying implementation.

Please see my earlier reply to this here: https://srfi-email.schemers.org/srfi-225/msg/17085937/

It's important to have this guarantee (and I'd like to repeat my suggestion to fix SRFI 125 with a PFN in any case) as the following example shows:

(define find-first-entry

  (lambda (ht n)

    (let f ((i 0))

      (if (= i n)

#f

          (hashtable-ref 

ht

i

           (lambda ()

             (f (+ i 1)))))))

(find-first-entry 1000000) should run in a bounded amount of (stack) space.