Parallel programming in functional style

  In this article is told about creation of model for parallel programming (PP).

• Introduction
  
• Lisp
  
• The extension of a Lisp for parallel calculations
  
• Lisp2D
  
• Advantages of special language to PP
  

  Necessity for creation of language for PP has arisen after there were possibilities of a writing of programs for multiprocessing systems and appearance in architectures modern processors of threads. And programmers and the public culture of programming has appeared not ready to a writing of P-programs as the usual procedural approach for PP has brought to that the programmer could not hold logically under the control all processes any more and underestimated side effects which give parallel processes. Very bad role in it is played by a habit to write simple details of programs not reflecting about that that they will already work in other conditions.
  To program it became real, it is necessary to change style of programming and to learn to program anew. To take the Knuth three-volume edition, to view, close and forget. ;)

  What properties such language should possess?

  Multyplatformness: now parallel computing systems the big set as there is a search of the most convenient systems, and this search is far from completion. This language should be abstract, not concern features of certain systems. Same abstract as the block of the scheme of algorithms differ from the assembler.

  Structurness: in procedural programming have already passed to this style, statements goto and more structures while, for less use. When the program has good structure in it easier to understand, as it is known that the given part of the program at change will affect only a small part of all project. At transition to object oriented programming there was a possibility to write service functions (methods) for operation with objects (and objects are parts of the project). And at change of operation of one object necessity for revising of operation of others passes. For PP it is very important as now it is a stumbling-block for transition to PP.

  Evidence: the programmer should have possibility to inspect behaviour of all computing process as a whole. In the absence of this mechanism, separate sites of the program cannot unambiguously define as other processes function. Introduction of semaphores and other mechanisms of synchronisation do not lead to desirable result as the idea of semaphores has come from a habit to think by turns and punishment has not kept itself waiting - there were stop situations when some processes on a circle close access on the one hand and wait access with another.

  Efficiency: ability as much as possible to load all computing resources (useful business, it is finite). The program Overall performance on a concrete platform is estimated by time spent for its execution. At addition to a platform of one more computing resource (the block to the multiprocessing system) there should be a rise of speed of the program. On reaching of certain power of system the program cannot load tasks additional resources any more as plays a role necessity of by turning of some operations for algorithm. It is important to give the chance to apply to the programmer as much as possible parallelism in the presence of unlimited computing resources. Such possibility we will name as efficiency of language.

  One of ways of the organisation of calculations is prompted by a life. People very much use for a long time this system for handle of the big organisations. There is a hierarchy of control, on top one controls, seldom two-three persons who directly set tasks to the managers, those in turn solve tasks in view by means of engaging of the employees.
  Well organised structures thus for an expedition of performance of the task do so: all subtasks which can be fulfilled in a parallel way are charged to separate employees, and those that demand certain by tuning of performance are charged to one person who is engaged only in monitoring by correctness of by turning of performance of tasks by the employees.
  For example of the bad organisation the Soviet system of reception of various documents at which there is no person except the person to whom any piece of paper which would accept from the person only inquiry about reception of the document is necessary can be and itself inspected strict by turnig of stamps and helps. In the absence of such tools we have system at which for passing of separate step all helps that we have passed the previous steps are necessary. This system can be compared to style of programming with usage of semaphores (document) for synchronisation of processes (officials).
  The system which has structure expresses that the separate control centre performs a small part of all operation and does not interfere with internal operation of the employees.
  Thus there was a question on the candidate - language which most of all would suit for the extension to PP. Having tried various styles of programming it became clear, that functional style, namely language ideally suits to above marked requirements a Lisp.

  Lisp - also known as (((Lots of (Idiotic (Silly (Parentheses)))))) has started the application only as a pilot model for the lambda-calculus theory. That in this language it was possible to program all general-recursive functions on Cherch (and this class coincides with a class of all algorithms which can be set by means of a Turing machine) in it to set possibility to recursion, check on zero-object enough and with elementary operations over objects in which area functions will work. So has appeared a Pure Lisp.
  Lisp objects are set as either atoms, or structures of atoms. Atom - by definition the indivisible object. Was concrete in a Lisp uniform structure of atoms the list and language is selected has received name LISt Processing.
  Function is a mapping from the field of objects in the field of objects.
  Complex functions turn out from elementary by means of concatenation which is necessary in the theory a lambda-calculus.
  In application of a principle Fon Neumann's - unities of data and programs language creators have gone further away and have created syntax at which the form of record of function was same as well as the data record form, and depending on requirements was interpreted as function or as data.

  More completely in a Lisp it is possible to read introduction in other sources:

Association of users of a Lisp - www.elwoodcorp.com/alu

The second edition of standard Common Lisp - gauss.upf.es/www-storage/cltl/clm/clm.html

  Function definition in Common Lisp looks so:
   (defun fname arglist body) where arglist represents the list from formal names of arguments and keywords. Keywords look so: &rest, &optional, &environment, … All these keywords are used for interpretation: what part of actual parametres of function to assign to what formal parametres. As the way of calculations of arguments is a component of function and at other order of calculations it would be already other algorithm logical would be to add keywords, for example &concurrent and &parallel then to bracket appropriate parametres.
  For example, function func from three arguments x, y, z demands, that they were calculated in such order: (z it is parallel (x then y)). It can be written so:
  (defun func (&parallel (z &concurrent (x y))) body)
  Now we will consider as it is possible to write calculation of in a parallel way several functions which part is fulfilled by turns. For by turns execution in Lisp there is a function progn,
(progn func₁ … func_n)
which calculates all functions func_i by turns and as the result returns value of the last expression. Accordingly we define the form parallelprogn which calculates minorant functions in parallel regulations, and the result returns nil.
  Further possibility to multisequencing exists in the moment between calculation of arguments and execution of a body of function. Sometimes there is a returning of result from function, thus she never considered value of several arguments. In this case it would be useful to start execution of function and calculation of arguments in parallel regulations, and at attempt by function to consider value of not calculated argument to stop process before result obtaining.
  We take in a Lisp function apply which calculates application of some function to the list of arguments and we create parallel clone parallelapply which fulfils calculations by the above described way. Here there is one trap.
  Power of language a Lisp consists in unity of the definition of programs and data. It gives possibility to write algorithms which create other algorithms which then and are calculated. But the order of calculation of arguments with a function body is a component of the function, and the form parallelapply would calculate all in a parallel way, not paying attention to what function it should fulfil, as it can be created dynamically in the course of program operation.
  This order of calculations means also it is necessary to set at level of definition of function.
  For example so:
  Normal function -
(defun func args body)
  and anonymous -
(lambda args body)
  instant function -
(paralleldefun func args body)
  and anonymous -
(parallellambda args body)
  At such extension of language the Lisp becomes more complex for programming, correction of ready programs by means of additions of directives on an order of calculations to become practically impossible. Easier already to write all from zero.
  Now has come it is time to recollect the Pure Lisp where the type of calculations was obviously defined by program structure - beautifully and naturally.
  Having convinced of what to use already written programs in any language for refinement to parallel fulfilment it is impossible, I have definitively refused idea of the extension of languages.
  It would be desirable to have such resource of expression of algorithms at which the record structure obviously defined an order of calculations. Thus my searches have led to an applicative language:

  Lisp2D is the experimental applicative language created for studying technicians of parallel programming.
  Functions in this language are mappings from set of objects in set of objects.
  The object - either atom or structure of objects.
  The atom - the indivisible object, can be different types: numbers, symbols, strings, arrays, functions. Also there are the types consisting of one object: true - the logical truth, nil - nothing.
  The structure is pair of references to other objects. The first (head) unit is designated first, the second (tail) - rest.
  The list are the pairs connected in special way: (a . (b . (… . (z . nil)) …) also are designated: (a b … z).
  The interpreter accepts the object from the console or from a file, calculates it and returns result.
  Value of atom, except for symbols will be result of atom. If to the symbol it is linked what or value in a current environment this value comes back, differently arises an error of the interpreter and comes back nil.
  If on an interpreter entrance the structure of objects this structure is perceived as start of function with arguments moves. In a head part there should be an object, the second unit is function, in a tail part there should be a list of arguments.
(object function arg1 arg2 … argn)
  The order of function evaluation and arguments depends on called function and is set during its definition.
  On a place function there can be a symbol, function or structure of functions.
  If function - the symbol that is taken functional value of the symbol from a current functional environment and this value is applied to an environment. In the absence of functional value there is an error of the interpreter and comes back nil.
  To define functional value for the symbol it is possible function defmethod.
(typename defmethod name arglist body)
  Function can be built in or lambda-call. The lambda-call is a definition of function without a name.
(lambda arglist body)
  The interpreter calculates in a parallel way all arguments.
   arglist - the list of formal names of arguments which contact actual values and have operation only in body execution time body. From the outside of this form of value of formal parametres are unavailable.
  The order of feed of arguments for function should correspond to an order in arglist
(object name x1 y1 z1 t1 a1)

  By means of the described method of regulation of an order of calculations to the programmer essentially to program parallel programs as the synchronisation most part is incurred by the interpreter easier. For example parallel calculation of arguments of function with the subsequent assignment of values to formal parametres of function hides in itself a synchpoint of the termination of calculation of all arguments. Automatic suspend of process for waiting of value of argument hides in itself all process of check of availability of result and a process stop/start. In most cases at practical programming it is possible to do without special system functions such as wait - a stop of process before value definition, lock, unlock - additional functions for access to divided data. Their usage litters the text of the program and complicates understanding of operation of all process.
  Programming with direct control of synchronisation of processes and joint using data demands the same eradication as the principle of a by turns control of operation of the program with the help goto in due time has been eradicated. There were structures while, for, do, until which as a matter of fact hid in itself necessary commands of control.
  Similitude of the majority of styles of programming to the procedural facilitates translation of programs in the machine code, but once again underlines their inconsistency to give to the programmer necessary toolkit for PP.
  I hope given article will help with judgement of problems of PP to all who is interested in it.