みんなのための関数型プログラミング

良い一日。 この記事は、ニューヨーク州立大学ストーニーブルック校の大学院生のブログに興味を持った投稿の翻訳です。 アクセシブルな形式の記事では、関数型プログラミングの基本概念、その長所と短所について説明しています。 関数型プログラミングの世界を掘り下げる必要があるかどうかを疑う幅広い読者に役立つと思います。 翻訳および用語に関する要望、提案、コメントは、個人の郵便で受け付けています。



翻訳者の意見は著者の意見と一致しない場合がありますが、記事の翻訳は非常に楽しかったです。



UPD： rsdnで別の翻訳オプションを見つけることができます（リンクのフラミンゴのおかげです）。



2006年6月19日月曜日

はじめに

プログラマーは先延ばし者（怠け者）です。 来て、コーヒーを入れて、メールをチェックして、夏のRSSを読んで、ニュースを読んで、技術サイトの最新記事をチェックして、プログラミングフォーラムで政治的な議論を調べてください。 すすぎ、何も見逃さないように繰り返します。 昼食に行きます。 戻って、IDEに数分間飛び込みます。 メールを確認してください。 コーヒーを作る。 そして突然、その日は終わりに近づいています。



しかし、時々、興味深い（恥ずかしい、有望な）記事やブログの投稿が表示されます。 適切な場所を探している場合は、数日ごとに少なくとも1つのそのような記事が表示されます。 これらの投稿は理解するのが難しく、時間がかかるため、読み取りフォルダーに蓄積されます。 何が何であるかを理解する前に、多くのリンクとPDFファイルでいっぱいのフォルダーが既に蓄積されていることがわかります。 森の真ん中に一年と小屋が必要になります。そこでは、周囲の何マイルもそれを理解する魂はありません。 また、毎朝川に歩いている間に誰かが食べ物を持ってきてゴミを拾うことをお勧めします。



私はあなたのリストが何であるか分かりませんが、私のリストのほとんどは関数型プログラミングを扱っています。 このような記事は通常、最も複雑です。 多くの場合、それらはドライなアカデミック言語で書かれており、「10年の経験を持つウォールストリートの退役軍人」でさえ、関数型プログラミング（FP）に関する記事の内容を理解していません。 シティグループまたはドイツ銀行のプロジェクトマネージャーに質問する場合 ^[1]彼らがErlangの代わりにJMSを選んだ理由は、彼らが産業開発にアカデミックな言語を使用できないことに対する返答として聞こえます。 問題は、最も厳しい要件を持つ最も複雑なシステムが、機能的なプログラミング要素を使用して記述されていることです。 何かが合わない。



実際、AFに関する記事は理解するのが難しいですが、簡単に書くことができます。 結果として生じる知識の深sの理由は、純粋に歴史的なものです。 本質的に、AFの概念に複雑なものはありません。 この記事を、私たちの命令的な心とAFの世界との架け橋として、「アクセスしやすいAFのガイド」として見てください。 コーヒーを入れて続けます。 すぐに同僚があなたのFIのコメントについて冗談を言い始めることを願っています。



では、AFとは何ですか？ どこから来たの？ それは何に適していますか？ FPの支持者が言っているように、本当に便利な場合、なぜ産業規模で使用されることが多いのですか？ 博士号を持つ人だけが関数型言語に傾くのはなぜですか？ しかしもっと重要なのは、なぜ関数型言語を学ぶのがそんなに難しいのでしょうか？ これらすべての閉鎖、継続、カリー化、レイジーコンピューティング、および副作用のないことの背後にあるものは何ですか？ 宇宙全体をカバーしていないプロジェクトで、これらすべてをどのように使用できますか？ なぜ私たちの命令的な心にとって神聖で大切な善から遠く離れているのですか？ すぐにそれを理解します。 まず、学術論文と現実世界の間に大きなギャップがある理由を理解しましょう。 この質問に答えるには、公園を歩いてください。

公園を散歩する

タイムマシンに乗りましょう。 私たちが公園を散歩したのは、紀元前380年の長い間忘れられていた春の晴れた日に、2000年以上も前のことです。 アテネの城壁を越えて、オリーブの木の穏やかな影の下で、プラトンはハンサムな奴隷の少年とアカデミーに向かって歩いた。 天気は素晴らしく、昼食はお腹の中で心地よく、会話は次第に哲学的な話題に変わりました。



「この2人の学生を見てください」とプラトンは語り、問題に教育的な意味を与えるために慎重に言葉を選びました。 「どちらが背が高いと思いますか？」男の子の奴隷は、2人が立っているプールの方を見ました。 「彼らはほぼ同じ高さです」と少年は答えた。 「「ほぼ同じ高さ」という言葉はどういう意味ですか？」プラトンに尋ねた。 「さて、ここからは同じように見えますが、私たちが近づくと、身長の違いが見えると確信しています。」



プラトンは微笑んだ。 彼は少年を正しい方向に導いた。 「それで、あなたは世界に理想的に一致するものがないと言いたいですか？」少年は思慮深くなって答えました：「はい、そう思います。 たとえそれが見えなくても、常に小さな違いがあります。 「それでは、この世界に完全に一致するものがない場合、「理想的な」平等の概念をどのように理解しますか？」これにより、少年はst迷しました。 彼は答えた：「私は知りません。」



したがって、数学の性質を理解する最初の試みが生まれました。 プラトンは、私たちの世界ではすべてが理想の近似にすぎないことを示唆しました。 彼はまた、理想に出会ったことはないが、人々は理想の概念を理解できることにも気付いた。 彼は、理想的な数学的形式は別の世界に存在しなければならず、私たちはこの「代替」宇宙とのつながりから何らかの形でそれらについて知っているという結論に達しました。 明らかに、完全な円は見えません。 しかし同時に、理想的な円とは何か、数学的にどのように記述できるかを理解しています。 それでは数学は何ですか？ なぜ宇宙は数学の法則で記述されているのですか？ 数学はすべてを説明できますか？ ^[2]



数学の哲学は非常に複雑な主題です。 ほとんどの哲学的分野と同様に、彼女はむしろ答えるよりも質問する。 ほとんどの科学者は、数学が本当のパズルであるという事実に同意します。それは、一連の基本的な一貫した原則と、これらの原則の運用方法に関する一連の規則に基づいています。 その後、ルールを組み合わせて、より複雑な法則を取得できます。 数学者はこのメソッドを「形式システム」または「計算」と呼びます。 たとえば、テトリス用の正式なシステムを構築できます。 実際、動作しているテトリスはそれ自体が正式なシステムであり、通常とは異なる形式で書かれています。



アルファケンタウリのふわふわした生き物の文明は、我々の正式なテトリスまたはサークルシステムを読むことができません。なぜなら、彼らの唯一の感覚器官は匂いしかできないからです。 彼らはテトリスを決して構築しないかもしれませんが、彼らは確実に円のための正式なシステムを持つでしょう。 ほとんどの場合、嗅覚はそれほど発達していないため、私たちはそれに慣れることができません。 しかし、プレゼンテーション言語が解読されるとすぐに（さまざまな感覚ツールと標準的なリバースエンジニアリング技術を使用して）、基本概念が知的に発達した文明に明らかになります。



たとえ宇宙に知的な文明がなかったとしても、テトリスとサークルの正式なシステムは依然として論理的に正しいでしょう。 これらのシステムを見つけて形式化することができるクリーチャーは存在しません。 賢明な異星人種が突然現れた場合、彼らはおそらく宇宙を記述する正式なシステムを開発するでしょう。 もちろん、宇宙にはこのゲームに類似するものがないため、テトリスを発明する可能性は低いです。 テトリスは、周囲の現実とは関係のない膨大な数の正式なシステム、パズルの1つの例です。 自然数のような概念でさえ、現実世界に常に起因するとは限りません。なぜなら、宇宙の何にも適用できないほど大きな数を想像できるからです。しかし、それは有限です。

ちょっとした歴史 ^[3]

タイムマシンのホイールを回して、1930年代に少し近づいてみましょう。 大恐pressionは、新旧の世界を破壊しました。 すべての社会階層のほとんどすべての家族は、大きな経済不況を感じました。 人々が貧困を恐れることのできない避難所はほとんど残っていません。 一部の人々は、そのような避難所で終わる幸運です。 プリンストン大学の数学に興味があります。



ゴシック様式で建てられた新しい建物は、大学に安全オーラを与えました。 全国のロジックの専門家がプリンストンに招待され、新しい部門が設立されました。 ほとんどのアメリカ人は食べ物、高い天井、木目模様の壁、お茶を飲みながらの毎日の議論、森の中を歩くのに苦労しましたが、プリンストンの生活環境を作りました。



このような無駄な生活を送っていた数学者の一人は、アロンゾ教会という名の若い男でした。 アロンゾはプリンストンで学士号を取得し、大学院に留まるよう説得されました。 アロンゾは、周囲が豪華すぎると感じました。 彼はめったにお茶と数学の問題を議論するように見えず、森の中を歩くのが好きではなかった。 アロンゾは孤独でした。一人で働いたとき、彼はより多作でした。 それにもかかわらず、彼はプリンストンの他の住民と定期的に会った。 その中には、アランチューリング（アランチューリング）、ジョンフォンノイマン（ジョンフォンノイマン）、カートゲーデル（カートゲーデル）がいました。



これら4人は正式なシステムに関心がありました。 彼らは物理的な世界にあまり注意を払わず、抽象的な数学的パズルを扱うことに興味がありました。 パズルには共通点がありました。数学者は計算の問題を研究しました。 無限のコンピューティング機能を備えたマシンがある場合、どのタスクを解決できますか？ 問題を自動的に解決することは可能ですか？ 解決できない問題はありますか？その理由は？ 異なるアーキテクチャの車のパワーは同じですか？



アロンゾは他の科学者とともに、ラムダ計算と呼ばれる正式なシステムを開発しました。 このシステムは、本質的には仮想マシンの1つのプログラミング言語でした。 関数を引数として受け取り、関数を返す関数に基づいていました。 このような機能は、システム全体に名前を与えたギリシャ文字ラムダによって指定されました ^[4] 。 このシステムを使用して、Alonzoは上記の質問に関する推論を構築し、それらに対する回答を導き出すことができました。



Alonzoに関係なく、Alan Turingは同様の研究を実施しました。 彼は別の正式なシステム（現在はチューリングマシンと呼ばれています）を開発し、それを使用してアロンゾに似た結論に達しました。 チューリング機械とリアブダ計算が同じ力を持っていることが後で証明されました。



この瞬間、私たちの物語は終わります。 記事を要約しますが、第二次世界大戦が始まっていない場合は、別のページに切り替えます。 世界は燃えていた。 米軍は大砲を非常に頻繁に使用しました。 精度を向上させるために、軍は弾道射撃テーブルに必要な微分方程式を絶えず解く多数の数学者を雇いました。 そのようなタスクは手動による解決には複雑すぎることがすぐに明らかになり、この問題を克服するために特別な機器が開発されました。 最初の弾道テーブルソリューションマシンは、IBMが製造したMark Iでした。重量は5トンで、750'000の部品で構成され、1秒間に3つの操作を実行できました。



もちろん、レースはそこで終わりませんでした。 1949年、電子離散可変自動コンピューター（EDVAC）が公開されました。 これは、フォンノイマンアーキテクチャの実装の最初の例であり、実際に動作する最初のチューリングマシンでした。 しばらくの間、アロンゾ教会の仕事はさておきました。



1950年代後半、プリンストン大学を卒業したMITのジョンマッカーシー教授は、アロンゾ教会に関心を示し始めました。 1958年、彼はリスト処理言語であるLis t P処理言語（Lisp）を導入しました。 Lispは、フォンノイマンコンピューターで実行されるアロンゾのラムダ計算の実装として考えられていました。 多くのコンピューター科学者は、Lispの表現力に注目しています。 1973年、マサチューセッツ工科大学の人工知能研究所のプログラマーのグループが鉄を開発し、それをLispマシンと呼びました。 これは、Alonzoのラムダ計算のハードウェア実装でした。

関数型プログラミング

— . - , - . , , — , . , . 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) .