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), … （同上より）
意味: 各 <初期値> が現在の環境の中で (ある未規定の順序で) 評価される。その結果を保持する新しい場所へ，それぞれの <変数> が束縛される。その拡張された環境の中で <本体> が評価される。
「環境」とは、変数名と対応する値を関係付けるテーブルである「フレーム」と呼ばれる連鎖の構造を指す。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.
意味: let* は let と似ているが，束縛を逐次的に左から右へと行うから，一つの (<変数> <初期値>) が示す束縛の領域は let* 式でその束縛から右の部分である。したがって２番目の縛は１番目の束縛が可視である環境でなされる等々である。
先ほどと同じ式を 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.
意味: 未定義値を保持する新しい場所へ，それぞれの<変数> が束縛される。その結果として得られた環境の中で各<初期値> が (ある未規定の順序で) 評価される。各 <変数>にそれぞれ対応する <初期値> の結果が代入される。その結果として得られた環境の中で <本体> が評価される。
再帰の例
letrec 式を使い、再帰的な関数を定義してみる。例えば、総和を求める sum 手続き。
(letrec ((sum (lambda (x)
(if (null? x) 0
(+ (car x) (sum (cdr x)))))))
(display (sum '(1 2 3 4 5)))) ; 15
相互再帰の例は、以下を参照。
- Revised^6 Report on the Algorithmic Language Scheme ： 数値が偶数か奇数か判断する。
- Mutual recursion - Rosetta Code
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.
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>.
簡単なループは名前つき 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 + * という形をしている。
これは、次のように覚えれば良い。
- rec : 再帰的な手続きを定義するのに用いることができる。
- * : 束縛が左から右へと、順に行われる。 ⇒ 先に束縛された変数を参照できる。
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 の例が挙げられている。この例における変数の参照関係を図示すると、以下のようになる。
これより、letrec* では相互再帰と、先に束縛された変数を参照できることが分かる。
この例で、letrec* を letrec に置き換えると、エラーが表示される。なぜなら、変数 x の初期値を評価したとき、参照する変数 p が #<undefined> となり、手続きの呼び出しができなくなるため。
7. まとめ
let, let*
let と let* は、初期値が変数を束縛するタイミングが違う。
- let は、変数を束縛する前に初期値を評価する。
- let* は、初期値の評価と変数への割り当てが順に行われる。
|
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. |
覚えておくこと
-
let 式により、初期値を変数に束縛する。
-
末尾に * を付けると、評価と変数の割り当てが順に行われる。
-
末尾に rec を付けると、初期値を計算する中で、束縛された変数を参照できる。
