Aller au contenu

Scheme

Un article de Wikipédia, l'encyclopédie libre.

Scheme
Logo.

Date de première version Voir et modifier les données sur Wikidata
Paradigme Fonctionnel
Auteurs Guy L. Steele et Gerald Jay Sussman
Dernière version R7RS-small ()[1]Voir et modifier les données sur Wikidata
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.orgVoir et modifier les données sur Wikidata
Extension de fichier scm et ssVoir et modifier les données sur Wikidata

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[2] 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.

Gérald Sussman et Guy Steele sont revenus sur la naissance de Scheme dans un article intitulé The First Report on Scheme Revisited[3] 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[note 1], 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

[modifier | modifier le code]

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

[modifier | modifier le code]

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 Revisedn Report on the Algorithmic Language Scheme[note 2], où n est le numéro de la révision, et abrégés en RnRS. 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[2] a été publiée en et ratifiée par 102 personnes, soit 2/3 des votants[4]. Ce rapport est immédiatement controversé, une partie des auteurs des principales implémentations ont indiqué qu’ils intègreraient quelques nouveautés du R6RS, mais pas la totalité du rapport[5], Marc Feeley considère que le but du R6RS ne pourra pas être atteint et qu’il faut travailler sur un nouveau standard.

En 2009, le Scheme Steering Committee a publié un communiqué[4] 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 R5RS, et un large, héritant du R6RS, mais néanmoins compatibles entre eux. Le Steering Committee crée deux groupes de travail pour préparer la nouvelle révision (R7RS) du langage.

La première partie du rapport, dit R7RS-small a été finalisée en [6].

Principales implémentations

[modifier | modifier le code]
  • 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 à R5RS.
  • 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 R5RS utilisable comme langage de script système et interprète de commandes.
  • Gauche est un produit R5RS multilingue sous licence BSD, pour programmeurs et administrateurs systèmes.
  • Bigloo (en) [7] 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

[modifier | modifier le code]

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

[modifier | modifier le code]
  1. Bien que Lisp ait utilisé la notation λ, mais sans savoir gérer les variables libres, le noyau théorique de Lisp reposait sur des équations récursives, et non le λ-calcul.
  2. Que l’on pourrait traduire par : « ne révision du rapport sur le langage algorithmique Scheme ».

Références

[modifier | modifier le code]
  1. a et b « https://small.r7rs.org/ »
  2. a et b (en) Revised⁶ Report on the Algorithmic Language Scheme.
  3. (en) Gerald Jay Sussman et Guy L. Steele, Jr., « The First Report on Scheme Revisited », Higher-Order and Symbolic Computation, vol. 11, no 4,‎ , p. 399-404 (ISSN 1388-3690 et 1573-0557, lire en ligne).
  4. a et b (en) Scheme Steering Committee Position Statement, 20 août 2009, consulté le 26 janvier 2013.
  5. (en) Marc Feeley, « Implementors' intentions concerning R6RS », sur lists.r6rs.org, (consulté le ) : « It seems clear to me that few Scheme implementors have the intention to modify their implementation to support R6RS fully. Generally each implementor intends to pick and choose minor R6RS features that will be supported (but not the same set of features for all Scheme implementations). For this reason I believe that R6RS will fail to achieve its goal of allowing the sharing of code between different Scheme subcommunities. We need to start working on a standard that will. ».
  6. (en) Revised7 Report on the Algorithmic Language Scheme [PDF].
  7. Bigloo chez inria.fr

Sur les autres projets Wikimedia :

Articles connexes

[modifier | modifier le code]

Liens externes

[modifier | modifier le code]