Clever Geek Handbook

OCaml言語のアクティブパターン拡張機能の実装

プロジェクトについて



2020年の春、コンピューターサイエンスセンターでの春の練習の一環として、Dmitry Kosarevの厳格な指導の下、OCamlプログラミング言語の新しいデザインを開発していました。



なぜOCaml



OCamlは、産業用プログラミング同期（したがって、マルチパラダイム、マルチプラットフォーム、非常に高速なコンパイラ、生成されたコードの高い生産性）および数学（したがって、型推論、表現力、および拡張性の強力な実装を備えた最先端の型システム）の最も成功し開発された実装の1つです。言語、数学表記およびセマンティクスへの近さ）。



同時に、言語コミュニティは非常に選択的であり、既存の言語に制限を導入しない限り、非常に要求の厳しい構造のみをゆっくりと言語に追加します。したがって、言語のコアは非常に小さく直感的であり、OCamlは、産業開発者と、たとえば、サンクトペテルブルク州立大学の高等代数学部および数理論学部の数学者の両方によって喜んで使用されています。



トピックを深くダイビングのために、私は記事を見てとることをお勧め大衆のためのOCamlとなぜOCamlのを。



現在、OCamlのマルチコアシステムを代数的効果と組み合わせて実装する作業が進行中です。これにより、言語の全体的なパフォーマンスが向上し、言語が不純な計算を許可するという事実に関連するタイプシステムの既存の制限がなくなります。



パターンマッチングとアクティブパターン



私の仕事は主に、機能プログラミング言語で広く使用されているパターンマッチング構造に焦点を当てています。

説明のために、バイナリツリーでノードを回転させる簡単な例を考えてみましょう。最も一般的な必須スタイルでは、コードはおそらく次のようになります。 







type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Nil
let rotate_left' t =
  if is_node t
  then
    let a = get_left  t in
    let p = get_value t in
    let r = get_right t in
    if is_node r
    then
      let b = get_left  t in
      let q = get_value t in
      let c = get_right t in
      Node(Node(a,p,b),q,c)
    else t
  else t


そして、これはパターンマッチング構造を使用して書かれたまったく同じコードです： 



let rotate_left = function
  | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
  | Node _ | Nil as x -> x


この設計を使用すると、次の利点があります。



  • 高い表現力;
  • 完全性チェック。これは、正確性チェックとプログラムのリファクタリングにとって重要なプロパティです。
  • 効率的なコンパイルスキーム。


完全性チェックとは、型の定義を知っているコンパイラが、サンプルがどれほど複雑で、サンプルが互いにどのように交差していても、すべての可能な選択肢が解析され、到達不能なブランチがないことが真であるかどうかを各一致についてチェックできることを意味します。したがって、型定義を変更した場合（新しい選択肢の追加、既存の選択肢の削除または変更）、コンパイラーは、直接影響を受けたコード内のすべての場所を親切に提供します。



たとえば、構文ツリーに新しい構成を追加した場合、コンパイラは関数本体までAST入力コードを表示します。ここで、新しい構成の入力コードを記述する必要があります。







このプロパティにより、OCamlはリファクタリングやその他のコード変更に対して非常に耐性があります。



説明されているすべての利点にもかかわらず、適用性には非常に深刻な制限が1つあります。気づきましたか？タイプ定義はパブリックである必要があります（コンパイラーがそれを構成する代替案を表示できるようにするため）。そしてもちろん、これは最も単純な抽象化でさえもすぐに分解します。たとえば、最も単純なリストインターフェイスを定義する場合、エクスポートするタイプ定義を事前に指定することはできません。 



module type List = sig
  type 'a t (* = ? *)
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end


ただし、この問題は根本的なものではなく、1987年に述べたように、抽象型でパターンマッチングを実現することは可能です。



問題の定式化



1987年以来、問題を解決するために多くの異なるデザインが文献に提示されてきました。それらのほんの一部です。







プロジェクトの開始までに、実装のための特定のソリューションの合理的かつ客観的な選択に関する作業がすでに行われていました。最も有利なのは、F＃言語で実装されたアクティブパターン拡張です。



このプロジェクトの目標は、OCamlコンパイラのアクティブパターンの実装を開始し、可能な限りうまくいくことでした。



アクティブなパターン



アクティブパターン（および同様の拡張機能）の考え方は非常に単純です：抽象化は関数内の実装を非表示にすることで実現されるため、抽象データタイプの未知の値を既知の選択肢のリストに変換するパターンマッチング内の関数呼び出しを許可する必要があります。アクティブなパターンは、この選択肢のリストを関数名の中にエンコードします。したがって、上記のリストのインターフェースで、次の関数を追加する必要があります(|Cons|Nil|)。 



module type List = sig
  type 'a t
  val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end


結果は、choice2次の定義を持つ匿名の合計タイプになります（までに同様の生成されたタイプがありますchoice32）。 



type ('a, 'b) choice2 =
  | Choice2_1 of 'a
  | Choice2_2 of 'b


したがって、この関数(|Cons|Nil|)は、リストを2つの選択肢のいずれかに変換します。リストの先頭と末尾のペア、またはリストが空であることを意味する空の選択肢のいずれかに変換します。



標準リストに対してこのような関数を定義するのは簡単で、次のようになります。 



let (|Cons|Nil|) = function
  | []      -> Nil
  | x :: xs -> Cons(x, xs)


使用例として、リスト内の連続する重複を削除する関数について考えてみます。 



(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
  | Nil -> nil
  | Cons(x, Nil) -> cons x empty
  | Cons(x, Cons(y, rest)) ->
      if x = y 
      then destutter (cons y rest)
      else cons x (destutter (cons y rest))


パターンマッチングのすべての利点が保持されていることに注意してください。マッチング構文は同じであり、完全性チェックは完全に機能します。このようなソリューションを効率的にコンパイルすることは、この概要の範囲を超えていますが、それも可能です。



進捗



この作業の一環として、OCamlコンパイラバージョン4.09の拡張機能の解析と型指定を実装することができました。結果は、ここに示されています。



コンパイラパーサーは、高度なMenhirパーサージェネレーターを使用して実装されます。 Menhirにはかなり完全で詳細なマニュアルがありますが、彼がいても、推論ルールを設定する方法と、その方法と理由が必ずしも明確ではありませんでした。結果として得られるパーサーパッチは非常に小さく単純ですが、そのパスは10〜15のshift-reduceおよびreduce-reduceの競合を通り、その解析と修正には時間がかかりました。







Menhirの開発者に敬意を表し、エラーの詳細と明確化に取り組んでくれた彼らに感謝します。パーサージェネレーターが競合を説明できず、1500の状態に対して構築されたオートマトンに従ってそれを解析する必要があった場合。もちろん、これには1桁以上の時間が必要でした。



拡張機能の入力は特に困難でした。入力コードは約37,000行かかり、ほとんど文書化されていません。これは初心者が理解するのは簡単ではありません。実装の重要な側面を説明するOlegKiselevの記事に助けられました。



私が自分でしたもう1つの結論は、プロジェクトの古いバージョンを使用することを忘れないことです。たとえば、2019バージョンと2005バージョンの同じタイピングの定量的な比較を次に示します。







2019バージョンには、コンパイラの分析と警告、および私が興味を持っていなかった追加の技術的な詳細が含まれています。理解するには、重要なアクションのみが含まれている2005バージョンを確認する必要がありました。



最後に、私の作業中に行った主な結論は、オープンソースプロジェクトのドキュメントが非常に重要であることを確認することです。言語と同じように表現力豊かなソースコードは、関数がどのように動作するかを伝えるだけであり、関数が何をするのか、なぜそのように動作するのかはわかりません。コールチェーンtype_self_pattern-> type_cases-> t ype_pat-> type_pat'->を読んで、type_pat_aux必要な機能を見つけるのは非常に困難です。または1つのパラメータ名のみconstrどのコンストラクターとその理由をここに記述する必要があるかを推測します。



毎回ユースケースを確認する必要があると、プログラマーの速度が低下し、すぐに疲れます。「7、プラスまたはマイナス2」というルールを思い出させてください。平均して、人が同時に頭の中に保持できるオブジェクトの数と同じです。そして、6番目のネストされた関数内のパラメーターの意味を最終的に理解し、なぜそれが必要なのか思い出せないことに突然気付いたとき、または必要でなかったことが判明したとき、費やされた時間の長さのために非常に悲しくなります。



結論



プロジェクトの一環として、アクティブパターンの解析と入力を実装することができました。パッチを適用したコンパイラは、アクティブパターンの使用例を使用してファイルを解析および入力できます。



次に、コンパイルスキーム（OCamlはパターンマッチングの重要な最適化コンパイルを使用します）とスキーマの完全性チェックを変更する必要があります。これらはプロジェクト中にOCamlコンパイラ開発チームによってほぼ完全に書き直されました。



私の有無にかかわらず、この実装がまだ完了することを願っています。すべての困難にもかかわらず、お気に入りの言語用の産業用コンパイラーの開発に挑戦することは素晴らしいことでした。



著者：



Alexander Bashkirovは、コンピューターサイエンスセンターの学生であり、JetBrainsの従業員であるサンクトペテルブルク州立大学のソフトウェアエンジニアリングの4年目の学士課程です。


More articles:


All Articles