In this explanation of Y-combinator (https://mvanier.livejournal.com/2897.html),
(define almost-factorial
(lambda (f)
(lambda (n)
(if (= n 0)
1
(* n (f (- n 1)))))))
(define factorialA (almost-factorial factorialA))
it says that the definition of factorialA would go into an infinite loop in standard scheme, however implementing it gives an error saying factorial A isn't defined.
I think this is expected as when we are defining (if not with a lambda) we are evaluating the definition which will end up calculating the arguments, one of which is the same function not yet defined.
Is this correct and how can we explain the above article then? Thanks
Consider the expression (define p M), where M is some expression and p is a variable.
Let's suppose we're evaluating this expression in environment E. Evaluating (define p M) should do two things:
M in environment E; let the result be x.E so that p is bound to x.So what should happen when we evaluate (define factorialA (almost-factorial factorialA)) in an environment E where factorialA is not already defined?
First, we try to evaluate (almost-factorial factorialA) in environment E. To do this, we first evaluate almost-factorial, which succeeds. We then evaluate factorialA, which fails because factorialA is not defined in environment E. Thus, the whole thing should be expected to fail.
On the other hand, if we try
(define (returns-factorialA) (almost-factorial (returns-factorialA)))
(define factorialA (returns-factorialA))
This does indeed run into an infinite loop. This is probably what the writer of the article was looking for.