Guidelines for Assignments

Up to 1/2 of your mark on assignments will be based on documentation and programming style, so it pays to read this section carefully. Your programs must be readable and understandable as well as correct.

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

Documentation

Preface each function with a header that gives the following information:
  1. the question number
  2. what the function does
  3. how the the function works (for complex functions)
  4. test cases

Programming Style

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)))), otherwise

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).