2012年11月6日火曜日

Scheme で変数の束縛 - let, let*, letrec, 名前付きlet, letrec*

1. Haskell の let 式は相互再帰的

Haskell で値を変数に束縛したい場合、let 式を使う。

束縛とは、束縛 (情報工学) – Wikipedia によると、

名前束縛(Name binding)あるいは名前結合とは、識別子に対応付けることを意味する。値に束縛された識別子を、その値への参照と呼ぶ。

例えば、値を変数に束縛した後、その変数を利用して計算を行う場合、

main = let x = 100 
           y = 200
           z = x + y
       in print (x, y, z)    -- (100,200,300)

Haskell の let 式の特徴は、束縛した変数を相互再帰的に利用できること。

3.12 let 式 によると、

Let 式let { d1 ; ... ; dn } in e という一般形式を持ち、入れ子でレキシカルスコープで相互再帰的な宣言リスト (このような let他の言語ではよく letrec と呼ばれる) を持つ。宣言のスコープ(有効範囲)は、式 e および宣言の右辺である。

 

2. Scheme の let 式における初期値の評価は、現在の環境で行われる

a. let 式の書き方

Scheme も let 式により、値を変数に束縛することができる。

let の書き方は、

let 束縛 本体

となり、束縛の中身は、

((変数1 初期値1) ...)

と書く。 4.2.2 Binding constructs によると、

— library syntax: let <bindings> <body>

Syntax: <Bindings> should have the form

((<variable1> <init1>) ...),

where each <init> is an expression, and <body> should be a sequence of one or more expressions.

let 式を使った簡単な例を挙げる。

(let ((x 100)
      (y 200))
  (display (cons x y)))   ; {100 . 200}

束縛された変数を参照できる範囲は、let 式の本体に限られる。

Each binding of a <variable> has <body> as its region. (同上より)

本体にある最後の式が、let 式の返り値となる。

 

b. 初期値が評価される環境

ただし、最初に Haskell で書いた let 式によく似たコードを書いても、エラーとなってしまう。

(let ((x 100)
      (y 200)
      (z (+ x y)))   ; x: unbound identifier in module in: x
  (display (cons x (cons y z))))

エラーの原因は、変数 z の初期値を評価するとき、変数 x を見つけることができないため。理由は、let 式 の初期値は、現在の「環境」で評価されるため。

Semantics: The <init>s are evaluated in the current environment (in some unspecified order),  … (同上より)

4.2.2. 束縛コンストラクト

意味: 各 <初期値> が現在の環境の中で (ある未規定の順序で) 評価される。その結果を保持する新しい場所へ,それぞれの <変数> が束縛される。その拡張された環境の中で <本体> が評価される。

「環境」とは、変数名と対応する値を関係付けるテーブルである「フレーム」と呼ばれる連鎖の構造を指す。Scheme は、フレームにより、変数が管理される。

3.2 The Environment Model of Evaluation

An environment is a sequence of frames. Each frame is a table (possibly empty) of bindings, which associate variable names with their corresponding values.

詳しくは、評価環境のモデルを参照。

上記の例では、変数 z に値を割り当てるとき、変数 x, y が「環境」に存在しない。そのため、x という識別子を見つけることができない。

 

c. 変数を参照するための方法

let 式の初期値は、現在の環境で評価される。そのため、上記の例に対して、トップレベルに変数 x, y が定義してあれば、変数を参照することができる。

(define x 1)
(define y 2)

(let ((x 100)
      (y 200)
      (z (+ x y)))
  (display (cons x (cons y z))))   ; {100 200 . 3}

もしくは、let 式をネストすれば、外側に定義した let 式の変数を参照できる。

(let ((x 100)
      (y 200))
  (let ((z (+ x y)))
    (display (cons x (cons y z)))))    ; {100 200 . 300}

 

d. let 式を lambda で表す

ところで、let 式は、lambda 式を呼び出す形のシンタクティックシュガーである。

let (special form) によると、

(let ((<var1> <exp1>)
(<var2> <exp2>)

(<varn> <expn>))
<body>)

という let 式は、以下の lambda 式の呼び出しに相当する。

((lambda (<var1> ...<varn>)
<body>)
<exp1>

<expn>)

先ほどの例で考えると、

(let ((x 100)
      (y 200))
  (display (cons x y))) 

を、次のような lamda 式に置きかえることができる。

((lambda (x y)
   (display (cons x y)))
   100
   200)

 

3. let* 式は、左から右へと順に初期値が評価され、変数を束縛する

Scheme には、let 式の末尾にアスタリスクがついた let* 式がある。この式は let と似ているが、値が変数に束縛されるタイミングが違う。let* は初期値の評価と変数への束縛が、左から右へと行われる。

Binding constructs - Revised(5) Scheme によると、

Semantics: Let* is similar to let, but the bindings are performed sequentially from left to right, and the region of a binding indicated by (<variable> <init>) is that part of the let* expression to the right of the binding.

4.2.2. 束縛コンストラクト

意味: let* は let と似ているが,束縛を逐次的に左から右へと行うから,一つの (<変数> <初期値>) が示す束縛の領域は let* 式でその束縛から右の部分である。したがって2番目の縛は1番目の束縛が可視である環境でなされる等々である。

先ほどと同じ式を let 式から、let* 式に置き換えてみる。

(let* ((x 100)
       (y 200)
       (z (+ x y)))
  (display (cons x (cons y z))))   ; {100 200 . 300}

この場合、変数 z が束縛されるとき、既に変数 x, y は存在する。そのため、最初に let でエラーとなった式が、let* では問題なく変数を参照できる。

 

束縛の順序が重要

初期値の変数への束縛は、左から右へと行われる。このため、各変数は、自身の右側にある束縛から参照できる。

the region of a binding indicated by (<variable> <init>) is that part of the let* expression to the right of the binding.(同上より)

Haskell では、let 式における束縛の順序を変更しても、結果は変わらない。

main = let z = x + y
           x = 100 
           y = 200
       in print (x, y, z)    -- (100,200,300)

なぜなら、let 式の中で相互再帰的に変数を参照できるため。

これに対して、Scheme では let* における束縛の順序を変更すると、エラーとなる。

(let* ((z (+ x y))
       (x 100)
       (y 200))
  (display (cons x (cons y z)))) ; x: unbound identifier in module in: x

この場合、最初に変数 z を束縛するために変数 x, y が評価される。このとき、変数 z の右にある変数 x, y を参照できない。

 

4. letrec は再帰的な定義をするときに用いる

let, let* との違い

R5RS には、let, let* に加えて、変数を束縛するための式がもう一つある。それが letrec.

letrec は、初期値と本体が評価される環境が let, let* と異なる。束縛された変数の有効範囲が letrec 式全体となるので、相互再帰的な手続きを定義することができる。

Binding constructs - Revised(5) Scheme によると、

Semantics: The <variable>s are bound to fresh locations holding undefined values, the <init>s are evaluated in the resulting environment …, the <body> is evaluated in the resulting environment, … Each binding of a <variable> has the entire letrec expression as its region, making it possible to define mutually recursive procedures.

4.2.2. 束縛コンストラクト

意味: 未定義値を保持する新しい場所へ,それぞれの<変数> が束縛される。その結果として得られた環境の中で各<初期値> が (ある未規定の順序で) 評価される。各 <変数>にそれぞれ対応する <初期値> の結果が代入される。その結果として得られた環境の中で <本体> が評価される。

 

再帰の例

letrec 式を使い、再帰的な関数を定義してみる。例えば、総和を求める sum 手続き。

(letrec ((sum (lambda (x)
                (if (null? x) 0
                    (+ (car x) (sum (cdr x)))))))
  (display (sum '(1 2 3 4 5))))  ; 15

相互再帰の例は、以下を参照。

 

letrec の制約

letrec 式には制約がある。それは、変数に対して代入したり、参照することなしに、初期値を評価できなければならないというもの。

it must be possible to evaluate each <init> without assigning or referring to the value of any <variable>. (同上より)

このような制約が必要となる理由は、Scheme では引数が値渡しであるため。名前渡しではないことによる。

Scheme passes arguments by value rather than by name.

値渡し とは、

… 実引数として変数を渡したとしても、その値のみが渡される。… その仕組みとしては、独立した新たな変数が関数内に用意され、元の値がコピーされる。そのため変数を渡したとしても、元の変数が変更されるという事はない。

名前渡し とは、

名前渡しでは値でも参照でもなく、式がそのまま渡される。… 式を参照するごとに値を計算して取り出す事が特徴である。

このため、letrec の典型的な使い方は、初期値に手続きを書くことである。

初期値を手続きにすることにより、変数が束縛されるとき、手続きは呼び出されない。変数に束縛した手続きを呼び出すときに、はじめて束縛した変数を参照することになる。

 

変数の初期値の中で、変数を参照した場合、#<undefined>

最初に letrec の制約について確認する。letrec 式の初期値で変数を参照し、その変数を本体で出力したら何が表示されるだろう?

(letrec ((x 100)
         (y x))
  (display x)     ; 100
  (display y))    ; #<undefined>

この場合、変数 y に対応した初期値は、変数 x を参照している。本体で変数 x を表示すると

#<undefined>

という値が表示された。

#<undefined> は、初期化されてない束縛を参照したときの定数を意味する。 letrec では、束縛の初期値として使われる。

3.12 Void and Undefined によると、

A constant that prints as #<undefined> is used as the result of a reference to a local binding when the binding is not yet initialized.

3.18 Void and Undefined

The constant #<undefined> is used as the initial value for letrec bindings.

上記の例を、letrec から let* 式に置き換えると、#<undefined> の代わりに 100 が表示される。

(let* ((x 100)
       (y x))
  (display x)     ; 100
  (display y))    ; 100

これは let* 式により、初期値が順に評価されるため。

letrec 式を使う場合、初期値で lambda を利用すると、変数 y を参照できるようになる。

(letrec ((x 100)
         (y (lambda () x)))
  (display x)     ; 100
  (display (y)))  ; 100

letrec 式では、束縛の順番を変更しても変数を参照できる。

(letrec ((y (lambda () x))
         (x 100))
  (display x)     ; 100
  (display (y)))  ; 100

 

処理系による違い

上記のコードを実行するために、Racket で R5RS, R6RS を利用した。

同じコードを Gauche, BiwaScheme Blackboard, Racket で Pretty Big を利用した場合、#<undefined> の代わりに 100 が表示される。一体どの実装が仕様を満たしているのだろう?

Gauche:letrec* によると、

たとえばこんな式が可能。

(letrec* ([var1 1] 
          [var2 (+ 1 var1)]
          [var3 (+ 1 var2)])
  var3) ;=> 3

ここにletrecを使った場合、R5RSでは結果は未定義 (処理系によってはletrec*のように動作するものもある)、R6RSではエラー (処理系は&assertionコンディションを通知しないとだめ)。

0.8.14現在のGaucheでは上の式のletrec*をletrecに置き換えても動作する。けれど、単純にletrec*をletrecのエイリアスにしてしまうことはできない。 letrecは最適化によって初期化式の順序が変わる場合があるからだ。

 

5. 名前付き let

let のバリエーションとして、名前付き let がある。この構文は、繰り返し処理を定義するときに用いられる。

11.16 Iteration によると、

(let <variable> <bindings> <body>) syntax

… <variable> is bound within <body> to a procedure whose parameters are the bound variables and whose body is <body>.

Scheme 入門 7. 繰り返し

簡単なループは名前つき let を使うのが一般的です。また、 複雑な再帰は letrec を使うことが多いようです。

上記の letrec で書いた手続き sum を、名前付き let で置き換えてみる。

(display
 (let sum ((x '(1 2 3 4 5)))
   (if (null? x) 0
       (+ (car x) (sum (cdr x))))))

名前付き let を書くときは、let 式を lambda 式に置き換えた方法を思い出し、束縛を引数と対応付けて考えると良い。

複数の束縛がある場合、次のように書く。例えば、手続き sum を累積変数を用い、末尾再帰の形に変更するなら、

(display
 (let sum ((x '(1 2 3 4 5))
           (acc 0))
   (if (null? x) acc
       (sum (cdr x)
            (+ acc (car x))))))

 

6. letrec*

R6RS には、更に letrec* という形式がある。let + rec + * という形をしている。

これは、次のように覚えれば良い。

  1. rec : 再帰的な手続きを定義するのに用いることができる。
  2. * : 束縛が左から右へと、順に行われる。 ⇒ 先に束縛された変数を参照できる。

Gauche:letrec* によると、

R6RSで導入されたletrec*は、letrecに初期化式の実行順序の保証を入れたもの。

Revised^6 Report on the Algorithmic Language Scheme

Semantics: … each <variable> is assigned in left-to-right order to the result of evaluating the corresponding <init>, the <body> is evaluated in the resulting environment, …  Despite the left-to-right evaluation and assignment order, each binding of a <variable> has the entire letrec* expression as its region, making it possible to define mutually recursive procedures. …

 

制約の比較

letrec と letrec* の制約を比較しておく。letrec では、以下のように述べられていた。

it must be possible to evaluate each <init> without assigning or referring to the value of any <variable>. (同上より)

これに対して letrec* には、次にように書かれている。

It must be possible to evaluate each <init> without assigning or referring to the value of the corresponding <variable> or the <variable> of any of the bindings that follow it in <bindings>. Another restriction is that the continuation of each <init> should not be invoked more than once. (同上より)

 

相互再帰と、変数の参照の例

Revised^6 Report on the Algorithmic Language Scheme には、letrec の例が挙げられている。この例における変数の参照関係を図示すると、以下のようになる。

SnapCrab_NoName_2012-11-3_11-27-9_No-00

これより、letrec* では相互再帰と、先に束縛された変数を参照できることが分かる。

この例で、letrec* を letrec に置き換えると、エラーが表示される。なぜなら、変数 x の初期値を評価したとき、参照する変数 p が #<undefined> となり、手続きの呼び出しができなくなるため。

 

7. まとめ

let, let*

let と let* は、初期値が変数を束縛するタイミングが違う。

  • let は、変数を束縛する前に初期値を評価する。
  • let* は、初期値の評価と変数への割り当てが順に行われる。

11.4.6 Binding constructs より、

let

let*

the initial values are computed before any of the variables become bound;

the bindings and evaluations are performed sequentially.

 

letrec, letrec*

letrec と letrec*の共通点は、初期値を計算するときに、束縛された変数を利用できること。このため、相互再帰的な定義ができる。

In a letrec or letrec* expression, all the bindings are in effect while their initial values are being computed, thus allowing mutually recursive definitions.

違いは、let と let* の関係と似ている。

  • letrec は、初期値が変数に割り当てられる前に評価される。
  • letrec* は、初期値の評価と割り当てが順に行われる。
letrec letrec*

the initial values are computed before being assigned to the variables;

the evaluations and assignments are performed sequentially.

 

覚えておくこと
  1. let 式により、初期値を変数に束縛する。
  2. 末尾に * を付けると、評価と変数の割り当てが順に行われる。
  3. 末尾に rec を付けると、初期値を計算する中で、束縛された変数を参照できる。