scala - qué - funciones de orden superior

¿Son los efectos secundarios todo lo que no se puede encontrar en una función pura?

Question

¿Es seguro decir que la siguiente dicotomía es válida?

Cada función dada es

• o bien puro
• o tiene efectos secundarios

Si es así, los efectos secundarios (de una función) son algo que no se puede encontrar en una función pura.

Answer 1

Esto depende mucho de las definiciones que elijas. Definitivamente es justo decir que una función es pura o impura . Una función pura siempre devuelve el mismo resultado y no modifica el entorno. Una función impura puede devolver resultados diferentes cuando se ejecuta repetidamente (lo que puede ser causado por hacer algo al medio ambiente).

¿Son todos los efectos secundarios de las impurezas? No lo diría, una función puede depender de algo en el entorno en el que se ejecuta. Esto podría ser leer alguna configuración, ubicación de GPS o leer datos de Internet. Estos no son realmente "efectos secundarios" porque no le hacen nada al mundo .

Creo que hay dos tipos diferentes de impurezas:

• La impureza de salida es cuando una función le hace algo al mundo. En Haskell, esto se modela utilizando mónadas: una función impura a -> b es en realidad una función a -> M b donde M captura las otras cosas que hace al mundo.

• La impureza de entrada es cuando una función requiere algo del entorno. Una función impura a -> b puede modelarse como una función C a -> b donde el tipo C captura otras cosas del entorno al que la función puede acceder.

Las mónadas y las impurezas de salida son ciertamente más conocidas, pero creo que las impurezas de entrada son igualmente importantes. Escribí mi tesis doctoral sobre las impurezas de entrada que llamo efectos colaterales , por lo que esta podría ser una respuesta sesgada.

Answer 2

Los efectos secundarios son parte de la definición del lenguaje. En la expresion

f e

los efectos secundarios de e son todas las partes del comportamiento de e que se "desplazan" y se convierten en parte del comportamiento de la expresión de la aplicación, en lugar de pasar a f como parte del valor de e .

Para un ejemplo concreto, considere este programa:

f x = x; x
f (print 3)

donde conceptualmente la sintaxis x; x x; x significa ''ejecuta x, luego ejecútalo de nuevo y devuelve el resultado''.

En un lenguaje donde la print escribe en la salida estándar como un efecto secundario, esto escribe

3

Porque la salida es parte de la semántica de la expresión de la aplicación.

En un lenguaje donde la salida de print no es un efecto secundario, esto escribe

3
3

porque la salida es parte de la semántica de la variable x dentro de la definición de f .

Answer 3

No veo problemas con la definición de una función pura: una función pura es una función. Es decir, tiene un dominio, un codominio y asigna los elementos del primero a los elementos del segundo. Se define en todas las entradas. No le hace nada al entorno, porque "el entorno" en este punto no existe: no hay máquinas que puedan ejecutar (para alguna definición de "ejecutar") una función determinada. Solo hay un mapeo total de algo a algo.

Luego, algún capitalista decide invadir el mundo de funciones bien definidas y esclavizar a esas criaturas puras, pero su esencia justa no puede sobrevivir en nuestra cruel realidad, las funciones se ensucian y comienzan a calentar la CPU.

Entonces, el ambiente es el responsable de hacer que la CPU se caliente y tiene mucho sentido hablar de pureza antes de que su propietario sea objeto de abuso y ejecución. De la misma manera, la transparencia referencial es una propiedad de un idioma, no se mantiene en el entorno en general, porque puede haber un error en el compilador o un meteorito puede caer sobre su cabeza y su programa dejará de producir el mismo resultado .

Pero hay otras criaturas: los habitantes oscuros del inframundo. Se parecen a las funciones, pero son conscientes del entorno y pueden interactuar con él: leer variables, enviar mensajes y lanzar misiles. Llamamos a estos familiares caídos de funciones "impuras" o "efectivas" y evitamos tanto como sea posible, porque su naturaleza es tan oscura que es imposible razonar sobre ellas.

Por lo tanto, existe una clara diferencia entre las funciones que pueden interactuar con el exterior y las que no. Sin embargo, la definición de "fuera" también puede variar. La mónada State se modela utilizando solo herramientas puras, pero pensamos en f : Int -> State Int Int como en el cálculo efectivo. Además, la non-termination y las excepciones ( error "..." ) son efectos, pero los haskellers generalmente no los consideran así.

Resumiendo, una función pura es un concepto matemático bien definido, pero generalmente consideramos funciones en lenguajes de programación y lo que es puro depende de su punto de vista, por lo que no tiene mucho sentido hablar de dicotomías cuando los conceptos involucrados no son bien definido.

Answer 4

Para que una función sea pura debe:

1. no se ve afectado por los efectos secundarios (es decir, siempre devuelve el mismo valor para los mismos argumentos)
2. no causa efectos secundarios

Pero, usted ve, esto define la pureza funcional con la propiedad o la ausencia de efectos secundarios. Está intentando aplicar la lógica hacia atrás para deducir la definición de efectos secundarios mediante el uso de funciones puras, que lógicamente deberían funcionar, pero prácticamente la definición de un efecto secundario no tiene nada que ver con la pureza funcional.

Answer 5

Una forma de definir la pureza de una función f es ∀x∀yx = y ⇒ fx = fy , es decir, dado el mismo argumento, la función devuelve el mismo resultado o conserva la igualdad.

Esto no es lo que las personas suelen decir cuando hablan de "funciones puras"; Por lo general, significan "puro", ya que "no tiene efectos secundarios". No he descubierto cómo calificar un "efecto secundario" (¡bienvenidos los comentarios!), Así que no tengo nada que decir al respecto.

No obstante, exploraré este concepto de pureza porque podría ofrecer alguna información relacionada. No soy un experto aquí; esto es sobre todo yo solo divagando Sin embargo, espero que despierte algunos comentarios perspicaces (¡y correctivos!).

Para entender la pureza tenemos que saber de qué igualdad estamos hablando. ¿Qué significa x = y , y qué significa fx = fy ?

Una opción es la igualdad semántica de Haskell. Es decir, la igualdad de la semántica que Haskell asigna a sus términos. Por lo que sé, no hay una semántica denotacional oficial para Haskell, pero Wikibooks Haskell Denotational Semantics ofrece un estándar razonable que creo que la comunidad está más o menos de acuerdo con ad-hoc. Cuando Haskell dice que sus funciones son puras, esta es la igualdad a la que se refiere.

Otra opción es una igualdad definida por el usuario (es decir, (==) ) al derivar la clase Eq . Esto es relevante cuando se utiliza el diseño de denotación, es decir, estamos asignando nuestra propia semántica a los términos. Con esta elección podemos accidentalmente escribir funciones que son impuras; Haskell no está preocupado por nuestra semántica.

Me referiré a la igualdad semántica de Haskell como = y la igualdad definida por el usuario como == . También asumo que == es una relación de igualdad, esto no es válido para algunos casos de == como para Float .

Cuando uso x == y como una propuesta, lo que realmente quiero decir es que x == y = True ∨ x == y = ⊥ , porque x == y :: Bool y ⊥ :: Bool . En otras palabras, cuando digo que x == y es verdadero, quiero decir que si se calcula a algo distinto de ⊥, entonces se calcula a verdadero.

Si x e y son iguales según la semántica de Haskell, entonces son iguales según cualquier otra semántica que podamos elegir.

Prueba: si x = y entonces x == y ≡ x == x y x == x es verdadero porque == es puro (de acuerdo con = ) y reflexivo.

De manera similar, podemos probar que ∀f∀x∀yx = y ⇒ fx == fy . Si x = y entonces fx = fy (porque f es puro), por lo tanto, fx == fy ≡ fx == fx y fx == fx es verdadero porque == es puro y reflexivo.

Este es un ejemplo tonto de cómo podemos romper la pureza para una igualdad definida por el usuario.

data Pair a = Pair a a

instance (Eq a) => Eq (Pair a) where
  Pair x _ == Pair y _ = x == y

swap :: Pair a -> Pair a
swap (Pair x y) = Pair y x

Ahora tenemos:

Pair 0 1 == Pair 0 2

Pero:

swap (Pair 0 1) /= swap (Pair 0 2)

Nota: ¬(Pair 0 1 = Pair 0 2) por lo que no se nos garantizó que nuestra definición de (==) estaría bien.

Un ejemplo más convincente es considerar Data.Set . Si x, y, z :: Set A entonces esperaría que esto sea válido, por ejemplo:

x == y ⇒ (Set.union z) x == (Set.union z) y

Especialmente cuando Set.fromList [1,2,3] y Set.fromList [3,2,1] denotan el mismo conjunto pero probablemente tienen diferentes representaciones (ocultas) (no equivalentes por la semántica de Haskell). Es decir, queremos estar seguros de que ∀z Set.union z es puro de acuerdo con (==) para Set .

Aquí hay un tipo con el que he jugado:

newtype Spry a = Spry [a]

instance (Eq a) => Eq (Spry a) where
  Spry xs == Spry ys = fmap head (group xs) == fmap head (group ys)

Un Spry es una lista que tiene elementos adyacentes no iguales. Ejemplos:

Spry [] == Spry []
Spry [1,1] == Spry [1]
Spry [1,2,2,2,1,1,2] == Spry [1,2,1,2]

Dado esto, ¿qué es una implementación pura (según == para Spry) para flatten :: Spry (Spry a) -> Spry a tal que si x es un elemento de un sub-spry también es un elemento del spry aplanado? (es decir, algo como ∀x∀xs∀ix ∈ xs[i] ⇒ x ∈ flatten xs )? Ejercicio para el lector.

También vale la pena señalar que las funciones de las que hemos estado hablando están en el mismo dominio, por lo que tienen el tipo A → A Eso es excepto cuando probamos ∀f∀x∀yx = y ⇒ fx == fy que cruza desde el dominio semántico de Haskell hasta el nuestro. Esto podría ser un homomorfismo de algún tipo ... tal vez un teórico de la categoría podría influir aquí (¡y por favor!).