×

Resource analysis by sup-interpretation. (English) Zbl 1185.68226

Hagiya, Masami (ed.) et al., Functional and logic programming. 8th international symposium, FLOPS 2006, Fuji-Susono, Japan, April 24–26, 2006. Proceedings. Berlin: Springer (ISBN 3-540-33438-6/pbk). Lecture Notes in Computer Science 3945, 163-176 (2006).
Summary: We propose a new method to control memory resources by static analysis. For this, we introduce the notion of sup-interpretation which bounds from above the size of function outputs. We establish a criteria for which the stack frame size is polynomially bounded. The criteria analyses terminating as well as non-terminating programs. This method applies to first-order functional programming with pattern matching. This work is related to quasi-interpretations but we are now able to determine resources of different algorithms and it is easier to perform an analysis with this new tools.
For the entire collection see [Zbl 1103.68004].

MSC:

68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
68N18 Functional programming and lambda calculus
PDFBibTeX XMLCite
Full Text: DOI Link