All the assigned course work can be found in the directory
/cs/dept/course/2012-13/F/4402
Course Work:
- 3 Assignments: total of 10%
- Test 1, 25%;
date:
- Test 2, 25%;
date:
- Final project 40%, end of exams.
Project presentation and the submission of documentation: December 13.
Subject to be covered:
- 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 +. *, -.