2015-01-27

Land of Lisp 4章メモ

4章メモ

真偽値

Common Lispでは空リストを偽、それ以外を真として扱う。また、空のフォームが空リストに評価され、nilは値nilをもつ定数で、値nilは空リストに等しいため、'() () 'nil nilはすべて空リストとなり偽。

条件分岐

if,when,unless, cond,caseがある。

ifは普通の条件分岐、whenは真、unlessは偽のときに式を実行する。 condは判定式を一つ目の要素に持つリストが1つの分岐にあたり、caseは各分岐でeqlで比較をするcondに等しい。

and/or

ショートサーキットされるのを利用して条件分岐に使う技法。個人的にはそこで副作用起こしてほしくない。

真偽値以上のもの

真偽値が空リストか否かであるので、真を返す時に情報を持たすことができる。ただfind-ifの例にあるようにこれだと結果として空リストを返したのか、偽を返したのかわからなくなる事があり得るので要注意。

正直、真偽値が個別にあるSchemeの設計の方が好み。

比較関数

Lispには比較関数がいろいろある。 eqとequalはC#の==とEqualsみたいなノリ(オブジェクトとしての等価と値としての等価)。

あとはわりとどうでもいいっぽい。

ところで

この章で何度も"対称性"という言葉がでるけどなにをさして"対称性"と言っているのだろうか。

2015-01-27

Land of Lisp 3章メモ

3章メモ

Lispのシンタックス

LispをLispたらしめるっぽいとこ。 Lispのコードは全部リスト。

クオート

Lispのコードは第一要素を関数名として評価される。(特殊形式除く) 評価を抑制するときはクオートする。

リストとコンスセル

リスト(a b c)はnilで終わるコンスセルの入れ子(a . (b . (c . nil))。 nilは()とおなじ。

cons

consでコンスセルを作る。

> (equal (cons 'a 'b) '(a . b))
T

list

listでリストを作る。

> (equal (list 'a 'b 'c) '(a b c))
T

car/cdr

(cadr x) = (car (cdr x))　の順。

2015-01-27

Land of Lisp 2章メモ

2章メモ

Land of Lisp 2章を読んでのメモ。

defparameter/defvar

グローバル変数定義。 defparameterだと同名の変数を定義した時に上書きされる。 defvarだとされない。

defun

deffunではない。

ash

arithmetic shift(算術シフト)の略。

lsh(logical shift)があるのかと思ったらなかった。 Emacs Lispにはあるらしいけど。

setf

set fieldの略らしい。変数の場所を返す式を突っ込んで評価後にそこに代入みたいなことをできるとか。

あとsetとかsetqがあって、setが基本でsetq(set quote)は変数名がくる(事が多い)第一引数のとこがクオートされるとか。

let/flet/labels

let,fletはわかるけどlabelsってどういう命名なの。。。

Source

(defvar *big* 100)

(defvar *small* 1)

(defun guess-my-number ()
  (ash (+ *big* *small*) -1))

(defun smaller ()
  (setf *big* (1- (guess-my-number)))
  (guess-my-number))

(defun bigger ()
  (setf *small* (1+ (guess-my-number)))
  (guess-my-number))

(defun start-over ()
  (setf *big* 100)
  (setf *small* 1)
  (guess-my-number))

2014-12-21

SML#のためにlib32gmp-devを入れる

SML# 2.0.0をLinuxMint17.1に入れようとしたけれど、 SML#はlib32gmp-devというパッケージに依存しており、lib32gmp-devは公式にはUbuntu12.04(Precise)=LinuxMint13までしかない。そのため、そのままではパッケージが足りずインストール出来ない。

そこでlib32gmp-devを入れる(ついでにgmpは最新の(6.0.0a)で)ためにやったことをメモがてら書いておく。 Ubuntu12.04でやれば簡単なんだけど、どうせなら新しいので動かしたいしね？当然これで必ずうまく行く保証はないし、やってみてどうなってもいかなる責任も負いません。

やった環境

環境は LinuxMint17.1 64bit (ベースはUbuntu14.04)
基本的にクリーンインストールの状態

当然Ubuntuでも同じ手順で大丈夫のはず

手順

Preciseのlib32gmp-devのソースパッケージを入手
最新のgmpのソースファイルを入手
debパッケージ用のファイルをソースパッケージから拝借
ソースパッケージ内の設定ファイルを修正
バイナリパッケージをビルド
インストール

1. ソースパッケージを入手

Ubuntu – Details of package lib32gmp-dev in precise

の右にある

gmp ソースパッケージをダウンロード:

以下の3つのファイル(.dsc、.orig.tar.gz、.diff.gz)を同じフォルダにDL

次に

$ dpkg-source -x gmp_5.0.2+dfsg-2ubuntu1.dsc

してソースパッケージを得る。

2. 最新のgmpのソースファイルを入手

1.のソースパッケージを作ったのとは別の場所に

https://gmplib.org/download/gmp/gmp-6.0.0a.tar.lz

からソースファイルをDL

次に

$ lzip -d gmp-6.0.0a.tar.lz
$ tar xf gmp-6.0.0a.tar

して解凍する。

3. ファイルをソースパッケージから拝借

ソースパッケージ内のdebianフォルダをソースファイルのフォルダ(gmp-6.0.0)内にコピーする。

4. 設定ファイルを修正

debianフォルダ内のいくつかのファイルを修正する。

まずrulesファイル3行目のバージョンを

ORIG_SRC_VERSION = 6.0.0

と修正。

またchangelogファイルの先頭に適当に追加する。下のようにしたけど、適当すぎる(というかなにが必要でなにが不要かよくわからない(まぁ自分でインストールするだけだしいいよね()))

gmp (2:6.0.0-1) unstable;urgency=low

* Update

-- koropicot <hoge@example.com>  Sat, 20 Dec 2014 17:10:29 +0900

あとpatchesフォルダを削除する

5. バイナリパッケージをビルド

ソースファイルのフォルダ(gmp-6.0.0)内で

debuild -uc -us -b

としてパッケージをビルドする。 debuildはdevscriptsパッケージに含まれる。

ビルド中にエラーが出たときはエラーメッセージから足りなそうなパッケージ追加したりする。

gcc-multilib g++-multilib build-essential quilt debhelper

とかが必要だった気がする。

6. インストール

うまくいくとソースファイルのフォルダと同じ階層に.debファイルが幾つかできているので、そこで

$ apt-ftparchive packages . | gzip -c9 > Packages.gz
$ apt-ftparchive sources . | gzip -c9 > Sources.gz

する。

次にリポジトリとして

deb file:<Packages.gzとかがあるフォルダ> ./

を追加する。 Synaptic パッケージマネージャの設定→リポジトリ→追加リポジトリ→新しいリポジトリを追加からやった。

リポジトリを変更したので

$ sudo apt-get update

そして…

$ sudo apt-get install lib32gmp-dev

するとlib32gmp-devがインストールできる。

その後

SML#のHPからUbuntu用64bitパッケージをDLしてインストールできた。そしてREPLも動いたので当初の目的達成。

動作かくにん! よかった。

参考サイト

2013-09-08

C#で部分適用

(話とかどうでもいいからソースみたい人は→Gist)

C#で部分適用をしようと思ったら、普通は

_1 => _2 => foo("hoge", _1, _2)

のようにラムダ式を書かなければなりません。
しかし、これが例えばScalaだと

foo("hoge", _, _)

と、適用しない(引数になる)ところに_を置くことで部分適用された関数を作ることが出来ます。

はい。うらやましいですよね。妬ましいですよね。

これをC#でどうにかやってやろうじゃないのって思いますよね。では、やりましょう。

方法

まず今やりたいことは、Func<>を拡張したいということなので、拡張メソッドを使うことはすぐ決まります。

そして、部分適用をする上で最低限必要な情報はどこが適用されないかです。
なので単純な方法として、適用しないところにそれを表す値を渡すことが考えられます。例えば、Option<T>型のようなものを取るようにして、Noneが来たところは_にあたるみたいな感じで行けそうに思えます。
しかし、これには問題が有ります。

部分適用した関数の型は、適用しなかった部分の型を取る関数になります。
例えば最初にあげたfoo関数がFunc<string,int,double>型ならば、 foo("hoge", _, _)はFunc<int,double>型になるわけです。しかし今考えた値レベルで適用しない部分を指定する方法では、型をつけることが出来なくなってしまいます。(~~依存型でもあれば別だが~~)

つまり、素直に部分適用後の関数に適切に型を付けるためには、適用しない部分が型レベルにわかる必要がありそうです。これはオーバーロードでどうにか出来そうに思えます。例えば、適用しない部分をPlaceholder型として2引数関数を対象とすると、

public static Func<T1,TResult> PartialApply<T1,T2,TResult>(
  this Func<T1,T2,TResult> func, Placeholder p, T2 v2)
{
  return _ => func(_,v2);
}

public static Func<T2,TResult> PartialApply<T1,T2,TResult>(
  this Func<T1,T2,TResult> func, T1 v1, Placeholder p)
{
  return _ => func(v1,_);
}

public static Func<T1,T2,TResult> PartialApply<T1,T2,TResult>(
  this Func<T1,T2,TResult> func, Placeholder p, Placeholder p)
{
  return (_1,_2) => func(_1,_2);
}

みたいな感じでしょうか。手書きは辛いでしょうがそこはT4にでも頼めば何とかなりそうです。

でもなんか嫌な予感がします。これが3引数になったらどうなるでしょうか。各引数で適用する/しないで2通りあるので、全引数に適用する場合を除いたとして2³-1 = 7通り。
もう少し行きましょう。4引数、2⁴-1 = 15通り。5引数、2⁵-1 = 31通り。…8引数、2⁸-1 = 255通り。…
はい、もうお分かりの通り引数のパターンは指数的に増加していきます。255通りならまだ何とかなりそうですが、Func<>型は16引数まで標準であるのでそこまで対応しようとすると、2¹⁶-1 =65535通りにもなり、とてもやばいです。

というわけで、この方法ではどうにもうまくいきそうもないです。さてどうしましょう。 これが第1引数だけ考えればいいのであれば楽なのですが… 第1引数のみ…多引数関数が第1引数…
(´・◞◟・)なんかカリー化したらうまくいきそうじゃね？

はい、なんかそんな気がしたのでカリー化した状態で今一度部分適用を考えてみます。

まずは2引数の場合
2引数関数をカリー化するとFunc<T1,Func<T2,TResult>>のようになります。ここで普通に第1引数を適用したいなら、func(v1)のようにすればいいですね。そして、第1引数を適用しないなら、次に第2引数を与えると、部分適用された関数、つまり第1引数の型を取る関数になってくれればいいので、この関数を拡張メソッドで_として定義すると…

public static Func<T1,Func<T_,TResult>> _<T_,T1,TResult>(
    this Func<T_,Func<T1,TResult>> func)
{
    return v1 => _ => func(_)(v1);
}

ですね。(上のコードではT1がT_、T2がT1になってます)
さらに3引数では…

public static Func<T1,Func<T2, Func<T_, TResult>>> _<T_, T1, T2, TResult>(
    this Func<T_, Func<T1,Func<T2, TResult>>> func)
{
    return v1 => v2 => _ => func(_)(v1)(v2);
}

です。
これは結局のところ、カリー化してあれば、適用しない場合は第1引数を一番後ろに回せばいいということです。この場合だと、各引数の数に対して、必要なメソッドはたった1つです!
組み合わせ爆発を克服出来ました!

これを使うためにはカリー化しなければならず、部分適用した後もカリー化された状態になってるので、他の関数と同じように扱うにはアンカリー化する必要がありますが、カリー化/アンカリー化も各引数の数に対して1つで済みます! やった!

また、見た目も

foo.Curry()("hoge")._()._().Uncurry()

のような感じになり、ギリ分かるレベルでしょう。

最後に、この方針で、軽く実装してみました。
ソースコードがGistにあります。
また実行した結果をIdeoneにあげておきました。

手動で書いたので4引数までしかないですが、後でT4で16引数まで伸ばす予定です。

2013-06-28

私がモナドをもふもふする過程でつまずいたこと

ここ数日モナド解説が流行ってるらしいので解説してみようと思ったけれど、解説できるほどモナドを理解していなかったので、私がつまずいた事をだらだらと。

モナドは特定の言語の概念ではない

モナドといえばHaskell、Haskellといえばモナドみたいなイメージを持ちがちだけど、モナドはHaskellだけのための何かではない。また、純粋関数型言語だけの概念でもない。

IOだけがモナドではない

簡単なはずの文字出力を、Haskellでしようとするといきなり現れて、多くの人にとって初モナドとなる事が多いと思われるIOモナド。でも、別にこれだけがモナドでは無い。

モナドと副作用は関係ない

関係ない、は言い過ぎかもしれないけれど、副作用の無い操作でもモナドは有用だし、副作用をごく普通に使う言語(C#とか！)でもモナドは有用。

モナドはインターフェイス

モナドは取り扱いを定めてるだけで、その意味や動作は個々のモナド(のインスタンス)により様々。

モナドで包んだ値を取り出したっていい

モナドのインターフェイスにはモナドで包まれた値をそのまま取り出す操作が無いために、副作用などを参照透明に実現できる。でもそれだけがモナドの価値ではない。たとえばHaskellのMaybeなどは、パターンマッチで容易に中の値を取り出せる。

2013-05-30

なんかできたものと、バリアントについて色々

bleisさんのLangExtでのOptionの設計 - ぐるぐる～を読んだ後気づいたら何かよくわからないものが出来上がっていたので、その紹介とかです。

GenericVariant

今回できたものはこちら(GitHub) GenericVariant

Genericじゃない気もするしよくわからない名前ですが、要は無名のバリアントが作れたりするものです。 (名前と実体の相違が甚だしいですが一応ジェネリックス使ってるので許して下さい)

var foo = new[]{
    Variant<int,string>.C1(4),
    Variant<int,string>.C2("foo")};
foo
    .ForEach(either => either
        .Match(
            C1: i => i.ToString(),
            C2: s => s)
        .Act(Console.WriteLine));

みたいな感じで使えます。(ForEachとActは今回のとは関係ないので適当に察してください)

実用的ななにかではないので、へー面白いと思って貰えたらそれだけでいいです。

以下戯言が続くので、どんな感じかもうちょっと見たい人は上のリポジトリのUsageを適当に見ると良いと思います。

バリアントとは何か

例えばF#やLangExtで言うOption[T]型はだいたい

Option[T] = None:Opiton[T] | Some:T->Option[T]

のような型ですが、ここに出てくる型名やラベルを除けば、
#がその型そのものを表すとすれば

# | T->#

と言ったかたちになります。
これはHaskellのMaybeのような同じだけど名前の違うものまで含んだ表現です。
ここでNoneにあたるとこが関数じゃないのがちょっと気になるので#をUnit->#と見ると

Unit-># | T->#

となります。

また、List[T]も上記記法で書くと

Unit-># | (T,#)->#

となります。

以上のように、バリアント型は、ある型からバリアントそれ自体への関数、すなわちコンストラクタの集まりによって定義されます。つまりバリアントのアイデンティティを決めるのは結局コンストラクタがとる型は何かということになります。

GenericVariantにおいては

そこで、例えばOption[T]にあたる型はVariant<Unit,T>として作れるようにしようと思って作ったのがGenericVariantということになります。

しかしこれではラベルも型名も扱いづらいため、UsageではVariant<Unit,T>に委譲する形で名前をつけOption[T]を書いています。またUsageでやっているようにList[T]のように再帰型(#がコンストラクタの引数の型に含まれる型)だと、 Variant<Unit,Tuple<T,ここどうするの>>となるので名前を付けないと書けません。

バリアントとレコード

バリアントと対をなすものとしてレコードがあります。レコードはバリアントのコンストラクタと対をなすように、レコード型から値を取り出す関数で定義されます。

そしてレコードの値としての実体は、各取り出し関数に対応した値の集まりです。

バリアントの値としての実体

通常バリアントの値は、コンストラクタに対応したラベル付きの値を持つものとして理解されます。しかし、先ほどのレコードとの双対性を考えると、

レコード
- 型:値を取り出す関数の集まり
- 値:ラベルに対応した値の集まり
バリアント
- 型:値を作る関数(取り出し関数と対をなす)の集まり
- 値:ラベルに対応した「値と対を成す何か」の集まり

とするのが綺麗です。ここで「値と対を成す何か」とは、何なんだって感じですが、これは要は継続です。 つまりバリアントは継続のレコードです。

でも、継続は普通の言語ではCPS変換(全域に渡る)しないとうまく扱えません。そこで、限定的に何とかしようとすると、値を取り出し同じ型で返すようにして、その後は普通の値として扱えるようにする事になります。

これはまさにパターンマッチです。 最初のbleisさんの記事で

探した限りはあまり他で同じようなことをやっているライブラリがなかったのですが、 LangExtは(F#のような)match式をある程度模倣するMatchメソッドを提供しています。

と最後の方にちょっと出てくるMatchメソッドこそが、バリアントの実体だったのです！！！！

結局

C#などでバリアントを作る場合、型はコンストラクタを提供し、値はコンストラクタに対応したMatch式(メソッド)を実装するのが、綺麗だと思います。

というわけで、アイデンティティとなる型を与えると、コンストラクタができて、それで作った値にはMatchがある、というものを作ってみたらできたのがGenericVariantです。

ただしこれはあくまで、綺麗だと思うかどうかの話であって、綺麗だから実用的だというわけではないので注意が必要です。
例えばこのままだと、あるOption型の値がSomeだとわかっていたとしても、そこから値を取り出すにはMatchを通すしかありません。。。

また、これは先の記事の話題にあった実装の中身を継承で実現するのか、ラベルを持って実装するのかには関係ありません。
今回のGenericVariantでは、SomeやNoneはコンストラクタであって型ではない、またC#ではScalaのsealdにあたるものがないので、勝手に継承されるのを防げないために、継承ではなくラベルを持つ形で実装していますが、
以前作ったOption、Eitherでは継承を使って、Matchメソッドを持つ型であるとしていました。

それと

GenericVariantを作るにあたって、型の数が異なるVariantを作らなければならなかったのでT4を使ってみました。

あっころくんが踏み込んじゃいけないところに・・・
— ぶれいす(よんた)さん (@bleis) 2013年5月30日

ああ、ころくんが魔道に
— でこ式さん (@dico_leque) 2013年5月30日

とか言われてしまいましたが、これくらいなら許される…よね？