COMMENT ⊗   VALID 00009 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input lisp[206,tex]  % TEX file for Homework Set 7, Spring 1979
C00004 00003	\HeadA⊂Problem Set $\#$7 - Due May 29, 1979⊃
C00016 00004	\QUEST 1\ (General Matching).
C00021 00005	\QUEST 2\ (Re-Writing Code).
C00024 00006	\QUEST 3\ (Implementing Dequeues).
C00026 00007	\QUEST 4\ (Discussion).
C00027 00008	\comment
C00031 00009	\par\vfill\eject
C00032 ENDMK
C⊗;
\input lisp[206,tex]  % TEX file for Homework Set 7, Spring 1979
\def\comment#1\tnemmoc{}

% This is hw set RDG wrote, handed out 22-May, due 29-May
\HeadA⊂Problem Set $\#$7 - Due May 29, 1979⊃
\QUEST 1\ (General Matching).

\HeadC⊂Part 1⊃
We now update the \LISPI REPLACE| functions written for HW$\#6$ to use the 
a)*\underspace\underspace'' and ``?\underspace\underspace'' variables in
\LISPI new|. (I.E. for the replacement value.)
Specifically, write a \LISPI \funct REPLACE-2[ old, pat, new, $n$ ]| which
first locates  $n$ (or arbitrary if $n$ \eq \LISPI 'INFINITY|) occurrences of
(instances of) \LISPI pat|.
Here we will insist that each 
``*\underspace\underspace'' and ``?\underspace\underspace'' variable
receive a unique value, which should be such that the first possible 
instantiation site was indeed instantiated.
Thus
\LISPI ((A A B) (A 9 B) (A A B))| would have two instances corresponding
to the pattern \LISPI (A *1 B)| -- its first and third members,
in both of these \LISPI *1| is equal to \LISPI (A)|.
[Notice the \LISPI cdar| of this sexpression, \LISPI (A B)|, also does
not qualify.]
If $n$ such instances are not found, \LISPI $\$$Found-All| is set to \NIL,
and the program terminates, outputting \NIL.

These binding should be in effect when \LISPI new| replaces each instantion of
\LISPI pat|.
So
\LISPI \funct REPLACE-2[ ((A A B) (A 9 B) (A A B)),\ (A *1 B),\ (7 *1 *1),\ $2$]|
will return
\LISPI ((7 (A) A) (A 9 B) (7 (A) A))|, setting 
\LISPI $\$$Found-All| to {\T}.
Note \LISPI \funct REPLACE-2[ ((A A B) (A 9 B) (A A B)) (A *1 B) (7 *1 *1) $3$]|
would return {\NIL}.

Final consideration: These special variables should be strictly local to
\LISPI REPLACE-2|; their earlier values should  {\bf NOT} be clobbered.
Hence if we had performed \LISPI (SETQ *1 'BLAH)| before running
the above function, \LISPI *1| should be \LISPI BLAH| after its execution,
not \LISPI (A)|.

\HeadC⊂Part 2⊃
Write a function which scans an S-expression for the first sub-expression
which satisfies a certain predicate. I.e.
\LISPI \funct FIND[ sexp, P]| will locate the first form, x,
embedded in \LISPI sexp| such that \LISPI \funct P[x]| is non-{\NIL}.
[Note \LISPI P| is, of course, a unary predicate.]
As a side effect, the global variable \LISPI $\$$Found-It| should be set \T
if such \LISPI FIND| was successful, and \NIL otherwise.
For example, 
\LISPI \funct FIND[ (A (B C)), {[\λ x: $~$\at x]}]| will return
\LISPI (B C)|.

\HeadC⊂Part 3⊃
Write \LISPI FIND-1[ sexp, P$↓1$, P$↓2$, $\ldots$, P$↓M$ ]|,
for arbitrary $M$, which returns that sub-expression which satisfies 
\LISPI P$↓i$| for all $i$.
Why can this function NOT be a standard EXPRession?

\HeadC⊂Part 4⊃
Use \LISPI FIND-1| to simulate \LISPI MATCHES|:
Write a set of predicates $\{ P↓i \}$ which use the global variable,
\LISPI PATTERN|, and all return  \T only when their common argument, x,
would \LISPI MTCH?| against \LISPI PATTERN|.
\QUEST 2\ (Re-Writing Code).

\HeadC ⊂Part 1⊃
You are to write a smarter, and more general, version of the
\LISPI DeLamb| function composed for the midterm.
It should still take an expression as its single argument, and
the \LISPI CAR| of this form should be a \LISPI LAMBDA| defination.
This lambda need not be unary: it may take an arbitrary number of
parameters.
This program should:

(1) Examine the  lambda expression -- if it contains any 
\LISPI EVAL| statements,
(not within a \LISPI QUOTE|,)
it should merely return the original form.

(2) For each variable within the LAMBDA expression, examine what its new value
will be. If that value is a constant (i.e. an atom, or a list of the form
\LISPI (QUOTE $\ldots$ )|,)  
then (i) remove that variable from the lambda variable list,
and (ii) substitute that constant value for the variable name wherever it occurs
within the lambda defination, except when that value if \LISPI QUOTE|d.

(3) If the remaining lambda defination has NO variables, then
(i) if its basic form is but one expression, return that expression. Otherwise.
(ii) Return \LISPI (PROGn $\ldots$ remaining-forms $\ldots$)|.

Write this as a MACRO.

\HeadC ⊂Part 2⊃
Write a program which uses a DO-loop to simulate a MAPCAR.
That is, \LISPI \funct F-MC[ function, list ]|\footnote*[for Fake-MapCar.]
should return the same result
\LISPI \funct MapCar[ function, list ]| would have.
This should be a macro.

Warning: MAPCAR can take an arbitrary number of arguments. I.e. it can take
$n$ arguments if its first parameter is a function of $n-1$ arguments.
\QUEST 3\ (Implementing Dequeues).

\HeadC ⊂Part 1⊃
Simulate a First-In-Last-Out stack with the functions 
\LISPI Init-S|, \LISPI Push| and \LISPI Pop|.
That is, typing 
\LISPI \funct Init-S[ S ]| makes \LISPI S| an empty stack,
for which 
\LISPI \funct Pop[ S ]| should return an error.
Typing
\LISPI \funct Push[ x,S ]|, then \LISPI \funct Push[ y,S ]|
enters first \LISPI x| and then \LISPI y| onto \LISPI S|.
Now typing \LISPI Pop[ S ]| will return \LISPI y|.
\LISPI Pop[ S ]| again returns \LISPI x|, and leave the stack
\LISPI S| empty.
\Hint Why should these functions be written as FEXPRs?\tnih

\HeadC ⊂Part 2⊃
Now simulate a FIFO (First-In-First-Out) Queue, using 
\LISPI Init-Q|, \LISPI PushQ| and \LISPI PopQ|; defined in the obvious way.

\HeadC ⊂Part 3⊃
Implement a Dequeue:
The functions \LISPI PushT| should push its first argument onto the Top of a
dequeue; while 
\LISPI PushB| should push its first argument onto the Bottom.
\LISPI PopT| and \LISPI PopB| has reciprocal meanings.
(Of course I will want a \LISPI Init-D| as well.)
\QUEST 4\ (Discussion).
Describe various optimizations which a compiler might be able to perform.
How would each of these be an improvement  
--- would it generate fewer, or faster instructions; or handle special cases
in more consistent manner?$\ldots$
\Note They need not correspond to what the standard LISP compiler happens
to do already. 
Feel free to discuss any opimization,
whether or not it deals with some LISP idiosyncrasy.
\eton

\HeadC ⊂Optional⊃
Sketch how you would implement these.
\comment
\QUEST 5\ (Diagnosing [For the last time]).

We will make one more extension to the Data Base, again concerning the
requirement parts of the symptom list for the diseases.
Each symptom will be in the form \LISPI (symp-fn . (require-name . require-val) )|.
As before, \LISPI symp-fn| will be a function, which takes the name of the
patient as an argument, and returns a value $\in [0,1]$.
Again, how this value get integrated will depend on \LISPI require-name|.
When it is \LISPI Must-Be|, then the \LISPI require-val|
will be a number $\in [0,1]$.
This value is then compared with the value \LISPI \funct symp-fn[ P ]| returns;
if \LISPI require-val| is less than \LISPI \funct symp-fn[ P ]|,
then there is no chance P has this disease.
Otherwise we merely check the next symptom.

The \LISPI Must-Not-Be| case is handled reciprocally; 
P will be declared not having the disease, d, when \LISPI $(1 -\null$
\funct symp-fn[ P ]) $<$ require-val|; otherwise the next case will be checked.

For the other cases, \LISPI Should-Be| and \LISPI May-Be|,
(as well as \LISPI Should-Not-Be| and \LISPI May-Not-Be|,)
the \LISPI require-val| will be a weighting factor:
The functions defined for last assignemnt should be used, only using
the value of \LISPI \funct symp-fn[ P ] $\times$ require-val| wherever
\LISPI \funct symp-fn[ P ]| had been used before.

When \LISPI require-name \eq 'A-Function|, then 
\LISPI require-val| will be a function of three arguments,
P, the curent value of $\Phi↓{P,d}$ and \LISPI \funct symp-fn[ P ]|.
The value it returns should be $\Phi↓{P,d}$'s new value.

Rewrite the appropriate functions to accomodate the changes. Note the
\LISPI Must-Be| and \LISPI Must-Not-Be| cases, as well as any
\LISPI A-Function| function, should be able to \LISPI THROW| some value,
(which is to be the final value of $\Phi↓{P,d}$,)
and terminate the testing of this patient for this disease.
The corresponding \LISPI CATCH| should be in this \LISPI Probably-Has| function.

Then test it on the data set <C.CS206>HW7.LSP.
Print out that P has d only if the final $\Phi↓{P,d} > 0.5$; and, for these cases,
indicate this value, as well as the probability class in which this belongs
(\LISPI $\null \in \{$ DEFINITELY PROBABLY MIGHT $\}$|).
\tnemmoc
\par\vfill\eject
\end