@INPROCEEDINGS{Sands:Skye,
  author = {David Sands},
  title = {Operational Theories of Improvement in Functional Languages
                 (Extended Abstract)},
  booktitle = {Proceedings of the Fourth {G}lasgow Workshop on
                 Functional Programming},
  year = {1991},
  series = {Workshops in Computing Series},
  publisher = {{S}pringer-Verlag },
  address = {Skye},
  pages = {298--311},
  month = {August},
  optnote = {},
  abstract = {In this paper we address the technical foundations essential to the
aim of providing a semantic basis for the formal treatment of relative
efficiency in functional languages.  For a general class of
{``functional''} computation systems, we define a family of improvement
preorderings which express, in a variety of ways, when one expression
is more efficient than another. The main results of this paper build
on Howe's study of equality in lazy computation systems, and are
concerned with the question of when a given improvement relation is
subject to the usual forms of (in)equational reasoning (so that, for
example, we can improve an expression by improving any
sub-expression).  For a general class of computation systems we
establish conditions on the operators of the language which guarantee
that an improvement relation is a precongruence.  In addition, for a
particular higher-order nonstrict functional language, we show that
any improvement relation which satisfies a simple monotonicity
condition with respect to the rules of the operational semantics has
the desired congruence property.
},
  url_Paper = {http://www.cse.chalmers.se/~dave/papers/Sands:Skye.pdf},
}

{"_id":"ScGquNiKp4n6BjhNE","bibbaseid":"sands-operationaltheoriesofimprovementinfunctionallanguagesextendedabstract-1991","downloads":0,"creationDate":"2017-02-03T08:24:26.854Z","title":"Operational Theories of Improvement in Functional Languages (Extended Abstract)","author_short":["Sands, D."],"year":1991,"bibtype":"inproceedings","biburl":"http://www.cse.chalmers.se/~dave/davewww2016.bib","bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["David"],"propositions":[],"lastnames":["Sands"],"suffixes":[]}],"title":"Operational Theories of Improvement in Functional Languages (Extended Abstract)","booktitle":"Proceedings of the Fourth Glasgow Workshop on Functional Programming","year":"1991","series":"Workshops in Computing Series","publisher":"Springer-Verlag ","address":"Skye","pages":"298--311","month":"August","optnote":"","abstract":"In this paper we address the technical foundations essential to the aim of providing a semantic basis for the formal treatment of relative efficiency in functional languages. For a general class of ``functional'' computation systems, we define a family of improvement preorderings which express, in a variety of ways, when one expression is more efficient than another. The main results of this paper build on Howe's study of equality in lazy computation systems, and are concerned with the question of when a given improvement relation is subject to the usual forms of (in)equational reasoning (so that, for example, we can improve an expression by improving any sub-expression). For a general class of computation systems we establish conditions on the operators of the language which guarantee that an improvement relation is a precongruence. In addition, for a particular higher-order nonstrict functional language, we show that any improvement relation which satisfies a simple monotonicity condition with respect to the rules of the operational semantics has the desired congruence property. ","url_paper":"http://www.cse.chalmers.se/~dave/papers/Sands:Skye.pdf","bibtex":"@INPROCEEDINGS{Sands:Skye,\n author = {David Sands},\n title = {Operational Theories of Improvement in Functional Languages\n (Extended Abstract)},\n booktitle = {Proceedings of the Fourth {G}lasgow Workshop on\n Functional Programming},\n year = {1991},\n series = {Workshops in Computing Series},\n publisher = {{S}pringer-Verlag },\n address = {Skye},\n pages = {298--311},\n month = {August},\n optnote = {},\n abstract = {In this paper we address the technical foundations essential to the\naim of providing a semantic basis for the formal treatment of relative\nefficiency in functional languages. For a general class of\n{``functional''} computation systems, we define a family of improvement\npreorderings which express, in a variety of ways, when one expression\nis more efficient than another. The main results of this paper build\non Howe's study of equality in lazy computation systems, and are\nconcerned with the question of when a given improvement relation is\nsubject to the usual forms of (in)equational reasoning (so that, for\nexample, we can improve an expression by improving any\nsub-expression). For a general class of computation systems we\nestablish conditions on the operators of the language which guarantee\nthat an improvement relation is a precongruence. In addition, for a\nparticular higher-order nonstrict functional language, we show that\nany improvement relation which satisfies a simple monotonicity\ncondition with respect to the rules of the operational semantics has\nthe desired congruence property.\n},\n url_Paper = {http://www.cse.chalmers.se/~dave/papers/Sands:Skye.pdf},\n}\n","author_short":["Sands, D."],"key":"Sands:Skye","id":"Sands:Skye","bibbaseid":"sands-operationaltheoriesofimprovementinfunctionallanguagesextendedabstract-1991","role":"author","urls":{" paper":"http://www.cse.chalmers.se/~dave/papers/Sands:Skye.pdf"},"downloads":0},"search_terms":["operational","theories","improvement","functional","languages","extended","abstract","sands"],"keywords":[],"authorIDs":["58943e3a2f18920f4c000022"],"dataSources":["SBHWXKotbthoEYKJv"]}