Reverseパターン

JavaScript programming

非純粋関数を合成可能な擬似純粋関数にするデザインパターン。非純粋関数の返り値を逆操作関数にすることで疑似純粋化し逆操作関数を無引数無返り値に統一することで合成可能化する。操作は逆操作により副作用を残さず中止および終了され複数の操作はArrow演算により単一の操作に合成される。

function proc(): () => void {
  return aggregate(
    bind(el, type, listener),
    bind(el, type, listener));
}

function bind(el, type, listener): () => void {
  el.addEventListener(type, listener);
  return () => el.removeEventListener(type, listener);
}

function aggregate(...as: (b => c)[]): b => c[] {
  return b => as.map(f => f(b));
}

https://github.com/falsandtru/spica/blob/master/src/arrow.test.ts

2020-04-21

ゼロトラストセキュリティの基本概念

security

境界防御からゼロトラストセキュリティへの変遷を通してゼロトラストセキュリティの基本概念を解説する。

境界防御

水際防御とも呼ばれる境界防御は概ね単一かつ唯一の防衛線を設置しこの最終防衛線を死守するセキュリティモデルである。一度でも突破されればもはや守るもののない一度たりともミスの許されない脆弱なセキュリティモデルでありトロイの木馬により容易に内部に侵入できるITセキュリティと極めて相性が悪い。

多層防御

セキュリティに何よりも求められるのは侵入の検知から対処までの時間的猶予である。多層防御は複数の防衛線を設置し可能な限り外側の防御線で早期に侵入を検知することでさらに内側の防御線の突破に要する時間を対処までの時間的猶予に変えるものでありその概念は縦深防御との同一性から容易に理解できる。しかしながらトロイの木馬による侵入容易性に対する解決にはならず内側の未突破の防衛線以外に基本的に侵入および展開を遮るものがないため侵入箇所より内側の防衛線より外側すべてが侵害可能範囲となり致命的ではなくとも非常に大きい被害が生じる可能性が高い。

ゼロトラストセキュリティ

ゼロトラストセキュリティは微視的には多層防御の縦の防御に横の防御と内側への防御を加えるものであり、全ノードが全周防御、いわば要塞化することでこれを実現し被害の周辺部への拡大を防ぎ局所化するセキュリティモデルである。巨視的には侵入者が重要部を制圧するまでに突破する必要のある防衛線の数と強度を十分に確保できるノード配置および動線の設計であり、被害の局所化はその効果、全（周辺）ノードのセキュア化はその前提である。

ゼロトラストセキュリティは本土防衛戦争と解釈すると理解しやすい。侵入者は国内に侵攻または国内で武装蜂起した敵軍であり我が方は首都の防衛成功を勝利条件とする。首都防衛を達成するためには侵攻および蜂起箇所から首都までの間に防衛線を設置しここで食い止める必要がある。ゼロトラストセキュリティにおいて防衛線はサーバーおよびネットワーク機器等の各ノードが個々に展開する多層防御でありこれは要塞化された都市に相当する。我が方は敵軍が首都を制圧するまでに可能な限り多くの要塞都市を経由させることで可能な限り多くの防衛線の突破を強いなければならず、よって要塞都市を迂回できる街道のごときいかなる物理的・電子的経路もあってはならない。ここから一部の部門でだけゼロトラストセキュリティを導入して要塞化しても他の要塞化されてない部門を突破して中心部へ侵攻できるため意味がなく、終着地である首都に相当する部門は必ず要塞化し防衛線を設置しなければならないことがわかる。また重要部では防衛線を迂回して都市へ侵入できないよう検問も実施しなければならない。企業の提案するゼロトラストセキュリティおよびその製品は基本的にこうした各都市の要塞化や検問ための装備にすぎず最終目標である首都防衛のための総合的防衛戦略ではないことに注意しなければならない。なお要塞による拠点防衛は軍事的には縦深防御から退化しているがITにおいては距離と補給の制約がないなど各種前提の相違から有効なものである。要塞は実世界では火砲の的だがITにおける火砲であるDDOSはインターネットに接続した一部の端末を潰すだけで陽動や拘束程度にしかならず、事業的にはともかくセキュリティ上の脅威度は低い（社内業務のための予備系統を利用できる場合）。ITにおいて脅威なのは巡航ミサイルによる中枢部への精密攻撃のようなものであり強いて言えば各都市にはこの発見および撃墜も期待される。閑話休題。

このように構築した都市と国家を俯瞰すると敵軍にはより多くの都市を経由させなければならず、都市はすべて防衛線を持つよう要塞化されていなければならず、もって敵軍が首都を制圧するために突破しなければならない防衛線を最大限多くかつ強固にするのがゼロトラストセキュリティの本質たる基本概念であることがわかる。逆に首都制圧までに突破を強いる防衛線の数と強度を勘案せず単にセキュリティ製品を購入し装備するとそのセキュリティ強度は首都との間に偶然存在する防衛線の数および強度に依存する確率的で非効率な信頼性の低いものとなる。ゼロトラストセキュリティを導入し全ノードをセキュア化したが結局少なくともいくつの防衛線および検問が必ず機能する機会が確保されているかおよびこのセキュリティレベルで十分であるかが明確でない場合がこれに該当する。

2020-03-07

データ構造のJavaScriptにおける実際

JavaScript

結論から書くとLinked ListはO(1)の操作を大量に行わない限りArrayの方が圧倒的に早く、Setに負けることすらある。Treeでも要素数1000以下では.indexOfが速すぎてArrayのほうが速い可能性が高い（特にHeap）。

まずオブジェクトの生成の時点でListは大幅に遅く不利でありこの出だしの遅れを操作コストの優位で挽回する形となるため基本的に生成コストの差でArrayのほうが圧倒的に速く、Setに追いつくのにすら数回の操作を要する（生成を直接測定するとArrayの4分の1程度の速度だが他のオブジェクト内だと最適化が外れて大幅に速度低下しやすい？）。またListはループ系構文の遅さから走査が遅いため原則として要素の最後の取り出し以外でO(n)の操作を行ってはならない。具体的には要素数1000程度のArrayの.indexOfによる走査速度は要素の参照のような単純な式や文と同等から10分の1程度という驚異的な速さだが素朴にループを回すと単純にループ回数に比例した時間がかかり100〜1000倍近い時間を要する。逆に要素数がほとんどの場合1,2個程度かつ任意の要素を削除可能なキューとしてはSetがArrayより2倍以上速い（意味がわからない）場合があり5個程度で逆転する。ライフサイクル全体で見ればLinked Listは静的なStackやQueueなどごく少数の用途において最速となるのみであり、原則として最大限Arrayに適した設計をしArrayを使うよう努力することがその他の適切なデータ構造の選択に勝る。 Tree構造も同じ根本的問題を共有していることからArrayを置換できる用途は限定的であると思われる。対数時間で走査できるようTree構造を実装しても要素数1000以下であればArrayで.indexOfしたほうが速いだろう。さらに廃棄されたオブジェクトがGCにかける負荷も実際の最適化では重要な考慮事項となり廃棄オブジェクトの参照のされ方の考慮や参照の明示的な削除を行わなければGCの負荷で実行速度が2〜4分の1に低下する場合がある。こうした問題は内部で最適化されたビルトインAPIとの実行性能の格差に由来することからチューニング済みのビルトインの標準ライブラリが提供されれば理論上適したデータ構造を実際に採用して実行速度を向上させられるようになるだろう。

追記 indexOfで実際のコードを高速化しようとするとうまくいかない。単体ベンチマークのスコアはメモリ上の局所性によるもので他の処理が挟まると局所性が失われるからかもしれない。しかし多少はループより速い。参照削除の効果は実コードでも明瞭に確認できる。

2019-08-10

Haskellの非実用性

Haskell

IDEなどの開発支援機能を使用できない場合が少なくない
- .chsファイルへの非対応
- 実際的な広いユースケースで現代的なプログラミングを実現できておらずインタラクティビティの低い原始的なプログラミングを強いられる
ビルドが長すぎる(1時間前後)
- 脆弱性修正の数分以内の緊急デプロイといったセキュリティ要件を満たさない
- ダウンタイムがビルド時間に応じて長時間化することで繁忙期などに発生した重大問題が甚大な機会損失および信用失墜に発展するリスクが非常に高い
- アップデートやデバッグなどにともなう長時間のリビルドによる人員設備等の稼働率低下による損失が大きすぎる
- 勤怠状況の不明瞭化による勤怠管理の困難化が怠業を誘発し周辺人員への悪影響などの周辺問題の連鎖的発生と拡大につながる構造的問題が生じる
レコードフィールド名に非現実的な制約がある
- 外部スキーマとの互換性の問題が不可避的
- ソースコードのエントロピーがフィールド名に限って悪化する

以上の理由からサービス開発へのHaskellの使用を放棄した。

Haskellは以前はプロダクションレディだったかもしれないが今は少なくともサービス開発においてはそうではない。一度プロダクションレディになれば永遠にプロダクションレディでいられるわけではない。実用言語であり続けるためにはプログラミングの進歩とこれにともなう要件の変化に継続的に追従する必要がある。

補足
当然ながらコンテナOSで実行するためスタティックリンクが必須となる。オプションを変えてテストする成果物とデプロイする成果物を変えるなど論外。 CIサーバーのキャッシュは小規模な実験的プロジェクトでも簡単に数ＧＢに達してあふれるので無意味。キャッシュできたとしても依存関係やStackのアプデごとに1時間かけて再構成しなければならず変化に極めて脆弱で気休め程度にしかならない。ローカルビルドとリモートビルドに1時間ずつかかるような試行錯誤が困難で触りたくないと思われるコードベースや開発環境のプロダクトは死んだプロダクトだということを念頭に置かなければならない。

2018-12-29

Haskellの差分リストはなんちゃって差分リストではないか？

Haskell

Haskellの差分リストは一般に([1,2,3] ++) . ([4,5,6] ++)のようにセクションで示される。しかしこれは連結の際に左側のリストの要素をたどって末尾を見るので計算量がリストの長さに比例して増加しO(n)となる。一方CTMCP(コンピュータプログラミングの概念・技法・モデル)では要素をたどらず直接末尾を見るので計算量がリストの長さに比例して増加せずO(1)となる実装がOzにより示され、そしてこの効率性が差分リストの特徴とされている。Haskellも遅延評価の場合は連結コストが使用時のコストに同化されO(1)となるかもしれないが正格評価の場合は連結時に直ちにO(n)のコストを支払わなければならず、さらにこの状況は完全な正格評価でなくともデータが正格あるいは評価済みであるだけでも生じるため遅延評価の中でも無縁な話ではない。これは本当に差分リストとして説明してよいのだろうか？どうも過日のなんちゃってクイックソートと同じ種類の誤りを含んでいるように見える。

そういえばHaskellの差分リストについて気になることがあったのを思い出したのでアドカレのネタに書いてみた。

議論の結果、Haskellの差分リストがO(n)で非効率となる状況は連結演算まで正格となる状況まで限定できそうであるという結論になった。つまり差分リストの問題点は指摘のとおりだが正格性依存な分クイックソートよりはマシ。

Haskellの差分リストはなんちゃって差分リストではないか？ : haskell_jp

2018-12-19

AsyncIteratorとPromiseによるObservablePromise抽象

TypeScript

ObservablePromiseはAsyncIterableインターフェイスを実装することで途中状態を取得可能にしたPromiseである。ObservablePromiseの最大の利点は非同期の途中状態と最終状態という意味的に異なる状態の分離をfor-awaitとasync/awaitという言語抽象レベルで行うことで標準的な形でこれを区別して扱えることであり、その内部表現もまた言語抽象であるAsync generatorで標準にのっとり簡潔に記述できる。

ObservablePromise抽象はコルーチンと親和性が高いためここではObservablePromiseをコルーチンとして実装した。ただしコルーチンの操作的基本機能であるsuspend/resumeはJavaScriptでは実用性が低いためプロパティを通してポートオブジェクトの形で追加的に提供する*1。ObservablePromiseは次のような表現を可能にする。なおこのコルーチンはCancelableでもあるためより正確にはCancelableObservablePromiseであり、単なるCancelablePromiseとしても有用性が高い。また基底のPromiseには同期Promiseを使用しておりコルーチンの生死判定とその事後処理は遅延なく同期的に行われる。

    it('terminate', done => {
      let cnt = 0;
      const co = new Coroutine(async function* () {
        assert(cnt === 0 && ++cnt);
        return 0;
      });
      co.finally(() => {
        assert(cnt === 1 && ++cnt);
      });
      co[Coroutine.terminator]();
      assert(cnt === 2 && ++cnt);
      co[Coroutine.terminator](1);
      co.catch(done);
    });

    it('iterate', async () => {
      let cnt = 0;
      const co = new Coroutine<number, number>(async function* () {
        assert(++cnt === 1);
        assert(undefined === (yield Promise.resolve(2)));
        assert(undefined === (yield Promise.resolve(3)));
        await wait(100);
        assert(undefined === (yield Promise.resolve(4)));
        return Promise.resolve(5);
      });
      assert(cnt === 1);
      for await (const n of co) {
        assert(n === ++cnt);
      }
      for await (const _ of co) {
        assert(false);
      }
      assert(await co === ++cnt);
      assert(cnt === 5);
    });

https://github.com/falsandtru/spica/blob/master/src/coroutine.test.ts

XMLHttpRequestはObservablePromiseで表現することで非常に簡潔になる。

    it('basic', async () => {
      const co = cofetch('');
      for await (const ev of co) {
        assert(ev instanceof ProgressEvent);
        assert(['loadstart', 'progress', 'loadend'].includes(ev.type));
      }
      assert(await co instanceof XMLHttpRequest);
    });

https://github.com/falsandtru/spica/blob/master/src/cofetch.test.ts

このようにObservablePromiseは優れた抽象表現でありその標準性から一般に推奨できるものである。ただしNode.jsが非同期APIにPromiseを採用しなかったようにパフォーマンス上の問題が生じる場合はこの限りではない。また2018年12月時点ではEdgeでAsyncIteratorが未実装であるためブラウザではもうしばらく待つ必要がある。そのほか、自身はコルーチンの管理にSupervisorを使用してプロセス管理の煩雑さを低減している。そしてこのSupervisorもまたコルーチンである。

*1:このコルーチンは入力のキューのサイズが0のときは入力を取らず自動で非同期イテレーションを回し、1以上のときは入力の都度イテレーションを回すことで自動手動両方のイテレーション方法に対応している。

2018-02-07

TypeScriptで型レベル関数とRequired/DeepRequired型を作って型レベルプログラミング

TypeScript

TypeScript 2.8で追加予定のConditional型とinfer prefixが開発版でリリースされたので型レベル関数と念願のRequired/DeepRequired型を作って型レベルプログラミングを可能にする。

型レベル関数

Conditional型はUnion型を展開するためEq<false, boolean>の結果はその非決定性からbooleanとなる。決定的な結果を返す関数はboolean型にのみ用意しておりDEq<false, boolean>はundefinedとなる。

type Falsy = undefined | false | 0 | '' | null | void;
type Function = (...args: any[]) => any;
type Class = new (...args: any[]) => any;

export type Not<T extends boolean> =
  T extends true ? false :
  T extends false ? true :
  never;
export type And<T, U> = T extends Falsy ? T : U;
export type Or<T, U> = T extends Falsy ? U : T;
export type Eq<T, U> = T extends U ? U extends T ? true : false : false;
export type If<S, T, U> = S extends Falsy ? U : T;
export type Case<T extends keyof U, U extends {}> = U[T];

export type DEq<T extends valueof<NondeterminateTypeMap>, U extends valueof<NondeterminateTypeMap>> =
  Determine<T> extends undefined ? undefined :
  Determine<U> extends undefined ? undefined :
  Eq<T, U>;
type Determine<T extends valueof<NondeterminateTypeMap>> =
  valueof<NondeterminateTypeMap> extends T ? undefined :
  T;
interface NondeterminateTypeMap {
  boolean: boolean;
}

export type keyof<T, V = any> = { [P in keyof T]: If<Eq<T[P], V>, P, never>; }[keyof T];
export type valueof<T, K = string> = { [P in keyof T]: P extends K ? T[P] : never; }[keyof T];

  describe('Eq', () => {
    it('', () => {
      assert((): true => true as Eq<true, true>);
      assert((): false => true as Eq<true, false>);
      assert((): false => true as Eq<false, true>);
      assert((): true => true as Eq<false, false>);
      assert((): Eq<true, boolean> => true as boolean);
      assert((): Eq<false, boolean> => true as boolean);
      assert((): Eq<boolean, true> => true as boolean);
      assert((): Eq<boolean, false> => true as boolean);
      assert((): Eq<boolean, boolean> => true as boolean);
      assert((): true => true as Eq<0, 0>);
      assert((): false => true as Eq<0, number>);
      assert((): true => true as Eq<number, number>);
      assert((): true => true as Eq<undefined, undefined>);
      assert((): false => true as Eq<void, undefined>);
      assert((): false => true as Eq<void, null>);
      assert((): false => true as Eq<void, undefined | null>);
      assert((): true => true as Eq<void, void>);
    });

  });

  describe('If', () => {
    it('', () => {
      assert((): 1 => 0 as If<true | 1, 1, 0>);
      assert((): 0 => 0 as If<false | 0, 1, 0>);
    });

  });

  describe('Case', () => {
    it('', () => {
      assert((): 1 => 0 as Case<'0', [1]>);
      assert((): 1 => 0 as Case<'0', { 0: 1 }>);
      assert((): number => 0 as Case<'1', { 0: 1, [otherwise: string]: number }>);
    });

  });

  describe('DEq', () => {
    it('', () => {
      assert((): true => true as DEq<true, true>);
      assert((): false => true as DEq<true, false>);
      assert((): false => true as DEq<false, true>);
      assert((): true => true as DEq<false, false>);
      assert((): undefined => undefined as DEq<true, boolean>);
      assert((): undefined => undefined as DEq<false, boolean>);
      assert((): undefined => undefined as DEq<boolean, true>);
      assert((): undefined => undefined as DEq<boolean, false>);
      assert((): undefined => undefined as DEq<boolean, boolean>);
    });

  });

Requiredなど

Deep系は除外するオブジェクトを指定できるので必須と任意を組み合わせたりDOM要素などの組み込みオブジェクトを持つオブジェクトにも使用できる。

export type Partial<T> =
  T extends object
    ? { [P in keyof T]?: T[P]; }
    : T;
export type DeepPartial<T, U extends object | undefined = undefined> =
  T extends object
    ? { [P in keyof T]?: NonNullable<T[P]> extends NonNullable<U | Function | Class> ? T[P] : DeepPartial<T[P], U>; }
    : T;
type Purify<T extends string> = { [P in T]: P; }[T];
export type Required<T> =
  T extends object
    ? { [P in Purify<keyof T>]: NonNullable<T[P]>; }
    : T;
export type DeepRequired<T, U extends object | undefined = undefined> =
  T extends object
    ? { [P in Purify<keyof T>]: NonNullable<T[P]> extends NonNullable<U | Function | Class> ? NonNullable<T[P]> : DeepRequired<NonNullable<T[P]>, U>; }
    : T;
export type Readonly<T> =
  T extends object
    ? { readonly [P in keyof T]: T[P]; }
    : T;
export type DeepReadonly<T, U extends object | undefined = undefined> =
  T extends object
    ? { readonly [P in keyof T]: NonNullable<T[P]> extends NonNullable<U | Function | Class> ? T[P] : DeepReadonly<T[P], U>; }
    : T;

  describe('Partial', () => {
    it('', () => {
      type R = { a: number; b: { c: string; }; d: () => 0; e: new () => object };
      type P = { a?: number; b?: { c: string; }; d?: () => 0; e?: new () => object };
      assert((): P => ({}) as Partial<R>);
      assert((): Partial<R> => ({}) as P);
      assert((): P => ({}) as Partial<Required<R>>);
      assert((): Partial<Required<R>> => ({}) as P);
    });

  });

  describe('DeepPartial', () => {
    it('', () => {
      type R = { a: number; b: { c: string; d: () => 0; e: new () => object }; };
      type P = { a?: number; b?: { c?: string; d?: () => 0; e?: new () => object }; };
      assert((): P => ({}) as DeepPartial<R>);
      assert((): DeepPartial<R> => ({}) as P);
      assert((): P => ({}) as DeepPartial<R>);
      assert((): DeepPartial<R> => ({}) as P);
      assert((): Partial<R> => ({}) as DeepPartial<R, R['b']>);
      assert((): DeepPartial<R, R['b']> => ({}) as Required<R>);
    });

  });

  describe('Required', () => {
    it('', () => {
      type R = { a: number; b: { c?: string; }; d: () => 0; e: new () => object };
      type P = { a?: number; b?: { c?: string; }; d?: () => 0; e?: new () => object };
      assert((): R => ({}) as Required<P>);
      assert((): Required<P> => ({}) as R);
      assert((): R => ({}) as Required<Partial<R>>);
      assert((): Required<Partial<R>> => ({}) as R);
    });

  });

  describe('DeepRequired', () => {
    it('', () => {
      type R = { a: number; b: { c: string; d: () => 0; e: new () => object }; };
      type P = { a?: number; b?: { c?: string; d?: () => 0; e?: new () => object }; };
      assert((): R => ({}) as DeepRequired<P>);
      assert((): DeepRequired<P> => ({}) as R);
      assert((): R => ({}) as DeepRequired<DeepPartial<R>>);
      assert((): DeepRequired<DeepPartial<R>> => ({}) as R);
      assert((): Required<P> => ({}) as DeepRequired<P, P['b']>);
      assert((): DeepRequired<P, P['b']> => ({}) as Required<P>);
    });

  });

  describe('Readonly', () => {
    it('', () => {
      type I = { readonly a?: number; readonly b: { c: string; }; readonly d: () => 0; readonly e: new () => object };
      type M = { a?: number; b: { c: string; }; d: () => 0; e: new () => object };
      assert((): I => ({}) as Readonly<M>);
      assert((): Readonly<M> => ({}) as I);
    });

  });

  describe('DeepReadonly', () => {
    it('', () => {
      type I = { readonly a?: number; readonly b: { readonly c: string; readonly d: () => 0; readonly e: new () => object }; };
      type M = { a?: number; b: { c: string; d: () => 0; e: new () => object }; };
      assert((): I => ({}) as DeepReadonly<M>);
      assert((): DeepReadonly<M> => ({}) as I);
      assert((): Readonly<M> => ({}) as DeepReadonly<M, M['b']>);
      assert((): DeepReadonly<M, M['b']> => ({}) as Readonly<M>);
    });

  });

型レベルプログラミング

非決定性計算がはかどりそうな気がするがお題が浮かばなかった。

https://github.com/falsandtru/spica/blob/master/src/lib/type.ts https://github.com/falsandtru/spica/blob/master/src/lib/type.test.ts