Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Fixed-point combinator
Summary
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.