zbMATH — the first resource for mathematics

Collected size semantics for strict functional programs over general polymorphic lists. (English) Zbl 1445.68047
Dal Lago, Ugo (ed.) et al., Foundational and practical aspects of resource analysis. Third international workshop, FOPARA 2013, Bertinoro, Italy, August 29–31, 2013. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 8552, 143-159 (2014).
Summary: Size analysis can be an important part of heap consumption analysis. This paper is a part of ongoing work about typing support for checking output-on-input size dependencies for function definitions in a strict functional language. A significant restriction for our earlier results is that inner data structures (e.g. in a list of lists) all must have the same size. Here, we make a big step forwards by overcoming this limitation via the introduction of higher-order size annotations such that variate sizes of inner data structures can be expressed. In this way the analysis becomes applicable for general, polymorphic nested lists.
For the entire collection see [Zbl 1326.68011].

68N18 Functional programming and lambda calculus
68P05 Data structures
68Q55 Semantics in the theory of computing
Full Text: DOI