{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:53:17Z","timestamp":1790927597535,"version":"4.1.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030449131","type":"print"},{"value":"9783030449148","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T00:00:00Z","timestamp":1587168000000},"content-version":"vor","delay-in-days":108,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We develop a theory for two recently-proposed spreadsheet mechanisms: <jats:italic>gridlets<\/jats:italic> allow for abstraction and reuse in spreadsheets, and build on <jats:italic>spilled arrays<\/jats:italic>, 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 <jats:italic>grid calculus<\/jats:italic>, 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.<\/jats:p>","DOI":"10.1007\/978-3-030-44914-8_27","type":"book-chapter","created":{"date-parts":[[2020,4,17]],"date-time":"2020-04-17T10:02:53Z","timestamp":1587117773000},"page":"743-769","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Higher-Order Spreadsheets with Spilled Arrays"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1925-7191","authenticated-orcid":false,"given":"Jack","family":"Williams","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6659-517X","authenticated-orcid":false,"given":"Nima","family":"Joharizadeh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5809-2484","authenticated-orcid":false,"given":"Andrew D.","family":"Gordon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5401-3478","authenticated-orcid":false,"given":"Advait","family":"Sarkar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,18]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Abadi, M., Cardelli, L.: A Theory of Objects. Monographs in Computer Science, Springer (1996)","DOI":"10.1007\/978-1-4419-8598-9"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, R., Erwig, M.: Inferring templates from spreadsheets. In: Proceedings of the 28th International Conference on Software Engineering. pp. 182\u2013191. ICSE \u201906, ACM, New York, NY, USA (2006)","DOI":"10.1145\/1134285.1134312"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"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\u201384. PPDP \u201906, ACM, New York, NY, USA (2006)","DOI":"10.1145\/1140335.1140346"},{"key":"27_CR4","unstructured":"Bock, A.A., B\u00f8gholm, 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)"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"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\u2013206 (2001)","DOI":"10.1017\/S0956796800003828"},{"key":"27_CR6","doi-asserted-by":"crossref","unstructured":"Chambers, C., Ungar, D.M.: Customization: Optimizing compiler technology for self, A dynamically-typed object-oriented programming language. In: PLDI. pp. 146\u2013160. ACM (1989)","DOI":"10.1145\/74818.74831"},{"key":"27_CR7","doi-asserted-by":"crossref","unstructured":"Cheng, T., Rival, X.: Static analysis of spreadsheet applications for type-unsafe operations detection. In: Vitek, J. (ed.) Programming Languages and Systems, pp. 26\u201352. Springer, Berlin Heidelberg, Berlin, Heidelberg (2015)","DOI":"10.1007\/978-3-662-46669-8_2"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Clack, C., Braine, L.: Object-oriented functional spreadsheets. In: 10th Glasgow Workshop on Functional Programming. pp. 1\u201312 (1997)","DOI":"10.1007\/3-540-63237-9_16"},{"key":"27_CR9","unstructured":"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\u2013141. IEEE (1998)"},{"key":"27_CR10","doi-asserted-by":"crossref","unstructured":"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\u2013145. ACM (2005)","DOI":"10.1145\/1062455.1062494"},{"key":"27_CR11","unstructured":"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\/"},{"key":"27_CR12","doi-asserted-by":"publisher","unstructured":"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 \u201920, ACM, New York, NY, USA (2020). https:\/\/doi.org\/10.1145\/3334480.3382806,http:\/\/doi.acm.org\/10.1145\/3334480.3382806","DOI":"10.1145\/3334480.3382806,"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Kay, A.: Computer software. Scientific American 251(3), 52\u201359 (1984), http:\/\/www.jstor.org\/stable\/24920344","DOI":"10.1038\/scientificamerican0984-52"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.1017\/S0956796820000234"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"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\u2013127. Onward! 2016, ACM, New York, NY, USA (2016)","DOI":"10.1145\/2986012.2986018"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"Mokhov, A., Mitchell, N., Peyton Jones, S.: Build systems \u00e0 la carte. PACMPL 2(ICFP), 79:1\u201379:29 (2018)","DOI":"10.1145\/3236774"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Peyton Jones, S.L., Blackwell, A.F., Burnett, M.M.: A user-centred approach to functions in Excel. In: ICFP. pp. 165\u2013176. ACM (2003)","DOI":"10.1145\/944746.944721"},{"key":"27_CR18","doi-asserted-by":"publisher","unstructured":"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\u201393 (Oct 2018). https:\/\/doi.org\/10.1109\/VLHCC.2018.8506584","DOI":"10.1109\/VLHCC.2018.8506584"},{"key":"27_CR19","doi-asserted-by":"crossref","unstructured":"Sestoft, P.: Implementing function spreadsheets. In: Proceedings of the 4th international workshop on End-user software engineering. pp. 91\u201394. ACM (2008)","DOI":"10.1145\/1370847.1370867"},{"key":"27_CR20","doi-asserted-by":"crossref","unstructured":"Sestoft, P., S\u00f8rensen, J.Z.: Sheet-defined functions: Implementation and initial evaluation. In: Dittrich, Y., Burnett, M., M\u00f8rch, A., Redmiles, D. (eds.) End-User Development, pp. 88\u2013103. Springer, Berlin Heidelberg, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-38706-7_8"},{"key":"27_CR21","doi-asserted-by":"crossref","unstructured":"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","DOI":"10.26226\/morressier.604907f41a80aac83ca25d58"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-44914-8_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T17:12:46Z","timestamp":1656609166000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-44914-8_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030449131","9783030449148"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-44914-8_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"18 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ESOP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Symposium on Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dublin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ireland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 April 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 April 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esop2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/2020\/esop","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"87","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"27","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"31% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11-12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference could not take place due to the COVID-19 pandemic. There was an online event on July 2, 2020.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}