星田さんの記事に対するコメント。
とりあえずSRFIのReduceの定義を見てみますか・・Ridentity？ 用例からするとBaseとか初期値？ あとCheck-argってのは引数がちゃんとプロシージャかチェックするものかな？
肝心の本体はFoldやん・・
うん。
ちょっと解説していきます。
まず、後の方に疑問として書かれてるんだけど、まずは、
CametanさんのコメントだとReduceってFoldLと実質同じなのかな？
一般的には、ザックリ言うと同じです。異名同関数、だって考えて基本的には良い。
ここからはSRFI-1に関しての話。
SRFI-1のreduceにはこう書いてある。
つまり、こういう事になる。
> (reduce + 0 '(1 2 3 4 5))
15 ;; これは良い
> (reduce cons '() '(1 2 3 4 5))
'(5 4 3 2 . 1) ;; 結果がfoldと違う(望ましい結果になっていない)> (reduce (lambda (x count) (if (symbol? x) (+ count 1) count)) 0 '(a b c d e 1 2 3 4 5)) ;; エラーが起きる
. . +: contract violation
expected: number?
given: 'a> (reduce (lambda (s max-len) (max max-len (string-length s))) 0 '("hoge" "fuga" "piyo" "foo" "bar" "baz")) ;; エラーが起きる
. . max: contract violation
expected: real?
given: "hoge"
>
つまり、SRFI-1のreduceはある種計算負荷を避ける為、だけに存在する関数です。
こう書いてるでしょ?
reduce が使用される場面としては、 手続き f のコストが高く、 fold が list の先頭要素と単位元に対して f を適用して同じ値を返すという冗長性を回避したい場合である。
んで、
ridentity は手続き f の右単位元 (right identity) である。
とかクソメンドくせぇ事が書いてある。
単純に言うと、例えば
> (reduce + 0 '(1 2 3 4 5))
15
で与えられたリストの先頭を見てみると、要するに計算としては
0 + 1 = 1 + 0
が同等だよ、ってのが成り立ってる。だからreduceを使用出来る。
一方、
> (reduce cons '() '(1 2 3 4 5))
'(5 4 3 2 . 1)
の場合、
(cons '() 1) ≠ (cons 1 '())
でしょ?等価にならない。
こういう場合はSRFI-1のreduceは「使えない」んだ。
だからSRFI-1のreduceの場合、「使用するケース」に制限がある。要するにこれはANSI Common Lispのreduceとは別物だね。
あと、ちなみに、identity関数ってのがあって、これは受け取った引数をそのまま返す関数の事。
Racketで言うと
(define (identity x)
x)
ってのが定義。一見バカバカしい関数に見えるんだけど、Racketでビルトインで定義されてるし、ANSI Common Lispにもある。日本語だと「恒等関数」とか訳されるのかしらん。バカバカしく見えるけど、たまには役に立ちます。
と言う余談を挟んでおいて、結果、RidentityのRってのは「右側の」って事ですね。上であげてる右単位元が成り立つのか、って事なんだけど、プログラミング上は星田さんが言ってる通り初期値になる。まぁ、数学的に言うと単位元、って事だ(結局、与えられたリストが空リストの場合、計算負荷を避ける為にfoldを呼び出すのを止めて、そのまま初期値を返す、と言う事)。
そしてcheck-argは星田さんが予想した通りのものです。ただし、そんな関数は標準Schemeにもないし、Racketにも存在しない(笑)。
っつーのもね。「参照実装」ってのは基本的に実装者向け情報なのよ。つまり、Schemeのインタプリタやコンパイラを作ってる人向けの情報で、結果、低レベル操作の部分ではcheck-argに相当する何かが既にあんだろ?って前提で書かれています。具体的にはevalとかapplyの実装でそれに類するモノがあるだろ、って言ってるわけですね。
だから各実装向けに汎用的に書いてる為、ユーザーが読むとサンドウィッチマンの富澤たけし状態になったりするわけよ(苦笑)。
じゃあFoldの定義は？と見ると・・ええ・・KonsってCons？ReceiveとかCarsとか％とか・・これは手に負えないｗ
KonsってのはSRFI-1の定義上の言い回しで、要するに手続きを表すprocでも関数を表すfuncでも構わない。要するに関数引数の事です。
そしてreceiveは、今で言うlet-valuesって考えていいかな。多値を受け取る機構、って考えて良い。
で、その頃のSchemeには多値、って機能があった。ただし、簡易に多値の返り値を受け取れる機構がなかったのよ(笑)。すごい使いづらくて、当時はlet-valuesが無かったんだ。
それで、「いくら多値があっても使いづらけりゃしょーがねぇだろ」ってぇんで、「Schemeにこんな仕様があったらいいな集」、つまりSRFI(※1)に「多値を受け取れる機構の仕様」として提案された文書がある。それがSRFI-8です。
このSRFI-8で提案されてる「多値を受け取る機構」がreceiveなんです。参照実装は以下の通り。
(define-syntax receive
(syntax-rules ()((receive formals expression body ...)(call-with-values (lambda () expression)(lambda formals body ...)))))
call-with-valuesってのがScheme/Racketでの「低レベルな」多値を受け取る機構の基本なんだけど、マクロを使ってreceiveと言う構文の形式を定義してそれをcall-with-valuesを使った方式に変換しています。
そして、今はlet-valuesがあるんで、receive自体は忘れて構いません(現行のlet-valuesはSRFI-11をベースにしてて、SRFI-8は受け入れられなかった、と言う事だ)。
それと%は気にせんでエエです。
忘れてるかもしれないけど、Lisp系語族の「命名に使える文字の種類」は他の言語の比じゃないです。だからANSI Common Lispなんかでも1+みたいな「他のプログラミング言語じゃ許されないような」関数名を付ける事が出来る。
単に、変数名で何かを強調したい、とか思った時、名前の先頭に%って打っても全然構いません。真似してやりたきゃやれば良い(笑)。
(ちなみに、参照実装を見ると、「ユーザーに直接触ってもらって欲しくない関数」の関数名の先頭を%としてる模様)
件の、多分ハマった場所は今風に書くとこんなカンジかな。
(let loop ((lists (cons lis1 lists)) (ans knil))
(let-values (((cars+ans cdrs) (%cars+cdrs+ lists ans)))
(if (null? cars+ans)
ans
(loop cdrs (apply kons cars+ans)))))
要するに「ユーザーに触って/使って欲しくない関数」である%cars+cdrs+は、まぁこれの定義自体も参照実装に書かれてるんだけど、結局「多値を返す」多値関数だ、と言う事。引数にlistsとansを2つ取って、返り値を2つ返す、と言う事。
それらを変数名cars+ansとcdrsで受け取って、本体部分はそれを利用したプログラムになってて、条件を満たさなければ再帰してる、と言う事。
そんなトコかな?
CametanさんのコメントだとReduceってFoldLと実質同じなのかな？（Reverseになるので）。結果を見比べるとRは）））））がまとまるConsでLは（（（（でまとまるConsって感じだったけど、定義を見ると再帰を起こす場所が違うんですね。
平たく言うと、受け取るリストを「左から処理」するのか「右から処理」するのか、ってのがLとRの違い、です。
(あるいは、リストをアタマから処理するのか、ケツから処理するのか、が違う)
- foldl -> 引数: + 0 '(1 2 3 4 5) -> 「左から」リストを処理していくので(((((0 + 1) + 2) + 3) + 4) + 5)になる
- foldr -> 引数: + 0 '(1 2 3 4 5) -> 「右から」リストを処理していくので(((((0 + 5) + 4) + 3) + 2) + 1)になる
つまり、
- foldl -> 引数: cons '() '(1 2 3 4 5) -> 「左から」リストを処理していくので(cons 5 (cons 4 (cons 3 (cons 2 (cons 1 '())))))になる -> '(5 4 3 2 1)と逆順になる。
- foldr -> 引数: cons '() '(1 2 3 4 5) -> 「右から」リストを処理していくので(cons 1 (cons 2 (cons 3 (cons 4 (cons 5 '())))))になる -> '(1 2 3 4 5)と元のリストのまんま。
となって、事実上、foldrは基本的には、
(define (foldr proc init lst)
(foldl proc init (reverse lst)))
と言う事です。
また、ANSI Common Lispだとreduceしかないのに、何故にScheme/RacketにはLとRの2つがあるのか、ANSI Common Lispでは「畳込みは左から、しか行えないのか」と言うとそうではなく、例によってANSI Common Lispは「総称指向」だからです。言い換えると「似たような効果の関数は全部一つにまとめちまえ」と言うのがANSI Common Lispの方針。
つまり、reduceでは「どっち側からリストを舐めていくか」と言うのをユーザーが指定出来て、左からだろうと右からだろうと、前からだろうと後ろからだろうと(こっちはイヤラシイなｦｲ・笑)、畳込みがかけられる、と言う事です。
敢えてfoldとreduceの差を言うと、「違うプロセスの関数はやっぱり違う関数であるべき」と言う思想と、「同じような手順を踏むなら一つの関数でいいじゃない」と言う思想の違い、かな。
なお、前回見た河北彩花の写真を3枚ひっつけたウィンドウを出すプログラムですが。
例えば前回よりちと大きな写真を使ってみる。ネットで拾ってきたコレね。
んで、例によって前回のようにRacketに読み込んでみて、*saika-image*として束縛します。
んで、あとは前回のコードと全く同じなんだけど。
前回、foldlを使ったコードはこんなカンジ。
;;; reduceを使った関数定義(河北彩花を複数置く関数)
(define (place-saikas saikas scene)
(foldl place-saika scene saikas))
んで出てくるウィンドウはこんなカンジだ。
画像が大きくなったから「重なってる」。当然手前にある写真ほど上のレイヤーってワケで、結局「畳込み」で最期に畳み込まれた画像が一番上に来てるわけね。
今度は、件のコードをfoldlからfoldrに改変してみる。
;;; reduceを使った関数定義(河北彩花を複数置く関数)
(define (place-saikas saikas scene)
(foldr place-saika scene saikas))
さて、これでウィンドウを表示させると、だ。
分かる?一番手前に来てる写真が変わってるでしょ?
つまり、foldlとfoldrでは「リスト処理の順番」が逆になってる、って事。
画像レイヤーを重ねる順番がfoldlとfoldrでは、結果真逆になってんのね。
SmallBasicなるものがあると知りました。へぇ〜WEBアプリとしてエディタが使えるらしいから甥っ子がもしもプログラミングに興味あるとか言い出したときには良いのかも？
面白そうですねぇ。
ただ、前にも書いたけど、現時点、「本物のBASIC」はISOあるいはJISで制定されてる「FullBASIC」しかないです。
んで、世界中でも、フリーの実装と言えば、日本で作られてる十進BASICしかないのじゃないかしらん。
手元で弄るのなら、是非とも十進BASICを弄ってみてください。そこのWebページは資料も豊富だし、掲示板に集まるユーザーもかなりフレンドリーな人たちですからね。それはそれで楽しめると思います。
なお、十進BASICはインタプリタじゃなくってコンパイラです。かつ、珍しくDelphiで書かれた処理系になっています。
十進BASIC エディタ。プログラム内容はここを参考にしている。
十進BASIC 実行ウィンドウ。
こういうのも見たので、複数の全然違うタイプの言語を使ってみるのも良いんだろうということで・・
うん、そうですね。アドバイスとしては基本的にエリック・レイモンドが書いてた事と同じだと思います(ただ、彼はやっぱオープンソース陣営っぽいバイアスがメチャクチャ酷い人ですが・・・・・・)。
まぁ、トレンドもありますしねぇ。今だと、個人的には、「C言語にマトモな入門書が一冊もない」と言う前提で、Cを学ぶのならRustを学んだ方がいいのかな、とかは思ってます。これはぶっちゃけ、僕個人は良くは知らない言語なんだけど(Linuxでのインストールがメンド臭そうだから)、尖った人達が「すげぇ!」って言ってるんで凄いんでしょう(笑)。日本じゃそうでもないんだけど、諸外国での人気は鰻登りのようです。GoogleのGo言語と登場時期は前後しますが、多分Goを学ぶならRustの方がエエんちゃうかなぁ・・・C言語代わりとしても。
つまり、Rustは「もはやゴチャゴチャして、仕様的にも何だか良く分からん事になってる」C言語に代わった「キレイな理想のC言語」を目指してる、っつーか・・・・・・そして存在目的は、C言語と同様の「ハードウェアを直に叩く」ような低レベル操作、です。抽象水準が最高位のLispと真逆の位置にある。
クラス抽象、ならまぁPythonで大丈夫かな。もっとこだわりたい、っつーのなら以前書いたEiffelでもやってみればいいだろうし。
ただし、オブジェクト指向の「理論」を見たい、ってぇのならLispで充分です。なんせ、Lispはオブジェクト指向の「開発」に関わってきてる。理論屋Lispの出番で、Lispでは「クロージャでオブジェクト指向を実装する」と言う事が出来る(※2)。特に元々、Schemeはその辺の理論的検証をする為に作られたプログラミング言語なんで、いわば「オブジェクト指向の理論」ってのはScheme畑の話なのね。
構文抽象、ってのは要するにLispのマクロの事です。
Prologは是非とも一回触ってみるべきかなぁ。ホント「異質な言語」なんで。もっとも「実用Common Lisp」だとProlog実装しちまうんで(笑)、それで充分かもしれない(※3)。
並列抽象は良く分からんので、発言は差し控えておきます。
いずれにせよ、理論的な話をすると、Lispだけでかなり多くの範疇をカバー出来るとは思う。足りないのはRustくらいか?PythonだとLisp経験を活かしつつ、クラス抽象に突っ込むくらい。あとはマジメにOOPを考えるのならEiffel、と。
Lisp、Rust、Python、Eiffel、Prologの5つが多分「一回はやってみる価値がある」プログラミング言語じゃないかしらん。今は。
分からんけど。
※1: なお、日本語版Wikipediaには、SRFIが「Scheme公式仕様の一種」と勘違いしてるような記事が投稿されたりしてるが、当然そんな事はない。あくまで「仕様の要求集」であり、仕様策定のグループが決めてる事とは全く関係がない。
また、その性質上、「外部ライブラリ」でもないのだ。
あくまで、Scheme実装者が、選択上、「これは俺の実装に入れておこうか?」と言う程度のモノであり、結果、Scheme実装同士を移動する際のコードのポータビリティを保証するモノでもないのだ。
(例えばGaucheの場合、SRFI-22を「採用」してて、UNIX用のスクリプトを書く際に他の言語でも見られる定番型のスクリプト記述が可能だが、一方、RacketはPLT Scheme時代からSRFI-22を採用していなく、結果、GaucheのUNIXスクリプトをRacketに持ってこようとすると、ポータビリティとしては破綻する)
また、SRFIの定義から仕様に格上げになる場合も「あることはある」が、絶対ではないし、特定の機能「だけ」に絞られる事もあって、提案された各文書が「丸ごと」格上げになる、なんつー事もないのだ。
※2: または、「実用Common Lisp」(PAIP)の13章では、ANSI Common Lispを用いて「オブジェクト指向の機能を実装する」例示が成されていて、簡単な「継承」のシステムまで作り出している。
また、ポール・グレアムの「On Lisp」でも、ANSI Common Lispでの「オブジェクト指向の実装例」が紹介されており、このように、Lispに於いては「言語組み込みのベース機能として」オブジェクト指向が必要なのか否か、と言う議論を無駄なモノとしている。
つまり、「必要になったら」自分でLispの上に自作のオブジェクト指向のレイヤーを「付け足す事が出来る」のだ。
ただし、「それってメンドくない?」と言われればその通りである(笑)。
※3: Prologはかつての日本ではかなりの人気があって、専門書も比較的多く出版された。
従って「古本でProlog入門を安く買う」のは狙い目だとは言えるのだが・・・・・・。
問題はPrologで「何が標準なのか」良く分からん辺りだ。これら過去、技術書が出版されてた時代では標準が無かった模様で、結果処理系によって操作方法(と言うかビルトインの命令だな)が違ったりして全然関係ないところで引っかかる可能性が高い。
また、現時点でのPrologの「主流」の仕様なり実装が何なのか、全く情報が無い、と言う辺りも困ったモンである。
(一応、デファクトスタンダードと呼べる処理系はSWI-Prolog、と言われてるらしい)
なお、かつてのJIS(日本産業規格)ではキチンとPrologの仕様を制定してはいたが、言語の人気がなくなって重要度が下がったせいか、2012年に廃止されている。
また、素のEmacsにはPrologモードが用意されているが、一方、Spacemacsでは開発版はあるにせよ、Prologレイヤーは現時点では存在しない。
