動作の可視化 インタプリタ動作中における内部状態を可視化できると面白い。 そこで、インタプリタ動作中のログを出力できるような仕組みを作る。 ログは以下のタイミングで起こるようにする。 onStart: インタプリタが動作したときに起こる。 onState state: 各ステップで状態を取得したときに起こる。 onCmd cmd: 各ステップで命令を取得できたときに起こる。 onEnd: インタプリタが終了するときに起こる。 これらはイベントリスナのように、関数の形で指定する。 Logの作成 src/Brainfuck/Interp/Log.pursを作成。 以下のimport文を書く。 1 2 3 4 5 6 7 8 9 module Brainfuck.Interp.Log where import Prelude import Brainfuck.Interp (Interp) import Brainfuck.State (State) import Brainfuck.Command (Command) import Effect.Class (class MonadEffect, liftEffect) import Effect.Console (log) Logを定義。 1 2 3 4 5 6 newtype Log m = Log { onStart :: Interp m Unit , onState :: State -> Interp m Unit , onCmd :: Command -> Interp m Unit , onEnd :: Interp m Unit } 関連する関数を定義。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 logStart :: forall m. Log m -> Interp m Unit logStart (Log { onStart }) = onStart logState :: forall m. Log m -> State -> Interp m Unit logState (Log { onState }) = onState logCmd :: forall m. Log m -> Command -> Interp m Unit logCmd (Log { onCmd }) = onCmd logEnd :: forall m. Log m -> Interp m Unit logEnd (Log { onEnd }) = onEnd いくつかのLog mを作っておく。 ...

入出力用のストリーム作成 例えば出力だけ考えてみると、まず考えられるのは単純に、 logで出力することである。しかしlog以外の選択肢も考えられる。 logでコンソール出力するだけでなく、Webページのテキスト上で出力したり、テキストファイルに吐き出したりできるような汎用性が持たせられると良い。 そこで今回は、いわゆる「ストリームオブジェクト」のようなものを作って、そこから入出力を行うような設計にしてみる。 Streamの作成 src/Brainfuck/Interp/Stream.pursを作成。この後使うモジュールをインポート。 1 2 3 4 5 module Brainfuck.Interp.Stream where import Prelude import Brainfuck.Interp (Interp) Stream型を作成する。これは入出力を束ねた型になっている。 inputは、外部からの入力を1文字受け取る。 outputは、Charの値を外部に出力する。 1 2 3 4 newtype Stream = Stream { input :: Interp Char , output ::Char -> Interp Unit } Streamを通じてデータを読み書きする関数を作成。 1 2 3 4 5 6 7 read :: Stream -> Interp Char read (Stream { input }) = input write :: Char -> Stream -> Interp Unit write c (Stream { output }) = output c 1 2 3 4 5 6 defaultStream :: Stream defaultStream = Stream { input, output } where input = pure 'N' -- Not Implemented output _ = pure unit -- Not Implemented ‘.‘と’,’ src/Brainfuck/Interp/Command.pursを修正する。まず以下のインポート文を追加。 1 2 3 import Brainfuck.Interp.Util (readCharOrFail) import Brainfuck.Interp.Stream (write, read, Stream) import Data.Char (toCharCode) as Char StreamはEnvのレコードのフィールドとして扱いたいところだが、 それをやるとBrainfuck.Interp.Stream、Brainfuck.Env、Brainfuck.Interpとでcircular importとなってしまう。 仕方ないのでinterpCommandの引数で扱うことにする。 ...

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.Command where import Prelude data Command = IncPtr -- "+" | DecPtr -- "-" | IncDat -- ">" | DecDat -- "<" | LBrace -- "[" | RBrace -- "]" | Output -- "." | Input -- "," | Nop -- otherwise instance Show Command where show = case _ of IncPtr -> ">" DecPtr -> "<" IncDat -> "+" DecDat -> "-" LBrace -> "[" RBrace -> "]" Output -> "." Input -> "," Nop -> "nop" fromChar :: Char -> Command fromChar = case _ of '>' -> IncPtr '<' -> DecPtr '+' -> IncDat '-' -> DecDat '[' -> LBrace ']' -> RBrace '.' -> Output ',' -> Input _ -> Nop 続いて、src/Brainfuck/Program.pursを作成。この後使う関数をまとめて読み込んでおく。 ...

線形回帰を勾配降下法を使って解いてみたメモ。 問題設定 $\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.Console (log) import Graphics.Canvas (CanvasElement, Dimensions) import Graphics.Canvas as Canvas import Math as Math canvasDimen :: Dimensions canvasDimen = { width: 600.0 , height: 600.0 } initCanvas :: CanvasElement -> Effect Unit initCanvas canvas = Canvas.setCanvasDimensions canvas canvasDimen main :: Effect Unit main = Canvas.getCanvasElementById "canvas" >>= case _ of Just canvas -> do initCanvas canvas ctx <- Canvas.getContext2D canvas Canvas.fillPath ctx $ Canvas.arc ctx { x: canvasDimen.width / 2.0 , y: canvasDimen.height / 2.0 , start: 0.0 , end: Math.tau , radius: 10.0 } Nothing -> log "Error on getCanvasElementById." ビルドに当たって，必要な以下の3つのパッケージをインストールする。 ...

シンプルな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.route('/') def hello(): return 'Hello, World' return app exportコマンドで環境変数を設定する。 ...

シンプルな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.serving import run_simple run_simple('127.0.0.1', 5000, app, use_debugger=True, use_reloader=True) 以降、サーバーを起動する際はpython3 app.pyを実行する。 ...

シンプルな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.'] if __name__ == '__main__': httpd = make_server('', 5000, app) httpd.serve_forever() 以降、サーバーを起動する際はpython3 app.pyを実行する。 ...

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.accept() print(f'Connected: {addr}') with conn: conn.shutdown(socket.SHUT_RDWR) if __name__ == '__main__': run_server(8080) 作ったサーバーを実行し、別の端末でcurl localhost:8080とすると、サーバー側で以下のようなメッセージが出力される。 60724の部分は実行の度に異なる。 ...