ATSプログラミング入門:
Prev	Chapter 4. データ型	Next

例: 整数式の評価

整数式を表現するために、次のようなデータ型 IEXP を宣言しましょう:

datatype IEXP =
  | IEXPcst of int // constants
  | IEXPneg of (IEXP) // negative
  | IEXPadd of (IEXP, IEXP) // addition
  | IEXPsub of (IEXP, IEXP) // subtraction
  | IEXPmul of (IEXP, IEXP) // multiplication
  | IEXPdiv of (IEXP, IEXP) // division
// end of [IEXP]

IEXP に関連するコンストラクタの意味は明確です。 IEXP 型の値はしばしば抽象構文木と呼ばれます。例えば、式 (~1+(2-3)*4) の抽象構文木は次のようになります:

IEXPadd(IEXPneg(IEXPcst(1)), IEXPmul(IEXPsub(IEXPcst(2), IEXPcst(3)), IEXPcst(4)))

文字列で書かれた整数式を抽象構文木へ変換することを構文解析と呼びますが、ここでは取り扱いません。次に定義する関数 eval_iexp は整数式の抽象構文木を取り、式の値である整数を返します:

fun
eval_iexp
  (e0: IEXP): int =
(
case+ e0 of
| IEXPcst (n) => n
| IEXPneg (e) => ~eval_iexp (e)
| IEXPadd (e1, e2) => eval_iexp (e1) + eval_iexp (e2)
| IEXPsub (e1, e2) => eval_iexp (e1) - eval_iexp (e2)
| IEXPmul (e1, e2) => eval_iexp (e1) * eval_iexp (e2)
| IEXPdiv (e1, e2) => eval_iexp (e1) / eval_iexp (e1)
) (* end of [eval_iexp] *)

整数式を成すのに if-then-else もコンストラクトできると考えてみましょう。例えば (if 1+2 <= 3*4 then 5+6 else 7-8) のような整数式を書けるとします。 (1+2 <= 3*4) の判定は整数式ではなくブール式であることに注意してください。これは、ブール式を表現するデータ型 BEXP も宣言する必要があることを示しています。その上 IEXP と BEXP は次のように相互再帰的に宣言されるべきです:

datatype IEXP =
  | IEXPcst of int // integer constants
  | IEXPneg of (IEXP) // negative
  | IEXPadd of (IEXP, IEXP) // addition
  | IEXPsub of (IEXP, IEXP) // subtraction
  | IEXPmul of (IEXP, IEXP) // multiplication
  | IEXPdiv of (IEXP, IEXP) // division
  | IEXPif of (BEXP(*test*), IEXP(*then*), IEXP(*else*))
// end of [IEXP]

and BEXP = // [and] for combining datatype declarations
  | BEXPcst of bool // boolean constants
  | BEXPneg of BEXP // negation
  | BEXPconj of (BEXP, BEXP) // conjunction
  | BEXPdisj of (BEXP, BEXP) // disjunction
  | BEXPeq of (IEXP, IEXP) // equal-to
  | BEXPneq of (IEXP, IEXP) // not-equal-to
  | BEXPlt of (IEXP, IEXP) // less-than
  | BEXPlte of (IEXP, IEXP) // less-than-equal-to
  | BEXPgt of (IEXP, IEXP) // greater-than
  | BEXPgte of (IEXP, IEXP) // greater-than-equal-to
// end of [BEXP]

明らかに、整数式を評価する時にはブール式も評価する必要があります。次の2つの関数 eval_iexp と eval_bexp はそれぞれ整数式とブール式の評価のための関数で、予想される通りですが相互再帰で定義されています:

fun
eval_iexp
(
  e0: IEXP
) : int = (
//
case+ e0 of
| IEXPcst n => n
| IEXPneg (e) => ~eval_iexp (e)
| IEXPadd (e1, e2) => eval_iexp (e1) + eval_iexp (e2)
| IEXPsub (e1, e2) => eval_iexp (e1) - eval_iexp (e2)
| IEXPmul (e1, e2) => eval_iexp (e1) * eval_iexp (e2)
| IEXPdiv (e1, e2) => eval_iexp (e1) / eval_iexp (e1)
| IEXPif
  (
    e_test, e_then, e_else
  ) =>
  (
    eval_iexp (if eval_bexp (e_test) then e_then else e_else)
  ) // end of [IEXPif]
//
) (* end of [eval_iexp] *)

and
eval_bexp
(
  e0: BEXP
) : bool = (
//
case+ e0 of
| BEXPcst b => b
| BEXPneg (e) => ~eval_bexp (e)
| BEXPconj (e1, e2) =>
    if eval_bexp (e1) then eval_bexp (e2) else false
| BEXPdisj (e1, e2) =>
    if eval_bexp (e1) then true else eval_bexp (e2)
| BEXPeq (e1, e2) => eval_iexp (e1) = eval_iexp (e2)
| BEXPneq (e1, e2) => eval_iexp (e1) != eval_iexp (e2)
| BEXPlt (e1, e2) => eval_iexp (e1) < eval_iexp (e2)
| BEXPlte (e1, e2) => eval_iexp (e1) <= eval_iexp (e2)
| BEXPgt (e1, e2) => eval_iexp (e1) > eval_iexp (e2)
| BEXPgte (e1, e2) => eval_iexp (e1) >= eval_iexp (e2)
//
) (* end of [eval_bexp] *)

この例における整数式とブール式は全て変数を含まない定数式です。そのため、これらの式の評価に環境は必要ありませんでした。 ATS のコアのような簡単な値渡し (call-by-value) の関数型プログラミング言語の評価器をどのように実装するのか示すために、より進んだ例を別の章で紹介します。

この章のコード全体と追加のテストコードはオンラインから入手できます。 (訳注: このコードを atscc でコンパイルする際には -DATS_MEMALLOC_LIBC オプションが必要です。)

Prev	Home	Next
例: 2分探索木	Up	パラメータ多相