The form is understood as such symbolical expression which value can be found by the interpreter. Earlier already used the most simple forms of language: constants, variable, ljambda-calls, calls of functions and their combination. Except them some special forms, such as ** ' ** and ** setq**, treating arguments differently, than usual functions have been examined. Ljambda-expression without actual parametres is not the form.

Computable expressions can be divided into three groups:

- Self-certain forms. These forms, like constants, are the objects representing only. These are such forms, as numbers and special constants
**true**,**false**and**nil**, and also signs and strings. - Symbols which are used as variables.
- Forms in the form of list structure which are:
- Calls of functions and ljambda-calls.
- Special forms into which enter
**setq**,**'**and many forms described in this chapter intended for handle by calculation and a context. - Macrocalls (will be examined later).

In widespread procedural languages along with the basic actions there are special operating mechanisms of a branching of calculations and the organisation of cycles. In Pascal structures ** if then else**, ** while do**, ** case ** and others, for example, are used.

Operating structures of a Lisp (for them we will use the term the offer) look outwardly as calls of functions. Offers will register in a kind parenthesis the expressions which second element operates as a name of operating structure, and other elements - as "arguments". Result of calculation just as at function, value is, i.e. operating structures represent forms. However offers are not calls of functions, and different offers use arguments differently.

The most important from the point of view of programming can be divided syntactic forms on the basis of their use into following groups

**Work with a context:**- -
**'**or calculation blocking; - - call of function and ljambda-call;
- - the sentence
**let**. **The execution form:**- - by turns
**progn**; - - the
**parallel**; - - the independent
**fork**. **Branching of calculations:**- - conditional sentences
**cond**,**if**. **Iterations:**- - cyclic sentences
**for**,**for***,**while**,**do-while**.

Function evaluation creates for the period of calculation new connections for formal parametres of function. New connections in the form can be created and by means of the offer ** let**. This structure looks so:

**(nil let ((**m_{1} {value_{1}}**)**|m_{1} **(**m_{2} {value_{2}}**)**|m_{2} …**)**

form_{1}

form_{2} …**)
**

The sentence ** let ** is calculated so, that at first dynamic variables ** m _{1}**,

>(nil setq a 2) nil >(nil let ((a 0)) (nil setq a 1)) nil >a 2

The form ** let ** is actually syntactic modification of a ljambda-call in which formal and actual parametres are placed in common in the form beginning:

**
(nil let ((**m_{1} {a_{1}}**) (**m_{2} {a_{2}}**)** … **(**m_{n} {a_{n}}**))**

form_{1} form_{2} …**)**

≡

**(nil (lambda
(**m

form

The lambda-expression body can consist of several forms which are calculated by turns, and value of last form comes back as value of a ljambda-call.

Values to form variables ** let ** are given simultaneously. It means, that values of all variables ** m**_{i } are calculated before linkage with formal parametres is carried out. New connections of these variables yet do not operate at the moment of calculation of initial values of variables which are listed in shape later. For example:

>(nil let ((x 2) (y (3 * x))) (nil list x y)); at calculationyatxthere is no connectionError:eval: Symbol x have no value

Sentence ** progn**, ** parallel ** and ** fork ** allow to work with several calculated forms:

**
(nil progn** form_{1} form_{2} … form_{n}**)
(nil parallel** form

(nil fork

At these special forms variable number of arguments. The sentence ** progn ** by turns calculates these arguments and returns value of last argument as value. The sentence ** parallel ** in parallel calculates all these arguments and does not return anything, ** nil**. The sentence **fork** starts form on calculation **(nil progn** form_{1} form_{2} … form_{n}**)**, does not expect their result and returns nothing, ** nil**. These forms didn't contain the mechanism of definition of internal variables:

>(nil progn (nil setq x 2) (nil setq y (3 * x))) nil >x 2

By means of the form ** let ** it is necessary to set a scope of variables. The given form allows to use the forms calculated by turns, and as result returns value of last form. This property name implicit ** progn**.

The sentence ** cond ** is the basic means of a branching of calculations. It is the syntactic form, allowing to operate calculations on the basis of conditions defined by predicates. The structure of the conditional offer is that:

**
(nil cond
(**p

(

…

Any forms can be predicates ** p _{i } ** and resultants expressions

- Expressions
**p**, carrying out a role of predicates, are calculated by turns from left to right (from top to down) until there will be an expression which value is not neither_{i}**nil**nor**false**i.e. which logic value is the true. - The expression corresponding to this predicate is calculated, and the received value comes back as value of all offer
**cond**. - If the true predicate is not present, value
**cond**will be**nil**.

In a following example by means of the sentence

>(nil defmethod type (l) (nil cond ((nil = l) 'empty) ((nil atom l) 'atom) (true 'list))) (lambda (l) (nil cond ((nil = l) 'empty) ((nil atom l) 'atom) (true 'list))) >(nil type '(a b c)) list >(nil type (nil atom '(a t o m))) atom

In the conditional sentence there can be no an expression ** a _{i} ** or on its place is frequent the several of forms can:

**
(nil cond
(**p

…

…

…

If to a condition expression as result of the sentence ** cond ** at the validity of a predicate value of a predicate stands out is not put in conformity. If to a condition there correspond some forms at its validity of the form are calculated by turns from left to right and value of last form (implicit ** progn**) will be result of the sentence ** cond**.

As an example of use of the conditional sentence we will define logic actions of logic of statements ** and**, ** or**, ** not**, ** => ** (implication) and ** <=> ** (identity):

>(('logic defclass) defvar value) logic >('logic defmethod set (x) ('value set x)) (lambda (x) ('value set x)) >('logic defmethod and (x) (nil cond (value x) (true false))) (lambda (x) (nil cond (value x) (true false))) >('x set ('logic newobject)) logic(EnvironmentLayer((this . .. logic(EnvironmentLayer((this . ... ) (value . nil) ))) (value . nil) )) >(x set true) true >(x and false) false >('logic defmethod or (x) (nil cond (value true) (true x))) (lambda (x) (nil cond (value true) (true x))) >(x or false) true >('logic defmethod not () (nil not value)) (lambda nil (nil not value)) >(x not) false >('logic defmethod => (x) (nil cond (value x) (true true))) (lambda (x) (nil cond (value x) (true true))) >(x set false) false >(x => true) true

Implication can be defined and through other operations:

('logic defmethod => (x) (this or (x not))) ('logic defmethod <=> (x) ((this => x) and (x => this)))

Predicates ** and ** and ** or ** are a part of the built in functions of a Lisp. The number of their arguments can be any.

>(nil and (nil atom nil) (nil = nil) (nil eq nil nil)) true

Sentence ** cond ** it is possible to combine in the same way, as well as calls of functions. For example, a predicate ** xor ** which is true in the presence of unique affirmative argument, it is possible to define as follows:

>('logic defmethod xor (x) (nil cond (value (nil cond (x false) (true value))) (true x))) (lambda (x) (nil cond (value (nil cond (x false) (true value))) (true x))) >(x set true) true >(x xor false) true >(x set false) false >(x xor false) false

In this function on a place of expression of the first condition again there is an sentence ** cond**. On a place, defined to a condition, also it is possible to use one more conditional offer, and in this case we will receive a conditional condition. Such constructions very quickly lead to difficult definitions.

The sentence ** cond ** represents most the general conditional structure. It criticise for an abundance of brackets and that the structure of this sentence is torn absolutely off from a natural language. Therefore in Lisp-systems others are used also, in various relations more natural, conditional sentences. But it is possible to manage and with the help only ** cond ** sentences.

In a simple case it is possible to take advantage brackets quite natural and containing few of the form ** if**.

**
(nil if** condition that-form otherwise-form**)
≡
(nil cond
(**condition that-form

(true

>(nil if (nil atom true) 'atom 'list) atom

In case of repeating calculations in a Lisp cycles are used known basically on procedural languages.

**
(**number **for*** variable {site for calculations}**)
**

By turns local variable gives numbers from ** 0 ** to ** number-1**. At each such value the cycle body is calculated.

For an example by means of the sentence ** for* ** we will define the function calculating ** n**-th degree of number (**n** - whole, positive):

>('number defmethod expt (n) (nil let ((result 1)) (n for* i (nil setq result (result * this))) result)) (lambda (n) (nil let ((result 1)) (n for* i (nil setq result (result * this))) result)) >(2 expt 3) 8

The cycle ** for ** differs from ** for* ** that in it all body is calculated in parallel, and each process has an own variable. The given cycle is applied at service of elements of a vector (in case calculations are independent of their order). The given cycles are defined even for service of elements of the list and strings.

The following cycle ** while ** is intended for by turns carried out actions before reception of satisfying results.

**
(nil while** condition {site for calculations}**)
**

>(nil setq x 10 s 0) nil >(nil while (x > 0) (nil setq s (s + x)) (nil setq x (x - 1))) false >s 55

The cycle ** do-while ** differs from ** while ** only a procedure for test and actions:

**
(nil do-while** {site for calculations} condition**)
**

In a "pure" functional Lisp is not present cyclic sentence (**for**, ** progn ** and others), especially operators of transfer of control. For programming of repeating calculations in it only conditional senteces and definitions recursive, or calling itself, functions are used.

For example, the recursive variant of function ** expt ** could be defined so:

('number defmethod expt (n) (nil if (n < 2) this (this * (this expt (n - 1)))))

Function ** expt ** calls itself until used as the counter the argument ** n ** will not decrease to one, i.e. only ** n-1 ** times. After that as result of a call of function ** expt ** value ** this ** comes back. By each transfer of value the result is multiplied by the previous level on ** this**. So ** this ** it will appear multiplied on itself ** n ** times.

Recursive definition of function ** expt ** is shorter, and reflects a function essence, than the versions based on ** for* ** is better.

Let's examine one more function simply defined through recursion, - a factorial (the factorial is a product of the given number on all integer positive numbers, smaller data. For example, a factorial from 5, designated as 5!, is 1*2*3*4*5=120. The zero factorial considers 1):

>('number defmethod ! () (nil if (this < 2) 1 (this * ((this - 1) !)))) (lambda nil (nil if (this < 2) 1 (this * ((this - 1) !)))) >(5 !) 120

Iterative and recursive programs are theoretically identical by the computing possibilities, otherwise, sets of computable functions with their help coincide (so-called partially recursive functions). So basically, it is possible to program any calculation by any of these ways. However properties of iterative and recursive variants of programs can essentially differ. In this connection often it is necessary to solve, what of ways of programming suits for the given problem more. Simplicity and naturalness of programming, and also its efficiency depends on the made choice from the point of view of time of execution and memory use.

By means of iterative programming, as a rule, longer and difficult in realisation, the result can be calculated is much easier and faster. It happens for two reasons, first, because computers in general are focused on by turns calculations, and, secondly, because compilers not always in a condition to transform recursive definition in iterative and use at calculations a stack, despite the fact that what it is not always necessary.

Recursive programming in general shorter and substantial. It is especially useful to use recursion when a solved problem or processed data inherently recursive. For example, mathematical definition of a factorial recursively and its realisation through recursive function is absolutely natural:

n! = 1 | , if n=0 |

n! = n*(n-1)! | , if n>0 |

The recursive decision well suits for operation with lists as lists can recursively contain sublists. Recursive functions can use with success at work with other dynamic structures which are not completely known in advance. Recursive procedures take the important place almost in all programs connected with an artificial intellect.