TOP > プログラマ2.0日報 > 2008年03月

あすなろBlogger

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

若者向きな Linux

2008.03.25

久々に仕事でUNIXサーバをいじることになりました。で...愕然としました。それは、

ls で表示された「ディレクトリを示す青色」が全然見えない....

ということです。そういや最近ちょっと暗くなると、細かい文字が読みづらくて困るんです.....要するに老眼、です(涙)。

というわけで bash エリアスを書き換え。

$ alias ls='ls -F'

です。ディレクトリは「/」が付くから、これが色分けの代わりですね。

....Linux でもデフォルト設定は、若者向き?ということになるのかなぁ(けど何であんなに暗い発色の blue が一番使いでのあるディレクトリに割り振られているんだろ)...

 

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.25 12:26

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

実世界インターフェイス

2008.03.23

このところ例の taspo の導入が本格化したこともあってか、それに対する問題と批判とか出てくるようになってきました。で...ちょっと思うことなのですが、

コンピュータの「中の世界」から、外の現実世界の情報を得ようとすると、極めて難しい....

ということを痛感するのですね。たとえば、taspo でしたら、成人が入手したカードを未成年者が借りて(あるいはそれこそ盗んで・奪って)使う...というのは当然の抜け穴です。もともと100%を目指すシステムではないからこそ、「たかがカードで証明しよう」と考えたわけでしょう。

しかし、もう少し何らかのかたちで、「信頼性のある実世界情報を得よう」とするのならば、それなりの証明・認証手段が必要になるわけです。たとえば、

このアクセスの向こう側にいるのは、人間かロボットか?

という古典的チューリングテストみたいな証明問題が、この間から切実化したこともあって、例の CAPTCHA の流行があったわけですが、これだってアダルトサイトをフロントエンドとする有名な突破法があったりするわけです。要するに、マシンログイン時のアカウント認証のように、

たかがコンピュータに以前保存されたデータと、今入力されたデータとを突き合わせればOK

というようなものは、それが「コンピュータの中だけで完結する非常に単純なケース」に過ぎないわけです。それを超えて、「何か意味のある属性」を証明しようとすると、大変な困難に遭遇する宿命にあるわけです....

勿論 taspo は、それを発行する機関で「20歳以上であること」を証明して、その証明結果をカードにしたものです。ですからこれは、「人の目による証明書のチェック」があって 発行される、という「認証」手続きがあるわけです。その証明書は

運転免許証、各種健康保険証、住民基本台帳カード、各種年金手帳、各種福祉手帳、外国人登録証明書、住民票

といった公的機関の証明書ですから、そういう「公的機関の証明力」に依存した証明をここで行うわけです....これも考えてみれば「認証の連鎖(たとえば PGP の認証の連鎖モデルって面白いですよ!)」みたいなことを前提にしているわけです。

まあ、考えてみれば例の「公的年金の名寄せ」問題で、そういう「公的機関が行う証明」の証明力(厳格にはその情報の一貫性)に疑問が付されている...が政治問題化している、という厄介な状況のもとで、「個人の情報」がどれだけデジタル化され、どれだけその情報がさまざまな局面で活用されうるか、あるいはその「情報の管理」の安全性がどれほどのものが要求されるか...といったことについての漠然とした危機感と同時に、「それをより安全かつ利便に使うためのインフラ」についての議論というものももう少しきっちり行うべきではないのか、という気がします。たとえば、昔総スカンを食って取り下げられた「納税者番号制度」だって、中途半端な住民基本台帳カードとは違い、

たとえば確定申告をしないでまったくOK、になる

というようなメリットだって実はあるわけです。もう一度「個人のさまざまな属性をデジタルに証明可能なインフラ」というものについての議論が必要なのではないか...などと思います。要するにコンピュータの世界と実世界とをつなぐための装備を、コンピュータの側から見た時の名称を仮に名づければ

実世界インターフェイス

の必要性、についてのコンセンサスを得るべきなのでは....とも思います。どうでしょう?

 

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.23 12:09

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

Java には何でないのだろう?

2008.03.18

というのは、マクロの話です。

私は Eclipse 使いじゃない(由緒正しく Emacs でコーディングする人)ので、たとえば JavaBeans のアクセサを、Emacs のキーボードマクロで変数宣言から自動生成するなんてしています。まこれは勿論 Eclipse 使いの人だったら、そういう自動生成を使っちゃっているのでは?とも思いますが、逆にこういうの、

手で生成して間違いがあった時にめちゃくちゃうっとおしい

ので、是が非でも「自動生成」すべきものです。OK? で...そういう時に、

マクロがあればねえ...

と思ったことのある人は多いのでは、と思います。まあ、強引にそういうマクロを、アノテーション+JavaAssist(みたいなクラスファイルを直接書き換えるようなタイプのバイトコード・エンジニアリング・ライブラリ)で、事後的に JavaBeans のアクセサを生成する、というのは出来なくもない(private なフィールドだとラッパクラスで包んでやれない...あるいは、ラッパを作るのならばリフレクションでprivate を一時的に解除する)のですが、やたらと手がかかります。でしたら、逆に

Java World ですべてを完結させずに、適当なテキストフィルタで置換した方がずっと早い....

なんて思ったりしちゃう(思うだけではなくて実行も...)わけです。

まあ、アノテーションを使った XML(とかでの) データの自動生成も使えないわけではないですが、意外にアノテーション・プロセッサの処理は面倒だったりします。「ちょいとしたマクロ代わり」というような不純な動機で使おう...というのにはさすがに敷居が高いですね。

Java にマクロがない理由、っていうと、やっぱりこんなことが嫌われたのでしょうか...

  1. 1. Java のソースはいわゆる「前方参照性」が問題にならない、という前提をマクロは崩す。もちょっと易しい言い方をすると、ソースコードの後の方にあるインスタンス変数やメソッドを、ソースコードで宣言が登場する以前に、前のほうで参照しても問題がない(変数・メソッドの「宣言順」はどうであっても問題にならない)...というのが Java のイイところの一つですが、マクロは define, undef とかあるように、「今のマクロの内容如何」によって、展開されるコードが変わりうるわけです。「マクロ定義の登場順」に依存した生成コードになっちゃうんですね(もちろんそれでエラーになる可能性も...)。これは原理的に違う...と思われたのかなぁ。
  2. 2. マクロは「大域置換」であって、特定のクラスに所属する...とは言えない。Java では変数だろうとメソッドだろうと何でもかんでも、クラスに付属していますね。ですけど、マクロの置換指示はとくに「このクラスだから....」という感じではなくて、マクロを実行するならば、たとえばマクロ定義をした static クラス MyMacroDefines を implements して置換指示をするような格好になるのでは?などとも思います。ここらへんもイレギュラーですね。

まあ、こんなことを考えちゃったりするのは、最近の関数型言語でもマクロが健在だ、というあたりからです。たとえば Erlang でもC言語風のマクロがありますし、Lisp→Scheme→Gauche だったら昔ながらの強烈なマクロがずっと存在しているわけです(Paul Graham の「On Lisp」(本だと)で使い倒してますね...)。また Gauche だと、R5RS(Schemeの仕様)で定義された「健全なマクロ」と二本立てだったりするわけです(単純に「健全」を言い換えると、「変数のバッティングが起きない」ということくらいにご理解ください)。ま、Lisp のマクロはCのマクロとはレベルの違う「プログラムジェネレータ」みたいなものですから、「Lispマクロ」として研究する価値のあるものです....

マクロ、というとマイナーながら m4 みたいなスタンドアロンのマクロプロセッサも UNIX なら必ずありますし、そろそろ天寿を全うし...に近くなっている(失礼) TeX が典型的なマクロ言語でしたから、「マクロの世界」というのは実はかなり深い歴史と実績がある「別な世界」だったりするのです。

さすがに Haskell にはマクロはないようです....ま、これは当然か。

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.18 16:43

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

オビの魔法使い - 謎のLisp脳

2008.03.17

さて、先週「プログラミングGauche」が出ていました。私は速攻でゲット。

で...この本のオビが

「Lisp脳」の謎に迫る ---- Scheme プログラマは何をどう発想しているのか?

というものでした。なるほどねえ....「Lisp脳」ね。

私なんかは世代的に「ハッカーを名乗るんだったら Lisp の素養はあって当然」という感覚なのですが、若いプログラマだと、「Lisp が得意=珍獣的プログラマ」という感覚なのかもしれませんね(苦笑)。

でこのところ関数プログラミングに光が当たってきだして、Lisp を知らない世代も「何かと気になる....」となってきた、ということを、このオビの名(迷)文句が示しているようにも思います。

それはともかく、この本の特徴...というと、まあわりと基本から説明している雰囲気です。「Lisp を巡るちょっとしたコラム」として「へえ~」というような雑学が開陳されていて、面白いです。たとえば、

λ算法がなぜ「λ」なのか、というと、ラッセルとホワイトヘッドが書いた「プリンセピア・マセマティカ」の中で、束縛変数を示すのに「カレット(^)」を使っていて、これをλ算法の祖であるチャーチが一行で ^x(x+x) と示したのだけども、カレットの表記が見た目ヘンなので、これをギリシャ文字のΛ(大文字)にした。しかし、他の記号と間違えやすい(確かに「かつ」を示す∧と間違えやすいです)ので、小文字のλになった(p63 の大意)。

なるほど、おそれいりました。.

で、この Gauche という処理系の特徴としては、

  1. 1. Perl の影響がある、ということを作者自身が認めちゃっている。で、正規表現リテラルとか、文字列フォーマットととか、そういうやや汚い(が実用的な)機能がサポートされている。
  2. 2. Common Lisp 起源のオブジェクトシステムである、CLOS を持っていて、すべてはオブジェクトである。
  3. 3. Common Lisp 起源の例外システムがある。
  4. 4. 汎用のアプリケーションサーバとして使える、Kahua というフレームワークがある(Erlang だと OTP に相当するもののようです)。

まあ、のっけから「Perl の影響を受けている」と言ってしまうのって、今のギョーカイの雰囲気からすると、結構度胸のあることのようにも思います。やはり「Perl の汚さ」というのは、「さすがにもう勘弁してよ...」という雰囲気がないわけではないですからね。まあとはいえ、正規表現を使うのに、それを文字列として評価する(たとえばJavaみたいに)のではなくて、独立のオブジェクトである正規表現リテラルで表現する、とか、文字列の中に評価時に展開される変数(というか式表現)を埋め込めるとか、そこらへんは「まあ、とにかく実用的、というものか」という感じで許せるものじゃないでしょうか。

別の流行ネタである Erlang だって、たとえば Haskell の美と比較すれば、ハッキリ汚いです。しかし、Erlang の強みはやはり「実用性」ですから、そこらへんこの Gauche と似た側面があるのではないでしょうか。考えてみれば近年では最高の成功した言語の一つである Java だって、smalltalk と比較すれば汚く、C++ と比較すれば「出来ないこと多すぎ」な、純粋に言語的に見れば中途半端かもしれないけども、「実用性はちゃんと考えてある」言語だったわけです。Gauche や Erlang が強調する「実用性」というのも、これは関数型プログラミングの「成熟」を表現しているのかもしれませんね。

 

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.17 20:16

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

頭に棚を作れ!

2008.03.13

「心に棚を作れ!」って表現は一部で有名ですが.....少し再帰と関連して「頭にスタック(棚という意味があります)を作れ!」というアドバイスです。

今している仕事では、SQLの複合検索条件をイメージしたUIがあります。ということは、カッコを使って入れ子になった条件を(かなり深いレベルだって)作れちゃうことになります....ですからこれ

使うのに結構コツが要る....

と実装者ながらオソレていたりするわけですけども、その「コツ」というのは、

入れ子状態をしっかり脳内でイメージする

ということでもあるわけです(ま、SQLで「どういうコードを吐くか」を理解するのも重要ですけどね)。この「入れ子状態」を表現する記憶装置が、他ならぬスタックです。

話は突然変わりますが、私が私淑する某アーチストは、長らく大学の先生もしてましたので、その講義を聴いたことがあります。ホントこの先生、天才です。というのは、講義ですからいわゆる「脱線」とかあるのは当然なのですが、この先生の講義で「脱線した中から更に再脱線し....でも、脱線元に戻って後始末し、さらに本線に戻る」というワザをやってのけたのです。要するにこの先生、しっかりと

脳内にスタックがある

ということです。コンテキストがきっちりとスタックに積まれていたわけですね!

レベル付きの複雑な入れ子構造、というのはプログラミングでもよくお目にかかります。会社→部門→部→課といった構造も「入れ子」ですし、実際これは本質的なデータ構造の一つで非常に重要なこともあって、特に「スタック」と呼ばれるわけです。しかも特にいわゆる「関数」を呼び出して、処理が終わったら呼び元に戻る...というのは、このスタックを利用しているわけです。もともと COBOL, Fortran, BASIC といった「古臭い」言語では、「再帰呼び出しができない」という制限がありましたが、これは「サブルーチンを呼ぶのに、スタックを使わなくてはいけない、という言語的制約が(古すぎるために)ない」という理由なのです。言い換えると、「スタック経由で関数を呼び出すならば、再帰ができる!」ということなのですね。

ですから、再帰をイメージするには、やはりこのスタックのイメージをしっかりと持つこと、というのが重要です。棚の上に「もの」が載り、その「もの」の上に更に「もの」が載り、その上にも更に積み重なって.....で、一番上に積む(PUSH)か一番上から取る(POP)か、この2つの動作しか許さないのがスタックデータ構造の基本になります。

階層入れ子データも、再帰も同じように「スタック」という概念で処理を一本化できる...というのは凄いことだと思いませんか? で、特に「再帰」の考え方が(効率が良いわけではないのに)人気がある理由とは、ホントはこういうことです。

複雑な階層構造を持った「全体」の手続きを考えなくても、その1つのレベルにスコープを限定して、「その上のレベルとその下のレベルとの関係性」だけに注目すれば、「何をすればいいのか」が簡単にワカる

ということなのです。数学的には「漸化式」とか「微分方程式」みたいな感覚ですね。ですから、とりあえず全体を考えること、は「心(頭)に棚を作って」おいておいて、その棚に積まれた「もの」の、その上の「もの」とその下の「もの」との関係に視点を特化して考える...ということなのです。その上の「もの」は再帰プログラミングでは、その中での再帰呼び出しに相当し、その下の「もの」は戻り値で表現されるわけです....

ね、頭にスタックを作りましょう!

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.13 09:31

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

再帰とポインタは必須教養、だろうか

2008.03.12

というのが、例の「Javaスクールの危険」で一番論議を呼んだ部分だ、ということは皆さんもよくご承知のことでしょう。で、最近の関数型言語ブームの中でやはり「関数型言語を使えるための必須技法」が再帰のわけです。ですから、少しこれを検討してみましょうか。

まあ私はプログラマとしては古手なので、Cを勉強しだす前にアセンブリを少しやっていたわけですね。ですから、「ポインタ=アセンブリでの間接参照」というイメージをガッチリと「C以前」から持っていたわけです(未だにポインタを MOV AX, word ptr ds:[BX] っていうようなイメージで捉えます。古臭いですね)....ですから、ポインタを「難しい」と捉える、ということ自体ありえなかったわけですね。まあ、こういう入り口は今はありえないでしょうが。

しかも、再帰については、学生時代に一番ホビーでハマった言語が Lisp でした。勿論80年代前半でも大型計算機センターには今見るとちょっとヘンな方言の Lisp が載ってましたので、それで遊んでアカウントの課金のほとんどがそれで消えた....なんて今から考えると馬鹿な話がありました。この時期、知り合ったオジサン(経済誌記者でした)が偶然 Mac 上の Lisp を趣味にしていたことがあって、Lisp 話でも盛り上がった....なんて思い出があります。その他当時京都大学で開発していた CP/M で動く Prolog(prolog-KABA) を手に入れて遊んでたこともあります....まあ、ここらへん特殊なバックグラウンドでしょうか。逆に言うと、当時の授業で使っていた Fortran や BASIC が再帰ができないのでツマラない印象を持っていたくらいです。

というわけで、私が「ポインタや再帰は勉強しないとダメだ!」なんて今の人を脅すのは若干忸怩たるものがあります。キャリアの始めの部分で、自然に憶えちゃったわけですから....とはいえ、ここらへんの資産が「すごく役立ってる」という意識はしっかりあります。

要するにポインタも再帰も、強く「抽象化」に関わっている技法です。しかし、ポインタならばメモリイメージをしっかり頭の中に保持できるのならば、再帰ならば意識を「関数仕様にしっかり(一時的に)フィックスできる」のならば、決して難しいものではありません。「イメージを持つ持ち方」をうまく切り替えること、がこの2つの技法に共通するキモのようにも感じます....「頭の使い方」なんですよね。

ですからポインタも再帰もまだ勉強していない人に対してのアドバイス....というと、こんなところでしょうか。

頭の新しい使い方を憶えると、新しい世界が開けるよ!

まあ、怖がらずにチャレンジしてごらんなさい!!!

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.12 14:10

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

関数型言語ブームは始まってる...

2008.03.11

か、どうかがこのエントリのネタです。

以前のエントリで「関数型言語ブーム」というようなことを書いたこともあって、

じゃあ、それホントなの?

というのはやはり気になるあたりです。ここはググって、「関数型言語ブーム」でどの程度来るかを見てみましょう。

純粋関数型言語Concurrent Clean: ホットコーナーの舞台裏
関数型言語がブームとなれば、次に来るのは、あなた、形式仕様記述
(Formal Methods)のブームですよ。\(^O^)/
オブジェクト指向+関数型言語 Scala - yojikのlog
昔チェックした時は、変な文法だなーと思っただけでスルーしてしまったけど、ここ最近の関数型言語ブームの影響で興味が出てきた。
810. Re. 809. 関数型言語はブーム?
やはり最近関数型はブームだと思います。
内部状態が無いので、
並列処理に有利で、また、見つけにくいバグなどが混入しにくい
のが大きな原因だと思います。
関数型言語の勉強にSICPを読もう - (1) SICPを読み始めた理由 - ひげ ...
世の中ではにわかに関数型言語(特にHaskell)がブームです。
もちろんそのブームにのっかったってのもありますが、d:id:higepon:20051214:1134573806にもあるようにそれ以前にSchemeを勉強しようとして挫折したことがあります。
関数型言語(関数型プログラミング)の勝利? | Diaspar Journal
LISPが発明されたのは1958年ということなので、今年の2008年でちょうど半世紀ですね。 長年に渡る研究の成果が実を結んでいくのを感じます。
jijixi's diary - 関数型言語の常識 , 関数型言語脳の常識 (…かどうか ...
つい何年か前までは「fold って何?うまいの?」とか言ってたわしだけど、すっかり関数型脳になった今では fold が無い生活なんて考えられない。
かつて、わしが最初に fold の使い方を知ったときの例は sum だった。要するにこんな↓の (コード例は昨今のブームを反映して Erlang)
みかログ: Erlangは関数型だけど難しくない
結構Erlangが密かなブームになっている気はするものの,期待しすぎているような話も結構あるように思う.
Panopticon :: ペンギンでもわかるScheme :: Schemeって?
僕の予想では、2008年くらいには関数型言語のブームきちゃうんじゃないのかな?という感じなので、ちょっと触ってみてもいいんじゃないでしょうか。

まだまだありますが、用法を見てみると、すでに「ブーム」と認知されている...という雰囲気ですね。とはいえ、本質的に「すべてのプログラマに多大なメリット」という感覚のもの...とはならないでしょう。そういう制限、みたいなことを割り引くと、やはりその範囲ではきっちりブームは始まっている、という感覚です(というか、一般プログラミング雑誌で紹介が載る...なんて、かなり久々じゃないか、という感じです。学者が書いた書籍で勉強する..というのが今まで当たり前でしたからね)。

さあ、あなたも勉強してみませんか???

あ、こんなのありました。

私は関数型言語が好きだ

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.11 18:07

facebookに投稿 このエントリーを含むはてなブックマーク このエントリーを含むはてなブックマーク このエントリーをはてなブックマークに追加 この記事をクリップ! livedoorclip ユーザー数 BuzzurlにブックマークBuzzurlにブックマーク この記事をtweetする

クィックソートで比較しようか

2008.03.08

さて、このところ「面白い本」の出版が目白押しで困ってます....

3/14 には、例の「プログラミングgacuche」が出るようです。ちょっと関数型言語のプチブームが起きている感じがありますよね。で、少しづつですが、Erlang の勉強(Armstrong)もしています(仕事が少し忙しい....)。

Erlang のイイところ、というのはやはり簡潔さ、です。まあ、関数型言語は一般に「プログラムが簡潔」という利点があるのですが、Erlang はまたかなり特別なくらいに「簡潔」なのです。でまあ、「関数型言語の簡潔さ」をちょっと体験してみようか....という企画ものです。

比較対象は例によってクィックソートです。アルゴリズムとしてはとびきり有名ですし、おもちゃとは言えない実用性もありますからね。言語は

  1. 1. Scheme(Gauche)
  2. 2. Prolog
  3. 3. Haskell
  4. 4. Erlang

というくらいにしましょうか。Prolog は関数型言語じゃありませんが、Erlang に影響が強い非手続型言語(論理型言語)ですから、これに含めます。ソースを載せますが、別にちゃんと理解しなくてもいいですよ! 単に「どうやって簡潔に書くか?」を追求し、そのスタイルを比較して入門する人の参考にまで....と思うだけです。

1. Scheme

まずはクラシックに Scheme から。

(define (sort1 x)
  (cond ((null? x) ())
    (else (append (sort1 (left (car x) (cdr x)))
              (cons (car x)
(sort1 (right (car x) (cdr x))))))))
(define (left a x)
  (cond ((null? x) ())
     ((>= a (car x)) (cons (car x) (left a (cdr x))))
     (else (left a (cdr x)))))

(define (right a x)
  (cond ((null? x) ())
     ((< a (car x)) (cons (car x) (right a (cdr x))))
     (else (right a (cdr x)))))

まあ古典的にはこんな感じでしょう。ただ、left と right が同じような関数になるのが気持ち悪いです....で、今熱い(かな?) gauche だと、コレクションフレームワークに filter 関数があって、これを使うともうちょい簡潔で「Lispっぽい」プログラムにできます。

(use gauche.collection)
(define (sort2 x)
  (cond ((null? x) ())
    (else
     (append (sort2 (filter (lambda (y) (>= (car x) y)) (cdr x)))
         (cons (car x)
               (sort2 (filter (lambda (y) (< (car x) y)) (cdr x)))))))

けど、lambdaカリー化無名関数を作って....というあたり少し難しいかな。

2. Prolog

次は Prolog です。

sort1([],[]).
sort1([X1|X2],Y) :- partition(X1,X2,P1,P2),
    sort1(P1,S1), sort1(P2,S2),
    append(S1,[X1|S2],Y).

partition(X,[],[],[]).
partition(X,[Y|Z],[Y|P1],P2) :- X >= Y, partition(X,Z,P1,P2).
partition(X,[Y|Z],P1,[Y|P2]) :- X < Y, partition(X,Z,P1,P2).

どうしても partition という左右分離述語が必要な感じです。ただし、組み込み述語で持っている append  を使って結果を連結する部分は、いわゆる「差分リスト」(解説)を使うともう少し簡潔にできます。

sort2(X,Y) :- sort2sub(X, Y,[] ).
sort2sub([], Y,Y ).
sort2sub([X1|X2], Y1,Y2 ) :- partition(X1,X2,P1,P2),
    sort2sub(P1, Y1,[X1|S] ), sort2sub(P2, S,Y2 ).

とはいえ、関数型言語ではない Prolog だと、引数に相当する変数と戻り値に相当する変数が区別されない(それが特徴ですが...)ので、読んで理解するには結構コツが要ります....

3. Haskell
sort1 [] = []
sort1 (x:xs) = sort1 [e | e <- xs, e < x] ++ [x] ++ sort1 [e | e <- xs, e >= x]

おお、これは簡潔です!! しかし、Haskell ってインデントによるブロック制御がある(Pythonと同様に...)ので、私はちょっとこれ苦手なスタイルだったりします。でも、いわゆる「リスト内包表記(数学の集合定義みたいに[e|e <- xs, e < x] とやる部分)」と、リスト連結に ++ 演算子が使えるのが Good ですよね! この2つがあるために、余計な partition(left,right) とか要りませんし、append も要りません。

4. Erlang

真打Erlang。

sort1([]) -> [];
sort1([Pivot|T]) -> sort1([X || X <- T, X < Pivot])
    ++ [Pivot] ++
    sort1([X || X <- T, X >= Pivot]).

これもリスト内包表記を持ち、++ によるリスト連結があります。しかも、インデントによるブロック制御ではなく、終端子として「;」(関数定義が終わらずに次の節が続く)か「.」(関数定義終わり)が使われ、フリーフォーマットな言語です。

どっちか言えば、Erlang は関数型言語の仕様としては、Haskell での「面白いけど言語的に難しい要素」(型推論モナド遅延評価)を取り除き、Prolog 風にパターンマッチを強化したもの(とはいえ差分リストは使えません....バックトラックしないからね。出来たら凄いのに)というニュアンスがあります。ですから、「Haskell のエレガンスを大体保持して、ぐっとやさしく実用的にしたモダンな関数型言語」というくらいかな。

ですから、よく「変数は書きかえれない!」というのが大きな特徴として言われますが、実際には「呼ばれるたびに状態が変わる関数」を作ることがちゃんとできます(プロセスディクショナリと言うErlangプロセスと結びついた Map(って Java の ThreadLocal みたいなもの...苦笑) とか ets という一種のデータベースを使います....)。ですから、「副作用がない」と言われますけども、現実的には「副作用のある関数」を書けますし、Haskell のように

たとえば putStr のように、(一般に)戻り値がなくコンソールに出力する(という副作用を持つ)関数を、IO Monad を返す(理論上)副作用のない関数として実装する

というようなややこしい部分はナシのわけです(まあ、コレがあるから Haskell は Haskell なんですけどね)。

Erlang に慣れれば、「Haskell への入門」みたいな感じでも使える...ということにどうやらなりそうです。関数型プログラミング言語へのとっかかりとしても、有用なのかもしれませんね。

投稿者 : 杉浦 こずえ | 投稿日時 : 2008.03.08 12:18

カレンダー

<< 2008年03月 >>

            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          

最新のエントリー

最新のトラックバック

最新のコメント

Tag

バックナンバー