# 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.
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 :
Listes :
Cette concaténation peut être abrégée en
ou en
Fonctions : elles sont définies comme des lambda-expressions
ou plus simplement
Application à une liste :
Évaluations conditionnelles :
et aussi
Exemple 1 - calcul d'une factorielle :
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 :
Versions tail-récursives des deux exemples précédents :

## Mises en œuvre
### R$^n$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$^n$ Report on the Algorithmic Language Scheme, où n est le numéro de la révision, et abrégés en R$^n$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$^6$RS, mais pas la totalité du rapport, Marc Feeley considère que le but du R$^6$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$^5$RS, et un large, héritant du R$^6$RS, mais néanmoins compatibles entre eux. Le Steering Committee crée deux groupes de travail pour préparer la nouvelle révision (R$^7$RS) du langage.
La première partie du rapport, dit R$^7$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 pour Microsoft Windows et plusieurs systèmes Unix
* Chicken est un compilateur Scheme-vers-C.
* Gambit est un compilateur Scheme-vers-C conforme à R$^5$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$^5$RS utilisable comme langage de script système et interprète de commandes.
* Gauche est un produit R$^5$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