perm filename MIDSOL.F77[206,LSP] blob sn#325498 filedate 1977-12-29 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00004 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .require "lspmac.pub[lsp,clt]" source C00003 00003 .hd206 Fall 1977 C00019 00004 C00024 ENDMK C⊗; .require "lspmac.pub[lsp,clt]" source; .LSPFONT .allop .basicops .MACRO hd206 (TERM) ⊂ .BEGIN NOFILL TURNON "←→" ←COMPUTER SCIENCE DEPARTMENT ←STANFORD UNIVERSITY .SKIP CS206 ←COMPUTING WITH SYMBOLIC EXPRESSIONS →TERM .TURNOFF .END ⊃ . .itemmac .PORTION MAINPORTION .PAGE ← 1 .hd206 Fall 1977 .skip .cb Solutions to Midterm Exam. .skip (All functions are given in both external and internal form. The basic auxiliary functions used in the definitions are presented and explained at the end.) .BEGIN INDENT 0,4 #. ⊗depth ⊗x is the length of the longest ⊗car-cdr chain reaching an atom in the S-expression ⊗x. .BEGIN NOFILL ⊗⊗ depth x ← qif qat x qthen 0 qelse max[depth qa x, depth qd x] + 1⊗ $$(DEFUN DEPTH (X) $ $$ (COND ((ATOM X) 0)$ $$ (T (PLUS (MAX (DEPTH (CAR X)) (DEPTH (CDR X))) 1))))$ .END #. Let ⊗u be a list, ⊗f a function mapping S-expressons to lists and ⊗p a predicate on S-expressions. Then ⊗⊗mapcat[u, f, p]⊗ is the list obtained by appending together the lists ⊗f[x] such that ⊗x is an element of ⊗u and ⊗p[x] is true. .BEGIN NOFILL ⊗⊗ mapcat[u, f, p] ← ⊗ ⊗⊗ qif qn u qthen qNIL⊗ ⊗⊗ qelse qif p qa u qthen [f qa u * mapcat[qd u, f, p]]⊗ ⊗⊗ qelse mapcat[qd u, f, p]⊗ $$(DEFUN MAPCAT (U F P) $ $$ (COND ((NULL U) NIL)$ $$ ((P (CAR U)) (APPEND (F (CAR U)) (MAPCAT (CDR U) F P)))$ $$ (T (MAPCAT (CDR U) F P))))$ .END #. Let ⊗g be a directed graph represented as a list of lists, with one sublist for each vertex in the graph and that sublist consists of the vertex followed by a list of vertices to which it is connected. ⊗⊗component[x, g]⊗ is a list of all vertices reachable from the vertex ⊗x by some path in the graph ⊗g. ⊗⊗bigcomponent[x, g⊗] is a list of all vertices connected to ⊗x by any combinatiion of paths in the graph ⊗g. ⊗component is computed using the auxiliary function ⊗comp which traces all loop free paths from ⊗x, keeping track of all the vertices visited. At the ⊗⊗n⊗th call to ⊗comp, ⊗u is a list of vertices reachable from ⊗x by a path of length ⊗n-1 (and in fact by no shorter path), ⊗g is the graph which is just carried along unchanged throughout the problem, and ⊗seen is a list of vertices already visited (including those in ⊗u). ⊗seen is used to avoid visiting a vertex more than once and hence getting into a loop. The recursive call to ⊗comp is made with the first argument getting the list of successors of elements of ⊗u that have not already been ⊗seen. The successors of an element ⊗z of ⊗u are just the vertices ⊗⊗qd assoc[z,_g]⊗. These are appended togther by ⊗mapapp and duplicates and vertices already ⊗seen are removed by ⊗setdiff. Note that since ⊗assoc is only applied to ⊗⊗x⊗'s that are vertices of ⊗g it will always return a nonempty list so taking ⊗cdr is safe. .BEGIN NOFILL ⊗⊗ component[x, g] ← comp[<x>, g, <x>]⊗ $$(DEFUN COMPONENT (X G) (COMP (LIST X) G (LIST X)))$ ⊗⊗ comp[u, g, seen] ← ⊗ ⊗⊗ union[u, ⊗ ⊗⊗ {setdiff[⊗ ⊗⊗ mapapp[u, $$(LAMBDA (X) (CDR (ASSOC X G)))$], seen]}⊗ ⊗⊗ [λv: qif qn v qthen qNIL⊗ ⊗⊗ qelse comp[v, g, union[v, seen]]]]⊗ $$(DEFUN COMP (U G SEEN) $ $$ (UNION U$ $$ ((LAMBDA (V) (COND ((NULL V) NIL)$ $$ (T (COMP V G (UNION V SEEN)))))$ $$ (SETDIFF (MAPAPP U$ $$ '(LAMBDA (X) (CDR (ASSOC X G))))$ $$ SEEN))))$ .END ⊗bigcomponent is just ⊗component applied to the undirected graph induced by ⊗g. The following solution is fairly compact. The second argument to the call to ⊗component produces the undirected graph corresponding to ⊗g. It does this by adding on to the list of vertices to which a given vertex ⊗x is connected, all those vertices connected to ⊗x. The latter are found using ⊗mapchoose which chooses ⊗⊗qa w⊗ for each sublist, ⊗w, of ⊗g such that ⊗⊗xεqd w⊗. .BEGIN NOFILL ⊗⊗ bigcomponent[x, g] ← ⊗ ⊗⊗ component[⊗ ⊗⊗ x, ⊗ ⊗⊗ mapcar[$$(LAMBDA $⊗ ⊗⊗ $$(X) $⊗ ⊗⊗ $$(CONS $⊗ ⊗⊗ $$(CAR X) $⊗ ⊗⊗ $$(UNION $⊗ ⊗⊗ $$(CDR X) $⊗ ⊗⊗ $$(MAPCHOOSE $⊗ ⊗⊗ $$G $⊗ ⊗⊗ $$(QUOTE (LAMBDA (W) (MEMBER (CAR X) (CDR W)))) $⊗ ⊗⊗ $$(QUOTE (LAMBDA (W) (CAR W))))))), $⊗ ⊗⊗ g]]⊗ $$(DEFUN BIGCOMPONENT (X G) $ $$ (COMPONENT$ $$ X$ $$ (MAPCAR $ $$ '(LAMBDA (X) $ $$ (CONS (CAR X)$ $$ (UNION (CDR X)$ $$ (MAPCHOOSE G$ $$ '(LAMBDA (W) $ $$ (MEMBER (CAR X)$ $$ (CDR W)))$ $$ '(LAMBDA (W) (CAR W))))))$ $$ G)))$ .END An alternate way of computing ⊗bigcomponent is given by ⊗bigc. This function is like ⊗component but the list of successors from any level is computed by taking the successors of a vertex ⊗x to be those vertices directly reachable from ⊗x in ⊗g (namely ⊗⊗qd assoc[x,_g]⊗ ) together with those vertices from which ⊗x is directly reachable in ⊗g (namely ⊗⊗invassoc[x,_g]⊗ ). ⊗comp1 is the auxiliary function that does the work. .BEGIN NOFILL ⊗⊗ bigc[x, g] ← comp1[<x>, g, <x>]⊗ $$(DEFUN BIGC (X G) (COMP1 (LIST X) G (LIST X)))$ ⊗⊗ comp1[u, g, seen] ← ⊗ ⊗⊗ union[u, ⊗ ⊗⊗ {setdiff[⊗ ⊗⊗ mapapp[u, ⊗ ⊗⊗ $$(LAMBDA $⊗ ⊗⊗ $$(X) $⊗ ⊗⊗ $$(UNION $⊗ ⊗⊗ $$(CDR (ASSOC X G)) $⊗ ⊗⊗ $$(INVASSOC X G)))$], ⊗ ⊗⊗ seen]}⊗ ⊗⊗ [λv: qif qn v qthen qNIL⊗ ⊗⊗ qelse comp1[v, g, union[v, seen]]]]⊗ $$(DEFUN COMP1 (U G SEEN) $ $$ (UNION U$ $$ ((LAMBDA (V) (COND ((NULL V) NIL)$ $$ (T (COMP1 V G (UNION V SEEN)))))$ $$ (SETDIFF (MAPAPP U$ $$ '(LAMBDA (X) (UNION (CDR (ASSOC X G))$ $$ (INVASSOC X G))))$ $$ SEEN))))$ .END #. Let ⊗successors ⊗x be the list of successors of an element ⊗x in some search space, i.e. they are the elements of the space that can be reached from ⊗x in one move. ⊗⊗bsearch[x, p]⊗ is an element of the space satisfying the predicate ⊗p and at the least depth in the search tree. Note that the behaviour of ⊗bsearch is not specified in the case that no element of the search space satisfies ⊗p. In the case of an infinite search space with no element satisfying ⊗p, ⊗bsearch will not terminate. If the search space is finite and no element satisfies ⊗p then something strange may happen when the space is exhausted (e.g. when ⊗successors returns qNIL). .BEGIN NOFILL ⊗⊗ bsearch[x, p] ← bsearch1[<x>, p]⊗ $$(DEFUN BSEARCH (X P) (BSEARCH1 (LIST X) P))$ ⊗⊗ bsearch1[u, p] ← ⊗ ⊗⊗ qif p qa u qthen qa u qelse bsearch1[qd u * successors qa u, p]⊗ $$(DEFUN BSEARCH1 (U P) $ $$ (COND ((P (CAR U)) (CAR U))$ $$ (T (BSEARCH1 (APPEND (CDR U) (SUCCESSORS (CAR U))) P))))$ .END .bb Basic auxiliary functions. ⊗mapapp and ⊗mapchoose belong to the general family of mapping functions discussed in class. ⊗mapchoose is like ⊗mapcar except it ignores those elements of ⊗u not satisfying ⊗p. .BEGIN NOFILL ⊗⊗ mapapp[u, fn] ← qif qn u qthen qNIL qelse fn qa u * mapapp[qd u, fn]⊗ $$(DEFUN MAPAPP (U FN) $ $$ (COND ((NULL U) NIL)$ $$ (T (APPEND (FN (CAR U)) (MAPAPP (CDR U) FN)))))$ ⊗⊗ mapchoose[u, pred, fn] ← ⊗ ⊗⊗ qif qn u qthen qNIL⊗ ⊗⊗ qelse qif pred qa u qthen fn qa u . mapchoose[qd u, pred, fn]⊗ ⊗⊗ qelse mapchoose[qd u, pred, fn]⊗ $$(DEFUN MAPCHOOSE (U PRED FN) $ $$ (COND ((NULL U) NIL)$ $$ ((PRED (CAR U))$ $$ (CONS (FN (CAR U)) (MAPCHOOSE (CDR U) PRED FN)))$ $$ (T (MAPCHOOSE (CDR U) PRED FN))))$ .END ⊗invassoc returns a list of elements which have ⊗x in the list associated with them in ⊗g. ⊗g is a special form of association list in which each element is associated with a list. .BEGIN NOFILL ⊗⊗ invassoc[x, g] ← ⊗ ⊗⊗ mapchoose[⊗ ⊗⊗ g, $$(LAMBDA (W) (MEMBER X (CDR W)))$, $$(LAMBDA (W) (CAR W))$]⊗ $$(DEFUN INVASSOC (X G) $ $$ (MAPCHOOSE G$ $$ '(LAMBDA (W) (MEMBER X (CDR W)))$ $$ '(LAMBDA (W) (CAR W))))$ .END ⊗union returns the list consisting of the set of elements ⊗x such that ⊗⊗xεu⊗ or ⊗⊗xεv⊗. Lists representing sets are assumed to have no duplications of elements. .BEGIN NOFILL ⊗⊗ union[u, v] ← ⊗ ⊗⊗ qif qn u qthen v⊗ ⊗⊗ qelse qif qa u ε v qthen union[qd u, v]⊗ ⊗⊗ qelse qa u . union[qd u, v]⊗ $$(DEFUN UNION (U V) $ $$ (COND ((NULL U) V)$ $$ ((MEMBER (CAR U) V) (UNION (CDR U) V))$ $$ (T (CONS (CAR U) (UNION (CDR U) V)))))$ .END ⊗setdiff returns a list consisting of the set of elements ⊗x such that ⊗⊗xεu⊗ and ⊗⊗¬xεv⊗. ⊗u and ⊗v are not necessarily repetition free. .BEGIN NOFILL ⊗⊗ setdiff[u, v] ← ⊗ ⊗⊗ qif qn u qthen qNIL⊗ ⊗⊗ qelse qif qa u ε v ∨ qa u ε qd u qthen setdiff[qd u, v]⊗ ⊗⊗ qelse qa u . setdiff[qd u, v]⊗ $$(DEFUN SETDIFF (U V) $ $$ (COND ((NULL U) NIL)$ $$ ((OR (MEMBER (CAR U) V) (MEMBER (CAR U) (CDR U)))$ $$ (SETDIFF (CDR U) V))$ $$ (T (CONS (CAR U) (SETDIFF (CDR U) V)))))$ .END .END