結果、実行ファイルの作成に成功した！そういうことだったのか〜。けど、気になるのはこの圧縮ファイルの形式。tgzってよくLinuxのソフトをインストールするときに見るヤツだな？もしかしてLinuxで作ったらLinuxの実行フィル、Windowsで作ったらWindows形式のファイルが作られるんだろうか
何か楽しそうにカタンをプログラミングしてる。是非ともPSのじぱんぐ島に勝って欲しい。
結構完成に近づいてるみたい。楽しみだ。
それはさておき。
そう、tgzってのはUNIX系で良く見る圧縮形式のファイルで、Windowsではそんなに有名じゃないんだけど(と言うのは、そもそもWindowsではtgzの解凍ツールがメジャーじゃなかったから、だ)、UNIX系OSだと殆どデファクトスタンダード、って言って良い程の圧縮形式だ。
UNIX系OSだとDOSと違ってデフォルトのコマンドラインツールが豊富で、結局、端末からいつでもファイルの圧縮・解凍が出来る。
反面、UNIX系OSだと著名なzipやrarなんかは、ソフトウェアをインストールせなアカンので、結果、「どのUNIXでも使える」tgzの方がUNIX間で圧縮・解凍するならラクなわけね。
尤も、WindowsもWindows 10になってからはPowerShellコマンドとしてtgzの圧縮・解凍が出来るようになったんじゃないかな・・・・・・。っつーか「ソフトを売る」モデルのWindowsではzip/rar(あるいは7z)が有名ではあったんだけど、別にWindowsに「デフォルトで」圧縮・解凍ソフトが付属してたわけじゃない(と思う)んで、初の「デフォルト搭載の圧縮・解凍ソフト」としてtgzが付属するようになった、って言い方も出来るかも。
そしてtarと言うのは単純に言うと、複数のファイルを一つのフォルダに纏めて情報を付加するコマンドだ。語源はTape Archive(テープ・アーカイヴ)から来てる・・・「テープ」だぞ(笑)?しかも皆が想像するだろう「アレ」ではない(笑)。こんなんだ。
わはははは(笑)。オープンリールだ(笑)。
そう、元々tarと言うコマンドは、ソフトウェアを配布する際にオープンリールのテープ(ミニコン上ではテープ・ドライヴと呼んでた・笑)にハードディスクからソフトを引っ張って来て「載せる」為のコマンドだったの。実はハードディスクはフロッピーディスクより登場が早く、フロッピーディスクが無いミニコンだとソフトウェアの「受け渡し」には、PCのフロッピー/カセットテープの代わりこういうオープンリールのテープを使ってたらしい。
この「ハードディスクからテープ上にソフトウェアアーカイブを作り出す」tarコマンドの使用後に、そのアーカイブに対してgzipで「圧縮」を掛ける。これがUNIXで有名になるtgzなわけだ。
さて、
もしかしてLinuxで作ったらLinuxの実行フィル、Windowsで作ったらWindows形式のファイルが作られるんだろうか
表面的にはWindow版Racketではzipファイルが作られるが・・・。
もう一回プログラミング言語のシステム、実装を復習しよう。
現在のモダンなプログラミング言語の「実装」は、大別すると大体次の2つに分けられるんじゃないか。
- ネイティヴコードコンパイラ
- バイトコードコンパイラ
ビックリするかもしんないけど、事実上、「純粋なインタプリタ実装」ってのは現代では殆ど無いんじゃないか、って思う。
そして、繰り返すが、「インタプリタ言語」や「コンパイラ言語」なんつーモンは存在しない。プログラミング言語はその言語仕様に於いて「インタプリタであるべき」とか「コンパイラであるべき」なんて書いてるこたぁまず無いんだ。従って「C言語はコンパイラ言語」なんつー説明は「仕様を読んだ事がないヤツ」が言い出す。仕様でコンパイラである事を要求してない以上、実は実装として「C言語インタプリタ」はあって構わないんだ。
あるのは「どういう言語実装があるのか」と言うだけの話であって、言語仕様に従う限り、「コンパイラで実装する」か「インタプリタで実装する」かは実装者の好みの問題になる。
さて、上の2つに戻ろう。ネイティヴコンパイラと言うのはターゲットをハードウェアとしたコンパイラだ。具体的にはアセンブリ言語に変換した後、それをマシン語へとアセンブルする(※1)。このテのコンパイラが吐く実行形式は、ターゲットのマシンに最適化してる為高速だ。ただし、Aと言うプラットフォームからソフトウェアをBと言うプラットフォームに持っていく事は難しい。ハードウェアも違えばOSも違う。インテルチップ用に作られたソフトウェアをPowerPC、あるいはARMをCPUにしてるマシンには持ち込めない。通常、例えばC言語コンパイラはこのスタイルなんで、ソースコードレベルならいざ知らず、コンパイル済み実行形式にはポータビリティがない。
バイトコードコンパイラ、と言うのは、仮想マシン(※2)、と呼ばれる(事実上)インタプリタ対象へのマシン語へとコンパイルする処理系だ。この「バイトコード」は、マシン語はマシン語だけど、「仮想マシンの作者が勝手に作った」言わば仮想コンピュータ向けのマシン語であって、仮想マシンが動いてる本物のマシン、つまりインテルチップとかPowerPCとかARMが直接理解出来るマシン語ではない。言い換えると、バイトコードと「本物のマシン」の間に仮想マシンと言う名のレイヤーが一つが挟まってるカタチになる。
現在はこういう処理系が多い。往年のPascalから始まって(※3)、C#、Java、Python、Ruby、そしてかなりの数のLisp処理系はこの形式を取っている。
当然Racketもそうだ。
この「バイトコードコンパイラ」の特徴として、「コンパイル済みのバイトコード」は原則どのプラットフォームでも「問題なく動く」ようになってんだ。そのターゲット用の仮想マシンさえあれば、と言う条件は付くが。
例えばRacketの場合、原則、
- 書いたプログラムのソースコードは各プラットフォームで共通
- コンパイルして出来たバイトコードは各プラットフォームで共通
- 仮想マシンだけはWindows用とUNIX用で違う
って事になるわけ。尤も仮想マシン自体は僕らが書く事はないわけだ。
いや、正直に言うと、ソースコードレベルでOSによって「違いが完全になくなる」って事は無いよな。例えばUNIX特有の機能を呼び出して使おう、なんつーソースコードを書けば、そりゃ「Windowsで無い袖は振れない」って事になる。
ただ、そういう極端な話(端末の機能周りが多い・笑)さえ除けば、「LinuxでコンパイルしたバイトコードはWindowsで動くし、逆もまたしかり」なんだよ。
もう一回繰り返すけど、バイトコードコンパイラの場合、プラットフォームの違いを吸収するのは「仮想マシンのレベル」になる。
とすると、だ。配布に関わる残された問題は「あなたは仮想マシン込みでソフトを配布しますか?」になるわけだ。
これがJavaのソフトウェアを一旦インストールすると、しょっちゅう右下のポップアップで「最新のJREをインストールしますか?」って訊かれる原因だ(笑)。
JavaだとJavaRuntimeEnvironmentって呼ばれてる部分が言っちゃえば「仮想マシン」で、一回Javaのソフトウェアをインストールすると、JREはJREで独自に管理され、Javaのソフトウェアは全て「その上で」動く。これが一つの方法だ。
一方、PythonやRacketの場合、ユーザーがPythonやRacketをインストールしてくれればいいけど、そうじゃない時、「配布するソフトウェアにインタプリタをこっそり忍び込ませる」ってテが考えられるわけ。
んでこのテの仮想マシン(インタプリタ)のコア(中核)部分を切り離して、かつ、書いたソフトウェアで使うライブラリとリンクして「ソフトウェアの一部として配布する」ってやり方をするのが一つの選択肢なんだ。要は「ミニマルな仮想コンピュータも一緒に配っちまう」。
んで、厳密な定義じゃないんだけど、「インタプリタのコア部分」「ミニマルな仮想コンピュータ」をランタイム、とか呼んだりすんのね。昔のVisual BASICなんかでも「ランタイムはヴァージョンxxを用意してください」とか書いてたソフトとかあったじゃん(※4)?それ、だ。
今のWindowsだとC#やVB.NetあるいはF#はMicrosoft言語なんで、OS自体が仮想マシン込みで提供されてるし、「OSのアップデートに伴って」.Netと言う仮想マシンもアップデートされるんで、ユーザーは仮想マシンもクソも気にせんで済む。
一方、「Microsoft言語」以外だと、Javaをはじめ、そう、この「仮想マシンの配布をどうすっか」って問題がデカイんだよな。一々インストールしてくれ、ってユーザーに頼むのもアレだし・・・実際、今はどうだか知らんが、「無料ゲーム」とか面白そうなのあって、インストールしてみたらRPGツクールで作られてて、「RPGツクールランタイムが云々」とか言われて嫌になった事あんだろ(笑)?
そういう問題が、仮想マシン採用処理系で出てくる問題なんだ。
次の写真で言うと、それぞれは次の意味になる。
- Launcher: Racketがインストールされているコンピュータなら端末からソフトウェアが起動出来るように、OSが要求するスクリプトのフォーマットに手直しする(WindowsならBATファイルを作成する)。
- Stand-alone: RacketがインストールされているコンピュータならRacketからコア(ランタイム)を切り出す必要がないので、バイトコードへとコンパイルするだけでいい。
- Distribution: Racketがインストールされていないコンピュータだと別途ランタイムが必要になるんで、配布形式にランタイムを含める。
つまり、前2者は特別インタプリタのコア部分(ランタイム)を含める必要がないんで、結果軽いんだけど、最後のパターンだとインタプリタのコア部分(ランタイム/仮想マシン)が必要なんで、「Racket本体(の一部)を含めますよ?」と言う意味になる。当然これはファイルサイズがデカくなるんで、当然圧縮した方が良くなるわけだ。
これは繰り返すけど、Racketだけじゃなくって、PythonとかRubyでも同様の問題があって、この「ランタイムを含むか否か」と言うのは配布形式に於いては非常に重要な課題となる。
ただ、UNIX系OSだとデフォルトでPythonを既に搭載してるケースが多いんで、RacketやRuby程面倒にはならない、って面はある。一方、WindowsだとPythonはデフォルトでは存在しないんで、配布形式を作成する際にはRacketと同様の手間がかかるわけだ(PythonのWindowsでのexeファイルを作成するユーティリティは、上記のRacketのような事を結果やってるわけだ)。
とまぁ、RacketやPythonで言う「コンパイル済ソフト配布」はC言語のようなコンパイラ処理系が作り出す実行形式とは意味合いが違うんだ。
要仮想マシン、って事だな(※5)。
さて。
圧縮の話が出たから、ってワケでもないが、今回の軽いネタは圧縮と解凍の話だ。
とは言っても難しい話はしない。それどころか以前書いた話の焼き直しをしようと思う。言い換えると同じ話を別の角度から見てみる。
圧縮技術の基本中の基本をランレングス圧縮と言う。
これは例えば'(A A A A A B B B B B B B B B A A A)と言うリストが与えられた時に'((5 A) (9 B) (3 A))と言うリストを返す事だ。意味は「Aが5個続いた後にBが9個続き、そしてAが3個続く」と言うモノだ。確かに情報が圧縮されているだろう。
もう一回、ポール・グレアムが書籍「ANSI Common Lisp」で挙げた例を再録しよう。
 | ANSI Common Lisp (スタンダードテキスト) ポール グレアム 桐原書店 |
レストランでは(ランレングス圧縮のアルゴリズム)は次のように働く。ウェイトレスが4人組の客のテーブルへとやってくる。
「ご注文は何にしますか?」とウェイトレスが尋ねる。
「日替わりを。」と最初の客が答える。
「私も同じモノを。」と二人目の客。
「それ、良さそうね。」と三人目。
皆が四人目を見る。「コリアンダースフレが食べたい。」と彼は静かに答える。
ウェイトレスは鼻を鳴らし、ヒールの向きを変え、カウンターへと戻っていく。
「日替わり3つ」と彼女はコックに大声で注文し、「それとコリアンダースフレ1つ」と続ける。
さて、ポール・グレアムは、その「ランレングス圧縮」を書いたANSI Common Lispのコードを次のように紹介している。
当然「意味が分からない」コードじゃない。ただ・・・うん、Lisp名人のポール・グレアムにしてはちと冗長なコードだよな、ってのが正直なトコじゃないだろうか。
誤解のないように言っておくと、これは別に書籍「ANSI Common Lisp」でアルゴリズムの紹介として本の後半辺りで出してきてるコードじゃない。むしろ前半も前半、3章で「ANSI Common Lispのリスト」を解説する為に出してる「サンプル」なんだ。「Lispではリストを使ってこういう風にプログラミングしますよ」と。
従って、ANSI Common Lispは初めて、って言う読者に対して「Lispのすげぇ機能を使ったプログラム」を見せてるわけじゃない。むしろそういう「Lisperが良く使うテクニック」を排して書かれたプログラムだ。
よって、僕らみたいに「ある程度Lisp慣れしてる」層にとっては、テクニカルな意味に於いてはちと物足りないプログラムになってる。言い換えると「もっと短く書けるよな?」と思うわけだ(笑)。
じゃあ、ある程度Lisp慣れしてたらどういうコードになるのか。Racketでこの「ランレングス圧縮」を書くなら、スタンダードな解は恐らく次のようになるんじゃないか。
(define (compress x)
(reverse
(foldl (lambda (elt lst)
(match lst
('() (cons elt lst))
((cons head tail) (match head
(`(,x ,xs) (if (eqv? elt xs)
(cons `(,(add1 x) ,xs) tail)
(cons elt lst)))
(else (if (eqv? elt head)
(cons `(2 ,head) tail)
(cons elt lst)))))))
'() x)))
Racketでポール・グレアムより短く書ける原因の一つは、ANSI Common Lispの仕様に含まれてないパターンマッチング構文、matchの存在だ。もちろん、実の事を言うと(Racketは厳密には違うが)Schemeの仕様にはmatchは無い。無いけど、match自体がSchemeでは有名で、かなりの実装がmatchをビルトインしてる。と言うのも「コンピュータサイエンティストのおもちゃ」であるSchemeは、プログラミング言語実装の実験場で、パターンマッチングの研究も盛んだったからだ。具体的にはAndrew Wrightと言う人の論文がキッカケで、これが各実装に広まったんだな。
そして、パターンマッチ及び構造化代入はあまりにも便利で、慣れるともはやこれナシでプログラムを書くのは考えられなくなる。
しかし、もっと大きな理由が、やっぱり畳み込み関数foldの存在だ。こいつがプログラムする側に「反復」を意識させずに物事を短くしてくれる。
foldの第一引数procは最低でもリスト(lst)と加工したい値の初期値initの2つを引数に取る。加工したい値は一種のアキュムレータ(累積値)であって、計算が進むとどんどんそのカタチを変えていく。
今回のcompressではこのアキュムレータの「状態」によって計算を切り替えてるわけだ。最初の状態は空リストであって、この状態ではlstからどんな値がやって来ようとconsする。と言うのも、空リストな以上、「以前取ってきたデータはない」わけで、重複もクソも関係ねぇからだよな。
あとの大枠のパターンは何にせよフツーのリストなわけだ。それを先頭(head)と残り(tail)のパターンとする。initが累積値な以上、常にheadの方が新しい情報だ(後ろに行けば行く程「古い情報」って事になる・・・lstの先頭の方の情報だ)。
この「新しい」情報のパターンも2種類ある。2要素のリストか、データそのものだ(1個しかない場合、「何個あるか」の情報は付加しない・・・ポール・グレアムのスタイル、ではな)。
リストだった場合、少なくとも前回lstから引っこ抜いてきたデータは連続して(2回以上)現れている。今lstから引っこ抜いて来たデータと同じデータだったら、「連続出現回数」を+1する。そうじゃなかったら今引っこ抜いてきたデータをそのままconsすればいい。
リストじゃない場合、前回「だけ」現れたデータだ。今引っこ抜いてきたデータと同じだったらリストを生成しなおし、前回 + 今回で都合2回現れた、って情報を付加してconsする。そうじゃなければ今回現れたデータも新しく登場したデータなんでそのままconsだ。
こう、引数のリスト(lst)だけで無く、アキュムレータであるinitの状態さえ逐一チェックして書けるのがfoldの強みなんだ。
これにより、ランレングス圧縮は完成する。簡単だろ?
> (compress '(1 1 1 0 1 0 0 0 0 1))
'((3 1) 0 1 (4 0) 1)
Pythonなら次のように書けばいい。
def compress(x):
from functools import reduce
def foo(lst, elt):
match lst:
case []:
return [elt]
case [head, *tail]:
match head:
case [x, xs]:
return [[x + 1, xs]] + tail if elt == xs else [elt] + lst
case head:
return [[2, head]] + tail if elt == head else [elt] + lst
return list(reversed(reduce(foo, x, [])))
Pythonのラムダ式は貧弱なんで、文を仕込めない。つまり、Python 3.10以降で登場したパターンマッチング構文はラムダ式に組み込めないんだ。
しょーがないんで、ローカル関数fooを作る。fooのロジックはRacketでのそれと全く同じだ。そしてfunctools.reduceをRacketのfoldlと同様に使う。如何にfunctools.reduceが強力なのか、何故に最重要関数だと言ってるのか、それを味わって欲しい。
そして新登場のパターンマッチング構文だけど、とにかく慣れろ。上に書いた通り、パターンマッチングはラク過ぎて、これを味わうと条件分岐で書くのがかったるくなる程だ。実際、僕も、Pythonでは条件式は使うが、圧倒的に条件文を書くよりパターンマッチングに頼る比率が高くなった。
言い換えると、Pythonでのモダンなプログラミング方策としては、「パターンマッチングが使えない時に」条件式を使う、って言う風になる気がする。もう「フツーの条件文」は限りなく「要らない子」に近くなっている。
ちなみに、現在のPythonの泣き所はイテレータだと思う。関数を使っても一体いつ返り値が実値でいつイテラブルなのかひっじょーに分かりづらいんだよ(笑)。
いや、「効率性の為にイテラブルにしました」ってのは分かるんだけど、逆順リストが欲しいだけでイテラブルを返されると、それをリストに変換する、ってのはひと手間なんだ。当たり前だよな。
いや、分かるよ?でもSchemeみたいにStream使用目的の場合はStreamのライブラリを使って・・・と言うような戦略が立たないんだよな、Pythonだと。Python 2.xの頃はイテラブル版とそうじゃない版の2つを提供してたんだけど(有名なブツとしてはrangeとxrangeってのがあった)、今やイテラブルが全体を侵食してる。
いや、実行効率を考えるとそれはそれでいいんだよ。でも実は「Pythonは学びやすい言語だ」ってテーゼに対して明らかに陰りが出てるんだ。New Comerが来た時、「これは一体何なんだ」ってなりやすいだろ?
実はPythonに限った話じゃないんだけど、OSやプログラミング言語ってこういうのが良く起きるんだよな。つまり、「初期段階から使っていた人の方が有利な法則」だ。
要は、何らかの仕様変更があった場合、古くから使ってた人は「差分の部分を知れば良い」。ところがNew Comerにとってみると仕様変更が重なりすぎて、全体像に対して「何が何だか分からなくなってる」ってのは良くあるんだわ(笑)。一貫してねぇじゃねぇか、と(笑)。
どんどんPythonってJava化してんだよ(笑)。Javaだって機能を付けすぎて何が何だか分かりづらくなってんじゃん(笑)。元々設計が悪いトコに色々新機能付けるモンだから、New Comerに対しては「一貫していない」「全体像を把握するのが困難な」言語になっている。
Lispが優秀なのは、ある意味言語デザイナー側が「何か新しく考えて機能を付け足す」事が出来ない辺りなんだよな(笑)。いや、出来るよ?マクロを使って。そしてそれはデザイナー側が出来るならユーザーも出来る、って範疇の話なんだけど、それ以前に「構文がない」のがLispの特徴だから、だ。「何か新機能を付けました!」っつってもLispの構文は崩れないんだよ(笑)。何故なら「構文が無いから」だ(笑)。無い袖は振れないんで、どんな新機能を作ってもS式内にピッタリ収まってしまう。
そういう安定度を誇ってるのがLispであって、60年前後の歴史は伊達じゃないんだよ(※6)。よって性質的には「殆ど変更がない」Lispは歴戦ユーザー相手だろうがNew Comerだろうが、同じ程度の「学習の難易度」しか提供しない。こんな言語はなかなか無いだろう。
話を戻すが、Pythonの「ちょこちょこ行われる」変更、には一貫性がないし、New Comerにとって学習負担になってると思う。使う方も「いつイテラブルでいつそうじゃないのか」は把握しづらいし、また、作る方も「どっちにするんだ?」ってのは悩ましい問題だ。
ここでは「フツーの関数」であるfunctools.reduceを基礎としてcompressを組み上げたんで、functools.reduceと同様に実値であるリストを返り値としてる。
さて、圧縮が出来た、って事は解凍がある。以前の記事はそこには触らなかったんだけど、今回は触ってみよう。
大体、圧縮したデータが元に戻らんようだったら使いようがない(※7)。
ポール・グレアムは書籍「ANSI Common Lisp」で次のようなコードを紹介してる。
compressに比べると短いが、それでも冗長に見える。
何が原因か、っつーと再帰を使ってるから、だよな(笑)。いや、Lisp使いは再帰大好きっ子ではあるんだけど、手慣れてくれば来る程「自分が書くコードの中での再帰比率が減っていく」。代わりにfold/reduceのような高階関数の登場比率が増えるんだ。
いや、ホント、何年もプログラミングでのたくっていて、C言語辺りで「反復を毎回書いてる」奴らを尊敬するよ(笑)。あんな面倒くさい構文を良く使い続けてられるよな、と(笑)。
プログラミング初心者は反復が嫌いだ。一方、Lisp慣れしてる奴らも再帰だろうと反復が嫌いだ(笑)。プログラミング経験の差があれど、初心者もそこそこモダンな言語のユーザーも、結論は全く同じなんだ(笑)。これを初心忘るべかざる、と言う(違
さて、圧縮はfold/reduceで書いた。じゃあ解凍で使うべき高階関数は・・・・・・?そう、ここで前回扱ったunfoldが出てくるんだよ。
fold/reduceは「何らかのデータを何にせよ単一の値に畳み込む」関数だ。言い換えると、畳み込み関数と言う渾名があるように、リストをアキュムレータへと畳み込む。要は本質的には圧縮関数なんだ。
逆にunfold関数は圧縮されたデータを復元する。解凍関数ってのがunfold関数の本質だ。
両者の形式を次のように比較すれば本質が見えるだろう。
- (fold エンコーディング規則 圧縮データの保存先 データ) => foldはエンコーダ
- (unfold デコード規則 圧縮されたデータ) => unfoldはデコーダ
相変わらず数学的バックグラウンドがどーなのか、ってのはサッパリ分からんが、foldの役割はエンコーダでunfoldの役割はデコーダと考えれば何となく双対っぽい(笑)。
そして、両者共エンコーディング規則、デコーディング規則をラムダ式として与えてるわけだ。
さて、こう考えるとunfoldの第2引数、シードは「圧縮されたデータ」と言う事だ。
繰り返そう。zipやrarが具体的にどういうエンコーディング規則を持ってるか、は知らんが、foldやunfoldは「理論的には」エンコードやデコードの規則をラムダ式で与えればファイルなんかでさえガンガン圧縮・解凍してくれる、って事になる。
- (fold zip/rarのエンコーディング規則 圧縮ファイルの出力 元ファイル)
- (unfold zip/rarのデコーディング規則 圧縮ファイル)
もうちょっと書くとこうか。
;;; 圧縮(with-input-from-file "file.txt"
(lambda ()
(fold zip/rar-encode <compressed.zip/rar> <file.txt>)));;; 解凍(with-input-from-file "compressed.zip/rar"(lambda ()(with-output-to-file "uncompressed.txt"(lambda ()(printf (unfold zip/rar-decode <compressed.zip/rar>)))))
注: <...> は何らかの機能で適するオブジェクトへと変換されたモノ、とする。
もちろんzip/rarなんて簡易な関数がある、とは言わないし、読み込んだファイルはリストデータではないんで、ここで書いてるのは結果かなり端折ってはいる。が、あくまで理論的モデル、としてはこういう構造が考えられるわけだ。foldは受け取ったファイルから圧縮ファイルを作り出せる。また「圧縮する際に」元データを消すわけにはいかないので、返り値用に別途アキュムレータが存在する必然性も分かるだろう(ファイルを圧縮する度に元ファイルを消すようなソフトウェアにはユーザーは間違いなく激怒する・笑)。
逆に、unfoldは実行結果が元データそのものになるんで、アキュムレータ的なモノは必要ない。解凍/復元したファイルを新しく作るのならunfoldの計算結果そのものをファイル書き込み機構に手渡すしかないわけだ。
これが2者が形式的には対称性がない、と言う迂遠な説明になる。
いずれにせよ、エンコーディング規則、デコーディング規則さえあれば、fold/unfoldは汎用的な圧縮/解凍のフレームワークを提供してる、と考える事が出来る。
とまぁ、そういう与太は置いておいて。元のランレングス圧縮のデコーディングを考えよう。
これはunfoldを利用してこう書く事が出来る。
(define (uncompress lst)
(apply append
(unfold null?
(lambda (x)
(match-let (((cons head tail) x))
(match head
(`(,k ,v) (make-list k v))
(else `(,head)))))
cdr
lst)))
ランレングス圧縮されたデータはリスト形式で与えられるので、当然空リストになれば「復元終了」なわけだ。また、リストを先頭から消費していくので、シード(圧縮データのリスト)の「更新」はcdrを取って行く事となる。
さて、デコードのルールだが、例えば '((3 1) 0 1 (4 0) 1) と言う圧縮データに対し、どんどんcarしていく前提だと、
- car したブツが(k v)と言う形式のリストだった場合、長さがkの要素がvのリストを作る。
例えばcarしたブツが'(3 1)だったら'(1 1 1)と言うリストを作るわけだ。
そして
- carしたブツがリストじゃなければそれをリスト化する。
例えばcarしたブツが0だったら'(0)と言うリストを作るわけだ。理由は、最終的に全部をappendする為だ。逆に言うと、appendはリスト同士を繋げるんで、生成したブツの要素が全部リストじゃないとマズいわけだ。
- '((1 1 1) (0) (1) (0 0 0 0) (1)) => append出来る
- '((1 1 1) 0 1 (0 0 0 0) 1) => append出来ない
そういった帳尻を合わせる為、にリスト化している(※8)。
結果、デコードは性交成功し、元データの復元、と相成るわけだ。
> (uncompress '((3 1) 0 1 (4 0) 1))
'(1 1 1 0 1 0 0 0 0 1)
compressとuncompressを直列に行うと、当然元データは元のまま、だ。
> (uncompress (compress '(A A A A A B B B B B B B B B A A A)))
'(A A A A A B B B B B B B B B A A A)
> (compress (uncompress '((5 A) (9 B) (3 A))))
'((5 A) (9 B) (3 A))
さて、Python版だが、前回作ったunfoldrを使う。
def uncompress(lst):
import itertools
def foo(x):
if x == []:
raise StopIteration
else:
match x:
case [head, *tail]:
match head:
case [k, v]:
return [[v] * k, x[1:]]
case head:
return [[head], x[1:]]
return itertools.chain.from_iterable(unfoldr(foo, lst))
ロジック自体はRacket版と同じだ。同じだが、ローカル関数fooを作ってる理由は先にも書いた通りPythonのラムダ式がへなちょこだから、だ。
そしてSchemeのSRFI-1のunfoldと違い、こちらのunfoldrはHaskellの影響を受けて作ったモノだ。よってコールバック関数(foo)は一つで、そこでデコーディング規則を全て書く。
まず、unfoldrはイテレータなのでほっとけば無限ループを行う。従って、停止条件(与えられたリスト(lst)が空リストだった場合)ではStopIteration例外を投げる事、とする。
あとの「変換規則」はRacket版のまま、だ。matchの入れ子になってるが、特に驚くに値しないだろう。
見慣れないのは返り値に被ってるitertools.chain.from_iterableだろう。これは返り値であるPythonのリストを平坦化する為に使っている。
とは言っても、この辺もPythonの悩みどころで・・・・・・割に豊富なユーティリティを備えてるPythonだが、どういうわけか(いや、原因はハッキリしてるが・笑)万能の「リスト平坦化関数」が存在しないんだ。理由?Pythonは再帰が苦手だからだよ(笑)。
どんなリストが与えられても完璧に平坦化するには再帰が必然なんだけど、Pythonは再帰が苦手だからそういう関数が書けないんだ(笑)。itertools.chain.from_iterableは不完全ながら高速にリストの入れ子を平坦化する。そんなわけでこれを使ったわけだ。
>>> list(itertools.chain.from_iterable([[1, 1, 1], [0], [1], [0, 0, 0, 0], [1]]))
[1, 1, 1, 0, 1, 0, 0, 0, 0, 1]
なお、itertools.chain.from_iterableはイテラブルを返すが、uncompressはリストに変換せずにそのまま、とした。何故ならunfoldr自体をイテレータとして設計したんで、そこは壊したくなかった、と言うそれだけの話だ。
カエサルのものはカエサルに。イテレータのものはイテレータに、っちゅうわけだ(謎
>>> ''.join(uncompress(compress('AAAAABBBBBBBBBAAA')))
'AAAAABBBBBBBBBAAA'
>>> compress(uncompress([[5, 'A'], [9, 'B'], [3, 'A']]))
[[5, 'A'], [9, 'B'], [3, 'A']]
取り敢えず今回はこんなトコかな。使いどころが難しそうなunfoldの実用例を思いつけたんで良かった良かった。
以上。
※1: Mac OS Xで有名化したLLVMはアセンブリに変換する前に仮想マシン用のバイトコードへと一旦コンパイルする。つまりマシン語を生成する前にコンパイルを2段階にわたって行う。
これは何らかの高級プログラミング言語で書かれたソースコードを直接アセンブリに変換するより良質なアセンブリを作りやすい、と言う研究結果からこのような実装になっている。
まぁ、細かい話をすると「そういう方式を採用してる実装もあるよ」と言う例だが、最終的にターゲット用のマシンコードを吐き出す、と言う意味ではターゲットはあくまで物理的なハードウェアだ。
※2: 「仮想マシン」と言う名前のインタプリタは文字通り、単純にはCPU(とメモリ)をエミュレートしたインタプリタだ。そしてCPU + メモリの組み合わせも動作原理はインタプリタだ。コンピュータは原理的にはインタプリタなんだ。
その「仮想コンピュータ」は大まかには実装方法が2つある。
主流は、ハードウェアとしてはほぼ絶滅しちまったスタックマシン。LispやPythonをはじめとして、C#、Java、等数多くのプログラミング言語処理系下のレイヤーとしてこれが採用されている。
もう一つは、マイナーながらも現在のハードウェアの殆どと同じような動作をするレジスタマシンだ。
後者は、例えば数多くのソフトウェアのマクロ言語として採用されてるLuaで使われている。
なお、これで言うと、実は、例えばパソコン上で動く「ファミコン」「スーパーファミコン」のエミュレータや、PC-9801のエミュレータも、「命令を実機と同様にした」一種の(レジスタマシン採用の)インタプリタなんだ、と言う事が出来る。
実はゲームやレトロPCのエミュレータもプログラミング言語のインタプリタと技術背景やコンセプトを共有してるんだ。
※3: 元々Pascalは、プラットフォーム間のソフトの移植性の問題を解決する為、仮想マシン前提で動くように作られたプログラミング言語だった。特に70年代後半から80年代前半で有名だったのが、カリフォルニア大学サンディエゴ校で作られたUCSD Pascalだ。
何度も同じ例を出して恐縮だが、この処理系での最大の性交成功例がロールプレイング・ゲームのWizardryだ。WizardryはUCSD Pascalで書かれたが故、移植プラットフォーム数が極めて多い。家庭用ゲーム機を除いても9種類くらいのプラットフォームで画像を除くと「ほぼ同じソフトウェアが動いている」。これは、「仮想マシンだけ取り替えれば良い」と言う性質の為だ(結果、フロッピーディスクには仮想マシンも含まれている)。日本のPC-8801/9801版、等も例外じゃない。
しかし、80年代後半になるとネイティヴコンパイラのTurbo Pascal(現・Delphi)がポピュラーになり、当初のPascalが持ってた移植性の高さは無くなってしまった。
※4: Visual Basicなんかも(バイトコード)コンパイラだろう。「Basicのようなインタプリタは・・・」とか言ってるおっさんの話には耳を傾けない事(笑)。大体、おっさんは思い込みが激しく、脳内で言う「BASIC」はNECのPC-6001のモノだったりして、「BASICの仕様を読んで理解してる」わけでもない。
※5: なお、Mac OS Xの場合、CLIのソフトは問題がないが、実はGUI部分自体が「巨大な仮想マシン」みたいになっていて、結果、書いたソフトをその環境から切り離すのが物凄く難しい形式になっている。言い換えるとそれが、現Macで採用されているObjective Cと言うプログラミング言語の特徴だ。イメージ的にはGUI全部がEmacsみたいなモノで、全てがそこに閉じ込められている形式、って言えば分かりやすいか。
そんなわけで、GUI込みになると、Mac <-> Linux間のソフトの移動よりWindows <-> Linux間のソフト移動の方が簡単となる。
※6: このLispの安定性の根本は、結局、「言語デザイナーが云々する」が基盤で考えられた言語ではなく、ラムダ算法と呼ばれる数学の一ジャンルに基礎を於いて、そこから逸脱してない言語だから、だ。つまり、「言語の構文設計」なんつー事を全くやらんでLispが作れる、ってところが大きい。
なお、Lispの60年前後の歴史に於いて、恐らく一番ドラスティックな、つまり根幹の変更はダイナミック・スコープに対してレキシカル・スコープが登場した事だろう。ただし、それがLisp語族に取って問題にならないのは、こういうドラスティックな変更は当然「全く新しいLisp」をもたらす。C言語に対してRustが現れるようなモノで、当然そこでは「互換性が無い新言語登場」と言う事になるわけだ。しかし、それが起きる、つまりパラダイム変換が起きたのは60年の歴史でも一回くらい、だし、それ以外では、「機能の追加」程度でLispの基本設計は全く揺るがないんだ。
一方、例えばJavaなんかで「新機能を搭載しても一貫した設計」なんて試みると、結果、過去の資産をマジで全部捨てて「新しい言語を作るに等しい」事になっちまうんじゃないか。それを避ける為にはad-hocな方策を取らざるを得ず、「新機能はいいけど(構文的に)使いづらい」なんつー事がわんさか出てくるわけだ。
※7: とここでは言ってるが、「データサイズを小さくするだけが目的の変換」だと、これも圧縮は圧縮だが、「元には戻せない」タイプの変換も存在する。
そのテの圧縮フォーマットは主に画像や音声、あるいは動画で使われている。画像で言うとPNGはどんなサイズにしようが元の写真の状態に戻せるが、一方、JPEGの場合はそうは行かない。また、動画や音声もあるファイルがデカすぎるんでサイズを変換する為に別のフォーマットにしたら元の画質・音質に戻りませんでした、と言う事も良くある。
このテの「元のデータに戻せない」類のデータ圧縮を「非可逆圧縮」と呼ぶ。
※8: もちろん、ここで単一要素をリスト化せず、後続のappendの処理も避けて、flattenしても良いとは思う。
> (flatten '((1 1 1) 0 1 (0 0 0 0) 1))
'(1 1 1 0 1 0 0 0 0 1)
