Subject: [apps-discuss] Pete Resnick's Discuss on draft-ietf-appsawg-json-merge-patch-06: (with DISCUSS)

From: "Pete Resnick" <[email-masked]>
Date: Wed, 20 Aug 2014 10:19:03 -0700

Pete Resnick has entered the following ballot position for
draft-ietf-appsawg-json-merge-patch-06: Discuss

When responding, please keep the subject line intact and reply to all
email addresses included in the To and CC lines. (Feel free to cut this
introductory paragraph, however.)

Please refer to http://www.ietf.org/iesg/statement/discuss-criteria.html
for more information about IESG DISCUSS and COMMENT positions.

The document, along with other ballot positions, can be found here:
http://datatracker.ietf.org/doc/draft-ietf-appsawg-json-merge-patch/

----------------------------------------------------------------------
DISCUSS:
----------------------------------------------------------------------

I am certainly willing to be talked out of this, but I am concerned about
the implementability and would like to DISCUSS it a bit.

In section 2:

   To apply the merge patch document to a target resource, the system
   realizes the effect of the following function, described in
   pseudocode.  For this description, the function is called MergePatch,
   and it takes two arguments: the target resource document and the
   merge patch document.  The Target argument can be any JSON value, or
   undefined.  The Patch argument can be any JSON value.

It took me repeated reading of the pseudocode (and may I mention that I
*hate* languages which rely on indentation ;-) ) to figure out that:

- If the Patch if not an object, the result *is* the Patch
- The Patch can't act on the internals of an array; it can only replace
the whole thing
- The Patch cannot replace objects with new objects.

Can't we *please* have a textual description of this protocol in addition
to a (recursive!) pseudocode function? I am not convinced that an
implementer will get their implementation right just from the pseudocode.

---

From: Richard Barnes <[email-masked]>
Date: Wed, 20 Aug 2014 16:23:01 -0400

On Wed, Aug 20, 2014 at 1:19 PM, Pete Resnick <[email-masked]>
wrote:

> implementer will get their implementation right just from the pseudocode

I don't really understand the confusion here.  This algorithm encodes
exactly what I surmised from looking at the example in the introduction,
and it was implementable in ~10min in python with only a very difference
between code and pseudocode (to deal with the case where Target[Name] is
undefined).

http://pastebin.mozilla.org/6073129

The textual description would probably be less clear, and would still be
recursive!

---

From: Pete Resnick <[email-masked]>
Date: Wed, 20 Aug 2014 15:39:01 -0500

On 8/20/14 3:23 PM, Richard Barnes wrote:
> exactly what I surmised from looking at the example in the 
> introduction, and it was implementable in ~10min in python with only a 
> very difference between code and pseudocode (to deal with the case 
> where Target[Name] is undefined).
>
> The textual description would probably be less clear, and would still 
> be recursive!

I would have been much more impressed if you had said, "It was 
implementable in ~10min is C without using recursion at all".

I'd also of course love to see some edge case examples (like a Patch 
being other than an object, or a Patch containing some nulls in an 
array) that actually debugged as opposed to repeating the obvious 
example from the document.

And of course that's my concern: Because there is no textual 
description, I can't tell if anything that I might implement that is 
structured differently from the pseudocode provided would in fact be 
equivalent except by doing a debug analysis of the psuedocode and my 
code. That's the difference between doing open source and writing a 
standard.

And I'll repeat, I could be talked out of it. But if I had to implement 
this in C without recursion, I'd be a grumpy implementer. Of course, I'm 
old and grumpy to begin with.

pr

-- 
Pete Resnick<http://www.qualcomm.com/~presnick/>
Qualcomm Technologies, Inc. - +1 (858)651-4478

---

From: Richard Barnes <[email-masked]>
Date: Wed, 20 Aug 2014 16:54:08 -0400

> implementable in ~10min is C without using recursion at all".

As someone whose day job involves writing C, that's a ridiculous standard
for anything that doesn't require bit-accuracy.

Likewise no recursion -- the state is going to have to get stored
somewhere, might as well be the stack.

I'd also of course love to see some edge case examples (like a Patch being
> other than an object, or a Patch containing some nulls in an array) that
> actually debugged as opposed to repeating the obvious example from the
> document.
>

That's a fine suggestion, but not DISCUSS-worthy.

> And of course that's my concern: Because there is no textual description,
> I can't tell if anything that I might implement that is structured
> differently from the pseudocode provided would in fact be equivalent except
> by doing a debug analysis of the psuedocode and my code. That's the
> difference between doing open source and writing a standard.
>

Textual descriptions are just algorithms in natural language.

> old and grumpy to begin with.

Honestly, if you're using JSON in C, you're probably a grumpy implementor.
C is not built to handle dynamic data structures like JSON hands you.

--Richard

---

From: Pete Resnick <[email-masked]>
Date: Wed, 20 Aug 2014 16:21:05 -0500

On 8/20/14 3:54 PM, Richard Barnes wrote:
> On Wed, Aug 20, 2014 at 4:39 PM, Pete Resnick 
> <[email-masked] <mailto:[email-masked]>> wrote:
>
> As someone whose day job involves writing C, that's a ridiculous 
> standard for anything that doesn't require bit-accuracy.
>
>     I'd also of course love to see some edge case examples (like a
>     Patch being other than an object, or a Patch containing some nulls
>     in an array) that actually debugged as opposed to repeating the
>     obvious example from the document.
>
>

None of the above is part of the DISCUSSion. I was simply saying that a 
python version that perfectly mirrors the pseudocode is not going to 
convince me that the pseudocode is sufficient for independent 
implementations.

Even if you had provided some non-recursive C that purportedly did the 
same thing, I'm not sure that would convince me that a textual 
description is unnecessary. Like I said, it took me quite a while 
looking at the pseudocode to figure out what the edge cases were. I'm 
*pretty sure* I could code it up in C at this point, but I'm not 
positive, because I'm not sure I've gotten all of the semantics right.
>     description, I can't tell if anything that I might implement that
>     is structured differently from the pseudocode provided would in
>     fact be equivalent except by doing a debug analysis of the
>     psuedocode and my code. That's the difference between doing open
>     source and writing a standard.
>
>

No, they are most certainly not. Textual descriptions provide semantics 
to the operations. Unlike algorithms, textual descriptions can give you 
the edge cases, can tell you what happens in all sorts of weird error 
conditions, etc., and all without having to give you the full algorithm. 
To take an example from one of the -core documents on this week's call:

    The sequence number selected for a notification MUST be greater than
    that of any preceding notification sent to the same client with the
    same token for the same resource.

Yes, that surely implies parts of an algorithm, but it doesn't require 
that the code, e.g., check for a client identifier or a token and 
compare it to some table of previously sent notifications. It simply 
means that, however you code it, you satisfy the requirement.
>
>     And I'll repeat, I could be talked out of it. But if I had to
>     implement this in C without recursion, I'd be a grumpy
>     implementer. Of course, I'm old and grumpy to begin with.
>
>
> Honestly, if you're using JSON in C, you're probably a grumpy 
> implementor.  C is not built to handle dynamic data structures like 
> JSON hands you.

Well, that might be true. I can think of all sorts of interesting ways 
to do a JSON implementation in C. (I've parsed some pretty weird crap in 
C in my day.) But really, this misses the point of my concern: As an 
implementer, it seems to me that I'm having to figure out the semantics 
of the algorithm in order to be sure I've gotten it right. Maybe my 
brain is soft today because of all of this reading, but it wasn't 
obvious to me that the pseudocode was so simple that anyone would be 
able to successfully do that.

pr

---

From: Richard Barnes <[email-masked]>
Date: Wed, 20 Aug 2014 17:29:38 -0400

On Wed, Aug 20, 2014 at 5:21 PM, Pete Resnick <[email-masked]>
wrote:

>> being other than an object, or a Patch containing some nulls in an array)
>> that actually debugged as opposed to repeating the obvious example from the
>> document.
>>
>
> same thing, I'm not sure that would convince me that a textual description
> is unnecessary. Like I said, it took me quite a while looking at the
> pseudocode to figure out what the edge cases were. I'm *pretty sure* I
> could code it up in C at this point, but I'm not positive, because I'm not
> sure I've gotten all of the semantics right.
>
>
>
>> equivalent except by doing a debug analysis of the psuedocode and my code.
>> That's the difference between doing open source and writing a standard.
>>
>
> No, they are most certainly not. Textual descriptions provide semantics to
> the operations. Unlike algorithms, textual descriptions can give you the
> edge cases, can tell you what happens in all sorts of weird error
> conditions, etc., and all without having to give you the full algorithm. To
> take an example from one of the -core documents on this week's call:
>
> that the code, e.g., check for a client identifier or a token and compare
> it to some table of previously sent notifications. It simply means that,
> however you code it, you satisfy the requirement.
>

It sounds like you're looking for some abstracted, "here's what the
algorithm must accomplish" definition.  The CORE case is simple enough that
that works.  In this case, the objective is complex enough that I don't see
how you get there without defining an algorithm.  (Keep in mind that JSON
itself is recursive, so to some degree, if you don't recurse, you're doing
it wrong!)

Could you suggest text?

--Richard

> implementor.  C is not built to handle dynamic data structures like JSON
> hands you.
>
>
> Well, that might be true. I can think of all sorts of interesting ways to
> do a JSON implementation in C. (I've parsed some pretty weird crap in C in
> my day.) But really, this misses the point of my concern: As an
> implementer, it seems to me that I'm having to figure out the semantics of
> the algorithm in order to be sure I've gotten it right. Maybe my brain is
> soft today because of all of this reading, but it wasn't obvious to me that
> the pseudocode was so simple that anyone would be able to successfully do
> that.
>
>
> pr
>
> --
> Pete Resnick <http://www.qualcomm.com/~presnick/> <http://www.qualcomm.com/~presnick/>

---

From: Nico Williams <[email-masked]>
Date: Wed, 20 Aug 2014 16:41:44 -0500

FYI, in jq, this can be implemented as follows (assuming $doc is bound
to the document to be edited and $patch is bound to the patch):

  def apply_patch(patch):
    . as $doc | patch as $patch | $patch |
    reduce (path(recurse(.[]?; true))?) as $path ($doc;
      ($patch | getpath($path)) as $value |
      if $value == null
      then delpaths([$path])
      elif $value | type | . == "number" or . == "string" or . == "boolean"
      then setpath($path; $value)
      else .
      end);

This applies the patches output by the `patch` closure to the input.
It recurses for traversing paths in the $patch.

In English this says "for each path in the patch, if the value at that
path in the patch is null then delete the same path from the document,
else if the value at that path in the patch is a scalar then set the
same path in the document to that scalar, else leave the document
as-is".

Nico
-- 

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Wed, 20 Aug 2014 17:15:13 -0500

> C is not built to handle dynamic data structures like JSON hands you.

Well, if you're using libjq, you're probably not too grumpy.  It's
notionally a copy-on-write API, so one writes code like:

    obj = jv_object_set(obj, jv_string("foo"), ...);

Memory management is easier than with non-COW JSON C libraries I've used.

Anyways, I'm making noise...  But I hope it helps someone.

You can find libjq at https://github.com/stedolan/jq .

Nico
--

---

From: Nico Williams <[email-masked]>
Date: Wed, 20 Aug 2014 17:20:37 -0500

On Wed, Aug 20, 2014 at 4:29 PM, Richard Barnes <[email-masked]> wrote:
> [...].  (Keep in mind that JSON

Path traversal in a tree requires a stack, which is really what Pete
R. must have meant, since tail-recursion is equivalent to looping, and
non-tail-recursion is equivalent to a loop that keeps state in a stack
-- it's the stack that must be a sticking point, and if it is it's the
need to traverse the tree that is the cause of it.

A path-based patch doesn't require a stack.  Sometimes a path-based
patch is easier to use than this scheme, sometimes it's the reverse.
Partly it depends on what you have to work with on the client side.

Nico
--

---

From: "Manger, James" <[email-masked]>
Date: Thu, 21 Aug 2014 09:31:53 +1000

> I'd also of course love to see some edge case examples
> (like a Patch being other than an object,

That would be examples 9, 10, 11, and 12 in Appendix A "Example Test Cases".

> or a Patch containing some nulls in an array)

Reasonable suggestion.

> that actually debugged as opposed to repeating the obvious example from the document.

The 15 examples in Appendix A do that.

--
James Manger

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 20 Aug 2014 17:55:30 -0700

As you know, the earlier drafts of this document were textural descriptions, and the WG kept having problems with the text. When the pseudocode replacement was suggested, the WG seemed to like that much better. Also note that the pseudocode in the draft is much more textural than typical pseudocode.

So, no, I don't think we can have a textural description that won't end up looking a lot like the pseudocode. In particular, I seriously doubt we can have such text without recursion; we tried earlier and pretty much failed.

Unfortunately, I cannot convince you about your hypothetical implementer who tries to get their implementation from the pseudocode but ignores the examples as test cases. We have a pretty complete set of examples that could shake out any implementation, I believe. Your discussion of C with Richard confuses me more on this point, since the C programmers I know would probably strongly prefer to go from pseudocode and examples than from text.

--Paul Hoffman

---

From: Pete Resnick <[email-masked]>
Date: Wed, 20 Aug 2014 20:26:54 -0500

On 8/20/14 7:55 PM, Paul Hoffman wrote:
> As you know, the earlier drafts of this document were textural descriptions...

Actually, I did not know. I haven't been following this particular 
document on the apps-discuss list.

> ...and the WG kept having problems with the text. When the pseudocode replacement was suggested, the WG seemed to like that much better. Also note that the pseudocode in the draft is much more textural than typical pseudocode.
>

Well, that may be the end of the DISCUSSion then. If you've already 
tried and failed to produce this, I'm not inclined to have you 
re-suffer. I may make some suggestions of text to clarify those things 
that I had trouble getting through, but those will simply be comments. 
If you all think they would be helpful to implementers, I think it would 
be good to add them. I'll work on that when I finish my other document 
reviews. But unless someone wants to come out of the woodwork and say, 
"Pete's right. Back to the saltmines!", consider this resolved. I'll 
update my ballot when I get a chance.

> Unfortunately, I cannot convince you about your hypothetical implementer who tries to get their implementation from the pseudocode but ignores the examples as test cases. We have a pretty complete…

It's a style thing. I always hated coding from pseudocode; I could 
always come up with more efficient algorithms. I'd rather just be told 
what the interfaces were and what the output was supposed to look like. 
But to each his own.

pr

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 21 Aug 2014 07:31:41 +0100

Pete,

I'm absolutely with you on the principle. Many of the current "web standards" are extremely hard to use because they rely completely on complex, undebuggable pseudo code. We should not repeat this mistake.

In this specific case, the pseudo code is simple and indeed works much better than a textual description. (And it has been derived from an implementation, which does pass all the examples.)

Sent from my iPad

> On 21.08.2014, at 02:26, Pete Resnick <[email-masked]> wrote:
> 
> Actually, I did not know. I haven't been following this particular document on the apps-discuss list.
> 
> Well, that may be the end of the DISCUSSion then. If you've already tried and failed to produce this, I'm not inclined to have you re-suffer. I may make some suggestions of text to clarify those things that I had trouble getting through, but those will simply be comments. If you all think they would be helpful to implementers, I think it would be good to add them. I'll work on that when I finish my other document reviews. But unless someone wants to come out of the woodwork and say, "Pete's right. Back to the saltmines!", consider this resolved. I'll update my ballot when I get a chance.
> 
> It's a style thing. I always hated coding from pseudocode; I could always come up with more efficient algorithms. I'd rather just be told what the interfaces were and what the output was supposed to look like. But to each his own.
> 
> pr
> 
> -- 
> _______________________________________________
> apps-discuss mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/apps-discuss
>

---

From: Carsten Bormann <[email-masked]>
Date: Thu, 21 Aug 2014 09:44:42 +0100

> On 20.08.2014, at 22:29, Richard Barnes <[email-masked]> wrote:
> 
> without defining an algorithm.

If you squint a bit*), you can see that the pseudo code is just a recursive (functional) definition, not really a (procedural) algorithm. Anything that has to say "go to step 6" fails the smell test. This one doesn't. 

Grüße, Carsten

*) needed because there are some variables, iirc.