計算機(主にソフトウェア)の話題

(Topics about Computer (mainly Software))

by Akihiko Koga
11th Feb 2019 (Update)
14th July 2018 (First)

圏論を勉強しよう へ
束論を勉強しよう へ
半群論を勉強しよう へ
ホームページトップへ戻る

ここでは,計算機,主にソフトウェアのことについて,考えたこと,思いついたこと, 徒然思い続けていることを書くつもりです.どちらかと言えば,数学より計算機よりの話題, 例えば,アルゴリズムやプログラミング,ちょっと理論よりではプログラム変換などの お話です.たぶん,圏論や束論はあまり出ないし,出てきても主役ではないと思います.

話題

  1. 線形オーダーのハノイの塔のプログラム 2018.07.14 (土) (初出)
    ハノイの塔のプログラムは再帰関数を説明するときよく使われる例題ですが, 通常, n 枚の円盤を動かすのに 2n - 1 の手順が必要ですから, それを生成するのに O(2n)の計算量が必要です.ここでは, 結果を表示せず,データとして計算だけすることにして O(n) のオーダーで 計算を終わらせようというものです.内容を読んだら,多少,ずるいと思うかも しれませんし,これは違うと思うかもしれません.

  2. コンビネータ論理(Combinatory Logic) のお話 : λ式から SKI を使った式への変換のトレース 2018.07.20 (金) (初出)
    一か月ほど前に,とある勉強会でコンビネータ論理を勉強してきた.その予習の ために,事前にWikipedia などを見て,SKI コンビネータの式のインタープリタと λ式から SKI コンビネータの式へ変換するツールを Ruby で書いてみた. そのツールには変換のトレース機能があり,変換の過程が分かって,結構良いのではないかと思うので,それを動かしながら, λ式から SKI コンビネータの式への変換方法を解説してみた.

  3. ドメイン取得とレンタルサーバーのお話 2018.11.04 (日)初出
    このコンテンツを置いていた geocities.jp からサイトを閉鎖すると連絡が ありましたので,独自ドメイン取得とレンタルサーバーを借りることに なってしまいました.そのとき検討したことを残しておこうという内容です. 今までの少し理論っぽい話とはだいぶ趣が違いますね.

  4. 簡単な演算子順位パーサー in Ruby を作る 2019.02.11 (月)初出
    λ計算やコンビネータ論理,あるいは,それらをベースに型理論を導入したり,あるいは 圏論を利用してそれらのモデルを作ったりと,計算機科学も数学と同様に抽象的で 難しい領域があります.そんなとき,計算機屋さんの良いところは,ちょっと作って 動かしてみることではないでしょうか.Ruby や LISP なら比較的簡単に原理実験的に 動くものができます.ただし,「簡単に」というのは見た目にこだわらず,それらの 言語のリストや配列を直接人間が扱う場合です.やはり,そういうのでは数学を やっているという雰囲気が出ないので,数式や何らかの人間に優しい言語でそれらの 実験ができれば助かります.ここは,本当に簡単なパーサーを作っておいて, 計算機科学の理論の勉強に役立てようという企画です.まずは作るだけで, 使うのは今後になると思います.

  5. SKIコンビネータ AGAIN 2019.02.11 (月)初出
    上で作成した演算子順位法のパーサーを使って,SKI コンビネータのインタープリタを 作成し,遊ぼうという企画です.SKIコンビネータの話は上にもありますが, そちらでは動くものは提供しませんでした.すぐ上で,パーサーの小さなものが できたので,それを使って,それぞれが玩具程度のちいさなプログラムで遊べるようになりました, こちらは動かして遊ぶということがメインなので,コンビネータの説明は 上の「コンビネータ論理(Combinatory Logic) のお話 : λ式から SKI を使った式への変換のトレース」の方をあわせて読んでいただくと良いと思います.


圏論を勉強しよう へ
束論を勉強しよう へ
半群論を勉強しよう へ
ホームページトップ(Top of My Homepage)