TY - JOUR
T1 - On the cost semantics for spreadsheets with sheet-defined functions
AU - Bock, Alexander Asp
AU - Bøgholm, Thomas
AU - Sestoft, Peter
AU - Thomsen, Bent
AU - Thomsen, Lone Leth
PY - 2022/4
Y1 - 2022/4
N2 - We give a simple operational cost semantics for evaluation of spreadsheet formulas and for full and minimal recalculation. We also present a semantics which caters for computing with unknown data values. This may be used to give an approximation of the cost when input data is not yet provided. This semantics is a rudimentary big-step trace-based abstract interpretation based upon the cost semantics. Together, the semantic presentations form the formal foundations for various cost calculations implemented in the Funcalc spreadsheet platform. This can be used in cost estimation tools, e.g. to estimate which formulas in a spreadsheet are the most expensive, or to schedule parallel recalculation of a spreadsheet. In future work, further analyzes and verification tools can be built upon the formal semantics to reduce the large number of errors that commonly occur in spreadsheets.
AB - We give a simple operational cost semantics for evaluation of spreadsheet formulas and for full and minimal recalculation. We also present a semantics which caters for computing with unknown data values. This may be used to give an approximation of the cost when input data is not yet provided. This semantics is a rudimentary big-step trace-based abstract interpretation based upon the cost semantics. Together, the semantic presentations form the formal foundations for various cost calculations implemented in the Funcalc spreadsheet platform. This can be used in cost estimation tools, e.g. to estimate which formulas in a spreadsheet are the most expensive, or to schedule parallel recalculation of a spreadsheet. In future work, further analyzes and verification tools can be built upon the formal semantics to reduce the large number of errors that commonly occur in spreadsheets.
U2 - https://doi.org/10.1016/j.cola.2022.101103
DO - https://doi.org/10.1016/j.cola.2022.101103
M3 - Journal article
VL - 69
JO - Journal of Computer Languages
JF - Journal of Computer Languages
SN - 2590-1184
M1 - 101103
ER -