top recent

プログラミング言語:高階関数

関連ページ

プログラミング言語 プログラミング プログラミング言語:高階関数:談話室

目次

  1. High-Order Function...
  2. ここでいう関数とは、Lispのように状態込みのものでなければならないのでしょうか?...
  3. (SHIMADAにとっては)魔法のような高階関数の例...
  4. PerlにはMemoizeモジュールがあった...
  5. できました（はぁと）...
  6. Common Lisp 版...
  7. GikoForth版...
  8. 継続渡しスタイル...
  9. Common Lisp による小さなインタプリタ "FOO"...
  10. コンビネータ...
  11. "To Mock A Mockingbird"...

High-Order Function

関数を引数に取る、または関数を返す関数のこと
…と短くまとめてしまうと「ふーん。で？」と終わってしまう。

しかし高階関数の考え方やその応用範囲は非常に広く、通常の関数の組み合わせでは表現できないような処理を実装できるらしい。

というわけで、ここでは純手続き型人間の発想から脱却すべく、高階関数の基本から応用までを追及してみたい。

[[id:683]] 2002-09-18 11:21:26

ここでいう関数とは、Lispのように状態込みのものでなければならないのでしょうか?

という疑問が。-戯

CやPascalの意味での関数と、Lisp系の意味の関数とは、
どうやら別物(というかC側がLisp側のサブセットかな)
であるようなので、ならば高階関数でいうところの関数は
どちらを指すのか、それともどっちでもいいのか、が
ちょっと気になりました。

どっちでもいいのでは？
使う側の頭にあるのはfunctorな気がします--有野

[[id:705]] 2002-06-15 19:21:05

(SHIMADAにとっては)魔法のような高階関数の例

プログラミング言語Standard ML入門 (本棚)の本で見掛けたこのコード。

fun memo f x = let val a = f x
in fn y => if x = y then a else f y
end

これがどう動くかというと、フィボナッチ数を計算する関数 fib があるとき

val fib = memo fib 31;
val fib = memo fib 32;
val fib = memo fib 33;
val fib = memo fib 34;

とすると、最後に fib に束縛されている関数は値31から34までに対応するフィボナッチ数を記憶しており、これらに対しては瞬時に結果を返す。

これを見たとき、最初はなぜ31〜34すべての答えを記憶できるか謎だった。
ちなみにPerlに訳すと、

sub memo {
my ($f, $x) = @_;
my $a = $f->($x);
return sub { my $y = shift; return ($y == $x) ? $a : $f->($y); };
}

sub fib {
my $x = shift;
if ($x == 0) { 0; }
elsif ($x == 1) { 1; }
else { fib($x - 2) + fib($x - 1); }
}

$fib = \&fib;
$fib = memo($fib, 31);
$fib = memo($fib, 32);
$fib = memo($fib, 33);
$fib = memo($fib, 34);
$fib->(34);
==> 5702887

サブルーチンと変数が別なのでちょっと苦しいけどまあこんな感じ。
# こうして並べて見るといかにPerlの構文が暗号めいているか分かるね。:-P

----
↑のコード、Rubyでも書いてみようと30分格闘したけどダメだった…。
def fib(x) ..... end したときに fib の手続き自体を取り出すことはできないものか。

- そういうのには Proc を使うんだよといいつつめんどくさくて動かない奴 :-P

[[id:859]] 2002-07-10 12:08:16

PerlにはMemoizeモジュールがあった

http://www.perldoc.com/perl5.8.0/lib/Memoize.html

[[id:1213]] 2002-09-18 12:02:37

できました（はぁと）

def memo(f,x)
a = f.call(x);
return Proc.new { | y |
if y == x then a
else f.call(y)
end
}
end

fib = Proc.new { | x |
if x == 0 then 0
elsif x == 1 then 1
else fib.call(x - 2) + fib.call(x - 1)
end
}
fib = memo(fib, 21);
fib = memo(fib, 22);
fib = memo(fib, 23);
fib = memo(fib, 24);
print fib.call(24);

fibの中で自分を呼ぶのに self.call() とかしたりしてハマってました。
----
- Proc.new{} の別名 proc{}, lambda{}
- aProc[arg]
- anObject.method(:name)
…などを知ったので第二版

def memo(f,x)
a = f[x];
return lambda { | y |
if y == x then a
else f[y]
end
}
end

def fib(x)
if x == 0 then 0
elsif x == 1 then 1
else fib(x - 2) + fib(x - 1)
end
end

fib = method(:fib)

fib = memo(fib, 21)
fib = memo(fib, 22)
fib = memo(fib, 23)
fib = memo(fib, 24)
print fib[24]

[[id:861]] 2002-08-06 23:19:09

Common Lisp 版

(defun memo (f x)
(let ((a (funcall f x)))
#'(lambda (y)
(if (eq x y)
a
(funcall f y)))))

(defun fib (x)
(cond ((eq x 0) 0)
((eq x 1) 1)
(t (+ (fib (- x 2)) (fib (- x 1))))))

(defvar fib #'fib)
(setq fib (memo fib 10))
(setq fib (memo fib 11))
(setq fib (memo fib 12))
(setq fib (memo fib 13))
(setq fib (memo fib 15))
(setq fib (memo fib 16))
(funcall fib 16)

[[id:865]] 2002-07-10 15:21:21

GikoForth版


: memo { f x | a y -- f' }
x f ::call -> a
:[ -> y
y x =
IF a ELSE y f ::call THEN
]: ::generate
;

: fib { x -- n }
x 2 <
IF x 0=
IF 0 ELSE 1 THEN
ELSE
x 1- recurse x 2 - recurse +
THEN
;

:[ fib ]: value fib

fib 31 memo -> fib
fib 32 memo -> fib
fib 33 memo -> fib
fib 34 memo -> fib

34 fib ::call .

5702887 ok


と、なりました。（あってる？）
----
fib(34)の答えということでいうと、うちのコの答えも5702887でした。
memo() のロジックということではよく分かりません。（爆
だってGikoForthさぱーり読めないんだもの。（火暴

----
「あってる？」というのはGikoForthのクロージャもどきの実装が「あってる？」という意味でした。ダイジョーブみたい。(^^;
- スタック操作命令を含まない版に差し換えました。やっぱり逆ポーランドですけれど‥‥‥(-_-;
----
memo() で作られるローカル変数の a がコールするたびに新しいものが用意されるのであれば大丈夫だと思います。

（自由変数という意味でのクロージャはコール元のローカル変数を束縛するのでまた違う意味になってきますが）

----
::generateメッセージが手続きブロックに送られるたびに、ローカル変数を新しい領域に複製しています。
なので、きっと大丈夫(^^;
一応memoった答えは瞬時に返ってきます。
（GCないのでメモリの解放を考えてないんだけども。←をい）

こうしてみるとMLだとcallとか使わずにf xだけで呼び出せるのがキレイですねぇ。

あと、レキシカルスコープは定義時に静的に変数を束縛しとけば良いのでコンパイラ向き、
ダイナミックスコープは実行時まで変数の束縛を遅延するからスクリプト言語向きかな、と思いました。

[[id:866]] 2002-07-30 23:21:44

継続渡しスタイル

関数呼び出しにあたって、パラメータとして続きの処理を渡すことで処理が進んで行くスタイル。
基本的に Call - Return ではなくなる。(ことが多い)

Masui:WebBasedアプリ -- あ"、Shiro さんダ。

[[id:1148]] 2002-09-08 20:18:22

Common Lisp による小さなインタプリタ "FOO"

継続渡しスタイルのコード例
http://www.paulgraham.com/lib/cint.lisp
- 印刷したらA4用紙に2枚、しかも半分("#|"から"|#"まで)はコメント。でも学ぶべきところは多い。
----
メモ

- 定義されている関数は @eval, @evlis, @evletrec, @apply の四つ。
- 最初に "@" がついているのは単に Common Lisp の元々の関数と名前が衝突しないため。
- 各関数の最後の引数は必ず 'cont' で、処理が終ったあとに続行するべきことが手続きとして渡される。
- 各手続きの処理は必ず tail-call の形で次に行うべき処理を呼び出す。(インタプリタが終るまで一切、呼び出し元への return がない。)
- それは引数で渡された cont だったり、 @xxx 関数のどれかだったりする。
- インタプリタ実行のコンテキスト情報はすべてパラメータとして次の関数に渡されるため Common Lisp のスタックフレームには一切保存されない。

----
コメントによるとインタプリタを起動するために与えるパラメータは
(@eval ; インタプリタのメイン評価関数
<expression> ; インタプリタに評価させるプログラム
'() ; 初期のバインディング(空リスト)
#'(lambda (x) x)) ; プログラム評価後にするべき継続。「結果の値を返しなさい」

----
((call/cc ...))がミソだね。
scheme使い以外理解できるんだろうか（ｗ
- ((call/cc ...)) はインタプリタに食わせるサンプルコードで、インタプリタ本文はもっと下の方にあります。
- call/cc を実現するのに call/cc を使っていない(Common Lispに call/cc はない)というところが面白いところですね。 当り前なんだろうけど、こう短いとびびります。

[[id:1233]] 2002-09-18 23:46:46

コンビネータ

組み合わせ子 (λ算法)
キーワードはコンビネータ？ (プログラミング言語:FPsystem)

[[id:1214]] 2002-09-18 12:18:07

"To Mock A Mockingbird"


邦訳:『ものまね鳥をまねる』森北出版
ISBN 4-627-01901-7

これにいろいろなコンビネータが紹介されています

[[id:1217]] 2002-09-18 13:09:27

top recent

HashedWiki version 3 beta
SHIMADA Keiki