2015/04/01

関数型言語のリストと命令型言語のリスト

C++納品の案件で、プロトタイプ&アルゴリズム検証用にSchemeで実装してから C++に移植するってのをやってて、 std::listとSchemerが考える「リスト」の違いに改めて気づいた。 いやもちろんリストというデータ構造を利用してるという意味では同じなんだけど。

リストを不定長データの集合を扱うコンテナと考えるならstd::list的な もので十分だし、データの挿入位置についてこだわりがないなら可変長配列を持ってる 言語は既にたくさんあって、さらにそういったデータ構造に対するfindや map的な操作も標準で提供されることが多いから、 そっちの面から見たらSchemeでのリスト操作は比較的素直に命令型言語の 組み込みリスト型or可変長配列型に移植できそうに思えるんだけど。

Scheme(や他の関数型言語)のリストってのは、 「既にあるリストに変更を加えずに、新たな要素を低いコストで追加したリストを 得られる」ってのがかなり決定的に重要な性質で。

探索しながら結果を積み上げていって、失敗したら別の選択肢を試す、 なんてコードは、Schemeなら途中までの結果は既に掴んでるから 単に再試行すればいいだけなんだけど、std::listにpush しちゃってる場合は巻き戻さないとならない。 これはまあ、関数型風の書き方と命令型風の書き方のミスマッチと言っちゃえばそれで おしまいなんだけど、 案外、二つのスタイルの根本的な差を端的に示してるのかなとも感じた。

(なお、「SchemeとC++の両方で実装」というのは個人的には成功だった。 循環ありの有向グラフをいじりまくる案件だったので試行錯誤にSchemeの方が圧倒的に楽だったのと、 Scheme版でテストデータを生成してC++版を流して一致するかどうか見る、という形で C++版の実装バグを簡単に潰せたので。 もちろん同一アルゴリズムを使ってる以上、アルゴリズムのバグは別にテストしないとならないんだけど、 実装の問題とアルゴリズムの問題を確実に切り分けられるだけでものすごく助かった。)

Tags: Programming, Gauche, Scheme, C++

2015/04/01

見ながら書く

開発スタイルのせいなのか、それとも短期記憶が小さいのかわからないけど、 自分は「関連情報を見ながら書く」ということが非常に多い。例えば関数を書いてる 時に、その呼び出し元と、それから書いてる関数から呼び出している関数の ソースを同時に開いて見ながら書く、とか、 複数の入力に対するREPLの出力を(REPL窓を2分割して)眺めながら さらに関数を修正する、とか。

だもんで、「書いている箇所でない場所を自由に広く見られる」「(書いているバッファではなく) 見ているバッファ内を自由に移動する」という機能が欠かせない。

Emacsだと、「今書いている関数を呼んでいる関数」が同じファイルにある時に 画面を分割して一方で見たい箇所、もう一方で書いてる箇所を表示するのが数キーストローク でできるんでありがたいんだけど、XCodeとかで思うようにできなくてじれったく 感じる。(Assistant editorのデフォルトを「今見てるファイル自身」に するのってカスタマイズでできるのかな?)

あと、「今書いているまさにその場所」というのを見る必要ってあまりなくて、 どっちかというと参考に参照している部分の方を広い視野で見たいんで、 「複数窓を開いて、参考にしている窓を手前に広く表示し、裏にあるウィンドウに タイプする」という操作も多用するんだけど、 どういうわけか最近のUIはフォーカスした窓を手前に持ってくる動作が デフォルトになってて困る。Linuxは新しくインストールしたらまずこの動作を 変えるんだけど、OSXとWindowsではどうやるのか知らない。

似たような話で、IDEの補完で出てくるウィンドウが、 今書いている箇所の数行先のまさに参照したい部分を隠しちゃっていらつく、 ということもよくある。補完は有難いんだけど、隠さないところに出してほしいなあ。

今風の開発スタイルについていけない、ロートルになったってことなのかもしれないが… みんなこれで使ってるのかなあ。それともカスタマイズしてる?

Tag: Programming

2015/02/19

リリース直後が最も開発効率が高い説

• リリース直前のクランチタイムには、他のことの優先度が下げられるので、 コードに関する事柄が脳内キャッシュに占める割合が最高に達する。
• リリースを済ませると、リリースに向けてのtodoを潰すために 動いていた多くの脳内プロセスが終了する。
• そうすると、「コードに関して膨大な情報が脳内キャッシュに載っており、 その上で好きなプロセスを自由に走らせることができる」という開発には理想的な状態に。

リリースしたらさっさと忘れてぱーっと遊ぶ、とかすると、 折角のキャッシュデータがフラッシュされちゃう。いや遊ぶなとかいうわけじゃないけど、 自分は大量の関連情報をキャッシュに載っけるまでが大変なタイプなので、 むしろこの性質を利用したい。

本来の締切りの手前に自主締切りを設けるとかすれば良いんだろうけれど、 というか一応そう試みてはいるんだけど、やっぱり心のどこかで本当の締切りを 意識していまってなかなかうまくいかない。

ただ、複数のプロジェクトを抱えている時に、コンテキストスイッチのタイミングを ずらすというのはそこそこうまくいっている感じだ。 つまり、プロジェクトAのスナップショットリリースを出したらすぐに プロジェクトBの作業を再開するのではなく、スナップショットリリースの後 少しプロジェクトAの仕事を続けてから、Bにスイッチする。

まあ、プロジェクトが重ならないのが一番いいんだけど。

Tag: Programming

2015/02/08

週給

本筋と関係ないんだけど

『アニメ『楽園追放』は"社会の壁"を壊してヒットを勝ち取った』

給料は1週間ごとに支払われる＝1週間でクビにできる　超成果主義のハリウッドでCGの腕を磨いた日々

[...]

野口　アメリカって怖いと思ったのは、会社ではギャランティーが1週間づつ支払われるんです。 すぐに首が切れるように。来週の給料はもうない、みたいな。だからちゃんと結果を出さないと、いつ切られるかわからない。そんな状態がずっと続くのは疲れるよな、と。

カリフォルニア含むアメリカの半分近くの州では、 法律で給料の頻度は少なくとも週毎とか 月2回とか決まってるんで、月給にすると労働法違反になる。 月給okの州でも制限(収入が多い専門職とか役員とかのみ)があったり、 「労使合意した場合のみ」となっているところが多い。 (労働省のサイトに詳細あり)。

キャッシュフローで考えても、 給料払う頻度が低いほど会社が有利、労働者が不利になるのだから、 週給で払われる方が労働者保護とは言えまいか。 むしろ「会社がいつ潰れても未払いの給料が最長1週間分で済む」と見るべきじゃないかなあ。

いつでもレイオフできるのは"at will"の労働契約ってやつで、 これは給与の頻度とは関係ない。途中でレイオフしても働いた分だけ清算すればいいのだから。

「すぐ首を切れるように」週給になってる、というのに違和感を覚えたので。 まあ、ペイチェックと合わせてレイオフ、みたいな心理的なタイミングが 取りやすい、ってことはあるかもしれないけど。

Tag: 生活

2015/01/30

クロージャの比較、あるいは「同じ」とはどういうことか

@SaitoAtsushi: R6RS では比較結果が未規定である事例として以下のような事例を挙げている。

(let ((p (lambda (x) x))) (eqv? p p))

未規定にすることで可能になるような最適化があったりする？ ざっと見た感じではどの R6RS 処理系も #t を返すっぽい。

この式そのもので#fを返すようにする意味はほとんど無いんだけれど、 もうちょい複雑になった場合にこの規則が意味を持つ可能性がある。

(define (foo a flag)
  (let ((p (lambda (x) (+ x a))))
    (bar (if flag identity p))))

上の式で、pは別の手続きに渡され得る(エスケープする可能性がある)から、 クロージャを作らざるを得ない。けれどもpがエスケープするのは flagが真の場合だけなので、クロージャをアロケートしてから flagが偽とわかったら無駄になる。 処理系としては次のような最適化をしてしまいたい。

(define (foo a flag)
  (bar (if flag identity (lambda (x) (+ x a)))))

この最適化自体は問題ない。

だが、コードがこうなったらどうだろう。

(define (foo a flag1 flag2)
  (let ((p (lambda (x) (+ x a))))
    (bar (if flag1 identity p)
         (if flag2 identity p))))

同じ論理を適用するなら、こういう最適化が許されてほしい。

(define (foo a flag1 flag2)
  (bar (if flag1 identity (lambda (x) (+ x a)))
       (if flag2 identity (lambda (x) (+ x a)))))

しかしこの場合、二つのlambda式でクロージャの実体が別々に作られ得るので、 実体のアドレスで比較すると等しくならない可能性があるわけ。

もちろん、結果的に二つアロケートする羽目になるなら元コードに 比べて損するわけだけど、flag1とflag2が 共に#fになる確率が低い場合は必ずしも全体的に損だとは 言えないわけで、こういう最適化の可能性を切り捨ててしまうわけにはいかない。

このプログラム変換は特にクロージャに限った話ではない。 次のコードは複素数を「作って」それを条件的にbarに渡している:

(define (foo a flag1 flag2)
  (let ((c (make-rectangular 1 a)))
    (bar (if flag1 0 c)
         (if flag2 1 c))))

これを次のように変換することには、何の問題もない:

(define (foo a flag1 flag2)
  (bar (if flag1 0 (make-rectangular 1 a))
       (if flag2 1 (make-rectangular 1 a))))

一般に、immutableなオブジェクトは、内容さえ同じなら、一度作ったものを使いまわそうが必要になる度に作ろうが関係ない(区別する必要がない)のだ。 (詳しくはHenry Bakerの"Equal Rights for Functional Objects or, The More Things Change, The More They Are the Same"参照)

そして、手続きというのはimmutableなオブジェクトである。 え、クロージャはmutableな状態を持ち得るじゃん、と思うかもしれないが、 mutableなのはクロージャが閉じ込んでいる環境の方で、手続きオブジェクト自体ではない。

struct procedure {
   environment * const e;
   const code * const c;
};

procedure->e の指してる先がmutableであっても、 構造体procedureはimmutableであって構わないわけ。

手続き自体がimmutableであるとしておくと、自由にコピーを作ったり、 あるいは中身が同じであるとわかる場合にひとつの実体にまとめてしまったり できるので、とても都合が良い。例えば次のコードであるが:

(define (foo a)
  (let ((p (lambda (x) x)))
    (bar p)))

pの実体はローカル環境を参照していないので、何度fooが呼ばれようが 全く同じ動作をする。従って次のように変換することで、fooを呼ぶ度に 手続きの実体をアロケートせずに済む。これはlambda liftingという変換の 基本的な場合で、Gaucheでもやっている。

(define G0 (lambda (x) x))

(define (foo a)
  (bar G0))

なお、「手続きオブジェクト」に色々な属性を後からつけられるようにしている 言語があるが、それをすると手続きはmutableなオブジェクトになってしまい、 多くのコンパイル時最適化手段が封じられてしまう。 一般的な実装では、手続きの定義箇所が実行される度に手続き実体をアロケート しなければならない。属性が変更され得るということは、「前回作られた手続き」 と「今回作られた手続き」が後から区別され得るということだから。

手続きに、ソースコード情報やら引数情報やらの属性を持たせるのはよくやることで、 処理系実装者としては「じゃあついでに任意の属性を後からでもつけられるように したら便利じゃね?」とかついつい考えがちなんだけど、そういう落とし穴もある。

閑話休題。

immutableなオブジェクトは実体がいくつあろうが関係ない、 というのは、オブジェクトの比較を実体のアドレスではなく内容で行うからだ。 Gaucheは複素数をヒープにアロケートするけれど、複素数の比較(eqv?)は 虚部と実部の等価性で判断するので、実体がメモリ上でもひとつなのか 別々なのかは気にする必要はないし、本来区別できない。

手続きがimmutableなら、手続きも内容で比較するのが正しい。はず、なのだけれど。 手続きの実体が上に書いたstruct procedureだと分かってるなら、 procedure->eとprocedure->cをそれぞれポインタ比較すれば 内容の比較になりそうだけれど、「言語仕様」としてはそこまで実装にべったりの 定義をしたくないわけだ。

クロージャの実装方法のバリエーションはいくらでもある。変更可能な 環境へのポインタを持つかわりに、環境のコピーを自分で持っておいて、 変更可能な部分だけをboxingしてあるかもしれない。 また、コード部分だって最適化の実装次第では「メモリ上では別の実体」 となっている可能性がある。実装の自由度を許容したまま「内容の等価性」を 定義することは非常に難しい。

かといって、実装に全く立ち入らずに「外から見て等しい動作をする手続きは等価である」 とするのも困る。「外から見て等しい動作をするかどうか」は 決定可能とは限らないからだ。

というわけで、手続きの等価性というのはかように面倒くさい問題で、 R6RSではそこそこ紛糾した結果として、「たとえ同じlambda式呼び出しで 作られたように見える手続きでも、等価かどうかは決めない」という選択をした。

ただねー、やっぱり

(let ((p (lambda (x) x))) (eqv? p p))

が未定義というのはどうも落ち着かない。 こういうコードを直接書くことはないにせよ、 pをハッシュテーブルやalistに入れて後で比較したりってことはあり得る。

そこでR7RSでは「コード上の起源が同じ手続きは同じ(eqv?)とする」とした。 上にあげたような最適化をやりたい場合は、 コード上のlambda式の評価で作られる手続きに実体の位置を示すtagを つける、という考え方で説明できる。概念的にはこんな感じ:

(define (foo a flag1 flag2)
  (let* ((tag (make-location-tag))
         (p (lambda-with-tag tag (x) (+ x a))))
    (bar (if flag1 identity p)
         (if flag2 identity p))))

これで、同じtagを持てばeqv?である、ということにする。 これならlambda式自体が複製されても等価性は変わらない。

(define (foo a flag1 flag2)
  (let ((tag (make-location-tag)))
    (bar (if flag1 identity (lambda-with-tag tag (x) (+ x a)))
         (if flag2 identity (lambda-with-tag tag (x) (+ x a)))))

但し、と大急ぎでつけたすけれど、R7RSでも(lambda (x) x)の 実体をシングルトンにして共有することは許されてるんで、 上のtagを使った形式はあくまで「実際に手続きの実体がアロケートされると わかってから」の話である。「コード上の起源が同じなら等しい」は 保証されるが、「コード上の起源が別なら等しくない」は保証されないってこと。

Tags: Programming, Scheme, Gauche, R6RS, R7RS