Section 1
Preview this deck
Implicit Heap-Dynamic Variables
Front
| 5 | 0 | ||
| 4 | 0 | ||
| 3 | 0 | ||
| 2 | 0 | ||
| 1 | 0 |
Active users
0
All-time users
0
Favorites
0
Last updated
6 years ago
Date created
Mar 1, 2020
Cards (115)
Section 1
(50 cards)
Implicit Heap-Dynamic Variables
variables that are bound to heap storage only when they are assigned values highest degree of flexibility disadvantage is the run time overhead of maintaining all the dynamic attributes another disadvantage is the loss of some error detection by the compiler
Token
category of lexemes
Explicit Declaration
statement in a program that lists variable names and specifies that they are a particular type
Ambiguity in Grammars
grammar is ambiguous iff it generates derivation that has two or more distinct parse trees
Syntax
form or structure of the expressions, statements, and program units
Influences on Language Design
1. computer architecture (languages are developed around the von Neumann architecture, fetch-execute cycle) 2. programming methodologies (e.g., OOP)
Reliability
conformance to specifications 1. type checking 2. exception handling 3. aliasing 4. readability and writability
Deallocation
process of placing a memory cell that has been unbound from a variable back into the pool of available memory
Compilation
translation from high-level language to machine language slow translation, fast execution
JIT Compiler
a hybrid between a compiler and an interpreter. the code is reasonably compiled, usually in pieces when it is needed, and saved so that it can be reused later.
Rule
has a left-hand side (LHS), which is a nonterminal, and a right-hand side (RHS), which is a string of terminals and/or nonterminals e.g. <id> -> identifier | identifier <arithmetic_operator> identifier
Linking and Loading
process of collecting system program units and linking them to a user program
Writability
ease with which a language can be used to create programs 1. simplicity and orthogonality 2. support for abstraction 3. expressivity
Derivation
repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols)
Binding Times
time at which a binding takes place language design time, language implementation time, compile time, load time, link time, run time
Elaboration
storage allocation and binding process indicated by the declaration, which takes place when execution reaches the code to which the declaration is attached. Occurs during run time
Cost
ultimate total cost of using a language 1. training others to use the language 2. writing programs 3. compiling programs 4. executing programs 5. language implementation system 6. reliability (poor reliability increases costs) 7. maintenance
Alias
when more than one variable name can be used to access the same memory location
Preprocessor Macro
specifies code from another file is to be included e.g. C #include
Top Down Parser
produce parse tree beginning at the root left-most derivation builds the parse tree in preorder
Type Inference
type of implicit type declaration that uses context
Static Variables
variables that are bound to memory cells before program execution begins and remain bound to those same memory cells until program execution terminates
Four Criteria
readability, writability, reliability, cost
Lifetime of a Variable
time during which the variable is bound to a specific memory location
Start Symbol
special element of the nonterminals of a grammar
Explicit Heap-Dynamic Variables
nameless (abstract) memory cells that are allocated and deallocated by explicit run time instructions written by the programmer. Variables can only be referenced through pointer or reference variables
Reserved Word
special word that cannot be used as a user-defined name
Semantics Analysis
generate intermediate code
Functional Languages
main means of making computations is by applying functions to given parameters e.g. LISP, Scheme
Static Binding
occurs before run time and remains unchanged throughout program execution
Readability
ease with which programs can be read and understood 1. overall simplicity 2. orthogonality (a relatively small set of primitive constructs can be combined in a relatively small number of ways to build the control and data structures of the language) 3. data types 4. syntax considerations
Scope
scope of a variable is the range of statements in which the variable is visible
Stack-Dynamic Variables
variables whose storage bindings are created when their declaration statements are elaborated, but whose types are statically bound
Semantics
meaning of the expressions, statements, and program units
Dynamic Binding
occurs during execution or can change during execution of the program disadvantages include reduced error-detection capability -- incorrect right sides of assignment statements are not detected, rather the type of the left side is changed to the incorrect type another disadvantage is cost -- requires considerable execution time, type checking must be done at run time, and every variable must hve a run time descriptor associated with it to maintain the current type languages with dynamic binding are typically interpreter rather than compiled
Type
range of values the variable can store and the set of operations that are defined for values of that type
Binding
association between attribute and entity, such as between a variable and its type of value, or between an operation and symbol
Terminals
lexemes or tokens
Grammar
finite non-empty set of rules
Logic Languages
rule-based e.g. Prolog
Local Variable
variable that is declared in a program unit or block
Bottom Up Parser
produce parse tree beginning at the leaves reverse of a right-most derivation
Von Neumann Bottleneck
Connection speed between a computer's memory and its processor determines the speed of a computer Program instructions often can be executed much faster than the speed of the connection; the connection speed thus results in a bottleneck
Imperative Languages
central features are variables, assignment statements, and iteration abstraction of von Neuman architecture e.g. C, Java, Perl, JavaScript, .NET, C++
Implicit Declaration
associates variables with types through default conventions rather than declaration statements
Variable
abstraction of a memory cell sextuple of attributes: name address value type lifetime scope
Allocation
process by which a memory cell, which is bound to a variable, is taken from a pool of available memory
Pure Interpretation
easier implementation, run-time errors easily and immediately displayed slower execution
Visibility
variable is visible in a statement if it can be referenced in that statement
Code Generation
machine code is generated
Section 2
(50 cards)
Compatible Type
type that is either legal for the operator or is allowed under language rules to be implicitly converted, by compiler-generated code, to a legal type automatic conversion is called coercion
Heap-Dynamic Array
array in which the binding of subscript ranges are storage allocation is dynamic and can change any number of times during the array's lifetime advantage is flexibility -- arrays can grow and shrink during program execution as the need for space changes disadvantage is that allocation and deallocation take longer and may happen many times during execution of the program
Stack-Dynamic Array
array in which both the subscript ranges and the storage allocation are dynamically bound at elaboration time; once ranges are bound and storage is allocated, they remain fixed during lifetime of the variable advantage is flexibility; size not need be known until array is about to be used
Mark-Sweep Approach
system allocates and deallocates pointers as necessary, doesn't reclaim and allows garbage to accumulate once all cells allocated, mark-sweep process begins and gathers all garbage left in heap every heap cell has indicator bit used by collection algorithm 1. all cells have bits set to indicate garbage or not garbage 2. marking phase - every pointer in program traced into heap, and all reachable cells marked as not garbage 3. sweep - all cells in the heap that have not been marked are returned to list of available space lazy approach
Record
possibly heterogeneous aggregate of data elements in which the individual elements are identified by names
Associative Array
unordered collection of data elements that are indexed by an equal number of values called keys aka map, dictionary
Value Type Variable
variable used to store data
Reference Type
variable similar to pointer, but references an object or a value in memory rather than the memory address
Lost Heap-Dynamic Variable, Memory Leak
an allocated heap-dynamic variable that is no longer accessible to the user program, also known as garbage or a memory leak 1. Pointer p1 is set to point to a newly created heap-dynamic variable. 2. p1 is later set to point to another newly created heap-dynamic variable.
Array
homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element
Subrange Type
contiguous subsequence of an ordinal type e.g. 12...14 is a subrange of integer type
Global Variable
a variable that is visible to every module in the program
Heterogeneous Array
array in which the elements need not be of the same type
Dynamic Scoping
based on the calling sequence of subprograms, not on their spatial relationship to each other. Thus, the scope can be determined only at run time disadvantages include difficulty in reading, inability to type check references to nonlocals statically, and the local variables of the subprogram during execution are all visible to any other executing subprograms regardless of proximity or how execution got to the executing subprogram
Pointer
type in which the variables have a range of values that consist of memory addresses
Union
type whose variables are allowed to store different type values at different times during execution
Fixed Stack-Dynamic Array
array in which the subscript ranges are statically bound, but the allocation is done at declaration elaboration time during execution. advantage over static is space efficiency; large array in one subprogram can use the same space as a large array in a different subprogram as long as both subprograms are not active at the same time disadvantage is the required allocation and deallocation time
Referencing Environment
collection of all variables that are visible in the statement reference collection of a statement in a static-scoped language is the variables declared in its local scope plus the collection of all variables of its ancestor scopes that are visible
Character String Type
type in which the values consist of sequences of characters
Static Ancestors
static parent(s) up to the largest enclosing subprogram
Nonlocal variable
variable that is visible but not declared within the program unit or block
Jagged Array
array in which the length of the rows need not be the same
Heap
area where storage is dynamically allocated
Object
instance of a user-defined (abstract) data type
Limited Dynamic Length String
strings allowed to have varying length up to a declared and fixed maximum set by the variable's definition C, C++ Descriptor (run time descriptor to store both fixed maximum length and the current length): name (limited dynamic string) maximum length current length address of first character
Fixed Heap-Dynamic Array
similar to fixed stack-dynamic in that subscript ranges and storage binding are both fixed after storage is allocated differences are that both are done when the user program requests them during execution and storage is allocated from the heap advantage is flexibility -- array's size always fits the problem disadvantage is allocation time from heap, which is longer than from the stack
Static Scoping
method of binding names to nonlocal variables. Scope of variable can be statically determined prior to execution, e.g., by human reader
Anonymous Variables
variables without names
Ordinal Type
type in which the range of possible values can be easily associated with the set of positive integers
Reference Type Variable
variable used to reference some other variable
Column Major Order
used to access multi-dimensional arrays by columns given matrix [1 2] [3 4] addresses are 0 = 1, 1 = 3, 2 = 2, 3 = 4 used by Fortran
Static String Length
length is static and set when the string is created Java, Python Descriptor (required only during compilation): name (static string) length address of first character
Row Major Order
used to access multi-dimensional arrays by rows given matrix [1 2] [3 4] addresses are 0 = 1, 1 = 2, 2 = 3, 3 = 4
Primitive Data Types
reflections of the hardware, like integer types. Some require non-hardware support for implementation
Block
languages that allow new static scopes to be defined in the midst of executable code stack dynamic so storage is allocated when section is entered and deallocated when section is exited int counter; while (...) { int counter; //new static scope counter++; }
Static Array
array in which the subscript ranges are statically bound and storage allocation is static (done before run-time) advantage is efficiency; no dynamic allocation or deallocation is required disadvantage is that the storage for the array s fixed for the entire execution time of the program
Static Parent
subprogram that declares a subprogram
Data Type
collection of data objects and a set of predefined operations on those objects
Dangling Pointer/Reference Definition, Dangers, Creation
pointer that contains the address of a heap-dynamic variable that has been deallocated dangerous because: 1. location may have been reallocated to new variable 2. could destroy value of new variable int * arrayPtr1; int * arrayPtr2 = new int[100]; arrayPtr1 = arrayPtr2; delete [] arrayPtr2; // Now, arrayPtr1 is dangling, because the heap storage // to which it was pointing has been deallocated.
Named Constant
variable that is bound to a value only once e.g. pi
String Design Issues
Special kind of character array, or primitive type? Static or dynamic length?
Heap-Dynamic Variables
variables that are dynamically allocated from the heap, often do not have identifiers associated with them and can be referenced only by pointer or reference variables
Enumeration Type
type in which all of the possible values, which are named constants, are provided in the definition provides a way of defining and grouping collections of named constants e.g. enum days { Mon, Tues,..., Fri}; where the days are implicitly assigned integer values 1...n
Dynamic Length Strings
varying length with no maximum JavaScript requires overhead of dynamic storage allocation and deallocation, but provides most flexibilty Descriptor (run time descriptor to store current length): current length
Reference Counters
counter that stores number of pointers currently pointing at a cell. When counter reaches zero, cell has become garbage and can be deallocated eager approach
Slice
substructure of an array; nothing more than a referencing mechanism
Rectangular Array
multi-dimensional array in which all of the rows have the same number of elements and all columns have the same number of elements model tables exactly
Descriptor
collection of the attributes of a variable
Accessing Array (1d)
address(list[k]) = address(list[lower_bound]) + ((k - lower_bound) * element_size) address of list[1] = address of list[0] + (1 - 0) * element_size address of list[1] = address of list[0] + 1 * element_size off by one -- no need for subtraction when lower bound is zero
Type Checking
activity of ensuring that the operands of an operator are of compatible types
Section 3
(15 cards)