Реактивне програмування в табличному процесорі



Табличний процесор (мова йде про MS Excel або LibreOffice Calc) — це досить цікавий і універсальний інструмент. Мені часто доводилося (і доводиться) користуватися його широкими можливостями: автоматизовані звіти, перевірка гіпотез, прототипування алгоритмів. Наприклад, я використовував його для вирішення завдань проекту Ейлера, швидкої перевірки алгоритмів, реалізував парсер одного прикладного протоколу (по роботі треба було). Мені подобається наочність, яку можна досягти в табличному процесорі, а ще мені подобається нестандартне застосування всього, чого тільки можливо :) На Хабре вже з'являлися цікаві статті на тему нестандартного застосування Excel:
habrahabr.ru/post/246975/
habrahabr.ru/post/237641/
habrahabr.ru/post/174373/
У цій довгій статті я хочу поділитися своїми експериментами в реактивному програмуванні з допомогою формул табличного процесора. В результаті цих експериментів у мене вийшов комп'ютер з процесором, пам'яттю, стеком і дисплеєм, реалізований всередині LibreOffice Calc за допомогою одних тільки формул (за винятком тактового генератора), який можна програмувати на якомусь подібному асемблера. Потім, в якості прикладу та proof-of-concept, я написав гру «Змійка» і біжучийповзе рядок для цього комп'ютера.

Передмова
Почалося все з того, що я зацікавився різними парадигмами програмування, відвідав вступне заняття Verilog в клубі робототехніки; і ось у статті на вікіпедії реактивної парадигмі я натрапив на такий текст:
Сучасні табличні процесори являють собою приклад реактивного програмування. Комірки таблиці можуть містити рядкові значення або формулу виду «=B1+C1», значення якої буде обчислено виходячи з значень відповідних комірок. Коли значення одного із залежних клітинок буде змінено, значення цієї комірки буде автоматично оновлено.
Дійсно, будь-хто користувався формул в Excel знає, що змінивши одну клітинку ми змінюємо пов'язані з нею осередку — виходить досить схоже на поширення сигналу в ланцюзі. Всі ці фактори і навели мене на такі думки: а що якщо ця «ланцюг» буде досить складною? є формули в табличному процесорі Тьюринг повними? можна «запрограмувати» формули, щоб отримати якісь нетривіальні результати? (наприклад зробити тетріс) Т. к. останнім часом я використовую Ubuntu на роботі і вдома, то всі експерименти я проводив у LibreOffice Calc 4.2.7.2

Цифровий дисплей 8x8
Почав експерименти я з реалізації дисплея. Дисплей представляє з себе набір квадратних чарунок 8х8. Тут в нагоді умовне форматування воно є і в Excel і в Calc). Виділяємо комірки, заходимо в Format/Conditional Formatting/Condition… і налаштовуємо зовнішній вигляд: чорний фон, за умови, що в комірці міститься, наприклад, пробіл. Тепер якщо записати в комірку пробіл, то вона стає чорною. Таким чином реалізуються пікселі нашого дисплея. Але цим дисплеєм хочеться якось керувати. Зліва від нього я виділив спеціальний стовпець в який будуть заноситися числа — ідея така, щоб цим числом ми ставили бітову маску для відображення на екрані. Зверху екрану я пронумерував стовпці. Тепер у кожну клітинку дисплея ми повинні написати формулу, яка дасть в результаті або пробіл, або порожній рядок, в залежності від того, встановлено чи потрібний біт в самому лівому стовпці.

=IF(MOD(TRUNC(<бітова маска>/(2^<номер стовпця дисплея>));2);" ";"")

Тут, по суті, відбувається зсув вправо (ділення на степінь двійки і потім відкидання дробової частини), а потім береться 0-й біт, тобто остачу від ділення на 2, і якщо він встановлений, то повертається пробіл, інакше порожній рядок.
Тепер при записі в самий лівий стовпець якогось числа на дисплеї відображаються пікселі. Далі мені хотілося згенерувати бітових масок, наприклад, для десяткових цифр і, в залежності від цифри, заповнювати стовпець масок дисплея потрібними числами.
Для генерації була створена ще одна конструкція 8х8, в яку руками заносяться одиниці, а формула згортає все це в одне число:
=SUMPRODUCT(<рядок комірок з одиницями і нуликами>;2^<рядок з номерами позицій>)

В результаті отримав таку матрицю бітових масок для цифр: Sign-generator0 0 24 36 36 36 36 24 0
1 0 8 24 40 8 8 8 0
2 0 24 36 4 8 16 0 60
3 0 24 36 8 4 36 24 0
4 0 12 20 36 60 4 4 0
5 0 60 32 56 4 4 56 0
6 0 24 28 32 36 36 24 0
7 0 60 4 8 16 16 16 0
8 0 24 36 24 36 36 24 0
9 0 24 36 36 28 24 4 0

Тут кожний рядок відповідає десятковій цифрі. Можливо, не найкрасивіші цифри вийшли, до того ж, верхній і нижній ряд не використаний, ну вже як намалював, так намалював )

Далі застосуємо функцію INDEX, якщо їй вказати матрицю, ряд і колонку, то вона повертає значення з цієї матриці. Так що, в кожній клітинці бітової маски дисплея пишемо формулу
INDEX(<матриця>; <цифра> + 1; <номер рядка дисплея>+1)

одиниці додаються тому, що INDEX вважає координати з одиниці, а не з нуля.

Циклічні посилання
Що ж, дисплей готовий, пишеш руками цифру — вона відображається. Далі мені захотілося зробити так, щоб цифра сама переключалася, тобто якийсь лічильник, який буде накопичувати суму. Тут то і довелося згадати про циклічні посилання у формулах. За замовчуванням, вони вимкнені, заходимо в опції, дозволяємо циклічні посилання, я у себе налаштував ось так: Опції обчислень

Циклічне посилання має на увазі під собою формулу у клітинці, що залежить від неї самої ж, наприклад, у клітинку A1 ми запишемо формулу "=A1+1". Така комірка, звичайно, не може бути обчислена — коли закінчується число допустимих ітерацій, то Calc видає або #VALUE, або помилку 523. На жаль, обдурити Сalc не вдалося, ідея була така, щоб зробити одну клітинку постійно зростаючою до якоїсь межі, наприклад, A1 я б записав щось на кшталт: =IF(A1<500; A1+1; 0), а в B1, наприклад, таке: =IF(A1=500;B1+1;B1). 500 — це просто магічне число, яке повинно було забезпечити затримку, тобто, поки в А1 накопичується сума, це б зайняло якийсь час, а потім би помінявся B1. (Ну тут треба було б ще подбати про початкової ініціалізації осередків.) Однак, мій план не спрацював: в Calc реалізовані якісь хитрі алгоритми кешування і перевірки (я навіть трошки заглядав у вихідні, але детально не копирсався), що зациклити обчислення формули не виходить, які б хитрі залежності не були. До речі в Excel 2003 цей трюк, здається, частково спрацьовував, і, взагалі, там схоже інша модель обчислення формул, але я все-таки вирішив експериментувати в Calc. Після цього я вирішив зробити лічильник на макросах, а на нього вже навішувати всі свої залежності. Один товариш мені, взагалі, підказав зробити на макросах тільки синхроімпульсів (сигнал clock), а на нього вже навішувати лічильники і все що потрібно. Ідея мені сподобалася — макрос виходив тривіальним: затримка і зміна стану на протилежне. Сам же лічильник складається з 4-х осередків: Лічильник від 0 до 9
A B
1 Reset 0
2 Clock [змінюється макросом 0 або 1]
3 Old value =IF(B1=1; 0; IF(B2 = 0; B4, B3))
4 New value =IF(B1 = 1; 0; IF(AND(B2 = 1; B4 = B3); IF(B4<9; SUM(B4;1); 0); B4))

Тут вже передбачено скидання для ініціалізації початкових значень, шляхом занесення 1 A1.
Такий лічильник підключається до дисплею з попереднього розділу, і виходить те, що видно на цьому відео:
Лічильник + дисплей 8х8
Шкода, що не вийшло повністю обійтися без макросів і тактовий генератор зробити на формулах не вийшло. Крім цього, виникла ще одна проблема: коли макрос зациклений — він блокує основний потік, і нічого вже зробити не можна, доводиться завершувати роботу Calc. Але у мене вже зріли думки про інтерактивності, хотілося якось управляти своєю майбутньою схемою, наприклад, скидати все в нуль, або міняти якісь режими під час роботи.

Неблокуючий таймер
На моє щастя, виявилося, що в Calc можна зробити так, щоб основний потік макросу не блокувався. Тут я трохи злукавив і просто «нагуглил» готове рішення, пристосувавши його під себе. Це рішення вимагало Bean Shell для LibreOffice. Пакет називається libreoffice-script-provider-bsh. Код складається з 2х частин: одна на BeanShell, інша на LibreOffice Basic. Чесно кажучи, повністю в коді я не розібрався… каюся (не володію Java, BeanShell, так і з об'єктною моделлю LibreOffice не особливо знайомий), але дещо все-таки підправив.
BeanShell частинаimport com.sun.star.uno.Type;
import com.sun.star.uno.UnoRuntime;
import com.sun.star.lib.uno.helper.PropertySet;
import com.sun.star.lib.uno.helper.WeakBase;
import com.sun.star.task.XJobExecutor;
import com.sun.star.lang.XInitialization;
import com.sun.star.beans.PropertyValue;
import com.sun.star.beans.XPropertyChangeListener;
import com.sun.star.beans.PropertyChangeEvent;
import com.sun.star.lang.EventObject;
import com.sun.star.uno.AnyConverter;
import com.sun.star.xml.crypto.sax.XElementStackKeeper; // defines a start and a stop routine

// This prevents an error message when executing the script a second time
xClassLoader = java.lang.ClassLoader.getSystemClassLoader();

try {
xClassLoader.loadClass("ms777Timer_01");
} catch (ClassNotFoundException e)
{
System.out.println( "class not found — compiling" );

public class ms777Timer_01 extends PropertySet implements XElementStackKeeper
{

// These are the properties of the PropertySet
public boolean bFixedRate = true;
public boolean bIsRunning = false;
public int lPeriodInMilliSec = 2000;
public int lDelayInMilliSec = 0;
public int lCurrentValue = 0;
public XJobExecutor xJob = null;

// These are some additional properties
Task xTask =null;
Timer xTimer = null;

public ms777Timer_01() {
registerProperty("bFixedRate", (short) 0);
registerProperty("bIsRunning", (short) com.sun.star.beans.PropertyAttribute.READONLY);
registerProperty("lPeriodInMilliSec", (short) 0);
registerProperty("lDelayInMilliSec", (short) 0);
registerProperty("lCurrentValue", (short) 0);
registerProperty("xJob", (short) com.sun.star.beans.PropertyAttribute.MAYBEVOID);
xTimer = new Timer();
}

//XElementStackKeeper
public void start() {
stop();
if (xJob==null) {return;}
xTask = new Task();
lCurrentValue = 1;
bIsRunning = true;
if (bFixedRate) {
xTimer.scheduleAtFixedRate( xTask, (long) lDelayInMilliSec, (long) lPeriodInMilliSec );
} else {
xTimer.schedule( xTask, (long) lDelayInMilliSec, (long) lPeriodInMilliSec );
}
}

public void stop() {
lCurrentValue = 0;
bIsRunning = false;
if (xTask!=null) { xTask.cancel();}
}

public void retrieve(com.sun.star.xml.sax.XDocumentHandler h, boolean b) { }

class Task extends TimerTask {
public void run() { // ця функція викликається по таймеру і смикає тригер, який ми передаємо або 0 або 1
xJob.trigger(lCurrentValue.toString());
if (lCurrentValue == 0)
lCurrentValue = 1;
else
lCurrentValue = 0;
}
}
}

System.out.println( "ms777PropertySet generated" );
} // of if (xClass = null)

Object TA = new ms777Timer_01();
return TA;


LibreOffice Basic частинаSub clock // цю функцію я повешал на кнопку, щоб запускати і зупиняти "тактовий генератор"
if isEmpty(oP) then // якщо запустили перший раз, то створюємо ці невідомі об'єкти в яких я не розібрався
oP = GenerateTimerPropertySet()
oJob1 = createUnoListener("JOB1_", "com.sun.star.task.XJobExecutor")
oP.xJob = oJob1
oP.lPeriodInMilliSec = 150 // тут задається затримка
endif

if state = 0 then // а тут зміна стану, 0 — означає синхроімпульсів зупинений і його треба запустити
oP.start()
state = 1
else // інакше означає що синхроімпульсів запущений і його треба зупинити
oP.stop()
state = 0
endif
End Sub

function GenerateTimerPropertySet() as Any // функція в якій дістається срипт на BeanShell
oSP = ThisComponent.getScriptProvider("")
oScript = oSP.getScript("vnd.sun.star.script:timer.timer.bsh?language=BeanShell&location=document")
GenerateTimerPropertySet = oScript.invoke(Array(), Array(), Array()
end function

sub JOB1_trigger(s as String) // це тригер який викликається по таймеру з BeanShell скрипта
SetCell(1, 2, s)
end sub

sub SetCell (x as Integer, y as Integer, val as Integer) // встановити значення у клітинці з координатами X, Y
ThisComponent.sheets.getByIndex(1).getCellByPosition(x, y).Value = val
end sub

Отже, на лист я додав компонент кнопку, назвав її «Старт/Стоп» і повешал на неї функцію clock. Тепер при натисканні кнопки, осередок змінювала своє значення 0 або 1 з заданим інтервалом, та потік програми більше не блокувався. Можна було продовжувати експерименти: вішати якісь формули на синхро-сигнал і всіляко «вивертатися».

Тут я почав думати, чого б такого зробити. Ось екран є, логіку, начебто, яку можна реалізувати, є синхроімпульсів. А що, якщо зробити біжучий рядок, або, взагалі, «Тетріс»? Це ж у мене виходить, практично, цифрова схемотехніка! Тут згадалася цікава гра по цифровій схемотехніці: kohctpyktop, там одне з завдань було зробити суматор і пам'ять з адресним доступом. Якщо там це можливо було зробити, значить і тут можна, — подумав я. А раз є екран, значить треба зробити гру. А там де одна гра, там і інша, значить треба зробити можливість робити різні ігри… Приблизно, як-то так, в мою голову прийшла ідея зробити процесор, щоб можна було в осередку заносити команди, а він би їх прочитував, міняв свій стан і виводив на екран те, що мені потрібно.

Роздумів було багато, проб і помилок теж, були думки зробити емулятор готового процесора, наприклад Z80 та інші не менш божевільні думки… зрештою я вирішив спробувати зробити пам'ять, стек, регістри і парочку команд типу mov, jmp, математичні команди типу add, mul, sub і т. д. було вирішено не робити, бо формули Calc вже і так це вміють і навіть більше, так що я вирішив використати у своєму «асемблері» безпосередньо формули табличного процесора.

Пам'ять
Пам'ять-це такий чорний ящик, якому на вхід можна подати адресу, значення, і сигнал на запис. Якщо сигнал на запис виставлений, то значення зберігається за цією адресою всередину чорного ящика, якщо сигнал не виставлений, то на виході " чорного ящика з'являється значення, збережене раніше за цією адресою. Ще потрібен окремий вхід для очищення вмісту. Ось таке визначення пам'яті я собі придумав для реалізації. Отже, у нас є осередки для зберігання значення, і є «інтерфейси»: входи і вихід:

m_address — адресу
m_value_in — значення для запису
m_set — сигнал "записати"
m_value_out — значення при читанні, вихідний сигнал
m_clear — сигнал на очищення

Щоб було зручніше, саме час скористатися можливістю іменувати клітинки в Calc. Стаємо на клітинку, Insert/Names/Define… Це дозволить дати зрозумілі імена клітинок і використовувати у формулах вже ці імена. Отже, я дав імена 5ти клітинок, що описані вище. Далі виділив квадратну область 10х10 — це ті клітинки, які будуть зберігати значення. По краях пронумерував рядки і стовпці — щоб використовувати номери стовпців і рядків у формулах. Тепер кожна комірка, що зберігає значення, заповнюється однаковою формулою:
=IF( m_clear = 1; 0; IF(AND(m_address = ([ячейка_с_номером_ряда] * 10) + [ячека_с_номером_колонки]; m_set = 1); m_value; [текущая_ячейка])),
логіка тут проста: спочатку перевіряється сигнал очищення, якщо він виставлений, то обнуляем клітинку, в іншому випадку дивимося збігається адреса (осередку адресуються числом 0..99, стовпці і рядки пронумеровані від 0 до 9) і виставлений сигнал на запис, якщо так, то беремо значення на запис, якщо ні, то зберігаємо своє поточне значення. Протягуємо формулу по всіх комірках пам'яті, і тепер ми можемо заносити в пам'ять будь-які значення. В комірку m_value_out заносимо наступну формулу: =INDIRECT(ADDRESS(ROW([первая_ячейка_памяти]) + m_address / 10; COLUMN([первая_ячейка_памяти]) + MOD(m_address; 10); 1;0);0), функція INDIRECT повертає значення за посиланням заданої в рядку, а функція ADDRESS як раз повертає рядок з посиланням, аргументи цей рядок і колонка листа, і тип посилання. Я оформив це таким чином:
Тут жовтим кольором позначені вхідні сигнали, які можна писати значення, в них формул немає, а червоним виділено те, що чіпати не можна, зелене поле — це вихідне значення, воно містить формулу, і на нього можна посилатися в інших формулах.

Стек
Пам'ять готова, тепер я надумав реалізувати стек. Стек — це такий чорний ящик, якому на вхід можна подати значення, сигнал на запис і сигнал на читання. Якщо поданий сигнал на запис, то стек зберігає значення у себе всередині, поруч із раніше збереженими, якщо поданий сигнал на читання, то стек на виході видає крайнє збережене у себе значення і видаляє його у себе всередині так, що крайнім значенням стає попереднє збережене. Тут вже довелося повозитися, тому що, на відміну від пам'яті, стек має внутрішню структуру: покажчик на вершину стека, який повинен правильно змінювати свій стан. Отже, для інтерфейсній частині я завів такі осередки:

s_address — адреса звідки починаються комірки для зберігання, наприклад "Z2"
s_pushvalue — значення, яке треба записати в стек
s_push — сигнал на запис
s_pop — сигнал на витяг з стека
s_popvalue — вихідний сигнал — значення, вилучене з стека
s_reset — сигнал скидання

Для внутрішніх структур я завів такі осередки:

sp_address — адреса клітинки куди показує покажчик стека
sp_row — ряд sp_address
sp_column — колонка sp_address
sp — покажчик стека, число, наприклад 20 означає що 20 значень вже збережено в стек і наступне буде 21-е
oldsp — старий покажчик стека, потрібен для коректної роботи sp

Ну і залишилася довга рядок комірок, в яких будуть зберігатися значення. Почнемо з формули для вилучення значення s_popvalue =IF(s_pop=1; INDIRECT(sp_address; 0); s_popvalue), тут все просто, якщо сигнал для вилучення поданий, то просто беремо значення комірки з адресою, куди показує покажчик стека, інакше зберігаємо старе значення. Формули для внутрішніх структур:
комірка формула
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)
Тут легко помітити, що для формування адреси, куди показує стек, ми беремо адресу початку стека і додаємо до нього покажчик стека. Старе значення покажчика стека оновлюється у разі коли обидва сигналу: і на запис і витяг — нульові. Поки все просто. Формула для sp ж досить складна, тому я наведу її з відступами, для кращого розуміння:
Покажчик стека sp=IF(s_reset = 1; // якщо сигнал скидання, то
0; // скинути вказівник 0
IF(AND(sp = oldsp; c_clock = 1); // інакше перевіряємо дорівнює чи стекпойнтер старим значенням і зведений чи синхросигнал (тобто треба оновити стекпойнтер)
SUM(sp; IF(s_push = 1; // якщо оновлення стекпойнтера потрібно, значить до старого значенням додаємо якесь зміщення (-1, 0 або 1)
1; // додаємо до стекпойнтеру 1, у разі якщо сигнал push
IF(s_pop=1; // в іншому випадку, якщо сигнал pop, то додаємо або 0 або -1
IF(sp > 0; -1; 0); // -1 додаємо у разі, коли sp > 0, інакше додаємо 0, тобто залишаємо старе значення
0))); // старе значення залишаємо у разі коли ні push ні pop не зведені
sp)) // якщо стекпойнтер не дорівнює старим значенням, або синхросигнал невзведен то зберігаємо старе значення

5 вкладених IF виглядають монстрообразно, надалі я такі довгі формули поділяв на кілька клітинок так, щоб у кожній клітинці було не більше 2-х IF'ів.

Залишилося привести формулу для комірок, зберігають значення: =IF (s_reset = 1; 0; IF (AND(s_push = 1; ROW([текущая_ячейка]) = sp_row; SUM(COLUMN([текущая_ячейка]); 1) = sp_column; oldsp <> sp); s_pushvalue; [текущая_ячейка])) тут в принципі можна «розпарсити» без відступів, суть така, що перевіряється деякий умова і у випадку, коли ця умова виконується — у клітинку заноситься s_pushvalue. Умова наступне: повинен бути зведений сигнал s_push; ряд комірки повинен збігатися з поруч, куди вказує sp; колонка, куди показує sp, повинна бути на 1 більше, ніж колонка нашого осередку; ну і sp не повинен рівнятися своїм старим значенням oldsp.

Картинка для наочності, що у мене вийшло:

Процесор
Ну ось, пам'ять є, стек є. Екран я зробив більше ніж 8х8, т. к. спочатку думав про тетріс, то зробив 10х20, як на BrickGame з 90х. Перші 20 осередків своїй пам'яті я використовував в якості відеопам'яті, тобто підключив їх до 20 рядків екрана (тому на картинці вони темно-червоного кольору), тепер я можу малювати на екрані щось, шляхом занесення в пам'ять за вказаною адресою потрібних мені значень. Залишилось реалізувати головне: те, що буде користуватися пам'яттю, стеком, зчитувати команди і виконувати їх.

Отже, центральний процесор у мене складається з наступних частин:
Структури CPUВходи:
c_reset — сигнал скидання (обнуляє стан процесора)
c_main — адреса початку програми, точка входу
c_clock — синхроімпульсів, подається ззовні
pop_value — значення зі стека, підключається до стеку =s_popvalue

Внутрішні структури:
command — команда на виконання
opA — перший операнд команди
opB — другий операнд команди
cur_col — поточний ряд (куди показує ip)
cur_row — поточна колонка
ip — instruction pointer, покажчик на команду
oldip — старий ip, потрібен для коректної роботи ip
ax — регістр загального призначення (РОН)
bx — РОН
cx — РОН
rax — копія ax, потрібна для того, щоб коректно модифікувати значення ax
rbx — копія bx
rcx — копія cx

Виходи:
mem_addr — адресу пам'яті, підключено до пам'яті
mem_value — значення для запису в пам'ять або зчитане з пам'яті
mem_set — сигнал для запису в пам'ять, підключений до пам'яті

pop_value — значення зі стека, або для запису в стек, підключено до стеку
push_c — сигнал запису в стек
pop_c — сигнал читання з стека


Коротко, як все працює: входи підключені до тактового генератора та скиду (який я повісив на кнопку для зручності, чиста формальність), точка входу налаштовується вручну. Виходи підключені до пам'яті і стека, на них, в залежності від команд, які будуть з'являтися потрібні сигнали. Команда і операнди заповнюються, в залежності від того, куди показує покажчик інструкцій ip. Регістри змінюють своє значення, в залежності від команд та операндів. ip теж може змінювати своє значення, залежно від команди, але за замовчуванням він просто збільшується на 1 на кожному кроці, а починається все з точки входу, яку зазначає чоловік. Т. о. програма може розташовуватися в довільному місці аркуша, головне — адресу першої клітинки вказати в c_main. Список команд підтримуваний процесором:mov — помістити значення в регістр, перший операнд ім'я регістра, другий — значення, наприклад mov ax 666
movm — помістити значення за адресою в пам'яті, перший операнд — адресу в пам'яті, другий операнд значення
jmp — перехід, один операнд — нове значення ip, другий операнд відсутній (але в комірці все-одно повинно щось бути! Магія Calc, яку я не розгадав...)
push — дістати значення зі стеку і покласти в регістр загального призначення, єдиний операнд — назва регістра (ax, bx або cx), магія з другим оператором така ж
pop — покласти значення в стек, операнд — значення
mmov — дістати значення з пам'яті і покласти в регістр, перший операнд — адресу пам'яті, другий операнд — назва регістра


В якості операндів і команд, в програмі можна вказувати формулу, головне — щоб в комірці в результаті вийшло значення, саме значення будуть потрапляти на обробку в процесор.
Почнемо з простих внутрішніх структур: cur_col=COLUMN(INDIRECT(ip)) і cur_row=ROW(INDIRECT(ip)) це просто поточний ряд і поточна колонка. command=IFERROR(INDIRECT(ADDRESS(ROW(INDIRECT(ip));COLUMN(INDIRECT(ip)); 1;0); 0); null) тут вже видно розходження теорії і практики. По-перше, довелося вставити перевірку на помилки. По-друге, у формулі довелося відмовитися від попередніх значень cur_col і cur_row — це призводило до якимось хитрим циклічним залежностями і не давало коректно працювати ip, втім мова про ip нижче. По-третє, тут я застосував спеціальне значення null (у разі помилки), для нього виділена окрема комірка з "-1".

Значення операндів формуються з поточного рядка і колонки зі зміщенням:
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)

Формула для instruction pointer:ip=IF(c_reset = 1; // перевірка на скидання
c_main; // якщо був скидання, то повертаємося на мейн
IF(AND(c_clock = 1;ip=oldip); // в іншому випадку перевіряємо треба оновлювати значення (зведений жмут і старе значення збігається з поточним)
IF(command="jmp"; // якщо значення міняти треба, то перевіряємо, чи є тче команда переходом
opA; // якщо поточна команда jmp, тоді беремо нове значення операнда
ADDRESS(ROW(INDIRECT(ip))+1; // якщо поточна команда jmp, тоді просто переходимо на наступний ряд
COLUMN(INDIRECT(ip))));
ip)) // якщо значення оновлювати не треба, то залишаємо старе
Фактично, ця довга формула у мене рознесена по декількох клітинок, але можна і все в одну записати.
opdip=IF(c_clock = 0; ip; oldip)

Формули для регістрів, також перевіряють яка команда є поточною, але враховується вже більше команд, тому рівень вкладеності IF зовсім нечитабельний. Тут я наведу приклад, як я розносив довгі формули з кількох клітинок:
Регістри загального призначенняАдреси комірок чисто умовні, для прикладу.

A B C D E
1 =IF(c_reset = 1; 0; B1) =IF (c_clock = 1; C1; ax) = IF(c_clock=1; IF (opA = «ax»; D1; IF(opB = «ax»; E1; ax));ax) =IF(AND(opA = «ax»;c_clock=1);IF (command = «pop»; pop_value; IF (command = «mov»; opB; ax)); ax) = IF(AND(opB=«ax»;command = «mmov»); mem_value; ax)
Тут A1 і є, власне, регістрі ax, а решта це допоміжні осередку.

Копія регістра rax=IF(c_reset= 1; 0; IF(AND(rax<>ax; c_clock=0); ax; rax))
Думаю тут зовсім не складно здогадатися, що відбувається. Інші регістри bx і cx влаштовані аналогічним чином.

Залишилася справа за малим — вихідні сигнали процесора:
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))
Це сигнали для роботи з пам'яттю і стеком. На перший погляд, сигнали push_c і pop_c, начебто, однакові по суті, але формули в них трошки різні. Можу лише відповісти, то, що вони отримані методом численних спроб і помилок. В процесі налагодження всієї цієї конструкції було багато помилок, і вони ще залишилися, на жаль процесор не завжди працює «як годинник». З якихось причин, я зупинився саме на такому варіанті, значить «по-іншому» щось не працювало. Зараз вже не зможу точно згадати що саме.

Картинка мого процесора:

Тут видно ще debug поля — в них виводяться не значення, а формули у вигляді тексту.

Програмування
Отже, комп'ютер готовий, можна приступати до написання програми. У процесі програмування виявилося кілька проблем, деякі з яких були вирішені, деякі все ж залишилися:
  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). Це все за що відповідають макроси: тактовий генератор і органи управління. Більше макросів не буде.

Почав розробку «Змійки» з псевдокода:
Псевдокод 'Блискавка'«Змійки» потрібні наступні сутності: координати голови; координати хвоста; масив, де зберігаються координати всіх точок змійки; координати м'ячика.

HEAD // ядрес комірки пам'яті з координатами голови
TAIL // ядрес комірки пам'яті з координатами хвоста
BXBY = rand // координати м'ячика
HXHY = *HEAD // координати голови
TXTY = *TAIL // координати хвоста

loop:
read DIRECTION // зчитуємо напрям (клавіші)
HEAD++ // збільшуємо покажчик голови на одиницю
HXHY += DIRECTION // векторно додаємо напрямок до координат голови
[HEAD] = HXHY // зберігаємо в пам'ять нові координати голови
BXBY <> HXHY? JMP cltail // якщо координати голови не збіглися з координатами м'ячика, то стрибаємо на "стирання хвоста"
BXBY = rand // генеруємо нові координати м'ячика
[BY] = OR([BY]; 9-2^BX) // малюємо м'ячик на екрані (перші 20 осередків пам'яті відображаються на екрані 10х20)
JMP svtail //перестрибуємо стирання хвоста
cltail:
[TY] = AND([TY]; XOR(FFFF; (9-2^TX))) // перемо хвіст з екрану
TAIL++ // збільшуємо покажчик хвоста
TXTY = [TAIL] // беремо нові координати хвоста з пам'яті
svtail:
[HY] = OR([HY]; 9-2^HX) // малюємо голову на екрані

JMP loop // переходимо на початок циклу

Ось такий нескладний алгоритм вийшов.
Зберігати дані я вирішив аггрегированном вигляді в регістрах, наприклад регістр ax зберігає BXBYHHTT, тобто фактично 4 двозначних змінних: координати м'ячика (BX і BY), номер комірки з координатами голови (HH), номер комірки з координатами хвоста (TT). Це ускладнює доступ до змінних, але дозволяє зменшити кількість рядків програми.

Далі потрібно було цей алгоритм деталізувати. Почнемо з ініціалізації:
Ініціалізація
Command Operand 1 Operand 2 Comment
mov ax =RANDBETWEEN(0;9) * 1000000 + RANDBETWEEN(0;19)* 10000 + 2120 BXBYHHTT
movm 21 509 Head: x — 5 y — 9
movm 20 409 Tail: x — 4; y — 9
mov cx R direction init
mov bx 5090409 HXHYTXTY
movm =MOD(ROUNDDOWN(rax/10000);100) =2^(9-ROUNDDOWN(rax/1000000)) draw ball

Далі починається основний цикл. Спочатку я просто взяв свій псевдокод і почав деталізувати кожну його рядок з урахуванням формул Calc і архітектури свого процесора. Вигляд у цього всього вийшов страшний:
Псевдокод наближений до робочогоloop:
cx = IF(OR(AND(rcx="U";key_trigger="D");AND(rcx="D";key_trigger="U");AND(rcx="L";key_trigger="R");AND(rcx="R";key_trigger="L"));rcx;key_trigger)
ax = IF(ROUND(MOD(rax;10000)/100) < 89; ROUND(MOD(rax;10000)/100)+1; 20) * 100 + MOD(rax;100) + ROUND(rax/10000) * 10000
bx = IF(AND(rcx="U";MOD(ROUND(rbx/10000);100)>0);rbx-10000;IF(AND(rcx="D";MOD(ROUND(rbx/10000);100)<19);rbx+10000;IF(AND(rcx="R";ROUND(rbx/1000000)<9);rbx+1000000;IF(AND(rcx="L";ROUND(rbx/1000000)>0);rbx-1000000;"FAIL"))))
push cx
[ROUND(MOD(rax; 10000)/100)] = ROUND(rbx/10000)
jmp IF(ROUND(rax/10000) <> ROUND(rbx/10000); ctail; next)
ax = MOD(rax;10000) + MOD(MOD(ROUND(rax/10000);100)*11 + 3; 20) * 10000 + MOD(ROUND(rax/1000000)*3+2;10)*1000000 // ball generator
cx = [MOD(ROUND(rax/10000);100)] // get [BY]
[MOD(ROUND(rax/10000);100)] = BITOR(rcx; 2^(9-ROUND(rax/1000000))) // draw ball on scr
jmp svtail
ctail:
cx = [MOD(rbx;100)] // cx = [TY]
[MOD(rbx;100)] = BITAND(rcx; BITXOR(HEX2DEC("FFFF"); 2^(9-ROUND(MOD(rbx;10000)/100)))) // clear tail on scr
ax = IF(MOD(rax;100) < 89; rax + 1; ROUND(rax/100)*100 + 20)
cx = [MOD(rax;100)] // cx = [TT]
bx = ROUND(rbx/10000)*10000 + rcx
svtail:
cx = [MOD(ROUND(rbx/10000);100)] // cx = [HY]
[MOD(ROUND(rbx/10000);100)] = BITOR(rcx; 2^(9-ROUND(rbx/1000000))) // draw head on scr
pop cx
jmp loop

Тут я замінив змінні псевдокода на регістри, в ax вирішив зберігати 4 двозначних числа: BXBYHHTT, bx HXHYTXTY, тобто координати голови і хвоста, а у cx — напрям, ну і використовувати його для проміжних потреб. Наприклад, коли треба перекласти з пам'яті в пам'ять, безпосередньо цього зробити не можна, доводиться робити через регістр.

Подальшим кроком було тільки замінити присвоювання на команди mov, movm і mmov відповідно і перенести код в клітинки на аркуші.

З цікавих особливостей варто відзначити генератор випадкових чисел. Функція табличного процесора нам не підходить, тому що на кожній генерації координат м'ячика в програмі треба мати нові випадкові значення. А функція обчислюється лише раз і потім лежить у клітинці, поки не обновишь лист. Тому тут був прменен т. н. лінійний конгруэнтный метод.

Для спрощення перевірок на те, що м'ячик з'явився посеред змії не робиться. Також не робиться перевірок на прохід змії крізь себе.

Працює програма дуже «слоупочно». Я записав відео в реальному часі і прискорене в 16 раз. В кінці відео я проходжу крізь себе і врезаюсь в стіну (в регістрі bx появляестя «FAIL» і змійка більше нікуди не повзе).

Прискорене в 16 раз відео:


Реальний час

На відео можна бачити, що внизу аркуша є код ще однією маленькою програми — висновок біжить повзучою рядка. Там застосований деякий «хак», а саме: у програмі використовуються дані з сусідніх комірок, але, зрештою, чому б і ні? Адже ніхто цього не забороняв.

Відео прискорено в 16 разів:


Проект доступний на гітхабі, для роботи потрібно LIbreOffice Calc з встановленим BeanShell.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.