www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Isn't "transitive" the wrong word?

reply "Janice Caron" <caron800 googlemail.com> writes:
Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
completely the wrong word?

The word "transitive" applies to binary relations, like less-than. A
relation R is transitive if

    (a R b) and (b R c) implies (a R c)

For example, less-than is transitive, because

    (a < b) and (b < c) implies (a < c)

But the word "transitive" has no meaning when applied to a unary type
constructor like const().

No, methinks the word you're looking for here is RECURSIVE. Const in D
is recursive, not transitive.

Should we change all the documention, or is this some new definition
of "transitive" which is in common use in some field of which I am
unaware?
Apr 04 2008
next sibling parent Jason House <jason.james.house gmail.com> writes:
Janice Caron Wrote:

 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?
 
 The word "transitive" applies to binary relations, like less-than. A
 relation R is transitive if
 
     (a R b) and (b R c) implies (a R c)
 
 For example, less-than is transitive, because
 
     (a < b) and (b < c) implies (a < c)
 
 But the word "transitive" has no meaning when applied to a unary type
 constructor like const().
 
 No, methinks the word you're looking for here is RECURSIVE. Const in D
 is recursive, not transitive.
 
 Should we change all the documention, or is this some new definition
 of "transitive" which is in common use in some field of which I am
 unaware?

If we had an operator for "contains" or "is accessible from", and an operator for const, I'd say "is accessible from" is transitive and const is distributive.
Apr 04 2008
prev sibling next sibling parent Jesse Phillips <jessekphillips gmail.com> writes:
On Fri, 04 Apr 2008 10:23:01 +0100, Janice Caron wrote:

 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?
 
 The word "transitive" applies to binary relations, like less-than. A
 relation R is transitive if
 
     (a R b) and (b R c) implies (a R c)
 
 For example, less-than is transitive, because
 
     (a < b) and (b < c) implies (a < c)
 
 But the word "transitive" has no meaning when applied to a unary type
 constructor like const().
 
 No, methinks the word you're looking for here is RECURSIVE. Const in D
 is recursive, not transitive.
 
 Should we change all the documention, or is this some new definition of
 "transitive" which is in common use in some field of which I am unaware?

Except when you look at the definition of transitive in the dictionary, "having or containing an object required to complete the meaning." Thus if we have a transitive const then all things inside it must also be const. I see no reason to make changes.
Apr 04 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 04/04/2008, Jesse Phillips <jessekphillips gmail.com> wrote:
 Except when you look at the definition of transitive in the dictionary,
  "having or containing an object required to complete the meaning." Thus
  if we have a transitive const then all things inside it must also be
  const.

What dictionary are you reading? It doesn't say that in Chambers or Merriam-Websters. M-W says 1 : characterized by having or containing a direct object <a transitive verb> <a transitive construction> 2 : being or relating to a relation with the property that if the relation holds between a first element and a second and between the second element and a third, it holds between the first and third elements <equality is a transitive relation> 3 : of, relating to, or characterized by transition
 I see no reason to make changes.

Given that transitive isn't a keyword, there are no changes to make. (I was just being nitpicky.) That said, I do suspect that using odd words in discussion or articles or whatever doesn't help lessen confusion.
Apr 04 2008
prev sibling next sibling parent guslay <guslay gmail.com> writes:
Janice Caron Wrote:

 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?
 
 But the word "transitive" has no meaning when applied to a unary type
 constructor like const().
 
 No, methinks the word you're looking for here is RECURSIVE. Const in D
 is recursive, not transitive.
 
 Should we change all the documention, or is this some new definition
 of "transitive" which is in common use in some field of which I am
 unaware?

You are correct. Recursive (but recursive is already full of meaning) or chaining would be better words for something that "brings the const along"... But I think the concept mainly need clarification, not a different name. I could not find a comprehensive definition. I think it would be helpful, as it is a key concept. Here is my attempt. I discern three parts: syntax, data, function. - If I am not mistaken, I've seen the term used to qualify how the syntax works. const(int*)** p; By the transitivity rule, this syntax defines a const pointer to a const pointer to an int pointer. - One part of it is purely data centric. A const pointer can point to a const data or a mutable data, but offers only a read-only view of it. For those who still want to fight about it, you could not mutate a mutable class members trough a const pointer (this is not where mutable breaks transitivity), as who could not mutate a global state. - But what is const transitivity when calling a const function? I would say that there is currently no such thing as const function transitivity. The only thing that would fit the concept is pure function. Because a const function provides sufficient indirection to mutate some states, the concept of transitivity seems to lose its meaning when applied to a function. "Logical const breaks transitivity." I cannot say that I agree. Logical const might break /something/. It might impede pure and functional programming, depending on how strong your assumptions are about FP (unshameful self-reference: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=69141 sorry for the grammar), but it does not break transitivity. This part needs clarification.
Apr 04 2008
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Janice Caron wrote:
 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?

No, it is used in this sense in academic papers on the subject.
Apr 04 2008
parent reply BCS <BCS pathlink.com> writes:
Walter Bright wrote:
 Janice Caron wrote:
 
 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?

No, it is used in this sense in academic papers on the subject.

That might not answer the question. One question that should be asked (but it might be to late to ask) is; is transitive the word that /should/ be used? Note that this is distinct from the question of transitive being the world that /is/ used.
Apr 04 2008
next sibling parent Walter Bright <newshound1 digitalmars.com> writes:
BCS wrote:
 Walter Bright wrote:
 Janice Caron wrote:

 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?

No, it is used in this sense in academic papers on the subject.

That might not answer the question. One question that should be asked (but it might be to late to ask) is; is transitive the word that /should/ be used? Note that this is distinct from the question of transitive being the world that /is/ used.

We should only invent new jargon if we're forced to. I don't see any compelling reason not to use transitive in the same form that academics use it to write papers about.
Apr 04 2008
prev sibling parent JMNorris <nospam nospam.com> writes:
BCS <BCS pathlink.com> wrote in news:ft5pqk$eam$5 digitalmars.com:

 Walter Bright wrote:
 Janice Caron wrote:
 
 Sorry to go all grammar/mathematics nit-picky, but isn't
 "transitive" completely the wrong word?

No, it is used in this sense in academic papers on the subject.

That might not answer the question.

To a perhaps surprising degree, that actually does answer the question. The Holy Roman Empire was neither holy nor Roman nor an empire--but was, for all of that, the Holy Roman Empire. If Twinkies can count as food, then a recursive const can surely count as transitive if enough people call it transitive. :-) -- JMNorris
Apr 04 2008
prev sibling next sibling parent Brad Roberts <braddr puremagic.com> writes:
On Fri, 4 Apr 2008, Walter Bright wrote:

 BCS wrote:
 Walter Bright wrote:
 Janice Caron wrote:
 
 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?

No, it is used in this sense in academic papers on the subject.

That might not answer the question. One question that should be asked (but it might be to late to ask) is; is transitive the word that /should/ be used? Note that this is distinct from the question of transitive being the world that /is/ used.

We should only invent new jargon if we're forced to. I don't see any compelling reason not to use transitive in the same form that academics use it to write papers about.

The term 'transitive' comes from the term 'transitive closure' used in graphs. Data structures form a graph and so the term transitive applies quite well. Later, Brad
Apr 04 2008
prev sibling next sibling parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Janice Caron wrote:

 The word "transitive" applies to binary relations

From the article on const: "Const being transitive in D means that every reference reachable through the const is also const." This is clearly expressing a binary relation. -manfred
Apr 04 2008
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Janice Caron wrote:

 So the relation is

y is reachable from x (through a series of pointers for example) Reachable is transitive: if z is reachable from y and y is reachable from x then z is reachable from x In D the transitivity of reachability carries over to const: if x is const and z is reachable from x then z is const -manfred
Apr 04 2008
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Janice Caron wrote:

   if x is const
  and z is reachable from x

  then

     z is const

My apologies for being thick, but I still don't get it. What /exactly/ is the binary relation R, such that: (1) (a R b) and (b R c) implies (a R c), is true in D (2) (a R b) and (b R c) implies (a R c), is false in C++ I still can't figure that out. Am I just missing something obvious?

a R b =(def) if a is const and b is reachable from a then b is const Counter example in C++: int* const pY; // constant pointer to changeable int *pY = 4; // legal - can use pY to modify an int pY = &someOtherIntVar; // illegal - can't make pY point anywhere else [cited from: http://www.possibility.com/Cpp/const.html] -manfred
Apr 05 2008
parent reply Manfred Nowak <svv1999 hotmail.com> writes:
Janice Caron wrote:

 STATEMENT 2:
 const is transitive in D, but not in C++.
 In what sense is statement 2 equivalent to statement 1?

The clause "with respect to reachability" is conviniently omitted, because it should be clear from the context. -manfred
Apr 05 2008
next sibling parent reply Jeff Nowakowski <jeff dilacero.org> writes:
Janice Caron wrote:
 
 So, we're all clear, right? Everyone understands why we say "const is
 transitive", not "const is recursive"?

I'd be interested in your definition of "recursive", given at the same level of detail with which you examined "transitive". I'd think you'd find you're saying exactly the same thing. Transitivity is recursive in nature. -Jeff
Apr 05 2008
parent reply Jeff Nowakowski <jeff dilacero.org> writes:
Janice Caron wrote:
 Now, the way I see it, const() is a function. It's a function which
 takes a type as its input, and returns a type as its output. According
 accu-functional.pdf, const() is defined by four rules (numbered 0 to
 3). Rule 1 says:
 
 Rule 1: If T.field has type U, then const(T).field has type const(U)
 
 That, to me, looks like a classic example of a recursive definition.

Ok, you've changed my mind. Saying "const is transitive" is sloppy, even though it's easy to see how that phrase could come about and it's intuitive to me -- since const(T) is riding on the transitive nature of data accessibility. Walter has said academics papers validate his usage. Maybe he can cite a source? I've looked around and haven't found any examples where "x is transitive" and x is a non-binary relation. -Jeff
Apr 06 2008
parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Jeff Nowakowski wrote:
 
 Walter has said academics papers validate his usage.  Maybe he can cite 
 a source?  I've looked around and haven't found any examples where "x is 
 transitive" and x is a non-binary relation.
 
 -Jeff

http://groups.csail.mit.edu/pag/pubs/tschantz-refimmut-mengthesis.pdf "Transitive - Provide transitive (deep) immutability that protects the entire abstract state of an object." (PS: I wish I had an euro every time I posted the Javari paper during the const discussion...) -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Apr 10 2008
next sibling parent Jeff Nowakowski <jeff dilacero.org> writes:
Bruno Medeiros wrote:
 
 http://groups.csail.mit.edu/pag/pubs/tschantz-refimmut-mengthesis.pdf
 "Transitive - Provide transitive (deep) immutability that protects the 
 entire abstract state of an object."

Thanks for the reference. I'm looking forward to reading the paper. As I said, I found the "transitive" term intuitive. Maybe this satisfies Janice?
 (PS: I wish I had an euro every time I posted the Javari paper during 
 the const discussion...)

I'm sure many things have been repeated in the const discussions :) Sometimes it takes a few times to get through. -Jeff
Apr 10 2008
prev sibling parent Leandro Lucarella <llucax gmail.com> writes:
Bruno Medeiros, el 10 de abril a las 21:12 me escribiste:
 Jeff Nowakowski wrote:
Walter has said academics papers validate his usage.  Maybe he can cite a
source?  I've 
looked around and haven't found any examples where "x is transitive" and x is a 
non-binary relation.
-Jeff

http://groups.csail.mit.edu/pag/pubs/tschantz-refimmut-mengthesis.pdf "Transitive - Provide transitive (deep) immutability that protects the entire abstract state of an object."

This will put again in the table the flame about const vs readonly =P -- Leandro Lucarella (luca) | Blog colectivo: http://www.mazziblog.com.ar/blog/ ---------------------------------------------------------------------------- GPG Key: 5F5A8D05 (F8CD F9A7 BF00 5431 4145 104C 949E BFB6 5F5A 8D05) ---------------------------------------------------------------------------- Pity's very underrated. I like pity. It's good. -- George Constanza
Apr 11 2008
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
Janice Caron wrote:
 
 Aha - so
 
 (1) "const" is short for "const with respect to reachability", and
 
 (2) "const with respect to reachability" actually means "(a is const)
 and (b is reachable from a) implies (b is const)".
 
 So, when we say "const is transitive", what we /in fact/ mean is:
 
 ((a is const) and (b is reachable from a) implies (b is const)) and
 ((b is const) and (c is reachable from b) implies (c is const))
 implies ((a is const) and (c is reachable from a) implies (c is
 const))
 
 Now why didn't I see that before? It's just so blindingly obvious!
 (The sarcasm wasn't aimed at you, by the way. Thanks for explaining).
 
 So, we're all clear, right? Everyone understands why we say "const is
 transitive", not "const is recursive"?

You say "It's just so blindingly obvious!" with sarcasm, as if it isn't obvious? Well, I *do* think all of the above is indeed obvious. (or at least "clear"). In fact, saying "const is transitive" is clearer to me than saying "const is recursive". You seem to think "transitive" is something that is said only of binary relationships. But another common usage is saying a given property is transitive, which is taken to mean that that property applies to all "objects" reachable from the original "object". Brad Roberts said it best, so I'll just quote him: "The term 'transitive' comes from the term 'transitive closure' used in graphs. Data structures form a graph and so the term transitive applies quite well." -- Bruno Medeiros - MSc in CS/E student http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Apr 10 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 04/04/2008, Manfred Nowak <svv1999 hotmail.com> wrote:
 Janice Caron wrote:

  > The word "transitive" applies to binary relations


 From the article on const:
  "Const being transitive in D means that every reference reachable
  through the const is also const."

  This is clearly expressing a binary relation.

So the relation is (a is const and b is const and a is reachable from b)? Correct me if I'm wrong, but isn't it also true that in C++, (a is const and b is const and b is reachable from a) and (b is const and c is const and c is reachable from b) implies (a is const and c is const and c is reachable from a) ? That would be a transitive binary relation, no? What am I missing?
Apr 04 2008
prev sibling next sibling parent Jesse Phillips <jessekphillips gmail.com> writes:
On Fri, 04 Apr 2008 16:57:43 +0100, Janice Caron wrote:

 On 04/04/2008, Jesse Phillips <jessekphillips gmail.com> wrote:
 Except when you look at the definition of transitive in the dictionary,
  "having or containing an object required to complete the meaning."
  Thus if we have a transitive const then all things inside it must also
  be const.

What dictionary are you reading? It doesn't say that in Chambers or Merriam-Websters. M-W says 1 : characterized by having or containing a direct object <a transitive verb> <a transitive construction> 2 : being or relating to a relation with the property that if the relation holds between a first element and a second and between the second element and a third, it holds between the first and third elements <equality is a transitive relation> 3 : of, relating to, or characterized by transition
 I see no reason to make changes.

Given that transitive isn't a keyword, there are no changes to make. (I was just being nitpicky.) That said, I do suspect that using odd words in discussion or articles or whatever doesn't help lessen confusion.

Well, I got it out of my Merriam-Websters and I don't think anyone is really mixing up the meaning of transitive with respect to D. But anyway it seams to have brought out a good idea, and I'm interested to see Walters input on it.
Apr 04 2008
prev sibling next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 04/04/2008, Manfred Nowak <svv1999 hotmail.com> wrote:
 Janice Caron wrote:

  > So the relation is
  [...]

  y is reachable from x (through a series of pointers for example)


  Reachable is transitive:

   if z is reachable from y
  and y is reachable from x

  then

     z is reachable from x


  In D the transitivity of reachability carries over to const:

   if x is const
  and z is reachable from x

  then

     z is const

My apologies for being thick, but I still don't get it. What /exactly/ is the binary relation R, such that: (1) (a R b) and (b R c) implies (a R c), is true in D (2) (a R b) and (b R c) implies (a R c), is false in C++ I still can't figure that out. Am I just missing something obvious? And even assuming there is such an R, wouldn't it make more sense to say "R is transitive", rather than "const is transtive"? Help me - I'm confused.
Apr 05 2008
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
"Janice Caron" wrote
 On 04/04/2008, Manfred Nowak wrote:
 Janice Caron wrote:

  > So the relation is
  [...]

  y is reachable from x (through a series of pointers for example)


  Reachable is transitive:

   if z is reachable from y
  and y is reachable from x

  then

     z is reachable from x


  In D the transitivity of reachability carries over to const:

   if x is const
  and z is reachable from x

  then

     z is const

My apologies for being thick, but I still don't get it. What /exactly/ is the binary relation R, such that: (1) (a R b) and (b R c) implies (a R c), is true in D (2) (a R b) and (b R c) implies (a R c), is false in C++ I still can't figure that out. Am I just missing something obvious? And even assuming there is such an R, wouldn't it make more sense to say "R is transitive", rather than "const is transtive"? Help me - I'm confused.

If c contains b, and b contains a, then the R becomes "is made const by" So you have: if(a is made const by b) and (b is made const by c) then (a is made const by c) True in D, false in C++. -Steve
Apr 05 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 05/04/2008, Manfred Nowak <svv1999 hotmail.com> wrote:
 a R b
  =(def)
  if a is const and b is reachable from a
  then b is const

Got it. It took me a while to prove it, but the relation you cite is indeed transitive in D, but not in C++. So, it is correct to say: STATEMENT 1: The relation "(a is const) and (b is reachable from a) => (b is const)" is transitive in D, but not in C++. However, I still dispute that it is correct to say: STATEMENT 2: const is transitive in D, but not in C++. In what sense is statement 2 equivalent to statement 1? The way I see it, statement 2 cannot be true, since "const" is not a relation.
Apr 05 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 05/04/2008, Manfred Nowak <svv1999 hotmail.com> wrote:
 Janice Caron wrote:

  > STATEMENT 2:
  > const is transitive in D, but not in C++.
  > In what sense is statement 2 equivalent to statement 1?

 The clause "with respect to reachability" is conviniently omitted,
  because it should be clear from the context.

Aha - so (1) "const" is short for "const with respect to reachability", and (2) "const with respect to reachability" actually means "(a is const) and (b is reachable from a) implies (b is const)". So, when we say "const is transitive", what we /in fact/ mean is: ((a is const) and (b is reachable from a) implies (b is const)) and ((b is const) and (c is reachable from b) implies (c is const)) implies ((a is const) and (c is reachable from a) implies (c is const)) Now why didn't I see that before? It's just so blindingly obvious! (The sarcasm wasn't aimed at you, by the way. Thanks for explaining). So, we're all clear, right? Everyone understands why we say "const is transitive", not "const is recursive"?
Apr 05 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 06/04/2008, Jeff Nowakowski <jeff dilacero.org> wrote:
  I'd be interested in your definition of "recursive", given at the same
 level of detail with which you examined "transitive".

Wikipedia defines recursion as follows: Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. Further down the page, it tells us: Functional recursion - A function may be partly defined in terms of itself. A familiar example is the Fibonacci number sequence: F(n) = F(n − 1) + F(n − 2). For such a definition to be useful, it must lead to values which are non-recursively defined, in this case F(0) = 0 and F(1) = 1. Now, the way I see it, const() is a function. It's a function which takes a type as its input, and returns a type as its output. According accu-functional.pdf, const() is defined by four rules (numbered 0 to 3). Rule 1 says: Rule 1: If T.field has type U, then const(T).field has type const(U) That, to me, looks like a classic example of a recursive definition.
 I'd think you'd find
 you're saying exactly the same thing.  Transitivity is recursive in nature.

Are you sure about that? In what way is "less than" recursive? "Less than" is certainly transitive, by definition (if (a < b), and (b < c), then it must be true that (a < c)). However, you'd be hard pressed to claim that "less-than" was "recursive". It's not defined in terms of itself. If I recall correctly, (a < b) is defined to be true if and only if there exists a positive number c such that a + c = b. That is a surely a non-recursive definition? The transitivity of "less than" is merely an emergent property, a /consequence/ of that definition. No recursion involved.
Apr 06 2008
prev sibling parent "Scott S. McCoy" <tag cpan.org> writes:
On Fri, 2008-04-04 at 11:17 -0700, Walter Bright wrote:
 BCS wrote:
 Walter Bright wrote:
 Janice Caron wrote:

 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
 completely the wrong word?

No, it is used in this sense in academic papers on the subject.

That might not answer the question. One question that should be asked (but it might be to late to ask) is; is transitive the word that /should/ be used? Note that this is distinct from the question of transitive being the world that /is/ used.

We should only invent new jargon if we're forced to. I don't see any compelling reason not to use transitive in the same form that academics use it to write papers about.

It's dubious, but not "wrong". given const(int) a; and a is typeof(b) and b is typeof(c) then c is const(int). This is generally true with all type classes and other attributes of a type system, with the exception of storage classes such as static, final, and const. Transitive const would imply that const storage class is now transitive, where previously only the type was transitive. Naturally, this has another implication of making const an attribute of the value, as opposed to an attribute of the identifier, which interestingly subsequently enough revokes it's previous definition of being a storage class. This means const is no longer a storage class, but an attribute of the value type. That is, const(int) is not the value type int with the storage class const. const is now an attribute of the value type system and int is no longer the type of a int marked "const", it's now simply const(int). It might be possible that it could be demoted into an int by copy-on-reference, or promoted into an invariant(int). It might also be that const(int) is a descendant of int. But const(int) is now the type. Naturally this opens the door for other terms which could be used to define the concept: the const value type attribute. Or, const as a part of the value type system, or whatever. So now that we're all talking about this, how about normalizing the syntax of const? private const int foo; The above example is inconsistent for a number of reasons. The first, that const is listed as a storage class as opposed to an attribute of the value type. And again it's inconsistent in a context I previously brought up: private const int foo; public const const(int) bar () { return foo; } In the above example, the behavior of the keyword "const" is relatively schizophrenic. const is listed as a part of the storage class for foo, and then as an access qualifier for bar(), with the same syntax. It would seem more consistent with the essence of const if const was always an attribute of the type, when associated with a value. private const(int) foo; This would also mean that: private const int foo; could maintain it's previous definition, which is a part of what's making people so frustrated about const. Since const is listed in the storage-class part of the declaration, const as a storage class could be possible. Alternatively, const as a storage class could be a syntax error. Cheerio, Scott S. McCoy
Apr 06 2008