CS 3304 Comparative Languages Midterm Exam 2 Review 2024 PDF

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

Department of Computer Science CS 3304 Comparative Languages Module 2 Midterm Exam 2 Review © 2024 Denis Gracanin 1 Department of Computer Science Introduction The midterm exam 2 is a closed book exam. Please review The Virginia Tech Undergraduate Honor System: http://www.honorsystem.vt.edu Duration: 75 minutes: § CRN 83353: 6 November 2024, 2:30pm-3:45pm, Surge 104C § CRN 83354: 5 November 2024, 9:30am-10:45pm, Graduate Life Center at Donaldson Brown 64 § CRN 83353: 5 November 2024, 2:00pm-3:15pm, New Classroom Building 260 It covers Chapters 6-10 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 2.1-2.9 and related assignments (Homeworks 3 and 4, Project 1) are included CS 3304 Module 2: Midterm Exam 2 Review 2 2 1  Department of Computer Science Chapter 6: Data Types Primitive Data Types Character String Types Enumeration Types Array Types Associative Arrays Record Types Tuple Types List Types Union Types Pointer and Reference Types Optional Types Type Checking Strong Typing Type Equivalence Theory and Data Types CS 3304 Module 2: Midterm Exam 2 Review 3 3 Department of Computer Science Data Types A data type defines a collection of data objects and a set of predefined operations on those objects A descriptor is the collection of the attributes of a variable An object represents an instance of a user-defined (abstract data) type One design issue for all data types: What operations are defined and how are they specified? CS 3304 Module 2: Midterm Exam 2 Review 4 4 2  Department of Computer Science Primitive Data Types Almost all programming languages provide a set of primitive data types Primitive data types: Those not defined in terms of other data types Some primitive data types are merely reflections of the hardware Others require only a little non-hardware support for their implementation Includes: § Integer § Floating Point § Complex § Decimal § Boolean § Character CS 3304 Module 2: Midterm Exam 2 Review 5 5 Department of Computer Science Character String Types and Operations Values are sequences of characters Design issues: § Is it a primitive type or just a special kind of array? § Should the length of strings be static or dynamic? Typical operations: § Assignment and copying § Comparison (=, >, etc.) § Catenation § Substring reference § Pattern matching CS 3304 Module 2: Midterm Exam 2 Review 6 6 3  Department of Computer Science User-Defined Ordinal Types An ordinal type is one in which the range of possible values can be easily associated with the set of positive integers Examples of primitive ordinal types in Java: § integer § char § boolean CS 3304 Module 2: Midterm Exam 2 Review 7 7 Department of Computer Science Enumeration Types All possible values, which are named constants, are provided in the definition C# example: enum days {mon, tue, wed, thu, fri, sat, sun}; Design issues: § Is an enumeration constant allowed to appear in more than one type definition, and if so, how is the type of an occurrence of that constant checked? § Are enumeration values coerced to integer? § Any other type coerced to an enumeration type? CS 3304 Module 2: Midterm Exam 2 Review 8 8 4  Department of Computer Science Array Design Issues What types are legal for subscripts? Are subscripting expressions in element references range checked? When are subscript ranges bound? When does allocation take place? Are ragged or rectangular multidimensional arrays allowed, or both? What is the maximum number of subscripts? Can array objects be initialized? Are any kind of slices supported? CS 3304 Module 2: Midterm Exam 2 Review 9 9 Department of Computer Science Subscript Binding and Array Categories Static: subscript ranges are statically bound and storage allocation is static (before run-time): § Advantage: efficiency (no dynamic allocation) Fixed stack-dynamic: subscript ranges are statically bound, but the allocation is done at declaration time: § Advantage: space efficiency Fixed heap-dynamic: similar to fixed stack-dynamic: storage binding is dynamic but fixed after allocation (i.e., binding is done when requested and storage is allocated from heap, not stack) Heap-dynamic: binding of subscript ranges and storage allocation is dynamic and can change any number of times: § Advantage: flexibility (arrays can grow or shrink during program execution) CS 3304 Module 2: Midterm Exam 2 Review 10 10 5  Department of Computer Science Rectangular and Jagged Arrays A rectangular array is a multi-dimensioned array in which all of the rows have the same number of elements and all columns have the same number of elements A jagged matrix has rows with varying number of elements: § Possible when multi-dimensioned arrays actually appear as arrays of arrays C, C++, and Java support jagged arrays F# and C# support rectangular arrays and jagged arrays CS 3304 Module 2: Midterm Exam 2 Review 11 11 Department of Computer Science Slices A slice is some substructure of an array; nothing more than a referencing mechanism Slices are only useful in languages that have array operations Examples: § Python: vector = [2, 4, 6, 8, 10, 12, 14, 16] mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] vector (3:6) is a three-element array mat[0:2] is the first and second element of the first row of mat § Ruby supports slices with the slice method: list.slice(2, 2) returns the third and fourth elements of list CS 3304 Module 2: Midterm Exam 2 Review 12 12 6  Department of Computer Science Implementation of Arrays Access function maps subscript expressions to an address in the array Access function for single-dimensioned arrays: address(list[k]) = address (list[lower_bound]) + ((k-lower_bound) * element_size) CS 3304 Module 2: Midterm Exam 2 Review 13 13 Department of Computer Science Record Types A record is a possibly heterogeneous aggregate of data elements in which the individual elements are identified by names Design issues: § What is the syntactic form of references to the field? § Are elliptical references allowed CS 3304 Module 2: Midterm Exam 2 Review 14 14 7  Department of Computer Science Tuple Types A tuple is a data type that is similar to a record, except that the elements are not named Used in Python, ML, and F# to allow functions to return multiple values Python: § Closely related to its lists, but immutable § Create with a tuple literal: myTuple = (3, 5.8, 'apple') § Referenced with subscripts (begin at 1) § Catenation with + and deleted with del CS 3304 Module 2: Midterm Exam 2 Review 15 15 Department of Computer Science List Types Lists in Lisp and Scheme are delimited by parentheses and use no commas: (A B C D) and (A (B C) D) Data and code have the same form: § As data, (A B C) is literally what it is § As code, (A B C) is the function A applied to the parameters B and C The interpreter needs to know which a list is, so if it is data, we quote it with an apostrophe: '(A B C) is data CS 3304 Module 2: Midterm Exam 2 Review 16 16 8  Department of Computer Science Unions Types A union is a type whose variables are allowed to store different type values at different times during execution Design issue: § Should type checking be required? CS 3304 Module 2: Midterm Exam 2 Review 17 17 Department of Computer Science Discriminated vs. Free Unions C and C++ provide union constructs in which there is no language support for type checking; the union in these languages is called free union Type checking of unions require that each union include a type indicator called a discriminant: § Supported by ML, Haskell, and F# CS 3304 Module 2: Midterm Exam 2 Review 18 18 9  Department of Computer Science Pointer and Reference Types A pointer type variable has a range of values that consists of memory addresses and a special value, nil Provide the power of indirect addressing Provide a way to manage dynamic memory A pointer can be used to access a location in the area where storage is dynamically created (usually called a heap) CS 3304 Module 2: Midterm Exam 2 Review 19 19 Department of Computer Science Design Issues of Pointers What are the scope of and lifetime of a pointer variable? What is the lifetime of a heap-dynamic variable? Are pointers restricted as to the type of value to which they can point? Are pointers used for dynamic storage management, indirect addressing, or both? Should the language support pointer types, reference types, or both? CS 3304 Module 2: Midterm Exam 2 Review 20 20 10  Department of Computer Science Problems with Pointers Dangling pointers (dangerous): § A pointer points to a heap-dynamic variable that has been deallocated Lost heap-dynamic variable: § An allocated heap-dynamic variable that is no longer accessible to the user program (often called garbage): o Pointer p1 is set to point to a newly created heap-dynamic variable o Pointer p1 is later set to point to another newly created heap-dynamic variable o The process of losing heap-dynamic variables is called memory leakage CS 3304 Module 2: Midterm Exam 2 Review 21 21 Department of Computer Science Reference Types C++ includes a special kind of pointer type called a reference type that is used primarily for formal parameters: § Advantages of both pass-by-reference and pass-by-value Java extends C++’s reference variables and allows them to replace pointers entirely: § References are references to objects, rather than being addresses C# includes both the references of Java and the pointers of C++ CS 3304 Module 2: Midterm Exam 2 Review 22 22 11  Department of Computer Science Type Checking Generalize the concept of operands and operators to include subprograms and assignments Type checking is the activity of ensuring that the operands of an operator are of compatible types A compatible type is one 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: this automatic conversion is called a coercion Type error: the application of an operator to an operand of an inappropriate type If all type bindings are static, nearly all type checking can be static If type bindings are dynamic, type checking must be dynamic A programming language is strongly typed if type errors are always detected Advantage of strong typing: allows the detection of the misuses of variables that result in type errors CS 3304 Module 2: Midterm Exam 2 Review 23 23 Department of Computer Science Strong Typing Language examples: § C and C++ are not: parameter type checking can be avoided; unions are not type checked § Java and C# are, almost: because of explicit type casting § ML and F# are Coercion rules strongly affect strong typing: they can weaken it considerably (C++ versus ML and F#) Although Java has just half the assignment coercions of C++, its strong typing is still far less effective than that of Ada CS 3304 Module 2: Midterm Exam 2 Review 24 24 12  Department of Computer Science Name Type Equivalence Name type equivalence means the two variables have equivalent types if they are in either the same declaration or in declarations that use the same type name Easy to implement but highly restrictive: § Subranges of integer types are not equivalent with integer types § Formal parameters must be the same type as their corresponding actual parameters CS 3304 Module 2: Midterm Exam 2 Review 25 25 Department of Computer Science Structure Type Equivalence Structure type equivalence means that two variables have equivalent types if their types have identical structures More flexible, but harder to implement Consider the problem of two structured types: § Are two record types equivalent if they are structurally the same but use different field names? § Are two array types equivalent if they are the same except that the subscripts are different? e.g., [1..10] and [0..9] § Are two enumeration types equivalent if their components are spelled differently? § With structural type equivalence, you cannot differentiate between types of the same structure: e.g., different units of speed, both float CS 3304 Module 2: Midterm Exam 2 Review 26 26 13  Department of Computer Science Chapter 7: Expressions and Assignments Statements Introduction Arithmetic Expressions Overloaded Operators Type Conversions Relational and Boolean Expressions Short-Circuit Evaluation Assignment Statements Mixed-Mode Assignment CS 3304 Module 2: Midterm Exam 2 Review 27 27 Department of Computer Science Expressions Expressions are the fundamental means of specifying computations in a programming language To understand expression evaluation, need to be familiar with the orders of operator and operand evaluation Essence of imperative languages is dominant role of assignment statements CS 3304 Module 2: Midterm Exam 2 Review 28 28 14  Department of Computer Science Arithmetic Expressions Arithmetic evaluation was one of the motivations for the development of the first programming languages Arithmetic expressions consist of operators, operands, parentheses, and function calls In most languages, binary operators are infix, except in Scheme and LISP, in which they are prefix; Perl also has some prefix binary operators Most unary operators are prefix, but the ++ and –- operators in C-based languages can be either prefix or postfix CS 3304 Module 2: Midterm Exam 2 Review 29 29 Department of Computer Science Arithmetic Expressions: Operator Precedence Rules The operator precedence rules for expression evaluation define the order in which “adjacent” operators of different precedence levels are evaluated Typical precedence levels: § parentheses § unary operators § ** (if the language supports it) § *, / § +, - CS 3304 Module 2: Midterm Exam 2 Review 30 30 15  Department of Computer Science Arithmetic Expressions: Operator Associativity Rule The operator associativity rules for expression evaluation define the order in which adjacent operators with the same precedence level are evaluated Typical associativity rules: § Left to right, except **, which is right to left § Sometimes unary operators associate right to left (e.g., in FORTRAN) APL is different; all operators have equal precedence and all operators associate right to left Precedence and associativity rules can be overridden with parentheses CS 3304 Module 2: Midterm Exam 2 Review 31 31 Department of Computer Science Arithmetic Expressions: Operand Evaluation Order Operand evaluation order: § Variables: fetch the value from memory § Constants: sometimes a fetch from memory; sometimes the constant is in the machine language instruction § Parenthesized expressions: evaluate all operands and operators first § The most interesting case is when an operand is a function call CS 3304 Module 2: Midterm Exam 2 Review 32 32 16  Department of Computer Science Functional Side Effects Two possible solutions to the problem: § Write the language definition to disallow functional side effects: o No two-way parameters in functions o No non-local references in functions o Advantage: it works! o Disadvantage: inflexibility of one-way parameters and lack of non-local references § Write the language definition to demand that operand evaluation order be fixed: o Disadvantage: limits some compiler optimizations o Java requires that operands appear to be evaluated in left-to-right order CS 3304 Module 2: Midterm Exam 2 Review 33 33 Department of Computer Science Referential Transparency A program has the property of referential transparency if any two expressions in the program that have the same value can be substituted for one another anywhere in the program, without affecting the action of the program: result1 = (fun(a) + b) / (fun(a) – c); temp = fun(a); result2 = (temp + b) / (temp – c); If fun has no side effects, result1 == result2 Otherwise, not, and referential transparency is violated Advantage of referential transparency: § Semantics of a program is much easier to understand if it has referential transparency CS 3304 Module 2: Midterm Exam 2 Review 34 34 17  Department of Computer Science Overloaded Operators Use of an operator for more than one purpose is called operator overloading Some are common (e.g., + for int and float) Some are potential trouble (e.g., * in C and C++): § Loss of compiler error detection (omission of an operand should be a detectable error) § Some loss of readability CS 3304 Module 2: Midterm Exam 2 Review 35 35 Department of Computer Science Type Conversions A narrowing conversion is one that converts an object to a type that cannot include all of the values of the original type e.g., float to int A widening conversion is one in which an object is converted to a type that can include at least approximations to all of the values of the original type, e.g., int to float CS 3304 Module 2: Midterm Exam 2 Review 36 36 18  Department of Computer Science Relational Expressions Use relational operators and operands of various types Evaluate to some Boolean representation Operator symbols used vary somewhat among languages (!=, /=, ~=,.NE., , #) JavaScript and PHP have two additional relational operators, === and !== Similar to their cousins, == and !=, except that they do not coerce their operands Ruby uses == for equality relation operator that uses coercions and eql? for those that do not CS 3304 Module 2: Midterm Exam 2 Review 37 37 Department of Computer Science Boolean Expressions Boolean Expressions: § Operands are Boolean and the result is Boolean § Example operators C89 has no Boolean type: it uses int type with 0 for false and nonzero for true One odd characteristic of C’s expressions: a < b < c is a legal expression, but the result is not what you might expect: § Left operator is evaluated, producing 0 or 1 § The evaluation result is then compared with the third operand (i.e., c) CS 3304 Module 2: Midterm Exam 2 Review 38 38 19  Department of Computer Science Short Circuit Evaluation An expression in which the result is determined without evaluating all of the operands and/or operators Example: (13 * a) * (b / 13 – 1) § If a is zero, there is no need to evaluate (b /13 - 1) Problem with non-short-circuit evaluation: index = 0; while (index < length) && (LIST[index] != value) index++; § When index==length, LIST[index] will cause an indexing problem (assuming LIST is length - 1 long) CS 3304 Module 2: Midterm Exam 2 Review 39 39 Department of Computer Science Assignments Functional language: expressions are the building blocks: § If computation is expression evaluation that depends only on the referencing environment for that evaluation § Expressions in a purely functional language are referentially transparent: value depends only on the referencing environment Imperative language: computation usually ordered series of changes to the values of variables in memory: § Assignments provide the principal means for these changes Side effect: a programming construct influences subsequent computation in any way other than by returning a value for use in the surrounding context: § Expressions: always produce value and may have side effects § Statements: executed solely for the side effects § Imperative programming: computing by means of side effects CS 3304 Module 2: Midterm Exam 2 Review 40 40 20  Department of Computer Science References and Values Subtle but important differences in the semantics of assignment in different imperative languages: § Context based: a variable may refer to the value of the variable (r-value) or its location (l-value) – a named container for a value Value model of variables: an expression is either an l-value or an r-value, based on the context in which it appears: § Built-in types can’t be passed uniformly to methods expecting class type parameters: wrapper classes, automatic boxing/unboxing Reference model of variables: a variable is a named reference for a value – every variable is an l-value: a 4 a 4 § E.g., integer values (like 2) are immutable b 2 b § A variable has to be dereferenced to obtain its value 2 c 2 c CS 3304 Module 2: Midterm Exam 2 Review 41 41 Department of Computer Science Assignment Statements The general syntax: The assignment operator: = Fortran, BASIC, the C-based languages := Ada = can be bad when it is overloaded for the relational operator for equality: § That’s why the C-based languages use == as the relational operator CS 3304 Module 2: Midterm Exam 2 Review 42 42 21  Department of Computer Science Combination Assignment Operators Imperative languages frequently update variables and can use statements like a = a + 1; that result in redundant address calculations: § If the address calculation has a side effect, It has to be rewritten using additional statement(s) Starting with Algol 68, many languages provide assignment operators to update variables, e.g., a += 1; C provides 10 different assignment operators, one for each of it binary arithmetic and bit-wise operators: § Additionally, prefix and postfix increment and decrement operators Multiway assignment - tuples: § a,b = c,d means a = c; b = d; § a,b = b,a; swapping variable values § a,b,c = foo(d,e,f); functions return tuples and single values CS 3304 Module 2: Midterm Exam 2 Review 43 43 Department of Computer Science Assignment Statements: Unary Assignment Operators Unary assignment operators in C-based languages combine increment and decrement operations with assignment Examples: sum = ++count (count incremented, then assigned to sum) sum = count++ (count assigned to sum, then incremented) count++ (count incremented) -count++ (count incremented then negated) CS 3304 Module 2: Midterm Exam 2 Review 44 44 22  Department of Computer Science Mixed-Mode Assignment Assignment statements can also be mixed-mode In Fortran, C, Perl, and C++, any numeric type value can be assigned to any numeric type variable In Java and C#, only widening assignment coercions are done In Ada, there is no assignment coercion CS 3304 Module 2: Midterm Exam 2 Review 45 45 Department of Computer Science Chapter 8: Statement-Level Control Structures Introduction Selection Statements Iterative Statements Unconditional Branching Guarded Commands Conclusions CS 3304 Module 2: Midterm Exam 2 Review 46 46 23  Department of Computer Science Control Structure A control structure is a control statement and the statements whose execution it controls Design question: § Should a control structure have multiple entries? CS 3304 Module 2: Midterm Exam 2 Review 47 47 Department of Computer Science Selection Statements A selection statement provides the means of choosing between two or more paths of execution Two general categories: § Two-way selectors § Multiple-way selectors CS 3304 Module 2: Midterm Exam 2 Review 48 48 24  Department of Computer Science Two-Way Selection Statements General form: if control_expression then clause else clause Design Issues: § What is the form and type of the control expression? § How are the then and else clauses specified? § How should the meaning of nested selectors be specified? CS 3304 Module 2: Midterm Exam 2 Review 49 49 Department of Computer Science Multiple-Way Selection Statements Allow the selection of one of any number of statements or statement groups Design Issues: § What is the form and type of the control expression? § How are the selectable segments specified? § Is execution flow through the structure restricted to include just a single selectable segment? § How are case values specified? § What is done about unrepresented expression values? CS 3304 Module 2: Midterm Exam 2 Review 50 50 25  Department of Computer Science Implementing Multiple Selectors Approaches: § Multiple conditional branches § Store case values in a table and use a linear search of the table § When there are more than ten cases, a hash table of case values can be used § If the number of cases is small and more than half of the whole range of case values are represented, an array whose indices are the case values and whose values are the case labels can be used CS 3304 Module 2: Midterm Exam 2 Review 51 51 Department of Computer Science Iterative Statements The repeated execution of a statement or compound statement is accomplished either by iteration or recursion General design issues for iteration control statements: § How is iteration controlled? § Where is the control mechanism in the loop? CS 3304 Module 2: Midterm Exam 2 Review 52 52 26  Department of Computer Science Counter-Controlled Loops A counting iterative statement has a loop variable, and a means of specifying the initial and terminal, and stepsize values Design Issues: § What are the type and scope of the loop variable? § Should it be legal for the loop variable or loop parameters to be changed in the loop body, and if so, does the change affect loop control? § Should the loop parameters be evaluated only once, or once for every iteration? § What is the value of the loop variable after loop termination? CS 3304 Module 2: Midterm Exam 2 Review 53 53 Department of Computer Science Logically-Controlled Loops Repetition control is based on a Boolean expression Design issues: § Pretest or posttest? § Should the logically controlled loop be a special case of the counting loop statement or a separate statement? CS 3304 Module 2: Midterm Exam 2 Review 54 54 27  Department of Computer Science User-Located Loop Control Mechanisms Sometimes it is convenient for the programmers to decide a location for loop control (other than top or bottom of the loop) Simple design for single loops (e.g., break) Design issues for nested loops: § Should the conditional be part of the exit? § Should control be transferable out of more than one loop? CS 3304 Module 2: Midterm Exam 2 Review 55 55 Department of Computer Science Iteration Based on Data Structures The number of elements in a data structure controls loop iteration Control mechanism is a call to an iterator function that returns the next element in some chosen order, if there is one; else loop is terminated C's for can be used to build a user-defined iterator: for (p=root; p==NULL; traverse(p)) {... } CS 3304 Module 2: Midterm Exam 2 Review 56 56 28  Department of Computer Science Unconditional Branching Transfers execution control to a specified place in the program Represented one of the most heated debates in 1960’s and 1970’s Major concern: Readability Some languages do not support goto statement (e.g., Java) C# offers goto statement (can be used in switch statements) Loop exit statements are restricted and somewhat camouflaged goto’s CS 3304 Module 2: Midterm Exam 2 Review 57 57 Department of Computer Science Guarded Commands Designed by Dijkstra Purpose: to support a new programming methodology that supported verification (correctness) during development Basis for two linguistic mechanisms for concurrent programming (in CSP) Basic Idea: if the order of evaluation is not important, the program should not specify one CS 3304 Module 2: Midterm Exam 2 Review 58 58 29  Department of Computer Science Selection Guarded Command Form: if -> [] ->... [] -> fi Semantics: when construct is reached: § Evaluate all Boolean expressions § If more than one are true, choose one non-deterministically § If none are true, it is a runtime error CS 3304 Module 2: Midterm Exam 2 Review 59 59 Department of Computer Science Loop Guarded Command Form: do -> [] ->... [] -> od Semantics: for each iteration: § Evaluate all Boolean expressions § If more than one are true, choose one non-deterministically; then start loop again § If none are true, exit loop CS 3304 Module 2: Midterm Exam 2 Review 60 60 30  Department of Computer Science Chapter 9: Subprograms Introduction Fundamentals of Subprograms Design Issues for Subprograms Local Referencing Environments Parameter-Passing Methods Parameters That Are Subprograms Calling Subprograms Indirectly Design Issues for Functions Overloaded Subprograms Generic Subprograms User-Defined Overloaded Operators Closures Coroutines CS 3304 Module 2: Midterm Exam 2 Review 61 61 Department of Computer Science Abstraction Two fundamental abstraction facilities: § Process abstraction: o Emphasized from early days o Discussed in this chapter (Chapter 9) § Data abstraction: o Emphasized in the1980s o Discussed at length in Chapter 11 CS 3304 Module 2: Midterm Exam 2 Review 62 62 31  Department of Computer Science Basic Definitions 1/2 A subprogram definition describes the interface to and the actions of the subprogram abstraction: § Python: function definitions are executable; in all other languages, they are non- executable § Ruby: function definitions can appear either in or outside of class definitions. If outside, they are methods of Object: o They can be called without an object, like a function § Lua: all functions are anonymous A subprogram call is an explicit request that the subprogram be executed A subprogram header is the first part of the definition, including the name, the kind of subprogram, and the formal parameters The parameter profile (aka signature) of a subprogram is the number, order, and types of its parameters CS 3304 Module 2: Midterm Exam 2 Review 63 63 Department of Computer Science Basic Definitions 2/2 The protocol is a subprogram’s parameter profile and, if it is a function, its return type Function declarations in C and C++ are often called prototypes A subprogram declaration provides the protocol, but not the body, of the subprogram A formal parameter is a dummy variable listed in the subprogram header and used in the subprogram An actual parameter represents a value or address used in the subprogram call statement CS 3304 Module 2: Midterm Exam 2 Review 64 64 32  Department of Computer Science Actual/Formal Parameter Correspondence Positional: § The binding of actual parameters to formal parameters is by position: the first actual parameter is bound to the first formal parameter and so forth § Safe and effective Keyword: § The name of the formal parameter to which an actual parameter is to be bound is specified with the actual parameter § Advantage: parameters can appear in any order, thereby avoiding parameter correspondence errors § Disadvantage: user must know the formal parameter’s names CS 3304 Module 2: Midterm Exam 2 Review 65 65 Department of Computer Science Procedures and Functions There are two categories of subprograms: § Procedures are collection of statements that define parameterized computations § Functions structurally resemble procedures but are semantically modeled on mathematical functions: o They are expected to produce no side effects o In practice, program functions have side effects CS 3304 Module 2: Midterm Exam 2 Review 66 66 33  Department of Computer Science Design Issues for Subprograms Are local variables static or dynamic? Can subprogram definitions appear in other subprogram definitions? What parameter passing methods are provided? Are parameter types checked? If subprograms can be passed as parameters and subprograms can be nested, what is the referencing environment of a passed subprogram? Are functional side effects allowed? What types of values can be returned from functions? How many values can be returned from functions? Can subprograms be overloaded? Can subprogram be generic? If the language allows nested subprograms, are closures supported? CS 3304 Module 2: Midterm Exam 2 Review 67 67 Department of Computer Science Local Referencing Environments Local variables can be stack-dynamic: § Advantages: o Support for recursion o Storage for locals is shared among some subprograms § Disadvantages: o Allocation/de-allocation, initialization time o Indirect addressing o Subprograms cannot be history sensitive Local variables can be static: § Advantages and disadvantages are the opposite of those for stack-dynamic local variables CS 3304 Module 2: Midterm Exam 2 Review 68 68 34  Department of Computer Science Semantic Models of Parameter Passing In mode Out mode Inout mode CS 3304 Module 2: Midterm Exam 2 Review 69 69 Department of Computer Science Design Considerations for Parameter Passing Two important considerations: § Efficiency § One-way or two-way data transfer But the above considerations are in conflict: § Good programming suggest limited access to variables, which means one-way whenever possible § But pass-by-reference is more efficient to pass structures of significant size CS 3304 Module 2: Midterm Exam 2 Review 70 70 35  Department of Computer Science Conceptual Models of Transfer Physically move a value Move an access path to a value Approaches: § Pass-by-Value (In Mode) § Pass-by-Result (Out Mode) § Pass-by-Value-Result (inout Mode) § Pass-by-Reference (Inout Mode) § Pass-by-Name (Inout Mode) CS 3304 Module 2: Midterm Exam 2 Review 71 71 Department of Computer Science Parameters that are Subprogram Names: Referencing Environment Shallow binding: § The environment of the call statement that enacts the passed subprogram § Most natural for dynamic-scoped languages Deep binding: § The environment of the definition of the passed subprogram § Most natural for static-scoped languages Ad hoc binding: § The environment of the call statement that passed the subprogram CS 3304 Module 2: Midterm Exam 2 Review 72 72 36  Department of Computer Science Implementing Parameter-Passing Methods Function header: void sub(int a, int b, int c, int d) Function call in main: sub(w, x, y, z) § Pass w by value § Pass x by result § Pass y by value-result § Pass z by reference CS 3304 Module 2: Midterm Exam 2 Review 73 73 Department of Computer Science Calling Subprograms Indirectly Usually when there are several possible subprograms to be called and the correct one on a particular run of the program is not know until execution (e.g., event handling and GUIs) In C and C++, such calls are made through function pointers CS 3304 Module 2: Midterm Exam 2 Review 74 74 37  Department of Computer Science Design Issues for Functions Are side effects allowed? § Parameters should always be in-mode to reduce side effect (like Ada) What types of return values are allowed? § Most imperative languages restrict the return types § C allows any type except arrays and functions § C++ is like C but also allows user-defined types § Java and C# methods can return any type (but because methods are not types, they cannot be returned) § Python and Ruby treat methods as first-class objects, so they can be returned, as well as any other class CS 3304 Module 2: Midterm Exam 2 Review 75 75 Department of Computer Science Overloaded Subprograms An overloaded subprogram is one that has the same name as another subprogram in the same referencing environment: § Every version of an overloaded subprogram has a unique protocol C++, Java, C#, and Ada include predefined overloaded subprograms In Ada, the return type of an overloaded function can be used to disambiguate calls (thus two overloaded functions can have the same parameters) Ada, Java, C++, and C# allow users to write multiple versions of subprograms with the same name CS 3304 Module 2: Midterm Exam 2 Review 76 76 38  Department of Computer Science Generic Subprograms A generic or polymorphic subprogram takes parameters of different types on different activations Overloaded subprograms provide ad hoc polymorphism Subtype polymorphism means that a variable of type T can access any object of type T or any type derived from T (OOP languages) A subprogram that takes a generic parameter that is used in a type expression that describes the type of the parameters of the subprogram provides parametric polymorphism: § A cheap compile-time substitute for dynamic binding CS 3304 Module 2: Midterm Exam 2 Review 77 77 Department of Computer Science Closures A closure is a subprogram and the referencing environment where it was defined: § The referencing environment is needed if the subprogram can be called from any arbitrary place in the program § A static-scoped language that does not permit nested subprograms doesn’t need closures § Closures are only needed if a subprogram can access variables in nesting scopes and it can be called from anywhere § To support closures, an implementation may need to provide unlimited extent to some variables (because a subprogram may access a nonlocal variable that is normally no longer alive) CS 3304 Module 2: Midterm Exam 2 Review 78 78 39  Department of Computer Science Coroutines A coroutine is a subprogram that has multiple entries and controls them itself – supported directly in Lua Also called symmetric control: caller and called coroutines are on a more equal basis A coroutine call is named a resume The first resume of a coroutine is to its beginning, but subsequent calls enter at the point just after the last executed statement in the coroutine Coroutines repeatedly resume each other, possibly forever Coroutines provide quasi-concurrent execution of program units (the coroutines); their execution is interleaved, but not overlapped CS 3304 Module 2: Midterm Exam 2 Review 79 79 Department of Computer Science Chapter 10: Implementing Subprograms The General Semantics of Calls and Returns Implementing “Simple” Subprograms Implementing Subprograms with Stack-Dynamic Local Variables Nested Subprograms Blocks Implementing Dynamic Scoping CS 3304 Module 2: Midterm Exam 2 Review 80 80 40  Department of Computer Science The General Semantics of Calls and Returns The subprogram call and return operations of a language are together called its subprogram linkage General semantics of calls to a subprogram: § Parameter passing methods § Stack-dynamic allocation of local variables § Save the execution status of calling program § Transfer of control and arrange for the return § If subprogram nesting is supported, access to nonlocal variables must be arranged CS 3304 Module 2: Midterm Exam 2 Review 81 81 Department of Computer Science Implementing “Simple” Subprograms Call Semantics: § Save the execution status of the caller § Pass the parameters § Pass the return address to the called § Transfer control to the called Return Semantics: § If pass-by-value-result or out mode parameters are used, move the current values of those parameters to their corresponding actual parameters § If it is a function, move the functional value to a place the caller can get it § Restore the execution status of the caller § Transfer control back to the caller Required storage: § Status information, parameters, return address, return value for functions, temporaries CS 3304 Module 2: Midterm Exam 2 Review 82 82 41  Department of Computer Science Implementing Subprograms with Stack-Dynamic Local Variables More complex activation record: § The compiler must generate code to cause implicit allocation and deallocation of local variables § Recursion must be supported (adds the possibility of multiple simultaneous activations of a subprogram) CS 3304 Module 2: Midterm Exam 2 Review 83 83 Department of Computer Science Implementing Subprograms with Stack-Dynamic Local Variables: Activation Record The activation record format is static, but its size may be dynamic The dynamic link points to the top of an instance of the activation record of the caller An activation record instance is dynamically created when a subprogram is called Activation record instances reside on the run-time stack The Environment Pointer (EP) must be maintained by the run-time system. It always points at the base of the activation record instance of the currently executing program unit CS 3304 Module 2: Midterm Exam 2 Review 84 42  Department of Computer Science Dynamic Chain and Local Offset The collection of dynamic links in the stack at a given time is called the dynamic chain, or call chain Local variables can be accessed by their offset from the beginning of the activation record, whose address is in the EP. § This offset is called the local_offset The local_offset of a local variable can be determined by the compiler at compile time CS 3304 Module 2: Midterm Exam 2 Review 85 85 Department of Computer Science Nested Subprograms Some non-C-based static-scoped languages (e.g., Fortran 95+, Ada, Python, JavaScript, Ruby, and Swift) use stack-dynamic local variables and allow subprograms to be nested All variables that can be non-locally accessed reside in some activation record instance in the stack The process of locating a non-local reference: § Find the correct activation record instance § Determine the correct offset within that activation record instance CS 3304 Module 2: Midterm Exam 2 Review 86 86 43  Department of Computer Science Static Scoping A static chain is a chain of static links that connects certain activation record instances The static link in an activation record instance for subprogram A points to one of the activation record instances of A's static parent The static chain from an activation record instance connects it to all of its static ancestors static_depth is an integer associated with a static scope whose value is the depth of nesting of that scope CS 3304 Module 2: Midterm Exam 2 Review 87 87 Department of Computer Science Blocks Blocks are user-specified local scopes for variables An example in C: { int temp; temp = list [upper]; list [upper] = list [lower]; list [lower] = temp; } The lifetime of temp in the above example begins when control enters the block An advantage of using a local variable like temp is that it cannot interfere with any other variable with the same name CS 3304 Module 2: Midterm Exam 2 Review 88 88 44  Department of Computer Science Implementing Dynamic Scoping Deep Access: non-local references are found by searching the activation record instances on the dynamic chain: § Length of the chain cannot be statically determined § Every activation record instance must have variable names Shallow Access: put locals in a central place: § One stack for each variable name § Central table with an entry for each variable name CS 3304 Module 2: Midterm Exam 2 Review 89 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 2: Midterm Exam 2 Review 90 90 45