perm filename HOMEW6.S79[206,LSP] blob sn#449541 filedate 1979-06-13 generic text, type C, neo UTF8
C00001 00001
C00002 00002	\input lisp[206,tex]  % TEX file for Homework Set 6, Spring 1979
C00004 00003	\HeadA⊂Problem Set $\#$6 - Due May 22, 1979⊃
C00016 00004	\QUEST 2\ (Pattern Matching).
C00021 00005	\QUEST 3\ (Macro).
C00024 00006	\QUEST 4\ (Iteration).
C00026 00007	\QUEST 6\ (Discussion).
C00029 00008	\par\vfill\eject
C00030 ENDMK
\input lisp[206,tex]  % TEX file for Homework Set 6, Spring 1979

% This is hw set RDG wrote, handed out 8-May, due 22-May
\HeadA⊂Problem Set $\#$6 - Due May 22, 1979⊃

\QUEST 1\ (Diagnosing, [What Else]).
We now further increase the versatility of the Data Base of patients and
This modification will, once again, involve changing from a symbol to a function.
For each disease, each symptom will still be in the form of a
\LISPE CONS|ed pair, \LISPE (\cons ⊂symp-fn . require-fn⊃)|,
only now
the requirement slot \LISPE require-fn| will be a function.
[The \LISPE symp-fn| will remain a function, as in last assigment.]

\HeadC ⊂Part 1⊃
You are to write a battery of routines to perform the following functions:
Each should expect two arguments, which will be the 
values of $\Phi↓{P,d}$ and 
\LISPE \funct symp-fn[ P ]|;
and will return the updated value of $\Phi↓{P,d}$.
You should include the following:
$$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\rm --- #}\cr
\%Must-Be⊗which does just what \LISPI Must-Be| did\cr
\%Must-Not-Be⊗which does just what \LISPI Must-Not-Be| did\cr
\%Should-Be⊗like \LISPI \%Must-Be|, but uses \LISPI AVE| where 
\LISPI \%Must-Be| used \LISPI TIMES|\cr 
\%Should-Not-Be⊗like \LISPI \%Must-Not-Be|, but uses \LISPI AVE| where 
\LISPI \%Must-Not-Be| used \LISPI TIMES|\cr 
\%May-Be⊗like \LISPI \%Must-Be|, but uses \LISPI MAX| where 
\LISPI \%Must-Be| used \LISPI TIMES|\cr 
\%May-Not-Be⊗like \LISPI \%Must-Not-Be|, but uses \LISPI MAX| where 
\LISPI \%Must-Not-Be| used \LISPI TIMES|\cr 

This uses the averaging functions,
\LISPI \funct AVE[ x,y ] \assign|\LISPE (QUOTIENT (PLUS X Y) 2.0)|.

\HeadC ⊂Part 2⊃
Now associate with each disease
an {\sl a priori} likelihood that any patient has this ailment.
That is, each disease will have the property (ie, its PLIST,)
\LISPI A-Priori|
whose value will be some flonum between $0.0$ and $1.0$.
When computing the probably some patient has some disease,
$\Phi↓{P,d}$ will be initialized to this value.

Rewrite last assignment's \LISPI Probably-Has| function to deal with
these two changes: that the second half of each symptom's pair is 
a function, and that the starting value $\Phi↓{P,d}$ must be looked up.

\HeadC ⊂Part 3⊃
Write a function which modifies the existing data set to match the above
It should read through the list of diseases,
performing the following modification to each individual disease:
First, it should add the \LISPI A-Priori| property to each.
For the time being, this should be $\sigma( d )$ for each disease, d,
where $\sigma( d )$ is defined as 
\LISPI $1.0 -$ [\funct SXHASH[ d ] $\div$ MAX]|,
using the name of the disease, \LISPI d|, (e.g. \LISPI Raving-Mad|,)
and \LISPI MAX \eq $\max↓{d}$[\funct SXHASH[ d ]]|,
as a normalizing factor.
it should read through the \LISPI Symptom| list,
replacing each
\LISPI Must-Be| atom with the \LISPI \%Must-Be| function;
and similarly for  \LISPI Must-Not-Be|.
Once this transforming function has been written,
set it on \LISPI DISEASES|.
\HINT For testing purposes, you may try running with \LISPI A-Priori|
set to $1.0$.\tnih
\HINT If you mess up your copy of \LISPI DISEASES| during this processing,
you will have to re-read it in.\tnih

\HeadC ⊂Part 4 (Optional)⊃
Can you think of a better form for these requirement functions?
I.e. one which more accurately reflects the nature of such
\LISPI Must-Be|, \LISPI Should-Be|, and \LISPI May-Be|
Is there some other data structure which you would find advantageous?
\QUEST 2\ (Pattern Matching).

\HeadC ⊂Part 1⊃
a) Using the \LISPI MATCHES|\footnote\dag[The same caveat still applies:
When ``*\underspace\underspace'' variables are used, first listify the expression
in which it appears.]
function written for the last homework set,
write a substituting function, \LISPI \funct REPLACE[ old, pat, new ]|.
It should scan for the first occurence it finds of 
(an instantiated  version of)
\LISPI pat| within (a new copy of) the S-expression, \LISPI old|.
It should then replace this with the S-expression, \LISPI new|,
and return this result.
[Note that this is non-destructive: \LISPI old| is unchanged.]
As a side effect, it should set the global variable, 
\LISPI $\$$Found-It|\footnote*[I will
try to follow the convention of starting the name of each global variable 
with the character $\$$.],
to \T if such a substitution occured 
[i.e. if an instance of \LISPI pat| was found,]
and \NIL otherwise.
For example:
\LISPI (REPLACE '(A (B C) D B A) '(B ?) 'E)| should return 
\LISPI '(A E D B A)|, and the value of
\LISPI $\$$Found-It| will be {\T}.
Note the \LISPI (B A)| at the end of the \LISPI old| argument is not substituted;
only the first occurence is altered.

b) Write this function as an FEXPR, to avoid typing those distracting `` {'} ''

\HeadC ⊂Part 2⊃
Define the function
\LISPI \funct nREPLACE[ old, pat, new ]| which actually overwrites
the cells in \LISPI old| when performing this substitution.
It is
otherwise just like \LISPI REPLACE|.
[IE \LISPI $\$$Found-It| is appropriately set.]

\HeadC ⊂Part 3⊃
Now write
\LISPI \funct REPLACE-1[ old, pat, new, $n$ ]|
which replaces the first $n$ occurences of (instances of)
\LISPI pat| in \LISPI old| with \LISPI new|.
This should be non-destructive --- ie, like 
\LISPI REPLACE|, it does not modify \LISPI old|.
It should reset the global \LISPI $\$$Found-Num| to the number of substitutions
it actually performed.
[In general, \LISPI $\$$Found-Num $≤$ $n$|.
Only when \LISPI $\$$Found-Num \eq $n$| were all the substitutations
In the special case that \LISPI $n$ \eq 'INFINITY|,
all possible substitutations should be made.

What should
\LISPI (Replace-1 '(A (A (A (A (A (A B)))))) '(A B) 'B 'INFINITY)|

\HeadC ⊂Part 4⊃
Write the corresponding
\LISPI \funct nREPLACE-1[ old, pat, new, $n$ ]| function.
What are the advantages/disadvantages of merely calling
\LISPI \funct nREPLACE[ old, pat, new ]| $n$ times?
\QUEST 3\ (Macro).
Write an \LISPI IF| macro.
As an example, it should take tranform
$$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr
(IF (= 2 fred) ⊗THEN (PRINC '{$|$Fred is $|$}) (PRINC 2)\cr
⊗ELSE (PRINC '{$|$Fred is NOT $|$}) (PRINC 2)),\cr
$$\vcenter{\halign{\lft{\LISPI #|}⊗\lft{\LISPI #|}\cr
(COND ⊗((= 2 fred) (PRINC '{$|$Fred is $|$}) (PRINC 2))\cr
⊗(T (PRINC '{$|$Fred is NOT $|$}) (PRINC 2))).\cr
It should scan for the keywords
\NOTE ``\LISPI IF|'' is NOT included in the above list,
as LISP itself will take care of the recursion,
if, for example, an \LISPI IF| is embedded within a \LISPI THEN| clause.\eton
\NOTE There may be an arbitrary number of forms between
any pair of keywords. If more than one follows preceeds the \LISPI THEN|,
they should be placed in a \LISPI PROGn|.\eton
\HINT The \LISPI MATCHES| function may be useful for this.\tnih

\HeadC ⊂Optional⊃
If you wish to get fancy, you may print error and warning messages:
Finding no \LISPI THEN| atom should always be an error. However,
if this clause is empty,
(ie immediately followed by a ``\LISPI (|'', ``\LISPI ELSE|''
or ``\LISPI ELSEIF|'',)
or if there is no \LISPI ELSE| clause, a warning may be generated.
\NOTE The \LISPI IF| macro should, of course, properly process these cases.\eton
\QUEST 4\ (Iteration).
Use \LISPI DO| to write a program which computes the $n↑{th}$ Fibonocci

Write the functions \LISPI OR-F|
and \LISPI OR-L|,
which simulates the standard LISP \LISPI OR| function,
as an FEXPR, and as a LEXPR , respectively.
(Why can't it be written as a standard EXPR?)
Which is more accurate?
\Hint Consider \LISPI (OR-? T (PRINC '{$|$What?$|$}))|.\tnih
\QUEST 6\ (Discussion).
Discuss the advantages/disadvantages inherent to EXPRs, FEXPRs, LEXPRs, and MACROs.
Describe situations in which a FEXPR is preferable to a MACRO,
and vice versa.