Re: [Cbor] A CBOR tag for alternatives/unions, request for comments

[Michael Peyton Jones <[e-mail]>]

I don't think we have any data on how common different number of
alternatives are, but we do have a large amount of experience writing code
in functional programming languages, which are one of the target use cases
for these tags.

The argument for going up to 8 alternatives in the most compact range is
simple:
- As computer scientists, we like to round things to powers of 2 :)
- Data types with more than 4 alternatives are common, so that is fewer
than we would like.
- Data types with more than 8 alternatives are rare.

Ergo: 8 should be enough for most purposes.

The argument for the second range is perhaps less clear. I could see the
argument for not including it at all. However, since the tag space is
comparatively more plentiful, it seemed cheap to use a modest amount of
them for this purpose. Again, the argument for the number of tags is from
experience: data types with more than 100 alternatives are *vanishingly*
rare, and likely machine-generated if they exist at all.

Best wishes,
Michael

On Thu, 24 Feb 2022 at 00:06, Carsten Bormann <[e-mail]> wrote:

> On 2022-02-24, at 00:30, Michael Richardson <[e-mail]> wrote:
> >
> >
> > {why haven't we adopted this document yet?}
>
> So it’s current author can munge it more freely, instead of waiting for a
> WG direction to form.
> (You can always do a hostile adoption, though ;-)
>
> > Hi, I've reviewed section 9 of notable-tags-06.
> > I raised a minor PR: https://github.com/cabo/notable-tags/pull/1
> > because I had to stare at the [uint,value] part really hard before I
> > understood things.  Part of the issue is that the "value" in the
> previous two
> > cases was just "obvious", and then I couldn't understand what it meant
> in the
> > third case.
>
> I just commented on the specific words.
>
> > I understood from the meeting this morning that tag 101 'e', is not
> actually
> > available.  But, actually it looks like it is according to IANA.org.
> > Or was it that another draft wanted it?
> > How about 'x' (NOPE) 'X' YES. 'u' YES.
> > https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml#cbor-tags
>
> (NOPE = tag 120 ‘x’ is already in use.)
> I’ll leave that choice to the proposers…
>
> > I think that the document might explain why we optimize the first 7
> (0..6),
> > rather than the first 3 or 5 or 9.  Are the next 128 worth it?
>
> We could skip the whole 1+2 tag range if we think the 24 1+1+1 cases from
> was-102 are enough of an expansion.
> But then we still have lots of 1+2 tags (0.07 % in use right now), if
> these actually are useful.
>
> I can’t really imagine more than 31 cases in one alternative being used
> very often, but then I’d like to hear from the people who actually use this.
>
> > I wonder if there are more than 7, are there typically more 100s?
> > If it turns out that 9 is the sweet spot, I'd be okay with more 1+1
> > and no 1+2.  I don't have any data on this.
> > I wonder if Michael, Duncan, Jared or Alexander do?
>
> Yes, we need a PDF (probability distribution function) :-)
> (Well, really, some intuition about that.)
>
> My hunch is that this is going to be approximately Zipf’s law, and that
> means the first 4 or 5 are really important, and then it goes down, but
> slowly.
>
> > I agree with the discussion that tag 101 could just encode 0..x
> > rather than uint+128.  I think that the simpler encoder might be worth it
> > here.  Particularly in some cases where I suspect which ones are the
> lower
> > numbered onces might not be known until later, and some code wants to
> come
> > back and fill in the alternatives afterwards, having left 1+4 for the
> uint or
> > something like that.
>
> See my previous message.
>
> Grüße, Carsten
>
>
>

-- 

*Michael Peyton Jones*
Software Engineering Lead | London, UK

Website: www.iohk.io <http://iohk.io>
Skype: michael.s.pj
Twitter: @mpeytonjones
PGP Key ID: 29F64616

[image: Input Output] <http://iohk.io>

[image: Twitter] <https://twitter.com/InputOutputHK> [image: Github]
<https://github.com/input-output-hk> [image: LinkedIn]
<https://www.linkedin.com/company/input-output-global>


This e-mail and any file transmitted with it are confidential and intended
solely for the use of the recipient(s) to whom it is addressed.
Dissemination, distribution, and/or copying of the transmission by anyone
other than the intended recipient(s) is prohibited. If you have received
this transmission in error please notify IOHK immediately and delete it
from your system. E-mail transmissions cannot be guaranteed to be secure or
error free. We do not accept liability for any loss, damage, or error
arising from this transmission