第一級関数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

計算機科学において、第一級関数(だいいっきゅうかんすう、: first-class functionファーストクラスファンクション[1]とは、関数第一級オブジェクトとして扱うことのできるプログラミング言語の性質、またはそのような関数のことである。型のある言語では、関数型(かんすうがた、: function type)という型の値となる。具体的にはプログラムの実行時に生成され、データ構造に含めることができ、他の関数の引数として渡したり、戻り値として返したりすることのできる関数をいう。この概念はメタプログラミングとは異なり、コンパイラ呼び出しやeval関数によって生成された関数は含まれない。無名関数も参照。

第一級関数は関数型言語には必要不可欠であり、高階関数のような形で日常的に用いられる。例として、関数とリストを引数に取り、リストの各要素に関数を適用した結果のリストを返すmap (mapcar) 関数が挙げられる。map関数をサポートするプログラミング言語は、何らかの形で関数を関数の引数として渡すことを許容しなければならない。

Schemeでの例:

(map func list0 list1 ... listN)

スタックベースのプログラミング言語では、高階関数の実装における自由変数の取り扱いに関して困難な問題が生じる。これはFunarg問題("function argument" の略称、: funarg problem)として知られている。

型理論では、型Aの値を受け取り、型Bの値を返す関数をAB(もしくはBA)と書く。これはPQと似ているが実は同じもので、カリー・ハワード対応(カリー・ハワード同型対応、: Curry-Howard correspondence)によれば、関数型は論理包含に関係しており、ラムダ抽象自然演繹における仮説、関数の適用はモーダスポネンスに相当する。また多くのプログラミング言語の機能として、型理論は第一級関数が連想配列などのデータ構造をモデルするのにも用いられる。

圏論においては、第一級関数は閉圏に相当する。たとえば単純型付きラムダ計算: simply typed lambda calculus)は、カルテシアン閉圏(デカルト閉圏)の言語に相当する。

利用[編集]

HaskellLispML、Schemeのような関数型言語は第一級関数を全面的にサポートしている。他に第一級関数をサポートしているプログラミング言語としては、ECMAScript (ActionScriptJavaScript)、IoLuaNemerlePerlPHPPythonRubyScalaTcl/Tkなどが挙げられる。

CC++C#Pascalなどのプログラミング言語は関数ポインタをサポートしており、データ構造に含めたり他の関数に引数として渡したりすることができる。しかし、それらの関数は一般にリフレクションなしではプログラムの実行時に動的に生成することができないため、第一級関数をサポートしているとは見なされていない。

最も第一級関数に近いのは、C#のJITコンパイラによって動的に生成された関数である。これは機械語命令の配列としてメモリにコンパイルされ、関数ポインタへキャストされる。しかしながら、このテクニックは下層管理のフレームワークアーキテクチャに依存しており移植可能でない。もしWindowsを使用しているならば、C#はタイプセーフな関数ポインタのデリゲート型を持っている。また、C#バージョン3ではラムダ式のサポートが追加された。レキサパーサはコンパイル時に動作し、コンパイラのラムダコード生成部分は実行時に動作する。

C++はoperator()を含むユーザ定義演算子をサポートしており、operator()を持つクラスは関数オブジェクトとして扱うことができる。関数オブジェクトはC++では他の第一級オブジェクトと同じように操作することができる。また、C++11では無名関数がサポートされている。

各言語での例[編集]

C++[編集]

#include <cmath>
#include <iostream>
#include <functional>
 
auto derivative = [](std::function<double(double)> f, double delta) {
    return [=](double x) {
        return (f(x + delta) - f(x)) / delta;
    };
};
int main() {
    double (*psin)(double) = std::sin;
    auto cos = derivative(psin, 0.000001);
    std::cout << cos(0) << std::endl;
}

D[編集]

alias real delegate(real x) Delegate;
 
Delegate makeDerivative(Delegate f, real deltaX)
{
    return delegate real (real x)
    {
       return (f(x + deltaX) - f(x)) / deltaX;
    };
}
 
void main()
{
    real mySin(real s)
    {
        return std.math.sin(s);
    }
 
    Delegate cos = makeDerivative(&mySin, 0.000001);
    writefln(cos(0));
}

Erlang[編集]

-module(calculus).
-export([derivate/2]).
 
% F: 数値を受け取り数値を返す関数
% DeltaX: 小さい正の数
% Fの近似導関数を返す。
 
derivative(F, DeltaX) ->
  fun(X) ->
    (F(X + DeltaX) - F(X)) / DeltaX
  end.

Scheme[編集]

(define square (lambda (x) (* x x))) ;変数に関数リテラルを代入
(define fns (list + sin square)) ;リストの要素を関数に
(define (compose f g) (lambda (x) (f (g x)))) ;2つの関数を引数として受け取り
        ;合成関数を返す関数
((compose sqrt square) -3) ;他の関数の戻り値としての関数、引数に-3を適用
;結果は3
(define fns-squared (map (lambda (fn) (compose square fn)) fns)) ;関数のリストを
        ;sqrt関数に合成 -> 関数のリスト
(map (lambda(fn) (fn 3)) fns-squared) ;すべての関数に引数を3で適用
;結果はリスト (9 0.01991485667481699 81)

Lisp[編集]

(lambda (a b) (* a b)) ; 関数リテラル
((lambda (a b) (* a b)) 4 5) ; 関数に4と5を渡す

Lua[編集]

この例では第一級関数はIPアドレスのテーブルのソート戦略を指定するのに使われている。

     network = {
       {name = "grauna",  IP = "210.26.30.34"},
       {name = "arraial", IP = "210.26.30.23"},
       {name = "lua",     IP = "210.26.23.12"},
       {name = "derain",  IP = "210.26.23.20"},
     }

テーブルのホスト名を辞書順の逆でソートするには、次のように書く。

    table.sort(network, function (a,b)
      return (a.name > b.name)
    end)

ALGOL 68[編集]

PROC newton = (REAL x, error, PROC (REAL) REAL f, f prime) REAL:
# ニュートン法 #
  IF f(x) <= error
  THEN x
  ELSE newton (x - f(x) / f prime (x), error, f, f prime)
  FI;

print((
  newton(0.5, 0.001, (REAL x) REAL: x**3 - 2*x**2 + 6, (REAL x) REAL: 3*x**2 - 4**x),
  newline
));

JavaScript[編集]

// 関数リテラル
function(message){
    print(message);
};
 
// 関数リテラルをコールバックに代入
SomeObject.SomeCallBack = function(message){
    print(message);
};

arguments.calleeプロパティを使うとJavaScriptでも無名再帰関数を書くことができる。なお、ECMAScript5のstrict modeではarguments.calleeの使用は禁じられている。

Perl[編集]

my $divisor = 10;
my $checker = sub { 
                my $val = shift;
                if ($val % $divisor ) { 
                      return 0; 
                } else {
                      return 1;
                }
         };

これはPerlにおける第一級関数だけでなく、クロージャの例にもなっている。また留意すべきこととして、オブジェクト指向Perlにおいてはクラスに関数のリファレンスをblessすることが可能である。

Python[編集]

Pythonではdef文またはlambda式によって関数を生成する。第一級関数としては十分柔軟であるが、lambda式によって定義できる関数の本体は式に限られ、文を含む関数を生成することはできない。

>>> #いくつかの組み込み関数とそれらの逆関数
>>> from math import sin, cos, acos, asin
>>> # ユーザ定義関数とそれらの逆関数を追加
>>> cube = lambda x: x * x * x
>>> croot = lambda x: x ** (1/3.0)
>>> # 関数の戻り値から関数を生成する第一級関数
>>> # compose(f,g)(x) == f(g(x))
>>> compose = lambda f1, f2: ( lambda x: f1(f2(x)) )
>>> # 第一級関数は配列の要素として扱える
>>> funclist = [sin, cos, cube]
>>> funclisti = [asin, acos, croot]
>>> # 整数のように自然にリストから関数を適用
>>> [compose(inversef, f)(.5) for f, inversef in zip(funclist, funclisti)]
[0.5, 0.49999999999999989, 0.5]
>>>

JavaScript[編集]

JavaScriptは第一級関数をサポートする。関数はレキシカルスコープを作り出す。

// f: 数値を受け取って数値を返す関数
// deltaX: 微小な正の数
// fの近似導関数を返す関数
function makeDerivative ( f, deltaX ) {
    return function (x) { 
       return ( f(x + deltaX) - f(x) ) / deltaX;
    };
}
var cos = makeDerivative( Math.sin, 0.000001 );
// cos(0)     ~> 1
// cos(Math.PI/2)  ~> 0

C#[編集]

C#ではバージョン3から匿名関数とラムダ式をサポートする。

using System;
class Program
{
  // f: doubleを受け取ってdoubleを返す関数
  // deltaX: 微小な正の数
  // fの導関数の近似を返す関数
  static Func<double, double> MakeDerivative(Func<double, double> f, double deltaX)
  {
    return (x) => (f(x + deltaX) - f(x - deltaX)) / (2 * deltaX);
  }
  static void Main()
  {
    var cos = MakeDerivative(Math.Sin, 0.00000001);
    Console.WriteLine(cos(0));            // 1
    Console.WriteLine(cos(Math.PI / 2));  // 0
  }
}

Ruby 1.9[編集]

def deriv(f, dx)
  ->(x){ (f[x + dx] - f[x]) / dx }
end
 
sin = ->(x){ Math.sin(x) }
 
cos = deriv(sin, 0.00000001)
 
puts sin[Math::PI / 2]
puts cos[Math::PI / 2]

Scala[編集]

 import Math._
 
 def deriv(f:Double => Double, dx:Double) = (x:Double) => (f(x + dx) - f(x)) / dx
 
 val cos = deriv(sin, 0.00000001)
 
 Console.println(sin(Pi / 2))
 Console.println(cos(Pi / 2))

Haskell[編集]

 derivative f delta = \x -> (f (x+delta) - f x) / delta
 
 main = do
 	let sin' = derivative sin 0.00000001
 	let x = pi / 3
 	print (sin x)
 	print (sin' x)

PHP 5.3[編集]

<?php
 
$greet = function($name) {
    echo "Hello $name";
};
 
$greet('World'); // Hello Worldを出力

関連項目[編集]

参考文献[編集]

  1. ^ Programming language pragmatics, by Michael Lee Scott, section 11.2 "Functional Programming".

外部リンク[編集]