関数合成（コンピュータサイエンス）

コンピュータサイエンスにおいて、関数合成とは、単純な関数を組み合わせてより複雑な関数を構築する行為またはメカニズムです。数学における通常の関数合成と同様に、各関数の結果は次の関数の引数として渡され、最後の関数の結果が全体の結果となります。

プログラマーは関数を他の関数の結果に適用することがよくありますが、ほとんどすべてのプログラミング言語でそれが可能です。場合によっては、関数の合成は、後で使用するためにそれ自体の関数として興味深いことがあります。このような関数は常に定義できますが、ファーストクラス関数を備えた言語では定義が簡単になります。

関数を簡単に構成できると、保守性とコードの再利用性を高めるために関数をファクタリング（分解）することが促進されます。より一般的には、プログラム全体を構成することで大規模なシステムが構築されることもあります。

狭義には、関数合成は、有限量のデータに対して操作する関数に適用され、各ステップではデータを順番に処理してから次のステップに渡します。潜在的に無限のデータ (ストリームまたはその他のcodata ) に対して操作する関数はフィルターと呼ばれ、代わりにパイプラインに接続されます。これは関数合成に類似しており、同時に実行できます。

たとえば、z = f ( y )とy = g ( x )のような2 つの関数 fとgがあるとします。これらを合成するということは、最初にy = g ( x )を計算し、次にy を使用してz = f ( y )を計算することを意味します。C言語の例を次に示します。

float x , y , z ; // ... y = g ( x ); z = f ( y );   

  
  

中間結果に名前を付けない場合は、手順を組み合わせることができます。

z = f ( g ( x ) ) ;  

長さは異なりますが、これら 2 つの実装は同じ結果を計算します。2 番目の実装では 1 行のコードしか必要ないため、俗に「高度に構成された」フォームと呼ばれます。高度に構成されたフォームの利点の 1 つは、読みやすさと保守性です。これは、必要なコード行数が少なくなり、プログラムの「表面積」が最小限に抑えられるためです。^[1] DeMarco と Lister は、表面積と保守性の間に逆の関係があることを経験的に検証しています。^[2]一方、高度に構成されたフォームを過度に使用することは可能です。関数のネストが多すぎると、逆の効果が生じ、コードの保守性が低下する可能性があります。

スタックベースの言語では、関数合成はさらに自然です。関数合成は連結によって実行され、通常はプログラム設計の主な方法となります。上記のForthの例:

ガールフレンド

これは、スタック上に以前あったものをすべて取得し、g を適用してから f を適用し、結果をスタックに残します。対応する数学表記については、 接尾辞合成表記を参照してください。

ここで、g() の結果に対して f() を呼び出す組み合わせが頻繁に役立つと仮定し、これを foo() という名前にして、それ自体を関数として使用します。

ほとんどの言語では、合成によって実装された新しい関数を定義できます。C の例:

フロートfoo (フロートx ) {戻り値f ( g ( x )); }   
     

(中間表現を含む長い形式も同様に機能します。) Forthの例:

  : foo ガールフレンド;

Cなどの言語では、新しい関数を作成する唯一の方法は、プログラム ソースで定義することです。つまり、実行時に関数を構成することはできません。ただし、定義済み関数の任意の構成を評価することは可能です。

#include <stdio.h> 

typedef int FXN ( int );  

int f ( int x ) { return x + 1 ; } int g ( int x ) { return x * 2 ; } int h ( int x ) { return x -3 ; }      
      
      

int eval ( FXN * fs [], int size , int x ) { for ( int i = 0 ; i < size ; i ++ ) x = ( * fs [ i ])( x );      

          

   xを返す; } 


int main () { // ((6+1)*2)-3 = 11 FXN * arr [] = { f , g , h }; printf ( "%d \n " , eval ( arr , 3 , 6 )); 

   
      
      

   // ((6-3)*2)+1 = 7 
arr [ 2 ] = f ; arr [ 0 ] = h ; printf ( "%d \n " , eval ( arr , 3 , 6 )); }         
      

関数型プログラミング言語では、関数合成は高階関数または演算子として自然に表現できます。他のプログラミング言語では、関数合成を実行するための独自のメカニズムを記述できます。

Haskellでは、上記の例foo = f  ∘   g は次のようになります。

foo = f . g

組み込みの合成演算子 (.) を使用します。これは、g の後の f、またはf と合成された gとして読み取ることができます。

合成演算子 ∘  自体は、Haskell ではラムダ式 を使用して定義できます。

( . ) :: ( b -> c ) -> ( a -> b ) -> a -> c f . g = \ x -> f ( g x )            
        

最初の行は (.) の型を記述します。関数f、   gのペアを受け取り、関数 (2 行目のラムダ式) を返します。Haskell では、 f と g の正確な入力と出力の型を指定する必要がないことに注意してください。a、b、c、x はプレースホルダーであり、fと  gの関係のみが重要です (f は g が返すものを受け入れる必要があります)。これにより、 (.) は多態的な演算子になります。

Lispのバリアント、特にScheme では、コードとデータの互換性と関数の扱いが、可変長合成演算子の再帰定義に非常に適しています。

( define ( compose . fs ) ( if ( null? fs ) ( lambda ( x ) x ) ; 引数が指定されていない場合は、恒等関数( lambda ( x ) (( car fs ) (( apply compose ( cdr fs )) x )))))に評価されます。   
        
              

; 例
( define ( add-a-bang str ) ( string-append str "!" ))  
    

( givebangを定義します(文字列->シンボルを作成しますbangシンボルを追加します->文字列)) 
     

( givebang 'set ) ; ===> set!  

; 匿名合成
(( compose sqrt negate square ) 5 ) ; ===> 0+5i     

APLの多くの方言には、シンボル を使用した関数合成が組み込まれています∘。この高階関数は、関数合成を、となるような左側関数の二項適用に拡張します。 A f∘g BA f g B

フー←フー∘フー

さらに、関数合成を定義することもできます。

o ← { ⍺⍺ ⍵⍵ ⍵ }  

中括弧を使用したインライン定義をサポートしていない方言では、従来の定義が利用できます。

∇ r ← ( f o g ) x r ← f g x ∇   
    

Raku にはHaskellと同様に関数合成演算子が組み込まれていますが、主な違いは、∘またはと表記されることですo。

私の& foo = & f ∘ & g ;     

また、 Haskellと同様に、演算子を自分で定義することもできます。実際、以下はRakudo実装で演算子を定義するために使用される Raku コードです。

# 実装では、ここではごまかしをしているため、行が少し異なります。proto 
sub infix :<∘> (&?, &?) is equiv(&[~]) is assoc<left> { * }  

multi sub infix :<∘> () { *. self } # `@array` が空の場合に `[∘] @array` が機能するようにしますmulti sub infix :<∘> (&f) { & f } # `@array` に要素が 1 つある場合に `[∘] @array` が機能するようにしますmulti sub infix :<∘> (&f, &g --> Block) { ( & f ) . count > 1 ?? -> | args { f | g | args } !! -> | args { f g | args } }     
       
  
      
           
           


# これを「Texas」のスペルにエイリアスします (Texas ではすべてが大きく、ASCII です) 
my & infix: <o> : = & infix: <∘> ;   

Nimは統一された関数呼び出し構文をサポートしており、メソッド構文.演算子を通じて任意の関数合成を可能にします。^[3]

func foo ( a : int ) : string = $ a func bar ( a : string , count : int ) : seq [ string ] = for i in 0 .. < count : result.add ( a ) func baz ( a : seq [ string ] ) = for i in a : echo i     
      
       
    
   
     
     

# 同等です! 
echo foo ( 5 ). bar ( 6 ). baz () echo baz ( bar ( 6 , foo ( 5 ))) 
  

Pythonでは、関数のグループの構成を定義する方法として、reduce関数を使用します (Python 3 では functools.reduce を使用します)。

# Python v2.6 以降で利用可能
from  functools  import  Reduce 
from  entering  import  Callable

def  compose ( * funcs )  ->  Callable [[ int ],  int ]: 
"""関数のグループ (f(g(h(...)))) を 1 つの複合関数に合成します。""" return Reduce ( lambda f , g : lambda x : f ( g ( x )), funcs )    
           

# 例
f  =  lambda  x :  x  +  1 
g  =  lambda  x :  x  *  2 
h  =  lambda  x :  x  -  3

# 関数 x=10 を呼び出す: ((x-3)*2)+1 = 15 
print ( compose ( f ,  g ,  h )( 10 ))

JavaScriptでは、2 つの関数 f と g を受け取り、関数を生成する関数として定義できます。

関数o ( f , g ) {関数( x )を返す{ f ( g ( x )を返す); } }   
      
         
    



// あるいは、ES2015 の残り演算子とラムダ式を使用するconst compose = (... fs ) => ( x ) => fs .reduceRight (( acc , f ) => f ( acc ), x )           

C#では、Funcs f と g を受け取り、新しい Func を生成する Extension メソッドとして定義できます。

// 呼び出し例: 
// var c = f.ComposeWith(g); 
// 
// Func<int, bool> g = _ => ... 
// Func<bool, string> f = _ => ...

パブリックスタティックFunc < T1 、T3 > ComposeWith < T1 、T2 、T3 > ( this Func < T2 、T3 > f 、Func < T1 、T2 > g ) => x => f ( g ( x ));                

Rubyのような言語では、バイナリ演算子を自分で構築できます。

クラスProc def compose ( other_fn ) -> ( * as ) { other_fn . call ( call ( * as )) } end alias_method :+ , :compose end 
   
       
  
    


f = -> ( x ) { x * 2 } g = -> ( x ) { x ** 3 } ( f + g ) . call ( 12 ) # => 13824       
       
   

しかし、Ruby 2.6ではネイティブ関数合成演算子が導入されました: ^[4]

f = proc { | x | x + 2 } g = proc { | x | x * 3 } ( f << g ) . call ( 3 ) # -> 11; f(g(3)) と同じ( f >> g ) . call ( 3 ) # -> 15; g(f(3)) と同じ     
     
   
   

構成性や構成可能性の原理を含む構成の概念は非常に普遍的であるため、多数の研究分野が別々に発展してきました。以下は、構成の概念が中心となる種類の研究のサンプルです。

• Steele (1994) は、関数合成を、 Haskell プログラミング言語の「モナド」と呼ばれる構成要素の集合体に直接適用しました。
• マイヤー（1988）は、ソフトウェアの再利用の問題を構成可能性の観点から取り上げました。
• Abadi & Lamport (1993) は、プログラムの安全性と活性を保証する関数合成の証明規則を正式に定義しました。
• Kracht (2001) は、構成性を記号論的システムの中に組み込み、計算言語学で頻繁に遭遇する構造的曖昧性の問題に適用することで、構成性の強化された形式を特定しました。
• van Gelder & Port (1993) は、自然言語処理のアナログな側面における構成性の役割を調査しました。
• Gibbons (2002) のレビューによると、IBM のJava言語向け Visual Age などのビジュアル プログラミング言語におけるコンポーネント アセンブリの検証は、構成の形式的な処理に基づいています。

プログラムやシステム全体を関数として扱うことができ、入力と出力が明確に定義されていれば簡単に構成することができます。^[5] フィルターを簡単に構成できるパイプラインは非常に成功し、オペレーティングシステムの デザインパターンになりました。

副作用のある命令型プロシージャは参照の透明性に違反するため、きれいに構成できません。ただし、コードの実行前と実行後の「世界の状態」をその入力と出力として考えると、きれいな関数が得られます。このような関数の合成は、プロシージャを次々に実行することに対応します。モナド形式はこの考え方を使用して、副作用と入出力 (I/O) を関数型言語に組み込みます。

• カレー作り
• 機能分解
• 実装の継承
• 継承セマンティクス
• 反復子
• パイプライン (Unix)
• 構成性の原則
• 仮想継承

• アバディ、マルティン、ランポート、レスリー(1993)、「仕様の作成」(PDF)、ACM Transactions on Programming Languages and Systems、15 (1): 73–132、doi :10.1145/151646.151649。
• Cox, Brad (1986)、『オブジェクト指向プログラミング、進化的アプローチ』、マサチューセッツ州レディング: Addison-Wesley、Bibcode :1986oopa.book.....C、ISBN 978-0-201-54834-1。
• Daume、Hal III、もう一つのHaskellチュートリアル。
• デマルコ、トム、リスター、ティム (1995)、「ソフトウェア開発: 最新技術と実践の現状」、デマルコ、トム(編)、『ソフトウェアのコストがなぜこんなに高いのか、そして情報化時代のその他の謎』、ニューヨーク、NY: ドーセット ハウス、ISBN 0-932633-34-X。
• ヴァン ゲルダー、ティモシー、ポート、ロバート (1993)、「シンボリックを超えて: 構成性のカーマスートラへの序論」、ホナバー、ヴァサント、ウーア、レナード(編)、人工知能と認知におけるシンボル処理とコネクショニスト モデル: 統合へのステップ、アカデミック プレス。
• ギボンズ、ジェレミー(2002)、「ビジュアルプログラミングのための余極限ベースのセマンティクスに向けて」、アルバブ、ファルハド、タルコット、キャロリン (編)、Proc. 5th International Conference on Coordination Models and Languages (PDF)、Lecture Notes in Computer Science、vol. 2315、Springer-Verlag、pp. 339–350、doi :10.1007/3-540-46000-4_18、ISBN 978-3-540-43410-8。
• コーン、ヘンリー、リベリ、アルバート（1974）、関数への初等的アプローチ、ニューヨーク、NY：マグロウヒル、ISBN 0-07-035339-5。
• Kracht, Marcus (2001)、「厳密な構成性とリテラル移動文法」、Proc. 3rd International Conference on Logical Aspects of Computational Linguistics、Lecture Notes in Computer Science、vol. 2014、Springer-Verlag、pp. 126–143、doi :10.1007/3-540-45738-0_8、ISBN 978-3-540-42251-8。
• マイヤー、バートランド（1988）、オブジェクト指向ソフトウェア構築、ニューヨーク、ニューヨーク州：プレンティスホール、pp. 13-15、ISBN 0-13-629049-3。
• ミラー、ジョージ A. (1956)、「魔法の数字 7、プラスマイナス 2: 情報処理能力の限界」、心理学評論、63 (2): 81–97、doi :10.1037/h0043158、hdl : 11858/00-001M-0000-002C-4646-B、PMID  13310704、2010-06-19 にオリジナルからアーカイブ、2010-05-02 に取得。
• ピアス、ベンジャミン C.、ターナー、デビッド N. (2000)、「Pict: π 計算に基づくプログラミング言語」、証明、言語、相互作用: ロビン ミルナーを讃えたエッセイ、コンピューティングの基礎シリーズ、ケンブリッジ、マサチューセッツ州: MIT プレス、pp. 455–494、ISBN 0-262-16188-5。
• Raymond, Eric S. (2003)、「1.6.3 構成のルール: 他のプログラムと接続されるようにプログラムを設計する」、The Art of Unix Programming、Addison-Wesley、pp. 15–16、ISBN 978-0-13-142901-7。
• Steele, Guy L. Jr. (1994)、「モナドの合成によるインタープリタの構築」、第 21 回 ACM プログラミング言語原理シンポジウム、pp. 472–492、doi : 10.1145/174675.178068、ISBN 0-89791-636-0。