Show HN: Fo: An experimental language which adds generics on top of Go
github.comI liked certain aspects of Go, but lack of generics was a deal-breaker for me. You approached it a way better than I (and many others) did. Instead of arguing on forums you started writing code.
Isn't interface{} a generic?
Noooooo! interface{} is a raw type. It’s like “Object” in java land. It has no meaning in its own right, and needs to be carefully checked whenever you want to actually use it. The proliferation of interface{} across the go ecosystem is really unfortunate, and will be hard to correct once generics are finally supported.
I haven’t dug too far into the Fo code yet, but I’d guess that it’s doing something akin to type erasure in Java, and adding conversions and type checks transparently when compiling down to a go binary. Sort of like how if you ever pop open a class file and dig into it, you’ll never see any references to generics. Everything compiles down to objects in the end with generated type checks.
Well, it is in the literal sense that it enables generic algorithms, just like the one, unnamed static type in all dynamic languages. But of course this is pedantry and no one really means this when talking about generics.
No, interface {} is more like void pointers in C and C++ or Object in C# and Java. It can hold values of any type. One of the major selling points of actual generics is that they provide type safety, but interface {} doesn't provide that.
Go type assertions are quite safe on the other hand, unlike C type casts. The only thing generics will do is to avoid that extra assertion step and the bit of overhead that's involved in that. You could argue wether it will actually increase readability of your code.
Generics (when used/implemented correctly) provide way more than just elimination of type assertions. It provides compile-time type safety, rather than runtime safety. It also provides elimination of the overhead (which isn't trivial, reflection is not inconsequential) and boilerplate code. It also allows you to use the same function/method for many different types without having to resort to boxing everything to an interface/object.
Depending on the implementation, too, generics can be more friendly in other ways. C# emits code for both value types and reference types when appropriate and uses the correct paths as needed.
unsafe.Pointer is the equivalent of C void pointer. interface{} is Any of Object in some other languages.
No, you have to use reflection to determine the type at runtime. Generics use the compiler to prove the type at compile time so that the runtime can forego the much-slower reflective code paths.
No? Generics are type-checked at compile time.
That's reflection not generics. It's mostly the same denotational semantics, but much less efficient performance.
I think it's more than that. You wouldn't commit code that doesn't compile. Your entire organization, however, will troubleshoot the code that fails on runtime in production.
It's not the same semantics at all. Using the top type is not even close to using a type parameter.
Code wins arguments.
For generics:
How do recursive types and self-referencing types work? What about generic types that themselves require generic types? Can type constraints be applied? What do generics look like on interfaces? How about in slices? When compiled, are specialized functions written or is the code shared? How is runtime reflection for type params implemented?
Also, oblig ref of a now-defunct lang on top of Go: https://oden-lang.github.io/
Finally, good work, I hope it was fun! Don't take criticisms too seriously, they are good things (as opposed to silence) and par for the course on this site.
Author here. I've been working on Fo part time for 4 months. Feel free to ask me anything.
Hi there! I worked on something similar a while ago: a compile-to-Go superset that adds some generic functions/methods. You may have come across it: https://github.com/lukechampine/ply
My perspective was that when I find myself wishing for generics in Go, what I really want is not full-blown generic types and functions, but rather a few helper functions like map/filter/reduce, or converting a map to a slice, etc.
Having "true" generics is undoubtedly useful when you really need them, but the Go ecosystem has shown that they aren't strictly required in order to write large, maintainable programs. And you pay for them in the form of misuse. In that sense, I view generics much the same as operator overloading.
Anyway, I ran into some tricky edge cases when working on Ply and I'm curious how you address them. First, Go lets you define local types, i.e. with a function scope instead of top-level scope. You can't define methods on these, nor can you reference them in top-level functions. How does Fo handle the case where I want to call a generic function/method on a locally-scoped type?
The second issue I ran into was imports. I didn't devote a ton of time to this, but it seemed like it could be tricky to properly fetch both Go and Ply packages and pre-compile the Ply packages to Go. How does Fo handle this?
Ply looks really cool! I can certainly understand the appeal of that kind of approach in terms of simplicity, stability, and better interop.
Local types are an edge case I'll need to spend more time working on. The type-checker won't have any problems; the real question is how to generate the appropriate Go code. One solution might be to move the local type into a higher scope during code-generation. Another might be inlining the relevant generic types in the same scope as the local type. Finally, the best solution might just be to say this sort of thing isn't allowed and the compiler will return an error.
Imports aren't supported right now, but it's one of the most important things I need to work on next. It'll be pretty tricky, but I'm confident I can find a solution.
The fortunate thing about the approach I'm using with Fo is that I have complete control over the parser, type-checker, and code-generator. At the cost of having significantly more complexity, I have the flexibility to tackle these sorts of edge cases without relying solely on existing tooling.
Did you consider parameterized packages? The idea is you can declare a set of related objects/types/methods as well as have concrete type specific initialization. E.g.
Then it can be used so:package stack[t] type Type []t func New() Type { return Type{} } ...import s “stack”[int] var s1 = s.New()Just as additional info to others, this is how Ada, Modula-2 and Modula-3 generics kind of work.
I think parameterized packages are a great idea. It would be a light-weight way of getting just a bit of generic code into go.
I made gotemplate to explore that idea
https://github.com/ncw/gotemplate
This requires a round of `go generate` for the actual code generation, but otherwise quite a similar experience.
Having it built in would be great!
Parameterized packages are interesting but they come with their own problems. It can get tedious if I want to use, e.g., a stack with multiple different types. They also lose some of the flexibility that comes with scoping type parameters to any function/method/data structure.
On the other hand writing such packages becomes easier as only two syntax extensions are needed (package header and import). You can easily abstract a package by replacing a concrete type with a package level parameter. More importantly, there is no other mechanism to tie together a bunch of objects, functions, methods etc. to the same parameter types.
I’ve seen this in ocaml and always thought it strange. I think it’s useful, but binding it to a package seems odd since packages are units of code distribution or some such.
It is not strange if you think of objects in OOP as modules/packages you can inherit from.
Think of it as a package macro.
Any plans to add formal sum types (as opposed to interface hacks)?
Definitely something I'm thinking about. It's one of a handful of features that I have in my head but haven't created an issue for.
What does the implementation look like under the hood? What are the limitations of your approach (i.e. generic interfaces) and are they fundamental or just on the todo list?
The Fo compiler parses and type-checks Fo source code and then generates and outputs Go code. It generates a unique concrete type for each usage of a generic type. You can look at the examples directory of the repo to see what this output looks like: https://github.com/albrow/fo/tree/master/examples/box.
Generic interfaces are pretty fundamental IMO. It's something I plan to add to the language before the v1 release.
Here are a couple diffs that leave out the copied code:
https://github.com/albrow/fo/compare/faf3c9f96a8ecd9d17ca968...
https://github.com/albrow/fo/compare/f76c531f839e5e76e5f6b7f...
It's very likely monomorphizing the types, i.e. creating a unique type for each generic invocation.
Can you do ad-hoc or bounded polymorphism? What about recursive types?
Yes, I've already been thinking about constraining type parameters to an interface. Internally, the type-checker considers type parameters to have underlying type interface {}. A constraint on a type parameter should be as straightforward as changing it's underlying type to a specific named interface instead of an empty one. The only tricky bit I can see is thinking about how this would work with generic interfaces or whether we should allow other kinds of type constraints (e.g., union types).
If it considers parametric types to be interface {}, is that a kind of type erasure? I don't know much about Go, but it's my understanding that interface {} types have an extra layer of indirection and are essentially just pointers.
Did you consider incrementing the first letter instead of decrementing when choosing a name?
The name would be "Ho", maybe he did.
Does this have anything in common with Go besides the language syntax? Is it binary-compatible with Go?
It seems to compile ("transpile") to Go, and then invoke Go compiler on the generated source. So I guess that would make it also binary compatible?
Briefly looking at source one can tell it just transforms Fo into Go and invokes go run
Nice work. But, serious question - When going with parameterized types I know from Haskell how you always end up needing one more language extension and always end up banging your head against the wall that separates types and values a little more. At least if you're not a math genius, but probably even then.
And from Java I know that there's a pretty trivial example that showcases how its Generics implementation is unsound when mixed with inheritance.
And I know that the Go maintainers have been hesitant for a long time because they didn't know a good version of Generics to add.
So, is there any version that just works, and never leads the user down any rabbit holes? And that doesn't lead to ever increasing type boilerplate?
Because I've been super happy ever since I decided that worrying about occasional usage of void pointers in C is just not worth my time. And where configurability is really needed, function pointers are totally fine - I don't think there is any need for static polymorphic dispatch (function pointers are probably even preferable, to avoid bloated machine code).
Haskell is a proving ground, so it's picked up a number of ideas that never quite panned out.
I think you can identify a core set of features that are pretty reasonable. I think that'd be type classes, constraints, and functional dependencies.
If they made a handful of extensions standard (GADTs, etc.) it would mostly Do What You Want without a lot of prodding.
> And from Java I know that there's a pretty trivial example that showcases how its Generics implementation is unsound when mixed with inheritance.
I'd be curious to see that. There's a well known limitation that mutable containers (and they're all mutable in Java) need to be invariant, but that doesn't make them unsound.
The type system was also already unsound due to covariant arrays and nulls being a member of all classes, but if you don't break those rules or disable checks, Java generics work as far as I can tell. By "work", I mean I've yet to get a ClassCastException in a fair amount of work with some gnarly Java generics.
And, really, 99% of the boilerplate in Java's typing is that you can't declare aliases for types; that seems to be more due to engrained hostility to syntactic sugar than any technical difficulty.
> So, is there any version that just works, and never leads the user down any rabbit holes?
Most of the "gradual typing" projects for languages like Javascript, Python, Ruby all seem to accomplish what you're looking for, by virtue of the fact that you can just ignore it when you don't want it.
> There's a well known limitation that mutable containers (and they're all mutable in Java) need to be invariant, but that doesn't make them unsound.
I see. Yeah I don't know precisely what these terms mean. If the creators of Generics mistakenly made them covariant, that only goes to show that maybe it's a little too complicated. IMHO.
To be more precise, what we want to do might be too complicated for practical (i.e. relatively simple) type systems to describe. So, why bother at all? Better learn how to structure programs simple enough to make them obviously correct (i.e. mistakes will be obvious and can be easily fixed). Instead of catering to the needs of impractical type systems. I think that's why C is still so popular: It removes most of the boilerplate (i.e. strides for array indexing, arithmetic operators, structs, other ABI things) but gets out of the users way if s/he needs to disregard these constraints for a while.
Even in C, there is a similar problem with const compatibility of pointers of more than 1 level of indirection. Example taken from [1]
[1] https://www.sanfoundry.com/c-tutorials-concept-pointer-compa...const int **pp2; int *p1; const int n = 13; pp2 = &p1; /* not allowed, but suppose it were */ *pp2 = &n; /** valid, both const, but sets p1 to point at n */ *p1 = 10; /* valid, but changes const n */> I'd be curious to see that.
CLU was the first language to implement generics in 1975.
There are many levels of generic capabilities, across multiple languages in about 45 years of research, we don't need the full shop, CLU generics would already be quite usefull versus interface{} everywhere.
With Java I assume you mean that you can create two arrays that are subtypes of each other if their contents are subtypes? i.e., `int[] < double[]`, or `Subclass[] < Superclass[]`?
If so, this is known wrong in the programming language theory community. Java just gets this wrong; if you remove it, generics in Java work correctly, I think.
The only time I find I need generics is when I'm prototyping things and making lots of changes. Node, Ruby, & Python are great for this. In fact, PHP's associative array is really powerful/sloppy since it can be used as a list, hash/dictionary, iterable, or object.
That aside, I don't think I've ever really been bothered by the lack of generics for actual work code.
I've been working full time in Go since 2012. I've never had a use for generics.
You've definitely had a use for it. Maps, chan and slices are all generic types. The built-in functions len(), make(), delete(), new(), append(), etc. are also generic. It's just that you can't define your own generic functions and types.
Ok, this is true :)
One of my first Go programs was based on this image resizer: https://github.com/nfnt/resize/blob/master/resize.go#L109
Do you have any recommendations for how to write this code without generics, without sacrificing performance, and without hundreds of lines of duplicated code?
After only a quick glance at your code, I'd try to tackle it by wrapping my own interface around the different image types (which you could argue the image standard lib should've already done for you). The interface will define CreateWeights and Resize operations. Each implementing type will consist of a struct with an embedded field of each image type you're handling, and passthrough calls to the underlying function you need. This way, your resizing logic can be implemented in one place.
The constructor might be harder to abstract as a single thing since there are variations for each image type... but that's the gist of how I'd tackle it with all of my 10 minutes of experience with your code :-) If this approach is workable, it should end up being clean and testable IMO.
Image allows you to do this more or less. The problem to be solved here is that if you write the resize logic just once, you are accessing pixels from the image via the interface in a tight loop, and most of the time taken by your image resizer is the overhead of that access.
Interesting, you have a point actually. I would have thought that the performance cost of calling through an interface would be negligible, but I'm wrong about that:
https://github.com/golang/go/issues/20116
The issues linked at the end there are interesting reads, and maybe they'll do something about this by Go 1.11.
Having said all that, will an implementation of your code with generics be all that much faster? Or slower? Of course, those are not answerable questions in practice with today's tools :-)
Go 1.11 is already feature freeze and it doesn't seem likely.
> Having said all that, will an implementation of your code with generics be all that much faster?
Likely yes. If generics are implemented via monomorphization, then you can avoid the overhead of virtual calls necessitated by interfaces.
It is possible that the compiler could become smart enough to devirtualize calls through interfaces.
Pretty sure devirtualization is a whole program optimization in the general case, and I don’t see the Go dev team Pershing that in the next couple of years.
> I don’t see the Go dev team Pershing that in the next couple of years
Agreed. But if I didn't mention it, I'm sure someone would have felt obligated to respond with a "well actually..."
How does Go statically type check collections, then? It seems like a pretty common, desirable use-case to me.
I could understand not missing this if you're coming from a dynamically typed environment, but understand that many people aren't.
Go can statically type check hash maps, arrays, and channels. If you want some other container type it must be written with a concrete element type in mind.
Wait, really? The language designers gave themselves (effective) generics and then kicked down the ladder afterwards so that other container implementers couldn't follow? That's hilarious.
Yes. And yes.
Why does it need to be fair? Serious question.
It doesn't, obviously, it's just hypocritical and patronizing.
What do you mean?
void do_stuff(Integer[] integers) { .... } do_stuff(new String[]{"1", "2", "3"}) Compiler: whoops, you passed an array of strings when the API called for an array of integers.
Umm don't? Why are you iterating over unknown types?
Right back atcha.
Try implementing a shared map type where access is protected by a mutex and otherwise works just like Go's builtin map type (which is a generic map type).
Why would I need to re-implement what is already there?
It's honestly hard for me to tell whether you're trolling or not, but all you need to do is compare and contrast the API of the built in map type and sync.Map. One has compile time type safety and the other one doesn't.
If you want a more motivating example, try implementing generic array operations such as reduce, scan, each, reverse etc. Ideally these should be as easy to use as this example:
Rob Pike implemented "ivy", an array programming language, in Go but producing something like an array programming package that can be used from Go (sort of like NumPy for Pyhton) can be very messy to use or implement (even with the use of reflect package).x := reduce(func(a, b int)int{return a*b}, []int[1,2,3]) y := reduce(func(a, b string)string{return a+b}, []string{"a", "b", "c"})bakul's point is that it's not already implemented--Go's existing map doesn't have finegrained synchronization, and you can't write a generic map that does.
Or, for another example, you can't write a generic LinkedHashMap, which is a weird data structure that allows you to write constant time LRU caches, and which I presume Go doesn't have.
And I've read about many people using Go and wishing for generics from day one.
It's mostly a "day 1" concern, is all.
Once you get over it you find that you can do whatever you need.
All turing complete languages can be used to do whatever we need, doesn't mean all of them are usefull to keep using in 2018.
Has anyone worked on Lisp-like macros in Go? Executing code at compile time to emit AST and compile it.. That is what I feel is really missing. Even with strictly a compile-time phase (no run-time macro evaluation) it could be quite useful.
Starting with generics seem to lead down the dark path of C++ template metaprogramming..
I would rather do something like
type StrBox = MakeBoxType!(string)
...and have clean hygienic macros to generate my "generic". Syntax candy can be added to that to get generics...but starting with generics and only supporting that went really really badly for the C++ ecosystem.
Completely agree. Go has parsing and type checking and what not as part of its stdlib. However they choose a code generation approach which is a separate step and often relies on code comments. Even if security fears of compile time execution were allayed, the Go stewards are very unlikely to support altering the very strict-yet-simple grammar for multiple reasons. Macros would be very welcome, but they can't help improve the language if the language is intentionally inflexible.
This is suuuper cool. I've thought of doing something similar for a while, but I tried approaching it from the "generate Go" angle. I also found the Go syntax too tedious to write a parser for (because I've never written a parser before, nor any kind of compiler, so the learning curve was too steep). So I was just going to try to build a simple, expression-based language that compiled to (and interoped with) Go. Unfortunately, I ran out of steam because the learning curve was so steep.
One approach would be to use the existing Go parser packages and modify them to suit your needs. Unfortunately (last time I checked) the standard library packages for this (go/ast, go/types, etc.) differ from the actual packages used by the Go compiler. But they might be close enough to suit your needs.
I recall experimenting with that, but I had a hard time making them work correctly (although I don't recall the details--might've been something to do with their parser DSL or something). The compiler doesn't use the stdlib because the compiler was originally implemented in C, and then they did a mechanical C -> Go translation.
Didn't know that the compiler itself isn't using the same packages after going in a bootstrapped fashion.
Using the existing packages is a great approach as I think that Go standard library has one of the best packages supported for AST/lexing/parsing family, in comparison to Python and Ruby. Haven't worked with Rust.
You really missed the opportunity here to call your language Foo
Or, "Go" but pronounced "Jo" for Generics.
"d͡ʒoʊ".
Or Ge?
A dynamically-typed addon for the language "Fo" could be called "Foo" (to rhyme with "Groo").
I was thinking Feaux or Phở
Or Goo.
but go already has generics https://www.reddit.com/r/rust/comments/5penft/parallelizing_...
Go actually has generics.
Just not for user-defined methods and types.
If you're referring to the map type, that is implemented in plain Go. (Though it does import "unsafe") . There are no generics like you would see in other languages.
https://golang.org/src/runtime/hashmap.go
https://dave.cheney.net/2018/05/29/how-the-go-runtime-implem...
Well, it's not quite fair to say it's "plain Go." The compiler converts expressions like x, ok := m["foo"] into function calls. User-level code can't define syntax sugar like that. Also, the hashmap implementation imports some internal packages, so you can't just copy and paste it. (I would know, because I mostly did copy and paste it for one of my own projects: https://github.com/lukechampine/randmap)
When discussing whether go has generics, "plain go" is a reasonable thing to say.
Besides it's a compiler. It's going to take an input in format X and translate it to an output in format Y. That's just what they do. Syntactic sugar debates aside there's still no generics in there.
"generics" is mostly a matter of type system, not of implementation - as Java and this Go implementation showcase. Indeed, "untyped" generics is trivially implementable in Go, via `interface {}`, you just loes all the type safety (and you have to write more verbose code).
My point is, Go type system DOES support generics, but only for "primitive" types, not for user-defined types.
C++ style (compiler) or Java style (boxing) implementation?
Looks more like C style macro token pasting with sugar.
Is there any support for bounded type variables? Or plans to add them?
Should be called mofo.
It would not be a good idea in Portuguese speaking countries (mold).
Nice work!
Interesting, now all you need to do is add exceptions :)
Perhaps. But if Go itself adds exceptions they're going to have to catch a MassDeveloperExodusException.
The standard reason I see for people wanting exceptions in Go is because they're sick of writing the following:
```go
thing, err := things.New()
if err != nil {
}log.Fatalln(err.Error()) // Or `return err````
But I would argue that it means they're not writing idiomatic go. A good reference for the value of error values is this go blogpost[0]. The HN discussion[1] of that post was also interesting, I like this comment in particular:
> In Go I not infrequently make use of a non-nil value AND a non-nil error. A canonical example of this is the io.Reader interface in Go's standard library [1]. I think it is a very useful idiom particularly when dealing with things where failure is more normal - e.g. dealing with network services, disk IO, decoding partially corrupt exif data from images. Often you want a best-effort at the value even if you run into problems.
Handling every error from every function that returns an error can be verbose. But for that verbosity you get a much easier to understand failure model, and the tools (defer) to handle failures reliably no matter what comes up. Exceptions are part of the reason that RAII is so critical in the C++ world.
Eh, rust’s result type has shown that you can do the same thing in way that is more type safe and more ergonomic.
Sure, if I had proper sum types + pattern matching in go that'd be great. I'm just saying that I'd prefer the status quo over adding exceptions specifically.
Oh for sure.
Exceptions are part of the reason that RAII is so critical in the C++ world.
I don’t think that’s quite true. You definitely want RAII with exceptions, yes, but RAII is extremely useful even without exceptions. I believe it’s common to disable C++ exceptions but still use RAII.
If you have multiple returns from a function (which can very easily happen with manual error checking) RAII is a big win.
> You definitely want RAII with exceptions, yes, but RAII is extremely useful even without exceptions.
Which is another way of saying exceptions are part of the reason for RAII.
Yesssss, but, I still think that’s misleading. It’s like saying ATMs are part of the reason for cash.
On HN, you can quote code by prepending each line with four spaces, but there is no syntax highlighting.
Thanks for the tip, but I avoid that because it ruins readability on mobile IMO.
... and class inheritance, namespaces, smart pointers, move semantics, std::initializer_list, etc.. :)
Golang already has an exceptions-equivalent construct in the shape of panic() and recover(): https://blog.golang.org/defer-panic-and-recover
You’re free to write exception-full code using those constructs, although the community tends to use error return values for the most part.
This is how I understood the use for panics:
https://stackoverflow.com/questions/44504354/should-i-use-pa...
In Java, say, exceptions are the standard for raising a normal error. A class of those exceptions are runtime errors which are equivalent of "panics". Yes you can handle them, but they denote a problem with the program that can't be solved by the interpreter (divide by zero error, etc)> You should assume that a panic will be immediately fatal, for > the entire program, or at the very least for the current > goroutine. Ask yourself "when this happens, should > the application immediately crash?" If yes, use a panic; > otherwise, use an error.If want (and if it makes sense) you can use panics as a control flow mechanism to quickly bubble up errors inside your implementations.
See an example in the standard library itself: https://golang.org/src/encoding/json/encode.go, line 295
What's frowned upon is leaking this out of your package's interface/contract.
Then it strikes me kind of like C++ exceptions. They have them, and it's kinda supported, and there are certain things you shouldn't do with them, so everyone just uses return codes.
Java/Python encourage the use of exceptions as returning error conditions, rather than return error codes.
panic() and recover() are not meant to be used like Java or C++ exceptions.
The phrase "are able to be" is more effectual than the phrase "are not meant to be" when it comes to how people use programming languages in the real world. If it's possible to build a Go system using only panic/recover and defer, just as it is using only interface{}, then there's some people who will use them that way.
Shouldn't it have been called Ho ?
And then we can take this, but put it on the JVM, and we end up with Jo!
Yo?