TY - JOUR
T1 - Generic go to go
T2 - dictionary-passing, monomorphisation, and hybrid
AU - Ellis, Stephen
AU - Zhu, Shuofei
AU - Yoshida, Nobuko
AU - Song, Linhai
N1 - Publisher Copyright:
© 2022 Owner/Author.
PY - 2022/10/31
Y1 - 2022/10/31
N2 - Go is a popular statically-typed industrial programming language. To aid the type safe reuse of code, the recent Go release (Go 1.18) published early 2022 includes bounded parametric polymorphism via generic types. Go 1.18 implements generic types using a combination of monomorphisation and call-graph based dictionary-passing called hybrid. This hybrid approach can be viewed as an optimised form of monomorphisation that statically generates specialised methods and types based on possible instantiations. A monolithic dictionary supplements information lost during monomorphisation, and is structured according to the program's call graph. Unfortunately, the hybrid approach still suffers from code bloat, poor compilation speed, and limited code coverage. In this paper we propose and formalise a new non-specialising call-site based dictionary-passing translation. Our call-site based translation creates individual dictionaries for each type parameter, with dictionary construction occurring in place of instantiation, overcoming the limitations of hybrid. We prove it correct using a novel and general bisimulation up to technique. To better understand how different generics translation approaches work in practice, we benchmark five translators, Go 1.18, two existing monomorphisation translators, our dictionary-passing translator, and an erasure translator. Our findings reveal several suggestions for improvements for Go 1.18 - specifically how to overcome the expressiveness limitations of generic Go and improve compile time and compiled code size performance of Go 1.18.
AB - Go is a popular statically-typed industrial programming language. To aid the type safe reuse of code, the recent Go release (Go 1.18) published early 2022 includes bounded parametric polymorphism via generic types. Go 1.18 implements generic types using a combination of monomorphisation and call-graph based dictionary-passing called hybrid. This hybrid approach can be viewed as an optimised form of monomorphisation that statically generates specialised methods and types based on possible instantiations. A monolithic dictionary supplements information lost during monomorphisation, and is structured according to the program's call graph. Unfortunately, the hybrid approach still suffers from code bloat, poor compilation speed, and limited code coverage. In this paper we propose and formalise a new non-specialising call-site based dictionary-passing translation. Our call-site based translation creates individual dictionaries for each type parameter, with dictionary construction occurring in place of instantiation, overcoming the limitations of hybrid. We prove it correct using a novel and general bisimulation up to technique. To better understand how different generics translation approaches work in practice, we benchmark five translators, Go 1.18, two existing monomorphisation translators, our dictionary-passing translator, and an erasure translator. Our findings reveal several suggestions for improvements for Go 1.18 - specifically how to overcome the expressiveness limitations of generic Go and improve compile time and compiled code size performance of Go 1.18.
UR - http://www.scopus.com/inward/record.url?scp=85168412135&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85168412135&partnerID=8YFLogxK
U2 - 10.1145/3563331
DO - 10.1145/3563331
M3 - Article
AN - SCOPUS:85168412135
SN - 2475-1421
VL - 6
JO - Proceedings of the ACM on Programming Languages
JF - Proceedings of the ACM on Programming Languages
IS - OOPSLA2
M1 - 168
ER -