Grid

Notes on Grid

Sheets

The following defines a single-sheet spreadsheet without named ranges.

For $M$ and $M$ non-negative integers, an $M× N$ grid is the set of all pairs of integers $(m, n)$ where $0\leq m < M$ and $0\leq n < N$. An $M× N$ sheet is a map from an $M× N$ grid to the set of possible cell values (see below).

A cell address is a pair $(m, n)$. We call $m$ the column and $n$ the row. A range address is a contiguous rectangle of cell addresses. That is, for cell address $(m, n)$ and non-negative integers $W$ and $H$, a range address is all pairs $(m + w, n + h)$ with $0\leq w < W$ and $0\leq h < H$. We call $W$ the width and $H$ the height of the range.

The value of a grid program is a sheet. The main, non-trivial challenge in evaluating a grid program is in sorting out the references.

Cells

Cells contain expressions and metadata. All values in our model are arrays; a single value is a $1× 1$ array. The possible value ‘nothing’ occurs when a cell refers to an empty cell (note that functions replace empty cells with values appropriate to their domain).

The following describes the contents of cells.

# A cell is a pair 
<cell> ::= (<expression> <meta>)

<expression> ::= <value>
               | <application>
               | <reference>
               | <name>

<value> ::= Array-of <atomic-value>

<atomic-value> ::= number?
                 | string?
                 | boolean?
                 | nothing?

Aside: We had some discussion about whether nothing? should not be an <expression>; after all, in some spreadsheets there are empty cells. However, it seemed convenient to unify the result of evaluating a range with <value>’s so that we only pass one thing to functions (namely, <values>), and it is the case that not all functions treat an empty cell in the same way. (For example, SUM replaces it with 0, AVERAGE ignores it, and so on.)

Aside: A <value> is always an array. Many values will be 1×1 arrays: we call these simple values. ~<value>’s have a non-zero dimension.

An application is an application of a built-in function to zero or more expressions.

<application> ::= (<builtin> <expression> ...)

Our model is that an <expression> is evaluated to give a <value>; then it is values that are passed to the builtins. However, note that the value of a cell is the top-left atomic value of the value of its expression.

Builtins come in different groups, depending on the usual type of the arguments. Some builtins require their arguments to be simple values; some allow non-simple values.

---

THE FOLLOWING IS OUT OF DATE

# An address is a row and a column
<cell-addr> ::= (<col-addr> <row-addr>)

<col-addr> ::= 1 | 2 | 3 | ...
<row-addr> ::= 1 | 2 | 3 | ...

<cell-value> ::= | Empty
                 | <literal>
                 | <cell-addr>
                 | (apply <builtin> <cell-expr> <cell-expr> ...)
                 
# A cell expression is a literal value or a formula
<cell-expr> ::= <literal>
                 | <cell-addr>
                 | <range-addr>
                 | (apply <builtin> <cell-expr> <cell-expr> ...)

<range-addr> ::= (<cell-addr> <cell-addr>)

<literal>  ::= <Integer> | <Inexact-Rational> | <String> | <Boolean> | <Error> 
<builtin> ::=
## Number ... -> Number
# Unary and binary + and - and n-ary +
    | + | -
    | * | / | quotient | remainder 
    | modulo
    | abs | max | min | round | floor | ceiling | truncate
    | sin | cos | tan | asin | acos | atan
    | random
    | sqrt | expt | exp | log | log10
## Number ... -> Boolean
## String ... -> Boolean
    | = | < | <= | > | >=
## Number -> String
## String -> Number
## Boolean -> Any
    | if 
## The following take or return an argument that is a range
    | vector-index | vector-match | 
    | array-index | array-match
    | offset
    | sum | count | mean | median | mode | quartile
    

# I haven't figured out formats yet. But format-depth means the depth of this
# cell in the function tree.
<cell-format> ::= (<format-type> <format-depth>)
<format-type> ::= none 
<format-depth> ::= <Natural>

Notes from conversation with TC

The grid language looks like this:

(sheet
 (row
  (cell 1 #:name fred) (cell (app + 1 :fred)) ...)
 (row ..)
 ..
 )