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

In this long article I want to share my experiments in reactive programming with the help of tabular 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 (except for the clock generator), which can be programmed in a certain assembly language. Then, as an example and proof-of-concept, I wrote the game "Snake" and the 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 in the robotics club; and here in the wikipedia article on the reactive paradigm 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 formulas in Excel knows that by changing one cell, we change the cells associated with it — it turns out to be rather similar to the propagation of a signal in a circuit. All these factors led me to the following thoughts: what if this “chain” would be quite complicated? Are formulas in the Turing tabular processor complete ? Is it possible to “program” formulas so that to get some non-trivial results? (for example make tetris) the last time I use Ubuntu at work and at home, I conducted all the experiments in LibreOffice Calc 4.2.7.2
')

8x8 digital display

I started the experiments with the implementation of the display. The display is a set of 8x8 square cells. Here conditional formatting came in handy (it is in both Excel and Calc). Select the cells, go to Format / Conditional Formatting / Condition ... and customize the appearance: a black background, provided that the cell contains, for example, a space. Now if you write a space in the cell, it becomes black. Thus, the pixels of our display are realized. But this display you want to somehow manage. To my left, I selected a special column in which the numbers will be entered - the idea is that with this number we set the 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 have to write a formula that will result in either a space or an empty string, depending on whether the required bit is set in the leftmost column.

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

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

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

As a result, I received such a matrix of bit masks for numbers:
Next, we apply the INDEX function, if we specify the matrix, row and column to it, then 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 counts the coordinates from one, not from zero.

Cyclical links

Well, the display is ready, you write a number with your hands - it is displayed. Next, I wanted to make the figure switch itself, that is, a counter that would accumulate the amount. Here we had to remember about cyclic references in formulas. By default, they are turned off, we go into the options, we enable circular links, I have set up myself like this:
A cyclic reference implies a formula in a cell that depends 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 permissible iterations ends, Calc gives out either #VALUE or error 523. Unfortunately, Calc did not succeed in deceiving, the idea was to make one cell constantly growing to some limit. For example, in A1 I would write something like: = IF (A1 <500; A1 + 1; 0), and in B1, for example, like this: = IF (A1 = 500; B1 + 1; B1). 500 is simply a magic number that should provide a delay, that is, as long as the amount accumulates in A1, it would take some time and then B1 would change. (Well, I would have to take care of the initial initialization of the cells.) However, my plan did not work: Calc implemented some clever caching and verification algorithms (I even looked at the source code a little, but didn’t pick at all) to loop the calculation of the formula It does not work, no matter how clever dependencies are. By the way, in Excel 2003, this trick seemed to work partially, and, in general, there seems to be another model for calculating formulas, but I still 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, in general, prompted me to make only a sync pulse (clock signal) on the macros, and I’m already hung on it with the counters and everything needed. I liked the idea - the macro was trivial: a delay and a change of state to the opposite. The counter itself consists of 4 cells:
There is already a reset for initialization of the initial values, by entering 1 into A1.
This counter is connected to the display from the previous section, and it turns out what is seen in this video:

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

Non-blocking timer

To my luck, it turned out that in Calc you can make it so that the main thread of the macro is not blocked. Here I was a little goof and just “googled” the ready 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 understand the whole code ... I repent (I don’t own Java, BeanShell, and the LibreOffice object model is not particularly familiar), but I did correct something.



So, on the sheet, I added a component button, 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 at a specified interval, and the application flow was no longer blocked. It was possible to continue the experiments: hang some formulas on the sync signal and in every possible way “pervert”.

Then I began to think of something to do this. There is a screen, logic, sort of like, any can be implemented, there is a clock pulse. And what if you make a running line, or, in general, "Tetris"? Well this is what I get, practically, digital circuitry! Then I remembered an interesting game on digital circuitry: kohctpyktop , there one of the tasks was to make an adder and memory with address access. If there it was possible to do it, then it is possible here too - I thought. And if there is a screen, then you have to make a game. And where there is one game, there is another, then it is necessary to make it possible to make different games ... Approximately, somehow, it occurred to my idea to make a processor so that I could enter commands into cells, and he would read them, change his state and displayed what I needed.

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

Memory

Memory is such a black box to which you can send an address, a value, and a write signal to the input. If the recording signal is set, the value is saved at this 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. Still need a separate entrance to clear the contents. This is the definition of memory I thought up for implementation. So, we have cells for storing values, and there are “interfaces”: inputs and output:

 m_address - address
 m_value_in - value to write
 m_set - write signal
 m_value_out - reading value, output signal
 m_clear - signal to clear

To make it more convenient, it's time to take the opportunity to call cells in Calc. Let's get to the cell, Insert / Names / Define ... This will give us clear names for the cells and use these names in the formulas already. So, I gave the names of 5 cells, as described above. Then I selected a square area of ​​10x10 - these are the cells that will store the values. Along the edges numbered rows and columns - to use the numbers of columns and rows in the formulas. Now each cell storing a value is filled with the same formula:
= IF (m_clear = 1; 0; IF (AND (m_address = ([cell_with_number_codes] * 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 check whether the address matches (the cells are addressed with the number 0..99, the columns and rows are numbered from 0 to 9) and the signal is set to write if yes, then we take the value to write, if not, then we save our current value. We stretch the formula for all memory cells, and now we can add any values ​​to memory. In the cell m_value_out, enter the following formula: = INDIRECT (ADDRESS (ROW ([first_cell_space]) + m_address / 10; COLUMN ([first_cell_space_setting]) + MOD (m_address; 10); 1; 0); 0), the function INDIRECT returns the value the link specified in the string, and the ADDRESS function just returns a string with a link, the arguments are a row and a column of a sheet, and a type of link. I designed it this way:
Here the yellow color indicates the input signals to which values ​​can be written, there are no formulas in them, and what cannot be touched in red, the green field is the output value, it contains the formula and can be referenced in other formulas.

Stek

The memory is ready, now I decided to implement the stack. A 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 keeps the value inside, next to the previously saved ones, if the read signal is given, the output stack gives the last stored value, and deletes it inside, so that the previous saved value becomes . We have already had to tinker here, because, unlike memory, the stack has an internal structure: a pointer to the top of the stack, which must correctly change its state. So, for the interface part, I got the following cells:

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

For internal structures, I started the following cells:

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

Well, there remained a long row of cells in which values ​​will be stored. Let's start with the formula for extracting the value of s_popvalue = IF (s_pop = 1; INDIRECT (sp_address; 0); s_popvalue), everything is simple, if the signal for extraction is given, simply take the value of the cell to the address where the stack pointer is displayed, otherwise save the old one 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 in order to form the address to which 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 in the case when both signals, both on the record and on the extract, are zero. So far, everything is simple. The formula for sp is quite complex, so I will give it with indents, for a better understanding:

5 nested IFs look monstrous, later on I would divide such long formulas into several cells so that each cell would have no more than 2 IFs.

It remains to give the formula for the cells that store 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 indents, the essence is that some condition is checked and in the case when this condition is fulfilled, s_pushvalue is entered into the cell. The condition is as follows: the s_push signal must be cocked; cell row must match the row where sp points to; the column where sp is shown should be 1 greater than the column of our cell; well, sp should not be equal to its old value oldsp.

Picture for clarity, that I got:

CPU

Well, there is memory, there is a stack. I made the screen more than 8x8, because originally thought about Tetris, I did 10x20, as on 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 (so they are dark red in the picture), now I can draw something on the screen by storing the values ​​I need . It remains to implement the main thing: that will use the memory stack, read commands and execute them.

So, my CPU consists of the following parts:

In short, how everything works: the inputs are connected to the clock generator and reset (which I hung on the button for convenience, pure formality), the entry point is manually configured. Outputs are connected to the memory and stack, and 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 value, depending on the commands, 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 specifies. So the program can be located in an arbitrary place on the sheet, the main thing is to specify the address of the first cell in c_main.
As operands and instructions, you can specify a formula in the program, the main thing is that in the cell, as a result, a value is obtained, namely, the values ​​will be processed by the processor.
Let's start with simple internal structures: cur_col = COLUMN (INDIRECT (ip)) and cur_row = ROW (INDIRECT (ip)) are just the current row and the current column. command = IFERROR (INDIRECT (ADDRESS (ROW (INDIRECT (ip)); COLUMN (INDIRECT (ip)); 1; 0); 0); null) here you can see the difference between theory and practice. First, I had to insert error checking. Secondly, in the formula it was necessary 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, but we are talking about ip below. Thirdly, here I have applied the special value null (in case of an error), a separate cell with "-1" is selected for it.

The values ​​of the operands are formed from the current row and column with 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 team is current, but more teams are already taken into account, so the IF nesting level is completely unreadable. Here I will give an example of how I distributed long formulas in several cells:

— :

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 stack. At first glance, the signals push_c and pop_c seem to be the same in essence, but the formulas in them are slightly different. I can only answer, that they are obtained by numerous trial and error. In the process of debugging all this design there were a lot of bugs, and they still remained, unfortunately the processor does not always work "like a clock." For some reason, I stopped at this option, it means “differently” something did not work. Now I can’t remember exactly what it is.

Picture of my processor:

Here you can also see the 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 the program. During the programming process, several problems were discovered, some of which were solved, some still remained:

1. «»
2. , , ,
3. «» , , . , , : 150-200

«» «», , . , «» , ( , «») «» .

, .. , : 4 4 1, , key_up, key_down, key_left key_right. key_trigger=IF(key_up; «U»; IF(key_down; «D»; IF(key_left; «L»; IF(key_right; «R»; key_trigger)))), .

«Debug», , ( 1 0 clock). : . .

«» :

. :

. Calc . :

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 worth noting random number generator. The function of the tabular processor does not suit us, because at each generation of the ball coordinates in the program, we need to have new random values. A function is calculated only once and then lies in the cell until you refresh the sheet. Therefore, a so-called pr. linear congruential 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 the snake through itself.

The program works very "sloopochno." I recorded the video in real time and accelerated 16 times. At the end of the video, I pass through myself and crash into a wall (FAIL appears in the bx register and the snake no longer crawls anywhere).

16 times faster video:




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

Video accelerated 16 times:


The project is available on a githab ; LIbreOffice Calc with BeanShell is required.