<commit_before>
			A brief introduction to Lisp

		Introduction

Yacas owes much of its current form to Lisp. A lot of ideas from
Lisp have been taken over into the Yacas interpreter. This book
aims to describe this connection, to show how Yacas compares
to other {Lisp} dialects ({Yacas} can be viewed as a dialect
of Lisp), and how the {Yacas} interpreter is related to Lisp.

Viewed from the top level, {Yacas} is just one function; {Yacas} is 
called with one, or possibly two arguments, or from a different point 
of view, a request is made to the {Yacas} system. How the function 
performs the action is implementation-dependent, but at the top-level
it can be viewed as one call. From c++ or Java, it might look like 

	yacas.Evaluate("expression");

Or from Lisp,

	(yacas expression environment)

The {environment} argument is optional; it can be a global resource 
that doesn't have to be passed in.

For instance, taking the derivative of a function could look like

	yacas.evaluate("D(x)Sin(x);");

when in c++, or 

	(yacas '(D x (sin x)) )

when in Lisp. The quote in Lisp makes it clear that the argument, 
the parameter to the request, is actually data, and not program. 
This is an important distinction which has to be made clear in 
Lisp, but is clearer in other environments, due to the form of data being
distinct from the form of program.

To drive home this point, {(* a 1)} would raise an error when given 
to the Lisp {eval} function if the variable {a} is not bound to a 
value, but would be perfectly valid data when passed to a CAS. In 
fact, one would like it to return {a} in this case. The {*}
operator is actually a function call when invoked from Lisp ( {(* a 1)} 
is a <i>program</i>), but is data when passed to a CAS.

One can conclude that {Yacas}, an engine for simplifying symbolic 
expressions and performing calculations, is just one huge function 
that performs that task, and has one entry point, a function call 
with one argument as the data to the request.

This section will first introduce the reader to the basic concepts 
of Lisp, and then proceed to show how the {yacas} function can be 
implemented in Lisp in general. Clearness of concepts explained will 
be favoured over efficiency and performance. A small subset of Lisp 
will be used, so it should be easy to take the code along to various 
different Lisp dialects, or to write a little Lisp implementation to 
implement the {yacas} function.

The first chapter briefly describes a small Lisp dialect. A small subset 
of what is usually found in the average Lisp interpreter is described. 
The Lisp dialect is different in small subtle ways from normal
Lisp implementations. Simplicity is put first. 

For the Lisp dialect presented, one was chosen that is different
from the Lisp dialect that represents {Yacas}. This separation
is done explicitly, on purpose, to facilitate implementation of
execution of algorithms written out in {Yacas} syntax from 
any other language. All the {Yacas}-specific details have to
be handled by the routine performing these algorithms, independent
of language constructs that might support it. 

Even though in Lisp program and data look the same, for {Yacas}
they are distinctly different in that data will likely not 
be evaluated by the default evaluator. It is important to keep
the distinction between data and program. 


		A little history of Lisp

Lisp is one of the older computer programming languages in existence.
It came from a mathematical background, lambda calculus, and is
used even now. Arguably, most programming languages owe a lot
to Lisp.

There are various sources on the internet describing the early history
of Lisp.

*REM should we put up a list here? Or have our own short history? Mention
*REM McCarthy etcetera?

		The Lisp interactive command line interface

When Lisp is started, the user is generally greeted with a prompt.
The Lisp interpreter is in its {read-eval-print} loop; it reads
in an expression typed in by the user, evaluates it, and prints
the result of evaluation to the console. 

The definition of an expression can be given like this: 

*	0. an expression is either an atom, or a list of expressions. 
*	0. an atom is a word, a list of characters.

So, the words {foo} and {bar} could be called atoms. A list is 
represented by writing the expressions in the list out with
spaces in between them, and brackets around them. So, {(foo bar)}
would be a list with two elements, {foo} and {bar}.

In Lisp, each expression can evaluate to a value (if no error occurred).
When evaluating an atom, the atom can either be a 'special' atom
that evaluates to itself, or otherwise a lexical word that refers
to a variable. When it is a variable, the Lisp system looks up its
value, and returns the value the variable is bound to, in what
is called the 'environment' the Lisp interpreter is evaluating in.
When a variable is not bound, an error is raised. 
The noted difference with the usual Lisp
dialects is that a normal Lisp system raises an error when an expression 
tries to evaluate a variable that is not bound to a value, whereas
in a CAS, the variable is a free parameter in some expression.

When a list of expressions is encountered, the first element in
the list is a function that should be called, and the rest of the
expressions in the list are the arguments. The interpreter handles
the list by first evaluating the arguments (the rest of the list),
and then calling the function with the evaluated arguments as parameters
to the function. There are exceptions to this; the function {quote}
returns its argument unevaluated. In stead of writing 
{(quote <expression>)}, a common short-hand is {'<expression>},
eg. the expression with a quote in front of it. Quotes are used
a lot, to tell the system that data is being passed in.

For the following example interaction, the following commands
are used: 
*	{quote} - {quote} takes one argument and returns it unevaluated
*	{eval}  - {eval}  takes one argument, which is evaluated before
{eval} is called, and then {eval} evaluates it again. {eval} can be used
to oppose {quote}.
*	{setf} - {setf} takes two arguments, the first a name of a variable,
the second an expression to be evaluated. The result of evaluating the second
argument is assigned to the variable.

The following is an interaction with our little lisp dialect. In the 
usual Lisp dialects, when variables are unbound, an error is raised.

	In> a
	Error, variable has no value : a

Lisp dialects are usually case-insensitive (the atom {a} is the same as {A}).

Here the atom {a} evaluated to itself, because it was not assigned.

	In> (setf a '(this is a list))
	Out> (this is a list )
	In> a
	Out> (this is a list )

Here we assigned the value {(this is a list)} to the variable {a},
and {a} now evaluates to that list. The system looked up the value
bound to the variable {a} without re-evaluating it.

*REM TODO@@@

	In> 'a
	Out> a
	In> (eval a)
	ERROR: function not defined : this
	Out> nil

With {quote} we can withhold evaluating a, and with {eval}
we can re-evaluate {a}. Since {this} is not a defined function
in this case, an error is raised.

Note that evaluation as defined in Lisp dialects is less suitable for 
CAS systems. A CAS would return expressions unevaluated,
which is what you want in a CAS. It then represents some function
which has not been specified yet. In a Lisp intepreter, it is nice
to have the interpreter raise an error, but in a CAS, where it
is data, it should not be simplified further.

For atoms that refer to variables that are not yet bound, the variables
should be returned unevaluated by default, and functions that are 
called but not defined should be returned as the same function but with their 
arguments evaluated. evaluation as defined in most Lisp dialects is not suited
to simplifying expressions. Later in this book an evaluator will
be developed in Lisp itself that is closer to a sense of 'simplification'
required for CAS.

Sometimes the user wants to refer to a function without having to define it, 
because transformation rules for the function can be given without explaining
explicitly how to go about evaluating the function. Certain functions
have properties, and sometimes it is easier to work with the properties
than to evaluate them explicitly.

For the rest of this book, it is assumed that the 
semi-colon, {;}, means that the rest of the input line
up to the end of line or end of file is a human readable comment, 
not to be executed.

		A basic set of Lisp primitive commands

Surprisingly few Lisp functions are needed to be able to implement
any algorithm in Lisp. Languages are usually referred to as being
<i>Turing complete</i> if any algorithm can be implemented in them.
Turing showed that a small apparatus, called a Turing machine,
was universal in that theoretically any algorithm could be implemented
in it. The way to show a language is Turing complete is to implement
a Turing machine in that language. if that is done, that language
can execute any algorithm, as a Turing machine can be implemented in
it, and Turing machines can execute any algorithm.

Note that building a Turing machine is just a theoretical exercise.
Turing machines don't concern themselves with efficiency. Algorithms
can be run, in finite time, but it will most certainly not be the
most efficient way to execute the algorithm on a real computer.

Methods to make execution more efficient break down in two steps:

*	0. encapsulating a specific algorithm in a function call, and
make define an efficient implementation of the function in the enviroment
the Lisp interpreter is executing in
*	0. writing a compiler that converts algorithms stated in 
Lisp code to a version that is more efficient, more close to the
hardware the program is running on

This section describes a minimum set of Lisp primitives needed 
for building a Turing machine, theoretically. After that, first
numeric operations are introduced, before implementing a Turing 
machine. Fundamentally, the language does not need to support 
arithmetic in order to be able to implement any algorithm, as other
constructs using lists can be used to represent and work with numbers,
but not implementing it does make the effort rather complex.

The following sections will describe the following minimal 
set of commands; 
*	0. macro-like commands {quote}, {if}, {cond}, {setf}, {while}, {progn}, {eval}, {defun} and {defmacro}.
*	0. function-like commands {assoc}, {first}, {rest}, {cons}, {atom}, {listp}, {list}, {equal}, {+}, {integerp}, {-} and {<}.

In the next sections, whenever a function call is explained,
the arguments to the function will be delimited by {<} and {>}.
Arguments are evaluated unless stated otherwise.

	    Naming conventions

The set of primitives described in this section are meant to be
used as building blocks for building a final bigger system.

	    Controlling evaluation

To control whether evaluation is performed, the following 
commands are available:

*	0. {(quote <expression>)} - as described in the introduction above, {quote}
takes one argument, and returns it unevaluated. 
*	0. {(eval <expression>)} - {eval} also takes one argument, and evaluates
it when {eval} is called. When {eval} is called, its argument was
evaluated already.

	    Assigning variables and functions

In addition, functions and macros can be defined:
*	0. {(setf <variable> <expression>)} - to assign a variable, {setf} can be used.
the {variable} argument is not evaluated before {setf} is called,
but {expression} is.
*	0. {(defun <function-name> <argument-list> <expression>)} - define a function
whose name is {function-name}, and a list of arguments {argument-list}.
This function can then be called from anywhere. Its arguments are first 
evaluated, and a set of local variables (listed in the {argument-list} argument) 
are reserved, and bound to the values passed in.
*	0. {(defmacro <macro-name> <argument-list> <expression>)} - does the
same as {defun}, but with the arguments not evaluated before evaluating the
body {expression}. Also, the {expression} is evaluated from within the
calling scope, so the {expression} can use variables from its calling
environment. A better way to look at macros is as if they were copy-pasted
into the place where they were called.

The default set of functions implemented in the core of a Lisp 
interpreter can be divided between function-like and macro-like
functions, in that when a function-like (defun) function is called,
its arguments are evaluated first. Examples of this are {cons},
{first} and {rest}. 

When calling macro-like (defmacro) functions, however, the arguments
are not evaluated first, and the variables defined in the calling
environment are visible while expressions using arguments on the
command line are evaluated. A macro can be viewed as a bit of
code that got pasted in to the place where it got called, by the 
interpreter (in fact, this is what a compiler can do).

The {defmacro} function allows the programmer to expand the language
by adding functions that act as if they were defined in the core
part of the interpreter. 

Macros are not necessary, strictly speaking. Macros clean up the
syntax of a program, in that it allows a programmer to write more
clean and brief code. For example, the expression

	(if (equal a b) () (print a))

could be written more concisely as

	(unless (equal a b) (print a))

if {unless} were defined. But it would have to be defined as a
macro, as when {unless} is called, the arguments should not 
be evaluated first. Unless can be defined as:

	(defmacro unless (predicate body) 
	  (if (eval predicate) 
	     nil 
	     (eval body) 
	) )    

This makes {unless} work, as the following interaction shows:

	In> (unless t (print 'SOMETHING))
	Out> nil
	In>  (unless nil (print 'SOMETHING))
	SOMETHING 
	Out> SOMETHING

Especially when code is generated, and does not have to be
human-readable, macros are not necessary. But they are a nice
feature nonetheless, and have to be implemented in the interpreter,
it can not be faked with normal {defun} functionality.

Examples involving {defun}:

	In> (defun foo (atom) (cons atom (list rest)))
	Out> foo
	In> (setf rest 'end)
	Out> end
	In> (foo a)
	Out> (a end )
	In> (foo b)
	Out> (b end )

In addition, nameless (pure) functions can be made, which work
exactly as their {defun}/{Defmacro} counterparts, as {lambda}
and {macro}:

*	0. {(lambda <arguments> <body>)} - define a pure unnamed function.
*	0. {(macro <arguments> <body>)} - define a pure unnamed macro.

Examples:

	In> (setf add '(lambda (x y) (+ x y)))
	Out> add
	In> (add 2 3)
	Out> 5

Note that pure functions, the {lambda} and {macro} expressions
described here, are not strictly necessary, if we have equivalents
for {defun} and {defmacro}. But pure unnamed functions do allow
for convenient notation, without clobbering up the global name
space. They also allow for locally defined functions. If they are 
required, they have to be part of the interpreter, since it cannot
be faked with {defun} and {defmacro}.

An interesting option is to not define the operations {defun}
and {defmacro}, but just {setf}, {lambda} and {macro}. This
set is just as powerful, and in fact allows you to create
{defun} and {defmacro} from them. We choose {defun} and {defmacro}
over the route of using {setf}, {lambda} and {macro} to define
{defun} and {defmacro} because {lambda} and {macro} are not
strictly required to build a CAS. When implementing a more
mature Lisp interpreter, it is wise to define {lambda} and {macro},
for the convenience of the programmer.

	    Creating and dissecting lists of expressions

Lists of expressions are used to build more elaborate structures.
The following commands are available for doing so:

To dissect a list:

*	0. {(first <list>)} - return the first element of a list
*	0. {(rest <list>)} - return the list with the first item removed.

Examples, taken from an interaction with {clisp}:

	In> (first '(a b c))
	Out> a
	In> (rest '(a b c))
	Out> (b c )

To reconstruct a list:

*	0. {(cons <first-expression> <rest-list>)} - {cons} returns a list
that has <first-expression> as its first element, and <rest-list> as the
rest of an expression.
*	0. {(list <...>)} - return a list with the <...> arguments evaluated.

Example taken from an interaction with {clisp}:

	In> (cons 'a '(b c))
	Out> (a b c )
	In> (list (+ 2 3) 4 3)
	Out> (5 4 3 )

One important function is {assoc}:

*	0. {(assoc <key> <assoc-list>)} - given an association list,
which is a list of (<key> <value>) pairs, return the first found pair 
for which the key matches the one given as first argument, or return 
{nil} if it wasn't found.

Examples:

*REM TODO missing setf to set up the list!!!

	In> (setf list '( ("name" "Peter") ("age" 28) ) )
	Out> list
	In> (assoc '"name" list)
	Out> ("name" "Peter" )
	In> (assoc '"age" list)
	Out> ("age" 28 )
	In> (assoc '"something" list)
	Out> nil

	    Predicates

Common Lisp has two special atoms, {t} and {nil}. {t}
stands for <i>true</i>, whereas {nil} stands for <i>false</i>.
{nil} is actually usually also the empty list. Typing an empty
list {()} is the same as typing {nil}:


	In> ()
	Out> nil
	In> nil
	Out> nil

In Common Lisp, {nil} is considered to mean <i>false</i> when 
considered as a boolean result from a list, and anything different
from {nil} is considered to mean <i>true</i>. This is then used 
as an efficient way to find items in lists. The result returned
can then either be a found result, or {nil} which means nothing
was found.

	In> (rest '(a b))
	Out> (b )
	In> (rest '(a))
	Out> nil

The author feels uneasy with having the {nil} atom overloaded
as both an empty list and <i>false</i> when used in predicates,
because it makes code harder take along to another language.
In some cases {nil} means an empty list, and in some cases
it means <i>false</i>, which complicates converting code,
due to the fact that the code has to be examined more closely
for this. {Yacas} has a distinct set of atoms, {True} and {False}
precisely for this reason. A test to see if something is an
empty list is still possible, by comparing the result of
evaluating an expression with an empty list. Indeed, Yacas is
not alone in this, Scheme (another dialect of Lisp) has different
symbols for <i>true</i> and <i>false</i>, {#t} and {#f} respectively.

Two predicates needed for operating on lists are then:

*	0. {(listp <expression>)} - {listp} returns {t} if <expression>
is a list, {nil} otherwise.
*	0. {atom <expression>} - {atom} returns {T} if the {expression}
passed in is an atom (a word).
*	0. (equal <expression-1> <expression-2>) - returns {t} if the
two expressions are the same, {nil} otherwise. Common Lisp has more
equality operators. They are more efficient for specific types of
comparisons. {equal} is the most generic form which works on all types
of input. As we are composing a minimum subset of functions to work
with in this part of this book, we will only mention {equal}.

Note the difference in {atom} and {listp}, which was taken from
Common Lisp. In Common Lisp predicates are supposed to be suffixed
by a 'p', but apparently not so with {atom}.

	    Variable scoping

*	0. {(let <assign-list> <expression>)} - Variables can be declared
locally in the function being called, using {Let}.

When {setf} is called, first the local variables are searched
for a candidate variable to set, and after that the global variables
are searched. When entering a function body, a local frame of local
variables for that function are defined, and the parameter variables
are bound to the arguments passed in to the function. {let} allows
the programmer to declare additional local variables. 

The following example sets up variables {n} and {m} and assigns them
values locally. {n} is bound to {a}, and {m} bound to {(b c)}.

	In> (let ( (n 'a) (m '(b c)) ) (cons n m))
	Out> (a b c )
	In> n
	ERROR: variable not defined : n
	Out> nil


The {expression} part in the {let} form gets evaluated after 
the local variables have been assigned. Note that evaluation of
the expressions in the {let} form are performed in the scope 
where the {let} form is called, thus expressions in the {let}
form can use local variables from its surroundings.

Local variables that are declared in a certain scope where the
variable already had a value mask the older declaration of the
variable.

Note: the values that will be assigned to the local variables are
evaluated <i>before</i> being assigned to the local variables.
So the expressions in the {assign-list} cannot refer to other variables
declared in the same {assign-list}. 

	    Execution control

No language is complete without conditional execution and looping.
*	0. {(if <predicate> <then-clause> <else-clause>)} - an if
statement: if {predicate} doesn't evaluate to {nil} return the 
result of evaluating the {then-clause} expression, otherwise
return the result of evaluating the {else-clause}.
*	0. {(while <predicate> <body>)} - this 
function evaluates {body} until {predicate} returns {nil} ({predicate}
is called before each iteration), and the result of the last
evaluation of {body} is returned afterwards.
*	0. {(cond (<pred-1> <body-1>) ... (<pred-n> <body-n>))} - 
similar to {cond} in Lisp: the items are traversed one at a time, from
front to end, evaluating the predicates. if one does not evaluate 
to {nil}, its {body} is evaluated, and the result of evaluating returned.
*	0. {(progn <body-1> ... <body-n>)} - evaluate multiple 
expressions, and return the result of evaluating the last expression,
{body-n}.

This concludes the a set of functions required for building up a 
computer algebra system. It is not a minimal set by any means, 
as a following section will show; {if} can be defined by using
{defmacro} and {cond}, for instance.

The next section will first introduce arbitrary number arithmetic
support. It is not strictly necessary for the interpreter to work
and be able to do anything, but it is the first concession we will
make towards efficiency, as it is rather hard to find an algorithm
that does not need arithmetic. 

The next sections after that will continue by introducing a few
building blocks that are needed to implement a CAS like Yacas.

		Arbitrary precision arithmetic

Before proceeding to build up a full system, we first introduce
the arithmetic to the system. Arithmetic could theoretically 
be performed by using what we already have (lists of objects,
where the number of objects in the list represents the number), 
but it would be impractical. 

We start with the representation of numbers. This section will
only refer to arbitrary precision integers, floating point numbers
will come later. The implementation of the Lisp dialect described here 
is designed to be easily extended that way.

Numbers are represented as atoms, sequences of characters. More 
specifically, they can be a sequence of digits from {0} to {9}
(we will work in the decimal number system here, as that is what
most humans are used to). Negative integers have a minus sign in
front of them. So, {1234} and {-1234} are atoms representing 
the integers 1234 and -1234 respectively. 

The most basic arithmetic operations are then addition and negating
a number:

	In> (+ 1 2 3)
	Out> 6
	In> (- 5)
	Out> -5
	In> (+ 2 (- 3))
	Out> -1

Together with a predicate to determine that something is an
integer ({integerp}), and an ordering operator <i>less than</i>
denoted {<}, other arithmetic operations like multiplication,
division, exponentiation etcetera can be built.

Some examples using {<} and {integerp}.

	In> (integerp 4)
	Out> t
	In> (integerp -4)
	Out> t
	In> (integerp 'a)
	Out> nil
	In> Out> (a b c )
	In> (integerp '(a b c))
	Out> nil
	In> (< 2 3)  
	Out> t
	In> (< 3 2)
	Out> nil

Note that a computer algebra system requires arbitrary precision
arithmetic, as for certain algorithms the intermediate results
of a calculation can become big, even if the final result is
small. So, a CAS should be able to do the following:

	In> (+ 12345678901234567890999999999999999999 1)
	Out> 12345678901234567891000000000000000000

		A few useful macros and functions

Now we are ready to create more powerful building blocks using the
primitive set of functions introduced in previous sections.

The routines developed here will be built from the primitive
building blocks described before. However, an implementation
is free to implement these hard-coded in the core kernel for
speed. This is advisable because the constructs developed here
will be used often, and so there is a need for efficiency.

Note that the functions introduced so far are not minimal. 
Some can be defined in terms of others. They are defined here
because they are easy to define in an interpreter without making
the interpreter much larger, but are used often, so efficiency
is required.
For instance, given the {cond} and {defmacro} operations, it is
possible to define an {if} operation:

	In> (defmacro Newif
	          (pred then else)
	          (cond
	             ( (eval pred) (eval then) )
	             ( t           (eval else) )
	        ) )
	Out> Newif
	In> (Newif (equal 'a 'b) 'c 'd)
	Out> d
	In> (Newif (equal 'a 'a) 'c 'd)
	Out> c
	In> (if (equal 'a 'b) 'c 'd)
	Out> d
	In> (if (equal 'a 'a) 'c 'd)
	Out> c

Now let us start by building a set of new primitives using
the ones introduced so far. We start by defining {Null}, which
returns True if its argument is an empty list:


	In> (defun null (expr) (equal expr nil) )
	Out> null
	In> (null 'a)
	Out> nil
	In> (null ())
	Out> t
	In> (null nil)
	Out> t


With this, we can define a {Length} function which returns the
length of a list:

	In> (defun length (list)
	  (if (null list)
	    0
	    (+ 1 (length (rest list)))
	) )
	Out> length
	In> (length '(a b c))
	Out> 3
	In> (length ())
	Out> 0

In addition to the already defined function {first}, we can define 
the functions {second}, {third}, etcetera to print code
that is easier to read:

	In> (defun second (list) (first (rest list) ) )
	Out> second
	In> (defun third  (list) (first (rest (rest list) ) ) )
	Out> third
	In> (setf lst '(a b c))
	Out> lst
	In> (first lst)
	Out> a
	In> (second lst)
	Out> b
	In> (third lst)
	Out> c

and with this we can start to print functions for boolean expressions.
First, let us define a {not} operator, which returns True if its
argument is {nil}:

	In> (defmacro not (a)  (null (eval a) ) )
	Out> not
	In> (not 'a)
	Out> nil
	In> (not nil)
	Out> t

Then <i>lazy</i> {and} and <i>lazy</i> {or} operations can be defined:

	In> (defmacro and (a b) (if (eval a) (eval b) nil) )
	Out> and
	In> (defmacro or  (a b) (if (eval a) t (eval b) ) )      
	Out> or

These evaluate their first argument first, and decide to evaluate the
second only if the first one does not give enough information to
decide whether to stop. For instance, if the first argument to {and}
returns <i>false</i> (eg. {nil}), then the result of evaluating the entire 
expression should be {nil}, otherwise it returns the result of evaluating
the second argument. {or} works the other way round: it evaluates the
second argument if the result of evaluating the first argument was
{nil}.

Lazy and and or operators can be used to combine predicates into
a larger predicate, but also to guard evaluation of an expression,
let it only evaluate an expression if a pre-condition is met.
The {unless} operation could equally well have been defined 
by using {or}:

	In> (defmacro unless (predicate body) 
	  (or (eval predicate) (eval body) ) )    
	Out> unless
	In> (unless t (print 'SOMETHING))
	Out> nil
	In> (unless nil (print 'SOMETHING))<commit_msg>Scary: we just lost Serge's changes to this document, so I patched it by hand from the emailed diff file.<commit_after>
			A brief introduction to Lisp

		Introduction

Yacas owes much of its current form to Lisp. A lot of ideas from
Lisp have been taken over into the Yacas interpreter. This book
aims to describe this connection, to show how Yacas compares
to other {Lisp} dialects ({Yacas} can be viewed as a dialect
of Lisp), and how the {Yacas} interpreter is related to Lisp.

Viewed from the top level, {Yacas} is just one function; {Yacas} is 
called with one, or possibly two arguments, or from a different point 
of view, a request is made to the {Yacas} system. How the function 
performs the action is implementation-dependent, but at the top-level
it can be viewed as one call. From c++ or Java, it might look like 

	yacas.Evaluate("expression");

Or from Lisp,

	(yacas expression environment)

The {environment} argument is optional; it can be a global resource 
that doesn't have to be passed in.

For instance, taking the derivative of a function could look like

	yacas.evaluate("D(x)Sin(x);");

when in c++, or 

	(yacas '(D x (sin x)) )

when in Lisp. The quote in Lisp makes it clear that the argument, 
the parameter to the request, is actually data, and not program. 
This is an important distinction which has to be made clear in 
Lisp, but is clearer in other environments, due to the form of data being
distinct from the form of program.

To drive home this point, {(* a 1)} would raise an error when given 
to the Lisp {eval} function if the variable {a} is not bound to a 
value, but would be perfectly valid data when passed to a CAS. In 
fact, one would like it to return {a} in this case. The {*}
operator is actually a function call when invoked from Lisp ( {(* a 1)} 
is a <i>program</i>), but is data when passed to a CAS.

One can conclude that {Yacas}, an engine for simplifying symbolic 
expressions and performing calculations, is just one huge function 
that performs that task, and has one entry point, a function call 
with one argument as the data to the request.

This section will first introduce the reader to the basic concepts 
of Lisp, and then proceed to show how the {yacas} function can be 
implemented in Lisp in general. Clearness of concepts explained will 
be favoured over efficiency and performance. A small subset of Lisp 
will be used, so it should be easy to take the code along to various 
different Lisp dialects, or to write a little Lisp implementation to 
implement the {yacas} function.

The first chapter briefly describes a small Lisp dialect. A small subset 
of what is usually found in the average Lisp interpreter is described. 
The Lisp dialect is different in small subtle ways from normal
Lisp implementations. Simplicity is put first. 

For the Lisp dialect presented, one was chosen that is different
from the Lisp dialect that represents {Yacas}. This separation
is done explicitly, on purpose, to facilitate implementation of
execution of algorithms written out in {Yacas} syntax from 
any other language. All the {Yacas}-specific details have to
be handled by the routine performing these algorithms, independent
of language constructs that might support it. 

Even though in Lisp program and data look the same, for {Yacas}
they are distinctly different in that data will likely not 
be evaluated by the default evaluator. It is important to keep
the distinction between data and program. 


		A little history of Lisp

Lisp is one of the older computer programming languages in existence.
It came from a mathematical background, lambda calculus, and is
used even now. Arguably, most programming languages owe a lot
to Lisp.

There are various sources on the internet describing the early history
of Lisp.

*REM should we put up a list here? Or have our own short history? Mention
*REM McCarthy etcetera?

		The Lisp interactive command line interface

When Lisp is started, the user is generally greeted with a prompt.
The Lisp interpreter is in its {read-eval-print} loop; it reads
in an expression typed in by the user, evaluates it, and prints
the result of evaluation to the console. 

The definition of an expression can be given such; 

*	0. an expression is either an atom, or a list of expressions. 
*	0. an atom is a word, a list of characters.

So, the words {foo} and {bar} could be called atoms. A list is 
represented by writing the expressions in the list out with
spaces in between them, and brackets around them. So, {(foo bar)}
would be a list with two elements, {foo} and {bar}.

In Lisp, each expression can evaluate to a value (if no error occurred).
When evaluating an atom, the atom can either be a 'special' atom
that evaluates to itself, or otherwise a lexical word that refers
to a variable. When it is a variable, the Lisp system looks up its
value, and returns the value the variable is bound to, in what
is called the 'environment' the Lisp interpreter is evaluating in.
When a variable is not bound, an error is raised. 
The noted difference with the usual Lisp
dialects is that a normal Lisp system raises an error when an expression 
tries to evaluate a variable that is not bound to a value, whereas
in a CAS, the variable is a free parameter in some expression.

When a list of expressions is encountered, the first element in
the list is a function that should be called, and the rest of the
expressions in the list are the arguments. The interpreter handles
the list by first evaluating the arguments (the rest of the list),
and then calling the function with the evaluated arguments as parameters
to the function. There are exceptions to this; the function {quote}
returns its argument unevaluated. In stead of writing 
{(quote <expression>)}, a common short-hand is {'<expression>},
eg. the expression with a quote in front of it. Quotes are used
a lot, to tell the system that data is being passed in.

For the following example interaction, the following commands
are used: 
*	{quote} - {quote} takes one argument and returns it unevaluated
*	{eval}  - {eval}  takes one argument, which is evaluated before
{eval} is called, and then {eval} evaluates it again. {eval} can be used
to oppose {quote}.
*	{setf} - {setf} takes two arguments, the first a name of a variable,
the second an expression to be evaluated. The result of evaluating the second
argument is assigned to the variable.

The following is an interaction with our little lisp dialect. In the 
usual Lisp dialects, when variables are unbound, an error is raised.

	In> a
	Error, variable has no value : a

Lisp dialects are usually case-insensitive (the atom {a} is the same as {A}).

Here the atom {a} evaluated to itself, because it was not assigned.

	In> (setf a '(this is a list))
	Out> (this is a list )
	In> a
	Out> (this is a list )

Here we assigned the value {(this is a list)} to the variable {a},
and {a} now evaluates to that list. The system looked up the value
bound to the variable {a} without re-evaluating it.

*REM TODO@@@

	In> 'a
	Out> a
	In> (eval a)
	ERROR: function not defined : this
	Out> nil

With {quote} we can withhold evaluating a, and with {eval}
we can re-evaluate {a}. Since {this} is not a defined function
in this case, an error is raised.

Note that evaluation as defined in Lisp dialects is less suitable for 
CAS systems. A CAS would return expressions unevaluated,
which is what you want in a CAS. It then represents some function
which has not been specified yet. In a Lisp intepreter, it is nice
to have the interpreter raise an error, but in a CAS, where it
is data, it should not be simplified further.

For atoms that refer to variables that are not yet bound, the variables
should be returned unevaluated by default, and functions that are 
called but not defined should be returned as the same function but with their 
arguments evaluated. evaluation as defined in most Lisp dialects is not suited
to simplifying expressions. Later in this book an evaluator will
be developed in Lisp itself that is closer to a sense of 'simplification'
required for CAS.

Sometimes the user wants to refer to a function without having to define it, 
because transformation rules for the function can be given without explaining
explicitly how to go about evaluating the function. Certain functions
have properties, and sometimes it is easier to work with the properties
than to evaluate them explicitly.

For the rest of this book, it is assumed that the 
semi-colon, {;}, means that the rest of the input line
up to the end of line or end of file is a human readable comment, 
not to be executed.

		A basic set of Lisp primitive commands

Surprisingly few Lisp functions are needed to be able to implement
any algorithm in Lisp. Languages are usually referred to as being
<i>Turing complete</i> if any algorithm can be implemented in them.
Turing showed that a small apparatus, called a Turing machine,
was universal in that theoretically any algorithm could be implemented
in it. The way to show a language is Turing complete is to implement
a Turing machine in that language. if that is done, that language
can execute any algorithm, as a Turing machine can be implemented in
it, and Turing machines can execute any algorithm.

Note that building a Turing machine is just a theoretical exercise.
Turing machines don't concern themselves with efficiency. Algorithms
can be run, in finite time, but it will most certainly not be the
most efficient way to execute the algorithm on a real computer.

Methods to make execution more efficient break down in two steps:

*	0. encapsulating a specific algorithm in a function call, and
make define an efficient implementation of the function in the enviroment
the Lisp interpreter is executing in
*	0. writing a compiler that converts algorithms stated in 
Lisp code to a version that is more efficient, more close to the
hardware the program is running on

This section describes a minimum set of Lisp primitives needed 
for building a Turing machine, theoretically. After that, first
numeric operations are introduced, before implementing a Turing 
machine. Fundamentally, the language does not need to support 
arithmetic in order to be able to implement any algorithm, as other
constructs using lists can be used to represent and work with numbers,
but not implementing it does make the effort rather complex.

The following sections will describe the following minimal 
set of commands; 
*	0. macro-like commands {quote}, {if}, {cond}, {setf}, {while}, {progn}, {eval}, {defun} and {defmacro}.
*	0. function-like commands {assoc}, {first}, {rest}, {cons}, {atom}, {listp}, {list}, {equal}, {+}, {integerp}, {-} and {<}.

In the next sections, whenever a function call is explained,
the arguments to the function will be delimited by {<} and {>}.
Arguments are evaluated unless stated otherwise.

	    Naming conventions

The set of primitives described in this section are meant to be
used as building blocks for building a final bigger system.

	    Controlling evaluation

To control whether evaluation is performed, the following 
commands are available:

*	0. {(quote <expression>)} - as described in the introduction above, {quote}
takes one argument, and returns it unevaluated. 
*	0. {(eval <expression>)} - {eval} also takes one argument, and evaluates
it when {eval} is called. When {eval} is called, its argument was
evaluated already.

	    Assigning variables and functions

In addition, functions and macros can be defined:
*	0. {(setf <variable> <expression>)} - to assign a variable, {setf} can be used.
the {variable} argument is not evaluated before {setf} is called,
but {expression} is.
*	0. {(defun <function-name> <argument-list> <expression>)} - define a function
whose name is {function-name}, and a list of arguments {argument-list}.
This function can then be called from anywhere. Its arguments are first 
evaluated, and a set of local variables (listed in the {argument-list} argument) 
are reserved, and bound to the values passed in.
*	0. {(defmacro <macro-name> <argument-list> <expression>)} - does the
same as {defun}, but with the arguments not evaluated before evaluating the
body {expression}. Also, the {expression} is evaluated from within the
calling scope, so the {expression} can use variables from its calling
environment. A better way to look at macros is as if they were copy-pasted
into the place where they were called.

The default set of functions implemented in the core of a Lisp 
interpreter can be divided between function-like and macro-like
functions, in that when a function-like (defun) function is called,
its arguments are evaluated first. Examples of this are {cons},
{first} and {rest}. 

When calling macro-like (defmacro) functions, however, the arguments
are not evaluated first, and the variables defined in the calling
environment are visible while expressions using arguments on the
command line are evaluated. A macro can be viewed as a bit of
code that got pasted in to the place where it got called, by the 
interpreter (in fact, this is what a compiler can do).

The {defmacro} function allows the programmer to expand the language
by adding functions that act as if they were defined in the core
part of the interpreter. 

Macros are not necessary, strictly speaking. Macros clean up the
syntax of a program, in that it allows a programmer to write more
clean and brief code. For example, the expression

	(if (equal a b) () (print a))

could be written more concisely as

	(unless (equal a b) (print a))

if {unless} were defined. But it would have to be defined as a
macro, as when {unless} is called, the arguments should not 
be evaluated first. Unless can be defined as:

	(defmacro unless (predicate body) 
	  (if (eval predicate) 
	     nil 
	     (eval body) 
	) )    

This makes {unless} work, as the following interaction shows:

	In> (unless t (print 'SOMETHING))
	Out> nil
	In>  (unless nil (print 'SOMETHING))
	SOMETHING 
	Out> SOMETHING

Especially when code is generated, and does not have to be
human-readable, macros are not necessary. But they are a nice
feature nonetheless, and have to be implemented in the interpreter,
it can not be faked with normal {defun} functionality.

Examples involving {defun}:

	In> (defun foo (atom) (cons atom (list rest)))
	Out> foo
	In> (setf rest 'end)
	Out> end
	In> (foo a)
	Out> (a end )
	In> (foo b)
	Out> (b end )

In addition, nameless (pure) functions can be made, which work
exactly as their {defun}/{Defmacro} counterparts, as {lambda}
and {macro}:

*	0. {(lambda <arguments> <body>)} - define a pure unnamed function.
*	0. {(macro <arguments> <body>)} - define a pure unnamed macro.

Examples:

	In> (setf add '(lambda (x y) (+ x y)))
	Out> add
	In> (add 2 3)
	Out> 5

Note that pure functions, the {lambda} and {macro} expressions
described here, are not strictly necessary, if we have equivalents
for {defun} and {defmacro}. But pure unnamed functions do allow
for convenient notation, without clobbering up the global name
space. They also allow for locally defined functions. If they are 
required, they have to be part of the interpreter, since it cannot
be faked with {defun} and {defmacro}.

An interesting option is to not define the operations {defun}
and {defmacro}, but just {setf}, {lambda} and {macro}. This
set is just as powerful, and in fact allows you to create
{defun} and {defmacro} from them. We choose {defun} and {defmacro}
over the route of using {setf}, {lambda} and {macro} to define
{defun} and {defmacro} because {lambda} and {macro} are not
strictly required to build a CAS. When implementing a more
mature Lisp interpreter, it is wise to define {lambda} and {macro},
for the convenience of the programmer.

	    Creating and disseminating lists of expressions

Lists of expressions are used to build more elaborate structures.
The following commands are available for doing so:

To disseminate a list:

*	0. {(first <list>)} - return the first element of a list
*	0. {(rest <list>)} - return the list with the first item removed.

Examples, taken from an interaction with {clisp}:

	In> (first '(a b c))
	Out> a
	In> (rest '(a b c))
	Out> (b c )

To reconstruct a list:

*	0. {(cons <first-expression> <rest-list>)} - {cons} returns a list
that has <first-expression> as its first element, and <rest-list> as the
rest of an expression.
*	0. {(list <...>)} - return a list with the <...> arguments evaluated.

Example taken from an interaction with {clisp}:

	In> (cons 'a '(b c))
	Out> (a b c )
	In> (list (+ 2 3) 4 3)
	Out> (5 4 3 )

One important function is {assoc}:

*	0. {(assoc <key> <assoc-list>)} - given an association list,
which is a list of (<key> <value>) pairs, return the first found pair 
for which the key matches the one given as first argument, or return 
{nil} if it wasn't found.

Examples:

*REM TODO missing setf to set up the list!!!

	In> (setf list '( ("name" "Peter") ("age" 28) ) )
	Out> list
	In> (assoc '"name" list)
	Out> ("name" "Peter" )
	In> (assoc '"age" list)
	Out> ("age" 28 )
	In> (assoc '"something" list)
	Out> nil

	    Predicates

Common Lisp has two special atoms, {t} and {nil}. {t}
stands for <i>true</i>, whereas {nil} stands for <i>false</i>.
{nil} is actually usually also the empty list. Typing an empty
list {()} is the same as typing {nil}:


	In> ()
	Out> nil
	In> nil
	Out> nil

In Common Lisp, {nil} is considered to mean <i>false</i> when 
considered as a boolean result from a list, and anything different
from {nil} is considered to mean <i>true</i>. This is then used 
as an efficient way to find items in lists. The result returned
can then either be a found result, or {nil} which means nothing
was found.

	In> (rest '(a b))
	Out> (b )
	In> (rest '(a))
	Out> nil

The author feels uneasy with having the {nil} atom overloaded
as both an empty list and <i>false</i> when used in predicates,
because it makes code harder take along to another language.
In some cases {nil} means an empty list, and in some cases
it means <i>false</i>, which complicates converting code,
due to the fact that the code has to be examined more closely
for this. {Yacas} has a distinct set of atoms, {True} and {False}
precisely for this reason. A test to see if something is an
empty list is still possible, by comparing the result of
evaluating an expression with an empty list. Indeed, Yacas is
not alone in this, Scheme (another dialect of Lisp) has different
symbols for <i>true</i> and <i>false</i>, {#t} and {#f} respectively.

Two predicates needed for operating on lists are then:

*	0. {(listp <expression>)} - {listp} returns {t} if <expression>
is a list, {nil} otherwise.
*	0. {atom <expression>} - {atom} returns {T} if the {expression}
passed in is an atom (a word).
*	0. (equal <expression-1> <expression-2>) - returns {t} if the
two expressions are the same, {nil} otherwise. Common Lisp has more
equality operators. They are more efficient for specific types of
comparisons. {equal} is the most generic form which works on all types
of input. As we are composing a minimum subset of functions to work
with in this part of this book, we will only mention {equal}.

Note the difference in {atom} and {listp}, which was taken from
Common Lisp. In Common Lisp predicates are supposed to be suffixed
by a 'p', but apparently not so with {atom}.

	    Variable scoping

*	0. {(let <assign-list> <expression>)} - Variables can be declared
locally in the function being called, using {Let}.

When {setf} is called, first the local variables are searched
for a candidate variable to set, and after that the global variables
are searched. When entering a function body, a local frame of local
variables for that function are defined, and the parameter variables
are bound to the arguments passed in to the function. {let} allows
the programmer to declare additional local variables. 

The following example sets up variables {n} and {m} and assigns them
values locally. {n} is bound to {a}, and {m} bound to {(b c)}.

	In> (let ( (n 'a) (m '(b c)) ) (cons n m))
	Out> (a b c )
	In> n
	ERROR: variable not defined : n
	Out> nil


The {expression} part in the {let} form gets evaluated after 
the local variables have been assigned. Note that evaluation of
the expressions in the {let} form are performed in the scope 
where the {let} form is called, thus expressions in the {let}
form can use local variables from its surroundings.

Local variables that are declared in a certain scope where the
variable already had a value mask the older declaration of the
variable.

Note: the values that will be assigned to the local variables are
evaluated <i>before</i> being assigned to the local variables.
So the expressions in the {assign-list} cannot refer to other variables
declared in the same {assign-list}. 

	    Execution control

No language is complete without conditional execution and looping.
*	0. {(if <predicate> <then-clause> <else-clause>)} - an if
statement: if {predicate} doesn't evaluate to {nil} return the 
result of evaluating the {then-clause} expression, otherwise
return the result of evaluating the {else-clause}.
*	0. {(while <predicate> <body>)} - this 
function evaluates {body} until {predicate} returns {nil} ({predicate}
is called before each iteration), and the result of the last
evaluation of {body} is returned afterwards.
*	0. {(cond (<pred-1> <body-1>) ... (<pred-n> <body-n>))} - 
similar to {cond} in Lisp: the items are traversed one at a time, from
front to end, evaluating the predicates. if one does not evaluate 
to {nil}, its {body} is evaluated, and the result of evaluating returned.
*	0. {(progn <body-1> ... <body-n>)} - evaluate multiple 
expressions, and return the result of evaluating the last expression,
{body-n}.

This concludes the a set of functions required for building up a 
computer algebra system. It is not a minimal set by any means, 
as a following section will show; {if} can be defined by using
{defmacro} and {cond}, for instance.

The next section will first introduce arbitrary number arithmetic
support. It is not strictly necessary for the interpreter to work
and be able to do anything, but it is the first concession we will
make towards efficiency, as it is rather hard to find an algorithm
that does not need arithmetic. 

The next sections after that will continue by introducing a few
building blocks that are needed to implement a CAS like Yacas.

		Arbitrary precision arithmetic

Before proceeding to build up a full system, we first introduce
the arithmetic to the system. Arithmetic could theoretically 
be performed by using what we already have (lists of objects,
where the number of objects in the list represents the number), 
but it would be impractical. 

We start with the representation of numbers. This section will
only refer to arbitrary precision integers, floating point numbers
will come later. The implementation of the Lisp dialect described here 
is designed to be easily extended that way.

Numbers are represented as atoms, sequences of characters. More 
specifically, they can be a sequence of digits from {0} to {9}
(we will work in the decimal number system here, as that is what
most humans are used to). Negative integers have a minus sign in
front of them. So, {1234} and {-1234} are atoms representing 
the integers 1234 and -1234 respectively. 

The most basic arithmetic operations are then addition and negating
a number:

	In> (+ 1 2 3)
	Out> 6
	In> (- 5)
	Out> -5
	In> (+ 2 (- 3))
	Out> -1

Together with a predicate to determine that something is an
integer ({integerp}), and an ordering operator <i>less than</i>
denoted {<}, other arithmetic operations like multiplication,
division, exponentiation etcetera can be built.

Some examples using {<} and {integerp}.

	In> (integerp 4)
	Out> t
	In> (integerp -4)
	Out> t
	In> (integerp 'a)
	Out> nil
	In> Out> (a b c )
	In> (integerp '(a b c))
	Out> nil
	In> (< 2 3)  
	Out> t
	In> (< 3 2)
	Out> nil

Note that a computer algebra system requires arbitrary precision
arithmetic, as for certain algorithms the intermediate results
of a calculation can become big, even if the final result is
small. So, a CAS should be able to do the following:

	In> (+ 12345678901234567890999999999999999999 1)
	Out> 12345678901234567891000000000000000000

		A few useful macros and functions

Now we are ready to create more powerful building blocks using the
primitive set of functions introduced in previous sections.

The routines developed here will be built from the primitive
building blocks described before. However, an implementation
is free to implement these hard-coded in the core kernel for
speed. This is advisable because the constructs developed here
will be used often, and so there is a need for efficiency.

Note that the functions introduced so far are not minimal. 
Some can be defined in terms of others. They are defined here
because they are easy to define in an interpreter without making
the interpreter much larger, but are used often, so efficiency
is required.
For instance, given the {cond} and {defmacro} operations, it is
possible to define an {if} operation:

	In> (defmacro Newif
	          (pred then else)
	          (cond
	             ( (eval pred) (eval then) )
	             ( t           (eval else) )
	        ) )
	Out> Newif
	In> (Newif (equal 'a 'b) 'c 'd)
	Out> d
	In> (Newif (equal 'a 'a) 'c 'd)
	Out> c
	In> (if (equal 'a 'b) 'c 'd)
	Out> d
	In> (if (equal 'a 'a) 'c 'd)
	Out> c

Now let us start by building a set of new primitives using
the ones introduced so far. We start by defining {Null}, which
returns True if its argument is an empty list:


	In> (defun null (expr) (equal expr nil) )
	Out> null
	In> (null 'a)
	Out> nil
	In> (null ())
	Out> t
	In> (null nil)
	Out> t


With this, we can define a {Length} function which returns the
length of a list:

	In> (defun length (list)
	  (if (null list)
	    0
	    (+ 1 (length (rest list)))
	) )
	Out> length
	In> (length '(a b c))
	Out> 3
	In> (length ())
	Out> 0

In addition to the already defined function {first}, we can define 
the functions {second}, {third}, etcetera to print code
that is easier to read:

	In> (defun second (list) (first (rest list) ) )
	Out> second
	In> (defun third  (list) (first (rest (rest list) ) ) )
	Out> third
	In> (setf lst '(a b c))
	Out> lst
	In> (first lst)
	Out> a
	In> (second lst)
	Out> b
	In> (third lst)
	Out> c

and with this we can start to print functions for boolean expressions.
First, let us define a {not} operator, which returns True if its
argument is {nil}:

	In> (defmacro not (a)  (null (eval a) ) )
	Out> not
	In> (not 'a)
	Out> nil
	In> (not nil)
	Out> t

Then <i>lazy and </i> and <i>lazy or</i> operations can be defined:

	In> (defmacro and (a b) (if (eval a) (eval b) nil) )
	Out> and
	In> (defmacro or  (a b) (if (eval a) t (eval b) ) )      
	Out> or

These evaluate their first argument first, and decide to evaluate the
second only if the first one does not give enough information to
decide whether to stop. For instance, if the first argument to {and}
returns <i>false</i> (eg. {nil}), then the result of evaluating the entire 
expression should be {nil}, otherwise it returns the result of evaluating
the second argument. {or} works the other way round: it evaluates the
second argument if the result of evaluating the first argument was
{nil}.

Lazy and and or operators can be used to combine predicates into
a larger predicate, but also to guard evaluation of an expression,
let it only evaluate an expression if a pre-condition is met.
The {unless} operation could equally well have been defined 
by using {or}:

	In> (defmacro unless (predicate body) 
	  (or (eval predicate) (eval body) ) )    
	Out> unless
	In> (unless t (print 'SOMETHING))
	Out> nil
	In> (unless nil (print 'SOMETHING))
{'fraction_non_alphanumeric': 0.06965299684542586, 'fraction_numerical': 0.005804416403785489, 'mean_word_length': 4.0290998096274135, 'pattern_counts': {'":': 0, '<': 167, '<?xml version=': 0, '>': 409, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 4, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4723442', 'n_tokens_mistral': 16139, 'n_tokens_neox': 15264, 'n_words': 9026}