なんか星田さんがどんどんLisperになっていってる(笑)。もう少しで星田オステオパシーならぬ星田トマベチーとかに進化しそうである(謎
そこで、星田さんの進化を畏れながら(笑)、今回もちょっとした補足説明をしていこうと思う。
色々と組み込み関数が出てきました。てっきりCARとCDRとCONSとIFだけでなんとかするパズルみたいな言語なのかと思ったよｗ
わはははははwwwww
ただし、ある意味正しい、です。
これを応用して「こういうカタチのアセンブリが書けね?」と論文を発表したのがジョン・マッカーシー、と言う人です。
そう、まずはLispは論文として「アセンブリの代替案」として発表された。
ここで語られた「論文上のLisp」を純Lisp、等と呼んだりします。
純Lispとは
5つの関数:
- atom: Schemeだと(define (atom x) (not (pair? x)))
- eq: Schemeだと (define eq eq?)
- car
- cdr
- cons
そして4つの特殊形式
- cond または if等の条件式
- quoteと言う評価停止命令
- lambdaと言う関数生成命令
- defineと言う束縛命令
さえあればプログラミングは何とかなるんだ、と言う理論的な提案です。他は全部これらで定義出来る、と言う。
これちょっと考えてみれば凄いんですよ。これがアセンブリ言語の代替に成り得るのなら、アセンブリが機械語と一対一対応ならば、機械語もLispになれる。と言う事はCPUそのものもLispで作れる、って事を示唆している。
もっともマッカーシーと言う人は理論上のある種お遊びとして考えてたようですが、彼のお弟子さん(笑)、世界ではじめてビデオゲームを作ったスティーブ・ラッセルって人がセンセが書いた論文を読んで
「あれ、これってそのままプログラムしたらエエんじゃね?」
と気づいた。実はこの時点では高級言語はBASICの親分みたいなFortranしかなかったし、って事はコンパイラしかなかった。
ってなわけで、世界ではじめてのインタプリタ、Lispが登場した、ってワケ。
と言うわけで、少なくとも「基本関数」は物凄く重要だと思われてるんで、特に「基本を重視する」あるいは「時間がなくて多くのモノが教えられない」場合は、atom、eq、car、cdr、consの5つはしつこいくらい丁寧に教えるわけです。
末尾再帰での書き換えか・・・一体どう違うのかよく分かってないので実行環境を入れたら色々とサンプルを試してみよう
これだね。
(define (cont? x l)
(cond
((null? l) #f)
((eq? x (car l)) #t)
(else
(cont? x (cdr l)))))
xがリストlに含まれてれば #t、含まなければ#fを返す関数ですね。
実は大方のLisp(ANSI Common LispやScheme)ではmemberって関数が提供されています。その名の通り、xがリストlのメンバーなのか否か調べる関数。
んで、これもLispの宿題にする、ってのは割にお馴染みなんですね。再帰の例題としては極めて良く出来てる。
(define (my-member x l)
(cond
((null? l) #f)
((eq? x (car l)) l)
(else(my-member x (cdr l)))))
ほっとんど上のcont?と同じ。違うのは見つかった時、リストそのものを返しちゃう辺りかな。
> (my-member 'a '(a b c))
'(a b c)
> (my-member 'b '(a b c))
'(b c)
>
こっちの方が「末尾再帰での書き換え」っつーか再束縛がどうなってんだか分かりやすいと思う。何故なら書き換わったリストそのものが返されちゃってるから、ですね。
なお、Lispの場合、結構な確率で、失敗した場合は偽(#f)を返すけど、成功した場合は残りのデータを丸ごと返すケースが多いです(笑)。
一つは、偽は唯一無二のデータ型になるけれど、他は全部真だから、と言う理由。
もう一つは、真だけ返してデータを捨てちゃうのが勿体無い、と言う考え方。「残りのデータそのもの」が真ならば、それをそのまま使って何か出来ないか、って考えるのがLisperなのです。そうすれば「もっと短く」プログラムが書けるかもしんない、と。
割にLisper自体もプログラムを短く仕上げる事にアツくなるのです。
あ、これは分かりやすいな。再帰部分に関数を置いて、1つ目に進める処理を入れて2つ目をカウンターにしてるって事・・だよね？
ですね。
ちなみに、そういうカウンターみたいな変数をアキュムレータ(累積器)と呼びます。
元々はCPUの累積器から転用してきた用語ですが、数同士の加算結果を保持するだけじゃなくって、リスト同士の加算結果も保持したりします。
なお、ここで挙げられてる関数lenも、ANSI Common LispやScheme等の組み込み関数、lengthの再実装です。
ここ最重要です。ここで語られてるのはソフトウェアの仕組みであり、その一般論です。インタプリタだけの話じゃない。
そう、実はゲームまでもが基本この範疇であり、世の中のプログラマでもこれを知ってる人と知らない人で二分されています。マジです。
言い換えると、ゲームを書く時でもこれを意識出来る人とそうじゃない人がいます。そしてそうなるとオブジェクト指向かどうか、ってのは二の次です。
なんかお馴染みのInputからの変数に入れての判定パターン来たか～。けど、なんでCondで#tを返したら抜けられるんだ？明日調べよう！
いやいや、逆に考えましょう。
「Condで#tを返したら抜けられる」んじゃなくって「再帰呼び出しせんから」そこで終わってる、んです。
言い換えると、別に
(define (repl)
(let ((l (read)))
(cond
((eq? l 'exit) #f)
(else
(write (eval l))
(repl)))))
でも
(define (repl)
(let ((l (read)))
(cond
((eq? l 'exit) 'done)
(else
(write (eval l))
(repl)))))
でも
(define (repl)
(let ((l (read)))
(cond
((eq? l 'exit) 'くぱぁ)
(else
(write (eval l))
(repl)))))
でも何でもイイんです。
大事なのは「その時点で再帰呼び出しを止める事」なのです。
その代わりにオマケで豊富な解説。まずAの部分・・うーん、空のリストを用意すれば良いのでは？とボンヤリ思う
合ってるやん！けど（）で表現するのか・・気づかんかった。で、Cか・・consでcarを足してったらええんでないの？
うお！当たった！
もう既に半分Lisperになっとる・・・・・・(笑)。
なお、ここで定義されてる関数revもANSI Common LispやSchemeの組み込み関数でお馴染みのreverseです。
ね?Lispって「組み込み関数使って何か作る」よりも「組み込み関数をどうやってプログラミングしてるのか」解説してるケースが多いのよ(笑)。
そして、組み込み関数が「再帰の例題」としては物凄く良く出来てる、っつーか、再帰を使った人類の叡智が全部入ってるのね(特にANSI Common Lisp)。
要するに、コンピュータサイエンスに於ける「再帰の博物館」状態になってるのです。
更にオマケの解説・・・あ、これだ！ネットの他のページで見たリストの結合の問題。第1引数の最後に入ってる空リストを第2引数と置き換える・・？どういうこっちゃ・・・Consは第2引数の頭に第1引数をつなげるんじゃなかったか・・ああ、時間がない。後は色々と試してみるぜ
appendね。
ちなみにね。
- 再帰よりも末尾再帰の方が簡単だ(Pythonでwhile True:〜が書けるなら)
- いまやreverseが使える
この二点さえ把握しとけば末尾再帰のappendが書けて、そっちの方がラクなのです。
リリカル☆LispおよびANSI Common Lisp風なら
(define (app x y)
(appi (reverse x) y))
(define (appi x y)
(if (null? x)
y(appi (cdr x) (cons (car x) y))))
なんでも再帰、川合史朗風なら
(define (app x y)
(define (appi x y)
(if (null? x)
y
(appi (cdr x) (cons (car x) y))))
(appi (reverse x) y))
名前付きletなら
(define (app x y)
(let appi ((x (reverse x)) (y y))
(if (null? x)
y
(appi (cdr x) (cons (car x) y)))))
そう、結局、consする要素を取ってくる側のリストを最初にreverseで反転させておけば考え方としては一番簡単だ、と言う・・・・・・。
果たして末尾再帰が卑怯なのか、やっぱり反転関数reverseが掟破りなのか(笑)。
このScheme実行環境「DrRacket」でな！これこれ！こういうエディタ式のが欲しかったのだ！
ただ、正確にはRacketってScheme止めたんだわ(笑)。昔はScheme処理系だったんだけど(MzSchemeとかPLT Schemeって名前だった)、独自路線になってある程度互換性はあるんだけど、Schemeのこれまた方言になっちゃったのね。
Pascalに対してのDelphiになっちゃった(って意味分からんか・笑)。
いずれにせよ、Lispには俺様Lispが山ほどあるんだけど、Racketは「世界で一番ユーザー数が多いだろう俺様Lisp」になっちゃったのよ(笑)。
と言う辺りで今回はオシマイ。
