[racket-dev] Generics updates

On Wed, Oct 2, 2013 at 4:29 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> That sounds right.
>
> But just in case there is any confusion on the larger point: predicates as
> way we check properties to ensure good properties of our abstractions is one
> of the important things that we have mostly gotten right in Racket.
> Chaperones, separate pair? and mpair? predicates, and presumably lots of
> other stuff are the way they are for this kind of reason.

Unfortunately, this is only half-true, I think.  In particular, a very
large number of our data structures violate this rule: vectors,
strings, byte strings boxes, hash tables, dictionaries, sequences, and
so on, all provide the same operations on both mutable and immutable
variants.  This is also true in general of structs -- a substruct can
be mutable when the superstruct is immutable.

Ultimately, for the purpose of consistency, I think we should try to
decide what the 'Rackety' style for this is.  Should we follow the
lead of hash tables, where `immutable?` is needed to determine
anything?  Or should we follow the lead of pairs, where there's a
whole separate type?  And how should this interact with subtyping, as
in this discussion?

Personally, I think I prefer separate unrelated data structures, with
a generic interface [1].  Maybe this means we should make `immutable?`
into a generic.

[1] I think that part of the reason some of these are conflated is
lack of generic operations.

Sam

>
> Robby
>
>
> On Wed, Oct 2, 2013 at 3:21 PM, Jay McCarthy <jay.mccarthy at gmail.com> wrote:
>>
>> Even if we were to remove set-add! from gen:set and not great gen:mset
>> then that would not be a vaild property. Generics are a lower bound on
>> the interface, not an upper bound, so there could be other functions
>> on the data structure that implement mutation. For instance, a gen:set
>> could be made for an external resource that was set-like.
>>
>> I think what you want is something like gen:fset that has no methods,
>> but is used for set authors to tag their set as having this property
>> for the benefit of consumers (which cannot be enforced.) Your library
>> would then consume fsets and not sets.
>>
>> Jay
>>
>>
>> On Wed, Oct 2, 2013 at 2:09 PM, Robby Findler
>> <robby at eecs.northwestern.edu> wrote:
>> > If we do go this way, we should be careful about the subtyping
>> > relationship
>> > since we want a predicate that means "will not be mutated and I can rely
>> > on
>> > that to reason about my library's behavior" and if mutable sets are a
>> > sub-thing of immutable ones, we might lose that (depending on how things
>> > are
>> > set up).
>> >
>> > Robby
>> >
>> >
>> > On Wed, Oct 2, 2013 at 2:57 PM, Jay McCarthy <jay.mccarthy at gmail.com>
>> > wrote:
>> >>
>> >> No. Mutable sets would implement gen:set and then just have a few more
>> >> methods in the gen:mset interface. Structs can implement any number of
>> >> generics.
>> >>
>> >> Jay
>> >>
>> >> On Wed, Oct 2, 2013 at 1:31 PM, J. Ian Johnson <ianj at ccs.neu.edu>
>> >> wrote:
>> >> > This means I can't interchange between mutable and immutable sets for
>> >> > my
>> >> > functions that only need to read generic sets, unless we further
>> >> > subdivide
>> >> > and have gen:set-query gen:set-constructor gen:set-mconstruct.
>> >> >
>> >> > -Ian
>> >> > ----- Original Message -----
>> >> > From: "Jay McCarthy" <jay.mccarthy at gmail.com>
>> >> > To: "Carl Eastlund" <cce at ccs.neu.edu>
>> >> > Cc: "Racket Developers" <dev at racket-lang.org>
>> >> > Sent: Wednesday, October 2, 2013 3:23:07 PM GMT -05:00 US/Canada
>> >> > Eastern
>> >> > Subject: Re: [racket-dev] Generics updates
>> >> >
>> >> > Regarding a point from RacketCon, I don't like that gen:set includes
>> >> > functions like set-add! and set-remove!. I think that sets with
>> >> > mutations are subclass of get:set and we should have a separate
>> >> > gen:mset (or something) interface for mutable versions.
>> >> >
>> >> > I dislike that an obvious implementation of sets, hash tables, are
>> >> > not
>> >> > sets to gen:set, because there are operations that cannot be
>> >> > performed
>> >> > on them.
>> >> >
>> >> > I think that "X implements generic G" should imply "All functions of
>> >> > G
>> >> > work on X". But this is not the case with gen:set and hasheq sets,
>> >> > for
>> >> > instance.
>> >> >
>> >> > Jay
>> >> >
>> >> >
>> >> > On Tue, Jul 23, 2013 at 9:37 AM, Carl Eastlund <cce at ccs.neu.edu>
>> >> > wrote:
>> >> >> My work on adding gen:set, and related changes to define-generics
>> >> >> and
>> >> >> gen:dict, is ready for review and (hopefully) to push to the master
>> >> >> branch.
>> >> >> The branch moved in the process of cleaning things up, it's now at:
>> >> >>
>> >> >>   https://github.com/carl-eastlund/racket/tree/generics-from-scratch
>> >> >>
>> >> >> (The "from scratch" just refers to the process of rebuilding the git
>> >> >> history, I didn't go out of my way to rewrite anything in the code
>> >> >> base
>> >> >> from
>> >> >> scratch, although in some places a lot of code did move around.)
>> >> >>
>> >> >> What's new in the branch:
>> >> >>
>> >> >> - Generics now support a few new options
>> >> >>   - #:fallbacks specifies fallback method implementations for
>> >> >> instances
>> >> >> with
>> >> >> no implementation
>> >> >>   - #:fast-defaults specifies instances on a "fast path", useful for
>> >> >> built-in types
>> >> >>   - #:defined-predicate gives a more intuitive and efficient
>> >> >> interface
>> >> >> than
>> >> >> #:defined-table
>> >> >>   - #:derive-property allows generics to piggy-back on existing
>> >> >> struct
>> >> >> properties
>> >> >>
>> >> >> - Sets are now a generic datatype through gen:set
>> >> >>   - lists are now sets
>> >> >>   - the built-in set types are now documented as "hash sets"
>> >> >>   - there are mutable and weak hash sets
>> >> >>   - you can define new set types quickly with
>> >> >> define-custom-set-types
>> >> >>   - most set operations are now methods with fallbacks
>> >> >>   - sets now support -copy and -clear operations, plus mutating [!]
>> >> >> versions
>> >> >> of operations
>> >> >>
>> >> >> - Dictionaries have a few changes
>> >> >>   - new macro define-custom-hash-types [*]
>> >> >>   - most dict operations are now methods with fallbacks
>> >> >>   - dicts now support -copy, -clear, -clear!, and -empty? operations
>> >> >>
>> >> >> I've run some benchmarks and performance of the various generic
>> >> >> operations
>> >> >> are comparable to the current HEAD, so there should be no major
>> >> >> performance
>> >> >> changes with this patch.
>> >> >>
>> >> >> [*] I've added define-custom-hash-types and define-custom-set-types
>> >> >> rather
>> >> >> than just adding make-custom-set akin to make-custom-hash because
>> >> >> make-custom-hash is hard to use.  The documented behavior -- that
>> >> >> any
>> >> >> custom
>> >> >> hash is equal to any other created with the same bindings and
>> >> >> predicates /
>> >> >> hash functions -- was never true and can be expensive or at least
>> >> >> tricky to
>> >> >> implement.  It seemed more sensible to just remove the erroneous
>> >> >> documentation on make-custom-hash, and add the definition form to
>> >> >> create
>> >> >> constructors for new, explicitly-compatible dict and set types.
>> >> >> Both
>> >> >> definition forms bind predicates and constructors for new (set or
>> >> >> dict)
>> >> >> types with immutable, mutable, and weak variants that inter-operate.
>> >> >>
>> >> >> If there are no serious issues brought up in the next day or two,
>> >> >> I'll
>> >> >> push
>> >> >> it to the development branch, since our current release process
>> >> >> isn't
>> >> >> following HEAD.
>> >> >>
>> >> >> Carl Eastlund
>> >> >>
>> >> >> _________________________
>> >> >>   Racket Developers list:
>> >> >>   http://lists.racket-lang.org/dev
>> >> >>
>> >> >
>> >> >
>> >> >
>> >> > --
>> >> > Jay McCarthy <jay at cs.byu.edu>
>> >> > Assistant Professor / Brigham Young University
>> >> > http://faculty.cs.byu.edu/~jay
>> >> >
>> >> > "The glory of God is Intelligence" - D&C 93
>> >> > _________________________
>> >> >   Racket Developers list:
>> >> >   http://lists.racket-lang.org/dev
>> >>
>> >>
>> >>
>> >> --
>> >> Jay McCarthy <jay at cs.byu.edu>
>> >> Assistant Professor / Brigham Young University
>> >> http://faculty.cs.byu.edu/~jay
>> >>
>> >> "The glory of God is Intelligence" - D&C 93
>> >> _________________________
>> >>   Racket Developers list:
>> >>   http://lists.racket-lang.org/dev
>> >
>> >
>>
>>
>>
>> --
>> Jay McCarthy <jay at cs.byu.edu>
>> Assistant Professor / Brigham Young University
>> http://faculty.cs.byu.edu/~jay
>>
>> "The glory of God is Intelligence" - D&C 93
>
>
>
> _________________________
>   Racket Developers list:
>   http://lists.racket-lang.org/dev
>