![]() ![]() Lambda calculus sequence combinator how to#Since I don't have much experience debugging C# lambda expressions and I certainly don't understand much of the lambda calculus, I don't really know what's going on or how to fix it. and never ends up actually entering the factorial lambda. From what I can surmise from using the reduced form, it seems as if it just ends up calling Y(factorial(Y(factorial(Y(factorial(. However, in both cases (original and reduced forms of the Y combinator), I end up with a stack overflow exception. My factorial lambda looks like this (adapted from here): Lambda factorial = f => new Lambda(n => n = 1 ? 1 : n * f(n - 1)) Īnd I call it like this: int result = (int)(Y(factorial))(5) I first tried to typedef it with using, but that didn't work, so now it's defined with delegate dynamic Lambda(dynamic arg) ) I attempted to write them in C# like this: // Original Here's the reduced definition: Y g = g(Y g) Here's the first definition: Y = λf.(λx.f(x x))(λx.f(x x)) To do this, I thought of using the Lambda Calculus' Y combinator. factorial, although my functions are much more complicated) in one line. So, $Y$ is preferable in the sense that it confines the implementation details of looping into one function, so that the 'bodies' of recursive definitions can be written in the straight forward way.I'm trying to figure out how to write recursive functions (e.g. These details would need to be copied into every content function. f f$, but it complicates the content with some of the details of how the looping is being achieved. Typical notation for recursive definitions in practical languages is something like: One way of thinking about why $Y$ would be preferable is that it separates 'content' from 'plumbing'. It then proposes the first method as a better solution. We would like to have a generic solution, without a need for any re-writes:… This solves it but requires re-writing each recursive call as self-application. …The self-application achieves replication here, passing the function's lambda expression on to the next invocation as an argument value, making it available to be referenced and called there. If the second method works, then what is the point of using the Y combinator? Wikipedia says this about the second method: This once again outputs 120, but is more readable and straightforward in my opinion. They are equivalent in the lambda calculus nonetheless)Īn alternative method, which is the topic of my question, is as follows: F = lambda r : lambda n : 1 if n = 0 else n * r(r)(n - 1)įact = F(F) # r gets substituted with F, therefore the expression in the body becomes F(F) which is fact ![]() This is because the one at the start would cause a recursion depth exception. Lambda calculus sequence combinator code#(The Y combinator in the code differs from the one at the start of the question. factorial: Y = lambda f : (lambda x : f(lambda v : x(x)(v)))(lambda x : f(lambda v : x(x)(v)))į = lambda r : lambda n : 1 if n = 0 else n * r(n - 1)įact = Y(F) # same as F(Y(F)), therefore the r in the body becomes Y(F) which is fact ![]() It can be easily used to implement a recursive function, e.g. The Y combinator is defined as $$Y=\lambda f.(\lambda x. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |