haskell variables functional-programming ssa modern-languages

haskell - ¿Todavía cree que necesita variables que pueda cambiar y, de ser así, por qué?



functional-programming ssa (14)

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

Pero mirando a través de mi código, me di cuenta de que realmente no tengo muchos (¿alguno?) Patrones de uso que no se puedan escribir de la misma manera con un solo formulario de asignación si estás escribiendo en un lenguaje razonablemente moderno.

Entonces, ¿cuáles son los casos de uso para las 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 límite 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 de lenguaje ensamblador, donde puedes 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 )

y

x = if a > b then a else b

o

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, mapa / recopilar, etc. disponibles.

¿Encuentra que todavía desea / necesita variables mutables en dicho entorno, y si es así, para qué?

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

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

  1. La respuesta del algoritmo de Fisher-Yates de Paul Johnson, que es bastante fuerte cuando se incluyen las restricciones del gran O. Pero luego, como señala catulahoops, el problema de la gran O no está ligado a la pregunta de SSA, sino más bien a tener tipos de datos mutables, y con eso puesto a un lado, el algoritmo puede escribirse bastante claramente en 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. área de jpalecek de un ejemplo de 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 aún podría escribirse algo así 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, como algunas personas se oponen a la densidad de esta formulación, podría ser refundida:

    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. El punto de la princesa sobre la dificultad de implementar colas de O (1) con estructuras inmutables es interesante (y puede ser la base para un ejemplo convincente) pero como se dijo es fundamentalmente sobre la mutabilidad de la estructura de datos, y no directamente sobre el tema de asignación múltiple .

  4. Estoy intrigado por la respuesta de Sieve of Eratóstenes, pero no estoy convencido. El Big-O adecuado, extraer tantos primos como desee del generador que se proporciona 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 sola asignación, y 2) en la medida en que se trataban de una sola tarea fácilmente contrarrestada por profesionales expertos en la materia, voy a golpear la línea de mi charla y / o reestructurar (tal vez tenerlo en copia de seguridad como tema de debate en el improbable caso de que me queden sin palabras antes de que se me acabe el tiempo).

Gracias de nuevo.

¿Qué ocurre cuando necesita realizar pequeños cambios en estructuras de datos de gran tamaño? Realmente no desea copiar una matriz completa o una clase grande cada vez que modificaría algunos elementos.

Creo que encontrará que los lenguajes más productivos 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 larga línea de "mapa x a 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 combinan bien con la persistencia, las colas son ridículas.

Las implementaciones más 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, entonces es posible, en principio, que cada operación se ejecute en O (n). Estas colas no son buenas cuando necesitas un rendimiento en tiempo real (o al menos consistente).

Chris Okasaki proporciona una implementación de colas inmutables en su libro , usan 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 su implementación subyacente, y sigue siendo 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.

En cuanto al área de un polígono, es fácil convertirlo a una forma funcional. Supongamos que tenemos un módulo vectorial 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 en su lugar

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.

El problema más difícil que he encontrado es barajar una lista. El algoritmo de Fisher-Yates (también conocido como el algoritmo de Knuth) implica iterar a través de la lista al intercambiar cada elemento con otro elemento al azar. El algoritmo es O (n), bien conocido y probado desde hace mucho tiempo como correcto (una propiedad importante en algunas aplicaciones). Pero requiere arreglos 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, el barajado funcional es O (n. Log n) porque funciona construyendo un árbol binario.

Por supuesto, si tuviera que escribir el algoritmo de Fisher-Yates en Haskell, lo pondría en la mónada ST , lo que le permite resumir un algoritmo que involucra matrices mutables dentro de una función pura y 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

v

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"

Ese algoritmo aleatorio es trivial de implementar con asignación única, de hecho es exactamente lo mismo que la solución imperativa con la iteración reescrita para la recursión final. (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 acerca de las estructuras de datos mutables y no tiene nada que ver con la asignación única.

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

Extrañaría las tareas en un lenguaje no puramente funcional. Principalmente 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 debe calcular el cuantil de una lista, tenga en cuenta el acumulador tmp que se asigna a 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 }

Note principalmente la last variable.

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

Gracias a la Tesis de Church-Turing, sabemos que todo lo que se puede escribir en un lenguaje completo de Turing se puede escribir en cualquier idioma de Turing completo. Por lo tanto, cuando llegue a eso, no hay nada que no pueda hacer en Lisp que no pueda hacer en C #, si lo intentó lo suficiente, o viceversa. (Más al punto, cualquiera de los dos se compilará en lenguaje de máquina x86 en la mayoría de los casos).

Entonces, la respuesta a su pregunta es: no hay 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á ligada al entrenamiento y la experiencia.

Las variables locales (método) ciertamente nunca tienen que asignarse dos veces. Pero incluso en la programación funcional, se permite reasignar una variable. Está cambiando (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 posible reemplazar toda la estructura. Piénsalo. El estado de una aplicación está 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á que reiniciar su aplicación con cada pulsación de tecla. :(

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

En realidad, trato de no usar múltiples asignaciones subconscientemente.

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 o sustra extra innecesario. Esto se usa con entradas largas estilo bignum, por lo que es una optimización que vale la pena. Lo que pasa, sin embargo, es que realmente es una tarea única.

No me perdería ninguna asignación múltiple en absoluto.

Nunca identifiqué tal caso. Y aunque siempre puedes inventar nuevos nombres, como en la conversión al formulario de SSA, en realidad creo que es 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 ). Encuentro que la forma de asignación única es bastante natural y nada difícil.

De vez en cuando echo de menos poder tener punteros a objetos mutables en el montón. Pero estas cosas no tienen nombres, así que no es la misma objeción. (¡Y también me parece que cuando uso objetos mutables en el montón, tiendo a escribir más errores!)

Quizás el problema principal aquí es el estilo de bucle en un idioma. En los lenguajes donde usamos la recursión, cualquier valor que cambie a lo largo del 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 de inject Smalltalk y Ruby) tienden a ser similares, aunque muchas personas en Ruby aún usarían each una y una variable mutable sobre la inject .

Cuando codifica bucles usando while y for , por otro lado, no tiene el fácil reingreso de variables que viene automáticamente cuando puede pasar varios parámetros a su porción de código que hace una iteración del ciclo, por lo que las variables inmutables serían bastante más inconvenientes.

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

  1. En la gran mayoría de los casos, las variables mutables no son necesarias, y estoy feliz de vivir sin ellas.

  2. Para la comunicación entre hilos, las variables mutables son esenciales, por razones bastante obvias. (Esto es específico de Haskell; los sistemas de tiempo de ejecución que usan mensajes que pasan al nivel más bajo no los necesitan, por supuesto.) Sin embargo, este uso es bastante raro que tener que usar funciones para leerlos y escribirlos ( readIORef fooRef val etc. ) no es una gran carga.

  3. He utilizado variables mutables dentro de un solo hilo, porque parecía facilitar ciertas cosas, pero luego me arrepentí al darme 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 la rana en la olla de agua caliente, no me había dado cuenta de lo fácil que Haskell me había hecho razonar sobre el uso de los valores hasta que encontré un ejemplo de cómo solía usarlos .

Así que en estos días he bajado bastante firmemente del lado de las variables inmutables.

Dado que las respuestas anteriores a esta pregunta han confundido estas cosas, me siento obligado a señalar con bastante contundencia que este problema es ortogonal a la pureza y la programación funcional. Siento que Ruby, por ejemplo, se beneficiaría de tener variables locales de asignación única, aunque posiblemente algunos otros cambios en el lenguaje, como la adición de recursividad final, serían necesarios para hacer esto realmente conveniente.

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 ningún problema que no pueda expresarse en ambas modas. Y especialmente porque usted señaló que el área de un ejemplo de un polígono de jpalecek podría escribirse con un plegado algo (que en mi humilde manera es más desordenado y lleva el problema a un nivel diferente de complejidad) - bien me hizo preguntarme por qué está bajando la mutabilidad por lo difícil. Así que intentaré argumentar en favor de un terreno común y una coexistencia de datos inmutables y mutables.

En mi opinión, esta pregunta se pierde un poco. Sé que los programadores estadounidenses somos proclives a que las cosas nos parezcan simples y limpias, pero a veces echamos de menos que también es posible una mezcla. Y esa es probablemente la razón por la cual, en la discusión sobre la inmutabilidad, rara vez alguien está tomando el término medio. 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 pensar: ¿realmente queremos perder la mutabilidad? ¿Es realmente uno o el otro? ¿No hay algún terreno común al que podamos llegar? ¿Cuándo la inmutabilidad me ayuda a alcanzar mis metas más rápido, cuando la mutabilidad? ¿Qué solución es más fácil de leer y mantener? (Que para mí es la mayor pregunta)

Muchas de estas preguntas están influenciadas por el gusto de un programador y por lo que se utilizan para programar. Así que me centraré en uno de los aspectos que suele ser el centro de la mayoría de los argumentos pro-inmutabilidad: Paralelismo:

A menudo, el paralelismo se lanza 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 paralelizar la manipulación de gráficos de datos realmente no es el tipo de cosa que será la forma más eficaz de paralelizar. Seguro que puede ser de gran beneficio, pero el desequilibrio es un problema real en ese espacio-problema. Por lo tanto, 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 la gráfica está aislada, que no la he revelado al mundo exterior, me gustaría realizar mis operaciones de la manera más concisa que se me ocurra. Y eso generalmente implica mutar los datos. Pero después de esta operación con los datos, quiero abrir los datos en todo el mundo, y ese es el punto donde 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 ingresan al mundo del paralelismo.

Así que los programas paralelos del mundo real generalmente tienen áreas donde los gráficos de datos se usan en operaciones de hilos únicos definitivos, porque simplemente no son conocidos por el exterior, y áreas en las que podrían estar involucrados en operaciones de subprocesos múltiples (con la esperanza de que los datos no sean manipulados) . Durante esas partes con subprocesos múltiples, nunca queremos que cambien, simplemente es mejor trabajar con datos obsoletos que con datos incoherentes. Lo cual puede ser garantizado 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 inmutable aquí, por favor verifique que solo yo pueda ver la copia mutable " . Ahora mismo tengo que garantizarlo yo mismo lanzando un bit de solo 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 cambiar 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 modelo de programación imperativa.

Así que para resumir. Los programas en mi humilde opinión generalmente tienen una buena razón para usar representaciones inmutables y mutables de gráficos de datos . Yo argumentarí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 privadas mutables , porque naturalmente hay áreas donde nunca se alcanzará el multihilo y la legibilidad y mantenibilidad podrían beneficiarse de una mayor estructuración imperativa.

Si quiere argumentar académicamente, entonces 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 forma SSA (Single Static Assignment) . 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 de SSA para comenzar:

  1. Por lo general, se necesitan más declaraciones (o más líneas de código) para escribir el código de esta manera. La brevedad tiene valor.
  2. Casi siempre es menos eficiente. Sí, sé que estás hablando de idiomas superiores, un alcance razonable, pero incluso en el mundo de Java y C #, lejos del ensamblaje, la velocidad es importante. Hay pocas aplicaciones donde la velocidad es irrelevante.
  3. 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 cabida en la programación en general.

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

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

Si tiene una función que crea una lista / árbol diferido y la reduce de nuevo, un compilador funcional puede optimizarla utilizando la deforestation .

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