Steven Schveighoffer:

> cast voids all warranties ;)

OK. But that idea is unchanged if you remove the cast and return an int* from that function.


> Memory allocation has to be allowed inside pure functions.  Otherwise, pure functions are too strict and limited.

I agree. But there are different ways to allocate memory, and those differences are important.


> Allowing malloc is somewhat exceptional because you then must allow free. But I see no reason (yet) to disallow free.  If free cannot be pure, then malloc cannot be pure.

I suggest to disallow both malloc/calloc and free inside pure functions, because what malloc returns a pointer, that is a value, that is not deterministic, it changes across different calls to malloc.


> Note, the 'hole' you refer to is not a bad thing.

It's a bad thing that will cause troubles to both D programmers and D compiler writers :-)


> A weakly pure function allows one to modularize pure functions, whereas prior to this, things like sort could not be pure functions, and therefore could not be used inside pure functions.  I think the hole allows pure functions to be actually usable and easy whereas before they were much too obscure to be useful in much code.

I think this is unrelated to the hole I was talking about.


> All that is required is to disallow casting.

Disallowing casting is not enough here.

I have written two more posts after that, but you may have missed them because I have broken the tread: http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=130426

Some examples:

class Foo {
  int x;
  bool opEquals(Foo o) { return x == o.x; }
}
pure Foo bar() {
  return new Foo; // OK
}
void main() {
  Foo f1 = bar(); // OK
  Foo f2 = new Foo;
  f1.x = 10; // OK
  assert(f1 != f2); // OK
  f1 = f2; // OK
  assert(f1 is f2); // no
}

Here bar() allocated memory and it's pure, this is OK. f1 is mutable. You are allowed to call opEquals. You are allowed to overwrite the reference f1. But you aren't allowed to read the reference f1, because this breaks the referential transparency of the results of pure functions.

The idea is a subtype of pointers/references, that at compile-time doesn't allow to read the value of the pointer/reference itself. I think this is able to patch the hole I was talking about (a cast is able to punch a hole again in this, of course).

Bye,
bearophile

On Wed, 23 Feb 2011 13:13:35 -0500, bearophile <bearophileHUGS@lycos.com> wrote:

> Steven Schveighoffer:
>
>> cast voids all warranties ;)
>
> OK. But that idea is unchanged if you remove the cast and return an int* from that function.

That is allowed, and it's expected that a pure function can return different references with identical calls.

Even if the return value is an immutable reference, it is allowed to return different references with identical calls.  You should never expect that a pure optimization occurs.  All you should expect is that a pure function returns the same value for identical calls.  Same value does not mean the same bits.

>> Allowing malloc is somewhat exceptional because you then must allow free.
>> But I see no reason (yet) to disallow free.  If free cannot be pure, then
>> malloc cannot be pure.
>
> I suggest to disallow both malloc/calloc and free inside pure functions, because what malloc returns a pointer, that is a value, that is not deterministic, it changes across different calls to malloc.

pure functions are not necessarily @safe functions, you can access pointers.

>> A weakly pure function
>> allows one to modularize pure functions, whereas prior to this, things
>> like sort could not be pure functions, and therefore could not be used
>> inside pure functions.  I think the hole allows pure functions to be
>> actually usable and easy whereas before they were much too obscure to be
>> useful in much code.
>
> I think this is unrelated to the hole I was talking about.

Then I don't know of the hole you mean.  Pure functions are 100% about optimization.  An optimization should *never* be assumed.  That is, given a pure function foo that returns a string, it should not be assumed that:

auto s = foo();
auto s2 = foo();

is always factored into

auto s = foo();
auto s2 = s;

It's an optimization, one which the compiler could or could not decide to use.

However, it *should* be assumed that:

assert(s == s2);

That is, the values are the same.

If you are going to use casts, then those rules are out the window.

>> All that is required is to disallow casting.
>
> Disallowing casting is not enough here.

What are your expectations for pure functions?

> I have written two more posts after that, but you may have missed them because I have broken the tread:
> http://www.digitalmars.com/webnews/newsgroups.php?art_group=digitalmars.D&article_id=130426
>
> Some examples:
>
> class Foo {
>   int x;
>   bool opEquals(Foo o) { return x == o.x; }
> }
> pure Foo bar() {
>   return new Foo; // OK
> }
> void main() {
>   Foo f1 = bar(); // OK
>   Foo f2 = new Foo;
>   f1.x = 10; // OK
>   assert(f1 != f2); // OK
>   f1 = f2; // OK
>   assert(f1 is f2); // no
> }
>
> Here bar() allocated memory and it's pure, this is OK. f1 is mutable. You are allowed to call opEquals. You are allowed to overwrite the reference f1. But you aren't allowed to read the reference f1, because this breaks the referential transparency of the results of pure functions.

There is no such guarantee for weakly-pure functions.  There's not even such a guarantee for strong-pure functions.  To guarantee this would require some sort of memoization, and require optimizations to be followed.

> The idea is a subtype of pointers/references, that at compile-time doesn't allow to read the value of the pointer/reference itself. I think this is able to patch the hole I was talking about (a cast is able to punch a hole again in this, of course).

I don't see any value in disallowing such accesses.  The expectation that two pure function calls will necessarily return the *exact* same bits when the function is returning references/pointers is incorrect.

-Steve

Steven Schveighoffer:

> That is allowed, and it's expected that a pure function can return different references with identical calls.

A pointer and a "transparent reference" are two different things. That function returns a pointer, and a pointer is a value.
If you call a pure function with the same input you need to receive the same value. Otherwise it's not pure. If you mean something else, then you have redefined the meaning of "pure" so much that the word "pure" is the wrong one to use.


> pure functions are not necessarily @safe functions, you can access pointers.

I know what I am currently able to do with pure functions in D. But here we are talking about what's the right/good way to design purity (or maybe we are even talking about what's the right way to modify D purity).

I presume you have understood what I have explained about transparent references.


> Pure functions are 100% about optimization.

Pure means first of all avoiding side effects. A pure function is not allowed to do some things, so both the programmer and the compiler are able to use such stronger constrains to perform some extra trasnformations normally not allowed on impure functions, and the resulting code is safer from certain kinds of bugs.


> An optimization should *never* be assumed.  That is, given a pure function foo that returns a string, it should not be assumed that:
> 
> auto s = foo();
> auto s2 = foo();
> 
> is always factored into
> 
> auto s = foo();
> auto s2 = s;
> 
> It's an optimization, one which the compiler could or could not decide to use.
> 
> However, it *should* be assumed that:
> 
> assert(s == s2);
> 
> That is, the values are the same.

I have suggested an extension of the type system that disallows statically code like: assert(s.ptr == s2.ptr);

because this may break the transparent nature of references coming out of pure functions.


> What are your expectations for pure functions?

Allocating memory in a pure function is so useful that I expect D pure function to allow it. On the other hand I expect pure functions to behave deterministically, same input means same output. To solve this I have suggested di disallow reading the value of references/pointers coming out of pure functions.


> There is no such guarantee for weakly-pure functions.  There's not even such a guarantee for strong-pure functions.

I know. This is something I'd like to add (well, I am not sure it's implementable, I am not sure it's a good idea, etc, so it's just an idea for now. And I don't think D will add it).


> To guarantee this would require some sort of memoization, and require optimizations to be followed.

I think no memoization is needed, I think the only change needed is on the type system (so there are no effects on runtime. This type system just disallows some programs).

I may call them @transparent pointers/references, they are a supertype of normal ones:

class Foo() {}
pure @transparent(Foo) bar() {
  return new Foo();
}
Foo bar2() { // not pure
  return new Foo();
}
void main() {
  @transparent Foo f1 = bar(); // OK
  @transparent Foo f2 = bar2(); // OK
  Foo f3 = bar(); // not allowed, Foo is a subtype of @transparent(Foo)
}


On a @transparent Foo reference you are allowed to overwrite it, modify or use anything in the class itself, but you are statically allowed to use "is" operator on it, because it breaks its transparency (if you cast it to a pointer or not transparent, then you punch a hole in this type part of the type system).

Something similar is acceptable for struct pointers too, and arrays:

struct Spam() {}
@transparent Spam* bar3() {
  return new Spam();
}

struct Spam() {}
@transparent int[] bar4() {
  return new int[10];
}

Bye,
bearophile

On Wed, 23 Feb 2011 14:31:35 -0500, bearophile <bearophileHUGS@lycos.com> wrote:

> Steven Schveighoffer:
>
>> That is allowed, and it's expected that a pure function can return
>> different references with identical calls.
>
> A pointer and a "transparent reference" are two different things. That function returns a pointer, and a pointer is a value.
> If you call a pure function with the same input you need to receive the same value. Otherwise it's not pure. If you mean something else, then you have redefined the meaning of "pure" so much that the word "pure" is the wrong one to use.

A pointer is not a value, it's a pointer.  int is a value.  You should expect two calls to a pure function to return the same exact int.

Because memory allocation has side effects, you have to accept that it can allow pure functions to not return exactly the same bits.  That is the price of allowing memory allocations.

D is a language that allows pointers and comparison of pointers.  There are plenty of languages that don't allow this (such as Java), one of those might be better suited for your requirements.

I see zero value in disallowing comparing pointers in D.  What kinds of problems does pointer comparison cause?  I know of none.  Showing an assert that two pointers are not equal is not evidence of an error, it's evidence of incorrect expectations.

-Steve

Steven Schveighoffer:

> A pointer is not a value, it's a pointer.  int is a value.  You should expect two calls to a pure function to return the same exact int.

I don't care of how you want to define what a pointer is. Definitions are labels for ideas, you are free to use a different label.


> Because memory allocation has side effects, you have to accept that it can allow pure functions to not return exactly the same bits.

I have suggested a way to avoid most of problems caused by that fact.


> D is a language that allows pointers and comparison of pointers.  There are plenty of languages that don't allow this (such as Java), one of those might be better suited for your requirements.

Java too allows to compare the value of references (like the "is" D operator) so the type system idea I have suggested is applicable in Java too, if Java wants to add pure functions that allow allocations.


> I see zero value in disallowing comparing pointers in D.

I have not suggested to disallow comparing all pointers. I have suggested to disallow it only for pointers/references allocated inside a pure function, that are @transparent.


> What kinds of problems does pointer comparison cause?  I know of none.

If you compare pointers created in a pure function, you are breaking the most important constraint of pure functions. A pure function is deterministic. D pure function aren't deterministic, because the value of the memory pointers they return can be different across different calls. If you leave this hole in pure functions, then their purity is much less useful, you can't perform optimizations, you can't reason about code like you are able to do with pure functions.

Currently you are able to write functions like:

pure bool randomPure() {
    int[] a1 = new int[1];
    int[] a2 = new int[2];
    return a1.ptr > a2.ptr;
}

Is this function pure? It returns a pseudo-random boolean. You are free to define this function as pure, but this form of purity is much less strong than what people think of "pure".

With the type system change I have prosed it becomes:

pure bool randomPure() {
    @transparent int[] a1 = new int[1];
    @transparent int[] a2 = new int[2];
    return a1.ptr > a2.ptr; // compile-time error, their ptr are @transparent, so they can't be read
}


> Showing an assert that two pointers are not equal is not evidence of an error, it's evidence of incorrect expectations.

One of the main purposes of a type system is indeed to disallow programs based on incorrect expectations, to help programmers that may not always remeber what the incorrect expectations are :-)

Bye,
bearophile

On Wed, 23 Feb 2011 15:28:32 -0500, bearophile <bearophileHUGS@lycos.com> wrote:

> Steven Schveighoffer:
>
>> I see zero value in disallowing comparing pointers in D.
>
> I have not suggested to disallow comparing all pointers. I have suggested to disallow it only for pointers/references allocated inside a pure function, that are @transparent.

That's not what your example showed.  It showed comparing two allocated pointers *outside* a pure function, and expected them to be equal.  I see that as disallowing all pointer comparisons.

>> What kinds of problems does pointer comparison cause?  I know of none.
>
> If you compare pointers created in a pure function, you are breaking the most important constraint of pure functions. A pure function is deterministic. D pure function aren't deterministic, because the value of the memory pointers they return can be different across different calls. If you leave this hole in pure functions, then their purity is much less useful, you can't perform optimizations, you can't reason about code like you are able to do with pure functions.
>
> Currently you are able to write functions like:
>
> pure bool randomPure() {
>     int[] a1 = new int[1];
>     int[] a2 = new int[2];
>     return a1.ptr > a2.ptr;
> }

This is the first real example you have made that shows a problem!  It uses all valid constructs within pure functions (without casts), and by current rules could be considered strong-pure, however, it violates the rule of pure that the same parameters should result in the same answer.

> Is this function pure? It returns a pseudo-random boolean. You are free to define this function as pure, but this form of purity is much less strong than what people think of "pure".

I would not define the function as pure.  The questions to answer are:

1. Can the compiler detect valid reference comparisons without annotation?
2. Is this going to be a common problem?

At first glance, I'd say the answer to number 2 is no.  Most people are not going to use the randomness of the memory allocator to subvert purity.  It's unlikely that you accidentally write code like that.

The answer to number 1, I don't know.  I don't think the compiler can determine the origin of allocated memory without annotation.

>
> With the type system change I have prosed it becomes:
>
> pure bool randomPure() {
>     @transparent int[] a1 = new int[1];
>     @transparent int[] a2 = new int[2];
>     return a1.ptr > a2.ptr; // compile-time error, their ptr are @transparent, so they can't be read
> }

I can see now the value in this.  I just wonder if it would be worth it.  Seems like such a rare bug to create a whole new type constructor.

It also has some unpleasant effects.  For example, the object equality operator does this:

bool opEquals(Object o1, Object o2)
{
  if(o1 is o2)
    return true;
  ...
}

So this optimization would be unavailable inside pure functions, no?  Or require a dangerous cast?

Would it be enough to just require this type of restriction in pure @safe functions?

I feel that a new type of reference is likely overkill for this issue.

>> Showing an
>> assert that two pointers are not equal is not evidence of an error, it's
>> evidence of incorrect expectations.
>
> One of the main purposes of a type system is indeed to disallow programs based on incorrect expectations, to help programmers that may not always remeber what the incorrect expectations are :-)

My point in the above statement is that when you say:

auto a = new int[1];
auto b = new int[1];
assert(a.ptr == b.ptr);

is not evidence of an error :)  This is what you did previously.

-Steve

Steven Schveighoffer:

> That's not what your example showed.  It showed comparing two allocated pointers *outside* a pure function, and expected them to be equal.  I see that as disallowing all pointer comparisons.

My first examples were not so good, I am sorry :-) Thank you for not ignoring my posts despite that.

The idea was that if you allocate memory inside a pure function, then the result of this memory allocation is a @transparent pointer/reference. And that a @transparent pointer/reference can't be read (but you are allowed to dereference it, overwrite it, etc).

So this is OK, because the transparency of the pointer is respected:

pure @transparent(int*) foo() {
  return new int; // allocates just one int on the heap
}
void main() {
  @transparent int* i = foo(); // OK
  *i = 10; // OK
}


> I just wonder if it would be worth it.

Probably not, but we need to understand what the holes are, before accepting to keep them in the language :-)


> It also has some unpleasant effects.  For example, the object equality operator does this:
> 
> bool opEquals(Object o1, Object o2)
> {
>    if(o1 is o2)
>      return true;
>    ...
> }
> 
> So this optimization would be unavailable inside pure functions, no?  Or require a dangerous cast?


Ick.
You can't give a @transparent Object to function that expects an Object, because transparent references disallow something that you are allowed to do on a not transparent reference/pointer:


pure @transparent Object foo() {
  return new Object();
}
void opEquals(Object o1, Object o2) {}
void main() {
  @transparent Object o = foo();
  opEquals(o, o); // not allowed
}



> Would it be enough to just require this type of restriction in pure @safe functions?

I don't know.

Currently @safe is a wrong name, it means means @memorySafe. So I think that currently "@memorySafe" and "pure" are almost orthogonal concepts.

Bye,
bearophile

On Wed, 23 Feb 2011 16:40:22 -0500, bearophile <bearophileHUGS@lycos.com> wrote:

> Steven Schveighoffer:
>
>> That's not what your example showed.  It showed comparing two allocated
>> pointers *outside* a pure function, and expected them to be equal.  I see
>> that as disallowing all pointer comparisons.
>
> My first examples were not so good, I am sorry :-) Thank you for not ignoring my posts despite that.
>
> The idea was that if you allocate memory inside a pure function, then the result of this memory allocation is a @transparent pointer/reference. And that a @transparent pointer/reference can't be read (but you are allowed to dereference it, overwrite it, etc).
>
> So this is OK, because the transparency of the pointer is respected:
>
> pure @transparent(int*) foo() {
>   return new int; // allocates just one int on the heap
> }
> void main() {
>   @transparent int* i = foo(); // OK
>   *i = 10; // OK
> }

@transparent has little value outside a pure function, because the compiler does not expect to be able to perform pure optimizations on normal functions.  Right now, the only drawback you have shown of being able to compare such references is when that comparison is used as the return value for a pure function.  We can't continue to enforce the @transparent rules when they don't prevent problems, or else the language becomes too burdensome.

>> It also has some unpleasant effects.  For example, the object equality
>> operator does this:
>>
>> bool opEquals(Object o1, Object o2)
>> {
>>    if(o1 is o2)
>>      return true;
>>    ...
>> }
>>
>> So this optimization would be unavailable inside pure functions, no?  Or
>> require a dangerous cast?
>
>
> Ick.
> You can't give a @transparent Object to function that expects an Object, because transparent references disallow something that you are allowed to do on a not transparent reference/pointer:
>
>
> pure @transparent Object foo() {
>   return new Object();
> }
> void opEquals(Object o1, Object o2) {}
> void main() {
>   @transparent Object o = foo();
>   opEquals(o, o); // not allowed
> }

Once a reference gets out of a pure function, I think it should implicitly cast to a non-transparent reference, or else you have a huge mess.  I would not like to define @transparent versions of all functions.

The question is, shouldn't you be able to compare two objects inside a pure function?  I would think so.  Note that the comparison inside opEquals does not alter purity, it's just an optimization.

Then again, I don't think opEquals would be callable inside a pure function, since it's not pure itself.

Would something like o is null be allowed?

>> Would it be enough to just require this type of restriction in pure @safe
>> functions?
>
> I don't know.
>
> Currently @safe is a wrong name, it means means @memorySafe. So I think that currently "@memorySafe" and "pure" are almost orthogonal concepts.

@safe is supposed to prevent using pointers.  But then again, the definition is a moving target.  I have a vague memory that really only pointer arithmetic is disallowed, comparison is allowed.

-Steve

== Quote from bearophile (bearophileHUGS@lycos.com)'s article
...
> Currently you are able to write functions like:
> pure bool randomPure() {
>     int[] a1 = new int[1];
>     int[] a2 = new int[2];
>     return a1.ptr > a2.ptr;
> }

Is it possible to fix this by disallowing using the value of a pointer, except allowing them to be compared for equality (only)?  In other words, within a pure function, only 'is' '!is', ==, != are permitted as tests of pointers?  Other arithmetic forbidden... this sort of matches the Java model where you can't fiddle with references except to check if they are the same.

Kevin

== Quote from Kevin Bealer (kevindangerbealer@removedanger.gmail.com)'s article
> == Quote from bearophile (bearophileHUGS@lycos.com)'s article
> ...
> > Currently you are able to write functions like:
> > pure bool randomPure() {
> >     int[] a1 = new int[1];
> >     int[] a2 = new int[2];
> >     return a1.ptr > a2.ptr;
> > }
> Is it possible to fix this by disallowing using the value of a pointer,
> except allowing them to be compared for equality (only)?  In other words,
> within a pure function, only 'is' '!is', ==, != are permitted as tests
> of pointers?  Other arithmetic forbidden... this sort of matches the Java
> model where you can't fiddle with references except to check if they are
> the same.
> Kevin

I wanted to add something I just realized -- malloc is essentially pure if you can't compare the pointers it returns.  Of course if you can't do either casting or arithmetic on these pointers I'm not sure how to use malloc.

Kevin