Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Exactitude des compilateurs: Partie 1

Dans cours

CS-320: Computer language processing

We teach the fundamental aspects of analyzing and interpreting computer languages, including the techniques to build compilers. You will build a working compiler from an elegant functional language into machine code using a popular backend called LLVM (htt ...

Description

Cette séance de cours explore l'exactitude des compilateurs, en se concentrant sur la définition de l'exactitude, les projets de compilateur, l'exactitude du langage d'expression et la preuve de l'exactitude à l'aide du vérificateur Stainless pour Scala. Il traite des exemples de compilateurs vérifiés tels que CompCert, CakeML et Bedrock2, ainsi que des concepts de compilateurs certifiés par rapport aux compilateurs avérés corrects. La séance de cours se penche également sur la vérification formelle, l'énumération des programmes pour des tests rigoureux des compilateurs et l'importance de s'assurer que les compilateurs génèrent des programmes corrects. Il couvre le processus de compilation à une machine de pile, l'interprétation des expressions, et l'exécution de programmes compilés. L'instructeur souligne l'importance de la vérification formelle dans l'établissement de l'exactitude du programme et les défis associés aux compilateurs de certification.

Enseignant·e

Viktor Kuncak

Viktor Kunčak joined EPFL in 2007, after receiving a PhD degree from MIT. Since then has been leading the Laboratory for Automated Reasoning and Analysis and supervised at least 12 completed PhD theses. His works on languages, algorithms and systems for verification and automated reasoning. He served as an initiator and one of the coordinators of a European network (COST action) in the area of automated reasoning, verification, and synthesis. In 2012 he received a 5-year single-investigator European Research Council (ERC) grant of 1.5M EUR. His invited talks include those at Lambda Days, Scala Days, NFM, LOPSTR, SYNT, ICALP, CSL, RV, VMCAI, and SMT. A paper on test generation he co-authored received an ACM SIGSOFT distinguished paper award at ICSE. A PLDI paper he co-authored was published in the Communications of the ACM as a Research Highlight article. His Google Scholar profile reports an over-approximate H-index of 38. He was an associate editor of ACM Transactions on Programming Languages and Systems (TOPLAS) and served as a co-chair of conferences on Computer-Aided Verification (CAV), Formal Methods in Computer Aided Design (FMCAD), Workshop on Synthesis (SYNT), and Verification, Model Checking, and Abstract Interpretation (VMCAI). At EPFL he teaches courses on functional and parallel programming, compilers, and verification. He has co-taught the MOOC "Parallel Programming" that was visited by over 100'000 learners and completed by thousands of students from all over the world.

Source officielle

Concepts associés (32)

Vérification formelle

In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics. Formal verification can be helpful in proving the correctness of systems such as: cryptographic protocols, combinational circuits, digital circuits with internal memory, and software expressed as source code.

Correction d'un algorithme

Un algorithme est correct s'il fait ce qu'on attend de lui. Plus précisément, rappelons qu'un algorithme est décrit par une spécification des données sur lesquelles l'algorithme va démarrer son calcul et une spécification du résultat produit par l'algorithme. Démontrer la correction de l'algorithme consiste à démontrer que l'algorithme retourne, quand il calcule en partant des données, un objet qui est un des résultats escomptés et qui satisfait la spécification du résultat comme énoncé dans la description de l'algorithme.

Bootstrap (compilateur)

Le bootstrapping décrit en informatique les techniques fondées sur l'écriture d'un compilateur (ou d'un assembleur) dans le langage de programmation cible qu'il doit compiler. De ce fait, il s'agit d'une technique de développement (sur un même système) ou de portage (d'un système à l'autre), qui part d'un premier compilateur minimal écrit de façon classique, amorçant une suite de versions, chacune préférable à la précédente. un dialecte d'Algol 58, a été le premier langage à fournir un tel bootstrap.

Compile time

In computer science, compile time (or compile-time) describes the time window during which a language's statements are converted into 0s and 1s for the computer to understand. The term is used as an adjective to describe concepts related to the context of program compilation, as opposed to concepts related to the context of program execution (runtime). For example, compile-time requirements are programming language requirements that must be met by source code before compilation and compile-time properties are properties of the program that can be reasoned about during compilation.

Compilateur

En informatique, un compilateur est un programme qui transforme un code source en un code objet. Généralement, le code source est écrit dans un langage de programmation (le langage source), il est de haut niveau d'abstraction, et facilement compréhensible par l'humain. Le code objet est généralement écrit en langage de plus bas niveau (appelé langage cible), par exemple un langage d'assemblage ou langage machine, afin de créer un programme exécutable par une machine.

Afficher plus

Séances de cours associées (29)

Exactitude des compilateurs: Partie 2

Explore l'exactitude des compilateurs, en mettant l'accent sur l'évaluation des expressions, la compilation bytecode et les opérations de pile.

Vérification des compilateurs : défis et avantages

Examine les défis et les avantages de la vérification des compilateurs, en soulignant l'importance de la vérification des compilateurs pour les logiciels critiques.

Compilateur de vérification: Approche Spec#

Explore le système de programmation Spec#, en se concentrant sur un compilateur de vérification pour C# 2.0.

Introduction à la vérification formelle

Introduit la vérification formelle, en mettant l'accent sur la preuve rigoureuse de l'exactitude du système et l'utilisation de modèles mathématiques.

Préfixe, Infix, Postfix et génération de code

Explore les notations de préfixe, d'infixe et de postfixe dans les expressions et leur rôle dans la génération de code.

Afficher plus

Concepts associés (32)

Vérification formelle

Correction d'un algorithme

Bootstrap (compilateur)

Compile time

Compilateur

Afficher plus