On 23-05-2012 14:21, deadalnix wrote:
> Le 23/05/2012 05:22, Steven Schveighoffer a écrit :
>> I have come across a dilemma.
>>
>> Alex Rønne Petersen has a pull request changing some things in the GC to
>> pure. I think gc_collect() should be weak-pure, because it could
>> technically run on any memory allocation (which is already allowed in
>> pure functions), and it runs in a context that doesn't really affect
>> execution of the pure function.
>>
>> So I think it should be able to be run inside a strong pure function.
>> But because it has no parameters and no return, marking it as pure makes
>> it strong pure, and an optimizing compiler can effectively remove the
>> call completely!
>>
>> So how do we force something to be weak-pure? What I want is:
>>
>> 1. it can be called from a pure function
>> 2. it will not be optimized out in any way.
>>
>> This solution looks crappy to me:
>>
>> void gc_collect(void *unused = null);
>>
>> any other ideas?
>>
>> -Steve
>
> Why a pure function can call a collection cycle ???? This is an impure
> operation by essence.
>
> I think what is need here is to break the type system to allow call of
> impure function into a pure one.

I think you're missing an amusing point:

class C { this() pure {} }

C foo() pure
{
    return new C(); // can trigger a collection!
}

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org

On Wed, 23 May 2012 08:21:42 -0400, deadalnix <deadalnix@gmail.com> wrote:

> Le 23/05/2012 05:22, Steven Schveighoffer a écrit :
>> I have come across a dilemma.
>>
>> Alex Rønne Petersen has a pull request changing some things in the GC to
>> pure. I think gc_collect() should be weak-pure, because it could
>> technically run on any memory allocation (which is already allowed in
>> pure functions), and it runs in a context that doesn't really affect
>> execution of the pure function.
>>
>> So I think it should be able to be run inside a strong pure function.
>> But because it has no parameters and no return, marking it as pure makes
>> it strong pure, and an optimizing compiler can effectively remove the
>> call completely!
>>
>> So how do we force something to be weak-pure? What I want is:
>>
>> 1. it can be called from a pure function
>> 2. it will not be optimized out in any way.
>>
>> This solution looks crappy to me:
>>
>> void gc_collect(void *unused = null);
>>
>> any other ideas?
>>
>> -Steve
>
> Why a pure function can call a collection cycle ???? This is an impure operation by essence.

Yes.  Memory allocation and deallocation from a global heap is by definition an impure operation (it affects global state).  However, we must make exceptions because without being able to allocate memory, pure functions become quite trivial and useless.

In functional languages, if such exceptions were not granted, a program would not be able to do much of anything.

> I think what is need here is to break the type system to allow call of impure function into a pure one.

We already are breaking the type system by marking an impure function (a function whose implementation is not marked pure) pure.  This only works for extern(C) fucntions, which are not mangled with the pure attribute.

But we need to be more specific about how the compiler should treat these functions.  They need to undergo no optimization based on purity.  They simply need to be able to be called from a pure function.

-Steve

On 23/05/12 05:22, Steven Schveighoffer wrote:
> I have come across a dilemma.
>
> Alex Rønne Petersen has a pull request changing some things in the GC to
> pure. I think gc_collect() should be weak-pure, because it could
> technically run on any memory allocation (which is already allowed in
> pure functions), and it runs in a context that doesn't really affect
> execution of the pure function.
>
> So I think it should be able to be run inside a strong pure function.

I am almost certain it should not.

And I think this is quite important. A strongly pure function should be considered to have its own gc, and should not be able to collect any memory it did not allocate itself.

Memory allocation from a pure function might trigger a gc cycle, but it would ONLY look at the memory allocated inside that pure function.

Don Clugston:

> The real question being asked is, do we need something for logical purity?

You mean something like @trusted_pure?


> Note that we need the same thing for caching.

Regarding caching, memoization, weak references, and related things, I prefer a more principled approach, like the ones I've shown in some Haskell-related papers.

Bye,
bearophile

Le 23/05/2012 14:32, Alex Rønne Petersen a écrit :
> On 23-05-2012 14:21, deadalnix wrote:
>> Le 23/05/2012 05:22, Steven Schveighoffer a écrit :
>>> I have come across a dilemma.
>>>
>>> Alex Rønne Petersen has a pull request changing some things in the GC to
>>> pure. I think gc_collect() should be weak-pure, because it could
>>> technically run on any memory allocation (which is already allowed in
>>> pure functions), and it runs in a context that doesn't really affect
>>> execution of the pure function.
>>>
>>> So I think it should be able to be run inside a strong pure function.
>>> But because it has no parameters and no return, marking it as pure makes
>>> it strong pure, and an optimizing compiler can effectively remove the
>>> call completely!
>>>
>>> So how do we force something to be weak-pure? What I want is:
>>>
>>> 1. it can be called from a pure function
>>> 2. it will not be optimized out in any way.
>>>
>>> This solution looks crappy to me:
>>>
>>> void gc_collect(void *unused = null);
>>>
>>> any other ideas?
>>>
>>> -Steve
>>
>> Why a pure function can call a collection cycle ???? This is an impure
>> operation by essence.
>>
>> I think what is need here is to break the type system to allow call of
>> impure function into a pure one.
>
> I think you're missing an amusing point:
>
> class C { this() pure {} }
>
> C foo() pure
> {
> return new C(); // can trigger a collection!
> }
>

Ok, but no direct call to GC collect will be done, so the function don't need to be pure, it need to be somehow hacked into the allocation mecanism, probably using compiler magic.

So basically the allocation mecanism have to break the type system to act like it is pure, even if it isn't.

On 23-05-2012 15:46, deadalnix wrote:
> Le 23/05/2012 14:32, Alex Rønne Petersen a écrit :
>> On 23-05-2012 14:21, deadalnix wrote:
>>> Le 23/05/2012 05:22, Steven Schveighoffer a écrit :
>>>> I have come across a dilemma.
>>>>
>>>> Alex Rønne Petersen has a pull request changing some things in the
>>>> GC to
>>>> pure. I think gc_collect() should be weak-pure, because it could
>>>> technically run on any memory allocation (which is already allowed in
>>>> pure functions), and it runs in a context that doesn't really affect
>>>> execution of the pure function.
>>>>
>>>> So I think it should be able to be run inside a strong pure function.
>>>> But because it has no parameters and no return, marking it as pure
>>>> makes
>>>> it strong pure, and an optimizing compiler can effectively remove the
>>>> call completely!
>>>>
>>>> So how do we force something to be weak-pure? What I want is:
>>>>
>>>> 1. it can be called from a pure function
>>>> 2. it will not be optimized out in any way.
>>>>
>>>> This solution looks crappy to me:
>>>>
>>>> void gc_collect(void *unused = null);
>>>>
>>>> any other ideas?
>>>>
>>>> -Steve
>>>
>>> Why a pure function can call a collection cycle ???? This is an impure
>>> operation by essence.
>>>
>>> I think what is need here is to break the type system to allow call of
>>> impure function into a pure one.
>>
>> I think you're missing an amusing point:
>>
>> class C { this() pure {} }
>>
>> C foo() pure
>> {
>> return new C(); // can trigger a collection!
>> }
>>
>
> Ok, but no direct call to GC collect will be done, so the function don't
> need to be pure, it need to be somehow hacked into the allocation
> mecanism, probably using compiler magic.

Sure there'll be a direct call to that. It's effectively what the GC does when collecting.

>
> So basically the allocation mecanism have to break the type system to
> act like it is pure, even if it isn't.

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org

On Wed, 23 May 2012 09:17:43 -0400, Don Clugston <dac@nospam.com> wrote:

> On 23/05/12 05:22, Steven Schveighoffer wrote:
>> I have come across a dilemma.
>>
>> Alex Rønne Petersen has a pull request changing some things in the GC to
>> pure. I think gc_collect() should be weak-pure, because it could
>> technically run on any memory allocation (which is already allowed in
>> pure functions), and it runs in a context that doesn't really affect
>> execution of the pure function.
>>
>> So I think it should be able to be run inside a strong pure function.
>
> I am almost certain it should not.
>
> And I think this is quite important. A strongly pure function should be considered to have its own gc, and should not be able to collect any memory it did not allocate itself.

Well, given that the above is not implemented, what do you propose for the meantime?

>
> Memory allocation from a pure function might trigger a gc cycle, but it would ONLY look at the memory allocated inside that pure function.
>

What if memory is tight, and the only way to get memory for this new allocation is to collect from the main heap?  This seems an odd limitation, since strong-pure functions would not be affected by collecting in the main heap *at all*.

-Steve

Le 23/05/2012 14:35, Steven Schveighoffer a écrit :
> On Wed, 23 May 2012 08:21:42 -0400, deadalnix <deadalnix@gmail.com> wrote:
>
>> Le 23/05/2012 05:22, Steven Schveighoffer a écrit :
>>> I have come across a dilemma.
>>>
>>> Alex Rønne Petersen has a pull request changing some things in the GC to
>>> pure. I think gc_collect() should be weak-pure, because it could
>>> technically run on any memory allocation (which is already allowed in
>>> pure functions), and it runs in a context that doesn't really affect
>>> execution of the pure function.
>>>
>>> So I think it should be able to be run inside a strong pure function.
>>> But because it has no parameters and no return, marking it as pure makes
>>> it strong pure, and an optimizing compiler can effectively remove the
>>> call completely!
>>>
>>> So how do we force something to be weak-pure? What I want is:
>>>
>>> 1. it can be called from a pure function
>>> 2. it will not be optimized out in any way.
>>>
>>> This solution looks crappy to me:
>>>
>>> void gc_collect(void *unused = null);
>>>
>>> any other ideas?
>>>
>>> -Steve
>>
>> Why a pure function can call a collection cycle ???? This is an impure
>> operation by essence.
>
> Yes. Memory allocation and deallocation from a global heap is by
> definition an impure operation (it affects global state). However, we
> must make exceptions because without being able to allocate memory, pure
> functions become quite trivial and useless.
>
> In functional languages, if such exceptions were not granted, a program
> would not be able to do much of anything.
>

Yes, you are missing the point.

collect is not something you should be able to call in a pure function. It can be triggered by allocating, but at this point you already are in an impure context called from a pure context.

At the end, you need an unsafe way to call impure code in pure functions.

>> I think what is need here is to break the type system to allow call of
>> impure function into a pure one.
>
> We already are breaking the type system by marking an impure function (a
> function whose implementation is not marked pure) pure. This only works
> for extern(C) fucntions, which are not mangled with the pure attribute.
>
> But we need to be more specific about how the compiler should treat
> these functions. They need to undergo no optimization based on purity.
> They simply need to be able to be called from a pure function.
>
> -Steve

Le 23/05/2012 15:47, Alex Rønne Petersen a écrit :
> On 23-05-2012 15:46, deadalnix wrote:
>> Le 23/05/2012 14:32, Alex Rønne Petersen a écrit :
>>> On 23-05-2012 14:21, deadalnix wrote:
>>>> Le 23/05/2012 05:22, Steven Schveighoffer a écrit :
>>>>> I have come across a dilemma.
>>>>>
>>>>> Alex Rønne Petersen has a pull request changing some things in the
>>>>> GC to
>>>>> pure. I think gc_collect() should be weak-pure, because it could
>>>>> technically run on any memory allocation (which is already allowed in
>>>>> pure functions), and it runs in a context that doesn't really affect
>>>>> execution of the pure function.
>>>>>
>>>>> So I think it should be able to be run inside a strong pure function.
>>>>> But because it has no parameters and no return, marking it as pure
>>>>> makes
>>>>> it strong pure, and an optimizing compiler can effectively remove the
>>>>> call completely!
>>>>>
>>>>> So how do we force something to be weak-pure? What I want is:
>>>>>
>>>>> 1. it can be called from a pure function
>>>>> 2. it will not be optimized out in any way.
>>>>>
>>>>> This solution looks crappy to me:
>>>>>
>>>>> void gc_collect(void *unused = null);
>>>>>
>>>>> any other ideas?
>>>>>
>>>>> -Steve
>>>>
>>>> Why a pure function can call a collection cycle ???? This is an impure
>>>> operation by essence.
>>>>
>>>> I think what is need here is to break the type system to allow call of
>>>> impure function into a pure one.
>>>
>>> I think you're missing an amusing point:
>>>
>>> class C { this() pure {} }
>>>
>>> C foo() pure
>>> {
>>> return new C(); // can trigger a collection!
>>> }
>>>

Rethinking about this, it show something interesting. To make sense, allocation in pure function should either be scoped or immutable.

Otherwise we can't ensure any « strong purity » on a function that return anything that can reference something else.

>>
>> Ok, but no direct call to GC collect will be done, so the function don't
>> need to be pure, it need to be somehow hacked into the allocation
>> mecanism, probably using compiler magic.
>
> Sure there'll be a direct call to that. It's effectively what the GC
> does when collecting.
>

At this point, you are in the allocation mecanism in druntime. You are not in pure code anymore.

If it is the case, then the type system is broken at the wrong place.

On 23-05-2012 15:17, Don Clugston wrote:
> On 23/05/12 05:22, Steven Schveighoffer wrote:
>> I have come across a dilemma.
>>
>> Alex Rønne Petersen has a pull request changing some things in the GC to
>> pure. I think gc_collect() should be weak-pure, because it could
>> technically run on any memory allocation (which is already allowed in
>> pure functions), and it runs in a context that doesn't really affect
>> execution of the pure function.
>>
>> So I think it should be able to be run inside a strong pure function.
>
> I am almost certain it should not.
>
> And I think this is quite important. A strongly pure function should be
> considered to have its own gc, and should not be able to collect any
> memory it did not allocate itself.
>
> Memory allocation from a pure function might trigger a gc cycle, but it
> would ONLY look at the memory allocated inside that pure function.

Implementing this on a per-function basis is not very realistic. Some programs have hundreds (if not thousands) of pure functions.

Not to mention, we'd need some mechanism akin to critical regions to figure out when a thread is in a pure function during stop-the-world. Further, data allocated in a pure function f() in thread A must not be touched by a collection triggered by an allocation inside f() in thread B. It'd be a huge mess.

And, frankly, if my program dies from an OOME due to pure functions being unable to do full collection cycles, I'd just stop using pure permanently. It's not a very realistic approach to automatic memory management; at that point, manual memory management would work better.

-- 
Alex Rønne Petersen
alex@lycus.org
http://lycus.org