Re: Proposal: 6NF

From: vc <boston103_at_hotmail.com>
Date: 20 Oct 2006 13:52:13 -0700
Message-ID: <1161377533.035718.66910@m73g2000cwd.googlegroups.com>

Marshall wrote:
> On Oct 20, 3:12 am, "vc" <boston..._at_hotmail.com> wrote:
> > Marshall wrote:
> > > On Oct 19, 8:40 pm, "vc" <boston..._at_hotmail.com> wrote:
> > > > Marshall wrote:
> >
> > > > > > "return new ModFour((val+a.val)%4)" is called a bug or cheating
> > > > > > because you used a function defined on the entire domain NxN (where N
> > > > > > is a subset of the natural numbers implemented by the computer) to
> > > > > > generate a result which is undefined for the (2,3) pair.
> >
> > > > > It's not a bug, since the program produces the correct result, which is
> > > > > 1. It's not "cheating" because WTF does cheating even mean in
> > > > > this context. What it is, is the absence of closure over the subclass.
> > > > > Which is no big deal.
> >
> > > > So producing an absurd result is no big deal ? You seem to have agreed
> > > > that in the {2,3} subset there is no '1', how come your java
> > > > implementation manages to extract '1' out of nowhere ?
> >
> > > Consider the below function:
> >
> > > Let S4 = {0, 1, 2, 3}
> > > Let S23 = {2, 3}
> > > f : S23, S23 -> S4
> >
> > The binary operation over S23 is g:S23:S23 -> S23, your f does not
> > qualify. A common example is '+'.
> >
> >
> > > f(2,2) = 0
> > > f(2,3) = 1
> > > f(3,2) = 1
> > > f(3,3) = 2
> >
> > > Your claim is what, exactly? That this is not a function? That
> > > it doesn't exist? That it's cheating? That it's invalidly defined
> > > because the result type is not the same as the types of
> > > both parameters?
> > It's not a binary opeartion that we've been talking about all along.
> > Did you read the reference I gave earlier or not ?

>

> So we agree that my f does not meet the definition of binary operation.
>

OK.

> Do we also agree that:

>


> 1) f is a function

> 2) f exists
> 3) f is well-defined
> ?

>

Yes.

> Apparently you also think that f is "absurd." Can we take
> as a definition of "absurd" to be any function that is not of
> the type g:A,A->A? Because it seems to me that there
> are many such functions.

No, we can take as absurd the contention that addMod4 is a binary operation over {2,3 } yielding 1.

>
>


> > > > > > At thispoint,   it may be useful to recall what a function is and

> > > > > > apply the memory,  if any,  to the addMod4 operation.

> >

> > > > > Indeed. A function is a mapping from one set to another.

> > > > > In this case, the domain is pairs of values from {0,1,2,3}

> > > > > and the range is that same set. This particular

> > > > > function qualifies as a binary function, and also

> > > > > exhibits closure over the set {0,1,2,3}. Since {2,3} is a

> > > > > subset of {0,1,2,3}, the function is fully defined over

> > > > > that subset. However, since that function is not closed

> >

> > > > How can it be 'fully defined' over {2,3} and 'not closed' at the same

> > > > time ?  What  does  (2,3) map to ? If you say to one,  then you

> > > > exctract '1' out of nowhere again.

> >

> > > I don't understand this "out of nowhere" business. It's just

> > > a plain, regular number one. Nothing could be simpler.

> >
> > Where is '1' in {2,3} ?

>

> It's not there, but so what? There's no sqrt(2) in there either;
> does that mean the sqrt function is absurd? Or am I simply
> not allowed to take the square root of values in {2,3}?
> What requires me to have *every* function have {2,3} as
> its range?

Your desire for any such function to be an operation over the set in question.

>

> You ask "How can it be 'fully defined' over {2,3} and 'not closed'
> at the same time ?" It appears that you believe that for
> a function to be fully defined, it has to have its return type
> the same as its two argument types.

Your imagination is playing tricks on you -- I never said that, it was not 'a function', but the specific addMod4 operation (which happens to be a special kind of function of course). For that operation the pair ((2,3), ..) does not exist which clearly means that the operation is not defined for this element of S23xS23.

>Is closure required

> for a function to be defined? We agree that closure is
> required to meet the definition of "binary operation" but
> I'm asking about the more general definition of "function."
> (I claim that to qualify as a function something has to
> be well-defined.)

It would probably be prudent to ask at this point what you mean by "to qualify as a function something has to be well-defined", but t's a nice diversion that has nothing to do with the binary operation inheritance discussion. In any case, you can easily find out that a fucntion is defined as a relation, mathematical, of course such that it uniquely associates elements of one set with elements of some other set, or possibly the same set.

>
>


> > > > > > > The *only* trouble anywhere in here is if you want to

> > > > > > > have methods which are mutator methods; that is,

> > > > > > > methods which modify the distinguished object in place.

> > > > > > > And yes, in that case, closure is an issue. I have not

> > > > > > > seen any math books that give functions the same

> > > > > > > semantics as inherited OOPL mutator methods however.

> >

> > > > > I note you did not respond to this important paragraph. Yes,

> > > > > in OOPLs, there is a problem with closure, subtyping,

> > > > > and mutator methods. Outside of OOPLs (in math, that

> > > > > is) this problem does not apply.

> >

> > > > We may tackle those issues later after we come to some agreement re.

> > > > the trivial stuff like functions and binary operations.

> >

> > > Okay. What is your definition of a function, then, and how

> > > does my f above stack up with regards to your

> > > definition?

> > Your 'f' has nothing to do with the whole discussion of 'inheriting'
> > a binary operation from a type.

>
> Why doesn't it?

Because your function ain't a binary operation derivable from the supertype operation (see the definition of waht the operation is). You've defined something different which is structurally different from the supertype operation.

>I already showed an example of working Java

> code in which a function is defined over pairs of ints mod 4,
> and that function is *inherited,* in the literal concrete Java Language
> Spec sense, by a subclass consisting of only the values {2, 3}.

The specifc implementation is irrelevant, you might as well have just used System.out.println(1). What is important is the fact that the base type has a binary operation and the derived type does not have it any more, instead you implemented a function which I hope by now is clearly a different animal altogether.

>

> Now, you called that "cheating" but I haven't heard your
> definition of cheating yet, so I'm unclear as to how to
> respond. I don't recall the word "cheating" being used
> in the JLS.

See above re. the S23xS23 -> S0123 function vs. the S0123xS0123 -> S0123 operation.

>

> Again, the only problem here is your assertion that
> sets are inextricably bound to functions defined
> over them, in some OOPL (but not very mathematical)
> sense.

Again, the above is pure fantasy of yours, I never said that. The operations, on the other hand, are "inextricably bound to", or rather are properties, of some familiar sets such as the set of natural numbers with addition (or successor). Without the successor/addition operation, calling the thing 'natural numbers' is as absurd as calling addMod4 an operation over {2, 3}.

>The algebra books I have read (admitedly few

> in number) have always made a clear distinction
> between a set and algebraic structures that include
> a set with binary operations defined over the set.

>

> I bet there's a relevant wikipedia article. Let's keep
> it simple:

>

> http://en.wikipedia.org/wiki/Monoid

>

> "A monoid is a set M with binary operation ∗ : M × M → M,
> obeying the following axioms: [associativity, identity]"

>

> Here, an algebraic structure is defined as a tuple consisting
> of a set and a binary operation. It's not just the set itself;
> it can't be. This example is particularly telling to me, because
> we can immediately see that Z participates in (at least) two
> monoids: (Z, +) and (Z, *). So if I say "the monoid Z" I'm
> being appallingly imprecise; I *cannot* assume an implicit
> relationship between the set and its operations. While
> the definition of +:Z,Z->Z depends on the definition of Z,
> it is entirely *distinct* from it; the relation + is a set, and
> Z is a set, and they are two distinct sets; + is not an element
> of Z.

It does not matter whether you consider, for example, the natural numbers as a primitive abstract objects with some intrinsic operations or an algebraic structure satisfying the commutative monoid axioms. In any interpretations, you will lose the addition operation when you move to the subset of odd numbers for instance. That's not what an OOP programmer would expect, the expectation being that the new structure should have more, not fewer properties, or in other words the (N, +) monoid should not disintegrate as a result of such subtyping.

Besides, you got it backwards, algebraic axioms capture and generalize some interesting properties of existing mathematical objects such as the natural numbers, the axioms do not 'define' a structure that is *the* natural numbers. Much less do they give one a license to throw away existing mathematical object properties, where did that come from ?

Example :

class Natural {
  Rational '+' { .. return .. }
}

class oddNatural extends Natural {
...
 }

• Assuming the language implements covariance (as Java 5 does):

o, x =3, y =5 oddNatural;
n Natural;
...

o = x + y; -- makes sense

z = x + y; -- does not make sense mathematically but is something the programmer would expect

If the language does not support covariance, then it will mangle the binary operation '+' in the second case into a function oddNaturalxoddNatural -> Natural

Now, I must retract my statement that the LSP will be violated with subset subtyping, my apologies to Jan and you for saying that . The LSP will not be violated with covariance, but the artificial '+' will be nonsensical. The LSP won't be violated in the first case either at least superficially, although the interpretation depends on whether you consider converting an operation to a function acceptable behavior.  I do not consider either acceptable because of getting unexpected properties in both cases.

>
>


> > > > > > > Also, I found this equation in a math book on page 3:

> >

> > > > > > >   P ⊆ N ⊆ Z ⊆ Q ⊆ R

> >

> > > > > > The equation looks like a random collection of characters.   What do

> > > > > > you suppose it means ?

> >

> > > > > I suppose your browser doesn't have the necessary font.

> >

> > > > > In prose, it means:

> >

> > > > >   The set of positive integers is a subset of the set of nonnegative

> > > > >   integers which is a subset of the integers which is a subset

> > > > >   of the rationals which is a subset of the reals.

> >

> > > > That's truly a trivial observation which is not strictly speaking

> > > > correct (see the earlier discussion re. real construction).

> >

> > > Wait, you're saying it's both trivial *and* incorrect? Earlier

> > > I recall you suggesting various people consult math books

> > > for such questions; I did consult one and it was quite clear

> > > on the question: every integer is also a real.

> > I guess you need another book because integers as commonly constructed

> > are not a subset of reals but rather are isomorphic to some subset of

> > reals. In cases when the subtlety is unimportant, one can say that
> > the integers are a subset of real, we discussed that before.

>

> You're very hung up on the construction issue; it's not the only
> way of thinking about this. I agree that we can validly take
> that viewpoint; I also agree that we can take a type-theoretic
> approach and reach the same conclusion that 2 and 2.0 are
> not the same number. Those are valid conclusions when
> embedded within the appropriate theoretical framework.
> There also exist (fairly simple) set-theoretic frameworks
> under which 2 and 2.0 *are* the same number,

Although that is correct up to a point, what framework do you have in mind ?

>and that

> is equally a valid conclusion when embedded within the
> appropriate theoretical framework.

If they are embedded, you cannot technically say one is a subset of another, but it does not matter.

>

> This isn't Highlander; it's not the case that "there can
> be only one!"
>
>
> Marshall
Received on Fri Oct 20 2006 - 15:52:13 CDT