🐥プログラミング基礎概念

プログラミング基礎概念まとめ

各言語の抽象としての基礎概念をまとめてていく.

💻プログラム

計算機科学におけるプログラム. パラダイムによって定義がことなる.

• 命令型パラダイム
  • コンピュータが行うべき命令の列(a sequence of executing instruction).
• オブジェクト指向型パラダイム
  • オブジェクトとメッセージング
• 関数型パラダイム
  • 関数そのもの

ref. プログラム (コンピュータ) - Wikipedia

SICP より

プロセスは計算機のなかに潜む抽象的な存在.

プロセスはもう一つの抽象的な存在, データを操作する.

プロセスの進行は, 規則のパターン, プログラムにしたがう.

プログラムは二つの要素をもつ.

• 手続き: データの処理方法(能動的)
• データ: 処理したいもの(受動的)

📝式(Expression)

計算機の解釈系に渡される前の表現. 解釈系に評価されると, 式はプロセスになる.

ref: 式 (プログラミング) - Wikipedia

言語によって定められた優先順位や結びつきの規定に則って評価される値, 変数, 演算子, 関数の組み合わせ.

📝プロセス(計算機科学)

プロセスは計算機のなかに潜む抽象的な存在. プロセスはもう一つの抽象的な存在, データを操作する. プロセスの進行は, 規則のパターン, プログラムにしたがう.

プログラムに必要な資源のこと. プログラム自体, データ, スタック, カウンタ, スタックポインタ, レジスタ, メモリなど.

3 つの状態 (Run, Blocked, Ready) を持つ. 複数のプロセスを仮想的に並列に実行するものがプロセッサ.

• 📝プロセス(OS)
• 📝経験我

📝リテラル(literal)

即値 (英: Immediate) ともいい, ソースコード内に値を直接表記したもの.

ref: リテラル - Wikipedia

静的に構文解析が可能なことが多い. 変数の対義語. 変更されない値.

📝変数(valuables)

変数の構成要素は以下の 2 つ.

• 識別子 (Identifier)
• 格納域実体 (Store entity)

x = 1 ということはどういうことかを説明する概念.

数学的な写像関係で x = 1 を説明しようとしている. { X -> x1=1 }みたいな感じ. x1 がメモリ上の実際の (束縛された) 値で, X がそれを指し示す識別子.

📝Identifiers

識別子 (Identifier)

📝Store Entity

格納域実体 (Store entity)

📝Environments

識別子と変数の写像関係を環境という.

• a collection of (symbol, value) pair.
• environment has a parent environment, possible to have multiple children.
• a function + an environment = a closure

Global Environments

どこからでも参照できる environments.

top environment, すべての親となる environments.

📝可変性(mutable)

📝不変性(immutable)の対義語. 時間とともに変化する性質.

📝不変性(immutable)

不変性. 一度値をセット(束縛)したらあとから変更できないということ.

破壊的変更が起きないともいう. データが変わる心配が不要.

📝永続性(persistent)

永続性. データを変更する際に変更前のバージョンを常に保持するデータ構造の性質. 永続データ構造と訳される.

ref: 永続データ構造 - Wikipedia

• note: deep copy vs shallow copy
• Clojure is immutable and persistent

Single-Assignment Store

単一代入格納域.

一度一つの値を束縛したら変更できない変数の集合. 定数.

関数型プログラミングでは, この変数が当たり前.

📝変数束縛

bindings, 束縛.

📝Unbound Value

メモリ上に値が存在しないが, 宣言された変数.

日本語は何だろう, 未定義変数?

• C/C++ では, ゴミ (不定データ) が格納されている.
• Java は 0 初期化されている.
• Prolog は実行時にエラー終了する.
• Oz は値が bind されるまでまちあわせる.

📝データフロー変数

DataFlow Value.

📝Unbound Value が束縛されるまでプログラムの実行を待ち合わせるような宣言的変数.

束縛されたときの実行を データフロー実行(Dataflow Execution)という.

あるスレッドがデータフロー変数を利用しようとしたとき, その変数に値が束縛されていない場合は, 別のスレッドが束縛するまで待ち合わせを行う.

このデータフロー変数によって, No Race Conditions (非競合状態) を実現すると並行プログラミングはとてもシンプルになる.

• refs.
  • 📝決定性データフロープログラミング
  • 💡Clojureのpromise/deliverはデータフロー変数のこと
  • データフロー変数 (Oz) で実現する Producer-Consumer Pattern | Futurismo

📝スコープ(Scope)

Valiable の有効範囲.

ref: スコープ - Wikipedia

Scoping Rules - スコープの範囲

📝静的スコープ(Lexical Scope)

refs: 静的スコープ - Wikipedia

変数はブロックの内側のみ有効.

Lexical Scope, Static Scope とも. 字句的スコープともいう.

free valuables are searched for in the environment in which the funcition was defined.

ブロック構造 (block Structure)

手続きの仮引数は局所的である. 関数の定義は局所的でない.

手続きをブラックボックスにするためには, 利用者に必要のない関数は隠蔽する必要がある.

定義の入れ子を ブロック構造 という. ブロック構造の中で定義された関数は局所的である.

できるだけブロックを利用することで巨大問題を, 扱える部品に分割できる.

SICP p17 より.

R example

Scope の外への戻り値は, Scope 内部の関数のコピーである.

# from R Programming coursera.
make.power <- function (n) {
    pow <- function (x) { x^n }
    pow
}
 
cube <- make.power (3)
square <- make.power (2)

📝動的スコープ(Dynamic Scope)

📝Emacs Lisp は ダイナミックスコープを採用している.

Emacs Lisp は, アプリケーション・プログラミングで使われる方言群である Scheme や Common Lisp とは根本的に異なる. 大きな違いの 1 つは, デフォルトで字句的スコープではなく動的スコープを使うことである. つまり, 呼出し関数の局所変数は, ポインタや参照を渡さなくとも, 呼び出された関数から参照できる.

• 動的スコープ - Wikipedia
• Emacs Lisp - Wikipedia
• レキシカルスコープとダイナミックスコープ | すぐに忘れる脳みそのためのメモ

📝状態(計算機科学)

State (状態) とは, 必要とされる計算の途中結果を含む, 値の時系列.

sequence of values calculated progressively, which contains the intermediate results of a computation.

状態の導入によって, プログラムに時間の概念を与える.

• 📝ソフトウェア状態管理概論
• 🔖状態

📝宣言的状態(Implicate State)

暗黙的状態. 宣言的状態. Stateless, declarative Stateともいう.

• 関数の実行結果が値をもつ

• 同じ入力には必ず同じ出力を返す.

• 📝参照透過性(Referential Transparency)

• 🔖declarative

📝明示的状態(Explicite State)

明示的状態, Explicite State. Stateful.

• 生存期間が 2 度以上の手続的呼び出しに渡るような一つの状態.
• 関数の実行の中に値をもつ.
• 手続きの引数に現れないもの.

同様なことを関数型パラダイムで実現するためには, 仮引数に状態を持たないといけない.

• cf. 📝宣言的状態(Implicate State)
• 🔖状態

Cell

Explicite State (明示的状態) を表す基本型. 二つの構成要素からなる.

• 名前値 (Vaiue)
• 単一代入格納域への参照 (Identifier)

declare
fun {Reverse L}
   % 空リストの cell を生成
   Rs = {NewCell nil}
in
   % リストの各要素を取り出して内部 Cell に結合
   for X in L do
      Rs := X|@Rs
   end
 
   % 内部セルをリターンする.
   % Ruby っぽい!
   @Rs
end
 
{Show {Reverse [1 2 3 4]}}

🔖モジュール性

ある部分を変更しても別の部分には変更が加わらないとき, それをモジュール性という.

Function Paradium ではできない. State があればできる.

📝同一実体(identity)

時間が経過して値が変化してもそれを指し示すものは変わらない参照.

📝評価戦略(Evaluation Strategy)

評価戦略. Substitutonal Rule (代入規則) とも.

プログラミング言語やラムダ計算のような式から成る計算模型において, 如何なる手順で, 評価すなわち式から値を得るか, という (通常決定的な) 規則群.

ref: 評価戦略 - Wikipedia

• Call-by-Name (名前呼び)
• Call-by-Value (値呼び)
• Call-by-Ref (参照呼び)

📝遅延評価(Lazy Evaluation)

値が必要になるまで式の評価を遅らせる評価戦略. 必要呼び(call-by-need)ともいう.

実際の評価が行われていない状態は プロミス(promise)やサンク(thunk)といい強制(force)することで値が計算される(このへんは各言語によって名称が異なる).

遅延評価のメリットは 計算量の最適化 である.

• 計算コストが高価なときは余分な計算をしなくて済む.
• メモリに乗らない大きなデータも扱える.
• I/Oを本当に必要になるときまで遅らせる.

言語で遅延評価がサポートされていて開発者が特別な意識をすることなく遅延評価ができるならばほとんどの場合使ったほうがいい(とClojure界隈でいってた).

---

• refs.
  • 遅延評価 - Wikipedia
  • Clojure: 遅延評価(Laziness Evaluation)
  • Clojure: 遅延シーケンス

Eager Evaluatin: 先行評価

Lazy Evaluation: 遅延評価 の対義語.

普通のことなのであまり話題に上がることがない.

Haskell

2 つの評価方法がありどちらを選択しても最後の結果が変わらないという性質がある.

• InnterMost Reduction: 最内簡約
  • 内側から評価する.
  • 評価対象が複数ある場合は, 左から評価する.
• OuterMost Reduction: 最外簡約
  • 外側から評価する.
  • 評価対象が複数ある場合は, 左から評価する.

SICP より

• 正規順序 (normal-order evaluation)
  1. 演算子と非演算子を評価.
  2. 演算子評価結果の手続きを非演算子評価結果の引数に作用させる.
• 作用素的順序 (applicative-order evaluation)
  • その値が必要になるまで, 非演算子を評価しない. 遅延評価??

📝糖衣構文(SyntaxSuger)

プログラミング言語において, 読み書きのしやすさのために導入される構文であり, 既に定義されている他の構文の (人間にとってより理解しやすい)書換えとして定義されるもののこと.

ref: 糖衣構文 - Wikipedia

📝関数(計算機科学)

関数(Function). パラダイムによって呼び方や定義が異なる.

• 手続き型: 📝プロシージャ(procedure)
• オブジェクト指向: 📝メソッド(methods)
• 関数型: 📝関数(Function)

大事なことは, 一般的には入力に対して同じ出力を出すというものが関数とよばれているが, それは数学や📝関数型プログラミングというパラダイムにおける📝ラムダ抽象を言っているが, たとえば手続き型のパラダイムでは関数とはルーチンであり, パラダイムによって関数の意味合いがことなること.

CTMCP での定義

Procedure is a procedure value with a contextual environment.

Since procedures (and functions) are values, we can pass them as inputs to other functions and return them as outputs.

SICPでの定義

• Processs (プロセス)
  • 計算機のなかに潜む抽象的な存在.
• Procedure (手続き・プロシージャ)
  • データの処理方法.

データにたいして繰り返しで処理をおこなう方法には, 再帰的処理と反復的処理がある.

Recursive: 再帰的

計算を実行するためには, 以前の計算結果を覚えておく必要がある. 計算効率と空間効率は x の大きさに比例する.

これを, 線形再帰プロセスという.

;; applicative-order evaluation
;; linier recursion
(defun plus (x y)
  (if (= x 0)
      y
    (1+ (+ (1- x) y))))

Iterative: 反復的

計算効率は, 入力値に比例する. 空間効率は, 一定.

これを線形反復プロセスという.

;; normal-order evaluation
;; linier iteration
(defun plus (x y)
  (if (= x 0)
      y
    (+ (1- x) (1+ y))))

以下からなる.

• 状態が一定個数の状態変数
• 状態が移ったときに状態変数をどう変化させるかの規則
• プロセスを終了させる条件.

関数の引数

いろいろ種類があり名前がつけられている.

仮引数(parameters)

関数定義時の引数.

実引数(arguments)

関数呼び出し時の実際の値.

位置引数

デフォルト引数

キーワード引数

位置引数は左から並んだ順に引数として解釈されるが, キーワード引数とは仮引数にキーワードをつけることで左からのならび順でなくて直接キーワードに対して値をbindできような方法.

📝可変長引数(Variadic Variable)

可変長引数. Variadic=可変長.Variadic Variable

オプション引数とも.

👉Related

up: 📂プログラミング概論