Homework 7: Spreadsheet

Due: 12/3

In [1]:
runTkinter = True  # use this to control running Tkinter examples in this notebook
allowExceptions = True # use this to skip execeptions, which halt notebook execution

In a module spreadsheet.py create a new tkinter-based class called Spreadsheet that is a Frame that contains a labelled array of cells that looks something like this (including a focus Label and a focus Entry -- see below):

Spreadsheet illustration

In this figure, the focus Label is on the left of the bottom row (containing "a0:") and the focus Entry (empty in this case) is to its right.

The prototype for a Spreadsheet instantiation is: Spreadsheet(parent, nRows=4, nColumns=4) where nRows is the number of rows and nColumns is the number of columns. The columns are numbered left to right from 0 to nColumns-1. The nRows rows are lettered in lower case starting with a in on the top. (Don't worry about having more than 26 rows for now!)

Let's demonstrate this. The solution module contains a self-test that creates a 4x4 spreadsheet:

In [2]:
if runTkinter:
    !python3 -m spreadsheet

The interaction model for this spreadsheet differs from that of normal Excel$^{TM}$-like (actually, VisiCalc$^{TM}$-like) spreadsheets, and may actually be easier for a programmer (especially a Python programmer) to understand. In "normal" spreadsheets, cells have text values or numeric values. In this case, all cells contain strings which can be evaluated like any Python expression. Strings evaluate to themselves and can therefore be used as both data and labels.

Cell expressions can use the names of other cells, with the exception that a cell cannot refer to itself either directly or indirectly. That's called a "cycle". We'll demonstrate it below.

The suggested implementation is to give each cell at least these three attributes:

  • an expression: a string the user types into the focus Entry (below)

  • a code: a code (that's a class) object created by the compile() builtin), and

  • a value: the result of evaluating the code (using eval() and, converted to a string (using str()), is what the users see when they look at a cell.

At any given time, one cell is the "focus". It appears with a yellow background. Associated with the focus are two additional widgets: the "focus Label" and the "focus Entry". The focus Entry is where the user edits the expression string for the focus and the focus Label is the name ("a0", "c3", etc.) of the focus cell. They are attributes (focusLabel and focusEntry) of the Spreadsheet and must be placed (e.g. via grid()) separately from the Spreadsheet widget itself.

It is strongly recommended that the cells be placed within the Spreadsheet using the grid geometry manager.

The user can click on any cell in the cell array to make it the focus. The focus Entry shows that cell's expression string and the focus Label shows its label. Pressing the Enter or Tab keys causes the focus Entry to become the cell's expression string, which is then compiled to a new code. After that, the cell and all cells related to it are updated to reflect the new value.

As states above, the cell array (i.e., the Spreadsheet), the focus Label, and the focus Entry all need to be placed with a geometry manager. Here is a test program (which is also the spreadsheet module's self-test) that your implementation should support:

In [3]:
%%file spreadsheet_t.py
from tkinter import Tk
from spreadsheet import Spreadsheet

root = Tk()
nRows = 6
nCols = 8
root.title(f"A {nRows}x{nCols} Spreadsheet")
spreadsheet = Spreadsheet(root, nRows, nCols)
spreadsheet.grid(row=1, column=0, columnspan=nCols)
spreadsheet.focusLabel.grid(row=0, column=0)
spreadsheet.focusEntry.grid(row=0, column=1)
root.mainloop()

Overwriting spreadsheet_t.py
In [4]:
if runTkinter:
    !python3 spreadsheet_t.py

This is downloadable from the web page, along with a working spreadsheet.pyc to compare against your work. The grader may have one or more tests that differ from this, but your code should at least work with this.

Note that spreadsheet.pyc is a bytecode-compiled version of the instructor's solution that can be imported via "import spreadsheet" or invoked from the command line like any other Python module:

In [5]:
if runTkinter:
    !python3 spreadsheet.pyc

It should work on any platform running Python 3.8, since Python bytecodes are platform-independent.

Compiling and Evaluating Cells

Initially, all cells start with a expression "" (an empty string) and a code of None, so all cells initially appear blank.

To show how evaluation works, let's take an example. Let's suppose we want to have an expression in cell a2 that adds the contents of cells a0 and a1, respectively. We would enter the right side of this expression in a2:

In [6]:
expression = "a0 + a1"

When this expression is entered, we use compile() to create an instance of the code class that represents it:

In [7]:
codeObject = compile(expression, "a2", 'eval')

In order to evaluate codeObject, we must provide a dictionary that maps the symbols expr uses to values. We call this a "symbol table":

In [8]:
symbolTable = { 'a0': 1, "a1": 2 }

and then pass this to eval() to get a value:

In [10]:
value = eval(codeObject, {}, symbolTable)
value
Out[10]:
3

Passing symbolTable as the third argument to eval() makes it refer to its symbols as global, rather than local. This is what we want. (Local would make sense if we were inside a function or method, which we are not.)

When we display this in a Cell (which is a Label) we would use str() to convert it to a string (if necessary):

In [ ]:
str(value)

It's convenient to always use str(), even if value is already a string.

Adding More Symbols to the Symbol Table

We can add other symbols to symtab and they can map to objects such as functions and constants:

In [11]:
def f(x):
    return x**2 + 3
symbolTable['f'] = f
from math import sin, pi
symbolTable['sin'] = sin
symbolTable['pi'] = pi
expr = 'f(a0) + sin(pi/4)'
codeObject = compile(expr, 'a3', 'eval')
eval(codeObject, {}, symbolTable)
Out[11]:
4.707106781186548

Your Spreadsheet should allow users to use all of the functions and constants (e.g.pi) in the math module. You can find them in the module's __dict__ attribute (i.e. its symbol table), but ignore those symbols that begin with '_'.

Dealing With Dependencies

When the user changes a cell's expression, it's not enough to update the cell itself. We also need to update all cells that depend on that cell. This is a problem in graph theory. Solving it is beyond the range of this course, so I've provided a dependencies module to do that for you. (You're free to write your own, of course!)

Here's how it works:

Set up a dictionary (not the symbol table) that contains the dependencies of each cell by name. If cell a2 is has the expression "a0 + a1" and cell a3 has the expression "f(a0) + sin(pi/4)", the dependencies would be:

In [13]:
deps = { 'a2': ('a0', 'a1'), 'a3': ('a0',)}

There's only one function in dependencies you should need: dependersOn():

In [14]:
from dependencies import dependersOn
In [15]:
help(dependersOn)

Help on function dependersOn in module dependencies:

dependersOn(node, deps)
    returns all nodes that depend on `node`
    
    If a cycle is detected, it raises the `CyclicDependency` exception.
    
    Case 1: normal dependencies (using tuples)
    >>> allDependencies('c', { 'a': ('b', 'c'), 'd': ('a', 'c'), 'f': () })
    ['a', 'd']
    
    Case 2: direct dependence on itself (using a tuple)
    >>> allDependencies('a', { 'a': ('a',) })
    Traceback (most recent call last):
        ...
    CyclicDependency
    
    Case 3: indirect dependence on itself (using a tuple)
    >>> allDependencies('a', { 'a': ('b',), 'b': ('a',) })
    Traceback (most recent call last):
        ...
    CyclicDependency
    
    Case 4: dependency where order matters
    >>> deps = { 'b': ('a',) , 'd': ('a', 'c'), 'c': ('a',)}
    >>> seq = allDependencies('a', deps)
    >>> seq
    ['b', 'd', 'c']
    >>> ordered(seq, deps)
    True

Pass it any cell's name and it will return a list of names of those cells that depend on it and therefore need to be updated:

In [16]:
dependersOn('a0', deps)
Out[16]:
['a2', 'a3']
In [17]:
dependersOn('a1', deps)
Out[17]:
['a2']
In [18]:
dependersOn('a2', deps)
Out[18]:
[]

So all you need is to traverse the list (in order) and update the cells' values in both the symbol table and on the screen.

Finding Dependencies

It will be up to you to build the dependencies dictionary (deps in the above examples). You could parse the expression yourself, but there's a much easier way to do this. When you compile a code object (with compile(), of course), the code object it returns has a number of attributes:

In [19]:
dir(codeObject)
Out[19]:
['__class__',
 '__delattr__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__init_subclass__',
 '__le__',
 '__lt__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 'co_argcount',
 'co_cellvars',
 'co_code',
 'co_consts',
 'co_filename',
 'co_firstlineno',
 'co_flags',
 'co_freevars',
 'co_kwonlyargcount',
 'co_lnotab',
 'co_name',
 'co_names',
 'co_nlocals',
 'co_posonlyargcount',
 'co_stacksize',
 'co_varnames',
 'replace']

The one we want is co_names:

In [20]:
codeObject.co_names
Out[20]:
('f', 'a0', 'sin', 'pi')

This code was produced for a3 (see above) and dependencies only need the names of cells, not the other stuff we put in the symbol table, so we remove everything that isn't a cell name, the appropriate dependency for a3 would be (a0,).

In [ ]:
deps['a3'] = ('a0', )
deps

Cyclic Dependencies

A "cycle" happens when one cell depends, directly or indirectly, on itself. If you pass a dependency dictionary that includes a cycle, dependersOn() will raise a CyclicDependency exception. Here's a direct (and obvious) example:

In [21]:
if allowExceptions:
    cyclicDeps = { 'a': ('a',) }
    dependersOn('a', cyclicDeps)

---------------------------------------------------------------------------
CyclicDependency                          Traceback (most recent call last)
<ipython-input-21-5dd2548d4f67> in <module>
      1 if allowExceptions:
      2     cyclicDeps = { 'a': ('a',) }
----> 3     dependersOn('a', cyclicDeps)

~/Dropbox/cpts481/hw07_spreadsheet/writeup/dependencies.py in dependersOn(node, deps)
     79                 except: # use a generic message
     80                     message = "dependency cycle detected"
---> 81                 raise CyclicDependency(message)
     82             result.append(subNode)
     83 

CyclicDependency: dependency cycle on 'a' detected

Here's a less obvious indirect dependency:

In [22]:
if allowExceptions:
    cyclicDeps = { 'a': ('b',), 'b': ('c',), 'c': ('a',) }
    dependersOn('a', cyclicDeps)

---------------------------------------------------------------------------
CyclicDependency                          Traceback (most recent call last)
<ipython-input-22-00c8e3ca1fd0> in <module>
      1 if allowExceptions:
      2     cyclicDeps = { 'a': ('b',), 'b': ('c',), 'c': ('a',) }
----> 3     dependersOn('a', cyclicDeps)

~/Dropbox/cpts481/hw07_spreadsheet/writeup/dependencies.py in dependersOn(node, deps)
     79                 except: # use a generic message
     80                     message = "dependency cycle detected"
---> 81                 raise CyclicDependency(message)
     82             result.append(subNode)
     83 

CyclicDependency: dependency cycle on 'a' detected

Evaluating a Cell with Error Handling

At no time should you permit a cell to be set to a value that causes a cyclic dependency or otherwise creates an erroneous value anywhere in the spreadsheet. (This is more strict than most spreadsheets.) When your code evaluates a cell c, it should:

  • save the current state of c

  • watch for an exception in the following

    • compile the new expression for c

    • update c's dependencies

    • evaluate the new c

    • evaluate every other cell that depends on c

  • if a CyclicDependency or any other exception (e.g. DivideByZero) is raised:

    • issue an error message using a tkinter message box

    • restore the saved state of c (including its old dependencies)

    • re-evaluate every other cell that depends on c

"evaluate" here includes updating a cell's on-display appearance

Final Notes

Here are some words of advice:

  • Build your code in small steps, testing as you go. (hint: doctest)

  • Factor relevant attributes and methods into the Cell and Spreadsheet classes.

  • Keep functions and methods short.

  • Give variables, functions, and methods meaningful names.

  • Don't start building the user interface until you have a working text-based algorithm.

These are not requirements. This is:

  • Make sure your Spreadsheet works just like a Frame: It should be possible to have several of them in the same application.