X

Download About Programming Languages PowerPoint Presentation

SlidesFinder-Advertising-Design.jpg

Login   OR  Register
X


Iframe embed code :



Presentation url :

Home / Education & Training / Education & Training Presentations / About Programming Languages PowerPoint Presentation

About Programming Languages PowerPoint Presentation

Ppt Presentation Embed Code   Zoom Ppt Presentation

PowerPoint is the world's most popular presentation software which can let you create professional About Programming Languages powerpoint presentation easily and in no time. This helps you give your presentation on About Programming Languages in a conference, a school lecture, a business proposal, in a webinar and business and professional representations.

The uploader spent his/her valuable time to create this About Programming Languages powerpoint presentation slides, to share his/her useful content with the world. This ppt presentation uploaded by onlinesearch in Education & Training ppt presentation category is available for free download,and can be used according to your industries like finance, marketing, education, health and many more.

About This Presentation

About Programming Languages Presentation Transcript

Slide 1 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming
Slide 2 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8
Slide 3 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops
Slide 4 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages
Slide 8 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point?
Slide 11 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values
Slide 12 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To
Slide 13 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions
Slide 14 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code
Slide 15 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body
Slide 17 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; }
Slide 19 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C
Slide 20 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C
Slide 21 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated
Slide 22 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated slide 22 Blocks in Common Languages Examples C, JavaScript * { … } Algol begin … end ML let … in … end Two forms of blocks Inline blocks Blocks associated with functions or procedures We’ll talk about these later * JavaScript functions provides blocks
Slide 23 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated slide 22 Blocks in Common Languages Examples C, JavaScript * { … } Algol begin … end ML let … in … end Two forms of blocks Inline blocks Blocks associated with functions or procedures We’ll talk about these later * JavaScript functions provides blocks slide 23 Simplified Machine Model Registers Environment pointer Program counter Data Code Heap Stack
Slide 24 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated slide 22 Blocks in Common Languages Examples C, JavaScript * { … } Algol begin … end ML let … in … end Two forms of blocks Inline blocks Blocks associated with functions or procedures We’ll talk about these later * JavaScript functions provides blocks slide 23 Simplified Machine Model Registers Environment pointer Program counter Data Code Heap Stack slide 24 Memory Management Registers, Code segment, Program counter Ignore registers (for our purposes) and details of instruction set Data segment Stack contains data related to block entry/exit Heap contains data of varying lifetime Environment pointer points to current stack position Block entry: add new activation record to stack Block exit: remove most recent activation record
Slide 25 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated slide 22 Blocks in Common Languages Examples C, JavaScript * { … } Algol begin … end ML let … in … end Two forms of blocks Inline blocks Blocks associated with functions or procedures We’ll talk about these later * JavaScript functions provides blocks slide 23 Simplified Machine Model Registers Environment pointer Program counter Data Code Heap Stack slide 24 Memory Management Registers, Code segment, Program counter Ignore registers (for our purposes) and details of instruction set Data segment Stack contains data related to block entry/exit Heap contains data of varying lifetime Environment pointer points to current stack position Block entry: add new activation record to stack Block exit: remove most recent activation record slide 25 Scope and Lifetime Scope Region of program text where declaration is visible Lifetime Period of time when location is allocated to program Inner declaration of x hides outer one (“hole in scope”) Lifetime of outer x includes time when inner block is executed Lifetime  scope { int x = … ; { int y = … ; { int x = … ; …. }; }; };
Slide 26 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated slide 22 Blocks in Common Languages Examples C, JavaScript * { … } Algol begin … end ML let … in … end Two forms of blocks Inline blocks Blocks associated with functions or procedures We’ll talk about these later * JavaScript functions provides blocks slide 23 Simplified Machine Model Registers Environment pointer Program counter Data Code Heap Stack slide 24 Memory Management Registers, Code segment, Program counter Ignore registers (for our purposes) and details of instruction set Data segment Stack contains data related to block entry/exit Heap contains data of varying lifetime Environment pointer points to current stack position Block entry: add new activation record to stack Block exit: remove most recent activation record slide 25 Scope and Lifetime Scope Region of program text where declaration is visible Lifetime Period of time when location is allocated to program Inner declaration of x hides outer one (“hole in scope”) Lifetime of outer x includes time when inner block is executed Lifetime  scope { int x = … ; { int y = … ; { int x = … ; …. }; }; }; slide 26 Inline Blocks Activation record Data structure stored on run-time stack Contains space for local variables May need space for variables and intermediate results like (x+y), (x-y)
Slide 27 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated slide 22 Blocks in Common Languages Examples C, JavaScript * { … } Algol begin … end ML let … in … end Two forms of blocks Inline blocks Blocks associated with functions or procedures We’ll talk about these later * JavaScript functions provides blocks slide 23 Simplified Machine Model Registers Environment pointer Program counter Data Code Heap Stack slide 24 Memory Management Registers, Code segment, Program counter Ignore registers (for our purposes) and details of instruction set Data segment Stack contains data related to block entry/exit Heap contains data of varying lifetime Environment pointer points to current stack position Block entry: add new activation record to stack Block exit: remove most recent activation record slide 25 Scope and Lifetime Scope Region of program text where declaration is visible Lifetime Period of time when location is allocated to program Inner declaration of x hides outer one (“hole in scope”) Lifetime of outer x includes time when inner block is executed Lifetime  scope { int x = … ; { int y = … ; { int x = … ; …. }; }; }; slide 26 Inline Blocks Activation record Data structure stored on run-time stack Contains space for local variables May need space for variables and intermediate results like (x+y), (x-y) slide 27 Activation Record For Inline Block Control link Pointer to previous record on stack Push record on stack Set new control link to point to old env ptr Set env ptr to new record Pop record off stack Follow control link of current record to reset environment pointer Control link Local variables Intermediate results Control link Local variables Intermediate results Environment pointer In practice, can be optimized away
Slide 28 - slide 1 Vitaly Shmatikov CS 345 Imperative Programming slide 2 Reading Assignment Mitchell, Chapter 5.1-2 C Reference Manual, Chapter 8 slide 3 Imperative 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, loops slide 4 Elements 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 5 Variable 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 6 Variables: Locations and Values When a variable is declared, it is bound to some memory location and 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 7 Copy 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 languages slide 8 Variables 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 9 l-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 10 l-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 variable What are the values of p and x at this point? slide 11 l-Values and r-Values (3) Declared functions and procedures Have l-values, but no r-values slide 12 Turing-Complete Mini-Language Integer variables, values, operations Assignment If Go To slide 13 Structured 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/functions slide 14 Fortran Control Structure 10 IF (X .GT. 0.000001) GO TO 20 11 X = -X IF (X .LT. 0.000001) GO TO 50 20 IF (X*Y .LT. 0.00001) GO TO 30 X = X-Y-Y 30 X = X+Y ... 50 CONTINUE X = A Y = B-A GO TO 11 … Similar structure may occur in assembly code slide 15 Historical 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 16 Modern Style Standard constructs that structure jumps if … then … else … end while … do … end for … { … } case … Group code in logical blocks Avoid explicit jumps (except function return) Cannot jump into the middle of a block or function body slide 17 Iteration Definite Indefinite Termination depends on a dynamically computed value How 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 18 Iteration Constructs in C while (condition) stmt; while (condition) { stmt; stmt; …; } do stmt while (condition); do { stmt; stmt; …; } while (condition); for (; ; ) stmt; Restricted form of “while” loop – same as ; while () { stmt; } for (; ; ) { stmt; stmt; …; } slide 19 “Breaking Out” Of A Loop in C slide 20 Forced Loop Re-Entry in C slide 21 Block-Structured Languages Nested blocks with local variables { int x = 2; { int y = 3; x = y+2; } } Storage management Enter block: allocate space for variables Exit block: some or all space may be deallocated slide 22 Blocks in Common Languages Examples C, JavaScript * { … } Algol begin … end ML let … in … end Two forms of blocks Inline blocks Blocks associated with functions or procedures We’ll talk about these later * JavaScript functions provides blocks slide 23 Simplified Machine Model Registers Environment pointer Program counter Data Code Heap Stack slide 24 Memory Management Registers, Code segment, Program counter Ignore registers (for our purposes) and details of instruction set Data segment Stack contains data related to block entry/exit Heap contains data of varying lifetime Environment pointer points to current stack position Block entry: add new activation record to stack Block exit: remove most recent activation record slide 25 Scope and Lifetime Scope Region of program text where declaration is visible Lifetime Period of time when location is allocated to program Inner declaration of x hides outer one (“hole in scope”) Lifetime of outer x includes time when inner block is executed Lifetime  scope { int x = … ; { int y = … ; { int x = … ; …. }; }; }; slide 26 Inline Blocks Activation record Data structure stored on run-time stack Contains space for local variables May need space for variables and intermediate results like (x+y), (x-y) slide 27 Activation Record For Inline Block Control link Pointer to previous record on stack Push record on stack Set new control link to point to old env ptr Set env ptr to new record Pop record off stack Follow control link of current record to reset environment pointer Control link Local variables Intermediate results Control link Local variables Intermediate results Environment pointer In practice, can be optimized away slide 28 Example