Final ! Will be given 4-6 pm Thurs. 5/14 in CHM 1407 ! Closed book, closed notes, closed neighbor ! Topics: “Everything!” • Syntax vs. semantics • Types of programming languages • Compilers vs. interpreters • Front ends vs. back ends • Ruby • Explicit vs. implicit declarations • Static vs. dynamic typing • Ruby control statements • Formal vs. actual parameters • Classes, objects in Ruby • Strings, regular expressions and matching in Ruby • Alphabets, strings and languages • Regular expressions • Deterministic and nondeterministic finite automata • Constructing NFAs from regular expressions: check, trans • Constructing DFAs from NFAs: the subset construction • Context-free grammars • Languages of CFG grammars • Derivations, parse trees • Ambiguity CMSC 330 - Spring 2011 1Final (cont.) • Top-down vs. bottom-up parsing • Recursive descent parsing: lookahead, first sets, recursive implementation • Predictive parsing • Left factoring of CFGs • Left recursion and its elimination • Parse trees vs. abstract syntax trees • Functional programming and OCaml • let / let rec / let … in … / let rec … in … • Lists in OCaml • Pattern-matching in OCaml • Tuples in OCaml • Polymorphism in OCaml • User-defined types, data types (variant records) in OCaml • Higher-order functions in OCaml: map, fold, anonymous functions • Static vs. dynamic scoping • Closures • Currying • OCaml modules and signatures • Imperative features in OCaml: ref, !, ;, L-values, R-values • Relating objects and closures • Name shadowing • Name spaces CMSC 330 - Spring 2011 2Final (cont.) • Free and bound variables • Static vs. dynamic types • Strong vs. weak types, type safety • Manifest vs. inferred types • Parameter passing: call-by-value, call-by-reference, call-by-name • Thunks • Semantics: denotational, operational, axiomatic • Operational semantics and evaluation • Defining evaluation via rules • Environments in evaluation • Function values and closures • Lambda calculus • Turing completeness • Beta reduction, substitution and alpha-conversion • Booleans and if-then-else in the lambda calculus • Church numerals and arithmetic in the lambda calculus • The Y (fixpoint) operator • Multithreading, locks, and wait / notifyAll • Small-step vs. large-step semantics • Nondeterminism, data races and deadlock • Static vs. automatic vs. programmer-allocated vs. persistent memory • Garbage collection: reference counting, mark and sweep, stop and copy, generational • History of programming languages CMSC 330 - Spring 2011
View Full Document
Unlocking...