Langages de programmation et compilation 2018-2019

Cours donné aux élèves de première année à l'École Normale Supérieure.

• Cours le vendredi de 8:30 à 10:30 en salle U ou V
• TDs le jeudi ou le vendredi, de 10h45 à 12h15 en salle INFO 4 NIR avec Lélio Brun
  
• Évaluation : un examen + un projet

Cours

• Cours 1 (21 septembre 2018) : Mise à niveau OCaml
  • transparents
  • code OCaml de la démo : wall.ml
  • Il y a un polycopié spécifique pour ce premier cours. (Version à l'italienne si vous souhaitez l'imprimer.)

• Cours 2 (28 septembre 2018) : Aperçu de la compilation / Assembleur x86-64
  • transparents
  • à propos du problème des N-reines :
    • le code C / le code x86-64
    • de la lecture : Henry S. Warren Hacker's Delight (à la bibliothèque)

• Cours 3 (5 octobre 2018) : Syntaxe abstraite / Sémantique / Interpréteurs
  • transparents

• Cours 4 (12 octobre 2018) : Typage
  • transparents

• Cours 5 (19 octobre 2018) : Analyse lexicale
  • transparents

• pas de cours les vendredis 26 octobre et 2 novembre
• Cours 6 (9 novembre 2018) : Analyse syntaxique 1/2
  • transparents
  • le fichier arith_expr.mll utilisé au début du cours

• Cours 7 (16 novembre 2018) : Analyse syntaxique 2/2
  • transparents

• Cours 8 (23 novembre 2018) : mode de passage des paramètres
  • transparents

• Cours 9 (30 novembre 2018) : Compilation des langages fonctionnels
  • transparents

• Cours 10 (7 décembre 2018) : Compilation des langages objets
  • transparents

• Cours 11 (14 décembre 2018) : Production de code efficace, partie 1
  • transparents

• Cours 12 (21 décembre 2018) : Production de code efficace, partie 2
  • transparents

• Cours 13 (11 janvier 2019) : Allocation mémoire
  • transparents

TD

• TD 1 (21/26 sep) : Mise à niveau OCaml
• TD 2 (28 sep/4 oct) : Assembleur x86-64
• TD 3 (5/11 oct) : Interprète mini-Python
• TD 4 (12/18 oct) : Algorithme W
• TD 5 (19 oct/8 nov) : Construction d'automates déterministes à partir d'expressions régulières
• pas de TD les 25-26 octobre ni les 1-2 novembre
• TD 6 (9/15 nov) : Analyse descendante
• TD 7 (16/22 nov) : Analyse syntaxique d'un petit langage
• TD 8 (23/29 nov) : Aide au projet
• TD 9 (30 nov/6 déc) : Aide au projet
• TD 10 (7/13 déc) : Production de code
• TD 11 (14/20 déc) : Coloriage de graphe
• TD 12 d'aide au projet vendredi 21 décembre / mardi 8 janvier
• TD 13 (11/17 jan) : GC stop & copy

Projet

Sujet (version 2 - 22 octobre)

Quelques tests sont fournis (les télécharger : tests-3-dec.tar.gz). Ce script shell peut être utilisé pour automatiser les tests, avec la syntaxe ./test -n binaire-compilo où n vaut 1 (tests parseur), 2 (tests typage) ou 3 (tests production de code).

Un module OCaml est fourni pour construire du code x86-64 : x86_64.ml / x86_64.mli / documentation / télécharger.
Libre à vous de le compléter si besoin.

Le projet est à rendre en deux fois :

• partie 1 (analyse syntaxique et typage uniquement) pour le dimanche 9 décembre 18:00 ;
• partie 2 (projet complet, avec production de code) pour le mercredi 9 janvier 18:00.

Il est conseillé de procéder construction par construction (que ce soit pour le typage ou pour la production de code), dans cet ordre : affichage, arithmétique, variables locales, fonctions (globales et monomorphes), classes (monomorphes), polymorphisme, fonctions de première classe.

Le rapport rendu avec le projet doit notamment aider à la compréhension du code du projet.

Il y aura des soutenances de projet en janvier (après le rendu du projet).

• La soutenance de projet dure 30 minutes et comporte deux parties : 15 minutes environ consacrées à la présentation du projet (approche choisie, partage du travail, points forts, démo, etc.) suivies de 15 minutes de questions.
• Un vidéo-projecteur sera à votre disposition. Vous pouvez préparer des diapositives si vous le souhaitez, mais cela n'est pas obligatoire.
• Vous pouvez profiter de la soutenance pour montrer des morceaux de code dont vous êtes particulièrement fiers.

Examen

Les notes de cours manuscrites ou reprographiées sont les seuls documents autorisés.

Archives : janvier 2009 (corrigé) / janvier 2010 (corrigé) / janvier 2011 (corrigé) / janvier 2012 (corrigé) / janvier 2013 (corrigé) / janvier 2014 (corrigé) / janvier 2015 (corrigé) / janvier 2016 (corrigé) / janvier 2017 (corrigé) / janvier 2018 (corrigé) / janvier 2019 (corrigé)

Liens / Bibliographie

Outils

• Assembleur x86-64
  • des ressources (en anglais) sur cette page d'Andrew Tolmach et en particulier ces notes
  • le fascicule x86-64 Machine-Level Programming de Bryant et O'Hallaron (en anglais)
  • le debugger Nemiver fonctionne sur du code x86-64 (exécution pas à pas, visualisation des registres, etc.)
  • le site godbolt.org permet de comparer facilement le code assembleur produit par de nombreux compilateurs

• OCaml : vous trouverez de nombreuses ressources sur ocaml.org.
  Pour travailler à l'ENS ou sur vos machines, voici quelques suggestions d'environnement de travail OCaml.

• Menhir, un outil d'analyse syntaxique (manuel)
  On peut l'installer avec opam.

• pour les débutants : une brève introduction au terminal GNU/Linux et une brève documentation des commandes les plus utiles

Cartes de référence

• OCaml : langage / bibliothèque / outils
• Emacs : général / mode Tuareg pour OCaml

Ouvrages en rapport avec le cours

• Alfred V. Aho, Monica S. Lam, Ravi Sethi et Jeffrey D. Ullman Modern Compilers: Principles, Techniques, and Tools.
  Dit « le dragon ». Traduit en français (Compilateurs : principes, techniques et outils).
• Benjamin C. Pierce Types and Programming Languages
• Randal E. Bryant et David R. O'Hallaron Computer Systems: A Programmer's Perspective

For foreign students not yet fluent in French

• A tiny French-English dictionary
• a rough correspondence between the lectures and chapters from the books above (which are in English):

  	Lecture	Chapters
  2	Assembly	Bryant & O'Hallaron 3
  3	Semantics	Pierce 3-4-5
  4	Typing	Pierce 8-9-10 et 22
  5	Lexical analysis	Dragon 3
  6-7	Syntactic analysis	Dragon 4
  11	Memory allocation	Bryant & O'Hallaron 9