Code generation to replace generics?

[Nate Finch]

So, I saw yet another post about generics in Go, and I had the same thought I'd had before... could we simply use code generation to replace generics?

Most template / generic code is simply there to prevent copy and paste of code. So instead of two methods that are exactly the same except for the types of the arguments/returns, you instead write it once with a variable type.

In my experience, most of the time, any one product tends to use a generic function / class for only a few concrete types, such as a few different business objects and string / int / guid.  This seems like a perfect problem to solve with code generation. There's no real difference between a generic function that can work on two types and two identical functions that have different type signatures... except that it's a maintenance headache, since any changes to one need to be copied to the other (in theory). If you're simply generating the code for both function bodies, then you only need to fix the code in one place (the source) and it gets propagated to all the places where it's generated.

I don't have all the specifics nailed down yet, but here's my initial thoughts

My idea is this: write the generic function that uses an interface. If it's a function that can work on anything, then you use interface{}.  This is real code that has to compile.

There is a way to mark the code as generic and what parts of the code are to be replaced.

Then whenever you use a generic version of the method, you mark the type that it uses, and run the code generator.  If that version of the function already exists, there's nothing to do.  If it doesn't exist, then a new one is created.

(function cribbed from this post)

func Map__interface(xs []interface{}, f func (x interface{}) interface{}) []interface{}{

    result := make([]interface{}, len(xs))

    for i,x := range xs {

        result[i] = f(x)

    }

    return result

}

The double underscore "__" prefix tells the code generator that text following the underscores is what should be replaced in the following function (interface{} being a special case... normally it would be just an exact word match for an existing interface).

so then you could write something like

xs := []string{}

mapped := Map__string(xs, func(x string) { return strings.ToUpper(x) })

and when the code generator is run, it would see the use of Map__string and notice there's no current implementation and output this in map.go:

func Map__string(xs []string, f func (x string) string) []string{

    result := make([]string, len(xs))

    for i,x := range xs {

        result[i] = f(x)

    }

    return result

}

Now... as for how all this would be built, if there's a better way to do it than a separator, etc... all up for discussion.  This is just an idea in my head right now and wanted to know what other people thought of it initially.

-Nate

[Dmitri Shuralyov]

This might be viable if the code generation is made to be completely automatic, so that there is never any manual unneeded maintenance work to be done. This is very important.

[Ian Lance Taylor]

On Mon, Dec 31, 2012 at 2:07 PM, Nate Finch <nate....@gmail.com> wrote:
> So, I saw yet another post about generics in Go, and I had the same thought
> I'd had before... could we simply use code generation to replace generics?

I believe it is doable, and it has been suggested before. I think it
is somewhat limiting. It becomes difficult to write a generic
function that takes a generic function as an argument. When running
the debugger you see strange names that do not appear in your source
code. Likewise when using type reflection on generic functions.

Ian

[Limbo Peng]

On 12/31, Nate Finch wrote:
> Then whenever you use a generic version of the method, you mark the type
> that it uses, and run the code generator. If that version of the function
> already exists, there's nothing to do. If it doesn't exist, then a new one
> is created.

Two questions:

1. Should the generated source replace the original one?
2. Can this code generation step be automatic? (maybe providing a replacement for "go build"?)

[bryanturley]

I think he meant runtime code generation.
Which is what you would need to have a single copy of a generic definition (not template) throughout any runtime loaded libraries without using boxing.

[Nate Finch]

Nope, I meant pre-compile time generation. Runtime generation removes type safety and doesn't get us much more than using interface{} and casts.

It would be a manual step before compile that writes out to the file new function definitions with the appropriate types replaced and then you could compile and run normally. There would be no problem with the debugger or anything during runtime because there would be actual code on disk for every function.  What the code generation does is let you have one definitive version of the code and then replicate it with carefully controlled changes to simulate templates (generics).

[bryanturley]

On Tuesday, January 1, 2013 11:45:58 AM UTC-6, Nate Finch wrote:

Nope, I meant pre-compile time generation. Runtime generation removes type safety and doesn't get us much more than using interface{} and casts.

It would be a manual step before compile that writes out to the file new function definitions with the appropriate types replaced and then you could compile and run normally. There would be no problem with the debugger or anything during runtime because there would be actual code on disk for every function.  What the code generation does is let you have one definitive version of the code and then replicate it with carefully controlled changes to simulate templates (generics).

So you really meant templates and not generics?
I may have my mental definition wrong but I have always considered them separate, even though they target mostly the same problem.
I was actually wondering why someone hasn't written an external templater for go already, since so many people can't seem to live without some form of generics.

gotemplate && go build  or a makefile so hard?
It would also allow for experimentation without corrupting core go.
But I cannot see a world where c++ style templates in go do not lead to the same problems c++ style templates already cause.

[Limbo Peng]

On 01/01, Nate Finch wrote:
> It would be a manual step before compile that writes out to the file new
> function definitions with the appropriate types replaced and then you could
> compile and run normally. There would be no problem with the debugger or
> anything during runtime because there would be actual code on disk for
> every function. What the code generation does is let you have one
> definitive version of the code and then replicate it with carefully
> controlled changes to simulate templates (generics).

A few issues brought by this precompiling approach:

1. Suppose we have main.go and the generated file is main_generated.go - currently "go build" will take all .go source files (in current package), which means both main.go and main_generated.go will be sent to the compiler - can it compile in such situation?

2. If a precompiler is required, then this package cannot be installed via "go get" (maybe trivial if it is used "in-house" only)

[Nate Finch]

Templates is a more accurate definition of the feature I'm proposing, yes.  However, in practice, there's little difference between how generics and templates are used, except in quite advanced programming techniques (that are generally better avoided anyway).

The reason I didn't use the word template is because fewer people write C++ these days, and I didn't want to anyone to confuse them with text / html templates (a la {{.Something}} in Go).

I guess I didn't explain clearly enough what I meant by code generation. I think people are too used to reflection and the runtime backflips we do to get stuff to work, and forget that you can write code that writes and maintains code for you. When I say code generation, I mean source code generation - UTF8 text on disk which is compiled by the Go compiler just like any other code. It just wasn't written by a guy directly banging on a keyboard.

Yes, it would be running a build script that does this code generation first, and then running go build (likely you'd have the script just also run go build).

[Michael Jones]

I am a huge fan of metaprogramming in all guises, ranging from M4/CPP like efforts to the extreme and obscure. Small taste here of using compile time processing for various simple but onon-trivial functions:

http://www.codeproject.com/Articles/19989/Template-Meta-Programming-and-Number-Theory

Eager to see Go able to have some fruits here. I presently just use M4.

--
 
 

--

Michael T. Jones | Chief Technology Advocate  | m...@google.com |  +1 650-335-5765

[Nate Finch]

1.) The trick is that the generated code goes in the same file.  So at the top of the file you have your template code that the preprocessor reads, and it rewrites the file, adding more code after that, which is the expanded template code.
2.) You can absolutely install the code using go get. The generated code becomes part of the package. You would check in the generated code into source control, for example. You only need to run the preprocessor if you change the template or add new uses of the templated code. The preprocessor is actually external to the code that is in whatever package you're writing.

Let me give an example - you write a package that sends emails.  Inside that package you want a generic function that'll do some transform on various lists of email addresses. You have the base function, which looks like a java or C# generic function, or a C++ templated function, something like this:

func Transform(addresses []Address) []Address {

  // do stuff

}

you then need an implementation of this that takes a slice of ExchangeAddress and one that takes a slice of GmailAddress:

func Transform(addresses []ExchangeAddress) []ExchangeAddress {

  // same do stuff as above, but with ExchangeAddress

}

func Transform(addresses []GmailAddress) []GmailAddress {

  // same do stuff as above, but with GmailAddress

}

All this code is checked into source control. The bottom two functions were generated by the code generator, based on the original template.

If someone wanted to modify your package, and add more implementations of Transform, they'd need the code generator.  If they just want to use it as is, they'd build it as normal.

-Nate

[Patrick Mylund Nielsen]

If it were added, the "compiled" code should go in pkg/ or bin/ during the compilation stage, not in the files checked into the repo. The below could work if no such support is added, but it seems just shy of checking .a and .o files into the repo to me.

--
 
 

[Rui Maciel]

On 01/01/2013 05:54 PM, bryanturley wrote:
> But I cannot see a world where c++ style templates in go do not lead to the
> same problems c++ style templates already cause.

What problems are you referring to?


Rui Maciel

[Tamás Gulácsi]

Gotgo already does this templating.

[Kyle Lemons]

I anticipate that, when go/types is complete, an even more powerful version of gotgo will be possible.

On Tue, Jan 1, 2013 at 1:34 PM, Tamás Gulácsi <tgula...@gmail.com> wrote:

Gotgo already does this templating.

--

[Michael Jones]

Many interesting uses of macro/preprocessing/metaprogramming involve generation of program text from fragments that are not valid program text. It seems that these situations will always require something outside the normal parsing/type situation.

--
 
 

[Nate Finch]

I hadn't seen that. I looked at it today and it essentially does what I proposed, though in a way that seems very cumbersome. I would not, for example, put the template code into a .got file. I'd just leave it in its own .go file.

[Tim Harig]

On Tue, Jan 01, 2013 at 10:50:41AM -0800, Michael Jones wrote:
> Eager to see Go able to have some fruits here. I presently just use M4.

I have wondered how many people might start doing that for other reasons.
Go overs very little in the way of conditional compilation, other than
for platform replacement. Sometimes you want users to be able to remove
features from the build that require libraries that they do not want, or
cannot be, installed on their systems. I once resorted to using M4 with
Ada for similar reasons.

The downside to using front ends for code production, is you end up having
to deal with build script madness.

[Michael Jones]

...and hard looks from Rob Pike. ;-)

--

[Limbo Peng]

On 01/01, Nate Finch wrote:

> I hadn't seen that. I looked at it today and it essentially does what I
> proposed, though in a way that seems very cumbersome. I would not, for
> example, put the template code into a .got file. I'd just leave it in its
> own .go file.

This is the issue that I've been considering. If you put the template code in a .go file, then you cannot use "go build" for current package, unless you move it away when compiling, otherwise the template code and the generated code will be sent to compiler at the same time.

If, as you said before, just replace the template code with the generated one, then it becomes difficult to modify the template - where do you save the template for later use?

[Limbo Peng]

On 01/01, Michael Jones wrote:
> Many interesting uses of macro/preprocessing/metaprogramming involve
> generation of program text from fragments that are not valid program text.
> It seems that these situations will always require something outside the
> normal parsing/type situation.

This, however, reminds me of Java - the language itself cannot be changed as people expect, so they invent AspectJ for rescue.

[Nate Finch]

Ahh but you see -  the template code is valid go code.  In the template you use interface{} or a custom defined interface.  The template code then can call methods on the interface (or in the case of the empty interface -  you can't).  That's actually what ensures the generated code will also compile -  the template code had to compile.

You put markers in comments around the template to let the code generator know it's a template.

Sorry no time for an example right now,  I'll write one out in the morning.

[Dan Kortschak]

How does that differ from just using interfaces? And if it does differ, how does user know about the generated func in a way that would allow the un-generated code to compile?

--
 
 

[Kyle Lemons]

I envision things more along the lines of the ability to examine the *calling* code and know the types so that type-safe implementations can be generated.  At the top of my wish list, though, would be the ability to take something like sort.Sort and generate an inlineable instantiation of the function (aka using the concrete type instead of sort.Interface).

[DisposaBoy]

I think you may be heading down the wrong path here. i.e. you see an existing similar project but but. at least in my opinion seem to be focusing more on the implementation . I'm not in a position to do any searching but IIRC the gotgo method is essentially a deadend . the author shared his thoughts on the issue somewhere on this list I think and it may be even turn out that they are issues you hadn't even thought of

[Philipp Schumann]

It's an interesting idea. Your "generic code" must be compilable by using interface{} as the replacement-name that is usually <T> or __T__ or some such. But this might fail in a number of generics use-cases.

Say, I want to use the + operator in a generic function because I know I will only instantiate it with numeric types and string. The template now wouldn't compile with interface{} anyway. Yet a template file such as .got that gets processed pre-compilation for types float64, uint8 and string -- no problem.

Writing a simple template preprocessor to suit just your needs in Go is so simple and trivial, I don't see a need for Go itself to provide a pre-fab solution here. When I looked at gotgo, I "didn't feel like learning its ways", so I built a simple really workable template preprocessor into my own minimalistic Go build tool in probably about an hour:

https://github.com/metaleap/go-buildrun

Use this, use gotgo, use gotemplate, roll your own... all of these approaches will take less than an hour to get going, which is far less time than it would take to study all the "Go generics" threads that have accumulated in this mailing list over the years...

[Nate Finch]

Code generation to solve generics is not a great solution, I agree. Far better would be an addition to the language to support it, in one way or another. But I think we can do better than what has been done before, and make it easier to use, until such a time as generics make it into the language (which may not be soon). Changing the implementation can make it much less of a headache to work with, which can make the difference between a project that is useful and one that just never gets used.

I think the problems the original author mentioned are fixable. Based on my limited searching, the main one seemed to be that the code was compiled into the same package as the template, so it wouldn't have access to the types from your package... for example, if you had an AVLTree template, if you wanted to make an AVLTree for your Customer type, the AVLTree package wouldn't know about that type, so it couldn't compile with that type in its code. This is pretty easily solved by just generating the AVLTree code in the same package as Customer, or in a package that references Customer.

[Nate Finch]

I doubt you'll ever get C++ style templates in Go (i.e. ones that can use built in operators like + in the templated code). I see that as in the same thoughtspace as operator overloading, which the Go team seems to not be in favor of. Generics in C# and Java do not support that sort of generic code, and notably neither of them support operator overloading either. I see Go generics as likely to be more similar to these generic implementations than C++'s templates... but I guess we'll have to see what the Go team comes up with.

You're right that this is not a hugely difficult project, and that simple versions could be whipped up in a minimum of time. However, I think that the complexity increases considerably as you try to make it easier for the programmer to use.

Anyway, maybe I should just go write some code and stop talking about it. And if no one feels that it is useful, then it won't get used.

[Limbo Peng]

On 01/02, Philipp Schumann wrote:
> Use this, use gotgo, use gotemplate, roll your own... all of these
> approaches will take less than an hour to get going, which is far less time
> than it would take to study all the "Go generics" threads that have
> accumulated in this mailing list over the years...

Good point. Just wonder if such an approach is feasible in *big* teams...