Calculation in a Lisp

  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:

1. 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.
2. Symbols which are used as variables.
3. Forms in the form of list structure which are:
   1. Calls of functions and ljambda-calls.
   2. Special forms into which enter setq, ' and many forms described in this chapter intended for handle by calculation and a context.
   3. 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₁ {value₁})|m₁ (m₂ {value₂})|m₂ …)
  form₁
  form₂ …)

  The sentence let is calculated so, that at first dynamic variables m₁, m₂, … from first "argument" of the form communicate (simultaneously) with corresponding values value₁, value₂, … Then values of forms form₁, form₂, … are by turns calculated. As value of all form value of last form comes back. As well as at functions, after the termination of calculation of connection of dynamic variables m₁, m₂, … any changes of their values are liquidated also (setq) will not be visible from the outside. For example:

>(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₁ {a₁}) (m₂ {a₂}) … (m_n {a_n}))
  form₁ form₂ …)
≡
(nil (lambda
  (m₁ m₂ … m_n)  ; formal parametre
  form₁ form₂ …)  ; function body
  (nil progn {a₁}) (nil progn {a₂}) … (nil progn {a_n}))  ; actual parametre

  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 calculation  y  at  x  there is no connection
Error:eval: Symbol x have no value

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

(nil progn form₁ form₂ … form_n)
(nil parallel form₁ form₂ … form_n)
(nil fork form₁ form₂ … form_n)

  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₁ form₂ … 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₁ a₁)
  (p₂ a₂)
  …
  (p_n a_n))

  Any forms can be predicates p_i and resultants expressions a_i. Value of the sentence cond is defined as follows:

1. Expressions p_i, 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 nil nor false i.e. which logic value is the true.
2. The expression corresponding to this predicate is calculated, and the received value comes back as value of all offer cond.
3. If the true predicate is not present, value cond will be nil.

>(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₁ a_1,1)
  …
  (p_i)  ; expression is absent
  …
  (p_k a_k,1 a_k,2 … a_k,n)  ; the several of forms as result
  …)

  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 otherwise-form))

>(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:

  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.