Schéma (langage de programmation) - Scheme (programming language)

Schème

Paradigmes	Multi-paradigme : fonctionnel , impératif , méta
Famille	Zézayer
Conçu par	Guy L. Steele et Gerald Jay Sussman
Première apparition	1975 ; il y a 46 ans ( 1975 )
Version stable	R7RS / 2013 ; il y a 8 ans ( 2013 )
Discipline de frappe	Dynamique , latent , fort
Portée	Lexical
Extensions de nom de fichier	.scm, .ss
Site Internet	www .scheme-reports .org
Les principales mises en œuvre
Beaucoup (voir Implémentations de schéma )
Influencé par
ALGOL , Lisp , MDL
Influencé
Clojure , Common Lisp , Dylan , EuLisp , Haskell , Hop , JavaScript , Julia , Lua , MultiLisp , R , Raquette , Ruby , Rust , S , Scala , T
Schéma sur Wikibooks

Scheme est un dialecte minimaliste de la famille Lisp des langages de programmation . Scheme se compose d'un petit noyau standard avec plusieurs outils pour l'extension du langage.

Scheme a été créé dans les années 1970 au MIT AI Lab et publié par ses développeurs, Guy L. Steele et Gerald Jay Sussman , via une série de mémos maintenant connus sous le nom de Lambda Papers . C'était le premier dialecte de Lisp à choisir une portée lexicale et le premier à nécessiter des implémentations pour effectuer une optimisation d'appel de queue , offrant un support plus fort pour la programmation fonctionnelle et les techniques associées telles que les algorithmes récursifs. C'était également l'un des premiers langages de programmation à prendre en charge les continuations de première classe . Il a eu une influence significative sur l'effort qui a conduit au développement de Common Lisp .

Le langage Scheme est standardisé dans la norme officielle IEEE et une norme de facto appelée Rapport ⁿ révisé sur le schéma de langage algorithmique (R n RS). La norme la plus largement appliquée est R5RS (1998). La norme la plus récente, R7RS, fournit des versions « petites » et « grandes » du langage Scheme ; la "petite" norme de langage a été ratifiée en 2013. Scheme a une base d'utilisateurs diversifiée en raison de sa compacité et de son élégance, mais sa philosophie minimaliste a également causé de grandes divergences entre les implémentations pratiques, à tel point que le Scheme Steering Committee l'appelle "le plus langage de programmation non portable" et "une famille de dialectes" plutôt qu'un seul langage.

Histoire

Origines

Scheme a commencé dans les années 1970 comme une tentative de comprendre Carl Hewitt du modèle de l' acteur , à cet effet , Steele et Sussman a écrit un « petit interprète Lisp » à l' aide Maclisp puis « mécanismes supplémentaires pour la création d' acteurs et d' envoyer des messages ». Scheme s'appelait à l'origine "Schemer", dans la tradition d'autres langages dérivés de Lisp tels que Planner ou Conniver . Le nom actuel résulte de l'utilisation par les auteurs du système d'exploitation ITS , qui limitait les noms de fichiers à deux composants d'au plus six caractères chacun. Actuellement, "Schemer" est couramment utilisé pour désigner un programmeur Scheme.

R6RS

Un nouveau processus de normalisation du langage a commencé lors de l'atelier Scheme de 2003, dans le but de produire une norme R6RS en 2006. Ce processus a rompu avec l' approche précédente R n RS de l'unanimité.

R6RS dispose d'un système de modules standard, permettant une séparation entre le langage de base et les bibliothèques. Un certain nombre d'ébauches de la spécification R6RS ont été publiées, la version finale étant la R5.97RS. Un vote réussi a abouti à la ratification de la nouvelle norme, annoncée le 28 août 2007.

Actuellement, les dernières versions de diverses implémentations de Scheme prennent en charge la norme R6RS. Il existe une implémentation de référence portable des bibliothèques à phases implicites proposées pour R6RS, appelée psyntax, qui se charge et s'amorce correctement sur diverses implémentations plus anciennes de Scheme.

Une caractéristique de R6RS est le descripteur de type d'enregistrement (RTD). Lorsqu'un RTD est créé et utilisé, la représentation du type d'enregistrement peut afficher la disposition de la mémoire. Il a également calculé le masque de bits de champ d'objet et les masques de bits de champ d'objet de schéma mutable, et a aidé le ramasse-miettes à savoir quoi faire avec les champs sans parcourir toute la liste des champs qui sont enregistrés dans le RTD. RTD permet aux utilisateurs d'étendre le RTD de base pour créer un nouveau système d'enregistrement.

R6RS introduit de nombreux changements significatifs dans la langue. Le code source est désormais spécifié en Unicode , et un grand sous-ensemble de caractères Unicode peut désormais apparaître dans les symboles et identificateurs Scheme , et il y a d'autres changements mineurs aux règles lexicales. Les données de caractères sont également désormais spécifiées en Unicode. De nombreuses procédures standard ont été déplacées vers les nouvelles bibliothèques standard, qui elles-mêmes forment une grande extension de la norme, contenant des procédures et des formes syntaxiques qui ne faisaient pas auparavant partie de la norme. Un nouveau système de modules a été introduit et les systèmes de gestion des exceptions sont désormais standardisés. Les règles de syntaxe ont été remplacées par une facilité d'abstraction syntaxique plus expressive (cas de la syntaxe) qui permet l'utilisation de tout Scheme au moment de l'expansion des macros. Des implémentations conformes sont désormais nécessaires pour prendre en charge la tour numérique complète de Scheme , et la sémantique des nombres a été étendue, principalement dans le sens de la prise en charge de la norme IEEE 754 pour la représentation numérique à virgule flottante.

R7RS

La norme R6RS a suscité la controverse car elle semble s'être écartée de la philosophie minimaliste. En août 2009, le Scheme Steering Committee, qui supervise le processus de normalisation, a annoncé son intention de recommander de scinder Scheme en deux langages : un grand langage de programmation moderne pour les programmeurs ; et une petite version, un sous-ensemble de la grande version conservant le minimalisme loué par les éducateurs et les exécutants occasionnels. Deux groupes de travail ont été créés pour travailler sur ces deux nouvelles versions de Scheme. Le site Scheme Reports Process contient des liens vers les chartes des groupes de travail, les discussions publiques et le système de suivi des problèmes.

Le neuvième projet de R7RS (petit langage) a été rendu disponible le 15 avril 2013. Un vote ratifiant ce projet s'est clôturé le 20 mai 2013, et le rapport final est disponible depuis le 6 août 2013, décrivant « le 'petit' langage de cet effort : il ne peut donc pas être considéré isolément comme le successeur du R6RS ».

Caractéristiques distinctives

Scheme est avant tout un langage de programmation fonctionnel . Il partage de nombreuses caractéristiques avec d'autres membres de la famille des langages de programmation Lisp. La syntaxe très simple de Scheme est basée sur des s-expressions , des listes entre parenthèses dans lesquelles un opérateur préfixe est suivi de ses arguments. Les programmes de schéma sont ainsi constitués de séquences de listes imbriquées. Les listes sont également la principale structure de données dans Scheme, ce qui conduit à une équivalence étroite entre le code source et les formats de données ( homoiconicité ). Les programmes Scheme peuvent facilement créer et évaluer dynamiquement des morceaux de code Scheme.

Le recours aux listes en tant que structures de données est partagé par tous les dialectes Lisp. Scheme hérite d'un riche ensemble de primitives de traitement de liste telles que cons, caretcdr de ses ancêtres Lisp. Scheme utilise des variables de type strict mais dynamique et prend en charge les procédures de première classe . Ainsi, les procédures peuvent être affectées en tant que valeurs à des variables ou passées en tant qu'arguments aux procédures.

Cette section se concentre principalement sur les fonctionnalités innovantes du langage, y compris les fonctionnalités qui distinguent Scheme des autres Lisps. Sauf indication contraire, les descriptions des fonctionnalités se rapportent à la norme R5RS.

Dans les exemples fournis dans cette section, la notation "===> résultat" est utilisée pour indiquer le résultat de l'évaluation de l'expression sur la ligne immédiatement précédente. C'est la même convention utilisée dans R5RS.

Caractéristiques de conception fondamentales

Cette sous-section décrit les fonctionnalités de Scheme qui l'ont distingué des autres langages de programmation depuis ses débuts. Ce sont les aspects de Scheme qui influencent le plus fortement tout produit du langage Scheme, et ce sont les aspects que toutes les versions du langage de programmation Scheme, à partir de 1973, partagent.

Minimalisme

Scheme est un langage très simple, beaucoup plus facile à mettre en œuvre que de nombreux autres langages de puissance expressive comparable . Cette facilité est attribuable à l'utilisation du calcul lambda pour dériver une grande partie de la syntaxe du langage à partir de formes plus primitives. Par exemple, sur les 23 constructions syntaxiques basées sur l'expression s définies dans la norme R5RS Scheme, 14 sont classées comme formes dérivées ou de bibliothèque, qui peuvent être écrites comme des macros impliquant des formes plus fondamentales, principalement lambda. Comme le dit R5RS (§3.1) : "La plus fondamentale des constructions de liaison variable est l'expression lambda, car toutes les autres constructions de liaison variable peuvent être expliquées en termes d'expressions lambda."

Formes fondamentales : define, lambda, quote, if, define-syntax, let-syntax, letrec-syntax, syntax-rules, set !

Formes dérivées : do, let, let*, letrec, cond, case, and, or, begin, nommé let, delay, unquote, unquote-splicing, quasiquote

Exemple : une macro à implémenter leten tant qu'expression à utiliser lambdapour effectuer les liaisons de variables.

(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))))

Ainsi, utiliser letcomme défini ci-dessus une implémentation de Scheme réécrirait " (let ((a 1)(b 2)) (+ b a))" en tant que " ((lambda (a b) (+ b a)) 1 2)", ce qui réduit la tâche de l'implémentation à celle de coder les instanciations de procédure.

En 1998, Sussman et Steele ont remarqué que le minimalisme de Scheme n'était pas un objectif de conception conscient, mais plutôt le résultat involontaire du processus de conception. « Nous essayions en fait de construire quelque chose de compliqué et avons découvert, par hasard, que nous avions accidentellement conçu quelque chose qui atteignait tous nos objectifs mais était beaucoup plus simple que nous l'avions prévu... nous avons réalisé que le calcul lambda - un petit formalisme simple - pourrait servir de noyau à un langage de programmation puissant et expressif."

Portée lexicale

Comme la plupart des langages de programmation modernes et contrairement aux Lisps antérieurs tels que Maclisp , Scheme a une portée lexicale : toutes les liaisons de variables possibles dans une unité de programme peuvent être analysées en lisant le texte de l'unité de programme sans tenir compte des contextes dans lesquels elle peut être appelée. Cela contraste avec la portée dynamique qui était caractéristique des premiers dialectes Lisp, en raison des coûts de traitement associés aux méthodes de substitution textuelle primitives utilisées pour implémenter les algorithmes de portée lexicale dans les compilateurs et les interprètes de l'époque. Dans ces Lisps, il était parfaitement possible qu'une référence à une variable libre à l' intérieur d'une procédure fasse référence à des liaisons bien distinctes externes à la procédure, selon le contexte de l'appel.

L'impulsion pour incorporer la portée lexicale, qui était un modèle de portée inhabituel au début des années 1970, dans leur nouvelle version de Lisp, est venue des études de Sussman sur ALGOL . Il a suggéré que les mécanismes de portée lexicale de type ALGOL aideraient à réaliser leur objectif initial d'implémenter le modèle d'acteur de Hewitt dans Lisp.

Les idées clés sur la façon d'introduire la portée lexicale dans un dialecte Lisp ont été popularisées dans le Lambda Paper de 1975 de Sussman et Steele, "Scheme: An Interpreter for Extended Lambda Calculus", où ils ont adopté le concept de la fermeture lexicale (à la page 21), qui avait été décrit dans un AI Memo en 1970 par Joel Moses , qui a attribué l'idée à Peter J. Landin .

Calcul lambda

La notation mathématique d' Alonzo Church , le calcul lambda, a inspiré l'utilisation par Lisp de "lambda" comme mot-clé pour introduire une procédure, ainsi qu'influencer le développement de techniques de programmation fonctionnelle impliquant l'utilisation de fonctions d'ordre supérieur dans Lisp. Mais les premiers Lisps n'étaient pas des expressions appropriées du calcul lambda en raison de leur traitement des variables libres .

Un système lambda formel a des axiomes et une règle de calcul complète. Il est utile pour l'analyse utilisant la logique et les outils mathématiques. Dans ce système, le calcul peut être vu comme une déduction directionnelle. La syntaxe du lambda calcul suit les expressions récursives de x, y, z, ..., les parenthèses, les espaces, le point et le symbole λ. La fonction du calcul lambda comprend : Premièrement, servir de point de départ à une puissante logique mathématique. Deuxièmement, cela peut réduire la nécessité pour les programmeurs de considérer les détails de la mise en œuvre, car il peut être utilisé pour imiter l'évaluation de la machine. Enfin, le calcul lambda a créé une méta-théorie substantielle.

L'introduction de la portée lexicale a résolu le problème en faisant une équivalence entre certaines formes de notation lambda et leur expression pratique dans un langage de programmation fonctionnel. Sussman et Steele ont montré que le nouveau langage pouvait être utilisé pour dériver avec élégance toute la sémantique impérative et déclarative d'autres langages de programmation, y compris ALGOL et Fortran , et la portée dynamique d'autres Lisps, en utilisant des expressions lambda non pas comme de simples instanciations de procédure mais comme « contrôle structures et modificateurs d'environnement". Ils ont introduit le style de continuation-passage avec leur première description de Scheme dans le premier des articles Lambda, et dans les articles suivants, ils ont commencé à démontrer la puissance brute de cette utilisation pratique du calcul lambda.

Structure de bloc

Scheme hérite de sa structure par blocs des langages structurés par blocs antérieurs, en particulier ALGOL . Dans Scheme, les blocs sont implémentés par trois constructions de liaison : let, let*et letrec. Par exemple, la construction suivante crée un bloc dans lequel un symbole appelé varest lié au nombre 10 :

(define var "goose")
;; Any reference to var here will be bound to "goose"
(let ((var 10))
  ;; statements go here.  Any reference to var here will be bound to 10.
  )
;; Any reference to var here will be bound to "goose"

Les blocs peuvent être imbriqués pour créer des structures de blocs arbitrairement complexes en fonction des besoins du programmeur. L'utilisation de la structuration par blocs pour créer des liaisons locales atténue le risque de collision d'espaces de noms qui pourrait autrement se produire.

Une variante de let, let*, permet aux liaisons de faire référence à des variables définies précédemment dans la même construction, ainsi :

(let* ((var1 10)
       (var2 (+ var1 12)))
  ;; But the definition of var1 could not refer to var2
  )

L'autre variante, letrec, est conçue pour permettre de lier entre elles des procédures récursives entre elles.

;; Calculation of Hofstadter's male and female sequences as a list of pairs

(define (hofstadter-male-female n)
  (letrec ((female (lambda (n)
		     (if (= n 0)
			 1
			 (- n (male (female (- n 1)))))))
	   (male (lambda (n)
		   (if (= n 0)
		       0
		       (- n (female (male (- n 1))))))))
    (let loop ((i 0))
      (if (> i n)
	  '()
	  (cons (cons (female i)
		      (male i))
		(loop (+ i 1)))))))

(hofstadter-male-female 8)

===> ((1 . 0) (1 . 0) (2 . 1) (2 . 2) (3 . 2) (3 . 3) (4 . 4) (5 . 4) (5 . 5))

(Voir les séquences masculines et féminines de Hofstadter pour les définitions utilisées dans cet exemple.)

Toutes les procédures liées dans un seul letrecpeuvent se référer les unes aux autres par leur nom, ainsi qu'aux valeurs des variables définies plus tôt dans le même letrec, mais elles ne peuvent pas faire référence aux valeurs définies plus tard dans le même letrec.

Une variante de let, la forme "let nommé", a un identifiant après le letmot - clé. Cela lie les variables let à l'argument d'une procédure dont le nom est l'identifiant donné et dont le corps est le corps de la forme let. Le corps peut être répété à volonté en appelant la procédure. Le let nommé est largement utilisé pour implémenter l'itération.

Exemple : un compteur simple

(let loop ((n 1))
  (if (> n 10)
      '()
      (cons n
	    (loop (+ n 1)))))

===> (1 2 3 4 5 6 7 8 9 10)

Comme toute procédure dans Scheme, la procédure créée dans le let nommé est un objet de première classe.

Récursion correcte de la queue

Scheme a une construction d'itération, do, mais il est plus idiomatique dans Scheme d'utiliser la récursivité de la queue pour exprimer l' itération . Des implémentations de Scheme conformes aux normes sont nécessaires pour optimiser les appels de queue afin de prendre en charge un nombre illimité d'appels de queue actifs (R5RS sec. 3.5) - une propriété que le rapport Scheme décrit comme une récursivité de queue appropriée - ce qui permet aux programmeurs de Scheme d'écrire des algorithmes itératifs en utilisant des structures récursives, parfois plus intuitives. Les procédures récursives de queue et la forme nomméelet prennent en charge l'itération à l'aide de la récursivité de queue.

;; Building a list of squares from 0 to 9:
;; Note: loop is simply an arbitrary symbol used as a label. Any symbol will do.

(define (list-of-squares n)
  (let loop ((i n) (res '()))
    (if (< i 0)
        res
        (loop (- i 1) (cons (* i i) res)))))

(list-of-squares 9)
===> (0 1 4 9 16 25 36 49 64 81)

Des suites de première classe

Les continuations dans Scheme sont des objets de première classe . Scheme fournit la procédure call-with-current-continuation(également connue sous le nom de call/cc) pour capturer la continuation actuelle en la compressant en tant que procédure d'échappement liée à un argument formel dans une procédure fournie par le programmeur. (R5RS sec. 6.4) Les continuations de première classe permettent au programmeur de créer des constructions de contrôle non locales telles que des itérateurs , des coroutines et des retours en arrière .

Les continuations peuvent être utilisées pour émuler le comportement des instructions return dans les langages de programmation impératifs. La fonction suivante find-first, étant donné la fonction funcet la liste lst, renvoie le premier élément xde lsttel que (func x)renvoie true.

(define (find-first func lst)
  (call-with-current-continuation
   (lambda (return-immediately)
     (for-each (lambda (x)
		 (if (func x)
		     (return-immediately x)))
	  lst)
     #f)))

(find-first integer? '(1/2 3/4 5.6 7 8/9 10 11))
===> 7
(find-first zero? '(1 2 3 4))
===> #f

L'exemple suivant, un puzzle de programmeur traditionnel, montre que Scheme peut gérer les continuations comme des objets de première classe, les liant à des variables et les passant comme arguments aux procédures.

(let* ((yin
         ((lambda (cc) (display "@") cc) (call-with-current-continuation (lambda (c) c))))
       (yang
         ((lambda (cc) (display "*") cc) (call-with-current-continuation (lambda (c) c)))))
    (yin yang))

Lorsqu'il est exécuté, ce code affiche une séquence de comptage : @*@**@***@****@*****@******@*******@********...

Espace de noms partagé pour les procédures et les variables

Contrairement à Common Lisp, toutes les données et procédures de Scheme partagent un espace de noms commun, alors que dans Common Lisp, les fonctions et les données ont des espaces de noms séparés permettant à une fonction et à une variable d'avoir le même nom, et nécessitant une notation spéciale pour faire référence à un fonctionner comme une valeur. Ceci est parfois connu sous le nom de distinction " Lisp-1 vs. Lisp-2 ", faisant référence à l'espace de noms unifié de Scheme et aux espaces de noms séparés de Common Lisp.

Dans Scheme, les mêmes primitives qui sont utilisées pour manipuler et lier des données peuvent être utilisées pour lier des procédures. Il n'y a pas d'équivalent de Common Lisp defunet de #'primitives.

;; Variable bound to a number:
(define f 10)
f
===> 10
;; Mutation (altering the bound value)
(set! f (+ f f 6))
f
===> 26
;; Assigning a procedure to the same variable:
(set! f (lambda (n) (+ n 12)))
(f 6)
===> 18
;; Assigning the result of an expression to the same variable:
(set! f (f 1))
f
===> 13
;; functional programming:
(apply + '(1 2 3 4 5 6))
===> 21
(set! f (lambda (n) (+ n 100)))
(map f '(1 2 3))
===> (101 102 103)

Normes de mise en œuvre

Cette sous-section documente les décisions de conception qui ont été prises au fil des ans et qui ont donné au Scheme un caractère particulier, mais qui ne sont pas les résultats directs de la conception d'origine.

Tour numérique

Scheme spécifie un ensemble relativement complet de types de données numériques comprenant des types complexes et rationnels , qui est connu dans Scheme sous le nom de tour numérique (R5RS sec. 6.2). La norme les traite comme des abstractions et n'engage l'implémenteur à aucune représentation interne particulière.

Les nombres peuvent avoir la qualité de l'exactitude. Un nombre exact ne peut être produit que par une suite d'opérations exactes impliquant d'autres nombres exacts : l'inexactitude est donc contagieuse. La norme spécifie que deux implémentations quelconques doivent produire des résultats équivalents pour toutes les opérations aboutissant à des nombres exacts.

La norme R5RS spécifie des procédures exact->inexactet inexact->exactqui peuvent être utilisées pour modifier l'exactitude d'un nombre. inexact->exactproduit "le nombre exact qui est numériquement le plus proche de l'argument". exact->inexactproduit "le nombre inexact qui est numériquement le plus proche de l'argument". La norme R6RS omet ces procédures du rapport principal, mais les spécifie comme des procédures de compatibilité R5RS dans la bibliothèque standard (rnrs r5rs (6)).

Dans la norme R5RS, les implémentations de Scheme ne sont pas obligées d'implémenter l'ensemble de la tour numérique, mais elles doivent implémenter « un sous-ensemble cohérent conforme à la fois aux objectifs de l'implémentation et à l'esprit du langage Scheme » (R5RS sec. 6.2.3). La nouvelle norme R6RS nécessite la mise en œuvre de la tour entière, et "des objets entiers exacts et des objets nombres rationnels exacts de taille et de précision pratiquement illimitées, et d'implémenter certaines procédures... section 3.4, section 11.7.1).

Exemple 1 : arithmétique exacte dans une implémentation qui prend en charge les nombres complexes rationnels exacts.

;; Sum of three rational real numbers and two rational complex numbers
(define x (+ 1/3 1/4 -1/5 -1/3i 405/50+2/3i))
x
===> 509/60+1/3i
;; Check for exactness.
(exact? x)
===> #t

Exemple 2 : même arithmétique dans une implémentation qui ne prend en charge ni les nombres rationnels exacts ni les nombres complexes mais accepte les nombres réels en notation rationnelle.

;; Sum of four rational real numbers
(define xr (+ 1/3 1/4 -1/5 405/50))
;; Sum of two rational real numbers
(define xi (+ -1/3 2/3))
xr
===> 8.48333333333333
xi
===> 0.333333333333333
;; Check for exactness.
(exact? xr)
===> #f
(exact? xi)
===> #f

Les deux implémentations sont conformes à la norme R5RS mais la seconde n'est pas conforme à R6RS car elle n'implémente pas la tour numérique complète.

Évaluation différée

Scheme prend en charge l'évaluation différée via le delayformulaire et la procédure force.

(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(set! a 20)
(force eval-aplus2)
===> 22
(define eval-aplus50 (delay (+ a 50)))
(let ((a 8))
  (force eval-aplus50))
===> 70
(set! a 100)
(force eval-aplus2)
===> 22

Le contexte lexical de la définition originale de la promesse est préservé, et sa valeur est également préservée après la première utilisation de force. La promesse n'est évaluée qu'une seule fois.

Ces primitives, qui produisent ou gèrent des valeurs connues sous le nom de promesses , peuvent être utilisées pour implémenter des constructions d' évaluation paresseuses avancées telles que les flux .

Dans la norme R6RS, ce ne sont plus des primitives, mais sont plutôt fournies dans le cadre de la bibliothèque de compatibilité R5RS (rnrs r5rs (6)).

Dans R5RS, une implémentation suggérée de delayet forceest donnée, implémentant la promesse comme une procédure sans arguments (un thunk ) et utilisant la mémorisation pour s'assurer qu'elle n'est jamais évaluée qu'une seule fois, quel que soit le nombre d' forceappels (R5RS sec. 6.4 ).

SRFI 41 permet l'expression de séquences finies et infinies avec une économie extraordinaire. Par exemple, il s'agit d'une définition de la séquence de Fibonacci utilisant les fonctions définies dans SRFI 41 :

;; Define the Fibonacci sequence:
(define fibs
  (stream-cons 0
    (stream-cons 1
      (stream-map +
        fibs
        (stream-cdr fibs)))))
;; Compute the hundredth number in the sequence:
(stream-ref fibs 99)
===>  218922995834555169026

Ordre d'évaluation des arguments de procédure

La plupart des Lisps spécifient un ordre d'évaluation pour les arguments de procédure. Le régime ne le fait pas. L'ordre d'évaluation, y compris l'ordre dans lequel l'expression dans la position de l'opérateur est évaluée, peut être choisi par une implémentation sur une base appel par appel, et la seule contrainte est que « l'effet de toute évaluation simultanée de l'opérateur et Les expressions d'opérande sont contraintes d'être cohérentes avec un certain ordre séquentiel d'évaluation." (R5RS sec. 4.1.3)

(let ((ev (lambda(n) (display "Evaluating ")
                     (display (if (procedure? n) "procedure" n))
                     (newline) n)))
  ((ev +) (ev 1) (ev 2)))
===> 3

ev est une procédure qui décrit l'argument qui lui est passé, puis renvoie la valeur de l'argument. Contrairement aux autres Lisps, l'apparition d'une expression en position d'opérateur (le premier élément) d'une expression Scheme est tout à fait légale, tant que le résultat de l'expression en position d'opérateur est une procédure.

En appelant la procédure "+" pour additionner 1 et 2, les expressions (ev +), (ev 1) et (ev 2) peuvent être évaluées dans n'importe quel ordre, tant que l'effet n'est pas comme si elles étaient évaluées en parallèle . Ainsi, les trois lignes suivantes peuvent être affichées dans n'importe quel ordre par le schéma standard lorsque l'exemple de code ci-dessus est exécuté, bien que le texte d'une ligne ne puisse pas être entrelacé avec une autre car cela violerait la contrainte d'évaluation séquentielle.

Évaluation 1

Évaluation 2

Procédure d'évaluation

Macros hygiéniques

Dans la norme R5RS et également dans les rapports ultérieurs, la syntaxe de Scheme peut facilement être étendue via le système de macros. La norme R5RS a introduit un puissant système de macros hygiéniques qui permet au programmeur d'ajouter de nouvelles constructions syntaxiques au langage à l'aide d'un sous-langage de correspondance de motifs simple (R5RS sec 4.3). Avant cela, le macro-système hygiénique avait été relégué à une annexe de la norme R4RS, en tant que système de "haut niveau" aux côtés d'un macro-système de "bas niveau", tous deux traités comme des extensions de Scheme plutôt que comme une partie essentielle de la langue.

Les implémentations du macro-système hygiénique, également appelé syntax-rules, sont nécessaires pour respecter la portée lexicale du reste de la langue. Ceci est assuré par des règles de nommage et de portée spéciales pour l'expansion des macros et évite les erreurs de programmation courantes qui peuvent se produire dans les systèmes de macros d'autres langages de programmation. R6RS spécifie un système de transformation plus sophistiqué, syntax-case, qui est disponible en tant qu'extension linguistique du schéma R5RS depuis un certain temps.

;; Define a macro to implement a variant of "if" with a multi-expression
;; true branch and no false branch.
(define-syntax when
  (syntax-rules ()
    ((when pred exp exps ...)
      (if pred (begin exp exps ...)))))

Les invocations de macros et de procédures se ressemblent beaucoup (toutes deux sont des expressions s), mais elles sont traitées différemment. Lorsque le compilateur rencontre une expression s dans le programme, il vérifie d'abord si le symbole est défini comme un mot-clé syntaxique dans la portée lexicale actuelle. Si c'est le cas, il essaie ensuite d'étendre la macro, en traitant les éléments de la queue de l'expression s comme des arguments sans compiler le code pour les évaluer, et ce processus est répété de manière récursive jusqu'à ce qu'il ne reste plus d'appels de macro. S'il ne s'agit pas d'un mot-clé syntaxique, le compilateur compile du code pour évaluer les arguments dans la queue de l'expression s, puis pour évaluer la variable représentée par le symbole en tête de l'expression s et l'appeler en tant que procédure avec le les expressions de queue évaluées lui ont été transmises en tant qu'arguments réels.

La plupart des implémentations de Scheme fournissent également des systèmes de macros supplémentaires. Parmi les plus populaires figurent les fermetures syntaxiques , les macros de renommage explicite et define-macro, un système de macro non hygiénique similaire au defmacrosystème fourni dans Common Lisp .

L'impossibilité de spécifier si une macro est hygiénique ou non est l'une des lacunes du système macro. Des modèles alternatifs d'extension tels que des ensembles de portées offrent une solution potentielle.

Environnements et évaluation

Avant R5RS, Scheme n'avait pas d'équivalent standard de la evalprocédure qui est omniprésente dans les autres Lisps, bien que le premier Lambda Paper ait décrit evaluatecomme "similaire à la fonction LISP EVAL" et que le premier rapport révisé en 1978 l'ait remplacé par enclose, qui prenait deux arguments . Les deuxième, troisième et quatrième rapports révisés ont omis tout équivalent de eval.

La raison de cette confusion est que dans Scheme avec sa portée lexicale, le résultat de l'évaluation d'une expression dépend de l'endroit où elle est évaluée. Par exemple, il n'est pas clair si le résultat de l'évaluation de l'expression suivante doit être 5 ou 6 :

(let ((name '+))
  (let ((+ *))
    (evaluate (list name 2 3))))

S'il est évalué dans l'environnement extérieur, où nameest défini, le résultat est la somme des opérandes. S'il est évalué dans l'environnement interne, où le symbole "+" a été lié à la valeur de la procédure "*", le résultat est le produit des deux opérandes.

R5RS résout cette confusion en spécifiant trois procédures qui renvoient des environnements et en fournissant une procédure evalqui prend une expression s et un environnement et évalue l'expression dans l'environnement fourni. (R5RS sec. 6.5) R6RS étend cela en fournissant une procédure appelée environmentpar laquelle le programmeur peut spécifier exactement quels objets importer dans l'environnement d'évaluation.

Avec un schéma moderne (généralement compatible avec R5RS) pour évaluer cette expression, il faut définir une fonction evaluatequi peut ressembler à ceci :

(define (evaluate expr)
   (eval expr (interaction-environment)))

interaction-environment est l'environnement global de l'interprète.

Traitement des valeurs non booléennes dans les expressions booléennes

Dans la plupart des dialectes de Lisp, y compris Common Lisp, par convention, la valeur est NILévaluée à la valeur false dans une expression booléenne. Dans Scheme, depuis la norme IEEE en 1991, toutes les valeurs à l'exception de #f, y compris NILl'équivalent de ' dans Scheme qui s'écrit '(), sont évaluées à la valeur true dans une expression booléenne. (R5RS sec. 6.3.1)

Là où la constante représentant la valeur booléenne de true est Tdans la plupart des Lisps, dans Scheme c'est #t.

Disjointure des types de données primitifs

Dans Scheme, les types de données primitifs sont disjoints. Un seul des prédicats suivants peut être vrai pour un objet Scheme : boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?. (R5RS sec 3.2)

Dans le type de données numérique, en revanche, les valeurs numériques se chevauchent. Par exemple, une valeur entière satisfait tous les prédicats integer?, rational?, real?, complex?et number?en même temps. (R5RS sec. 6.2)

Prédicats d'équivalence

Scheme a trois types différents d'équivalence entre des objets arbitraires désignés par trois prédicats d'équivalence différents , des opérateurs relationnels pour tester l'égalité eq?, eqv?et equal?:

• eq?évalue à à #fmoins que ses paramètres ne représentent le même objet de données en mémoire ;
• eqv?est généralement le même que eq?mais traite les objets primitifs (par exemple les caractères et les nombres) spécialement de sorte que les nombres qui représentent la même valeur soient eqv?même s'ils ne se réfèrent pas au même objet ;
• equal?compare les structures de données telles que les listes, les vecteurs et les chaînes pour déterminer si elles ont une structure et un eqv?contenu congruents . (R5RS sec. 6.1)

Des opérations d'équivalence dépendantes du type existent également dans Scheme: string=?and string-ci=?compare deux chaînes (cette dernière effectue une comparaison indépendante de la casse); char=?et char-ci=?comparer les caractères; =compare des nombres.

commentaires

Jusqu'à la norme R5RS, le commentaire standard dans Scheme était un point-virgule, ce qui rend le reste de la ligne invisible pour Scheme. De nombreuses implémentations ont pris en charge des conventions alternatives permettant aux commentaires de s'étendre sur plus d'une seule ligne, et la norme R6RS en autorise deux : une expression s entière peut être transformée en commentaire (ou "commentée") en la faisant précéder de #;(introduit dans SRFI 62) et un commentaire multiligne ou "bloc de commentaire" peut être produit en entourant le texte avec #|et |#.

Entrée sortie

L'entrée et la sortie de Scheme sont basées sur le type de données du port . (R5RS sec 6.6) R5RS définit deux ports par défaut, accessibles avec les procédures current-input-portet current-output-port, qui correspondent aux notions Unix d' entrée standard et de sortie standard . La plupart des implémentations fournissent également current-error-port. La redirection de l'entrée et de la sortie standard est prise en charge dans la norme, par des procédures standard telles que with-input-from-fileet with-output-to-file. La plupart des implémentations fournissent des ports de chaîne avec des capacités de redirection similaires, permettant à de nombreuses opérations d'entrée-sortie normales d'être effectuées sur des tampons de chaîne au lieu de fichiers, en utilisant les procédures décrites dans SRFI 6. La norme R6RS spécifie des procédures de port beaucoup plus sophistiquées et capables et de nombreux nouveaux types de Port.

Les exemples suivants sont écrits dans un schéma R5RS strict.

Exemple 1 : avec la sortie par défaut sur (current-output-port) :

(let ((hello0 (lambda() (display "Hello world") (newline))))
  (hello0))

Exemple 2 : Comme 1, mais en utilisant un argument de port facultatif pour les procédures de sortie

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (hello1 (current-output-port)))

Exemple 3 : Comme 1, mais la sortie est redirigée vers un fichier nouvellement créé

;; NB: with-output-to-file is an optional procedure in R5RS
(let ((hello0 (lambda () (display "Hello world") (newline))))
  (with-output-to-file "helloworldoutputfile" hello0))

Exemple 4: Comme 2, mais avec un fichier explicite ouvert et un port fermé pour envoyer la sortie au fichier

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p)))
      (output-port (open-output-file "helloworldoutputfile")))
  (hello1 output-port)
  (close-output-port output-port))

Exemple 5 : Comme 2, mais avec l'utilisation de call-with-output-file pour envoyer la sortie vers un fichier.

(let ((hello1 (lambda (p) (display "Hello world" p) (newline p))))
  (call-with-output-file "helloworldoutputfile" hello1))

Des procédures similaires sont fournies pour la saisie. Le schéma R5RS fournit les prédicats input-port?et output-port?. Pour la saisie et la sortie de caractères, write-char, read-char, peek-charet char-ready?sont fournis. Pour écrire et lire des expressions Scheme, Scheme fournit readet write. Lors d'une opération de lecture, le résultat renvoyé est l'objet de fin de fichier si le port d'entrée a atteint la fin du fichier, et cela peut être testé à l'aide du prédicat eof-object?.

En plus de la norme, SRFI 28 définit une procédure de formatage de base ressemblant à la formatfonction de Common Lisp , d'après laquelle elle est nommée.

Redéfinition des procédures standards

Dans Scheme, les procédures sont liées à des variables. Chez R5RS, la norme de langage exigeait formellement que les programmes puissent modifier les liaisons variables des procédures intégrées, les redéfinissant efficacement. (R5RS "Changements de langue") Par exemple, on peut étendre +pour accepter des chaînes ainsi que des nombres en le redéfinissant :

(set! +
      (let ((original+ +))
        (lambda args
          (apply (if (or (null? args) (string? (car args)))
                     string-append
                     original+)
                 args))))
(+ 1 2 3)
===> 6
(+ "1" "2" "3")
===> "123"

Dans R6RS, chaque liaison, y compris les liaisons standard, appartient à une bibliothèque et toutes les liaisons exportées sont immuables. (R6RS sec 7.1) Pour cette raison, la redéfinition des procédures standard par mutation est interdite. Au lieu de cela, il est possible d'importer une procédure différente sous le nom d'une procédure standard, ce qui en fait est similaire à la redéfinition.

Nomenclature et conventions de nommage

Dans le schéma standard, les procédures qui convertissent d'un type de données à un autre contiennent la chaîne de caractères "->" dans leur nom, les prédicats se terminent par un "?", et les procédures qui modifient la valeur des données déjà allouées se terminent par un "!". Ces conventions sont souvent suivies par les programmeurs Scheme.

Dans des contextes formels tels que les normes Scheme, le mot « procédure » ​​est utilisé de préférence à « fonction » pour désigner une expression lambda ou une procédure primitive. Dans l'usage normal, les mots « procédure » ​​et « fonction » sont utilisés de manière interchangeable. L' application de la procédure est parfois appelée formellement combinaison .

Comme dans d'autres Lisps, le terme " thunk " est utilisé dans Scheme pour désigner une procédure sans arguments. Le terme "récursion de queue appropriée" fait référence à la propriété de toutes les implémentations de Scheme, à savoir qu'elles effectuent une optimisation des appels de queue de manière à prendre en charge un nombre indéfini d' appels de queue actifs .

La forme des titres des documents standards depuis R3RS, "Revised ⁿ Report on the Algorithmic Language Scheme", est une référence au titre du document standard ALGOL 60 , "Revised Report on the Algorithmic Language Algol 60," La page Résumé de R3RS est étroitement calquée sur la page Résumé du rapport ALGOL 60.

Examen des formulaires et procédures standard

Le langage est formellement défini dans les normes R5RS (1998) et R6RS (2007). Ils décrivent des « formulaires » standard : mots-clés et syntaxe d'accompagnement, qui fournissent la structure de contrôle du langage, et des procédures standard qui exécutent des tâches courantes.

Formulaires standards

Ce tableau décrit les formulaires standard de Scheme. Certains formulaires apparaissent sur plusieurs lignes car ils ne peuvent pas être facilement classés en une seule fonction dans la langue.

Les formulaires marqués "L" dans ce tableau sont classés comme formulaires dérivés de "bibliothèque" dans la norme et sont souvent implémentés comme des macros utilisant des formulaires plus fondamentaux dans la pratique, ce qui rend la tâche de mise en œuvre beaucoup plus facile que dans d'autres langages.

Notez que cela beginest défini comme une syntaxe de bibliothèque dans R5RS, mais l'expandeur doit en être informé pour obtenir la fonctionnalité d'épissage. Dans R6RS, ce n'est plus une syntaxe de bibliothèque.

Procédures standards

Les deux tableaux suivants décrivent les procédures standard du schéma R5RS. R6RS est beaucoup plus étendu et un résumé de ce type ne serait pas pratique.

Certaines procédures apparaissent sur plusieurs lignes car elles ne peuvent pas être facilement classées en une seule fonction dans le langage.

Les procédures de chaîne et de caractère qui contiennent "-ci" dans leurs noms effectuent des comparaisons indépendantes de la casse entre leurs arguments : les versions majuscules et minuscules du même caractère sont considérées comme égales.

Les implémentations de - et / qui prennent plus de deux arguments sont définies mais laissées facultatives dans R5RS.

Demandes de schéma pour la mise en œuvre

En raison du minimalisme de Scheme, de nombreuses procédures et formes syntaxiques courantes ne sont pas définies par la norme. Afin de garder le langage de base petit mais de faciliter la standardisation des extensions, la communauté Scheme dispose d'un processus de « demande de schéma de mise en œuvre » (SRFI) par lequel les bibliothèques d'extensions sont définies grâce à une discussion approfondie des propositions d'extension. Cela favorise la portabilité du code. De nombreuses SRFI sont prises en charge par toutes ou la plupart des implémentations de Scheme.

Les SRFI bénéficiant d'un soutien assez large dans différentes implémentations comprennent :

• 0 : construction d'expansion conditionnelle basée sur les caractéristiques
• 1 : bibliothèque de listes
• 4: types de données vectoriels numériques homogènes
• 6 : ports de chaîne de base
• 8 : recevoir, se lier à plusieurs valeurs
• 9 : définition des types d'enregistrement
• 13 : bibliothèque de chaînes
• 14 : bibliothèque de jeux de caractères
• 16 : syntaxe pour les procédures d' arité variable
• 17 : ensemble généralisé !
• 18 : Prise en charge du multithreading
• 19 : types de données de temps et procédures
• 25 : primitives de tableaux multidimensionnels
• 26 : notation pour spécialiser les paramètres sans curry
• 27 : sources de bits aléatoires
• 28 : chaînes de format de base
• 29 : localisation
• 30 : commentaires multilignes imbriqués
• 31 : une forme spéciale pour l'évaluation récursive
• 37 : args-fold : un processeur d'arguments de programme
• 39 : objets paramètres
• 41 : cours d'eau
• 42 : compréhensions avides
• 43 : bibliothèque de vecteurs
• 45 : primitives pour exprimer des algorithmes paresseux itératifs
• 60 : entiers sous forme de bits
• 61 : une clause de cond plus générale
• 66 : vecteurs d'octets
• 67 : comparer les procédures

Implémentations

Le design élégant et minimaliste a fait de Scheme une cible populaire pour les concepteurs de langages, les amateurs et les éducateurs, et en raison de sa petite taille, celle d'un interprète typique , c'est également un choix populaire pour les systèmes embarqués et les scripts . Cela a abouti à des dizaines d'implémentations, dont la plupart diffèrent tellement les unes des autres que le portage de programmes d'une implémentation à une autre est assez difficile, et la petite taille du langage standard signifie que l'écriture d'un programme utile d'une grande complexité en standard, portable Scheme est presque impossible. La norme R6RS spécifie un langage beaucoup plus large, dans une tentative d'élargir son attrait pour les programmeurs.

Presque toutes les implémentations fournissent une boucle traditionnelle de lecture-évaluation-impression de style Lisp pour le développement et le débogage. Beaucoup compilent également des programmes Scheme en binaire exécutable. La prise en charge de l'intégration du code Scheme dans des programmes écrits dans d'autres langages est également courante, car la simplicité relative des implémentations de Scheme en fait un choix populaire pour ajouter des capacités de script à des systèmes plus importants développés dans des langages tels que C . Les interpréteurs Gambit , Chicken et Bigloo Scheme compilent Scheme en C, ce qui rend l'intégration particulièrement facile. De plus, le compilateur de Bigloo peut être configuré pour générer du bytecode JVM , et il dispose également d'un générateur expérimental de bytecode pour .NET .

Certaines implémentations prennent en charge des fonctionnalités supplémentaires. Par exemple, Kawa et JScheme offrent une intégration avec les classes Java, et les compilateurs Scheme to C facilitent souvent l'utilisation de bibliothèques externes écrites en C, jusqu'à permettre l'intégration du code C réel dans la source Scheme. Un autre exemple est Pvts , qui propose un ensemble d'outils visuels pour soutenir l'apprentissage de Scheme.

Usage

Scheme est largement utilisé par un certain nombre d'écoles; en particulier, un certain nombre de cours d'introduction à l' informatique utilisent Scheme en conjonction avec le manuel Structure and Interpretation of Computer Programs (SICP). Au cours des 12 dernières années, PLT a dirigé le ProgramByDesign projet (anciennement TeachScheme!), Qui a exposé près de 600 enseignants du secondaire et des milliers d'élèves du secondaire à rudimentaire programmation Scheme. MIT ancienne classe de programmation d' introduction de 6.001 a été enseigné dans le schéma, bien que 6.001 a été remplacé par des cours plus modernes, SICP continue d'être enseigné au MIT. De même, le cours d'introduction à l' UC Berkeley , CS 61A, était jusqu'en 2011 entièrement enseigné dans Scheme, à l'exception de quelques détournements mineurs dans Logo pour démontrer la portée dynamique. Aujourd'hui, comme le MIT, Berkeley a remplacé le programme par une version plus moderne qui est principalement enseignée en Python 3 , mais le programme actuel est toujours basé sur l'ancien programme et des parties de la classe sont toujours enseignées en Scheme.

Le manuel Comment concevoir des programmes de Matthias Felleisen, actuellement à la Northeastern University, est utilisé par certains instituts d'enseignement supérieur pour leurs cours d'introduction à l'informatique. La Northeastern University et le Worcester Polytechnic Institute utilisent Scheme exclusivement pour leurs cours d'introduction Fundamentals of Computer Science (CS2500) et Introduction to Program Design (CS1101), respectivement. Rose-Hulman utilise Scheme dans son cours plus avancé sur les concepts de langage de programmation. Le cours de base de l'Université Brandeis , Structure and Interpretations of Computer Programs (COSI121b), est également enseigné exclusivement en Scheme par l'informaticien théorique Harry Mairson . La classe d'introduction de l'Université de l'Indiana , C211, est entièrement enseignée en Scheme. Une version à votre rythme du cours, CS 61AS, continue d'utiliser Scheme. Les cours d'introduction à l'informatique à Yale et Grinnell College sont également dispensés à Scheme. Programming Design Paradigms, un cours obligatoire pour les étudiants diplômés en informatique de la Northeastern University , utilise également largement Scheme. L'ancien cours d'introduction à l'informatique à l'Université du Minnesota - Twin Cities, CSCI 1901, utilisait également Scheme comme langage principal, suivi d'un cours qui initiait les étudiants au langage de programmation Java ; cependant, suivant l'exemple du MIT, le département a remplacé 1901 par le CSCI 1133 basé sur Python, tandis que la programmation fonctionnelle est couverte en détail dans le cours de troisième semestre CSCI 2041. Dans l'industrie du logiciel, Tata Consultancy Services , la plus grande société de conseil en logiciels d'Asie , utilise Scheme dans son programme de formation d'un mois pour les nouveaux diplômés universitaires.

Le schéma est/était également utilisé pour les éléments suivants :

• Le Document Style Semantics and Specification Language (DSSSL), qui fournit une méthode de spécification des feuilles de style SGML , utilise un sous-ensemble Scheme.
• Le célèbre éditeur graphique raster open source GIMP utilise TinyScheme comme langage de script .
• Guile a été adopté par le projet GNU comme langage de script officiel, et cette implémentation de Scheme est intégrée dans des applications telles que GNU LilyPond et GnuCash comme langage de script pour les extensions. De même, Guile était le langage de script pour l' environnement de bureau GNOME , et GNOME a toujours un projet qui fournit des liaisons Guile à sa pile de bibliothèques. Il existe un projet pour incorporer Guile dans GNU Emacs , le programme phare de GNU, remplaçant l' interpréteur Emacs Lisp actuel .
• Elk Scheme est utilisé par Synopsys comme langage de script pour ses outils technologiques de CAO (TCAD) .
• Shiro Kawai, programmeur senior sur le film Final Fantasy : The Spirits Within , a utilisé Scheme comme langage de script pour gérer le moteur de rendu en temps réel.
• Google App Inventor pour Android utilise Scheme, où Kawa est utilisé pour compiler le code Scheme en codes octets pour la machine virtuelle Java s'exécutant sur les appareils Android.

Voir également

• Essentials of Programming Languages , manuel utilisant Scheme comme fondement

Les références

Lectures complémentaires

• Une introduction au schéma et à sa mise en œuvre ( un miroir )
• Christopher T. Haynes (1999-06-22). « L'expérience de normalisation du langage de programmation de schéma » .
• Guy L. Steele Jr. , Richard P. Gabriel . "L'évolution de Lisp" (PDF) .
• Gerald Sussman et Guy Steele , SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349 , MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, décembre 1975.

Liens externes

• Régime à Curlie
• Programmation de schémas sur Wikibooks
• Écrivez-vous un schéma en 48 heures sur Wikibooks
• Médias liés à Scheme (langage de programmation) sur Wikimedia Commons
• Bookmarklet qui ajoute Interactive Scheme REPL à n'importe quel site Web