Functional programming for all

Good day. This article is a translation of a post that interested me in a postgraduate blog at the State University of New York at Stony Brook. The article in an accessible form describes the basic concepts of functional programming, their advantages and disadvantages. I think it will be useful to a wide circle of readers who doubt whether they need to delve into the world of functional programming or not. Suggestions, suggestions and comments on the translation and terminology are accepted by personal mail.

The opinion of the translator may sometimes not coincide with the opinion of the author, but translating the article was extremely entertaining.

UPD: you can find an alternative translation on rsdn (thanks to flamingo for the link).

Monday, June 19, 2006
')

Introduction

Programmers are procrastinators (i.e., lazy). Come, make coffee, check your email, read the RSS feed, read the news, check out the latest articles on the technical website, look through the political discussions on the programmer's forum. Wash off, repeat to not miss anything. Go for lunch. Return, bump into IDE for a few minutes. Check mail. Make coffee. And suddenly the day comes to an end.

But from time to time in the field of view are entertaining (difficult, promising) articles and blog posts. If you are looking in the right place, then at least one such article will appear every few days. These posts are difficult to understand, this takes time, so they accumulate in the folder "Read". Before you have time to understand what's what, it turns out that a bunch of links have already accumulated and a folder full of PDF files. It will take you a whole year and a hut in the middle of the forest, where there is not a soul for miles to figure it all out. And it is advisable that someone bring food every morning and pick up trash while you walk to the river.

I do not know what your list is, but most of my list is about functional programming. Such articles are usually the most complex. Often they are written in a dry academic language, and even the “Wall Street veterans with ten years of experience” do not understand what is said in the articles on functional programming (AF). If you ask a project manager in Citi Group or Deutsche Bank ^[1] why they chose JMS instead of Erlang, you will hear in reply that they cannot use academic language for industrial development. The problem is that the majority of complex systems with the most stringent requirements were written using functional programming elements. Something does not converge.

Indeed, articles on FP are difficult to understand, but they can be written more simply. The reason for the abyss of knowledge is purely historical. In fact, the concept of OP is nothing complicated. Look at this article as an “accessible guide to OP”, as if it were a bridge between our imperative minds and the world of OP. Make a cup of coffee and continue. I hope that very soon colleagues will start joking about your AF comments.

So what is OP? Where did it come from? What is it suitable for? If it is really as useful as the advocates of AF say, why not use it more often on an industrial scale? Why do only people with PhD lean towards functional languages? But more importantly, why is it so damn difficult to master functional languages? What lies behind all these closures, continuations, currying, lazy calculations and the absence of side effects? How can all this be used in a project that does not cover the whole universe? Why is it all so far from the good that is holy and dear to our imperative hearts? Soon we will figure everything out. To begin with, let us understand the reason for the huge gap between academic articles and the real world. To answer this question is enough to walk in the park.

Walk in the park

Get in the time machine. Our walk in the park took place more than 2 thousand years ago in one of those sunny days of the long-forgotten spring of 380 BC. Outside the city walls of Athens, under the gentle shadows of olive trees, Plato strolled in the direction of the Academy with a beautiful boy slave. It was a wonderful weather, dinner was given a pleasant weight in the stomach, and the conversation smoothly turned to philosophical topics.

“Look at those two students,” Plato said, carefully choosing the words to give the question educational meaning. “Which of them do you think is higher?” The boy, the slave, looked towards the pool, near which there were two people. "They are about the same height," replied the boy. “What do you mean by the words 'approximately one height'?”, Asked Plato. “Well, from here they look the same, but I’m sure that if we get closer, I can see the difference in height.”

Plato smiled. He led the boy in the right direction. “So you want to say that there are no ideally coinciding things in the world?” The boy became thoughtful and answered: “Yes, I think so. There is always a little difference, even if we can't see it. ”He got to the bottom of it! “Then if there are no ideally coinciding things in this world, then how do you understand the concept of 'ideal' equality?” This put the boy in a stupor. He replied: "I do not know."

Thus was born the first attempt to understand the nature of mathematics. Plato suggested that in our world everything is just an approximation of the ideal. He also realized that people are able to understand the concept of an ideal, although they have never come across it. He came to the conclusion that the ideal mathematical forms must exist in another world, and that we somehow know about them from the connections with this “alternative” universe. Obviously, we cannot see the perfect circle. But at the same time, we understand what a perfect circle is and how it can be described mathematically. What then is math? Why is the universe described by mathematical laws? Can everything be described by mathematics? ^[2]

The philosophy of mathematics is a very complex subject. Like most philosophical disciplines, she asks questions rather than answers them. Scientists for the most part agree with the fact that mathematics is a real puzzle: it is based on a set of basic consistent principles and a set of rules on how to operate on these principles. Then we can combine the rules, getting more and more complex laws. Mathematicians call this method a "formal system" or "calculus." For example, you can build a formal system for Tetris. In essence, a working Tetris is itself a formal system, it is simply written in an unusual form.

The civilization of fluffy creatures with Alpha Centauri cannot read our formal Tetris system or circle, because their only sense organ can smell only odors. They may never build Tetris, but they will probably have a formal system for the circle. Most likely, we will not be able to get acquainted with it, since our sense of smell is not so developed. But as soon as the representation language is deciphered (by various sensory instruments and standard reverse engineering), the basic concepts will become clear to any intellectually developed civilization.

Even if not a single intelligent civilization existed in the universe, the formal system for Tetris and the circle would still be logically correct. Simply, there would be no creatures capable of finding and formalizing these systems. If a sensible alien race suddenly appears, they will most likely develop their formal system for describing the universe. Of course, it is unlikely that they will invent Tetris, because in the universe there are no analogues to this game. Tetris is one example of a huge number of formal systems, riddles that are not related to the surrounding reality. Even the concept of natural numbers can not always be attributed to the real world, because you can imagine such a large number that it can not be applied to anything in the universe, but it will be finite.

A bit of history ^[3]

Let's turn the wheels of our time machine and move a little closer in the 1930s. The Great Depression devastated the New and Old World. Almost all families from all social groups felt a huge economic recession. There are very few shelters in which people could not fear poverty. Some people are lucky enough to be in such shelters. We are interested in mathematics at Princeton University.

New buildings built in the Gothic style gave the university an aura of security. Logicians from across the country were invited to Princeton to establish a new unit. While most Americans were struggling to feed themselves, high ceilings, wood-patterned walls, daily discussions over a cup of tea, and walks in the woods made up living conditions at Princeton.

One of the mathematicians who lived in such a wasteful lifestyle was a young man named Alonzo Church. Alonzo received a bachelor's degree from Princeton and was persuaded to remain in graduate school. Alonzo felt the setting was too luxurious. He rarely appeared on the discussion of mathematical problems over a cup of tea and did not like to walk in the woods. Alonzo was a loner: he was more prolific when he worked alone. Nevertheless, he regularly met with other inhabitants of Princeton. Among them were Alan Turing, John von Neumann, and Kurt Gödel.

These four were interested in formal systems. They did not pay much attention to the physical world, they were interested in working with abstract math puzzles. There was something in common in their puzzles: mathematicians studied questions of computation. If we have a machine with infinite computational capabilities, what tasks can be solved on it? Is it possible to solve problems automatically? Are there unsolvable problems and why? Will the machines with different architecture have the same power?

Together with other scientists, Alonzo developed a formal system called Lambda calculus. The system was essentially a programming language for one of the imaginary machines. It was based on functions that take functions as arguments, and return a function. Such a function was designated by the Greek letter Lambda, which gave the name to the whole system ^[4] . Using this system, Alonzo managed to build reasoning about the above questions and to derive answers to them.

Regardless of Alonzo, Alan Turing conducted a similar study. He developed another formal system (which is now called the Turing Machine), and using it came to conclusions similar to Alonzo. Later it was proved that the Turing machine and the Lyabda calculus have the same power.

At this point, our story stops. I would summarize the article, and you would switch to another page if World War II had not started. The world was on fire. US troops very intensively used artillery. To improve accuracy, the army hired a large group of mathematicians who constantly solved the differential equations necessary for ballistic firing tables. It quickly became clear that such a task was too difficult for a manual solution; special equipment was developed to overcome this problem. The first ballistic table machine was the Mark I built by IBM - it weighed 5 tons, consisted of 750'000 parts and could perform 3 operations per second.

The race, of course, did not end there. In 1949, the Electronic Discrete Variable Automatic Computer (EDVAC) was shown to the public. It was the first example of the implementation of the von Neumann architecture, and was the first truly working Turing machine. For some time, Alonzo Church’s work was set aside.

At the end of the 50s, MIT professor John McCarthy, also a graduate of Princeton, began to show interest in the work of Alonzo Church. In 1958, he introduced the list processing language, Lis t P rocessing language (Lisp). Lisp was conceived as an implementation of the Alonzo Lambda calculus, which runs on von Neumann computers. Many computer scientists have noted Lisp's expressive power. In 1973, a group of programmers in an artificial intelligence laboratory at the Massachusetts Institute of Technology developed iron, which they called the Lisp machine. It was a hardware implementation of Alonzo lambda calculus.

Functional programming

— . - , - . , , — , . , . Java (, Java ). Java , . .

, . , , , , , . — . , . . — (alias) ( ). . . Java , final ( const C++). -final

final int i = 5;
final int j = i + 3;

, . final, … . Java: , .

, , , - . , ! . -, , . . , , . , . ?

, , . . , . , , . , , Java . , final ^[5].

String reverse(String arg) {
    if(arg.length == 0) {
        return arg;
    }
    else {
        return reverse(arg.substring(1, arg.length)) + arg.substring(0, 1);
    }
}

, ^[6]. , . . , . , .

, , , . , . . . . , , . , , — . , .

Unit

, . , , ( ). , — . , — , .

, unit-. . . , , . Unit-, , . Java C++ — , . .

, , — . , , . . , , - , . — , , , .

, — . . , . , . , , , . , ! , , , . , , . , — !

, . , . !

- . deadlock- (race conditions) ! . , , .

, ? , . Ericsson Erlang . Erlang- . , , , Wall Street. -, Erlang, , Java . Erlang .

. , , CPU. .

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

, , s1 s2, , . , , , . — , inline! . CPU . . , , . . 100% .

Windows . . . Windows XP , ( Windows Update , ). Unix . , . , . 100% , - , . Wall Streets , .

. [. Smalltalk- ]. Java . , , , . , . , , , , . , . . , .

. ! — , . ! , , . , Erlang, .

(Machine Assisted Proofs and Optimizations)

, . — , , . , , , , ^[7]. . .

, . , Unit- ! (rock solid systems). . , .

, , , « , , , final». . final , Java. , , , - . — .

— , Java C. — , Java . C:

int add(int i, int j) {
    return i + j;
}

, C . Java , . Java ( , final):

class add_function_t {
    int add(int i, int j) {
        return i + j;
    }
}

add_function_t add = new add_function_t();

add . . add . . add_function_t runtime , . , . , ( ) . . Java , ( ). « », , Java .

? , . . , - , ( ). , , . ? .

, Java , , .

    void handleMessage(Message msg) {
        // ...
        msg.setClientCode("ABCD_123");
        // ...
        
        sendMessage(msg);
    }
    
    // ...
}

, , . , — . ? , , . :

class MessageHandler {
    void handleMessage(Message msg) {
        // ...
        if(msg.getDestination().equals("server1") {
            msg.setClientCode("ABCD_123");
        } else {
            msg.setClientCode("123_ABC");
        }
        // ...
        
        sendMessage(msg);
    }
    
    // ...
}

. , . MessageHandler :

abstract class MessageHandler {
    void handleMessage(Message msg) {
        // ...
        msg.setClientCode(getClientCode());
        // ...
        
        sendMessage(msg);
    }
    
    abstract String getClientCode();
    
    // ...
}


class MessageHandlerOne extends MessageHandler {
    String getClientCode() {
        return "ABCD_123";
    }
}


class MessageHandlerTwo extends MessageHandler {
    String getClientCode() {
        return "123_ABCD";
    }
}

. . . ! :

class MessageHandler {
    void handleMessage(Message msg, Function getClientCode) {
        // ...
        Message msg1 = msg.setClientCode(getClientCode());
        // ...
        
        sendMessage(msg1);
    }
    
    // ...
}


String getClientCodeOne() {
    return "ABCD_123";
}


String getClientCodeTwo() {
    return "123_ABCD";
}


MessageHandler handler = new MessageHandler();
handler.handleMessage(someMsg, getClientCodeOne);

. . , - , . - : runtime , . - «» ! . , .

, , « » . , - , . . .

. , , , . ( ? , - , ). .

«» Java — . . , . :

int pow(int i, int j);
int square(int i)
{
    return pow(i, 2);
}

, , , . ( (Haskell Curry), , ). , , , . — , ( ).

. , . . , .

square = int pow(int i, 2);

. pow, 2 . Java, :

class square_function_t {
    int square(int i) {
        return pow(i, 2);
    }
}
square_function_t square = new square_function_t();

, . . , ! , , ().

( ) — , . , :

String s1 = somewhatLongOperation1();
String s2 = somewhatLongOperation2();
String s3 = concatenate(s1, s2);

. , : somewhatLongOperation1, somewhatLongOperation2, concatenate . .

somewhatLongOperation1 somewhatLongOperation2 , . , , ? — . , - s1 s2. , concatenate. concatenate , , ! Haskell — . Haskell - (!), Haskell .

. .

. — , , , , , . — .

, . , :

unless(stock.isEuropean()) {
    sendToSEC(stock);
}

, sendToSEC (stock) . unless? , , Haskell, . unless !

void unless(boolean condition, List code) {
    if(!condition)
        code;
}

, code , condition == true. , , unless .

, [. — Python]. . , . , Java, , . Haskell . , , . ( ).

. . . . , , :

System.out.println("Please enter your name: ");
System.in.readLine();

, ! , -, ( , ), ! , ( ). . , . ! (continuation), (monads) (uniqueness typing). , . , , . .

, « » : . , , , -1.

, , , . — . , , . «» — , , . , . :

int i = add(5, 10);
int j = square(i);

add 15, i, , . i square. , , . (Continuation Passing Style CPS), add square.

int j = add(5, 10, square);

add — , , add . j 225.

, . -

System.out.println("Please enter your name: ");
System.in.readLine();

, . CPS, , !

System.out.println("Please enter your name: ", System.in.readLine);

println readLine, , readLine . , , readLine ( ). Java println void. - ( readLine), ! , . , , . , ( )! , , — . , println readLine , .

. CPS, , , . CPS, . ( ).

CPS , , , , . , add(5,10). , CPS , — , add . -CPS ? , , CPS, ?

, . CPS . , , CPS ! , «return», , . (push) , (pop) . - jump . , , !

, CPS , , , . -CPS , . ? , . , ? ! — , , , CPS ! , add(5,10), .

. — , , , . , — , , , — , ( ) — . , ( ).

, , . ? -, — . . , , . , . , . ( Scheme call-with-current-continuation), — ( CPS — ). ( ). «» , «» . , , . , . . , . . !

? . Web- ( Seaside Smalltalk). ASP.NET Microsoft , , . C# , ASP.NET — . Web- — ! — . , Web, .

(Pattern matching)

. . , , , , — .

Pattern matching . Java:

int fib(int n) {
    if(n == 0) return 1;
    if(n == 1) return 1;
        
    return fib(n - 2) + fib(n - 1);
}

Java- Pattern matching-

int fib(0) {
    return 1;
}
int fib(1) {
    return 1;
}
int fib(int n) {
    return fib(n - 2) + fib(n - 1);
}

? .

, ! . , switch ( ), . , ( ). , . . int fib(int n) n 1, , int fib(1) — .

, . Pattern matching :

int f(int n < 10) { ... }
int f(int n) { ... }

? ! , if, pattern matching . WndProc, Win32 ( ). . , , , 1, 3.

Pattern matching , . ( ) . . , Pattern matching. , , .

«» — , , . , . , . . ( Common Lisp) final — . , — . , . - : . . , final :

Function makePowerFn(int power) {
   int powerFn(int base) {
       return pow(base, power);
   }


   return powerFn;
}


Function square = makePowerFn(2);
square(3); // returns 9

make-power-fn , . , square(3)? power powerFn, makePowerFn , . square? - power, square . cube, ? power make-power-fn . . . :

Function makeIncrementer() {
   int n = 0;


   int increment() {
       return ++n;
   }
}


Function inc1 = makeIncrementer();
Function inc2 = makeIncrementer();


inc1(); // returns 1;
inc1(); // returns 2;
inc1(); // returns 3;
inc2(); // returns 1;
inc2(); // returns 2;
inc2(); // returns 3;

n , . n, , , makeIncrementer . ? ? .

. , . , — (heap) ^[8]. , , , , , :

class some_function_t {
   SymbolTable parentScope;
   
   // ...
}

, , . ! . , , , -, . — , «» , , .

?

. , . , , , , , , . ( ) , . , Google — .

?

, , coffeemug [] gmail.com. .

[1]. 2005 , . . - , $300,000 .

[2]. . , , .

[3]. , , . — , . , , , . . .

[4]. , «», , . — . . , «» , «».

[5]. , Java . , .

[6]. . .

[7]. . , .

[8]. , , O(1) .