¿Crees que todavía necesitas variables que puedas cambiar? De ser así, ¿por qué?

https://stackoverflow.com/questions/610956

03-07-2019
|

Pregunta

Uno de los argumentos que he escuchado en contra de los lenguajes funcionales es que la codificación de una sola asignación es demasiado difícil, o al menos significativamente más difícil que "normal". programación.

Pero al revisar mi código, me di cuenta de que realmente no tengo muchos patrones de uso (¿alguno?) que no se puedan escribir del mismo modo si se usa una forma de asignación única si se escribe en un lenguaje razonablemente moderno.

¿Cuáles son los casos de uso para variables que varían dentro de una sola invocación de su alcance? Teniendo en cuenta que los índices de bucle, los parámetros y otros valores de alcance de alcance que varían entre invocaciones no son asignaciones múltiples en este caso (a menos que tenga que cambiarlos en el cuerpo por alguna razón), y suponiendo que está escribiendo en algo lo suficientemente por encima del nivel del lenguaje ensamblador, donde puede escribir cosas como

values.sum

o (en caso de que no se proporcione la suma)

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"

cuando lo necesite, y tenga listas de comprensión, mapeo / recopilación, etc. disponibles.

¿Encuentra que todavía quiere / necesita variables mutables en dicho entorno y, de ser así, para qué?

Para aclarar, no estoy pidiendo una recitación de las objeciones al formulario SSA, sino ejemplos concretos en los que se aplicarían esas objeciones. Estoy buscando fragmentos de código que sean claros y concisos con variables mutables y que no se puedan escribir sin ellos.

Mis ejemplos favoritos hasta ahora (y la mejor objeción que les espero):

algoritmo de Fisher-Yates , que es bastante fuerte cuando se incluyen las restricciones big-O. Pero luego, como señala Catulahoops, el problema de la O grande no está ligado a la pregunta de la SSA, sino más bien a tener tipos de datos mutables, y con eso aparte, el algoritmo se puede escribir bastante claramente en la 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's área de un polígono ejemplo:

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 aún podría estar 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)
               }

O, dado que algunas personas se oponen a la densidad de esta formulación, podría reformularse:

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

El punto de Princess sobre la dificultad de implementar colas O (1) con estructuras inmutables es interesante (y puede proporcionar la base para un ejemplo convincente), pero como se dice, es fundamentalmente sobre la mutabilidad de la estructura de datos, y no directamente sobre el tema de la asignación múltiple.
Estoy intrigado por la respuesta del Tamiz de Eratóstenes, pero no estoy convencido. El Big-O adecuado, extraiga tantos números primos como desee del generador que aparece en el documento que citó, no parece fácil de implementar correctamente con o sin SSA.

Bueno, gracias a todos por intentarlo. Como la mayoría de las respuestas resultaron ser 1) basadas en estructuras de datos mutables, no en una asignación única, y 2) en la medida en que se trataba de una forma de asignación única fácilmente contrarrestada por los expertos en la materia, voy a marque la línea de mi charla y / o reestructuración (tal vez lo tenga como respaldo como tema de discusión en el improbable caso de que me quede sin palabras antes de que se agote el tiempo).

Gracias de nuevo.

Solución

Nunca he identificado un caso así. Y aunque siempre puedes inventar nuevos nombres, como en la conversión a un formulario de SSA, en realidad me parece fácil y natural que cada valor tenga su propio nombre. Un lenguaje como Haskell me da muchas opciones sobre qué valores nombrar, y dos lugares diferentes para poner enlaces de nombre ( let y where ). El formulario de asignación única me parece bastante natural y nada difícil.

A veces extraño poder tener punteros a objetos mutables en el montón. Pero estas cosas no tienen nombre, por lo que no es la misma objeción. (Y también encuentro que cuando uso objetos mutables en el montón, tiendo a escribir más errores).

Otros consejos

El problema más difícil que he encontrado es barajar una lista. El algoritmo Fisher-Yates (también conocido como algoritmo de Knuth) implica iterar a través de la lista intercambiando cada elemento con otro elemento aleatorio. El algoritmo es O (n), bien conocido y probado desde hace mucho tiempo (una propiedad importante en algunas aplicaciones). Pero requiere matrices mutables.

Eso no quiere decir que no se pueda barajar en un programa funcional. Oleg Kiselyov ha escrito sobre esto . Pero si lo entiendo correctamente, la ordenación funcional es O (n. Log n) porque funciona al construir un árbol binario.

Por supuesto, si tuviera que escribir el algoritmo de Fisher-Yates en Haskell, simplemente lo pondría en ST monad , que le permite resumir un algoritmo que incluye arreglos mutables dentro de una función pura agradable, como esta:

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

Si desea hacer el argumento académico, por supuesto, no es técnicamente necesario asignar una variable más de una vez. La prueba es que todo el código se puede representar en el formulario SSA (Asignación Estática Única) . De hecho, esa es la forma más útil para muchos tipos de análisis estático y dinámico.

Al mismo tiempo, hay razones por las que no todos escribimos código en forma SSA para comenzar:

Por lo general, se necesitan más declaraciones (o más líneas de código) para escribir código de esta manera. La brevedad tiene valor.
Es casi siempre menos eficiente. Sí, sé que estás hablando de lenguajes superiores, un alcance justo, pero incluso en el mundo de Java y C #, lejos del ensamblaje, la velocidad es importante. Hay pocas aplicaciones donde la velocidad es irrelevante.
No es tan fácil de entender. Aunque SSA es "más simple" en un sentido matemático, es más abstracto del sentido común, que es lo que importa en la programación del mundo real. Si tienes que ser realmente inteligente para asimilarlo, entonces no tiene lugar en la programación en general.

Incluso en tus ejemplos anteriores, es fácil hacer agujeros. Tome su declaración de case . ¿Qué sucede si hay una opción administrativa que determina si '*' está permitido, y una opción separada para saber si '?' está permitido? Además, cero no está permitido para el caso entero, a menos que el usuario tenga un permiso del sistema que lo permita.

Este es un ejemplo más real con ramas y condiciones. ¿Podría escribir esto como una única "declaración"? Si es así, ¿es su " declaración " realmente diferente de muchas declaraciones separadas? Si no, ¿cuántas variables temporales de solo escritura necesita? ¿Y esa situación es significativamente mejor que tener una sola variable?

Creo que encontrará los lenguajes más productivos que le permiten mezclar estilos funcionales e imperativos, como OCaml y F #.

En la mayoría de los casos, puedo escribir código que es simplemente una línea larga de '' mapa xay, y reducir y a z ''. En el 95% de los casos, la programación funcional simplifica mi código, pero hay un área donde la inmutabilidad muestra sus dientes:

La gran disparidad entre la facilidad de implementación y la pila inmutable y una cola inmutable.

Las pilas son fáciles y se combinan bien con persistencia, las colas son ridículas.

Lo más implementaciones comunes de colas inmutables usan una o más pilas internas y rotaciones de pila. Lo bueno es que estas colas se ejecutan en O (1) la mayor parte del tiempo , pero algunas operaciones se ejecutarán en O (n). Si confía en la persistencia de su aplicación, es posible, en principio, que todas las operaciones se ejecuten en O (n). Estas colas no son buenas cuando necesita un rendimiento en tiempo real (o al menos consistente).

Chris Okasaki proporciona una implementación de colas inmutables en su libro , utilizan la pereza para lograr O (1) para todas las operaciones. Es una implementación muy inteligente y razonablemente concisa de una cola en tiempo real, pero requiere una comprensión profunda de los detalles de la implementación subyacente, y aún es un orden de magnitud más complejo que una pila inmutable.

En contraste, puedo escribir una pila y una cola usando listas enlazadas mutables que se ejecutan en tiempo constante para todas las operaciones, y el código resultante sería muy sencillo.

Con respecto al área de un polígono, es fácil convertirlo a una forma funcional. Supongamos que tenemos un módulo de vectores como este:

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 nuestra función de área usando un poco de magia de 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

O podemos usar el producto cruzado

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

No encuentro ninguna función ilegible.

Ese algoritmo aleatorio es trivial de implementar usando una sola asignación, de hecho, es exactamente lo mismo que la solución imperativa con la iteración reescrita para la recursión de cola. (Erlang porque puedo escribirlo más rápido 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).

Si la eficiencia de esas operaciones de matriz es una preocupación, entonces esa es una pregunta sobre estructuras de datos mutables y no tiene nada que ver con una asignación única.

No obtendrá una respuesta a esta pregunta porque no existen ejemplos. Es solo una cuestión de familiaridad con este estilo.

En respuesta 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"

Me faltarían las tareas en un lenguaje no puramente funcional. Sobre todo porque dificultan la utilidad de los bucles. Ejemplos (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
}

Esto debería calcular el cuantil de una lista, tenga en cuenta el acumulador tmp que se asigna varias veces.

Un ejemplo similar sería:

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
}

Tenga en cuenta principalmente la variable último .

Estos ejemplos podrían reescribirse utilizando fold en una tupla para evitar múltiples tareas, pero eso no ayudaría a la legibilidad.

Las variables locales (método) ciertamente nunca tienen para ser asignadas dos veces. Pero incluso en la programación funcional se permite reasignar una variable. Es cambiar (parte de) el valor que no está permitido. Y como dsimcha ya respondió, para estructuras muy grandes (quizás en la raíz de una aplicación) no me parece factible reemplazar toda la estructura. Piénsalo. El estado de una aplicación está todo contenido en última instancia por el método de punto de entrada de su aplicación. Si absolutamente ningún estado puede cambiar sin ser reemplazado, tendría que reiniciar su aplicación con cada pulsación de tecla. :(

Si tiene una función que construye una lista / árbol perezoso y luego la reduce nuevamente, un compilador funcional puede optimizarla usando deforestation .

Si es complicado, puede que no. Entonces estás fuera de suerte, rendimiento y rendimiento. memoria inteligente, a menos que pueda iterar y usar una variable mutable.

Gracias a la Tesis de Turing de la Iglesia, sabemos que todo lo que se puede escribir en un lenguaje completo de Turing se puede escribir en cualquier lenguaje completo de Turing. Entonces, cuando llegas a eso, no hay nada que no puedas hacer en Lisp que no puedas hacer en C #, si lo intentaste lo suficiente, o viceversa. (Más concretamente, cualquiera de los dos se compilará en lenguaje de máquina x86 en la mayoría de los casos de todos modos).

Entonces, la respuesta a su pregunta es: no existen tales casos. Todos los casos son más fáciles de comprender para los humanos en un paradigma / lenguaje u otro, y la facilidad de comprensión aquí está vinculada a la capacitación y la experiencia.

Quizás el problema principal aquí es el estilo de bucle en un idioma. En los idiomas en los que usamos recursividad, cualquier valor que cambie en el transcurso de un ciclo se vuelve a vincular cuando se llama nuevamente a la función. Los lenguajes que usan iteradores en bloques (por ejemplo, el método inyectar de Smalltalk y Ruby) tienden a ser similares, aunque muchas personas en Ruby todavía usarían cada y una variable mutable sobre inyectar .

Cuando codificas los bucles usando mientras y para , por otro lado, no tienes la posibilidad de volver a vincular las variables que vienen automáticamente cuando puedes pasar en varios parámetros a su porción de código que realiza una iteración del bucle, por lo que las variables inmutables serían bastante más inconvenientes.

Trabajar en Haskell es una muy buena manera de investigar la necesidad de las variables mutables, ya que el valor predeterminado es inmutable, pero están disponibles las mutables (como IORefs , MVars y pronto). Recientemente he estado, " " investigando " De esta manera, yo mismo, y he llegado a las siguientes conclusiones.

En la gran mayoría de los casos, las variables mutables no son necesarias, y estoy feliz de vivir sin ellas.
Para la comunicación entre subprocesos, las variables mutables son esenciales, por razones bastante obvias. (Esto es específico de Haskell; los sistemas de tiempo de ejecución que usan el paso de mensajes al nivel más bajo no los necesitan, por supuesto). Sin embargo, este uso es tan raro que tener que usar funciones para leerlos y escribirlos ( readIORef fooRef val etc.) no es una gran carga.
He usado variables mutables en un solo hilo, porque parecía facilitar ciertas cosas, pero luego lo lamenté cuando me di cuenta de que era muy difícil razonar sobre lo que estaba sucediendo con el valor almacenado allí. (Varias funciones diferentes estaban manipulando ese valor). Esto fue un poco revelador; En el estilo típico de rana en la olla de agua caliente, no me había dado cuenta de lo fácil que Haskell me había permitido razonar sobre el uso de valores hasta que encontré un ejemplo de cómo solía usarlos. .

Así que en estos días he llegado con bastante firmeza al lado de las variables inmutables.

Dado que las respuestas anteriores a esta pregunta han confundido estas cosas, me siento obligado a señalar aquí con bastante fuerza que este problema es ortogonal tanto para la pureza como para la programación funcional. Creo que Ruby, por ejemplo, se beneficiaría de tener variables locales de asignación única, aunque posiblemente sean necesarios algunos otros cambios en el lenguaje, como agregar la recursión de la cola, para que esto sea realmente conveniente.

¿Qué pasa cuando necesita hacer pequeños cambios en grandes estructuras de datos? Realmente no desea copiar una matriz completa o una clase grande cada vez que modifique algunos elementos.

Realmente no he pensado mucho en esto, excepto ahora que lo estás señalando.

En realidad trato de no usar múltiples tareas inconscientemente.

Aquí hay un ejemplo de lo que estoy hablando, en python

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

Escrito de esta manera para evitar un Módulo adicional o resta innecesario. Esto se usa con entradas largas de estilo bignum, por lo que es una optimización que vale la pena. Sin embargo, la cuestión es que realmente es una tarea única.

No me perdería ninguna tarea múltiple.

Sé que solicitó un código que mostrara los beneficios de las variables mutables. Y desearía poder proporcionarlo. Pero como se señaló anteriormente, no hay problema que no pueda ser expresado en ambas modas. Y especialmente porque usted señaló que el área de jpalecek de un ejemplo de polígono podría escribirse con un algo plegable (que en mi humilde opinión es mucho más desordenado y lleva el problema a diferentes niveles de complejidad), bueno, me hizo preguntarme por qué se está reduciendo la mutabilidad. difícil. Así que trataré de hacer un argumento para un terreno común y una coexistencia de datos inmutables y mutables.

En mi opinión, esta pregunta pierde un poco el punto. Sé que los programadores somos propensos a que nos gusten las cosas limpias y simples, pero a veces echamos de menos que una mezcla también es posible. Y es probable que esa sea la razón por la que en la discusión sobre la inmutabilidad es raro que alguien ocupe un lugar intermedio. Me pregunto por qué, porque seamos sinceros: la inmutabilidad es una gran herramienta para abstraer todo tipo de problemas. Pero a veces es un gran dolor en el culo . A veces simplemente es demasiado restrictivo. Y eso solo me hace parar y eso: ¿realmente queremos perder la mutabilidad? ¿Es realmente una o la otra? ¿No hay un terreno común al que podamos llegar? ¿Cuándo la inmutabilidad me ayuda a alcanzar mis metas más rápido, cuándo la mutabilidad? ¿Qué solución es más fácil de leer y mantener? (lo que para mí es la pregunta más importante)

Muchas de estas preguntas están influenciadas por el gusto de un programador y por lo que están acostumbrados a programar. Así que me enfocaré en uno de los aspectos que generalmente es el centro de la mayoría de los argumentos pro-inmutabilidad: Paralelismo:

A menudo se arroja paralelismo al argumento que rodea la inmutabilidad. He trabajado en conjuntos de problemas que requieren más de 100 CPU para resolver en un tiempo razonable. Y me ha enseñado una cosa muy importante: la mayoría de las veces, la paralelización de la manipulación de gráficos de datos no es realmente el tipo de cosa que será la forma más eficiente de paralelizar. Seguro que puede beneficiarse enormemente, pero el desequilibrio es un problema real en ese espacio problemático. Así que, por lo general, trabajar en múltiples gráficos mutables en paralelo e intercambiar información con mensajes inmutables es mucho más eficiente. Lo que significa que, cuando sé que el gráfico está aislado, que no lo he revelado al mundo exterior, me gustaría realizar mis operaciones en él de la manera más concisa que pueda imaginar. Y eso generalmente implica mutar los datos. Pero después de esta operación en los datos, quiero abrir los datos a todo el mundo, y ese es el punto en el que generalmente me pongo un poco nervioso, si los datos son mutables. Debido a que otras partes del programa podrían corromper los datos, el estado se vuelve inválido, ... porque después de abrirse al mundo, los datos a menudo entran en el mundo del paralelismo.

Entonces, los programas paralelos del mundo real generalmente tienen áreas donde los gráficos de datos se usan en operaciones definitivas de un solo hilo, porque simplemente no son conocidos por el exterior, y áreas en las que podrían estar involucrados en operaciones de subprocesos múltiples (con suerte solo suministrando datos no siendo manipulado). Durante esas partes de subprocesos múltiples, nunca queremos que cambien, simplemente es mejor trabajar con datos desactualizados que con datos inconsistentes. Lo que puede garantizarse por la noción de inmutabilidad.

Eso me hizo llegar a una conclusión simple: el verdadero problema para mí es que ninguno de los lenguajes de programación con los que estoy familiarizado me permite decir: " Después de este punto, toda esta estructura de datos será inmutable " y " dame una copia mutable de esta estructura de datos inmutables aquí, verifica que solo yo pueda ver la copia mutable " . En este momento tengo que garantizarlo yo mismo cambiando un poco de lectura o algo similar. Si pudiéramos tener soporte para el compilador, no solo me garantizaría que no hice nada estúpido después de voltear dicho bit, sino que podría ayudar al compilador a hacer varias optimizaciones que antes no podía hacer. Además, el lenguaje aún sería atractivo para los programadores que están más familiarizados con el imperativo modelo de programación.

Entonces, para resumir. Los programas IMHO usualmente tienen una buena razón para usar representaciones inmutables y mutables de gráficos de datos . Yo diría que los datos deberían ser inmutables por defecto y el compilador debería hacer cumplir eso, pero deberíamos tener la noción de representaciones mutables privadas , porque naturalmente hay áreas donde los hilos nunca alcanzarán, y la legibilidad y la capacidad de mantenimiento podrían beneficiarse de una estructuración más imperativa.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow