t-nissieの日記： 【電脳】Erlangで遊んでみた 番外編 たらい回し関数，ネイティブコンパイラ，native compiler，計時，型推論

『お気楽 OCaml プログラミング入門』というサイトにのっている
末尾再帰のある「たらい回し関数」を Erlang の native compiler の
HiPE (High Performance Erlang) でコンパイルして実行時間を
計ってみる．

よく知らないけど，ネイティブコンパイラは型推論ってのをやってるの？

この「たらい回し関数」ってのの収束は保証されているのだろうか？→保証される
追記：竹内郁雄が考えたのをMcCarthyって人が間違えて憶えてひろめたらしい．
たらい回し関数によるGCC、OCaml、Haskellの速度比較
竹内関数
スライド：どう転んでもLisp

実行結果（単位はμ秒．コンパイルのときnativeを付けると４倍くらい速くなるみたい．）:

Erlang R15B02 (erts-5.9.2) [source] [smp:8:8] [async-threads:0] [hipe] [kernel-poll:false]
 
Eshell V5.9.2  (abort with ^G)
1> c(recursive).
{ok,recursive}
2> recursive:tak(18,9,0).
9
3> timer:tc(recursive, tak, [18,9,0]).
{501940,9}
4> timer:tc(recursive, tak, [18,9,0]).
{500840,9}
5> timer:tc(recursive, tak, [18,9,0]).
{501064,9}
6> c(recursive, native).
{ok,recursive}
7> timer:tc(recursive, tak, [18,9,0]).
{129403,9}
8> timer:tc(recursive, tak, [18,9,0]).
{130020,9}
9> timer:tc(recursive, tak, [18,9,0]).
{129576,9}
10>

肥大化しつつある recursive.erl:

-module(recursive).
-export([factorial/1]).
-export([fibonacci/1]).
-export([fibonacci2/1]).
-export([counter/1]).
-export([count_words/1]).
-export([tak/3]).
 
%%% N!
factorial(0) ->
    1;
factorial(N) ->
    N * factorial(N-1).
 
%%% Fibonacci sequence (slow version)
fibonacci(0) ->
    0;
fibonacci(1) ->
    1;
fibonacci(N) ->
    fibonacci(N-1) + fibonacci(N-2).
 
%%% Fibonacci sequence (fast tail-call-optimization version)
%%% http://en.literateprograms.org/Fibonacci_numbers_%28Erlang%29
fibonacci2_tr(   0, Result, _Next) ->
    Result;
fibonacci2_tr(Iter, Result,  Next) ->
    fibonacci2_tr(Iter-1, Next, Result+Next).
fibonacci2(N) ->
    fibonacci2_tr(N, 0, 1).
 
%%% count to N
counter_tr(1, Current) ->
    io:format("~w~n",[Current]);
counter_tr(N, _Current) when N < 1 ->
    N;
counter_tr(N, Current) ->
    io:format("~w~n",[Current]),
    counter_tr(N-1, Current+1).
counter(N) ->
    counter_tr(N,1).
 
%%% count the number of words in a string
count_words_tr([],Counter) ->
    Counter+1;
count_words_tr([32|T],Counter) ->
    count_words_tr(T,Counter+1);
count_words_tr([_|T],Counter) ->
    count_words_tr(T,Counter).
count_words(T) ->
    count_words_tr(T,0).
 
%%% tak
tak( X, Y, Z ) when X =< Y ->
    Z;
tak( X, Y, Z ) ->
    %% io:format("~w ~w ~w~n",[X,Y,Z]),
    tak( tak( X-1, Y, Z ),
     tak( Y-1, Z, X ),
     tak( Z-1, X, Y ) ).
 
%%% tarai http://ja.wikipedia.org/wiki/%E7%AB%B9%E5%86%85%E9%96%A2%E6%95%B0
tarai( X, Y,_Z ) when X =< Y ->
    Y;                           %%% Not Z %%%
tarai( X, Y, Z ) ->
    %% io:format("~w ~w ~w~n",[X,Y,Z]),
    tarai( tarai( X-1, Y, Z ),
           tarai( Y-1, Z, X ),
           tarai( Z-1, X, Y ) ).

収束ではなく停止性

[parsley (5772)]

この「たらい回し関数」ってのの収束は保証されているのだろうか？

停止性は証明されています
Notes on higher-dimensional tarai functions [arxiv.org]

Code読みましたが、関数名Takだと別の関数になってしまうので、Taraiの方がいいと思います

--
Copyright (c) 2001-2014 Parsley, All rights reserved.

Re:収束ではなく停止性

[t-nissie (8647)]

コメントありがとうございます．
Erlangで一秒以内で終わるのはTakで，Taraiは数分かかるみたいです．
closureってのを使って遅延評価すると速くなるみたいです．
http://d.hatena.ne.jp/sfujiwara/20070513/1179067776

いろいろ追記しておきました．

リンクの論文は引数が３より大きくても停止するっていう証明ですね．
簡単な関数なのに驚くべき深遠な世界がひろがってますね．

--
love && peace && free_software
t-nissie