EXPL02 - デカルト言語 - 並列ロジック プログラミング言語 Wiki - デカルト言語 - 並列ロジック プログラミング言語

←　前のページに戻る

4. 二式言語: 純関数型プログラミング言語

4.1 純関数型プログラミング言語とは

二式言語は純関数型プログラミング言語になるように一式言語を改造しましょう。

純関数型プログラミング言語とは何か？

関数型プログラミング言語もいろいろな種類があります。

まず思い浮かぶのはLISPではないでしょうか。カッコで囲まれた関数を組み合わせてプログラムを作成します。多重のカッコのネストによって如何にも関数の組み合わせでプログラムしている感じがします。

さらにはML系の言語が関数型プログラミング言語と呼ばれます。SMLやOCamlは関数型と呼ばれますが、LISPほどカッコなどもなく、一見普通のC言語と変わらないプログラミング言語に見えます。

C言語といえば、基本的にはサブルーチンや手続きも関数として定義しますが、これは関数型プログラミング言語とは呼ばれませんね。

もっとも関数型言語の代表のように呼ばれる言語にはHaskellがあります。

さて、一般に関数型プログラミング言語というだけでもいろいろな定義があります。

関数型言語では、第一級関数が必要不可欠とか、高階関数が使えないととか、無名関数とかラムダ関数が欲しいとか難しい話になることが多い気がします。 型推論や遅延評価が有用だということもよく言われます。 (Haskellが最強と呼ばれるのはこのあたりをすべて持つとともに他にモナドなどの機能が追加されているからでしょうか。)

型推論や遅延評価以外については、後の章で追加機能として説明する予定です。

しかし、まず基本的に純粋に関数型言語にとって必要な機能は何でしょうか。それは、私は参照透過性を持つということだと思います。

C言語のような一般的な手続き言語では、変数を定義して値を設定し、それを順次変更していくことができます。 そのために、同じ引数の組み合わせで関数を呼び出しても結果が常に同じという保証はありません。

つまり、参照透過性が保証されている純関数型言語では、関数は状態を持たず、同じ引数の組み合わせでは常に同じ結果を返します。

例えば、三角関数sinでは、引数のラジアンの値に対する返り値は常に同じ値です。呼び出される度に他の変数の変更などに影響されて返る値が変わるようなことはありません。 純関数型言語では、内部状態を持たないので関数を数学的に扱うことが可能になり、動作を把握して予想することが容易になります。

このような特徴を持つため、純関数型言語ではプログラムの副作用を考慮する必要がなく、プログラムの動作を保証しやすいといわれています。

4.2 二式言語の改造点

では、純関数型言語にするためにはどうすればよいのでしょうか？

それは、ずばり代入処理を廃止することです。変数に値を代入することを禁止して構文からも代入処理を無くします。 ただし、変数の定義時の初期値の設定は許可します。初期値が他の変数を参照する数式であってもよいのです。 しかし、一度定義して値が定まった変数には代入処理で値を変えることはできないようにします。

そして、定義された変数のスコープ内ではずっと同じ値であり続けます。

変数の定義はOK　○
　　　var df = a * 2 + c;

代入はNG ×
　　　df = a * 2 + c;

関数の引数も同様です。関数が呼び出されるときに設定された値はその関数の中で参照はできますが変更はできません。 しかし、再帰関数処理で新たに呼び出すときに別の値が設定されるのは許されます。 新たに引数に設定された変数は呼び出された関数内では有効ですが、呼び出した関数内ではその関数が呼び出されたときの引数のままであることに注意してください。

function f(a, b)と定義された関数で、f(1, 2)と呼ばれた場合は変数aは1, 変数bは2と設定され変更できなくなる。

しかし、function f(a, b)の定義の中で、さらにf(a+1, b*3)とよばれた場合は、呼び出された関数の中では変数aは2, 変数bは6となる。

4.3 二式言語のソース

// Enhancing PL/0 is remodeled to a pure functional programming language.

<program>
                                <setVar Line 1>
                                <print "#include <stdio.h>">
                                <print "#include <stdlib.h>">
                                <print>
                                <print "int main() ">
                                <print "{">
                {<Comment>}
                <block>
                                <print "}">
                {<Comment>}
                ;
<block>         [ "const"       <emsg "constant name.">
                                <printf "const int ">
                  <ident>       <emsg "constant definition.">
                  "="           <printf " = ">
                  <number>
                  {","          <printf ", ">
                   <ident>      <emsg "constant definition.">
                   "="          <printf " = ">
                   <number>
                   }            <emsg "';' is missing.">
                   ";"          <print ";">
                ]
                {<Comment>}
                { "function"    <emsg "function name.">
                                <printf "int ">
                  <ident>       <emsg "function definition.">
                  "("           <printf "(">
                  [<ident #id1> <printf "const int " #id1>
                   { ","        <printf ", ">
                     <ident #id2> <printf "const int " #id2>
                   }
                  ]
                  ")"           <print ")">
                  ";"
                                <print "{">
                  <block>       <print "}">
                }
                {<Comment>}
                <statement>
                ;
<statement>     <SKIPSPACE> ::sys <line #Line> <setVar Line #Line>
                {<Comment>}
                (  <ident #var> "="     <emsg "expression.">
                                <printf "const int " #var " = ">
                  <expression>  <print ";">
                  ";"           <emsg "syntax error.">
                |
                  <ident #func> <emsg "syntax error.">
                                "(" <emsg "function call.">
                                <printf #func "(">
                        [<expression> {"," <expression>}]
                  ")"           <printf ")">
                                <print ";">
                  ";"           <emsg "syntax error.">
                | "return"      <printf "return ">
                   <expression>
                                <print ";">
                  ";"           <emsg "syntax error.">
                | "var"         <emsg "variable name.">
                                <printf "const int ">
                  <ident>       <emsg "variable definition.">
                  "="           <printf " = ">
                  <expression>
                  {","          <printf ", ">
                   <ident>      <emsg "variable definition.">
                   "="          <printf " = ">
                   <expression>
                   } ";"        <print ";">
                | "begin"       <print "{">
                     { <statement> }
                  "end"         <print "}">
                | "if"          <emsg "if sentence.">
                   <printf "if (">
                   <condition>
                   "then"       <print ") {">
                   <statement>
                  ["else"       <print "} else {">
                   <statement>
                  ]
                                <print "}">
                |
                  "print"       <emsg "print sentence. ">
                   [
                    (
                      <strings #str>    <printf 'printf("%s ", "'#str'" );'><print>
                    |                   <printf 'printf("%d ", '>
                      <expression>      <print ');'>
                    )
                   { ","
                    (
                      <strings #str2>   <printf 'printf("%s ", "'#str2'" );'><print>
                    |                   <printf 'printf("%d ", '>
                      <expression>      <print ');'>
                    )
                   }
                   ]
                                        <print 'printf("\n");'>
                  ";"           <emsg "syntax error.">
                )
                ;
<condition>     "odd"           <emsg "odd syntax.">
                                <printf "((">
                  <expression>  <printf ") & 1)">
                |
                <expression>
                ("="            <printf " == ">
                |"#"            <printf " != ">
                |"<="           <printf " <= ">
                |"<"            <printf " < ">
                |">="           <printf " >= ">
                |">"            <printf " > ">
                )
                <expression> ;
<expression>    [ "+"           <printf "+">
                 |"-"           <printf "-">
                ] <term> {
                        ("+"    <printf "+">
                        |"-"    <printf "-">
                        ) <term>};
<term>          <factor> {
                ("*"            <printf "*">
                |"/"            <printf "/">
                ) <factor>};
<factor>        <ident #f>
                 "("            <printf #f "(">
                  [ <expression>
                        {","    <printf ", ">
                        <expression>}]
                 ")"            <printf ")">

                | <ident> | <number>
                | "("           <printf "(">
                        <expression>
                  ")"           <printf ")">
                ;

<ident #id>     <ID #id>
                <reserved #id>
                ;
<ident>         <ident #id>
                <printf #id>
                ;
<number #sign #n>
                ["+"            <is #sign "">
                |
                 "-"            <is #sign "-">
                |
                                <is #sign "">
                ]
                <NUM #n>
                ;
<number>        <number #sign #n>
                <printf #sign #n>
                ;
<strings #str>  <STRINGS #str>
                ;
<strings>       <strings #str>
                <printf #str>
                ;

<Comment>       "//" <SKIPCR>
                ;

<reserved #id>
                <not ::sys <member #id
                  (var begin end if then while for do function
                        return print odd)>>
        ;

<emsg #x>
                <x <getVar #Line Line>
                   <warn "error : " #Line ":" #x>
                   <exit>>
                ;
<emsg2 #x>      <getVar #Line Line>
                <warn "error : " #Line ":" #x>
                <exit>
                ;

<compile>
        ::sys<args #x>
        ::sys<nth #inputfile #x 1>
        ::sys<suffix #outputfile #inputfile c>
        <print inputfile #inputfile>
        <print outputfile #outputfile>
        ::sys<openw #outputfile
                ::sys<openr #inputfile <program>>>
        ;

? <compile>;

4.3.1 修正部分

まず、一式言語のソースにあったblockの中の変数定義"var"を二式言語のソースからは削除します。

以下を削除

                [ "var"         <emsg "variable name.">
                                <printf "int ">
                  <ident>       <emsg "variable definition.">
                  {","          <printf ", ">
                   <ident>      <emsg "variable definition.">
                   } ";"        <print ";">
                ]

次に、二式言語のfunctionの定義では、変換先の引数の定義に"const"を追加します。

一式言語のfunctionの定義

                { "function"    <emsg "function name.">
                                <printf "int ">
                  <ident>       <emsg "function definition.">
                  "("           <printf "(">
                  [<ident #id1> <printf "int " #id1>
                   { ","        <printf ", ">
                     <ident #id2> <printf "int " #id2>
                   }
                  ]
                  ")"           <print ")">
                  ";"
                                <print "{">
                  <block>       <print "}">
                }

　　↓

二式言語のfunctionの定義

                { "function"    <emsg "function name.">
                                <printf "int ">
                  <ident>       <emsg "function definition.">
                  "("           <printf "(">
                  [<ident #id1> <printf "const int " #id1>　⇒　引数にconstを追加
                   { ","        <printf ", ">
                     <ident #id2> <printf "const int " #id2>　⇒　引数にconstを追加
                   }
                  ]
                  ")"           <print ")">
                  ";"
                                <print "{">
                  <block>       <print "}">
                }

一式言語のstatementの定義から、代入文の定義を削除し、代わりにvar変数の定義を加えます。 この場合実際は、varの定義では、代入文の前にconst intを付けてC言語に変換してやれば良いですから、一式言語の代入文の定義は流用できます。 つまり、代入文の定義をvarの定義に改造するのが手っ取り早いのです。

二式言語の関数内のvar変数の定義

                | "var"         <emsg "variable name."> ⇒　varの定義を追加
                                <printf "const int ">   ⇒　引数にconst int を追加。
                  <ident>       <emsg "variable definition.">
                  "="           <printf " = ">
                  <expression>
                  {","          <printf ", ">
                   <ident>      <emsg "variable definition.">
                   "="          <printf " = ">
                   <expression>
                   } ";"        <print ";">

極めて少量の修正で手続き言語であった「一式言語」が純関数型の「二式言語」に改造できてしまいましたよ。

4.4 二式言語のソースのコンパイル方法

それでは、二式言語用のサンプルプログラムを作成してコンパイルしてみましょう。

まず、「4.3 三式言語のソース」を pl02.dec と名前をつけて保存しておいてください。

次のサンプルプログラムのソースを使います。

// sample program for enhanced PL/0
function f(n);
begin
        if n <= 1 then
                return 1;

        var a = f(n-2), b = f(n-1);
        var c = a + b;

        return c;
end

begin
        print f(1);
        print f(2);
        print f(3);
        print f(4);
        print f(5);
end

フィボナッチ数を計算するプログラムです。

代入文が一つもないですね。確認してみてください。

このサンプルプログラムをf2.pl0という名前で保存してコンパイルします。

$ descartes pl02.dec f2.pl0
inputfile f2.pl0
outputfile f2.c
result --
        <compile>
-- true

f2.c にコンパイル結果が出力されました。

インデントを直してf2.cを見ると次のようになります。

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int f(const int n) {
        {
            if (n <= 1) {
                return 1;
            }
            const int a = f(n - 2), b = f(n - 1);
            const int c = a + b;
            return c;
        }
    }
    {
        printf("%d ", f(1));
        printf("\n");
        printf("%d ", f(2));
        printf("\n");
        printf("%d ", f(3));
        printf("\n");
        printf("%d ", f(4));
        printf("\n");
        printf("%d ", f(5));
        printf("\n");
    }
}

関数fの変数n, a, c がconst int で定義されていて、まさに純関数型といった感じです。

それではgccでコンパイルして実行します。

$ gcc f2.c -o f2.out

$ ./f2.out
1
2
3
5
8

できました。

それでは、次の章では、一式言語を改造してクロージャが使えるようにします。

クロージャというと難しいイメージがあるかもしれませんが、実は基本は今回の純関数型と同じで簡単なのです。

純関数でもクロージャでも七面倒な理屈は抜きにして、基本について集中して考えれば難しいことはありません。

そのあたりを説明して簡単な改造をするだけでできるクロージャの導入を行います。