テーブルプロセッサ（MS ExcelまたはLibreOffice Calcについて話している）は、かなり面白く、汎用性の高いツールです。 自動レポート、仮説テスト、アルゴリズムのプロトタイピングなどの幅広い機能を頻繁に使用しました（そして使用する必要がありました）。 たとえば、Eulerプロジェクトのタスクを解決し、アルゴリズムをすばやくチェックし、1つのアプリケーションプロトコル用のパーサーを実装するために使用しました（作業する必要がありました）。 私は、テーブルプロセッサで実現できる可視性が好きであり、可能なすべてのものの非標準アプリケーションも好きです。 Excelの非標準アプリケーションのトピックに関する興味深い記事がすでにHabréに掲載されています。

「Excelの30行のアセンブラー」

軍隊のITスペシャリストのためにすべきこと、またはVBAゲームで書いた方法

「ExcelブックのRPGゲーム」



この長い記事では、テーブルプロセッサの式を使用したリアクティブプログラミングの実験を共有します。 これらの実験の結果、プロセッサ、メモリ、スタック、ディスプレイを備えた「コンピューター」を取得しました。これは、式（クロックジェネレーターを除く）のみを使用してLibreOffice Calc内に実装されています。 次に、例と概念実証として、このコンピューター用のゲーム「Snake」と走るクリープラインを書きました。

まえがき

それはすべて、私がさまざまなプログラミングパラダイムに興味を持つようになったという事実から始まり、ロボティクスクラブでのVerilogの入門レッスンに参加しました。 そして、ここで、 反応型パラダイムウィキペディアの記事で、次のテキストに出会いました。

最新のテーブルプロセッサは、リアクティブプログラミングの例です。 テーブルセルには、文字列値または「= B1 + C1」形式の式を含めることができます。その値は、対応するセルの値に基づいて計算されます。 依存セルの1つの値が変更されると、このセルの値は自動的に更新されます。

実際、Excelで数式を使用した人は誰でも、1つのセルを変更するとそれに関連付けられたセルも変更されることを知っています。これは、回路内の信号の伝播にかなり似ています。 これらすべての要因から、次のような考えに至りました：この「チェーン」が非常に複雑な場合はどうでしょうか？ チューリングテーブルプロセッサの数式は完全ですか？ いくつかの重要な結果を得るために数式を「プログラム」することは可能ですか？ （例えば、テトリスを作る） 私は仕事や家庭でUbuntuを使用しているため、LibreOffice Calc 4.2.7.2ですべての実験を行いました。

8x8デジタルディスプレイ

私はディスプレイの実装で実験を始めました。 ディスプレイは8x8の正方形セルのセットです。 条件付き書式設定が便利になりました（ExcelとCalcの両方で使用可能です）。 セルを選択し、書式設定/条件付き書式設定/条件...に移動して、外観を調整します。セルにスペースなどが含まれている場合は、黒の背景になります。 セルにスペースを書き込むと、黒になります。 したがって、ディスプレイのピクセルが実現されます。 しかし、私はこのディスプレイを何とかして管理したいです。 左に、数字を入力する特別な列を強調表示しました。この数字を使用して、画面に表示するビットマスクを設定します。 画面の上部で、列に番号を付けました。 ここで、表示の各セルに、左端の列に目的のビットが設定されているかどうかに応じて、スペースまたは空の行になる数式を記述する必要があります。

 = IF（MOD（TRUNC（<ビットマスク> /（2 ^ <表示列番号>））; 2）; ""; ""）

ここで、実際には、右へのシフトが発生し（2の累乗で除算された後、小数部分が破棄されます）、0番目のビット、つまり2による除算の残りが取得され、設定されている場合はスペースが返され、そうでない場合は空の文字列が返されます。

これで、数値の左端の列に書き込むと、ディスプレイにピクセルが表示されます。 次に、たとえば10進数のビットマスクを生成し、数値に応じて、ディスプレイマスクの列に必要な数値を入力します。

世代のために、別の8x8デザインが作成されました。このデザインでは、ユニットは手で入力され、式はこのすべてを1つの数値にまとめます。

 = SUMPRODUCT（<1と0のセルの行>; 2 ^ <位置番号の行>）

その結果、数値用のビットマスクのマトリックスが得られました。

次に、INDEX関数を適用します。行列、行、列を指定すると、この行列から値が返されます。 したがって、表示ビットマスクの各セルに、式を書きます

 INDEX（<matrix>; <digit> + 1; <display line number> +1）

INDEXはゼロではなく1から座標を計算するため、単位が追加されます。

円形リンク

さて、ディスプレイの準備ができました、あなたはあなたの手で数字を書く-それが表示されます。 次に、数値を切り替える、つまり、金額を累積する特定のカウンターを切り替えたかったのです。 ここで、式の循環リンクについて覚えておく必要がありました。 デフォルトでは、それらはオフになり、オプションに移動し、循環リンクを有効にします。私はこのように自分で設定しました：

循環リンクは、それ自体に応じて、セル内の数式を意味します。たとえば、セルA1では、数式「= A1 + 1」を記述します。 もちろん、そのようなセルは計算できません-有効な反復回数が終了すると、Calcは#VALUEまたはエラー523を生成します。残念ながら、Calcはだまされることができません。たとえば、A1では次のように記述します：= IF（A1 <500; A1 + 1; 0）、およびB1では、たとえば：= IF（A1 = 500; B1 + 1; B1）。 500は、遅延を提供するはずの魔法の数字です。つまり、A1に金額が蓄積される限り、時間がかかり、B1は変化します。 （まあ、ここではセルの初期初期化に注意する必要があります。）しかし、私の計画はうまくいきませんでした：Calcはいくつかのトリッキーなキャッシングと検証アルゴリズムを実装します依存関係がどれほどトリッキーであっても機能しません。 ちなみに、Excel 2003では、このトリックは部分的に機能しているようで、一般に、数式を計算するための別のモデルがあるようですが、Calcで実験することにしました。 その後、マクロのカウンターを作成することを決定し、既にすべての依存関係をハングさせています。 ある仲間は、一般に、マクロに同期パルス（クロック信号）のみを作成し、既にカウンターとそれに必要なものをすべて追加するように言った。 私はこのアイデアが気に入りました-マクロは些細なものであることが判明しました：遅延と状態の反対の変化。 カウンター自体は4つのセルで構成されます。

A1に1を入力して、初期値を初期化するためのリセットが既に提供されています。

このようなカウンターは前のセクションのディスプレイに接続されており、このビデオに表示されているものがわかります。



マクロがなければ完全に機能せず、クロックジェネレーターが式で機能しなかったことは残念です。 さらに、別の問題が発生しました。マクロがループされると、マクロがメインスレッドをブロックし、既に何も実行できないため、Calcを終了する必要があります。 しかし、双方向性に関する私の考えはすでに成熟しており、将来のスキームを何らかの形で制御したいと考えていました。

ノンブロッキングタイマー

幸いなことに、Calcでは、メインマクロストリームがブロックされていないことを確認できることがわかりました。 ここで私はトリックをして、既成のソリューションを「グーグル」して、自分用に調整しました。 このソリューションには、LibreOffice用のBeanシェルが必要でした。 パッケージはlibreoffice-script-provider-bshと呼ばれます。 コードは2つの部分で構成されています。1つはBeanShellに、もう1つはLibreOffice Basicにあります。 正直なところ、私はコードを完全に理解していませんでした...悔い改めました（Java、BeanShellは話せず、LibreOfficeオブジェクトモデルにあまり詳しくありません）が、何かを修正しました。







そこで、「Start / Stop」と呼ばれるボタンコンポーネントをシートに追加し、その上に時計機能を掛けました。 これで、ボタンが押されると、セルは指定された間隔で値を0または1に変更し、アプリケーションフローはブロックされなくなりました。 実験を続けることができました：同期信号にいくつかの式をハングアップし、あらゆる方法で「変態」すること。



それから私は何かすることを考え始めました。 画面、ロジック、ある種のようなものがあり、どれでも実装することができ、時計があります。 しかし、もしあなたが忍び寄る線、または一般的にテトリスを作るとしたらどうでしょう？ 実はデジタル回路です！ それから、デジタル回路で面白いゲームを思い出しました： kohctpyktop 、タスクの1つはアドレスアクセスで加算器とメモリを作ることでした。 そこでできるとしたら、ここでも可能だと思いました。 そして、画面があるので、ゲームを作成する必要があります。 そして、あるゲームには別のゲームがあるので、別のゲームを作ることができるようにする必要があります...そのような何かが、どういうわけか、セルにコマンドを入力し、彼がそれらの状態を変更できるようにプロセッサを作るという考えに思いつきました必要なものを表示しました。



たくさんの考え、試行錯誤があり、完成したプロセッサのエミュレーターを作る考えがありました。たとえば、Z80やその他の同様にクレイジーな考えです...最後に、私はメモリ、スタック、レジスター、mov、jmp、数学的なaddコマンドなどのいくつかのコマンドを作成しようとすることにしました、mul、subなど Calcの式はこれ以上の方法を既に知っているため、それを行わないことにしました。そのため、「アセンブラ」でテーブルプロセッサの式を直接使用することにしました。

記憶

メモリはそのようなブラックボックスであり、記録用のアドレス、値、および信号に入力できます。 記録用の信号が設定されている場合、値はブラックボックス内の指定されたアドレスに保存されます。信号が設定されていない場合、このアドレスで以前に保存された値はブラックボックスの出力に表示されます。 また、内容をクリアするには別の入力が必要です。 ここに、私が実装するために思いついたメモリの定義があります。 そのため、値を保存するためのセルがあり、「インターフェース」があります：入力と出力：

 m_address-アドレス
 m_value_in-書き込みの値
 m_set-書き込み信号
 m_value_out-値の読み取り、出力信号
 m_clear-クリアするシグナル

より便利にするために、Calcでセルに名前を付ける機能を活用しましょう。 セルに進みましょう。挿入/名前/定義...これにより、セルに使用可能な名前が与えられ、これらの名前が数式で使用されます。 そのため、上記の5つのセルに名前を付けました。 次に、10x10の正方形の領域を選択しました-これらは値を保存するセルです。 エッジの周りの行と列の番号-数式で列と行の数を使用します。 これで、値を保存する各セルに同じ数式が入力されます。

= 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]））、

ここでのロジックは単純です：最初に、クリーニング信号が設定されている場合はチェックされ、次にセルがゼロになります。そうでない場合は、アドレスが一致するかどうかを確認します（セルは番号0..99でアドレス指定され、列と行には0から9まで番号が付けられます）はい、レコードの値を取得し、そうでない場合は現在の値を保存します。 すべてのメモリセルに数式を拡張し、メモリに任意の値を入力できるようになりました。 次の式をm_value_outセルに配置します。= INDIRECT（ADDRESS（ROW（[first_memory_cell]）+ m_address / 10; COLUMN（[first_memory_cell]）+ 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	=行（間接（s_address））
sp_column	= COLUMN（間接（s_address））+ sp
oldsp	= IF（AND（s_push = 0; s_pop = 0）; sp; oldsp）

ここで、スタックが示すアドレスを形成するために、スタックの先頭のアドレスを取得し、それにスタックポインターを追加することに気付くのは簡単です。 スタックポインタの古い値は、書き込み信号と排出信号の両方がゼロのときに更新されます。 これまでのところ、すべてがシンプルです。 spの式は非常に複雑なので、理解を深めるためにインデントを付けます。



5つのネストされたIFはモンスターのように見えますが、このような長い数式をいくつかのセルに分割したため、各セルには2つしかIFがありませんでした。



値を格納するセルの式を与えることは残ります：

  = 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 ]）） 

ここでは、原則として、インデントなしで「解析」できます。ポイントは、特定の条件がチェックされ、この条件が満たされると、s_pushvalueがセルに入力されることです。 条件は次のとおりです。s_push信号をコックする必要があります。 セルの行は、spが指す行と一致する必要があります。 spが表示する列は、セルの列よりも1多い必要があります。 まあ、spはoldspと古い値を等しくすべきではありません。



わかりやすくするために、私が得たもの：

CPU

さて、メモリがあり、スタックがあります。 画面を8x8より大きくしました。 元々はテトリスについて考えていましたが、90年代のBrickGameのように、10x20をやりました。 メモリの最初の20セルをビデオメモリとして使用しました。つまり、それらを画面の20行に接続しました（したがって、画像では濃い赤になっています）。今、必要な値を適切なアドレスに保存して、画面に何かを描画できます。 メモリ、スタックを使用し、コマンドを読み取り、実行する主なものを実装する必要があります。



したがって、私の中央処理装置は次の部分で構成されています。



要するに、それがどのように機能するのか：入力はクロックに接続されてリセットされます（便宜上、純粋な形式のためにボタンにハングアップしました）、エントリポイントは手動で構成されます。 出力はメモリとスタックに接続され、コマンドに応じて、必要な信号が出力されます。 ip命令ポインターが指す場所に応じて、コマンドとオペランドが入力されます。 レジスタは、命令とオペランドに応じて意味が変わります。 ipは、コマンドに応じて値を変更することもできますが、デフォルトでは、各ステップで1ずつ増加するだけであり、すべてが人が示すエントリポイントから始まります。 T.O. プログラムはシートの任意の場所に配置できます。主なことは、c_mainの最初のセルのアドレスを指定することです。

オペランドとコマンドとして、プログラムは数式を指定できます。主なことは、セル内の結果は値であり、処理のためにプロセッサに送信される値です。

単純な内部構造から始めましょう。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について説明します。 第三に、ここでは特別なヌル値（エラーの場合）を適用し、「-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）

レジスタの式は、どのコマンドが現在のコマンドであるかをチェックしますが、より多くのコマンドがすでに考慮されているため、IFネストレベルは完全に読み取り不可です。 ここで、長い数式を複数のセルに分散する方法の例を示します。



残っているのは、プロセッサの出力信号のみです。

push_value	= IFERROR（IF（command = "push"; opA; push_value）; null）
push_c	= IF（コマンド= "プッシュ"; 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信号は本質的には同じように見えますが、それらの式はわずかに異なります。 私はそれらが多くの試行錯誤の方法によって得られたと答えることができます。 この設計全体をデバッグする過程で、多くのバグがありましたが、残念なことに、プロセッサは「クロックのように」動作しない場合があります。 何らかの理由で、私はそのようなオプションだけに決めました。つまり、「別の方法で」何かが機能しなかったことを意味します。 今は正確に何を正確に思い出せない



私のプロセッサーの写真：



ここでは、デバッグフィールドを見ることができます。値は表示されず、テキスト形式の数式が表示されます。

プログラミング

これで、コンピューターの準備が整いました。プログラムの作成を開始できます。 プログラミングプロセス中に、いくつかの問題が発見されましたが、そのうちのいくつかは解決され、いくつかはまだ残っています。

1. 時々「コンピューター」はバグがあり、予測できない動作をします
2. プログラムを含むほとんどすべてがシート上に表示されている必要があります。そうでない場合、表示範囲をはるかに超えるセルは内容を更新しません。
3. 「コンピューター」は遅いことがわかり、ティック間の遅延を減らすと、表示と一部の数式に更新する時間がありません。経験的に、私はラップトップに最適な遅延を多かれ少なかれ選択しました：150-200 ms

「プログラム」の各行は1つの「ティック」で実行されるため、行は可能な限り小さくする必要があります。可能な場合は、1つの式にできるだけ詰め込むようにしてください。主な問題は、テトリスのコードが大きすぎてシートにまったく収まらない可能性があることが判明したため、（私はテトリスで苦しめられた後）「スネーク」を書き、これに最小限の行数を使用しようとすることに決めました。



入力インターフェース、すなわちコントロールボタンはマクロで実行する必要がありました。4つの矢印ボタンと、ボタンが押されると1が配置される4つのセル（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））））キー。



また、プログラムをデバッグするためのデバッグボタンを作成しました。これを使用して、手動でクロックジェネレーターを制御し、セルの状態がどのように変化するかを確認できます（クロックセルに1または0を交互に入れます）。これがすべてのマクロが担当するものです：クロックとコントロール。これ以上マクロはありません。



彼は擬似コードで「Snake」の開発を始めました。



次に、このアルゴリズムを詳しく説明する必要がありました。初期化から始めましょう：



その後、メインサイクルが開始されます。最初は、擬似コードを取得し、Calcの式とプロセッサのアーキテクチャを考慮して、各行の詳細を記述し始めました。これはすべてひどく見えました：



次の手順は、割り当てをそれぞれmov、movm、およびmmovコマンドに置き換え、コードをシート上のセルに転送することのみでした。



興味深い機能のうち、乱数ジェネレーターに注目する価値があります。テーブルプロセッサ関数は、プログラム内のボール座標の各世代で、新しいランダムな値を必要とするため、私たちには適していません。そして、関数は一度だけ計算され、シートを更新するまでセルに置かれます。したがって、いわゆる線形合同法。



簡単にするために、ボールがヘビの真ん中に現れたことの確認は行われません。また、ヘビが自分自身を通過するためのチェックも行われません。



プログラムは非常に「ずさん」です。ライブビデオを録画し、16倍加速しました。ビデオの最後で、私は自分自身を通り抜けて壁にぶつかります（bxレジスタに「FAIL」が表示され、ヘビは他のどこにも忍び寄りません）。



16倍高速のビデオ：









結論-ビデオでは、シートの下部に別の小さなプログラムのコードがあることがわかります旅のクリーピングの行が。そこで、いくつかのハックが適用されました。つまり、プログラムは隣接セルからのデータを使用しますが、最終的にはどうしてですか。結局のところ、誰もこれを禁じていません。



ビデオを16倍高速化：





プロジェクトはgithubで利用できます; BeanShellがインストールされたLIbreOffice Calcは動作するために必要です。