{"id":{"repo_id":"aachen","oai_identifier":"oai:publications.rwth-aachen.de:51897"},"canonical_url":"https://search.dev.ndltd.org/etd/aachen/oai:publications.rwth-aachen.de:51897","repository":{"repo_id":"aachen","name":"RWTH Aachen University","base_url":"https://publications.rwth-aachen.de/oai2d"},"display":{"title":"Type inference based deforestation of functional programs","abstract":"In lazy functional programs a data structure is often used to combine two separate parts of the program. This intermediate data structure is produced by one part and consumed by another one. The gained modularity has to be payed for in terms of a longer runtime, because construction and destruction of the intermediate data structure costs time. Deforestation is the name for a class of optimising program transformations that transform a program into an equivalent program which does not produce such intermediate data structures. In this thesis a new deforestation method is described which combines a known method, short cut deforestation, with a new analysis based on type inference. Short cut deforestation eliminates an intermediate list by a single, local transformation. In return, short cut deforestation places high demands on the syntactic structure of the program which run contrary to the goal of comprehensible programs. We describe an algorithm that transforms an arbitrary producer of an intermediate data structure into the form required by short cut deforestation. The core of the algorithm is an efficient type inference algorithm, because the transformation problem can be reduced to a type inference problem.","abstract_html":"In lazy functional programs a data structure is often used to combine two separate parts of the program. This intermediate data structure is produced by one part and consumed by another one. The gained modularity has to be payed for in terms of a longer runtime, because construction and destruction of the intermediate data structure costs time. Deforestation is the name for a class of optimising program transformations that transform a program into an equivalent program which does not produce such intermediate data structures. In this thesis a new deforestation method is described which combines a known method, short cut deforestation, with a new analysis based on type inference. Short cut deforestation eliminates an intermediate list by a single, local transformation. In return, short cut deforestation places high demands on the syntactic structure of the program which run contrary to the goal of comprehensible programs. We describe an algorithm that transforms an arbitrary producer of an intermediate data structure into the form required by short cut deforestation. The core of the algorithm is an efficient type inference algorithm, because the transformation problem can be reduced to a type inference problem.","abstract_has_math":false,"creators":["Chitil, Olaf"],"institution":"Publikationsserver der RWTH Aachen University","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Indermark, Klaus"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2001,"date_issued":"2001","date_published":"2001","updated_at":"2026-07-30T19:40:42Z","subjects":["info:eu-repo/classification/ddc/004","Informatik","Funktionale Programmierung","Deforestation","Typinferenz"],"languages":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114146%22"],"render_values":[{"text":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114146%22","href":"https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114146%22","code":true}]}]},"links":{"outbound_url":"https://publications.rwth-aachen.de/record/51897","outbound_label":"Repository record","outbound_source":"dc:identifier"},"source_record":{"url":"https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A51897","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Indermark, Klaus"]},{"key":"dc:creator","label":"Author","values":["Chitil, Olaf"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:coverage","label":"Dc Coverage","values":["DE"]},{"key":"dc:date","label":"Dc Date","values":["2001"]},{"key":"dc:publisher","label":"Institution","values":["Publikationsserver der RWTH Aachen University"]},{"key":"dc:relation","label":"Dc Relation","values":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-1144"]},{"key":"dc:type","label":"Dc Type","values":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["info:eu-repo/classification/ddc/004","Informatik","Funktionale Programmierung","Deforestation","Typinferenz"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://publications.rwth-aachen.de/record/51897","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114146%22"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In lazy functional programs a data structure is often used to combine two separate parts of the program. This intermediate data structure is produced by one part and consumed by another one. The gained modularity has to be payed for in terms of a longer runtime, because construction and destruction of the intermediate data structure costs time. Deforestation is the name for a class of optimising program transformations that transform a program into an equivalent program which does not produce such intermediate data structures. In this thesis a new deforestation method is described which combines a known method, short cut deforestation, with a new analysis based on type inference. Short cut deforestation eliminates an intermediate list by a single, local transformation. In return, short cut deforestation places high demands on the syntactic structure of the program which run contrary to the goal of comprehensible programs. We describe an algorithm that transforms an arbitrary producer of an intermediate data structure into the form required by short cut deforestation. The core of the algorithm is an efficient type inference algorithm, because the transformation problem can be reduced to a type inference problem."]},{"key":"dc:source","label":"Dc Source","values":["Aachen : Publikationsserver der RWTH Aachen University IX, 155 S. (2001). = Aachen, Techn. Hochsch., Diss., 2000"]},{"key":"dc:title","label":"Title","values":["Type inference based deforestation of functional programs"]}]}],"canonical_facts":{"dc:contributor":["Indermark, Klaus"],"dc:coverage":["DE"],"dc:creator":["Chitil, Olaf"],"dc:date":["2001"],"dc:description":["In lazy functional programs a data structure is often used to combine two separate parts of the program. This intermediate data structure is produced by one part and consumed by another one. The gained modularity has to be payed for in terms of a longer runtime, because construction and destruction of the intermediate data structure costs time. Deforestation is the name for a class of optimising program transformations that transform a program into an equivalent program which does not produce such intermediate data structures. In this thesis a new deforestation method is described which combines a known method, short cut deforestation, with a new analysis based on type inference. Short cut deforestation eliminates an intermediate list by a single, local transformation. In return, short cut deforestation places high demands on the syntactic structure of the program which run contrary to the goal of comprehensible programs. We describe an algorithm that transforms an arbitrary producer of an intermediate data structure into the form required by short cut deforestation. The core of the algorithm is an efficient type inference algorithm, because the transformation problem can be reduced to a type inference problem."],"dc:identifier":["https://publications.rwth-aachen.de/record/51897","https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-114146%22"],"dc:language":["eng"],"dc:publisher":["Publikationsserver der RWTH Aachen University"],"dc:relation":["info:eu-repo/semantics/altIdentifier/urn/urn:nbn:de:hbz:82-opus-1144"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:source":["Aachen : Publikationsserver der RWTH Aachen University IX, 155 S. (2001). = Aachen, Techn. Hochsch., Diss., 2000"],"dc:subject":["info:eu-repo/classification/ddc/004","Informatik","Funktionale Programmierung","Deforestation","Typinferenz"],"dc:title":["Type inference based deforestation of functional programs"],"dc:type":["info:eu-repo/semantics/doctoralThesis","info:eu-repo/semantics/publishedVersion"]},"updated_at":"2026-07-30T19:40:42Z"}