Backwards Strictness Analysis: Proved and Improved

Kei Davis; Philip Wadler

doi:10.1007/978-1-4471-3166-3_2

Backwards Strictness Analysis: Proved and Improved

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a syntax tree representing an expression, and some information regarding that expression, a backwards analysis will involve propagating the information (with appropriate transformation) towards the leaves of the tree, to yield information about the subexpressions. Here, the information at the root will describe the required definedness of the value of the expression, with the results of the analysis describing the definedness of the values lower in the tree sufficient or necessary to meet the condition at the root. In Projections for Strictness Analysis [1], such an analysis is described in which the information at each node is encoded by a special kind of function called a projection, with the results of the analysis revealing strictness information about the expression. This paper describes a more general and powerful technique, and provides proofs that both techniques meet a corresponding generalisation of the safety condition described in [1].

Original language	English
Title of host publication	Functional Programming
Subtitle of host publication	Proceedings of the 1989 Glasgow Workshop 21–23 August 1989, Fraserburgh, Scotland
Publisher	Springer-Verlag GmbH
Pages	12-30
Number of pages	19
ISBN (Electronic)	978-1-4471-3166-3
ISBN (Print)	978-3-540-19609-9
DOIs	https://doi.org/10.1007/978-1-4471-3166-3_2
Publication status	Published - 1989

Publication series

Name	Workshops in Computing
Publisher	Springer London
ISSN (Print)	1431-1682

Access to Document

10.1007/978-1-4471-3166-3_2

Cite this

@inproceedings{e4e546f3768a43679bcfb57229d1aa0f,

title = "Backwards Strictness Analysis: Proved and Improved",

abstract = "Given a syntax tree representing an expression, and some information regarding that expression, a backwards analysis will involve propagating the information (with appropriate transformation) towards the leaves of the tree, to yield information about the subexpressions. Here, the information at the root will describe the required definedness of the value of the expression, with the results of the analysis describing the definedness of the values lower in the tree sufficient or necessary to meet the condition at the root. In Projections for Strictness Analysis [1], such an analysis is described in which the information at each node is encoded by a special kind of function called a projection, with the results of the analysis revealing strictness information about the expression. This paper describes a more general and powerful technique, and provides proofs that both techniques meet a corresponding generalisation of the safety condition described in [1]. ",

author = "Kei Davis and Philip Wadler",

year = "1989",

doi = "10.1007/978-1-4471-3166-3_2",

language = "English",

isbn = "978-3-540-19609-9",

series = "Workshops in Computing",

publisher = "Springer-Verlag GmbH",

pages = "12--30",

booktitle = "Functional Programming",

}

TY - GEN

T1 - Backwards Strictness Analysis: Proved and Improved

AU - Davis, Kei

AU - Wadler, Philip

PY - 1989

Y1 - 1989

N2 - Given a syntax tree representing an expression, and some information regarding that expression, a backwards analysis will involve propagating the information (with appropriate transformation) towards the leaves of the tree, to yield information about the subexpressions. Here, the information at the root will describe the required definedness of the value of the expression, with the results of the analysis describing the definedness of the values lower in the tree sufficient or necessary to meet the condition at the root. In Projections for Strictness Analysis [1], such an analysis is described in which the information at each node is encoded by a special kind of function called a projection, with the results of the analysis revealing strictness information about the expression. This paper describes a more general and powerful technique, and provides proofs that both techniques meet a corresponding generalisation of the safety condition described in [1].

AB - Given a syntax tree representing an expression, and some information regarding that expression, a backwards analysis will involve propagating the information (with appropriate transformation) towards the leaves of the tree, to yield information about the subexpressions. Here, the information at the root will describe the required definedness of the value of the expression, with the results of the analysis describing the definedness of the values lower in the tree sufficient or necessary to meet the condition at the root. In Projections for Strictness Analysis [1], such an analysis is described in which the information at each node is encoded by a special kind of function called a projection, with the results of the analysis revealing strictness information about the expression. This paper describes a more general and powerful technique, and provides proofs that both techniques meet a corresponding generalisation of the safety condition described in [1].

U2 - 10.1007/978-1-4471-3166-3_2

DO - 10.1007/978-1-4471-3166-3_2

M3 - Conference contribution

SN - 978-3-540-19609-9

T3 - Workshops in Computing

SP - 12

EP - 30

BT - Functional Programming

PB - Springer-Verlag GmbH

ER -