# 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 program), 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.

Of course this is a bit of an oversimplification. We are not just interested in evaluating and simplifying expressions. When Yacas is embedded inside an application that offers a user interface, one would want to have access to all the operations allowed, and their arguments. Furthermore, for a debugger, information about the internal state of the interpreter is needed (values of global variables, etc.).

At the end of the day we want to arrive at a language where we can implement an algorithm in a few lines of code, and have the compiler generate efficient code for it.

Given the strong typed Lisp we are using here, how is it different from using c++/Java directly?

The difference is in the syntax. Algorithms for manipulating symbolic expressions are written down much more naturally in a language that supports these operations natively. The code to perform symbolic manipulation operations can look surprisingly complex when written in c++ or Java. Later on, a compiler for the Lisp dialect developed here that will try to compile to human-readable source code will be described. Although the results are somewhat readable, they are a lot less readable than the original Lisp or Yacas script code they were generated from.

Convenient notation aids the programmer greatly in thinking about a problem. It is not unusual in mathematics to devise a new notation scheme to make life easier. For example, the bra ket notation, where `<a|b>` stands for the inproduct defined as

    Integrate()a*b

has the added advantage of being able to write down projection operators of the form `|b><a|` which would be a lot more cumbersome to deal with without this notation.

Flexibility is not lost in a strong typed system; one can define a type `EXPRESSION`, which (naturally) represents an expression that can be manipulated. This could even be the default type for variables for which types are not specified, to make life easier for the programmer. This is not advisable, though, as the section describing the compiler will make clear.

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 favored 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.

##

Why choose Lisp over other languages?

Lisp has some powerful options not available in for instance c++/Java. The syntax is closer to the way a human thinks about transforming expressions, and the resulting routines are thus shorter and easier to read. The same routine, when written out in Lisp or in c++, is much more readable and natural in Lisp than in c++, for instance. c++ syntax is made for other purposes.

Also, the typed Lisp dialect developed in this book is easily translated to other languages. This removes the argument of Lisp being less efficient; the code can be converted to efficient c++/Java code. What is more, the code is easy to parse and transform into these languages, giving a language-independent specification of algorithms.

##

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.

##

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;

- an expression is either an atom, or a list of expressions.
- 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.

    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 Turing complete 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:

- encapsulating a specific algorithm in a function call, and make define an efficient implementation of the function in the environment the Lisp interpreter is executing in
- 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;

- macro-like commands `quote`, `if`, `cond`, `setf`, `while`, `progn`, `eval`, `defun` and `defmacro`.
- 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:

- `(quote <expression>)` - as described in the introduction above, `quote` takes one argument, and returns it unevaluated.
- `(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:

- `(setf <variable> <expression>)` - to assign a variable, `setf` can be used. the `variable` argument is not evaluated before `setf` is called, but `expression` is.
- `(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.
- `(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 predicate nil 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`:

- `(lambda <arguments> <body>)` - define a pure unnamed function.
- `(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:

- `(first <list>)` - return the first element of a list
- `(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:

- `(cons <first-expression> <rest-list>)` - `cons` returns a list that has as its first element, and as the rest of an expression.
- `(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`:

- `(assoc <key> <assoc-list>)` - given an association list, which is a list of ( ) 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:

    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 true, whereas `nil` stands for false. `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 false when considered as a boolean result from a list, and anything different from `nil` is considered to mean true. 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 false 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 false, 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 true and false, `#t` and `#f` respectively.

Two predicates needed for operating on lists are then:

- `(listp <expression>)` - `listp` returns `t` if is a list, `nil` otherwise.
- `atom <expression>` - `atom` returns `T` if the `expression` passed in is an atom (a word).
- (equal ) - 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

- `(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 before 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.

- `(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`.
- `(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.
- `(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.
- `(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 less than denoted `<`, other arithmetic operations like multiplication, division, exponentiation etc. 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
                 ( pred then)
                 ( t    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`, etc. 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 a) )
    Out> not
    In> (not 'a)
    Out> nil
    In> (not nil)
    Out> t

Then lazy and and lazy or operations can be defined:

    In> (defmacro and (a b) (if a b nil))
    Out> and
    In> (defmacro or  (a b) (if a t 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 false (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 predicate body) )
    Out> unless
    In> (unless t (print 'SOMETHING))
    Out> nil
    In> (unless nil (print 'SOMETHING))
    SOMETHING
    Out> SOMETHING

Most of these functions are convenience functions. They make code easier to read. Macros in effect allow you to extend the language.

##

A reality check: implementing more functions in the interpreter for efficiency

Even though new functions can be created in Lisp code rather than the interpreter, it is not necessarily a good idea to do so. For instance, declaring additional local variables can be done with `defmacro` (and in this case `macro` would also be necessary). However, it is used a lot in Lisp code, so it makes sense to write an efficient version in the interpreter itself. This section describes a few commands that, although not strictly necessary, should be implemented in the interpreter for efficiency of execution.

The reasons for adding these functions fall into the following categories:

- routines that make for easy debugging (example: `print`).
- routines that can be implemented a lot more efficiently in the interpreter than using the base Lisp commands (example: `let`).
- routines that are already implemented in the interpreter any way (examples: `second`, `third`, `null`, `eq`). It is a pity if these were not used while they are already implemented efficiently and available.
- commands related to user interfacing. An example is `exit`, which is not strictly needed, but facilitates quitting the command line version of the interpreter. These should be implemented in the code that is only used in the console version. `exit` makes less sense in a graphical user interface, where stopping the application is likely to be performed in different ways. `exit` is not strictly a function needed for CAS.

The commands described here can be implemented in the interpreter, but they are not strictly necessary, or they can be implemented in Lisp code using more basic primitives.

- `(let ( (<var-1> <val-1>) ... (<var-n> <val-n>) ) <body>)` - evaluate the values `val-1` through and declare new local variables and then assign the values to the new local variables. Note that the values are evaluated before assigning them to the variables, so the variables can not depend on each other.