集合論に基づいた言語を作りたい

1 名前：デフォルトの名無しさん [2014/08/10(日) 21:27:16.56 ID:x7G32Sd0] 計算機科学の基礎は集合論であるという。 ならば、集合論に基づいた言語を作れば美しい言語になるのでは？ そんな発想から徹底的に集合論的思想で言語仕様を考えるスレです。 75 名前：1 mailto:sage [2014/08/13(水) 18:42:03.57 ID:O4gvlVlr] こんどこそID違うと思うけど１です。 どういうのが美しいかというと、教科書の記述をコピペすると それがそのまま実装になるような言語がいいな。 用途は主に教育用。実用性はあんまり追わない。 76 名前：デフォルトの名無しさん mailto:sage [2014/08/13(水) 19:07:44.67 ID:1bb/GYoz] 意味不明 77 名前：デフォルトの名無しさん mailto:sage [2014/08/13(水) 19:14:36.99 ID:OawzouLt] 美味しいものが食べたい 78 名前：1 mailto:sage [2014/08/13(水) 20:07:16.34 ID:O4gvlVlr] 明日から２日くらいレスできなくなるけど、失踪したわけじゃないからな。 よろしく。 79 名前：デフォルトの名無しさん [2014/08/14(木) 00:15:37.33 ID:qppS6X9h] ファジィ論理 - Wikipedia ファジィ論理（ファジィろんり、英: Fuzzy logic）は、ファジィ集合から派生した多値論理の一種で、真理値が0から1までの範囲の値をとり、 古典論理のように「真」と「偽」という2つの値に限定されないことが特徴である。 ファジィ論理と確率論理は数学的に似ており、どちらも0から1までの値を真理値とするが、概念的には解釈の面で異なる。 ファジィ論理の真理値が「真の度合い」に対応しているのに対し、確率論理では「確からしさ」や「尤もらしさ」に対応している。 ■[QC]量子コンピュータの基礎：振幅の初期化 本記事は、量子コンピュータの初期状態の作り方についてです。1998年に発表された手法です。 状態 2量子ビットの場合、0,1,2,3と4つの状態が作られます。 d.hatena.ne.jp/cgi-bin/mimetex.cgi?\sqrt{\frac{1}{2}}|1>~+~\sqrt{\frac{1}{2}}|3> を観測すると、振幅d.hatena.ne.jp/cgi-bin/mimetex.cgi?\sqrt{\frac{1}{2}} の2乗が出現確率なので、この状態を「観測」すると、50%の確率で|1>、50%の確率で|3>が得られます。 問題は、この状態をどうやって人為的に作り出すかというお話しです。 このレベルですら、論文になるほどの内容…。 d.hatena.ne.jp/yukoba/20090928/p1 量子プログラミング言語 蓮尾 一郎（東京大学大学院情報理工学系研究科） 星野 直彦（京都大学数理解析研究所） 量子プログラミング言語とは――研究の動機 量子計算の分野においてアルゴリズムを記述するためには，量子回路が用いるのが一般的だろう． 一方で，（量子でない）古典アルゴリズムを回路で表現することはあまりなく擬似コードとよばれるプログラムもどきが用いられる． この一点においてすでに「量子計算のためのプログラミング言語とはどのようなものか？」という疑問が自然に浮かびあがるのであり， 筆者らはこの疑問に答えるべく（おもに数学的なアプローチから）研究を行っている． しかし以下ではさらにもう少し，「量子プログラミング言語の実現によって何が可能となるのか？」ということについて論じたい． www-mmm.is.s.u-tokyo.ac.jp/~ichiro/papers/quantProgLangJapaneseMar2014.pdf 80 名前：デフォルトの名無しさん mailto:sage [2014/08/14(木) 07:53:05.12 ID:18xo22zy] en.wikipedia.org/wiki/Z_notation wwwold.stups.uni-duesseldorf.de/publications/proz.pdf 81 名前：デフォルトの名無しさん mailto:sage [2014/08/14(木) 22:20:55.55 ID:ao1eYSCw] 「全貌はともあれこういうことをこうカッコよく書けそう」みたいなのをみたい 82 名前：デフォルトの名無しさん mailto:sage [2014/08/15(金) 12:53:42.95 ID:Aqg845W8] www.buzzword.jp/img/face10.png 83 名前：1 mailto:sage [2014/08/16(土) 08:32:34.29 ID:ceF43G6L] >>81 とりあえず、正規表現と有限オートマトン、文脈自由言語とプッシュダウンオートマトン あたりを美しく、または教科書のとおりに書きたいなと思ってる。 具体的な案はまだない。 84 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 09:06:38.11 ID:/1p3o6vn] 意味不明。雰囲気だけで語るな。 85 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 09:20:19.06 ID:atIrV/RU] Peggyでいいじゃん。 86 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 09:21:32.20 ID:InfE8TR8] だからせめて記述例を書けよ お前の脳内は読めねえ 87 名前：１ mailto:sage [2014/08/16(土) 09:37:02.60 ID:ceF43G6L] だから具体的な案はまだないんだって。 88 名前：１ mailto:sage [2014/08/16(土) 10:17:23.81 ID:ceF43G6L] 有限オートマトンの遷移関数を書くのに、関数の引数のパターンマッチは欲しいかな。 89 名前：１ mailto:sage [2014/08/16(土) 10:35:06.72 ID:ceF43G6L] と、おもったけどそんなめんどくさいことしなくても連想配列でもいいのか。 90 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 10:41:17.00 ID:eWpr12Q+] >>87 ここはお前の日記帳じゃないんだから、具体的にまとまってから書いてくれ 91 名前：1 mailto:sage [2014/08/16(土) 11:51:35.82 ID:ceF43G6L] 俺が持ってる教科書、マイケルシプサの計算理論の基礎っていう本の38,39ページに載ってる A={w|wは少なくとも一つの1を含み最後に現れる1の後に偶数個の0が存在する} っていう言語を受理するオートマトンの実装例は以下のような感じかな。かなりC++ぽいが。 enum State {q1,q2,q3}; set<State> Q={q1,q2,q3}; set<char> Σ={'0','1'}; map<pair<State,char>,State> δ={ &nbsp;&nbsp;(q1,'0')=>q1, &nbsp;&nbsp;(q1,'1')=>q2, &nbsp;&nbsp;(q2,'0')=>q3, &nbsp;&nbsp;(q2,'1')=>q2, &nbsp;&nbsp;(q3,'0')=>q2, &nbsp;&nbsp;(q3,'1')=>q2 }; set<State> F={q2}; class Automaton { &nbsp;&nbsp;set<State> Q; &nbsp;&nbsp;set<char> Σ; &nbsp;&nbsp;map<pair<State,char>,State> δ; &nbsp;&nbsp;State start; &nbsp;&nbsp;set<State> F; &nbsp;&nbsp;bool accept(char *str){ &nbsp;&nbsp;&nbsp;&nbsp;State state=start; &nbsp;&nbsp;&nbsp;&nbsp;while(str){ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;state=δ[(state,*str)]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;str++; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;return F.include(state); &nbsp;&nbsp;} } M = (Q,Σ,δ,q1,F); 92 名前：1 mailto:sage [2014/08/16(土) 11:54:15.04 ID:ceF43G6L] あれ、空白ミスってんな。 プレビューでみたらちゃんと空白になってたと思ったけど。 93 名前：1 mailto:sage [2014/08/16(土) 11:57:01.89 ID:ceF43G6L] まあ、いいや。インデントなしで再投稿 enum State {q1,q2,q3}; set<State> Q={q1,q2,q3}; set<char> Σ={'0','1'}; map<pair<State,char>,State> δ={ (q1,'0')=>q1, (q1,'1')=>q2, (q2,'0')=>q3, (q2,'1')=>q2, (q3,'0')=>q2, (q3,'1')=>q2 }; set<State> F={q2}; class Automaton { set<State> Q; set<char> Σ; map<pair<State,char>,State> δ; State start; set<State> F; bool accept(char *str){ State state=start; while(str){ state=δ[(state,*str)]; str++; } return F.include(state); } } M = (Q,Σ,δ,q1,F); 94 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 13:25:37.77 ID:atIrV/RU] Ragelでいいじゃん。 95 名前：1 mailto:sage [2014/08/16(土) 15:25:06.91 ID:ceF43G6L] とりあえず、集合と連想配列と組のリテラル表記は欲しいな。 型さえ一致してれば組はクラスに暗黙のキャストできる感じで。 96 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 17:30:42.83 ID:wloQcISK] 目新しいものがないな。なんとなく美しくなりそうってのは天才的センスがないと実現しない。 天才か凡才かを確定させるためにさっさと作ってしまおう。 97 名前：１ mailto:sage [2014/08/16(土) 17:44:24.71 ID:ceF43G6L] まじかｗ 言語仕様きめるだけでも結構大変だぞｗ さくっと作れるみたいなこと言うなｗ 98 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 17:45:22.16 ID:0H8IvnJl] 結局、見た目の問題でしかないの？ 新しいパラダイムもなにも無いなら、わざわざ言語を作る意味が無いよ 99 名前：１ mailto:sage [2014/08/16(土) 17:56:17.24 ID:ceF43G6L] いまのところシンタックスシュガーの問題の域をでてないな。 オートマトンだけじゃなくてもっと色んな問題を考察していけば なんか出てくるのかもしれないが。 とにかく、今のプログラミング言語において集合は不当に冷遇されてる気がする。 もっと集合を活躍させるべき、というのがこのスレの発端です。 100 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 17:59:58.20 ID:0E9vEosE] >>75を具体的に語って欲しい 101 名前：１ mailto:sage [2014/08/16(土) 18:04:10.41 ID:ceF43G6L] 型のキャストって結構不自由じゃない？ 集合論に基づいた型の表記法が一致したらバンバンキャストできるようにしちゃうとか。 102 名前：デフォルトの名無しさん mailto:sage [2014/08/16(土) 18:09:17.80 ID:ceF43G6L] >>100 いや、>>75を具体的に語ったのが>>93なんだけども。 残念ながら教科書コピペとはほど遠いC++チックなコードになっちゃったけど 教科書の定義にはなるべく従ったコードにしたつもり。 103 名前：デフォルトの名無しさん mailto:sage [2014/08/17(日) 00:08:28.60 ID:rJnEUKU4] OCamlのvariantみたいなことがしたいのかなあ？ 104 名前：１ mailto:sage [2014/08/17(日) 00:17:38.28 ID:wbAX39n3] OCamlは触ったことがないけど面白そうな雰囲気ですね。 本でもかってくるかな。 105 名前：デフォルトの名無しさん mailto:sage [2014/08/17(日) 00:38:59.38 ID:rJnEUKU4] >>1はCライクな言語しか触ったこと無いの？ だったら、もっと色々な言語を知るべきだよ。 その上でLispなり何なりで好きなようにDSLを実装すればいい。 少なくとも、集合が不当に冷遇されてるなんてことはない。ありえない。 106 名前：デフォルトの名無しさん [2014/08/17(日) 05:17:10.40 ID:ruDVRpF3] 集合論よりかは圏論のほうが良くないか。厳密には違うが、ほぼ集合論の一般化でプログラム言語として利用する上では不具合無いだろ。 Haskell/圏論 - Wikibooks ja.wikibooks.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Simple-cat.png ja.wikibooks.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Functor.png ja.wikibooks.org/wiki/Haskell/%E5%9C%8F%E8%AB%96 Scala で圏論入門 https://github.com/scalajp/introduction-to-category-theory-in-scala-jp/wiki Coq を始めよう このチュートリアルでは定理証明支援系言語である Coq について解説をします。 読者の前提知識としては OCaml や Haskell などの関数型言語でプログラミングできることを想定します。 また、本文書において Coq のプログラムとの比較には Haskell と OCaml を用いますが、Haskell や OCaml を書いたことがなくても他の関数型言語に触れていれば理解できるような内容を心がけます。 www.iij-ii.co.jp/lab/techdoc/coqt/coqt1.html 圏論は数学をするための「高級言語」　 www.is.s.u-tokyo.ac.jp/isnavi/images/logic/picture04.gif www.is.s.u-tokyo.ac.jp/isnavi/logic06.html 107 名前：デフォルトの名無しさん [2014/08/17(日) 07:09:05.41 ID:YbL+7IWD] メニー・コアの時代にはそういう言語が流行るんだろな。 108 名前：デフォルトの名無しさん [2014/08/17(日) 07:29:25.82 ID:ruDVRpF3] 圏論 - Wikipedia 圏論（けんろん、category theory）は、数学的構造とその間の関係を抽象的に扱う数学理論の 1 つである。 さらに一般的な圏論、つまり、意味論的な柔軟性をもち高階論理との親和性があるようなより現代的な普遍的代数が発展し、現在では数学全体を通して応用されている。 トポスと呼ばれる特別な種類の圏は、数学基礎論としての公理的集合論に取って代わることすら可能である。 実際構成的数学を記述する手段としても、トポスは非常に精緻に機能することが示されている。 集合論 - Wikipedia さまざまな数学の問題に対応した構造を理解するときには、個々の対象が具体的にどんな集合として定義されたかということよりも、 類似の構造を持つほかの数学的対象との関係性の方がしばしば重要になる。 この関係性は対象間の写像のうちで「構造を保つ」ようなものによって定式化される。このような考え方を扱うために圏論が発達した。 集合論の著しい特徴は集合間の写像たちまでが再び集合として実現できることだが、こういった性質を圏論的に定式化することで 集合論の圏論化・幾何化ともいうべきトポスの概念がえられる。 109 名前：１ mailto:sage [2014/08/17(日) 09:26:36.14 ID:wbAX39n3] >>105 私の使用言語は主にC/C++ですね。 あとはRubyを少々。JavaやC#はかじった程度。 関数型言語は触ったことないですね。 >少なくとも、集合が不当に冷遇されてるなんてことはない。ありえない。 うーん。そうなんですか。でもそれだとこのスレが終わってしまうｗ >>106 圏論は知らないですね。なんか難しそうってイメージです。 はたして独学で勉強できるかどうか。。。 110 名前：デフォルトの名無しさん [2014/08/17(日) 09:41:10.85 ID:ruDVRpF3] 集合が{○、●、◎、□、■}とすると、 圏は{→(1)、→(2)、→(3)、→(4)、→(5)}> 111 名前：デフォルトの名無しさん [2014/08/17(日) 09:51:19.75 ID:ruDVRpF3] 途中で送信した。 (ある条件をみたす)全ての集合に対して、(ある条件をみたす)全ての集合の写像の集まりが圏。 圏論は、集合間の写像に注目したもの。 厳密なことは知らないが、どんな集合も圏として扱えるはずだろう。 集合{○、●、◎、□、■}に対して、圏{○→○、●→●、◎→◎、□→□、■→■}、(f(x)=xとなる写像)が作れる。 112 名前：デフォルトの名無しさん mailto:sage [2014/08/17(日) 09:52:50.76 ID:wbAX39n3] >>110 →の意味がわからないｗ あと最後の>は必要なの？ 113 名前：１ mailto:sage [2014/08/17(日) 09:53:56.42 ID:wbAX39n3] うおリロードしてなかった。 114 名前：デフォルトの名無しさん [2014/08/17(日) 10:02:50.89 ID:ruDVRpF3] 圏の主人公って「対象」なのかな？「射」なのかな？ | TETRA'S MATH 「しりとりの圏」を圏とみなそうとするとき、まず、1字1字があって、 artet-math.img.jugem.jp/20101201_1468744.jpg 　それを始域、終域とする文字列を考えるのか。 artet-math.img.jugem.jp/20101201_1468743.jpg それとも、まず文字列ありきで、 artet-math.img.jugem.jp/20101201_1468745.jpg 始域、終域の一致でそれらの関係をひとまとまりのものとして捉えるのか… artet-math.img.jugem.jp/20101201_1468746.jpg どっちのイメージが圏の本質に近いのだろう？ で、検索していたら、檜山さんの有限集合と写像の圏もJavaScriptで書いてみた、遊んでみてねにて、「圏の主役は射です。」と書いてあるのを発見。なるほど。 math.artet.net/?eid=1306322 115 名前：１ mailto:sage [2014/08/17(日) 10:17:17.51 ID:wbAX39n3] TODOが一気にふえたな。 とりあえず、Ocamlの本買ってきます。 圏論を理解できるようになるのは相当先かな〜。 116 名前：デフォルトの名無しさん mailto:sage [2014/08/17(日) 10:34:34.27 ID:kLc8LA2s] >>1はやりたいことが沢山あって圧倒される段階か。その後何年かして夢見た事はすべてやり尽くした段階になる。 能力が足りないとそうなるまえに死んでしまうがね。 117 名前：デフォルトの名無しさん [2014/08/17(日) 10:36:45.62 ID:ruDVRpF3] Ocamlは副作用があって純粋な関数型でない。副作用ありでいいならJavascriptも関数型言語でJavascriptで関数型の勉強可能。 純粋関数型プログラミングとは 関数が純粋であるというのは、副作用がないということである。副作用とは、関数が、内部で、なんらかの状態を隠しもつことをいう。 OCamlのようなML由来の言語は"ほぼ純粋"である。副作用を、参照や配列の形で使えるけども、大抵は、書いたコードは純粋関数型に落ち着くことが多い。 Haskellもまた、関数型言語で、純粋関数型だ。OCamlは、より実用的といえる。純粋でない関数もときには便利だからだ。 ocaml.org/learn/tutorials/functional_programming.ja.html JavaScriptで学ぶ関数型プログラミング hamasyou.com/blog/2014/02/21/functional-javascript/ JavaScript はプロトタイプベースのオブジェクト指向言語ですが、関数型言語の機能も備えています。 www.geocities.jp/m_hiroi/light/js03.html JavaScript - Javascrptで関数型プログラミングの入門 - Qiita qiita.com/takeharu/items/cf98d352ff574c5ac536 JavaScriptは関数型言語の特徴を取り入れていると思いますが、純粋な関数型言語ではありません。しかし今、そしてこれからのトレンドは関数型言語と言われています。 そこでJavaScriptでより関数型言語的なプログラミングを可能にするfn.jsを使ってみましょう。 www.moongift.jp/2014/02/fn-js-javascript%E3%82%92%E9%96%A2%E6%95%B0%E5%9E%8B%E8%A8%80%E8%AA%9E%E3%81%AE%E3%82%B9%E3%82%BF%E3%82%A4%E3%83%AB%E3%81%A7%E6%9B%B8%E3%81%8F%EF%BC%81/ CoffeeScript と Node.js による関数型の JavaScript www.ibm.com/developerworks/jp/java/library/j-coffeescript/ Functional JavaScript https://gist.github.com/ympbyc/5564146 118 名前：デフォルトの名無しさん [2014/08/17(日) 10:45:48.55 ID:ruDVRpF3] この記事では、クイックソート・アルゴリズムの実装について、 様々な言語で書かれた関数型プログラミングのコードを紹介しています なお、この記事の内容は、 2ちゃんねる掲示板 のプログラム板にあるスレッド 【PHP,Python】スクリプト, バトルロワイヤル36【Perl,Ruby】 で行われた議論を整理、加筆したものです。 関数型言語が関数型プログラミングを何の苦もなく実践できるのは、当たり前の話です。 Haskell quicksort [] = [] quicksort (pivot:xs) = quicksort littles ++ pivot:(quicksort bigs) where f x (ls, bs) = if x < pivot then (x:ls, bs) else (ls, x:bs) (littles, bigs) = foldr f ([], []) xs この節で取り上げる Ruby, JavaScript, Python はどれも関数型言語には分類されていませんが、関数型の特性を取り入れていると言われています。 それでは、これら言語の関数型プログラミング・スタイルを見ていくことにしましょう。 JavaScript function quicksort(xs) { function f(xs) { var pivot = xs[0]; function g(pair, x) { var ls = pair[0], bs = pair[1] return x < pivot ? [ls.concat([x]), bs] : [ls, bs.concat([x])]; } var pair = xs.slice(1).reduce(g, [[], []]); var littles = pair[0], bigs = pair[1]; return [].concat( quicksort(littles), [pivot], quicksort(bigs) ); } return xs.length <= 1 ? xs : f(xs); } www.h6.dion.ne.jp/~machan/misc/qsort-in-fp.html 119 名前：デフォルトの名無しさん [2014/08/17(日) 10:51:34.94 ID:ruDVRpF3] こっちのクイックソートのほうが短くわかりやすかった。 クイックソート - NullPointer's Blog Erlangで書くと… quicksort([]) -> []; quicksort([Head|Tail]) -> quicksort([X || X <- Tail, X < Head ]) ++ [Head] ++ quicksort([X || X <- Tail, X >= Head]). 小さいのを左に集めて、大きいのを右に集めて、繰り返し…、アルゴリズムの説明そのままのコードになる。 簡単すぎ。アルゴリズムを理解するという目的であれば、関数型のコードの方が10000倍理解しやすい。 関数型っぽい書き方は、最近のJavaScriptならばサクッと書けますが… function quickSort(array) { if (array.length <= 1) return array; var pivot = array.pop(); var lt = array.filter(function(a){ return a < pivot }); var ge = array.filter(function(a){ return a >= pivot }); return quickSort(lt).concat([pivot]).concat(quickSort(ge)) } paulownia.hatenablog.com/entry/20111204/1323015703 120 名前：１ mailto:sage [2014/08/17(日) 15:08:45.66 ID:wbAX39n3] 本屋めぐってきたけどOcamlの本なかったわー 廃れてしまった言語なん？ しかたないからwebで情報探すか。 121 名前：デフォルトの名無しさん mailto:sage [2014/08/17(日) 15:31:49.05 ID:8WbwPRMF] ググれば数秒でみつかるのに。 caml.inria.fr/resources/index.en.html 122 名前：デフォルトの名無しさん mailto:sage [2014/08/17(日) 16:03:30.63 ID:PGXi6tC2] >>109 > うーん。そうなんですか。でもそれだとこのスレが終わってしまうｗ いいことじゃん。 続きはブログでやってくれ。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

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