Les fermetures sont-elles considérées comme un style fonctionnel impur?

33

Les fermetures sont-elles considérées comme impures dans la programmation fonctionnelle?

Il semble que l'on puisse généralement éviter les fermetures en transmettant des valeurs directement à une fonction. Par conséquent, les fermetures devraient-elles être évitées autant que possible?

S'ils sont impurs, et j'ai raison de dire qu'ils peuvent être évités, pourquoi tant de langages de programmation fonctionnels prennent-ils en charge les fermetures?

L'un des critères d'une fonction pure est le suivant: "La fonction évalue toujours la même valeur de résultat avec la même valeur d'argument ."

Supposer

f: x -> x + y

f(3)ne donnera pas toujours le même résultat. f(3)dépend de la valeur de yce qui n’est pas un argument de f. Ainsi fn'est pas une fonction pure.

Puisque toutes les fermetures reposent sur des valeurs qui ne sont pas des arguments, comment une fermeture peut-elle être pure? Oui, en théorie, la valeur fermée pourrait être constante, mais il n’ya aucun moyen de le savoir simplement en consultant le code source de la fonction elle-même.

Là où cela m'amène, c'est que la même fonction peut être pure dans une situation mais impure dans une autre. On ne peut pas toujours déterminer si une fonction est pure ou pas en étudiant son code source. Au lieu de cela, on peut être amené à la considérer dans le contexte de son environnement au moment où elle est appelée avant que cette distinction puisse être faite.

Est-ce que j'y pense correctement?

utilisateur2179977
la source
6
J'utilise des fermetures tout le temps à Haskell, et Haskell est aussi pur que possible.
Thomas Eding
5
Dans un langage purement fonctionnel, yne peut pas changer, donc le résultat de f(3)sera toujours le même.
Lily Chung
4
yfait partie de la définition de fmême si elle n'est pas explicitement désignée comme une entrée dans f- c'est toujours le cas qui fest défini en termes de y(on pourrait désigner la fonction f_y, pour rendre la dépendance à yexplicitement), et donc changer ydonne une fonction différente . La fonction particulière f_ydéfinie pour un particulier yest très pure. (Par exemple, les deux fonctions f: x -> x + 3et f: x -> x + 5sont des fonctions différentes , et toutes deux pures, même si nous avons utilisé la même lettre pour les désigner.)
ShreevatsaR

Réponses:

26

La pureté peut être mesurée par deux choses:

  1. La fonction renvoie-t-elle toujours la même sortie, avec la même entrée? c'est-à-dire qu'il est référentiellement transparent?
  2. La fonction modifie-t-elle quelque chose en dehors de elle-même, c'est-à-dire qu'elle a des effets secondaires?

Si la réponse à 1 est oui et la réponse à 2 est non, alors la fonction est pure. Les fermetures ne rendent une fonction impure que si vous modifiez la variable fermée.

Robert Harvey
la source
Le déterminisme du premier élément n'est-il pas? Ou est-ce que cela fait aussi partie de la pureté? Je ne connais pas trop le concept de "pureté" dans le contexte de la programmation.
4
@ JimmyHoffa: Pas nécessairement. Vous pouvez mettre la sortie d'un temporisateur matériel dans une fonction et rien en dehors de cette fonction n'est modifié.
Robert Harvey
1
@ RobertHarvey S'agit-il de la manière dont nous définissons les entrées d'une fonction? Ma citation de wikipedia se concentre sur les arguments des fonctions, alors que vous considérez en outre les variables fermées comme des entrées.
user2179977
8
@ user2179977: à moins qu'elles ne soient mutables, vous ne devez pas considérer les variables fermées comme des entrées supplémentaires pour la fonction. Vous devez plutôt considérer que la fermeture elle-même est une fonction et une fonction différente lorsqu'elle ferme sur une valeur différente de y. Ainsi, par exemple, nous définissons une fonction gtelle qu'elle g(y)est elle-même la fonction x -> x + y. Ensuite, gune fonction d'entiers qui renvoie des fonctions, g(3)une fonction d'entiers qui renvoie des entiers et g(2)une fonction différente des entiers qui renvoie des entiers. Les trois fonctions sont pures.
Steve Jessop
1
@Darkhogg: Oui. Voir ma mise à jour.
Robert Harvey
10

Les fermetures apparaissent Lambda Calculus, qui est la forme la plus pure de programmation fonctionnelle possible, alors je ne les appellerais pas "impures" ...

Les fermetures ne sont pas "impures" car les fonctions dans les langages fonctionnels sont des citoyens de première classe - cela signifie qu'elles peuvent être traitées comme des valeurs.

Imaginez ceci (pseudocode):

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

yest une valeur. Sa valeur dépend x, mais xest immuable y, sa valeur est également immuable. Nous pouvons appeler fooplusieurs fois avec des arguments différents qui produiront des ys différents , mais ces ys vivent tous dans des domaines différents et dépendent de xs différents pour que la pureté reste intacte.

Maintenant changeons-le:

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

Nous utilisons ici une fermeture (nous fermons sur x), mais c'est la même chose que in foo- des appels bardifférents avec des arguments différents créent différentes valeurs de y(souvenez-vous - les valeurs sont des valeurs) qui sont toutes immuables, de sorte que la pureté reste intacte.

Veuillez également noter que les fermetures ont un effet très similaire au currying:

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

bazn'est pas vraiment différent de bar- dans les deux cas, nous créons une valeur de fonction nommée yqui retourne son argument plus x. En fait, dans Lambda Calculus, vous utilisez des fermetures pour créer des fonctions avec plusieurs arguments - et ce n’est toujours pas impur.

Idan Arye
la source
9

D'autres ont très bien couvert la question générale dans leurs réponses, je ne ferai donc que regarder pour dissiper la confusion que vous signalez dans votre édition.

La fermeture ne devient pas une entrée de la fonction, elle "va" dans le corps de la fonction. Pour être plus concret, une fonction fait référence à une valeur dans l'étendue externe dans son corps.

Vous avez l'impression que cela rend la fonction impure. Ce n'est pas le cas, en général. En programmation fonctionnelle, les valeurs sont immuables la plupart du temps . Cela s'applique également à la valeur fermée.

Disons que vous avez un morceau de code comme celui-ci:

let make y =
    fun x -> x + y

L' appel make 3et make 4vous donnera deux fonctions avec des fermetures plus makede » yargument. L'un d'eux reviendra x + 3, l'autre x + 4. Ce sont deux fonctions distinctes cependant, et les deux sont purs. Ils ont été créés en utilisant la même makefonction, mais c'est tout.

Notez le plus souvent quelques paragraphes en arrière.

  1. En Haskell, ce qui est pur, vous ne pouvez fermer que sur des valeurs immuables. Il n'y a pas d'état mutable à fermer. Vous êtes sûr d'obtenir une fonction pure de cette façon.
  2. Dans les langages fonctionnels impurs, comme F #, vous pouvez fermer les cellules de référence et les types de référence et obtenir une fonction impure. Vous avez raison de dire que vous devez suivre l'étendue dans laquelle la fonction est définie pour savoir si elle est pure ou non. Vous pouvez facilement savoir si une valeur est modifiable dans ces langues, donc ce n'est pas vraiment un problème.
  3. Dans les langages POO prenant en charge les fermetures, tels que C # et JavaScript, la situation est similaire à celle des langages fonctionnels impurs, mais le suivi de l'étendue externe devient plus délicat, car les variables sont modifiables par défaut.

Notez que pour 2 et 3, ces langues n'offrent aucune garantie de pureté. L'impureté n'y est pas une propriété de la fermeture, mais de la langue elle-même. Les fermetures ne changent pas beaucoup la situation par elles-mêmes.

scrwtp
la source
1
Vous pouvez absolument fermer les valeurs mutables dans Haskell, mais une telle chose serait annotée avec la monade IO.
Daniel Gratzer
1
@jozefg non, vous fermez une IO Avaleur immuable , et votre type de fermeture est IO (B -> C)ou est similaire. La pureté est maintenue
Caleth
5

Normalement, je vous demanderais de clarifier votre définition de «impur», mais dans ce cas, cela n'a pas vraiment d'importance. En supposant que vous contrastiez avec le terme purement fonctionnel , la réponse est non, car rien dans les fermetures est intrinsèquement destructeur. Si votre langage était purement fonctionnel sans fermetures, il serait toujours purement fonctionnel avec des fermetures. Si au lieu de cela, vous voulez dire "non fonctionnel", la réponse est toujours "non"; les fermetures facilitent la création de fonctions.

Il semble que l'on puisse généralement éviter les fermetures en transmettant des données directement à une fonction.

Oui, mais votre fonction aurait alors un paramètre supplémentaire, ce qui changerait son type. Les fermetures vous permettent de créer des fonctions basées sur des variables sans ajouter de paramètres. Ceci est utile lorsque vous avez, par exemple, une fonction qui prend 2 arguments et que vous voulez en créer une version qui ne prend qu'un argument.

EDIT: En ce qui concerne votre propre édition / exemple ...

Supposer

f: x -> x + y

f (3) ne donnera pas toujours le même résultat. f (3) dépend de la valeur de y qui n'est pas un argument de f. Donc f n'est pas une fonction pure.

Dépend est le mauvais choix de mot ici. En citant le même article que vous avez fait sur Wikipedia:

En programmation informatique, une fonction peut être décrite comme une fonction pure si les deux affirmations suivantes concernent la fonction:

  1. La fonction évalue toujours la même valeur de résultat avec les mêmes valeurs d'argument. La valeur du résultat de la fonction ne peut dépendre d'aucune information cachée ni d'aucun état susceptible de changer au fur et à mesure de l'exécution du programme ou entre différentes exécutions du programme, ni des entrées externes des périphériques d'E / S.
  2. L'évaluation du résultat ne provoque pas d'effet secondaire ou de sortie observable sémantiquement, tel que la mutation d'objets mutables ou la sortie sur des périphériques d'E / S.

En supposant que ysoit immuable (ce qui est généralement le cas dans les langages fonctionnels), la condition 1 est remplie: pour toutes les valeurs de x, la valeur de f(x)ne change pas. Cela devrait être clair du fait que ce yn'est pas différent d'une constante, et x + 3est pur. Il est également clair qu'il n'y a pas de mutation ou d'E / S en cours.

Doval
la source
3

Très rapidement: une substitution est "référentiellement transparente" si "la substitution de" conduit à ", et une fonction est" pure "si tous ses effets sont contenus dans sa valeur de retour. Les deux peuvent être précisés, mais il est essentiel de noter qu'ils ne sont pas identiques et que même l'un n'implique pas l'autre.

Parlons maintenant des fermetures.

"Fermetures" ennuyeuses (généralement pures)

Les fermetures se produisent parce que lorsque nous évaluons un terme lambda, nous interprétons les variables (liées) comme des recherches d’environnement. Ainsi, lorsque nous renvoyons un terme lambda à la suite d’une évaluation, les variables qu’il contient auront "fermé" sur les valeurs qu’ils avaient prises lors de sa définition.

Dans le lambda calcul, cela est trivial et toute la notion disparaît. Pour démontrer cela, voici un interprète de calcul lambda relativement léger:

-- 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 partie importante à noter est addEnvlorsque nous ajoutons un nouveau nom à l'environnement. Cette fonction est appelée uniquement "à l'intérieur" du Absterme de traction interprété (terme lambda). L’environnement est "recherché" chaque fois que nous évaluons un Varterme, ce qui permet de Varrésoudre le problème Namementionné dans le Envqui a été capturé par la Abstraction contenant le Var.

Maintenant, encore une fois, en termes simples, LC est ennuyeux. Cela signifie que les variables liées ne sont que des constantes à la portée de tous. Elles sont évaluées directement et immédiatement en tant que valeurs désignées dans l'environnement comme ayant une portée lexicale jusque-là.

C'est aussi (presque) pur. La seule signification d'un terme dans notre lambda calcul est déterminée par sa valeur de retour. La seule exception est l’effet secondaire de la non-résiliation qui est matérialisé par le terme 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")))

Fermetures intéressantes (impures)

Maintenant, dans certains contextes, les fermetures décrites dans LC ci-dessus sont ennuyeuses car il n’ya aucune notion d’interaction avec les variables sur lesquelles nous avons fermé. En particulier, le mot "fermeture" a tendance à invoquer un code comme le code Javascript suivant

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

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

Cela montre que nous avons fermé la nvariable dans la fonction interne incret que l'appel incrinteragit de manière significative avec cette variable. mk_counterest pur, mais increst décidément impur (et non pas référentiellement transparent non plus).

Qu'est-ce qui diffère entre ces deux instances?

Notions de "variable"

Si nous examinons la signification de substitution et d'abstraction au sens propre du terme LC, nous remarquons qu'elles sont clairement claires. Les variables ne sont littéralement rien de plus que des recherches immédiates sur l'environnement. L'abstraction Lambda n'est littéralement rien de plus que la création d'un environnement augmenté pour évaluer l'expression interne. Ce modèle ne laisse aucune place au type de comportement que nous avons observé avec mk_counter/ incrcar aucune variation n’est autorisée.

Pour beaucoup, c’est le cœur de ce que signifie "variable": la variation. Cependant, les sémanticistes aiment faire la distinction entre le type de variable utilisé en LC et le type de "variable" utilisé en Javascript. Pour ce faire, ils ont tendance à appeler ce dernier une "cellule mutable" ou un "slot".

Cette nomenclature suit le long usage historique de "variable" en mathématique, où il signifiait plutôt "inconnu": l'expression (mathématique) "x + x" ne permet pas xde varier dans le temps, elle a plutôt un sens de la valeur (unique, constante) xprend.

Ainsi, nous disons «slot» pour souligner la capacité de mettre des valeurs dans un slot et de les supprimer.

Pour ajouter à la confusion, en Javascript ces "slots" ressemblent à des variables: nous écrivons

var x;

pour en créer un, puis quand nous écrivons

x;

cela nous indique que nous recherchons la valeur actuellement stockée dans cet emplacement. Pour rendre cela plus clair, les langues pures ont tendance à penser que les machines à sous prennent des noms comme des noms (mathématiques, lambda calcul). Dans ce cas, nous devons explicitement étiqueter quand nous obtenons ou mettons depuis un emplacement. Une telle notation a tendance à ressembler à

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

L'avantage de cette notation est que nous avons maintenant une distinction nette entre les variables mathématiques et les slots mutables. Les variables peuvent prendre des slots comme valeurs, mais le slot particulier nommé par une variable est constant sur toute sa portée.

En utilisant cette notation, nous pouvons réécrire l’ mk_counterexemple (cette fois-ci dans une syntaxe semblable à Haskell, bien qu’une sémantique bien différente de celle de Haskell):

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

Dans ce cas, nous utilisons des procédures qui manipulent cet emplacement mutable. Afin de l'implémenter, nous devrions fermer non seulement un environnement constant de noms, xmais également un environnement mutable contenant tous les emplacements nécessaires. Ceci est plus proche de la notion commune de "fermeture" que les gens aiment tellement.

Encore une fois, mkCounterc'est très impur. C'est aussi très opaque par rapport au référentiel. Mais remarquez que les effets secondaires ne découlent pas de la capture du nom ou de la fermeture du nom, mais plutôt de la capture de la cellule mutable et des opérations produisant des effets secondaires sur elle getet put.

En fin de compte, je pense que c'est la réponse finale à votre question: la pureté n'est pas affectée par la capture de variables (mathématiques), mais par les opérations à effets secondaires effectuées sur des emplacements mutables nommés par des variables capturées.

Ce n’est que dans les langues qui ne cherchent pas à être proches de LC ou à maintenir la pureté que ces deux concepts sont si souvent confondus, ce qui conduit à la confusion.

J. Abrahamson
la source
1

Non, les fermetures ne rendent pas une fonction impure tant que la valeur fermée est constante (ni modifiée par la fermeture ni par un autre code), ce qui est le cas habituel en programmation fonctionnelle.

Notez que si vous pouvez toujours passer une valeur sous forme d'argument, vous ne pouvez généralement pas le faire sans beaucoup de difficulté. Par exemple (coffeescript):

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

Sur votre suggestion, vous pouvez simplement revenir:

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

Cette fonction n'est pas appelée à ce stade, elle est simplement définie . Vous devez donc trouver un moyen de transmettre la valeur souhaitée closedValueau point où la fonction est appelée. Au mieux, cela crée beaucoup de couplage. Dans le pire des cas, vous ne contrôlez pas le code au niveau du point d’appel, c’est donc impossible.

Les bibliothèques d'événements dans des langages qui ne prennent pas en charge les fermetures offrent généralement un autre moyen de transmettre des données arbitraires au rappel, mais ce n'est pas beau et crée beaucoup de complexité à la fois pour le responsable de la bibliothèque et pour les utilisateurs.

Karl Bielefeldt
la source