perm filename PROBS2.S77[206,LSP] blob sn#280565 filedate 1977-04-28 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00002 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .require "book.pub[let,jmc]" source_file C00009 ENDMK C⊗; .require "book.pub[let,jmc]" source_file; .font B "ms25"; .font C "grfx25" .font D "grfx35" .TURN OFF "{}∂[]" .cb CS206 Computing with Symbolic Expressions Spring 1977 .cb Problem Set 2 .cb Due May 12 .skip 2 Write and debug the following LISP functions. Submit printed output containing a prettyprint of each function and examples showing the results of the functions. 1. Unification: Let %2vars%1 be a list of atoms to be called variables, all others being considered to be constants. In our examples we will take %2vars%1 = (U V W X Y Z). An %2association list%1 or %2a-list%1 for short, is a list of pairs such that the first element of each pair is associated with a second element which can be any s-expression. An example of an a-list showing a possible set of assignments for our variables could be %2w1%1 = ((X.A)(Y.(B.C))(X A B C)(W.(X.A)). Note that the same first element can appear in more than one pair; the function %2assoc%1 only sees the first occurrence. .skip 1 .nofill The function %2sublis[w,x] ← %3if at %2x %3then %1{%2assoc%1[%2x,w%1]}[%2λz.%3if n %2z %3then %2x %3else d %2z%1] %3else %2sublis%1[%2w,%3a %2x%1].%2sublis%1[%2w,%3d %2x%1] .fill gives the result of simultaneously substituting for the variables of %2w%1 the s-expressions that are paired with them. Thus %2sublis%1[%2w1%1,(X X A W Y)] = (A A A (X.A)(B.C)) and %2sublis%1[((X TIMES A B)(Y.C)),(PLUS X Y)] = (PLUS (TIMES A B) C). Sublis has an inverse of sorts called inst defined as follows; .nofill %2inst[pat,exp,w] ← %3if %2w = %1NO %3then %1NO %3elseif at %2pat %3then %2[%3if %2pat %3ε %2vars %3then %2{assoc [pat,w]}[λz.%3if n %2z %3then %2[pat.exp].w %3elseif d %2z %3equal %2exp %3then%2 w %3else %1NO] %3elseif %2pat %3eq %2exp %3then %2w %3else %1NO] %3elseif at %2exp %3then %1NO %3else %2inst[%3d %2pat, %3d %2exp, inst[%3a %2pat,%3a %2exp,w]]%1 .fill inst is an inverse of sublis in the sense that %2inst[pat,exp,w] %1≠ NO implies %2sublis[inst[pat,exp,w],pat]=exp%1. %2inst%1 and %2sublis%1 are used in programs that symbolically transform expressions according to rules like the following: (TIMES (PLUS X Y)(DIFFERENCE X Y)) → (DIFFERENCE (POWER X 2)(POWER Y 2)). A related concept is called unification. We say that %2x1%1 and %2x2%1 unify to %1x%2 if there exist %2w1%1 and %2w2%1 such that: %2x=sublis[w1,x1]=sublis[w2,x2]%1 Assuming our conventions on variables and constants, (A X) and (X B) unify to (A B), and (A X) and (B X) don't unify. If %2x1%1 and %2x2%1 have no variables in common, a single a-list %2w%1 can be used. We say that %2w%1 unifies %2x1%1 and %2x2%1 to %2x%1 if and only if %2x=sublis[w,x1]=sublis[w,x2].%1 Thus the a-list ((X.A)(Y.A)) unifies (A X) and (A Y) to (A A) and ((X.Y)) unifies them to (A Y). The latter is more general in the sense that (A A) is an instance of (A Y) and the converse statement is not true. If %2x1%1 and %2x2%1 unify at all, there are %2most general unifiers%1 which differ from one another only by a renaming of the variables. Write a LISP function for %2unify[x1,x2]%1 whose value is NO if %2x1%1 and %2x2%1 can't be unified and a most general unifier otherwise. Examples of the function follow: %2unify%1[(A X),(A Y)] = ((X.Y)) %2unify%1[(A (B X) Y), (A U (C V))] = ((U B X)(YC V)). To simplify matters, you may assume that %2x1%1 and %2x2%1 have no variables in common. 2. Write a LISP function to convert a recursive function definition to a PROG using SETQ's and GO's instead of the function calls. Design your function so that it only makes the change when it is correct to do so. 3. The compilers described in the class notes convert a LISP program to an assembly language form called LAP code. The conversion from this code to actual machine code is of less theoretical interest than the compilation process, but it is necessary to do it at some point. Write a function %2slowlap[x]%1 which takes the LAP code produced by a compiler and returns a list of the actual code. You can put the machine code values for the nmemonics on their property lists. This assembler need only cover the codes necessary for the example compilation of %2alt%1 in the class notes.