How to implement generics? #229

Activity

1. cosmos72

   added

   enhancement

   on Feb 16, 2021
2. cosmos72

   self-assigned this

   on Feb 16, 2021
3. cosmos72

   changed the title [-]Implement generics[/-] [+]How to implement generics?[/+] on Oct 28, 2021
4. cosmos72 commented on Oct 28, 2021

   

   cosmos72

   on Oct 28, 2021

   Last edited by cosmos72

   MemberAuthor

   More actions

   A fundamental issue came to my mind:
   a sufficiently sophisticated interpreter can implement generics, in the sense that code passed to the interpreter can use generics, and the interpreter can implement the correct semantics for it. For example, gophernotes' underlying interpreter "gomacro" already has partial support for them, and implementing what's missing is not overly complicated.

   But generic code in third-party libraries, which are currently compiled with Go toolchain and then loaded in gophernotes as shared libraries, pose a much more difficult challenge:
   Go toolchain compiles generic code on-demand, i.e. only if it's instatiated and only for the types it is instatiated on. Go toolchain has no way to instantiate generic code at runtime, when an interpreter (or any other program) may need it.

   The issue is easier to understand on a concrete example:
   let's suppose that the hypothetical Go module example.com/go/stack contains the following:

   type Stack[T any] {
      // unexported fields
   }
   
   func (s *Stack[T]) push(T elem) {
     // ...
   }
   
   func (s *Stack[T]) pop() T {
     // ...
   }

   when you type import "example.com/go/stack" in Gophernotes, it internally uses the Go toolchain to download and compile the module as a shared library.

   If Stack was a non-generic class, the shared library would contain the reflect.Type for Stack, which allows creating Stack objects and calling their methods: that's exactly what an interpreter needs.

   Instead our Stack[T] is a generic class: in order to do anything with it, it must be instantiated first. This means a reflect.Type for Stack[T] does not exist and cannot exist.
   Only its instantiation on some concrete type, as Stack[int] or Stack[MyClass], can have a corresponding reflect.Type.

   And here comes the issue: when import "example.com/go/stack" is entered in Gophernotes, there is no way to know in advance which concrete instantiations of Stack[T] will be needed.
   Maybe Stack[int] ? Maybe hundreds of other instantiations, possibly using as T a type that does not exist yet, and will be defined later?

   There's no way to know in advance the instantiations a user may ask for. So there's no way to compile them in advance.

   This leaves us with two alternative solutions - and I am tempted to call them workarounds rather than solutions, because both have significant drawbacks:

   1. every time the user tries to use a type Stack[X], where X is a concrete type, instantiate it by invoking Go toolchain, compiling a shared library, and loading it. It will be extremely slow and consume a lot of memory, but at least it works.

   2. when import "example.com/go/stack" is entered in Gophernotes, do not compile the module using Go toolchain. Instead, load its source code in the interpreter, and use interpreter's support for generics to instantiate any Stack[X] that the user may attempt to use. This means that third-party libraries imported by Gophernotes will be interpreted - no longer compiled. They will be slow, and Gophernotes does not support .S files written in assembly, nor it supports Cgo. So a lot of libraries would no longer work when imported by Gophernotes.

   Ideas for other solutions?
   Any contribution is welcome :)
5. cosmos72

   added

   help wanted

   limitation

   question

   and removed

   enhancement

   on Oct 28, 2021
6. cosmos72 commented on Nov 2, 2021

   

   cosmos72

   on Nov 2, 2021

   MemberAuthor

   More actions

   @dwhitena @SpencerPark @sbinet any idea or suggestion on the best approach to move forward ?
7. sbinet commented on Nov 2, 2021

   

   sbinet

   on Nov 2, 2021

   Member

   More actions

   I don't remember whether gomacro is using reflect under the hood to manipulate types, but if it does, one could perhaps weigh in and propose to have a reflect API that can also manipulate parametrized types.
8. cosmos72 commented on Nov 6, 2021

   

   cosmos72

   on Nov 6, 2021

   Last edited by cosmos72

   MemberAuthor

   More actions

   Yes, gomacro heavily uses reflect under the hood to manipulate types and values.

   This has several limitations, including that reflect package cannot create named types or interface types - indeed gomacro must emulate them.

   Generics are not supported by reflect, and if I remember correctly there's no plan to support them. Only instantiated generic types will be supported.

   And I am quite sure there's no plan to support instantiating generics at runtime - which for the foreseeable future will require invoking the Go toolchain.
9. cosmos72 commented on Nov 6, 2021

   

   cosmos72

   on Nov 6, 2021

   Last edited by cosmos72

   MemberAuthor

   More actions

   A third solution came to my mind: when importing a package, instantiate its generics on a custom type that satisfies the constraint(s).

   First example: for the Stack[T] above, instantiate Stack[interface{}] when importing, compiling and loading example.com/go/stack with Go toolchain.

   Second example: for an hypothetical generic type

   type Set[T Ordered] { /* ... */ }

   where the constraint Ordered is

   type Ordered[T] interface {
       Compare(T other) int
   }
   

   we can instantiate, compile and load with Go toolchain the type Set[OrderedX] where OrderedX is

   type OrderedX {
     X_ interface{} // the wrapped value
     Compare_ func(other OrderedX) int
   }
   // implement the interface Ordered[OrderedX]
   func (obj OrderedX) Compare(other OrderedX) int {
       return obj.Compare_(other)
   }

   This allows wrapping any type with a method Compare() inside an OrderedX and use it inside the instantiated Set[OrderedX]