Introduction to
Logic Programming
What
versus
How
 

Lessons Sierra Tools Examples Zoom Piazza


Week 10

This week, we continue with presentations of term projects. The projects we have seen so far are all very good, and the presentations have been excellent. Thanks to all of the presenters for getting your main points across effectively and for doing so within the requested time limits.

Note that the deadline for submission of project files and project reports is 11:59 pm this Wednesday. Please try to keep the reports short. 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). If you would like to deploy your projects for use by others, you can give them links to this web page; or, if you like, we can post your project on the Worksheets website.

If, after completing your projects, you want to continue project work beyond the end of the quarter, please let us know, and we can arrange Stanford credit for your efforts. If you are interested in working on program sheets and program planning for Mechanical Engineering, you can get in touch with Jeff Wood (jwood11@stanford.edu). If you are interested in commercial opportunities for applications of Logic Programming in Computational Law, you can get in touch with Abhijeet Mohapatra from Symbium (abhijeet@symbium.com).

As discussed last week, if you need more time to finish your work for the course, you can avail yourself of the option to take a temporary incomplete, as discussed in the posting on New Course Requirements. We will assume that this is the case if we do not receive your project report by Wednesday night. As mentioned earlier, if you choose this option, you can complete your work and submit your report any time in the coming year, and we will clear your incomplete on the next grading cycle.

New Course Requirements

These are difficult times. We are still trying to deal with the impact of the global pandemic; and now, with the death of George Floyd, we are confronted with yet another reminder that racial injustice still exists in our society. From various communications I have received, it is clear that many of you are deeply distressed by these circumstances, in some cases to the point that you are experiencing difficulty in concentrating on class work. The CS faculty is actively discussing how to deal with this situation on a departmental level. However, with presentations and projects coming due in CS 151, we cannot wait for the outcome of those discussions. Vinay and George and I have considered the situation, and we have decided to relax the course requirements to give you some space to deal with these circumstances. (1) We hereby forego the requirement for presentations. If you wish, you may still present your project on the day you are scheduled and we will attend and give you feedback, but you are not required to make a presentation. (2) We hereby drop assignment 5, the one where you are asked to evaluate the projects of others. (That said, we would appreciate evaluations from any of you who are willing to volunteer them.) (3) At this point we are retaining the requirement that you complete your projects and submit your reports by the end of June 10. *However*, if you are unable to complete your work by then, we will give you a temporary incomplete for the course. (You can complete your work and submit your report any time in the next year, and we will clear your incomplete on the next grading cycle.) We hope that by relieving you of these immediate obligations, you will be better able to cope with the stress of the moment. If you still have problems in spite of these accommodations, please let us know, and we will work together to find other ways to make things easier for you.

Week 9

Nine weeks down. One week to go. Time for you all to share your ideas for and progress on your term projects. See Piazza post for a detailed schedule of presentations. On Tuesday, we will have presentations from Teams A - E; and on Thursday we will hear from Teams F - K. Next week, we will hear from Teams L - Q.

Given the number of teams presenting, we can afford at most 10 minutes for each presentation. The upshot is that you should aim to finish your presentation in about 7 minutes or so, leaving a few minutes for questions and answers. Given the time constraint, you need to focus on the main aspects of your project - the problem being solved, a brief explanation of why it is important or interesting, a description and/or demo of your solution, a discussion of the suitability of logic programming in producing your solution, and, where appropriate, any plans you might have for deployment to a user community.

Note that we are also asking each team to provide a brief assessment of the projects of others. As assignment 5, we would like each team to submit a report summarizing these assessments, for each other team providing a single phrase describing the project, a numerical evaluation of the project (from 1 - 5, with 1 being lowest and 5 being highest), and a sentence or two justifying the evaluation.

Week 8

On Tuesday of this week, we will continue our look at applications of Logic Programming. George will start things off with a reprise of his presentation from last year's course. The we will have Jeff Wood talking about his proposed course planning system for the Mechanical Engineering Department. Finally, we will have Abhijeet Mohapatra talking about the commercial use of Logic Programming in Complaw applications at Symbium.

On Thursday, Vinay Chaudhri will give us a glimpse of various extensions to Logic Programming, e.g. constraint systems, existential logic programs, answer set programming, and Inductive Logic Programming.

Next week, we will start with project presentations. Read the Project Presentation link on the lessons page for guidance on preparing your presentation. Note that your project does not need to be finished in order. for you to present. We expect that the early presentations will be more like proposals while the presentations on later days will be more like final reports. George will let you know which day you are scheduled to present.

Week 7

At this point in the course, we have seen all of the basics of Logic Programming - datasets, queries and updates, 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. In some ways, we have just scratched the surface.

On the other hand, we have covered enough that we can start to build 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 applications in General Game Playing and Computational Law. And, next week, we will have some guests join us to talk about their implementations and their aspirations in other application areas.

As this is the second week of this unit of the course, the associated assignments are due by the end of the week (Sunday, May 24, at midnight). You should also be finalizing your term project. After this week, there will be less than 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. You might want to read ahead to the assignments for next week to see what is expected.

If you are struggling to find or choose a project, see below for links to projects we would like people to try and links to materials associated with last year's projects.

Project
ME Course Planning
CS Course Planning
CS Program Sheets

 

Last Year's Projects
Connect Four
Evil Games
Hex
Logical Splitwise
Logiczzle
Chatbot
NBA Draft
Poker
Public Land Usage
Resx
Sudoku
Veterans Benefits

Note also that the CS department needs people to maintain the undergraduate and masters program sheets. We would very much like to see groups choose to understand and improve the existing program sheets. Added benefit: possible financial support for updating the actual sheets in the Fall.

Week 6

This week, we begin our look at operation definitions. Just as views can be thought of as names for queries, operations can be thought of as names for updates. The upshot is that, like view definitions, operation definitions can be recursive, extending the expressiveness of our update language in essential ways.

The good news is that the semantics of operation definitions is much simpler than the semantics of view definitions. This will allow us to get to interesting applications more quickly. In the second half of this week, we will look at the use of view definitions and operation definitions in building interactive "worksheets". And next week, we will see a couple of application areas that rely on view definitions and operation definitions, viz. General Game Playing and Computational Law.

Since this is the first week of this unit, the assignments on this material are not due until the Sunday after next (on May 24). That said, you might want to get started early on those assignments. Also, you should have chosen 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. If you want feedback on your term project, feel free to jot down a description of what you want to do and email it to the course staff or post as a private message on Piazza.

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.

This week, we spend all of our time looking at examples. We start our first session with some simple examples - Kinship and Blocks World, and we then progress to more interesting examples - lists and trees and sets. In our second session, we move on to more complicated examples - modeling dynamic systems, natural language processing, and metaknowledge.

Note that we have added a couple of chapters to the list of readings and we have added another assignment for the week. We have also finalized the material and schedule for the rest of the course. And we have added some details about the term project and the fifth assignment (Project Evaluations). Be sure to take a look so that you know what is coming.

As this is the second week of this unit of the course, the associated assignments are due by the end of the week (Sunday, May 10, at midnight). 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 and updates 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 take a 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 numerous 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 and updates, 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 and updates, but we have not yet finished. We have another week to go before moving on to more interesting topics.

Chapters 3 and 4 give precise definitions of the syntax and semantics of queries and updates. 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 or update 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. (This algorithm is also used in computing the positive and negative updates of update rules.) 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 and updates to get answers even more efficiently.

Your solutions to Assignments 2.1 - 2.5 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.

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 and updates. We add variables and logical operators to our language and show how to use them in writing queries and updates, and we give a formal semantics for queries and updates 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 performing updates, and we will suggest some techniques for optimizing queries and updates 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.

Finally, remember that the the second assignment set is not due until after we have finished this entire unit on queries and updates (by midnight on April 26).

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 the three assignments (1.1, 1.2, and 1.3) 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 the program sheets and program planning project for the ME department (which George will post in the next week or so).

Welcome

Welcome to CS 151. We had hoped this would be a traditional classroom-based course, as in the past. However, due to the Coronavirus situation, that is not an option; and so, this time around, we are going to run the course entirely online. As this is the first time we are teaching this course in this way, 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.

All of the course materials are online here. This includes the course textbook, background readings, the Sierra logic program development environment, and a suite of software tools for analyzing and transforming logic programs. Click the tabs at the top of the 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.

Throughout the quarter, we will be using Zoom for live presentations and discussions. Once the course starts, you will find access details here, along with a schedule of such sessions. Note that the course is currently scheduled to begin on April 7.

In addition, 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. If you have any problems or feedback for the developers, email team@piazza.com.

Even though we are doing this online, 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.


Teaching Staff

Mike Genesereth
Email: genesereth@stanford.edu
Office: Gates 220
Vinay Chaudhri
Email: vinay_chaudhri@yahoo.com
Office: Gates 222
George Younger
Email: gyounger@stanford.edu
Office: Gates 217



Comments and complaints to genesereth@stanford.edu.