[racket-dev] Generics updates

From: Stephen Chang (stchang at ccs.neu.edu)
Date: Fri Aug 2 15:43:08 EDT 2013

Actually, I am realizing that every derived method depends on
set->stream, even the ones that don't document it (ie set-union,
set-union!, set-intersect, set-intersect!, etc), since they use
in-set.

I was in the process of creating a patch for the docs to add the
missing dependencies but I ran into an issue that I think warrants
discussion.

When the docs specifies dependencies for derived methods, there are
actually two kinds that are being conflated.

*** The first kind of dependency is stricter and requires the
programmer to explicitly implement the required methods, and fallbacks
do not count. In the code, this dependency is enforced with a call to
the #:defined-predicated supplied to define-generics.

Example:

set-copy says it depends on set-clear and set-add!.

Below is a set implementation that implements all the primitive
methods plus set->stream. There exist set-clear and set-add! functions
but set-clear is a fallback so set-copy wont work. Only if I
explicitly implement set-clear will I get set-copy.

(struct lstset (lst)
  #:transparent
  #:methods gen:set
  [(define (set-member? s x) (match s [(lstset lst) (member x lst)]))
   (define (set-add s x)
     (match s
       [(lstset lst)
        (lstset (cons x (filter (λ (y) (not (equal? y x))) lst)))]))
   (define (set-remove s x) (match s [(lstset lst) (lstset (remove x lst))]))
   (define (set-add! s x) (void))
   (define (set-remove! s x) (void))
   (define (set->stream s) (lstset-lst s))])

> (set-add (lstset '(1 2)) 4)
(lstset '(4 1 2))
> (set-clear (lstset '(1 2)))
(lstset '())
> (set-copy (lstset '(1 2 3)))
. . set-copy: not implemented for (lstset '(1 2 3))



*** The second kind of dependency is looser and allows fallbacks. For
example set-count requires set->stream, but if I implement in-set,
that is good enough.


I guess my question is, is this a docs issue, or should the code have
more calls to set-implements?



On Fri, Aug 2, 2013 at 1:47 PM, Stephen Chang <stchang at ccs.neu.edu> wrote:
>> With that in mind, I think it would make sense to move `set-first' and
>> `set-empty?' to the primitive set (making it clear that they are
>> optional, and can be derived from `set->stream' if need be). With those
>> two in the primitive set, anything that implements all the primitives
>> should get all the derived for free, right?
>
> Oh yeah, I like that better than moving set->stream to primitives
> since they are more "standard" set operations.
>
> Carl, I dont see how guaranteeing some fallback implementations
> affects allowing more efficient versions. I think most programmers
> understand that the default implementation is probably not very
> efficient.
>
>
>
>
>
>
>>
>> Vincent


Posted on the dev mailing list.