generics via containers?

[simon place]

i few months back i played about producing some parallel (channel'ed) LINQ type codes, needed much of it, but then thought i'd try and make a general library, for experience, but couldn't quite make it as complete as i wanted.

so reading the recent thread;  https://groups.google.com/forum/?fromgroups=#!topic/golang-nuts/fmmmgg3B1Ic rang a lot of bells, and made me think it might be useful to post an idea i got during this;

have 'range' be able to take an interface of any array, and return interface's of the array elements.

(with basically the same thing for channels, and a range over an interface to a none container just produce a copy.)

example:

func iterator(values interface{}) interface{} {

outchannel:= make(interface{})

go func() {

for _,v:=range values{

outchannel <- v

}

close(outchannel)

}()

return outchannel

}

values could be an interface to an array OR to a channel, which could come from another iterator/generator.

obviously the returned value needs, at some point, to be unboxed by the caller to the type that it knows is in the array/channel, and functions with unboxing could be passed in as required.

possibly a compiler could optimise (avoid) the boxing/unboxing by producing templated code for all the types actually used, and then perhaps choose only to do this for relatively short pieces of code, and not for long elaborate pieces, allowing code caching optimisation when fruitful?

[simon place]

Nobody think this is at all interesting, or just dumb enough, to comment?

even given that function parameters are a collection?

[Ian Lance Taylor]

On Wed, May 22, 2013 at 3:29 PM, simon place <simon...@googlemail.com> wrote:
> Nobody think this is at all interesting, or just dumb enough, to comment?
>
> even given that function parameters are a collection?

I didn't really understand your original post. I don't understand how
it helps address the issues people face with generics. I don't know
what "make(interface{})" means.

For example, one of the major reasons people want generics is so that
they can write a compile-time type-safe container that is not a slice
or a map. Can you give an example of how to write such a thing?

Ian

[simon place]

I didn't really understand your original post.  I don't understand how
it helps address the issues people face with generics.  I don't know
what "make(interface{})" means.

that should have been;    "make(chan interface{})"

 

For example, one of the major reasons people want generics is so that
they can write a compile-time type-safe container that is not a slice
or a map.  Can you give an example of how to write such a thing?

i was only looking at read over iteration, so only range needed to be overloaded for interfaces, for general generic containers the slice access builtin operator would also need to be overloaded for interfaces.

so;

a:=[]int{1,2,3,4,5}

var b interface{}

var c interface{}

b=a

c=1

b[3]=c  // this would replace 3 with 1 into the third element of a.

but currently you can't refer to an element of an array without LOCALLY the type of the contents, but you can currently, using interfaces, write code that actually doesn't need to know. With interface overloads, and by passing into the scope functions that operate on interfaces, you could do anything you like to an unknown, in that scope, slice.

something like this, for a set; 

    func (this *Set) Insert(item interface{}, equals func(interface{},interface{})bool) {

        if !this.Includes(item,equals){   // 'Includes' somehow checks if already in set, also using interfaces

           this=append(this,item) 

           }

      }

 

    s:=Set{make(int,100)}   // or something

    compareInts:=func(a int,b int){return a==b}

    s.Insert(1,compareInts)   // compareInts could 'disappear' into a closure

    size:=len(s)  // since this is outside the 'generic' function this is just the non-overloaded use of len

so actually append() and len() would also need this overload.

if the compiler actually produces code doing the boxing/unboxing thats in your code, doesn't matter, it could general replace it with multiple static versions as required, or not.

[simon place]

correction, not enough thinking about how to attach the function to the Set type, in the example 's' isn't actually an interface;

need to add something more, like

    type Set struct{[]int}

    var s interface{}

[simon place]

and, also need to unbox for the type the function is on, like this maybe;

    s(Set).Insert(1,compareInts)   // compareInts could 'disappear' into a closure

[Dave Cheney]

I'm very confused. Is this a proposal for adding range support to user defined types?

--
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/groups/opt_out.
 
 

[John Nagle]

On 5/22/2013 8:45 PM, Dave Cheney wrote:
> I'm very confused. Is this a proposal for adding range support to user defined types?

I don't get it either. The business with "range" sounds like a
request for Python-type generators. You can do that in Go with
a goroutine.

(There's an interesting optimization opportunity here.
If a goroutine communicates only via channels of length 0,
and with only one other goroutine, it can be compiled
as a coroutine. In that situation, either one goroutine
or the other has control, and a send to a channel always
results in an immediate transfer of control. This provides
all the functionality of generators with low overhead and
existing Go syntax.)

John Nagle

[Dan Kortschak]

There has been quite a bit of discussion of this idea over at
golang-dev, just a little while ago.

[simon place]

I'm very confused. Is this a proposal for adding range support to user defined types?

no, its to overload 'range' to accept an interface of an array, nothing else, range would in this case return what it would have done if the array hadn't been in an interface, as another interface.  This bypasses the actual type, which wouldn't be know locally in a generic function, and so normally would be a show stopper.

this way you can write generic functions.

the confusion is probably me getting carried away, (the Set example), and trying the same trick for other array built-ins ( [:],len,append) to get full generic containers.

[Gregg H.]

so you're saying modify range so that this works without explicitly making v an int?

a := []interface{}{1, 2, 3}

for _,v := range a {

  fmt.Println(v + 10)

}

--

[Nico]

Just for fun, here's a proof of concept of a type-safe set using reflect:


http://play.golang.org/p/yCUCRTNYYB


package main

import (
"fmt"
"reflect"
)

func main() {
var set struct {
Set
Add, Rem func(float64)
}
makeSet(&set)
set.Add(3.14)
set.Add(42.)
set.Rem(42.)
fmt.Println(set.Set)
}

type Set map[interface{}]struct{}

// Input:
// *struct{Set; Add, Remove func(int) T}
// where T is an arbitrary type
func makeSet(stptr interface{}) {
// get struct fields and types
st := reflect.ValueOf(stptr).Elem()
st_set := st.Field(0)
st_add := st.Field(1)
st_rem := st.Field(2)

// make Set
st_set.Set(reflect.ValueOf(make(Set)))

// make Add
adder := func(in []reflect.Value) []reflect.Value {
k := in[0]
v := reflect.ValueOf(struct{}{})
st_set.SetMapIndex(k, v)
return []reflect.Value{}
}
st_add.Set(reflect.MakeFunc(st_add.Type(), adder))

// make Rem
remover := func(in []reflect.Value) []reflect.Value {
k := in[0]
var v reflect.Value
st_set.SetMapIndex(k, v)
return []reflect.Value{}
}
st_rem.Set(reflect.MakeFunc(st_rem.Type(), remover))
}

[simon place]

so you're saying modify range so that this works without explicitly making v an int?

a := []interface{}{1, 2, 3}

for _,v := range a {

  fmt.Println(v + 10)

}

no, that's an array of interfaces, each of which just happens to be an int, and this is already handled and would have major repercussions if changed.

what i'm talking about is what range currently throws out, an interface that is an array of fixed type

a:=[]int{1,2,3,4,5}

var b interface{}

b=a   // here a is 'boxed' into the interface

for _,c:=range b {   // this currently is a type violation

      fmt.print(c(int))   // c needs to be unboxed, because its an interface, but this isn't the generic part

     }

this only works to make generics, because c could be handled, as an interface, without caring whats in it, any time you do care, it will need to be manipulated by function(s) that take an interface parameter, that are passed into the scope, or, directly passed out to be handled by the caller that knows what type is in the interface. 

[simon place]

>
> For example, one of the major reasons people want generics is so that
> they can write a compile-time type-safe container that is not a slice
> or a map.  Can you give an example of how to write such a thing?

Just for fun, here's a proof of concept of a type-safe set using reflect:


http://play.golang.org/p/yCUCRTNYYB

reflection can always do generics, just expensively, and it seems to me generics are more about speed than type safety, by enabling compilation of type specific code.

[Nico]

On 23/05/13 20:15, simon place wrote:
>
> reflection can always do generics, just expensively, and it seems to me
> generics are more about speed than type safety, by enabling compilation
> of type specific code.

It seems everyone expects generics to solve all their problems.

Ian brought up the example of type-safe containers, and I just wanted to
check whether generics are really necessary. They are not. Yes, reflect
is slow, but the message I would take from this example is that we don't
need generics for type-safe containers.

If the language were to include a few more builtins (as append and
copy), implementing common algorithms over containers, then there
wouldn't be such a need for generics.

Let's say, we had a builtin sort like this:

sort([]T) // only for those T that <= is define
sort([]T, func less(a,b T) int) // for any T

and maybe some

filter([]T, func cond(a T) bool)

and

apply([]T, func process(a T) T)


I think this builtins would encourage the use of interfaces instead of
generic types.

[simon place]

yes, but these wouldn't have helped me with the original LINQ library.

and 

although i do think that JS's array stuff, (map,reduce,every,any,foreach,some,filter etc), is all very nice and fast, having these as builtins kinda feels like a scripting language thing, something that it had to do so as to be reasonably fast, in the end the Go runtime should be able to be written in Go.

[Ian Lance Taylor]

On Thu, May 23, 2013 at 1:34 PM, Nico <nicolas...@gmail.com> wrote:
>
> Ian brought up the example of type-safe containers, and I just wanted to
> check whether generics are really necessary. They are not. Yes, reflect is
> slow, but the message I would take from this example is that we don't need
> generics for type-safe containers.

In fairness, I said compile-time type-safe containers. Using reflect
gives you run-time type-safe containers. That is, using reflect, the
containers are type-safe at runtime, but they aren't type-safe at
compile time.

Ian

[Nicolas Riesco]

The example I provided it's compile-time type-safe (it comes with the trick of using a struct).

[Nicolas Riesco]

On Thu, May 23, 2013 at 11:06 PM, simon place <simon...@googlemail.com> wrote:

yes, but these wouldn't have helped me with the original LINQ library.

we wouldn't need a LINQ library if those builtins were available 

[Ian Lance Taylor]

Sorry, I missed the reference back to the earlier message. That is a
clever approach.

Ian