How to implement a spreadsheet
semantic-domain.blogspot.com
semantic-domain.blogspot.com
https://en.wikipedia.org/wiki/Apropos_%28Unix%29 : "Often a wrapper for the "man -k" command, the apropos command is used to search all manual pages for the string specified. This is often useful if one knows the action that is desired, but does not remember the exact command or page name."
TBH learning now that "man -k" exists (I don't think I can have "man man"-ed in the last decade) is probably a lot more useful for me.
man -K MANOPT
A far more severe problem IMO is the fact that many Linux distros ship without manpages in their default installs.
Ouch, too much Debian credit, too much Linux credit, even. That's by Bill Joy circa 1977, so it's a BSD Unix thing, widely adopted everywhere else.
Man -k was AT&T's reaction to apropos, IIRC. There is a certain logic to using "man" to search man pages.
The file format is pretty simple. At least for the spreadsheets I create.
As a side note, I love text-based (or extremely simple) file formats. So easy to write tools for them.
# This data file was generated by the Spreadsheet Calculator.
# You almost certainly shouldn't edit it.
let A0 = 45
let A1 = 56
let A2 = @sum(A0:A1) gcc -I/usr/include/X11 jarijyrki.c -o jarijyrki
jarijyrki.c:15:33: error: ‘U’ undeclared here (not in a function)
int q,P,W,Z,X,Y,r,u; char E[U][U][T+1] ,D[T]; Window J; GC k; XEvent w;
^ ${CC} ${X11CCFLAGS} ${CFLAGS} -DNeedFunctionPrototypes \
-DU=40 -DT=98 '-Dz=(T+1)*U*U' -DQ=80 -DS=20 -DN=10 -DB=5 -DG=23 \
-Dp=7 '-DM=((p+1)*Q)+S' '-DH=(G*S)+S+S' -DC=XK_Up -DL=XK_Down \
-DO=XK_Left -DV=XK_Right -DR=XK_Escape -D_=XK_BackSpace \
$? -o $@ ${X11LDFLAGS} -lX11
[1] http://www.ioccc.org/2000/Makefile [2] http://www.ioccc.org/2000/sheet1.info
ex.
loeb [const 1,
const 2,
\xs -> x !! 0 + x !! 1]
Naturally, it doesn't allow for mutations or anything fancy, but it is an interesting curiosity.
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)Here's a presentation that dives into loeb and expands it to a comonadic fixpoint that lets you do the fibs example correctly: https://www.youtube.com/watch?v=F7F-BzOB670
http://blog.sigfpe.com/2006/11/from-l-theorem-to-spreadsheet...
(I completely missed your GitHub link the first time I read this comment)
> let xs = [1, 2, (xs !! 0) + (xs !! 1)] in xs
[1, 2, 3]
> let xs = [(xs !! 1) - 1, (xs !! 2) - 1, 3] in xs
[1, 2, 3]
All of these spreadsheets are, naturally, written in emacs lisp.
Nice to see it in OCaml though.
But it might have been there as well.
I have stumbled on massive spreadsheets in the wild where most of the cells needed to be recalculated when you changed something, and that could take a long time to recalculate.
It seems like most software out there today does this, which is pretty cool.
You'll probably also end up learning a thing or two about JavaScript. Even now, 2 years after I first saw this, I'm seeing new things in it, and I've been doing JS for 20 years.
with (DATA) return eval(value.substring(1));
Anyway, I'm not aware of any JS feature which wouldn't be easily replicated in most other dynamic languages. JS was rather unlucky when it comes to language features - its development stalled for years, while in the same time Python, Perl, Ruby, PHP evolved quickly. JS only now gets features implemented in other langs many years ago.
- Everything gets recomputed on any minor change.
- If a cell is referenced by N other cells, it will be recomputed N+1 times on every update. Worse, this can be exponential for A2=A1+A1, A3=A2+A2, which leads to A1 being recomputed 5 times. There's no sharing or memoization.
- Circular references are detected because they trigger a "too much recursion" exception.
- An impure cell "=Math.random()" will be observed with different values by its dependencies.
Incidentally, I have been playing around with the concept myself (client work) and it turns out you can hack a semi-working solution in just a handful lines of js:
http://kephra.de/copycat/zarasheet/
I kept the references. Both the original fiddle and the authors website are linked from my page.
http://z80cpu.eu/files/archive/rlee/B/BORLAND/TURBO%20PASCAL...
NB I know you can get Google spreadsheet data as JSON, but I was more thinking of something where you could have "headless" operation that could be embedded in other applications.
http://docs.oasis-open.org/office/v1.2/os/OpenDocument-v1.2-...
Nevertheless, removing the "reads" seems more worthwhile than removing "observers". You want to model the data flow efficiently, not the data dependencies. The dependencies are provided indirectly in the code anyways.
It has a few novel features like transactional input.
We use Javelin for state management in the hoplon.io web framework.
which basically allows to express interdependencies between data (a.k.a. formulas) in a way that updates sink variables when source variables are changed.
At the moment, I think not even Rx extensions for .NET (which I consider to be the most advanced reactive implementation in a mainstream language) do support this style of computation.
I did not take the approach of cells actually observing each other. Instead I had a recursive function that worked from the entered cell to:
-- parsed a string DSL of "=sum(B4:B8)" into a javascript function, that pulls some premade functions like sum, vlookup etc, and makes a string list representing what an arguments getter will need to fetch ("a_r3c1_r7c1" ie array, row 3, col 1 to row 7 col 1). The user still just sees "=sum(B4:B8)"
-- note who "I depend on",
-- note who "depends on me"
-- recurse 'outwards', skipping cells in "depends on me" that are still waiting on 'needs recalc' of their own "I depend on".
The update algorithm is not the hard part. Microsoft also has a very detailed documentation of their own update algorithm online (cant find it at the moment though).
The hardest part was updating the string representations of the formulas when you insert a new column or row, and then re-updating each cell's dependencies arrays.
Definitely not a performance problem, but more of a "how the fuck do I wrap my head around all the different ways someone could want to insert, cut, copy and paster here".
One mistake I made was trying to impliment the undo/redo to be totally reversable at every step. So every command stores the way to go both back and forward. In hindsight, I should have just stored forward commands and rebaked from the beginning when someone wanted to go back in time.
I wish I had more time to work on the project, but I've been busy with other work.
notes: - an excel to JSON parsing library in node :) https://github.com/NickStefan/parsexcel.js
- A lot of people mentioning Handsontable.js. That library has some major design flaws. We used it in our git style version controlled spreadsheet app (http://www.gridhub.xyx). Handsontable only takes simple 'number' or 'string' value for each cell. It should have been an object that could store CSS for that cell, formula for that cell, and the value for that cell. I made a few pull requests, but they largely ignored me. The code is odd (they use labels, continue, and other C style code).Handsontable is great only for presenting tables. Its terrible for implementing a full excel clone.
There is nothing language specific here, just think of the OCaml as pseudo-code.