2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Aug 9 '17 at 17:11
  • $\begingroup$ 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. $\endgroup$ – Gilles 'SO- stop being evil' Aug 9 '17 at 17:13
  • $\begingroup$ 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. $\endgroup$ – MarkokraM Aug 9 '17 at 20:22
  • $\begingroup$ I added more information. Hope it helps to see what I'm after. $\endgroup$ – MarkokraM Aug 10 '17 at 7:21
  • $\begingroup$ 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 $\endgroup$ – Andrej Bauer Aug 11 '17 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.