Считаете ли вы, что вам все еще нужны переменные, которые можно изменить, и если да, то почему?

StackOverflow https://stackoverflow.com/questions/610956

Вопрос

Один из аргументов, которые я слышал против функциональных языков, заключается в том, что кодирование с одним присваиванием слишком сложно или, по крайней мере, значительно сложнее, чем «обычное» программирование.

Но, просматривая свой код, я понял, что на самом деле у меня не так много (каких-то?) шаблонов использования, которые нельзя было бы так же хорошо написать, используя единую форму задания, если вы пишете на достаточно современном языке.

Итак, каковы варианты использования переменных, область действия которых меняется в пределах одного вызова?Принимая во внимание, что индексы цикла, параметры и другие значения, связанные с областью действия, которые различаются между вызовы в этом случае не являются множественными назначениями (если только вы придется по какой-то причине измените их в теле), и предполагая, что вы пишете на чем-то, что достаточно далеко выше уровня ассемблера, где вы можете писать такие вещи, как

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, а прошу конкретные примеры, когда эти возражения могут быть применимы.Я ищу ясные и лаконичные фрагменты кода с изменяемыми переменными, которые невозможно было бы написать без них.

Мои любимые примеры (и лучшее возражение, которое я ожидаю от них):

  1. Пола Джонсона Алгоритм Фишера-Йейтса ответ, который довольно силен, если учесть ограничения big-O.Но тогда, как указывает catulahoops, проблема большого О связана не с вопросом 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).

  2. Джпалечека площадь многоугольника пример:

    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])]

  3. Точка зрения Принцессы о сложности реализации очередей O(1) с неизменяемыми структурами интересна (и вполне может послужить основой для убедительного примера), но, как уже говорилось, она в основном касается изменяемости структуры данных, а не непосредственно проблемы множественного присваивания. .

  4. Меня заинтриговал ответ Эратосфена, но он меня не убедил.Правильный генератор big-O, вытащите столько простых чисел, сколько захотите, приведенный в цитируемой им статье, нелегко правильно реализовать с SSA или без него.

Что ж, спасибо всем за попытку.Поскольку большинство ответов оказались либо 1) основанными на изменяемых структурах данных, а не на одном назначении, и 2) в той степени, в которой они касались формы единого назначения, с которой легко могут справиться специалисты-практики в данной области, я собираюсь вычеркните линию из моего выступления и/или реструктурируйте его (может быть, сохраните его в качестве темы для обсуждения на тот маловероятный случай, если у меня закончатся слова раньше, чем закончится время).

Еще раз спасибо.

Это было полезно?

Решение

Я никогда не идентифицировал такой случай.И хотя вы всегда можете просто придумать новые имена, например, при преобразовании в форму SSA, на самом деле я считаю, что каждому значению легко и естественно иметь собственное имя.Такой язык, как Haskell, дает мне множество вариантов именования значений и два разных места для размещения привязок имен (let и where).Я считаю форму с одним заданием вполне естественной и совсем не сложной.

Иногда мне не хватает указателей на изменяемые объекты в куче.Но у этих вещей нет названий, так что это не одно и то же возражение.(А еще я обнаружил, что когда я использую изменяемые объекты в куче, я склонен писать больше ошибок!)

Другие советы

Самая сложная проблема, с которой я столкнулся, — это перетасовка списка.А Фишер-Йейтс Алгоритм (также иногда известный как алгоритм Кнута) включает в себя перебор списка, заменяя каждый элемент случайным другим элементом.Алгоритм O(n) хорошо известен и уже давно доказал свою корректность (важное свойство в некоторых приложениях).Но для этого требуются изменяемые массивы.

Это не значит, что вы не можете выполнять перетасовку в функциональной программе.Олег Киселёв об этом написано.Но если я правильно его понимаю, функциональная перетасовка — это O(n .log n), потому что он строит двоичное дерево.

Конечно, если бы мне нужно было написать алгоритм Фишера-Йейтса на Haskell, я бы просто поместил его в файл 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:

  1. Обычно для написания кода таким образом требуется больше операторов (или больше строк кода).Краткость имеет ценность.
  2. Это почти всегда менее эффективно.Да, я знаю, что вы говорите о более высоких языках — это справедливый обзор — но даже в мире Java и C#, вдали от ассемблера, скорость имеет значение.Есть несколько приложений, где скорость не имеет значения.
  3. Это не так легко понять.Хотя SSA «проще» в математическом смысле, он более абстрактен от здравого смысла, что важно в реальном программировании.Если вам нужно быть очень умным, чтобы понять это, то ему нет места в программировании в целом.

Даже в приведенных выше примерах легко проделать дыры.Примете ваше case заявление.Что, если существует административная опция, определяющая, будет ли '*' разрешено, и отдельный вопрос о том, разрешено ли '?' позволено?Кроме того, ноль не допускается для целочисленного случая, если у пользователя нет системного разрешения, которое позволяет это.

Это более реальный пример с ветвями и условиями.Не могли бы вы написать это как единственное «Заявление?» Если да, то ваше «утверждение» действительно отличается от многих отдельных утверждений?Если нет, то сколько временных переменных, доступных только для записи, вам нужно?И является ли эта ситуация значительно лучше, чем просто наличие одной переменной?

Я думаю, вы обнаружите, что наиболее продуктивные языки позволяют смешивать функциональные и императивные стили, такие как OCaml и F#.

В большинстве случаев я могу написать код, который представляет собой просто длинную строку «сопоставить x с y, уменьшить y до z».В 95% случаев функциональное программирование упрощает мой код, но есть одна область, где неизменность показывает свои зубы:

Огромное несоответствие между простотой реализации и неизменяемым стеком и неизменяемой очередью.

Стеки просты и хорошо сочетаются с настойчивостью, очереди просто смешны.

Большинство распространенные реализации неизменяемых очередей используйте один или несколько внутренних стеков и ротацию стеков.Плюсом является то, что эти очереди выполняются за O(1). большую часть времени, но некоторые операции будут выполняться за O(n).Если вы полагаетесь на постоянство в своем приложении, то в принципе возможно, что каждая операция выполняется за O(n).Эти очереди бесполезны, когда вам нужна производительность в реальном времени (или, по крайней мере, стабильная).

Крис Окасаки обеспечивает реализацию неизменяемых очередей в его книга, они используют лень для достижения O(1) для всех операций.Это очень умная и достаточно лаконичная реализация очереди реального времени, но она требует глубокого понимания деталей базовой реализации, и она все же на порядок сложнее, чем неизменяемый стек.

Напротив, я могу написать стек и очередь, используя изменяемые связанные списки, которые выполняются за постоянное время для всех операций, и результирующий код будет очень простым.

Что касается площади многоугольника, ее легко преобразовать в функциональную форму.Предположим, у нас есть такой модуль 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

Я не считаю ни одну функцию нечитаемой.

Этот алгоритм перемешивания тривиально реализовать с использованием одиночного присваивания, фактически он точно такой же, как императивное решение с итерацией, переписанной на хвостовую рекурсию.(Эрланг, потому что я могу написать его быстрее, чем Хаскель.)

 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"

Я бы пропустил задания на нечисто функциональном языке.Главным образом потому, что они мешают использовать циклы.Примеры (Скала):

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 переменная.

Эти примеры можно было бы переписать, используя свертывание кортежа, чтобы избежать множественных присваиваний, но это не улучшит читаемость.

Локальные переменные (методы) конечно никогда иметь быть назначен дважды.Но даже в функциональном программировании допускается переназначение переменной.Его изменение (часть) значения, которое не разрешено.И как уже ответил dsimcha, для очень больших структур (возможно, в корне приложения) замена всей структуры мне кажется нецелесообразной.Думаю об этом.Состояние приложения в конечном итоге определяется методом точки входа вашего приложения.Если абсолютно никакое состояние не может измениться без замены, вам придется перезапускать приложение при каждом нажатии клавиши.:(

Если у вас есть функция, которая создает ленивый список/дерево, а затем снова сокращает его, функциональный компилятор может оптимизировать его, используя вырубка леса.

Если это сложно, возможно, нет.Тогда вам не повезло с точки зрения производительности и памяти, если только вы не можете выполнять итерацию и использовать изменяемую переменную.

Благодаря тезису Чёрча-Тьюринга мы знаем, что всё, что можно написать на тьюринг-полном языке, можно написать и на любой Тьюринг-полный язык.Итак, когда вы приступите к делу, вы поймете, что нет ничего такого, чего вы не могли бы сделать в Lisp, чего вы не могли бы сделать в C#, если бы вы достаточно старались, или наоборот.(Более того, в большинстве случаев любой из них в любом случае будет скомпилирован до машинного языка x86.)

Итак, ответ на ваш вопрос:таких случаев нет.Есть случаи, которые людям легче понять в той или иной парадигме/языке, и простота понимания здесь связана с обучением и опытом.

Возможно, основной проблемой здесь является стиль циклов в языке.В языках, где мы используем рекурсию, любые значения, изменяющиеся в ходе цикла, повторно привязываются при повторном вызове функции.Языки, использующие итераторы в блоках (например, Smalltalk и Ruby). inject метод), как правило, аналогичны, хотя многие люди в Ruby по-прежнему используют each и изменяемая переменная над inject.

Когда вы кодируете циклы, используя while и for, с другой стороны, у вас нет простой возможности повторной привязки переменных, которая происходит автоматически, когда вы можете передать несколько параметров в фрагмент кода, выполняющий одну итерацию цикла, поэтому неизменяемые переменные были бы гораздо более неудобными.

Работа в Haskell — действительно хороший способ выяснить необходимость изменяемых переменных, поскольку по умолчанию они неизменяемы, но доступны изменяемые переменные (например, IORefs, MVars, и так далее).Недавно я сам «исследовал» этот путь и пришел к следующим выводам.

  1. В подавляющем большинстве случаев изменяемые переменные не нужны, и я счастлив жить без них.

  2. Для межпоточного взаимодействия изменяемые переменные необходимы по довольно очевидным причинам.(Это специфично для Haskell;системы времени выполнения, которые используют передачу сообщений на самом низком уровне, конечно, в них не нуждаются.) Однако такое использование достаточно редко, поэтому для их чтения и записи приходится использовать функции (readIORef fooRef val и т. д.) не представляет собой большого бремени.

  3. Я использовал изменяемые переменные внутри одного потока, потому что это, казалось, упрощало некоторые вещи, но позже пожалел об этом, поскольку понял, что стало очень трудно рассуждать о том, что происходит со значением, хранящимся там.(Несколько различных функций манипулировали этим значением.) Это было своего рода откровением;в типичном стиле «лягушка в горшке с теплой водой» я не осознавал, насколько легко Haskell облегчил мне рассуждать об использовании значений, пока не наткнулся на пример того, как я их использовал .

Итак, сегодня я довольно твердо встал на сторону неизменяемых переменных.

Поскольку предыдущие ответы на этот вопрос вносили путаницу в эти вещи, я чувствую себя обязанным здесь весьма убедительно указать, что эта проблема ортогональна как чистоте, так и функциональному программированию.Я считаю, что Ruby, например, выиграет от наличия локальных переменных с одним присваиванием, хотя, возможно, для того, чтобы сделать это по-настоящему удобным, потребуются некоторые другие изменения в языке, такие как добавление хвостовой рекурсии.

А как насчет того, когда вам нужно внести небольшие изменения в большие структуры данных?На самом деле вы не хотите копировать целый массив или большой класс каждый раз, когда вам нужно изменить несколько элементов.

Я особо об этом не думал, за исключением того момента, когда вы на это указали.

На самом деле я стараюсь не использовать несколько заданий подсознательно.

Вот пример того, о чем я говорю, на Python 

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

Написано таким образом, чтобы избежать ненужного дополнительного модуля или вычитания.Это используется с длинными целыми числами в стиле bignum, поэтому это достойная оптимизация.Однако дело в том, что на самом деле это одно задание.

Я бы вообще не пропустил несколько заданий.

Я знаю, что вы просили код, демонстрирующий преимущества изменяемых переменных.И мне бы хотелось это предоставить.Но, как отмечалось ранее, не существует проблемы, которую нельзя было бы выразить обоими способами.И особенно после того, как вы отметили, что область примера многоугольника jpalecek можно записать с помощью алгоритма свертывания (что, ИМХО, намного сложнее и переносит проблему на другой уровень сложности) - ну, это заставило меня задаться вопросом, почему вы так отказываетесь от изменчивости жесткий.Итак, я попытаюсь привести аргументы в пользу общей точки зрения и сосуществования неизменяемых и изменяемых данных.

На мой взгляд, этот вопрос немного не соответствует сути.Я знаю, что мы, программисты, склонны любить все чистое и простое, но иногда мы упускаем из виду, что возможно и сочетание.И, вероятно, именно поэтому в дискуссии о неизменности редко кто-то занимает золотую середину.Мне просто интересно, почему, потому что давайте посмотрим правде в глаза - неизменяемость — отличный инструмент абстрагирования всех видов проблем.Но иногда это огромная боль в заднице.Иногда это просто слишком ограничивает.И одно это заставляет меня остановиться и задуматься: действительно ли мы хотим потерять изменчивость?Действительно ли это или-или? Нет ли какой-то точки соприкосновения мы можем прийти?Когда неизменность помогает мне быстрее достичь своих целей, а когда изменчивость? Какое решение легче читать и поддерживать? (для меня это самый большой вопрос)

Многие из этих вопросов зависят от вкуса программиста и от того, на чем он программирует.Поэтому я сосредоточусь на одном из аспектов, который обычно является центром большинства аргументов в пользу неизменяемости — параллелизме:

Часто параллелизм используется в аргументах относительно неизменности.Я работал над наборами задач, для решения которых требовалось более 100 процессоров за разумное время.И это научило меня одной очень важной вещи:В большинстве случаев распараллеливание манипуляций с графиками данных на самом деле не является наиболее эффективным способом распараллеливания.Конечно, это может принести большую пользу, но дисбаланс является настоящей проблемой в этом проблемном пространстве.Поэтому обычно параллельная работа с несколькими изменяемыми графами и обмен информацией с неизменяемыми сообщениями намного эффективнее.Это означает, что когда я знаю, что граф изолирован и что я не раскрыл его внешнему миру, я хотел бы выполнить над ним свои операции самым кратким способом, который только могу придумать.И это обычно включает в себя изменение данных.Но после этих операций с данными я хочу открыть данные для всего мира - и в этот момент я обычно немного нервничаю, если данные изменяемы.Поскольку другие части программы могут повредить данные, состояние становится недействительным...потому что после открытия миру данные часто попадают в мир параллелизма.

Таким образом, в реальных параллельных программах обычно есть области, где графы данных используются в окончательных однопоточных операциях (потому что они просто неизвестны снаружи), и области, где они могут участвовать в многопоточных операциях (надеюсь, просто предоставляя данные, а не манипулируя ими). .Мы никогда не хотим, чтобы во время этих многопоточных частей они менялись — просто лучше работать с устаревшими данными, чем с противоречивыми данными.Что может быть гарантировано понятием неизменности.

Это заставило меня прийти к простому выводу:Настоящая проблема для меня заключается в том, что ни один из языков программирования, с которыми я знаком, не позволяет мне сказать: «После этого момента вся эта структура данных станет неизменной» и «дайте мне изменяемую копию этой неизменяемой структуры данных, пожалуйста, убедитесь, что только я могу видеть изменяемую копию».Прямо сейчас я должен гарантировать это сам, перевернув бит только для чтения или что-то подобное.Если бы мы могли иметь поддержку компилятора, это не только гарантировало бы мне, что я не сделаю ничего глупого после изменения указанного бита, но и могло бы фактически помочь компилятору выполнить различные оптимизации, которые он не мог сделать раньше.Плюс — язык по-прежнему будет привлекателен для программистов, более знакомых с императивной моделью программирования.

Итак, подведем итог.ИМХО в программах обычно есть веская причина использовать как неизменяемые, так и изменяемые представления графов данных..Я бы сказал, что данные должны быть неизменяемый по умолчанию и компилятор должен обеспечить это - но у нас должно быть понятие частных изменяемых представлений, потому что, естественно, есть области, куда многопоточность никогда не достигнет - а читаемость и удобство обслуживания могут выиграть от более императивного структурирования.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top