npm publishしてみた

npmにmb_strwidthというpackageをpublishしました。
PHPmb_strwidth() と同じ動きをする関数です。
https://www.npmjs.com/package/@demouth/mb_strwidth
https://github.com/demouth/mb_strwidth

console.log(mb_strwidth('𩸽定食食べたい😭')); // 15
// PHP 7.3.28
var_dump(mb_strwidth('𩸽定食食べたい😭')); // int(15)

動機

npmのpackageの公開ってどういう感じなのか知りたかったので、昔書いたgistを少し書き換えて公開してみました。 別にmb_strwidth()をJSで使いたかった訳ではないです。

参考にしたのはこちらの記事で、ほぼこの通りにやっただけです。 https://zenn.dev/manycicadas/books/b6f2d99b5208e9

以上。

Writing A Compiler In Goを完走した

去年の夏に書籍「Writing A Compiler In Go」を購入して以降、時間を見つけてコツコツ進めていたのですが、先日ようやく完走することができました。

基本的には本に書いてあることを写経しながら進めるだけでコンパイラが完成してしまうので、内容をしっかり理解していなくても完走はできてしまいます。なので、記憶の定着を目的にこの本で何をやったのかブログに残しておこうと思います。

目次

「Writing A Compiler In Go」とは

f:id:y_d:20220110173925p:plain

「Writing A Compiler In Go」という本ですが、これの前作にあたる「Writing An Interpreter In Go」の日本語訳が「Go言語でつくるインタプリタ」としてオライリーから出ているので、ご存じある方も多いかと思います。 私は数年前に「Go言語でつくるインタプリタ」を読んでいて、続編の日本語訳が出版されるのを待っていたのですが、いつまで経っても発売されないので昨年英語版を購入しました。

「Writing A Compiler In Go」を超簡単に説明すると「写経しながら軽量な自作コンパイラを作ってみよう」という本です。 前作「Writing An Interpreter In Go」で実装したインタプリタを書き換えることで、Virtual Machine(VM)上で動作するようになります。

コンパイラを作るというと、想像もつかないくらい難しいことをやるんじゃないかと身構えてしまいますが、この本は小さなテストを先に書いてから小さな実装を書き、それを何度も積み重ねながら進んでいきます。そして気がついた頃にはいつの間にかVMと、そのVM用のバイトコードを生成するコンパイラを完成している、という感じで意外とつまずくことなく最後まで辿り着くことができてしまいます。

前作「Writing An Interpreter In Go」でやったこと

その前に前作「Writing An Interpreter In Go」でやったことを振り返っておこうと思います。 前作では「Monkey言語」というJS風のオリジナル言語を定義し、そのインタプリタを実装しました。

Monkey言語はこんな感じの言語です。

// Monkey言語の一例
let people = [{"name": "Anna", "age": 24}, {"name": "Bob", "age": 99}];
let getName = fn(person) { person["name"]; };
getName(people[0]); // => "Anna"
getName(people[1]); // => "Bob"

入力となるMonkey言語に対して、字句解析、抽象構文木解析、評価を順番にしていくことでMonkey言語を実行します。

下図のように最初はただの文字列として扱われていたプログラムが順に処理されていくことで実行結果を得ることができます。 図では「10 + 2;」を順に評価して、12という結果を得ています。

f:id:y_d:20220110174141p:plain

ここまでが前作「Writing An Interpreter In Go」でやったことのおおまかな流れです。

つぎに字句解析と抽象構文木解析についても軽く復習します。

字句解析 Laxer

字句解析では文字を1文字ずつ読み進めていき、意味のあるところで区切っていきます。 例えば「let number = 2;」だったら「l」「e」「t」…という感じで1文字ずつ読み進め、行頭から「let」という字句を見つけることで、これは「let」トークンだ、と識別します。

f:id:y_d:20220110174156p:plain

構文木解析 Parser

先ほど字句解析にかけたものをもとに、今度は構文木解析します。 意味のある形にまとめられ、ツリー状のデータ構造になります。

ちなみに既存のパーサージェネレータは使用せず、自前のパーサー(Pratt構文解析器)を実装します。

f:id:y_d:20220110174207p:plain

評価 Eval

Tree-Walkingインタプリタを実装します。 この実装方式では、抽象構文木を辿り、順に評価していきます。

難しそうな感じがしますが、前処理の構文木解析によってすでにツリー状なっているので、あとは実行するだけです。意外に単純。

f:id:y_d:20220110174217p:plain

「Writing A Compiler In Go」で何をやるか

ここまでが前作「Writing An Interpreter In Go」でやったことでした。

そして、これを踏まえて「Writing A Compiler In Go」ではインタプリタを下図のように書き換えます(赤色の部分)。

f:id:y_d:20220110174233p:plain

Tree-WalkingインタプリタではASTをたどりながら評価していきましたが、今回この部分を書き換え、コンパイラVMを追加します。 この変更によりASTから直接評価するのではなく、コンパイラが事前にASTをたどりバイトコード(中間表現)を生成し、そのバイトコードVMが順に評価することになります。実装方式は変わりますが、得られる結果は書き換える前と同じです。 ※今回実装するVMインタプリタの実装方式の一種です。JITコンパイラは実装しません。

では、なぜ既に実装ずみのインタプリタをわざわざコンパイラVMで実装し直すのか、その理由について本書籍では「modular」と「performance」をあげていますが、主な魅力は「performance」と説明しています。仮想マシンを構築することで、より少ない命令で表現できるようになり、結果としてコード密度が高まり、実行速度が向上するということだそうです。 実際書籍の一番最後でフィボナッチ数列ベンチマークを実行し3倍速くなることを確認することになります。

なお、今回オリジナルのMonkey言語をVM方式に書き換えるわけですが、実在する多くのプログラミング言語もライフタイムの中で実行方式をVM方式に書き換えるているらしく、Rubyもその一つとして説明されています。

Rubyがまさにこの例だ。バージョン1.8以下ではtree-walkingインタプリタで、ASTをたどりながら実行する。しかし、バージョン1.9から仮想マシンアーキテクチャに移行した。

— Go言語で作るインタプリタ - 3章 評価

それでは作成ずみのインタプリタをどのように書き換えるか説明していこうと思いますが、その前にいくつか説明をしておくことがあります。

スタックマシンとバイトコードとデコード

今回実装するVMはスタックマシンです。 スタックは後入れ先出し(Last In First Out)のデータ構造で、これを使って演算します。 例えば1 + 2を実行する場合は  ・「1」をスタックにプッシュ  ・「2」をスタックにプッシュ  ・2つポップして加算したものをプッシュする と順に行うことで、スタックのトップに加算の結果が残り、結果が「3」だということが分かります。

f:id:y_d:20220110174400p:plain

f:id:y_d:20220110174350p:plain

これを実行するバイトコードは以下のように定義されたりします(説明用に単純化した架空のバイトコードで、実際に使われるものではありません)。

PUSH 1
PUSH 2
ADD

しかし実際は上記のようなマルチバイトの文字列ではなく、以下のようなバイナリ表現に変換したバイトコードVMに渡される事になります。

00000001 00000001
00000001 00000010
00000010

これは下図のような感じでOpecodeとOperandをバイトコードに変換したものです。 ちなみにオペコードの長さが1バイトなのでバイトコードと呼ばれるらしいです。

f:id:y_d:20220110174423p:plain

ということで、「00000001 00000001 00000001 00000010 00000010」という謎の数値の羅列がVMに渡されることになりますが、VMはこの数値を受け取ってどのように解釈するのでしょうか。

VMバイトコードに対して「デコード」「実行」のサイクルをループします。 バイトコードは以下のように評価されます。

f:id:y_d:20220110174440p:plain

PUSHはOperand(つまり引数)が1つあるので、PUSHの隣のバイトコードも読み取ります。ここまででバイトコードが「PUSH 1」を意味することが分かり、実際にスタックに1をPUSHします。

f:id:y_d:20220110174453p:plain

そして、次のOpcodeに処理を進めます。 こんな感じでVMバイトコードを読み取ることで、次に何をすれば良いかわかるので、それに応じて順次処理を行うことができます。これが大まかな仕組みです。

f:id:y_d:20220110174503p:plain

コンパイラVM

上記で概念的な説明をしてきましたが、実際に今回作成するコンパイラVMが何をするか、もう少し具体的に説明します。

定数領域とglobal変数が存在しています。

本書籍で実装するmonkey言語のコンパイラで、

let three = 1 + 2;

コンパイルすると、定数領域には「1」と「2」が定義された上で、次のようなInstructionが生成されます。

# 定数の0番目をスタックにロードする
OpConstant 0

# 定数の1番目をスタックにロードする
OpConstant 1

# スタックの上から1番目と2番目を足した結果をスタックに積む
OpAdd

# グローバル変数に格納する(let文)
OpSetGlobal 0

# スタックの一番上をポップする(let文が終わるので)
OpPop

VMが実行される前の状態は、下記のようにコンパイラが生成した定数が存在するだけです。 f:id:y_d:20220110174527p:plain

OpConstantが実行されると、オペランド(この例だと0番と1番)で指定された定数をstackにpushします。 f:id:y_d:20220110174545p:plain

OpAddでstackの上2つをpopして、加算した結果をpushします。 f:id:y_d:20220110174559p:plain

OpSetGlobalでstackのトップをglobal領域にセットします。何番目にセットするかはオペランドで指定されます。 f:id:y_d:20220110174611p:plain

OpPopでstackから1つpopします。 f:id:y_d:20220110174619p:plain

終わりに

条件分岐、関数呼び出し、コールフレームの実装 、クロージャあたりについても書こうと思いましたが、本とソースを読んだ方が速いので、この辺でやめておこうと思います。

非常にシンプルなコンパイラではありますが、私のような凡人プログラマにも実装できました。 興味がある方はぜひ「Writing A Compiler In Go」を読んでみてください。 洋書ですが公式サイトから購入するとHTML版をダウンロードできるので、DeepLのChrome Extensionなどを使えば普通に読めちゃうんじゃないかと思います。

以上です。

Goのクリーンアーキテクチャ実装 go-clean-arch を読む

Go言語で実装されたクリーンアーキテクチャの実装例を見つけたので、ソースを読みつつなんとなくクラス図とER図を書いてみました。

github.com

クラス図

  • 図の中にメモ書きしてありますが、ほぼ全てのオブジェクトを main で生成しています。
  • Model は Article と Author の2つですが、 Usecase や Handler の名前は ArticleXxxx になっています。関心の対象が Article だから?

f:id:y_d:20210727230244p:plain
クラス図

ER図

  • DB上には article と author 以外にいくつかテーブルがありましたが、実装上はこの2つのテーブルだけを使っているようでした。
  • article が author_id を保持するようになっています。

f:id:y_d:20210727230241p:plain
ER図

JOINについて気になった

複数の article と、それに紐付く author をセットで取得する部分の実装が気になりました。

素朴に考えると、 article と author の2テーブルをJOINして1回のSQL発行でデータ取得しそうな気がしますが、この go-clean-arch では、

  1. article を複数取得 (ArticleRepositoryを使用)
  2. article 1件1件をループで回す
  3. ループの中で article 1件に対応する author を1件取得 (AuthorRepositoryを使用)

という感じでループの中で何度もSQLを発行している実装となっていて、パフォーマンスの考慮はなさそうでした。
この辺はサンプル実装だからですかね。
RDBを使った場合、1テーブル1モデルにするのは無理がある?

以上です。