ATSプログラミングチュートリアル:
PrevNext

Chapter 9. 再帰

ATS において再帰の概念はあちこちに現われます。 例えば、静的には再帰的に定義された種 (データ種) や型 (データ型) があり、また動的には再帰的に定義された関数があります。 言葉の上では、単語 再帰 は "戻る (go back)" を意味しています。 あるモノが再帰的に定義されているなら、それ自身の定義中にそのモノを書くことができることを意味しています。 再帰関数と非再帰関数を定義する (もしくは実装する) いくつかの方法を次に示します。 このとき後者は前者の特殊ケースです。

キーワード fun は再帰関数定義の開始に使います。 例えば、次のコードは再帰関数の定義です: 

fun
fact(x: int): int =
  if x > 0 then x * fact(x-1) else 1
(* end of [fact] *)

非再帰関数は、それ自身の定義中でそれ自身を使う再帰関数の特殊形です。 そのため、もちろん非再帰関数の定義の開始に fun を使うこともできます。 けれども、非再帰として定義されていることを明示的に示す必要があるのであれば、キーワード fn を使うことができます。 例えば、非再帰関数の定義は次のように与えられます: 

fn square(x: int): int = x * x

上記の関数は次のような名前とラムダ式を繋ぐ束縛にコンパイラによって変換されます: 

val square = lam (x: int): int => x * x

別の例として、次のコードでは fact が二度現われて、2つの別個の関数を差していることに注意してください: 

fn
fact(x: int): int =
  if x > 0 then x * fact(x-1) else 1
(* end of [fact] *)

最初の (等号の左側にある) fact 定義済みの (非再帰の) 関数を参照しており、2番目は以前に宣言されたものを参照しています。

再帰関数は再帰的な値としても定義できます。 例えば、上記で定義した再帰関数 fact は次のように定義することもできます: 

val
rec
fact : int -> int =
lam (x) =>
  if x > 0 then x * fact(x-1) else 1
(* end of [fact] *)

このとき、キーワード rec は fact が再帰的に定義されていることを示しています。 つまり、それはそれ自身の定義中に現われることができます。 実際、fact の前者の定義は後者にコンパイラによって変換されます。 もちろん、再帰を実装するのに参照を使うこともできます: 

val
fact = ref<int->int>($UNSAFE.cast(0))
val () =
!fact :=
(
  lam (x:int):int => if x > 0 then x * !fact(x-1) else 1
) (* end of [val] *)

しかし、これは私の推奨するスタイルではありません。 不動点式として fact を定義するまた別の方法を紹介します: 

val
fact =
fix f(x: int): int =>
  if x > 0 then x * f(x-1) else 1
(* end of [fact] *)

もちろん望むなら、不動点式をラムダ式で置き換えることがいつでも可能です。 例えば、lambda(x:int):int => x+x は fix _(x:int):int => x+x のように書くこともできます。

相互再帰関数を定義するためには、関数定義の連結にキーワード and を使います。 例えば、次のコードは2つの関数 isevn と isodd を相互再帰的に定義しています: 

fun
isevn(x: int): bool =
  if x > 0 then isodd(x-1) else true
and
isodd(x: int): bool =
  if x > 0 then isevn(x-1) else false

読者の推測する通りですが、上記のコードは (2つの相互再帰値を定義するために) 次のような形にコンパイラによって変換されます: 

val
rec
isevn : int -> bool =
  lam (x) => if x > 0 then isodd(x-1) else true
and
isodd : int -> bool =
  lam (x) => if x > 0 then isevn(x-1) else false

もちろん非再帰関数の定義を連結するのに、キーワード and を使うことはできます。 しかし、そのような使用はまれでしょう。

ここでは、ATS における関数定義の方法全てを紹介しませんでした。 例えば、ATS ではスタックに確保されたクロージャ関数を定義することもできます。 そしてこの関数は再帰的にも非再帰的にも定義できるのです。 このチュートリアルの別の章でそのような関数を紹介するかもしれません。

しばしば、ある場所で関数に対するインターフェイス (すなわち型) を宣言し、そしてその定義 (もしくは実装) を別の場所で与えることがあります。 例えば、はじめに次のような宣言を導入します: 

extern fun fact (x: int): int

その後、上記の宣言に一致する fact を実装することができます: 

implement
fact (x) =
  if x > 0 then x * fact(x-1) else 1
// end of [fact]

関数定義の開始に implement が使われると、(それ自身を含む) 前に宣言したシンボルがその定義中に現われることができます。 好ましいなら、implement を implmnt に置き換えることもできます。

この章で使ったコード全体は オンライン から入手できます。

PrevHomeNext
ドット記号オーバーロードUpデータ型