コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

利用者:Mpsuzuki/sandbox5

プログラミング言語における可変長配列（かへんちょうはいれつ、英語: variable-length array: VLA）とは、コンパイル時には長さが決まっておらず、実行時に長さが決まる配列データ構造である [1]。類義語に「動的配列」がある。動的配列と区別するのは、初期化後には長さを変更できない配列を指す場合である（動的配列は一般には初期化後にも長さを変更することもできるものを指す）。またさらに基本的な配列と同様に自動変数であって明示的な解放が不要なものに限定する場合もある（C言語など）。本項では主にこの狭義のVLAについて述べる。

配列の固定長・可変長および静的・動的の区分
コンパイル時の
定数での指定		 初期化時の
変数での指定		 初期化後の
変更
狭義の固定長配列 必須 不可 不能
狭義の可変長配列
（広義の固定長配列） 		無効[2] 必須 不能
広義の可変長配列
（動的配列） 		可能 可能 可能

古くからあるコンパイル型言語のうち Ada、 ALGOL [注釈 1]、 COBOL などの配列は、宣言と初期化に分けられておらず、初期化時に一度だけ長さを定めることができるよう設計されているため、 狭義の固定長配列・狭義のVLAの対比を持たない。 同様に、インタプリタ型言語の APL、 J言語 も宣言と初期化が分けられておらず、初期化時に一度だけ長さを定めることができる。

動的配列ではない狭義のVLAを追加したプログラミング言語には、 C99 [注釈 2] [注釈 3]、 Fortran 90がある。

Object Pascal（Borland Delphiで使用される言語）では狭義のVLAではなく動的配列を拡張した [注釈 4]。 また、Rustも配列はコンパイル時に長さを定めなければならない狭義の固定長配列だが [10]、標準ライブラリのstd::vecは初期化後にも長さを変更できる動的配列であり [11]、狭義のVLAではない動的配列である。

Java、C#などの現代的なオブジェクト指向言語の配列クラスは 当初から動的配列として設計され、 コンパイル時に長さを定めなければならない狭義の固定長配列もVLAも持たない。 ただし、パフォーマンスの観点からC++におけるstd::arrayクラスや、 C#におけるSpanクラスあるいはstackalloc演算子のような、 初期化時に一度だけ長さを決めることができるVLAに似たクラスを導入する例がある。

C言語の拡張とVLA

[編集]

C99以前のC言語のようにVLAを持たない環境では、自動変数の有効期間を持つメモリ領域を動的に割り当てるalloca()関数 [注釈 5] によって同等の機能を実装することがあった。

C++言語規格自身はCのような記法の可変長配列を含まないため [注釈 6]、 標準ライブラリのstd::vectorクラスを可変長配列と呼ぶ文書もある [注釈 7]。 狭義には、初期化後に長さを変更できないものをVLA、初期化後も長さを変更できるものをDynamic Array（英語版）と呼んで区別している [注釈 8]。 この区別に従えば、初期化後に長さを変更できるstd::vectorは動的配列であり、VLAではない。 しかし、固定長配列・可変長配列・動的配列の3つを異なるものとして備えた言語が少ないこともあり、 プログラミング言語解説文書においては可変長配列と動的配列を区別しないものも少なくない [注釈 9]。

メモリ

[編集]

割り当て

[編集]

プログラミング言語規格の多くはメモリの管理方式について詳細を定めないが [注釈 10]、 セグメント方式によってメモリを管理する処理系では、実行時の管理方法としてスタック方式とヒープ方式を併用するものが多い [注釈 11]。 この2つは特性が大きく異なるため、古いプログラミング言語の処理系では、 自動変数のメモリはスタック領域に、動的割り当てのメモリはヒープ領域にとることが多かった [注釈 12]。 狭義のVLAは自動変数でありながらメモリを動的に割り当てるが、例えばGNU Cコンパイラに含まれるFortranコンパイラは固定長配列と同様にスタック上に割り当てる[20]。

割り当ての上限量と失敗

[編集]

C言語規格においては、固定長配列と同様にsizeof演算子によってVLAのバイト容量を得られることが定められているため [注釈 13]、VLAの上限はsizeof演算子の戻り値の上限であるSIZE_MAXバイトに制限されることになる[注釈 14]。 ヒープ領域がギガバイトサイズの環境ではSIZE_MAXもギガバイト単位となることが多いので、ギガバイトサイズのVLAが文法上は許される。

ただしVLAを必須とするC99に準拠する処理系であっても上限値までのVLAを実際に割り当てられる保証は無い。 個別の関数の実行にあたって用意されるスタック領域は数MB程度という環境が多く [注釈 15]、 VLAをスタック領域に割り当てる処理系であれば、巨大なVLAの割り当てはスタックオーバーフローを起こす。 malloc()関数のような動的メモリ割り当てはその失敗を戻り値によって知ることができるが、 固定長配列・VLAとも割り当ての失敗はセグメント破壊のシグナル [注釈 16]などで検知するしかない。 従って、単一スコープ内でmalloc()とfree()を1度だけ行う処理であっても、VLAで単純に書き換え可能とは言えない。

ポインタを通じたVLAへのアクセス

[編集]

いくつかのプログラミング言語では、動的に割り当てたメモリをポインタで参照している場合、そのサイズをポインタから知ることはできず、別途長さを管理する変数が必要である（C言語など）。このような言語でもVLAは固定長配列と同様に配列のポインタ変数からサイズを知ることができる。 ただし、VLAのメモリアドレスをポインタを介して間接参照した場合、そのポインタは不完全な型と見なされ、sizeof演算子などでサイズを取得できない[24]。

例

[編集]

次のC99の関数は、指定されたサイズの可変長配列を割り当て、浮動小数点の値で埋めて、別の関数に渡す。配列は自動変数として宣言されているため、read_and_process() から戻るとその存続期間が終了する。 例に示したprocess()関数のように、可変長配列を他の関数に渡す場合、可変長配列とその長さを渡す必要があるが、C99では長さを指定する引数は可変長配列の引数よりも前に置かなければならない [注釈 17]。 

float read_and_process(int n)
{
    float vals[n];

    for (int i = 0; i < n; i++)
        vals[i] = read_val();
    return process(n, vals);
}


以下はAdaにおける同じ例である。Adaの配列は境界を持っている。従って、長さをProcess関数に渡す必要はない。 

type Vals_Type is array (Positive range <>) of Float;

function Read_And_Process (N : Integer) return Float is
   Vals : Vals_Type (1 .. N);
begin
   for I in 1 .. N loop
      Vals (I) := Read_Val;
   end loop;
   return Process (Vals);
end Read_And_Process;

Fortran 90での同等の関数は次の通りである。コンパイル時にプロシージャ・インターフェイスを検査するFortran 90の機能を利用する場合、process()関数に長さnを渡す必要は無い。 

function read_and_process(n) result(o)
    integer,intent(in)::n
    real::o

    real,dimension(n)::vals
    integer::i

    do i = 1,n
       vals(i) = read_val()
    end do
    o = process(vals)
end function read_and_process

一方、関数がFortran 90以前の呼び出しインターフェイスを使用する場合は、まず（外部）関数を宣言し、配列の長さを引数として明示的に渡す必要がある（Cの場合と同様だが、長さの引数を先に渡すという制限は無い）。 

function read_and_process(n) result(o)
    integer,intent(in)::n
    real::o

    real,dimension(n)::vals
    real::read_val, process
    integer::i

    do i = 1,n
       vals(i) = read_val()
    end do
    o = process(vals,n)
end function read_and_process

次のCOBOLのコード断片は、PEOPLE-CNT値で指定された長さ（メンバー数）を持つレコードの可変長配列DEPT-PERSONを宣言する。 

DATA DIVISION.
WORKING-STORAGE SECTION.
01  DEPT-PEOPLE.
    05  PEOPLE-CNT          PIC S9(4) BINARY.
    05  DEPT-PERSON         OCCURS 0 TO 20 TIMES DEPENDING ON PEOPLE-CNT.
        10  PERSON-NAME     PIC X(20).
        10  PERSON-WAGE     PIC S9(7)V99 PACKED-DECIMAL.


オブジェクト指向言語における呼称

[編集]

JavaやC#などの配列をクラスとして持つオブジェクト指向言語は 初期化の際にコンストラクタを実行するため [注釈 18]、 必ずしもコンパイル時に長さを定めなくても良いことが多い。 また、各インスタンスに割り当てたメモリ領域をデストラクタによって解放でき、 またガベージコレクタも備えているため、 自動変数にヒープ領域を用いることの難点はある程度解消されている。

そのため、これらの言語が持つ配列クラスは、 長さを決定するタイミングがコンパイル時か・初期化時かという対比によって固定長配列・可変長配列と呼ぶのではなく、 初期化後の拡大縮小の可否によって固定長配列・可変長配列と呼ぶことが多い。 これらの言語において、初期化時にのみ長さを決定できる狭義の可変長配列に相当するのは固定長配列である。

また、これらの言語では、配列のインスタンスを自動変数として持ったとしても、 必ずしもすべてのデータをスタック領域に持つわけではないので [注釈 19]、 パフォーマンスの観点からメモリの割り当てを制御するためには、 自動変数に動的割り当てとは異なる管理を期待するような間接的な方法は取らず、 C#のようにstackalloc演算子によって 明示的にスタック領域からメモリバッファを確保するなどの直接的な方法を取る [28]

次のC#のコード断片は、stackallocキーワードによって整数型の配列をスタック上に宣言する [注釈 20]。 stackallocによって割り当てたメモリ空間をポインタ型に変換することはC#では危険な操作と見做されるため、unsafeというキーワードによって当該のブロックを「安全でない」(unsafe) とマークしなければならない[注釈 21]。 

unsafe void declareStackBasedArray(int size)
{
    int *pArray = stackalloc int[size];
    pArray[0] = 123;
}


C#7.2以降はstackallocで確保したメモリ領域からSpan型 [30] への変換が可能となり、安全な操作の範囲内でstackallocを使えるようになった。 

void declareStackBasedArray(int size)
{
    Span<int> array = stackalloc int[size];
    array[0] = 123;
}

Javaの


これらの言語では、VLAをサポートするというよりも、 C#の例のようにスタック領域のメモリの利用形態の一つと

脚注

[編集]

参考文献

[編集]

注釈

[編集]
  1. ^ en|英語版ではALGOL 68からとしているが、 これはALGOL 68で追加された動的配列のFLEXのことと思われる。 ALGOL 68の文法定義 [3]には具体的な例が無いが、 ALGOL 68 with fewer tears[4]に例が記載されている。 狭義のVLAはALGOL 60の段階でサポートしている。 ALGOL 60の文法定義 [5]の5.2.4.2に"The expressions can only depend on variables and procedures which are nonlocal to the block for which the array declaration is valid. Consequently in the outer-most block of a program only array declarations with constant bounds may be declared."とあり、変数だけではなく関数の返り値を用いて初期化を行うことも可能であった。 ALGOL 58では文法定義 [6] E.2. "Array declarations"に"... are lists of integers separated by commas."としており、狭義の固定長配列のみのサポートする。
  2. ^ ただしC11ではサポート必須ではなくオプションに格下げとなった [7]。
  3. ^ C11規格書 附属書C 6.7.6.2 第4条参照。
  4. ^ 従来の配列をarr: Array[N] of Int;のように宣言したのに対し、 arr: array of Int;のように宣言した上で SetLength()メソッド[8]によって長さを指定する [9]。
  5. ^ スタック領域から動的に割り当てたメモリ領域へのポインタを返す関数。 malloc()関数に似たAPIだが、スタック領域へのポインタを返すため、free()関数で返却する必要は無く、固定長配列へのポインタと同様にスコープを抜けた段階で使用不能となる。 POSIX標準とはならなかったが、古くから様々なUnixシステムのCライブラリで提供されてきた。 SunOS 4.1.3での解説[12]、 Ultrix 4.2での解説[13]、 2.10 BSDでの解説[14]、 RedHat Linux 4.2での解説[15]、 FreeBSD 1.0での解説[16]、 Visual Studio 2015での解説[17] などを参照。
    malloc()関数と異なり、alloca()関数は割り当てに失敗してもNULLを返すとは限らない。GNU libcの実装はNULLを返すとするが、SunOS 4ではスタック領域を越えた場合の挙動は未定義としており、FreeBSDではスタック領域外のポインタを返すことがあると記す。
  6. ^ ISO C++規格自体にはVLAの語は見えず、 JIS C++規格（JIS X 3014:2003, ISO/IEC 14886:2003の和訳）にも 可変長配列の語は見えない。ただし、附属書Iの strstreambufクラスの解説（D.7.1）に 「動的な配列」や「動的配列」の語が見える。 これはdynamic arrayの訳語として用いられている。 附属書Iは参考情報であるため用語定義はされていないが、 動的配列オブジェクトを開放するためのプライベートメソッドを備えることから、 ここでいう動的配列は自動変数ではない。
  7. ^ 例えばcpprefjpのstd::vectorの解説 [18]ではstd::vectorクラスを「可変長配列」と記す。
  8. ^ 例えばcppreference日本語訳ページ[19]ではstd::vectorクラスを「動的なサイズの配列」と記す。
  9. ^ 可変長配列・動的配列を区別しないだけでなく、 std::listクラスのような連結リストまで可変長配列に含める解説文書もあるので注意が必要である。
  10. ^ 様々なプラットフォームでの実行を可能とするためC99やCOBOLなど、 多くの言語規格はメモリ管理方式について何も定めない。 Fortran 90の言語規格には参考解説の中でVLAを含む自動変数にはスタック領域が、 動的割り当てメモリにはヒープ領域が適しているとの文言が見えるが (ISO/IEC 1539:1991 C.13.1.4参照)、あくまでも解説であり規定の一部ではない。 スタックとヒープを明確に定義しているものとしては、 C++に対する技術報告書の ISO/IEC TR 18015があるが、これは規格ではなく技術報告書である。
  11. ^ この他に機械語を格納するコードセグメント（英語版）、データの初期値を格納するデータセグメント（英語版）、実行開始時点でメモリアドレスが定まっている変数に用いるBSSセグメントなどがある。
  12. ^ ヒープ領域から割り当てたメモリ領域は、 明示的に解放するかガベージコレクタが回収しない限り使用されつづけるので メモリリークの原因となり易い。 関数やブロックスコープに閉じた自動変数は 割り当てや解放が頻繁に起きるため、ガベージコレクタを前提とできない言語では、 解放処理が不要なスタック領域に自動変数をとったほうが管理が容易である。
    後述するJavaのように、より現代的なプログラミング言語ではインスタンスが スタック領域のデータとヒープ領域のデータの複合になっている場合もある。
  13. ^ C11規格書 §6.5.3.4 第2条参照。これに対して、malloc()関数の戻り値ポインタにはsizeof演算子を適用しても1個のポインタ変数が占めるバイト数しか得られない。
  14. ^ C11規格書 §7.20.3 第2条参照。
  15. ^ Windowsの既定値は1MB [21] Mac OS Xの既定値は8MB (iOSは1MB)[22]、 Linuxの既定値は2～32MB[23]である。
  16. ^ シグナルとシグナルハンドラはC言語規格に含まれている（C11規格書 §7.14.1 参照）。 ただし、signal関数によって明示的に送信したものとその受信は必須であるものの、 どのような条件でどのようなシグナルが発生するかはC言語規格の中では規定されず、 セグメント破壊が生じても何のシグナルも発生しない実装もあり得る。
  17. ^ C99規格書 §6.7.5.2 第10条の例を参照。 
    void func(int* vals, size_t n) { ... }

    や 

    void func(size_t n, int vals[n]) { ... }

    のような引数の順序は許されるが、 

    void func(int vals[n], size_t n) { ... }

    のような引数の順序は許されない。 これは、 

    void func(void)
{
    int vals[n];
    size_t n = 10;
}

    が許されないことと同様である。

  18. ^ C++やObjective-CなどのC言語を拡張して作られたオブジェクト指向言語の場合、 クラスとしての配列はライブラリが提供するもので、 最も基本的なC言語由来の文法で配列データを構築した場合には コンストラクタは実行されない。 これに対し、JavaやC#ではnew()演算子を用いずに ソースコードに即値として記述した配列であっても コンストラクタが実行される。
  19. ^ Java言語仕様 [25] はヒープとスタックの使い分けを定めないが、 Java VM仕様の 2.5.2 Java Virtual Machine Stacks [26] 、2.5.3 Heap [27] に言及があり、「The heap is the run-time data area from which memory for all class instances and arrays is allocated.」と書かれており、 JavaのArrayクラスは初期化後に長さを変更できないが、ヒープ領域にデータを持つことになる。
  20. ^ C#の通常の配列も 
    void declareNormalArray(int size)
{
    int[] array = new int[size];
    ...
}

    のように実行時に評価される長さを使って宣言できる。 C#の通常の配列は宣言後にArray.Resize()メソッド [29]を使って長さを変更できる動的配列である。 C#ではポインタ型、Span型と配列型は異なるため、 stackallocで割り当てたメモリ領域に対してArray.Resize()メソッドは適用できない。

  21. ^ C#のコンパイラは既定ではunsafeとマークされたコードのコンパイルを中止するため、コンパイルオプションに "/unsafe" （Monoのコンパイラであるmcsの場合は"-unsafe"）を追加する必要がある。

出典

[編集]
  1. ^ “Variable Length Arrays”. 2017年9月21日閲覧。
  2. ^ コンパイル段階で定数となる式で長さを指定した場合、狭義の固定長配列として動作する言語が一般的である
  3. ^ Adriaan van Wijngaarden, Barry James Mailloux, John Edward Lancelot Peck, Cornelis Hermanus Antonius Koster, Michel Sintzoff, Charles Hodgson Lindsey, Lambert Guillaume Louis Théodore Meertens. “Revised Report on the Algorithmic Language ALGOL 68”. 2024年2月27日閲覧。
  4. ^ Template:Cite webの呼び出しエラー：引数 title は必須です。C. H. Lindsey. “{{{title}}}”. 2024年2月27日閲覧。
  5. ^ Template:Cite webの呼び出しエラー：引数 url は必須です。J. W. Backus, F. L. Bauer, J. Green, C. Katz, J. McCarthy, A. J. Perlis, H.Rutishauser, K. Samelson, B. Vauquois, J. H. Wegstein, A. van Wijngaardern, N. Woodger. “[{{{url}}} Revised report on the algorithmic language ALGOL 60]”. 2024年2月27日閲覧。
  6. ^ A.J.Perlis, K. Samelson. “Preliminary Report - International Algebraic Language”. 2024年2月27日閲覧。
  7. ^ “Variable Length - Using the GNU Compiler Collection (GCC)”. 2017年9月21日閲覧。
  8. ^ “System.SetLength”. 2024年2月25日閲覧。
  9. ^ “Structured Types (Delphi): Dynamic Arrays”. 2024年2月25日閲覧。
  10. ^ Rust By Example 日本語版 “配列とスライス”. 2024年2月25日閲覧。
  11. ^ Rust By Example 日本語版 “ベクタ型”. 2024年2月25日閲覧。
  12. ^ “man alloca (SunOS 4.1.3)}”. 2024年2月22日閲覧。
  13. ^ “man alloca (Ultrix 4.2)”. 2024年2月22日閲覧。
  14. ^ “man alloca (2.10 BSD)”. 2024年2月22日閲覧。
  15. ^ “man alloca (RedHat Linux 4.2)”. 2024年2月22日閲覧。
  16. ^ “man alloca (FreeBSD 1.0)”. 2024年2月22日閲覧。
  17. ^ “_alloca (Visual Studio 2015マニュアル)”. 2024年2月22日閲覧。
  18. ^ “cpprefjp std::vector”. 2024年2月22日閲覧。
  19. ^ “cppreference.com std::vector”. 2024年2月23日閲覧。
  20. ^ “Code Gen Options - The GNU Fortran Compiler”. 2017年9月21日閲覧。
  21. ^ “/STACK (スタック割り当て)”. 2024年2月23日閲覧。、
  22. ^ “Threading Programming Guide: Threading Cost”. 2024年2月23日閲覧。
  23. ^ “man pthread_create”. 2024年2月23日閲覧。
  24. ^ “sizeof Operator”. 2017年9月21日閲覧。
  25. ^ “The Java® Language Specification (Java SE 21 Edition)”. 2024年2月23日閲覧。
  26. ^ “The Java® Virtual Machine Specification (Java SE 21 Edition): Java Virtual Machine Stacks”. 2024年2月23日閲覧。
  27. ^ “The Java® Virtual Machine Specification (Java SE 21 Edition): Heap”. 2024年2月23日閲覧。
  28. ^ alloca()関数とmalloc()関数の使い分けのような状態とも言える。 C#におけるstackallocは巨大なバッファの確保に対しては StackOverflowExceptionを発生させることになっている。 レファレンスマニュアル “stackalloc 式 (C# リファレンス)”. 2024年2月25日閲覧。 では手動で設定した固定値で stackalloc演算子を使うかnew演算子を使うかを分ける例を示す。
  29. ^ “Array.Resize<T>(T[, Int32) メソッド]”. 2024年2月24日閲覧。
  30. ^ “System.Span<T> 構造体”. 2024年2月24日閲覧。


「https://ja-two.iwiki.icu/w/index.php?title=利用者:Mpsuzuki/sandbox5&oldid=99423650」から取得