2022-10-12

Python の decorator

python

概要

本記事では，python の decorator について

decorator の基本
syntax sugar
引数をとる decorator

についてまとめた．

decorator の基本

decorator とは，関数を引数にとってその関数の動作になんらかの変更を加えた新しい関数を返すものである．

簡単な例を下に挙げる．

def decorate(func):
    def wrapper():
        print('**********')
        func()
        print('**********')
    return wrapper

def say_hello():
    print('Hello!')

say_hello = decorate(say_hello)

say_hello()

出力

**********
Hello!
**********

decorateという関数が，引数なしの関数funcを受け取る decorator である． decorate(say_hello)のようにsay_helloという関数を decorator に渡すことで，say_hello の実行前後に'**********'という行を出力するように加工した関数が返ってきている．

syntax sugar

def say_hello():
    print('Hello!')

say_hello = decorate(say_hello)

という書き方は同じ関数名を何度も書いていて，少しくどい．また，関数を加工する部分が関数定義箇所から離れてしまうので，可読性も低い．

そこで，syntax sugar として次の書き方が使える．

@decorate
def say_hello():
    print('Hello!')

これは効果としては上にあげた書き方と等価である． @によるsyntax sugar を用いたほうが，簡潔かつわかりやすく書ける．

引数を受け取る decorator

上の例で，********** が表示される行数を decorator に与える引数によって制御したいとする．つまり，次のような使い方ができるようにしたい．

@decorate_multi_line(num_lines=3)
def say_hello():
    print('Hello!')

say_hello()

出力

**********
**********
**********
Hello!
**********
**********
**********

これを行うためには，decorator_multi_line に出力行数のパラメータ num_linesを与えると，「関数の実行前後にnum_lines行だけ**********を出力するように加工する decorator 」を返すようにすれば良い．

具体的には，次のように実装できる．

def decorate_multi_line(num_lines):
    def decorate(func):
        def helper():
            for i in range(num_lines):
                print('**********')
        def wrapper():
            helper()
            func()
            helper()
        return wrapper
    return decorate

decorate_multi_line(num_lines=3)という呼び出しによって，3行ずつ装飾行を加えるdecorateがつくられる．ここで返ってきたdecorateがさらにsay_helloなどの関数に適用されることで，期待通りの動作が実現される．

2022-09-28

bash の TAB補完をカスタマイズする

bash

概要

bash はコマンド名や引数の補完機能を備えており，入力中に TAB キーを押すことで候補を表示したり残りの部分を入力したりできる．

ただし，デフォルトであらゆる状況に対して適切な補完が効くわけではないので，文脈に応じて補完候補を自分でカスタマイズしたいという状況が生じる．このようなとき，bash に備わっている programmable completion という機構を使うことで好きなように補完候補を指定することができる．

本記事では，lpコマンド(プリンタに印刷命令を発行するコマンド)を題材に自作の補完を実装してみた．

補完のしくみ

bash では補完を行う際，事前に設定されたシェルスクリプト関数を呼び出す．このシェルスクリプト関数はコマンド名や入力中の引数を受け取って解析し，文脈に応じて適切な補完候補を生成する．

bash-completionというパッケージで便利な補完がかなりいろいろと定義されており，たいていはインストールされて使えるようになっているはずである．

GitHub - scop/bash-completion: Programmable completion functions for bash

もし入っていれば，/usr/share/bash-completionなどに補完用の関数の定義がある(~/.bashrc内にこれらのファイルを読み込む設定があるはずである)．

現在定義されている補完はcomplete -pで確認できる．bash-completionが入っていれば次のような表示が出るはずである．

complete -F _longopt mv
complete -F _root_command gksudo
complete -F _command nice
complete -F _longopt tr
complete -F _longopt head
...

この出力はそのまま bash で実行できるような形で出力されており，complete -F <function-name> <command-name> で <command-name>というコマンドの引数の補完方法に<function-name>というシェルスクリプト関数を指定するという意味になる．

bash-completionはかなり便利だがそれでもパターンが網羅されているわけではない．自分で補完候補を定義したい場合は，自分でシェルスクリプト関数を書いて補完用の関数として指定すれば良い．

自作の補完関数は，~/.bash_completionに保存しておけばbash-completionが勝手に読み込んでくれる．

簡単な例

_dummy() {
    COMPREPLY=( one two )
}
complete -F _dummy dummy

上の内容をdummyなどの名前でファイルに保存し，source dummyなどで定義内容を読み込む．ここでdummy <TAB>などと入力すると，one twoと補完候補が表示されるのがわかる．

_dummy は補完用の関数で，COMPREPLYという配列変数に補完候補を設定する． complete -F _dummy dummyでdummyというコマンドに対する引数の補完方法として_dummy()を使うように指定する．

補完用の関数名は _ + コマンド名とするのが通例となっているようである．

入力引数の取得

実際の状況では，特定のオプションの直後にオプションの設定値の候補を補完するなど現在入力中の引数に依存したより複雑な補完が要求される．

このために入力中の引数の数や引数の中身を取得するための _get_comp_words_by_ref という関数がbash-completionで用意されている．これを使うには，次のように書けばよい．

local cur prev cword
_get_comp_words_by_ref -n : cur prev cword

localというのは関数のローカル変数を定義するための bash のキーワードである． _get_comp_words_by_ref -n : cur prev cwordという書き方で，それぞれ

cur: 現在入力中の引数
prev: ひとつ前の引数
cword: 引数の数

が設定される．

例えば，次のように補完を定義する．

_dummy() {
    local cur prev cword
    _get_comp_words_by_ref -n : cur prev cword
    echo
    echo cur: ${cur}
    echo prev: ${prev}
    echo cword: ${cword}
}
complete -F _dummy dummy

ここでdummy foo barと入力した段階で TAB キーで補完を試みると，各変数の内容は

cur: "bar"
prev: "foo"
cword: "2"

のように設定される．

補完候補の絞り込み

入力途中の文字列にマッチする候補だけに絞りこむには compgen という組み込み関数が使える．

comgen <option> <word>

という形で，オプションで指定した方法で生成された補完候補のうち先頭がwordにマッチするもののリストを生成する．

例えば，-W <word list>という空白区切りの文字列を補完候補とするようなオプションを使って，

compgen -W "foo bar baz" ba

と実行すると，foo,bar,bazのうちbaから始まるbarとbazが補完候補として生成される．

典型的には，COMPREPLYの値にcompgenで生成したリストを設定することで候補の絞り込みを実現する．

実例: lp コマンドでプリンタ名の補完

lp コマンドは，プリンタに印刷命令を発行するコマンドで次のように使う．

lp <filename>

-d <printer-name>というオプションでどのプリンタを使うか指定できるのだが，デフォルトでは適切に補完が効かない．しかし，プリンタの型番など人間が覚えているはずがないので，なんとか補完候補を表示してほしいものである．

そこで，実装したのが次の関数である．

_lp() {
    local cur prev cword
    _get_comp_words_by_ref -n : cur prev cword
    if [[ "$prev" == "-d" ]]; then
        # generate available printer list
        local printers=$(lpstat -e | tr '\n' ' ')
        COMPREPLY=( $(compgen -W "${printers}" -- ${cur}) )
    else
        COMPREPLY=( $(compgen -f -- ${cur}) )
    fi
}
complete -F _lp lp

_get_comp_words_by_refで引数を取得する．直前の引数を見て，-dなら現在の補完候補としてプリンタ名のリストを生成する(lpstat -eで取得できる)． tr '\n' ' 'というのは改行文字を空白文字に変換してcompgen -Wの引数として使えるようにするための処理である．

-dオプション以外のときは，compgen -fでファイル名を補完候補として使う．

たったこれだけのことだが結構快適になるものである．困ったときはぜひ自分で補完を定義するのに挑戦してみてほしい．

参考

下の記事は内容が充実している．

blog.cybozu.io

公式な資料としてはman bashの Programmable Completion というセクションやman bash-builtinsのcompleteやcompgenの項目を見ると良い．

実装例をいろいろと見たい場合には，/usr/share/bash-completion以下にいろいろと置かれている．

2022-08-21

SATySFi のマクロ入門

SATySFi

この記事について

SATySFi のマクロは，インラインコマンドやブロックコマンドの形で多段階計算によるプリプロセス機構を利用できるようにするものである． SATySFi上でDSLを実装してパッケージなどとして提供するような場合には，最終的にマクロによるインターフェースとして提供するのが基本になるだろう．

この記事では，マクロの定義方法やエラー位置の取得方法について説明する．

前回の記事で，SATySFiの多段階計算について基本的な内容をまとめた．多段階計算でわからない部分があれば合わせて読んでみてほしい．

sankantsu.hatenablog.com

大半はSATySFi本体のソースコードや手元での実験に基づいて書いている．間違いがあれば遠慮なく指摘してほしい．

バージョンは0.0.7に基づいている．

マクロの定義

マクロの定義は，次の文法によって行う．

let-inline \macro-name@ param... = ...
let-block +macro-name@ param... = ...

macro-nameはマクロの識別子であり，通常の変数名と同じである．識別子の最後に@文字をつけることに注意する．

param...は，~param-nameまたはparam-nameの並びである．各パラメータは，ステージ0の変数として扱われる．また，

~param-name (early macro parameter) は 'a型の変数
param-name (late macro paramter) は &'a型の変数

として扱われる．

マクロの定義本体はステージ1のプログラムとして記述する．返り値の型はインラインコマンドであればinline-text，ブロックコマンドであればblock-textになる必要がある．

通常のインラインコマンドなどと違い，コンテキストの第0引数を受け取る形の定義

let-inline ctx \macro-name@ param... = ...

はサポートされていないことに注意しておく．

また，moduleの内部にマクロを定義することも現状できない．

マクロの適用

マクロの適用は，次の文法によって行う．

\macro-name@ arg...;
+macro-name@ arg...;

通常のインラインコマンド，ブロックコマンドと同様，\macro-name@はインラインテキスト中に，+macro-name@はブロックテキスト中に書く必要がある．

arg...は~(exp)または(exp)の並びである．括弧は省略できない． expには通常の関数に渡す引数のとほとんど同じ形式の式を書ける．

パラメータの種類ごとに引数の渡し方に違いがある．

~param-nameの形のパラメータ (early macro parameter)
- ~(exp)の形で引数を渡す．
- param-nameにステージ0の式expが束縛される．
param-nameの形のパラメータ (late macro parameter)
- (exp)の形で引数を渡す．
- param-nameにステージ0で&(exp)と書いた場合に相当する値が束縛される．

マクロの適用は文書全体の評価よりも先に行われ，評価結果のインラインテキストに置き換えられる．マクロの評価の詳細については後で再び説明する．

簡単な例

マクロの使い方の確認のため，次のような例を考える．

@require: stdjareport

let-inline \foo@ ~a b =
  let x = ~(lift-int a) + 1 in
  let y = ~b + 1 in
  let it = embed-string ((arabic x) ^ #` `# ^ (arabic y)) in
    it

in

document (|
  title = {Test of macro definition};
  author = {sankantsu};
|) '<
   +p {
     \foo@ ~(100) (200);
   }
>

例ではaはint型，bは&int型の変数になっている．動作自体は受け取った引数それぞれに1を足して出力するだけの簡単なものであるが，~をつけて宣言するかどうかで変数の使い方が違うのがわかる．

マクロの評価

先程の例で用いたマクロは，マクロを使わずに次のように書くのとほぼ等価である．ただし，関数の定義部分は@stage: 0の別ファイルに分けた．

% header0.satyh
@stage: 0

let foo a b = 
  &(let x = ~(lift-int a) + 1 in
    let y = ~b + 1 in
    let it = embed-string ((arabic x) ^ #` `# ^ (arabic y)) in
      it
  )

@require: stdjareport
@import: header0

let-inline \id it = it

in

document (|
  title = {Test of macro definition};
  author = {sankantsu};
|) '<
   +p {
     \id(~(foo 100 &200));
   }
>

次の点に注意しておく．

マクロの定義はステージ0の関数定義になっている．また，定義全体を&(...)で囲んでいる．
マクロの適用はステージ0の関数適用になっている．
- 引数の受け渡しについて，~(exp)のタイプは単にexpに，(exp)のタイプは&(exp)に置き換わっている．

マクロの動作がわかりにくいという場合は上のような置き換えを考えてみると良いかもしれない．

エラー位置の取得

マクロの導入のモチベーションは，DSLのパースをプリプロセス中に行うことで迅速なエラー報告を可能にするというものであった．これまで説明した内容だけでも，DSLの実装やエラー報告自体は可能になるが，ソースコード上のエラー位置を報告することができない． DSLである程度複雑な文法を扱うようにするとなると，入力箇所のどこにエラーがあるかわかったほうが便利だろう．

この問題を解決するために導入されたのが，@`...`という形で記述する positioned literal というものである．この形式で書かれた文字列は，通常の文字列stringに加えてコード中の位置を表すinput-position型が付加されたinput-position * string型として扱われる．

input-position型の値は，

val get-input-position : input-position -> string * int * int

というプリミティブを用いることで文字列先頭位置の(ファイル名,列番号,行番号)を取り出すことができる．

文字列位置の取得を行う簡単な例を示す (report-position.satyという名前で保存されているとする．)．

% report-position.saty
@require: stdjareport

let-inline \report-position@ ~posmsg =
  ~(
    let (ipos,msg) = posmsg in
    let (fname,line,col) = get-input-position ipos in
    &(
      let it-msg = embed-string ~(lift-string msg) in
      let it-fname = embed-string ~(lift-string fname) in
      let it-line = embed-string (arabic ~(lift-int line)) in
      let it-col = embed-string (arabic ~(lift-int col)) in
        {#it-msg; (at #it-fname;:#it-line;:#it-col;)}
    )
  )

in

document (|
  title = {Test of reporting position};
  author = {sankantsu};
|) '<
   +p {
     \report-position@ ~(@`Hello!`);
   }
>

コンパイルすると，本文としてHello! (at report-position.saty:24:27)という文字列が得られ，文字列の先頭位置が取得できていることがわかる．

文字列の途中の位置を取得したい場合には，文字列をパースしていくときに同時に文字列中での現在位置を追っていく必要がある．自分自身はまだ詳しく見れていないが，satysfi-base/parserなどで一応このあたりの基本的な機能は提供されているようである．

使用例: 2進文字列の10進変換

単純な例であるが，文字列で表現された2進数を10進変換して表示するマクロを作成した．

2進数表現の文字列を受け取り10進表示するマクロ\decode@を提供する．例えば，\decode@ ~(@`001011`);とすれば，11が表示できる． \decode@ ~(@`0010a1`);のように，0,1以外の文字を含めた場合には次のような表示をして停止する．

...
preprocessing 'decode-binary.satyh' ...
preprocessing 'stdjareport.satyh' ...
preprocessing 'test.saty' ...
! [Error during Evaluation] test.saty:21:31: error of decode-binary: invalid character 'a'

出力されるログから，プリプロセス中にエラー検出がなされていることが確認できる．

実装と使用例を次に示す．

% decode-binary0.satyh
@stage: 0
@require: list
@require: base/char
@require: base/string

module DecodeBinary0 : sig

  val decode : input-position * string -> int

end = struct

  type digit-char =
  | Digit of int
  | UnknownCharacter of Char.t

  type result-type =
  | DecodeVal of int
  | ErrorPos of int * Char.t

  let decode-char ch =
    let char-0 = Char.make `0` in
    let char-1 = Char.make `1` in
      if Char.equal ch char-0 then
        Digit(0)
      else if Char.equal ch char-1 then
        Digit(1)
      else
        UnknownCharacter(ch)

  let decode-str str =
    let char-lst = String.to-list str in
    let-rec aux (acc,pos) lst =
      match lst with
      | [] -> DecodeVal(acc)
      | ch :: tail -> (
          match decode-char ch with
          | Digit(b) ->
              let accnew = 2*acc + b in
                aux (accnew, pos + 1) tail
          | UnknownCharacter(ch) -> ErrorPos(pos,ch))
    in
    aux (0,0) char-lst

  let decode (ipos,str) =
    let (fname,line,col) = get-input-position ipos in
    let res = decode-str str in
    match res with
    | DecodeVal(value) -> value
    | ErrorPos(pos,ch) ->
        let error-msg =
          fname ^ `:` ^ (arabic line) ^ `:` ^ (arabic (col + pos + 1)) ^ `: `#
          ^ `error of decode-binary: invalid character`
          ^ #` '` ^ (Char.to-string ch) ^ `'`
        in
        abort-with-message error-msg

end

% decode-binary.satyh
@stage: 1
@import: decode-binary0

let-inline \decode@ ~posstr =
  let num-str = arabic (~(lift-int (DecodeBinary0.decode posstr))) in
    embed-string num-str

% test.saty
@require: stdjareport
@import: decode-binary

let num-iter = 3000
let text = {The quick brown fox jumps over the lazy dog.}
let-rec repeat n x = if n <= 0 then [] else (x :: (repeat (n - 1) x))
let long-text =
  repeat num-iter text
    |> List.fold-left (fun lhs rhs -> {#lhs; #rhs;}) {}

in

document (|
  title = {Decode binary digits};
  author = {sankantsu};
|) '<
   +p {
     #long-text;
   }
   +p {
     001011: \decode@ ~(@`0010a1`);
   }
>

実装に関してはそれほど凝ったことはしていないので，詳しくは説明しない．基本的には文字列を前から読んで2進数の値を計算していき，0,1以外の文字が来たらエラーを出力して停止するだけである．

ソースコードはレポジトリにもまとめてある．

github.com

参考資料

マクロに関する資料は現状非常に少ない．

マクロでコード中の位置を取得・使用する機能 · gfngfn/SATySFi Wiki · GitHub

gfngfn 氏のエラー位置報告機能に関する紹介．

コード中の位置を取得してエラー報告できるDSLのパッケージを試しに創ってみた · gfngfn/SATySFi Wiki · GitHub

同じく gfngfn 氏によるやや複雑なDSLによるデモ．本記事より複雑な例を見たい場合は実装を読んで見ると良いと思う．

2022-08-19

SATySFi の多段階計算入門

SATySFi

この記事について

SATySFi には多段階計算という機構があり，文書のプリプロセスに利用することができる．

ただ，現状まとまった資料がないので使ってみようと思っても敷居が少し敷居が高い．この記事は多段階計算について，

何のためにあるのか
どうやって書くのか

といった部分の基本を入門向けにまとめる試みである．

SATySFiのバージョンは0.0.7に基づいている．推測に基づいて書いている部分もあるので，間違っている箇所があったら遠慮なく指摘してほしい．

なお，前提としてSATySFiの通常のコマンド定義等は知っているものとしている．

多段階計算とは

多段階計算は，プログラムの評価を多段階に分けて処理する機構である．

それぞれの段階をステージと呼び，stage 0 -> stage 1 -> ... -> stage (n-1)の順で評価を行う． stage 0を評価するとstage 1のプログラムが出力され，stage 1を評価するとstage 2のプログラムが出力され，... といった具合で処理が進む．つまり，あるステージは次のステージのためのプリプロセス的な役割を行うことができる．

SATySFi の多段階計算の動機

SATySFi は組版処理に特化した言語であり，型検査による組版処理開始前のエラー報告が大きな強みである．

一方，組版処理においては文書を生成するという役割上，比較的複雑な処理でも簡潔に記述できることが望まれる．このような要求に対処する方法として，文字列を解釈するような言語内DSL(domain specific language)を設計して使うという方法がある．

ここで，通常DSLが解釈されるのは文書の組版処理と同じタイミングであるため，DSLの入力にエラーがあった場合にこのエラーが発見されるのは組版処理中である．したがって，例えば500ページの文書を組版するのにエラー箇所が490ページ目であればそこまでの490ページ分の組版処理が終わってから初めてエラーが発見されて処理が中止され，そこまでの組版結果は無駄になってしまう．

そこで，多段階計算を導入してプリプロセスの段階でDSLの解釈を行うことで全体の文書の組版を開始する前にエラー報告を行うことができるようにしたいという動機がある．

SATySFi では2段階の計算をサポートしており，stage 0とstage 1が存在する． stage 0でstage 1のプリプロセスを行う間にエラーを発見することで，迅速なエラー報告を行うことができるようになる．

文法と評価規則

肝となる文法は次の2つである．

stage 1のプログラム中に，~(...)という記法によってstage 0のコードを埋め込むことができる．
stage 0のプログラム中に，&(...)という記法によってstage 1のコードを埋め込むことができる．

SATySFiの文書ファイルはstage 1のプログラムとして解釈する．

stage 1のプログラム中に~(...)という式が現れたら，stage 1の評価を行う前に~(...)の中身をstage 0のプログラムとして評価する． stage 0の評価の結果が&(exp)(expはstage 1の式)という形になればstage 0の評価は終了し，~(&(exp))全体をexpで置き換える．

非常に単純な例として，1 + ~(&2)というstage 1のコードを考える． stage 1の評価を始める前に，~(&2)の中身&2をstage 0のプログラムとして評価する． 2は整数を表すstage 1の式なので，&2はすでに&(stage 1 の式)という形になっている．したがってstage 0の評価は直ちに終了して~(&2) -> 2という置き換えが行われ，元のプログラムは1 + 2というstage 1のコードになる．

上の例は実質的にstage 0で何もしていないのであまり意味がないが，もちろんstage 0の上でいろいろな計算を行うことができる．後から，もう少し複雑な例についても考えていく．

stage の指定

SATySFi では，ファイル冒頭にステージの指定@stage: ...を書くことでそのファイルがどのステージに関するコードかを記述する．指定できるのは，次の3つである．

@stage: 0: stage 0のコード
@stage: 1: stage 1のコード
@stage: persistent: stage 0, stage 1どちらでも使えるコード(後述)

プリプロセス用の関数を定義したいなら，基本的に@stage: 0のファイル内で書くことになる．

指定を省略した場合，デフォルトで@stage: 1と等価になる．文書ファイルに対するステージの指定は@stage: 1でなければならない．

@stage: persistentは少し特殊で，stage 0とstage 1両方で使えるコードを記述する．ただし，~(...)や&(...)のステージをまたぐ文法を使うことはできない．例えば，標準ライブラリのlist.satygなどはpersistentである．

ファイル間の依存関係において，次の制約を満たす必要がある．

@stage: 0のファイルは@stage: 1のファイルに依存してはいけない．
@stage: persistentのファイルは@stage: 0,@stage: 1のファイルに依存してはいけない．

型システム

SATySFi の多段階計算では，int,string,int -> intといった普通の基本型や関数型に加えて，&(...)で表される "1つ上のステージのコードを表す型" を導入している．例えば，stage 0 での &int型というのは，"stage 1 でintとして評価されるコードの型" である．

ステージ間に関する型の規則として次の2つが要求される．

stage 1でτ型の値が要求される部分にstage 0のコードの埋め込み~(exp)がある場合，expはstage 0で&τ型が付かなければならない．
stage 0で&τ型の値が要求される部分にstage 1のコードの埋め込み&(exp)がある場合，expはstage 1でτ型が付かなければならない．

このような型システムによって，stage 0のプリプロセスによって生成されたstage 1のコードが正しく型付けされたコードになっていることが保証される．

少し複雑な例

次のようなプログラムを考える．

% stage 1
let n = 100 in
  ~( let double x = &(~x + ~x) in double &n )

それぞれの変数のステージと型をまとめると，次のようになっている．

n: stage 1のint
x: stage 0のint&
double: stage 0の&int -> &int

基本として，stage 0の変数はstage 0のコード中でしか使えないし，stage 1の変数はstage 1のコード中でしか使えない．特に，stage 0中の&τ型の変数と，stage 1中のτ型の変数は別物であるという点に注意しておくべきだろう．

中身について少し詳しく見てみる．まずは関数定義を見てみる．

% stage 0
let double x = &(~x + ~x)

&(...)に囲まれた部分はstage 1のコードであるから，~x + ~xをstage 1の式として解釈する． +は左右にintをとり，int型の値を返す二項演算子であるから，~xや~x + ~xはstage 1でint型が付かなければならない．従って上に述べた型付け規則から，xはstage 0で&int型が付かなければならない． &(~x + ~x)はstage 0で&int型の値であるから，doubleの型は&int -> &intである．

次に関数適用に注目する．

% stage 0
double &n

nはstage 1でint型の変数として宣言されているので，&nはstage 0で&int型の値である．

doubleの定義を思い出すと，stage 0は次のように評価される．

~(double &n)
-> ~(&(~(&n) + ~(&n)))
-> ~(&(n + n))
-> (n + n)

つまり，元のプログラムはstage 0のプリプロセスが終わると，全体let n = 100 in (n + n)というstage 1のプラグラムになっていることがわかる．

もう少し実用的な例: 累乗関数の生成

プリプロセスの目的として，エラー報告の迅速化以外だけでなく，事前計算による高速化がある．下の関数はpower 3のように書くことで(fun x -> x * x * x * 1)のようなコードを生成し，実行時の再帰をなくすことで処理が高速化できることが期待される．

@stage: 0

let power n =
  let-rec aux n x =
    if n <= 0 then &1 else &(~x * ~(aux (n - 1) x))
  in
  &(fun x -> ~(aux n &x))

power 3の評価の様子を下に示す．

power 3
-> &(fun x -> ~(aux 3 &x))
-> &(fun x -> ~(if 3 <= 0 then &1 else &(~(&x) * ~(aux (3 - 1) &x))))
-> &(fun x -> ~(&(x * ~(aux 2 &x))))
-> &(fun x -> ~(&(x * ~(if 2 <= 0 then &1 else &(~(&x) * ~(aux (2 - 1) &x))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(aux 1 &x))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(if 1 <= 0 then &1 else &(~(&x) * ~(aux (1 - 1) &x))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * ~(aux 0 &x))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * ~(if 0 <= 0 then &1 else ~(aux (0 - 1) &x)))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * ~(&1))))))))
-> &(fun x -> ~(&(x * ~(&(x * ~(&(x * 1)))))))
-> &(fun x -> ~(&(x * ~(&(x * (x * 1))))))
-> &(fun x -> ~(&(x * (x * (x * 1)))))
-> &(fun x -> (x * (x * (x * 1))))
~(power 3)
-> ~(&(fun x -> (x * (x * (x * 1)))))
-> (fun x -> (x * (x * (x * 1))))

stage 0 から stage 1 への値の移動

stage 0で何らかの計算を行ってその結果をstage 1のコード中で使いたいとする．例えば，stage 0で足し算を行うなら~(1 + 2)のように記述すれば良いが，結果として出てくる3はstage 0のintであってstage 1のintではないのでそのままではstage 1のコード中に埋め込めない．

このようなとき，lift-string : int -> &intというプリミティブを使うと，stage 0における計算結果をstage 1に埋め込めるようにすることができる．上の例であれば ~(lift-int (1 + 2))とすればlift-int (1 + 2) = lift-int 3が評価され，"3を表すstage 1のコード" を埋め込むことができる．

現状は，lift-int,lift-float,lift-string,lift-lengthの4つのプリミティブが提供されているが，将来的には任意の型に使えるlift : 'a -> &'aに置き換わる可能性がある．

汎用のliftが無い場合でも，たとえばlist型のlift関数は次のようにして実装できる．

@stage: 0
@require: list

let lift-list liftf lst =
  let codeacc =
    lst |> List.fold-left (fun codeacc x ->
             &(~(liftf x) :: ~codeacc))
             &[]
  in
  &(List.reverse ~codeacc)

lift-list : ('a -> &'a) -> 'a list -> &('a list)は，リストの各要素をliftする関数とリストを受け取って，リスト全体をliftしたものを返す．

参考記事

本記事を執筆するにあたって参考にした記事・スライドをいくつか挙げる．

github.com

多段階計算導入前の gfngfn 氏 (SATySFi開発者) の記事．モチベーションやおおまかなアイデアが描かれている．

多段階計算の型システムの基礎 from T. Suwa

www.slideshare.net

同じく gfngfn 氏のスライド．多段階計算の型システムに関する解説．直観的な図を使って説明していてわかりやすい．

qiita.com

zr_tex8r 氏の記事．文字列の16進数を解釈するコマンドを題材にした多段階計算の利用．

keens.github.io

keen 氏のスライド．多段階計算を利用した正規表現のコンパイル．

2022-07-22

SATySFi の set-math-char プリミティブで遊ぶ

SATySFi

概要

SATySFi に比較的最近追加された set-math-char という数式モード内での入出力文字の対応を指定するためのプリミティブで遊んでみたという話

set-math-char の仕様 (推測込み)

SATySFi version 0.0.7 で追加された set-math-char というプリミティブがある．以下は，CHANGELOGからの抜粋

Add primitive set-math-char : int -> int -> math-class -> context -> context for handling various Unicode code points in the math mode.

CHANGELOGの説明にあるように，数式モード内でUnicode文字を扱うためのプリミティブであるようである．しかし，比較的新しいプリミティブであるため既存のドキュメントには記載がないようである．

動作を確認するため，ソースをのぞいてみると次の箇所が関係ありそうである．

let def =
  Instruction.(
    [
    (* ... *)
    ; inst "PrimitiveSetMathChar"
        ~name:"set-math-char"
        ~type_:Type.(tI @-> tI @-> tMATHCLS @-> tCTX @-> tCTX)
        ~fields:[
        ]
        ~params:[
          param "cp_from" ~type_:"int";
          param "cp_to" ~type_:"int";
          param "mk" ~type_:"math_class";
          param "(ctx, ctxsub)" ~type_:"context";
        ]
        ~is_pdf_mode_primitive:true
        ~is_text_mode_primitive:true
        ~code:{|
let uch_from = Uchar.of_int cp_from in
let uch_to = Uchar.of_int cp_to in
let mkmap = ctx.HorzBox.math_class_map in
Context(HorzBox.({ ctx with
  math_class_map = mkmap |> MathClassMap.add uch_from (uch_to, mk);
}), ctxsub)
|}
    (* ... *)
]

このあたりを見て推測するに，set-math-charは次のような仕様と思われる．

ctx |> set-math-char cp-from cp-to mk によってコンテキストctxを変換すると，変換後のコンテキストでは，数式(${...})中で Unicode コードポイントcp-from をもつ入力文字を cp-toの Unicode文字として出力する．空白の扱いは mk で指定した数式クラスに準ずる．

cpは code point の略のようである．

遊んでみる

set-math-charを使って，数式内の文字 a,b,c をギリシャ文字 $\alpha, \beta, \gamma$ に変化させてみる．使用したソースは以下

@require: stdjareport

let-inline ctx \alph-to-greek m =
    let cp-table =
        [
            (0x0061, 0x1D6FC); % a,alpha
            (0x0062, 0x1D6FD); % b,beta
            (0x0063, 0x1D6FE); % c,gamma
        ]
    in
    let-rec aux ctx cp-table =
        match cp-table with
        | [] -> ctx
        | (cp-from,cp-to) :: tail ->
              let nctx = ctx |> set-math-char cp-from cp-to MathOrd in
              aux nctx tail
    in
    let nctx = aux ctx cp-table in
    embed-math nctx m

in

document (|
    title = {Test of set-math-char primitive};
    author = {sankantsu};
|) '<
     +p {
         before set-math-char: ${abc}
     }
     +p {
         after set-math-char: \alph-to-greek(${abc});
     }
>

alph-to-greekの中身を簡単に説明すると，cp-tableという変数に格納したコードポイントの対応を set-math-char を使って順番に適用してコンテキストを変換し，最後に，変換後のコンテキストnctx で数式を読み込んで文書中に埋め込む．

satysfiでコンパイルすると以下のような出力が得られ，文字が変換されていることがわかる．

生成したpdf

2022-06-26

ABC257 感想・反省

競プロ

atcoder.jp

結果

atcoder.jp

ABCD4完(74:55 + 4ペナ)

Performance: 1175
Rate: 1293 -> 1280 (-13)

しょうもないWAが多く冴えない回だった

コード

github.com

各問題の振り返り

A

特定のパターンの文字列の $X$ 文字目を取り出す問題

文字列を実際につくらなくても，割り算して何種類目の文字か数えればいい．

いきなり1WA．原因は大文字を出力しなければいけないのに小文字にしてしまったこと

6:42 (+ 1WA)

B

コマの動きをシミュレーションして最終配置を求める問題

コマが追い越さないことを利用して問題を読み変えると少し楽になる．

ここで3WAも出してしまう．原因は， $Q$ の値だけ制約が少し大きいのを見逃して，メモリの確保が足りていなかったこと．原因に気づくのに時間がかかりかなりロスしてしまった．

22:24 (+ 3WA)

C

単純なしきい値を用いた判定器の正解率を最大化する問題

一番簡単なのはしきい値で全探索することだが，候補が[tex: 10⁹]程度あるので無理．実際にはしきい値は与えられた体重のどれか(または体重の最大値より大きい値)だけ考えれば十分なので，これで候補数を $O(N)$ に減らせる．ただし，各しきい値に対して正解数の計算は安直にやると $O(N)$ かかるのでまだ少し工夫がいる．大人，子供それぞれの体重をソートしておいて，各しきい値の候補に対して正しく判定される大人と子供の人数をそれぞれソート済みの配列に対する2分探索で計算することによって $O(N \log N)$ で解いた．

16:16

D

任意のジャンプ台の間を移動できるようにするための条件を求める問題

訓練の回数を増やすと，飛び移れるジャンプ台の数が増えることはあっても減ることはない
訓練回数を固定すれば，条件を満たすかどうかは比較的簡単に判断できる

という点を考慮すると，訓練の回数について2分探索するのが良さそうである．実際条件を満たすかの判定については，ジャンプ台 $i$ からジャンプ台 $j$ に飛び移れるときに $i\to j$ の辺を張ったようなグラフを考えて，すべての始点からDFSなりBFSなりして到達可能性を調べることでできる([tex: O(N³)])．

デバッグのためにいれた出力自体が間違っているというしょうもない理由で手間取り，ここでも時間ロスした．

30:33

E

与えられた予算で最大の数字をつくる問題

はじめ，残っている予算に対してその時点でつくれる数字の最大値をDPで求めていけばよさそうと考えた．一見すると $O(N)$ で良さそうなのだが，整数の桁あふれが問題になる．多倍長整数を使えばできそうに見えるが，整数の桁が $O(N)$ になるので，整数の計算やコピーに $O(N)$ かかることになり実は全体で[tex: O(N²)]になってしまう．

解決策が思い浮かばず時間切れ．

終了後解説を見て通した．桁数に注目するという考察ができていなかった．以前もD - At Most 3 (Contestant ver.)で失敗したが，10進の桁に注目する考察が苦手なのかもしれない．

2022-06-19

ABC256 感想・反省

競プロ

atcoder.jp

結果

atcoder.jp

ABCDE5完(57:45 + 1ペナ) Performance: 1544

大きく詰まるところはなく5完できたのでとりあえず満足．

コード

github.com

各問題の振り返り

A

$2^ N$ を出力するだけ

cmath の pow 関数は浮動小数点で計算するので，一応整数型で pow を自前で実装．一応 long 型にしておいたが，制約的には int でも大丈夫なはず．

2分26秒

B

野球っぽいルールに従って得点を数える

累積和で効率的にできそうなことは気づいたが計算量は余裕があるため，問題文どおりに愚直にシミュレーションしたほうが実装ミスは少ないと判断．

5分23秒

C

3x3マスの盤面において，縦横の和が指定されたときのありうる盤面数を数える (俗に言う魔法陣)

基本はありうる数字の埋め方について全探索だが，9マスぶんの数字の埋め方のパターンは $30^ 9$ で大きすぎる．探索する数を減らすため盤面の自由度を考えてみると，左上4マスだけ埋めればあとは自動的に決まることに気づく．もっと盤面が大きければ DFS などで探索したいが，たかが4つなので4重for文の雑なコードで済ませた．