Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
ProgLang Finals
REVIEWER MODULE 8-11
| Term | Definition |
|---|---|
| Semantics | definition of the meaning of any syntactically and type-wise correct program. |
| programming language | well-defined only when its semantics, syntax, and type system are fully defined. |
| Evaluation of Expression | crucial in programming languages. |
| In mathematics | expressions are pure, meaning they have no side effects, making the order of subexpression evaluation unimportant. |
| Infix Notation | Most programming languages use infix notation for binary operations, where the operator is placed between operands. Example: (a+b)−(c∗d) |
| Associativity and Precedence | To eliminate ambiguity, associativity and precedence rules are assigned to operators. |
| Polish Notation - Prefix | Operator before operands. Example: −+ab∗cd |
| Polish Notation - Postfix | Operator after operands. Example: ab+cd∗− |
| Limitations | Cannot use the same symbol for operations with different arities. |
| Cambridge Prefix Notation | Operator precedes operands, enclosed in parentheses. Example: (−(+ab)(∗cd)) |
| N-ary Operators | Example: (+abcd) |
| Short-Circuit Evaluation | Evaluates a Boolean expression from left to right, stopping as soon as the truth value is determined. AND: if (! A) false else B if (! A) false else B OR: if (A) true else B if (A) true else B |
| Assignment Semantics | The source expression is evaluated in the current state, resulting in a value that replaces the target variable's value, leading to a new state. |
| Multiple Assignment - Support | Many languages support multiple target variables for a single source expression. Example: a=b=c=0 |
| Turing Completeness | A language is Turing complete if it can compute any computable function and has sequence, conditional, and looping statements. |
| Bohm-Jacopini Theorem | Establishes the requirements for Turing completeness. |
| Branching | Includes return, break, continue, and goto statements |
| Return | Terminates a function or method immediately. |
| Break and Continue | Used primarily in loops. |
| Conditionals - Types | Basic if statements and case (switch) statements. |
| Conditionals - Usage | Select alternative paths during program execution. |
| Loops - While Loop | Executes while the expression is true. Syntax: while (Expression) Statement |
| Do-While Loop | Executes the statement once and then repeats while the expression is true. Syntax: do Statement while (Expression) |
| For Loop | Convenient for counting and iterating over arrays Example: for (int i = 0; i < SIZE; i++) sum += a[i]; |
| Iterators | Allow for flexible loop control. |
| Break Statement | Terminates a loop from anywhere within its body. |
| Continue Statement | Aborts the current iteration and begins the next. |
| Input/Output (I/O) - File Handling: Opening Files | Must locate and open before accessing. |
| Input/Output (I/O) - File Handling: Access Modes | Sequential or random access |
| Access Modes - Sequential | Entities are read/written in order. |
| Access Modes - Random | Entities can be accessed in any order. |
| Input/Output (I/O) - File Handling: Closing Files | Releases control so other programs can access the file later. |
| Standard Files - Keyboard Input and Screen Output | Identified as standard files. |
| Standard Files - Error Messages | Stored in a standard error file. |
| Standard Files - Java Naming | System.in, System.out, System.err (similar to C's stdin, stdout, stderr). |
| Input/Output Streams - File Streams | Transfer data to/from the file system. |
| Input/Output Streams - Pipe Streams | Direct data from one stream to another |
| Input/Output Streams - Memory Streams | Transfer data between memory and the program. |
| Input/Output Streams - Filter Streams | Perform transformations like buffering or encryption. |
| Understanding Semantics | Essential for defining and comprehending programming languages. |
| Expression Evaluation | Central to programming, with considerations for side effects and evaluation order. |
| Control Structures | Fundamental for creating comprehensive and functional programs. |
| I/O Handling | Crucial for interacting with external data sources and managing program input/output efficiently. |
| MODULE 9 | MODULE9 |
| Functions | a fundamental concept in programming languages, providing a tool for abstraction. |
| Functions | are essential tools for abstraction, allowing code to be modular, reusable, and easier to understand. |
| Procedures, subroutines, subprograms, or methods | Different terms used in various programming languages to describe functions. |
| Distinctions in Languages - Fortran and Ada | Differentiate between functions (return a value) and subroutines/procedures (do not return a value). |
| C-like languages | Do not differentiate; both are termed functions. |
| C++ and Java | Use the term "method" for a function declared inside a class. |
| Control Return - Void functions/procedures | Return control when the end of the function body is reached or a return statement is encountered. |
| Control Return - Non-void functions | Return control when a return statement with an expression is encountered, designating the return value. |
| Parameters | Identifiers in a function declaration. |
| Arguments | Expressions in a function call. |
| Algol/Pascal | Use "actual parameter" for an argument in the call and "formal parameter" for a parameter in the function declaration. |
| C/Java | Use "argument" for the former and "parameter" for the latter |
| Some texts | Use "parameter" synonymously with "argument". |
| Parameter Passing Mechanisms - Five Principal Ways | By Value, By Reference, By Value-Result, By Result, and By Name |
| By Value | The value is computed and copied to the parameter. It only passes a copy, hence changes in the parameter do not affect the argument. |
| By Reference | The memory address of the argument is copied to the parameter, allowing the function to modify the actual argument. |
| By Value-Result | Combines pass by value and pass by result, copying the argument's value at the start and the computed result back at the end. |
| By Result | Copies the computed parameter value back to the argument at the end of the call. |
| By Name | Textually substitutes the argument for each parameter occurrence, evaluated when used by the function. |
| Program State | defined as the binding of all active objects to their current values. |
| Environment | This map pairs active objects (variables) with specific memory locations. |
| Memory | This map pairs active memory locations with their current values. |
| memory example part1: | Example: Consider variables i and j with values 13 and -1 respectively during execution. If i and j are associated with memory locations 154 and 155, the state can be represented as: |
| memory example part2: | Environment: {<i 154>, <j 155>} Memory: {<0 undef>, ..., <154 13>, <155 -1>} Here, undef denotes an undefined memory value. |
| State Transformations | refer to the changes that occur in a program's state during its execution. These transformations can be modeled as a series of state-transforming functions. |
| Denotational Semantics | The denotational semantics of a language involves defining the meanings of abstract language elements as collections of state-transforming functions. |
| Elements Needed for Semantics | Mathematical Entities, State Model, and Partial Functions |
| Mathematical Entities | Basic elements like integers, real numbers, characters, and booleans. |
| State Model | For a simple language like Clite, the state can be represented as a set of variable-value pairs. |
| Partial Functions | These functions are not defined for all possible input states, e.g., division by zero. |
| Implementation | The meaning of an abstract program can be defined as a set of functions (M) that transform the program state. In Clite, these functions define the meaning of program constructs like Skip, Block, Conditional, Loop, and Assignment. |
| Meaning of a Program- Function Definitions: | M: Program -> State, M: Statement × State -> State, and M: Expression × State -> Value |
| M: Program -> State | The meaning of a Program is a function that produces a State. |
| M: Statement × State -> State | The meaning of a Statement, given a current State, produces a new State. |
| M: Expression × State -> Value | The meaning of an Expression, given a current State, produces a Value. |
| Initial State | The meaning of a program's body starts with an initial state where all declared variables are undefined. This state changes as the program executes, with variables being assigned and reassigned values. |
| Example Program: Consider a Clite program that computes the factorial of a number n: | void main() { int n, i, f; n = 3; i = 1; f = 1; while (i < n) { i = i + 1; f = f * i; } } |
| The program's state transitions can be mapped as follows: | 1. Initial state: <n undef>, <i undef>, <f undef> 2. After n = 3: <n 3>, <i undef>, <f undef> 3. After i = 1: <n 3>, <i 1>, <f undef> 4. After f = 1: <n 3>, <i 1>, <f 1> |
| continuation of the example: Each step represents a state transformation as per the semantic definitions. | 5. During loop (first iteration): <n 3>, <i 2>, <f 1> 6, After f = f * i (first iteration): <n 3>, <i 2>, <f 2> 7. During loop (second iteration): <n 3>, <i 3>, <f 2> 8. After f = f * i (second iteration): <n 3>, <i 3>, <f 6> |
| Environment and Memory | Crucial for understanding the program state as they map variables to memory locations and values, respectively. |
| State Transformations | Central to how a program executes and changes over time. |
| Denotational Semantics | Provides a mathematical foundation for understanding program behavior. |
| Initial State | Important for determining the starting point of the program's execution. |
| Partial Functions | Highlight limitations and special cases in program execution. |
| Memory Structure in Programming Languages | Static Area, Run-Time Stack, and Heap |
| Static Area | This is where values with known storage requirements at compile time are stored. These values remain constant throughout the program's execution. |
| Run-Time Stack | Manages the active functions, locally-declared variables, and parameter-argument linkages during program execution. |
| Heap | Contains dynamically allocated values, such as strings, dynamic arrays, objects, and other dynamic data structures like linked lists. |
| Heap Memory States | Unused, Undef, and Elementary Value |
| Unused | The memory word is not allocated to the program. |
| Undef | The memory word is allocated but not yet assigned a value. |
| Elementary Value | The memory word holds a basic value like an integer or float. |
| Heap Management Functions | new and delete |
| new | Allocates a contiguous block of memory in the heap and returns the address of the first word, marking the words as undef. Example: new(5) allocates a block of 5 words. |
| delete | Deallocates a contiguous block of memory, returning it to the unused state Example: delete(h + 10, 5) deallocates the block starting at h + 10. |
| Heap Overflow | Occurs when a new operation cannot find a contiguous block of unused memory large enough to satisfy the request. |
| Dynamic Arrays | Arrays whose size is not known until runtime are allocated space in both the stack and the heap. |
| The stack | holds a reference to the array's starting address, while the heap holds the array's entries. |
| Dope Vector | Created to manage the array, containing the array's address, size, and type. Steps: 1. Compute the address for the array. 2. Push the address onto the stack. 3. Push the array size onto the stack. 4. Push the array type onto the stack. |
| Garbage | Blocks of heap memory that cannot be accessed by the program, typically because no pointers reference them. |
| Garbage: Creation | Can occur when the dope vector for a dynamically allocated array is removed before the heap block is deallocated. Example: A linked list node becoming orphaned when its reference is removed. |
| Garbage Collection | Reclaims unused heap blocks for later use by the program. |
| Strategies: Reference Counting | Tracks the number of pointers referencing each node. When a node's count reaches zero, it and its descendants are returned to the free list. |
| Reference Counting Algorithm: | 1. Increase the reference count for the new node. 2. Decrease the reference count for the old node. 3. If a node's count reaches zero, return it to the free list. |
| Mark-Sweep | Invoked when the heap is full. Makes two passes on the heap: |
| Mark Pass | Marks all accessible nodes. |
| Sweep Pass | Returns unmarked nodes to the free list. |
| Copy Collection | Divides the heap into two blocks (from_space and to_space). Only one block is active at a time, and nodes are copied and repacked into the inactive block when the active block is full. This repacks active nodes and frees up space. |
| Heap Overflow | Must handle situations where new cannot allocate the requested memory. |
| Memory Leaks | Prevent garbage by ensuring all allocated memory is properly deallocated. |
| Performance | Different garbage collection strategies have varying impacts on performance and memory usage. |
Created by:
JonasTiglao28
Popular Computers sets