Skip to main content

Ralsina.Me — Roberto Alsina's website

Posts about StupidSheet

Coming soon...

I have man­aged to cre­ate the most bizarre way to write a spread­sheet en­gine in Python.

I still need to pol­ish some things, but here are the high­light­s:

  • Your for­­mu­las com­pile to C

  • C is in­­­lined us­ing In­­s­tant

Yes, that means you ed­it a cell in the GUI and you need to wait un­til gcc com­piles the thing.

Is it go­ing to be use­ful? Prob­a­bly not. Is it cool? I say yeah.

I will pol­ish it some­what, cre­ate a sttan­dalone en­gine, and show it here.

Sometimes, you need to do it the hard way.

You may have no­ticed no posts about Stupid­Sheet for about a week.

Well, I ran in­to the lim­i­ta­tions of the for­mu­la pars­er I was do­ing us­ing Ape­ri­ot. I just could­n't make it parse this:

A1=IF(A2=B2,1,0)

So, I spent the next week try­ing one pars­ing pack­age for Python a day un­til I could find one I un­der­stood and could make it parse that ex­am­ple.

I must say it was ed­u­ca­tion­al.

So, now the pars­er is based on PLY which is pret­ty much Lex+Y­ACC with a (s­light­ly more) python­ic syn­tax, and it work­s.

Yes, it's a bit hard­er, but by try­ing to do things sim­ply I was lim­it­ing my­self too much, and, per­haps un­der­es­ti­mat­ing my­self.

I am a pret­ty smart guy, there is no rea­son I can't un­der­stand these things.

Almost a real spreadsheet! (with video)

I was able to hack a bit at Stupid­Sheet this morn­ing, and there are some re­al ad­vances.

In fac­t, it's a bare­ly func­tion­al spread­sheet al­ready! Hel­l, it has at least one fea­ture OOcalc lack­s, and one both OOcalc and KSpread missed.

Check it out in this video (9.5M­B):

Sor­ry, dead file

Sor­ry if the au­dio is out of sync and/or too low. And you prob­a­bly can't stream it, you need to down­load it first. And maybe it will 404 on you. If that's the case, wait a few min­utes and in­sist.

Stupid Sheet: Redoing cell displacements

For my spread­sheet pro­jec­t, I had to re­do some­thing I had for­got­ten about: cell dis­place­men­t. I did that once when the for­mu­la lan­guage was python.

At the time, I parsed the python us­ing the to­k­enize mod­ule and Ka-Ping Yee's re­gur­gi­tate.

Python->­To­ken­s->Dis­place cell­s->re­gur­gi­tate->Python

Since I have lots of oth­er things to do, I de­cid­ed to do it the same way, and wrote the equiv­a­lent of re­gur­gi­tate for Trax­ter, my for­mu­la lan­guage.

It turns out it was not re­al­ly hard, but I had to re­do parts of the pars­er so it kept more in­for­ma­tion about the source.

Af­ter that it was sim­ple, you see, Trax­ter com­piles to Python. That means all I had to do was an­oth­er (very sim­i­lar) back­end, and there it is, a Trax­ter-­to-­Trax­ter com­pil­er. Or de­com­pil­er. Or some­thing. And rel­a­tive cell ref­er­ences are work­ing again (and now with the right syn­tax).

A graph is a graph is a graph.

Af­ter hack­ing for about two hours the cell de­pen­den­cies yes­ter­day us­ing dict­s, I found my­self say­ing "how can I check if the de­pen­den­cy graph is cycli­cal?"

And of course it hit me. That's the de­pen­den­cy graph. Use a graph li­brary!

I looked for about 2 min­utes be­fore find­ing one that's prob­a­bly not op­ti­mal, but is damn sim­ple and in the pub­lic do­main: graph_lib.py by Nathan Den­ny.

First in­ter­est­ing da­ta point, the first two lines on the file (yes, I found out there is a lat­er ver­sion):

#--Version 1.0.0
#--Nathan Denny, May 27, 1999

Yup. In two days this piece of code is turn­ing 8 years old and un­touched. But it works just fine and dandy!

Here's the piece of code that makes the en­gine run which has grown from a hum­ble 10 LOC to al­most a whoop­ing 40 LOC:

class SpreadSheet(QtCore.QObject):
    _cells = {}
    tools = {}
    graph=Graph()

    def __init__(self,parent):
        QtCore.QObject.__init__(self,parent)
        for name in dir(functions):
                self.tools[name]=eval('functions.'+name)


    def __setitem__(self, key, formula):
        key=key.lower()
        c=traxcompile('%s=%s;'%(key,formula))
        self._cells[key] = [c[key][0],False,compile(c[key][0],"Formula for %s"%key,'eval')]

        # Dependency graph
        if not self.graph.has_node(key):
                self.graph.add_node(key)
        for edge in self.graph.in_arcs(key):
                self.graph.delete_edge(edge)
        for cell in c[key][1]:
                self.graph.add_edge(cell,key)
        try:
                print 'GRAPH(TOPO): ',self.graph.topological_sort()
                self._cells[key][1]=False
                print 'GRAPH(BFS) : ',self.graph.bfs(key)
                for cell in self.graph.bfs(key)[1:]:
                        self.emit(QtCore.SIGNAL('changed'),(cell))
        except Graph_topological_error:
                # We made the graph cyclic
                # So, mark this cell as evil
                self._cells[key][1]=True
                # And remove all incoming edges to go back to
                # status quo
                for edge in self.graph.in_arcs(key):
                        self.graph.delete_edge(edge)

    def getformula(self, key):
        key=key.lower()
        return self._cells[key][0]
    def __getitem__(self, key ):
        print self._cells[key]
        if self._cells[key][1]:
                return "ERROR: cyclic dependency"
        else:
                print 'evaluating [%s]: '%key,type(self._cells[key][0]),self._cells[key][0]
              return eval(self._cells[key][0], self.tools, self)

This en­gine sup­port­s:

  • Us­er de­fined func­­tions (just add them in for­­mu­la.py)

  • Cell de­pen­­den­­cies with de­tec­­tion of ci­­cles, of any length

  • Un­lim­it­ed size spread­­sheets

  • No­ti­­fi­­ca­­tion of cell changes to oth­­er mod­­ules

  • Au­­to­­mat­ic re­­cal­cu­la­­tion

  • A cus­­tom for­­mu­la lan­guage (ok, that's not in this piece of code ;-)

The whole project is now 1167 LOC, of which 591 are gen­er­at­ed or graph_lib, which means ev­ery­thing in­clud­ing the trax­ter "com­pil­er" and the UI is less than 600 lines of code.

Not too shab­by.

My goal is a func­tion­al spread­sheet with a work­ing GUI and sup­port­ing the most com­mon func­tions and pieces of the for­mu­la lan­guage in .... 2000 LOC, and I am will­ing to work on it for about two week­s.

Let's see how it turns out. Of course any­one with 5 free min­utes can con­trib­ute his favourite spread­sheet func­tion (I al­ready have sum ;-)


Contents © 2000-2023 Roberto Alsina