Self-reference in function definition

0
votes

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

2
scopeschemelispsicpy-combinator

2 Answers

1
votes

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:

  1. It should evaluate M in environment E; let the result be x.
  2. It should modify environment 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.

0
votes

From the SICP perspective, this is not a self-referencing procedure because factorialA is a value, not procedure.

in Chapter 4 Representing Expressions which develops a scheme evaluator we have:

(define (definition-value exp)
  (if (symbol? (cadr exp))
      (caddr exp)
      (make-lambda (cdadr exp)   ; formal parameters
                   (cddr exp)))) ; body

What this means is that if the expression after define is a raw symbol like factorialA then it will evaluate the body of the expression immediately and assign its value to factorialA. But if it is a list like (factorialA) or (factorialA n) then it will create a lambda expression instead. When the lambda expression is evaluated a procedure is created meaning the body is only evaluated when the procedure is called.