Why doens't function type support comparision but channel type does?

[T L]

.

[Jan Mercl]

On Wed, Nov 23, 2016 at 2:40 PM T L <tapi...@gmail.com> wrote:

Functions can be inlined.

--

-j

[Volker Dobler]

Just one argument out of many: Closures.

x := 3

f1 := func() int {

return x

}

f2 := func() int { return 3 }

// Is f1 == f2 ?

x = 4

// What now? Still f1 == f2? Or never equal?

V.

[chris dollin]

If functions are comparable you have to be very
careful in defining /when/ they are equal.

func f(x int)int {return x+2}
func g(x int)int {return x+2}
func h(x int)int {return x+1+1}

Are f and g equal? f and h?

func k() func (int)int { return func(int x)int {x + 1}}

Are k() and k() equal? f and k()?

var x = 17
func l() func(int)int {y := 2; return func(int x)int {x +y}}

l() and f? and k()? and l()?

Disallowing equality tests on functions allows the
compiler to freely re-use code (or not).

Chris

--
Chris "allusive" Dollin

[T L]

Then?

Is there any problem to think no two functions can be equal?

[T L]

Any bad to think then never equal?

 

V.

[Axel Wagner]

So, your suggestion is, to have functions be comparable, but have the comparisons always be false (unless compared to nil)? How would that be useful and *not* completely confusing? e.g. how would that not lead to people asking here, once a week, why (os.Open == os.Open) == false or something like that?

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Volker Dobler]

That's basically is it: If functions are never equal so it is

not sensible make them comparable.

V.

[T L]

On Wednesday, November 23, 2016 at 10:35:59 PM UTC+8, Axel Wagner wrote:

So, your suggestion is, to have functions be comparable, but have the comparisons always be false (unless compared to nil)? How would that be useful and *not* completely confusing? e.g. how would that not lead to people asking here, once a week, why (os.Open == os.Open) == false or something like that?

No, I don't os.Open != os.Open, they are the same question, so they are equal.
I just mean comparing different functions always returns false.
 

On Wed, Nov 23, 2016 at 3:30 PM, T L <tapi...@gmail.com> wrote:

On Wednesday, November 23, 2016 at 9:53:57 PM UTC+8, Volker Dobler wrote:

Just one argument out of many: Closures.

x := 3

f1 := func() int {

return x

}

f2 := func() int { return 3 }

// Is f1 == f2 ?

x = 4

// What now? Still f1 == f2? Or never equal?

Any bad to think then never equal?

 

V.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[T L]

functions from the same declaration are equal.
and function variables at the same address are equal.
 

[Axel Wagner]

So, even though two functions do completely different things, you still want to have them equal? And even though two other functions do completely the same thing, they should be different?

Can you give a good justification of that behavior? And do you really think it won't confuse people like hell?

One of the main reasons given for not making functions comparable, is that there is no good, intuitive notion of what "equality" means in the face of inlining and closures, so *no matter what behavior you choose*, people will be confused.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Jan Mercl]

On Wed, Nov 23, 2016 at 3:30 PM T L <tapi...@gmail.com> wrote:

> Then? 

Then there is nothing to compare. If a function is inlined then you cannot have a function pointer to it (like in func foo() {}; f := foo). So fully supporting comparing function pointers means disabling inlining of any function used in the f := foo or similar construct. Forbidding comparing functions to anything else than nil solves the problem.

--

-j

[T L]

Predeclared functions, including inlined ones, can be viewed as constants, which have not addresses.
We can compare variable to constant, right?
 

--

-j

[T L]

On Wednesday, November 23, 2016 at 11:11:24 PM UTC+8, Axel Wagner wrote:

So, even though two functions do completely different things, you still want to have them equal? And even though two other functions do completely the same thing, they should be different?

If two functions do completely different things, they mus be two different functions.
Two different functions can also do the same thing, but they should be not equal.
 

Can you give a good justification of that behavior? And do you really think it won't confuse people like hell?

One of the main reasons given for not making functions comparable, is that there is no good, intuitive notion of what "equality" means in the face of inlining and closures, so *no matter what behavior you choose*, people will be confused.

On Wed, Nov 23, 2016 at 4:01 PM, T L <tapi...@gmail.com> wrote:

On Wednesday, November 23, 2016 at 10:39:01 PM UTC+8, Volker Dobler wrote:

Am Mittwoch, 23. November 2016 15:30:39 UTC+1 schrieb T L:

On Wednesday, November 23, 2016 at 9:53:57 PM UTC+8, Volker Dobler wrote:

Just one argument out of many: Closures.

x := 3

f1 := func() int {

return x

}

f2 := func() int { return 3 }

// Is f1 == f2 ?

x = 4

// What now? Still f1 == f2? Or never equal?

Any bad to think then never equal?

That's basically is it: If functions are never equal so it is

not sensible make them comparable.

V.

functions from the same declaration are equal.
and function variables at the same address are equal.
 

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[Jan Mercl]

On Wed, Nov 23, 2016 at 4:28 PM T L <tapi...@gmail.com> wrote:

> Predeclared functions, including inlined ones, can be viewed as constants, which have not addresses.
> We can compare variable to constant, right?

Wrong.

Function pointers, specific Go implementation details aside for now, are real pointers which you can use in the program to call the function it points to. So making them "constants, which have not addresses" is not an option.

--

-j

[T L]

Here, for "Predeclared functions", I mean formally declared function, not the variable ones.
 

 

--

-j

[T L]

But we can't take addresses of formally declared functions and function literals.
We can only take addresses of function variables.

--

-j

[Jan Mercl]

On Wed, Nov 23, 2016 at 4:55 PM T L <tapi...@gmail.com> wrote:

> But we can't take addresses of formally declared functions and function literals.

Yes, so if you cannot have the function pointer (like in func foo() {}; fp := foo) then there is nothing to compare so I don't understand what's the connection to comparing of function pointers.

> We can only take addresses of function variables.

Addresses of function variables can be compared freely without any limitation. Note: There's a distinction between the value of a function variable (that's the function pointer) and the address of the variable, that's not the function address and so it can be compared normally. To be explicit. Address of a function variable is a pointer to a pointer. Maybe that's making this thread confusing.

--

-j

[T L]

On Thursday, November 24, 2016 at 12:06:43 AM UTC+8, Jan Mercl wrote:

On Wed, Nov 23, 2016 at 4:55 PM T L <tapi...@gmail.com> wrote:

> But we can't take addresses of formally declared functions and function literals.

Yes, so if you cannot have the function pointer (like in func foo() {}; fp := foo) then there is nothing to compare so I don't understand what's the connection to comparing of function pointers.

We cannot tabke addresses of constants too, but we can compare constants.
 

[Jan Mercl]

On Wed, Nov 23, 2016 at 6:00 PM T L <tapi...@gmail.com> wrote:

On Thursday, November 24, 2016 at 12:06:43 AM UTC+8, Jan Mercl wrote:

On Wed, Nov 23, 2016 at 4:55 PM T L <tapi...@gmail.com> wrote:

> But we can't take addresses of formally declared functions and function literals.

Yes, so if you cannot have the function pointer (like in func foo() {}; fp := foo) then there is nothing to compare so I don't understand what's the connection to comparing of function pointers.

We cannot tabke addresses of constants too, but we can compare constants.

Constants have value that can be compared to some other value. Above quoted from your earlier post is the correct observation that one cannot have a function _value_ of a predeclared function or a function literal. So what value comparison is now supposed to be analogical to comparing constants? Put other way: In `if fv == whatever {}`, where the `fv` you are talking about comes from, such that it has something in common to comparing constants?

--

-j

[Axel Wagner]

On Wed, Nov 23, 2016 at 4:30 PM, T L <tapi...@gmail.com> wrote:

If two functions do completely different things, they mus be two different functions.

No. An example has been given above, here is another one:

https://play.golang.org/p/uNN0G4gzFm

 

Two different functions can also do the same thing, but they should be not equal.

Why not? If someone who never read go code reads "f == g", why would they assume that this is your definition? Why wouldn't they get confused, that two functions who have the same definition (not "stem from the same declaration", but "contain the same code") are not equal?

I agree that your definition is *consistent*. But it is still a) confusing for some cases and b) *not obviously the only sensible one*. Meaning, newcomers won't be able to infer from the expression, what it does. At all.

(yes, go has similar problems elsewhere. But that doesn't mean, that we should pile on)

 

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Axel Wagner]

(note: I'm exiting this thread now. I believe at this point it's reasonably clear, that there are good reasons for this and anyone not convinced yet won't be convinced by further arguments anyway)

[Ian Lance Taylor]

On Wed, Nov 23, 2016 at 7:00 AM, T L <tapi...@gmail.com> wrote:
>
> On Wednesday, November 23, 2016 at 10:35:59 PM UTC+8, Axel Wagner wrote:
>>
>> So, your suggestion is, to have functions be comparable, but have the
>> comparisons always be false (unless compared to nil)? How would that be
>> useful and *not* completely confusing? e.g. how would that not lead to
>> people asking here, once a week, why (os.Open == os.Open) == false or
>> something like that?
>
>
> No, I don't os.Open != os.Open, they are the same question, so they are
> equal.

Even this seemingly simple statement is unclear. Go now supports
-buildmode=shared and -linkshared, meaning that a Go program can link
against a set of shared libraries that are themselves written in Go.
When running in this mode, a function like os.Open can easily appear
multiple times in a single program image, in different shared
libraries. So while `os.Open == os.Open` might reasonably always be
true, given
func F() func(string) (*os.File, error) {
return os.Open
}

then it is much less clear whether

F() == os.Open

should be true, as F might be in a shared library and might return a
pointer to a different instance of os.Open.

Ian

[roger peppe]

Ian, what you say is true, but is also true of types and other objects too, I think. I found some interesting anomalies playing around with the new plugin package.

Myself, I would have no objection to saying that two function values are equal if they are defined by the same source code and use no variables in outer non-global scopes. But I guess that would preclude certain compiler optimisations that pull in variables that happen to have known constant values.

I also wouldn't mind defining closure equality as undefined, but perhaps best to steer away from more undefined behaviour.

  cheers,
    rog.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Ian Lance Taylor]

On Wed, Nov 23, 2016 at 3:49 PM, roger peppe <rogp...@gmail.com> wrote:
> Ian, what you say is true, but is also true of types and other objects too,
> I think. I found some interesting anomalies playing around with the new
> plugin package.

We've worked hard to make sure that what I said earlier is not true of
types, even in the presence of shared libraries. If we've failed,
please file bugs. Even with plugins it should work correctly.

Ian

[T L]

On Thursday, November 24, 2016 at 1:30:55 AM UTC+8, Axel Wagner wrote:

On Wed, Nov 23, 2016 at 4:30 PM, T L <tapi...@gmail.com> wrote:

If two functions do completely different things, they mus be two different functions.

No. An example has been given above, here is another one:

https://play.golang.org/p/uNN0G4gzFm

 

Two different functions can also do the same thing, but they should be not equal.

Why not? If someone who never read go code reads "f == g", why would they assume that this is your definition? Why wouldn't they get confused, that two functions who have the same definition (not "stem from the same declaration", but "contain the same code") are not equal?

I agree that your definition is *consistent*. But it is still a) confusing for some cases and b) *not obviously the only sensible one*. Meaning, newcomers won't be able to infer from the expression, what it does. At all.

(yes, go has similar problems elsewhere. But that doesn't mean, that we should pile on)

Then, how about let functions come from the same one function literal be equal?
 

[T L]

so os.File from a plugin is the same as the os.File in the host program?
how do we know the os package from a plugin is the same package in the host program?

 

[Jesper Louis Andersen]

First idea: Two functions are the same if their pointers (or closure pointers) refer to the same value. This is usually a recipe for disaster. As many people have noted, program transformations made by the compiler can change the pointers. So the meaning of your program is suddenly dependent on the particular version of Go, or the particular optimizations you have enabled. Moving around code can alter a program analysis to make an optimization (not) trigger as well.

All in all, if you want to avoid subtle errors in your programs, this is a bad equality definition.

Second idea: Two functions are the same if they are the from a *syntactic* point of view. In particular functions such as

func f(x, y int) int {

return x + y

}

func g(x, y int) int {

return y + x

}

will not be equal. This is deeply unsatisfactory, as we human beings are rather good at figuring out that the two functions are actually the same function with the same semantics. We probably wouldn't accept this as a valid kind of equality. But it has the advantage it is fairly easy to compute and it is not troubled as the pointer solution: we can create it deterministically.

Third idea: functions f and g are equal if

f(x) = g(x) forall inputs x (1)

This is in many ways the right definition, implementation troubles aside. Whenever you optimize your code, you replace a slow f with a fast g. They better behave the same on all inputs. Many proofs of programs utilize this notation as well (it is called extensionality). The idea is that if you can, externally, prove that the above (1) holds, then surely you can swap f for g in a program with no change. Proof assistants usually have more powerful type systems which allows you to write down such a proof for a given program. However, most programming languages do not. They rely on some external proof of correctness in its place.

Testing (1) is in general impossible since the space from which the x-values are drawn might be infinitely large in a way that it cannot be symbolically contained. For some cases, you may be able to model-check all inputs, or you may be satisfied with a large number of random trials. The latter *is* possible in Go fairly easily. See the https://golang.org/pkg/testing/quick/ package and in particular the CheckEqual function.

Fourth idea: disallow equality checks on functions.

In many ways, this is the sane solution. While we would like the third idea above, it is in general not achievable, so we have to opt for a lesser solution. And since most of those have flaws—one way or the other—we opt for a non-solution. It isn't that far-fetched: some languages disallow equality tests on floating point numbers because of their numerical instability. After a couple of computations, the error-term of your FP computation might be large enough that you won't compare equal to the original value. Hence, by disallowing direct equality comparison, you force people to check for equality by scrutinizing the difference and checking if it is under some ε-value.

[Michael Jones]

As you imply, the third idea in the form of “probabilistic equality” is generally unworkable. The computer risks forum is literally full of examples of failures here. A contrived example:

 

func a(x int) (int y) {

    If x != 0 {

       Y = 1/x

    }

    return

}

 

func a(x int) (int y) {

    If x != 0 {

        Y = 1/x

    }

    if x = 25638625386 {

    y = 42 // model a rare bug

    }

    return

}

 

It would be a miracle if a behavioral tester found a difference here, as intel can attest. You can test every input or you can prove equality. Nothing else means equal.

 

How about “Idea Four”? If the functions needing equality testing are amenable to interfaces then build a HelloMyNameIs() function for each of them. If not suitable, perhaps reserved arguments could return an id that can be compared. Each of these are just examples of “the programmer knows so ask her”

[Jesper Louis Andersen]

On Thu, Nov 24, 2016 at 8:23 PM Michael Jones <michae...@gmail.com> wrote:

 

It would be a miracle if a behavioral tester found a difference here, as intel can attest. You can test every input or you can prove equality. Nothing else means equal.

 

Not in a modern world. Here is an Erlang program, which does the same as your example:

-spec a(integer()) -> number() | undefined.

a(X) ->

    if

         X == 25638625386 -> exit({error, 42});

         X /= 0 -> 1 / X;

         true -> undefined

    end.

Random testing is unlikely to find this particular bug, but the concept of concolic testing is more clever. In Erlang we have a tool, CuTer, which performs concolic testing of programs. Running this on our example with some seed value (the input 3) immediately finds the problem in seconds:

[jlouis@lady-of-pain tmp]$ cuter z a '[3]' --recompile

Compiling z.erl ... OK

Testing z:a/1 ...

.xxxxxxxx

z:a(25638625386)

xxxxxxxxxxxxxx

=== Inputs That Lead to Runtime Errors ===

#1 z:a(25638625386)

How does it work? In the above if-expression, we note that the seed value of 3 took the branch behind 'X /= 0'. If we pick the branch 'X == 25638625386' and then ask an SMT solver (Z3 is what Cuter uses by default) if it can find something you can plug into X to make this go through.

In the more general case, we have traversed many such branch-decisions down to a certain depth. We can then invert one of the branch decisions and ask the SMT solver to find results which follows the path down to that branch, and then goes in another direction, due to the inversion. The reason an SMT solver is needed is because some of the earlier branch decisions might make it non-trivial to find one that forces a new path deep down in the decision tree. We get expressions of the form (X > 5) AND (X != 37) AND (Y < 7) AND (Y + X == 25) and ask the solver for values X and Y such that the expression is satisfied. Since we inverted one of the branch decisions, a sat of this expression gives us a new path to explore. We can continue forcing out new branches down to a certain depth.

Here is another function:

-spec b(pos_integer(), pos_integer(), pos_integer()) -> {ok, pos_integer()}.

b(X, Y, Z) ->

    case lists:sum([X,Y,Z]) of

        4321 -> exit(argh);

        Sum -> {ok, Sum}

    end.

which is given values X, Y and Z summing to 4321 is an error:

[jlouis@lady-of-pain tmp]$ cuter z b '[3,2,1]' --recompile

Compiling z.erl ... OK

Testing z:b/3 ...

.xxxxxx

z:b(1, 4281, 39)

xxxx

=== Inputs That Lead to Runtime Errors ===

#1 z:b(1, 4281, 39)

You are now in a territory where random testing is unlikely to find anything. At least not naive random testing with uniform distributions. But if you can ask the system (through profiling) what branch decisions were taken, SMT solvers can produce inputs which forces us to take different branches. In turn, they pick a specimen for each code block and makes sure every possible code block is traversed.

Another solution is to use a profiler, see that X = 25638625386 is never hit and then write a generator like this (Erlang QuickCheck)

my_int() ->

    frequency([

        {1, 25638625386},

        {1000, int()}]).

which will generate the nasty case 1/1001 times. Combined with suffix trees over what probalistic paths the generator has hit, this also forces out this value[0]

[0] Many computer games use the same trick. If a given ability were truly random, some games would feel unfair. Hence, the distribution is pseudo-random to make sure the given event happens at least with a certain probability. See http://dota2.gamepedia.com/Pseudo-random_distribution for instance, for Dota 2's variant.

[Michael Jones]

This is very nice! However, am i right in understanding that the magic is in knowing the text of the program--the fact that there are untaken branches? If so, this is not simply a 'behavioral' verification...it knows about the construction of the code and not just its behavior. Maybe I was unclear.

On the other line of development, Rob Pike's coverage analyzer would be handy that way too.

--

Michael T. Jones
michae...@gmail.com

[Jesper Louis Andersen]

On Fri, Nov 25, 2016 at 12:30 AM Michael Jones <michae...@gmail.com> wrote:

This is very nice! However, am i right in understanding that the magic is in knowing the text of the program--the fact that there are untaken branches? If so, this is not simply a 'behavioral' verification...it knows about the construction of the code and not just its behavior. Maybe I was unclear.

 

Indeed you are right. This requires the ability to work on the program text. It is a bit too hard to work on the output assembly for the program. The advantage of a model-checker or a probalistic method such as "testing/quick" is that they regard the system-under-test as a black box.

This fact can be used in numerous ways. The most powerful one is that once you have a specification model, in *any* programming language, it applies to any system implementing that model, in *any* language. This has been used historically for checking protocols for correctness, where the specification were written in some high-level language (Haskell, Erlang) but the code being tested were run in a low-level language (C, typically).

In short, no single method applies in every case. Figuring out if two programs are observationally equivalent usually requires one to exploit the structure of the program text. Because from that structure the proof or search strategy can be extracted.
 

[Axel Wagner]

I think, in the context of this thread, talking about formally proving whether two functions produces equivalent results is a red herring.

a) It is an impossible problem to solve in general, so you'd need to restrict your definition to some provable subset

b) That will be impossible to put in a spec in any sensible way without blowing it up immensely

c) Even if, that subset can't include side-effects, which would make it completely useless for go

and d) even if you could, requiring to implement those proofs would make it highly unlikely if not impossible, that more than one (or a very small handful) go-implementation exists, defeating the point of a good spec in the first place (think about, for example, what that would mean for gopherjs or gomobile, where a func() can be implemented by opaque javascript/asm/dalvik bytecode/compiled machine code).

If you want to debate the finer points of such proof engines for go existing as a tool separate from the language, I think that should go in a separate thread. I don't think it can be sensibly argued that it should become part of the language as the equality operator on func's.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Jesper Louis Andersen]

Indeed, the whole point is that you shouldn't add equality of functions to a language. I disagree that the formal proof of function equivalence is a red herring. Rather, it is the crux of the problem: the only sensible equality of functions turns out to be observational equality, which is non-trivial to handle. But in order to understand that, you eventually have to discuss what it would take to add such a thing to a language. Talk is rather cheap compared to writing a robust compiler with deterministic interfaces. In the same vein, I don't think float32 and float64 should be eqtypes either. Nor, can it be argued, should a map or array because their equivalence isn't an O(1) operation.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

[atd...@gmail.com]

It highly depends on what you define a function.

If it's in the mathematical sense, it won't work.

A function, in practice, is a small embedded program (stored as a valur in the main program). It's not just the text (semantics). It's defined somewhere (in some package etc...)

That's all those things that probably need to be equal.

[Michael Jones]

To be pedantically specific, this thread is about "Why doens't function type support comparision but channel type does?" Careful analysis of the original phrasing suggests the matter to be "why is the difference as it is" and this has been explained quite clearly. The subject of language changes is itself off-topic, as is the discussion of implications and motivations for changes.

[Ian Lance Taylor]

On Thu, Nov 24, 2016 at 6:01 AM, T L <tapi...@gmail.com> wrote:
>
> On Thursday, November 24, 2016 at 8:16:49 AM UTC+8, Ian Lance Taylor wrote:
>>
>> On Wed, Nov 23, 2016 at 3:49 PM, roger peppe <rogp...@gmail.com> wrote:
>> > Ian, what you say is true, but is also true of types and other objects
>> > too,
>> > I think. I found some interesting anomalies playing around with the new
>> > plugin package.
>>
>> We've worked hard to make sure that what I said earlier is not true of
>> types, even in the presence of shared libraries. If we've failed,
>> please file bugs. Even with plugins it should work correctly.
>
>

> so os.File from a plugin is the same as the os.File in the host program?
> how do we know the os package from a plugin is the same package in the host
> program?

In a Go program, the path used in the import statement uniquely
defines a package. If you write a plugin that breaks that rule, your
plugin will not work correctly.

Ian