構造化プログラミング、と言うのは、プログラミング言語はたったの3要素(機能)さえあればプログラムが可能になる、と言う設計の事で、大方のプログラミング言語はこのシステムを採用している。
その3要素とは、
だ。
当然、これらは実はダイクストラが「発明」したわけじゃない。ALGOLもそう設計されてたしね。ただ、ダイクストラが「まとめて」「発信した」と言う事だ。
これら三つはプログラミング言語の「機能」として存在し、端的に言うと、プログラミング言語の「文」(Statement)と言うのはこれらを制御するようにデザインされている。
つまり、これらは「関数」とか「手続き」ではない。もうちょっと下部レイヤーの話で、この三つを組み合わせて「関数」なり「手続き」を作成するわけだ。
「プログラミングはややこしい」と思う人も多いだろうが、実は殆どのケースだと、プログラミングする、ってことは逐次実行と条件分岐と反復しか書かないんだ。重要な事なんでもう一度書く。逐次実行と条件分岐と反復しか書かないのがプログラミングなんだ。
自然言語と違って、極めて単純な事しか書いてない。3つしかやってないんだよ。
ちなみに、Lispだともっと要素数が少ない。Lispが提唱したプログラミングの「要素」とは
- 再帰をサポートしたサブルーチン
- 条件分岐
で、2つしかプログラミングに必要がない、と言ってる(※1)。二個しかない。結果二つの事しかやってないんだわ。にっこにっこにーだ。
Lispの神髄「にっこにっこにー」
「いや、いくらなんでも逐次実行は必要だろ。」って言う人もいるかもしんない。
ただ、元々Lispはどーやら逐次実行が無かったらしいんだな(※2)。皆が使えるようになった初めてのLisp、Lisp1.5以前の話だから詳細は分からんが。
逐次実行と言うのは、テキストファイルに書かれたプログラムの行を「上から下へと順番に実行していく」機能の事だ。そう聞けば「なるほど、そりゃ必要だ」って思うだろう。ところが、原則、最初のLispではその機能が欠けてたらしい。
そんなプログラミング言語なんてあり得るのか?と思うかもしれないけど、Schemeプログラマなんかはその方法を良く知ってるだろう。逐次実行が無くてもデータを連鎖して書けばいい。
Schemeなんかでは実際、
(((((...)))))
なんてスタイルで書かれるプログラムが多い。内側のS式が値を返せば外側のカッコがそれをキャプチャし、そしてそこも値を返し・・・と連鎖していく。
元々のLispだとSchemeのようなプログラミングスタイルだったようだ。明らかに今で言う関数型プログラミングだ。
一方、これがFortranなんかのプログラマには不評で、Lisp1.5辺りでは「逐次実行」が導入された。progと言うのがそれだ。
要するに、1960年前後のプログラマもScheme的なプログラミング手法が苦手だったわけだな。
以降、ANSI Common LispやEmacs Lispで良く見られる
()()()()()
と言うスタイル「でも」書けるようにLispの機能が拡張されたわけだ。
でも、実はこれは本質的な部分じゃない。Lispは基本的には「たった2つの機能」で何とかやれるように設計されていて、その「たった2つの機能」が「特殊形式」と呼ばれるLisp根幹の「機能」に含まれてるわけだ(※3)。
さて、しつこいようだかもう一度書いておく。
プログラミングってのは極論、二個か三個かの「構文」しか書いてないんだ。言い換えるとどんなデカイプログラムだろうと二個か三個の「機能」しか使ってない。
だってそれしかないんだもの(笑)。
他にやる事がないんだ。ある意味毎回毎回同じ事を書いている。自然言語で言うと「おはようございます」と「おやすみなさい」しか言ってないようなもんだ(笑)。違いがあるのはそれらに与える「デコレーション」だ、っつー事だ。
Lispなんかだと、個人的には、結局大まかにはdefineとifしか書いてないような気がする(笑)。いや、ホントにそんな気分なんだって(笑)。あとは些事なんだ。毎回毎回ifとdefineばっか書いている。
さて、とは言ってもそれらは「プログラミングの基礎」ではあるんだけど、当然それだけだとプログラムにはならない。つまり、一つのプログラミング言語は「基本のシステム」として関数なり演算子を提供しないとならない。じゃないと何も出来ないから、だ。
んで、「何をユーザーに基本として提供するか」と言うのはぶっちゃけ、言語設計者の好みだ。例えば四則演算を提供する、ってのもそういう事だ。逆に言うと基本機能として四則演算を提供しない、と言う設計も十分あり得るんだよ。
嘘だと思う?足し算も引き算も無いプログラミング言語があり得る、とか。いや、理論的にはあるんだ。っつーか、Lispがそもそもそうだった。
魔法言語リリカル☆Lispの最終問題、団子数、ってのは冗談じゃないんだよ。四則演算以前にオリジナルの(論文上の)Lispにはそもそも数値さえ無い。
このような素っ頓狂な言語デザインもあり得るんだ。
ただし、あまりにも突拍子がねぇと効率の問題なんかが出てくる。非効率な言語を使うのもツライからね。
そう言ったわけで、言語デザイナーは何を根幹のデータ及び演算子/関数として提供するか、と言うのを結構慎重に考えるだろう。そしてかなりの部分は効率性を重視した低レベル(CPUとメモリで直接行うような範疇)の機能の翻訳となる。
あるいは、「ユーザーがプログラムするには難しい」関数なんかも言語側が提供しないといけない。
例えば、Schemeのcall/ccは汎用的かつ難しい機能だが、この関数に関してなるたけ簡易な説明を頑張ろう、ってやってるサイトもある。例えば「call/ccはフツーの関数」だと言う。しかし結論から言うとやっぱこの関数はフツーじゃない、んだ。
と言うのも、フツー、ユーザーはこの関数を作る事が出来ない。これはインタプリタなりコンパイラが提供しないと使えない関数だ。例えばcall/ccが無いPythonでcall/ccをプログラムするのは不可能だ。何故なら環境をキャプチャする手段をユーザー側が組み立てる事が出来ないから。
よって、call/ccはインタプリタ/コンパイラ自体に埋め込ま/組み込まれている根源的な関数じゃないとならない。Schemeではこのテの「ユーザーがプログラミングするのが不可能な関数」にcar、cdr、cons、eq?、pair?等がある(※4)。
さて、低レベルな根幹として色んな関数なり手続きなりを提供するとして。それらだけではプログラミングはツライ事になる。従って低レベルな関数なり手続きを随時組み合わせた、いわば「標準ライブラリ」と言うものをプログラミング言語は提供するのが大方のパターンとなる。
しかし、実際にプログラミングを行うにあたっては、「標準ライブラリ」でも間に合わなくなるだろう。
結果、各ユーザーが独自の「ユーティリティ」を作っていかないとプログラミングはいつまで経っても「面倒臭い」範疇に留まるわけだ。
そして、言語の良し悪しは、ある意味、
「如何にユーザーがラクにユーティリティを作成可能か」
が決める、と言う事になる。
この「ユーティリティ作成」に於いて、絶大な力を発揮するのが高階関数と言う機能だ。高階関数とは「関数を引数として取る機能」あるいは「関数を返す機能」を持った関数の事だが、これがあるとないとではユーティリティ作成の難易度がメチャクチャ変わる。
Lispは登場時点から「ユーティリティが作りやすい」言語だった。他の言語でも「出来ない」たぁ言わないが、高階関数を簡単に扱えて、しかも動的型付け言語であるLispよりも「ユーティリティが作りやすい」プログラミング言語は長い間存在しなかったんだ。
高階関数が扱える、と言う事は何らかの関数の計算の「心臓部」を決定する事を後回しに出来る、って事だ。それが抽象性を高め汎用性を押し上げる。
ところで、Lispは元々抽象性が高いが、それでもインタプリタ「埋め込み」の関数は低レベルではある。そして低レベルな機能の方が汎用性が高い、ってのは割にあり得る話ではあるんだよな。
これがある意味、C言語脳の妄言の根拠になっている。低レベルな方が色んな動作を直接記述できるから汎用性が高い。なるほど、でも反面全部それで書くのはメンド臭い。
今までの話の要点は、インタプリタ埋め込みの基本機能 -> 標準ライブラリ -> ユーティリティと話が繋がってきたが、これは下位レベル -> 抽象度が高いレベル、と言う流れではあるんだけど、実は「汎用性」と言う意味で言うとだんだん落ちてきている、と言う事。ユーティリティは汎用性が求められるんだけど、一方、言語組み込みの標準ライブラリよか汎用性は落ちるだろう事。ただし、特定の問題に於いては使いやすいと言うのがユーティリティの特徴だと言えるだろう。
要するに、ユーティリティとは汎用性が高いユーザー独自のライブラリなんだけど、言語組み込みの関数群よりは汎用性が落ちる、と。その汎用性と使い勝手の良さのバランスが丁度いい辺りに座するのが「良いユーティリティ」だと言う事が言えると思う。
ただ、ここで「バランス」とか言われても困るだろう。なんせ具体的にこうだ、と言う理論があるわけでもないし、手がかりなんてあるのや否や。
そこで、ここではある種、理論的な「流れ」としてSchemeを例として「ライブラリの実装の流れ」を整理して見せてみようと思う。
これは実際に「こうやって実装されてますよ」と言う意味じゃない。あくまで「理論上の流れ」だ。そしてこういう「流れ」があれば、この「流れの先」に自分が作るべきユーティリティライブラリの存在がおぼろげながら見えるんじゃないか、と言う話だ。
では始めよう。
まずは繰り返すが、Lispの基礎、と言うのは次の2つ、だと言う事だ。
- 再帰をサポートするサブルーチン
- 条件分岐
そしてこの他にインタプリタに埋め込まれた基本の関数(及び特殊形式)群がある。
実際はこの2つは分けようがない。何故なら再帰が反復を表す以上、条件分岐が無ければ無限ループに陥ってしまう。
従って、Lispでは再帰と条件分岐は、関数(つまりサブルーチン)定義上、必ず一緒に使わざるを得ない。
これは異常に見えるが、一方、機械語/アセンブリ言語では反復と条件分岐はぶっちゃけ同じだ。両者ともジャンプ、と言う機能なだけで、ダイクストラが言う「構造化プログラミング」と言うのはジャンプの意味を2つに分けたわけだが、Lispは分けなかった、と言うそれだけの話だ。Lispの方がむしろ機械語/アセンブリ言語に準じていて、それをそのまま抽象化した、と捉える事が出来る。
Schemeでは次いで、形式的に「末尾再帰」と言うスタイルで書けばそのまま機械語/アセンブリ言語レベルでのジャンプ構文にそのまま変換する(※5)。
そして基本的には「末尾再帰」と言うのはフツーの手続き型言語で言うwhileと同じだ、ってのは何度か指摘した。言わばwhileは末尾再帰の構文糖衣(Syntactic Sugar)だ。
しかし、Schemeでは、whileを実装して提供するより、名前付きletと言う構文を用意する事を選んだ。ここで抽象レベルが一段上がる。フツーの再帰ではなく「末尾再帰」と言う特殊な再帰をベースにした構文が生まれた、と言う事だ。一般の再帰より汎用性は落ちるが、末尾再帰を書く事自体はラクになる、と言う事だ(※6)。
さて、末尾再帰だが、大まかに言うと二種類ある。一つは計数反復、と言われるスタイル。カウンタを用意して与えられた数値を頼りに再帰を行う・・・C言語なんかで良く見られる形式の「反復」のスタイルだ。
もう一つが、長い間Lisp特有だったcdr再帰、と言われるスタイルだ。与えられたリストのcdrの長さを利用して再帰を行い、そのリストそのものを操作する。
基本的にはこの2つの末尾再帰が根幹となる(※7)。
また、cdr再帰はリスト再帰、と言われる再帰の一つだが、リスト再帰自体は必ずしも末尾再帰とは限らない。リストのcar部とcdr部を同時に再帰対象にするcar+cdr再帰等もあり、これは末尾再帰化出来ない(※8)。
さて、これら再帰の「パターン」の中で、末尾再帰がSchemeでは一番使われるので、名前付きletと言う構文が用意されている、ってのは既に見た通りだ。
そしてお題のシンプルさ、と言う意味だと計数反復は原則、これ以上の抽象化は行えない(※9)。
残るはcdr再帰だ。Lispに於いてcdr再帰こそがホント頻出で、計数反復より多いくらいだ。
何故なら、例えばC言語のような力の弱い言語だと、配列を舐める際でさえ、要素番号に頼らざるを得ないので計数反復を行わないとならない。一方、cdr再帰はリストの要素番号なぞに頼らない再帰の為、必然的に計数反復の出現率は極端に落ちる。
cdr再帰が頻出だ、と言う事は抽象レベルを一段上げる事が出来る。つまり、汎用性を若干犠牲にしつつ、より短く簡単に書ける「関数」を提供しよう、と言う話だ。
ここで基本となる関数をどうすんのか、と言うのは色々と考えられるが、ここではSchemeの仕様に含まれないfoldを基礎として考えよう。なんつったって、高階関数の中では最強と言っていいくらいの汎用性があるから、だ。
教科書的にはfoldは次のように定義可能だ。
これでもfoldは強力だが、これから生やしていく関数群の基礎としてはまだまだ非力だ。
1つ目としては可変長引数が取れない。
2つ目としては仮に可変長引数としてリストを取ったとしても、それらリストの長さがバラバラだった時にどうすんのか、と言う問題がある。Racketのfoldlだと受け取るリストの長さが揃ってないとエラーになるが、本来ならそれは望ましくないんだ。リストのどれかが消費され終わった時、演算が終わるようにしたい。
高階関数で高階関数を書く場合、抽象度が高いお陰で簡単に仕事を終える事が出来るが、一方、「基礎機能で」ベースとなる高階関数をマジメに書こう、とすればこれがなかなか大変になる。そして例えば今後mapを作る事を考えてる以上、今ここでmapを使うわけにはいかないだろう。
大まかに言うと、可変長引数であるclist2が空リストか否か、で場合分けしてる。空リストだった場合は、「教科書的なfoldの実装」でO.K.だ。
問題は空リストじゃない場合、だ。その時、clist1をclist2にconsして、リストを要素とした一つのリストにしてしまうのがポイントだ。
そのリストをちょっとした処理(%cars+cdrs+)するのだが、その説明は後へ回す。
いずれにせよ、clist1をclist2へconsする事によって、可変長引数版のfoldは「リストを要素とした一つのリスト」を引数とする関数へと変化する。形式的にはclist2が空リストだった場合と同じような計算をすればいい、って事になる。その部分が(apply kons `(,@(car lists) ,ans))だと言う事だ。
問題はここ、だ。
例えば'(a b c)と'(1 2 3 4 5)と言う2つのリストが与えられた場合、konsはknilも対象として含んだ3引数関数じゃないとならないが、それぞれのリストの要素の処理の順序はaと1、bと2、cと3となり、そこで処理を打ち切る。
つまり、実際に受け取るリストの構造としては、'((a 1) (b 2) (c 3))でなくてはならない、と言う事だ。フツーならmapを使えばイイような場面だが、mapが使えない、と言う縛りならどうなるのか、が議題だ。
そして、ここでmapを使ったように変換する関数が%cars+cdrs+だ。なお、%が接頭になってる関数は裏方で表面的には使わんぞ、と言う事を意図してる。
関数%cars+cdrs+はまた再帰を使って次のように書く。
関数%cars+cdrs+は関数%cars+cdrsを使って書く。
%cars+cdrsは「リストのリスト」を受け取った時、各リストのcar部分とcdr部分をまとめたものを多値として返す。
例えば、
のように、要素のcar部分だけをまとめ、残ったcdr部分もリストとしてまとめてしまう。
これを利用して、どれかが空リストにならない限り、再帰的に同じ要素番号の要素を一気にまとめてしまうのが%cars+cdrs+だ。
実行結果は確かに可変長引数版のfoldが欲しいリストになってるだろう。またリストの長さは、短い方のリストに合わせて残り('(1 2 3 4 5)の4と5)は省かれている。
この計算を行うのが%anynull?で論理演算を使って再帰的に定義される。
条件は
- 受け取ったリスト(lst)が空リストじゃない事。かつ
- (car lst)が空じゃないか、あるいは(cdr lst)が%anynull?を満たす事。
これにより、リストの要素リストのどれかが空だった場合、即刻#tを返す事となり、結果、%cars+cdrs+は、そのケースの時に速攻計算を打ち止め、アキュムレータ(acc: 累積器)を返すわけだ。
これで基礎となるfoldの実装は終わりだ。
なお、foldの第一引数のデータ型が関数かどうか確かめて、関数じゃない場合、Racket組み込みのraise-argument-errorを使って例外を投げるようにしている。
なお、一見使いづらいfoldは、それより低レベルの名前付きletに比べると守備範囲は劣るが、それでも、いつも言ってる通り汎用性で言うと群を抜いてる。
foldを入手しただけで、Schemeの仕様の一部分、あるいは基礎的なユーティリティをすぐさま作る事が可能だ。
例えばこれを利用したライブラリ関数/ユーティリティには次のようなモノが考えられる。
例えばリストの長さを調べるlengthと言う関数は、基礎関数だと思われてるが、実際はfoldで作る事が出来る。
関数sumは基本的にはPythonで言うsum関数と同じで、リストを引数として取り、その総和を返す。
関数productはsumの掛け算版だ。階乗を計算する際にも使う事が出来る基礎を提供する。
そして、foldの有用性で良く例に挙げられるのがリストを反転させる関数、reverseだ。こういう基礎関数も「基礎の基礎」としてfoldを置けば、それで記述する事が出来る。確かにfoldの汎用性を実感出来るだろう。
さて、ここでPythonで言うrangeを作ってみよう。
rangeは一見、計数反復の代表格のように思えるが、実はfoldでも作る事が可能だ。
若干病的な実装にならざるを得ないが、計数反復でも場合によってはfoldで実装出来る、と言う例示にはなるだろう。
関数rangeはcase-lambdaを用いてオプショナル引数の挙動を制御する。
基本となる3引数版のポイントはmake-listを使ってstepを要素としたリストを生成する事だ。初期値startを含むリストをknilとしてfoldを呼び出す。あとは粛々と(car knil)に対して加算を行い、knilに結果をconsして行くのが基本だ。結果、knilは3引数rangeが求める結果が反転して収まり、それをreverseして返す。
あとは、2引数版と1引数版から3引数版を呼び出すだけ、だが、それぞれ、startがstopよりも大きい場合とstopが0だった場合、空リストを返すように調整しないとならない。この辺はハックとなる。
次にfold-rightを作ろう。
実は教科書的な意味でもfold-rightはfoldから作る事が出来る。現時点reverseがあるんで、引数のリストをreverseして与えれば「リストを右から走査する」fold-rightの要件を満たす事が出来るわけだ。
一方これにも二点難点がある。
- 可変長引数ではない。
- リストを「右から走査する」とは言っても長さが違うリストに対してはどう解釈するのか?
1.はfoldの時にも出てきた問題だが、2.はどうか。
例えば与えるリストが'(a b c)と'(1 2 3 4 5)だった場合を考えよう。逆順のリストにする、と言った場合、'(c b a)はすぐ答えになるが、'(1 2 3 4 5)を「長さを'(a b c)に揃えつつ逆順」とはどう言った意味になるんだろうか。それは'(5 4 3)なのかあるいは'(3 2 1)になるべきなのか。
これ、理論的な根拠ではどっちなのか、と言うのは見つからなかった。ただ、SRFI-1の実装なんか見ると、求められるリストは'(3 2 1)と言う事になるようだ。つまり、余計な部分を落としてから逆順にする、と言うのが求められる。
とりあえず「余計なトコを落とす」と言う事を考えよう。foldで利用する為に%cars+cdrs+は次のような変換を行っていた。
しかしこれはfold-rightで求める引数じゃない。欲しい引数は'((a b c) (1 2 3))なんだが、実は%cars+cdrs+を二回適用するとそのカタチに落ち着く。
従って次のような補助関数を定義しておく。
次に、上の例だと'((a b c) (1 2 3))の各要素リスト全部をひっくり返したい。
通常のLispプログラミングだとmapでreverseさせる辺りだが、現時点mapをまだ作ってない。
従って、またもやfoldを使って次のような補助関数を作る。
これでやっとfold-rightが書ける。
これもclist2が空リストかどうかで動作が変わり、空リストだったら教科書通りのfold-rightでいい。そうじゃなければ引数リストを操作した後、カッコを外すようにして、結果foldをapplyすれば一丁上がり、だ。
さて、軽いジャブとしていくつかfold-rightを基本とするライブラリ/ユーティリティを見てみよう。
まずはこれもSchemeで提供されている基本的な関数で、Lisp初心者による再帰の練習の最初の山場となるappend。ここでは若干トリッキーな実装となってるが、fold-rightを二重掛けする事によって可変長引数のappendが実現出来る。
関数list-copyは与えられたリストの要素をコピーした新しいリストを作って返す。
ユーティリティfilterは与えられたリストの要素で、条件を満たさなかったモノをフィルタリングしたリストを返す。このユーティリティも単純にはfold-rightを利用して書くことが出来る、言わばfold-rightの子だ。
removeは逆に、条件を満たした要素を排除したリストを返す。言わばfilterとは相互補完的な関数だ。
これは直接的にfold-rightでは書かないが、filterを利用してる以上、fold-rightの孫のようなものだ。
ここでやっと、高階関数の代表格であるmapを作る。mapもfold-rightから作る事が出来る。
教科書的なリスト引数を一つしか取らないmapは次のように定義可能だ。
当然、ここでは可変長引数としてリストを取るmapを作成せねばならない。
が、最初のfoldに比べるとかなりラクになっている。と言うのも、関数のレイヤーの層が増えてきてて、抽象度のレベルが高くなってきてるから、だ。
また、テクニック的にも既に使ったテクニックを使うだけ、なんで、あまり悩まずに書けるだろう。
テストしてみよう。
ここでちと寄り道して、mapから2つのユーティリティを作ってみよう。
Pythonのユーティリティであるenumerate。cdr再帰を利用してリストの要素に要素番号を付加する関数だ。これはmapとrangeの合わせ技で作る事が出来る。
もう一つもPythonのユーティリティとして有名なzipだ。これは複数のリストを引数に取り、同じ要素番号同士の要素を組み合わせてリストにしたもののリストを返す。
なお、気づいた人は気づいただろうが、foldを作る為に作った補助関数%cars+cdrs+は、表現は違うがやってる事は殆どzipと同じだ。
言い換えると、zipがあればfoldはもっと簡単に作れた筈なんだが、敢えてfoldを使って一方、fold -> fold-right -> mapと来てやっとzipが出来ている。まるで、エロに目覚めたクソガキが国語辞典を入手した際、"セックス"を調べたら"性交の事"と書いてて、"性交"を調べたら"セックスの事"って書いてて悔し涙を流す事に似ている(笑・※10)。
いずれにせよ、ここでは「理論的な繋がり」を見せる為に敢えて一本のフローをハッキリさせて関数を書いてきているが、理論だけではこのテのメタ循環が起こる事があり得る。
従って、実際の言語仕様の設計をする際にはメタ循環が起こらないように慎重に「基本となる関数」を選定してる、と言う事だ。
なお、zip自体はSRFI-1にて提供されている。
fold-rightの応用に戻ろう。今度はmemberを実装してみる。
実はこの実装はかなり無理クリだ。ここでは理論的な流れとしてはmemberをfold-rightの応用として敢えて紹介する事を選んだが、実際の実装がこうなってる、と主張はしていない。
あくまで「理屈ではこうなる」と言う事だ。
まず、基本的な構造としては、与えられたobjとlstの先頭が一致した際に、call/ccでknilを持って脱出してる。つまり、fold-rightの計算を途中で止める。
この方針の難点は、fold-rightの性質上、lstに一個もobjと一致する要素が含まれない場合、fold-rightではknilがlstそのものになり、結果lstが返ってしまう。
しかし「発見されなかった」場合は#fを返すべきで、これは望んだ結果じゃないだろう。
一方、与えられたlstの先頭がobjと即座に一致した場合はどうなるんだろう?実はこのケースでもlstが返ってくる。
つまり、「与えられたlstの先頭がobjの場合」も「objがlstに含まれなかった場合」も両方ともlstが返ってきて見分けが付かないんだ。
この不具合を避ける為に色々と小手先のテクニック(ハック)を導入してるわけだ。
さて、memberが高階関数になった、って事はassocもmemberを利用して書けるようになった、と言う事だ。これは大きい。事実上、cdr再帰を利用したかなりの関数がmemberで書けると言う事を意味する。
ここでfoldから始まった旅が終了する。
今まで書いてきた事はあくまで「理論上の流れ」なんだけど、自分でユーティリティを作る際には「この流れに乗っかる」と言うのは悪くないんじゃないか、と思っている。
最後に、今まで作ってきた関数群を有向グラフとして表示しておこう。流れを掴むのがラクになるんじゃないか。
※1: これは「構造化プログラミング」の文脈に合わせた言い方であり、実際はLispには他に重要な機能(構文)である「何もすんな」がある・・・quoteだ。
※2: 逐次実行として機能が「独立してなかった」と言った方が正しい。
オリジナルのLispではcondが条件分岐の基本で、かつ、condは逐次実行を「含んで」いた(暗黙のprognってヤツだ)。そしてそれは現在も受け継がれている。
なお、Lisp発明者のマッカーシーは、「(逐次実行を含んだ)condの設計は失敗だった」と述懐してたらしい。
現在のLispの殆どは、condではなく、「逐次実行を含まない」ifを条件分岐の基本としてる。
ちなみに、「プログラミングが出来ない」プログラミング初心者が一番何に躓いてるのか、と言うと、僕が観察する限り、それは条件分岐でも反復でもなく「逐次処理」だ。根本的に、「書かれた順番通りに動作する」と言うのを分かってないヤツがあまりにも多いんだ。
「そんな簡単なトコで躓く?」とプログラミング経験者は思うだろうが、事実だ。彼らは「書かれた順番通りに動作する」と言う事が分かっていない。ある意味教育の不備ではある。「簡単な」と思い込んでるが故に、とんでもないトコで躓いてる、ってのが想像出来ないんだろう。
そういうタイプが往年より増えてるかもしんない。シングルタスクのOSの世界に住んでたら「全ては書かれた順番通りに動作する」のが当たり前だが、マルチタスクなOSの現代だと、「あらゆるプログラムを同時に走らせられる」世界なんで、その辺ピンと来ない可能性の方が高いんだ。
そう、彼らは「書かれた順番通りに動作する」より、直感的に「順序に関係なく書かれたモノは全て同時に動作する」ような勘違いをしている。
※3: 厳密には、「特殊形式(Special Operator)」と言う用語はANSI Common Lispの用語で、ANSI Common Lispのインタプリタ及びコンパイラで、通常言語で言う「文」の役割を果たすオペレータ群(いわゆる基礎構文)を指す。ANSI Common Lispでは、これを利用して作った「構文」の役割を果たしてるオペレータ群を「マクロ」として分けている。
しかも、例えば理論的には、束縛構文letはラムダ式を用いてマクロとして定義可能だが、ANSI Common Lispではletは基礎構文、つまり特殊形式として定義されている。恐らくコンパイル時の効率を考慮しての事だろう。
一方、Schemeの場合、標準ライブラリとしては基礎構文だろうが、それを組み合わせて作った構文類だろうが、構文(syntax)として定義されていて、どれがどれを基本として定義されてるか、は不明となっている。
言い換えるとSchemeの場合は、仕様上構文、として定義されてるものはインタプリタ自体に埋め込まれてる「基本構文」として全部実装するのも自由だ、と言う事になる。
このように、仕様は、効率性から考えると必ずしも完全に「理論」を反映してるわけではない。
※4: このテの、インタプリタあるいはコンパイラの実装上、「埋め込まなければならない真に基本的な関数/手続き群」の類をプリミティブ(primitive)と呼んだりする。
※5: 実際は、Scheme処理系では直接マシン語に変換する処理系は少なく、むしろJavaやPythonのような仮想マシンを備えていて、そこで使われてる機械語/アセンブリ言語へと変換する処理系が多い。
また、末尾再帰でも直接ジャンプ構文に変換出来ない場合もある。
※6: 実際は名前付きletでもフツーの再帰は出来なくはない。
※7: この辺の再帰スタイルの違いは、基本的には結局、対象とするデータが何か、と言う辺りに依り、言語がどんなデータ型を用意してるのか、で発生する。
結局、例えばSchemeに於いて、vector相手の再帰だとか、string相手の再帰だとか、データ型によって色々と考えられるが、Lispは元々のList Processorの名の通り、それらの「新しく加えられたデータ型」よりリストを基礎として作られたプログラミング言語なんで、ここでは「その他のデータ型」は考慮しない。
※8: car+cdr再帰は木構造相手に良く出てくる再帰で、代表的なモノにflattenがある。
また、継続受け渡し方式(CPS)を用いて形式的に末尾再帰化は可能だが、それらは最適化には至らない。
※9: ANSI Common Lispのdotimesと言うマクロを借りてくる事は可能だ。
ただし、Schemeの歴史の中で、ANSI Common Lispのdotimesを何が何でも借りてこないと・・・と言った雰囲気になった事はないだろう。基本的にはSchemerは再帰構文だけで計数反復は十分だ、と考えている。
同時に、実はANSI Common Lispの「反復構文」は再帰を基本としていない。どっちかっつーと、フツーの言語並の血なまぐさい、ホンモノの「反復(つまりジャンプ)」をより重視している。
※10: ちなみに、某英英辞書には
connecting bodies to produce children
等と説明されていて、海外の辞書編纂者の方が思い切りが良い(笑)。
