UPMC LI101 --- cours « Programmation récursive » --- Carte de référence

Revision: 1.87

Ce document ne décrit que le sous-ensemble de Scheme enseigné dans l'UE Programmation récursive de l'UPMC. Cette carte de référence peut être librement utilisée lors des contrôles de connaissance.

1 Spécification

;;; <nom-fonction>: <type-fonction>
;;; (<nom-fonction> <variable>^*) sémantique...
;;; ERREUR lorsque ...
;;; HYPOTHÈSE: ...

(define (<nom-fonction> <variable>^*)
... )

2 Grammaire des types

<AutreType>	->	Tout type dont l'usage est préconisé par un exercice.

<types>	->	<type>
		<type> `` <types>*

<type>	->	<type-non-contraint>
		<type-contraint>

<type-destination>	->	<type>
		`Rien`

<type-non-contraint>	->	<type-base>
		`LISTE` `[` <type> `]`
		`COUPLE` `[` <type> <type> `]`
		`VECTEUR` `[` <type> `]`
		`NUPLET` `[` <type>^*`]`
		<type>`^` <nat>
		<type> `+ #f`
		`(` <type-fonction> `)`

<type-base>	->	t] `nat` ou `int` ou `float` ou `Nombre` ou `string` ou `bool` ou `Valeur` ou `Image` ou `symbol` ou <variable-type> ou <AutreType>

<type-contraint>	->	<type> `/` <contrainte> `/`

<type-fonction>

<types>	`->`	<type-destination>
	`->`	<type-destination>

<variable-type>	->	`alpha`
		`beta`
		etc.

3 Grammaire du langage

<programme>	->	<expression-ou-définition>^*

<alternant>	->	<expression>

<alternative>	->	`(if` <condition> <conséquence> <alternant> `)`

<application>	->	`(` <fonction> <argument>^* `)`

<argument>	->	<expression>

<bloc>	->	`(let (` <liaison>^* `)` <corps> `)`
		`(let* (` <liaison>^* `)` <corps> `)`

<booléen>	->	`#t`
		`#f`

chaîne

" caractères autres que guillemets "

<citation>	->	`(quote` <S-expression> `)`
		`'` <S-expression>

<clause>	->	`(` <condition> <expression> `)`

<clauses>	->	<clause> <clause>^*
		<clause>^`(else` <expression>* `)`

<condition>	->	<expression>

<conditionnelle>	->	`(cond` <clauses> `)`

<conjonction>	->	`(and` <expression>^*`)`

<conjonction-ou-disjonction>	->	<conjonction>
		<disjonction>

<conséquence>	->	<expression>

<constante>	->	<booléen>
		nombre
		chaîne

<corps>	->	<définition>^*<expression>

<définition>	->	`(define (` <nom-fonction> <variable>^`)` <corps>* `)`

<disjonction>	->	`(or` <expression>^*`)`

<expression>	->	<constante>
		<variable>
		<nom-fonction>
		<forme-spéciale>
		<application>

<expression-ou-définition>	->	<expression>
		<définition>

<fonction>	->	<expression>

<forme-spéciale>	->	<conditionnelle>
		<alternative>
		<conjonction-ou-disjonction>
		<citation>
		<bloc>

identificateur

t] tous les symboles de Scheme qui ne sont pas des mots-clés c'est-à-dire cond, else, if, quote, begin, let, let*, define, or, and.

<liaison>	->	`(` <variable> <expression> `)`

nombre

tous les nombres de Scheme

<nom-fonction>	->	identificateur

<S-expression>	->	<constante>
		symbole
		<vecteur>
		`(` <S-expression>^* `)`

symbole

tous les symboles de Scheme

<variable>	->	identificateur

<vecteur>	->	`#(` <S-expression>^* `)`

4 Commentaires

;;; Commentaire général
;; Commentaire de bloc
; petit commentaire local

Un commentaire général porte sur les expressions ou définitions qui suivent. Il débute toujours en première colonne.

Un commentaire de bloc qualifie l'expression ou la définition qui suit. Il est aligné avec cette expression ou définition.

Un commentaire local porte sur l'expression de la même ligne qui précéde immédiatement ce commentaire. Il s'achève en bout de ligne.

5 Bibliothèque

Les nombres peuvent être des entiers, des rationnels ou des flottants.

equal?:Valeur × Valeur --> bool
(equal? v₁ v₂) compare deux valeurs quelconques

5.1 Nombres

not:bool --> bool
(not b) rend la négation de b number?:Valeur --> bool
(number? v) reconnaît si v est un nombre integer?:Valeur --> bool
(integer? v) reconnaît si v est entier positive?:Nombre --> bool
(positive? x) vérifie que x est strictement positif negative?:Nombre --> bool
(negative? x) vérifie que x est strictement négatif odd?:int --> bool
(odd? n) vérifie que n est impair even?:int --> bool
(even? n) vérifie que n est pair =:Nombre × Nombre --> bool
(= x₁ x₂) compare deux nombres +:Nombre × Nombre × ... --> Nombre
(+ x...) rend la somme de ses arguments -:Nombre × Nombre --> Nombre
(- x₁ x₂) rend x₁ - x₂ *:Nombre × Nombre × ... --> Nombre
(* x...) rend le produit de ses arguments /:Nombre × Nombre/non nul/ --> Nombre
(/ x₁ x₂) rend x₁/x₂ >:Nombre × Nombre --> bool
(> x₁ x₂) vérifie que x₁>x₂

Prédicats analogues: >=, < et <= quotient:int × int/non nul/ --> int
(quotient n₁ n₂) rend le quotient de la division euclidienne de n₁ par n₂ modulo:int × int/non nul/ --> int
(modulo n₁ n₂) rend le reste de la division euclidienne de n₁ par n₂ max:Nombre × Nombre × ... --> Nombre
(max x...) rend le plus grand des x min:Nombre × Nombre × ... --> Nombre
(min x...) rend le plus petit des x abs:Nombre --> Nombre
(abs x) rend la valeur absolue de x sqrt:Nombre/³0/ --> Nombre
(sqrt x) rend la racine carrée de x

5.2 S-expressions

pair?:Valeur --> bool
(pair? v) vérifie que v a un car et un cdr list?:Valeur --> bool
(list? v) reconnaît que v est une liste (éventuellement vide) car:LISTE[alpha]/pair?/ --> alpha
(car l) rend le premier terme de la liste l. [ERREUR lorsque l ne satisfait pas pair?] cdr:LISTE[alpha]/pair?/ --> LISTE[alpha]
(cdr l) rend la liste formée de tous les termes de l sauf son premier. [ERREUR lorsque l ne satisfait pas pair?]

(cadr l) <==> (car (cdr l))
(cddr l) <==> (cdr (cdr l)) etc.

cons: alpha ×LISTE[alpha] --> LISTE[alpha]
(cons v l) crée une nouvelle liste telle que son car est v et son cdr est l list: alpha × ... -->LISTE[alpha]
(list v...) crée une liste dont les termes sont les arguments. (list) rend la liste vide length:LISTE[alpha] --> nat
(length l) rend la longueur de la liste lappend:LISTE[alpha] × ... --> LISTE[alpha]
(append l...) rend la concaténation des listes reçues en arguments reverse:LISTE[alpha] --> LISTE[alpha]
(reverse l) rend la liste renversée de lmember: alpha ×LISTE[alpha] --> LISTE[alpha]+#f
(member v l) rend le suffixe de l débutant par v ou #f si v n'apparaît pas dans lassoc: alpha ×LISTE[COUPLE[alpha beta]] --> COUPLE[alpha beta]+#f
(assoc c al) rend le couple (clé valeur) dont la clé est c ou bien #f s'il n'y a pas de tel couple symbol?:Valeur --> bool
(symbol? v) reconnaît que v est un symbole string?:Valeur --> bool
(string? v) reconnaît que v est une chaîne de caractères string-length:string --> nat
(string-length s) rend la longueur de la chaîne s substring:string × nat × nat --> string
(substring s i j) construit la chaîne à partir des caractères [i ... j[ de s string-append:string × ... --> string
(string-append s...) construit la concaténation de toutes les chaînes reçues en arguments vector?:Valeur --> bool
(vector? v) reconnaît que v est un vecteur vector: alpha × ... -->VECTEUR[alpha]
(vector v...) rend le vecteur dont les termes sont les argumentsvector-ref:VECTEUR[alpha] --> alpha
(vector-ref vecteur index) rend le index-ième terme du vecteurvector-length:VECTEUR[alpha] --> nat
(vector-length vecteur) rend la longueur du vecteurvector->list:VECTEUR[alpha] --> LISTE[alpha]
(vector->list vecteur) rend la liste des termes du vecteurlist->vector:LISTE[alpha] --> VECTEUR[alpha]
(list->vector liste) rend le vecteur des termes de la listemap: (alpha -->beta) × LISTE[alpha] --> LISTE[beta]
(map f l) rend la liste dont les termes sont les images par f des termes de la liste l

5.3 Divers

display:Valeur --> Rien
(display v) imprime la valeur, ne rend rien d'intéressant newline: -->Rien
(newline) passe à la ligne, ne rend rien d'intéressant

6 Suppléments

Les fonctions et formes spéciales suivantes ne sont utilisables sous DrScheme que si le paxon (ou teachpack) MIAStools est actif.filtre: (alpha -->bool) × LISTE[alpha] --> LISTE[alpha]
(filtre p l) rend la liste extraite de l dont les termes satisfont le prédicat p reduce: (alpha × beta -->beta) × beta × LISTE[alpha] --> beta
(reduce f e l) Compose binairement par f les éléments de la liste l en terminant par e. Plus formellement: (reduce f e (list e₁ e₂ ...e_n)) º (f e₁ (f e₂ ...(f e_n e) ...)). erreur:symbol × alpha × ... -->

(erreur f...) signale une erreur avec f comme nom de fonction et les arguments suivants comme explication de l'erreur. Signaler une erreur stoppe l'évaluation. erreur?: (alpha × ... -->beta) × alpha × ... --> bool
(erreur? f...) teste si une fonction f appliquée à ses arguments provoque une erreur. verifier: ... -->bool
(verifier nom sexp == sexp...) regroupe les tests relatifs à la fonction nom. Évalue tour à tour chaque S-expression avant et après le signe d'équivalence == et vérifie que les valeurs sont égales. Rend \#t si tous les tests sont corrects.

7 Bibliothèque graphique

Le système de coordonnées des primitives graphiques varie de (-1,-1) pour le coin bas gauche à (+1,+1) pour le coin haut droit. Le type Coordonnée désigne un nombre entre -1 et +1. Les images construites sont par défaut carrées et de côté 100 pixels.image-vide: -->Image
(image-vide) rend une image carrée blanche.filled-triangle:Coordonnée⁶ --> Image
(filled-triangle x₀ y₀ x₁ y₁ x₂ y₂) rend une image carrée blanche contenant un triangle noir de sommets (x₀, y₀), (x₁, y₁) et (x₂, y₂). invert:Image --> Image
(invert image) rend une nouvelle image à couleur inversée. line:Coordonnée⁴ --> Image
(line x₀ y₀ x₁ y₁) rend une image carrée blanche contenant un segment noir partant de (x₀, y₀) jusqu'à (x₁, y₁). overlay:Image × ... --> Image
(overlay image...) rend une image superposant les contenus des images reçues en arguments [ERREUR lorsque les images sont de tailles différentes] quarter-turn-right:Image --> Image
(quarter-turn-right image) rend une nouvelle image dont le contenu est celui de l'image tournée de 90 degrés dans le sens des aiguilles d'une montre. stack:Image × Image --> Image
(stack image₁ image₂) rend une nouvelle image par juxtaposition de l'image₁ au dessus de l'image2. [ERREUR lorsque les images sont de largeurs différentes] image?:Valeur --> bool
(image? v) reconnaît si v est une image image-width:Image --> nat
(image-width image) rend la largeur d'une image (en pixels). image-height:Image --> nat
(image-height image) rend la hauteur d'une image (en pixels). resize-image:Image × nat × nat --> Image
(resize-image image largeur hauteur) rend une nouvelle image homothétique avec une largeur et une hauteur spécifiées (en pixels). mirror-image:Image --> Image
(mirror-image image) rend une image miroir (symétrie y) de l'image fournie.

8 Lignes et paragraphes

Une ligne est une chaîne de caractères sans fin de ligne. Un paragraphe est une chaîne de caractères débutant par une fin de ligne suivie de lignes, chacune terminée par une fin de ligne. Par exemple, "bon jour" est une ligne, tandis que la chaîne suivante est un paragraphe formé de deux lignes:

"
bon
jour
"

paragraphe:LISTE[Ligne] --> Paragraphe
(paragraphe lignes) rend le paragraphe formé des lignes paragraphe-cons:Ligne × Paragraphe --> Paragraphe
(paragraphe-cons ligne paragraphe) construit un paragraphe ayant en premier ligne suivi des lignes de paragraphe lignes:Paragraphe --> LISTE[Ligne]
(lignes paragraphe) rend la liste des lignes que comporte le paragraphe paragraphe-append:Paragraphe × ... --> Paragraphe
(paragraphe-append paragraphes...) rend le paragraphe correspondant à la concaténation des paragraphes reçus en arguments ->string:Valeur --> string
(->string v) construit une chaîne représentant l'argument qui peut être quelconque (nombre, symbole, chaîne, liste, etc.)

9 Bibliothèque d'arbres

Les fonctions préfixées par ab- forment la barrière d'abstraction des arbres binaires. Les fonctions préfixées par ag- forment la barrière d'abstraction des arbres généraux.

La barrière d'abstraction est formée de constructeur(s), sélecteurs (ou accesseurs) et reconnaisseur(s). ab-noeud: alpha ×ArbreBinaire[alpha] × ArbreBinaire[alpha] --> ArbreBinaire[alpha]
(ab-noeud etiquette arbre-gauche arbre-droit) construit un arbre binaire ab-vide: -->ArbreBinaire[alpha]
(ab-vide) construit un arbre binaire vide ab-noeud?:ArbreBinaire[alpha] --> bool
(ab-noeud? arbre) reconnaît si un arbre binaire n'est pas vide ab-etiquette:ArbreBinaire[alpha] --> alpha
(ab-etiquette arbre) rend l'étiquette d'un arbre binaire non vide ab-gauche:ArbreBinaire[alpha] --> ArbreBinaire[alpha]
(ab-gauche arbre) rend le sous-arbre gauche d'un arbre binaire non vide ab-droit:ArbreBinaire[alpha] --> ArbreBinaire[alpha]
(ab-droit arbre) rend le sous-arbre droit d'un arbre binaire non vide ab-expression:ArbreBinaire[alpha] --> Expression
(ab-expression arbre) rend l'expression construisant l'arbre binaire ag-noeud: alpha ×LISTE[ArbreGeneral[alpha]] --> ArbreGeneral[alpha]
(ag-noeud etiquette sous-arbres) construit un arbre général ag-etiquette:ArbreGeneral[alpha] --> alpha
(ag-etiquette arbre) rend l'étiquette d'un arbre général ag-foret:ArbreGeneral[alpha] --> LISTE[ArbreGeneral[alpha]]
(ag-foret arbre) rend la forêt sous la racine de l'arbre ag-expression:ArbreGeneral[alpha] --> Expression
(ag-expression arbre) rend l'expression construisant l'arbre général

Ce document a été traduit de L^AT_EX par H^EV^EA.