「Julia言語で入門するプログラミング」第14回である。未読の方は第1回〜第13回読んで欲しい。

一覧はこちら

全角半角の改善

前回までで全角と半角の判定方法がわかった。かなり寄り道してしまったが、もともとやりたかった文字スペースの調整を行おう。

まずは、前回作成した"全角半角判定.jl"を組み込もう。"全角半角判定.jl"にはテストコードも含まれているので、それらは分離する。ちょっと長いが不要な関数を削除したりしたので全文記載しておく。"EastAsianWidth.txt" も忘れずにフォルダに配置しよう。

#全角半角判定.jl
struct EastAsianWidthMatcher_単一コードポイント
    reg
end
function EastAsianWidthMatcher_単一コードポイント()
    EastAsianWidthMatcher_単一コードポイント(r"^([0-9A-F]{4});(F|H|W|Na|A|N) *#.*$")
end
function Base.occursin(matcher::EastAsianWidthMatcher_単一コードポイント, 定義行)
    return occursin(matcher.reg, 定義行)
end
struct EastAsianWidthMatcher_範囲コードポイント
    reg
end
function EastAsianWidthMatcher_範囲コードポイント()
    EastAsianWidthMatcher_範囲コードポイント(r"^([0-9A-F]{4}..[0-9A-F]{4});(F|H|W|Na|A|N) *#.*$")
end
function Base.occursin(matcher::EastAsianWidthMatcher_範囲コードポイント, 定義行)
    return occursin(matcher.reg, 定義行)
end
for (tp, f) in [(:EastAsianWidthMatcher_単一コードポイント, :(==))
                (:EastAsianWidthMatcher_範囲コードポイント, :in)]
    @eval begin
        function east_asian_width特性抽出(matcher::$tp, コードポイント, 定義行)
            m = match(matcher.reg, 定義行)
            定義行中コードポイント = eval範囲コードポイント(m.captures[1])
            if $f(コードポイント, 定義行中コードポイント)
                east_asian_width = m.captures[2] 
                return (true, east_asian_width)
            else
                return (false, nothing)
            end
        end        
    end
end
function get_east_asian_width(コードポイント, 定義行)
    matchers = [
        EastAsianWidthMatcher_単一コードポイント()
        EastAsianWidthMatcher_範囲コードポイント()
    ]
    for matcher in matchers
        if occursin(matcher, 定義行)
            return east_asian_width特性抽出(matcher, コードポイント, 定義行)
        end
    end
    return (false, nothing)
end
function get_east_asian_width(コードポイント)
    path = joinpath(@__DIR__, "EastAsianWidth.txt")
    lines = open(path, "r") do f
        readlines(f)
    end
    for 定義行 in lines
        can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
        if can_match
            return east_asian_width
        end
    end
end
function 十六進数prefix付与(範囲コードポイント)
    function prefix付与(s)
        return "0x" * s
    end
    return replace(範囲コードポイント, r"[0-9A-F]{4}" => prefix付与)
end
function eval範囲コードポイント(範囲コードポイント)
    range = 十六進数prefix付与(範囲コードポイント) #"0x0041..0x005A"という文字列に変換
    code_str = replace(range, ".." => ":") #"0x0041:0x005A"という文字列に変換
    expr = Meta.parse(code_str) #:(0x0041:0x005A) という抽象構文木に変換
    return eval(expr) #抽象構文木を評価
end
function is全角byEastAsianWidth特性(e)
    if !(e in ["Na", "N", "W", "F", "H", "A"])
        throw(DomainError("無効なeast_asian_width特性です"))
    end
    return e in ["W", "F", "A"]
end
function is全角(c)    
    コードポイント = Int(c)
    e = get_east_asian_width(コードポイント)
    return is全角byEastAsianWidth特性(e)
end
function is半角(c)
    return !is全角(c)
end

#全角半角判定_test.jl
include("全角半角判定.jl")
@testset "単一コードポイント" begin
    s = "0020;Na          # Zs         SPACE"
    @testset "正常取得" begin
        @test get_east_asian_width(0x0020, s) == (true, "Na")
    end
    @testset "境界値検査" begin 
        @test get_east_asian_width(0x001F, s) == (false, nothing)
        @test get_east_asian_width(0x0021, s) == (false, nothing)
    end
end
@testset "範囲コードポイント" begin
    s = "0041..005A;Na    # Lu    [26] LATIN CAPITAL LETTER A..LATIN CAPITAL LETTER Z"
    @testset "正常取得" begin
        @test get_east_asian_width(0x0041, s) == (true, "Na")
        @test get_east_asian_width(0x0059, s) == (true, "Na")
        @test get_east_asian_width(0x005A, s) == (true, "Na")
    end
    @testset "境界値検査" begin 
        @test get_east_asian_width(0x0040, s) == (false, nothing)
        @test get_east_asian_width(0x005B, s) == (false, nothing)
    end
end
@testset "ファイルから取得" begin
    @testset "単一コードポイント" begin
        @test get_east_asian_width(0x0020) == "Na"
    end
    @testset "範囲コードポイント" begin
        @test get_east_asian_width(0x00BD) == "A"
    end
end
@testset "parse範囲コードポイント" begin
    s = "0041..005A"
    @test parse範囲コードポイント(s) == 0x0041:0x005A
end
@testset "eval範囲コードポイント" begin
    s = "0041..005A"
    @test eval範囲コードポイント(s) == 0x0041:0x005A
end
@testset "全角判定byEastAsianWidth特性" begin
    @testset "全角" begin
        @test is全角byEastAsianWidth特性("W") 
        @test is全角byEastAsianWidth特性("F")
        @test is全角byEastAsianWidth特性("A")
    end
    @testset "半角" begin
        @test !is全角byEastAsianWidth特性("Na") 
        @test !is全角byEastAsianWidth特性("N")
        @test !is全角byEastAsianWidth特性("H")
    end
end
@testset "全角半角判定" begin
    @testset "全角" begin
        @test is全角('あ') 
        @test is全角('ア')
        @test is全角('Ａ')
        @test is全角('雨')
        @test is全角('　')
        @test is全角('ー')
    end
    @testset "半角" begin
        @test is半角('a') 
        @test is半角('A')
        @test is半角('1')
        @test is半角('ｱ')
        @test is半角(' ')
        @test is半角('-')
    end
end

"game_test.jl"を実行したときに、同時に"全角半角判定_test.jl"も動くようにしておく。

#game_test.jl
module GameTest
include("game.jl")
include("全角半角判定_test.jl")
...

これで準備はOKだ。さあ、さあ、さあ、始めよう！！

スペースを入れて幅を調整するために、下記の"戦況表示"関数の中で$(c.名前)としているところを工夫する必要がある。

function 戦況表示(プレイヤーs, モンスターs)
    function 表示(c::Tキャラクター)
        s = "$(c.名前) HP:$(c.HP) MP:$(c.MP)"
    ...
end

まずは文字数に関する制限を再確認しておこう。文字列の幅は、全角幅で8文字分、半角幅で16文字分になるようにする半角スペースを入れて調整する。「ドラゴン」という名前であれば、全角4文字なので後ろに半角スペースを8個入れることになる。「tarou」という名前であれば、半角5文字なので後ろに半角スペースを11文字入れることになる。

これを実現する"名前表示調整"関数を作ろう。まずテストはこのような感じである。わかりづらいが、半角幅で16文字となるようにスペースで埋めている。

#game_test.jl
@testset "名前表示調整" begin
    @test 名前表示調整("a") == "a               "    
    @test 名前表示調整("ab") == "ab              "    
    @test 名前表示調整("あ") == "あ              "
    @test 名前表示調整("太郎") == "太郎            "
    @test 名前表示調整("tarou") == "tarou           "
    @test 名前表示調整("1234567890123456") == "1234567890123456"
    @test 名前表示調整("ドラゴン") == "ドラゴン        "
    @test 名前表示調整("ドラゴンドラゴン") == "ドラゴンドラゴン"
end

これを実装するのは簡単だ。次のようになる。

#ui_helpter.jl(新規ファイル)
include("全角半角判定.jl")
function 名前表示調整(名前)
    function 文字幅(文字)
        if is半角(文字)
            return 1
        elseif is全角(文字)
            return 2
        else 
            throw(ArgumentError("不正な文字です"))
        end
    end
    function 必要な半角スペース(名前)
        最終文字列幅 = 16
        名前文字列幅 = sum(文字幅(x) for x in 名前)
        n = 最終文字列幅 - 名前文字列幅
        return " "^n
    end
    return 名前 * 必要な半角スペース(名前)
end

関数そのものには特に説明することはないが、この関数の定義場所については補足しておく必要がある。まあ別に本質的な問題でもなんでもなく、ただの技巧上の問題に過ぎないが、一応説明しておく。

普通に考えればこの関数は、"戦況表示"関数のある"ui.jl"の中に定義すれば良い。しかし、"game_test.jl"の関数は、"ui.jl"をincludeしないことを思い出そう。そのため、"ui_helper.jl"というファイルを新たに作り、そこに"名前表示調整"関数を定義する。あとは、"ui_helper.jl"を"ui.jl"と"game_test.jl"それぞれでincludeすれば良い。helperという名前に特にこだわりがあるわけではなく、"ui_util"みたいな名前でも良かったのだが、utilityというと便利ツールとして独立して使えるようなイメージがある。今回の処理は完全に"戦況表示"関数の補助の役割であって、独立して使うイメージがないため、utilityではなくhelperという名前にした。一般的にも使い分けは微妙なところだ。

それはそれとして、今回作った関数を"戦況表示“関数へ実際に組み込んでみよう。

#ui.jl
function 戦況表示(プレイヤーs, モンスターs)
    function 表示(c::Tキャラクター)
        s = "$(名前表示調整(c.名前)) HP:$(c.HP) MP:$(c.MP)"
    ...
end

これで期待した通りに表示される。

しかし問題がある。動かしてみると、動くには動くのだが、悲しいくらいに遅い。どうすればいいだろうか？

ファイルデータのキャッシュ

原因はまだはっきりとしないが、心当たりはある。ユニコードの全角と半角を判定しよう でも触れているが、コードポイントを1文字処理するたびに"EastAsianWidth.txt"を全行読み取っているからである。

さて、このコードはコードポイントを1つ判定するたびに、ファイルを開いて全行読み込んでいる。ディスクIOというのは最も遅い部類の処理なので、パフォーマンスの観点から言うと最悪のコードだ。が、まあ今のところは速度懸念も出ていないので、ひとまずこのままにしよう。気になるのであれば好きなように改善して欲しい。

https://muuumin.net/unicode-width/

「今のところは速度懸念も出ていない」などと書いておきながら一瞬で出てしまって恥ずかしいのだが、ともかく戦略はこうだ。今はファイルからデータをいちいち読み取っているが、これを一度だけファイルから読み取ってしまい、メモリ中に確保してしまうようにしよう。このように実際のデータの配置場所から取得すると時間がかかるときに、高速にデータを取得できる場所に一時的にデータを置くことを「キャッシュする」と呼ぶことがある。

"get_east_asian_width"関数を見てみよう。この関数の中では、"EastAsianWidth.txt"を全行読み込んでいる。

function get_east_asian_width(コードポイント)
    path = joinpath(@__DIR__, "EastAsianWidth.txt")
    lines = open(path, "r") do f
        readlines(f)
    end
    ...
end

この部分を改善したい。テキストファイルの中身を配列に保存しているが、この配列を一度作ったら以後使い回したいという意図だ。実現手段はいくらか考えられる。例えばゲームの開始時に"EastAsianWidth.txt"ファイルを開いて読み取って配列に保存しておき、"is全角"とか"get_east_asian_width" 関数はその配列を引数として受け取る、というような形だ。うーん、まあ、どうしてもというのであればそれでもいい。しかし、文面から伝わるように、私はあまり乗り気ではない。

というのが、"get_east_asian_width"関数と"EastAsianWidth.txt"というのは不可分の存在に思えるためだ。なるべくなら両者を切り離したくない。"EastAsianWidth.txt"を格納する変数が"get_east_asian_width"関数とは全然関係ないところで作られて、それを外から渡してくるのではなく、極力関数に近いところで処理をしたい。今は単純なローカル変数なので、完全に関数内で完結している。しかしローカル変数だと関数を抜けると破棄されてしまうので、キャッシュのための変数としては使うことはできない。このための常套手段がクロージャである。

ゲームの開始時の処理で次のようなコードを作ったのを覚えているだろうか？

function main(乱数生成器)
    ...
    描画ツール = create描画ツール()
    モンスター遭遇イベント通知!([モンスター遭遇イベントui処理!], 描画ツール)
    ...
end

やりたいことはこれと同じである。まずクロージャを作る。そのタイミングで"EastAsianWidth.txt"を読み取り、クロージャ内部の変数を初期化する。その後クロージャはその変数を参照するようにすれば、重たいファイル読み取りの処理は一度きりで済む。早速やってみよう。

まずクロージャで最終的に提供したい関数は、"is全角", "is半角"関数である。そしてこれらの関数が利用するのが"get_east_asian_width"関数であり、この関数にキャッシュ対応を効かせたい。

@timeマクロでの計測

キャッシュ対応を入れる前に今の"is全角"関数の速度を測定しておこう。対応を入れた後でどのくらい改善したかを確認する。Juliaでその度を計測するのは簡単で、"@time"というマクロを使うと良い。

julia> @time is全角('あ')
  0.150258 seconds (108.14 k allocations: 5.934 MiB, 20.18% compilation time)
true
julia> @time is全角('あ')
  0.117154 seconds (82.65 k allocations: 4.279 MiB)
true
julia> @time is全角('あ')
  0.116560 seconds (82.65 k allocations: 4.279 MiB)
true

1回目の呼び出しは約0.15秒、2回目以降は約0.11秒程度のようだ。

キャッシュ対応

では改めてキャッシュ対応を入れる関数を確認してみよう。

#全角半角判定.jl
function get_east_asian_width(コードポイント)
    path = joinpath(@__DIR__, "EastAsianWidth.txt")
    lines = open(path, "r") do f
        readlines(f)
    end
    for 定義行 in lines
        can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
        if can_match
            return east_asian_width
        end
    end
end

変数"lines"がキモである。この変数にファイルの中身を読み込むのをクロージャの初期化の一度きりにしたいのだ。こんな感じになる。

#全角半角判定.jl
struct 全角半角判定器
    is全角
    is半角
end
function create全角半角判定器()
    #クロージャの作成時にlines変数に"EastAsianWidth.txt"の中身を保持するようにした
    path = joinpath(@__DIR__, "EastAsianWidth.txt")
    lines = open(path, "r") do f
        readlines(f)
    end
    function get_east_asian_width(コードポイント, 定義行)
        ...
    end        
    function get_east_asian_width(コードポイント)
        #都度"EastAsianWidth.txt"を読み込むのはやめた
        for 定義行 in lines
            can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
            if can_match
                return east_asian_width
            end
        end
    end    
            
    function is全角byEastAsianWidth特性(e)
        ...
    end    
    function is全角(c)    
        ...
    end
    function is半角(c)
        ...
    end
    return 全角半角判定器(is全角, is半角)
end

関数がクロージャの中身に閉じ込められたことで、"is全角"、"is半角"はクロージャ経由でアクセスする必要がある。

#game_test.jl
@testset "名前表示調整" begin
    判定器 = create全角半角判定器()
    @test 名前表示調整("a", 判定器) == "a               "    
    @test 名前表示調整("ab", 判定器) == "ab              "    
    @test 名前表示調整("あ", 判定器) == "あ              "
    @test 名前表示調整("太郎", 判定器) == "太郎            "
    @test 名前表示調整("tarou", 判定器) == "tarou           "
    @test 名前表示調整("1234567890123456", 判定器) == "1234567890123456"
    @test 名前表示調整("ドラゴン", 判定器) == "ドラゴン        "
    @test 名前表示調整("ドラゴンドラゴン", 判定器) == "ドラゴンドラゴン"
end

#ui_helper.jl
function 名前表示調整(名前, 全角半角判定器) #引数追加
    function 文字幅(文字)
        if 全角半角判定器.is半角(文字) #変更
            ...
        elseif 全角半角判定器.is全角(文字) #変更
            ...
        end
    end
    ...
end

同時に、クロージャの中身に押し込められ、公開もされなくなった関数がテストできなくなっている。公開していない関数はテストの意義も薄れるので、ここは潔く諦めてテストケースを削除しておこう。

さてこれでテストコードは通ると思うが、次は本体側コードである。"名前表示調整"関数に引数を追加するので、それを呼び出す"戦況表示"関数にも引数が追加になる。

#ui.jl
function 戦況表示(プレイヤーs, モンスターs, 全角半角判定器) #引数追加
    function 表示(c::Tキャラクター)
        s = "$(名前表示調整(c.名前, 全角半角判定器)) HP:$(c.HP) MP:$(c.MP)" #引数追加
        ...

さらに"戦況表示"関数の呼び出し元に引数を追加していく。

#game.jl
function main(乱数生成器)
    ...
    描画ツール = create描画ツール()
    ...
    全角半角判定器 = create全角半角判定 #追加
    描画ツール.画面更新(戦況表示(プレイヤーs, モンスターs, 全角半角判定器)) #引数追加
    ...
end

#ui.jl
function 行動決定ui処理!(行動者::Tプレイヤー, プレイヤーs, モンスターs, 描画ツール, 全角半角判定器) #引数追加
    表示文字列リスト = [戦況表示(プレイヤーs, モンスターs, 全角半角判定器) #引数追加
                    ;"$(行動者.名前)のターン"]
    描画ツール.画面更新(表示文字列リスト)
end

さて、"main"関数の方はこれでいいが、"行動決定ui処理"の方は、さらに引数を追加していく必要がある。"描画ツール"の時と同じように、これは大変な作業になりそうだ。

だがしかし待ってほしい。本当に「さらに引数を追加」する必要があるだろうか？"全角半角判定器"って何に使うんだっただろうか？そう、画面表示の見栄えを整えるのに使っているのだった。そして現状、"描画ツール"は大変な努力の末に画面描画に関わる関数に追加されている。ならば、"全角半角判定器"を、"描画ツール"に埋め込んでしまってはどうだろうか？

#ui.jl
struct 描画ツール
    画面更新
    現在表示行数加算
    ページサイズ
    全角半角判定器 #追加
end
function create描画ツール()
    ...
    return 描画ツール(画面更新, 現在表示行数加算, ページサイズ, create全角半角判定器()) #変更
end

こうすることで、"全角半角判定器"は"描画ツール"に含まれることになる。あとは"全角半角判定器"が必要になったときに"描画ツール"から引き抜いてくればいい。

結果、このような形になる。なお、"描画ツール"はテストコード側でも使うので、"ui.jl"から"ui_helper.jl"に定義場所を変えている。

#game.jl
function main(乱数生成器)
    ...    
    描画ツール = create描画ツール()
    モンスター遭遇イベント通知!([モンスター遭遇イベントui処理!], 描画ツール)
    ...
    描画ツール.画面更新(戦況表示(プレイヤーs, モンスターs, 描画ツール)) #変更
    ...
end

#ui_helper.jl
struct 描画ツール #定義場所移動
    ...
end
function create描画ツール() #定義場所移動
    ...
end
function 名前表示調整(名前, 描画ツール) #変更
    function 文字幅(文字)
        if 描画ツール.全角半角判定器.is半角(文字) #変更
            return 1
        elseif 描画ツール.全角半角判定器.is全角(文字) #変更
            return 2
        ...
        end
    end
    ...
end

#ui.jl
function 戦況表示(プレイヤーs, モンスターs, 描画ツール) #変更
    function 表示(c::Tキャラクター)
        s = "$(名前表示調整(c.名前, 描画ツール)) HP:$(c.HP) MP:$(c.MP)" #変更
        ...
end
function 行動決定ui処理!(行動者::Tプレイヤー, プレイヤーs, モンスターs, 描画ツール) #変更
    表示文字列リスト = [戦況表示(プレイヤーs, モンスターs, 描画ツール) #変更
    ...
end

#game_test.jl
@testset "名前表示調整" begin
    描画ツール = create描画ツール() #全角半角判定器ではなく、描画ツールを作るように変更
    @test 名前表示調整("a", 描画ツール) == "a               "    #引数変更
    ... #以下同様
end

これで動かしてみるとどうなるだろうか？実を言うと、私の手元では大して速くならなかった。と言うか、体感では全然変わらなかった。もう少し正確に検証しておこう。再度"@time"マクロの出番である。

julia> 判定器 = create全角半角判定器()
julia> @time 判定器.is全角('あ')
  0.382862 seconds (938.13 k allocations: 52.917 MiB, 2.21% gc time, 69.66% compilation time)
true
julia> @time 判定器.is全角('あ')
  0.121222 seconds (84.86 k allocations: 4.081 MiB)
true
julia> @time 判定器.is全角('あ')
  0.119699 seconds (84.86 k allocations: 4.081 MiB)
true

この対応前の計測結果は、初回が約0.15秒、2回目以降が約0.11秒だった。改善していないどころか、むしろわずかに悪化している。

これはファイルからの読み込み自体は実際には大きな問題なのではなく、大量のデータを都度検索するところにボトルネックがあることを示している。あるいはJuliaが賢くて、ファイルに変更がないことを検知し、再度読み込む必要はないよっ！と、裏でキャッシュ対応のようなことをやってくれているのかもしれない。

ともあれ、ファイル読み込みを無くせば高速化するであろうと言う目論見は完全に誤診であった。あわわ、大変なことになった。裁判で訴えられる前に次の手を打つ必要がある。

関数のメモ化

次に試したいのは、「メモ化」だ。メモ化というのは、キャッシュの一種である。関数を呼び出した際に、「呼び出し時の引数」と「その引数に対する関数の値」のペアをどこかにメモしておく。そうすると、同じ引数で何度も関数を呼び出す際に、一度計算した結果を使い回すことができる、というテクニックだ。

次の"get_east_asian_width"関数を例にして考えよう。

#全角半角判定.jl
function get_east_asian_width(コードポイント)
    for 定義行 in lines
        can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
        if can_match
            return east_asian_width
        end
    end
end

この関数は、与えられたコードポイントに対して、”east_asian_width"を返す。与えられたコードポイントをキーにした辞書をどこかに保持しておけば、メモ化が実現できそうだ。辞書はクロージャ内の変数として保持すれば良いだろう。簡単なので結果だけ示そう。

east_asian_widthメモ = Dict() #追加
function get_east_asian_width(コードポイント)
    if haskey(east_asian_widthメモ, コードポイント) #追加
        return east_asian_widthメモ[コードポイント] #追加
    end #追加
    for 定義行 in lines
        can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
        if can_match
            east_asian_widthメモ[コードポイント] = east_asian_width #追加
            return east_asian_width
        end
    end
end    

これに対して"@time"マクロで計測すると、ようやくはっきりとした効果を見ることができる。

julia> 判定器 = create全角半角判定器()
julia> @time 判定器.is全角('あ')
  0.435867 seconds (978.02 k allocations: 55.280 MiB, 4.38% gc time, 71.92% compilation time)
true
julia> @time 判定器.is全角('あ')
  0.005053 seconds (2.23 k allocations: 144.136 KiB, 98.73% compilation time)
true
julia> @time 判定器.is全角('あ')
  0.000037 seconds (6 allocations: 320 bytes)
true

実際にコードを動かすと、体感としても改善を実感することができるようになっている。初回の戦況表示こそ遅いが、それ以降は待たされることはない。まさに桃源郷である。

メモ化関数を一般化しよう

さて、メモ化の仕組みをよく見てみると、何か独立した処理に切り出せそうではないだろうか？ある関数を受け取り、その関数の”メモ化された”バージョンの関数を生成する、そんな関数を作りたい。

臆することはない。我々はすでにメモ化された"get_east_asian_width"関数を得ている。これを睨みながら作れば良い。

"メモ化"関数は、関数"func"を受け取って、関数"メモ化されたfunc"を返す。"メモ化されたfunc"は、引数に対する結果をメモした辞書を持つ。そして、引数をもらったらとりあえず辞書を参照し、なければ引数に関数"func"を適用して、結果を辞書に追加する。これがやりたいことの全てだ。

#メモ化.jl
function メモ化(func)
    memo = Dict()
    function メモ化されたfunc(arg)
        if haskey(memo, arg)
            return memo[arg]
        end
        val = func(arg)
        memo[arg] = val
        return val
    end
end

こうすることで、"get_east_asian_width"関数は、メモ化のことなど忘れて、本来の仕事である"east_asian_width"の検索に専念することができる。

#全角半角判定.jl
function get_east_asian_width(コードポイント)
    for 定義行 in lines
        can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
        if can_match
            return east_asian_width
        end
    end
end    
メモ化get_east_asian_width = メモ化(get_east_asian_width)

そして、実際に使用されるのは、メモ化された関数である。

#全角半角判定.jl
function is全角(c)    
    コードポイント = Int(c)
    e = メモ化get_east_asian_width(コードポイント)
    return is全角byEastAsianWidth特性(e)
end

メモ化の注意点

今取り扱っている"メモ化"関数の注意点を述べておこう。

引数が1つだけである

複数の引数に対応するには、一工夫必要だ。とはいえ、そう難しい話ではない。次のような形にすれば良い。

#メモ化.jl
function メモ化(func)
    memo = Dict()
    function メモ化されたfunc(args...; kwargs...)
        allargs = (args, kwargs)
        if haskey(memo, allargs)
            return memo[allargs]
        end
        val = func(args...; kwargs...)
        memo[allargs] = val
        return val
    end
end

"args..."についている"..."というのは可変長引数を意味しており、任意の個数の引数を受け取ることができる。受け取った引数は"args"がタプルとして保持する。";"以降の引数はキーワード引数だ。"kwargs..."と"..."がついているのは同じく可変長引数を意味する。つまり"kwargs"は可変長のキーワード引数だ。受け取った変数名と値の組は、"kwargs"がペアのタプルとして保持する。それらのタプルをひとまとめにしているのが"allargs"であり、これがメモ化の辞書のキーとなる。

メモ化された関数を何度呼び出しても副作用は最初の一度だけしか働かない。

例えば関数の中で"println"してみたり、グローバル変数を書き換えたりといった、「値を返す」以外の動作はメモ化のスコープ外だ。副作用のある関数をメモ化したければ、副作用のある部分とない部分に切り分けて、ない部分をメモ化することしかできない。

引数が可変の時

メモを参照するとき、辞書のキーになるのは引数である。引数が一致すれば保存していた値を返す。この一致という時に気になってくるのが可変のオブジェクトである。例えば、配列をキーにしていた時、その配列の中身が変わったり、配列に要素がpush!されたとしたら？同じ変数だから一致とみなされて、古い配列の時のメモが帰ってきたりしないだろうか？

これは微妙な問題である。たとえば、対象のオブジェクトが配列なのか、可変な構造体なのかでも変わる。

JuliaのDictの説明を見ると、キーの一致は"isequal"でされるとなっている。

Dict{K,V}() constructs a hash table with keys of type K and values of type V. Keys are compared with isequal and hashed with hash.

https://docs.julialang.org/en/v1/base/collections/#Base.Dict

"isequal"というのは、基本的には"=="と同じである。(ちなみに"IdDict"という辞書はキーの一致に"==="を使う。"=="と"==="って何が違うんだっけ？という人は第4回のこのあたりを参照しよう。)

Similar to ==, except for the treatment of floating point numbers and of missing values. 

https://docs.julialang.org/en/v1/base/base/#Base.isequal

そして、"=="というのは、割といい感じに一致と見做してくれる比較演算子だ。整数の1と小数の1.0を同じと判定してくれるし、配列などは内部の要素に潜り込んで一致の比較をしてくれる。

For collections, == is generally called recursively on all contents, though other properties (like the shape for arrays) may also be taken into account.

https://docs.julialang.org/en/v1/base/math/#Base.:==

例えば、配列の場合、全く別々の変数に確保した別の配列であっても、内部に保持している要素が一致していれば一致と判定してくれる。

julia> a = [1, 2, 3]
julia> b = [1, 2, 3]
julia> a == b
true
julia> c = [1.0, 2.0, 3.0]
julia> a == c
true

また、同じ配列であっても、"push!"などで変更が加わると辞書のキーとしては不一致の判定となる。

julia> d = Dict()
julia> a = [1, 2, 3]
julia> d[a] = "a"
julia> d[a]
"a"
julia> push!(a, 4)
julia> d[a]
ERROR: KeyError: key [1, 2, 3, 4] not found

この一致判定を基準にしているので、配列の場合は中身の要素が変わった後、古いメモを参照することはない。

しかし一方で、可変な構造体の時には要注意だ。この時には内部の値が変わっても辞書のキーとして一致すると判定されてしまう。

julia> mutable struct S
         a
         b
       end
julia> s = S(1, 2)
julia> d = Dict()
julia> d[s] = "s"
julia> d[s]
"s"
julia> s.a = 3
julia> d[s]
"s"

基本的にメモ化で最も懸念すべきはこの状況だ。エラーにもならず、不正確な答えが返ってしまう。テストが甘ければ簡単に見過ごしてしまう不具合となる。これは是非とも改善したいところだ。そこで次のようなテクニックをを使おう。

ハッシュ値

今起きている問題は、ここまではメモのキーとして使っている値の同値性をJulia任せにしていたことで発生している。であれば、引数が同値であるかどうかを自前で判定してあげるようにすれば、この問題は解決するはずだ。Juliaは可変な構造体の同値性は、同じメモリアドレスにあるオブジェクトであるか？という基準で判定している。そうではなく、可変な構造体の時には、オブジェクト自体の同値性に加えて、内部の変数の同値性も判断に加えてあげればいい。そのための道具が「ハッシュ値」である。

ハッシュ値の話に入る前に、少し例え話をしよう。

あなたの近所の金持ちが、押し入り強盗に現金100億円を強奪されたとする。被害者は殴られはしたものの、気絶したふりをして難を逃れていたために幸いにも命に別状はなく、犯人像を極めて詳細に説明した。貴重な目撃証言に警察は色めきたった。警察の懸命なるの結果、ほどなくして捜査線上に一人の容疑者が浮かび上がる。それがあなただ。身長190センチを超える堂々たる体躯、ギリシャ彫刻のような均整のとれた筋肉質の肉体、絶世の美女ですら頬を赤らめるほどの並外れた美貌、強靭な意志と深い知性の光を宿す瞳、聴く者全てを魅力する落ち着いたバリトンボイス。全てがあなたの特徴とよく一致していた。もちろん犯人はあなたではない。(これはネタバレになるが、犯人は生き別れの双子の兄なのだ。)しかし真犯人とあなたを見分けるのは容易ではない。よく調べれば、耳の後ろのホクロの有無とか、すね毛の本数とか、つむじの角度などに微妙な違いがあることはわかるだろう。しかしその違いを見つけ出すには長い時間がかかる。あなたは明日にも妹の結婚式を控えており、警察の見当違いの取り調べに付き合っている時間はないのだ。いきりたつ取調官にあなたは優しいバリトンボイスで囁いた。

「お願いしますよ、刑事さん。私は無関係なんです。現場に指紋は残っていないんですかね？指紋を比べていただけたら、私は犯人ではないとはっきりするんですがね。」

指紋を照合することは簡単だ。警察官はあなたの髪の毛一本一本を丹念に調べる必要はなく、ただほんの数センチのサイズの模様を確認すればいいだけだ。すぐにも結果が出たらしい。取調べ官がバツの悪そうな顔で近づいてくる。どうやら妹の結婚式には間に合いそうだ。

巨大なデータとハッシュ値もちょうどこのような関係にある。ハッシュ値というのは、任意のデータに対する「指紋」のようなものだ。何かデータを決めると、ハッシュ関数という関数によって、そのデータに対応するハッシュ値を計算することができる。ハッシュ関数には色々な種類があるが、入力するデータが同じだと、ハッシュ値は常に同じになるという性質は共通している。この性質により、２つのデータのハッシュ値が異なると、元のデータは必ず異なると言うことができる。ハッシュ値は通常、小さい固定長のデータになるように設計される。例え元のデータが何テラバイトあろうとも、ハッシュ値というのはせいぜい数百ビットのデータになる。短い事は良い事だ。2つのテラバイト級のデータが一致することを確認するには、数十分、数時間、いやひょっとすると数日かかってしまうかもしれないが、そのハッシュ値の比較は閃光のように速い。

もっともお気づきのように、ハッシュ値が同じであっても、元のデータが同じであるとは言い切れない。任意のサイズのデータを小さなデータに圧縮してしまうので、複数のデータが同じハッシュ値になるということがありえるのだ。世界中にあなたと同じ指紋を持つ人物が絶対にいないとは言い切れないのと同じだ。これをハッシュ値の衝突という。ただし、ハッシュのサイズが十分大きければ、衝突の確率を事実上無視することはできる。今回我々が使うハッシュ値も桁数が十分大きいために、偶然衝突するという可能性は無視することにする。

さて、Juliaにはハッシュ値を計算するための関数"hash"が"Base"モジュールに定義されている。"hash"の使い方は簡単で、単にオブジェクトを渡してあげるだけでいい。

julia> hash(0)
0x77cfa1eef01bca90
julia> hash(1)
0x5bca7c69b794f8ce
julia> hash([1, 2])
0x3ccbd9a80ebef2b4
julia> hash((1, 2))
0x6b582411db110482

"hash"関数に第2引数を渡すこともできる。これは複数のデータのハッシュ値を求める時に、別のデータから作ったハッシュ値を混ぜ合わせるのに使う。例えば次のように使う。次の例は、"h"という変数を経由して、配列"arr"の要素全てのハッシュ値が混ぜ合わさり、最終的に配列"arr"のハッシュ値となっている。

function f(arr::Array)
    h = UInt(0)
    for a in arr
        h = hash(a, h)
    end
    return h
end

ところでこれでは不十分だ。この関数は配列のハッシュ値を求めているが、実際には中身の要素のみで決まっている。もしもここで、タプルのハッシュ値を求める関数を次のように作リたくなったとしよう。同じ発想で次のようになるだろう。

function f(tup::Tuple)
    h = UInt(0)
    for t in tup
        h = hash(t, h)
    end
    return h
end

この二つの関数に配列"[1, 2, 3]"とタプル"(1, 2, 3)"を与えると、いずれも中身の要素にしか依存しないため、どちらも同じ値を返すことになる。これはあまり嬉しくない。配列とタプルは別のものなので、中身の要素が同じでもハッシュ値は別になって欲しい。

そこで、ハッシュ値を別にするために、それぞれの関数で適当な値を初期値にしておく。それぞれ関数で違いさえすれば良いので、適当な固定値でいい。"rand(UInt)"で生成した値を入れておこう。

function f(arr::Array)
    h = UInt(0xb205b0de6bd3ccfa)
    for a in arr
        h = hash(a, h)
    end
    return h
end

function f(tup::Tuple)
    h = UInt(0xf61e6b5d548f0c02)
    for t in tup
        h = hash(t, h)
    end
    return h
end

可変オブジェクトに対するメモ化

ハッシュ値を活用して、可変オブジェクトも含めたメモ化を実現しよう。まずは期待値をはっきりさせるためのテストを書いてみよう。

#メモ化_test.jl
mutable struct メモ化テスト用構造体
    数値
    配列
end
...
@testset "可変オブジェクトの中身が変わったとき、不要なメモを参照しないこと" begin
    @testset "配列" begin
        f(x) = sum(x)
        g = メモ化(f)
        a = [1, 2]
        @test g(a) == 3
        push!(a, 3) #[1, 2, 3]
        @test g(a) == 6
        a[1] = 10 #[10, 2, 3]
        @test g(a) == 15
    end
    @testset "構造体" begin
        f(x) = x.数値 + sum(x.配列)
        g = メモ化(f)
        s = メモ化テスト用構造体(1, [2, 3])
        @test g(s) == 6
        s.数値 = 2 #(2, [2, 3])
        @test g(s) == 7
        s.配列[1] = 20 #(2, [20, 3])
        @test g(s) == 25
        s.配列 = [10, 20] #(2, [10, 20])
        @test g(s) == 32
    end
end

配列や構造体の中身が変わったとき、古いメモを参照せず、変更後の値で関数を再計算していることのテストとなっている。では実装に入ろう。

まず"メモ化"関数そのものは次のようになっている。引数そのものではなく、引数のハッシュ値をDictのキーにしている。

#メモ化.jl
function メモ化(func)
    memo = Dict()
    function メモ化されたfunc(args...; kwargs...)
        key = メモ化用hash_allargs(args..., kwargs...) #変更
        if haskey(memo, key) #変更
            return memo[key] #変更
        end
        val = func(args...; kwargs...)
        memo[key] = val #変更
        return val
    end
end

引数のハッシュ値を求める関数が、"メモ化用hash_allargs"である。

#メモ化.jl
function メモ化用hash_allargs(args...; kwargs...)
    h = UInt(0)
    for arg in args
        h = メモ化用hash(arg, h)
    end
    for kwarg in kwargs
        h = メモ化用hash(kwarg, h)
    end
    return h
end

先程の説明ではハッシュ値の計算の初期値に"UInt(0xb205b0de6bd3ccfa)"というようなハッシュ値をつけたが、この例ではあえて"UInt(0)"にしている。"メモ化用hash_allargs"関数に類似のものがあれば区別のために初期値をつけてもいいが、今回はこの関数は唯一無二なのでこのままにしている。

"メモ化用hash"関数というのが何かというと、基本的にはただの"Base.hash"関数である。なぜ上記の関数で、直接"Base.hash"関数を利用せず、"メモ化用hash"という関数を経由しているかは、この後説明する。

#メモ化.jl
function メモ化用hash(x::Any)
    return メモ化用hash(x, UInt(0))
end

function メモ化用hash(x, h::UInt)
    return Base.hash(x, h)
end

ここからが工夫のしどころだ。

まず、可変な構造体の時には標準の"Base.hash"関数では、内部のフィールドの値の変化を検知できない。

julia> mutable struct S
         a
         b
       end
julia> s = S(1, 2)
julia> hash(s)
0x1b872280db5ddea2
julia> s.a = 3
julia> s
S(3, 2) #内部のフィールドの値が変わった
julia> hash(s)
0x1b872280db5ddea2 #ハッシュ値は変わっていない

このため、標準の"Base.hash"を使っては、結局、可変な構造体の内部フィールドが変化しても、古いメモを参照することになってしまう。

これを避けるために、対象の構造体に特化した"メモ化用hash"関数を作る。

#メモ化_test.jl
mutable struct メモ化テスト用構造体
    数値
    配列
end

function メモ化用hash(s::メモ化テスト用構造体, hsh::UInt)
    #オブジェクト自体と内部のフィールドも組み合わせてのハッシュ
    h = hsh
    h = Base.hash(s, h)
    h = メモ化用hash(s.数値, h)
    h = メモ化用hash(s.配列, h)
    return h
end

"Base.hash(s, h)"でオブジェクト自体のハッシュ値を求め、さらにその内部の値のハッシュ値と混ぜ合わせることで最終的なハッシュ値としている。こうすることで、同じ構造体の別のオブジェクトに変わった場合には別のハッシュ値となるし、同じオブジェクトのまま内部の"数値"や"配列"が変わっても別のハッシュ値となる。同じハッシュ値となるのは、同じオブジェクトのままで、かつ、内部のフィールドの値も同じ時のままのとき(あるいは無視できるくらい低い確率での偶然の衝突)だけだ。

これで最低限テストが通るはずだ。しかし、明らかにまだ改善の余地がある。今の実装だと、構造体にフィールドが増えた時には"メモ化用hash"関数をメンテナンスする必要があるし、メモ化される関数の引数となる構造体が出てくるたびに、その構造体に特化した"メモ化用hash"を作る必要がある。

まずは構造体のフィールドのハッシュ値の計算について、ベタ書きするのではなく、"propertynames"で動的に取得するようにしよう。"propertynames"の引数のfalseは、非公開のプロパティも含めて取得するという意味だ。

#メモ化_test.jl
function メモ化用hash(s::メモ化テスト用構造体, hsh::UInt)
    #オブジェクトそのものが同一で、かつ、内部のフィールドも同値
    h = hsh
    h = Base.hash(s, h)
    for p in propertynames(s, false) #変更
        h = メモ化用hash(getproperty(s, p), h) #変更
    end #変更
    return h    
end

さらに、この関数を特定の構造体に特化したものではなく、可変の構造体の時には共通で使えるものにしよう。

#メモ化.jl
function メモ化用hash(x::Any, h::UInt)
    if ismutable(x) && isstructtype(typeof(x))
        return メモ化用hash_可変構造体(x, h) 
    end
    return Base.hash(x, h)
end

function メモ化用hash_可変構造体(s, hsh::UInt)
    #オブジェクトそのものが同一で、かつ、内部のフィールドも同値
    h = hsh
    h = Base.hash(s, h)
    for p in propertynames(s, false)
        h = メモ化用hash(getproperty(s, p), h)
    end
    return h    
end

#メモ化_test.jl
#= 削除
function メモ化用hash(s::メモ化テスト用構造体, hsh::UInt)
    #オブジェクトそのものが同一で、かつ、内部のフィールドも同値
    h = hsh
    h = Base.hash(s, h)
    for p in propertynames(s, false)
        h = メモ化用hash(getproperty(s, p), h)
    end
    return h    
end
=#

これで今後、構造体のフィールドが増えたり、対象の構造体が増えても困ることは無くなった。

最後に、少し上で触れた点を補足しておこう。

“メモ化用hash”関数というのが何かというと、基本的にはただの”Base.hash”関数である。なぜ上記の関数で、直接”Base.hash”関数を利用せず、”メモ化用hash”という関数を経由しているかは、この後説明する。

なぜ"Base.hash"を特化させなかったかというと、"Base.hash"関数の影響範囲が大きいからである。"Base.hash"関数は様々なJuliaの標準関数に使われている。だれか他の人が作ったライブラリに使われていることもある。今回、可変の構造体はオブジェクトのアドレスだけでなく内部フィールドの値もハッシュの結果に含めたが、それはメモ化のためにそうしたいのであって、他の場面でも常にそうであって欲しいとは限らない。他の場面では、可変な構造体はオブジェクトのアドレスだけを同値性の根拠として欲しいこともあるだろう。"Base.hash"関数を特化させてしまうと、そういったケースで融通が効かなくなってしまうのだ。そのため、"メモ化"関数のみが参照する新しい関数"メモ化用hash"を作り、その関数の振る舞いを変更するようにしたのだ。

マクロ化してみよう

ここまでメモ化について語ってきたが、いよいよ大詰めである。今の所の"メモ化"関数の使い方はこのようなものだ。

f(x) = sum(x)
g = メモ化(f)
g([1, 2, 3])

関数を定義し、使用する前に"メモ化"関数を被せる。悪くはない。悪くはないが、こうできた方がもっと素敵ではないだろうか？

@メモ化 f(x) = sum(x) #定義と同時にメモ化を宣言！
f([1, 2, 3]) #イエーイ！

"@メモ化"というのはマクロである。マクロがなんだかよくわからないという人は、 JuliaとLispのマクロの比較 を読んで欲しい。簡単に言えば、マクロは構文変換のための機能である。マクロは関数とは違い、プログラムの実行時には動かない。その時には既に仕事を終えている。マクロはプログラムが起動した後、実行される前の段階で動くのだ。入力はソースコード、出力は抽象構文木である。マクロを使うことで、与えられた関数定義を変換して、自動的にメモ化版の関数が呼び出されるような抽象構文木に変換してやろうというわけである。

では今からこのマクロを作っていくわけだが、何からとりかかればいいのかよくわからない。マクロを作るのは難しい。普通は関数のようには簡単には作れない。それは、通常の関数が数値や文字列や構造体のようなデータを入力とするのに対し、マクロはソースコードを入力とするからだ。ソースコードは複雑だ。その複雑なソースコードを分解したりこねくり回りたり組み合わせたりするのがマクロだ。マクロが難しいのは当然なのだ。

まずは落ち着いて、今からつくりたいマクロが、何を何に変換するものなのか、具体例を書き出してみるのが大切だ。我々はすでに具体的な"メモ化"関数を持っているので、"@メモ化"マクロでもこれを大いに活用しよう。

簡単な例を考えよう。

@メモ化 f(x) = sum(x)

と書くと、これが変換されて

_f(x) = fum(x)
f = メモ化(_f)

となってくれたならば、"f"を呼び出したつもりで、実際には"メモ化されたf"を呼び出すことができる。

もう1つ具体例を考えよう。

@メモ化 function get_east_asian_width(コードポイント)
    for 定義行 in lines
        can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
        if can_match
            return east_asian_width
        end
    end
end

と書くと、これが変換されて

function _get_east_asian_width(コードポイント)
    for 定義行 in lines
        can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
        if can_match
            return east_asian_width
        end
    end
end    

get_east_asian_width = メモ化(_get_east_asian_width)

となってくれたならば、"get_east_asian_width"を呼び出したつもりで、実際には"メモ化されたget_east_asian_width"を呼び出すことができる。ここまでくると読めてきた。"@メモ化"マクロは、引数として与えられた関数定義に対して次のように作用してあげたら良さそうである。

1. 引数として渡された関数定義(オリジナル関数)の関数名を取得する。
2. 取得した関数名を別名に変換して、オリジナル関数とそっくりのコピー関数を定義する。
3. オリジナル関数の関数名に、メモ化したコピー関数を代入する。

では取り掛かってみよう、と言いたいところだが、その前にマクロ作成に役立つツールを紹介しよう。

なお、今回作成するマクロは、Memoize.jl というライブラリのソースを参考にしている。

MacroTools

MacroToolsというのは、ライブラリの名前だ。マクロを作るために便利な関数を利用することができる。

https://juliahub.com/ui/Packages/MacroTools/38lnR/0.5.9

MacroToolsはJuliaの標準ライブラリではないので、ダウンロードとインストールが必要がある。しかし、ややこしい手順は必要ない。Juliaは標準でパッケージシステムを備えているので、このようなライブラリを非常に簡単にインストールすることができる。

Replで"]"を入力すると、パッケージモードというのに切り替わる。

(@v1.6) pkg> 

あとは"add MacroTools"と打ち込むだけで、自動でダウンロードとインストールが行われ、即座にMacroToolsのライブラリを使うことができる。

さらにそのコマンドを覚えるのすら面倒な私のような怠け者のための親切な仕組みが用意されている。MacroToolsがインストールされていない状態で、"using MacroTools"としてみると、Juliaは次のようなエラーメッセージを出してくれる。

ERROR: LoadError: LoadError: ArgumentError: Package MacroTools not found in current path:
- Run `import Pkg; Pkg.add("MacroTools")` to install the MacroTools package.

ここで指示された通り、"import Pkg; Pkg.add("MacroTools")"をコピーしてReplにペーストしてみると、見事MacroToolsがインストールされる。私はいつもこの方法でパッケージを取得している。

話が少し逸れたが、今回はMacroToolsのうち2つの関数を紹介したい。

splitdef

まず紹介するのは"splitdef"という関数である。これは、関数定義(の抽象構文木)を受け取り、関数名、引数、返り値、などの要素に分解してくれるやつだ。例えば、"f(x) = sum(x)"という関数定義に適用した場合、次のような辞書を返してくれる。

julia> using MacroTools
julia> dict = splitdef(:(f(x) = sum(x)))
Dict{Symbol, Any} with 5 entries:
  :name        => :f
  :args        => Any[:x]
  :kwargs      => Any[]
  :body        => quote…
  :whereparams => ()

combinedef

splitdefの逆の働きをするのがcombinedefである。これはsplitdefとは逆に辞書から関数定義(の抽象構文木)を作ることができる。

julia> dict
Dict{Symbol, Any} with 5 entries:
  :name        => :f
  :args        => Any[:x]
  :kwargs      => Any[]
  :body        => quote…
  :whereparams => ()

julia> dict[:name] = :_f

julia> combinedef(dict)
:(function _f(x; )
      sum(x)
  end)

splitdefとcombinedefが今回やりたいことに役立ちそうなのがよくわかると思う。

“@メモ化”マクロの実装

準備は整った。ではいよいよマクロの定義に入ろう。

第一ステップは、「引数として渡された関数定義(オリジナル関数)の関数名を取得する。」である。これには"splitdef"を使う。

using MacroTools

macro メモ化(関数定義)
    関数定義dict = try
        splitdef(関数定義)
    catch
        error("＠メモ化 は関数定義にのみ適用可能です")
    end
    関数名 = 関数定義dict[:name] 

第2ステップは、「取得した関数名を別名に変換して、オリジナル関数とそっくりのコピー関数を定義する。」である。次の処理である。

using MacroTools

macro メモ化(関数定義)
    ...
    非メモ化関数定義dict = copy(関数定義dict)
    非メモ化関数定義dict[:name] = Symbol("##非メモ化", 関数名)
    非メモ化関数定義= combinedef(非メモ化関数定義dict)

"Symbol("##非メモ化", 関数名)"という部分で、コピー関数の関数名を定義している。オリジナル関数の名前が"f"なら"##非メモ化f"だし、"hoge"なら"##非メモ化hoge"である。ここで"##"を先頭につけることで、普通にはコピー関数呼び出せなくなっている。ソースコード上は"#"はコメントとして認識されるからだ。

そして、"combinedef"で、コピー関数を構築している。

第3ステップは、「オリジナル関数の関数名に、メモ化したコピー関数を代入する。」である。そしてマクロの結果を返している。

using MacroTools

macro メモ化(関数定義)
    ...
    return esc(quote
        $(非メモ化関数定義)
        $(関数名) = メモ化($(非メモ化関数定義dict[:name]))
    end)
end

"quote"全体を囲う"esc"が気になるかもしれない。通常、マクロ定義の中で、"esc"で囲まれた部分は要注意だ。これは変数の保護を取り払うため、マクロ定義の外の変数と衝突してしまうからだ。そのため、マクロ展開の結果が関数の中に埋め込まれるような場合、その関数のローカル変数と同じ名前だと不具合の原因になってしまう。しかし、今回はあまり気にしなくていい。マクロ展開の結果生成されるものは、むしろ外部からぜひ呼び出して欲しいものだからだ。

まとめると次のようになる。

#メモ化.jl
using  MacroTools

macro メモ化(関数定義)
    関数定義dict = try
        splitdef(関数定義)
    catch
        error("＠メモ化 は関数定義にのみ適用可能です")
    end
    関数名 = 関数定義dict[:name]

    非メモ化関数定義dict = copy(関数定義dict)
    非メモ化関数定義dict[:name] = Symbol("##非メモ化", 関数名)
    非メモ化関数定義= combinedef(非メモ化関数定義dict)

    return esc(quote
        $(非メモ化関数定義)
        $(関数名) = メモ化($(非メモ化関数定義dict[:name]))
    end)
end

これで作りたいものができているだろうか？確認するには"macroexpand1"というマクロを使ってみると良い。

julia> @macroexpand1 @メモ化 f(x) = sum(x)
quote
    function var"##非メモ化f"(x; )
        sum(x)
    end
    f = メモ化(var"##非メモ化f")
end

いい感じだ。(実際の出力にはもう少し余分な情報が出ているが、ここでは消している。)もう1つ確認してみよう。

julia> @macroexpand @メモ化 function get_east_asian_width(コードポイント)
           for 定義行 in lines
               can_match, east_asian_width = get_east_asian_width(コードポイント, 定義行)
               if can_match
                   return east_asian_width
               end
           end
       end
quote
    function var"##非メモ化get_east_asian_width"(コードポイント; )
        for 定義行 = lines
            (can_match, east_asian_width) = get_east_asian_width(コードポイント, 定義行)
            if can_match
                return east_asian_width
            end
        end
    end
    get_east_asian_width = メモ化(var"##非メモ化get_east_asian_width")
end

少なくとも見かけ上は問題なさそうである。さらに確信を持つためには動作確認してみることが重要だ。

#メモ化_test.jl
@testset "@メモ化" begin
    count = 0
    @メモ化 function sum_with_count(a, b...; c, d...)
        count += 1
        return a + sum(b) + c + sum(x.second for x in d)
    end
    @test sum_with_count(1, 2, 3; c = 4, d = 5, e = 6) == 21
    @test count == 1 #初めての呼び出しなので副作用あり
    @test sum_with_count(1, 2, 3; c = 4, d = 5, e = 6) == 21
    @test count == 1 #メモ化が効いているので副作用なし
    @test sum_with_count(1, 2, 3, 7; c = 4, d = 5, e = 6) == 28
    @test count == 2 #別の引数での初めての呼び出しなので副作用あり
    @test sum_with_count(1, 2, 3, 7; c = 4, d = 5, e = 6) == 28
    @test count == 2 #メモ化が効いているので副作用なし
end

メモ化が効いていることを確認するために、あえて副作用のある関数をメモ化している。同じ引数の2回目の呼び出しで副作用が働いてないことが、メモ化が成功していることの根拠になっている。メモ化の本来の意味で言えば、2回目の呼び出しが高速化されていることを確認するのでもいいのだが、実行時間に依存するテストは不安定になりそうなのでやめておいた。これでマクロ版の"メモ化"が正しく動くであろうことを確認できた。

ついにマクロを書いてみたが、どうだっただろうか？今回、メモ化の仕事の大部分は関数が行い、最後の最後のちょっとした構文変換の部分だけマクロで書いた。ここだけはどうしてもマクロでなければできなかったからだ。マクロは難しいので、使うのは最低限の範囲に留めよう。しかし、マクロでなければできないタスクというのは確かにあるのだ。

不足していたケースの考慮

マクロまで書いてフィニッシュといきたいところだが、まだこのメモ化関数には不十分な点がある。細かい話になるが順番に見ていこう。

配列の中に可変な構造体がある時

可変な構造体が直接引数に来た時にはうまく動いてくれているが、引数の配列の中身にある時にうまく動くか心配だからだ。結論から言うと、心配して正解だ。次のテストは失敗する。

@testset "配列中の可変構造体" begin
    function f(arr)
        s = 0
        for a in arr
            s += a.数値 + sum(a.配列) 
        end
        return s
    end
    g = メモ化(f)
    a1 = メモ化テスト用構造体(1, [2, 3])
    a2 = メモ化テスト用構造体(4, [5, 6])
    a3 = メモ化テスト用構造体(7, [8, 9])
    arr = [a1, a2, a3]
    @test g(arr) == 45
    a1.数値 = 2 #a1(2, [2, 3])
    @test g(arr) == 46
    a1.配列[1] = 20 #a1(2, [20, 3])
    @test g(arr) == 64
    a1.配列 = [10, 20] #a1(2, [10, 20])
    @test g(arr) == 71
end

これは次の関数が、構造体の内部の変化を検知できないためだ。引数が配列のパターンは、if文はfalseとなるため、"Base.hash"が呼ばれることになる。

function メモ化用hash(x::Any, h::UInt)
    if ismutable(x) && isstructtype(typeof(x))
        return メモ化用hash_可変構造体(x, h) 
    end
    return Base.hash(x, h)
end

引数が配列のパターンの時には、配列の内部の要素に"メモ化用hash"関数が適用されるようにすれば、問題は解決する。

function メモ化用hash(arr::AbstractArray, h::UInt)
    h += UInt(0x678f70fafbaac9d0)
    for a in arr
        h = メモ化用hash(a, h)
    end
    return h
end

その他のコレクションの中に可変な構造体がある時

配列以外にも、タプルや辞書など、構造体を自身の内部に持つことのできるデータ構造がある。これらにも対応する必要がある。一気に掲載しよう。似たようなコードなので解説するところは特にない。また、テストコードはもっとつまらないので掲載しない。気になるのであればGitHubのコードを確認して欲しい。

#メモ化.jl
function メモ化用hash(arr::AbstractArray, h::UInt)
    h += UInt(0x678f70fafbaac9d0)
    for a in arr
        h = メモ化用hash(a, h)
    end
    return h
end

function メモ化用hash(tup::Tuple, h::UInt)
    h += UInt(0x3353154edfc87de2)
    for t in tup
        h = メモ化用hash(t, h)
    end
    return h
end

function メモ化用hash(dict::AbstractDict, h::UInt)
    h += UInt(0x832ca5a1cc82b534)
    for pair in dict
        h = メモ化用hash(pair.first, h)
        h = メモ化用hash(pair.second, h)
    end
    return h
end

function メモ化用hash(pair::Pair, h::UInt)
    h += UInt(0x5046feabcffb2cf8)
    h = メモ化用hash(pair.first, h)
    h = メモ化用hash(pair.second, h)
    return h
end

function メモ化用hash(set::Set, h::UInt)
    h += UInt(0x1ad119380dcd30ee)
    for elem in set
        h = メモ化用hash(elem, h)
    end
    return h
end

他に構造体を含む可能性のある要素はあるだろうか？あるかもしれないが、一旦ここまでにしておこう。ただ、想定外のコレクションが構造体を含んでいた時に、誤ったメモを取得する可能性を排除するために、次のようにしておこう。

#メモ化.jl
function メモ化用hash(x::Any, h::UInt)
    if ismutable(x) && isstructtype(typeof(x))
        return メモ化用hash_可変構造体(x, h) 
    end
    if isprimitivetype(typeof(x))
        return Base.hash(x, h)
    end
    throw(DomainError("メモ化用hashが想定外の型に対して適用されました"))
end

"Base.hash"を素朴に呼ぶのは数値などのプリミティブ型のみにしておき、複雑なデータ構造は自前の"メモ化用hash"や"メモ化用hash_可変構造体"が呼ばれることを前提に、それらのケースを抜けると例外が発生するようにしておく。こうすると、ケアしていないデータ構造の時には例外が発生して、不適切な場合にメモ化が適用されて誤作動することがなくなるのだ。

不変な構造体の時

さて、ここまで可変な構造体を目の敵にしてきたが、実際には不変な構造体も同じ話だ。不変な構造体はフィールドを直接変化させることはできないが、フィールドに配列のような可変なオブジェクトがあれば、その中身を書き換えること自体は可能だからだ。そのため、結局、不変な構造体も可変な構造体と同じ対応が必要になる。

不変な構造体も対象にした結果、次のようになる。テストコードが気になったら、GitHubで確認して欲しい。

#メモ化.jl
function メモ化用hash(x::Any, h::UInt)
    if isstructtype(typeof(x))
        return メモ化用hash_構造体(x, h) 
    end
    if isprimitivetype(typeof(x))
        return Base.hash(x, h)
    end
    throw(DomainError("メモ化用hashが想定外の型に対して適用されました"))
end

まとめ

長々と話したが、これでようやく一区切りだ。メモ化の対応も行い、戦況表示が遅い問題は解消されたと思う。今回はキャッシュ対応やメモ化など、少し技巧的な話題だった。随分細かい説明が続いてしまったが、マクロを登場させることができたのは僥倖だった。

さて、次回の方針については少し検討中だ。引き続き花子のスキルを実装しようかと思っていたが、ちょっとユーザーインターフェースにも凝りたくなってきた。ユーザーインターフェースはフレームワークの細かい使い方の話になりそうでやらないつもりだったが、このシリーズを初めて1年以上経過し、愛着も湧いてきている。かわいい我が子に綺麗なおべべを着せてやりたくなったというわけだ。まあ少し試してみて、うまくいかなければ何事もなかったかのように花子のスキルの実装を始めていることだろう。ではまた次回！

コード

今回のコードはGitHubの下記のページにアップしている。

https://github.com/muuumin-soft/julia-intro-prog/tree/main/rpg14

参考文献

Hands-On Design Patterns and Best Practices with Julia

https://github.com/JuliaCollections/Memoize.jl