📝Programming Base Concepts

📝Programming Base Concepts

up: 📂プログラミング言語処理系

Program: プログラム #

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

パラダイムによって, 定義がことなる.

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

SICP より #

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

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

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

Expression: 式 #

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

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

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

Process: プロセス #

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

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

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

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.

Single-Assignment Store #

単一代入格納域. 一度一つの値を束縛したら変更できない変数の集合.定数.

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

bindings #

変数束縛.

Type: 型 #

データ構造・型のページへ移動

TODO: githubから移植.

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 つは, デフォルトで字句的スコープではなく動的スコープを使うことである. つまり, 呼出し関数の局所変数は, ポインタや参照を渡さなくとも, 呼び出された関数から参照できる.

State: 状態 #

State (状態) とは, 必要とされる計算の途中結果を含む, 値の時系列. (sequence of values calculated progressively, which contains the intermediate results of a computation)

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

modular #

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

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

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界隈でいってた).


Eager Evaluatin: 先行評価 #

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

Haskell #

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

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

未整理 SICP より. #

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

糖衣構文 | SyntaxSuger #

ref: 糖衣構文 - Wikipedia

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

例外 | Exceptions #

プログラムがある処理を実行している途中で,なんらかの異常が発生した場合に, 現在の処理を中断 (中止) して, 別の処理を行うこと. その際に発生した異常のことを例外と呼ぶ.

ref: 例外処理 - Wikipedia

よくある 2 つの概念.

  • try: 例外ハンドラをもつ例外補足コンテクストを生成.
  • raise: もっとも内部の例外補足コンテキストへ jamp し, そこにある例外ハンドラを起動.

各コンテキストはスタックで管理され, try はスタックの 1 つに marker をつける. raise は marker にジャンプして marker の場所に例外処理のコンテキストを挿入する.(ref. CTMCP p93)

例外の種類 #

  • Asynchronous Exceptions: 非同期例外
  • Synchronous Exceptions: 同期例外
    • Traps: 意図的に OS が止める breakpont, systemcall, file open
    • Faults: リカバリ可能な例外, page fault, segmentation fault
    • Aborts: リカバリ不可能な例外, プログラムは強制終了.

💡例外がないと戻り値チェックでうんコード #

例外をつかわないと, コンテクストごとの結果を検証必要があり, return 文 と case 文が乱立するうんこコードが出来る.

例えば, 下位のコンテキスト (A) で発生したエラーは, return -> return -> して上位でも戻り値のエラーチェックが必要.

#define ERROR -1
#define OK 0

int main (void) {
  if (C ()==ERROR) {
    printf ("Error\n");
  }
}

int A () {
  return ERROR;
}

int B () {
  if (A () == ERROR) {
    return ERROR;
  }
  else {
    return OK;
  }
}

int C () {
  if (B () == ERROR) {
    return ERROR;
  }
  else {
    return OK;
  }
}

Function: 関数 #

関数.

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

  • 手続き型: procedure
  • オブジェクト指向: method
  • 関数型: function

手続き型パラダイム: procedure | プロシージャ #

戻り値つきのサブルーチン. C 言語 など.

ref: C 言語 - Wikipedia

プログラム中で意味や内容がまとまっている作業をひとつの手続きとしたもの.

手続きにつけられたラベル.アセンブラのラベルと同義. (ref: 関数プログラミング実践入門)

オブジェクト指向パラダイム: method | メソッド #

あるクラスないしオブジェクトに所属するサブルーチン.

ref: メソッド (計算機科学) - Wikipedia

各オブジェクトが持っている自身に対する操作. オブジェクトは「データ」と「手続き」から成っているが, その「手続き」の部分に当たる.

ref: メソッドとは 〔 メンバ関数 〕 【 method 】

関数型パラダイム: function | 関数 #

関数は, ある型の引数を他の型の引数の結果に変換する. 型とは, 互いに関連する値の集合.

ref: プログラミング Haskell: Graham Hutton

数学に置ける関数の概念に近い. ある集合から集合への写像.

ref: 関数 (数学) - Wikipedia

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))))

以下からなる.

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

関数の引数 #

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

位置引数 #

デフォルト引数 #

キーワード引数 #

可変長引数(オプション引数): Variadic Variable #

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

オプション引数とも.

Anki #

遅延評価とはなんですか?またそのメリットはなんですか? #

値が必要になるまで式の評価を遅らせる評価戦略.

計算コストを削減したり大きなデータを扱うことができる.

ref