Typed lambda calculusA typed lambda calculus is a typed formalism that uses the lambda-symbol () to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a type depends on the calculus considered (see kinds below). From a certain point of view, typed lambda calculi can be seen as refinements of the untyped lambda calculus, but from another point of view, they can also be considered the more fundamental theory and untyped lambda calculus a special case with only one type.
Lambda-calculLe lambda-calcul (ou λ-calcul) est un système formel inventé par Alonzo Church dans les années 1930, qui fonde les concepts de fonction et d'application. On y manipule des expressions appelées λ-expressions, où la lettre grecque λ est utilisée pour lier une variable. Par exemple, si M est une λ-expression, λx.M est aussi une λ-expression et représente la fonction qui à x associe M. Le λ-calcul a été le premier formalisme pour définir et caractériser les fonctions récursives : il a donc une grande importance dans la théorie de la calculabilité, à l'égal des machines de Turing et du modèle de Herbrand-Gödel.
Lambda cubethumb|Le lambda-cube. Initialement proposé par Henk Barendregt, le -cube permet de visualiser les différentes dimensions pour lesquelles le calcul des constructions apporte une généralisation par rapport au lambda-calcul simplement typé où un terme ne peut dépendre que d'un autre terme. Chaque axe représente une nouvelle forme d'abstraction : Terme dépendant de type : le polymorphisme ; Type dépendant de type : présence d'opérateurs de types ; Type dépendant de terme. Catégorie:Calculabilité Catégorie:Théor
Calcul des constructionsLe calcul des constructions (CoC de l'anglais calculus of constructions) est un lambda-calcul typé d'ordre supérieur dans lequel les types sont des valeurs de première classe. Il est par conséquent possible, dans le CoC, de définir des fonctions qui vont des entiers vers les entiers, mais aussi des entiers vers les types ou des types vers les types. Le CoC est fortement normalisant, bien que, d'après le théorème d'incomplétude de Gödel, il soit impossible de démontrer cette propriété dans le CoC lui-même, puisqu'elle implique sa cohérence.
Simply typed lambda calculusThe simply typed lambda calculus (), a form of type theory, is a typed interpretation of the lambda calculus with only one type constructor () that builds function types. It is the canonical and simplest example of a typed lambda calculus. The simply typed lambda calculus was originally introduced by Alonzo Church in 1940 as an attempt to avoid paradoxical use of the untyped lambda calculus. The term simple type is also used to refer extensions of the simply typed lambda calculus such as products, coproducts or natural numbers (System T) or even full recursion (like PCF).
Sémantique opérationnelleEn informatique, la sémantique opérationnelle est l'une des approches qui servent à donner une signification aux programmes informatiques d'une manière rigoureuse, mathématiquement parlant (voir Sémantique des langages de programmation). Une sémantique opérationnelle d'un langage de programmation particulier décrit comment chaque programme valide du langage doit être interprété en termes de suite d'états successifs dans la machine. Cette suite d'états est la signification du programme.
Sémantique dénotationnelleEn informatique, la sémantique dénotationnelle est une des approches permettant de formaliser la signification d'un programme en utilisant les mathématiques. Parmi les autres approches, on trouve la sémantique axiomatique et la sémantique opérationnelle. Cette discipline a été introduite par Christopher Strachey et Dana Scott. En général, la sémantique dénotationnelle utilise des techniques de programmation fonctionnelle pour décrire les langages informatiques, les architectures et les programmes.
PapierLe papier est un matériau en feuilles minces fabriqué à partir de fibres végétales. C'est un support d'écriture et de dessin avec de nombreuses autres applications. On appelle carton un papier épais et rigide. L'usage du papier est attesté il y a en Chine. Il s'y fabrique à partir de plantes riches en cellulose. L'invention de la xylographie au en augmente l'usage et la fabrication. À la même époque, il se diffuse dans le monde musulman, où les fabricants utilisent le chiffon, puis en Occident où on lui ajoute de la colle pour l'adapter à l'écriture à la plume.
Pure type systemNOTOC In the branches of mathematical logic known as proof theory and type theory, a pure type system (PTS), previously known as a generalized type system (GTS), is a form of typed lambda calculus that allows an arbitrary number of sorts and dependencies between any of these. The framework can be seen as a generalisation of Barendregt's lambda cube, in the sense that all corners of the cube can be represented as instances of a PTS with just two sorts. In fact, Barendregt (1991) framed his cube in this setting.
Programmation fonctionnelleLa programmation fonctionnelle est un paradigme de programmation de type déclaratif qui considère le calcul en tant qu'évaluation de fonctions mathématiques. Comme le changement d'état et la mutation des données ne peuvent pas être représentés par des évaluations de fonctions la programmation fonctionnelle ne les admet pas, au contraire elle met en avant l'application des fonctions, contrairement au modèle de programmation impérative qui met en avant les changements d'état.
HaskellHaskell est un langage de programmation fonctionnel fondé sur le lambda-calcul et la logique combinatoire. Son nom vient du mathématicien et logicien Haskell Curry. Il a été créé en 1990 par un comité de chercheurs en théorie des langages intéressés par les langages fonctionnels et l'évaluation paresseuse. Le dernier standard est Haskell 2010 : c'est une version minimale et portable du langage conçue à des fins pédagogiques et pratiques, dans un souci d'interopérabilité entre les implémentations du langage et comme base de futures extensions.
Sémantique des langages de programmationEn informatique théorique, la sémantique formelle (des langages de programmation) est l’étude de la signification des programmes informatiques vus en tant qu’objets mathématiques. Comme en linguistique, la sémantique, appliquée aux langages de programmation, désigne le lien entre un signifiant, le programme, et un signifié, objet mathématique. L'objet mathématique dépend des propriétés à connaître du programme. La sémantique est également le lien entre : le langage signifiant : le langage de programmation le langage signifié : logique de Hoare, automates.
Système FLe est un formalisme logique qui permet d'exprimer de façon très riche et très rigoureuse des fonctions et d'y démontrer formellement des propriétés difficiles. Plus précisément, le (également connu sous le nom de lambda-calcul polymorphe ou de lambda-calcul du second ordre) est une extension du lambda-calcul simplement typé introduite indépendamment par le logicien Jean-Yves Girard et par l'informaticien John C. Reynolds. Ce système se distingue du lambda-calcul simplement typé par l'existence d'une quantification universelle sur les types qui permet d'exprimer du polymorphisme.
Papier couchéthumb|Tranche d'un papier couché.1 - papier2 - couche d'égalisation3 - couche de lissage Le papier ou carton couché est un papier ou carton dont la surface est recouverte d'une ou plusieurs couches généralement constituées de produits minéraux (pigments) en mélange avec des liants et des produits d'addition divers. Quelque 40 % des papiers impression-écriture et près de 50 % des cartons sont couchés. L'opération de couchage consiste à déposer sur une ou sur les deux faces d'une feuille de papier ou de carton — appelée support — un enduit à base de pigments fins.
Normal form (abstract rewriting)In abstract rewriting, an object is in normal form if it cannot be rewritten any further, i.e. it is irreducible. Depending on the rewriting system, an object may rewrite to several normal forms or none at all. Many properties of rewriting systems relate to normal forms. Stated formally, if (A,→) is an abstract rewriting system, x∈A is in normal form if no y∈A exists such that x→y, i.e. x is an irreducible term. An object a is weakly normalizing if there exists at least one particular sequence of rewrites starting from a that eventually yields a normal form.
Type dépendantEn Informatique et en Logique, un type dépendant est un type qui peut dépendre d'une valeur définie dans le langage typé. Les langages Agda et Gallina (de l'assistant de preuve Coq) sont des exemples de langages à type dépendant. Les types dépendants permettent par exemple de définir le type des listes à n éléments. Voici un exemple en Coq. Inductive Vect (A: Type): nat -> Type := | nil: Vect A 0 | cons (n: nat) (x: A) (t: Vect A n): Vect A (S n).
Programmation purement fonctionnelleEn informatique, la programmation purement fonctionnelle est un paradigme de programmation qui considère toutes les opérations comme l'évaluation de fonctions mathématiques. L'état et les objets immuables sont généralement modélisés à l'aide d'une logique temporelle, en tant que variables explicites représentant l'état du programme à chaque étape de son exécution : l'état d'une variable est transmis en tant que paramètre d'entrée d'une fonction de transformation d'état, qui renvoie l'état mis à jour en tant que partie de sa valeur de retour.
SemanticsSemantics () is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and computer science. In English, the study of meaning in language has been known by many names that involve the Ancient Greek word σῆμα (sema, "sign, mark, token"). In 1690, a Greek rendering of the term semiotics, the interpretation of signs and symbols, finds an early allusion in John Locke's An Essay Concerning Human Understanding: The third Branch may be called σημειωτική [simeiotikí, "semiotics"], or the Doctrine of Signs, the most usual whereof being words, it is aptly enough termed also λογικὴ, Logick.
Logique combinatoireEn logique mathématique, la logique combinatoire est une théorie logique introduite par Moses Schönfinkel en 1920 lors d'une conférence et développée dès 1929 par Haskell Brooks Curry pour supprimer le besoin de variables en mathématiques, pour formaliser rigoureusement la notion de fonction et pour minimiser le nombre d'opérateurs nécessaires pour définir le calcul des prédicats à la suite de Henry M. Sheffer. Plus récemment, elle a été utilisée en informatique comme modèle théorique de calcul et comme base pour la conception de langages de programmation fonctionnels.
Total functional programmingTotal functional programming (also known as strong functional programming, to be contrasted with ordinary, or weak functional programming) is a programming paradigm that restricts the range of programs to those that are provably terminating. Termination is guaranteed by the following restrictions: A restricted form of recursion, which operates only upon 'reduced' forms of its arguments, such as Walther recursion, substructural recursion, or "strongly normalizing" as proven by abstract interpretation of code.
