Abstract
We develop a theory for two recently-proposed spreadsheet mechanisms: gridlets allow for abstraction and reuse in spreadsheets, and build on spilled arrays, where an array value spills out of one cell into nearby cells. We present the first formal calculus of spreadsheets with spilled arrays. Since spilled arrays may collide, the semantics of spilling is an iterative process to determine which arrays spill successfully and which do not. Our first theorem is that this process converges deterministically. To model gridlets, we propose the grid calculus, a higher-order extension of our calculus of spilled arrays with primitives to treat spreadsheets as values. We define a semantics of gridlets as formulas in the grid calculus. Our second theorem shows the correctness of a remarkably direct encoding of the Abadi and Cardelli object calculus into the grid calculus. This result is the first rigorous analogy between spreadsheets and objects; it substantiates the intuition that gridlets are an object-oriented counterpart to functional programming extensions to spreadsheets, such as sheet-defined functions.
Chapter PDF
Similar content being viewed by others
References
Abadi, M., Cardelli, L.: A Theory of Objects. Monographs in Computer Science, Springer (1996)
Abraham, R., Erwig, M.: Inferring templates from spreadsheets. In: Proceedings of the 28th International Conference on Software Engineering. pp. 182–191. ICSE ’06, ACM, New York, NY, USA (2006)
Abraham, R., Erwig, M.: Type inference for spreadsheets. In: Proceedings of the 8th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming. pp. 73–84. PPDP ’06, ACM, New York, NY, USA (2006)
Bock, A.A., Bøgholm, T., Sestoft, P., Thomsen, B., Thomsen, L.L.: Concrete and abstract cost semantics for spreadsheets. Tech. Rep. TR-2008-203, IT University of Copenhagen (2018)
Burnett, M., Atwood, J., Djang, R.W., Reichwein, J., Gottfried, H., Yang, S.: Forms/3: A first-order visual language to explore the boundaries of the spreadsheet paradigm. Journal of functional programming 11(2), 155–206 (2001)
Chambers, C., Ungar, D.M.: Customization: Optimizing compiler technology for self, A dynamically-typed object-oriented programming language. In: PLDI. pp. 146–160. ACM (1989)
Cheng, T., Rival, X.: Static analysis of spreadsheet applications for type-unsafe operations detection. In: Vitek, J. (ed.) Programming Languages and Systems, pp. 26–52. Springer, Berlin Heidelberg, Berlin, Heidelberg (2015)
Clack, C., Braine, L.: Object-oriented functional spreadsheets. In: 10th Glasgow Workshop on Functional Programming. pp. 1–12 (1997)
Djang, R.W., Burnett, M.M.: Similarity inheritance: a new model of inheritance for spreadsheet vpls. In: Proceedings. 1998 IEEE Symposium on Visual Languages (Cat. No. 98TB100254). pp. 134–141. IEEE (1998)
Erwig, M., Abraham, R., Cooperstein, I., Kollmansberger, S.: Automatic generation and maintenance of correct spreadsheets. In: Proceedings of the 27th international conference on Software engineering. pp. 136–145. ACM (2005)
Jelen, B.: Excel Dynamic Arrays Straight to the Point. Holy Macro! Books (2018), see also https://blog-insider.office.com/2019/06/13/dynamic-arrays-and-new-functions-in-excel/
Joharizadeh, N., Sarkar, A., Gordon, A.D., Williams, J.: Gridlets: Reusing spreadsheet grids. In: Extended Abstracts of the 2020 CHI Conference on Human Factors in Computing Systems. CHI EA ’20, ACM, New York, NY, USA (2020). https://doi.org/10.1145/3334480.3382806,http://doi.acm.org/10.1145/3334480.3382806
Kay, A.: Computer software. Scientific American 251(3), 52–59 (1984), http://www.jstor.org/stable/24920344
McCutchen, M., Borghouts, J., Gordon, A.D., Peyton Jones, S., Sarkar, A.: Elastic sheet-defined functions: Generalising spreadsheet functions to variable-size input arrays (2019), unpublished manuscript available at https://aka.ms/calcintel
McCutchen, M., Itzhaky, S., Jackson, D.: Object spreadsheets: A new computational model for end-user development of data-centric web applications. In: Proceedings of the 2016 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software. pp. 112–127. Onward! 2016, ACM, New York, NY, USA (2016)
Mokhov, A., Mitchell, N., Peyton Jones, S.: Build systems à la carte. PACMPL 2(ICFP), 79:1–79:29 (2018)
Peyton Jones, S.L., Blackwell, A.F., Burnett, M.M.: A user-centred approach to functions in Excel. In: ICFP. pp. 165–176. ACM (2003)
Sarkar, A., Gordon, A.D., Jones, S.P., Toronto, N.: Calculation view: multiple-representation editing in spreadsheets. In: 2018 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC). pp. 85–93 (Oct 2018). https://doi.org/10.1109/VLHCC.2018.8506584
Sestoft, P.: Implementing function spreadsheets. In: Proceedings of the 4th international workshop on End-user software engineering. pp. 91–94. ACM (2008)
Sestoft, P., Sørensen, J.Z.: Sheet-defined functions: Implementation and initial evaluation. In: Dittrich, Y., Burnett, M., Mørch, A., Redmiles, D. (eds.) End-User Development, pp. 88–103. Springer, Berlin Heidelberg, Berlin, Heidelberg (2013)
Williams, J., Joharizadeh, N., Gordon, A.D., Sarkar, A.: Higher-order spreadsheets with spilled arrays (with appendices). Tech. rep., Microsoft Research (2020), https://aka.ms/calcintel
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2020 The Author(s)
About this paper
Cite this paper
Williams, J., Joharizadeh, N., Gordon, A.D., Sarkar, A. (2020). Higher-Order Spreadsheets with Spilled Arrays. In: Müller, P. (eds) Programming Languages and Systems. ESOP 2020. Lecture Notes in Computer Science(), vol 12075. Springer, Cham. https://doi.org/10.1007/978-3-030-44914-8_27
Download citation
DOI: https://doi.org/10.1007/978-3-030-44914-8_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-44913-1
Online ISBN: 978-3-030-44914-8
eBook Packages: Computer ScienceComputer Science (R0)