Posts

Brainfuckの記事ではあるが、実はモナド変換子を使ってみたかっただけだったりする。 以下の3部の記事で構成されている。 インタプリタと基本的な命令の実装 (この記事) CUIでの入出力処理の実装 CUIでのインタプリタ可視化 Halogenを用いた入出力処理の実装 この記事でインタプリタの基本的な部分を実装し、 残りの3記事はインタプリタとはあまり関係ない話となる (とはいえ出力ができないと Hello, World すら書けないので、必要な記事ではある)。 Brainfuckインタプリタの構造 Brainfuckインタプリタは以下の情報を内部に持っているものとする。 program: 命令の列。 iptr: インストラクションポインタ。実行する命令の位置を示す。プログラムカウンタみたいなもの。 dptr: データポインタ。メモリ上のある位置を示す。 memory: メモリ。 インタプリタは以下の手順を踏む。 iptr番目の命令をprogramから読み取る。 読み取れなかったらプログラムを終了する。 命令に応じてmemory、dptrの書き換えだったり、入出力を行う。 iptrを1進め、手順1に戻る。 どんな命令があるのかについてはWikipedia参照。 準備 適当なディレクトリを作って、プロジェクトの初期化を行う。 % spago init 命令列の作成 src/Brainfuck/Command.pursを作成する。 Commandを定義。Showクラスのインスタンスにして、Charからの変換をする関数を作る。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 module Brainfuck....

線形回帰を勾配降下法を使って解いてみたメモ。 問題設定 $\bm{y} = (y^{(1)}, y^{(2)}, \ldots, y^{(N)})^T,\ \bm{x}_i = (1, x_1^{(i)}, x_2^{(i)}, \ldots, x_D^{(i)})^T$ とおく。$(\bm{x}_i, y_i),\ i = 1, 2, \ldots, N$ がデータとして与えられている。このとき、入力と出力の間に $$ \begin{aligned} y &= h_{\bm{w}}(\bm{x})\\ &:= w_0 + w_1x_1 + w_2x_2 + \cdots + w_Dx_D\\ &= \bm{w}^T\bm{x} \end{aligned} $$ が成り立つと仮定し、これに適する$\bm{w}$を見つけたい。「適する」とは具体的に何なのかというと、ここでは予測とデータとの二乗誤差の和 $$ J(\bm{w}) = \frac{1}{2} \sum_{i=1}^{N} (h_{\bm{w}}(\bm{x}_i) - y^{(i)})^2 $$ が最小となる $\bm{w}$ を求める。この $J$ については呼び名がいくつかあるが、ここではコスト関数と呼ぶ。 係数 $1/2$ は微分した時に出てくる $2$ を消し去るための便宜的なものであり、つける必然はない。 コスト関数の勾配 $w_j$に関する偏微分を計算すると、 $$ \frac{\partial J(\bm{w})}{\partial w_j} = \sum_{i=1}^{N} (h_{\bm{w}}(\bm{x}_i) - y^{(i)})x_j^{(i)},\ j = 0, 1, \ldots, D $$...

学校の授業で勉強はしたが、自分で考えてまとめたことはなかったのでここに記しておく。 問題設定(1) $\bm{y} = (y^{(1)}, y^{(2)}, \ldots, y^{(N)})^T,\ \bm{x}_i = (1, x_1^{(i)}, x_2^{(i)}, \ldots, x_D^{(i)})^T$ とおく。$(\bm{x}_i, y_i),\ i = 1, 2, \ldots, N$ がデータとして与えられている。このとき、入力と出力の間に $$ \begin{aligned} y &= h_{\bm{w}}(\bm{x})\\ &:= w_0 + w_1x_1 + w_2x_2 + \cdots + w_Dx_D\\ &= \bm{w}^T\bm{x} \end{aligned} $$ が成り立つと仮定し、これに適する$\bm{w}$を見つけたい。「適する」とは具体的に何なのかというと、ここでは予測とデータとの二乗誤差の和 $$ J(\bm{w}) = \frac{1}{2} \sum_{i=1}^{N} (h_{\bm{w}}(\bm{x}_i) - y^{(i)})^2 $$ が最小となる $\bm{w}$ を求める。この $J$ については呼び名がいくつかあるが、ここではコスト関数と呼ぶ。 係数 $1/2$ は微分した時に出てくる $2$ を消し去るための便宜的なものであり、つける必然はない。 コスト関数の最小値を求める(1) コスト関数の行列表現 まず $J$ を行列だけで表現してみる。 $$ \begin{aligned} J(\bm{w}) &= \frac{1}{2} \sum_{i=1}^{N} (\bm{w}^T\bm{x}_i - y^{(i)})^2\\ &= \frac{1}{2} \sum_{i=1}^{N} (\bm{x}_i^T\bm{w} - y^{(i)})^2\\ &= \frac{1}{2} \begin{pmatrix} \bm{x}_1^T\bm{w} - y^{(1)}\\ \bm{x}_2^T\bm{w} - y^{(2)}\\ \vdots\\ \bm{x}_N^T\bm{w} - y^{(N)}\\ \end{pmatrix}^T \begin{pmatrix} \bm{x}_1^T\bm{w} - y^{(1)}\\ \bm{x}_2^T\bm{w} - y^{(2)}\\ \vdots\\ \bm{x}_N^T\bm{w} - y^{(N)}\\ \end{pmatrix}\\ &= \frac{1}{2} \left( \begin{pmatrix} \bm{x}_1^T\bm{w}\\ \bm{x}_2^T\bm{w}\\ \vdots\\ \bm{x}_N^T\bm{w}\\ \end{pmatrix} - \bm{y} \right)^T \left( \begin{pmatrix} \bm{x}_1^T\bm{w}\\ \bm{x}_2^T\bm{w}\\ \vdots\\ \bm{x}_N^T\bm{w}\\ \end{pmatrix} - \bm{y} \right) \end{aligned} $$ ここで、...

英語だと “bouncing ball programming” とか検索すると出てくるやつ。 単にボールが弾むだけなのだが、思ったより勉強になったので書き残す。 実際のプログラムの動作はGitHub Pagesを参照。 プロジェクトの初期化 適当なディレクトリを作って、その中でプロジェクトを作成。 % spago init % spago build 今回は、追加のパッケージは必要なときにspago installコマンドで入れることにする。 Canvas入門 src/Main.pursを以下のようにする。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 module Main where import Prelude import Data.Maybe (Maybe(..)) import Effect (Effect) import Effect....

シンプルなToDoリストのWeb APIを作る。 今までWSGIの仕様のみ、Werkzeug の2通りで実装したが、今回はFlaskといくつかのライブラリを使う。使うのは以下の通り。 Flask: WSGIアプリフレームワーク。 peewee: ORMライブラリ。 marshmallow: データの変換やvalidationをするためのライブラリ。 Flaskとは WSGIのWebアプリを作るためのフレームワーク。 フレームワークであるため、Flaskが用意した作法に従ってコードを書くことで比較的手軽にWebアプリが作成できる。 前回との比較でいうならば、例えばルーティングの仕組みをプログラマが書く必要はない。これはFlaskに備わっている。 Djangoのようなフレームワークとは違って、持っている機能は少ない。必要に応じて外部ライブラリを組み合わせる。 例えば、Djangoではデフォルトでデータベースの仕組みが内蔵されているが、Flaskにはない。その代わりに、 データベースのライブラリとしてsqlite3やSQLAlchemy、peeweeなど、好きなものを用いれば良い。 ToDoリストAPIの仕様 今回ToDoのデータは以下キーと値を持つJSONデータとする。 key value id ID content ToDoの内容 created_at 作成日時 (ISO8601) updated_at 更新日時 (ISO8601) APIの仕様は以下の通り。 URL Method 説明 返却値 /todo/ GET 全てのToDoを取得。 ToDoのデータのリスト /todo/ POST ToDoを作成。 なし (LocationヘッダにそのToDoへのURLを乗せる) /todo/<todo_id> GET todo_idのidを持つToDoを取得。 ToDoのデータ /todo/<todo_id> PUT todo_idのidを持つToDoを変更。 なし /todo/<todo_id> DELETE todo_idのidを持つToDoを削除 なし データはSQLiteで管理する。 雛形 todo_listディレクトリを作成。todo_list/__init__.pyを以下のようにする。 1 2 3 4 5 6 7 8 9 10 11 from flask import Flask def create_app(): app = Flask(__name__) @app....

シンプルなToDoリストのWeb APIを作る。 前回はWSGIの仕様のみを参考にして作ったが、 今回はWerkzeugというライブラリを利用する。 Werkzeugとは Werkzeugのドキュメントの “Werkzeug is a comprehensive WSGI web application library.“という文面にもある通り、 これはWSGIのWebアプリを作るためのライブラリである。 あくまでフレームワークではなく、ライブラリであることに注意する。 Webアプリを作るうえで、便利なクラスや関数が用意された「道具箱」のようなイメージを持つとよいかもしれない (そもそも"werkzeug"という単語はドイツ語で「道具」という意味)。 あくまで道具があるだけなので、どういう設計を行うかなどを考える余地がある。 ToDoリストAPIの仕様 前回と同じだが、再掲する。 簡単のため、今回ToDoのデータはidと内容のみ持つデータとし、{ id: 0, "content": "やること" }というJSON形式とする。 APIの仕様は以下の通り。 URL Method 説明 返却値 /todo/ GET 全てのToDoを取得。 ToDoのデータのリスト /todo/ POST ToDoを作成。 なし (LocationヘッダにそのToDoへのURLを乗せる) /todo/<todo_id> GET todo_idのidを持つToDoを取得。 ToDoのデータ /todo/<todo_id> PUT todo_idのidを持つToDoを変更。 なし /todo/<todo_id> DELETE todo_idのidを持つToDoを削除 なし データは最終的にはSQLiteで管理する。 雛形 app.pyを以下のようにする。 1 2 3 4 5 6 7 8 9 10 11 from werkzeug.wrappers import Response def app(env, start_response): response = Response('Hello, World') return response(env, start_response) if __name__ == '__main__': from werkzeug....

シンプルなToDoリストを作る。 今回は勉強のため、Webアプリケーションフレームワークは使わずに、 敢えてWSGIの仕様のみ参考にして書く． WSGIとは WSGIとは、WebサーバーとWebアプリとの間の標準的なインターフェース。 WSGIの仕様に沿ってWebアプリを作れば、 WSGI対応のどんなWebサーバーとも連携することができる。 WSGIの仕様はPEP3333に書かれている． ToDoリストAPIの仕様 簡単のため、今回ToDoのデータはidと内容のみ持つデータとし、{ id: 0, "content": "やること" }というJSON形式とする。 APIの仕様は以下の通り。 URL Method 説明 返却値 /todo/ GET 全てのToDoを取得。 ToDoのデータのリスト /todo/ POST ToDoを作成。 なし (LocationヘッダにそのToDoへのURLを乗せる) /todo/<todo_id> GET todo_idのidを持つToDoを取得。 ToDoのデータ /todo/<todo_id> PUT todo_idのidを持つToDoを変更。 なし /todo/<todo_id> DELETE todo_idのidを持つToDoを削除 なし データは最終的にはSQLiteで保存するが、最初は単純にlistで扱う。 雛形 まずはサーバーを作る。この時点ではルーティング処理を書いていない。 どのようなリクエストをしてもHello, Worldをレスポンスとして返す。 1 2 3 4 5 6 7 8 9 10 11 from wsgiref.simple_server import make_server def app(env, start_response): start_response('200 OK', [('Content-type', 'text/plain; charset=utf-8')]) return [b'Hello, World....

1年以上前に書いた記事 で、HTTPサーバーもどき(リクエストを読まず、ただ一方的にレスポンスを返すだけのサーバ)を書いた。 今回はもう少しだけこれを進化させる。 動機 非常にどうでもいいのだが動機を記しておく。 Land of Lispの13章でソケット通信が出てきた。 Land of Lispで扱っているCommon Lispの処理系がCLISPなのに対し、今自分が利用しているのはSBCLなので、 本文中のコードが動かない。そこで色々調べて、usocketを利用しようと思いつく。 その後なんとか書き上げる。ところがChromeやcurlでは動くのに、Safari(現バージョンは14.0.2)では動かない。ページを読み込んだ後、タイムアウトしたかのような挙動を起こす。 その理由を明らかにしたくて「そもそもLisp以外では動くのか。例えばPythonのソケット通信では動くのか」「PythonのWebアプリ、例えばFlaskの開発用サーバーで動くのはなぜか」 など色々調べた。cpythonのsocketserverやhttp.serverなどのソースコードも読んだ。 調べた結果、どうやらSafariがたまに「何も送らない通信(?)」を行うことが原因だった。 何も送ってくれないと、リクエストをrecvで受け取るときに、ブロッキングが働いてサーバー側が固まってしまう。 ただし普通のリクエストも送ってくるので、マルチスレッドなどの多重化を行なっておけば 問題なくSafariでもページが読み込まれる。なのでFlaskの開発用サーバーでは大した問題にならなかった。 Safariがなぜこんな通信をするのかはよく分からない。HTTPの仕様をちゃんと読んでいないので、何か見落としがあるのだろうか。もしくはバグか何かなのか。 何はともあれ、色々ソースコードを読んでいくうちに、リクエストヘッダの取得のやり方など参考になった。 せっかくなのて得た知見を元に再びHTTPサーバを作ってみようと思い立った。 作るもの 以下の条件を満たすHTTPサーバのようなものを作る(そもそも、どこまで実装できたらHTTPサーバと呼べるのだろうか)。 マルチスレッドにする。 HTTPリクエストのリクエストライン、ヘッダ情報をパースする。 リクエストボディは今回は考慮しない。 前回に比べてPythonについての知見が広がったため、 コードにおいてf-stringsやtype-annotation、dataclassなどの機能を使ってみている。 また処理を細かく関数に分ける。 listen用のソケットの作成 待ち受け用のソケットを作成し、それを返す関数を作成する。 bindやlistenは前回説明した通り。 動作確認を何度も行う都合上、TIME_WAIT状態のポートを待つのは面倒なので、setsockopt(...)の記述でそれを解決している。 (この辺りの詳細は"TIME_WAIT"とか"REUSEADDR"あたりのキーワードで検索すれば出てくる) 1 2 3 4 5 6 7 8 9 import socket def server_socket(port: int): soc = socket.socket(socket.AF_INET, socket.SOCK_STREAM) soc.setsockopt(socket.SOL_SOCKET, socket.SO_REUSEADDR, True) soc.bind(('', port)) soc.listen(5) return soc 動作確認 以下のようにrun_serverを作る。 1 2 3 4 5 6 7 8 9 10 def run_server(port: int): with server_socket(port) as soc: while True: conn, addr = soc....

平綴じ印刷ができるように、PDFの順序を入れ替えたり、空白ページを挿入するプログラムを書いた。 方法1はPython + いろんなコマンドで、方法2はPythonのPDFライブラリであるPyPDF4を利用した方法。 実装してみた結果、後者が圧倒的に簡単だった。 動機 平綴じがしたい場面が出てきたが、印刷機に専用の設定が見つからなかった。 なので平綴じになるようにPDFのページ順を1,2,3,4,5,6,7,8,…から4,1,2,3,8,5,6,7,..に変え、それをプリンタで両面刷り(短辺綴じ)・2ページ割付で印刷することを考えた。 平綴じの場合、紙に両面4ページずつ印刷されることになる。するとPDFのページ数は4の倍数でなくてはならない。よって、4の倍数でなかった場合はその分を空白ページで埋めなければならない。 PDFファイルの準備 テスト用にPDFファイルを作っておく。ここはなんでも良いのだが、とりあえず以下のLaTeXのコードから10ページのPDFファイルを作る。名前はinput.pdfとしておく。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 \documentclass{jsarticle} \begin{document} \centering \Huge 1 Page \newpage 2 Page \newpage 3 Page \newpage 4 Page \newpage 5 Page \newpage 6 Page \newpage 7 Page \newpage 8 Page \newpage 9 Page \newpage 10 Page \end{document} 方法1：Python + 諸々のコマンドの利用 方針 PDFのページ順を変えるためには、pdftkコマンドを利用すれば良い。pdftkは、Homebrewならbrew install pdftk-javaで使えるようになる)。例えば8ページのPDFファイルinput....

PureScriptで配列のシャッフルをしたい。型はこんな感じ。乱数は副作用を伴うため、返り値の型はEffectで包まれる。 1 shuffle :: forall a. Array a -> Effect (Array a) アルゴリズムはFisher-Yates ShuffleのModern Algorithmの項の2つ目を利用する。これをさまざまな方法で作成したところ、Functor, Applicative, Monadなどに関連する事項だったり、STモナドの使い方、FFIの使い方だったりが学べたので、備忘のために書く。 準備 適当なディレクトリでプロジェクトを作成する。今回使うパッケージをインストールする。 $ spago init $ spago install arrays $ spago install random $ spago install foldable-traversable 方法1: 素直(?)な書き方 ここでは、src/Shuffle.pursに記述する。 天下り的ではあるが、これから使う関数、型をimportしておく。 1 2 3 4 5 6 7 8 9 10 module Shuffle where import Prelude import Effect (Effect) import Data.Array (range, (!!), updateAt, length) import Data.Traversable (for) import Effect.Random (randomInt) import Data.Maybe (maybe) import Data....