読者です 読者をやめる 読者になる 読者になる

「PHPに型推論を実装する〜入門編〜」という題でPHPカンファレンス福岡2016で話してきた

PHPカンファレンス福岡2016で型推論器ってどんな感じなのという話をしました。PHPカンファレンス福岡は去年も登壇したんですが今年は弊社もスポンサードしつつの登壇です。

参加者や運営スタッフの皆さんの対応含めて心地良い雰囲気だったので、ああ参加して良かったなと自然と思えるような素晴らしいイベントでした。参加者や運営のスタッフの皆さんお疲れ様でした!

JavaScript(ES2015)でvarやletを使う必要はほぼ無い

ES2015でvarやletを使う場面はほとんど無いので、まずconstを使う。constだとダメな場合にはletを使う。

背景

ES2015では、変数を宣言するための文法としてconstとletが導入された。

const foo = 'foo';
let bar = 'bar';

constは再代入できない変数を宣言できる。letは再代入できる変数を宣言できる。

const foo = 'foo';
foo = 'hoge'; // ERROR

let bar = 'bar';
bar = 'hoge'; // OK

あれ、じゃあvarとletは同じなの?っていうとそうではなく、letやconstはvarとは違って、関数スコープよりも細かなブロック単位のスコープを提供する。例えばconstやletを使うと、if文やfor文などのブロック中でのみ有効な変数を宣言できる。

で、プロジェクトにES2015を導入すると、「お、varじゃなくてlet使えばええんやな!」と言わんばかりにletだけを使う人を見かけるんだけど、実際にはletもほとんど使う必要なくて、多くの場合はconstで問題ない。また、他人が書いたソースコードの中でletを見ると、「これ後で再代入されるん?」って一瞬身構えるので、再代入の必要がないならconstを使う方が可読性も良くなる。

ES2015になって変数の文法が増えたわけだけど、開発者はまずconstを使って、再代入が必要ならletを使って、letも使えない特殊な事情がある場合のみvarを使う、というようにするといい。

varは別に非推奨になったわけではないので普通に使えるんだけど、プロジェクトで機械的にvarを使わせたくない場合には、ESLintでno-varを有効にする。

Airbnbが公開しているES6に対応したJavaScriptコーディング規約においても、まずconstを使うこと、varは避けることが書かれている。

追記: よくよく調べてみると、ESLintには再代入しないletに警告を出すprefer-constがあった。より厳格にしたい場合はこのprefer-constを有効にする。

まとめ

ES2015では、varやletを使う必要のある場面はそれほどない。変数の宣言にはconstを使う。再代入が必要な場合にのみlet使う。

factorでズンドコキヨシを書いてみた

連鎖性言語のfactorで今流行り(?)のズンドコキヨシ書いてみた。連鎖性言語って何?っていう方はここの説明を見てほしい。

IN: .
USING: random io kernel sequences math ;

"" [ dup "ズンズンズンズンドコ" tail? not ]
[ { "ズン" "ドコ" } random append ] while
"キ・ヨ・シ!" append write

実行する。

$ factor zundoko.factor
ズンドコドコズンズンズンズンドコキ・ヨ・シ!

昔触ってたfactorのこと完全に忘れててこれ書くのになんやかんやで1時間ぐらいかかったけど、たまにfactor書くとやっぱ面白い。最近の連鎖性言語をちょろっと調べてみたら、今はkittenというイケてる感じの関数型連鎖性言語も登場してるみたい。暇があったらまたこういうの触っていきたい。

JavaScriptでのDOM操作は重いのかという話とForced Synchronous Layoutについて

2015年にもなるのにJavaScriptでのDOM操作のパフォーマンスについて書く。ウェブページにインタラクションを持たせたい時に、JavaScriptでDOM操作を行うことがよくある。このDOM操作のパフォーマンスについて、よく聞く意見を大別すると次の2つがある。

  • JavaScriptによるDOM操作は重たい
  • レンダリングが重いだけで、DOM操作そのものはそれほど重たくない

JavaScriptでオブジェクトのプロパティを操作したりする単体の処理は通常1ミリ秒もかからないが、DOM操作をするとレンダリングが完了するまでに数十ミリ秒程度かかったりする場合がある。1番目のDOM操作が重たいと言っている人は経験則的にそう言っていることが多い。

レンダリングの仕組みを知っている人は2番目の意見を言うが、重箱の隅をつつくような話をするとこれも必ずしも正しいわけではない。DOM操作するコードによっては、JavaScriptの実行そのものをブロックするケースもあるからだ。この記事ではその辺りの事情についておさらい的に説明する。

DOM操作するとそもそも何が起こるのか

現在見ているウェブページのドキュメントのDOMツリーに属するDOM要素を操作をすると、JavaScriptの実行が終わってからブラウザのレンダリング処理が行われる。具体的にはWebkit系のレンダリングエンジンだと次の図のようになる。

f:id:anatoo:20151013210539p:plain

ScriptingではJavaScriptの実行が行われる。DOM操作の処理もここに含まれる。

Calculate Styleでは、更新されたDOM要素ごとのスタイルが再計算される。例えば、DOM要素を生成してDOMツリーに追加すると、その影響で当たるスタイルを更新しないといけない要素が出てくるので、それらのDOM要素に当たるスタイルがCSSセレクタのマッチング処理とともに再計算される。

Layoutでは、計算されたDOM要素のスタイルを元に要素のレイアウトの計算を行う。いわゆるリフローと呼ばれるものはこれ。Firefoxだとリフローと呼ばれる。

Paintでは要素をレイヤごとにラスタライズする。Composite Layersではラスタライズした各レイヤを1枚に合成して最終的なレンダリング結果を生成する。

HTML5アプリでのインタラクションやアニメーションのレンダリングのパフォーマンス改善というのは、このDOM操作した後のこの一連の実行パスをどのようにして最適化するかという話である。

例えば、iOSやAndroidなどのモバイル端末で60FPSのアニメーションを達成しようとすると、LayoutやPaintなどの処理をやってたら速度的にちょっときつくなるのでなるべく最後のComposite Layersだけが実行されるようなコードを記述したりする。

DOM操作に伴うレンダリングの処理は、JavaScriptの実行そのものを遅くするわけではないので、そういう意味では後続するレンダリングが重いだけでDOM操作そのものは大して重くない、というのはおおむね正解である。実際ドキュメントのDOMツリーに属していないDOM要素を操作してもこれらのレンダリング処理は行われない。

ただし、JavaScriptのコードの書き方によってはForced Synchronous Layoutを引き起こして、JavaScriptの実行そのものをブロックする場合がある。

Forced Synchronous Layout is 何

Forced Synchronous Layoutとは、JavaScriptと同期する形で実行されるレイアウト計算処理のことである。通常このレイアウト計算は、JavaScriptの実行が終わってから初めて行われるので、JavaScriptの実行を遅くしたりするわけではない。しかしForced Synchronous LayoutではJavaScriptの実行中に同期的に処理されるので、JavaScriptの実行パフォーマンスを劣化させることがある。

DOM APIにはレイアウト情報を参照するメソッドやプロパティがいくつかある。具体的には、offsetHeightプロパティやoffsetWidthプロパティやgetBoundingClientRect()メソッド等がある。Forced Synchronous Layoutは、ドキュメントのDOMツリー内でDOM操作を行った後、そのDOM要素のレイアウト情報を参照するコードを書くと起こる。

例えば、DOM要素を生成してbody要素に追加する次のようなコードを見てみよう。

var div = document.createElement('div');
div.innerHTML = 'hogehoge';

document.body.appendChild(div);

このコードでは、JavaScriptの実行が終わってから初めてレイアウト計算が行われる。対して、次のコードではForced Synchronous Layoutが発生する。

var div = document.createElement('div');
div.innerHTML = 'hogehoge';

document.body.appendChild(div);

// ここでForced Synchronous Layoutが起こる 
console.log(div.offsetHeight);

Webkitなどのレンダリングエンジンでは、JavaScriptによるDOM操作が行われてもすぐにレイアウト計算を行うのではなくJavaScriptの実行が一旦終わってから行うが、DOM操作を行った後にgetBoundingClientRect()やoffsetHeightなどのプロパティを参照すると、正しいレイアウト情報を返すためにレンダリングエンジンはその場でレイアウト計算を行う。

Forced Synchronous Layoutが起こっているかどうかは、ChromeのウェブインスペクタのTimelineでプロファイルを取ればわかる。

f:id:anatoo:20151013222902p:plain
https://developers.google.com/web/tools/profile-performance/rendering-tools/forced-synchronous-layouts

Forced Synchronous Layoutが発生したからと言って即パフォーマンス上の問題が出るわけではないが、ループ内などでForced Synchronous Layoutを引き起こすと、JavaScript実行中にレイアウト計算が何度も繰り返し起こるのでJavaScriptのパフォーマンスが大幅に劣化する事がある。

まとめ

JavaScriptでのDOM操作自体は大して重くない。重く見えるのはDOM操作に伴うレンダリング処理がJavaScriptの実行後に行われるからである。ただし、DOM操作するコードがForced Synchronous Layoutを引き起こす場合にはJavaScriptの実行パフォーマンスを劣化させる原因になる。

PHPカンファレンス福岡2015で「PHPで学ぶ仮想マシン型正規表現エンジンの仕組み」という題で発表してきました #phpconfuk

f:id:anatoo:20150630111516j:plain

6/27に開催されたPHPカンファレンス福岡2015で「PHPで学ぶ仮想マシン型正規表現エンジンの仕組み」という題で発表してきました。

正規表現エンジンの実装は、大別するとDFA型とVM型の二種類あるのですが、今回のこの発表ではVM型の仕組みについて解説しました。

もともとこの話の元ネタは、数年前に読んだRegular Expression Matching: the Virtual Machine Approachという記事です。この記事を読んで、こんなに単純な仕組みで正規表現エンジンって実装できるのか!とちょっとした衝撃を受けて、その感動を伝えられればということで今回話しました。

ちょっと時間が足りず最後の方が早足になってしまって当日会場で話を聞いていた人にはわかりづらくなってしまいましたが、資料を一度ゆっくり見てもらえば多分理解できると思います。

PHPで学ぶ〜とか言いつつスライドにはPHPのコードは一行たりとも出てきませんが、スライド中で紹介している自分の記事の中ではPHPを使ってVMの実装をしています。

発表資料は以下になります。

セッションに参加していただいた皆さんありがとうございました。また、運営スタッフの皆さんや@cakephperさん @akase244さん @localdiskさんお疲れ様でした。

JavaScriptをプロトタイプベースのオブジェクト指向言語と言うべきではない

勘違いしている方も結構多いと思ったので、これの解説。

ウェブ上の記事を眺めていると、JavaScriptをプロトタイプベースのオブジェクト指向言語(以下OOPと書く)と説明している例がよく散見される。この書き方は間違ってはいないかもしれないが、もはや誤解を生むだけである。

そう言う理由には、ES6からはclass構文があるため、通常のクラスベースのOOPと一切何も変わらなくなっているからというのがある。だが最も大きな理由は、JavaScriptはプロトタイプベースのOOPの中でも異端であり、本来のプロトタイプベースのOOPとはあまり似ていないからである。

JavaScriptでは、new演算子を使ってオブジェクトを生成したり、prototypeオブジェクトを使ってオブジェクトのメソッドやプロパティを定義したりするが、他のプロトタイプベースのOOPではnew演算子は無いし、prototypeオブジェクトも無い。

この記事では、本来のプロトタイプベースのOOPがどういったものであり、JavaScriptとはどう違うのかを説明する。

JavaScriptの確認

まずは、JavaScriptでオブジェクトを定義・生成する方法を確認していく。

コンストラクタとして、まずは関数を定義する。

var MyObject = function(name) {
  this.name = name;
};

次に、定義した関数オブジェクトのprototypeプロパティにプロパティを定義することで、オブジェクトがインスタンス化された時のプロパティやメソッドを定義できる。

MyObject.prototype = {
  createGreeting: function() {
    return 'Hello, ' + this.name;
  }
};

オブジェクトをインスタンス化する際には、new演算子を使って生成する。

var obj = new MyObject('JavaScript');
obj.createGreeting(); // => 'Hello, JavaScript'が返る

さて、プロトタイプベースのOOPではこういったオブジェクトの定義や生成はどうやって行うのか。

プロトタイプベースのOOPでは?

純粋なプロトタイプベースのOOPでは、クラスやJavaScriptのprototypeオブジェクトのようなものは無い。新しいオブジェクトを作るには、new演算子によるインスタンス化ではなくオブジェクトの複製を作ることで自分が欲しいオブジェクトを作成していく。

ここでは、プロトタイプベースのOOPの例として、ioという言語で説明する。ioは純粋なプロトタイプベースのOOPだ。また、ioには制御構文用の文法が無く全てが(if文ですらも)メソッドである。

まずは、先ほどJavaScriptで書いたようなMyObjectをioで作ったのが以下だ。

// オブジェクトの複製を作る
MyObject := Object clone
// メソッドの定義
MyObject createGreeting := method("Hello, " .. self name)
// プロパティの定義
MyObject name := "Your Name"

ioの文法のほんの少し説明すると、:=演算子は変数を宣言する演算子である。また、JavaScriptではオブジェクトのプロパティのアクセスに"."演算子を使うが、ioでは単にスペースを使う*1。また、引数がない場合にはメソッド呼び出しに()は不要だ。

hoge := "hogehoge" // JSだとvar hoge = "hogehoge";になる
hoge size // JSだとhoge.sizeになる
hoge print // printメソッドの呼び出し

先ほどの例では、MyObjectというオブジェクトを作っているが、重要なことはこのMyObjectはすでに利用できる一個のオブジェクトだということだ。例えば、ここでcreateGreetingメソッドを呼び出せばそれはそのまま動作する。JavaScriptではこうはいかない。

MyObject createGreeting // "Hello, Your Name" が返る

ioでは新しくオブジェクトを作るときには、クラスをインスタンス化してオブジェクトを生成する代わりに、すでにあるオブジェクトを複製することでオブジェクトを生成する。

myobj := MyObject clone
myobj name = "io"
myobj createGreeting // => "Hello, io" が返る

さて、ioのやり方を見るとJavaScriptとはだいぶ違うことがわかる。ioなどのプロトタイプベースのOOPではオブジェクトの定義や継承や生成などの処理を全てcloneを通じて行えるので非常にシンプルだ。それに比べるとJavaScriptのprototypeオブジェクトを使うやり方は何かちぐはぐな印象を与えてくる。

GoFのデザインパターンの一つにオブジェクトの生成に関わるプロトタイプパターンというのがあるが、プロトタイプベースのOOPではこのデザインパターンを言語の設計レベルで全面的に採用することでnew演算子やクラスの存在を消してしまっている。

JavaScriptでは、プロトタイプ(ひな形)となるオブジェクトは関数オブジェクトのprototypeプロパティに代入したオブジェクトになるが、これは通常のオブジェクトとしてそのまま利用できるわけではないし、これはある意味クラスを表現するクラスオブジェクトのような形になっている。

ioではそういったオブジェクトは無くプロトタイプ(ひな形)となるのはそのオブジェクト自身である。ioではオブジェクトの複製を通じてのみ新しいオブジェクトを生成できる。

こうやって書いてみると、JavaScriptが通常のプロトタイプベースのOOPとどれほどかけ離れているかがわかる。JavaScriptはクラスを持たないためプロトタイプベースのOOPとして分類できるのかもしれないが、その仕組みを観察してみると、クラスベースとプロトタイプベースの合いの子のような妙な形になっている。

終わりに

個人的な意見になるが、JavaScriptをプロトタイプベースのOOPと言い切っている人は、プロトタイプベースのOOPがどういったものかを理解していない、もしくはioやSelfのような言語を触ったことがない人だろう。なぜならJavaScriptは何の留保も無しにプロトタイプベースと言い切るにはあまりに奇妙だからだ。何にせよ、ES6からはclass構文が追加されたので、JavaScriptをプロトタイプベースのOOPと言うのはもはや適切ではないだろう。

追記: ブックマークコメントへの返信

id:oscdis765 Even though ECMAScript includes syntax for class definitions, ECMAScript objects are not fundamentally class-based such as those in C++, Smalltalk, or Java.
http://b.hatena.ne.jp/entry/249961310/comment/oscdis765

id:otherworld インスタンス化に使うキーワードが違うだけで、プロトタイプチェーンを辿ってプロパティ/スロットを解決するというコンセプトは同じじゃ?? jsをクラスベースと呼ぶ方が無理がある
http://b.hatena.ne.jp/entry/249961310/comment/otherworld

この記事では、JavaScriptをクラスベースのOOPと呼ぶべきという主張をしているわけではないです。プロトタイプベースの、という枕詞を付けても説明として何の意味もないという話です。

*1:余談だがioではプロパティと言わずにスロットと呼ぶ

JavaScriptでパーサコンビネータのコンセプトを理解する(「正規表現だけに頼ってはいけない」の続き)

前回の記事の続き。前回は、正規表現が使えない時はパーサコンビネータを使ってみると良いということを書いた。

パーサコンビネータのためのライブラリは、以下のように各言語ごとにいくつかある。

各言語でいくつかあるのだが、正規表現と違ってパーサコンビネータには統一的な書き方があるわけではないし、ライブラリによって使い方も様々である。なので、今まで正規表現だけ使ってきた開発者がちょっと使ってみようと思っても、使い方がよくわからずに面食らってしまうことがある。

パーサコンビネータはテキストをパースするための非常に強力な仕組みだが、その背後にある考え方を理解しなければこれらのパーサコンビネータのライブラリを使う際の障害になるだろう。逆に言うと、それさえ理解できればどのライブラリでもそれほど苦労せずに使えるようになるだろう。

実は、単純なものであればパーサコンビネータを書くことはそれほど難しくない。この記事では、学習のためにJavaScriptで単純なパーサコンビネータを実際に作りつつ、パーサコンビネータのコンセプトを解説する。

関数としてのパーサ

パーサコンビネータでは、パーサを関数として扱うことが多い。そして、その関数をいくつも加工したり合成したりしていくことで自分が欲しいパーサを構築する。

パーサコンビネータの実装として有名なのが、関数型言語のHaskellのparsecである。パーサコンビネータはHaskellのような関数型言語でよく親しまれている。というのも、パーサを関数として扱うやり方が、関数を値として扱ったり、関数を引数に取る高階関数を作ったり、関数の合成をしたりということをよく行う関数型言語では親しみやすいからだろう。

パーサコンビネータでは、パーサを関数として扱っていくが、その関数はどのような入力と出力を取るのだろうか? どのようなパーサコンビネータのライブラリでも基本的にはパーサは以下のよう入力と出力をベースにしている。

  • 入力: パースする文字列、現在の読み取り位置
  • 出力: パースが成功したかどうか、パースされた結果、新しい読み取り位置

パーサとしての関数では、当然パースの対象となる文字列をパラメータとして取る。それと、現在どの位置の文字を読み取っているのかという情報も受け取る。

出力では、パーサは文字列のパーサに成功か失敗かを返す。パーサが想定している文字列を受け取れなかったら失敗を返す。パースが成功した場合には、パーサは文字列を解釈(パース)して様々な値を生成するので、パースされた結果を返す。また、どこまでパースし終わったかを伝えるために新しい読み取り位置も同時に返す。

実際にJavaScript風の擬似コードで書くと以下のようになる。

/**
 * @param {String} target パーサの対象となる文字列
 * @param {Number} position 現在の読み取り位置
 * @return {Array} 成功したかどうか、パース結果、新しい読み取り位置の3つの要素を持った配列
 */
function parse(target, position) {
  // ...

  // パース成功したかどうか
  var success = ...; 

  // パース結果(パース失敗の場合はエラー情報など)
  var result = ...; 

  // 新しい読み取り位置
  var newPosition = ...; 
  
  return [success, result, newPosition];
}

パーサコンビネータでは、この関数として定義したパーサを使ってどのように実装されていくのか? 見ていこう。

単純な文字列をパースするパーサを書く

まず初めに、一番簡単なパーサを書くところから始めていく。ここでは 'hoge'という文字列をパースするパーサを書いてみる。

function parseHoge(target, position) {
  if (target.substr(position, 4) === 'hoge') {
    // 成功
    return [true, 'hoge', position + 4];
  } else {
    // 失敗
    return [false, null, position];
  }
}

ごくごく単純なコードだと思う。targetの現在の位置(position)から、4文字読み込んで、それが'hoge'ならパースが成功を返す。そうでなければ失敗を返す。

このパーサを実行してみると以下の様な動作をする。

parseHoge('hoge', 0) // => [true, 'hoge', 4]を返す

parseHoge('ahoge', 1) // => [true, 'hoge', 5]を返す

parseHoge('aaa', 0) // => [false, null, 0]を返す

さて、このパーサは'hoge'という文字列しかパースできないので、汎用的ではない。なのでこれを一部変えて、文字列を受け取って先ほどのようなパーサを返す以下の様なtoken関数を定義する。こうすると単純な文字列のパーサを生成する関数として汎用化できる。

/**
 * 単純な文字列のパーサを生成する
 * 
 * @param {String} str
 * @return {Function} strのパーサ
 */
function token(str) {
  var len = str.length;

  return function(target, position) {
    if (target.substr(position, len) === str) {
      return [true, str, position + len];
    } else {
      return [false, null, position];
    }
  };
}

これも試してみよう。

token('foobar')('foobar', 0); // => [true, 'foobar', 6]を返す

token('foobar')('foobar', 1); // => [false, null, 1]を返す

token関数のおかげで、単純な文字列のパーサを簡単に生成できるようになった。

とはいえ、これだけでは単純な文字列をパースできるだけで、パーサコンビネータとしての利用価値はまだ無い。ここからどんどんパーサコンビネータを拡張していこう。

繰り返しを表現するパーサを作る

正規表現で、繰り返しの表現がある。例えば、/(hoge)*/という正規表現は0個以上の'hoge'という文字列にマッチする。ここでは、この繰り返しの処理をパーサコンビネータで実装してみる。

/(hoge)*/という正規表現をそのままパーサとして書くと以下のparseHogeMany()関数になる。

function parseHogeMany(target, position) {
  var result = [];

  for (;;) { 
    if (target.substr(position, 4) === 'hoge') {
      result.push('hoge');
      position += 4;
    } else {
      break;
    }
  }

  return [true, result, position];
}

このパーサも'hoge'という文字列の繰り返ししかパースできないので、これを汎用的にする。

パーサコンビネータでは、パーサを入力に受け取って加工したパーサを返す関数がよくある。ここでは、パーサを受け取ってその繰り返しのパーサを生成する以下のmany関数を書いた。

/**
 * パーサを受け取って、そのパーサの解釈できる文字列を
 * 繰り返した文字列を解釈できるパーサを生成する
 * 
 * @param {Function} parser
 * @return {Function}
 */
function many(parser) {
  return function(target, position) {
    var result = [];

    for (;;) { 
      var parsed = parser(target, position);
      // 受け取ったパーサが成功したら
      if (parsed[0]) {
        result.push(parsed[1]); // 結果を格納して
        position = parsed[2];   // 読み取り位置を更新する
      } else {
        break;
      }
    }

    return [true, result, position];
  }
}

ここで、今まで作った関数(token, many)を試してみよう。なんとなく雰囲気出てきたんじゃなかろうか?

many(token('hoge'))('hogehoge', 0); // => [true, ['hoge', 'hoge'], 8] を返す

many(token('hoge'))('', 0); // => [true, [], 0] を返す

many(token('foobar'))('foo', 0); // => [true, [], 0] を返す

選択を表現するパーサを作る

さらにこのパーサコンビネータの表現力を増やしていこう。

正規表現ではパイプを使って選択を表現できる。例えば、/(foo|bar)/という正規表現は、'foo'もしくは'bar'という文字列にマッチする。

まずは単純に書き下すと以下のようになる。

function parseFooOrBar(target, position) {
  if (target.substr(position, 3) === 'foo') {
    return [true, 'bar', position + 3];
  }

  if (target.substr(position, 3) === 'bar') {
    return [true, 'bar', position + 3];
  }

  return [false, null, position];
}

これも汎用性が無いので、汎用性を持たせて書き直したchoice関数が以下になる。many関数と同様に、このchoice関数も入力としてパーサを受けとって新しい性質を持ったパーサを生成する。

/**
 * @param {Array} parsers... パーサの配列
 * @return {Function} 選択を表現するパーサ
 */
function choice(/* parsers... */) {
  var parsers = arguments;

  return function(target, position) {
    for (var i = 0; i < parsers.length; i++) {
      var parsed = parsers[i](target, position);
      // パース成功したら結果をそのまま帰す
      if (parsed[0]) {
        return parsed;
      }
    }

    return [false, null, position];
  };
}

さて、このchoice関数を作ったことで、正規表現でいう/(hoge|fuga)*/という表現をこのパーサコンビネータで表現できるようになった。

var parse = many(choice(token('hoge'), token('fuga')));

parse('', 0); // => [true, [], 0] を返す
parse('hogehoge', 0); // => [true, ['hoge', 'hoge'], 8] を返す
parse('fugahoge', 0); // => [true, ['fuga', 'hoge'], 8] を返す
parse('fugafoo', 0); // => [true, ['fuga'], 4] を返す

パーサを連結する

上ではchoiceやtokenやmanyなどの関数を作ったが、正規表現でいう/(foo|bar)baz/と同じことができるようにするためには、今度はパーサ同士を結合する関数が必要になってくる。

読んでるひとももうだんだん慣れてきたと思うので一気に以下のseq関数を書いてみた。この関数は複数のパーサを連結する。連結されたパーサが内部で持っているパーサが一つでも失敗すれば全体として失敗する。

/**
 * @param {Array} parsers... 結合するパーサの配列
 * @return {Function} パーサ
 */
function seq(/* parsers... */) {
  var parsers = arguments;
  return function(target, position) {
    var result = [];
    for (var i = 0; i < parsers.length; i++) {
      var parsed = parsers[i](target, position);

      if (parsed[0]) {
        result.push(parsed[1]);
        position = parsed[2];
      } else {
        // 一つでも失敗を返せば、このパーサ自体が失敗を返す
        return [false, null, position];
      }
      
    }
    return [true, result, position];
  };
}

このseq関数を使うことで、先ほどの正規表現/foo(bar|baz)/と同じこともできるようになった。

var parse = seq(token('foo'), choice(token('bar'), token('baz')));

parse('foobar', 0); // => [true, ['foo', 'bar'], 6] を返す

parse('foobaz', 0); // => [true, ['foo', 'baz'], 6] を返す

parse('foo', 0); // => [false, null, 0] を返す

オプションを表現するパーサを作る

失敗しても気にしないパーサというのも必要になってくる。例えば/(hoge)?/という正規表現では、hogeという文字がマッチしてもしなくてもパースしてくれる。これもパーサコンビネータで実装してみよう。

オプションを表現するパーサを生成してくれるoption関数が以下になる。

/**
 * @param {Function} parser
 * @return {Function}
 */
function option(parser) {
  return function(target, position) {
    var result = parser(target, position);
    if (result[0]) {
      return result;
    } else {
      return [true, null, position];
    }
  };
}

これも試してみるとこういうことになる。内部で渡したパーサを実行するのだが、このパーサが失敗を返したとしてもoption関数が生成したパーサは成功を返す。その代わりパース結果にはnullが入り、読み取り位置も更新されない。

var parser = option(token('hoge'));

parser('hoge', 0); // => [true, 'hoge', 4] を返す
parser('fuga', 0); // => [true, null, 0] を返す

正規表現も使えるようにする

パーサコンビネータは、正規表現と違って、そのプログラミング言語のコードで記述、拡張できることが多い。

正規表現を使っている場合、自分でコードを書いてその正規表現エンジンを拡張することは基本的にできない。正規表現エンジンはその言語ではなくCなどで書かれている場合が多いからだ。しかしそのプログラミング言語で記述しているパーサコンビネータであれば拡張は可能だ。

パーサコンビネータを拡張するのは非常に簡単だ。パーサの入出力のインターフェイスさえ守れば内部のロジックを自分で好きなように書けるからだ。

さらにこのパーサコンビネータを使いやすくするために、パーサコンビネータ内で正規表現が使えるようにしてみよう。ここでは、正規表現を使ってパーサを生成する以下のregex関数を書いた。

/**
 * @param {RegExp} regexp
 * @return {Function}
 */
function regex(regexp) {
  if (regexp.source.substring(0, 1) !== '^') {
    regexp = new RegExp(
      '^' + regexp.source,
      (regexp.global ? 'g' : '') +
      (regexp.ignoreCase ? 'i' : '') +
      (regexp.multiline ? 'm' : '')
    );
  }

  return function(target, position) {
    regexp.lastIndex = 0;
    var regexResult = regexp.exec(target.slice(position));

    if (regexResult) {
      position += regexResult[0].length;
      return [true, regexResult[0], position];
    } else {
      return [false, null, position];
    }
  };
}

ほんの20行程度書くことで、正規表現を利用できるパーサを書くことができた。

これも試してみよう。

var parser = regex(/hoge/);

parser('hoge', 0); // => [true, 'hoge', 4]を返す

parser = regex(/([1-9][0-9]*)/);

parser('2014', 0); // => [true, '2014', 4]を返す
parser('01', 0); // => [false, null, 0]を返す

再帰する文法を扱えるようにする

前回の記事では、正規表現ではできないことの一つに、再帰的な文法を扱うことができないということを書いた。パーサコンビネータでは、どうやって再帰的な文法を記述するのだろう?

パーサコンビネータのライブラリでは、パーサの実装を遅延評価するパーサを生成して再帰的な文法を記述することが多い。あるパーサの実装を遅延評価すると、パーサを再帰的に構築できる。

ちょっとこれはイメージしづらいと思うのでこれも実際にコードを書いてから解説する。

まず、パーサの実装を遅延評価するlazy関数を記述する。lazy関数は受け取った関数をパース時に初めて評価して、その結果返ってきたパーサを内部で利用する。

function lazy(callback) {
  var parse;
  return function(target, position) {
    if (!parse) {
      parse = callback();
    }    
    return parse(target, position);
  };
}

このlazy関数を使って、試しにごく簡単な再帰的な構造のパーサを作ってみよう。プログラム内のループは再帰呼び出しでも記述できることはよく知られているが、パーサコンビネータでもmanyと同じことは実はこのlazy関数を使って再帰的な構造のパーサを作ることでもできる。例えば、many(token('hoge'))は以下の様にも記述することができる。

var parse = option(seq(token('hoge'), lazy(function() {
  return parse;
})));

parse('hoge', 0); // => [true, ['hoge', null], 4]が返る
parse('hogehoge', 0); // => [true, ['hoge', ['hoge', null]], 8]が返る
parse('hogehogehoge', 0); // => [true, ['hoge', ['hoge', ['hoge', null]]], 12]が返る

パーサの結果を加工するパーサを書く

さて、ここまでパーサコンビネータを書いてきてだいぶ強力になってきたのでついでにパーサの結果を加工するパーサを生成するmap関数を書いてみることにする。

これは、実際に複雑なパーサを構築する時にあると便利である。例えば、プログラミング言語のパーサのようなものを構築する際に、パースの途中で必要の無いデータを削ったり、パースした結果を特定のオブジェクトに変換することができるようになるからである。

function map(parser, fn) {
  return function(target, position) {
    var result = parser(target, position);
    if (result[0]) {
      return [result[0], fn(result[1]), result[2]];
    } else {
      return result;
    }
  };
} 

実際にこれを試してみる。helloという文字列をパースできたら、その結果を加工する例が以下である。

var parse = map(token('hello'), function(result) {
  return result + 'という文字列をパースできたよ';
});

parse('hello', 0); // => [true, 'helloという文字列をパースできたよ', 5]が返る
parse('foobar', 0); // => [false, null, 0]が返る

特定の文字のみを受け入れるパーサを書く

正規表現では、[](ブラケット)で文字クラスを表現できる。例えば、/[abc]/という正規表現はabcという文字のいずれかにマッチする。

これと同じものをパーサコンビネータでも作ってみると以下のようになる。

function char(str) {
  var dict = {};
  for (var i = 0; i < str.length; i++) {
    dict[str[i]] = str[i];
  }

  return function(target, position) {
    var char = target.substr(position, 1);
    if (dict[char]) {
      return [true, char, position + 1];
    } else {
      return [false, null, position];
    }
  };
}

実際にこれを試してみる。

// abcdefといういずれかの文字だけを受け入れるパーサを生成する
var parse = char('abcdef');

parse('a', 0); // => [true, 'a', 1]が返る
parse('b', 0); // => [true, 'b', 1]が返る
parse('g', 0); // => [false, null, 0]が返る
parse('', 0); // => [false, null, 0]が返る

数式のパーサを構築する

さて、ここまで幾つかパーサを生成する関数を作ってきたが、そろそろ強力になってきたので実際に簡単な数式のパーサを書いてみよう。対象とする数式は、演算子は+と-だけで、利用できる数値は整数のみで、括弧を使うことはできるが、式の間にスペースを入れることもできない以下の様な数式だ。

1+1
2-10+5
10+(0-30)+4

まず整数のパーサを書くと以下のようになる。

var number = map(regex(/[0-9]|[1-9][0-9]*/), function(parsed) {
  // パースした文字列を整数に変換する
  return parseInt(parsed, 10);
});

number('0', 0); // => [true, 0, 1]が返る
number('10', 0); // => [true, 10, 2]が返る
number('a1', 0); // => [false, null, 0]が返る

パーサコンビネータの利点のひとつに、パーサを関数として扱えるので、個別の文法のテストが記述できる点がある。ここでは、数値だけをパースするnumber関数を定義しているが、これはただの関数なので、これをそのままユニットテストなどでテストできる。

次は演算子のパーサを書こう。演算子はここでは単に'+'か'-'にマッチすれば良いので簡単だ。

var operator = char('+-');

次は括弧のついた式のパーサを書こう。括弧の中に入る式のパーサ(以下のコードではexpressionという変数を使っている)はまだ定義していないので、lazy関数で囲って遅延評価することにする。

var parenthesis = lazy(function() {
  var parser = seq(token('('), expression, token(')'));
  return map(parser, function(parsed) {
    // 括弧の文字列はいらないので中の数式のパース結果だけを取り出す
    return parsed[1];
  });
});

次に、演算の対象となる数値や式のパーサを書く。この数式では、演算の対象となるのは整数か括弧つきの式かのどちらかであるので、choice()関数を使って以下のようになる。

var atom = choice(num, parenthesis);

次に演算子を使った計算の式を書こう。この数式では、利用できる演算子は全て二項演算子であるので、計算式を表す文字列は、計算の対象、演算子、計算の対象という風に並ぶことになる。従って以下のように記述できる。

var expression = map(seq(atom, many(seq(operator, atom))), function(parsed) {
  // パースの結果を整形する
  // 例えば1+2-3は[1, '+', 2, '-', 3]というような形にする
  return [parsed[0]].concat(parsed[1].reduce(function(result, item) {
    return result.concat(item);
  }, []));
});

最後に、実際にパーサとして試しやすいように以下のようなラッパを作る。パースが失敗した時や、文字列を最後までパースしきれない時にはメッセージを出すようにした。

var parse = function(target) {
  var result = expression(target, 0);

  if (!result[0]) {
    console.log('パース失敗');
  } else if (target.length !== result[2]) {
    console.log((1 + result[2]) + '文字目でパース失敗');
  }

  return result[1];
};

実際に使ってみよう。

var result = parse('1+2-(3+1-(4))');
console.log(JSON.stringify(result));

これを実行すると以下のように表示される。

[1,"+",2,"-",[3,"+",1,"-",[4]]]

文字列がきちんとパースされているようだ。他にも色々な文字を試してみよう。

parse('1+2-(3+1'); // => "4文字目でパース失敗"と表示される
parse('hoge'); // => "パース失敗"と表示される
parse('0-3+(((3)))'); // => [0, '-', 3, '+', [[[3]]]]が返る

数式ではない文字列や一部間違っている数式を与えた時にはきちんとパース失敗していることがわかる。

終わりに

この記事で作成したJavaScript製のパーサコンビネータは、fnparse.jsとしてgithubで公開している。短いコードながらも普通のパーサコンビネータとしても一応利用できるようになっている。

正規表現は便利だが、正規表現が本質的にパースできない文法にはパーサコンビネータを使うとよい。パーサコンビネータのライブラリの利用は、一見すると難しく見えるが、背後のコンセプトさえ理解できればそれほど難しいわけではない。この記事では、実際にJavaScriptで簡単なパーサコンビネータを作ることによって、その背後のコンセプトや仕組みを説明した。