プリンキピア

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

4.1 Models of Computation4.1　計算モデル

Learning Objectives学習目標
By the end of this section, you will be able to:
この節を終えると、次のことができるようになる。
• Define low-level programming languages, including assembly language
・アセンブリ言語を含む、低水準プログラミング言語を定義する。
• Define middle-level and high-level programming languages, such as C and JavaScript
・CやJavaScriptなどの、中水準・高水準プログラミング言語を定義する。
• Compare and contrast the various programming paradigms
・さまざまなプログラミングパラダイムを比較し、共通点と相違点を示す。
Algorithms are used to solve computational problems and create computational models. A computational model is a system that defines what an algorithm does and how to run it. Examples of such computational models include physical devices that can run software, programming languages, or a design specification of such. A programming language is a linguistic application of an algorithm, which uses computational models focused on defining notations for writing code.
英語のヒント
アルゴリズムは、計算上の問題を解き、計算モデルを作るために使われる。計算モデルは、アルゴリズムが何をし、どう実行するかを定めるシステムである。たとえば、ソフトウェアを実行できる物理的な装置、プログラミング言語、それらの設計仕様などが含まれる。プログラミング言語は、コードを書くための記法の定義を中心とする計算モデルを使う、アルゴリズムの言語的な応用である。
Many computational models have been devised for a host of other applications. There are many different roles and perspectives within the worlds of computer science and software development. The end goal of software development is to create working software that can run on a hardware model, which itself uses a (hardware) realization of an algorithm that enables specific physical computers to execute software programs. A hardware model is designed for the convenience of a machine, not a human software author, so hardware models are poorly suited to writing code. Computer scientists have created programming languages which are designed specifically for programmers to develop practical applications. These languages are usually classified into high-level (Java, Python) and low-level languages (assembly language). A high-level programming language operates at a high level of abstraction, meaning that low-level details such as the management of memory are automated. In contrast, a low-level programming language operates at a low level of abstraction. Languages like C and C++ can perform both high-level and low-level tasks.
英語のヒント
ほかにも数多くの用途に向けて、多くの計算モデルが考案されている。コンピューターサイエンスやソフトウェア開発の世界には、さまざまな役割や視点がある。ソフトウェア開発の最終目標は、ハードウェアモデル上で実行できる、動くソフトウェアを作ることである。そのハードウェアモデル自体は、特定の物理的コンピューターにソフトウェアを実行させるアルゴリズムを、ハードウェアで実現したものを利用する。ハードウェアモデルは、人間のソフトウェアの書き手ではなく、機械の都合に合わせて設計されるため、コードを書くのには向かない。コンピューター科学者は、プログラマーが実用的なアプリケーションを開発できるよう、専用のプログラミング言語を作ってきた。これらは通常、高水準言語（Java、Python）と低水準言語（アセンブリ言語）に分類される。高水準プログラミング言語は、抽象化の水準が高く、メモリ管理などの低水準の詳細が自動化される。これに対し、低水準プログラミング言語の抽象化の水準は低い。CやC++のような言語は、高水準と低水準の両方の仕事を実行できる。
Most software is designed, written, and discussed in terms of how a program should work. It is basically a series of steps that provide a direction of how the program must be executed. An example of this would be the “Map Reduce model” which is used in distributed systems like the Google search engine to produce search results for large data sets using a complex algorithm. Moving even further away from hardware models, computer scientists have also defined an abstract model, which is a technique that derives simpler high-level conceptual models for a computer while exploring the science of what new algorithms can or cannot do.
英語のヒント
ソフトウェアの大半は、プログラムがどう動くべきかという観点で設計され、書かれ、議論される。基本的には、実行方法を指示する一連の手順である。一例が「Map Reduceモデル」であり、Googleの検索エンジンのような分散システムで、複雑なアルゴリズムを使って大規模データセットの検索結果を生成するために利用される。コンピューター科学者は、ハードウェアモデルからさらに離れ、抽象モデルも定義している。これは、新しいアルゴリズムで何ができ、何ができないかを科学的に探りながら、コンピューターの、より単純で高水準な概念モデルを導く手法である。
Modern computers are equipped with a central processor, referred to as a central processing unit (CPU), which is a computer chip capable of executing programs. A CPU’s hardware model relies on a specific CPU instruction set architecture (ISA) that defines a list of operations that the CPU can execute, such as storing the results of calculations (Figure 4.2). With the advancements of technology, computer engineers have designed computer architectures with increasing sophistication and power. Examples of hardware models include the MOS Technology 6502 architecture used by the Nintendo Entertainment System, the ARM architecture used by mobile phones, and the x86-64 and AMD64 architectures used by modern personal computers. Computer engineers design architectures with hardware specifications, such as execution speed or energy use, in mind. Therefore, hardware models are not suitable for humans to use for communicating algorithms.
英語のヒント
現代のコンピューターは、中央処理装置（CPU）と呼ばれる中央プロセッサーを備える。これはプログラムを実行できるコンピューターチップである。CPUのハードウェアモデルは、特定の命令セットアーキテクチャー（ISA）に基づく。ISAは、計算結果の保存など、CPUが実行できる操作の一覧を定める（図4.2）。技術の進歩とともに、コンピューター技術者は、より高度で強力なアーキテクチャーを設計してきた。例として、Nintendo Entertainment Systemで使われるMOS Technology 6502、携帯電話で使われるARM、現代のパーソナルコンピューターで使われるx86-64やAMD64などがある。技術者は、実行速度やエネルギー使用など、ハードウェアの仕様を念頭に設計する。そのため、ハードウェアモデルは、人間がアルゴリズムを伝えるために使うのには適さない。
Figure 4.2

attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license · CC BY 4.0 · Source出典

Figure 4.2 A standard CPU model shows how a program logic applies low-level instructions to an input to get an output; the program leverages registers and memory (black arrows) and the CPU orchestrates the overall execution of the program (red arrows). (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)
図4.2 標準的なCPUのモデルは、プログラムの論理が入力に低水準の命令を適用して、出力を得る仕組みを示す。プログラムはレジスターとメモリを利用し（黒い矢印）、CPUは実行全体を統括する（赤い矢印）。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）
A programming model is designed for humans to read and write. A programming model focused on defining a notation for writing code can also be called a programming language. A programming model can be used to implement a software algorithm using a strict set of syntactical rules. A language’s syntax can define keywords such as “if.” The syntax may include a mathematical operator, a fundamental programming operation that combines values, such as “+.” The syntax can define punctuation such as “;”. Essentially, the syntax gives the precise meaning for what each of these elements directs a computer to do. The text of a program written in a programming language is called source code. Software engineers have created practically all software by writing source code in various programming languages. Since a programming model cannot directly execute a program, a compiler or interpreter must translate source code from a middle-level or high-level language into something a computer can execute.
英語のヒント
プログラミングモデルは、人間が読み書きするために設計される。コードを書くための記法の定義に重点を置くプログラミングモデルは、プログラミング言語とも呼べる。厳密な構文規則によって、ソフトウェアのアルゴリズムを実装するために利用できる。言語の構文は「if」などのキーワードを定める。また「+」のように、値を組み合わせる基本的なプログラミング操作である数学演算子を含むことがある。「;」などの区切り記号も定められる。要するに構文は、これらの各要素がコンピューターに何をさせるか、正確な意味を与える。プログラミング言語で書かれたプログラムのテキストは、ソースコードと呼ばれる。ソフトウェア技術者は、さまざまな言語でソースコードを書くことによって、事実上すべてのソフトウェアを作ってきた。プログラミングモデルはプログラムを直接実行できないため、コンパイラーまたはインタープリターが、中水準・高水準言語のソースコードを、コンピューターが実行できる形へ変換しなければならない。
As mentioned, abstract models are computational models used to think about algorithms in the abstract, rather than being used to create and run software. The goal of an abstract model is to make it easy for people to devise and convey algorithms. Computer scientists use abstract models to create new algorithms, analyze the efficiency of algorithms, and prove facts about what algorithms can and cannot do. An abstract model is not concerned with the details of computer architectures, which makes it easier to focus on these sorts of deep questions. Examples of abstract models include the Random Access Machine, the Turing machine, and the Lambda calculus. The Random Access Machine (Figure 4.3) is a CPU that consists of unlimited memory cells that can store any arbitrary value. Just like any other CPU, the PC determines the statement to be executed next. A Random Access Machine can be used to analyze the efficiency of algorithms. A Turing machine (Figure 4.4) is a mathematical model that can implement any algorithm. The Lambda calculus is a theoretical computation concept using lambda functions. It was defined by Alonzo Church and inspired the functional programming paradigm, which you will learn more about in Programming Language Paradigms.
英語のヒント
前述のとおり、抽象モデルは、ソフトウェアを作って実行するためではなく、アルゴリズムを抽象的に考えるための計算モデルである。目標は、人がアルゴリズムを考案し、伝えやすくすることである。コンピューター科学者は、新しいアルゴリズムの作成、効率の解析、何ができ何ができないかという事実の証明に、抽象モデルを使う。コンピューターのアーキテクチャーの詳細を扱わないため、こうした深い問いに集中しやすい。抽象モデルには、ランダムアクセスマシン、チューリングマシン、ラムダ計算などがある。ランダムアクセスマシン（図4.3）は、任意の値を保存できる無制限のメモリセルを備えたCPUである。ほかのCPUと同じように、次に実行する文はPCが決める。アルゴリズムの効率の分析に利用できる。チューリングマシン（図4.4）は、どのアルゴリズムも実装できる数学モデルである。ラムダ計算は、ラムダ関数を使う理論的な計算の概念である。アロンゾ・チャーチが定義し、関数型プログラミングのパラダイムに着想を与えた。これについては「プログラミング言語のパラダイム」でさらに学ぶ。
Figure 4.3

attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license · CC BY 4.0 · Source出典

Figure 4.3 A Random Access Machine has unlimited memory cells that can store any arbitrary value. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)
図4.3 ランダムアクセスマシンは、任意の値を保存できる、無制限のメモリセルを備える。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）
Figure 4.4

attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license · CC BY 4.0 · Source出典

Figure 4.4 A neural Turing machine (NTM) leverages the pattern matching capabilities of neural networks in addition to more traditional computational models. It use a controller that interacts with external memory resources through attention mechanisms that mimic human attention to improve performance. (attribution: Copyright Rice University, OpenStax, under CC BY 4.0 license)
図4.4 ニューラルチューリングマシン（NTM）は、従来の計算モデルに加え、ニューラルネットワークのパターン照合能力を活用する。人間の注意を模したアテンション機構を通じて外部のメモリ資源とやり取りする制御器を使い、性能を向上させる。（出典表記：著作権者 Rice University、OpenStax、CC BY 4.0ライセンス）
A function defines how to convert an input into an output, and functional programming is a paradigm in which algorithms are written as mathematical functions. An example of a functional programming paradigm is a recursion (refer to the following code snippet), where a function is used to call itself. The factorial of an integer can be computed using a recursive function.
英語のヒント
関数は、入力を出力に変換する方法を定める。関数型プログラミングは、アルゴリズムを数学的な関数として書くパラダイムである。一例が、関数を使ってその関数自身を呼び出す再帰である（次のコードの抜粋を参照）。整数の階乗は、再帰関数で計算できる。
import java.util.*;
public class Recursion {
  public static int Factorial_Recursion(int Val){
    if(Val==0){
      return 1;
    }
    else
      return Val*Factorial_Recursion(Val-1);
  }
  public static void main(String[] args){
    Scanner s =new Scanner(System.in);
    System.out.println("Enter an input value: ");
    int Val=s.nextInt();
    System.out.println("The factorial of " + Val + " is: " +
Factorial_Recursion(Val));
  }
}
An algorithm described in an abstract model cannot be run directly. First, a software developer must implement the algorithm, which means translating the abstract algorithm into source code in a programming language.
英語のヒント
抽象モデルで記述されたアルゴリズムは、そのままでは実行できない。まず、ソフトウェア開発者が実装しなければならない。つまり、抽象的なアルゴリズムを、プログラミング言語のソースコードへ変換する必要がある。
It may be surprising that so many different programming models can exist, and that algorithms can be translated from one model to another. However, this translation is by design; computer science established the Church-Turing Thesis, which is a scientific theory stating that an algorithm can be converted from any reasonable computational model to another. The Church-Turing Thesis provides a lens through which computer scientists can invent many computer architectures and programming languages, all of which can run algorithms.
英語のヒント
これほど多くの異なるプログラミングモデルが存在でき、アルゴリズムをモデル間で変換できることは、意外に思えるかもしれない。しかし、この変換は意図されたものである。コンピューターサイエンスは、どの妥当な計算モデルから別のモデルへもアルゴリズムを変換できるとする科学的な理論、チャーチ＝チューリングのテーゼを確立した。このテーゼは、コンピューター科学者が、どれもアルゴリズムを実行できる、多くのアーキテクチャーやプログラミング言語を生み出すための見方を与える。
Computer scientists have created terminology to make sense of the similarities and differences among all these programming languages. For example, any programming language can be low level or high level, or it can fall anywhere on the spectrum.
英語のヒント
コンピューター科学者は、これらすべての言語の共通点と相違点を理解するため、用語を作ってきた。たとえば、プログラミング言語は低水準、高水準のいずれにもなり得るし、その間の連続的な範囲のどこに位置することもできる。