フローチャート言語

フローチャート言語(FCL) は、プログラム分析と特殊化、特に部分評価の基本概念を説明する目的で設計された、シンプルな命令型プログラミング言語です。この言語は、1989 年に Carsten K. Gomard と Neil D. Jones によって初めて発表されました。^[1]その後、1993 年に Peter Sestoft との共著^[2]や、1998 年に John Hatcliff の講義ノート^[3]で再登場しました。以下は、John Hatcliff の講義ノートに登場した FCL について説明しています。

FCL は、フォン ノイマン コンピューターがプログラムを実行する方法に近い命令型プログラミング言語です。プログラムは、暗黙の状態、つまりグローバル メモリを維持しながら、一連のコマンドに従って順番に実行されます。FCL には手順の概念はありませんが、条件付きジャンプと無条件ジャンプが用意されています。FCL プログラムの抽象呼び出しグラフは単純なフロー チャートであるため、FCL はその名前にふさわしいものです。

FCL プログラムは、名前付きの値の有限の系列をパラメータとして入力し、結果として値を生成します。

FCL の構文はBackus-Naur 形式を使用して指定します。

FCL プログラムは、正式なパラメータ宣言のリスト、エントリ ラベル、および一連の基本ブロックです。

< p >  ::= "(" < x > * ")" "(" < l > ")" < b > +

当初、この言語では負でない整数変数のみが許可されます。

基本ブロックは、ラベル、割り当てのリスト、およびジャンプで構成されます。

< b >  ::=  < l > ":" < a > * < j >

代入は、式に変数を割り当てます。式は、定数、変数、または組み込みの n 項演算子の適用のいずれかです。

< a >  := < x > ":= < e > 
< e >  := < c > | < x > | < o > "(" < e > * ")"

プログラム全体で出現する変数名は、プログラムの先頭で宣言する必要はありません。プログラムの先頭で宣言された変数は、プログラムへの引数を指定します。

値は負でない整数のみであるのと同様に、定数も同様です。副作用がない限り、一般的な演算のリストは無関係ですが、例外として 0 による除算などがあります。

< c >  ::= "0" | "1" | "2" | ...
 < o >  ::= "+" | "-" | "*" | "=" | " < " | " > " | ...

ここで、=、< 、... は C と同じ意味を持ちます。-の意味は、xy<0 の場合、xy=0 となるということです。

^{n>2 の場合に n番目の} フィボナッチ数を計算するプログラムを作成します。

(名詞)
(初期化)

初期化: x1 = 1
      x2 = 1

嘘: x1 = x1 + x2

      t = x1
      x1 = x2
      x2 = t

      ｎ = -(ｎ 1)

      if >(n 2) then fib else exit

終了: 戻り値 x2

ここで、 fibのループ不変量は、x1 が (i+2-1)^番目、x2 が (i+2) 番目のフィボナッチ数であること^{です。ここで、i は}fibがジャンプした 回数です。

プログラムの実行トレースを表示することで、n=4 の場合のメソッドの正しさを確認できます。

${\displaystyle {\begin{aligned}&\left({\mathtt {init}},\ \left[n\mapsto 4,\ x1\mapsto 0,\ x2\mapsto 0,\ t\mapsto 0\right]\right)\\\rightarrow &\left({\mathtt {fib}},\ \left[n\mapsto 4,\ x1\mapsto 1,\ x2\mapsto 1,\ t\mapsto 0\right]\right)\\\rightarrow &\left({\mathtt {fib}},\ \left[n\mapsto 3,\ x1\mapsto 1,\ x2\mapsto 2,\ t\mapsto 0\right]\right)\\\rightarrow &\left(\left\langle {\mathtt {halt}},\ 3\right\rangle、\ \left[n\mapsto 2、\ x1\mapsto 2、\ x2\mapsto 3、\ t\mapsto 0\right]\right)\end{aligned}}}$

はプログラムの最終状態を示し、戻り値は です。 ${\displaystyle \left\langle {\mathtt {halt}},\ v\right\rangle }$${\displaystyle v}$

可逆フローチャート言語（RL）は、各計算プロセスが可逆である可逆コンピューティング用に設計された、シンプルな可逆命令型プログラミング言語です。^[4] RLは、ステップ、テスト、アサーションを組み合わせて、プログラムの可逆性を保証します。

RL では、決定論的な逆方向計算を可能にし、処理中に情報が失われないようにする可逆プログラムの構築を重視しています。この特性により、RL は、通常は不可逆な操作を伴う従来のフローチャート言語とは区別されます。RL の構文とサンプル プログラムは、従来のフローチャート言語によく似ていますが、可逆性を確保するための制約が追加されています。これには、可逆ループ、可逆条件、アトミック計算ステップの可逆性が含まれます。

可逆性制約のため、RL は従来のチューリングマシンよりも計算能力は劣りますが、可逆チューリングマシン (RTM) と同等であり、可逆プログラミングの基礎を築きます。たとえば、構造化プログラム定理の可逆バリアントは、RL を使用して効果的に分析でき、可逆コンピューティングの理論的基礎におけるその重要性を示しています。また、RL の構造化バリアント (SRL: 構造化可逆フローチャート言語) ^[4]もあり、これは、プログラムの可逆性を保証する方法でシーケンス、選択、および反復を組み合わせています。