CS计算机代考程序代写 ada scheme Java Lambda Calculus python c# c++ flex data structure algorithm Names, Scopes and Bindings

Names, Scopes and Bindings
Chapter 3

Name, Scope, and Binding
§Ease of programming – main driving force behind the design of modern languages
§Core issues in language design: § names – abstraction
§ control flow
§ types, composite types
§ subroutines – control abstraction § classes – data abstraction
§High level programming – more abstract § Farther from hardware
§Abstraction – complexity becomes manageable § This is true in general
2

Name, Scope, and Binding
§Name: a character string representing something else
§ Abstraction
§ Easy for humans to understand § Much better than addresses
§Binding: association of two things
§ Example: between a name and the thing it names
§Scope of a binding: the part of the program (textually) in which the binding is active
§Binding Time: the point at which a binding is created
3

Binding
§Static vs. Dynamic
§ Static: bound before run time
§ Dynamic: bound at run time
§ Trade-off:
§ Early binding times: greater efficiency § Late binding times: greater flexibility
§Compiles vs. Interpreted languages
§ Compiled languages tend to have early binding times § Interpreted languages tend to have late binding times
Language
Binding Time
Advantage
Compiled
Early (static)
Efficiency
Interpreted
Late (dynamic)
Flexibility
4

Lifetime and Storage Management
§Lifetime of name-to-binding: from creation to destruction
§ Object’s lifetime ≥ binding’s lifetime
§ Example: C++ variable passed by reference (&)
§ Object’s lifetime < binding’s lifetime – dangling reference § Example: C++ object § created with new § passed by reference to subroutine with & § deallocated with delete § Scope of a binding: the textual region of the program in which the binding is active 5 Lifetime and Storage Management §Storage Allocation mechanisms: § Static § absolute address, retained throughout the program § Stack § last-in, first-out order; for subroutines calls and returns § Heap § allocated and deallocated at arbitrary times 6 Lifetime and Storage Management §Static allocation: § global variables § code instructions § explicit constants (including strings, sets, etc.) §A = B / 14.7 §printf(“hello, world\n”) § small constants may be stored in the instructions § C++ static variables (or Algol own) § Statically allocated objects that do not change value are allocated in read-only memory § constants, instructions 7 Lifetime and Storage Management §Stack-based allocation: § parameters, local variables, temporaries § allocate space for recursive routines § reuse space § Frame (activation record) for each subroutine call: § position in stack: frame pointer § arguments and returns § local variables, temporaries: § fixed offset from the frame pointer at compile time § return address § dynamic link: reference to (stack frame of) caller § static link: reference to (stack frame of) routine inside which it was declared 8 Lifetime and Storage Management 9 Lifetime and Storage Management §Heap allocation § (different from “heap” data structure for priority queues) § dynamic allocation: lists, sets, strings (size can change) § single linked list of free blocks § fragmentation: internal, external 10 Lifetime and Storage Management §Heap allocation § allocation algorithms § first fit, best fit– O(n) time § pool allocation – O(1) time § separate free list of blocks for different sizes § buddy system: blocks of size 2k § Fibonacci heap: blocks of size Fibonacci numbers § defragmentation 11 Lifetime and Storage Management §Heap maintenance § Explicit deallocation § C, C++ § simple to implement § efficient § object deallocated too soon – dangling reference § object not deallocated at the end of lifetime – memory leak § deallocation errors are very difficult to find § Implicit deallocation: Garbage collection § functional, scripting languages § C#, Java, Python § avoid memory leaks (difficult to find otherwise) § recent algorithms more efficient § the trend is towards automatic collection 12 Scope Rules § Scope of a binding: § textual region of the program in which binding is active § Subroutine entry – usually creates a new scope: § create bindings for new local variables § deactivate bindings for redeclared global variables § make references to variables § Subroutine exit: § destroy bindings for local variables § reactivate bindings for deactivated global variables § Scope: maximal program section in which no bindings change § block: module, class, subroutine §C:{ ... } § Elaboration time: when control first enters a scope 13 Scope Rules §Referencing environment § the set of active bindings; determined by: § Scope rules (static or dynamic) § Binding rules (deep or shallow) §Static Scoping (Lexical Scoping) § almost all languages employ static scoping § determined by examining the text of the program § at compile time § closest nested rule § identifiers known in the scope where declared and in each enclosed scope, unless re-declared in an enclosed scope § examine local scope and statically enclosing scopes until a binding is found 14 Scope Rules § Subroutines § bindings created are destroyed at subroutine exit § exception: static (C), own (Algol) § nested subroutines: closest nested scope § Python, Scheme, Ada, Common Lisp § not in: C, C++, Java § access to non-locals: scope resolution operator § C++ (global): ::X § Ada: MyProc.X § built-in objects § outermost scope § outside global 15 Scope Rules § Example: Nested subroutines 16 Scope Rules §Access to non-locals: static links § each frame points to the frame of the routine inside which it was declared § access a variable in a scope k levels out by following k static links and then using the known offset within the frame 17 Scope Rules §Declaration order § object x declared inside block B §the scope of x may be: § the entire block B or § only the part of B after x’s declaration 18 Scope Rules §Declaration order § Example: C++ int n = 1; void f(void){ int m = n; int n = 2; } // global n // local n § Example: Python – no declarations n= 1 def f(): m = n # error # add “global n” to use the global n n =2 19 Scope Rules §Declaration order § Example: Scheme (let ((A 1)) (let ((A 2) (B A)) B)) ; return 1 (let ((A 1)) (letrec ((A 2) (B A)) B)) ; return 2 20 Scope Rules §Dynamic Scoping § binding depends on flow at run time § use the most recent, active binding made at run time § Easy to implement – just a stack with names § Harder to understand § not used any more § why learn? – history 21 Scope Rules § Example: Dynamic Scoping n: integer procedure first() n := 1 procedure second() n : integer first() n := 2 – global – local if read_integer() > 0
second()
else first()
write_integer(n)
§ Static scoping: prints 1
§ Dynamic scoping: prints 2 for positive input, 1 for negative
22

Scope Rules
§ Example: Dynamic scoping problem
§ scaled_score uses the wrong max_score
max_score : integer –– maximum possible score
function scaled_score(raw_score : integer) : real
return raw_score / max_score * 100

procedure foo( )
max_score : real := 0 –- highest % seen so far

foreach student in class
student.percent := scaled_score(student.points)
if student.percent > max_score
max_score := student.percent
23

Binding of Referencing Environments
§ Referencing environment: the set of active bindings § static: lexical nesting
§ dynamic: order of declarations at run time
§ Reference to subroutine: when are the scope rules applied? § Shallow binding: when routine is called
§ default in dynamic scoping
§ Deep binding: when reference is created
§ default in static scoping § Example (next slides)
24

Binding of Referencing Environments
§ print_routine
§ shallow binding
§ to pick line_length
§ older_than_threshold
§ deep binding
§ otherwise, if print_selected_records has a variable threshold, it will hide the one in the main program
25

Binding of Referencing Environments
26

Binding of Referencing Environments
§Deep binding implementation: Subroutine closure § explicit representation of a referencing environment
(the one in which the subroutine would execute if called now) § reference to subroutine
§ Why binding time matters with static scoping?
§ the running program may have two instances of an object § only for objects that are neither local nor global
§ Examples when it does not matter:
§ subroutines cannot be nested: C
§ only outermost subroutines can be passed as parameters:
Modula-2
§ subroutines cannot be passed as parameters: PL/I, Ada 83
27

Binding of Referencing Environments
§ Example: Deep binding in Python
def A(I, P):
def B():
print(I)
# body of A:
if I > 1: P()
else:
A(2, B)
def C():
pass # do nothing
A(1, C) # main program; output 1
§ referencing environment captured in closures: dashed boxes, arrows § when B is called via P, two instances of I exist
§ the closure for P was created in the initial invocation of A
§ B’s static link (solid arrow) points to the frame of the earlier invocation 28

Binding of Referencing Environments
§First-class values
§ can be passed as a parameter
§ can be returned from subroutine § can be assigned into a variable
§Second-class values
§ can only be passed as a parameter
§Third-class: none
§ Other authors may have different definitions: no second-class; first-
class may require anonymous function definition (lambda expressions)
§ Subroutines:
§ first-class: functional and scripting languages, C#
§ C, C++: pointers to functions are first-class § second-class: most imperative languages
§ third class in Ada83
29

Binding of Referencing Environments
§ First-class subroutines: additional complexity
§ a reference to a subroutine may outlive the execution of the scope
in which that subroutine was declared § Example: Scheme
(define plus-x
(lambda (x)
(lambda (y)(+ x y))))
(let ((f (plus-x 2)))
(f 3)) ; return 5
§ plus-x returns an unnamed function (3rd line), which uses the
parameter x of plus-x
§ when f is called in 5th line, its referencing environment includes the
x in plus-x, even though plus-x has already returned
§ x must be still available – unlimited extent – allocate on heap (C#)
30

Binding of Referencing Environments
§Lambda expressions
§ come from lambda calculus: anonymous functions
§ Example: Scheme
((lambda (i j) (> i j) i j) 5 8) ;return 8
§ Example: C#: delegate or => (int i, int j) => i > j ? i : j
31

Binding of Referencing Environments
§First-class subroutines
§ are increasingly popular; made their way into C++, Java § Problem: C++, Java do not support unlimited extent
§ Example: C++
for_each(V.begin(), V.end(),
[](int e){ if (e < 50) cout << e << “ “; } ); 32 Binding of Referencing Environments §Lambda functions in Python § Example ids = ['id1', 'id2', 'id30', 'id3', 'id22', 'id100’] # Lexicographic sort print(sorted(ids)) => [‘id1’, ‘id100’, ‘id2’, ‘id22’, ‘id3’, ‘id30’]
# Integer sort
sorted_ids = sorted(ids, key=lambda x: int(x[2:]))
print(sorted_ids)
=> [‘id1’, ‘id2’, ‘id3’, ‘id22’, ‘id30’, ‘id100’]
33

Binding of Referencing Environments
§ Lambda functions in Python § Example
def myfunc(n):
return lambda a : a * n
mydoubler = myfunc(2)
print(mydoubler(11))
=> 22
mytripler = myfunc(3)
print(mytripler(11))
=> 33
34