{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/11868"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/11868","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Improving Efficiency and Safety of Program Generation","abstract":"Program Generation (PG) is about writing programs that write programs. A program generator composes various pieces of code to construct a new program. When employed at runtime, PG can produce an efficient version of a program by specializing it according to inputs that become available at runtime. PG has been used in a wide range of applications to improve program efficiency and modularity as well as programmer productivity. There are two major problems associated with PG: (1) Program generation has its own cost, which may cause a performance loss even though PG is intended for performance gain. This is especially important for runtime program generation. (2) Compilability guarantees about the generated program are poor; the generator may produce a type-incorrect program. In this dissertation we focus on these two problems. We provide three techniques that address the first problem. First, we show that just-in-time generation can successfully reduce the cost of generation by avoiding unnecessary program generation. We do this by means of an experiment in the context of marshalling in Java, where we generate specialized object marshallers based on object types. Just-in-time generation improved the speedup from 1.22 to 3.16. Second, we apply source-level transformations to optimize the execution of program generators. Up to 15\\% speedup has been achieved in runtime generation time for Jumbo, a PG system for Java. Third, we provide a technique to stage analysis of generated programs to perform a portion of the analysis at compile time rather than completing the entire analysis at runtime. We also give experimental evidence via several examples that this technique reduces runtime generation cost. To address the second problem of PG, we first show that operational semantics of record calculus and program generation are equivalent, and that a record type system can be used to type-check program generators. We also show that this is true in the presence of expressions with side-effects. We then make use of an already-existing record calculus feature, subtyping, to extend the program generation type system with subtyping constraints. As a result, we obtain a very expressive type system to statically guarantee that a generator will produce type-safe code. We state and prove the theorems based on an ML-like language with program generation constructs.","abstract_html":"Program Generation (PG) is about writing programs that write programs. A program generator composes various pieces of code to construct a new program. When employed at runtime, PG can produce an efficient version of a program by specializing it according to inputs that become available at runtime. PG has been used in a wide range of applications to improve program efficiency and modularity as well as programmer productivity. There are two major problems associated with PG: (1) Program generation has its own cost, which may cause a performance loss even though PG is intended for performance gain. This is especially important for runtime program generation. (2) Compilability guarantees about the generated program are poor; the generator may produce a type-incorrect program. In this dissertation we focus on these two problems. We provide three techniques that address the first problem. First, we show that just-in-time generation can successfully reduce the cost of generation by avoiding unnecessary program generation. We do this by means of an experiment in the context of marshalling in Java, where we generate specialized object marshallers based on object types. Just-in-time generation improved the speedup from 1.22 to 3.16. Second, we apply source-level transformations to optimize the execution of program generators. Up to 15\\% speedup has been achieved in runtime generation time for Jumbo, a PG system for Java. Third, we provide a technique to stage analysis of generated programs to perform a portion of the analysis at compile time rather than completing the entire analysis at runtime. We also give experimental evidence via several examples that this technique reduces runtime generation cost. To address the second problem of PG, we first show that operational semantics of record calculus and program generation are equivalent, and that a record type system can be used to type-check program generators. We also show that this is true in the presence of expressions with side-effects. We then make use of an already-existing record calculus feature, subtyping, to extend the program generation type system with subtyping constraints. As a result, we obtain a very expressive type system to statically guarantee that a generator will produce type-safe code. We state and prove the theorems based on an ML-like language with program generation constructs.","abstract_has_math":false,"creators":["Aktemur, T. Baris"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":null,"degree_department":null,"school":null,"contributors":["Kamin, Samuel N.","Adve, Vikram S.","Marinov, Darko","Roşu, Grigore","Sestoft, Peter"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-05-20T04:03:06Z","date_published":"2009-05-20T04:03:06Z","updated_at":"2026-07-22T22:24:52Z","subjects":["programming languages","program generation","type systems","multi-staged programming","meta-level programming"],"languages":["en"],"rights":["Copyright 2009 Baris Aktemur"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 2009"],"render_values":[{"text":"Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 2009","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/11868","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kamin, Samuel N.","Adve, Vikram S.","Marinov, Darko","Roşu, Grigore","Sestoft, Peter"]},{"key":"dc:creator","label":"Author","values":["Aktemur, T. Baris"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009-05-20T04:03:06Z","2009"]},{"key":"dc:type","label":"Dc Type","values":["Dissertation / Thesis","text"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["programming languages","program generation","type systems","multi-staged programming","meta-level programming"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2009 Baris Aktemur"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 2009","http://hdl.handle.net/2142/11868"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Program Generation (PG) is about writing programs that write programs. A program generator composes various pieces of code to construct a new program. When employed at runtime, PG can produce an efficient version of a program by specializing it according to inputs that become available at runtime. PG has been used in a wide range of applications to improve program efficiency and modularity as well as programmer productivity. There are two major problems associated with PG: (1) Program generation has its own cost, which may cause a performance loss even though PG is intended for performance gain. This is especially important for runtime program generation. (2) Compilability guarantees about the generated program are poor; the generator may produce a type-incorrect program. In this dissertation we focus on these two problems. We provide three techniques that address the first problem. First, we show that just-in-time generation can successfully reduce the cost of generation by avoiding unnecessary program generation. We do this by means of an experiment in the context of marshalling in Java, where we generate specialized object marshallers based on object types. Just-in-time generation improved the speedup from 1.22 to 3.16. Second, we apply source-level transformations to optimize the execution of program generators. Up to 15\\% speedup has been achieved in runtime generation time for Jumbo, a PG system for Java. Third, we provide a technique to stage analysis of generated programs to perform a portion of the analysis at compile time rather than completing the entire analysis at runtime. We also give experimental evidence via several examples that this technique reduces runtime generation cost. To address the second problem of PG, we first show that operational semantics of record calculus and program generation are equivalent, and that a record type system can be used to type-check program generators. We also show that this is true in the presence of expressions with side-effects. We then make use of an already-existing record calculus feature, subtyping, to extend the program generation type system with subtyping constraints. As a result, we obtain a very expressive type system to statically guarantee that a generator will produce type-safe code. We state and prove the theorems based on an ML-like language with program generation constructs.","Submitted by Tankut Aktemur (aktemur@illinois.edu) on 2009-05-20T04:03:06Z No. of bitstreams: 1 aktemur-dissertation.pdf: 911505 bytes, checksum: e731bc68e365a4d791f7f443d504c5e7 (MD5)","Made available in DSpace on 2009-05-20T04:03:06Z (GMT). No. of bitstreams: 1 aktemur-dissertation.pdf: 911505 bytes, checksum: e731bc68e365a4d791f7f443d504c5e7 (MD5) Previous issue date: 2009"]},{"key":"dc:title","label":"Title","values":["Improving Efficiency and Safety of Program Generation"]}]}],"canonical_facts":{"dc:contributor":["Kamin, Samuel N.","Adve, Vikram S.","Marinov, Darko","Roşu, Grigore","Sestoft, Peter"],"dc:creator":["Aktemur, T. Baris"],"dc:date":["2009-05-20T04:03:06Z","2009"],"dc:description":["Program Generation (PG) is about writing programs that write programs. A program generator composes various pieces of code to construct a new program. When employed at runtime, PG can produce an efficient version of a program by specializing it according to inputs that become available at runtime. PG has been used in a wide range of applications to improve program efficiency and modularity as well as programmer productivity. There are two major problems associated with PG: (1) Program generation has its own cost, which may cause a performance loss even though PG is intended for performance gain. This is especially important for runtime program generation. (2) Compilability guarantees about the generated program are poor; the generator may produce a type-incorrect program. In this dissertation we focus on these two problems. We provide three techniques that address the first problem. First, we show that just-in-time generation can successfully reduce the cost of generation by avoiding unnecessary program generation. We do this by means of an experiment in the context of marshalling in Java, where we generate specialized object marshallers based on object types. Just-in-time generation improved the speedup from 1.22 to 3.16. Second, we apply source-level transformations to optimize the execution of program generators. Up to 15\\% speedup has been achieved in runtime generation time for Jumbo, a PG system for Java. Third, we provide a technique to stage analysis of generated programs to perform a portion of the analysis at compile time rather than completing the entire analysis at runtime. We also give experimental evidence via several examples that this technique reduces runtime generation cost. To address the second problem of PG, we first show that operational semantics of record calculus and program generation are equivalent, and that a record type system can be used to type-check program generators. We also show that this is true in the presence of expressions with side-effects. We then make use of an already-existing record calculus feature, subtyping, to extend the program generation type system with subtyping constraints. As a result, we obtain a very expressive type system to statically guarantee that a generator will produce type-safe code. We state and prove the theorems based on an ML-like language with program generation constructs.","Submitted by Tankut Aktemur (aktemur@illinois.edu) on 2009-05-20T04:03:06Z No. of bitstreams: 1 aktemur-dissertation.pdf: 911505 bytes, checksum: e731bc68e365a4d791f7f443d504c5e7 (MD5)","Made available in DSpace on 2009-05-20T04:03:06Z (GMT). No. of bitstreams: 1 aktemur-dissertation.pdf: 911505 bytes, checksum: e731bc68e365a4d791f7f443d504c5e7 (MD5) Previous issue date: 2009"],"dc:identifier":["Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 2009","http://hdl.handle.net/2142/11868"],"dc:language":["en"],"dc:rights":["Copyright 2009 Baris Aktemur"],"dc:subject":["programming languages","program generation","type systems","multi-staged programming","meta-level programming"],"dc:title":["Improving Efficiency and Safety of Program Generation"],"dc:type":["Dissertation / Thesis","text"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}