Lecture
|
Functional programming aims
give each program a simple mathematical interpretation.
This interpretation should be independent of the details of the performance and
understandable to people who do not have a scientific degree in the subject area.
Lawrence Paulson
Before you begin the description of the actual functional programming, it is necessary to refer to the history of programming in general. In the 40s of the 20th century, the first digital computers appeared, which, as you know, were programmed by switching various types of toggle switches, wiring and buttons. The number of such switchings reached about a few hundred and inexorably grew with the increasing complexity of programs. Therefore, the next step in the development of programming was the creation of all sorts of assembly languages with simple mnemonics.
However, even assemblers could not become the tool that ordinary people could use, since Mnemonic codes were still too complicated, especially since every assembler was tightly connected with the architecture on which it was executed. Thus, the next step after assembler became the so-called imperative high-level languages (BASIC, Pascal, C, Ada, and others, including object-oriented). Such languages were imperative for the simple reason that their main feature is orientation, primarily to the sequential execution of instructions operating with memory (i.e. assignments) and iterative loops. Calls of functions and procedures, even recursive, did not relieve such languages from obvious imperativeness (prescription).
The cornerstone in the functional programming paradigm, as will be shown later, is function. If we recall the history of mathematics, we can estimate the age of the concept of "function". He is already about four hundred years old, and mathematics has invented an infinite number of theoretical and practical devices for operating functions, ranging from ordinary operations of differentiation and integration, to abstruse functional analyzes, theories of fuzzy sets and functions of complex variables.
Mathematical functions express the relationship between the parameters (input) and the result (output) of a process. Since computation is also a process with input and output, the function is quite a suitable and adequate means of describing computations. It is this simple principle that underlies the functional paradigm and functional programming style. A functional program is a collection of function definitions. Functions are defined through other functions or recursively through themselves. In the process of executing the program, the functions receive the parameters, calculate and return the result, if necessary, calculate the values of other functions. When programming in a functional language, the programmer should not describe the order of calculations. He simply needs to describe the desired result in the form of a system of functions.
Addressing the objectives of the course, it is necessary first of all to emphasize that functional programming, as well as logic programming, has found great application in artificial intelligence and its applications. Therefore, here functional programming is considered extremely meticulously and with all possible details. The rest of this lecture covers the history of functional programming, properties of functional languages, problems to be solved, and some reference data.
As you know, the theoretical foundations of imperative programming were laid back in the 1930s by Alan Turing and John von Neumann. The theory underlying the functional approach was also born in the 20s – 30s. Among the developers of the mathematical foundations of functional programming are Moses Schönfinkel (Germany and Russia) and Haskell Curry (England), who developed combinatorial logic, as well as Alonzo Church (USA), the creator of l-calculus.
The theory remained a theory until in the early 50s of the last century, John McCarthy developed Lisp, which became the first almost functional programming language and for many years remained the only such language. Although Lisp is still used (as, for example, FORTRAN), it no longer satisfies some modern requirements that force software developers to charge the compiler as much as possible, thereby easing their overwork. The need for this, of course, arose because of the ever-increasing complexity of the software.
In connection with this circumstance typification begins to play an increasing role. In the late 1970s - early 1980s, typing models were intensively developed that are suitable for functional languages. Most of these models included support for such powerful mechanisms as data abstraction and polymorphism. Many typed functional languages appear: ML, Scheme, Hope, Miranda, Clean and many others. In addition, the number of dialects is constantly increasing.
As a result, it turned out that almost every functional programming group used its own language. This prevented the further spread of these languages and gave rise to numerous smaller problems. To remedy the situation, a joint group of leading researchers in the field of functional programming decided to recreate the merits of various languages in a new universal functional language. The first implementation of this language, named Haskell in honor of Haskell Curry, was created in the early 1990s. Currently Haskell-98 standard is valid.
First of all, most functional programming languages are implemented as interpreters, following the traditions of Lisp. Interpreters are convenient for quick debugging of programs, eliminating the lengthy compilation phase, thereby shortening the normal development cycle. However, on the other hand, interpreters in comparison with compilers usually lose several times in speed of execution. Therefore, in addition to interpreters, there are compilers that generate good machine code (for example, Objective Caml) or C / C ++ code (for example, Glasgow Haskell Compiler). What is significant, almost every compiler with a functional language is implemented in the same language.
In this course, to describe functional programming examples, we will use either some abstract functional language close to mathematical notation, or Haskell, whose free compilers can be downloaded from www.haskell.org.
As the main properties of functional languages, we briefly consider the following:
· Brevity and simplicity;
· Strict typing;
· Modularity;
· Functions are values;
· Purity (no side effects);
· Delayed (lazy) calculations.
Programs in functional languages are usually much shorter and simpler than the same programs in imperative languages. Let us compare programs in C and in an abstract functional language using the example of sorting the list using the fast Hoare method (an example that has already become classic when describing the advantages of functional languages).
Example 1. Quick sort Hoare to C.
void quickSort (int a [], int l, int r) { int i = l; int j = r; int x = a [(l + r) / 2]; do { while (a [i]
Example 2. Quick sort of Hoare in an abstract functional language.
quickSort ([]) = [] quickSort ([h: t]) = quickSort (n | nt, n <= h) + [h] + quickSort (n | nt, n> h)
Example 2 should read this:
1. If the list is empty, the result will also be an empty list.
2. Otherwise (if the list is not empty), the head (first element) and tail (the list of remaining elements, which may be empty) are highlighted. In this case, the result will be the concatenation (splicing) of a sorted list of all tail elements that are less than or equal to the head, a list from the head itself, and a list of all tail elements that are larger than the head.
Example 3. Quick sorting of Hoare in Haskell.
quickSort [] = [] quickSort (h: t) = quickSort [y | y <- t, y = h]
As can be seen, even in such a simple example, the functional programming style wins both in the amount of written code and in its elegance.
In addition, all memory operations are performed automatically. When creating an object, memory is automatically allocated for it. After the object fulfills its purpose, it will soon also be automatically destroyed by the garbage collector, which is part of any functional language.
Another useful feature that makes it possible to shorten a program is the built-in pattern matching mechanism. This allows functions to be described as inductive definitions. For example:
Example 4. Determination of the N-th Fibonacci number.
fibb (0) = 1 fibb (1) = 1 fibb (N) = fibb (N - 2) + fibb (N - 1)
The pattern matching mechanism will be examined in further lectures; however, it can be seen here that functional languages go to a more abstract level than traditional imperative languages (the object-oriented paradigm and its extensions are not considered here).
Practically all modern programming languages are strictly typed languages (perhaps, with the exception of JavaScript and its dialects, there are no imperative languages without the concept of "type"). Strong typing provides security. A program that passes type checking simply cannot fall into the operating system with a message like "access violation", especially for languages such as C / C ++ and Object Pascal, where using pointers is a typical way to use a language. In functional languages, most errors can be corrected at the compilation stage, so the debugging stage and the overall development time of the programs are reduced. In addition, strong typing allows the compiler to generate more efficient code and thereby speed up the execution of programs.
Considering the example of Hoare’s quick sort, you can see that in addition to the differences already mentioned between the C variant and the abstract functional language, there is another important difference: the C function sorts the list of int values (integers), and the abstract function functional language - a list of values of any type that belongs to the class of ordered variables. Therefore, the last function can sort the list of integers, and the list of floating-point numbers, and the list of strings. You can describe any new type. Having determined for this type of comparison operation, it is possible to use quickSort without recompilation and with lists of values of this new type. This useful property of the type system is called parametric or true polymorphism, and is supported by most functional languages.
Another type of polymorphism is function overloading, which allows you to give different, but somewhat similar functions to the same name. A typical example of an overloaded operation is a normal addition operation. The addition functions for integers and floating-point numbers are different, but for convenience they have the same name. Some functional languages in addition to parametric polymorphism, support and overload operations.
In C ++, there is such a thing as a template that allows a programmer to define polymorphic functions like quickSort. The standard C ++ STL library includes such a function and many other polymorphic functions. But the C ++ templates, like the generic functions of Ada, actually generate a lot of overloaded functions, which, by the way, the compiler must compile each time, which adversely affects the compilation time and the size of the code. And in functional languages, the polymorphic function quickSort is one single function.
In some languages, such as Ada, strong typing forces the programmer to explicitly describe the type of all values and functions. To avoid this, a special mechanism is built into strongly typed functional languages that allows the compiler to determine the types of constants, expressions and functions from the context. This mechanism is called type inference mechanism. Several such mechanisms are known, but most of them are variations of the Hindley-Milner typing model, developed in the early 1980s. Thus, in most cases, you can omit the types of functions.
The modularity mechanism makes it possible to divide programs into several relatively independent parts (modules) with clearly defined links between them. This facilitates the design and subsequent support of large software systems. Modularity support is not a feature of functional programming languages, however, it is supported by most of these languages. There are highly developed modular imperative languages. Examples of such languages are Modula-2 and Ada-95.
In functional languages (as well as in programming languages and math in general), functions can be transferred to other functions as an argument or returned as a result. Functions that take functional arguments are called higher order functions or functionals. Perhaps the most well-known functionality is the map function. This function applies a certain function to all elements of the list, forming another list from the results of a given function. For example, by defining the function of raising an integer in a square as:
square (N) = N * N
You can use the map function to square all the elements of a list:
squareList = map (square, [1, 2, 3, 4])
The result of executing this instruction will be the list [1, 4, 9, 16].
Clean (no side effects)
In imperative languages, a function can read and modify the values of global variables during its execution and perform input / output operations. Therefore, if you call the same function twice with the same argument, it may happen that two different values are calculated as the result. This function is called a function with side effects.
To describe functions without side effects allows virtually any language. However, some languages encourage or even require side effects from the function. For example, in many object-oriented languages, a hidden parameter is passed to a member function of a class (often called this or self), which this function implicitly modifies.
In pure functional programming, the assignment operator is absent, objects cannot be changed and destroyed, one can only create new ones by decomposing and synthesizing existing ones. The garbage collector built in language will take care of unnecessary objects. Due to this, in pure functional languages all functions are free from side effects. However, this does not prevent these languages from imitating some useful imperative properties, such as exceptions and mutable arrays. For this there are special methods.
What are the benefits of pure functional languages? In addition to simplifying the analysis of programs, there is another significant advantage - parallelism. Since all functions for calculations use only their parameters, we can calculate independent functions in an arbitrary order or in parallel, this will not affect the result of calculations. Moreover, this parallelism can be organized not only at the level of the language compiler, but also at the level of architecture. Several research laboratories have already developed and used experimental computers based on similar architectures. An example is a Lisp machine.
In traditional programming languages (for example, C ++), a function call results in the evaluation of all arguments. This method of calling a function is called call-by-value. If any argument was not used in the function, then the result of the calculation disappears, therefore, the calculations were performed in vain. In a sense, the opposite of call-by-value is call-by-necessity. In this case, the argument is evaluated only if it is needed to calculate the result. An example of this behavior is to take the conjunction operator of all the same C ++ (&&), which does not compute the value of the second argument, if the first argument has a false value.
If a functional language does not support deferred calculations, then it is called strict. In fact, in such languages the order of computation is strictly defined. An example of strict languages is Scheme, Standard ML and Caml.
Languages using deferred computing are called non-strict. Haskell is a loose language, like Gofer and Miranda, for example. Lax languages are often clean.
Very often, strict languages include means of supporting some useful features inherent in non-strict languages, such as endless lists. In the delivery of Standard ML there is a special module to support deferred computing. And Objective Caml, in addition, supports an additional reserved word lazy and a construct for lists of values that are calculated by necessity.
The following tasks are traditionally considered in functional programming courses:
1. Getting a residual procedure.
If given the following objects:
P (x 1 , x 2 , ..., x n ) is a certain procedure.
x 1 = a 1 , x 2 = a 2 - known values of parameters.
x 3 , ..., x n - unknown values of parameters.
It is required to obtain the residual procedure P1 (x 3 , ..., x n ). This problem is solved only on a narrow class of programs.
2. Construction of a mathematical description of functions.
Let there be a program P. For it, the input values and output values are defined. It is required to construct a mathematical description of the function.
f: Dx 1 , ..., Dx n -> Dy 1 , ..., Dy m .
3. Definition of the formal semantics of a programming language.
4. Description of dynamic data structures.
5. Automatic construction of the "significant" part of the program according to the description of the data structures that are processed by the created program.
6. Proof of the presence of some property of the program.
7. Equivalent program transformation.
All these tasks are quite easily solved by means of functional programming, but practically insoluble in imperative languages.
This section provides a brief description of some functional programming languages (very few). For more information, see the resources listed in the next section.
Lisp (List processor) . It is considered the first functional programming language. Untyped. It contains a lot of imperative properties, but in general it is the functional style of programming that encourages. When calculating, it uses call-by-value. There is an object-oriented dialect of the language - CLOS.
ISWIM (If You See What I Mean). Functional prototype language. Developed by Landin in the 1960s to demonstrate what a functional programming language could be. Together with the language, Landin developed a special virtual machine for executing programs on ISWIM. This call-by-value virtual machine is called SECD machine. The syntax of the ISWIM language is based on the syntax of many functional languages. The syntax of ISWIM is similar to ML syntax, especially Caml.
Scheme . A Lisp dialect designed for computer science research. When developing Scheme, emphasis was placed on the elegance and simplicity of the language. Thanks to this, the language is much smaller than Common Lisp.
ML (Meta Language). A family of strict languages with a developed polymorphic type system and parameterizable modules. ML is taught in many Western universities (in some even as the first programming language).
Standard ML . Один из первых типизированных языков функционального программирования. Содержит некоторые императивные свойства, такие как ссылки на изменяемые значения и поэтому не является чистым. При вычислениях использует вызов-по-значению. Очень интересная реализация модульности. Мощная полиморфная система типов. Последний стандарт языка — Standard ML-97, для которого существует формальные математические определения синтаксиса, а также статической и динамической семантик языка.
Caml Light и Objective Caml . Как и Standard ML принадлежит к семейству ML. Objective Caml отличается от Caml Light в основном поддержкой классического объектно-ориентированного программирования. Также как и Standard ML строгий, но имеет некоторую встроенную поддержку отложенных вычислений.
Miranda . Designed by David Turner as the standard functional language that used lazy evaluation. It has a strict polymorphic type system. Like ML, it is taught in many universities. Has had a great influence on the Haskell language developers.
Haskell . One of the most common non-strict languages. It has a very developed typing system. The system of modules is somewhat worse developed. The latest language standard is Haskell 98.
Gofer (GOod For Equational Reasoning). Haskell's simplified dialect. Designed for learning functional programming.
Clean . Specially designed for parallel and distributed programming. Syntax resembles Haskell. Clean. Использует отложенные вычисления. С компилятором поставляется набор библиотек (I/O libraries), позволяющих программировать графический пользовательский интерфейс под Win32 или MacOS.
www.haskell.org — очень насыщенный сайт, посвящённый функциональному программированию в общем и языку Haskell в частности. Содержит различные справочные материалы, список интерпретаторов и компиляторов Haskell'а (в настоящий момент все интерпретаторы и компиляторы бесплатны). Кроме того, имеется обширный список интересных ссылок на ресурсы по теории функционального программирования и другим языкам (Standard ML, Clean).
cm.bell-labs.com/cm/cs/what/smlnj - Standard ML of New Jersey. Very good compiler. In addition to the compiler, the free distribution includes the utilities MLYacc and MLLex and the Standard ML Basis Library. Separately, you can take the documentation for the compiler and the library.
www.harlequin.com/products/ads/ml/ - Harlequin MLWorks, commercial compiler Standard ML. However, for non-commercial purposes, you can use the version with a few limited features for free.
caml.inria.fr — институт INRIA. Домашний сайт команды разработчиков языков Caml Light и Objective Caml. Можно бесплатно скачать дистрибутив Objective Caml, содержащий интерпретатор, компиляторы байт-кода и машинного кода, Yacc и Lex для Caml, отладчик и профайлер, документацию, примеры. Качество компилированного кода у этого компилятора очень хорошее, по скорости опережает даже Standard ML of New Jersey.
www.cs.kun.nl/~clean/ — содержит дистрибутив компилятора с языка Clean. Компилятор коммерческий, но допускается бесплатное использование в некоммерческих целях. Из того, что компилятор коммерческий, следует его качество (очень быстр), наличие среды разработчика, хорошей документации и стандартной библиотеки.
1. Хювёнен Э., Сеппенен И. Мир Lisp'а. В 2-х томах. М.: Мир, 1990.
2. Burge V. Methods of recursive programming. M .: Mechanical Engineering, 1983.
3. Field A., Harrison P. Functional programming. M .: Mir, 1993.
4. Henderson P. Functional programming. Application and implementation. M .: Mir, 1983.
5. Jones S., Lester D. Realization of functional languages. M .: Mir, 1991.
6. Henson M. Elements of functional languages. Dept. of CS. University of Sassex, 1990.
7. Fokker J. Functional programming. Dept. of CS. Utrecht University, 1995.
8. Thompson S. Haskell: The Craft of Functional Programming. 2-nd edition, Addison-Wesley, 1999.
9. Bird R. Introduction to Functional Programming using Haskell. 2-nd edition, Prentice Hall Press, 1998.
Comments
To leave a comment
Functional programming
Terms: Functional programming