レキシカルスコープとダイナミックスコープ

1. レキシカルスコープとダイナミックスコープの違い

言語によって、変数のスコープに関する仕様が異なる。スコープには、レキシカルスコープとダイナミックスコープがある。採用しているスコープにより、変数の参照の仕方が違う。

レキシカルスコープでは、プログラムとして書かれた字句を解析すれば、変数のスコープを把握できる。実行時のことは考えなくて良い。これに対して、ダイナミックスコープでは、実行時における関数の呼び出され方により、参照できる変数が異なる。

用語の説明を見る前に、具体例を見た方が理解しやすい。

Scope (computer science) - Wikipedia の Lexical scoping and dynamic scoping によると、

… if function f invokes a separately-defined function g, then under lexical scoping, function g does not have access to f's local variables (since the text of g is not inside the text of f), while under dynamic scoping, function g does have access to f's local variables (since the invocation of g is inside the invocation of f).

（同上より、装飾は引用者による）

関数 f から関数 g を呼び出す場合を想定する。関数は、各々独立に定義されており、一方の関数がもう一方をネストしてないとする。

関数 f で定義されているローカル変数を、関数 g から、

1. レキシカルスコープでは、参照できない。
2. ダイナミックスコープでは、参照できる。

 

各言語が採用しているスコープ

言語によって、採用しているスコープが異なる。もしくは、両方使える。

Lexical scoping によると、

Lexical scoping is standard in all ALGOL-based languages such as Pascal, Modula2 and Ada as well as in modern functional languages such as ML and Haskell.

Dynamic scoping

Some languages, like Perl and Common Lisp, allow the programmer to choose static or dynamic scoping when defining or redefining a variable. Logo and Emacs lisp are examples of languages that use dynamic scoping.

多くの言語で、レキシカルスコープが採用されている。ダイナミックスコープを採用している言語として、Emacs Lisp がある。

 

レキシカルスコープの例

Scope (computer science) - Wikipedia に書かれていた例を、各言語で試してみる。

Python

x = 7
def g(): return x
def f(): 
    x = 9
    return g()
print f()           #=> 7

javascript

var x = 7;
function g(){ return x; }
function f(){ 
    var x = 9;
    return g();
}
f();                //=> 7

Haskell

x = 7
g = x
f = let x = 9 in g
main = print f      #=> 7

scheme

(define x 7)
(define g (lambda () x))
(define f
  (lambda ()
    (let ((x 1))
      (g))))
(f)   ;=> 7

関数 f が呼び出された後に、関数 g が呼び出されても、関数 g の中にある変数の参照先は変わらない。

レキシカルスコープの実行結果を見ると、「コレ普通じゃない？」と感じる。理由は、

Dynamic scoping によると、

dynamic scoping can be dangerous and few modern languages use it.

ダイナミックスコープは取り扱いが難しいので、モダンな言語でほとんど採用されていない。そのため、レキシカルスコープの考え方の方が馴染みがある。

 

ダイナミックスコープの例

続いて、ダイナミックスコープを採用している Emacs Lisp の例。

Emacs Lisp

(setq x 7)
(defun g () x)
(defun f ()
  (let ((x 9))
    (g))
(message "%d" (f))  ;=> 9

レキシカルスコープの言語に慣れていると、ダイナミックスコープの結果に違和感を感じる。

関数 f を呼び出した後、関数 f の中で関数 g が呼び出される。これにより、関数 g の中にある変数の参照先が変わってしまう。

もし、関数 f が呼び出されず、関数 g だけが実行されたら、

(setq x 7)
(defun g () x)
(message "%d" (g))  ;=> 7

関数の呼び出され方により、参照できる変数が変わる。実行時のことを考える必要なければならない。そのため、コード全体を見通すことが大変そう。 (+_+)

では、ダイナミックスコープにメリットはあるのだろうか？

Emacs Lisp - Wikipedia によると

Emacs Lispは、アプリケーション・プログラミングで使われる方言群であるSchemeやCommon Lispとは根本的に異なる。大きな違いの1つは、デフォルトで字句的スコープではなく動的スコープを使うことである。つまり、呼出し関数の局所変数は、ポインタや参照を渡さなくとも、呼び出された関数から参照できる。

関数から呼び出された側の関数は、自分のローカルにある変数の内容が、呼び出された文脈により変化する。

レキシカルスコープ的な視点で考えると、呼び出された側の関数は、呼び出した側の関数にネストされたかのように見える。

ところで、なぜ Emacs Lisp は、ダイナミックスコープを採用したのだろう？

Scope (computer science) - Wikipedia, the free encyclopedia によると、

Correct implementation of static scope in languages with first-class nested functions is not trivial, as it requires each function value to carry with it a record of the values of the variables that it depends on (the pair of the function and this environment is called a closure).

Dynamic scoping is fairly easy to implement. To find an identifier's value, the program could traverse the runtime stack, checking each activation record (each function's stack frame) for a value for the identifier.

レキシカルスコープより、ダイナミックスコープの方が実装が簡単とのこと。

Scope - GNU Emacs Lisp Reference Manual にも、同様のことが書かれている。

Emacs Lisp uses dynamic scoping because simple implementations of lexical scoping are slow. In addition, every Lisp system needs to offer dynamic scoping at least as an option; if lexical scoping is the norm, there must be a way to specify dynamic scoping instead for a particular variable. It might not be a bad thing for Emacs to offer both, but implementing it with dynamic scoping only was much easier.

 

2. レキシカルスコープとダイナミックスコープにおける変数の生存期間

書かれたテキストにより決まるレキシカルスコープ

Scope (computer science) - Wikipedia の Lexical scoping and dynamic scoping によると、

In lexical scoping (…), if a variable-name's scope is a certain function, then its scope is the program text of the function definition: within that text, the variable-name exists, and is bound to its variable, but outside that text, the variable-name does not exist.

レキシカルスコープでは、関数の中で定義されてる変数のスコープは、プログラムの字句によって決まる。関数の中に書かれている変数は、その関数が記述されている内側で存在するが、外側では存在しない。

 

実行時に決まるダイナミックスコープ

Scope (computer science) - Wikipedia の Lexical scoping and dynamic scoping によると、

By contrast, in dynamic scoping (or dynamic scope), if a variable-name's scope is a certain function, then its scope is the time-period during which the function is executing: while the function is running, the variable-name exists, and is bound to its variable, but after the function returns, the variable-name does not exist. （同上より）

ダイナミックスコープでは、関数の中で定義されてる変数のスコープは、その関数が実行されている期間と同じ。関数が実行されている間、変数は存在するが、関数の実行が終了すると変数は消える。

 

3. 実装から見る、名前の解決

実装の難しさ

レキシカルスコープとダイナミックスコープを実装する難しさについて、以下のように述べられている。

Lexical scoping

Correct implementation of static scope in languages with first-class nested functions is not trivial, as it requires each function value to carry with it a record of the values of the variables that it depends on (the pair of the function and this environment is called a closure).

レキシカルスコープを実装することが難しいのは、関数に対して、クロージャと呼ばれる、その関数が依存する変数（環境）を持って回る必要があるため。

Dynamic scoping

Dynamic scoping is fairly easy to implement. To find an identifier's value, the program could traverse the runtime stack, checking each activation record (each function's stack frame) for a value for the identifier. In practice, this is made more efficient via the use of an association list, which is a stack of name/value pairs. Pairs are pushed onto this stack whenever declarations are made, and popped whenever variables go out of scope.^[1]

ダイナミックスコープの実装が簡単なのは、実行中の関数に関する情報を持つスタックの中から、参照したい値を探すだけで済むため。

スタックとは、Call stack - Wikipedia によると、

Since the call stack is organized as a stack, the caller pushes the return address onto the stack, and the called subroutine, when it finishes, pops the return address off the call stack and transfers control to that address. If a called subroutine calls on to yet another subroutine, it will push another return address onto the call stack, and so on, with the information stacking up and unstacking as the program dictates.

サブルーチンを呼ぶときに、利用されるデータ構造。サブルーチンが呼び出されるとき、スタックにリターンアドレスが積まれ、呼び出されたサブルーチンが終了すると、リターンアドレスが取り出され、そのアドレスに制御が移される。

プログラムを実行するときの、メモリの利用のされ方と名称について、詳しくは、 Data segment - Wikipedia の Program memory を参照。

The computer program memory is organized into the following:

• Data Segment (Data + BSS + Heap)
• Stack
• Code segment

 

名前（識別子）の探し方

変数を参照するとき、レキシカルスコープとダイナミックスコープでは、以下の点が異なる。

Lexical scoping によると、

With lexical scope, a name always refers to its (more or less) local lexical environment. This is a property of the program text and is made independent of the runtime call stack by the language implementation. Because this matching only requires analysis of the static program text, this type of scoping is also called static scoping. …

Static scoping allows the programmer to reason about object references such as parameters, variables, constants, types, functions, etc. as simple name substitutions. This makes it much easier to make modular code and reason about it, since the local naming structure can be understood in isolation.

レキシカルスコープでは、「名前」が指し示す対象は、プログラムの字句を見れば分かる。実行時のことを考える必要ない。そのため、プログラムのテキストにおいて、参照しているものの名前を置き換えるだけで、何を指し示しているか把握できる。

Dynamic scoping によると、

With dynamic scope, each identifier has a global stack of bindings. Introducing a local variable with name x pushes a binding onto the global x stack (…), which is popped off when the control flow leaves the scope. Evaluating x in any context always yields the top binding. In other words, a global identifier refers to the identifier associated with the most recent environment. Note that this cannot be done at compile-time because the binding stack only exists at run-time, which is why this type of scoping is called dynamic scoping.

ダイナミックスコープでは、実行時に変数のような識別子があると、スタックに積まれる。その後、識別子が必要になったら、スタックに積まれている順に検索される。つまり、実行中の関数から、一番近い場所にある環境から、対象を見つけ出そうとする。

先ほどの例で考えると、

(setq x 7)
(defun g () x)
(defun f ()
  (let ((x 9))
    (g))
(message "%d" (f))  ;=> 9

1. 変数 x は 7 に束縛され、スタックに積まれる。
2. 関数 f の呼び出しにより、変数 x は 9 に束縛され、スタックに積まれる。
3. 関数 g が呼び出され、変数 x が参照される。このとき、直前にスタックに積んだ、中身が 9 の変数 x が取り出される。

これにより、結果が 9 となる。

Ruby のネストしたメソッドと、変数のスコープ

0. 目次

1. JavaScript, Haskell, Python でネストした関数を定義する
2. Ruby でネストしたメソッドは定義できるが、変数のスコープに注意
3. 内部スコープから、外部スコープを参照できない
4. トップレベルに定義したメソッドの所属先は Object
5. ネストしたメソッドの所属先は、外側のメソッドと同じクラス

 

1. JavaScript, Haskell, Python でネストした関数を定義する

2 つの値を足し合わせる関数を定義したい。

a. JavaScript

JavaScript で書くなら、

function sum(x, y){ return x + y; };
sum(1, 2);    //=> 3

JavaScript では、ネストした関数を定義できる。

JavaScript Reference - MDN の入れ子の関数とクロージャ によると、

関数の内部に関数を入れ子にする事ができます。入れ子にされた (内側の) 関数は、それを含む (外側の) 関数に対してプライベートです。それは同時に クロージャ を形成します。

• cf. JavaScript のクロージャ と オブジェクト指向

よって、次のように sum 関数を書くことができる。

function sum(x){ 
    function _sum(y){
	return x + y;
    };
    return _sum;
};
sum(1)(2);    //=> 3

sum 関数を利用するには、関数の呼び出しを 2 回行い、一つづつ引数を与える。

上記の sum 関数の定義は、最初に定義した関数をカリー化したもの。

カリー化 - Wikipedia とは、

複数の引数をとる関数を、引数が「もとの関数の最初の引数」で戻り値が「もとの関数の残りの引数を取り結果を返す関数」であるような関数にすること。

次に、ネストした関数を無名関数に変更。JavaScript で無形関数を定義するには、関数定義から名前を削除すれば良い。

JavaScript Reference - MDN の 関数を定義する によると、

function name([param[, param[, ... param]]]) {
   statements
}

name

関数名。省略する事ができ、その場合関数は無名関数と見なされます。

関数を定義するとき、`function’ と書くのは長くて面倒。しかし、無名関数の作り方は、素直でわかりやすい。

function sum(x){
    return function(y){
	return x + y;
    }
}
sum(1)(2);   //=> 3

sum 関数を、全て無名関数で定義して、実行するには、

(function(x){
    return function(y){
	return x + y;
    }
})(1)(2);     //=> 3

• cf. JavaScript の無名関数に引数を与える

 

b. Haskell

Haskell で sum 関数を定義するなら、

sum' x y = x + y
main = print $ sum' 1 2   -- 3

Haskell で関数をネストするには、let 式か、where 節を用いる。

• cf. 4.5 字句の有効範囲と入れ子形式

sum' x = sum''
    where
      sum'' y = x + y

無名関数の書き方は、The Haskell 98 Language Report の3.3 カリー化された適用とラムダ抽象 によると、

ラムダ抽象は \ p₁ ... p_n -> e と書く。ここで、p_i はパターンである。

JavaScript のように、関数定義から名前を削除したら、無名関数になる訳ではない。最初に書いた sum’ 関数の定義は、

• 4.4.3.1 関数束縛

と呼ばれる。無名関数を使った書き方と、同等であることが保証されている。

• cf. Haskell でデータコンストラクタによるパターンマッチ

ネストしている sum’’  関数を、無名関数に変更すると、

sum' x = \y -> x + y

引数 2 つの定義よりも、上記の方が、Haskell では本質的な形。

理由は、Haskell - Wikipedia によると、

Haskell において、2つの引数を持つ関数は、1つの引数をとり「1つの引数をとる関数」を返す関数と同義である。…

f x = ... x ... は、 f = (\x -> ... x ... ) のシンタックスシュガーであるとも言える。

Currying - HaskellWiki

In Haskell, all functions are considered curried: That is, all functions in Haskell take just single arguments.

このため、引数 2 つの関数束縛と、カリー化した定義は、関数を適用するとき、同じように書ける。この点、Haskell の記述はシンプルで使いやすい。

ところで、Haskell - Wikipedia によると、

Haskell の定義は変数に束縛するのが定数であるか関数であるかにかかわらず、「変数 = 値」という一貫した形でも定義できる。

JavaScript でも、関数を定義するときに、無名関数を変数に代入する形式で書くことができる。

var sum = function(x, y){ return x + y; };

• cf. Function コンストラクタか関数宣言か関数式か

Haskell で、sum 関数を全て無名関数で定義し、関数を適用するには、

main = print $ (\x -> \y -> x + y) 1 2

 

c. Python

Python でも、sum 関数を定義してみる。

def sum(x, y):
    return x + y
print sum(1, 2)    #=> 3

Python も、ネストした関数を定義できる。

実行モデル — Python 2.6ja2 documentation によると、

プログラムテキスト中に名前が出現するたびに、その名前が使われている最も内側の関数ブロック中で作成された 束縛 (binding) を使って名前の参照が行われます。

ブロック(block)は、Python のプログラムテキストからなる断片で、一つの実行単位となるものです。モジュール、関数本体、そしてクラス定義はブロックです。…

ある名前がコードブロック内で使われると、その名前を最も近傍から囲うようなスコープ (最内スコープ: nearest enclosing scope) を使って束縛の解決を行います。こうしたスコープからなる、あるコードブロック内で参照できるスコープ全ての集合は、ブロックの環境(environment)と呼ばれます。

ある名前がブロック内で束縛されている場合、名前はそのブロックにおけるローカル変数 (local variable) です。ある名前がモジュールレベルで束縛されている場合、名前はグローバル変数 (global variable) です。 (モジュールコードブロックの変数は、ローカル変数でもあるし、グローバル変数でもあります。) ある変数がコードブロック内で使われているが、そのブロックでは定義されていない場合、変数は自由変数(free variable)です。

（装飾は引用者による、以下同じ）

def sum(x):
    def _sum(y):
        return x + y
    return _sum

sum 関数を呼び出すには、引数を一つづつ渡す。JavaScript と同じ。

print sum(1)(2)    #=> 3

• cf. Python でネストした関数の定義と、呼び出し

ただし、無名関数を定義するとき、JavaScript のように関数から名前を削除する、という書き方はできない。よって、以下はエラーとなる。

def sum(x):
    return def(y):
        return x + y

無名関数を書くには、ラムダ形式を利用する。

def sum(x):
    return lambda y: x + y

関数の呼び出し方は、ネストした関数と同じ。

全てラムダ形式で定義し、実行するには、

print (lambda x: lambda y: x + y)(1)(2)

 

2. Ruby でネストしたメソッドは定義できるが、変数のスコープに注意

Rubyでも、同様に sum メソッドを定義してみる。

def sum(x, y)
  x + y
end
p sum(1, 2)    #=> 3

他の言語と同じように、ネストしたメソッドを定義することができるだろうか？

def sum(x)
  def _sum(y)
    x + y
  end
  _sum
end
p sum(1)(2)

しかし、これは sum メソッドを呼び出した時点で

syntax error

となる。

また、sum メソッドを引数一つにして呼び出した場合、_sum の呼び出しで、

「引数の数が違う」

とエラーがでる。

 

a. 手続きオブジェクトを使い、外側の変数を参照

これに対処するには、ネストしたメソッドの代わりに、手続きオブジェクトを利用しなければならない。

手続きオブジェクトは、Proc.new で生成するか、もしくは、以下の形式を使う。

lambda{ } または proc{ ]

def sum(x)
  lambda{|y| x + y}
end
p sum(1).call(2)

• cf. Ruby の関数オブジェクト - Proc とブロックの使い方

上記では、sum メソッドの呼び出しにより、手続きオブジェクトが返される。手続きオブジェクトに引数を渡して、計算を行わせるには、call メソッドを呼び出す。call メソッドを書くのが面倒なら、

[]

を使えばよい。

p sum(1)[2]

ただし、[] による手続きオブジェクトの呼び出しは、配列の要素を参照するメソッドと被るので、あまり好きではない。

• cf. callを省略する (via Rubyの呼び出し可能オブジェクトの比較(1) - 世界線航跡蔵)

全て無名関数で書くなら、

p lambda{|x| lambda{|y| x + y }}.call(1).call(2)
p lambda{|x| lambda{|y| x + y }}[1][2]

やはり、スッキリとした書き方とは思えない。(+_+)

 

b. ネストしたメソッドから、外側の変数を参照できない

Ruby では、他の言語のように、ネストしたメソッドは定義できないのだろうか？

メソッド定義のネスト によると、

ネストされた定義式は、それを定義したメソッドが実行された時に定義されます。

ドキュメントにこのように書かれているので、定義することはできるようだ。

「実行されたときに定義される」

という性質は、Ruby のクラスとインスタンス変数の関係に似ている。

メタプログラミングRuby

メタプログラミングRuby , p45 によると、

Ruby ではオブジェクトのインスタンス変数はクラスと何のつながりもない。インスタンス変数は値を代入したときに初めて出現する。

例えば、 以下の Person クラスのインスタンス変数 @name は、name メソッドを呼び出さなければ、存在しない。

class Person
  def name
    @name
  end
  def name=(name)
    @name = name
  end
end

person = Person.new
p person.instance_variables   #=> []

person.name = "Tarou"
p person.instance_variables   #=> [:@name]

• cf. Object#instance_variables
• Module#attr_accessor

ネストしたメソッドは定義できる。そのため、下記のコードを実行しても、エラーがでなかった。

def sum(x)
  def _sum(y)
    x + y
  end
end

不思議なことに、ネストされた _sum メソッドは、トップレベルから呼び出すことができる。呼び出した結果、

「メソッド内の x が、ローカル変数でもメソッドとしても定義されてない

という内容のエラーが表示された。

NameError: undefined local variable or method `x' for main:Object

class NameError は、

未定義のローカル変数や定数を使用したときに発生します。

_sum メソッドを呼び出したとき、そのスコープに変数 x は存在しない。

他の言語のように、ネストした関数と同じつもりで書くことはできない。

 

3. 内部スコープから、外部スコープを参照できない

内側のメソッドから、外側のメソッドの変数を参照できなかった。理由は、Ruby のスコープの仕様による。

メタプログラミングRuby によると、

Java や C# と言った言語には、「内部スコープ」から「外部スコープ」の変数を参照できる仕組みもあるが、Ruby にはこうした可視性の入れ子構造は存在せず、スコープはきちんと区別されている。新しいスコープに入ると、束縛は新しい束縛と交換される。（p113）

プログラムがスコープを切り替えて、新しいスコープをオープンする場所は 3 つある。

• クラス定義
• モジュール定義
• メソッド呼び出し

… この3つの境界線は、class, module, def といったキーワードで印が付けられている。3つのキーワードはそれぞれスケープゲートのように振る舞う。（p115）

クラスやモジュールの定義のコードはすぐに実行される。一方、メソッド定義のコードは、メソッドを呼び出したときに実行される。（p116）

メソッドに関連した箇所を、まとめると、

1. キーワード def によるメソッドの定義は、メソッドの呼び出しのときに実行される。
2. メソッドの呼び出しにより、新しいスコープに切り替わる。
3. つまり、ネストしたメソッドが実行されるとき、新しいスコープに切り替わり、外側のスコープの変数を参照できない。

 

フラットスコープ

ちなみに、class, module, def によるスコープの制約を超えて、変数を参照したい場合、

• Class.new
• Module.new
• Module#define_method()

を利用する。これを

「フラットスコープ」

と呼ぶそうだ。( メタプログラミングRuby, p118)

 

4. トップレベルに定義したメソッドの所属先は Object

先ほどの sum メソッドは、トップレベルに定義した。Ruby では、トップレベルに定義するメソッドは、関数定義のように見える。Java のように、main メソッドを持つ、特別なクラスを作成する必要がない。

では、トップレベルに定義したメソッドは、どこに所属するのだろう？

その手がかりは、特殊な変数である self

「現在のメソッドの実行主体」

（変数と定数 より）

にある。

メタプログラミングRuby によると、

Ruby のコードはオブジェクト（カレントオブジェクト）の内部で実行される。カレントオブジェクトは self とも呼ばれる。self キーワードでアクセスできるからだ。…

メソッドを呼び出すときは、レシーバが self になる。…

レシーバを明示せずにメソッドを呼び出すと、全て self に対するメソッドの呼び出しになる。 (p63)

自分が Ruby の小さなデバッガになったと考えてみよう。ブレークポイントに当たるまで命令文を次々に渡っていくとする。さて、一息ついて、周りを見てみよう。どんな景色が見えるだろうか？それがあなたのスコープだ。

スコープ一面に束縛があるはずだ。足元をみると、ローカル変数がいくつもある。顔を見上げると、自分がオブジェクトの中に立っていることに気づく。傍にはメソッドとインスタンス変数がいる。ここがカレントオブジェクト、つまり self だ。遠くのほうに定数のツリ－がはっきりと見える。これで自分の位置が把握できた。目を細めてもっと遠くを見ると、グローバル変数がたくさん見える。(p112)

例えば、Person クラスを定義し、class 定義と、メソッドの定義の中で self を出力してみる。

class Person
  p self               #=> Person
  def initialize(name)
    p self             #=> <Person:0x2252928>
    @name = name
  end
end

tarou = Person.new("Tarou")

クラス定義内では、Person クラスが実行主体となる。メソッド内では、Person クラスのインスタンスが実行主体となる。

先ほどの sum 関数において、同様に self を出力すると、main と表示される。

p self         #=> main

def sum(x)
  p self       #=> main
  def _sum(y)
    x + y
  end
end

sum(1)

main とは、第1章 Ruby言語ミニマム によると、

… 実はRubyプログラム実行中はどこにいようとselfが設定されている。つまりトップレベルにもクラス定義文にもselfがあるのだ。

例えばトップレベルでもselfがある。トップレベルのselfは、mainという。なんの変哲もない、Objectクラスのインスタンスだ。…

… トップレベルのself即ちmainはObjectのインスタンスなので、トップレベルでもObjectのメソッドが呼べるということになる。そして ObjectにはKernelというモジュールがインクルードされており、そこで pやputsなどの「関数風メソッド」が定義されている（図10）。だからこそトップレベルでもpやputsが呼べるのだ。

図10: mainとObject、Kernel

Rubyが抱える課題、NaClの前田氏が講演 － ＠IT

多くの言語では、トップレベルの関数（メソッド）にはレシーバーがないが、Rubyではトップレベルで関数を定義すると、それは暗黙的にmainオブジェクトの”関数的”メソッドとして定義される。Rubyではすべてがメソッドで、動的束縛を行うためメソッド探索のコストがかかる。

トップレベルに定義するメソッドは、Object クラスのメソッドとなる。Ruby のトップレベルは、Java における main メソッドを持ったクラスの中のようなもの。

• cf. Rubyのオブジェクトは生物なんかじゃない、トップレベルこそが生物なんだ！ - hp12c
• What is the Ruby Top-Level? « Like Dream of Banister Fiend

 

5. ネストしたメソッドの所属先は、外側のメソッドと同じクラス

a. Ruby を構成する基本的な要素

ところで、Ruby では「オブジェクト」が、プログラムの基本的な要素として扱われる。

オブジェクト によると、

Ruby で扱える全ての値はオブジェクトです。 Ruby のオブジェクトに対して可能な操作はメソッド呼び出しのみです。あるオブジェクトが反応できるメソッドは、そのオブジェクトが所属するクラスによって一意に決定します。

Ruby に純粋な関数は存在しない。関数のように見える記述も、全てオブジェクトのメソッド。

クラスもオブジェクトとして扱われる。先ほど、Person クラスの定義の中で、self を出力したとき、クラス名である

Person

が表示された。このとき、実行主体はクラスを表すオブジェクト。Java のように「静的なクラス定義と、実行中の動的なオブジェクトが別の世界にある」イメージとは趣が違う。

Person クラスは、Class クラスのインスタンス。self に対して、Object#class を呼び出せば、所属するクラスを確認できる。詳しくは、以下を参照。

メタプログラミングRuby, p46、

オブジェクトの内部には、インスタンス変数とクラスへの参照があるだけだ。…メソッドは、オブジェクトじゃなくて、クラスにあるんだ。…

クラスはオブジェクトである。… クラスは Class クラスのインスタンスなのだ。

• cf. class Class
• メタクラス - Wikipedia
• Metaclass - Wikipedia
• Rubyのメタクラス階層 - 世界線航跡蔵

オブジェクトはクラスに所属し、クラスはメソッドを持つ。逆に言えば、メソッドは必ずどこかのクラスに所属する。よって、ネストしたメソッドも、所属先のクラスがある。

では、ネストしたメソッドは、どのクラスに所属するのだろう？

 

b. コンテキスト

メソッドの評価 によると、

引数のデフォルト式も含め、すべてそのメソッドのコンテキストで評価されます。

コンテキストとはなんだろう？Ruby のリファレンスマニュアルを読んでいると、「コンテキスト」という言葉を、しばしば見かける。

例えば、Object#instance_eval 。

オブジェクトのコンテキストで文字列 expr またはオブジェクト自身をブロックパラメータとするブロックを評価してその結果を返します。

オブジェクトのコンテキストで評価するとは評価中の self をそのオブジェクトにして実行するということです。

• cf. クエリ:コンテキスト | るりまサーチ

Person クラスに、name 属性と、与えられたブロックを実行するだけのメソッド test を定義する。

class Person
  attr_accessor :name
  def test
    yield
  end
end

このクラスを使い、instance_eval を呼び出すときに、self を出力。

tarou = Person.new
tarou.name = "Tarou"
tarou.instance_eval{
  p self     #=> #<Person:0x232d640 @name="Tarou">
  p @name    #=> "Tarou"
}

instance_eval メソッドにおけるブロックの self が、レシーバーのインスタンスとなっている。

次に、test メソッドで self を呼び出したときと、上記を比較してみる。

tarou.test{ 
  p self     #=> main
  p @name    #=> nil
}

test メソッドのブロックでは、self がトップレベルのオブジェクトである main となる。よって、インスタンス変数 name を参照しても、nil となる。なぜなら、main オブジェクトに name 属性を設定していないため。

同じ内容のブロックでも、コンテキストが変化することにより、評価の結果が異なる。

Rubyの呼び出し可能オブジェクトの比較 (2) - というよりコンテキストの話 - 世界線航跡蔵 によると、

コンテキストとはおおざっぱに言えばローカル変数の状態、self, klassから成る。

ここでローカル変数というのは、参照できる限り外側のスコープも含めた全部だ。selfというのはデフォルトでメソッドを受け取る相手である。Rubyのプログラムにはいつでもselfがいて、擬似変数selfを通じてアクセスできるのであった。

Rubyの呼び出し可能オブジェクトの比較 (3) - なんかklassの話 - 世界線航跡蔵

… Rubyでは、メソッドはselfに定義されると考えたくなるが、そうではない。実はこれが前に名前だけ触れたklassである。klassは正式な用語ではなく、この記事では仮にそう呼ぶというだけである。…

Rubyレベルでは表にあわれないがRuby処理系は内部でここでいうklassを常に保持している。これは「今メソッドを定義したらどこに定義されるか」というクラスである。この存在を考えるとRuby文法の理解がすっきりする。

トップレベルでは"main"と呼ばれるある特定のObjectインスタンスがselfなのに、トップレベルでメソッドを定義するとObjectのインスタンスメソッドになる。defの中に更にdefを書くと、それらのdefを含むクラスのインスタンスメソッドになる。メソッドは「selfに対して」定義されるわけではないのだ。

… トップレベルではselfはmainで、klassはObjectだ。class文に入るとselfは構築中のクラスのClassオブジェクトになり、 klassも同じになる。defの中を評価するときは(メソッドを実行するときは)selfはレシーバーで、klassはレシーバーのクラスである。

また、第14章 コンテキスト によると、

典型的な手続き型言語のイメージだと、手続き呼び出しのたびに、ローカル変数領域や戻る場所など手続き一つの実行のために必要な情報を構造体（スタックフレーム）に格納し、それをスタックに積む。…

… Rubyでは…理由がいろいろあって、スタックはなんと七本もある。…

スタックとして、メソッド定義先クラスを管理する ruby_class 、ローカル変数スコープを管理する ruby_scope などがあるとのこと。

ruby_classはdefでメソッドを定義するときに対象となるクラスを表す。普通のクラス定義文ではselfがそのクラスになるのでruby_class == selfだが、トップレベルやeval、instance_evalという特殊なメソッドの途中では self != ruby_classになることがある。  （同上より）

ruby_scopeはローカル変数スコープを表すスタックである。メソッド・クラス定義文・モジュール定義文・特異クラス定義文などが独立したスコープだ。（同上より）

 

c. トップレベルのネストしたメソッドは、Object クラスに所属する

上記から sum メソッドについて考えると、

1. トップレベルに定義した sum メソッドが評価されることにより、self は main で、メソッドの定義先は Object となる。
2. 「メソッドの評価は、すべてそのメソッドのコンテキストで評価される。」よって、ネストしたメソッドを評価するとき、外側のメソッド定義先クラス ruby_class は変わらないが、キーワード def により、ローカル変数スコープ ruby_class が刷新されるのではないか？
3. つまり、ネストしたメソッド _sum のコンテキストは、self は main で、メソッドの定義先は Object となる。しかし、外側のメソッドのローカル変数を参照することはできない。

簡単にいえば、外側のメソッドと同じレジーバーのクラスに、ネストしたメソッドが追加される。よって、トップレベルでネストしたメソッドを定義すると、Object クラスのメソッドになる。そのため、トップレベルではレシーバーを省略して _sum メソッドを呼び出すことができた。

例えば、適当にトップレベルにネストしたメソッドを定義し、呼び出しを行なってみる。

def add1(x)
  def add2(y)
    y + 2
  end
  x + 1
end

p add1(100)    #=> 101
p add2(100)    #=> 102

トップレベルの main オブジェクトに add1, add2 メソッドが定義されたのが分かる。

 

d. クラス定義におけるネストしたメソッドは、そのクラスに所属する

次に、トップレベルでネストしたメソッドを定義した場合と、クラスで定義した場合を比較する。

最初に書いた Person クラスで、ネストしたメソッドを定義し、呼び出してみる。Person#initialize 内に age メソッドを定義。

class Person
  p self               #=> Person
  def initialize(name, age)
    p self             #=> <Person:0x2201b08>
    @name, @age = name, age
    def age
      p self           #=> <Person:0x2201b08 @age=30, @name="Tarou">
      @age
    end
  end
end

tarou = Person.new("Tarou", 30)
p tarou.age  #=> 30

結果、initialize メソッドの内側に定義された age メソッドは、Person クラスのメソッドとして呼び出せた。つまり、ネストしたメソッドは、外側のメソッドが所属するクラスに属する。

ところで、このように書けるメリットはあるのだろうか？あるメソッドを実行したときに、新規にメソッドを追加したり、別のメソッドを上書きして、挙動を変化させることに意味が見いだせれば、使いどころがある。ただし、内側に定義したメソッドにおいて、自由変数を使えないのはデメリットな気がする。

 

e. ネストしたメソッドの、呼び出し制限の違い

あるオブジェクトに定義されたメソッドを、調べるためのメソッドが、Object, Module クラスに定義されている。

Object#methods

そのオブジェクトに対して呼び出せるメソッド名の一覧を返します。このメソッドは public メソッドおよび protected メソッドの名前を返します。

上記のメソッドでは、private メソッドは含まれないことに注意。Object#methods 以外に、以下のメソッドが定義されている。

• Object#public_methods
• Object#protected_methods
• Object#private_methods

Module#instance_methods

そのモジュールで定義されている public および protected メソッド名の一覧を配列で返します。

上記と同じく、private メソッドは含まれな。Module#instance_methods 以外に、以下のメソッドが定義されている。

• Module#public_instance_methods
• Module#protected_instance_methods
• Module#private_instance_methods

これらのメソッドを使い、先ほどトップレベルに定義した add1, add2 メソッドを調べてみる。

p self.methods.grep /add1/   #=> []
p self.methods.grep /add2/   #=> []

p self.private_methods.grep /add1/  #=> [:add1]
p self.private_methods.grep /add2/  #=> [:add2]

add1, add2 メソッドは、main オブジェクトのプライベートメソッドとして追加されているのが分かる。

これに対して、先ほどの Person クラスに追加した age メソッドについて確認すると、パブリックメソッドとして追加されていた。

p tarou.methods.grep /age/           #=> [:age]
p tarou.public_methods.grep /age/    #=> [:age]

トップレベルに定義されたメソッドと、クラス内に定義されたメソッドで、呼び出し制限に一貫性がないのはなぜだろう？

 

f. ネストしたメソッドを Method オブジェクトとして取り出す

最後に、ネストしたメソッドを、Method オブジェクトとして取り出してみる。

class Method とは、

Object#method によりオブジェクト化されたメソッドオブジェクトのクラスです。

メソッドの実体（名前でなく）とレシーバの組を封入します。 Proc オブジェクトと違ってコンテキストを保持しません。

先ほどの add2 メソッドを Method オブジェクトとして取り出す。

add = self.method :add2
p add.call(100)   #=> 102
p add[100]        #=> 102

Person クラスの age メソッドも取り出してみる。

tarou = Person.new("Tarou", 30)
age = tarou.method :age
p age.call        #=> 30
p age[]           #=> 30

• cf. Rubyの呼び出し可能オブジェクトの比較(1) - 世界線航跡蔵

 

参考記事

• Ruby で簡単なテキスト処理

参考サイト

• Scope (computer science) - Wikipedia

参考書籍

メタプログラミングRuby, p110

ブロックは単体では実行できない。コードを実行するには、ローカル変数、インスタンス変数、self といった環境が必要になる。…

ブロックを定義すると、その時その場所にある束縛を取得する。ブロックをメソッドに渡すときは、その束縛も一緒に持っていく。

Ruby, JavaScript, Python で既存のクラスを拡張 - オープンクラス(モンキーパッチ) と Scala の暗黙の型変換

1. 「リストの要素を取得する」関数を例として、クラスの拡張を考える

Lisp でリストの先頭要素を得る関数は car 。先頭以外の残りの要素を取得するには cdr 。

(car '(1 2 3 4 5))   => 1
(cdr '(1 2 3 4 5))   => (2 3 4 5)

( cf. CAR and CDR – Wikipedia )

Haskell で上記に相当する関数は、

• head
• tail

類似した対照的な関数に

• init
• last

がある。

main = do let xs = [1..5]
          print $ head xs   -- 1
          print $ tail xs   -- [2,3,4,5]
          print $ init xs   -- [1,2,3,4]
          print $ last xs   -- 5

これらの関数名を、他の言語でも使えるように、拡張の方法をそれぞれ見ていく。

 

2. Ruby で組み込みのクラス Array を拡張

Ruby で同様の関数名を探すと、Array クラスに要素一つを取得する関数

• first
• last

が見つかる。

first -> object | nil

配列の先頭の要素を返します。要素がなければ nil を返します。

first(n) -> Array

先頭の n 要素を配列で返します。n は 0 以上でなければなりません。

[PARAM] n:

取得したい要素の個数を整数で指定します。

複数の要素を取得するには、引数に要素数を与える関数も定義されている。これは last も同じ。

ところで、Haskell と同じ関数名で呼び出したい場合、Ruby には既存のクラスを拡張する方法が用意されている。

「まつもと直伝 プログラミングのオキテ 第21回 オープンクラスとRuby on Rails」によると、

Rubyでは既存のクラスに定義を追加できます。…

後から機能を追加できるクラスのことを「オープンクラス」と呼びます。

既存の Array クラスを拡張するには、同クラスを定義する要領で行えばよい。

class Array
  alias :head :first

  def tail
    last(length-1)
  end

  def init
    first(length-1)
  end
end

xs = (1..5).to_a

p xs.head   #=> 1
p xs.tail   #=> [2, 3, 4, 5]
p xs.init   #=> [1, 2, 3, 4]
p xs.last   #=> 5

他の言語から考えると、既存のクラスを変更できることは過激な仕様に見える。なぜなら、既に存在するクラスは、ある種グローバルで固定的な定数のようなイメージを持っていたため。

よって、オープンクラスを利用したら、変更を把握しておくためのコストが発生する。

デメリットは，オープンクラスには悪影響を及ぼす可能性があることです。オープンクラスはクラスライブラリの状態を大きく変更してしまうので，プログラム全体に影響を与えてしまいます。 …

複数のライブラリがオープンクラスを使って既存のクラスを変更した場合，お互いに矛盾があると回避する方法が存在しません。…

オープンクラスを利用したライブラリを使うときには，ライブラリ同士がお互いに矛盾しないかどうかをよく吟味する必要があります。…

(同上より)

オープンクラスの別名は モンキーパッチ – Wikipedia

オリジナルのソースコードを変更することなく、実行時に動的言語(例えばSmalltalk, JavaScript, Objective-C, Ruby, Perl, Python, Groovy, など)のコードを拡張したり、変更したりする方法である。…

当初はモンキーパッチは、ルールを無視して実行時にこっそりとコードを変更することから、ゲリラパッチと呼ばれていた。これらのパッチを複数当てると、時折直感に反するような相互作用が生まれることがあり、Zope 2では、交戦中のパッチと呼ばれていた。

モンキーの語源はおもしろい。 ^^;

ゲリラとゴリラは同音異字に近かったため、何人かの人がゲリラパッチの代わりにゴリラパッチという間違った用語を使用し始めた。交戦することのないゲリラパッチを開発者が作成するのが非常に難しかったため、より弱そうに聞こえるモンキーパッチという用語が作られることになった。^[2]

 

3. JavaScript で既存の Array オブジェクトのプロトタイプを拡張

上記のような Ruby の仕組みは、プロトタイプベース的な性質と考えておけばいいのかな？

プロトタイプベースの言語と言えば JavaScript 。

Array オブジェクトのプロトタイプに head, tail, init, last を定義するなら、

Array.prototype.head = function(){ return this[0]; };
Array.prototype.tail = function(){ return this.slice(1); };
Array.prototype.init = function(){ return this.slice(0,this.length-1); };
Array.prototype.last = function(){ return this[this.length-1]; };

var ary = [1,2,3,4,5];
console.log(ary.head());   // 1
console.log(ary.tail());   // [2, 3, 4, 5]
console.log(ary.init());   // [1, 2, 3, 4]
console.log(ary.last());   // 5

• Array, prototype - MDC Docs
• JavaScript のハッシュとオブジェクト

 

4. Python で既存のクラスを拡張

組み込みクラスは拡張できない

Python では組込みクラスに手を出せない。

例えば「リスト」。

• type 関数

で任意のリストに適用すると、返される値は

list

この list に属性を追加しようとすると、TypeError となる。

>>> list.x = 100
Traceback (most recent call last):
  File "", line 1, in 
TypeError: can't set attributes of built-in/extension type 'list'

つまり、list を拡張することはできない。

これに対処するには、組込みクラスを拡張することを諦め、リストをサブクラス化したものを使う。

(cf. ruby vs python | Lambda the Ultimate )

class List(list):
    def head(self):
        return self[0]

    def tail(self):
        return self[1:]

    def init(self):
        return self[0:-1]

    def last(self):
        return self[-1]

xs = List(range(1,6))

print xs.head()   #=> 1
print xs.tail()   #=> [2, 3, 4, 5]
print xs.init()   #=> [1, 2, 3, 4]
print xs.last()   #=> 5

 

ユーザが定義したクラスは、実行時に振舞いを変えることができる

ただし、ユーザが定義したクラスでは、後からメソッドを追加できる。

例えば、Ruby でユーザ定義したクラス Person に後からメソッドを追加するには、class 定義を繰り返せばよい。

class Person
    def initialize(name)
      @name = name
    end
end

ps = Person.new("Tarou")
p ps

class Person
  attr_accessor :age
end

ps.age = 30
p ps

ちなみに、Ruby が奇妙な言語だとはじめて感じたのは、この定義の仕方を見たとき。 class の定義が一つの場所に固定されてない。 Java であるなら、クラス定義は一箇所に限定され、実行時にそれが変化することはない。

この点に関して、「メタプログラミングRuby」 (p41) では class の役割について、わかりやすく説明されている。

Ruby の class キーワードは、クラス宣言というよりもスコープ演算子のようなものである。もちろん、存在しないクラスは作成する。しかしそれは、副作用と言ってもいいかもしれない。 class の主な仕事は、あなたをクラスのコンテキストに連れていくことである。そのコンテキストであなたがメソッドを定義する。

(太字は引用者による)

同様のことを、Python で書く場合は、

1. クラスを定義
2. 引数を一つ与える関数を別に定義
3. 上記関数をクラスの属性として設定

( cf. 和訳 : なぜPythonのメソッド引数に明示的にselfと書くのか | TRIVIAL TECHNOLOGIES on CLOUD )

class Person:
    def __init__(self, name):
        self.name = name

def setAge(self, age):
    self.age = age

p = Person("Tarou")

Person.setAge = setAge
p.setAge(30)

print p.name
print p.age

 

5. Scala の暗黙の型変換は、既存のクラスを拡張したように見せかける

Scala では implicit conversion を利用すると、既存のクラスを拡張したように見せかけることができる。 implicit converson は、コンパイラがあるクラスのオブジェクトを別のクラスに自動的に変換してくれる機能。

定義の仕方は、

1. 変換元のクラスをラップしたクラスを定義。
2. 上記クラスに「拡張すると想定したメソッド」を定義。
3. implicit def により、変換元から変換先を指定。

書き方は以下の通り。

implicit def 適当な名前(変換元のクラス) = 変換先のクラス

これにより、変換元のクラスに対して「拡張したと想定したメソッド」を呼び出したとき、コンパイラが自動的に変換先のクラスにしてくれる。

例えば、Scala の List クラスを拡張し、head, tail に相当するメソッド「先頭, 尾部」を定義したかのように見せかける。

class ListWrapper[T](xs : List[T]){ 
  def 先頭: T = xs.head
  def 尾部: List[T] = xs.tail
}

implicit def list2ListWrapper(xs: List[Any]) = new ListWrapper(xs)

val xs = Range(1,6).toList
println(xs.先頭)   // 1
println(xs.尾部)   // List(2, 3, 4, 5)

( cf. Ruminations of a Programmer: Why I like Scala's Lexically Scoped Open Classes )

コード上では、リストに対してメソッドを拡張したかのように見える。

 

6. Haskell はクラスとメソッドという関係がないので、自由に拡張できる

Haskell では、クラスとメソッドが結合している関係が存在しないので、既存のクラスを拡張という概念がそもそも存在しない。同様のことをしたいなら、単純に適用したい型を引数に与える関数を定義すればいい。

car, cdr をリストに対して適用できるようにするには、

car :: [a] -> a
car (x:_)  = x

cdr :: [a] -> [a]
cdr (_:xs) = xs

別名を付けるだけなら、

car = head
cdr = tail

 

オブジェクトは関数とデータ構造が密結合している

これを見て、「Why OO Sucks」のオブジェクト指向に対する批判を思い出した。

Objection 1 - Data structure and functions should not be bound together

Objects bind functions and data structures together in indivisible units. I think this is a fundamental error since functions and data structures belong in totally different worlds.

( cf. Matzにっき(2007-04-12) )

Haskell でリストの要素を swap する 9 つの方法

0. Python でリストの要素を swap する方法

Python で「リストの特定のインデックス i, j の要素を swap したい」場合、以下のように書ける。

def swap(i, j, ary):
    tmp    = ary[i]
    ary[i] = ary[j]
    ary[j] = tmp

要素を交換するために、一時的に値を退避させておく変数 tmp を利用し、要素を上書き。

多重代入を使うなら、一時変数を省略できる。

ary[i], ary[j] = ary[j], ary[i]

こういった操作ができるのは、Python ではリストが「変更可能なシーケンス型」として定義されているため。

では、同様のことを変数の更新ができない Haskell ではどのように書けばよいのか？

 

1. データコンストラクタによる分解と take, drop 関数を使う

例えば、具体的に 0 ～ 7 を要素に持つリストの 2 番目と 5 番目の要素を交換したい場合で考える。

典型的なリスト処理は、リストをデータコンストラクタで分解し、要素を先頭から末尾へと辿る。

先頭の要素 0 から見て、交換したい要素の位置は 2 番目と 5 番目。これを一つ後ろに進め、要素 1 から見た場合、交換したい要素の位置は 1 番目と 4 番目になる。同じように要素 2 から見たら、0 番目と 3 番目。

つまり、先頭から末尾へと視点を移していくと、交換したい要素の位置が相対的に変化する。これを利用して swap 関数を考えればよい。

交換したい要素の小さい方のインデックスが 0 より大きい場合は、元の要素をそのまま返す。データコンストラクタで (x:xs) のように分解したとき、リスト xs に対しては swap する位置を 1 ずつ変化させて再帰的に定義。

swap i j (x:xs)     = x : swap (i-1) (j-1) xs

次に、交換したい要素の小さい方のインデックスが 0 となった場合。以下のように区分けすれば take, drop 関数を組み合わせればよいことがわかる。

swap 0 j xs'@(x:xs) = xs' !! j : take (j-1) xs
                      ++ x : drop j xs

全体は gist: 940061 — Gist

 

2. スライスしてから結合

別の方法としては、予め特定のインデックス間の要素をスライスする関数をしておき、下図の黄色の部分を取得した後、 swap する要素を結合して、最後に全体を合わせる。

slice 関数は、ライブラリに定義されている splitAt 関数を利用して定義。

slice i j = snd . splitAt i . fst . splitAt (j+1)

これを使い、

swap i j xs = let a = slice' 0     (i-1)
                  b = slice' (i+1) (j-1)
                  c = slice' (j+1) (length xs - 1) 
              in a ++ (xs!!j):b ++ (xs!!i):c
    where
      slice' i j = slice i j xs

全体は gist: 940063 — Gist

 

3. 累積変数でインデックスを付ける

Python のリストはインデックスが付いている。しかし、Haskell のリストは付いていない。インデックスが利用できれば swap 関数を考えやすいのではないかな？

累積変数でインデックスを代替する方法を考える。

swap i j xs0 = swap' 0 xs0
    where
      swap' idx [] = []
      swap' idx (x1:xs1) | idx == i  = xs0 !! j : swap''
                         | idx == j  = xs0 !! i : swap''
                         | otherwise = x1       : swap''
          where
            swap'' = swap' (idx+1) xs1

gist: 940091 — Gist

 

4. zip 関数でインデックスを付け、累積変数を使い末尾再帰

インデックスを付けるなら、累積変数を使うよりも zip 関数を使う方が楽。予めインデックス付けしてから関数を適用する方法に変更してみる。

ついでなので、累積変数 acc を利用し、末尾再帰で定義。

swap i j xs0 = swap' [] withIdx
    where
      withIdx = zip [0..] xs0

      swap' acc []                         = reverse acc
      swap' acc ((idx,x1):xs1) | idx == i  = swap' ((xs0!!j):acc) xs1
                               | idx == j  = swap' ((xs0!!i):acc) xs1
                               | otherwise = swap' (x1:acc)       xs1

gist: 940084 — Gist

 

5. 畳み込み関数

データコンストラクタでリストを分解し、順に要素を辿っていくのなら、畳み込み関数を使った方がスッキリと書ける。

累積変数 acc を用意し、そこへ要素を追加すると伴に、インデックスを更新していく。

swap i j xs = reverse $ fst $ foldl f ([],0) xs
    where
      f (acc, idx) x | idx == i  = (xs!!j:acc, idx+1)
                     | idx == j  = (xs!!i:acc, idx+1)
                     | otherwise = (x:acc, idx+1)

gist: 940099 — Gist

 

6. map 関数でシンプルに

考えてみたら、データコンストラクタによる分解、累積変数、畳み込み関数とか面倒なことを考えなくても、map 関数で個々の要素を変換する方法が一番考えやすくないかな？

swap i j xs = swap' withIdx
    where
      withIdx = zip [0..] xs
      
      swap' = map f
          where
            f (idx, x) | idx == i  = xs !! j
                       | idx == j  = xs !! i
                       | otherwise = x

gist: 940129 — Gist

 

7. オブジェクト指向的に考える

実は、一番最初に考えた方法は全然違う。オブジェクト指向で考える方が馴染みがあるので、個々の要素に自分で考えてもらう方が自然な感じがする。

頭に入れておくことは、個々の要素が把握できる情報を、

• 自分の持っている値
• 自分よりも後ろにあるリスト

の 2 つだけだと制約を付けて考えること。

イメージしやすいように、リストを一方向リストで描く。

リストをデータコンストラクタの分解により、先頭から末尾のリストへと次々に swap 関数を適用していくことをイメージする。

swap 0 3 xs となったとき、リスト xs は自分の持っている値 (先頭要素) が swap 対象であることを知る。ここから後ろのリストに対して、この要素が保持する値を swap する値を取得したい。この役割を担うのが関数 idxAt 。

idxAt を後方のリストに対して次々に適用していく。

目的の要素に辿り着いたら、その値を返す。

これで swap するための片方の値 5 を取得できた。

次に、先ほどの swap 0 3 xs のときに戻り、もう片方の値を swap するため、後方のリストへ自分が保持する値 2 を渡していく。この役割を担うのが関数 set 。

後ろのリストへ set 関数を適用していく。

目的の要素に辿り着いたら、要素を置き換える。

以下が上記を実現したコード。

swap 0 j (x:xs) = idxAt (j-1) xs : set x (j-1) xs
    where
      idxAt 0 (x:_) = x
      idxAt j (_:xs) = idxAt (j-1) xs

      set x 0 (_:ys) = x:ys
      set x j (y:ys) = y:set x (j-1) ys

swap i j (x:xs) = x : swap (i-1) (j-1) xs

gist: 940153 — Gist

 

8. State モナド (1)

全く別の方法として、効率も何もかも無視し、「状態の変更」という視点から State モナドを利用したらどう書けるか試す。

さて、何をどう考えればいいのか？

下図のように想定する。

• 内容が変更されると想定する「リスト」と「一時変数」を用意

これが時刻 t0 ～ t3 において、以下のように変化すると考える。

1. 時刻 t0 : リストを swap する前の状態。
2. 時刻 t1 : 一時変数にリストの 2 番目の要素を代入する。
3. 時刻 t2 : リストの 2 番目の要素を 5 番目の要素で上書き。
4. 時刻 t3 : リストの 5 番目の要素を一時変数の値で上書き。

時刻 t0 における「リスト」と「一時変数」の状態を、時刻 t1 の状態に変更する関数を f1 とする。( 以降それぞれ f2, f3 と仮定。 )

State モナドを利用する場合、型を合わせるために「状態を変更する関数」を

s –> (a, s)

という型であると想定する必要がある。

関数 f1 ～ f3 の関数を上記の型に合うように考えるなら、

f1 :: ([a], a) –> ((), ([a], a))

しかし、これだとごちゃごちゃして見にくいので、予め以下のように別名を付けておく。

リストは、

type Ary a = [a]

一時変数は、

type Temp a = a

上記 2 つを合わせたものを、

type Vars a = (Ary a, Temp a)

これにより、先ほどの f1 を以下のように書ける。

f1 :: Vars a –> ((), Vars a)

更に、ライブラリに定義されている State モナドを利用するために、

f1 :: State (Vars a) ()

という型に合わせる。

 

予め State モナドを利用するために、

import Control.Monad.State

関数 f1 は「一時変数にリストの i 番目の要素を代入する」。名前を toTemp とするなら、

toTemp :: Int -> State (Vars a) ()
toTemp i = State $ \(xs, tmp) -> ((), (xs, xs !! i))

get, put 関数を使って定義すると、

toTemp i = get >>= \(xs, tmp) ->
           put (xs, xs!!i)

modify 関数で置き換えるなら、

toTemp i = modify $ \(xs, tmp) -> (xs, xs!!i)

 

リストの i 番目の要素を j 番目の要素で上書きする関数を copyElem とすると、

copyElem :: Int -> Int -> State (Vars a) ()
copyElem i j = modify $ \(xs, tmp) ->
               (take i xs ++ xs!!j : drop (i+1) xs, tmp)

 

リストの j 番目の要素を一時変数の値で上書きする関数を formTemp とすると、

fromTemp :: Int -> State (Vars a) ()
fromTemp j = modify $ \(xs, tmp) ->
             (take j xs ++ tmp : drop (j+1) xs, tmp)

上記 3 つの関数を使い swap を定義する。

swapS :: Int -> Int -> State (Vars a) ()
swapS i j = toTemp i >> copyElem i j >> fromTemp j

swap i j xs = fst $ execState (swapS i j) (xs, 0)

全体は gist: 940268 — Gist

 

9. State モナド (2)

上記の State モナドでは「一時変数」に相当するものを想定した。しかし、これがなくても問題ない。

別名を付けるのも面倒なので、リストの特定のインデックスを更新する関数 update を

update :: Int –> a –> [a] -> ((), [a])

とする。 これを元に State モナドに合わせるために以下のように型を定める。

update :: Int -> a -> State [a] ()

この update 関数の定義は、

update i x = State $ \xs -> ((), take i xs ++ x : drop (i+1) xs)

先ほどと同じように get, put 関数を使うなら、

update i x = get >>= \xs ->
             put $ take i xs ++ x : drop (i+1) xs

modify 関数で置き換えるなら、

update i x = modify $ \xs -> take i xs ++ x : drop (i+1) xs

次に、リストの特定のインデックスの値を取得する関数を getIdxAt とすると、その型は、

getIdxAt :: Int -> State [a] a

この定義は、

getIdxAt i = State $ \xs -> (xs !! i, xs)

get 関数を使うと、

getIdxAt i = get >>= \ xs ->
             return $ xs !! i

関数合成を利用すると、

getIdxAt i = get >>= return . (!! i)

この二つの関数を使い swap を定義する。

swapS i j = getIdxAt i >>= \a ->
            getIdxAt j >>= \b ->
            update i b >>
            update j a

swap i j xs = (execState $ swapS i j) xs

上記 swapS 関数では変数 a, b の二つを利用しているが、一つだけでも十分。

swapS i j = getIdxAt i >>= \tmp ->
            getIdxAt j >>= update i >>
            update j tmp

do 式を使うなら、

swapS i j = do tmp <- getIdxAt i
               update i =<< getIdxAt j
               update j tmp

そういえば、get 関数を使うなら、getIdxAt 関数も必要もないか。

swapS i j = do xs <- get
               update i (xs!!j)
               update j (xs!!i)

全体は gist: 940572 — Gist

多重代入と変数の swap - Python と Ruby の比較

Python で多重代入を利用した変数の swap

Python の 6.3 代入文 (assignment statement) によると、

代入の定義では、左辺値と右辺値がオーバラップするような代入 (例えば、"a, b = b, a" を行うと、二つの変数を入れ替えます) を定義しても `安全 (safe)' に代入できます …

例えば、2 つの変数 a, b を入れ替えるなら、変数の値を退避しておく一時変数を省略できる。

a = "hoge"
b = "piyo"

a, b = b, a

print a,b         #=> piyo hoge

 

代入対象の変数にオーバーラップがある場合

注意点としては、

代入対象となる変数群 の間で オーバラップがある場合は安全ではありません！

(同上より)

次のようなケース。

ary = ["hoge", "piyo", "fuga"]
i = 100

i, ary[i] = 1, 999

print ary          #=> ['hoge', 999, 'fuga']

もし、swap が見かけ通り一つの文として同時に実行されているなら、swap を行う時点の i の値は 100 となり、ary[100] は存在しないためにエラーとなる。しかし、実際には最初の i に 1 が代入されたことにより、i の値が上書きされ、ary[1] に 999 が代入される。

以下のように順次実行されているのと同じように見える。

i= 1
ary[i] = 999

しかし、変数を a, b を swap したときのように swap させると、

ary = [1,2,3,4,5]
i = 0

i, ary[i] = ary[i], i

print i, ary

結果は、

1 [1, 0, 3, 4, 5]

となる。 右辺の i は更新される前の i の値を参照しているようで、何だかよくわからなくなってきた。  (+_+)

てっきり、以下のように実行されるのかと思った。

i = ary[i]
ary[i] = i

右辺の代入される値は、多重代入の前の変数で名前解決が行われるのかな？

i = ary[0]
ary[i] = 0

 

Ruby で多重代入を利用した変数の swap

同じく多重代入ができる Ruby で動作を確認すると、

a = "hoge"
b = "piyo"

a, b = b, a

p a,b        

次のように同じ結果となる。

"piyo"
"hoge"

また、「代入対象となる変数群の間でオーバラップがある場合」も結果は同じ。

ary = ["hoge", "piyo", "fuga"]
i = 100       

i, ary[i] = 1, 999

p ary          #=> ["hoge", 999, "fuga"]

以下も Python と同じ。

ary = [1,2,3,4,5]
i = 0

i, ary[i] = ary[i], i

p i, ary

結果は、

1
[1, 0, 3, 4, 5]

Haskell で変数の更新を伴うインデックス付きループを再帰で置き換えるには

1. ループ内における変数の更新はややこしい

Programming in Scala (p354) に次のような関数の例が書かれている。

• 「
  Programming
  in Scala
  

  Scalaスケーラブル
  プログラミング
  
  文字列の配列の中から最長の文字列と、そのインデックスを返す」

これを Python で書くなら、

def longestWord(words):
    word = words[0]
    idx = 0
    for i in range(1, len(words)):
        if len(word) < len(words[i]): 
            word = words[i]
            idx = i
    return (word, idx)

print longestWord("The quick brown fox".split())

やってることは単純。しかし、昔からこういうコードを読むのは苦手だった。

最初にローカル変数を複数用意して、ループ内でごちゃごちゃと更新。この程度ならまだしも、ループが二重以上になると頭が沸騰してくる。 (+_+)

曲者はループ内での変数の更新。

更新されている変数は、

• 最長の文字列を保持する word 
• 最長の文字列のインデックスを保持する idx
• 文字列の配列要素を走査するための i

配列を走査するイメージを頭に描きつつ、状況に応じて変数を更新。

誰かに計算を任せ、その結果を受け取るという楽な方法ではない。

 

2. 「再帰」と更新用の引数を用いて、変数の更新を模倣する

では、これを変数の更新が許されず、for ループも用意されていない Haskell でどう書くのか？

次の 2 点を覚えておく。

1. ループを「再帰」で置き換える。
2. 変数の更新は、再帰で与える引数において、更新後と想定する値を渡すことで代替。

加えて、Haskell では配列ではなくリストがよく用いられ、配列的な発想とは異なることに注意。

構造的な違いとして、配列は要素が格納されている場所にインデックス情報が存在するのに対して、リストはそれがない。リストが再帰的な構造を基盤として要素を走査するが、配列はインデックスによりそれを行うこと。

よって、完全に対応したものを考えているのではなく、結果として同等な方法の比較をする。

 

更新される値を考えない場合

まずは、インデックスは無視して、最長の文字列を返すだけの関数を考える。

longestWord [x]    = x
longestWord (x:xs) = let word = longestWord xs
                     in if length x < length word 
                        then word 
                        else x

リストに対する関数を考えるときは、オブジェクト指向のアナロジーで考えているので、上記二行目のコード、

longestWord xs

を以下のように頭の中で置き換えている。

xs.longestWord()

全体としては下図のようなイメージ。

 

更新される値に相当する引数を使う

次に、インデックスも返すために、更新用の変数と同じ役割をする引数 idx を関数に追加する。 idx 変数に配列のインデックスに相当する値を累積させる。(これを累積と言うのか微妙だけれど。。)

longestWord' idx [x]      = (x, idx)
longestWord' idx (x1:xs1) = let (x2, idx2) = longestWord' (idx+1) xs1
                            in if length x1 < length x2
                               then (x2, idx2)
                               else (x1, idx)

longestWord xs = longestWord' 0 xs

先ほどと同じく上記二行目のコード、

longestWord’ (idx+1) xs1

を以下のように頭の中で置き換えている。

xs1.longestWord’(idx+1)

これより、インデックスを累積 (更新) するための変数は、リストのある要素が次の要素に対して、特定の計算の結果を渡す先だと見ることができる。

リスト処理における再帰的な関数は、オブジェクト指向の考え方と親和性が高い。

 

3. 予めインデックスを用意しておく方法

別の方法としては、対象のリストとは別にインデックスのリストを用意し、それと組み合わせた結果に対して関数を定義する。

longestWord' :: [(String, Int)] -> (String, Int)
longestWord' [x]             = x
longestWord' (x1@(x,idx):xs) = let x2@(x', idx') = longestWord' xs
                               in if length x < length x' 
                                  then x2 else x1
                                  

longestWord xs = longestWord' $ zip xs [0..]

この方法は、インデックス情報を持った配列に構造を予め似させてから計算を行なっていると言える。ただし、ループはリストの再帰的な構造を利用することにより代替していることは先ほどと変わりはない。

また、遅延評価の Haskell では、予めどのくらいインデックスが必要か考えておく必要はない。

 

4. State モナドで試したら

ところで、状態の「更新」と聞いて連想するのは State モナド。「longestWord’ 関数を再帰的に適用するごとにインデックスの状態を更新する」と見なして考えたら、どのように書けるのだろう？

 

s –> (a, s) 型の関数

最初は、ライブラリに用意されている State モナドを利用するのではなく、関数をつなげる関数も自分で定義して考える。

State モナドで、状態の変更をシミュレートした関数として用いられるのは、

s –> (a, s)

という型を持つ。

先ほど定義した longestWord’ 関数の場合であれば、第1引数と第2引数を逆転させ、適当に配列を与えたときの型がこれに相当する。

*Main> :t (flip longestWord') ["The","quick","brown","fox"]
(flip longestWord') ["The","quick","brown","fox"]
  :: (Num a) => a -> ([Char], a)

この関数を再帰によりつなぎ、計算が進行するに連れ、インデックスを保持する変数が更新されていくと考えてみる。

 

計算をつなげる関数

最初に以下の型を持つ関数に対して、

s –> (a, s)

1. 何らかの状態を持つ型 s の値を引数に与えると、
2. その値が更新されたことに付随して、
3. 結果 a が生じる
4. … と解釈できる関数を「つなげる」関数

を考える。( 詳しくは「Haskell の State モナド (1) - 状態を模倣する」を参照 )

読みやすさを考慮して、上記関数の型に別名を付けておく。

type State s a = s -> (a, s)

この State s a 型をつなげる計算を comb とする。 (>>= に相当)

comb :: State s a -> (a -> State s b) -> State s b
comb m k = \s -> let (x1, s') = m s in k x1 s'

comb の第1引数の結果に対して、第2引数が関心を持たない関数を comb_ とする。 (>> に相当)

comb_ :: State s a -> State s b -> State s b
comb_ m n = m `comb` \_ -> n

状態の変更を行わず、与えた引数を結果とする関数を ret とする。 (return に相当)

ret :: a -> State s a
ret x = \s -> (x, s)

 

計算をつなげる関数を使って longestWord’ を定義

準備ができたので、longestWord’ 関数の定義をする。

ここでは「インデックスを保持する変数」が更新されることに付随して、「最長の文字列」という結果が生じると見なして考える。上記で定義した 3 つの関数を使うと、更新されるインデックスを隠蔽できる。

State s a の s に相当するのが「インデックス」を表わす Int 型。 a に相当するのが「最長の文字列」を保持する String 型。

longestWord' :: [String] -> State Int String
longestWord' [x]    = ret x
longestWord' (x:xs) = longestWord' xs `comb` \x' ->
                      if length x < length x'
                      then inc `comb_` ret x'
                      else ret x

inc = \idx -> ((),idx +1) 

longestWord xs = longestWord' xs 0

インデックスを更新する操作を inc 関数で定義している。

( コード全体は gist: 823793 - GitHub )

 

5. Control.Monad.State を利用する

今度はライブラリに用意されている関数に置き換える。

最初に State モナドを利用するためにモジュールをインポート。

import Control.Monad.State

これを利用して、

longestWord' :: [String] -> State Int String
longestWord' [x] = return x
longestWord' (x:xs) = longestWord' xs >>= \x' ->
                      if length x < length x'
                      then inc >> return x'
                      else return x

inc = modify (+1)

longestWord xs = runState (longestWord' xs) 0

inc 関数は、インデックスの状態に相当する変数を更新していた。このような状態を更新する関数もライブラリに用意されている。

Control.Monad.State.Class

modify :: MonadState s m => (s -> s) -> m

Maps an old state to a new state inside a state monad. The old state is thrown away.

( コード全体は gist: 823796 – GitHub )

 

do 式

モナドは do 式を利用できるので、longestWord’ 関数を以下のように書くことも可能。

longestWord' :: [String] -> State Int String
longestWord' [x]    = return x
longestWord' (x:xs) = do x' <- longestWord' xs
                         if length x < length x'
                            then do inc 
                                    return x'
                            else return x

( コード全体は gist: 823796 - GitHub )

 

6. 更新する変数を増やした場合

最初に定義した Python のコードでは、更新される変数は idx と word だった。上記 Haskell のコードでは、更新される値がインデックスに限定されている。

idx と word が更新されると想定し、より Python で書いたときのコードに似せるなら、

longestWord' word idx []     = (word, idx)
longestWord' word idx (x:xs) = let (x', idx') = longestWord' x (idx+1) xs
                               in if length word < length x'
                                  then (x', idx')
                                  else (word, idx)

longestWord (x:xs) = longestWord' x 0 xs

大雑把なイメージは下図。 longestWord 関数において、longestWord’ 関数の第1・第2引数を与えることが、Python における変数の初期化に相当する。

先ほどと同じようにオブジェクト指向的に見るなら、

longestWord' x (idx+1) xs

を以下のように頭の中で置き換える。

xs.longestWord’(x, idx+1)

 

State

word, idx を更新される変数と見なし、先ほどと同じく、ライブラリに用意されている State モナドを利用しないで書いてみる。

今回は、更新される変数として word, idx をタプルの要素とし、結果に相当するものは () とする。

関数の型は、

[String] –> State (String, Int) ()

更新される変数 word を計算のつながりの中で参照するためには、状態を結果として取り出す必要がある。そのための関数を get とすると、

get :: State s s
get = \s -> (s, s)

状態を変更するための関数 put も用意しておく。

put :: s -> State s ()
put x = \_ -> ((), x)

最終的に結果は必要なく、状態がわかれば良いので、そのための関数 execState を定義。

execState :: State s a -> s -> s
execState s s0 = snd $ s s0

これらを用いて、

longestWord' :: [String] -> State (String, Int) ()
longestWord' [] = ret ()
longestWord' (x:xs) = get             `comb` \x1@(word, idx) ->
                      put (x, idx+1)  `comb_` 
                      longestWord' xs `comb_` 
                      get             `comb` \x2@(word', idx') ->
                      if length word < length word' then put x2 else put x1
                   
longestWord (x:xs) = (execState $ longestWord' xs) (x, 0)

( コード全体は gist: 823947 – GitHub )

 

Control.Monad.State

Control.Monad.State を利用するなら、

longestWord' [] = return ()
longestWord' (x:xs) = get             >>= \x1@(word, idx) ->
                      put (x, idx+1)  >> 
                      longestWord' xs >> 
                      get             >>= \x2@(word', idx') ->
                      if length word < length word' then put x2 else put x1

longestWord (x:xs) = execState (longestWord' xs) (x, 0)

( コード全体は gist: 824329 - GitHub )

上記を do 式で書き直すと、

longestWord' [] = return ()
longestWord' (x:xs) = do x1@(word, idx) <- get
                         put (x, idx+1) 
                         longestWord' xs
                         x2@(word', idx') <- get
                         if length word < length word' then put x2 else put x1

( コード全体は gist: 824329 – GitHub )

 

7. foldl を使い、畳み込みながら更新

追記(2011.2.19) : 畳込み関数を使うなら、foldl の第2引数に更新する変数に相当する値を与える。

longestWord' (x:xs) = foldl f (x, 0, 0) xs
    where
      f (word, idx, i) w | length word < length w = (w, inc, inc)
                         | otherwise              = (word, idx, inc)
          where 
            inc = i + 1

longestWord xs = let (word, idx, _) = longestWord' xs in (word, idx)

 

State

Control.Monad.State を使うなら、どうなるのだろう？ (cf. Haskell の sequence 関数 - foldr をイメージして)

読みやすくするために予め別名を付ける。

type Word  = String  -- 最長の文字列
type Idx   = Int     -- 最長の文字列のインデックス
type Index = Int     -- ループで使うインデックス

これを用いて、畳み込むとき、ループで使うインデックス (Index) が更新されていくと同時に、 (最長の文字列、そのインデックス) という結果が生じると解釈する。

longestWord' :: [String] -> State Index (Word, Idx)
longestWord' (x:xs) = foldl f (return (x, 0)) xs
    where
      f :: State Index (Word, Idx) -> String -> State Index (Word, Idx)
      f s w = s >>= \(word, idx) ->
              (if length word < length w
              then return (w, idx+1)
              else return (word, idx)) >>= \wordIdx ->
              State $ \i -> (wordIdx, i+1)

longestWord xs = let (wordIdx, _) = runState (longestWord' xs) 0 in wordIdx

( コード全体は gist: 834817 - GitHub)

do 式で置き換えるなら、

longestWord' :: [String] -> State Index (Word, Idx)
longestWord' (x:xs) = foldl f (return (x, 0)) xs
    where
      f :: State Index (Word, Idx) -> String -> State Index (Word, Idx)
      f s w = do (word, idx) <- s
                 wordIdx <- if length word < length w
                            then return (w, idx+1)
                            else return (word, idx)
                 State $ \i -> (wordIdx, i+1)

longestWord xs = let (wordIdx, _) = runState (longestWord' xs) 0 in wordIdx

( コード全体は gist: 834817 - GitHub )

//TODO

「Haskell の Data.IORef を使い IO モナドの中で変数を更新」につづく

 

参考記事

• 第6回 局所的な「状態」を利用するためのStateモナド - 本物のプログラマはHaskellを使う：ITpro

Python のパッケージを pip でインストール

1. EasyInstall を使い、Python Package Index よりパッケージをインストール

PyPI とは、

The Python Package Index is a repository of software for the Python programming language.

Python のパッケージが管理されているリポジトリ。

 

easy_install

CheeseShopTutorial - PythonInfo Wiki によると、お手軽に Python のパッケージをインストールするには、EasyIntall を使うとのこと。

EasyInstall (easy_install) gives you a quick and painless way to install packages remotely by connecting to the Package Index or even other websites via HTTP.

EasyInstall を利用するには setuptools 0.6c11 を予め入れておく。

OS と Python のバージョンに合わせ、Using Setuptools and EasyInstall にある

• setuptools-0.6c11.win32-py2.5.exe

をダウンロードしてインストール。

Windows Notes によると、

If typing easy_install at the command prompt doesn't work, check to make sure your PATH includes the appropriate C:\\Python2X\\Scripts directory.

コマンドラインから easy_install を実行するために、

• C:\Python25\Scripts

を環境変数の PATH に追加した。

 

2. pip でパッケージをインストール

ところで、easy_install 以外にもパッケージをインストールするツールは存在する。

pip 0. 8.2 は、

pip is a replacement for easy_install. It uses mostly the same techniques for finding packages, so packages that were made easy_installable should be pip-installable as well.

上記には easy_install と比べて以下の利点が挙げられている。

• All packages are downloaded before installation. Partially-completed installation doesn't occur as a result.
• Care is taken to present useful output on the console.
• The reasons for actions are kept track of. For instance, if a package is being installed, pip keeps track of why that package was required.
• Error messages should be useful.
• The code is relatively concise and cohesive, making it easier to use programmatically.
• Packages don't have to be installed as egg archives, they can be installed flat (while keeping the egg metadata).
• Native support for other version control systems (Git, Mercurial and Bazaar)
• Uninstallation of packages.
• Simple to define fixed sets of requirements and reliably reproduce a set of packages.

例えば、上記「パッケージをアンインストールすることができる」に関して easy_install は、

easy_install never actually deletes packages (unless you're installing a package with the same name and version number as an existing package), so if you want to get rid of older versions of a package, please see Uninstalling Packages, below.

(Upgrading a Package より)

 

pip のインストール

まずは、easy_install を利用して pip をインストール。

easy_install pip

 

pip でパッケージのインストールとアンインストール

pip でパッケージをインストールするには、

pip install パッケージ名

アンインストールするには、

pip uninstall パッケージ名