Find CISC prerequisites

Question

Below I have some code written in prolog as a brief example. The goal of the program is to take a Computer and Information Science (CISC) course number and return any CISC prerequisites (prereqs).

I would like to know if this code followed common practices in prolog.

%CISC Courses
cisc(100).
cisc(101).
cisc(103).
cisc(106).
cisc(120).
cisc(160).
cisc(201).
cisc(211).
cisc(225).
cisc(233).
cisc(298).
cisc(300).
cisc(301).
cisc(311).
cisc(320).
cisc(330).
cisc(333).
cisc(340).
cisc(349).
cisc(365).
cisc(370).
cisc(380).
cisc(390).
cisc(397).
cisc(399).
cisc(400).
cisc(431).
cisc(432).
cisc(433).
cisc(440).
cisc(444).
cisc(460).
cisc(491).
cisc(498).
cisc(499).

Define Prereqs
prereqs(160,120).
prereqs(211,120).
prereqs(225,120).
prereqs(300,120).
prereqs(233,160).

prereqs(301,211).
prereqs(301,233).
prereqs(311,160).
prereqs(311,225).
prereqs(320,211).

prereqs(320,233).
prereqs(330,211).
prereqs(333,233).
prereqs(340,233).
prereqs(349,233).

prereqs(370,333).
prereqs(390,120).
prereqs(397,225).
prereqs(397,301).
prereqs(399,233).

prereqs(400,233).
prereqs(400,301).
prereqs(431,233).
prereqs(431,399).
prereqs(432,233).

prereqs(433,301).
prereqs(433,399).
prereqs(440,370).
prereqs(444,433).
prereqs(460,225).

prereqs(460,233).
prereqs(491,225).
prereqs(491,301).
prereqs(498,298).

%Return prereqs to a given class with prereqs of prereqs
prereq(X,Y) :- prereqs(X,Y),format("CISC ~w is a prereq of CISC ~w~n",[Y,X]).

prereq(X,Y) :- prereqs(X,Z),
    prereq(Z, Y).

Answer 1

In my opinion, your code would benefit considerably from a better naming convention.

In Prolog, a good predicate name makes clear what each argument denotes.

For example, when I see:

prereqs(460, 233).

then I have no idea what the arguments are. I see it is about prerequisites, but in which direction? Is 460 a prerequisite of 233, or is it the other way around? Also, why is this called "prereqs" although each clause only denotes a single prerequisite?

A much more descriptive name for this predicate would be (for example!):

prerequisite_of_course(460, 230).

because this makes clear what is the prerequisite of what. Another very good, descriptive name would be for example:

course_prerequisite(230, 460).

You will find that, if you use more descriptive names, then emitting output yourself will become unnecessary: The predicate name alone will make the situation perfectly clear. Let the toplevel do the printing for you!

The variable names in:

prereq(X, Y) :-
    prereqs(X, Z),
    prereq(Z, Y).

could also be improved considerably by choosing more descriptive names or abbreviations, such as Req, Course etc. For transitive relations between courses, you can for example use:

Course0 → Course1 → ... → Course

Answer 2

Since cisc/1 is unused by your current code, you should either delete the definitions or check in prereq that the given course numbers are indeed CISC courses.

I wonder how long your code takes to find the prerequisites in the following pathological case, and whether it reports any duplicates.

• There is a course graph with 20 levels.
• At each level there is an A and a B course.
• Each course on a level prerequires both the A and B courses of the previous levels.

This means that there are \$2^\text{levels}\$ possible paths in the graph. Visiting them all would take a considerable amount of time.