第4章アルゴリズムの言語による実現：低水準プログラミング言語

Linking Programsプログラムのリンク

Figure 4.18 illustrates the processing steps of C programs from source code to execution.

図4.18は、Cプログラムのソースコードから実行までの処理手順を示す。

Figure 4.18 The linking process that is used by languages to make them portable requires a number of different steps. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図4.18 言語の移植性を実現するために使うリンク処理には、いくつもの異なる段階が必要である。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）

Linking refers to the process of collecting and combining various pieces of object code into a single program file that can be loaded into memory and executed. A linker is a program that performs linking. Understanding linkers will help you build large programs, avoid dangerous programming errors, understand how language scoping rules are implemented, understand other important systems concepts (such as virtual memory and paging), and use shared libraries (a file that is to be shared by an executable file). Virtual memory is an operating system concept where the secondary memory acts as main memory to compensate for memory shortage. Paging is a technique where the secondary memory is used to store and retrieve the data into the main memory. The memory is divided into small regions called pages which enables for the quick access of the data. If a page is found, it is called a “Page hit;” otherwise, it is a “Page miss.”

英語のヒント

リンク処理とは、さまざまなオブジェクトコードを集めて結合し、メモリへ読み込んで実行できる1つのプログラムファイルにする過程である。リンカーは、このリンク処理を行うプログラムである。リンカーを理解すると、大規模なプログラムの構築、危険なプログラミングエラーの回避、言語のスコープ規則の実装の理解、仮想メモリやページングなどの重要なシステム概念の理解、共有ライブラリー（実行可能ファイルが共有するファイル）の利用に役立つ。仮想メモリは、メモリ不足を補うために補助記憶が主記憶として働く、オペレーティングシステムの概念である。ページングは、補助記憶を使ってデータを保存し、主記憶へ取り出す技術である。メモリはページと呼ぶ小さな領域に分割され、それによってデータへ素早くアクセスできる。ページが見つかれば「ページヒット」、見つからなければ「ページミス」と呼ぶ。

Programs are translated and linked using a compiler driver, a program that invokes other components that helps in translating the high-level program to a machine code, as in Figure 4.19 and using the following code:

英語のヒント

プログラムの変換とリンクには、コンパイラードライバーを使う。これは、高水準プログラムを機械語コードへ変換するのを助ける、ほかの構成要素を呼び出すプログラムである。図4.19と、次のコードに示す。

linux> gcc -Og -o prog main.c sum.c
linux> ./prog

Figure 4.19 Source files and separately compiled relocatable object files can be linked into an executable object file. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図4.19 ソースファイルと、別々にコンパイルされた再配置可能なオブジェクトファイルは、実行可能なオブジェクトファイルへリンクできる。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）

Linkers are used to ensure:

リンカーは、次の性質を確保するために使う。

• Modularity: Program can be written as a collection of smaller source files, rather than one monolithic mass. Using a linker facilitates building libraries of common functions (e.g., Math library, standard C library). A library is a file that contains object code (a code from the object file that is generated after compilation) for functions and global variables (variables that have global scope and can be used anywhere in the program) that are intended to be reused.

英語のヒント

• モジュール性：プログラムを1つの巨大な塊としてではなく、小さなソースファイルの集まりとして書ける。リンカーを使うと、共通の関数を集めたライブラリー（数学ライブラリー、Cの標準ライブラリーなど）を作りやすい。ライブラリーは、再利用することを意図した関数やグローバル変数のオブジェクトコードを含むファイルである。オブジェクトコードは、コンパイル後に生成されるオブジェクトファイル内のコードをいう。グローバル変数は、グローバルなスコープを持ち、プログラム内のどこでも使える変数である。

• Efficiency: It saves time to run separate compilations and change one source file, compile, and then relink since there is no need to recompile other source files. Also, libraries save memory space because common functions can be aggregated into a single file and yet executable files (the end product after compiling and linking) and running memory images (current memory) contain only code for the functions they actually use.

英語のヒント

• 効率：ソースファイルごとにコンパイルしておけば、1つのソースファイルを変更し、それをコンパイルしてから再リンクすることで時間を節約できる。ほかのソースファイルを再コンパイルする必要がないからである。また、共通の関数を1つのファイルにまとめられる一方で、実行可能ファイル（コンパイルとリンク後の最終成果物）と実行中のメモリイメージ（現在のメモリ）には、実際に使う関数のコードだけが含まれるため、ライブラリーはメモリ領域の節約にもなる。

Linking Stepsリンクの手順

Programs define and reference symbol. A symbol is an identifier for a function or a global variable. The first linking step performs symbol resolution. During the symbol resolution step, the linker associates each symbol reference with exactly one symbol definition (Figure 4.20).

英語のヒント

プログラムはシンボルを定義し、参照する。シンボルは、関数やグローバル変数を表す識別子である。リンクの第1段階では、シンボル解決を行う。この段階で、リンカーは各シンボル参照を、ちょうど1つのシンボル定義に対応付ける（図4.20）。

Figure 4.20 In the process of compilation and linking in C++, “.hpp” are the header files, “.cpp” are the actual C++ programs, “.o” are the object files, and “.exe” is the executable. (credit: modification of “C++ compilation process” by “Prog”/Wikimedia Commons, CC0 1.0)

図4.20 C++のコンパイルとリンクでは、「.hpp」はヘッダーファイル、「.cpp」は実際のC++プログラム、「.o」はオブジェクトファイル、「.exe」は実行可能ファイルである。（クレジット：「Prog」／Wikimedia Commonsによる「C++ compilation process」を改変、CC0 1.0）

Symbol definitions are stored in an object file (by the assembler) called a symbol table. A symbol table is an array of structures in which each entry includes name, size, and location of symbol.

英語のヒント

シンボル定義は、アセンブラーによって、シンボル表と呼ばれるオブジェクトファイルに格納される。シンボル表は構造体の配列であり、各項目にはシンボルの名前、大きさ、場所が含まれる。

The second linking step performs code relocation (Figure 4.21). This step merges separate code and data sections into single sections (one for code and one for data). It relocates symbols from their relative locations in the .o files (the object files) to their final absolute memory locations in the executable. It updates all references to these symbols to reflect their new positions.

英語のヒント

リンクの第2段階では、コードの再配置を行う（図4.21）。この段階では、別々のコードセクションとデータセクションを、コード用とデータ用のそれぞれ1つのセクションへ統合する。.oファイル（オブジェクトファイル）内の相対位置にあるシンボルを、実行可能ファイル内の最終的な絶対メモリ位置へ移す。そして、これらのシンボルへの参照をすべて更新し、新しい位置を反映させる。

Figure 4.21 This diagram shows the input types in an array and the index locations. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図4.21 この図は、配列内の入力の型と、添字の位置を示している。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）

Executable and Linkable Module Format実行可能・リンク可能なモジュールの形式

There are three kinds of object files (modules) that relate to the linking process (Figure 4.22):

リンク処理に関係するオブジェクトファイル（モジュール）には、3種類ある（図4.22）。

• Relocatable Object File (.o file): Contains code and data in a form that can be combined with other relocatable object files to form executable object file. Each .o file is produced from exactly one source (.c) file.

英語のヒント

• 再配置可能オブジェクトファイル（.oファイル）：ほかの再配置可能オブジェクトファイルと結合して実行可能オブジェクトファイルを作れる形式で、コードとデータを含む。各.oファイルは、ちょうど1つのソース（.c）ファイルから作られる。

• Executable Object File (a.out file): Contains code and data in a form that can be copied directly into memory and then executed.

• 実行可能オブジェクトファイル（a.outファイル）：メモリへ直接コピーし、その後実行できる形式で、コードとデータを含む。

• Shared Object File (.so file): Special type of relocatable object file that can be loaded into memory and linked dynamically, at either load time or runtime. These object files are called Dynamic Link Libraries (DLLs) on Windows.

英語のヒント

• 共有オブジェクトファイル（.soファイル）：再配置可能オブジェクトファイルの特殊な種類で、ロード時または実行時に、メモリへ読み込んで動的にリンクできる。Windowsでは、これらのオブジェクトファイルをダイナミックリンクライブラリー（DLL）と呼ぶ。

Figure 4.22 The subcategories of Executable and Linkable modules are arranged in a hierarchy. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)

図4.22 実行可能・リンク可能なモジュールの下位分類を、階層として配置している。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）

All three object files follow the executable and linkable format (ELF) which is a standard binary format for object files originally proposed by AT&T System V Unix, and later adopted by BSD Unix variants and Linux. Unix is an operating system that has been used widely, primarily in servers and software development since the 1970s, and Linux is Unix-compatible.

英語のヒント

3種類のオブジェクトファイルはすべて、Executable and Linkable Format（ELF）に従う。これは、もともとAT&T System V Unixが提案し、後にBSD Unixの派生版やLinuxが採用した、オブジェクトファイルの標準バイナリー形式である。Unixは、1970年代以来、主にサーバーやソフトウェア開発で広く使われてきたオペレーティングシステムであり、LinuxはUnixと互換性がある。