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

- Janice Caron (14/14) Apr 04 2008 Sorry to go all grammar/mathematics nit-picky, but isn't "transitive"
- Jason House (2/23) Apr 04 2008 If we had an operator for "contains" or "is accessible from", and an ope...
- Jesse Phillips (5/25) Apr 04 2008 Except when you look at the definition of transitive in the dictionary,
- Janice Caron (15/20) Apr 04 2008 What dictionary are you reading? It doesn't say that in Chambers or
- Jesse Phillips (5/31) Apr 04 2008 Well, I got it out of my Merriam-Websters and I don't think anyone is
- guslay (15/27) Apr 04 2008 You are correct. Recursive (but recursive is already full of meaning) or...
- Walter Bright (2/4) Apr 04 2008 No, it is used in this sense in academic papers on the subject.
- BCS (5/12) Apr 04 2008 That might not answer the question.
- Walter Bright (4/18) Apr 04 2008 We should only invent new jargon if we're forced to. I don't see any
- Brad Roberts (6/25) Apr 04 2008 The term 'transitive' comes from the term 'transitive closure' used in
- Scott S. McCoy (49/68) Apr 06 2008 It's dubious, but not "wrong".
- JMNorris (8/18) Apr 04 2008 To a perhaps surprising degree, that actually does answer the question.
- Manfred Nowak (6/7) Apr 04 2008 From the article on const:
- Janice Caron (8/14) Apr 04 2008 So the relation is (a is const and b is const and a is reachable from b)...
- Manfred Nowak (14/15) Apr 04 2008 [...]
- Janice Caron (9/23) Apr 05 2008 My apologies for being thick, but I still don't get it. What /exactly/
- Steven Schveighoffer (7/42) Apr 05 2008 If c contains b, and b contains a, then the R becomes "is made const by"...
- Manfred Nowak (11/26) Apr 05 2008 a R b
- Janice Caron (11/15) Apr 05 2008 Got it. It took me a while to prove it, but the relation you cite is
- Manfred Nowak (4/7) Apr 05 2008 The clause "with respect to reachability" is conviniently omitted,
- Janice Caron (14/20) Apr 05 2008 Aha - so
- Jeff Nowakowski (6/9) Apr 05 2008 I'd be interested in your definition of "recursive", given at the same
- Janice Caron (27/31) Apr 06 2008 Wikipedia defines recursion as follows:
- Jeff Nowakowski (9/17) Apr 06 2008 Ok, you've changed my mind. Saying "const is transitive" is sloppy,
- Bruno Medeiros (9/15) Apr 10 2008 http://groups.csail.mit.edu/pag/pubs/tschantz-refimmut-mengthesis.pdf
- Jeff Nowakowski (7/13) Apr 10 2008 Thanks for the reference. I'm looking forward to reading the paper. As...
- Leandro Lucarella (9/18) Apr 11 2008 This will put again in the table the flame about const vs readonly =P
- Bruno Medeiros (17/37) Apr 10 2008 You say "It's just so blindingly obvious!" with sarcasm, as if it isn't

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

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

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

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 transitionI 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

On Fri, 04 Apr 2008 16:57:43 +0100, Janice Caron wrote:On 04/04/2008, Jesse Phillips <jessekphillips gmail.com> wrote: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.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 transitionI 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

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

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

Walter Bright wrote:Janice Caron wrote: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.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

BCS wrote:Walter Bright wrote: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.Janice Caron wrote: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.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

On Fri, 4 Apr 2008, Walter Bright wrote:BCS wrote: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, BradWalter Bright wrote: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.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

On Fri, 2008-04-04 at 11:17 -0700, Walter Bright wrote:BCS wrote: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. McCoySorry 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 06 2008

BCS <BCS pathlink.com> wrote in news:ft5pqk$eam$5 digitalmars.com:Walter Bright wrote: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. :-) -- JMNorrisSorry 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

Janice Caron wrote:The word "transitive" applies to binary relationsFrom 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

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

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

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 constMy 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

"Janice Caron" wroteOn 04/04/2008, Manfred Nowak wrote: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++. -SteveJanice 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 constMy 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

Janice Caron wrote: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] -manfredif x is const and z is reachable from x then z is constMy 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?

Apr 05 2008

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 constGot 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

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

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

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

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

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

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. -Jeffhttp://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

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

Bruno Medeiros, el 10 de abril a las 21:12 me escribiste:Jeff Nowakowski wrote: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 ConstanzaWalter 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. -Jeffhttp://groups.csail.mit.edu/pag/pubs/tschantz-refimmut-mengthesis.pdf "Transitive - Provide transitive (deep) immutability that protects the entire abstract state of an object."

Apr 11 2008

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