Notes and hints on Programming Project 4

Corrections, clarifications, and additions to the original assignment:

other notes

  1. For part one of this project, you will have to design your data structure. Now, in lisp, the basic structures are lists and s-expressions, but this does not mean that a list is your only option. For one thing, you could sort the list. Also, you can build complex structures out of lists. I.e., you could have small lists where each position represents a kind of data. For instance, representing a node in a binary tree could be done with a list of five positions, representing first, a special tag to make identification of this data structure easy, then the key, the data, and the left and right kids:

    (defun make-bstree-node (key data left right)
     (list '*bstree* key data left right))
    The first symbol makes your predicate easy to define: 
    (defun bstree-p (node)
     (eq (car node) '*bstree*))
    Now you can write accessor functions for each of these, as follows: 
    (defun bstree-node-key (node)
     (cadr node))
(defun bstree-node-data (node)
     (caddr node))
(defun bstree-node-left (node)
     (cadddr node))
(defun bstree-node-right (node)
     (nth 4 node)))
    You could even write destructive modifiers such as: 
    (defun set-bstree-node-left (node left-kid)
     (setf (cadddr node) left-kid))
    Which would set the left kid of node to be the new left-kid input. Alternatively, one could use the def-struct macro, which creates a record-style data structure for you, giving you constructors, accessors and a predicate for free. Consult the manual for further details on how to use defstruct.
  2. If you want to store values, between calls, one simple way is to just use a global setq, to bind this value to a variable. Another way is to use the let macro to create a local binding. This is a good way, within programs to create local variables. The syntax is as follows: 
    (let (binding-1 ... binding-n)
   lisp-expressions)
    where each binding is of the form: 
    (variable-name value)
    And value could be any lisp function returning a value, while lisp-expressions is a sequence of expressions. Within lisp-expression, any occurance of variable-name will evaluate to strong>value (unless of course variable-name is rebound by another let command). One can also embed function definitions (defun calls) within a let statement, and then the function has access to the variable, which maintains its value between function calls (though no functions outside the let statement have access to this value, except by calling one of these functions).
  3. Many people have asked about how these sets should look. Well, to avoid confusion, I've provided two handy routines to print sets for you. We will assume that sets are to be printed as follows 
    [cardinality {set elements} level]
    Though for part II, since all sets are of level 1, we could ignore the level. These functions should work as long as your predicate setp and your three accessors cardinality, elements, and level work. This printing operation does not make any assumptions about how you represent sets. You do not have to try to make your set representation efficient for printing - this is just for us to tell what sets you construct. Also, it is only printing the elements in the order that your elements function returns them, there is no need to correlate this with any internally sorted order. The sample data output will be shown in this format. These files can also be found in the dt01 course account in file print-set.lisp . 
    ;this function prints a simple set in the format:
; (makeset '(a b)) -->   [2 {A B}]
;note this will not work properly for higher-level sets.
(defun princ-s-set (set)
  (cond ((setp set)
	 (princ "[")
	 (princ (cardinality set))
	 (princ " ")
	 (princ "{")
	 (let ((elts (elements set)))
	   (and elts
		(princ (car (elements set)))
		(mapcar (function (lambda (x)  (princ " ")(princ x)))
	                (cdr (elements set)))))
	 (princ "}")
	 (princ "]")
	 )
	(t (princ set)))
  set)


;this function prints a higher level set in the format:
; (makeset '(a b)) -->   [2 {A B} 1]
(defun princ-h-set (set)
  (cond ((setp set)
	 (princ "[")
	 (princ (cardinality set))
	 (princ " ")
	 (princ "{")
	 (let ((elts (elements set)))
	   (and elts
		(princ-h-set (car (elements set)))
		(mapcar (function (lambda (x)  (princ " ")(princ-h-set x)))
		        (cdr (elements set)))))
	 (princ "}")	 
	 (princ " ")
	 (princ (level set))
	 	 (princ "]")
	 )
	(t (princ set)))
  set)
    Note that this will not allow you to type in sets in this format to lisp. You will have to use constructor functions like make-set to input sets. If you wanted to be able to just type in sets like the output function, you'd have to write a reader. You can write one that accepts the same format (and builds the valid set, calling make-set), for 5 points of extra credit, or perhaps your kindly TA might write one for you if he's feeling generous, with some spare time.
  4. Some people expressed confusion about how to compute the powerset using the recursive definition listed. First, this is not the most efficient way to produce this set, since many subsets are produced multiple times and unioned together - sort of like the way lists were generated and appended together in the strong>reverse fucntion which used append. Still, it is conceptually very simple. The main idea is to do a sort of double recursive call using a helper function. To implement the big union, you could haver a function like the following: 
    (defun Union-from (set i n)
  (cond ((> i n) (Nullset))
	(t (set-union (powerset (rem-element (nth-item i set) set))
		      (union-from set (1+ i) n)))))

(defun power-set (set)
  (set-union (make-set set)
	     (union-from set 1 (cardinality set))))
    For higher-level sets, we will have not just one universe, but one universe for each level. In general, U^0 is U, and for n>0, U^n is defined as setunion(U^(n-1),Powerset(U^(n-1))). Remember that complements of higher-order sets of level n, are to be with respect to U^(n-1).
  5. problems with (lambda ...)
    As you remember from the section on lisp, lambda is the way to make a new (unnamed) function in lisp, that you could apply to some arguments. Now one (somewhat dubious) decision that was made in common lisp is to have different "value" slots on an atom - including one for the value of a variable, and a separate one for the function value. The advantage of this is that you can use the same toekn, e.g., list as a function or a variable. The way you tell is whether it's in a function position (e.g., the first thing in a list that's not in a priviledged special form position) or value position. Sometimes you want to use the function value elsewhere. For this purpose, you have the lisp form (function name). This returns the function value for name. There's also an abbreviation, #'name, (similar to the 'name abbreviation for (quote name)) which works the same way. Well, so far, so good - the confusing bit is when we get to functions that are not stored in the function slots of names, but are generated by lambda expressions. Common lisp decided that lambda would not be a special form, but a macro. What's worse, while the only purpose of lambda is to return a function, common lisp declared that it only does this in function position. While most actual implementations will also return the function as the value of the lambda expression no matter where it gets evaluated, technically this is not required by common lisp, and the lambda expression is undefined if it appears in other positions (such as the function that mapcar uses). In particular, CMU common lisp will let you use defun to make a function named lambda, which is different from the lambda macro. This is a very bad idea, and is liable to cause lots of confusion,...