Guidelines for Assignments

If your assignment has basically no documentation, no comments on the code, we will refuse to mark it. As a result, you will receive 0 marks for it. Poor documentation and programming style, even if your programs work correctly, can result in deduction of 50% of the total marks for the assignment. For example, if an assignment is worth 10 marks, you can lose 5 marks for poor documentation and programming style. So it pays to read this section carefully. Your programs must be readable and understandable as well as correct.

First, in any submitted assignment, at the top of the first page you should write your name, student number, the course and section number, and the assignment number.

Documentation

Note: for Prolog, replace "function" with "predicate" in what follows.

Preface each function with a header that gives the following information:

the question number
what the function does
how the the function works (for complex functions)
test cases

Programming Style

Put the most important function first. Do not begin your program with a bunch of utilities.
Indent your programs for clarity; use a consistent style.
Build complex functions from simple ones.
Avoid complex paths of control; do not nest conditionals more than 2 deep.
Use meaningful function and variable names.
When using data structures write appropriate access functions, such as:

     (defun left-subtree (tree)
         (first (rest tree))
     )

Sample Lisp Program

#| Question 2.

description: zip : list, list -> list
zip takes two lists and returns a single list where the elements of the two input lists alternate.

algorithm:
zip(x, y) = nil, if x = nil or y = nil
= cons(first(x), cons(first(y), zip(rest(x), rest(y))))

Note: You don't have to write such an algorithm all the time, especially for simple functions. Different styles could be used in explaining an algorithm. What's important is whether someone reading your program (in this case, your TA) can understand how it works. For example, you may lose marks if a simple function is programmed in some complex way that is hard to understand. It gets worst if there is no clear explanation of how your program works. If you are not sure what exactly you should do otherwise, then just follow the style here.

test cases:
(zip '(a c e) '(b d f)) => (a b c d e f)
(zip '(a c e) '(b d)) => (a b c d)

|#

(defun zip (list1 list2)
    (cond
        ((null list1) nil)
        ((null list2) nil)
        (t (cons (first list1)
            (cons (first list2)
                (zip (rest list1) (rest list2)))))
    )
)

Sample Prolog Program

See http://www.sics.se/ps/sicstus/sicstus_3.html#SEC5 for a description of the argument modes: +, -, ?

/* ---------------------------------------------------------
Question 4

   sublist(?SubList, +List)

   Given a List, SubList is a list that results from removing
   some elements from the beginning of the List and from the
   end of the List.

   test cases:
   sublist(SubList, [1, 2, 3]) => Sublist = [[], [1], [2], [3],
      [1, 2], [2, 3], [1, 2, 3]]
   sublist([a, b], [b, c, a]) => no
   --------------------------------------------------------- */

sublist(SubList, List) :-
   conc(_FrontList, SubList, MidList), % _FrontList are the elements deleted
                                        % from the front of the List
    conc(MidList, _BackList, List).

/* ---------------------------------------------------------
   conc(+List1, +List2, -ConcList)

   Given two lists, List1 and List2, ConcList is a list that
   results from concatenating the two lists.

   test cases:
   conc([a, b], [1, 2, 3], ConcList) => ConcList = [[a, b, c, 1, 2, 3]]
   conc([], [], ConcList) => ConcList = [[]]
   --------------------------------------------------------- */

conc([], List2, List2).

conc([First | RestList1], List2, [First | RestConcList]) :-
conc(RestList1, List2, RestConcList).