Programmation Scheme/Grammaire de base

Programmation Scheme

1. Introduction
2. Notions élémentaires
3. Syntaxe de base
4. Grammaire de base
5. La boucle d'évaluation
6. Variables globales et variables locales
7. Récursivité

La base de la programmation Scheme est la définition de procédures.

Une procédure de base est de la forme

(opération_primitive expression1 expression2 … expression_n)

où opération_primitive est une procédure prédéfinie. À la place d'une opération primitive, on peut aussi utiliser une procédure définie préalablement.

Les arguments de la procédures sont écrits les uns à la suite des autres, séparés par un ou plusieurs espaces, voire même des sauts de ligne. Ce sont des expressions qui peuvent être des constantes, des variables ou elles-mêmes des procédures.

Quelques opérations primitives

Pour quitter l'interpréteur Scheme, il faut taper (exit).

Opérations sur les nombres

• + : addition ;
• - : soustraction ;
• / : division ;
• expt : élévation à la puissance (n'admet que deux expressions en argument) ; (expt a b) calcule a^b ;
• sqrt : racine carrée (une seule expression) ;
• abs : valeur absolue (une expression) ;
• sin, cos, tan : fonctions trigonométriques (une expression) ;
  asin, acos, atan : leurs fonctions réciproques (une expression) ;
• log : logarithme néperien (une expression) ;
• exp : exponentielle (une expression).

On remarque de fait que Scheme utilise la notation préfixée (parfois appelée « notation polonaise », bien que celle-ci soit sans parenthèse). Par exemple, l'expression infixée « 1+2+3 » donne, en notation préfixée, « (+ 1 2 3) ».

Notons également que 1/7 désigne la fraction formelle ; pour effectuer l'opération, il faut écrire (/ 1 7) (le résultat étant… 1/7).

Opérations sur les listes

• quote : indique explicitement que l'objet est une liste (en cas de confusion possible, notamment lorsque le premier objet est une lettre ou une opération primitive) ;
  (quote (expression1 … expression_n)) est abrégé en '(expression1 … expression_n) (la parenthèse ouvrante est précédée par une apostrophe) ;
• car : retourne le premier élément d'une liste ;
• cdr : retourne la liste amputée du premier élément ;
• cons : construit une liste à partir de deux expressions dont la deuxième est une liste ;
• list : construit une liste à partir d'un nombre arbitraire d'expressions.

Exemples

(cons 'a '(b))
⇒ (a b)

(list 'a 'b)
⇒ (a b)

(car '(a b))
⇒ a

(cdr '(a b))
⇒ (b)

Si l'on utilise cons et que le deuxième élément n'est pas une liste, cela crée alors une « liste pointée »

(cons 'a 'b)
⇒ (a . b)

(cons 'a '(b))
⇒ (a b)

(cons '(a) 'b)
⇒ ((a) . b)

En fait, cons construit des paires (cf infra), et le second élément de la paire n'est pas nécessairement une liste.

L'opération car sur liste pointée renvoie l'élément à la gauche du point, cdr renvoie l'élément à la droite du point.

Opérations sur les variables

Pour mettre une expression expr dans une variable var, on utilise define :

(define var expr)

en notation « infixée », cela revient à écrire « var = expr ».

Soit une expression expr contenant des variables var1, var2, … , var_n. Pour mettre cette expression dans une variable fct et en faire une fonction, on utilise aussi define :

(define (fct var1 … var_n) expr)

Cela revient à écrire, en notation infixée :

fct(var1, …, var_n) = expr

Pour l'évaluer en attribuant des valeurs constantes cst1, cst2, …, cst_n à ces variables (c'est-à-dire en notation infixée calculer fct(cst1, cst2, …, cst_n)), on écrit :

(fct cst1 … cst_n)

Structures de contrôle

Exécution conditionnelle

L'exécution conditionnelle se fait avec l'opération primitive if. Dans l'expression

(if booléen expr)

alors l'expression expr est éxecutée si booléen est vrai (#t), elle n'est pas exécutée sinon. Ainsi

(if #t '(a))
⇒ (a)

(if #f '(a))
⇒

Si l'on met deux expressions (if booléen expr1 expr2), alors expr1 est évaluée si booléen est vrai et expr2 est évaluée si booléen est faux — cela équivaut, en langage infixé, à « if booléen then expr1 else expr2 ». Ainsi

(if #t '(a) '(b))
⇒ (a)

(if #f '(a) '(b))
⇒ (b)

Bien sûr, tel quel, cela ne présente d'intérêt que si booléen est une expression dont l'évaluation donne un booléen. Les opérations primitives donnant des booléens sont appelées « prédicats » (voir ci-après).

On peut aussi utiliser l'opération perimitive cond ; celle-ci admet plusieurs booléens :

(cond
   (booléen1 expr1)
   (booléen2 expr2)
   …
   (booléen_n expr_n)
   (else expr_sinon))

L'expression expr1 est évaluée si booléen1 est #t, expr2 est évaluée si booléen2 est #t, …, expr_n est évaluée si booléen_n est #t . C'est l'équivalent du « case of » de certains langages. La dernière expression, introduite par else, est évaluée si toutes les autres sont fausses ; elle est optionnelle.

Prédicats

Les principaux prédicats sont :

• = : égalité numérique ;
• eq? ou equal? : égalité de deux expressions ;
• eqv? : équivalence de deux expressions ; la différence entre l'égalité et l'équivalence est que l'égalité concerne le contenu, l'équivalence concerne l'expression ; ainsi, deux listes de même contenu mais créées séparément ne sont pas équivalentes ;
• <, > : relations d'ordre strictes ;
• <=, >= : relations d'ordre larges ;
• null? : l'expression est-elle la liste vide ?
• list? : l'expression est-elle une liste (éventuellement vide, mais pas une liste pointée) ?
• pair? : l'expression est-elle une paire ? (Une liste non vide est une paire)
• number? : l'expression est-elle une constante de type nombre ?

Par ailleurs, on dispose des opérateurs logiques classiques or (ou logique), and (et logique), not (non logique).

Boucle

Scheme ne possède pas de structure de boucle. Le problème est traité par la récursivité (voir plus loin).

Il existe toutefois un opérateur map qui applique une fonction successivement à une liste d'arguments.

Exemple

pour calculer les racines carrées des nombres de 1 à 5 :

scheme> (map sqrt '(1 2 3 4 5))
⇒ (1 1.4142135623730951 1.7320508075688772 2 2.23606797749979)

Exemples

Opérations sur plusieurs nombres

scheme> (+ 1 2 3 4)
⇒ 10

(soit « 1+2+3+4 » en notation infixée)

scheme> (- 1 2 3)
⇒ -4

(soit « 1-2-3 » en notation infixée)

scheme> (/ 1 2 3)
⇒ 1/6

(soit « 1/2/3 » en notation infixée)

Opérations imbriquées

scheme> (+ 1 (* 2 2))
⇒ 5

(soit « 1+2×2 » en notation infixée)

scheme> (expt (cos (/ 3.1416 2)) 2)
⇒ 0.4999981633974483

soit à peu près ½, puisque cos(π/2) = 1/√2

Définir une liste d'entiers

Il y a quatre manières équivalentes de définir la liste (1 2 3 4) :

'(1 2 3 4) / (quote (1 2 3 4))
(list 1 2 3 4)
(cons 1 (cons 2 (cons 3 (cons 4 ()))))

Fonction simple

La fonction double multiplie un nombre par deux :

scheme> (define (double x) (* 2 x))

Pour l'utiliser :

scheme> (double 3)
⇒ 6

Paires et listes

Si l'on représente les paires comme des boîtes à deux cases, alors on a les équivalences suivantes entre listes et paires :

Paires et listes

Liste	Paire
(a)	a ( )
(a . b)	a b
(a b)	a b ( )

On voit que la liste (a b) est en fait une paire de paires.

Si on représente les paires comme les nœuds d'un arbre, on a la représentation suivante.

Paires et listes :
représentation arborescente

Liste	Paire
(a)	* / \ a ()
(a . b)	* / \ a b
(a b)	* / \ a * / \ b ()

Exemples

scheme>'(a . ())
⇒(a)

scheme>'(a . (b . ()))
⇒(a b)

À l'origine, le Lisp a été écrit pour les IBM 704. Une paire était alors représentée par deux valeurs : une adresse et une partie décrémentale, d'où les acronymes :

• car : content of address of register ;
• cdr : content of decrement of register.

Notez que car se prononce tel quel (à l'anglaise) et que cdr se prononce approximativement « cadeur » ou « coudeur » (/'kʌ dər/ ou /'ku dər/). Dans le jargon du MIT, on utilise le verbe to cdr down dans le sens « examiner les éléments d'une liste un par un » (cons a quant à lui donné le verbe to cons up).

Les opérateurs car et cdr peuvent être composés :

• (caar ( … )) est l'équivalent de (car ( car … )) ;
• (cddr ( … )) est l'équivalent de (cdr ( cdr … )) ;
• (cadr ( … )) est l'équivalent de (car ( cdr … )) ;
• (cdar ( … )) est l'équivalent de (cdr ( car … )) ;
• …

Exemples

scheme> (caar '((1 2) 3))
⇒ 1

scheme> (cddr '(1 2 3))
⇒ (3)

scheme> (cadr '(1 2 3))
⇒ 2

scheme> (cdar '((1 2) 3))
⇒ (2)

Importance de la grammaire

Le Lisp, dont est dérivé Scheme, a été conçu essentiellement en tant que formalisme, dans le sens : représentation formelle et systématique des données et instructions. À l'inverse de nombreux langages qui proposent de nombreuses instructions avec pour chaque une syntaxe adaptée à leur utilisation, Lisp et Scheme proposent une grammaire, une manière systématique de représenter les données et les instructions, sous forme d'expressions symboliques ou « S-expressions ».

Cela en a fait un outil de choix pour le travail sur l'intelligence artificielle, puisque l'on s'intéresse là à la possibilité d'apprentissage, au développement de nouvelles fonctionnalité plus qu'à un corpus préétabli d'instructions.

Si l'on résume la grammaire, on a :

• un vocabulaire de base composé de trois type de mots :
  1. les variables, notées dans le tableau ci-dessous <var> ;
  2. les constantes, notées dans le tableau ci-dessous <cst> ;
  3. les opérations primitives, notées dans le tableau ci-dessous <prm> ;
• deux types de phrases :
  1. les expressions, notées dans le tableau ci-dessous <exp> ;
  2. les définitions globales, notées dans le tableau ci-dessous <def>.

Le tableau ci-dessous, inspiré de [1] indique des exemples de syntaxe ; les exemples sont séparés par un tube « | ».

Résumé de la grammaire de scheme

Vocabulaire
<var>	=	x | i | diametre_du_tube | …
<cst>	=	-1 | 1 | 3/2 | 2.72 | … | 'a | 'toto | …
<prm>	=	+ |* | cos | if | let | …
Grammaire
<def>	=	(define (<var> <var> … <var>) <exp>)
<exp>	=	<var> | <cst> | (<var> <exp> … <exp>) | (<prm> <exp> … <exp>)

Voir aussi

Dans Wikipédia

• Arborescence
• Intelligence artificielle
• S-expression
• (anglais) CAR and CDR
• (anglais) Cons

Autre

• History of Lisp

---

Syntaxe de base < ↑ > La boucle d'évaluation