On one of classifications programming languages share on procedural, named also operator or imperative, and declarative languages. The overwhelming majority of programming languages now in use, for example the BASIC, Cobol, Fortran, Pascal, C and Ada, concern procedural languages. The most essential classes of declarative languages are functional, or applied, and logic languages. To category applicateve languages concern, for example Lisp, FP, Apl, Nial, Krc and Logo. The most known language of logic programming is the Prolog.
Programming languages | ||
The procedural | The logical | The functional |
BASIC | Prolog | Lisp |
Cobol | KLO | APL |
Fortran | Mandala | Nial |
Pascal | Logo | |
Ada | Krc |
In practice programming languages are not purely procedural, functional or logical, and comprise features of languages of various types. On a procedural language it is often possible to write the functional program or its part and on the contrary. Can was instead of language type speak about style or a programming technique more precisely. Naturally various languages support different styles in a different degree.
The procedural program consists of operators and the sentences controlling of their execution. Typical operators are assignment statements and control transfers, input\output statements and special sentences for the organisation of cycles. It is possible to make fragments of programs of them and the subroutine. At the heart of such programming the capture of value of any variable, fulfilment over it operations and saving of new value by means of the assignment statement and so until then it will not be received yet (and, probably lay, desirable definitive value is printed out).
The functional program consists of a collection of definitions of functions. Functions, in turn, represent calls of other functions and the sentences controlling of calls. Calculations start with call of some function which in turn calls the functions entering into its definition etc. according to hierarchy of definitions and structure of conditional sentences. Functions it is frequent or direct, or call itself.
Each call returns some value in the function which has called it, which calculation after that proceeds; this process repeats until then while the function which has started calculation will not return an end result to the user.
"Pure" functional programming does not recognise assignment and control transfers. The branching of calculations is grounded on the mechanism of processing of arguments of the conditional sentence. Repeated calculations are carried out through the recursion which is the main resource of functional programming.
Many practical situations assume the recursive or self-repeating behaviour which is coming back to. We will assume, that, for example, we try to read the text in other language, using an explanatory dictionary of this language. When in the text there is an unfamiliar word its explanation is searched in the dictionary. In a word explanation can, in turn, there will be unfamiliar words which need to be found in the dictionary etc. This procedure it is possible to define by means of following rules:
Word meaning finding-out:The arch represented above corrected name recursive or using as in it the reference to own definition contains. It is a question not of a vicious circle of definitions, and about a line of action which is suitable for usage and we will quite fulfil.
In the recursive description of operations it makes sense to pay attention to following circumstances. First, procedure contains as a rule terminal branches and a termination condition. Secondly, when procedure reaches a recursive branch functioning process stops also new same process is started from the beginning, but already at new level. The interrupted process somehow is remembered. He will wait and will start to be executed only after the termination of new process. In turn, new process can stop, expect etc.
So the tree of the interrupted processes from which it is fulfilled only last at the moment time processes (leaflets) is derivated as though; after the termination of their operation process preceding them continues to be fulfilled. Entirely all process is fulfilled, when the tree again will become empty, or, in other words, all interrupted processes will be fulfilled.
Musical forms and operations also can be recursive in many respects (for example, a canon in which the tune is accompanied by the same tune with delay, and others).
The purposeful behaviour and solution of problems are recursive processes. In the same way and researches in the field of an artificial intelligence are recursive in the attempt to research the processes proceeding in a brain with which help there is a research and solution of problems including researches in the field of an artificial intelligence.
The recursion in Lisp is grounded on the mathematical theory of recursive functions. The recursion well suits for operation with lists as lists can consist of sublists, i.e. have a recursive structure. For processing of recursive structures naturally enough usage of recursive procedures.
Lists can be defined by means of following rules Backus-Naur:
list | → nil | ; the list or is empty, or it |
list | → (head . tail) | ; is a dot pair, which tail is the list |
head | → atom | |
head | → list | ; recursion "in depth" |
tail | → list | ; recursion "in width" |
The recursion is both in head definition, and in tail definition. We will notice, that the definition brought above directly mirrors definitions of the functions working with lists which can handle recursive call a list head, i.e. "in depth" (in a direction first ), and a tail, i.e. "in width" (in a direction rest).
Lists can be defined and in the following form which underlines logical recursiveness of construction of lists and atoms and sublists:
list | → nil | |
list | → (unit unit … ) | |
unit | → atom | |
unit | → list | ; recursion |
In programming on Lisp the recursion is used for the organisation of repeating calculations. On it splitting of a problem and its sharing into the subtasks, which solution is grounded, how much it is possible, try to reduce to already solved or according to the main idea of recursion to the task solved at the moment.
On recursion it is grounded and often used at problem solving and by search the mechanism of returns with which help it is possible to return from a deadlock branch to a branching place, having cancelled the done calculations. The recursion in Lisp represents not only the organisation of calculations is a views and problem solving methodology.
The theory of recursive functions along with algebra of lists and a lambda-calculus is one more support upon which is based Lisp. In this area of mathematics the theoretical questions linked with computable are studied. The computable are understood as such tasks which basically can be programmed and solved by means of the computer. The theory of recursive functions offers along with a Turing machine, a lambda-calculus and others theoretical a formalism equivalent to them algorithmic computable.
In the theory of recursive functions functions (algorithms) and their properties are considered and classed according to what functions can be received and calculated, using various forms of recursion. The main idea of recursive definition consists that function can be reduced by means of recurrence relations to some initial values, to earlier certain functions or to the most defined function, but with more "simple" arguments. Calculation of such function is ended while it is reduced to known initial values. For example, Fibonacci numbers
0, 1, 1, 2, 3, 5, …
using infix notation Lisp, it is possible to define by means of following recurrence relations:
(0 fib) = 0
(1 fib) = 1
(n fib) = (((n - 1) fib) + ((n - 2) fib))
Class of the functions received thus, name as a class of primitively recursive functions.
There are also the functions which are not primitively recursive. As an example it is possible to bring function Ackerman which can be set following recurrence relations:
(0 Ack x y) = (y + x)
(1 Ack x y) = (y * x)
(2 Ack x y) = (y ^ x)
…
Set by means of brought above the scheme function Ack is not primitively recursive though it and computable, i.e. it can be defined and on the basis of this definition to calculate its value for finite time.
It is possible to show, that there are the functions which values can be calculated by means of algorithm but which cannot be described algorithmically. Calculation of such function can be infinite. As an example we will bring function (n f m) which result is 1 in case in decimal notation numbers π there is a fragment of repeating digits m in the length n.
It is possible to show, that the algorithm of calculation of this function exists, but we do not know, what it. We can only try to calculate π signs in hope, that the required fragment will find out, but to define, whether calculation will be completed sometime, we cannot. Such functions are named general-recursive.
The class primitively recursive functions is interesting enough from the point of view of many practical problems. Application of recursive functions in Lisp is not limited to only numerical arguments, they are used (and even first of all) for character structures that opens new big possibilities in comparison with numerical calculations.