All the assigned course work can be found in the directory
/cs/dept/course/2010-11/F/4402
Course Work:
- Assignment 1, 10%;
deadline: October 19
- Assignment 2, 10%;
deadline: November 25
- Assignment 3, 10%;
deadline: December 9
- Midterm 30%;
date: November 4
- Final project 40%, end of exams.
Subject covered so far:
- general discussion on imperative and declarative programming language
paradigms; logic programming family of languages;
- logical preliminaries: general notion of a logical system, classical
propositional (CPL) and predicate (PL) logics; consistency;
- clausal fragment of CPL; Horn clause classification;
- the resolution rule for CPL, its soundness and completeness;
- resolution-based deductive process, Robinson's results on resolution;
- clausal fragment of PL; Horn clause classification; logic programs;
- the unification theory and algorithm
- the resolution rule for PL, the resolution-based deductive process,
extending Robinson's results on resolution to PL;
- selection functions and SLD deductions for programs and goals; independence of
selection functions;
- answer substitutions, correct answer substitutions, and computed
answer substitutions;
- SLD search trees;
- the relationship between computed and correct answer substitutions
- the definition of Standard Prolog and its Turing-completeness;
- extending Standard Prolog with negation-like operations;
- negation as failure, SLDNF deductions;
- constraint logic programming (CLP): domains, constraint solvers, constraint
clauses and programs;
- constarint resolution and deductive process;
- CLP metainterpreter;
- review of CLP systems.
Project
The first part of the project is a parser for Horn language.
Your parser should be able to:
1. do syntax verification of clauses
2. represent clauses using preselected data structures.
Notes for part 1:
1. when selecting data structures for terms and clauses please keep in
mind the unification algorithm and the algorithm for computing resolvents;
2. if you want to adopt the "standard" list notation used by most Standard PROLOG
systems (i.e., the "[...]" notation), then your parser should be able to
represent such lists as terms (cf. the discussion in Lloyd's book on page 9
where lists are represented in terms of the two argument function ".").
Documentation for part 1:
1. provide details on the data structures for terms and clauses as well as
on syntax error handling;
2. give examples and provide test results.
This part of the project has to be submitted by the end of October.
Minimal list of predefined predicates and functions to be implemented:
- predicates: consult, halt, is, unify
- functions: list formation, arithmetic operations +. *, -.
Note: a student cannot receive a passing final grade
without receiving at least 14% on midterm.