30

I've been trying to get my head around shallow binding and deep binding, wikipedia doesn't do a good job of explaining it properly. Say I have the following code, what would the output be if the language uses dynamic scoping with

a) deep binding

b) shallow binding?

x: integer := 1
y: integer := 2

procedure add
  x := x + y

procedure second(P:procedure)
  x:integer := 2
  P()

procedure first
  y:integer := 3
  second(add)

----main starts here---
first()
write_integer(x)
imz -- Ivan Zakharyaschev
  • 4,921
  • 6
  • 53
  • 104
John Jiang
  • 11,069
  • 12
  • 51
  • 60

3 Answers3

30

Deep binding binds the environment at the time the procedure is passed as an argument

Shallow binding binds the environment at the time the procedure is actually called

So for dynamic scoping with deep binding when add is passed into a second the environment is x = 1, y = 3 and the x is the global x so it writes 4 into the global x, which is the one picked up by the write_integer.

Shallow binding just traverses up until it finds the nearest variable that corresponds to the name so the answer would be 1.

John Jiang
  • 11,069
  • 12
  • 51
  • 60
  • 2
    For shallow binding, if I were to place "write_integer(y)" inside of procedure second (before P() ) would I get 3 or 2 ? Also for shallow binding, can I not change the value of a global variable? – vvMINOvv Feb 14 '12 at 00:30
  • 1
    The dynamic scope with shallow binding would print "5". This is because dynamic scope uses the bindings (variable-value combinations) from the method it's called from. So the dynamic scope with shallow binding would use the binding `x = 2`, unlike the dynamic scope with deep binding which would use (as @jjia6395 said) `x = 1` (the binding from when `add` was passed into the method `second` as a parameter). – Antoine Dahan Oct 09 '14 at 00:47
  • @AntoineDahan not if `second` dynamically introduces the new binding for a new variable which happens to be named `x` (as evident by its use of `x:integer := 2` instead of `x := 2`), so `add` (called from `second`, while `second` is alive) changes that dynamically created `x` to 5. But `write_integer(x)` references the global `x`. So, this pseudocode is misleading. it should've used "=" in definitions, like `x:integer = 1`, and ":=" in mutating assignments, like `x := x + y`. – Will Ness Dec 29 '15 at 12:44
  • That said, I object to this misuse of terminology -- in LISP context, where they first appeared, "deep" and "shallow" are just implementation techniques for dynamic *or* lexical scoping, and can be used to implement *both*, so are indistinguishable from within a program if implemented correctly. What's called "deep" binding here is just a misunderstanding - it should instead be talking about "free var resolution time" and make it *explicit* by writing `second( closed(add,(x,y)) )` instead. It's still a dynamic name resolution, in both cases. You just want 2 freeze'em. So freeze'em. Explicitly! – Will Ness Dec 29 '15 at 12:54
0

a) In deep binding we deal with the environment of add, in which x refers to the global x and y refers to the y local to first (the last executed function which has a declaration of y)

x (global) = x (global) + y (local) : x = 1 + 3 = 4

b) In shallow binding, we deal with the environment of second, in which x refers to the x local to second and y refers to the y local to first (the last executed function which has a declaration of y)

x (local) = x (local) + y (local) : x = 2 + 3 = 5

BUT : write_integer(x) outputs the global x which is equal to 1

Finally

a) 4

b) 1

El Hadji Bassirou Toure
  • 1
  • 1
-3

shallow binding should be 5. definations: http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=15&lngWId=6

pranav
  • 1
  • 9
    No, with shallow binding it outputs `1`, as jjia6395 says. This is because the call to `P()` modifies the `x` that is local to `second`, which then disappears when `second` returns. The call to `write_integer(x)` prints the global `x`, which was not modified. – ruakh Feb 06 '12 at 22:03