# Can't evaluate original Y combinator, two other variants do work, what do I miss?

I have made an evaluator of Lambda expressions. I tried to do Y combinator, but for some reason I can't get the original one working:

$$λf.(λx.f \space (x \space x)) \space (λx.f \space (x \space x))\tag1$$

This is probably for a reason, I don't know how to interpret $f (x \space x)$ part, or my evaluator does it right-wise or call-by-value.

However these two variants of the Y combinator do work as expected:

$$λf.((λx.(f \space (𝜆y.((x \space x) \space y)))) \space (λx.(f \space (𝜆y.((x \space x) \space y))))) \tag2$$

and

$$λf.((λx.(x \space x)) \space (λx.(f \space (λy.((x \space x) y)))))\tag3$$

Latter is evidently a self-application version of the former one.

Already, I have found that most implementations use the latter two equations:

Javascript

http://kestas.kuliukas.com/YCombinatorExplained/

Python

https://github.com/bzanchet/pycombinator/blob/master/pycombinator.py#L194

Scheme

https://github.com/calincru/Y-Combinator#the-strict-applicative-order-y-combinator

I have added parentheses for the last two expression to make it clear the order of the evaluation. For the first case, I'm not totally sure, but when I interpret it like this:

$$λf.((λx.(f \space (x \space x))) \space (λx.(f \space (x \space x))))\tag4$$

it will cause infinite loop. Also self-application version of it would simply be:

$$λf.((λx.(x \space x)) \space (λx.(f \space (x \space x))))\tag5$$

Right?

I have used my own macro run on Hy language interpreter, so I rather discuss about the abstract implementation side of the problem than specific code. But this is how I'm applying Y combinator to the standard factorial function:

$$(((𝜆 f · ((𝜆 x · (f \space (x \space x))) \space (𝜆 x · (f \space (x \space x)))))\\ (𝜆 f · (𝜆 n · (if \space (= \space n \space 1) \space 1 \space (* \space n \space (f \space (dec \space n)))))))\\ 7)\tag6$$

Result should be: 5040.

Note: In Hy, prefix notation of the mathematical operations are used.

• What's the problem with the original one? Does your evaluiator crash (in which case this would be a coding issue, off-topic here), loop infinitely, give the wrong result...? What expression are you evaluating? We can help you understand why a particular term evaluates in a particular way, but we can't guess what your program is doing. – Gilles 'SO- stop being evil' Aug 9 '17 at 17:11
• About the parentheses: parentheses have no effect on the order of evaluation. They only affect how the term is parsed. If you aren't sure about that, I recommend that you draw a syntax diagram ($\lambda x.M$ is a tree with $\lambda$ at the root, $x$ as the left child and $M$ as the right child, etc.). Order of evaluation is about which path the evaluator takes through the tree to find something to evaluate. – Gilles 'SO- stop being evil' Aug 9 '17 at 17:13
• I think main problem is that I cannot decide what part is function and what argument at each part in the first expression. No crash, no infinite loop. If i provide factorial function to the first y combinator, either some sort of function or alternatively int error is returned. I will provide more information tomorrow. – MarkokraM Aug 9 '17 at 20:22
• I added more information. Hope it helps to see what I'm after. – MarkokraM Aug 10 '17 at 7:21
• It sounds to me like a problem with your your implementation of lambda calculus, i.e., the problem you're describing seems to be just a parsing error. How did you implement your language? I'll show you mine and you show me yours. Here's mine: plzoo.andrej.com/language/lambda.html – Andrej Bauer Aug 11 '17 at 13:13