CLIP

Computational Logic Course Material and Tools

Logic Programming, Prolog, Constraint Logic Programming, Resolution, Verification, ...


This site provides some course material and tools for teaching Logic Programming, Prolog, CLP, and Computational Logic in general, covering both theory and practice. Different parts of this material come from undergraduate and graduate courses taught by us at different institutions, including the Technical University of Madrid (UPM -- CS / AI Dept.), the IMDEA Software Institute, UT Austin (CS Dept.), and the University of New Mexico (CS and ECE Depts).

for part of the rationale behind some of this course material.

These courses have been developed and are taught by members of the CLIP group and other contributors. There is much more information available on the CLIP (Computational Logic, Languages, Implementation, and Parallelism) research group and our Computational Logic Software pages. Please note that these pages are all under permanent construction/change. Suggestions, comments, questions, raves, rants, etc., should be directed by email to <clip@cliplab.org>. You are welcome to use all or part of this course material, we only ask you to please quote the origin. We would also very much appreciate if you let us know that you are using it and also that you send us by email to the address above any error corrections or improvements you may make to this material. Thanks in advance.

Teaching tools

Slides and Examples: The Basic Sequence

Motivational Introduction:

Pure Logic Programming / Pure Prolog

  • A "hands-on" Introduction to Pure Logic Programming (Pure Prolog).
    Topics covered:
    • Syntax: terms (variables, constants, structures), facts and rules (clauses), predicates, programs, and queries
    • Declarative meaning of facts, rules, predicates, and queries
    • Running programs in a Prolog system
    • Top-down operational meaning of programs
    • Unification: definition, algorithm, examples, and its role in execution
    • SLD-resolution: a schematic interpreter and the choices made in standard Prolog
    • Comparison with imperative and functional languages
    • Search: the search tree, depth-first (backtracking) and breadth-first search, control of search
    • Modes: running programs in different directions
    • Database programming, structured data, and data abstraction; terms as data structures with pointers
    • Logic programs and the relational database model; deductive databases, Datalog, and ASP
    • Recursive programming and types (including recursive types and defining "not equal")
    • Arithmetic with Peano numbers; functional syntax, packages, and directives
    • Lists: membership, length, sum, concatenation, and reversal
    • Binary trees, polymorphism, and manipulating symbolic expressions
    • Graphs, automata, and the Towers of Hanoi
    • Learning to compose recursive programs
  • Developing Programs with a Prolog System.
    [slides] [accessible html]

Additional Features of Prolog and the ISO Standard

  • Additional Features of Prolog and the ISO Standard.
    Topics covered:
    • The ISO Prolog standard; advantages and drawbacks of classical systems
    • Programming interface: top level, interpreters, compilers, debuggers, modules
    • Syntax and terminology; defining operators
    • The execution mechanism of classical Prolog
    • Built-in arithmetic and arithmetic programs
    • Dynamic checking of basic types
    • Structure inspection (functor/3, arg/3, =../2): arrays, subterms; strings and atoms
    • Meta-logical predicates: choosing implementations by calling mode; comparing non-ground terms
    • Input/output
    • The cut: white, green, and red cuts
    • Meta-calls and higher order: call/N, maplist, anonymous predicates
    • Aggregation predicates: findall/3, bagof/3, setof/3
    • Negation as failure and cut-fail
    • Dynamic program modification: assert, retract, lemmas
    • Meta-interpreters
    • Incomplete data structures: difference lists; quick-sort with and without append
    • Parsing: with lists, difference lists, and strings; Definite Clause Grammars (DCGs)
    • Other issues, typical libraries, and extensions in Ciao
  • 99 Programs in Prolog.
    [interactive ALD version] [source code in markdown]

Efficiency Issues in Prolog

Constraint Logic Programming

Additional Topics

Additional CLP topics

  • Additional slides on How To Solve Finite Domain Constraints. [slides]
  • A longer, 5-day seminar on CLP. [html]
  • Concurrent (Constraint) Logic Programming. [slides]

LP and CLP Theory

  • Automated Deduction Fundamentals. [slides]
  • First Order Logic and Logic Programming Theory. [slides]
  • Same, but just the model and fixpoint semantics. [slides]
  • CLP: operational, model, and fixpoint semantics. [slides]

Some Ciao Prolog tutorials

Some older Ciao Prolog tutorials

Other topics

  • Global Analysis by Abstract Interpretation. [slides]
  • Abstract Specialization and its Applications. [slides]
  • Parallel Execution of Logic Programs. [slides]
  • Intro to Prolog Implementation:
    WAM tutorial, by Hassan Ait-Kaci. [slides] [auth version] [older book website]
    Manuel Hermenegildo's original 1989 tutorial. [slides pdf]
  • Distributed/Internet programming using LP/CLP systems. [slides]
  • WWW programming using LP/CLP systems. [slides] [Code for examples]
  • A very brief intro to Operational and Axiomatic Semantics [slides]

General Note: We used to start with basic theory (resolution, etc..), then Logic Programming, then Prolog, CLP(*), and Concurrent LP. Eventually, we decided to start directly with a quick introduction to Logic Programming and Prolog programming, presenting only afterwards theory, CLP, and Concurrent (C)LP. If you prefer to start with theory, just use the lp_theory slides first and skip some slides (first order languages and unification, mainly) from logic_programming.tex.

(One of the reasons for doing things this way is that our students take a semester of formal logic prior to this course and are therefore quite familiar with, e.g., resolution, but not with logic programming. We feel it is best for student motivation to get as quickly as possible to the practical use of the programming tools.)

------------