Midterm: Functions, grammar, logic, Python, Prolog, and a little Scheme CSE 341: Programming Languages The University of Washington, Seattle, Winter 2012 Date: Friday, February 17 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, and Scheme. 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 ```