En mathématique ou en informatique, une expression exprime la façon de calculer une valeur. Par exemple,  
a*f(a-1)  
dit qu'il faut appliquer la multiplication -- qui est représentée par l'opérateur * -- aux valeurs des deux sous-expressions a et f(a-1). À nouveau, pour cette dernière, on doit appliquer la fonction f à la valeur de a-1 qui est elle-même obtenue...
 
Première remarque: La dénomination « programmation applicative » qui désigne le style de programmation que nous utiliserons pendant ce semestre est issue de cette vision du calcul d'une expression (« appliquer la multiplication », « appliquer la fonction f »...). En effet, l'évaluation des expressions est une des clefs d'une telle programmation.
 
Remarque historique: Fortran (FORmula TRANslator), premier langage de programmation évolué et compilé, a été défini, en 1954, par John Backus dont un des buts était de « permettre une formulation concise d'un problème en utilisant les notations mathématiques »: il s'agissait avant tout de pouvoir écrire directement les expressions mathématiques.
 
Compréhension d'une expression  
Considérons l'expression, écrite dans le langage mathématique habituel,  
3x² + 2x + 4  
On peut déjà remarquer quelques caractéristiques qui ne sont jamais présentes dans les langages informatiques:

• dans 3x² et dans 2x, la multiplication est sous-entendue, c'est-à-dire que l'on peut écrire aussi 3 × x² + 2 × x + 4;
• l'exponentiation (dans x²) est notée en mettant l'exposant en dessus de la ligne, ce qui n'est pas possible dans les écritures linéaires utilisées en informatique.

 
Il faut remarquer que l'addition, la multiplication, la division... sont des opérations binaires: à deux valeurs elles font correspondre une troisième. Lors de l'évaluation d'une expression, une telle opération (qui est appelée l'opération principale de l'expression) est appliquée aux résultats de l'évaluation de deux sous-expressions. Pour bien indiquer les sous-expressions, on peut entourer chaque expression, non réduite à une variable, par des parenthèses: on dit que l'on a un langage complètement parenthésé. Mais habituellement on « oublie » des parenthèses:  

a - b + c	peut se comprendre	(a - b) + c
	ou	a - (b + c)
a + b × c	peut se comprendre	(a + b) × c
	ou	a + (b × c)
a / b / c	peut se comprendre	(a / b) / c
	ou	a / (b / c)

 

 
ce qui, dans les trois cas, ne donne pas le même résultat! Quelle est la bonne lecture? => difficultés pour analyser automatiquement les expressions.
 
Différentes écritures linéaires d'une expression
 
Il existe plusieurs écritures linéaires (i.e. comme suite de caractères) d'une expression selon le placement de l'opérateur par rapport à ses opérandes:

• en préfixé, l'opérateur précède ses opérandes,
• en suffixé, l'opérateur suit ses opérandes,
• en infixé, un opérateur binaire se situe entre ses arguments.

 
Par exemple, l'expression
 
a / c + 5sin(b × d), peut s'écrire:  
 
  en préfixé: + / a c × 5 sin × b d  
 
  en suffixé: a c / 5 b d × sin × +  
 
  en infixé: ((a / c) + (5 × sin(b × d)))  

 
Lemme de Lukasiewicz: si l'on connait l'arité des opérateurs, on peut retrouver l'expression à partir de l'une des notations suffixe et préfixe.
 
Autrement dit, ces deux notations représentent de façon non-ambiguë l'expression. En revanche, la notation infixe est ambiguë et il est nécessaire d'utiliser des parenthèses.
 
Remarques:

1. la notation mathématique utilise la notation préfixe pour les fonctions en écrivant d'abord le nom de la fonction puis, entre parenthèses, les différents arguments séparés par une virgule;
2. noter aussi la différence entre ab qu'on lit a× b -- on considère donc qu'il y a deux symboles, a et b -- et sin qui représente un seul symbole, le nom de la fonction sinus;
3. dans la terminologie mathématique, on distingue les opérateurs (+, ×...) et les fonctions (sin...); en Scheme, on ne parlera pas d'opérateur mais systématiquement de fonctions;
4. en Scheme, nous nommerons applications ces expressions (car nous verrons que la notion d'expression est plus générale: une application Scheme est une expression Scheme, mais il y a des expressions Scheme qui ne sont pas des applications);
5. dans la littérature, on dit parfois « appel de fonction » à la place d'« application de fonction ».