1. hisaway

    No comment

    hisaway
Changes in body
Source | HTML | Preview

この記事は、fukuoka.ex Elixir/Phoenix Advent Calendar 2019 の4日目です。

昨日は@torifukukaiouさんの「Elixirを書いていると将棋が強くなります(新しいことをはじめよう)」でした.

本記事では,並列化コンパイラPelemayのコード変換機能実装を通して得られた知見を共有します.


並列化コンパイラ Pelemay

先日, PelemayというElixirの並列化コンパイラをリリースしました.

こんな使い方をします.

mix.exs
def deps do
  [
    {:pelemay, "~> 0.0"},
  ]
end

mix deps.get

defmodule M do
  require Pelemay
  import Pelemay

  defpelemay do
    def map_square (list) do
      list
      |> Enum.map(& &1 * &1)
    end
  end
end

上記の関数は与えられたリスト(数値のみで構成)の各要素を2乗する関数です.
defpelemay do ~ endで括った関数を並列化します.
defpelemayとは何か? マクロで作られたライブラリ特有の構文であります.

Pelemay v0.0.4では下記の条件を満たす式を静的に並列化します.
(並列化と言いいましてもマルチコアではなく,シングルコア上でSIMD(ベクトル演算)命令を出力するように裏で色々やります.)

  • Enum.mapに匿名関数を渡す
  • 匿名関数の処理内部が四則演算 +, -, *, / と剰余演算である関数remのみで構成されている
  • 匿名関数外の変数を使っていない

という具合に制約が多いまだまだ伸び代たっぷりなライブラリです.

そんなPelemayを実装する上で得られた知見を共有できればと思います.

動作環境

  • MacOS: 10.14.6
  • OTP 22/Elixir 1.9.0

Macroモジュール

私が一番お世話になったのが, Macroモジュールです. まんまですね

このモジュールの内,

  • Macro.unpipe/1  パイプで繋がった一連の式を加工しやすいように前処理する
  • Macro.prewalk/2 ElixirのASTを走査し,必要に応じてコードを書き換える補佐

上記2つの関数についてご紹介します.

Macro.unpipe/1

論よりRunです,ひとまず下記のコードをiexで実行して値を確認しましょう.

iex> ast = quote do: list |> Enum.map(&foo(&1)) |> Enum.map(&bar(&1))

おぞましい値が出ますね.抽象構文木といいます.
変数のastは Abstract Syntax Tree(抽象構文木)のことです.

以降,本記事で扱う変数astは上記のパイプで繋がった式を指します.

{:|>, [context: Elixir, import: Kernel],
 [
   {:|>, [context: Elixir, import: Kernel],
    [
      {:list, [], Elixir},
      {{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
       [{:&, [], [{:foo, [], [{:&, [], [1]}]}]}]}
    ]},
   {{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
    [{:&, [], [{:bar, [], [{:&, [], [1]}]}]}]}
 ]}

括弧の対応関係を読み切る必要はありません.

  • パイプとかEnumとかあるし,コンパイラはこんな風に情報を受けっているんだな
  • 括弧がネストしてるから再帰で走査する形っぽい?

という事だけ察してくださいませ.

それでPelemayというか, 私はこの表現をいじくるわけですがこのままだと目が疲れるのでなんとかしたい...
そこで登場するのがMacro.unpipeです.

名前の通り,パイプを消します.では,次のコードを実行します.

iex> Macro.unpipe(ast)

少しばかりおまけがついていますが,パイプが外れてリスト構造になりました.


[
  {{:list, [], Elixir}, 0},
  {{{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
    [{:&, [], [{:foo, [], [{:&, [], [1]}]}]}]}, 0},
  {{{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
    [{:&, [], [{:bar, [], [{:&, [], [1]}]}]}]}, 0}
]

リストということは...Enumが使えます!

つまり,メタプログラミングでもEnumが使えるということです.
(まぁ,中身は相変わらず多重のタプル{}があるんですが)

パイプを使ったコードをunpipeすることで得られるリストは,一番最初がデータ(変数)であることが自明になり,残りはデータ変換処理であることがわかります.

Macro.prewalk/2, 3

Pelemayでは, Enum.mapをサポートしていますが,サポートするためにはコードから探してくる必要があります.
そこで活躍するのがMacro.prewalk/2です.

元の説明を訳すと,深さ優先行き掛け順で走査するとあります.
とりあえず動作を確認しましょう.

iex> Macro.prewalk(ast, fn x -> x |> IO.inspect end)
{:|>, [context: Elixir, import: Kernel],
 [
   {:|>, [context: Elixir, import: Kernel],
    [
      {:list, [], Elixir},
      {{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
       [{:&, [], [{:foo, [], [{:&, [], [1]}]}]}]}
    ]},
   {{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
    [{:&, [], [{:bar, [], [{:&, [], [1]}]}]}]}
 ]}
{:|>, [context: Elixir, import: Kernel],
 [
   {:list, [], Elixir},
   {{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
    [{:&, [], [{:foo, [], [{:&, [], [1]}]}]}]}
 ]}
{:list, [], Elixir}
{{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
 [{:&, [], [{:foo, [], [{:&, [], [1]}]}]}]}
{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}
{:__aliases__, [alias: false], [:Enum]}
:Enum
:map
{:&, [], [{:foo, [], [{:&, [], [1]}]}]}
{:foo, [], [{:&, [], [1]}]}
{:&, [], [1]}
1
{{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}, [],
 [{:&, [], [{:bar, [], [{:&, [], [1]}]}]}]}
{:., [], [{:__aliases__, [alias: false], [:Enum]}, :map]}
{:__aliases__, [alias: false], [:Enum]}
:Enum
:map
{:&, [], [{:bar, [], [{:&, [], [1]}]}]}
{:bar, [], [{:&, [], [1]}]}
{:&, [], [1]}
1

また括弧がたくさん出てきますね.Macro.prewalk/2はコードの中間表現を1つずつ走査します.

このMacro.prewalk/2に渡す関数には,コードをどのように変更するのかを記述します.

試しに:Enum:Stringに変えてみましょう.

iex> replace = fn 
...>   :Enum -> :String
...>   other -> other
...> end
iex> Macro.prewalk(ast, &replace.(&1))

EnumがStringに変わりました.

{:|>, [context: Elixir, import: Kernel],
 [
   {:|>, [context: Elixir, import: Kernel],
    [
      {:list, [], Elixir},
      {{:., [], [{:__aliases__, [alias: false], [:String]}, :map]}, [],
       [{:&, [], [{:foo, [], [{:&, [], [1]}]}]}]}
    ]},
   {{:., [], [{:__aliases__, [alias: false], [:String]}, :map]}, [],
    [{:&, [], [{:bar, [], [{:&, [], [1]}]}]}]}
 ]}

Pelemayでのコード変換

実際には,パイプで繋がった一連の式を関数定義群から抽出しなくてはいけないので,Keyword.take/2doブロック内部の式を取ってくるといった処理が必要です.

その後,本記事で紹介したMacro.unpipe/1+@で前処理,Macro.prewalk/3で書き換えています.
unpipeした後は必然的にパイプを付け直さないといけないのですが,これはマクロとして定義されているパイプライン構文|>を展開するのと同じ動作で実現できます.(kernel.exから定義を引っ張ってきて少し改良)

なるべくシンプルかつ汎用的に使えるように実装しようとしているのですが,これが中々難しく手詰まっているところです.

まとめ

Elixirでコード変換をする上で,役立つ関数についてご紹介しました.


明日12/5は @tuchiroさんの「mqttライブラリ使ってみた記事」です.お楽しみに!さんの「mqttライブラリ使ってみた記事」です.お楽しみに!