The table processor (we are talking about MS Excel or LibreOffice Calc) is a rather entertaining and versatile tool. I often had (and have to) use its wide capabilities: automated reports, hypothesis testing, prototyping of algorithms. For example, I used it to solve the tasks of the Euler project , quickly check algorithms, implemented a parser for one application protocol (I needed to work). I like the visibility that can be achieved in a table processor, and I also like the non-standard application of everything that is possible. Interesting articles on the topic of non-standard application of Excel have already appeared on Habré:
“Assembler in 30 lines on Excel”
What to do for an IT specialist in the army or how I wrote “RPG game in Excel workbook” on VBA games


In this long article, I want to share my experiments in reactive programming using table processor formulas. As a result of these experiments, I got a “computer” with a processor, memory, stack and display, implemented inside LibreOffice Calc using only formulas (with the exception of the clock generator), which can be programmed in a kind of assembler. Then, as an example and proof-of-concept, I wrote the game "Snake" and a running creeping line for this computer.

Foreword

It all started with the fact that I became interested in various programming paradigms, attended an introductory lesson on Verilog at the Robotics Club; and here in the reactive paradigm wikipedia article I came across the following text:

Modern table processors are an example of reactive programming. Table cells can contain string values ​​or a formula of the form “= B1 + C1”, the value of which will be calculated based on the values ​​of the corresponding cells. When the value of one of the dependent cells is changed, the value of this cell will be automatically updated.

Indeed, anyone who used the formulas in Excel knows that changing one cell we change the cells associated with it - it turns out pretty similar to the propagation of a signal in a circuit. All these factors led me to the following thoughts: what if this “chain” is quite complex? Are the formulas in the Turing table processor complete ? Is it possible to “program” the formulas so as to get some non-trivial results? (e.g. make tetris) Since I use Ubuntu at work and at home, I did all the experiments in LibreOffice Calc 4.2.7.2

8x8 digital display

I started experiments with the implementation of the display. The display is a set of 8x8 square cells. Conditional formatting came in handy (it is available in both Excel and Calc). Select the cells, go to Format / Conditional Formatting / Condition ... and adjust the appearance: a black background, provided that the cell contains, for example, a space. Now if you write a space in the cell, then it becomes black. Thus, the pixels of our display are realized. But I want to manage this display somehow. To my left, I highlighted a special column in which numbers will be entered - the idea is that with this number we set a bit mask for display on the screen. At the top of the screen, I numbered the columns. Now in each cell of the display we must write a formula that will result in either a space or an empty line, depending on

= IF (MOD (TRUNC (<bitmask> / (2 ^ <display column number>)); 2); ""; "")

Here, in fact, a shift to the right occurs (division by a power of two and then the fractional part is discarded), and then the 0th bit is taken, that is, the remainder of the division by 2, and if it is set, a space is returned, otherwise an empty string.
Now, when writing to the leftmost column of a number, the display shows pixels. Next, I wanted to generate bit masks, for example, for decimal digits and, depending on the number, fill the column of display masks with the necessary numbers.
For the generation, another 8x8 design was created, in which units are entered by hands, and the formula collapses all this into one number:

= SUMPRODUCT (<row of cells with ones and zeros>; 2 ^ <row with position numbers>)

As a result, I got such a matrix of bit masks for numbers:
Next, apply the INDEX function, if you specify a matrix, row and column, it returns the value from this matrix. So, in each cell of the display bitmask, we write the formula

INDEX (<matrix>; <digit> + 1; <display line number> +1)

units are added because INDEX calculates coordinates from one, not from zero.

Circular links

Well, the display is ready, you write a number with your hands - it is displayed. Next, I wanted to make the number switch itself, that is, a certain counter that would accumulate the amount. Here I had to remember about cyclic links in formulas. By default, they are turned off, go to options, enable cyclic links, I configured it myself like this:
A cyclic link implies a formula in a cell, depending on it itself, for example, in cell A1 we write the formula "= A1 + 1". Such a cell, of course, cannot be calculated - when the number of valid iterations ends, Calc either produces #VALUE or error 523. Unfortunately, Calc could not be deceived, the idea was to make one cell constantly grow to a certain limit For example, in A1 I would write something like: = IF (A1 <500; A1 + 1; 0), and in B1, for example, this: = IF (A1 = 500; B1 + 1; B1). 500 is just a magic number that should have provided a delay, that is, as long as the amount accumulates in A1, it would take some time, and then B1 would change. (Well, here it would be necessary to take care of the initial initialization of the cells.) However, my plan did not work: Calc implements some tricky caching and verification algorithms (I even looked a bit at the source, but didn’t tackle it in detail), that it was impossible to loop the calculation of the formula, no matter how tricky dependencies were. By the way, in Excel 2003 this trick seems to have partially worked, and, in general, there seems to be a different model for calculating formulas, but I decided to experiment in Calc. After that, I decided to make a counter on macros, and already hang all my dependencies on it. One comrade told me, in general, to make only a sync pulse (clock signal) on macros, and already add counters and everything that is needed on it. I liked the idea - the macro turned out to be trivial: a delay and a change of state to the opposite. The counter itself consists of 4 cells: that looping the calculation of the formula does not work, no matter how tricky dependencies are. By the way, in Excel 2003 this trick seems to have partially worked, and, in general, there seems to be a different model for calculating formulas, but I decided to experiment in Calc. After that, I decided to make a counter on macros, and already hang all my dependencies on it. One comrade told me, in general, to make only a sync pulse (clock signal) on macros, and already add counters and everything that is needed on it. I liked the idea - the macro turned out to be trivial: a delay and a change of state to the opposite. The counter itself consists of 4 cells: that looping the calculation of the formula does not work, no matter how tricky dependencies are. By the way, in Excel 2003 this trick seems to have partially worked, and, in general, there seems to be a different model for calculating formulas, but I decided to experiment in Calc. After that, I decided to make a counter on macros, and already hang all my dependencies on it. One comrade told me, in general, to make only a sync pulse (clock signal) on macros, and already add counters and everything that is needed on it. I liked the idea - the macro turned out to be trivial: a delay and a change of state to the opposite. The counter itself consists of 4 cells: After that, I decided to make a counter on macros, and already hang all my dependencies on it. One comrade told me, in general, to make only a sync pulse (clock signal) on macros, and already add counters and everything that is needed on it. I liked the idea - the macro turned out to be trivial: a delay and a change of state to the opposite. The counter itself consists of 4 cells: After that, I decided to make a counter on macros, and already hang all my dependencies on it. One comrade told me, in general, to make only a sync pulse (clock signal) on macros, and already add counters and everything that is needed on it. I liked the idea - the macro turned out to be trivial: a delay and a change of state to the opposite. The counter itself consists of 4 cells:
A reset is already provided for initializing the initial values ​​by entering 1 in A1.
Such a counter is connected to the display from the previous section, and it turns out what is visible in this video:

It is a pity that it did not work out completely without macros and the clock generator did not work out on the formulas. In addition, another problem arose: when the macro is looped - it blocks the main thread, and nothing can be done already, you have to quit Calc. But my thoughts about interactivity were already ripening, I wanted to somehow control my future scheme, for example, reset everything to zero, or change some modes during operation.

Non-blocking timer

Fortunately, it turned out that in Calc you can make sure that the main macro stream is not blocked. Here I played a trick and just “google” the ready-made solution, adapting it for myself. This solution required a Bean Shell for LibreOffice. The package is called libreoffice-script-provider-bsh. The code consists of 2 parts: one on BeanShell, the other on LibreOffice Basic. Honestly, I didn’t fully understand the code ... I repent (I don’t speak Java, BeanShell, and I am not particularly familiar with the LibreOffice object model), but I corrected something.



So, I added a button component to the sheet, called it “Start / Stop” and hung the clock function on it. Now, when the button was pressed, the cell changed its value to 0 or 1 with the specified interval, and the application flow was no longer blocked. It was possible to continue experiments: to hang up some formulas on a sync signal and to "pervert" in every possible way.

Then I began to think of something to do. There is a screen, logic, sort of like, any can be implemented, there is a clock. But what if you make a creeping line, or, in general, Tetris? Well, it turns out, practically digital circuitry! Then I recalled an entertaining game in digital circuitry: kohctpyktop, there one of the tasks was to make an adder and memory with address access. If it was possible to do there, then it is possible here, I thought. And since there is a screen, then you need to make a game. And where there is one game, there is another, so it is necessary to make it possible to make different games ... Something like that, somehow, the idea came to my mind to make a processor so that it would be possible to enter commands into the cells, and he would read them, change his state and displayed what I needed.

There were a lot of thoughts, trial and error, there were thoughts of making an emulator of a finished processor, for example, Z80 and other equally crazy thoughts ... In the end, I decided to try to make memory, a stack, registers and a couple of commands like mov, jmp, mathematical add commands , mul, sub, etc. it was decided not to do it, because Calc formulas already know how to do this and even more, so I decided to use the formulas of the table processor directly in my “assembler”.

Memory

Memory is such a black box, which can be input to the address, value, and signal for recording. If the signal for recording is set, then the value is stored at the given address inside the black box; if the signal is not set, then the value stored earlier at this address appears at the output of the black box. You also need a separate input to clear the contents. Here is a definition of memory that I came up with for myself. So, we have cells for storing the value, and there are “interfaces”: inputs and outputs:

m_address - address
m_value_in - value for writing
m_set - write signal
m_value_out - read value, output signal
m_clear - signal to clear

For convenience, it's time to take advantage of the ability to name cells in Calc. Let's get to the cell, Insert / Names / Define ... This will give usable names for the cells and use these names in the formulas. So, I gave the names to the 5 cells that are described above. Then I selected a 10x10 square area - these are the cells that will store the values. Numbered rows and columns around the edges - to use the numbers of columns and rows in formulas. Now each cell that stores the value is filled with the same formula:
= IF (m_clear = 1; 0; IF (AND (m_address = ([cell_with row number] * 10) + [cell_with column number]; m_set = 1); m_value; [current cell])) ,
the logic here is simple: first, the cleaning signal is checked, if it is set, then the cell is zeroed, otherwise we look to see if the address matches (the cells are addressed with the number 0..99, the columns and rows are numbered from 0 to 9) and whether the signal is set for recording if yes, then we take the value for the record, if not, then we save our current value. We stretch the formula across all memory cells, and now we can enter any values ​​into the memory. Enter the following formula in the m_value_out cell: = INDIRECT (ADDRESS (ROW ([first_memory_cell]) + m_address / 10; COLUMN ([first_memory_cell]) + MOD (m_address; 10); 1; 0); 0), the INDIRECT function returns the value by the link specified in the line, and the ADDRESS function just returns the line with the link, the arguments are a series and a column of the sheet, and the type of link. I designed it this way:
Here, the yellow signals indicate the input signals into which values ​​can be written, there are no formulas in them, and what is forbidden to touch is highlighted in red, the green field is the output value, it contains the formula and can be referenced in other formulas.

Stack

The memory is ready, now I decided to implement the stack. The stack is such a black box, to which you can supply a value, a write signal and a read signal to the input. If a write signal is given, the stack saves the value inside it, next to the previously saved ones; if a read signal is given, the output stack issues the last stored value and deletes it inside itself so that the previous stored value becomes the last value . We had to tinker here, because, unlike memory, the stack has an internal structure: a pointer to the top of the stack, which should correctly change its state. So, for the interface part, I got the following cells:

s_address - the address where the storage cells start from, for example, "Z2"
s_pushvalue - value to be written to the stack
s_push - write signal
s_pop - signal to retrieve from the stack
s_popvalue - output signal - value retrieved from the stack
s_reset - reset signal

For internal structures, I got the following cells:

sp_address - cell address where the stack pointer shows 
sp_row - row sp_address
sp_column - sp_address column
sp - stack pointer, a number, for example 20 means that 20 values ​​are already stored on the stack and the next will be the 21st
oldsp - old stack pointer, needed for sp to work correctly

Well, there remains a long row of cells in which the values ​​will be stored. Let's start with the formula for extracting the value s_popvalue = IF (s_pop = 1; INDIRECT (sp_address; 0); s_popvalue), then everything is simple, if the signal for extraction is given, then we simply take the value of the cell to the address where the stack pointer shows, otherwise we save the old value. Formulas for internal structures:

cell	formula
sp_address	= ADDRESS (sp_row; sp_column; 1; 0)
sp_row	= ROW (INDIRECT (s_address))
sp_column	= COLUMN (INDIRECT (s_address)) + sp
oldsp	= IF (AND (s_push = 0; s_pop = 0); sp; oldsp)

It is easy to notice here that to form the address where the stack shows, we take the address of the beginning of the stack and add the stack pointer to it. The old value of the stack pointer is updated when both the write and eject signals are zero. So far, everything is simple. The formula for sp is quite complicated, so I'll give it indentation, for a better understanding:

5 nested IFs look monster-like, later on I divided such long formulas into several cells so that in each cell there were no more than 2 IFs.

It remains to give the formula for cells storing the value:

 = IF (s_reset = 1; 0; IF (AND (s_push = 1; ROW ([current_cell])) = sp_row; SUM (COLUMN ([current_cell]); 1) = sp_column; oldsp <> sp); s_pushvalue; [current_cell ]))

here, in principle, you can "parse" without indentation, the point is that a certain condition is checked, and if this condition is met, s_pushvalue is entered in the cell. The condition is as follows: the s_push signal must be cocked; the row of the cell must coincide with the row where sp points; the column where sp shows should be 1 more than the column of our cell; Well, sp should not equal its old value to oldsp.

Picture for clarity, what I got:

CPU

Well, there is memory, there is a stack. I made the screen bigger than 8x8, because originally thought about Tetris, I did 10x20, like on a BrickGame from the 90s. I used the first 20 cells of my memory as video memory, that is, I connected them to 20 lines of the screen (therefore they are dark red in the picture), now I can draw something on the screen by storing the values ​​I need at the right address . It remains to implement the main thing: that which will use the memory, the stack, read commands and execute them.

So, my central processor consists of the following parts:

In short, how it works: the inputs are connected to a clock and reset (which I hung up on the button for convenience, a pure formality), the entry point is manually configured. The outputs are connected to the memory and the stack, depending on the commands, the necessary signals will appear on them. The command and operands are populated, depending on where the ip instruction pointer points to. Registers change their meaning depending on the instructions and operands. ip can also change its value, depending on the command, but by default it simply increases by 1 at each step, and everything starts from the entry point that the person indicates. T.O. the program can be located in any place of the sheet, the main thing is to specify the address of the first cell in c_main.
As operands and commands, a program can specify a formula, the main thing is that in the cell the result is a value, it is the values ​​that will be sent to the processor for processing.
Let's start with simple internal structures: cur_col = COLUMN (INDIRECT (ip)) and cur_row = ROW (INDIRECT (ip)) is just the current row and current column. command = IFERROR (INDIRECT (ADDRESS (ROW (INDIRECT (ip)); COLUMN (INDIRECT (ip)); 1; 0); 0); null) the difference between theory and practice is already visible here. Firstly, I had to insert an error check. Secondly, in the formula I had to abandon the previous values ​​of cur_col and cur_row - this led to some tricky cyclic dependencies and did not allow ip to work correctly, however, we will talk about ip below. Thirdly, here I applied a special null value (in case of an error), a separate cell with "-1" is allocated for it.

The values ​​of the operands are formed from the current row and column with an offset:

opA = IFERROR (INDIRECT (ADDRESS (cur_row; cur_col + 1; 1; 0); 0); null)
opB = IFERROR (INDIRECT (ADDRESS (cur_row; cur_col + 2; 1; 0); 0); null)

Formulas for registers also check which command is current, but more commands are already taken into account, so the IF nesting level is completely unreadable. Here I will give an example of how I spread the long formulas into several cells:

The only thing left is the processor output signals:

push_value	= IFERROR (IF (command = "push"; opA; push_value); null)
push_c	= IF (command = "push"; c_clock; 0)
pop_c	= IF (AND (command = "pop"; c_clock = 1); 1; 0)
mem_addr	= IF (c_reset = 1; 0; IF (OR (command = "movm"; command = "mmov"); opA; mem_addr))
mem_value	= IF (c_reset = 1; 0; IF (command = "movm"; opB; IF (command = "mmov"; m_value_out; mem_value)))
mem_set	= IF (c_reset = 1; 0; IF (command = "movm"; 1; 0))

These are signals for working with memory and the stack. At first glance, the push_c and pop_c signals seem to be the same in essence, but the formulas in them are slightly different. I can only answer that they were obtained by the method of numerous trial and error. In the process of debugging this entire design, there were many bugs, and they still remained, unfortunately the processor does not always work “like a clock”. For some reason, I settled on just such an option, which means that “in a different way” something did not work. Now I can’t remember exactly what exactly.

Picture of my processor:

Here you can see debug fields - not values ​​are displayed in them, but formulas in the form of text.

Programming

So, the computer is ready, you can start writing a program. During the programming process, several problems were discovered, some of which were resolved, some still remained:

1. Sometimes the "computer" is buggy and behaves unpredictably
2. It is necessary that almost everything be visible on the sheet, including the program, otherwise cells that are far beyond the limits of visibility do not update their contents
3. The "computer" turned out to be slow, reducing the delay between ticks leads to the fact that the display and some formulas do not have time to update. Empirically, I chose, more or less, the optimal delay for my laptop: 150-200 ms

Since each line of the “program” is executed in one “tick”, the lines should be as small as possible, if possible, try to cram as much as possible into one formula. The main problem turned out to be that the code for Tetris turns out to be too large and may not fit on the sheet at all, so it was decided (after I was tormented with Tetris) to write “Snake” and try to use the minimum number of lines for this.

Input interface i.e. control buttons, had to be done on macros: 4 buttons with arrows and 4 cells in which 1 is placed, if the button is pressed, which I called key_up, key_down, key_left and key_right. The trigger key_trigger = IF (key_up; "U"; IF (key_down; "D"; IF (key_left; "L"; IF (key_right; "R"; key_trigger)))), in which the last pressed key.

I also made the Debug button, for debugging the program, using it you can use your hands to control the clock generator and watch how the states of the cells change (it puts 1 or 0 in the clock cell alternately). This is all the macros are responsible for: the clock and controls. There will be no more macros.

He began the development of "Snake" with pseudocode:

Next, it was necessary to detail this algorithm. Let's start with the initialization:

Then the main cycle begins. At first, I just took my pseudo-code and began to detail each line of it, taking into account the Calc formulas and the architecture of my processor. This all looked terrible:

The next step was only to replace the assignments with the mov, movm and mmov commands, respectively, and transfer the code to the cells on the sheet.

Of the interesting features, it is worth noting the random number generator. The table processor function does not suit us, because at each generation of the ball coordinates in the program, you need to have new random values. And the function is calculated only once and then lies in the cell until you refresh the sheet. Therefore, the so-called linear congruent method .

To simplify, checks that the ball appeared in the middle of the snake is not done. Also, no checks are made on the passage of a snake through itself.

The program works very “sloppy”. I recorded live video and accelerated 16 times. At the end of the video, I go through myself and hit the wall (in the bx register, “FAIL” appears and the snake does not creep anywhere else).

16 times faster video:




In the video you can see that at the bottom of the sheet there is a code of another small program - the conclusion of a traveling creeping line. Some hack was applied there, namely: the program uses data from neighboring cells, but, in the end, why not? After all, no one forbade this.

Video accelerated by 16 times:


The project is available on the github ; LIbreOffice Calc with BeanShell installed is required to work.