Scheme and Shallow Binding

问题:

 (define make (lambda (x) (lambda (y) (cons x (list y)))))

 (let ((x 7)
       (p (make 4)))
   (cons x (p 0)))

I'm new to Scheme and functional program, so I am a bit clunky with walking through programs, but I get that if I used deep binding this program will return (7 4 0). Makes sense. What would this program do using shallow binding? I get this may sound dumb but is the p in the line with cons a redefinition? So in that case, we would return (7 0)?

Basically, I understand the concept of deep v. shallow binding, but I feel like I'm jumbling it up when looking at Scheme because I'm not crazy familiar with it.

回答1:

See this wikipedia article for a discussion on scoping (it mentions lexical/dynamic scoping and deep/shallow binding) bearing in mind that Scheme is lexically scoped. Will Ness' answer provides additional information. For now, let's see step-by-step what's happening in this snippet of code:

; a variable called x is defined and assigned the value 7
(let ((x 7)
; make is called and returns a procedure p, inside its x variable has value 4
      (p (make 4)))
; 7 is appended at the head of the result of calling p with y = 0
  (cons x (p 0)))

=> '(7 4 0)

Notice that in the second line a closure is created in the lambda returned by make, and the variable x inside will be assigned the value 4. This x has nothing to do with the outer x, because Scheme is lexically scoped.

The last line is not a redefinition, as mentioned in the previous paragraph the x inside make is different from the x defined in the let expression.

回答2:

Deep or shallow binding is an implementational technique and can not be observed from inside the program. The difference for the programmer is between lexical and dynamic scoping rules, but both can be implemented with any of the two techniques (i.e. one notion has got nothing to do with the other).

Deep or shallow refers to the choice of stack frame to hold a given outer scoped variable's binding. In deep binding there is a chain of frames to be accessed until the correct frame is entered holding the record for the variable; in shallow binding all bindings are present in one, shallow environment. See also "rerooting" (which only makes sense in the context of shallow binding implementation of lexical scoping).

To your specific question, under lexical scoping rules your code would return (7 4 0) and under dynamic - (7 7 0), because the call ((lambda(y) (list x y)) 0) is done inside the dynamic scope of x=7 binding (as a side note, (cons x (list y)) is the same as (list x y)):

x = 7
p = (lambda (y) (list x y))      ; x=4 is unused, in p=(make 4)
(cons 7 (p 0)) == (list 7 7 0)   ; 'x' in this line and in lambda body for p
                                 ;   both refer to same binding that is
                                 ;   in effect, i.e. x=7