[racket-dev] Generics updates

From: Sam Tobin-Hochstadt (samth at cs.indiana.edu)
Date: Wed Oct 2 16:53:39 EDT 2013

On Wed, Oct 2, 2013 at 4:44 PM, Jay McCarthy <jay.mccarthy at gmail.com> wrote:
> This is a good message, but I have one quibble.
>
> I think it makes sense to separate data immutability and logical
> immutability. For instance, I may have a library for querying REST
> services where a "server" object is represented by an immutable
> string. The string is immutable? but the service behind it is not. I
> don't want the happenstance of which data was used to construct the
> object to give the wrong idea of its mutability.

I think what you're saying here is that part of what we want from
immutability is knowing that doing the same thing again on the
immutable data won't change the behavior.  But of course, this is a
property of _both_ the data and the operation -- `file->bytes` takes
immutable input, but running it multiple times doesn't guarantee
anything. I'm not sure where this leaves us in terms of API design,
though.  In a capability-based language, or in a language like Clean,
`file->bytes` might take the filesystem as input, but that's not very
Rackety. :)

My inclination is that a dictionary implemented with immutable data
structures but representing the results of `getenv` shouldn't be
`immutable?`, whereas maybe one with mutable insides but a functional
interface should be, but that really depends on what we're trying to
say.

Sam

>
> Jay
>
> On Wed, Oct 2, 2013 at 2:41 PM, Sam Tobin-Hochstadt
> <samth at cs.indiana.edu> wrote:
>> 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
>>>
>
>
>
> --
> 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

Posted on the dev mailing list.