Re: [go-nuts] Re: Algorithm Club

[Jesper Louis Andersen]

On Fri, Mar 31, 2017 at 6: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.
>
>
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
can parameterize over V. That is, you can have the type 'forall V .
Map' 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.

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

Re: [go-nuts] Re: Algorithm Club

[Will Faught]

On Sat, Apr 1, 2017 at 12:11 AM, Egon Elbre  wrote:

> On Sat, Apr 1, 2017 at 1:42 AM, Will Faught  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.

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

Re: [go-nuts] Re: Algorithm Club

[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

On Friday, March 31, 2017 at 1:21:02 PM UTC-4, Michael Jones wrote:
>
> yes
>
> On Fri, Mar 31, 2017 at 12:30 PM, Ian Davis  > wrote:
>
>> 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
>>
>> -- 
>> 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 
>

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

Re: [go-nuts] Re: Algorithm Club

[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{}) }

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
>
> On Fri, Mar 31, 2017 at 2:46 AM, Egon  
> wrote:
>
>> 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.
>>  
>>
>>>
>>> On Wednesday, March 29, 2017 at 9:18:01 PM UTC-7, Egon wrote:

 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, 

Re: [go-nuts] Re: Algorithm Club

[Jan Mercl]

On Fri, Mar 31, 2017 at 6:20 PM Michael Jones 
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(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

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

Re: [go-nuts] Re: Algorithm Club

[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

On Fri, Mar 31, 2017 at 2:46 AM, Egon  wrote:

> 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.
>
>
>>
>> On Wednesday, March 29, 2017 at 9:18:01 PM UTC-7, Egon wrote:
>>>
>>> On Thursday, 30 March 2017 03:15:33 UTC+3, Will Faught wrote:

 Egon:

 >See https://docs.google.com/document/d/1vrAy9gMpMoS3uaVphB3
 2uVXX4pi-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 

Re: [go-nuts] Re: Algorithm Club

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

>
> On Wednesday, March 29, 2017 at 9:18:01 PM UTC-7, Egon wrote:
>>
>> 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  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 

Re: [go-nuts] Re: Algorithm Club

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

On Wednesday, March 29, 2017 at 9:18:01 PM UTC-7, Egon wrote:
>
> 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  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 

Re: [go-nuts] Re: Algorithm Club

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

Re: [go-nuts] Re: Algorithm Club

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

On Tue, Mar 28, 2017 at 12:28 AM, Egon  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+unsubscr...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: Algorithm Club

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

On Mon, Mar 27, 2017 at 3:11 PM David Collier-Brown 
wrote:

> 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
>
>
>
> On Monday, March 27, 2017 at 2:40:12 AM UTC-4, Egon wrote:
>
> 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.
>
>
> 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, 

Re: [go-nuts] Re: Algorithm Club

[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 



On Monday, March 27, 2017 at 2:40:12 AM UTC-4, Egon wrote:
>
> 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.
>
>
>> 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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: Algorithm Club

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

On Sun, Mar 26, 2017 at 11:40 PM Egon  wrote:

> 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.
>
>
> 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.*
>
> --
Michael T. Jones
michael.jo...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: Algorithm Club

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


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

Re: [go-nuts] Re: Algorithm Club

[Egon]

On Sunday, 26 March 2017 05:15:10 UTC+3, Bakul Shah wrote:
>
> 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 { {} } 
> 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. 
>

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

Bakul 
>
> On Sat, 25 Mar 2017 20:57:51 EDT David Collier-Brown  > wrote: 
> > 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 
> > 
> > 
> > On 24/03/17 11:21 PM, Michael Jones wrote: 
> > > 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   
> > > > 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 

Re: [go-nuts] Re: Algorithm Club

[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 { {} }
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

On Sat, 25 Mar 2017 20:57:51 EDT David Collier-Brown  
wrote:
> 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
> 
> 
> On 24/03/17 11:21 PM, Michael Jones wrote:
> > 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  > > 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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: Algorithm Club

[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


On 24/03/17 11:21 PM, Michael Jones wrote:

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

--
Michael T. Jones
michael.jo...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Re: [go-nuts] Re: Algorithm Club

[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 
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+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
-- 
Michael T. Jones
michael.jo...@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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.