- 1 名前：デフォルトの名無しさん mailto:sage [2009/07/27(月) 10:15:31 ]
- ※ ここはCommon Lisp、SchemeをはじめとするLisp族全般のスレです ※
■過去スレ
Part26: ttp://pc12.2ch.net/test/read.cgi/tech/1240567959/
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)
- 45 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 16:45:19 ]
- >>41
すいません、良く試してみると返り値は正しいんですが
元のリストの変更は n=0 の時失敗してしまうようです…。
(let ((ls '(1 2 3)))
(foo ls 0)
ls)
- 46 名前：27 mailto:sage [2009/07/29(水) 17:01:31 ]
- >>32
自分が書いたのはこんなの。
Lisp/Schemeはほとんど使ったことないんで書き方がおかしいかもしれないが。
(define (add-elt elt set)
(cond
((null? set) (list elt))
((member elt set) set)
(else (cons elt set))))
(define (map-add-elt elt set)
(cond
((null? set) '())
(else (map (lambda (m) (add-elt elt m)) set))))
(define (power-set set)
(cond
((null? set) '(()))
(else (let
((ps (power-set (cdr set))))
(append ps (map-add-elt (car set) ps))))))
- 47 名前：32 mailto:sage [2009/07/29(水) 17:55:23 ]
- >>46
ああ〜〜〜〜〜、そうかぁ。
集合の要素を１つ抜いた部分集合を全部の要素について考えたのですが、
ああ、そうですね。全部考える必要などなかったです。
- 48 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 18:38:55 ]
- 冪集合は格要素を「とる」か「とらない」で再帰すれば良いと考えて
こう書いてみました
(define (power l)
(if (not (pair? l)) (list l)
(append
(power (cdr l)) ;先頭をとらない
(map (pa$ cons (car l)) (power (cdr l))) ;先頭をとる
)))
- 49 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 18:42:50 ]
- こないだカタランの問題、続きがあるので
良かったら考えてみてください
元々は小町算を解くために考えた問題です
結局、カタランが出来たのにこれはまだ解けずにいます
問題
2引数を取る演算子のリストと、演算数のリスト(演算子より1個多い)を引数にとって
全ての生成可能な式のリストを生成するkomachiを定義せよ
(komachi '(+ - *) '(1 2 3 4))
を実行すると
(
(+ (- (* 1 2) 3) 4)
(+ (- 1 (* 2 3)) 4)
(+ (- 1 2) (* 3 4))
... ;こんな感じで全パターンが出るまで続く。上の並びは適当
)
この条件をつけるかはお任せ
条件：「演算子、あるいは演算数のみに注目した場合、順序の入れ替えはないものとする」
例えば '(+ -) '(1 2 3)において
(+ 1 (- 2 3))を(+ 1 (- 3 2)) ;演算数の順序を入れ替えたのでNG
(+ 1 (- 2 3))を(- 1 (+ 2 3)) ;演算子の順序を入れ替えたのでNG
こうすると、komachiが生成する式の総数は
(演算子は空気と思えばよいので)演算数のカタラン数に一致します。多分。
- 50 名前：32 mailto:sage [2009/07/29(水) 18:53:31 ]
- >>48
なるほどよくわかりました。２^nを計算
するアルゴリズムと基本的には同じですね。
要素をとる、とらない、の2通りがあるから。
冪集合の名前の通りだ。
- 51 名前：27 mailto:sage [2009/07/29(水) 19:25:07 ]
- >>48
pa$というのは何ですか？mzschemeだとエラーになってしまいます。
- 52 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 19:35:51 ]
- >>51
(define (pa$ fn . args) (lambda more-args (apply fn (append args more-args))))
- 53 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 20:28:19 ]
- >>51
部分適用といって、手続きの引数の一部を固定した新たな引数を返す手続き。
例えば、
((pa$ + 3) 2) ⇒ 5
みたいな。SRFI-26のcutと似たようなもの。cutなら、
((cut + 3 <>) 2) ⇒ 5
こんな感じ。
- 54 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 20:33:40 ]
- 新たな引数→新たな手続きの間違い。失礼。
- 55 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 21:11:30 ]
- 教えてもらってやっと納得のいくコードが書けたよ。
最初に書いたのは無駄だらけだった（笑）。
(define (power-set ls)
(if (null? ls)
'(())
(let ((subset (power-set (cdr ls))))
(append subset
(map (lambda (x) (cons (car ls) x)) subset)))))
- 56 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 22:22:39 ]
- >>45
おっと失礼。マクロじゃなきゃダメですね。
(defmacro foo (ls n) `(if (= ,n 0) (pop ,ls) (pop (cdr (nthcdr (- ,n 1) ,ls))) ))
- 57 名前：デフォルトの名無しさん mailto:sage [2009/07/29(水) 23:07:40 ]
- >>51
mzscheme なら curry
ちなみに >>52 の pa$ は片方が空リストになる時にエラーになった
- 58 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 00:37:16 ]
- >>52>>53>>57
curryingのことだったのか。名前の由来には何か歴史的な事情でもある？
- 59 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 02:25:44 ]
- ((pa$ + 3) 2) ⇒ 5
こんなのは無駄に問題を難しくしてるだけ
(+ 3 2)
これでいいじゃないか
(pa$ + 3) は何を返す？
手続きを作ったところでそれを保存したり表示したりできるわけでもないし
無駄なことをするな
- 60 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 03:20:20 ]
- >>58
歴史的経緯は知らないけれど、部分適用をあらわすのに$を使うのはgaucheの命名規約。
practical-scheme.net/wiliki/wiliki.cgi?Scheme%3a!%E3%81%A8%3f#H-yofpb1
個人的には、curry って名前なら(lambda (x y z) ...) を
(lambda (x) (lambda (y) (lambda (z) ...)))ってしてくれるんじゃないと違和感があるなあ。
可変長引数で困るけど。
>>59
そりゃ実用上はpa$をそんな使い方する人いないでしょ。
- 61 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 07:46:09 ]
- >>59
作った手続きを束縛して再利用するに決まってんじゃん。
もしかして、複数の引数を持つ手続きを呼ぶ際には、
毎回必ず全ての引数の値が異なるようになる呪いを掛けられてる人ですか？
というか、クロージャがファーストクラスな言語でそういう事を言うのが信じられない。
- 62 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 08:07:48 ]
- >>58
partial apply で $ をつけるのは Haskell の $ 演算子由来だそうな
ttp://practical-scheme.net/wiliki/wiliki.cgi?Scheme%3a%e5%88%9d%e5%bf%83%e8%80%85%e3%81%ae%e8%b3%aa%e5%95%8f%e7%ae%b1%3alog00#H-1bifybk
- 63 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 09:17:14 ]
- カリー化を使うとうまく解ける問題があったら教えてください。
- 64 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 09:37:19 ]
- 構文糖衣みたいなもんなので特にない
- 65 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 10:08:48 ]
- (pa$ + 3) とか (cut + 3 <>) とかではなくマクロにして
(bind (+ 100 $1)) とか (bind (+ 200 . $rest)) とか書けないかな。
直観的になって嬉しいと思うんだけど。
- 66 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 12:44:20 ]
- >>65
前以って arity がわかってるんなら syntax-case で
codepad.org/29239gmR
みたいな感じとか。
(bind 1 (+ 100 $1))
みたいに使う。後者の例はどうするのがいいんだろ。
- 67 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 12:57:17 ]
- arityを書かなきゃいけないのはダサいな。式の中の$nを調べて自動で出してほしいところ。
- 68 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 13:00:09 ]
- 一方ロシアは
(^(x) (+ 100 x))
- 69 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 13:00:55 ]
- (define-macro (bind . body) `(lambda ($1) ,@body))
後者は構文として正しくない
- 70 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 13:06:38 ]
- > (bind (+ 200 . $rest))
@restとすると展開
$restとすると単値(リスト)
がいいかも
((bind (+ 200 @rest)) 300 400) ; ==> 900
((bind (cons 200 $rest)) 300 400) ; ==> (200 300 400)
- 71 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 14:04:09 ]
- >>67
LOL の 5.2 節を参考にしてみたんだけどダサいかな。
マクロ引数を flatten してごにょごにょすればそういうのもできるよ
- 72 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 15:20:22 ]
- >>65
srfi-26 の議論の中で引数の番号つきの部分適用の話が出たことはあるそうだ。
srfi.schemers.org/srfi-26/mail-archive/msg00018.html
>>66-67
最も大きい番号を arity とみなす実装。
d.hatena.ne.jp/SaitoAtsushi/20080811/1218380989
確かにどこから rest 引数にすりゃいいのか決められないな。
- 73 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 15:33:03 ]
- > 確かにどこから rest 引数にすりゃいいのか決められないな。
単純に最も大きい番号の数より多い引数が rest になるんじゃまずいのかな。
式の中で $1, $2, $3, $rest が使われていたら
(lambda ($1 $2 $3 . $rest) ...) になるみたいな。
- 74 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 15:55:35 ]
- >>56
ありがとうございます。
こういう時にマクロを使うんですね。勉強になります。
- 75 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 16:04:53 ]
- (define-macro (bind1 . body) `(lambda ($1 . $rest) ,@body))
(define-macro (bind2 . body) `(lambda ($2 . $rest) (lambda ($1) ,@body)))
- 76 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 18:59:24 ]
- 誰か弟子にしてください！！
- 77 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 19:06:06 ]
- おう! いいぞ。 今日から俺のことを師匠と呼べ。
- 78 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 20:12:50 ]
- 再帰使って自分を弟子にしろ
- 79 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 20:14:17 ]
- どこかに終了条件がないと無限ループになるぞ
- 80 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 20:28:49 ]
- streamにして、毎回弟子を取り出せばおｋ
- 81 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 20:32:38 ]
- ((null 弟子) nil)
- 82 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 22:19:40 ]
- _これって何？
どんな時に使うの？
- 83 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 22:42:53 ]
- >>82
プレースホルダー。
使わない引数とかを表現するのに使う作法。
(define (const a) (lambda _ a)) とか。
- 84 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 22:42:59 ]
- 引数が必要ない時に使う
透明あぼーんと同じ
- 85 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 22:53:15 ]
- 仕様にあるんだっけ？
いつもdummy、みたいな変数名を付けてた
- 86 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 22:55:17 ]
- 仕様にはない。
あくまで作法。
- 87 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 22:59:04 ]
- prologではそれで最適化とかなかったっけ
まあフロー解析すりゃいいけど
- 88 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 23:00:47 ]
- ああ、CLやschemeは_も変数として定義出来るのを忘れてたよ
- 89 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 23:04:28 ]
- 82です．分かりました．
みなさんありがとうございます．
- 90 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 23:14:28 ]
- Erlang だと _X みたいな変数は自動で CL で言うところの ignore 扱いになるね
- 91 名前：デフォルトの名無しさん mailto:sage [2009/07/30(木) 23:23:04 ]
- haskell でも言語仕様でプレースホルダーとしての意味を規定してたはず。
- 92 名前：デフォルトの名無しさん mailto:sage [2009/07/31(金) 17:54:45 ]
- >>82
R6RS のマクロパターンではワイルドカード
それ以外の場所ではただのシンボル
- 93 名前：デフォルトの名無しさん mailto:sage [2009/07/31(金) 20:57:59 ]
- 自分はand-let*の中でよく使いますね < '_
- 94 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 05:00:54 ]
- >>93
and-let*で _ 使いたくなる時ってある?
単に条件判断のみやりたい時は変数書かなくてもいいわけだし。
- 95 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 10:21:04 ]
- SICP昔読んだ程度の初心者なのですが、最近翻訳された「Let Over Lambda」は
Lisperの皆様から見てどんな感想でしょうか。
どうもマクロというと難しいという印象強いので、翻訳以前から本は知ってましたけど
読むのは気が引けてました。
また、翻訳レベルはどうでしょうか？Amazonの立ち読み見た限りではかなり良い
翻訳に感じました。
- 96 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 12:34:57 ]
- >>94
単に趣味の問題です:-)
変数だけ書いたり式だけ書いたりするのはバランスが悪く感じるので
'_を使っているんです
Cなんかで変数宣言＆初期化する時に=を揃えるような感覚です
int hoge = 10;
int foo = 30;
- 97 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 12:36:09 ]
- 揃わなかった:-(
- 98 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 12:45:30 ]
- Cの代入で桁をきれいに揃えようとして0で埋めたら8進になっちゃった
という話を思い出した。
x = 123;
y = 054;
- 99 名前：デフォルトの名無しさん [2009/08/01(土) 22:40:23 ]
- すみません、どこで質問していいのか分からなかったので教えてください
LispマシンっていうのはPC98がBASICだったみたいに
LISPを基本的に動作するパソコンんの事でしょうか？
- 100 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 22:44:52 ]
- まずはPC98が何だったか調べる作業から始めろ
- 101 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 22:47:04 ]
- てにをはがおかしい
- 102 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 22:49:03 ]
- いや、てにをはを直したとしても、繕い切れない何かがある
- 103 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 22:53:07 ]
- >>99
終盤の一部のPC98を除いてROMに最初からBASICインタプリタが塔載されていたことを思うと、
確かにBASICを基本としていたのかもしれないとは思うが、
ハードウェアの構造がBASICに特に有利ということはない。
実際、他の言語の方が効率的に使えた。
一般にLispマシンってのはLispを主要な言語とするだけでなくて、
CPU のインストラクションのレベルから設計時に Lisp を前提とし、
Lisp のために最適化されているようなマシンだと思う。
- 104 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 23:05:31 ]
- ELIS/TAOってどこかで動いているんかな？
- 105 名前：デフォルトの名無しさん mailto:sage [2009/08/01(土) 23:42:14 ]
- シュレディンガーの猫みたいな問いだな
- 106 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 01:20:22 ]
- 俺の横で寝てるよ
- 107 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 07:12:03 ]
- 猫が？竹内先生が？
- 108 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 10:03:15 ]
- 俺が
- 109 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 10:05:11 ]
- せつこ! それシュレディンガーやない、ドッペルゲンガーや!
- 110 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 11:48:22 ]
- リストのドッペルゲンガーの作り方って↓でいいのかい？
(define (copy ls)
(if (atom? ls)
ls
(cons (copy (car ls))
(copy (cdr ls)))))
(define (atom? x)
(not (pair? x)))
- 111 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 12:03:10 ]
- ベクタを忘れてる
- 112 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 13:05:54 ]
- (define (copy . ls) ls)
で良い。
- 113 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 14:02:53 ]
- >>99
ウィキペディアに項目あり
- 114 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 19:41:25 ]
- >>>111
あ、いや、リストですから。
>>112
なるほど、そうなんですね。
因みにコードは復刊する竹内先生の本にあったものを拝借。
- 115 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 21:24:33 ]
- ディープコピーｗするなら110しないとだめだよ
- 116 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 23:17:07 ]
- copyされたものかどうかを見抜くことってできないですか？
お前はドッペルゲンガーだろ？って (double? ls) => #t #f
- 117 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 23:31:39 ]
- eq?で十分だけど？
- 118 名前：デフォルトの名無しさん mailto:sage [2009/08/02(日) 23:31:57 ]
- 見抜くことが出来たらコピーではないとおもう
- 119 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 02:41:23 ]
- >>116-117
比較じゃなくて、「同じものが存在するか」を調べたいってこと？
Scheme 的には出来ない。
コピーしたときにオブジェクトに何らかのマークをつけるような
データ構造を作ってなんとかするというのが妥当かな。
あんまり知らんけど Ruby には汚染フラグってあったよな？
あんな感じで。
で、なんでそんなことをしたいのやぅぃ？
- 120 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 02:45:39 ]
- set-car!set-cdr!を禁止すればeq?でいいんだけど？
- 121 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 02:47:06 ]
- いやいやルートから比較するならやっぱりeq?で十分だけど？
- 122 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 05:05:49 ]
- www.r6rs.org/final/html/r6rs/r6rs-Z-H-14.html#node_idx_434
より。
(eq? (list ’a) (list ’a)) ⇒ #f
(let ((x ’(a))) (eq? x x)) ⇒ #t
- 123 名前：116 mailto:sage [2009/08/03(月) 08:53:06 ]
- ああ、そっか。eq?でいいのですね。
eq?の動作を誤解してました。
- 124 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 16:23:20 ]
- >>123
名前が長くなるほど、同値性の判断は柔らかくなるよん。
名前が短くなるほ(ry
- 125 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 17:11:16 ]
- フィルター処理で同一か判断する(何もフィルタリングされなかった)
時に使える＞eq?
非破壊という前提ならほとんどの処理に当てはまる
- 126 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 17:47:44 ]
- 組込み関数のequal?ってこんな感じ？
(define (my-equal? ls1 ls2)
(if (not (pair? ls1))
(eq? ls1 ls2)
(and (my-equal? (car ls1) (car ls2))
(my-equal? (cdr ls2) (cdr ls2)))))
ところでconsはeq?と並んで基本関数だと本にあったはず。
でも、SICPでconsも定義されていたような覚えがあるんだけど。
consも作れる？
- 127 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 17:51:36 ]
- 覚えがある、じゃなくて読み返せ
- 128 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 18:16:04 ]
-
(define ((cons a b)p)(p a b))
(define (car p)(p (lambda(a b)a)))
(define (car p)(p (lambda(a b)b)))
- 129 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 18:24:12 ]
- >>128
それそれ。中西先生の本にあった基本5関数の話が崩壊してしまった
気分になるんですよ。
- 130 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 18:24:52 ]
- それじゃ印字もできないし、「作れる」とは言わない
- 131 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 18:56:05 ]
- 印字する関数を作れば良いだけ
- 132 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 18:59:25 ]
- じゃあ作れよ
ちなみに「印字する関数」だけじゃ済まなくなるぞ
- 133 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 20:29:06 ]
- 基本５関数っていっても「関数」は５つあればいいけど
QUOTE LAMBDA IF (COND)といった特別式は別に必要なんじゃないかな
５関数とリスト構造だけでチューリング完全なら教えてほしい
自分はかなり考えたけど無理だった
(もっともLAMBDAがあれば基本５関数もIFもいらなくなるけど。QUOTEはいるかな）
- 134 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 20:39:37 ]
- そりゃラムダ計算がチューリング等価だからなぁ…
- 135 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 20:52:44 ]
- >>133
マッカーシー先生のLispの最初の論文にはcondが使われているし
基本関数とは別物では？
[ → ; → ; → ]
- 136 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 21:37:05 ]
- >>133
www-formal.stanford.edu/jmc/recursive/node3.html
- 137 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 21:48:37 ]
- うん、論文では特別式にあたるものも使われているにもかかわらず
wikiを始め基本5関数"のみ"でチューリング完全と言及されているものも多いんだけど
λ計算を初めて知った時、それだけでチューリング完全になるなんて思いもつかなかった自分には
基本5関数"のみ"ではチューリング完全ではないとは断定できなくて…
チャーチ数とかYコンビネータとか思いつくような人ならアレだけでチューリング完全に仕立て上げられちゃうんじゃないかとも思ったもんで
- 138 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 22:22:44 ]
- 基本5関数のみだったら単に5つの関数でしかないわけで、
そこに合成・再帰の操作を許して得られる関数のクラスがチューリング完全、
という言い方になるんだろうね
- 139 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 22:40:47 ]
- そうなんだろうけど、λ（lambda）かdefun（label）があればそれだけでチューリング完全なわけで
結局、基本5関数はチューリング完全なλ算法系の上で"Lisp"を構築するプリミティブにすぎないって話になっちゃうんじゃないかな
基本5関数とチューリング完全性は無関係ってことに
- 140 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 22:46:35 ]
- だからそのLAMBDAやLABELを基本関数で記述している、というのが上の論文の肝でしょ
- 141 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 22:58:08 ]
- ところで「チューリング完全である」っていう述語はどうやって記述すればいいの？
- 142 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 23:02:44 ]
- ttp://ja.wikipedia.org/wiki/%E7%B4%94LISP
「リスト」が曲者かと
- 143 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 23:06:44 ]
- うーん記述には特別式を使っているように思えるけどなぁ…
- 144 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 23:13:02 ]
- lib.store.yahoo.net/lib/paulgraham/jmc.lisp
- 145 名前：デフォルトの名無しさん mailto:sage [2009/08/03(月) 23:18:37 ]
- condもdefunも使ってるじゃないですか
|
 |
