ジェンセンの装置

イェンセンの装置は、名前による呼び出しを利用するコンピュータプログラミング技術である。これはデンマークのコンピュータ科学者ヨーン・イェンセンによって考案された。イェンセンは、 Regnecentralenでピーター・ナウアと共に働いていた。彼らは、 ALGOL 60の最も初期の正しい実装の一つであるGIER ALGOLコンパイラの開発に携わっていた。ALGOL 60は名前による呼び出しを使用していた。^{[1] [2] [3]}チューリング賞受賞のスピーチの中で、ナウアはイェンセンと共にGIER ALGOLで働いたことについて言及している。

説明

ジェンセンの手法は、名前による呼び出しと副作用を利用しています。名前による呼び出しは、引数の評価を実際に手続きで使用されるまで遅らせる引数渡しの規則であり、これは手続きのコピー規則の帰結です。名前による呼び出しはALGOLによって導入されました。

ジェンセンの装置の典型的な例は、級数の合計を計算する手順である。[ ^{4] [5] [6]}${\displaystyle \textstyle \sum _{k=\ell }^{u}a_{k}}$

 実数プロシージャSum(k, l, u, ak)
      値l, u;
      整数k, l, u;
      実数ak;
      コメントk と ak は名前で渡されます。
   実数sの開始。
      
      s := 0;
      k := lの場合、ステップ1でuが実行するまで
         s := s + ak;
      合計 := s
   終わり;

このプロシージャでは、インデックス変数kと合計項はak名前で渡されます。名前による呼び出しにより、プロシージャはループ実行中にインデックス変数の値を変更することができますfor。また、名前による呼び出しは、akループの各反復処理中に引数を再評価します。通常、akは変化する（副作用のある） に依存しますk。

たとえば、実数配列の最初の 100 項の合計を計算するコードは次V[]のようになります。

合計(i, 1, 100, V[i])。

の実行中Sum、実際の引数はループiの各ステップで増加しfor、 の各プロシージャの評価ではakの現在の値を使用してi連続する配列要素にアクセスしますV[i]。

ジェンセンの手法は一般論です。二重和は次のように表すことができます。

合計(i, l, m, 合計(j, l, n, A[i,j]))

関数Sumは、適切な式を用いるだけで任意の関数に適用できます。整数の和を求める場合は式は となりSum(i,1,100,i);、整数の平方和を求める場合はとなりますSum(i,1,100,i*i);。^[7]式の数値積分を開始するには、 の場合と非常によく似た方法を用い、式を少し変形するとよいでしょうSum。

の評価はサンクakによって実装されます。サンクは本質的には環境を持つサブルーチンです。サンクは引数を持たないクロージャです。手続きが仮引数の値を必要とするたびに、サンクを呼び出します。サンクは、呼び出し元のコードのスコープ（手続きのスコープではありません）内で実引数を評価します。

この名前渡し機能がない場合、コンピュータ言語のプロトコルに従って渡される式を具体化する関数を定義するか、各使用法に応じて必要な式を選択するための何らかの取り決めとともに概要関数を作成する必要があります。

GPS

もう一つの例は、DE KnuthとJN MernerのALGOL 60 confidentialに記載されているGPS（General Problem Solver）です。^[8]

実 手順GPS(I, N, Z, V);実数I, N, Z, V;
    begin  for I := 1 step 1 until N do Z := V; GPS := 1 end ;

以下は、GPS を使用して m 番目の素数を見つける単一のステートメントです。

I := GPS(I, if I=0 then -1.0 else I, P, if I=1 then 1.0 else 
   if GPS(A, I, Z, if A=1 then 1.0 else 
      if entier(A)×(entier(I)÷entier(A))=entier(I) ∧ A<I
       then 0.0 else Z) = Z then 
      ( if P<m then P+1 else I×GPS(A, 1.0, I, -1.0)) else P)

(注: 元の論文では、末尾近くの式は となっていますが、これは ALGOL 60 のforGPS(A, 1.0. I, 0.0)文の意味の仕様における特殊なケースによるものです。)

批判

ジェンセンの手法は名前による呼び出しに依存しているが、名前による呼び出しは複雑で、いくつかの問題を抱えている。そのため、ほとんどの言語では名前による呼び出しは利用できない。クヌースは、ALGOL 60ではincrement(n)引数を1つ増やす手続きを表現できないと述べている。呼び出しは、アクセスごとに変化する関数のincrement(A[i])場合、期待される動作を実行しない。 ^[9]クヌースは、「言語を拡張するために、この目的のために手続きのみに頼るのではなく、『マクロ』定義機能を使用することで、より満足のいく実行プログラムが得られる」と述べている。 i

他にも、引数を交換する名前呼び出し手順には微妙な問題が発生する可能性があると指摘する人もいます。^[10]明らかな交換手順は次のようになります。

手順swap(a, b)
  整数a, b;
  開始
    整数temp;
    温度:=a;
    a := b;
    b := 温度;
  終わり;

この手続きは多くの引数に対しては正しく動作しますが、 の呼び出しにswap(i,A[i])問題があります。コピールールを使用すると、以下の割り当てが発生します。

温度:= i;
 i := A[i];
 A[i] := 温度;

問題は、2番目の代入で が変更されるiため、A[i]3番目の代入の がおそらく開始時と同じ配列要素にならないことです。一方、この手続きを逆に記述した場合（bをaではなくtempに保存する）、 として呼び出されない限り、目的の動作が実行されます。（より安全な方法として を使用します。） swap(A[i],i)swap()temp1 := a; temp2 := b; a := temp2; b := temp1;

参照

• コールスタック、スタックフレーム、静的リンク、および表示（環境リンクを含むクローズ）
• ダフの装置
• 関数を値として渡し、返す方法のFunarg 問題
• 男性または少年テスト、環境テスト

参考文献

1. Naur, Peter (2005). Peter Naur Lecture Video. ACM Awards . デンマーク: Association for Computing Machinery . 2020年9月11日閲覧。
2. David (2006年3月1日). 「ソフトウェアのパイオニア、ピーター・ナウアがACMチューリング賞を受賞」ACM公共政策. Association for Computing Machinery . 2020年9月11日閲覧。
3. “ACM: Fellows: Peter Naur, Professor Emeritus, University of Copenhagen, Citation”. 2005年. 2008年2月12日時点のオリジナルよりアーカイブ。 2020年9月21日閲覧。2008年2月12日アーカイブ - Wayback Machine
4. マクレナン、ブルース・J. (1987). 『プログラミング言語の原則：設計、評価、実装』（第2版）. ホルト、ライナーハート、ウィンストン. pp.  141–2 . ISBN 0-03-005163-0。
5. Dijkstra, EW (1961年11月). 「ALGOL 60の擁護（編集者への手紙）」. Communications of the ACM . 4 (11): 502– 503. doi : 10.1145/366813.366844 . S2CID  34185299.
6. Knuth, DE (1967年10月). 「ALGOL 60に残る問題点」. Communications of the ACM . 10 (10): 611– 617. doi : 10.1145/363717.363743 . S2CID  10070608.
7. は用語の引数をSum必要とするため、型変換が想定されます。real
8. クヌース、ドナルド E.ジャック・N・マーナー（1961年6月）。 「ALGOL 60 機密」。共通。 ACM。4 (6): 268–272 .土井: 10.1145/366573.366599。S2CID  22215746。
9. Knuth 1967、p. 613。たとえば、は2回increment(A[increment(j)])増加しますj。
10. マクレナン 1987

外部リンク

• ALGOLスタイルのブロック構造と名前による呼び出しのための標準的なストアレスセマンティクス