Subject: Re: RECUR Subset and IPTel's CPL: Need Resolution

From: [email-masked]
Date: Mon, 14 May 2001 10:29:40 -0400

John claimed:
>> Not being in Minnesota, I can not be sure of all that was
>> discussed.  However, I really am reluctant to see us "step
>> back" a draft in order to make it fit a smaller model such as
>> telephony.
>
>Yeah, but RECUR is too big for calendaring, too.

Pardon me but can you be a bit more vague w/that?  Thats like saying "The 
PC wont work" and expecting someone to fix it over the phone...

The recurrence grammar is somewhat confusing at first but is quite 
powerful.  It can easily express farily complex and mundane recurrence 
patterns in a compact manner.  That makes it ideal for Calendaring & 
Scheduling.  We have had some ambiguities w/it but not all parts of it (or 
w/some of the parts proposed for removal).

>It can happen, I think; there's no law that says that the Draft
>Standard has to be a superset of the Proposed Standard.  In fact,
>there's at least one case where RFC-2026 mandates that features
>be removed:

This is not your other argument.  You have claimed that its too "big" 
(err, complex??); not that 2 or more implementations do not implement it. 
The iptel argument so far seems to be one of "we want speed over 
complexity so we do not want to have x,y, & z in the grammar".  These are 
not the same justifications you cite.

In fact, there are at least 2 engines that I can think of that support 
stuff that is on the chopping list like BYSETPOS.  Outlook uses it 
exclusively to represent stuff like "The 4th Thursday of the Month" and 
Organizer also supports it from what I recall.  By removing 'unwanted' 
stuff from the grammar to make it easier for some to build, you have 
managed to make cuts that are non-backwards compatabile and that severly 
impact interoperatbility with existing early implimentors of the Drafts. 
Way to go. 

This is definitly starting to feel like a Monday already...

Bruce
PS: It seems this thread was not cross posted to the iptel list based on 
the addresses in my reply header above.  Can someone repost that address 
and cross post this for me??
===========================================================================
Bruce Kahn                                INet: [email-masked]
Iris Associates                          Phone: 978.392.5335
Westford, MA, USA 01886                    FAX: and nothing but the FAX...
Standard disclaimers apply, even where prohibited by law...

---

From: John Stracke <[email-masked]>
Date: Mon, 14 May 2001 11:50:59 -0400

[email-masked] wrote:

> Pardon me but can you be a bit more vague w/that?

Heh.  I suppose I could: "Um...RECUR...I dunno..." ;-)

But I was vague because we've gone over this before, and I went
into detail then.

> The recurrence grammar is somewhat confusing at first but is
> quite powerful.

That is, in fact, the problem: how do you build a user interface
that expresses the full power? It can be done, I suppose, but
it's going to be *massively* complex, very hard for users to
learn.

The problem is that the recurrence rules are designed as a
grammar, with the expectation that there'll be no difficulty in
getting engines to understand and expand them.  From that
viewpoint, it's not a particularly complex grammar; but, from the
viewpoint of a user who has to be able to take a recurrence rule,
hold in their head, and maybe edit it, it's *far* too
complicated.  To repeat the example I posted in my
draft-stracke-calsch-rrule-subset-00.txt (unsubmitted, but posted
to the WG:
<http://www.imc.org/ietf-calendar/mail-archive/msg06770.html>),
iCalendar lets you specify an event which:

   * occurs every 79 seconds,
   * also occurs at 3:15:25 PM on the 12th, 37th, and 159th days
     of the year,
   * but does not occur unless it's 13 or 23 seconds after the
     minute,
   * and does not occur on the second Tuesday of the month.

This is absurd--and yet, any compliant implementation has to be
able to accept it, expand it (not too hard), show it to the user
(difficult), and let the user edit it (well-nigh impossible).

(In fact, I've since realized I could've come up with something
even more complex, since RRULE and EXRULE can each appear
multiple times in a VEVENT.)

> This is not your other argument.  You have claimed that its too
> "big" (err, complex??); not that 2 or more implementations do
> not implement it.

In fact, my objections are based largely on the prediction that
no two implementations will implement the same subset of RECUR.
To quote my draft again:

     In order to make the user interface comprehensible,
     each CUA will probably expose only a subset of the
     available recurrence features to the user.  The risk,
     then, is that different CUAs will expose different
     subsets, and will not be properly tested for iCalendar
     objects which stray outside those subsets.  Even if
     they expand those iCalendar objects correctly, they may
     not display the full recurrence rule correctly, since
     that would require complicating the UI.  If that
     happens, the user will wind up seeing that the
     recurrence rule for their repeating event says it
     occurs every Monday, but the calendar does not show the
     event on every Monday; there are gaps.  Confusing the
     users like this effectively means that there will not
     be interoperability: even if the underlying iCalendar
     implementations understand each other, the users don't.

> In fact, there are at least 2 engines that I can think of that
> support stuff that is on the chopping list like BYSETPOS.
> Outlook uses it exclusively to represent stuff like "The 4th
> Thursday of the Month" and Organizer also supports it from what
> I recall.

It is not enough to be able to say "implementations A and B use
BYSETPOS, and implementations C and D use UNTIL, so they both can
stay in".  For iCalendar to advance to Draft Standard, there must
be two implementations which implement the *entire* RECUR
grammar.  In my opinion, "implement" in this case must cover the
user interface, not just the backend.  (Patrik, am I right on
this procedural point? I'm relying in part on your ruling that 1
day == 24 hours would confuse the users.)

>  By removing 'unwanted' stuff from the grammar to make it
> easier for some to build, you have managed to make cuts that
> are non-backwards compatabile and that severly impact
> interoperatbility with existing early implimentors of the
> Drafts.  Way to go.

But this is a normal part of the IETF process: the spec will
change as it proceeds from Internet-Draft to Proposed Standard to
Draft Standard to (rarely) Standard.  The IETF's goal is produce
good standards for interop, which will be used for a long, long
time; the only way to be sure of that is to judge the early
implementations, and tweak the specs accordingly.  That
necessarily implies that early adopters are risking some
transition pain in the short run, in order to improve interop
over the long run.

--
/=================================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.   |
|Chief Scientist |================================================|
|eCal Corp.      |You're just jealous because the voices only talk|
[email-masked]|to me.                                          |
\=================================================================/

---

From: Eric Busboom <[email-masked]>
Date: Mon, 14 May 2001 10:39:37 -0700 (PDT)

John, Johnathan,

This is how I understand the problems that the IPTEL group identified with
RECUR. Are these correct?

	(1) Telephony equipment must be able to check that a given time is
	included with in the events specified by a DTSTART, DURATION and set of
	RRULES, RDATEs, EXRULEs and EXDATEs in constant time. ( Or is it
	O(n) for the number of elements in the byrules? ) Generally, RECUR
	rules require O(n) in the number of occurrences.

Other problems that have been identified include:

	(2) Because the RRULEs are so complex, and because there are many
	different ways to specify a single set of occurrences, it will be very
	difficult for a CUA to create a GUI that can manipulate any arbitrary
	incoming RRULEs.

The proposed solutions are:

	(1) Remove COUNT

	(2) Remove BYSETPOS

	(3) Remove byrules and frequencies for hour, minute and second.

	(4) Limit the duration of an event to less than 24 hours.

(1) and (2) are proposed to directly allow constant time operation. (3)
and (4) are proposed to disallow a RRULE from generating any two
occurrences that overlap. Overlapping rules compicate a specific algotithm
for performing (1).

Now, for some questions.

For (1). Is it O(1) or O(n) with number of BYrule elements? The body of
draft-stracke-calsch-rrule-subset-XX.txt says O(1), but the algorithm in
the appendix implies O(n). Or does the O(1) mean "O(1) in number of
occurrences?"

Past discussions noted that the algorithm may be O(1) in a single rule,
but will be linear with respect to multiple rules. So what would you do
with a client that always expanded recurrence rules to RDATE?  (thereby
forcing O(n). ) Would the telephony equipment set a limit on the maximum
number of RDATE, RRULE, EXRULE and EXDATE properties it would accept, and
reject anything over that limit?

And, if the algorithm is O(n) with number of rules, and actually O(n) with
number of BYxxx rule part elements in each rule, then in the general case
the algorithm is O(n^2) in the size of the RRULE, a long way from O(1).

So, do you really need O(1), or can you get by with an very fast check of
the upper bound of the occurrence set? That is, what if you could quickly
determine if the rrule is too complex for your processor to handle?

Also, please review the current proposed text change for for RECUR, issue
#15 at:

	http://softwarestudio.org/iCal/ProposedChanges.txt

These restrictions prevent many absurd examples like the one in
draft-stracke-calsch-rrule-subset-XX.txt.

eric.

---

From: John Stracke <[email-masked]>
Date: Mon, 14 May 2001 14:12:28 -0400

Eric Busboom wrote:

> with a client that always expanded recurrence rules to RDATE?

Personally, I wouldn't worry about it, because such a client is not likely to get
many users.  If my calendar turns "every Monday for a year" into "1/1, 1/8, 1/15,
1/22, ...", then I can't edit it to be "every Tuesday" without a massive
investment of my time.

> Would the telephony equipment set a limit on the maximum

Jonathan?

> draft-stracke-calsch-rrule-subset-XX.txt.

Yeah, but I don't think they simplify the conceptual model; they just add extra
limitations that the user has to understand.

--
/==============================================================\
|John Stracke    | http://www.ecal.com |My opinions are my own.|
|Chief Scientist |=============================================|
|eCal Corp.      |Speak softly and carry an Illudium Q-32      |
[email-masked]|Explosive Space Disintegrator.               |
\==============================================================/

---

From: Alan Davies <[email-masked]>
Date: Mon, 14 May 2001 14:12:22 -0400

>the algorithm is O(n^2) in the size of the RRULE, a long way from O(1).

Surely it's O(n) with the number of BYxxx rule part elements
in all of the rules combined?

--Alan

---

From: Eric Busboom <[email-masked]>
Date: Mon, 14 May 2001 11:37:19 -0700 (PDT)

> in all of the rules combined?

Oh yes -- that is more sensible. Anyway, the point still holds -- the
algorithm can't be constant time.

eric.

---

From: Jonathan Lennox <[email-masked]>
Date: Mon, 14 May 2001 14:53:00 -0400 (EDT)

> 	rules require O(n) in the number of occurrences.

O(n) in the textual length of a rule, specifically.  (With the constant
factor small, hopefully.)  This is clearly inevitable, because the server
has to read and parse the rule in order to execute it.

O(1) in the value of any parameter, though.

> 	difficult for a CUA to create a GUI that can manipulate any arbitrary

This is the issue John identified.  Seeing what existing GUIs do was a
motivating factor for my decisions as to which parts would be okay to drop,
but it's not directly behind my decision to create a subset.

> occurrences that overlap. Overlapping rules compicate a specific algotithm

It's a bit more complicated than "occurences which overlap", but yes, that's
basically correct.

> the appendix implies O(n). Or does the O(1) mean "O(1) in number of

See above.  O(n) in the textual size of the rule; O(1) both in the number
occurences and in the elapsed time since DTSTART.  (I suspect any algorithm
which can resolve COUNT and BYSETPOS has to be non-constant-time in at least
one of these.)

> reject anything over that limit?

If it always expanded its rules, then yes, it would.  I suppose the
equipment would have to have a "don't be absurd" response if someone dropped
a 10-megabyte rule on it.

> the algorithm is O(n^2) in the size of the RRULE, a long way from O(1).

No, because rules are resolved sequentially, from what I understand.  Check
the first one, check the second one, etc.  Yes, it's O(m*s) (if you have 'm'
rules, each of average size 's'), but that's the same thing as O(n).

> draft-stracke-calsch-rrule-subset-XX.txt.

Yes, but I think they're orthogonal.  (I.e. they add additional restrictions
to prevent paradoxical rules, but don't alter theoretical algorithmic
complexity needed needed to resolve an RRULE.)

-- 
Jonathan Lennox
[email-masked]