Re: choice of character for relational division

From: Bob Badour <bbadour_at_pei.sympatico.ca>
Date: Mon, 02 Apr 2007 13:34:16 GMT
Message-ID: <sD7Qh.18463$PV3.191339@ursa-nb00s0.nbnet.nb.ca>

Marshall wrote:

> On Mar 31, 11:04 pm, Gene Wirchenko <g..._at_ocis.net> wrote:
>

>>"Marshall" <marshall.spi..._at_gmail.com> wrote:
>>
>>[snip]
>>
>>
>>>So, if you had to choose an ascii character for
>>>relational division, which one would you use
>>>and why?
>>
>>    I would not do so unless the meaning was fairly obvious, and it
>>did not horribly overload the character.

>
>
> It's hard to come up with something that's obvious for relational
> division, since it's such an infrequently used operation. However
> there is certainly the issue of *not* picking something that is
> familiarly associated with some other operation, such as the
> sad case of using << to mean "write to a stream." The overloading
> issue is certainly important, though.
>
>
>

>>Instead, I would pick a
>>three-or-so-letter name.  ("mod" is used by some.  ALGOL used "DIV"
>>and "REM".)

>
>
> Yeah, I'm starting to see the value. One issue is that I think
> it makes sense to use the same charset for both join, union,
> and their inverses. (I.e., you wouldn't want a language to
> use "+" and "minus" for addition and subtraction.) Since I'm
> having relation join, union be the same thing as boolean and,
> or, so it's not clear which one to pick. If I used join/union,
> then the inverses would be divide/minus I suppose, but
> then that would look weird with booleans. If I use and/or,
> then what are the inverses?
>
>
>

>>     "|" is used a lot in one of my computing science classes.  "|x|"
>>can mean the absolute value of x, or the size of x.  "x|y" means that
>>x divides evenly into y.  "|" is also used something like "such that",
>>as in {x | x>0}.  I do not like this overloading.

>
>
> It's a design issue. There is a balance to be struck. On the one
> hand, attempting to completely avoid any overloading of any
> character is going to lead to something that is wildly verbose,
> and probably not very readable. On the other hand too much
> overloading and programs start to look like line noise, and
> again readability suffers.
>
> Using |x| doesn't seem like a great choice to me because
> we already have abs(x) which is hardly any longer and
> much more obvious. (And to many programmers, familiar.)
>
> Using | as the "divides" operator is probably quite familiar
> to math students, and if you're studying prime numbers for
> example, divisibility is likely to be something you're talking
> about a lot. It also figures in to the Fundamental Theorem
> of Arithmetic. But it's not much use in programming.
>
> On the other hand, | to mean "such that" is set theory
> and set builder notation is awesome.
>
> /: (a, b | b != 0)
>
> "division is a function that has parameters a and b where
> b is not zero." Can't beat that.
>
> For a long time I was playing with a variation of set
> builder notation for a programming notation. (You can
> see similar things in list comprehensions in languages
> like Clean.) Ultimately I dropped it because I found
> better ways to accomplish the same thing, but it was
> pretty compact and readable.

I actually like set builder notation a lot for relations.

Compare the statement above to "division, '/', is a relation among attributes quotient, dividend and divisor where divisor is not zero". Except, for completeness one needs to include the domains of everything:

/: (quo, dend, sor |

	quo in Q, dend in I, sor in I
	, sor != 0, dend = sor * quo

)

(I used quo for QUOtient, dend for diviDEND and sor for diviSOR.)

A similar (slightly more D'ish) alternative might be: /: {{quo in Q, dend in I, sor in I} | sor != 0, dend = quo * sor}

How do we decide what appears after the '|' ? For example, if we have a relation for the square root of integers, do we use:

sqrt: {{root in R, n in I} | n >= 0}

or do we use:

sqrt: {{root in R, n in W}} ?

(Some prefer N_0 for 'naturals including zero' over W for 'whole numbers'; substitute N_0 for W above if you prefer.)

Specialization by constraint would make both expressions equivalent. Which would we consider canonical?

We can use the above notation to express important invariants too:

*: {{ prod in I, cand in I, er in I} |

	cand != 0 or prod = 0, er != 0 or prod = 0
	, cand != 1 or prod = er, er != 1 or prod = cand
	, exists({prod'=prod,cand'=er,er'=cand} in *)
	, prod = SIGMA^er_1 cand
	, prod = SIGMA^cand_1 er

}

(I used prod for PRODuct, cand for multipliCAND and er for multipliER.)

What then is the most effective way to express 'SIGMA' as a fold of '+'? And 'PI' as a fold of '*' ?

Is the 'exists' constraint above the best way to express commutativity? What about associativity and distributivitiy?

Do the 'better ways' you have found obviate the above questions? I am very interested to hear what you think those better ways are and how they improve the situation. Received on Mon Apr 02 2007 - 08:34:16 CDT