サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
iPhone 16
www.ice.nuie.nagoya-u.ac.jp/~h003149b
もともとは、values、call-with-valuesを むりやり使うという趣旨だったので、 色々変かも。 valuesを使った関数の例 自然数nは必ず、 n = (2^k)*q ; qは奇数 という形に書く事ができる(例えば、80 = (2^4)*5、246 = (2^1)*123)。 自然数をこのような形に表す事を、 とりあえず「kq分解」とか「偶奇分解」とか呼ぶ事にする (実際には、そんな言葉は無い)。 このkとqを求める関数は、valuesを使って次のように書ける。 (define (k&q n) (let loop ((k 0) (q n)) (if (even? q) (loop (+ k 1) (/ q 2)) (values k q)))) この関数を使って、ミラー・ラビンテストを行なう関数を作る。 フェルマー(Fermat)テスト nが素数の場合、1<=a<nとなるa
「証明」という言葉と「計算」という言葉 「計算」という言葉の説明 「証明」という言葉の説明 ここまでのまとめ 補足:「完全」という言葉について 対角化定理と再帰定理 対角化定理 再帰定理 ラムダ計算との関係 第1不完全性定理、停止問題、その他 第1不完全性定理の証明 停止問題、真を表す述語の定義不可能性 自然数論の決定不能性 補足: 「決定可能」「決定不能」という言葉について 第2不完全性定理 第2不完全性定理の証明 第2不完全性定理の内容 補足: ヒルベルトの形式主義(ヒルベルト・プログラム) まとめ 文献 「証明」という言葉と「計算」という言葉 論理学についての話や説明をする場合、 「証明」とか「証明できる」という言葉がふたつの意味で使われる。 ひとつは数学とか日常で普通に使うのと同じ普通の意味での 「証明できる」(何かの正しさを筋道立てて示すことができる)で、 もうひとつは形式的な論
「ホワイトライト」がどんな話だったかほとんど憶えてない。 連続体問題については容易に参照できる資料がたぶん色々あるはず。 でも「ホワイトライト」の解説もかなりいい加減だった気がするので、 気にしない事にする。 とりあえず関係ありそうな出来事をいくつか並べておく。 1878 カントールが集合論の第2論文で連続体仮説を述べる 1900 ヒルベルトが23の問題のひとつに連続体問題をあげる 1902 ラッセルのパラドクス 1908 ツェルメロが集合論の公理系を提示 1922 フレンケル、スコーレムが置換公理を追加 1939 ゲーデルが連続体仮説の無矛盾性を証明 1946 ゲーデル「カントールの連続体問題とは何か」 1963 コーエンが連続体仮説の独立性を証明 「濃度」「基数」「連続体問題」の説明 連続体問題を説明するには、まず「濃度」とか「基数」の説明がいる。 何かと何かを比較するやり方のひとつに
よく知らない事についていい加減に説明するパターン。 「アスペクト指向プログラミング」 まずAspectJに関する簡単な紹介を読むと、機能だけなら メソッド結合、多重継承、リフレクションあたりで実現できるように見える。 多重継承に対するミックスインみたいな事で ある種の作法のようなものなのかというと、 紹介を読む限りそんな風には書いてない。 「アスペクト」というのは、 複数のクラスにまたがって存在するような問題とか関心事とからしいけど、 例えば多重継承で処理できるような事はアスペクトなのかどうかとか いまいちはっきりしない。 アスペクトの例として例外処理とかパフォーマンスの最適化とかが挙がっているけど、 例外処理はともかく最適化にAspectJの機能をどう使うのかもよく判らない。 元論文らしいKiczalesらの「Aspect-Oriented Programming」を読む。 Aspect
いくつかの問題 停止問題 プログラムを実行すると、 実行が終了して停止するか停止せずにいつまでも実行を続けるかの、 どちらかになる。 そこで、与えられたプログラムが停止するか、 いつまでも停止しないかを判定する、 という問題(プログラムの「停止問題」という)を考える。 (この問題をちゃんとした問題として扱うには、 プログラムがどう実行されるのかが 正確に(処理系依存とかのあいまいさ無しに)定義されている必要がある。 だから普通は、チューリングマシンみたいな できるだけ単純な道具立てを使って話をする。 でも、ここでは細かい事にはこだわらず、 「適当にどうにか定義してある」事にしておく。) 停止問題を解くプログラムを作りたいとする。 これは、コンパイラと比較すると判りやすいかもしれない。 コンパイラはプログラム(のソース)を受けとり、 実行コードを出力する。 停止問題を解くプログラムは、 プロ
戻る Mattias Felleisen, Amr Sabry 「Continuations in Programming Practice: Introduction and Survey」 を訳したもの。 参考文献のところが省略されていたりして、まだいいかげん。 Continuations in Programming Practice: Introduction and Survey Mattias Felleisen, Amr Sabry 目次 1. 計画 2. 制御スタックと継続 2.1 関数の呼出しと戻り 2.2 再帰呼出し 3. 評価器の制御状態 3.1 Tiny Schemeの定義 3.2 自然意味論 3.3 項書換え 3.4 実践: 他の言語の評価 3.5 CEK機械 4. 継続を操作する 4.1 エラー脱出 4.2 ラベルとジャンプ 4.3 例
ワンのタイルに関する決定問題についての説明 (説明不足)。 ワンのタイルというのは4辺それぞれに文字列(記号列)が書いてある四角いタイルで、 タイルを並べる時の規則があって、 接している2辺に書かれている文字列は同じでないといけない。 またタイルを回転させてはいけない (もともとのワンのタイルは各辺に記号が書かれたタイルではなく 各辺が色づけがされたタイルで接する辺は同色という規則みたいだけど、 説明の都合で変更した)。 そして、 与えられたタイルのリストに対して それらのタイルだけを使って全平面をタイル張りできるかを判定せよ、 というのが問題。 ただし与えられたタイルを全部使う必要は別に無い。 例えば、次のようなタイルを与えられたとする。 これらタイルの場合、 次のような並びを繰り返していくことで全平面をタイル張りできる。 ワンは初め全面敷き詰め可能かどうかは判定可能だと考えたみたいだけ
自分自身を出力するプログラムを書いてみる事にする。 あたりまえだけど、プログラム全体を文字列とかリストにして、 プログラム中に埋め込むわけにはいかない。 でも全体は無理でも、 プログラム内の一部分だけなら文字列やリストにして利用することはできる。 そこで、プログラムを、 Aパート ... プログラムの一部分を、単に文字列とかリストにしたもの。 Bパート ... プログラム全体を出力する部分。 の2つに分けて考える。 Aパートは、Bパート(または、その一部分)をリテラルとして保持して、 Bパートがそれを利用して全体を出力するという役割分担になる。 Schemeの場合 簡単のために Schemeで考える(Lispでも動く)。 プログラムの構成は、大まかには、 (<Bパート> <Aパート>) みたいになる。 とりあえず、AパートはBパートそのものをリストにしていると考える。 するとAパート
Lispの最大の特徴は、S式と呼ばれるカッコだらけの表記法だろう。 そのほかにも色々特徴とされる事柄はあるけど、 たいていの特徴については、 同様の特徴を持ってて広まっている言語が他にもある。 だからわざわざLispを使う理由はあんまりないと思う。 多分Lispを使いたくなるかどうかは、 S式を(カッコに辟易しつつも)好きになるかどうかにある。 「Lispは、うっとうしい大量のよけいなカッコといっしょに さまざまな物を手にいれました。その後、 ほかの人々も大量のカッコ以外の全てを手に入れました」 リスト 名前が LISt Processorから来ているだけに、 Lispにとってリストはものすごく重要だし、 プログラムの構造とも深く結び付いている。 でもデータ構造としてのリストは、 MLや Haskellのような関数型言語でも重要で、 例えばリストのパターンマッチングとか リスト操作に関する
サンクトペテルブルクのパラドックスと呼ばれる問題を取り上げる (このパラドックスの日本語表記にはかなりぶれがあるみたいで 他にも、聖、セント、セイント、ペテルブルグ、ペテルスブルグ、ピータースバーグなど 色々な表記がある)。 (もともとは、確率解釈における主観説を批判する文章として書いたものの一部。 なので、最後ら辺は蛇足ぎみ) サンクトペテルブルクのパラドックスとは次のようなものである。 次のような賭けを考える。 表と裏の出る確率がそれぞれ1/2のコインを表が出るまで振る。 そして表が出たのがn回目に振ったときなら、 賞金として2^n円がもらえるとする。 いくらの金額だったらこの賭けをやるだろうか。 賞金の期待値を求めると、 ∞ E = Σ(2^n / 2^n) → ∞ n=1 となる。 したがって、いくら払ってもこの賭けをやった方が良いことになる。 しかし、10回目に初めて表が出ても1
タイトルどおりGaucheでスクリプトを書いてみたその体験について記す。 書きたいプログラムが先にあったわけではなく、 Gaucheでスクリプトプログラムを書いてみるという目的が先にあり、 書くプログラムは後から探した。 フィイル操作があり、コマンドライン引数の処理があり、 多少の文字列操作があるプログラムという事で、 pdumpfsをGaucheで書く事にした。 pdumpfsをGaucheに書き換えた gdumpfs というのがすでにあって、プログラムを理解しやすだろうと考えたのもある。 Gauche が何か pdumpfs が何かについての細かい説明はしない。 GaucheはSchemeの処理系で、 pdumpfsはPlan 9のdumpfsにヒントを得たバックアッププログラム。 くわしい事はそれぞれのページを参照。 [目次」 ディレクトリの差分をコピーできるようにする ディレクトリ
... レーヴェンハイム・スコーレムの定理により、 そもそも何らかのモデルが存在するならばその加算モデルが存在する と確信できること、は確かにその通りである。 しかしそのような加算モデルが存在すると信じる直接的理由を、 我々はもたないままである。 なぜ我々がそれらの公理系の無矛盾性、充足可能性を確信するのかと言えば、 その公理系が当初記述しようとしていた非加算モデルが明瞭だ と思われるからなのである。 マイケル・ダメット「プラトニズム」 「意図されなかった」解釈 -- たとえば、非可算と「想定されていた」集合が、 そのなかでは「実際には」可算であるようなモデル -- の存在の意義について、 ある点までは論者のあいだの一致がある。 こうしたモデルの存在が示すことは 「意図された」解釈、もしくはある人々の好む表現では「集合の直観的概念」、 が形式的体系によっては「捉え」られないということだとい
訳文 Mattias Felleisen, Amr Sabry 「 Continuations in Programming Practice: Introduction and Survey 」 だいたい次のような内容。 継続とスタックの関係を述べた後、 いくつかの計算モデルで継続がどう表現されるかを説明する。 その後、色々な制御オペレータを継続を使って説明し、 call-with-current-continuationを導入し 継続を使ったプログラム例を示す。 David Ungar, Randall B. Smith 「 SELF: The Power of Simplicity 」 Joel Mose 「 The Function of FUNCTION in LISP or Why the FUNARG Problem Should be Called the Environ
参照透過性と遅延評価 純粋遅延関数型言語に入出力を導入する場合には、 参照透過性や遅延評価とどう折り合いをつけるか、 が問題になる。 参照透過性(Referential Transparency) 「参照透過性」の正確な定義は知らない。 けれど、だいたい 「等しいものを別の等しいものに置き換えられて、 置き換えての全体の結果が変わらない」 という性質を「参照透過性」と呼ぶ。 (「代入可能性の原理」とどう違うのかは、よく判らない) なんでこの性質を参照透過性と呼ぶのかも正確な所は判らないけど、 たぶん次のような事が元になっているのでは、と予想している (以下しばらく、本題(入出力の話)とは関係ない)。 クワインは「指示と様相」(「論理的観点から」に収録)で、 だいたい次のような事を書いている。 名前(とか項とか)が単に対象を指示するものとして現れている場合を 「純粋に指示的(purely r
2004-06-07-Mon 雑記: 判らない事が判らないままで、判らない事が どんどん増えていく一方のような気がする。 Scheme: syntax-rules R5RSをのsyntax-rulesの挙動がよく判らない。 伝統的なマクロの場合、マクロを定義するプログラムというのは リスト操作を行なう普通のLisp、Schemeプログラムに過ぎない。 一方、syntax-rulesの場合、 Schemeとは異なるパターンマッチング言語で書かなければならない。 パターンマッチングを使えばリスト操作をマクロで書く事はできる。 例えばbeginとは逆に後ろの式から順に実行するrbeginというマクロを考える。 この場合、 (rbegin en ・・・ e1 e0) という式を (begin e0 e1 ・・・ en) という式に変換してやるだけだから、伝統的なマクロなら (define-mac
戻る SELF: The Power of Simplicity DAVID UNGAR, RANDALL B. SMITH 原文 概要 SELFは、探求プログラミングのための オブジェクト指向言語で、 プロトタイプ、スロット、振る舞いという 少数の単純で具体的な考えに基づいている。 プロトタイプは継承とインスタンス化を一つにし、 多くのオブジェクト指向言語よりも単純で柔軟な枠組みを提供する。 スロットは、変数と手続きを単一の構造に一体化させる。 これにより継承階層を使い、 従来の言語における字句スコープ機能を採り入れられる。 そして最後に、SELFは状態と振る舞いを区別しないので、 普通のオブジェクトと手続きとクロージャとの間の相違が小さくなる。 SELFの単純さと表現力は、 オブジェクト指向計算に新たな洞察を与える。 To thine own self be true.(自己に忠実であ
人間の認識能力にあったモデル化手法としてオブジェクト指向は重要である。 この伝承は嘘ではないと思う。 しかし、デザインパターンのカタログを眺めていると、 このような考え方にはあまり従っていないように見える。 人間にとって何が自然な「もの」であるかという視点ではなく、 プログラムの修正を柔軟に行えるようにするためには、 何がオブジェクトであるべきかという視点で設計が行われている。 柴山悦哉「デザインパターン」 (bit Vol.31,No.5 1999年5月号 特集リセットセミナー) ミックスイン 例1 Personクラスというのがあって、 名前を出力するdisplayName()というメソッドを持っているとする。 そして名前を出力する時に名前の前後に「***」を付けて出力し、 それ以外の性質はPersonクラスと全く同じであるような StarPersonクラスを定義したいとする。 こういう
断片的なメモの一部 同じような内容のメモ。 あとは関係あるのかないのか判らないメモ。 読み返してみたら、ひどいなあ。 ずっと疑問に(あるいは、変に)感じる事がある。 それがここで扱いたい事で、 一言で言うと一応は次のようになる。 「なんで今が「今」なんだろう」 でも、これでは何が言いたいのか判らない。 なので何が疑問なのかをできるだけ判るように説明する、 というのが一応の目的になるはず。 (経験的には、なぜだか判る人にはほとんど説明の必要がないのに、 この疑問と全く無縁の人には誤解しか与えられないみたいだけど) 「なんで」という言い方になっているけど、 別に理由とか原因を求めているのではない (答というなら「理由はない」「とにかくそうだから」とかになるのだろう)。 1998年5月17日の日付のあるメモに、 次のように書いてある。 「今」を問題にする時、その「今」は文章が書かれた時点、 あ
The Function of FUNCTION in LISP or Why the FUNARG Problem Should be Called the Environment Problem Joel Mose 原文 概要 多くの強力なプログラミング言語に共通するある問題が、 関数の自由変数にどんな値を割り当てるかを決めなければいけない場合に 発生する。 この問題を解くための異なる実装アプローチを考察する。 議論は、LISPの実装に集中し、 なぜ現在のたいていのLISPシステムが オリジナルのLISP1.5システムほど一般的でないのかを指摘する。 可能な限りALGOL風の用語での議論を試みたので、 LISPになじみのない読者も困難なくこの文章を読めるに違いない。 多くのプログラマは、 スタックを使って再帰関数の引数と局所変数の値を管理する事を 良く知っている (訳注1)。 具体的に
不動点オペレータY 階乗関数は、 (define fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1)))))) のように、再帰的に定義できる。 再帰的定義を行なう場合はdefineやletrecを使うけど、 代わりにletを使うと再帰的定義はできない。 defineやletrecをどうしても使いたくないなら、多少工夫がいる。 例えば、factの引数を増やすという方法がある。 (let ((fact (lambda (self n) (if (= n 0) 1 (* n (self self (- n 1))))))) (fact fact 10)) ⇒ 3628800 (中略) 不動点オペレータYを使うと次のように書ける。 (let* ((Y (lambda (g) ((lambda (s) (g (lambda (x) ((s s) x))
この言語は、MITの二人の聰明な人間がしていた大きな論争にはじまります。 それは、私がMITに学生として来るちょっと前のことでした。 この論争というのは、Carl Hewittと、 新しく学生として入ったGerry Sussmanの間に起こったものです。 Guy L. Steele Jr.「Scheme 過去・現在・未来 前編」 (bit vol.28,No.4 1996 4月号) あれは玉突きだね。.....いや、というよりはキャッチボールだ 北村薫「六の宮の姫君」 Actorに基づく言語 メッセージ送信 アクターにメッセージを送る。 メッセージを受け取ったアクターは、別のアクターにメッセージを送る。 以下同様。 例えば「1と2と3からなるメッセージをアクターaに送る」という事を [a 1 2 3] と書く事にする。 アクターaはメッセージを受け取ると、別のアクターにメッセージを送る。
Schemeとか関数型言語を使う人は、ラムダ計算が好きだったりする。 実際にラムダ計算をするのは別に好きではないと思うけど。 日本にも、 ラムダ算法騎士団の 総本山 があったりする。 Schemeのlambdaでも実際のlambda計算みたいな事ができる。 ; *** car、cdr、cons *** ; car、cdr、consが、lambdaだけで書ける事は、わりと有名。 ; (car、cdr、consが書けるというのは、 ; (eq? x (car (cons x y))) ; (eq? y (cdr (cons x y))) ; が成立するという事。) ; 次のようになる。 (define _cons (lambda (x y) (lambda (z) (z x y)))) (define _car (lambda (z) (z (lambda (x y) x)))) (defin
プログラミングそのものは、あまり好きではない。 当然、実用的な内容はない。 2005年4月以降どうなるか不明。 Lispの(S式以外の)特徴(未完成) Scheme、Common Lisp、Emacs Lispの比較(未完成) 内容のわりに長い。 自己出力プログラムと自己参照プログラム 計算できない問題・関数について 停止問題とかbusy beaver関数の事など。 Schemeでラムダ計算 不動点オペレータについて 再帰的定義に使うYオペレータとかの事。 継続の説明(前置き) 継続の使用法 Schemeでの継続の使用。 SchemeとActor理論 CPS(Continuation Passing Style)について 「SchemeとActor理論」と同じ内容なので、 どうするか考え中。 CPSで多値(とか) values、call-with-valuesがあるから、 無理してS
「継続の書(Book of Continuation): 8面以降でもコンティニューできるようになる」 (「レインボーアイランド」) Schemeには継続を扱うための関数 call-with-current-continuation (別名 call/cc) がある。 でもここでは blockという(機能としては違いの無い)構文を定義して、 それを使って説明していく。 blockの定義は、 (define-syntax block (syntax-rules () ((_ name e1 e2 ...) (call-with-current-continuation (lambda (name) e1 e2 ...))))) とか、 (define-macro (block name . body) `(call-with-current-continuation (lambda (,n
継続の説明の断片 「John Reynolds "The Discoveries of Continuations" によると、 継続の概念が初めて現れるのは1964年らしい。 そして、1970、1971年頃(さらにその後も)何人もの人によって再発見されている。 Knuth は、何人もの人が独立に演算子順位文法を考えだしたのに 自分は思いつかなかったから、 「自分は、自力で演算子順位文法を思いつけなかった唯一の計算機科学者だ」 とか考えたらしい。 「自分は、自力で継続を思いつけなかった唯一の計算機科学者だ」 と考えた人もいるのだろうか。」 C言語のexit() 関数は、関数呼び出しと言うよりジャンプだ、 という事を聞くことがある。 なぜかというとexit() は関数呼び出しから戻ってこないから。 例えば、 exit(1); printf("Not reached\n"); となっている時、
「王女アテー姫を含めてハザールの男女は、 この能力によって朝ごと変身を済ませ、 そのたびに、見たこともない斬新な顔で立ち現れる。 だから近親者同士でさえ見分けがつかないほどだ。 旅行者の見聞はこれとはまったく異なり、ハザールの顔つきはどれもそっくりで、 しかも歳を重ねても容貌が変わらない。それゆえ人違いの混乱や厄介が絶えない。 どちらにせよ、結果は同じことで、ハザール族の顔はまず覚えられないし、 覚えても無益となる。」 ミロラド・パヴィチ「ハザール事典」 Lispには数限りないほどの方言がある (例えば、 http://dreamsongs.com/NewFiles/Hopl2Slides.pdf とか参照)。 そのなかで普及している Lispというと、 Scheme、Common Lisp、Emacs Lispの3つだろう。 ユーザの多さでいうと、多い順に Emacs Lisp、Comm
このページを最初にブックマークしてみませんか?
『www.ice.nuie.nagoya-u.ac.jp』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く