Programmation Scheme/Grammaire de base

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche


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

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[modifier | modifier le wikicode]

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

Opérations sur les nombres[modifier | modifier le wikicode]

  • + : 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[modifier | modifier le wikicode]

  • 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 (expression1expression_n)) est abrégé en '(expression1expression_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 renvoit l'élément à la gauche du point, cdr renvoit l'élément à la droite du point.

Opérations sur les variables[modifier | modifier le wikicode]

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 var1var_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 cst1cst_n)

Structures de contrôle[modifier | modifier le wikicode]

Exécution conditionnelle[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Dans Wikipédia
Autre



Syntaxe de base < > La boucle d'évaluation