1-9-midterm1.pdf

Department of Computer Science CS 3304 Comparative Languages Module 1 Midterm Exam 1 Review © 2024 Denis Gracanin 1...

Department of Computer Science CS 3304 Comparative Languages Module 1 Midterm Exam 1 Review © 2024 Denis Gracanin 1 Department of Computer Science Introduction The midterm exam 1 is a closed book exam. Please review The Virginia Tech Undergraduate Honor System: http://www.honorsystem.vt.edu Duration: 75 minutes: § CRN 83353: 9 October 2024, 2:30pm-3:45pm, Surge 104C § CRN 83354: 8 October 2024, 9:30am-10:45pm, Graduate Life Center at Donaldson Brown 64 § CRN 83353: 8 October 2024, 2:00pm-3:15pm, New Classroom Building 260 It covers Chapters 1-5 of the Textbook Consists of two parts: § Twenty quiz questions (multiple choice, true/false), three points each, 60 points total § Two essay/problem questions, 20 points each, 40 points total It is a comprehensive exam, all material covered in lectures 1.1-1.8 and related assignments (Homeworks 1 and 2) are included CS 3304 Module 1: Midterm Exam 1 Review 2 2 1  Department of Computer Science Chapter 1: Preliminaries Reasons for Studying Concepts of Programming Languages Programming Domains Language Evaluation Criteria Influences on Language Design Language Categories Language Design Trade-Offs Implementation Methods Programming Environments CS 3304 Module 1: Midterm Exam 1 Review 3 3 Department of Computer Science Language Evaluation Criteria Readability: the ease with which programs can be read and understood Writability: the ease with which a language can be used to create programs Reliability: conformance to specifications (i.e., performs to its specifications) Cost: the ultimate total cost CS 3304 Module 1: Midterm Exam 1 Review 4 4 2  Department of Computer Science The von Neumann Architecture CS 3304 Module 1: Midterm Exam 1 Review 5 5 Department of Computer Science The von Neumann Architecture Fetch-execute-cycle (on a von Neumann architecture computer) initialize the program counter repeat forever fetch the instruction pointed by the counter increment the counter decode the instruction execute the instruction end repeat CS 3304 Module 1: Midterm Exam 1 Review 6 6 3  Department of Computer Science 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 Known as the von Neumann bottleneck; it is the primary limiting factor in the speed of computers CS 3304 Module 1: Midterm Exam 1 Review 7 7 Department of Computer Science Programming Methodologies Influences 1950s and early 1960s: Simple applications; worry about machine efficiency Late 1960s: People efficiency became important; readability, better control structures § Structured programming § Top-down design and step-wise refinement Late 1970s: Process-oriented to data-oriented § Data abstraction Middle 1980s: Object-oriented programming § Data abstraction + inheritance + polymorphism CS 3304 Module 1: Midterm Exam 1 Review 8 8 4  Department of Computer Science Language Categories Imperative § Central features are variables, assignment statements, and iteration § Include languages that support object-oriented programming § Include scripting languages § Include the visual languages § Examples: C, Java, Perl, JavaScript, Visual BASIC.NET, C++ Functional § Main means of making computations is by applying functions to given parameters § Examples: LISP, Scheme, ML, F# Logic § Rule-based (rules are specified in no particular order) § Example: Prolog Markup/programming hybrid § Markup languages extended to support some programming § Examples: JSTL, XSLT CS 3304 Module 1: Midterm Exam 1 Review 9 9 Department of Computer Science Implementation Methods Compilation § Programs are translated into machine language; includes JIT systems § Use: Large commercial applications Pure Interpretation § Programs are interpreted by another program known as an interpreter § Use: Small programs or when efficiency is not an issue Hybrid Implementation Systems § A compromise between compilers and pure interpreters § Use: Small and medium systems when efficiency is not the first concern CS 3304 Module 1: Midterm Exam 1 Review 10 10 5  Department of Computer Science Layered View of Computer The operating system and language implementation are layered over machine interface of a computer CS 3304 Module 1: Midterm Exam 1 Review 11 11 Department of Computer Science Compilation Translate high-level program (source language) into machine code (machine language) Slow translation, fast execution Compilation process has several phases: § Lexical analysis: converts characters in the source program into lexical units § Syntax analysis: transforms lexical units into parse trees which represent the syntactic structure of program § Semantics analysis: generate intermediate code § Code generation: machine code is generated CS 3304 Module 1: Midterm Exam 1 Review 12 12 6  Department of Computer Science Pure Interpretation No translation Easier implementation of programs (run-time errors can easily and immediately be displayed) Slower execution (10 to 100 times slower than compiled programs) Often requires more space Now rare for traditional high-level languages Significant comeback with some Web scripting languages (e.g., JavaScript, PHP) CS 3304 Module 1: Midterm Exam 1 Review 13 13 Department of Computer Science Hybrid Implementation Systems A compromise between compilers and pure interpreters A high-level language program is translated to an intermediate language that allows easy interpretation Faster than pure interpretation Examples § Perl programs are partially compiled to detect errors before interpretation § Initial implementations of Java were hybrid; the intermediate form, byte code, provides portability to any machine that has a byte code interpreter and a run-time system (together, these are called Java Virtual Machine) CS 3304 Module 1: Midterm Exam 1 Review 14 14 7  Department of Computer Science Chapter 2: Evolution of the Major Programming Languages Zuse’s Plankalkül Minimal Hardware Programming: Pseudocodes The IBM 704 and Fortran Functional Programming: Lisp The First Step Toward Sophistication: ALGOL 60 Computerizing Business Records: COBOL The Beginnings of Timesharing: Basic Everything for Everybody: PL/I Two Early Dynamic Languages: APL and SNOBOL The Beginnings of Data Abstraction: SIMULA 67 Orthogonal Design: ALGOL 68 Some Early Descendants of the ALGOLs CS 3304 Module 1: Midterm Exam 1 Review 15 15 Department of Computer Science Chapter 2: Evolution of the Major Programming Languages Programming Based on Logic: Prolog History's Largest Design Effort: Ada Object-Oriented Programming: Smalltalk Combining Imperative ad Object-Oriented Features: C++ An Imperative-Based Object-Oriented Language: Java Scripting Languages The Flagship.NET Language: C# Markup/Programming Hybrid Languages CS 3304 Module 1: Midterm Exam 1 Review 16 16 8 Copyright © 2018 Pearson. All rights reserved. Department of Computer Science Genealogy of Common Languages CS 3304 Module 1: Midterm Exam 1 Review 17 17 Department of Computer Science Language Groups Imperative: § von Neumann (Fortran, Pascal, Basic, C) § Object-oriented (Smalltalk, Eiffel, C++?) § Scripting languages (Perl, Python, JavaScript, PHP) Declarative: § Functional (Scheme, ML, pure LISP, FP) § Logic, constraint-based (Prolog, VisiCalc, RPG) Imperative languages, particularly the von Neumann languages, predominate: § They will occupy the bulk of our attention CS 3304 Module 1: Midterm Exam 1 Review 18 18 9  Department of Computer Science C Designed for systems programming (at Bell Labs by Dennis Richie) in 1972 Evolved primarily from BCLP and B, but also ALGOL 68 Powerful set of operators, but poor type checking Initially spread through UNIX Though designed as a systems language, it has been used in many application areas CS 3304 Module 1: Midterm Exam 1 Review 19 19 Department of Computer Science Combining Imperative and Object-Oriented Programming: C++ Developed at Bell Labs by Stroustrup in 1980 Evolved from C and SIMULA 67 Facilities for object-oriented programming, taken partially from SIMULA 67 A large and complex language, in part because it supports both procedural and object-oriented programming Rapidly grew in popularity, along with OOP ANSI standard approved in November 1997 Microsoft’s version: MC++: § Properties, delegates, interfaces, no multiple inheritance CS 3304 Module 1: Midterm Exam 1 Review 20 20 10  Department of Computer Science An Imperative-Based Object-Oriented Language: Java Developed at Sun in the early 1990s: § C and C++ were not satisfactory for embedded electronic devices Based on C++: § Significantly simplified (does not include struct, union, enum, pointer arithmetic, and half of the assignment coercions of C++) § Supports only object-oriented programming § Has references, but not pointers § Includes support for applets and a form of concurrency CS 3304 Module 1: Midterm Exam 1 Review 21 21 Department of Computer Science JavaScript Began at Netscape, but later became a joint venture of Netscape and Sun Microsystems A client-side HTML-embedded scripting language, often used to create dynamic HTML documents Purely interpreted Related to Java only through similar syntax CS 3304 Module 1: Midterm Exam 1 Review 22 22 11  Department of Computer Science Python An OO interpreted scripting language Type checked but dynamically typed Used for form processing Dynamically typed, but type checked Supports lists, tuples, and hashes CS 3304 Module 1: Midterm Exam 1 Review 23 23 Department of Computer Science Chapter 3: Describing Syntax and Semantics Introduction The General Problem of Describing Syntax Formal Methods of Describing Syntax Attribute Grammars Describing the Meanings of Programs: Dynamic Semantics CS 3304 Module 1: Midterm Exam 1 Review 24 24 12  Department of Computer Science Syntax and Semantics Syntax: the form or structure of the expressions, statements, and program units Semantics: the meaning of the expressions, statements, and program units Syntax and semantics provide a language’s definition Users of a language definition § Other language designers § Implementers § Programmers (the users of the language) CS 3304 Module 1: Midterm Exam 1 Review 25 25 Department of Computer Science Formal Definition of Languages Recognizers: § A recognition device reads input strings over the alphabet of the language and decides whether the input strings belong to the language § Example: syntax analysis part of a compiler Generators: § A device that generates sentences of a language § One can determine if the syntax of a particular sentence is syntactically correct by comparing it to the structure of the generator § Example: emacs doctor (M-x doctor) CS 3304 Module 1: Midterm Exam 1 Review 26 26 13  Department of Computer Science BNF and Context-Free Grammars Context-Free Grammars § Developed by Noam Chomsky in the mid-1950s § Language generators, meant to describe the syntax of natural languages § Define a class of languages called context-free languages Backus-Naur Form (1959) § Invented by John Backus to describe the syntax of Algol 58 § BNF is equivalent to context-free grammars CS 3304 Module 1: Midterm Exam 1 Review 27 27 Department of Computer Science Grammar Grammar: a finite non-empty set of rules A start symbol is a special element of the nonterminals of a grammar An abstraction (or nonterminal symbol) can have more than one RHS → | begin end Syntactic lists are described using recursion → ident | ident, A derivation is a repeated application of rules, starting with the start symbol and ending with a sentence (all terminal symbols) CS 3304 Module 1: Midterm Exam 1 Review 28 28 14  Department of Computer Science Derivations Every string of symbols in a derivation is a sentential form A sentence is a sentential form that has only terminal symbols A leftmost derivation is one in which the leftmost nonterminal in each sentential form is the one that is expanded A derivation may be neither leftmost nor rightmost CS 3304 Module 1: Midterm Exam 1 Review 29 29 Department of Computer Science Parse Tree A hierarchical representation of a derivation = a + const b CS 3304 Module 1: Midterm Exam 1 Review 30 30 15  Department of Computer Science An Ambiguous Grammar A grammar is ambiguous if and only if it generates a sentential form that has two or more distinct parse trees Example: expression → | const → / | - const - const / const const - const / const CS 3304 Module 1: Midterm Exam 1 Review 31 31 Department of Computer Science ANTLR Summary ANTLR is a free, open source parser generator tool ANTLR supports infinite lookahead for selecting the rule alternative that matches the portion of the input stream being evaluated Use any ANTLR development tool that works for you (command line, IntelliJ plugin, others): § IntelliJ appears to have the best features CS 3304 Module 1: Midterm Exam 1 Review 32 32 16  Department of Computer Science Static Semantics Nothing to do with meaning Context-free grammars (CFGs) cannot describe all of the syntax of programming languages Categories of constructs that are trouble: § Context-free, but cumbersome (e.g., types of operands in expressions) § Non-context-free (e.g., variables must be declared before they are used) CS 3304 Module 1: Midterm Exam 1 Review 33 33 Department of Computer Science Attribute Grammars Attribute grammars (AGs) have additions to CFGs to carry some semantic info on parse tree nodes Primary value of AGs: § Static semantics specification § Compiler design (static semantics checking) CS 3304 Module 1: Midterm Exam 1 Review 34 34 17  Department of Computer Science Attribute Grammars: Definition An attribute grammar is a context-free grammar G = (S, N, T, P) with the following additions: § For each grammar symbol x there is a set A(x) of attribute values § Each rule has a set of functions that define certain attributes of the nonterminals in the rule § Each rule has a (possibly empty) set of predicates to check for attribute consistency Let X0 → X1 … Xc be a rule: § Functions of the form S(X0) = f(A(X1), … , A(Xn)) define synthesized attributes § Functions of the form I(Xj) = f(A(X0),... , A(Xn)), for i ≤ j ≤ n, define inherited attributes § Initially, there are intrinsic attributes on the leaves CS 3304 Module 1: Midterm Exam 1 Review 35 35 Department of Computer Science Dynamic Semantics There is no single widely acceptable notation or formalism for describing semantics Several needs for a methodology and notation for semantics: § Programmers need to know what statements mean § Compiler writers must know exactly what language constructs do § Correctness proofs would be possible § Compiler generators would be possible § Designers could detect ambiguities and inconsistencies CS 3304 Module 1: Midterm Exam 1 Review 36 36 18  Department of Computer Science Operational Semantics Operational Semantics: § Describe the meaning of a program by executing its statements on a machine, either simulated or actual § The change in the state of the machine (memory, registers, etc.) defines the meaning of the statement To use operational semantics for a high-level language, a virtual machine is needed: § A hardware pure interpreter would be too expensive § A software pure interpreter also has problems: o The detailed characteristics of the particular computer would make actions difficult to understand o Such a semantic definition would be machine- dependent CS 3304 Module 1: Midterm Exam 1 Review 37 37 Department of Computer Science Denotational Semantics Based on recursive function theory The most abstract semantics description method Originally developed by Scott and Strachey (1970) The process of building a denotational specification for a language: § Define a mathematical object for each language entity § Define a function that maps instances of the language entities onto instances of the corresponding mathematical objects The meaning of language constructs are defined by only the values of the program's variables CS 3304 Module 1: Midterm Exam 1 Review 38 38 19  Department of Computer Science Axiomatic Semantics Based on formal logic (predicate calculus) Original purpose: formal program verification Axioms or inference rules are defined for each statement type in the language (to allow transformations of logic expressions into more formal logic expressions) The logic expressions are called assertions CS 3304 Module 1: Midterm Exam 1 Review 39 39 Department of Computer Science Axiomatic Semantics Form Pre-, post form: {P} statement {Q} An example: a = b + 1 {a > 1} § One possible precondition: {b > 10} § Weakest precondition: {b > 0} CS 3304 Module 1: Midterm Exam 1 Review 40 40 20  Department of Computer Science Chapter 4: Lexical and Syntax Analysis Introduction Lexical Analysis The Parsing Problem Recursive-Descent Parsing Bottom-Up Parsing CS 3304 Module 1: Midterm Exam 1 Review 41 41 Department of Computer Science Syntax Analysis The syntax analysis portion of a language processor nearly always consists of two parts: § A low-level part called a lexical analyzer (mathematically, a finite automaton based on a regular grammar) § A high-level part called a syntax analyzer, or parser (mathematically, a push-down automaton based on a context-free grammar, or BNF) CS 3304 Module 1: Midterm Exam 1 Review 42 42 21  Department of Computer Science Reasons to Separate Lexical and Syntax Analysis Simplicity: less complex approaches can be used for lexical analysis; separating them simplifies the parser Efficiency: separation allows optimization of the lexical analyzer Portability: parts of the lexical analyzer may not be portable, but the parser always is portable CS 3304 Module 1: Midterm Exam 1 Review 43 43 Department of Computer Science Lexical Analysis A lexical analyzer is a pattern matcher for character strings A lexical analyzer is a “front-end” for the parser Identifies substrings of the source program that belong together - lexemes § Lexemes match a character pattern, which is associated with a lexical category called a token § sum is a lexeme; its token may be IDENT CS 3304 Module 1: Midterm Exam 1 Review 44 44 22  Department of Computer Science Regular Expressions A regular expression is one of the following: § A character § The empty string, denoted by ε § Two regular expressions concatenated § Two regular expressions separated by | (i.e., or) § A regular expression followed by the Kleene star * (concatenation of zero or more strings). Numerical literals in Pascal may be generated by the following: CS 3304 Module 1: Midterm Exam 1 Review 45 45 Department of Computer Science Lexical Analyzer The lexical analyzer is usually a function that is called by the parser when it needs the next token Three approaches to building a lexical analyzer: § Write a formal description of the tokens and use a software tool that constructs a table-driven lexical analyzer from such a description § Design a state diagram that describes the tokens and write a program that implements the state diagram § Design a state diagram that describes the tokens and hand-construct a table-driven implementation of the state diagram CS 3304 Module 1: Midterm Exam 1 Review 46 46 23  Department of Computer Science Deterministic Finite Automaton Pictorial representation of a scanner for calculator tokens, in the form of a finite automaton. This is a deterministic finite automaton (DFA): § lex, scangen, ANTLR, etc. build these things automatically from a set of regular expressions. § Specifically, they construct a machine that accepts the language. CS 3304 Module 1: Midterm Exam 1 Review 47 47 Department of Computer Science Building Lexers Scanners tend to be built three ways: § Ad-hoc § Semi-mechanical pure DFA (usually as nested case statements) § Table-driven DFA Ad-hoc generally yields the fastest, most compact code by doing lots of special- purpose things, though good automatically-generated scanners come very close Writing a pure DFA as a set of nested case statements is a surprisingly useful programming technique: § It is often easier to use perl, awk, sed or similar tools Table-driven DFA is what ANTLR produces CS 3304 Module 1: Midterm Exam 1 Review 48 48 24  Department of Computer Science The Parsing Problem Goals of the parser, given an input program: § Find all syntax errors; for each, produce an appropriate diagnostic message and recover quickly § Produce the parse tree, or at least a trace of the parse tree, for the program Two categories of parsers: § Top down: o Produce the parse tree, beginning at the root o Order is that of a leftmost derivation o Traces or builds the parse tree in preorder § Bottom up: o Produce the parse tree, beginning at the leaves o Order is that of the reverse of a rightmost derivation Useful parsers look only one token ahead in the input CS 3304 Module 1: Midterm Exam 1 Review 49 49 Department of Computer Science Faster Parsing Fortunately, there are large classes of grammars for which we can build parsers that run in linear time: § The two most important classes are called LL and LR. LL stands for ‘Left-to-right, Leftmost derivation’. LR stands for ‘Left-to-right, Rightmost derivation’. LL parsers are also called ‘top-down’, or 'predictive' parsers & LR parsers are also called ‘bottom-up’, or 'shift-reduce' parsers. There are several important sub-classes of LR parsers: § Simple LR parser (SLR). § Look-ahead LR parser (LALR). We won't be going into detail on the differences between them. CS 3304 Module 1: Midterm Exam 1 Review 50 50 25  Department of Computer Science Top-down Parsers Top-down Parsers § Given a sentential form xAa the parser must choose the correct A-rule to get the next sentential form in the leftmost derivation, using only the first token produced by A The most common top-down parsing algorithms: § Recursive descent: a coded implementation § LL parsers: table driven implementation CS 3304 Module 1: Midterm Exam 1 Review 51 51 Department of Computer Science Bottom-up Parsers Bottom-up parsers: § Given a right sentential form, a, determine what substring of a is the right-hand side of the rule in the grammar that must be reduced to produce the previous sentential form in the right derivation § The most common bottom-up parsing algorithms are in the LR family CS 3304 Module 1: Midterm Exam 1 Review 52 52 26  Department of Computer Science Recursive-Descent Parsing There is a subprogram for each nonterminal in the grammar, which can parse sentences that can be generated by that nonterminal EBNF is ideally suited for being the basis for a recursive-descent parser, because EBNF minimizes the number of nonterminals An example grammar for simple expressions: ® {(+ | -) } ® {(* | /) } ® id | int_constant | ( ) CS 3304 Module 1: Midterm Exam 1 Review 53 53 Department of Computer Science Left Recursion Problem The Left Recursion Problem of the LL Grammar Class § If a grammar has left recursion, either direct or indirect, it cannot be the basis for a top-down parser § A grammar can be modified to remove direct left recursion as follows: For each nonterminal A: 1. Group the A-rules as: A → Aα1 | … | Aαm | β1 | β2 | … | βn where none of the β’s begins with A 2. Replace the original A-rules with: A → β1A’ | β2A’ | … | βnA’ A’ → α1A’ | α2A’ | … | αmA’ | ε CS 3304 Module 1: Midterm Exam 1 Review 54 54 27  Department of Computer Science Pairwise Disjointness The other characteristic of grammars that disallows top-down parsing is the lack of pairwise disjointness: § The inability to determine the correct RHS on the basis of one token of lookahead § Def: FIRST(a) = {a | a =>* ab } (If a =>* e, e is in FIRST(a)) Pairwise Disjointness Test: § For each nonterminal, A, in the grammar that has more than one RHS, for each pair of rules, A ® ai and A ® aj, it must be true that: FIRST(ai) ⋂ FIRST(aj) = f § Example: A ® a | bB | cAb A ® a | aB CS 3304 Module 1: Midterm Exam 1 Review 55 55 Department of Computer Science Bottom-up Parsing The parsing problem is finding the correct RHS in a right-sentential form to reduce to get the previous right-sentential form in the derivation: Intuition about handles: § Def: b is the handle of the right sentential form g = abw if and only if (rm: rightmost) S =>*rm aAw =>rm abw § Def: b is a phrase of the right sentential form g if and only if S =>* g = a1Aa2 =>+ a1ba2 § Def: b is a simple phrase of the right sentential form g if and only if S =>* g = a1Aa2 => a1ba2 Discussion: § The handle of a right sentential form is its leftmost simple phrase § Given a parse tree, it is now easy to find the handle § Parsing can be thought of as handle pruning CS 3304 Module 1: Midterm Exam 1 Review 56 56 28  Department of Computer Science Chapter 5: Names, Bindings, and Scopes Introduction Names Variables The Concept of Binding Scope Scope and Lifetime Referencing Environments Named Constants CS 3304 Module 1: Midterm Exam 1 Review 57 57 Department of Computer Science Imperative Languages Imperative languages are abstractions of von Neumann architecture: § Memory § Processor Variables are characterized by attributes: § To design a type, must consider scope, lifetime, type checking, initialization, and type compatibility CS 3304 Module 1: Midterm Exam 1 Review 58 58 29  Department of Computer Science Name, Scope, and Binding A name is a mnemonic character string used to represent something else: § Most names are identifiers § Symbols (like '+') can also be names A binding is an association between two things, such as a name and the thing it names The scope of a binding is the part of the program (textually) in which the binding is active CS 3304 Module 1: Midterm Exam 1 Review 59 59 Department of Computer Science Names: Special Words An aid to readability; used to delimit or separate statement clauses A keyword is a word that is special only in certain contexts A reserved word is a special word that cannot be used as a user-defined name Potential problem with reserved words: § If there are too many, many collisions occur (e.g., COBOL has 300 reserved words!) CS 3304 Module 1: Midterm Exam 1 Review 60 60 30  Department of Computer Science Variables A variable is an abstraction of a memory cell Variables can be characterized as a sextuple of attributes: § Name § Address § Value § Type § Lifetime § Scope CS 3304 Module 1: Midterm Exam 1 Review 61 61 Department of Computer Science Types and Values Type: determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines the precision Value: the contents of the location with which the variable is associated: § The l-value of a variable is its address § The r-value of a variable is its value Abstract memory cell: the physical cell or collection of cells associated with a variable CS 3304 Module 1: Midterm Exam 1 Review 62 62 31  Department of Computer Science The Concept of Binding A binding is an association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol Binding time is the time at which a binding takes place CS 3304 Module 1: Midterm Exam 1 Review 63 63 Department of Computer Science Static and Dynamic Binding A binding is static if it first occurs before run time and remains unchanged throughout program execution A binding is dynamic if it first occurs during execution or can change during execution of the program CS 3304 Module 1: Midterm Exam 1 Review 64 64 32  Department of Computer Science Storage Allocation Mechanisms Static: objects are given an absolute address that is retained throughout the program’s execution Stack: objects are allocated and deallocated in last-in, first-out order, usually related to subroutine calls and returns Heap: objects allocated and deallocated at arbitrary times: § Need more general (expensive) storage management algorithm CS 3304 Module 1: Midterm Exam 1 Review 65 65 Department of Computer Science Garbage Collection Allocation of heap-based objects: triggered by some specific operation in a program (e.g., object instantiation) Deallocation: explicit in some languages (e.g., C++), implicit in others (e.g., Java) Garbage collection mechanism identifies and reclaims unreachable objects (implicitly deallocated) Explicit deallocation benefits: simplicity and execution speed provided that the programmer can correctly identify the end of an object’s lifetime Implicit deallocation (automatic garbage collection) benefits: eliminates manual allocation errors such as dangling reference and memory leak CS 3304 Module 1: Midterm Exam 1 Review 66 66 33  Department of Computer Science Variable Attributes: Scope The scope of a variable is the range of statements over which it is visible The local variables of a program unit are those that are declared in that unit The nonlocal variables of a program unit are those that are visible in the unit but not declared there Global variables are a special category of nonlocal variables The scope rules of a language determine how references to names are associated with variables CS 3304 Module 1: Midterm Exam 1 Review 67 67 Department of Computer Science Scope Rules Scope: a program section of maximal size in which no bindings change, or at least no re-declarations permitted In most languages with subroutines, we open a new scope on subroutine entry: § Create bindings for new local variables § Deactivate bindings for global variables that are re-declared (these variable are said to have a “hole” in their scope) § Make references to variables § On subroutine exit destroy bindings for local variables and reactivate bindings for the deactivated global variables Statically scoped: bindings based on purely textual rules (most languages, e.g., C, Java, C++) Dynamically scoped: bindings depend on the flow of execution during run time (APL, Snobol, Tcl, early Lisp) CS 3304 Module 1: Midterm Exam 1 Review 68 68 34  Department of Computer Science Elaboration Elaboration is the process by which declarations become active when control first enters a scope Elaboration entails the creation of bindings In many languages, it also entails the allocation of stack space for local objects, and possibly the assignment of initial values Ada: storage may be allocated, tasks started, or exceptions propagated as a result of the elaboration of declarations CS 3304 Module 1: Midterm Exam 1 Review 69 69 Department of Computer Science Static Scope Based on program text To connect a name reference to a variable, you (or the compiler) must find the declaration Search process: search declarations, first locally, then in increasingly larger enclosing scopes, until one is found for the given name Enclosing static scopes (to a specific scope) are called its static ancestors; the nearest static ancestor is called a static parent Some languages allow nested subprogram definitions, which create nested static scopes (e.g., Ada, JavaScript, Common Lisp, Scheme, Fortran 2003+, F#, and Python) CS 3304 Module 1: Midterm Exam 1 Review 70 70 35  Department of Computer Science Nonlocal Objects & Static Chains Access to non-local variables static links: § Each frame points to the frame of the (correct instance of) the routine inside which it was declared § In the absence of formal subroutines, correct means closest to the top of the stack § You access a variable in a scope k levels out by following k static links and then using the known offset within the frame thus found CS 3304 Module 1: Midterm Exam 1 Review 71 Department of Computer Science Dynamic Scoping Rules The key idea in static scope rules is that bindings are defined by the physical (lexical) structure of the program With dynamic scope rules, bindings depend on the current state of program execution: § They cannot always be resolved by examining the program because they are dependent on calling sequences § To resolve a reference, we use the most recent, active binding made at run time Dynamic scope rules are usually encountered in interpreted languages: § Early LISP dialects assumed dynamic scope rules Such languages do not normally have type checking at compile time because type determination isn’t always possible when dynamic scope rules are in effect CS 3304 Module 1: Midterm Exam 1 Review 72 72 36  Department of Computer Science Example: Static vs. Dynamic program scopes (input, output); var a : integer; procedure first; begin a := 1; end; procedure second; var a : integer; begin first; end; begin a := 2; second; write(a); end. If static scope rules are in effect (as would be the case in Pascal), the program prints 1 If dynamic scope rules are in effect, the program prints 2 The issue is whether the assignment to the variable a in procedure first changes the variable a declared in the main program or the variable a declared in procedure second CS 3304 Module 1: Midterm Exam 1 Review 73 73 Department of Computer Science Scope and Lifetime Scope and lifetime are sometimes closely related, but are different concepts Consider a static variable in a C or C++ function CS 3304 Module 1: Midterm Exam 1 Review 74 74 37  Department of Computer Science Referencing Environments The referencing environment of a statement is the collection of all names that are visible in the statement In a static-scoped language, it is the local variables plus all of the visible variables in all of the enclosing scopes A subprogram is active if its execution has begun but has not yet terminated In a dynamic-scoped language, the referencing environment is the local variables plus all visible variables in all active subprograms CS 3304 Module 1: Midterm Exam 1 Review 75 75 Department of Computer Science Summary Please review The Virginia Tech Undergraduate Honor System, for more information see: http://www.honorsystem.vt.edu/ CS 3304 Module 1: Midterm Exam 1 Review 76 76 38