Introduction to
Logic Programming
What
versus
How
 

Lessons Sierra Tools Examples Piazza


Week 9

Nine weeks down. One week to go. On Tuesday of this week, Vinay Chaudhri will talk about various extensions to the basic Logic Programming we have seen in this course. He will talk about Constraint Logic Programming, Existential Logic Programs, and Answer Set Programming, among other topics. On Thursday, we will have presentations by two former CA 151 students (Tristan Krueger and George Younger). They will reprise their final presentations for you, to give you an idea of the sorts of presentation you might want to aim for in the last week of the course,

We will devote next week to project reports. For a change, *you* will be presenting and *we* will be in the audience. George will organize the schedule. Note that we are also asking you to rate the projects of the other students. See Assignment 5. More on this next week.


Week 8

Heads up! We are changing our plans a little. And this affects you!

First of all, we are adjusting the schedule. We had originally planned to devote this coming week to a couple of interesting applications of Logic Programming, viz. General Game Playing and Computational Law. However, given feedback from some of you and low live attendance in lectures, we have decided to forgo those presentations. Instead, we will be scheduling individual meetings between the teaching staff and each of the teams in the class. Our idea is to discuss the class with each team - to figure out what is working and what is not and to discuss your term project ideas. George will post a schedule of meetings on Piazza.

Second, in order to give you more time to work on the latest assignment and to give you time to prepare for the discussions next week, we have decided to postpone the due date for the latest assignment by one week. It is now due by midnight PDT on Sunday May 23.

After this coming week, we will resume our previously announced schedule. We will take a look at extensions to Logic Programming. And then in the final week of the quarter, we will have project presentations from al of the teams in the class.


Week 7

This coming week, we will look at how Logic Programming can be used in creating interactive webpages, called worksheets. Worksheets nicely combine everything that we have seen thus far, and they make for very nice demonstrations. We recommend (though do not require) that you showcase 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). You should also be finalizing your term project proposals. 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.


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 can 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 general-purpose database systems and 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 many people. The concepts of stratification and unification are difficult for many people 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. The fun starts now.

This week, we spend all of our time looking at examples. In our first session, we concentrate on simple examples - Kinship and Blocks World and so forth. In our second session, we 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. Most 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 optional Tournament assignment.


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 dramatically 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 just how 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 Piazza 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.

Chapters 3 gives 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 chapters.

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 case, we can get by with with much less work.

This week, we look at ways to do these computations without enumerating all instances. In Chapter 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 Chapter 6, we talk about ways we can take advantage of this algorithm in optimizing queries to get answers even more efficiently.

Your solutions to Assignments 2.1 - 2.3 are due by midnight this coming Sunday. (1) Note that you will likely have trouble doing Assignment 2.3 without using some of the optimization techniques discussed in Chapter 6. (2) You may also need to enlarge Sierra's "query depth" on the Settings menu, 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.


No class this Thursday

The annual FutureLaw conference will take place on April 8, and several of us need to attend. If you like, you can drop in for any or all of the conference. Click here for details. Registration is required, but the conference is free.

FutureLaw is an annual conference on Legal Technology. It brings together researchers, engineers, entrepreneurs, lawyers, investors, and policy makers from around the world to share ideas about the cutting edge of Legal Technology. It is the best known conference of its type in the world.

The conference this year will have even more relevance to CS and AI than usual. (1) The keynote speaker will be Alan Kay, a legend in CS, winner of virtually every CS award (the Kyoto Prize, the Draper Prize, Turing Award), and a great speaker. (2) Also, this year there will be a major award closely related to Logic Programming.


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.

Judging by the discussion on the Forum, it appears that, for many of you, the toughest part of the first assignment set was figuring out how to use the meta-vocabulary of types and predicates and attributes to describe types and predicates and attributes. Most of our work will be closer to part 1 of assignment 1.3 (describing real world things, like movies), but we wanted you to do parts 2 and 3 to get you to think explicitly about those concepts.

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 some practical algorithms for computing answers, and we will suggest some techniques for optimizing queries that takes advantage of these algorithms.

A reminder that we would like you all to form teams and start working with your teammates - on both the biweekly assignments and on the term project. Also, please take advantage of Piazza. 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 textbook. 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 Piazza 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 Piazza forum is a good way to deal with these subtleties. And, even if you think you understand everything, you might consider using Piazza to help others and thus consolidate your understanding of the issues.

Note that this week's assignments are due by midnight Sunday night. 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 last year. And read the suggestions that George will post occasionally on Piazza. We are particularly interested in seeing one or more teams working on program sheets.


Welcome

Welcome to CS 151. We had hoped this would be a traditional classroom-based course, as in the past. However, due to the continuing Coronavirus situation, that is not an option; and so, once again, we are going to run the course entirely online. We ask for your patience as we proceed. If you think there is a way we could make the course more successful in this format, please feel free to make suggestions.

We will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates and instructors. Rather than emailing questions to the teaching staff, we encourage you to post your questions on Piazza. Just click the rightmost tab above to go to Piazza. (Note that you may need to sign up in order to access the course page on Piazza.) If you have any problems or feedback for the developers, email team@piazza.com.

Throughout the quarter, we will be using Zoom for live presentations and discussions. To get details, go to Piazza and look for the Zoom link in a pinned post. All sessions will be recorded, and we will place links to the recording in this pinned post as well. Class meetings will take place Tuesdays and Thursdays from 2:30 pm - 3:50 pm PDT. The first session is scheduled for March 30.

Even though this is an online course, we would like to preserve the tradition of working in teams. Ideal size 3, but teams of size 2 or 4 are okay if there are good reasons. (Piazza provides a mechanism for you to find teammates. See the first announcement there to take advantage of this.) Note that, except in extreme circumstances, all team members will receive the same grade. Grades for the course will be based on five assignments and a term project. Each of the assignments will count for 10% of your grade, and the term project will count for 50% of your grade.


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 notes, background readings, the Sierra logic program development environment, a suite of software tools for analyzing and transforming logic programs, and a Piazza course 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. If you are desperate for a printed version of the course text, click on the image below to purchase a copy from Amazon.

Note that, as you proceed through the online materials, you may occasionally encounter technical problems. 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
Email: genesereth@stanford.edu
Vinay Chaudhri
Email: vinay_chaudhri@yahoo.com
George Younger
Email: gyounger@stanford.edu



Comments and complaints to genesereth@stanford.edu.