Imperative ProgrammingReading AssignmentImperative ProgrammingElements of Imperative ProgramsVariable DeclarationsVariables: Locations and ValuesCopy vs. Reference SemanticsVariables and Assignmentl-Values and r-Values (1)l-Values and r-Values (2)l-Values and r-Values (3)Turing-Complete Mini-LanguageStructured Control FlowFortran Control StructureHistorical DebateModern StyleIterationIteration Constructs in C“Breaking Out” Of A Loop in CForced Loop Re-Entry in CBlock-Structured LanguagesBlocks in Common LanguagesSimplified Machine ModelMemory ManagementScope and LifetimeInline BlocksActivation Record For Inline BlockExampleslide 1Vitaly ShmatikovCS 345Imperative Programmingslide 2Reading AssignmentMitchell, Chapter 5.1-2C Reference Manual, Chapter 8slide 3Imperative ProgrammingOldest and most popular paradigm• Fortran, Algol, C, Java …Mirrors computer architecture• In a von Neumann machine, memory holds instructions and data Key operation: assignment• Side effect: updating state (i.e., memory) of the machineControl-flow statements• Conditional and unconditional (GO TO) branches, loopsslide 4Elements of Imperative ProgramsData type definitionsVariable declarations (usually typed)Expressions and assignment statementsControl flow statements (usually structured)Lexical scopes and blocks• Goal: provide locality of referenceDeclarations and definitions of procedures and functions (i.e., parameterized blocks)slide 5Variable DeclarationsTyped variable declarations restrict the values that a variable may assume during program execution• Built-in types (int, char …) or user-defined• Initialization: Java integers to 0. What about C?Variable size• How much space needed to hold values of this variable?– C on a 32-bit machine: sizeof(char) = 1 byte, sizeof(short) = 2 bytes, sizeof(int) = 4 bytes, sizeof(char*) = 4 bytes (why?)– What about this user-defined datatype:slide 6Variables: Locations and ValuesWhen a variable is declared, it is bound to some memory locationand becomes its identifier• Location could be in global, heap, or stack storagel-value: memory location (address)r-value: value stored at the memory location identified by l-valueAssignment: A (target) = B (expression)• Destructive update: overwrites the memory location identified by A with a value of expression B– What if a variable appears on both sides of assignment?slide 7Copy vs. Reference SemanticsCopy semantics: expression is evaluated to a value, which is copied to the target• Used by imperative languagesReference semantics: expression is evaluated to an object, whose pointer is copied to the target• Used by object-oriented languagesslide 8Variables and AssignmentOn the RHS of an assignment, use the variable’s r-value; on the LHS, use its l-value• Example: x = x+1• Meaning: “get r-value of x, add 1, store the result into the l-value of x”An expression that does not have an l-value cannot appear on the LHS of an assignment• What expressions don’t have l-values?– Examples: 1=x+1, ++x++ (why?)– What about a[1] = x+1, where a is an array? Why?slide 9l-Values and r-Values (1)Any expression or assignment statement in an imperative language can be understood in terms of l-values and r-values of variables involved• In C, also helps with complex pointer dereferencing and pointer arithmeticLiteral constants• Have r-values, but not l-valuesVariables• Have both r-values and l-values• Example: x=x*y means “compute rval(x)*rval(y) and store it in lval(x)”slide 10l-Values and r-Values (2)Pointer variables• Their r-values are l-values of another variable– Intuition: the value of a pointer is an addressOverriding r-value and l-value computation in C• &x always returns l-value of x• *p always return r-value of p– If p is a pointer, this is an l-value of another variableWhat are the values of p and x at this point?slide 11l-Values and r-Values (3)Declared functions and procedures• Have l-values, but no r-valuesslide 12Turing-Complete Mini-LanguageInteger variables, values, operationsAssignmentIfGo Toslide 13Structured Control FlowControl flow in imperative languages is most often designed to be sequential• Instructions executed in order they are written• Some also support concurrent execution (Java)Program is structured if control flow is evident from syntactic (static) structure of program text• Big idea: programmers can reason about dynamic execution of a program by just analyzing program text• Eliminate complexity by creating language constructs for common control-flow “patterns”– Iteration, selection, procedures/functionsslide 14Fortran Control Structure10 IF (X .GT. 0.000001) GO TO 2011 X = -XIF (X .LT. 0.000001) GO TO 5020 IF (X*Y .LT. 0.00001) GO TO 30X = X-Y-Y30 X = X+Y...50 CONTINUEX = AY = B-AGO TO 11… Similar structure may occur in assembly codeslide 15Historical DebateDijkstra, “GO TO Statement Considered Harmful”• Letter to Editor, Comm. ACM, March 1968• Linked from the course websiteKnuth, “Structured Prog. with Go To Statements”• You can use goto, but do so in structured way …Continued discussion• Welch, “GOTO (Considered Harmful)n, n is Odd”General questions• Do syntactic rules force good programming style?• Can they help?slide 16Modern StyleStandard constructs that structure jumpsif … then … else … endwhile … do … endfor … { … }case … Group code in logical blocks Avoid explicit jumps (except function return)Cannot jump intothe middle of a block or function bodyslide 17IterationDefiniteIndefinite• Termination depends on a dynamically computed valueHow do we know statically (i.e., before we run the program) that the loop will terminate, i.e., that n will eventually become less than or equal to 0?slide 18Iteration Constructs in C• while (condition) stmt;while (condition) { stmt; stmt; …; }• do stmt while (condition);do { stmt; stmt; …; } while (condition);• for (<initialize>; <test>; <step>) stmt;– Restricted form of “while” loop – same as<initialize>; while (<test>) { stmt; <step> }for (<initialize>; <test>; <step>) { stmt; stmt; …; }slide 19“Breaking Out” Of A Loop in Cslide 20Forced Loop Re-Entry in Cslide 21Block-Structured LanguagesNested blocks with local variables{ int x = 2;{ int y = 3;x = y+2;}}• Storage management–