Entries

スポンサーサイト
[EDIT]
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

-件のコメント

コメントの投稿

新規
非公開にする

-件のトラックバック

トラックバックURL
http://harukazehajime.blog115.fc2.com/tb.php/131-6c246ca5
この記事に対してトラックバックを送信する(FC2ブログユーザー)
関数型言語
[EDIT]
それはFORTRANコンパイラが登場して3年後のこと。ジョン・マッカーシーが、配列を操作するためのプログラミング言語としてLISP(LISt Processing)が登場しました。歴史的に見れば3番目の高級言語です。

LISPのソースコードはそれ自身が配列であり、データでもあります。またプログラミングにおいてソースコードは、ただ実行するだけの「ステートメント=文」と、実行すると一意の値になる「式」が存在しますが、LISPではすべてが式で表されます。よって、サブルーチンを作るとき、値を返さないようなサブルーチンを作ることはできません。
例えばC言語において、以下のソースコード
int main(){
int i = 1;
int j = 0;
return (i > j) ? i : j;
}
の main関数と (i > j) ? i : j; は式であり、ほかは文です。mainは最終的に i か j の値を表すようになり、(i > j) ? i : j; も i か j の値を表します。今回の例であれば i > j は成立し、? の直後の i が式の結果になり、mainはreturn文に続く式 (i > j) ? i : j; の結果である i を表すようになります。
ちなみにreturn (i > j) ? i : j; は
if(i > j){
return i;
}else{
return j;
}
と等価です。

これとまったく同じものをLISPで書くとどうなるか。
(defun main ()
(setq i 1)
(setq j 0)
(if (> i j) i j))
defunは関数に名前を付ける特殊な式で、関数名・引数・関数の定義と続けます。defunはすべてを評価した後、関数名を式の結果とします。
引数は単純な変数のリストという形で書き、その変数に引数の値が渡されます。空の括弧は何もないことを表すnilと評価され、すなわち引数がないことを表します。
setqはいわゆる変数宣言と代入です。setqは第1引数を変数名として変数に第2引数を割り当て、第2引数をそのまま返します。
ifも特殊な式で、比較を行う式・その結果が真(t)だったときの式・偽(nil)だったときの式と並んでいて、比較した式の結果が真だったときの式か偽だったときの式の結果がifの結果となって表されます。
>は続く引数リスト(今回なら i と j)に対して大小比較を行い、第1引数が第2引数より大きければ t、そうでなければnilを式の結果とします。
このように、すべて何かしらの値を返しています。
LISPはこのままでは関数名を返すだけで、実際にその関数を呼び出すことはしてくれません。どこかで呼び出す必要があります。今回の例なら、defunのあとに次のように書きます。
(main)
これでようやく関数が実行され、結果として0が返ってきます。実行する際、まずsetqを順に評価し、i には 0、j は1が割り当てられます。次に (> i j) が評価されます。これは i > j と等価で、今回この式は正しいのでt(真)と評価されます。すると今度はifが評価され、真の場合の式である i の結果を返します。これがmainの結果となって0が返ってきたわけです。

このようにLISPで自作の関数を実行するには自分で呼び出さなければならないので、引数を与える形で関数を作成した方が良い場合が多々あります。今回の例なら以下のように作る方が便利でしょう。
(defun main (i j) (if (> i j) i j))
(main 0 1)
2行目はは引数として0と1を渡しています。引数はそれぞれdefunの第2引数のリスト、今回は i と j に格納されます。引数がsetqと同じような役割を果たすので、関数は前回とまったく同じように評価されます。

関数型言語の古参でかつ定番中の定番とも言えるLISPで説明してきましたが、ほかの関数型言語も大体通用します(当然、構文などは異なりますが)。LISPは数多ある関数型言語の中でも直感的で、学習が容易だと思います。
LISPはLISPだけをつかってLISPそのものを自在に改造できる(メタプログラミング)ので、様々な方言が存在します。ここでいう方言とは、これまでも何度か扱ってきたBASICのように、おなじ言語でも処理系によって拡張されたりしている言語がある、という意味です。
方言としてはEmacsに特化されたEmacs LISP(elisp)、教育向けとして使われているらしいscheme、相次いで現れる方言を統一し、ANSIで標準規格が策定されたCommon LISP、ゼロックスのAltoに採用され一世を風靡したInterLispなどが有名です。この記事では主にCommon LISPを前提としています。例えばschemeでは真と偽の値として#tと#fを用いていて、先ほどの解説をそのまま適用することはできないようです。

それではいよいよ階乗を求めるプログラムです。ほかの言語だと大抵は2桁を超える数値から階乗を求めようとすると桁あふれで求められなかったりしますが(電卓に桁数の上限があるのと一緒)、LISPは数学の問題を解くことを得意としているので、言語レベルで何十桁にも及ぶ数値が扱えます。
(defun fact (n)
(if (<= n 1)
1
(* n (fact (- n 1)))))
関数の定義はこれで終わりです。LISPはリストや関数をすべて括弧で括って表現するので、このように括弧だらけになることで有名です。
実際に階乗を求めるときは例えば次のようにします。
(fact 120)
乗算、減算、比較などすべての演算子が先頭に来るという以外は構造化プログラミングで説明したことが通用します。その際、(fact (- n 1))は再帰になっているのも自明でしょう。

演算子が先頭に来る(前置記法)のはLISP特有のもので、演算子も関数であり、関数名は必ずリストの先頭(LISPではCAR: Contents of Address part of Register と呼ぶのが一般的です)に存在している必要があるからです。
また、LISPではリストのすべての項目に対して関数を適用することができるものもあります。例えば1+2+3+4+5は
(+ 1 2 3 4 5)
とすることで求めることができます。
 

 

emacsのおかげで関数型言語=LISPという印象が多いと思いますが、ほかの言語もあります。
1966年、ML(Meta Language)のベースとなるISWIM(If you See What I Mean)が考案されます。考案されただけで実装されることはありませんでしたが、後の関数型言語に大きな影響を与えました。翌67年、APLが実装されました。LISP以外では一番最初ですから、LISPが実装されてからかれこれ9年。
1972年、ISWIMに影響された純粋関数型言語SASLが誕生します。翌1973年にはISWIMのひとつの機能を除くすべてを実装したとされるMLと、同じ頃に同じエディンバラ大学で、小さな関数型言語Hopeが開発されました。MLは定理証明器の一部として開発されたため型推論を持ち、特に注目を集めたんだと思います。
75年、LISPの方言Schemeが誕生。77年はAPLの方言ともいえるFPが誕生。84年は乱立するLISP方言を統一すべくCommon Lispが策定されます。85年に純粋関数型言語の火付け役Mirandaや速度重視のCamlが、86年にErlang、87年にはMirandaの影響を受けた純粋関数型言語Cleanが、90年にはMirandaの影響を受けたHaskellの最初のバージョン、StanderdML、Dylanなど立て続けに誕生。96にObjective Caml、98年にはHaskellが現在の形(Haskell 98)になります。
関連記事

0件のコメント

コメントの投稿

新規
非公開にする

0件のトラックバック

トラックバックURL
http://harukazehajime.blog115.fc2.com/tb.php/131-6c246ca5
この記事に対してトラックバックを送信する(FC2ブログユーザー)

Appendix

プロフィール

さくらゆーな

Author:さくらゆーな
鉄道熱が再燃して、撮影に模型にいろいろやってます。
最近反核運動に偏ってるのを反省したいけど
知れば知るほど極悪非道な界隈で止まらない…

カレンダー

07 | 2017/08 | 09
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

+ アーカイブ
 

最近の記事

カテゴリー

検索フォーム


キーワード

カウンター

トータルカウンター
現在の閲覧者数:

ads3

Mac ソフトのことなら act2.com

Make a donate

もしこのブログを気に入っていただけたら上記アフィリエイトプログラムか下のPayPalでブログ・サイトの維持にご協力ください。

donationPrice

ブロとも申請フォーム

この人とブロともになる

ブログランク

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。