# Programmation Scheme/Version imprimable

* Si vous imprimez cette page, choisissez « Aperçu avant impression » dans votre navigateur, ou cliquez sur le lien Version imprimable dans la boîte à outils, vous verrez cette page sans ce message, ni éléments de navigation sur la gauche ou en haut.
* Cliquez sur Rafraîchir cette page pour obtenir la dernière version du wikilivre.
* Pour plus d'informations sur les version imprimables, y compris la manière d'obtenir une version PDF, vous pouvez lire l'article Versions imprimables.
Une version à jour et éditable de ce livre est disponible sur Wikilivres, une bibliothèque de livres pédagogiques, à l'URL : https://fr.wikibooks.org/wiki/Programmation_Scheme

# Introduction

Scheme (prononcer « skim' ») est un langage de programmation dérivé du langage fonctionnel Lisp, créé dans les années 1970 au MIT par Gerald Jay Sussman et Guy L. Steele.
Le but des créateurs du langage était d'épurer le langage Lisp en conservant les aspects essentiels, la flexibilité et la puissance expressive. Scheme a donc une syntaxe extrêmement simple, avec un nombre très limité de mots-clé. Comme en Lisp, la notation préfixée permet de s'affranchir des opérateurs de précédence. De plus, la puissance des macros de Scheme lui permettent de s'adapter à n'importe quel problème, notamment de le rendre orienté objet et donc multi-paradigme.
La spécification de Scheme précise que toutes les mises en œuvres (interpréteurs, compilateurs) doivent optimiser le cas de la récursion terminale.
Les types de données de base de Scheme sont
* les booléens,
* les nombres, qui peuvent être entiers de taille indéfinie, rationnels ou complexes,
* les caractères ou les symboles, qui sont des variables.
À ceux-là s'ajoutent des types de données composites suivants :
* chaînes de caractères,
* vecteurs,
* paires orientées,
* listes,
* listes associatives,
* tables de hachage
* et un type particulier générique, la S-expression, dont tous les autres types dérivent, rendant possible la méta-programmation, c'est-à-dire la capacité qu'a un programme d'agir sur lui-même.

## Conventions du manuel

L'invite de l'interpréteur est symbolisée ici par scheme>, et varie selon les systèmes utilisés.
Le résultat de l'expression évaluée est imprimée au-dessous en caractères italiques.
Par exemple :
Indique que dans l'interpréteur de commande, on tape « (+ 1 2 3 4 5 6) », et qu'après avoir appuyé sur la touche [↵] ([entrée] ou [retour]) l'interpréteur affiche « 21 ».

## Télécharger un interpréteur Scheme

Plusieurs interpréteurs gratuits existent. On peut par exemple citer :
* Petite Chez Scheme, sous Microsoft Windows 95–XP, MacOS X, Linux sur Intel, FreeBSD sur Intel, Sun OS (la version complète Chez Scheme est payante) ;
* DrScheme, sous Microsoft Windows 95–XP, MacOS X, Linux sur Intel, Sun OS.
* STklos, sous Microsoft Windows NT–XP, MacOS X, Linux 2.2, FreeBSD 4.2, Solaris 8, Irix 6.5.20, Open Darwin 7.0
Voir aussi la FAQ de Schemers.org.

## Documentation

* Michael Sperber et coll., Revised$^6$ Report on the Algorithmic Language Scheme, 2007 (lire en ligne)

# Notions élémentaires

Scheme est un langage de programmation fonctionnelle qui procède de façon algorithmique, c'est-à-dire qu’il établit une méthode propre à la résolution d'un problème en détaillant les étapes de calcul. L'intérêt étant de le rendre utilisable pour toute donnée considérée.

## Expressions élémentaires
### Spécifier

Pour résoudre un problème on devra d’abord spécifier les informations qui entreront en jeu dans sa résolution, à savoir :
* Les données, celles qui sont fournies avant l'exécution du programme et qui serviront de base aux calculs.
* Les résultats que renverront ces calculs.
* Les relations qui lient ces données avec les résultats.

### Désigner

Pour pouvoir faire référence dans le programme à une information ou une valeur prédéfinie on lui attribuera d’abord un nom, généralement en utilisant des lettre (x, y, z...) ou un mot permettant à l'utilisateur de comprendre facilement à quoi il renvoie.

### Typer

Toute information peut être aussi caractérisée par un type, à savoir un domaine de valeur (Z, N, R...) associé à un ensemble d'opérations possibles sur ce domaine (+, -, /...). L'un des intérêt de Scheme est d’être "dynamiquement typé", c'est-à-dire que l'interpréteur n'exigera pas que l’on fournisse le type de chaque information (contrairement à Java par exemple), mais il le "déduira" lui-même au moment de l'exécution selon les opérations effectuées.
* Exemple de définition
* (define n 1) ; n va prendre la valeur 1.

## Notation élémentaire

Tout d’abord le " ; ", il permet d'insérer les commentaires dans un programme : toute la ligne sur la droite ne sera pas considérée par le compilateur, mais il en faut un à chaque ligne.
Scheme utilise la notation préfixée, c'est-à-dire que les opérateurs sont placés devant les opérandes correspondants. Par exemple pour écrire 7+9, en Scheme on écrira :
Les différents opérateurs sont : +, -, *, quotient (division entière), remainder (reste) La comparaison peut se faire avec >, >=, <, <= et =. Ces opérations renverront des booléens, par exemple :
Va renvoyer #f (faux), car 1 n’est pas plus grand que 5.
La différence peut s'exprimer avec le not :
Va renvoyer vrai car 5 est différent de 13.

## Les booléens

* Notation :
Un booléen appartient au domaine B et ne peut prendre que deux valeurs:
Vrai : #t ; (true) Faux : #f ; (false)
* Opérations :
Il est possible d’utiliser les opérateur logiques : and, or et not (et, ou et non).
Ex : On peut exprimer la dualité De Morgan en Scheme, pour rappel ¬(a . b) = ¬a ∨ ¬b et ¬(a ∨ b) = ¬a . ¬b) :
Ce qui donne :
et

## Les caractères

Les caractères sont définis sur le domaine C (l'ensemble des caractères).
* Notation :
    #\a ; un "a"
    #\A ; un "A"
    #\. ; un point (est aussi un caractère)
    #\space ; un espace
    #\newline ; aller à la ligne
* Opérations possibles :
    char>?, char=>?, char<?, char<=? et char=? est utilisé pour comparer deux caractères d’après leur ordre alphabétique. :L'opération renverra un booléen (#t ou #f) selon si la comparaison demandée est vraie ou fausse.
    Par exemple : (char<? #\f #\g) renverra #t, f est plus petit que g dans l’ordre alphabétique.
    Une variante qui ne tient pas compte de la classe (majuscule ou minuscule) est aussi possible:
    char-ci=?, char-ci<?, char-ci>?, char-ci>=?, char-ci<=? .

## Les chaînes

Domaine C$^*$
* Notation :
    On utilise les "" pour exprimer une chaîne : "Voici une chaîne". Attention "a" n’est pas la même chose que #\a, une chaîne peut contenir un seul caractère.
    Pour utiliser un " dans une chaîne on placera un \ devant : "Voici une \"chaîne\"".
    Et pour utiliser un \ il suffira de placer un autre \ devant : "Voici un \\ dans une chaîne".
* Comparaison de chaînes :
    On utilisera string<?, string>?, string=>?, string=<?, string=?
    L'opération renverra un booléen selon la longueur des deux chaînes considérées.
* Concaténation de chaînes :
    Permet de mettre deux chaînes bout à bout grâce à l'opérateur : string-append.
    La ligne suivante renvoie "abracadabra":
    (string-append "abra" "cadabra")

# Syntaxe de base

Un programme Scheme est fait de :
* mots-clefs,
* variables,
* formules structurées,
* constantes (nombres, caractères, chaînes, vecteurs, listes, symboles…),
* espaces, et
* commentaires.
Les variables, symboles et mots-clefs sont appelés « identifiants ».

## Identifiants

Un identifiant peut être composé des caractères suivants :
* lettres minuscules ou capitales ; Scheme n'est pas sensible à la casse pour les identifiants ;
* chiffres ;
* caractères : ? ! . + - * / < = > : $ % ^ & _ ~ @ ;
mais il ne peuvent pas commencer par un chiffre ni par un signe « @ », « . » « + » et « - ».
Les identifiants sont séparés par des espaces, des parenthèses ou des guillemets anglais « " ».

## Nombres

Un nombre est écrit de manière habituelle ; le séparateur décimal est le point. Pour les puissances de 10, on utilise le symbole e : 5·10$^3$ s'écrit 5e3. Les nombres rationnels peuvent être écrits comme des fractions, par exemple 1/3.
Les nombres complexes peuvent être écrits en notation « rectagulaire » (par exemple 1.2+3.4i) ou polaire (par exemple 1,2·e$^{i3,4}$ s'écrit 1.2@3.4). Un imaginaire pur a·i se note toujours 0+ai ; par exemple, i se note 0+1i.
Les valeurs booléennes sont notées #t pour « vrai » (true) et #f pour « faux » (false).

## Autres types

Les caractères seuls doivent être précédés d'un croisillon et d'une barre de fraction inversée « #\ », afin de les distinguer des identifiants. Une chaîne de caractères est simplement mise entre deux guillemets anglais « "…" ».
Un vecteur est introduit par un croisillon suivi d'une parenthèse ouvrante « #( », et se termine par une parenthèse fermante « ) ».
Les formules structurées et les listes de constantes sont mises entre parenthèses « (…) ». La liste vide est notée «  ».
Un commentaire est introduit par un point-virgule « ; » et se termine à la fin de la ligne. Il est d'usage d'utiliser plusieurs points-virgule pour indenter les commentaires, c'est-à-dire les décaler vers la droite et ainsi marquer la correspondance avec l'indentation du reste du code.

## Mots-clefs

Les mots-clefs — c'est-à-dire les noms des opérations primitives, des fonctions prédéfinies — sont des identifiants. Ils sont composés de manière systématique.
Les prédicats (renvoyant des valeurs booléennes) se terminent par un point d'interrogation (par exemple eq?). Les prédicats sur les types de variable sont composés du nom du type suivi du point d'interrogation.
La plupart des procédure s'appliquant aux caractères, chaînes de caractère et vecteurs commencent respectivement par char-, string- et vector-. Les procédures qui convertissent un type en un autre sont de la forme type1->type2.
Les procédures dont la fin a des « effets de bord » se terminent par un point d'exclamation « ! ».

## Références

* ↑ le croisillon « # » est souvent appelé à tort « dièse », mais le dièse est différent : « ♯ »

# Grammaire de base

La base de la programmation Scheme est la définition de procédures.
Une procédure de base est de la forme
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

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 »
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

Pour mettre une expression expr dans une variable var, on utilise define :
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 :
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 :

### 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
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
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 :
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 :

## Exemples
### Opérations sur plusieurs nombres

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

### Opérations imbriquées

    (soit « 1+2×2 » en notation infixée)
    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) :

### Fonction simple

    La fonction double multiplie un nombre par deux :
    Pour l'utiliser :

## 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) | ab |
| (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

À 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
## 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 :
** les variables, notées dans le tableau ci-dessous <var> ;
** les constantes, notées dans le tableau ci-dessous <cst> ;
** les opérations primitives, notées dans le tableau ci-dessous <prm> ;
* deux types de phrases :
** les expressions, notées dans le tableau ci-dessous <exp> ;
** les définitions globales, notées dans le tableau ci-dessous <def>.
Le tableau ci-dessous, inspiré de 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

# La boucle d'évaluation

Sauf exception, tous les systèmes Scheme disposent d'un interpréteur. L'interpréteur fonctionne selon une boucle d'évaluation, appelée REPL, pour read, eval, print, loop.
Dans cette boucle, l'interpréteur :
* R) lit une expression.
* E) évalue (calcule le résultat de) cette expression.
* P) imprime sur la sortie standard le résultat de l'évaluation.
* L) recommence en R).
Un exemple d'évaluation :
La boucle d'évaluation permet d'utiliser le système comme une calculette sophistiquée, de saisir ou tester des expressions relativement simples.
Pour des programmes plus complexes, on utilisera un éditeur de texte capable d'apparier les parenthèses, comme Emacs, et on chargera le code saisi dans l'évaluateur :
    Le source se trouve dans le fichier mon-code.scm

## Manière décrire

Les parenthèses déroutent les débutants en Scheme ou Lisp. Avec un peu d'expérience — et un bon éditeur de texte — on les oublie, on doit les oublier.
Habituellement, le code Scheme se lit et s'écrit selon l'indentation, c'est-à-dire le décalage vers la droite. Habituellement, on met toutes les parenthèses fermantes les unes à la suite des autres, on ne fait pas de diagonales de parenthèses fermantes comme en C++ ou Java ; l'imbrication des blocs est définie par leur seule indentation — les parenthèses sont destinées au compilateur ou à l'interpréteur, la personne qui programme, elle, ne les « voit pas »…

### Exemple
## Voir aussi
### Dans Wikipédia

* Arbre syntaxique abstrait

# Variables globales et variables locales

Les variables (dont les fonctions) définies avec define sont globales, c'est-à-dire qu'elles existent en dehors de l'expression qui les a créées.
Si une variable ne doit être utilisée que dans l'expression et pas ailleurs, il est intéressant de la définir uniquement en local :
* elle ne mobilise pas de place en mémoire une fois l'expression évaluée ;
* on peut réutiliser le nom de la variable ailleurs sans risque de « collision » (cas de noms de variable classiques comme « i », « x », « foo » ou « toto ») ;
* cela facilite la récursivité : un même nom de variable est utilisé à « plusieurs niveaux » et peut avoir une valeur différente à chaque niveau.
Ceci se fait avec l'opération primitive let.

## Définition de variables locales

Si des expressions expr1, expr2, …, expr_n contiennent des variables var1, var2, …, var_n et que l'on veut attribuer des valeurs constantes cst1, cst2, …, cst_n à ces variables, on utilise let :
On a donc une liste de paires (variable constante) suivie d'une liste d'expressions.

### Exemple

    En notation infixée, l'expression donnerait « let x = 1 ; x+1 ».On voit ici que x n'est pas réutilisable en dehors de l'expression.

### Exemple

    En notation infixée, l'expression donnerait « let x = 1 ; let y = 5 ; x+y ».

## Utilisation d'une expression à variables locales

Considérons des expressions faisant intervenir des variables. Si on veut que les valeurs des variables ne soient pas définies dans les expressions elles-mêmes, mais que les variables soient tout de même locales, on utilise lambda. Avec une seule variable var prenant la valeur cst, on a :
Les expressions expr1, …, expr_n peuvent éventuellement être des fonctions globales. Avec n variables var1, var2, …, var_n prenant les valeurs cst1, cst2, …, cst_n :
On peut ainsi définir une procédure locale, en mettant l'expression totale dans une variable avec let :
on n'a ici pour l'opération let qu'une seule paire (variable constante), la variable étant le nom de la fonction et la constante étant la fonction elle-même, les variables de la fonction étant définies avec lambda.

### Exemple
## Voir aussi
### Dans Wikipédia

* Variable locale
* Variable globale

# Récursivité

La récursivité, c'est lorsqu'une procédure s'appelle elle-même. Il faut impérativement prévoir une condition de fin, sans quoi l'appel récursif ne se termine jamais.

## Un exemple simple : la factorielle

Calculons la factorielle d'un entier :
Si l'on fait
en effet, puisque n vaut 0, l'évaluation de (= n 0) est #t, et donc l'évaluation de (if (= n 0) 1 (* n (factorielle (- n 1)))) est « 1 » (première expression suivant le booléen de if).
Si l'on fait
en effet, (= n 0) est #f, c'est la seconde expression suivant le booléen qui est évaluée, soit (* n (factorielle (- n 1))) → (* 1 (factorielle 0)) (en remplaçant n par sa valeur, « 1 »).
Si l'on fait
car au final, on se retrouve à évaluer
    (* 4 (factorielle 3))
    → (* 4 (* 3 (factorielle 2)))
    → (* 4 (* 3 (* 2 (factorielle 1))))
    → (* 4 (* 3 (* 2 (* 1 (factorielle 0)))))
    → (* 4 (* 3 (* 2 (* 1 1)))))
    → 24
on remplace à chaque étape « (factorielle n) » par « (* n factorielle (n-1)) » (en écriture semi-préfixée) jusqu'à arriver à 0, puisque « (factorielle 0) » est remplacé par « 1 ».

## Voir aussi
### Dans Wikipédia

* Récursivité