CS 345 slide 233 Spring 20053 April 2005Bindings and ScopesDefinitions bind names to things:function f (int x) : int{ return x^2;}• binds name f tothe function thatreturns the squareof its argumentint z;…z := 4;• binds name z to a specific memory location;• binds z’s location to thevalue 4Function applications bind parameter names toarguments: f(9) binds the x in f’s body to 9.In each of int x;function f(int x)   the occurrence of x is abinding occurrenceA binding’s scope= the textual region in which any occurrence ofthe name is defined by the binding.CS 345 slide 234 Spring 20053 April 2005Free namesThe two definitionsfunction e(int a): int{ return a^2}function f(int b): int{ return b^2}bind the same function to e and f, but do thedefinitionsfunction g (int a): int{ return p^2}function h (int a): int{ return q^2}bind the same function to g and h?What’s the difference?• a and b are dummies, bound in e and f• p and q are not dummies— they are free in g and hThe definitions of e and f are self-contained, butthose of g and h depend on the bindings of their freevariables.In general,• renaming a bound variable throughout its scopehas no effect,• renaming a free variable can be hazardous.CS 345 slide 235 Spring 20053 April 2005How are free names’ bindings determined?int y0 = 7; 1function f( int x ): int 2{ return x + y; }; 3int r = 0; 4{ int y1 = 1; 5r := f(3); 6} 7{ int y2 = 2; 8r += f(3); 9} 10print( r ); 11The occurrence of variable y in function f (line 3) isfree in f because it has no binding occurrence in f.Static binding If names are bound statically, then a function’sfree variables are bound by the environment of thefunction’s definition.In the example, y in (3) is bound by declaration (1), sof(3) where y1 = 1H S (3 + y0 where y0 = 7) where y1 = 1H S (3 + 7) where y1 = 1H S 10andf(3) where y2 = 2H S (3 + y0 where y0 = 7) where y2 = 2H S 3 + 7 where y2 = 2H S 10so the value of r is 20.CS 345 slide 236 Spring 20053 April 2005Dynamic binding If names are bound dynamically, a function’s freevariables are bound by the environment of each ofthe function’s calls.In the example, the y in (3) is bound by declarations (5)and (8), sof(3) where y1 = 1H S 3 + y1 where y1 = 1H S 3 + 1H S 4andf(3) where y2 = 2H S 3 + y2 where y2 = 2H S 3 + 2H S 5so the value of r is 9.In statically scoped languages,• parameters are bound to arguments, and• names are bound to definitionsaccording to the so-calledLexical Scope Rules:function f ( x : T1 ) : T2; begin S end;f ( E ) binds each free occurrence ofparameter x in S to argument Ebegin var x = E; S endbinds each free occurrence of namex in S to definition ECS 345 slide 237 Spring 20053 April 2005Why do the rules refer to functions’ “free” variables?To handle cases likefunction g( int x0 ): int 1{ int r = x0; 2{ int x1 = 5; r += x1+2; } 3return r; 4}; 5print( g(3) ); 6… in which only the first x (lines 1 and 2) is bound to 3;the other x (line 3) is not “free in the body of g”.The best-known dynamically scoped language is Lisp,whose author (John McCarthy) has described itsdynamic scoping as a “bug” (fixed in Scheme).As we shall see, another instance of dynamic scopingis C’s macros.Most other modern languages (Pascal, C, C++, Ada,Java, Haskell, …) are scoped statically.CS 345 slide 238 Spring 20053 April 2005Parameter-Argument BindingThe term bind is used in several senses:• environments bind names to locations• states bind locations to values• procedure invocations bind parametersto arguments.The parameter-argument binding model of pureexpression languages (such as Haskell) is simple:1. a function application (call) binds each parametername in (a copy of) a function’s body to an argumentexpression2. the function-body copy is evaluatedIn Pascal and C, the introduction the notion oflocation —and the resulting distinction betweenl-values and r-values— introduces more possibilities:An argument could be1. an r -value (as in Haskell) (“by value”)2. an l -value (only some arguments) (“by reference”)3. an expression (to be executed ) (“by name”)4. some combination of 1–3C: all parameters are bound to arguments’ r-values (call by value )Pascal: default: by value;var parameter: by reference.CS 345 slide 239 Spring 20053 April 2005By ValueParameters are local variables, initialized at eachcall with arguments’ r-values.Also known as copy-in binding.Implementation: For each parameter…0. evaluate argument1. copy argument’s value to parameterThat is, for each parameter and the correspondingargument:parameteri := argumentiConsequences:• assignments to parameters within a procedureaffect parameters (local) only• even if an argument’s value is never used by itsfunction, it is nevertheless evaluatedExample (a successor function in Pascal and C):function succ ( i : integer ): integer;beginsucc := (i +1) mod sizeend;x := succ (x);int succ (int i) {return (i+1) % size;}x = succ(x);CS 345 slide 240 Spring 20053 April 2005By ReferenceParameters are indirect references, bound at eachcall to arguments’ l -values.That is, for each parameter:parameteri := &(argi)every occurrence of parameteri is dereferencedConsequences:• assignment to parameter updates argument• arguments must have l -valuesMotivations for use:• to obtain argument update• to avoid argument copyingExample (a “by-reference” version of succ):procedure incr ( var i: integer );begini := (i +1) mod sizeend;incr (x);“Call-by-reference” in C:Use parameters and arguments of type pointer.Example: a “by-reference” version of succ:void incr(int* i){ *i = (*i+1) % size;