Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
Programmation : Introduction à Scheme
(Article écrit par Damien Guichard - février 2004)
|
|
Scheme, ça fonctionne - Partie 1
Présentation du langage Scheme
Le langage Scheme (prononcez "Skim") a été inventé en 1975 au MIT par Guy Lewis Steele Jr. et Gerald Jay Sussman.
Scheme est particulièrement adapté au calcul symbolique, à l'intelligence artificielle, à la recherche en informatique
théorique, tout en étant facile d'apprentissage et agréable pour le débutant en programmation.
Scheme est un dialecte du langage Lisp, sa syntaxe est donc totalement parenthésée, pas de mots-clés, tout commence
par un "(" et tout finit par un ")". Enfin, et c'est probablement le plus important, Scheme privilégie la valeur sur
l'action, le quoi sur le comment, le calcul sur la commande. Scheme est le langage idéal si votre projet calcule
beaucoup, mais éventuellement, ne fait rien ou presque rien.
Installation
Le premier Scheme sur Amiga était Scheme.lha (60921 octets) en juillet 1988.
Et il est encore d'actualité aujourd'hui. Sinon il y a aussi SIOD.lha,
scm.lha et UMBScheme212.lha,
tous disponibles sur Aminet dans le répertoire /Dev/Lang.
Après décompression de l'archive, lancez l'exécutable, une invite apparaît où vous pouvez entrer une expression que Scheme
évaluera. Cette expression est forcément en notation préfixe (opérateur en premier, opérandes ensuite), et complètement
parenthésée, pour calculer 1 + 2 ça donne :
L'invite peut être différente de ":=>" mais normalement le système répond toujours 3.
Le mieux c'est d'exécuter Scheme dans un Shell KingCON.
Pour tester les programmes-exemples il suffit de les copier-coller.
Au commencement
Au commencement il y a la déclaration, elle se fait avec "define" :
On peut vérifier que "one" vaut bien 1 :
"one" est bien une variable, on peut lui affecter une autre valeur à l'aide de "set!" :
Désormais "one" vaut 2.
On peut aussi déclarer des fonctions, ainsi :
|
:=> (define (succ a) (+ a 1) )
|
Déclare la fonction "succ" qui attend un argument "a" et renvoie a+1.
Ensuite, l'application de fonction se fait comme d'habitude, en notation préfixe :
Une autre possibilité indispensable est l'alternative, c'est la fonction "if"
qui renvoie son 2e argument si le premier est vrai, ou renvoie son 3e si le premier est faux.
Exemple, le "minimum de a et b" c'est "a" si "a" est plus petit que "b", et c'est "b" dans le cas contraire :
;; fonction minimum
(define (min a b)
(if (< a b)
a
b
)
)
|
Remarquez bien la façon dont les parenthèses sont alignées sur la même colonne, c'est primordial pour la lisibilité.
Le point-virgule introduit simplement un commentaire.
Le raisonnement
Heureusement, l'intérêt de Scheme est de fournir une approche systématique pour des calculs beaucoup plus poussés.
Par exemple il y a 7 marches d'escalier devant l'allée de mon immeuble, mais combien de façon ai-je donc de les monter ?
Je peux monter 1 marche.
Je peux monter 2 marches et même 3 marches à la fois.
Mais je ne peux pas monter 4 marches en une seule emjambée.
L'astuce c'est que si j'ai déjà monté "n" marches alors il me reste (- 7 n) marches à monter.
Donc la première enjambée laisse au choix 6, 5 ou 4 marches à monter.
Donc le nombre de façons de monter 7 marches c'est le nombre de façons d'en monter 6 plus celui d'en monter 5 plus celui d'en monter 4.
En généralisant le nombre de façons de monter "m" marches c'est le nombre de façons d'en monter (- m 1) plus celui d'en monter (- m 2)
plus celui d'en monter (- m 3).
Ça c'est pour les cas compliqués, pour les cas simples c'est plus facile, à l'évidence il n'y a qu'une façon de monter 1 marche,
2 d'en monter 2 et 4 d'en monter 3.
Ce qui donne :
(define (ways m) ;; nombre de façons de monter
(define res 0)
(if (= m 1) (set! res 1)) ;; 1 marche
(if (= m 2) (set! res 2)) ;; 2 marches
(if (= m 3) (set! res 4)) ;; 3 marches
(if (>= m 4) ;; 4 marches ou plus
(set! res
(+ (+
(ways (- m 1)) ;; m - 1 marches
(ways (- m 2))) ;; m - 2 marches
(ways (- m 3)) ;; m - 3 marches
)
)
)
res
)
|
"res" est simplement une variable qui contient le résultat.
Copiez-collez la fonction, et la réponse tant attendue est :
Soit 44 façons de monter 7 marches.
Le déroulement
La fonction suivante répète "n" fois le bloc "commands".
(define (repeat n commands)
(if (> n 0)
(begin
(commands)
(repeat (- n 1) commands)
)
)
)
|
Maintenant considérons la série (ways m), visiblement le dernier terme de cette série est la somme des 3 précédents.
Nous pouvons donc initialiser 3 variables pour les 3 premières marches, et ensuite boucler jusqu'à la m-ième marche.
(define (ways m)
(define a 1)
(define b 2)
(define c 4)
(define d 0)
(define (body)
(set! d (+ (+ a b) c))
(set! a b)
(set! b c)
(set! c d)
)
(repeat (- m 1) body)
a
)
|
Le "repeat" effectue la boucle désirée.
Le résultat renvoyé est la dernière expression c'est-à-dire "a".
Maintenant que vous êtes curieux, vous voulez savoir combien de façons de monter les 1665 marches de la tour Eiffel ?
La réponse précise, même sur un simple Amiga 500, avec UMB-Scheme :
==> (ways 1665)
270 773 945 474 168 507 366 030 491 331 797 860 998 916 440 277 318 033 085 605 558 227 070 373 433 640 351 632 118 239 429 189 762 538 068 697 145 470 791 366 337 590 212 958 277 117 276 452 112 047 140 005 766 715 744 374 303 716 851 050 049 510 524 848 528 224 380 670 234 481 418 384 182 660 852 282 558 063 573 941 768 154 836 383 150 537 499 569 375 964 262 766 789 131 423 105 692 669 101 899 159 757 352 882 021 997 935 344 411 258 659 448 468 823 147 628 451 733 084 325 501 040 808 298 026 042 870 670 083 623 692 080 825 713 465 449 377 419 946 454 031 884 706 619 237 642 689
|
Eh oui ! Si vous aviez gagné cette somme à la loterie, vous pourriez acheter une fusée pour Alpha du Centaure, et à la bourse
d'Alpha du Centaure vous achèteriez tout l'or de la voie-lactée et assez de briques lego pour construire l'étoile-noire
grandeur nature. Et pour être sûr d'avoir du soleil, vous offririez un milliard d'euros pour chaque grain de sable de Saint-Tropez.
Et encore là j'ai que des idées de radin... Mais je m'égare.
Pour aller plus loin
Après les fonctions pourquoi pas les données ? En attendant un prochain article, voici deux bons textes d'introduction à Scheme :
mitpress.mit.edu/sicp/.
www.scheme.com/tspl2d/index.html.
Plus de documentations sur Scheme :
www.schemers.org/.
www.cs.indiana.edu/scheme-repository/home.html.
www.swiss.ai.mit.edu/projects/scheme/.
|
