日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

キューマシンにおける不動点プログラミング
山口 文彦

キューマシンは先入れ先出しの記憶装置を持つ抽象計算機である。キューマシンは演算の並列実行に相性が良いとされている一方で、関数などの部分プログラムの呼出しを含むプログラムを単純なキューマシンの命令列で表現することに困難がある。ここで、部分プログラムはインライン展開し、再帰的な部分については不動点を用いることで、さまざまな計算手続きが単純なキューマシン上で表現できるのではないかと考えた。しかし、キューマシンにおける不動点プログラミングについて知見がない。そこで本稿では、スタックマシンにおける不動点プログラミングを参考に、キューマシンにおける不動点プログラミングについて考察する。

Queue machine is a type of computer which has first in, first out memory. Queue machine have goodpotential to concurrent execution, however, there is a diﬃculty on describing function call in simple queuemachine codes. This paper discusses fixed point programming on simple queue machine, which may enable
representing various calculation including recursive programs.

計算の木の葉ノードが別の木に展開されるような仕1 はじめに組みを単純なキューマシンで実行することは難しい。

キューマシン [1] は先入れ先出しの記憶装置 (キュー)なぜなら、葉の一つが高さのある木に置き換わるとすを持つ抽象機械である。演算子を節とし演算子の引数ると、置き換えられる木の節 (葉を含む) は命令列中を子とする木 (以下、これを計算の木と呼ぶ。単純なの離れた箇所 (それはすでに実行済の箇所であるかも式の場合は構文木に等しい) を考えたとき、キューマしれない) に挿入されなければならないからである。

シンの命令列は、計算の木を幅方向に巡回することで元々提案されたキューマシンアーキテクチャ [1] に得られる。したがって、ある演算や関数の引数となるおいては、命令キューを引数と呼出元の依存関係を保演算のうちで最上位のものが、命令列中に続けて登場持したままセグメントに分割し、子セグメントが全する。副作用のない純粋な関数型言語においては、演て実行済みになるまで親セグメントの実行を待つと算や関数の複数の引数は並列に計算することができいう同期の仕組みを導入している。これによって、関ることが知られているが、キューマシンにおいては、数呼び出しが実行されると、その関数の実行が終了

このような並列に計算できる演算が命令列の中に連するまで、関数の呼び出し元が待機することになる。

続して現れる。このことから、キューマシンは細粒度同じセグメントに配置された命令は並列に実行できの並列実行を考える際の計算モデルとして有用であるため、並列性を高めるためには、セグメントはできると考えられる。

るだけ大きい方がよい。極論として、計算の木の高さ

しかし、関数呼び出しなどのように、計算の途中で∗ Fixed-point Programming on Queue Machine.

This is an unrefreed paper. Copyrights belong tothe author.
Fumihiko YAMAGUCHI, 長崎県立大学情報システム学部情報セキュリティ学科, Dept. Information Security,
University of Nagasaki.

ごとに高々一つのセグメントしかないとすれば、それは単純なキューマシンと変わらない。
本稿では、単純なキューマシンに立ち返り、計算を表現する方法について考える。関数呼び出しが大きなオーバーヘッドとなっていることから、実行前にすべての関数呼び出しを展開しておくことを考える。再帰的な関数が使われていなければ、この展開によって計++算の木が作られ、キューマシンの命令列を完成するこ***とができると考える。このとき、再帰的な関数の扱い2が課題として残る。ここで、定義された関数の呼び出3+2

しを使わずに再帰的な計算を表現することができれ

452 3 * 2 5 + 4 * +2*
3+2452 5 2 3 + 4 * * +ば、課題の解決につながる。そのような計算の表現と
図1

して、不動点を用いた計算の表現がある。関数型言語

スタックマシンの命令列 (左) とキューマシンの命令列 (右)においては、匿名関数を用いた式として、再帰的な計算を表現することができる。しかし、キューマシンにデータキューおける不動点プログラミングについては知見がない。

命令キュー

手掛かりとして、スタックマシンにおける不動点プロ[][2 5 2 3 + 4 * * +]グラミングが挙げられる。とくに、スタックを用いた[2][5 2 3 + 4 * * +]インタプリタ言語である Postscript において、関数[2 5][2 3 + 4 * * +]不動点に相当するプログラムを書くことができ、それ[2 5 2][3 + 4 * * +]によって def (ブロックに名前を付ける、定義のため[2 5 2 3][+ 4 * * +]の命令) を用いずに再帰的な計算が表現できることが[2 3 7][4 * * +]分かっている [5]。本稿ではキューを用いた計算を表[2 3 7 4][* * +]

現する言語である FIFOL を、適宜拡張しながら議論[7 4 6][* +]する。FIFOL は Postscript に似た言語である。

[6 28]

[+]

[34]

[]

以下、キューマシン、不動点およびスタックマシン
における不動点プログラミングについて述べたのち、

図2

2 5 2 3 + 4 * * + の実行の様子

キューマシンにおける不動点プログラミングの例をいくつか示し、課題を明らかにする。

2 5 2 3 + 4 * * + が実行される様子を示している。図 2 の各行は、ある時点のデータキューと命令2 研究の背景キューが書かれている。いずれのキューも、中身の列

2. 1 キューマシンが [ ] で括られ、右から入って左から出るものとす

ある式の値を計算するキューマシンの命令列は、そる。実行の 1 ステップでは、命令キューの先頭を取の式の構文木を巡回して得られる。構文木の巡回にり出し、それがデータならデータキューに格納し、演よって命令列が得られる点では、スタックマシンと同算子なら、必要なだけのデータをデータキューから取様であるが、スタックマシンの命令列が構文木を深さり出して、演算結果をデータキューに格納する。命令優先で巡回したときの帰りがけ順にノードを記録しキューが空になった時点で、データキューには計算結て得られる (式をこのように記述する方法は逆ポーラ

果が格納されている。

ンド記法として知られている) のに対して、キューマ

FIFOL はキューを使った計算を記述するプログラ

シンの命令列は構文木を下方から幅優先で巡回するミング言語であり、2001 年夏のプログラミング・シ順にノードを記録することで得られる。例として中ンポジウムにおいて課題として (パズルとして) 登場

置記法で 2*3+(2+5)*4 と書かれる式の構文木を図 1した [2]。そのインタプリタの scheme による実装がに挙げ、スタックマシンおよびキューマシンの命令列公開されている [6]。

として表現する場合の構文木のたどり方と、それぞれの命令列を示す。
図 2 には、図 1 に示したキューマシンの命令列

キューマシンの並列性に着目した研究として、FI-FOL の SIMD 拡張に関する研究 [4] がある。この中でベクトル長さやマルチスカラの繰り返し数についても言及があるが、これらを可変にする繰り返しの構を表す際や命令列に名前を付ける (定義する) 際など造については未解決となっている。に使われる。また、スタックの先頭にあるブロックを実行する (実行すべき命令列の先頭にブロックの中身2. 2 不動点プログラミングを追加する) exec という命令が用意されている。

関数 F の不動点とは、x = F (x) となるような x

スタックマシンでは、関数の引数の相当するデータのことである。ここで、関数を引数とする関数の不動をスタックに積んで計算を行う。そこで、ブロックを点によって、再帰的な関数を表現することができる。

スタックに積めば、計算手順を引数とする計算を表現

このことは次のように説明される。

することができる。そのような計算の不動点であるよ

再帰的な関数 f はその定義の中で自分自身であるうな計算手順を構成することで、再帰的な関数に相当f を呼び出す関数である。f が、f ≡ D と定義されするプログラムを書くことが可能であることが分かっるとすると、この f の定義式の本体 D の中には識別ている [5]。具体的には Postscript における不動点プ子 f が自由に登場する。この f を λ 抽象して得られログラミングは次のように説明される。

る λf.D という関数を考える。この関数に x (この xF , G を Postscript の命令列であるとする。F がは関数である) を適用して (λf.D)x とすると、これG の不動点であることを、{F }G と F が同じ計算は元々の f とほぼ同様な計算をしながら、f を再帰をすることであるとする。G の中には、スタック呼び出しする代わりに x を呼ぶ計算を表す。ここで、の先頭に積まれた {F } を実行するための exec が元の再帰的な関数 f は、f ≡ D と定義される関数であると考えられる。このとき、G 中のこの exec をあるから、x = (λf.D)x を満たす x と同じ計算を表dup exec に置き換えて得られる命令列を G′ とするす。すなわち、f は λf.D の不動点である。と、命令列 {G′ } G′ は G の不動点となっている。こ純粋な λ 計算においては、式 F の不動点を得る不のことを示すには、{{G′ } G′ } G と {G′ } G′ が同動点演算子を構成することができる。不動点演算子

じ計算をすることを示せばよい。前者はスタックにとしては、Y オペレータ (λf.(λx.f (xx))(λx.f (xx))){{G′ } G′ } を積んで G を実行し、後者はスタックなどが知られている。に {G′ } を積んで G′ を実行する。ここで、G と G′

多くのプログラミング言語で、関数などの部分プロはスタックの先頭の積まれたブロックに対する動作グラムを定義する仕組みが用意されており、再帰的なだけが異なる。前者は {{G′ } G′ } に対して exec を計算を行うときには、そうした仕組みを使って、再帰行うので、ここで {G′ } G′ の計算が行われる。後者的な部分プログラムを定義することが一般的である。

は、{G′ } に対して dup exec が行われるので、(スしかし、不動点を用いることで、再帰的な計算を一つタックの先頭に {G′ } を二つ積んで exec を行うのの式として扱うことができる。関数の呼び出しを式で) やはり {G′ } G′ の計算が行われる。したがって、に置き換えるという点で、不動点プログラミングは、{{G′ } G′ } G と {G′ } G′ は同じ計算をする。以上

インライン展開と同様な意味合いを持つものと考えから {G′ } G′ は G の不動点となっていることが分られる。

かる。なお、{G′ } G′ は {G′ } dup exec と書くことができる。

2. 3 スタックマシンにおけるこの方法を使って、Postscript において、def を用

不動点プログラミングいることなく、再帰的な計算を表現することができスタックマシンの例として、Postscript インタプリる。なお、上記のように不動点を構成することはでき

タ [3] が挙げられる。

Postscript には、命令の列をブロックという形でデータとしてスタックに積む機能がある。ブロック
は、命令列を { } で括って表す。これは、条件分岐るが、Postscript の命令列からその不動点を得る不動点演算子を Postscript で書くことはできていない。

データキュー

[]データキュー命令キュー[ { dup exec } dup exec ][ { dup exec } ][ dup exec ][ H dup exec ]

[]
[ H ]

[ { dup exec } { dup exec } ] [ exec ][ H H ][ { dup exec } ][ H ][ dup exec ]
..
.

命令キュー

[ dup exec ][ exec ][ "hello" dup = exec ][ H "hello" ][ dup = exec ][ "hello" H H ]図3{ dup exec } dup exec の実行の様子[ = exec ][ H H ]

[ exec ]..
.

3 キューマシンにおける不動点プログラミング

図4{ "hello" dup = exec } dup exec の実行の様子

キューマシンインタプリタである FIFOL には、文字列を扱う機能がないので、¨ (ダブルクォーテー

Postscript に お け る ブ ロック と 同 様 に 、命 令 列 をション) で括られた文字列は、そのままデータキューキューに格納する構文が用意されている。これを用いに格納されることにする。このとき、hello と表示て、if などの条件分岐や loop という繰り返しが実しつづけるプログラムは、次のように書くことがで行される。しかし、キューの先頭にある命令列を命令きる。

キューに入れる命令は存在しない。ここでは、そのよ{ "hello" dup = exec } dup exec

うな exec という命令を追加して FIFOL を拡張し、このプログラムを実行したときのデータキュー

この拡張された FIFOL 上で不動点プログラミングをおよび命令キューの様子を図 4 に示す。なお、図 4考える。

では、紙面の大きさと見やすさのために、ブロック{ "hello" dup = exec } を H で表している。
3. 1 単純なループ

このプログラムのブロック中で、dup と exec のFIFOL の命令 dup は、キューの先頭から要素を間に = がある。これはもちろんこの時点でキュー取り出して、取り出した要素を 2 回キューに格納すの先頭にある "hello" を出力するためのものである。したがって、{ dup exec } dup exec というる。ここで、exec の引数は dup されてできるブ

命令列は、命令列 { dup exec } をキューに格納しロック { "hello" dup = exec } であり、= の引数て、これを複製したのち、キューの先頭の命令列を実は "hello" という文字列である。図 4 の 4 行目でこ行する。こうして exec によって dup exec が実行されらが交互に出現しているように、キューマシンの命れるとき、キューには { dup exec } が格納されて令列においては、ある演算を行おうとする演算の引数いるので、実行を無限に繰り返すプログラムとなる。と演算子が必ずしも近くにない。

また、このプログラムを実行したときのデータキューと命令キューの様子を図 3 に示す。
これはただ無限ループするだけのプログラムだが、3. 2 階乗の計算
もう少し意味のある計算として、階乗計算を行うプ

キューマシンにおいても (FIFOL には exec の導入

ログラムを次に示す。という拡張を必要としたものの) ある種の不動点プロ{ dup { rot pop pop }グラミングが可能であることが分かる。
さて次に、上記のような無限の繰り返しの中に別の計算を入れることを考える。例として hello と表示しつづけるプログラムを考えるが、実は FIFOL には{ rot rot dup rot rot dec mul
dup rot rot rot exec }rot rot rot ifzeroelse }dup 10 1 rot exec

このプログラムでは 10! を計算するが、プログラとを仮定している。すなわち、データキュー内のデーム中最下段にある 10 を別の非負整数値にすれば、そタ数が (あまり) 変化しないということである。こうの値の階乗を計算する。

することで、データキュー内のデータの位置調整をす

ここで、 rot はキューの先頭のデータを取り出しる場合にも rot の個数が定数個になる。て改めてキューに格納する (末尾に追加する) 命令である。このような命令が必要なのは、キューの中のデータの順序を調整するためである。

4 結論
キューマシンにおける不動点プログラミングにつスタックマシンであれば、ある計算 (関数) に必要いて考察した。いくつかのプログラム例を示して、な計算 (引数) は、その計算の近くで求められる。引

キューマシンにおいても関数定義ないしブロックの名数の順序を変更したい場合には、スタックの上部だ前付けを行うことなく、ある種の繰り返しを表現できけで入れ替えが可能である。しかし、キューマシンることを示した。

では他の計算の途中経過がデータキュー上にあるた

しかし、本稿で示した繰り返しは、繰り返しの中でめに、キューの中身を回すだけの命令によって、デーデータキューに格納されるデータ数が変らないものにタキュー全体をほぼ一周させる必要が生じることが限られている。これは、一般の再帰的な計算の表現である。

はなく、単純な繰り返ししか表現できていないことをこうした理由もあって、上記のプログラムでは、意味する。残念ながら、現在のところ、そのような計以下の二つの機能拡張をしている。dec は整数一つ算しか表現することができていない。この点についてを引数としてキューから受け取り、その整数から 1解決するような仕組みを考えることが今後の課題とを減じた値をキューに格納する命令である。また、なる。

ifzeroelse は整数と二つのブロックを引数としてキューから受け取り、整数が 0 であれば最初のブロッ

参 考 文 献クの中身を、そうでなければ二番目のブロックの中身[ 1 ] 前田敦司: 新しい計算モデル キューマシンとその並列関数型言語への応用, 情報処理学会論文誌, Vol.38,
No.3, pp.574–583, 1997
[ 2 ] 田中哲朗: プログラミングコンテスト実施報告, 夏のプログラミング・シンポジウム「プログラミングの鉄人—プログラミングの技」, pp. 3–14, 2001
[ 3 ] Adobe Systems 著, 桑沢清志 訳: Postscript リ
ファレンスマニュアル第三版, アスキー, ISBN: 9784756138224, 2001
[ 4 ] 大日向大地: SIMD 拡張 FIFOL を使った科学技術計算, 情報処理学会, 夏のプログラミング・シンポジウ
ム報告集 (2005 年), pp. 97–102, 2006
[ 5 ] 山口文彦: ML で不動点演算子を定義する, 情報処理学会, 夏のプログラミング・シンポジウム報告集 (2005年), pp. 103–108, 2006
[ 6 ] Eiichi Wada: fifol simulator,
http://www.iij.jp/~ew/sim.html, (last accessed:Sep. 4, 2017)

を命令キューに追加する命令である。
スタックマシンであれば dec は 1 sub などと書かれ、また ifzeroelse も 0 eq および ifelse を用いて書かれるところだが、キューマシンにおいては、この 1 や sub、0、eq および ifelse を適宜配置したり、結果を使う計算に渡すためにキューを回す必要が生じる。
この階乗計算プログラムでは、exec が 3 行目と 5行目に登場するが、いずれも最初のブロック (およびその複製) を実行する。このブロックを実行する時点で、データキューには、階乗計算の引数、計算の途中
経過、ブロックの 3 つのデータが格納されているこ