A name is a mnemonic character string used to represent something else.
Names allow us to refer to variables, constants, operations, types, and so on using symbolic identifiers rather than low-level concepts like addresses.
Subroutines are control abstractions.
Classes are data abstractions.
the notion of binding time, which refers not only to the binding of a name to the thing it represents, but also in general to the notion of resolving any design decision in a language implementation.
- Language design time：控制流结构，基本类型，复杂对象组织方法等语义方面的内容
- Language implementation time：基础类型大小，和操作系统交互，堆和栈的组织方式和大小
- Program writing time：算法，数据结构，命名
- Compile time：高级数据结构和机器码的映射，静态数据的内存布局
- Link time：引用其他的模块的绑定关系到链接时才能确定（增量编译）
- Load time：程序装载时才能确定实际的地址（虚实地址转换）
- Run time：变量值绑定，程序启动时机，模块装载时机，首次“看到”声明的时机，子程序调用时机，代码块进入时机，表达式求值、语句执行时机
Compiler-based language implementations tend to be more efficient than interpreter-based implementations because they make earlier decisions.
The period of time between the creation and the destruction of a name-to-object binding is called the binding’s lifetime.
Global variables are the obvious example of static objects, but not the only one.
Numeric and string-valued constant literals are also statically allocated.
Finally, most compilers produce a variety of tables that are used by run-time support routines for debugging, dynamic type checking, garbage collection, exception handling, and other purposes; these are also statically allocated.
Manifest constants can always be allocated statically, even if they are local to a recursive subroutine: multiple instances can share the same location.
If a language permits recursion, static allocation of local variables is no longer an option.
Fortunately, the natural nesting of subroutine calls makes it easy to allocate space for locals on a stack.
Each instance of a subroutine at run time has its own frame (also called an activation record) on the stack, containing arguments and return values, local variables, temporaries, and bookkeeping information.
A heap is a region of storage in which subblocks can be allocated and deallocated at arbitrary times.
Heaps are required for the dynamically allocated pieces of linked data structures, and for objects such as fully general character strings, lists, and sets, whose size may change as a result of an assignment statement or other update operation.
The principal concerns are speed and space, and as usual there are tradeoffs between them.
- With a first fit algorithm we select the first block on the list that is large enough to satisfy the request.
- With a best fit algorithm we search the entire list to find the smallest block that is large enough to satisfy the request.
Intuitively, one would expect a best fit algorithm to do a better job of reserving large blocks for large requests. At the same time, it has higher allocation cost than a first fit algorithm, because it must always search the entire list, and it tends to result in a larger number of very small “left-over” blocks.
In effect, the heap is divided into “pools,” one for each standard size. The division may be static or dynamic. Two common mechanisms for dynamic pool adjustment are known as the buddy system and the Fibonacci heap.
The problem with external fragmentation is that the ability of the heap to satisfy requests may degrade over time.
The run-time library for such a language must then provide a garbage collection mechanism to identify and reclaim unreachable objects.
手动 vs 自动：
- The traditional arguments in favor of explicit deallocation are implementation simplicity and execution speed.
- manual deallocation errors are among the most common and costly bugs in real-world programs.
The textual region of the program in which a binding is active is its scope. In most modern languages, the scope of a binding is determined statically, that is, at compile time.
- statically scoped: compile time
- dynamically scoped: bindings depend on the flow of execution at run time
At any given point in a program’s execution, the set of active bindings is called the current referencing environment. The set is principally determined by static or dynamic scope rules.
- deep binding: the choice is made when the reference is first created
- shallow binding: the choice is made when the reference is finally used
In a language with static (lexical) scoping, the bindings between names and objects can be determined at compile time by examining the text of the program, without consideration of the flow of control at run time.
a name that is introduced in a declaration is known in the scope in which it is declared, and in each internally nested scope, unless it is hidden by another declaration of the same name in one or more nested scopes.
To find the object corresponding to a given use of a name, we look for a declaration with that name in the current, innermost scope. If there is one, it defines the active binding for the name. Otherwise, we look for a declaration in the immediately surrounding scope.
A name-to-object binding that is hidden by a nested declaration of the same name is said to have a hole in its scope.
In others, the programmer can access the outer meaning of a name by applying a qualifier or scope resolution operator.
Put another way, can an expression E refer to any name declared in the current scope, or only to names that are declared before E in the scope?
Several early languages, required that all declarations appear at the beginning of their scope.
C++ and Java further relax the rules by dispensing with the define-before-use requirement in many cases. In both languages, members of a class (including those that are not defined until later in the program text) are visible inside all of the class’s methods.
Recursive types and subroutines introduce a problem for languages that require names to be declared before they can be used: how can two declarations each appear before the other?
- A declaration introduces a name and indicates its scope, but may omit certain implementation details.
- A definition describes the object in sufficient detail for the compiler to determine its implementation.
This modularization of effort depends critically on the notion of information hiding, which makes objects and algorithms invisible, whenever possible, to portions of the system that do not need them.
An alternative solution to the multiple instance problem appeared in Euclid, which treated each module as a type. Given a module type, the programmer could declare an arbitrary number of similar module objects.
In a language with dynamic scoping, the bindings between names and objects depend on the flow of control at run time, and in particular on the order in which subroutines are called.
Because the flow of control cannot in general be predicted in advance, the bindings between names and objects in a language with dynamic scoping cannot in general be determined by a compiler.
To keep track of the names in a statically scoped program, a compiler relies on a data abstraction called a symbol table.
In a language with dynamic scoping, an interpreter (or the output of a compiler) must perform operations analogous to symbol table insert and lookup at run time.
A name that can refer to more than one object at a given point in the program is said to be overloaded. Overloading is in turn related to the more general subject of polymorphism.
aliases: Two or more names that refer to the same object at the same point in the program are said to be aliases.
overloaded: A name that can refer to more than one object at a given point in the program is said to be overloaded
- Redefining Built-in Operators
When should scope rules be applied to such a subroutine: when the reference is first created, or when the routine is finally called?
动态作用域常使用 shallow binding：
This late binding of the referencing environment of a subroutine that has been passed as a parameter is known as shallow binding.
静态作用域常使用 deep binding：
It therefore makes sense to bind the environment at the time the routine is first passed as a parameter, and then restore that environment when the routine is finally called.
This early binding of the referencing environment is known as deep binding.
Deep binding is implemented by creating an explicit representation of a referencing environment (generally the one in which the subroutine would execute if called at the present time) and bundling it together with a reference to the subroutine. The bundle as a whole is referred to as a closure.
An object that plays the role of a function and its referencing environment may variously be called an object closure, a function object, or a functor.
Prior to the development of high-level programming languages, assembly language programmers could find themselves writing highly repetitive code. To ease the burden, many assemblers provided sophisticated macro expansion facilities.
So-called hygienic macros(卫生宏) implicitly encapsulate their arguments, avoiding unexpected interactions with associativity and precedence.