![]() ![]() ![]() In this article, we’ll go the other way around: I’ll start by describing, in simple terms, the essence of the Y combinator - or how to make recursion work without recursive definitions, and from there I will derive the usual Y combinator. Most articles I’ve seen dedicated to explaining the Y combinator start by showing you the Y combinator, which in itself is fairly inscrutable, and then trying to explain why it works. Y allows one to define recursive functions without using self-referential definitions. In fact, this technique means that once we have found one complete set of combinators $J$ and a good technique for writing $\lambda$-terms as $J$-terms, we can use this technique to get the representation in terms of any other finite, complete set of combinators.The Y combinator is a central concept in lambda calculus, which is the formal foundation of functional languages. Since there are only finitely many terms in $J$, the substitution step is also linear time and linear space. Then, substitute each term in $J$ for an equivalent term in the SKI calculus. Then, come up with a linear time and linear space algorithm for taking $\lambda$ closed terms and turning them into $J$ closed terms. The idea is this: First, extend the SKI combinators to a new, larger finite set $J$ of combinators. So it's a good thing that there is a linear time and linear space algorithm for doing this translation. If you want to use SKI as a step in compiling a language which will be used in real-world software, it's critical that the translation not blow up the size of the code super-linearly. Our algorithm instead rewrites it as $S (Kf) I$. One optimisation which reduces output size is looking for opportunities to use $\eta$-reduction, such as with the term $\lambda x. So the final result should be $S (S (K S) (S (KK) I)) (S (S (K S) (S (KK) I)) (KI))$ unless I've messed something up (which is very plausible).Įdit: this is definitely not the most efficient algorithm for taking a closed term in the $\lambda$ calculus and producing an equivalent term in the SKI calculus, either in running time or in the size of the output. Kf)$, which becomes $S (K S) (S (KK) I)$. S (Kf) (S (Kf) I)$, which would produce a lengthy but correct term. Note that we have eliminated the variable $x$ and all instances of $\lambda$ abstraction. x))$, which we would then rewrite as $S (Kf)(S (Kf) I)$. fx)$, which we would then rewrite as $S (Kf) (S (\lambda x. We would write this according to rule 3 as $S (\lambda x. f(fx)$, we would first simplify $\lambda x. The equality in rule 2 only holds when $x$ does not occur free in $c$, so applying this rule out of context can lead to an incorrect result. ![]() Rule 2 says that when $x$ and $c$ are distinct variables or when $c$ is either $S, K$ or $I$, we should rewrite $\lambda x. M$ in this language, where $M$ has no $\lambda$ abstractions in it, and outputting an equivalent term with no abstractions at all in it, where the free variables in the resulting term all occur free in $\lambda x. The rules provide an algorithm for taking a term $\lambda x. To be precise, consider the language of the $\lambda$ calculus extended with $S, K,$ and $I$. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |