COMMENT ⊗   VALID 00008 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input mytex[1,rdg]  % This is a TEX file, used in the soln for Problem Set 1
C00003 00003	\HeadA⊂Answers to Problem Set $\#$1 - Due April 10, 1979⊃
C00008 00004	\QUESTION 4.
C00010 00005	\QUESTION 5.
C00021 00006	\QUESTION 6\ (Optional).
C00030 00007	\QUESTION 8.
C00034 00008	\par\vfill\eject
C00035 ENDMK
C⊗;
\input mytex[1,rdg]  % This is a TEX file, used in the soln for Problem Set 1

% This is the answer to the homework set # 1 
% Handed out: Thursday 3-April; due Thursday 10-Apr

\def\QUESTION #1.{\HeadB⊂Question $\#$#1⊃\eightpoint\hangindent 10pt\sl\xskip\!}
\def\ANSWER{\par\HeadC⊂Answer⊃\ninepoint\rm\!}
\def\LISP{\bf}
\def\NOTE #1\eton{\par{\sl $\underline {NOTE}$: #1}\par}
\def\a{{\LISP $\underline a$}}
\def\d{{\LISP $\underline d$}}
\def\equatno(#1){{\sl Equation (#1)}}
\def\ref #1[#2]{{\bf #1},{\sl #2}}
\HeadA⊂Answers to Problem Set $\#$1 - Due April 10, 1979⊃

\QUESTION 1.
If we represent sums and products as indicated above, and use
{\LISP (MINUS X)}, {\LISP (QUOTIENT X Y)}, and {\LISP (POWER X Y)},
as representations of $-x$, $x\over y$ and $x↑y$ respectively, then\par
\halign{\quad\lft{#}⊗\ \lft{#}\cr
a. ⊗What do the following lists represent?\cr% \vskip 3pt
⊗\qquad {\LISP (QUOTIENT 2 (POWER (PLUS (MINUS Y) 3))}\cr
⊗\qquad {\LISP (PLUS -2 (MINUS 2) ((TIMES X (POWER Y 3.3)))}\cr% \vskip 3pt
b. ⊗How are the expressons $xyz+3(u+v)↑{-3}$ and $(xy-yx)/(xy+yx)$ represented?\cr
}

\ANSWER
\NOTE The ``sums and products as indicated above'' mentioned above may be
{\hbox {$n$-ary}} -- not just binary.\eton
\halign{#⊗#⊗\lft{#}\cr
a⊗1. ⊗$2\over (X +(-Y))↑3$\cr
⊗2. ⊗$-2 + -2 + (X \times Y↑{3.3})$\cr
b⊗1. ⊗{\LISP (PLUS (TIMES X Y Z) (TIMES 3 (POWER (PLUS U V) (MINUS 3) ) ) )}\cr
⊗2. ⊗{\LISP (QUOTIENT (PLUS (TIMES X Y) (MINUS (TIMES Y X) ) )}\cr
⊗⊗\qquad{\LISP (PLUS (TIMES X Y) (TIMES Y X) ) )}\cr
}

\QUESTION 2.
``Represent the network or graph acconrding to a scheme whereby there is a sublist
for each vertex consisting of the vertex itself followed by the vertices to which
it is connected.''\par
In the above mentioned graph notation, what graph is represented by the list
{\LISP ((A D E F) (B D E F) (C D E F) (D A B C) (E A B C) (F A B C))}?
\ANSWER
This graph, $L↓{3,3}$,
corresponds to the famous {\sl Gas, Water and Electric Graph} --
where each of these three utilities hook up to each of three houses.
See Figure 1 at end of answer set.

\QUESTION 3.
Write the list {\LISP (PLUS (TIMES X Y) X 3)} as an S-Expression.
This is sometimes referred to as ``dot-notation''.\par
\ANSWER
\NOTE The handout showed {\LISP $\underline ($ (PLUS (TIMES X Y) X 3)}. 
The extra first ``{\LISP (}''  was a typo.\eton
{\LISP $\left(PLUS\ .\ \biggglp\bigglp TIMES\ .\ \biglp X\ .\ (Y\ .\ NIL) \bigrp\biggrp
.\  \biglp X\ .\ (3\ .\ NIL) \bigrp\bigggrp\right)$}.
If you had trouble constructing this, try drawing first the LISP Cells.
See Figure 2 at end of answer set.
\QUESTION 4.
Write the following S-Expressions in list notation to whatever extent is
possible.\par
\halign{\quad#. ⊗\lft{\LISP #}\cr
a⊗(A . NIL)\cr
b⊗(A . B)\cr
c⊗((A . NIL) . B)\cr
d⊗((A . B) . ((C . D) . NIL)\cr
}
\ANSWER
One can apply the rules:
$$\vcenter{\halign{\rt{\LISP #}⊗$\ \→\ $\lft{\LISP #}\cr
(\ {\sl <expr>}\ .\ NIL\ )⊗(\ {\sl <expr>}\ )\cr
(\ {\sl <expr-1>}\ .\ ({\sl <expr-2>}) )⊗(\ {\sl <expr-1>}\ {\sl <expr-2>}\ )\cr
}}$$
[where {\sl <expr>}, {\sl <expr-1>} and {\sl <expr-2>} are all S-expressions,]
to derive the answers:\par
\halign{\quad#. ⊗\lft{\LISP #}⊗#\cr
a⊗(A)⊗\cr
b⊗(A . B)⊗  i.e. no change\cr
c⊗((A) . B)⊗\cr
d⊗((A . B) (C . D))\cr
}
\QUESTION 5.
How would you represent polynomials in one variable as lists? 
Can you think of more than one way? 
How would you represent polynomials in several variables?
Can you tell if two lists represent the same polynomial?
\ANSWER
There are several possible answers.
[An abbreviated version of an subset of the following would
constitute an acceptable answer.]
The most obvious encoding is to to precisely represent the polynomial itself.
Then $a↓n X↑n + a↓{n-1} X↑{n-1} + \cdotss + a↓1 X + a↓0$ would be transformed
to 
{\LISP (PLUS (TIMES a$↓n$ (POWER X n) )
(TIMES a$↓{n-1}$ (POWER X n-1) ) $\cdotss$
(TIMES $a↓1$ (POWER X 1) ) (TIMES a$↓0$ (POWER X 0) ) )}.

Other solutions make use of the fact that we are
dealing with a polynomial in one variable.
Merely listing the coefficients in ascending (or descending) order
is a straightforward represetation.
This  same
$a↓n X↑n + a↓{n-1} X↑{n-1} + \cdotss + a↓1 X + a↓0$
could be efficiently represented as either
{\LISP (a$↓N$ a$↓{N-1}$ $\cdots$ a$↓1$ a$↓0$)} or
{\LISP (a$↓0$ a$↓1$ $\cdots$ a$↓{N-1}$ a$↓N$)}.
[Forgive the dot-like ellipses. The above are bonafide lists.]
Notice that this polynomial may be of arbitrary length, and still use this format --
this is one big advantage in list structures.
If this polynomial is sparse, (i.e. most coefficients are $0$,)
it may be more space efficient to store a list of {\LISP CONS}ed pairs.
Each of these pairs refers to a term, $a↓i X↑i$ in the polynomial for which
the coefficient is non-trivial.
The \a\ part holds the power, $i$, of this term, and the \d\ part,
the coefficient, $a↓i$.
[The purists will remark this question asked for a {\bf list} representation,
and each member of this list is really a more general S-expression.
We could appease such a critism by replacing each term in the list by a list,
and use its \a\ and \d\a\ parts for the power and coefficient, respectively.]
Or we could use this same approach, and general a list of simple numbers,
where the $1↑{st}$, $3↑{rd}$, $5↑{th}$, and so on hold the exponents of the terms
whose coefficient is the $2↑{nd}$, $4↑{th}$, $6↑{th}$, $\ldots$.
[EG: One suggestion would represent $x↑7 + 3x↑3 - 5x$ as 
{\LISP ( (7 . 1) (3 . 3) (1 . -5) )}, or 
{\LISP ( (7 1) (3 3) (1 -5) )} in its first modification; or simply
{\LISP (7 1 3 3 1 -5)} in the second.]

As all polynomial are factorable, one could also encode a polynomial as a
list of its roots, preceded by its leading (scaling) coefficient.
As this may require complex numbers, one should provide for an encoding for
$a+b\iit$\ -- for example, as {\LISP (a . b)}.

One can provide yet other answers to this question if some other knowledge 
about this problem is assumed -- for example,
knowing, {\sl a priori}, that only the $3↑{rd}$ and $17↑{th}$ terms may
vary, we could just encode these two values in a list.

If we know each coefficient is a natural number, we
could be cute, and apply the following procedure, 
plucked  from the number theorist's bag of tricks:
As background, the {\sl Fundamental Theory of Arithmetic} states that
every natural number has a unique prime factor decomposition.
That is, any $n \in \Nscr$ can be expressed as the product of powers
of distinct primes: i.e. $n = \prod↓i {p↓i}↑{a↓i}$, where these
$p↓i$ are primes, and all $a↓i$ are natural numbers,
(only a finite number of which are non-zero).
We can therefore encode the integer list
$\left<\ a↓1\ a↓2\ \cdotss\ a↓{n-1}\ a↓n\ \right>$ be the unique integer,
$$n↓{\left<\ a↓1\ a↓2\ \cdotss\ a↓{n-1}\ a↓n\ \right>} = \prod↓{1<i<n} {p↓i}↑{a↓i},$$
where $p↓i$ is the $i↑{th}$ prime 
--- i.e. $(\ p↓0,\,p↓1,\,p↓2\,p↓3 \ldots\ ) = (\ 2,3,5,7, \ldots\ )$.
A minor annoyance arises when these lists are of arbitrary length, as
there would be no way to determine whether the list of length $n$, or of
length, say, $n+3$, when the last $3$ terms were all $0$.
The simple solution is to encode this length, $n$, as well:
So
$$\left<\ a↓1\ a↓2\ \cdotss\ a↓{n-1}\ a↓n\ \right> \→
{p↓0}↑n \times \prod↓{1≤i≤n} {p↓i}↑{a↓i}.$$
This allows a polynomial to be encoded into a single integer --
this $n↑{th}$ degree polynomial,
$P(x) = a↓n X↑n + a↓{n-1} X↑{n-1} + \cdotss + a↓1 X + a↓0$,
would be mapped into 
$$n↓{P(x)} = {p↓0}↑n \times \prod↓{1≤i≤n} {p↓i}↑{a↓i}.$$
This could then be {\sl listified} into {\LISP ($n↓{P(x)}$)}.
One could also undo any space-saving this method might have achieved by
representing this number, $n↓{P(x)}$, as a list of this many {\LISP T}s.
[I.E. $1$ would map onto {\LISP ( T )}, $2$ onto {\LISP (T T)}, $\ldots$,
and, as expected, {\LISP $0 \→$ ()}.]
Of course,
the rquired storage space might pose a minor problem here,
but true Number Theorists would
never consider this a limitation$\ldots$.

Similar mechanisms can be used to encode polynomials of many variables.
Here there is no ready ordering analogous to one exploited in the first solution --
where simply the coefficients are listed by the ascending order of the sole variable.
An answer is to represent each term in the polynomial as a term in a list.
If most addends use most of the variables,
this $a↓{i↓1i↓2\cdots i↓M}X↓1↑{i↓1}X↓2↑{i↓2}\cdots X↓M↑{i↓M}$ 
term could be represented by the list
{{\LISP (i$↓1$ i$↓2$ $\cdots$ i$↓M$ a$↓{i↓1i↓2\cdots i↓M}$ )}}.
When $M=1$ this reduces to one of the cases shown above.
If you expect only a few of the $M$ variables to be present in most of the terms,
(i.e. have a non-zero power,)
then space could be saved by explicitly mentioning just those variables with
such a non-trivial power.
So, if $5.2{x↓2}↑3x↓4$ was one term in this polynomial over  the four variables,
$\leftset x↓1, x↓2, x↓3, x↓4 \rightset$, it would be represented
by {\LISP (2 3 4 1 5.2)}, where the first two terms, $2$ and $3$,
mean that $x↓2$ was raised to the $3↑{rd}$ power, and the $4$ and $1$ refer to the
$x↓4↑1$ multiplicand. The final $5.2$ is the coefficient.
[If $x$, $y$, and $z$s were used, they could be inserted as the odd members of
this terms, in leiu of the subscripts now used.]

One requirement for any encoding scheme is the ability to decode it back -- in this
case, into the polynomial it was representing. 
Hence one can always determine if two lists represent the same polynomial:
At worst, this can be done by decoding both lists, and comparing the resultant
polynomials. Of course, this can be done more easily in some schemes than in others.
\QUESTION 6\ (Optional).
Prove that the number of ``shapes'' of S-expressions with $n$ atoms is 
$(2n-2)!\over [n! (n-1)!]$.
(The two shapes of S-expressions with three atoms are 
{\LISP (A . (B . C))} and {\LISP ( (A . B) . C))}.
\ANSWER
Now let $s↓n$ be the number of ``shapes'' of S-expressions with $n$ atoms.
By the defination of S-expressions,
both the \a\ and \d\ parts of any S-expression with $n$ atoms
(when $n>0$,) will point to sub-S-expressions.
WLOG the \a\ part will lead to $i$ atoms, and the \d\ part, to $n-i$.
From the defination of these $s↓k$s,
there are precisely $s↓i$ such sub-trees sprouting from this \a\
part, and independently, $s↓{n-i}$ shapes from the \d.
Thus, there are $s↓i \times s↓{n-i}$ S-expression with $n$ atoms, where
the \a\ part has exactly $i$ atoms. 
This $i$ can range from $1$ up to $n-1$. 
[Both $0$ and $n$ were excluded because neither the \a\ nor the \d\ part
may lead to $0$ atoms.]
Thus, we have the recurrance relation:
$$s↓n = \sum↓{i=i}↑{n-1} s↓i s↓{n-i}\eqno(1)$$
With the boundary condition, $s↓1 = 1$, we might consider this problem solved -
a proof by induction. 
Proving far too messy, it was abandoned in favor of the proof given as the
following answer.

\QUESTION 7\ (Optional).
The above result can also be obtained by writing $S = A + S \times S$ as an 
``equation'' satisfied by the set of S-expressions with the nterpretation
that an S-expression is either an atom or a pair of S-expressions.
The next step is to regard the equation as the quadratic $S↑2 - S + A = 0$,
solve it by the quadratic formula choosing the minus sign for the square root.
Then the radical is regarded as the $1\over 2$ power, and expanded by the binomial
theorem. Manipulating the binomial coefficients yields the above formula as
the coefficient of $A↑n$ in the expansion.
Why does this somwhat ill-motivated and irregular procedure give the right answer?
\ANSWER
``{\sl Ah, the wonder of mathematics}'' is not the desired response.
Instead, we will start with the conditions given in partial answer to
{\sl Question 6}.
Notice the form in \equatno(1) resembles the coefficient of the $x↑n$th
term of the product of two polynomials; in both cases,
a sum is taken over those terms whose subscripts sum to $n$.
Here only the $i=0$ and $i=n$ cases have been omitted.
With this as motivation, let us define the appropriate polynomial
$$S(x) = \sum↓{n≥0} s↓n x↑n.\eqno(2)$$
As a first comment, let $s↓0 = 0$. Not only will this save some trouble
later on, but this ``number of shapes of S-expressions with $0$ atoms''
would be a hard to define quantity anyway.
We then wish to consider ${S(x)}↑2$.
If we assume this infinite sequence is sufficiently
well behaved to randomize the order of summation,
we may write this out
$$S(x) \times S(x) = \sum↓{n≥0}\,\left[\sum↓{i=0}↑n s↓i \times s↓{n-i}\right] x↑n.\eqno(3)$$
For $n > 1$, the $n↑{th}$ coefficient of this product polynomial can be written
$$(2 \cdot s↓0 \cdot s↓n)+ \sum↓{i=1}↑{n-1} s↓i s↓{n-i}.\eqno(4)$$
Noting that $s↓0 = 0$, we may ignore the first addend above, leaving only
the summation which, by \equatno(1) above, means each coefficient
is precisely $s↓n$ for all $n≥2$, and $0$ for $n=0$ and $1$.
Putting this together,
$$S(x) \times S(x) = \ldots = \sum↓{n>1} s↓n x↑n = S(x) - [s↓1x + s↓0].\eqno(5)$$
As $s↓1 = 1$ and $s↓0 = 0$, this means
$$S(x)↑2 = S(x) - x,\eqno(6)$$
which is but a change of variables from the equation given.

We once again throw mathematical caution to the wind,
with the na{\"\i}ve assurance that
this formal power series can be manipulated at will, and all transformations
will be valid.
Here we regard this ``$S(x)$'' as a single variable, and solve the quadratic
equation, using \equatno(6) above.
We get
$$S(x) = {1 \pm \sqrt{1 - 4 \cdot 1 \cdot x}\over 2}.\eqno(7)$$
The $(1 - 4 x)↑{1\over2}$ term expands to
$$\sum↓{m≥0}{{1\over2}\choose m} (-4x)↑m.\eqno(8)$$
Taking the suggested $\null - \null$ radical,
and using\footnote*[Non-believers should consult 
{\ref Knuth[Vol I]},
pages 385-389 for this expansion, (for \equatno(8),)
and page 72 for following equality (for \equatno(9).)]
$${{1\over2}\choose m} = {(-1)↑{m-1}\over 4↑m(2m-1)}{2m\choose m},\eqno(9)$$
we see
$$\vcenter{\halign{{#}⊗\lft{$\dispstyle{\null = #}$}\cr
$S(x)$⊗{1\over2}\left\{1 - \sum↓{m≥0}
	\left[{(-1)↑{m-1}\over 4↑m(2m-1)}{2m\choose m}(-4x)↑m\right]\right\}\cr
⊗{1\over2}\left\{1 - \sum↓{m≥0}
	\left[{(-1)↑{m-1}(-1)↑m\over 4↑m(2m-1)}{2m\choose m}4↑mx↑m\right]\right\}\cr
⊗{1\over2}\left\{1 - -\sum↓{m≥0}
	\left[{1\over (2m-1)}{2m\choose m}x↑m\right]\right\}\cr
}}\eqno(10)$$
We now pull out the $m=0$ term, and see it equals
$$\left({1\over (2\times 0 - 1)}{{2\times 0}\choose 0}\right)
= \left({1\over -1}{0\choose 0}\right)
= -1.
\eqno(11)$$
Thus, this power series is:
$$\vcenter{\halign{{#}⊗\lft{$\dispstyle{\null = #}$}\cr
$S(x)$⊗\ldotss\cr
⊗{1\over2}\left\{1 + -1 +
	\sum↓{m>0}\left[{1\over (2m-1)}{2m\choose m}x↑m\right]\right\}\cr
⊗\sum↓{m>0}\left[{1\over 2(2m-1)}{2m\choose m}x↑m\right]\cr
}}\eqno(12)$$
Thus each coefficient of this polynomial, for all $n>1$, is 
$$s↓n = {{2n\choose n}{1\over 2(2n-1)}} =
{(2n-2)!\over (n-1)! n!}
\eqno(13)$$,
as desired.
{\bf QED}
\QUESTION 8.
``Lisp functions operate upon S-expression, and are themselves S-expressions.''
State briefly what this means from each of the three points of view:
LISP as a mathematical formalism, LISP as a programming language for Artificial
Intelligence applications, and LISP as an implementation language.
\ANSWER
This is the vonNeumann concept, of identical instructions and data representations.
As a mathematical formalism, this permits the the procedures to be examined
as mathematical objects, in the same manner as other data.
These program-objects can then be readily analysized.
Program Verication, dedicated to proving programs ``correct'',
is an example of this in operation.
From an Artificial Intelligence point of view, 
it is often useful to manipulate the operators,
and thereby effectively update the course of action to be taken in a given situation.
Automatic Programming is based on this ability.
These transforms,
done using the same methods which manipulate conventional data,
can be used to update even the program currently being run itself.

This facility makes LISP a very versatile and effective implementation language,
as new features can be added very easily.
This allows for easy bootstrapping 
-- once the core LISP functions have been implemented,
they can be used in the defination of the rest.
It also means the same format can be used to store ``source'' code as other data
within a work area.

An ongoing debate has long raged within the AI community on whether
the nature of computers can be defined in a {\sl Declarative} versus
a {\sl Procedural} manner. [See Winston's book.]
This whole controversy has meaning only in the context of such a LISP-like
system, where the distinction between functions and data can be blurred.
\par\vfill\eject
\end