Saturday, October 27, 2012

Source Saturday: Prolog and Lists

Welcome to a new feature of Recoding!  On Source Saturdays, I'll be going through some code I've written that week and exploring design decisions that lead to the code.  This week, we look into my experimentation with Prolog.

I'm taking an Artificial Intelligence class at my college.  So far, I've learned that real life is nothing like Hollywood movies make it out to be.  One of our assignments is to create a virtual adviser that suggests what courses a CS student needs to take next semester.  You can find the full (incomplete) project here.

One of the things we need to check for is that the student has completed (or is taking) all of the prerequisites to a course.  If they haven't, we can't suggest it.  At first glance, this seems simple enough. Just slam out something like:
prereq(csc140, csc145).
hasPrereqs(Student, Class) :-
    prereq(Pre, Class),
    creditFor(Student, Class).
This solves two problems: When one class is required and when one or another class is required.  One glaring problem is that it'll return false if the class doesn't have any requirements.  That too, is simply solved with Prolog's if-then-else.
hasPrereqs(Student, Class) :-
    (prereq(Pre, Class) ->
    creditFor(Student, Class);
We've solved everything but one problem - multiple required classes.  You can see my struggle with the problem in my first StackOverflow Prolog question.  My main issue was csc201, which had the prereqs of either (csc130 AND csc140) OR (csc145).  Thus, it'd return a set that included a list and an atom.  I eventually came up with rules that allowed for all cases.  While my answer worked, it was messy.  Fortunately, mndrix was there to help and proposed an alternate solution.
prereq(csc140, []).
prereq(csc145, [csc140]).
hasPrereqs(Student, Class) :-
  prereq(Class, Pres),
  forall(member(Pre, Pres), hasClass(Student, Pre)).

Awesome.  There's one thing I'd like to focus on here. I spent a lot of time trying to figure out how to iterate over a list in Prolog.  forall/2 was suggested, but I couldn't figure out how to use it given a raw list, rather than something that results in a list.  My "aha" moment was member/2.  It "returns" all the data in a list through a variable, rather than a list.  forall/2 can then take that data and check it against hasClass/2 to determine the truthiness of the items.  This has the disadvantage of requiring me to reformat all of the prereqs as well as creating entries for classes that don't have prereqs but I think it lends the code to be more self-documenting.  Every class is accounted for.

No comments:

Post a Comment