Add Multiset Support

[Rickasaurus]

Rationale

Sets are great, but they can't account for many recent use cases we've been seeing with Barb where the number of each element must be tracked. For this reason we've been discussing internally at Bayard Rock adding Multiset support.

Considerations

Once upon a time Barb was not in heavy use at my company. Many features of Barb were tweaked to allow Set operations to work fluidly with other types for convenience. In this end this has come back to bite us somewhat as we must be very careful in our implementation of Multisets if we want to ensure backwards compatibility.

1 -- Arrays are automatically converted to sets when passed to the set operators, and changed back afterward.

This is perhaps worse than it seems on the surface. Most of our internal Barb usage leans heavily on the array syntax [| .. |] to define sets. Additionally, the most common collections from the program-internal records we access are arrays, leaving us with many cases in the form of array1 /\ array2. For backwards compatibility these must still act as set operations for now. This may be revisited in a future major release of Barb.

2 -- Singular elements are lifted to sets when passed to a set operator, and then changed back afterward.

For example, array1 /\ 1 would find the intersection of the element 1 with the array, which is either 1 or the empty set. This is most commonly used in the form array1 /?\ "somestring" as we work heavily with strings and often want to see if a string exists in some array.

3 -- Type selection with set operations are defined by reflective lookup in the set operation functions.

This isn't so bad, as these are easily extended. However, there is currently no way to define how an external .NET type will interact with Sets and Multisets.

4 -- Infinite predicate-based Sets and Multisets would be very useful to have.

These would sets defined in terms of an inclusion predicate in the form of (obj -> bool). It seems possible to define these for all operations, but they would need to fail on error if an attempt is made to realize one by returning it to .NET.

Implementation Options

1 -- Make all Multisets explicit, with up-conversions of Sets when interacting with Multisets.

This would put the onus on the set operation functions. The challenge here is carefully defining the interactions of arrays, multisets, and sets for each operation.

2 -- Define a separate set of operators for Multisets

I really don't like this, as it will explode our operator list, but it might be the easiest way to move forward as we could consider the interactions of each type separately.

Affected Areas

Assuming option #1 above, the following set operation functions in Interop.fs would need to be changed to be well defined for multi-sets:

\/ - unionObjects
/\ - intersectObjects
/?\ - doObjectsIntersect
(= - isSubsetOf
=) - isSupersetOf
-) - leftDifference
(- - rightDifference
-- - symmetricDifference
* -- Additionally we need to add the scalar product with mutlisets.

The parser and interpreter would also need to be modified for Multiset specific cases.

Syntax

We have settled at least on using {{ ... }} to define the context of a multiset, although there is some room for argument.

Considerations

1 -- We need to be able to explicitly convert .NET types to discrete Multisets.

For this we are considering a projection operator similar to a list comprehension of the form:
``{{ x : X -> x }}wherex` is the bound out element, and `X` is the .NET collection type.

2 -- We would like to be able to implicitly convert .NET types from Multisets.

This can be pushed off an expanded on in the future but for now a Multiset of the form {{ 'a': 2; 'b': '1 }} should turn into an array of the form [| 'a'; 'a'; 'b' |].

3 -- We need to be able to define discrete non-infinite multisets.

These could either take the form of {{ 'a': 2; 'b': '1 }} or {{ 'a'; 'a'; 'b' }}.

4 -- We would like to be able to define infinite multisets.

These could take the form of an inclusion predicate `{{ fun x -> ... }}``.