\newchapter{Symbolic computation}

\leveldown{}

\epigraph{We will then augment the representational power of our language by introducing symbolic expressions --- data whose elementary parts can be arbitrary symbols rather than only numbers.}{Structure and Interpretation of Computer Programs}

Some numbers can only be represented in binary system approximately, like $\frac{1}{3}$ and $\pi$.
If we calculate $\frac{1}{3} \cdot 3$ step-by-step, we may have loss of significance.
We also know that $sin(\frac{\pi}{2}) = 1$, but calculating this expression in usual way,
we can also have some noise in result.
Arbitrary-precision arithmetic\footnote{\url{https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic}} is not a solution,
because these numbers cannot be stored in memory as a binary number of finite length.

How we could tackle this problem?
Humans reduce such expressions using paper and pencil without any calculations.
We can mimic human behaviour programmatically if we will store expression as tree and symbols like $\pi$ will be converted into number at the very last step(s).

This is what Wolfram Mathematica\footnote{Another well-known symbolic computation system are 
\href{https://en.wikipedia.org/wiki/Maxima_\%28software\%29}{Maxima} and 
\href{https://en.wikipedia.org/wiki/SymPy}{SymPy}} does.
Let's start it and try this:

\begin{lstlisting}
In[]:= x + 2*8
Out[]= 16 + x
\end{lstlisting}

Since Mathematica has no clue what $x$ is, it's left \textit{as is}, but $2 \cdot 8$ can be reduced easily, both by Mathematica and by humans,
so that is what has done.
In some point of time in future, Mathematica's user may assign some number to $x$ and then, Mathematica will reduce the expression even further.

Mathematica does this because it parses the expression and finds some known patterns.
This is also called \textit{term rewriting}\footnote{\url{https://en.wikipedia.org/wiki/Rewriting}}.
In plain English language it may sounds like this:
``if there is a $+$ operator between two known numbers, replace this subexpression by a computed number which is sum of these two numbers, if possible''.
Just like humans do.

Mathematica also has rules like ``replace $sin(\pi)$ by 0'' and ``replace $sin(\frac{\pi}{2})$ by 1'', but as you can see, $\pi$ must be preserved
as some kind of symbol instead of a number.

% TODO example
So Mathematica left $x$ as unknown value.
This is, in fact, common mistake by Mathematica's users: a small typo in an input expression may lead to a huge irreducible expression with the typo left.

Another example: Mathematica left this deliberately while computing binary logarithm:

\begin{lstlisting}
In[]:= Log[2, 36]
Out[]= Log[36]/Log[2]
\end{lstlisting}

Because it has a hope that at some point in future, this expression will become a subexpression in another expression and 
it will be reduced nicely at the very end.
But if we really need a numerical answer, we can force Mathematica to calculate it:

\begin{lstlisting}
In[]:= Log[2, 36] // N
Out[]= 5.16993
\end{lstlisting}

Sometimes unresolved values are desirable:

\begin{lstlisting}
In[]:= Union[{a, b, a, c}, {d, a, e, b}, {c, a}]
Out[]= {a, b, c, d, e}
\end{lstlisting}

Characters in the expression are just unresolved symbols\footnote{\textit{Symbol} like in LISP} with no connections to numbers or other expressions, 
so Mathematica left them \textit{as is}.

Another real world example is symbolic integration\footnote{\url{https://en.wikipedia.org/wiki/Symbolic_integration}}, 
i.e., finding formula for integral by rewriting initial expression using some predefined rules.
Mathematica also does it:

\begin{lstlisting}
In[]:= Integrate[1/(x^5), x]
Out[]= -(1/(4 x^4))
\end{lstlisting}

Benefits of symbolic computation are obvious: it is not prone to loss of significance\footnote{\url{https://en.wikipedia.org/wiki/Loss_of_significance}} and 
round-off errors\footnote{\url{https://en.wikipedia.org/wiki/Round-off_error}}, but drawbacks are also obvious: you need to store expression in (possible huge) tree
and process it many times.
Term rewriting is also slow.
All these things are extremely clumsy in comparison to a fast \ac{FPU}.

``Symbolic computation'' is opposed to ``numerical computation'', the last one is just processing numbers step-by-step, using calculator, \ac{CPU} or \ac{FPU}.\\
\\
Some task can be solved better by the first method, some others -- by the second one.

\myheading{Rational data type}

Some LISP implementations can store a number as a ratio/fraction
\footnote{\url{https://en.wikipedia.org/wiki/Rational_data_type}}, i.e., placing two numbers in a cell (which, in this case, is called \textit{atom} in LISP lingo).
For example, you divide 1 by 3, and the interpreter, by understanding that $\frac{1}{3}$ is 
an irreducible fraction\footnote{\url{https://en.wikipedia.org/wiki/Irreducible_fraction}}, creates a cell with 1 and 3 numbers.
Some time after, you may multiply this cell by 6, and the multiplication function inside LISP interpreter may return much better result (2 without \textit{noise}).

Printing function in interpreter can also print something like \TT{1 / 3} instead of floating point number.

This is sometimes called ``fractional arithmetic'' [see \ac{TAOCP}, 3rd ed., (1997), 4.5.1, page 330].

This is not symbolic computation in any way, but this is slightly better than storing ratios/fractions as just floating point numbers.

Drawbacks are clearly visible: you need more memory to store ratio instead of a number;
and all arithmetic functions are more complex and slower, because they must handle both numbers and ratios.

Perhaps, because of drawbacks, some programming languages offers separate (\textit{rational}) data type, as language feature, or supported by a library
\footnote{More detailed list: \url{https://en.wikipedia.org/wiki/Rational_data_type}}:
Haskell, OCaml, Perl, Ruby, Python (\textit{fractions}), Smalltalk, Java, Clojure,
C/C++\footnote{By GNU Multiple Precision Arithmetic Library}.

\levelup{}