perm filename PROBS1.F77[206,LSP]3 blob sn#325494
filedate 1977-12-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00002 00002 .REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file
C00003 00003 .hd206 FALL 1977
.REQUIRE "LSPMAC.PUB[LSP,CLT]" source_file;
.PAGE FRAME 56 HIGH 80 WIDE;
.evenleftborder ← oddleftborder ← 1000;
.area text lines 1 to 56;
.MACRO hd206 (TERM) ⊂
.BEGIN NOFILL TURNON "←→"
←COMPUTER SCIENCE DEPARTMENT
CS206 ←COMPUTING WITH SYMBOLIC EXPRESSIONS →TERM
.MACRO hw (NUMBER, DUEDATE) ⊂
. BEGIN TURNON "←" NOFILL
←PROBLEM SET NUMBER
. TURNOFF END ⊃
.hd206 FALL 1977
.hw 1, |October 11|
.bb General homework policy.
When the homework involves writing LISP functions, debug your functions
using LISP at LOTS. Prepare a file that contains for each function the
1) The external form of your function.
2) A ⊗brief description of how it works and why.
3) An internal form listing.
4) Results from some representative sample runs.
List this file and turn it in. Include also the name of the file where
the functions live. (For grading purposes, in case something is not clear,
it is useful to try out a function on suitable test cases.)
Solutions will be put up in a file on the <CS206> directory and
you will be able to list, read, or load and try them. Late assignments
are discouraged and will not be accepted after the solutions appear.
.item ← 0
.BEGIN INDENT 0,6
Write the following LISP functions.
#. ⊗⊗foo u⊗ is a list consisting of the atomic elements of the list ⊗u
followed by a list of the nonatomic elements of ⊗u preserving the order within
each group. Thus
⊗⊗⊗foo[$$(A (B C) A B (D E))$] = $$(A A B (B C) (D E))$⊗
#. ⊗⊗prod[u, v]⊗ is the product of the polynomials ⊗u and ⊗v. We consider
only polynomials in one variable, say ⊗x, and represent a polynomial as a list
of its coefficients in order of increasing powers of ⊗x. Thus
⊗⊗x%53%*+x+5⊗ is represented by $$(5 1 0 1)$.
#. ⊗⊗locations[e, u]⊗ is a list of the locations where ⊗e occurs as a subexpression
of ⊗u. A location is a list ⊗⊗l⊗=(β%41%*_..._β%4n%*) where each β%4i%* is $A or
$$(Cβ%41%*R_..._(Cβ%4n%*R_⊗⊗u⊗)...)$ is the subexpression at location ⊗l in ⊗u.
⊗⊗⊗locations[$Y, $$(((X . Y) . Z) . X)$] = $$((D A A))$⊗
#. ⊗⊗commons x⊗ is a list of pairs. The set of ⊗⊗car⊗'s of the pairs is the set of
subexpressions of the S-expression ⊗x that occur more than once in ⊗x and the
⊗cdr of each pair
is a list of the locations where the ⊗car occurs. Thus
⊗⊗⊗commons $$(((X . Y) . Z) . X)$ = $$((X . ((A A A) (D))))$⊗