Le 23/05/2012 15:52, Steven Schveighoffer a écrit :
> 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

It is up to the GC to collect memory when it is tight. This operation isn't and shouldn't be pure.

It can eventually be called within the allocation mecanism.

On Wed, 23 May 2012 09:52:31 -0400, deadalnix <deadalnix@gmail.com> wrote:

> Le 23/05/2012 14:35, Steven Schveighoffer a écrit :
>> 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'm failing to see an argument in this response.  If I can call an impure function for allocating memory, why is it illegal to call an impure function for collecting unused memory?

-Steve

On 23-05-2012 15:55, deadalnix wrote:
> 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.

The runtime is a bit of a special case in the first place. It's an extremely low-level component of the language.

Mind you, I'm not saying there isn't room for improvement in our type system!

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

On Wed, 23 May 2012 09:56:58 -0400, deadalnix <deadalnix@gmail.com> wrote:

> Le 23/05/2012 15:52, Steven Schveighoffer a écrit :
>> 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
>
> It is up to the GC to collect memory when it is tight. This operation isn't and shouldn't be pure.
>
> It can eventually be called within the allocation mecanism.

Don has said that any collection cycle triggered by a pure function should not touch the main heap, only memory allocated from within this function (or 'pure function' stack I guess).

This means that a strong-pure function could throw an OutOfMemoryError, whereas a non-pure one would run fine.

I'm with Alex on this, this situation is not tenable.

-Steve

Le 23/05/2012 15:57, Steven Schveighoffer a écrit :
> On Wed, 23 May 2012 09:52:31 -0400, deadalnix <deadalnix@gmail.com> wrote:
>
>> Le 23/05/2012 14:35, Steven Schveighoffer a écrit :
>>> 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'm failing to see an argument in this response. If I can call an impure
> function for allocating memory, why is it illegal to call an impure
> function for collecting unused memory?
>
> -Steve

Allocating is a much more simpler operation than collect, and its impact is way more reduced.

Plus, allocating memory is something mandatory to do anything non trivial. GC collect isn't that important, as it can be triggered by allocating mecanism itself (and this mecanism is already impure).

If you do allow everything impure to be done on pure function based on the fact that allocating is impure, what is the point to have pure function at all ?

On 23-05-2012 16:03, deadalnix wrote:
> Le 23/05/2012 15:57, Steven Schveighoffer a écrit :
>> On Wed, 23 May 2012 09:52:31 -0400, deadalnix <deadalnix@gmail.com>
>> wrote:
>>
>>> Le 23/05/2012 14:35, Steven Schveighoffer a écrit :
>>>> 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'm failing to see an argument in this response. If I can call an impure
>> function for allocating memory, why is it illegal to call an impure
>> function for collecting unused memory?
>>
>> -Steve
>
> Allocating is a much more simpler operation than collect, and its impact
> is way more reduced.

Yes, but allocation implies possible collection!

>
> Plus, allocating memory is something mandatory to do anything non
> trivial. GC collect isn't that important, as it can be triggered by
> allocating mecanism itself (and this mecanism is already impure).
>
> If you do allow everything impure to be done on pure function based on
> the fact that allocating is impure, what is the point to have pure
> function at all ?

The point is *real world practicality*. You need to be able to use the core.memory API in pure functions to do anything memory-heavy.

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

On Wed, 23 May 2012 10:03:01 -0400, deadalnix <deadalnix@gmail.com> wrote:

> Le 23/05/2012 15:57, Steven Schveighoffer a écrit :
>> On Wed, 23 May 2012 09:52:31 -0400, deadalnix <deadalnix@gmail.com> wrote:
>>
>>> Le 23/05/2012 14:35, Steven Schveighoffer a écrit :
>>>> 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'm failing to see an argument in this response. If I can call an impure
>> function for allocating memory, why is it illegal to call an impure
>> function for collecting unused memory?
>>
>> -Steve
>
> Allocating is a much more simpler operation than collect, and its impact is way more reduced.

Huh?  Allocation *does* a collect!  How can it be "simpler"?

> If you do allow everything impure to be done on pure function based on the fact that allocating is impure, what is the point to have pure function at all ?

Memory collection is hardly "everything."  We are looking at the few exceptions needed to make the system usable.

-Steve

Le 23/05/2012 16:03, deadalnix a écrit :
> Le 23/05/2012 15:57, Steven Schveighoffer a écrit :
>> On Wed, 23 May 2012 09:52:31 -0400, deadalnix <deadalnix@gmail.com>
>> wrote:
>>
>>> Le 23/05/2012 14:35, Steven Schveighoffer a écrit :
>>>> 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'm failing to see an argument in this response. If I can call an impure
>> function for allocating memory, why is it illegal to call an impure
>> function for collecting unused memory?
>>
>> -Steve
>
> Allocating is a much more simpler operation than collect, and its impact
> is way more reduced.
>
> Plus, allocating memory is something mandatory to do anything non
> trivial. GC collect isn't that important, as it can be triggered by
> allocating mecanism itself (and this mecanism is already impure).
>
> If you do allow everything impure to be done on pure function based on
> the fact that allocating is impure, what is the point to have pure
> function at all ?

You'll find a different between :

pure void foo() {
   new Stuff(); // May collect
}

and

pure void foo() {
    gc.collect();
}

The second one is obviously not pure. And the first one need a hook to an allocating function in druntime, function which isn't pure, but made look like a pure one, and that is able to call impure gc.collect .

gc.collect is a system wide procedure that involve all thread runniong in your application and every single piece of memory in it. This is probable the most far away from pure function I can think of.

On 23-05-2012 16:42, deadalnix wrote:
> Le 23/05/2012 16:03, deadalnix a écrit :
>> Le 23/05/2012 15:57, Steven Schveighoffer a écrit :
>>> On Wed, 23 May 2012 09:52:31 -0400, deadalnix <deadalnix@gmail.com>
>>> wrote:
>>>
>>>> Le 23/05/2012 14:35, Steven Schveighoffer a écrit :
>>>>> 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'm failing to see an argument in this response. If I can call an impure
>>> function for allocating memory, why is it illegal to call an impure
>>> function for collecting unused memory?
>>>
>>> -Steve
>>
>> Allocating is a much more simpler operation than collect, and its impact
>> is way more reduced.
>>
>> Plus, allocating memory is something mandatory to do anything non
>> trivial. GC collect isn't that important, as it can be triggered by
>> allocating mecanism itself (and this mecanism is already impure).
>>
>> If you do allow everything impure to be done on pure function based on
>> the fact that allocating is impure, what is the point to have pure
>> function at all ?
>
> You'll find a different between :
>
> pure void foo() {
> new Stuff(); // May collect
> }
>
> and
>
> pure void foo() {
> gc.collect();
> }
>
> The second one is obviously not pure. And the first one need a hook to
> an allocating function in druntime, function which isn't pure, but made
> look like a pure one, and that is able to call impure gc.collect .
>
> gc.collect is a system wide procedure that involve all thread runniong
> in your application and every single piece of memory in it. This is
> probable the most far away from pure function I can think of.

You're still just lying to yourself by thinking that a GC allocation is strictly pure. I understand that there is a difference between implicit and explicit collection, but it boils down to the same thing. D is a systems language, and a pragmatic language. We're not Haskell. Let's be practical.

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

On 23/05/12 15:56, Alex Rønne Petersen wrote:
> 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.

No, it's not realistic for every function. But it's extremely easy for others. In particular, if you have a pure function which has no reference parameters, you just need a pointer to the last point a strongly pure function was entered. This partitions the heap into two parts. Each can be gc'd independently.

And, in the non-pure part, nothing is happening. Once you've done a GC there, you NEVER need to do it again.

> 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.

Not so. It's impossible for anything outside of a strongly pure function to hold a pointer to memory allocated by the pure function.
In my view, this is the single most interesting feature of purity.

> 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.

Of course. But I don't see how that's relevant. How the pure function actually obtains its memory is an implementation detail.

There's a huge difference between "a global collection *may* be performed from a pure function" vs "it *must* be possible to force a global collection from a pure function".

The difficulty in expressing the latter is a simple consequence of the fact that it is intrinsically impure.