Spreadsheets Are Special

Written by Janet Swift

Thursday, 17 September 2020

Article Index
Spreadsheets Are Special
Cellular Automata And Spreadsheets

Page 2 of 2

The CA way to parallel programming

The use of a range reference and a function to get rid of the for loop is just the start.

An adventurous spreadsheet user can write formulas that refer to formulae stored in other cells. This raises the level of sophistication to the point were it reaches the forefront of computer science research.

The problem is that if you have formulae in different cells and one cell depends on the result of another then the result will depend on the order that you evaluate them in.

In other words a set of self-referencing formulas produces a race hazard and even the possibility of circular dependency.

At first spreadsheet implementers solved this problem by simply imposing some rules that gave a known order of evaluation - usually top to bottom and left to right.

Spreadsheet users quickly learned to think in terms of "everything above and to the left is evaluated and safe to use".

This may seem like avoiding the issue but even this simple approach could cope with circular references that needed an iterative approach to evaluate.

The spreadsheet would simply recalculate itself repeatedly in the same order until it was either stopped or until the calculation converged to a solution.

Later spreadsheets took a more reasonable and efficient approach to re-computation and created a dependency graph that allowed the expressions to be evaluated in a natural order. This didn't eliminate the need to iterate to evaluate circular references but it did mean that you could write formulas that depended on other results anywhere in the spreadsheet and expect the system to work out everything in a sensible order.

Today we have rediscovered this approach in reactive programming. In a reactive language you set up relations between variables that work exactly like spreadsheet references. If you write A=B+C then variable A is updated every time B or C change their value. You are establishing a long term relationship between A, B and C rather than a one off update as in procedural programming. In reactive programming we use different jargon but essentially what is being reinvented is the spreadsheet approach to programming.

What is less obvious is that the spreadsheet brings with it a natural approach to parallel programming. Each formula entered into a cell is to be evaluated in place and display its current result in that cell. This is an inherently parallel algorithm. If you could build the hardware equivalent of a spreadsheet with one processor per cell then all you would have to do is ensure that each processor evaluated just the formula in its cell and display the result.

In this case the order of evaluation doesn't matter as long as the processors always re-compute until the results settle to a stable state. While this would not be a good way to implement a software emulation of the spreadsheet concept it is a very reasonable way for real hardware to be used - the settling time would be very short. As it happens I was involved in a project to build a machine exactly like this and its settling time was fast enough for real time changes to be made.

This whole approach to parallel processing is of course nothing more than a cellular automaton (CA).

The CA is possibly the most important computational architecture we have yet to explore. It has been suggested that a CA can give us the theory of everything we have been looking for.

If you don't believe that CAs are capable of great complexity then just take a look at the Game of Life - a 2D CA with amazingly simple rules that generates very complex behaviour. The idea is that something like the simple rules for Life are at the heart of the universe which simply gets on computing those rules and on the way generates all there is.

The spreadsheet is a CA and it is an advanced computational model that turns out to be surprisingly easy to use.

Whatever you think of the spreadsheet don't dismiss it as trivial.

spreadicon

Janet Swift is a long-term spreadsheet afficianado and her books about Lotus 1-2-3 and SuperCalc were very well received. Financial Functions With A Spreadsheet is part of the I Programmer Library from I/O Press.

Mitch Kapor and Lotus 1-2-3

Dan Bricklin - inventor of the PC spreadsheet

Is Excel To Blame For Our Economic Pain?

Companies That Use Spreadsheets Survive

Spreadsheet Risk Revealed

Getting at the Data

The Meaning of Life

Excel 2019 Bible (Book Review)

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

DuckDB And Hydra Partner To Get DuckDB Into PostgreSQL
11/11/2024

The offspring of that partnership is pg_duckdb, an extension that embeds the DuckDB engine into the PostgreSQL database, allowing it to handle analytical workloads.

+ Full Story

Azul Outperforms OpenJDK By Up To 37%
23/10/2024

Azul has announced that its Azul Platform Prime outperforms comparable OpenJDK distributions by as much as 37%. The company has also launched the Azul Java Performance Engineering Lab (JPEL) aimed at [ ... ]

+ Full Story

More News