Accurate step counting

Accurate step counting. Catherine Hope and Graham Hutton.

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.

Somewhat related to a recent discussion (in which I mentioned EOPL1's scetion on deriving a compiler and machine from an interpreter).

The paper is, of course, worth checking out regardless.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Nice to see some application

Nice to see some application of the technique of Olivier Danvy et. al. to relate evaluators and abstract machines. I can recommend everyone to read up on that. It has helped me gain a lot of intuition about the evaluation of programming languages.