ここ最近

ここ最近なにしているか

ご飯食べてます。
本読んでます。
寝てます。
ウェブ小説読んでだらけてます。
時々勉強します。
ブログのタイトル変えました。

今日（というか昨日）はK-trivialityというものを知って、いろいろ調べたりしていた。確率論と情報理論と計算論のつながりは面白いなあとかケタケタ笑ってました。イマイチどこで分野が区切れてどのタームがどこで通じないのかわかっていないので、なんとかしないといろいろ不便だと思いました。

同型への憧憬

　例えば私は高校生のころに読んだ本で、生物とプログラミング言語Lispの自己記述性、自己参照性の類似性、よりかっこつけて言えば同型であることについて非常に感動を覚え、興奮したのを覚えています。これは、単なる帰納に対して演繹がきちんと訓練されていない状態、演繹の元となる知識が少ない状態ではすこぶる難しいということが原因であったのかもしれません。あるいはそうであっても、私はそれに感動を覚えたというのは事実です。見たことのない、まるで宇宙人のような、あるいは転校生のような新たな類似性、同型の指摘はぞくぞくとするものです。
　プログラミング言語Lispの特徴を一言で表すのならば、プログラムを書き換えるプログラムとでもいいましょうか。プログラムを書き換えるプログラムが存在するということは、プログラムとプログラムが処理する対象の間に壁はなく、プログラムを処理するプログラムとプログラムとの間にも、プログラムを処理するプログラムを処理するプログラムとプログラムの間にもありません。Lispにとってメタであることは、自然なことなのです。そして、これは私達にとっても自然なことではないでしょうか。何かの課題、例えばスポーツである条件を満たすことを求められるとします。この時、私たちはどのようにこれに応えるでしょうか。まずその条件をみたすことができるかを考え、できないなら訓練をするように考える。自分を書き換えるという行為は普遍的であり、書き換えるという意思を、訓練しようとする意思を持つことは訓練を要するものではありません。では、私たちはどのようにして、この能力を得たのでしょうか？
　自らを書き換えるという行為、これは私たちの体それ自体が、ある大きな系、システムの中の構成要素であるということから可能になります。大気、温度、音、光、話し声、思考、体性感覚といったありとあらゆる「環境」と「人間」は相互作用をしています。ここで、どこからどこまでが環境かあるいは人間であるかはまったくもって問題ではありません。重要なのは環境というのはそれ自体が流動する系であり、その中に人間という境界が不定形な入れ物が漂っているということだけです。人間は、人間の意思によって環境と相互作用を行い、自らを変化させます。環境はただ変化するだけです。ですが、その環境は変化するだけで内側に意思を内包し、人間の自己書き換えを実現してしまいます。
　環境は物理的な背景によって裏打ちされています。これに対し、プログラミング言語は物理的な背景にもう一段、計算機的な層を持っています。物理が情報処理だという考えも入れてしまえばこの２つの層は同じではありますが、それはさておき、プログラミング言語では言語処理系という環境とプログラムという人間が相互作用を行います。ここでも、環境と人間の境は不安定です。プログラムはどちらでしょうか？　データはどうか、あるいは言語処理系といってもライブラリはどうだ、のように。
　このような同型について、これを知ったからといって、何が変わるのかという向きもあるでしょう。それは想像力の欠如というものでしょう。私は想像というよりも妄想して楽しめます。より発展的なことは「GEB」を読むことによって得られるでしょう。

最中などいかかでしょうか？ 略してMonads

（このエントリはLisp Advent Calendar ９日目の記事です）
Lisp好きで関数型にちょっと興味があり、ちょうど面白そうなチュートリアルを見つけたので、紹介します。

Monads for Schemersというものです。これは関数型の文脈でよく言及されるMonadsについて、Schemeを使い説明していくもので、「なんかHakellとか面白そうだぞ」と思っていた（Lisp advent calendarなのに……！）私にぴったりでした。これの内容をかいつまんで説明します。

副作用はありません

副作用のないSchemeのサブセット（Curry化されている）"Pure Lisp"において次のプログラムを処理することを考えてみましょう。

(define (begin v1 v2) v2)
(begin (turn-on-safety!)
       (pull-trigger!))

ここで気をつけないと行けないのは副作用のない"Pure Lisp"では引数の評価順序に規則がないことです。もしも、引数の評価順序によって例えば今の"begin"の値が変わってしまったとすると、それは副作用があるということで、前提と矛盾します。ですので、引数の評価順序に規則はありません。右からやっても、左からやっても、左右に振動しながらでも構わないはずです。なので、

   (begin (turn-on-safety!)
           (pull-trigger!))
 -> (begin (turn-on-safety!)  ; effect: pull-trigger!
           #<void>)
 -> (begin #<void>            ; effect: turn-on-safety!
           #<void>)
 -> #<void>

というように評価されても構いません。この場合、銃の引き金を引いてからセイフティを外すことになります。

ピュアじゃないとイケナイ世界

この文章内でMonadsを導入する理由を文の後半から引用すると、
1. 評価順序を規定すること。(enforcing evaluation order)
2. アキュムレータを抽象化すること。(abstracting away accumulators)
と書かれています。
途中の説明において、評価順序を規定するのには継続渡しスタイルを、アキュムレータを抽象化するのにはアキュムレータ渡しスタイルが用いられています。
継続渡しスタイルに関しては多くの方が聞いたことくらいはあると思います。わかりやすく短い解説(ただし英語)がありますので(The 90 minutes Scheme to C compiler)こちらを参照してください。
あるいは、ググればたくさんチュートリアルがあるので、頑張ってください。

最後の方に書かれている"pipe"(>>=, *, let)と"lift"(unit, return)を使った、"monadic rand in Lisp"を見てみましょう。乱数生成のためのseedから、生成された乱数とそれをseedとして持ったconsを返すことが目的です。

(define (rand)
  (pipe (get-seed)
        (lambda (seed)
         (let ([ans (modulo (* seed 16807) 2147483647)])
            (begin (set-seed ans)
                   (lift ans))))))

これを、Haskellで書くとこんな感じでしょうか。State Monadがすでに抽象化されている分短いですね（きちんと書けてないけど……）。

import Control.Monad.State
rand :: State Int Int
rand = state $ \x -> (( x * 16807 ) `mod` 2174, (x* 16807) `mod` 2147483647)

何がどうなってこういうコードになるかはさておき、実際にgaucheで動かしてみましょう。他にも"lift"や"set-seed"関数などを本文から拾ってくる必要があります。あと、Curry化されていないことにも気をつけて下さい。

gosh> (define (runState m) (m (date-nanosecond (current-date))))
runState
gosh> (runState (rand))
(799718464 . 799718464)
gosh> (runState (rand))
(765944281 . 765944281)

seedを受け取って、乱数と乱数生成のためのseedのconsが返って来ました。同様にHaskellでも、

*Main> runState (do{rand}) 1652
(1010, 1010)

となります。

おわりに

Lispあんまり関係ないじゃないか（#^ω^）ﾋﾟｷﾋﾟｷという向きもあると思います、というか書いてて思いました。
けど、Lisp、特にSchemeとかだと継続の話題が多いので、こういうのもあるんだなーという感じで面白いと思います。
何に使えるかどうかですか？　……なんでしょうね？ :-)

Clack-web application environment for common lisp

同じように詰まる人がいないとも限らないのでメモ。
clackを使おうとして、私みたいなこと

になった場合の対処法。
clack_documentにあるような"Hello world" プログラムについては、

(defun app (env)
  (declare (ignore env))
  '(200
    (:content-type "text/plain")
    ("Hello, World!"))
    :port 8080)

と変更するとうまくいく。

@nitro_idiotさんに教えて頂きました。大変助かりました。感謝します。
後にclackは:port 5000を指定するとdocumentにも書いてあるのを発見しました。

Grass interpreter

を作っています。
Grass-ちょっと草植えときますね型言語(参考link[2])というのは、lambda計算を素にした(らしいし、それっぽい)言語で、brainfuckの類、つまり難解言語の１つです。それっぽいというのも、公式にあるlambda計算からGrassへの変換がまったく理解できていないからです。CPS変換ってなんぞ。(ShibuyaLispでも聞いたけど分からなかった)

で、それをcommon lispで実装しようとしている、というわけです。

環境:
Windows7 home premium
lisp box (GNU Emacs + Clozure common lisp + SLIME)

といっても今のところできているのは関数適用と値を返すところだけで、関数定義とかはこれからです。眠いので、寝てから作ります。以前から頑張って作ろうとはしていたのですが、なんともやるきがたらず全くできていませんでした。[1]は非常に役に立ちました。
将来的にはCで実装とかやってみたいですね。

あとでGithubにあげる、はずです。
https://github.com/fetasteinのどこかにGrassのレポジトリを作る予定です。
ああ、悲しきかな過去の遺産共よ。君たちは忘れない。(コミットの履歴とか)

課題:
関数定義
churchian true and false(おそらく分岐の実現に必要)

というわけで、ブログ書きこみ終了のポーズ!　λ(ｷｬﾋﾟｯ☆彡)

参考:
[1]http://d.hatena.ne.jp/higepon/20080605/1212678422: MoshによるGrassインタプリタ実装
[2]http://www.blue.sky.or.jp/grass/doc_ja.html:　Grass公式ページ
[3]プログラミング言語を作る 前橋 和弥 (著) 出版社: 技術評論社
[4]プログラミング言語scheme R.ケント.デイヴィグ (著)　出版社: ピアソンエデュケーション

Project_Euler

をやっています。
主にC言語でやっていきますが、時々schemeだったり、common lisp だったりするかも。
そして、非常に大学の初年度のプログラミング演習の匂いのするコードです。
基本的にCの反復練習のためにやっています。

問題1は、
"1000より小さいの3と5の倍数をすべて足しあわせよ"

/*Project Euler:problem1*/
#include<stdio.h>

int main(){
  
  int product, i;
  product = 0;
  for(i=0; i< 1000; i++){
    if(i % 5 ==0 || i % 3 == 0) product += i;
  }
  printf("%d", product);
  return 0;
}

問題2
"40000より小さいフィボナッチ数列の値のうち、偶数の値をすべて足しあわせよ。ただしF(0) = 1, Fib(1) = 2とする"

/*Project Euler:problem2*/
#include<stdio.h>

int main(){
  int table[65536];
  table[0] = 1;
  table[1] = 2;
  int i, j, product;
  product = 0;
  for(i=2; table[i-1] < 40000; i++){
    table[i] = table[i-1] + table[i-2];
  }
  for(j=0; j<i; j++){
    if(table[j] % 2 == 0) product += table[j];
  }
  printf("%d\n", product);
  return 0;
}

今日は眠いのでここまで。