{"id":{"repo_id":"glasgow","oai_identifier":"oai:theses.gla.ac.uk:4817"},"canonical_url":"https://search.ndltd.org/etd/glasgow/oai:theses.gla.ac.uk:4817","repository":{"repo_id":"glasgow","name":"University of Glasgow","base_url":"https://theses.gla.ac.uk/cgi/oai2"},"display":{"title":"Cheap deforestation for non-strict functional languages","abstract":"In functional languages intermediate data structures are often used as glue to connect separate parts of a program together. Deforestation is the process of automatically removing intermediate data structures. In this thesis we present and analyse a new approach to deforestation. This new approach is both practical and general. We analyse in detail the problem of list removal rather than the more general problem of arbitrary data structure removal. This more limited scope allows a complete evaluation of the pragmatic aspects of using our deforestation technology. We have implemented our list deforestation algorithm in the Glasgow Haskell compiler. Our implementation has allowed practical feedback. One important conclusion is that a new analysis is required to infer function arities and the linearity of lambda abstractions. This analysis renders the basic deforestation algorithm far more effective. We give a detailed assessment of our implementation of deforestation. We measure the effectiveness of our deforestation on a suite of real application programs. We also observe the costs of our deforestation algorithm.","abstract_html":"In functional languages intermediate data structures are often used as glue to connect separate parts of a program together. Deforestation is the process of automatically removing intermediate data structures. In this thesis we present and analyse a new approach to deforestation. This new approach is both practical and general. We analyse in detail the problem of list removal rather than the more general problem of arbitrary data structure removal. This more limited scope allows a complete evaluation of the pragmatic aspects of using our deforestation technology. We have implemented our list deforestation algorithm in the Glasgow Haskell compiler. Our implementation has allowed practical feedback. One important conclusion is that a new analysis is required to infer function arities and the linearity of lambda abstractions. This analysis renders the basic deforestation algorithm far more effective. We give a detailed assessment of our implementation of deforestation. We measure the effectiveness of our deforestation on a suite of real application programs. We also observe the costs of our deforestation algorithm.","abstract_has_math":false,"creators":["Gill, Andrew John"],"institution":"University of Glasgow","degree_name":null,"degree_level":"PhD","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1996,"date_issued":"1996","date_published":"1996","updated_at":"2026-11-19T08:23:20Z","subjects":["QA75 Electronic computers. Computer science"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null,"record_url":null,"record_label":null,"record_kind":null,"record_source":null,"download_url":"https://theses.gla.ac.uk/4817/1/1996gillphd.pdf","download_label":"Download PDF","download_source":"dc:identifier.uri","access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://theses.gla.ac.uk/cgi/oai2?verb=GetRecord&metadataPrefix=uketd_dc&identifier=oai%3Atheses.gla.ac.uk%3A4817","prefix":"uketd_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Gill, Andrew John"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["1996"]},{"key":"dc:date.issued","label":"Date","values":["1996"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Glasgow"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://theses.gla.ac.uk/4817/"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://gla.on.worldcat.org/oclc/53650242"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["PhD"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA75 Electronic computers. Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://theses.gla.ac.uk/4817/1/1996gillphd.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In functional languages intermediate data structures are often used as glue to connect separate parts of a program together. Deforestation is the process of automatically removing intermediate data structures. In this thesis we present and analyse a new approach to deforestation. This new approach is both practical and general. We analyse in detail the problem of list removal rather than the more general problem of arbitrary data structure removal. This more limited scope allows a complete evaluation of the pragmatic aspects of using our deforestation technology. We have implemented our list deforestation algorithm in the Glasgow Haskell compiler. Our implementation has allowed practical feedback. One important conclusion is that a new analysis is required to infer function arities and the linearity of lambda abstractions. This analysis renders the basic deforestation algorithm far more effective. We give a detailed assessment of our implementation of deforestation. We measure the effectiveness of our deforestation on a suite of real application programs. We also observe the costs of our deforestation algorithm."]},{"key":"dc:format","label":"Dc Format","values":["pdf"]},{"key":"dcterms:accessrights","label":"Dcterms Accessrights","values":["public"]},{"key":"dc:title","label":"Title","values":["Cheap deforestation for non-strict functional languages"]}]}],"canonical_facts":{"dc:creator":["Gill, Andrew John"],"dc:date":["1996"],"dc:date.issued":["1996"],"dc:description.abstract":["In functional languages intermediate data structures are often used as glue to connect separate parts of a program together. Deforestation is the process of automatically removing intermediate data structures. In this thesis we present and analyse a new approach to deforestation. This new approach is both practical and general. We analyse in detail the problem of list removal rather than the more general problem of arbitrary data structure removal. This more limited scope allows a complete evaluation of the pragmatic aspects of using our deforestation technology. We have implemented our list deforestation algorithm in the Glasgow Haskell compiler. Our implementation has allowed practical feedback. One important conclusion is that a new analysis is required to infer function arities and the linearity of lambda abstractions. This analysis renders the basic deforestation algorithm far more effective. We give a detailed assessment of our implementation of deforestation. We measure the effectiveness of our deforestation on a suite of real application programs. We also observe the costs of our deforestation algorithm."],"dc:format":["pdf"],"dc:identifier.uri":["https://theses.gla.ac.uk/4817/1/1996gillphd.pdf"],"dc:language":["en"],"dc:publisher.institution":["University of Glasgow"],"dc:relation.isreferencedby":["https://theses.gla.ac.uk/4817/"],"dc:relation.isreferencedby.uri":["https://gla.on.worldcat.org/oclc/53650242"],"dc:subject":["QA75 Electronic computers. Computer science"],"dcterms:accessrights":["public"],"dc:title":["Cheap deforestation for non-strict functional languages"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["PhD"]},"updated_at":"2026-11-19T08:23:20Z"}