I've had a talk with Walter today, and two interesting things transpired.

First off, Walter pointed out that I was wrong about one conversion rule (google value preservation vs. type preservation). It turns out that everything that's unsigned and less than int is actually converted to int, NOT unsigned int as I thought. This is the case in C, C++, and D.

Second, as of today Walter devised a very crude heuristic for typechecking narrowing conversions:

(a) a straight assignment x = y fails if y is wider than x.

(b) however, x = e compiles for more complex expressions EVEN if there is potential for loss of precision.

Now enter polysemy. With that, we can get the right rules in place and minimize false positives. An expression will yield a polysemous value with the as-C-does-it type as its principal type. The secondary type is a carefully computed narrower type that is the tightest actual type.

If you just say auto or use the value with overloaded functions etc., it's just like in C - the as-in-C type will be in vigor. But if you specifically ask for a narrower type, the secondary type enters in effect.

Examples:

uint u1 = ...;
ushort us1 = ...;
auto a = u1 & us1; // fine, a is uint
ushort b = u1 & us1; // fine too, secondary type kicks in

long l1 = ...;
auto c = u1 / l1; // c is long
int d = u1 / l1; // fine too, secondary type kicks in

We need to think this through for complex expressions etc. Walter and I are quite excited that this will take care of a significant portion of the integral conversions mess (in addition to handling literals, constants, and variables within a unified framework).

The plan is to deploy polysemous integrals first without changing the rest of the conversion rules. At that point, if the technique turns out to enjoy considerable success, Walter agreed to review and possibly stage in the change I suggested to drop the implicit signed -> unsigned conversion. With that, I guess we can claim victory in the war between spurious vs. too lax conversions.

I'm very excited about polysemy. It's entirely original to D, covers a class of problems that can't be addressed with any of the known techniques (subtyping, coercion...) and has a kick-ass name to boot. Walter today mentioned he's still not sure I hadn't made "polysemy" up. Indeed, Thunderbird and Firefox are suggesting it's a typo - please "add to dictionary" :o).


Andrei

On 2008-11-28 19:08:06 -0500, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> said:

> Walter today mentioned he's still not sure I hadn't made "polysemy" up. Indeed, Thunderbird and Firefox are suggesting it's a typo - please "add to dictionary" :o).

Does this help?

polysemy
noun Linguistics
the coexistence of many possible meanings for a word or phrase.

-- New Oxford American Dictionary, 2nd Edition

polysemy
n : the ambiguity of an individual word or phrase that can be used (in different contexts) to express two or more different meanings [syn: lexical ambiguity] [ant: monosemy]

-- WordNet <http://wordnet.princeton.edu/perl/webwn?s=polysemy>

-- 
Michel Fortin
michel.fortin@michelf.com
http://michelf.com/

On Fri, 28 Nov 2008 16:08:06 -0800, Andrei Alexandrescu <SeeWebsiteForEmail@erdani.org> wrote:

>I've had a talk with Walter today, and two interesting things transpired.
>
>First off, Walter pointed out that I was wrong about one conversion rule (google value preservation vs. type preservation). It turns out that everything that's unsigned and less than int is actually converted to int, NOT unsigned int as I thought. This is the case in C, C++, and D.
>
>Second, as of today Walter devised a very crude heuristic for typechecking narrowing conversions:
>
>(a) a straight assignment x = y fails if y is wider than x.
>
>(b) however, x = e compiles for more complex expressions EVEN if there is potential for loss of precision.
>
>Now enter polysemy. With that, we can get the right rules in place and minimize false positives. An expression will yield a polysemous value with the as-C-does-it type as its principal type. The secondary type is a carefully computed narrower type that is the tightest actual type.
>
>If you just say auto or use the value with overloaded functions etc., it's just like in C - the as-in-C type will be in vigor. But if you specifically ask for a narrower type, the secondary type enters in effect.
>
>Examples:
>
>uint u1 = ...;
>ushort us1 = ...;
>auto a = u1 & us1; // fine, a is uint
>ushort b = u1 & us1; // fine too, secondary type kicks in
>
>long l1 = ...;
>auto c = u1 / l1; // c is long
>int d = u1 / l1; // fine too, secondary type kicks in
>
>We need to think this through for complex expressions etc. Walter and I are quite excited that this will take care of a significant portion of the integral conversions mess (in addition to handling literals, constants, and variables within a unified framework).
>
>The plan is to deploy polysemous integrals first without changing the rest of the conversion rules. At that point, if the technique turns out to enjoy considerable success, Walter agreed to review and possibly stage in the change I suggested to drop the implicit signed -> unsigned conversion. With that, I guess we can claim victory in the war between spurious vs. too lax conversions.
>
>I'm very excited about polysemy. It's entirely original to D, covers a class of problems that can't be addressed with any of the known techniques (subtyping, coercion...) and has a kick-ass name to boot. Walter today mentioned he's still not sure I hadn't made "polysemy" up. Indeed, Thunderbird and Firefox are suggesting it's a typo - please "add to dictionary" :o).
>

I think it's a very relevant term. Given that type of a value attaches a meaning to that value, values getting different types (meanings) depending on the context are polysemous. Very cool.

>
>Andrei

Andrei Alexandrescu wrote:
> I've had a talk with Walter today, and two interesting things transpired.
> 
> First off, Walter pointed out that I was wrong about one conversion rule (google value preservation vs. type preservation). It turns out that everything that's unsigned and less than int is actually converted to int, NOT unsigned int as I thought. This is the case in C, C++, and D.

That has some interesting consequences.

  ushort x = 0xFFFF;
  short y = x;
  printf("%d %d %d\n", x>>1, y>>1, y>>>1);

// prints: 32767 -1 2147483647

What a curious beast the >>> operator is!

> I'm very excited about polysemy. It's entirely original to D, covers a class of problems that can't be addressed with any of the known techniques (subtyping, coercion...) and has a kick-ass name to boot. 

I agree. By making the type system looser in the one place where you actually need it to be loose, you can tighten it everywhere else. Fantastic.

Andrei Alexandrescu wrote:
> I'm very excited about polysemy. It's entirely original to D,

I accused Andrei of making up the word 'polysemy', but it turns out it is a real word! <g>

Don wrote:
> Andrei Alexandrescu wrote:
>> I've had a talk with Walter today, and two interesting things transpired.
>>
>> First off, Walter pointed out that I was wrong about one conversion rule (google value preservation vs. type preservation). It turns out that everything that's unsigned and less than int is actually converted to int, NOT unsigned int as I thought. This is the case in C, C++, and D.
> 
> That has some interesting consequences.
> 
>   ushort x = 0xFFFF;
>   short y = x;
>   printf("%d %d %d\n", x>>1, y>>1, y>>>1);
> 
> // prints: 32767 -1 2147483647
> 
> What a curious beast the >>> operator is!
> 
>> I'm very excited about polysemy. It's entirely original to D, covers a class of problems that can't be addressed with any of the known techniques (subtyping, coercion...) and has a kick-ass name to boot. 
> 
> I agree. By making the type system looser in the one place where you actually need it to be loose, you can tighten it everywhere else. Fantastic.

My enthusiasm about polysemy got quite a bit lower when I realized that the promises of polysemy for integral operations can be provided (and actually outdone) by range analysis, a well-known method.

The way it's done: for each integral expression in the program assign two numbers: the smallest possible value, and the largest possible value. Literals will therefore have a salami-slice-thin range associated with them. Whenever code asks for a lossy implicit cast, check the range and if it fits within the target type, let the code go through.

Each operation computes its ranges from the range of its operands. The computation is operation-specific. For example, the range of a & b is max(a.range.min, b.range.min) to min(a.range.max, b.range.max). Sign considerations complicate this a bit, but not quite much.

The precision of range analysis can be quite impressive, for example:

uint b = ...;
ubyte a = ((b & 2) << 6) | (b >> 24);

typechecks no problem because it can prove no loss of information for all values of b.


Andrei

On 2008-12-01 21:16:58 +0100, Walter Bright <newshound1@digitalmars.com> said:

> Andrei Alexandrescu wrote:
>> I'm very excited about polysemy. It's entirely original to D,
> 
> I accused Andrei of making up the word 'polysemy', but it turns out it is a real word! <g>

Is this the beginning of discriminating overloads also based on the return values?

Fawzi

Fawzi Mohamed wrote:
> On 2008-12-01 21:16:58 +0100, Walter Bright <newshound1@digitalmars.com> said:
> 
>> Andrei Alexandrescu wrote:
>>> I'm very excited about polysemy. It's entirely original to D,
>>
>> I accused Andrei of making up the word 'polysemy', but it turns out it is a real word! <g>
> 
> Is this the beginning of discriminating overloads also based on the return values?

No. I think return type overloading looks good in trivial cases, but as things get more complex it gets inscrutable.

On Mon, 1 Dec 2008, Andrei Alexandrescu wrote:

> My enthusiasm about polysemy got quite a bit lower when I realized that the promises of polysemy for integral operations can be provided (and actually outdone) by range analysis, a well-known method.
> 
> The way it's done: for each integral expression in the program assign two numbers: the smallest possible value, and the largest possible value. Literals will therefore have a salami-slice-thin range associated with them. Whenever code asks for a lossy implicit cast, check the range and if it fits within the target type, let the code go through.
> 
> Each operation computes its ranges from the range of its operands. The computation is operation-specific. For example, the range of a & b is max(a.range.min, b.range.min) to min(a.range.max, b.range.max). Sign considerations complicate this a bit, but not quite much.
> 
> The precision of range analysis can be quite impressive, for example:
> 
> uint b = ...;
> ubyte a = ((b & 2) << 6) | (b >> 24);
> 
> typechecks no problem because it can prove no loss of information for all values of b.
> 
> 
> Andrei

The term I see associated with this technique, indeed well known, is Value Range Propagation.  Combine this sort of accumulated knowledge with loop and if condition analysis as well as inlining, and often a signivicant amount of dead code elimination can occur.

Later,
Brad

Walter Bright Wrote:

> Andrei Alexandrescu wrote:
> > I'm very excited about polysemy. It's entirely original to D,
> 
> I accused Andrei of making up the word 'polysemy', but it turns out it is a real word! <g>

Did Andrei also make up this word? http://www.worldwidewords.org/weirdwords/ww-pop3.htm