Re: choice of character for relational division
Date: Mon, 02 Apr 2007 13:34:16 GMT
Message-ID: <sD7Qh.18463$PV3.191339_at_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 - 15:34:16 CEST