Functional, Declarative, and Imperative Programming [closed] Ask Question

At the time of writing this, the top voted answers on this page are imprecise and muddled on the declarative vs. imperative definition, including the answer that quotes Wikipedia. Some answers are conflating the terms in different ways.

Refer also to my explanation of why spreadsheet programming is declarative, regardless that the formulas mutate the cells.

Also, several answers claim that functional programming must be a subset of declarative. On that point it depends if we differentiate "function" from "procedure". Lets handle imperative vs. declarative first.

Definition of declarative expression

The only attribute that can possibly differentiate a declarative expression from an imperative expression is the referential transparency (RT) of its sub-expressions. All other attributes are either shared between both types of expressions, or derived from the RT.

A 100% declarative language (i.e. one in which every possible expression is RT) does not (among other RT requirements) allow the mutation of stored values, e.g. HTML and most of Haskell.

Definition of RT expression

RT is often referred to as having "no side-effects". The term effects does not have a precise definition, so some people don't agree that "no side-effects" is the same as RT. RT has a precise definition:

An expression e is referentially transparent if for all programs p every occurrence of e in p can be replaced with the result of evaluating e, without affecting the observable result of p.

Since every sub-expression is conceptually a function call, RT requires that the implementation of a function (i.e. the expression(s) inside the called function) may not access the mutable state that is external to the function (accessing the mutable local state is allowed). Put simply, the function (implementation) should be pure.

Definition of pure function

A pure function is often said to have "no side-effects". The term effects does not have a precise definition, so some people don't agree.

Pure functions have the following attributes.

• the only observable output is the return value.
• 出力の唯一の依存関係は引数です。
• 出力が生成される前に引数が完全に決定されます。

RT は式 (関数呼び出しを含む) に適用され、純度は関数 (の実装) に適用されることに留意してください。

RT 式を作成する不純な関数のわかりにくい例としては並行性がありますが、これは割り込み抽象化レイヤーで純粋性が損なわれるためです。これについて知る必要はまったくありません。RT 式を作成するには、純粋関数を呼び出します。

RT の派生属性

宣言型プログラミングで引用されるその他の属性、例えば1999年の引用Wikipedia で使用されているものは、RT から派生したものか、命令型プログラミングと共有されています。したがって、私の正確な定義が正しいことが証明されます。

注意：外部価値RT の要件のサブセットです。

• 宣言型言語には、 や などのループ制御構造がありません。forこれwhileは、不変性により、ループ条件が変わることがないためです。

• 宣言型言語は、ネストされた関数の順序 (論理的な依存関係とも呼ばれます) 以外の制御フローを表現しません。これは、不変性により、評価順序の他の選択によって結果が変わらないためです (以下を参照)。

• 宣言型言語は論理的な「ステップ」（つまり、ネストされた RT 関数呼び出しの順序）を表現しますが、各関数呼び出しがより高いレベルのセマンティクス（つまり、「何をするか」）であるかどうかは、宣言型プログラミングの要件ではありません。命令型との違いは、不変性（つまり、より一般的には RT）のため、これらの「ステップ」は可変状態には依存できず、表現されたロジックの関係順序（つまり、関数呼び出しのネスト順序、つまりサブ式）のみに依存することです。

たとえば、HTML段落は、<p>段落内のサブ式（つまりタグ）が評価されるまで表示されません。変更可能な状態はなく、タグ階層の論理関係（サブ式のネスト、これは同様にネストされた関数呼び出し）。

• したがって、不変性 (より一般的には RT )の派生属性があり、宣言式は構成要素 (つまり、サブ式の関数引数) の論理関係のみを表現し、可変状態関係は表現しません。

評価順序

部分式の評価順序の選択によって、関数呼び出しのいずれかが RT でない (つまり関数が純粋でない) 場合にのみ、さまざまな結果が得られます。たとえば、関数外部の変更可能な状態が関数内でアクセスされる場合などです。

たとえば、 などのネストされた式がいくつかあるf( g(a, b), h(c, d) )場合、関数f、g、 がh純粋であれば、関数の引数の積極的な評価と遅延評価は同じ結果になります。

一方、関数f、g、 がh純粋でない場合は、評価順序の選択によって異なる結果が得られる可能性があります。

式演算子は単項接頭辞、単項接尾辞、または二項中置表記を装った単なる関数呼び出しであるため、ネストされた式は概念的にはネストされた関数であることに注意してください。

余談ですが、すべての識別子 ( a、b、cなどd) がどこでも不変で、プログラム外部の状態 (I/O など) にアクセスできず、抽象化レイヤーが破損していない場合、関数は常に純粋です。

ちなみに、Haskell には異なる構文がありますf (g a b) (h c d)。

評価注文の詳細

関数は入力から出力への状態遷移（可変の格納値ではない）である。純粋関数呼び出しのRT合成では、これらの状態遷移の実行順序は独立している。各関数呼び出しの状態遷移は、副作用がなく、関数呼び出しは他の関数呼び出しから独立しているという原則に基づいている。RT関数はキャッシュされた値に置き換えられる可能性がある。 によくある誤解を正す純粋なモナド構成は常に宣言的かつRTにもかかわらず、HaskellのIOモナドはおそらく不純したがって、Worldプログラムの外部の状態に関しては命令的です (ただし、以下の警告の意味で、副作用は分離されています)。

積極的評価とは関数が呼び出される前に関数の引数が評価されることを意味し、遅延評価とは引数は評価されない関数内でアクセスされるまで（そしてアクセスされた場合）。

定義: 関数パラメータは関数定義サイトで宣言され、関数引数は関数呼び出しサイトで提供されます。パラメータと引数の違いを理解してください。

概念的には、すべての式は関数呼び出し（の合成）です。例えば、定数は入力のない関数、単項演算子は1つの入力を持つ関数、二項演算子は2つの入力を持つ関数、コンストラクタは関数であり、制御文（例えばif、、for）もwhile関数でモデル化できます。これらを命じる 引数関数 (ネストされた関数の呼び出し順序と混同しないでください) は、構文によって宣言されていない で評価されます。たとえば、の結果に対して をf( g() )積極的に評価することgも、 を評価して、その結果が 内で必要な場合にのみ を遅延評価することもできます。fgfgf

注意：いいえチューリング完全言語（つまり、無制限の再帰を許可する言語）は完全に宣言的であり、例えば、遅延評価はメモリと時間の不確定性を導入する。しかし、評価順序の選択によるこれらの副作用は、メモリ消費、実行時間、レイテンシ、非終了性、および外部ヒステリシスつまり外部同期です。

関数型プログラミング

宣言型プログラミングではループを使用できないため、反復処理を実行する唯一の方法は関数型再帰です。この意味で、関数型プログラミングは宣言型プログラミングに関連しています。

しかし、関数型プログラミングは宣言型プログラミングに限定されません。関数型合成はサブタイプ化とは対照的特に、表現の問題、拡張は次のように達成できる。サブタイプの追加または機能分解。拡張は組み合わせることができる両方の方法論の。

関数型プログラミングでは通常、関数はファーストクラス オブジェクトになります。つまり、関数型は文法内の他の型が出現できる場所であればどこにでも出現できます。その結果、関数は関数を入力したり操作したりできるため、関数の構成を強調して関心の分離、つまり決定論的計算のサブ計算間の依存関係を分離できます。

例えば、別の関数を書く代わりに（関数も宣言的である必要がある場合は、ループの代わりに再帰を使用します）コレクションの各要素に適用できる可能性のある無限の数の特殊アクションのそれぞれに対して、関数型プログラミングでは、再利用可能な反復関数（、、など）を使用しますmap。foldこれらfilterの反復関数は、ファーストクラスの特殊アクション関数を入力します。これらの反復関数は、コレクションを反復し、各要素に対して入力された特殊アクション関数を呼び出します。これらのアクション関数は、コレクションを反復するためのループ文を含める必要がなくなったため、より簡潔になっています。

ただし、関数が純粋でない場合は、実際には手続き型であることに注意してください。純粋でない関数を使用する関数型プログラミングは、実際には手続き型プログラミングであると主張することもできます。したがって、宣言型式が RT であることに同意する場合は、手続き型プログラミングは宣言型プログラミングではないと言うことができ、したがって、関数型プログラミングは常に RT であり、宣言型プログラミングのサブセットでなければならないと主張することができます。

並列処理

この第一級関数による関数合成は、並列性の深さ独立した機能を分離することによって。

ブレントの原理: 作業 w と深さ d の計算は、p プロセッサ PRAM で時間 O(max(w/p, d)) で実装できます。

並行性と並列性も宣言型プログラミングが必要つまり、不変性と RT です。

では、並列性 = 並行性というこの危険な仮定はどこから来たのでしょうか。これは副作用のある言語の自然な帰結です。言語のいたるところに副作用がある場合、一度に複数のことを行おうとすると、各操作の効果がインターリーブされることで、基本的に非決定性が生じます。したがって、副作用のある言語では、並列性を実現する唯一の方法は並行性です。したがって、この 2 つが混同されているのをよく見かけるのも不思議ではありません。

FP評価順序

評価順序は、関数合成の終了とパフォーマンスの副作用にも影響することに注意してください。

熱心な（CBV）と怠惰な（CBN）は、カテゴリ的な決闘である[10] は、評価順序が逆になっているため、つまり、外側の関数と内側の関数のどちらが先に評価されるかが異なります。逆さまの木を想像してください。すると、eager は関数ツリーの枝の先端から枝の階層を上って最上位の関数の幹まで評価します。一方、lazy は幹から枝の先端まで評価します。eager には連言積 ("and"、別名カテゴリの "積") がなく、lazy には選言余積 ("or"、別名カテゴリの "和") がありません。[11]。

パフォーマンス

• 熱心な

非終了の場合と同様に、eagerは結合関数合成では熱心すぎる、つまり合成制御構造はlazyでは行われない不必要な作業を行う。例最初の真の要素で終了する折り畳みでリストが構成されている場合、eager はリスト全体をブール値に熱心に、そして不必要にマッピングします。

この不必要な作業が「最大」余分な費用がかかる原因となっている。log n 係数純粋関数のeagerとlazyの逐次時間計算量を比較すると、どちらもeagerとlazyの計算量に差がある。解決策としては、関数（リストなど）をlazyコンストラクタ（つまり、eagerとオプションのlazy積）とともに使うことだ。eagerではeagerの誤りは内部関数から生じるからである。これは積が構成型、つまり初期不動点上の初期代数を持つ帰納型だからである[11]

• 怠け者

非終了性と同様に、遅延は選言的機能合成では遅延しすぎます。つまり、共帰納的終了性は必要以上に遅く発生する可能性があり、その結果、不要な作業と、遅延の非決定性の両方が発生します。これは、積極的な場合は当てはまりません。10][11]。ファイナリティの例としては、状態、タイミング、非終了、実行時例外などがあります。これらは命令型の副作用ですが、純粋な宣言型言語（Haskellなど）でも、命令型IOモナド（すべてのモナドが命令型ではないことに注意！）には空間割り当てに暗黙の状態があり、タイミングは命令型の現実世界に対する状態です。オプションのeager coproductsでもlazyを使用すると、内部coproductsに「遅延」が漏れます。lazyでは、遅延の不正確さが内部coproductsに漏れるためです。外部機能から発生する（非終了セクションの例を参照してください。ここで、==は外部二項演算子関数です）。これは、コプロダクトが最終性、つまり最終オブジェクト上の最終代数を持つ共帰納的型によって制限されるためです[11]。

遅延は、遅延とスペースに関する関数の設計とデバッグにおいて不確定性を引き起こし、そのデバッグは大多数のプログラマーの能力を超えている可能性が高い。不協和音宣言された関数階層と実行時の評価順序。eager で評価された lazy 純粋関数は、実行時にこれまでにない非終了状態を引き起こす可能性があります。逆に、lazy で評価された early 純粋関数は、実行時にこれまでにない空間とレイテンシの不確定性を引き起こす可能性があります。

非終了

コンパイル時には、チューリング完全な言語における停止問題と相互再帰のため、関数が終了することは通常保証されません。

• 熱心な

積極的だが怠惰ではない場合、 Head「and」の論理積でTail、 または のいずれかが終了しない場合は、それぞれ またはのいずれかが真ではありません。これは、左側は終了せず、右側は終了するためです。HeadTailList( Head(), Tail() ).tail == Tail()List( Head(), Tail() ).head == Head()

一方、lazy では両側が終了します。したがって、eager は連言積に対して過度に先行し、必要のない場合には終了しません (実行時例外を含む)。

• 怠け者

1遅延は有効だが積極的ではない場合、 「または」の論理和が終了しない2場合は、左側は終了し、右側は終了しないため、は真になりません。fList( f ? 1 : 2, 3 ).tail == (f ? List( 1, 3 ) : List( 2, 3 )).tail

一方、eager ではどちらの側も終了しないため、等価テストに到達することはありません。したがって、lazy は選言的コプロダクトに対しては遅延しすぎており、そのような場合には、eager の場合よりも多くの作業を行った後 (実行時例外を含む) に終了に失敗します。

[10] 宣言的継続と圏的双対性、Filinski、セクション 2.5.4 CBV と CBN の比較、および 3.6.1 SCL における CBV と CBN。

[11] 宣言的継続と圏的双対性、Filinski、セクション 2.2.1 積と余積、2.2.2 終端オブジェクトと初期オブジェクト、2.5.2 遅延積を含む CBV、および 2.5.3 積が積極的な CBN。