記録は作業の証

鉄道とコンピュータ

ゼロから作るDeep LearningをCommon Lispで書き直す(ステップ1～3)

dezero Common Lisp

はじめに

Common Lispで深層学習コンパイラを作っている人に感銘を受けたので、プログラミングの練習のためにと自分もCommon Lispで似たものを書いてみようと思い、この本を買った。

ゼロから作るDeep Learning ❸ ―フレームワーク編

ゼロから作るDeep Learning ❸ ―フレームワーク編

Amazon

本のソースコードはここで公開されている。 github.com

先駆者の方々も何人かおられるようなので、参考にする。 msyksphinz.hatenablog.com github.com

github.com

実装の方針

行列を表現するなら、PythonであればNumPy一択だが、Common Lispでは少し考える必要がある。 最初の数ステップを書き直しながら、次のライブラリを試した。

  • numcl

    • NumPyに似せたAPIが使えるというライブラリ。Lisp力が低くてうまく動かせず。

  • mgl-mat

    • BLASやCUDAを使って高速な計算ができるというライブラリ。足し算や掛け算をするためにaxpy!やgemm!を使ってみたものの、計算したい行列のほかに計算結果を格納するための行列を用意する必要があり、計算式を書くのも少し難しかったので、途中でやめてしまった。
  • Common Lisp標準の多次元配列
    • msyksphinzさんの記事ではRubyのArrayをそのまま使っていたので、Common Lispでも同じように自分で書いてみようとした。多次元配列の生成や計算の書き方で自分が詰まってしまうことがあった。
  • array-operations
    • Common Lisp標準の多次元配列を生かし、機能を拡張する関数やマクロを提供するライブラリ。直感的に使える関数やマクロが多く、特にvectorizeマクロが便利で扱いやすかった。

array-operationsが自分に合っていると感じ、自作のルーチンも使いながらプログラムを書くことに決めた。 テストフレームワークはFiveAMとroveで迷ったが、とりあえずroveを使用することにした。

ソースコード

ステップ1

github.com

オリジナルの書き方に似せるため、規約を設けることにした。

  • クラス名は<>で囲う。
    • 今後出てくるクラスとしてexpやfunctionという名前があるが、これはcl:expやcl:functionと衝突するため。
  • インスタンスを作るラッパー関数を用意し、クラス名と同じ名前を付ける。
    • make-instance関数を何度も呼ぶのは少し面倒だし、map関数で複数の値をオブジェクトに包む場合は(lambda (x) (make-instance...)と書かなければならないため。
    • Pythonのようにクラス名の後にコンストラクタに渡す値が書けるとすっきりして見える、気がする。
  • アクセサは@で始まる名前を付ける。
  • クラスはファイルの先頭寄りにまとめて記述する。
    • アクセサを使う場所より後にアクセサを含むクラスを定義すると、そのような関数は定義されていないという警告が出るため。

ステップ2

github.com

functionという名前はcl:functionと衝突する。defpackageの:shadowを使ってもよかったかもしれない。

ステップ3

github.com

行列の計算のためにarray-operationsを導入するが、このぐらいは自分で書いてもよかったかもしれない。

Common Lispの開発環境を構築する

はじめに

プログラミングを始めるには、どの言語でも開発環境の構築が必要である。この記事ではCommon Lispの開発環境をEmacsというテキストエディタとSteel Bank Common Lisp(以下SBCLと呼ぶ)という言語処理系を用いて説明する。

まず、SBCLをインストールし、動作確認を行う。次に、サードパーティのライブラリを利用するためのQuicklispというソフトウェアを導入する。そしてEmacsをインストールし、Common Lispプログラムの編集とデバッグを容易にするため、Slyを中心にパッケージを導入する。

 

導入手順

SBCLのインストール

Common Lispはよく知られたCと同様に、標準化された言語仕様を持つプログラミング言語である。CにはGCCやClangをはじめとする言語処理系が多数あるように、Common Lispにも様々な言語処理系が存在する。この記事では、フリーかつよく使われている言語処理系のSBCLを導入する。SBCLは入力したプログラムをその場で実行できるREPLを持っているが、入力したテキストを編集する行編集機能や履歴機能を持たない。rlwrapを使うと、SBCLに行編集機能や履歴機能を付加でき、その不便さを軽減できる。

OSのパッケージマネージャを利用する方法

読者がLinuxを利用していてなおかつ管理者権限を持っていれば、ディストリビューションのパッケージマネージャを使ってインストールができる。

DebianやUbuntuの場合

$ sudo apt-get update

$ sudo apt-get -y sbcl rlwrap

ArchLinuxの場合

$ sudo pacman -Syu sbcl rlwrap

Windowsの場合はwingetが利用できる

> winget install SBCL.SBCL

手作業で導入する方法

SBCLのサイトからバイナリをダウンロードする。

Windowsの場合は、ダウンロードしたバイナリがインストーラになっているのでそれを実行する。

Linuxでは次のようにすると、ホームディレクトリに導入できる。

$ tar xf sbcl-2.4.1-x86-64-linux-binary.tar.bz2

$ cd sbcl-2.4.1-x86-64-linux

$ env INSTALL_ROOT=${HOME}/.local sh install.sh

rlwrapも次の手順に従ってインストールする。

コンパイルに必要なコンパイラとライブラリをインストールする。

$ sudo apt-get update

$ sudo apt-get install build-essential curl libreadline-dev

続いてrlwrapのソースコードをダウンロードしてコンパイルする。

$ curl -LO https://github.com/hanslub42/rlwrap/releases/download/0.46.1/rlwrap-0.46.1.tar.gz

$ tar xf rlwrap-0.46.1.tar.gz

$ cd ../rlwrap-0.46.1

$ ./configure --prefix=${HOME}/.local

$ make

$ make check

$ make install

~/.profileまたは~/.bash_profileに次の内容を追記し、ログインしなおす。

export PATH=${HOME}/.local/bin:${PATH}

動作確認をする

ここでは--noinformオプションを使い、SBCLの著作権表示を抑制している。

(quit)と入力すると、SBCLを終了できる。

$ rlwrap sbcl --noinform

* (format t "Hello, world!~%")

Hello, world!
NIL

* (quit)

Quicklispのインストール

Common Lispそれ自体には、プログラムをパッケージングして流通させる仕組みがない。パッケージングを行うにはAnother System Definition Facilityと呼ばれるライブラリが使われており、CにおけるMakeの役割を果たしている。また、ソフトウェアを簡単にダウンロードできるように、Quicklispと呼ばれるソフトウェアも広く使われている。

Quicklispは、シェルではなくCommon Lispの言語処理系からその機能を利用するのが特徴となっている。

 

まずQUicklispのインストーラをダウンロードし、GnuPGを使って改ざんの有無を確認する。

$ curl -O https://beta.quicklisp.org/quicklisp.lisp

$ curl -O https://beta.quicklisp.org/quicklisp.lisp.asc

$ gpg --verify quicklisp.lisp.asc quicklisp.lisp

続いてSBCLにインストーラをロードし、Quicklisp本体をインストールする。

$ rlwrap sbcl --load quicklisp.lisp

* (quicklisp-quickstart:install)

* (ql:add-to-init-file)

* (quit)

Qucklispの動作確認をする。ここでは、よくある処理をまとめたAlexandriaというライブラリをインストールしている。

$ rlwrap sbcl

* (ql:quickload :alexandria)

* (alexandria:ensure-list 'hello)
(HELLO)
* (alexandria:ensure-list '(hello))
(HELLO)
* (quit)

Emacsのインストール

OSのパッケージマネージャを利用する方法

DebianやUbuntuの場合

$ sudo apt-get update

$ sudo apt-get -y emacs

ArchLinuxの場合

$ sudo pacman -Syu emacs

Windowsの場合

> winget install GNU.Emacs

Slyのインストール

Common Lispはほかのプログラミング言語とは異なり、対話的環境を中心に開発を進めるスタイルをとる。SlyはEmacsとCommon Lisp処理系を連携させることで、プログラムの実行やデバッグを容易にすることを目的としたパッケージである。Slyには例えば次のような機能がある。

  • REPLにプログラムのすべてまたは一部を送信して計算結果を得る
  • 関数や変数の名前の補完
  • 関数呼び出しの履歴を得る

~/.emacs.d/init.elに次の内容を貼り付ける。

Common Lisp IDE

そしてEmacsを起動する。

$ emacs

Altキーとxキーを押下しslyと入力する(M-x sly)。

するとSLyが起動し、REPLが現れる。

 

 
 

 

 

netctl環境でpkgfile-update.serviceがfailする問題を直す

備忘録

pkgfile

pkgfileはファイルを所有しているパッケージを高速に検索できるプログラムである。そのパッケージをインストールしていなくても検索できるため、システムにないコマンドが入力されたら候補となるパッケージを提案するフックが作られている。

参考:

pkgfile - ArchWiki

問題

このpkgfileはsystemdユニットファイルを持っており、システム起動時や一定間隔ごとにデータベースの更新処理を行う。データベースはインターネットからダウンロードしてくるため、ネットワーク設定が完了する前のタイミングではユニットがfailしてしまう。自分はネットワーク設定にnetctlを利用しているのだが、解決法が長いこと分からなかった。

解決法

pkgfile - ArchWikiではなくsystemd - ArchWikiのほうに解決法が書かれていた。

netctl環境でpkgfileを導入するには次のステップを踏まなければならない。

# pacman -Syu
# pacman -S pkgfile
# systemctl enable netctl-wait-online.service # <- これが必要
# systemctl enable pkgfile-update.timer

競技プログラミングにRustで参加するときに、なるべく高速で入出力する

備忘録 考えたこと

この記事の続きです。

elderica.hatenablog.jp

自分のコードが遅い

ここずっと、アルゴ式というサイトでいろいろな問題に挑戦しています。このサイトは競うためものではないので、正答例や解説を読んだり、他人のコードを読むのが簡単です。

自分はRustで解いていますが、自分のコードが他人の書いたC++より何倍も実行時間が長いのがずっと気になっていました。RustはC++と遜色ないパフォーマンスが出せる言語だったはずです。自分のコードと、正答例、他人のC++コードを比較してみましたが、問題を解く部分のアルゴリズムはほぼ同じに見えました。そうであれば何がコードを遅くしているのでしょうか？

問題のコード

algo-method.com

use std::collections::VecDeque;

fn main() {
    #[allow(unused)]
    let _x: usize = scan_line()[0];
    let _q: usize = scan_line()[0];

    let mut scheduled_completion_times: VecDeque<usize> = VecDeque::new();
    let mut completed_task_counter: usize = 0;
    for _ in 0.._q {
        let mut query = read_words().into_iter();
        let op_id = query.next().expect("query has operation id");
        let current_time: usize = query.next().unwrap().parse().unwrap();
        match op_id.as_str() {
            "0" => {
                scheduled_completion_times.push_back(current_time + _x);
            }
            "1" => {
                while let Some(&s) = scheduled_completion_times.front() {
                    if s <= current_time {
                        completed_task_counter += 1;
                        scheduled_completion_times.pop_front();
                    } else {
                        break;
                    }
                }
                println!("{}", completed_task_counter);
            }
            _ => unreachable!(),
        }
    }
}

fn read_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    String::from(line.trim())
}

#[allow(dead_code)]
fn read_words() -> Vec<String> {
    read_line().split_whitespace().map(String::from).collect()
}

#[allow(dead_code)]
fn scan_line<F>() -> Vec<F>
where
    F: std::str::FromStr,
{
    read_line()
        .split_whitespace()
        .flat_map(|s| s.parse::<F>())
        .collect()
}

プロファイリングしてみる

犯人探しに役立てるため、プロファイリングを行います。RustではCやC++と同じものが使えるようです。

nnethercote.github.io

qiita.com

cargo-flamegraphを利用してみることにします。まずはインストールします。

$ cargo install flamegraph

新しくパッケージを作り、問題のコードを配置します。 ここで、大きめのテストケースをアルゴ式のサイトからダウンロードしておきます。

$ cargo new task889 && cd task889
$ cat > src/main.rs # コードをコピペ
$ cp ~/Downloads/<テストケースのファイル名> ./testcase.txt

計測します。

$ env CARGO_PROFILE_RELEASE_DEBUG=true cargo flamegraph --freq 10000 < testcase.txt > /dev/null

出てきたflamegraph.svg はこんな感じです。ブラウザで開くと、塗り分けられた四角形をクリックして拡大できます。縦軸がスタックで横軸が時間(正確にはサンプリングしたときに実行中だった関数の割合)です。

gist.github.com

std::io::stdio::_print関数とtask889::read_words関数が、main関数を実行中だった時間のほとんどを占めています。コードが遅い原因は入出力が怪しいことがわかりました。

事例を調べてみる

調べてみると、Rustは並行性を考慮してデフォルトではバッファリングを行なわないそうです。

keens.github.io

codom.hatenablog.com

また、競技プログラミング向けに高速で入力が可能なクレートがありました。このクレートはMITライセンスかつモジュール一つで構成されています。このモジュールと標準出力のバッファリングを自分のコードに導入すると、C++と同等の実行時間になりました。

github.com

fast_input を読む

このクレートではStdinのロックを取って入力をEOFまで読み、全てをVec<u8>型でヒープに保持します。 また、入力を切り出すときはヒープに割り当てを行うような操作をせず、単にスライスを返すだけという設計になっています。

ここで自分のコードとfast_inputを比べてみます。

fn read_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    String::from(line.trim())
}

#[allow(dead_code)]
fn read_words() -> Vec<String> {
    read_line().split_whitespace().map(String::from).collect()
}
  • 単語ごと/行ごとにヒープに割り当てを行っている。
  • 入出力で明示的にロックを取っておらず、バッファリングもしないため、ロックとアンロックが大量に発生する。

問題はここにあったのです。

入力コードの刷新

MITライセンスとはいえ、fast_input をそのまま使い続けるのはどうだろうかと感じ、こんな感じのコードを書きました。slurpする型なので安直にSlurperという名前です。もっと良い名前はあるでしょうか？

use std::cell::Cell;
use std::io::{stdin, Read};

struct Slurper {
    str: String,
    pos: Cell<usize>,
}

impl Slurper {
    fn stdin() -> Self {
        let mut s = String::with_capacity(65536);
        stdin()
            .lock()
            .read_to_string(&mut s)
            .expect("read until EOF");
        Self {
            str: s,
            pos: Cell::new(0),
        }
    }

    fn read_line(&self) -> &str {
        let start_pos = self.pos.get();
        let mut current_pos = start_pos;
        while current_pos < self.str.len() && &self.str[current_pos..current_pos + 1] != "\n" {
            current_pos += 1;
        }
        self.pos.set(current_pos + 1);
        self.str[start_pos..current_pos].trim_end()
    }

    #[allow(dead_code)]
    fn read_word(&self) -> &str {
        let start_pos = self.pos.get();
        let mut current_pos = start_pos;
        while current_pos < self.str.len()
            && &self.str[current_pos..current_pos + 1] != " "
            && &self.str[current_pos..current_pos + 1] != "\n"
        {
            current_pos += 1;
        }
        self.pos.set(current_pos + 1);
        self.str[start_pos..current_pos].trim_end()
    }

    #[allow(dead_code)]
    fn read_words(&self) -> Vec<&str> {
        self.read_line().split_ascii_whitespace().collect()
    }

    #[allow(dead_code)]
    fn scan_line<F>(&self) -> Vec<F>
    where
        F: std::str::FromStr,
    {
        self.read_line()
            .split_ascii_whitespace()
            .flat_map(str::parse::<F>)
            .collect()
    }
}

このコードを導入して試してみると、その結果はfast_inputを使ったものやC++コードとほぼ同等になりました! Vec<u8>ではなくStringで保持しているせいか、ごく僅かに遅いですが十分でしょう。 collectせずにイテレータを返してもいいかもしれません。

反省

実際には、かなりの試行錯誤とGoogle検索に頼り、構造的なアプローチが取れていませんでした。デバッグやプロファイリングの技術をもっと学ぶ必要がありそうです。

検索するなかで便利そうなツールを他にも見つけました。

  • Hotspot
    perfのプロファイリングデータを読んで視覚的に表示するツールです。
  • KCachegrind
    ValgrindのツールのCallgrindが出力したプロファイリングデータを読みこんで視覚的にコールグラフを見られるツールです。プロファイリングにも使えます。
  • gprof2dot
    いろいろなプロファイリングツールが出力したプロファイリングデータから、コールグラフなどを出力できるツールです。

コンパイラの開発を通してプログラムの書き方について学ぶ取り組み

記録を取ることもなく黙々とやっていたので、日記はステップ11から。

  • 2020/6/11
    • 無引数の定義を実装した。
  • 2020/5/28
    • 忙しかったのと、ほかにやってみたいことがあったのでブランクが空いてしまった。
    • 関数呼び出しの実装をした。
    • strndup関数がimplicit declaration errorになって呼べないのでおかしいなと思って、manを見たりStackoverflowを見た。原因は、プログラム内で_POSIX_C_SOURCEを定義してないせいで関数原型宣言が公開されていなかったのだった。
  • 2020/5/12
    • for文を追加した。
    • ブランク空けちゃったのはもったいない。
    • リファレンス実装では補助的なファクトリ関数を用意して読みやすさと書きやすさを高めている。
      • new_unaryやread_expr_stmtなど。
      • リファレンンス実装ではlhsを使いまわしているのだから、自分は二項演算子用のファクトリ関数で書いているが、本来はunary用専用のノードを用意したほうがいいのだろうなと思った。
        • これはTODOとしたい。
  • 2020/5/7
    • if文とwhile文を追加した。
    • リファレンス実装の中でシリアルナンバーを一時的な変数に保存しているのを見て、どうしてこう書いているのか不思議に思い、そうしないで直接シリアルナンバーを出力するよう書いてみたところ、このテストケースでGNUアセンブラからラベルが見つからないエラーが出た。
      • 理由は単純で、子のノードをコンパイル中にシリアルナンバーがインクリメントされてしまい、戻ってきたら対応が取れなくなってしまうからだった。
  • 2020/5/5
    • リファレンス実装に倣ってFunction構造体を足してみた。
    • 9ccはchibiccを参考してCでやっているが、zinccでのやりかたも気になりCommon Lispで真似てみることにした。CLだとテストを整備するのが少々煩雑で、Cとシェルスクリプトの組みあわせのやりかたはとても単純で良いと思った。
  • 2020/5/4
    • if文を追加しようとしたがバグがあり、その解決の過程で、それまでに書いたコードにはその場しのぎ のコードが目立つと感じて一旦取りやめた。
      • コード生成においてpop raxが入力プログラムの各式のコード生成終了後に挿入されてしまい、if文がraxの値に依存していたせいで、必要な値が潰されてしまう現象が起きていた。
    • リファレンス実装を見ながらリファクタリングや、制約の撤廃を行なった。
      • main関数のコード生成の責任をコード生成部に移した。
      • ファイル名や関数名をより良いものにした。
      • 各モジュールが公開すべき関数やグローバル変数と非公開とすべき関数とグローバル変数を分けた。
      • オブジェクト生成を専用の関数で行なうように統一した。
      • スタックフレームのサイズを使った変数の個数から計算したり、受け入れ可能なプログラム行をメモリの許す限り無制限とした。
  • 2020/4/28
    • ステップ9からステップ11まで進んだ。
    • 可変長の変数を定義できるようになった。
      • 本では、識別子に使用可能な文字を判定するのにctype.hのisalnum(3)関数の代わりにis_alnum関数を定義して使っていた。isalnum(3)はアンダースコアを認識せず、ロケールに左右されるためだろうか？
    • returnキーワードを導入した。
      • 本ではreturnキーワードのために、トークン用の新たな列挙定数TK_RETURNを定義するように書いていたが、予約語を表すTK_RESERVEDで十分と考えた。演算子もキーワードも言語の予約語と考えたほうがすっきりするし、導入もしやすかった。
      • returnキーワードに対してコード生成するとき、return用のエピローグの中で誤ってmov rsp, rspと書いていて、SEGVを起こした。正しくはmov rsp, rbp。
    • gdbのTUIを起動する方法を知った。

Tips/気をつけること

連結リストを構築するときは、ダミーのhead要素を作ってそこに新しい要素を繋げていって、最後にhead->nextを返すようにするとコードが簡単になります。このような方法ではhead要素に割り当てられたメモリはほとんど無駄になりますが、ローカル変数をアロケートするコストはほぼゼロなので、特に気にする必要はありません。

/* こういうこと？ */

#include <stdio.h>
#include <stdlib.h>

typedef struct Cell Cell;
struct Cell {
    struct Cell *next;
    char *word;
};

/* producer */
Cell *create_list(void) {
    Cell dummy = { .next = NULL, .word = NULL };
    Cell *current = &dummy;

    char *words[] = {"akizuki", "teruzuki", "suzutsuki", "hatsuzuki", NULL};

    for (char **place = words; *place != NULL; place++) {
        Cell *cell = calloc(1, sizeof(Cell));
        cell->word = *place;
        cell->next = NULL;
        current->next = cell;
        current = cell;
    }
    return dummy.next;
}

/* consumer */
int main(void) {
    Cell *current = create_list();

    for (; current != NULL; current = current->next) {
        printf("%s\n", current->word);
    }
    return 0;
}

  • 前章までに実装した機能では、関数の最後に必ず1つのret命令を出力していました。この章で説明した方法でreturn文を実装すると、return文ごとにさらに余分なret命令が出力されることになります。それらの命令はまとめることも可能ですが、ここでは簡単に実装するために、ret命令を複数出力してもかまわないということにしました。こういう細かいところは今の時点では気にしても仕方がないので、実装のシンプルさを優先することが大切です。難しいコードを書けるというのは役立つスキルですが、そもそもコードを難しくしすぎないというのは、時にはさらに役立つスキルなのです。

    • 無駄が気になることは多い。つい、もっと賢い処理にしようとしてしまうこともあるが、その努力に見合わない結果になるどころか、複雑な書き方になりやすいってことだろうか？

Undefined Behavior(未定義の動作)

Common Lispを学ぶためのリソース

まずはこの記事を読むことをおすすめします。

A Road to Common Lisp 翻訳 · GitHub

書籍

Practical Common Lisp(実践Common Lisp)

gigamonkeys.com

一番最初に読むのに向いている。内容は古びてはいるものの、リスト遊びに終始するよりはるかに良い。日本語版もある。

Programming Algorithms

vseloved.github.io

Common Lispで様々なアルゴリズムを実装する本。

Common Lisp Recipes

weitz.de

github.com

Vim/Neovimで編集するためのプラグイン

github.com

github.com

github.com

ソースコードを読むなら

Alexandria

alexandria.common-lisp.dev

数多くのユーティリティ関数やマクロを提供しており、これを利用するプロダクトも多い。

CL-UTILITIES

www.cliki.net ユーティリティ関数のつめあわせ。

GENERIC-COMPARABILITY

github.com

OpenSMTPDを使ってOutlook.com経由でメールを送る

前提とする環境はArch Linuxで公式パッケージからopensmtpdをインストールする場合。

まずMicrosoftアカウントでアプリパスワードを発行する。 パーミッションは640、所有ユーザはroot、所有グループはsmtpdとして/etc/smtpd/secretsを書く。

 hogefuga myaccount@outlook.jp:アプリパスワード

1列目のhogefugaはラベルなのでなんでもよい。あとで使う。 2列目は使っているメールアドレスとアプリパスワードをコロンで繋いだもの。

/etc/smtpd/smtpd.confは次のような内容にする。

table aliases file:/etc/smtpd/aliases
table secrets file:/etc/smtpd/secrets
 
listen on localhost
 
action "local" maildir alias <aliases>
action "relay" relay host smtp+tls://hogefuga@smtp.office365.com:587 auth <secrets>
 
match for local action "local"
match from local for any action "relay"

7行目のhogefugaはsecretsで定義したラベルにする。

これでsendmail(1)が使えるようになるので、sendjpmailなどで遊ぼう。

つぎのページを参考にした。

support.microsoft.com