Programmation Scheme/Version imprimable

Programmation Scheme

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

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la Licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans Texte de dernière page de couverture. Une copie de cette licence est incluse dans l'annexe nommée « Licence de documentation libre GNU ».

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

Exemple d'interpréteur Scheme : DrScheme sous MacOS X

Exemple d'interpréteur Scheme : Petite Chez sous MacOS X

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 :

scheme> (+ 1 2 3 4 5 6)
⇒ 21

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

1. Les données, celles qui sont fournies avant l'exécution du programme et qui serviront de base aux calculs.
2. Les résultats que renverront ces calculs.
3. 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.

(...) ;Un commentaire sur une ligne
(...) ;Un autre
(...) ;sur trois
(...) ;lignes.

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 :

(+ 7 9)

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 :

(> 1 5)

Va renvoyer #f (faux), car 1 n’est pas plus grand que 5.

La différence peut s'exprimer avec le not :

(not (= 5 13))

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 :

(not(and a b))=(or((not a)(not b))

et

(not (or a b))=(and(not a)(not b))

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³ 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^i 3,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 « ! ».

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

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

(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

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 :

scheme> (+ 1 2 3 4 5 6)
⇒ 21

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 :

scheme> (load "mon-code.scm")

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

Indentation mode C++/Java

( <prm>
   ( <prm>
      ( <prm> … )
   )
)

Indentation mode Scheme

( <prm>
   ( <prm>
      ( <prm> … )))

Exemple

(define (fold-left fonction graine liste)
  (if (null? liste)
      graine
      (fold-left fonction (fonction graine (car liste)) (cdr liste))))

scheme> (fold-left + 0 (list 1 2 3 4 5 6))
⇒ 21

scheme> (fold-left * 1 (list 1 2 3 4 5 6))
⇒ 720

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 :

(let ((var1 cst1) … (var_n cst_n)) expr1 … expr_n)

On a donc une liste de paires (variable constante) suivie d'une liste d'expressions.

Exemple

scheme>(let ((x 1)) (+ x 1)) 
⇒ 2
scheme>(+ x 1)
⇒ Error: variable x is not bound

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

scheme>(let ((x 1)(y 5)) (+ x y) ) 
⇒ 6

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 :

((lambda (var) expr1 … expr_n )(cst))

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 :

((lambda (var1  … var_n) expr1 … expr_n)(cst1 … cst_n))

On peut ainsi définir une procédure locale, en mettant l'expression totale dans une variable avec let :

(let
;;; définition de la fonction
   ((fct (lambda  (var1  … var_n) expr1 … expr_n )))
;;; utilisation de la fonction
   (fct cst1  … cst_n))

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

 (let ((double (lambda  (x) (* 2 x)))) (double 5))
⇒ 10

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 :

(define (factorielle n)
   (if (= n 0)
      1
      (* n (factorielle (- n 1)))))

Si l'on fait

(factorielle 0)
⇒ 1

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

(factorielle 1)
⇒ 1

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

(factorielle 4)
⇒ 24

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é

GFDL

Vous avez la permission de copier, distribuer et/ou modifier ce document selon les termes de la licence de documentation libre GNU, version 1.2 ou plus récente publiée par la Free Software Foundation ; sans sections inaltérables, sans texte de première page de couverture et sans texte de dernière page de couverture.