Catherine Hope
Accurate Step Counting
Hope, Catherine; Hutton, Graham
Abstract
Starting with an evaluator for a language, an abstract machine for the same language can be mechanically derived using successive program transformations. This has relevance to studying both the space and time properties of programs because these can be estimated by counting transitions of the abstract machine and measuring the size of the additional data structures needed, such as environments and stacks. In this article we use this process to derive a function that accurately counts the number of steps required to evaluate expressions in a simple language.
Citation
Hope, C., & Hutton, G. (2005). Accurate Step Counting.
Conference Name | 17th International Workshop on Implementation and Application of Functional Languages |
---|---|
Publication Date | Jan 1, 2005 |
Deposit Date | Oct 26, 2005 |
Publicly Available Date | Oct 9, 2007 |
Peer Reviewed | Peer Reviewed |
Public URL | https://nottingham-repository.worktribe.com/output/1020404 |
Files
stepCounting.pdf
(<nobr>160 Kb</nobr>)
PDF
You might also like
Calculating correct compilers II: Return of the register machines
(2020)
Journal Article
Liquidate your assets: reasoning about resource usage in liquid Haskell
(2019)
Journal Article
Call-by-need is clairvoyant call-by-value
(2019)
Journal Article
AutoBench: comparing the time performance of Haskell programs
(2018)
Conference Proceeding
Theorem proving for all: equational reasoning in Liquid Haskell (Functional Pearl)
(2018)
Conference Proceeding