見出し画像

【TypeScript】式木の美しき表現【出題編】

SHIFT Group 技術ブログ

こんにちは、SHIFTビジネスプロセスアウトソーシンググループに所属しているShunkiです。 運用関連のお仕事でご飯を食べさせてもらっています。 プログラミングに関する理論を調べて遊ぶのが趣味の1つです。 遊ぶさいはMicrosoftが誇るプログラミング言語、TypeScriptをよく使っています。

この記事は、題名の通り【TypeScript】に関する問いを【出題】します。
下記4つの型関数と1つの関数を使ったコードをお見せするので、その型関数と関数の仕様を類推して実装せよ、というのが問いになります。
我こそはという方は、ぜひ挑戦してみてください。

  • 型関数

    • Poly.Schema

    • Poly.Diagram

    • Poly.Fix

    • Poly.Cata.When

  • 関数

    • Poly.Cata.caseOf

なお、これからお見せするコードはThe Expression Problemを題材として扱っています。 背景知識として、The Expression Problemを抑えておくと、解答しやすくなるかもしれません。

また、Polyの名称は型理論における多項式関手（polynomial functor）を意識したものです。 そして、Fixは自己関手の不動点、Cataは自己関手の始代数からの準同型であるcatamorphismを意識しています。 そのため、これらの専門用語を調べておくと、解答がしやすくなるかもしれません。

ただし、FixとCataがPolyの名前空間に入っているのは、多項式関手に特化したそれぞれの実装があれば十分であることを表しています。 つまり、一般の自己関手ではなく、多項式関手の不動点と、多項式関手の始代数からの準同型があれば、解答するには十分と言うことです。

また、名前空間（namespace）を使っているのは、プログラムのコード片を記事で示すさいに、一々ファイル名やimport文を明示するのが煩わしいという理由からです。もちろん解答の際は、ファイルを分けて構いません。

仕様を類推するためのコード

まずは、4つの型関数と1つの関数の使用例をお見せします。 具体的には、真理値（true、false）と論理積（&&）や否定（!）からなる論理式を表す抽象構文木（AST; abstract syntax tree）について、構造と解釈を定義したり、拡張したりします。 その使用例から仕様を類推し、4つの型関数と1つの関数を実装してみてください。

構造の定義

この節では、型関数Poly.Schema、Poly.Diagram、Poly.Fixを使って、真理値と論理積からなる抽象構文木の構造を定義しています。つまり、これら３つの型関数は木構造全般を定義するのに便利な型関数と言うことです。

概観を述べておくと、AST1.Treeは葉にboolean型の値を持つ2分木になります。 このとき、葉（外部頂点）が名前空間Val内で定義されており、内部頂点が名前空間And内で定義されています。 ただし、2分木に対する解釈が与えられていないため、ValとAndが何を意味するのか、ここではまだコーディングされていません。

namespace Val {
  export type Schema = Poly.Schema<"val", boolean, never>;

  type Make = (value: boolean) => Poly.Diagram<Schema, unknown>;
  export const make: Make = a => ({ i: "val", a, x: {} });
}

namespace And {
  export type Schema = Poly.Schema<"and", undefined, "lhs" | "rhs">;

  type Make = <X>(lhs: X, rhs: X) => Poly.Diagram<Schema, X>;
  export const make: Make = (lhs, rhs) => ({ i: "and", a: undefined, x: { lhs, rhs } });
}

namespace AST1 {
  export type Schema = Val.Schema & And.Schema;
  export type Tree = Poly.Fix<Schema>;
  export const val = Val.make;
  export const and = And.make<Tree>;
}

namespace AST1 {
  namespace Example {
    // AST1-Example-Tree
    const t0: Tree = val(false); // false
    const t1: Tree = val(true); // true
    const t2: Tree = and(val(false), val(true)); // false && true
    const t3: Tree = and(and(val(false), val(true)), val(false)); // (false && true) && false
  }
}

ValとAndはお互いを直接参照せずに実装されている点に注意してください。 ただし、内部頂点であるAndは子として外部頂点Valを持つ可能性があるため、Valの情報を後から入手する必要があります。 上記では、And.make<Tree>のTreeから入手しています。 経路を丁寧に追っていくと、AST1.Treeの定義にAST1.Schemaが使われており、AST1.Schemaの定義にVal.Schemaが使われているため、And.makeはVal.Schemaの情報を入手できるわけですね。

また、AST1.Schemaの定義で、&（intersection type）が使われていることにも注意してください。 このことから、Poly.Schemaはオブジェクト形式の型{ ??? }を生成することが予想できます。 しかし、よく知られている通り、TypeScriptで2分木を定義するのであれば|（union type）、特に判別可能なユニオン型 (discriminated union)が使われるはずです。 したがって、オブジェクト形式の型からユニオン型を作るテクニックが必要になります。 そのようなテクニックを知らない場合は、keyof型演算子とインデックスアクセス型（Indexed Access Types）について調べてみるとよいでしょう。

解釈の定義

この節では、型関数Poly.Cata.Whenと、関数Poly.Cata.caseOfを使って、真理値と論理積からなる抽象構文木の解釈を定義しています。 つまり、これらの（型）関数は木構造全般を解釈するのに便利な（型）関数と言うことです。

概観を述べておくと、AST1.evaluateは抽象構文木を論理式として解釈する関数になります。 このとき、Valは真理値として解釈され、Andは論理積として解釈されます。 そもそも、そのように意図して構造を定義していたわけですが、下記のような解釈が与えられない限り、ValもAndも単なる2分木の頂点でしかありません。 解釈と共にValとAndの意味がコーディングされます。

namespace Val {
  type Evaluate = Poly.Cata.When<Schema, boolean>;
  export const evaluate: Evaluate = { val: v => v };
}

namespace And {
  type Evaluate = Poly.Cata.When<Schema, boolean>;
  export const evaluate: Evaluate = { and: (_, { lhs, rhs }) => lhs && rhs };
}

namespace AST1 {
  type Evaluate = (tree: Tree) => boolean;
  export const evaluate: Evaluate = Poly.Cata.caseOf<Schema, boolean>({
    ...Val.evaluate,
    ...And.evaluate
  });
}

namespace AST1 {
  namespace Example {
    console.log("AST1-Example-evaluate");
    console.log(evaluate(val(false))); // => false
    console.log(evaluate(val(true))); // => true
    console.log(evaluate(and(val(false), val(false)))); // => false
    console.log(evaluate(and(val(false), val(true)))); // => false
    console.log(evaluate(and(val(true), val(false)))); // => false
    console.log(evaluate(and(val(true), val(true)))); // => ture
  }
}

解釈においても、お互いを直接参照せずにValとAndが実装されている点に注意してください。 これは、子要素が必ず先に解釈されることで実現されています。

例えば、抽象構文木の内部頂点としてAndを見た時、lhsとrhsは子要素（Tree型の値）のはずです。 ところが、And.evaluateの実装では、lhs && rhsとあるように、lhsとrhsは真理値（boolean型の値）となっています。 ここから、Andが解釈されるより前に子要素が解釈されていることがわかるはずです。 Andは、子要素が解釈された結果のみを参照して、言い換えれば子要素の具体的な構造（Valなどの構造）を直接参照することなく、自身の解釈を定義できています。

なお、子要素から解釈が進む順序性はcatamorphismの性質から来るものです。 実装がよく想像できない場合は、catamorphismについて調べるとよいでしょう。

ただし、Val.evaluateとAnd.evaluateのように分離されている関数を統合する機能は、catamorphismとは無関係です。 これは判別可能なユニオン型のみを引数に取る関数の性質から来ています。 雑に述べると、反変Hom-関手は余積と積を交換できるので、分離された関数の積から、引数が余積となるような一つの関数へまとめあげることが可能です。 しかし、理論的に成り立つからと言って、TypeScriptの型検査を簡単に突破できるとは限りません。 そのため、分離された関数を統合する部分については実装をお見せしておきます。

namespace Poly {
  export type When<S extends Schema, X, Y> = { readonly [i in keyof S]: (a: S[i]["a"], x: Pow.Diagram<S[i]["n"], X>) => Y };

  type CaseOf = <S extends Schema, X, Y>(when: When<S, X, Y>) => (poly: Diagram<S, X>) => Y;
  export const caseOf: CaseOf = f => ({ i, a, x }) => f[i](a, x);
}

注意として、Poly.WhenとPoly.Cata.Whenは異なる型関数です。 また、Poly.caseOfとPoly.Cata.caseOfは異なる関数です。 ただし、Poly.Cata.WhenはPoly.Whenを用いて実装して構いませんし、Poly.Cata.caseOfもPoly.caseOfを用いて実装して構いません。 また、型関数Poly.Whenの実装を参考に、型関数Poly.SchemaとPoly.Diagramを実装して構いません。

構造の拡張

この節では、真理値と論理積に加えて、否定も含んだ抽象構文木の構造を定義しています。

概観を述べておくと、AST2.Treeは葉にboolean型の値を持ち、分岐数が1か2の木構造になります。 ただし、葉と分岐数が2の内部頂点を改めて定義する必要はありません。 ValとAndの定義が流用されます。 裏を返せば、分岐数が1の内部頂点としてNotの定義を加えれば、それだけで構造が拡張できてしまいます。

namespace Not {
  export type Schema = Poly.Schema<"not", undefined, "term">;

  type Make = <X>(term: X) => Poly.Diagram<Schema, X>;
  export const make: Make = term => ({ i: "not", a: undefined, x: { term } });
}

namespace AST2 {
  export type Schema = Val.Schema & And.Schema & Not.Schema;
  export type Tree = Poly.Fix<Schema>;
  export const val = Val.make;
  export const and = And.make<Tree>;
  export const not = Not.make<Tree>;
}

namespace AST2 {
  namespace Example {
    // AST2-Example-Tree
    const t0: Tree = not(val(false)); // !false
    const t1: Tree = not(val(true)); // !true
    const t2: Tree = and(not(val(false)), not(val(true))); // !false && !true
    const t3: Tree = not(and(val(false), val(true))); // !(false && true)
  }
}

AST2.Treeで構造を拡張しても、AST1.Treeは一切の影響を受けないことに注意してください。 また、AST1.evaluateも影響を受けず、実行時にエラーが発生することもなく、実行結果も変わりません。 つまり、影響が及ばないよう、4つの型関数と1つの関数を実装する必要があります。

解釈の拡張

この節では、真理値と論理積からなる抽象構文木に別の解釈を与えます。

概観を述べておくと、AST1.stringifyは抽象構文木を論理式を表す文字列として解釈する関数です。 このとき、Valは真理値を表す文字列として解釈され、Andは論理積を表す文字列として解釈されます。

もともとは単なる論理式としての解釈（AST1.evaluate）を意図して抽象構文木の構造は定義されていました。 つまり、この文字列としての解釈（AST1.stringify）は、意図していなかった解釈になります。 構造と解釈を分離しておくと、このように解釈を拡張できます。 極端に言ってしまえば、Valの真理値を反転させたり（trueをfalseに、falseをtrueに）、Andを論理和（||）として解釈することも可能です。

namespace Val {
  type Stringify = Poly.Cata.When<Schema, string>;
  export const stringify: Stringify = { val: v => v ? "true" : "false" };
}

namespace And {
  type Stringify = Poly.Cata.When<Schema, string>;
  export const stringify: Stringify = { and: (_, { lhs, rhs }) => `(${lhs} && ${rhs})` };
}

namespace AST1 {
  type Stringify = (tree: Tree) => string;
  export const stringify: Stringify = Poly.Cata.caseOf<Schema, string>({
    ...Val.stringify,
    ...And.stringify
  });
}

namespace AST1 {
  namespace Example {
    console.log("AST1-Example-stringify");
    console.log(stringify(val(false))); // => "false"
    console.log(stringify(val(true))); // => "true"
    console.log(stringify(and(val(false), val(true)))); // => "(false && ture)"
    console.log(stringify(and(and(val(false), val(true)), val(false)))); // => "((false && ture) && false)"
  }
}

AST1.stringifyを実装しても、AST1.evaluateは一切の影響を受けないことに注意してください。 また、AST1.Tree、AST2.Treeも影響を受けません。 つまり、影響が及ばないよう、4つの型関数と1つの関数を実装する必要があります。

構造と解釈の拡張

AST2.Treeでは、真理値と論理積に加えて、否定も含んだ抽象構文木に構造を拡張できました。 この節では、同じようにAST1.evaluateを拡張します。

概観を述べておくと、AST2.evaluateはAST1.evaluateと同様に抽象構文木を論理式として解釈する関数です。 このとき、真理値と論理積の解釈を改めて定義する必要はありません。 ValとAndの定義が流用されます。 裏を返せば、Notを否定として解釈する実装を加えることで、解釈が拡張されるということです。

namespace Not {
  type Evaluate = Poly.Cata.When<Schema, boolean>;
  export const evaluate: Evaluate = { not: (_, { term }) => !term };
}

namespace AST2 {
  type Evaluate = (tree: Tree) => boolean;
  export const evaluate: Evaluate = Poly.Cata.caseOf<Schema, boolean>({
    ...Val.evaluate,
    ...And.evaluate,
    ...Not.evaluate
  });
}

namespace AST2 {
  namespace Example {
    console.log("AST2-Example-evaluate");
    console.log(evaluate(not(val(false)))); // => true
    console.log(evaluate(not(val(true)))); // => false
    console.log(evaluate(and(not(val(false)), not(val(false))))); // => true
    console.log(evaluate(not(and(val(true), val(true))))); // => false
  }
}

AST2.evaluateを実装しても、これまでの定義と解釈はどれも影響を受けないことに注意してください。 つまり、影響が及ばないよう、4つの型関数と1つの関数を実装する必要があります。

追加のヒント

ヒントが不要であれば読み飛ばしてください。

最初に述べた通りPolyは多項式関手を意識しています。 多項式$${\textstyle\sum_{i∈S} a_i x^{n_i}}$$​の主要な構成要素は単項式$${a x^n}$$であって、さらに単項式の主要な構成要素はべき乗$${ x^n}$$です。 そのため、順序良く積み上げて実装していくのであれば、次のような流れで実装していくと良いでしょう。

  1. TypeScriptの型を対象、関数を射とする圏を考える（より正確には圏とみなすために必要な性質を持った型と関数のみを以降の議論では扱う）。

  2. べき乗関手を定義する（Pow.Schema、Pow.Diagram、Pow.mapを実装する）。

  3. 多項式関手を定義する（Poly.Schema、Poly.Diagram、Poly.mapをPowを使って実装する）。

  4. 多項式関手のF-代数が考えられることを確認する（代数は対象と射の組であるが、ここではそのうちの射のみ、さらにその射が属する型を作る型関数Poly.Algebraが実装できればよい）。

  5. 多項式関手の最小不動点を定義する（Poly.Fixを再帰型に関するエラーに注意しながら実装する）。

  6. 多項式関手のcatamorphismを定義する（Poly.cataをPoly.Algebra、Poly.Fix、Poly.mapを使って実装する）。

  7. 上で提示されたPoly.When、Poly.caseOfの型引数を限定すると、代数Poly.Algebraを構築できることを確認し、Poly.Cata.Whenを実装する。

  8. Poly.caseOfとPoly.cataを関数合成し、関数Poly.Cata.caceOfを実装する。

ただし、Pow.mapは安全な実装ができないので、これについてはコードをお見せしておきます。

namespace Pow {
  type Map = <X, Y>(xy: (x: X) => Y) => <S extends Schema>(pow: Diagram<S, X>) => Diagram<S, Y>;
  export const map: Map = f => x => {
    type Y = Diagram<keyof typeof x, ReturnType<typeof f>>;
    const y: Partial<Y> = {};
    for (const i in x) y[i] = f(x[i]);
    return y as Y;
  };
}

なぜ、上記のコードが安全でないか簡単に捕捉しておきます。 TypeScriptは構造的部分型を採用しているので、必要なプロパティの型さえ合っていれば、余剰なプロパティがあってもアップキャストに成功します。 アップキャストされると、余剰プロパティは型としては消えたように振る舞いますが、実行時には変わらず存在します。

なぜなら、原則としてTypeScriptは型情報がランタイムの挙動へ影響しないように設計されているからです。 型情報がアップキャストの影響を受けたとしても、ランタイム上の実際のオブジェクトはアップキャストの影響をまったく受けません。

つまり、余剰プロパティも残ったままになります。 そのため、ランタイム上の実際のオブジェクトからプロパティを列挙する場合、型情報からは見えない余剰プロパティも一緒に列挙される可能性があります。

上記のコードで具体的に言えば、iが想定外の値になるかもしれないということです。 したがって、上記のPow.map関数は安全ではありません。

とは言え、余剰プロパティが入り込まない限りは安全に使えます。 ここまで見てきたような、ASTの構造や解釈の実装の仕方であれば、心配しなくとも大丈夫でしょう。

発展問題：遅延評価を使った短絡評価

ここまでお見せしてきたコードの中で、Andを論理積として解釈するコードがありました。 その補足として、すべての子の解釈が終わってから、Andの解釈が開始されると述べました。 これは、短絡評価されないことを意味します。 もし、短絡評価されるのであれば、lhsがfalseと解釈された場合、rhsの解釈はスキップされるはずです。 しかし、lhsがfalseと解釈されたとわかったころには、すべての子の解釈も終わってしまっています。 つまり、rhsの解釈も終わっており、スキップはできません。

では、短絡評価が実現できないかと言うと、そうでもありません。 下記のコードで使っているような、型関数Poly.Lazy.Cata.Whenと関数Poly.Cata.lazyOfを実装できれば、短絡評価が再現できます。 LazyやlazyOfという名称からわかる通り、遅延評価をさせればよいということです。

TypeScript（JavaScript）のような正格評価が既定の言語で遅延評価したいのであれば、関数を使うのが手っ取り早いでしょう。 関手を関数へ変換するのであれば、表現可能関手としての性質を使うと良いかもしれません。
具体的には、Powの表現可能関手としての性質を活かせれば、型関数Poly.Lazy.Cata.Whenと関数Poly.Cata.lazyOfを実装できます。

まだまだ、物足りないという方は、ぜひとも実装に挑戦してみてください。

namespace Err {
  export type Schema = Poly.Schema<"err", undefined, never>;

  type Make = Poly.Diagram<Schema, unknown>;
  export const make: Make = ({ i: "err", a: undefined, x: {} });
}

namespace AST3 {
  export type Schema = Val.Schema & And.Schema & Err.Schema;
  export type Tree = Poly.Fix<Schema>;
  export const val = Val.make;
  export const and = And.make<Tree>;
  export const err = Err.make;
}

namespace And {
  export namespace Lazy {
    type Evaluate = Poly.Lazy.Cata.When<Schema, boolean>;
    export const evaluate: Evaluate = { and: (_, evaluate) => evaluate("lhs") && evaluate("rhs") };
  }
}

namespace Err {
  type Evaluate = Poly.Cata.When<Schema, boolean>;
  export const evaluate: Evaluate = { err: () => { throw new Error(); } };
}

namespace AST3 {
  type Evaluate = (tree: Tree) => boolean;
  export const evaluate: Evaluate = Poly.Cata.lazyOf<Schema, boolean>({
    ...Val.evaluate,
    ...And.Lazy.evaluate,
    ...Err.evaluate
  });
}

namespace AST3 {
  namespace Example {
    console.log("AST3-Example-evaluate");
    try { console.log(evaluate(and(val(false), err))); } catch { console.log("err"); } // => false
    try { console.log(evaluate(and(val(true), val(true)))); } catch { console.log("err"); } // => ture
    try { console.log(evaluate(and(val(true), err))); } catch { console.log("err"); } // => "err"
    try { console.log(evaluate(and(err, val(false)))); } catch { console.log("err"); } // => "err"
  }
}

執筆者プロフィール：Shunki
新卒で金融系のSIerで働き、途中、広告代理店の会社でふらふらした後、SHIFTへ入社。
プログラミングの理論面を調べて遊ぶのが趣味の人。２児の父。

《解答編はこちら》

お問合せはお気軽に
https://service.shiftinc.jp/contact/

SHIFTについて（コーポレートサイト）
https://www.shiftinc.jp/

SHIFTのサービスについて（サービスサイト）
https://service.shiftinc.jp/

SHIFTの導入事例
https://service.shiftinc.jp/case/

お役立ち資料はこちら
https://service.shiftinc.jp/resources/

SHIFTの採用情報はこちら
https://recruit.shiftinc.jp/career/

PHOTO：UnsplashのVystralith


最後まで読んでくださり、ありがとうございます！

御社サービスのご相談はお気軽に。
ソフトウェア品質のプロがお伺いします。