Topics for test on the Logic Paradigm, lambda Prolog, and Operational Semantics ($Date: 2004/11/10 21:13:43 $) This test covers homeworks 3-4, and includes the logic programming paradigm as embodied in \Prolog and operational semantics, as well as coding operational semantics in \Prolog. You might want to think about the following questions, instead of or before reading the study guide below. - What are the skills we've learned? - What terms or concepts are important? - Of these which are the most important? - What are the "big ideas"? The following are some of my answers to these questions. In listing topics, I use the following Key: ++ very important and fundamental or pretty sure to be on the test, + important but somewhat advanced or a bit less likely to be on the test, * less important but still a topic that may appear - we covered it, but not so important for the test [Homework problem] (Year: old exam problem) Skills: \Prolog Programming + give the most general unifier of two terms + give the output of a query in \Prolog (Spring 92: queries about combinators encoded in \Prolog, Spring 94: queries about multimethod signature database, Spring 97: queries about CSP little-step semantics) Fall 99: queries on movie database) * tracing a query in \Prolog on paper ++ write a \Prolog relation that works with some inductively defined datatype, such as lists [find_last, consecutive, subst_second] (Spring 92: remove duplicates, intersection of lists, Spring 97: merge of two lists, Fall 97: subseteq for lists, Fall 98: append_all elements in a list of lists) or natual numbers [modulo] (Spring 92: remainder in natural numbers) (Spring 92: free variables in Smalltalk expressions) + write a \Prolog program to model some concept [program of study] (Spring 97: complete module for binary trees, Fall 99: extend facts about movies with rule about actor-directors) ++ write a \Prolog relation that deals a set of abstract values (i.e., a recursively specified ADT) [set operations, dequeue operations] (Spring 94: equal_as_sets for sets, Spring 95: binary trees of integers and incOver5 relation) * write a higher-order \Prolog relation like mapfun or mappred (Spring 95: foldleft, Spring 95: relational algebra operators including projections, restrictions, join, compose) Operational Semantics + reading and writing operational semantics rules (in the mathematical notation) (Spring 90: write TTS for deterministic Turing machine, Spring 91: write TTS for erratic nondeterminism on expressions, Spring 94: write type checking rule for while loops, Spring 97: big-step semantics for boolean expressions) ++ write a \Prolog program that embodies some operational semantics [while language: increment location, side effects, do-until loop, add booleans and relational operators, add environments] - translate a little-step semantics to a big-step semantics, or vice versa Concepts/Terms/Ideas: Although the terms and concepts parts will focus on the logic paradigm and operational semantics, I am fond of asking "integrative" and compartiive questions that may combine these ideas. You should be able to explain and use (in problems or essays) the following (with appropriate comparisons to related concepts): Logic Programming + relational model of programs + specification vs. program * constructive proof - methodology for designing logic programming languages + the goals and purpose of logic programming (vs. the other paradigms) (Spring 92: how do concepts of logic programming apply to DBMS? Fall 98: compare \Prolog and Haskell for reducing costs of programming) * to what extent lambda Prolog fulfills those goals ++ facts, rules, queries * Horn clauses + kinds, types + declarative and procedural interpretations of clauses (Spring 95: describe differences between declaraative and procedural interpretations, with example) (Spring 95: what practical problems would happen if \Prolog obeyed the logical interpretation completely?) + logical variables, scope of logical variables in a clause (Spring 95: how pattern matching in SML differs from \Prolog) + term, ground term (Spring 92: what is a ground term, give example) - logical rules for deduction + closed world assumption ++ substitution, unifier, most general unifier (mgu) (Spring 92: what is a substitution, give example, Spring 92, Spring 94: example and importance of unifiers, Fall 98: importance of mgus) ++ instance of a term, common instance + generality of terms, alphabetic variants * meaning of a logic program * soundness, completeness - occurs check * resolution * search strategy used by Prolog - composition of substitutions ++ backtracking ++ semantics of cut (!) * problems with negation as failure + machine arithmetic (is) + lambda terms in \Prolog + higher-order predicates and terms in \Prolog - semantics of implication in \Prolog facts and queries + universal and existential quantifiers in \Prolog - higher-order abstract syntax Operational Semantics + general concept of operational semantics (Spring 97: compare operational semantics and \Prolog) + big-step, evaluation (or natural) semantics ++ little-step, computation semantics, terminal transition system (TTS) [while language problems] ++ side condition and other notation for describing rules + approaches to dealing with error conditions in semantics + configuration, terminal configuration * lambda calculus semantics, beta and eta rules, structural rules * normal form * alpha conversion, alpha equivalence class * Church-Rosser property, confluence ++ how recursion is modeled by unrolling (semantics of mu, while) ++ semantics of commands in imperative languages + use of the store in semantics + use of the environment in semantics