Stratégie d'évaluation (informatique)

Cet article est une ébauche concernant l’informatique et l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Un langage de programmation utilise une stratégie d'évaluation pour déterminer « quand » évaluer les arguments à l'appel d'une fonction (ou encore, opération, méthode) et « comment » passer les arguments à la fonction. Par exemple, dans l'appel par valeur, les arguments doivent être évalués avant d'être passés à la fonction.

La stratégie d'évaluation d'un langage de programmation est spécifiée par la définition du langage même. En pratique, la plupart des langages de programmation (Java, C...) utilisent l'appel par valeur. En effet, l'appel par valeur permet de raisonner plus facilement lorsque l'on essaie de déterminer et de calculer la complexité algorithmique d'un programme puisque l'on sait précisément quand les arguments sont évalués.

Appel par nom

Article détaillé : Machine de Krivine.

Dans l'appel par nom, la fonction est évaluée d'abord et, à chaque fois que dans cette évaluation les paramètres sont invoqués, ceux-ci sont évalués. Par exemple, considérons une fonction fst qui rend le premier élément d'une paire. fst (3 + 2, 6 * 8) s'évalue d'abord en 3 + 2 et enfin en 5.

Appel par valeur

Article détaillé : machine SECD.

Dans l'appel par valeur, les paramètres sont d'abord évalués, puis la fonction est évaluée. Par exemple, considérons une fonction fst qui rend le premier élément d'une paire. fst (3 + 2, 6 * 8) s'évalue d'abord en fst (5, 6 * 8), puis en fst (5, 48) et enfin en 5.

Appel par nécessité

Article détaillé : évaluation paresseuse.

L'appel par nécessité est une optimisation de l'appel par nom dans laquelle les valeurs d'expressions déjà évaluées sont mémoïsées, ce qui permet de ne pas avoir à évaluer plusieurs fois les mêmes expressions.

Bibliographie

  • (en) John C. Mitchell, Concepts in Programming Languages, Cambridge University Press,
  • C. Livercy, Theorie des programmes / schemas, preuves, sémantique, Dunod, 1978
  • (en) Harold Abelson et Gerald Jay Sussman, Structure and Interpretation of Computer Programs, Cambridge, Massachusetts, The MIT Press, , Second éd., 657 p. (ISBN 978-0-262-01153-2, lire en ligne)
  • (en) Clem Baker-Finch, David King, Jon Hall et Phil Trinder, « An Operational Semantics for Parallel Call-by-Need », Research report, Faculty of Mathematics & Computing, The Open University, vol. 99, no 1,‎ (lire en ligne [ps])
  • (en) Robert Ennals et Simon Peyton Jones « Optimistic Evaluation: a fast evaluation strategy for non-strict programs » () (lire en ligne) [PDF]
    —International Conference on Functional Programming
    — « (ibid.) », ACM Press,‎
  • (en) Bertram Ludäscher, « CSE 130 lecture notes », CSE 130: Programming Languages: Principles & Paradigms,
  • (en) Benjamin C. Pierce, Types and Programming Languages, MIT Press, (ISBN 0-262-16209-1)
  • (en) Peter Sestoft, Demonstrating Lambda Calculus Reduction, vol. 2566, Springer-Verlag, coll. « Lecture Notes in Computer Science / The Essence of Computation: Complexity, Analysis, Transformation. Essays Dedicated to Neil D. Jones. », , 420–435 p., PDF (ISBN 3-540-00326-6, lire en ligne)
  • (en) « Call by Value and Call by Reference in C Programming », Call by Value and Call by Reference in C Programming explained.

Voir aussi

v · m
Codage
Modèles de calcul
Algorithmique
Syntaxe
Sémantique
Logique mathématique
Mathématiques discrètes
  • icône décorative Portail de la logique
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail de l’informatique