Final: Functions, grammar, logic, Python, Prolog, Scheme, ML and concepts covered in Week 10. |
CSE 341: Programming Languages The University of Washington, Seattle, Winter 2012 |
Date: Thursday, March 15 |
Description: The exam will be of a mixed format: some multiple-choice questions (bring a Scantron form), and some written-answer questions, including coding in Python, Prolog, Scheme, and ML. |
Topics Covered:
The following topics are officially covered by the exam, but there will not be
questions on every topic.
1. Concepts Pure function domain range as set of ordered pairs Language theory Context-Free Grammar sentential form derivation leftmost derivation left recursion Parsing chart parser chart edge complete edge incomplete edge fundamental rule ambiguity Propositional Logic proposition symbol logical connective WFF truth table syllogism logical validity modus ponens resolution clause form Predicate Calculus constant, variable, function, term, arity predicate quantifier WFF free variable bound variable clause form substitution unifier most-general unifier interpretation, domain, mappings for constants, functions, predicates satisfiability, model, tautology, contradiction variable-free term Herbrand universe Herbrand base atom variable-free atom Herbrand model minimal Herbrand model 2. Python statement expression conditional statement conditional expression numbers: int, float, complex strings, string literals, quoting, multiline string syntax string operations, substrings, indexing, concatenation lists, slicing, list comprehensions tuples dictionaries functions, def, lambda classes, __init__, __call__, self, inheritance closures generators range functional composition 3. Prolog Edinburgh syntax clause, rule, fact, database, query, variable, constant list syntax Prolog-style unifiers (e.g., [X = a, Y = f(b)]). declarative semantics: minimal Herbrand model procedural semantics: Prolog's depth-first search algorithm Cut negation as failure 4. Scheme form, value procedure application lambda expression define recursive function definitions one-way recursion, two-way recursion list manipulation: cons, car, cdr, null? caar, cadr, cdar, cddr, etc. meta-circular evaluator eval apply lazy evaluation with thunks, promises, delay and force streams memoization macro, hygienic macro 5. ML value bindings basic types tuples, lists, options cartesian products function types datatypes type inference rules function definition with patterns polynomial multiplication in ML (see Ullman pp.88-91) curried form composition of functions map polymorphism 6. More Concepts Turing completeness UI completeness orthogonality of constructs |