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
CS 3361
| Term | Definition |
|---|---|
| Algorithms and data structures | Focuses on problem solving, often with constraints of time and space Early languages: Assembly, Fortran, Pascal, C Modern Languages: Python, Java, C++, C# |
| Software Development/Engineering | Needs reliability, maintainability, scalability Early languages: C Pascal, BASIC Modern languages: Java, C#, Python, Javascript, Ruby, Swift |
| Alphabets | A finite, non empty set of symbols Can be represented using ∑ |
| Syntax | A set of rules that a sequence of characters in a source course must be considered a conforming programming the that language The form of structure of the expressions, statements and program units |
| Sematics | Describes how valid a program is interpreted as sequences as computational steps The meaning of expressions, statements, or program units |
| Languages | A set of strings all of which are chosen from ∑*, where ∑ is a particular alphabet |
| Sentences | A set of strings that comprise a language built from characters over some alphabet Sometimes called statements |
| Lexeme | The lowest syntactic unit of a language |
| Token | A category of lexemes |
| Language recognizers | A device that reads input strings over the alphabet of the language and decides whether input strings belong to the language |
| Language notation: asterisk * | A certain value has to be included 0 or more times L(ab*c) = ac or abbbbbbbc |
| Language notation: plus + | A certain value has to be included 1 or more times L(ab+c) = abc or abbbbbbbc |
| Language notation: pipe | | A certain value has to include either the value directly before or after the pipe L(ab|c) = ab or ac |
| Language notation: Square Brackets [] | A certain value has to include one and ONLY one of the values inside them L(b[aei]d) = bad or bed or bid |
| Language notation: Parenthesis () | A groups one or more characters or strings and includes it in the value L((big) a) = big a |
| Language generators | A device that generates sentences of a language It can be used to determine if a sentences are syntactically correct |
| Vocabulary | Exhaustive sets of words or symbols that constructs languages |
| Chomsky Hierarchy: Type - 0 | Unrestricted grammar/languages |
| Chomsky Hierarchy: Type - 1 | Context sensitive grammar/languages |
| Chomsky Hierarchy: Type - 2 | Context-free grammar/languages |
| Chomsky Hierarchy: Type - 3 | Regular grammar/languages |
| Deterministic Finite Automata (DFA) | For each input there is one, and only one, state which an automation can transition from its current state |
| Nondeterministic Finite Automata (NFA) | For each input, they can put into multiple state to which an automation can transition from its current state |
| Derivation | A repeated application of rules, starting with the symbol and ending with a sentence |
| Ambiguity | A grammar is ambiguous if these exists one or more derivations that derive the same sentence |
| Parse Trees | The hierarchial structures of sentences of the languages they define |
| Attribute grammar | A device used to describe one or more of the structure of a programming that can be described with only a context free grammar |
| Attributes | Associated with grammar symbols Have a value assigned to them |
| Attribute computation functions | Associated with grammar rules sometimes called semantic functions |
| Predicate functions | Associated with grammar rules States the semantic rule of languages |
| Operational Semantics | Describe the meaning of a program by executing its statements on a machine, either stimulated or actual |
| Denotational Semantics | Based on the recursive function theory The most abstract semantic description method |
| Axiomatic semantics | based on predicate logic (predicate logic) |
| Rule of consequence | ({P}S{Q},P' => P,Q Q'{P'}S{Q'})/{P'}S{Q'} |
| Lexical Analysis | a pattern matcher to source things |
| Terminal Symbols | Lowercase letters at the beginning of the English alphabet (a, b, c ...) |
| Non-terminal symbols | Uppercase letters at the beginning of the English alphabet (A, B, C, ...) |
| String of terminals | Lowercase letters at the end of the English alphabet (x, y, z) |
| Terminals and nonterminals | Uppercase letters at the end of the English alphabet |
| Mixed strings (terminals and/or nonterminals) | Lowercase greek letters (α, ß, У, ) |
| EBNF: Brackets {} | Value has to appear from 0 to infinity times |
| EBNF: Square brackets [] | Value has to appear from 1 to infinity times |
| Shift reduce algorithms | The action of replacing the handle on the top of the parse stack with the corresponding LHS |
| Language Evaluation Criteria: Readability | The ease in which programs in a language can read and understood Readability must be considered in the context of the problem domain |
| Language Evaluation Criteria: Writeability | The ease with which a language can be used to create programs Writability must be considered in the context of the problem domain |
| Language Evaluation Criteria: Reliability | Conformance to specifications A program is said to be reliable if it performs to its specifications under all conditions |
| Language Evaluation Criteria: Cost | Training programmers to use the language Writing programs (closeness to particular applications) Executing programs |
| Language Evaluation Criteria: Portability | The ease with which programs can be moved from one implementation to another |
| Language Evaluation Criteria: Generality | The applicability to a wide range of applications |
| Language Evaluation Criteria: Well-definedness | The completeness and precision of the language’s official defining document |
| Language categories: Imperative | Central features are variables, assignment statements, and iteration Includes languages that support object-oriented programming Includes scripting languages Include visual languages Examples: C, Java, Perl, Javascript, Visual BASIC.NET, C++ |
| Language categories: Functional | Applies and composes functions to given parameters to drive computation Examples: LISP, Scheme, ML, F#, SequenceL |
| Language categories: Logic | Largely based on formal logic Rules are specified in no particular order Examples: Prolog, ASP, Datalog |
| Language categories: Markup/Programming hybrid | Markup languages themselves are not programming languages However, some programming capability has crept into some extensions to HTML and XML Examples: JSTL, XSLT |
| data type | a collection of data objects and a set of predefined operations on those objects |
| descriptor | The collection of the attributes of a variable |
| object | an instance of a user-defined (abstract data) type |
| Primitive data types | Those not defined in terms of other data types |
| Common Primitive Data Types: Boolean | Could be implemented as bits, but often as bytes. |
| Common Primitive Data Types: Character | Stored as numeric codings (ASCII / Unicode / etc.) |
| Common Primitive Data Types: Complex | Each value consists of two floats, the real part and the imaginary part. |
| Common Primitive Data Types: Decimal | Store a fixed number of decimal digits, in coded form (BCD) |
| Common Primitive Data Types: Floating Point | Model real numbers, but only as approximations. |
| Common Primitive Data Types: Integers | Can be up to 8 different integer types in a language. - Signed vs Unsigned & 8,16, 32 and 64 bit |
| Values | sequences of characters |
| Typical operations of Character String Types | - Assignment and copying - Comparison (=, >, etc.) - Catenation - Substring reference - Pattern matching |
| Character String Type: C and C++ | - Not primitive - Use char arrays and a library of functions that provide operations |
| Character String Type: Fortran and Python | Primitive type with assignment and several operations |
| Character String Type: Java (and C#, Ruby, and Swift) | Primitive via the String class |
| Character String Type: Perl, JavaScript, Ruby, and PHP | Provide built-in pattern matching, using regular expressions |
| Character String Length Options: Static | COBOL, Java’s String class |
| Character String Length Options: Limited Dynamic Length | C and C++ - In these languages, a special character is used to indicate the end of a string’s characters, rather than maintaining the length |
| Character String Length Options: Dynamic (no maximum) | Python, Perl, JavaScript |
| Array | A homogeneous aggregate of data elements in which an individual element is identified by its position in the aggregate, relative to the first element. |
| Indexing | a mapping from indices to elements |
| Index Syntax | - Fortran and Ada use parentheses - Most other languages use brackets |
| Heterogeneous Array | A array in which the elements need not be of the same type |
| Jagged matrix | A matrix has rows with varying number of elements |
| Associative Array | An unordered collection of data elements that are indexed by an equal number of values called keys |
| Tuple | A data type that is similar to an array |
| Lists were first supported in the first functional programming language | LISP |
| Lists in Lisp and Scheme are delimited by | parentheses and use no commas |
| List Operations in Scheme: CAR | Returns the first element of its list parameter - (CAR ′(A B C)) returns A |
| List Operations in Scheme: CDR | Returns the remainder of its list parameter after the first element has been removed - (CDR ′(A B C)) returns (B C) |
| List Operations in Scheme: CONS | puts its first parameter into its second parameter, a list, to make a new list - (CONS ′A ′(B C)) returns (A B C) |
| List Operations in Scheme: LIST | Returns a new list of its parameters - (LIST ′A ′B ′(C D)) returns (A B (C D)) |
| Python Lists | - Also serves as arrays - mutable - Elements can be of any type - Create with an assignment |
| Pointer | - Provide the power of indirect addressing - Provide a way to manage dynamic memory - A pointer can be used to access a location in the area where storage is dynamically created (usually called a heap) |
| Pointers: Assignment | Set a pointer variable’s value to some useful address |
| Pointers: Dereferencing | yields the value stored at the location represented by the pointer’s value - Can be explicit or implicit |
| Dangling pointers (dangerous) | A pointer points to a heap-dynamic variable that has been deallocated |
| Lost heap-dynamic variable | A variable that is no longer accessible to the user program (often called garbage) |
| Pointers can/are... | - Extremely flexible but must be used with care - Pointers can point at any variable regardless of when or where it was allocated |
| Statically typed languages | Type checking happens at compile time. |
| Dynamically typed languages | Type checking happens at run time. |
| Strongly typed languages | Type is assigned to a variable (compile or run-time) and retains that type and can’t be intermingled in expressions with other types easily. |
| Weakly typed languages | Type is assigned to a variable (compile or run-time) and can be intermingled in expressions with other types easily. |
| Type Declaration: static | All variable types have to be explicitly stated as this information is required at compile time |
| Type Declaration: Dynamic | Explicit declaration is not required as type is assigned to a variable at runtime. |
| Performance: Static | Do more processing at compile time but give better run-time performance |
| Performance: Dynamic | More efficient compiler/interpreters, but type-checking at run-time affects performance. |
| Flexibility and Errors: Static | Is less prone to runtime errors but provide less flexibility to programmer. |
| Flexibility and Errors: Dynamic | Provides more flexibility but more prone to runtime errors. |
| Names: Length | If too short, they cannot be connotative |
| Names: Format | - Must begin with a letter or underscore - Subsequent characters may consist of letters, digits, and underscores. |
| Names: Special words | An aid to readability; used to delimit or separate statement clauses |
| Keyword | A word that is special only in certain contexts. |
| Reserved word | - A special word that cannot be used as a user-defined name - Potential problem: If there are too many, many collisions occur |
| Variables | an abstraction of a memory cell |
| Variable Attributes: Address | - The location of the variable in the memory - Can be changed during execution (during time and place) |
| Variable Attributes: Name | - A word that is used to identify a variable - Not every variable has this |
| Variable Attributes: Type | Determines the range of values of variables and the set of operations that are defined for values of that type; in the case of floating point, type also determines the precision |
| Variable Attributes: Value | The contents of the location with which the variable is associated - The l-value of a variable is its address - The r-value of a variable is its value |
| Variable Attributes: Lifetime | The lifetime of a variable is the time during which it is bound to a particular memory cell |
| Variable Attributes: Scope | The scope of a variable is the range of statements over which it is visible |
| Binding | An association between an entity and an attribute, such as between a variable and its type or value, or between an operation and a symbol |
| Binding time | The time at which a binding takes place. |
| Static Binding | A binding that happens before run time and remains unchanged during the program |
| Dynamic binding | A binding that occurs first during execution and can change throughout the execution |
| Explicit Declaration | A program statement used for declaring the types of variables |
| Implicit Declaration | A default mechanism for specifying types of variables through default conventions, rather than declaration statements |
| Type Inferencing | The type of the variable is set in the context of the type of the value assigned to the variable in a declaration statement |
| Static Variable | Bound to memory cells before execution begins and remains bound to the same memory cell throughout execution - Efficient by not flexible |
| Stack-Dynamic Variable | - Variables that are allocated from the run-time stack - Allows recursion but overhead of allocation and deallocation and inefficient references (indirect addressing)* |
| Explicit Heap-Dynamic Variable | - Nameless (abstract) memory cells that are allocated and deallocated by explicit directives, specified by the programmer, which take effect during execution - Referenced only through pointers or references. - Provides for dynamic storage management but |
| Implicit Heap-Dynamic Variable | - Bound to heap storage when they are assigned values - Flexible but is Inefficient and lacks error detection |
| Scope: Local | The local variables of a program unit are those that are declared in that unit |
| Scope: Nonlocal | The nonlocal variables of a program unit are those that are visible in the unit but not declared there |
| Scope: Global | Global variables are a special category of nonlocal variables |
| Static Scope | The scope of a variable can be statically determined—that is, prior to execution |
| Two categories of static-scoped languages | - Those in which subprograms can be nested - Those in which subprograms can not be nested. |
| Blocks | A method for creating static scopes within sections of code |
| let construct | A let construct has two parts - The first part binds names to values - The second part uses the names defined in the first part |
| Global Variables | Variables declared outside of function definitions and behave differently than different variable |
| Expressions | The fundamental means to specify operations in a language |
| Arithmetic expressions consist of | Operators, operands, parenthesis, function calls |
| Arithmetic expressions: binary operators are | infix and have two operands Example from C: x + y |
| Arithmetic expressions: unary operators are | prefix and has one operand - Example from C: ++x |
| Operator precedence | Deifine the order that adjacent operators of different precidence are evaluated |
| Operator associativity | Define the order in which adjacent operators with the same precedence level are evaluated |
| Typical associativity rules | Left to right, except **, which is right to left Sometimes unary operators associate right to left (e.g., in FORTRAN) |
| Precedence and associativity rules can be overridden with... | Parentheses |
| Operand evaluation order: Variables | - 1st step - fetch the value from memory |
| Operand evaluation order: Constants | - 2nd step - Sometimes a fetch from memory; - Sometimes the constant is in the machine language instruction |
| Operand evaluation order: Parenthesized expressions | -3rd step - Evaluate all operands and operators first |
| Functional side effects | When a function changes a two-way parameter or a non-local variable |
| Problem with functional side effects: | When a function referenced in an expression alters another operand of the expression |
| Functional side effects – Solution#1 | - Write the language definition to disallow functional side effects - Write the language definition to demand that operand evaluation order be fixed |
| Overloaded Operators | - Use of an operator for more than one purpose is called operator overloading - Potential problems are loss of compiler error detection and some loss of readability |
| Uses of the + operator | - Integer Addition (Common) - Floating Point Addition (Common) - String Concatenation(Java, Python, others) - List Concatenation |
| Narrowing conversion | One that converts an object to a type that cannot include all the values of the original type |
| Widening conversion | One in which an object is converted to a type that can include at least approximations to all the values of the original type |
| Mixed-mode expression | An operation that has operands of different types |
| Coercion | Implicit type conversion |
| Disadvantage of coercions: | They decrease in the type error detection ability of the compiler |
| Primary Causes of errors of expressions | - Inherent limitations of arithmetic Ex: Division by zero - Limitations of computer arithmetic Ex: Overflow |
| Relational Expressions | - Use relational operators and operands of various types - Evaluate to some Boolean representation - Operator symbols used vary somewhat among languages. |
| Boolean Expressions | Operands are Boolean and the result is Boolean |
| Short Circuit Evaluation | An expression in which the result is determined without evaluating all of the operands and/or operators EX: A < B and B < C * If A<B evaluates false – no need to look at B < C. |
| Assignment can either be... | An expression or a statement |
| Parallel Computing | The simultaneous use of multiple compute resources to solve a computational problem |
| Node | A standalone server. |
| CPU | - One of the most misused terms in computing – often because the term’s meaning has shifted over time. - For our purposes, the CPU will refer to a physical processor within a node, with each CPU likely containing multiple “cores” |
| CPU Time | - The amount of time a process runs in terms of parallelism - cpu_time = wall_time x cores |
| Wall Clock Time | The amount of time it takes for the program to run but parallelism can cut back the time |
| Observed Speedup | wall clock time/ cpu time |
| Embarrassingly Parallel | Each task of a problem can be solved independently of all other tasks |
| Multi-core Computing | - Multi-core processors contain multiple ‘processing units’ (called cores) on a single chip. - Allows for parallel execution across cores – each able to reach the same system resources (RAM, Keyboard, Monitor, etc...) |
| Symmetric Multiprocessor (SMP) | - A symmetric multiprocessor is a computer system with multiple identical processors. - Each processor likely has multiple cores. - Allows for parallel execution across cores – each able to reach the same system resources (RAM, Keyboard, Monitor, etc... |
| Clusters | - A group of loosely coupled computers working together closely. - Processes can be spread across multiple nodes but processes are unable to reach the same system resources (RAM, Keyboard, Monitor, etc...) |
| Grid Computing | - Highly distributed form of parallel computing. - Clusters or single resources are spread across multiple sites using the Internet for connectivity. - Plagued by high latency issues. |
| Cloud Computing | - Same as Grids but often run by for-profit entities. - Sites are often spread over large geographic areas but most processing occurs within a single site – to help avoid latency issues. |
| Programming models: Serial programming | - Executes serially using a single core / thread - Single core machines |
| Programming models: Multi-core / Multi-threaded Programming | - Executes in parallel using multiple cores / threads - All threads are running on the same machine and access the same RAM - Multicore & Symmetric Multiprocessing |
| Programming models: Massively Parallel Programming | - Executes in parallel using multiple machines - Clusters, Massive Parallel Processors, & Grid/Cloud |
| Concurrency can occur at four levels: | - Machine instruction level -High-level language statement level - Unit level - Program level |
| Categories of Concurrency: Physical concurrency | Multiple independent processors ( multiple threads of control) |
| Categories of Concurrency: Coroutines (quasi-concurrency) | have a single thread of control |
| Thread of control | A program is the sequence of program points reached as control flows through the program |
| Task | - A unit of a program that can be in concurrent execution with other units of the same program. - Each task in a process can support one thread of control. |
| Process | Another name for a task. |
| Thread | Smallest sequence of programmed instructions that can be managed independently by a scheduler |
| Task Synchronization | A mechanism that controls the order in which tasks execute |
| Two kinds of synchronization: | Cooperation synchronization and Competition synchronization |
| Task communication is necessary for synchronization, provided by: | Shared nonlocal variables, Parameters, and Message passing |
| Cooperation | Task A must wait for task B to complete some specific activity before task A can continue its execution |
| Competition | Two or more tasks must use some resource that cannot be simultaneously used |
| Scheduler | Maps task execution onto available processors |
| Task Execution States: New | The task has been created but has not yet begun execution. |
| Task Execution States: Ready | The task is ready to run but is not currently running. |
| Task Execution States: Running | The task has been assigned a processor and the code is currently executing. |
| Task Execution States: Blocked | The task has been running but cannot continue. |
| Task Execution States:Dead | The task is no longer active in any sense. |
| Liveness | The state where a program is running |
| Race conditions | - Correct behavior of a program is dependent on the sequence/timing of other events. - Only an issue if one or more possible behaviors are undesirable. |
| Mutex lock | Ensure that only one thread at a time has access to an object |
| The two possible states of a mutex/mutex lock | Unlocked and locked |
| Lock overhead can include: | - Memory space allocated for the locks - CPU time spent to initialize, destroy or alter the locks - The time spent acquiring or releasing the lock |
| The more locks a program uses... | The higher the overhead associated with the usage |
| Lock Contention | Occurs when a process/thread attempts to acquire a lock held by another process/thread. |
| Deadlock | The situation when each of at least two tasks is waiting for a lock the other task holds |
| If used inproperly, locks can... | create deadlocks in code that wouldn’t have deadlocked previously |
| Course Granularity: | - Small number of locks, each protecting a large segment of data - Overhead: Results in less lock overhead when a single process is accessing the data. - Contention: Results in worse performance when multiple processes are running concurrently. |
| Fine Granularity: | - Larger number of locks, each protecting a fairly small amount of data. - Overhead: Results in increased overhead when a single process is accessing the data. - Contention: Results in better performance when multiple processes are running concurrentl |
| Semaphore | A data structure consisting of a counter and a queue for storing task descriptors |
| Difference between mutex locks and semaphores | - An object’s mutex can only be acquired by one thread at a time. - An object’s semaphore contains a thread counter, so it can be acquired by multiple threads simultaneously. |
| Monitors | - Abstract data types for shared data - Encapsulate the shared data and its operation to restrict access |
| Semaphores and Monitors can... | Implement each other |
| Message Passing | Is used for communication among processes (not threads) |
| Communication between process pairs | - Send/Receive or Put/Get - Synchronous or asynchronous |
| Synchronous Communication | - Multiple parties continually listen for and act upon replies from each other. - Real world example: Phone Conversation |
| Asynchronous Communication | - Parties do not actively listen for messages. - Real world example: Text Messaging |
| Collective communication | Communication between processes |
| Process group (collective) | Several processes logically grouped together |
| Communication Patterns – Broadcast | One process sends the same data to all processes. |
| Communication Patterns – Multicast | - One process sends the same data to many processes - Many processes send the same data to many processes - One-to-many vs many-to-many |
| Communication Patterns – Scatter | One process sends different data to all processes |
| Communication Patterns – Gather | One process receives results from all processes |
| Amdahl’s Law | Calculates how much a computation can be sped up by running it in parallel Total Time = Nonparallelizable + (Total Time – Nonparalleizable) |
| Parallel Overhead | The amount of time it takes for parallelization |
| CPU Bound | - The rate of execution is limited by the speed of the CPU. - A process is considered CPU bound if it spends most of its time simply using the CPU. |
| I/O Bound | - The rate of execution is limited by the speed of the I/O subsystem or time spent waiting for input. - A process if considered I/O bound if it spends most of its time handling I/O |
| Memory Bound | - The rate of execution is limited by the amount of memory available and the speed of memory access. - A process is considered memory bound if it processes large amounts of memory or spends much of its time waiting on the memory subsystems |
| Cache Bound | - The rate of execution is limited by the speed and size of the onboard cache. - A process if considered cache bound if it processes more data than fits in the cache. |
| Lambda expression | Applied to parameter(s) by placing the parameter(s) after the expression |
| Higher-order function, or functional form either | - Takes functions as parameters, - Yields a function as its result, or - Does both. |
| Functional Forms: Functional Composition | A functional form that takes two functions as parameters and yields a function whose value is the first actual parameter function applied to the application of the second. |
| Functional Forms: | A functional form that takes a single function as a parameter and yields a list of values obtained by applying the given function to each element of a list of parameters |
| Fundamentals of Functional Programming Languages | - Mimic mathematical functions to the greatest extent possible - Variables are not necessary, as is the case in mathematics |
| Referential Transparency | In a Functional Programming Language, the evaluation of a function always produces the same result given the same parameters |
| Data object types: | originally only atoms and lists |
| List form: | Parenthesized collections of sublists and/or atoms Ex: (A B (C D) E) |
| Scheme program | Collection of function definitions |
| Proposition | A logical statement that may or may not be true |
| Symbolic Logic | Logic which can be used for the basic needs of formal logic |
| Predicate calculus | A particular form of symbolic logic used for logic programming |
| Objects in propositions are represented by simple either... | constants or variables |
| Constant | A symbol that represents an object |
| Atomic propositions | consist of compound terms |
| Compound term | One element of a mathematical relation, written like a mathematical function |
| Compound Terms: Functor | Function symbol that names the relationship |
| Compound Terms: Tuple | Ordered list of parameters |
| Propositions: Fact | Proposition is assumed to be true |
| Propositions: Query | Truth of proposition is to be determined |
| Compound proposition | - Have two or more atomic propositions - Propositions are connected by operators |
| Resolution | An inference principle that allows inferred propositions to be computed from given propositions |
| Unification | Finding values for variables in propositions that allows the matching process to succeed |
| Instantiation | Assigning temporary values to variables to allow the unification to succeed |
| Declarative semantics | - There is a simple way to determine the meaning of each statement - Simpler than the semantics of imperative languages |
| Prolog - Term | A constant, variable, or structure |
| Prolog - Constant | An atom or an integer |
| Prolog - Atom | Symbolic value of Prolog. Can either be... - a string of letters, digits, and underscores beginning with a lowercase letter - a string of printable ASCII characters delimited by apostrophes |
| Prolog - Variable | Any string of letters, digits, and underscores beginning with an uppercase letter |
| Prolog - Instantiation | - Binding of a variable to a value - Lasts only as long as it takes to satisfy one complete goal |
| Prolog - Structure | Represents atomic proposition Ex: functor(parameter list) |
Created by:
Valitine
Popular Miscellaneous sets