Prolog HW CS101a Aut08 Tim Hickey due Tue 11 18 November 10 2008 1 Overview The goal of this assignment is to give you the opportunity to learn how to use Logic Programming and Prolog in particular to solve some simple natural language and scheduling problems You will be given a program that allows users to ask questions about the current classes at Brandeis for Spr09 It translates those questions into an internal representation using DCGs and then answers the questions by querying a database consisting of all courses for next year that have been assigned a block Actually some classes science labs in particular do not fit nicely into the block system and so don t appear in this database 2 Prolog resources You should use SWI Prolog for this assignment You can download it for free from http www swi prolog org This is a professional quality Prolog implementation distributed under an open source license and should run on most Mac Linux and Windows platforms The SWI website also contains a Prolog manual http gollem science uva nl SWI Prolog Manual 3 The course knowledge base The main predicate in this prolog program is a collection of facts stored in the file current pl about the courses offered at Brandeis for the Spr09 semester Here are a few facts from the DB course 3212 cosi 2 a 1 Introduction to Computers f Hickey Timothy J course 4080 cosi 113 b 1 Machine Learning p Pollack Jordan course 4081 cosi 128 a 1 Modern Database Systems j Cherniack Mitch course 4501 econ 57 a 1 Environmental Economics b Bui Linda 1 The course predicate has 9 fields as follows course ID Dept Num Suffix Section Title Block LastName FirstName where the ID is a number uniquely identifying that course among all courses for Spr09 The Dept is a 3 or 4 letter abbreviation for the department the Num is the course number the suffix is one of the standard suffixes a b or d The Title is the official course title and LastName FirstName are the name of the instructor This database only contains classes which are scheduled for standard blocks and so doesn t contain any of the Science lab courses 3 1 Accessors and Setof The first step is to write some accessors which allow one to get the fields for a particular course quickly e g to find the suffix for a particular course num we can use the following predicate course suffix ID Suffix course ID Dept Num Suffix Sec Title Block LN FN Note that the underscores at the beginning of variable names are indicators to the Prolog compiler that you the author know that the variable Dept only appears once in the procedure and hence is not being used to pass values between the head of the procedure and the predicates in the body If you don t add the underscores the compiler will complain You can then find the set of all suffixes in the database using the following query setof S C course suffix C S L length L N L a b N 2 The setof T Q L operator generates a list L of terms which are instantiations of T obtained by solving the query Q The C prefix of the query C course suffix C S is an existential quantifier that causes the value of C to be reset after each solution of the query is found If you don t do this then it will return a different list L for each possible value of C 3 2 Problem 1 Write accessors for all of the other fields and use a setof query it to determine how many different values there are for each field 2 4 Scheduling From the description of the blocks it is easy to create a predicate which is true if two blocks conflict It starts off like this Here are all the conflicting blocks conflicts X X any course conflicts with itself conflicts k s1 conflicts l s1 conflicts s1 k conflicts s1 l conflicts k s3 conflicts l s3 conflicts k s3 conflicts l s3 and so on We can use this to write a predicate which is true if two courses do not conflict courses no conflict N1 N2 course block N1 B1 course block N2 B2 not conflicts B1 B2 This can be generalized to show that a course N1 does not conflict with any of a list L of courses course doesnot conflict N1 course doesnot conflict N1 N Ns courses no conflict N1 N course doesnot conflict N1 Ns and finally that a list of courses in non conflicting no conflicts no conflicts B Bs course doesnot conflict B Bs no conflicts Bs We will be working with lists of class ids and so it is nice to have a procedure which will printout all of the class information for those classes in a nice form Here is one way to do this writeclasses L where L is a list of class ID numbers writeclasses writeclasses A As course A Dept Num Suf Sec Title Block Last First block Block Time write Time write write course A Dept Num Suf Sec Title Block Last First nl writeclasses As 3 We can use this to help create schedules as follows If you want to take any four courses the following query will work L A B C D no conflicts L writeclasses L but if we wanted the first two classes to be COSI classes numbered 100 or more the third to be an econ and the fourth to be an english or history class we could modify the query as follows L A B C D course dept A cosi course num A N1 N1 100 course dept B cosi course num B N2 N2 100 course dept C econ member X eng hist course dept D X no conflicts L writeclasses L Even better is to store this query as a procedure which can be loaded into the interpreter and evaluated with a simple call schedule1 L L A B C D course dept A cosi course num A N1 N1 100 course dept B cosi course num B N2 N2 100 course dept C econ member X eng hist course dept D X no conflicts L writeclasses L 4 1 Problem 2 Sometimes students want to keep an entire day free The hw4code pl program has a predicate course free on day courseID day which is true if the given block does not meet on the given day Use this to create a procedure schedule2 by modifying schedule1 above to find a schedule that does not meet on Monday How many such schedules are possible use setof and length to figure this out 5 A Natural Language Front End We can now create a simple natural language front end that will let the user make English like queries to the database The top level will look like this interact write prompt read request UserRequest write UserRequest nl question Tree UserRequest write Tree nl 4 findanswers Tree Answer writeclasses Answer nl where question T U is …