Go to Qiita Advent Calendar 2024 Top
LoginSignup
97
81

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@hiruberuto

どう見てもJavaScriptなのに遅延評価するオレオレプログラミング言語を作りました。遅延評価 is 何？

Last updated at Posted at 2016-10-18

急にプログラミング言語を作りたくなったので、見た目はJavaScriptなのに遅延評価なプログラミング言語を作ってみました。このエントリで解説されている内容はほとんど実用性がないので、暇つぶしをしたい人だけお読みください。

今回作ったもの

「そもそも『遅延評価』って何？」っていう人が多いとは思うのですが、それはおいおい説明するとして、まずは今回作ったものを簡単に紹介します。今回作ったプログラミング言語の名前は、コンセプトそのまんまでLazyScriptです。JavaScriptのサブセットを用意して新しいプログラミング言語を作ったと私が言い張るのは実は既に二回目なのですが、処理系を作ってすらいない前回と違って、今回はちゃんとインタプリタを作りました。コンセプトは次のような感じです。

  • 評価の過程を確認しやすい。今回作った処理系では、比較的読みやすい形式で評価の過程を表示できるようにしました。遅延評価のお勉強向けです（これはHaskellの評価の過程を確認するのがあまりに困難だというのが根底にあります）。このため、コンパイラではなくインタプリタにしました。
  • JavaScriptの構文のサブセット。Haskell系の言語の構文に抵抗のある人もいるかもしれないので、JavaScriptを元にした平凡な構文にしました。実際、構文としては完全にJavaScriptで、LazyScriptのコードをそのままJavaScriptエンジンに突っ込んでも動く場合があります。
  • ブラウザで動く。ちょっとした暇つぶしで遊ぶだけのために、どこの馬の骨が書いたのかわからないプログラムをローカルで動かしたくないでしょう。安心安全のウェブアプリです。

以下のページでインタプリタの実行を試すことができます。幾つか簡単なサンプルコードを用意してあるので、本文を読みつつ試してみてください。ちゃんと動かないものがあったらごめんなさい。

遅延評価の奇妙な世界(1) 定数関数

さて、自分で作ったインタプリタを動かしながら、遅延評価の奇妙な世界を鑑賞していきましょう。まずは次のコードです。

square = (x) => x * x
square (4 + 2)

見た目は完全にJavaScriptのコードと同じですね。変数squareは引数の値を二乗する関数です。このsquareを4 + 2を引数にして呼び出すと、普通のJavaScriptなら、

  1. まず4 + 2 = 6が計算される
  2. 6を引数にsquareが呼び出され、xに6が代入される
  3. squareの本体部ではx * x = 6 * 6 = 36が計算され、36が結果として返される

というように処理が進んでいくはずです。算数の式変形のように表記すると、次のようなイメージです。

  square(4 + 2)
= square(6)
= 6 * 6
= 36

しかし、今回筆者が作ったインタプリタでは、コードを入力してEvaluateボタンを押すと、次のような手順で計算が進んでいきます。

  square(4 + 2)
= ((x) => x * x)(4 + 2)
= (4 + 2) * (4 + 2)
= 6 * 6
= 36

不思議なことに、引数の部分に与えられた式を評価しないまま、その式ごと関数に渡され、(4 + 2) * (4 + 2)という式に展開されています。もちろん最終的な結果はどちらも変わらないのですが、計算の手順が明らかに異なっています。このことがどんな違いをもたらすのかは、次の関数cstを使ってみるとわかるでしょう。

cst = (x, y) => x
cst(20 + 22, foo)

一行目では関数cstを定義しています。LazyScriptにはfunction文がないので、どんな関数もアロー関数式を使って定義します。この関数cstは、２つの引数のうち、最初に渡した引数xの値を返すだけの関数です。その関数cstに引数20 + 22とfooを与えて呼び出すのですが、これがJavaScriptであれば、まず20 + 22を計算し、それから変数fooの値を参照し、それから関数cstを呼び出すはずです。しかし、このインタプリタでは次のようになります。

  cst(20 + 22, foo)
= 20 + 22
= 42

よく考えると、先ほどふたつめの引数に与えられた変数fooですが、この変数は定義されていません。JavaScriptなら未定義の変数を参照しようとすると"Uncaught ReferenceError: foo is not defined"みたいなエラーになりますが、この処理系では関係ありません。cstはふたつめの引数は無視しますから、それが未定義の変数であろうがエラーにはならないのです。そして20 + 22は普通に計算できますから、最終的な値は42と正常に求めることができます。

構文上の見た目はJavaScriptと全く同じなのに、この言語ではぜんぜん違う手順で計算を進めるのです。このように、どんな手順で式の計算を進めていくのかという決まりを評価戦略といいます。そして現存のプログラミング言語のほぼすべては、JavaScriptと同じように関数を呼び出す前にまずは引数を評価する正格評価を基本戦略とします。Haskellや今回筆者が作ったLazyScriptのようなごく一部の言語は、それが必要になるまでなるべく計算をサボる遅延評価を基本戦略とします1。怠惰デスねぇ。

遅延評価の奇妙な世界(2) 無限リスト

次は遅延評価でリストをあつかってみます。ここでは、リストとはheadプロパティとtailプロパティを持ったオブジェクトが連結したものであるとします。リストの終端はnullで表します。たとえば、配列[1, 2, 3]のような感じで数が順番に格納されているリストzeroToTwoを、次のようなオブジェクトで表すことにします。

zeroToTwo = { head: 0, tail: { head: 1, tail: { head: 2, tail: null } } }

このとき、リストのひとつ後ろを手繰るにはtailプロパティを参照すればいいし、要素を取り出すにはheadプロパティを参照します。例えば、二番目の要素を取り出すには、２回tailをたどったあとでheadにアクセスします。

zeroToTwo.tail.tail.head        // 2

これを踏まえたうえで、次の変数answersの定義を見てみましょう。

answers = { head: 42, tail: answers }

このコードをJavaScriptで評価した場合、上の式の右辺を評価する時点ではanswersは未定義なので、 answers.tailはundefinedになるはずです。しかし、LazyScriptではanswers.tailはちゃんと再帰的にanswers自身を示しています。したがって、answers.tail.tail.tail.tail.tailというようにひたすらプロパティを手繰っていっても、それはいつもanswers自身と同じものなので、決してエラーになることはありません。そしてどの時点でheadを触っても、必ずちゃんと42が返ってきます。

   answers.tail.tail.tail.head
 = {head: 42, tail: xs}.tail.tail.tail.head
 = answers.tail.tail.head
 = {head: 42, tail: xs}.tail.tail.head
 = answers.tail.head
 = {head: 42, tail: xs}.tail.head
 = answers.head
 = {head: 42, tail: xs}.head
 = 42

つまり、answersはすべての要素に42が格納された無限長のリスト[42, 42, 42, ...]であると捉えることができます。今度はすべての自然数が順番に格納されているような無限リストを作ってみましょう。次のような関数iterateを用意すると、すべての自然数が順番に格納されたリストnat = [0, 1, 2, 3, ...]を次のように定義することができます。

iterate = (n, f) => ({ head: n, tail: iterate(f(n), f) })
nat = iterate(0, (x)=>x+1)

iterateは終了条件のない再帰関数ですから、これを普通のJavaScriptエンジンで実行できたとしてもあっさりスタックオーバーフローになるでしょう。というか、そもそもこのようにアロー関数式で定義した場合、iterateの右辺ではまだiterate自身が定義されていないのでundefinedです。JavaScriptで再帰的な関数を書くにはfunction文を使うかarguments.calleeを参照しますが、LazyScriptでは再帰呼び出しのためにそのような仕組みは必要ではなく、平気で正常に評価できます。

   nat.tail.tail.tail.tail.head
 = iterate(0, (x) => x + 1).tail.tail.tail.tail.head
 = ((n, f) => {head: n, tail: iterate(f(n), f)})(0, (x) => x + 1).tail.tail.tail.tail.head
 = {head: 0, tail: iterate(((x) => x + 1)(0), (x) => x + 1)}.tail.tail.tail.tail.head
 = iterate(((x) => x + 1)(0), (x) => x + 1).tail.tail.tail.head
 = ((n, f) => {head: n, tail: iterate(f(n), f)})(((x) => x + 1)(0), (x) => x + 1).tail.tail.tail.head
 = {head: ((x) => x + 1)(0), tail: iterate(((x) => x + 1)(((x) => x + 1)(0)), (x) => x + 1)}.tail.tail.tail.head
 = iterate(((x) => x + 1)(((x) => x + 1)(0)), (x) => x + 1).tail.tail.head
 = ((n, f) => {head: n, tail: iterate(f(n), f)})(((x) => x + 1)(((x) => x + 1)(0)), (x) => x + 1).tail.tail.head
 = {head: ((x) => x + 1)(((x) => x + 1)(0)), tail: iterate(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0))), (x) => x + 1)}.tail.tail.head
 = iterate(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0))), (x) => x + 1).tail.head
 = ((n, f) => {head: n, tail: iterate(f(n), f)})(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0))), (x) => x + 1).tail.head
 = {head: ((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0))), tail: iterate(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0)))), (x) => x + 1)}.tail.head
 = iterate(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0)))), (x) => x + 1).head
 = ((n, f) => {head: n, tail: iterate(f(n), f)})(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0)))), (x) => x + 1).head
 = {head: ((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0)))), tail: iterate(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0))))), (x) => x + 1)}.head
 = ((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0))))
 = ((x) => x + 1)(((x) => x + 1)(((x) => x + 1)(0))) + 1
 = ((x) => x + 1)(((x) => x + 1)(0)) + 1 + 1
 = ((x) => x + 1)(0) + 1 + 1 + 1
 = 0 + 1 + 1 + 1 + 1
 = 1 + 1 + 1 + 1
 = 2 + 1 + 1
 = 3 + 1
 = 4

natのリストの後ろを.tailで手繰ると、そのたびにひとつづつ大きな自然数を得ることができます。上のコードではnat.tail.tail.tail.tail.headとtailを4回たどったので、そこでheadを読むと4が返ってきます。ちょっと式変形が大げさですが、ちゃんとnatが自然数の無限リストになっていることがわかります。これが正常に計算できるのも、natの定義の式の評価を出来るだけ遅らせているからです。

JavaScriptの遅延評価

JavaScriptが正格評価だというのは、式の大半は正格評価だということであって、実はJavaScriptも一部に遅延評価のような振る舞いをする式があります。たとえば、ショートサーキット演算子x || yは、xが真ならyに書かれた式は計算されずに無視されますが、これも一種の遅延評価だと捉えることができます。LazyScriptではほぼすべての式がショートサーキット演算子のように必要な部分だけを計算します。

遅延評価の何が嬉しいのか

遅延評価にはいいところがいっぱいあります。

1.言語仕様が簡単になる

LazyScriptには&と&&のような通常の演算子とショートサーキット演算子という区別が存在しません。すべての演算子がショートサーキット演算子と同じように必要な分だけしか計算しないという振る舞いをするからです。その意味では遅延評価の言語は単純です。

2.コードが単純になる

JavaScriptでは基本的に上から順に計算されていきますから、変数を参照するときはその変数が予め定義されていなくてはなりません。たとえば、次のように、xが定義される前にyの定義の中でxを参照してしまうと、エラーになったりundefinedになるでしょう。

y = x * 2
x = 42

しかし、HaskellやLazyScriptでは変数の定義がどのような順番で並んでいてもまったく関係ありません。初期化の都合に合わせて並べるのではなく、自分が読みやすく意味のわかりやすいまとまりごとに並べればいいのです。

また、上で述べたとおりに再帰的な定義のデータを扱うことができるようになります。無限リストのような再帰的なデータなんて、あまり使わないと思うかもしれません。でも筆者が今回インタプリタを作ったときに再帰的な定義が欲しくなることが実際にありました。具体的には、構文解析器の定義です。簡単に説明すると、例えば任意個の括弧[]に囲まれたaの文字、つまり[[[[a]]]]]のような文字列を構文解析したいとき、定義は次のような感じになります。

遅延評価なHaskellでは
expression = (string "[" *> expression *> string "]") <|> string "a"
  • 式とは(expression =)
  • まず文字列[があって(string "[")
  • それから(*>)、式があって(expression)
  • それから(*>)、文字列[がある(string "]")
  • または(<|>)、文字列aがある(string "a")

というように読むのですが、式expressionの定義の中にexpression自身が再帰的に現れるのです。こんな風に実際に再帰的な定義というのはありうるのですが、Haskellのような遅延評価の言語では上の定義をそのまま書き下せる一方で、正格評価の言語ではこれを書くために一工夫が必要になります。今回インタプリタをPureScriptという正格評価の言語で書いたため、上の式にfixという変な関数を噛ませるという工夫が必要になりました。

正格評価なPureScriptでは
expression = fix \expression' -> (string "[" *> expression' *> string "]") <|> string "a"

こんな感じで、遅延評価の言語にくらべ、正格評価の言語では評価順序の都合のために若干コードが汚くなります。若干ですが。

3.実行効率が上がる(かもしれない)

『必要になるまでなるべく計算を遅らせる』という振る舞いからもわかるように、遅延評価では不要な計算を省け実行効率が向上する場合があります。

遅延評価と正格評価で極端に性能が異なる関数として、たらい回し関数がよく知られています2。この関数を素直に書いた場合は、遅延評価のHaskellが正格評価のC++を上回るようです。もっとも、ほとんどの普通の計算ではさすがにC++のほうが早いですし、C++でも結果をキャッシュするなどして最適化すれば良い話ですから、本気で速度が欲しいなら素直にC++で書いたほうが現実的ではあります。

4. 堅牢性が向上する(かもしれない)

先に挙げた例からもわかりますが、必要になるまで計算をしないということは、不要な計算でエラーが発生するような場合にそのエラーが回避して正常に計算を続行できるということを意味します。そのため堅牢性が向上すると言えるかも……。もっとも、堅牢なソフトウェアを作りたいなら、静的な型付けの言語を使ったりテストをちゃんと書いたりすることのほうがずっと大切です。

遅延評価の闇・スペースリーク

リストの数の合計を求めるようなプログラムを書いてみましょう。詳細な説明は省きますが、リストの合計を計算する関数sumは、foldlという関数を使って次のように定義することができます(このfoldlはインタプリタのサンプルコードにもあります)。

foldl = (f, a, xs) => xs == null ? a : foldl(f, f(a, xs.head), xs.tail)
sum = (xs) => foldl((x, y) => x + y, 0, xs)

この関数sumを使おうとすると、最終的には正しく計算できるものの、評価の途中で式が凄まじく長くなります。これがスペースリークという遅延評価独特の問題です。計算の内容によってはこれでメモリを使い果たし、最悪はエラーで計算が中断してしまいます。

これを解決するには、正格評価演算子という特殊な演算子で式の一部を正格評価します。LazyScriptではカンマ演算子で正格評価ができるようになっています。このfoldlの正格評価バージョンfoldlPは次のように定義することができます。

foldlP = (f, a, xs) => {
    b = f(a, xs.head)
    return xs == null ? a : (b, foldlP(f, b, xs.tail))
}

このfoldlPを使うと、最初に一旦少し式が長くなるものの、あとは評価が進むに連れて単調に短くなっていきます。一部に正格評価を用いることでメモリの消費を抑えたわけです3。

遅延評価のほうが基本的にはいろいろコードがスッキリする場面が多いのですが、一方でスペースリークのような独特の問題を持ち込むことになります。正格評価演算子のような特殊な仕様も必要ですし、決して便利なばかりとはいえないようです。

言語の純粋性と遅延評価の関係

言語が純粋である(『純粋関数型プログラミング言語』である)ということと、評価戦略がデフォルトで遅延評価であるということを、混同しているひとを見かけることがあります。たしかに純粋関数型言語の代表選手であるHaskellが遅延評価を採用していることから、言語が純粋であれば遅延評価も採用されるものだと思うのかもしれません。でも言語は純粋でも、正格評価を採用している言語はいくつかあります。この意味で、言語の純粋性と遅延評価は別々のものだと言ってしまっていいでしょう。

ただ、純粋ではないが遅延評価、というような言語は、実用的なものはおそらく存在しないと思います。何しろ遅延評価では評価の順序が不明瞭なので、式に作用が含まれると、その作用がどのような順序で実行されるのか、予想するのがとても難しくなります。このため、デフォルト遅延評価を採用するなら、言語を純粋にするほかないと思います。

純粋 純粋でない
正格評価 Elm, PureScriptなど C/C++, Java, JavaScript, Pythonなど
遅延評価 Haskell, Rなど (人類には早過ぎる)

なお、「関数型プログラミング言語」の特徴として遅延評価が挙げられることがよくあるのですが、遅延評価をまともに使おうとしている関数型プログラミング言語はHaskellがほとんど唯一です（※追記：あとで知ったのですが、わりとメジャーな言語であるRは、遅延評価の言語であるようです。使ったことがないので良く知らないんですけども）。LispもSchemeもOCamlもScalaもElmもPureScriptもElixerも関数型プログラミング言語に分類されることが多いと思いますが、それらの言語では遅延評価なんて申し訳程度に使っているだけです。遅延評価を関数型プログラミング言語の特徴として挙げるのはあまりに無理があります。

さいごに

それでは、今読んだ話はすべて忘れて、明日からも普通に正格評価な言語を使いましょう。こんな言語を作っておいてなんですが、筆者は遅延評価はぜんぜん好きじゃないです。Haskellはモナドが難しいとか言われますが、Haskellで難しいのはモナドなんかじゃなくて遅延評価だと筆者は思います。遅延評価の闇に浸かりたい人はぜひHaskellへどうぞ。

Haskellのスペースリークは闇が深すぎて、Qiitaのアドベントカレンダーに専用のカレンダーが立ち上がるくらいです。正格評価にしておいたほうが便利な場面が多いせいで、最近ではHaskell(というかGHC)にもデータをデフォルトで正格に評価する拡張が導入されたりしたようです。

ちなみに、私はHaskellの遅延評価を使いこなせず、正格評価のPureScriptに逃げました。自分で遅延評価な言語の処理系を作れるくらいなので、遅延評価についての理解が乏しいというわけではないと思うんですが、遅延評価はほんとに苦手です。PureScriptでは正格評価がデフォルトですが、実用上は何ひとつ困っていません。じゃあなぜHaskellは遅延評価なのかって？　さあ……私にはよくわからないので、『なぜ関数プログラミングは重要か』を読んでみてください。無限リストを直接表現できるというのは、理論としてはわりと面白いとは思うんですけど。

プログラミング言語を自作するっていう話題はみんな好きみたいですし、今回は前回の記事の発展形として書きました。前回のorelangというLispっぽい構文のプログラミング言語はあまりに構文が簡素でしたが、今回作ったLazyScriptは変数はもちろんクロージャつきの関数が使えたり、ちゃんと優先順位つきの四則演算ができたりと、比較的まともな構文を持っています。

筆者は２年に一度くらいのペースでおもちゃみたいなプログラミング言語の処理系を自作して遊んでいる気がします。普通のプログラミング言語を作っても車輪の再発明でしかないですから、だいたいは今回のようにとてつもなく変なコンセプトの言語を作ります。遅延評価を評価戦略にする言語は極めて稀ですから、今回のLazyScriptも相当に貴重なコンセプトの言語であると思います。

LazyScriptインタプリタにはまだまだ機能も足りないしバグも残っているのですが、foldlとfoldlPの振る舞いの違いを再現できたところで飽きた満足したので、ここらでLazyScriptは終了にします。遅延評価については忘れてしまって構わないです。このエントリで筆者が言いたいのは、こんな風に自分のオリジナルなプログラミング言語を作るのは面白いということです。

参考文献

  1. 『なるべくサボる』とひとことで言っても、どの手順で計算するのかは厳密には言語仕様で決まっているわけではなく、処理系依存だったりします。Haskellでも厳密にはどの手順で計算されるかは決められていないのですが、どの手順で計算しても同じ結果になるようになっているので、厳密な順序は基本的には気にしなくていいようになっています。詳しくは参考文献の『Haskellコンパイルシステム利用の手引き』をどうぞ。 ↩

  2. なお、今回筆者が作ったLazyScriptインタプリタでもたらい回し関数は実行できるのですが、計算はできるものの、どこかにバグがあるのか極端に効率が低いです。直せるといいんですが……。 ↩

  3. なお、foldlと``foldl'は、使い分けるというより、ほとんどの場合は正格版のfoldl'`のほうが効率がいいようで、`foldl`はほとんど使い道がないようです。詳しくは参考文献の『foldlを直す』を。 ↩

97
81
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
97
81

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?