LISPとは

John McCarthyが1958年に考案したプログラミング言語

LISPの特徴

  1. 1.記号処理向けの言語である 

  2. 2.記号的人工知能の研究に多く用いられた 

  3. 3.コンパイラとインタプリタ両方がある(処理系にもよる) 

  4. 4.λ計算に基づいている 

  5. 5.リスト処理(再帰的データ構造を扱う)を行う 

    1. 1.LISP=リスト処理+λ計算 ともいえる 

    2. 2.Lisp=LISt Processor 

  6. 6.LISPのインタプリタをLISP自身で記述できる(メタサーキュラー・インタプリタ) 

  7. 7.対話的に実行できる 

  8. 8.ラピッド・プロトタイピングに向いている 

  9. 9.括弧が多い 

  10. 10.方言が多い(Schemeはそれらのうちの一つ) 

  11. 11.(相対的に少数だが)信奉者がいる 

  12. 12.古くからあるのに先進的な機能を含んでいる 

    1. 1.マクロが強力 

    2. 2.塵集め(自動メモリ管理) 

    3. 3.函数型的なプログラミングが可能 

    4. 4.高階函数を扱える。 

計算機の二大用途(の分類の仕方の一つ)

数値計算

数値シミュレーション: 颱風の進路予測、有限要素法等

統計的人工知能: サポート・ベクタ機械、強化学習、ディープラーニング

記号計算

数値以外の計算、例えば論理計算、記号的人工知能

(プログラミング)言語処理系とは

計算機はCPUごとに異なる機械語を実行できるが、他の言語で書かれたプログラムは直接実行できない。実行するにはプログラミング言語処理系が必要である。

プログラミング言語処理糸系とは、機械語以外のプログラムを実行するためのプログラム群のことである。

インタプリタ方式

ある言語で書かれたプログラムを、それぞれの言語ごとの小単位ごとに解釈・実行する(通常は機械語の場合が多い)プログラムをインタプリタという。

コンパイラ方式

ある言語で書かれたプログラムを、一挙に特定のCPUの機械語に翻訳する(通常は機械語の場合が多い)プログラムをコンパイラという。コンパイル前のプログラムをソース・コード(プログラム)、コンパイルした結果のデータをオブジェクト・コード(プログラム)という。オブジェクト・コードとライブラリをいくつかまとめてくっつける作業を行うプログラムをリンカと呼ぶ。リンクの結果が実行可能プログラム(ファイル)となる。コンパイラ方式の場合には、これら一連の作業を行うプログラムをまとめて言語処理系という。

λ計算

Churchによって考案された計算の基礎理論の一つ(当初の目的は違ったが)。総合人間学部の学部授業としては計算幾何学の基礎Aがある。

 

プログラミング・パラダイムとは

プログラムを書く際の考え方のこと。それぞれの言語ごとにその言語を使ってプログラムを書く際の標準的な考え方があらかじめいくつか設定されている場合がある。それをその言語のプログラミング・パラダイムと言う。複数の場合もあり、そういった言語の場合にはマルチ・パラダイムと言う。

 

古典的3大(4大)パラダイム

手続き型(procedural)

プログラムの断片により計算機はその状態を変えてゆくと考える。するとプログラムはそういった手続きを記述したものであると思える。プログラムの実行は、手続きの指示通りに計算機の状態を変化させてゆくことである。フォン・ノイマン機械(あるいはチューリング機械)に合ったパラダイムである。変数とそれへの代入文がある場合には大抵これの場合が多い。

FORTRAN, Algol, LISP, BASIC, COBOL, JAVA, Javascript, C, C++, C#, Ruby, Python, OCaml

函数型(functional)

プログラムは数学的な函数を記述したものであると考える。プログラミングとは、データ型と函数を次々に定義してゆくことである。プログラムの実行とは函数に引数を与えてその値を求めることである。LISPは函数型的にプログラムを書くことも可能だが、実際の応用例では代入文を多用する場合も多いので、函数型ではない、という人もいる。函数型言語は数学的に美しい。しかし実行のオーバヘッドが大きい場合がある。

再帰的函数, λ計算, コンビネータ論理, ML, Haskell, Erlang

論理型(logic)

論理式(logical formula)がプログラムであると考える。ただし、ホーン節(Horn clause)などの限られた形の論理式に限定してプログラムを記述する。プログラムの実行は、推論(inference)を行うことである。やはり数学的には美しいが、実際の応用プログラムでは数学的に美しく意味がつかない領域でプログラムを記述することになる場合も多い。

Prolog, Temporal Prolog

オブジェクト指向(object-oriented)

計算とは、オブジェクト(object)たちが内部状態を保ち、それらがメッセージをやりとりして相互作用し、状態を変えてゆくということである、と考える。各オブジェクトの中身は外からは見えない(データ隠蔽)。ただしプログラムは各オブジェクトのメッセージに対する反応の仕方(他のオブジェクトへのメッセージ送信を含む)を記述する。上記3大パラダイムとは直交する概念である。クラス概念がある場合とない場合がある。クラスとはオブジェクトをまとめたもので、(基本的に)メッセージに対する反応の仕方の記述が同じである。

SIMULA, Smalltalk, Ruby, Python, JAVA, Javascript, C++, C#, Objective-COBOL

 

プログラミング言語の特徴

変数があるか

変数(variable)とは、データが入る箱と思えばよい。箱には大抵名前を付ける。ただし箱がプログラムの実行に伴って動的に用意・破棄されたりする場合がある(局所変数)。局所変数(local variable)は名前も局所的に有効である。イメージ的には、プログラムの実行開始時から終了時まで存在する変数を大域変数(global variable)と呼ぶ。

上記の例ではコンビネータ論理のみが変数を持たない(しかし計算万能である)

変数が書き換え可能か

変数の値を書き換えられるかどうか。Haskell, Prolog(バックトラックを除く), Erlang等の変数はimmutableである。

書き換え可能な変数をmutableと言う。そうでない場合にはimmutableと言う。

実行前の型チェックを行うか

データ型のチェックを実行時に動的に行う言語(動的型付けの言語)と、実行前に行う言語(静的型付けの言語)がある。静的型付けには、実行前の型チェックに通れば実行時に型エラーが起きないことが保証される強い型付けと、そうとは限らない弱い型付けがある。

パラダイムは何か

上記のようなパラダイム、あるいはそれらをさらに細分化した・発展させたパラダイムでどれを採用しているのか。

(オブジェクト指向の場合には、)クラス概念があるかどうか

クラス概念があるのかどうか。

計算万能とは

チューリング機械と同等の計算能力を持つ、ということ。これは停止しないプログラムを記述できるということを含意する。従って停止するプログラムしか記述できない言語がもしあれば、その言語は計算万能ではない。例えば再帰函数の一部を成す原始再帰函数のクラスはすべて停止するので、計算万能ではない。殆どのプログラミング言語は計算万能である。チューリング完全とも言う。