SW中のあれこれ

開発を続けているつもりの小さなアプリケーションで、
今後の内部実装をどうしようか考えていたところ、
いくつかヒントを見つけたためエントリとして書き残しておきます。

2.4.3 データ主導プログラミング(data-directed-programming)と加法性

http://sicp.iijlab.net/fulltext/x243.html

手続きを実装する際には, どうしても処理内容がデータ型に依存してしまいます.

上記のセクションは, データの持つ型(メタ情報)を元に,
処理のふるい分けを行うシステムを導入することで,
プログラムの加法性(過去のプログラムを修正せずに新しい機能を追加する)を
手に入れるための参考になります.

続くセクションでメッセージパッシング, 汎用演算につながっていきますがが,
ここでは操作と型を軸とする二次元テーブルから実際の手続きを検索することで,
apply-genericの実装しています.

拡張性や実行効率とか色々あると思いますが,
たった一つのテーブルだけで実装できるシンプルさがツボにきますね.

(欄外)ハッシュテーブルを用いてスパースな行列

上のテーブル実装(put/get)ですが,
srfi-69を利用すれば一行で解決でした.

(use srfi-69)

(define (type-tag obj)
  (assert (pair? obj))
  (car obj))
(define (contents obj)
  (assert (pair? obj))
  (cdr obj))

(define *table* (make-hash-table))
(define (put op tags item)
  (hash-table-set! *table* (cons op tags) item))
(define (get op tags)
  (hash-table-ref/default *table* (cons op tags) #f))

(define (apply-generic op . args)
  (let* ((tags (map type-tag args))
         (proc (get op tags)))
    (if proc
      (apply proc (map contents args))
      (error (list op tags)))))

hash-tableのキーに操作名と型名のペアを入れることで, 検索しやすくしています.
個人的にはシングルディスパッチでも良いのですが,
SICPでも多重ディスパッチ用にtype-tagは引数全てから取得するようにしています.

使う側:

(define (sound obj)
  (apply-generic 'sound obj))
(put 'sound '(duck)
  (lambda (o) (display "quack")))
(put 'sound '(cat)
  (lambda (o) (display "myaa")))

(define animal-a '(duck))
(define animal-b '(cat))

(sound animal-a)
(sound animal-b)

3.3.4 ディジタル回路のシミュレータ と 3.3.5 制約拡散

http://sicp.iijlab.net/fulltext/x334.html
http://sicp.iijlab.net/fulltext/x335.html

時間経過による状態変更や制約ネットワークによる状態変化の自動伝播.

状態変化の伝播を宣言的に扱う, いわゆるリアクティブなシミュレータを実装する
教科書的なお手本例として見ることができるかなーと考えつつ読み返し中.

続くセクションでストリームが出てきます.
こちらは離散状態変化を並びとして抽象化して取り扱うことにつながるため,
若干毛色が違うように感じています.

外部からの刺激に対して自動的に各オブジェクトの状態が更新されるシステムも,
データフローに着目して, 回路を記述する方針と,
イベントに着目して, イベントストリームへの演算で設計する方針かで,
コードの見た目が大きく変わりそうです.

シミュレータ部分は他にいい実装例がないか模索したいところです.

(欄外)SRFI-38

もちろん他のLisp方言にもありますが,
S式の部分共有のためのリーダーマクロです.

http://wiki.call-cc.org/eggref/4/srfi-38

(define signal (list 0 1))
(set-cdr! (cdr signal) signal)

(write/ss signal)
;=> #0=(0 1 . #0#)

(define shared
  (with-input-from-string "(list #0=(list 1) #0# #0#)" read/ss))

Chicken Schemeではsrfi-38はeggsとして提供されていて,
処理系標準にはないようです.

Let Over Lambda で指摘されている,
実はLispの式は ではなく 有効非循環グラフ であるという特徴です.

http://letoverlambda.com/textmode.cl/guest/chap4.html#sec_5

All our talk about lisp programs being trees of cons cells has actually been a small lie. Sorry about that. Lisp programs are actually not trees but are instead directed acyclic graphs—trees with possibly shared branches. Since the evaluator doesn't care about where the branches it is evaluating come from, there is nothing wrong with evaluating code with shared structure.

コンスセルの仕組みを覚えれば, 循環構造が作れることは分かるので自然な機能と思いつつも,
他の言語では, AST に相当する部分が実は ではない(ことを許す)というのはちょっと面白いです.

任意の根から始まる部分共有を持つグラフ構造 を書き出すパワーが
write/ssにあると信じて試しに使っていくことにします.
(何か制約があったような気がしますが...)

終わりに

今回の下調べの目標は,

  • データ主導プラグラミング(型によるふるい分け)
  • 状態変化を自動伝播する制約ネットワーク
  • 任意の根から始まる部分共有を持つグラフ構造

といった感じです.
組み合わせると,

型ディスパッチされる制約に従って状態変化する部分共有を許すデータ
(つまりリアクティブなドキュメント?)

といった何かが作れないか夢想してます.