Erlang実験室：状態遷移を書くのはこんなに簡単 - 檜山正幸のキマイラ飼育記 (はてなBlog)
あまり強調されないようですが、Erlangでは、その構文と実行メカニズムとがあいまって、状態遷移のプログラミングがとても容易です。 例題として、正規表現 /aa?b*c/ とマッチする文字列を認識するオートマトンを作ってみましょう。まず、状態遷移図を描き*1、それから遷移表を書きます。図と表のなかで、EOSは End Of String のマーカー、◎は終状態です 遷移表： 0から3までの各状態について、入力ごとの遷移先は次の通り。×はエラーです。 状態 文字a 文字b 文字c EOS その他 0 1 × × × × 1 2 2 3 × × 2 × 2 3 × × 3 × × × ◎ × この表を見ながら、Erlangコードを書きます。以下のような感じ。 accept(N) -> % 引数Nが状態 case N of 0 -> receive $a -> accept(1); _ -> e
プログラミング言語Makeの関数型フラグメント：まとめとサンプル - 檜山正幸のキマイラ飼育記 (はてなBlog)
一時Makefileに凝っていました。Makefileの記述構文のなかに、「Lispに似た小さな関数型言語が埋め込まれているんだ」とか言ってましたよね。あれはまー、遊び半分なんだけど、このテの知識は、実際にMakefileを読み書きするときにも役にたちます。 過去のMakefile関係エントリーを読み返そうと思ったら、けっこう量があるし、紆余曲折があるんで、ここに整理してまとめておこうと思います。 内容： 参考資料 概念と用語 データ型 変数 関数 制御構造 画面出力と強制終了 ●参考資料 Makefileに関しては、次のエントリー群でゴタゴタと説明しています。 Makefileの書き方、その勘どころ Makefileの書き方：プログラミング言語Make プログラミング言語Make 補遺：引数付きの関数 Make 補遺の補遺：遊んでいるだけ Make言語で算術演算 <-- バカ！ もっとも
イプシロン計算ってなんですかぁ？ こんなもんですよぉ - 檜山正幸のキマイラ飼育記 (はてなBlog)
ラムダ計算は、計算モデルとしてだけでなく、手計算の実際的手段としても役立ちます。しかし、通常使われる各種変換（アルファ、ベータ、イータ、デルタ）ではうまく計算が進まないときがあります。例えば、gがfの逆関数のとき、f(g(y)) は y に簡約されるのだけど、f(g(y)) ⇒ y って簡約規則は通常のラムダ計算ではうまく定式化できません（いや、できるかもしれませんが、僕にはうまい方法が思いつきません）。 そこで、ラムダ計算に加えてイプシロン計算も使うとよさそうです。でも、イプシロン計算は、ラムダ計算ほどにポピュラーではないですね。簡単な例でイプシロン計算を紹介しましょう。 内容： イプシロン記号とイプシロン項 イプシロン項の意味 イプシロン項が定義する関数 例題：gがfの断面（セクション）であること イプシロン記号とイプシロン項 負の数-1とか、無理数√2とかを導入するとき、次のような定
もう一度、ちゃんとJSON入門 - 檜山正幸のキマイラ飼育記 (はてなBlog)
僕自身も僕の周辺もJSONをよく使います。でも、細かい点でけっこうミスをやらかしています(苦笑)。このエントリーで、JSONを使う上で注意すべきこと／間違いやすい点をすべて列挙します。 内容 兼チェックリスト： 仕様原典さえ読めば完璧（のはずだが） 数値の前にゼロを付けてはいけない 16進数表記も禁止だよ 数値の前にプラスを付けてはいけない 小数点からはじまる数値はダメ 用語法が違うよ：プロパティとメンバー メンバー名には常に文字列を使う 空文字列""もメンバー名に使える 配列要素はキッチリと並べよう 文字列を囲むには二重引用符だけ 文字列内のエスケープが微妙に違う 仕様にないエスケープは構文エラー undefinedもNaNもありません ラッパーオブジェクトは使わないのが吉 型システムとtypeofに関する注意 最後に 仕様原典さえ読めば完璧（のはずだが） JSONは、小さくて簡単な仕様
ホッピングボール：書きはじめよう、ゆるゆると - 檜山正幸のキマイラ飼育記 (はてなBlog)
状態遷移マシンは、計算機構のモデルとして有名なものだし重要ですよね。僕が「ホッピングボール・マシン」と名付けた（適切な名前が見あたらなかったので）モデルは、とても単純な状態遷移マシンです。これ以上の単純化は難しいというくらい単純です。 この単純なモデルであるホッピングボール・マシンは、プログラム意味論はもとより、圏論、論理、グラフ理論などの立場からも興味深い素材で、この素材を使って次のようなことを説明できます。 振る舞い意味論 模倣／双模倣 モノイド圏 高次圏 計算現象と物理現象のアナロジー 一般化された行列計算 僕が「面白いなー」と思っていることはだいたい、ホッピングボール・マシンを例題として解説できそうです。以前から、ホッピングボール・マシンとその周辺について書きたいとは思っていたのです。でも、なかなか書き出せないでいました。 ホッピングボール・マシン自体は単純なんですが、背後に非常に
いまさらながらだけど、オブジェクトとクラスの関係を究めてみようよ - 檜山正幸のキマイラ飼育記 (はてなBlog)
オブジェクトとクラスの関係について、次のような説明を見かけました（文言の引用ではなくて、檜山による要約）。 オブジェクトとクラスは全体としてツリー構造をしていて、ツリーの末端をオブジェクト、末端以外のノードをクラスという。末端であるオブジェクトは、その親ノードであるクラスのインスタンスと呼び、クラスどおしの親子関係を継承関係と呼ぶ。 うーむ、この説明、ある意味「簡潔でわかりやすい」とも言えるのだけど、ちょっと単純化し過ぎでしょ。 オブジェクトやクラスの概念て、そんなに美しくもなきゃ、整合的でもありません。実用性やら実装上の都合やらでゴチャゴチャですがね。しかし、そのゴチャゴチャが悪いともいえません。ゴチャゴチャを無理に単純化することなく、必然性を持った（幾分は偶発的だけど(苦笑)）複雑さとして理解すべきかと思います。 というわけで、メタクラスやレイフィケーション（reification）な
CPS（継続渡し方式）変換をJavaScriptで説明してみるべ、ナーニ、たいしたことねーべよ - 檜山正幸のキマイラ飼育記 (はてなBlog)
久々にThe n-Category Cafeを見たら、Mike Stayによる"The Continuation Passing Transform and the Yoneda Embedding"なんて記事がありました。 米田埋め込みは圏論ではお馴染み。継続渡しへの変換はコンピュータ・プログラミングではお馴染み。 この2つは、実は同じものなんだよ。なんで、誰もこのことを言わないんだろうね？ The Yoneda embedding is familiar in category theory. The continuation passing transform is familiar in computer programming. They're the same thing! Why doesn't anyone ever say so? Mike Stayのこの記事、面白いのだ
シェルのリダイレクトを「こわいものなし」というくらい完全に理解しよう - 檜山正幸のキマイラ飼育記 (はてなBlog)
「Java BlockingQueueで遊ぶ：パイプラインごっこ」でパイプラインの話をしたので、本来の、つまりUnixのパイプやリダイレクトを少し調べてみました。 たまに話題となる some-command >file 2>&1 と some-command 2>&1 >fileの挙動の違いについて、「シェルはコマンドラインリダイレクトの指定を右から左に解釈実行する」なんて説明が見つかりました。んなバカな！ パージングは左から右にするものですよ。パーズツリーを逆順にたどることはできるけど、そんなことする必然性はなんにもないよ。 次の記事を読むと、「右から左」なんて事情じゃないことが分かるでしょう。 UNIXの部屋 検索: リダイレクト シェルのリダイレクトにまつわる失敗 さてここでは、複雑なリダイレクト処理も完全に理解できる処方箋を示しましょう。例えば、次のコマンドラインが何をするか分かる
デカルト閉圏におけるお絵描き計算の基礎 - 檜山正幸のキマイラ飼育記 (はてなBlog)
昨日の圏論勉強会に少し顔を出しました。そしたら、たけをさんがお絵描き計算（絵算；pictorial calculation）をしていました（この記事を参照）。けっこうめんどくさい計算をお絵描きしていたので、その場でお絵描き2級を授与しました（少し、はやまった気もするが）。 使っていた描き方は、「デカルト閉圏における絵算 詳細編」のものですが、実は「デカルト閉圏における絵算 オマケ」で補足訂正しているので、新しい流儀を使ってくださいな。新しい描き方を使うと、ベータ変換、イータ変換がより直感的になります。そのことを以下で説明。 内容： 新しい描き方 ベータ変換のアニメーション 引き伸ばしとジグザグ等式 関連するエントリー 新しい描き方 ラムダ抽象（カリー化）により分岐とループができますが、新しい描き方では： 分岐ノードを小さな丸で描く。必要なら文字「λ」で印を付ける。 ループの向きは逆方向だと
Make言語で算術演算 <-- バカ！ - 檜山正幸のキマイラ飼育記 (はてなBlog)
おまえは何をやっとるんじゃ!?＞俺 アホじゃー、バカじゃーー。 それでは、いってみましょう。 予備知識： Makefileの書き方：プログラミング言語Make プログラミング言語Make 補遺：引数付きの関数 Make 補遺の補遺：遊んでいるだけ Make言語には算術演算がない さて、今話題の（って、そんなこたぁねーよ）プログラミング言語Makeですが、豊富な（って、ホントかぁ？）文字列処理関数を備えていますが、なぜか算術演算がありません。足し算もできません。でも大丈夫、足し算くらいすぐに実装できますよ（って、ホントかぁ？）。 最初に老婆心から言っておきますが、すぐさまホントに足し算が欲しいなら、次の不粋な方法が現実的かと思います。 add = $(shell expr $(1) + $(2)) タリー表現による足し算 自然数（0以上の整数）を次のように表現しましょう； 0は""（空文字列
Makefileの書き方：プログラミング言語Make - 檜山正幸のキマイラ飼育記 (はてなBlog)
「Makefileの書き方、その勘どころ」にて： まだ、関数を使ってソースやターゲットを生成する方法とかパターン規則の説明をしてないので、続きを書くと思います。調べているうちに、GNU Makeの構文（の一部）はある種のプログラミング言語だという気がしてきました；そのことも書きたい気がしてます。 というわけで続きを書きます。 実は、関数呼び出しを使うときは、代入に「=」を使うより「:=」のほうが適切かつ効率的なときが多いのですが、その話は次の機会にします。 これの説明が中心になります。 内容： 前置き 変数の種類と変数定義 ソースコードの後のほうを参照すること Makeは上から下へと実行していくのだ MakeとLispは似ている 実例 ●前置き 以下、Make一般ではなくてGNU Makeの話です。GNU Makeより古いMakeにも備わっていた伝統的機能の説明はしません。 GNU Mak
Makefileの書き方、その勘どころ - 檜山正幸のキマイラ飼育記 (はてなBlog)
「ほとんど忘れた、Makefile」 にて： Makefileなんてもう何年も書いたことがないぞ。ウーン、だめだ、忘れている。 「忘れている」ってよりは、僕の知識じゃ古すぎて、改めて勉強しないとダメでした*1。 なにしろ、makeだけじゃ機能が貧弱なんで、cpp（Cプリプロセッサ）やm4（マクロプロセッサ）と組み合わせて使っていた頃しか知らんからね（古すぎ！）。今じゃGNU Makeを（使おうと思えば）どこでも使えるから、GNU Makeを習えばそれでいいじゃないかな。僕は、Windows上のMSYS（MinGW - Minimal SYStem）でGNU Makeを動かしました。 というわけで、GNU Makeの手習いをしたからメモしておきます。以下、名前がMakefileじゃなくても、GNU Makeへの指示を書いたファイルは何でもMakefileと呼びます。 [追記]id:paell
プログラマのための「ゲーデルの不完全性定理」(1) - 檜山正幸のキマイラ飼育記 (はてなBlog)
「プログラマのためのJavaScript」の番外シリーズ -- いやっ、ホントに。 これはシリーズのハブエントリーです。番号を（0じゃなくて）1にしたのは、全体目次だけじゃなくて内容が含まれるから。 ※ 印刷時にはサイドバーは消えるはずです、お試しください。 シリーズ全体目次（予定） （この記事；総論） 速攻速習編 自己適用からゲーデル化へ 「展望」への緊急パッチ（オハナシだよ） Reflective JavaScript 停止問題の構造 不完全性定理の構造 今回の内容： ゲーデルの不完全性定理とプログラミング ゲーデルが示したこと 不完全性定理の兄弟 -- 停止問題 JavaScript使うんだもんね 関連する記事（参考） 次の記事 速攻速習編 ●ゲーデルの不完全性定理とプログラミング 「ゲーデル」（人名；Kurt Godel、'o'の上に点々が付いてる）や彼の「不完全性定理」とかって、
檜山正幸のキマイラ飼育記 (はてなBlog)
2023-10-25 圏スタンピング・モナドの代数は前層／余前層 雑記／備忘 「左加群は前層、右加群は余前層、双加群はプロ関手」の続きです。余前層としての右加群（または前層としての左加群）が、ファミリー〈集合族〉の圏上のモナドのアイレンベルク／ムーア代数になってるよ、という話です。$`\newcommand{\mrm}[1]{\mathrm{#1}}… 2023-10-24 続・有向コンテナと多項式コモナド： 錯綜整理 雑記／備忘 「有向コンテナと多項式コモナド」にて： モノイド類似構造である有向コンテナ〈圏〉構造が、多項式自己関手を台とするコモノイド構造として反映されるわけです。面白いですね。 面白そうなので、アーマン／ウウスタル〈Danel Ahman, Tarmo Uustalu〉以外の… 2023-10-23 Diag構成の変種とその書き方 雑記／備忘 ある文脈では、図式と関手は同
絵を描いて学ぶ・プログラマのためのラムダ計算 - 檜山正幸のキマイラ飼育記 (はてなBlog)
「JavaScriptで学ぶ・プログラマのためのラムダ計算」は、1回では述べ切らなくて、一段落付いたところで区切りました。これはかえって良かったですね、ブックマークやトラックバックでフィードバックが得られたので。 そのフィードバックなどをかんがみて、「残り＝次回の話題」として予告した内容とは食い違ってしまうのだけど、今回は、文章では伝わりにくい（前回うまく伝わらなかったと思える）ラムダ計算の大事なツボを、なんとか表現してみようと思います。 ［このエントリーの内容はだいぶ前にほぼ出来上がっていたのだけど、ココに書いてある事情で、“お絵描き”がなかなか出来なかったのです。］ ※印刷のときはサイドバーが消えます。 内容： 知っていて損はない 計算は身体的に理解しよう ラムダ項のツリー表示：準備 ラムダ項のツリー表示：描く！ β変換に対応するツリーの描き換え もっとβ変換をやってみよう 計算現象を
檜山正幸のキマイラ飼育記 - JavaScriptで学ぶ・プログラマのためのラムダ計算
「JavaScriptによるテンプレート・モナド、すっげー簡単!」にて： 紙と鉛筆でラムダ計算を実行できることは必要だな、やっぱり。 なんて強調したので、ラムダ計算の入門、いってみよう。 [追記]練習問題集を追加しました。説明を読みながら、あるいは読んだ後で是非やってみてください。→「JavaScriptで学ぶ・プログラマのためのラムダ計算 問題集」[/追記] ※印刷のときはサイドバーが消えます。 内容： JavaScriptの関数リテラル ラムダ式ってなんだ ラムダ計算の体系と適用操作 ラムダ式の例をいくつか β変換 -- ラムダ計算のキモ！ β変換を何度か実行してみる 中間まとめ、まだ続きがあるよ JavaScriptの関数リテラル 最初に、JavaScriptに関する知識を確認しておきましょう。なお、JavaScriptの対話的実行環境については「もっともお手軽な対話的JavaScr
プログラマのためのJavaScript (5)：コンパイル単位 - 檜山正幸のキマイラ飼育記 (はてなBlog)
最近の言語処理系では、コンパイラとインタプリタの区別がしにくくなっています。対話的処理系でも、内部ではコンパイラが走っていることが多いからです。JavaScriptも、「コンパイラかインタプリタか？」を判断しにくい実行形態ですね。しかし、コンパイラとして、あるいはインタプリタとしてのJavaScript処理方式を理解してないと、プログラミングで戸惑＜とまど＞うこともあるので、今回はこの点をハッキリさせましょう。 ●JavaScriptの典型的な実行モデル 現実の実装は色々でしょうが、ここでは、JavaScriptは次のように実行されると考えましょう： ソースコードはコンパイラによりJavaScript仮想機械（以下、JSVMと略記）のコード列にコンパイルされる。 コンパイル済みコード列がJSVMにより実行される。 コンパイル中も実行中も、オブジェクト構造が参照され変更される。 通常、コンパ
檜山正幸のキマイラ飼育記 - 世界で一番か二番くらいにやさしい「モナド入門」
気まぐれと偶然となりゆきで、ここ2,3回はモナドを話題にしました。googleで「モナド」を引いてザッと眺めると、「モナドはむずかしいー」とか「モナドで挫折した」みたいな雰囲気が感じられて、説明芸人の血が少し騒ぎましたね。「なら、予備知識ゼロでモナドの説明をしてやろうじゃねーか」と。 タイトルはだいぶ煽っちゃった…… けど、ハッタリじゃないつもり…… けど、実際はどうかな？ ※印刷のときはサイドバーが消えます。 内容： とりあえず、あたりさわりなくモナドの来歴を紹介する こんな課題を考えてみよう：副作用付き計算 カウントアップする関数達 カウントアップしたい意志を戻り値で伝える それでは、いったい誰がカウントアップをするのだ 関数の引数の型をCountup型にまで拡張する そして、これがモナドだ とりあえず、あたりさわりなくモナドの来歴を紹介する 今からここで説明する「モナド（monad）
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
