Lisp Scheme Part26

1 名前：デフォルトの名無しさん mailto:sage [2009/04/24(金) 19:12:39 ] ※ ここはCommon Lisp、SchemeをはじめとするLisp族全般のスレです ※ ■過去スレ 　Part25: ttp://pc12.2ch.net/test/read.cgi/tech/1231856193/ 　Part24: ttp://pc11.2ch.net/test/read.cgi/tech/1224939205/ 　Part23: ttp://pc11.2ch.net/test/read.cgi/tech/1215875388/ 　Part22: ttp://pc11.2ch.net/test/read.cgi/tech/1211381920/ 　Part21: ttp://pc11.2ch.net/test/read.cgi/tech/1207300697/ 　Part20: ttp://pc11.2ch.net/test/read.cgi/tech/1205021786/ 　Part19: ttp://pc11.2ch.net/test/read.cgi/tech/1200237296/ 　Part18: ttp://pc11.2ch.net/test/read.cgi/tech/1186922295/ 　Part17: ttp://pc11.2ch.net/test/read.cgi/tech/1177065699/ 　Part16: ttp://pc11.2ch.net/test/read.cgi/tech/1172404795/ 　Part15: ttp://pc11.2ch.net/test/read.cgi/tech/1151025773/ 　Part14: ttp://pc11.2ch.net/test/read.cgi/tech/1132275726/ 　Part13: ttp://pc11.2ch.net/test/read.cgi/tech/1115901841/ 　Part12: ttp://pc11.2ch.net/test/read.cgi/tech/1100229366/ 　Part11: ttp://pc11.2ch.net/test/read.cgi/tech/1091456033/ 　Part10: ttp://pc11.2ch.net/test/read.cgi/tech/1075630259/ 　Part09: ttp://pc11.2ch.net/test/read.cgi/tech/1069594582/ 　Part08: ttp://pc5.2ch.net/tech/kako/1058/10582/1058263391.html 　Part07: ttp://pc5.2ch.net/tech/kako/1042/10421/1042167213.html 　Part06: ttp://pc3.2ch.net/tech/kako/1031/10315/1031560687.html 　Part05: ttp://pc3.2ch.net/tech/kako/1023/10230/1023091882.html 　Part04: ttp://pc.2ch.net/tech/kako/1016/10162/1016211619.html 　Part03: ttp://pc.2ch.net/tech/kako/1008/10082/1008220265.html 　Part02: ttp://pc.2ch.net/tech/kako/1002/10025/1002584344.html 　Part01: ttp://piza2.2ch.net/tech/kako/987/987169286.html ■テンプレート置き場 　ttp://wiki.fdiary.net/lisp/ (id:guest pass:cl) 652 名前：デフォルトの名無しさん mailto:sage [2009/07/03(金) 18:29:18 ] LISPの本と思わずに、T先生と生徒のかけあいを楽しめばいいんだ。 653 名前：デフォルトの名無しさん mailto:sage [2009/07/03(金) 20:12:01 ] 初心者向けと書かれるとおれそんなんじゃないし読むことないや と結局買っても積んだままにしてしまう お決まりの言語のおさらいを数章割かれてるのを見ると頭に来るからだ いっそのこと超上級者向けのが興味をそそられる 654 名前：デフォルトの名無しさん mailto:sage [2009/07/03(金) 20:24:17 ] >>653 SICP も初心者向だよwW 655 名前：デフォルトの名無しさん mailto:sage [2009/07/03(金) 21:51:02 ] だから1章で飽きて放り投げちゃったんだよ。 656 名前：デフォルトの名無しさん mailto:sage [2009/07/03(金) 22:05:20 ] 目次みて1章はつまんなそうだと思ったら3章あたりから読み始めればよかったのに。 657 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 00:37:31 ] 良い本は、 例え初心者向けと銘打たれていても、 光る記述で満ち溢れており、 熟練者でも楽しめるものなのだ。 だからグルの書いた本は面白いのだ。 658 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 01:45:12 ] 苫米地先生の事ですね。わかります。 659 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 01:54:17 ] >>658 ビビッタ。 実は、最近なぜか洗脳について勉強していたりする。関係あるの？ 660 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 02:01:58 ] Lisperじゃん。 661 名前：デフォルトの名無しさん [2009/07/04(土) 02:02:46 ] とまちゃんだけはガチ 662 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 02:04:31 ] sage忘れたすまぬ 663 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 03:21:58 ] 竹内本は目次の時点で駄目だな 664 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 03:34:00 ] 無縁の衆生ですな。 665 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 05:49:37 ] >>655 もったいないお化けが出るぞ 666 名前：デフォルトの名無しさん mailto:sage [2009/07/04(土) 19:46:29 ] The Little Schemer買ったお。たくさん勉強するお。 667 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 10:42:05 ] shibuya.lispどうだった、行った人？ 668 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 12:41:05 ] >>667 面白かったよ。#4あるならLTしようと思ったくらいには(TTはなんいどたかい)。 669 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 12:47:18 ] すみません、以下のプログラム想定外なことだらけなのですが 以下のs1で、値が変更出来るようなプログラムは書けますか？ schemeは値渡しなので無理なような気もしますが また、test関数では内部でtをset!しているにもかかわらず その変更は影響がないように見えますが何故なのでしょうか (define (s1 t v) (set! t v)) (define (sa t v) (set-car! t v)) (define (sd t v) (set-cdr! t v)) (define (sa2 t v) (let ((r (cdr t))) (set-car! r v))) (define (test f) (define t '(()())) (let ((r (f t 1))) (print t) (set! t '(()())) r)) (test s1) (test sa) (test s1) ;why? (test sd) (test sa2) ;(map test (list s1 sa sd sa2)) 670 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 13:11:03 ] 引数のバインディング変えても外からは見えないだろ。 int f(int x) { x = 10; } やってるのはこれと同じ 671 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 13:17:32 ] >>669 set! は変数とオブジェクトの結び付き (束縛) を付け替えるオペレータ。 set-car! や set-cdr! はオブジェクト (consセル) の中身を変更するオペレータ。 ってことを念頭に置いて考えるとわかりやすいかも。 あまりに根本的すぎることなのでそこを理解できてないようだとちょっと説明しづらい。 672 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 13:26:06 ] > また、test関数では内部でtをset!しているにもかかわらず > その変更は影響がないように見えますが何故なのでしょうか 処理系がわからんから何とも言えんが、 おそらくその処理系は、クォートされたリストをすべての関数呼び出しで共有するように作られているんだと思う。 test 内の (define t '(()())) のところでは、 すべての関数呼び出しで共有される '(()()) というリストを t に束縛する、みたいな処理が行われる。 そこで、(test sa) を実行してしまうと、そのリストが '(1 ()) に書き換えられてしまう。 そのため、次回以降の test の呼び出しでは、'(1 ()) というリストが t に束縛されてしまう。 そもそも scheme では、クォートされたリストに set-car!、set-cdr! しちゃいけないことになってるので、 こんな処理をすること自体が間違い。 やるんだったら、毎回リストを生成するようにする。 (define t (list '() '()) 673 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 13:55:51 ] 問題をきちんと理解してから解答を考えよう って約束したじゃないですかー 674 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 14:02:00 ] >>672 > 処理系がわからんから何とも言えんが、 むしろ何も言うな 675 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 14:29:33 ] おまえがな。 676 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 15:05:14 ] shibuya.lispの参加者、もっと感想・ネタを書いてくれ。 悪口・不満的な話は、直接、主催者にメールでもしてくれ。 677 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 15:24:01 ] いずれ上がるだろう動画を楽しみに待つ 678 名前：デフォルトの名無しさん [2009/07/05(日) 15:48:43 ] つ www.nicovideo.jp/mylist/13373941 679 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 15:53:09 ] ニコに挙げたのか つべで探してたわ 680 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 15:53:51 ] 感謝。既に上がってるのは想定外だった 681 名前：デフォルトの名無しさん [2009/07/05(日) 15:54:39 ] つべはこっち。 www.youtube.com/view_play_list?p=C7D5490AD455E464 682 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 17:24:59 ] >>670-672 ありがとうございます >>671 関数の引数はjavaのように、 実体を指すポインタのコピーが渡ると考えれば良いですよね set!だとコピーしたポインタ自体を変更しても元データには全く影響がないが set-car!だと、コピーしたポインタの指す先を変更するので 引数にset-car!しても破壊的変更が可能 だとすれば、参照渡しで実現出来る 関数の実引数の実体を直接書き換えるような 関数の作成は不可能ですね >>672 >そもそも scheme では、クォートされたリストに set-car!、set-cdr! しちゃいけない これは初めて知りました。これが原因ですね コードはGaucheとGuileで試したのですが どちらもクォートされたリストは共有されるような実装ってことですね 683 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 18:31:28 ] >>682 > クォートされたリストは共有されるような実装ってことですね 確か Gauche の場合は REPL が起動してるときは共有されないはず。 だからといってそれを期待しちゃだめなんだけど。 Gauche のマニュアルから引用 ↓ 注: R5RSは、リテラル式の値を変更するのはエラーであるとしています。 しかしGaucheはペアとベクタについてはそれが定数であるかどうかをチェックしておらず、 set-car!やvector-set!等の破壊的手続きによってそれらの値を変更してもエラーは報告されません。 そうした場合の動作は不定です。 684 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 18:45:19 ] 参照渡しって何か ダイナミックスコープっぽいような気がするけど この二つは何か関係あるのかな？ 685 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 18:48:13 ] >>684 関係ない。 686 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 18:49:34 ] 全く関係ない。 参照渡しは仮引数/実引数バインディングスタイルの一つ ダイナミックスコープは自由変数のルックアップスタイルの一つ 687 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 18:52:02 ] そんなめんどうな話なのか？ 局所変数と大域変数の話なのでは。 湯浅先生の「Scheme入門」だとP３２〜。 688 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 18:58:16 ] koguro さんのトークは資料が見やすくていいなー 689 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 19:13:16 ] いちいちそんな糞本挙げなくていいよ 690 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 19:19:18 ] 湯浅先生を糞呼ばわりできるお前って何様？ 691 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 19:23:28 ] 俺は>>689じゃないけど、その先生が立派な人で、その本が立派なものだったとしても時代にそぐわなくなることってあると思うんだよなー。 湯浅先生の名前があればもう否定しどころがないみたいな言い方じゃなくて、もっと良い点と悪い点を検討する必要はあるんじゃないの？ もちろん、糞本って言う方もどのへんが糞なのか示さないと議論にならんけど。 692 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 19:49:36 ] とりあえず糞って言っとこう的な煽りは2chの華だねｗ 693 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 19:51:06 ] たいした人でもないのに いちいち先生つけるなよ 694 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 19:52:53 ] 何の脈絡もなく 湯浅の糞本持ち出す687ってなんなんだろう？ 695 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 20:03:58 ] 名著はちゃんと読んだ方がいいと思うぞ。 おっと、ここは2chだったな。玉石混交ですな。 696 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 20:13:11 ] 読む本は選べ 時間の無駄 697 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 21:01:42 ] 嫉妬ってみっともないなとオモタ 698 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 21:05:35 ] 糞本の宣伝に嫉妬とか 699 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 21:06:09 ] 釣れますか 700 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 21:18:47 ] >>690 生暖かく見守っといてやれって。 701 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 21:24:08 ] 湯浅の本なんて有り難がってよんでんのか 702 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 22:23:54 ] ところでここLispスレ 703 名前：デフォルトの名無しさん mailto:sage [2009/07/05(日) 23:57:54 ] うっかりSICP 704 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 05:04:12 ] >>677 そういうことじゃないだろ。 実際に参加したの感想が聞きたいんだが。 いいアイデアが浮かんだとか、もっと○○の分野を勉強しようと思ったとか、その他いろいろ。 705 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 08:04:38 ] マ板行けよ 706 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 09:12:44 ] Scheme入門はちょっと古すぎる気がしないでもないな 内容もCommonLisp入門とほぼ同じだし。 でも絶版とはいえ某所でpdfでくばってたから結構読んでる人は居るんじゃないかな 707 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 12:32:27 ] >>701 ありがたがってるかどうか別として、先人への敬意が無い連中って 人として問題ありってことだと思うよ。 708 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 12:47:26 ] 世界初のCL実装 709 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 12:48:13 ] 世界初のCL実装でしょ。 MITあたりの人達もびっくりしたという。 710 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 12:52:02 ] Little Schemerに出てくるYコンビネーターってどういう利点があるの？ 難しくてめげそう。だれか教えれ。ﾌﾟﾘｰｽﾞ 711 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 12:56:15 ] 実用上たいして意味は無い (define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))) みたいなのを、factっていう名前を使わずに 無名関数のみで定義できるという意義がある 712 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 12:57:21 ] そうそう。KCLをわずか2人で開発した日本が世界に誇るLisperだぜ。 本の内容は今となっては古い部分もあるが基本的な考え方は変わらないだろ。 713 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:01:27 ] util.sparse が組込みになってないのは、 やっぱ普通のスクリプト言語的用途だと従来のハッシュテーブルの方が効率はいいってことでいいんだよね？ 714 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:08:15 ] >>710 無名関数のみで定義できるという意義ってﾅｰﾇ？ 715 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:13:46 ] λ計算には関数定義なんてない 無名関数だけで再帰の計算が出来ることがわかれば λ計算だけで、色々な計算が出来ることが示せるわけ 716 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:16:46 ] ｽﾏﾇ。 λ計算だけで、色々な計算が出来ることが示せると何が証明できるの？ 717 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:19:42 ] ちょっとは自分で調べれ チャーチ・チューリングとかでググってみそ 718 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:26:54 ] >>717 ググッた。 「チャーチ＝チューリングのテーゼとは、「計算できる関数」という直観的な概念を、帰納的関数と呼ばれる数論的関数のクラスと同一視しようという主張である。 このクラスはチューリング・マシンで実行できるプログラムのクラス、ラムダ記法で定義できる関数のクラスとも一致する。 よって簡単にはテーゼは、計算が可能な関数とは、その計算を実行できるような有限のアルゴリズムが存在するような関数、 よっておおよそコンピュータで実行できる関数と同じだと主張する。」 つまり、「SchemeはYコンビネータがあれば計算可能な再帰関数を有限のステップで計算可能ですYO!」ってことでおｋ？ 719 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:31:18 ] 「あれば」じゃなくて「あるので」の方が正しいﾆﾎﾝｺﾞかなｗ 720 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 13:38:34 ] schemeはYコンビネータを使わなくても計算可能な関数は計算出来る 普通の名前つきの再帰関数やletrecなどが実質Yコンビネータに相当 721 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 14:22:44 ] ＞普通の名前つきの再帰関数やletrecなどが実質Yコンビネータに相当 おお、そういうことなのか。でもよく考えると「計算できる関数」ってどういう意味かわからん。 とりあえず漏れの使う程度の関数は「計算できる関数」ってことか？ じゃ、無限ループするようなバグがある関数は「計算できない関数」ってクラスなのか？ どういう違いがあるとそうなるんだろう？ 722 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 14:49:14 ] 「Lisp脳」の謎に迫る - Schemeプログラマの発想 karetta.jp/book-node/gauche-hacks/023107 上のページのように問題をリストの加工と捉えて (map 何らかの加工 (iota 100 1)) という風にすると、確かに処理が分かりやすいんだけど、 一旦、処理の過程の無駄なリストにメモリが使われますよね。 iota 10000000000 とかリストがでかくなった時を考えると、困ると思うのですが 僕が神経質なだけでしょうか。 723 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 15:07:17 ] (map f (iota 100 1))の場合で、仮にリストを順に辿って最後に結果を返す関数をgとして (g (map f (iota 100 1))のようにすればgの実装次第では コンパイルの結果、Cでfor (i = 1; i <= 100; ++i) {...}と書いたようなループになって 中間リストは一切作られない…ような最適化をする為の理論とかはあります common lispのseriesライブラリ等は、この手の中間リスト消去をある程度してくれると聞いてます 724 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 15:43:34 ] >>722 無駄を省くプログラミング技術はLisp, Schemeでも重要。 ただし、よいプログラマは本当に無駄なところだけ、改良しようとする。 (iota 1 10000000000)のセル消費が他に比べて負担が 大きいプログラムの多くはトイプログラムじゃないですか? 725 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 16:10:07 ] Haskellでも使えばいい 726 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 16:49:50 ] >>722 SICPにある遅延を使ったストリームによればいいんじゃない。 今のコンピューターはたっぷりメモリがあるんだし富豪プログラミングでも いいとは思うけど。 727 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 19:09:25 ] >>721 「ゲーデルの世界」（海鳴社）にそういった計算可能関数の話があった。 今、読んでいるところ。λ、チューリングマシンとの関係の説明も あったと思う。とりあえず原始帰納的関数から理解しようとしている。 Schemeが理解の助けになるかもしれない。 728 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 20:34:49 ] >>723-726 ありがとうございます。 >>724 ＞本当に無駄なところだけ やたらめったら改良するより、労力のコスパが高いところを見つけて改良すれば十分って話ですよね。 >>726 3.5.1にこの話題が出てますね。 ちょっと難しいけど、これがベストな解決策だろうなぁ。 遅延ストリームを使い始めると、何でこれ遅延ストリーム使わないの！！って思うようになりそうだ。 ＞富豪プログラミングでもいいとは思うけど。 反復だと時間さえかければ解けるものが リスト渡しだと記憶空間の限界に達したら絶対に解けないというのは 僕には気持ち悪さが残ります。 729 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 20:39:24 ] 足りなくなったら考えればいいのよ 730 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 20:59:14 ] 2000年問題、文字コード、IP枯渇・・・ 731 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 21:38:55 ] >>727 チャーチ＝チューリングのテーゼによれば、アルゴリズムのある関数は全て計算可能である。 つまり、アルゴリズムを学ぶことが計算可能関数を学ぶことに相当している。 そしてアルゴリズムを学ぶ際にはSchemeが理解の助けになる。 簡単にまとめると、「Yコンビネータがあるチューリング完全な言語ではアルゴリズムのある関数は全て計算可能である」ということになる。 あたりまえの事だけど、数学的に保証してくれてるので安心してプログラミングして計算ができるわけだ。 732 名前：デフォルトの名無しさん mailto:sage [2009/07/06(月) 23:58:44 ] Yコンビネータの話とλ計算の話をごっちゃにしてはいけない。 コンビネータの話とλ計算の話はもともと別の話。それが途中で コンビネータの理論はλ計算の理論に翻訳可能だとわかったので、 同時に語られることが多いというだけ。 コンビネータ理論の歴史は古くて1920年代にSchonfinkelと言う人が始めて Curry（カリー化のカリー）が発展させた。 733 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 00:18:57 ] Yコンビネータに関する疑問について言えば、Yコンビネータの存在意義という のは、確か再帰の概念が存在しない言語において再帰と同等の物を導入するため、 だったと思う。 734 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 00:50:34 ] そういえば、ものまね鳥、あれからすぐに図書館に 返したんだけど。借りられたかな。 735 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 01:25:05 ] ここで>>368のリンク先にあるラムダ式を簡約するArcのプログラムを読むと感動すること請け合いである。 736 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 07:39:45 ] >>713 詳しいことはドキュメントに書いてあるよ 737 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 11:14:49 ] まだ実験的なものかと思ってたのでドキュメント見てなかった でも、英語の説明しかねーや。 読むのめんどい。 ところで、 sparse って名前だと sparse な何かわからんので、 モジュール名はあんまりよくないと思った。 Scheme 処理系に入ってたら、 S式をパースするものっぽい気もしてしまう… 738 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 11:28:27 ] 保守的GCと心中する気がなければ、ただの一時しのぎだろ 739 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 20:07:45 ] >>737 > Scheme 処理系に入ってたら、 S式をパースするものっぽい気もしてしまう… その発想は鳴かった 740 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 23:26:48 ] >>731 計算可能な関数には３つの系譜があるようだ。 ○ゲーデル〜クリーニ　一般帰納的関数 ○チャーチ　λ−定義可能な関数 ○チューリング　チューリングマシンで実行できる関数 ゲーデルの流れだと原始帰納的関数は計算可能関数。 Lispの本の例題に登場するアッカーマン関数は原始帰納的関数ではないのだけど 帰納的関数であり計算可能関数らしい。階乗計算とかフィボナッチ数とかは 原始帰納的関数なんだと思う。詳しい方、間違ってたら補正してください。 741 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 23:49:28 ] >>740 チューリングマシンと等価なのは部分再帰関数であって、原始再帰関数は 部分再帰関数の部分集合に過ぎない。 742 名前：デフォルトの名無しさん mailto:sage [2009/07/07(火) 23:54:14 ] >>740 あんまりわかんないなら，書き込まなくていいと思う． 743 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 00:23:08 ] ボイスコッド正規形ならクリーニアンクロージャ作れるからラムディ 744 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 00:46:46 ] 帰納的定義のackermann functionってこんな感じ？ (define (iter f n) (if (= n 0) (f 1) (f (iter f (- n 1))))) (define (ack n) (if (= n 0) (lambda (m) (+ m 1)) (lambda (m) (iter (ack (- n 1)) m)))) (display ((ack 3) 5)) ;; nice curried... 745 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 08:32:21 ] >>７４１ 740ではないが， 原始帰納関数　⊆　部分再帰関数　⊆　一般帰納関数 ということになるってこと？ 部分再帰関数と一般帰納関数の違いって何？ 746 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 09:48:29 ] function = partial function∪total function 747 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 09:58:51 ] >>745 一般再帰(帰納的)関数の定義は？Kleeneの言うgeneral recursive function の意味で言っているのなら、部分再帰関数の真部分集合。なぜなら部分再帰関数は 全域関数でもありうるから。 つまり、 原始再帰関数　c　一般再帰関数 c　部分再帰関数 ということ。ちなみに、原始再帰関数も真部分集合だぞ。Ackermann関数がその一例。 つーかおまい情報系出身か？この辺は一般常識だぞ。 門外漢なら計算理論の教科書を読むべき。 748 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 10:11:31 ] >>746 partial function ⊃ total function 749 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 13:01:30 ] オレ、門外漢なんで高橋先生の「計算論」を読んでみた。 関数と部分関数ってのがあるんだね。そこを強調するのに 部分帰納的関数という言い方をするんだそうだ。 一般帰納的関数はゲーデルの本にあった言い方で クリーニの1936年の論文らしい。邦訳があったら読んでみたい。 750 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 15:57:45 ] →ゲーデルのセミナーでの言い方 ゲーデルは共同研究やセミナーで使っただけで、 帰納的関数について長らく公表しなかった。 ゲーデルにとっては公表するほどの成果ではなかったらしい。 751 名前：デフォルトの名無しさん mailto:sage [2009/07/08(水) 16:26:45 ] ゲーデルは算定可能という概念も提案した。 結局、これら６つの同等性が証明されてチャーチの提唱へ。 752 名前：baka mailto:sage [2009/07/08(水) 17:40:48 ] すいません、LittleSchemerが難しいと感じるのってやばいですか？ いま2章のand again, and again...のとこなんですが意味わかめです。

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef