University of Toronto - Fall 2002 Department of Computer Science

CSC 324: Principles of Programming Languages


Project 2: Prolog

Project 2 handout.

Project 2 data file.

Prolog references and downloads

Marking Scheme
Automarking marking scheme
Fact base used for automarking.

The following lists may grow as people ask me about various aspects of Prolog you may or may not use. If you're not sure you're allowed to use something and it's not in either list, please ask me.

Allowed: ,, ;, !, ->, =, \+, not, import, anything in basics (except for), setof and related predicates, findall, member, reverse, var, nonvar, ground, <, >= and the other arithmetic operators, true.

Not allowed: functor, arg, =.., assert, retract, fail, repeat, for, sort.

Project clarifications and corrections

As usual, most questions will be answered on the newsgroup, but important clarifications, and any corrections to the specifications, will be posted here.

December 5: Important specification change: queries with specific lengths given should work, but don't try to get queries with specific durations to work. It turns out that in some cases, even integer lengths won't always be equal to themselves, even when they look like they should. The problem lies in how Prolog deals with floating point numbers, and basically the issue is that one can pretty much never guarantee that some calculation will produce the internal representation we expect. So, if your queries with the Duration specified return nothing, that's ok. For length, this is not an issue, because all lengths are integers, and integers can be reliably tested for equality. My apologies to anyone who has spent time trying to make queries work with specified durations.

December 4: On the handout, I say: "All your predicates should be generic, so that they could be used with databases describing any train system, not just the one you are working with." But then the specification of city assumes that the two train types are freight and passenger. That's my mistake, I should have had a better specification for city which didn't depend on the two train types. As a result, when you deal with the city predicate, you will have to violate the requirement that your predicates be generic. Because of this, I have to guarantee that names of the two train types will not be changed when we design the fact base for testing your code, and that no train types will be added or removed. However, their speed limits might still be changed.

December 1: In XSB, you must be careful about spacing before an opening parenthesis:
Whenever you use a predicate, e.g., pred(X,Y,Z), you are not allowed to have a space between the predicate name and the (.
Whenever you use ( ) for grouping, e.g., to override the default precedence of operators like ;, \+ and ->, you must have a space before the (.

December 1: The preconditions "Length is either uninstantiated or a number. Duration is either uninstantiated or a number." are not required for route, bdfsRoute or fastestRoute. In all cases, the query should simply yield no when those conditions are not respected.

November 30: The -> operator is a lot less clearly documented in the XSB manual than I thought, so here's a brief summary: unlike the cut, whose scope is always the predicate where it is defined, -> can be given a smaller scope by use of parentheses: in
A, (B -> C; D),
Prolog will try A again even if B succeeds, whereas in
A, (B, !, C; D),
as soon a B succeeds, A will not be tried again.

November 29: Issues with floating point numbers: because the duration values are floating point numbers, you should not expect to be able to issue a query with the duration specified and get the answer back unless the duration happens to be an integer or a select few fractions that can be represented exactly using a binary encoding of floating point numbers, such as 0.5. So the query
route(montreal,cornwall,passenger,P,L,0.5).
should produce an answer, but if the duration is something like 0.7917 or anything else that looks like it was rounded, you won't get any answer back out, and that's ok. With my system, I was able to get a duration like 2.5278 back out by querying for 2.527777, but that's really just a fluke: in general you can't expect to be able to guess what unrounded number to use, and you don't have to.

November 27: New correction in p2.data: the duplicate Chatham-London link was supposed to be Chatham-Sarnia.

November 26: For task 3, if any query gives out more than 10 answers, just show the first 10 answers. (For d, only show 5 answers.)

November 26: For task 1, you should change the city names to have only lower case letters, and replace any spaces by underscores, so that you data can follow valid Prolog syntax. Examples: toronto, north_bay.

November 22: A typo has been fixed in p2.data: Kitchener was mispelled in a couple places.