perm filename FINAL.S78[206,LSP] blob sn#361411 filedate 1978-06-15 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00009 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file C00004 00003 .hd206 Spring 1978 C00005 00004 [20 points]#. Imagine that you are writing a program to play card games. This C00011 00005 [15 points]#. The function mirror[x] computes the "mirror image" of an S-expression. C00014 00006 [15 points]#. This problem concerns iteration of functions and sequences of statements. C00017 00007 [15 points]#. The following is a sequential program to compute the predicate perf. C00019 00008 [25 points]#. Let po be a list of pairs of atoms. po defines an ordering relation C00027 00009 [25 points]#. Add a clause qif qa exp = $WHILE qthen ... to compexp in LCOM0 C00032 ENDMK C⊗; .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file; . .MACRO hd206 (TERM) ⊂ .BEGIN NOFILL TURNON "←→" .place heading ←COMPUTER SCIENCE DEPARTMENT ←STANFORD UNIVERSITY .place text CS206 ←COMPUTING WITH SYMBOLIC EXPRESSIONS →TERM .TURNOFF .END ⊃ .LSPFONT .FONT A "FIX25"; .basicops .allops .itemmac 1 .PORTION MAINPORTION .PAGE ← 1 .hd206 Spring 1978 .cb Final Exam and Solutions. .skip This examination is open book and notes. When you are asked to write LISP programs you may use external or internal form. Read each question carefully and be sure you understand what is wanted before you begin work. Do problems 1 through 4 and either 5 or 6. There is a total of 90 points possible distributed as indicated at the beginning of each problem. GOOD LUCK!! .item←0 [20 points]#. Imagine that you are writing a program to play card games. This question concerns some of the problems you might have to solve in writing such a program. .begin indent 4,4 ##. Decide on a representation of a playing card as an S-expression. Each card will have a ⊗suit [$HEART, $DIAMOND, $CLUB, or $$SPADE$] and a ⊗value [$2, ... $10, $J, $Q, $K or $$A$]. Write a predicate ⊗iscard[x] that determines if an arbitrary S-expression represents a card. Write functions ⊗suit and ⊗value that return the corresponding properties when given an S-expression satisfying ⊗iscard. The obvious representation is a pair $$(<suit>.<value>)$ although a two element list would work also. We define two global constants: .begin nofill ⊗⊗ suits ← $$(CLUB DIAMOND HEART SPADE)$⊗ ⊗⊗ values ← $$(2 3 4 5 6 7 8 9 10 J Q K A)$⊗ then ⊗⊗ iscard x ← ¬qat x ∧ memq[qa x, suits] ∧ memq[qd x, values]⊗ ⊗⊗ suitof x ← qa x⊗ ⊗⊗ value x ← qd x⊗ .end ##. Write a program ⊗makdek which takes no arguments and returns a list containing the 52 cards of a deck. (Any order will do). .begin nofill ⊗⊗ makdek[] ← ⊗ ⊗⊗ mapapp[[λs: mpacar[[λval: s . val], values]], suits]⊗ where ⊗⊗ mapapp[f, u] ← qif qn u qthen qNIL qelse apply[f, <qa u>] * mapapp[f, qd u]⊗ .end ##. Write a program which takes as input a list of cards (a hand) and returns a list consisting of the maximal runs of length ≥ 3 in the hand. A run is a list of cards satisfying ⊗isrun where ⊗next[val] is simply the next item in the list of values given above and ⊗⊗⊗isrun u ← qn u ∨ qn qd u ∨ [[suit qa u=suit qad u] ∧ [value qad u=next value qa u] ∧ [isrun qd u]]⊗. A maximal run is one that cannot be extended in either direction by the cards remaining in the hand. The initial order of cards in the hand is unimportant. The idea is to extract runs from the hand by starting with the next card left, figuring out what card extends the run downward if any using ⊗before and if it is in the hand moving it to the run being built. When this can no longer be done the run is extended upward using ⊗after to find the next card in the run. When the run is maixmally extended, it is either discarded if the length is less than 3 or added to the result. Then the process is continued until the hand is empty. .begin nofill ⊗⊗ mkruns h ← qif qn h qthen qNIL qelse lrun[qd h, <qa h>]⊗ ⊗⊗ lrun[h, run] ← ⊗ ⊗⊗ {before qa run}[λc: ⊗ ⊗⊗ qif c ε h qthen lrun[del[c, h], c . run] qelse rrun[h, run]]⊗ ⊗⊗ rrun[h, run] ← ⊗ ⊗⊗ {after lastof run}[λc: ⊗ ⊗⊗ qif c ε h qthen rrun[del[c, h], run * <c>]⊗ ⊗⊗ qelse qif length run < 3 qthen mkruns h⊗ ⊗⊗ qelse run . mkruns h]⊗ where ⊗⊗ next[x, v] ← ⊗ ⊗⊗ qif qn qd v qthen qNIL qelse qif x = qa v qthen qad v qelse next[x, qd v]⊗ ⊗⊗ before c ← suitof c . next[value c, reverse values]⊗ ⊗⊗ after c ← suitof c . next[value c, values]⊗ ⊗⊗ lastof u ← qif qn qd u qthen qa u qelse lastof qd u⊗ ⊗⊗ del[x, u] ← ⊗ ⊗⊗ qif qn u qthen qNIL qelse qif x = qa u qthen qd u qelse qa u . del[x, qd u]⊗ .end .end [15 points]#. The function ⊗mirror[x] computes the "mirror image" of an S-expression. It is defined by ⊗⊗⊗mirror[x] ← qif qat x qthen x qelse [mirror qd x] . [mirror qa x]⊗. Prove the following statements: .begin indent 4,4 ##. ⊗⊗∀x: issexp mirror x⊗ This is done by S-expression induction. In the case ⊗⊗qat x⊗, ⊗⊗mirror_x_=_x⊗ and we have ⊗issexp_x. In the case ⊗⊗¬qat x⊗ ⊗⊗mirror_x⊗ is ⊗⊗mirror_qd x_._mirror_qa x⊗. By induction both arguments to ⊗cons satisfy ⊗issexp and by the LISP axioms the result of the ⊗cons satisfies ⊗issexp. Thus the proof is complete. ##. ⊗⊗∀x: [fringe mirror x = reverse fringe x]⊗ .begin nofill turnon "∂" .n←50 Again we use S-expression induction. In the case ⊗⊗qat x⊗ we have ⊗⊗fringe mirror x = fringe x⊗ ∂(n)by definition of ⊗mirror ⊗⊗ = <x>⊗ ∂(n)by definition of ⊗fringe ⊗⊗ = reverse <x>⊗∂(n)by definition of ⊗reverse ⊗⊗ = reverse fringe x⊗ ∂(n) by substitution In the case ⊗⊗¬qat x⊗ we have: .n ← 60 ⊗⊗fringe mirror x = fringe[mirror qd x . mirror qa x]⊗ ∂(n) by definition of ⊗mirror ⊗⊗ = [fringe mirror qd x] * [fringe mirror qa x]⊗ ∂(n)by $FRINGECONS (since by the above proof and hypothesis that ⊗⊗¬qat x⊗, ⊗⊗mirror_qd x⊗ and ⊗⊗mirror_qa x⊗ are S-expressions.) ⊗⊗ = [reverse fringe qd x] * [reverse fringe qa x]⊗ ∂(n) by induction ⊗⊗ = reverse[[fringe qa x] * [fringe qd x]]⊗ ∂(n) by homework (since ⊗⊗islist fringe qa x⊗ and ⊗⊗islist fringe qd x⊗) ⊗⊗ = reverse fringe x⊗ ∂(n) by definition of ⊗fringe .end .end [15 points]#. This problem concerns iteration of functions and sequences of statements. .begin indent 4,4 ##. Write a program ⊗repeat[f,n,x] which takes as input a function ⊗f, a number ⊗n and an initial input ⊗x and returns the result of iterating ⊗f ⊗n times begining with input ⊗x. Thus the value of ⊗repeat[f,0,x] is ⊗x, the value of ⊗repeat[f,2,x] is ⊗f[f[x]], and so on. As a particular example, ⊗⊗repeat[add1,5,0]⊗ is 5. .begin nofill ⊗⊗ repeat[f, n, x] ← ⊗ ⊗⊗ qif n = 0 qthen x qelse repeat[f, sub1 n, apply[f, <x>]]⊗ .end ##. Write a program ⊗mk-for[var,lo,hi,seq] that takes as input a variable name, two integers and a sequence of statements [of the sort that can occur in a qprog] and produces the LISP code which when evaluated will have the effect of executing the sequence of statements with ⊗var=lo, ⊗var=lo+1, ... ⊗var=hi. Thus .begin nofill indent 0,0 ⊗⊗mk-for[$$J, 1, 4, ((SETQ F (TIMES F J)))$]=⊗ $$(PROG (J) (SETQ J 1) FOR (SETQ F (TIMES F J)) (SETQ J (ADD1 J)) (COND ((LESSEQ J 4) (GO FOR))))$ and ⊗⊗ mkfor[var, lo, hi, seq] ← ⊗ ⊗⊗ [<$$PROG$, <var>, <$$SETQ$, var, lo>, $$FOR$> * seq]⊗ ⊗⊗ * <<$$SETQ$, var, <$$ADD1$, var>>, ⊗ ⊗⊗ <$$COND$, <<$$LESSEQ$, var, hi>, $$(GO FOR)$>>>⊗ .end .end [15 points]#. The following is a sequential program to compute the predicate ⊗perf. Convert this into a functional program [a program containing no assignments or qgo's] that computes the same predicate. .begin nofill select 2 indent 16,16 perf[n] ← qprog[[x,y,z]; x ← n; y ← n; z ← n; per1: x ← x-1; qif x=0 qthen qreturn[z=0]; per2: qif y≥x qthen [y ← y-x; qgo per2]; qif y=0 qthen z ← z-x; y ← n; qgo per1] %1and%* ⊗⊗ perf n ← perf1[n, n, n]⊗ ⊗⊗ perf1[x, y, z] ← qif x = 1 qthen z = 0 qelse perf2[sub1 x, y, z]⊗ ⊗⊗ perf2[x, y, z] ← ⊗ ⊗⊗ qif ¬[x > y] qthen perf2[x, y - x, z]⊗ ⊗⊗ qelse qif y = 0 qthen perf1[x, n, z - x]⊗ ⊗⊗ qelse perf1[x, n, z]⊗ .end [25 points]#. Let ⊗po be a list of pairs of atoms. ⊗po defines an ordering relation on these atoms as follows: if ⊗x.y occurs in ⊗po then ⊗x precedes ⊗y [written ⊗⊗x_<_y⊗]. Let ⊗s be the list [set] of atoms occuring in ⊗po. ⊗topsort[po] is a list ⊗u such that each element of ⊗s occurs in ⊗u at most once. Further more, if ⊗⊗x_<_y⊗ in the ordering defined by ⊗po and ⊗x and ⊗y both occur in ⊗u then ⊗x must occur before ⊗y in ⊗u. Finally, ⊗u contains all of the elements of ⊗s if possible. In any case ⊗u is "sorted" with respect to the ordering defined by ⊗po. Thus if ⊗po is $$((A.D)(B.D)(C.D)(C.A))$ we have $$A_<_D$, $$B_<_D$, $$C_<_D$, and $$C_<_A$. ⊗s is then $$(A_D_B_C)$. Also, .begin nofill indent 16,16 ⊗⊗topsort[$$((A.D) (B.D) (C.D) (C.A))$] = $$(B C A D)$⊗ ⊗⊗topsort[$$((A.D) (B.D) (C.D) (C.A) (A.C))$] = $$(B)$⊗ .end One method of producing such a ⊗u is to add elements to ⊗u one at a time. At each stage choose any atom, ⊗x, occuring in ⊗po that is not already in the chosen set and which has no predecessors in ⊗po other than those already chosen. That is any pair ⊗⊗y_._x⊗ that occurs in ⊗po is such that ⊗y is already chosen. .break Write a recursive function definition for ⊗topsort. Show that your program is correct. That is, show that the list returned by your program satisfies the conditions given above. Your proof need not be formal, but it should be clear and well organized. Try to make a simple statement of the correctness in terms of some well chosen lemmas, such that the statement itself is fairly obvious. Then fill in the details (proofs of lemmas) as much as you have time to. You may want to put some effort into improving your program so that it is easier to prove correct. The desired list ⊗u is produced by ⊗ts1 applied to ⊗po and the set ⊗⊗s_=_elements_po⊗ of elements of ⊗po. ⊗ts1 looks for an element, ⊗m, of the remaining set ⊗s that has no predecessor in the remaining constraint ⊗po. If it succeeds, ⊗m becomes the next element of the result and is ⊗⊗del⊗ed from ⊗s and ⊗⊗rem⊗ed from ⊗po. The process ⊗rem removes the restriction that ⊗m preceed any remaining element, as this is now guaranteed. .begin nofill indent 12,12 ⊗⊗ topsort po ← ts1[po, elements po]⊗ ⊗⊗ ts1[po, s] ← ⊗ ⊗⊗ {findmin[po, s]}[λm: ⊗ ⊗⊗ qif m = $$NOMIN$ qthen qNIL⊗ ⊗⊗ qelse m . ts1[rem[m, po], del[m, s]]]⊗ ⊗⊗ findmin[po, s] ← ⊗ ⊗⊗ qif qn s qthen $$NOMIN$⊗ ⊗⊗ qelse qif nopred[qa s, po] qthen qa s⊗ ⊗⊗ qelse findmin[po, qd s]⊗ ⊗⊗ rem[x, po] ← ⊗ ⊗⊗ qif qn po qthen qNIL⊗ ⊗⊗ qelse qif x = qaa po qthen rem[x, qd po]⊗ ⊗⊗ qelse qa po . rem[x, qd po]⊗ ⊗⊗ nopred[x, po] ← qn po ∨ [¬[x = qda po] ∧ nopred[x, qd po]]⊗ ⊗⊗ elements po ← el1[po, qNIL]⊗ ⊗⊗ el1[po, s] ← qif qn po qthen s qelse el1[qd po, addpair[qa po, s]]⊗ ⊗⊗ addpair[pr, s] ← ⊗ ⊗⊗ qif memq[qa pr, s] qthen [qif memq[qd pr, s] qthen s qelse qd pr . s]⊗ ⊗⊗ qelse qif memq[qd pr, s] qthen qa pr . s⊗ ⊗⊗ qelse qa pr . [qd pr . s]⊗ .end It is clear that ⊗ts1 returns a list ⊗u containing each element of ⊗s at most once. Furthermore at any stage the result sofar plus the remains of ⊗s add up to the original ⊗s. Thus when ⊗ts1 stops either ⊗s has been used up and every element of ⊗s is contained in ⊗u exactly once, or every element of the remaining ⊗s has a predecessor in the remaining ⊗po (hence in the initial ⊗po). In this case in every ordering of the remaining elements some element will follow some element it is required to preceed and it is impossible to sort all of ⊗s. [eg. ⊗po does not define a partial-ordering] To show that the list ⊗u produced by ⊗⊗ts1[po,s]⊗ satisfies the ordering requirements we note that: .begin nofill ⊗⊗findmin[po,s]≠$$NOMIN$ ⊃ nopred[findmin[po,s],po]⊗ thus we can show by induction on ⊗⊗length_s⊗ that ⊗⊗sorted[ts1[po,s],po]⊗, where ⊗⊗sorted[u,po]←qn u ∨ [nopred[qa u,po] ∧ sorted[qd u,rem[qa u,po]]]⊗ .end Suppose ⊗sorted[u,po] is true and ⊗x.yεpo and ⊗y comes before ⊗x in ⊗u. Then as ⊗u contains each element at most once, by ⊗⊗cdr⊗ing through ⊗u we will arrive at a stage where ⊗sorted[u',po'] holds with ⊗⊗y_=_qa u⊗, ⊗⊗x_ε_qd u⊗, and the ⊗⊗x.y_ε_po'⊗ as ⊗x will not have been ⊗⊗rem⊗ed from ⊗po. This violates ⊗⊗nopred[qa u',po']⊗ and thus leads to a contradiction. Hence the statement that ⊗⊗sorted[ts1[po,s],po]⊗ is sufficient to prove that the ordering requirements are satisfied. [25 points]#. Add a clause ⊗⊗qif qa exp = $WHILE qthen ... ⊗ to ⊗compexp in LCOM0 [or LCOM4] to compile $WHILE expressions, and write the necessary auxiliary functions. A $WHILE expression has the form $$(WHILE <exp> DO <stmts>)$ where $<exp> can be any LISP term that LCOM0 is capable of compiling and $<stmts> is a list of while-statements each of which is of one of the following forms: $$(SETQ <var> <exp>)$, $$(RETURN <exp>)$ or $$(IF <exp> <stmt>)$ where $<var> is a variable name, and the $<stmt> in the $IF is either a $SETQ or a $RETURN statement, but not a conditional. The $WHILE expression is evaluated as follows: first evaluate the $<exp>, and if it is qNIL then the value of the whole expression is qNIL. Otherwise execute the sequence of statements in order. If a $RETURN is executed then the value of the $WHILE expression is the value of $<exp> in the $RETURN statement. If a $SETQ is executed, the value of $<var> becomes the value of the $<exp>. If and $IF is executed, the $<exp> is evaluated and if it is not qNIL then the $<stmt> is executed, otherwise it has no effect. If the end of the sequence is reached then repeat this process. You may assume that any variables occuring in the $WHILE expression are already bound and thus the relative stack position of the variable can be obtained by adding the value of ⊗⊗qd assoc[var,vpr]⊗ to ⊗m, the basic stack offset argument in ⊗compexp. Thus after adding such a clause to LCOM4 we might have [after flattening] .BEGIN NOFILL ⊗⊗compexp[$$(WHILE T DO ((IF (NULL U) (RETURN Z)) (SETQ Z (CONS (CAR U) Z)) (SETQ U (CDR U))))$,⊗ ⊗⊗ -10,⊗ ⊗⊗ $$((U.5) (Z.4))$] =⊗ .BEGIN INDENT 24,24 .SELECT 6 TAG0 (MOVEI 1 (QUOTE T)) (JUMPE 1 TAG1) (MOVE 1 5 P) (JUMPN 1 TAG2) (MOVE 1 4 P) (JRST 0 TAG1) TAG2 (HLRZ 1 @ 5 P) (MOVE 2 4 P) (CALL 2 (QUOTE CONS)) (MOVEM 1 4 P) (HRRZ 1 @ 5 P) (MOVEM 1 5 P) (JRST 0 TAG0) TAG1 .END .END .begin nofill The clause to add to ⊗compexp is: ⊗⊗ qelse qif qa exp = $$WHILE$ qthen compwhile[qad exp,qaddd exp,gensym[],gensym[],m,vpr]⊗ where .indent 12,12 ⊗⊗ compwhile[exp, seq, l1, l2, m, vpr] ← ⊗ ⊗⊗ l1⊗ ⊗⊗ . [combool[exp, m, l2, qNIL, vpr]⊗ ⊗⊗ * [compseq[seq, l2, m, vpr] * <<$$JRST$, 0, l1>, l2>]]⊗ ⊗⊗ compseq[seq, l, m, vpr] ← ⊗ ⊗⊗ qif qn seq qthen qNIL⊗ ⊗⊗ qelse comstmt[qa seq, l, m, vpr] * compseq[qd seq, l, m, vpr]⊗ ⊗⊗ compstmt[stmt, l, m, vpr] ← ⊗ ⊗⊗ qif qa stmt = $$SETQ$ qthen ⊗ ⊗⊗ [compexp[qadd stmt, m, vpr]⊗ ⊗⊗ * <<$$MOVEM$, 1, m + qd assoc[qad stmt, vpr], $$P$>>]⊗ ⊗⊗ qelse qif qa stmt = $$RETURN$ qthen ⊗ ⊗⊗ [compexp[qad stmt, m, vpr] * <<$$JRST$, 0, l>>]⊗ ⊗⊗ qelse qif qa stmt = $$IF$ qthen ⊗ ⊗⊗ {gensym[]}[λll: ⊗ ⊗⊗ combool[qad stmt, m, ll, qNIL, vpr]⊗ ⊗⊗ * [compstmt[qadd stmt, l, m, vpr] * <ll>]]⊗ .end