OCamlのモジュールとCommon LispのCLOSの比較

はじめに

OCamlのモジュールシステムとCommon LispのCLOSは、どちらもプログラムを構造化し、再利用性を高めるための強力な仕組みです。しかし、そのアプローチは大きく異なります。今回は、図形を描画するという同じ具体例を使って、それぞれの違いを見ていこうと思います。

Common Lisp のマクロを学ぶ

基本となる記号

Common Lisp(私が使用しているのはSBCL)では、老眼に優しくないクオートとバッククオートがそれぞれ違う機能として使われています。（これらはリーダーマクロもしくはリードマクロと呼ばれているもので、実はこれ自体を変更するset-macro-characterやset-dispatch-macro-charaterなんていう関数も存在しますが、今回は触れません）

マクロを定義する時、このThe ROUGANに優しくないクオートとバッククオートを使います。

シンプルにSBCLのみのCommon Lisp環境を作るためのメモ

ASDFの設定

SBCLインストール後、sbclコマンドでREPLを起動し、以下のようにASDFのバージョンを確認します。この際、rlwrapをインストールしておくと使いやすくなります。

* (require 'asdf)
* (asdf:asdf-version)
"3.3.1"

リストを2つのグループに分ける関数を作る

partition

OCamlのListモジュールにはpartitionという便利な関数がありまして、これを使うとクイックソートが簡単に書くことができます。

let rec qsort = function
  | [] -> []
  | h :: t ->
    let (l, r) = List.partition (fun x -> x < h) t in
    (qsort l)@[h]@(qsort r)

こりゃ便利！と思い、他の言語でも使いたい！ということで自前で書くことにしました。

ようやくL99問題が残り1/3になった

意外な効果

「OCamlのL99問題をCommon Lispで書いてみる」ことで、OCamlとCommon Lispを同時に勉強するという無謀な方法をしばらく地道に続けている私ですが、素人発想ながら、意外と効果があるのではないかと最近思っています。

やっとできたCommon LispでOCaml L99-50 Huffman code

Huffman code自体は難しくない

Huffman codeについてはWikipediaの解説が分かりやすいので、ここでは割愛しますが、紙と鉛筆を使ってハフマン木を書いてみるとわかりやすいように思います。

さて、プログラムの話になりますが、今回はOCamlにあってCommon Lispに無いものでいろいろ悩みました。

OCamlでは値を持てる列挙型みたいなヴァリアント型というものがあります。これは再帰にすることもできます。Rustのenumと似ています。しかし、Common Lispで同様のことを行うのはなかなか難しかったです。Common Lispにも列挙型的なものはあるようで、以下のような形で定義するようです。

オイラーのトーシェント関数

L99-33、34

オイラーのトーシェント関数とは「正の整数nに対して、nと互いに素である1以上n以下の自然数の個数φ(n)を与える数論的関数φである!」……え?　数論的関数??　

ちょっと何言ってるか分からない。

「自然数」「互いに素(タガイニソ)」はなんか聞いたことがあるようなないような気が……

ここでL99-33の単純な問題の意味を悟る。

「aとbが互いに素」とは、aとbを共に割り切る正の整数が1のみである。つまり、aとbの最大公約数が1であるということ。「互いに素」は英語でcoprimeという……、ふむ。そうL99-33の問題は単純な問題ではなく、「互いに素」かどうかと判定する関数でありました。

ユークリッドの互除法

L99-32問目

OCamlのL99問題の32問目は2つの正の整数の最大公約数(the greatest commom divisor)を求めよ、という問題。これは私自身、過去にやったことがあるので、できる気がします(記憶が確かなら)

ユークリッドの互除法は例えば a = 10 b = 8 とした時、以下のような流れで計算していきます。

1. a(10) / b(8) = 1 余り(r) 2
2. b(8) / r(2) = 4 余り(r) 0
3. 余り(r)が0になった時の除数、つまり2が最大公約数

といった流れで求めることができます。

え、エラトステネスの篩ですか？

素数とは

素数とは１より大きい自然数で、正の約数が１とそれ自身のみという数字のことで、私は学校での知識としての素数より、映画「博士の愛した数式」で寺尾聰さん演じる博士がもっとも愛した数字としての印象が強いです。この映画では素数の他にも「完全数」「友愛数」なども出てきます。この映画で、数学に興味を持った方は意外と多いのではないでしょうか。

今回はその博士に最も愛された素数についての問題をやってみます。これはこのところずっと勉強しているOCamlのL99の31問目が素数の問題だからですが、実は素数判定にはやり方が色々あるようで、OCamlのL99-31のドキュメントには「より賢い解決法として「エラトステネスの篩(ふるい)」というものがあるから調べてみて」と書かれています。

再帰の処理を追うのがすこぶる苦手

OCamlのL99-27でピタッと止まる

しばらく記事の更新が遅れてしまってました。実はここのところOCamlのL99問題の答えを読みながら、それをCommon Lispで書いてみるということをずっとやっていました。

なぜこのようなやり方をしているのかと言いますと、そもそも私はOCamlにはまだ慣れていないし、Common Lispも初心者という状態です。しかし、年齢的にも生活的にも時間が限られている。したがって、少しばかり理解しているOCamlのコードを読むことでより一層OCamlに慣れ、さらにCommon Lispで書くことによって、Common Lispにも慣れていく、という方法を思いつきました。そもそもL99問題の解答は、プロの方がベストなものを提供してくれているわけですから、よい見本にもなるのではないか、と思います。

Common Lispでrangeを作ってみる

あえて作る

Common Lispでrangeをわざわざ作る必要は「ない」のですが、勉強になるかと思い、作ってみました。
まずは普通に作ってみます。

(defun range-normal (start end &optional (step 1))
  (if (> start end)
      '()
      (cons start (range-normal (+ start step) end step))))

これを使って、1から1000までをstepを3でリストを作ってみます。

これからCommon Lispに入門する人たちへ

インストール

私が最初に躓いたのが、このインストールであります。大抵の言語はバージョンが違う程度でインストール方法はだいたい決まっています。しかしCommon Lispの場合、種類がありすぎてわからないのであります。SBCL(Steel Bank Common Lisp)、 CMU Common Lisp、GNU Common Lisp、 CCL(Clozure Common Lisp)、 商用ではAllegro Common Lisp、 Lispworksなどいろいろあります。これが、「よし！Lisp勉強してみよう！」という意気込みをいきなりサゲてくるのであります。なんとも初心者泣かせの言語であります。

Rustでcar/cdr

Rustでcar/cdr的なもの

Rustでcar/cdr的なものは無いか？

fn main() {
    let v = vec![1, 2, 3, 4, 5];
    let (hd, tl) = v.split_first().unwrap();
    assert_eq!(hd, &1);
    assert_eq!(tl, &[2, 3, 4, 5]);
}

split_firstは、Option<(&T, &[T])>を返します。これを利用すればcar/cdr関数と同じように処理できます。split_first_mutというものもあり、こちらはミュータブルな参照を返します。car/cdrという名前で使いたい場合は以下のような関数を作成すればいいかと思います。

LispのL-99 その2

前回の続きP04から

P04は「要素の数を返すnumber-of-elements関数を作る」という問題。
「むむむ...lengthじゃだめですか...」
ということで以下のようなものになりました。

LispのL-99

L-99

L-99とは99問あるLispの問題集のようなものらしく、私のようなビギナーには良いかもしれないと思いチャレンジしてみました。L-99のURLはこちら
P01は「リストの最後の要素を返すmy-lastという関数を作る」という問題。
「むむ…lastという関数を使えばすぐに結果が得られるような…でも問題の意図は違うところにありそうな…」

色んなLispエイリアンたち

不思議なキャラクター

オライリージャパンから出版されている書籍は、デッサンのような動物たちが表紙のものが多いのですが、その中で、一際異彩を放っている「Land of Lisp」の表紙。
なぜエイリアン？
不思議とこのイラストは、みるたびに愛着が湧いてくる。

Common LispでSQLite3

cl-dbi

ちょっとずつ進めているCommon Lispの勉強ですが、時々欲していたデータベース、特にPythonで気軽に使えていたSQLite3をCommon Lispでも使いたいという思いがあり、色々調べていたところ、著名なLisperの深町さんが作成なさったcl-dbiというライブラリを発見しました。早速使わせていただこうということで、ソースコードを眺める。

Common Lispのcond

Pythonにはないcond文

Rustをしばらく使い、たまにPythonを触る時、パターンマッチングのための何かが欲しくなることがあります。Pythonでもif文で似たようなことはできますが、何となくすっきり感がありません。