I'm studying dynamic/static scope with deep/shallow binding and running code manually to see how these different scopes/bindings actually work. I read the theory and googled some example exercises and the ones I found are very simple (like this one which was very helpful with dynamic scoping) But I'm having trouble understanding how static scope works.
Here I post an exercise I did to check if I got the right solution:
considering the following program written in pseudocode:
int u = 42;
int v = 69;
int w = 17;
proc add( z:int )
u := v + u + z
proc bar( fun:proc )
int u := w;
fun(v)
proc foo( x:int, w:int )
int v := x;
bar(add)
main
foo(u,13)
print(u)
end;
What is printed to screen
a) using static scope? answer=180
b) using dynamic scope and deep binding? answer=69 (sum for u = 126 but it's foo's local v, right?)
c) using dynamic scope and shallow binding? answer=69 (sum for u = 101 but it's foo's local v, right?)
PS: I'm trying to practice doing some exercises like this if you know where I can find these types of problems (preferable with solutions) please give the link, thanks!
Best Answer
Your answer for lexical (static) scope is correct. Your answers for dynamic scope are wrong, but if I'm reading your explanations right, it's because you got confused between
u
andv
, rather than because of any real misunderstanding about how deep and shallow binding work. (I'm assuming that youru
/v
confusion was just accidental, and not due to a strange confusion about values vs. references in the call tofoo
.)Correct.
Your parenthetical explanation is right, but your answer is wrong:
u
is indeed set to126
, andfoo
indeed localizesv
, but sincemain
printsu
, notv
, the answer is126
.The sum for
u
is actually97
(42+13+42
), but sincebar
localizesu
, the answer is42
. (Your parenthetical explanation is wrong for this one — you seem to have used the global variablew
, which is17
, in interpreting the statementint u := w
in the definition ofbar
; but that statement actually refers tofoo
's local variablew
, its second parameter, which is13
. But that doesn't actually affect the answer. Your answer is wrong for this one only becausemain
printsu
, notv
.)For lexical scope, it's pretty easy to check your answers by translating the pseudo-code into a language with lexical scope. Likewise dynamic scope with shallow binding. (In fact, if you use Perl, you can test both ways almost at once, since it supports both; just use
my
for lexical scope, then do a find-and-replace to change it tolocal
for dynamic scope. But even if you use, say, JavaScript for lexical scope and Bash for dynamic scope, it should be quick to test both.)Dynamic scope with deep binding is much trickier, since few widely-deployed languages support it. If you use Perl, you can implement it manually by using a hash (an associative array) that maps from variable-names to scalar-refs, and passing this hash from function to function. Everywhere that the pseudocode declares a local variable, you save the existing scalar-reference in a Perl lexical variable, then put the new mapping in the hash; and at the end of the function, you restore the original scalar-reference. To support the binding, you create a wrapper function that creates a copy of the hash, and passes that to its wrapped function. Here is a dynamically-scoped, deeply-binding implementation of your program in Perl, using that approach:
and indeed it prints
126
. It's obviously messy and error-prone, but it also really helps you understand what's going on, so for educational purposes I think it's worth it!