Scheme

Scheme (prononciation : /skim/) est un langage de programmation dérivé du langage fonctionnel Lisp, créé dans les années 1970 au Massachusetts Institute of Technology (MIT) par Gerald Jay Sussman et Guy L. Steele.

Scheme
Date de première version	1975
Paradigme	Fonctionnel
Auteurs	Guy L. Steele et Gerald Jay Sussman
Dernière version	R7RS-small (2013)
Typage	fort, dynamique
Normes	IEEE 1178-1990, ANSI, RnRS
Influencé par	Lisp
A influencé	JavaScript, Ruby, Hop, Snap!
Implémentations	Bigloo, Gambit, PLT Scheme…
Site web	www.scheme-reports.org
Extension de fichier	scm et ss

Le but des créateurs du langage était d'épurer le 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és. Comme en Lisp, la notation préfixée permet de s'affranchir d'une précédence des opérateurs. De plus, la puissance des macros de Scheme lui permet 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 implémentations 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étaprogrammation, c'est-à-dire la possibilité d'étendre le langage avec de nouveaux opérateurs spéciaux.

Histoire

Gérald Sussman et Guy Steele sont revenus sur la naissance de Scheme dans un article intitulé The First Report on Scheme Revisited et publié en 1998.

En 1973, Carl Hewitt propose son modèle d'acteur et écrit avec ses étudiants une implémentation en Lisp appelée Planner-73, puis PLASMA (acronyme de PLAnner-like System Modeled on Actors). Sussman et Steele voulant mieux comprendre le modèle d’Hewitt, notamment en le reliant aux notions traditionnelles de la programmation, écrivent un petit interprète Lisp et des primitives pour créer des acteurs et envoyer des messages entre eux. Ils utilisent la même syntaxe pour les fonctions et les acteurs, les premières étant des fermetures déclarées par le mot clef lambda et retournant une valeur, et les seconds par alpha. Les acteurs ne retournant pas, mais appellent des continuations, qui sont les autres acteurs qu’il connait.

Le langage est nommé « Schemer », suivant le nommage des langages Planner et Conniver, desquels il s’inspire. Cependant, le système ITS utilisé à l’époque limite les noms de fichiers à 6 caractères, tronquant le nom à « SCHEME ». Sussman et Steele disent ne plus se souvenir de pourquoi ils n’ont pas choisi d’abréger en « SCHMR », comme Planner et Conniver qui utilisaient « PLNR » et « CNVR ».

Ils découvrent, après avoir écrit des programmes avec des acteurs, que l’implémentation de l’interprète était identique, que le code à évaluer concerne des fonctions ou des acteurs, et qu’il en était de même pour le code qui crée les fonctions et acteurs. La différence entre le fait que seules les fonctions retournent des valeurs et pas les acteurs n’existait pas dans l’implémentation, mais seulement dans les primitives utilisées dans le corps des définitions des fonctions et acteurs. Ils en déduisent que les acteurs et les fermetures sont en fait le même concept, et Hewitt l’a lui-même admis plus tard.

Ces découvertes sur l’embryon qu’était alors Scheme ont mené à trois conclusions majeures. En premier lieu, le modèle d’acteur d’Hewitt se représentait parfaitement en λ-calcul. Ce n’était pas nouveau en soi pour les théoriciens de la sémantique dénotationnelle, mais Scheme a permis d’apporter une dimension pratique à ces théories. Ensuite, il est apparu que le formalisme simple et petit du λ-calcul peut servir à un noyau d’un langage de programmation expressif et puissant, Scheme est donc un λ-calcul appliqué. Le corollaire est immédiat : la sémantique dénotationnelle est équivalente à la sémantique opérationnelle. Enfin, la quête d’un langage ultime pour l’intelligence artificielle s’est révélée tourner en rond, puisque les travaux sur les langages ont commencé par Lisp, suivi de CONVERT, puis Planner, Conniver, PLASMA, lui-même suivi par un dialecte simplifié de Lisp.

Aperçu de la syntaxe du langage

Les variables sont typées dynamiquement et leur portée est lexicale :

 (define var1 value)

  (let ([var2 value])
    ...)

Listes :

  (cons 1 (cons 2 (cons 3 (cons 4 '()))))

Cette concaténation peut être abrégée en

  (list 1 2 3 4)

ou en

  '(1 2 3 4)

Fonctions : elles sont définies comme des lambda-expressions

  (define fun
    (lambda (arg1 arg2)
       ...))

ou plus simplement

  (define (fun arg1 arg2)
    ...)

Application à une liste :

  (apply fun (list value1 value2))

Évaluations conditionnelles :

  (cond (test1 expr1)
        (test2 expr2)
        ...
        (else exprn))

et aussi

  (if condition
        then-expr
        else-expr)

Exemple 1 - calcul d'une factorielle :

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

 (factorial 5)
 ;; ⇒ 120

Exemple 2 - définition d'une fonction map, qui applique une lambda-expression (qui élève son argument au carré) à tous les éléments d'une liste :

  (define (map f lst)
    (cond ((null? lst) lst)
          (else (cons (f (car lst))
                      (map f (cdr lst))))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;;  ⇒ (1 4 9 16)

Versions tail-récursives des deux exemples précédents :

  (define (factorial n)
    (let loop ((fact 1)
               (n n))
      (cond ((= n 0) fact)
            (else (loop (* n fact) (- n 1))))))

 (factorial 5)
 ;; ⇒ 120

  (define (map f lst)
    (do ((lst lst (cdr lst))
         (res '() (cons (f (car lst)) res)))
        ((null? lst) (reverse res))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;; ⇒ (1 4 9 16)

Mises en œuvre

RⁿRS

Scheme est, avec Common Lisp, le dialecte de Lisp le plus populaire. Comme Lisp, il existe de multiples implémentations chacune ajoutant des fonctionnalités en fonction des besoins de leurs utilisateurs. Un rapport fait régulièrement le point sur les différentes implémentations, afin de dégager une définition du langage consensuelle. Ces rapports sont nommés Revisedⁿ Report on the Algorithmic Language Scheme, où n est le numéro de la révision, et abrégés en RⁿRS. Leur but est de pouvoir échanger du code entre différentes implémentations conformes à une révision donnée du rapport.

La sixième révision a été publiée en septembre 2007 et ratifiée par 102 personnes, soit 2/3 des votants. Ce rapport est immédiatement controversé, une partie des auteurs des principales implémentations ont indiqué qu’ils intègreraient quelques nouveautés du R⁶RS, mais pas la totalité du rapport, Marc Feeley considère que le but du R⁶RS ne pourra pas être atteint et qu’il faut travailler sur un nouveau standard.

En 2009, le Scheme Steering Committee a publié un communiqué dans lequel il rappelle la diversité des implémentations de Scheme, qui sont à la fois sa faiblesse et sa force. Il annonce que la diversité actuelle justifie la distinction entre deux langages Scheme, l’un dit small, héritant de IEEE Scheme et du R⁵RS, et un large, héritant du R⁶RS, mais néanmoins compatibles entre eux. Le Steering Committee crée deux groupes de travail pour préparer la nouvelle révision (R⁷RS) du langage.

La première partie du rapport, dit R⁷RS-small a été finalisée en juillet 2013.

Principales implémentations

• MIT/GNU Scheme
• Chez Scheme (en), un interprète Scheme libre et compilateur commercial^{[réf. nécessaire]} pour Microsoft Windows et plusieurs systèmes Unix
• Chicken est un compilateur Scheme-vers-C.
• Gambit est un compilateur Scheme-vers-C conforme à R⁵RS.
• Guile est le langage d'extension du projet GNU. L'interprète Scheme est une bibliothèque qui peut servir comme langage de script pour des applications.
• Racket, anciennement PLT-Scheme, une suite de programmes incluant un interprète (racket), un outil de développement graphique (MrEd), un éditeur orienté pédagogie (DrRacket), et divers composants incluant des bibliothèques Component object model (COM) et ODBC.
• Kawa est une implémentation de Scheme en Java.
• Scsh ou Scheme Shell est un produit R⁵RS utilisable comme langage de script système et interprète de commandes.
• Gauche est un produit R⁵RS multilingue sous licence BSD, pour programmeurs et administrateurs systèmes.
• Bigloo (en) 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 une implémentation libre du langage Scheme de l'Université de Nice qui est légère et efficace.
• Elk est une implémentation libre du langage.
• Le logiciel de retouche d'images GIMP inclut un interprète d'un langage dérivé de Scheme, TinyScheme, pour écrire sous forme de script (appelé script-fu) certaines manipulations d'image.
• D'autres produits se trouvent sur la schemers.org FAQ

Différences avec Lisp

Scheme reprend la syntaxe des S-expressions de Lisp en changeant quelques mots clefs. Une expression scheme est soit une valeur atomique (nombre, chaîne de caractères, identificateur, etc.), soit une liste d’expressions. Les différences notables avec Lisp sont :

• Portée lexicale à travers des fermetures ;
• Espace de noms unique pour fonctions et variables : Scheme utilise define là où Lisp choisissait ou defvar ou defun ;

Common Lisp vs. Scheme

Notes et références

Voir aussi

Articles connexes

• SRFI
• GNU Guile
• OCaml

Liens externes

• (fr) Une courte introduction à Scheme. Notes de cours, Jean-Jacques Girardot, Ecole Nationale Supérieure des Mines de Saint-Etienne, 2008.
• (en) The Scheme Programming Language écrit par R. Kent Dybvig.
• (en) Collection de ressources.
• (en) MIT Scheme. Présentation de l'implémentation MIT/GNU et liens vers d'autres ressources.