Dynamic Scoping - Deep Binding vs Shallow Binding

Question

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)

Etruria

Is this Python? is your question language agnotic? please specify – Alewife

Answer 1

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.

Etruria

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? – Lebanon

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). – Coakley

@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. – Micrococcus

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! – Micrococcus

Answer 2

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

Ovovitellin

Answer 3

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

Harijan

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. – Awry