Scheme

Introduction

Scheme est un langage de programmation fonctionnel dérivé du langage Lisp (qui signifie "list processing").

Si l'on excepte le langage machine et le langage d'assemblage (ou plus communément « assembleur »), Lisp est le deuxième langage le plus ancien (juste après Fortran) parmi les langages qui se sont largement diffusés. Lisp a beaucoup évolué depuis le début des années 1960 et a ainsi donné naissance à de nombreux dialectes, dont Scheme.

Celui-ci hérite donc de la majorité des caractéristiques de Lisp : le travail sur les données se fait par le biais de liste, sa notation est préfixée, les données sont typées dynamiquement, la gestion de la mémoire se fait automatiquement (contrairement au C par exemple), la métaporgrammation est facilitée (possibilité d'étendre le langage avec de nouveaux opérateurs spéciaux), etc. Scheme de différencie de Lisp de par sa syntaxe épurée et un nombre réduit de mot-clés. Néanmoins cette simplicité n'est pas au détriment de la flexibilité et de la puissance de ce langage.

Finalement on peut noter que la souplesse de ce langage lui permet d'être multiparadigme : on peut en effet le modifier à l'aide de macro pour le rendre orienté objet (par exemple).

Installation

Un certain nombre de programmes existe pour coder du Scheme (voir références). Je vous conseille PLT Scheme, tout bêtement parce que j'ai appris à coder avec celui-ci et qu'il me paraît assez souple et agréable à utiliser. Vous pouvez le télécharger à cette adresse : http://www.plt-scheme.org/, sous download choisissez ensuite "DrScheme".

Prise en main et configuration

Une fois le logiciel installé, vous devriez avoir la fenêtre suivante sous les yeux :

[Image:scheme_interface.png]

Les plages principales sont détaillées sur le schéma : la plage de code (au dessus), l'évaluation de celui-ci (partie inférieure), et le bouton évaluer qui nous permettra d'exécuter le programme.

Mais avant de commencer à coder, il faut régler le niveau de langage utilisé : il est préfèrable de le régler sur "pretty big (assez gros scheme) pour avoir accès à la majorité des fonctions intéressantes. Pour ce faire, il faut aller sous le menu langage (une fenêtre s'ouvre) > faire dérouler les options sous PLT > choisir "assez gros scheme" (ou pour la version anglaise "pretty big scheme".

Nous voici prêts à faire un programme en Scheme!

Concepts de base

Les variables

Les variables sont crées en utilisant le mot-clé "define" :

(define radius 10) 
(define PI 3.14159) 
(define area (* PI radius radius))

Si on tape ces variables dans la console, on aura les résultats suivants :

> area
314.159
> PI
3.14159
> radius
10

REMARQUE : on peut également noter les variables / fonctions / ... à évaluer directement dans la plage de code. Ainsi pour la première instruction, on aurait pu mettre directement :

(define radius 10) 
radius

Et la console nous aurait directement dit :

10

Les opérations mathématiques

Une particularité de Scheme est l'utilisation d'une notation préfixée, c'est-à-dire que les opérateurs seront au début de l'expression mathématique. Par exemple, au lieu d'écrire (2 + 9) nous allons écrire (+ 2 9). Cela peut sembler peu naturel mais on prend assez vite l'habitude.

Comme le résume le tableau suivant, nous avons l'habitude d'utiliser une notation "infix", Scheme utilise une notation "prefix" et d'autres programmes utilisent une notation "postfix" :

Infix	Postfix	Prefix	Notes
A * B + C / D	A B * C D / +	+ * A B / C D	multiplie A et B, divise C par D, additionne le résultat
A * (B + C) / D	A B C + * D /	/ * A + B C D	additionne B et C, multiplié par A, divisé par D
A * (B + C / D)	A B C D / + *	* A + B / C D	divise C par D, additionne B, multiplie par A

En Scheme, il existe parmi les fonctions de base les opérateurs suivants : +,- ,*,/

> (* 3 3)
9
> (/ 9 3)
3

Mais aussi des fonctions plus poussées comme :

> (sqrt 81)
9
> (expt 4 2)
16
> (remainder 9 2)
1

Pour avoir la liste exhaustive des opérateurs je vous conseille de fouiller dans la documentation.

Les procédures

Les opérations qui se répètent peuvent être nommées et définies dans une procédure. Par exemple, si on veut définir une procédure qui calcule l'aire d'un cercle :

(define (circle-area r) (* pi r r))

NOTE : define peut ainsi être utilisé pour construire des variables, mais également des procédures!

La syntaxe d'une telle procédure se définit ainsi :

(define (<name> <par-list>) <body>)

où

<par-list> ::= empty | <par> <par-list> 
<body> ::= <expression> | <expression> <body>

la liste de paramètre peut être vide ou contenir un nombre indéfini de paramètre, et le body peut être constitué d'une ou plusieurs expressions.

Les commentaires

Comme dans tout langage de programmation, il existe deux types de commentaire. Le commentaire sur une ligne :

;;je suis un commentaire sur une ligne

#|
je suis un commentaire
sur plusieurs lignes
|#

Conditions et booléens

En scheme, les fonctions qui retournent un booléen (vrai ou faux, ou #t ou #f) sont appelés "predicates". Exemples :

> (= 9 9)
#t
> (< 7 3)
#f
> (> 7 3)
#t
> (>= 8 8)
#t

Il est ensuite possible de combiner ces "predicates" avec des mots-clés logiques tels que "and", "or" ou "not" :

> (and (< 1 2) (= 4 4))
#t
> (or (= 1 1) (= 2 3))
#t
> (not (> 1 999))
#t

La forme spéciale "cond" (équivalente aux "if" des langages conventionnels) permet de tester une prédiction pour ensuite renvoyer une valeur :

(cond 
((< n 10) 0) 
((< n 20) 5) 
(else 10))

Ici si n est plus petit que 10, la valeur renvoyée sera 0, s'il est entre 10 et 20 on renverra 5, et sinon 10.

REMARQUE : il est tout à fait possible d'utiliser le mot-clé "if" à la place de "cond". C'est d'ailleurs ce que je vais faire dans la suite de cet article, pour garder une certaine cohérence avec les autres langages de programmation.

Exercices : votre premier programme

A présent vous avez assez de connaissance pour construire votre premier programme. Essayez de réfléchir un peu avant de regarder les réponses.

• Tout d'abord imaginez un programme (appelé "max-value") qui, entre deux chiffres, renvoie le plus grand. Exemple :

;; Résultats attendus :
;; (max-value 5 6) = 6
;; (max-value 5 5) = 5

'réponse'

(define (max-value a b)
  (if (> a b) 
      a 
      b))

• Puis prévoyez un progamme (appelé max-value-3) qui aura la même fonction que la procédure précédente, sauf qu'il prendra 3 chiffres en paramètres.
  • astuce : il est tout à fait possible de réutiliser votre exercice précédent!

;; Résultats attendus :
;; (max-value-3 5 6 7) = 7 
;; (max-value-3 5 7 7) = 7 
;; (max-value-3 7 7 7) = 7

'réponse'

(define (max-value-3 a b c)
  (max-value (max-value a b) c))

• Finalement écrivez une procédure (appelée median) qui choisira le médian de trois chiffres (donc celui qui se trouve au milieu).

;; Résultats attendus :
;; (median 5 6 7) = 6 
;; (median 5 7 7) = 7 
;; (median 7 7 7) = 7

'réponse'

(define (median a b c)
  (cond ((= (max-value-3 a b c) a) (max-value b c))
        ((= (max-value-3 a b c) b) (max-value a c))
        (else (max-value a b)))) 

'attention!' : le bout de code suivant, même s'il marche, est un exemple typique de mauvaise programmation!

(define (median-2 a b c)
  (cond ((and (<= a b) (<= b c)) b)
        ((and (<= a c) (<= c b)) c)
        ((and (<= b a) (<= a c)) a)
        ((and (<= b c) (<= c a)) c)
        ((and (<= c a) (<= a b)) a)
        ((and (<= c b) (<= b a)) b)))

Les chaînes de caractères

Les chaînes de caractères (ou string) sont définies de la manière suivante :

(define prenom 'Bertrand)

Les listes

L'unité de base la plus utilisée en scheme est la paire, construite avec le mot-clé "cons" :

>(cons12) 
(1 . 2) 
>(cons ’a ’b) 
(a . b) 
>(define p (cons ’geneve ’ge)) 
>p 
(geneve . ge)

Des opérateurs spécialisés nous permettent d'accéder aux éléments de la paire :

>(first p) 
geneve
>(rest p) 
ge

MAIS (et c'est là que ça se complique), un élément d'une paire peut également être une paire! Exemple :

>(cons ’mars (cons ’earth (cons ’venus ’mercur))) 
(mars earth venus . mercur)

ET une liste définit comme une paire (ou une série de paire) qui se termine par un élément vide () :

>(cons ’mars (cons ’earth (cons ’venus (cons ’mercur ()))))
(mars earth venus mercur)

Pour se faciliter la vie, il est possible d'utiliser le mot-clé "list" afin d'éviter une construction laborieuse de "cons". Exemple :

>(define l (list ’mars ’earth ’venus ’mercur)) 
>l 
(mars earth venus mercur) 

IMPORTANT : on accède aux éléments de la liste de la même manière qu'avec une paire!

>(first (rest l)) 
earth 
>(rest (rest l)) 
(venus mercur) 
>(first (rest (rest l))) 
venus

Mises en œuvre

Scheme est, avec Common Lisp, le Lisp le plus populaire. Le langage est défini par le document R6RS (Revised⁶ Report on the Algorithmic Language Scheme : Sixième révision du rapport sur le langage algorithmique Scheme).

Les principales implémentations de Scheme sont:

• Chez Scheme, un interpréteur Scheme gratuit et compilateur commercial pour Microsoft Windows et plusieurs systèmes Unix
• Chicken est compilateur Scheme-vers-C.
• Gambit est un compilateur Scheme-vers-C conforme à R5RS.
• Guile est le langage d'extension du projet GNU. L'interpréteur Scheme est une bibliothèque qui peut servir comme langage de script pour des applications.
• PLT Scheme, une suite de programmes incluant un interpréteur (MzScheme), un outil de développement graphique(MrEd), un éditeur orienté pédagogie (DrScheme), et divers composants incluant des bibliothèques Component object model (COM) et ODBC.
• Scsh ou Scheme Shell est un produit R5RS utilisable comme langage de script système et interpréteur de commandes.
• Gauche est un produit R5RS multilingue sous licence BSD, pour programmeurs et administrateurs systèmes.
• Bigloo est un compilateur Scheme-vers-C et Scheme-vers-Java qui produit des exécutables compacts et rapides, doté d'un nombre relativement important de bibliothèques.
• STklos est un produit libre du langage Scheme de l'Université de Nice qui est légère et efficace.
• Le logiciel de retouche d'images Gimp inclut un interpréteur d'un langage dérivé de Scheme, SIOD (Scheme In One Defun) pour scripter (appelé script-fu) certaines manipulations d'image.
• D'autres produits se trouvent sur la schemers.org FAQ

Liens externes

• Le standard Scheme.
• Une collection de ressources.
• Scheme Requests for Implementation (SRFI)
• « Structure and Interpretation of Computer Programs » Abelson et Sussman. Un cours d'exceptionnelle qualité, avec vidéo en ligne[1]. Ce livre dépasse le cadre de l'enseignement du langage, et enseigne les fondements des langages de programmation. Sert de support de cours depuis de nombreuses années au MIT.
• How to Design Programs. Autre cours de Scheme.
• Teach Yourself Scheme. Un autre cours, destiné aux débutants.
• The Scheme Programming Language écrit par R. Kent Dybvig.
• Une bibliothèque d'articles de recherche donne des liens vers les articles originaux qui ont donné naissance au langage.
• Cours de Scheme Quelques cours de scheme basés sur les cours donnés en 1Modèle:Re année de deug mias
• Cours de scheme en video par Abelson & Sussman du MIT