依存型-プログラミング言語の未来

みなさんこんにちは！



今日考えられているトピックの風変わりさといくつかの抽象化にもかかわらず-それはあなたの週末を多様化できることを願っています。 投稿の最後に、著者からの3つのリンクを配置します。これにより、イドリス、F *、およびJavaScriptでの依存型付けに慣れることができます。



プログラミング言語が60年代からあまり変わっていないように見えることもあります。 彼らがこれについて私に話すとき、私はしばしば、私たちが自由に使えるクールなツールと機能の数と、それらが私たちの生活を単純化する方法を思い出します。 オフハンド：これらは、統合されたデバッガー、単体テスト、静的アナライザー、クールなIDE、型付き配列などです。 言語の開発は長く進歩的なプロセスであり、言語の開発が完全に変わるような「銀の弾丸」はありません。



今日は、この進行中のプロセスの最後の段階の1つについてお話したいと思います。 私たちが話している技術はまだ活発に研究されていますが、すべてが主流の言語にすぐに定着することを示しています。 そして、私たちの物語は、コンピューターサイエンスの最も基本的な概念の1つ、つまり型から始まります 。

タイプの世界

型付けは、私たちの思考と切り離せないものの1つであり、型の概念自体もほとんど考えません。 1がint



なぜですか。ただし、この値を引用符で囲むだけで、 string



に変わる場合はどうでしょうか。 本質的に「タイプ」とは何ですか？ プログラミングではよくあることですが、答えは質問の文言に依存します。



タイプは多様です。 一部の型システムでは、型と値の間に非常に明確な境界があります。 したがって、3、2、および1はinteger



値ですが、 integer



は値ではありません。 このコンストラクトは言語に「埋め込まれ」、意味とは根本的に異なります。 しかし、実際、そのような違いは必要ではなく、私たちを制限するだけです。



型を解放して別のカテゴリの値に変換すると、多くの驚くべき可能性が広がります。 値は保存、変換、および関数に渡すことができます。 したがって、型をパラメーターとして受け取る関数を作成し、一般化された関数を作成できます。これは、オーバーロードなしで多くの型で機能できる関数です。 Cで行うように、奇妙なポインター演算や型キャストを行うのではなく、特定の型の値の配列を使用できます。プログラムの実行中に新しい型を収集し、自動JSONデシリアライゼーションなどの機能を提供することもできます。 ただし、型を値として扱っても、値でできることを型で行うことはできません。 そのため、たとえば、ユーザーインスタンスを操作して、名前の比較、年齢や識別子の確認などを行うことができます。

 if user.name == "Marin" && user.age < 65 { print("You can't retire yet!") }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、 User



タイプで同じことをしようとすると、タイプ名と場合によってはプロパティ名のみを比較できます。 これはインスタンスではなくタイプであるため、プロパティの値を確認することはできません。

 if typeof(user) == User { print("Well, it's a user. That's all I know") }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

空ではないユーザーのリストのみを受信できる機能があれば、それはどれほどクールでしょうか？ または、正しい形式で記述されている場合にのみ電子メールアドレスを受け入れる関数ですか？ これらの目的には、「空でない配列」または「電子メールアドレス」タイプが必要です。 この場合、値に依存する型、つまり 依存型について。 主流の言語では、これは不可能です。



型を使用できるように、コンパイラはそれらをチェックする必要があります。 変数に整数が含まれていると言う場合、その中にstring



がなければ良いでしょう。そうでなければコンパイラは誓います。 原則として、これは良いことです。なぜなら、それが私たちに懇願することを許さないからです。 型の確認は非常に簡単です。関数がinteger



返し、その中に"Marin"



を返そうとすると、これはエラーになります。



ただし、依存型では、事態はさらに複雑になります。 問題は、コンパイラが型をチェックするときです。 プログラムがまだ実行されていない場合、配列に正確に3つの値があることをどのように確認できますか？ 整数がまだ割り当てられていない場合、整数が3より大きいことを確認する方法は？ これには魔法があります...または、言い換えると、 数学です。 数値のセットが常に3より大きいことを数学的に証明できる場合、コンパイラはこれを検証できます。

スタジオでの数学！

数学的帰納法は、証拠を定式化するために使用されます。 帰納法により、声明の真実を無条件に確認することができます。 たとえば、次の数式が任意の正数に当てはまることを証明したいと思います。

 1 + 2 + 3 + ... + x = x * (x + 1) / 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

可能なxの数は無限であるため、すべての数字を手動で確認するには非常に長い時間がかかります。 幸いなことに、これは必要ありません。 次の2つのことを証明する必要があります。

1. この声明は最初の日に観察されます。 （通常は0または1です）
2. このステートメントが数値n
   
   
   
   について真である場合、次の数値n + 1
   
   
   
   についても真になります。

ステートメントは最初の数字とそれに続くすべての数字の両方に当てはまるため、考えられるすべての数字に当てはまることがわかります。



これを証明することは難しくありません：

 1 = 1 * (1 + 1) / 2 1 = 1
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、ステートメントが他のすべての数値にも適用されることを証明する必要があります。 これを行うには、ある数nで機能すると仮定し、n + 1でも機能することを確認します。



次の式が真であると仮定します。

 1 + 2 + 3 + ... + n = n * (n + 1) / 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

n + 1



を確認してください：

 (1 + 2 + 3 + ... + n) + (n + 1) = (n + 1) * ((n + 1) + 1) / 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、 "(1 + 2 + 3 + ... + n)"



上記の等式で置き換えることができ"(1 + 2 + 3 + ... + n)"



。

 (n * (n + 1) / 2) + (n + 1) = (n + 1) * ((n + 2) / 2)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

に簡素化

 (n + 1) * (n/2 + 1) = (n + 1) * (n/2 + 1)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

式の両方の部分が等しいため、このステートメントが真であることを確認しました。 これは、各ケースを手動で計算せずにステートメントの真理を検証できる方法の1つであり、依存型が機能するのはこの原則に基づいています。 型理論が正しいことを確認するために数学的ステートメントを書きます。



このアプローチの利点は、数学的な証明をコンピュータープログラムの形式で発行で​​きるという事実にあります。これが必要なことです。

プログラミングに戻る

そのため、いくつかのことが最初に証明され、次に特定の値に移ることができることがわかりました。 これをプログラミング言語で行うには、型システム自体に書き込まれるコードでこれらのステートメントを表現する方法が必要です。つまり、型システムを改善する必要があります。



例を考えてみましょう。 ここには、2つの配列を取り、それらを結合するappend関数があります。 原則として、このような関数の署名は次のようになります。

 append: (arr1: Array, arr2: Array) -> Array
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、署名を見るだけでは、正しい実装を確認することはできません。 関数が配列を返すという事実は、それが何かをしたという意味ではありません。 結果を確認する1つの方法は、結果の配列の長さがパラメーター配列の長さの合計と等しいことを確認することです。

 newArray = append([1], [2, 3]) assert(length(newArray) == 3)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、プログラムのコンパイル時にチェックされる制約を作成できる場合、実行時にこれをチェックする理由は次のとおりです。

 append: (arr1: Array, arr2: Array) -> newArray: Array where length(newArray) == length(arr1) + length(arr2)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

append



は、2つのArray



引数を取り、 newArray



引数と呼ばれる新しいArray



引数を返す関数であることを宣言しappend



。 今回だけ、新しい配列の長さが関数へのすべての引数の長さの合計に等しくなければならないという警告を追加します。 実行時に上記のステートメントは、コンパイル時に型に変換されます。



上記のコードは、値ではなく型の世界を参照しています。つまり、 ==



記号は、値ではなく、返された型のlength



比較を示しています。 このようなメカニズムが機能するためには、返される型の長さが実際の数に関する情報を提供する必要があります。



このようなメカニズムの動作を保証するには、各番号が別々のタイプであることを確認する必要があります。 1つだけ値を含めることができます：1. 2つ、3つ、および他のすべての数値についても同じことが言えます。 当然、そのような作業は非常に骨の折れる作業ですが、プログラミングを行うのはそのような作業のためです。 これを行うコンパイラーを作成できます。



これを行った後、1、2、3、および異なる数の要素を含む配列に個別の型を作成できます。 ArrayOfOne



、 ArrayOfTwo



など



したがって、長さ関数を定義できます。この関数は、上記の配列タイプのいずれかをArrayOfOne



、 ArrayOfOne



に対してOne



、 ArrayOfOne



に対してTwo



などの依存戻りタイプを持ちます。 番号ごとに。



配列の特定の長さに個別の型があるので、両方の配列が同じ長さであることを（コンパイル時に）確認できます。 これを行うには、それらのタイプを比較します。 また、型は他の型と同じ値であるため、操作を型に割り当てることができます。 ArrayOfOne



とArrayOfTwo



合計がArrayOfOne



と等しいことを指定することにより、2つの特定のタイプの追加を決定できます。



コンパイラーは、作成したコードが正しいことを確認するために必要なすべての情報です。



ArrayOfThree



型の変数を作成するとします。

 result: ArrayOfThree = append([1], [2, 3])
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コンパイラは[1]に値が1つしかないと判断できるため、 ArrayOfOne



型を割り当てることができます。 ArrayOfTwo



を[2、3]に割り当てることもできます。



コンパイラーは、結果の型が最初と2番目の引数の型の合計と等しくなければならないことを知っています。 また、ArrayOfOne + ArrayOfTwoがArrayOfThreeと等しいことも知っています。つまり、IDの右側の式全体がArrayOfThree型であることを知っています。 左側の式と一致し、コンパイラは満足しています。



以下を書いた場合：

 result: ArrayOfTwo = append([1], [2, 3])
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

型が正しくないことがわかるため、コンパイラは完全に不満になります。

依存型付けはとてもクールです

この場合、膨大な数のバグを許可することは不可能です。 依存型付けにより、ユニットごとのエラー、存在しない配列インデックスへのアクセス、nullポインター例外、無限ループ、壊れたコードを回避できます。



依存型を使用すると、ほとんど何でも表現できます。 階乗関数は自然数のみを受け入れ、 login



関数は空行を受け入れず、 removeLast



関数は空でない配列のみを受け入れます。 さらに、プログラムを開始する前に、これらすべてがチェックされます。



ランタイムチェックの問題は、プログラムが既に実行されている場合に失敗することです。 これは、プログラムがユーザーのみで実行され、ユーザーのみでは実行されない場合は正常です。 依存型を使用すると、そのようなチェックを型のレベルまで実行できるため、プログラム実行中にこの種の障害が発生することはありません。



依存型付けは主流のプログラミング言語の未来だと思うので、待つのが待ち遠しいです！



→ イドリス



→ F *



→ JavaScriptへの依存型の追加