May 29, 2012
On Tuesday, 29 May 2012 at 17:35:12 UTC, Michel Fortin wrote:
> On 2012-05-29 15:09:00 +0000, Artur Skawina <art.08.09@gmail.com> said:
>
>>   int a[1024];
>>   int[] da = a[0..1024];
>> 
>>   if (whatever)
>>      da = da[3..14];
>>   if (something_else)
>>      da = [42] ~ da;
>>   // etc
>> 
>>   if (da_is_a_slice_of_a())
>>      still_inside_a();
>> 
>> How do you implement da_is_a_slice_of_a()?
>
> Indeed, for that to work you'd still need to handle this case specially. My bad for not catching that.
>
> Personally, I think it'd be much cleaner to go with some kind of magic function than trying to match the condition against a predefined pattern. Something like da.isSliceOf(a), which could do the usual pointer thing at runtime and call some sort of CTFE intrinsic at compile-time.

it would be elegant to reuse 'in', but is it too error-prone?

int[10] tmp;
int*    ptr = &tmp[4];

if(ptr in tmp) // O(1), i.e. ok.
{
}

May 29, 2012
On 5/29/2012 6:29 AM, Don Clugston wrote:
> I think that's a no-go.
> Implementation-specific behaviour at runtime is bad enough, but at compile time,
> it's truly horrible. Consider that any change to unrelated code can change the
> results. Something that makes it really terrible is that the same function can
> be called in CTFE once before inlining, and once after. Good luck tracking that
> down.
> And at runtime, you have a debugger.

True, but when code relies on undefined behavior, behavior may also differ based on compiler settings, link order, compilation order, etc.

Also, note that CTFE can compute different floating point results at compile time than at runtime (because CTFE uses 80 bits for everything, even floats).

The solution is to eliminate all undefined behavior, but we can't do that and still have a systems programming language.
May 29, 2012
On 5/29/2012 7:20 AM, Michel Fortin wrote:
> Wouldn't it be possible to just catch the case where you compare two pointers
> not assigned from the same memory block and issue an error?
>
> Here's an idea: make each CTFE pointer some kind of struct with a pointer to the
> memory block and an offset. When comparing, if the memory block isn't the same,
> it's an error. If you add or subtract to a pointer, it'll still belong to the
> same memory block but with a different offset, thus it remains comparable. When
> dereferencing, you can make sure the pointer still points inside the block,
> assuming the block knows its length.


That was my suggestion a few posts back in the thread, and Don correctly demolished it.

May 29, 2012
Just a general note: going the "make a special case for two comparisons" route won't work if, for example, someone decides to use a lambda for comparing pointers.
May 30, 2012
On 29/05/12 16:20, Michel Fortin wrote:
> On 2012-05-29 13:29:35 +0000, Don Clugston <dac@nospam.com> said:
>
>> On 27/05/12 02:45, Walter Bright wrote:
>>> You could implement it as simply comparing the addresses - you'd be no
>>> worse off than C is, and you would get the correct answer for pointers
>>> both in and out of the array without needing special cases.
>>
>> I think that's a no-go.
>> Implementation-specific behaviour at runtime is bad enough, but at
>> compile time, it's truly horrible. Consider that any change to
>> unrelated code can change the results. Something that makes it really
>> terrible is that the same function can be called in CTFE once before
>> inlining, and once after. Good luck tracking that down.
>> And at runtime, you have a debugger.
>
> Wouldn't it be possible to just catch the case where you compare two
> pointers not assigned from the same memory block and issue an error?
>
> Here's an idea: make each CTFE pointer some kind of struct with a
> pointer to the memory block and an offset. When comparing, if the memory
> block isn't the same, it's an error. If you add or subtract to a
> pointer, it'll still belong to the same memory block but with a
> different offset, thus it remains comparable. When dereferencing, you
> can make sure the pointer still points inside the block, assuming the
> block knows its length.

Thats _exactly_ what it does right now.
May 30, 2012
On 30/05/12 01:47, Mehrdad wrote:
> Just a general note: going the "make a special case for two comparisons"
> route won't work if, for example, someone decides to use a lambda for
> comparing pointers.

You mean effectively like:

bool cmp(void *x, void *y)
{
   return x < y:
}

assert ( cmp(x, y) && cmp(x, z) );

?
Yes, this is why it's a special case.


I can imagine how that could be implemented in the current CTFE, I cannot see how it could be done reasonably with a JIT CTFE implementation.

You'd have to have a special lamba for "pointer inside a range" rather than simple pointer comparisons.

I'm suggesting that "is pointer inside a range" is a different primitive operation from "comparison of two pointers to the same memory block".

Even though C code typically uses the latter to implement the former, it's relying on undefined behaviour.
May 30, 2012
On Tue, 29 May 2012 13:35:12 -0400, Michel Fortin <michel.fortin@michelf.com> wrote:

> On 2012-05-29 15:09:00 +0000, Artur Skawina <art.08.09@gmail.com> said:
>
>>    int a[1024];
>>    int[] da = a[0..1024];
>>     if (whatever)
>>       da = da[3..14];
>>    if (something_else)
>>       da = [42] ~ da;
>>    // etc
>>     if (da_is_a_slice_of_a())
>>       still_inside_a();
>>  How do you implement da_is_a_slice_of_a()?
>
> Indeed, for that to work you'd still need to handle this case specially. My bad for not catching that.
>
> Personally, I think it'd be much cleaner to go with some kind of magic function than trying to match the condition against a predefined pattern. Something like da.isSliceOf(a), which could do the usual pointer thing at runtime and call some sort of CTFE intrinsic at compile-time.

That doesn't help when most code does not use this today.  I.e. one of the main benefits of ctfe is that you don't *have* to write special code.

-Steve
May 30, 2012
On 2012-05-30 14:44:37 +0000, "Steven Schveighoffer" <schveiguy@yahoo.com> said:

> On Tue, 29 May 2012 13:35:12 -0400, Michel Fortin  <michel.fortin@michelf.com> wrote:
> 
>> Personally, I think it'd be much cleaner to go with some kind of magic  function than trying to match the condition against a predefined  pattern. Something like da.isSliceOf(a), which could do the usual  pointer thing at runtime and call some sort of CTFE intrinsic at  compile-time.
> 
> That doesn't help when most code does not use this today.  I.e. one of the  main benefits of ctfe is that you don't *have* to write special code.

But at the other end, there should be an easy to understand separation between what is supported by CTFE and what is not. Once you try to add special cases for some code patterns by adding heuristics, those heuristics now define the line and would have to become part of the language specification.

More generally, the drawback of this kind of pattern recognition is that there's an infinite pool of equivalent patterns to recognize, and seemingly innocuous changes to a CTFEable function could break its CTFEablility if they happen to cross the invisible boundary.

I'm just trying to point out the drawbacks of too clever heuristics. If such an heuristic is used, I think it should be limited in scope and well documented. Unfortunately, that means you'll still have to care about writing code in a way that fits the documented pattern. It'd be much easier to reason about CTFEability if the pattern had to be encapsulated in its own function.

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

May 30, 2012
On Wed, 30 May 2012 11:33:54 -0400, Michel Fortin <michel.fortin@michelf.com> wrote:

> On 2012-05-30 14:44:37 +0000, "Steven Schveighoffer" <schveiguy@yahoo.com> said:
>
>> On Tue, 29 May 2012 13:35:12 -0400, Michel Fortin  <michel.fortin@michelf.com> wrote:
>>
>>> Personally, I think it'd be much cleaner to go with some kind of magic  function than trying to match the condition against a predefined  pattern. Something like da.isSliceOf(a), which could do the usual  pointer thing at runtime and call some sort of CTFE intrinsic at  compile-time.
>>  That doesn't help when most code does not use this today.  I.e. one of the  main benefits of ctfe is that you don't *have* to write special code.
>
> But at the other end, there should be an easy to understand separation between what is supported by CTFE and what is not. Once you try to add special cases for some code patterns by adding heuristics, those heuristics now define the line and would have to become part of the language specification.
>
> More generally, the drawback of this kind of pattern recognition is that there's an infinite pool of equivalent patterns to recognize, and seemingly innocuous changes to a CTFEable function could break its CTFEablility if they happen to cross the invisible boundary.
>
> I'm just trying to point out the drawbacks of too clever heuristics. If such an heuristic is used, I think it should be limited in scope and well documented. Unfortunately, that means you'll still have to care about writing code in a way that fits the documented pattern. It'd be much easier to reason about CTFEability if the pattern had to be encapsulated in its own function.

Unless of course, you simply always allow it, which is what I think we should do :)

-Steve
May 31, 2012
On 30/05/12 17:33, Michel Fortin wrote:
> On 2012-05-30 14:44:37 +0000, "Steven Schveighoffer"
> <schveiguy@yahoo.com> said:
>
>> On Tue, 29 May 2012 13:35:12 -0400, Michel Fortin
>> <michel.fortin@michelf.com> wrote:
>>
>>> Personally, I think it'd be much cleaner to go with some kind of
>>> magic function than trying to match the condition against a
>>> predefined pattern. Something like da.isSliceOf(a), which could do
>>> the usual pointer thing at runtime and call some sort of CTFE
>>> intrinsic at compile-time.
>>
>> That doesn't help when most code does not use this today. I.e. one of
>> the main benefits of ctfe is that you don't *have* to write special code.
>
> But at the other end, there should be an easy to understand separation
> between what is supported by CTFE and what is not. Once you try to add
> special cases for some code patterns by adding heuristics, those
> heuristics now define the line and would have to become part of the
> language specification.
>
> More generally, the drawback of this kind of pattern recognition is that
> there's an infinite pool of equivalent patterns to recognize, and
> seemingly innocuous changes to a CTFEable function could break its
> CTFEablility if they happen to cross the invisible boundary.
>
> I'm just trying to point out the drawbacks of too clever heuristics. If
> such an heuristic is used, I think it should be limited in scope and
> well documented. Unfortunately, that means you'll still have to care
> about writing code in a way that fits the documented pattern. It'd be
> much easier to reason about CTFEability if the pattern had to be
> encapsulated in its own function.


The heuristic is:  one pointer comparison in each direction, connected by && or ||. No restriction on the pointer expressions, except that they must have no side-effects.

That covers most legitimate cases.
The ones it doesn't cover are:
- doing two interleaved isInside() comparisons:

p1 >= q1 && s1 >= r1 && p2 < q2 && s2 < r2
which needs to be rewritten as:
(p1 >= q1 && p2 < q2) && (s1 >= r1 && s2 < r2)

- saving two one-side compares, and then not using them for _anything_ except an && or ||
---> this is a fundamental limitation

- calling two functions which each return a one-side-compare:
bool cmp(void *a, void *b) { return a<b);
cmp(p1, q1) && cmp(q2, p2)

----> this one could actually be done, because it would only be legal to call such a function from an && or ||. Implementation would be complicated though.
Next ›   Last »
1 2 3
Top | Discussion index | About this forum | D home