西尾泰和のはてなダイアリー

■文字列の解析

プログラミング言語の処理系は、文字列として与えられたソースコードから意味を汲み取る必要があります。例えば"int x = 1234;"という文字列から、"1234"の部分が整数を意味しているということを理解する必要があります。

どうすればそのようなことができるでしょうか？

最初の一歩として"ab12cd"という文字列を受け取ると"12"を返す関数を作ることを考えてみましょう。

どうすればそのような関数を作れるでしょうか？

素朴に1文字ずつループ

まずはやりたいことをもっと明確に言語化してみましょう。やりたいことは「文字列を頭から1文字ずつ見ていって、0〜9の文字が続いている範囲を取り出したい」です

最初の文字が「0〜9の文字」でなかったら？その時は特に何もせずに次の文字を見れば良い。

次の文字も「0〜9の文字」でなかったら？その時も特に何もせずに次の文字を見れば良い。

次の文字が「0〜9の文字」だったら？これは結果として返すべき文字列の一部ですね。だけどまだreturnしてはいけません。だって次の文字の「0〜9の文字」かもしれませんから。と言うことは「後で結果として返すもの」を溜めておく必要がありますね。resultという名前で呼ぶことにします。

次の文字も「0〜9の文字」だったら？これも結果として返すべき文字列の一部です。これも溜めておく必要があります。

その次の文字が「0〜9の文字」でなかったら？ここでついに「0〜9の文字が続いている範囲」が終わりました！溜めておいた結果を返しましょう。

でも、「文字が『0〜9の文字』でない」という条件は「0〜9の文字が続いている範囲」の前と後と両方で使われていますね。「文字が『0〜9の文字』でない」という条件だけではどう行動するべきかが決まらないわけです。そこで「0〜9の文字が続いている範囲」が見つかったか、まだ見つかっていないのかを条件に含めることにします。これはis_foundという名前で呼ぶことにします。

こういう考え方で作られたPythonのコードが以下になります。

def find_int(string):
    result = ""
    is_found = False
    for char in string:
        print 'char=%r, result=%r, is_found=%r' % (char, result, is_found)
        if char in '0123456789':
            result += char
            is_found = True
        elif is_found:
            return result

    return ''


print find_int("ab12cd")

実行すると次のようになります。

char='a', result='', is_found=False
char='b', result='', is_found=False
char='1', result='', is_found=False
char='2', result='1', is_found=True
char='c', result='12', is_found=True
12

---

拙著「コーディングを支える技術」の読者から頂いた質問など対して、こんな感じで補足記事を書いて行きたいと思っています。質問・感想はおきがねなくどうぞ。

この解説は拙著の第3章と第4章の間に新しい章として入るのが適当かなと思います。その章のこの後の話の流れとしては

• is_foundってのが1個あるだけならまだしも、もっと複雑になると分けがわからなくなる、どうしよう。(状態遷移図の導入)
• 正規表現を使うと楽ちん
• ネストしたカッコを正規表現で切り出せるか？(正規言語, 文脈自由言語)
• どうやる？(再帰下降パーサ, yacc)
• どう表現する？(BNF)

という感じかな。

拙著に関する他のエントリーは「「コーディングを支える技術」著者公式ページ」からたどれるようにします。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 23:28

■トレイトを勉強していたらクラスの定義の食い違いに気づいた話

以前自分が書いた記事Scalaのtraitはmixinか？を元に、トレイトに関する補足記事を書こうとして「そうだ、どうせならば元論文の記述とも照らしあわせたほうがよいな」と「Traits: A Mechanism for Fine-grained Reuse」を読んだ。そこで気づいたのだけども、この件に関して意見が咬み合わないことがあるのは、そもそも「クラス」の定義に食い違いがあるせいではないか？

「Traits: A Mechanism for Fine-grained Reuse」での定義ではクラスとは「空クラスnil」もしくは「属性の集合と、メソッドの集合と、親クラス」と定義されている*1

で、トレイトとは「メソッドの集合」と定義されている*2

これがどういうことかというと、トレイトなどから作られたクラスは「自分を構成するのにどういうトレイトが使われたか」という情報を持たないってことなんだ。なのでsuperはトレイトに対して何も特別な挙動をしない。クラスの中からsuperした際にはusesしてるトレイトのことは考えないし、トレイトのメソッドからusesした時はそのメソッドが元々トレイトの中にあったという情報とはまったく無関係に「そのトレイトがいまusesされているクラス」の親クラスを指すわけだ。

僕のクラスのメンタルモデルはPythonに慣れているので「属性の集合と、メソッドの集合と、複数の親クラスへの参照」になっていて、それがトレイトを学んだ際に「属性の集合と、メソッドの集合と、1個の親クラスへの参照と、0個以上のトレイトへの参照」へと更新されたのだけども、それはトレイトを提案した人たちの定義とは食い違っていたということだ。

この辺りの話は以前id:sumimさんがブログに書かれていたように思うけども、「平坦化」とかで検索しても見つけられず…。

追記: あった： Scalaのトレイトは実はトレイトじゃなくただのミクスイン - Smalltalkのtは小文字です 「リニア化」と「フラット化」だった。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 18:40

■下書きの下書き

ブログで書籍の改訂版の下書きを書く、と言ったものの、それはそれで時間がかかるので下書きの下書き

文字列の解析(文法の章の次に挿入)

• 空白を読み飛ばしてaaaaを見つける
• 123.456のようなパターンの文字列を切り出すには
• まずforで書いてみる(使う言語はJSがいいかな)
• 状態遷移図
• 正規表現を使うと1行、すばらしい！
• 正規言語のフォーマルな定義
• 正規表現は万能ではない、正規言語でない例、対応したカッコ
• 文脈自由言語、BNF、yacc
• (PEGとかPackrat Parserの話はさすがに深追いし過ぎかな…？)
• (コラム)バッカスとナウア

ツイートする

Permalink | コメント(0) | トラックバック(0) | 03:32

■何をどう学ぶか？２：三大入力方法

先日の「何をどう学ぶか？」では、抽象的な知識を得るために具体的な知識から育てる方法について書きました。ではその具体的な知識はどうすれば効率よく入力できるのか？それに答えるのがこの第２章です。

拙著「コーディングを支える技術」では、余白にコラムの形で散らばって書かれています。ただ、書いた後で「写経」というテクニックが、言葉の意味に引きずられて予想以上に誤解されていることがわかり、字数の制限が厳しく言葉足らずなせいで誤解を助長するのではと不安になったのでスライドで補足することにしました。

ツイートする

Permalink | コメント(0) | トラックバック(0) | 22:31

■FPGAでライフゲームを作りました

動画の内容

• ランダムに初期化(see 線形帰還シフトレジスタ - Wikipedia)
• しばらく実行(高速モード：1ステップ3msec。VGA60Hzの画面の更新が17msecなので画面1回更新されるごとに5ステップ進んでいる計算)
• 画面をクリア、低速モード(256倍遅い)に移行
• Rペントミノを配置するボタンを押す
• しばらく走らせる
• 高速モードに変える

実装

• 読み書き用のアドレスをインクリメントする
• 2行+3マス文の323bitのシフトレジスタに読んだデータをpushする(see シフトレジスタ - Wikipedia)
• シフトレジスタの0, 1, 2, 160, 161, 162, 320, 321, 322の9ビットを束ねてアドレスとし、ライフゲームのルールがハードコードされた512bitのROMから1bit読む
• 読んだ値をVRAMに書き込む

各1クロックでできるかな〜と思ったけども、画面が流れるバグ(おそらくアドレス計算が間に合わなくて1つずれたところに書き込んだと思われる)が起きたので今は各2クロックで動かしている。

なので今は 1ピクセルあたり8クロック * 160x120ピクセル / 50MHz で画面1回更新するのに3msecということになる。頑張ればもっと縮む可能性がある。

消費したリソースは、ロジックエレメントが459個(3%)、メモリが57912bit(11%)とのこと。あと9倍くらい余裕があるから、解像度を2倍にしてピクセル数を4倍にするくらい行けそうだけど、この問題をどうやって解決するか： DE0でFPGAのチップ内蔵RAMをVRAMに使おうとしたら上手く行かなかった日記

ソースコード

Verilog HDL素人が書いたソースコードはこちら： https://github.com/nishio/fpga/blob/master/lifegame.v

ちなみにさっき知ったんだけど、Verilog HDLにもfor文があるみたいですよ。（えっ

追記

さすがに酷いので単純なシフトレジスタはfor文を使って書き換えました。512行のルールテーブルは何とかならないかな。

追記

シフトレジスタの実装について、こんなことしなくても

for(i = 0; i < 322; i = i + 1) begin
	buffer[i + 1] <= buffer[i];
end

この1行でいいじゃん、という指摘を頂きました(thanks @natutan!)

buffer[1:322] <= buffer[0:321];

たしかに…それができることは知っていたのになぜ思いつかなかったか…。たぶん僕の脳の中ではまだC言語の配列みたいなイメージで捉えられているのだろうなぁ。だから「要素が323個ある配列」を1個ずらすことが「代入文1つでできる」という発想を思いつくことができなかった。

ツイートする

Permalink | コメント(4) | トラックバック(0) | 02:09