Você acha que você ainda precisa de variáveis ??que podem ser alteradas, e se assim por quê?

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

Pergunta

Um dos argumentos que tenho ouvido contra linguagens funcionais é que única atribuição de codificação é muito difícil, ou pelo menos significativamente mais difícil do que a programação "normal".

Mas olhando através de meu código, eu percebi que eu realmente não tem muitos padrões de uso (qualquer?) Que não podem ser escritos tão bem, utilizando o formulário de atribuição única Se você estiver escrevendo em uma linguagem razoavelmente moderno.

Então, quais são os casos de uso de variáveis ??que variam dentro de uma única invocação de seu alcance? Tendo em mente que índices de loop, parâmetros e outros valores de escopo obrigado que variam entre invocações não são várias atribuições neste caso (a menos que você Have a mudá-los no corpo por alguma razão), e assumindo que você está escrevendo em algo um longe o suficiente acima do nível de linguagem de montagem, onde você pode escrever coisas como 

values.sum

ou (em suma caso não é fornecido) 

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

e 

x = if a > b then a else b

ou 

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

quando você precisa, e têm compreensões lista, mapa / coleta, e assim por diante disponíveis.

Você acha que você ainda quiser / precisar variáveis ??mutáveis ??em um ambiente como esse, e se assim for, para quê?

Para esclarecer, eu não estou pedindo uma recitação das objeções à forma SSA, mas exemplos em vez de concreto onde essas objeções seria aplicável. Estou à procura de pedaços de código que são clara e concisa com variáveis ??mutáveis ??e não podia ser escritos até sem eles.

Os meus exemplos favoritos até agora (e o melhor objeção espero a eles):

  1. de Paul Johnson Fisher-Yates algoritmo resposta, que é muito forte quando você incluir as restrições big-o. Mas então, como catulahoops pontos fora, a questão big-O não está vinculado à questão SSA, mas sim para ter tipos de dados mutáveis, e com isso anular o algoritmo pode ser escrito em vez claramente em 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. O jpalecek área de exemplo, um polígono : 

    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
}

    que ainda pode ser escrito algo como: 

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

    Ou, já que algumas pessoas se opõem à densidade desta formulação, poderia ser reformulada: 

    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. ponto da princesa sobre a dificuldade de implementação O (1) filas com estruturas imutáveis ??é interessante (e pode muito bem servir de base para um exemplo convincente), mas como dito, é fundamentalmente sobre a mutabilidade da estrutura de dados, e não diretamente sobre o assunto atribuição múltipla.

  4. Estou intrigado com a resposta Crivo de Eratóstenes, mas não convencido. O bom big-O, puxar tantos primos como você gostaria gerador dada no jornal citou não parece fácil de implementar corretamente com ou sem SSA.

Bem, obrigado a todos por tentar. Como a maioria das respostas acabou por ser 1) com base em estruturas de dados mutáveis, e não em uma única tarefa, e 2), na medida em que eles estavam prestes forma única atribuição facilmente combatida por profissionais qualificados na arte, eu vou golpear a linha de minha palestra e / ou reestruturar (talvez tê-lo em backup como um tópico de discussão no caso improvável de eu ficar sem palavras antes de executar fora de tempo).

Obrigado novamente.

Foi útil?

Solução

Eu nunca identificadas caso a. E enquanto você pode sempre inventar novos nomes, como em conversão para a forma SSA, eu realmente acho que é fácil e natural para cada valor para ter o seu próprio nome. A linguagem como Haskell me dá um monte de opções sobre quais valores para nome e dois lugares diferentes para colocar ligações de nome (let e where). I encontrar o formulário-atribuição única bastante natural e não de todo difícil.

eu ocasionalmente perca ser capaz de ter ponteiros para objetos mutáveis ??no heap. Mas essas coisas não têm nomes, por isso não é a mesma objeção. (E eu também acho que quando eu usar objetos mutáveis ??na pilha, que tendem a escrever mais bugs!)

Outras dicas

O problema mais difícil que eu me deparei é baralhar uma lista. A Fisher-Yates algoritmo (às vezes também conhecido como o algoritmo Knuth) envolve iteração através da lista trocando cada item com um outro item aleatória. O algoritmo é O (n), bem conhecido e de longa desde provada correta (uma propriedade importante em algumas aplicações). Mas isso requer matrizes mutáveis.

Isso não quer dizer que você não pode fazer baralhar em um programa funcional. Oleg Kiselyov tem escrito sobre este . Mas se eu o compreendo corretamente, baralhar funcional é O (n. Log n) porque funciona através da construção de uma árvore binária.

Claro que, se eu precisava para fazer o algoritmo Fisher-Yates em Haskell Eu tinha acabado de colocá-lo no ST mônada , que permite encerrar um algoritmo envolvendo matrizes mutáveis ?? dentro de uma função pura agradável, como este: 

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

v

Se você quiser fazer o argumento acadêmico, então é claro que não é tecnicamente necessário atribuir uma variável mais de uma vez. A prova é que todo o código pode ser representado em SSA (Cessão Individual Estático) formar. Na verdade, essa é a forma mais útil para muitos tipos de estática e análise dinâmica.

Ao mesmo tempo, existem razões que não todo o código de escrita em forma SSA para começar com:

  1. Geralmente, leva mais declarações (ou mais linhas de código) para escrever código desta forma. Brevidade tem valor.
  2. É quase sempre menos eficiente. Sim, eu sei que você está falando línguas mais altos - um escopo justo - mas mesmo no mundo de Java e C #, longe de montagem, a velocidade é importante. Há poucas aplicações onde a velocidade é irrelevante.
  3. Não é tão fácil de entender. Embora SSA é "simples" em um sentido matemático, é mais abstrato do senso comum, que é o que importa na programação do mundo real. Se você tem que ser muito inteligente para grok ele, então ele não tem lugar na programação em geral.

Mesmo em seus exemplos acima, é fácil criar buracos. Leve a sua declaração case. E se há uma opção administrativa que determina se '*' é permitido, e um separado para se '?' é permitido? Além disso, o zero não é permitida para o caso inteiro, a menos que o usuário tem uma permissão de sistema que permite isso.

Este é um exemplo mais do mundo real com ramos e condições. você poderia escrever isso como uma única "declaração?" Se assim for, é a sua "declaração" muito diferente de muitas declarações separadas? Se não, quantas variáveis ??temporárias só de escrita que você precisa? E é nessa situação significativamente melhor do que apenas ter uma única variável?

Eu acho que você vai encontrar a maioria das línguas produtivas permitem misturar estilos funcionais e imperativas, como OCaml e F #.

Na maioria dos casos, eu posso escrever o código que é simplesmente uma longa linha de "mapa de x para y, reduzir y para z". Em 95% dos casos, a programação funcional simplifica o meu código, mas há uma área onde imutabilidade mostra seus dentes:

A grande disparidade entre a facilidade de implementação e pilha imutável e uma fila imutável.

As pilhas são fáceis e combinam bem com persistência, as filas são ridículo.

O mais implementações comuns de filas imutáveis ?? um uso ou pilhas mais internos e rotações de pilha. A vantagem é que essas filas executado em O (1) a maior parte do tempo , mas algumas operações será executado em O (n). Se você está contando com persistência em seu aplicativo, em seguida, é possível, em princípio, que a cada operação é executado em O (n). Essas filas não são bons quando você precisa realtime (ou pelo menos consistente) desempenho.

Chris Okasaki do fornece uma implementação de filas imutáveis ??em seu livro , eles usam preguiça para conseguir o (1) para todas as operações. É um muito inteligente, implementação razoavelmente concisa de uma fila em tempo real - mas requer profundo conhecimento de seus detalhes de implementação subjacentes, e seu ainda uma ordem de magnitude mais complexos do que uma pilha imutável

.

Em constrast, eu posso escrever uma pilha e fila usando listas ligadas mutáveis ??que funcionam em tempo constante para todas as operações, eo código resultante seria muito simples.

Em relação à área de um polígono, é fácil convertê-lo em forma funcional. Vamos supor que temos um módulo Vector assim: 

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 }

Podemos definir nossa função área usando um pouco de magia tupla: 

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

Ou podemos usar o produto cruzado em vez 

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

Eu não encontrar qualquer função ilegível.

Esse algoritmo shuffle é trivial de implementar usando atribuição única, na verdade, é exatamente o mesmo que a solução imperativo com a iteração reescrito para recursão de cauda. (Erlang, porque eu posso escrevê-lo mais rapidamente do que 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).

Se a eficiência dessas operações de matriz é uma preocupação, então isso é uma pergunta sobre estruturas de dados mutáveis ??e não tem nada a ver com a única atribuição.

Você não receberá uma resposta a esta pergunta, porque não existem exemplos. É apenas uma questão de familiaridade com este modelo.

Em resposta a Jason - 

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"

eu iria perder atribuições em uma linguagem não-puramente funcional. Principalmente porque impedem a utilidade de loops. Exemplos (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
}

Isso deve calcular o quantil de uma lista, observe o tmp acumulador que é atribuído a várias vezes.

Um exemplo semelhante seria: 

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
}

Nota principalmente a variável last.

Esses exemplos poderiam ser reescrito usando dobra em uma tupla para evitar várias atribuições, mas que realmente não ajudaria a legibilidade.

(método) As variáveis ??locais certamente nunca Have a ser atribuído a duas vezes. Mas, mesmo na programação funcional re-atribuição de uma variável é permitido. É mudar (parte de) o valor que não é permitido. E como dsimcha já respondeu, por estruturas muito grandes (talvez na raiz de um aplicativo) não parece viável para mim para substituir toda a estrutura. Pense nisso. O estado de um aplicativo é tudo contido em última análise, pelo método de ponto de entrada de sua aplicação. Se for absolutamente nenhum estado pode mudar sem ser substituído, você teria que reiniciar o aplicativo com cada tecla pressionada. : (

Se você tem uma função que constrói um preguiçoso lista / árvore, em seguida, reduz-lo novamente, um compilador funcional pode ser capaz de otimizá-lo usando desmatamento .

Se é complicado, talvez não. Então você é tipo de fora da sorte, desempenho e memória sábio, a menos que você pode interagir e usar uma variável mutável.

Graças à tese de Church-Turing, sabemos que qualquer coisa que pode ser escrito em uma linguagem Turing-completa pode ser escrito em qualquer linguagem Turing-completo. Então, quando você começa para baixo direito a ela, não há nada que você não pode fazer em Lisp que você não poderia fazer em C #, se você tentou com força suficiente, ou vice-versa. (Mais ao ponto, qualquer um vai ficar compilados para baixo para linguagem de máquina x86 na maioria dos casos de qualquer maneira.)

Assim, a resposta à sua pergunta é: não existem tais casos. Todos existem são casos que são mais fáceis para os seres humanos para compreender em um paradigma / idioma ou another-- ea facilidade de compreensão aqui está ligada à formação e experiência.

Talvez a questão principal aqui é o estilo de looping em um idioma. Em langauges onde usamos recursão, todos os valores em mudança ao longo de um circuito são quando a função é chamada de novo ligados a re. Idiomas usando iteradores em blocos (por exemplo, o método inject de Ruby do Smalltalk e) tendem a ser semelhantes, embora muitas pessoas em Ruby ainda usaria each e uma variável mutável ao longo inject.

Quando você loops de código usando while e for, por outro lado, você não tem a fácil re-ligação de variáveis ??que vem automaticamente quando você pode passar em vários parâmetros para o seu pedaço de código que faz uma iteração do loop, portanto as variáveis ??imutáveis ??seria um pouco mais inconveniente.

Trabalho em Haskell é uma boa maneira de investigar a necessidade de variáveis ??mutáveis, já que o padrão é imutável, mas os mutáveis ??estão disponíveis (como IORefs, MVars, e assim por diante). Eu estive recentemente, er, "investigar", desta forma eu mesmo, e chegaram às seguintes conclusões.

  1. Na grande maioria dos casos, as variáveis ??mutáveis ??não são necessárias, e eu sou uma vida feliz sem eles.

  2. Para a comunicação inter-thread, variáveis ??mutáveis ??são essenciais, por razões bastante óbvias. (Isto é específico para Haskell, sistemas de tempo de execução que o uso de passagem de mensagens no nível mais baixo não precisa deles, é claro.) No entanto, esse uso é bastante raro que ter que usar funções para ler e escrever-los (readIORef fooRef val etc.) é não muito de um fardo.

  3. Eu tenho usado variáveis ??mutáveis ??dentro de um único segmento, porque parecia a fazer certas coisas mais fáceis, mas mais tarde se arrependeu quando percebi que tornou-se muito difícil de raciocinar sobre o que estava acontecendo com o valor armazenado lá. (Várias funções diferentes foram manipular esse valor.) Este foi um pouco de um revelador; em típico sapo-in-the-pot-de-aquecer a água estilo, eu não tinha percebido o quão fácil Haskell tinha feito isso por mim para raciocinar sobre o uso de valores até que eu corri em um exemplo de como eu costumava usá-los .

Então, esses dias eu vim para baixo bastante firmemente ao lado de variáveis ??imutáveis.

Uma vez que as respostas anteriores a esta pergunta ter confundido essas coisas, sinto-me compelido a apontar aqui muito energicamente que esta questão é ortogonal a ambos pureza e programação funcional. Eu sinto que Ruby, por exemplo, iria beneficiar de ter-atribuição única variáveis ??locais, embora, possivelmente, algumas outras alterações na linguagem, como a adição de cauda recursão, seria necessário fazer isso realmente conveniente.

O que dizer quando você precisa fazer pequenas mudanças em estruturas de dados grandes? Você realmente não quer copiar uma matriz todo ou grande classe cada vez que você iria alterar alguns elementos.

Eu realmente não tenho pensado sobre isso muito, exceto agora que você está apontando-o para fora.

Na verdade eu não tente usar várias atribuições inconscientemente.

Aqui está um exemplo do que estou falando, em python 

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

Escrito desta forma para evitar um Modulo adicional unneccesary ou subtração. Isto é usado com estilo bignum longos inteiros, por isso é uma otimização de valor. Coisa sobre isso, porém, é que ele realmente é uma única tarefa.

Eu não perderia atribuição múltipla em tudo.

Eu sei que você pediu para o código que fez mostrar os benefícios de variáveis ??mutáveis. E eu gostaria de poder fornecê-la. Mas, como apontado antes - não há nenhum problema que não pode ser expresso em ambas as modas. E especialmente desde que você apontou que a área de jpalecek de um exemplo polígono poderia ser escrito com uma dobradura algo (que é IMHO maneira mais confusa e leva o problema a diferente nível de complexidade) - bem, fez-me pergunto por que você está descendo sobre mutabilidade assim Difícil. Então eu vou tentar fazer o argumento para um terreno comum e de uma coexistência de dados imutáveis ??e mutáveis.

Na minha opinião esta questão perde o ponto um pouco. Eu sei que nós programadores são propensos a gostar de coisas limpo e simples, mas às vezes sinto falta que uma mistura também é possível. E isso é provavelmente por isso que na discussão sobre a imutabilidade raramente há alguém tomando o meio termo. Eu só quero saber porquê, porque vamos enfrentá-lo - imutabilidade é uma grande ferramenta de abstrair todos os tipos de problemas. Mas às vezes é um enorme dor na bunda . Às vezes, ele simplesmente é demasiado restritiva. E que só me faz parar e coisa - será que realmente quer mutabilidade solta? É, realmente, ou um ou outro? Não existe um terreno comum podemos chegar a? Quando é que a imutabilidade me ajudar a alcançar meus objetivos mais rapidamente, quando faz mutabilidade? Qual a solução mais fácil de ler e manter? (que para mim é a maior questão)

Muitas dessas questões são influenciados pelo gosto de um programador e por que eles são usados ??para programa no Então eu vou focar um dos aspectos que normalmente é o centro da maioria dos argumentos pró-imutabilidade - Paralelismo:.

Muitas vezes paralelismo é lançada no argumento circundante imutabilidade. Eu trabalhei em conjuntos de problemas que exigiam 100+ CPUs para resolver em um tempo razoável. E ele me ensinou uma coisa muito importante: Na maioria das vezes paralelização a manipulação de gráficos de dados não é realmente o tipo de coisa que vai ser a forma mais eficiente para paralelizar. Com certeza pode se beneficiar muito, mas desequilíbrio é um problema real em que problema do espaço. Por isso, normalmente trabalhando em vários gráficos mutáveis ??em paralelo e troca de informações com mensagens imutáveis ??é a maneira mais eficiente. O que significa, quando eu sei que o gráfico é isolado, que eu não tenha revelado para o mundo exterior, eu gostaria de realizar minhas operações sobre ele da maneira mais concisa que eu posso pensar. E que geralmente envolve mutação os dados. Mas depois destes operação nos dados Eu quero abrir os dados para o mundo inteiro - e esse é o ponto onde eu costumo ficar um pouco nervoso, se os dados é mutável. Porque outras partes do programa pode corromper os dados, o estado torna-se inválido, ... porque depois de abrir-se ao mundo dos dados, muitas vezes não entrar no mundo de paralelismo.

Assim, programas paralelos mundo real costumam ter áreas onde gráficos de dados são usados ??em operações com um único fio definitivas - porque eles simplesmente não são conhecidos para o exterior - e áreas onde poderiam ser envolvidos em operações multi-threaded (espero apenas fornecer dados não sendo manipulado). Durante as partes multi-threaded que nunca os quer mudar - ele simplesmente é melhor para trabalhar em dados desatualizados do que em dados inconsistentes. Que pode ser garantida pela noção de imutabilidade.

Isso me fez chegar a uma conclusão simples: O verdadeiro problema para mim é que não das linguagens de programação estou familiarizado com permitam-me dizer: "Após este ponto esta estrutura de dados inteira shal ser imutável" e "me dar uma cópia mutável desta estrutura de dados imutáveis ??aqui, por favor verificar que só eu posso ver a cópia mutável" . Agora eu tenho que garantir que me lançando um pouco de somente leitura ou algo similar. Se pudéssemos ter suporte de compilador para ele, não só garantiria para mim que eu não fiz nada stupid após lançando disse pouco, mas poderia realmente ajudar o compilador fazer várias otimizações que não podia fazer antes. Plus -. A linguagem ainda seria atraente para os programadores que estão mais familiarizados com o modelo de programação imperativo

Assim, para resumir. IMHO programas geralmente têm uma boa razão para usar as duas representações imutáveis ??e mutáveis ??de gráficos de dados . Eu diria que os dados devem ser imutável por padrão e o compilador deve impor que - mas devemos ter o noção de representações mutáveis ??privadas , porque há, naturalmente, são áreas onde multi- rosqueamento nunca vai chegar -. e legibilidade e facilidade de manutenção poderia se beneficiar de uma estruturação mais imperativo

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top