Notes de cours IFT2030.doc

Cours IFT2030 - Concepts des langages de programmation
Cours 1, Lundi 9 janvier 2006
Cours 2, jeudi 12 janvier 2006 Syntaxe infixe, par opposition à préfixe (opérateur au milieu plutôt qu'au
début) Dans le cours: Scheme, C, Prolog
Cours 3, lundi 16 janvier 2006
Démo 1, mardi 17 janvier 2006 Haskell: Fonctionnel Simula: Objet+impértif (coroutines)
PostScript: Impératif Prolog: Logique
Concurrent: Pascal Lisp: Fonctionnel et impératif
(g.auto.mém) Simula Famille Algol (typique parce que blocs, procédures, begin, end)
Fortran Pas Algol (évident), très peu procédures (label surtout)
Forth Postfix, peu lisible, relativement concis, codera efficacement.
quelque proc. Algol68 Types prédéfinis, plus d'abstraction, coroutines,
très bon, mais il n'y avait pas vraiment de bon compilateur à
l'époque
Java Très lisible, mais peut-être moins que Algol. Famille Algol, blocs
{ }, etc.
Haskell Très très concis, moy. lisible (selon expérience), Pas algol,
plutôt fonctionnel Langages Type Algol: Pascal, Java, C, modula-2, simula, algol, oberon,
Qbasic, ADA95 Extension stricte: (par exemple C est inclus au complet dans C++)
ML ( SML
( O'Caml Exercices:
Choix parmi: C++, Java, VB, Fortran, Perl, Prolog
a) Simulateur d'avion réaliste: C++, (Java), ((VB pour GUI p-être))
b) Jeux de carte pour cellulaires: Java [Très portable, Bcoup de vm,
petit], (C++)
c) Jeu 3D style Doom pour WinXP: VB(Librairie, Outils matériels),
C++(en pratique)
d) Pour WinXP, un logiciel interactif de conception de jeu, utilisé par
exemple pour créer les niveaux: VB(pas de problème de portabilité ou
de performance), (C++(par habitude))
e) Jeu d'aventure texte: Prolog (si..., mais dur pour les I/O), Perl (si
prog court)
f) Site web (télécharger, écrans, forum, etc.): Perl, Java, VB.net(p-
être avec les nouv. exten.) 7. 1. indéfini, peut donner 1 ou -1 si on prned un négatif.
2. short dépend du compilateur.
3. ordre d'évaluation des expressions indéterminé.
4. trop d'arguments (31 max pour le standard, p-être plus) Cours 4, jeudi 19 janvier 2006
Cours 5, lundi 23 janvier 2006 Saut de la page 38 à la page 161 des anciennes notes de cours. Effet de bord: Effet causé par exemple par l'ordre des opérations ou des
sorties qui peut faire que le résultat de la fonction ne
sera pas toujours le même. Donc, dans un langage fonctionnel, on ne pourra pas faire une boucle de la
façon usuelle. Scheme:
True/False: #t #f let: Pour un genre de bloc local, on affecte pour une expression
seulement...
(let ((a 5) (b 2)) (+ a b)) le let vaut donc 7
Attention à la portée pour les variables. L'ordre normal nous garanti qu'on va obtenir une réduction normale (peut-
être avec répétitions) mais sinon il ets possible qu'on boucle à l'infini
lors de la réduction. Mais si on obtient une réduction, on obtiendra la
même peut importe l'ordre.
Démo 2, mardi 24 janvier 2006 2.1/2.2
. a*b+c
o postfixe: a b * c +
o préfixe: + * a b c
. a*(b+c)
o post: a b c + *
o pré: * a + b c
. a*b+c*d
o post: a b * c d * +
o pré: + * ab * c d
. a*(b+c)*d
o post: a b c + * d * ( ou a b c + d * * )
o pré: * * a + b c d
. (b/2 + sqrt((b/2)*(b/2)-a*c))/a
o post: b 2 / b 2 / b 2 / * a c * - sqrt + a /
o pré: / + / b 2 sqrt - * / b 2 / b 2 * a c a 2.8: 7 7 * 4 2 * 3 * - [Évaluer avec une pile] | | | |2 | |3 | | | | |7 | |4 |4 |8 |8 |24 | | |7 |7 |49 |49 |49 |49 |49
|49 |25 | | 2.3:
1: + 2: * 3: + 4: * 5: %
/ \ / \ / \ / \ / \
* c a + * * * d + a
/ \ / \ / \ / \ / \ / \
a b b c a b c d a + %
sqrt
/ \ / \ |
b c b 2 -
/ \
* *
/ \
/\
% % a
c
/ \ / \
b 2 b 2
nota: Pour écrire le préfixe (postfixe similaire) il suffit de suivre
l'arbre, on note le noeud, on fait la branche gauche, puis la branche
droite (récursif).
2.6/2.7: ( E ::= E + T | E - T | T
T ::= T * F | T / F | F *notons que tout sur une même ligne
donnerait plus de
F ::= number | name | (E) liberté... donc aurait créé des
ambigüités... a) 2 + 3 b) (2+3) A.dériv. ASA A.D. ASA E + E +
/|\ / \ | / \
E + T 2 3 T 2 3
| | |
T F F
| | /|\
F 3 ( E )
| /|\
2 E + T
| |
T F
| |
F 3
|
2 2.16: Traduire EBNF vers BNF nota: [] ( 0 ou 1 fois
::= {} ( 0 ou + fois
| id :=
| if then
{elsif then }
[else ] end
| loop end
| while do end
::= {;} Devient, en BNF: ::=
| id :=
| if then end
| loop end
| while do end
::=
::=|;
::=|else
::=|elseifthen
2.19: par exemple ambigüe avec: if a then if b then c else d S::= x
| if E then S
| if E then S else S Devient: S::= T O x
T::= {if E then T x else}
O::= {if E then T} S
/ | \
T O x
/ |
|
// \\
if E then T
|
//|\\
if E then T x else
|

Faire l'évaluation des expressions en Scheme: a) (let ((f(lambda (x)(+ x 1)))(f (+ 2 3)))
lamba va définir une fonction anonyme retournant la valeu de
l'entrée plus un.
Ordre applicatif:
(f (+ 2 3))
(f 5)
((lambda (x) (+ x 1)) 5)
(let (x 5) (+ x 1))
(+ 5 1)
6
Ordre normal:
((lambda (x) (+ x 1)) (+ 2 3))
(let (x (+ 2 3)) (+ x 1))
(+ (+ 2 3) 1 )
6
b) ((lambda (x) (x x)) (lamda (z) (z z))
Applicatif/Normal
(let (x (lambda (z) (z z))) (x x)
((lambda (z) (z z)) (lambda (z) (z z)))
et donc tourne en rond ...
c) ((let ((f (lambda (x y) x)))
(let (g (lambda (z) (z z))))
(f (+ 1 2) (g g))))
Applicatif:
L'évaluation ne termine pas!
Normal:
(+ 1 2) ( 3. Cours 6, jeudi 26 janvier 2005 Faire attention de ne pas confondre:
L'environnement d'évaluation de la lambda-expression
L'environnement d'évaluation du corps de la lamba-expression
(Qui est l'environnement d'éval. de la lamba-express ET un bloc
lexical) (Voir nouvelles notes p.±110-112)
Cours 7, lundi 30 janvier 2006 ANNULÉ
Démo 3, mardi 31 janvier 2006 1) manqué. 2) Avec xn = (xn-1 + N/xn-1)/2 et x0 = N, afficher valeurs jusqu'à ce
que |xn2 -N| < 1/1000 Scheme: (define (racine n)
(racaux n n)
)
(define (racaux n sqrtn)
(if
(<
(abs
(-
(* sqrtn sqrtn)
n
)
)
1/1000
)
sqrtn
(racaux n
(/
(+
sqrtn
(/ n sqrtn)
)
2
)
)
)
)
Pseudo-Java: racine(n) {
racaux(n,n)
} racaux(n,x) {
double a=(x+(n/2))/2;
if (abs(a*a-n) < 1/1000)
return a;
else
return racaux(n,a);
}
3) Refaire le même exercice avec des entiers et avec comme condition
d'arrêt xi=xi-1 (define (racine n)
(racaux n n)
(define (racaux n x)
(let ((a (quotient
(+ x (quotient n x))
2)
(if (= x a)
a
(racaux n a))))) 4) Définir (binaire ( decimal 10001) ( 17 Et (decimal ( binaire
17) ( 10001 Comment faire?:
10001, on fait 1?20 + 0(21 + ...
1 + 2* val(1000)
val(0)=0
val(1)=1 En Scheme: (define (binaire->decimal n)
(if (< n 2)
n
(+ (modulo n 10)
(* 2
(binaire->decimal
(quotient n 10)))))) 17, a-17/2 a+10*val(b)
b=17mod2 1+10*1000 (define (decimal->binaire n)
(if (< n 2)
n
(+ (modulo n 2)
(* 10 (decimal->binaire
(quotient n 2)))))) Cours 8, jeudi 2 février 2006 char-ci permet d'ignorer la casse eq? Teste l'identité (la même adresse)
equal? Teste l'égalité du contenu, de la structure.
Cours 9, lundi 6 février 2006 Position terminale: Lorsqu'on est en train de calculer ce qui sera
directement retourné par la fonction. Par