Functional programming combines different approaches to defining computation processes based on fairly strict abstract concepts and methods of symbolic data processing.

A feature of functional programming languages ​​is that program texts in functional programming languages ​​describe “how to solve a problem”, but do not prescribe a sequence of actions for solving it. The main properties of functional programming languages: brevity, simplicity, strong typing, modularity, the presence of lazy (lazy) calculations.

Functional programming languages ​​include: Lisp, Miranda, Gofel, ML, Standard ML, Objective CAML, F#, Scala, Pythagoras, etc.

Procedural programming languages

A procedural programming language allows the programmer to define each step in the process of solving a problem. The peculiarity of such programming languages ​​is that tasks are divided into steps and solved step by step. Using a procedural language, the programmer defines language constructs to carry out a sequence of algorithmic steps.

Procedural programming languages: Ada, Basic, C, COBOL, Pascal, PL/1, Rapier, etc.

Stack programming languages

A stack programming language is a programming language that uses machine model stack. Stack-based programming languages: Forth, PostScript, Java, C#, etc. When using the stack as the main channel for passing parameters between words, language elements naturally form phrases (sequential chaining). This property brings these languages ​​closer to natural languages.

Aspect-oriented programming languages ​​5) Declarative programming languages ​​6) Dynamic programming languages ​​7) Educational languages programming 8) Interface description languages ​​9) Prototype programming languages ​​10) Object-oriented programming languages ​​11) Logical programming languages ​​12) Scripting programming languages ​​13) Esoteric programming languages

Standardization of programming languages. Programming Paradigm

The concept of a programming language is inextricably linked to its implementation. To ensure that compilation of the same program by different compilers always gives the same result, programming language standards are being developed. Standards organizations: American National Standards Institute ANSI, Institute of Electrical and Electronics Engineers IEEE, Organization international standards ISO.

When a language is created, a private standard is released, determined by the language developers. If a language becomes widespread, then over time different versions of compilers appear that do not exactly follow the particular standard. In most cases, there is an expansion of the initially fixed capabilities of the language. A consensus standard is being developed to bring the most popular implementations of the language into line with each other. Very important factor The standardization of a programming language is the timeliness of the appearance of the standard - before the wide distribution of the language and the creation of many incompatible implementations. In the process of language development, new standards may appear, reflecting modern innovations.

Programming Paradigms

Paradigm- a set of theories, standards and methods that together represent a way of organizing scientific knowledge - in other words, a way of seeing the world. By analogy, it is generally accepted that a paradigm in programming is a way of conceptualizing that defines how calculations should be carried out and how the work performed by a computer should be structured and organized.

There are several basic programming paradigms, the most important of which at the moment are the paradigms of directive, object-oriented and functional-logical programming. To support programming in accordance with a particular paradigm, special algorithmic languages ​​have been developed.

C and Pascal are examples of languages ​​designed for prescriptive programming, where the program developer uses a process-oriented model, that is, tries to create code that operates on data in the proper way. The active principle in this approach is considered to be a program (code) that must perform everything necessary to achieve desired result actions on passive data.

Programming technology as a process of developing software products created as an inextricable whole in the form of well-tested programs and teaching materials, describing their purpose and use.

Programming- process of creation computer programs. In a broader sense: the range of activities associated with the creation and maintenance of work. state of programs - computer software.

Programming technology- a set of methods and tools used in the software development process.

Programming technology is a set of technological instructions, including:

· indication of the sequence of technological operations;

· listing the conditions under which this or that operation is performed;

· descriptions of the operations themselves, where for each operation the initial data, results, as well as instructions, regulations, standards, criteria, etc. are defined.

Modern programming technology - component approach, which involves building software from individual components - physically separate pieces of software that interact with each other through standardized binary interfaces. Currently quality criteria a software product is considered to be:− functionality; − reliability;− ease of use;− efficiency(the ratio of the level of services provided by the software product to the user when given conditions, to the volume of resources used);− maintainability(characteristics of a software product that allow minimizing efforts to make changes to eliminate errors in it and to modify it in accordance with the changing needs of users); mobility(the ability of a software system to be transferred from one environment to another, in particular, from one computer to another).

An important step creation of a software product. testing and debugging.

Debugging− this is an activity aimed at detecting and correcting errors in software product using the execution processes of its programs.

Testing− this is the process of executing its programs on a certain set of data, for which the result of application is known in advance or the rules of behavior of these programs are known.

The following PS testing methods exist:

1) Static testing - manual testing of the program at the table.

2) Deterministic testing - with various combinations of source data.

3) Stochastic – ref. The data is selected randomly, and the output is determined by the quality of the results or an approximate estimate.

Programming styles.

A programming style is a set of programming techniques or methods that programmers use to produce programs that are correct, efficient, easy to use, and easy to read.

There are several programming styles:

1. Procedural programming is programming in which a program is a sequence of statements. Used in high-level languages ​​Basic, Fortran, etc.
2. Functional programming is programming in which a program is a sequence of function calls. Used in Lisp and other languages.
3. Logic programming – this is programming in which the program is a set of determination of relationships between objects. Used in Prolog and other languages.

Object-oriented programming– this is programming in which the basis of the program is an object that is a collection of data and rules for their transformation. Used in Turbo-Pascal, C++, etc.

The functions are abstractions, in which the implementation details of some action are hidden behind a separate name. A well-written set of functions allows them to be used many times. Standard Library Python comes with a wealth of pre-built and debugged functions, many of which are versatile enough to handle a wide variety of inputs. Even if a certain section of code is not used several times, but in terms of input and output data it is quite autonomous, it can be safely separated into a separate function.

This lecture is more oriented towards practical considerations rather than functional programming theory. However, where necessary, relevant terms will be used and explained.

Next, we will look in detail at the description and use of functions in Python, recursion, passing and returning functions as parameters, sequence processing and iterators, as well as the concept of a generator. It will be demonstrated that in Python, functions are objects (and therefore can be passed as parameters and returned as a result of executing functions). Besides, we'll talk about how you can implement some functional programming mechanisms that do not have direct syntactic support in Python, but are widespread in functional programming languages.

What is functional programming?

Functional programming is a programming style that uses only compositions of functions. In other words, this programming in expressions rather than imperative commands.

As David Mertz points out in his article on functional programming in Python, "functional programming - programming in functional languages ​​(LISP, ML, OCAML, Haskell, ...)", the main attributes of which are:

• “The presence of first-class functions” (functions, like other objects, can be transferred inside functions).
• Recursion is basic management structure in a programme.
• Processing lists (sequences).
• Prohibition of side effects in functions, which primarily means the absence of assignment (in “pure” functional languages)
• Operators are prohibited and the emphasis is on expressions. Instead of operators, the entire program is ideally one expression with accompanying definitions.
• Key question: What needs to be calculated, not How.
• Using functions of higher orders (functions over functions over functions).

Functional program

In mathematics, a function displays objects from the same set ( function definition sets) to another ( set of function values). Mathematical functions (they are called clean) “mechanically”, they unambiguously calculate the result from the given arguments. Pure functions should not store any data between two calls. You can think of them as black boxes, about which you only know what they do, but not at all how.

Functional style programs are designed as composition functions. In this case, functions are understood in almost the same way as in mathematics: they map one object to another. In programming, “pure” functions are an ideal that is not always achievable in practice. Practical useful functions usually have by-effect: Save state between calls or change the state of other objects. For example, it is impossible to imagine I/O functions without side effects. Actually, such functions are used for the sake of these “effects”. In addition, mathematical functions easily work with objects that require an infinite amount of information (for example, real numbers). In general, computer

• Translation

- The PLO will no longer be able to save us from the “Cloud Monsters.”

Translator's note: There are two concepts - parallelism (execution simultaneously, independently) and concurrency (execution in steps, one by one, but several tasks at the same time) and, as always, I had to rack my brains to find the right terms.

I will duplicate some words or terms in parentheses in the original in order to search using English terms Additional information, which will be many times larger.

You may have already heard such an expression as: “Clojure”, “Scala”, “Erlang” or even “Java now has lambdas”. And you have at least a vague idea of ​​“Functional Programming”. If you are a member of any programming community, then this topic may have already been discussed by you.

If you Google "Functional Programming" you won't see anything new. The second language created previously already covers this topic, it was created in the 50s and is called Lisp. Then why the hell did this topic become popular only now? Just 60 years later?

In the beginning, computers were very slow

Believe it or not, computers were much slower than the DOM. No, really. And at the same time, there were 2 main ideas in the agreement on the design and implementation of programming languages:

The first two have similar curricula, will introduce you to the basics of Functional Programming and are very suitable for beginners. The third of the links, this course on Computer Programming Paradigms, covers more than Functional Programming. It is important to note that these materials are for entry-level.

I've always wanted to write a series of articles on functional programming for this magazine, and I'm very glad that I finally got the opportunity. Even though my series on data analysis is still far from finished :). I will not announce the content of the entire series, I will only say that today we will talk about different programming languages ​​that support the functional style and corresponding programming techniques.

Programming languages ​​that not everyone knows about

I started programming as a child, and by the age of twenty-five it seemed to me that I knew and understood everything. Object oriented programming became part of my brain, every conceivable book on industrial programming was read. But I still had the feeling that I had missed something, something very subtle and incredibly important. The fact is that, like many in the nineties, at school I was taught to program in Pascal (oh yes, glory Turbo Pascal 5.5! - Approx. ed.), then there was C and C++. At the university, Fortran and then Java as the main tool at work. I knew Python and several other languages, but it was all wrong. But I did not have a serious education in the field of Computer Science. One day during a flight across the Atlantic, I couldn't sleep and I wanted to read something. Somehow, magically, I had a book about the Haskell programming language at my fingertips. It seems to me that it was then that I understood the true meaning of the expression “beauty requires sacrifice.”

Now, when people ask me how I learned Haskell, I say this: on an airplane. This episode changed my attitude towards programming in general. Of course, after the first acquaintance, many things seemed not entirely clear to me. I had to strain myself and study the issue more carefully. And you know, ten years have passed, many functional elements have become part of industrial languages, lambda functions already exists even in Java, type inference- in C++, pattern matching- in Scala. Many people think that this is some kind of breakthrough. And in this series of articles I will tell you about functional programming techniques using different languages ​​and their features.

Internet users often compile all sorts of lists and tops for the amusement of the public. For example, “a list of books you should read before you turn thirty.” If I were given the task of making a list of books on programming that you should read before you are any older, then the first place would certainly go to the book by Abelson and Sussman "Structure and interpretation of computer programs". Sometimes it even seems to me that the compiler or interpreter any language should stop anyone who has not read this book.

Therefore, if there is a language with which you need to start learning functional programming, it is Lisp. In general, this is a whole family of languages, which includes a now quite popular language for the JVM called Clojure. But it is not particularly suitable as a first functional language. For this it is better to use the language Scheme, which was developed at MIT and until the mid-2000s served as the main language for teaching programming. Although the introductory course with the same title as the book mentioned has now been replaced by a course on Python, it has still not lost its relevance.

I will try to briefly talk about the Scheme language and in general about the idea behind the languages ​​of this group. Despite the fact that Lisp is very old (of all high-level languages, only Fortran is older), it was in it that many programming methods used today first became available. In what follows, I will use the name Lisp, meaning a specific implementation - Scheme.

Syntax in two minutes

The syntax in Lisp is, hmm, a little controversial. The fact is that the idea underlying the syntax is extremely simple and is built on the basis of the so-called S-expressions. This is a prefix notation in which the familiar expression 2 + 3 is written as (+ 2 3) . This may seem strange, but in practice it gives some additional opportunities. By the way, (+ 2 10 (* 3.14 2)) also works :). Thus, the entire program is a collection of lists that use prefix notation. In the case of the Lisp language, the program itself and the abstract syntax tree - “if you know what I mean” 😉 - are essentially no different. Such a record makes parsing Lisp programs are very simple.
Since we are talking about a programming language, we should talk about how to define functions in this language.

Here we need to make a small digression. There is one subtlety, the significance of which is underestimated in modern literature. It is still necessary to separate a function in the mathematical sense and a function as we understand it in functional programming. The fact is that in mathematics, functions are declarative objects, and in programming they are used to organize the computation process, that is, in a sense, they rather represent imperative knowledge, knowledge that answers the question “how?” That is why Abelson and Sussman in their book very carefully separate this and call functions in programming procedures. This is not accepted in modern functional programming literature. But I still strongly recommend separating these two meanings of the word “function” at least in your head.

The easiest way to define a function is to write the following code. Let's start with something indecently simple:

(define (sq-roots a b c) (let ((D (- (* b b) (* 4 a c)))) (if (< D 0) (list) (let ((sqrtD (sqrt D))) (let ((x1 (/ (- (- b) sqrtD) (* 2.0 a))) (x2 (/ (+ (- b) sqrtD) (* 2.0 a)))) (list x1 x2))))))

Yes, it's exactly what you thought - solving a quadratic equation in Scheme. But this is more than enough to see all the features of the syntax. Here sq-roots is the name of the function from three formal parameters.

At first glance, the let construct, which is used to define local variables, has too many parentheses. But this is not true, we simply first define a list of variables, and then an expression in which these variables are used. Here (list) is empty list, which we return when there are no roots, and (list x1 x2) is a list of two values.

Now about expressions. In our sq-roots function we used an if construct. This is where functional programming comes in.

The point is that, unlike imperative languages ​​such as C, in functional languages ​​if is an expression, not a statement. In practice, this means that it cannot have an else branch. Because an expression must always have a meaning.

You can't talk about syntax without talking about syntactic sugar. In programming languages, syntactic sugar refers to constructs that are not necessary, but only make the code easier to read and reuse. To begin with, let's give a classic example from the C language. Many people know that arrays are not a necessary means of expression, since there are pointers. Yes, indeed, arrays are implemented through pointers, and a[i] for the C language is the same as *(a + i) . This example is generally quite unusual, with a funny effect associated with it: since the addition operation remains commutative in the case of pointers, the last expression is the same as *(i + a) , and this can be obtained by removing the syntactic sugar from expressions i[a] ! The operation of removing syntactic sugar in English language called a special word desugaring.

Returning to the Scheme language, there is an important example of syntactic sugar. To define variables, as in the case of functions, a keyword is used (in Lisp and Scheme this is called special form) define . For example, (define pi 3.14159) defines the variable pi. Generally speaking, you can define functions in exactly the same way:

(define square (lambda (x) (* x x)))

this is the same as

(define (square x) (* x x))

The last line looks a little easier to read compared to the version that uses a lambda expression. However, it is clear that it is enough to have the first option, and the second is optional. Why is the first one more important? Because one of the most basic properties of functional languages ​​is that functions in them are first-class objects. The latter means that functions can be passed as an argument and returned as a value.

If you look at let from the point of view of a lambda expression, you can easily notice the following correspondence:

(let ((x 5) (y 2)) (* x y)) (apply (lambda (x y) (* x y)) (list 5 2))

Functional programming

There are functional languages clean And unclean. Pure functional languages ​​are relatively rare, they include primarily Haskell And Clean. Pure languages ​​have no side effects. In practice, this means no assignment or I/O as we are used to. This creates a number of difficulties, although in the languages ​​already mentioned this is solved quite cleverly, and in these languages ​​they write code with a lot of input/output. Languages ​​like Lisp, OCaml or Scala allow functions with side effects, and in this sense these languages ​​are often more practical.

Our task is to learn the basic techniques of functional programming in Scheme. Therefore, we will write purely functional code, without using a generator random numbers, I/O and set! , which will allow you to change the values ​​of variables. You can read about all this in the book SICP. Now let's focus on the most important for us.

The first thing that confuses a beginner about functional programming is the lack of loops. But what should we do? Many of us are taught that recursion is bad. This is argued by the fact that recursion in conventional programming languages ​​is usually implemented inefficiently. The point is that in the general case one should distinguish between recursion as a technical technique, that is, calling a function from itself, and recursion as a process. Functional languages ​​support optimization of tail recursion or, as it is sometimes called, accumulator recursion. This can be illustrated with a simple example.

Let's say we have two functions - succ and prev. The first returns a number 1 greater than the argument, and the second returns 1 less. Now let's try to define the addition operation in two ways:

(define (add x y) (if (eq? y 0) x (add (succ x) (prev y)))) (define (add-1 x y) (if (eq? y 0) x (succ (add- 1 x (prev y)))))

What is the difference between the first and second case? The fact is that if we consider the calculation method for the first case step by step, we can see the following:

(add 3 4) => (add 4 3) => (add 5 2) => (add 6 1) => (add 7 0) => 7

In the second case we will have something like this:

(add-1 3 4) => (succ (add-1 3 3)) => (succ (succ (add-1 3 2))) => (succ (succ (succ (add-1 3 1)) )) => (succ (succ (succ (succ (add-1 3 0))))) => (succ (succ (succ (succ 3)))) => (succ (succ (succ 4))) => (succ (succ 5)) => (succ 6) => 7

Despite the fact that in both cases the result is the same, the calculation process is radically different. In the first case, the amount of memory used does not change, but in the second it increases linearly. The first process is iterative, and second - recursive. Yes, for writing effective programs In functional languages, tail recursion must be used to avoid stack overflow.

Lists

One of essential elements functional programming, along with recursion, - lists. They provide the basis for complex structures data. As in other functional languages, lists are simply linked in a head-to-tail fashion. The cons function is used to create a list, and the car and cdr functions are used to access the head and tail of the list, respectively. So, the list (list 1 2 3) is nothing more than (cons 1 (cons 2 (cons 3 "()))). Here "() is an empty list. So a typical list processing function looks like this:

(define (sum lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))

This function simply sums the elements of a list. Many list processing functions look like this; in one of the following articles I will tell you why. For now, I’ll just note that if we replace the first argument in addition with 1, we get a function that calculates the length of the list.

Higher order functions

Since functions can be passed as arguments and returned as a value, it would be nice to find a use for this. Consider the following classic example:

(define (map f lst) (if (null? lst) lst (cons (f (car lst)) (map f (cdr lst)))))

The map function applies the f function to each element of the list. As strange as it may seem, we can now express the function for calculating the length of a list length in terms of sum and map:

(define (length lst) (sum (map (lambda (x) 1) lst)))

If you suddenly decided now that all this is somehow too simple, then let’s think about this: how to implement lists using higher-order functions?

That is, you need to implement the functions cons , car and cdr so that they satisfy the following relation: for any list lst it is true that the value (cons (car lst) (cdr lst)) coincides with lst . This can be done as follows:

(define (cons x xs) (lambda (pick) (if (eq? pick 1) x xs))) (define (car f) (f 1)) (define (cdr f) (f 2))

How it works? Here the cons function returns another function which has one parameter and depending on that returns either the first or second arguments. It is easy to check that the required relationship holds for these functions.

Using quote and metaprogramming

One nice feature of the Lisp language is that it is extremely convenient for writing programs that convert other programs. The fact is that a program consists of lists, and a list is the main data structure in the language. There is a way to simply “quote” the text of a program so that it is perceived as a list of atoms.

Atoms are simply character expressions, for example ("hello "world) , which is the same as "(hello world) , or in the full form (quote (hello world)) . Although most Lisp dialects have strings , sometimes you can get by with quote . More importantly, using this approach you can simplify code generation and program processing.

First, let's try to understand symbolic calculations. This is usually understood as computer algebra systems that are capable of handling symbolic objects, formulas, equations and other complex mathematical objects (there are many such systems, the main examples being systems Maple And Mathematica).

You can try to implement symbolic differentiation. I think everyone who is close to finishing school can imagine the rules of differentiation (although in reality everything is a little more complicated - here we will calculate the partial derivative by simply counting other variables are constants, but this does not complicate the matter at all).

So I'll just give an example of code that would show the essence of the matter, leaving the details to the reader (who, I hope, will carefully study the book "Structure and Interpretation of Computer Programs").

(define (deriv exp var) (cond ((number? exp) 0) ((variable? exp) (if (same-variable? exp var) 1 0)) ((sum? exp) (make-sum (deriv ( addend exp) var) (deriv (augend exp) var))) ((product? exp) (make-sum (make-product (multiplier exp) (deriv (multiplicand exp) var)) (make-product (deriv (multiplier exp) var) (multiplicand exp)))) (else (error "unknown expression type - DERIV" exp))))

Here the deriv function is an implementation of the differentiation algorithm as taught in school. This function requires implementation of number functions? ,variable? and so on, which allow us to understand what nature this or that element of expression has. You also need to implement additional functions make-product and make-sum. Here we use the cond construction, which is still unknown to us - this is an analogue of the switch operator in programming languages ​​such as C and Java.

Before we move on to implementing the missing features, it is worth noting that functional programming quite often uses a top-down development approach. This is when the most general functions are written first, and then small functions that are responsible for implementation details.

(define (variable? x) (symbol? x)) (define (same-variable? v1 v2) (and (variable? v1) (variable? v2) (eq? v1 v2))) (define (make-sum a1 a2) (list "+ a1 a2)) (define (make-product m1 m2) (list "* m1 m2)) (define (sum? x) (and (pair? x) (eq? (car x) "+ ))) (define (addend s) (cadr s)) (define (augend s) (caddr s)) (define (product? x) (and (pair? x) (eq? (car x) "*)) ) (define (multiplier p) (cadr p)) (define (multiplicand p) (caddr p))

The implementation of these functions does not require special comments, with the possible exception of the cadr and caddr functions. These are nothing but functions that return the second and third elements of a list respectively.

If you use the interactive Scheme interpreter, you can easily verify that the resulting code works correctly, but without simplifying the expressions:

(deriv "(+ x 3) "x) => (+ 1 0) (deriv "(* (* x y) (+ x 3)) "x) => (+ (* (* x y) (+ 1 0 )) (* (+ (* x 0) (* 1 y)) (+ x 3)))

For trivial cases (for example, multiplication by 0), the simplification problem is solved quite easily. This question is left to the reader. Most of the examples in this article are taken from the SICP book, so if you have any difficulties, you can simply refer to the source (the book is in the public domain).

Like any dialect, Lisp has great metaprogramming capabilities, mostly related to the use of macros. Unfortunately, this issue requires analysis in a separate article.

Let's write a function that will remove syntactic sugar from the function definition as discussed earlier:

(define (desugar-define def) (let ((fn-args (cadr def)) (body (caddr def))) (let ((name (car fn-args)) (args (cdr fn-args))) (list "define name (list "lambda args body)))))

This function works great with well-formed function definitions:

(desugar-define "(define (succ x) (+ x 1))) => (define succ (lambda (x) (+ x 1)))

However, this doesn't work for regular definitions like (define x 5) .
If we want to remove syntactic sugar in a large program containing many different definitions, then we must implement additional check:

(define (sugared? def) (and (eq? (car def) "define) (list? (cadr def))))

Such a check can be built directly into the desugar-define function, making sure that if the definition does not need to remove syntactic sugar, it simply does not change (this trivial exercise is left to the reader). Then you can wrap the entire program in a list and use map:

(map desugar-define prog)

Conclusion

In this article, I did not set myself the task of talking about Scheme in any detail. First of all, I wanted to show several interesting features of the language and attract the reader to study functional programming. This wonderful language, despite its simplicity, has its own charm and features that make programming in it very exciting. As for the tool for working with Scheme, the strong-willed can swing at MIT-Scheme, and the rest - enjoy an excellent learning environment Dr. Racket. In one of the following articles I will definitely tell you how to write your own Scheme interpreter.

Lazy calculations

In traditional programming languages ​​(such as C++), calling a function causes all arguments to be evaluated. 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 is lost, therefore, the calculation was done 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 the conjunction operator from C++ (&&), which does not evaluate the value of the second argument if the first argument is false.

If a functional language does not support lazy evaluation, then it is called strict. In fact, in such languages ​​the order of evaluation is strictly defined. Examples of strict languages ​​include Scheme, Standard ML, and Caml.

Languages ​​that use lazy evaluation are called non-strict. Haskell is a loose language, just like Gofer and Miranda, for example. Lax languages ​​are often pure.

Very often, strict languages ​​include support for some of the useful features found in non-strict languages, such as infinite lists. Standard ML comes with a special module to support deferred calculations. In addition, Objective Caml supports the additional reserved word lazy and a construct for lists of values ​​calculated as needed.

This section provides a brief description of some (very few) functional programming languages.

§ Lisp(List processor). It is considered the first functional programming language. Untyped. It contains a lot of imperative properties, but in general it encourages the functional style of programming. Uses call-by-value for calculations. There is an object-oriented dialect of the language - CLOS.

§ ISWIM(If you See What I Mean). Functional language prototype. Developed by Landin in the 60s of the 20th century to demonstrate what a functional programming language could be. Along with the language, Landin also developed a special virtual machine for executing programs on ISWIM. This call-by-value virtual machine is called a SECD machine. The syntax of many functional languages ​​is based on the syntax of the ISWIM language. The syntax of ISWIM is similar to that of ML, especially Caml.

§ Scheme. A Lisp dialect intended for scientific research in the field of computer science. Scheme was designed with an emphasis on elegance and simplicity of the language. This makes the language much smaller than Common Lisp.

§ M.L.(Meta Language). A family of strict languages ​​with a developed polymorphic type system and parameterizable modules. ML is taught in many Western universities (some even as the first programming language).

§ Standard ML. One of the first typed functional programming languages. Contains some imperative properties such as links to changeable values and therefore is not pure. Uses call-by-value for calculations. A very interesting implementation of modularity. Powerful polymorphic type system. The latest language standard is Standard ML-97, for which there are formal mathematical definitions syntax, as well as static and dynamic semantics of the language.

§ Caml Light And Objective Caml. Like Standard ML, it belongs to the ML family. Objective Caml differs from Caml Light mainly in its support for classic object-oriented programming. Just like Standard ML is strict, but has some built-in support for lazy evaluation.

§ Miranda. Developed by David Turner as a standard functional language that used lazy evaluation. It has a strict polymorphic type system. Like ML, it is taught in many universities. He had a great influence on the developers of the Haskell language.

§ Haskell. One of the most common non-strict languages. It has a very developed typing system. The module system is somewhat less well developed. The latest language standard is Haskell-98.

§ Gofer(GOod For Equational Reasoning). Simplified Haskell dialect. Designed for teaching functional programming.

§ Clean. Specifically designed for parallel and distributed programming. The syntax is similar to Haskell. Clean. Uses deferred calculations. The compiler comes with a set of libraries (I/O libraries) that allow you to program a graphical user interface under Win32 or MacOS.

Let us recall that the most important characteristic The functional approach is the fact that any program developed in a functional programming language can be considered as a function, the arguments of which may also be functions.

The functional approach gave rise to a whole family of languages, the ancestor of which, as already noted, was the LISP programming language. Later, in the 70s, the original version of the ML language was developed, which subsequently developed, in particular, into SML, as well as a number of other languages. Of these, perhaps the “youngest” is the Haskell language, created quite recently, in the 90s.

An important advantage implementation of functional programming languages ​​is automated dynamic distribution computer memory for storing data. In this case, the programmer gets rid of the need to control the data, and if necessary, can run the “garbage collection” function - clearing memory from data that the program will no longer need.

Complex programs in the functional approach are built by aggregating functions. In this case, the program text is a function, some of the arguments of which can also be considered as functions. Thus, code reuse comes down to calling a previously described function, the structure of which, unlike an imperative language procedure, is mathematically transparent.

Because a function is a natural formalism for functional programming languages, implementing various aspects of function-related programming is greatly simplified. Writing recursive functions becomes intuitively transparent, i.e. functions that call themselves as an argument. The implementation of processing recursive data structures also becomes natural.

Due to the implementation of a pattern matching mechanism, functional programming languages ​​such as ML and Haskell are good for symbolic processing.

Naturally, functional programming languages ​​are not without some disadvantages.

These often include the nonlinear structure of the program and the relatively low efficiency of implementation. However, the first drawback is quite subjective, and the second has been successfully overcome by modern implementations, in particular, a number of recent SML language translators, including a compiler for the Microsoft .NET environment.

To develop professional software in functional programming languages, you need to deeply understand the nature of the function.

Note that the term “function” in mathematical formalization and software implementation refers to different concepts.

Thus, a mathematical function f with a domain of definition A and a range of values ​​B is the set of ordered pairs

such that if

(a,b 1) f and (a,b 2) f,

In turn, a function in a programming language is a construct of this language that describes the rules for converting an argument (the so-called actual parameter) into a result.

To formalize the concept of “function,” a mathematical theory known as lambda calculus was constructed. More precisely, this calculus should be called the calculus of lambda conversions.

Conversion refers to the transformation of calculus objects (and in programming, functions and data) from one form to another. The initial task in mathematics was the desire to simplify the form of expressions. In programming, this particular task is not so significant, although, as we will see later, the use of lambda calculus as the initial formalization can help simplify the type of program, i.e. lead to program code optimization.

In addition, conversions provide a transition to newly introduced notations and, thus, allow one to represent the subject area in a more compact or more detailed form, or, in mathematical language, change the level of abstraction in relation to subject area. This feature is also widely used by object-oriented and structured-modular programming languages ​​in the hierarchy of objects, program fragments and data structures. The interaction of application components in .NET is based on the same principle. It is in this sense that the transition to new notations is one of the most important elements of programming in general, and it is lambda calculus (unlike many other branches of mathematics) that represents an adequate way to formalize renotations.

Let us systematize the evolution of the theories underlying the modern approach to lambda calculus.

Let's consider the evolution of programming languages ​​developing within the framework of the functional approach.

Early functional programming languages, which originate from the classic LISP (LISt Processing) language, were designed to process lists, i.e. symbolic information. In this case, the main types were an atomic element and a list of atomic elements, and the main emphasis was on analyzing the contents of the list.

The development of early programming languages ​​became functional programming languages ​​with strong typing, a typical example here is the classic ML, and its direct descendant SML. In strongly typed languages, every construct (or expression) must have a type.

However, in later functional programming languages ​​there is no need for explicit type assignment, and the types of initially undefined expressions, as in SML, can be inferred (before the program is run) based on the types of the expressions associated with them.

The next step in the development of functional programming languages ​​was the support of polymorphic functions, i.e. functions with parametric arguments (analogues mathematical function with parameters). In particular, polymorphism is supported in SML, Miranda and Haskell.

At the present stage of development, “new generation” functional programming languages ​​have emerged with the following advanced capabilities: pattern matching (Scheme, SML, Miranda, Haskell), parametric polymorphism (SML) and so-called “lazy” (as needed) calculations (Haskell, Miranda, S.M.L.).

The family of functional programming languages ​​is quite large. This is evidenced not so much by the significant list of languages, but by the fact that many languages ​​have given rise to entire trends in programming. Let us recall that LISP gave rise to a whole family of languages: Scheme, InterLisp, COMMON Lisp, etc.

The SML programming language was no exception, which was created in the form of the ML language by R. Milner at MIT (Massachusetts Institute of Technology) and was originally intended for logical deductions, in particular, theorem proving. The language is strictly typified and lacks parametric polymorphism.

The development of “classical” ML has become three modern languages ​​with almost identical capabilities (parametric polymorphism, pattern matching, “lazy” calculations). This is the SML language, developed in the UK and the USA, CaML, created by a group of French scientists at the INRIA Institute, SML/NJ - a dialect of SML from New Jersey, and also a Russian development - mosml (the "Moscow" dialect of ML).

The proximity to mathematical formalization and the initial functional orientation caused the following advantages of the functional approach:

1. ease of testing and verification of program code based on the possibility of constructing a rigorous mathematical proof of the correctness of programs;

2. unification of the presentation of the program and data (data can be encapsulated in the program as function arguments, the designation or calculation of the function value can be done as needed);

3. safe typing: invalid data operations are excluded;

4. dynamic typing: typing errors can be detected at runtime (the lack of this property in early functional programming languages ​​can lead to overflow random access memory computer);

5. independence of the software implementation from the machine representation of data and the system architecture of the program (the programmer is focused on the details of the implementation, and not on the features of the machine representation of data).

Note that realizing the benefits that functional programming languages ​​provide depends significantly on the choice of software and hardware platform.

If .NET technology is chosen as the software platform, almost regardless of the hardware implementation, the programmer or manager software project additionally receives the following benefits:

1. integration different languages functional programming (this makes maximum use of the advantages of each of the languages, in particular, Scheme provides a pattern matching mechanism, and SML provides the ability to calculate as needed);

2. integration of various approaches to programming based on the cross-language Common Language Infrastructure, or CLI (in particular, it is possible to use C# to provide the advantages of an object-oriented approach and SML - functional, as in this course);

3. common unified typing system Common Type System, CTS (uniform and safe management types of data in the program);

4. multi-stage, flexible system for ensuring the security of program code (in particular, based on the assembly mechanism).

The main features of functional programming languages ​​that distinguish them from both imperative languages ​​and logic programming languages ​​are referential transparency and determinism. In functional languages, there is significant variation in parameters such as typing and calculation rules. In many languages, the order of evaluation is strictly defined. But sometimes strict languages ​​contain means to support some useful elements, inherent in non-strict languages, for example, infinite lists (Standard ML has a special module to support lazy calculations). In contrast, non-strict languages ​​allow energetic computation in some cases.

Thus, Miranda has lazy semantics, but allows you to specify strict constructors by marking the constructor arguments in a certain way.

Many modern functional programming languages ​​are strongly typed languages ​​(strong typing). Strong typing provides greater security. Many errors can be corrected at the compilation stage, so the debugging stage and overall program development time are reduced. Strong typing allows the compiler to generate more efficient code and thus speed up program execution. Along with this, there are functional languages ​​with dynamic typing. The data type in such languages ​​is determined during program execution (Chapter 3). They are sometimes called "typeless". Their advantages include the fact that programs written in these languages ​​have greater generality. A disadvantage can be considered the attribution of many errors to the program execution stage and the associated need to use type checking functions and a corresponding reduction in the generality of the program. Typed languages ​​contribute to the generation of more “reliable” code, while typed languages ​​produce more “general” code.

The next criterion by which functional programming languages ​​can be classified may be the presence of imperative mechanisms. At the same time, it is customary to call functional programming languages ​​that are devoid of imperative mechanisms “pure”, and those that have them are called “impure”. In the overview of functional programming languages ​​below, programming languages ​​will be referred to as "practical" and "academic". By “practical” languages ​​we mean languages ​​that have a commercial application (they were used to develop real applications or there were commercial programming systems). Academic programming languages ​​are popular in research circles and in the field computer education, but there are practically no commercial applications written in such languages. They remain just a tool for conducting theoretical research in the field of computer science and are widely used in the educational process.

A list of the most popular functional programming languages ​​is given below using the following criteria: general information; typing; type of calculation; purity.

Common Lisp. The version of Lisp, which since 1970 can be considered the language standard, thanks to the support of the artificial intelligence laboratory of the Massachusetts Institute of Technology, is typeless, energetic, with a large set of imperative inclusions, allowing assignment, destruction of structures. Practical. Suffice it to say that vector graphics editor Autocad.

Scheme. A Lisp dialect intended for scientific research in computer science and teaching functional programming. Thanks to the lack of imperative inclusions, the language is much smaller than Common Lisp. Dating back to a language developed by J. McCarthy in 1962. Academic, typeless, energetic, clean.

Refal. A family of languages ​​developed by V. F. Turchin. The oldest member of this family was first realized in 1968 in Russia. It is still widely used in academic circles. Contains logic programming elements (pattern matching). Therefore, the Refal language is proposed in this textbook as a language for self-study.

Miranda. Strongly typed, supports user data types and polymorphism. Developed by Turner based on the earlier SALS and KRC languages. Has lazy semantics. No imperative inclusions.

Haskell. The development of the language occurred at the end of the last century. Widely known in academic circles. In some Western universities it is used as the main language for students to study. One of the most powerful functional languages. Lazy language. Purely functional language. Typed. Haskell is a great tool for learning and experimenting with complex functional data types. Programs written in Haskell have a significant object code size and low execution speed.

Clean. A Haskell dialect tailored to the needs of practical programming. Like Haskell, it is a lazy, purely functional language, containing type classes. But Clean also contains interesting features, which have no equivalent in Haskell. For example, imperative features in Clean are based on unique types, the idea of ​​which is borrowed from linear logic. Clean contains mechanisms that can significantly improve the efficiency of programs. These mechanisms explicitly suppress lazy computation. The Clean implementation is a commercial product, but a free version is available for research and educational purposes.

ML(Meta Language). Developed by a group of programmers led by Robert Milier in the mid-70s. in Edinburgh (Edinburgh Logic for Computable Functions). The idea of ​​the language was to create a mechanism for constructing formal proofs in a system of logic for computable functions. In 1983 the language was revised to include concepts such as modules. Came to be called standard ML. ML is strong typed language with static type checking and applicative program execution. It has gained great popularity in research circles and in the field of computer education.