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

←　前のページに戻る

6. 四式言語: 高階関数をサポートするプログラミング言語

高階関数の実現方法について説明します。 まずは、一式言語を改造して、手続き型言語に高階関数を導入します。

関数自体を変数に代入できる関数、 関数を関数の引数に設定できる関数、そんなプログラミング言語をつくります。

6.1 高階関数をサポートするプログラミング言語とは

高階関数とは何でしょうか。 それは、関数の引数に関数を設定できて、かつ関数の返り値として関数を返すことができる関数のことです。

英語ではhigher-order functionと呼ばれます。

第一級関数（first-class function）と呼ばれることもあります。

通常の手続き言語のように数値や文字列などのデータを扱う関数やサブルーチンよりも、柔軟で高度なプログラミングを可能とします。

さて、今までのPL/0言語や一式言語から三式言語までは、データ型は整数型だけがサポートされていましたが、高階関数をサポートするならば関数型もデータ型としなければなりません。 そのため、データの型を新たに設定できるようにコンパイラを改造する必要が出てきます。

そこで、変数のデータ型として、int型とfunc型を指定できるように改造します。 さらには、func型の変数には関数を代入できるようにします。

変数定義を次のようにします。

  var 変数名: データ型;

例えば

  var a: int, xy: func;

関数引数と返り値もデータ型を指定できるように関数の定義も同様に以下のようにしましょう。

データ型:function 関数名 ( データ型: 引数変数, ...); 
begin

end

例えば

int:function dec(n:int);
begin
        return n-1;
end

変数に次のように関数を代入できるようになります。

var   a:int, f:func;
int:function test(cc:int, dd:int);
begin
        return cc*dd;
end

begin
        f = test;
        a = $f(20, 30);
        print a;
end

変数f に関数testを代入しています。

上に示したように、変数に代入された関数を呼び出す場合には、変数名の頭に$を付けるようにします。

関数の返り値に関数を設定することもできます。return の値に関数を設定できるようにします。

var   a:int, f:func;
int: function test(cc:int, dd:int);
begin
        return cc*dd;
end

func: function test2(f: func);
begin
        return f;
end

begin
        f = test2(test);
        a = $f(20, 30);
        print a;
end

関数test2の引数と返り値に関数型を設定し、test関数を返しています。

本当なら名前のない匿名関数も使えると面白いのですが、今回の四式言語では扱いません。 後の別の章で匿名関数をサポートした新言語について説明したいと思います。

6.2 四式言語の改造点

6.2.1 いかに高階関数を実現するか？

一式言語を次のようなポイントで改造して、高階関数をサポートした四式言語を実現します。

- 変数の定義に、データ型の指定を付けます。

- 関数の定義で関数の型の指定を付けます。

- 関数の引数にデータ型の指定を付けます。

- 関数型の変数の先頭に$を付けて、引数を付けると変数に設定された関数が実行できるようにします。

6.2.2 四式言語の改造部分

関数型のためのデータ型を出力するC言語に含めます。

                              <print "typedef int (*func)();">

これは、func型を定義しています。これは、int型を返す関数へのポインタとして定義しています。

四式言語では、int型とfunc型の２つの型をサポートすることになります。

次は、変数の定義に、データ型の指定を付けましょう。

                [ "var"         <emsg "variable name.">
                <ident #var1> <emsg "variable definition.">
                ":" <ident #type1>
                              <print #type1 #var1 ";">
                {","
                 <ident #var2>
                              <emsg "variable definition.">
                 ":" <ident #type2>
                              <print #type2 #var2 ";">
                 } ";"

var 変数名: データ型, というような変数名だけではなく型を指定できるようにします。 上の処理では、#var1　および #var2が変数名であり、#type1 および #type2　がデータ型です。

これをC言語に出力するときには、type1 var1; type2 var2; のように変形してprint文で出力しています。

次は関数定義に返り値と引数のデータ型の処理を付けましょう。

                {
                  <ident #typef> ":"
                  "function"    <emsg "function name.">
                                <printf #typef " ">
                  <ident>       <emsg "function definition.">
                  "("           <printf "(">
                  [<ident #var3>
                    ":" <ident #type3>
                                <printf #type3 " " #var3>
                   { ","        <printf ", ">
                     <ident #var4>
                     ":" <ident #type4>
                                <printf #type4 " " #var4>
                   }
                  ]
                  ")"           <print ")">
                  ";"
                                <print "{">
                  <block>       <print "}">
                }

上に示した処理では、まず#typefに関数の型を指定します。

#var3 および #var4が引数の変数であり、#type3　と #type4　がデータ型を示します

これらに基づいてC言語の関数に変換して出力します。

次は関数内のローカル変数の定義です。

              | "var"         <emsg "variable name.">
                <ident #var1> <emsg "variable definition.">
                ":" <ident #type1>
                              <print #type1 #var1 ";">
                {","
                 <ident>      <emsg "variable definition.">
                 ":" <ident>
                              <print #type2 #var2 ";">
                 } ";"

これは、グローバル変数の定義と同じで、関数内で定義できるということで異なります。

次は、func型の変数を使って関数呼び出しをする処理です。

<factor>      ( "$"           <printf "(*">
              <ident #f>
               "("            <printf #f ")(">

変数名の前に　$　が付いていたら、関数型の関数とします。

6.3 四式言語のソース

// Enhanced PL/0
/*
 * The type is added to the variable.
 * The type is added to the function.
 * The type is added to the argument of the function.
 * Support of the higher-order function.
 */

<program>
                                <setVar Line 1>
                                <print "#include <stdio.h>">
                                <print "#include <stdlib.h>">
                                <print "typedef int (*func)();">
                                <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>}
                [ "var"         <emsg "variable name.">
                  <ident #var1> <emsg "variable definition.">
                  ":" <ident #type1>
                                <print #type1 #var1 ";">
                  {","
                   <ident #var2>
                                <emsg "variable definition.">
                   ":" <ident #type2>
                                <print #type2 #var2 ";">
                   } ";"
                ]
                {<Comment>}
                {
                  <ident #typef> ":"
                  "function"    <emsg "function name.">
                                <printf #typef " ">
                  <ident>       <emsg "function definition.">
                  "("           <printf "(">
                  [<ident #var3>
                    ":" <ident #type3>
                                <printf #type3 " " #var3>
                   { ","        <printf ", ">
                     <ident #var4>
                     ":" <ident #type4>
                                <printf #type4 " " #var4>
                   }
                  ]
                  ")"           <print ")">
                  ";"
                                <print "{">
                  <block>       <print "}">
                }
                {<Comment>}
                <statement>
                ;
<statement>     <SKIPSPACE> ::sys <line #Line> <setVar Line #Line>
                {<Comment>}
                (  <ident #var> "="     <emsg "expression.">
                                <printf #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.">
                  <ident #var1> <emsg "variable definition.">
                  ":" <ident #type1>
                                <print #type1 #var1 ";">
                  {","
                   <ident>      <emsg "variable definition.">
                   ":" <ident>
                                <print #type2 #var2 ";">
                   } ";"
                | "begin"       <print "{">
                     { <statement> }
                  "end"         <print "}">
                | "if"          <emsg "if sentence.">
                   <printf "if (">
                   <condition>
                   "then"       <print ") {">
                   <statement>
                  ["else"       <print "} else {">
                   <statement>
                  ]
                                <print "}">
                | "while"       <emsg "while sentence.">
                                <printf "while (">
                  <condition>
                  "do"          <print ") {">
                  <statement>
                                <print "}">
                | "for"         <emsg "for sentence.">
                                <printf "for (">
                   <ident>
                     "="        <printf " = ">
                     <expression> ";" <printf ";">
                   <condition> ";" <printf ";">
                   <ident>
                     "="        <printf " = ">
                     <expression> "do" <printf ") {">
                   <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>        ( "$"           <printf "(*">
                <ident #f>
                 "("            <printf #f ")(">
                |<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>;

6.4 四式言語のソースのコンパイル方法

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

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

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

const x = 2;
var   a:int, b:int, i:int, f:func, aa:int;
int:function test(cc:int, dd:int);
begin
        a = 10;
        a = a + x;
        for i=0; i<10; i=i+1 do
        begin
                print "i=", i;
        end
        dd = 314;
        cc = dd;
        return a;
end

int:function test2(cc:int, dd:int);
begin
        return cc*dd;
end

func:function fc(f:func);
begin
        return f;
end

begin
        b = test(10, 03);
        print b;
        f = test;
        a = $f(20, 30);
        print a;
        f = test2;
        aa = $f(2, 3);
        print aa;

        f = fc(test);
        aa = $f(2, 3);
end

int型の値を返すtest1, test2関数と、関数を引数でとり関数を返すfc関数を定義して、それらを使って計算する例題となっています。

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

$ descartes pl04.dec a.pl0
inputfile a.pl0
outputfile a.c
result --
        <compile>
-- true

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

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

#include <stdio.h>
#include <stdlib.h>
typedef int (*func) ();

int main()
{
    const int x = 2;
    int a;
    int b;
    int i;
    func f;
    int aa;
    int test(int cc, int dd) {
        {
            a = 10;
            a = a + x;
            for (i = 0; i < 10; i = i + 1) { {
                    printf("%s ", "i=");
                    printf("%d ", i);
                    printf("\n");
            }
            }
            dd = 314;
            cc = dd;
            return a;
        }
    }
    int test2(int cc, int dd) {
        {
            return cc * dd;
        }
    }
    func fc(func f) {
        {
            return f;
        }
    }
    {
        b = test(10, 03);
        printf("%d ", b);
        printf("\n");
        f = test;
        a = (*f) (20, 30);
        printf("%d ", a);
        printf("\n");
        f = test2;
        aa = (*f) (2, 3);
        printf("%d ", aa);
        printf("\n");
        f = fc(test);
        aa = (*f) (2, 3);
    }
}

関数型funcが定義されて、それを使った関数があることを確認してみてください。

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

$ gcc a.c -o a.out

$ ./a.out
i= 0
i= 1
i= 2
i= 3
i= 4
i= 5
i= 6
i= 7
i= 8
i= 9
12
i= 0
i= 1
i= 2
i= 3
i= 4
i= 5
i= 6
i= 7
i= 8
i= 9
12
6
i= 0
i= 1
i= 2
i= 3
i= 4
i= 5
i= 6
i= 7
i= 8
i= 9

ちゃんとコンパイルして実行できました。