Introduction to
Logic Programming

Lessons References Epilog Sierra Forum

Week 10

Last week of the course. Time to finish up your projects and submit your project videos and project reports. See the Project Presentation and Project Report links on the course website for information on what to submit. See the Ed post for details on submission. Most important: Keep your videos and reports short. The ideal running time for videos is 5 minutes; and the maximum length is 10 minutes. You should aim for at most 2-3 pages for your project reports.

Note that you are also required to do Assignment 5. You need to view the submitted videos and provide your evaluation. See the text of Assignment 5 for details on how to evaluate project presentations. We will post details on Ed describing how to access the videos of other teams.

The deadline for submission of your videos and project report is 11:59 pm this Tuesday, and the deadline for assignment 5 is 11:59 pm next Sunday. Once we have evaluated your submissions, we will upload your projects and reports to the Projects page on the course website (the same place as the reports from last year's class).

Week 9

Heads up! Last week of class meetings! This week, we continue our look at applications of Logic Programming with two previous students talking about their class projects and, in the case of Tristan Krueger, talking about his subsequent work at Symbium.

Reminder that we will be giving extra credit to any of your who attend this week's lectures. We want our guests to feel welcome, and having a room full of attentive students is a good way to accomplish that. Besides, listening to these presentations might help you shape your projects and presentations and get a better grade.

Although the class meetings will be done after this week, your work is not done. You still need to submit video summaries fo your projects. And you need to review the submissions of others and provide evaluations. See details in the Ed Forum.

Week 8

At this point in the course, we have seen all of the basics of Logic Programming - datasets, queries, view definitions, and operation definitions. There is plenty more to learn, e.g. constraint satisfaction, planning, Disjunctive Logic Programming, Existential Logic Programming, Answer Set Programming, Inductive Logic Programming, Theorem Proving, and so forth. Arguably, we have just scratched the surface.

On the other hand, we have covered enough that we can start building practical systems; and it is time to look at some examples. This past week, we saw how Logic Programming can be used in creating interactive webpages, called worksheets. This coming week, we look at some applications in the area of Computational Law. On Tuesday, i will give an overview of Computational Law; and, on Thursday, Preston will talk about Computable Contracts with a focus on Insurance applications.

Next week, we will have presentations from past students in CS 151. On Tuesday, John will show the project report for his game project and answer questions. Afterward, Tristan Krueger will talk about his application for scheduling vacations in national parks. On Thursday Vinay Chaudhri will join us to talk about advanced topics in Logic Programming.

You are all highly encouraged to attend these last two sessions - for your own edification and to make our guests feel welcome. To sweeten the deal, we will award two points of extra credit to everyone who attends these sessions.

In addition to attending these lectures, you should be concentrating on your term projects - refining your projects, writing the code, and preparing your presentations. In addition to writing your logic programs, we would like you to create recorded presentations; and we will make these available to everyone in the class. Note that Project Evaluation assignment calls for teams to evaluate the projects of other team. This means you will all view the videos of others. The good news is that, with everyone doing videos, we can drop the last two classes from the schedule.

Week 7

This week, we will look at how Logic Programming can be used in creating interactive webpages, called worksheets. Worksheets combine many things that we have seen thus far, and they make for very nice demonstrations. We recommend (though do not require) that you consider showcasing your term projects using worksheets.

As this is the second week of this unit of the course, the associated assignments are due by the end of the week (Sunday at midnight). I think that you will find these much easier than the assignments for the previous unit.

You should also be finalizing your plans for your term projects. After this week, there will be three weeks left in the quarter, and in that time you will need to complete your project, give a brief presentation and demonstration to the class, and submit a final report, all by the end of the last week of class.

As you choose your projects, you might bear in mind that the CS department needs people to maintain its academic program sheets. We would very much like to see one or two groups choose to understand and improve the existing program sheets. Added benefit: possible financial support for updating the actual sheets in the Fall. (If you are a CS student and you want to check out the current system, go to GIN, log in, click on Dashboard, and click on Blank Program Sheets.)

Week 6

This week, we begin our look at dynamic logic programming (DLP). As we shall see, DLP is an extension of traditional logic programing in which we define not just views of datasets but also operations that transform datasets into other datasets. The good news is that the semantics of operation definitions is much simpler than the semantics of view definitions.

Next week, we will look at the use of dynamic logic programming in creating interactive "worksheets" (which is arguably a "killer app" for DLP).

Since this is the first week of this unit, the assignments on this material are not due until the Sunday after next. That said, you might want to get started early on those assignments. Also, you will need to choose the topic for your term project by the end of next week, so that you will have plenty of time to do the work before the end of the quarter.

Week 5

Phew. Last week was not an easy week for some people. The concepts of stratification and unification are difficult to grasp when they are seen for the first time. The good news is that, with these complexities behind us, the rest of the course is relatively easy.

This coming week, we will spend all of our time looking at examples. In our first session, we will concentrate on simple examples - Kinship and Blocks World and so forth. In our second session, we will move on to more complicated examples - lists and trees and sets.

As this is the second week of this unit of the course, the associated assignments are due by the end of the week (at midnight this coming Sunday). If you have not already done so, you should get to work on the assignments. Most are easy, but not all. Many people find the zebra problem to be difficult. For those of you who are breezing through the assignments and yearning for something more challenging, we suggest you take a look at the Tournament example.

Week 4

By this point in the course, you should be adept at writing simple queries that are both correct and reasonably efficient. Ideally, in Logic Programming, your only concern should be correctness, and efficiency should be left to the interpreter and/or compiler. As it turns out, there are tools that can significantly enhance the efficiency of logic programs (in ways that cannot be done with traditional imperative programs). However, in many cases, it is still necessary for the programmer to take efficiency into account.

This coming week, we start our look at view definitions. View definitions are similar to queries, except that we can name the resulting relations, and we can use them in the definitions of other views. This capability is convenient, and it increases the expressiveness of our logic programming language. It also increases the complexity of our semantics and our execution algorithms. The upshot is that we will spend the entire week on these topics. Then, next week, we will look at examples of view definitions, and we will begin to get a sense of the power and beauty of Logic Programming.

As with our treatment of queries, this unit of the course will take two weeks, and so the assignments on this material are not due until the Sunday after next. It is okay to take a glance at the assignments, but if you get stuck you might want to wait to finish the assignments until you have read the relevant chapters and/or listened to the corresponding lectures. As always, make use of the Forum if you have any questions.

Week 3

We have now begun our look at queries, but we have not yet finished. We have another week to go before moving on to more interesting topics.

In Lesson 3, we saw precise definitions for the syntax and semantics of queries. If you want to know the answers to a query or the results of executing an update, you just need to think about the instances of the constituent rules and apply the definitions given in the lessons.

Although these definitions are simple and precise mathematically, they are not exactly satisfying from a computational point of view. The number of instances of query rules can be extremely large, even for finite Herbrand universes; and, of course, there are infinitely many instances for infinite Herbrand universes. The good news is that, in many cases, we can get by with with much less work.

This week, we look at ways to do these computations without enumerating all instances. In Lesson 5, we introduce the algorithm used by the Epilog / Sierra interpreter in answering queries. The algorithm is guaranteed to produce the same answers as our instance-based semantics but operates much more efficiently. In Lesson 6, we talk about ways we can use knowledge of this algorithm to optimize queries to get answers even more efficiently.

The assignments for this unit are due by midnight this coming Sunday. (1) Note that you will likely have trouble doing Assignment 5 without using some of the optimization techniques discussed in Lesson 6. (2) You may also need to enlarge Sierra's "Unification Limit", as this problem has quite a large search space. (3) Finally, if you are having trouble, you should consider working on a simplified version of the problem before tackling the entire problem. For example, you might start with a two column cryptarithmetic puzzle.

Week 2

By this point, you should have mastered the material in Chapters 1 and 2. From Chapter 1, you should be familiar with the basic idea of Logic Programming - logic programs as runnable specifications. From Chapter 2, you should understand the concept of datasets and some of the issues involved in creating datasets to describe application areas. In fact, you should be more than familiar with this material - ideally, you should be saying to yourself (and others) that, when all is said and done, this stuff is pretty easy. In fact, it *is* easy. But it is also very important, as we use datasets not just for practical purposes but also in defining the semantics of more complex notions to come.

Week 2 focusses on queries. We add variables and logical operators to our language and show how to use them in writing queries, and we give a formal semantics for queries written within this language. As we shall see, the semantics is simple and very precise. However, it is not very practical from a computational point of view. In Week 3, we will look at more practical algorithms for computing answers, and we will suggest some techniques for optimizing queries that take advantage of these algorithms.

A reminder that we would like you to take advantage of the Forum. If you are confused about something, you might be able to get insight from others. If you have mastered the material, you might be able to help others; and explaining things might help you to understand the material more deeply.

Week 1

Okay. We are on our way! The course begins now. On Tuesday, we will have an introductory presentation on the subject matter of the course and course logistics. On Thursday, we will have our first substantive class.

Your goal this week is to read through and understand the first two chapters of the notes. The first chapter is just an overview, and it is an easy read. That said, you should not shortchange the material. The chapter talks about the main ideas of Logic Programming and how they relate to each other. The second chapter introduces Datasets. Datasets are fundamental to the theory of Logic Programming, and they are important in practical implementation. The concept is simple, but there are some nuances; and we recommend you read the notes carefully and do the exercises.

You should also drop by the Forum to check out what others in the class are saying. There are some subtleties in Logic Programming that you can miss and that can lead to confusion. Engaging in discussion on the Forum is a good way to deal with these subtleties. And, even if you think you understand everything, you might consider using the Forum to help others and thus consolidate your understanding of the issues.

Note that this week's assignments are due next week by midnight Sunday. After this, the assignments for each unit will be due every other week. The "Project" is not due this week. But you should start thinking about what you might want to do. Look at the assignments from previous years. And read the suggestions that we will post occasionally on the Forum.

Finally, we would like you to form teams and work together throughout the quarter. Ideally three members per team, but four ok and two possible in extreme circumstances. If you have not found teammates after the first class or two, drop by the Forum and use the Teammate thread to find others in need of teammates.

Course Description

Logic Programming is a style of programming based on Symbolic Logic. In recent years, there has been increasing interest in Logic Programming due to applications in deductive databases, automated worksheets, Enterprise Management (business rules), Computational Law, and General Game Playing.

This course is an introduction to Logic Programming theory, current technology, and popular applications. Work in the course takes the form of lectures, readings, online exercises, programming assignments, and a term project.

All of the course materials are online here. There are links to lessons, additional readings, the Epilog language, the Sierra interactive development environment, some examples, and the Ed Forum. Click the tabs at the top of this page to access this content. The Lessons tab is your friend. Use it. And be sure to check this page frequently, as we will be posting periodic updates here.

Note that, as you proceed through the online materials, you may occasionally encounter minor errors or inconsistencies. Apologies in advance for this. We are still working on the course. You may get extra credit for reporting such problems (especially if your reports are not overly irate).

Teaching Staff

Mike Genesereth
Office: Gates 308
Office Hours: Wed 3:00 pm - 4:00 pm
Preston Carlson
Location: Zoom
Office Hours: Mon 3:30 pm - 5:00 pm
Office Hours: Fri 12:00 pm - 1:30 pm
John Nguyen
Location: Zoom
Office Hours: Wed 10:30 am - 12:00 pm
Office Hours: Thu 10:30 am - 12:00 pm