Algorithm Club

[Mandolyte]

The recent survey reveled that generics was thing that would improve Go the most. But at 16%, the responses were rather spread out and only 1/3 seemed to think that Go needed any improvement at all - see link #1. I think most will concede that generics would help development of algorithms, libraries, and frameworks. So in the spirit of friendly rivalry, here is a list of algorithms developed for Swift:

https://github.com/raywenderlich/swift-algorithm-club

As you might guess, it is chock-full of generics. Yeah, I'm a little envious. :-) enjoy...

#1 https://blog.golang.org/survey2016-results

[Rob Pike]

Algorithms are not helped by generic types as much as by polymorphism, a related but distinct subject.

-rob

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

[Michael Jones]

Type-based generally is all that I ever seem to want...making a macro-like LLRB heap concrete to handle objects of my own type and with my own comparison function.  I believe this is what Rob speaks of. I've personally never needed to sort or order a bunch of unknown "things"

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.

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

--

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

[David Collier-Brown]

We still don't understand genrality: the current generics are unimpressive. The proposals for Go are typically "let's do something that has failed already, in hopes that trying it agin will have a different result".  That, alas, is one of the definitions of insanity.

Due caution is advised!

[Michael Jones]

I think I was saying that what I seem to want personally is the "simple, weak, slight" thing that you likely see as failure.

The opposite end of that--where everything is a list and can be composed without special regard (lisp) or everything is an object that can receive any message (smalltalk) are comfortable for me, but just not what I find myself wanting very often.

My own view is not important in the sense that a broad survey would be, but since it seems much less than what people seem to dream of, I wanted to share that maybe people could be happy with less than they seek.

Or maybe that ultimate typeless generality is what others really need somehow. I would not know. 

On Fri, Mar 24, 2017 at 6:13 PM David Collier-Brown <dave...@gmail.com> wrote:

We still don't understand genrality: the current generics are unimpressive. The proposals for Go are typically "let's do something that has failed already, in hopes that trying it agin will have a different result".  That, alas, is one of the definitions of insanity.

Due caution is advised!

--
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.
For more options, visit https://groups.google.com/d/optout.

[David Collier-Brown]

Hmmn, we may be thinking different things... I *think* I'm looking for a
way to say "an X of Y", and see composition as a possible approach.
I just don't know if it will be a, the, or not the answer (;-))

--dave

> <mailto:golang-nuts...@googlegroups.com>.

> For more options, visit https://groups.google.com/d/optout.
>
> --
> Michael T. Jones

> michae...@gmail.com <mailto:michae...@gmail.com>

[Bakul Shah]

The simplest design I can think of (that does what you seem to
want) is to add parameterized packages. Here's a
stereotypical example:

========
package stack(T) // parameterized on stack element type
import "fmt"
type Type struct { rep []T
func New() *Type { &T{} }
func (stk *Type)Push(t T) { stk.rep = append(stk.rep, t) }
func (stk *Type)Pop()(T, error) {
var t T
ln := len(stk.rep)
if ln = 0 { return t, fmt.Errorf("Empty stack") }
t = stk.rep[ln-1]
stk.rep = st.rep[:ln-2]
return t, nil
}
========
package foo

import intstack "stack"(int) // stack of ints
import intstackstack "stack"(intstack.Type) // stack of stack of ints

var istk intstack.Type
var istkstk intstackstack.Type
...
istk.Push(5)
x, err := istk.Pop()
istkstk.Push(istk)
=========

Note that
- This adds only two syntax rules.
1. In the package header, its name can be followed by a
parenthesized list of names.
2. A package import must provide a complete list of types,
which are concrete or its own parameter types. And such
instantiated package must be given a local name.
- *All* we are doing is saving some typing.
- Given this, this feature can be expanded out via a preprocessor.
- Given this, no new semantics need be defined!
- Only one instance of a given type of package need be
generated and compiled.
- The intstackstack example is to show composability.
- This actually makes interface types more useful than now.

The last point is worth elaborating on. Currently the "io"
package defines a bunch of interface types such as Reader,
Writer and so on. These interface types allow you to use
objects of a variety of other types so as as they implement
relevant functions. But "io" interface types are primarily for
byte slices. If "io" was defined as a parameterized package,
one can have similar choices for other slice types. Currently
to provide similar set of useful interface types for other
slice types you would have to replicate a whole bunch of
packages.

Avoiding duplication of code should not be taken lightly.
Copies can diverge, bug fixes or peroformance improvements may
not be made consistently across all copies, newer copies may
not have as much testing, and as different copies may have
different bugs (and written by different people) each has to
be independently and thoroughly reviewed etc.

Go may not impress lanuage designers but it is a practical
language. IMHO the above has a similar feel for "generics" --
it is simple, very easy to teach, it is not turing complete or
anything fancy but takes care of most of the common use cases.

I had looked at previous formal proposals but none seemed
as simple as this.

Bakul

[Will Faught]

Generics is polymorphism, though; actually, it's a kind of polymorphism called parametric polymorphism. It's program behavior that doesn't depend on the types of the data it uses. It's useful for algorithms for types that contain variable types. There are numerous slice, map, and chan utility functions, for example, which aren't possible for users to make in Go.

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

[Michael Jones]

This is just what I dream of. (Well, not dream really as I do it already with a macro processor, but I dream of it being integrated and robust.)

[Egon]

https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/edit#heading=h.wko1dvdznk4y

[Mandolyte]

@Bakul - is your approach documented in Egon's collection? I think it is essentially the same as Egon's at
https://groups.google.com/d/msg/golang-nuts/JThDpFJftCY/1MqzfeBjvT4J

Perhaps your syntax is cleaner, simpler. I also like this general approach. In Egon's document, this approach has nearly no downsides. Sounds like @Michael Jones also would be happy this.

Cheers...

[Egon]

On Sunday, 26 March 2017 15:30:30 UTC+3, Mandolyte wrote:

@Bakul - is your approach documented in Egon's collection? I think it is essentially the same as Egon's at
https://groups.google.com/d/msg/golang-nuts/JThDpFJftCY/1MqzfeBjvT4J

Perhaps your syntax is cleaner, simpler. I also like this general approach. In Egon's document, this approach has nearly no downsides.

Depending what do you want to use generics for, there are significant downsides. Mainly, you cannot create chained general purpose functions... e.g. LINQ, Rx... in the summary document see problems "functional code" and "language extensions".

You could argue that using such approaches is not good for Go... but this wouldn't invalidate that this generics approach doesn't solve these problems nicely.

You are always making trade-offs.

Personally, I think it makes trade-offs that are suitable to Go... but I understand why people would disagree with it.

[Mandolyte]

I agree that it makes the suitable trade-offs. And Linq is doing pretty well without generics (https://github.com/ahmetb/go-linq); not familiar with Rx.

When I consider the dilemma, the two things I don't want are slow programmers and slow execution, leaving "slow compilers and bloated binaries". But here is how I think about this option:

- There are alternatives that only impact compiler speed if they are actually used. I think that's fair.

- There are alternatives that result in binaries hardly any larger than if you copy-pasted. Again, I think that's reasonable.

As I understand it, the package template approaches fall into this camp. So with the above restrictions, count me in favor of slow and bloated :-)

[Egon]

On Monday, 27 March 2017 04:06:17 UTC+3, Mandolyte wrote:

I agree that it makes the suitable trade-offs. And Linq is doing pretty well without generics (https://github.com/ahmetb/go-linq); not familiar with Rx.

When I consider the dilemma, the two things I don't want are slow programmers and slow execution, leaving "slow compilers and bloated binaries". But here is how I think about this option:

- There are alternatives that only impact compiler speed if they are actually used. I think that's fair.

The unfortunate reality is that when you add generics to a language it will be almost impossible to avoid it.

And the dilemma is not a binary-yes-no... e.g. would you give 100x performance to have fast programmers, fast execution and no code-bloat... or would you give 10% performance for medium speed programmers, fast execution and some code-bloat?

It's better to view the dilemma as a rating system. As a facilitated example:

copy-paste:

1. convenience: 0/10

2. code size: 10/10

3. performance: 10/10

4. flexibility: 10/10

5. readability: 5/10

interfaces:

1. convenience: 4/10

2. code size: 0/10

3. performance: 2/10

4. flexibility: 6/10

5. readability: 8/10

type-level generics with boxing:

1. convenience: 7/10

2. code size: 0/10

3. performance: 5/10

4. flexibility: 8/10

5. readability: 1/10

package-level generics with out-of-bounds boxing:

1. convenience: 6/10

2. code size: 3/10

3. performance: 8/10

4. flexibility: 5/10

5. readability: 7/10

Obviously, do not take these numbers seriously.

- There are alternatives that result in binaries hardly any larger than if you copy-pasted. Again, I think that's reasonable.

Here you are making a trade-off... it's not just about size, but also about performance. More code means more icache misses.

The main point is that "there are approaches that produce less code than copy-pasting". So ideally we want smaller binaries than you would get from copy-pasting.

As I understand it, the package template approaches fall into this camp. So with the above restrictions, count me in favor of slow and bloated :-)

Not necessarily. I suspect it will be faster to compile than most generics packages and similarly dealing with bloat will be easier.

[Michael Jones]

Another dimension is "intellectual complexity." Where that is smaller, everything else is better for coding, documenting, debugging, testing, reading, using, and maintaining. 

It is a critical measure for maintaining the 'Go' of Go. 

--

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

[David Collier-Brown]

Folks, is this something that we should do with a template processor?
More topically, is this a set of somethings that we should prototype each of, using templates?

I'd love to see actual experiments in computer "science" (;-)) and a debate about the tradeoffs based on code.

--dave 

[Jesper Louis Andersen]

In addition, there are also the notion of "staging meta-compilation" as witnessed in e.g., BER-MetaOCaml.

The idea is that if you want the best program efficiency, no compiler is able to carry out the needed optimizations. So you start meta-compiling by staging the compiler and generating code at each stage for the next one. Preferably in a type-safe manner. You can get some tremendously fast computational kernels out of this method. Usually, such speed only matter to a small part of a code base, so the effort is well spent doing these kinds of optimizations. Or it matters a lot in which case you need a GPU, FPGA or ASIC to make it run fast enough.

Generics are trying very hard to be a lot of things at the same time: Convenient notation, Efficency, and Type safety. This means it has to make trade-offs along those areas, one way or the other.

As for Code Size and icache misses: back in the day, the MLton project found that code expansion usually happens on a few types. Less than a handlful is the common case. And because (polyvariant) inlining follows, there are a lot of situations where the code size expansion doesn't matter at all to a modern largeish icache. Of course, this was 15 years ago, so many things may have happened in the meantime.

--

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.

[David Collier-Brown]

I can't speak to the staging process, but I became all too aware of how
to cause cache misses on a SPARC (:--)

In a mature, sane and well-debugged program, write #define debug()
macros so they always caused a cache miss even when not turned on, then
sprinkle enthusiastically throughout all the hot parts of the program.

--dave

> /copy-paste:/

> 1. convenience: 0/10
> 2. code size: 10/10
> 3. performance: 10/10
> 4. flexibility: 10/10
> 5. readability: 5/10
>

> /interfaces:/

> 1. convenience: 4/10
> 2. code size: 0/10
> 3. performance: 2/10
> 4. flexibility: 6/10
> 5. readability: 8/10
>

> /type-level generics with boxing:/

> 1. convenience: 7/10
> 2. code size: 0/10
> 3. performance: 5/10
> 4. flexibility: 8/10
> 5. readability: 1/10
>

> /package-level generics with out-of-bounds boxing:/

> 1. convenience: 6/10
> 2. code size: 3/10
> 3. performance: 8/10
> 4. flexibility: 5/10
> 5. readability: 7/10
>

> *Obviously, do not take these numbers seriously.*

>
> - There are alternatives that result in binaries hardly any
> larger than if you copy-pasted. Again, I think that's
> reasonable.
>
>
> Here you are making a trade-off... it's not just about size, but
> also about performance. More code means more icache misses.
>

> The main point is that /"there are approaches that produce less
> code than copy-pasting"/. So ideally we want smaller binaries

> than you would get from copy-pasting.
>
> As I understand it, the package template approaches fall
> into this camp. So with the above restrictions, count me in
> favor of slow and bloated :-)
>
>
> Not necessarily. I suspect it will be faster to compile than
> most generics packages and similarly dealing with bloat will be
> easier.
>
>
> On Sunday, March 26, 2017 at 9:08:20 AM UTC-4, Egon wrote:
>
> On Sunday, 26 March 2017 15:30:30 UTC+3, Mandolyte wrote:
>
> @Bakul - is your approach documented in Egon's
> collection? I think it is essentially the same as
> Egon's at
> https://groups.google.com/d/msg/golang-nuts/JThDpFJftCY/1MqzfeBjvT4J
>
> Perhaps your syntax is cleaner, simpler. I also like
> this general approach. In Egon's document, this
> approach has nearly no downsides.
>
>
> Depending what do you want to use generics for, there
> are significant downsides. Mainly, you cannot create
> chained general purpose functions... e.g. LINQ, Rx...

> /in the summary document see problems "functional code"
> and "language extensions"./

>
> You could argue that using such approaches is not good
> for Go... but this wouldn't invalidate that this
> generics approach doesn't solve these problems nicely.
>
> You are always making trade-offs.
>

> /Personally, I think it makes trade-offs that are

> suitable to Go... but I understand why people would

> disagree with it./

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

> <mailto:golang-nuts...@googlegroups.com>.

[Will Faught]

Something I've never seen addressed in the generics tradeoffs debate (not saying it hasn't been, but I haven't see it personally) is that without generics, you're forced to use interface{}, which just boxes the values anyway. So you're already paying a performance cost for type-agnostic code without generics. And if you copy/paste code instead of boxing, you're just bloating the size of the binary like generic templates would. It seems to me if boxing generics was added, there wouldn't be a downside: if you didn't want to pay the performance cost of boxing generics, then don't use generics; if you can pay the cost, then use them, and it won't perform any worse than it would now with interface{}, and perhaps could perform even better, depending on the semantics and implementation. You could have the same opt-in performance tax in the form of bloated binaries/slow builds as well, but lack of an official debugger right now is predicated on builds being fast, so that seems like a no-go.

[Egon]

On Tuesday, 28 March 2017 07:56:57 UTC+3, Will Faught wrote:

Something I've never seen addressed in the generics tradeoffs debate (not saying it hasn't been, but I haven't see it personally)

See https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/edit#heading=h.j8r1gvdb6qg9

is that without generics, you're forced to use interface{}

You can also use copy-paste, code-generation.

 

which just boxes the values anyway. So you're already paying a performance cost for type-agnostic code without generics. And if you copy/paste code instead of boxing, you're just bloating the size of the binary like generic templates would. It seems to me if boxing generics was added, there wouldn't be a downside:

It would be slower than copy-paste and generated approaches.

 

if you didn't want to pay the performance cost of boxing generics, then don't use generics; if you can pay the cost, then use them, and it won't perform any worse than it would now with interface{}, and perhaps could perform even better, depending on the semantics and implementation. You could have the same opt-in performance tax in the form of bloated binaries/slow builds as well,

When generics are added, then they will be (almost) impossible to avoid. So the opt-in "slow builds" isn't really opt-in unless you really try...

[gary.wi...@victoriaplumb.com]

Parametric polymorphism is enabled by generics.

[Will Faught]

Egon:

>See https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/edit#heading=h.j8r1gvdb6qg9

I don't see the Implicit Boxing section point out that this is what happens now when you shoehorn everything into interface{}. In this sense, I don't see a performance downside for boxing generics compared to the current state of things.

>You can also use copy-paste, code-generation.

I was referring to the downsides of copy/paste here: "You could have the same opt-in performance tax in the form of bloated binaries/slow builds as well, but lack of an official debugger right now is predicated on builds being fast, so that seems like a no-go."

>It would be slower than copy-paste and generated approaches.

It wouldn't be slower than interface{}, right?

>When generics are added, then they will be (almost) impossible to avoid. So the opt-in "slow builds" isn't really opt-in unless you really try...

By opt-in, I meant the code we write ourselves. In shared code, it would be no more impossible to avoid generics than interface{} is now, which doesn't seem to have been a problem. If there's a case where the performance is too slow, one could always copy/paste the code and remove the generics from it.

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/VbWfF865C3s/unsubscribe.
To unsubscribe from this group and all its topics, send an email to golang-nuts+unsubscribe@googlegroups.com.

[Egon]

On Thursday, 30 March 2017 03:15:33 UTC+3, Will Faught wrote:

Egon:

>See https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/edit#heading=h.j8r1gvdb6qg9

I don't see the Implicit Boxing section point out that this is what happens now when you shoehorn everything into interface{}.

Because it can also be implemented in other ways.

 

In this sense, I don't see a performance downside for boxing generics compared to the current state of things.

As said... there is a performance upside for some other approaches.

>You can also use copy-paste, code-generation.

I was referring to the downsides of copy/paste here: "You could have the same opt-in performance tax in the form of bloated binaries/slow builds as well, but lack of an official debugger right now is predicated on builds being fast, so that seems like a no-go."

The builds being fast are necessary for many things, mainly iterating on features, tests.

 

>It would be slower than copy-paste and generated approaches.

It wouldn't be slower than interface{}, right?

Yes.

 

>When generics are added, then they will be (almost) impossible to avoid. So the opt-in "slow builds" isn't really opt-in unless you really try...

By opt-in, I meant the code we write ourselves. In shared code, it would be no more impossible to avoid generics than interface{} is now, which doesn't seem to have been a problem. If there's a case where the performance is too slow, one could always copy/paste the code and remove the generics from it.

Copy-paste wouldn't remove generics used in the standard-library... i.e. it's hard to avoid the compile-time overhead. I agree, it's possible, but unlikely that anyone will do it.

 

On Tue, Mar 28, 2017 at 12:28 AM, Egon <egon...@gmail.com> wrote:

On Tuesday, 28 March 2017 07:56:57 UTC+3, Will Faught wrote:

Something I've never seen addressed in the generics tradeoffs debate (not saying it hasn't been, but I haven't see it personally)

See https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB32uVXX4pi-HnNjkMEgyAHX4N4/edit#heading=h.j8r1gvdb6qg9

is that without generics, you're forced to use interface{}

You can also use copy-paste, code-generation.

 

which just boxes the values anyway. So you're already paying a performance cost for type-agnostic code without generics. And if you copy/paste code instead of boxing, you're just bloating the size of the binary like generic templates would. It seems to me if boxing generics was added, there wouldn't be a downside:

It would be slower than copy-paste and generated approaches.

 

if you didn't want to pay the performance cost of boxing generics, then don't use generics; if you can pay the cost, then use them, and it won't perform any worse than it would now with interface{}, and perhaps could perform even better, depending on the semantics and implementation. You could have the same opt-in performance tax in the form of bloated binaries/slow builds as well,

When generics are added, then they will be (almost) impossible to avoid. So the opt-in "slow builds" isn't really opt-in unless you really try...

 

but lack of an official debugger right now is predicated on builds being fast, so that seems like a no-go.

On Friday, March 24, 2017 at 12:10:08 PM UTC-7, Mandolyte wrote:

The recent survey reveled that generics was thing that would improve Go the most. But at 16%, the responses were rather spread out and only 1/3 seemed to think that Go needed any improvement at all - see link #1. I think most will concede that generics would help development of algorithms, libraries, and frameworks. So in the spirit of friendly rivalry, here is a list of algorithms developed for Swift:

https://github.com/raywenderlich/swift-algorithm-club

As you might guess, it is chock-full of generics. Yeah, I'm a little envious. :-) enjoy...

#1 https://blog.golang.org/survey2016-results

--
You received this message because you are subscribed to a topic in the Google Groups "golang-nuts" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/golang-nuts/VbWfF865C3s/unsubscribe.

To unsubscribe from this group and all its topics, send an email to golang-nuts...@googlegroups.com.

[Will Faught]

>Because it can also be implemented in other ways.

Do you mean interface{} can be implemented in other ways? I couldn't make out your meaning.

>As said... there is a performance upside for some other approaches.

The other approaches have downsides, or at least generation does. Compared to using interface{} as is done now, boxing generics improves type safety and expressiveness and has no performance regression. That's a clear net win.

[Egon]

On Friday, 31 March 2017 09:02:09 UTC+3, Will Faught wrote:

>Because it can also be implemented in other ways.

Do you mean interface{} can be implemented in other ways? I couldn't make out your meaning.

There are multiple ways of implementing "boxing generics" and "interface{}". Implying it has same perf. characteristics as interface{}, implies the same implementation as interface{}.

 

>As said... there is a performance upside for some other approaches.

The other approaches have downsides, or at least generation does. Compared to using interface{} as is done now, boxing generics improves type safety and expressiveness and has no performance regression. That's a clear net win.

I meant other generics approaches (not alternatives).

Boxing generics adds complexity to the compiler, without solving some of the problems that generics intends to solve.

Mainly, implementing highly performant data-structures would still require code-generation/copy-paste.

And that is a pretty big downside.

[Michael Jones]

There is part of the topic that has always been slightly beyond my grasp. (Maybe I do understand...but just lack absolute certainty.) Maybe others know the answer...

In a template system (which is what I prefer but that's not the point of this email) we have the notion of the TYPE(s) being a formal argument. We presume that the code will compile or fail based on the suitability of the instantiated type. That is, a templated Min would fail on the comparison "<" if the TYPE was "Map[something]something." Call that a lexical fail. 

My question is, what about a semantic fail. Say, "<" for floating point. In the sort package the Less function does !Less(a,b)&&!Less(b,a) to figure out Equal(a,b). That works for ints and strings, but when I templated sort I found that it failed in tests with float32 and float64 because of NaN values, which are !Less(a,b)&&!Less(b,a) yet !Equal(a,b). I had to make two templates, one for floating point values and one for integral/string values.

My uncertainty is in the fact that I only discovered the problem through testing--i had failed to anticipate it. It was easy to fix, but only after the fact. That makes me wonder about the truly perfect generality of templated reusable software, which would be most perfect if it failed to compile rather than fail in some rare edge condition under use or testing.

The closest solution I have known about this was IBM Research's AXIOM symbolic mathematical system, which had a robust and mathematically pure concept of types and operators and commutativity and inverses and the like. It was possible to make a function for "two arguments that were elements of a ring with property A and B." That made sense to me, but was off-putting to some users. 

I recalled it i the sort case because I wanted to kinds of typed clients for "<", the kind where !Less(a,b)&&!Less(b,a) === Equal(a,b), and the kind where that is not the case--and ideally--a way to have instantiation for the first kind use path A and the second kind use path B. That would have made the code truly general.

I fear this pedantry will make Russ suspicious of slowing compilation AND programmers. :-)

Michael

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

[Ian Davis]

On Fri, 31 Mar 2017, at 05:19 PM, Michael Jones wrote:

There is part of the topic that has always been slightly beyond my grasp. (Maybe I do understand...but just lack absolute certainty.) Maybe others know the answer...

In a template system (which is what I prefer but that's not the point of this email) we have the notion of the TYPE(s) being a formal argument. We presume that the code will compile or fail based on the suitability of the instantiated type. That is, a templated Min would fail on the comparison "<" if the TYPE was "Map[something]something." Call that a lexical fail. 

My question is, what about a semantic fail. Say, "<" for floating point. In the sort package the Less function does !Less(a,b)&&!Less(b,a) to figure out Equal(a,b). That works for ints and strings, but when I templated sort I found that it failed in tests with float32 and float64 because of NaN values, which are !Less(a,b)&&!Less(b,a) yet !Equal(a,b). I had to make two templates, one for floating point values and one for integral/string values.

Is this because sort.Less requires total ordering and, because of NaN, < for floats only offers partial ordering?

Ian

[Michael Jones]

yes

--

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.

[Jan Mercl]

On Fri, Mar 31, 2017 at 6:20 PM Michael Jones <michae...@gmail.com> wrote:

> I recalled it i the sort case because I wanted to kinds of typed clients for "<", the kind where !Less(a,b)&&!Less(b,a) === Equal(a,b), and the kind where that is not the case--and ideally--a way to have instantiation for the first kind use path A and the second kind use path B. That would have made the code truly general.

I've been thinking about this for some time and the idea how to solve this particular issue goes like this:

        func Less<T>(a, b T) bool {

                switch x := a.(type) {

                case *float32, *float64:

                        return !math.IsNaN(a) && !math.IsNaN(b) && a < b

                default:

                        return a < b

                }

        }

The point is that the type switch goes away completely when the [future] compiler sees the type-specialized version and can infer which case path will be taken. Of course, the current compiler rejects .(type) for non-interface types.

--

-j

[Egon]

On Friday, 31 March 2017 19:20:26 UTC+3, Michael Jones wrote:

There is part of the topic that has always been slightly beyond my grasp. (Maybe I do understand...but just lack absolute certainty.) Maybe others know the answer...

In a template system (which is what I prefer but that's not the point of this email) we have the notion of the TYPE(s) being a formal argument. We presume that the code will compile or fail based on the suitability of the instantiated type. That is, a templated Min would fail on the comparison "<" if the TYPE was "Map[something]something." Call that a lexical fail. 

My question is, what about a semantic fail. Say, "<" for floating point. In the sort package the Less function does !Less(a,b)&&!Less(b,a) to figure out Equal(a,b). That works for ints and strings, but when I templated sort I found that it failed in tests with float32 and float64 because of NaN values, which are !Less(a,b)&&!Less(b,a) yet !Equal(a,b). I had to make two templates, one for floating point values and one for integral/string values.

My uncertainty is in the fact that I only discovered the problem through testing--i had failed to anticipate it. It was easy to fix, but only after the fact. That makes me wonder about the truly perfect generality of templated reusable software, which would be most perfect if it failed to compile rather than fail in some rare edge condition under use or testing.

This problem is less about generics and more about variance in behavior.

In the same way you could write an io.Reader that doesn't work as an io.Reader should, because there are no guarantees. It is a programmer error to implement the "wrong thing"... The problem is that generics introduces more variance in behavior, but not much more than an interface.

The question is rather -- how verify highly-variant behavior?

I think the best approach, is to provide property tests. E.g. after sorting the output should be sorted. In the best scenario the test could look something like:

type Floats []float32

// snip implementation

func TestFloats(t *testing.T) { sort.TestInterface(t, Floats{}) }

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.

--

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

[David Collier-Brown]

In a previous life, this was one of the problems we had with generate-and-execute.

In lisp, you could almost always create correct code and run it.  With C, I could generate library interposers by the ton, but they only *usually* worked, so I had to generate unit tests, too. Fortunately I had a mad colleague who loved generating tests (;-))

I wonder how many corner cases there are in C++/Java/Rust/whatever generics of exactly this sort?

--dave

yes

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.

[Bakul Shah]

IMHO sort() is best thought of as a higher order function (one taking a functional argument, the comparison function). It would be perfectly fine to use a > b  as this comparison function or a < b or any other compare function a given type (e.g. case ignoring compare function on strings).  Some confusion may be due to the way Go sort package shoehorns a generic function into Go's existing machinery. Ideally I’d want something like

func sort(vector []T, func compare(a, b T)bool) 

with T to be specified at the call site.

You can achieve this with a parametric package extension (the only new syntax is in package header and package import. So it is limited but simple to understand).

What you are asking for (flagging a “semantic fail” at compile time) is perhaps way beyond what a generics package in a language like Go can do.

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

[David Collier-Brown]

That's an interesting thought: one can generate a generic from a type
which has an ordering, and identity and perhaps a few other functions as
its interface.

That eliminates the "grad student slave writing tests" from the
algorithm (;-)) and makes it, in principle, computable in a Go kind of way.

--dave

On 31/03/17 04:55 PM, Bakul Shah wrote:
> IMHO sort() is best thought of as a higher order function (one taking a
> functional argument, the comparison function). It would be perfectly
> fine to use a > b as this comparison function or a < b or any other
> compare function a given type (e.g. case ignoring compare function on
> strings). Some confusion may be due to the way Go sort package
> shoehorns a generic function into Go's existing machinery. Ideally I’d
> want something like
>
> func sort(vector []T, func compare(a, b T)bool)
>
> with T to be specified at the call site.
>
> You can achieve this with a parametric package extension (the only new
> syntax is in package header and package import. So it is limited but
> simple to understand).
>
> What you are asking for (flagging a “semantic fail” at compile time) is
> perhaps way beyond what a generics package in a language like Go can do.
>
>> On Mar 31, 2017, at 9:19 AM, Michael Jones <michae...@gmail.com

>> <https://groups.google.com/d/topic/golang-nuts/VbWfF865C3s/unsubscribe>.

>> To unsubscribe from this group and all its topics,
>> send an email to golang-nuts...@googlegroups.com.
>> For more options, visit
>> https://groups.google.com/d/optout

>> <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
>> <mailto:golang-nuts...@googlegroups.com>.

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

>> <https://groups.google.com/d/optout>.
>>
>>
>>
>>
>> --
>> Michael T. Jones
>> michae...@gmail.com <mailto:michae...@gmail.com>

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

>> <mailto:golang-nuts...@googlegroups.com>.

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

> You received this message because you are subscribed to a topic in the
> Google Groups "golang-nuts" group.
> To unsubscribe from this topic, visit
> https://groups.google.com/d/topic/golang-nuts/VbWfF865C3s/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to
> golang-nuts...@googlegroups.com

> <mailto:golang-nuts...@googlegroups.com>.

[Will Faught]

On Sat, Apr 1, 2017 at 12:11 AM, Egon Elbre <egon...@gmail.com> wrote:

On Sat, Apr 1, 2017 at 1:42 AM, Will Faught <will....@gmail.com> wrote:

For example []GenericElement could be boxed as:

struct{ itab ptr; ... data []struct{elem ptr} }

or

[]struct{itab, elem ptr}

Can you explain in more detail what's going on there? What's itab? You seem to have pointers represents the slice elements, and that's what I meant by allocating on the heap and passing pointers around. Boxing is just moving values from the stack to the heap, or starting a value in the heap rather than the stack, right?

https://research.swtch.com/interfaces

When you have a slice you could specify the interface table pointer once or for each element. One could prevents significant amount of memory at the cost of making internals more complicated.

Boxing also involves adding additional type information to distinguish between different types of pointers.

 

Right, but my point is that currently it's not implemented that way, so it works the same way, so there would be no performance regression.

 

 

https://www.infoq.com/presentations/java-evolution-performance

 

Which part of that are you referring to?

The 10x performance difference in dictionary implementation between C# and Java.

Sure, if you implement it the right way, you can do even better than pure boxing, but (without having read your source or being familiar with what C# does under the hood for its reified generics), but do they achieve that with some tradeoff? Like compile-time or run-time specialization? I'm talking about not having a tradeoff at all.

 

 

My original point was the relative upsides and downsides of boxing generics relative to what Go is now, not boxing generics versus other kinds of generics in an abstract sense. Constraints have already been made on these tradeoffs, for instance fast builds. You seem to be talking about general pros and cons for generics approaches and implementations. It'd be great to start from scratch and ponder all these ideas, but I'm talking about building on what we already have. 

Yes.

I think the reason boxing hasn't been implemented is because it doesn't improve the current Go language enough. You can already use interfaces as such boxes and implement small wrapper around them to make it type-safe...

Generics does improve the language, though, that's why generics is already in the language to some degree with the built-in map, slice, array, channel, etc. types, or the ability to require that both operands for the ==, +, etc. operators are the same type. Those features exhibit the type safety and expressiveness benefits you get with generics. The Go authors themselves have implicitly praised the virtues of generics by including it in a limited form from the outset. An argument against generics is an argument for slices, maps, channels, etc. only working on interface{} types. Who wants that?

 

Is something missing here?

Accidentally sent the email too early :D

http://research.swtch.com/generic

The reason Go doesn't have generics is because the designers of the language try to avoid all the problems listed, at least to some degree.

Sure, you can disagree with this philosophy, which is fine, I completely understand. But, that is the route Go Team has chosen. The only way forward is to find newer more interesting trade-offs and implementations.

Agreed, fair enough, but my point was that, while the Go Team identifies boxing as having a performance cost, it dosn't acknowledge that this cost is no different than using interface{}, as you suggested above, which just boxes the values anyway. If we're already going to be boxing values, we might as well get some type safety and expressiveness out of the deal.

[Jesper Louis Andersen]

On Fri, Mar 31, 2017 at 6:19 PM Michael Jones <michae...@gmail.com> wrote:

There is part of the topic that has always been slightly beyond my grasp. (Maybe I do understand...but just lack absolute certainty.) Maybe others know the answer...

In a template system (which is what I prefer but that's not the point of this email) we have the notion of the TYPE(s) being a formal argument. We presume that the code will compile or fail based on the suitability of the instantiated type. That is, a templated Min would fail on the comparison "<" if the TYPE was "Map[something]something." Call that a lexical fail. 

You can implement a parameterized type as a universal. This means you can take a type, T, as a parameter, but you are specifically not allowed to do anything to T other than to pass it around. In particular, you are not allowed to call any method on T.

The notion is useful in a lot of situations. A container of type Map<K, V> can parameterize over V. That is, you can have the type 'forall V . Map<int, V>' for concrete types K (which is 'int' in this instance). Another example is a function like ' length : forall A . []A -> int' which can count the "size" of a slice for any slice type.

Once you require additional functions, you must supply what amounts to a signature. That is, you must make sure that whenever you introduce your type parameter T, you also introduce a function, 'less' over that parameter T. Different langauges use different notions, but OCaml uses this one:

module type ORD =
  sig
    type t
    val less : t -> t -> bool
  end

We can then implement different modules which "ascribe" to the above module type and "plug them in", specializing our implementation. C++ uses a slightly different notation, but you can achieve the same. Haskell uses a concept called Type Classes, Scala uses Traits and Swift probably uses Protocols. Different notions which lets you acheive what you want.

But all of these notions does not verify any property of your 'less' function. We should obviously require that our 'less' function is total, which amounts to checking the following 4 properties:

less_refl: forall X . less X X

less_anti : forall X Y . less X Y && less Y X => X = Y

less_trans : forall X Y Z . less X Y && less Y Z => less X Z

less_comp : forall X Y . less X Y || less Y X

Some programming languages and proof assistants allows you to require such rules be true for a parameterized type. You are simply, as a programmer, tasked with providing evidence for the truth of the above 4 rules. It does slow down the programmer however, often by a factor of 30 or more.

A slightly simpler solution, which I often use, is to write down the above rules as QuickCheck properties and then verify them by trying out random inputs from a generator. For instance by writing:

-module(less_total).

less(X, Y) -> X < Y.

prop_less_trans() ->
    ?FORALL({X, Y, Z}, {real(), real(), real()},
            ?IMPLIES(less(X, Y) andalso less(Y, Z),
                     less(X, Z))).

And then running 'eqc:module({testing_time, 30}, less_total)' which gives as many random test cases as possible in a 30 second time frame (usually in the millions). If the 'real()' generator periodically generates infs and nans (it should!) then we can eventually find the problem you mention.

In my experience, it is currently feasible to require randomized test cases for your production code, if the code requires high amounts of correctness. Some algorithms, PAXOS-variants I'm looking at you, are almost impossible to get right unless you approach them semi-formally. But requiring such rigor of every piece of code is futile. Not all code requires production quality, and much code is experimental for other reasons. Also, it would severely limit the amount of programmers who could write code---and I think we need more programmers, not less.

The key insight is that you are plugging in your T and your Less under the assumption they work. That is, you are looking at your T and Less as being part of your axioms in the system. You can then write your sorter under those axioms. The reason you want to decouple the notion of T and Less from the rest of the code is manyfold:

* efficiency: you can plug in a better implementation later

* flexibility: you can plug in another implementation later

* correctness: your proof is not required to "dig into" the details of the T and Less implementation.

So in practice, we are just programming under assumptions about the underlying correctness properties. And because we are rather bad as computer scientists, we don't require the necessary rigor of the parts we are using. Mathematicians are in the same boat, but at least they tend to build upon things which has been proven correct, so they are vastly better off.

[Michael Jones]

Thank you for this thoughtful response. It helpful and inspires new thoughts.

When I was a boy learning C (1976 or 1977, UNIX 6th Edition at Bell Labs via "learn") the definition of qsort() was a new idea for me. The exposure of base and stride so nakedly (after BASIC and FORTRAN and LISP and SAIL and ALGOL60 which hid them behind a name) was new and the role of the comparison function was a surprise in terms of API and the approach of passing in the brain as an argument.

At first I did not like it, because it seemed that so many function calls would be expensive and I was sensitized to that. (having used a PDP-8 taught lessons about expensive.) I always was a little iffy about qsort because of this and from time to time would write a custom sort in my programs where the difference made a difference. On the other hand, qsort() always worked and was admirably flexible--serving myself and millions of others now for more than half a century.

I've always looked closely at how people thought about reusable sort utilities and efficiency. On IBM mainframes there was a 3rd party sort utility that generated machine code for your comparison function two human generations before JIT. In SmallTalk it was like qsort since everything had compare methods. This was the "old" way. The newer way is different, having a less() method and using it twice to decide about greater() and equal(). That works too...except when it doesn't...as in the case of quiet and signalling NaNs in IEEE floating point. It might be faster too, since "<" is less decisions than "<" or "=" or ">" and the sort code may be in a tight loop of while less() or while greater() and thereby be faster than the old way.

The qsort() whole-brain as argument works in all cases because the developer knows how to make the subtle decisions. The newer partial-brain method works in those (vast majority) of cases where the implied rest-of-brain is semantically correct. The downside is that the developer may not realize when this is introducing bugs. (Just as in the qsort() case they might not realize the bug there if they don't handle NaNs properly.)

One certain way is to have mathematical statements about meaning, as you list above. Another point of view is to acknowledge floating point as a special thing--not numbers at all--different from integral types because of reserved values with magic meanings when compared, and deal with that specially.

All interesting. Thank you!

Michael