高校「情報Ⅰ」単語帳 - 第一学習社「高等学校 情報Ⅰ」 - アルゴリズムとプログラミング

コンピュータプログラム (computer program)

コンピュータが行うべき処理を順序立てて記述したもの。広義の「ソフトウェア」の一部であるが、実用上はプログラムとソフトウェアはほとんど同義のように扱われることが多い。

現代のコンピュータではプログラムは一定の形式に従ってデータとして表現され、記憶装置(メインメモリ)に格納される。実行時にはCPU(中央処理装置)がプログラムに記述された命令を順番に読み出して解釈・実行していく。

プログラムを作成する作業や工程を「プログラミング」(programming)、これを行う人や職種のことを「プログラマ」(programmer)という。人間がプログラムを記述する際には、人間が理解しやすい人工言語である「プログラミング言語」(programming language)を使うことが多い。プログラミング言語で記述されたプログラムを「ソースコード」(source code)という。

ソースコードはコンピュータが解釈・実行することができないため、コンパイラなどの変換ソフトによってコンピュータが解釈・実行できる機械語(マシン語)などで構成された「オブジェクトコード」(object code)に変換されてから実行される。スクリプト言語のように、この変換処理を開発時には行わず、実行時にインタプリタなどのソフトウェアによって動的に行う場合もある。

ITの分野では、コンピュータプログラムの設計やアルゴリズム(計算手順)の理解などのために、内部で行われる処理や演算の詳細な流れをフローチャートに表すことが多い。プログラムに限らず、業務手順など様々な過程や手順の図示に応用できる。

一つのフローチャートには開始と終了があり、その間に一つ以上の工程が含まれる。流れは分岐や繰り返しによって複数に枝分かれしたり戻ったりすることがあるが、途中どのような経路を通っても必ず一つの開始から始まって一つの終了で終わる。

フローチャートで用いる部品の種類や図記号の形状はJIS X 0121で規格化されており、一般的にはこれを用いることが多い。主な部品として、開始や終了を表す「端子」(円・楕円・角丸長方形)、「処理」(長方形)、プログラムにおけるサブルーチンや関数などの「定義済み処理」(左右が二重線の長方形)、「入出力」(平行四辺形)、条件分岐などの「判断」(菱形)、繰り返しの範囲を示す「ループ端」(開始は上側、終了は下側の角が欠けた長方形)、他の図との出入り口を示す「結合子」(小さな丸)、処理の流れを示す「線」(右や下へは線分・左や上には矢印)などがある。

プログラミング言語でプログラムを開発することを「プログラミング」(programming)、プログラミング言語で記述したプログラムを「ソースコード」(source code)という。語彙、文法、記法などが自然言語よりも厳密に定義されており、記述したソースコードはソフトウェアによって自動的に解析、処理、変換などすることができる。

コンパイラとインタプリタ

プログラミング言語は人間にとって理解、記述しやすい語彙や文法で構成された言語であり、そのままではコンピュータ(のCPU)が解釈、実行することができないため、ソフトウェアによってCPUが実行可能な言語(機械語、マシン語)によるプログラムに変換して実行される。

開発時や導入時などに一度にまとめて変換処理を行うことを「コンパイル」(compile)、そのような変換ソフトを「コンパイラ」(compiler)という。実行時に変換と実行を同時並行で行うソフトウェアを「インタプリタ」(interpreter)という。

高水準言語と低水準言語

プログラミング言語は人間にとっての理解のしやすさや機械語に対する抽象度の高さによって分類されることがあり、機械寄りの言語を「低水準言語」(low-level language)あるいは「低級言語」と呼び、人間寄りの言語を「高水準言語」(high-level language)あるいは「高級言語」という。

機械語の命令コードと一対一に対応する命令語を用いてプログラミング言語を行う低水準言語のことを特に「アセンブリ言語」(assembly language)と呼び、機械語への変換ソフトを「アセンブラ」(assembler)という。

プログラミングパラダイム

プログラムをどのようなものとして捉え、構築していくかについて一定の設計思想やルールがある場合が多く、これを「プログラミングパラダイム」(programming paradigm)という。複数の書き方が可能な言語は「マルチパラダイム」であるという。パラダイムに基いて言語を分類することもある。

手続きを順番に記述していく「手続き型言語」(procedural language)あるいは「命令型言語」(imperative language)や、関連するデータ群と手続き群を一つのまとまりとして捉える「オブジェクト指向言語」(object-oriented language)、プログラムを関数の組み合わせとして捉える「関数型言語」(functional language)、データ間の関係や論理を記述していく「論理型言語」(logic programming language)などの種類がある。

また、主な利用目的や主要な処理系の実装方式により分類することもあり、記述や実行の手間を軽減して迅速にプログラム開発ができる「スクリプト言語」(script language)あるいは「軽量言語」(LL：Lightweight Language)、特定の分野や処理に特化した「ドメイン固有言語」(DSL：Domain Specific Language)などの分類がある。

基本的な特徴としては、豊富なデータ型とコンテナ型、ガベージコレクション、Unicodeによる多言語対応、プログラムのモジュール(部品)化による他のプログラムへの容易な組み込み、プログラムの仕様の文書化(ドキュメンテーション)を支援する機能などがある。

ユニークな特徴としては、多くの言語では人間にとってプログラムを読みやすくするために便宜的に行われるインデント(字下げ)を言語仕様上の構文の一つとして採用しており、ブロックの範囲を示すのに用いられる。

言語自体の文法や語彙、記法な最小限のシンプルなものに抑えられているが、対照的に、極めて広範囲の分野に渡り豊富な機能を提供する標準ライブラリが用意されている。当初は手続き型言語とオブジェクト指向言語の特徴を備えた言語として設計されたが、関数型言語の要素の多くを取り入れ、様々なスタイルのプログラミングが可能なマルチパラダイム言語として知られている。

他の言語や環境との連携機能も充実しており、Pythonからアクセスできない低レベルの機能をC言語で記述して拡張モジュールとして組み入れる仕組みが提供されているほか、Javaライブラリを利用できる実行環境の「Jython」や、Microsoft .NET環境で.NET Frameworkの機能を利用できる「IronPython」などの処理系もある。

標準の言語処理系(CPython)にはソースコードを読み込みながら同時に実行するインタプリタが含まれ、コンパイルやビルドなど手間や時間のかかる作業を省略して記述したプログラムを即座に実行してみることができる。この処理系はオープンソースソフトウェアとして公開されており、誰でも自由に入手、利用、改変、再配布などすることができる。

Pythonの最初のバージョンは1991年にオランダのグイド・ヴァン・ロッサム(Guido van Rossum)氏によって発表された。現在ではWebアプリケーションの開発用言語として人気が高いほか、データ処理や統計解析などの分野でよく利用されることで知られる。

特定の領域や対象に関連する処理や定義の記述に特化した語彙や仕様を持つ言語のことを指し、C言語やXMLのように特定の用途や目的を持たない汎用のプログラミング言語やマークアップ言語などと対比される。

ただし、このような機能があればDSLであるとか、このような水準に達していれば汎用言語であるといったような厳密な基準や定義はなく、Webページの動的な生成に特化したDSLとして産まれながら、次第に機能が拡張され汎用的になっていったPHPのような例もある。

DSLには対象や領域ごとに様々な言語がある。各分野で特に著名な例としては、Webページ記述のためのHTML、スタイル記述言語のCSS、組版言語のTeX/LaTeX、ページ記述言語のPostScript、データベースへの問い合わせ言語SQL、電子回路設計のためのハードウェア記述言語(HDL)であるVerilogやVHDL、文字列のパターンを表現する正規表現、文脈自由文法を定義するBN記法(BNF)などがある。

元になる汎用の言語(ホスト言語)が存在し、その語彙や構文を借りながら、複雑な機能を制限、省略するなどして定義されたものを「組み込みDSL」(embedded DSL)あるいは「内部DSL」(internal DSL)と呼び、既存の言語とは無関係に独立に定義されたものを「外部DSL」(external DSL)という。

テキスト形式は文字のみで構成されるデータで、画像など他の形式のデータや、コンピュータ向けの制御データ、文字の大きさや色などの修飾情報などは含まない。テキストエディタは文字の編集に特化したソフトウェアであり、こうした文字以外の情報を扱うことはできない。

現代では一般的な文書作成はレイアウトや見た目の修飾ができるワープロソフトなどを使うことが一般的なため、テキストエディタは主にソフトウェアの設定ファイルやコンピュータプログラムのソースコード、マークアップ言語による文書ファイルなどの作成・編集に用いられる。プログラムの編集に特化したものは特にコードエディタと呼ばれることもある。

製品によっては、行番号の表示や折返し桁数の設定、正規表現による複雑な条件を用いた検索や置換、操作の取り消し(アンドゥ)、編集作業の記録・再生や自動化(マクロやスクリプト)、特定の記号やキーワードの色分け表示(シンタックスハイライト)など文字データの編集を支援する便利な機能が利用できる。

Windowsの「メモ帳」やmacOSの「テキストエディット」のように多くのOSには付属のテキストエディタが存在するが、フリーソフトウェアやオープンソースソフトウェアとして配布されているエディタや、企業などが製品として開発・販売しているものも数多く存在する。UNIX環境では伝統的にvi/VimやEmacsが標準的に使われている。

個々のソフトウェアの開発者が毎回すべての機能をゼロから開発するのは困難で無駄なため、多くのソフトウェアが共通して利用する機能は、OSやミドルウェアなどの形でまとめて提供されている。

そのような汎用的な機能を呼び出して利用するための手続きを定めたものがAPIで、個々の開発者はAPIに従って機能を呼び出す短いコードを記述するだけで、自分で一から処理内容を記述しなくてもその機能を利用したソフトウェアを作成することができる。

広義には、プログラミング言語の提供する機能や言語処理系に付属する標準ライブラリの持つ機能を呼び出すための規約などを含む場合もある(Java APIなど)。

また、APIを経由して機能を呼び出す形でプログラムを構成することにより、同じAPIが実装されていれば別のソフトウェア上でそのまま動作させることができるのも大きな利点である。実際、多くのOS製品などでは同じ製品の旧版で提供していたAPIを引き継いで新しいAPIを追加するという形で機能を拡張しており、旧バージョン向けに開発されたソフトウェアをそのまま動作させることができる。

APIの形式

APIは人間が記述・理解しやすい形式のプログラムであるソースコード上でどのような記述をすべきかを定めており、原則としてプログラミング言語ごとに定義される。

関数やプロシージャなどの引数や返り値のデータ型やとり得る値の意味や定義、関連する変数や定数、複合的なデータ構造の仕様、オブジェクト指向言語の場合はクラスやプロパティ、メソッドの仕様などを含む。

通信回線を通じて遠隔から呼び出すような構造のものでは、送受信するパケットやメッセージの形式、通信プロトコル(通信規約)などの形で定義される仕様をAPIと呼ぶこともある。

Web API

近年ではネットワークを通じて外部から呼び出すことができるAPIを定めたソフトウェアも増えており、遠隔地にあるコンピュータの提供する機能やデータを取り込んで利用するソフトウェアを開発することができる。

従来は通信を介して呼び出しを行うAPIはRPC(リモートプロシージャコール)の仕様を元に製品や環境ごとに個別に定義されることが多かったが、インターネット上でのAPI呼び出しの場合は通信にHTTPを、データ形式にXMLやJSONを利用するWeb APIが主流となってきている。

2000年代前半まではWeb APIの標準として仕様が巨大で機能が豊富なSOAPの普及が試みられたが、2000年代中頃以降は軽量でシンプルなRESTful APIが一般的となり、狭義のWebアプリケーションだけでなく様々な種類のソフトウェアやネットサービス間の連携・接続に幅広く用いられるようになっている。

APIと実装

API自体は外部からの呼び出し方を規定した決まりごとに過ぎず、呼び出される機能を実装したライブラリやモジュールなどが存在して初めてAPIに挙げられた機能を利用することができる。

あるソフトウェアのAPIが公開されていれば、同じAPIで呼び出すことができる互換ソフトウェアを開発することもできる。ただし、APIを利用する側のプログラムが(スクリプトなどではなく)バイナリコード(ネイティブコード)の場合にはこれをそのまま動作させることはできないのが一般的で、同じソースコードを元に互換環境向けにコンパイルやビルドをやり直す必要がある(ソースレベル互換)。

また、API自体は標準実装における動作の詳細までは定義していないため、APIが同一の互換ソフトウェアだからといって動作や振る舞いがまったく同じであるとは限らない。商用ソフトウェアの場合はAPIが非公開だったり、すべては公開されていなかったりすることが多く、公開情報だけではAPI互換の製品を作ることも難しい。

APIと知的財産権

従来は特許で保護されている場合を除いて、APIそのものには著作権その他の知的財産権は存在しないとする見方が一般的で、実際、元のソフトウェアのコードを複製せずすべて独自に実装するという方法でAPI互換ソフトウェアが数多く開発されてきた。

ところが、米オラクル(Oracle)社が権利を有するJava言語やその処理系に関して、米グーグル(Google)社が同社の許諾を得ずにAndroidスマートフォン向けにJava APIを実装した実行環境(Dalvik VM)を開発・提供しているのは著作権侵害であるとの裁判が起こされ、米裁判所は訴えを認める判決を出した。今後はAPIの権利について従来の状況が変化していく可能性がある。

変数につけた名前を「変数名」と呼び、記憶されているデータをその変数の値という。データの入れ物のような存在で、プログラム中で複数のデータを扱いたいときや、同じデータを何度も参照したり計算によって変化させたい場合に利用する。

変数をプログラム中で利用するには、これからどんな変数を利用するかを宣言(declaration)し、値を代入(assignment)する必要がある。コード中で明示的に宣言しなくても変数を利用できる言語もある。変数に格納された値を利用したいときは、変数名を記述することにより値を参照(reference)することができる。

変数の型

プログラム中で扱うデータは整数、浮動小数点数、文字列など様々なデータ型に分かれており、変数も特定のデータ型を持つ。多くの言語では宣言時に一つのデータ型を指定しなければならず、後から型は変えられないが、特定の型を指定しなくても処理系が適切な型を適用(型推論)してくれる言語や、代入などによって途中で型を切り替えることができる言語もある。

変数のスコープ

変数は宣言した位置などにより通用する範囲(スコープ)が決まっており、範囲の外から参照や代入を行うことはできない。プログラム全体を通用範囲とするものを「グローバル変数」(大域変数)、特定のサブルーチンや関数、メソッド、コードブロックなどの中でのみ通用するものを「ローカル変数」(局所変数)という。オブジェクト指向言語では「クラス変数」や「インスタンス変数」などに分かれる。

特定の関数やメソッド、サブルーチンなどのコードブロックに所属せず、プログラム全体を有効範囲(スコープ)とする変数である。通常、プログラムの冒頭など、どのブロックにも含まれない最も外側に変数宣言を記述することにより定義することができる。変数の寿命はプログラムの開始から終了までで、プログラムの実行中はずっと同じメモリ領域に置かれ、内容が維持され続ける。

多数の関数などにまたがってプログラム全体で頻繁に参照・更新される変数などを、いちいち引数などの形で明示的に受け渡さなくてもよいといった利点があり、メモリ容量や処理速度に厳しい制約がある場合などには多用されることもある。

一方、プログラム中のどこからでも変更できるため、プログラムの規模が大きくなるとどこでどのように書き換えられているのか把握しにくくなり、予期せぬバグが生まれたり、開発の分業やコードの追加・修正が困難になる。

また、開発者の異なる複数のソースコードを連結して実行ファイルを生成する場合など、グローバル変数の変数名が衝突してバグを生み出すこともある。このような特徴からグローバル変数の使用を好ましくないと考える開発者も多く、グローバル変数を仕様から排除したプログラミング言語もある。

用意されている比較の種類や記法は言語によって様々だが、数の一致や大小は数学の表記に倣って「=」(等しい)「>」(より大きい)「<」(より小さい)の組み合わせで記述する場合が多い。

その際、「～以上」(≧)は「>=」または「=>」、「～以下」(≦)は「<=」または「=<」とする。不一致(≠)は「!=」や「<>」などで表されることが多い。

「=」は代入の意味で用いられることもあるため、混同や誤用しないよう一致の比較演算子を「==」などとする言語も多い。一致・不一致の演算子は数だけでなく文字や文字列、真偽値など様々なデータ型に用いられる。

異なるデータ型の比較

「1==“1”」のようなデータ型の異なる値同士の比較を許容する(自動的に一方の型に変換して比較する)言語と、これを禁じてエラーとして処理する言語がある。前者の場合、例えば「==」を実質的な内容の一致、「===」を内容とデータ型両方の一致(厳密等価演算子あるいは同値演算子と呼ばれる)として使い分ける言語もある。

複合的なデータ構造の比較

オブジェクト指向言語におけるインスタンスや、配列などの複合的なデータ構造などを比較できる言語もある。

その際、一致・不一致は「両方ともメモリ上の同一の実体を指し示している」(参照が一致している)ことを意味する場合と、「含まれるデータの型や値がすべて同じである」(内容が一致している)ことを意味する場合がある。どちらか一方の比較のみ可能な場合と、それぞれを異なる記法で書き分けるようになっている場合がある。

論理否定(NOT)、論理和(OR)、論理積(AND)、排他的論理和(XOR)のそれぞれについて、「&&」といった1～2文字記号の組み合わせや、「and」などの符号を演算子として用いる。具体的な演算子の定義は言語によって異なる。否定論理積(NAND)や否定論理和(NORなどの演算子が用意されている場合もある。

NOTは「!a」(aではない)のように演算対象となる被演算子(オペランド)を一つ記述する単項演算子で、他は「a && b」(aかつb)のように二つを記述する二項演算子である。「a && b && c」(aかつbかつc)のように三つ以上を連結することもでき、複数の論理演算のどれを先に計算するか優先順位が決まっている(ほとんどの場合NOT→AND→ORの順)。

論理演算子とビット演算子

コンピュータでは1ビットの値の1を真に、偽を0に置き換えて論理演算子を行うことが頻繁にあり、二つのビット列のそれぞれ対応する桁にある値同士(NOTではビット列の各桁の値)で論理演算を行うことをビット演算という。

ビット演算のための演算子をビット演算子と呼び、各論理演算子に対応する演算を行うためのビット演算子が別に用意されていることが多い。例えばC言語や多くの派生言語では「&&」が論理演算のAND、「&」がビット演算のAND、「||」が論理演算のOR、「|」がビット演算のORとなっている。

論理学では記号「∧」を用いて「P∧Q」のように表記し、電子工学(論理回路)では記号「⋅」を用いて「P⋅Q」のように表す。論理積演算を行う論理回路を「論理積演算回路」「AND演算回路」「ANDゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの論理積演算を行う演算子が用意されており、キーワード「and」を用いて「P and Q」と書くものや、C言語に倣って「&」(アンパサンド)記号を用いて「P&Q」と表記する言語が多い。また、ビット演算と区別して条件式などで用いる真偽値(真理値)の論理積演算を定義している言語では、「and」キーワードや「&&」などの記号が用いられることが多い。

三入力以上の場合は、まず二つを選んで論理積を取り、その結果と残りの一つを選んで論理積を取り、という手順を繰り返すことで結果を得ることができ、すべての入力が1のときのみ出力が1となり、いずれかの入力が0の場合には0となる。

論理積は論理和(OR演算)と論理否定(NOT演算)を組み合わせて P∧Q ⇔ ¬(¬P∨¬Q) と表すことができる。逆に、論理和は論理積と論理否定を組み合わせて P∨Q ⇔ ¬(¬P∧¬Q) と表すことができる。これをド・モルガンの法則という。

論理学では記号「∨」を用いて「P∨Q」のように表記し、電子工学(論理回路)では記号「+」を用いて「P+Q」のように表す。論理和演算を行う論理回路を「論理和演算回路」「OR演算回路」「ORゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの論理和演算を行う演算子が用意されており、キーワード「or」を用いて「P or Q」と書くものや、C言語に倣って「|」記号を用いて「P|Q」と表記する言語が多い。また、ビット演算と区別して条件式などで用いる真偽値(真理値)の論理和演算を定義している言語では、「or」キーワードや「||」などの記号が用いられることが多い。

三入力以上の場合は、まず二つを選んで論理和を取り、その結果と残りの一つを選んで論理和を取り、という手順を繰り返すことで結果を得ることができ、いずれかの入力が1のときに出力が1となり、すべての入力が0の場合に0となる。

論理和は論理積(AND演算)と論理否定(NOT演算)を組み合わせて P∨Q ⇔ ¬(¬P∧¬Q) と表すことができる。逆に、論理積は論理和と論理否定を組み合わせて P∧Q ⇔ ¬(¬P∨¬Q) と表すことができる。これをド・モルガンの法則という。

論理学では記号「¬」を用いて「P¬Q」のように表記し、電子工学(論理回路)では記号「¯」(上線)を用いて「P」のように表す。論理否定演算を行う論理回路を「否定演算回路」「NOT演算回路」「NOTゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの論理否定演算(ビット反転)を行う演算子が用意されており、キーワード「not」を用いて「not p」のように書くものや、C言語などの記法にならって「~」(チルダ)記号を用いて「~p」のように表記する言語が多い。

ビット演算と区別して条件式などで用いる真偽値(真理値)の論理否定演算を定義している言語では、「not」キーワードや「!」などの演算子が用いられることが多い。いずれの場合も、演算の対象となる被演算子(オペランド)が一つの単項演算子である。

論理和(OR演算)に似ているが、論理和では「いずれか一方が真」なら他方が何であれ結果は真となるが、排他的論理和では「いずれか一方のみが真」の場合に真となる。両者共に真の場合は真とならないことを「排他的」と表現している。

三入力以上の場合は、まず二つを選んで排他的論理和を取り、その結果と残りの一つを選んで排他的論理和を取り、という手順を繰り返すことで結果を得ることができる。入力における真の数が奇数個のときに出力が真に、偶数個のとき偽となる。

論理学では記号「⊻」を用いて「P⊻Q」のように表記し、電子工学(論理回路)では記号「⊕」を用いて「P⊕Q」のように表す。排他的論理和演算を行う論理回路を「排他的論理和回路」「XOR回路」「XORゲート」などと呼ぶ。

多くのプログラミング言語でもビットごとの排他的論理和演算を行う演算子が用意されており、キーワード「xor」を用いて「P xor Q」と書くものや、C言語に倣って「^」(ハット、キャレット)記号を用いて「P^Q」と表記する言語が多い。

あるビットが「0」のとき、「1」と排他的論理和を取ると「1」になるが、元の値が「1」なら結果は「0」になる。すなわち、「1と排他的論理和を取る」という演算は「そのビットの値を反転する」という操作になる。これを利用して、反転したい位置を「1」にセットしたビット列を用いて、入力値の特定のビットのみを反転させるという操作がよく用いられる。

命令の出現順、記述順の通りに順番に命令を実行する「順次構造」(sequence)、条件によって実行する命令の流れがいくつかに分岐する「選択構造」(selection)あるいは「分岐構造」、同じ命令の流れを繰り返し実行する「反復構造」(iteration)あるいは「繰り返し構造」(repetition)の3つを基本とする考え方が多い。

また、方法論や言語の違いにより、これらに加えて、プログラム中の任意の別の箇所に実行の流れを移す「無条件分岐」(ジャンプ命令、goto文)や、別の命令群に流れを移し、終わると元の場所に流れを戻す「サブルーチン」(呼び出し、コール)、プログラム終端以外の箇所で実行を終わらせる「停止」(終了)などを加える場合もある。

プログラミング言語における制御構造

機械語やアセンブリ言語(ニーモニック)のようなCPUの構造に忠実な低水準言語では、命令実行の流れを制御する命令として無条件ジャンプ命令と条件ジャンプ命令しか用意されていないことが多く、他の制御構造はこれらと他の命令を組み合わせて実装する。

人間に分かりやすく抽象的なプログラム構造を記述できる高水準言語では、選択や反復を記述するための制御文が用意されていることが多い。言語によって名称や仕様は異なるが、選択構造は「if文」(二分岐)や「switch文」(多分岐)などで、反復構造は「for文」「while文」「do-while文」などで記述することができる。

コンピュータのCPUがプログラムを実行する際、特に指定がなければプログラムを先頭から読み込んで命令を並んでいる順に従って一つずつ実行していく。この最も基本的な命令実行の制御構造を、(他の構造と対比するため便宜的に)順次構造と呼ぶ。

一方、命令の中には命令実行の流れを変更するものもある。これを用いて、条件に従って別の実行位置に流れを分岐させる制御構造を「選択構造」あるいは「分岐構造」、条件が満たされる間だけ同じ個所を繰り返し実行する制御構造を「反復構造」あるいは「繰り返し構造」という。

コンピュータのCPUがプログラムを実行する際、特に指定がなければ命令を先頭から順に実行するが、分岐命令が存在する場合、特定の条件が満たされたらメモリの指定番地に実行位置を変更(ジャンプ)し、以降はそこから順に命令を実行していく。

このような実行制御を「条件分岐」と呼び、プログラムに複雑な処理をさせたい場合は必須の機能となる。一方、条件が満たされる間だけ同じ個所を繰り返し実行する制御構造もあり、「反復構造」あるいは「繰り返し構造」という。

コンピュータのCPUがプログラムを実行する際、特に指定がなければ命令を先頭から順に実行するが、反復構造になっている場合、指定の条件が満たされている間、指定範囲の末尾の命令を実行したら範囲の先頭に戻り、その範囲を繰り返し実行する。

同じ処理を様々な対象に次々に適用したい場合などに用いられ、プログラムに複雑な処理をさせたい場合には必須の機能となる。一方、特定の条件が満たされたらメモリの指定番地に実行位置を変更(ジャンプ)する制御構造もあり、「選択構造」あるいは「分岐構造」という。

よく知られるのはプログラムの制御構造の入れ子構造で、if( 条件A ){ ... if( 条件B ){ ... } ... } といったように、条件分岐やループの内部に、別の条件分岐やループなどが含まれた制御構造を指す。複雑な条件による分岐や多重ループを記述するための基本的なテクニックとして多くのプログラミング言語で利用できる。

for文の中にfor文を記述するなど、同じ構文を入れ子状に繰り返すことを指す場合が多いが、while文の中にif文など、異なる制御構文を内部に記述することも含む場合がある。内側の構文の内部にさらに構文を重ねて、マトリョーシカのように何重も入れ子にすることができ、階層の多さを「入れ子構造の深さ」と表現することがある。

サブルーチンなどの入れ子構造

プログラミング言語の中には、サブルーチンやプロシージャ、関数、クラスなどのコードのまとまりを入れ子構造させ、内部に同種のまとまりを定義することができるものもある。例えば、関数の内部に定義された別の関数を「関数内関数」「ローカル関数」などと呼び、クラスの内部に定義された別のクラスを「クラス内クラス」「インナークラス」「内部クラス」などという。

データ構造の入れ子構造

あるデータ構造の要素として、そのデータ構造自身を埋め込むことができる場合があり、データ構造の入れ子構造を形成する。例えば、配列を構成する個々の要素が配列になっている多次元配列は配列の入れ子構造である。

配列の配列など、内部が再帰的に同じ構造になっているものを指すことが多いが、連想配列の要素が配列になっているものなど、制御構文の場合と同じように異なる構造が入れ子状になっている場合も含むことがある。

プログラム中の様々な状況や箇所で繰り返し必要となるような処理をサブルーチンとして名前をつけて一つの塊として定義することで、その処理を何度も繰り返し記述・複製する必要がなくなり、コード量の削減や開発効率の向上、記述ミスなどによる誤り(バグ)の減少などが期待できる。

サブルーチン内部の処理に反映させるため、呼び出し側から値を指定できるようになっている場合が多く、この値を「引数」(ひきすう/argument)という。また、処理結果として呼び出し元に値を返すことができる場合があり、この値は「返り値」あるいは「戻り値」という。返り値を持つサブルーチンは「関数」(function)と呼ぶのが一般的である。

かつてはプログラムが起動したとき最初に実行される主系統のコード集合を「メインルーチン」(main routine)、そこから呼び出される形で実行される副系統のコード群をサブルーチンと呼んで区別していたが、現在ではそのような構造に当てはまらない例も増えており、サブルーチンのことを単にルーチンと呼ぶことも多い。

サブルーチンに相当するコード集合は、プログラミング言語によっては「プロシージャ」(procedure)のように異なる名称で呼ばれることもある。オブジェクト指向プログラミングでは一般的に「メソッド」(method)という。返り値を持つか否かで名称が異なる言語(Pascalのプロシージャと関数など)や、C言語のようにすべてを関数と呼ぶ場合もある。

プログラム上で関連する一連の命令群を一つのかたまりとしてまとめ、外部から呼び出せるようにしたサブルーチンやプロシージャ(手続き)の一種である。呼び出し時に引数(ひきすう/argument)と呼ばれる値を指定することができ、この値をもとに内部で処理を行って、結果を返り値(かえりち/return value)あるいは戻り値(もどりち)として呼び出し元に通知する。

プログラミング言語によって、返り値を持つものを関数(ファンクション)、処理を行うだけのものをサブルーチンやプロシージャとして区別する場合もある(Pascalなど)が、C言語やJavaScriptのようにすべてが関数で引数や返り値が省略可能になっている言語もある。

多くのプログラミング言語は開発者が自由に関数を定義してプログラム中で呼び出せる構文や記法を定めているほか、算術関数や文字列処理などよく使われる基本的な関数言語仕様や標準ライブラリなどの中であらかじめ実装済みとなっている(組み込み関数)。

関数といっても数学のように計算を行うものには限られず、「利用者に入力を促して入力値を返す」関数といったものもあり得る。途中で画面に何かを表示するなど、引数や返り値と直接関係ない処理を行ってもよい。

プログラムは内部に変数の値など実行状態を持つため、これを反映して同じ引数から異なる返り値が得られる場合もある。また、関数が行う処理によって状態が変化することもあり、これを関数の持つ「副作用」という。多くの算術関数のように副作用のない関数もある。

配列はほとんどのプログラミング言語に存在する最も基本的なデータ構造の一つで、単純に変数を一列に並べたものである。データ全体はコード中で配列名で指し示され、各要素は通し番号などの添字で区別される。例えば、長さ5の整数型の配列変数xを宣言すると、x[0]からx[4]まで5つの整数型の変数が用意され、それぞれ独立に整数値を格納することができる。

各要素のデータ型が同じでなければならない言語と、要素ごとに異なる型のデータを格納できる言語がある。変数の宣言が必須の言語では、配列変数の宣言時に要素のデータ型と数をあらかじめ指定しなければならないことが多い。要素数を後から増減できる動的配列(可変長配列)が利用できる言語もある。

添字は0から始まる整数とする言語が多く、要素がn個の配列の添字は0からn-1までとなる。添字に文字列など整数以外のデータ型の値を取れるようにしたデータ構造を利用できる言語もあり、これを「連想配列」(associative array)と呼ぶ。言語によっては同様のデータ構造を辞書(ディクショナリ)、ハッシュ、マップ、連想リスト等と呼ぶこともある。

配列の要素として配列を格納した、入れ子状のデータ構造を「多次元配列」という。配列の要素が配列になっており、その要素が値になっている構造が「2次元配列」で、配列が3段階に入れ子状になっている構造は「3次元配列」である。同様に、入れ子がn段階になっている配列を一般に「n次元配列」という。要素が値になっている単純な配列をこれらと対比する場合は「1次元配列」と呼ぶことがある。

曖昧さのない単純で明確な手順の組み合わせとして記述された一連の手続きで、必ず有限回の操作で終了し、解を求めるか、解が得られないことが示される。コンピュータで実行する場合は、基礎的な演算、値の比較、条件分岐、手順の繰り返しなどを指示する命令を組み合わせたプログラムとして実装される。

数値などの列を大きい順または小さい順に並べ替える「整列アルゴリズム」、たくさんのデータの中から目的のものを探し出す「探索アルゴリズム」、データが表す情報を損なわずにより短いデータに変換する「圧縮アルゴリズム」といった基本的なものから、画像の中に含まれる人間の顔を検出する、といった複雑なものまで様々な種類のアルゴリズムがある。

同じ問題を解くアルゴリズムが複数存在することもあり、必要な計算回数や記憶領域の大きさ、手順のシンプルさ、解の精度などがそれぞれに異なり、目的に応じて使い分けられる。例えば、ある同じ問題に対して、原理が単純で簡単にプログラムを記述できるが性能は低いアルゴリズム、計算手順が少なく高速に実行できるが膨大な記憶領域を必要とするアルゴリズム、厳密な解を求めるものより何桁も高速に近似解を求めることができるアルゴリズムなどがある。

データの並べ替え(ソート)における順序の指定などに用いられる概念で、小さい方から大きい方へ、あるいは本来の並び順における先頭側から末尾側へ「昇(のぼ)っていく」順序のことを意味する。

数字であれば1、2、3…と小さい値から大きい値へ、アルファベットであれば「A」から「Z」に向けて、カナであれば「ア」から「ン」に向けて、日付や時刻であれば過去側・古い側から未来側・新しい側に向けて並べる順序である。

一方、大きい方から小さい方へ、あるいは本来の並び順とは逆に並べる順序は「降順」(descending order)という。「9、8、7」「Z、Y、X」「ん、を、わ」といった本来とは逆の並び順のことである。

データの並べ替え(ソート)における順序の指定などに用いられる概念で、大きい方から小さい方へ、あるいは本来の並び順における末尾側から先頭側へ「降(お)りていく」順序のことを意味する。

数字であれば9、8、7…と大きい値から小さい値へ、アルファベットであれば「Z」から「A」に向けて、カナであれば「ン」から「ア」に向けて、日付や時刻であれば未来側・新しい側から過去側・古い側に向けて並べる順序である。

一方、小さい方から大きい方へ、あるいは本来の並び順の通りに並べる順序は「昇順」(ascending order)という。「1、2、3」「A、B、C」「あ、い、う」といった本来定められた並び順のことである。

まず、2から目的の数までの整数のリストを用意する。このリストの中から最初の素数である2の倍数を消していく。リストに残った整数のうち、先頭にある3が次の素数である。次に、リストの中から3の倍数を消してゆき、残った整数のうち先頭にある5が次の素数である。

このように、先頭に残った数の倍数をリストから消してゆき、その都度先頭に残った数を集めると、素数のリストが得られる。このアルゴリズムが「篩」(ふるい)と呼ばれるのは、この一連の操作が、粉状のものを何段階もふるいにかけてより分ける作業に似ていることに由来する。

この操作は目的の数まで繰り返す必要はなく、先頭に残った素数の2乗が与えられた数を超えるまで(先頭の素数が目的の数の2乗根を超えるまで)でよい。これ以降にリストに消されずに残っている数はすべて素数である。整数においては $a\times b=b\times a$ が成り立つため、これ以降に存在する合成数はそれ以前の操作によりすべて消されているためである。

多くのプログラミング言語には乱数を生成する組み込みの関数やメソッドなどが用意されており、呼び出すたびに規則性のないランダムな数値を返す。多くの言語では0以上1未満の浮動小数点数が得られるようになっており、用途に応じて必要な形式に計算・加工して利用する。

コンピュータはその性質上、ソフトウェアによって完全な乱数を生成することはできないため、統計的に乱数と同じ性質を持つような「擬似乱数」(pseudorandom numbers)を計算によって生成している。

これは計算方法と初期値が分かれば全く同一の数値列を再現できるため、暗号化などの用途では不都合となる場合がある。このため、センサーを内蔵して外界の物理現象を測定して数値として反映させるなどの手法により、擬似的でない真の乱数を生成する半導体チップが利用される場合もある。