Today アクセスカウンター Yesterday アクセスカウンター

ホワット・ア・ワンダフル・ワールド

私は知識に何ものかを付け加え,また他の人々がより多くのものを付け加える手助けをした --- G.H.ハーディ

全記事一覧 << 2008/06 12345678910111213141516171819202122232425262728293031 2008/08 >>

プロフィール

あろは (alohakun)

  • Author:あろは (alohakun)
  • 若槻俊宏 (WAKATSUKI toshihiro)

    連絡先 : alohakun ___at___ gmail.com
    mixi : http://mixi.jp/show_friend.pl?id=182927
    twitter : http://twitter.com/alohakun

    abstract

    プログラミングという人間の知的行為を体系化し,単なる職人芸ではなく,サイエンスにするための研究をしています.

    具体的には,等価変換計算モデルに基づいた,仕様記述からのプログラム合成の研究をしています.

    もっと噛み砕くと,プログラムの正しさをどのように定式化し,どのような枠組みで,どのように変換を進めていけば,正しさを保証したまま,効率的なプログラムを手に入れることができるのか,ということについて研究しています.

    キーワード : equivalent transformation, computation model, programming paradigm, formal specification, program synthesis













    あわせて読みたい


    この日記のはてなブックマーク数


    スカウター : ホワット・ア・ワンダフル・ワールド


    Map









    FC2 BLOG RANKING

FC2カウンター

ブロとも申請フォーム

この人とブロともになる

LLVM 2.3 を動かしてみる

2008/07/23(水) 13:13:54

なにやら @/id:TAKESAKO さんから 「8/30 の LL Future でパネルディスカッション や ら な い か ?」 (もちろん,実際はもっと非常に丁寧な文章です) というお誘いを受け,ホイホイ快諾してしまったら 「なにやら llvm-gcc を使ってブラウザ上で C とか Python のコードを動かすという構想があるそう.というわけで 『gcc と LLVM が紡ぎだす未来 〜ブラウザで言語処理系を無理やり動かして未来を先取りする〜』 みたいなことをテーマに,gcc フロントエンドとか LLVM とか AVM2 とかと LL の未来についてネタふりしてパネラーの皆さんと楽しく議論してください,超期待してます」 と,いきなりものすごいプレッシャーが.

Running C and Python Code on The Web
C言語をブラウザで実行、Ruby/Python/Perlも然り

なんと交通費まで出していただけることになったので,せめて交通費 + チケット代ぶんぐらいの働きはしないと申し訳なさすぎる.「LLVM は初心者ですが頑張ります

というわけで,まずは hello, world.

YT さんのブログ連載を読んでいると,LLVM イマイチすぎるなという印象を禁じえなかったわけですが (もちろん,LLVM をターゲットとする独自言語のコンパイラを一から書こうとか変なことを考えなければ,もう十分に実用レベルの技術になってます.COINS とかもそうなんですけど,C とか,公式に対応している以外の言語のコンパイラを書こうとすると,とたんにあの機能も足りない,この機能は未実装かッッ!となるのですが…)

最近,最新版の LLVM 2.3 がリリースされたようなので,改善に期待しつつのんびり見ていきましょう.

とりあえず,公式サイトから Windows mingw 用バイナリを落として解凍 (以下,MSYS + MinGW 環境)
http://llvm.org/releases/2.3/llvm-2.3-x86-mingw32.tar.bz2

aloha@LENOVO-A41D2048 /c/tmp
$ tar jxvf llvm-2.3-x86-mingw32.tar.bz2
llvm-2.3/
llvm-2.3/bin/
llvm-2.3/bin/bugpoint.exe
llvm-2.3/bin/fpcmp.exe
llvm-2.3/bin/llc.exe
llvm-2.3/bin/lli.exe
llvm-2.3/bin/llvm-ar.exe
llvm-2.3/bin/llvm-as.exe
llvm-2.3/bin/llvm-bcanalyzer.exe
llvm-2.3/bin/llvm-db.exe
llvm-2.3/bin/llvm-dis.exe
llvm-2.3/bin/llvm-extract.exe
llvm-2.3/bin/llvm-ld.exe
llvm-2.3/bin/llvm-link.exe
llvm-2.3/bin/llvm-nm.exe
llvm-2.3/bin/llvm-PerfectShuffle.exe
llvm-2.3/bin/llvm-prof.exe
llvm-2.3/bin/llvm-ranlib.exe
llvm-2.3/bin/llvm-stub.exe
llvm-2.3/bin/llvmc2.exe
llvm-2.3/bin/opt.exe
llvm-2.3/bin/tblgen.exe

Java で言うところの jasmin (バイトコードアセンブラ) が llvm-as.exe で,java (VM + JIT インタプリタ) が lli.exe,javap (逆アセンブラ) が llvm-dis.exe なんでしょうか.他は gcj (GNU Compiler for Java) みたいに,バイトコードからアセンブラを生成したりするときのツールチェインみたいです.

とりあえず YT さんところの hello-world-llvm (ネタ元は既にリンク切れ) を実行してみましょう.

aloha@LENOVO-A41D2048 /c/tmp/llvm-2.3/test
$ cat test.ll

@.LC0 = internal constant [13 x i8] c"Hello world!\00"

declare i32 @puts(i8 *)

define i32 @main() {
%cast210 = getelementptr [13 x i8]* @.LC0, i64 0, i64 0
call i32 @puts(i8 * %cast210)
ret i32 0
}

$ ../bin/llvm-as.exe test.ll
$ ls

test.bc test.ll test.ll~

$ ../bin/llvm-dis.exe test.bc

c:\tmp\llvm-2.3\bin\llvm-dis.exe: error opening 'test.ll': file exists! Sending to standard output.
; ModuleID = 'test.bc'
@.LC0 = internal constant [13 x i8] c"Hello world!\00" ; <[13 x i8]*> [#uses=1]

declare i32 @puts(i8*)

define i32 @main() {
%cast210 = getelementptr [13 x i8]* @.LC0, i64 0, i64 0 ; [#uses=1]
call i32 @puts( i8* %cast210 ) ; :1 [#uses=0]
ret i32 0
}

$ ../bin/lli.exe test.bc
Hello world!

$ ../bin/llc.exe test.bc
$ ls

test.bc test.ll test.ll~ test.s

$ cat test.s

.text
.align 16
.globl _main
.def _main; .scl 2; .type 32; .endef
_main:
pushl %ebp
Llabel1:
movl %esp, %ebp
Llabel2:
subl $8, %esp
call ___main
movl $_.LC0, (%esp)
call _puts
xorl %eax, %eax
addl $8, %esp
popl %ebp
ret
.data
_.LC0: # .LC0
.asciz "Hello world!"
.def _puts; .scl 2; .type 32; .endef

$ gcc test.s

This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

あらら.たぶん C ランタイムへの依存性とか書いてなかったのが悪いのかな.
一回 llvm-gcc も download して,C から llvm コードを吐かせてみた方がよさそうかも.

とりあえず,ネイティブコードまで落とさなければ実行可能みたいですね.puts が呼べているのは,lli.exe が何やら勝手に libc の関数を呼び出しているらしい.




llvm-gcc を使えば,普通に実行ファイル作れますね.

$ tar jxvf llvm-gcc4.2-2.3-x86-mingw32.tar.bz2
$ cat test.c

#include<stdio.h>

int main() {
puts("hello, world!");
return 0;
}

$ ../bin/llvm-gcc.exe test.c
$ ls

a.exe test.c test.c~

$ ./a.exe
hello, world!

llvm のバイトコードも吐かせることができて,こんな感じになります.

$ ../bin/llvm-gcc.exe -emit-llvm -S test.c
$ cat test.s
; ModuleID = 'test.c'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"

target triple = "i386-mingw32"
@.str = internal constant [14 x i8] c"hello, world!\00" ; <[14 x i8]*> [#uses=1]

define i32 @main() nounwind {
entry:
%retval = alloca i32 ; <i32*> [#uses=2]
%tmp = alloca i32 ; <i32*> [#uses=2]
%"alloca point" = bitcast i32 0 to i32 ; <i32> [#uses=0]
%tmp1 = call i32 @puts( i8* getelementptr ([14 x i8]* @.str, i32 0, i32 0) ) nounwind ; <i32> [#uses=0]
store i32 0, i32* %tmp, align 4
%tmp2 = load i32* %tmp, align 4 ; <i32> [#uses=1]
store i32 %tmp2, i32* %retval, align 4
br label %return

return: ; preds = %entry
%retval3 = load i32* %retval ; <i32> [#uses=1]
ret i32 %retval3
}

declare i32 @puts(i8*)

LLVMTB:0CM:1 このエントリーを含むはてなブックマーク | livedoorクリップ livedoorクリップ BuzzurlにブックマークBuzzurlにブックマーク newsing it!

知識表現とProlog / KR

2008/07/20(日) 21:21:25

えらく古い本 (1985) ですが,たまたま研究室に転がっていたので眺めていたら,けっこう面白かったのでメモ.

知識表現とPROLOG/KR

ET 言語の,D ルールの定義構文 (as *Head | *Body) とか,変数の頭に * (アスタリスク)が付くのとかも,Prolog/KR の as 構文 (assert の略らしい) なのかな ? Prolog/KR も変数の頭に * が付くのか,とか,こういう由来系の情報ってのは面白いです.

Prolog/KR ってのは Lisp と Prolog の融合を進めたような言語のようです.というか,Lisp で書かれた Prolog 処理系のようです.

知識表現の利便性のために拡張された Prolog であり,多重世界の概念でプログラムの階層化(モジュール化)を可能にするそう.特に,AI における知識フレームなどが,一世界一概念という形で素直に対応付けられるらしい.

Prolog/KR は,もともと Utilisp [Chikayama 1981] (日立,富士通のMシリーズ,IBM370 で動く)上に作製されたが,現在 Franzlisp (VAX Unix),Maclisp (DEC-20),Zetalisp (Lisp マシン) の版がある.Lisp マシン版は多重世界機構の拡張とともに Uranus と呼ばれている. (p.70)

あたりに,非常に時代を感じますが,本の内容自体は (非アカデミックの水準では ?) それほど古びてない感じですね.

多重世界機構とか,リストでプログラムが表現されている(メタ記述が容易)とか,パターンマッチング機能がある,自動バックトラッキング部分と,決定的な部分が分離されているのでユーザが任意のプログラミングスタイルを選択できる,などは,まんま ET 言語にもあてはまりますね.なるほど,かなり大きな影響を受けているようです.ET のワールド機構,D ルールと N ルールの区別,単一化とパターンマッチングの分離 (Prolog から,より純粋なルール型言語へ.高レベルから低レベルまでを柔軟に記述可能) などにそのまま対応します.

多重世界機構の応用例として,Smalltalk の持つクラス間の階層構造を,そのまま素直に多重世界の入れ子構造で表現して,Tiny Smalltalk の処理系を十数行で実装したりしたりとか,なかなか面白い本です.

ちょっと検索したみたら,こんな記述も.

100 年 Windows 横山哲也 2006年09月12日 渕一博氏を偲ぶ

Prologは,プログラム言語としてはかなり未完成であった。例えば,まともなプログラムを書くには,カットオペレータという演算子が必須である。ところが,カットオペレータの強力さと単純さはGOTO文の比ではなく,結果としてプログラムの見通しは極めて悪いものとなった。そこで,研究者の間では,述語論理型言語にどのような制御構造が必要かという考察が行われていたことを記憶している。私は,自分の研究に,中島秀之氏(現公立はこだて未来大学学長)の作成したProlog/KRを使うことにした。当時,オンライン・コミュニティはあまり発達しておらず,中島氏が所属していた東京大学まで電話をして磁気テープを送ってもらったことを覚えている。もちろんオープンリールである。

 Prolog/KRは,LispとPrologと融合した言語で,十分な制御構造が備わっていた。ただし,追加された制御構造は手続き型の側面が強く,述語論理の特徴を生かせていたとは言い切れない。ところで,どうでもいいことだが,1986年に広島で開催された情報処理学会全国大会で偶然中島氏をお見かけしたので,著書にサインをいただいた。今でも大事にとってある。

 一方,ICOTではPrologを拡張したGHC(Guarded Horn Clause)をベースに,KL-1を開発した。こちらは,述語論理の特徴を生かし,さらに並列処理まで実現していた。ただ,Prolog固有の構文が色濃く残っており,慣れないと使いこなすのは難しいだろう。





追記

Common Lisp 上で動く Prolog/KR 処理系が存在するようです.

Uranus Prolog/KR
BookTB:0CM:0 このエントリーを含むはてなブックマーク | livedoorクリップ livedoorクリップ BuzzurlにブックマークBuzzurlにブックマーク newsing it!

Thinkpad X61s (7666-77J) 購入

2008/07/17(木) 20:57:27

5 年ぐらいぶりに新しい PC 買いました.あと,我が家で初めての Windows 機です.

ずっと,学会やゼミ,勉強会などのために,持ち運びがしやすい note PC が欲しかったのですが.

期待していた新型の EeePC も,高い重いデカいと散々な感じで,一時は MacBook の中古で良い出物があった (core 2 duo 2.0 GHz / Mem 2 G / 英語キーボード) ので,心が動きかけたのですが.やはり,白い note PC とか無いなと (あと,大きくて持ち運びしんどそうだし.Mac はハードの選択肢がほとんど無いのが…).

そんなこんなでいろいろ悩んでいたところ,タイムリーなことに,先週の i-うぃん堂 の特価セールで,Thinkpad X61 と X61s が同じ値段で安売りされていました.夏の感謝セールとかで,送料が無料の上,8 万円以上のアウトレット品を買うと無料でメモリ 1 GB 増設キャンペーン (計 2 GB積まれる) とかもありーので,代引き手数料込みで 85430 円.

やはり Thinkpad は超カッコいい.これだよこれ,他の軽量モバイル note PC など全くに相手にならない.これは買うしか無いでしょう.

X61 と X61s のどちらにしようか迷ったのですが,

(1) 基本的に s の方が軽量化のため元値が高価 (231000 円 vs 168000 円)なのでお得 (まぁ,アウトレット品なので微妙なんですが)

(2) X61 の方は CPU クロックが上 (core 2 duo 2.2 GHz) なのは良いものの,発熱量が多そう (Matz さんが低温火傷という事例あり).X61s は 1.4 GHz なので,クロックは下ではあるが,もともとモバイル note PC に速度など求めてないので,発熱量が低い方が良いに決まってる.

(3) X61 は Windows Vista が初期インストール (X61s は XP) だが,おそらくビデオチップがチップセット内臓で,メモリが 2 GB 程度で HDD も低速の X61 では使い物にならない

(4) X61s ならば重量も 1.3 kg 弱ぐらいなので,1 kg 弱ぐらいの UMPC と重さ自体はそれほど変わらない (X61 だと 1.43 g ぐらいで 500 g ぐらい違う).

というわけで X61s に決定しました.X61 が X30 系列 (パワフルモバイル)で X61s が X40 系列 (スリムモバイル) らしいです.

僕は Thinkpad の X40 に強い憧れがあったのですが,その後継機種がこんなに安く手に入るとは.

防水キーボードでコーヒーがこぼれても大丈夫「火事の炎にさらされ、消火ホースからの水を浴び、2階の窓から放り投げられ、さらに数昼夜の間ずぶ濡れになった家財道具の残骸にまみれ」ても全てのデータが無事だったなど,数々のレジェンドに彩られた愛すべき過剰品質,プロフェッショナル御用達の高級機種の代名詞だった Thinkpad.

それが中国企業 lenovo によりコモディティ化し,単なるイチ家電製品になってしまったということなのでしょうね.常に僕達の憧れだった,赤緑青に輝く IBM のロゴが消えてしまったのは悲しいですが,そのおかげで,僕のような貧乏学生の手にも届く価格帯にまで降りてきてくれたわけで,これはこれで大変素晴らしいことだと思います.

まだ今のところは IBM のチェックもしっかりしていて,生産体制にも以前と比べて大きな変化は無いようですし,X61 は評判がなかなか良い感じです.大事にしようと思います.
メモTB:0CM:0 このエントリーを含むはてなブックマーク | livedoorクリップ livedoorクリップ BuzzurlにブックマークBuzzurlにブックマーク newsing it!

1+1=2を証明するためには1万ステップ以上かかるよ,という話

2008/07/17(木) 18:31:55

なんかすごいサイトを見つけてしまいました.

Metamath Proof Explorer Home Page

数学の基礎付けに関する 20 世紀の記念碑的偉業と称えられながらも,歴史上何人がこれまで読破したのか,と常にネタにされる Principia Mathematica (12 万円,2000 ページ!) に,1+1=2 の証明が載ってるっていうのはわりと有名な話だと思いますけど.

追記 : Radium Software Development 2006-06-30 : Proof that 1 + 1 = 2

# ちなみに,三巻組の大著の全文をオンラインで見ることができます."From this proposition it will follow, when arithmetical addition has been defined, that 1+ 1= 2."

このサイトでは,全ての定理が索引付けでハイパーリンクされていて,例の 1 + 1 = 2 の証明も,トップレベルから全てのサブ命題を追うことが可能になってます.

Theorem o1p1e2 4165

なんと 1518 個のサブ定理を 11086 ステップかけて証明する必要があるそう.

定理っていうのは,プログラムにおけるサブルーチンみたいなものなんですけど.
もし,途中の定理を全て「インライン展開」すると 10 億ステップを超えるとか.




ちなみに,us.metamath.org では,現代公理的集合論 ZFC (1+1=2 程度ならば,公理 C は必要ないみたいですが) を数学の基礎においているみたいですが,PM の初版では分岐階型理論 (theory of types),2 版では単純階型理論 (simple theory of types) という定式化が採用されているそうです

ラッセルの論理学は確かに時代後れである。ゲーデルその他の数理論理学者の批判をまつまでもなく、ラッセルの論理学が厳密さを欠いているということは、いまや周知の事実である。たとえば、『数学原理』には公理は与えられているが、推論法則を欠いている。したがって、やかましくいえば、『数学原理』において公理以外の定理を導出することは不可能である。また、初版において用いられている分岐階型理論においても、また、一九二五年に発表された第二版において採択された単純階型理論においても、その定式化は甚だしく厳密さを欠いている。そして、これらの理論が組合せ論理学の立場から正しく再構成されたのは比較的最近のことなのである。

(中略)

すでに述べたように、『数学原理』に内在するいろいろの技術的欠陥を現在の進んだ立場からあげつらうことはむづかしいことではない。しかし、理性の分析、あるいは、その再構成という仕事に哲学史上はじめて着手することによって、十九世紀的理性、あるいは、ドイツ観念論的理性と訣別して現代への第一歩を踏みだしたという点において、『数学原理』に代表されるラッセルの論理学の功績は永遠に残るであろう。したがって、『数学原理』が現代ヨーロッパにおげる最高の思想的所産であるというボヘンスキーの手放しの礼讃もけっして誇張ではあるまい。

ラッセルは哲学者で,メタ数学は 「数理哲学」 なんですよね.数学の道具を使って,人間知性を哲学している.

もう一つ引用.

バートランド・ラッセルのポータルサイト (著書解題4)ラッセル著『数理哲学序説』(中村秀吉・解題) 『ラッセル協会会報』n.4(1966年5月)pp.3-5.

ラッセルのこの方面で業績は、師のホワイトヘッドとの共著である大作『数学原理』に集大成されているといってよい。かれは1900年から1910年頃までの、かれの人生における最良の10年間をこの仕事の完成に惜しみなくささげたのである。しかしこの本は非常に大冊であるばかりか、かなり冗長な、ほとんど退屈な記号の羅列なので、実際に通読した人はほとんどないといっても過言ではあるまい。これを通読した人は一ダースしかいないだろうとか、ことによると、これを書いたラッセルとホワイトヘッドだけではなかろうか、などといううわさもたてられたほどである。しかしラッセル自身はここにとりあげる『数理哲学入門』において、ほとんど記号を使わないでその平易な解説を試みたのである。この『数理哲学入門』は、ラッセルが1918年5月から1919年9月まで(松下注:「1918年9月」の間違い)、反戦運動のかどで、獄につながれていた間に一気に書き上げたもの(注:獄中での執筆)である。われわれは彼の集中力にも驚くのであるが、同時に、いかほど自分がやったことの要約とはいえ、ほとんど参考書もない不便ななかで、これほど明晰かつ性格に『数学原理』の要点を叙述できたことに一驚を禁ぜざるえないのである。
本書ではまず数学のもっとも基本的概念である自然数列から問題が説き起こされ、自然数の定義が導入される。がんらい哲学では、自然数を何か感性的対象とふつうの一般者との両面をもったもの、ないしその中間者として、独自の対象と考えられてきた。一方、ペアノは自然数の公理系をつくるのに成功し、ある命題群を満足する勝手のものとして自然数を陰伏的に定義した。ラッセルはこの両方の考え方にあきたらず、個々の自然数を相似な、個物のクラスのクラスとして定義した。これによって個々の自然数は純粋に論理的な慨念であるクラスに還元されることになり、その把握に何か特殊な直感力のようなものを必要としなくなったのである。同時に、ペアノの公理とは違って現実的個物との関係もつき、一と他の関係のような哲学的アポリアにも一応の答を用意できることとなった。
メモTB:0CM:3 このエントリーを含むはてなブックマーク | livedoorクリップ livedoorクリップ BuzzurlにブックマークBuzzurlにブックマーク newsing it!

初心者にプログラミングを教える際の難しさ

2008/07/16(水) 13:36:46

今のプログラミング言語は,アルゴリズム (計算手順) を書き下す (だけの) ものなんですよね.

なので,初心者にプログラミングを教える際 「どうやってアルゴリズムを作れば良いのか ?」「熟練者は,どのように発想しているのか ?」 ということを教える際には,向きません.これがプログラミング教育の本質的な難しさです.

アルゴリズムを作るための方法論と,それを表現できるプログラミング言語が無いから,結局はたくさん本読ませて,問題解かせて,自分で勉強してがんばってね,数こなせば自然とわかってくるから,という前時代的な教育しかできないのです.これでは脱落者がたくさん出てしまっても無理はありません.

amachang さんががんばってます.執筆中のマインドマップを引用するってのは,ちょっと申し訳ない気もするのですが,面白い一文を発見.

IT 戦記 2008-07-15 プログラミング未経験者が JavaScript でプログラミングをするために必要なこと
僕はプログラミングというものをこういう風に思っています。


「状態と機能をたくさん持ったモノ」(例えば、パソコン)に、「こうだったら(状態)、こうする(機能)」という「ルール」を書いていって「便利なモノ」(例えば、ゲーム)を作る作業がプログラミングである。


これは全くその通りなのだと思いますけど,現在のプログラミング言語は,こういう人間の自然な思考(?)を素直に書き下すようにはできてないんですよね.

我田引水ですけど,僕は北大の一般教養で,今 TA やってます (問題解決プログラミング/人工知能プログラミングの両クラス合同演習).

# 人工知能とか大仰な講義名ですけど,学部一年レベルの講義なので,ようするに,ちょっと高度なアルゴリズムのことです.全学共通科目なので,工学部や情報系以外の学生もウェルカムな講義ですし (まぁ,ほぼ全員が理系だと思いますけど)

プログラミングどころか,パソコンのタッチタイプすらおぼつかない大学新入生相手に,いきなり ET という変なプログラミング言語を使って,アルゴリズムの作り方 (発想法) を教えています.

よくある「プログラミング」を教える講義,すなわち,アルゴリズムの書き下し方 (コーディング) を教えるのではありません.アルゴリズムの作り方,考えるための方法論を教えている (つもりの,ことを目指している) 講義です.

それは,例えばプログラミング言語 Ruby は,(いろいろ理由があると思いますが)学生が学習しやすい,とかいうレベルの話ではありません.

ET 言語は,ルールベースなので,通常のアルゴリズムを書き下す言語とは,根本的に異なるのです (もちろん,普通に,アルゴリズムを書き下すこともできますが.それは清書用で,むしろどうやって考えるか,考えるための道具の方が重要)

ルールというのは,amachang の定義を借りれば,

状態,{条件} --> こうする.

という,まさしく自然な発想をそのまま書き下すような表記になっています.

そして,具体例をたくさん書き並べていくだけで,それもある種のプログラムとして実行可能です (算術演算アトムの記法が,Lisp というか,S 式ライクで微妙ですが… まぁ,全くの初心者の場合,こう書くんだよ,と言うと,案外素直に覚えてくれるものです.逆に,脳が C とか VB とかに汚染されている子(笑)の場合は,ちょっと戸惑ったり苦労しているみたいです).

(factrial 0 *x) --> (= *x 1).
(factrial 1 *x) --> (:= *x (x 1 1)).
(factrial 2 *x) --> (:= *x (x 2 (x 1 1))).
(factrial 3 *x) --> (:= *x (x 3 (x 2 (x 1 1)))).

いろいろルールを書いていくうちに,何らかの法則性が見えてきたら,より一般的なルールを書くと.

(factrial *n *x) --> (:= *n1 (- *n 1)), (factrial *n1 *x1), (:= *x (x *n *x1)).

# ちょっとトリビアルすぎる例ですが… 実際の講義では,非常に簡単で具体的な例題 (長さ 3 のリストの 2 番目を取り出すルールを書け,とか) から,徐々に一般的で複雑な例題に (任意の長さの整数リストの各要素の値を n 倍したリストを作るルールを書け,のように) 発展していきます.

実際には,D ルールには優先順位がある (同じ状態と条件に対して適用可能なルールが複数存在する場合,先に定義されたルールが,後に定義されたルールよりも優先的に採用される) のですが,条件を順序に依存しないようにちゃんと書けば,順番さえ任意です.

ルールベースのプログラミング言語は,条件を工夫したり,効率化するためのルールを追加していくことで,試行錯誤しながら,自然とルールを積み上げ,アルゴリズムを構築していくことが可能な枠組みになってます.
雑談TB:0CM:0 このエントリーを含むはてなブックマーク | livedoorクリップ livedoorクリップ BuzzurlにブックマークBuzzurlにブックマーク newsing it!

最近のコメント

リンク

このブログをリンクに追加する

最近のトラックバック

人生の残り日数

日本人男性の平均寿命は 28700日.

RSSフィード

カテゴリー