イジハピ！
Emacsを自由に使いこなすために、Lispを勉強している。
今は「Scheme手習い（The Little Schemer）」に取り組んでいる。（以降はTLSと略す）
全面的にクイズ形式になっていて、トレーニング・ペーパー形式で進められる楽しい本だ。
Lispが身につくかどうかはまだ明らかではない。
この本はとにかく再帰を練習する。
ありがちな例だと階乗というのがある。
n! = n x n-1 x n-2 x ... x 3 x 2 x 1
これはn人の人が並ぶ並び方と一緒な数である。
いま、aさんという人が並ぼうとすると、並び方はaさんが先頭でaさんが末尾の1通りだけである。
たった一人の人間が経っていることを、「並ぶ」というかどうか分からない。
ただ「立つ」と言う方が正しいのではないか。
そんな話は深入りしない。
とりあえず
1! = 1
である。
（ところで、0!も定義上1である。0人の人が並ぶときは「誰も並ばない」という1通りの場合の数しかないから？）
aさんとbさんが並ぶとすると、ab、baの2通りある。
2! = 2 x 1 = 2
先頭には、aさんが来るかbさんが来るかの2通りある。
末尾には、aさんがすでに並んでいればbさんが、bさんがすでに並んでいればaさんが来るしかないから、先頭が決まると自然に決まるので、1通りしかない。
aさんとbさんとcさんが並ぶとすると、abc、acb、bac、bca、cab、cbaの6通りある。
3! = 3 x 2 x 1 = 6
先頭には、aさんが来るかbさんが来るかcさんが来るかの3通りある。
この後の説明省いていいですか。
さて、階乗の計算方法の説明だが、
「nの階乗は、nに、n引く1を掛けて、n引く2を掛けて、それをその調子でそのままずーっと繰り返して、2を掛けて、1を掛ければいいんだよん」
と説明してもいいが、こう説明してもいい。
（１）nが1のときnの階乗は1である。
（２）nの階乗がn!であるとすると、n+1の階乗はn!にn+1を掛けたものである。
これが高校でよく習う、九州大学の入試でよく出るという、ブレーズ・パスカルが確立した数学的帰納法である。
（考え方じたいはギリシャ時代からあったそうだ。へー）
たとえば2の階乗を考える。
2の階乗は1の階乗に2を掛けて求められるが、1の階乗は1であったから、2の階乗は1に2を掛けたものであるので、2である。
1! = 1
2! = 1! x 2 = 1 x 2 = 2
へぇー。
3の階乗を考える。
3の階乗は2の階乗に3を掛けて求められるが、2の階乗は2であったから、3の階乗は2に3を掛けたものであるので、6である。
3! = 2! x 3 = 2 x 3 = 6
へぇーへぇーへぇー。
あと50個ぐらい検証していいですか。
やめておこう。
ということで、最初の一歩と、ある段階と次の段階の関係が分かれば、ドミノ倒し的に全部分かる。
数式で書くとこうなる。
1! = 1
n! = n x (n - 1)!
こういう式を漸化式という。
この場合の漸は、漸次に原発を廃炉するとか、漸進的に核武装をすすめるとかそういうのと一緒で、だんだん少しずつという意味だ。
Schemeで書くとこうなる。
(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
実行してみる。
gosh> (define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
!
gosh> (! 1)
1
gosh> (! 2)
2
gosh> (! 3)
6
gosh> (! 4)
24
gosh> (! 5)
120
gosh>
できてるっぽい。
では解説する。
(lambda (引数のリスト)
関数の中身))
というのは関数のテンプレートである。
lambdaというのはランバダという踊りではなくて（FAQ）、ギリシャ文字のλ（ラムダ）であるが、無名関数を返す関数である。
defineはlambdaが返した無名関数に関数名をつける関数である。
基本Lispは
（関数名 引数のリスト）
という形になっている。
(cond
(条件1 実行する式1)
(条件2 実行する式2)
・・・)
これ、条件も、実行する式も、たいてい()で囲むので、それをさらに()で囲むのが忘れやすい。
(= 式1 式2)
と書いて評価すると、式1と式2が等しいと#tを返し、等しくないと#fを返す。
最初に=を書くのが独特である。
この式だけ実験的に実行できる。
gosh> (= 1 1)
#t
gosh> (= 1 3)
#f
ほらねー。
ここが昔のマイコンのBASIC感覚で楽しい。
((= n 1) 1)
であるが、これはnが1のときは1を返す、ということになる。
最初の一歩だけは絶対に「こうだからこうなのだ！」と人為的に定義しないといけないのね。
もっとも、このプログラムの場合は、nが1か、1でないか、どっちかしかない。
(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
だが、最後の文だけカッコがものすごい。
カッコカッコカッコカッコ・・・という歌が昔あったが（山口百恵「ロックンロール・ウィドウ」）それぐらいすごい。
これ、字下げをちゃんと合わせてやるともっと見やすいのではないだろうか。
(define !
(lambda (n)
(cond
(
(= n 1)
1
)
(else
(* n
(!
(- n 1)
)
)
)
)
)
)
たいして見やすくならない。
これ、Lispを勉強しはじめの人が必ず最初にやってみてハマる落とし穴だそうである。
見事にハマってしまった。
実際には、カッコにカーソルを当てると対応したカッコが水色に光るようにEmacsを設定しているので、それほど苦にならない。
Emacsの設定 - karetta.jp
(else (* n (! (- n 1)))))))
は、nが1でないときの実行部分である。
もっとも、末尾の)))は、(define、(lambda、(condに対応する閉じカッコであって、実質的にnが1でないときの実行部分は以下のようである。
(else (* n (! (- n 1))))
これは、
n x (n - 1)!
を表している。
(* 2 3)は6を返す。
gosh> (* 2 3)
6
ほらね。
これが昔のBASIC感覚で。
それはもう前に書いた。
実験は略す。
(else (* n (! (- n 1))))
を内側から研究すると、
(- n 1)
は
n - 1
だから、
(! (- n 1))
は、
(n - 1)!
になる。
ここが再帰しているー！
いま、作りかけの!という関数のその中で、!を使っているー！
それでいいんですか？
いいんです！
なぜなら引数を1減らしているからだ。
1減らした数について!を計算すると、その中で1減らす。
どんな数であっても、1ずつ減らしていくと、いつかは1にたどり着く。
で、1の場合だけはもう定義してあるのである。
で、
(* n (! (- n 1)))
は、
n x (n - 1)!
になる。
だったらそういう風に、普通の算数っぽい順番に書くように作ればいいのにね。
それはLispを研究している人も昔から重々承知でいろいろやっているけど、うまくいかないそうだ。
よく知らない。
とりあえずプログラムが出来たので実行してみよう。
を実行する。
(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
において、引数nが1になるから、
((= n 1) 1)
が実行されて、1が返る。
それはまあいいね。
を実行する。
(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
において、引数nが2になるから、elseに入る。
(else (* n (! (- n 1))))
は、
(else (* 2 (! (- 2 1))))
になる。(- 2 1)は1であるから、
(else (* 2 (! 1)))
になる。(! 1)は1であるから、
(else (* 2 1))
であるから
(else 2)
になって、2が返る。
合ってるーー！！！
#! /usr/local/bin/perl
# factorial.pl --- 階乗の計算
use strict;
use warnings;
use 5.10.0;
say &factorial(shift);
sub factorial {
my $n = shift;
if ($n == 1) {
return 1;
} else {
return $n * &factorial($n - 1);
}
}
実行してみる。
$ factorial.pl 1
1
$ factorial.pl 2
2
$ factorial.pl 3
6
こういうのが「Scheme手習い」には百個以上？出てくる。
楽しい。
それでは、今日も話が長くなったが、今宵はこの歌でお別れしましょう。
山口百恵さんで「ロックンロール・ウィドウ」。
今は「Scheme手習い（The Little Schemer）」に取り組んでいる。（以降はTLSと略す）
全面的にクイズ形式になっていて、トレーニング・ペーパー形式で進められる楽しい本だ。
Lispが身につくかどうかはまだ明らかではない。
この本はとにかく再帰を練習する。
再帰
再帰とは、カンタンに言うと自分自身を呼び出す関数を書くことだ。ありがちな例だと階乗というのがある。
n! = n x n-1 x n-2 x ... x 3 x 2 x 1
これはn人の人が並ぶ並び方と一緒な数である。
いま、aさんという人が並ぼうとすると、並び方はaさんが先頭でaさんが末尾の1通りだけである。
たった一人の人間が経っていることを、「並ぶ」というかどうか分からない。
ただ「立つ」と言う方が正しいのではないか。
そんな話は深入りしない。
とりあえず
1! = 1
である。
（ところで、0!も定義上1である。0人の人が並ぶときは「誰も並ばない」という1通りの場合の数しかないから？）
aさんとbさんが並ぶとすると、ab、baの2通りある。
2! = 2 x 1 = 2
先頭には、aさんが来るかbさんが来るかの2通りある。
末尾には、aさんがすでに並んでいればbさんが、bさんがすでに並んでいればaさんが来るしかないから、先頭が決まると自然に決まるので、1通りしかない。
aさんとbさんとcさんが並ぶとすると、abc、acb、bac、bca、cab、cbaの6通りある。
3! = 3 x 2 x 1 = 6
先頭には、aさんが来るかbさんが来るかcさんが来るかの3通りある。
この後の説明省いていいですか。
さて、階乗の計算方法の説明だが、
「nの階乗は、nに、n引く1を掛けて、n引く2を掛けて、それをその調子でそのままずーっと繰り返して、2を掛けて、1を掛ければいいんだよん」
と説明してもいいが、こう説明してもいい。
（１）nが1のときnの階乗は1である。
（２）nの階乗がn!であるとすると、n+1の階乗はn!にn+1を掛けたものである。
これが高校でよく習う、九州大学の入試でよく出るという、ブレーズ・パスカルが確立した数学的帰納法である。
（考え方じたいはギリシャ時代からあったそうだ。へー）
たとえば2の階乗を考える。
2の階乗は1の階乗に2を掛けて求められるが、1の階乗は1であったから、2の階乗は1に2を掛けたものであるので、2である。
1! = 1
2! = 1! x 2 = 1 x 2 = 2
へぇー。
3の階乗を考える。
3の階乗は2の階乗に3を掛けて求められるが、2の階乗は2であったから、3の階乗は2に3を掛けたものであるので、6である。
3! = 2! x 3 = 2 x 3 = 6
へぇーへぇーへぇー。
あと50個ぐらい検証していいですか。
やめておこう。
ということで、最初の一歩と、ある段階と次の段階の関係が分かれば、ドミノ倒し的に全部分かる。
数式で書くとこうなる。
1! = 1
n! = n x (n - 1)!
こういう式を漸化式という。
この場合の漸は、漸次に原発を廃炉するとか、漸進的に核武装をすすめるとかそういうのと一緒で、だんだん少しずつという意味だ。
Lispで書く
で、これをLispで書く。Schemeで書くとこうなる。
(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
実行してみる。
gosh> (define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
!
gosh> (! 1)
1
gosh> (! 2)
2
gosh> (! 3)
6
gosh> (! 4)
24
gosh> (! 5)
120
gosh>
できてるっぽい。
では解説する。
define
(define 関数名(lambda (引数のリスト)
関数の中身))
というのは関数のテンプレートである。
lambdaというのはランバダという踊りではなくて（FAQ）、ギリシャ文字のλ（ラムダ）であるが、無名関数を返す関数である。
defineはlambdaが返した無名関数に関数名をつける関数である。
基本Lispは
（関数名 引数のリスト）
という形になっている。
cond
condというのはcondition（条件）の略で、枝分かれをする式である。(cond
(条件1 実行する式1)
(条件2 実行する式2)
・・・)
これ、条件も、実行する式も、たいてい()で囲むので、それをさらに()で囲むのが忘れやすい。
=
=はイコールである。(= 式1 式2)
と書いて評価すると、式1と式2が等しいと#tを返し、等しくないと#fを返す。
最初に=を書くのが独特である。
この式だけ実験的に実行できる。
gosh> (= 1 1)
#t
gosh> (= 1 3)
#f
ほらねー。
ここが昔のマイコンのBASIC感覚で楽しい。
nが1のとき
ということで、最初のcondの条件／実行する式のセットは((= n 1) 1)
であるが、これはnが1のときは1を返す、ということになる。
最初の一歩だけは絶対に「こうだからこうなのだ！」と人為的に定義しないといけないのね。
else
condの最後の条件として、elseと書くと、それまでのあらゆる条件が満たされなかった場合に実行される条件となる。もっとも、このプログラムの場合は、nが1か、1でないか、どっちかしかない。
nが1でないとき
いま書いているプログラムの、(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
だが、最後の文だけカッコがものすごい。
カッコカッコカッコカッコ・・・という歌が昔あったが（山口百恵「ロックンロール・ウィドウ」）それぐらいすごい。
これ、字下げをちゃんと合わせてやるともっと見やすいのではないだろうか。
(define !
(lambda (n)
(cond
(
(= n 1)
1
)
(else
(* n
(!
(- n 1)
)
)
)
)
)
)
たいして見やすくならない。
これ、Lispを勉強しはじめの人が必ず最初にやってみてハマる落とし穴だそうである。
見事にハマってしまった。
実際には、カッコにカーソルを当てると対応したカッコが水色に光るようにEmacsを設定しているので、それほど苦にならない。
Emacsの設定 - karetta.jp
(else (* n (! (- n 1)))))))
は、nが1でないときの実行部分である。
もっとも、末尾の)))は、(define、(lambda、(condに対応する閉じカッコであって、実質的にnが1でないときの実行部分は以下のようである。
(else (* n (! (- n 1))))
これは、
n x (n - 1)!
を表している。
*
*は掛け算を示す。(* 2 3)は6を返す。
gosh> (* 2 3)
6
ほらね。
これが昔のBASIC感覚で。
それはもう前に書いた。
-
-は引き算だ。実験は略す。
再帰！
ということで、(else (* n (! (- n 1))))
を内側から研究すると、
(- n 1)
は
n - 1
だから、
(! (- n 1))
は、
(n - 1)!
になる。
ここが再帰しているー！
いま、作りかけの!という関数のその中で、!を使っているー！
それでいいんですか？
いいんです！
なぜなら引数を1減らしているからだ。
1減らした数について!を計算すると、その中で1減らす。
どんな数であっても、1ずつ減らしていくと、いつかは1にたどり着く。
で、1の場合だけはもう定義してあるのである。
で、
(* n (! (- n 1)))
は、
n x (n - 1)!
になる。
だったらそういう風に、普通の算数っぽい順番に書くように作ればいいのにね。
それはLispを研究している人も昔から重々承知でいろいろやっているけど、うまくいかないそうだ。
よく知らない。
とりあえずプログラムが出来たので実行してみよう。
nが1のとき
(! 1)を実行する。
(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
において、引数nが1になるから、
((= n 1) 1)
が実行されて、1が返る。
それはまあいいね。
nが2のとき
(! 2)を実行する。
(define !
(lambda (n)
(cond
((= n 1) 1)
(else (* n (! (- n 1)))))))
において、引数nが2になるから、elseに入る。
(else (* n (! (- n 1))))
は、
(else (* 2 (! (- 2 1))))
になる。(- 2 1)は1であるから、
(else (* 2 (! 1)))
になる。(! 1)は1であるから、
(else (* 2 1))
であるから
(else 2)
になって、2が返る。
合ってるーー！！！
nが3のとき
は、もう検証しなくていいですか。Perlに移植してみる
Perlも再帰できるから、移植してみる。#! /usr/local/bin/perl
# factorial.pl --- 階乗の計算
use strict;
use warnings;
use 5.10.0;
say &factorial(shift);
sub factorial {
my $n = shift;
if ($n == 1) {
return 1;
} else {
return $n * &factorial($n - 1);
}
}
実行してみる。
$ factorial.pl 1
1
$ factorial.pl 2
2
$ factorial.pl 3
6
こういうのが「Scheme手習い」には百個以上？出てくる。
楽しい。
それでは、今日も話が長くなったが、今宵はこの歌でお別れしましょう。
山口百恵さんで「ロックンロール・ウィドウ」。
