進捗遅くなった、って見る向きもあるだろうけど、「リリカル☆Lisp」って以前にも言ったけど、進めば進むほど章末の練習問題の歯ごたえが増していくんだ。
それを考えると、結構ハイペースだと思う。
天才型かもしれん。
ここではちょっとしたトリビアを。
コンス、ってのは確かに重要なLisp用語なんだけど、実はこれはconstructorの略称です。
オブジェクト指向に慣れてる人は、オブジェクト生成機構をコンストラクタ、って呼んだりするの知ってると思うんだけど、実は両者とも語源は全く同じ。
っつーか、プログラミング言語用語でコンストラクタ、ってのはまさしく「データ型を生み出す機能」って考えて良いです。
これ、パッと見だと「ウゲ、ややこしい」って思うかもしれないけど、かなり重要です。
っつーか、プログラミング上「等しい」って何をもって定義するのか、ってのは実はどのプログラミング言語でも悩ましい問題なの。
同一のオブジェクトだったら「等しい」って言って良いけど、じゃあ別々のオブジェクトだけど内容が同じだったらどーすんだろ、とか結構ややこしい事が多いのね。
例えばここに星田さんがいて、星田さんと星田さんが同じか、って訊かれれば、同一オブジェクトなんで「等しい」は成立する。
じゃあ、仮に星田さんが一卵性双生児だったとしよう。もう一人が星田(弟)だったとして、星田さんと星田(弟)氏は同一と見なして良いのか?遺伝子レベルでは全く同じだからな。
こういう事がしょっちゅうプログラミングでは起こり得て、むしろLispは全てのケースに於いて、「どんな比較でもドンと来ーーーい」と親切に色々と用意している。
なお、C言語では「二つが全く同じオブジェクトを指してるのか」と言うのは悪名高いポインタ、を使って比較するので、「オブジェクトがどーのこーの」って考えさせない辺りは、低レベル言語だけあってさすが、です。
なお、Schemeでは「メンド臭ければeq?とequal?の中間のeqv?を使え」と言う格言があって(笑)、大体初心者状態の時はこれで切り抜けます(笑)。
んでまあ、共用してるデータの置き換えに注意みたいな話があって・・
そう、破壊的変更には気をつけよう。
ちなみに、Scheme方言のRacketにはこのset-car!とかset-cdr!が存在しない。
一方、こうやって実験する際に「破壊的変更が出来ない」って言われても困っちゃう。
これらを使うと、上のリリカル☆Lispの写真で紹介されてるコードは次のように書く事が出来る。
(define x
(mcons 8
(mcons 9
(mcons 10 '()))))
(define y (mcdr x))
とまぁ、結果の見た目がちと違うが、基本的にはリリカル☆Lispが説明した通りの解となる。
今回の問題。なぜか今回はこのヒントの部分と、途中の「ここ出ますよ！」って言ってたところをそのまま書くと正解でした。だが・・実際はよく分かってないのに正解してしまった印象。これはちゃんと振り返って理解してないところを洗い出さねば・・。
そう、今回の再帰の課題はこのブログでも解説した事があるけど、末尾再帰だ。
ちなみに、ここの章末問題のように、末尾再帰関数を呼び出す為のsと末尾再帰エンジンsiに分けて書く、と言うのはScheme形式と言うよか、どっちかっつーとANSI Common Lispの方で良く行われる形式だ。
(defun s (n)
(si n 0))
(defun si (n x)
(if (zerop n)
x(si (1- n) (+ n x))))
一方、Schemeでは通常、なんでも再帰で川合史朗さんがやってるようなローカル関数(作成法をインターナルdefineとか呼んだりするが※1)を作成するか、
(define (s n)
(define (si n x)
(if (zero? n)
x
(si (- n 1) (+ n x))))
(si n 0))
あるいは名前付きletとかnamed-letと呼ばれる構文を用いる。
(define (s n)
(let si ((n n) (x 0))
(if (zero? n)
x
(si (- n 1) (+ n x)))))
そう、Schemerは全然forは欲しがらないんだけど、名前付きletは大好きだ。これが無ければループが書けないって程、である。
そしてここで見たように、同じLispでもANSI Common LispとSchemeは随分と流儀が違う。
大まかには、ANSI Common Lispはガンガン関数を置いていくのに対し、Schemeだとローカル関数を多用して、全部内側に置こうとする傾向が強い。
また、ANSI Common Lispでは再帰は使うけどScheme程多用しない。従って名前付きletなんつー構文もサポートしていない。結果、マクロの宿題として「名前付きletを書きなさい」なんつー問題が出るくらい、である。
一応、末尾再帰最適化の話もこのブログで書いた事があります。
そして残念ながらPythonには末尾再帰最適化の機能がない。
def fact(n):
def fact2i(n, x):
if n == 0:
return x
else:
return fact2i(n - 1, x * n)
return fact2i(n, 1)
だからPythonでは人力で末尾再帰を最適化するしかないです。
def fact(n):
def fact2i(n, x):
while True:
if n == 0:
return x
else:
x *= n
n -= 1
return fact2i(n, 1)
ただし、何度も言いますが、while True: 〜 で反復を書ける人には、フツーの再帰より末尾再帰の方が簡単です。最適化が出来るくらいなんだから、実は二つ共書いてるロジックはほぼ同一、って言って良いのです。
あと、聞き手の「すずか」ちゃんが異様に理解力が高くて嫉妬
それを人は予定調和、と呼ぶ(謎
普通の単純な再帰を使った階乗計算は仕事中に突然理解出来た（Ifの次の数が０だったり１だったりするのが謎だったｗ。足し算は０じゃないと困るし掛け算は１じゃないと困るってだけの事ですよね？）。
そうそう。
初期値はなんでもいいんだけど、階乗計算の時は初期値は0より大きくないと、「行った計算が無駄になる」んで(笑)
なお余談ですが。PythonもLispも凄いのよ。階乗計算って解が整数なわけなんだけど、すぐデカくなり過ぎてコンピュータでそのまま扱うには凄く厄介な範疇に飛び込むのね。でもPythonもLispも「ヘーキな顔して」デカイ整数を扱う。
んで、桁数を最終的にどうするんか、って問題はあるんだけど、基本的にC言語みたいな貧弱な言語だと整数のまま階乗計算は行えないのね。
このままじゃダメ => n × (n - 1) × (n - 2) × ... × 3 × 2 × 1
そこで底は理論上は何でもいいんだけど全部対数にしちゃって和を取るの。
log|n| + log|n - 1| + log|n - 2| + ... + log|3| + log|2| + log|1|
log|1|は底が何だろうと0だし。つまりこれが初期値だわな。
だから、C言語とかだと基本的には次のように計算するのね。
(define (fact n)
(let fact2i ((n n) (x 0))
(if (zero? n)
(inexact->exact (round (exp x)))(fact2i (- n 1) (+ (log n) x)))))
Pythonだと次のようなカンジ。あくまで「カンジ」だけど。
def fact(n):
from math import exp, log
return int(round(exp(sum([log(i) for i in range(1, n)]))))
これが・・うーん・・？ (cons (car x)(app (cdr x) y))))って最後のリストyに足していってるってことなんだろうけど、(car x)(app (cdr x)の部分はカッコでくくった１まとまりって事でこの部分だけが再帰処理されてるってことでエエんやろか・・・じゃないと、acd→bacdになりそうだしなぁ・・。
難しいでしょ(笑)?
そう、これが出来たら再帰初心者卒業なのよ。
ここでも書いたけどまさしくappendだ。これを自作出来るか読んで理解出来ればまずは当分大丈夫なんだ。
いや、一生大丈夫かもしんね。
よって、これ「だけ」はアタマ悩まして苦しむ価値があります。これが理解出来たら眼の前が開ける。童貞卒業した時のような感動がある(笑)。
Paizaのオンライン実行環境Schemeに入れてもエラーだったり何も出なかったり・・
うん、何故ならその辺のコードはSchemeじゃなくって恐らくANSI Common Lispのモノだからな(笑)。
- Scheme -> 関数定義は (define foo (lambda (x ...) か (define (foo x ...) で書き始める
- ANSI Common Lisp -> 関数定義は (defun foo (x ...) で書き始める
ので、実は形式が違うのです。
関係ないけど上から流れてゆく癖がついてるので、先にfact-recが書かれてないのがすごい違和感。
そう、実はLispだと、マクロは別格なんだけど、関数がファイル上でどういう順番で定義されてるのか、ってのは割にユルくてどーでもいい。
言い換えると自分で読みやすいように順番を決めて良い。
だからC言語みたいに関数の定義順序が大事で、変える時にはプロトタイプ宣言が必要な言語、とか余計イライラするわけだ(笑)。
Pythonのクラスに関しては、ちょっとここで説明すれば長くなりそうなんで、暇を見つけたら纏めて書いてみようか、と思う。
ゲームに関してもね。
取り敢えず今回はここで終了。
※1: ローカル関数自体はPythonでも使える為、覚えておいて良い手法である。
def s(n):
def si(n, x):
if n == 0:
return x
else:
return si(n - 1, n + x)
return si(n, 0)
言い換えると「ローカル関数がない」C言語出身者は、ローカル関数なんつーものを思いつきもしない。
※2: しかし、両者ともClojureと言うこれまた別種の「第3のLisp」が入ってるからたまげる。ANSI Common Lisp、Schemeに比べると最新のLispと言って良い。
ClojureはJVM(Java仮想マシン)上で動く事を念頭に置いて作られていて、Javaの豊富なライブラリを使い回せる、と言った実用性に重きを置いた久々のLispである。言い換えるとJavaに寄生したコバンザメである(謎
それで酷けりゃシンイチに寄生したミギーだ(笑)。シンイチは弱くてもミギーは滅茶苦茶強い、ってのも良く似てる。
もっとも、これはClojureの専売特許ではなく、Twitterを書いてるScalaなんて言語も同じアイディアで、JVM上で動いている。
いずれにせよ、新参の割には熱狂的なファンが多いLisp方言である。
Clojureでのコードは以下のようになる。
(defn fact[n]
(if (= n 0) 1 (* n (fact (- n 1)))))(defn sum[l]
(if (empty? l) 0 (+ (first l) (sum (rest l)))))(defn app [x y]
(if (empty? x)
y
(cons (first x) (app (rest x) y))))
