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

Type Inférence: Hindley-Milner Aperçu

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 couvre l'inférence de type dans les langages typés statiquement, en se concentrant sur des algorithmes tels que la propagation ascendante et l'inférence basée sur les contraintes Hindley-Milner. Il explique comment affecter des types aux expressions de programme et introduit des règles de type pour les variables, les constantes, les paires et les fonctions. La séance de cours explore également l'inférence de type Hindley-Milner, en soutenant les types structurés génériques et en présentant des exemples d'inférence de type dans des programmes sans annotations.

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

Proximité ontologique

Informatique théorique

Théorie des langages de programmation: Langage de programmation de haut niveau

Concepts associés (30)

Type system

In computer programming, a type system is a logical system comprising a set of rules that assigns a property called a type (for example, integer, floating point, string) to every "term" (a word, phrase, or other set of symbols). Usually the terms are various constructs of a computer program, such as variables, expressions, functions, or modules. A type system dictates the operations that can be performed on a term. For variables, the type system determines the allowed values of that term.

Théorie des types

En mathématiques, logique et informatique, une théorie des types est une classe de systèmes formels, dont certains peuvent servir d'alternatives à la théorie des ensembles comme fondation des mathématiques. Ils ont été historiquement introduits pour résoudre le paradoxe d'un axiome de compréhension non restreint. En théorie des types, il existe des types de base et des constructeurs (comme celui des fonctions ou encore celui du produit cartésien) qui permettent de créer de nouveaux types à partir de types préexistant.

Substructural type system

Substructural type systems are a family of type systems analogous to substructural logics where one or more of the structural rules are absent or only allowed under controlled circumstances. Such systems are useful for constraining access to system resources such as , locks, and memory by keeping track of changes of state that occur and preventing invalid states. Several type systems have emerged by discarding some of the structural rules of exchange, weakening, and contraction: Ordered type systems (discard exchange, weakening and contraction): Every variable is used exactly once in the order it was introduced.

Inférence de types

L'inférence de types est un mécanisme qui permet à un compilateur ou un interpréteur de rechercher automatiquement les types associés à des expressions, sans qu'ils soient indiqués explicitement dans le code source. Il s'agit pour le compilateur ou l'interpréteur de trouver le type le plus général que puisse prendre l'expression. Les avantages à disposer de ce mécanisme sont multiples : le code source est plus aéré, le développeur n'a pas à se soucier de retenir les noms de types, l'interpréteur fournit un moyen au développeur de vérifier (en partie) le code qu'il a écrit et le programme est peu modifié en cas de changement de structure de données.

Conversion de type

En informatique la conversion de type, le transtypage ou la coercition (cast en anglais) est le fait de convertir une valeur d'un type (source) dans un autre (cible). On distingue trois formes de conversion (dont un seul mérite vraiment le nom de conversion) suivant la relation de sous-typage existant entre les types source et cible : la conversion entre types incomparables ; la coercition ascendante (transtypage vers le haut) ; la coercition descendante (transtypage vers le bas). C'est la coercition la plus ancienne historiquement.

Afficher plus

Séances de cours associées (35)

Fondements de Scala: Modélisation et Systèmes de Type

Couvre les fondements de Scala, y compris la modélisation des types récursifs, des types paramétrés et de la variance.

Type Inférence

Explore l'inférence de type dans les langages typés statiquement, en utilisant des algorithmes pour attribuer des types aux expressions de programme avec précision.

Programmation Fonctionnelle Vérifiée : Nicolas Voirol défense de thèse de doctorat publique

Explore la programmation fonctionnelle vérifiée, la vérification formelle, les résolveurs SMT, la vérification de type, les fonctionnalités Scala, l'automatisation et les types dépendants.

Compiler Extension Lab

Couvre le Compiler Extension Lab, en se concentrant sur l'ajout de nouvelles fonctionnalités à un compilateur de langage fonctionnel simple.

Types dans Lambda Calculus

Couvre les types dans le calcul lambda, y compris la définition des types, la spécification des règles et la preuve de la solidité.

Afficher plus

Concepts associés (30)

Type system

Théorie des types

Substructural type system

Inférence de types

Conversion de type

Afficher plus