Planche : 1
Le langage Scheme
Revision: 1.6
Rétrospective DEUG 1er semestre
Christian Queinnec
UPMC--LIP6
Planche : 2
Rappels
Tous les documents
sont
présents sur le réseau. Ce cours n'est qu'une approximation.
Le cours tient sur 11 séances de 1h25 au premier semestre. Le but du
cours tient dans son titre: « Processus d'évaluation ». Il utilise le
langage Scheme pour parvenir à cette fin ou plus exactement un
sous-ensemble assez réduit. L'évaluateur final est la clé de voûte du
cours dont l'organisation est pensée en vue de cet évaluateur final.
Planche : 3
Semaine 1
introduction
Introduction générale aux notions d'algorithme, de langage, de machine
et de calcul.
TD:
Exercices (description d'un noeud, de l'anthypharèse, de l'euro).
TP:
Prise en main des machines, édition de texte, lancer DrScheme.
DrScheme a une interface assez agréable, permet de limiter le niveau
du langage (à faire cependant). Il existe sur unix et windows
librement diffusable. Il est gourmand en mémoire et lent.
Planche : 4
Semaine 2
notation préfixée,
booléens,
nommage
Premiers pas en Scheme par l'exemple (nombres, booléens, fonctions,
(logiques, arithmétiques), appel, definition). En termes
plus Schemiens (12, -2.3, #t, #f, +, -, *, equal?, not,
and, or, <, >=, =, (fun arguments), define, if.
TD:
Fonctions non récursives simples (calcul d'aire, de TVA, discriminant).
TP:
Édition, évaluation d'expressions arithmétiques simples,
sauvegarde du travail, préliminaires sur boucle fondamentale
d'interaction. Que faire en cas d'erreur.
Imposer la présentation des programmes à l'écran.
Les fonctions ont toujours une arité fixe. Les alternatives sont
ternaires et begin ne sert qu'à tracer l'évaluation.
Planche : 5
Semaine 3
composition,
typage d'une expression,
modèle d'évaluation par substitution,
analyse descendante d'un problème
Notion mathématique sur fonctions, signature (domaine, codomaine),
composition. Modèle d'évaluation par substitution. Côté Scheme,
introduction du cond; fonctions passées en argument.
TD:
Résolution équation second degré.
TP:
Composition d'images.
Planche : 6
Semaine 4
compréhension d'une définition récursive,
méthode de travail pour l'écriture de définition récursive,
blocs lexicaux
Schémas de récursion sur les nombres.
TD:
Variantes sur schéma de récursion
(define (f n) (define (f n)
(if (= n 0) (if (>= n constante)
cas de base cas d'arrêt
(composer n (f (- n 1))) ) ) (composer n (f (+ n 1))) ) )
TP:
racine carrée, entrelacement de représentations d'entiers,
nombre de pavage de couloir, décomposition d'entiers.
Ne surtout pas dramatiser la récursion.
On utilisera principalement des entiers.
Planche : 7
Semaine 5
liste,
schéma récursif,
citation
Listes pures, plates et homogènes. Fonctions cons, car, cdr.
Récursion sur listes pures, plates et homogènes. Comparaison entre
cons, list et append. Introduction de la citation (quote).
TD:
schéma récursif sur liste et variantes.
(define (f l)
(if (pair? l)
(combiner l (f (cdr l)))
cas de base ) )
TP:
longueur d'une liste, renversement, concaténation avec
récursion sur le second argument.
Dogme: jamais ne prendras car ou
cdr de quelque valeur qui n'est pas pair?.
Donc récursion avec pair? plutôt que null?.
On ne traite que des listes pures homogènes et plates.
Planche : 8
Semaine 6
approfondissement listes,
itérateurs
listes d'associations (assoc) homogènes et pures. listes de listes,
listes de fonctions, schémas d'itération map, for-each, reduce,
combine. schéma avec accumulateur.
TD:
doublons, doublons stricts, histogrammes.
TP:
récursion pour créer des graphiques.
Les primitives graphiques sont reprises du livre d'Hailperin.
Planche : 9
Semaine 7
Sexpression
Concept de Sexpression: «Sexp = Atom + Sequence(Sexp)» et «Atom =
Nombre | Caractère | Booléen | Symbole | Chaîne | Fonction |
Vecteur(Sexp)». Schéma de récursion sur les Sexp:
(define (f e)
(if (pair? e)
(combiner (f (car e)) (f (cdr e)))
cas de base ) )
TD:
dérivation symbolique d'expression arithmétique, simplification.
TP:
évaluateur d'expressions arithmétiques (nombres, opérateurs
arithmétiques) puis introduction de variables (afin
d'introduire un environnement).
On ne dessine pas de boîtes mais des arbres.
Les Sexpressions sont à distinguer des listes.
Planche : 10
Semaine 8
barrière d'abstration,
interfaces
Notion de barrière d'abstraction (encapsulation). Interface
fonctionnelle (type abstrait n'exportant que des fonctions).
S'appuyer sur l'encodage des arbres binaires des cours précédents.
TD:
réécriture de formes COND en formes IF (sans BEGIN implicite).
TP:
vérificateur de la syntaxe du scheme version deug (parler de
grammaire).
Planche : 11
Semaine 9
Boucle fondamentale d'interaction,
eval et analyse syntaxique
Emploi d'eval pour conversion texte->fonction. Un interprète Scheme
lit des Sexpressions (restreintes à la grammaire de Scheme (parler de
grammaire (avec exercices (cf. leçon 8) avant), l'évalue puis imprime
le résultat. Les opérations read et display règlent
les deux extrémités; au milieu est la fonction eval. Scheme
est un langage universel, on peut donc écrire eval.
Quelles sont les bases: qqs traits syntaxiques, quelques formes
spéciales et quelques fonctions. On fera d'abord une analyse
syntaxique pour voir ce qu'est le programme, puis on exécutera ce que
l'on a compris. On peut aussi expliquer ce qu'est une boucle
d'interprétation.
TD:
Déterminer les variables globales d'une expression.
expansion de and, or, case, cond.
TP:
Évaluateur d'un petit langage de composition d'images avec une
forme de liaison de nom local (l'équivalent d'un LET).
Voici la grammaire du Scheme enseigné:
<program> := <expression>
| <global-definition>
<expression> := <constant>
| <variable>
| (cond <clause> ... )
| (if <expression> <expression>)
| (if <expression> <expression> <expression>)
| (quote <data>)
| (begin <expression> ... )
| (let () <definition> ... <expression> ... )
| (let ( <binding> ... ) <definition> ... <expression> ... )
| (<expression> ... )
;;
;;
<constant> := boolean | number | character | "string"
<data> := <constant>
| <symbol>
| ()
| ( <data> ... )
;;
<clause> := ( <expression> <expression> ... )
| (else <expression> ...)
<binding> := ( <variable> <expression> )
<definition> := (define (<variable> ...)
<definition> ...
<expression> ... )
;;
<global-definition> := <definition>
| (define <variable> <expression>)
;;;
;;;
;;;
Planche : 12
Semaine 10
eval sans récursion
La fonction eval (première partie). Description et
codage. L'évaluateur est, pour l'instant,
celui-ci.
Expliquer la structure d'evaluate, l'analyse syntaxique et le
transfert sur la bonne fonction d'évaluation. Revue des traits et
formes spéciaux en commençant par les variables, puis quote, if, begin
et evaluate-call. Pour cela il faut introduire la notion
d'environnement, lookup et extend et pour les fonctions,
create-function et invoke c'est-à-dire les types abstraits
environnements et fonctions.
TD:
restructuration d'eval. changement d'implantation
des environnements ou des fonctions.
TP:
Lancer l'évaluateur sur des petites expressions. L'évaluer
lui-même et comparer les temps d'évaluation. L'enrichir avec les
fonctions sur les chaînes, la factorielle. Interdire les if non
ternaires.
voir le code de l'interprète.
Planche : 13
Semaine 11
récursion,
environnement initial,
noyau/extensions
Eval (seconde partie): explication de let, ebody, enrich et récursion
mutuelle. Puis expliquer les primitives et l'environnement initial (ce
sont les parties les plus complexes).
Interprétation, compilation, bibliothèques.
Révisions, mise en perspective du cours et de ses concepts.
TD:
Simplificateur de programme.
Ajout de nouvelles formes spéciales when,
repeat.
TP:
Ajouter trace d'expression, metteur au point pas à pas.
Planche : 14
Semaine 12
Conférence Informatique-liberté.
questionnaire d'évaluation du cours.
Ce document a été traduit de LATEX par
HEVEA.