¿Se consideran los cierres un estilo funcional impuro?

33

¿Se consideran impuros los cierres en la programación funcional?

Parece que generalmente se pueden evitar cierres pasando valores directamente a una función. Por lo tanto, ¿deben evitarse los cierres cuando sea posible?

Si son impuros, y estoy en lo cierto al afirmar que se pueden evitar, ¿por qué tantos lenguajes de programación funcionales admiten cierres?

Uno de los criterios para una función pura es que "la función siempre evalúa el mismo valor de resultado dados los mismos valores de argumento ".

Suponer

f: x -> x + y

f(3)No siempre dará el mismo resultado. f(3)depende del valor del ycual no es un argumento de f. Por flo tanto, no es una función pura.

Dado que todos los cierres se basan en valores que no son argumentos, ¿cómo es posible que un cierre sea puro? Sí, en teoría, el valor cerrado podría ser constante, pero no hay forma de saberlo con solo mirar el código fuente de la función en sí.

A donde esto me lleva es que la misma función puede ser pura en una situación pero impura en otra. Uno no siempre puede determinar si una función es pura o no mediante el estudio de su código fuente. Por el contrario, es posible que tenga que considerarlo en el contexto de su entorno en el momento en que se llama antes de que se pueda hacer tal distinción.

¿Estoy pensando en esto correctamente?

usuario2179977
fuente
66
Uso cierres todo el tiempo en Haskell, y Haskell es tan puro como parece.
Thomas Eding
55
En un lenguaje funcional puro, yno puede cambiar, por lo que la salida de f(3)siempre será la misma.
Lily Chung
44
yes parte de la definición de faunque no esté marcado explícitamente como una entrada para f- sigue siendo el caso que fse define en términos de y(podríamos denotar la función f_y, para hacer que la dependencia sea yexplícita), y por lo tanto el cambio yda una función diferente . La función particular f_ydefinida para un particular yes muy pura. (Por ejemplo, las dos funciones f: x -> x + 3y f: x -> x + 5son diferentes funciones, y ambos puro, a pesar de que pasó a utilizar la misma letra para denotar ellos.)
ShreevatsaR

Respuestas:

26

La pureza se puede medir por dos cosas:

  1. ¿La función siempre devuelve la misma salida, dada la misma entrada; es decir, ¿es referencialmente transparente?
  2. ¿La función modifica algo fuera de sí misma, es decir, tiene efectos secundarios?

Si la respuesta a 1 es sí y la respuesta a 2 es no, entonces la función es pura. Los cierres solo impiden una función si modifica la variable cerrada.

Robert Harvey
fuente
¿No es el primer ítem determinismo? ¿O es eso también parte de la pureza? No estoy muy familiarizado con el concepto de "pureza" en el contexto de la programación.
44
@JimmyHoffa: No necesariamente. Puede poner la salida de un temporizador de hardware en una función, y nada fuera de la función se modifica.
Robert Harvey
1
@RobertHarvey ¿Se trata de cómo definimos las entradas a una función? Mi cita de wikipedia se centra en los argumentos de la función, mientras que adicionalmente considera las variables cerradas como entradas.
user2179977
8
@ user2179977: a menos que sean mutable, debería no tener en cuenta las variables cerradas en off como entradas adicionales a la función. Por el contrario, debe considerar que el cierre en sí mismo es una función y una función diferente cuando se cierra por un valor diferente de y. Entonces, por ejemplo, definimos una función gtal que g(y)es en sí misma la función x -> x + y. Entonces ges una función de enteros que devuelve funciones, g(3)es una función de enteros que devuelve enteros y g(2)es una función diferente de enteros que devuelve enteros. Las tres funciones son puras.
Steve Jessop
1
@Darkhogg: Sí. Mira mi actualización.
Robert Harvey
10

Aparecen los cierres de Lambda Calculus, que es la forma más pura de programación funcional posible, por lo que no los llamaría "impuros" ...

Los cierres no son "impuros" porque las funciones en lenguajes funcionales son ciudadanos de primera clase, lo que significa que pueden tratarse como valores.

Imagina esto (pseudocódigo):

foo(x) {
    let y = x + 1
    ...
}

yes un valor Su valor depende de x, pero xes inmutable, por lo que yel valor también es inmutable. Podemos llamar foomuchas veces con diferentes argumentos que producirán diferentes ys, pero ytodos ellos viven en diferentes ámbitos y dependen de diferentes xs para que la pureza permanezca intacta.

Ahora vamos a cambiarlo:

bar(x) {
    let y(z) = x + z
    ....
}

Aquí estamos usando un cierre (estamos cerrando sobre x), pero es igual que en foo- diferentes llamadas a barcon diferentes argumentos crean diferentes valores de y(recuerde, las funciones son valores) que son todos inmutables para que la pureza permanezca intacta.

Además, tenga en cuenta que los cierres tienen un efecto muy similar al curry:

adder(a)(b) {
    return a + b
}
baz(x) {
    let y = adder(x)
    ...
}

bazno es realmente diferente de bar: en ambos creamos un valor de función llamado yque devuelve su argumento plus x. De hecho, en Lambda Calculus usas cierres para crear funciones con múltiples argumentos, y todavía no es impuro.

Idan Arye
fuente
9

Otros han cubierto muy bien la pregunta general en sus respuestas, por lo que solo trataré de aclarar la confusión que señalas en tu edición.

El cierre no se convierte en una entrada de la función, sino que "va" al cuerpo de la función. Para ser más concreto, una función se refiere a un valor en el alcance externo en su cuerpo.

Tiene la impresión de que hace que la función sea impura. Ese no es el caso, en general. En la programación funcional, los valores son inmutables la mayor parte del tiempo . Eso se aplica también al valor cerrado.

Digamos que tienes un código como este:

let make y =
    fun x -> x + y

Llamando make 3y make 4le dará dos funciones con cierres sobre makeel yargumento. Uno de ellos regresará x + 3, el otro x + 4. Sin embargo, son dos funciones distintas, y ambas son puras. Fueron creados usando la misma makefunción, pero eso es todo.

Tenga en cuenta la mayor parte del tiempo unos pocos párrafos atrás.

  1. En Haskell, que es puro, solo puedes cerrar valores inmutables. No hay un estado mutable para cerrar. Está seguro de obtener una función pura de esa manera.
  2. En lenguajes funcionales impuros, como F #, puede cerrar celdas de referencia y tipos de referencia, y obtener una función impura en efecto. Tiene razón en que tiene que rastrear el alcance dentro del cual se define la función para saber si es pura o no. Puede saber fácilmente si un valor es mutable en esos idiomas, por lo que no es un gran problema.
  3. En los lenguajes OOP que admiten cierres, como C # y JavaScript, la situación es similar a los lenguajes funcionales impuros, pero el seguimiento del alcance externo se vuelve más complicado ya que las variables son mutables de forma predeterminada.

Tenga en cuenta que para 2 y 3, esos idiomas no ofrecen ninguna garantía sobre la pureza. La impureza allí no es una propiedad del cierre, sino del lenguaje en sí. Los cierres no cambian mucho la imagen por sí mismos.

scrwtp
fuente
1
Puede cerrar absolutamente valores mutables en Haskell, pero tal cosa se anotaría con la mónada IO.
Daniel Gratzer
1
@jozefg no, cierra sobre un IO Avalor inmutable , y su tipo de cierre es IO (B -> C)o somesuch. Se mantiene la pureza
Caleth
5

Normalmente le pediría que aclare su definición de "impuro", pero en este caso realmente no importa. Suponiendo que está contrastando el término puramente funcional , la respuesta es "no", porque no hay nada en los cierres que sea inherentemente destructivo. Si su lenguaje fuera puramente funcional sin cierres, seguiría siendo puramente funcional con cierres. Si, en cambio, quiere decir "no funcional", la respuesta sigue siendo "no"; los cierres facilitan la creación de funciones.

Parece que generalmente se pueden evitar los cierres al pasar datos directamente a una función.

Sí, pero su función tendría un parámetro más, y eso cambiaría su tipo. Los cierres le permiten crear funciones basadas en variables sin agregar parámetros. Esto es útil cuando tiene, por ejemplo, una función que toma 2 argumentos, y desea crear una versión que solo tome 1 argumento.

EDITAR: con respecto a su propia edición / ejemplo ...

Suponer

f: x -> x + y

f (3) no siempre dará el mismo resultado. f (3) depende del valor de y que no es un argumento de f. Por lo tanto, f no es una función pura.

Depende es la elección incorrecta de la palabra aquí. Citando el mismo artículo de Wikipedia que hiciste:

En la programación de computadoras, una función puede describirse como una función pura si ambas afirmaciones sobre la función tienen:

  1. La función siempre evalúa el mismo valor de resultado dados los mismos valores de argumento. El valor del resultado de la función no puede depender de ninguna información oculta o estado que pueda cambiar a medida que avanza la ejecución del programa o entre diferentes ejecuciones del programa, ni puede depender de ninguna entrada externa de los dispositivos de E / S.
  2. La evaluación del resultado no causa ningún efecto secundario o salida semánticamente observable, como la mutación de objetos mutables o la salida a dispositivos de E / S.

Suponiendo que yes inmutable (que suele ser el caso en lenguajes funcionales), se cumple la condición 1: para todos los valores de x, el valor de f(x)no cambia. Esto debería quedar claro por el hecho de que yno es diferente de una constante, y x + 3es puro. También está claro que no hay mutación o E / S.

Doval
fuente
3

Muy rápidamente: una sustitución es "referencialmente transparente" si "sustituir lo similar conduce a lo similar" y una función es "pura" si todos sus efectos están contenidos en su valor de retorno. Ambos pueden hacerse precisos, pero es vital tener en cuenta que no son idénticos ni siquiera uno implica al otro.

Ahora hablemos de los cierres.

"Cierres" aburridos (en su mayoría puros)

Los cierres ocurren porque cuando evaluamos un término lambda interpretamos las variables (enlazadas) como búsquedas de entorno. Por lo tanto, cuando devolvemos un término lambda como resultado de una evaluación, las variables dentro de él habrán "cerrado" los valores que tomaron cuando se definió.

En el simple cálculo lambda esto es algo trivial y toda la noción simplemente desaparece. Para demostrar eso, aquí hay un intérprete de cálculo lambda relativamente liviano:

-- untyped lambda calculus values are functions
data Value = FunVal (Value -> Value)

-- we write expressions where variables take string-based names, but we'll
-- also just assume that nobody ever shadows names to avoid having to do
-- capture-avoiding substitutions

type Name = String

data Expr
  = Var Name
  | App Expr Expr
  | Abs Name Expr

-- We model the environment as function from strings to values, 
-- notably ignoring any kind of smooth lookup failures
type Env = Name -> Value

-- The empty environment
env0 :: Env
env0 _ = error "Nope!"

-- Augmenting the environment with a value, "closing over" it!
addEnv :: Name -> Value -> Env -> Env
addEnv nm v e nm' | nm' == nm = v
                  | otherwise = e nm

-- And finally the interpreter itself
interp :: Env -> Expr -> Value
interp e (Var name) = e name          -- variable lookup in the env
interp e (App ef ex) =
  let FunVal f = interp e ef
      x        = interp e ex
  in f x                              -- application to lambda terms
interp e (Abs name expr) =
  -- augmentation of a local (lexical) environment
  FunVal (\value -> interp (addEnv name value e) expr)

La parte importante a tener en cuenta es addEnvcuando aumentamos el entorno con un nuevo nombre. Esta función se llama solo "dentro" del Abstérmino de tracción interpretado (término lambda). El entorno se "busca" cada vez que evaluamos un Vartérmino y, por lo tanto, se Varresuelve lo que sea que se Namemencionó en el Envque fue capturado por la Abstracción que contiene el Var.

Ahora, nuevamente, en términos simples de LC esto es aburrido. Significa que las variables enlazadas son solo constantes en lo que a nadie le importa. Se evalúan de forma directa e inmediata como los valores que denotan en el entorno como alcances léxicos hasta ese punto.

Esto también es (casi) puro. El único significado de cualquier término en nuestro cálculo lambda está determinado por su valor de retorno. La única excepción es el efecto secundario de la no terminación que se incorpora en el término Omega:

-- in simple LC syntax:
--
-- (\x -> (x x)) (\x -> (x x))
omega :: Expr
omega = App (Abs "x" (App (Var "x") 
                          (Var "x")))
            (Abs "x" (App (Var "x") 
                          (Var "x")))

Cierres (impuros) interesantes

Ahora, para ciertos entornos, los cierres descritos en el LC simple anterior son aburridos porque no existe la noción de poder interactuar con las variables que hemos cerrado. En particular, la palabra "cierre" tiende a invocar código como el siguiente Javascript

> function mk_counter() {
  var n = 0;
  return function incr() {
    return n += 1;
  }
}
undefined

> var c = mk_counter()
undefined
> c()
1
> c()
2
> c()
3

Esto demuestra que hemos cerrado la nvariable en la función interna incry que la llamada incrinteractúa significativamente con esa variable. mk_counteres puro, pero incres decididamente impuro (y tampoco es referencialmente transparente).

¿Qué difiere entre estas dos instancias?

Nociones de "variable"

Si observamos qué significan sustitución y abstracción en el sentido claro de LC, notamos que son decididamente simples. Las variables son literalmente nada más que búsquedas de entorno inmediatas. Lambda abstracción es, literalmente, nada más que la creación de un entorno aumentada para evaluar la expresión interior. No hay espacio en este modelo para el tipo de comportamiento que vimos con mk_counter/ incrporque no hay variación permitida.

Para muchos, este es el corazón de lo que significa "variable": variación. Sin embargo, a los semánticos les gusta distinguir entre el tipo de variable utilizada en LC y el tipo de "variable" utilizada en Javascript. Para hacerlo, tienden a llamar a este último una "celda mutable" o "ranura".

Esta nomenclatura sigue el largo uso histórico de "variable" en matemáticas donde significaba algo más como "desconocido": la expresión (matemática) "x + x" no permite xvariar con el tiempo, sino que tiene un significado independientemente del valor (único, constante) xtoma.

Por lo tanto, decimos "ranura" para enfatizar la capacidad de poner valores en una ranura y eliminarlos.

Para agregar más a la confusión, en Javascript estas "ranuras" se ven igual que las variables: escribimos

var x;

para crear uno y luego cuando escribimos

x;

nos indica buscando el valor actualmente almacenado en ese espacio. Para hacer esto más claro, los lenguajes puros tienden a pensar en las tragamonedas como nombres de nombres (matemáticos, cálculo lambda). En este caso, debemos etiquetar explícitamente cuándo obtenemos o colocamos desde una ranura. Tal notación tiende a parecerse a

-- create a fresh, empty slot and name it `x` in the context of the 
-- expression E
let x = newSlot in E

-- look up the value stored in the named slot named `x`, return that value
get x

-- store a new value, `v`, in the slot named `x`, return the slot
put x v

La ventaja de esta notación es que ahora tenemos una distinción firme entre variables matemáticas y ranuras mutables. Las variables pueden tomar ranuras como sus valores, pero la ranura particular nombrada por una variable es constante en todo su alcance.

Usando esta notación podemos reescribir el mk_counterejemplo (esta vez en una sintaxis similar a la de Haskell, aunque decididamente una semántica similar a la de Haskell):

mkCounter = 
  let x = newSlot 
  in (\() -> let old = get x 
             in get (put x (old + 1)))

En este caso, estamos utilizando procedimientos que manipulan esta ranura mutable. Para implementarlo, necesitaríamos cerrar no solo un entorno constante de nombres, xsino también un entorno mutable que contenga todos los espacios necesarios. Esto está más cerca de la noción común de "cierre" que la gente ama tanto.

De nuevo, mkCounteres muy impuro. También es muy referencialmente opaco. Pero tenga en cuenta que los efectos secundarios no surgen de la captura o el cierre del nombre, sino de la captura de la célula mutable y las operaciones de efectos secundarios en ella como gety put.

En última instancia, creo que esta es la respuesta final a su pregunta: la pureza no se ve afectada por la captura de variables (matemáticas) sino por las operaciones de efecto secundario realizadas en ranuras mutables nombradas por variables capturadas.

Es solo que en los idiomas que no intentan estar cerca de LC o no intentan mantener la pureza, estos dos conceptos a menudo se combinan y generan confusión.

J. Abrahamson
fuente
1

No, los cierres no hacen que una función sea impura, siempre que el valor cerrado sea constante (ni modificado por el cierre ni por otro código), que es el caso habitual en la programación funcional.

Tenga en cuenta que si bien siempre puede pasar un valor como argumento, generalmente no puede hacerlo sin una cantidad considerable de dificultad. Por ejemplo (coffeescript):

closedValue = 42
return (arg) -> console.log "#{closedValue} #{arg}"

Por su sugerencia, puede regresar:

return (arg, closedValue) -> console.log "#{closedValue} #{arg}"

Esta función no se llama en este momento, solo se define , por lo que tendría que encontrar alguna forma de pasar el valor deseado closedValueal punto en el que realmente se llama a la función. En el mejor de los casos, esto crea mucho acoplamiento. En el peor de los casos, no controlas el código en el punto de llamada, por lo que es efectivamente imposible.

Las bibliotecas de eventos en idiomas que no admiten cierres suelen proporcionar alguna otra forma de devolver datos arbitrarios a la devolución de llamada, pero no son bonitas y crean una gran complejidad tanto para el responsable de la biblioteca como para los usuarios de la biblioteca.

Karl Bielefeldt
fuente