変更できる変数がまだ必要だと思いますか?必要な場合はその理由を教えてください。

https://stackoverflow.com/questions/610956

03-07-2019
|

質問

私が関数型言語に対して聞いた議論の 1 つは、単一代入コーディングは難しすぎる、または少なくとも「通常の」プログラミングよりもはるかに難しいというものです。

しかし、自分のコードを見直してみると、ある程度現代的な言語で記述している場合、単一の割り当てフォームを使用して同様にうまく記述できない使用パターンは実際には多く (まったく?) ないことに気付きました。

では、スコープの 1 回の呼び出し内で変化する変数の使用例は何でしょうか?ループのインデックス、パラメータ、その他のスコープ境界値は変化することに留意してください。間この場合、呼び出しは複数の代入ではありません (ただし、 しなければならない 何らかの理由で本体内でそれらを変更してください）、アセンブリ言語レベルよりもはるかに高いレベルで次のようなものを記述できると仮定します。

values.sum

または (合計が提供されない場合)

function collection.sum --> inject(zero, function (v,t) --> t+v )

そして

x = if a > b then a else b

または

n = case s 
  /^\d*$/ : s.to_int
  ''      : 0
  '*'     : a.length
  '?'     : a.length.random
  else    fail "I don't know how many you want"

必要に応じて、リスト内包表記、マップ/収集などを利用できるようになります。

このような環境でも可変変数が必要であると思いますか?もしそうなら、何のために必要ですか?

明確にするために、私は SSA フォームに対する反対意見を列挙することを求めているのではなく、それらの反対意見が適用される具体的な例を求めています。可変変数を使用し、可変変数なしでは書けない、明確で簡潔なコードを探しています。

これまでのところ私のお気に入りの例 (そして、それらに対する私が期待する最大の反論):

ポール・ジョンソンのフィッシャー・イェーツアルゴリズムこれは、big-O 制約を含めると非常に強力です。しかし、catulahoops が指摘しているように、big-O の問題は SSA の問題ではなく、むしろ可変データ型を持つことに関係しており、それを脇に置くと、アルゴリズムは SSA でかなり明確に書くことができます。
```
 shuffle(Lst) ->
     array:to_list(shuffle(array:from_list(Lst), erlang:length(Lst) - 1)).
 shuffle(Array, 0) -> Array;
 shuffle(Array, N) ->
     K = random:uniform(N) - 1,
     Ek = array:get(K, Array),
     En = array:get(N, Array),
     shuffle(array:set(K, En, array:set(N, Ek, Array)), N-1).
```

jpalecekの多角形の面積例：

def area(figure : List[Point]) : Float = {
  if(figure.empty) return 0
  val last = figure(0)
  var first= figure(0)
  val ret = 0
  for (pt <- figure) {
    ret+=crossprod(last - first, pt - first)
    last = pt
  }
  ret
}

これはまだ次のように書かれているかもしれません:

def area(figure : List[Point]) : Float = {
    if figure.length < 3
        0
      else
        var a = figure(0)
        var b = figure(1)
        var c = figure(2)
        if figure.length == 3
            magnitude(crossproduct(b-a,c-a))
          else 
            foldLeft((0,a,b))(figure.rest)) { 
               ((t,a,b),c) => (t+area([a,b,c]),a,c)
               }

あるいは、この定式化の密度に反対する人もいますので、次のように言い換えることもできます。

def area([])    = 0.0   # An empty figure has no area
def area([_])   = 0.0   # ...nor does a point
def area([_,_]) = 0.0   # ...or a line segment
def area([a,b,c]) =     # The area of a triangle can be found directly
    magnitude(crossproduct(b-a,c-a))
def area(figure) =      # For larger figures, reduce to triangles and sum
    as_triangles(figure).collect(area).sum

def as_triangles([])      = []  # No triangles without at least three points
def as_triangles([_])     = []
def as_triangles([_,_])   = []
def as_triangles([a,b,c | rest) = [[a,b,c] | as_triangles([a,c | rest])]

不変構造で O(1) キューを実装することの難しさについての Princess の指摘は興味深い (そして、説得力のある例の基礎を提供するかもしれない) が、前述したように、それは基本的にデータ構造の可変性に関するものであり、複数の代入の問題に関するものではありません。。
私はエラトステネスの篩の答えに興味をそそられましたが、納得はしていません。彼が引用した論文に記載されている適切な big-O は、必要なだけ素数をプルするジェネレーターですが、SSA の有無にかかわらず、正しく実装するのは簡単ではないようです。

そうですね、皆さん試してくれてありがとう。答えのほとんどは、1) 単一の代入ではなく、可変のデータ構造に基づいている、2) 単一の代入形式に関するものであり、当業者であれば簡単に反論できる、のいずれかであることが判明したため、私は次のようにします。私の講演の線を引いたり、再構成したりしてください (時間切れになる前に、万が一言葉が足りなくなった場合に備えて、ディスカッションのトピックとしてバックアップしておくとよいでしょう)。

再度、感謝します。

解決

このようなケースを特定したことはありません。また、SSA形式への変換のように、いつでも新しい名前を作成することができますが、実際には、各値が独自の名前を持つことは簡単で自然なことです。 Haskellのような言語では、名前を付ける値について多くの選択肢があり、名前バインディングを配置する2つの異なる場所（ let と where ）があります。単一割り当てフォームは非常に自然であり、まったく難しいものではありません。

時折、ヒープ上の可変オブジェクトへのポインタを持つことができません。しかし、これらのものには名前がないので、同じ異議はありません。（また、ヒープで可変オブジェクトを使用すると、より多くのバグを作成する傾向があることもわかりました！）

他のヒント

私が遭遇した最も難しい問題は、リストをシャッフルすることです。 Fisher-Yates アルゴリズム（Knuthアルゴリズムとも呼ばれる）には、リストの反復処理が含まれます各アイテムをランダムな他のアイテムと交換します。アルゴリズムはO（n）であり、既知であり、長い間正しいことが証明されています（一部のアプリケーションでは重要な特性です）。ただし、可変配列が必要です。

それは、機能的なプログラムではシャッフルができないと言っているわけではありません。 Oleg Kiselyovはこれについて書いています。しかし、彼を正しく理解していれば、関数シャッフルはO（n。log n）です。これはバイナリツリーを構築することで機能するからです。

もちろん、HaskellでFisher-Yatesアルゴリズムを記述する必要がある場合は、 STモナド。これにより、可変配列は、次のような純粋な関数内にあります。

-- | Implementation of the random swap algorithm for shuffling.  Reads a list
-- into a mutable ST array, shuffles it in place, and reads out the result
-- as a list.

module Data.Shuffle (shuffle) where


import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.STRef
import System.Random

-- | Shuffle a value based on a random seed.
shuffle :: (RandomGen g) => g -> [a] -> [a]
shuffle _ [] = []
shuffle g xs = 
    runST $ do
      sg <- newSTRef g
      let n = length xs
      v <- newListArray (1, n) xs
      mapM_ (shuffle1 sg v) [1..n]
      getElems v

-- Internal function to swap element i with a random element at or above it.
shuffle1 :: (RandomGen g) => STRef s g -> STArray s Int a -> Int -> ST s ()
shuffle1 sg v i = do
  (_, n) <- getBounds v
  r <- getRnd sg $ randomR (i, n)
  when (r /= i) $ do
    vi <- readArray v i
    vr <- readArray v r
    writeArray v i vr
    writeArray v r vi


-- Internal function for using random numbers
getRnd :: (RandomGen g) => STRef s g -> (g -> (a, g)) -> ST s a
getRnd sg f = do
  g1 <- readSTRef sg
  let (v, g2) = f g1
  writeSTRef sg g2
  return

学術的な議論をしたい場合は、もちろん、変数を複数回割り当てる必要はありません。証拠は、すべてのコードが SSA（単一の静的割り当て）形式で表現できることです。確かに、これは多くの種類の静的および動的分析にとって最も有用な形式です。

同時に、最初からSSA形式でコードを書かない理由があります：

通常、この方法でコードを記述するには、より多くのステートメント（またはコード行）が必要です。簡潔さには価値があります。
ほとんど常に非効率的です。はい、あなたは高等言語について話していることを知っています-公正な範囲-しかし、JavaとC＃の世界でさえ、アセンブリから遠く離れて、速度が重要です。速度が関係ないアプリケーションはほとんどありません。
理解するのは簡単ではありません。 SSAは「シンプル」ですが、数学的な意味では、常識からより抽象的です。これは、実際のプログラミングでは重要です。あなたがそれを本当に賢くする必要があるなら、それはプログラミング全般に場所がありません。

上記の例でも、穴を開けるのは簡単です。 case ステートメントを受け取ります。 '*' を許可するかどうかを決定する管理オプションと、 '？' を許可するかどうかを個別に管理するオプションがある場合はどうなりますか？また、整数の場合、ユーザーに許可されているシステム権限がない限り、ゼロは許可されません。

これは、ブランチと条件を含むより現実的な例です。これを単一の「ステートメント」として記述できますか？もしそうなら、あなたの「声明」は多くの個別のステートメントとは本当に違いますか？そうでない場合、一時的な書き込み専用変数はいくつ必要ですか？そして、その状況はただ一つの変数を持つよりもはるかに良いですか？

OCamlやF＃など、機能的なスタイルと命令的なスタイルを混在させることができる最も生産的な言語が見つかると思います。

ほとんどの場合、「xをyにマップし、yをzに減らす」という長い行のコードを書くことができます。 95％の場合、関数型プログラミングはコードを単純化しますが、不変性が歯を見せている領域が1つあります：

実装の容易さと不変のスタックと不変のキューの間の大きな不一致。

スタックは簡単で、永続性とうまくメッシュします。キューはばかげています。

最も不変キューの一般的な実装は、1つ以上の内部スタックとスタックローテーションを使用します。利点は、これらのキューがほとんどの場合でO（1）で実行されることですが、一部の操作はO（n）で実行されます。アプリケーションの永続性に依存している場合、原則としてすべての操作がO（n）で実行される可能性があります。これらのキューは、リアルタイム（または少なくとも一貫した）パフォーマンスが必要な場合は役に立ちません。

岡崎クリスは、彼の本に不変のキューの実装を提供しています。すべての操作でO（1）を達成するための怠iness。リアルタイムキューの非常に賢明で合理的な実装ですが、その基礎となる実装の詳細を深く理解する必要があり、それでも不変スタックよりもはるかに複雑です。

constrastでは、すべての操作で一定の時間で実行される可変リンクリストを使用してスタックとキューを記述できます。結果のコードは非常に簡単です。

ポリゴンの領域に関しては、ポリゴンを機能的な形に簡単に変換できます。次のようなVectorモジュールがあるとします：

module Vector =
    type point =
        { x : float; y : float}
        with
            static member ( + ) ((p1 : point), (p2 : point)) =
                { x = p1.x + p2.x;
                  y = p1.y + p2.y;}

            static member ( * ) ((p : point), (scalar : float)) =
                { x = p.x * scalar;
                  y = p.y * scalar;}

            static member ( - ) ((p1 : point), (p2 : point)) = 
                { x = p1.x - p2.x;
                  y = p1.y - p2.y;}

    let empty = { x = 0.; y = 0.;}
    let to_tuple2 (p : point) = (p.x, p.y)
    let from_tuple2 (x, y) = { x = x; y = y;}
    let crossproduct (p1 : point) (p2 : point) =
        { x = p1.x * p2.y; y = -p1.y * p2.x }

少しのタプルマジックを使用して、エリア関数を定義できます。

let area (figure : point list) =
    figure
    |> Seq.map to_tuple2
    |> Seq.fold
        (fun (sum, (a, b)) (c, d) -> (sum + a*d - b*c, (c, d) ) )
        (0., to_tuple2 (List.hd figure))
    |> fun (sum, _) -> abs(sum) / 2.0

または、代わりにクロス積を使用できます

let area2 (figure : point list) =
    figure
    |> Seq.fold
        (fun (acc, prev) cur -> (acc + (crossproduct prev cur), cur))
        (empty, List.hd figure)
    |> fun (acc, _) -> abs(acc.x + acc.y) / 2.0

どちらの関数も判読できないとは思わない。

このシャッフルアルゴリズムは、単一の割り当てを使用して実装するのは簡単です。実際、反復が末尾再帰に書き換えられた命令型ソリューションとまったく同じです。（ErlangはHaskellよりも速く書くことができるからです。）

 shuffle(Lst) ->
     array:to_list(shuffle(array:from_list(Lst), erlang:length(Lst) - 1)).

 shuffle(Array, 0) -> Array;
 shuffle(Array, N) ->
     K = random:uniform(N) - 1,
     Ek = array:get(K, Array),
     En = array:get(N, Array),
     shuffle(array:set(K, En, array:set(N, Ek, Array)), N-1).

これらの配列操作の効率が懸念される場合、それは可変データ構造に関する問題であり、単一の割り当てとは関係ありません。

例が存在しないため、この質問に対する答えは得られません。これは、このスタイルに精通していることの問題です。

ジェイソンへの応答で-

function forbidden_input?(s)
    (s = '?' and not administration.qmark_ok) ||
    (s = '*' and not administration.stat_ok)  ||
    (s = '0' and not 'root node visible' in system.permissions_for(current_user))

n = if forbidden_input?(s)
    fail "'" + s + "' is not allowed."
  else
    case s
      /^\d*$/ : s.to_int
      ''      : 0
      '*'     : a.length
      '?'     : a.length.random
      else    fail "I don't know how many you want"

純粋に関数型ではない言語での割り当てを見逃します。主に、ループの有用性を妨げるためです。例（Scala）：

def quant[A](x : List[A], q : A) = {
  var tmp : A=0
  for (el <- x) { tmp+= el; if(tmp > q) return el; }
  // throw exception here, there is no prefix of the list with sum > q
}

これはリストの分位数を計算する必要があります。複数回割り当てられるアキュムレータ tmp に注意してください。

同様の例は次のとおりです。

def area(figure : List[Point]) : Float = {
  if(figure.empty) return 0
  val last = figure(0)
  var first= figure(0)
  val ret = 0
  for (pt <- figure) {
    ret+=crossprod(last - first, pt - first)
    last = pt
  }
  ret
}

主に last 変数に注意してください。

これらの例は、複数の割り当てを回避するためにタプルでfoldを使用して書き換えることができますが、実際には読みやすくなりません。

ローカル（メソッド）変数が2回割り当てられることはありません。ただし、関数型プログラミングでも、変数の再割り当ては許可されています。許可されていない値の変更（の一部）です。 dsimchaがすでに答えたように、非常に大きな構造（おそらくアプリケーションのルート）の場合、構造全体を置き換えることは現実的ではないようです。考えてみてください。アプリケーションの状態はすべて、最終的にアプリケーションのエントリポイントメソッドに含まれます。置き換えられずに状態がまったく変化しない場合、キーストロークごとにアプリケーションを再起動する必要があります。：（

遅延リスト/ツリーを構築してから再び縮小する関数がある場合、機能コンパイラは森林破壊。

トリッキーな場合、そうではないかもしれません。そして、あなたは運、パフォーマンス、そして反復可能な変数および可変変数を使用できる場合を除き、メモリに関しては賢明です。

教会チューリング論文のおかげで、チューリング完全言語で記述できるものはすべて、 任意の チューリング完全言語で記述できることがわかっています。それで、あなたがそれに真っ先に着くとき、あなたがC＃でできなかったこと、あなたが十分に努力した場合、またはその逆で、あなたがLispでできないことは何もありません。（要点は、いずれにしても、ほとんどの場合、いずれかがx86マシン言語にコンパイルされます。）

つまり、あなたの質問に対する答えは、そのようなケースはありません。あるパラダイム/言語で人間が理解しやすいケースがすべてあります。ここでの理解の容易さは、トレーニングと経験に関係しています。

おそらくここでの主な問題は、言語のループのスタイルでしょう。再帰を使用する言語では、関数が再び呼び出されたときに、ループの過程で変化する値が再バインドされます。ブロックでイテレータを使用する言語（SmalltalkとRubyの inject メソッドなど）は似ている傾向がありますが、Rubyの多くの人は依然として each と上の可変変数を使用します注入。

while および for を使用してループをコーディングする場合、渡すことができるときに自動的に来る変数の簡単な再バインドはありません。ループの1回の繰り返しを行うコードチャンクのいくつかのパラメーターで、不変変数はかなり不便になります。

Haskellでの作業は、可変変数の必要性を調査するための非常に良い方法です。デフォルトは不変ですが、可変変数は利用可能です（ IORefs 、 MVars 、など）。私は最近、「調査中」です。このようにして、次の結論に達しました。

ほとんどの場合、可変変数は不要であり、変数なしで生活できてうれしいです。
スレッド間通信には、かなり明白な理由から、可変変数が不可欠です。（これはHaskellに固有です;最下位レベルでメッセージの受け渡しを使用するランタイムシステムはもちろんそれらを必要としません。）しかし、この使用はまれであり、関数を使用してそれらを読み書きする必要があります（ readIORef fooRef val など）はそれほど負担になりません。
単一のスレッド内で可変変数を使用しました。特定のことを簡単にするように思えたのですが、後で格納された値に何が起こっているのかを推論するのが非常に難しくなったことに気づき、後悔しました。（いくつかの異なる関数がその値を操作していました。）これは少し目を見張るものでした。典型的な温かい水のカエルのスタイルでは、Haskellが値の使用について推論するのがどれほど簡単かを理解していませんでしたが、値を使用する方法の例を見つけるまでは。

したがって、最近では不変の変数の側面にかなりしっかりと落ち着きました。

この質問に対する以前の回答はこれらのことを混乱させていたので、この問題は純粋なプログラミングと関数型プログラミングの両方に直交していることをここで非常に力強く指摘しなければならないと思います。たとえば、Rubyは単一割り当てのローカル変数を使用することでメリットが得られると思いますが、これを本当に便利にするためには、おそらく末尾再帰の追加など、言語にいくつかの変更を加える必要があります。

大規模なデータ構造に小さな変更を加える必要がある場合はどうですか？いくつかの要素を変更するたびに、配列全体または大きなクラスをコピーするのは本当に望ましくありません。

あなたが指摘していることを除いて、これについてはあまり考えていません。

実際には、無意識のうちに複数の割り当てを使用しないようにしています。

Pythonでのイムの話の例

start = self.offset%n
if start:
    start = n-start

不要な余分なモジュロまたは減算を回避するためにこの方法で書かれました。これは、bignumスタイルのlong intで使用されるため、価値のある最適化です。ただし、それに関することは、それが実際に単一の割り当てであるということです。

複数の割り当てを見逃すことはありません。

可変変数の利点を示すコードを求めていることは承知しています。そしてそれを提供できればと思います。しかし、前に指摘したように、両方の方法で表現できない問題はありません。そして特に、jpalecek のポリゴン例の領域は折りたたみアルゴリズム (私見ですが、これははるかに厄介で、問題をさまざまな複雑さのレベルに引き上げます) で記述できると指摘して以来、なぜ可変性について非難するのか不思議に思いました。難しい。そこで、共通の根拠と、不変データと可変データの共存についての議論を試みます。

私の意見では、この質問は少し要点を外しています。私たちプログラマーはクリーンでシンプルなものを好む傾向があることはわかっていますが、混合も可能であることを見逃してしまうことがあります。そしておそらくそれが、不変性に関する議論で中間点を取る人がほとんどいない理由です。なぜだろうと思うのですが、正直に言ってみましょう - 不変性は素晴らしいツールです あらゆる種類の問題を抽象化します。しかし、時々それは お尻の大きな痛み. 。場合によっては、単に制約が強すぎる場合もあります。それだけでも、私は立ち止まって考えてしまいます - 私たちは本当に可変性を失いたいのでしょうか？それは本当に二者択一なのでしょうか？ 何か共通点はないのでしょうか 到着できるでしょうか？不変性があれば目標をより早く達成できるのはどのような場合ですか?また、可変性がある場合はどのような場合ですか? どのソリューションが読みやすく保守しやすいでしょうか? （これが私にとって最大の質問です）

これらの質問の多くは、プログラマーの好みやプログラミングに使用されるものによって影響されます。そこで、私は通常、不変性支持の議論の中心となる側面の 1 つである並列性に焦点を当てます。

多くの場合、並列処理は不変性に関する議論に投入されます。私は、妥当な時間内に解くのに 100 以上の CPU を必要とする問題セットに取り組んできました。そして、それは私にとても重要なことを教えてくれました。ほとんどの場合、データのグラフ操作を並列化することは、実際には最も効率的な並列化方法ではありません。それは確かに大きな利益をもたらす可能性がありますが、その問題領域では不均衡が本当の問題です。したがって、通常は複数の可変グラフを並行して処理し、不変メッセージで情報を交換する方がはるかに効率的です。つまり、グラフが孤立していて、外部に公開していないことがわかっているときは、思いつく限り最も簡潔な方法でグラフに対して操作を実行したいと考えます。そして、それには通常、データの変更が含まれます。しかし、データに対するこれらの操作の後、データを全世界に公開したいと考えています。データが変更可能である場合、通常少し緊張するのはこの点です。プログラムの他の部分がデータを破損する可能性があるため、状態は無効になります。なぜなら、世界に公開された後、データは並列処理の世界に入ることがよくあるからです。

したがって、現実世界の並列プログラムには通常、データグラフが最終的なシングルスレッド操作で使用される領域 (データグラフは単に外部には知られていないため) と、データグラフがマルチスレッド操作に関与する可能性がある領域 (できれば操作されていないデータを提供するだけ) があります。。これらのマルチスレッド部分では、それらが変更されることは決して望ましくありません。単純に、一貫性のないデータを処理するよりも、古いデータを処理するほうが良いのです。これは不変性の概念によって保証できます。

そこで私は次のような単純な結論に達しました。私にとっての本当の問題は、私がよく知っているプログラミング言語では次のようなことができないことです。 「この時点以降、このデータ構造全体は不変になります。」 そして「この不変データ構造の変更可能なコピーをここに渡してください。私だけがその変更可能なコピーを見ることができることを確認してください。」. 。現時点では、読み取り専用ビットまたは同様のものを反転して、自分でそれを保証する必要があります。コンパイラがこれをサポートできれば、ビットを反転した後に愚かなことをしていないことが保証されるだけでなく、コンパイラが以前は実行できなかったさまざまな最適化を実際に実行できるようになります。さらに、命令型プログラミングモデルに精通しているプログラマにとって、この言語は依然として魅力的です。

要約すると。私見では 通常、プログラムにはデータグラフの不変表現と可変表現の両方を使用する十分な理由があります。. 。データは次のようにすべきだと私は主張します。 デフォルトで不変 そしてコンパイラはそれを強制する必要がありますが、 プライベートな可変表現の概念, なぜなら、当然のことながら、マルチスレッドでは決して到達できない領域が存在し、より命令型の構造化によって可読性と保守性が向上する可能性があるからです。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow