View mode: basic / threaded / horizontal-split · Log in · Help
May 29, 2012
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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
Re: Pointer semantics in CTFE
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