メモ： スキーム手習い
リスト遊びの巻末には
再帰などの技法を極めるために次に読むべき本は Friedman 氏と Felleisen 氏著 "The Little Schemer" ( MIT Press ) です。
とあって、しかしその邦訳版である「スキーム手習い」は絶版しているとある（2000年６月）。昨日無理やりリスト遊びは最後まで目を通した。で、上記の「スキーム手習い」が気になったのでメモ。
Amazon.co.jp： Scheme手習い: Daniel P. Friedman, Matthias Felleisen, 元吉 文男, 横山 晶一: 本
lisp フィボナッチ関数と二重再帰
よくあるLISPの例題にフィボナッチ数列の二重再帰の式があるのだけど、とりあえずトレースできていそうな手応えを得るまでに2週間も掛かった。あんまりわからないものだから色々手をつけているけど、これじゃあ死ぬまでにはとても終わりそうにないな。
解けるようになると何でもないのは根本的に解っていないせいだろう。
フィボナッチ数列の定義
最初のフィボナッチ数は1
次のフィボナッチ数も1
それ以降のフィボナッチ数は二つ前とひとつ前のフィボナッチ数を足して作ります。
1,1,2,3,5,8,13...
（リスト遊び p55 ss4.3 フィボナッチ数列、山本和彦 2000/06/01）
で、その例題は
M.HiroiさんのXyzzy LISP Programming の LIST7 フィボナッチ関数（再帰版）
(defun fibo (x)
(if (or (= 0 x) (= 1 x))
1
(+ (fibo (- x 1)) (fibo (- x 2)))))
fibo(x)に0から5を代入して上記の式を解く。
- (fibo(0)) = 1
- (fibo(1)) = 1
- (fibo(2)) = (+ (fibo(- 2 1)) (fibo(- 2 2))) = (+ (fibo(1)) (fibo(0))) = (+ 1 1) = 2
- (fibo(3)) = (+ (fibo(- 3 1)) (fibo(- 3 2))) = (+ (fibo(2)) (fibo(1))) = (+ 2 1) = 3
- (fibo(4)) = (+ (fibo(- 4 1)) (fibo(- 4 2))) = (+ (fibo(3)) (fibo(2))) = (+ 3 2) = 5
- (fibo(5)) = (+ (fibo(- 5 1)) (fibo(- 5 2))) = (+ (fibo(4)) (fibo(3))) = (+ 5 3) = 8
(fibo(x))を5で解くと
- (fibo(5)) = (+ (fibo(- 5 1)) (fibo(- 5 2))) = (+ (fibo(4)) (fibo(3)))
- 左から右へ展開して一回目の展開は完了。（上記のリスト６）
- この後(fibo(4))、(fibo(3))と展開は再帰呼び出しされて(fibo(0))まで進む。（５から１へ）
- するとカッコの殻を破って値が顔をだすので逆の順番で足し算が始まる。（１から６へ）
なんだか辻褄合わせで解けたような、それでいて理解はできていないような。ゆっくりでも進むしかない。
メモ : Nexus7 + TK-FBP052 + ELECOM Keyboard layout
Nexus7(2012)用に TK-FBP052 を購入。
購入後にしたこと。
- 乾電池をキーボード本体に入れる
- キーボードの電源をonにする
- Nexus7のbtをonにする（設定-bluetooth）
- デバイスの検索をする（設定-bluetooth-デバイスの検索）
- キーボードの[fn]+[Esc]を押してキーボード側のペアリングを開始
- Nexus7に表示されるn桁の数字の入力と[Enter]の打鍵でペアリングを完了
- 何かのアプリケーションで入力（多分英語キーボード配列で入力される
- GooglePlayでELECOM Keyboard layoutを検索
- ELECOM Keyboard layoutをインストール
- Nexus7を再起動
- http://www.elecom.co.jp/news/201310/keyboardlayout/ にある通りに設定
メモ Windows で Common Lisp の練習環境は Xyzzy
見出のとおり、日本のWindowsユーザには Xyzzy という Common Lisp 環境があるじゃないですか、というネタ。
AutoLISP と Common Lisp と代入 - 阿房峠 で挙げたとおり、AutoLISPがCommon Lisp のサブセット+図形編集コマンドであるとすると、再帰も使えるのではないかと考えているのだけど、再帰を使った AutoLISP のコードはまだ見てない。再帰じゃなくて多分 while で記述できるだろうし、AutoCADのユーザはたぶんCとかVBとかVBAとかの手続き型の言語を使っている人が多いだろう。
探し方が悪いだけできっとあるのだろう。検索キーワードも"再帰"と漢字なので英語の検索はしていない。AutoLISPで再帰がつかえたらなんかいいのかと聞かれても、何も返せない。悟りが開けるらしいとか、……云々。
自分のことを挙げれば関数の展開がわかっていない。返り値の格納場所とか言ってる時点で多分間違い。関数が鉛筆で解けない。だから再帰がわからないし頓珍漢な答えをだすのだ。
でも、AutoLISP ではメニューマクロの置き換え位はできるようになった。ところが公開されている AutoLISP が読めてはいない。コードを追って値がどうなっているのか説明できる自信がない。ということで、他のLISPで何かをつかめればいいなあと思うのだった。
お盆の間は 「Land of Lisp」 をやって、「リスト遊び」と「もう一つのScheme入門」を読んでいたのだけれど困ったのは実行環境だった。Emacs は使っているから EmacsLisp は困らないのだけれど Land of Lisp は CLISP で書かれているので CLISPの実行環境がいる(ちなみにSchemeはNexus7で実行してる)。ところが本文で示されたURLは"帯域使い杉"とかで制限されてる。仕方なくgoogleで検索してlispboxの中のclisp.exeだけ使ったりするんだけど、これってマニアック過ぎないのだろうか。WindowsユーザでLispをやってみたい人はみんなEmacsな人なのだろうかと思ったところで、気がついた。
Xyzzy がありました。しかも、Xyzzy で Common Lisp 入門 も Makoto HIROI さんが作ってくれてる。これがいいんじゃないかな。今晩帰ったら早速始めたいと思います。そのためのメモ。
xyzzyはWindowsで動作するテキストエディタ。Emacsと一般的なテキストエディタの利点を取り込んでいる。作者は亀井哲弥。マクロ言語としてCommon Lisp系のxyzzy Lispを実装しており、高機能なLisp処理系としての側面も持つ。現在は派生版の開発が続いている。
xyzzy はカスタマイズ可能で軽快な Windows 用のテキストエディタのようなものです。 作者も使ったことのないような機能を満載しています。
xyzzy - カスタマイズ可能で軽快な Windows 用テキストエディタ
Xyzzy Wiki †
亀井さん作成のエディタxyzzyに関する情報をまとめるwikiです。オフィシャルなwikiでは無いのでご注意ください。
はじめに
xyzzy は 亀井哲弥氏 が作成された Emacs 系のエディタです。xyzzy に搭載されている Lisp (以後 xyzzy Lisp と記述) は、Lisp の標準である Common Lisp に準拠 [*1] している優れた処理系です。この xyzzy Lisp を使って、Lisp でプログラミングを楽しもうというのが本ページの趣旨であります。Lisp は初めてという方は Common Lisp 入門 を読んでみてください。Common Lisp の基本を詳しく説明しています。
M.Hiroi's Home Page / xyzzy Lisp Programming
そして、Lisp をすすめる最大の理由が、プログラミングが簡単でとても面白いからです。少し勉強しただけで、プログラムを作ることができるようになります。Emacs Lisp は仕様が旧式なため少々使いにくいところがありますが、xyzzy Lisp ならば大丈夫です。優秀な処理系が身近にあるのですから、これを機会に Lisp の世界に足を踏み入れてみましょう。
M.Hiroi's Home Page / xyzzy Lisp Programming Common Lisp 入門
丸善に来たからって舞い上がって、Land of Lisp を買うんじゃなかった。まずは、XyzzyでCommon Lispだったな。ずいぶん遠回りしたものだ。
Android で Scheme
Here's a preliminary version of Gambit Scheme for the Android platform, inspired by Marc Feeley's iOS version.
Gambit Scheme is a "complete, portable, efficient, and reliable implementation of the Scheme programming language, conforming to the R4RS, R5RS and IEEE Scheme standards, and implementing all optional features. Tail calls and first class continuations conform to the Scheme semantics. The full numeric tower is implemented, including: arbitrary precision integers (bignums), rationals, inexact reals (floating point numbers), and complex numbers."
Gambit for Android includes the ability to interact with a Gambit Scheme REPL (read-evaluate-print-loop), add and save Scheme scripts, and start and telnet into a REPL server running on the device.
Gambit for Android - Google Play の Android アプリ
PCが手元にあるときは Common Lisp でも Scheme でも実行環境があるからいいのだけど、枕元とかで本を読んでいる時に関数を試してみたい時があって、以前から ○○lispとか○○Scheme とかを Nexus7 に落としては試していた。実際に関数を入れてみると例題にある式と返り値が違っていたり、組み込み関数？がなかったりでがっかりするのだった。
ついに今日は使える環境にたどり着いて、上記の Gambit で紫藤さんのもう一つのScheme入門を楽しんでいる。３章までの四則演算やリストの評価もテキストとおりに返ってくる。楽しい。
AutoLISP と Common Lisp と代入
- 実はXLISP、と一概に言っても、Ver.1.0、2.0、と3.0ではまるで違う言語である。
- XLISP1.0は過去の(現代の観点から言うと)貧弱なハードウェアでも動く小さいオブジェクト指向のLisp方言、XLISP2.0はCommon Lispのサブセットであった。
- AutodeskのVisual LISPはXLISP1.0から派生している。
ということで、AutoLISPの練習としてCommon Lispを練習している。Common Lispの参考書は新しいものは少なくてしかも激高なのでつい、Schemeの入門書のようなところに手を出してしまう。そこには
Scheme は基本的に関数型プログラミング言語なので、基本的には代入を用いないでプログラムを書くことができます。しかし、代入を用いたほうがかえって簡潔に書ける場合もあり、 内部状態や継続を利用する時は代入を使う必要があります。
https://www.shido.info/lisp/scheme_asg.html もう一つのScheme入門 10.代入
と書いてある。代入しないなんて……。どうしたらいいんだろう。とまた手が止まる。
まあ、そういう時はあれだ、Google先生だ。で聞いた結果、やっぱりいつもの先生方との対面となるのだった。
関数型プログラミングでは、よく「代入は使ってはならない」と言われます。関数型言語の一種である Emacs Lisp を生業とする僕は、この言葉に長年悩まされてきました。代入を使わないで実用的なプログラムを書くことは無理だからです。
Emacs Lisp は、Common Lisp に近く、Common Lisp は命令型言語ですので、再代入は避けられないというのが、最近の僕の結論です。
関数型プログラミングと代入 - あどけない話 （山本和彦さん）
なので、安心してAutoLISPではsetqすることにした。
山本さんみたいなすごいヒトでも、呪いに縛られることがあるのか。しかし、それを解決できるところがすごいヒトのすごいところ。（なんだか「すごい」ってのは、言葉としてはずいぶんと安い感じではあるとは思うけど）
ちなみに、自分では自分自身、擬似科学とか代替医療とかにはわりと鼻が利くホウだと思っているのだけど、ことプログラミングのこととなるとまったく自信がない。多分代替医療に嵌るヒトはこういうプロセスを踏むことができずに、何を信用していいのかわからずに、でも何かを選択せざるを得ない状況で、仕方なく選んでしまうのだと思う。選んでしまえばそこには慣性が生じるので捨てることは難しいのでは、と思うのだった。
ところが、Lisp は完全な関数型言語ではありません。引数以外の変数を定義して、setq などで値を代入することができるからです。つまり、変数の値を書き換えることでプログラムを実行する「手続き型言語」の機能もあるわけです。とくに Common Lisp の場合、手続き型言語からいろいろな機能が持ち込まれたため、ほかの関数型言語に比べると不純度の高い関数型言語になっています。
M.Hiroi's Home Page / xyzzy Lisp Programming
ここにも！！。
再帰
先日からLand of Lispを読み進めている。目的は再帰とlambdaの理解なのだけど最初に出てきた再帰の式だけでも？？？が浮かんで前に進まない。
というわけで、わからないことはGoogle先生に聴くとこにした。
その中でも理解できそうなページは以下のもの。
7. 繰り返し
1. 初めに
今回は繰り返しについて説明します。繰り返しができれば、一通りプログラムを書くことができます。 繰り返しのための構文 do もありますが、一般に、Scheme は繰り返しのために再帰を使います。
2. 再帰再帰関数とは関数定義の中で自分自身を呼び出す関数です。 慣れないと奇妙な感じがしますが、慣れてしまえば、気にならなくなります。
https://www.shido.info/lisp/idx_scm.html もう一つのScheme入門（紫藤貴文さん）
https://www.shido.info/lisp/scheme7.html 7.繰り返し
再帰関数(初級) - 八発白中 （深町英太郎さん）
再帰関数(上級) - 八発白中 こちらには末尾再帰の例が載っている。
紫藤さんのページも平行して読んでいたのだけどそこまでは進んでいないし、深町さんのページもいつも検索には引っかかるのだけど読んでおらず、改めて本気で読まないと頭に入らないなあと。ただし、Land of Lispの例文にある (1+ hoge hoge）の(1+)の返り値はどこに溜め込むのは理解できてない。形としては、アンチョコとして使えるとは思うのだけど、他人には説明できないなあ。
アンチョコということでは、
lispの再帰関数，関数作成の練習 - Set::prototype
には数十もの再帰の例が載っていた。
さて、Land of Lispの訳者で役者（
川合史朗＠Gaucheは、ハワイで俳優をしている｜【Tech総研】
）の川合史郎さんのサイト
http://practical-scheme.net/index-j.html
）には、「なんでも再帰」（
http://practical-scheme.net/docs/tailcall-j.html
）というページでCのforとSchemeの再帰の比較をしている。これもまあ、全く理解できない。いつかわかる日が来るのだろうか？
それとPaul Graham氏の記事の翻訳が多数。
