Monomorphization: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
m Citation name "Download Limit Exceeded" -> "Extending Smt-Lib v2 with λ-Terms and Polymorphism"
Citation bot (talk | contribs)
Alter: template type, url. URLs might have been anonymized. Add: s2cid, citeseerx, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by AManWithNoPlan | #UCB_webform 800/2200
Line 1: Line 1:
{{Short description|Compile-time transformation}}
{{Short description|Compile-time transformation}}
In [[programming languages]], '''monomorphization''' is a [[compile-time]] process where [[polymorphic function]]s are replaced by many monomorphic functions for each unique instantiation.<ref>{{cite web |title=Generic Data Types - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch10-01-syntax.html |access-date=27 May 2021}}</ref> This transformation is desirable, since then the output [[intermediate representation]] (IR) will have concrete types and can be optimized better. Furthermore, most IRs are designed to be low-level and do not support polymorphism. Code generated this way is typically faster than [[boxed type]]s, but may compile slower and take more space due to duplicating the function body.<ref>{{cite web |last1=Hume |first1=Tristan |title=Models of Generics and Metaprogramming: Go, Rust, Swift, D and More |url=https://thume.ca/2019/07/14/a-tour-of-metaprogramming-models-for-generics/ |access-date=27 May 2021}}</ref><ref>{{Cite journal|last=Tanaka|first=Akira|last2=Affeldt|first2=Reynald|last3=Garrigue|first3=Jacques|date=2018|title=Safe Low-level Code Generation in Coq Using Monomorphization and Monadification|url=https://www.jstage.jst.go.jp/article/ipsjjip/26/0/26_54/_article/-char/ja/|journal=Journal of Information Processing|volume=26|pages=54–72|doi=10.2197/ipsjjip.26.54|doi-access=free}}</ref><ref>{{Cite web|title=Extending Smt-Lib v2 with λ-Terms and Polymorphism|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.663.6849&rep=rep1&type=pdf#page=61|access-date=2021-07-06|website=citeseerx.ist.psu.edu}}</ref><ref>{{Cite journal|last=Cai|first=Yufei|last2=Giarrusso|first2=Paolo G.|last3=Ostermann|first3=Klaus|date=2016-01-11|title=System f-omega with equirecursive types for datatype-generic programming|url=https://doi.org/10.1145/2837614.2837660|journal=Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages|series=POPL '16|location=St. Petersburg, FL, USA|publisher=Association for Computing Machinery|pages=30–43|doi=10.1145/2837614.2837660|isbn=978-1-4503-3549-2}}</ref><ref>{{Cite book|last=Klabnik|first=Steve|url=https://books.google.com/books?id=0Vv6DwAAQBAJ&newbks=0&hl=en|title=The Rust Programming Language (Covers Rust 2018)|last2=Nichols|first2=Carol|date=2019-08-06|publisher=No Starch Press|isbn=978-1-7185-0044-0|language=en}}</ref><ref>{{Cite book|last=Felty|first=Amy P.|url=https://books.google.com/books?id=l9hJCgAAQBAJ&newbks=0&printsec=frontcover&pg=PA291&dq=%22Monomorphization%22+-wikipedia&hl=en|title=Automated Deduction - CADE-25: 25th International Conference on Automated Deduction, Berlin, Germany, August 1-7, 2015, Proceedings|last2=Middeldorp|first2=Aart|date=2015-07-30|publisher=Springer|isbn=978-3-319-21401-6|language=en}}</ref>
In [[programming languages]], '''monomorphization''' is a [[compile-time]] process where [[polymorphic function]]s are replaced by many monomorphic functions for each unique instantiation.<ref>{{cite web |title=Generic Data Types - The Rust Programming Language |url=https://doc.rust-lang.org/book/ch10-01-syntax.html |access-date=27 May 2021}}</ref> This transformation is desirable, since then the output [[intermediate representation]] (IR) will have concrete types and can be optimized better. Furthermore, most IRs are designed to be low-level and do not support polymorphism. Code generated this way is typically faster than [[boxed type]]s, but may compile slower and take more space due to duplicating the function body.<ref>{{cite web |last1=Hume |first1=Tristan |title=Models of Generics and Metaprogramming: Go, Rust, Swift, D and More |url=https://thume.ca/2019/07/14/a-tour-of-metaprogramming-models-for-generics/ |access-date=27 May 2021}}</ref><ref>{{Cite journal|last1=Tanaka|first1=Akira|last2=Affeldt|first2=Reynald|last3=Garrigue|first3=Jacques|date=2018|title=Safe Low-level Code Generation in Coq Using Monomorphization and Monadification|url=https://www.jstage.jst.go.jp/article/ipsjjip/26/0/26_54/_article/-char/ja/|journal=Journal of Information Processing|volume=26|pages=54–72|doi=10.2197/ipsjjip.26.54|doi-access=free}}</ref><ref>{{Cite journal|title=Extending Smt-Lib v2 with λ-Terms and Polymorphism|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.663.6849&rep=rep1&type=pdf#page=61|access-date=2021-07-06|website=citeseerx.ist.psu.edu|citeseerx = 10.1.1.663.6849}}</ref><ref>{{Cite journal|last1=Cai|first1=Yufei|last2=Giarrusso|first2=Paolo G.|last3=Ostermann|first3=Klaus|date=2016-01-11|title=System f-omega with equirecursive types for datatype-generic programming|url=https://doi.org/10.1145/2837614.2837660|journal=Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages|series=POPL '16|location=St. Petersburg, FL, USA|publisher=Association for Computing Machinery|pages=30–43|doi=10.1145/2837614.2837660|isbn=978-1-4503-3549-2|s2cid=17566568}}</ref><ref>{{Cite book|last1=Klabnik|first1=Steve|url=https://books.google.com/books?id=0Vv6DwAAQBAJ|title=The Rust Programming Language (Covers Rust 2018)|last2=Nichols|first2=Carol|date=2019-08-06|publisher=No Starch Press|isbn=978-1-7185-0044-0|language=en}}</ref><ref>{{Cite book|last1=Felty|first1=Amy P.|url=https://books.google.com/books?id=l9hJCgAAQBAJ&dq=%22Monomorphization%22+-wikipedia&pg=PA291|title=Automated Deduction - CADE-25: 25th International Conference on Automated Deduction, Berlin, Germany, August 1-7, 2015, Proceedings|last2=Middeldorp|first2=Aart|date=2015-07-30|publisher=Springer|isbn=978-3-319-21401-6|language=en}}</ref>


==Example==
==Example==

Revision as of 18:08, 12 December 2021

In programming languages, monomorphization is a compile-time process where polymorphic functions are replaced by many monomorphic functions for each unique instantiation.[1] This transformation is desirable, since then the output intermediate representation (IR) will have concrete types and can be optimized better. Furthermore, most IRs are designed to be low-level and do not support polymorphism. Code generated this way is typically faster than boxed types, but may compile slower and take more space due to duplicating the function body.[2][3][4][5][6][7]

Example

For example, this is an example of a use of a generic identity function

fn id<T>(x: T) -> T {
    return x;
}

fn main() {
    let int = id(10);
    let string = id("some text");
    println!("{0}, {1}", int, string);
}

After monomorphization, this would become

fn id_i32(x: i32) -> i32 {
    return x;
}

fn id_str(x: &str) -> &str {
    return x;
}

fn main() {
    let int = id_i32(10);
    let string = id_str("some text");
    println!("{0}, {1}", int, string);
}

See also

References

  1. ^ "Generic Data Types - The Rust Programming Language". Retrieved 27 May 2021.
  2. ^ Hume, Tristan. "Models of Generics and Metaprogramming: Go, Rust, Swift, D and More". Retrieved 27 May 2021.
  3. ^ Tanaka, Akira; Affeldt, Reynald; Garrigue, Jacques (2018). "Safe Low-level Code Generation in Coq Using Monomorphization and Monadification". Journal of Information Processing. 26: 54–72. doi:10.2197/ipsjjip.26.54.
  4. ^ "Extending Smt-Lib v2 with λ-Terms and Polymorphism". citeseerx.ist.psu.edu. CiteSeerX 10.1.1.663.6849. Retrieved 2021-07-06.
  5. ^ Cai, Yufei; Giarrusso, Paolo G.; Ostermann, Klaus (2016-01-11). "System f-omega with equirecursive types for datatype-generic programming". Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL '16. St. Petersburg, FL, USA: Association for Computing Machinery: 30–43. doi:10.1145/2837614.2837660. ISBN 978-1-4503-3549-2. S2CID 17566568.
  6. ^ Klabnik, Steve; Nichols, Carol (2019-08-06). The Rust Programming Language (Covers Rust 2018). No Starch Press. ISBN 978-1-7185-0044-0.
  7. ^ Felty, Amy P.; Middeldorp, Aart (2015-07-30). Automated Deduction - CADE-25: 25th International Conference on Automated Deduction, Berlin, Germany, August 1-7, 2015, Proceedings. Springer. ISBN 978-3-319-21401-6.