Re: [Json] Proposed minimal change for duplicate names in objects

John Cowan <cowan@mercury.ccil.org> Wed, 03 July 2013 16:27 UTC

Return-Path: <cowan@ccil.org>
X-Original-To: json@ietfa.amsl.com
Delivered-To: json@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 91E1111E81F3 for <json@ietfa.amsl.com>; Wed, 3 Jul 2013 09:27:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.556
X-Spam-Level:
X-Spam-Status: No, score=-3.556 tagged_above=-999 required=5 tests=[AWL=0.043, BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id oj5lxcaMfEHT for <json@ietfa.amsl.com>; Wed, 3 Jul 2013 09:27:32 -0700 (PDT)
Received: from earth.ccil.org (earth.ccil.org [192.190.237.11]) by ietfa.amsl.com (Postfix) with ESMTP id 138CA11E81E8 for <json@ietf.org>; Wed, 3 Jul 2013 09:27:32 -0700 (PDT)
Received: from cowan by earth.ccil.org with local (Exim 4.72) (envelope-from <cowan@ccil.org>) id 1UuPtx-0000F3-WA; Wed, 03 Jul 2013 12:27:30 -0400
Date: Wed, 3 Jul 2013 12:27:29 -0400
From: John Cowan <cowan@mercury.ccil.org>
To: Nico Williams <nico@cryptonector.com>
Message-ID: <20130703162729.GC32044@mercury.ccil.org>
References: <B86E1D4B-1DC8-4AD6-B8B3-E989599E0537@vpnc.org> <CAK3OfOj3MNNhjwo2bMa5CgoqynzMRVvviBXC8szxt5D17Z7FDg@mail.gmail.com> <51D3C63C.5030703@cisco.com> <CAK3OfOg5ErNO5zozaCB-qchSaUb-dy4Da5b1KKJNTM0Bnpm+1A@mail.gmail.com> <51D3CB52.7040902@cisco.com> <CAK3OfOgsWFpUzus_Nfq3rewtnnjwk-5_k2WX11yQhNPC+BoR5g@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CAK3OfOgsWFpUzus_Nfq3rewtnnjwk-5_k2WX11yQhNPC+BoR5g@mail.gmail.com>
User-Agent: Mutt/1.5.20 (2009-06-14)
Sender: John Cowan <cowan@ccil.org>
Cc: Paul Hoffman <paul.hoffman@vpnc.org>, Eliot Lear <lear@cisco.com>, "json@ietf.org WG" <json@ietf.org>
Subject: Re: [Json] Proposed minimal change for duplicate names in objects
X-BeenThere: json@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "JavaScript Object Notation \(JSON\) WG mailing list" <json.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/json>, <mailto:json-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/json>
List-Post: <mailto:json@ietf.org>
List-Help: <mailto:json-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/json>, <mailto:json-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 03 Jul 2013 16:27:36 -0000

Nico Williams scripsit:

> > You've got to retain state.  You don't have to retain the value, but you
> > do have to retain the name.  It's O(k), and knowing you I know you're
> > smart enough to approach that (because I am and so I'm using inductive
> > theory ;-).  And I'll bet you a nickel that this is not going to be
> > anyone's high order bit.

I do not understand the third sentence.  If k is a constant, then O(k) is
the same as O(1), and it is palpable that you cannot pack all the names
of a JSON object into O(1) space, since the amount you need varies as the
product of the (mean) length of the names and the number of names.  As
such, it is not even O(n).  You can get an O(n) probabilistic implementation
by retaining fixed-length hashes of the names already seen, though.

> You'd only have to retain state to satisfy this up-till-now
> non-existent requirement.

Quite so.

> It's a psychological cost too.  No one wants their code rendered
> non-compliant by a new RFC.  That's part of what's making it hard to
> get consensus.

True, but we gave way to that feeling, we'd never have any new standards,
as the first thing a standard does is to break existing implementations.
("The first thing a principle does is kill somebody."  --Peter Wimsey)
We must simply take the view of the ANSI C Rationale, which wisely said
"Existing code [meaning user code, the equivalent of JSON data] is
important; existing implementations are not."

> *My* opinion here is that in the case of streaming generators and
> parsers the burden of avoiding/dealing with duplicate names should be
> one layer higher: at the applications using them.  But it's also my
> opinion that some such apps may not be able to do anything about this
> either,

+1

> which is why my proposal is we write SHOULD and explain when
> it's OK to not stick to the SHOULD.

In that case, we should write a conditional MUST.  We use SHOULD when
we want to provide scope for implementer judgement.  But that is an
editorial detail.

-- 
John Cowan              http://www.ccil.org/~cowan      cowan@ccil.org
"After all, would you consider a man without honor wealthy, even if his
Dinar laid end to end would reach from here to the Temple of Toplat?"
"No, I wouldn't", the beggar replied.  "Why is that?" the Master asked.
"A Dinar doesn't go very far these days, Master.        --Kehlog Albran
Besides, the Temple of Toplat is across the street."      The Profit