BNF、EBNF、ABNF、まー正規表現だな - 檜山正幸のキマイラ飼育記
BNFとか正規表現の話を。 ミニマムなBNFと正規表現 BNF（バッカス／ナウア記法）は、プログラミング言語の構文記述によく使われるメタ構文です。もともとは、「?」（省略可能）や「*」（任意回の繰り返し）のような記号は使わなかったようです。現在の正規表現で標準的に使われる「?」「*」「+」は、なくても次のように定義可能なのです。（以下で、EMPTYはそこに何もないことです。ほんとに何も無いと分かりにくいので目印にEMPTYを使います。） // X は A? X ::= EMPTY | A // Y は A* Y ::= EMPTY | A Y // Z は A+ Z ::= A | A Z 「|」があれば「?」「*」「+」を定義できますが、その代わりに再帰的な定義になります。 「::=」の左に同じ記号が複数回登場するのを許すと、「|」さえも不要になります。 // X は A? X ::=
この機会にマスターしようぜ、正規表現、構文図、オートマトン - 檜山正幸のキマイラ飼育記 (はてなBlog)
正規表現と構文図について解説します。オートマトンについても詳しく述べます。オートマトン・スゴロクで遊びましょう！ 世間でよく知られている／使われている概念・方法にはこだわらず、僕（檜山）の感覚で一番わかりやすいと思われる筋書きと用語法／図式法を使って説明します。この記事に目を通して“感じ”が掴めたら、形式言語理論の教科書を読み始めることが出来るでしょう。 [追記]この記事の内容に対する具体例は、「正規表現とオートマトン：なんだ簡単じゃん、JavaScriptによる実装」にあります。[/追記] 内容： 正規表現 正規表現の例 構文図 基本記号 連接 選択 省略可能 繰り返し ストレートワイヤーによるレイアウト調整 有限状態オートマトン 有限状態オートマトンの実行 バックトラックと先読み スゴロクとオートマトン コマをたくさん使うスゴロクと並列処理 非決定性オートマトンと決定性オートマトン 正
Erlang実験室：武士道と云ふは死ぬ事と見付けたり - 檜山正幸のキマイラ飼育記 (はてなBlog)
Erlangでは、「死ぬこと＝プロセスをクラッシュさせること」の解釈／意義／価値観が、他の言語とは随分違います。潔＜いさぎよ＞く死ぬことが推奨されていますが、これは責務の放棄とは違います。 内容： 事故や災害への対処は個人ではなくて企業や社会が行うべき 正常と異常のはざま 例外を使うのは例外的？ 多プロセス並列プログラミングと例外 潔さと無責任は違う -- 武士道プログラミング ●事故や災害への対処は個人ではなくて企業や社会が行うべき Erlangの書き方や文化で、なかなか馴染めないのが「異常時の処理を書かない」という方針です。 多くのプログラミング言語のコードでは、次のような分岐をしばしば見受けます。 if (正常条件) { 正常時の処理; } else { 異常時の処理; } switch (値) { case 正常な値_1 : 正常時の処理_1; break; case 正常な値_2
拳銃を撃つお巡りさんとか先生とか - 檜山正幸のキマイラ飼育記 (はてなBlog)
ちょっと遅れた言及だが、 拳銃抜いたおまわりさんに支援メール相次ぐ いうことをきかない不良ヤンキーに対して拳銃を抜いて立ち退かせた、と。なるほど。 思い出したのは、新田たつおのビッグマグナム黒岩先生*1。黒岩先生は（当時の）文部大臣に銃の所持を認められているから、拳銃を抜いて立ち退かせてもいいんだよ。オトガメなし。 赤塚不二夫のおそ松くん、天才バカボンに出てくる本官さんもしょっちゅう銃をぶっぱなしていたな。でも、今回のおまわりさんは本官さんよりずっとまともみたい。 さて、ジョージ・G・スピーロの『ポアンカレ予想』（asin:4152088850）にロバート・L・ムーアというトポロジーの先生の逸話があるのだけど： 講義中に学生が気を散らしでもすれば、ムーアは教室に六連発拳銃を持ち込み、それを教卓の上に置いて講義を続けたという話だが、実際に一回はそういうことがあったらしい。 本物の拳銃ぅ、ムー
あの福井市の小学生、その驚くべき発見とは - 檜山正幸のキマイラ飼育記 (はてなBlog)
みなさん、お待たせいたしました。発表いたします。 なにを発表？ -- ことの発端は、「福井市の小学生が驚くべき発見」をまず読んでくださいませ。 読みましたか？ はい、では、いきます。 ●中藤小学校の先生が言いたかったこと 前のエントリーでは、図を少し縮小して貼っていたので、以下のリンクをクリックして原寸大の図を脇に表示しておいてください。 図を別ウィンドウで表示 (a), (b), (c), (d), (e)の5つの例で、周囲の長さはすべて16です。しかし、面積は異なります。念のために表にまとめておけば： ＼ (a) (b) (c) (d) (e) 周囲の長さ 16 16 16 16 16 面積 16 15 14 13 7 小学校の先生が言いたかったことを、（子供向けじゃなくて）大人の言葉で表現すれば次のようになります。 面積が周囲の長さから求まるなら、 面積 = f(周囲の長さ) という
福井市の小学生が驚くべき発見 - 檜山正幸のキマイラ飼育記 (はてなBlog)
たまたま目にした論文に面白いことが書いてありました。 随分と昔（1976年）のことらしいのですが、福井県福井市中藤＜なかふじ＞小学校の先生が、「図形の周囲の長さから面積は求められないし、面積から周囲の長さも求められない」ことを子供達に納得してもらうために、次のような宿題を出したんだそうです。 次の図の「S」と書かれた四角は正方形のタイルです。このタイルの一辺の長さを単位として測ることにして； 図形(a)の周囲の長さは16、面積は16です。たまたま長さも面積も16でしたが、これで法則性があると早とちりしてはいけません。(b)から(e)までの周囲の長さと面積も求めてみなさい。 驚くべきことに、先生の意図に反して、とある子供が“周囲の長さと面積の関係”を発見してしまったというのです。 この子の発見は、その前年（1975年）出版の論文集（University of Tokyo Press）に公表さ
インド、ロシアだけじゃないぞ、ブラジル発の熱帯式算数もあるんだぜ - 檜山正幸のキマイラ飼育記 (はてなBlog)
一昨日のエントリーで、ロシア発のマスロフ式算数を紹介しました。実はこれ、リトヴィノフ（G. L. Litvinov）のサーベイ論文"MASLOV DEQUANTIZATION, IDEMPOTENT AND TROPICAL MATHEMATICS: A BRIEF INTRODUCTION"（http://glitvinov.googlepages.com/2007_JMS_426.pdf）の0.2%ほどを解説したものでした。 リトヴィノフ論文のタイトルにTROPICALって単語が入ってるのに気がつきましたか？ ロシアのマスロフとはまた別に、ブラジルのシモン（Imre Simon）*1に始まると言われる熱帯風（トロピカル）な計算体系があります（トロピカルというネーミングは、ペリン（Dominic Perrin）によるそうです）。 トロピカルという用語の使用法は現状混乱ぎみですが、ここでは
いまさらながらだけど、オブジェクトとクラスの関係を究めてみようよ - 檜山正幸のキマイラ飼育記 (はてなBlog)
オブジェクトとクラスの関係について、次のような説明を見かけました（文言の引用ではなくて、檜山による要約）。 オブジェクトとクラスは全体としてツリー構造をしていて、ツリーの末端をオブジェクト、末端以外のノードをクラスという。末端であるオブジェクトは、その親ノードであるクラスのインスタンスと呼び、クラスどおしの親子関係を継承関係と呼ぶ。 うーむ、この説明、ある意味「簡潔でわかりやすい」とも言えるのだけど、ちょっと単純化し過ぎでしょ。 オブジェクトやクラスの概念て、そんなに美しくもなきゃ、整合的でもありません。実用性やら実装上の都合やらでゴチャゴチャですがね。しかし、そのゴチャゴチャが悪いともいえません。ゴチャゴチャを無理に単純化することなく、必然性を持った（幾分は偶発的だけど(苦笑)）複雑さとして理解すべきかと思います。 というわけで、メタクラスやレイフィケーション（reification）な
シェルのリダイレクトを「こわいものなし」というくらい完全に理解しよう - 檜山正幸のキマイラ飼育記 (はてなBlog)
「Java BlockingQueueで遊ぶ：パイプラインごっこ」でパイプラインの話をしたので、本来の、つまりUnixのパイプやリダイレクトを少し調べてみました。 たまに話題となる some-command >file 2>&1 と some-command 2>&1 >fileの挙動の違いについて、「シェルはコマンドラインリダイレクトの指定を右から左に解釈実行する」なんて説明が見つかりました。んなバカな！ パージングは左から右にするものですよ。パーズツリーを逆順にたどることはできるけど、そんなことする必然性はなんにもないよ。 次の記事を読むと、「右から左」なんて事情じゃないことが分かるでしょう。 UNIXの部屋 検索: リダイレクト シェルのリダイレクトにまつわる失敗 さてここでは、複雑なリダイレクト処理も完全に理解できる処方箋を示しましょう。例えば、次のコマンドラインが何をするか分かる
ムンクの叫び - 檜山正幸のキマイラ飼育記 (はてなBlog)
国立西洋美術館でムンク展をやっているのだが、 長男：「ムンクといえば、『ムンクの叫び』でしょう。」 父親：「よく知っているな。」 長男：「だって、有名だよ。」 父親：「あー、確かに有名だな。」 長男：「で、ムンクはなんて叫んだの？」 父親：「へっ？」 長男：「だから、ムンクはなんて叫んでそんなに有名になったの？」 父親：「… 」
テンソル：定義とか周辺の話とかナニやら - 檜山正幸のキマイラ飼育記 (はてなBlog)
奇遇ですね。 「テンソルってなんかよくわかんね」 僕も比較的最近、「テンソルってなんなんだよ」と考える機会がありました。 「テンソルってなんなんだよ」と最初に考えたのはもう二十数年も前になるのではないでしょうか。それ以来、たまに思い起こすことがあります。 昔（二十から三十年ほど前です）は、微分幾何や物理工学系の本も含めて勘定すれば、テンソルの本はけっこうたくさんあったように思います。が、最近は何故かあんまり見かけませんね（僕の気のせいでしょうか？）。まーとにかく、当時はテンソルの教科書は複数あって見比べることも出来たのですが、どれを読んでもサッパリまったく理解できませんでした。 これは黒魔術か？ それらの本におけるテンソルの定義は次のようなものでした。 i1, ..., in、j1, ..., jmを適当な範囲を動く添字（番号）だとして、添字付けられた数（スカラー）の組 ai1, ...,
檜山正幸のキマイラ飼育記 - JavaScriptで学ぶ・プログラマのためのラムダ計算
「JavaScriptによるテンプレート・モナド、すっげー簡単!」にて： 紙と鉛筆でラムダ計算を実行できることは必要だな、やっぱり。 なんて強調したので、ラムダ計算の入門、いってみよう。 [追記]練習問題集を追加しました。説明を読みながら、あるいは読んだ後で是非やってみてください。→「JavaScriptで学ぶ・プログラマのためのラムダ計算 問題集」[/追記] ※印刷のときはサイドバーが消えます。 内容： JavaScriptの関数リテラル ラムダ式ってなんだ ラムダ計算の体系と適用操作 ラムダ式の例をいくつか β変換 -- ラムダ計算のキモ！ β変換を何度か実行してみる 中間まとめ、まだ続きがあるよ JavaScriptの関数リテラル 最初に、JavaScriptに関する知識を確認しておきましょう。なお、JavaScriptの対話的実行環境については「もっともお手軽な対話的JavaScr
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
