enumeration bugs

[Michael D. Adams]

I believe these functions are non-conforming to the R6RS spec.

> (import (rnrs))
> (enum-set-universe (make-enumeration '(a b a)))
(a b a) ;; should return an object of type enum-set

> (enum-set->list (make-enumeration '(a b a)))
(a b a) ;; should remove duplicates (It's a set not a multi-set)

> (enum-set->list ((enum-set-constructor (make-enumeration '(a b a))) '(a b a)))
(a a b) ;; should remove duplicates

[Abdulaziz Ghuloum (aghuloum)]

On May 5, 2008, at 5:13 PM, Michael D. Adams wrote:
> Public bug reported:
>
> I believe these functions are non-conforming to the R6RS spec.
>
>> (import (rnrs))
>> (enum-set-universe (make-enumeration '(a b a)))
> (a b a) ;; should return an object of type enum-set

Yes, but the type enum-set is not defined (there is no enum-set?
predicate), and it does not have to be disjoint from other types. It
is possible that I missed a detail somewhere. Pointer?

>> (enum-set->list (make-enumeration '(a b a)))
> (a b a) ;; should remove duplicates (It's a set not a multi-set)

Who should remove the duplicates? make-enumeration or enum-set-
 >list? Enumerations are ordered, right? Which "a" should be
removed, the first or the last? Is that specified anywhere?

Maybe it's an error to pass make-enumeration a list of symbols with
duplicates, but I do not see that in the specification of make-
enumeration (all it says is that the argument must be a *list* of
symbols).

In all honesty, I don't understand the purpose of this library, never
used it for anything, and do not see it useful for anything. Maybe
if I understand it better, I could see how it should be implemented
and what reasonable constraints are implicitly there, maybe then I
can do a better job with it. So, do you have a good use/explanation
of this library beyond what's in the 1 page of the spec?

Aziz,,,

[Michael D. Adams (mdmkolbe)]

>>> (import (rnrs))
>>> (enum-set-universe (make-enumeration '(a b a)))
>> (a b a) ;; should return an object of type enum-set

>Yes, but the type enum-set is not defined (there is no enum-set?
>predicate), and it does not have to be disjoint from other types. It
> is possible that I missed a detail somewhere. Pointer?

True, but the enum-set type must support the enum-set operators. Examples

> (enum-set-universe (enum-set-universe (make-enumeration '(a b a))))
Unhandled exception
 Condition components:
   1. &assertion
   2. &who: enum-set-universe
   3. &message: "not an enumeration"
   4. &irritants: ((a b a))
> (enum-set-complement (enum-set-universe (make-enumeration '(a b a))))
Unhandled exception
 Condition components:
   1. &assertion
   2. &who: enum-set-complement
   3. &message: "not an enumeration"
   4. &irritants: ((a b a))

>>> (enum-set->list (make-enumeration '(a b a)))
>> (a b a) ;; should remove duplicates (It's a set not a multi-set)

> Who should remove the duplicates? make-enumeration or enum-set->list?
> Enumerations are ordered, right? Which "a" should be removed, the first or the last? Is that specified anywhere?

Under the heading for "make-enumeration" R6RS-libs says "The make-enumeration procedure creates a new enumeration type whose universe consists of those symbols (in canonical order of their first appearance in the list)". So it is in order of the first appearance.

I completely agree with you that the enumeration library is rather strangely defined. (I'm dealing with them because implementing them for the summer job.) The best intuition that I can come up with is that enumerations are:
  (1) finite sets that
  (2) are restricted to symbols (an arbitrary restriction in my mind) and
  (3) that have a universe set attached to them (the universe specifies an order for reification to lists and is used for enum-set-complement).

I have no clue as to what their use would be. They are too weak to be used like "Haskell enumerations" (i.e. they provide no benefit for argument checking because there is no enum-type-compare function thus a list of symbols might be just as good) while also being too restricted to be used like general purpose sets (i.e. they only work on symbols). Conceivably a good enum-set implementation could improve some of the asymptotic performance, but then again how often do you really need a "set" of symbols large enough for the asymptote to matter?

[Abdulaziz Ghuloum (aghuloum)]

On May 5, 2008, at 10:40 PM, Michael D. Adams wrote:
>>>> (import (rnrs))
>>>> (enum-set-universe (make-enumeration '(a b a)))
>>> (a b a) ;; should return an object of type enum-set
>
>> Yes, but the type enum-set is not defined (there is no enum-set?
>> predicate), and it does not have to be disjoint from other types. It
>> is possible that I missed a detail somewhere. Pointer?
>
> True, but the enum-set type must support the enum-set operators.

Duuh. I think I implemented this based on some non-final draft of
R6RS. Will fix.

> Examples [...]

>>>> (enum-set->list (make-enumeration '(a b a)))
>>> (a b a) ;; should remove duplicates (It's a set not a multi-set)
>
>> Who should remove the duplicates? make-enumeration or enum-set->list?
>> Enumerations are ordered, right? Which "a" should be removed, the
>> first or the last? Is that specified anywhere?
>
> Under the heading for "make-enumeration" R6RS-libs says "The make-
> enumeration procedure creates a new enumeration type whose universe
> consists of those symbols (in canonical order of their first
> appearance
> in the list)". So it is in order of the first appearance.

Cool. Thanks. Must've missed that.

> I completely agree with you that the enumeration library is rather
> strangely defined. (I'm dealing with them because implementing
> them for the summer job.)

You can take it from Ikarus if it's good enough for your purpose.

> The best intuition that I can come up with is that enumerations are:
> (1) finite sets that
> (2) are restricted to symbols (an arbitrary restriction in my
> mind) and
> (3) that have a universe set attached to them (the universe
> specifies an order for reification to lists and is used for enum-
> set-complement).

I think they also have types so that every call to "make-enumeration"
returns a unique type of universe, so that you can do "enum-set-
projection" from one universe to another. (whatever that's useful for)

> I have no clue as to what their use would be.

Great :-)

> Conceivably a good enum-set implementation could improve some of the
> asymptotic performance, but then again how often do you really need a
> "set" of symbols large enough for the asymptote to matter?

I haven't seen anybody who uses them, let alone in performance
critical code. There's bigger fish to fry than optimizing this
library (IMHO).

Aziz,,,

[Abdulaziz Ghuloum (aghuloum)]

Fixed in 1470. Thanks. Let me know if you run across any other bugs.