Aller au contenu

Scheme

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

Page d’aide sur l’homonymie

Pour l’article homonyme, voirscheme.

Scheme
Logo.
Date de première version Voir et modifier les données sur Wikidata
Paradigme Fonctionnel
Auteurs Guy L. SteeleetGerald Jay Sussman
Dernière version R7RS-small ()[1]Voir et modifier les données sur Wikidata
Typage fort, dynamique
Normes IEEE1178-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
modifier

Scheme(prononciation:/skim/) est unlangage de programmationdérivé du langage fonctionnelLisp,créé dans les années 1970 auMassachusetts Institute of Technology(MIT) parGerald Jay SussmanetGuy 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, lanotation préfixéepermet de s'affranchir d'uneprécédence des opérateurs. De plus, la puissance desmacrosde Scheme lui permet de s'adapter à n'importe quel problème, notamment de le rendreorienté objetet donc multi-paradigme.

La spécification de Scheme[2]précise que toutes les implémentations doivent optimiser le cas de larécursion terminale.

Les types de données de base de Scheme sont lesboolé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, laS-expression,dont tous les autres types dérivent, rendant possible lamétaprogrammation,c'est-à-dire la possibilité d'étendre le langage avec de nouveauxopérateurs spéciaux.

Histoire

[modifier|modifier le code]

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 sonmodèle d'acteuret écrit avec ses étudiants une implémentation en Lisp appelée Planner-73, puis PLASMA (acronymedePLAnner-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 desfermeturesdéclarées par le mot cleflambdaet retournant une valeur, et les seconds paralpha.Les acteurs ne retournant pas, mais appellent descontinuations,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èmeITSutilisé à 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 lasé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 à lasémantique opérationnelle.Enfin, la quête d’un langage ultime pour l’intelligence artificielles’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]

Lesvariablessont typées dynamiquement et leur portée estlexicale: 

(definevar1value)

(let([var2value])
...)

Listes: 

(cons1(cons2(cons3(cons4'()))))

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

(list1234)

ou en 

'(1234)

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

(definefun
(lambda(arg1arg2)
...))

ou plus simplement 

(define(funarg1arg2)
...)

Application à une liste: 

(applyfun(listvalue1value2))

Évaluations conditionnelles: 

(cond(test1expr1)
(test2expr2)
...
(elseexprn))

et aussi 

(ifcondition
then-expr
else-expr)

Exemple 1- calcul d'une factorielle: 

(define(factorialn)
(if(=n0)
1
(*n(factorial(-n1)))))

(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(mapflst)
(cond((null?lst)lst)
(else(cons(f(carlst))
(mapf(cdrlst))))))

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

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

(define(factorialn)
(letloop((fact1)
(nn))
(cond((=n0)fact)
(else(loop(*nfact)(-n1))))))

(factorial 5)
;; ⇒ 120

(define(mapflst)
(do((lstlst(cdrlst))
(res'()(cons(f(carlst))res)))
((null?lst)(reverseres))))

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

Mises en œuvre

[modifier|modifier le code]

RnRS

[modifier|modifier le code]

Scheme est, avecCommon 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ésRevisednReport on the Algorithmic Language Scheme[note 2],oùnest le numéro de la révision, et abrégés enRnRS.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 enet 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, leScheme Steering Committeea 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 ditsmall,héritant de IEEE Scheme et du R5RS, et unlarge,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, ditR7RS-smalla été finalisée en[6].

Principales implémentations

[modifier|modifier le code]
  • MIT/GNU Scheme
  • Chez Scheme(en),un interprète Schemelibreet compilateurcommercial[réf. nécessaire]pourMicrosoft Windowset plusieurs systèmes Unix
  • Chicken est un compilateur Scheme-vers-C.
  • Gambit est un compilateur Scheme-vers-C conforme à R5RS.
  • Guileest le langage d'extension duprojet GNU.L'interprète Scheme est unebibliothèquequi 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 deretouche d'imagesGIMPinclut un interprète d'un langage dérivé de Scheme,TinyScheme,pour écrire sous forme descript(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]
Cette section est vide, insuffisamment détaillée ou incomplète.Votre aideest la bienvenue!Comment faire?

Scheme reprend la syntaxe desS-expressionsdeLispen 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 desfermetures;
  • Espace de noms unique pour fonctions et variables: Scheme utilisedefinelà où Lisp choisissait oudefvaroudefun;

Common Lisp vs. Scheme

Notes et références

[modifier|modifier le code]

Notes

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

Références

[modifier|modifier le code]
  1. ↑aetb«https://small.r7rs.org/»
  2. ↑aetb(en)Revised⁶ Report on the Algorithmic Language Scheme.
  3. ↑ (en)Gerald JaySussmanetGuy L.Steele, Jr.,«The First Report on Scheme Revisited»,Higher-Order and Symbolic Computation,vol.11,no4,‎,p.399-404(ISSN1388-3690et1573-0557,lire en ligne).
  4. ↑aetb(en)Scheme Steering Committee Position Statement,20 août 2009, consulté le 26 janvier 2013.
  5. ↑ (en)Marc Feeley, «Implementors' intentions concerning R6RS», surlists.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)Revised7Report on the Algorithmic Language Scheme[PDF].
  7. ↑Bigloochez inria.fr

Voir aussi

[modifier|modifier le code]

Sur les autres projets Wikimedia:

Articles connexes

[modifier|modifier le code]

Liens externes

[modifier|modifier le code]
Ce document provient de «https://fr.wikipedia.org/w/index.php?title=Scheme&oldid=219035636».