Hash λ Bye

Haskell, Clojure, MLなどの話

『入門 監視』読んだ

『入門 監視』 という本を読んだ。 普段は低レベルな部分の監視が多くて見失いがちだった、高レベルなポイントの監視について思いを馳せる機会を与えてもらったので読んでよかった。

以下、個人的に心の動いたポイントを記す。 本の内容については大して触れていないので、本書の内容そのものが知りたい人は読むしかない。

p.12 1.3.2 アラートに関しては、OSのメトリクスはあまり意味がない

体感としてもOSメトリクス自体にアラートつけて意味のあるアラート出せたことそんなに無かった。 監視を始めるにあたっていきなりこのOSメトリクスから取り組んでアラートを設定すると疲弊しそう。

メトリクス自体はとってもよい。 しかしトラブルが起きた時の解析材料としてのみ有用だと考えた方がよい。 OSから収集できるロードアベレージやメモリ使用率などが上昇したからといって、 必ずしもサービスに影響を与えるとは限らないことがある。 これに対してアラートを発することは、無駄なアラートの原因にもなる。 そのためメトリクス自体は収集しておいて、後のトラブルシュートで役立てる、というのがベターな使い方になる。

p.25 お願いだから円グラフは使わないで

かつてメモリの使用量を表示するグラフが円グラフで提供されていたことがあった。 実際に役に立たなかったのでそのとおりだと思う。

円グラフはあくまでも表示された瞬間のスナップショットでしかなく、時系列データの表現ではない。 メモリの枯渇を起こすまでの 傾向 がまったく可視化されないので肝心の時に役に立たない。 時系列データに対しては少なくともこの円グラフの表現は適切ではないと言える。

p.28 デザインパターン2: ユーザ視点での監視

経験的にサービス故障を検知する監視を最初に定義していたので、結果的にこのパターンに沿っていたように思う。

監視はいきなりシステムの深部から始めるのではなく、 システムの外側、つまりユーザが観測できるポイントから監視しましょう、ということ。

これまでの仕事柄、サーバサイドやネットワーク周辺の監視の仕事が多かった。 RESTful APIを提供しているサーバだと、特定のシナリオに従ってAPIを呼び出すようなスクリプトを定期的に実行し、その結果を監視するのが一番よさそう。 ネットワークにおいてはエッジからエッジまでユーザデータの転送を流し続けられるといい。JunosだとReal-time Performance Monitoring (RPMと呼ぶ)という機能を設定しておくと、同じ機能を持っているルータ間での実測性能をメトリクスとして蓄積できる。ルータ間でiperf動かしているような感じ。

p.47 3.3 インシデント管理

自分の対応を振り返ってみると、対応が終わったあとの振り返りが徹底できていないかな、という反省もあるので付箋を貼ったところ。

インシデント管理のラフなフローは下記のように

  1. 認識
  2. 記録
  3. 診断、分類、解決、クローズ
  4. 問題発生中のコミュニケーション
  5. 改善策

アラートとチケットについて

アラートをトリガとしてチケットが作成されるしかけができていると、 上記のリストの1, 2あたりは達成されていると思う。

しかしAtlassianの記事にはこんな注意事項もコメントされている。

現在の監視ツールの多くはノイズが非常に大きいことを考えると、アラートに基づいた自動チケット作成は、アラートのノイズ問題をチケット作成のノイズ問題へと拡大することになります。

アラートにノイズが多いのは現場あるあるかなと思う。 こんな現場ではチケット作成の自動化にすぐ飛びつくだけだとアラートのノイズの問題がチケットの滞留の問題に転化されるだけになってしまう。

このままでは運用が機能しなくなるので先にノイズを減らす対策をした方がよさそう。 本書でも「チェックボックス監視」というアンチパターンで指摘されているように不要な監視・アラートが仕込まれていることが原因でこのようにノイズに埋もれがちになる。

問題発生中のコミュニケーション

問題の解析とか対処している時は、他の部署とのコミュニケーションまで手が回らないことがあると思う。 本書ではインシデントの解消に取り組む人とは別に「コミュニケーション調整役」を定義している。

絶対そういうロール分けがあった方がいいと思う。 問題を解決を実行的に担当する人間には部署間調整やユーザへの周知などまで手が回らないのは容易に想像できる。 したがって作業担当と調整担当が最速の状況を把握しつつも、調整担当が関連部署への連絡をすることで、作業担当も集中して取り組めてミスも減らせる。

p.59 4.7 分意数

最小、平均、最大だけだと見逃す性質があるのですごく重要な観点。

システムのメトリクスをとっていると飛び抜けて大きいデータが急に現れたりすることがある。 最小、平均、最大だけ見ていると、最大がこの外れたデータで見えたりして驚く。 実際には70〜95パーセンタイルあたりをみてみると、外れたデータはなくて許容範囲に収まっていることが多い。

このようにGauge型メトリクスの跳躍を正しくとらえるためにも分意数による観測はとても役に立つ。 最小、最大だけでなくその間にあるデータの分布も見ましょう、ということなんだけど。

p.65 5.1 ビジネスKPI

サービスの正しさを監視する目的で実装をしてきたことが多いので、この視野での監視はカバーできていなかった。 本書でおさらいしてみて、こういうハイレベルなメトリクスの収集も面白そうだなと感じた。

こういうデータって経営層にレポートするのだろう。 報告に向けたレポート能力や定量データだけに頼りすぎないように誘導する議論のスキルが必要だったりしそう。 いろいろデータ以外にも配慮するべきところありそうだ。

p.80 6.3.1 フロントエンドパフォーマンスのメトリクス

必要性は認識していながら、サーバ側ばかりやってて実装方法をあまり知らなかったのだけど、本書を読んでなんとなくイメージついた。 ブラウザがAPI持っているらしい。(知らなかった)

バックエンドでどんなにチューニングしてもフロントエンドがボトルネックになってユーザ体験損なうということもあるだろう。 そういう問題を倒すための手法としてフロントエンドでの観察方法も身につけていく機会が持てればいいのだけど。

ユーザに近いことから監視ポイントを作っていくっていう目線で考えると、 ユーザにエラー表示した時点でアラート上がるように仕組みを作るのが第一歩になるのかな。

p.93 7.3 healthエンドポイントパターン

ping/pongくらいな単調なやつかと思ったらけっこうしっかりしたエンドポイントだった。

この例ではデータベース検索やキャッシュの取り出しを一回のリクエストの中で行うことで、 サブシステムとの結合をテストする目的があるらしい。

テスト、と書いたのがまさにこの監視の本質なのではないかと個人的には思っている。 少なくともサービスの正常性を監視をしようとするなら、継続的にテストを行うのが一番良いのはないか。 だから自動テストが常にプロダクション環境でも回るようにしておく。 勿論そのテストシナリオが複雑になりすぎないようにいくらかのトレードオフはあるはず。 しかし、いずれにせよ定期的なテストをサービス提供の裏で続けることでシステムの複合的なヘルスチェックを行う意義は大きいように思う。

このhealthエンドポイントではそうしたテストの中でも比較的小さいスコープ、つまり「コンポーネント同士のネットワーク間連携」を中心にチェックしている。 アプリケーションそれ自体で提供するならそのくらいの機能で十分かもしれない。

p.119 8.5 データベースサーバ

性能劣化に気づく重要な指標としてスロークエリは割と認識していたけど、 ミドルウェアの特性にあった監視戦略は引き出しにあまり無いなと感じた。

本書で紹介されているような 『実践ハイパフォーマンスMySQL』 のような本を読みたくなる日が来そう。 (その前に 『詳解システムパフォーマンス』 が読みたいが)

p.140 9.1.5 インタフェイスのメトリクス

スループットは事前の検証で計測することが多かったので、リアルタイムに監視する発想がなかった。 なのでなるほどと思う。

しかしプロダクション環境で物理帯域ぎりぎりのトラフィックをテスト的に印加するのは他のユーザへの影響があることも考えると気軽にできない。 スループットのテストはやはり定常監視とは別で議論した方がいいのか。

あまりすっきりした結論が出ず、個人的にはもやもやしている。

p.146 9.4 ルーティング

BGPのピアの監視はしていたが、下記のポイントは今までケアできていなかった。

  • TCAMのサイズ
  • ASパスの変更
  • 送受信プレフィクス数

サービス提供するお客様のBGPルータから広報される経路は、事前の設計で取り決めたものがあったので、 当時はあまり気にしていなかった。 しかし、いま考えてみるとお客様の使い方を観測するためにも上記のような監視ポイントを押さえておいても良かったのかもしれない。

という反省。

p.147 9.6.2 ハードウェア

個人的にはネットワーク機器の監視の中でもちょっと面白いと感じている部分だったりする。

  • シャーシの内部にどんな部品が内蔵されており、どんな役割をするのか。
  • 壊れるとしたらどんなアラートが上がるのか。

など、そのシステム(=ルータ)を分解していくような楽しさがあって、ハードウェア監視は好き。

LinuxのベアメタルとかもメーカごとのMIBを読んでどこを監視するのか探るのは面白い。

雑感

本書を読んでも分かるけど監視のスキルといっても幅広い。 うまく監視するためには監視対象をよく知らないといけない。

個人的には監視周りのことを仕事でやって面白いのはそんなふうに監視対象をハックしていく瞬間だったりする。 監視をするためにその対象をよく調べて発見をしていく過程が楽しい。

あと、本書に通底するNagiosへの怒り(「ただしNagios、てめーはだめだ」的な雰囲気)が非常にパーソナルで良かった。

プログラミング言語学習の助走

なにか気になるプログラミング言語を見つけたとする。

 

僕が社会人になりたての頃は形から入っていたのか、とりあえずそのプログラミング言語の本を買ってた。その本を片手にいきなり腰を据えてコードを書き始めるって感じたった。

 

真正面から取り組むのは意外と苦しくて結構挫折しがちだった。

 

ここ数年でやり方が変わってることに気付いた。

週一回くらいの気まぐれで気になっているプログラミング言語の公式サイトのドキュメントをちらっと読む。または買っておいた本を少し読む。

 

でもまだコードは書かない。色んなところにあるドキュメントを拾いながら少しだけ頭でっかちになる。

 

ふと時間のできたタイミングや作りたいものができたタイミングでようやく重い腰をあげてそのプログラミング言語を使う。

 

すると不思議な爽快感がある。憧れていた人に実際に会った時のような幻滅と歓喜の入り交じった妙な感覚。でもひどい落差も覚えないのですんなりとそのプログラミング言語を使い始められる。

 

事前に知識だけを入れておくことで、そのプログラミング言語に対して少し距離をおいた熱意をもつことができるのだろう。

ふーん、まあ、そんな感じだよね、でもそこが好き。みたいな。熟年夫婦の愛情に似ている。

 

HaskellClojureに対してはそんな風にして馴染んでいった。けれど、ずっと淡白かというとそうでもなくて、学び始めてからも新しい発見の度にテンション上がったりするので、ほとんど娯楽の永久機関なのでは、と最近思う。

 

まあ、僕はゆっくり堀の周りをうろついて助走をつけながら本丸に登る方が向いてるんだなーという話。

ということで何度も挫折してる数学はそういうアプローチで再挑戦しよう。

コードを書く時の生産性の低さに気付く

大して複雑なコードでもないのに、スクリプト書くのに3時間もかかった話。

問題

仕事で必要になりそうなスクリプトを書いてた。 公開できないけど。

以降に説明するような処理をするClojureスクリプトを書いていたが、 あらかた満足に動くようになるまで3時間もかかってしまった。

時間かかりすぎ、と思った。 ちゃんと設計や実装の戦略を仕込んでおけば半分の時間でできそうだなと、雑ながら感じている。

概要

ログの解析をおこなう。

JSON形式で出力されるログを走査して、 各種データの処理開始と処理終了のログを見つけたら、 そのログをペアリングして経過時間を計算する。

そのように各種データがそれぞれどのくらい時間かかっているのかをログから集計する。

一般的な処理ステップ

  • ログを読んでJSONデータ構造に復元
  • データの正規化
  • 処理の開始、終了にまとめる
  • 集計処理

シンプルだ

分析

どこに時間がかかっているのか?

体感

ソースにしているログのデータにばらつきがあったので、意外とコーナーケースの発見に時間がかかった。 pringデバッグしながらやっていたのでそれで時間くった気がする。

なのでログの解析(parsing)だけで2時間かかってたかもしれない。

何故時間がかかったのか?

なんでだろう。

  1. ゴミデータ、はずれデータが原因で動かない時のデバッグ
  2. API誤解したまま使って、predicateが逆に動いていたり

ふーん。

あ、あともう一個。

比較的大きめに関数を組んでから実行して、動かなくて部品に分解しなおしてデバッグ

これはかなりやり方よくなかったなと思う。 つい小さなパーツでの確認をとばして、どんどん大きい方に結合してからデバッグしちゃう。

小さいスコープ&合成

ということで、いま明確に認識しているのは、 この 小さな部品に分解したあとの小さなテストをしていなかった ところ。

リクスヘッジしてなかったなー。

(ちなみにすごい人はこういうところのリスクヘッジしなくても流れるように正しいコードを書くので基本スキルが違う気がしている)

どうするべきだったのか

実際のデータを使って入出力しつつ、 最小限の部品を入力と出力の間に挟むようにして動作確認していくべきだった。

Step 1

input ---> [ json parsing ] ---> output

Step 2

input ---> [ json parsing ] > [ normalize ] ---> output

Step 3

input ---> [ json parsing ] > [ normalize ] > [ accumlate ] ---> output

こんな感じでpipelineのpassを増やしていくようにして動きを見ていければよかったなーと。 テスト自体もプログラム本体の成長に従って修正されていくTDD的なやり方だったらよかったのかもしれない。

次のアクション

計測

時間を測ろう。

なんの機能あるいはどのステップの実装にどれくらい時間がかかっているかを知る必要がある。

gitのcommitのタイムスタンプから測れるかな。 でもsquashすると解らなくなるので、割とこまめに計測した方が良さそう。

pomodoro techniqueベースで時間管理することが多いから、 pomodoro timerの終わりでcommitするのが良いか。

練習

もっとたくさんプログラミングの練習をしたいな、と思った。

プログラムの速度よりは、振る舞いを実現できるか、というような機能要件にフォーカスしたい。 プログラムの効率・性能はそれから改善していけるので、まずはナイーブでも短い時間で実装できるスキルを磨きたい。

どんな問題を解くか?

どんな問題がいいかなー。

と考えた結果、手元にあってある程度現実的な問題を含む、『珠玉のプログラミング』でも読んで解いてみようかな。

読書

テスト駆動開発』もういちど読みつつ、 実践交えてやりたいな。

duct-frameworkに定時起動ジョブを仕込む

ただのtips。みんな気付いているけどショボすぎて言わないことだ。

ductをREPLから起動・停止くらいはできる人に向けている。 それも解らないよーという人は、なんというか、なんでこの記事を読もうと思ったのか。 そういう人はこちらを読むと良いと思う。

ClojureのDuctでWeb API開発してみた

結論

chimeをintegrantのライフサイクルに組み込むことでバックグラウンド処理するジョブが定義できるよという話。

構成要素

  • duct (core 0.6.2)
  • integrant
  • chime 0.2.2

やりかた

config.edn

まずは設定を書いておく

(抜粋)

 :example.job/channel {}
 :example.job/hello {:ch #ig/ref :example.job/channel}

:example.job/channel はジョブ起動の通知を送ってくれるchannel (core.asyncのchan) を保持する。

:example.job/hello は channel の通知を受け取って起動されるバックグラウンド処理そのもの。 ジョブの起動には通知をくれる channel が必要なので ig/ref で解決している。

clojure

(ns example.job
  (:require [integrant.core :as ig]
            [clojure.core.async :as a]
            [chime :refer [chime-ch]]
            [clj-time.core :as time]
            [clj-time.periodic :as periodic]))

(defmethod ig/init-key :example.job/channel [_ _]
  (chime-ch (periodic/periodic-seq (time/now) (time/seconds 5))
            {:ch (a/chan (a/dropping-buffer 1))}))

(defmethod ig/halt-key! :example.job/channel [_ ch]
  (a/close! ch))

(defmethod ig/init-key :example.job/hello [_ {:keys [ch]}]
  (a/go-loop []
    (when-let [time (a/<! ch)]
      (prn "Hello world at " time)
      (recur))))

少しかいつまんで解説。

channelの初期化

(defmethod ig/init-key :example.job/channel [_ _]
  (chime-ch (periodic/periodic-seq (time/now) (time/seconds 5))
            {:ch (a/chan (a/dropping-buffer 1))}))

chime-ch 指定された時刻にタイムスタンプデータを送信するchannelを生成する。

clj-time/periodicperiodic/periodic-seq を使ってchannelからメッセージを受け取る時刻の無限ストリームを取得する。 (個人的に時間の経過を無限ストリームで表現する設計大好き)

{:ch (a/chan (a/dropping-buffer 1))} ここは chime-ch で生成される channel のバッファに長さと廃棄ポリシを設定している。

channelの破棄

(defmethod ig/halt-key! :example.job/channel [_ ch]
  (a/close! ch))

channel を閉じるだけ。 channel からメッセージを受け取れなくなった軽量プロセスはparking状態のまま何もしなくなるので、実質的にバックグラウンドジョブは停止している。

channelを使ったジョブ

(defmethod ig/init-key :example.job/hello [_ {:keys [ch]}]
  (a/go-loop []
    (when-let [time (a/<! ch)]
      (prn "Hello world at " time)
      (recur))))

when-let を使って channel からメッセージが届く時のみ印字処理を行って次のメッセージがくるまで待機するようにループさせている。

Result

ductなのでREPLから (go) と入力するとサーバの起動とともにREPLに5秒間隔でHello worldとぬかしてくるジョブが起動する。

:initiated
"Hello world at " #object[org.joda.time.DateTime 0x86ddf48 "2018-04-15T07:49:08.518Z"]
"Hello world at " #object[org.joda.time.DateTime 0x7f4e3d0e "2018-04-15T07:49:23.518Z"]
"Hello world at " #object[org.joda.time.DateTime 0x6aa2035 "2018-04-15T07:49:28.518Z"]
"Hello world at " #object[org.joda.time.DateTime 0x549f285d "2018-04-15T07:49:33.518Z"

Web APIとバッチジョブ

モチベーションの話。

僕がやりたかったのは、Web API経由で操作可能なWebクローラみたいなもの。 クローラが巡回しにいくエンドポイントをCRUDで操作できる的なやつ。

ただ、Web APIとバッチジョブっていう組み合わせは 応用が効く ような気がしている。 ふつーの典型的なバッチジョブを作るにしても、ジョブの実行時間や結果の履歴などの統計情報をWeb API経由で取れるようにしておくと、他のAdmin向けサービスの統合がしやすくなったりする。

運用系APIがあるというのは僕みたいなインフラ屋からするととてもポイント高い。

(脱線) Finagleという実例

バックグラウンドジョブとは少し違うけど、僕がとても感心したのはfinagleというScala向けマイクロサービスフレームワーク

このfinagleはマイクロサービスのエンドポイントを作るたくさんのAPIを提供している。なかでも面白いのがサービスエンドポイントの統計情報もとれる仕組みが標準で提供されていること。

Metrics

ユーザのリクエストで起動するにせよ、定時起動するにせよ、サービスの稼働状況を抽出できるAPIを備えていると、デプロイ後のフィードバックが得やすくなる。 これはサービスの改善点を定量的に探ったり問題を検知したりするのに役立つ。

バッチジョブ作る人へ

こんな風にジョブの統計情報を外部にexposeできるような仕組みを仕込んでおくと、サービスが成長した時にありがたがられること間違いなし。

Web APIとバッチジョブは割といい組み合わせだと再認識した。

小さなバッチジョブを作ろうと思ったらまずは

lein new duct {プロジェクト名} +api +ataraxy

と打ってほしい。

Clojure思ったより書けない問題

今日ちょっと仕事でデータの加工して集計する作業があったので、 加工スクリプトClojure使おうとした。

結果、全然書けなくて愕然とした訳だけど、その理由を考えてみる。

ちなみにClojureは全く悪くない。僕が勉強不足だっただけ。

1. CIDER REPLとバッファの連携のさせ方が不勉強

いま開いているバッファをREPLに突っ込んで、 そのバッファの名前空間上で式を評価したい。

とかがそもそもどうやるのかまだ解っていない。

このあたりはREPL駆動開発的な 自分なりの フローを作ることで解決すると思う。

2. ClojureJavaInteropに必要な特殊形式知らなすぎ

コンストラクタどう呼ぶのか。 メソッドどう呼ぶのか。

JVMの資産を利用できるのが強みのClojureのはずなのに、 JavaとのInterop方法忘れてていちいち調べてた。

これから

上手く書けなかったのがめちゃくちゃ悔しい。 自分のほしいものを書けるようならないと、使えると言っちゃ駄目だ。 そしてClojureを使えるようになりたい。

HaskellのCofreeのネタを書くためにもFixとうとうの導入を試してはみるけど、 Clojure触る時間をしばらく主軸に置こうかな。 という風に少し重みを変えよう。

さて、Clojureで何作るか探すかなー。

Haskellで再帰的な構文木にFix(不動点)を導入してみる

まえおき

例によって僕の記事など読まなくても下記のリンクで解説されているので、 Haskell楽しいなと思う人はこちらをどうぞ。

An Introduction to Recursion Schemes

生きるのに疲れた人は半分白目のゆるい気持ちで以降を読んでね。

Haskellで抽象構文木 (AST) にメタデータを付与する

以前この記事でASTへのメタデータの埋め込み方について少し整理して、 下記のようなアプローチがあることを明らかにした。

  1. メタデータを保存するための値コンストラクタをASTのブランチとして定義する
  2. メタデータを保存するラッパーを定義する

加えて

Fixを使ってなんかファンシーにする

というアプローチについて最後に少し言及した。 これについては当時の僕の頭では理解が追いつかなかったが、 いま少しだけ近づけてきた気がするのでまたしても整理してみる。

導入

僕達は日常的に再帰的な構文に出くわしている。

ラムダ項の定義とかもうまさしくそれ。

t ::=
    x
    λx. t
    t t

型システム入門のP.40から拝借

Haskellで書くと、例えばこうなる。

type Id = String

data Term
  = Var Id
  | Abs Id Term
  | App Term Term
  deriving (Eq, Show)

問題

素朴に記述したこのAST。 使っているうちに構文木そのもののデータだけでなく、メタデータを保存していきたくなる。

メタデータの例

  • ソースファイル名
  • ファイル内の位置情報

普通にアプローチするとこのASTの定義を改造してメタデータを埋め込める場所を用意する。

例えばトークンの開始位置と終了位置を含むデータ Region を埋め込む例の場合。

data Term
  = Var Region Id
  | Abs Region Id Term
  | App Region Term Term
  deriving (Eq, Show)

しかし、これだとASTのデータ型は純粋な構文 以外 のデータも持つことになってしまう。 できればメタデータをASTをに混ぜるのではなく、分離した上で自然に組み合わせたい。

ということでその立役者となる Cofree を目指すことになる。

しかし、そもそも Cofree の下地となっている Fix という構造がよく解らなかったので、この記事ではまず下記のポイントを確認していこうと思う。

  1. Fix とはなにものなのか
  2. Fix を導入するとなにが起こるのか

再帰的な構文の抽象化

data Term
  = Var Id
  | Abs Id Term   -- 再帰あり
  | App Term Term -- 再帰あり
  deriving (Eq, Show)

もう一度構文定義を再掲。 3つ中2つのコンストラクタは再帰的に Term を受け取るようになっている。

たとえば Abs は具体的なデータとして Term再帰的に内包できる。

この再帰構造はもう一段抽象化できる。 型変数を導入することで下記のようになる。

data TermF a
  = VarF Id
  | AbsF Id a
  | AppF a a
  deriving (Eq, Show)

コンストラクタの中で Term を持っていたところを型変数 a に括りだした形になる。 型をみると解るように、carrier typeを持つこのデータ型は Functor になることができる。 言語拡張の DeriveFunctor , DeriveTraversable , DeriveFoldable を使うことで、 このデータ型はとても多くの性質を獲得できるようになる。

これで具体的な項を作ってみる。

> let absx = AbsF "x" $ VarF "x"
> :t absx
absx :: TermF (TermF a)
> let absxy = AbsF "x" $ AbsF "y" $ VarF "y"
> :t absxy
absxy :: TermF (TermF (TermF a))

こんな感じ。

項がネストする深さに応じて型もネストしている のが解る。 10の深さの項を作ると、

TermF (TermF (TermF (TermF ...)))

とTermFが10個続いていくことになる。 でもこれは扱いにくい。 構成するデータに応じて型が変わり過ぎる。

古いバージョンの定義を使って項を構成して見比べてみよう。

> let absx = Abs "x" $ Var "x"
> :t absx
absx :: Term
> let absxy = Abs "x" $ Abs "y" $ Var "y"
> :t absxy
absxy :: Term

型が単純。

型変数を導入する前はどんな構成方法でも項の型は Term だった。 しかし型変数を導入したら、構成方法によって型が変わってしまった。

実はこれでは充分ではない。 ネストする、つまり再帰する型を一つの型に収束させる必要がある。

イメージ的には、

TermF (TermF a) -> TermF
TermF (TermF (TermF a)) -> TermF

のようにネストした型を TermF みたいな何か単純な表現に収束してくれるものを求めている。

Fix

ここで奇妙なデータ型を導入する。

newtype Fix f = In (f (Fix f))

定義方法はこちらに従った: Understanding F-Algebras

複雑な型を内部にもっており、僕も最初に見た時は面食らった。

この Fix を使うと先ほどの再帰的にネストしていく型を収束できる。 ただしデータの構成時にちょっとおまけが必要。

> let absxfix = In $ AbsF "x" $ In $ VarF "x"
> :t absxfix
absxfix :: Fix TermF

お、型のネストが消えた。 読みやすさのために括弧を使ってみる。

> let absxfix = In ( AbsF "x" ( In ( VarF "x" ) ) )
> :t absxfix
absxfix :: Fix TermF

TermF を構成したら必ず In でラップしてやるのがミソ。
すると Fix TermF という型が表れて再帰を隠してくれる。 もう少し深い項を構成してみよう。

> let absxyfix = In $ AbsF "x" $ In $ AbsF "y" $ In $ VarF "y"
> :t absxyfix
absxyfix :: Fix TermF

やっぱり Fix TermF に収束した。

収束の過程・仕組み

単純に型合わせの過程を観察して、確かに Fix TermF になることを見てみよう。

と言いつつ気力が湧いてきたら書く (ごめんなさい)

Fixは型レベルのfixだった

Fix はデータ型だけどこれと同じような定義を持つ関数がある。

Control.Monad.Fix.fix

型はこんな感じ。

> :t fix
fix :: (a -> a) -> a

関数を渡すと値が出てくる変なヤツ。

一方でFixの種 (kind) はどうだろうか?

> :k Fix
Fix :: (* -> *) -> *

似すぎ。

もしやと思ってそれぞれの定義を見比べる。

まずfixの定義。 ( こちらを参照 )

fix :: (a -> a) -> a
fix f = f (fix f)

再帰的に呼び出す fix f の結果に f を適用している。

newtype Fix f = In (f (Fix f))

再帰的に呼び出す Fix f の結果に f を適用している。

一緒じゃん。

形が似ていることは解った。 fix を既に知っている人にとっては Fix の振る舞いはもはや疑問の余地がないものだろう。

ただ僕はよく解らないのでちゃんと考える必要がある。

Fixは何なのか

下記のリンクを読めば解る人には解るかもしれない。

HaskellWiki - 不動点と再帰

僕は解らない。

試してみた僕の理解だと Fix f とは

fを再帰的に適用して収束するとこを見つける関数のようなもの

という認識。

Fix f とするとき、 Fix の定義により

Fix f = f(f(f(f(...))))

となる。 再帰的に型コンストラクf を適用していくことを表現している。

この Fix というデータ型と似た関数版もやはり再帰に関わる。

Control.Monad.Fix.fix

fix f = f(f(f(f(f(...)))))

こうなる。 こちらも同様に関数 f再帰的に適用していくことを表現している。

データ型版も関数版も再帰的に f再帰的に適用することを表現しているのがポイント。

Fixで得たもの・失ったもの

Fix を使うことで任意の深さで再帰する型 (例えば TermF ) を同一の型で表現することができるようになった。 この統一的な表現方式により、冒頭のリンクで言及されているような

  • 再帰的なデータの走査
  • データ構造の再帰と作用の分離

などを手にすることができる。

この Fix によってもたらされた恩恵の向こうに Cofree が待っているようだ。

得たもの

Cofreeという抽象構造へのステップ。 あと少しっぽい。

うまくいけばASTにメタデータきれいに 載せられるかもしれない!

失ったもの

単純に項を構成する方法。 Fix導入前は項を構成して比較することも容易だった。

> ( Abs "x" ( Var "x" ) ) == ( Abs "x" ( Var "x" ) )
True

なのでテストを書くのが楽だった。

ところが今回は Fix で構文データをラップする必要が出てくる。

しかしFixという構造自体はEqのインスタンスにできなさそう。同値という性質を定義できない。 なのでFixを使って作られた項は単純な比較ができなくなる。

2019-03-03

コメントにて Fix の同値性は定義できる旨をアドバイス頂いたので検証。 ご指摘の通り Fix の導入にあたり前述のようなデメリットは無いと分った。

import Data.Functor.Classes (Eq1, eq1)

instance Eq1 TermF where
  liftEq _ (VarF i) (VarF j) = i == j
  liftEq f (AbsF i x) (AbsF j y) = i == j && f x y
  liftEq f (AppF a b) (AppF c d) = f a c && f b d
  liftEq _ _ _ = False

instance (Eq1 f) => Eq (Fix f) where
  (In x) == (In y) = eq1 x y

上記のように2つの定義、すなわち 1. TermFEq1 2. Fix fEq を与えることで同値性のテストもできるようになる。

*Main Lib Data.Functor.Classes> lhs = In $ AbsF "x" $ In $ AbsF "y" $ In $ VarF "y"
*Main Lib Data.Functor.Classes> rhs = In $ AbsF "x" $ In $ AbsF "y" $ In $ VarF "y"
*Main Lib Data.Functor.Classes> lhs == rhs
True

こんな風に Fix で包んだ項も比較できる。

GHC 8.6系から使える QuantifiedConstraints を使ってさらに無駄なく定義できるかは確認中。

  • Eq (Fix f) を定義するためには Eq f を仮定したい
  • Eq fを仮定したいところだが f はカインドが * -> * なので Eq (f a) を仮定しようとする (ここが自信ない)
  • Eq (f a) を仮定することで導入される型変数 a が、定義 Eq (Fix f) に現れないためにエラーとなる
    * Variable `a' occurs more often
        in the constraint `Eq (f a)' than in the instance head `Eq (Fix f)'
      (Use UndecidableInstances to permit this)
    * In the instance declaration for `Eq (Fix f)'
   |
31 | instance Eq (f a) => Eq (Fix f) where
   |          ^^^^^^^^^^^^^^^^^^^^^^
   |

Free f a みたいなデータ型に Eqインスタンス定義を与えるならいけそう。

FixやCofreeは本当に必要か?

エレガントに見えるけど率直さを失った。 本当に必要な抽象か?

比較してみる

1. メタデータを保存するための値コンストラクタをASTのブランチとして定義する

ASTに位置情報という付加情報のためのブランチを作る。 簡単、率直だが美しくはない。

ASTの規模が小さいならブランチを作るコスト、それらを分解するコストは大したことないのでこれでいい。 というかSML/NJがこれを導入している実績あるので、 同程度の規模ならなんとかなると思っていいんじゃないかな。

人生はエレガンス、がスローガンの人だけ次を読むべき。

2. メタデータを保存するラッパーを定義する

位置情報を保存するラッパーを作る。 ASTそれ自体の定義はピュアに保てる。

今回の Fix も所詮ラッパーなので導入コストについていえば、実は2と変わらなかったりする。 その上で構文が FunctorTraversable Foldable を備えるなら 応用力では今回の Fix アプローチが勝る。

と、言えなくもない。

ただし、僕はこの Fix ベースの構文定義を使っている実用的なプログラミング言語をまだ目撃していない。 事例が無いので何か本質的な瑕疵でもあるのでは、と恐怖している。

誰か Fix 使った構文定義しているプログラミング言語実装の例を知っていたら教えてほしい。

うそ。教えてなくてもいい。 僕が Fix の餌食になるので。

まあ、せっかく学んだのでこのアプローチを簡単に捨てるのはまだ少し惜しい気もしている。 ということで、もう少し調査を続行。

次の話題

どうもこの手法、 Recursion Scheme と呼ばれるアプローチらしい。

An Introduction to Recursion Schemes

ということで冒頭のリンクにたどり着いたのだった。

この記事の基礎になっている論文が下記。

Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire

木構造の簡約・走査に関連する発想の一つみたいだ。 読みたい。読もう。

直近の懸念は、この Fix を導入したとして、 派手に壊れたテストをどうやって直して行くか、だ。

その問題に対して何かヒントがあるか拾っていきたい。

最近

ずっとvtuberの動画観てる。

  • ときのそら
  • ぜったい天使くるみちゃん (もう活動一時停止してる)

歌う人好きっぽい。

(技術の話をして)

Haskellで抽象構文木 (AST) にメタデータを付与する

2018-01-04 追記: ここで全部語り尽くされている気がしたので、Labelling AST Nodes with locations なにもこんなブログ読むことはないのかもしれない。

megaparsecを使って構文解析器を書いている。

構文解析やっているとASTにソースファイルの位置情報とかをメタデータとして乗せたくなるが、 どんな感じで実装するのか調べた。

僕自身はどのアプローチをとるのか決まっていない。

問題

やりたいこと

megaparsec, parsecなどのコンビネータライブラリはジェネレータ系のalex + happyと比べると幾分まともなエラーメッセージを吐くようになっている。(alex + happyがえげつないほどterseなだけ)

しかし、構文解析が終わった後のα変換によるshadowingの回避や型推論のフェーズでコンパイラがエラーを見つけた場合に、 そのトークンの位置が保存されていないと、エラーメッセージとして不親切に思う。

なので、ASTに位置 SourcePos のようなものを乗せたい。

解きたいこと

しかし、単純に既存のデータ構造に埋め込むと、値コンストラクタのArityが変わったり、コンストラクタのパターンが増えたりしてせっかく書いたhspecのテストも盛大に直さなければならない。

それは嫌だ。

僕がやりたいのは 「ASTにメタデータとして位置情報を乗せたい」 のであって 「ASTの意味を変えたい」 訳では断じて無い。 僕がやりたいことを簡潔にデータ型として表現したい。

おい、Haskellお前ならできるはずだろ!?

夢を見させてくれよ!

お前そういうの得意だろ!?

アプローチ

少し既存の構文解析器を調べた。

下記の調査をまとめると。

  1. メタデータを保存するための値コンストラクタをASTのブランチとして定義する
  2. メタデータを保存するラッパーを定義する

の2種類のアプローチを観測した。

1. ASTにブランチを追加するパターン

下記の2言語で発見。

dhall-haskell

Note というコンストラクタをメインのASTにブランチとして定義して、 s にメタ情報を格納しているらしい。

    -- | > Note s x                                 ~  e
    | Note s (Expr s a)

s が位置情報を含んでいる模様。

ASTがプログラミング言語の構文を定義するのだとすると、 こういったメタ情報がコンストラクタに表れるのはやはりノイズでしかないので できれば排除したいなーという思い。

SML/NJ

fixitem というデータ型を定義している

type 'a fixitem = {item: 'a, fixity: symbol option, region: region}

この region というのが場所を保存している。

でそれをASTのコンストラクタに埋め込んでいる。

  | FlatAppExp of exp fixitem list (* expressions before fixity parsing *)

あるいは位置保存用のコンストラクタを各サブツリーのデータ型に定義している。

  | MarkExp of exp * region   (* mark an expression *) |

この MarkXXX とつくコンストラクタは全て位置情報を確保しておくためだけにある、 メタな何かだ。

式やパターンなどのASTごとにこういった MarkXXX というコンストラクタを定義している。

これはdhallと同じアプローチのようだ。

2. ASTにラッパーをかぶせるパターン

下記の2言語で発見。

ghc

概ね知りたいことがWikiに書いてあった。

The HsSyn types

ghcマジ天使。

  • SrcLoc というのが位置情報を持っている。
  • SrcSpan というのが位置から位置までのブロックを表している
  • Located ee の実際のブロックを保存する
-- | We attach SrcSpans to lots of things, so let's have a datatype for it.
data GenLocated l e = L l e
  deriving (…)

type Located e = GenLocated SrcSpan e

ghcではなんらかのASTを構築したら、これを Located で包むことによって、 位置情報を付加している。

この場合、ASTそれ自体 (この場合HsSyn) の定義は変わらないので 関心事は上手く分離されているといえる。

elm-compiler

ghcと同様の方式を選んでいるように見える。

これは式のASTの例だが、

-- EXPRESSIONS


type Expr def =
    A.Located (Expr' def)


data Expr' def
    = Literal Literal.Literal
    ...

Expr' が実際のAST。( def はbinderっぽいので気にしなくてよし)

それに Located というデータをかぶせている。

これは何かというと、

-- ANNOTATION


type Located a =
    Annotated R.Region a

Locatedペイロードとして a この場合は Expr' とともに、 Region を持つようになっている。

data Region =
  Region
    { start :: !Position
    , end :: !Position
    }
    deriving (Eq, Show)

Region がまさしく位置情報。

ghcと同じアプローチを感じる。

(発展的話題) なんか色々言ってる人がおる

おもむろに怪しい道具 Fix を持ち出す海外勢の様子。

How to work with AST with Cofree annotation?

Adding source positions to AST nodes for free

何やってるのかわからない。

どいつもこいつも Fix 大好きだなおい。 本気で言っているのか。

それは本当にお前たちの問題領域を簡潔に保っているのか。

という疑念が晴れない。 というか、ここにわざわざFreeモナドを導入する必要はあるのか。 ぶっちゃけ使いたいだけじゃないのか。

ダークパワーを使いたくない僕としてはまだこのアプローチにだいぶ抵抗感がある。

どうするどうする

どうしよう。

ASTそのものは定義を変えずにいけるghc方式をとるかもしれない。

だいぶ素人なので詳しい人いたらアドバイスください。。。

まとめ

ASTに位置情報を付与したい場合は

  1. メタデータを保存するための値コンストラクタをASTのブランチとして定義する
  2. メタデータを保存するラッパーを定義する

という方法があるらしい。

(その他、識別子から位置情報を引くハッシュテーブルを作るみたいなのもあった気がする)