Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fixed-point combinator
Résumé
In mathematics and computer science in general, a fixed point of a function is a value that is mapped to itself by the function.
In combinatory logic for computer science, a fixed-point combinator (or fixpoint combinator) is a higher-order function that returns some fixed point of its argument function, if one exists.
Formally, if the function f has one or more fixed points, then
and hence, by repeated application,
In the classical untyped lambda calculus, every function has a fixed point.
A particular implementation of fix is Curry's paradoxical combinator Y, represented by
In functional programming, the Y combinator can be used to formally define recursive functions in a programming language that does not support recursion.
This combinator may be used in implementing Curry's paradox. The heart of Curry's paradox is that untyped lambda calculus is unsound as a deductive system, and the Y combinator demonstrates this by allowing an anonymous expression to represent zero, or even many values. This is inconsistent in mathematical logic.
Applied to a function with one variable, the Y combinator usually does not terminate. More interesting results are obtained by applying the Y combinator to functions of two or more variables. The additional variables may be used as a counter, or index. The resulting function behaves like a while or a for loop in an imperative language.
Used in this way, the Y combinator implements simple recursion. In the lambda calculus, it is not possible to refer to the definition of a function inside its own body by name. Recursion though may be achieved by obtaining the same function passed in as an argument, and then using that argument to make the recursive call, instead of using the function's own name, as is done in languages which do support recursion natively. The Y combinator demonstrates this style of programming.
An example implementation of Y combinator in two languages is presented below.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.