表現の問題

式問題は、プログラミング言語における難しい問題であり、静的に型付けされたデータ抽象化の拡張性とモジュール性に関するものです。目標は、表現と動作の両方で拡張可能なデータ抽象化を定義することです。既存のコードを再コンパイルせずに、静的な型安全性 (キャストなしなど) を維持しながら、データ抽象化に新しい表現と新しい動作を追加できます。この問題の記述は、プログラミングパラダイムとプログラミング言語^{[アップデート]}の欠陥を明らかにしており、2023年現在、多くの解決策が提案されているものの、未解決と見なされています^{[引用が必要]}。^{[引用が必要]}

フィリップ・ワドラーは、ライス大学のプログラミング言語チーム（PLT）との議論に応えて、この課題を定式化し、「表現問題」^[1]と名付けました。彼はまた、この課題の背景を定義する3つの情報源を引用しました。

この問題は、1975 年にJohn Reynoldsによって初めて発見されました。 ^[2] Reynolds は、データ抽象化の 2 つの形式について論じました。1 つは現在抽象データ型(ADT) として知られているユーザー定義型 (代数データ型と混同しないでください)、もう 1 つは現在ではメソッドが 1 つしかないオブジェクトのプリミティブ形式として理解されている手続き型データ構造です。彼は、ユーザー定義型は新しい動作で拡張でき、手続き型データ構造は新しい表現で拡張できるという点で、これらは補完的であると主張しました。また、1967 年にさかのぼる関連作業についても論じました。15 年後の 1990 年、William Cook ^[3] は、Reynolds のアイデアを、両方とも大幅に成長していたオブジェクトと抽象データ型のコンテキストに適用しました。Cook は、データ抽象化に暗黙的に含まれる表現と動作のマトリックスを特定し、ADT が動作軸に基づいているのに対し、オブジェクトは表現軸に基づいていることを論じました。彼は、問題に関連する ADT とオブジェクトに関する作業について広範囲に渡って議論しています。また、両方のスタイルの実装をレビューし、両方向の拡張性について議論し、静的型付けの重要性についても明らかにしました。最も重要なのは、メソッドの内部化や最適化など、レイノルズが考えていたよりも柔軟性が高い状況について議論したことです。

ECOOP '98 で、Shriram Krishnamurthiら^{[4] は、}式指向プログラミング言語とそのツールセットを同時に拡張するという問題に対するデザイン パターン ソリューションを発表しました。彼らは、プログラミング言語設計者がその問題を利用して、自分たちの創作物の表現力を実証できると考えたため、それを「表現力の問題」と名付けました。PLT の場合、この問題は DrScheme (現在はDrRacket)の構築時に現れ、彼らはそれをmixinの再発見によって解決しました^[5]。^{[6] [7]}プログラミング言語に関する論文でプログラミング言語の問題を使用するのを避けるため、Krishnamurthi らは、古い幾何学プログラミングの問題を使用して、パターン指向ソリューションを説明しました。ECOOP プレゼンテーション後の Felleisen および Krishnamurthi との会話で、Wadler は問題の PL 中心の性質を理解し、Krishnamurthi のソリューションではキャストを使用して Java の型システムを回避していると指摘しました。議論は型メーリング リストで続けられ、Corky Cartwright (ライス大学) とKim Bruce (ウィリアムズ大学) が、OO 言語の型システムによってこのキャストが排除される可能性を示しました。これに対して Wadler はエッセイを書き、課題として「言語が表現の問題を解決できるかどうかは、その言語の表現能力の顕著な指標である」と述べました。「表現の問題」というラベルは、表現 = 「言語でどれだけ表現できるか」と表現 = 「表現しようとしている用語は言語表現である」をもじったものです。

ライス大学のPLTとほぼ同時期に、表現問題の変種を共同発見した研究者もいた。特にトーマス・キューネ^[8]は博士論文で、スマラグダキスとバトリ^[9]はECOOP 98の並行論文で発見した。

いくつかのフォローアップ研究では、式の問題を使用してプログラミング言語設計の威力を示しました。^{[10] [11]}

表現の問題は、多次元ソフトウェア製品ライン設計、特にFOSD プログラムキューブの応用または特殊なケースにおける基本的な問題でもあります。^[要出典]

式の問題にはさまざまな解決策があります。それぞれの解決策は、実装するためにユーザーが記述する必要があるコードの量や、必要な言語機能が異なります。

• 多重派遣^[12]
• Ruby構文 § オープンクラス^[13]
• 関数の余積^[14]
• 型クラス^[15]
• タグレスファイナル^[16] / オブジェクト代数^[17]
• 多型変異体^[18]

拡張したい C#で記述された次のライブラリのソース コードがないと想像できます。

パブリックインターフェイスIEvalExp  
{
    int評価(); 
}

パブリッククラスLit : IEvalExp    
{
    パブリックLit ( int n )  
    {
        Γ = Γ ;  
    }

    パブリックint N {取得; }     

    パブリックint評価()  
    {
        N を返します。 
    }
}

パブリッククラスAdd : IEvalExp    
{
    パブリックAdd ( IEvalExp左、IEvalExp右)    
    {
        左=左;  
        右=右;  
    }

    パブリックIEvalExp左{取得; }     

    パブリックIEvalExp右{取得; }     

    パブリックint評価()  
    {
        Left.Eval () + Right.Eval ( )を返します。   
    }
}

パブリック静的クラスExampleOne   
{
    パブリック静的IEvalExp AddOneAndTwo () =>新しいAdd (新しいLit ( 1 )、新しいLit ( 2 ));         
    パブリックスタティックint EvaluateTheSumOfOneAndTwo () => AddOneAndTwo (). Eval ();     
}

1 + 2このライブラリを使用すると、で行ったように算術式を表現しExampleOne.AddOneAndTwo()、 を呼び出して式を評価することができます。ここで、このライブラリを拡張したいとします。オブジェクト指向プログラミング言語.Eval()を使用しているため、新しい型を追加するのは簡単です。たとえば、次のクラスを作成できます。

パブリッククラスMult : IEvalExp    
{
    パブリックMult ( IEvalExp左、IEvalExp右)    
    {
        左=左;  
        右=右;  
    }

    パブリックIEvalExp左{取得; }     

    パブリックIEvalExp右{取得; }     

    パブリックint評価()  
    {
        Left.Eval ( ) * Right.Eval ( )を返します。   
    }
}

ただし、型に新しい関数 (C# 用語では新しいメソッド) を追加する場合は、インターフェイスを変更してIEvalExpから、インターフェイスを実装するすべてのクラスを変更する必要があります。別の可能性としては、インターフェイスを拡張する新しいインターフェイスを作成し、、およびクラスIEvalExpのサブタイプを作成することですが、 で返される式はすでにコンパイルされているため、古い型に対して新しい関数を使用することはできません。この問題は、F#などの関数型プログラミング言語では逆になり、特定の型に対して関数を追加するのは簡単ですが、型の拡張や追加は困難です。 LitAddMultExampleOne.AddOneAndTwo()

論文「大衆のための拡張性」のアイデアを使用して、拡張性を念頭に置いて元のライブラリを再設計してみましょう。 ^[17]

パブリックインターフェースExpAlgebra < T >  
{
    T直訳( int n );  
    T ( T左、T右)を追加します。    
}

パブリッククラスExpFactory : ExpAlgebra < IEvalExp >    
{
    パブリックIEvalExpLit ( intn )​​   
    {
        新しいLit ( n )を返す。  
    }

    パブリックIEvalExpを追加します( IEvalExp左、IEvalExp右)     
    {
        新しいAdd ( left , right )を返します。   
    }
}

パブリック静的クラスExampleTwo < T >   
{
    パブリック静的T AddOneToTwo ( ExpAlgebra < T > ae ) => ae . Add ( ae . Lit ( 1 ), ae . Lit ( 2 ) );       
}

最初のコード例と同じ実装を使用しますが、型に対する関数と代数のファクトリを含む新しいインターフェイスを追加します。型から直接式を生成するのではなく、インターフェイスをExampleTwo.AddOneToTwo()使用して式を生成することに注意してください。インターフェイスExpAlgebra<T>を拡張して関数を追加できるようになりましたExpAlgebra<T>。式を出力する機能を追加します 。

パブリックインターフェイスIPrintExp : IEvalExp    
{
    文字列印刷(); 
}

パブリッククラスPrintableLit : Lit 、IPrintExp     
{
    パブリックPrintableLit ( int n ) : base ( n )    
    {
        Γ = Γ ;  
    }

    パブリックint N {取得; }     

    パブリック文字列Print ()  
    {
        N.ToString ()を返します。 
    }
}

パブリッククラスPrintableAdd : Add 、IPrintExp     
{
    パブリックPrintableAdd ( IPrintExp左、IPrintExp右) :ベース(左、右)       
    {
        左=左;  
        右=右;  
    }

    パブリック新しいIPrintExp左{取得; }      

    パブリック新しいIPrintExpRight { get ; }​      

    パブリック文字列Print ()  
    {
        Left.Print () + " + " + Right.Print ( )を返します。     
    }
}

パブリッククラスPrintFactory : ExpFactory 、ExpAlgebra < IPrintExp >     
{
    パブリックIPrintExpを追加します( IPrintExp左、IPrintExp右)     
    {
        新しいPrintableAdd ( left , right )を返します。   
    }

    パブリック新しいIPrintExpLit ( int n )​    
    {
        新しいPrintableLit ( n )を返します。  
    }
}

パブリック静的クラスExampleThree   
{
    パブリック静的int Eval () => ExampleTwo < IPrintExp > . AddOneToTwo (新しいPrintFactory () ). Eval ();      
    パブリック静的文字列Print () => ExampleTwo < IPrintExp > . AddOneToTwo (新しいPrintFactory () ). Print ();      
}

では、 でExampleThree.Print()既にコンパイルされた式を出力しているためExampleTwo、既存のコードを変更する必要がないことに注意してください。また、これは依然として強く型付けされているため、リフレクションやキャストは不要であることにも注意してください。 でPrintFactory()を にExpFactory()置き換えると、そのコンテキストには メソッドが存在しない ExampleThree.Print()ため、コンパイル エラーが発生します。.Print()

• FOSDプログラムキューブの応用
• ジェネリックプログラミング
• POPLmarkチャレンジ

• フィリップ・ワドラー著『表現の問題』。
• 講義: ラルフ・レメルによる表現の問題。
• C9 講義: Ralf Lämmel 博士 - 高度な関数型プログラミング - Channel 9での表現の問題。^{[リンク切れ‍ ]}
• 表現問題に対する独立して拡張可能なソリューション、Matthias Zenger および Martin Odersky、EPFL ローザンヌ。