[racket-dev] Generics and data structures

From: Ryan Culpepper (ryan at cs.utah.edu)
Date: Wed May 9 20:02:04 EDT 2012

On 05/09/2012 04:13 PM, Asumu Takikawa wrote:
> Hi all,
> Racket currently provides several generic extensible data structure APIs
> such as dictionaries, sequences, streams, and so on. Unfortunately, each
> data structure currently has its own extension API, but no consistent
> convention exists: some APIs use lists of methods, some use vectors,
> etc.  Furthermore, these APIs are usually rather low-level (e.g.,
> dependent on ordering in the method table).
> Vincent and I have been working on a unified user-friendly extension
> interface based on unstable/generics by Eli and Jay (which we have moved
> to collects/generics). We have a prototype that implements our proposed
> interface for prop:dict and prop:ordered-dict with complete backwards
> compatibility with their respective extension APIs. That is, we have
> modified racket/dict and data/ordered-dict to use generics.
> The code is on github here:
>    https://github.com/takikawa/racket/tree/generics
> We would like to get feedback on what we have so far and if nobody has
> any objections, we would like to push what we currently have to master.
> Ideally, we would provide similar interfaces for the other generic APIs
> in the tree, such as streams and sequences. However, the existing APIs
> rely on different representations for method tables from the one used by
> unstable/generics, specifically a vector of methods. This makes
> backwards compatibility complicated and we're not sure how to proceed.
> Some specific examples:
>    * `prop:sequence`: Instead of a vector of methods, this struct
>      property takes a procedure which takes a struct instance and
>      produces a sequence (not a vector of methods).
>    * `prop:equal+hash-code` uses a list of methods instead of a vector.
>    * `prop:dict/contract` is given both a method vector and a vector
>      of sub-contracts that are used to assemble the method contracts.
>      The generics library currently uses a single vector.
> To apply our proposal to these cases, we could change these struct
> properties to use the generics library's preferred representation.
> However, this would break backwards compatibility with code that
> currently uses these struct properties, which makes this a non-starter.
> Does anyone have any suggestions on how to proceed without breaking
> backwards compatibility?

See the 'supers' argument to 'make-struct-type-property'.

Create 'real-prop:sequence' that takes a vector (compatible with 
generics library).

Define 'prop:sequence' as a backwards compatibility property that takes 
an old-style implementation and transforms it into the new-style 
implementation vector. 'prop:dict/contract' plays the same trick, IIRC.


> Streams present a slightly different issue. `prop:stream` already
> represents its methods with a vector. However, it is used heavily in the
> implementation of racket/base, so we cannot re-write it to use generics
> (which depends on racket/base).
> Assuming we can't restructure racket/private/for to break the circular
> dependency, another solution would be to allow the generics library to
> create a generic interface attached to an existing struct property[1],
> given the struct property accessor.  That would require exposing the
> struct property accessor from the internals of racket/base.  Would that
> be an acceptable solution?
> [1]: currently, the generics library needs to be the one defining
>       the struct property.
> Any thoughts or suggestions?
> Cheers,
> Asumu&  Vincent
> _________________________
>    Racket Developers list:
>    http://lists.racket-lang.org/dev

Posted on the dev mailing list.