Lecture
Functional programming is a section of discrete mathematics and a programming paradigm in which the computational process is interpreted as calculating the values of functions in the mathematical understanding of the latter (as opposed to functions as subroutines in procedural programming).
Contrasted with the paradigm of imperative programming, which describes the computation process as a sequential change of states (in a sense similar to that in automata theory). If necessary, in functional programming, the entire set of consecutive states of the computational process is represented explicitly, for example, as a list.
Functional programming involves doing a calculation of the results of functions from the source data and the results of other functions, and does not imply the explicit storage of the program state. Accordingly, it does not imply the variability of this state (as opposed to imperative, where one of the basic concepts is a variable that stores its value and allows changing it as the algorithm runs).
In practice, the difference between a mathematical function and the concept of “function” in imperative programming lies in the fact that imperative functions can rely not only on arguments, but also on the state of variables external to the function, and also have side effects and change the state of external variables. Thus, in imperative programming, when calling the same function with the same parameters, but at different stages of the algorithm, you can get different data at the output due to the influence of the state of variables on the function. And in a functional language, when calling a function with the same arguments, we always get the same result: the output data depends only on the input. This allows program execution environments in functional languages to cache the results of functions and call them in an order not defined by the algorithm and parallelize them without any additional actions by the programmer (see below Pure functions)
λ-calculus is the basis for functional programming, many functional languages can be considered as a “superstructure” above them [1] .
Main article: Functional programming language
The most famous functional programming languages are [2] :
The still incompletely functional initial versions of both Lisp and APL made a special contribution to the creation and development of functional programming. Later versions of Lisp, such as Scheme, as well as various versions of APL, supported all the features and concepts of a functional language [5] .
As a rule, interest in functional programming languages, especially purely functional, was more scientific than commercial. However, such notable languages as Erlang, OCaml, Haskell, Scheme (after 1986) as well as specific R (statistics), Mathematica (symbolic mathematics), J and K (financial analysis), and XSLT (XML) found application in the commercial programming industry . Such widely used declarative languages as SQL and Lex / Yacc contain some elements of functional programming, for example, they are careful not to use variables. Spreadsheet languages can also be viewed as functional, because spreadsheet cells are given an array of functions, usually depending only on other cells, and if you want to model variables, you have to use the capabilities of the imperative macro language.
Lambda calculus has become the theoretical basis for the description and calculation of functions. Being a mathematical abstraction, not a programming language, it formed the basis of almost all functional programming languages today. A similar theoretical concept, combinatorial logic, is more abstract than λ-calculus and was created earlier. This logic is used in some esoteric languages, such as Unlambda. Both λ-calculus and combinatorial logic were developed for a clearer and more accurate description of the principles and fundamentals of mathematics [6] .
The first functional language was Lisp, created by John McCarthy during his work at the Massachusetts Institute of Technology in the late fifties and implemented, initially, for IBM 700/7000 (Eng.) Russian. [7] . Lisp introduced many concepts of functional language, although it professed not only the functional programming paradigm [8] . Further development of Lisp became such languages as Scheme and Dylan.
An information processing language (Information Processing Language (English), IPL) is sometimes defined as the very first machine functional language [9] . This is a language type for working with a list of characters. It contained the concept of a “generator”, which used a function as an argument, and also, since it is an assembly level language, it can be positioned as a language having higher order functions. However, in general, IPL is focused on the use of imperative concepts [10] .
Kenneth E. Iverson developed the APL language in the early sixties, documenting it in his book A Programming Language (ISBN 9780471430148) [11] . APL has had a significant impact on the language of FP (English) Russian., Created by John Backus. In the early nineties, Iverson and Roger Hui (English) Russian. created a successor to APL — the J. programming language. In the mid-nineties, Arthur Whitney (Eng.) Russian, who previously worked with Iverson, created the K language, which was later used in the financial industry on a commercial basis.
In the seventies at the University of Edinburgh, Robin Milner created the ML language, and David Turner began the development of the SASL language at the University of St. Andrews and, subsequently, the Miranda language at the University of Kent. Ultimately, several languages were created on the basis of ML, among which are the most famous Objective Caml and Standard ML. Also in the seventies, a programming language was developed based on the Scheme principle (the implementation of not only the functional paradigm), which was described in the well-known work “Lambda Papers”, as well as in the eighty-fifth year book “Structure and Interpretation of Computer Programs”, in which the principles of functional programming has been conveyed to a wider audience. [ source not specified 1920 days ]
In the eighties, Per Martin-Löf created an intuitionistic theory of types (also called constructive). In this theory, functional programming received constructive evidence of what was previously known as the dependent type. This gave a powerful impetus to the development of dialog-proof theorems and the subsequent creation of many functional languages.
Haskell was created in the late eighties in an attempt to combine the many ideas derived from the study of functional programming. [five]
Some concepts and paradigms are specific to functional programming and are mostly foreign to imperative programming (including object-oriented programming). However, programming languages are usually a hybrid of several programming paradigms, so “mostly imperative” programming languages can use any of these concepts. [ source not specified 1920 days ]
Main article: Higher order function
Functions of higher orders are those functions that can take as arguments and return other functions. [12] Mathematicians often call such a function an operator, for example, a derivative operator or an integration operator.
Higher-order functions allow the use of currying - the transformation of a function from a pair of arguments to a function that takes its arguments one by one. This transformation got its name in honor of H. Curry.
Functions that are pure are those that do not have the side effects of I / O and memory (they depend only on their parameters and return only their result). Pure functions have several useful properties, many of which can be used to optimize code:
Although most compilers of imperative programming languages recognize pure functions and remove general subexpressions for calls to pure functions, they cannot always do this for precompiled libraries that, as a rule, do not provide this information. Some compilers, such as gcc, for optimization purposes, provide the programmer with keywords to refer to pure functions [13] . Fortran 95 allows you to designate functions as “pure” [14] .
Main article: Recursion
In functional languages, a loop is usually implemented as a recursion. Strictly speaking, in the functional programming paradigm there is no such thing as a cycle. Recursive functions call themselves, allowing operations to be performed again and again. A large stack may be required to use recursion, but this can be avoided in the case of tail recursion. Tail recursion can be recognized and optimized by the compiler into the code obtained after compiling a similar iteration in an imperative programming language. [15] Scheme language standards require the recognition and optimization of tail recursion. You can optimize tail recursion by transforming the program in the style of using continuations when compiling it, as one of the ways. [sixteen]
Recursive functions can be generalized using higher-order functions using, for example, cathamorphism and anamorphism (or “convolution” and “unfolding”). Functions of this kind play the role of such a thing as a cycle in imperative programming languages. [ source not specified 1920 days ]
Functional languages can be classified according to the way the function arguments are processed in the process of its calculation. Technically, the difference lies in the denotational semantics of the expression. For example, with a strict approach to the calculation of the expression
print (len ([2 + 1, 3 * 2, 1/0, 5-4]))
there will be an error at the output, since the third element of the list contains division by zero. With a non-strict approach, the value of the expression will be 4, since, strictly speaking, the values of its elements are not important for calculating the length of the list and may not be calculated at all. With a strict (applicative) order of calculation, the values of all arguments are pre-calculated before calculating the function itself. In the case of a non-strict approach (normal order of calculation), the values of the arguments are not calculated until their value is required when calculating the function [17] .
As a rule, the non-strict approach is implemented as a graph reduction. Lax computations are used by default in several purely functional languages, including Miranda, Clean and Haskell. [ source not specified 1920 days ]
In principle, there are no obstacles to writing programs in a functional style in languages that are not traditionally considered functional, just as you can write programs in an object-oriented style in structural languages. Some imperative languages support constructs that are typical for functional languages, such as higher order functions and list comprehensions, which make it easier to use the functional style in these languages. An example would be functional programming in Python. Another example is the Ruby language, which has the ability to create both lambda objects and the possibility of organizing anonymous higher-order functions through a block using the yield construct.
In C, function pointers as argument types can be used to create higher-order functions. Higher-order functions and the deferred list structure are implemented in C ++ libraries. In C # version 3.0 and higher, you can use λ-functions to write a program in a functional style. In complex languages, such as Algol-68, the available metaprogramming tools (in fact, language additions with new constructions) allow you to create data-specific objects and program constructions that are functional-style, after which you can write functional programs using them. [ source not specified 1920 days ]
Imperative programs tend to emphasize a sequence of steps to perform an action, and functional programs to the location and composition of functions, often without denoting the exact sequence of steps. A simple example of two solutions to the same task (using the same Python language) illustrates this.
# imperative style
target = [] # create an empty list
for item in source_list: # for each item in the source list
trans1 = G (item) # apply G () function
trans2 = F (trans1) # apply the function F ()
target.append (trans2) # add converted item to list
The functional version looks different:
# functional style # FP languages often have built-in compose () function compose2 = lambda A, B: lambda x: A (B (x)) target = map (compose2 (F, G), source_list)
Unlike the imperative style, which describes the steps leading to the achievement of a goal, the functional style describes the mathematical relationship between the data and the goal.
The main feature of functional programming, which determines both the advantages and disadvantages of this paradigm, is that it implements a stateless computation model . If an imperative program at any stage of execution has a state, that is, a set of values for all variables, and produces side effects, then a purely functional program has neither the state nor parts of it, nor does it produce any side effects. What is done in imperative languages by assigning values to variables is achieved in functional languages by passing expressions to function parameters. The immediate consequence is that a purely functional program cannot change the data it already has, but can only generate new ones by copying and / or expanding old ones. The consequence of the same is the rejection of cycles in favor of recursion.
Improved code reliability
The attractive side of stateless computation is to increase the reliability of the code due to a clear structuring and the absence of the need to track down side effects. Any function works only with local data and works with them always the same, no matter where, how and under what circumstances it is called. The impossibility of data mutation when using them in different places of the program eliminates the appearance of difficult-to-find errors (such as, for example, randomly assigning an incorrect value to a global variable in an imperative program).
Convenience of organizing unit testing
Since a function in functional programming cannot produce side effects, it is impossible to change objects both inside the scope and outside (as opposed to imperative programs, where one function can set some external variable readable by the second function). Единственным эффектом от вычисления функции является возвращаемый ей результат, и единственный фактор, оказывающий влияние на результат — это значения аргументов.
Таким образом, имеется возможность протестировать каждую функцию в программе, просто вычислив её от различных наборов значений аргументов. При этом можно не беспокоиться ни о вызове функций в правильном порядке, ни о правильном формировании внешнего состояния. Если любая функция в программе проходит модульные тесты, то можно быть уверенным в качестве всей программы. В императивных программах проверка возвращаемого значения функции недостаточна: функция может модифицировать внешнее состояние, которое тоже нужно проверять, чего не нужно делать в функциональных программах [18] .
Возможности оптимизации при компиляции
Традиционно упоминаемой положительной особенностью функционального программирования является то, что оно позволяет описывать программу в так называемом «декларативном» виде, когда жесткая последовательность выполнения многих операций, необходимых для вычисления результата, в явном виде не задаётся, а формируется автоматически в процессе вычисления функций. Это обстоятельство, а также отсутствие состояний даёт возможность применять к функциональным программам достаточно сложные методы автоматической оптимизации.
Возможности параллелизма
Ещё одним преимуществом функциональных программ является то, что они предоставляют широчайшие возможности для автоматического распараллеливаниявычислений. Поскольку отсутствие побочных эффектов гарантировано, в любом вызове функции всегда допустимо параллельное вычисление двух различных параметров — порядок их вычисления не может оказать влияния на результат вызова.
Недостатки функционального программирования вытекают из тех же самых его особенностей. Отсутствие присваиваний и замена их на порождение новых данных приводят к необходимости постоянного выделения и автоматического освобождения памяти, поэтому в системе исполнения функциональной программы обязательным компонентом становится высокоэффективный сборщик мусора. Нестрогая модель вычислений приводит к непредсказуемому порядку вызова функций, что создает проблемы при вводе-выводе, где порядок выполнения операций важен. Кроме того, очевидно, функции ввода в своем естественном виде (например, getchar из стандартной библиотеки языка C) не являются чистыми, поскольку способны возвращать различные значения для одних и тех же аргументов, и для устранения этого требуются определенные ухищрения.
Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования (присваивание, цикл, «неявный PROGN» были уже в LISPе). Использование таких средств позволяет решить некоторые практические проблемы, но означает отход от идей (и преимуществ) функционального программирования и написание императивных программ на функциональных языках. В чистых функциональных языках эти проблемы решаются другими средствами, например, в языке Haskell ввод-вывод реализован при помощи монад — нетривиальной концепции, позаимствованной из теории категорий.
Comments
To leave a comment
Functional programming
Terms: Functional programming