関数型の考え方: 遅延処理、第 2 回

遅延評価について掘り下げる

クロージャーをサポートする言語では、遅延評価を簡単に実装することができます。連載「関数型の考え方」の今回の記事では、Groovy のクロージャーをビルディング・ブロックとして使用して遅延リストを作成する方法を説明します。その後、言語によってはフィールドの初期化を遅延できるという点を含め、遅延評価のパフォーマンス上および概念上のメリットを探ります。

Neal Ford, Software Architect / Meme Wrangler, ThoughtWorks Inc.

Neal Ford の写真Neal Ford は世界的な IT コンサルティング企業である ThoughtWorks のソフトウェア・アーキテクトであり、Meme Wrangler でもあります。また彼は、アプリケーション、教育資料、雑誌記事、コースウェア、ビデオや DVD によるプレゼンテーションなどの設計と開発も行っています。さまざまな技術に関する本の著者、編集者でもあり、最新の著書は『プロダクティブ・プログラマ ― プログラマのための生産性向上術』です。彼は大規模なエンタープライズ・アプリケーションの設計や構築を専門にしています。また彼は世界各地で開催される開発者会議での講演者としても国際的に有名です。彼の Web サイトをご覧ください。



2013年 10月 31日

この連載について

この連載の目的は、読者の皆さんの考え方を関数型の発想へと方向転換し、よくある問題を新たな考え方で検討することによって、日常的なコーディングの改善方法を見つけるお手伝いをすることです。そのために、関数型プログラミングに特徴的な概念、関数型プログラミングを Java 言語で行えるようにするフレームワーク、JVM 上で動作する関数型プログラミング言語、そして今後、言語設計を学習する上での方向性などについて詳しく探ります。この連載の対象読者は、Java および Java の抽象化がどのように機能するかは知っていても、関数型言語を使用した経験がほとんど、あるいはまったくない開発者です。

関数型の考え方: 遅延処理、第 1 回」では、Java での遅延ライブラリーについて探りました。今回の記事では、クロージャーをビルディング・ブロックとして使用して、単純な遅延リストを作成する方法を説明します。その後、遅延評価によるパフォーマンス上のメリットと併せ、Groovy、Scala、Clojure における遅延処理のいくつかの側面を探ります。

遅延リストの作成

この連載の初めのほうの記事で、Groovy における簡単な遅延リストの実装を紹介しましたが、それが動作する仕組みを詳しく取り上げることはしませんでした。ここでは、それを説明します。

前回の記事で説明したように、言語は「正格」(すべての式を先行評価する) タイプまたは「遅延」(絶対的に必要になるまで評価を延期する) タイプに分類することができます。Groovy は基本的には正格な言語ですが、非遅延リストを遅延リストに変換することもできます。その方法は、クロージャーの中で正格なリストを再帰的にラップするというものです。こうすれば、クロージャー・ブロックの実行を遅らせることによって後続値の評価を遅らせることができます。

Groovy での正格な空のリストは、空の大括弧 ([]) を使用した配列によって表現されます。このリストを以下のようにクロージャーの中にラップすれば、空の遅延リストになります。

{-> [] }

リストに要素を追加する場合は、以下のように、その要素を先頭に追加してから、新しいリスト全体を再び遅延リストにします。

{-> [ a, {-> [] } ] }

リストの先頭に要素を追加するためのメソッドは、以前より「プリペンド (prepend)」または「コンズ (cons)」と呼ばれています。さらに他の要素を追加するには、追加する新しい要素ごとに上記の操作を繰り返します。したがって、リストに 3 つの要素 (abc) を追加すると、以下のようになります。

{-> [a, {-> [b, {-> [ c, {-> [] } ] } ] } ] }

この構文は扱いにくいものですが、いったんその原理を理解すれば、Groovy で従来の遅延コレクション用のメソッド一式を実装するクラスを作成することができます (リスト 1 を参照)。

リスト 1. Groovy でクロージャーを使用して遅延リストを作成する
class PLazyList {
  private Closure list

  private PLazyList(list) {
    this.list = list
  }

  static PLazyList nil() {
    new PLazyList({-> []})
  }

  PLazyList cons(head) {
    new PLazyList({-> [head, list]})
  }

  def head() {
    def lst = list.call()
    lst ? lst[0] : null
  }

  def tail() {
    def lst = list.call()
    lst ? new PLazyList(lst.tail()[0]) : nil()
  }

  boolean isEmpty() {
    list.call() == []
  }

  def fold(n, acc, f) {
    n == 0 || isEmpty() ? acc : tail().fold(n - 1, f.call(acc, head()), f)
  }

  def foldAll(acc, f) {
    isEmpty() ? acc : tail().foldAll(f.call(acc, head()), f)
  }

  def take(n) {
    fold(n, []) {acc, item -> acc << item}
  }

  def takeAll() {
    foldAll([]) {acc, item -> acc << item}
  }

  def toList() {
    takeAll()
  }
}

リスト 1 のコンストラクターは、private です。このコンストラクターが呼び出されると、空のリストを作成する nil() を使用して、空のリストを作成することから始められます。リストに新しい要素を追加するには、cons() メソッドを使用することができます。このメソッドは、渡されたパラメーターをプリペンドして、その結果をクロージャー・ブロック内にラップします。

その次の 3 つのメソッドは、リストのトラバースを可能にします。head() メソッドはリストの先頭の要素を返し、tail() メソッドは先頭の要素を除くすべての要素のサブリストを返します。この 2 つのメソッドでは、いずれも call() を使用してクロージャー・ブロックを呼び出します。これは、遅延という観点では評価の「強制」として知られています。ここでは値を取得していることから、値を取り込むときには遅延処理ではなくなります。そして 3 つ目の isEmpty() メソッドは想像通り、解決する項が残っているかどうかを調べます。

残りのメソッドは、リストに対する操作を行うための高階関数です。fold() メソッドと foldAll() メソッド (あるいは Groovy の場合のみ、injectAll() メソッド) は、「reduce」としても知られる、「畳み込み」抽象化を行います。これまでの多くの記事 (例えば、「関数型の観点で考える、第 3 回」など) で、この系列のメソッドの使い方を紹介しましたが、純粋にクロージャー・ブロックの観点で作成された再帰的定義を紹介するのは今回が初めてです。foldAll() メソッドは、リストが空であるかどうかを調べ、空である場合は acc (アキュムレーター。畳み込み操作のシード値) を返します。リストが空でなければ、リストの tail() に対して再帰的に foldAll() を呼び出して、アキュムレーターとリストの先頭の要素を渡します。すると (引数 f で表される) 関数が 2 つの引数を取って、1 つの結果を生成します。これが、1 つの要素を隣接する要素の上に折り重ねていくという「畳み込み」操作です。

リストの作成と操作は、リスト 2 のようにして行われます。

リスト 2. 遅延リストを操作する
def lazylist = PLazyList.nil().cons(4).cons(3).cons(2).cons(1)
println(lazylist.takeAll()) //[1, 2, 3, 4]
println(lazylist.foldAll(0, {i, j -> i + j})) // 10
lazylist = PLazyList.nil().cons(1).cons(2).cons(4).cons(8)
println(lazylist.take(2))  //[8, 4]

リスト 2 では、空のリストで cons() に値を渡して実行することにより、リストを作成しています。注意する点として、takeAll() で要素を取り込むと、要素の順序はリストへの追加順と逆になります。これは既に説明したように、cons() は実際にはプリペンドの簡略表現であり、要素をリストの先頭に追加するためです。また、リストを合計するには、foldAll() メソッドを使用して、畳み込み操作として加算を適用する変換コード・ブロック {i, j -> i + j} を渡します。最後に take() メソッドを使用して、最初の 2 つの要素だけを強制評価しています。

上記の例とは異なり、実際の遅延リストの実装では、再帰を避け、もっと柔軟な操作メソッドを追加しますが、概念的に実装の中で何が行われているのかを知っておくと、実装を理解して使用するときの助けとなります。


遅延処理のメリット

遅延リストには、いくつかのメリットがあります。まず 1 つ目は、遅延リストを使用して無限数列を作成できることです。値は必要になるまで評価されないため、遅延コレクションを使用すれば、無限大のリストをモデル化することができます。Groovy で実装された無限数列の例は、記事「関数型の考え方: Groovy に隠された関数型の機能、第 1 回」に記載されているとおりです。2 つ目のメリットは、ストレージ・サイズが削減されることです。コレクション全体を保持するのではなく、後続値を派生させることができれば、実行速度と引き換えにストレージ域を手に入れることができます。遅延コレクションを使用することにした場合、値を保管するコストと、新しい値を計算するコストとのトレードオフになります。

そして 3 つ目のメリットは、ランタイムでより効率的なコードを生成できることであり、これは遅延コレクションを使用する主なメリットの 1 つでもあります。一例として、リスト 3 のコードを検討してみましょう。

リスト 3. Groovy での回文の検出
def isPalindrome(s) {
  def sl = s.toLowerCase()
  sl == sl.reverse()
}

def findFirstPalindrome(s) {
  s.tokenize(' ').find {isPalindrome(it)}
}

s1 = "The quick brown fox jumped over anna the dog";
println(findFirstPalindrome(s1)) // anna

s2 = "Bob went to Harrah and gambled with Otto and Steve"
println(findFirstPalindrome(s2)) // Bob

リスト 3isPalindrome() メソッドは、対象の単語の大/小文字を正規化してから、その単語を逆向きで読んだ場合でも文字の並びが同じであるかどうかを判別します。findFirstPalindrome() メソッドは、渡された文字列で最初の回文を見つけるために Groovy の find() メソッドを使用します。このメソッドが、フィルタリング・メカニズムとしてコード・ブロックを引数に取ります。

例えば、非常に長い文字列があり、その中で最初の回文を見つけなければならないとします。リスト 3 のコードは、findFirstPalindrome() メソッドの実行中に、先行して文字列全体をトークン化し、中間データ構造を作成してから、find() コマンドを発行します。Groovy の tokenize() メソッドは遅延に対応しないため、この例では巨大な一時データ構造が作成されることになりますが、結局はその大部分が破棄されるだけです。

同じコードを Clojure で作成した場合の例をリスト 4 で検討してみましょう。

リスト 4. Clojure での回文
(defn palindrome? [s]
  (let [sl (.toLowerCase s)]
  (= sl (apply str (reverse sl)))))

(defn find-palindromes [s]
    (filter palindrome? (clojure.string/split s #" ")))

(println (find-palindromes "The brown fox jumped over anna."))
; (anna)
(println (find-palindromes "Bob went to Harrah and gambled with Otto"))
; (Bob Harrah Otto)
(println (take 1 (find-palindromes "Bob went to Harrah and gambled with Otto")))
; (Bob)

リスト 3リスト 4 とでは、実装の詳細は変わりませんが、使用している言語構成体が異なります。Clojure の palindrome? 関数では、パラメーターの文字列を小文字にしてから、それを逆順にした文字列と等しいかどうかをチェックします。apply を追加で呼び出して、reverse によって返された文字列を比較用の文字列に変換します。find-palindromes 関数が使用している Clojure の filter 関数が引数として取るのは、フィルターとしての役割を果たす関数とフィルタリング対象のコレクションです。palindrome? 関数を呼び出す場合、Clojure にはいくつかの方法があります。その 1 つとして、匿名関数を作成して #(palindrome? %) のように呼び出す方法があります。これは、単一の引数を取る匿名関数の構文糖です。この関数の長いバージョンは以下のようになります。

    (fn [x]
      (palindrome? x))

引数が 1 つだけの場合、Clojure では匿名関数を宣言して引数に名前を付ける必要はありません。そのため、#(palindrome? %) 関数呼び出しでは引数を % に置き換えています。リスト 4 では、さらに短い形式の関数名を直接使用することができます。filter が要求しているのは、単一の引数を取り、palindrome? と一致するブール値を返すメソッドです。

Groovy から Clojure への変換に伴うのは、構文の変更だけではありません。遅延可能な Clojure のデータ構造は、コレクションでの filtersplit のような操作を含め、すべて遅延されます。そのためリスト 4 に記載した 2 番目の例で明らかなように、Clojure バージョンでは、複数の要素からなるコレクションに対して find-palindromes を呼び出すと、何もかもが自動的に遅延されます。filter からは、出力するときに強制的に遅延コレクションが返されます。最初のエントリーだけが必要な場合には、take を使用して、リストのなかから必要とされる遅延要素の数を指定する必要があります。

Scala での遅延処理の手法は少し異なります。デフォルトですべてを遅延させるのではなく、Scala はコレクションの遅延ビューを提供します。リスト 5 に記載する、Scala での回文問題の実装について検討してみましょう。

リスト 5. Scala での回文
def isPalindrome(x: String) = x == x.reverse
def findPalidrome(s: Seq[String]) = s find isPalindrome

findPalindrome(words take 1000000)

リスト 5 では、take メソッドによってコレクションから 100 万個の単語を取り出しますが、特に最初の回文を見つけることが目的の場合には、それではかなり非効率です。words コレクションを遅延コレクションに変換するには、view メソッドを使用します。

findPalindrome(words.view take 1000000)

view メソッドによってコレクションの遅延トラバースが可能になるため、より効率的なコードになります。


フィールドの初期化の遅延

遅延処理の話題を終える前に、2 つの言語 (Scala と Groovy) には、コストのかかる初期化を遅延させる便利な機能が用意されていることに触れておきます。Scala では、以下のように val 宣言の前に lazy を追加することで、フィールドを先行評価するものから必要に応じて評価するものへと変換することができます。

lazy val x = timeConsumingAndOrSizableComputation()

上記は基本的に、リスト 6 に記載するコードの構文糖です。

リスト 6. 遅延フィールド用に生成された Scala の構文糖
var _x = None
def x = if (_x.isDefined) _x.get else {
  _x = Some(timeConsumingAndOrSizableComputation())
  _x.get
}

Groovy にも、抽象構文木 (Abstract Syntax Tree: AST) 変換として知られる高度な言語機能を使用した同様の機能があります。AST 変換では、ユーザーはコンパイラーによる抽象構文木の生成を操作して、下位レベルで変換を行うことができます。事前定義されている変換の 1 つは @Lazy 属性です。リスト 7 に、その使用方法を示します。

リスト 7. Groovy での遅延フィールド
class Person {
    @Lazy pets = ['Cat', 'Dog', 'Bird']
}

def p = new Person()
assert !(p.dump().contains('Cat'))

assert p.pets.size() == 3
assert p.dump().contains('Cat')

リスト 7Person インスタンス p には、このデータ構造に初めてアクセスするまでは、Cat 値は存在しないように見えます。Groovy では、以下のようにクロージャー・ブロックを使用してデータ構造を初期化することもできます。

class Person {
    @Lazy List pets = { /* complex computation here */ }()
}

また、遅延して初期化されるフィールドを保持するために、ソフト参照 (必要に応じて再利用できる、ポインター参照の Java バージョン) を使用するように Groovy に対して指示することもできます。

class Person {
    @Lazy(soft = true) List pets = ['Cat', 'Dog', 'Bird']
}

まとめ

今回の記事では、遅延処理をさらに深く探り、Groovy のクロージャーを使用して一から遅延コレクションを作成しました。また、遅延構造を検討することを勧める理由を説明し、そのメリットをいくつか示しました。具体的には、ランタイムがリソースを最適化できることが大きなメリットとなります。そして最後に、遅延して初期化されるフィールドに関する、Scala および Groovy での難解ながらも有用な遅延処理を明らかにしました。

参考文献

学ぶために

  • 「Lazy lists in Groovy」: Andrey Paramonov 氏のブログで、クロージャーを使用して遅延リストを作成することに関する彼の見解を参考にしてください。
  • Scala: Scala は JVM での新しい関数型言語です。
  • Clojure: Clojure は JVM で動作する新しい関数型 Lisp です。
  • Totally Lazy: Totally Lazy フレームワークは、直観的な DSL のようなインターフェースを使用して、数え切れないほどの関数型の拡張機能を Java に追加します。
  • Functional Java: Functional Java は、多数の関数型言語の構成体を Java に追加するフレームワークです。
  • 「多忙な Java 開発者のための Scala ガイド」: この developerWorks の連載で Scala について詳しく学んでください。
  • Technology bookstore で、この記事で取り上げた技術やその他の技術に関する本を探してください。
  • developerWorks Java technology ゾーン: Java プログラミングのあらゆる側面を網羅した記事が豊富に用意されています。

製品や技術を入手するために

  • IBM 製品の評価版をダウンロードして、DB2、Lotus、Rational、Tivoli、および WebSphere などが提供するアプリケーション開発ツールやミドルウェア製品を試してみてください。

議論するために

  • developerWorks コミュニティーに参加してください。ここでは他の developerWorks ユーザーとのつながりを持てる他、開発者によるブログ、フォーラム、グループ、Wiki を調べることができます。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Java technology
ArticleID=950155
ArticleTitle=関数型の考え方: 遅延処理、第 2 回
publish-date=10312013