Lecture
Functional programming is explained using the LISP Common Lisp dialect as an example. This dialect is most common and has an official standard. Common Lisp can work not only in batch mode (when it starts as a normal program), but also in dialog mode.
LISP is probably the first practically implemented language 1 , which was based on a serious theoretical foundation and tried to raise the practice of programming to the level of concepts, and not vice versa - to lower the concepts to the level that existed at the time of the creation of the practice language.
Currently, functional programming is represented by a whole family of languages, but LISP does not give up its positions.
In some cases, the conscious assimilation of concepts, even at the lowest level, is impossible without basic theoretical information. A familiarity with such a basis, in turn, stimulates a much deeper interest in the theory and contributes to the understanding that it is impossible not to rise to the highest levels of knowledge and skills without mastering the theory.
The theoretical basis of the LISP language is the logic of functionality: combinatorial logic or (by the name of one of the basic concepts in the most popular of its current formalizations) 
-calculus.
AT - calculus expressive means, at first glance, extremely stingy. There are two basic operations: applying a function to an argument (fx) and quantifying a function by expression 
. In terms -calculus squaring function is written as 
or, to be closer to the usual mathematical notation, 
.
The main operation is a symbolic calculation of applying a function to an argument: 
converted to t [u]. But this operation can be applied anywhere in the expression, so that no particular discipline of calculation is fixed. Moreover, functions can be calculated in the same way as arguments. Already this little subtlety leads to a fundamental expansion of opportunities. -numbers compared to normal procedure calls. If we wish to confine ourselves to it, then the typed -calculus, in which, as is customary in most modern programming systems, values are strictly divided by type. In typed - there are only types of functions in calculus, but this is enough, since functions can take as parameters and return functions.
But in its original form -calculus is untyped, any object can be a function, an argument, and, moreover, a function can be applied to itself. Of course, this makes looping possible, but not a single “universal” algorithmic system can do without it. For example, the expression
calculated infinitely, but a slightly more complex expression
can either give a or loop, depending on the choice of the order of its calculation. But all the same, if we arrive at a result, then it is determined unequivocally. So the compatibility of computations does not spoil the uniqueness, if the language is well designed.
J. McCarthy transferred ideas -calculations in programming, without losing almost nothing from the original concepts. Further, he noticed that in a rudimentary form in - The notion of a list appeared, and transferred lists as the main data structures into its language. - the numeration was inspired by the agreement of the LISP language that the first member of the list is treated as a function that applies to the others.
The basic unit of data for a LISP system is the list.
Lists are defined by the following inductive definition.
The elements of the list (l 1 , ..., l n ) are called l 1 ,. . . l n . Equality of lists is given by the following inductive definition.
Example 8.2.2 . All lists (), (()), ((())), etc., are different. The lists nil, (nil, nil), (nil, nil, nil) and so on are also different. The lists (((A, B), C), (A, (B, C)), (A, B, C), where A, B, C are different atoms, are pairwise distinct.
Since the concept defined by the inductive definition should be constructed as a result of a finite number of steps for applying the definition, we exclude lists that refer to themselves. The lists in our consideration are isomorphic to ordered final trees whose leaves are nil or atoms.
The vertices of the list L are given by the following inductive definition.
The length of the list is the number of items in it. The depth of the list is the maximum number of nested pairs of brackets in it. The union of lists (l 1 , ..., l n ) and (k 1 , ..., k m ) is the list
(l 1 ..., l n , k 1 , ..., k m ).
Replacing the vertex a of the list L with an atom or the list M is obtained by replacing the subtree L corresponding to a with a tree for M. The replacement is denoted by L [a | M]. Through L [a || M] will denote the result of replacing several occurrences of vertex a by M.
Atoms in the LISP language are numbers, names, true T. Lying is an empty list of NIL, which in principle is not an atom, but in the LISP language when checking whether it is an atom, it is true . In the same way, the truth is issued when checking whether it is an on-list. However, all list operations are applicable to NIL, and those that work with atoms are often not applicable to it. For example, an attempt to assign a value gives an error.
Basic operation for specifying lists (list ab... Z). She calculates her arguments and collects them into a list. For this operation, without evaluating the arguments, there is a cursive '(ab.. Z). It is a special case of the quote function (abbreviated to denoted as'), which prohibits all calculations in its argument and copies it into the result as it is.
By tradition, elementary list parsing operations are denoted by names that begin with c and end with r, and in the middle there is a certain sequence of letters a and d; (car s) selects the head (the first member of the list), (cdr s) - the tail (the sublist of all members, starting with the second). The letters a and d are applied starting at the end. The total number of characters in the resulting atom must be no more than six. Consider a fragment of a dialogue illustrating these operations. As soon as a complete expression is entered in the dialog, it is calculated or an error is generated.
[13]> (setq a '(bc (de) fg)) (BC (DE) FG) [14]> (cddr a) ((DE) FG) [15]> (cddar a) *** - CDDAR: B is not a list 1. Break [16]> ^ Z [17]> (caaddr a) D [18]> (cdaddr a) (E)
If special blocking operations are not applied, the first argument of the list is interpreted as a function whose arguments are the remaining elements of the list. This allows the program to also set the list.
Thus, in LISP, as well as in sentence languages, the data structure of the program and the memory fields processed by the program are the same. Apparently, this is one of the most successful forms of maintaining conceptual unity for high-level systems.
Attributes may be associated with each atom-name in the memory field. The standard attribute is the value of the atom. To set this attribute, there is a function (setq atom value), similar to assignment. This function does not evaluate its first argument; it treats it as a name that needs to be assigned a value.
The value in LISP can be local . If we change the value of an atom inside a certain block, then such an "assignment" acts only inside the minimal enclosing brackets and disappears outside the block. In addition to the value, names can have any number of other attributes that are necessarily global . They belong to the name itself, not to the block. The method of setting the values of these attributes is somewhat artificial. There is another setf function that evaluates its first argument, giving a reference to a place to which a value can be assigned (for example, an attribute). The function of getting the value of the attribute get, even if there is no attribute yet, indicates its place. The following example demonstrates how this works.
[38]> (setf (get 'b' weight) '(125 kg)) (125 KG) [39]> (get 'b' weight) (125 KG)
Let's take a closer look at the LISP data structure. She is a two-tier. At the top level there is a list structure . At the bottom is the structure of information associated with the atom. She is depicted in Fig. 8.1. Both of these levels recursively refer to each other, for example, the attributes of an atom are lists.
There are data types (in terms of programming) in LISP, but they are determined dynamically. In particular, if a real number is assigned to an atom as a value, then the type of the atom becomes float.
For LISP (as for any other functional language) it is not necessary 2 to say where and how data structures (lists) are located.
They should be considered as purely mathematical objects with a complex structure, which always accurately indicates the current computational elements:
The general data structure and program of a functional language can be viewed as a connected loaded graph that dynamically changes during calculations, which has active vertices , that is, functions that are currently computed, potentially active vertices corresponding to functions that are assigned to calculate or continue (deferred, suspended, etc.), and passive vertices , whose participation in the calculations is not currently planned. The graph arcs mark connections by control or by data between functions. Such a graph is hereinafter referred to as the abstract functional calculation graph .
It is possible to specify such a graph and the strategy of working out active vertices in different ways. In this case there may appear different forms of functional programming.
For an abstract calculator, it is natural to consider the graph of functional dependencies as the memory field of a functional program in which the field of view is highlighted: active (or active and potentially active) vertices-functions with their arguments.
In the practice of implementing functional programming systems there are three options for concretizing the representation of the graph:
Switching and associative schemes are considered when discussing non-imperative models of computations (see § 1.2 and 3.1). The choice of the sequentially viewed structure for the first functional language is conditioned by the unique possibility for that time of realizing the functionality by modeling it with the operational means of the traditional model of computation. The list structure is also constructed by means of the address representation that is more or less standard for the traditional model. From a linguistic point of view, it is this choice that ensures the uniformity of the structure of the program and the data, on the basis of which J. McCarthyudal was able to build a system of means sufficient for practical functional programming.
A LISP program is defined as a list of applications of functions, some of which can be calculated during the execution of the program itself. As a rule, the lists specified in the program are interpreted as applications of functions and are calculated if another function does not define previously activated functions (you have seen that the quote function prohibits the calculation of its argument, the setq function prohibits the calculation of only the first of two arguments, and the setf function causes the first argument to be calculated to the stage when the reference to its value is received). Any expression yields a value, which is used, in particular, during interactive work with LISP (by the example of which concepts are illustrated).
The main control functions are conceptually the same and allow you to dynamically build the block structure of the program. In particular, the function
(block name e1... en) (8.1)
calculates its arguments, starting with the second, one by one, thereby specifying a sequence of commands. Its first argument, name, is the name of the block. At any time, from any enclosing block, you can exit and return a value using the function
(return-from name value) (8.2)
This LISP compares favorably with most languages, where such structural transitions are either incomplete or incorrectly implemented.
Further, the block is any description of the function. The description of the function is made using the function defun, which, in turn, is defined through the primitives function and lambda. The first of them specifies that the name being its argument is considered as a function (it is often abbreviated to # 'in a specific syntax), the second forms the value of a functional type. The function name is also the name of the function block.
Example 8.4.1 . This example illustrates the definition of factorial, calling an anonymous function, and the ability to evaluate an arbitrary functional expression created in the program.
[1]> (defun fact (n) (if (= n 0) 1
(* (fact (- n 1)) n)))
FACT
[2]> (fact 40)
815915283247897734345611269596115894272000000000
[3]> ((lambda (x) (fact (* xx))) 5)
15511210043330985984000000
[4]> (setq g '(lambda (x) (fact (* xx))))
(LAMBDA (X) (FACT (* XX)))
[5]> (eval (list g 3))
362880 It should be noted that the definition of the function with the given name and the value of the name can be set independently. For example, we can set (setq fact 7) in the same context, although, of course, this is a disgusting way of programming.
All formal parameters of functions are local variables. No changes in their values go outside. But all other properties remain global! Let's give an example.
[23]> (defun f (x) (progn (setf
(get 'x' weight) '(25 kg)) (+ x 3)))
F
[24]> (setf (get 'x' weight) '(30 kg))
(30 KG)
[25]> (get 'x' weight)
(30 KG)
[26]> (setq x 5)
five
[27]> (f 3)
6
[28]> x
five
[29]> (get 'x' weight)
(25 KG) In LISP, it is possible to create an anonymous block with its local variables, without declaring it a function. Creating such a block is called variable binding and is performed by the let function.
The value of a name inherited from the outside will still be external! See the example below.
[32]> (setq a '(bcd))
(BCD)
[33]> (setq b 5)
five
[34]> (list (let ((b 6)) (eval (car a)))
(eval (car a)))
(5 5)
[35]> (list (let ((b 6)) b) (eval (car a)))
(6 5)
[36]> (list (let ((b 6)) (list ba))
(eval (car a)))
((6 (BCD)) 5)
[37]> (list (let ((b 6)) (eval (car
(list 'ba)))) (eval (car a)))
(5 5) The most important feature of functional programming as a style, first used in the LISP language, are functionals with function arguments. Consider an example of squaring all members of a tuple.
[57]> (setq a (list 1 5 7 9 11 13 15 19 22 28)) (1 5 7 9 11 13 15 19 22 28) [58]> (mapcar (function (lambda (x) (* xx))) a) (1 25 49 81 121 169 225 361 484 784)
The mapcar functional applies its first argument to all members of the second.
Such functionals, in particular, make cycles practically unnecessary. Nevertheless, in the LISP language there are loop constructions as a tribute to the programming tradition. The alienness of the cycles is emphasized by the fact that they always give the value NIL.
And finally, we give an example 3 .
Example 8.4.2 .This program builds an automaton for finding all occurrences of some system of words in the input stream. Later it is analyzed from the point of view of automaton programming.
; ================================================ =
;
; convolution / sweep of the text system
; the text is a list
; ((Name Option ...) ...)
; the first name in the convolution is the designation of the text system
; (Element ...)
; (Name Token (Options))
; ((example (ma (w n)
; (w a))
; (w n))
; ((n ins)))
; ================================================ =
; convolution implementation: unic, ass-all, swin, gram, bnf
(defun unic (vac) (remove-duplicates (mapcar 'car vac)))
;; list of unique beginnings
(defun ass-all (Key Vac)
;; a list of all the continuation options
(cond
((Null Vac) Nil)
((eq (caar Vac) Key) (cons (cdar Vac)
(ass-all Key (cdr Vac))))
(T (ass-all Key (cdr Vac)))
))
(defun swin (key varl) (cond
;; the next step of convolution or remove the brackets in the absence of options
((null (cdr varl)) (cons key (car varl)))
(T (list key (gram varl)))
))
(defun gram (ltext)
;; left convolution if there were common beginnings
((lambda (lt) (cond
((eq (length lt) (length ltext)) ltext)
(T (mapcar
# '(lambda (k) (swin k (ass-all k ltext)))
lt)
))) (unic ltext)
))
(defun bnf (main ltext binds) (cons (cons main (gram ltext)) binds))
;; bringing to mind the BNF
; ================================================ ==
; sweep implementation: names, words, lexs, d-lex, d-names,
; h-all, all-t, pred, sb-nm, chain, level1, lang
(defun names (vac) (mapcar 'car vac))
;; designated characters
(defun words (vac) (cond
;; used characters
((null vac) NIL)
((atom vac) (cons vac NIL))
(T (union (words (car vac)) (words (cdr vac))))))
(defun lexs (vac) (set-difference (words vac) (names vac)))
;; undefined lexemes
(defun d-lex (llex)
;; terminal self-determination
(mapcar # '(lambda (x) (set xx)) llex))
(defun (llex)
;; definition of non-terminals
(mapcar # '(lambda (x) (set (car x) (cdr x))) llex))
(defun h-all (h lt)
;; goal substitution
(mapcar # '(lambda (a)
(cond
((atom h) (cons ha))
(T (append ha)))
) lt))
(defun all-t (lt tl)
;; tailing
(mapcar # '(lambda (d)
(cond
((atom d) (cons d tl))
(T (append d tl))
)) lt))
(defun pred (bnf tl)
;; joining predecessors
(level1 (mapcar # '(lambda (z) (chain z tl)) bnf)))
(defun sb-nm (elm tl)
;; name definition
(cond
((atom (eval elm)) (h-all (eval elm) tl))
(T (chain (eval elm) tl))
))
(defun chain (chl tl)
;; chain assembly
(cond
((null chl) tl)
((atom chl) (sb-nm chl tl))
((atom (car chl))
(sb-nm (car chl) (chain (cdr chl) tl)))
(T (pred (all-t (car chl) (cdr chl)) tl))))
(defun level1 (ll)
;; alignment
(cond
((null ll) NIL)
(T (append (car ll) (level1 (cdr ll))))))
(defun lang (frm)
;; output of the given text system
(d-lex (lexs frm))
(d-names frm)
(pred (eval (caar frm)) '(())
)) Listing 8.4.1. An automaton for finding all occurrences of a certain system of words in the input streamLet us examine the capabilities of the language LISP in the complex.
The expressive means of specifically syntactic representation of the overall data structure and programs of the LISP language are extremely meager. But this presentation allows one to unambiguously associate the syntax and implementation structure.
Реализационное представление как нельзя лучше соответствует соглашению об общности функциональной структуры и структуры данных: в каждом списке голова рассматривается как указание (имя, ссылка или что-то подобное) на функцию, а хвост — как последовательность указаний на аргументы. Задание свойства списка не быть функцией, т. е. отмена выделенного статуса головы, обозначающей функцию, достигается с помощью блокировок. Это удачное решение в условиях принятого соглашения, позволяющее трактовать нефункциональныйсписок как константную функцию, "вычисляющую" свое изображение (представление). Еще более важно то, что оно обеспечивает гибкость представления: функцию eval, заставляющую список принудительно вычисляться, естественно трактовать просто как снятие блокировок. Заметим, что на уровне абстрактного синтаксиса функция eval обязана быть универсально применимой к любому списку.
К сожалению, такой универсализм провоцирует крайне ненадежное и неэффективное программирование, поэтому это решение нельзя считать удачным. Справедливости ради заметим, что в те времена, когда разрабатывался язык, задача надежности еще не была поставлена, но плохо то, что сформировался стихийный стандарт, не способствующий качеству программирования.
Для обеспечения практической пользы функции eval следовало бы предусмотреть компенсирующие регламенты ее корректного применения на уровне конкретного синтаксиса, режимов вычислений и системных механизмов.
Attention !
На уровне абстрактного и конкретного синтаксиса разные семантические возможности имеют разный статус, поэтому в конкретном представлении необходимо предусматривать механизм скрытия и даже полного запрета тех возможностей, которые концептуально разумны лишь на уровне абстрактного синтаксиса 4 .
Структура списков LISP идеальна для представления абстрактного синтаксиса языка. И хотя злые языки называют этот синтаксис"утомительным нагромождением скобок", он в точности соответствует абстрактному синтаксису. Если даже не учитывать преимущества указанного соответствия, то остается простота представления программ и данных в виде линейной текстовой последовательности символов.
Другие гипотетические кандидаты на роль конкретного синтаксиса по этому критерию явно проигрывают. Традиционные математические формы задания функций и их применений являются текстуально избыточными (как префиксная, так и постфиксная записи требуют обязательного обрамления параметров скобками), а бесскобочная нотация Лукасевича (и прямая, и обратная) еще более запутывали бы тексты по сравнению с "утомительным нагромождением скобок". Но за счет внеязыковых прагматических соглашений о том, как располагать на двумерном носителе (на бумаге или на экране) скобочную структуру, можно существенно облегчить. Если же система программированиябудет поддерживать (и проверять!) прагматические соглашения (что характерно для развитых систем), то вид программ станет вполне читаемым. Таким образом преодолеваются неудобства линейного представления.
Today we could talk about other formats of a particular LISP syntax, including those not related to the linear representation. The use of advanced graphics tools for on-screen set of programs allows you to fully connect the two-dimensional work. However, traditions and spontaneously formed standards leave no room for the introduction of such formats. Here, once again and in full, the harmful effects of early standardization manifested themselves, hindering the development of a direction that remains one of the most conceptually rich and promising.
The dictation of linearity has taken root so deeply that even in those cases where it could be overcome painlessly, the language system is most often still built as linear. This concerns not only the functional style 5 .
The standard add-on for Common Lisp, which imitates an object-oriented style, is the CLOS - Common Lisp Object System module. By itself, objectivity does not give any gain compared to the LISP language, since the possibilities of dynamic computation of functions in LISP are even wider. Apparently, this is why CLOS has two interesting modifications that make it not quite similar to a standard OOP.
Let's start with the concept of data structure in Common Lisp. The structure is defined by the defstruct function
(defstruct pet name (species' cat) age weight sex)
Setting the structure automatically sets the constructor function of the make-pet structure, which can take key arguments for each of the fields:
(make-pet: nick 'Viola: age' (3 years): sex 'femina))
and the access function for each of the fields, for example pet-nick, used to get the value of the field or a link to it. If the field is not initialized (neither by default nor by the constructor), it gets the initial value of NIL. There is no further specification of structure fields 6 .
In the object, for each field, access functions and the names of key parameters for initialization of arguments can be explicitly specified. We give an example of a class defined on the basis of another class.
(defclass pet (animal possession) (
(species: initform 'cat)
(nick: accessor nickof
: inintform 'Pussy
: initarg namepet)
) This class inherits fields, access functions, and so on from the animal and possession classes. For example, the cost field is in the class value if it is in one of these classes. Since there are no static types of fields, there are no conflicts.
The main function of inheritance in CLOS is to define ordering on classes. Each class has its own ordering. An heir is smaller than his ancestors, one of the ancestors is the one that was previously listed in the inheritance list when defining a class. CLOS completes this partial order to linear. The method of replenishing the order can be changed at any time and without notification, and the hacker use of features of a particular replenishment is considered a gross stylistic mistake. If the system finds incompatibility in the definition of order, then it gives an error, as in the following example:
[6]> (defclass init () ())
# <STANDARD-CLASS INIT>
[7]> (defclass a (init) ())
# <STANDARD-CLASS A>
[8]> (defclass b (init) ())
# <STANDARD-CLASS B>
[9]> (defclass c1 (ab) ())
# <STANDARD-CLASS C1>
[10]> (defclass c2 (ba) ())
# <STANDARD-CLASS C2>
[11]> (defclass contr (c1 c2) ())
*** - DEFCLASS CONTR:
inconsistent precedence graph,
cycle (# <STANDARD-CLASS A> # <STANDARD-CLASS B>) CLOS can specify methods that differ from functions in that their arguments are specified, for example
(defmethod inspectpet ((x pet) (y float)) (setf weightofanimal 3.5))
As you can see from this example, methods are not necessarily associated with classes. They can be associated with any type. CLOS methods may have additional specifications. In order to understand how these specifications interact with the ordering of class types, consider the following program and the result generated when it is executed.
(defclass thing ()
((weight: initform '(0 kg)
: accessor weightof
: initarg: weight)))
(defclass animal (thing)
((specie: accessor specieof
: initarg: spec)
(sex: accessor sexof
: initform 'm
: initarg: sex)))
(defclass possession (thing)
((owner: accessor ownerof
: initform 'nnn)
(cost: accessor costof
: initform '(0 bucks)
: initarg: cost))
)
(defclass person (animal)
((specie: initform 'human)
(name: initarg: thename
: accessor nameof)))
(defclass pet (animal possession)
((nick: initarg: thenick
: accessor nickof)
(specie: initform 'cat)))
(defmethod act: before ((p pet))
(print "Cat mews"))
(defmethod act: after ((p pet))
(print "Cat turns"))
(defmethod act: around ((p pet))
(progn (print "You have a cat") (call-next-method)))
(defmethod act ((p animal))
(progn (print "Animal is close to you") (call-next-method)))
(defmethod act: before ((p animal))
(print "You see an animal"))
(defmethod act: after ((p animal))
(print "You send the animal off"))
(defmethod act: around ((p animal))
(progn (print "You don't like wild animals") (call-next-method)))
(defmethod act ((p possession)))
(progn (print "You test your property") (call-next-method)))
(defmethod act: before ((p possession))
(print "You see your property"))
(defmethod act: after ((p possession))
(print "You are pleased by your property"))
(defmethod act: around ((p possession))
(progn (print "You admire your property
if it is in good state ") (call-next-method)))
(defmethod act ((p thing))
(print "You take the thing"))
(defmethod act: before ((p thing))
(print "You see something"))
(defmethod act: after ((p thing))
(print "You identified this thing"))
(defmethod act: around (((p thing)))
(progn (print "You are not interested
in strange things ") (call-next-method)))
(act (make-instance 'pet: thenick "Viola": cost' (25 kop))) Listing 8.6.1. The interaction of additional CLOS method specifications with class type ordering When downloading this file, the following occurs:
[1]> (load 'myclasses) ;; Loading file E: \ clisp-2000-03-06 \ myclasses.lsp ... "You have a cat" "You don't like wild animals" "You admire your property if it is in good state" "You are not interested in strange things" "Cat mews" "You see an animal" "You see your property" "You see something" "Cat purrs" "Animal is close to you" "You test your property" "You take the thing" "You identified this thing" "You are pleased by your property" "You send the animal off" "Cat turns" ;; Loading of file E: \ clisp-2000-03-06 \ myclasses.lsp is finished. TExample 8.6.2. Program Download Result 8.6.1
It is seen that the ordering of classes with respect to inheritance allows you to build entire sequences of actions when calling a single method.
Since CLOS has no mechanisms for hiding specific views, no mechanisms for replacing direct access to data with functions, or other characteristic features of OOP, we see another example of how a different, no less interesting essence is covered with a buzzword (in this case, OOP): the beginnings of planning actions on the structure of data types In this regard, it is worth recalling a brilliant experiment in planning calculations on a data structure, currently (apparently, temporarily) forgotten: the Estonian PRIZ system [28].
Inadequate theorizing prevents us from seeing and developing the real virtues of the system and fixes weak points.
Comments
To leave a comment
Programming Styles and Techniques
Terms: Programming Styles and Techniques