LoginSignup
45
38

More than 5 years have passed since last update.

@Kuniwak(Yuki Kokubun)in株式会社ディー・エヌ・エー

TypeScript のコンパイル時計算はどこまでできるのか？

Last updated at Posted at 2015-07-12

最近は仕事で TypeScript を書いています。この TypeScript は、コンパイルすると JavaScript にできるという特徴をもつ altJS と呼ばれる言語の仲間です。なかでも、推論つきの静的型検査がついていることが最大の特徴でしょう。

さて、話は変わりますが、プログラマは「コンパイル時計算」という言葉が大好きで、とくにうっかりチューリング完全になっちゃったものとかを見つけると、手を叩いて大喜びしたりするわけですね。

TypeScript にもコンパイル時計算があって、コンパイル時の型検査がそのひとつです。今回は、この型検査を利用して、どのレベルの計算機能までを実現できるのか試してみました。

結論からいうと、TypeScript のコンパイル時計算を使って組み合わせ回路を実現できました。

実証コードとして、コンパイル時 4bit 加算器をつくってみました。4bit 加算器は 7 + 7 までの足し算ができるデジタル回路の一種です。

コンパイル時 4bit 加算器のデモ

なお、チューリング完全には至っていません。現時点では再帰（またはループ）する方法を見つけることができませんでした。再帰の有無は、コンパイル時計算の停止性に関する重大な問題です。よく対策されていたということでしょう。

さて、この組み合わせ回路を組み立てるにあたって、3つの TypeScript の機能を使いました。

  • Call signature: 関数呼び出し可能な型の宣言。
  • Overload: Javaでおなじみ、引数の型によって、呼び出す関数を変える機能。
  • TypeQuery: 変数の型を型宣言で利用できるようにする機能。

これらを使って、どのようにコンパイル時 4bit 加算器をつくったのか解説していきます。

登場人物の説明

Call signature

Call signature を使うと、関数呼び出し可能な型を宣言できます。JavaScript の Function 型はインスタンス変数を定義できるのですが、これを素直に表現するために、この Call signature という構文がつくられたのでしょう。

// JavaScript は、関数にインスタンス変数を定義できる
var myFunc = function() { return 'foo'};
myFunc.bar = 'bar';

console.log(myFunc()); // 'foo'
console.log(myFunc.bar); // 'bar'

// これを Interface で表現すると、次のようになる
//   interface MyFunc {
//     (): string;
//     bar: string;
//   }

Overload

Java でおなじみの overload は、TypeScript でも使えます。

interface A1 {}
interface A2 {}
interface B1 {}
interface B2 {}

interface Overload {
  (value: A1): B1;
  (value: B2): B2;
}

// A1, A2 型をもつ変数を定義
let a1: A1;
let a2: A2;

// Overload 型の変数も定義しておく
let overload: Overload;

// A1 型が渡されているので、B1 型が返される
const b1: B1 = overload(a1);

// A2 型が渡されているので、B2 型が返される
const b2: B2 = overload(a2);

TypeQuery

TypeQuery を使うと、変数の型を型宣言に利用できます。

const variable = '';

// この場合、variable は文字列型なので、foo は文字列型になる
const foo: typeof variable = '';

実装ステップ

条件分岐を実装する

さて、これらを使って条件分岐を実装してみましょう。

interface A { }
interface B { }
interface ThenA { }
interface ThenB { }

// 分岐のための関数の型宣言
interface Switch {
  (val: A): ThenA;
  (val: B): ThenB;
}
let sw: Switch;

// A型がきたので、resultAの型は ThenA になる
let inputA: A;
let resultA = sw(inputA);

// B型がきたので、resultBの型は ThenB になる
let inputB: B;
let resultB = sw(inputB);

Call signature と Overload を使って、条件分岐が実現できていることがわかります。

条件分岐が実装できたということは、論理ゲートが実装できるようになったということです。論理ゲートの実装に移りましょう。

論理ゲートを実装する

まず、論理ゲートの入力にあたる型を定義してしまいます。

interface O { o: void } // 0 を意味する型
interface I { i: void } // 1 を意味する型

途中の o: void と i: void は、インターフェース O と I が構造的部分型により等価とみなされてしまうことを防ぐためのものです。

次に、NOT ゲートを定義してみましょう。NOT ゲートは、0が入力されると1を返し、1が入力されると0を返します。

interface Not {
  (input: O): I;
  (input: I): O;
}

あっ、これただの NOT ゲートの真理値表ですね？この NOT は次のように使えます。

interface O { o: void } // 0 を意味する型
interface I { i: void } // 1 を意味する型

interface Not {
  (input: O): I;
  (input: I): O;
}
let not: Not;

let o: O;
let result1 = not(o); // -> I 型になります

let i: I;
let result2 = not(i); // -> O 型になります

次に、AND ゲートと OR ゲートを定義してみましょう。

interface And {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): O;
  (inputA: I, inputB: O): O;
  (inputA: I, inputB: I): I;
}

interface Or {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): I;
  (inputA: I, inputB: O): I;
  (inputA: I, inputB: I): I;
}

これは次のように利用できます。

interface O { o: void } // 0 を意味する型
interface I { i: void } // 1 を意味する型

interface And {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): O;
  (inputA: I, inputB: O): O;
  (inputA: I, inputB: I): I;
}

let and: And;
let o: O;
let i: I;

let result1 = and(o, o); // -> O 型
let result2 = and(o, i); // -> O 型
let result3 = and(i, o); // -> O 型
let result4 = and(i, i); // -> I 型

これで、これらの基本的なゲートを組み合わせて複雑な回路を組み立てる順序が整いました！

半加算器を実装する

ここからは、これまでのゲート回路を使いつつ、4bit 加算器をより単純な部品から組み立てていくことにしましょう。4bit 加算器は、半加算器と全加算器という部品に分解することができます。

まずは半加算器を実装します。

半加算器の回路図

interface O { o: void } // 0 を意味する型
interface I { i: void } // 1 を意味する型

interface And {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): O;
  (inputA: I, inputB: O): O;
  (inputA: I, inputB: I): I;
}

interface Xor {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): I;
  (inputA: I, inputB: O): I;
  (inputA: I, inputB: I): O;
}

let inputA: O; // A 端子の入力
let inputB: O; // B 端子の入力

let outputS: typeof halfAdder.s; // S 端子の出力
let outputC: typeof halfAdder.c; // C 端子の出力 

// 半加算器の定義
// module 構文でカプセル化してある。
module halfAdder {
  let and: And;
  let xor: Xor;

  // 出力端子S
  //   inputA と inputB を XOR ゲートで接続したもの。
  //   export がついているので、halfAdder.s でアクセスできる。
  export let s = xor(inputA, inputB);

  // 出力端子C
  //   inputA と inputB を AND ゲートで接続したもの。
  //   halfAdder.c でアクセスできる。
  export let c = and(inputA, inputB);
}

ここで、ようやく TypeQuery が登場しました！
TypeQuery は Overload の型推論結果を型宣言に組み込み、出力端子に結果を取り出す役目をもっています。

結果を半加算器のデモで確認してみましょう。inputA と inputB の型を書き換え、outputS と outputC の型がどのように推論されるかを確認してください（推論結果は、outputS にカーソルをあわせると表示されます）。

下のようになっていることが確認できますね。

  • let inputA: O、let inputB: O → outputS は O 型、outputC は O 型
  • let inputA: O、let inputB: I → outputS は I 型、outputC は O 型
  • let inputA: I、let inputB: O → outputS は I 型、outputC は O 型
  • let inputA: I、let inputB: I → outputS は O 型、outputC は I 型

全加算器を実装する

半加算器が実装できたので、全加算器を組み立てます。

全加算器の回路図

interface O { o: void } // 0 を意味する型
interface I { i: void } // 1 を意味する型

interface And {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): O;
  (inputA: I, inputB: O): O;
  (inputA: I, inputB: I): I;
}

interface Or {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): I;
  (inputA: I, inputB: O): I;
  (inputA: I, inputB: I): I;
}

interface Xor {
  (inputA: O, inputB: O): O;
  (inputA: O, inputB: I): I;
  (inputA: I, inputB: O): I;
  (inputA: I, inputB: I): O;
}

let inputA: O; // A 端子の入力
let inputB: O; // B 端子の入力
let inputX: O; // X 端子の入力

let outputS: typeof fullAdder.s; // S 端子の出力
let outputC: typeof fullAdder.c; // C 端子の出力 

// 全加算器
module fullAdder {
    let xor: Xor;
    let and: And;
    let or: Or;

    // 1つめの半加算器
    let _a1: typeof inputA;
    let _b1: typeof inputB;
    module _halfAdder1 {
        export const sum = xor(_a1, _b1);
        export const carry = and(_a1, _b1);
    }

    // 2つめの半加算器
    let _a2: typeof _halfAdder1.sum;
    let _b2: typeof inputX;
    module _halfAdder2 {
        export const sum = xor(_a2, _b2);
        export const carry = and(_a2, _b2);
    }

    export const sum = _halfAdder2.sum;
    export const carry = or(_halfAdder1.carry, _halfAdder2.carry);
}

デモ

4bit 加算器を実装する

もう後は勢いで。

6bit加算器の回路図

// INTPUT ////////////////////////////////
//   O: Low
//   I: High

let inputA1: I;
let inputA2: I;
let inputA3: O;
let inputA4: O;

let inputB1: O;
let inputB2: I;
let inputB3: O;
let inputB4: O;

// OUTPUT ///////////////////////////////
//   Hover the outputN to read the result

let output1: typeof halfByteAdder.sum1;
let output2: typeof halfByteAdder.sum2;
let output3: typeof halfByteAdder.sum3;
let output4: typeof halfByteAdder.sum4;

// //////////////////////////////////////

interface O { O: void }
interface I { I: void }

interface And {
    (a: O, b: O): O;
    (a: O, b: I): O;
    (a: I, b: O): O;
    (a: I, b: I): I;
}

interface Or {
    (a: O, b: O): O;
    (a: O, b: I): I;
    (a: I, b: O): I;
    (a: I, b: I): I;
}

interface Xor {
    (a: O, b: O): O;
    (a: O, b: I): I;
    (a: I, b: O): I;
    (a: I, b: I): O;
}

interface Not {
    (a: O): I;
    (a: I): O;
}

let o: O;
let i: I;
let and: And;
let or: Or;
let xor: Xor;
let not: Not;

module halfByteAdder {
    let _a1: typeof inputA1;
    let _b1: typeof inputB1;
    let _x1: O;
    module fullAdder1 {
        let __a1: typeof _a1;
        let __b1: typeof _b1;
        export module _halfAdder1 {
            export const sum = xor(__a1, __b1);
            export const carry = and(__a1, __b1);   
        }

        let __a2: typeof _halfAdder1.sum;
        let __b2: typeof _x1;
        export module _halfAdder2 {
            export const sum = xor(__a2, __b2);
            export const carry = and(__a2, __b2);   
        }

        export const sum = _halfAdder2.sum;
        export const carry = or(_halfAdder1.carry, _halfAdder2.carry);
    }


    let _a2: typeof inputA2;
    let _b2: typeof inputB2;
    let _x2: typeof fullAdder1.carry;
    module fullAdder2 {
        let __a1: typeof _a2;
        let __b1: typeof _b2;
        export module _halfAdder1 {
            export const sum = xor(__a1, __b1);
            export const carry = and(__a1, __b1);   
        }

        let __a2: typeof _halfAdder1.sum;
        let __b2: typeof _x2;
        export module _halfAdder2 {
            export const sum = xor(__a2, __b2);
            export const carry = and(__a2, __b2);   
        }

        export const sum = _halfAdder2.sum;
        export const carry = or(_halfAdder1.carry, _halfAdder2.carry);
    }


    let _a3: typeof inputA3;
    let _b3: typeof inputB3;
    let _x3: typeof fullAdder2.carry;
    module fullAdder3 {
        let __a1: typeof _a3;
        let __b1: typeof _b3;
        export module _halfAdder1 {
            export const sum = xor(__a1, __b1);
            export const carry = and(__a1, __b1);   
        }

        let __a2: typeof _halfAdder1.sum;
        let __b2: typeof _x3;
        export module _halfAdder2 {
            export const sum = xor(__a2, __b2);
            export const carry = and(__a2, __b2);   
        }

        export const sum = _halfAdder2.sum;
        export const carry = or(_halfAdder1.carry, _halfAdder2.carry);
    }


    let _a4: typeof inputA4;
    let _b4: typeof inputB4;
    let _x4: typeof fullAdder3.carry;
    module fullAdder4 {
        let __a1: typeof _a4;
        let __b1: typeof _b4;
        export module _halfAdder1 {
            export const sum = xor(__a1, __b1);
            export const carry = and(__a1, __b1);   
        }

        let __a2: typeof _halfAdder1.sum;
        let __b2: typeof _x4;
        export module _halfAdder2 {
            export const sum = xor(__a2, __b2);
            export const carry = and(__a2, __b2);   
        }

        export const sum = _halfAdder2.sum;
        export const carry = or(_halfAdder1.carry, _halfAdder2.carry);
    }

    export let sum1: typeof fullAdder1.sum;
    export let sum2: typeof fullAdder2.sum;
    export let sum3: typeof fullAdder3.sum;
    export let sum4: typeof fullAdder4.sum;
    export let carry: typeof fullAdder4.carry;
}

デモ

おわりに

コンパイル時計算で4bit加算器まで実装できることを確認できました。

TypeScript の型計算がこのレベルの計算機能を獲得した理由は、次のとおりです。

  • Interface を Callable にできること
  • Overload によって条件分岐を宣言できること
  • TypeQuery によって条件分岐を型宣言空間での適用へと置き換えられること

できればチューリング完全までもっていきたかったのですが、さすがは TypeScript チームというところ、きちんと対策がされているようです。みなさんも、TypeScript のコンパイル時計算で遊んでみましょう。

Enjoy TypeScript!

45
38
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
45
38