高校「情報Ⅰ」単語帳 - 日本文教「情報Ⅰ」 - アルゴリズムとプログラミング

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

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

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

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

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

プログラミング言語やマークアップ言語でコードを記述するとき、すでに記述されたコードを完全に削除するのではなく一時的に無効化して試験などを行いたい場合がある。

そのような場合に当該箇所の前や後にコメント記法を追加してコメント化する(コードとして解釈・実行されなくなる)ことをコメントアウトという。コメント記法を取り除けば再びコードとして復活させることができる。

コメントの開始や終了を指示する記号の組み合わせなどは言語によって異なり、HTMLやXML系マークアップ言語では <-- と --> で囲んだ部分が、CSSやC言語系の記法を採用するプログラミング言語(Java、JavaScriptなど)では /* と */ で囲んだ部分(あるいは//から行末まで)がコメントとなる。

なお、通常はコードの一部をコメントとして外す(out)ことを指すが、注釈を書き入れるなど、本来の意味でコメントを記述することを含めてコメントアウトと呼ぶ人もいる。

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)などの分類がある。

プロセッサは設計段階でどのような命令番号(オペコード)が与えられたらどのように動作するかが決められている。機械語のプログラムは基本的に命令番号を実行順に並べたデータとなっており、個々の命令には必要に応じて処理すべき対象となるデータ(オペランド)などを付記する。

機械語はプロセッサに直接命令を与える言語であるため、プロセッサの持つすべての機能を利用することができる。どのようなプログラミング言語で記述されたプログラムであっても、ソフトウェアによる変換や調整を経て最終的には機械語のプログラムとしてプロセッサに渡され実行される。

ニーモニックとアセンブリ言語

人間が命令番号そのものを暗記して直にプログラムを記述するのは容易ではないため、各番号に意味を類推しやすいアルファベットの並び(ニーモニック)を一対一に対応付け、これを用いてプログラムを記述する手法が用いられる。このようにして作られたプログラミング言語をアセンブリ言語(assembly language)という。

アセンブリ言語によるプログラミングはハードウェアを直に制御でき、短く高速なプログラムを記述することができるが、大規模で複雑なプログラムや大人数での分業などには向いていない。OSやデバイスドライバなどハードウェアを直接的に制御する必要のあるプログラムや、極めてシビアに実行速度が求められる場面などで部分的に用いられることが多い。

命令セットとプログラムの互換性

命令番号と動作の対応関係、および各命令に付随するオペランドの形式などを定めた体系は命令セットアーキテクチャ(ISA：Instruction Set Architecture)あるいは単に命令セットと呼ばれ、同じ命令セットを持つプロセッサ間では互いに同じ機械語プログラムをそのまま実行することができる。

一般に、同じメーカーの同じ製品シリーズのプロセッサ製品間は同じ命令セットを共有し、新しい製品に新たな命令が追加されるようになっており、異なるモデルや世代の製品間でも同じ機械語プログラムを動作させることができる。異なるメーカーが同じ命令セットを実装した製品を開発する場合もあり、互換プロセッサなどと呼ばれる。

命令セットが異なるプロセッサ間では同じ機械語プログラムは動かないため、プログラムのソースコードからコンパイルなどの処理を行ってそのプロセッサの命令セットによって記述された機械語プログラムを生成する必要がある。

コンパイラ(compiler)はプログラミング言語で記述されたソースコードを解釈し、実行可能な機械語(マシン語)などのコードに一括して変換するソフトウェアで、変換後のコードを元に実行可能ファイルを作成して実行される。

記述したコードを実行に移すまでに手間や準備時間が必要だが、機械語への変換と実行が分離されるため、プログラムを少ない消費メモリで高速に実行でき、実行時にソースコードが不要(利用者へソースコードを提供しなくてよい)という特徴がある。

コンパイラ型言語は言語の開発元が提供する公式の処理系や、広く普及している主要な処理系がコンパイラであるような言語を指し、機械語コードへ変換しながら同時に実行する「インタプリタ型言語」(インタプリタ言語)と対比される。

このような分類は現代よりもプログラミング言語とその処理系が密接に関連付けられていた1990年代以前によく用いられたが、インタプリタとコンパイラのどちらを用いるかは言語そのものの特性ではなく、実際、今日では一つの言語に両者が標準的に提供されることも少なくないため、このような分類を用いることはほとんどなくなった。

インタプリタ(interpreter)はプログラミング言語で記述されたソースコードを解釈し、実行可能な機械語(マシン語)のコードに変換しながら同時に実行するソフトウェアで、変換処理の分だけ消費メモリ容量や実行速度は犠牲になるが、ソースコードを与えるだけで即座に実行できるという特徴がある。

インタプリタ型言語は言語の開発元が提供する公式の処理系や、広く普及している主要な処理系がインタプリタであるような言語を指し、機械語コードへの変換を一括して行い、実行可能ファイルを生成してから実行する「コンパイラ型言語」(コンパイラ言語)と対比される。現代では、いわゆるスクリプト言語が該当する。

このような分類は現代よりもプログラミング言語とその処理系が密接に関連付けられていた1990年代以前によく用いられたが、インタプリタとコンパイラのどちらを用いるかは言語そのものの特性ではなく、実際、今日では一つの言語に両者が標準的に提供されることも少なくないため、このような分類を用いることはほとんどなくなった。

主な特徴

C言語やJavaに似た記法や文法を採用した手続き型の言語で、簡潔な記述でプログラムを開発することができる。関数を変数のように(第一級のオブジェクトとして)扱ったり、関数を引数に取る高階関数を定義できるなど、関数型プログラミング言語の仕様も取り込んでいる。

オブジェクト指向にも対応しているが、他の多くの言語で一般的な、オブジェクトの雛形を定義したクラスを用いる方式(クラスベース)ではなく、既存のオブジェクトを複製して機能を追加していく「プロトタイプベース」と呼ばれる手法を採用している。

Webブラウザでの利用

WebページのHTMLファイル内に特殊な記法を用いて埋め込まれて記述され、Webブラウザに内蔵された言語処理系によってページの表示時に解釈・実行されることが多い。スクリプトのみを記述したファイル(.jsファイル)を読み込む形で利用されることもある。ページ内の要素に動きや効果を加えたり、閲覧者の操作に即座に反応して何らかの処理を行ったりするのに用いられる。

主要なWebブラウザの多くが標準で対応しているが、ブラウザの種類やバージョンによって仕様や挙動に違いがあり、開発者を悩ませ続けている。他の言語の場合にも見られる言語そのものの仕様・実装の違い(バージョンの違いや各社独自の拡張や仕様・実装の相違)の他に、HTMLやCSSの仕様や解釈の相違や、スクリプトからWebページ上の表示要素を扱う際に必要となるDOM(Document Object Model)と呼ばれるAPIの違いもあるため、複数のブラウザで同じように動作するスクリプトを開発するのは一筋縄ではいかない。

他の実行環境

近年ではWebブラウザに留まらず様々な環境に言語処理系が移植され、様々な用途で使用されている。Node.jsやASP.NETのようにWebサーバ上でプログラムを実行して動的にWebブラウザに応答を返すシステムや、オペレーティングシステム(OS)上で直に実行可能な処理系(Windows Scripting Hostなど)がよく知られる。米アドビ(Adobe)社の「Flash」では標準のスクリプト言語に採用されていた(正確にはActionScriptと呼ばれる方言)。

AltJS

開発効率や保守性、プログラムの読みやすさなどの改善、よく起こりがちな誤りの防止などを目的に、JavaScriptを元に独自の機能や仕様を追加したり、文法や記法の追加・変更を行った言語がいくつか開発されており、「AltJS」(Alternative JavaScript)と総称される。

これらの言語で書かれたプログラムは「トランスパイラ」(transpiler：トランスコンパイラの略)と呼ばれる変換ソフトにより一旦JavaScriptによる表記に変換されるため、JavaScriptの実行環境さえあれば通常のスクリプトと同じように実行できる。著名なものには「TypeScript」や「JSX」、「CoffeeScript」などがあり、Webアプリケーションの開発現場などでよく利用される。

Javaとの違い

名称にプログラミング言語「Java」の語を冠しているが、他の「Java○○」技術とは異なり、Java言語の拡張仕様や関連技術などではなく、記法や予約語などの一部が共通していること以外に直接的な繋がり互換性はない。

実際、型システムや関数、オブジェクト指向の扱いなど言語仕様の根本的な部分のいくつかがJavaとは大きく異なる。かつてはJavaにもWebページ内にプログラムを埋め込んで実行する「Javaアプレット」と呼ばれる仕組みがあったため、主に技術者以外のWebに携わる人々にとって名称が紛らわしく、しばしば混同や取り違えが発生した。

歴史

1995年にネットスケープ・コミュニケーションズ(Netscape Communications)社(当時)のブランダン・アイク(Brendan Eich)氏によって開発され、当時最も人気の高いWebブラウザだった「Netscape Navigator 2.0」に初めて実装された。

当初は「LiveScript」(ライブスクリプト)という名称だったが、同社がJava開発元のサン・マイクロシステムズ(Sun Microsystems)社(当時)と提携していたことから、Javaの名称を冠してJavaScriptに改称された。

1997年にはEcma International(エクマ・インターナショナル)によって「ECMAScript」の名称で仕様が標準化され、ISOやJISなども同様の規格を標準化した。ECMAScriptは20年以上に渡って活発に改版を重ねており、各社の処理系もこれに準拠する形で機能追加が進められている。

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

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

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

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

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

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

ITの分野では、ある特定の機能を持ったコンピュータプログラムを他のプログラムから呼び出して利用できるように部品化し、そのようなプログラム部品を複数集めて一つのファイルに収納したものをライブラリということが多い。

一般的に、ライブラリにはオブジェクトコード(機械語などで記述された実行可能形式のプログラム)が格納されているが、それ単体で起動して実行することはできず、他の実行可能ファイルに連結されて利用される。言語や処理系によってはソースコードの集合をライブラリという場合もある。

様々なプログラムが共通して利用する汎用性の高い機能などがライブラリとして開発・提供されることが多く、標準的なライブラリはオペレーティングシステム(OS)やプログラミング言語の開発環境、開発ツールなどの一部として付属することが多い。

特定のソフトウェアやハードウェアを利用したプログラムを開発するために必要な機能がライブラリの形でまとめられている場合もあり、当該システムのソフトウェア開発キット(SDK)などの一部として開発者に提供される。

また、部品化されたコンピュータプログラム以外にも、特定の分野や形式のデータなどを検索、取得、再利用しやすい形にまとめたファイルやデータベース、Webサイトなどのことを「フォトライブラリ」「音声ライブラリ」などといったように呼ぶことがある。

個々のソフトウェアの開発者が毎回すべての機能をゼロから開発するのは困難で無駄なため、多くのソフトウェアが共通して利用する機能は、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」という処理を実行すると、数値計算のコードが適用されて「2」という結果が得られるが、文字列型の値について「"1"+"1"」という処理を実施すると、文字列の連結処理が適用されて「"11"」という結果が得られる。

整数を文字列で除算しようとするなど、型が不整合な処理はエラーとなる。"1"という文字列型の値を1という整数型の値に変換するなど、異なる型へ一定のルールに基づいて変換することを「型変換」あるいは「型キャスト」(type casting)という。

プリミティブ型と複合型

様々なデータ型のうち、それ以上要素に分解できない最小単位のデータを格納する最も基本的なデータ型を「単純データ型」「プリミティブデータ型」などという。

言語によって用意されている単純型の種類は異なるが、文字型や文字列型、整数型、浮動小数点数型(あるいは固定小数点数型や実数型)、論理型(ブーリアン型)、日付・時刻型、バイナリ型などが用意されていることが多い。

ポインタ型や参照型などメモリ上の位置を格納する型や、関数型などプログラムをデータのように扱う型、データが「無い」ことを明示するvoid型など、特殊な型が用意されている言語もある。

浮動小数点数型に単精度や倍精度など異なる精度の型が用意されていたり、整数型がバイト長や符号の有無(負数を表現できるか否か)でいくつかの種類に分かれているなど、データの種類が同じでも仕様が異なる複数の型に分かれている場合もある。

一方、複数のデータ型を組み合わて定義された型や、複数の要素からなるデータ構造を格納するためのデータ型を「複合データ型」(complex type)という。配列や連想配列(ハッシュ、マップ、辞書)、リスト、タプル、集合型(セット)、列挙型などがこれに当たる。

組み込み型とユーザー定義型

言語仕様や標準ライブラリなどにあらかじめ用意されているデータ型を「組み込みデータ型」(ビルトインデータ型)、開発者が独自に定義したものを「ユーザー定義データ型」(user-defined type)という。

組み込み型は言語処理系が標準的に扱うことができ、演算子による演算を行ったり、基本的な操作や処理を行うための関数やメソッドが標準で提供されることが多い。

ユーザー定義型は単に既存の組み込みデータ型に別名を与えられるだけの場合もあるが、様々なデータ型を組み合わせた複合データ型を独自に定義できる機能を指すことが多い。演算子の処理内容を独自に定義(上書き)して、ユーザー定義型の値に対しても演算子を適用できる言語もある。

型宣言と型付け

プログラムの開発者がそれぞれの変数などのデータ型をプログラム上に明示することを「型宣言」(type statement)という。コード中で使用する変数などについて必ず事前に型宣言しなければならない言語と、型宣言しなくても変数などを使ってよい言語がある。

プログラムの実行前、ソースコードの記述やコンパイルの時点で型が決定されることを「静的型付け」(static typing)、実行時に実際の値に基づいて型が決定されることを「動的型付け」(dynamic typing)という。

型宣言が不要な言語の多くは動的型付けを採用しているが、「型推論」(type inference)機能により内部的に静的型付けを自動的に行う仕組みの言語もある。

文字を表す文字コードを連ねた文字列データを格納する型で、予め格納できる文字列の長さを指定する固定長文字列型(fixed length string)と、任意の長さの文字列を格納できる可変長文字列型(variable length string)がある。言語や処理系によっては一方しか無い場合もある。

古い言語や処理系ではASCII文字(いわゆる半角英数字・記号)しか格納できない仕様のものもあるが、近年ではUnicodeなどで表現さrた多バイト文字(漢字など)をそのまま格納できるようになっているものが多い。

一文字分の文字コードを格納するためのデータ型として文字型(character type)が用意されているC言語/C++言語などでは、組み込みデータ型としての文字列型が無く、文字型のデータの配列などの形で文字列を格納する。

どのくらいの長さのデータで一つの整数を表現するかによって表現できる値の範囲が異なる。例えば16ビット(2バイト)符号なし整数型であれば、0から65,535(2¹⁶-1)までの間に含まれる整数値を表現できる。

多くの言語では、“int” や “Integer” などの型名で示される整数型が16ビットあるいは32ビットを表し、8ビットや16ビットは “short” などの型名や修飾子で、32ビットや64ビットは “long” などで表されることが多い。言語によっては8ビットの任意のビット列を格納する “char” や “byte” などの型が用意されており、8ビット長の整数型としても利用できる。

C言語の場合は処理系によってshort、int、longの長さが異なるが、規格上はint16_tのようにビット長を明示した型名も用意されている。同じように “Int64” といった長さが明記されたデータ型を用いる言語もある。

符号付きと符号なし

扱う値の範囲の違いにより、0と正の整数のみを格納できる符号なし整数型(unsigned integer)と、負の整数も格納できる符号付き整数型(signed integer)が選択できる場合がある。

符号付き整数は最上位ビットが正負の符号を表しており、表現できる値の幅は符号なしと同じだが、絶対値の上限は半分となる。例えば、16ビット符号なし整数の範囲は 0～65,535 だが、16ビット符号付き整数の範囲は -32,768～32,767 となる。

浮動小数点型では、数値の正負を表す「符号部」、数値を2進数で表したときの各桁の数字の並びである「仮数部」、小数点の位置を表す「指数部」の組み合わせで値を表現する。仮数に基数(通常は2)を指数乗した値を乗じ、符号を付け加えたものが表現する数値となる。

例えば、「-4.375」は2進数では「-100.011」であり、仮数と指数に分離すると「-1.00011×10¹⁰」(値はすべて2進表記)となる。符号は正を0、負を1とすることが多いため、符号部の値は「1」、仮数部の値は「100011」、指数部の値は「10」となる。数値が0の場合は符号と指数は不定となるが、便宜上各部をすべて0としたもの(+0.0×10⁰)を0の表現として扱うことが多い。

格納できる値の範囲は整数型とは異なり、表現可能な桁の長さ(有効数字)と、数の大きさそのもの(指数部の大きさ)がそれぞれ独立に決まっている。例えば、一般的な仕様の単精度浮動小数点数型は、十進数に換算して概ね10の38乗程度までの絶対値の数を表すことができるが、このうち各桁の数字を正確に表せるのは上位6桁程度である。

IEEE 754形式

浮動小数点型には全体のデータ長や仮数部と指数部のビット数の配分などで様々な形式が存在するが、広く普及している標準規格としてIEEE 754形式が知られる。

全体で16ビット(符号1+指数5+仮数10)の「半精度浮動小数点数型」、32ビット(符号1+指数8+仮数23)の「単精度浮動小数点数型」、64ビット(符号1+指数11+仮数52)の「倍精度浮動小数点数型」、128ビット(符号1+指数15+仮数112)の「四倍精度浮動小数点数型」の4つの形式が定められており、それぞれ表現できる数値の幅の異なる。

実用上は単精度と倍精度がよく用いられ、プログラミング言語や論理回路などでもこの2つに標準で対応しているものが多い。例えば、C言語系の言語では単精度を「float」、倍精度を「double」という型名で表す。

プログラミング言語では言語仕様などで様々な演算子が定義されており、これを組み合わせて式や命令文を構成することができる。対象となる被演算子の数によって、「a++」のように一つしか取らないものを「単項演算子」(unary operator)、「a+b」のように二つのものを「二項演算子」(binary operator)、「c?x:y」のように三つのものを「三項演算子」(ternary opeator)、任意個の被演算子を列挙できるものを「多項演算子」(n-ary operator)という。

演算子は演算の内容によっても分類でき、「a-b」「x/10」のように四則演算などの算術的な計算を記述する「算術演算子」(arithmetic operator)、「a>b」「x==y」のように二項の比較や関係を表す「比較演算子」(comparison operator)あるいは「関係演算子」(relational operator)、「a&&b」「x||y」のように論理演算を行う「論理演算子」(logic operator)などがある。

多くの言語では演算子は言語仕様で定義されており開発者が任意に追加、削除、変更することはできないが、言語によってはコード中で独自の演算子を定義して利用することができたり、既存の演算子に別の演算内容を割り当てる「多重定義」(オーバーロード)ができる場合もある。

プログラミング言語などにも命題の真偽を表す仕組みや表記法が用意されていることがあり、真理値あるいはブール値(boolean value)などと呼ぶ。条件式や論理演算(ブール演算)の結果を表すことができ、真理値を表すことができるデータ型を論理型、ブーリアン型(ブール型)などという。

リテラルの表記は言語によって異なるが、真は「true」「True」「TRUE」などと、偽は「false」「False」「FALSE」などと表記することが多い。真理値に相当する値を整数で代用し、0が偽、0以外が真とする言語や処理系もある。

電子回路などの場合には、真理値を1ビットの値の0と1に対応付け、電流のオンとオフ、電圧の高低、電荷の有無などの物理量で表す。デジタル信号の1を真、0を偽に対応付けるのが一般的。

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

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

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

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

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

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

プログラム上で関連する一連の命令群を一つのかたまりとしてまとめ、外部から呼び出せるようにしたサブルーチンやプロシージャ(手続き)の一種である。呼び出し時に引数(ひきすう/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型関数のように、明示的に何も返さないよう指定できる言語もある。

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

複数のデータの配置や関係性、データの参照や出し入れなどの操作のルールを定義したもので、様々な種類がある。それぞれに特徴や適した処理があるため、同じ処理の記述でも、目的に対して適切なデータ構造を選択できるかどうかでプログラムの複雑さや処理性能に大きな差がつくことがある。

データ構造の種類

最も基本的なデータ構造には、要素を一列に並べた「配列」(array)、要素を格納した順に取り出すことができる「キュー」(queue)、格納したのとは逆順に取り出すことができる「スタック」(stack)などがある。

格納された要素への参照データを含むデータ構造もあり、任意の標識と要素を一対一に関連付けて格納する「連想配列」(辞書、ハッシュ、マップとも呼ばれる)、要素が前後の要素への参照を持つ「連結リスト」(linked list)、要素が任意個の他の要素への参照を持つ「グラフ」(graph)、一つの頂点から樹状に枝分かれしたグラフである「木構造」(ツリー構造)などがある。

これらには細部の仕様が異なるバリエーションがある。例えば、連結リストには前の要素が後の要素への参照を持つだけの「片方向リスト」(単方向リスト)、これに加えて後の要素が前の要素への参照も持つ「双方向リスト」、要素が環状に連なっている「循環リスト」などいくつかの種類がある。

言語上の扱い

プログラミング言語では、基本的なデータ構造のいくつかが言語仕様や標準ライブラリなどにあらかじめ組み込まれて提供されていることが多い。用意されていない場合でも、既存のデータ構造や複合データ型、クラスなどの仕様を利用して開発者がデータ構造の定義や挙動の実装を行うことがある。

実際のプログラム上では基本的なデータ構造を単体で用いることも多いが、あるデータ構造の要素として別のデータ構造を格納するなど、アルゴリズムに合わせて組み合わせて用いる場合もある。

配列はほとんどのプログラミング言語に存在する最も基本的なデータ構造の一つで、単純に変数を一列に並べたものである。データ全体はコード中で配列名で指し示され、各要素は通し番号などの添字で区別される。例えば、長さ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以外の分野では、論文などの文章中で参照すべき注釈の位置を記した番号や記号、数学のべき乗の指数や対数の底、化学式の原子の数などのように、文字の斜め上や下などに小さく添えられた数字や文字、記号、数式などが添字の一種である。

配列(array)は多くのプログラミング言語に用意されている基本的なデータ構造の一つで、単純に複数のデータを一列に並べたものである。コード中で配列は配列名で参照され、配列内の各要素は添字(インデックス)によって識別される。

配列の要素に配列が格納されており、配列が入れ子状になったデータ構造を扱うことができる言語もあり、これを「多次元配列」という。例えば、配列の要素が配列になっており、その要素は値であるような2段階の入れ子構造を「2次元配列」と呼ぶ。

「1次元配列」という呼称はこのような入れ子状の配列と対比して、単に値が並んでいるだけの単純な配列のことを指す。注釈なく単に「配列」という場合は通常は1次元配列のことを意味することが多い。

配列(array)は多くのプログラミング言語に用意されている基本的なデータ構造の一つで、単純に複数のデータを一列に並べたものである。コード中で配列は配列名で参照され、配列内の各要素は添字(インデックス)と呼ばれる番号で識別される。

配列の要素が配列に、さらにその要素が配列に…という具合に入れ子構造になっている「配列の配列」を「多次元配列」(multidimensional array)という。2次元配列はその最も基本的な構造で、配列の要素が配列になっており、その要素に個々の値が格納されている。

例えば、C言語やその記法を受け継ぐ言語で整数型の配列aを int a=[2][3]; のように宣言すると、a[0]やa[1]は通常の配列とは異なりそれ自体が配列となっている。その配列の要素が値であるため、値にアクセスするには「a[0][0]」(1番目の配列の1番目の要素)、「a[1][2]」(2番目の配列の3番目の要素)のように添字を2つ指定する。

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

データ構造のリスト

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

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

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

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

キューは先頭が常に最も古い要素になるデータ構造で、新しい要素は必ず末尾に追加される。取り出すときは常に先頭の最も古い要素から取り出される。このように先に入れたものほど先に取り出される管理方式を「FIFO」(First-In First-Out：先入れ先出し)という。

実装上は、キューのために確保された記憶領域の中ですべての要素が到着順に並ぶとは限らず、実際の位置や順序とは別に到着順や末尾の位置などの情報を内部的に記録・管理する手法が用いられることが多い。人間の行列のように要素が取り出されるたびに残りのすべての要素の物理的な位置を隣(一つ前)に移動させるのは非効率だからである。

バリエーションとして、列の両端から要素の追加や取り出しを行える「両端キュー」(double-ended queue)や、追加する要素に優先度を設定して、優先度の高いものから取り出すようにする「優先度付きキュー」(priority queue)などがある。

一方、「先に足された要素ほど後に取り出される」(末尾から順に取り出す)という規則で要素の出し入れを管理するデータ構造は「スタック」(stack)と呼ばれる。そのような管理方式を「LIFO」(Last-In First-Out：後入れ先出し)あるいは「FILO」(First-In Last-Out：先入れ後出し)という。

要素の出し入れ

キューに要素を追加する操作を「エンキュー」(enqueue)、取り出す操作を「デキュー」(dequeue)という。エンキューされた要素はキューの末尾に追加され、キューの要素数は1増加する。

デキューを指示するとキューの先頭の要素が取り出され、その要素はキューから取り除かれる。先頭から2番目にあった要素(2番目に古かったデータ)が新しい先頭になり、キューの要素数は1減少する。

キューイング (queuing/queueing)

キューを用いて要素の管理を行うことを「キューイング」(queuing)という。キューイングは機器間やプログラム間など独立に動作する二つの主体の間で非同期にデータの受け渡しを行う手法としてよく用いられる。システム間で汎用的にデータを受け渡しするシステムを「メッセージキュー」(message queue)という。

例えば、コンピュータからプリンタにデータを伝送する速度とプリンタがデータを紙に印刷する速度では、後者のほうが圧倒的に遅い。伝送と印刷を同時に行おうとするとコンピュータ側はほとんどの時間待たされることになり無駄であるため、印刷データを一旦キューに保管し、プリンタの処理の進み具合に応じて専用の制御プログラムが少しずつデータを伝送する手法が用いられる。

スタックは要素が入ってきた順に並べ、先頭が最も古く、末尾が最も新しい要素となる。取り出すときは末尾にある最も新しいものから順に取り出す。このように後に入れたものほど先に取り出される管理方式を「LIFO」(Last-In First-Out/後入れ先出し)あるいは「FILO」(First-In Last-Out/先入れ後出し)という。

ほとんどのマイクロプロセッサにはメモリ領域に設けたスタックを操作するための機械語の命令やレジスタなどを内蔵しており、機械語のプログラムの実行制御などで非常によく用いられるデータ構造として知られる。特に、サブルーチンや関数を呼び出す際に処理中のデータや戻りアドレスなどを一時的に退避するコールスタック(実行スタック)のことを単にスタックと呼ぶ場合もある。

一方、先に追加した要素ほど先に取り出される(先頭から順に取り出す)規則で要素の出し入れを管理するデータ構造は「キュー」(queue)あるいは「待ち行列」と呼ばれる。

プッシュ/ポップ (push/pop)

スタックに要素を追加する操作を「プッシュ」(push)、取り出す操作を「ポップ」(pop)という。プッシュされた要素はスタックの末尾に追加され、スタックの要素数は1増加する。

ポップを指示するとスタックの末尾の要素が取り出され、その要素はスタックから取り除かれる。末尾から2番目にあった要素(2番目に新しかった要素)が新しい末尾となり、スタックの要素数は1減少する。

プログラミング言語などによっては、この2つの操作に加え、末尾あるいは指定位置の要素を取り出さずに値を読み込む「ピーク」(peek)、末尾あるいは指定位置の値を書き換える「ポーク」(poke)といった操作を提供している場合もある。

プロトコルスタック/ソフトウェアスタック

ネットワークプロトコル(通信規約)やソフトウェアは物理的な装置や回線に近い部分から利用者に近いものまで、役割に応じて階層構造に分かれていることが多い。

このとき、互いに相互運用性のあるプロトコルやソフトウェアを積み重ね、全体として一つのシステムや機能を実現したものをプロトコルスタック、ソフトウェアスタックなどということがある。

例えばプロトコルであれば、物理層からアプリケーション層まで、UTPケーブル - Ethernet - IP(Internet Protocol) - TCP(Transmission Control Protocol) - HTTP(Hypertext Transfer Protocol)といったように積み上げた各階層の機能が互いに連携しあって通信が可能となる。

専門知識や技能のスタック

ある事業や業務に必要な専門的な知識や技能の総体を、プロトコルやソフトウェアになぞらえて階層状に整理したものをスタックと呼ぶことがある。

階層の積み上げ方は分野によって異なり、ソフトウェアのようにハードウェア寄りから利用者寄りへ重ねていく場合と、企画-設計-実装-…といったように工程の前後関係に基づいて整理する考え方がある。

特に、ある事業分野に必要なすべてのスキルを一人で備え、すべて遂行することができる技術者のことを「フルスタックエンジニア」(英語では “full stack developer”)という。

例えば、Webサービスを開発・提供する場合に、通常はそれぞれの専門的なスタッフや部門で分業される、企画、設計、ページやユーザーインターフェースのデザイン、画像制作、HTML/CSSコーディング、サーバ側(バックエンド)プログラミング、クライアント側(フロントエンド)プログラミング、テスト、機材や回線の調達・導入、ネットワーク設定、サーバ管理、システム運用、プロモーション、利用者サポートなどを一人でできる人材のことをフルスタックであるという。

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

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

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

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

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

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