イドリス言語の概要

Agdaはあまりにも主流です！

ロシア語のイドリス言語に関する資料はほとんどありません。簡単な概要でこれを修正しようとします。 また、私は、初心者、機能的ではない、依存型のプログラマーに馴染みのない人にもテキストを理解できるようにします。したがって、そのような言語に精通している人にとっては、最後まで巻き戻したり、公式ドキュメントをすぐに読んだりする方が簡単かもしれません。 私は言語と理論の真剣な紹介を書くことを想定していませんが、それがすべてであるものを示すことを望みます。



したがって、イドリスは、依存型を持つ純粋な関数型汎用プログラミング言語です。

これはなぜですか？

簡単な答えとして、ダイクストラの有名な引用が適切です。 それ以来アプローチは変更されましたが、目標は同じままです。

プログラマの製品は彼らが書くプログラムだと考えている人は、深く間違っています。 プログラマーは、信頼できる決定を作成し、説得力のある議論の形でそれらを提示する義務があり、書かれたプログラムのテキストは、この証拠が適用される資料のみをサポートしています。

より正確に言うと、作成して使用する理由はいくつかあります。著者のEdwin Bradyは、それを使用して、依存型のアプリケーションプログラミングを研究します。 私のように、多くの人が正確なプログラム仕様をコンパイルする機能が好きです。 また、正式な検証を通じてアプリケーションプログラムのデバッグ時間を大幅に短縮したいと考えています。 そして、ここで2番目の引用が頼みます：

プログラムをテストすると、エラーの存在を非常に効果的に実証できますが、エラーがないことを実証するには絶望的に不十分です。

静的型付けと依存型

プログラミング言語のタイピングを分類する方法の1つは、それを静的と動的に分けることです。 動的型付けでは、型はコンパイル時に不明であるため、チェックできません。 これはプログラムをより速く書くのに役立ちますが、同時にプログラムの実行中に検出される類型化エラーのクラスを追加しますが、これは通常あまり快適ではありません。 Idrisは静的型付けを使用しているため、それについてのみ以下で説明します。 しかし、動的型付けに慣れている人を怖がらせないために、 型推論も使用されていることにすぐに気付きます。 コンテキストからコンパイラに明らかな型は、明示的に省略できます。



入力は、文字列、数値、浮動小数点数など、いくつかのプリミティブ型に制限できます。 ある値のタイプ（たとえば、関数の引数、またはそれによって返される値）について「言う」ことができるのは、 「string」 、 「number」 、 「floating point number」だけです。 しかし、これは通常、構造のようなもので補完されます：単純なCのような構造、クラス、（一般化された）代数データ型など、同時に型（Cのtypedef



、Haskellのtype



）と同義で、たとえば「言う」ことができます、 「Date」 、「date」の構造、クラス、またはタイプを事前に定義済み。



これを「ポインター」というフレーズで補足できますが、同時に配列を使用できますが、高レベル言語では、 一般的なプログラミング （C ++のテンプレート、Javaのジェネリック）がより頻繁にサポートされ、既に「日付リスト」 、 「道路グラフ」などのフレーズを作成できます" 、 "イベントツリー " 。 つまり、型は他の型によってパラメーター化できます。



そして最後に、値で型をパラメーター化できます。これにより、 「 5行のリスト」 、 「Vasilyによって署名されたメッセージ」 、 関数タイプは、より一般的な「メッセージを受信して​​ユーザーデータを返す関数 」ではなく、 「特定のユーザーによって署名されたメッセージを受信し、このユーザーのデータを返す関数」という形式を取ることができます 。 さらに、これは、いわば、主語から述語への切り替え、「タイプとしての発言」の原則を使用することを可能にします： 「5は3より大きい」 、 「5は3より大きいことは事実ではありません」 、 「7は素数」 、 「Vasily received 2」メッセージ 。 これらは、偶然、他のいくつかの言語（Agda、Coq、Epigramなど）でIdrisに実装されている依存型ですが、Idrisは現代の応用言語になりたいという欲求によってそれらと区別されます。



また、完全な関数型プログラミングの条件下では、コンピュータープログラムと数学的証明の間の対応を使用できます（ カレー-ハワード対応 ）。たとえば、 「AはB未満、BはC未満、AはC未満」または「メッセージが送信されました」一部のユーザーにとって、これはこのユーザーがこのメッセージにアクセスできることを意味します” ; 次に、関数の本体が証明になります。証明は、指定された型の値を返すだけで、証明の証明は型チェックです。

トータル機能プログラミング

前述のように、イドリスは純粋な関数型言語です。 ただし、関数のtotalityプロパティのオプション要件もサポートされています。これは、2つのプロパティを意味します。

1. 確実性はどこにでもあります：関数は入力に対して定義されなければなりません。 純粋な言語では、このプロパティが存在しないことが、プログラムが「落ちる」ためのほとんど唯一の方法です（特にIOの場合は、そのアクションの一部と考えられるコンパイラのバグのためにシステムによるプロセスを強制終了します）。
2. 厳密な正規化：再帰的な関数呼び出し中に、その引数の少なくとも1つを厳密に（構造的に）減らすか、関数が各反復で生産的でなければなりません-つまり 結果の一部と、次の反復計算の約束を返します。 前者の場合、これは停止問題を回避して機能の完了を保証し、後者の場合、有限長で任意の長さの最終プレフィックスを読み取る機能を保証します。

これは、まず証拠を構築するために重要ですが、私の観察から判断すると、通常のプログラムの正確さは有益です。 ちなみに、このプロパティの存在により、この関数の遅延計算と貪欲な計算の結果が同じになることが保証され、Idrisの計算はデフォルトで貪欲ですが、引数を遅延させることができます。



このオプションは、個々の関数、ファイル、またはコンパイラのフラグで有効にできます。

例

異常な構文は、記述されている内容の本質から注意をそらすように思われるため、構文については説明しません。 コード例はMLファミリーの言語に精通している人向けに提供されており、残りの部分については、これらの例の前にテキストの説明があります。

部門

ほとんどすべてのプログラミング言語（または標準ライブラリ）で利用可能な、誰もが使い慣れた操作は部門です。 しかし、0で割ることは禁止されており、さまざまな議論の余地がある決定につながります。

• Infinityなどの特別な何かを返すには、Infinityを使用する他のすべての関数/演算の演算規則も決定する必要があります。これにより、算術全体が複雑になりますが、たとえば、単純なプロパティa / b = c→b * c = aが失われます、さらに、それを使用しようとすると、簡単に予想外の結果につながります。
• 例外を発生させるために：これは、通常のプログラムフローの中断につながるだけでなく、キャッチされていない例外を含むバグの根拠を作成するだけでなく、それが不可能にならない場合、関数に関する議論（特に正式）を大幅に複雑にします。
• 結果をMaybeにラップして、0で除算しようとするとNothingを返します。前の2つよりも優れています。ただし、関数自体はプログラマに正しいプログラムの作成を促さず、式の精度が低下したり、カテゴリ理論で過度に飽和したりする可能性があります。この除算の実装を使用する機能。

依存型を持つ言語、特にIdrisには、別のオプションが表示されます。0による除算を禁止します。言い換えると、0による除算は禁止されます。 関数のタイプは、「2つの数値を取り、2番目の数値が0でなく、数値を返す関数」と記述されます。 必要に応じて、戻り値と関数の引数との関係を示すプロパティでこの仕様を補足できます。 「...など...」ですが、別の定理に任せる方が簡単ですが、ここでは除算関数のタイプの説明に戻ります。通常の2つの引数に、3つ目の引数を追加する必要があります。



次に、除算を使用する3つのケースを検討します（コンパイル時間について話していることを思い出してください）。

1. 除数は既知です。自然数の等価性は決定可能であるため（つまり、コンパイラは除数がゼロかどうかを確認します）、したがって、必要に応じて、通常の2つの引数を持つ関数にそのような除算関数をラップして、同じ単純な3番目の引数。
2. 除数は不明ですが、ゼロに等しくないことを確認するための除数がわかっています。たとえば、負でない数よりも大きい場合です。 次に、証拠を所定の場所に記述するか、持っているものを取り（数が非負数よりも大きいことを証明する）、必要なものを返す関数を使用する（この数がゼロに等しくないことを証明する）必要があります。 そのような関数は、単に関数、または補題または定理と呼ぶことができますが、すでに述べたように、この文脈ではそれはまったく同じです。
3. 私たち自身は、除数がゼロに等しくないことを確信していません（不平等を証明するために状況を慎重に検討した後、前のケースはこのケースに入るかもしれません）：この場合のみ、実際に除算の前にチェックを導入する必要があります; 除数がゼロの場合、代替ソリューションを使用し、そうでない場合は、受信した情報を使用して除算を実行します。

もちろん、このアプローチはIdrisでは必要ありませんが、プログラマーが計算を正しく実行できるようにします。



最後に、コード例は除算関数のフレームワークです。

 -- (total)      -- "==" -    ,  Bool -- "=" -  ,  total div : (n, m: Nat) -> ((m == Z) = False) -> Nat --   0 - ;     --    , ,      div n Z f = FalseElim $ trueNotFalse f --     div n (S k) f = {-todo-}?div_rhs
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これは単なるワイヤーフレームであるため、メタ変数div_rhs



がここで使用されます。 Agdaに精通している人は既に「穴」を知っており、その弱いバージョンはIdrisのメタ変数であり、残りについては説明します。Idrisを使用すると、コンテキスト（その位置から見える変数）と目的（この位置から構築/返却される）、証拠とプログラムの両方の記述を非常に容易にします。 この場合、次のようになります。

  n : Nat k : Nat f : S k == 0 = False -------------------------------------- div_rhs : Nat
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

それらを半自動的に入力することも可能です： Nat



を返す目的で、（REPL / IDE）「refine」コマンドを使用して、たとえばplus



関数の名前を渡し、 plus



関数が必要な型の値を返すことができる場合、それを置き換えますこのメタ変数の代わりに、その引数に2つの新しいメタが置き換えられます。 プロセスは、別の機能で使用されるプロセスと同じです-メタ変数の完全自動置換、つまり 証拠の検索：場合によっては、必要な証拠を自動的に見つけることができます。



タイプ（読みやすいように少し編集）：

 λΠ> :t div div : Nat -> (m : Nat) -> (m == 0 = False) -> Nat
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 λΠ> :t div 1 2 div 1 2 : (2 == 0 = False) -> Nat
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 λΠ> :t div 1 2 refl div 1 2 refl : Nat
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 λΠ> :t div 1 0 refl (,        )
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

除算関数の実装から脱線して、このアプローチが私たちに与えるものを見てみましょう。 前述の正確さから始めましょう。関数は本来の動作をします。 関数は、通常、実装するものと考えて考えることができます（算術、この場合：ゼロで除算することはできませんが、除算の過程で例外のような概念は含まれず、結果は数値です）。 関数については、形式的にも含めて、それが表す概念と同じ方法で話すことができます。 推論をコードで書き留めます。 これを使用する関数では、推論と結論が計算と絡み合ってチェックできるようになり、プログラマーの頭の中やテキストコメントに残ることはなくなりました。 また、プログラムは、計算のレシピだけでなく、正しい推論と決定から構成されます。

リスト

リスト（または配列）を操作することも、ほぼ同じ一連の物議を醸す決定とその後のエラーにつながる一般的なタスクです。 特に、リストのn番目の要素を返す関数を考えます。その実装の問題は、リストにない位置から要素を要求できることです。 通常の解決策は、「アクセス違反」または「セグメンテーションフォールト」に該当し、例外をスローする（場合によってはそれで該当する）場合があります。



依存型を持つ言語では、さらに考えられる解決策がいくつか現れます。 最初の方法は、ゼロによる除算の問題を解決するのと似ています。 関数の最後の引数は、要求された位置がリストの長さより小さいことの証明です。



ここでは、さまざまな数字、リスト、「if-then-else」などを確認できます。 言語自体で定義されています。 ライブラリに実装されている自然数は、Cでのコンパイル時にGMP番号に置き換えられ、加算や乗算などの関数は対応するGMP関数に置き換えられます。これにより、コンパイルされたプログラムでの迅速な計算とそれらについての話し合いが可能になります。 次に、コードを見てみましょう。

 data Nat = Z | S Nat data List a = Nil | (::) a (List a) length : List a -> Nat length [] = 0 length (x::xs) = 1 + length xs index : (n : Nat) -> (l : List a) -> (ok : lt n (length l) = True) -> a index Z (x::xs) p = x index (S n) (x::xs) p = index n xs ?indexTailProof index _ [] refl impossible indexTailProof = proof { intros; rewrite sym p; trivial; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

indexTailProof



はCoqスタイルの戦術を使用した証明ですが、Agdaスタイル、つまり より馴染みのある機能（真実は、戦術がまもなくAgdaにも導入されるということです）。



2番目の解決策は、リストだけでなく、固定長のリスト、つまり、依存型を持つ言語のコンテキストで呼び出されるベクターを使用することです。 上記で例を挙げました。これにより、「5行のリスト」と言うことができます。 いわゆる 最終型-つまり、異なる値の数が有限である型：自然数の同じ型であるが、上限があると考えることができます。 このタイプは、自然数よりも「n未満の数」と言う方が簡単であるため、特に便利です。 ベクトルのn番目の要素を取得するための関数の型は、「n未満の数とn型の要素のリストを取り、a型の要素を返す関数」として読み取られます。



この場合、タスクは証明を提供することではなく、必要なタイプ（n未満）を構築することです。 ちなみに、ここでの証明の論理は古典的（直観的）とは異なり、証明の構築にあります。つまり、ステートメント/型の証明はこの型の任意の値であるため、以前のアプローチとの類似性を追跡できますが、同時に、プログラム全体を書くと、それは変わります。



コード：

 data Fin : (n : Nat) -> Type where fZ : Fin (S k) fS : Fin k -> Fin (S k) data Vect : Nat -> Type -> Type where Nil : Vect Z a (::) : (x : a) -> (xs : Vect na) -> Vect (S n) a index : Fin n -> Vect na -> a index fZ (x::xs) = x index (fS k) (x::xs) = index k xs --  -    ,    --   ""  index fZ [] impossible
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、明確な証拠からさらに先に進みますが、正しいプログラムを構築しています。



さて、ベクトルにたどり着いたので、ここにそれらを結合する機能があります。多くの場合、依存型を示すための例として与えられています。

 (++) : Vect ma -> Vect na -> Vect (m + n) a (++) [] ys = ys (++) (x::xs) ys = x :: xs ++ ys
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

本文は通常のリストと同じですが、タイプはより興味深いものですm + n



注意してください。

その他の例

上記は、イドリスが修正するのに役立つ個々の小さな関数の例ですが、ここにいくつかのより大きなものがあります：

• プロトコル：DSLを使用してプロトコルを記述し、実装できるプロトコルライブラリがあります。 プロトコル記述と実装の不一致はエラーになります。
• 物理学とゲーム ：計算が正しいだけでなく、メインプログラムを書いた後に定理を証明することも有用です。
• ファンクタ、適用ファンクタ、およびモナドの法則は、時間クラス自体のコードに含めることができます 。
• 暗号化 ：重要なことの明らかな例。
• テキスト/バイナリ形式の解析とコンパイル：構成された行がソースデータに解析され、解析されたデータがソース行にコンパイルされることを正式に証明できます。 それが私がイドリスの最初のプロジェクトとして選んだものです。
• アクセス権システム、データベース、デバイスドライバー-Idrisでの実装はまだ見ていませんが、信頼できるものを見たいと思っています。

DOMとやり取りするためのWebフレームワークとライブラリの両方がその上に記述されており（執筆時点では、コンパイラはC、LLVM、Java、およびJavaScriptでのコンパイルをサポートしています）、あらゆる種類のパーサー（ one 、 two ）であり、システムプログラミングを対象としています。 HaskellからIdrisに対応するプログラムは非常に簡単です。



イドリスはまだ生産に使用されていません-少なくとも広く使われています（ポツダム気候影響研究所で積極的に使用されていると聞きましたが、これは通常生産で正確に理解されているとは限りません）。 主な技術的障害は「非ロールイン」であり、これは「ロールイン」によって決定されるべきです。

おわりに

この言語は新しいため、「未加工」ですが、他の言語で蓄積された現代の理論と実践を使用して現代的です。



イドリス（およびその後に登場する言語）の将来の使用について少し夢を見ることができるようになると、プログラムの信頼性の一般的な向上に加えて、正式な仕様に伴う技術的なタスク、またはそれらからなることさえ想像できます。 プルーフマーケットのようなサービスの成長。 物理、数学、ロジバンのような他の理論と言語のライブラリ。 証明された定理の正式な仕様のリストとしての記事と本。 特に自動的にチェックされたレプリカと質問と回答のペアから構築された通信。

関連リンクと本

• ドキュメントとリンクのある公式サイト 。
• github wiki ;
• idris-modeを使用したスクリーンキャスト （ちなみにidris-vimがあります ）。
• Software Foundations-依存型を持つ言語の優れた入門書ですが、Coqを使用しています。
• 型理論と関数型プログラミング -そのような言語の根底にある理論の説明。
• TaPL、Haskellの書籍、およびAgdaのドキュメントが全体像を示しています。

PS

コメントとアイデアについて、このレビューがテストされた人々に感謝します。