Informatique et recherche
opérationnelle
IFT2030

Concepts des langages de programmation

Automne 2002


Accueil

Professeur et
Démonstrateurs

Horaires et locaux

Notes de cours

Démonstrations
et devoirs

Examens

Liens utiles

Au sujet du
livre de cours

Consultez vos notes

Foire aux questions
(FAQ)

Notes de cours

Deux types de notes vous sont proposés ici:

  • les notes de cours réalisées par Marc Feeley
  • des brèves de cours qui résument très sommairement les points importants abordés en cours et proposent le cas échéant des exemples vus en cours mais non extraits du livre ou des notes de cours (un peu de variété ne fait pas de mal).
Mes bonnes résolutions pour cette session: Je ferai le maximum pour que cette page soit mise à jour avant chaque cours afin que vous puissiez vous y présenter avec les exemples que nous étudierons. D'avance mille excuses pour les fois où je n'y parviendrai pas (le premier cours en est un exemple).

Prenez note que mes brèves de cours pourront être mise à jour après le cours concerné.


Acétates rédigées par Marc Feeley


Cours après cours

  • [lundi 2 décembre 2002] (2 heures)
    • Quelques prédicats classiques (suite)
      • arbre de preuve pour insertion
      • permutation d'une liste (essayez de l'écrire en C/C++ ou Java)
      • tri d'une liste en O(n.n!)
      • un tri plus décent (quicksort)
      • les différences de listes (où comment faire une concaténation en temps constant).
    • La négation en Prolog
  • [lundi 2 décembre 2002] (1 heure)
    • Entre l'intuition et la réalité (cas de l'insertion d'une valeur dans un arbre binaire de recherche utilisée pour la suppression)
    • Prolog et les listes
      • parallèle avec les listes en Scheme
      • quelques prédicats classiques:
        • appartenance d'un élément à une liste
        • intersection de deux listes
        • concaténation de deux listes
        • insertion d'un élément dans une liste

  • [mardi 26 novembre 2002] (2 heures)
    • Unification
    • Algorithme de contrôle de Prolog
    • Arbre de preuve
    • Structure de données en Prolog

  • [lundi 25 novembre 2002] (1 heure)
    • Programmation logique et Prolog
      • langage déclaratif
      • un exemple intuitif
      • principes de base de Prolog

  • [mardi 19 novembre 2002] (2 heures)
    • Scheme suite et fin (attachez vos tuques):
      • Deux exemples sur les continuations qui montrent que l'on peut rendre terminale une récursivité qui ne l'est pas en se servant des continuations.

    Suppléments:

    • ai-je déclenché (malgré moi) en vous la passion des continuations?
      Si oui, alors essayez d'écrire avec une continuation la méthode liste->reverse-int
      qui prend en paramètre une liste et une continuation et qui retourne l'entier dont les chiffres sont en ordre inverse par rapport à la liste:

      (liste->reverse-int '(1 2 3 4) f) devrait produire 4321, où f est une fermeture à définir.

      Voici une solution possible: [cont.scm] où la fonction avec continuation est masquée.


  • [lundi 18 novembre 2002] (1 heure)
    • les fonctions peuvent avoir comme valeur de retour une fonction
      • composition de deux fonctions
      • curification d'une fonction
      • les continuations

    Suppléments:

    • La fonction map curifiée: map.scm

  • [mardi 12 novembre 2002] (2 heures)
    • récursion plate versus récursion profonde, cas de la fonction reverse
    • à votre tour d'être du bon côté du marteau (évaluation du cours)
    • les fonctions en Lisp sont des objets de première classe:
      • les fonctions peuvent être stockées dans des structures de données
      • les fonctions peuvent avoir comme paramètre des fonctions (on parle alors de fonction d'ordre supérieur)
        • map
        • for-each
        • fonctions avec nombre variable d'arguments
        • garder les éléments d'une liste qui possèdent une certaine propriété (application au tri-rapide)
        • combiner les éléments d'une liste entre-eux à l'aide d'une fonction

    Suppléments:

    • Une version itérative et récursive profonde de reverse: reverse.scm (ce n'est pas la version prédéfinie de la fonction).

  • [lundi 11 novembre 2002] (1 heure)
    • les fonctions de traitement des listes (suite): append et reverse
    • récursion terminale
    • la forme spéciale letrec

  • [mardi 5 novembre 2002] (2 heures)
    • Les formes spéciales de base and,or,not, et lambda
    • Variables globales et locales en Scheme, notion d'environnement
    • Les listes pour représenter des données:
      • les formes spéciales quote et eval
      • représentation graphique des listes
      • les fonctions de traitement des listes: car, cdr, cons, list, car, append, length, member, reverse, etc.

  • [lundi 4 novembre 2002] (1 heure)
    • Introduction aux langages fonctionnels
    • Particularités de Scheme: typé dynamiquement, portée statique, concis
    • Évaluation d'une expression en Scheme
    • Les formes spéciales de base if,let,define, display, write

  • [lundi 28 octobre 2002] (1 heure)
    • Les méthodes (suite et fin, alarme ou pas)
      • mécanisme d'appel d'une méthode

  • [mardi 22 octobre 2002] (2 heures)
    • Les méthodes (suite et alarme)
      • les macros (C) et les procédures en ligne (C++)
      • paramètres optionnels (cas de C++)
      • surdéfinition d'une méthode (en C++ ou Java)
      • surdéfinition d'un opérateur en C++
      • risquons nos vies à l'UdeM en restant dans une salle de cours pendant que l'alarme se déclenche

    Suppléments:

    • Exemple typique de classe C++, surdéfinition des opérateurs: les déclarations Rational.h, les définitions Rational.cc et le programme rat.cc,

  • [lundi 21 octobre 2002] (1 heure)
    • Les méthodes (suite)
      • passage de paramètre par nom
      • cas des tableaux à deux dimensions passés en paramètre (en C, en JAVA)
      • cas des méthodes passées en paramètre (C)

    Suppléments:

    • Illustration du passage par nom exemple.
    • Passage d'un tableau à 2 dimensions en paramètre en C: tab2.c.
    • Passage d'un tableau à 2 dimensions en paramètre en JAVA: Tab2.java.
    • Passage d'une méthode en paramètre: demo1.c.

  • [mardi 8 octobre 2002] (2 heures)
    • Représentation de types "utilisateur" classiques (suite et fin)
      • les structures, les unions
      • les pointeurs (pointeurs fous, fuite de mémoire, et garbage collector)
    • Les méthodes
      • les différents modes de passage des paramètres

  • [lundi 7 octobre 2002] (1 heure)
    • Représentation de types classiques
    • types primitifs (entiers, flottants, caractères, booléens)
    • type pseudo-primitif: string
    • types "utilisateur"
      • types ordinaux (énumérations et intervalles)
      • les tableaux (static, fixed stack-dynamic, stack-dynamic, head-dynamic)

  • [mardi 1 octobre 2002] (2 heures)
    • Concept de variable (nom,adresse,valeur,type,durée de vie et portée)
      • liens statiques et dynamiques
      • liens de typage
      • liens de stockage
      • vérification de type, langages fortement typés

  • [lundi 30 septembre 2002] (1 heure)
    • Étude d'un compilateur complet (analyse lexicale, syntaxique et sémantique) traduisant des sources écrits dans un sous-ensemble de C, en un byte-code réaliste interprétable par une machine à pile: Suite et fin !
      • présentation du byte-code
      • présentation de la machine à pile associée
      • comment générer le byte-code ?

    Suppléments:

    • Le mini-compilateur écrit par Marc Feeley et disponible dans les notes de cours du même auteur: tinyc.c.

  • [mardi 24 septembre 2002] (2 heures)
    • Analyse syntaxique montante (bottom-up) et descendante (top-down)
    • Principes d'écriture d'un analyseur syntaxique descendant récursif, grammaires LL1
    • Étude d'un compilateur complet (analyse lexicale, syntaxique et sémantique) traduisant des sources écrits dans un sous-ensemble de C, en un byte-code réaliste interprétable par une machine à pile:
      • codage de l'ASA

    Suppléments:

    • Le mini-compilateur écrit par Marc Feeley et disponible dans les notes de cours du même auteur: tinyc.c.

  • [lundi 23 septembre 2002] (1 heure)
    • Analyse lexicale, rôle et implémentations possibles (atomate / lex)
    • Écriture d'un analyseur lexical
      • Codage direct d'un automate
      • Flex

    Suppléments:

    • Le code d'un mini-analyseur lexical écrit en C: lex.c
    • Le code d'un mini-analyseur lexical écrit en flex, ift2030.lex
      Vous aimez flex ? Précipitez-vous sur la documentation en ligne également disponible dans les man-pages (man flex)
    • Un exemple de programme reconnu par les deux analyseurs précédants: prog.tordu

  • [mardi 17 septembre 2002] (2 heures)
    • Une grammaire est ambiguë s'il existe au moins une chaîne pour laquelle plusieurs arbres syntaxiques existent -> notion de précédance et d'associativité des opérateurs
    • Note concernant les notations pré- et post-fixée des expressions
    • Analyse lexicale, rôle et implémentations possibles (atomate / lex)
    • Un exemple de programme reconnu par les deux analyseurs précédants: prog.tordu

  • [lundi 16 septembre 2002] (1 heure)
    • Classification Chomskienne des langages (suite et fin?)
      • Les langages de type 2 (hors-context / context-free)
      • Quelques mots sur les langages de type 1 (contextuels)
      • Encore moins de mots sur les langages de type 0
    • Grammaires BNF (Backus Naur Form) et arbres syntaxiques abstraits (ASA)

  • [mardi 10 septembre 2002] (2 heures)

    • Brève histoire des langages de programmation (suite et fin)
    • Description des langages de programmation
      • Pourquoi ?
      • Moyens: tutoriels, manuels de référence, description formelle
      • Syntaxe versus sémantique
    • Classification chomskiennes des langages
      • Grammaire, dérivation
      • Les langages réguliers (ou langages de type 3)

  • [lundi 9 septembre 2002] (1 heure)

    • Choix des langages de programmation (suite et fin)
    • Implémentation des langages de programmation (compilation=traduction vs interprétation)
    • Brève histoire des langages de programmation

    Suppléments:

    • Le premier ordinateur électronique utilisable [eniac] (1946, UPenn)
    • Hiérarchie d'un sous-ensemble de langages marquants
    • Machine de Von Neumann
    • Exemple de petit code machine pour famille x86 (Intel):
      binaire    hex
      10001011   8B  \
      01000101   45   | lire 1er entier dans reg. AX
      00001010   0A  /
      00000011   03  \
      01000101   45   | lire 2em entier et ajouter a AX
      00010100   14  /
      
    • Que fait ce morceau de programme Pascal ?
      read(x);
      2: if x = 0 then goto 8;
      writeln(x);
      4: read(next);
      if next = x then goto 4;
      x := next;
      goto 2;
      8: ;
    • Compter les mots d'un texte et afficher les mots en ordre croissant de fréquence. Voici une idée des temps d'exécution: [temps vs formes], [temps vs mots ]
      Voici un exemple de corpus sur lequel appliquer ces programmes.

  • [mardi 3 septembre 2002] (2 heures)

    Bonne rentrée à toutes et tous. Notre premier cours commence avec quelques généralités:

    • Tour d'horizon du cours IFT2030, conseils d'usage, etc.
    • Quelques raisons pour l'étude de ce cours
    • Tour d'horizon des domaines d'application
    • Évaluation d'un langage, revue de quelques critères (non exhaustifs et souvent dépendants et/ou contradictoires: facilité de lecture/écriture, orthogonalité, sécurité, coût, support aux gros projets)


    [top]


  • Dernière mise à jour : Sun Jan 5 13:40:51 EST 2003
    dift2030@iro.umontreal.ca