ID2213 Logic Programming 7.5 credits

Logikprogrammering

In this course the student develops knowledge and skills in constructing and understanding the meaning of programs in the paradigm of logic programming. Logic programming is programming with a special class of logical expressions. In systems that execute logic programs the user poses questions to a database of statements (the program) and the system answers these questio

Show course information based on the chosen semester and course offering:

Offering and execution

No offering selected

Select the semester and course offering above to get information from the correct course syllabus and course offering.

Course information

Content and learning outcomes

Course contents *

The course presents logic and logic programming for software development. This includes an overview of Horn clauses and their application in knowledge representation and reasoning as well as logic programming in Prolog and its semantics. The course presents algorithms over lists and trees as well as search algorithms in graphs, database programming, recursive programming, non-deterministic programming. Tools for arithmetic in Prolog, structure inspection, metalogic, control mechanisms for search, negation in Prolog, incomplete data structures, parsing by means of DCG. Various more efficient data structures, such as difference structures, are introduced. We show how technologies from functional programming fit in the framework of the logic programming and can be expressed in the programming language Prolog. Finally, the course presents some AI applications, such as simple expert systems, and gives a short overview of current methodological trends.

In this course students will meet the theory and the basic design principles within logic programming while they in for example degree projects, can practise the methods.

Application: puzzles and games, parsing, compilation, formula manipulations, expert systems. Introduction to modifications and extensions of Prolog: parallel Prolog, equation and constraint solving, richer forms of clauses, modules, object orientation and Prolog.

In the project part of the course

  • the student identifies and defines a problem-oriented project suited to illustrate the use of logic programming techniques
  • the student formulates the project by means of the terminology of logic programming (implementation of a program or analysis of a program/system)
  • the student carries out the project in a group or individually within the time frame
  • the student presents her/his work with a short report and an oral presentation in a "mini workshop".

Intended learning outcomes *

Having passed the course, the student should be able to:

  • explain the basic concepts in logic programming
  1. program syntax for Logic Programming
  2. the equality theory for terms and the unification procedure
  3. the search mechanisms in Prolog
  • implement algorithms over trees and lists as logic programs
  • explain and use the logical and the most common non-logical control structures in Prolog
  • be able to account sketchily for whether and why a certain assignment is suited (or not suited) to be implemented using logic programming techniques
  • carry out and present a smaller logic programming project in a group or individually in stated time frames.

For higher grades, the student should also be able to

  • use DCG notation for grammars in Prolog
  • explain the operational and declarative semantics for logic programs
  • design adequate representations of abstract data types such as sets sparse matrices, hash tables in logic programs
  • use and explain difference structures (e g d-lists)
  • use metaprogramming techniques in logic programming languages.

Course Disposition

No information inserted

Literature and preparations

Specific prerequisites *

  • Completed course ID1018 Programming I or DD1393 Software Engineering, or the equivalent.
  • Completed course ID1020 or DD1338 Algorithms and Data Structures, or the equivalent.
  • Completed course SF1624 or IX1303 Algebra and Geometry, or the equivalent.
  • Completed course SF1610 or IX1500 Discrete Mathematics, or the equivalent.

Recommended prerequisites

Programming in high level languages. Some experience of recursion as a programming technique.

Knowledge and skills in elementary logic (the language of logic, deductions, models).

Equipment

No information inserted

Literature

Sterling and Shapiro, The Art of Prolog, 2nd ed. MIT Press 1994, or other appropriate text.

Examination and completion

Grading scale *

A, B, C, D, E, FX, F

Examination *

  • PRO1 - Project, 3.0 credits, Grading scale: P, F
  • TEN1 - Examination, 4.5 credits, Grading scale: A, B, C, D, E, FX, F

Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.

The examiner may apply another examination format when re-examining individual students.

Examination takes place with written or oral examination, oral project presentation as well as assessment of the presentations of fellow students, written project report as well as program code for the project.

In agreement with KTH´s coordinator for disabilities, it is the examiner who decides to adapt an examination for students in possess of a valid medical certificate.. The examiner may permit other examination forms at the re-examination of few students

Opportunity to complete the requirements via supplementary examination

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

Alf Thomas Sjöland

Further information

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Course web ID2213

Offered by

EECS/Computer Science

Main field of study *

Computer Science and Engineering

Education cycle *

Second cycle

Add-on studies

Master thesis using logic programming.

Contact

Thomas Sjöland

Ethical approach *

  • All members of a group are responsible for the group's work.
  • In any assessment, every student shall honestly disclose any help received and sources used.
  • In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.

Supplementary information

In this course, the EECS code of honor applies, see: http://www.kth.se/en/eecs/utbildning/hederskodex.

The content overlaps with new basic course ID1213. This course on the advanced level contains a larger project.