ELVM Scratch 3.0 backend

この記事は 言語実装 Advent Calendar 2020 の12日目の記事です。 昨日はfukkunさんの「Lazy Code Motion」でした。 明日はelpinalさんの「モジュールのパターンマッチ・Focused Logic」です。

はじめに

こんにちは。algonです。

今年の4月頃にScratchで遊んでいて、そのときにELVMのScratch 3.0のバックエンドを実装しました。 この記事では

• Scratchについて
• ELVMについて
• どのようにScratchバックエンドを実装したか

などについて紹介したいと思います。

Scratchとは

ScratchはMIT Media Lab Lifelong Kindergarten Groupによって開発されているビジュアルプログラミング言語とその開発環境です。 ブロック状のパーツをグラフィカルに組み合わせていくことで直感的にプログラミングすることができます。

簡単な例を示すと、「1秒毎に変数をインクリメントして表示する」プログラムは以下のように実装できます。 (こちらから実行することができます。)

このプログラムでは、緑色の旗ボタンをクリックすると実行が始まり、 1秒毎に「へんすう」がインクリメントされながら吹き出しの中にその値が表示されます。

Scratchでは、このような簡単なプログラムはもちろん、 ブロック崩しのようなゲームからLISP処理系まで、 基本的には何でもつくることができます。

開発環境

Scratchの開発環境は公式サイトから利用でき、Webブラウザさえあれば簡単に遊ぶことができます。 作ったプログラムを共有しないのであればログインすら不要です。

Scratchエディタ

言語について

Scratchでは「緑色の旗ボタンがクリックされたタイミング」や「キーボードの〜キーが押されたタイミング」 などのイベントに応じて動作するスクリプトを記述することによってプログラムを行います。

データ型

Scratchのデータには数値、文字列、真偽値の3種類があります。 数値と文字列はどちらも同じ形のブロックで表され、必要に応じてキャストが行われます¹。

ブロック

Scratchでは以下に挙げるようなブロックを組み合わせることでプログラミングを行います。 ブロックの機能によって形や色が分けられています。 ブロックの形が合わないような繋ぎ方はできなくなっており、これによってシンタックスエラーを回避しています。

イベントブロック

上部が丸くなっているブロックは「ハットブロック」と呼ばれ、 対応するイベントが発生するとこれらのブロックから実行が開始されます。

コントロールブロック

条件分岐やループを行うためのブロックです。

数値演算

数値演算を行うブロックです。

文字列演算

文字列に関する演算を行うブロックです。

真偽値演算

真偽値に関する演算を行うブロックです。

変数

Scratchでは変数を扱うことができます。 変数には数値か文字列のどちらかを格納することができます。

リスト

リストを扱うこともできます。

その他

その他にも様々な機能を持つブロックが用意されています。

カスタムブロック

一連の手続きをまとめた新しいブロックを定義して利用することができます。 他のプログラミング言語における関数のように使うことができ、再帰的に呼び出すこともできます。

ここに挙げたブロック以外にも、見た目を変えたり音を鳴らしたりするブロックも用意されています。 ブロックの完全な一覧と説明はwikiを参照してください。

Scratchのコード生成

さて、Scratchについての説明はこれくらいにしておいて、本題に移りたいと思います。

一通り遊んでみたあと、何か面白いことはできないかと考えていました。
そんなときに思い出したのがScratcher’s AtCoderです。

Scratch → C++ (Scratcher’s AtCoder)

Scratcher’s AtCoder は、yos1upさん作の、 ScratchでAtCoder(競技プログラミングのコンテスト)に参加するためのChrome拡張機能です。

Scratcher’s AtCoderでは、 ScratchのプログラムからC++のコードを出力することによってAtCoderに参加できるようにしています。

「〜ときいてまつ」ブロックと「〜という」ブロックを標準入出力として解釈してC++のソースコードへ変換を行っているようです。

C言語 → Scratch (???)

ScratchからC++を生成することができるのであれば、 逆に別の言語からScratchプログラムを生成することもできるはずです。 少し調べたところ誰もやっていなさそうなので挑戦してみることにしました。

そこで、ELVMを用いて C言語からScratchのコードを生成することを考えました。

shinh/elvm

ELVMはLLVMのような仕組みを用いて、C言語から様々な難解言語に対してコンパイルを行うことができるコンパイラ基盤です。 ELVMでは、フロントエンド(改造された8cc)によってC言語からELVM IRへの変換が行われ、 各言語のバックエンドによってIRからそれぞれの言語への変換が行われます。

今回はScratchのコードを生成するので、 ELVM IRを入力としてScratchのコードを出力するバックエンドを作成することになります。

Scratchのソースコード(?)を扱う

Scratchエディタで作成したScratchプログラムはメニューの「ファイル → コンピュータにほぞんする」 からローカルに保存し、「ファイル → コンピュータからよみこむ」から保存したプロジェクトを 読み込むことができるようになっています。

ここで保存・読み込みしているファイルがプログラムの本体なので、このファイルを機械的に生成すればよいことになります。

このファイルのフォーマットについてはScratch File Format - Scratch Wikiに詳しい説明がありました。

The Scratch 3.0 file format is the format used to store exported Scratch 3.0 projects and sprites. These are ZIP archives which contain information encoded in a text-based format called JSON and project media in separate files. Projects have the extension .sb3, and sprites .sprite3.

JSON形式のプロジェクトファイルとその他のアセット(画像や音声)がzipアーカイブされたファイルになっているようです。

wikiのページにはJSONファイルについてのフォーマットが書かれています。 大まかには次のような雰囲気になっています。

{
    "targets":[
        {
            "isStage":true,
            "name":"Stage",
            "variables":{
                "#r:a":["a", "0"],
                "#r:b":["b", "0"],
                ...(略)...
            },
            "broadcasts":{},
            "blocks":{
                ...(略)...
                "b250":{
                   "opcode":"data_setvariableto",
                   "next":"b251",
                   "parent":"b247",
                   "shadow":false, "topLevel":false,
                   "inputs":{ "VALUE":[2, "b249"]},
                   "fields":{ "VARIABLE":["b", "#r:b"]}
                },
                "b249":{
                   "opcode":"operator_mod",
                   "next":null,
                   "parent":"b250",
                   "shadow":false, "topLevel":false,
                   "inputs":{
                       "NUM1":[2, "b248"],
                       "NUM2":[1, [10, "16777216"]]
                   },
                   "fields":{}
                },
                ...(略)...
            },
            "comments":{},
            "currentCostume":0,
            "costumes":[{
                "name":"backdrop",
                "assetId":"fcb8546c50e11d422b78fd55e34d7e7e",
                "md5ext":"fcb8546c50e11d422b78fd55e34d7e7e.svg",
                "dataFormat":"svg"
            }],
            "sounds":[],
            "volume":100,
            "layerOrder":0,
            "tempo":60,
            "videoTransparency":50,
            "videoState":"on",
            "textToSpeechLanguage":null
        }
    ],
    "monitors":[],
    "extensions":[],
    "meta":{"semver":"3.0.0"}
}

ELVM

ELVMはとてもシンプルに設計されたVMです。 簡単にまとめると、以下のような仕様になっています。

• ワード: 符号なし整数 (多くのバックエンドで24bit)
• レジスタ: A, B, C, D, SP, BP の6種類 (それぞれ1ワード)
• メモリのアドレス空間: 1ワード
• 命令列はメモリとは別に存在
  • 各ベーシックブロックに対してアドレス(PC)が振られる
  • あるPCへジャンプすると対応するベーシックブロックの先頭の命令から順に実行される
• 命令: 以下の22種類
  • MOV dst, src
    • 代入
  • ADD dst, src
    • 加算
  • SUB dst, src
    • 減算
  • LOAD dst, src
    • メモリ読み込み
  • STORE src, dst
    • メモリ書き込み
  • PUTC src
    • レジスタの値をASCIIコードとして標準出力に1文字書く
  • GETC dst
    • 標準入力から1文字読み、ASCIIコードをレジスタに格納
  • EXIT
    • プログラムの終了
  • JEQ/JNE/JLT/JGT/JLE/JGE jmp, dst, src
    • 条件付きジャンプ
  • JMP jmp
    • ジャンプ
  • EQ/NE/LT/GT/LE/GE dst, src
    • 比較結果(0か1)をdstに格納
  • DUMP
    • 何もしない

バックエンドの実装

ここからはELVMの構成要素をScratch上でどのように扱うかについて見ていきます。

レジスタ

ELVMの6つのレジスタはScratchの変数を用いて管理します。 符号なし24bit整数の範囲(0〜16777215)はそのままScratch上での数値として扱うことができます²。

標準入出力

標準入力は「〜ときいてまつ」ブロックを用いて受け取り、 標準出力はリストの1要素を1行にみたてて出力します。

以下のスクリーンショットは test/echo.eir から生成した例です。 NULL文字が入力されるまで標準入力の文字を標準出力にエコーし続けるプログラムです。

特殊文字を入力するためにエスケープ文字として全角バックスラッシュ(＼)を使うことにしました³。

改行文字は ＼n 、null文字は ＼0 、それ以外の特殊文字は ＼dXXX (XXXは10進3桁)で入力します。

入力を処理する部分は次のように実装しました。 _w はGETC命令が呼ばれたことを示すフラグ変数です。 標準出力のstdoutの他に、標準入力のバッファとしてstdinというリストを用いています。 入力された文字列を文字毎に区切ってstdinに追加しています。

GETC命令の実装は次のようになっています。 標準入力から1文字取ってきてascii_encodeを呼び出しています。 結果はgetcharとascii_encodeどちらも変数_rに格納するということにしています。(ここではascii_encodeの結果がそのままgetcharの結果になります。)

PUTC命令の実装は次のようになっています。 今度は_rが入力となり、入力の数値をASCIIコードとして解釈し、対応する文字をstdoutに追記しています。 改行文字のとき(_r == 10)は新しい行を追加します。

ASCIIエンコーダ・デコーダ

ascii_encodeとascii_decodeの実装は以下のようになっています。

特殊文字(＼dXXX)の場合は3文字目から3文字をそのままコードとして返します。

それ以外の文字の場合は後述する背景を用いたテクニックによってASCIIコードに変換します。

当初はASCIIテーブルをリストとして埋め込んでおいて、 リストのi番目を取得する操作と線形探索によってASCIIエンコーダ・デコーダを実装しようとしていたのですが、 Scratchの等価演算子(=ブロック)は大文字小文字を区別しない という仕様のせいでうまく動きませんでした。

大文字小文字を区別して等価判定を行うハックとして「コスチューム」を用いる方法がScratch Wikiで紹介されていたので最終的にこれを採用しました⁴。

Case Sensing

背景

背景は複数用意することができ、それぞれに名前をつけることができます。

ステージの背景を切り替えるための「はいけいを〜にする」というブロックがあります。 入力には背景の番号もしくは背景の名前を用いることができ、 指定した背景に切り替えることができます。

ここで、背景の名前を入力したときの挙動がポイントで、実はこのときの背景の名前は大文字と小文字が区別されるという仕様になっています。 そして現在の背景の名前と番号はそれぞれ「はいけいのなまえ」「はいけいのばんごう」ブロックから得ることができます。 これらを使って背景の名前としてASCIIテーブルを埋め込むのが次のテクニックです。

ASCIIテーブルを背景に埋め込む

背景を128個用意し、それぞれに

• 1番目の背景は「＼0」
• 2番目の背景は「＼1」
• …
• 34番目の背景は「!」
• 35番目の背景は「"」
• …
• 66番目の背景は「A」
• …
• 98番目の背景は「a」

のように名前をつけておくと、背景をASCIIテーブルとして用いることができるようになります。

例えば「はいけいを33+1にする」を実行したあとで「はいけいのなまえ」を参照することで!を得ることができ、ASCIIコードの33から!という文字を引くことができます。 エンコードはこの逆を行います。

「はいけいを〜にする」ブロックでは大文字小文字が区別されるため、「はいけいを"A"にする」と「はいけいを"a"にする」はそれぞれ66番目の背景と98番目の背景に切り替わり、正しくASCIIエンコードを行うことができます。

メモリの管理

24bitのアドレスで表現されるメモリをどう扱うかが一番の悩みどころでした。

まず愚直な方針として、巨大なリストを用意し、メモリの各ワードをリストの1要素として表現しようと考えました。 しかし残念ながら、Scratchのリストは最大で20万要素に制限されているため、そのままでは24bitのアドレス空間を扱うことができません。

また、2^24個の値を10進表記の文字列として連結して1つの巨大な文字列として扱うのはどうだろうと思い試してみたところ、プロジェクトが重くなりすぎてエラーで落ちてしまいました。
実はScratchのプロジェクトファイルには最大で5MBというサイズ制限があり、メモリの情報を直に持たせるとそれだけで5MBを超えてしまうのが原因でした。

そこで値を文字列としてそのまま連結するのではなく圧縮した状態で持つことにしました。 圧縮といっても複雑なロジックを書くのは大変なのでBase64を用いて文字列化します。 初めは16進表記で文字列化しようとしていましたが、圧縮率の観点からBase64でエンコードすることにしました⁵。

それでもメモリ全体の値を持つのはファイルサイズの制限からまずそうなので、適当なグループ毎(4069要素毎)にリストの1要素に格納することにして、未使用の部分は空にしておいて必要になったタイミングで生成するようにしました。

この例では、

• 0番地に8388608
• 1番地に4194304
• …
• 4096番地に0
• 4097番地に0
• …

という感じで値が格納されています。

あとはASCIIコードと同じようにBase64エンコーダ・デコーダを実装すれば完了、といきたいところですが、ここに来てまたまた問題に直面します。

実は、Scratchには「文字列のi文字目を変更する」ブロックが存在しないのでした！ 「文字列のi文字目を取得する」ブロックがあるので変更するブロックもあるだろうと思い込んでいました……

しばらく考えた後、 特定のグループ(4069要素)だけ別のリストに要素毎にデコードしておいて、 必要になったタイミングでエンコードして書き戻す方針を思いつきました。

ちょうどOSのページイン・ページアウトのようなイメージです。 (以降、Base64デコードして要素ごとにばらす操作をページイン、その逆をページアウトと呼ぶことにします。)

ページアウトの処理には「i文字目を変更する」という操作は必要なく、 「文字列の末尾に文字を追加する」操作によって実現できます。

展開中のページ以外の範囲を書き換える必要が出てきたら、そのタイミングでページアウト・ページインを行います。

「こういうときはダーティビットを用意すると不要なページアウト処理をなくせる」 というOSの授業で習った知識を思い出しましたが、今回は不要でした。
メモリのロードだけなら「文字列のi文字目を取得する」ブロックを使うことでページインなしで読み込めるからです。 つまり、ページインが必要なのはメモリを書き換えるときのみなので、そもそもダーティビットは不要なのでした。

そんなこんなでようやくメモリ管理の方針が決まりました。

Base64エンコーダ・デコーダ

base64_encode、base64_decode の実装は以下のようになっています。ASCIIエンコーダ・デコーダと基本的に同じです。

背景の番号をASCIIの空間分(128要素分)ずらしている点と、 衝突を避けるために先頭に ! を前置している点が異なります。

MOV命令

変数の値を初期化するブロックがそのまま使えます。

ADD命令、SUB命令

符号なし整数のラップアラウンドのために0x1000000でmodを取っています。

LOAD命令、STORE命令

_r 変数を経由して値を読み書きしています。

EXIT命令

処理を中断するブロックがそのまま使えます。

JMP系命令

pcレジスタを変更します。-1しているのは外側のループでpcのインクリメントを行っている分を打ち消すためです。 (あるベーシックブロック内の命令をすべて実行し終えたら次のベーシックブロックに遷移する必要があるため、ループの末尾でPCのインクリメントを入れています。)

JGE, JLE, JNE命令では、比較を行う際にブロック数を減らすために逆の判定を行いif-elseブロックのelse側を利用するような工夫を行っています。

Scratchには「X ≤ Y」のようなブロックが存在しないため、愚直にやろうとすると「X<(Y+1)」のようになってしまい、加算の1ブロックが余計に必要になってしまいます。

比較系命令

if-elseブロックを用いて愚直に実装しています。GE命令やNE命令では、JGE命令やJNE命令と同様のブロック数を減らす工夫を行っています。

制御フロー

PCレジスタの値に応じて対応するベーシックブロックを実行するようにします。

switch文が欲しくなりますが、Scratchにはswitch文に相当するブロックは存在しないので、if-elseを用いて実装します。

素直に実装すると次のようになると思います。

これでいいのですが、目的のベーシックブロックにたどり着くまでにPCの大きさに比例した回数の比較が発生することになり、後ろの方を実行するのが遅くなってしまいます。

そこで、以下のように二分探索的にif-elseをネストするようにしました。

最終的には、ここからさらに512個毎のチャンクに分けることでネストが深くなりすぎないようにしました。 (ただ、この工夫にどれくらい効果があるかは不明です。)

C言語でJSONを生成

ELVMのバックエンドとして完成させるために、ここまでに紹介したScratchのプログラムをJSONとして出力するものをC言語で実装します。 wikiのJSONの仕様が不完全だったため、コードを読みに行ったりScratchエディタで組み立てたものをリバースエンジニアリングしながら頑張りました。

実装したものが target/scratch3.c になります。

方針としては、まずはブロックの木を構築し、これをトラバースしながらJSONを出力しています。

バックエンドのエントリポイントは void target_scratch3(Module *module) です。module->data に静的に配置するデータの情報が、module->text に命令列が格納されています。

以下の部分で各コンポーネントを構築しています。

1635  scr3_impl_read_stdin();
1636  scr3_impl_ascii_encode();
1637  scr3_impl_ascii_decode();
1638  scr3_impl_base64_decode();
1639  scr3_impl_base64_encode();
1640  scr3_impl_writeback_page();
1641  scr3_impl_expand_page();
1642  scr3_impl_store();
1643  scr3_impl_load();
1644  scr3_impl_initialize();
1645  scr3_impl_getchar();
1646  scr3_impl_putchar();
1647  scr3_impl_init_memory(module->data);
1648  scr3_impl_main_loop(module->text);

その後、JSONを出力します。 Scratchプログラムの変数(レジスタやリスト)、ブロック(プログラム本体)、背景(ASCIIテーブルとBase64テーブル)などを出力していきます。

1652  printf("{\"targets\":[{\"isStage\":true,\"name\":\"Stage\",");
1653  printf("\"variables\":{");
1654  for (scr3_reg_t reg = 0; reg < scr3_reg_count; reg++) {
1655    if (reg) putchar(',');
1656    const char *name = scr3_register_name[reg];
1657    printf("\"#r:%s\":[\"%s\", \"0\"]", name, name);
1658  }
1659  printf("},\"lists\":{");
1660  for (int list = 0; list < SCR3_NUM_OF_LIST; list++) {
1661    if (list) putchar(',');
1662    const char *name = SCR3_LIST_NAME[list];
1663    printf("\"#l:%s\":[\"%s\", []]", name, name);
1664  }
1665  printf("},\"broadcasts\":{},\"blocks\":{");
1666
1667  scr3_emit_all();
1668
1669  printf("},\"comments\":{},\"currentCostume\":192,\"costumes\":[");
1670
1671  // embed ASCII table in backdrops
1672  for (int i = 0; i < 128; i++) {
1673    char escaped_char_str[10];
1674    if (32 <= i && i < 127) {
1675      sprintf(escaped_char_str, (i == '"' || i == '\\') ? "\\%c" : "%c", i);
1676    } else if (i == 10) {
1677      sprintf(escaped_char_str, "＼n");
1678    } else {
1679      sprintf(escaped_char_str, "＼%d", i);
1680    }
1681    printf(
1682        "{\"name\":\"%s\",\"assetId\":\"%s\",\"md5ext\":\"%s.svg\","
1683        "\"dataFormat\":\"svg\"},",
1684        escaped_char_str, SCR3_SVG_MD5, SCR3_SVG_MD5);
1685  }
1686  // embed Base64 table in backdrops (with prefix '!')
1687  for (int i = 0; i < 64; i++) {
1688    printf(
1689        "{\"name\":\"!%s\",\"assetId\":\"%s\",\"md5ext\":\"%s.svg\","
1690        "\"dataFormat\":\"svg\"},",
1691        SCR3_BASE64_TABLE[i], SCR3_SVG_MD5, SCR3_SVG_MD5);
1692  }
1693
1694  // main backdrop
1695  printf(
1696      "{\"name\":\"backdrop\",\"assetId\":\"%s\",\"md5ext\":\"%s.svg\","
1697      "\"dataFormat\":\"svg\"}",
1698      SCR3_SVG_MD5, SCR3_SVG_MD5);
1699
1700  printf(
1701      "],\"sounds\":[],\"volume\":100,\"layerOrder\":0,\"tempo\":60,"
1702      "\"videoTransparency\":50,\"videoState\":\"on\",\"textToSpeechLanguage\":"
1703      "null}],\"monitors\":[{\"id\":\"#l:stdout\",\"mode\":\"list\","
1704      "\"opcode\":");
1705  printf(
1706      "\"data_listcontents\",\"params\":{\"LIST\":\"stdout\"},\"spriteName\":"
1707      "null,\"value\":[],\"width\":480,\"height\":280,\"x\":0,\"y\":0,"
1708      "\"visible\":true}],\"extensions\":[],\"meta\":{\"semver\":\"3.0.0\"}}");
1709  return;

C言語にはraw stringリテラルがないため、頑張ってダブルクオートをエスケープしています。

ちなみに、#define RAW(...) (#__VA_ARGS__) というマクロによってraw stringリテラルを模倣することもできますが、連続する空白文字が半角スペース1個に置換されてしまいます。

 1#include <stdio.h>
 2#define RAW(...) (#__VA_ARGS__)
 3int main(void) {
 4  printf("%s\n",RAW(
 5    {
 6      "foo": [
 7        "bar",
 8        "baz"
 9      ]
10    }
11  ));
12  // => { "foo": [ "bar", "baz" ] }
13}

初めはこれを使って実装を進めていたのですが、 エディタのシンタックスハイライトやフォーマッタがうまく動かなかったり、 あまりきれいな方法とは言えないので結局使いませんでした。

実行

ELVMのコマンド

elvmのリポジトリのルートディレクトリでmakeを実行すると、out/以下に8cc、elc、eliなどが生成されます。

out/8ccはELVM IRを出力する機能が加わった8ccです。 C言語のソースファイル(*.c)をコンパイルしてEIRファイル(*.eir)を出力することができます。

$ ./out/8cc -S -Ilibc ./test/fizzbuzz.c -o ./fizzbuzz.eir
$ ls ./fizzbuzz.eir
./fizzbuzz.eir

out/elcはEIRファイルを入力に取って、各バックエンドの出力を得ることができます。 コマンドラインオプションでバックエンドの名前を指定します。 バックエンドの名前はtarget/elc.cのget_target_funcから確認できます。

$ ./out/elc -rb ./test/basic.eir > basic.rb
$ ruby basic.rb
!!@X

out/eliはEIRをそのまま解釈して実行するインタプリタです。

$ ./out/eli ./test/basic.eir
!!@X

Scratchプロジェクトの生成

Scratchバックエンドが出力したJSONからsb3ファイルを生成するための補助スクリプト(tools/gen_scratch_sb3.sh)を作成しました。 以下のように使うことができます。

$ ./out/elc -scratch3 ./test/echo.eir > ./echo.eir.scratch3
$ ./tools/gen_scratch_sb3.sh ./echo.eir.scratch3
$ ls echo.eir.scratch3.sb3
echo.eir.scratch3.sb3

elcが出力したJSONファイル(./echo.eir.scratch3)を引数として渡して実行すると、同じディレクトリに*.sb3ファイルが生成されます。生成された*.sb3ファイルはScratchエディタから読み込んで実行できます。

コマンドラインからの実行

生成されたScratchプログラムをコマンドラインから実行するための補助スクリプト(tools/runscratch3.sh, tools/run_scratch.js)を作成しました。

コマンドラインから実行するにはtoolsディレクトリ以下にnpmパッケージscratch-vmをインストールしておく必要があります。

run_scratch.js 側でエスケープ処理を行っているため、 コマンドラインから実行する場合は特殊文字もそのまま入力できます。

$ cd tools
$ npm install scratch-vm
$ echo -e "hello\nworld" | node ./run_scratch.js ../echo.eir.scratch3.sb3
hello
world

ちなみに実行はかなり遅く、私の環境では結果が出力されるまでに20秒くらいかかりました⁶。

C言語からの変換

以下のようにしてC言語で書かれたプログラム(your_program.c)をScratchプロジェクト(your_program.scratch3.sb3)へ変換できます。

$ ./out/8cc -Ilibc -S your_program.c -o your_program.eir
$ ./out/elc -scratch3 your_program.eir > your_program.scratch3
$ ./tools/gen_scratch_sb3.sh your_program.scratch3
$ ls your_program.scratch3.sb3
your_program.scratch3.sb3

8cc in Scratch

$ ./out/elc -scratch3 ./out/8cc.c.eir > ./out/8cc.c.eir.scratch3  # 8ccをScratchに変換
$ cat ./test/8cc.in
int putchar(int x);

int main() {
  putchar('X');
  return 0;
}
$ time nodejs --stack-size=65500 ./tools/run_scratch.js \
> ./out/8cc.c.eir.scratch3 < ./test/8cc.in > ./8cc.in.eir # Scratch版8ccでコンパイルしてEIRを出力

real    92m52.362s
user    90m44.119s
sys     0m10.411s
$ ./out/eli ./8cc.in.eir  # eliで実行
X$ 

1.5時間くらいかかりましたが、Scratch上で8ccが動きました!!

生成された ./out/8cc.c.eir.scratch3 のサイズは46MBくらいありました。 Scratchの仕様上は5MBの制限があるはずですが、scratch-vmではそれを超えるものでも一応実行できるようです。 ちなみに、Scratchエディタからは読み込むことができませんでした。

elc in Scratch

8ccが動いたならelcも! と思いながら走らせてみましたが、48時間経っても終わらなかったので諦めました…… 残念!

おわりに

この記事では今年の4月頃に取り組んだELVM Scratchバックエンドの実装について紹介しました。 やはりいろいろな制約がある環境でのプログラミングは楽しいですね。

みなさんも是非ScratchやELVMで遊んでみてください。

1#include <stdio.h>
2int main(void) {
3  printf("Thank you for reading!\n");
4  return 0;
5}