お気楽 Go 言語プログラミング入門

はじめに

今回は電卓プログラムに「遅延評価 (delayed evaluation または lazy evaluation)」という機能を追加してみましょう。まず最初に、遅延評価について簡単に説明します。

●遅延評価とは？

一般的なプログラミング言語の場合、関数を呼び出す前に引数の式が評価され、その結果が関数に渡されます。これを「正格 (strict) な評価」といいます。これに対し、実際に値が必要となる時まで式の評価を行わない方法を「遅延評価」といいます。

プログラミング言語では、関数型言語の Haskell が遅延評価を行います。また、Scheme には遅延評価を行うための機能 (delay, force) が用意されています。今回は Scheme と同様に、delay と force を電卓プログラムに追加することにします。

●delay と force の動作

次は、delay と force の動作を説明します。

delay(式)
force(promise)

電卓プログラムの場合、遅延評価を実現するため構文に delay 式を追加します。delay 式は引数の式を評価しないで「プロミス (Promise)」というデータを返します。

引数の式はこのプロミスに保存されていて、組み込み関数 force(promise) を実行すると、プロミスに格納されている式を評価してその値を返します。このとき、値がプロミスに保存されることに注意してください。再度 force(pomise) を実行すると、保存された値が返されます。

簡単な使用例を示しましょう。

Calc> a = delay(begin println("oops!"), 1 + 2 end);
<Promise>
Calc> force(a);
oops!
3
Calc> force(a);
3

delay(begin ... end) の返り値を変数 a にセットします。このとき、引数の begin 式は評価されません。force(a) を実行すると、式 begin println("oops!"), 1 + 2 end が評価されるので、画面に oops! が表示されて返り値は 3 になります。

次に、force(a) を実行すると、式を評価せずに保存した値を返すので oops! は表示されません。

●構文解析の修正

それではプログラムを作りましょう。字句解析はトークンに DELAY を、キーワード keyTable に delay と DELAY を追加するだけです。delay 式の処理は関数 factor で行います。次のリストを見てください。

リスト : 因子の処理

func factor(lex *Lex) Expr {
    switch lex.Token {

    ・・・省略・・・

    case DELAY:
        lex.getToken()
        if lex.Token != '(' {
            panic(fmt.Errorf("delay: '(' expected"))
        }
        lex.getToken()
        e := expression(lex)
        if lex.Token != ')' {
            panic(fmt.Errorf("delay: ')' expected"))
        }
        lex.getToken()
        return newMakePromise(e)

    ・・・省略・・・

    }
}

トークンが DELAY の場合、次のトークンが左カッコ '(' であることを確認してから、expression で式を読み込みます。そして、次のトークンが右カッコであることを確認してから、関数 newMakePromise で式 e を格納した構造体 MakePromise を生成して返します。あとは、MakePromise を Eval で評価すると、プロミスを表す構造体 Promise を生成するようにします。

●プロミスの定義

次はプロミスを表す構造体 Promise を定義します。

リスト : プロミスの定義

type Promise struct {
    val  Value
    expr Expr
    env  *Env
}

func newPromise(expr Expr, env *Env) *Promise {
    return &Promise{nil, expr, env}
}

func (_ *Promise) isTrue() bool { return true }
func (_ *Promise) String() string { return "<Promise>" }

// Promise の生成
type MakePromise struct {
    expr Expr
}

func newMakePromise(expr Expr) *MakePromise {
    return &MakePromise{expr}
}

func (p *MakePromise) Eval(env *Env) Value {
    return newPromise(p.expr, env)
}

構造体 Promise のフィールド変数 val は式を評価した結果を格納します。expr が評価する式です。env は Promise を生成したときの環境です。プロミスを評価するときは、それを生成したときの環境で行います。プロミスを評価するときの環境では行わないことに注意してください。Promise は値なので、メソッド isTrue を定義します。また、Promise を表示するため、メソッド String() も定義します。

構造体 MakePromise は式 expr を格納するだけです。メソッド Eval は MakePromise に格納されている式 p.expr と環境 env を関数 newPromise に渡して Promise を生成するだけです。

●プロミスの評価

最後にプロミスを評価する組み込み関数 force を作ります。

リスト : プロミスの評価

func force(v Value) Value {
    p, ok := v.(*Promise)
    if !ok {
        panic(fmt.Errorf("force: Promise required, %v", v))
    }
    if p.val == nil {
        p.val = p.expr.Eval(p.env)
    }
    return p.val
}

force は簡単です。最初に引数 v がプロミスであることを確認します。そして、p.val が nil ならば、まだ式を評価していないので、格納してある環境 p.env で式 p.expr をメソッド Eval で評価します。最後に p.val を返します。

●たらいまわし関数

それでは、遅延評価の簡単な例題として「たらいまわし関数」を取り上げます。次のリストを見てください。

リスト : たらいまわし関数

def tak(x, y, z)
  if x <= y then
    z
  else
    tak(tak(x - 1, y, z), tak(y - 1, z, x), tak(z - 1, x, y))
  end
end

def tarai(x, y, z)
  if x <= y then
    y
  else
    tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y))
  end
end

関数 tarai や tak は「たらいまわし関数」といって、再帰的に定義されています。これらの関数は、引数の与え方によっては実行に時間がかかるため、Lisp などのベンチマークに利用されることがあります。

関数 tarai は通称「竹内関数」と呼ばれていて、日本の代表的な Lisper である竹内郁雄先生によって考案されたそうです。そして、関数 tak は関数 tarai のバリエーションで、John Macarthy 先生によって作成されたそうです。たらいまわし関数が Lisp のベンチマークで使われていたことは知っていましたが、このような由緒ある関数だとは思ってもいませんでした。

関数 tarai は遅延評価を行う処理系では高速に実行できることが知られています。tarai のプログラムを見てください。x <= y のときに y を返しますが、このとき引数 z の値は必要ありませんね。引数 z の値は x > y のときに計算するようにすれば、無駄な計算を省略することができます。なお、関数 tak は x <= y のときに z を返しているため、遅延評価で高速化することはできません。ご注意ください。

delay と force を使うと、たらいまわし関数は次のようになります。

リスト : delay と force による遅延評価

def taraiDelay(x, y, z)
  if x <= y then
    y
  else
    let zz = force(z) in
      taraiDelay(taraiDelay(x - 1, y, delay(zz)),
                 taraiDelay(y - 1, zz, delay(x)),
                 delay(taraiDelay(zz - 1, x, delay(y))))
    end
  end
end

遅延評価したい処理をプロミスにして引数 z に渡します。そして、x > y のときに引数 z のプロミスを force で評価します。すると、プロミス内の処理が評価されて z の値を求めることができます。たとえば、delay(0) を z に渡す場合、force(z) とすると返り値は 0 になります。delay(x) を渡せば、x に格納されている値が返されます。delay(taraiDelay(...)) を渡せば taraiDelay が実行されて、その値を求めることができます。

それでは、実際に実行してみましょう。

Calc> let s = clock() in println(tarai(12,6,0)), since(s) end;
12
4.077236115s
Calc> let s = clock() in println(taraiDelay(12,6,delay(0))), since(s) end;
12
222.4µs

実行環境: Julia 1.23.2, Ubunts 22.04 (WSL2), Intel Core i5-6200U 2.30GHz

tarai の場合、遅延評価の効果はとても大きいですね。

●クロージャによる遅延評価

ところで、delay と force がなくても、クロージャを使って遅延評価を行うことができます。次のリストを見てください。

リスト : クロージャによる遅延評価

def taraiClo(x, y, z)
  if x <= y then
    y
  else
    let zz = z() in
      taraiClo(taraiClo(x - 1, y, fn() zz end),
               taraiClo(y - 1, zz, fn() x end),
               fn() taraiClo(zz - 1, x, fn() y end) end)
    end
  end
end

遅延評価したい処理をクロージャに包んで引数 z に渡します。そして、x > y のときに引数 z の関数を呼び出します。すると、クロージャ内の処理が評価されて z の値を求めることができます。たとえば、fn() 0 end を z に渡す場合、z() とすると返り値は 0 になります。fn() x end を渡せば、x に格納されている値が返されます。fn() taraiClo(...) end を渡せば、関数 taraiClo が実行されてその値が返されるわけです。