関数型言語を利用したアプリケーションは少ない。でももっと色々作れるのでは？という話。主にHaskellを念頭において書く。 Haskell製アプリケーションの実例。 Pugs Perl6インタプリタ。本家よりも先に実装。 darcs バージョン管理システム。パッチ志向。 x…

設計規約 モジュールの外部仕様は設計段階ですべて決定する。 外部仕様に基づいたテスト仕様を設計段階で記述する。 設計の項目は「確定」「未定」「任意」の三状態をとる。 設計時に確定できない詳細*1を「未定」として扱う。「未定」の項目は他のモジュー…

http://d.hatena.ne.jp/bleis-tift/20090804/1249389793の話。 確かに元のコーディング規約は突っ込みどころが多い。Javaの規約をそのまま持ち込むという時点で規約項目の検討が甘いことは想定できるし、実際の突っ込みも納得できるものが多い*1。 このコー…

http://d.hatena.ne.jp/katzchang/20090724/p2への回答。 自分専用ツール(自由すぎる)を含めるとデータが怪しくなるので、業務と研究/OSSとを分けてみました。 業務で使っている/いた C C++ C# Python TCL/TK x86 Assembler PL/M 研究/OSSで使っている/いた*…

破壊的に更新する (define Y! (lambda (index . metas) (let ((table (map (lambda (meta) (apply meta metas)) metas))) (let ((funcs (map car table)) (settbl (map cdr table))) (map (lambda (setlst) (let loop ((curfs funcs) (curss setlst)) (if (a…

http://d.hatena.ne.jp/kilrey/20090516#p2の解説。 FORTRANはゴシック。まだルネサンスが始まっていない。 COBOLとBASICはドイツ・ルネサンス。時代的にはイタリア・ルネサンスと重なるが、画風はゴシックに近い。 ALGOL、LISPはイタリア・ルネサンス初期。…

FORTRAN ジオット ALGOL マザッチオ COBOL アルブレヒト・デューラー LISP ボッティチェリ BASIC ピーテル・ブリューゲル C言語 ミケランジェロ Forth ドナテッロ Pascal*1 ラファエロ Smalltalk レオナルド・ダ・ヴィンチ Prolog エル・グレコ C++ ルーベン…

ForthなどのConcatenative言語はContinuation Passing Styleそのものか。となるとContinuation領域の操作を制限することで最適化の余地を大きくしたり、といった話がシンプルに記述できるかも。 参考 http://hengsu.cocolog-nifty.com/personal_newsn/2007/0…

http://d.hatena.ne.jp/kilrey/20090505#p1を書いて得心したのだけど、Y-Combinatorってリンカなのね。 (define p0 (lambda (f0 f1) (lambda (n) (if (zero? n) 1 (+ n (f1 (- n 1))))))) だったら(f0 f1)が環境で、(lambda (n)〜)がオブジェクト。YYが環境…

毎回lambdaを生成するのは実行コストが高いからdelay〜forceすると軽くなる*1。 delay〜force化 (define YY (lambda (index . metas) ((lambda (mm) (apply (mm (list-ref metas index)) (map mm metas))) (lambda (meta) (lambda procs ((lambda (pp) (appl…

何となくY-Combinatorで相互再帰を書いてみた。思ったより綺麗に書けたので公開しておく。 まずは普通のY-Combinator (define p (lambda (f) (lambda (n) (if (zero? n) 1 (+ n (f (- n 1))))))) (define Y-a (lambda (meta) ((lambda (proc) (meta (lambda …

http://homepage1.nifty.com/herumi/diary/0904.html#30の話。 配列a[N]が与えられたときに M_a := { i : a[i] >= a[j] for all j }の元を一つ求めよ 私もこちらの方が楽だと思う口だ。Constractだけ書けばコンパイラが実装してくれる世界が理想。実際には「…

http://www.kmonos.net/wlog/96.html#_1508090428への返答。 「集合」を明示的に値とするアプローチ [1] [2] だと、「同順の要素の並びはどちらでもいい」ソートアルゴリズムは、全ての可能なソート順の集合を返すことになると思います。 あくまでも仕様レベ…

http://www.kmonos.net/wlog/96.html#_2319090427の話。 「値」の単位での非決定性には、少なくとも、速度面のメリットは全く見出せない。たぶん、複数の値を束ねた「集合」をまるで「値」のように表現するべきだと思う。 具体的に この場合、実装するべきは…

たらいまわしまくってみた。 ＼ (tarai 12 6 0) (ytarai 12 6 0) ytarai/tarai gcc -O3 -fomit-frame-pointer 0.06 0.12 2. g++ TMP 0.00 x x gforth 1.18 x x pforth 4.57 x x runhugs 0.24 x x ghc 0.00 x x ocaml 1.40 x x perl 18.08 x x python 7.62 45…

(define Y (lambda (f) ((lambda (proc) (f (lambda (x y z) ((proc proc) x y z)))) (lambda (proc) (f (lambda (x y z) ((proc proc) x y z))))))) (define Ytarai (lambda (f) (lambda (x y z) (if (<= x y) y (f (f (- x 1) y z) (f (- y 1) z x) (f (- …

stackless pythonなどの「stackless」という語はちょっと語弊がある。それを説明するにはC言語のスタックを説明せねばならない……と思ったが、http://practical-scheme.net/docs/stack-j.htmlを参照するだけで充分だった。stacklessというのはCスタックを使わ…

関数を一般化したものが部分継続なのではないか。 継続として見る場合 継続 部分継続 CPUに送る命令 goto call という関係。

脳内concatenativeの状態。 Parameterを渡す何か Stackとは限らない何か。VMインスタンスごとに一組*1あれば良い。 Continuation Stack 従来、Return Stackと呼ばれていたもの。部分継続をpush, popすることで処理を制御する。scheme的な継続はglobal継続と…

最近、頭の中の言語がStack-basedだったのがconcatenativeに切り替わった気がする。極端なことを言えばStackでなくても良い。 たぶん、CPSの表現の一形態としてStack+固定コード形式がある。むしろ固定コードが前提にあって、一部だけを動的にした結果がRetu…

XXX(自作言語)のコアは独自拡張PEGです。本来のPEGでは入力ストリームを解析しますが、XXX(自作言語)PEGでは入力ストリームを解析する際に並行して副ストリームへの操作を行います。この副ストリームへの操作をアクションと呼びます。 アクションは 入力スト…

メニーコアに対応したプログラミングについて考えてみた。 手続き型パラダイムでは辛い。何故かというとシングルコアにしか対応していないから。現状の同期・排他モデルでは並列度の上昇に対応することが難しい、というより面倒くさい。さらにpthreadはあく…

http://d.hatena.ne.jp/Britty/20090214/p1の話。↓のブクマの続きを書こうとしたら長くなったのでエントリに。 これは明確な「harassment」だけど、当人に「いやがらせ」る意志がない以上話が通じないのも当然かと思う(適切な訳は「迷惑行為」?)。 あまりに…

http://d.hatena.ne.jp/kilrey/20090214#p1に繋がる話。 現状の手続き型言語でマルチスレッド対応する場合にはセマフォなどの排他・同期条件を利用する。その排他・同期条件を利用する文法としてはJavaのsynchronizedがもっとも洗練されているだろう。単純な…

http://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3a%E5%A4%9A%E5%80%A4の話。 手続き型言語におけるn-in, 1-outの関数は、処理系の実装の手抜きから生じたものだと思う。call by referenceやcall by nameの言語ではそれで困ることはなかった (関数は…

強参照を持つオブジェクトはGCされない。 強参照を持たず、ソフト参照を持つオブジェクトはGCされるかもしれない。 強参照・ソフト参照を持たず、弱参照を持つオブジェクトはGCされる。 強参照・ソフト参照・弱参照を持たないオブジェクトはGCされる。 こう…

http://d.hatena.ne.jp/kilrey/20090117#p2の解説。 PEGに足りないものは以下のように導出する。 A? := A/ A* := (A A*)/ A+ := A A* &A := !!A ちなみにfailは内部実装でのみ利用する。ここでは考慮していないが、実用上はエラー報告がきわめて重要。 (追記…

実装終了。高速化はまた明日にしよう。 call/ccを使えるschemeだから何とかなった*1けど、C言語で実装するのはかなり面倒かも。ループに変換できるはずだけど、ねえ。 *1:きっとforthでも何とかなる。

左再帰対応PEGについて改めて考え直してみた。 実装できることは確定。 実行効率にオーバーヘッドがあるかも。 動作自体はかぎりなく右再帰に近い。 文法は左再帰、実行は右再帰という合いの子が出来るということだ。悪くないね。

PEGは左再帰ができない。Wikipediaにも載っている程度の常識的な話だ。 でも、それは本当なのかちょっと疑わしいような気がしてきた。あくまでも実装上の都合にすぎないのではないか、と。もう少し考えを整理する必要はあるけどもたぶん実装できる。 右再帰…