檜山正幸のキマイラ飼育記 このページをアンテナに追加 RSSフィード

キマイラ・サイトは http://www.chimaira.org/です。
トラックバック/コメントは日付を気にせずにどうぞ。
連絡は hiyama{at}chimaira{dot}org へ。
蒸し返し歓迎!
ところで、アーカイブってけっこう便利ですよ。タクソノミーも作成中。今は疲れるので作っていません。

2016-08-25 (木)

あのサンプル画像の正体

| 12:49 | あのサンプル画像の正体を含むブックマーク

画像処理のサンプルとして、次の女性の肖像がやたらに登場しますよね。もう定番です。

[*1]

この画像は、もっと大きな写真から顔の部分だけを切り出したものです。

[*2]

もとは、ヌードの全身写真です。ここに画像を挿入するのは憚られるので、リンクだけにしておきます。

右下に PLAYBOY'S PLAYMATE OF THE MONTH とあります。あーなるほど。いかにもPLAYBOYのグラビアっぽいですね。

Wikipedia項目PLAYBOYを調べてみると:

最も売れた号

『プレイボーイ』で過去に最も売れたのは1972年11月号で、716万1561冊を記録した。また、この号に含まれていたレナ・ショブロムのヌード写真はその一部がスキャンされて画像圧縮アルゴリズムの評価用テスト・イメージとして標準的に使用されるようになった。この画像は同分野では単に「レナ」として知られている。

そうか、あの画像はレナさんの顔だったんですね。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20160825

2016-08-24 (水)

arXiv.orgのオルタナティブ!? viXra.org

| 11:47 | arXiv.orgのオルタナティブ!? viXra.orgを含むブックマーク

viXra.orgという論文アーカイブサイトがあります。「ヴィクスラ」と発音するのかな? サイトの名前とデザインは、arXiv.orgを真似てるんだかパロってるんだか。実際、arXiv.orgのオルタナティブを標榜しています。

http://vixra.org/why によると、arXiv.orgの承認システムによって投稿を阻まれている人々でも自由にアーカイブを公開する場を与える、ということらしいです。原則的に投稿は拒否されません(引用: We will not prevent anybody from submitting)。

これで思い出すのは南堂さんです。

南堂さんは、ご自身の“超球理論”をarXiv.orgに投稿したいけど承認を得られない、と嘆いていました。そんな南堂さんでも、viXra.orgなら投稿できるんじゃないでしょうか。

ただし、ものには限度があって、viXra.orgであっても、猥褻、誹謗中傷など公序良俗に反する内容、剽窃・盗用、危険性を持つ誤謬は拒否または削除される、とのこと。「危険性を持つ誤謬」(dangerously misleading)は微妙ですね。例えば、「ガンは通常医療に頼らずホメオパシーで治せ」という内容は「危険性を持つ誤謬」とみなされるのか否か?

南堂“超球理論”は危険性を持つように思えないので、たぶん大丈夫でしょう。

こんなゆるい基準で投稿を受け付けていると、トンデモ論文サイトになってしまうのではないか? その点は覚悟の上らしいです。

It is inevitable that viXra will therefore contain e-prints that many scientists will consider clearly wrong and unscientific.


このような事情から、多くの科学者が明らかな間違い・ニセ科学であると判断する電子的プレプリントがviXraにアーカイブされるのは避けようがない。

それでもなお、投稿と公開の自由を担保して、通常なら無視されてしまうような優れたアイディアを拾い上げる機会を提供する、という理念なんですね。


viXra.orgにたどり着いたのは、割と珍しいキーワードで検索して見つかったPDF論文でした。URLは全然気にしてなかったんですが、内容がどことなくアヤシイのです。その論文のサイトがviXra.orgだった、というわけです。

今まで知らなかったのは、Googleでの検索順位が上位には来ないからでしょう。まー、上位に来たらマズイ気はします。

viXra.orgの意義を判断するのは難しいですが、このサイトの論文を読むときはフルスロットルの注意力と判断力が必要なので、疲れるなー、とは思います。


[追記]次はジョークサイト:

The snarXiv is a random high-energy theory paper generator ...

[/追記]

トラックバック - http://d.hatena.ne.jp/m-hiyama/20160824

2016-08-22 (月)

モノイド圏の単位対象の定義について: これ難しいやん

| 12:19 | モノイド圏の単位対象の定義について: これ難しいやんを含むブックマーク

(C, ¥otimes, I)をモノイド圏とします。α, λ, ρをそれぞれ、結合律子、左単位律子、右単位律子とします(律子(りつし)に関しては「律子からカタストロフへ」を参照してください)。

λ, ρに関する等式的法則を書き並べてみます。ただし、αによる括弧の組み換えは省略します(その意味で多少不正確です)。

  1. ρA¥otimesB = A¥otimesλB : A¥otimesI¥otimesB ¥stackrel{¥sim}{=} A¥otimesB
  2. λA¥otimesB = λA¥otimesB : I¥otimesA¥otimesB ¥stackrel{¥sim}{=} A¥otimesB
  3. A¥otimesρB = ρA¥otimesB : A¥otimesB¥otimesI ¥stackrel{¥sim}{=} A¥otimesB
  4. λI = ρI : I¥otimesI ¥stackrel{¥sim}{=} I

通常は、1番がモノイド単位の公理として採用されます。しかし僕は、2番と3番を一緒にしたほうが使いやすい気がして、個人的には2番+3番を仮定していました。その背景には、「1番 ⇔ 2番+3番」だろうという思い込みがあります。

間違ってました。実際は「1番 ⇔ 2番+3番+4番」でした。つまり、1番を採用しないなら、2番、3番に加えて4番も公理に入れないとダメなんです。

「1番 ⇒ 2番+3番+4番」、つまり1番を仮定すれば残りの3つが出てくることはケリー(G. Max Kelly)が発見したそうです。簡単な等式的な変形かと思いきや、これは難しいです。次の古い(1993)論説の最初のほうに証明が書いてあります*1

「2番+3番+4番 ⇒ 1番」については、サーヴェデラ(Neantro Saavedra Rivano)が示したそうです。このことについては、ヨアヒム・コック(Joachim Kock; SDGのAnders Kockとは別人だが、赤の他人ではないようだ)が解説しています。

モノイド圏の単位対象の定義は、けっこう難しい問題みたいです。1番にしろ「2番+3番+4番」にしろ、高次圏に拡張するには問題があるようです(よく知らんけど)。それで、別な定義が提案されています。

とりあえず、単位対象がない半モノイド圏(C, ¥otimes)を考えます。Cの対象Uに対して、次の性質を定義します。

  • Uが左消約的(left cancellative)とは、U¥otimesX ¥stackrel{¥sim}{=} U¥otimesY ならば X ¥stackrel{¥sim}{=} Y が成立すること。
  • Uが右消約的(left cancellative)とは、X¥otimesU ¥stackrel{¥sim}{=} Y¥otimesU ならば X ¥stackrel{¥sim}{=} Y が成立すること。
  • Uがモノイド・ベキ等対象(monoidal idempotent object)とは、U¥otimesU ¥stackrel{¥sim}{=} U であること。

左右の区別は逆にする人もいそうです。消約性のイコールは同型にしてもいいかも知れません。[追記]同型に直しました。[/追記])まーともかく、以上の準備のもとで、単位対象を「左消約的かつ右消約的なモノイド・ベキ等対象」として定義します -- 名前が長い! 「消約ベキ等対象」でいいかな。この定義だと、高次化に都合がいいらしいです(よく知らんけど)。高次圏における単位対象や恒等射に関してはコックがまとめページを作っています。

モノイド圏に関する新しめの解説では、「単位対象=消約ベキ等対象」としているものもあります。例えば:

λ, ρは後から定義して、冒頭の等式はすべて定理になります。特に、λI = ρI : I¥otimesI ¥stackrel{¥sim}{=} I は、最初に与えたベキ等性に一致します。

どうでもいいような細かい話の割には難しいので、現実的な態度としては、冒頭の4つの等式は最初から仮定して自由に使う、でいいんじゃないかと思います。


[追記]

以前「豊饒圏(ピノキオ)が圏(人間)になる物語」において:

δ = λI-1 = ρI-1 の証明はけっこう難しいようで、(I, δ, idI) がコモノイドになることは一般的には自明ではありません。

と書いているので、λI = ρI は成立するが難しいことは知ってはいたんですね。

λI = ρIGlobularによる証明があります→ http://globular.science/1512.002v1 (chorome推奨)-- これを眺めると、難しいことが実感できるでしょう。

[/追記]

*1[追記]短いノートとしては、http://www.mathematik.uni-muenchen.de/~pareigis/Vorlesungen/98SS/Quantum_Groups/LN3_2.PDF (9ページ)があります。Bodo Pareigisのコースの一部ですが、モノイド圏について簡潔にまとめられています。[/追記]

トラックバック - http://d.hatena.ne.jp/m-hiyama/20160822

2016-08-19 (金)

無料で入手できる本格的(紙なら高額)な微分幾何の専門書4選

| 16:53 | 無料で入手できる本格的(紙なら高額)な微分幾何の専門書4選を含むブックマーク

コンピュータ科学や組み合わせ論を“微分幾何”とみなす:CADGの夢」に関連して微分幾何について調べていたとき、商業出版物(紙の書籍)と同等なPDFをみつけました。「無料で入手できる本格的(紙なら高額)な理数系専門書15選」への追加として、4点の書籍を紹介します。

Functional Differential Geometry

Functional Differential Geometry (MIT Press)

Functional Differential Geometry (MIT Press)

タイトルは、「Functional Programming + Differential Geometry」の意味らしいです。著者の一人Gerald Jay Sussmanは、あの『SICP 計算機プログラムの構造と解釈』のサスマンです。微分幾何の教科書に、Scheme*1のコードが散りばめられています。

The Convenient Setting of Global Analysis

タイトルのConvenientは単に「便利な」という意味だけではなくてテクニカルタームでもあります。ユークリッド空間の代わりにコンビニエント・ベクトル空間(convenient vector space)という空間を使った無限次元微分多様体論の教科書です。

Synthetic Differential Geometry

SDG(Synthetic Differential Geometry)の定番教科書です。

Synthetic Geometry of Manifolds

リー理論、微分作用素ラプラシアンなどを、SDG、smooth scheme(C-scheme)*2の手法で扱ったもの(らしい)です。

*1:代数幾何のスキームとは関係ありません。Lispの方言であるプログラミング言語Schemeです。

*2プログラミング言語Schemeとは関係ありません。代数幾何で登場するスキームです。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20160819

2016-08-09 (火)

パワーアップ・モナド工場の秘密

| 12:20 | パワーアップ・モナド工場の秘密を含むブックマーク

モノイドからモナドを作る話は:

C = (C, ¥otimes, I) をモノイド圏として、C内のモノイドの圏を Monoid(C)、C上のモナドの圏を Monad(C) とすると、Monoid(C)→Monad(C) という関手があります。(monoidとmonadは綴が似ているので注意してください。)

ラックス・モノイド関手については、次の記事で書きました。

ラックス・モノイド関手に関する次の2つの定理は、ラックス・モノイド関手の定義からすぐに出ます。

  1. 2つのラックス・モノイド関手を結合すると、またラックス・モノイド関手になる。
  2. 単一対象と恒等射だけからなる自明圏からのラックス・モノイド関手は、モノイドと同じである。

2番めの定理は次の記事で述べています。

CEをモノイド圏として、F:CE をラックス・モノイド関手とします。先に挙げた2つの定理を組み合わせると:

  • ラックス・モノイド関手Fは、Monoid(C)→Monoid(E) を誘導する。

Dを圏(モノイド圏である必要はない)とすると、自己関手と自然変換の圏 End(D) は、関手の結合を(非対称な)モノイド積としてモノイド圏となります。すぐ上の主張のEを End(D) に置き換えると:

  • ラックス・モノイド関手 F:C→End(D) は、Monoid(C)→Monoid(End(D)) を誘導する。

Monoid(End(D)) = Monad(D) なので、

  • ラックス・モノイド関手 F:C→End(D) は、Monoid(C)→Monad(D) を誘導する。

さらに、次の記事で述べたフォークロを考慮しましょう。

Dがモノイド圏C上の加群圏になっていると、その加群構造からラックス・モノイド関手 H:C→End(D) を構成できます*1。これから、Monoid(C)→Monad(D) を作れます。つまり、

  • Dがモノイド圏C上の加群圏ならば、C内のモノイドは、D上のモナドを誘導する。

モノイド圏Cは、自分自身の上の加群圏であることから、

  • モノイド圏C内のモノイドは、C上のモナドを誘導する。

これが「モナド工場の秘密(オリジナル版)」でした。C内のモノイドが、異なる圏D上のモナドを誘導するという事実は、パワーアップしたモナド工場を与えることになります。

パワーアップ・モナド工場の実例をひとつ挙げましょう。

上記の記事で説明した状況で、コンパクト測度空間の圏CompMSはモノイド圏で、その反対圏CompMSopもモノイド圏です。うまいこと定義すると、バナッハ空間の圏Banはモノイド圏CompMSop上の加群圏になります。よって、“CompMSop内のモノイド=CompMS内のコモノイド”は、バナッハ空間の圏Ban上のモナドを定義します。CompMSには、対角射を余乗法とするコモノイドがたくさん(対象の数だけ)あります。モノイド圏ではないBan上のモナドを大量生産できました。[追記]CompMS側をちょっと細工する必要がありますね。でも、大筋はこれでいいかと。[/追記]

*1:実際は、Hは強モノイド関手になります。強モノイド関手はラックス・モノイド関手の特別なものなので、特に問題はありません。

akameakame 2016/08/16 14:16 はじままして。
少しお聞きしたいことがあります。
檜山の記事で「基本圏」を紹介されていたと思いますが、「基本圏」が紹介されている文献などはありますか?

m-hiyamam-hiyama 2016/08/16 16:56 akameさん、
基本圏? あー、http://d.hatena.ne.jp/m-hiyama/20111128/1322438761 で触れたことがありましたね。
"fundamental category"とか"fundamental groupoid"で検索すれば、文献は引っかかりますよ。nLabの該当エントリーから、Related conceptsとReferencesをたどっていくのが良いかと思います。

sasahara@mb.point.ne.jpsasahara@mb.point.ne.jp 2016/08/17 16:57 バナッハ空間の圏ってテンソル積を完備化してモノイド圏にできるんじゃ?

m-hiyamam-hiyama 2016/08/18 10:40 sasaharaさん、
出来そうですね。出来たら色々嬉しいこともあります。
ですが、今回の話とは関係ありません。Banのモノイド構造はあっても使わないので。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20160809

2016-08-05 (金)

コンピュータ科学や組み合わせ論を“微分幾何”とみなす:CADGの夢

| 09:55 | コンピュータ科学や組み合わせ論を“微分幾何”とみなす:CADGの夢を含むブックマーク

『シン・ゴジラ』僕のツボにはまったんですよね。コワ面白かった! 最近、もうひとつ「これは面白い!」と思っていることがあります。微分幾何の応用の話です。多くの人が「応用」という言葉から連想する内容とはちょっと違います。微分幾何を換骨奪胎して、その枠組を、微分とも幾何ともまったく無関係と思える分野にも適用するのです。

微分とも幾何ともまったく無関係と思える分野」には、コンピュータ科学や組み合わせ論が含まれます。これには驚きました。好奇心を刺激されて、しばらく猿になって調べまくってました。

調べても理解できないことがたくさんあるので、断片的で中途半端な知識を推測(妄想?)でつなぎ合わせるという手法(いつものやり口)で語ってみます。圏と多様体の定義くらいは仮定しますが、それ以外の知識は要求しないオハナシ調です。

内容:

  1. リソース計算が微分計算だってぇぇ?!
  2. 微分の計算が出来る圏
  3. 組み合せ論とデータ構造の理論
  4. 伝統的微分幾何へ
  5. なめらかさ
  6. 圏論的抽象微分幾何=CADG
  7. カリー/ハワード/ランベック対応
  8. CADGのこれから

リソース計算が微分計算だってぇぇ?!

ラムダ計算をご存知でしょうか? ラムダ計算はコンピュータ科学において重要な位置を占めます。関数型プログラミング言語は、すべからくラムダ計算の影響を受けています。関数型とは言いがたいプログラミング言語(例えばJavaC++)でさえ、最近はラムダ式(ラムダ計算の表現法)をサポートしています。

1993年、ボードル(Gérard Boudol)は、多重度付きラムダ計算という“ラムダ計算の変種(バリアント)”を提案しました。

多重度付きラムダ計算は後〈のち〉にリソース・ラムダ計算(resource lambda-calculus)、あるいは単にリソース計算(resource calculus)と呼ばれるようになります。リソースとは、現実世界の物品のように、使いたいなら生産する必要があり、消費すればなくなり、破棄にもコストがかかるモノです。ボードルのリソース・ラムダ計算は、“リソースを引数に受け取る関数”の計算体系です。

21世紀に入ってすぐに、また別種のラムダ計算が登場します。エラア/レギエ(Thomas Ehrhard, Laurent Regnier)による微分ラムダ計算(differential lambda-calculus)です。

スコット(Dana Scott)などの手法により、計算可能関数はある位相空間上の連続関数とみなせます。この連続関数を多項式関数(のようなもの)で近似できないか? というのが動機だったようです。計算可能関数=連続関数=微分可能関数というフィクショナルな仮定のもとで、テイラー展開により多項式近似ができます -- そこで、ラムダ計算に微分概念を導入しよう、と。たぶんそんな感じ。

リソース・ラムダ計算にも微分ラムダ計算にも、ジラール(Jean-Yves Girard)の線形論理の影がちらついているので、両者の類似性に気付いていた人はいたでしょう。が、リソース・ラムダ計算と微分ラムダ計算の関係に決着が付くのはさらに10年ほど(ボードルからは20年ほど)たってからです。

マンゾネット(Giulio Manzonetto)は、リソース・ラムダ計算と微分ラムダ計算のあいだの構文的変換を構成すると共に、両者に共通なモデルを与えます。モデルとは、ラムダ計算の形式的・記号的な式や手順に対する実体的な意味のことです。

つまり、リソース・ラムダ計算と微分ラムダ計算は、構文は違えども、その意味するところは同じだったのです。

微分の計算が出来る圏

リソース・ラムダ計算と微分ラムダ計算が共通に「意味するところ」とは何なのでしょう? マンゾネットが使ったモデル(「意味するところ」)は、ブルート/コケット/シーリー(Richard Blute, Robin Cockett, Robert Seely)が定義していたデカルト微分(Cartesian differential categories)です。

デカルト微分圏は、デカルト圏(直積がある圏と思えばいいです)であり、射に対する微分が行える圏です。圏Cの射 f:A→B に対して、その微分 D[f] が圏C内の射として確定します。f |→ D[f] という対応が組み込まれている圏がデカルト微分圏です。

D[-] は微分作用素(differential operator)ですが、ここではラムダ計算の習慣に従い微分コンビネータ(diffrential combinator)と呼びましょう。この微分コンビネータは、微分計算に必要な道具と法則を抽象化したもので、チェーンルール(合成関数の微分公式)や偏微分と全微分との関係などが微分コンビネータの公理になっています。高校から大学教養で習う程度の微分計算は、微分コンビネータとその性質を使ってだいたいは出来ます。

デカルト微分圏を解析学入門の教材に使うのは、準備に時間がかかり過ぎるので、教育的に良い選択とは言えないでしょう。しかし、デカルト微分圏の内実解析学入門として特に違和感がないものです(記法や理論構成には違和感があるでしょうが)。

不思議なのは、解析学入門的な構造を持つデカルト微分圏が、解析学とはまったく無関係なリソース・ラムダ計算のモデルにもなることです。これは、リソース・ラムダ計算に特有な稀な現象なのでしょうか?

組み合せ論とデータ構造の理論

1986年、圏論の専門家であるジョイアル(André Joyal)は、組み合わせ論(combinatorics)で扱う離散構造(ツリー、グラフなど)の圏論的な定式化として組み合わせスピシーズ(combinatorial species)を導入しました。

組み合わせ的構造の表現であるスピシーズには、足し算・掛け算などの演算が定義できますが、それだけでなく、スピシーズの微分(derivation)が出来ます。

ジョイアルの原典は古いフランス語論文なので、フィオレ(Marcelo Fiore)の論文を引用しておきましょう。一般化されたスピシーズと、微分を含む種々の計算が解説されています。

ジョイアルのアイディアはプログラミングにも応用できます。

プログラミングでは、アルゴリズムと共にデータ構造が重要です。リスト、二分木、多次元配列などは典型的なデータ構造です。これらのデータ構造(のインスタンス)は、なんらかの形状(shape)を持ち、その形状のなかの“場所”に基本データを割当てて構成されます。「形状 + 場所 + 基本データ」で構成されるデータ構造をコンテナ(container)と呼びます。

コンテナは、関手(container functor)として定式化することが出来て、それらの関手の微分(differentiation/derivation)を定義可能なのです。これは、ジョイアルによる解析関手の微分*1(derivatives of alytic functors)をコンピュータ科学の文脈で再現・発展させたものです。コンテナの微分を簡潔に解説したものとして、次の論説があります。

スピシーズやコンテナの事例は、離散的・組み合わせ的構造のなかにも微分概念が潜んでいることを示唆します。デカルト微分圏やその一般化には、種々の微分概念に対する統合フレームワークとしての役割が期待されています。

伝統的微分幾何へ

話はまだ続きます。解析学入門(初等的な微積分)の次は何を学ぶでしょうか。色々な方向性があるでしょうが、有力な候補として多様体微分幾何(differential geometry of manifolds)があります。

微分幾何を展開するなら、多様体はなめらか(smooth)である必要があるので、単に多様体と言ったら“なめらかな多様体”のことだとします。また、「なめらか」と「C(無限回微分可能)な」は形容詞としてまったく同義として使います。

題名に「微分幾何」と付いている教科書で扱う内容は、(なめらかな)多様体の理論だと言っていいでしょう。この分野を伝統的微分幾何*2(traditional differential geometry)と呼ぶことにします。形容詞「伝統的」を付けたのは、非伝統的な微分幾何も扱う予定だからです。

さて、前節で紹介したデカルト微分圏という概念装置は、伝統的微分幾何を包摂しうるでしょうか? この問を言い換えると、なめらかな多様体の圏をC-Manとするとき*3C-Manデカルト微分圏であるか? となります。

答はNoです。圏C-Manデカルト微分圏(の実例)ではありません。もし、圏論的定式化により伝統的微分幾何まで扱いたいなら、別な手法が必要なのです。

実は、随分と以前に、伝統的微分幾何の圏論的定式化に手を付けた人がいます。

上記論文でロシツキー(Jiri Rosicky)が示した先駆的アイディアは、ほぼ30年間かえりみられなかったようです。2010年代に入って、コケット(Robin Cockett)とクラットウェル(Geoffrey Cruttwell)がロシツキーの手法を発展させます。その結果が公表されたのは、ロシツキー論文からちょうど30年後の2014年です。

  • Title: Differential structure, tangent structure, and SDG
  • Authors: Cockett, R. and Cruttwell, G.
  • Journal: Applied Categorical Structures, 22 (2), pg. 331–417, 2014.

この論文はWeb上で入手できないようです*4が、今年の6月末(June 28, 2016)にarXiv.orgに投稿された次の論文からだいたいの内容は想像できます*5

  • Title: Differential bundles and fibrations for tangent categories (2016)
  • Authors: J.R.B. Cockett, G.S.H. Cruttwell
  • Pages: 58p
  • URL: https://arxiv.org/abs/1606.08379

接構造(tangent structure)を持つ圏 -- 接圏(tangent category)が、伝統的微分幾何の再定式化を与え、同時に非伝統的微分幾何をも射程に収めるフレームワークです。

なめらかさ

デカルト微分圏と接圏、そしてそれらの変種や拡張が幾つか提案されています。しかし、定義や用語法はまだ未整理で、若干の混乱も見受けられます。提案されている複数の圏(むしろ、圏の種別=ドクトリン)を大分類するために、微分コンビネータ付き圏(category with differentical combinator)と接構造付き圏(category with tangent structure)という言葉を使うことにします。

微分コンビネータと接構造は、「なめらかさ」を定義する2つの方法です。それぞれ、「なめらかな関数は、なめらかな微分導関数)を持つ」「なめらかな曲線は、なめらかに変動する接線族を持つ」という常識的見解を圏論的に定式化したものです。

圏論的定式化においては、「なめらかな関数(写像)とは何か?」「なめらかな図形(多様体)とは何か?」という問に答えることを放棄している点に注意してください。関数や図形がなめらかさを担うのではなくて、なめらかさは圏に付与される構造・特性です。個々の構成員ではなくて、社会・組織全体により「なめらかさ」が具現されるわけです。

これは、現代の線形代数が「ベクトルとは何か?」という問に答えることを放棄しているのと同じ事情です。ベクトル空間の要素を便宜上「ベクトル」と呼ぶだけで、ベクトルの正体はどうでもよいのです。注目すべきはベクトル空間のほうです。

同様に、なめらかな圏の対象を「なめらかな多様体」、射を「なめらかな写像」と呼ぶだけで、その正体はどうでもよいのです。注目すべきはなめらかな圏です。そして、なめらかな圏の定義法として、微分コンビネータ付き圏と接構造付き圏があるわけです。

対象や射が具体的に何であるかを問題にしないことは、非伝統的微分幾何を展開するうえで本質的です。例えば、リソース・ラムダ計算のモデルとして使われたMRelと呼ばれる圏の対象は、位相も何も持たない単なる集合です。しかし圏MRelなめらかな構造を持つので、MRelの対象を「なめらかな多様体」と呼んで差し支えないのです(無理にそう呼ぶ必要はありませんが)。

圏論的抽象微分幾何=CADG

微分コンビネータ付き圏が接構造付き圏になることは分かっています。そして、接構造付き圏により伝統的微分幾何がかなりの程度再現(recover)できることも分かってきました。まだ輪郭はハッキリとしないものの、新しい分野が立ち上がりつつあると言えるでしょう。先走ってこの分野に名前を付けてしまいましょう。

  • 圏論的抽象微分幾何(Categorical Abstract Differentical Geometry*6 : CADG)

圏論的(特にトポス論的)な微分幾何は既に存在します。SDG(synthetic differential geometry)やC-schemeはそのようなものです。しかしこれらは、伝統的微分幾何のニュースタイルという趣であり、ジャンル内にとどまっている点においては保守的です。

一方、CADGの特徴は、非伝統的な微分幾何を射程に入れていることです。例えば、コケット/クラットウェルは、非伝統的応用を考慮してベクトル空間の使用をやめて、可換モノイドにまで一般化しています。そのため、伝統的微分幾何の引き写しではうまくいかないことも多いのです。

従来の論法が使えない状況において、クラットウェルは微分形式の外微分計算をしています。

今年(2016年)になってクラットウェルは、ド・ラーム・コホモロジーまで定義しようとしています(2013年の微分形式とは違った方法を使っているようです)。

  • Title: A simplicial foundation for de Rham cohomology in tangent categories (29 Jun 2016)
  • Authors: G.S.H. Cruttwell, Rory B. B. Lucyshyn-Wright
  • Pages: 52p
  • URL: https://arxiv.org/abs/1606.09080

これらのことから、CADGは空疎な枠組ではなくて、幾何的内容(geometric content)を含んでいるように思えます。

カリー/ハワード/ランベック対応

コンピュータと論理の界隈では、カリー/ハワード対応という教義があります。教祖をもう一人増やして、カリー/ハワード/ランベック対応(Curry-Howard-Lambek correspondence)と呼ぶこともあります。この教義によれば、「ラムダ計算、論理、圏」の三者は聖なるトリニティ(三位一体)を形成することになります。

最も基本的なトリニティは、「単純型付きラムダ計算、連言・含意を持つ命題論理、デカルト閉圏」から成るものです。他にも、カリー/ハワード/ランベック対応には色々な拡張・変種があります。

今我々が気になることは、微分トリニティが存在するかどうかです。微分ラムダ計算とデカルト微分圏との対応は既に確立されていると言ってでしょう。では論理は? 微分論理? って、それ何だ?

微分論理」という言葉を使っている人がいないわけではありません。例えば、次のレアード(Jim Laird)のスライド。

なんかあまりピンと来ません。論理として、分かりやすく説得的な解釈があるといいんですけどね。僕は、カリー/ハワード/ランベックの信奉者なので、いずれはハッキリとした微分論理が登場すると期待してます。

CADGのこれから

「CADGとは何であるか/何であるべきか」をまとめておくと: 「なめらかさ」を圏上の接構造(tangent structur)として捉えることにより、微分幾何的手法を広い範囲に適用する試み、となるでしょう。

これからやるべきことは:

  1. CADGの基礎をかためる。
  2. 広く浅く、非伝統的な事例を探索する。
  3. 狭く深く、伝統的微分幾何を再構成する。

あたりでしょう。

歴史が浅い分野なので、まだトッ散らかっています。定義の方法、公理の選び方、理論の組み立て方などは荒削りなので、整理して体系化する必要があるでしょう。それが基礎がためです。

現在、ラムダ計算、データ構造/データ型、組み合わせ論、論理などへの応用(適用)はされつつありますが、もっと多くの適用例が見つかると楽しいですね。物理や工学への応用があると説得力が増すでしょう。個人的には、形式言語理論/オートマトンの理論に応用できたら嬉しい(見通しはないけど)。

この記事の前のほうで「デカルト微分圏を解析学入門の教材に使うのは、準備に時間がかかり過ぎるので、教育的に良い選択とは言えない」と書きましたが、時間をかけてもいいのなら、教育の方法としても意外にイケる気がします。形式的計算で言えることと、解析学固有の議論を要することが、ハッキリと切り分けられるメリットがあります。

CADGの適用分野には、当の伝統的微分幾何も含まれます。幾何学的公理を付け加えることにより、「どこまで伝統的微分幾何を再現できるか?」は興味深い課題です。ベクトル場、微分形式、接続(共変微分)あたりの再現です。CADGとは無関係に、プロパーな幾何学の文脈で“圏上の接構造”を使っている例もあります。「接関手の上のモナド」で紹介したジャビン(Benoît Jubin)の論文はその例です。こういう動きもCADGに取り込めるかも知れません。

CADGを使って幾何学として新しいことが出来る望みは薄いと思います。しかし、伝統的微分幾何はCADGの本家であり、本家の概念や手法を他分野に輸出することを可能とするのがCADGフレームワークです。であるなら、本家における有効性をある程度は検証しておく必要があります。

現時点では、CADGの意義や将来性は何とも言えません。フレームワークだけでは有り難みが薄いので、アプリケーションがどれだけ出るか、が鍵でしょう(ソフトウェアと同じだな)。まー、好奇心と興味の対象としては今でも十分に面白いですけどね。

*1:derivative of a functor を導関数に似せて「導関手」と呼びたいところですが、導来関手(derived functor)と紛らわしいのでやめておきます。

*2:古典微分幾何(classical differential geometry)という言葉もよく使われます。

*3:過去の記事「微分のチェーンルール」や「接関手の上のモナド」では単にManと書いた圏です。

*4:マウント・アリソン大学(http://www.mta.ca/)のクラットウェルのページが消失しているようです。

*5[追記]スライドはありますね。http://www.mathstat.dal.ca/~selinger/fmcs2012/slides/FMCS2012-Cruttwell.pdf このスライドからも概要は分かるでしょう。[/追記]

*6:"abstract differential geometry"という言葉が使われた事例はありますが、広く認知された用語ではないようなので、ここで使いました。

2016-08-03 (水)

『シン・ゴジラ』を観た

| 09:29 | 『シン・ゴジラ』を観たを含むブックマーク

映画『シン・ゴジラ』を観ました。僕が感じたことは2つ。

  1. これは怖い。
  2. (他人事ながらも)ほっとした。

ネタバレは、たぶんありません。つうか、あらすじ書いたりするの面倒だからヤラン。

まず、「(他人事ながらも)ほっとした」話。これはね、監督・特技監督・樋口真嗣さん、総監督・庵野秀明さん、東宝の関係者の皆さん、-- まったく接点も何もない赤の他人なんですが、それでも、「よかったですね」と思うわけです。

去年の夏『進撃の巨人』を観ましたが、あまり出来はよくなくて、世間の評判もサンザン。樋口監督やスタッフが大人げない行動をやらかしちゃったし。興行収入もきびしかったでしょう。

東宝としては、『進撃の巨人』は『シン・ゴジラ』への助走のような意味合いもあったでしょう。それがコケちゃったから、『シン・ゴジラ』も不安だなー、的な空気もあったんじゃないか、と想像します。封切り(7月29日)の前後は、関係者はキリキリと胃が痛む思いだったんじゃないか、と想像します。

今回東宝は、製作委員会方式をとらず単独制作。いわば「社運をかけた」作品。これがコケたら、誰がどう責任とるんだろう? 他人事だけどさー、想像しただけでコッチも胃が痛くなっちゃいます。

いやほっとしました。ということは、間違いなくヒットするだろうと確信できる出来。万人にとって面白い映画はないので、批判の論点は諸々あるでしょうが、常識的に言えば傑作ですよ。日本映画と言わず、世界の水準でみても高い評価を得られるでしょう。

世界的なヒットも期待できると思います。ですが、やはりこれは日本人に刺さる要素が多いので、他の国の人が観ても我々のような感慨を抱くだろうか? たぶんそれはない。そこまでの普遍性はない気がします。

たいていの方が指摘するように、東日本大震災と福島第一原発事故、あれを経験していますからね、我々は。最近の熊本地震を重ねる人もいるでしょう。『シン・ゴジラ』は特撮SF怪獣映画じゃなくて、パニック映画/災害映画です。僕のように直接被災をしてない者でも身につまされるものがあります。

パニック映画/災害映画としての出来の良さ、迫力が「これは怖い」という感想につながります。ゴジラの造形が怖い、という人もいます(実際そうです)が、もう存在自体が怖い。まったく愛嬌がない、災厄そのものです。

映画は主に政府と自衛隊の災害対応を描くわけですが、そこでのやり取りがどれ程リアルなのか、僕には分かりません。が、素人目には十分リアルに写ります。東宝怪獣映画では定番の“メーサー兵器”も登場せず、実在の(と思われる)重火器で攻撃するもまったく歯が立たない。切ないくらいに役立たず。逆に言えば、ゴジラが人智を超えて強い。破壊と殺戮がまったく容赦無いのです。

ゴジラは、いちおう生物という設定ですが、感情がない。意図もない。ほぼ機械的な本能だけ。実際の災厄というものはそういうものです。だから怖いのです。

東日本大震災3.11の夕方のニュースで、水と土の膨大な塊が田畑や家を押し潰しながら進行する映像を見ました。そのとき、家から火の手があがっていました。見たこともないし、想像もしたことがない状況。水と土に、さらに火。これがもしフィクションの一場面なら、「作り過ぎだろう、これ」と言いたくなるような映像。でも、それは実際の映像でした。

そんな記憶が残っている僕(たぶん多くの人)にとっては、作り物の映像にも「もしかしたら、あるかもしれない」という「怖さ」が押し寄せます。結果、娯楽としてのカタルシスには欠けるのですが、悲観的なラストではないので、観終わって落ち込むことはありません。僅かですがコメディ要素もあります*1。観て損はない傑作です。


[追記 date="翌日"]

事前情報は仕入れずに行ったのですが、後から「みなさん、どう思っているのかな?」と検索したら、やはり好評ですね。不満・批判は「あれが描かれてない」が多いみたい。でも、あれ以上の詰め込みは無理のような。

僕の一番の高評価ポイントは、専門家でない観客にはリアリティが感じられたところです。ですから、「理由が分からないままにゴジラは東京湾に去って行き、その後行方が知れず」というエンドであったとしても(まったくスッキリしないけど)映画としての評価はさほど下がらなかったと思います。むしろ、作戦が成功するほうが超ラッキー。

リアルっぽい災害シミュレーションにミッション遂行を主軸とするなら、家族や男女の愛情、一般の人々の思いや行動、民間企業の頑張り、ゴジラ誕生の秘密 … などを盛り込むのは無理があるし、散漫で中途半端になるでしょう。

お笑い担当のコメディエンヌは、リアリティをぶち壊していたけど、可愛いからあれでいいです。

[/追記]


[さらに追記]

[/さらに追記]

*1:ゴジラで1回、人間で数回笑いました。ギャグっぽい場面は夾雑物だと感じる人もいるでしょうが、シリアスになり過ぎないためにある程度のオチャラケはあったほうがいいと僕は思います。

内海内海 2016/08/03 09:53 私も昨日IMAXで観賞して来ました。仰る通り怪獣映画というより一級品のディザスタームービーですよね。 感情描写がほぼ無い巨大災害に近いゴジラにこちらも感情的な対立構造や恋愛描写をほぼ削ぎ落とした政府組織が立ち向かう物語が、 最近のハリウッド映画でいうと 「オデッセイ」 の様な 「頭の良い登場人物全員がベストを尽くす事で困難なミッションを達成する」 系の話としてキチンと成立していたと思います。 ただやっぱり物語としてのカタルシスはちょっと足りないかなと (^_^;) 最後の展開も在来線使ったアレは良かったけど、 あの注入作業も割とスムーズに進んでしまって感情の引っ掛かりが無さ過ぎると思うんですよね。 基本メインの登場人物もあの時ただ見守る事しかやってないし (ハリウッドならあそこはポンプ車のバルブが途中で外れて主人公が命懸けでそのバルブを自力で繋ぎに行く展開にしそうだから一長一短だけどw)

m-hiyamam-hiyama 2016/08/03 11:59 内海さん、
全体の2/3くらい見た段階で、「スカッと終わってくれ」とはまったく思いませんでしたね。「これ以上被害が拡大しないように」とか、「なんとか終息してくれ」です。なので、後半1/3は、どんなダサい作戦でも目的(事態の終息)を達すればあんまり不満はなかったですね、僕は。
> 主人公が命懸けでそのバルブを自力で繋ぎに行く展開
むしろ、秘密兵器やヒーローが登場するとゲンナリだったでしょう。あれは、まーまーバランスのとれた終わり方だったと思います。
ちょっと不満は、ビームかな。ファンサービスで見せ場かも知れないけど、「そこまで強くする必要ないだろう」と。

2016-08-01 (月)

又吉イエスさんによる大川隆法批判

| 09:25 | 又吉イエスさんによる大川隆法批判を含むブックマーク

今回は出馬しないのかな」で引用した又吉イエスさんの大川隆法批判(動画):

とても面白い意見なので冒頭部分(この部分だけで十分)を文字起こししました。

「天地を創造された地球至高神は大川隆法・総裁先生だ」に対する又吉イエスさんのコメント:

それはまったく嘘でしょう。
宇宙万物を創り、人類を創造したのが、この再臨のキリスト・唯一神又吉イエスです。
ですから、大川隆法がそんなことをしたという事実はまったくありません。
これは嘘つきなんですよ、そんなこと言うならですね。
彼は、なんですか、釈迦の再臨であるとか(苦笑/嘲笑)色んなこと言っています。
少し頭がどうかしているんですよ。
トラックバック - http://d.hatena.ne.jp/m-hiyama/20160801

2016-07-28 (木)

ツリー書き換え系とマックレーンの一貫性定理

| 11:36 | ツリー書き換え系とマックレーンの一貫性定理を含むブックマーク

モノイド圏に対するマックレーンの一貫性定理(Mac Lane's coherence theorem for monoidal categories)は有名なんですが、それが主張する内容を把握しづらい定理です。同値な内容を様々な形で述べることができます。ここでは、ツリー書き換え系との関係でマックレーンの一貫性定理を定式化してみます -- この形でも謎な感じは払拭できないのですが、応用には便利な形になります。

なお、この記事は、「自然演繹の再構築への道」で述べた計画の一部です。

内容:

  1. マックレーンの一貫性定理
  2. 定式化の概要
  3. 二分木
  4. 二分木の基本変形
  5. 二分木のパスと部分ツリー
  6. ツリーの単純書き換え
  7. ツリー書き換えの圏
  8. 評価関手
  9. 単純ツリー書き換えの評価
  10. ツリー書き換えによるマックレーンの一貫性定理の記述

マックレーンの一貫性定理

マックレーンの一貫性定理については、nLabのエントリーがあります。

このnLabエントリーには、6種類の形で定理が述べられています。証明は別なエントリーにあります(2016年7月時点では一部未完)

ここでは、MITのテンソル圏のコース講義資料にある次の形を採用します。

Let X1, ..., XnC. Let P1, P2 be any two parenthesized products of X1, ..., Xn (in this order) with arbitrary insertions of unit objects 1.

Let f, g : P1 → P2 be two isomorphisms, obtained by composing associativity and unit isomorphisms and their inverses possibly tensored with identity morphisms.

Then f = g.


X1, ..., Xn をモノイド圏Cの対象とする。P1, P2 は、X1, ..., Xn 達を掛け算(モノイド積)して得られる対象とする。掛け算は括弧により優先順位が曖昧性なく指定されていて、X1, ..., Xn がこの順で出現しなくてはならない。また、モノイド単位1が因子として適当に挿入されることを許すとする。

f, g : P1 → P2 は2つの同型射とする。これらの同型射は、結合律子、左単位律子、右単位律子、それらの逆、恒等射を、射の結合とモノイド積で組み合わせたものとする。

上記の設定で、f = g が成立する。

元の講義資料では、一貫性定理を、「任意のモノイド圏には厳密化(strictification)が存在する」ことを仮定して証明しています。厳密化は、ひとつ前の講義資料において、モノイド圏Cの自己関手圏End(C)への巧みな“表現”を構成することで示しています。

厳密化に関する別な議論として:

ブレイド付きモノイド圏の場合の概要は:

定式化の概要

ここでやることは、マックレーンの一貫性定理の表現方法を多少変えるだけです。Cが与えられたモノイド圏として、別な圏Bと、Bからの関手 F:BC を構成します。関手Fの像として得られる部分圏 B'⊆Cやせた圏である、という主張がマックレーンの一貫性定理となります。

Bは、完全に組み合わ的/帰納的に構成します。圏Bの対象は、二分木です。そして、圏Bの射は、ツリー(二分木)の書き換え(rewriting)です。関手Fは、ツリーを式とみなしての評価写像(evaluator)になります。

このような形にすると、「式に、その計算結果である値を対応させる」という、プログラミング言語ではお馴染みの意味論になります。見慣れた形ならば、幾分かは分かりやすく親しみやすいのではないか、と思うわけです。

二分木

Wを集合として、i∈W が特定されているとします。iを含むのでWは空ではありません。W = {i} が最小のケースです。Wの要素をリーフ(葉、末端)とする二分木(binary tree)は、次のように帰納的に定義されます。

  1. Wの要素は二分木である。
  2. s, tが二分木ならば、(s∧t) は二分木である。
  3. 以上により定義されるものだけが二分木である。

Wから作られた二分木全体の集合を BinTree(W) とします。

W = {i, a, b} のとき、(a∧((a∧b)∧i)) は二分木(BinTree(W)の要素)の例です。∧は、ここでは論理ANDではなくて、下の図のようなツリーの形状に似せた記号です。双子サクランボの枝の形ですね。

リーフノードはWの要素ですが、「ノードのラベルとしてWの要素を使っている」とみなしてもかまいません。Wをラベル集合と解釈するなら:

  • リーフノードは、Wの要素でラベル付けされている。
  • リーフではないノードにはラベルが付いてない。
  • ラベルが付いたリーフノードが1個だけでも(特殊な)ツリーとみなす。

リーフでないノードをブランチノードと呼ぶことにします。

ツリー(二分木)を図示する場合は、リーフノードはWの要素として書き、ブランチノードは無名のドットで表します。ブランチノードは、必ず左の子ツリーと右の子ツリーを持ちます。

二分木の基本変形

s, t, p, q, r などはBinTree(W)の要素、つまり二分木を表すとします。ある形状の二分木が与えられたとき、それを別な二分木に変形する操作を考えます。その変形操作を列挙しましょう。

  1. 左スイッチ: ((p∧q)∧r) → (p∧(q∧r))
  2. 右スイッチ: (p∧(q∧r)) → ((p∧q)∧r)
  3. iの左削除: (i∧p) → p
  4. iの左挿入: p → (i∧p)
  5. iの右削除: (p∧i) → p
  6. iの右挿入: p → (p∧i)

左スイッチは「左のブランチノードを右へスイッチする」の意味です。6つの操作に略称を付けておきます。

名前 略称 適用可能なツリー
左スイッチ LSw ((p∧q)∧r) の形のツリー
右スイッチ RSw (p∧(q∧r)) の形のツリー
iの左挿入 LIns 任意のツリー
iの左削除 LDel (i∧p) の形のツリー
iの右挿入 RIns 任意のツリー
iの右削除 RDel (p∧i) の形のツリー

これら6つの操作をツリー(二分木)の基本変形と呼びましょう。LSw←→RSw、LIns←→LDel、RIns←→RDe は互いに逆になっています。これを考慮して基本変形を絵に描くと、次のようです。

基本変形をBinTree(W)からBinTree(W)への部分写像と考えて、すぐ上で約束した略称を写像の名前として使います。例えば、LSwは BinTree(W)→BinTree(W) という部分写像です。部分写像はまた、BinTree(W)→(BinTree(W) + {⊥}) という写像と考えることもできます。ここで、⊥は未定義を意味する特殊な値です。

これらの基本変形は、結合律子(associator)、左単位律子(left unitor)、左単位律子(right unitor)を組み合わせ的に表現したものです(律子(りつし)に関しては「律子からカタストロフへ」を参照してください)。

二分木のパスと部分ツリー

二分木内のノードを正確に指し示すために、ツリーのパスを考えましょう。パスは、{1, 2}*の要素だとします。{1, 2}*の要素は、数字1か2を並べた列ですが、コンピューター屋さんの風習に従って、あいだにスラッシュ(/)をはさみます。また、先頭にもスラッシュを付けることにします。すると、空列は /、121は /1/2/1 となります。1が左、2が右を表すと約束します。

BinTree(W)の要素である二分木tを、Wをラベル集合とするラベル付きツリーと考えて、パスξの位置のノードラベルを label(t, ξ) と書きます。labelは、BinTree(W)×{1, 2}*→(W + {⊥}) という写像になります。

t = (a∧((a∧b)∧i)) のとき、

  • label(t, /) = ⊥
  • label(t, /1) = a
  • label(t, /2) = ⊥
  • label(t, /2/1) = ⊥
  • label(t, /2/2) = i
  • label(t, /2/2/1) = ⊥
  • label(t, /2/1/1) = a
  • label(t, /2/1/2) = b

ツリーの特定のノードを指定すると、そのノードと子孫達からなるサブツリーが決まります。これを、subtree(t, ξ) と書くことにします。

subtreeは、BinTree(W)×{1, 2}*→(BinTree(W) + {⊥}) という写像になります。

先と同じく t = (a∧((a∧b)∧i)) なら、

  • subtree(t, /) = (a∧((a∧b)∧i))
  • subtree(t, /1) = a
  • subtree(t, /2) = ((a∧b)∧i)
  • subtree(t, /2/1) = (a∧b)
  • subtree(t, /2/2) = i
  • subtree(t, /2/2/1) = ⊥
  • subtree(t, /2/1/1) = a
  • subtree(t, /2/1/2) = b

ツリーの単純書き換え

与えられたツリーを別なツリーに書き換えるステップを単純書き換え(simple rewrite/rewriting)と呼びましょう。以下に正確な定義を書いていきます。

単純書き換えは次のもので構成されます。

  1. 二分木t (t∈BinTree(W))
  2. パスξ (ξ∈{1, 2}*
  3. 基本変形u (u∈{LSw, RSw, LIns, RIns, LDel, RDel})

これらは次の条件を満たすとします。

  1. subtree(t, ξ) が定義されている(つまり、subtree(t, ξ) ≠ ⊥)。
  2. subtree(t, ξ) にuを適用可能である。

この条件が成立しているなら、u(subtree(t, ξ)) が定義できます。例えば、

  • t = (a∧((a∧b)∧i))
  • ξ = /2
  • u = RDel

のとき、

  • subtree(t, ξ) = subtree(t, /2) = ((a∧b)∧i)

となり、これにRDelを適用可能であり、

  • u(subtree(t, ξ)) = RDel(subtree(t, /2)) = RDel(((a∧b)∧i)) = (a∧b)

です。

tにおけるsubtree(t, ξ)を、u(subtree(t, ξ))で置き換えた結果を subst(t, ξ, u) とします。例えば、

  • subst((a∧((a∧b)∧i)), /2, RDel) = (a∧(a∧b))

となります。

ツリーtの単純書き換えは、t, ξ, u で決まりますが、書き換え(部分ツリーの置換)の結果である t' = subst(t, ξ, u) も一緒にして、[t, (ξ, u), t'] の形にします。この記法の意味は次のとおりです。

  • ツリーtにおいて、パスξで指定されるサブツリーを基本変形uにより書き換えた結果はt'である。

ツリー書き換えの圏

ツリーtの単純書き換えを [t, (ξ, u), t'] の形で表しましたが、これを一般化して次の形式を考えます。

  • [t0, (ξ0, u0), t1, ..., tn-1, (ξn-1, un-1), tn]

ここで、0≦i<n に対して [ti, (ξi, ui), ti+1] は単純書き換えになっているとします。

この形のリストは、長さが 3, 5, 7, ... と奇数になりますが、ツリーtだけを含む長さ1のリスト [t] も一緒に考えることにします。

今説明した形のリストをツリーの書き換え(rewrite, rewriting)と呼びます。ツリーの書き換えは、ツリーの単純書き換えの列です。ツリーの書き換えを表すリストは長さが 2n + 1 です。n = 0 のときは [t] の形、n > 0 なら、[t0, (ξ0, u0), t1, ..., tn-1, (ξn-1, un-1), tn] の形をしています。nを、書き換えのステップ数(number of steps)と呼ぶことにします。nステップ(n > 0)の書き換えを [t0, ..., tn] のように略記していいとします。

さて、ツリーの書き換えを射とする圏を作りたいのですが、しりとりの圏と大差ないのでサッサと進めます。

Wは特定元iが指定された集合として、圏BTRWを次のように定義します。

  1. 対象の集合は、Obj(BTRW) = |BTRW| = BinTree(W) とする。
  2. 射の集合は、Mor(BTRW) = (BinTree(W) に属するツリーを書き換える書き換え全体の集合)とする。
  3. 域は、dom([t]) = t、dom([t0, ..., tn]) = t0 と定義する。
  4. 余域は、cod([t]) = t、cod([t0, ..., tn]) = tn と定義する。
  5. 結合は、しりとり結合と同じ。
  6. 恒等射は、idt = [t]

これらのデータから実際に圏が出来るのを確認するのは容易です。

BTRWの射は、ステップ数がn(n≧0)のツリー書き換えすが、それはn個の単純ツリー書き換えの結合として一意に表すことができます。つまり、射の結合演算子を「;」として、次の等式が成立します。

  • [t0, (ξ0, u0), t1, ..., tn-1, (ξn-1, un-1), tn] = [t0, (ξ0, u0), t1];...;[tn-1, (ξn-1, un-1), tn]

評価関手

次に、圏BTRWからモノイド圏 C = (C, ¥otimes, I) への関手を構成します。ただし、ψ:W→|C| は与えられているとして、ψ(i) = I の条件を付けます。

ψから決まる関手 Fψ:BTRWC とします。記号の乱用で、F = Fψ とも書きます。

関手Fの対象部分(object part)は、次のように再帰的に定義します。

  1. a∈W のとき、F(a) := ψ(a)。特に、F(i) := ψ(i) = I
  2. F((s∧t)) := F(s)¥otimesF(t)

次に、Fの射部分(morphism part)を定義するのですが、単純書き換え [t, (ξ, u), t'] に対する F([t, (ξ, u), t']) は定義されていると仮定します。次の節で実際の定義をします。

F([t, (ξ, u), t']) が定義されているなら、前節の最後で述べた等式を意識して:

  • F([t0, (ξ0, u0), t1, ..., tn-1, (ξn-1, un-1), tn]) := F([t0, (ξ0, u0), t1]);...;F([tn-1, (ξn-1, un-1), tn])

ここで、右辺の「;」は圏Cにおける射の結合です。また、

  • F([t]) = idF(t)

以上のデータから定義される F = Fψ が関手になることも容易に確認できます。

この関手 F = Fψ:BTRWC を、圏Cを値とする評価関手(evaluation functor)と呼ぶことにします。

単純ツリー書き換えの評価

前節で先延ばしにした F([t, (ξ, u), t']) の定義を述べます。以下で、α, λ, ρ はモノイド圏Cの結合律子、左単位律子、右単位律子とします。

まず ξ = / (ルート)の場合を定義します。

  1. u = LSw、t = ((p∧q)∧r) のとき、F([t, (/, u), t']) = αF(p),F(q),F(r)
  2. u = RSw、t = (p∧(q∧r)) のとき、F([t, (/, u), t']) = αF(p),F(q),F(r)-1
  3. u = LIns のとき、F([t, (/, u), t']) = λF(t)-1
  4. u = LDel、t = (i∧p) のとき、F([t, (/, u), t']) = λF(p)
  5. u = RIns のとき、F([t, (/, u), t']) = ρF(t)-1
  6. u = RDel、t = (p∧i) のとき、F([t, (/, u), t']) = ρF(t)

ξ ≠ / のとき、p = subtree(t, ξ) とします。サブツリーp上では、F([p, (/, u), p']) が定義できます。サブツリーp上の定義を、二分木全体tまで拡張すればいいのですが、それには、「左子ツリーから親ツリー」「右子ツリーから親ツリー」への拡張を定義すれば十分です。その拡張を繰り返し適用すればいいからです。

  • F((p∧q)) := F([p, (/, u), p'])¥otimesidF(q)
  • F((q∧p)) := idF(q)¥otimesF([p, (/, u), p'])

ツリー書き換えによるマックレーンの一貫性定理の記述

以上で、モノイド圏に関するマックレーンの一貫性定理を述べる準備が出来ました。記号 W、BTRWC、ψ、Fψ の意味は今までと同じです。

  • W: 特定の要素iが指定された集合
  • BTRW: 二分木とツリー書き換えの圏
  • C: モノイド圏
  • ψ: W→|C| という写像、ただし ψ(i) = I
  • Fψ: ψにより定義される評価写像

s, tが2つの二分木で、x, y:s→t を圏BTRWの射とします。このとき、

  • Fψ(x) = Fψ(y) in C

これがモノイド圏に関するマックレーンの一貫性定理です。

Cの対象で、A = F(s), B = F(t) と書けるようなA, Bを選んだとき、A→B という射で F(x:s→t) の形で書ける射は在っても1本だけです。別な言い方をすると、評価関手Fψの像である部分圏はやせた圏です。

トラックバック - http://d.hatena.ne.jp/m-hiyama/20160728

2016-07-26 (火)

教養としてのC言語プログラミング入門は成立するのか

| 13:52 | 教養としてのC言語プログラミング入門は成立するのかを含むブックマーク

比較的に短い期間のなかで、プログラミングの基本的なことを勉強する(させる)とき、どんな話題や課題を選ぶべきでしょうか?

ここでの「基本的」とは、「将来、もっと発展的なことを学ぶための土台を作る」という意味ではありません。「入門者でも手が届く典型的な事項」という程度の意味です。教養としてプログラミングをかじるときに、どこをかじるべきか? という問〈とい〉と言ってもいいでしょう。

使うプログラミング言語C言語です -- と、ここでズッコケる人がいそう。そもそも、入門になんでC言語使うんだよ!? って話は当然あるんですが、まー、そこは「なんらかの事情でC言語しかない」前提にします。実は、この前提のテキストと問題集があったのですが、それを見て僕が感じたことを雑駁に書きます。

内容:

  1. パラメータの与え方:scanf()を使う
  2. scanf()でいいのか?
  3. コマンドライン引数
  4. 標準入力の利用
  5. バッファ
  6. main()以外の関数
  7. 考慮すべきこと

パラメータの与え方:scanf()を使う

まず、どんな種類の処理を扱うか? C言語による文字列処理/テキスト処理はだいぶ難しいですよね。となると、やれることは数の計算になってしまいます。ユークリッドの互除法とか、数値データの平均値を求めるとか、ですね。

ここでは、引き算と大小比較で割り算の余りを求めるコードフラグメントを例とします。

// nとkは整数変数
int r = n;
while (r >= k) {
    r = r - k;
}

この例題を、n = 249, k = 83 に関して実行したいなら、次のコードになるでしょう。

// exam-1.c
#include <stdio.h>

int main()
{
    int n = 249, k = 83;

    int r = n;
    while (r >= k) {
        r = r - k;
    }
    printf("結果: %d\n", r);

    return 0;
}

これを、n = 175, k = 47 に対して計算するために、ソースファイルをコピーして一部書き換えはさすがにやりたくない(やらせたくない)ですよね。そこで登場するのがscanf()です。

// exam-2.c
#include <stdio.h>

int main()
{
    int n, k;
    printf("整数を入力してください > ");
    scanf("%d", &n);
    printf("もうひとつ整数を入力してください > ");
    scanf("%d", &k);

    int r = n;
    while (r >= k) {
        r = r - k;
    }
    printf("結果: %d\n", r);

    return 0;
}

$ gcc ./exam-2.c

$ ./a.exe
整数を入力してください > 175
もうひとつ整数を入力してください > 47
結果: 34

$ 

scanf()でいいのか?

現実的なプログラミングでscanf()を使うことはあまりないでしょう。むしろ、使用を(暗黙的にでも)禁止されていることがありそうです。そんな問題含みの関数を使う(使わせる)のはいかがなものか? とは思います。

ですが、次のような理由でscanf()が消極的に支持されているのでしょう。

  1. scanf()の使用を禁止すると、代替手段のための知識やスキルが必要になってしまう。
  2. scanf()を安全に使うことは注意すれば出来るので、禁止するほどのことはない。
  3. 教養としてのプログラミングなら、そのへんのこと(不注意によるバッファ・オーバーランとか)に神経質になる必要はない。

これらの意見に反論するのは難しいので、僕もscanf()を排除する気はないのですが、それにしてもscanf()は使い勝手が悪い。

上の例で、不適切な値や数値と解釈できない入力をしてしまうと、予測できない奇妙な動作をします。(k = -47 に対する結果はscanf()のせいじゃないです。整数が循環してるせいですが、「循環を巡る話:螺旋、時計、2の補数表現、角度算、リング」を参照。)

$ ./a.exe
整数を入力してください > 175
もうひとつ整数を入力してください > -47
結果: -2147483635

$ ./a
整数を入力してください > x
もうひとつ整数を入力してください > 結果: 32

$

不適切な入力をキチンとハンドルするには、値の検査だけでなく、scanf()の戻り値をチェックしたり、標準入力のフラッシュをしたりする必要があるので、けっこう面倒なことになります。面倒を避けるなら、「入力が正しくないときのことは考えないことにしよう」とかでお茶を濁すしかありません。

コマンドライン引数

「基本部分だけを教える」であっても、コマンドライン引数は使ったほうがいいと僕は思います。

先の例でプロンプトを出して入力してもらうパラメータを、コマンドライン上で指定するように変更すると例えば次のようになります。

// exam-3.c
#include <stdio.h>

int main(int argc, char *argv[])
{
    if (argc < 3) {
        fprintf(stderr, "引数が少なすぎます.\n");
        return 1;
    }
    int n = atoi(argv[1]);
    int k = atoi(argv[2]);

    int r = n;
    while (r >= k) {
        r = r - k;
    }
    printf("結果: %d\n", r);

    return 0;
}

*argv[] の先頭のアスタリスクがオマジナイになってしまいますが、それを言うなら、scanf()の第2引数に入っているアンパサンド(&nとか)だってオマジナイです。( char *argv[] や &n を理解するにはアドレスやポインターを知る必要がありますが、これはけっこうハードルが高い。)

実際に使われているコマンドラインコマンドでは、プロンプトを出してパラメータ入力を求めるプログラムはあんまりなくて、コマンドライン上にパラメータを指定します。この事実を根拠に、対話的プロンプトはやめてコマンドラインだけでもいいような気がします。

標準入力の利用

例えば、次のような課題を考えてみます。

  • ファイルに整数値の列が入っているとして、それらの整数値の平均値を求めよ。

データが入っているファイルを名前で扱うなら、ファイルのオープン/リード/クローズという一連の手順が必要です。この手順を「基本」のなかに含めていいかも知れませんが、ファイルハンドルやファイルポインタの概念は割と難しいものです。

データ入力の口は、とりあえずは標準入力でいいと思います。

// exam-4.c
#include <stdio.h>

int main()
{

    int x; // 個々のデータ(整数値)
    int n = 0; // データの個数
    float sum = 0.0; // データの総和、後でnで割り算する

    int rscan; // scanf() の戻り値
    while (1) {
        rscan = scanf("%d", &x);
        if (rscan != 1) break;
        n++;
        sum += x;
    }
    if (n == 0) {
        fprintf(stderr, "データがありません.\n");
        return 1;
    } else {
        printf("結果: %f\n", sum/n); // 注意: %d だとダメ
        return 0;
    }
}

標準入力のいいところは、ファイルからでもキーボードからでもデータを入力できることです。

$ gcc exam-4.c

$ ./a.exe
1 2 3 4
5 6
^D
結果: 3.500000

$ cat nums.txt
1 2 3 4
5 6

$ ./a.exe < nums.txt
結果: 3.500000

$

標準入力は、プログラム自身が対話的プロンプトやコマンドライン引数からファイル名を取る方法よりむしろ優れた方法と言えるでしょう。

バッファ

C言語で頭が痛いのがバッファの扱いです。前の問題と同じくファイルやキーボードからデータを入力するとして、平均からの差(偏差)を求める課題を考えてみます。出力も数値(整数とは限らない)の列になります。

平均の場合は、数値の列を頭からお尻に向かって一回なめる過程で計算が出来ました。しかし今度の問題では、読み取った数値達を憶えておかなくてはなりません。憶えておく場所がバッファですが、これは難しい。

数値の個数は前もって予測できないので、動的にバッファを取る必要がありますが、「教養としての」「基本」で、動的バッファ確保をやるんかい? 「大きめのバッファを取る」が妥協点でしょうね。

とりあえず、バッファに保存するだけのコード。

// exam-5.c
#include <stdio.h>

int main()
{
    int numbers[100];
    int x; // 個々のデータ(整数値)
    int n = 0; // データの個数

    int i;
    int rscan; // scanf() の戻り値
    for (i = 0; i < 100; i++) {
        rscan = scanf("%d", &x);
        if (rscan != 1) break;
        numbers[i] = x;
    }
    n = i;
    // バッファ内容をそのまま出力
    printf("%d個の数値を読み込みました.\n", n);
    for (i = 0; i < n; i++) {
        printf("[%d] %d\n", i, numbers[i]);
    }

    return 0;
}

これは100個までは保存して、その後は捨てます(「裸の100はやめろ」とか言われそうですが、まぁまぁ)。現実的には、元データが100個を越える数値を含むときはエラーにしたほうが好ましいでしょうが、問題を「最初の100個まで」とすればこれでも許されるでしょう。

main()以外の関数

プログラムが多少長くなったら関数に切り出したくなりますし、切り出すべきです。でも、関数呼び出し/引数渡しはけっこう難しい。main()内にすべて書く、で済ませるのもひとつの判断だと思います。

前節の問題でも、平均値と偏差を求める部分をmain()内に混ぜ込んでしまうことはできます。

// exam-6.c
#include <stdio.h>

int main()
{
    int numbers[100];
    int x; // 個々のデータ(整数値)
    int n = 0; // データの個数
    float sum = 0.0; // データの総和

    int i;
    int rscan; // scanf() の戻り値
    for (i = 0; i < 100; i++) {
        rscan = scanf("%d", &x);
        if (rscan != 1) break;
        numbers[i] = x;
        sum += x;
    }
    n = i;
    float mean = sum/n; // 平均値
    for (i = 0; i < n; i++) {
        printf("%f\n", numbers[i] - mean);
    }

    return 0;
}

これくらいなら、そんなにゴチャゴチャではありませんが、配列の平均値を求める関数は独立させたい感じはします。

でもね、C言語だと配列は長さを保持してないので、float mean(int cout, float numbers[]) のような関数が必要なんですよね。int main(int argc, char *argv[]) をちゃんと説明しておけば大丈夫かな? って、char *argv[] を“ちゃんと説明する”って、すごく大変なんですけど、、、

言わないお約束ではあったんですが、冒頭で出した「入門になんでC言語使うんだよ!?」という疑問はどうしても頭をもたげますね。

考慮すべきこと

適切な妥協点を見出すのは、ほんとに難しいなー、と感じます。気付いた点や考慮すべきと思える点を順不同でズラズラと書き並べます。

  1. リテラル文字列はいいが、処理対象としての文字列(ヌル文字で終わるキャラクタ配列)は難しい。
  2. したがって、処理対象は数値に限られるだろう。
  3. つまり、データ型としてはintとfloatだけ。(longやdoubleも使うと混乱しそう。)
  4. scanf()の使用は避けられないと思う。
  5. printf(), scanf() のフォーマット指定は %d, %f, %s の3つだけでいいだろう。
  6. scanf()の引数に現れる &n のアンパサンドはオマジナイでも致し方ない。
  7. どうせオマジナイが避けられないなら、scanf()のフォーマット指定を %10s とかのオマジナイ(長さ付き)にしたほうがいいかも。
  8. 固定長のバッファは必要だが、動的バッファは難しいから諦める。
  9. 固定長のバッファを使い、バッファに入らない残余は捨てるかエラーとする。
  10. エラーハンドリングは難しい問題だから、深入りはしない。不正な入力に対しては変なことが起きてもしょうがない、とする。
  11. エラーメッセージはstderrに書く、くらいは注意してもいいと思う(これもオマジナイになるけど)。
  12. コマンドライン引数の取り方は学んで使ったほうがいい。char *argv[](または char **argv)はオマジナイ。
  13. コマンドライン引数が使えれば、主要なデータを標準入力から取り、オプショナルなパラメータをコマンドライン引数から取るようなことが出来る。対話的プロンプトによるパラメータ入力では、標準入力からのデータ入力と両立しない。
  14. (main()以外の)関数を導入したほうがいいと思うが、配列やポインターが引数に渡るメカニズムは難しい。引数を、数値と配列の名前に限定するといいかも知れない。

最後に身も蓋もないことを言ってしまうと:

  • 可能ならば、C言語は避けるべきである。
トラックバック - http://d.hatena.ne.jp/m-hiyama/20160726