Monday, January 3, 2011

GoLang Proposals

Go is a very new programming language, barely a year old. Since its initial release, it has become an instant success, almost overnight. Google designed Go primarily for high-level systems programming. Since then, Google has replaced a few of its internal servers with custom Go servers. I believe this success is driven by the simplicity of Go, and its special features which focus on concurrency.

Compared to C, it has many more features so I consider its features a strict superset of C's features. Compared to C++ however, Go is very different, possibly described by a classic Venn-diagram in which Go's features and C++'s features intersect, but both have features the other doesn't. For example, method overloading can be accomplished in both languages, but in different ways.One feature that C++ has enjoyed is that of templates, which do not exist in Go. This requires that algorithms that can work on multiple datatypes be written out each time, which negatively affects readability and maintainability. While adding full-fledged C++ templates to Go is certainly possible, I believe we need to look at other languages for guidance.

Java started out as a simple language. Java's success is due in part to this simplicity, however, language designers at Sun (now Oracle) decided very late in the process (2004, a full 9 years after its introduction in 1995) to add generics to the language. In addition, they chose to use C++ syntax, which has conflicts with the shift operator (>>). In my opinion, avoiding the introduction of generics has divided the community, effected incompatibilities, and complicated the standard library with multiple versions of the same function.

Depending on your definition of generics, they may have different kinds of parameters. The most intellectually challenging are Agda generics, which imply that generics are just functions which return types, and any function may take types as a parameter. C++ templates are similar to this kind of generics, but make a distinction between usual functions and functions returning types. Since this is a minority when it comes to generics implementations, we will not consider this kind of generics in the remainder of this article.

The most prevalent form of generics are found in Java and Haskell, which only allow types as parameters. From this point of view, the only generic type found in Go today is the map type, so it will be the primary example used.


Proposal #1: Add first-class types

This is doomed for failure, because it requires Agda-like (or C++/RTTI) semantics, but it is worth discussing. It is the proposal which requires the least syntactic changes, even if it might be the most intellectually demanding on semantics and runtime. If Go did have first-class types, then we could define the Map type as follows:

func Map(KeyT .(type), T .(type)) .(type) {
type mapT []struct{
hash int
key KeyT
value T
}
return mapT
}

Using this proposal, we can simulate map[KeyT]T with Map(KeyT, T). As you can see, type parameters are indicated with the ".(type)" token as is found in Go type-switch statements. One advantage of this system would be that it could be used to define Array(n, T) and Matrix(m, n, T) which would be impossible to define using more restrictive generics. Other functions that could defined using this proposal are new and make, which take a type as their first parameter. Here is a summary of the related changes to the Go specification:

Result        |= ".(type)"
ParameterDecl |= TypeName ".(type)"
Expression |= TypeName

In addition to these syntactic changes, a few paragraphs of rules and discussion maybe required.


Proposal #2: Add 'generic' (or '_Generic') keyword

This is the crux of this blog article. Since first-class types require that types and objects be intermixed, it requires that every parameter be suffixed with .(type), but with the generic keyword, we can enforce that every parameter be a type parameter (Java/Haskell-style generics). This makes declarations much easier to read, and has provides a much more structured style.

generic Map[KeyT]T []struct{
hash int
key KeyT
value T
}

Using this proposal, we can simulate map[KeyT]T with Map[KeyT]T. As you can see, this is very close to the standard built-in map type, with the obvious case difference. Here is an overview of the associated changes to the Go specification:

TypeLit       |= GenericType
TopLevelDecl |= GenericDecl
GenericType = "generic" GSignature Type
GenericDecl = "generic" identifier GSignature Type
GSignature = GParameters identifier
GParameters = "[" [ GParameterList [ "," ] ] "]"
GParameterList = GParameterDecl { "," GParameterDecl }
GParameterDecl = identifier

Having considered adding generic syntax to LiteralType, I don't think it would work well with literal syntax or semantics. What would such a literal mean? Would it simply be syntactic sugar for the base-type of the generic type with all the free variables filled in? If all that would be gained is syntax sugar, then I don't see the value of adding it to literal syntax.

This generics model also allows more than one parameter inside the brackets, but it also requires at least one parameter after the brackets, which is also very similar to how generic types work in Haskell, since the prevalence of monads has made the last parameter more important than the others. This generics model is also much closer to Go's existing map type, the only problem now is that the first letter is uppercase "M" whereas the built-in map type has a lowercase "m". This leads us to our next section, which discusses another proposal.


Proposal #3: Add 'attrib' (or '_Attrib') keyword

This proposal combines two issues into a single solution. The first issue is nonessential attributes (such as alignment, packing, etc.) for which GCC uses the __attribute__((id)) syntax. The second issue is the public/private convention in Go which may be an issue in the future if it is used to implement existing APIs such as POSIX, which require lowercase external symbols. The solution I propose to both of these issues are a new syntax: _Attrib(id), which allows simple annotation of declarations in such a way as to override normal Go semantics. Consider two such attributes: public and private, which would allow us to define the built-in map type as follows:

generic attrib(public) map[KeyT]T []struct{
hash int
key KeyT
value T
}

Using this proposal, there would be no difference between this defined type and the built-in map type. This would allow very small Go compilers which need only handle arrays and slices, and leave the map type, and possibly other built-in functions such as cap and len to a library implementation.

The syntax was designed to force the attrib specifier immediately before the identifier, to make it clear which identifier it is referring to. The changes to the MethodDecl production are questionable, and require more consideration and discussion. I have also considered moving AttribSpec to before the keywords which would simplify the grammar significantly. This is the summary of all the required extensions to the Go specification.

ConstSpec    |= AttribSpec IdentifierList 
[ [ Type ] "=" ExpressionList ]
TypeSpec |= AttribSpec identifier Type
VarSpec |= AttribSpec IdentifierList
( Type [ "=" ExpressionList ]
| "=" ExpressionList )
MethodDecl |= "func" Receiver AttribSpec
MethodName Signature [ Body ]
FunctionDecl |= "func" AttribSpec identifier
Signature [ Body ]
GenericDecl |= "generic" AttribSpec identifier
GSignature Type
AttribSpec = "attrib" "(" identifier
[ "(" ExpressionList ")" ] ")"

Proposal #4: Add 'pragma' (or '_Pragma') keyword

Another method used for nonessential attributes are top-level pragmas. Using pragmas, you can specify information to be used on a per-file or per-package basis. This could be a useful and simple extension to the language that could bring existing GCC syntax to Go compilers. Here is an example of using pragmas in a Go source file:

pragma("GCC poison strdup")
pragma("DSGO prefix pthread_")

Other possibilities for pragmas are to use Go with OpenMP, even though it might sound funny at first, because most of the features of OpenMP are already in Go! However, we should never underestimate what people will do with compilers, given the chance. Here is a summary of the associated extensions to the Go specification:

TopLevelDecl |= PragmaDecl
PragmaDecl = "pragma" "(" string_lit ")"

Conclusion

We have reviewed four possible extensions to the Go programming language, which may not seem in the spirit of Go right now, but over time may become necessary. If Go is to be used for serious projects, developers may come to expect these features, rather than hope for them. As we have learned from Java, if we wait for too long to introduce new features to Go, it may polarize the community, which would be an undesirable outcome for everyone.

3 comments:

  1. Are you the author of language-go - A Haskell library for Go code analysis and generation ?

    If so, i have a question or two. Is it possible to contact you somehow?

    ReplyDelete
  2. Hi Andy,

    It turns out that I was able to contact you with my language-go questions. Thank you for your reply to them.

    ReplyDelete
  3. Go does not have only one generic type. It has at least five:

    * pointers
    * channels
    * arrays
    * slices
    * maps

    ReplyDelete