scratchでC++再現した話

はじめに

某高専の授業で提出課題に「矢印キーを使うゲームを作ろう！」というものがありました。
矢印キーを使うー＞コードエディター　ー＞IDE on scratch
ということでC++ likeな何かをscratchでつくり、それのエディターとして提出することにしました。

この記事は

• scratcher
• コンパイラを作ったことのない人

向けの記事となっています。

また、もっといい実装方法があると思いますが、考えたものを直接scratchで作っているので最適化の段階まで行けませんでした。

完成品はこちら

このような画面が出てくるので左上の旗(下のほう)を押せば実行できます

Visual Scratch Code

課題判定フラグをたてるためのものです。
矢印キーでカーソルを移動させてエンターで改行、スペースで挿入できます。

右に行くとき

• その行の最後じゃないとき
  • 右へ移動(x+=1)
• 行の最後のとき
  • 下に行があるなら一つ下の行へ移動(y+=1;x=1)
    

左に行くとき

• 左に行ってみる
• もし端っこで上の行がないなら
  • 前の行の端へ移動(y-=1;x=1)
• 上があれば
  • 前の行の最後へ移動(y-=1;x=len(code[y]))
    

上下に行くとき

移動可能なら y±1
行がないなら限界点まで移動

画面の描画

show_lineで描画する行を計算します。
描画はリストの表示を応用してます(それ以外の方法だと30fpsまでしかでません)
show_lineはカーソルの位置から計算されます。
カーソルが常に画面内に入るようになってます
show_lineの計算ができたら、13回show_line+countの行をVSCodeに入れます。
カーソルの部分だけ別で追加処理をします。
カーソルの位置の前後をtemp1,2にいれて、それと"|"を合成します。

基本構造

変数とかメモリ管理のやり方

残念ながらscratchには辞書や2次元配列なるものが存在しません。
なのでリスト(配列)のindexを一致させ辞書的に情報を扱えるシステムを構築しました。具体的にpythonで例を示すと、

# aの値を読むとき
RAM[name_list.find("a")]
# aにbを代入
if type_list[name_list.find("a")]==type_list[name_list.find("a")]:
    RAM[name_list.find("a")]=RAM[name_list.find("b")]

このようにname_list.find(...)がたくさん出てくるコードになります。

メモリ解放(変数削除)

name_list.find(削除したい変数名)が最後じゃない場合、最後の値と入れ替えて最後を消すとこでRAMの使用量を最小限にしています。

if len(name_list)>name_list.find(...):
    RAM[name_list.find(...)]=RAM[-1]
    type_list[name_list.find(...)]=type_list[-1]
    name_list[name_list.find(...)]=name_list[-1]
RAM.pop(-1)
name_list.pop(-1)
type_list.pop(-1)

各関数の返り値

scratchには関数(定義ブロック)の返り値という概念が存在しないのでどうにかしないといけません。
関数の引数の最後に「返り値を保存する変数の名前」を用意することで返り値用の変数も必要なくなりました。

def add(arg1,arg2,return_name):
    RAM[name_list.find(return_name)]=arg1+arg2

必要な機能の実装

scratchには高水準言語を処理するのには機能が物足りません。
とくに繰り返し、文字列関係は機能が少ないので自分で実装します。

substring

文字列のi番目からj番目の部分を切り取る、部分文字列です。
仕組みは簡単で

def substring(string,i,j,return_name):
    RAM[name_list.find(return_name)]=""
    counter=i
    for _ in range(j-i+1):
        RAM[name_list.find(return_name)]+=string[counter]
        counter+=1

counterをi~jにしてstringのcounter番目の文字を足していくという実装をしました。

str.find

文字列から文字、文字列を探しインデックスを返す関数です。
これもsubstringと同じようにループで探したい文字が来たらcounterをreturnするだけです。
pythonコードは省きます。

is_num is_string is_variable

与えられた文字列が数字、文字列、変数名かどうかを判別します。
正規表現がないので大変なことになっていますが、各文字を取り出して条件分岐しています。
variableは特に大変で最初は数字や記号NGで__はシステムで使われていて、、、
などこだわると限りがないのである程度判別できるようにしました。

実際の流れ

実際にどのように場合分けされて処理されていくか説明します。
その前に適当な命名すぎるのでリファレンスを載せておきます。

• eval
  • 式・評価のこと
  • =()+-*/%などの処理にあたる
• comp
  • 比較のこと
  • <>==not<=>=orなどの処理

各行単位で(compile_line)

• main.cppの指定した行を実行する関数
• (main.cppの長さ)回繰り返します
• ifやwhileなどでも呼び出されます

1. 変数定義

TYPES={int,string,bool}　が行の最初に来ていてその次に半角スペース、変数名なら変数を定義します。
また、"["が含まれる場合、配列の定義として分岐される。
具体的にはA[B]の正規表現でA+"["+i+"]"という名前の変数をB回定義します。
疑似的に配列が宣言できます。

2. cout/cin

coutとcinは処理の仕方が似ているのでほとんどコピペで実装できました。
<<(cinなら>>)ごとに要素を区切りその区切られたものを出力(入力してそれに代入)します。
正規表現がscratchにないので大変なことになっているが、大まかなコードを示すと、

if (line[counter]=="<" and line[counter+1]=="<") or line[counter]==";":
    output(newline)
    newline=""
else:
    newline=newline+line[counter]
couter+=1

3. eval

いままでの処理ではなかった場合文以外でも頻繁に用いられるのでevalを呼び出します。
evalの中身は

• 関数の引数の処理
• 関数の呼び出し
• 代入処理
  となっています。
  func1(func2(a),"2",3)のようなものは以下の手順で分解されます。

1. 最初の状態

   eval(value='func1(func2(a),"2",3)',id=1,return=None)
   

2. 引数のeval

   eval(value='func1(func2(a),"2",b)',id=1,return=None)
       eval(value='func2(a)',id=2,return=func1.arg1)
       eval(value='"2"',id=2,return=func1.arg2)
       eval(value='b',id=2,return=func1.arg3)
   

3. 引数の中の関数や値のeval

   eval(value='func1(func2(a),"2",3)',id=1,return=None)
       eval(value='func2(a)',id=2,return=func1.arg1)
           eval(value='a',id=3,return=func2.arg1)
               eval(value='5',id=4,return=a.value)
       eval(value='"2"',id=2,return=func1.arg2)
       eval(value='b',id=2,return=func1.arg3)
           eval(value='3',id=3,return=b.value)
   

4. それを繰り返して得られた値の処理
   処理されていくと最終的に何かしらの値になるのでそれがどんどんさかのぼって関数の引数となり関数が呼び出されます。

eval(value='func1(func2(a),"2",3)',id=1,return=None)
    func2.arg1=5
    func1.arg1=func2.return
    func1.arg2="2"
    func1.arg3=3

このようにevalの中でevalが呼び出されるのでevalの引数にidが付けられていて、idから深さがわかるようになっています。

これから具体的にevalがどう処理するかを説明します。

文節単位で(eval)

先ほど示した例のように、入れ子関係がとても複雑になる代わりにeval関数自体はだいぶ簡略化されました。
ですが簡略化されたといってもある程度の処理が必要なのでこれから簡単に説明します。

1. 文字列

与えられたもの(value)の両端の文字が「"」ならstringなので「"」を除いたもの(本体部分)を返します。

2. 関数

()を含むなら関数呼び出しを行います。
引数に対してid=id+1でevalされます(＝入れ子では子にあたる部分で引数を処理します)
returnに関数を呼び出した結果を代入します。

3. 代入

=を含み、==ではないとき「左の名前の変数」に「右をevalしたreturn」を代入します。

4. 比較

<>==<=>=andorなどの場合左と右の比較結果の0,1をretunに代入します。
代入の処理を何種類も用意しただけです。
evalの中では比較の文字があるか探してあればそれの前後で分けてそれぞれevalした結果をcompした結果をreturnします。

for count in range(len(COMP)):
    if value in COMP[cout]:
        comp_count=value.find(COMP[count])
        value1=value[0:comp_count-1]
        value2=value[comp_count+len(COMP):-1]
        comparator(id,value1,value2,COMP[count],return)

5. 演算

+-*/%の演算をします。
比較とほとんど同じです。
+など一文字しかないのでその分処理が少し楽になっています。
pythonコードは省略します。

6. 数字、変数

もじ数字ならそれをそのまま返します。
変数ならその中身を参照し、それを返します。

7. 配列

配列の場合、配列そのものが呼び出されたら0番目のアドレスを返し、場所指定がある場合その値を返します。

まとめ

関数名にコンパイラと書かれているのにインタプリンタでごめんなさい！！！
中間言語を生成してもう一度それを処理する仕組みを作るのはさすがに骨が折れるだけじゃ済みそうになかったので許してください。
関数やclassなどは実装難易度がものすごく高いので今回は実装できませんでしたが、機会があれば完全再現したいです。