fun word_get (): stropt
[stropt] は、有効な文字列もしくは NULL ポインタであるような optional 文字列型であることに注意してください。
もし [word_get] が NULL ポインタを返したなら、それは与えられた (単語の) ストリーム終端に逹っしたことを示しています。
これは [word_get] が状態を持つ関数であること意味しています。
一般的に、状態を持つ関数を使うことは貧弱なプログラミングスタイルであると考えられています。
例えば、libc の関数 [strtok] は状態がないと間違われるために悪名高いものです。
そしてその被害を受けた誰もが真実を知るのです。
ATS には、単純にそれらをテンプレートに変えることで状態を持つ関数を削除できる便利なアプローチがあります。
差し当り、動く実装を作ることに集中しましょう。
abstype wcmap_type = ptr typedef wcmap = wcmap_type[wcmap_type] がボックス化型で、つまりこの型のサイズはポインタの (型 [ptr] の) サイズになることに注意してください。
型 [wcmap] の値はどうやって生成すべきでしょうか？ 空のマップを作るために次の関数を導入しましょう:
fun wcmap_create (): wcmap
もし単語が出現したら、その発生回数を 1 増やす必要があります。
これは次の関数で行ないます:
fun wcmap_incby1 (map: wcmap, w: string): void
またそれらの出現回数に従って単語をソートする必要があるので、[wcmap] 値を羅列する関数を導入しましょう:
fun wcmap_listize (map: wcmap): list0 @(string, int)
ATS ライブラリの一部である libats には、多くのマップ実装があります。
データ構造に精通していれば、[wcmap] に最適な構造は hashtable-based map 実装であることは明確でしょう。
もちろん、平衡木 (例: AVL-tree) に基づいたマップ実装も同じく有効でしょう。
私自身の実験では、前者は後者よりも 2-3 倍程度高速でした。
fun WordCounting (): wcmap
これで [WordCounting] を呼び出すことによって、出現したそれぞれの単語からその出現回数へのマップである
[wcmap] を生成できます。
[WordCounting] は次のように実装できます:
implement WordCounting () = let // fun loop (map: wcmap): void = let // val opt = word_get () val issome = stropt_is_some (opt) // in if issome then let val () = wcmap_incby1 (map, stropt_unsome (opt)) in loop (map) end else () // end of [if] end // end of [loop] // val map = wcmap_create () val ((*void*)) = loop (map) // in map end // end of [WordCounting]本質的に、内部関数 [loop] は [word_get] を呼び出して単語を数えて、それから単語の出現回数を 1 増加させています; [word_get] が ([stropt_is_some] が false を返すような) NULL ポインタを返すと [loop] は終了します。
上記に示した ATS の抽象型を効果的に使ったトップダウンのプログラミングスタイルを、読者が正確に評価できることを、私は期待しています。 私個人の所見では、多くのプログラマはボトムアップスタイルのプログラミングを実用上使っています。 単語を数える問題が与えられたとき、彼等は [wcmap] (とそれに関連した関数群) もしくは [word_get] のような関数を実装することに注目しようとします。 単語を数えるような単純な問題なら、有能なプログラマは彼らが選んだどんなアプローチを用いても、おそらく扱えるでしょう。 けれども、より大きなより複雑な問題を取り扱う時、使われえないコードを書くボトムアップアプローチを用いた彼らは簡単に焦点を失ないうるのです。 ある意味では、プログラムを書くことは物語を語ることと似ています: もし語り部の焦点がはずれると、物語が一貫性を得るのは難しくなります。
fun char_get (): int
もし [char_get] が非負の整数を返したら、その整数は ASCII 文字です;
そうでなければ、それ以上文字がないことを示しています。
[char_get] に基づいた [word_get] のありうる実装は次のようになります:
implement word_get () = let // typedef charlst = list0(char) // fnx loop ( // argmentless ) : charlst = let val i = char_get () in // if i >= 0 then ( if isalpha (i) then loop2 (cons0{char}(int2char0(i), nil0)) else loop () // end of [if] ) else nil0((*void*)) // end // end of [loop] and loop2 ( res: charlst ) : charlst = let val i = char_get () in if isalpha (i) then loop2 (cons0{char}(int2char0(i), res)) else res // end of [if] end // end of [loop2] // val cs = loop () // in // case+ cs of | nil0 () => stropt_none ((*void*)) | cons0 _ => stropt_some (string_make_rlist (cs)) // end // end of [word_get][loop2] はアルファベット文字を集めるために呼び出され、[loop] は非アルファベット文字をスキップするために呼び出されることに注意してください。 ([fun] が置かれるべき場所にある) キーワード [fnx] は、[loop] と [loop2] が一緒にコンパイルされ、それら本体の末尾再帰呼出がローカルジャンプに変換できることを意味しています。 関数 [string_make_rlist] は与えられたリストの逆順の文字の並びから成る文字列を生成します。 例えば、'a', 'b', 'c' から成るリストなら、生成される文字列は "cba" です。
local // staload "libats/ML/SATS/basis.sats" // staload HT = "libats/ML/SATS/hashtblref.sats" // assume wcmap_type = hashtbl(string, int) // in (* in of [local] *) implement wcmap_create () = $HT.hashtbl_make_nil (i2sz(1024)) // end of [wcmap_create] implement wcmap_incby1 (map, w) = let // val opt = $HT.hashtbl_search (map, w) // in // case+ opt of | ~Some_vt (n) => { val-~Some_vt _ = $HT.hashtbl_insert (map, w, n+1) } | ~None_vt ((*void*)) => $HT.hashtbl_insert_any (map, w, 1) // end // end of [wcmap_incby1] implement wcmap_listize (map) = $HT.hashtbl_takeout_all (map) end // end of [local]上記で示したコード全体を含む実行可能なプログラムは、ファイル wordcnt.dats から入手できます。 またそこには Makefile もあります。
次のリストは、ハーマン・メルヴィルの小説「白鯨」の中で使われている単語の内、使用頻度の高い 100 個を抜き出したものです:
the -> 14515 of -> 6673 and -> 6464 a -> 4799 to -> 4683 in -> 4210 that -> 3080 it -> 2533 his -> 2513 i -> 2127 he -> 1894 but -> 1822 s -> 1816 with -> 1765 as -> 1750 is -> 1748 was -> 1645 for -> 1637 all -> 1535 this -> 1431 at -> 1331 by -> 1211 whale -> 1191 not -> 1169 from -> 1095 so -> 1066 be -> 1062 on -> 1062 him -> 1061 you -> 953 one -> 921 there -> 864 now -> 786 or -> 783 had -> 779 have -> 772 were -> 684 they -> 667 which -> 653 like -> 647 me -> 629 then -> 628 are -> 618 their -> 618 some -> 617 what -> 617 when -> 606 an -> 600 no -> 590 my -> 586 upon -> 566 out -> 537 man -> 527 up -> 523 into -> 522 ship -> 513 more -> 507 ahab -> 501 if -> 500 them -> 471 we -> 470 ye -> 470 sea -> 455 old -> 449 would -> 432 other -> 427 been -> 415 over -> 408 these -> 405 will -> 397 though -> 384 its -> 381 only -> 377 down -> 376 such -> 375 who -> 366 any -> 360 yet -> 345 head -> 344 boat -> 333 time -> 333 her -> 332 long -> 330 captain -> 327 very -> 323 here -> 321 about -> 317 do -> 316 still -> 312 than -> 311 great -> 306 those -> 306 said -> 303 before -> 298 has -> 293 must -> 293 two -> 292 t -> 291 most -> 285 seemed -> 283当然ですが、whale はこの小説で最もよく使われた名詞で、さらに2番目と3番目はそれぞれ ship と sea です。
fun{} char_get (): int
また、[char_get] を直接もしくは間接的に呼び出す関数は、テンプレートとして宣言される必要があります。
これは [word_get] と [WordCounting] も同様にテンプレートに変換する必要があることを意味しています:
fun{} word_get (): stropt fun{} WordCounting (): wcmapここで、次のような関数 [WordCounting_fileref] を宣言してみましょう:
fun WordCounting_fileref (inp: FILEref): wcmap
この関数は、与えられたファイルハンドルから全ての単語を読み出すような [WordCounting] の単なる変形です。
すると [WordCounting_fileref] は次のように実装できます:
local staload STDIO = "libc/SATS/stdio.sats" in (* in of [local] *) implement WordCounting_fileref (inp) = let // implement char_get<> () = $STDIO.fgetc0 (inp) // in WordCounting () end // end of [WordCounting_fileref] end // end of [local]これで別々のファイルハンドルについて、2つのスレッドが同時に [WordCounting_fileref] を呼び出しても安全です。 上記の [WordCounting_fileref] の実装を含む実行可能なプログラムは、ファイル wordcnt2.dats から入手できます。 またそこには Makefile もあります。
ATS のテンプレートシステムは、コードの組織化と再利用を容易にできる高度なプログラミングの機能です。 実際に使われるテンプレートを解説するために、より多くのプログラミング例を徐々に紹介します。
線形型を使うことで、プログラム wordcnt.dats を修正してメモリクリーンな実装にすることができました。 修正されたバージョンの全体は wordcnt_vt.dats から入手できます。 またそこには Makefile もあります。