開拓馬’s blog

いろいろやる

ほとんどのエンジニアには解けるらしいパズルを解いてみた

ジャバ・ザ・ハットリ氏作成の「ほとんどのエンジニアには解けるパズル」*1シリーズを全問解いたので感想とかwrite upとかを書きます。

出題者のブログはこちら

問題一覧はこちら(全8問)

目次

感想

問題はマイルドなCTFみたいでした。CTFはakictfksnctfの問題をちまちま解いたり、SECCONの過去問を漁ったりしていたので、こうした形式のパズルには多少慣れていました。ここに上げたサイトの問題と比較すれば「ほとんどのエンジニアには解けるパズル」は簡単な部類なのかなと思います。

解くにあたってcurlコマンドの基礎を学ぶことができたのは収穫でした。もともとcurlコマンドに対する理解は「-Oコマンド付けてファイルを落とすやつでしょ」ぐらいだったので、一般的なサーバにリクエストを投げるという使い方を確認することができました。

その意味では、最初の3問は有意義でしたが、第4問以降は単なる数学パズルの色合いが濃く、学習という観点ではそこまで得るものはなかったのかもしれません。ただ、数学パズルやCTFの練習問題としては結構楽しかったと感じています。

Write up(ネタバレ注意)

復習、忘備録を兼ねてここに解法を残して置こうと思います。ここから先はネタバレが含まれているため、自力で解きたい方は読まないようにお願いします。

実のところ問題作成者はネタバレ非推奨と発言しているため、ここに解法を書くのはあまり褒められた行為ではないのかもしれません。しかし、curlコマンドの使い方等の技術的な知識は、

  1. 「未知の知識が必要な場面が生じる」
  2. 「使い方を調査する≒答えを見る」
  3. 「実際に使う」
  4. 「次回以降マニュアルを見ずに使えるようになる」

というプロセスを踏んで覚えるものであると私は思います。3の後に後戻りせず4に到達できるのであれば、2で閲覧する答えが解説書であっても、info curlの出力であっても、本記事のネタバレであっても本日的には変わらないのでは?むしろ、答えが参照しやすくなっている方が2の段階でつまずくことがなくなっていいのでは?という考えからここに解法を載せることにしました(一応ボタンを押さないと表示されないようにはしておきます)。

解説はHTTP通信などをほとんど知らない人が読んでもふんわりと理解できる程度には詳しく書くように心がけました。解いているうちに詰まってしまったら読んでみるのもいいのかもしれません。curlの使用例を知りたいという人も解説を見ながら第1問を解いてみるのもいいかもしれません。

第1問

第2問

第2問以降は暇があったら書きます(第1問程度の文量で書くと結構長くなりそうなので)。

*1:○○なら誰でもできるっていう釣りタイトル個人的にはきらい

AWS Lambdaを使ってAmazonコインを安く買う

先日AWS Lambdaを初めて使ったので忘備録を兼ねて書きます

今回書いたコードはここで見れます

Amazonコインの価格変動

1年ぐらい前からHearthstoneというデジタルカードゲームにハマっています。 Hearthstoneは課金でカードパックを買えるのですが、Amazonアプリストア版のAndroidアプリを使用すると、Amazonコインでの支払いが可能で、クレジットカードで直接買うよりより少し安くなります。

そんなAmazonコインですが、実は日々値段が変動しているみたいです。

Amazonコインの価格の変動・推移を調べてみる2018-2 | JJゃもの部屋 \(^o^)/ 破滅に向かって2011

↑の記事を見た感じ、10000コインが8100円のときにまとめ買いしておくとおトクなようです。

Amazonコインが安い日を見逃さないために、今回はpythonでwebスクレイピングを行いコインの価格を自動で追跡するスクリプトを作成しました。また、そのスクリプトAWS Lambdaで自動化しました。

Amazonコインの価格を自動で取得する

PythonAmazonコインの価格を追うスクリプトを書きました。

まず、venvを用いて仮想環境を作成し、必要となるライブラリをインストールします。

$ python3 -m venv amazoncoin
$ cd amazoncoin
$ source bin/activate # bash zsh等の場合
$ source bin/activate.fish # fish shellの場合
(amazoncoin)$ pip install requests beautifulsoup4
(amazoncoin)$ pip freeze > requirements.txt #必要なライブラリを書き出しておく(あとで使う)

10000Amazonコインの販売ページは https://www.amazon.co.jp/dp/B00KQVXDW0/ であり、価格はid=priceblock_ourpricespanタグに記載されているので、以下のようなスクリプトで価格を取得できます。*1

import requests
from bs4 import BeautifulSoup

def find_price():
    coin_url = "https://www.amazon.co.jp/dp/B00KQVXDW0/"

    resp = requests.get(coin_url, timeout=1)
    soup = BeautifulSoup(resp.text, 'html.parser')
    target = soup.findAll('span',{'id':"priceblock_ourprice"})
    return int(target[0].text[2:].replace(',', ''))

print(find_price())#=> 8100など

価格をLine Notifyで通知する

次に、取得した価格をLine Notifyを使って自分のLINEアカウントに通知することにしました。 [参考] https://qiita.com/hiro-abe/items/e42f857bd6b40bc178a3

下準備として、LINE Notifyのwebページでアクセストークンを取得し、環境変数LINE_NOTIFY_TOKENに値を書き入れておきます。

$ export LINE_NOTIFY_TOKEN=XXXXXXXXX # bash zsh等の場合
$ set -x LINE_NOTIFY_TOKEN XXXXXXXXX # fishの場合

そして、以下のスクリプトを実行するとLINEに通知が届きます。

import requests
from bs4 import BeautifulSoup
import os

def lambda_handler(event, context):

    output_url = "https://notify-api.line.me/api/notify"
    token = os.getenv("LINE_NOTIFY_TOKEN", "")
    
    price = find_price()
    headers = {"Authorization" : "Bearer "+ token}
    message =  '現在10000 Amazonコインは' + str(price) + '円です'
    payload = {"message" :  message}
    
    r = requests.post(output_url ,headers = headers ,params=payload)
    
    
    return 'Notify Amazon Coin Price is running'

lambda_handler(None, None) # => LINEの指定したトークルームに通知が来る

これで、script.lambda_handler関数を実行することで、Amazonコインの価格がLINEに届くようになりました。

AWS Lambdaで毎日自動で動かす

上記のスクリプトをASW Lambdaを用いて自動化します。 Lambdaを用いて自動化します。今回は毎朝8時に実行させるようにします。

スクリプトのパッケージ化

最初に作成したスクリプトをzipにまとめます。Lambdaは使用するスクリプトをzip形式でアップロードする方式になっているためです。*2 このとき注意しなければならないのは、標準ライブラリ以外のライブラリも一緒にzipにまとめる必要がある点です。

デプロイ用のディレクトリを作成し、そこに今回のスクリプトとライブラリをすべて設置し、zipにまとめることにします。

mkdir deploy #デプロイ用ディレクトリを作成
cp script.py deploy #今回作ったスクリプトをデプロイ用ディレクトリにコピー
pip3 install -r requirements.txt -t deploy/ #-tオプションでデプロイ用ディレクトリにライブラリをインストール
cd deploy/
zip -r package.zip * #パッケージを作成
mv package.zip ../

これで、作業ディレクトリにpackage.zipが作成されます。 動作確認として、以下のようなコマンドを実行したらスクリプトが正しく動作することを確認してください。

(amazoncoin) $ deactivate #仮想環境が有効になっている場合のみ
$ cd deploy/
$ python3 -c "import script;script.lambda_handler(None, None)"
# > Notify Amazon Coin Price is running
# (LINEに通知が来る)

AWS Lambdaの設定

パッケージが完成したので、早速Lambdaのセッティングをしてみます。

まず、Lambdaの管理ページから新しい関数を作成します。 ロールは「テンプレートから新しいロールを作成」を選択し、「Basic Edge Lambdaアクセス権限」を使用します。他は適当に入力してかまいません。 f:id:pf_siedler:20180415133028p:plain

次に、先程作成したpackage.zipをLambdaにアップロードします。 このとき、ハンドラには[pythonのファイル名].lambda_handlerを指定します。 f:id:pf_siedler:20180415133042p:plain

そして、環境変数の欄にLINE Notifyのアクセストークンを入力します。 f:id:pf_siedler:20180415133023p:plain

最後にタイムアウトの値を少し大きめの値に変更しておきます。*3メモリは最小の128mbで足りるのでデフォルトのままでかまいません。 f:id:pf_siedler:20180415133036p:plain

イベントタイミングの指定

次に通知が来るタイミングを指定します。 トリガーにCloudWatch Eventsを指定します。 ルール名と説明は適当に埋め、ルールタイプを「スケジュール式」、 スケジュール式をcron(0 23 * * ? *)を指定します。

f:id:pf_siedler:20180415133315p:plain

これで毎日グリニッジ標準時の23時、つまり日本時間の8時にスクリプトが実行されるようになりました。

おわりに

今回はpythonを用いてwebスクレイピングと、AWS Lambdaによる自動化を行いました。

今回、個人的につまずいた点は以下のとおりです。

  • ライブラリをzipに含めないとライブラリの関数が使えない点*4
  • イベントのトリガーに何を選べばいいのかわからない点

今後の課題として、価格がn円以下のときのみ通知を流すようにしたり、TwitterやDiscordに自動投稿させたりなんかをやりたいと思っています。

今回のプロジェクトはこちらのリポジトリで管理してあります。よかったらforkしてみてください。また、改善点などあればissueに書いてくださると助かります。

*1:後々、価格がn円以下なら通知するといった条件分岐をしやすくするために結果をint型で返すようにした

*2:一応、webページで直接コードを書く機能もある。zipでうpしたファイルをweb上で微修正するということも可能。

*3:今回のスクリプト実行には4秒ぐらいかかる場合があり、デフォルトの3秒ではタイムアウトが生じる場合がある

*4:もしかしたら、これを自動でやってくれるソフトがあるのかもしれないが見つからなかった

東京大学eeic3年後期実験「大規模ソフトウェアを手探る」2016年度まとめ

東大生がOSS開発やってみた…みたいな記事

「大規模ソフトウェアを手探る」って?

大規模ソフトウェアを手探る

「大規模ソフトウェアを手探る」は、東京大学工学部電気電子/電子情報工学科(eeic)で開講されている、学部3年生向けの実験科目です。

ネット上に公開されているOSSオープンソース・ソフトウェア)をひとつ選んで、それを改造するという内容の講義です。

2~3人でチームを組んで、数万〜数十万行のプログラムに体当たりで改造を試みることで、以下のようなことを体験するのがこの講義の狙いです。

  • 全容を把握できない程度に大きなプログラムを扱う
  • 他人が書いたコードに触れる
  • デバッガの扱い方を学ぶ
  • 先生やTA、他の学生からフィードバックをもらい、それを開発に活かす
  • チームでの開発を体験する

また、この実験では、成果物をブログ形式で公開することで、レポートの代替として認められています。 ネット上には「インストールしてみた」「ライブラリを使ってみた」系の記事がたくさんあり、後を追う誰かの助けになっています。 我々が実験を通して得た知見も、誰かの役に立つのではないか?ということで、ブログ形式のレポートを認めているようです。

この記事では、そんなレポートの数々を一覧にしてみました。

OSS開発に興味がある方、学科選びに悩んでいる一二年生、そしてどの実験を受講しようか迷っている未来のeeic民の一助となれば幸いです。

目次


連載形式の記事については、初回あるいは目次のページを取り上げています。

コンパイラ・言語

gcc

結局なにをどう変更したのか(まとめ) - 27++'s Report

内容

  • 生成ファイルに自動で名前を付ける
  • 末尾の;を補完する

Python その1

Python3.x系でprint命令文を追加する話. - Qiita

Pythonにプライベート変数を実装しようと試みた話。 - Qiita

内容

  • Python3.x系でもprint文を使えるようにする
  • private変数を実装する

Python その2

Pythonを改造してみた はじめに - 開拓馬’s blog

内容

テキストエディタ

Vim

Vimにnanoみたいなコマンドチートシートを表示した話 - チョコの包み紙の裏

内容

nano

nanoを手探ってみる#1: ビルドする - meloidae’s blog

内容

  • tabキーでファイル名を補完する
  • 起動後でもnanorcのリロードをできるようにする
  • 雪を降らせる

ブラウザ

FireFox

大規模ソフトウェアを手探る Firefox - Qiita

内容

  • url欄の文字を隠す
  • 右クリックからタブの複製を行う
  • 新規タブを開くとクリップボードの内容を自動で検索する
  • タブを複数選択して一気に閉じる機能を付ける

Chromium

Chromiumを手探った#1 - Chromiumをビルドしよう - しゅわしゅわdedede。

内容

  • 新規タブで表示されるページをユーザが設定できるようにする

OpenTween

OpenTweenを手探ってみた#1 - Qiita

OpenTween 目次 : トルネード一門計算機室

内容

  • お気に入り一覧を登録順にする
  • 同内容のつぶやき(パクツイ)を検索する
  • フォロー/フォロワーの変化を可視化する
  • 時間制限付きのミュート機能を追加する

ユーティリティ

Libre Office

LibreOfficeを手探る - libsoft’s blog

内容

  • spaceを入力すると下付き文字モードが解除されるようにする

Rhythmbox

Rhythmboxで1曲ループを実現する −0− - かるぅあみるく(仮)

内容

  • 一曲ループ機能を追加する

GIMP

GIMPの履歴機能に制限を加えてみた - team-cの日記

内容

  • 変更履歴の数が増えすぎてフリーズする問題を防ぐ

まとめは以上になります。

昨年度にこの講義を受講されたid:SWIMATH2さんが、15年度のまとめ記事を作成してくださっています。

東京大学eeic3年後期実験「大規模ソフトウェアを手探る」2015年度まとめ - クフでダローバルな日記

こちら記事に「来年以降のeeicの後輩たちがまたまとめてくれるのを楽しみにしています。」とあったので、大変僭越ながら便乗させていただきました。

17年度以降も、後輩たちがまとめてくれるのを楽しみにしています。

Mac bookにBasicTeXを導入してみた

先日Mac BookのOSを再インストールしたのでTeXを入れ直し、ついでにLuaLaTeXに乗り換えた話をします。

BasicTeXを入れる

Mac用のTeX環境として、MacTeXというものがあります。 とりあえずこれをインストールすればMacTeXが使えるようになるのですが、インストーラのサイズが2.8Gもあり、ダウンロードに1時間程度かかって面倒です。 そのうえあまり使わないGUIアプリがついてきてLaunchpadが汚染されます。 *1

私の場合、Emacsのorg-modeやPandocを使ってMarkdownTeXに変換するのが主な利用法なので最低限のコマンドが使えれば十分です。

そこで最小限の機能だけ持ったBasicTeXを入れることにしました。

MacTeXのサイトからBasicTeX.pkgをダウンロードします。 BasicTeX.pkgを起動しインストーラの指示に従ってインストールします。

インストールが完了すると/usr/local/texlive/2016bacis(数字はバージョンによって異なる)というディレクトリが作成されます。 *2

必要なパッケージを入れる

BasicTeXは本当に最小限で日本語環境が使えないので必要なパッケージを入れます。

ターミナルで以下のコマンドを実行します。

% sudo tlmgr update --self —all
% sudo tlmgr install collection-langjapanese

ちなみにtlmgrはTeXLive managerの略だそうです。 *3

collection-langjapaneseにはluatex-jaというパッケージが入っており、LuaTeXを日本語で使えるようになります。

ghostscriptImageMagickを入れる

次にghostscriptImageMagickをインストールします。これらは画像処理やpdf関連の処理を行うプログラムで、TeXをpdfに出力する際に使われるそうです。

brew install ghostscript
brew install imagemagick

インストールにはhomebrewを使用しました。「homebrewって何?」「brewコマンドが使えない」って人は"homebrew"で検索してみてください。

LuaLaTeXで書いてみた

LuaTeXの詳細はTeX Wikiの説明に丸投げします。ざっくりまとめるとLuaというプログラミング言語LaTeXを混ぜたシステムです。

フォントの指定がわりと楽にできたり、Unicode文字に対応していたりとLaTeXより便利な点がいくつかあるのですが、 一番の利点はdviファイルを経由せずにpdf出力ができる点です。 *4

% platex report.tex
% dvipdf report.dvi
    #LaTeXではこんな感じにやっていたのが

% lualatex report
    #LuaTeXだとこれでOK

とりあえずluatex-ja Wikiにあるサンプルを出力してみました。

\documentclass{ltjsarticle}
\usepackage{luatexja} % ltjclasses, ltjsclasses を使うときはこの行不要
\begin{document}
\section{はじめてのLua\TeX-ja}
ちゃんと日本語が出るかな?
\subsection{出たかな?}
長い文章を入力するとちゃんと右端のところで折り返されるかな?
大丈夫そうな気がするけど.ちょっと不安だけど何事も挑戦だよね.
\end{document}

上記をtest.texの名称で保存しpdf出力してみます。

% lualatex test.tex
  :
  :
! LaTex Error: File `filehook.sty’ not found.

どうやらfilehook.styが必要なのにインストールされていないのでエラーが発生したようです。tlmgrを使ってfilehookをインストールします。

% sudo tlmgr install filehook

これに限らず、hoge.sty not found.というエラーが発生した場合、sudo tlmgr install hogeでスタイルファイルをインストールする必要があります。

何度か「実行」→「エラー」→「スタイルファイルを入れる」を繰り返すと出力が成功します。

f:id:pf_siedler:20161123141357p:plain

画像が表示されない場合

以降はLuaTeXを使い始めたばかりのときに躓いた部分を紹介します。同じような失敗をしている人の参考になれば幸いです。

LaTeXで画像を使用する場合、ヘッダ部分に

\usepackage[dvipdfmx]{graphicx}

と記述します。

一方でLuaLaTeXで画像を使用する場合、ドライバ指定オプションは不要です。

\usepackage{graphicx} %LuaTeXではこう

ここでドライバ指定を付けたまま出力すると、画像の部分が白抜き状態になります。

\documentclass{ltjsarticle}
\usepackage{luatexja}
\usepackage{graphicx} %[dvipdfmx]は不要
\begin{document}
\section{はじめてのLua\TeX-ja}
ちゃんと画像が出るかな?

\begin{figure}[h]
  \includegraphics[width=10cm]{test.jpg}
  \caption{Lenna}
\end{figure}
\end{document}

f:id:pf_siedler:20161123141531p:plain

オプションを付けたままだとこんな感じ

f:id:pf_siedler:20161123141509p:plain

筆者はネットから拾ってきたLaTeXのサンプルコードを何も考えずにコピペした結果、この症状に見舞われ数時間無駄にしました。

脳死コピペ、ダメゼッタイ

*1:個人の感想です。TeXShopは人によっては便利かも

*2:フルパッケージのMacTeXの場合、ディレクトリがtexlive/2016のように数字のみになる。MacTeX関連の記事を読む場合、2016→2016bacisと読み替える必要がある

*3:こういう略語の元の言葉を覚えておくとコマンドを暗記しやすい気がする

*4:pdf直接出力はLuaLaTeXの派生元であるpdfTeXで実装された機能です。pdfTeXは国内ではマイナーですが、海外ではよく使われているそうです。

Pythonを改造してみた プロンプトをうるさくしてみた

前回まではPythonに新たな予約語を追加してきました。Pythonは与えられたコードをASTなどの中間データに変換しながら、最終的には擬似的なバイトコードを生成しceval.cで処理するという方式を取っていることがわかりました。

しかし、この記事では文法関係の話はまったくしません。というのも、Python改造に取り組むきっかけとなった講義でgdbの使い方を習ったのですが、私達はデバッガまったく使わずにここまでの改変をやってきたのです。せっかくなのでデバッガを使ってコードを読み解きたいと思います。

gdbPythonを追う

ビルドまでの経緯はこちら

Emacs上でM-x gud-gdbを入力しデバッガを起動します。 mainブレークポイントを置いて引数を入れずに(つまりインタラクティブモードが起動するはず)runします。 すると、Programs/python.cが開きました。

そのままnextstepを連打していくと、おおよそ、以下のような動きをすることがわかりました。

  1. Modules/main.cに移動し、各種初期化処理を行う
  2. Python/getopt.c内のサブルーチンでオプションを受け取る
  3. main.cに戻り、オプションに従ってフラグを切り替える
  4. 引数からソースコードの名前を取得、存在しない場合、インタラクティブモードを開始するフラグを建てる
  5. Python/pythonrun.cIntaractiveloop()関数に来る
  6. プロンプト">>> "が表示される

上記の流れを見た上で、やることを決めました。

メッセージの書き換え

Pythonをファイル名を指定せずに実行すると、インタラクティブモードが起動します。インタラクティブモードを終了したい場合は、ctrl+Dを入力するか、exit()関数、またはquit()関数を実行する必要があります。この仕様がちょっと不親切で終了しようとしてexitと入力するとUse exit() or Ctrl-D (i.e. EOF) to exitと表示され、終了してくれません。 *1

exitと入力すれば終了できるようにするのは複雑な例外処理を行う必要がありそうなので仕方ないのかもしれません。しかし、終了の仕方を説明していないのも不親切だと私は思います。「消し方が分からない、やめ方が分からない」ソフトはユーザーをイライラされるものだと思います。

そこで、Python起動時に表示されるメッセージに「exit()quit()と入力すると終了できます」という説明文を付け足すことにしました。

サクッと完成

grepで該当部分の起動時のメッセージを検索したところ、main.c内でそれらしい文字列が#defineされているのを発見。書き換えます。

#define COPYRIGHT \
    "Type \"help()\", \"copyright\", \"credits\" or \"license()\" " \
    "for more information.\nType \"exit()\" or \"quit()\" or Ctrl-D to exit."

ついでに、"help"、"license"の後ろに括弧を付けました。 *2 ビルドして実行したところ、メッセージが変化しました。

% ~/mypython/bin/python3
Python 3.5.2 (<<略>>)
[GCC 4.8.4] on linux
Type "help()", "copyright", "credits" or "license()" for more information.
Type "exit()" or "quit()" or Ctrl-D to exit.
>>>

ほんとにちょっとした変更ですが、多少は使いやすくなったのかな……?

オプションを追加 おもしろ機能

-a--hogeのようなハイフンから始まるオプションはCUIアプリにとって欠かせないものです。 オプションを受け取る部分の処理はgetopt.cようなので、ちょっと書き足して新しい予約語を足してみようと思います。

それでは追加するオプションにはどんな機能を付けましょうか。先程と同じ文字列の変更なら簡単にできそうです。プロンプトの">>> "を適当に他の記号に変えてみることにしました。

そんなわけで、Pythonの名前にちなんで--spamオプションを付けるとプロンプトが">>> "から"SPAM>> "に変わるという機能を作ってみることにしました。 *3

spamオプションの追加

getopt.c--spamオプション用の処理部分を追加します。ハイフン2つ+単語のオプションには--help--versionが存在するので、それを真似します。

else if (wcscmp(argv[_PyOS_optind], L"--version") == 0) {
    ++_PyOS_optind;
    return 'V';
}

#if SPAM_MODE
else if (wcscmp(argv[_PyOS_optind], L"--spam") == 0) {
    ++_PyOS_optind;
    return 'P';
}
#endif

ヘルプ表示、バージョン表示は-h -Vでもできます。どうやら--helpを受け取った場合、内部で-hに変換するという方式を取っているようなのでspamにもアルファベット一字のオプションを割り当てることにします。spamの頭文字である-s-Sはすでに使われているのでs"p"amの-Pを割り当てました。

ビルドして実行したところ、--spamオプションを付けても"Unknown option"エラーが発生しませんでした。

% ~/mypython/bin/python3 --hoge #存在しないオプションを付けるとエラーを起こす
Unknown option: --
<<略>>

% ~/mypython/bin/python3 --spam #普通に起動した
Python 3.5.2 (<<略>>)
[GCC 4.8.4] on linux
<<略>>

% ~/mypython/bin/python3 -P #普通に起動した
Python 3.5.2 (<<略>>)
[GCC 4.8.4] on linux
<<略>>

spamモードの追加

main.c--spamオプションを受け取ったときの処理を付け加えます。プロンプトの表示はPython/pythonrun.cで行われるのでspamフラグが立ったことを伝えなければなりません。とりあえずグローバル領域でフラグ変数を定義して伝えることにしました。

/* command line options */
#if SPAM_MODE
#define BASE_OPTS L"bBc:dEhiIJm:OqRsStuvVPW:xX:?"
int Active_spam_mode = 0;
#else
#define BASE_OPTS L"bBc:dEhiIJm:OqRsStuvVW:xX:?"
#endif
      :
      :
      while ((c = _PyOS_GetOpt(argc, argv, PROGRAM_OPTS)) != EOF) {
          if (c == 'c') {
      :
          switch(c){
      :

              case 'V':
                  version++;
                  break;
              case 'P':
                  Active_spam_mode++;
                  break;

pythonrun.cPyUnicode_FromString()関数の引数に">>> "という文字列を与えているのを発見。適当に他の文字列にしてビルドしてみるとプロンプトが変わりました。どうやらこの部分でプロンプトの文字を定義しているようなので、フラグが立っているときだけ"SPAM>> "を与えるように変更します。

#if SPAM_MODE
extern int Active_spam_mode;//main.cで定義したグローバル変数をextern

char* spam_message()//あとで拡張できるように関数にしておく
{
    return "SPAM>> ";
}
#endif
      :
      :
#if SPAM_MODE
      if(Active_spam_mode) {
      _PySys_SetObjectId(&PyId_ps1, v = PyUnicode_FromString(spam_message()));
      }
      else {
        _PySys_SetObjectId(&PyId_ps1, v = PyUnicode_FromString(">>> "));
      }
#else
        _PySys_SetObjectId(&PyId_ps1, v = PyUnicode_FromString(">>> "));
#endif

実行してみます。

% ~/mypython/bin/python3
Python 3.5.2 (<<略>>)
[GCC 4.8.4] on linux
<<略>>
>>>

% ~/mypython/bin/python3 --spam
Python 3.5.2 (<<略>>)
[GCC 4.8.4] on linux
<<略>>
SPAM>> print("やったぜ。")
やったぜ。
SPAM>>

プロンプトがが変わりました!spamモード実装完了です!

文字列をランダムに表示させる

ただプロンプトが変わるだけでは物足りないので、複数パターンのプロンプトがランダムに表示されるように変更してみます。

どうやら標準ライブラリをインクルードしても問題なくビルドできるようなのでstdlib.htime.hを用いた一番簡単な乱数生成を使うことにします。 *4

プロンプトのレパートリーは適当に5~6個用意しました。

//time.h stdlib.hのインクルード
#if SPAM_MODE
#include <stdlib.h>
#include <time.h>
#endif

#if SPAM_MODE
extern int Active_spam_mode;

char* spam_message()
{
  int c;
  static int f;
  if(!f){
    f = 1;
    srand((unsigned int)time(NULL));
  }

  c = (int)random()%10;
  switch(c){
  case 0:
  case 1:
    return "  _____ _____        __  __ \n / ____|  __ \\ /\\   |  \\/  |\n| (___ | |__) /  \\  | \\  / |\n \\___ \\|  ___/ /\\ \\ | |\\/| |\n ____) | |  / ____ \\| |  | |\n|_____/|_| /_/    \\_\\_|  |_>> ";  
  case 2:
  case 3:
  case 4:
    return "spam>> ";
  case 5:
  case 6:
    return "SPAM>> ";
  case 7:
    return "\n\n _____ _   _ _____  ___  ________ _   _ _   _ \n|_   _| | | |  ___| |  \\/  |  ___| \\ | | | | |\n  | | | |_| | |__   | .  . | |__ |  \\| | | | |\n  | | |  _  |  __|  | |\\/| |  __|| . ` | | | |\n  | | | | | | |___  | |  | | |___| |\\  | |_| |\n  \\_/ \\_| |_\\____/  \\_|  |_\\____/\\_| \\_/\\___/\n==============================================\n\n1.egg bacon and spam\n2.egg bacon sausage and spam\n3.spam bacon sausage and spam\n4. ";
  case 8:
    return "\\(^o^)/SPAM\\(^o^)/SPAM\\(^o^)/>> ";
  case 9:
    return "Nobody expects the Spanish Inquisition!\nOur two weapons are fear and surprise...and ruthless efficiency...\nOur THREE weapons are fear, surprise... ";
  default:
    return ">>> ";
  }
}
#endif

プロンプトがうるさいインタラクティブモード

ビルドして実行してみました。

f:id:pf_siedler:20161106171817p:plain
こんな感じでプロンプトがうるさくなります f:id:pf_siedler:20161106171821p:plain
スパムのスケッチに登場する食堂、メニューを書き足してみようみたいなイメージ f:id:pf_siedler:20161106171825p:plain
もはやスパムとは無関係なネタ、スペイン宗教裁判も

実は乱数の初期化がうまく行っておらず毎回同じ順番でプロンプトが登場したり、Macだとアスキーアートが崩れたり、粗がありますが完成ということで……

*1:おそらくexitやquitのreprあるいはstrの戻り値を"Use ~ to exit"にしているのだと思われる

*2:説明通りに"help"や"license"と入力すると"Type help()"というメッセージとともに関数の使い方が説明される

*3:モンティ・パイソンというコメディグループのネタ。ちなみにPythonの公式ドキュメントにもメタ構文変数としてspamが登場する

*4:stdlib.hの擬似乱数は性能がよくないので使用を控えるべきという意見もあるが、今回は乱数が偏ってもあまり問題にならないので使うことにした

Pythonを改造してみた 排他的論理のブール演算子作った

Pythonでは、ブール演算で排他的論理を表現する場合、以下のような書き方があります。*1

#and or not演算子を組み合わせて記述
a and not b or not a and b
#bool()関数の返り値が不一致であるか判定する
bool(a) != bool(b)
#operatorモジュール使用
from operator import xor
xor(a, b)

しかし、これらの記法は一見どのような演算をやっているのかわかりづらいです。また三項以上への拡張性も。よろしくありません。

andorのようにa exor bと記述すれば排他的論理をを計算してくれる演算子があれば、コードの可読性が向上しそうです。 そこで今回はPythonコンパイラを改造して、排他的論理和演算子exorを実装してみました。

文法の追加

ビルドまでの経緯はこちら

Grammar/GrammarPaser/Python.asdlから、andorが記述されている部分を探し出し、exorの処理を新たに追加します。

# #if EXOR_TEST

test: exor_test ['if' exor_test 'else' test] | lambdef
test_nocond: exor_test | lambdef_nocond
lambdef: 'lambda' [varargslist] ':' test
lambdef_nocond: 'lambda' [varargslist] ':' test_nocond

# #if EXOR_TEST
exor_test: or_test ('exor' or_test)*
or_test: and_test ('or' and_test)*
and_test: not_test ('and' not_test)*
not_test: 'not' not_test | comparison
comparison: expr (comp_op expr)*

どうやらこの部分でandornotの優先順位を決めているようです。今回はexororより優先順位が低いという設定にしました。全体の優先順位は
not > and > or > exor
になります。

Python.asdlの変更は以下の一行だけ。ブール演算子の種類にexorを付け加えます。

    boolop = And | Or | Exor

astの書き換え

Python/ast.cand/orの真似をするだけです。

#if EXOR_TEST//変更後のコード
        case exor_test:
        case or_test:
        case and_test:

          :
          :

            if (!strcmp(STR(CHILD(n, 1)), "and"))
                return BoolOp(And, seq, LINENO(n), n->n_col_offset,
                              c->c_arena);
        if (!strcmp(STR(CHILD(n, 1)), "exor"))
                return BoolOp(Exor, seq, LINENO(n), n->n_col_offset,
                                    c->c_arena);
            assert(!strcmp(STR(CHILD(n, 1)), "or"));
            return BoolOp(Or, seq, LINENO(n), n->n_col_offset, c->c_arena);
#else//もとのコード
        case or_test:
        case and_test:

          :
          :

            if (!strcmp(STR(CHILD(n, 1)), "and"))
                return BoolOp(And, seq, LINENO(n), n->n_col_offset,
                              c->c_arena);
            assert(!strcmp(STR(CHILD(n, 1)), "or"));
            return BoolOp(Or, seq, LINENO(n), n->n_col_offset, c->c_arena);
#endif

Python/symtable.cにはブール演算子特有の処理がひとつもなかったので書き換える場所はありませんでした。

コンパイラ

肝心のコンパイラ部分の書き換えです。exorand/orよりずっと複雑な処理が必要なのでexor使用時にコンパイラが生成するコードを自分で作る必要がありました。

and/orが動く仕組み

Pythoncompile.cで作成した擬似的な機械語Python/ceval.cが処理するという動きで動作しています。 プログラムの処理中に一時的に使用するデータは、一時的にFILO形式のスタック領域にロードされて処理されます。

例えばa + bの処理をする場合、

  1. aをスタックに格納
  2. bをスタックに格納
  3. スタックの先頭から2つのデータを削除し、和をスタックに格納

という順序で処理されます。 Pythonが内部で生成している擬似的なオペコードはdisモジュールを用いることで見ることができます。

>>> import dis
>>> def f(a, b):
...     a + b
...
>>> dis.dis(f)
  2           0 LOAD_FAST                0 (a)#aをスタックに格納
              3 LOAD_FAST                1 (b)#bをスタックに格納
              6 BINARY_ADD      #ススタックの先頭から2つのデータを削除し、和をスタックに格納
              7 POP_TOP             
              8 LOAD_CONST               0 (None)
             11 RETURN_VALUE        
>>>

and/orの場合はどのようになっているかというと、例としてa and bの場合、

  1. aをスタックに格納
  2. スタック先頭の真偽値を参照し真ならスタックの先頭を削除、偽なら4にジャンプ
  3. bをスタックに格納
  4. 次の処理

と処理されます。*2

>>> import dis
>>> def f(a, b):
...     a and b
...
>>> dis.dis(f)
  2           0 LOAD_FAST                0 (a)#aをスタックに格納
              3 JUMP_IF_FALSE_OR_POP     9 #スタック先頭の真偽値を参照し、真ならスタックの先頭を削除、偽ならジャンプ
              6 LOAD_FAST                1 (b)#bをスタックに格納
        >>    9 POP_TOP         #次の処理(今回は関数を終える処理)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE        
>>>

この時、「4.次の処理」の行でスタックの先頭はaかbのどちらかなのですが、その真偽値は論理積の真偽値と一致しています(真偽値表などを書いて確認してみてください)。 なぜ、ブール型(TrueFalse)ではなくa、bの値をそのまま使うのかというと、「スタックの先頭を削除してTrue/Falseをスタックに格納」という処理を省略して処理を早めるためだと思われます。 思わぬところでバグが生じそうな気もしますが……

http://qiita.com/keisuke-nakata/items/e0598b2c13807f102469

この仕様は、a1 and a2 and a3 ...のように複数の演算子が複数並ぶ場合に、最初の方で偽の値を見つけたら、後半の多くを確認することなく結果が得られるのでかなりの時間短縮が見込めます。

排他的論理和は根本的に別物

先程「exorand/orよりずっと複雑」と述べました。それは exorは絶対に全部の式を判定しなければならない ので、andorのように 場合によっては後半の値を確認しない 演算と根本的に異なるということです。これまでのように他の部分を真似るのではなく、自分で実装を考える必要があります。

とりあえず、exorは専用の関数を用意して処理することにしました。

//compile.c
static int
compiler_visit_expr(struct compiler *c, expr_ty e)
{
      :
      :

    switch (e->kind) {
    case BoolOp_kind://
#if EXOR_TEST
      if(e->v.BoolOp.op == Exor)
           return compiler_exor(c, e);//exorだけ別の処理を行う
#endif
         return compiler_boolop(c, e);//and/orはどちらもこの関数で処理される
      :
      :

内部の処理はどうしましょうか。例えば、a exor bの場合、とりあえず「aをスタックに格納」→「bをスタックに格納」という処理は必要そうです。 Pythonの既存のオペコードには、POP_JUMP_IF_FALSEというものが存在します。これは「スタック先頭の真偽値を参照し、真ならジャンプ。真偽にかかわらずスタック先頭のデータは消す」という処理を行います。 またUNARY_NOTというオペコードもあります。これは「スタック先頭の真偽値を反転」という処理です。*3 また、UNARY_NOTで反転された値はブール型に変換されます。

>>> not 0.000 #もとが数値や
True
>>> not "A" #文字列でも結果はブール型になる
False
>>>

POP_JUMP_IF_FALSEUNARY_NOTを組み合わせればexorを実現できそうです。 a exor b exor c exor ...の場合、

  1. aをスタックに格納
  2. bをスタックに格納
  3. スタック先頭の真偽値を参照し、真なら4にジャンプ。真偽にかかわらずスタック先頭のデータは消す
  4. スタック先頭の真偽値を反転
  5. cをスタックに格納
  6. スタック先頭の真偽値を参照し、真なら4にジャンプ。真偽にかかわらずスタック先頭のデータは消す
  7. スタック先頭の真偽値を反転
  8. 以下繰り返し

という順番に処理を行えば排他的論理和の計算ができます。ちょうど下図のように式を変形していくイメージです。 f:id:pf_siedler:20161105140248p:plain *4

試行錯誤の結果以下のようなコードを作成しました。

#if EXOR_TEST
static int
compiler_exor(struct compiler *c, expr_ty e)
{
    basicblock **buf, *end;
    Py_ssize_t i, n;
    asdl_seq *s;

    assert(e->kind == BoolOp_kind);
    assert(e->v.BoolOp.op == Exor);
    end = compiler_new_block(c);
    s = e->v.BoolOp.values;
    n = asdl_seq_LEN(s) - 1;
    buf = (basicblock**)malloc(sizeof(basicblock*)*n);
    VISIT(c, expr, (expr_ty)asdl_seq_GET(s, 0));//「aをスタックに格納」に相当する処理
    assert(n >= 0);
    for (i = 1; i < n; ++i) {
        buf[i-1] = compiler_new_block(c);
        VISIT(c, expr, (expr_ty)asdl_seq_GET(s, i));//「bをスタックに格納」
    ADDOP_JABS(c, POP_JUMP_IF_FALSE, buf[i-1]);
    ADDOP(c, UNARY_NOT);
    compiler_use_next_block(c, buf[i-1]);
    }
    VISIT(c, expr, (expr_ty)asdl_seq_GET(s, n));
    buf[n-1] = compiler_new_block(c);
    ADDOP_JABS(c, POP_JUMP_IF_TRUE, buf[n-1]);
    ADDOP(c, UNARY_NOT);
    compiler_use_next_block(c, buf[n-1]);
    ADDOP(c, UNARY_NOT);
    compiler_use_next_block(c, end);
    return 1;
}
#endif

この実装だと、最初以外全部偽だった場合だけ最初の項の値がそのまま出力されてしまうので、 最後に一度は否定を挟むようにして、結果をブール型で統一してあります。速さは犠牲になりますが、わかりやすさを重視しました。

使ってみた

ビルドして実際にexor演算子を使ってみました。

>>> 1 exor 1
False
>>> 0 exor 1
True
>>> True exor 0
True
>>> False exor False
False

どうやらちゃんと動いているようです。

disassembleモジュールで分析した結果が以下になります。

>>> import dis
>>> def f(a, b, c):
...     a exor b exor c
...
>>> dis.dis(f)
  2           0 LOAD_FAST                0 (a)
              3 LOAD_FAST                1 (b)
              6 POP_JUMP_IF_FALSE       10
              9 UNARY_NOT
        >>   10 LOAD_FAST                2 (c)
             13 POP_JUMP_IF_TRUE        17
             16 UNARY_NOT
        >>   17 UNARY_NOT
             18 POP_TOP
             19 LOAD_CONST               0 (None)
             22 RETURN_VALUE

次は何やろう

本シリーズは講義のレポートも兼ねて執筆しています。その講義ですが、ちょうどexorの実装ができたところで終盤になり、残り時間も少なくなってきました。*5

講義中にgdbの使い方を教わったのに全く活用していないのは少し残念ですし、言語仕様以外も軽くいじってみたいという思いもありました。
そこで残り時間でPythonCUI部分をいじって--hogeみたいな新しいオプションとちょっとした機能の追加をやってみました。次回はその様子を説明します。

*1:ビット演算の排他的論理和とは別物です

*2:orなら、2行目の真偽が逆になります。これもa or bと同じ真偽値が得られます

*3:UNARY_NOTは本来not演算子を使ったときに使用される

*4:⊕は排他的論理和の記号

*5:講義は一回210分を10回、うち2回は開発以外のことをやるので、二人組で取り組んだ場合の開発時間は8回210分2人=7人日。また毎回講義中盤に進捗報告会をやるので、実際はさらに短いです。

Pythonを改造してみた はじめに

Pythonは実行時にソースコードから機械語を生成するインタプリタ型言語の一種です。この記事ではPythonがコードを実行する際に、内部でどのような処理を行っているのかを調査した結果を紹介します。

しかし、ただソースコードやドキュメントを読むだけでは面白くありません。また、Pythonオープンソースで誰でも自由にソースコードをいじることができます。なので「Pythonを改造して新しい予約語を追加する」という方法でインタプリタの仕組を追ってみることにしました。

このページではソースコードをダウンロードしてビルドする所までの様子をお伝えします。 実際に改造を行った部分の説明は以下の記事からご覧いただけます。

これらの記事は大規模ソフトウェアを手探るという大学の講義のレポートを兼ねています。

また、ソースコードをいじる作業やブログ記事の作成はブログ主(id:pf_siedler)ともう一名の学生の二人組で行いました。

環境

ビルド

Pythonの公式サイトからソースコード(tarball形式)をダウンロードして適当なディレクトリに展開します。 ターミナルでソースコードを展開したディレクトリに移動しconfigureを叩きます。ここで、デバッグを行いやすいように、CFLAGS-g -O0オプションを与えます((-gデバッグシンボルを付けるオプション。これを付けないとデバッガを使うことができない。-O0は最適化を行わないオプション。デバッグ時にソースコードがそのままの状態で読める。))。また、--prefixオプションでインストール先のディレクトリをホーム直下のmypythonディレクトリに指定します。

その後、makemake installを行いインストールを行いました。makeには-jオプションで複数のプロセッサを割り当て高速化しました。

% tar zxvf Python3.5.2

% cd Python3.5.2

% CFLAGS="-g -O0" ./configure --prefix=/home/(username)/mypython/

% make -j8

% make install

ビルドは問題なく完了しました。~/mypython/bin/python3を実行することでPythonを起動できます。

% ~/mypython/bin/python3
Python 3.5.2 (<<>>)
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

ドキュメントを読む

とりあえずビルドはできましたが、どこから手をつければいいかわかりません。そこでネットの記事を漁って情報を仕入れることにしました。 すると、昨年度の「大規模ソフトウェア」受講者にPythonを改造した方がいたので記事を読んでみると、Changing CPython’s Grammarなるガイドラインが紹介されていました。
この講義は「同じことをしようとしている誰かの役に立つため」に最終レポートをブログ形式で一般公開することを要求されているのですが、早速後輩の役に立つとは……

ガイドによると新しい予約語を追加する場合、おおよそ以下のような変更を加えればよいそうです。

  1. Grammar/Grammarをいじる(文法をの規定)
  2. Parser/Python.asdlをいじる(構文解析部分の自動生成に使うらしい?)
  3. Python/ast.cをいじる(AST生成)
  4. Python/symtable.c(をいじるASTに意味付けを行いコンパイラに渡す)
  5. Python/compile.cをいじる(コードに従ってバイトコードを生成)

後ろ3つはC言語のコードですが、GrammarPython.asdlは独特な記法で書かれていて大きな変更しづらそうです。また、C言語のファイル3つもマクロを使用して関数を呼び出しているので、既存のコードから大幅に外れた変更は難しそうです。

なので 既存の構文とほとんど同じ動きをする構文を追加する

慣れたら少し変わったことをする
という順序で開発を行っていくことにしました。

参考資料

Python公式ページ
Developer's Guideの23. Changing CPython’s Grammarに文法を変更する手順が記載されています。

大規模ソフトウェアを手探る
この記事を書くきっかけとなった大学の講義ページです。

CPythonに後置インクリメントを加えてみた
昨年度の大規模ソフトウェアを手探る受講者の方が書いたページです。Pythonのディベロッパーズガイドはこの記事を読んで知りました。

Python internals: adding a new statement to Python
「Pythonにuntil文を追加してみた」という内容の記事です。とても参考になりました。

dis/inspect モジュールを使った Python のハッキング
disassembleモジュール等を使ってPythonの言語仕様を解析する内容の記事です