The code below, under dynamic scope assumption, would return error.
(let ((f (lambda (g)
(lambda (n)
(if (zero? n)
1
(* n ((g g) (- n 1))))))))
((f f) 5))
My answer was 0, because:
n*(n-1)*(n-2)*(n-3)*(n-3)*(n-4)*1;; since the call with n=0, n bound to 0
0*0*0*0*1
What am I missing here?
(define test
(let ((x 10))
(lambda () x)))
Here we return lambda function from the scope where x is a local variable. Under lexical scope an environment gets attached to the created lambda function. This environment consists of the bound variables on top of the free variables that were available when the lambda function was being created -- here, x, bound to 10. Thus when this returned lambda function is called, its x can only be 10.
In dynamic scope the let is dead code. The lambda function that is created does not store its lexical environment and thus when it will be called, x will be looked up fresh, at the actual time of the call. The variable that was called x with value 10 will no longer exist by then. The x looked up by the lambda will be whatever you have x bound to, at the call time:
(let ((x 20))
(test))
; ==> 20
And of course:
(test); == ERROR: Unbound variable x
So to your code it's the same problem. Whatever g is when (lambda (n) ...) is evaluated, creating the lambda function, goes out of scope when that lambda function is returned, and thus when that returned lambda function is called, g will be looked up fresh, and will be whatever g is bound to at the time of calling, as before. In order for this to work in a dynamic scope you could do this:
(let ((f (lambda (g n)
(if (zero? n)
1
(* n (g g (- n 1)))))))
(f f 5))
The difference here is that g never goes out of scope. This works in both dynamic and lexical scope. You can simplify it for dynamic scope like this:
(let ((f (lambda (n) ; ((lambda (f) (f 5))
(if (zero? n) ; (lambda (n)
1 ; (if (zero? n)
(* n (f (- n 1))))))) ; 1
(f 5)) ; (* n (f (- n 1))))))
In lexical scope the f inside (lambda (n) ...) is unbound variable, but in a dynamic scope f is first established, and after the call (f 5) it remains available for all the nested calls, (f 4), (f 3) etc., until the evaluation of (f 5) inside (lambda (f) (f 5)) is finished; only then that f is disestablished, destroyed, when that lambda is exited returning the result of (f 5).
In Paul Grahams nice wrap-up of McCarthys original lisp paper he mentions that there was a bug in the paper. The very first higher order function, maplist, had x as the name for the list argument. In the demonstration diff he passes a function to maplist that has x as a parameter. These two collide after the first pair and thus it does not work because of dynamic scope. Dynamic scope is extremely error prone and in Common Lisp where all globals are dynamic, the *earmuffs* naming convention is a necessity to avoid countless hours finding the global that changed the function to do something completely different than expected.