Actually, I agree that there’s a wide disparity between functional style type constructors and Avail’s types. But I look at it this way: There’s simply *no way* to implement unordered set-like constructs in the functional style, whereas Avail can have ordered or unordered set-like entities. The problem with trying to build unordered sets from type constructors is that, well, you can’t. The base equality (the one that matters) seems to be a recursive structural equality, which always makes the order matter even when you don’t want it to. You can’t subtract ordering distinction from types that expose it structurally, which functional style always does.
However, there might be a way to add primitive unordered maps and/or sets to
functional languages the same way that vectors are made directly available in
Scheme. For elements that have a natural, unambiguous order (reflexive,
antisymmetric, transitive), one could try the non-primitive solution of just
sorting the elements. But a sorted list or vector is far too slow to use this
way (except in Avail where you secretly have a BTree-balanced rope
implementation of tuples…). If instead you use a non-normalized search tree
(i.e., where the precise shape of the tree is intended not to matter, just the
order), the structural differences will make the structures appear unequal.
There’s probably a way around both issues (two occurrences of the same problem,
leakage of unessential representation), maybe by defining a special equality
operation of some sort… although I don’t see how default lazy semantics (like
in Haskell) could ever be made compatible with hiding structural representation
in this way. At the least, you’d probably have to distinguish finite and
infinite lists, perhaps through explicit annotations.
Avail can have a map whose keys are sets, like the type {set→any|}. You can
look up a particular set as a key in the map without having to know what order
the elements were “added” in the set constructor: {{2,1}→3, {1,2,3}→6}[{1,2}]
should produce 3. If the order mattered, you’d probably want something more
like {<2,1>→3, <1,2,3>→6}. There is middle ground, where you want (explicitly)
ordered elements without duplicates, but of course you’d have to have a
different set of semantics for deciding what order things should be kept in
when adding a key, replacing a key, removing a key, computing a union of
disjoint keys, computing a union where the keys overlap, computing a union
where the keys not only overlap but occur in a different order in the two
inputs, etc. All do-able... for certain types of elements. I won’t go into
more detail about tactics, however – let’s see what you come up with.
By the way, explicitly ordered keys in maps wouldn’t work very well inside
objects and object types. That’s why C++ object representation is so
incredibly messy in the presence of multiple inheritance. Accretion of fields
in one hierarchy allows you to just append a new field to the end of the
representation, but as soon as you have multiple superclasses… either the
compiler has to rip your representation apart and make a new copy of every
method at the junction class (not even possible in general because of the
linker's constraints), or stitch the fields together like Frankenstein’s
monster, intersperse multiple vtables, generate stub methods that adjust object
pointers, etc. Well at least they recognized that “diamond inheritance” was a
concern. Avail’s object mechanism automatically uses the diamond inheritance
pattern with maximum sharing – if you want separate has-a -like parts in the
supertype, just use a has-a relationship. The object types covary with the
types of the contained subobjects anyhow, so even Avail’s has-a is more
powerful than C++’s is-a. Oh, and any specific C++ compiler has to leak its
choice of representation, since classes are just structs and have to obey
(somewhat modified) struct layout rules.
Here’s something I noticed years after designing the object mechanism: Since
fields can be shared between objects, Avail’s object mechanism actually
subsumes /object inheritance/ (like Self’s parent fields).
Ok, have fun with it!
> On Jan 3, 2015, at 12:25 PM, Robbert van Dalen <[email protected]>
> wrote:
>
> thank you for taking your time discussing this.
>
>> Having read the indicated section at the link you provided (and the rest of
>> the page), it appears that Avail’s object types are a close fit for
>> implementing extensible records
>
> indeed, after reading your elaborate exposition of the avail object type
> system, it appears that they are a close fit.
> however, there is one snag: object fields have no natural ordering, whilst
> tuple fields obviously do (i could be wrong).
>
> while the notion of equality in avail is very well designed and first class,
> i believe that ordering (less than, greater than) is less developed.
> for instance, i would like to be able to order tuples (if they contain
> elements that can also be ordered). next to that, there are no primitive
> ordered sets or maps.
>
> one challenge i’d like to take on is whether it is possible to implement a
> generic avail library that can order almost everything out-of-the-box,
> without any boilerplate.
> note that in scala, (boilerplate free) generic ordering can be achieved via
> implicits; in haskell, via type classes.
>
> probably, you or todd can implement such library in a day or so.
> but please don’t. let me have a stab at it - in order for me to learn more
> about avail.
>
> cheers,
>
> - robbert
signature.asc
Description: Message signed with OpenPGP using GPGMail
