Stratégie d'évaluation - Evaluation strategy

Stratégies d'évaluation

Dans un langage de programmation , une stratégie d'évaluation est un ensemble de règles permettant d'évaluer des expressions. Le terme est souvent utilisé pour faire référence à la notion plus spécifique d'une stratégie de passage de paramètres qui définit s'il faut évaluer les paramètres d'un appel de fonction, et si oui dans quel ordre (l' ordre d'évaluation ) et le type de valeur qui est passé à la fonction pour chaque paramètre (la stratégie de liaison ). La notion de stratégie de réduction est distincte, bien que certains auteurs confondent les deux termes et que la définition de chaque terme ne soit pas largement acceptée.

Pour illustrer, une application de fonction peut évaluer l'argument avant d'évaluer le corps de la fonction et transmettre l'adresse, donnant à la fonction la possibilité de rechercher la valeur actuelle de l'argument et de la modifier via assignation .

La stratégie d'évaluation est spécifiée par la définition du langage de programmation et n'est fonction d'aucune implémentation spécifique. La convention d'appel définit les détails de transmission de paramètres spécifiques à l'implémentation.

Table

Il s'agit d'un tableau des stratégies d'évaluation et des langues représentatives par année d'introduction. Les langues représentatives sont répertoriées par ordre chronologique, en commençant par la ou les langues qui ont introduit la stratégie (le cas échéant) et suivies des langues importantes qui utilisent la stratégie.

Stratégie d'évaluation Langues représentatives Année d'introduction
Appel par référence FORTRAN II , PL/I 1958
Appel par valeur ALGOL , C , Schéma 1960
Appel par nom ALGOL 60 , Simulateur 1960
Appel par copie-restauration Fortran IV , Ada 1962
Appel par besoin Haskell , R 1971
Paramètres d'appel par référence C++ , PHP , C# , Visual Basic .NET ?
Appel par référence à const C , C++ ?
Appelez en partageant Java, Python, Rubis ?

Commandes d'évaluation

Alors que l' ordre des opérations définit l' arbre syntaxique abstrait de l'expression, l'ordre d'évaluation définit l'ordre dans lequel les expressions sont évaluées. Par exemple, le programme Python 

def f(x):
    print(x)
    return x

f(1) + f(2)

sorties 1 2dues à l'ordre d'évaluation de gauche à droite de Python, mais un programme similaire en OCaml : 

let f x =  print_string (string_of_int x); x ;;
f 1 + f 2

sorties en 2 1raison de l'ordre d'évaluation de droite à gauche d'OCaml.

L'ordre d'évaluation est principalement visible dans le code avec des effets secondaires , mais il affecte également les performances du code car un ordre rigide inhibe l' ordonnancement des instructions . Pour cette raison, les normes de langage telles que C++ laissaient traditionnellement l'ordre indéfini, bien que des langages tels que Java et C# définissent l'ordre d'évaluation de gauche à droite et que la norme C++17 ait ajouté des contraintes sur l'ordre d'évaluation.

Évaluation stricte

L'ordre d'application est une famille d'ordres d'évaluation dans laquelle les arguments d'une fonction sont évalués complètement avant que la fonction ne soit appliquée. Cela a pour effet de rendre la fonction stricte , c'est-à-dire que le résultat de la fonction est indéfini si l'un des arguments n'est pas défini, donc l'évaluation d'ordre applicatif est plus communément appelée évaluation stricte . De plus, un appel de fonction est effectué dès qu'il est rencontré dans une procédure, il est donc également appelé évaluation avide ou évaluation gloutonne . Certains auteurs appellent l'évaluation stricte « appel par valeur » en raison de la stratégie de liaison d'appel par valeur nécessitant une évaluation stricte.

Common Lisp, Eiffel et Java évaluent les arguments de fonction de gauche à droite. C laisse l'ordre indéfini. Scheme exige que l'ordre d'exécution soit l'exécution séquentielle d'une permutation non spécifiée des arguments. OCaml laisse également l'ordre non spécifié, mais en pratique évalue les arguments de droite à gauche en raison de la conception de sa machine abstraite . Tous ces éléments sont une évaluation stricte.

Évaluation non stricte

Un ordre d'évaluation non strict est un ordre d'évaluation qui n'est pas strict, c'est-à-dire qu'une fonction peut renvoyer un résultat avant que tous ses arguments ne soient entièrement évalués. L'exemple prototypique est l'évaluation d'ordre normal , qui n'évalue aucun des arguments tant qu'ils ne sont pas nécessaires dans le corps de la fonction. L'évaluation d'ordre normal a la propriété de se terminer sans erreur chaque fois qu'un autre ordre d'évaluation se termine sans erreur. Notez que l' évaluation paresseuse est classée dans cet article comme une technique de liaison plutôt que comme une commande d'évaluation. Mais cette distinction n'est pas toujours suivie et certains auteurs définissent l'évaluation paresseuse comme une évaluation d'ordre normal ou vice-versa, ou confondent la non-stricte avec l'évaluation paresseuse.

Les expressions booléennes dans de nombreuses langues utilisent une forme d'évaluation non stricte appelée évaluation de court-circuit , où l'évaluation revient dès qu'il peut être déterminé qu'un booléen sans ambiguïté résultera, par exemple, dans une expression disjonctive (OR) où trueest rencontré, ou dans une expression conjonctive (AND) où falseest rencontré, et ainsi de suite. Les expressions conditionnelles utilisent de la même manière une évaluation non stricte - une seule des branches est évaluée.

Comparaison de l'ordre applicatif et de l'évaluation de l'ordre normal

Avec une évaluation d'ordre normale, les expressions contenant un calcul coûteux, une erreur ou une boucle infinie seront ignorées si elles ne sont pas nécessaires, permettant la spécification de constructions de flux de contrôle définies par l'utilisateur, une fonction non disponible avec l'évaluation d'ordre applicatif. L'évaluation de l'ordre normal utilise des structures complexes telles que les thunks pour les expressions non évaluées, par rapport à la pile d'appels utilisée dans l'évaluation de l'ordre applicatif. L'évaluation de l'ordre normal a toujours manqué d'outils de débogage utilisables en raison de sa complexité.

Stratégies de liaison strictes

Appel par valeur

Dans l'appel par valeur, la valeur évaluée de l'expression d'argument est liée à la variable correspondante dans la fonction (souvent en copiant la valeur dans une nouvelle région de mémoire). Si la fonction ou la procédure est capable d'affecter des valeurs à ses paramètres, seule sa variable locale est affectée, c'est-à-dire que tout ce qui est passé dans un appel de fonction reste inchangé dans la portée de l'appelant lorsque la fonction revient.

Limites implicites

Dans certains cas, le terme "appel par valeur" est problématique, car la valeur qui est transmise n'est pas la valeur de la variable telle qu'elle est comprise par le sens ordinaire de valeur, mais une référence spécifique à la mise en œuvre à la valeur. L'effet est que ce qui ressemble syntaxiquement à un appel par valeur peut finir par se comporter plutôt comme un appel par référence ou un appel par partage , souvent en fonction d'aspects très subtils de la sémantique du langage.

La raison du passage d'une référence est souvent que le langage ne fournit pas techniquement une représentation de valeur de données compliquées, mais les représente plutôt comme une structure de données tout en préservant un semblant d'apparence de valeur dans le code source. Il est souvent difficile de prédire exactement où la frontière est tracée entre les valeurs appropriées et les structures de données se faisant passer pour telles. En C , un tableau (dont les chaînes sont des cas particuliers) est une structure de données mais le nom d'un tableau est traité comme (a comme valeur) la référence au premier élément du tableau, tandis que le nom d'une variable struct fait référence à une valeur même s'il a des champs qui sont des vecteurs. Dans Maple , un vecteur est un cas particulier d'une table et donc d'une structure de données, mais une liste (qui est rendue et peut être indexée exactement de la même manière) est une valeur. Dans Tcl , les valeurs sont "à double accès" de sorte que la représentation de la valeur est utilisée au niveau du script, et le langage lui-même gère la structure de données correspondante, si nécessaire. Les modifications apportées via la structure de données sont répercutées sur la représentation des valeurs et vice versa.

La description "appel par valeur où la valeur est une référence" est courante (mais ne doit pas être comprise comme étant un appel par référence) ; un autre terme est appel par partage . Ainsi le comportement de l'appel par valeur Java ou Visual Basic et de l'appel par valeur C ou Pascal sont sensiblement différents : en C ou Pascal, appeler une fonction avec une grande structure en argument entraînera la copie de toute la structure (sauf si c'est en fait une référence à une structure), provoquant potentiellement une grave dégradation des performances, et les mutations de la structure sont invisibles pour l'appelant. Cependant, en Java ou Visual Basic, seule la référence à la structure est copiée, ce qui est rapide, et les mutations de la structure sont visibles pour l'appelant.

Appel par référence

L'appel par référence (ou le passage par référence) est une stratégie d'évaluation où un paramètre est lié à une référence implicite à la variable utilisée comme argument, plutôt qu'à une copie de sa valeur.

Cela signifie généralement que la fonction peut modifier (c'est-à-dire affecter à ) la variable utilisée comme argument—quelque chose qui sera vu par son appelant. L'appel par référence peut donc être utilisé pour fournir un canal de communication supplémentaire entre la fonction appelée et la fonction appelante. Un langage d'appel par référence rend plus difficile pour un programmeur de suivre les effets d'un appel de fonction et peut introduire des bogues subtils. Un simple test décisif pour savoir si un langage prend en charge la sémantique d'appel par référence est de savoir s'il est possible d'écrire une swap(a, b)fonction traditionnelle dans le langage.

L'appel par référence peut être simulé dans des langages qui utilisent l'appel par valeur et ne prennent pas exactement en charge l'appel par référence, en utilisant des références (objets faisant référence à d'autres objets), tels que des pointeurs (objets représentant les adresses mémoire d'autres objets) . Des langages tels que C , ML et Rust utilisent cette technique. Il ne s'agit pas d'une stratégie d'évaluation distincte - la langue appelle par valeur - mais elle est parfois appelée "appel par adresse" ou "passage par adresse". En ML, les références sont type- et la mémoire de sécurité , semblable à Rust.

Dans les langages purement fonctionnels, il n'y a généralement pas de différence sémantique entre les deux stratégies (puisque leurs structures de données sont immuables, il n'y a donc aucune possibilité pour une fonction de modifier l'un de ses arguments), elles sont donc généralement décrites comme des appels par valeur même si les implémentations utilisez fréquemment l'appel par référence en interne pour les avantages d'efficacité.

Voici un exemple qui illustre l'appel par référence dans le langage de programmation E : 

def modify(var p, &q) {
    p := 27 # passed by value: only the local parameter is modified
    q := 27 # passed by reference: variable used in call is modified
}

? var a := 1
# value: 1
? var b := 2
# value: 2
? modify(a, &b)
? a
# value: 1
? b
# value: 27

Voici un exemple d'appel par adresse qui simule l'appel par référence en C : 

void modify(int p, int* q, int* r) {
    p = 27; // passed by value: only the local parameter is modified
    *q = 27; // passed by value or reference, check call site to determine which
    *r = 27; // passed by value or reference, check call site to determine which
}

int main() {
    int a = 1;
    int b = 1;
    int x = 1;
    int* c = &x;
    modify(a, &b, c); // a is passed by value, b is passed by reference by creating a pointer (call by value),
                    // c is a pointer passed by value
                    // b and x are changed
    return 0;
}

Appelez en partageant

L'appel par partage (également appelé « appel par objet » ou « appel par partage d'objet ») est une stratégie d'évaluation notée pour la première fois par Barbara Liskov en 1974 pour le langage CLU . Il est utilisé par des langages tels que Python , Java (pour les références d'objets), Ruby , JavaScript , Scheme, OCaml, AppleScript et bien d'autres. Cependant, le terme « appel par partage » n'est pas d'usage courant ; la terminologie est incohérente entre les différentes sources. Par exemple, dans la communauté Java, on dit que Java est un appel par valeur. L'appel par partage implique que les valeurs dans le langage sont basées sur des objets plutôt que sur des types primitifs , c'est-à-dire que toutes les valeurs sont « encadrées ». Parce qu'elles sont encadrées, on peut dire qu'elles passent par copie de référence (où les primitives sont encadrées avant de passer et déballées à la fonction appelée).

La sémantique de l'appel par partage diffère de l'appel par référence : "En particulier ce n'est pas un appel par valeur car les mutations d'arguments effectuées par la routine appelée seront visibles par l'appelant. Et ce n'est pas un appel par référence car l'accès n'est pas donné à les variables de l'appelant, mais seulement à certains objets". Ainsi, par exemple, si une variable a été passée, il n'est pas possible de simuler une affectation sur cette variable dans la portée de l'appelé. Cependant, étant donné que la fonction a accès au même objet que l'appelant (aucune copie n'est effectuée), les mutations de ces objets, si les objets sont mutables , au sein de la fonction sont visibles pour l'appelant, ce qui peut sembler différent de l'appel par valeur sémantique. Les mutations d'un objet modifiable au sein de la fonction sont visibles pour l'appelant car l'objet n'est ni copié ni cloné, il est partagé.

Par exemple, en Python, les listes sont modifiables, donc : 

def f(a_list):
    a_list.append(1)

m = []
f(m)
print(m)

sorties [1]car la appendméthode modifie l'objet sur lequel elle est appelée.

Les affectations au sein d'une fonction ne sont pas perceptibles par l'appelant, car, dans ces langages, passer la variable signifie uniquement passer (accéder à) l'objet réel auquel la variable fait référence, pas accéder à la variable d'origine (de l'appelant). Étant donné que la variable de rebond n'existe que dans le cadre de la fonction, la contrepartie dans l'appelant conserve sa liaison d'origine.

Comparez la mutation Python ci-dessus avec le code ci-dessous, qui lie l'argument formel à un nouvel objet : 

def f(a_list):
    a_list = [1]

m = []
f(m)
print(m)

sorties [], car l'instruction a_list = [1]réaffecte une nouvelle liste à la variable plutôt qu'à l'emplacement auquel elle fait référence.

Pour les objets immuables , il n'y a pas de réelle différence entre appel par partage et appel par valeur, sauf si l'identité de l'objet est visible dans le langage. L'utilisation de l'appel par partage avec des objets mutables est une alternative aux paramètres d'entrée/sortie : le paramètre n'est pas affecté à (l'argument n'est pas écrasé et l'identité de l'objet n'est pas modifiée), mais l'objet (argument) est muté.

Appel par copie-restauration

L'appel par copie-restauration - également connu sous le nom de « copie d'entrée/de copie-sortie », « appel par résultat de valeur », « appel par retour de valeur » (comme on l'appelle dans la communauté Fortran ) - est un cas particulier d'appel par référence où le à condition que la référence soit unique à l'appelant. Cette variante a attiré l'attention dans les contextes de multitraitement et d'appel de procédure distante : si un paramètre d'un appel de fonction est une référence qui pourrait être accessible par un autre thread d'exécution, son contenu peut être copié dans une nouvelle référence qui ne l'est pas ; lorsque l'appel de fonction revient, le contenu mis à jour de cette nouvelle référence est copié dans la référence d'origine ("restauré").

La sémantique de l' appel copie-restauration diffèrent également de ceux d'appel par référence, où deux arguments de la fonction ou plusieurs alias un autre ( par exemple, le point à la même variable dans l'environnement de l'appelant). Sous appel par référence, écrire à l'un affectera l'autre ; l'appel par copie-restauration évite cela en donnant à la fonction des copies distinctes, mais laisse le résultat dans l'environnement de l'appelant indéfini selon lequel des arguments alias est copié en premier - les copies seront-elles faites dans l'ordre de gauche à droite à la fois à l'entrée et au retour ?

Lorsque la référence est passée à l'appelé non initialisée, cette stratégie d'évaluation peut être appelée "appel par résultat".

Stratégies de liaison non strictes

Appel par nom

Appel par le nom est une stratégie d'évaluation où les arguments d'une fonction ne sont pas évalués avant que la fonction est appelée plutôt, ils sont substitués directement dans le corps de la fonction ( en utilisant substitution en évitant la capture ), puis à gauche à évaluer chaque fois qu'ils apparaissent dans le fonction. Si un argument n'est pas utilisé dans le corps de la fonction, l'argument n'est jamais évalué ; s'il est utilisé plusieurs fois, il est réévalué à chaque apparition. (Voir l'appareil de Jensen .)

L'évaluation appel par nom est parfois préférable à l'évaluation appel par valeur. Si l'argument d'une fonction n'est pas utilisé dans la fonction, l'appel par nom fera gagner du temps en n'évaluant pas l'argument, tandis que l'appel par valeur l'évaluera malgré tout. Si l'argument est un calcul non terminé, l'avantage est énorme. Cependant, lorsque l'argument de fonction est utilisé, l'appel par nom est souvent plus lent, nécessitant un mécanisme tel qu'un thunk .

Les langages .NET actuels peuvent simuler un appel par nom à l'aide de délégués ou de Expression<T>paramètres. Ce dernier aboutit à un arbre syntaxique abstrait donné à la fonction. Eiffel fournit des agents, qui représentent une opération à évaluer en cas de besoin. Seed7 fournit un appel par nom avec des paramètres de fonction. Les programmes Java peuvent effectuer une évaluation paresseuse similaire à l'aide d' expressions lambda et de l' java.util.function.Supplier<T>interface.

Appel par besoin

Article principal: évaluation paresseuse

L'appel par besoin est une variante mémorisée de l'appel par nom, où, si l'argument de la fonction est évalué, cette valeur est stockée pour une utilisation ultérieure. Si l'argument est pur (c'est-à-dire sans effets secondaires), cela produit les mêmes résultats que l'appel par nom, ce qui permet d'économiser le coût du recalcul de l'argument.

Haskell est un langage bien connu qui utilise l'évaluation appel par besoin. Parce que l'évaluation des expressions peut se produire arbitrairement loin dans un calcul, Haskell ne prend en charge que les effets secondaires (tels que la mutation ) via l'utilisation de monades . Cela élimine tout comportement inattendu des variables dont les valeurs changent avant leur évaluation différée.

Dans l'implémentation de R de call by need, tous les arguments sont passés, ce qui signifie que R autorise des effets secondaires arbitraires.

L'évaluation paresseuse est l'implémentation la plus courante de la sémantique d'appel par besoin, mais des variations comme l' évaluation optimiste existent. Les langages .NET implémentent l'appel par besoin en utilisant le type Lazy<T>.

La réduction de graphe est une implémentation efficace de l'évaluation paresseuse.

Appel par extension de macro

L'extension appel par macro est similaire à l'appel par nom, mais utilise la substitution textuelle plutôt que la capture, évitant ainsi la substitution. Mais la substitution de macro peut provoquer des erreurs, entraînant une capture de variable , conduisant à un comportement indésirable. Les macros hygiéniques évitent ce problème en vérifiant et en remplaçant les variables masquées qui ne sont pas des paramètres.

Appeler par le futur

Voir aussi : Futures et promesses

"Appel par futur", également connu sous le nom d'"appel parallèle par nom", est une stratégie d'évaluation simultanée dans laquelle la valeur d'une expression future est calculée en même temps que le flux du reste du programme avec des promesses, également connu sous le nom de contrats à terme. Lorsque la valeur de la promesse est nécessaire, le programme principal bloque jusqu'à ce que la promesse ait une valeur (la promesse ou l'une des promesses termine le calcul, si ce n'est pas déjà fait à ce moment-là).

Cette stratégie est non déterministe, car l'évaluation peut avoir lieu à n'importe quel moment entre la création du futur (c'est-à-dire lorsque l'expression est donnée) et l'utilisation de la valeur du futur. Il est similaire à l'appel par besoin en ce sens que la valeur n'est calculée qu'une seule fois, et le calcul peut être différé jusqu'à ce que la valeur soit nécessaire, mais il peut être démarré avant. De plus, si la valeur d'un futur n'est pas nécessaire, comme s'il s'agit d'une variable locale dans une fonction qui retourne, le calcul peut être terminé à mi-chemin.

Si implémenté avec des processus ou des threads, la création d'un futur engendrera un ou plusieurs nouveaux processus ou threads (pour les promesses), accéder à la valeur les synchronisera avec le thread principal, et terminer le calcul du futur correspond à tuer les promesses en calculant son valeur.

Si elle est implémentée avec une coroutine , comme dans .NET async/await , la création d'un futur appelle une coroutine (une fonction asynchrone), qui peut céder à l'appelant, et à son tour être cédée lorsque la valeur est utilisée, en coopération multitâche.

Évaluation optimiste

L'évaluation optimiste est une autre variante d'appel par besoin où l'argument de la fonction est partiellement évalué pendant un certain temps (qui peut être ajusté au moment de l' exécution ). Une fois ce temps écoulé, l'évaluation est abandonnée et la fonction est appliquée à l'aide d'un appel par besoin. Cette approche permet d'éviter certains frais d'exécution de la stratégie d'appel par besoin tout en conservant les caractéristiques de terminaison souhaitées.

Voir également

Les références


Lectures complémentaires

Liens externes