You'll have two weeks to do the lab, starting with the lab session on Jan. 27, and it will be due at the end of the day on Feb. 9th.
Note: the lab session of Feb. 3rd will be used for the first in-lab quiz of the term.
Obtaining and submitting the lab will be done using the same mechansim as in lab 1, though of course this time the repo name is lab2.
Instructions are given below and will be discussed in the lab session, along with further discussions of higher order functions and let-over-lambda.
Marking: the lab will be marked out of 21. Of the 21 marks: 7 marks are for the useEach function in lab2a_fun.cl and 14 marks are for the implementation of the buildTree construction function and its three specified local methods.
Lab 2 objectives
Lab 2 is meant to give you practice with higher order functions and let-over-lambda in lisp:
Each node in the binary tree has a key field, a data field, and left and right subtrees.
The dispatcher allows the user to issue commands to traverse the tree in specific orders (pre-order, in-order, post-order traversals) and apply one of a set of commands to each of the nodes in the tree (currently the commands are just to print the node's key and value or reset the node's value to nil).
The dispatcher relies on a set of local methods from buildTree:
Lab 2 requirements and restrictions
For lab 2, you are to finish implementing the functions in the provided lab2a_fun.cl and lab2b_fun.cl files and test/debug them using the provided lab2a_test.cl and lab2b_test.cl scripts. (When I mark your lab2a/b_fun.cl code I'll be using my own test script that loads the *fun.cl files and tests the functions work as specified independently.)
General/structural requirements:
Helper functions can be created in the _fun.cl files, but for the lab2b_fun.cl file be sure you carefully consider whether such functions belong as separate global functions or whether they should be methods within buildTree.
Part I: lab2a_fun.cl and lab2a_test.cl
Copies of the starting contents for the lab2a_fun and lab2a_test files are provided below, along with some suggestions for implementing useEach.
; (useEach FL AL) ; --------------- ; applies each function in list FL to the set of parameters in list AL, ; e.g. (useEach '(* + >) '(5 4)) ; builds and returns a list from the results of ; (* 5 4) (+ 5 4) (< 5 4) ; generates an error message if FL or AL are not lists ; generates an error message and skips anything in FL that ; is not a symbol bound to a function (i.e. checks both symbolp and fboundp for each) ; but it does continue processing the rest of the functions in FL (defun useEach (L arglist) nil) |
Implementation suggestions:
The test script and a sample working run:
#! /usr/bin/sbcl --script (format t "~%--- Begin loading lab2a_fun.cl ---~%") (load "lab2a_fun.cl") (format t "~%--- completed loading of lab2a_fun.cl ---~%") ; ------------ testing of useEach -------------------- (format t "~%---------- Testing useEach ----------~%") (defun prt1 (x) (format nil "~A" x)) (defun prt2 (x y) (format nil "~A,~A" x y)) (defvar A1 '(1.21)) (defvar L1 (list 'sqrt 3 'prt1)) (defvar A2 '(5 (10 15))) (defvar L2 (list 'prt2 'cons 'foo)) (defvar A3 '(2 6)) (defvar L3 (list '< '* '+)) (defvar A4 '(2.3 1.6)) (defvar L4 '(> / -)) (defun testUE (L A) (format t "~%Testing useEach on funlist ~A applied to args ~A~%" L A) (format t "Final results list was ~A~%" (useEach L A))) (testUE L1 A1) (testUE L2 A2) (testUE L3 A3) (testUE L4 A4) (testUE nil A1) (testUE 5 A2) (format t "~%---------- Testing finished ----------~%~%") |
Part II: lab2b_fun.cl and lab2b_test.cl
buildTree works on a binary tree of key-value pairs represented using a list structure, where nil represents an empty tree and otherwise a tree is composed of four elements: the key and data values for the root of the tree (or subtree) then the list representing the left subtree, then the list representing the right subtree.
Thus a tree consisting of just the single key-value pair 3,17 would look likeNote the format is not terribly readable for humans, but works out well for recursive processing.
buildTree expects to be passed the tree and the data types for its keys and values, e.g.
(buildtree (3 17 (1 200 nil nil) (99 1000 nil nil)) 'integer 'integer)
Using the let-over-lambda approach discussed in lectures, it returns a dispatch function that allows us to issue commands and options to process the tree where the commands are 'print or 'reset and the options are 'inorder, 'preorder, or 'postorder:
(defvar tr1 (buildtree (3 17 (1 200 nil nil) (99 1000 nil nil)) 'integer 'integer)) (funcall tr 'print 'postorder) (funcall tr 'reset 'inorder)
Copies of the starting contents for the lab2b_fun and lab2b_test files are provided below, along with implementation suggestions for the methods of buildTree.
; (printNode n)
; print the given node's key/value: assumes n is structurally valid
; (i.e trusts n is either nil or a list whose front two elements are a key and value)
(defun printNode (n)
(when (not (null n))
(format t "(~A:~A)" (car n) (cadr n))))
; (resetNode n)
; resets the node's value field to nil: assumes n is structurally valid
; (i.e trusts n is either nil or a list whose front two elements are a key and value)
(defun resetNode (n)
(when (not (null n))
(setf (cadr n) nil)))
; (buildtree inittree k v)
; ------------------------
; builds and returns a dispatcher to handle commands to apply to a binary tree
; whose content is provided in inittree
; (optional arg: nil if not provided)
; and whose key and value data types are k and v respectively
; (also optional args: 'integer if not provided)
; the supported dispatcher commands are provided in the lambda section,
; and the supported internal methods are described in the labels section
(defun buildtree (&optional (inittree nil) (k 'integer) (v 'integer))
(let ((root inittree) ; root of tree
(keytype (if (symbolp k) k 'integer)) ; expected data type for node keys
(valtype (if (symbolp v) v 'integer))) ; expected data type for node values
(labels ( ; local methods
; (setTypes k v)
; set the expected key and value types for tree node contents
; no restrictons on k/v other than being symbols,
; e.g. (setTypes 'integer 'real)
(setTypes (k v)
nil)
; (checkNode n quiet)
; check if node n has valid structure and key/value types:
; - a list of 4 fields of appropriate types:
; 1st of type keytype, 2nd of type valtype, 3rd and 4th are lists
; - is *not* expected to recursively check third and fourth fields,
; just check that they are lists
; prints error message and returns nil if error detected,
; otherwise returns t
(checkNode (n)
nil)
; (traverse n order action)
; traverse subtree n using the indicated order (preorder, inorder, postorder)
; and on each subtree applies the indicated action (printNode or resetNode)
(traverse (n order action)
nil)
) ; end of local methods
(lambda (cmd &optional (arg1 nil) (arg2 nil))
(cond
; command was: setTypes keytype valtype
((equalp cmd 'setTypes) (setTypes arg1 arg2))
; command was: reset traversal-order value
((equalp cmd 'reset) (traverse root arg1 'resetNode))
; command was: print traversal-order
((equalp cmd 'print) (traverse root arg1 'printNode))
(t (format t "Error: invalid command ~A~%" cmd)))))))
|
Implementation suggestions:
if it's pre-oder then funcall the action on n here
call recursively on the left subtree (caddr n)
if it's in-order then funcall the action on n here
call recursively on the right subtree (cadddr n)
if it's post-order then funcall the action on n here
The test script and a sample working run:
#! /usr/bin/sbcl --script
(format t "~%--- Begin loading lab2b_fun.cl ---~%")
(load "lab2b_fun.cl")
(format t "~%--- completed loading of lab2b_fun.cl ---~%")
; ---------- testing of myfun function ---------------------------------
(defun testTree (tree ktype vtype)
(let ((dispatch nil))
(format t "Building dispatcher~%")
(format t "enter anything to continue~%")(read-line)
(setf dispatch (buildTree tree))
(when (null dispatch)
(format t "Null dispatcher created~%"))
(unless (null dispatch)
(format t "~%setting key/value expected types (~A,~A)~%" ktype vtype)
(funcall dispatch 'setTypes ktype vtype)
(format t "~%running pre-order print~%")
(funcall dispatch 'print 'preorder)
(format t "~%~%running in-order print~%")
(funcall dispatch 'print 'inorder)
(format t "~%~%running post-order print~%")
(funcall dispatch 'print 'postorder)
(format t "~%~%reset default value to nil~%")
(funcall dispatch 'reset 'preorder)
(format t "~%running in-order print~%")
(funcall dispatch 'print 'inorder)
(format t "~%~%"))))
; ---------- testing of myfun function ---------------------------------
(format t "~%--- run tests on bstree of int/int ---~%")
(testTree '(4 1 (2 2 (1 3 nil nil) (3 4 nil nil)) (6 5 (5 6 nil nil) (7 7 nil nil))) 'integer 'integer)
(format t "~%--- run tests on tree with types real,real but one invalid key ---~%")
(testTree '(10.1 1 (5.5 2 (0.1 3 nil nil) (6.7 4 nil nil)) ("ick" 5 (50.5 6 nil nil) (700 7 nil nil))) 'real 'real)
(format t "~%--- run tests on tree with types real,integer but one invalid value ---~%")
(testTree '(10.1 1 (5.5 2 (0.1 3 nil nil) (6.7 4 nil nil)) (50 5 (50.5 6 nil nil) (700 7.7777 nil nil))) 'real 'integer)
(format t "~%--- run tests on non-list with types real,real ---~%")
(testTree 10 'real 'real)
(format t "~%---END OF TESTING---~%~%")
|