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

**デフォルトの名無しさん** · 2014/08/10(日) 21:27:16.56

計算機科学の基礎は集合論であるという。
ならば、集合論に基づいた言語を作れば美しい言語になるのでは？
そんな発想から徹底的に集合論的思想で言語仕様を考えるスレです。

１ · 2014/09/16(火) 19:43:03.56

>>268
それじゃ丸コピー？

１ · 2014/09/16(火) 20:03:52.99

setElemの計算量オーダーが書いてないな。
ほかのは書いてあるのもあるのに。

**デフォルトの名無しさん** · 2014/09/16(火) 20:35:47.52

>>269
純粋関数型言語における配列の実装は、
一般的には B-Tree またはその亜種を用いるのが一般的
で、常識的には更新する要素とは無関係な部分ツリー(への参照)を
そのまま(更新後の)新しい配列に引き継ぐから、丸コピーにはならない
（Data.Matrixのソースを確認した訳じゃないんで、あくまで一般論であることに注意）
また、配列を利用するアプリケーション側でも、必要な複数の更新操作を関数合成で
まとめてから適用するのが一般的だから、更新のオーバヘッドもさほど気にならない

更に言えば、>>243のように(ライブラリを用いず)自前でリストを配列に見立てて
配列操作を実装するのは自由な選択だけど、メモリ効率を考慮しなければならないケースであれば、
(>>243のように)配列更新のたびにリストを丸コピーするのは、お馬鹿さんと言うしかない
リストの一要素だけを更新する時、更新した要素の tail リストは更新後のリストと共有できるはずだ

最後に、こういったパズル/ボードゲーム系の全解探索問題を記述する場合、何も考えず
ゲームの局面ごとに盤面全体を丸々コピーするコードを書いてしまうのは、純粋/非純粋な関数型に限らず
手続き型プログラミングであったとしても初心者レベルのコード設計力だと見なすしかない
通常、チェスや将棋のように膨大な空間を探索しなければならないゲームのプログラミングでは、
プレイの「一手(いって)」に関する情報だけを局面として記憶し、差分として管理する

１ · 2014/09/16(火) 20:55:03.92

ふーむ。
たしかにツリーをつかえば丸コピーは避けられるかもしれないな。
勉強になりました。

１ · 2014/09/16(火) 21:47:36.14

Data.Matrixがないって言われる…
なぜ？

$ ghc connect4_4.hs

connect4_4.hs:3:8:
Could not find module ‘Data.Matrix’
Perhaps you meant
Data.Ratio (from base)
Data.Ratio (needs flag -package haskell2010-1.1.2.0)
Use -v to see a list of the files searched for.

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.8.3

**240** · 2014/09/16(火) 22:18:12.61

>>273
cabal install matrix

１ · 2014/09/16(火) 22:31:31.46

>>274
ありがとうございます。コンパイルできました。
でも[[Int]]をMatrixに置き換えたらバグが発生。
ただいまデバッグ中です。

**デフォルトの名無しさん** · 2014/09/16(火) 22:50:04.77

>>253
アセンブラ以外で言語仕様にキャリーフラグが関与する演算子があるのは TL/1 しか見たことない

１ · 2014/09/16(火) 23:22:16.78

Matrix版できたっぽいのであげます。

http://www.age2.tv/rd05/src/up4372.txt

Matrixのindexは１から始まるそうなのでそれに合わせて外部仕様も変更しました。
いままでは列の指定が０～６だったのが１～７になります。
今思えば外部仕様まで変えることはなかったような気もしますが後の祭り。

**デフォルトの名無しさん** · 2014/09/16(火) 23:34:02.05

よく知られてるゲーム、GUIのあるゲームで頼む。
麻雀、OTHELLO、将棋、囲連星はwindowsGUIはある。

１ · 2014/09/16(火) 23:38:22.55

習作だから実用性はあんまり求めてないんだよなぁ。
connect4は小さい割に動いてるもの作ってる気になれるから気に入ってる。

**240** · 2014/09/17(水) 06:12:56.94

>>277
結構よいのでは。
しつこいけど、whereは1度使ってみたらいいんじゃないかなあ。
letで頭から読む/書くという感覚もわかるけど、
whereを使うと、1つの関数定義全体を宣言的に読む/書く感覚がわかると思う。

**デフォルトの名無しさん** · 2014/09/17(水) 12:19:24.89

>>268
>参照透過性は、プログラマが気にすることではない。(略)
>純粋関数型でコンパイルが通れば参照透過性がある。

コンパイル通るかどうか気にする必要あるじゃんかw

**デフォルトの名無しさん** · 2014/09/17(水) 13:02:50.04

>>268
> 純粋関数型でコンパイルが通れば参照透過性がある。

え？純粋関数型で型検査によって参照透明性を確保しているのはHaskellぐらいでは。

Haskell以外の、例えばMirandaやClean等の他の純粋関数型言語では、
型システムに依存せずに言語機能を制約して参照透明性を確保している
という理解なんだが。

**デフォルトの名無しさん** · 2014/09/17(水) 13:40:46.72

参照透過性は型とは関係ないだろ?
型があってもなくても破壊的代入があったらアウト。

**デフォルトの名無しさん** · 2014/09/17(水) 13:41:37.54

ちょっと本題から外れるが。

たしかに本格的に型システムと一体化させたのはHaskellからだけど、
Mirandaから参照透過性に対して型システムは使い始めてる。
MirandaでKAOSってOSを記述した時のinteract型が、
Miranda本体にも取り入れられてる。
この時に導入されたcomp, returnがmonadタイプの定式化の元になった。
E. Moggiが"Notions of computations and monads"で定式化して。
Haskellを設計、開発することになったのは、
この辺を本格的にやろうと思うとオープンソースじゃないとやりにくいから。

**デフォルトの名無しさん** · 2014/09/17(水) 14:19:32.02

>>284
確かにMirandaの評価戦略でのIO絡みの例外的扱いは、
HaskellのIOモナドの原型っぽい感じだな。

１ · 2014/09/17(水) 19:25:16.95

>>280
where使ってみました。
ただ、gameの中のletはどうやってwhereにすればいいかよくわからなかったのでletのままです。

http://www.age2.tv/rd05/src/up4389.txt

**240** · 2014/09/18(木) 17:39:55.46

>>286
doの中のletは仕方ない。そういうもの。
もう普通にHaskell入門レベルはクリアしてると思う。
不要な括弧が結構あるけど、それは単に慣れの問題だから構わないと思う。
おつかれさん。

１ · 2014/09/18(木) 19:52:18.04

>>287
ありがとうございます。

haskell触ってみたけど、今のところ関数型言語や参照透過性の有難さはあんまり実感できてない。
CPUのコアがもっと増えてコンパイラの最適化が今より強力になったらどうかわからんが、
C/C++より効率的なコーディングをするのは難しそう。

かといって生産性が劇的にあがるかというとそんな感触もなかった。
RubyにはC/C++より生産性高いと思わせるなにかがあったが
haskellとRubyを比べた時、はたしてhaskellのほうが生産性高いかといわれると？
もうちょっとデカいアプリを組んでみる必要があるのかもしれんが。

とりあえず、haskellでコーディングされた実用的で有名なアプリがあれば教えてほしいです。

**デフォルトの名無しさん** · 2014/09/18(木) 19:55:50.99

Monadius
1985年5月29日、そのゲームは、全国のゲーマーに衝撃を与えた。
らしい。
僕はよく知らない。そのときまだ生まれたばかりだったからだ。
20周年をむかえたグラディウスと、ゲームを、ゲームプログラミングを愛する人たちに感謝を込めて贈る。
http://www.geocities.jp/takascience/haskell/monadius_ja.html

１ · 2014/09/18(木) 20:11:37.12

>>289
これはすごいかも。

１ · 2014/09/19(金) 19:22:36.10

＞そういうデータの一塊であるMonadiusが、 updateMonadius, renderMonadius, isMonadiusOverという演算に関してGameを成す、と宣言されています。
これが圏論ってやつ？

**デフォルトの名無しさん** · 2014/09/19(金) 19:58:12.78

数学得意なら圏論から攻めてもいいと思うけど、
モナドは圏論わからなくても使うことはできるので...

１ · 2014/09/19(金) 20:19:26.79

数学は好きだけど下手の横好きだな。
>>291のことがわかればもうちょっとhaskell好きになれそうなんだけど。

**240** · 2014/09/19(金) 21:47:04.42

>>293
それ自体は圏論じゃなくて型クラス。
型gがGameクラスであるためには
そのupdate, render, isGameoverの3つのメソッドが必要だと宣言されていて、
Monadius型はGame型クラスのインスタンスです、
メソッドはそれぞれupdateMonadius, renderMonadius, isMonadiusOverになります、
というもの。

１ · 2014/09/19(金) 22:15:41.15

>>294
よくわからんがC++のテンプレートやjavaのインターフェースともちょっと違う感じ？

**デフォルトの名無しさん** · 2014/09/19(金) 22:17:11.20

これは最近よく目にするfilter-map-reduceとは違うの？

**240** · 2014/09/20(土) 07:19:58.23

>>295
型クラスは値ではなくて型のクラスってところがユニーク。

Haskellの型クラスはJava等のインターフェースより柔軟に使える。
Java等のインターフェースとクラスの関係は、
クラスを定義する時に「このインターフェースを実装します」と宣言するけど、
Haskellの型クラスでは、型クラスと型をそれぞれ別々に定義した上で、
「この型はこの型クラスのインスタンスだよ」と宣言する。
つまり、既存の型や既存の型クラスを使って、後から
「この型をこの型クラスのインスタンスとして使うよ」ということができる。

実は、286のコードでも型クラスのメソッドが多数使われている。
Ord型クラスのメソッドの>とか<とか、Eq型クラスのメソッドの==とか。
あと、game関数やmain関数の型を見ると、IO型クラスを使っていることがわかる。

**デフォルトの名無しさん** · 2014/09/20(土) 12:34:10.95

C++14で型クラス的なconceptってのが入りそうになったけど、
時期尚早ってことで見送られた。
次にStroustrupが簡略化した版が入る予定。

**デフォルトの名無しさん** · 2014/09/20(土) 17:49:48.64

>>1は何をしたいんだ。
関数型言語は効率が悪そうたって、「集合論に基づいた言語」とかいうのはもっと効率が悪くなるだろうに。

１ · 2014/09/20(土) 22:48:20.83

>>297
すいません。後付けできるってのがよくわからないです。
コンパイル時には明示的に宣言しないといけないのは型クラスもインターフェースも同じですよね？

>>299
集合論に基づいた言語は教科書の章末問題をサクサクっとインプリメントすることを目的としてる。
実用性はあんまり求めない。

**デフォルトの名無しさん** · 2014/09/20(土) 23:24:10.24

http://en.wikibooks.org/wiki/Haskell/Classes_and_types
のA concerted exampleと同じことをtype classなしで書いてみれば?
type classがあると細々としたことまで、
少ないコード量で強く型付けできることが分かるはず。

**デフォルトの名無しさん** · 2014/09/21(日) 13:51:15.50

>>288
> haskell触ってみたけど、今のところ関数型言語や参照透過性の有難さはあんまり実感できてない。
参照透明の良さっていうのは、逆から言うと、状態が沢山あるコードはクソだ、ってこと。
停止性問題で難題になったのは、状態が少し増えるだけで組み合わせの数が爆発すること。
再代入が減らせれば、コードの複雑性が減ることがあるから、参照透明がありがたい。
関数型の良さは、宣言型言語であること。参照透明は関数型言語の目的ではなく、それを必要としているというだけだ。

生産性が劇的に上がるかというと、c++でテンプレートメタプログラミングしてる人からそれを取り上げたら劇的に生産性が下がると言うだろうし、const をc++から取り除いても劇的に生産性が下がるだろう。
Ruby と haskell を比べても仕方ない。
一つのプロジェクトで一つの言語しか使えないわけではないのだから、部分によって、書きやすい言語、高速な言語、ライブラリの充実した言語を使い分ければよい。
そして Ruby でも関数型スタイルで一部を書くことができる。

なんかちょっと固定観念が強い気がする。
あとコンピュータサイエンスと言語の歴史を知らないのにあれこれ分かったつもりになってるように見えるのが不安。

**デフォルトの名無しさん** · 2014/09/21(日) 14:55:43.06

「集合論に基づいた言語」をつくるうえで参考になるかもしれないということで関数型言語の話が
出てきているんだろうけど、>>1はそれについて、参考になったとか、自分が考えているのとはこう違うから
参考にならなかったという話はせず、効率やら生産性の話をするんだよな。
「集合論に基づいた言語」で効率や生産性の向上を目的としてないなら、関数型言語で効率や生産性の向上が
なくてもどうでもいいことだと思うけど。

**デフォルトの名無しさん** · 2014/09/21(日) 15:30:26.77

無限集合を扱おうとすれば、関数型言語にあるような遅延評価か、論理型言語にあるような全解収集をするしかないだろ。
要素の重複を認めないのなら、生成されたものがすでに集合に含まれているかどうか調べるためのしくみも必要だし。
集合の包含関係はどのように調べるんだろ。

それとも数式処理のようなものを考えているのかな。

１ · 2014/09/21(日) 16:27:12.72

>>302
関数型言語には状態がないってのはなんとなくしっくりこないなぁ。
状態はあるけど考慮しなきゃいけないスコープが関数の引数に限られるってイメージなんだが。
あと、参照透過性を守ったって停止性問題が根本的に解決するわけじゃないよね？

＞なんかちょっと固定観念が強い気がする。
まあ、おれもいいおっさんだからな。
それなりに固定観念はあるだろう。

＞あとコンピュータサイエンスと言語の歴史を知らないのにあれこれ分かったつもりになってるように見えるのが不安。
これは自覚症状ないんだが。たとえばどの辺が分かったつもりの発言になってる？

>>303
言語を評価するとなったら効率か生産性かだろう。
集合論に基づいた言語では狭い領域の問題に限り（教科書の章末問題とか）
高い生産性を発揮することを目標にしてる。
関数型言語触ってみたけど>>286のコードに関していえばヒントになるようなものはなかった。
型クラスとかは勉強すれば面白いのかもしれん。

１ · 2014/09/21(日) 16:55:50.54

>>304
無限集合は扱いが難しいので、できれば無しの方向で。

**デフォルトの名無しさん** · 2014/09/21(日) 19:35:49.05

無しの方向ってどうするの?
自然数全体の集合等を扱わないとか、内包的記法を扱わないとか。

1 · 2014/09/21(日) 20:23:58.88

自然数全体の集合の部分集合は基本的に表現するのに無限のビットを必要とするので。
遅延評価とか使えばある程度ごまかせるかもしれないけど、
遅延評価つかっても無限集合の包含関係とかは計算不能な場合もあるので、無限集合は扱わない方向で。

内包的表記は有限集合だけに使えるようにするとか。

**デフォルトの名無しさん** · 2014/09/21(日) 20:27:48.01

∞という数・文字をあつかえばいい。
{ 2n | n=1,・・,∞}は無限集合。

**デフォルトの名無しさん** · 2014/09/21(日) 20:40:29.63

無限大を扱うのも無限小を扱うのも似通ったもので。1/xで反転するので。
時空間で無限小を扱わない量子重力理論を思い出した。

時空の原子を追うループ量子重力理論　　L.スモーリン（カナダ・ペリメター理論物理学研究所）

私たちは空間も時間も連続したものだと考えているが，実は大間違いかもしれない。
相対論と量子力学の統合を目指す新理論によると，「時空の原子」が存在する。
アインシュタインが果たせなかった難問解決の道筋が見えてきた。
量子力学と一般相対論の基本原理を注意深く組み合わせることで，「ループ量子重力理論」が生まれた。
この理論によると，空間は個別の小さな塊からできていて，最小の塊の体積はおよそ１立方プランク長（10-99cm3）だ。
時間の進みは飛び飛びで，その最小単位はおよそ１プランク秒（10-43秒）となる。
ループ量子重力理論は純粋に理論的な研究の成果だが，実際に検証できる可能性がある。
例えば，空間の構造が離散的だとすると，そこを伝わる光のスピードは波長によってわずかに異なる。
この観測が可能な天文衛星が計画されており，時空の離散的構造から生まれる効果が近い将来に確かめられるだろう。
http://www.nikkei-science.com/page/magazine/0404/loop.html

１ · 2014/09/21(日) 20:47:19.79

>>309
簡単にいうけど、実際に実装するのは結構難しいんじゃないかな。

**デフォルトの名無しさん** · 2014/09/21(日) 20:49:08.07

量子重力理論でフリードマン方程式に到達 ―築き上げられた「ミクロからマクロへの架け橋」

「ビッグバンの只中に何が起こっていたのか」ということについては、現行の物理学では説明を下すことができない。
この二つを統合させた「全方位的な」理論が――量子重力理論が ――求められているところであり、研究が進められている。
この度、ドイツとカナダの研究チームによってPhysical Review Lettersに発表された重大な発見は、まさにこの路線に沿ったものだ。

発表された理論によれば、空間はこれ以上分割することのできない、ほんの小さな「土台、構成要素 (building blocks)≒ 素空間」からできているという。
この着想を出発点として彼らが到達したのは、宇宙論の方程式のなかでも最も肝要なものの一つとして見なされている「フリードマン方程式」だ。
今回の成果は、量子力学と相対論が実際に統合可能であるということを示している ――
http://livedoor.blogimg.jp/dogon23/imgs/a/4/a4fed584.jpg

アインシュタインによる一般相対性理論では重力が扱われており、言うなれば「マクロな世界」を一般的に記述するのが相対論だ。他方、量子力学が扱うのは原子や素粒子といったような「ミクロの世界」だった。
両理論ともに、それぞれの縄張りの領域では成功を収めてきたが、プランクスケールのような極限的な状況においては破綻してしまう、という難点が指摘されていた。

水が原子から構成されているのとまったく同じように、空間はある種の「原子」から ――素空間から ――構成されているのではないか、とOriti氏は想像している。
そして、二つの理論を統合することのできるような新たな理論ではこの「空間の原子」を記述することが切に求められるというわけであり、その理論が冒頭でも触れた「量子重力理論」だ。

アインシュタインの相対論では、時空は連続的なものとして捉えられている。
しかし、Oriti氏らによる数学的なタスクでは、空間を極小の「素空間」へと分解して、これに量子力学を適用させることが試みられた。
それにより空間に、ひいては空間を記述する相対論に量子力学を応用してみる、というのがチームの企てだった。
http://livedoor.blogimg.jp/dogon23/imgs/7/2/7207d807.jpg
http://blog.livedoor.jp/dogon23/archives/31545793.html

**デフォルトの名無しさん** · 2014/09/21(日) 22:44:17.86

>>308
>無限集合は扱わない
>内包的表記は有限集合だけに使えるようにする

こういうのはどうするんだ?

p(a,b) : a,bは(0以外の)自然数で、aはbで割り切れる
としたとき、
{x|p(x,1)} = {1,2,3,…}
{x|p(1,x)} = {1}

**デフォルトの名無しさん** · 2014/09/22(月) 01:03:15.50

>無限集合は扱わない方向で。

オートマトンが受理する列の集合が無限集合になることもあるけど
それも扱わないのか?
>>83

**デフォルトの名無しさん** · 2014/09/22(月) 01:29:01.36

ZFC

**デフォルトの名無しさん** · 2014/09/22(月) 01:30:24.14

ブール代数

**デフォルトの名無しさん** · 2014/09/22(月) 01:32:50.90

3値論理

１ · 2014/09/22(月) 06:51:14.13

>>313
両方扱わない。
それは、p(1,x)の計算結果がたまたま有限集合になってるだけで、
定義域は無限集合なので扱わない。

>>314
オートマトンが受理する列の集合を変数として扱うことはしない。
関数として受理するかしないかを判定することはもちろんできる。

>>315
ZFCから導き出される真の式の集合とかは変数として扱わない。

>>316
ブール代数は基本的に有限だよね？

>>317
マイナーすぎじゃね？

**デフォルトの名無しさん** · 2014/09/22(月) 06:55:11.39

>>318
では逆に、HaskellやPythonのリスト内包表記じゃダメな理由は？

１ · 2014/09/22(月) 08:32:07.69

遅延評価が必要になる。
めんどくさい割に実用的じゃないと思う。
haskellの無限リストを使うときだって最後はtakeとか使って有限集合に落とすんでしょ？

**デフォルトの名無しさん** · 2014/09/22(月) 11:31:48.61

>>291
何の関係もない。

**デフォルトの名無しさん** · 2014/09/22(月) 11:34:43.17

>>305
>状態はあるけど考慮しなきゃいけないスコープが関数の引数に限られるってイメージなんだが。

それが関数に状態がないということ。
引数が同じなら同じ結果を返す。
数学的な関数の定義に等しい。

**デフォルトの名無しさん** · 2014/09/22(月) 12:49:44.48

> haskellの無限リストを使うときだって最後はtakeとか使って有限集合に落とすんでしょ？

takeのように単純な関数だとは限らない。
ゲーム木の探索の枝刈りのようなややこしい条件で止めたりするから意味がある。

まあただtwitterで、らくだの人と川の人が時々論戦しているように、デフォルトで
なんでもかんでも遅延か、遅延にしたいものだけ明示的に遅延にするのが良いのか？
は、まだ結論が出ていないとは思う。

**デフォルトの名無しさん** · 2014/09/22(月) 15:09:16.19

無限集合を扱わないで

>教科書の章末問題をサクサクっとインプリメントする

のはちゃんとできるのかな。
できるんだったら >>15みたいなことを言わずに最初から有限集合に限定と言えば良いわけで。

**デフォルトの名無しさん** · 2014/09/22(月) 16:52:16.32

有限集合限定なら言語なんか作らずにライブラリで済むんじゃないか。
それにライブラリ作らなくても、Maximaなら要求よりももっと複雑なこともできる。

**デフォルトの名無しさん** · 2014/09/22(月) 17:18:16.63

A. 無知ゆえに（ありきたりな）発想が溢れている人、行動力がある人
B. 知識でがんじがらめになって発想が死んだ人

たいがいこのどっちかに当てはまってしまう。そして結局このスレもAとBとの対立構造に終始して終わる。

１ · 2014/09/22(月) 18:14:10.47

>>322
そういわれるとそんな気もしてきますね。

>>323
ゲーム木の探索で遅延評価使うとminmaxがαβになったりするんでしょうか。
さすがにそこまではない？

>>324
無限集合を使って生産性が上がる例があるなら教えてほしいです。
無限集合は面白い概念だけど扱いが難しい。
正直>>15のときは無限集合の実装の大変さの見通しが甘かったと言わざるを得ない。

>>325
＞有限集合限定なら言語なんか作らずにライブラリで済むんじゃないか。
その可能性はありますね。

＞それにライブラリ作らなくても、Maximaなら要求よりももっと複雑なこともできる。
Maximaは昔少しだけ触ったことあるけど色んな事が出来るっぽいですね。
素因数分解とかやらせてみたことあります。

>>326
まあ、最悪なにも形あるものは生み出せなくても私は勉強になってますけどね。

**デフォルトの名無しさん** · 2014/09/22(月) 19:40:23.96

>>326
Aのほうが遥かにマシだな。
ありきたりでも行動していればそのうちありきたりじゃない発想が出る。
行動する人に対して既存の知識を振り回して笑うことしかできない奴は
いつまでたっても何もつくれない。

**デフォルトの名無しさん** · 2014/09/22(月) 20:07:25.83

>>327
生産性が上がる例とかいうのは知らんけど。
俺が何冊か見た集合論の教科書は無限集合を扱ったものばかりだったから、
無限集合を扱えない処理系で
>教科書の章末問題をサクサクっとインプリメントする
なんてできるのかなと思った。

無限集合を扱っている教科書を想定してたから>>15になったんだろ?

**デフォルトの名無しさん** · 2014/09/22(月) 20:21:24.00

あたし中卒やからね　仕事をもらわれへんのやと書いた
女の子の手紙の文字は　とがりながら震えてる
ガキのくせにと頬を打たれ　少年たちの眼が年をとる
悔しさを握りしめすぎた　拳の中　爪が突き刺さる

１ · 2014/09/22(月) 20:46:51.62

>>329
>>15は>>13で話振られたから答えただけ。
実は集合論の教科書はあんまり想定してなくて、離散数学の教科書を想定してた。

**デフォルトの名無しさん** · 2014/09/22(月) 21:29:11.48

集合を言語へどう使うか決まってないし、有限・無限とか細かい部分を決めても意味ないだろ。
スタンダードな言語に対して、集合が扱える仕組みが取り込めばいいだけなのかとか。

**デフォルトの名無しさん** · 2014/09/22(月) 21:48:28.53

集合論の教科書を想定せずに
>発想から徹底的に集合論的思想で言語仕様を考える
と言ってたのか…
で、結局、有限集合限定だから
>言語なんか作らずにライブラリで済む
んじゃないか、と…

**デフォルトの名無しさん** · 2014/09/22(月) 21:54:05.38

ライブラリを作ってみてライブラリではここが不満だって気づいてから言語作り始めても遅くない。
そういう下地があると１ヶ月くらいでコンパイラを書ける。凡人でも。

**デフォルトの名無しさん** · 2014/09/22(月) 21:56:13.85

>>330
ファイト！

**デフォルトの名無しさん** · 2014/09/22(月) 21:58:03.07

>>332
>有限・無限とか細かい部分を決めても意味ないだろ。

一番大きい部分だろw

**デフォルトの名無しさん** · 2014/09/22(月) 22:23:43.15

>>336
どういう用途に使うかに強く依存する。
たとえば、プログラムコードは有限だから、それを有限集合で表現するのは可能だろう。
最初に何に使うのかが決まらないと、有限・無限はどうするか決まらない。

**デフォルトの名無しさん** · 2014/09/22(月) 22:31:18.61

>>337
>たとえば、プログラムコードは有限だから、それを有限集合で表現するのは可能だろう。

何言ってるかさっぱり分からん。

>有限・無限とか細かい部分を決めても意味ないだろ。

とどう関係するんだ?

**デフォルトの名無しさん** · 2014/09/22(月) 22:51:19.51

任意のプログラムコードを、ある自然数に対応させることは可能のはずだ。この値は有限値で。
具体的には、ゲーデル文構成のようにしたらいいと思うが良くはわからん。

ゲーデルの不完全性定理 - Wikipedia
ゲーデルの不完全性定理とは、数学基礎論における重要な定理の一つで、クルト・ゲーデルが1930年に証明したものである。
ゲーデル文の構成
ゲーデル数というテクニックを使って間接的に自己言及を可能とし、ゲーデル文を構成する。
コンピュータでは全てのデータを一意な数値で表しており、特に文字列や論理式そして論理式の列も数値で表す。
このように、論理式を数値で表す行為を論理式のゲーデル数化といい、命題Pに対応する数値をPのゲーデル数という。

**デフォルトの名無しさん** · 2014/09/22(月) 22:56:41.54

ゲーデル数 - Wikipedia
ゲーデル数は、数理論理学において何らかの形式言語のそれぞれの記号や整論理式に一意に割り振られる自然数である。
一般化
計算可能性理論において、「ゲーデル数化」は上述よりさらに一般化した意味を持つ用語として使われる。
1.形式言語の構成要素に自然数を割り当てて、形式言語の構成要素の操作を、数を操作するアルゴリズムでシミュレートできるようにする。
2.より一般化して、枚挙可能な数学的オブジェクトに自然数を割り当てて、その数学的オブジェクトにアルゴリズム的操作ができるようにする。
これは数というよりも文字列を操作する計算模型（チューリングマシンなど）に必須の考え方である。

チューリングマシン - Wikipedia
チューリング機械とは次の7つ組である。
http://upload.wikimedia.org/math/6/3/d/63d3280aa62307d33bea8f0e64f4dac7.png
Q は有限集合であり、その元を状態という。
Γ は Q に交わらない有限集合であり、字母とよばれる。その元を記号という。
b は Γ の元であり、空白記号とよばれる。
Σ は Γ - {b} の部分集合であり、入力字母とよばれる。その元を入力記号という。
δ は Q × Γ から Q × Γ × {left, right} への写像であり、遷移函数とよばれる。δ(q, a) = (q', a', m) は、
「現在の状態が q であり、着目位置にある記号が a であれば、状態を q' に移し、着目位置に記号 a' を書き込んでから、着目位置を m 方向に1つずらす」と読む。
qinit は Q の元であり、初期状態とよばれる。
qacc は Q の元であり、受理状態とよばれる。

**デフォルトの名無しさん** · 2014/09/22(月) 23:19:51.98

お前アホだろ。
>プログラムコードは有限だから
ってコード長が有限ってことを言いたかったのかよ。

**デフォルトの名無しさん** · 2014/09/22(月) 23:51:04.16

言語の開発以前に、無限にするか、有限にするか決めたとして。
有限の範囲ではおさまらない具体的な例・モデルってあるのか?
既存のコンピュータ、ノイマン型は、有限集合で操れるから具体的にイメージ出来ない。

**デフォルトの名無しさん** · 2014/09/23(火) 00:04:48.04

とりあえず有限長の語の集合が無限集合になりうることくらいは理解してくれ。
証明が無限を扱うことと、証明長が有限なことは全然別の話。
プログラムにしても同様。

**デフォルトの名無しさん** · 2014/09/23(火) 00:11:51.00

>>343
それは分かってて。
さきに無限を使うと選択した場合、具体的な利用法が不明。
既存のプログラム、有限集合で扱える範囲を超えなかったら意味が無い。

１ · 2014/09/23(火) 00:23:18.08

>>344
計算不能な集合を扱いたいの？

**デフォルトの名無しさん** · 2014/09/23(火) 00:32:18.88

言語を開発する上で、既存の有限集合に基づくモデルで十分だという立場。
無限を扱うメリットを知りたい。

**デフォルトの名無しさん** · 2014/09/23(火) 00:50:04.92

無限小、無限大を取り込んでない、自然数に基づく数学に、あとから無限小、無限大を取り入れても矛盾しない。

超準解析 - Wikipedia
超準解析ではイプシロン-デルタ論法によって一度は数学から追放されたと思われた、無限小や無限大という極限に関する古典的で
直観的な感覚、すなわち、いわゆる実数論にもとづかないライプニッツ流の古典的な微積分を数学的に厳密に定式化し、取り戻すことができる。
このような古典的な微積分におけるオリジナルな無限小解析学とは区別されることもある。
アブラハム・ロビンソンによって考案された。超準解析の基本的な手法である超積はアラン・コンヌらによって作用素環の研究に応用されてもいる。
超実数は実数を拡張した数概念である。実数体に無限小・無限大を加えたものは体をなし、超実数体と呼ばれる。
超実数体は *R, R* などと表記される。その元を超実数という。

Rubyによる超準解析クラス.(HyperRael,MathExt)
超実数体とは,(大雑把に云えば) 実数体にライプニッツ的な無限小を添加して出来る体のことだ.
微分等, 通常の実数では limit を使う場面で, 超実数体内部の四則演算として直接求めることが出来る.
超準的な計算では, 無限小や∞の強さもわかるので無限小/無限小, 無限小*∞, ∞/∞ 等の計算が矛盾無く解釈可能となる.
ただし単なる体なので, 真の0(無限小でなく) については, 0*∞＝0 で, 0/0 や 1/0 は定義されない.
この点は IEEE754 的な浮動小数点計算で 1.0/0.0 で Infinity を返すような気持の悪さは解消できる.
http://www.math.kobe-u.ac.jp/~kodama/tips-HyperReal.html

**デフォルトの名無しさん** · 2014/09/23(火) 00:58:09.60

んなもん、チューリング完全な言語は能力同等なんだから
無限をその言語機能で直接書きやすく実行効率よくするかどうかの判断しだいだよ
で、1はもう無限を直接扱うのはあきらめたんでしょ

今度は有限の制約があっても、1が元々やりたかった範囲がカバーできてるのかって問題になるわけだが、
「やりたかった範囲」がぼんやりしてるからこれ以上はわからんわな

**デフォルトの名無しさん** · 2014/09/23(火) 01:02:03.65

おっと書きわすれた。まあ俺もみんながいってるように、
まず既存言語+ライブラリでやりたいことがどの程度できるのか確かめる
のがいいと思うけどね

**デフォルトの名無しさん** · 2014/09/23(火) 11:31:06.71

無限集合を扱わない代わりにストリームを集合として扱えるようにしようぜ

**デフォルトの名無しさん** · 2014/09/23(火) 11:38:18.07

無限集合を扱うのが困難なように言っているが、どういう操作を実装するか次第だろう。
例えば分数ライブラリがあるが、必要になればいくらでも循環小数や無理数の桁を取り出せ、しかし普段は分子と分母を保存しておくだけ。
それをさらに除算以外の演算もサポートした、値を式で保持するライブラリもある。
実際に何かの集合を扱うたびに本物のコンテナを生成するよりもマシな気がするけど。

>>305
> 関数型言語には状態がないってのはなんとなくしっくりこないなぁ。
変化しないものは状態といわない。
例えば人間には生と死という状態があるが、親が人間かどうかというのは変更がないから状態とはしない。
プログラムでいえば再代入のあるものが状態だ。
c/c++のconst変数は建前では参照透明だ(キャスト、mutableがであるので実際は違う)。
本当に関数型言語に状態がないかどうかは言語によるし、システムコールによる副作用があっても参照透明と呼ぶのはレトリックと言われても仕方ない気もする。
特定の言語自体の価値よりも、関数型プログラミング的テクニック全体に価値がある。c++でもPythonでも使える。

> あと、参照透過性を守ったって停止性問題が根本的に解決するわけじゃないよね？
難題とか複雑性が減るとかいう表現を使ったのは、停止性問題の証明には関係ないからだよ。

> これは自覚症状ないんだが。たとえばどの辺が分かったつもりの発言になってる？
>288 を読んで知ったかぶりらしく思わない人がどれだけいただろうか。

**デフォルトの名無しさん** · 2014/09/23(火) 12:03:18.67

>>326は嘘で、無知で発想が支離滅裂で実行力もない人が多いみたいです。

**デフォルトの名無しさん** · 2014/09/23(火) 16:14:06.99

実装に寄らないクラス定義、メソッド、オペレータ、その処理の定義決めればいいんじゃね
オペレータオーバーロードできない処理系ではオペレータの代わりにメソッド実装でいいし、しっかり概念が定義されてたらどの言語にも移植できるやん

1 · 2014/09/24(水) 20:26:39.07

うーん。とりあえず、集合のリテラルがある言語、またはリテラルを自作できる言語ってある？

**デフォルトの名無しさん** · 2014/09/24(水) 20:34:18.13

C++11

**デフォルトの名無しさん** · 2014/09/24(水) 20:46:24.29

Pascalの型に集合はあったけど、リテラルあったっけ？

１ · 2014/09/24(水) 21:32:20.18

C++11すげぇｗ
正気の沙汰とは思えないｗ
しかしこれ、setみたいなテンプレート型のリテラルもちゃんと作れるのかなぁ？

**デフォルトの名無しさん** · 2014/09/24(水) 21:47:35.83

つうかC++11使ってリテラル定義しなくても、初期化子書けばいいだけ。

１ · 2014/09/24(水) 21:59:47.35

std::initializer_listなんてものもあるのか。
世の中知らないうちに便利になってるな。

**デフォルトの名無しさん** · 2014/09/24(水) 22:19:34.82

VDM http://en.wikipedia.org/wiki/Vienna_Development_Method
Z http://en.wikipedia.org/wiki/Z_notation

**デフォルトの名無しさん** · 2014/09/25(木) 22:46:08.06

>>1 >>360
あーまだそんなこと言ってるのか

１ · 2014/09/26(金) 20:57:23.89

C++１１結構面白そうだが完全準拠したコンパイラが無いっぽい？

**デフォルトの名無しさん** · 2014/09/26(金) 21:17:42.44

お前のOSにゃ無いかもしれんな

１ · 2014/09/26(金) 21:24:17.23

とりあえずVisual Studio 2013 Express でいじってみてるけど結構楽しい。

int _tmain(int argc, _TCHAR* argv[])
{
set<set<int> > a = { { 1, 2 }, { 3 }, { 4, 5, 6 } };
for (auto i : a){ for (auto j : i) cout << j << " "; cout << endl; }
return 0;
}

とか書けていい感じ。

**デフォルトの名無しさん** · 2014/09/26(金) 21:37:43.18

>>1はC++のように集合が扱える言語が実現したいのか?
一部のスクリプト言語だったらかなり以前からできていなかったか。
CでもC++でも以前から、ライブラリで拡張したら集合は扱えたはずだろ。

１ · 2014/09/26(金) 21:56:27.24

>>365
個人的にはもうちょっと言語の設計が根本から変わるようなものが
集合にはあるんじゃないかと思ってるんだが。
それがなんだかは分からないｗ
いまのところ集合を普通のライブラリとして用意する以上のアイディアは出てない。

**デフォルトの名無しさん** · 2014/09/26(金) 22:40:52.33

（>>856 の続き）

始めは「考えられるリスクの低減」から
・ライブラリや共通部品の多くは(アルゴリズムやデータ変換を実現する単純なものもあるが)
　データベース/ファイル／ネットワーク/プロセス間通信といったプログラムの
　外部インターフェイス処理が多くを占める
　これらを実装するには、プログラマにシステムコールや標準ライブラリ(>>829)、
　そして社外のライブラリや社内の共通部品等等、幅広い知識が求められる
　これを経験の浅いメンバに負わせるのは無謀
・ライブラリ/共通部品の実装技術は機能仕様(=ビジネスルール)には依存しないから、
　類似のシステム開発プロジェクトがあれば、類似の実装になる
　もしライブラリ設計担当がいくつかのプロジェクトを経験したベテランであれば、
　過去の(失敗を含めた)経験から、既存の設計やコードを改造母体にして短期間で設計できる
　これと同じことを経験の浅いメンバに期待するのは無茶
・万が一、ライブラリ/共通部品の開発日程が遅延して結合テストに間に合わなかったり、
　結合テストでバグが多発する事態になれば、その影響はプロジェクトの全体に及ぶ
　もしモスク(>>856)の中位/上位層であれば影響範囲は限定的だし、
　その炎上の火消しのためにライブラリ/共通部品を担当させて余力のあるベテランを投入できる
　（当然、ライブラリ/共通部品設計には日程厳守(or 前倒し)と高品質(=バグ0)をベテランに要求する）

１ · 2014/09/26(金) 22:44:11.22

>>367
仕事でやってんじゃないんだから好きにさせろ。