高校「情報Ⅰ」単語帳 - 実教出版「図説情報Ⅰ」 - アルゴリズムとプログラミング

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

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

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

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

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

ソフトウェアの誤作動を引き起こすコンピュータプログラム中の欠陥を指し、人間がプログラムを書き記す際に起きる単純な誤記や勘違いなどによるものから、構想や設計の段階で誤りや矛盾が含まれていたことに起因するものなど、様々な原因によって発生する。プログラム中の誤りを発見し取り除く作業・工程を「デバッグ」(debug：除虫する)という。

バグを含むプログラムを実行することで生じる問題は様々だが、典型的なものとしては、利用者の操作に応答しなくなったり、設計意図と異なる挙動を示したり、誤ったデータを出力したり、記録されたデータを破壊したりといった振る舞いが挙げられる。

ビデオゲームの分野では、キャラクターやフィールドが通常はありえない状態になる現象や、不可能なはずの挙動や展開が可能になるバグが注目されることが多い。製品としては欠陥だが、バグによって可能になる奇妙な挙動や攻略テクニックなどを「裏技」「バグ技」などと呼んで面白がる文化がある。

潜在的なバグ

常に同じ実行箇所に差し掛かると同じ問題を引き起こすバグは発見しやすいが、いつどこで実行しても同じ箇所で必ず不具合を引き起こすとは限らない。特定の入力データや操作、使用環境や設定、あるいはそれらの特定の組み合わせによって発現し、それ以外の状況では誤作動を引き起こさない場合がある。

例えば、1980年代までは日付データの年号部分を西暦の下二桁で記録・管理することは記憶容量の節約や処理速度の向上に寄与するとして推奨されることが多かったが、西暦2000年に到達すると正常に動作しなくなる(西暦2000年問題)。実際、情報システム業界は1990年代末に業務用システムの改修に大きな人手を割くことになった。

バグの発見と修正

コンピュータプログラムの設計・記述の多くは人間が行うため、バグの発生・混入を未然に完全に防ぐ方法はなく、いかに効率よく早期に発見し取り除くかが重要となる。そのためには、ソフトウェア開発の各段階で繰り返し入念にテストを行い、発見された不具合や誤作動についてプログラム上の発生箇所や原因を特定し、対処方法を決定して修正などを行う。

発見されたほとんどのバグは正しい動作を行うプログラムコードに差し替えられる。発売・公開前のプログラムは修正して実行ファイルなどを作りなおすが、利用者の手元に提供した後にバグが発見されることもある。そのような場合には、開発元が「パッチ」「バグフィックス」などと呼ばれる修正プログラムをインターネットなどを通じて配布し、利用者側のソフトウェアを更新する。

オペレーティングシステム(OS)やライブラリ、ミドルウェアなど基盤的なソフトウェアの場合には、修正によってプログラムの振る舞いが変わり、従前の振る舞いを前提に動作していた他のプログラムなどに思わぬ影響を及ぼすことがある。深刻な影響が想定される場合はバグをあえて放置し、別の箇所や方法で悪影響を抑えるというアプローチが取られる場合もある。

歴史

古くは19世紀の記録に機械の設計・製造上の誤りや不良が “bug” と呼ばれていた事例がいくつか知られており、初出がいつに遡るのかは判然としない。現代のコンピュータのソフトウェアにおける用例に近い初期のエピソードとして最も有名なものは、1947年にグレース・ホッパー(Grace Hopper)氏が米ハーバード大学で遭遇した事例である。

初期の電気機械式のコンピュータ「Harvard Mark II」の不具合を調査する過程で、あるスタッフがリレー(スイッチ)に蛾が挟まって接触不良を起こしているのを発見した。彼女は日誌に蛾をテープで留め、“First actual case of bug being found”(実際にバグが見つかった最初の事例) と書き残した。

プログラムが仕様や開発者の意図と異なる動作をする場合、そのような動作を引き起こすプログラム上の欠陥、誤りを「バグ」(bug：虫)という。テストなどによって発見された誤作動・不具合について、その原因やソースコード上での位置を探索・特定し、意図した通りに動作するように修正する作業をデバッグという。

バグの探索

デバッグ作業ではまず、バグがプログラムのどこに潜んでいるのかを探し出す。バグはエラーなどで停止したコードに存在するとは限らない。あるコードが誤ったデータを生成し、そのデータを使って処理を行おうとした別のコードが致命的なエラーを起こして停止するということもあるからである。

位置が特定されると、なぜそのような誤りが生じたのか原因を調べる。単純な誤記によるものから、プログラムを構成する論理やアルゴリズムの誤りに原因がある場合、当初の想定では予期していなかった入力値や動作環境など、様々なものが原因になりうる。

バグの修正

原因が特定されると修正が行われるが、様々なシステムの基盤に用いられるような製品では外部のシステムがすでにそのバグが存在する前提で作られてしまっている場合もあるため、修正せずに存在を周知して個別に対策するよう呼びかける場合もある。

また、修正によって新たなバグが発生したり、別の箇所に潜んでいたバグを顕在化させる「デグレード」と呼ばれる事態が生じることもあるため、修正したプログラムは当該箇所以外への影響も含めて入念にテストされることが多い。

デバッガ

デバッグ作業を支援するソフトウェアを「デバッガ」(debugger)あるいは「デバッグツール」(debugging tool)という。“debugger” は英文法的には「デバッグを行う者」という意味だが、プログラムを自動的に修正してくれるわけではなく、バグの位置を特定するためにプログラムの動作状況を解析・可視化する機能などを提供するものを指し、デバッグ作業自体は人間の開発者が行う。

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

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

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

様々な表現形式があるが、一般的な手法では、対象が取りうる状態を円や矩形などで列挙し、どこからどこへ遷移が起きうるかを矢印によって示す。各矢印の脇に、その遷移が起きるための条件やきっかけとなる出来事などを記述する。自らに遷移する場合は自分を指し示す輪っか状の矢印を書き入れる。

対象に開始や終了がある場合は、特殊な記号で示される場合がある。UMLでは開始を塗りつぶした丸印で、終了を内側を塗りつぶした二重丸で記載するよう定められている。

状態遷移表

状態遷移図の各状態を一行として表の形で書き表したものを状態遷移表という。

一般的な形式では、各行が対象の状態を、各列がイベントを表し、ある状態のときにあるイベントが起きたときにどの状態に遷移するかを書き入れていく。

また、縦軸・横軸ともに状態を並べ、各状態の交差する項目にそのような遷移が起こるイベントを書き入れていく様式もある。

ソフトウェア開発の分野ではテストを行う際にテストケースを漏れなく網羅するために状態遷移表が作成される場合がある。

ステートマシン図 (state machine diagram)

ソフトウェアの設計などに用いられるUML(Unified Modeling Language)では、状態遷移図に相当する図をステートマシン図(state machine diagram)として定義している。

あるオブジェクトの振る舞いを漏れなく記述するために用いられるもので、開始状態を塗りつぶした丸印(●)、終了を内側を塗りつぶした二重丸で表し、途中の状態を角丸の矩形を並べて図示していく。

状態間は遷移する方向に矢印で繋ぎ、脇に遷移の説明を添える。遷移したときに実行する動作がある場合は矩形を横に区切って下半分に動作の内容を記述する。

アクティビティ図ではそれ以上分割できない最小の動作単位を「アクション」(action)と呼び、角丸四角形で図示する。アクションを組み合わせたひとまとまりの動作を「アクティビティ」(activity)と呼ぶ。

活動の開始ノード(黒丸で示される)から終了ノード(丸で囲った黒丸で示される)までの間にアクションやアクティビティを配置し、それぞれの依存関係に従って矢印で結んでいく。

次のアクションへ情報などが受け渡される場合には、中間に四角形で示す。矢印で結ばれた手順の流れを「フロー」(flow)という。異常終了などでフローが途中で終了する場合には、終了地点に丸囲みの×印を記す。

アクティビティ図全体を縦または横(あるいはその両方)に分割して実行主体や段階を示すことができる。アクションやアクティビティが分割されたどの領域に存在するかによって、どの主体による動作かを示したり、どのような段階に行われる動作かを示すことができる。

フローの分岐・合流

特定の条件に従ってフローが分岐する場合には、菱形の「デシジョン」(decision：判断)ノードを置いて2方向に矢印を記し、それぞれの脇に条件を記述する。フローが合流する地点には同じ菱形の「マージ」(merge：合流)ノードを置く。

ある時点から複数のフローを並列に実行する場合には、その開始地点に太い直線で示される「フォーク」(fork：分岐)ノードを置き、複数のフローを出発させる。これらの同期を取って一つのフローに戻したい場合には、同じく太い直線の「ジョイン」(join：結合)ノードを置き、フローを集合させる。

プログラミング言語でプログラムを開発することを「プログラミング」(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)などの分類がある。

一般的には「順接、反復、分岐の三つの制御構造のみを組み合わせて処理の流れを記述すること」と説明されることが多いが、これは本来の定義とは異なる誤解が広まったものだとも指摘される(後段で詳述)。

今日一般的に言われる構造化プログラミングとは、プログラム中のコードの実行順の制御を、記述した順番に実行する「順接」あるいは「順次」(sequence)、指定された条件が成り立つ間繰り返す「反復」あるいは「繰り返し」(iteration)、指定された条件を満たすか否かによって枝分かれする「分岐」あるいは「選択」(selection)の三つのみを組み合わせて記述することとされる。

特に、実行順の制御をこの三つに限定することにより、かつてのプログラミングで多用されていた、指定した任意の位置に無条件に移動する “goto” 文を排除し、処理の流れがあちこちへ飛んで見通しが悪くなるのを防ぐことが重要であると説明される。

構造化定理とその解釈

この原則は1966年にイタリアのコンピュータ科学者コラド・ベーム(Corrado Böhm)とジュゼッペ・ヤコピーニ(Giuseppe Jacopini)が証明した「構造化定理」(Structure theorem)あるいは「構造化プログラム定理」(Structured program theorem)によって基礎付けられているとされる。

確かにこの定理はすべてのアルゴリズムが順接、反復、分岐の三つの組み合わせで記述できることを示してはいるが、計算科学における理論上の可能性を述べており、これによって見通しの良いプログラムを開発できるといった趣旨の主張は含まれていない。

実際、高名なコンピュータ科学者のドナルド・クヌース(Donald Knuth)は、プログラムからgoto文を除去してこの三つの組み合わせに置き換えることにより却って構造が失われる例を示し、構造化定理のこのような解釈を批判している。

ダイクストラの構造化プログラミング

「構造化プログラミング」(structured programming)の語が最初に提唱されたのは1969年にオランダのコンピュータ科学者エドガー・ダイクストラ(Edsger W. Dijkstra)が発表した論文で、本来はこちらが構造化プログラミングの定義であるとされる。

彼の主要な問題意識は、プログラムの規模が大きくなっても正しさを容易に検証できるような「良く構造化されたプログラム」(well-structured program)を記述する方法論で、そのためのいくつかの考察と原則を構造化プログラミングという概念でまとめた。

これには、現代では関数やサブルーチンなどとして知られる、プログラムの「段階的な抽象化」(step-wise abstraction)、現代のオブジェクト指向プログラミングに近い、「抽象的なデータ構造」(abstract data structures)とこれに関連付けられた「抽象的な構文」(abstract statements)の「共同詳細化」(joint refinement)が含まれる。

これらを適用したプログラムは上下に階層化された交換可能なモジュール(部品)を連結したような構造になると指摘し、これを真珠のネックレスの構造に例えて説明している。この論考には「構造化定理」も「三つの制御構文」も「goto文」も登場せず、構造化プログラミングの本来の概念とこれらとはあまり関係がない。

しかし、ダイクストラが別の機会に発表したgoto文の濫用に疑問を呈する論説(1968年の “Go To Statement Considered Harmful” )や、他の論者とのいわゆる「goto文論争」、また、「構造化定理」と「構造化プログラミング」の名称の類似性などを通じて、次第に「三つの制御構文」式の理解が広まっていったと考えられている。

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

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

変数の型

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

変数のスコープ

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

プログラムは実行時にコンピュータのメインメモリ(RAM)内にデータの保管領域を確保し、データの書き込みや読み出し、書き換えなどを行うことができる。コンピュータ内部では個々のデータの記憶位置を番地(メモリアドレス)で識別・指定するが、人間には分かりにくいため、プログラミング言語で記述するプログラム(ソースコードという)の中では、名前の付いた「変数」(variable)として扱う。

仕様上の命名規則

変数名として使用可能な文字の種類や名付けの規則(禁止事項)は言語仕様によって決まっているが、C言語では半角英数字(0～9、a～z、A～Z)とアンダーバー(_)のみ使うことができ、この仕様を踏襲している言語が多い。数値リテラルと区別する必要から、先頭に数字を使うことはできない。多くの言語は英大文字と小文字を別の文字として区別するが、同一視する言語もある。

先頭や末尾に特定の記号を付けることでデータ型やデータ構造(コレクション)の種類を指定することができる言語もある。例えば、Perlでは「$a」のように先頭が「$」(ドルマーク)の変数はスカラ変数を表しており、Visual BasicやVBAでは「a$」のように末尾が「$」の変数は文字列型となる。

慣習上の命名規則

言語仕様上の変数名の規則とは別に、言語ごとの慣習や、組織・プロジェクトごとに命名規則を定めて一定の規則性に従って命名する場合もある。例えば、先頭にデータの種類を表す接頭辞を付ける命名法を「ハンガリアン記法」という。「jpyPrice」のようにデータの意味を表すものを「アプリケーションハンガリアン」、「bChecked」のようにデータ型などを表すものを「システムハンガリアン」という。

また、複数の単語を連ねて変数名とする場合に、「fooBarBuz」のように単純に連結して各単語の先頭を大文字にする方式を「キャメルケース」、「foo_bar_buz」のようにアンダーバーで区切る方式を「スネークケース」という。キャメルケースのうち、「FooBarBuz」のように変数名自体の先頭を大文字にする方式は「パスカルケース」とも呼ばれる。

例えば、プログラム上で整数型の変数xを宣言し、これに1を代入すると、以降のコードではxの値は1として扱われる。別の値を再代入すれば、以降xはその値となる。他の変数に格納された値を代入することもできる。

プログラミング言語にはデータ型(data type)の区別があり、整数の 1 と文字列の "1" は内部的に別の表現形式で表され、適用可能な操作も異なる。変数の型が固定される言語では異なる型の値を再代入することはできないが、スクリプト言語などでは代入によって値と型の両方を同時に変更できる場合もある。

代入を表す書式は言語によって異なるが、C言語やその記法を受け継ぐ多くの言語(JavaやJavaScriptなど)では「x=1;」のように等号(イコール記号)が代入を表す。条件式などで「もし等しければ」という比較を表す場合は、if(x==1) のように等号を2つ並べて「==」と記す。

この記法では、「xの現在の値に1を加算する」は「x=x+1;」のようになり、数学の等号とは意味が異なるため、初学者を混乱させるとして批判されることもある。このため、「=」を数式と意味が似ている比較に用い、代入は「:=」など別の記法にしている言語もある。

言語によっては、演算と代入を組み合わせ、変数の現在の値に指定の演算を行う「復号代入演算子」が用意されていることがある。例えば、加算「+」と代入「=」を組み合わせた加算代入演算子「+=」は、左辺の変数に右辺の値を加算する操作を表す。「x=x+1;」は「x+=1;」と書くことができる。

なお、英語では数学の代入は「代用」「置き換え」などを意味する “substitution” である一方、プログラミングの代入は「割り当て」を意味する “assignment” であり、異なる語、概念となっている。変数の substitution という場合は、変数名が記述された箇所を実際の値で置き換える操作などを表す。

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

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

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

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

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

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

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

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

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

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

データ構造の入れ子構造

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

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

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

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

サブルーチンなどのネスト

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

データ構造のネスト

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

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

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

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

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

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

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

多くのプログラミング言語は、関数やサブルーチン、クラスなど部品化された機能単位を組み合わせて複雑なプログラムを作成する仕組みを持っている。ある言語で利用できる関数のうち、言語仕様に規定されており、処理系が直接解釈できるものを組み込み関数という。

言語によって何が用意されているかは異なるが、基本的・汎用的な文字列操作や算術演算、入出力などの関数が提供されていることが多い。オブジェクト指向言語の場合は、組み込みクラスや組み込みオブジェクト、およびそれらに付随する組み込みメソッドが同様の役割を果たす。

言語仕様に規定され、標準的に利用できる関数全体を「標準関数」という。言語によっては、組み込み関数以外にも、部品化されたプログラム集であるライブラリによって提供される標準関数が規定されている場合がある。そのような関数は「標準ライブラリ関数」という。

これに対し、開発者が自らのプログラム上で独自に定義・実装した関数を「ユーザー定義関数」(user-defined function)という。SDKなど特定の用途や環境でのみ利用可能な関数などもユーザー定義関数として実装されて提供される。

仮引数と実引数

関数などを定義する際に外部から受け取った値を表す変数などを「仮引数かりひきすう」(formal argument)、関数を呼び出す側が実際に指定した値を「実引数じつひきすう」(actual argument)という。

例えば、2つの数を受け取って和を返す関数 function sum(a, b){ return a + b; } があるとき、aやbを仮引数という。一方、この関数を呼び出すコード s=sum(1,2); における1や2が実引数となる。1はaに、2はbに代入されて関数内の処理が実行される。

値渡しと参照渡し

プログラミング言語の引数には「値渡しあたいわたし」(call by value)と「参照渡しさんしょうわたし」(call by reference)があり、どちらもサポートしている言語と片方のみサポートしている言語がある。

値渡しは変数の内容をコピーして渡す方法で、渡された関数などが変数の内容を変更しても、元の変数には影響がない。参照渡しは変数の所在を表す情報を渡す方法で、渡した側と渡された側が同じ変数を共有するため、呼び出された側で変更を加えると呼び出し側にも変更が反映される。

関数などが処理を行った結果として呼び出し元に報告される値のこと。反対に、呼び出し元から関数などに対してパラメータとして渡す値のことは「引数」(ひきすう、argument)という。

戻り値は計算結果の数値や処理結果のデータなどが代表的だが、処理が正しく終了したかどうかを表す真偽値やコード番号、メッセージなどを返す場合もある。多くの言語では「return x+y;」(変数xとyの和を返却する)のようにreturn文(リターン文)と呼ばれる記法で返す値を指定する。

ほとんどのプログラミング言語では戻り値は一つしか返すことができないが、変数への参照やメモリアドレス(ポインタ)を返したり、配列などの複合的なデータ構造、データ型に値を格納して返すことで、複数のデータの集合を返すことができるようになっていることが多い。C言語のvoid型関数のように、明示的に何も返さないよう指定できる言語もある。

関数などを定義する際に戻り値のデータ型もあらかじめ宣言するようになっていることが多く、呼び出し側で受け取る変数の型も揃える必要がある。言語によっては、同じ名前だが引数と戻り値のデータ型が異なる複数の関数やメソッドなどを同時に定義し、引数の型によって自動的に使い分ける機能(オーバーロード)が利用できる場合もある。

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

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

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

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

配列変数は一つの変数に複数の値を並べて格納できるデータ構造で、多くのプログラミング言語に標準で用意されている。配列内の各要素を識別・指定するために通し番号が与えられており、これをコード上で変数名の隣などに記述したものを添字という。

例えば、C言語やその記法を受け継ぐ多くの言語では角括弧で囲んだ数字が配列の添字を表し、“a[0]” は配列aの先頭の要素を、“a[9]” は先頭から10番目の要素をそれぞれ指し示す。

スクリプト言語などでは配列の添字として0から始まる整数の通し番号以外に、任意のプリミティブ型(実数や文字列など)の値を指定できるデータ構造が用意されていることがあり、言語によって連想配列、ハッシュ、マップ、辞書(ディクショナリ)など様々な名称で呼ばれる。

IT以外の分野では、論文などの文章中で参照すべき注釈の位置を記した番号や記号、数学のべき乗の指数や対数の底、化学式の原子の数などのように、文字の斜め上や下などに小さく添えられた数字や文字、記号、数式などが添字の一種である。

プログラミングの分野では、ソースコードのことを「プログラムリスト」「ソースリスト」などと呼び、これを略してリストということがある。

データ構造のリスト

基本的なデータ構造の一つで、複数のデータを順序を付けて格納することができる複合データ型(コンテナ/コレクション)をリストという。

中でも、各データが次のデータの所在を表す参照情報(リンク/ポインタ)を持っているものを「連結リスト」(linked list：リンクリスト/リンクトリスト)と呼び、これを略してリストという場合も多い。リストは他に動的配列などを用いても実装することができる。

連結リストの各要素はデータの他に自分の隣の要素を指し示す所在情報を持っている。これを辿ることで、各要素に順番にアクセスすることができる。各要素が自分の次(後)の要素への参照のみを持つ構造を「片方向リスト」「単方向リスト」と呼び、これに加えて自分の前の要素への参照をもつものを「双方向リスト」という。

また、先頭から末尾へ直線上に要素が連結されているものを「線形リスト」、先頭も末尾もなく要素が円環状に連結されているものを「循環リスト」という。

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

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

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

データの探索

何らかのデータ形式やデータ構造として集められたデータの集合に対して、一定の手順に基づいて指定の条件を満たすデータを探し出し、一致したデータやその位置を明らかにする(あるいは対象の中には存在しないことを確定させる)操作のことを「探索」(search)という。

探索アルゴリズム

コンピュータなどで実行できるよう定式化された探索手順のことを「探索アルゴリズム」(search algorithm)という。例えば、最も単純な方法として、一列に並べたデータ列に対して端から順に指定の条件に一致するか照合する方法がある。これを「線形探索」(linear search)という。

また、順位や大小が比較できるデータ群であれば、大きい順または小さい順に整列(並べ替え)して、目的のデータと半分の位置にあるデータを比較すれば、含まれる方の半分に絞り込むことができる。残ったデータ群の半分の位置と比較すれば、もう半分に絞り込める。これを繰り返して残りが一つになれば探索完了となる。この方法は「二分探索」(binary search)と呼ばれる。

線形探索では一回の比較で一つしか候補が減らないため、平均してデータの個数に比例した回数の比較が必要となる(これを $O\left(n\right)$ と表記する)が、二分探索ならば一回の比較で候補を半分に減らせるため、平均してデータの個数の2を底とした対数で済む(これを $O\left(\log n\right)$ と表記する)。

このように、探索する対象の特性に適したアルゴリズムを選択することで効率的に探索を行うことができる。文字列内の特定のパターンを探索するためのアルゴリズムや、木構造やグラフなどのデータ構造に格納された要素を探索するためのアルゴリズムなどがよく知られている。

検索との違い

ITの分野では「検索エンジン」「全文検索」のようにデータ群から条件に一致するものを探し出す操作を「検索」と呼ぶこともある。いずれも英語では “search” であり、意味や用法に明確な違いはないが、慣例として情報科学などの学問分野では「探索」の語が、探索法を応用した具体的なシステムやサービスなどでは「検索」の語が好まれる。

最も単純なアルゴリズムで、配列などに格納されたデータ列の中から、まず先頭の要素を探しているデータと比較する。一致しなければ2番目の要素と比較する。これを末尾の要素まで繰り返し、途中でデータを発見したらそこで探索を終了する。

N個のデータ列の中から線形探索する場合、最良のケースは先頭の要素と一致する場合で比較回数は1回、最悪のケースは末尾まで探してもデータが見つからなかった場合で比較はN回、平均の比較回数はN/2回となる。比較回数の平均値は要素数に正比例して増大する。

仕組みが単純なため短いプログラムコードで記述でき、コードを読んだ人が処理を理解しやすく、探索対象のデータ列以外に余分な記憶領域を消費せず、事前にデータ列のソート(大きい/小さい順に並べ直す処理)などの前処理を行う必要がないという利点がある。より高度なアルゴリズムに比べると平均の比較回数は多く、性能の高いアルゴリズムとは言えない。

まず、データを降順(大きい順)あるいは昇順(小さい順)に並べ替え、探索したいデータが中央の要素より大きいか小さいかを調べる。これにより、データが全体の前半分にあるか後ろ半分にあるかを判定することができるため、存在しない側の半分は探索範囲から外すことができる。

半分になったデータ群の中央の要素と再び比較し、前半と後半のどちらにあるかを調べる。この操作を繰り返し行うことで、一回の操作ごとに探索範囲の大きさが半分になっていき、中央の要素が求めるデータに一致するか、探索範囲の要素数が一つになる(求めるデータは見つからなかったことが確定する)と探索は終了する。

値の大小は文字の索引順の前後関係などに適宜置き換えることにより、順序と比較手段を定義できればどのようなデータにも適用することができる。

n個のデータ群から平均でlog₂n回の比較で探索を終えることができ、例えば1000個のデータを10回の比較で探索できる。原理は単純ながら高速なアルゴリズムである。ただし、要素があらかじめ整列済みである必要があるため、未整列のデータに適用するにはソートの分の計算時間も必要となる。

すべての要素について隣接する要素と大きさを比較し、並べたい順番と逆転していたら両者を入れ替える。この手順を最高で要素数-1回繰り返すと並べ替えが完了する。要素の入れ替えが発生しなくなった時点で処理を打ち切ってもよい。

一般的な実装では、この処理を列の一方の端から反対の端まで順番に行うことが多く、繰り返しの度に未整列の要素の中で最も大きな(あるいは小さな)要素が列の端に移動していく様子を泡(バブル)が浮き上がっていく様に例えてこのような名称となった。

最良の場合の計算時間は O(n) と高速だが、最悪の場合の計算時間は O(n²) と整列法の中でも最も遅い部類に入り、平均して高速な手法とは言えない。ただし、要素の比較・交換は順序を問わず並列化しやすいという特徴があり、並列分散処理が可能な環境では高速化することができる。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート(内部ソート)で、同じ大きさの要素の順序が入れ替わらない安定ソートである。アルゴリズムの理解や実装が容易で、コードの記述量が少ない。実用上はあまり使われないが、整列法の学習ではほぼ必ず取り上げられ、効率化した派生アルゴリズムも多く考案されている。

数値の列を先頭から小さい順(昇順)に並べる場合を考える。まず、先頭から末尾までの間で最も小さい値を見つけ、先頭の値と交換する。次に2番目から末尾までの間で最も小さい値を見つけ、2番目の値と交換する。

以降も同様に、「n番目から末尾までで最も小さい値を見つけ、n番目と入れ替える」という操作を繰り返す。これを末尾の一つ前の値まで繰り返せば、先頭が最も小さく末尾が最も大きい数値の列が得られる。

列の元の状態によらず O(n²) の計算量がかかるため処理時間の予測はしやすいが、ソートアルゴリズムの中では最も遅いものの一つに分類される。木構造の一種である二分ヒープ木を用いて改良した手法を「ヒープソート」(heap sort)という。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート(内部ソート)で、同じ大きさの要素の順序の維持は保証されない不安定ソートである。挿入ソートなどと同じように、アルゴリズムの理解や実装が容易なため、対象データ列が短いことが分かっている場合などに利用されることがある。

数値の列を先頭から小さい順(昇順)に並べる場合を考える。まず、先頭から2つの値を比較して小さい方を先頭に、大きい方を2番目に置く。次に3番目の値を取り出し、先頭・2番目と順に比較し、適切な位置に挿入する。

4番目以降も同様にして、n番目の値を取り出して先頭からn-1番目までと順番に比較し、適切な位置に挿入する操作を繰り返す。これを末尾の値まで繰り返せば、先頭が最も小さく末尾が最も大きい数値の列が得られる。

n番目の値を挿入する際、それが整列済みの列の中で最も小さければ先頭の値との1回の比較で挿入位置が決定できるが、最も大きければ整列済みの値の数(n-1回)だけ比較を繰り返さなければならない。

すなわち、要素が整列済みに近い状態ならば高速に整列を完了でき、最良計算時間はO(n)となるが、逆順に並んでいる場合は比較回数が爆発的に増大し、最悪計算時間は O(n²) となってしまう。この欠点をある程度緩和したアルゴリズムとして「シェルソート」(Shell sort)がある。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート(内部ソート)で、同じ大きさの要素の順序が維持される安定ソートである。アルゴリズムの理解や実装が容易なため、対象データ列が短いことが分かっている場合などに利用されることがある。人間に並べ替えを行わせると、多くの人がまっさきに自然に思いつく方法であるとも言われる。

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

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

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