この第 1 版は Lua 5.0 向けに書かれました。後のバージョンでもほとんどは関連していますが、いくつか違いがあります。
第 4 版は Lua 5.3 を対象にしており、Amazon や他の書店で購入できます。
書籍を購入することで Lua プロジェクトのサポート にもつながります。

Previous でのプログラミングLua Next
第 1 部：言語 第 6 章：ファンクションの詳細

6.3 – 適切な末尾再帰

Lua のファンクションのもう 1 つの興味深い機能は、適切な末尾再帰を行うことです。（概念的には再帰は直接関係しませんが、多くの著者たちは「適切な末尾再帰」という用語を使用しています。）

末尾再帰は goto の一種で、呼び出しとして表現したものです。ファンクションが最後の処理として別のファンクションを呼び出す、つまりそれ以降に処理すべきことが何もないときに末尾再帰が発生します。たとえば、次のコードでは、g の呼び出しは末尾再帰です

    function f (x)
      return g(x)
    end
f が g を呼び出すと、それ以降に処理すべきことは何もありません。このような場合、呼び出されたファンクションが終了しても、プログラムは呼び出し側ファンクションに戻る必要はありません。したがって、末尾再帰の後、プログラムはスタックに呼び出し側ファンクションに関する情報を保持しておく必要がありません。Lua インタープリターなどの言語実装の中には、この事実を利用し、末尾再帰を実行するときに追加のスタック領域を実際に使用しないものもあります。このような実装は適切な末尾再帰をサポートしていると言います。

適切な末尾再帰はスタック領域を使用しないため、プログラムで実行できる「入れ子」となった末尾再帰の数には制限がありません。たとえば、次のファンクションを任意の数字で引数として呼び出すことができます。スタックがオーバーフローすることはありません

    function foo (n)
      if n > 0 then return foo(n - 1) end
    end

適切な末尾再帰を使用するときの微妙な点は、末尾再帰とは何かということです。一見そう思える候補の中には、呼び出しファンクションが呼び出しの後に処理すべきことがないという基準を満たさないものがあります。たとえば、次のコードでは、g の呼び出しは末尾再帰ではありません

    function f (x)
      g(x)
      return
    end
この例のポイントは、g の呼び出し後、f は返す前に g からの不定期な結果を破棄する必要があります。同様に、次のすべての呼び出しは基準を満たしていません
    return g(x) + 1     -- must do the addition
    return x or g(x)    -- must adjust to 1 result
    return (g(x))       -- must adjust to 1 result
Lua では、return g(...) 形式での呼び出しのみが末尾再帰です。ただし、Lua は呼び出し前にこれらを評価するため、g と引数の両方が複雑な式になる可能性があります。たとえば、次の呼び出しは末尾再帰です
      return x[i].foo(x[j] + a*b, i + j)

前述の通り、末尾再帰は goto の一種です。したがって、Lua で適切な末尾再帰をかなり有用に適用できる 1 つは、ステートマシンをプログラミングすることです。そのようなアプリケーションでは、各状態をファンクションで表すことができます。状態を変更するには、特定のファンクションへ移動（または呼び出し）します。例として、簡単な迷路ゲームを考えてみましょう。迷路にはいくつかの部屋があり、それぞれに最大 4 つのドア（北、南、東、西）があります。各ステップで、ユーザは移動方向を入力します。その方向にドアがあると、ユーザは対応する部屋に移動します。そうでない場合、プログラムは警告を出力します。目標は、最初の部屋から最後の部屋に移動することです。

このゲームは典型的なステートマシンであり、現在の部屋が状態になります。各部屋に対して 1 つのファンクションを使用して、このような迷路を実装できます。ある部屋から別の部屋に移動するには末尾再帰を使用します。4 つの部屋がある小さな迷路は次のようになります

    function room1 ()
      local move = io.read()
      if move == "south" then return room3()
      elseif move == "east" then return room2()
      else print("invalid move")
           return room1()   -- stay in the same room
      end
    end
    
    function room2 ()
      local move = io.read()
      if move == "south" then return room4()
      elseif move == "west" then return room1()
      else print("invalid move")
           return room2()
      end
    end
    
    function room3 ()
      local move = io.read()
      if move == "north" then return room1()
      elseif move == "east" then return room4()
      else print("invalid move")
           return room3()
      end
    end
    
    function room4 ()
      print("congratulations!")
    end
最初の部屋を呼ぶことからゲームを開始します。
    room1()
適切なテールコールがない場合、ユーザーが動かすごとに新しいスタックレベルが作成されます。一定の移動回数を超えると、スタックオーバーフローが発生します。適切なテールコールがあれば、ユーザーが行える移動回数に制限はなく、これは各移動が実際には通常の呼び出しではなく、別の関数への goto を実行するためです。

この簡単なゲームでは、部屋や動きをテーブルで記述するデータドリブン型のプログラムが、より優れた設計であることがわかるでしょう。ただし、ゲームの各部屋で特別な状況が多数ある場合は、この状態マシン設計が非常に適切です。

著作権 © 2003–2004 Roberto Ierusalimschy. All rights reserved. Next