見出し画像

Retro-gaming and so on

連想リストの話


これも大変良い事だと思っている。
最近では徐々にそうではなくなっているが、それでも日本人の「オープンソース」に対する抵抗は諸外国の人に比べると結構デカイ。
「自分のソースを晒し」て、下手だと批判される事を極度に畏れる国民性なんだ。
反面、毛唐の連中はあまりその辺気にせんらしい(※1)。
逆に、「他人がソースを勝手に改造して"より良くする"」事の方がメリットが大きい、と捉えるくらいだ(※2)。
ま、別に「どっちが文化的に上だ」とか言う気はない。
プログラミングはそもそも「大人数で行う」可能性が常にあり、逆に言うと、毛唐でも、アーティストが音楽制作やら絵画制作で「作成途中で大多数に晒して不特定多数がそれを編集可能にする」事はあり得ないわけで、そういう意味で言うと、日本人プログラマの多くは、個人で行うプログラミングを、どっちかっつーと「アート気分で」行ってる、って事だろう。
ただ、プログラミング学習時は、なるたけソースを晒して添削された方が「トク」だと言う事は確かにある。

さて、プログラミング言語で「何かを書く」場合、いつも言うけど短く書けたらそっちの方が正義の法則と言うのがある。まぁ、俺が勝手に名付けたんだがな(笑)。

一般に、書くべきプログラムの短さの秘訣、ってのは2つある。
1つはそのプログラミング言語に豊富なビルトインライブラリがあるケースだ。プログラミング言語Pythonがそれにあたる。
Pythonの場合、何か書け、とか、例えば宿題で出た時でも、自分で作るより検索で適したライブラリ関数が無いか、って探した方が結果早かったりする(※3)。そもそもユーティリティ指向だ、ってのがPythonの特徴だ。
最近ユーティリティユーティリティっつってるけど、ユーティリティは「コードをなるたけ短く書く事が出来る」道具集だ。当然短く書ければそっちが正義、の法則だと、ユーティリティが豊富なプログラミング言語の方が良い、って事になる。そしてそのトレードオフがどんなユーティリティを備えてるのか、と言う知識量、って事になる。
そしてユーティリティが少ないプログラミング言語の場合、自分でユーティリティを作っていってライブラリ化するしかない(※4)。
これは「プログラミングを始めたばっか」だと大して揃わない。当然だ。前にも書いたけど「プログラミングを始めたばっか」だとどんなツールが開発に役立つのか全く分からんから、だ。
しかし、色々プログラムを開発していくと、「自作ユーティリティ集」も大きくなっていくだろう。結果、色々経験していくと、自分自身がステップアップするだけではなく、自作ユーティリティライブラリが育っていって、どんどんプログラムの開発がラクになっていくわけだ。
いずれにせよ、「ユーティリティの量」と言うのがそのプログラムの「短さ」「簡潔さ」を支える1つの秘訣となる。
2つ目は便利構文の多さだ。この辺はLispとその他の言語では大きく方針が違う。
Pythonはフツーの言語での条件分岐なんかの量はむしろ減らした設計にしてる。その方が「初心者に優しい」からだ。それは「構文を減らした方が記憶への負担が少ない」と言う判断でもある。一方で、内包表記、と言う他の言語では見られない便利構文は増やしてる傾向がある。
そして、加えると、Pythonのような「フツーの」言語だと構文はライブラリにはならない。便利構文を追加するのは言語設計者の特権であり、いくらPythonユーザーがwhenunlessのような条件分岐の変種が欲しい、と思っても設計者が「必要ない」と判断すれば言語仕様に取り込まれる事はない。
一方、Lisp系言語では構文そのものもユーザーが作れる。それがマクロだ。結果、Lispではユーザーがマクロを駆使して「構文をライブラリとして追加出来る」自由がある。特にSchemeだと構文がANSI Common Lispに比べると比較的少ない設計なんで、構文も「ユーティリティ」としてユーザーがライブラリ作成する余地があるし、それも育てる事が可能となる。

まぁ、場合によってはLispコードよりPythonのコードの方が短く見える可能性があるが、それはPythonのユーティリティに拠る、と言う確率はかなり高い。
ただし、構文的なモノ(つまり言語としてのパワー)で見ると、ここで見た通り、Lisp系言語の圧勝だ。
他にはmap vs. リスト内包表記のような「同じような事を書くならどっちが短いか?」と言うような例もあるが、実はこれは関数と構文の比較なんで、一概には言えない。探せばLispでリスト内包表記を使えるようにするライブラリ(つまり、原理的に「構文を追加」する言語拡張ライブラリだ)もあるが、大方のLispプログラマは、mapを使う事だけ、に不満を覚える事はないようだ(※5)。

いずれにせよ、コードを短く書くには第1にユーティリティの存在、第2に便利構文の存在、が重要だ。
後者は通常(Lisp以外では)ユーザーはどうしようもねぇんで、第1のユーティリティの話を続けよう。
ユーティリティの理解を深めよう、と言う話だ。
特に、純なSchemeは仕様上、ユーティリティの数は少ない。
一方、「これを実装して提供しなきゃSchemeとして認めない」と要求するユーティリティの数々は、数は少ないけど研ぎ澄まされた、汎用性の高さを極めたモノ、として提供されている。
今回は連想リストの検索関数、assocの類の話だ。

まず、連想リストの形式を初歩から見直してみよう。
日本でSchemeを学ぶなら一番、と言って良いサイト、「紫藤のページ」から連想リストの項目を見てみよう。




まず、連想リストはキーと値が形作るリストを要素としたリストだ。キーと値1つの場合はドットペアを作る事が多いが、一方、それは必須じゃない。値が複数になってて、結果リストを中に内包していても構わない。非常に柔軟な形式なのが連想リストだ。
柔軟な」。ここ重要。
と言うのも、連想リストは、考えてみれば分かるがデータ型ではない。あくまでデータ形式なんだ。もうちょっと言うと単なるリストだ。形式をある程度整えただけ、の。


と言う事はどういう事だろうか?
Schemeでは公式にはassqassvassoc、と言う検索関数がある。
つまり、本質的な事を言うと、これらは連想リスト専用の検索関数ではない。むしろ単なるリストから特定のモノを探す機能がベースなんだ。
例えば次のようなリストを考える。

(define wc '(hi everybody to meet you))

通常は、例えばリストwchiyouを含むかどうか、は同じユーティリティである、memberの類を使って調べるだろう(※6)。


しかし、実はassocの類も使おうと思えば使えるんだ。


もちろん、返り値のデータ形式は違う。しかしながら、本質的には「探す」と言う仕様に関しては両者共結果を満たしてるのが分かるだろう。

なんでこの2つは同じような「探す」と言う仕様を満たしてるんだろうか。
平たく言うと、これらの関数定義が殆ど瓜二つ、だからだ。



殆ど同じだ、と言って良いだろう(※7)。
奇しくも、いささか常軌を逸したLispの「ライブラリ関数の再実装による学習」が役立つケースだ。そしていつか書いた通り、4つの基礎的再帰関数が書ければ、大体のケースに対応出来る、と言う実例だ。
要するにmemberが書ける人ならassocはすぐ書ける、って事だ。

さて、星田さんが書いた次の関数を見てみよう。


そう、ここまで来たら分かるだろう。
実はこの関数、memberあるいはassocの構造とほぼ同じなんだ。つまり、memberassoc再実装してる。
これは、ユーティリティとしてmemberまたはassocを使う局面なんだ。

しかし、itemlistが想定してるリストは構造体のリストだ。決して連想リストではない。
そしてmemberも値を探すのが基本的な機能であって、構造体の中身をチェックするようには書けない。
そこで次のようなトリックを使う。


こうすると、キーを(item-name x)とした一時的な連想リストが生成される(※8)。



これを利用する。
これとassocを使った関数return-structは次のように書ける。


これは望んだ動作になってる筈だ(※9)。


今回のテーマは「既存のユーティリティを使いこなそう」と言う事だが、Lisp学習の上での「ライブラリ関数の再実装をする」と言うおかしなプログラミング学習法がたまには役に立つ、と言う話でもある。
結局、Lispが備えてるライブラリ関数を再実装した経験がある、って事は汎用のユーティリティに付いても他の言語のユーザーより「遥かに熟知してる」と言う意味になる。
何か再帰を書いてて、「あれ、これどっかで見たパターンだぞ?」と思えば、それがユーティリティを使うタイミングだ。
絶対どっかで勉強した事がある、んだ。

※1: 逆に言うと、日本人でソースを晒す人たちは、全世界的に見ても「キレイな」コードを書く率が高く、元々スーパープログラマ的な人ばっか、って事だ。

※2: 2000年代後半辺りから「プログに代わるニューメディア」ってぇんで、一時期Wikiが持ち上げられてたが、「誰でも簡単に既存の文章を編集出来る」と言うシステムが日本人には合わず、結果下火になった。
例えばWikiで書かれている記事に修正が入った場合、編集者側が申し訳なく思うのか、「編集しました」とコメントを残す例が多く、結果、Web検索した側から言うと、記事本文より「編集しました」コメントの方が量が多かったりして(笑)、なんとも読みづらい記事に結果なってる、ってのも良く起きたくらいだ。
このように、元々日本人は、「ネット上での見知らぬ人との共同作業」と言うのをあまり好まない、っつーかヘタではあるわけだ。
なお、余談だけど、Wikiと言うのはWiki Wiki Webと呼ばれる「システム」の略称であって、結果、WikipediaをWikiと訳すのは間違いだ。
そもそも、Wikipedia、と言う呼称そのものが「Wikiを使った百科事典」から来てるので、WikipediaをWikiと訳すのはおかしな用法、って事になる。

※3: 結果やっぱり2022年現在だとますます「プログラミングする能力」より「検索能力」の方が遥かに重要だ、と言う事になってきてる。
なお、GaucheをはじめとするScheme系言語処理系のユーザーマニュアルの検索性能の低さを嘆いていたが、実のトコ、Pythonでもそんなにリファレンスの検索性能は高くない。検索をかけてみると「関係ない」項目のリストアップの方が多いくらいだ。
んで、ぶっちゃけた話すると、実は「検索機構」を作るのはメチャクチャ難しいんだ。どの検索機構でも根底はデータベースなんだが、これは基本的には「曖昧な」検索キーワードを許さない。「確実な」キーワードじゃないとそもそも探せないシステムなんだ。
言い換えると、Googleの検索技術の何が優秀か、と言うと「曖昧な検索」を受け入れる辺りだ。ユーザーの知識が「不完全」だと言う前提で検索を行い、結果、該当項目を探し出す、と言う「データベースのラッパー」の設計が見事だ、と言う意味になる。
このGoogleのようなシステムを独自に開発して、自身のプログラミング言語処理系のマニュアルに組み込む、と言うのはコストがかかりすぎる、と言うのが本当のトコだろう(だから書かれてる中身はさておき、Racketのマニュアル検索機能が「遅いにせよ」狙った結果が返ってくるトコを見ても、Racketの検索プログラムは極めて優秀だ、って事になる)。
余談だが、大手の本屋に行って、本屋で書籍を探すのを売り場のねーちゃん、とかに頼むと、彼女らはGoogleでWeb検索してるのを見てズッコケた事がある(そして結果の一番上に来るのは当然Amazonになる・笑)。自社データベースがあるのに?とか思ったんだけど、これが上の「あいまい検索」の問題で、結果自社データベースだと購買者の言う「うろ覚えの可能性が高い」書籍名だと「弾かれる」可能性が高い、からなんだ(笑)。それが分かった時、ものすごくビックリして感動した(笑)。「なるほど」と。
そういう意味で、自社でのデータベースを利用した検索結果よりググった方が確実、って状況になってるわけだ。
(これ、ホントにそうなのか、自分で本屋・・・例えばジュンク堂とかにでも行って確かめてみよう・笑)

※4: これで面白いのが任天堂のRPG、「MOTHER2」の開発秘話だ。Mother2の開発は4年かかったが、全くプログラムが「動かなかった」。ここにヘルプに入るのが後の任天堂社長になる故・岩田聡氏だが、まずは今で言うgithubbugzillaを合わしたようなモノを開発現場で作成し、そしてC言語によるユーティリティをガンガン作り出したらしい。要するにMother2開発に必要、そして特化したユーティリティライブラリを、それまでの開発難航したソースコードから判断して作りまくって、プログラマ陣に使わせはじめてから開発スピードが急上昇した、との事だ。
なお、スーファミのMother2が、家庭用ビデオゲームのゲームとしては、C言語によってプログラムされた最初期のモノのうちの1つになる(この時期は、ゲーム業界では、アセンブリ言語で開発するのが一般的だった)。

※5: ちなみに、基本機能だけ使うのなら、ANSI Common LispのloopマクロはPythonのリスト内包表記っぽい。深く使おうとするのならややこしい存在ではあるが。

※6: なお、現R7RSやRacketのmemberは拡張が成されていて、オプショナル引数として等価判定関数を取る事が出来る。
すなわち、こう書く事が可能だ。


これならもっと短く書ける。
等価判定関数としてラムダ式を与え、そこでindexにあたるxitem構造体のyに於けるitem-nameを取り出して比較する。
連想リストとassocを使った本論の関数より効率もいい筈だ。
現時点ではSRFI-1requireしてて、そこのmemberもRacketのようにオプションで等価判定関数を取る事が出来るんで、恐らく互換的な問題は生じないだろう。
しかしながら、一般的なScheme(R7RSはともかく、現時点でも実装の主流はR5RSなんで)として、ユーティリティの使い方、と言う話にしたかったんで、敢えて本論ではassocを取り上げた。

※7: ここでの => はSchemeのcondでの独特の構文だ(ANSI Common Lispでは存在しない)。
たまに条件判定での「結果」を使い回ししたい場合がある。このケースでは(null? lst)#tを返すケースだが、=> でその結果を本体部分で使いまわす事が出来る。
結果、

#tが返る => 条件節での返り値を使い回したい => not で反転させる => #f を返す

と言う流れが形成される。
なお、 => を使う際には、基本的に本体部分にはクロージャが入る。

※8: ここのトリックは、実はユーティリティとしてPythonのenumerateを作る、と言うロジックとほぼ変わらない。
ただし、アッチは整数をconsする、と言う辺りで汎用性がある。何故なら整数自体が汎用性のあるデータだから、だ。
一方、こっちはitem、と言うユーザー定義型になり、再びitemと言うデータを作るかどうか分からない。また、スロット/フィールドが同じとは限らないし、またアクセサの名称が同じとも限らない。
その辺の「条件」が厳しすぎるが故に、これをユーティリティにするのは厳しくなるわけだ。

※9: ただし、これは後での最適化の話になるだろうが、どのみち、リストを舐めつつ検索、ってのは効率の問題が生じる。今のPC環境ではクリティカルではないだろうが。
しかしながら、ここで「連想リストに変換」と言うのは、将来的にハッシュテーブルに置き換える事も可能だ、と言う可能性の提示でもある。
取り敢えず最初は「リストでどこまでも」行ってみよう。
  • Xでシェアする
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

最近の「プログラミング」カテゴリーもっと見る

最近の記事
バックナンバー
人気記事