I would like to understand how a spreadsheet (a group of named or otherwise identified cells containing values or formulas referencing other cells) is solved. I have tried looking at existing projects, but there was so much going on with the GUI, serialization, events, etc. that I couldn't find the spreadsheet.
At its simplest how does it work?
At its core, a spreadsheet is a functional language with dynamic typing and each function or value being able to be referenced as a cell in the matrix.
Instead of things like (defn some-name ...) the some-name part is placed in a cell itself.
If you go to a dynamically updating functional language ide (such as lighttable for clojure), you will see much of the same functionality as a spreadsheet. Bind a value to a name, write a function that uses that value, change the value and the output of the function changes immediately. This is the same as doing something like writing =A1 + B2 in the location of C3 in excel.
Thus, functional programmers often like to write spreadsheets as toy programs... and the subject of research papers too. (Yes, I'm sorry, they are all behind an ACM.org paywall)
Spreadsheet functional programming
The functional programming community has shown some interest in spreadsheets, but surprisingly no one seems to have considered making a standard spreadsheet, such as Excel, work with a standard functional programming language, such as Haskell. In this paper, we show one way that this can be done. Our hope is that by doing so, we might get spreadsheet programmers to give functional programming a try.
Forms/3: A first-order visual language to explore the boundaries of the spreadsheet paradigm
Although detractors of functional programming sometimes claim that functional programming is too difficult or counter-intuitive for most programmers to understand and use, evidence to the contrary can be found by looking at the popularity of spreadsheets. The spreadsheet paradigm, a first-order subset of the functional programming paradigm, has found wide acceptance among both programmers and end users. Still, there are many limitations with most spreadsheet systems. In this paper, we discuss language features that eliminate several of these limitations without deviating from the first-order, declarative evaluation model.
Implementing function spreadsheets
A large amount of end-user development is done with spreadsheets. The spreadsheet metaphor is attractive because it is visual and accommodates interactive experimentation, but as observed by Peyton Jones, Blackwell and Burnett, the spreadsheet metaphor does not admit even the most basic abstraction: that of turning an expression into a named function. Hence they proposed a way to define a function in terms of a worksheet with designated input and output cells; we shall call it a function sheet.
The start of Spreadsheet at Wikipedia gives some hints as to how to implement one:
A spreadsheet is an interactive computer application program for organization and analysis of data in tabular form. Spreadsheets developed as computerized simulations of paper accounting worksheets. The program operates on data represented as cells of an array, organized in rows and columns. Each cell of the array is a model–view–controller element that can contain either numeric or text data, or the results of formulas that automatically calculate and display a value based on the contents of other cells.
Building on this from Outline of Model-View-Controller paradigm as expressed in the Java libraries. The author goes on to mention applets (a bit dated, it was written in '93-'96) and mentions his web page which goes to http://csis.pace.edu/~bergin/Java/applets.htm (yes, applets) for the corresponding spreadsheet code http://csis.pace.edu/~bergin/Java/Spreadsheet.java
I will point out that the entirety of the spreadsheet, is not that big in this applet 570 lines including documentation.
That said, depending on the language, you could probably do it all with just function pointers in a sparse array.
Conceptually, each cell is a node of a directed acyclic graph, and references to other cells create edges in that graph. When you change a cell, a topological sorting of all the nodes reachable from the cell you changed will give you the order you need to evaluate the cells. Once you've determined the correct order, it's just standard expression parsing.
As mentioned already, a spreadsheet is easily implemented as a DAG (directed acyclic graph) stored in a simple hash or dictionary. Some simple code to play with is probably the easiest way to understand it:
A very simple Python version: http://code.activestate.com/recipes/355045-spreadsheet/
This was explained and elaborated in this blog post: http://ralsina.me/weblog/posts/BB585.html
There's also a simple JavaScript version with a GUI here: http://jsfiddle.net/ondras/hYfN3/
with which is deprecated and eval which is dangerous. But it does work. Sort of. It shows that it's possible without a DAG.
I have coded a python package that allows you to convert MS Excel file objective function cells structure into Python. XL2py
Cell values are parsed to a dict() type object appends their values. Cells with references to other cells by formulas comprise nodes. Nodes refer to a cell whose value is defined by its formula. From each node formula, a dependency structure is defined so as to define whether circular references exists or not. Node calculation orders are defined by taking into account involved cells dependency structures.
As of the I/O tree-structure, you may use any minimization algorithm implement in Python as your will.
I would suggest you take a look at https://github.com/gusmaogabriels/XL2py
Best regards, Gabriel
