独学Common Lisp

束縛するlambda、多値とlet

複数の解

C言語をはじめとするプログラミング言語では関数が返す値は一つだけです。引数は複数の値を受け取れますが、返り値は必ず一つと決まっています。この問題を解決するためにC言語ではポインタを使って関数から値を参照して書き換えることがあります。

しかし、Common Lispでは「多値」がネイティブでサポートされています。つまり、必要であれば関数の解を複数返すことができるのです。

これは当然といえば当然で、計算の中には本質的に複数の解を持つものがあります。代表的なのは整数の範囲における割り算で、分数を習うまでは小学生の割り算は商と余りを併記して答えるはずです。Common Lispのfloor関数も商と余りを「多値」として返します。

(floor 5 2)
; => 2
;    1

関数の評価結果が2行に渡って表示されます。これが「多値(multiple-value)」です。(表示の仕方は処理系によって異なることがあります。2,1のように表示されるかもしれません。)

今回は多値と共に、改めてラムダによる「束縛」を考えてみます。

つるかめ算入門

中学受験をする小学生が習う算数の解法に「つるかめ算」というものがあります。「鶴と亀が合わせて8匹、足の数が合わせて26本あるとき、鶴と亀はそれぞれ何匹いますか」とか、「10円切手と50円切手が合わせて8枚、合計280円分あるとき、10円切手と50円切手はそれぞれ何枚ありますか」という問題です。

つるかめ算の問題は本質的に2つの解を持ちます。鶴と亀の両方の数を答えなければならないからです。ですから、つるかめ算を行う関数を作るとすれば、多値で定義するのが自然です。

つるかめ算には一定の解法があります。面積図を用いた視覚的な解法もありますが、計算機での処理には向いていないので今回は仮置きによる解法を使います。

  1. まず、全てを鶴だと仮定して、仮の足の合計を出します
  2. 次に、実際の足の合計から仮の足の合計を引いて差分を求めます
  3. そして、足の合計の差分を1匹あたりの足の差分で割ると、亀が何匹いるのかが分かります
  4. 最後に、実際の合計匹数から、亀の匹数を引くと鶴が何羽いるのかが分かります

つるかめ算はとてもよくできた算法だと思います。鶴の足が2本で、亀の足が4本という定数部分を10円切手と50円切手に置き換えると切手にも使えます。中学生になれば鶴がx匹、亀がy匹と求める解を先に変数(シンボル)に置き換えて、

 x +  y = 匹数
2x + 4y = 足の数

という連立方程式を解くことになります。

つるかめ関数

さて、つるかめ算を解く関数を作ります。まずは鶴と亀のそれぞれの足の本数を定数として定義しなければなりませんが、今回は切手にも対応したいので、プログラム中で変更可能なパラメータとして定義します。パラメータを定義するにはdefparameterを使います。

(defparameter *leg1* 2)
(defparameter *leg2* 4)

defvarは一度定義した後、もう一度defvarしても値が変更されません。インタラクティブな開発や動的なプログラムでは一度プログラムを終了してもう一度ロードし直すのは面倒なので、今回はdefparameterを使います(「定義」ではなく値の「セット」はどちらでもできますが、値のセットはここでは紹介しません)。

次に、前節で述べた手順に沿って計算式を作っていきます。

  1. 全て鶴だと仮定する: X = (* *leg1* n-sum)
  2. 実際の足の本数との差分を取る: Y = (- leg-sum X)
  3. 1匹あたりの足の差分で割る: 亀 = (/ Y (- *leg2* *leg1*))
  4. 全体の引数から亀を引く: 鶴 = (- n-sum 亀)

特に変わったことはありませんが、今まで通りこの式をつなげると答えは4の鶴が関数の評価結果になってしまいますが、今回は4の鶴と3の亀を合わせて返さなければなりません。よって、亀の値を保存した状態で4の処理を行う必要があります。lambdaを使って値をシンボルに束縛しましょう。

(defun tsuru-kame (n-sum leg-sum)
  ((lambda (n-leg2)
     (values (- n-sum n-leg2) n-leg2))
   (/ (- leg-sum (* *leg1* n-sum))
      (- *leg2* *leg1*))))

valuesアクセッサは引数を多値オブジェクトにします。3の計算まで行った後、その評価結果がlambdaの引数n-leg2(亀)に束縛されて、(- n-sum n-leg2)(鶴)とn-leg2(亀)の2つの値が返されます。

多値を返すのは全く難しくありません。これだけで組み込みのfloor関数と同じように、関数を呼び出した時の評価結果は改行されて表示されます。

(tsuru-kame 8 26)
; => 3
;    5

let = lambda ?

これまでlambdaをたくさん使ってきましたが、今回のように値を束縛するためだけにlambdaを使うのは直感的ではありません。なぜなら、束縛される値とシンボルが離れているからです。ラムダ計算は'(λ SYMBOL . DEF) VALUE'というスタイルですから、値の束縛がメインの時はシンボルと値の間に定義が入ってしまって見にくくなってしまうのです。

そこでCommon Lispにはletという便利なオペレータ(マクロ)があります。これは書き方の違うlambdaで、'(let ((SYMBOL VALUE) ...) DEF)'という風に使うことができます。

つるかめ関数をletを使って書き換えると以下のようになります。

(defun tsuru-kame (n-sum leg-sum)
  (let ((n-leg2 (/ (- leg-sum (* *leg1* n-sum))
                   (- *leg2* *leg1*))))
    (values (- n-sum n-leg2) n-leg2)))

多くの場合、上から下へ、左から右へ目が動く方が自然に文章を読むことができます。今回は束縛すべき値が上へ行き、最終的な評価結果となるvaluesが最終行となりましたから、こちらの方が自然です。

letは変則的なlambdaなので、束縛されるシンボルはlambdaと同じレキシカルスコープを持ちます。関数内で使用する変数を束縛する際に多用されます。

lambdaにはlambda*という兄弟がいます。これは、多重のラムダを提供します。

((lambda (a)
   ((lambda (b)
      (1+ b))
    (1+ a)))
 1)
; => 3

この式は、外側のラムダがaを1に束縛した後、内側のラムダがb(1+ a)に束縛しますので、bは2になります。abが同時に束縛されるのではなく、束縛されたaを使ってbを束縛するという「直線的」な束縛です。一方、並列的な束縛はabが同時に束縛されます。

((lambda (a b)
   (1+ b))
 1 2)
; => 3

これは普通のラムダなので、letで置き換えられます。

(let ((a 1)
      (b 2))
  (1+ b))
; => 3

二重のラムダもletで置き換えられますが、二重のletになります。

(let ((a 1))
  (let ((b (1+ a)))
    (1+ b)))
; => 3

この重なるラムダを自動で作り出すのがlet*です。let*を使うと1つで書くことができます。

(let* ((a 1)
       (b (1+ a)))
  (1+ b))
; => 3

並列的な処理しかしないならlet*を使うのは無駄ですが、前の束縛を次の束縛で使うような場合はlet*を使います。

letlet*も大変便利なオペレータですが、lambdaletを表すことができても、letlambdaを表すことはできません。lambdaはシンボルの束縛を遅延させることができますが、letにはそのようなことはできず、letの使用と同時に束縛を行いますから、高階関数に渡して使うようなことはできません。

(defvar 5+ (lambda (x) (+ x 5)))
(mapcar 5+ '(1 2 3))
; => (6 7 8)

これは推奨されない使い方で、5+が欲しければdefvarではなくdefunを使うべきであり、どうしてもdefvarを使いたければ*5+*のように囲んで大域変数であることを明示すべきですが、lambdaの入った変数5+ではxという引数シンボルがmapcarで初めて束縛されます。lambdaの引数シンボルはレキシカルクロージャが作られた時ではなく、レキシカルクロージャが呼び出された時に値に束縛されます。

なお、5+にはすでに作成されたレキシカルクロージャが束縛されていますから、function(#')は不要です。functiondefunで定義された関数からレキシカルクロージャを作るスペシャルオペレータです。

flet

Common Lispでは前節のようにdefvarで定義されたシンボルにラムダを入れることもできます。ラムダ(レキシカルクロージャ)はデータでもあるので、当然といえば当然のことです。

lambdaの引数シンボルにラムダを束縛することもできます。

((lambda (5+)
   (mapcar 5+ '(1 2 3)))
 (lambda (x) (+ x 5)))
; => (6 7 8)

これは前節で大域的に行ったことをレキシカルに行っているものです。今回の5+はレキシカル変数(lambdaの引数)ですから、非推奨な処理ではありません。

しかし、せっかくletを使ったので、letで書き換えてみます。

(let ((5+ (lambda (x) (+ x 5))))
  (mapcar 5+ '(1 2 3)))
; => (6 7 8)

これはこれで特に違和感はありませんが、defvarに対してletがあるように、大域的なdefunに対してレキシカルな関数を定義するfletというオペレータがあります。fletを使うとlambdaが不要になります。

(flet ((5+ (x)  
         (+ x 5)))
  (mapcar #'5+ '(1 2 3)))
; => (6 7 8)

fletは関数の定義だけを行い、レキシカルクロージャは作成しないのでdefunと同じ扱いです。高階関数で5+を使うときはfunction(#')が必要です。レキシカル関数を使う場合、lambdaよりもfletの方が関数であることが明示されるので可読性が高まります。

multiple-value-bind

さて、様々な束縛オペレータを紹介しましたが、つるかめ算に戻りましょう。つるかめ算の問題が変則的で、「亀の数だけを答えよ」という問題だった時はどうすればいいでしょうか。

tsuru-kame関数を書き換えてしまうのは正しくはありません。関数の中身を書き換えると計算が一つ減りますが、つるかめ算は本質的には2つの解を持つ問題ですから、あえて1つの答えしか返さないように「改悪」する必要はありません。

そこで、tsuru-kame関数から返された多値を受け取り、亀だけを返せば変則的な問題にも対応できます。多値を受け取るのはmultiple-value-bindです。

(multiple-value-bind (tsuru kame)
    (tsuru-kame 8 26)
  kame)
; => 5

multiple-value-bindオペレータはlambdaと似た使い方ですが、引数リストの次の要素は多値オブジェクトとして評価される処理でなければなりません。

なお、多値オブジェクトを普通の方法で受け取ると最初の値だけが受け取れます。もし問題が「鶴の値だけを求めよ」であれば、以下のようになります。

(let ((tsuru (tsuru-kame 8 26)))
  tsuru)
; => 3

もちろんlambdaで受け取ってもいいですが、すでに述べたように束縛が同時に行われる場合はletを使用した方が可読性が高まります。

参考文献


Copyright © 2017- satoshiweb.net All rights reserved.