©2003 Alex Glebe

Parallel programming in functional style

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

Introduction

  Necessity for creation of language for PP has arisen after there were possibilities of a writing of programs for multiprocessing systems and occurrence in architecture 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 by-effects which give parallel processes. Very bad role in it is played with a habit to write simple details of programs not reflecting about that that they will already work in other conditions.
  To program it became really necessary to change style of programming and to learn to program anew. To take the Knuth three-volume edition, to see, close and forget. ;)

  What properties such language should possess?
   Multyplatforming: now parallel computing systems the big set as there is a search of the most convenient systems, and this search is far from end. 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.
   Structuring: in procedural programming already have passed to this style, less use operators of transition goto and more structures while, for. When the program well structured in it to understand easier, 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 work with objects (and objects are parts of the project). And at change of work of one object necessity for revision of work of others disappears. For PP structuring it is very important as now it is a stumbling-block for transition on PP.
   Evidence: the programmer should have possibility to supervise behaviour of all computing process as a whole. In the absence of this mechanism, separate sites of the program cannot unequivocally 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 consistently 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, certainly). The program overall performance on a concrete platform is estimated by time spent for its performance. At addition to a platform of one more computing resource (the block to multiprocessing system) there should be an increase of speed of the program. On achievement of certain capacity of system the program cannot load problems additional resources any more as plays a role necessity of sequence of some actions 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 name 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 management of the big organisations. The hierarchy of management is created, on top one operates, seldom two-three persons who directly set problems to the managers, those in turn solve tasks in view by means of attraction of the employees.
   Well organised structures thus for acceleration of performance of a problem do so: all subtasks which can be carried out in parallel are charged to separate employees, and those that demand certain sequence of performance are charged to one person who is engaged only in monitoring by correctness of sequence of performance of problems by the employees.
   As 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 serve and itself supervised strict sequence of stamps and inquiries. In the absence of such service we have system at which for passage of a separate step all inquiries that we have passed the previous steps are necessary. This system can be compared to style of programming with use of semaphores (inquiries) for synchronisation of processes (officials).
   The system which has structure is expressed that the separate knot of management performs a small part of all work and does not interfere with internal work of the employees.
   Thus there was a question on the candidate - language which most of all would approach for expansion to PP. Having tried various styles of programming it became clear, that functional style, namely language Lisp ideally approaches to above marked requirements.

Lisp

   Lisp - also known as (((Lots of (Idiotic (Silly (Parentheses)))))) has begun the application only as experimental model for the lambda-calculation 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 operate. So has appeared Pure Lisp.
   Lisp objects are set as either atoms, or structures of atoms. Atom - by definition indivisible object. Was concrete in 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 it is possible to read Lisp introduction in other sources:
Association of Lisp users - www.elwoodcorp.com/alu
The second edition of Common Lisp standard - gauss.upf.es/www-storage/cltl/clm/clm.html
   Why Lisp has been chosen? Let's consider its properties.
   Multyplatforming: in connection with that that it purely theoretical formed not leaning on the concrete architecture.
   Structuring: what can be more structured? The program in Lisp is a call of one function with arguments (in Pure Lisp with one argument). At first values of arguments are calculated, then over values appropriate processing is made and one value - result of function comes back. And in Pure Lisp process of calculation of arguments is independent of calculation of other arguments (so they can be calculated in a parallel way!) also it will be independent of that in what way to be handled result called function.
   Evidence - it is result of good structure. At reprogramming of one function it is enough to reconsider processing of functions which it call also functions which are called by it.
   Efficiency: the mechanism of multisequencing of tasks is built in theories of general-recursive functions. Namely the complex function created by means of concatenation f (g (x)) is obliged to be calculated consistently, and calculation of arguments of function f (x, y, …, z) can and should be calculated in a parallel way. Set by means of Pure Lisp function cannot will be fulfilled more in a parallel way, than it is set by its structure.
   That began to program really on Lisp in different styles (first of all in procedural) in its definition have entered so-called pseudo-functions which values except returning still create a side effect and also concept of the variables which values vary by means of pseudo-functions.
   Application of pseudo-functions in programming reduces efficiency of multisequencing as in some cases consecutive operation of side effects is required. But these pseudo-functions are necessary for qualitative programming as not always easier to write algorithm in functional style, and it is better to use the styles corresponding to the solved task much more often.
   At definition of language Lisp there was no problem of parallel calculations and an order of calculations has been set hard and consecutive: at first arguments at the left on the right, then function - for usual functions. With introduction of pseudo-functions also macroes which individually solve a question on an order of calculations of arguments also were added.
   Thus there was a question - as in merging of all styles to create the mechanism which effectively would set conditions on possibility of multisequencing of calculations.

Lisp expansion for parallel calculations

   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 in 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 sequentially. For consecutive execution in Lisp there is a function progn,
(progn func1 … funcn)
which calculates all functions funci consistently and as the result returns value of the last expression. Accordingly we define the form parallelprogn which calculates minorant functions in a parallel mode, 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 a parallel mode, and at attempt by function to consider value of not calculated argument to stop process before result reception.
   We take in 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 Lisp consists in unity of the job 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 untitled -
(lambda args body)
   moment function -
(paralleldefun func args body)
   and untitled -
(parallellambda args body)
   At such extension of language Lisp it becomes more difficult to program, 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 about 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

   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, characters, 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 characters will be result of atom. If to the character 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 input moves the structure of objects this structure is perceived as start of function with arguments. 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 character, function or structure of functions.
   If function - the character that is taken functional value of the character 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 character it is possible by function defmethod.
(typename defmethod name arglist body)
   Function can be built in or lambda-call. The lamda-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. 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)

Advantages of special language for PP

   By means of the described method of regulation of an order of calculations to the programmer essentially easier to program parallel programs as the synchronisation most part is incurred by the interpreter. 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 the stop of process for waiting of value of argument hides in itself all process of check of readiness of result and process stopping/starting. 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 handle of synchronisation of processes and joint using data demands the same eradication as the principle of a sequence 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 handle.
   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 software to all who is interested in it.