Subject: RE: [rohc] Re: FW: [tcpm] WG last-call of TCP header compression

From: "Finking, Robert" <[email-masked]>
Date: Wed, 28 Sep 2005 09:43:45 +0100

Hi Joe,

Thanks for the reply and the pragmatic approach you are taking. Just one
thing I wanted to point out, which is tripping us up here - I think you
missed the negative when I said:

> > To be clear, prolog has not been used as pseudocode, but yes we are 

That's: "NOT been used". To repeat, Prolog has NOT been used as
pseudocode. The FN is neither Prolog, nor is it pseudocode. The FN as it
was when I inherited it from Richard Price was based on Prolog, so
closely in fact that you could execute it. However there were many
things in that notation which were hard to read/manage, so we abandoned
prolog and stuck to producing an easy to use notation.

I myself hadn't ever written any Prolog prior to helping Richard out
with his implementation (which was my original role), though I was aware
of the maths behind it.

The only association the FN has with Prolog at present is that the
parsing/checking tool which Carsten/Eilert produced was written in
Prolog. It could just as well have been written in C however.

I must admit to being slightly disheartened that somebody with a formal
language background is having difficulty with the notation - it really
is pretty simple considering what it's aiming to communicate.

Regards

Raffles

> -----Original Message-----
> From: Joe Touch [mailto:[email-masked]] 
> Sent: Tuesday, September 27, 2005 5:11 PM
> To: Finking, Robert
> Cc: [email-masked]; Ghyslain Pelletier (LU/EAB); Kristofer 
> Sandlund (LU/EAB); [email-masked]
> Subject: Re: [rohc] Re: FW: [tcpm] WG last-call of TCP header 
> compression
> 
> 
> Hi, Robert,
> 
> Finking, Robert wrote:
> > Hi Joe,
> > 
> > Thanks. Yes it does help and it's good to see we're making 
> progress on 
> > some points at least. The thing that's coming across to me after 
> > reading several exchanges is that a lot of your objections 
> seem to be 
> > rooted in misunderstandings. It seems to me that you've missed the 
> > basics of the FN, which is causing you a lot of confusion.
> 
> I agree; the key question is whether that's a reasonable 
> outcome, though.
> 
> I may not have a lot of background about ROHC, but I do have 
> deep background in TCP and IP, and had a fairly deep formal 
> language background which I've used fairly regularly to 
> design notations (e.g., for distributed switch simulation and 
> most recently for virtual network configuration).
> 
> > This of course is our fault and we clearly need to lay out the 
> > foundations A. more clearly and B. (as you rightly point out) 
> > throughout the document wherever they're salient. At 
> present I think 
> > we've accidentally assumed that the reader has understood 
> everything 
> > perfectly and remembered everything they've read up to that 
> point in 
> > the document, which is on reflection rather silly of us. 
> Easy to lose 
> > the wood for the trees!
> 
> That's common for all of us; it helps to remind ourselves 
> that if we wanted performance or economy, we'd write in 
> assembler, and that all higher level notations need to be 
> human-accessible ;-)
> 
> > To try and clarify the whole underlying idea though, it's based on 
> > relations (in a mathematical sense). The whole idea is to have a 
> > single definition of how the compressed and uncompressed 
> versions of a 
> > field relate to each other. When I say "relational" I'm 
> talking maths 
> > - or "math" if you're in the US :-) - not programming languages.
> 
> This is sounding more and more like a grad school project 
> than an IETF spec ;-)
> 
> > This is perhaps the easiest way to think of the FN; as a 
> mathematical 
> > notation - rather than as a programming language. Since the 
> experience 
> > of most readers with programming languages will be with C, 
> C++, Java, 
> > Python etc. I can appreciate that programming language 
> analogies are 
> > bound to be made, but we need to avoid the reader doing so 
> because it 
> > will only cause confusion. Similarity with such languages 
> is cosmetic 
> > only.
> > 
> > To pick up on just one specific point you made:
> > 
> > 
> >>This is a specification. In specifications, language is
> >>usually imperative pseudocode or EBNF. It's confusing to use 
> >>prolog as pseudocode in this case because you're not doing 
> >>unification. While that explains some of the notation, it 
> >>doesn't make a good case for it.
> > 
> > 
> > To be clear, prolog has not been used as pseudocode, but yes we are 
> > doing unification (though in a wider sense than that supported by 
> > Prolog). We originally made that explicit in the draft but as my 
> > co-author pointed out most of the readers will not know what 
> > unification is, and if they did go and look it up they'll 
> find lots of 
> > Prolog references, which won't necessarily help, so we added in the 
> > "two-way matching" text which is included in section 3.2.1 Perhaps 
> > some imperative pseudocode may help in specifying example 
> > implementations of some of the encoding methods, but the FN 
> > specifically aims to avoid telling the implementer *how* to 
> do his/her 
> > job and instead aims at specifying *what* needs to be done, in a 
> > formal, non-ambiguous, machine checkable (and yes if you want to, 
> > compilable) way.
> > 
> > This is the case for the FN, that it facilitates a *formal* 
> > specification. I can understand your concerns about readability and 
> > it's an issue that we've strived to tackle, both in the way 
> the draft 
> > is written and also in the notation itself.
> > 
> > The underpinning assumption of the FN, is that header 
> compression is a 
> > fundamentally complex task, that can't be successfully specified in 
> > plain old English, even when augmented with the variety of ad hoc 
> > methods that have been employed in the past. The FN 
> therefore aims to 
> > be "as simple as possible, but no simpler".
> > 
> > If it can be shown that something simpler than the FN would suffice 
> > for this task, then sure lets have it, but it is my view that the 
> > other approaches taken thus far to tackle this problem have been 
> > insufficient.
> 
> I agree on that point, but jumping from box notation to 
> Prolog is quite a large leap of faith - in both 'leaping' and 
> 'faith'. I understand why you want to use Prolog as it 
> implies flexibility in the compressor and decompressor (you 
> write a 'validator' in both cases, and let the interpreter 
> figure out how to handle it), but if this notation isn't 
> generating running code (and it isn't), then it's primary 
> purpose must be for humans to follow.
> 
> And as a notation, Prolog is write-only, much like APL.
> 
> For specs, I prefer notations that are easier to read and follow.
> 
> If your point is that the notation as-is has some other 
> benefit, then the FN doc needs to make that case. If not, I 
> suspect other TCP-folk who want to design compressors will 
> have the same reaction I and others I've polled had - which is to
> 	a) not read it
> 	b) read it and not think it's useful
> 
> > It is understandable to wish that a thing is simpler than 
> it is, but 
> > it is I think a mistake to attempt to treat a fundamentally complex 
> > problem
> > *too* simply; ultimately failure will result. My belief is that the
> > complexity of this problem requires a formal definition if 
> a workable
> > solution is to be found. Of course I may be wrong!
> 
> You are making a fine point for a dissertation, provided you 
> have a reasons that back it up. But again for the IETF, this 
> notation is just plain obscure to me and to others.
> 
> Joe
> 

_______________________________________________
Rohc mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/rohc

---

From: Joe Touch <[email-masked]>
Date: Wed, 28 Sep 2005 08:09:20 -0700

>>>To be clear, prolog has not been used as pseudocode, but yes we are 

I didn't miss it; I'm speaking about even the use of Prolog-style in a
spec.

> Prolog. It could just as well have been written in C however.

Agreed. So can a Prolog interpreter. However...

> is pretty simple considering what it's aiming to communicate.

That's the issue. Simple can be awkward, and things even 'based on
Prolog' are awkward to follow. Elegant to write compact representations,
and elegant to run (when actual code), but inaccessible as a way to
communicate to another human, which is, after all, what I hope the
primary goal of the FN would be.

Joe